4. Планирование и диспетчеризация процессов и задач

Дисциплины FCFS, SNJ, SRT, RR.

Стратегии планирования

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

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

- по возможности заканчивать вычисления (вычислительные процессы) в том же самом порядке, в котором они были начаты;

-  отдавать предпочтение более коротким процессам;

-  предоставлять всем пользователям (процессам пользователей) одинаковые услуги, в том числе и одинаковое время ожидания.

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

Когда говорят о диспетчеризации, то всегда в явном или неявном виде имеют в виду понятие задачи (потока). Если ОС не поддерживает механизм гредои, то можно заменять понятие задачи на понятие процесса. Так как эти термины часто используются именно в таком смысле, мы вынуждены будем использовать тер­мин «процесс» как синоним термина «задача».

Известно большое количество правил (дисциплин диспетчеризации), в соответ­ствии с которыми формируется список (очередь) готовых к выполнению задач. Различают два больших класса дисциплин обслуживания — бесприоритетные и приоритетные. При бесприоритетпом обслуживании выбор задачи произво­дится в некотором заранее установленном порядке без учета их относительной важности и времени обслуживания. При реализации приоритетных дисциплин обслуживания отдельным задачам предоставляется преимущественное право по­пасть в состояние исполнения. Перечень дисциплин обслуживания и их класси­фикация приведены на рис. 2.1.

Запомним о приоритетах следующее:

□   приоритет, присвоенный задаче, может являться величиной постоянной;

□   приоритет задачи может изменяться н процессе ее решения.

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

Рассмотрим кратко некоторые основные (наиболее часто используемые) дисци­плины диспетчеризации.

Самой простои в реализации является дисциплина FCFS (first come — first served), согласно которой задачи обслуживаются «в порядке очереди», то есть в порядке их появления. Тс задачи, которые были заблокированы в процессе работы (попа­ли в какое-либо из состояний ожидания, например, из-за операций ввода/выво­да), после перехода в состояние готовности ставятся в эту очередь готовности перед теми задачами, которые еще не выполнялись.

Дисциплина обслуживания SJN (shortest job next, что означает: следующим будет выполняться кратчайшее задание) требует, чтобы для каждого задания была из­вестна оценка и потребностях машинного времени. Необходимость сообщать ОС характеристики задач, в которых описывались бы потребности в ресурсах вычис­лительной системы, привела к тому, что были разработаны соответствующие языковые средства. В частности, язык JCL (job control language, язык управле­ния заданиями) был одним из наиболее известных. Пользователи вынуждены были указывать предполагаемое время выполнения, и для того, чтобы они не злоупотребляли возможностью указать заведомо меньшее время выполнения (с целью получить результаты раньше других), ввели подсчет реальных потреб­ностей. Диспетчер задач сравнивал заказанное время и время выполнения, и в случае превышения указанной оценки в данном ресурсе ставил данное задание не в начало, а и конец очереди. Еще в некоторых ОС в таких случаях использова­лась система штрафов, при которой и случае превышения заказанного машинно­го времени оплата вычислительных ресурсов осуществлялась уже но другим рас­ценкам.

Дисциплина обслуживания SJN предполагает, что имеется только одна очередь задании, готовых к выполнению. И задания, которые в процессе своего исполне­ния были временно заблокированы (например, ожидали завершения операции ввода/вывода), вновь попадают в конец очереди готовых к выполнению наравне с вновь поступающими. Это приводи к  тому, что задания, которым требуется очень немного времени для своего завершения, вынуждены ожидать процессор наравне с длительными работами, что не всегда хорошо.

Для устранения этого недостатка и была предложена дисциплина SRT (shortest remaining Lime, следующее задание требует меньше всего времени для своего за­вершения).

Дисциплина обслуживания RR предполагает, что каждая задача получает процес­сорное время порциями (говорят: квантами времени, q). После окончания кванта времени q задача снимается с процессора и он передается следующей задаче. Снятая задача ставится в конец очереди задач, готовых к выполнению. Эта дис­циплина обслуживания иллюстрируется рис. 2.3. Для оптимальной работы сис­темы необходимо правильно выбрать закон, по которому кванты времени выде­ляются задачам.