Основные понятия систем массового обслуживания

Система массового обслуживания — математический (абстрактный) объект, элементами которого являются (рис. 2.1):

• • входной (входящий) поток заявок (требований) на обслуживание;
• • приборы (каналы) обслуживания;
• • очередь заявок, ожидающих обслуживания;
• • выходной (выходящий) поток обслуженных заявок;
• • поток заявок на дообслуживание после прерывания обслуживания;
• • поток необслуженных заявок.

Заявка (запрос, требование, вызов, клиент, сообщение, пакет) — объект, поступающий в СМО и требующий обслуживания в приборе. Совокупность последовательных заявок, распределенных во времени, образуют входной поток заявок.

Рис. 2.1. Система массового обслуживания

Обслуживающий прибор (прибор, устройство, канал, линия, орудие, автомобиль, маршрутизатор и т.п.) — элемент СМО, назначением которого является обслуживание заявок.

Обслуживание — задержка заявки в обслуживающем приборе на некоторое время.

Длительность обслуживания — время задержки (обслуживания) заявки в приборе.

Накопитель (буфер, входной буфер, выходной буфер) — совокупность мест для ожидания заявок перед обслуживающим прибором. Количество мест для ожидания — емкость накопителя.

Заявка, поступившая в СМО, может находиться в двух состояниях:

• 1) обслуживания (в приборе);
• 2) ожидания (в накопителе), если все приборы заняты обслуживанием других заявок.

Заявки, находящиеся в накопителе и ожидающие обслуживания, образуют очередь заявок. Количество заявок в накопителе, ожидающих обслуживания, — длина очереди.

Дисциплина буферизации (дисциплина постановки в очередь) — правило занесения поступающих заявок в накопитель (буфер).

Дисциплина обслуживания — правило выбора заявок из очереди для обслуживания в приборе.

Приоритет — преимущественное право (на захват ресурсов) на занесение в накопитель или выбор из очереди для обслуживания в приборе заявок одного класса по отношению к заявкам других классов.

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

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

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

В системах ИМ при реализации СМО принимаются следующие ограничения и допущения:

• • поступившая в систему заявка мгновенно попадает на обслуживание, если в очереди нет заявок и прибор свободен;
• • в приборе на обслуживании в каждый момент времени может находиться только одна заявка;
• • после окончания обслуживания какой-либо заявки в приборе очередная заявка выбирается из очереди на обслуживание мгновенно, т.е., прибор не простаивает, если в очереди есть хотя бы одна заявка;
• • поступление заявок в СМО и длительности их обслуживания не зависят от числа заявок, уже находящихся в системе, или от каких- либо других факторов;
• • длительность обслуживания заявок не зависит от интенсивности поступления заявок в систему.

Остановимся на некоторых элементах СМО более подробно.

Входной (входящий) поток заявок. Потоком событий называется последовательность однородных событий, следующих одно за другим и происходящих в какие-то, вообще говоря, случайные моменты времени. Если событие заключается в появлении заявок, имеем поток заявок. Для описания потока заявок в общем случае необходимо задать интервалы времени т = t_k - t_k-1 между соседними моментами t_k__k и t_k поступления заявок с порядковыми номерами к - 1 и к соответственно (к — 1, 2, ...; t₀ — 0 — начальный момент времени).

Основной характеристикой потока заявок является его интенсивность X — среднее число заявок, поступающих на вход СМО за единицу времени. Величина т = 1/Х определяет средний интервал времени между двумя последовательными заявками.

Поток называется детерминированным, если интервалы времени т_к между соседними заявками принимают определенные заранее известные значения. Если при этом интервалы одинаковы (х_к = т для всех к = 1, 2, ...), то поток называется регулярным. Для полного описания регулярного потока заявок достаточно задать интенсивность потока X или значение интервала т = 1/Х.

Поток, в котором интервалы времени х_к между соседними заявками представляют собой случайные величины, называется случайным. Для полного описания случайного потока заявок в общем случае необходимо задать законы распределений F_fc(x_fc) каждого из интервалов времени х_к, к = 1,2,....

Случайный поток, в котором все интервалы времени х_ь х₂,... между соседними последовательными заявками представляют собой независимые случайные величины, описываемые функциями распределений FjCij), F₂(x₂), ... соответственно, называется потоком с ограниченным последействием.

Случайный поток называется рекуррентным, если все интервалы времени х_ь т₂, ... между заявками распределены по одному и тому же закону F(t). Рекуррентных потоков много. Каждый закон распределения порождает свой рекуррентный поток. Рекуррентные потоки иначе называют потоками Пальма.

Если интенсивность X и закон распределения F(t) интервалов между последовательными заявками не меняются со временем, то поток заявок называется стационарнъш. В противном случае поток заявок является нестационарным.

Если в каждый момент времени t_k на входе СМО может появиться только одна заявка, то поток заявок называется ординарным. Если в какой-либо момент времени может появиться более одной заявки, то поток заявок — неординарный, или групповой.

Поток заявок называется потоком без последействия, если заявки поступают независимо друг от друга, т.е. момент поступления очередной заявки не зависит от того, когда и сколько заявок поступило до этого момента.

Стационарный ординарный поток без последействия называется простейшим.

Интервалы времени т между заявками в простейшем потоке распределены по экспоненциальному (показательному) закону: с функцией распределения F(t) = 1 - е~^м; плотностью распределения/(f) = Хе~'^л, где X > 0 — параметр распределения — интенсивность потока заявок.

Простейший поток часто называют пуассоновским. Название происходит от того, что для этого потока вероятность P_fc(At) появления ровно к заявок за некоторый интервал времени At определяется законом Пуассона:

Следует заметить, что пуассоновский поток, в отличие от простейшего, может быть:

• • стационарным, если интенсивность X не меняется со временем;
• • нестационарным, если интенсивность потока зависит от времени: X = >.(t).

В то же время простейший поток, по определению, всегда является стационарным.

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

1. Суммирование (объединение) потоков. Простейший поток в теории СМО аналогичен нормальному закону распределения в теории вероятностей: к простейшему потоку приводит предельный переход для потока, являющегося суммой потоков с произвольными характеристиками при бесконечном увеличении числа слагаемых и уменьшении их интенсивности.

Сумма N независимых стационарных ординарных потоков с интенсивностями Х_ь Х₂,..., X_N образует простейший поток с интенсивностью

N

X=Y,^i при условии, что складываемые потоки оказывают более или

[=1

менее одинаково малое влияние на суммарный поток. На практике суммарный поток близок к простейшему при N > 5. Значит, при суммировании независимых простейших потоков суммарный поток будет простейшим при любом значении N.

• 2. Вероятностное разрежение потока. Вероятностное (но не детерминированное) разрежение простейшего потока заявок, при котором любая заявка случайным образом с некоторой вероятностью р исключается из потока независимо от того, исключены другие заявки или нет, приводит к образованию простейшего потока с интенсивностью X* = рХ, где X — интенсивность исходного потока. Поток исключенных заявок с интенсивностью X** = (1 - р)Х — тоже простейший поток.
• 3. Эффективность. Если обслуживающие каналы (приборы) рассчитаны на простейший поток заявок с интенсивностью X, то обслуживание других типов потоков (с той же интенсивностью) будет обеспечено с не меньшей эффективностью.
• 4. Простота. Предположение о простейшем потоке заявок позволяет для многих математических моделей получить в явном виде зависимости показателей СМО от параметров. Наибольшее число аналитических результатов получено для простейшего потока заявок.

Анализ моделей с потоками заявок, отличными от простейших, обычно усложняет математические выкладки и не всегда позволяет получить аналитическое решение в явном виде. Свое название «простейший» поток получил именно благодаря этой особенности.

Заявки могут иметь разные права на начало обслуживания. В этом случае говорят, что заявки неоднородные. Преимущества одних потоков заявок перед другими на начало обслуживания задаются приоритетами.

Важной характеристикой входного потока является коэффициент вариации

где т_инт — математическое ожидание длины интервала; о — среднее квадратическое отклонение длины интервала х_инт (случайной величины) .

Для простейшего потока (а =—, т = —) имеем v = 1. Для большинства

X X

реальных потоков 0 < v < 1. При v = 0 поток регулярный, детерминированный. Коэффициент вариации — характеристика, отражающая степень неравномерности поступления заявок.

Каналы (приборы) обслуживания. Основная характеристика канала — длительность обслуживания.

Длительность обслуживания — время нахождения заявки в приборе — в общем случае величина случайная. В случае неоднородной нагрузки СМО длительности обслуживания заявок разных классов могут различаться законами распределений или только средними значениями. При этом обычно предполагается независимость длительностей обслуживания заявок каждого класса.

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

где ц — интенсивность обслуживания, здесь р = _-—; т₀бсл — матема-

^обсл

тическое ожидание времени обслуживания.

Кроме экспоненциального распределения встречаются /с-распре- деление Эрланга, гиперэкспоненциальное, треугольное и некоторые другие. Это нас не должно смущать, так как показано, что значение критериев эффективности СМО мало зависит от вида закона распределения времени обслуживания.

При исследовании СМО выпадает из рассмотрения сущность обслуживания, качество обслуживания.

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

Эффективность СМО зависит не только от параметров входных потоков и каналов обслуживания, но также и от того, в какой последовательности обслуживаются поступающие заявки, т.е. от способов управления потоками заявок при их входе в систему и направлении на обслуживание.

Способы управления потоками заявок определяются дисциплинами:

• • буферизации;
• • обслуживания.

Дисциплины буферизации и обслуживания могут быть классифицированы по следующим признакам:

• • наличие приоритетов между заявками разных классов;
• • способ вытеснения заявок из очереди (для дисциплин буферизации) и назначения заявок на обслуживание (для дисциплин обслуживания);
• • правило вытеснения или выбора заявок на обслуживание;
• • возможность изменения приоритетов.

Вариант классификации дисциплин буферизации (постановки в очередь) в соответствии с перечисленными признаками представлен на рис. 2.2.

В зависимости от наличия или отсутствия приоритетов между заявками разных классов все дисциплины буферизации могут быть разбиты на две группы: бесприоритетные и приоритетные.

По способу вытеснения заявок из накопителя можно выделить следующие классы дисциплин буферизации:

• • без вытеснения заявок — заявки, поступившие в систему и заставшие накопитель полностью заполненным, теряются;
• • с вытеснением заявки данного класса, т.е. такого же класса, что и поступившая заявка;
• • с вытеснением заявки из класса самого низкого приоритета;
• • с вытеснением заявки из группы классов низких приоритетов.

Рис. 2.2. Вариант классификации дисциплин буферизации

Дисциплины буферизации могут использовать следующие правила вытеснения заявок из накопителя:

• • случайное вытеснение;
• • вытеснение последней заявки, т.е. поступившей в систему позже всех;
• • вытеснение «долгой» заявки, т.е. находящейся в накопителе дольше всех поступивших ранее заявок.

На рис. 2.3 представлена классификация дисциплин обслуживания заявок в соответствии с теми же признаками, что и для дисциплин буферизации.

Иногда емкость накопителя в моделях полагают неограниченной, хотя в реальной системе она ограничена. Такое допущение оправдано, когда вероятность потери заявки в реальной системе из-за переполнения емкости накопителя меньше 10^_3. В этом случае дисциплина практически не влияет на показатели обслуживания заявок.

В зависимости от наличия или отсутствия приоритетов между заявками разных классов все дисциплины обслуживания, как и дисциплины буферизации, могут быть разбиты на две группы: бесприоритет- ные и приоритетные.

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

• • одиночного режима;
• • группового режима;
• • комбинированного режима.

Рис. 2.3. Вариант классификации дисциплин обслуживания

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

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

Комбинированный режим — комбинация одиночного и группового режимов, когда часть очередей заявок обрабатывается в одиночном режиме, а другая часть — в групповом.

Дисциплины обслуживания могут использовать следующие правила выбора заявок на обслуживание.

Бесприоритетные (заявки не имеют привилегий на досрочное обслуживание — захват ресурсов):

• • обслуживание в порядке поступления — заявка выбирается из очереди в режиме FIFO (first in —first out, первый вошел — первый вышел);
• • обслуживание в обратном порядке — заявка выбирается из очереди в режиме LIFO (last in — first out, последний вошел — первый вышел);
• • обслуживание в случайном порядке — заявка выбирается из очереди в режиме RAND (random — случайным образом);
• • обслуживание в циклическом порядке — заявки выбираются в процессе циклического опроса накопителей в последовательности 1, 2,Н СН — количество накопителей), после чего указанная последовательность повторяется;

Приоритетные (заявки имеют привилегии на досрочное обслуживание — захват ресурсов):

• • с относительными приоритетами — если в процессе текущего обслуживания заявки в систему поступают заявки с более высокими приоритетами, то обслуживание текущей даже бесприоритетной заявки не прерывается, а поступившие заявки направляются в очередь; относительные приоритеты играют роль только в момент окончания текущего обслуживания заявки при выборе из очереди новой заявки на обслуживание.
• • с абсолютными приоритетами — при поступлении заявки с высоким приоритетом обслуживание заявки с низким приоритетом прерывается и на обслуживание направляется поступившая заявка; прерванная заявка может быть возвращена в очередь или удалена из системы; если заявка возвращена в очередь, то ее дальнейшее обслуживание может быть выполнено с прерванного места или заново;
• • со смешанными приоритетами — строгие ограничения на время ожидания в очереди на обслуживание отдельных заявок требуют присвоения им абсолютных приоритетов; вследствие этого время ожидания заявок с низкими приоритетами может оказаться недопустимо большим, хотя отдельные заявки имеют запас по времени ожидания; для выполнения ограничений по всем видам заявок можно наряду с абсолютными приоритетами некоторым заявкам присвоить относительные приоритеты, а остальные обслуживать в бесприоритетном режиме;
• • с чередующимися приоритетами — аналогом относительных приоритетов, приоритет учитывается только в моменты завершения текущего обслуживания группы заявок одной очереди и назначения новой группы на обслуживание;
• • обслуживание по расписанию — заявки разных классов (находящиеся в разных накопителях) выбираются на обслуживание согласно некоторому расписанию, задающему последовательность опроса очередей заявок, например в случае трех классов заявок (накопителей) расписание может иметь вид {2, 1, 3, 3, 1, 2} или {1, 2, 3, 3, 2, 1}.

В компьютерных системах ИМ, как правило, по умолчанию реализуется дисциплина FIFO. Однако они имеют инструментальные средства, которые предоставляют пользователю возможность организовать нужные ему дисциплины обслуживания, в том числе и по расписанию.

Поступающие в СМО заявки делят на классы. В СМО, представляющей собой абстрактную математическую модель, заявки относятся к разным классам в том случае, если они в моделируемой реальной системе различаются хотя бы одним из следующих признаков:

• • длительностью обслуживания;
• • приоритетами.

Если заявки не различаются длительностью обслуживания и приоритетами, они могут быть представлены заявками одного класса, в том числе и при поступлении от разных источников.

Для математического описания дисциплин обслуживания со смешанными приоритетами используется матрица приоритетов, представляющая собой квадратную матрицу Q = (q,_;), i,j - 1,..., Я, Я — число классов заявок, поступающих в систему.

Элемент q_(j матрицы задает приоритет заявок класса i по отношению к заявкам класса; и может принимать следующие значения:

• • 0 — нет приоритета;
• • 1 — приоритет относительный;
• • 2 — приоритет абсолютный.

Элементы матрицы приоритетов должны удовлетворять следующим требованиям:

• • q_n = 0, так как между заявками одного и того же класса не могут быть установлены приоритеты;
• • если q₍j = 1 или 2, то q^ = 0, так как если заявки класса i имеют приоритет к заявкам класса j, то последние не могут иметь приоритет к заявкам класса i (i,j = 1, ..., Я).

В зависимости от возможности изменения приоритетов в процессе функционирования системы приоритетные дисциплины буферизации и обслуживания делятся на два класса:

• 1) со статическими приоритетами, которые не изменяются со временем;
• 2) с динамическими приоритетами, которые могут изменяться в процессе функционирования системы в зависимости от разных факторов, например при достижении некоторого критического значения длины очереди заявок какого-либо класса, не имеющего приоритета или обладающего низким приоритетом, ему может быть предоставлен более высокий приоритет.

В компьютерных системах ИМ обязательно имеется единственный элемент (объект), через который, и только через него, вводятся заявки в модель. По умолчанию все вводимые заявки бесприоритетные. Но есть возможности присвоения приоритетов в последовательности 1, 2, ..., в том числе и в ходе выполнения модели, т.е. в динамике.

Выходящий поток — это поток обслуженных заявок, покидающих СМО. В реальных системах заявки проходят через несколько СМО: транзитная связь, производственный конвейер и т.п. В этом случае выходящий поток является входящим потоком для следующей СМО.

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

Заметим, что интервалы времени между заявками выходящего потока — это не то же самое, что интервалы обслуживания. Ведь может оказаться, что после окончания очередного обслуживания СМО какое-то время простаивает из-за отсутствия заявок. В этом случае интервал выходящего потока состоит из времени незанятости СМО и интервала обслуживания первой пришедшей после простоя заявки.

В СМО кроме выходящего потока обслуженных заявок может быть и поток необслуженных заявок. Если в такую СМО поступает рекуррентный поток, а обслуживание — экспоненциальное, то и поток необслуженных заявок — рекуррентный.

Очереди свободных каналов. В многоканальных СМО могут образовываться очереди свободных каналов. Количество свободных каналов — величина случайная. Исследователя могут интересовать различные характеристики этой случайной величины. Обычно это среднее число каналов, занятых обслуживанием за интервал исследования, и их коэффициенты загрузки.

Как мы уже отмечали ранее, в реальных объектах заявки последовательно проходят обслуживание в нескольких СМО.

Конечное множество последовательно взаимосвязанных СМО, обрабатывающих циркулирующие в них заявки, называется сетью массового обслуживания (СеМО) (рис. 2.4, а).

Рис. 2.4. Вариант сети массового обслуживания

СеМО называют также многофазными СМО.

Пример построения ИМ СеМО мы рассмотрим позже.

Основными элементами СеМО являются узлы (У) и источники (генераторы) заявок (Г).

Узел сети — это система массового обслуживания.

Источник — генератор заявок, поступающих в сеть и требующих определенных этапов обслуживания в узлах сети.

Для упрощенного изображения СеМО используется граф.

Граф СеМО — ориентированный граф (орграф), вершины которого соответствуют узлам СеМО, а дуги отображают переходы заявок между узлами (рис. 2.4, б).

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

Для лучшего восприятия этого творческого потенциала в первом приближении остановимся на классификации моделей СМО.