9. Вопросы планирования процессов в спо

К дисциплине планирования, в общем случае может применяться широкий спектр требований, наиболее существенные из которых следующие:

• она должна быть справедливой - не давать преимуществ одним процессам за счет других и ни в коем случае не допускать бесконечного откладывания процессов,

• она должна обеспечивать максимальную пропускную способность системы - выполнение максимального количества единиц работы (процессов) в единицу времени;

• она должна обеспечивать приемлемое время реакции для интерактивных пользователей;

• она должна обеспечивать гарантированное время реакции для процессов реального времени;

• она должна быть предсказуемой - дисперсия времен выполнения процессов, обладающих одинаковыми характеристиками, должна быть минимальной;

• она должна учитывать внешние приоритеты, присваиваемые процессам пользователем и/или администратором системы;

• накладные расходы по ее реализации (затраты процессорного времени и др. ресурсов) должны быть минимизированы;

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

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

С точки зрения реализации дисциплины планирования подразделяются, прежде всего, на дисциплины вытесняющие и невытесняющие (кооперативные). Для первых возможно прерывание активного процесса и лишение его ресурса ЦП по инициативе планировщика, для вторых - нет. Дисциплины с вытеснением выполняют более частые переключения процессов, следовательно, имеют большие накладные расходы. Но в большинстве случаев только они могут обеспечить требуемые показатели справедливости обслуживания.

Классификация дисциплин также определяется способом определения приоритетов процессов. Различают приоритеты:

• внешние - назначаемые администратором системы или пользователем в соответствии с классом пользователя и/или произведенной пользователем оплатой;

• статические - вычисляемые планировщиком при поступлении процесса в систему и не изменяемые впоследствии;

• динамические - перевычисляемые планировщиком периодически или/и при событиях, влияющих на планирование процессов;

• комплексные - динамически вычисляемые приоритеты, учитывающие внешний приоритет процесса, его статические характеристики, а также ход выполнения процесса, текущее состояние очереди готовых процессов и, возможно, состояние других системных ресурсов.

Среди базовых дисциплин планирования процессов можно назвать:

• “Первым пришел – первым обслуживается” – простейшая дисциплина без вытеснения, работа которой понятна из ее названия. Обеспечивает минимальные накладные расходы и гарантирует отсутствие бесконечного откладывания, но не обеспечивает справедливости для коротких процессов.

• “Карусель” - простейшая дисциплина с вытеснением. Процесс получает в свое распоряжение ЦП на некоторый квант времени Q (в простейшем случае – Q=const.). Если за время Q процесс не завершился, он вытесняется с ЦП и направляется в конец очереди готовых процессов, где ждет выделения ему следующего кванта, и т.д. Карусель обеспечивает наилучшие показатели справедливости. Эффективности карусели существенно зависит от выбора величины кванта Q.

• “Самая короткая работа - следующая” - наивысший приоритет имеет самый короткий процесс. Для того, чтобы применять эту дисциплину, должна быть заранее известна длительность процесса. Обеспечивает максимальную пропускную способность системы. Для коротких процессов дисциплина обеспечивает наилучшие показатели, но показатели для длинных процессов значительно хуже. Дисциплина может применяться как в вытесняющем, так и в невытесняющем варианте.

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

• “Многоуровневые очереди с обратной связью” предполагают расщепление очереди готовых процессов на две и более подочереди - более длинные (использовавшие больше времени ЦП) процессы попадают в очереди с большими номерами и, соответственно, с меньшими приоритетами. Селекция процессов по длительности, таким образом, происходит динамически. Разные очереди могут обслуживаться по разным дисциплинам.

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

• с высоким приоритетом - процессы реального времени;

• с нормальным приоритетом - интерактивные процессы;

• с низким приоритетом - счетные (пакетные) процессы.

Обычно внутри класса с нормальным приоритетом существует еще несколько градаций, которые для процесса могут вычисляться динамически. Типичные правила динамического перевычисления приоритетов сводятся к таким:

• приоритет процесса, долгое время находящегося в состоянии ожидания, повышается;

• приоритет процесса, часто выполняющего операции ввода-вывода, повышается;

• приоритет процесса, чаще получающего внешние сообщения и прерывания, повышается;

• если приоритет процесса не повышается, он убывает.