З

Конец … начало

Выполнение

апуск Выбор Завершение

а) упрощенный фрагмент диспетчеризации с FCFS (FIFO) без квантования времени ЦП.

З Конец … начало Выполнениеапуск Выбор Завершение

Истечение кванта

б) упрощенный фрагмент схемы диспетчеризации с FCFS (FIFO) с квантованием времени ЦП.

Рис. 4. Одноочередная реализация диспетчеризации для операций Запуск, Выбор, Истечение_кванта

На рис. 4 представлена схема формирования очереди готовых процессов при выполнении операций планирования Запуск и операции диспетчеризации Истечение_кванта. Заметим, что операция Выбор производит выделение кванта времени ЦП, процессу, дескриптор которого находится в начале очереди готовых процессов, формируемой по принципу FCFS. Алгоритм, иллюстрируемый данной схемой, прост для реализации; необходимо отметить, что в рассмотренной схеме в наиболее благоприятных условиях находятся процессы, которым требуется меньшее время для использования ресурсов (включая ЦП).

4.2.2. Краткое описание алгоритма многоочередной диспетчеризации для операцииИстечение_кванта.

Рассмотренная выше дисциплина является одноочередной. Ее усовершенствованием является модификация данной схемы, связанная с введением многоочередной схемы диспетчеризации.

На рис.5 представлена схема многоочередной диспетчеризации.

Очередь1

З

Конец … начало

Выполнение

апуск Выбор Завершение

Очередь2

Конец … начало

Очередь3

Конец … начало

:

:

Очередь1

Конец … начало

:

:

Очередь n-1

Конец … начало

Очередь n

Конец … начало

Истечение_кванта

Рис.5. Многоочередная реализация диспетчеризации для операций Истечение_кванта.

Для представленной схемы организуются n очередей. После выполнения операции планирования для какого-либо процесса его дескриптор помещается в Очередь 1. В принципе, в качестве первой очереди может использоваться списковая структура, формирование которой осуществляется не обязательно в соответствии с правилом FCFS. В очереди с номерами от 2 до n поступают дескрипторы активных процессов, отношении которых произведена операция Истече­ние_кванта. Поступление и извлечение дескрипторов процессов в/из очередей осуществляется следующим образом.

При выполнении операции Выбор процесс, дескриптор которого расположен в начале i-той очереди (1<=i<=n), будет помещен в состояние выполнение только в том случае, если все очереди от первой до (i-1)-ой – пустые. Выполнение выбранного процесса будет осуществляться в течение кванта времени (если, конечно, не произойдет операция диспетчеризации Запрос_ресурса, Завершение или какая-либо другая операция планирования процессов в отношении данного выполняемого процесса). После истечения кванта времени, вследст­вие выполнения операции диспетчеризации Истечение_кванта времени ЦП произойдет перевод процесса из состояния выполнение в состоя­ние готовность и его дескриптор поступает в конец очереди с номером i+1.

Последующая за этим операция Выбор переведет в состояние выполнение тот процесс, дескриптор которого стоит в начале очереди с самым младшим номером. Таким процессом может оказаться процесс, дескриптор которого стоял следующим в очереди i или в очереди i+1 (при условии, что после выбора процесса из очереди i последняя оказалась пустой). Дескриптор процесса, переводимого из пассивного состояния в активное (с помощью операции Запуск), поступает в первую очередь (i=1). Если это имеет место быть, после окончания кванта времени ЦП, выделенного для выполнения процесса из очереди i, будет осуществлен запуск процесса, дескриптор которого помещен в очередь номер 1.

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