Параметры и характеристики систем массового обслуживания

Параметры и характеристики систем массового обслуживания

 

1. Параметры систем  массового обслуживания

1.1. Общие положения.

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

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

Процесс функционирования СМО включает в общем случае следующие этапы:

1. приход (поступление) требования;
2. ожидание (при необходимости) в очереди;
3. обслуживание в приборе;
4. уход требования из системы.

Изучение любой системы, в том  числе и СМО, предполагает ее формализацию (описание), т.е. определение параметров системы, необходимых и достаточных для анализа характеристик ее функционирования.

Для формализации любой СМО необходимо описать:

1. процесс поступления заявок в систему;
2. процесс обслуживания заявок в системе;
3. дисциплину обслуживания.

 

1.2. Процесс поступления  заявок.

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

Пусть t₁, t₂, t₃, ... , t_k, ... — моменты поступления в систему 1-го, 2-го, 3-го, ..., k-го, ... требований:

Обозначим через t_k = t_k – t_k-1 промежуток времени между моментами прихода (k–1)-го и k-го требований, который называется интервалом прихода k-го требования (k = 1, 2, 3, ...).

Если интервалы прихода всех заявок являются постоянными, т.е. , то такой поток называется  детерминированным или регулярным. Однако, как правило, интервалы прихода t_k являются случайными величинами, и соответствующий поток заявок называется стохастическим или случайным. Очевидно, что регулярный поток является частным случаем случайного потока.

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

 .

Поток заявок, для которого функции  распределения интервалов прихода всех заявок одинаковы, т.е.

называется рекуррентным. Другими словами, для рекуррентного потока интервалы прихода (t ) всех заявок распределены по одному и тому же закону.

Важная характеристика любого потока — это его интенсивность, которая обозначается через l(t) и определяет среднее число заявок, поступающих в систему в единицу времени. Если интенсивность поступления l(t) не зависит от времени, т.е. l(t) º l, то такой поток называется стационарным.

Величина а, обратная интенсивности l (а=1/l), определяет среднее значение интервалов прихода или средний интервал поступления заявок.

Если в каждый момент времени t₁, t₂, t₃, ... поступает только одна заявка, то такой поток называется ординарным, в противном случае — групповым (могут приходить одновременно две или более заявок). В дальнейшем рассматриваются только рекуррентные, стационарные и ординарные потоки.

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

При анализе СМО важное место  занимает так называемый простейший поток. Простейшим называется поток, в котором интервалы поступления заявок распределены по экспоненциальному закону:

.

Очевидно, что параметр l данного экспоненциального распределения является интенсивностью соответствующего простейшего потока.

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

Простейший поток обладает следующими свойствами.

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

2) Если из простейшего потока  интенсивности l исключить каждую заявку с вероятностью р (а с вероятностью 1–р оставить), то как поток исключенных, так и поток оставшихся заявок, окажутся простейшими с интенсивностями рl и (1–р)l соответственно:

 3) Число заявок N(t) простейшего потока, поступающих в СМО за время t, будучи случайной целочисленной дискретной величиной, распределено по закону Пуассона:

Поэтому очень часто простейший поток называют стационарным Пуассоновским потоком. Такое же выражение было получено (см. пособие "Математические основы моделирования дискретных систем") и для простейшего процесса чистого размножения, что позволяет утверждать: процесс чистого размножения является адекватной моделью простейшего потока.

Таким образом, для описания рекуррентного, стационарного и ординарного процесса поступления заявок необходимо в общем случае задать функцию распределения интервалов их поступления. Однако не всегда бывает известной функция распределения. В таких случаях вместо неизвестной функции распределения для описания входного потока задаются интенсивность l (или средний интервал а=1/l) и коэффициент вариации (КВ) n_а интервалов поступления, что оказывается достаточным для многих теоретических и практических приложений. Более того, в большинстве аналитических исследований в качестве входного потока заявок рассматривается простейший поток, ибо только в этом случае удается получать сколько-нибудь содержательные результаты анализа СМО. А для описания простейшего потока достаточно задать интенсивность l, т.к. при этом КВ n_аº1 в силу экспоненциального характера распределения интервалов поступления заявок.

Выделение используемых при анализе  СМО потоков схематически представлено на рисунке:

1.3. Процесс обслуживания.

По аналогии с процессами поступления  заявок в систему для описания процессов обслуживания необходимо задать функцию распределения B_k(t) длительности обслуживания для каждой k-й заявки (k = 1, 2, 3, ...), которая в общем случае является случайной величиной. При этом под длительностью обслуживания t_в понимается промежуток времени, в течение которого заявка находится в обслуживающем приборе. Далее будем считать, что все заявки создают статистически однородную нагрузку, т.е. длительности обслуживания всех заявок распределены по одному и тому же закону:

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

Величина b, обратная интенсивности m (b=1/m), определяет среднее время обслуживания одной заявки.

Как и в случае интервалов поступления, если функция распределения B(t) неизвестно, то для многих приложений (теоретических и практических) оказывается достаточным определить интенсивность обслуживания m (или среднее время обслуживания b) и КВ n_в длительности обслуживания. Если длительность обслуживания распределено по экспоненциальному закону, то достаточно задать интенсивность обслуживания m (или среднее время обслуживания b). Следует отметить, что, в отличие от интервалов поступления заявок, отказ от экспоненциального характера распределения длительности их обслуживания не столь усложняет задачу аналитического исследования СМО, и многие содержательные результаты получены при произвольном характере распределения времени обслуживания.

 

1.4. Дисциплина обслуживания.

Дисциплиной обслуживания (ДО) называется правило, по которому выбираются на обслуживание заявки из очереди. Различают следующие ДО:

1) обслуживание в порядке поступления  или дисциплина FIFO (First Input, First Output — первым пришел, первым ушел);

2) обслуживание в обратном порядке  или дисциплина LIFO (Last Input, First Output — последним пришел, первым ушел);

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

В дальнейшем в качестве ДО будем  рассматривать ДО FIFO.

Таким образом, для описания СМО необходимо задать:

1) функцию распределения A(t) интервалов поступления (общий случай) или интенсивность поступления l (или средний интервал а=1/l) и КВ n_а интервалов поступления;

2) функцию распределения В(t) длительности обслуживания (общий случай) или интенсивность обслуживания m (или среднее время обслуживания b=1/m) и КВ n_вºn времени обслуживания;

3) дисциплина обслуживания (ДО FIFO).

Следует отметить, что на практике СМО  описывается, как правило, путем определения совокупности параметров {l, n_a} и {m, n}, считая, что ДО по умолчанию является дисциплина FIFO. Более того, если интервалы поступления или длительности обслуживания распределены по экспоненциальному закону, то нет необходимости задать и соответствующий КВ, т.к. в таком случае он равен 1 (n_a º1 или n = 1). Графическое представление СМО, для которой определены параметры, имеет вид:

 

1.5. СМО с неоднородной  нагрузкой.

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

Для формализации СМО с неоднородной нагрузкой необходимо описать:

1. процесс поступления заявок каждого класса, т.е. необходимо задать либо функции распределений А₁(t), А₂(t), ..., А_H(t) интервалов поступления (общий случай), либо интенсивности поступления l₁, l₂, ..., l_H (или средние интервалы поступления a₁, a₂, ..., а_H) с КВ n_а1, n_а2, ..., n_аH интервалов поступления, где Н – количество классов заявок, поступающих в систему;
2. процесс обслуживания заявок каждого класса, т.е. необходимо задать либо функции распределения В₁(t), B₂(t), ..., B_H(t) длительностей обслуживания (общий случай), либо интенсивности обслуживания m₁, m₂, ..., m_H (или средние времена обслуживания b₁, b₂, ..., b_H) с КВ n₁, n₂,..., n_H длительностей обслуживания;
3. дисциплину обслуживания, в качестве которой может быть задана:

а) ДО бес приоритетная, когда между  заявками разных классов нет приоритетов (приоритет ¾ это преимущественное право на обслуживание);

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

в) ДО с абсолютными приоритетами, когда приоритеты учитываются так  же и во время обслуживания –  высокоприоритетные заявки прерывают  обслуживание низкоприоритетных;

г) ДО со смешанными приоритетами, когда  заявки данного класса имеют к заявкам одних классов относительный приоритет, к заявкам других – абсолютный, а к заявкам третьих – нет приоритета.

Вопросы математической формализации перечисленных ДО выходят за рамки  курса "Моделирование дискретных систем".

 Графическое представление СМО с неоднородной нагрузкой имеет вид

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

1) — интенсивность объединенного потока (простейшего);

2) — усредненное время обслуживания заявок объединенного потока, где — доля заявок класса k в суммарном потоке ( );

3) — из этого выражения определяется КВ n длительности обслуживания заявок объединенного потока.

После преобразований исходная модель примет вид:

1.6. Многоканальные СМО.

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

Для описания МК СМО задается та же совокупность параметров, что и для  ОК СМО (см. раздел 1.4). Дополнительно задается только количество N обслуживающих приборов. Графическое представление МК СМО имеет вид:

1.7. Мнемоническое обозначение  СМО.

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

А – описывает распределение (или задает характер закона распределения) интервалов поступления заявок;

В – описывает распределение длительностей обслуживания заявок;

N – задает количество обслуживающих приборов в СМО.

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