Базовые дисциплины планирования
2.2. Базовые дисциплины планирования
Ниже приводятся описания некоторых базовых дисциплин планирования. Эти дисциплины достаточно просты в реализации и хорошо исследованы методами как аналитического (например, [12]), так и имитационного (например, [27]) моделирования. Мы называем их базовыми, поскольку в реальных системах они служат основой для построения более сложных и гибких модификаций и комбинаций, для которых аналитические модели построить, как правило, невозможно.
FCFS (first come - first serve - первым пришел - первым обслуживается) - простейшая дисциплина, работа которой понятна из ее названия. Это дисциплина без вытеснения, то есть, процесс, выбранный для выполнения на ЦП, не прерывается, пока не завершится (или не перейдет в состояние ожидания по собственной инициативе). Как дисциплина без вытеснения, FCFS обеспечивает минимум накладных расходов. Среднее потерянное время при применении этой дисциплины не зависит от длительности процесса, но штрафное отношение при равном потерянном времени будет большим для коротких процессов. Поэтому дисциплина FCFS считается лучшей для длинных процессов. Существенным достоинством этой дисциплины, наряду с ее простотой, является то обстоятельство, что FCFS гарантирует отсутствие бесконечного откладывания процессов: любой поступивший в систему процесс в конце концов будет выполнен независимо от степени загрузки системы.
На рисунке 2.2 показан пример планирования по дисциплине FCFS для трех процессов - A, B и C. На временной диаграмме каждый прямоугольник представляет интервал времени, в течение которого процесс находится в системе. Над верхним левым углом такого прямоугольника указан идентификатор процесса, а в скобках - его длительность. Незатемненные участки соответствуют активному состоянию процесса, затемненные - состоянию ожидания. Процесс A поступает в момент времени 0 и требует для выполнения 6 единиц процессорного времени. ЦП в этот момент свободен, и процесс A сразу же активизируется. В момент времени 2 поступает процесс B, требующий 11 единиц. Поскольку ЦП занят процессом A, процесс B ожидает в очереди готовых процессов до момента 6, когда процесс A закончится и освободит ЦП. Только после этого процесс B начинает выполняться. Пока процесс B выполняется, поступают еще два процесса: C - в момент времени 8 и D - в момент 10, которые ждут завершения процесса B. Когда процесс B завершится, ЦП будет отдан процессу C, поступившему раньше, а процесс D остается в ожидании. В линейке, расположенной под временной шкалой, указаны идентификаторы процессов, активных в данный момент времени. Читатель может сам определить показатели эффективности планирования - для каждого процесса и усредненные. Следует, однако, предупредить, что к усредненным показателям надо относиться с осторожностью, так как достоверными могут считаться только результаты, полученные на статистически значимой выборке.
