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

На рисунке 1 показаны элементы системы массового обслуживания одной очереди:

Массив клиентов можно считать либо ограниченным (закрытые системы) или неограниченным (открытые системы). Неограниченный массив представляет собой теоретическую модель системы с большим числом возможных клиентов банка (на оживленной улице, автомагистрали АЗС). Пример ограниченного массива могут быть несколько процессов, которые будут работать (подаваться) на компьютер, или определенное количество машин для ремонта сервисным работником. Надо взять термин “клиент” очень в целом. Клиенты могут быть люди, машины различной природы, компьютерные процессы, телефонные звонки и т.д.

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

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

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

Дисциплина очереди представляет способ организации очереди (правила вставки и удаления клиентов из / в очереди). Есть такие пути:

1) FIFO (First In First Out – первый заходит и выходит) также называется FCFS (First Come First Serve – первый зашел и обслуживается) – обычная очередь.

2) LIFO (Last In First Out – последний заходит, первый выходит) еще называется LCFS (Last Come First Serve – последний заходит, первый обслуживается) – стек.

3) SIRO (Serve In Random Order – обслуживаются в случайном порядке).

4) Приоритет очереди, который может рассматриваться как количество очередей для различных приоритетов.

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

Большинство количественных параметров (например, средняя длина очереди, среднее время, проведенное в системе) не зависит от очередности дисциплины. Вот почему большинство моделей либо не принимают дисциплину очередей во внимание вообще или берут на себя нормальную очередь FIFO. На самом деле, единственный параметр, который зависит от очередности дисциплины – это дисперсия (или стандартное отклонение) времени ожидания. Существует такое важное правило (которое может быть использовано, например, чтобы проверить результаты имитационного эксперимента):

Два крайних значения времени ожидания дисперсии предназначены для очереди FIFO (минимум) и очереди LIFO (максимальной).

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

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

Выход представляет собой способ, как клиенты покидают систему. Выход в основном игнорируется теоретическими моделями, но иногда клиенты покидают сервер в очередь снова (“Round Robin” системы с разделением времени).

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

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

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

Классификация систем массового обслуживания Кендалла

Классификация систем массового обслуживания Кендалла (1953), существует в нескольких модификациях. Наиболее полная классификация использует 6 символов:

A/B/s/q/c/p

где:

A модель прибытия (Распределение интервалов между прибытиями).

B это образец обслуживания (распределение длительности обслуживания).

s количество серверов.

q это очередные дисциплины (FIFO, LIFO, …). Опущены для FIFO или если не указано

c это способность системы. Опущены для неограниченных очередей.

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

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

M является (марковским) процессом Пуассона с экспоненциальным распределением интервалов или продолжительности обслуживания соответственно.

E_m является распределение Эрланга интервалов или продолжительности обслуживания.

D является символом для детерминированных (известных) прибытий и продолжительности постоянного обслуживания.

G общее (любое) распределение.

GI общее (любое) распределение с независимыми случайными значениями.

       Примеры:

D/M/1 = Детерминированный (известный) вход, один экспоненциальный сервер, один безлимитный FIFO или неопределенная очередь, неограниченное количество клиентов.

M/G/3/20 = вход По Пуассону, три сервера с любого распределения, максимальное количество клиентов 20, неограниченное количество клиентов.

D/M/1/LIFO/10/50 = Детерминированное прибытие, один экспоненциальный сервер, очередь стек максимального размера 9, общее количество клиентов 50.

Оригинал статьи находиться здесь