3. Приоритет клиентов

На практике клиенты часто разделяются на 7Vприоритетных классов, где клиент, принадлежащий классур, имеет более высокий приоритет, чем клиент, принадлежащий классу р+1. Мы различаем два типа приоритета.

Неприоритетное обслуживание (Non-preemptive)

Поступивший вызов с более высоким приоритетом, чем обслужи­ваемый клиент, ждет до конца обслуживания, пока сервер будет свободен (и все клиенты с более высоким приоритетом будут обслужены). Это дис­циплина также называется HOL (Head-Of-the-Line — «Во главе очереди»).

Приоритетное обслуживание (Preemptive)

Если обслуживаемый клиент имеет более низкий приоритет, чем новый поступивший вызов, то обслуживание прерывается. При этом воз­можны следующие способы возвращения к работе.

Приоритетное возвращение к работе PR (Preemptive resume) — после прерывания обслуживание прерванного вызова продолжается, при этом имеются варианты:

• приоритетное без повторения (Preemptive without re-sampling), обслу­живание перезапускается, начиная с того самого момента, на кото­ром оно было прервано;

• приоритетное с повторением (Preemptive with re-sampling), обслужи­вание начинается снова с новым временем обслуживания.

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

В литературе, посвященной организации очереди, мы встречаем много других стратегий и обозначений. GD обозначает произвольную дис­циплину организации очереди (general discipline).

Поведение клиентов является также предметом моделирования.

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

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

Перепрыгивающий — применяется к системам, где клиенты могут «перепрыгнуть» из одной, например, длинной, очереди в другую — корот­кую очередь.

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

Пример 13.1.2: Система коммутации с программным обеспечением (Накопленная Управляемая Программа (spc)

В SPC (Stored Program Controlled) задачи систем процессоров раз­делены, скажем, на десять приоритетных классов. Приоритет, например, обновляется каждые 5 миллисекунд. Сообщения об ошибках от про­цессора имеют самый высокий приоритет, тогда как стандартные задачи управления имеют самый низкий приоритет. Обслуживание принятых вызовов имеет более высокий приоритет, чем обнаружение новых попы­ток вызова.

2. Основные результаты в теории организации очередей

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

Формула Литтла, представленная в секции 5.3 - наиболее общий результат, который является справедливым для произвольной системы организации очереди. Теорема проста в применении и во многих случаях очень полезна.

В общем случае только системы организации очереди с Пуассонов- скими потоками вызовов просты для исследования. Относительно систем организации очереди при последовательном установлении соединения и организации очередей на сетях связи (например, компьютерных сетей) важно знать те случаи, где процесс выхода из системы организации очереди — Пуассоновский процесс. Эти системы организации очереди названы симметричными системами организации очереди, потому что они симметричны во времени, поскольку процесс поступления вызовов и процесс выхода из системы имеют один и тот же тип. Если для такой оче­реди рассматривать диаграмму процесса по тактам времени, невозможно решить, выполнена ли эта диаграмма при прямом или обратном процессе (обратимость) (Kelly, 1979 [60]).

Классическая модель организации очереди играет ключевую роль в теории организации очереди, потому что другие системы будут часто сходиться к этой модели, когда число обслуживающих приборов будет увеличиваться (теорема Пальма 6.1 в секции 6.4).

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

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

3. Формула Полячека-Хинчина для M/G/1

Мы ранее получили среднее время ожидания для системы М/М/1 (секция 12.2.4), и позже рассматривали М/D/l (секция 13.5). В общем случае среднее время ожидания для М/G/l определяется следующей теоремой.

Теорема 13.1 Формула Полячека-Хинчина (1930 -32):

W - (13.1)

г = ЙГТ)-, (ад

V = A^S- 8= ^ти₂- (13-3)

Здесь W— среднее время ожидания обслуживания для всех клиентов, 5 - среднее время обслуживания, А - предложенная нагрузка, и е является коэффициентом формы распределения времени пребывания в системе (3.10).

Чем регулярнее процесс обслуживания, тем меньше среднее время ожидания. Соответствующий результат для процесса поступления вызо­вов изучен в секции 13.6. В реальной телефонной нагрузке коэффициент формы чаще всего равен 4-6, в нагрузке передачи данных 10-100.

Формула (13.2) — один из самых важных результатов в теории орга­низации очереди, и мы изучим ее более тщательно.