Основы дискретно-событийного моделирования СМО
Лекция № 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; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!