Глава 3. Дисциплины обслуживания заявок.

3.1 Бесприоритетная дисциплина обслуживания.

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

1) в порядке поступления (первой обслуживается заявка, поступившая раньше других);

2) в порядке, обратном порядку поступления заявок (первой обслуживается заявка, поступившая позже других);

3) наугад, т. е. путем случайного выбора из очереди.

Дисциплина обслуживания в порядке поступления называется FIFO1 (первый при), а дисциплина обслуживания в обратном порядке-LIFO2.

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

Бесприоритетчюе обслуживание заявок на основе дисциплины FIFO организуется в соответствии со следующим рисунком

Бесприоритетная дисциплина обслуживания

где Пр -процессор и О - очередь для заявок типа z1, ..., zn. Вновь поступившая заявка заносится в конец очереди. Заявки выбираются на обслуживание из начала очереди. Примером может служить очередь заданий печати для принтера.

3.2 Дисциплина обслуживания с относительными приоритетами заявок

Если требуется, чтобы заявки некоторого типа имели меньшее время ожидания (время пребывания), чем заявки других типов, то необходимо первым предоставить преимущественное право на обслуживание, называемое приоритетом. Приоритеты заявок характеризуются целыми положительными числами 1, 2, 3, ..., причем наиболее высокому приоритету соответствует меньшее число.

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

При использовании относительных приоритетов обработка заявок организуется по следующей схеме.

Дисциплина обслуживания с относительными приоритетами

Заявкам типа z_l ..., z_m присвоены относительные приоритеты i, ..., М соответственно. Заявка z_р поступившая в систему, заносится в очередь О_р, в которой хранятся заявки приоритета р=1, ....М. В очереди O_р заявки упорядочены по времени поступления. Когда процессор Пp заканчивает ранее начатое обслуживание, то управление передается программе ДИС­ПЕТЧЕР. ДИСПЕТЧЕР выбирает на обслуживание заявку с наи­большим приоритетом — заявку z_i, если очереди О₁ ..., О_i-1 не со­держат заявок. Выбранная заявка захватывает процессор Пр на все время обслуживания.