Содержание к диссертации
Введение
1. Объект, цель и задачи исследования 10
1.1. Архитектура системы САГМ 10
1.1.1. Программное обеспечение локального сервера 11
1.1.2. Программное обеспечение удалённого сервера 12
1.1.3. Графический интерфейс системы
1.2. Постановка задачи исследования 18
1.3. Выводы по разделу 20
2. Численно-аналитический метод расчёта вероятностно-временных характеристик нестационарных систем обслуживания 21
2.1. Суть численно-аналитического метода решения систем дифференциальных уравнений 24
2.1.1. Алгоритм нумерации состояний НСО 25
2.1.2. Решение системы ОДУ. 26
2.2. Особенности программной реализации метода 29
2.2.1. Способ борьбы с погрешностью вычислений. 29
2.2.2. Оптимизация реализации численно-аналитического метода
2.3. Оценка точности метода 33
2.4. Сравнительная оценка скорости работы программной реализации метода 35
2.5. Рекурсивный алгоритм генерации матрицы коэффициентов для системы ОДУ 2.5.1. Суть метода 38
2.5.2. Алгоритм метода для двухканальной системы 40
2.5.3. Алгоритм метода для сетевой модели 44
2.5.4. Сортировка элементов матрицы 49
2.6. Выводы по разделу 52
3. Использование гипердельтной аппроксимации для построения имитационных моделей 53
3.1. Автоматизация процесса нахождения параметров гипердельтного распределения 55
3.1.1. Общее уравнение i-го начального момента гипердельтного распределения 55
3.1.2. Программная реализация метода Ньютона для расчёта параметров аппроксимирующего гипердельтного распределения
3.2. Проверка точности аппроксимирования гипердельтным распределением 62
3.3. Особенности применения гипердельтного распределения при имитационном моделировании 76
3.4. Выводы по разделу 79
4. Выбор и обоснование аппаратно программных средств «АСМИС», нагрузочное тестирование 80
4.1. Тестирование локального сервера 81
4.2. Тестирование удалённого сервера 99
4.3. Выводы по разделу 103
5. Методика определения достаточности программно-аппаратных компонентов, удовлетворяющих требованиям к оперативности обработки заявок .104
5.1. Место проблемы выбора и обоснования программно-аппаратных компонентов, удовлетворяющих требованиям к оперативности обработки заявок .104
5.2. Схема подготовки и решения задачи определения достаточности аппаратно-программных компонентов НСО 106
5.3. Выводы по разделу 109
Заключение 110
Список литературы 112
- Графический интерфейс системы
- Особенности программной реализации метода
- Особенности применения гипердельтного распределения при имитационном моделировании
- Схема подготовки и решения задачи определения достаточности аппаратно-программных компонентов НСО
Графический интерфейс системы
Отличительной чертой современных аппаратно-программных комплексов (АПК) является то, что при создании они, прежде всего, должны быть ориентированы на функционирование не только в нормальных, но и в критических (кризисных) условиях. Это обусловлено с одной стороны возрастанием угроз, вызванных техногенными, природными и человеческими факторами, с другой — желанием использовать уже существующие АПК для решения новых более сложных задач.
В рассматриваемых ситуациях мониторинг и прогнозирование должны сопровождаться целенаправленными процедурами реконфигурации структур (в общем случае, управления структурами) как самих АПК, так и систем управления (СУ) ими для обеспечения максимально допустимого уровня их работоспособности и пропускной способности. Для определения возможности реализации всех операций, связанных с технологическим циклом управления, на заданном временном интервале применяют математическое моделирование. Математической базой является теория массового обслуживания (ТМО), позволяющая решать разнообразные задачи анализа и синтеза АПК путем определения технико-экономических показателей эффективности функционирования комплексов в целом при известных технических параметрах их элементов и рабочей нагрузке. Большинство авторов используют модели ТМО в предположении, что очередь заявок бесконечна, существует стационарный режим, а коэффициент загрузки не превышает единицы [55, 65].
Однако наибольший практический и теоретический интерес представляют модели нестационарных систем обслуживания, учитывающие поведение АПК в контуре управления технологическими процессами и объектами, функционирующими в условиях перегрузок на заданном (директивном) временном интервале. Этим объясняется появление в последнее время публикаций, связанных с исследованием поведения моделей ТМО в переходных режимах [61, 60, 49, 64].
На основе результатов работ [13, 14, 46, 47] разработан комплекс программ [42] расчёта надежности и планирования испытаний программных средств, в котором системы обыкновенных дифференциальных уравнений (ОДУ) для различных моделей нестационарных систем обслуживания решаются с помощью численных методов. Популярным программным инструментом, например, является Matlab, предлагающий несколько процедур для решения систем ОДУ. Основными недостатками традиционных численных методов являются накапливаемая на каждом шаге интегрирования погрешность и время работы алгоритма. Причём, вычислительная погрешность может привести и к отсутствию физического смысла получаемого решения.
В частности, для решения систем, которые будут описаны в следующем разделе, была использована процедура ode45 из пакета Matlab (при настройках по умолчанию), основанная на паре вложенных методов Рунге—Кутты порядков 4 и 5, разработанных Э. Фельбергом [50]. Глобальная погрешность этой процедуры имеет порядок 0(h5), где h — максимальная величина шага, в данном случае, по времени. Положив число заявок на обслуживание равным 100 (что даёт 5151 дифференциальное уравнение в системе Чепмена—Колмогорова), при интенсивности поступления всех заявок 1, а интенсивности обработки 2, было замечено, что многие состояния имели отрицательную вероятность, в частности, вероятность состояния номер 5087 стала -9,271964480522870 Ю"9. Увеличение же точности расчётов значительно увеличило время работы программы.
В то же время, желание учёта большего числа факторов реальных процессов, подлежащих моделированию, приводит к увеличению числа уравнений Чепмена—Колмогорова относительно вероятностей состояний. Время численного решения такого рода систем уравнений, как показывают эксперименты, экспоненциально зависит от общего числа состояний систем обслуживания. Это накладывает серьезные ограничения на разрабатываемые модели нестационарных систем обслуживания.
Высказанные соображения свидетельствуют об актуальности разработки аналитического метода расчета вероятностей состояний нестационарных систем обслуживания с конечным источником (НСО), рассматриваемых в настоящей работе.
На основании этого было принято решение рассмотреть альтернативные методы расчёта систем дифференциальных уравнений. Одним из таких методов является численно-аналитический метод, предлагаемый в следующем параграфе.
Особенности программной реализации метода
Для контроля погрешности в программу была добавлена возможность задания точности чисел, т. е. определения номера десятичного знака после запятой, который округляется в арифметических операциях и все числа правее которого отбрасываются. Необходимо учитывать тот факт, что чем большая точность чисел используется, тем больше времени требуется на совершение арифметических операций с ними и, соответственно, тем дольше производится расчёт решения. В классе BigDecimal реализованы все необходимые в аналитическом методе арифметические операции кроме нахождения экспоненты. Данная функциональность была реализована в ходе разработки, в её основе лежит ряд Тейлора ех = Т,п-о—- (13) После реализации алгоритма с числами типа BigDecimal, его точность и, к сожалению, время работы значительно возросли. Так, например, при iV = 100, Я = 1, [І = 2 с использованием точности чисел в 1000 знаков расчёт вероятностей состояний занимал полтора часа.
В ходе анализа времени работы алгоритма было выяснено, что основное время занимает расчёт коэффициентов к по формулам (10)-(12). Для ускорения этой части программы было сделано несколько изменений в коде.
1. Изначально при вычислении коэффициентов по (11) выполнялся цикл оту = 0 до У = і. При такой реализации, при очередному, таком, что Vj 1, приходилось пересчитывать все предыдущие к, кратные кц, кратность которых больше 1. Это приводило к многократному пересчёту одних и тех же значений и значительно увеличивало время работы программы. После оптимизации цикл стал выполняться от j = і к j = 0. Таким образом, каждое значение к вычисляется только один раз.
2. Было установлено, что большинство элементов матрицы А равны 0, поэтому в (8) было добавлено условие: bij = wij aiwkWj, aiw 0, (14) что позволило значительно сократить время работы алгоритма, за счёт отбрасывания операций, не влияющих на результат.
3. Изначально в программе выделялась оперативная память для хранения всех значений Ь, но было замечено, что при вычислении значений кц, используются только значения bis, с тем же первым индексом і. Было принято решение выделять память только для хранения набора коэффициентов Ъц при фиксированном і, а при переходе к вычислению значений при новом і освобождать использованную память. Такая оптимизация позволила сократить требуемый размер памяти для хранения коэффициентов Ъ в (N + 1)(N + 2)/2 раз и, как следствие, увеличить скорость работы программы.
4. Большая часть алгоритма может выполняться в многопоточном режиме, поэтому были определены точки, в которых потоки должны синхронизироваться, и реализована многопоточная структура алгоритма. Этими точками при вычислении к для любого і являются: a. Окончание расчёта коэффициентов btj (14). b. Окончание расчёта коэффициентов kij, для которых аи = ап и Vj 1 (10) и для которых аи Ф ajj (11). c. Окончание расчёта оставшихся коэффициентов кц (11), (12), выполняющийся в один поток вычислений.
Кроме того была проведена оптимизация расчёта вероятностей состояний при вычисленных коэффициентах к:
Из формулы (7) видно, что значения Xj(t) для двух собственных чисел таких, что ан = ai+li+1, будут удовлетворять уравнению Xj+1(t) = t5q(t). Таким образом, при использовании этого уравнения в (7), удаётся значительно сократить время работы алгоритма.
Было замечено, что при вычислении вероятностей состояний на промежутке времени от t± до t2 с шагом h в (7) целесообразно сохранять значения экспоненты в отдельный вектор Е размерности К. Действительно, если значения экспоненты для момента времени t± сохранены, тогда для вычисления вероятностей состояний в момент времени t± + h можно воспользоваться выражением Xj (t + h) = tvJ_1eaJJhEj. Данная модификация метода значительно уменьшает время работы алгоритма. Алгоритм вычисления вероятностей состояний по (7) так же был разделён на потоки. Все перечисленные в данном пункте изменения программы значительно сократили время её работы. В последующих разделах представлено сравнение скорости и точности работы реализованного метода с Matlab. 2.3. Оценка точности метода
Одним из способов проверки точности работы метода является суммирование вероятностей всех состояний в какой-либо момент времени, так как суммарная вероятность всегда остаётся равной 1. В рассматриваемой модели НСО для всех заявок была установлена интенсивность поступления А = 1, интенсивность обработки [І = 2, число заявок взято iV = 100, точность чисел — 1000 знаков. Рассчитывались вероятности состояний при t = 50. Сумма всех вероятностей состояний, рассчитанных численно-аналитическим методом составила 1 + 616856 10"678. При этом, ни одна вероятность не была отрицательной. В Matlab сумма всех состояний была равна 1, но были состояния, вероятность которых меньше нуля, в частности состояние номер 5087 имело вероятность -9,271964480522870 Ю"9.
Для дополнительной проверки точности на Java был реализован метод метод Рунге-Кутты четвёртого порядка для решения систем дифференциальных уравнений с постоянным шагом. В таблице 2 приведены значения вероятности поглощающего состояния с номером 5150 при t = 50, 100, 150. Интенсивность поступления заявок А = 1, интенсивность обработки [І = 2, iV = 100. Шаг по времени в методе Рунге—Кутты обозначен h.
Особенности применения гипердельтного распределения при имитационном моделировании
Для разработки, обоснования архитектуры и тестирования различных систем наряду со стендовыми испытаниями широко применяется имитационное моделирование. Предположение о простейших законах распределения моделируемых случайных величин далеко от истинных и обосновывается лишь простотой применяемых математических моделей. Для устранения данного недостатка на практике используются аппроксимации фазовыми распределениями: неоднородно-эрланговское, гиперэкспоненциальное и распределение Кокса [45, 7, 36]. Использование неоднородно-эрланговского распределения для моделирования микропроцессорных систем электровоза рассмотрено в статье [6]. Однако при коэффициентах вариации аппроксимируемых распределений, где коэффициент вариации такой, что V T, (1) где n-число фаз, V - коэффициент вариации, параметры аппроксимирующего распределения становятся комплексно сопряжёнными, что делает невозможным их использование в имитационном моделировании. Увеличение числа этапов в коксовском распределении приводит к значительным затратам. Поэтому в качестве аппроксимирующего распределения предлагается использовать гипердельтное [35]. В данной статье рассматривается способ представления распределений, который называется гипердельтным распределением с использованием аппроксимаций по методу моментов.
Плотность гипердельтного распределения представлена в (2): п fa(t) = ClS(t-1i), (2) 7=1 П где с І - вероятности, удовлетворяющие условию, XQ =1 , а - дельта-функция г=1 Дирака. Очевидным является тот факт, что чем больше величина n, тем выше точность аппроксимирующего распределения. 3.1. Автоматизация процесса нахождения параметров гипердельтного распределения
Для автоматизации процесса расчёта параметров аппроксимирующего распределения, необходимо найти общее уравнение для вычисления его /-го начального момента. Для нахождения /-го начального момента найдём -ю производную преобразования Лапласа в точке 5 = 0.
Преобразование Лапласа для плотности гипердельтного распределения выглядит следующим образом: F(s) = L{f(t)} = Г e-stf(t)dt = Г e-st YS=i(Ci 8(t - Tt)) dt, где f(t) - плотность гипердельтного распределения, n - число этапов гипердельтного распределения. J0" e-st Z?=i(Cf6(t - T))dt = YS=1(cte-bs). Таким образом нулевой начальный момент равен 00 (-1)0 = Z=i(oe- ) = Y,f=1ct = 1. Первый начальный момент:v1 (-1)1 = Н=1( е- 5) ds = Z?=1(i СІ е-Ь )3=0 = Z?=1(i с{). Второй начальный момент: v2 (-1)2 = Д е- 5) d2s = ЕГ=1((- )2 СІ е-ь )3=0 = Т,=1((-п)2 СІ). Третий начальный момент: v3 (-1)3 = Н е- 5) d3s = Z?=1((i)3 ct е- )5=0 = Z?=1((i)3 СІ). Четвёртый начальный момент: v4 (-1)4 = YJl=1(CieiS). 0 d4s = І?=1((- І)4 СІ e- s)s=0 = ЕГ=1((- )4 c{). Таким образом k-й начальный момент равен: Vk = I]f=l((_it f c = Sr=i(tik Ci). (3)
Программная реализация метода Ньютона для расчёта параметров аппроксимирующего гипердельтного распределения Для нахождения параметров распределения с,- 3} необходимо решить систему нелинейных уравнений, представленную в (4), данная система получена из (3). С1+С2+... + Ск+... + С„ = 1 с,т1+с2т2+...+сХ+...+сХ = К (4) Ctf + С2Т2 + ...+CkTk+...+CnT2 = V2 Q7f + С2Т2 +...+ СкТк +...+ СпТкп = Vk с,т; + с2т2 +...+сктк +...+сх = Vi где vk - k-й начальный момент исходного распределения, а і и п такие, что / = 2и-1. При п = 2 параметры аппроксимирующего распределения находятся аналитически, система нелинейных уравнений (4) при этом принимает вид: С± + С2 = 1, СгТг + С2Т2 = vlt С±Т2 + С2Т22 = v2, СгТІ + С2Т2 = v3. При условии, что моменты v3, v2, v± известны, из системы (5) получаем: у3-у2Уг+ \v3-6v3v2v1-3v2v +4v3v\+4v. 7\,2 = 2(y2-vl) , (6) с Ц 1 + Зт v 2vl = . jv3-6v3v2v1-3v2v +4v3vf+4v2 2 \ у3 І В таблице 1 приведены значения аппроксимирующих коэффициентов для некоторых распределений при = 2. Таблица 1. Значения аппроксимирующих коэффициентов. Распр Плотность fa(t) = C t - TJ + C26(t - T2) еделе распределения Ci Q Тг 7-2 ние Экспо ненци f(t) = Хе и 1 V2 2 1+T 1 V2 2 V2 Xу 2J 2 V2 1 + T ально е Гамм fit) 1 + Vr + 1 1 - Vr + 1 r + 1 - Vr + 1 r + 1 + Vr + 1 а = хулу-1 exp(-Xt) (r-Dt 2Vr + l 2Vr + l X X Норм f(t) 1 1 a — a a — a ально cxpf !7f) 2 2 е = ,—00V27TCT t 00 Равно мерно е 1 m = \-,0 t a КО, t 0, t a 2 2 a a t2 Релея fix) = t exp V2o a2 ,t 2 + V (3 - 7Г) л/6тг2 - 39ТГ + ) 2 X V (3 - 7Г) л/6тг2 - 397Г + ) Л/7Г-Л/67Г2-397Г + л/2 (4 - я) л/тг - л/бтг2 - 397Г + V2(4 - тг) 0 Аналитическое решение данной системы уравнений при 2 вызывает значительные трудности, поэтому было принято решение разработать численный алгоритм решения данной системы на основании метода Ньютона для решения систем нелинейных уравнений. Для вычисления элемента матрицы Якоби системы (4) предлагается следующая формула: Wt1= fl,z = l,y =ymax/2 p,z = l,y ymax/2 Tr\i \,j =jmJ2 [Т]-2 (i-\) Cj,i l,j jmax /2 где Ушах - число столбцов матрицы. Для вычисления значений столбца F, использовалась следующая формула: Ft = с;. -i,7=i Y,Cj T-\i \ І j где - число этапов в аппроксимирующем распределении. Для вычисления решения на каждом шаге в методе Ньютона рекомендуется использовать формулу: п+1 = п F 1 " W Для простоты формула была преобразована в: Хп+1 =хп FK ) W l (Х„ ) , (7) Данный алгоритм обеспечивал нахождение решения системы нелинейных уравнений только из достаточно близкого начального приближения 1 В [17] описан алгоритм, позволяющий автоматизировать процесс поиска этого приближения. На основании этого алгоритма, формула (7) приняла вид: Xn+X=Xn-W l(Xn) (F(Xn)-a (F(Xo)) где a = max 0,1 ( r т + УW faJW2 )] I 2mN\\F(xJ\\ \\W-l(xJ\\2 4j-( J dlft А=1 dx j dx h n где m - количество уравнений в системе, N такое, что. dxdx
Для проверки точности аппроксимации, были решены следующие задачи: существует некоторое обслуживающее устройство, обрабатывающее заявки. Время обработки заявок случайно и распределяется экспоненциально. Начальные моменты времени обработки заявок измерены. Необходимо аппроксимировать время обработки заявки, и сравнить результаты с исходным (экспоненциальным) распределением. На рисунке 1 приведены графики функций аппроксимируемого (экспоненциального) распределения и аппроксимирующего (гипердельтного) с числом этапов n=7 [5]. Рис.1. Пример аппроксимации гипердельтным распределением. В таблице 2 приведены начальные моменты аппроксимируемого и аппроксимирующего распределений.
Схема подготовки и решения задачи определения достаточности аппаратно-программных компонентов НСО
Для определения возможности реализации всех операций, связанных с технологическим циклом локального сервера, было проведено его нагрузочное тестирование с помощью специализированной программы, описанной в [26], которое показало, что уже при 4, подключённых к системе датчиках, возникают ошибки в системе. Анализ этих ошибок показал, что они связаны с технологическими операциями взаимодействия программного обеспечения локального сервера с базой данных. В качестве базы данных использовалась SQLite [59]. Особенность этой базы данных такова, что она не предоставляет отдельного сервиса для выполнения операций чтения и записи данных, а интегрируется в разрабатываемую программу в качестве сторонней программной библиотеки. Кроме того, в качестве хранилища данных используется единственный файл, и разработчику необходимо самому заботиться о синхронизации потоков чтения и записи данных.
Для получения более полной картины и возможности определения оптимального числа датчиков, подключаемых к одному локальному серверу была разработана модель нестационарной системы обслуживания (НСО) и проведено её аналитическое и имитационное моделирование [8].
Порядок поступления и обработки заявок: 1. В модели используется только 1 тип датчиков. 2. Детерминировано через интервал времени в систему поступают заявки от датчиков. Так как датчики одного типа, и заявки от всех датчиков обрабатываются непрерывно, было принято решение объединить каждую группу заявок приходящих одновременно в единую заявку. 3. Детерминировано через интервал времени поступает заявка второго типа, связанная с технологическим циклом синхронизации данных между локальным и удалённым сервером. 4. Важно, что бы после одновременного поступления двух заявок второго и первого типа, они успели обслужиться до момента поступления следующей заявки.
В ходе натурного эксперимента были получены начальные моменты времени обслуживания заявок первого и второго типов. С их помощью были рассчитаны параметры аппроксимирующего гипердельтного распределения программой [29] по методу моментов [38-41]. Параметры данного распределения представлены ниже: Г 0.99 . 0.0018 .0.0027. 0.003 . 0.0019 . 3.43У - 4 .2.6SE - 5 } Ці U.628E-91 0.137 0.192 0.265і 0.336 0.41 0.49 У Г 0.99 , 0.002 ,0.0028, 0.0031, 0.0016 , 1.834Е -4 , 1.996Е - 5) Ц2 І3.793Е-81 0.696 1.0001і 1.397 І 1.762 l 2.2458 l 2.647 У K = {5\1}. Описанная выше имитационная модель была реализована программно [25]. В таблице 1 приведены вероятности свободного состояния системы в различные моменты времени, полученные с помощью имитационной модели.
Для проверки полученных результатов была разработана аналогичная имитационной численно-аналитическая модель, которая описывается следующими параметрами: 1. Имеется одно обслуживающее устройство. 2. N=2 - количество типов заявок. Приоритет заявки типа 1 выше, чем у типа 2. 3. Заявки каждого типа поступают через детерминированные интервалы времени. 4. X - вектор интенсивности поступления заявок, причём At -интенсивность поступления заявок типа і. 5. Закон распределения времени обслуживания заявок -экспоненциальный. 6. p - вектор интенсивности обслуживания, причём At - интенсивность обслуживания заявок типа і. 7. К - і -я компонента вектора, определяет количество заявок типа і, поступающих в систему за интервал моделирования. В каждый момент времени система описывается следующими параметрами: 1. п, і-я компонента вектора определяет количество заявок типа і, находящихся в НСО в данный момент. 2. in, і-я компонента вектора определяет количество заявок типа і, уже получивших обслуживание и покинувших НСО. Время обработки заявок в модели распределяется экспоненциально. Для эксперимента были использованы следующие исходные данные: L 5J \І = {3.3663,497}, К = {5\1}. Описанная модель была реализована программно [27]. В таблице 2 приведены вероятности р свободного состояния системы в различные моменты времени t, полученные с помощью аналитической модели.
При аппроксимировании гипердельтным распределением используется 13 начальных моментов, а при аппроксимировании экспоненциальным – только 1, очевидно, что гипердельтная аппроксимация будет значительно точнее повторять свойства исходного распределения. Поэтому для сравнения работы обеих моделей в имитационной модели генератор случайных величин по гипердельтному закону распределения был заменён на генератор случайных величин по экспоненциальному закону распределения. В таблице 3 приведены вероятности p свободного состояния системы в различные моменты времени t, полученные с помощью имитационной модели с экспоненциальным генератором случайных величин и исходными данными такими же, как и в аналитической модели, описанной выше.