Очередь с приоритетами

Очереди с приоритетами относятся к дисциплинам, при которых входящим сообщениям приписывается ряд параметров (либо случайно, либо основываясь на некото­рых свойствах сообщения), определяющих относительную позицию сообщения в очереди. Эта позиция будет перемен­ной функцией времени, благодаря появлению в очереди сообщений с высший приоритетом. Для любого момента времени t приоритет данного сообщения определяется как функция приписываемых параметров; большая величина, достигаемая этой функцией, обусловливает выс­ший приоритет. Т. е. используемая система обозначе­ний такова, что сообщение с приоритетом q2 имеет прес имущественное обслуживание по сравнению с сообщением с приоритетом qlt если q2 > q1. В системах с фиксирован­ным приоритетом, которые обсуждаются сейчас, это оз­начает, что сообщение иа р-й группы приоритета имеет более высокий приоритет, чем сообщение из (р — 1)-й группы. Это правило приоритетов нарушается при про­цедуре «первый пришел — первым обслужен».

Кроме того, определим Wp — математическое ожидание времени пребывания в очереди сообщения с приписанным параметром p. \V0 может быть интерпретировано как математическое ожидапие времени, которое требуегся для окончания обслуживания сообщения, находящегося и обработке, при входе в систему пового сообщения.

Мы рассмотрим четыре типа систем приоритетов. 13 двух системах мы предполагаем, что как только началась обработка сообщения, она не может быть прервана, и полная обработка заключается в окончательной передаче сообщения. Это правило определяет системы без преры­вания. U противоположность этому, в двух других изу­чаемых типах систем обслуживания прерывание допус­кается, г. е. обработка (или передача) сообщения может быть прервана немедленно после появления в очереди сообщения с высшим приоритетом. Так как мы считаем, что каждое сообщение имеет определенное время обслу­живании (выбранное из некоторого экспоненциального распределения), связанное с ним, мы должны далее по­лагать, что когда прерванное сообщение вновь поступает в устройство обработки, его обслуживание начинается с того самого этапа, на котором оно было прервано (это относится к так называемому возобновлению после преры­вания) *).

Другой отличительной чертой для этих систем явля­ется форма приписывания приоритета. В двух системах приписывание приоритета для любого сообщения сохра­няется фиксированным во времени, т. о. входящему сооб­щению приписывается число (скажем р) для того, чтобы фиксировать уровень приоритета. Мы относим такие си­стемы к так называемым системам с фиксированным прио­ритетом. В двух других системах приписывание приори­тета изменяется линейно во времени. В частности, сооб­щение, входящее в очередь в момент Г, получает номер 6Р, где 0< 6г< о2< ...< Ьр, и приоритет q„ (/), свя­занный с этим сообщением в момент t, определяется

следующим образом:

qp(t) = {t-T)bP

где t изменяется от Т до времени окончания обслуживания сообщопия. Эта система относится к так называемым си­стемам приоритета с зависимой задержкой.