ЛК_СМО_

Одноканальная система массового обслуживания с ожиданием и произвольным законом продолжительности обслуживания

В системах с ожиданием заявка, заставшая все каналы занятыми, не покидает систему, а становится в очередь и ожидает, пока не освободится какой-нибудь канал.
Т.е СМО с ожиданием подразумевает наличие буфера с очередью из заявок, заставших все каналы занятыми и ждущих освобождения одного из каналов. Если время ожидания заявки в очереди ничем не ограничено, то система называется «чистой системой с ожиданием». Если оно ограничено какими-то условиями, то система называется «системой смешанного типа». Это промежуточный случай между чистой системой с отказами и чистой системой с ожиданием.
Для практики наибольший интерес представляют именно системы смешанного типа.
Ограничения, наложенные на ожидание, могут быть различного типа. Часто бывает, что ограничение накладывается на время ожидания заявки в очереди; считается, что оно ограничено сверху каким-то сроком Tож , который может быть как строго определенным, так и случайным.
При этом ограничивается только срок ожидания в очереди, а начатое обслуживание доводится до конца, независимо от того, сколько времени продолжалось ожидание (например, в системах с коммутацией каналов после установления соединения между абонентами процесс разговора уже не прерывается).
В других задачах естественнее наложить ограничение не на время ожидания в очереди, а на общее время пребывания заявки в системе (например, при передаче SMS-сообщений, если после определенного количества попыток сообщение не доходит до адресата оно аннулируется).
Можно рассмотреть и такую смешанную систему, когда заявка становится в очередь только в том случае, если длина очереди не слишком велика. Здесь ограничение накладывается на число заявок в очереди (или на размер буфера m, рис. 6).

Рис. 6
В системах с ожиданием существенную роль играет так называемая «дисциплина очереди». Ожидающие заявки могут вызываться на обслуживание как в порядке очереди (раньше прибывший раньше и обслуживается), так и в случайном, неорганизованном порядке. Существуют СМО «с приоритетами», где некоторые заявки обслуживаются предпочтительно перед другими («генералы и полковники вне очереди»).

Одноканальная СМО с ожиданием и произвольным законом продолжительности обслуживания обозначается как М|G|1.
Предположим, что заявки обслуживаются в порядке их поступления. Состояния СМО нумеруются по числу заявок в СМО, находящиеся в очереди или обслуживаемых:
- СМО свободна (0); канал занят, очереди нет (1); канал занят, одна заявка стоит в очереди (2); канал занят и (к-1) заявок стоят в очереди.
13 EMBED Visio.Drawing.11 1415
Финальные вероятности для такой СМО существуют не всегда, а только тогда, когда система не перегружена. Если 13 EMBED Equation.3 1415 строго меньше единицы, то финальные вероятности существуют, при 13 EMBED Equation.3 1415 больше единицы очередь растет неограниченно, при 13 EMBED Equation.3 1415=1 СМО справляется с потоком заявок только, если этот поток регулярный, а время обслуживания равно интервалу между заявками. Это идеальный случай, когда очереди вообще не будет. Но стоит только потоку заявок стать чуть-чуть случайным – и очередь уже будет расти до бесконечности.
Финальные вероятности состояний при 13 EMBED Equation.3 1415 меньше единицы:
13 EMBED Equation.3 1415; 13 EMBED Equation.3 1415; 13 EMBED Equation.3 1415
Среднее число заявок в такой системе
13 EMBED Equation.3 1415
Среднее время пребывания заявки в системе
13 EMBED Equation.3 1415
Среднее число заявок в очереди
13 EMBED Equation.3 1415
Среднее время пребывания заявки в очереди
13 EMBED Equation.3 1415
Если обозначить через 13 EMBED Equation.3 1415 продолжительность обслуживания і-й заявки, тогда средняя продолжительность обслуживания 13 EMBED Equation.3 1415, второй момент продолжительности обслуживания 13 EMBED Equation.3 1415.
Здесь М{} означает математическое ожидание. Тогда в соответствии с формулой Поллачека-Хинчина [1, 2] среднее время ожидания заявки в очереди равно
13 EMBED Equation.3 1415, (21)

а средняя задержка заявки в СМО определяется по формуле
13 EMBED Equation.3 1415. (22)

Применяя теорему Литтла, получим выражения для среднего числа заявок в очереди на обслуживание 13 EMBED Equation.3 1415 и среднего числа заявок в системе 13 EMBED Equation.3 1415:
13 EMBED Equation.3 1415; (23)
13 EMBED Equation.3 1415. (24)
Если продолжительность обслуживания всех заявок одинакова, будем иметь СМО с детерминированным законом продолжительности обслуживания М|D|1, для которого характерно равенство 13 EMBED Equation.3 1415. В результате получим
13 EMBED Equation.3 1415; 13 EMBED Equation.3 1415. (25)
Пропускная способность системы с ожиданием, при тех же
· и µ, будет всегда выше, чем пропускная способность системы с отказами: в случае наличия ожидания необслуженными уходят не все заявки, заставшие n каналов занятыми, а только некоторые. Пропускная способность увеличивается при увеличении среднего времени ожидания.
Многоканальная система массового обслуживания

Рассмотрим многоканальную систему массового обслуживания при условии, что входной поток заявок является простейшим, продолжительность обслуживания заявок распределена по показательному закону с параметром
·. Число обслуживающих каналов обозначим m. При таких условиях СМО обозначается как M| М| m.
Предположим, что сообщения обслуживаются в порядке их поступления любым из свободных каналов. Диаграмма состояний такой СМО в установившемся режиме изображена на рис. 7.

13 SHAPE \* MERGEFORMAT 1415

Рис. 7. Диаграмма состояний системы

В установившемся режиме для такой СМО получим следующую систему уравнений:

13 EMBED Equation.3 1415;
13 EMBED Equation.3 1415;
...
13 EMBED Equation.3 1415 при 13 EMBED Equation.3 1415;
13 EMBED Equation.3 1415 при і > m. (26)

К этим уравнениям необходимо добавить условие:

13 EMBED Equation.3 1415. (27)

Решим систему уравнений относительно неизвестных Рі.
Из первого уравнения находим:

13 EMBED Equation.3 1415. (28)

Со второго уравнения, получаем:

13 EMBED Equation.3 1415. (29)

Из третьего уравнения получим:

13 EMBED Equation.3 1415. (30)
При решении уравнений для любого і при і
· m, получим соотношение:

13 EMBED Equation.3 1415. (31)

При этом:
13 EMBED Equation.3 1415. (32)

И
13 EMBED Equation.3 1415. (33)

Полученные формулы для определения Р0 и Рm называются формулами Эрланга. Если предположить, что в случае занятости всех m каналов заявка получит отказ в обслуживании, то вероятность отказа Ротк равняется 13 EMBED Equation.3 1415. Полученные выражения справедливы для і
· m.

Рассмотрим вариант, когда і
· m и і > m. Для упрощения обозначим 13 EMBED Equation.3 1415. Решая систему уравнений, получим:
13 EMBED Equation.3 1415 при і
· m; (34)
13 EMBED Equation.3 1415 при і > m. (35)

Вероятность Р0 можно определить из нормировочного условия 13 EMBED Equation.3 1415. Подставив значение Рі , после преобразования можно записать

13 EMBED Equation.3 1415. (36)

Это соотношение также называют формулой Эрланга.
Вероятность того, что сообщение будет поставлено в очередь на обслуживание, определяется по формуле:

13 EMBED Equation.3 1415. (37)

Тогда среднее число заявок-сообщений, ожидающих в очереди на обслуживание, равно
13 EMBED Equation.3 1415. (38)

Получим 13 EMBED Equation.3 1415.
Используя теорему Литтла, определим среднее время ожидания в очереди:

13 EMBED Equation.3 1415 . (39)

Тогда, средняя задержка сообщения в СМО будет определяться как

13 EMBED Equation.3 1415. (40)

Воспользовавшись теоремой Литтла, можно рассчитать среднее число сообщений в системе в целом:
13 EMBED Equation.3 1415. (41)
Поскольку 13 EMBED Equation.3 1415, получим 13 EMBED Equation.3 1415.
Характеристика дисциплин обслуживания без приоритетов

Пусть на вход системы поступает L простейших потоков с интенсивностями
·1,
·2....
·L, Если обслуживающий канал занят, то заявки записываются в ЗУ (рис. 8).
Из поступающих потоков формируется один суммарный поток с интенсивностью 13 EMBED Equation.3 1415. Обслуживание заявок осуществляется в порядке их поступления. Предположим, что закон распределения времени обслуживания произвольный и свойства обслуживающего канала описываются двумя наборами характеристик:
1) средним временем обслуживания заявки і-го типа 13 EMBED Equation.3 1415, і =1, 2,, L;
2) величиной второго начального момента времени обслуживания заявки і-го типа 13 EMBED Equation.3 1415, і = 1, 2,, L.
Коэффициент загрузки канала заявками і-го типа равен
13 EMBED Equation.3 1415.
Тогда общая загрузка канала заявками всех типов равняется 13 EMBED Equation.3 1415.
Получим выражение для среднего времени ожидания заявок в очереди.
Пусть в произвольный момент времени в очереди уже находились l1, l2, ..., L заявок типов 1, 2, , L и поступила заявка j- го типа. Тогда время ожидания для этой заявки рассчитывается как:

13 EMBED Equation.3 1415, (42)

где 13 EMBED Equation.3 1415 – время, необходимое для завершения обслуживания заявки, уже находившейся на обслуживании; Ті – время обслуживания заявки і- го типа.
Выполнив операцию усреднения, получим:
13 EMBED Equation.3 1415. (43)

Воспользовавшись формулой Поллачека-Хинчина, имеем
13 EMBED Equation.3 1415. (44)

Таким образом, в системе с безприоритетной дисциплиной обслуживания среднее время ожидания в очереди всех типов заявок одинаково, а средняя задержка в системе заявки і-го типа равна:

13 EMBED Equation.3 1415. (45)

Тогда средняя задержка заявки любого типа равна средневзвешенному от 13 EMBED Equation.3 1415 по всем потокам:

13 EMBED Equation.3 1415. (46)

Далее по теореме Литтла рассчитаем среднее число заявок в системе:

13 EMBED Equation.3 1415, где 13 EMBED Equation.3 1415. (47)
Аналогично получим формулу для среднего числа заявок в очереди:

13 EMBED Equation.3 1415. (48)

Характеристика дисциплины обслуживания разнородных сообщений с относительным приоритетом

Пусть на вход СМО поступает простейший поток с
· типов заявок с интенсивностями
·1,
·2, ...,
·
·, причем более высокому приоритету отвечает меньшее значение индекса при
·.
Поступающая в СМО заявка с приоритетом j становится в очередь заявок этого же приоритета. В результате для каждого типа заявок существует своя очередь, в которой обслуживание выполняется в порядке поступления. После завершения обслуживания текущей заявки диспетчер выбирает первую заявку из очереди с наибольшим приоритетом (рис. 8).
13 SHAPE \* MERGEFORMAT 1415

Средние значения продолжительности обслуживания обозначим как 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, ..., 13 EMBED Equation.3 1415, а вторые начальные моменты – 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, ..., 13 EMBED Equation.3 1415. Тогда продолжительность обслуживания заявки с приоритетом
· определяется выражением

13 EMBED Equation.3 1415, (49)

де
·0 – время дообслуживания заявки, уже находившейся на обслуживании;
Ті – суммарное время обслуживания заявок і-го приоритета, которые уже находились в очереди;
13 EMBED Equation.3 1415 – суммарное время обслуживания заявок, которые имеют приоритет больше
· и поступили позже заявки с приоритетом
·.
Усреднив это выражение для произвольного
·, получим [1]
13 EMBED Equation.3 1415, (50)
где 13 EMBED Equation.3 1415; 13 EMBED Equation.3 1415.
В соответствии с теоремой Литтла можно определить среднее число заявок, находящихся в очереди на обслуживании
13 EMBED Equation.3 1415. (51)
Характеристика дисциплины обслуживания сообщений с абсолютным приоритетом

Пусть на вход СМО поступает простейший поток заявок с интенсивностями
·1,
·2....
·
·, где индекс
· означает приоритет этих заявок.
Как и в предыдущем случае, для каждого приоритета организуется очередь, в которой заявки располагаются в порядке поступления.
Предположим, что обслуживается заявка j- го приоритета, а на вход системы поступает заявка і- го приоритета.
Если i > j, то поступившая ставится в очередь заявок с тем же самым приоритетом. При i < j обслуживание заявки j- го приоритета прекращается и начинается обслуживание заявки і-го приоритета. После окончания обслуживания заявки і-го приоритета дообслуживаются заявки j-го приоритета, если не поступила новая заявка с более высоким приоритетом.
Среднее время ожидания заявки приоритета
· равно 13 EMBED Equation.3 1415, где 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 – соответственно среднее время ожидания начала обслуживания и среднее время возможного ожидания в прерванном состоянии.
Время 13 EMBED Equation.3 1415представляет собой суммарное время ожидания окончания обслуживания всех заявок более высокого приоритета и заявок приоритета
·, которые уже находились в очереди.
Суммарное среднее время ожидания в прерванном состоянии за счет обслуживания всех заявок (с приоритетом выше
·), которые поступили за время обслуживания заявки приоритета
·, равно:

13 EMBED Equation.3 1415. (52)

В результате среднее время ожидания заявки приоритета
· можно определить из выражения

13 EMBED Equation.3 1415. (53)

В данном случае среднее число заявок в очереди определяется как и для дисциплины с относительным приоритетом.
Для сравнительной оценки на рис. 10 приведены качественные зависимости времени ожидания обслуживания заявок от их приоритета.
13 SHAPE \* MERGEFORMAT 1415


Рис. 10. Зависимость времени ожидания в очереди от приоритета

Из этих зависимостей видно, что дисциплина обслуживания с абсолютным приоритетом в большей мере удовлетворяет требованиям относительно ограничения задержек высокоприоритетных сообщений за счет увеличения задержки сообщений с низким приоритетом.
Таким образом, теория массового обслуживания обеспечивает возможность количественной оценки показателей качества обслуживания потребителей в телекоммуникационной сети в разных, но сравнительно несложных условиях. Для исследования процессов, протекающих в сложных системах массового обслуживания, могут применяться и другие методы, основанные на представлении ТКС уже сетью массового обслуживания, где уже отдельные элементы сети моделируются СМО.



0

1

2

m-1

m

m+1


·


·


·


·


·

Рm+1

m
·

Рm-1

3
·

Р2

2
·

Р1


·

Р0

(m-1)
·

Рm

m
·


·

m
·


·1


·2


·L

Канал

ЗУ

Рис. 8. Схема организации
обслуживания заявок без приоритетов


·1


·2


· a

Диспетчер

Канал

Рис. 9. Схема организации обработки заявок
с относительным приоритетом

С относительным приоритетом

1

2

3

4

5

С абсолютным приоритетом

Без приоритета


·

13 EMBED Equation.3 1415



Root EntryTIMES NEW ROMANTIMES NEW ROMAN
Times New RomanTIMES NEW ROMAN
Times New RomanTIMES NEW ROMAN
Times New RomanTIMES NEW ROMAN
Times New RomanTIMES NEW ROMAN
Times New Roman 
·
·
·
·
·я
·Н
·
·
·
·!Ђ
·
·
·
·
·
·3
·S PG
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·a Ne
·
·
·
·
·
·
·E
·
·і
·
·
·
·
·
·
·
·S Fa
·
·
·
·
·
·
·*
·Equation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Native

Приложенные файлы

  • doc 14735247
    Размер файла: 413 kB Загрузок: 0

Добавить комментарий