Приложения теории массового обслуживания. Учебник для студентов высших учебных заведений, обучаемых по направлениею
 Скачать 1.27 Mb.
|
|
9.2 Синтез моделирующих алгоритмов Основными принципами построения моделирующих алгоритмов есть: – принцип, который позволяет определять последовательные состояния системы через некоторые интервалы времени (принцип Δt); – принцип последовательного проведения требований. Первый принцип состоит в том, что состояния СМО определяются для моментов времени, разделенных одинаковыми интервалами времени Δt. При этом для большинства таких моментов состояние СМО не изменяется в сравнении с предыдущим моментом, т.е. весь интервал времени Δt есть неинтересным для исследования. Интерес представляют особые состояния, отвечающие моментам поступления требований в систему и моментам выхода требований из неё. При увеличении Δt растет вероятность попадания в интер- вал особого состояния и снижается точность и достоверность моделирования (за счет возможного попадания в один интервал двух и больше особых состояний). Уменьшение Δt приводит к резкому росту времени моделирования. При моделировании процессов обработки требований в СМО удобнее строить моделирующие алгоритмы по принципу последовательного проведения требований. Его идея состоит в последовательном воспроизведении истории отдельных требований в порядке поступления их в систему: алгоритм обращается к сведениям о других требованиях лишь в том случае, если это необходимо для решения вопроса о дальнейшем порядке обслуживания данной заявки. Такого рода моделирующие алгоритмы экономные, не требуют специальных мер по учету особых состояний системы, н они имеют довольно сложную логическую структуру и не всегда доступные для построения. При моделировании приходится решать следующие задачи: 1. Получение последовательности случайных чисел, равномерно распределенных в интервале [0, 1]. 2. Преобразование чисел полученной последовательности в величины, имеющих некоторую определенную функцию распределения. 3. Построение логической схемы алгоритма, учитывающего особенности работы СМО, что моделируется. 4. Построение алгоритмов фиксации состояний СМО и обработки результатов моделирования. 5. Выбор количества реализаций в соответствии с заданной точностью обусловленных характеристик СМО. 6. Моделирование на ЭВМ. 7. Окончательная обработка и анализ результатов. Для моделирования потоков событий необходимы алгоритмы выработки случайных величин, соответствующих длительностям интервалов времени между соседними событиями необходимого вида потока. Возможную нестацио- нарность потоков можно организовать введением в алгоритм формирования случайных величин зависимости от текущего времени поступления (или начала обслуживания) определенного требования. Эти случайные величины должны быть распределены по определенному закону, т.е. имеет место задача создания 96 последовательности случайных величин с определенной функцией распреде- ления. Сначала получают последовательность чисел, равномерно распределен- ных в интервале [0, 1], а потом эту последовательность превращают в последовательность случайных величин с необходимой функцией распределе- ния. Способы получения случайных чисел с равномерным распределением: – алгоритмический – получение ряда псевдослучайных чисел; – начальное занесение в память ЭВМ таблицы случайных чисел, полученных из натурного эксперимента испытания СМО. При первом способе последовательность псевдослучайных чисел вырабатывается самой ЭВМ с помощью специальных алгоритмов. При этом предъявляются следующие требования: – получаемая последовательность чисел должна иметь статистическую структуру, очень близкую к структуре равномерной совокупности; – количество операций, необходимое для выработки каждого числа последовательности, не должно быть слишком большим. Последовательность псевдослучайных чисел характеризуется периодич- ностью повторения. Надо так подбирать „случайные” числа х i (i = 1, 2, ..., m), чтобы длина периода повторения была наибольшей. Для обоснования „случайности” последовательности псевдослучайных чисел необходимо использовать систему следующих тестов: – проверка частот повторения чисел из разных интервалов; – проверка пар; – проверка интервалов; – проверка комбинаций. Множество псевдослучайных чисел, удовлетворяющее всем этим тестам, называется локально случайным. Все упомянутые выше тесты характеризуются одним общим свойством: испытанные псевдослучайные числа (или разряды в них) классифицируются по некоторыми признаками (разным для каждого теста) и полученное эмпирическое распределение сравнивается с теоретичес- ким. Для сравнения применяются обычные статистические критерии. Имея случайные числа, равномерно распределенные на интервале [0, 1] можно получить последовательность случайных величин ξ с заданной плотностью распределения f (х), если решить уравнение a U dx x f ) ( , где U – число из исходной равномерной последовательности; а – минимально возможное число из последовательности случайных величин с плотностью распределения f(х) Наиболее распространенными есть три подхода к статистическому моделированию систем массового обслуживания: – моделирование марковского процесса; – моделирование полумарковского процесса; – моделирование реального процесса обслуживания. 97 9.3 Моделирование марковского процесса В СМО поступает поток требований с функцией распределения интервала времени между требованиями А(z). Длительность обслуживания случайная величина с функцией распределения В(x). Определить характеристики QoS. Моделирование марковского процесса возможно только для экспонентных законов, где функция А(z) = 1 – e -λz и В(x) = 1 – e -μx . При этом работа m-серверной системы с потерями описывается марковским процессом х(t), где его состояния принимают значения 0, 1, 2, ..., m. Любая траектория марковского процесса устроена таким образом, что время пребывания ξ и в і-м состоянии имеет экспонентное распределение с параметром λ + i, т.е. t i i e t P ) ( (9.1) В момент выхода из этого состояния осуществляется переход в состояние i + 1 с вероятностью i p i (9.2) или в состоянии i – 1 с вероятностью i i q i (9.3) При i = m возможен переход только в состояние m – 1 с вероятностью, равной 1 (рис. 3.23, а). Поэтому, при воссоздании работы системы необходимо моделировать два случайных механизма: время пребывания в і-м состоянии согласно (9.1) и вероятности переходов по (9.2) и (9.3), что показано на рис. 9.1. а) б) Рисунок 9.1 – Траектория марковского процесса со случайным (а) и детерминированным (б) временами пребывания в состояниях Итак, для моделирования необходимы: программа реализации случайных величин, распределенных по экспонентному закону (9.1); программа генериро- вания равномерно распределенных случайных чисел для выбора направления переходов по (9.2) и (9.3); ячейки памяти для фиксации текущего времени системы, которое меняется прыжками в соответствии со случайными периодами пребывания в последовательных состояниях, и n разрядов (а не m ячеек) для записи номеров занятых серверов или одна ячейка для записи количества занятых серверов. Такой подход дает большую экономию машинной памяти, что особенно важно при моделировании сложных систем. t i i -1 i+1 i i i t i e ) ( t i i - 1 i+1 i i i i 1 98 9.4 Моделирования вложенной цепи Маркова Из анализа свойств траектории марковского процесса х(t) следует, что при вычислении оценки среднего количества занятых серверов случайные периоды пребывания в отдельных состояниях можно заменить их средними значениями. Рассмотрим траекторию процесса х(t) к моменту Т N , то есть к моменту N-го перехода. Необходимо вычислить dt t x f T T M N T N N j 0 ) ( 1 ) ( (9.4) В нашем случае f[х(t)] = i, если х(t) = i , i = 0, 1, ..., m. Функционал (9.4) представляет собой случайную величину, зависящую от выборочной траектории процесса х(t). При замене ξ и случайного времени пребывания в состоянии i-го средним значением 1 / (λ + i) (рис. 9.1, б) среднее значение функционала (9.4) сохраняется неизменным, а его дисперсия существенным образом уменьшается, так как устраняется один из двух случайных механизмов, порождающих траекторию x(t), а именно случайные распределения (9.1). Уменьшение дисперсии является первым преимуществом такого подхода к статистическому моделированию, а отсутствие потребности в моделировании случайных интервалов пребывания – второй. Опишем этот алгоритм моделирования в общем случае. Пусть данный однородный марковский процесс х(t) с дискретным множеством состояний S, обусловленный матрицей интенсивностей перехода A = ||a ху ||, х, y S. Траектории процесса х(t) являются ступенчатыми функциями и имеют простое вероятностное содержание. Если в момент t процесс х(t) находится в состоянии х, то время, которое осталось находиться в этом состоянии t x есть случайной величиной, распределенной по экспонентному закону z a x xx e z t P В момент выхода t + t х процесс переходит в состояние у с вероятностью xx xy xy a a p , x y , S y Величины р ху есть переходными вероятностями вложенной цепи Маркова. На процесс х(t) можно смотреть как на марковскую цепь с присоеди- ненными случайными величинами. В состоянии х присоединенной случайной величиной считаем t х – случайное время пребывания в этом состоянии. Результатом моделирования обычно есть среднее значение интеграла некоторой функции f(х), определенной над процессом х(t) согласно (9.4). В этом случае выгодно заменять t x на среднее значение 1 / (–a хх ). Этот алгоритм можно применить и в случае произвольных законов. Надо только их предварительно аппроксимировать такими распределениями, которые являются линейными комбинациями или свертками экспонентных распределений. Это приводит к некоторому увеличению числа состояний, тем не менее, как показывает практика моделирования, получается экономия машинного времени и объемов памяти. 99 9.5 Моделирование реального процесса обслуживания При имитационном моделировании алгоритм воссоздаёт процесс работы системы во времени, имитируя шаги процесса или элементарные явления с сохранением их временной и логической структуры. Алгоритм моделирования таков, чтобы за минимальное время получить статистические оценки макси- мальной точности. Есть несколько подходов к имитационному моделированию СМО. Один из них – это моделирование реального процесса обслуживания входного потока требований. Здесь используются подпрограммы реализации двух случайных величин: соответственно функции распределения интервалов времени между требованиями A(z) и функции распределения длительности обслуживания B(x) (см. гл. 3). Процесс прибытия требований в систему моделируется как рекуррентный – момент прибытия очередного требования получаем добавлением случайного интервала A(z) к предыдущему, а моменты освобождения серверов – добавлением к текущему моменту времени случайной длительности обслуживания B(x). Интервалы формируются датчиками псевдослучайных чисел, настроенными на нужные законы распределения. Случайные величины A(z) и B(t)с нужным законом распределения получаются из последовательности случайных величин с равномерным распре- делением на отрезке [0, 1], а те – из последовательности случайных величин, распределенных по закону Бернулли с параметром p = 0,5. Для получения случайных величин с нужной функцией распределения F(t), случайная величина t вычисляется как обратная функция F –1 от аргумента, которым есть величина x, равномерно распределенная на отрезке [0, 1], то есть t = F –1 (x) [2]. Поток требований можно задать рядом интервалов времени z между требованиями. Для моделирования любого потока достаточно на i-м шаге получить значение величины z i , с соответствующей моделированному потоку функцией распределения F(z). В пуассоновском потоке с параметром экспо- нентная функция распределения z между i-ми (i - 1)-м требованиями такая: z dt i e z F 0 1 ) ( , (9.5) где – параметр потока на интервале [0, z]. Для моделирования потока с параметром необходимо найти обратную функцию к функции (9.5) и для экспонентного распределения получаем л ) 1 ln( i i x z (9.6) Плотность гиперэкспонентного распределения определяется как z z e p e p z p 2 1 л 2 2 л 1 1 л л ) ( (9.7) Это значит, что с вероятностью p 1 интервал времени между требованиями имеет экспонентное распределение с параметром 1 , а с вероятностью p 2 – с параметром 2 (соответственно, p 1 + p 2 = 1). Для моделирования такого потока требований используется вспомогательный датчик случайных равномерно распределенных чисел на интервале [0, 1] y, задающий вероятности p 1 и p 2 100 (p 2 = 1 – p 1 ). Случайная величина z i определяется в зависимости от полученного значения p 1 и соответственно выражению (9.6), поэтому 1 2 1 1 при л ) 1 ln( л ) 1 ln( p y x p y при x z i i i i i (9.8) Итак, при получении от вспомогательного датчика случайной величины y i , не превышающей заданной вероятности p 1 , интервал z i формируется исходя из значения параметра 1 . В противоположном случае (y i > p 1 , „сгенерирована” вероятность p 2 ) – исходя из значения параметра 2 . Этот способ очень простой и не требует нахождения обратной функции к плотности (9.7). Самоподобный поток можно получить от суперпозиции нескольких независимых с одинаковым распределением ON/OFF источников, интервалы между ON и OFF периодами которого имеют эффект Ноа. Именно эффект Ноа в распределении длительностей ON/OFF периодов есть базовым при моделировании самоподобного трафика и он есть синонимом бесконечной дисперсии. Математически для достижения этого эффекта можно использовать распределение Парето, которое еще называют „распределением с длинным хвостом”. Плотность распределения Парето задается функцией: 1 ) ( a x b b a x f , где a – параметр формы, b – мода распределения (здесь это минимальное значение случайной величины x). Причем, при a 2 дисперсия бесконечна (что и нужно в качестве одного из условий самоподобия). Наличие в распределении так называемого „длинного хвоста” обеспечивает свойство пачечности трафика, поскольку в распределении сильно возрастает вероятность длинных интервалов между требованиями (например, отсутствие пакетов на интервале) и для „поддержки” заданного среднего значения количества требований необходима их концентрация (увеличение) на других интервалах времени. Параметр формы a и параметр Херста H находятся в такой зависимости: 2 3 a H В практическом моделировании распределение Парето получается путем перехода от равномерного распределения методом обратной функции: a i i U b z , где z i – i-й интервал между требованиями, U – случайное число, равномерно распределенное на интервале [0, 1]. Алгоритм моделирования на рис. 9.2 позволяет исследовать СМО типа GI/G/m/r. При этом могут быть любыми тип входного потока, распределение длительности обслуживания и дисциплина обслуживания – с потерями при r = 0, с неограниченной очередью при r = ∞, и комбинированная при 0 < r < ∞. 101 О ч и с т к а с ч е т ч и к о в , Т = 0 , Т 1 = 0 , O j = , j = 1 … m Н а ч а л о Ф о р м и р . z i T = T + z i T = O T + z i > O O = m in [O j ] P k = P k + (T - T 1 ) T 1 = T k = K m a x k = k - 1 P k = P k + (T - T 1 ) T 1 = T k = k + 1 O j = d = d + 1 Ф о р м и р . z i В и б о р n Ф о р м и р . O n s = s + 1 Ф о р м и р . z i Д а Н е т Н е т Н е т Д а Д а s > S m a x И з м . Y о б с л P B = d / (d + s ) P w = C w / s З м . Y в х P k = P k / T , k = 0 … K m a x К о н е ц k > m Н е т С w = С w + 1 W k = T k < m Д а Д а s = s + 1 Н е т W i = W i+ 1 i= m + 1 … K m a x Ф о р м и р . O j И з м . Y в х T C w = T -W m + 1 Рисунок 9.2 – Алгоритм имитационной модели 102 Для основных переменных имитационной модели приняты следующие обозначения (назначения других переменных указаны далее по тексту): s – текущее количество обслуженных требований; S max – максимальное количество обслуженных требований; d – количество потерянных (не обслуженных) требований; k – текущееколичество требований в системе (в серверах и очереди); r – количество комплектов ожидания; m – количество серверов в системе; n – номер занимаемого сервера (n m); K max – максимальное количество требований в системе (K max = m + r); С w – количество требований, попавших в очередь на ожидание. Работа модели начинается с установки в нуль таймера (счетчика) текущего времени T, таймера момента предыдущего события T1 и всех других накопительных счетчиков. Моментам выхода из системы требований приписываются значения, которые превышают предельное значение таймера T (все серверы свободные). Момент выхода требования из системы соответствует моменту освобож- дения сервера и записывается в индивидуальную ячейку памяти, закрепленную за каждым сервером. При занятии сервера в нее записывается момент его буду- щего освобождения, найденный как сумма значений таймера текущего времени и длительности обслуживания B(t). При освобождении сервера в эту ячейку записывается такое значение (например, 10 99 , „бесконечность”), которого никогда не достигнет в результате всего времени моделирования таймер T. После сброса схемы в исходное состояние формируется случайный момент z i прибытия i-го требования. Из ячеек памяти, закрепленных за каждым сервером, выбирается минимальный из моментов освобождения серверов O j (j – номер освобождающегося сервера). Вариант обработки текущего события определяется соотношением между T + z i и O j . Если T + z i min[O j ], то текущим событием есть прибытие требования. Соответственно перемещается таймер текущего времени T. К счетчику P k времени нахождения системы в состоянии с k требованиями (в серверах и в очереди) прибавляется разность T – T1 и обновляется значение T1. Если новое требование застает в системе K max требований (заняты все m серверов и все r комплектов ожидания, т.е. k = K max ), то к счетчику отказов d прибавляется 1. Далее формируется момент z i+ 1 прибытия нового требования. После подпрограммы измерения избыточной нагрузки выполняется возвращение к оператору проверки условия T + z i > O j (поскольку z обновленное). При наличии в системе свободных мест (серверы или комплекты ожидания) k < K max . Поэтому текущее значение количества требований в системе k увеличивается на единицу и проверяется наличие свободных серверов. Если k > m,то их нет, соответственно данное требование направляется в комплект ожидания. При этом счетчик задержанных требований C w увеличивается на единицу, а в закрепленной за комплектом ожидания ячейке памяти W k записывается момент занятия T. Потом формируется момент 103 прибытия очередного требования z i+1 и запускается подпрограмма измерения входной нагрузки Y вх Если есть хотя бы один свободный сервер (k m), то определяется его номер n по наличию признака „” в закрепленной за ним ячейке памяти. Далее формируется момент будущего освобождения O n = T + B(t) n-го сервера и записывается в его ячейку памяти. Потом счетчик количества обслуженных требований s увеличивается на 1. После подпрограммы измерения входной нагрузки Y вх формируется следующий момент z i+1 прибытия нового требования. После подпрограммы измерения обслуженной Y обсл нагрузки выполняется проверка достижения заданного количества обслуженных требований S max . Если предел количества обработанных требований не достигнут, то выполняется возвращение к оператору поиска минимального из моментов освобождения серверов O j . В противном случае ведется расчет стационарных вероятностей P k , которые определяются как доля общего времени T, в течение которого в системе было занято ровно k мест (серверов и комплектов ожидания). Для этого накопленные значения счетчиков P k делятся на значение таймера общего времени моделирования T. Вероятность потерь по времени P t соответствует доле времени, в течение которого в системе были занятые все m серверов, или отношению суммарного времени занятия m серверов за интервал времени наблюдения к длине этого интервала, то есть P k / T при k = m. Вероятность потерь по требованиям P B находится из отношения количества потерянных требований d к общему количеству входных требований d + s (потерянных и обслуженных). Вероятность ожидания P w>0 находится из отношения количества задержанных требований C w к общему количеству обслуженных требований s. Если T + z i > min[O j ], то очередным событием есть завершение начатого обслуживания и освобождение места в системе (сервера или комплекта ожида- ния j). Здесь также перемещается таймер текущего времени T, к счетчику P k времени пребывания системы в состоянии с k занятыми местами прибавляется разность T – T1 и обновляется значение T1. Потом количество занятых мест (количество обслуженных системой требований) k уменьшается на единицу. При k m есть очередь, а поэтому, после освобождения сервера из первого (головного) комплекта ожидания ожидающее требование, передается сразу же в этот сервер на обслуживание. При этом количество обслуженных требований s увеличивается на 1. Длительность ожидания каждого требования из очереди, которую рассчитывают как разность между текущим моментом времени T и моментом времени постановки требования в очередь на ожидание (записано в ячейку W m+ 1 ), накапливается в специальном массиве T Cw для определения функции распределения длительности ожидания и других моментов. Вслед за этим требования (записи в ячейках памяти о моментах постановки в очередь), находящиеся в комплектах ожидания начиная из второго, последовательно перемещаются в комплекты с номером на единицу меньшим (обслуживание требований происходит по правилу FIFO). Потом для данного сервера, который принял требование из очереди на обслуживание формируется момент будущего освобождения O n = T + B(t) и записывается в его ячейку памяти. 104 Если k < m, то очереди нет и освобождается сервер системы. В ячейку памяти, закрепленную за освобожденным сервером j, записывается „бесконеч- ность” – признак свободности сервера. После этого выполняется переход на выбор следующего минимального из моментов освобождения серверов O j Подпрограммы „измерения” обслуженной и входной (сумма обслуженной и избыточной) нагрузок и их дисперсии содержат массивы для сохранения всех интервалов времени между требованиями и всех длительностей обслуживания требований. Обслуженная нагрузка определяется из отношения суммарного времени занятия всех серверов к общему времени наблюдения. Входная нагрузка определяется из отношения среднего времени занятия сервера к среднему времени интервала между двумя требованиями (M t / M z ). Она же определяется и как среднее число требований за среднюю длительность занятия сервера M t . При этом дисперсия нагрузки находится как дисперсия количества требований за M t для всех интервалов M t , содержащихся в периоде наблюдения. Для исследования системы с дисциплиной обслуживания с потерями необходимо выбрать количество комплектов ожидания r = 0, при этом автоматически K max = m. Для проверки корректности построения имитационной модели необходимо выполнить следующие тесты: – проверка „случайности” генератора равномерно распределенных чисел на интервале [0, 1] по критерию 2 Пирсона ; – проверка произвольно распределенных случайных чисел по центральным моментам распределения, коэффициентам асимметрии и эксцесса. Можно испытать имитационную модель на получение заранее известных результатов. Для этого генерируется пуассоновский поток (экспонентное распределение интервалов времени между требованиями) и значения вероятностей потерь сравниваются со значениями формулы Эрланга. Моделирование функций A(z) и B(x) путем перехода от равномерного распределения методом обратной функции выполняется по формулам табл. 9.1. Таблица 9.1 – Метод моделирования случайной величины Вид функции Параметр распределения Плотность распределения Способ моделирования Экспонентная λ – интенсивность x e i i U x ln 1 Релея b – мода распределения 2 2 2b x e b x i i U b x ln Вейбулла a – параметр формы a x a e ax 0 1 0 a i i U x / 1 ln 1 Парето a – параметр формы b – мода распределения (b -минимальное значение) 1 a x b b a a i i U b x / 1 |