Дисциплины диспетчеризации

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

При использовании приоритетов возможны два варианта:

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

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

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

Существующие дисциплины дис­петчеризации процессов могут быть разбиты на два класса – вытесняющие (pre­emptive) и не вытесняющие (non-preemptive). Диспетчеризация без перераспределения процессорного времени, т.е. невы­тесняющая многозадачность (non-preemptive multitasking) – это такой способ диспетчеризации процессов, при котором активный процесс выполняется до тех пор, пока он сам, «по собственной инициативе», не отдаст управ­ление Диспетчеру задач. Диспетчер задач – программа, обслуживающая очередь задач на использование центрального процессора.

Диспетчеризация перераспределением процессорного времени между задача­ми, то есть вытесняющая многозадачность (preemptive multitasking) – это такой способ, при котором решение о переключении процессора с выполнения одного процесса на выполнение другого процесса принимается диспетчером задач, а не самой активной задачей. При вытесняющей многозадачности механизм диспетчеризации задач целиком сосредоточен в операционной системе, и программист может писать свое приложение, не заботясь о том, как оно будет выполняться параллельно с другими задачами. В большинстве современных ОС для мощных вычислительных систем, а также и в ОС для ПК, ориентированных на высокопроизводительное выполнение приложений (Windows NT, OS/2, Unix), реализована вытесняющая многозадачность.

Рассмотрим, как организована вытесняющая многозадачность в ОС Windows NT. Жизненный цикл задачи начинается в тот момент, когда программа создает новую задачу. Менеджер процессов выделяет память для задачи и обращается к ядру. После инициализации задача проходит через следующие состояния:

• Готовность. При поиске задачи на выполнение диспетчер просматривает только задачи, находящиеся в состоянии готовности, у которых есть все для выполнения, но не хватает только процессора.

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

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

• Ожидание. Задача может входить в состояние ожидания несколькими способами: задача по своей инициативе ожидает некоторый объект, для того чтобы синхронизировать свое выполнение; операционная система (например, подсистема ввода-вывода) может ожидать в интересах задачи; подсистема окружения может непосредственно заставить задачу приостановить себя. Когда ожидание задачи подойдет к концу, она возвращается в состояние готовности.

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

• Завершение. Когда выполнение задачи закончилось, она входит в состояние завершения. Находясь в этом состоянии, задача может быть либо удалена, либо не удалена. Это зависит от алгоритма работы менеджера объектов, в соответствии с которым он и решает, когда удалять объект.

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

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

К достоинствам этой дисциплины, прежде всего, можно отнести простоту реали­зации и малые расходы системных ресурсов на формирование очереди задач.

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

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

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

Все эти три дисциплины обслуживания могут использоваться для пакетных ре­жимов обработки, когда пользователь не вынужден ожидать реакции системы, а просто сдает свое задание и через несколько часов получает свои результаты вычислений. Для интерактивных же вычислений желательно прежде всего обес­печить приемлемое время реакции системы и равенство в обслуживании, если система является мультитерминальной. Если же это однопользовательская сис­тема, но с возможностью мультипрограммной обработки, то желательно, чтобы те программы, с которыми мы сейчас непосредственно работаем, имели лучшее время реакции, нежели наши фоновые задания. При этом мы можем пожелать, чтобы некоторые приложения, которые выполняются без нашего непосредственного уча­стия (например, программа получения электронной почты, использующая модем и коммутируемые линии для передачи данных), тем не менее гарантированно по­лучали необходимую им долю процессорного времени. Для решения подобных проб­лем используется дисциплина обслуживания, называемая RR (round robin – круговая, карусельная), и приоритетные методы обслуживания.

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

Дисциплина диспетчеризации RR – это одна из самых распространенных дис­циплин. В своей простейшей реализации дисциплина карусельной диспетчеризации пред­полагает, что все задачи имеют одинаковый приоритет. Если же необходимо вве­сти механизм приоритетного обслуживания, то это, как правило, делается за счет организации нескольких очередей. Процессорное время будет предоставляться в первую очередь тем задачам, которые стоят в самой привилегированной очереди. Если она пустая, то диспетчер задач начнет просматривать остальные очереди. Именно по такому алгоритму действует диспетчер задач в операционных систе­мах OS/2 и Windows NT.

Дисциплины обслуживания FCFS, SJN, SRT относятся к невытесняющим. Дисциплина RR и многие другие, построенные на ее основе, относятся к вытес­няющим.