Основы дискретно-событийного моделирования СМО
Лекция № 5
Тема: Типы моделей СМО
План лекции
1. Типы моделей СМО
2. Формула Литтла
3. Одноканальные СМО
4. Многоканальные СМО
5. Основы дискретно-событийного моделирования СМО
5.1. Основные понятия моделирования СМО
5.2 Пространство состояний СМО
5.3 Пример построения модели СМО
Типы моделей СМО
В теории СМО рассматриваются только такие модели, параметры эффективности которых можно получить аналитически в замкнутом или числовом виде. Для обозначения таких моделей СМО часто используют запись, предложенную Кендаллом:
,
где a – распределение времени поступления требований,
b – распределение времени обслуживания,
c – количество устройств обслуживания,
d –дисциплина очереди.
e –ёмкость очереди.
f – ёмкость источника заявок на обслуживание.
Как a, b, c, d, e, f рассматривают:
a, b | d | c, e, f |
М – пуассоновское (или марковское) распределение | G – произвольная дисциплина очереди | 1 |
D – детерминированное распределение | FIFO | …. |
– распределение Эрланга | LIFO | |
G – распределение произвольного вида | RANDOM | ∞ |
В зависимости от a, b, c, d, e, f возможны следующие типы моделей СМО:
Тип моделей | Результаты исследований |
получены аналитические результаты | |
– другие модели | методы имитационного моделирования |
Наиболее распространенной моделью, которая рассматривается в ТМО, является модель типа . Эта модель имеет только одно устройство обслуживания ( ), и в ней процессы распределения времени поступления (первая буква М) и обслуживания (вторая буква М) являются марковскими. Для такой модели время между двумя поступлениями требований в систему и время их обслуживания имеют экспоненциальные распределения. Модель может применяться, например, для моделирования работы однопроцессорной системы или стандартного устройства для ввода–вывода информации (магнитного диска, принтера и т.д.).
|
|
Модель типа – детерминированная, а модель – смешанная. Если ведомостей про систему мало, её модель обозначают как – модель с любыми распределениями вероятностей случайных величин и устройствами для обслуживания.
В ТМО аналитические результаты получены только для моделей типов , і Для определения характеристик моделей с другими значениями параметров СМО используются методы имитационного моделирования.
Формула Литтла
В теории массового обслуживания важное значение имеет формула Литтла (закон сохранения стационарной очереди), которая позволяет вычислять среднее количество требований, находящихся в системе.
Рассмотрим СМОобщего вида, которую изобразим в виде «черного ящика», и будем наблюдать за её входным и выходным потоками требований.
|
|
Выходной поток
Пусть – некоторый случайный процесс поступления требований в СМО за промежуток времени ; – выходной поток требований из СМО на этом же промежутке. Изобразим оба случайных процесса в виде графиков (рис.1):
Рис.1. Входной и выходной случайные процессы в СМО
Обозначим через количество требований, находящихся в системе в любой момент времени . Значения можно найти по формуле: .
Заштрихованная площадь между двумя кривыми определяет общую работу (произведение количества требований на время нахождения в СМО) на промежутке времени , которая измеряется в требованиях за секунду.
Интенсивность поступления требований в СМО за время наблюдения можно определить:
(1)
а среднее время пребывания требований в системе за тот же промежуток времени:
(2)
Среднее количество требований, находящихся в СМО за промежуток времени :
(3)
Из формул (1)–(3) получим формулу:
|
|
(4)
Используя предельный переход при , определим – интенсивность поступления, – среднее время пребывания требований в системе. Тогда существует предел для среднего количества требований, находящихся в СМО, т.е. . Тогда из формулы (4) получим формулу Литтла:
Итак, для любого закона распределения промежутков времени между двумя моментами поступления требований и любого распределения времени их обслуживания, количества устройств обслуживания и дисциплины обслуживания, среднее количество требований, находящихся в СМО, определяют через интенсивность поступления и среднее время пребывания требований в системе.
Одноканальные СМО
Рассмотрим одноканальную СМО с одним устройством для обслуживания и очередью к нему , т.е. СМО типа :
Входной поток--------Очередь-------Устройство---------Выходной поток
q S
Если обозначить через среднее время пребывания требования в очереди, то из формулы Литтла можно получить среднее количество требований в очереди:
|
|
Если обозначить через среднее время обслуживания требования в устройстве и рассматривать СМО как систему с одним устройством, то, используя формулу Литтла, можно найти среднее количество требований в устройстве для обслуживания:
.
Для СМО с одним устройством для обслуживания всегда имеет место равенство:
где – среднее время пребывания требований в системе.
Коэффициент загруженности (коэффициент использования) устройства для обслуживания можно определить через интенсивность поступления требований в систему ( ) и скорость обслуживания этих требований в устройстве ( ), т.е. , где . Тогда .
Можно показать, что – это вероятность того, что во время поступления требования в систему устройство для обслуживания будет занятым, т.е. , где – вероятность того, что устройство для обслуживания будет свободным.
Введем коэффициент вариации как отношение среднего квадратического отклонения от среднего значения к среднему значению : .
Для экспоненциального закона распределения коэффициент вариации , т.к. для этого закона .
Для регулярного детерминированного закона распределения ( ). Таким образом, для модели СМО типа G/G/1 с одним устройством для обслуживания и при произвольных законах поступления и обслуживания требований среднее количество требований определяется как
.
Среднее время пребывания требований в одноканальной СМО определяется по формуле:
.
Из этой формулы видно, что среднее время пребывания требований в системе зависит только от математического ожидания и среднего квадратического отклонения времени обслуживания.
Таким образом, время ожидания определяется: .
Конечно нужно знать нормированное время ожидания:
.
Для моделей типа М/М/1:
.
Для моделей типа M/D/1:
.
Таким образом, система с регулярным законом обслуживания характеризуется средним временем ожидания, вдвое меньшим, чем для системы с экспоненциальным законом обслуживания. Это закономерно, т.к. время пребывания требований в системе и их количество пропорциональны дисперсии времени обслуживания.
Многоканальные СМО
Рассмотрим многоканальную СМО с одинаковыми устройствами для обслуживания, т.е. СМО типа .
Анализ многоканальных СМО, в отличие от одноканальных, является намного сложнейшим. С помощью ТМО можно получать аналитические зависимости в замкнутом виде для расчетов характеристик работы многоканальных СМО в стационарном режиме работы, однако лишь для модели типа . Для СМО с другими законами распределения времени поступления и обслуживания требований используют числовые методы.
Для системы, которая состоит из одинаковых устройств для обслуживания, коэффициент загруженности: .
В ТМО рассматриваются многоканальные СМО типа с устройствами для обслуживания двух типов:
- с отказами, когда заняты все устройств и требование получает отказ в обслуживании;
- с ожиданием, когда заняты все устройств и требование ожидает в очереди (количество мест ожидания ), если в системе находится требований и поступает новое требование, то оно получает отказ.
Для каждого из этих двух случаев можно построить системы дифференциальных уравнений, которые описывают вcе состояния СМО, а потом решить эти уравнения при условии, что система функционирует в стационарном режиме. Приведем основные формулы, необходимые для расчетов параметров СМО типа .
1. Вероятность того, что все устройства для обслуживания свободны:
, если .
2. Вероятность того, что занято обслуживанием устройств или в системе находится k требований:
, .
3. Вероятность того, что все устройства заняты ( ). Обозначим эту вероятность через :
, .
4. Вероятность того, что все устройства заняты обслуживанием и s требований находятся в очереди:
, .
5. Вероятность того, что время пребывания требований в очереди превышает некоторую заданную величину :
.
6. Средняя длина очереди:
.
7. Среднее количество свободных от обслуживания устройств:
.
8. Среднее количество занятых обслуживанием устройств:
.
9. Среднее время ожидания требованием начала обслуживания в системе:
, .
Используя приведенные формулы, можно рассчитать параметры СМО типа , а потом сравнить эти параметры с результатами имитационного моделирования.
Основы дискретно-событийного моделирования СМО
Дата добавления: 2021-07-19; просмотров: 142; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!