Лекция 12. Дисциплины очереди в СМО и построение характеристик СМО при различных дисциплинах очереди

Дисциплины очереди в СМО и построение характеристик СМО при различных дисциплинах очереди. Заключительные замечания по теме.

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

Дисциплина очереди «БЕСПРИОРИТЕТНАЯ». Это – самая простая дисциплина. На бытовом языке это - «живая очередь»: заявка, попав в СМО, становится последней в имеющуюся очередь; сама очередь продвигается в естественном порядке – как только узел обслуживания освобождается, первая по очереди заявка поступает на обслуживание, а все остальные заявки в очереди продвигаются на одно место вперед.

Именно для «бесприоритетных» СМО получена формула Поллачека-Хинчина; среднее время ожидания в очереди для заявки в «бесприоритетных» СМО есть число

.

Дисциплина очереди «ОТНОСИТЕЛЬНЫЕ ПРИОРИТЕТЫ». Мы по-прежнему рассматриваем полипоточную СМО с N пуассоновскими потоками; все предыдущие обозначения сохраняют смысл.

Занумеруем имеющиеся потоки числами 1,2,..., N; фиксируем произвольную подстановку

;

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

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

Такой порядок организации очереди называется «относительными приоритетами».

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

Будем считать, что потоки занумерованы своими приоритетами. Для каждого k положим ; это число называется загрузкой СМО первыми k потоками; число называется общей загрузкой СМО.

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

,

при этом для удобства принимается, что .

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

.

Среднее число заявок приоритета k, находящихся в очереди, есть

.

Среднее число заявок приоритета k, находящихся в СМО, есть

.

Наконец, общее число заявок, находящихся в СМО, есть

.

И, наконец,

Дисциплина очереди «АБСОЛЮТНЫЕ ПРИОРИТЕТЫ». Эту дисциплину очень легко описать после того, как уже описана дисциплина «относительные приоритеты». А именно, предположим, что входным потокам присвоены приоритеты, т.е. задана подстановка

;

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

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

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

,

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

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

Датчик случайных чисел – это компьютерная программа с выходным продуктом в виде сколь угодно большого набора чисел, которые можно интерпретировать как значения случайной величины с конкретным законом распределения. В любом языке программирования имеется макрокоманда, каждый вызов которой дает число из интервала (0,1), но чем больше совокупность таких чисел, тем равномернее расположены они в интервале (0,1); последнее означает, что если (0,1) разбить на любое число равных частей, то количества чисел, поставляемых упомянутой макрокомандой и попадающих в ячейки разбиения, будут все меньше и меньше отличаться друг от друга. В языке БЭЙСИК, например, эта макрокоманда выглядит так: ; и после каждого очередного написания этой команды будет возникать новое число , и совокупность этих чисел будет все равномернее располагаться в интервале (0,1). Этот датчик – имитатор равномерно распределенной в интервале (0,1) случайной величины. Будем в ближайшем тексте условно обозначать символом RND число только что описанной природы.

В теории вероятностей доказывается следующая теорема: если - случайная величина с функцией распределения и - равномерно распределенная случайная величина в интервале (0,1), то случайная величина , получаемая при решении уравнения , в качестве своей функции распределения имеет ту же . Это позволяет создавать на компьютере потоки не только равномерно распределенных в интервале (0,1) чисел, но и произвольным образом распределенных чисел. Простейший пример доставляет экспоненциальное распределение: числа , получаемые из решения уравнения , то есть числа распределены экспоненциально.

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

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