Первым поступил — первым обслужен

Простейшая стратегия планирования "первым поступил — первым обслужен" (first-come-first-served — FCFS) известна также как схема "первым пришел — первым вышел", или схема строгой очередности. Как только процесс становится готовым к выполнению, он присоединяется к очереди готовых про­цессов. При прекращении выполнения текущего процесса для выполнения выбирается процесс, который находился в очереди дольше других.

На рис. 9.5 приведен пример выполнения одного цикла описанного ранее примера, а в табл. 9.5 представлены некоторые ключевые результаты. Во-первых, определено время завершения каждого процесса, так что мы можем определить время оборота T_r (turnaround time — ТАТ), которое представляет собой полное время, затраченное процессом в системе (время ожидания и время обслуживания). Более полезной величиной является нормализованное полное время, которое определяется как отношение полного времени ко времени обслуживания и указывает относительную задержку, испытываемую процессом. Минимальное значение этого отношения — 1. Возрастание значения отношения соответствует снижению уровня обслуживания.

Как видите, стратегия FCFS гораздо лучше работает для длинных процессов, чем для коротких. Вот данные, приведенные в работе [FINK88]:

Нормализованное время оборота для процесса Y оказывается существенно большим, чем для других процессов. Общее время нахождения процесса в системе в 100 раз превышает время, необходимое для обработки процесса. Такая ситуация возникает, когда короткий процесс поступает в систему сразу после длинного. С другой стороны, даже в таком экстремальном случае длинные процессы хорошо обрабатываются — так, время оборота процесса Z почти в два раза превышает время оборота Y, но нормализованное время ожидания процесса Z меньше 2.

Другая трудность при использовании стратегии FCFS связана с тенденцией процессов, ориентированных на работу с процессором, к получению преимущества над процессами, ориентированными на ввод-вывод. Рассмотрим множество процессов, один из которых ориентирован на использование процессора, а остальные — на работу с устройствами ввода-вывода. При работе процесса, ориентированного на процессор, все остальные процессы вынуждены находиться в состоянии ожидания. Некоторые из них могут находиться в очереди ввода-вывода, в заблокированном состоянии, но могут и вернуться в очередь готовых к выполнению процессов за то время, пока выполняется процесс, ориентированный на использование процессора. Возникает ситуация, когда несмотря на потенциальное наличие работы для устройств ввода-вывода они находятся в состоянии простоя. При прерывании выполнения текущего процесса, готовые процессы (ориентированные на ввод-вывод) быстро проходят через состояние выполнения и тут же оказываются заблокированными очередной операцией ввода-вывода. Если же в этот момент окажется заблокирован и процесс, ориентированный на использование процессора, то последний будет находиться в состоянии простоя и, таким образом, стратегия FCFS может привести к неэффективному использованию как устройств ввода-вывода, так и процессора.

Для однопроцессорных систем FCFS — не самая подходящая стратегия, но она часто комбинируется с использованием приоритетов. В этом случае плани­ровщик поддерживает ряд очередей, по одной для каждого уровня приоритета, и работает с процессами в каждой очереди в соответствии со стратегией FCFS. С примером такой системы мы познакомимся позже, при рассмотрении планирования с обратной связью.

Круговое планирование

Очевидный путь повышения эффективности работы с короткими процессами в схеме FCFS — использование вытеснения на основе таймера. Простейшая стратегия, основанная на этой идее, — стратегия кругового (карусельного) пла­нирования (round robin — RR). Таймер генерирует прерывания через определен­ные интервалы времени. При каждом прерывании исполняющийся в настоящий момент процесс помещается в очередь готовых к выполнению процессов, и начи­нает выполняться очередной процесс, выбираемый в соответствии со стратегией FCFS. Эта методика известна также как квантование времени (time slicing), поскольку перед тем как оказаться вытесненным, каждый процесс получает квант времени для выполнения.

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

На рис. 9.5 и в табл. 9.5 показаны результаты работы круговой стратегии при использовании кванта времени q с продолжительностью 1 и 4. Обратите внимание, что наиболее короткий процесс Е значительно быстрее проходит через систему при малом кванте времени.

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

В [HALD91] предложено улучшение кругового планирования, которое названо в работе виртуальным круговым планированием (virtual round robin — VRR) и позволяет избежать пристрастности в работе. Данная схема показана на рис. 9.7. Новый процесс присоединяется к очереди готовых к выполнению процессов, управление которой осуществляется на основе стра­тегии FCFS. Когда исчерпывается время работающего процесса, он возвраща­ется в очередь готовых к выполнению процессов; при блокировании процесса для ожидания завершения операции ввода-вывода он поступает в очередь процессов, ожидающих завершения операции ввода-вывода. Пока что все, как обычно. Новым оказывается наличие вспомогательной очереди, в которую переносятся процессы после их разблокирования по завершении операций ввода-вывода. При выборе процесса для выполнения преимущество отдается процессам из вспомогательной очереди. Изучение производительности такой схемы показывает, что с точки зрения беспристрастности данный подход лучше простого кругового планирования.