Лекция №14
По дисциплине “Теория распределение информации»
Наименование темы: 1.Система типа G/G/1
Дисциплины обслуживания. Модель с приоритетами
Система типа G/G/1
Система типа G/G/1-этот класс систем предполагает, что как распределение интервалов времени между поступлением входных заявок-требований, так и распределение времени обслуживания в сервере описываются произвольными функциями плотности вероятности. Обозначим функцию плотности вероятности входного потока заявок a(t), а функцию плотности вероятности времени обслуживания b(x). Рассмотрим последовательность поступающих заявок на обслуживание - требований, пронумерованных индексами и вспомним обозначения, введенные ранее.
Cn - n -е требование, поступающее в систему,
tn - промежуток времени между поступлениями n -го и n -1 требований, плотность вероятности a(t) - не зависит от n.
xn - время обслуживания n -го требования, плотность вероятности b(x) -также не зависит от n,
wn - время ожидания n - го требования в очереди.
Напомним определение незавершенной работы для системы массового обслуживания. По определению незавершенная работа в каждый момент времени - это остаточное время, необходимое для освобождения системы от всех требований, находящихся в ней к этому моменту. Очевидно, что для системы G/G/1 значение незавершенной работы непосредственно перед поступлением n-го требования в точности равно времени wn. Таким образом, последовательность этих значений будет образовывать дискретную марковскую цепь, вероятности переходов которой могут быть определены по характеристикам входного потока и времени обслуживания. Зная эти переходные вероятности можно найти все характеристики изучаемой СМО. Рассмотрим два случая поступления требования Сn в систему - поступление в занятую систему (Рис. 1) и в свободную систему (Рис. 2).
Рис. 1 Случай, когда требование Cn+1 поступает в занятую систему.
Рис. 2 Случай, когда требование Cn+1 поступает в свободную систему.
Нетрудно видеть, что для первого случая
.
Для второго случая 
.
Определим случайную величину, равную разности между временем обслуживания требования с номером n и промежутком времени между поступлениями n +1 и n -го требований 
.
Фундаментальное свойство этой случайной величины состоит в том, что для стабильных СМО, т.е. имеющих стационарное распределение вероятностей состояний, ее математическое ожидание должно быть отрицательным. Смысл этого утверждения понятен из определения. Очевидно, что в среднем время обслуживания должно быть меньше времени между поступлениями соседних требований. Используя эту величину можно записать выражение для рекуррентного определения величин wn в компактном виде
Решая это уравнение последовательно, начиная с нулевого требования, можно получить
.
Условие стабильности М<un> <0, может быть записано в более привычной форме:
При выполнении этого условия будет существовать стационарное распределение вероятностей
Эта функция распределения может быть записана через искомую плотность вероятности для времени ожидания в очереди
.
Для ее нахождения Линдли получил интегральное уравнение, носящее его имя.
Функция c(u) определяется в свою очередь интегралом, похожим на свертку плотностей вероятности входного потока заявок и времени обслуживания
.
Решить уравнение Линдли в общем случае не удается. Если ввести преобразования Лапласа от функций плотности вероятности
то удается записать:
Дисциплины обслуживания. Модель с приоритетами
Дисциплина обслуживания – это способ определения того, какое требование в очереди должно обслуживаться следующим. Решение может основываться на одной из приведенных ниже характеристик или на их совокупности:
1) мера, определяемая относительным временем поступления рассматриваемого требования в очередь;
2) мера требуемого или полученного до сих пор времени обслуживания;
3) функция, определяющая принадлежность требования к той или иной группе.
Примерами дисциплин обслуживания являются постоянно используемая модель «первый пришел - первый обслужен» (FCFS-first came-first served), называемая в русскоязычной литературе «дисциплина обслуживания в порядке поступления»-ОПП. Приведем здесь список некоторых типичных дисциплин обслуживания.
ОПП-обслуживание в порядке поступления (FCFS);
ООП – обслуживание в обратном порядке, т.е. последнее поступившее требование обслуживается первым (LCFS);
ПК – первоочередное обслуживание требований с кратчайшей длительностью обслуживания (SPT/SJE);
ПКД – первоочередное обслуживание требований с кратчайшей длительностью дообслуживания (SRPT);
ПКС – первоочередное обслуживание требований с кратчайшей средней длительностью обслуживания (SEPT);
ПКСД – первоочередное обслуживание требований с кратчайшей средней длительностью дообслуживания (SERPT);
ПКОВ – первоочередное обслуживание требований с кратчайшим обязательным временем (SIPT).
Если сравнивать эти дисциплины по среднему времени ожидания попарно, и обозначать тот факт, что среднее время ожидания для дисциплины D1,больше или равно среднему времени ожидания для дисциплины D2 следующим образом: D1®D2, то можно построить следующую диаграмму
ПО ® ОПП ® ПК ® ПКД
¯
¯ ® ОП ®®®®
Итак, основным предметом анализа различных дисциплин обслуживания будем считать расчет среднего времени ожидания требования в очереди или среднего времени пребывания в системе.
Предположим, что требования принадлежат одному из P различных приоритетных классов, обозначаемых индексом p =1,2,3… P. Каждому требованию, находящемуся в системе в момент времени t ставится в соответствие значение некоторой приоритетной функции qp(t). Чем больше значение этой функции, тем выше приоритет требования. Всякий раз, когда принимается решение для выбора требования на обслуживание, выбор делается в пользу требования с наибольшим значением приоритетной функции. В простейшем случае в качестве приоритетной функции выбирается просто значение p. В этом случае приоритет требования тем больше, чем больший номер класса принадлежности оно имеет. Рассмотрим достаточно общую модель, основанную на системе M/G/1. Предположим, что требования из приоритетного класса p образуют пуассоновский поток с интенсивностью lp требований в секунду. Время обслуживания каждого требования из этого класса выбирается независимо в соответствие с распределением с плотностью вероятности bp(x) со средним значением
.
Введем следующие определения
Здесь r интерпретируется как доля времени, в течение которого сервер занят (r <1), а каждый из парциальных коэффициентов rp – как доля времени, в течение которого сервер занят обслуживанием заявок из приоритетного класса с номером p.
Если требование в процессе обслуживания может быть удалено из сервера и возвращено в очередь при поступлении требования с более высоким приоритетом, то говорят, что система работает с абсолютным приоритетом, если обслуживание любого требования, находящегося в сервере не может быть прервано, то говорят что СМО работает с относительным приоритетом.