Глава 2. Управление задачами

Понятия процесса (process) и потока выполнения (thread) нам уже известны. Мы теперь знаем, в чем здесь имеется сходство, а в чем — существенное различие. Од­нако в данной главе при рассмотрении вопросов распределения процессорного времени мы не всегда будем разделять эти понятия. Дело в том, что по отношению к этому ресурсу — процессорному времени — оба этих понятия практически экви­валенты. Они выступают просто как некоторая работа, для выполнения которой необходимо предоставить центральный процессор. Поэтому мы будем в основном использовать термин задача (task), который является как бы обобщающим. Ведь каждый поток выполнения на самом деле получает статус задачи, и для него созда­ется соответствующий дескриптор. Но мы должны помнить о различиях между дескриптором процесса и дескриптором задачи. Даже если процесс состоит из един­ственного потока, мы говорим о дескрипторе процесса, содержащем информацию, с помощью которой операционная система отслеживает все ресурсы, необходи­мые процессу для его выполнения. Один из основных модулей супервизора опера­ционной системы — диспетчер задач — переводит процессы в одно из состояний в зависимости от того, доступен тот или иной ресурс или не доступен. И посколь­ку в мультизадачной системе любой процесс содержит хотя бы один поток, то по­току (то есть задаче) ставится в соответствие дескриптор задачи, в котором сохра­няется контекст этих вычислений. Сказанное справедливо для мультипрограммных систем, поддерживающих мультизадачный режим. В мультипрограммных систе­мах, не поддерживающих мультизадачность, контекст прерванного процесса хра­нится в дескрипторе этого процесса. Заметим, что повсеместно распространенные системы Windows 9x/NT/2000/XP являются и мультипрограммными, и мульти­задачными. Не случайно начиная с Windows NT и Windows 95 компания Microsoft отказалась от термина «задача» и стала использовать понятия процесса и потока выполнения (треда, нити). Правда, для изложения вопросов диспетчеризации это становится неудобным, ибо здесь чаще используется обобщающее понятие.

Еще одним доводом в пользу термина «задача» при рассмотрении вопросов ор­ганизации распределения процессорного времени между выполняющимися вы­числениями является аналогичный выбор этой сущности разработчиками про-

Управление задачами__________________________________________________ 51

цессоров. Именно для отображения этой ситуации и обеспечения дополнитель­ными возможностями системных программистов в решении вопросов распреде­ления процессорного времени они вводят специальные информационные струк­туры и аппаратную поддержку для работы с ними. Во многих современных микропроцессорах, предназначенных для построения на их основе мощных муль­типрограммных и мультизадачных систем, имеются дескрипторы задач. Приме­ром, подтверждающим этот тезис, являются микропроцессоры, совместимые с архитектурой ia32, то есть с 32-разрядными процессорами фирмы Intel. Основ­ные архитектурные особенности этих микропроцессоров, специально прорабо­танные для организации мультизадачных операционных систем, рассматрива­ются достаточно подробно в главе 4. Здесь мы лишь отметим тот факт, что в этих процессорах имеется специальная аппаратная поддержка организации мульти­задачного (и мультипрограммного) режима. Речь идет о сегменте состояния за­дачи (Task State Segment, TSS), который предназначен, прежде всего, для сохра­нения контекста потока или процесса и который легко позволяет организовать и мультипрограммный, и мультизадачный режимы. Не случайно был введен тер­мин «задача», ибо он здесь применим и по отношению к полноценному вычисли­тельному процессу, и по отношению к легковесному процессу (потоку выполне­ния, треду, нити). На самом деле этот аппаратный механизм применяется гораздо реже, чем об этом думали разработчики архитектуры ia32. На практике оказа­лось, что для сохранения контекста потоков эффективнее использовать программ­ные механизмы, хотя они и не обеспечивают такой же надежности, как аппарат­ные.

Итак, операционная система выполняет следующие основные функции, связан­ные с управлением процессами и задачами:

- создание и удаление задач;

- планирование процессов и диспетчеризация задач;

- синхронизация задач, обеспечение их средствами коммуникации.

Создание задачи сопряжено с формированием соответствующей информаци­онной структуры, а ее удаление — с расформированием. Создание и удаление задач осуществляется по соответствующим запросам от пользователей или от самих задач. Задача может породить новую задачу. При этом между задачами появляются «родственные» отношения. Порождающая задача называется «от­цом», «родителем», а порожденная — «потомком». Отец может приостановить или удалить свою дочернюю задачу, тогда как потомок не может управлять от­цом.

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

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

52__________________________________________ Глава 2. Управление задачами

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

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

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

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

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

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

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

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

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

планирования стали называть диспетчеризацией¹. Очевидно, что планирование процессов осуществляется гораздо реже, чем текущее распределение ресурсов меж­ду уже выполняющимися задачами. Основное различие между долгосрочным и краткосрочным планировщиками заключается в частоте их запуска, например: крат­косрочный планировщик может запускаться каждые 30 или 100 мс, долгосрочный — один раз в несколько минут (или чаще; тут многое зависит от общей длительности решения заданий пользователей).

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

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

Планирование вычислительных процессов и стратегии планирования

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

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

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

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

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

¹ К сожалению, здесь наблюдается терминологическая несогласованность. Собственно модули супер­визора, отвечающие за диспетчеризацию задач, часто называют планировщиками (scheduler). Одна­ко фактически, говоря о тех же планировщиках памяти или о каких-нибудь других модулях, отвеча­ющих за динамическое распределение ресурсов, имеют в виду, что эти планировщики осуществляют диспетчеризацию. Наконец, иногда диспетчеризацию называют краткосрочным планированием.

54__________________________________________ Глава 2. Управление задачами

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

На сегодняшний день абсолютное большинство компьютеров — это персональные IBM-совместимые компьютеры, работающие на платформах Windows компании Microsoft. Это однопользовательские диалоговые мультипрограммные и мульти­задачные системы. При создании операционных систем для персональных компь­ютеров разработчики, прежде всего, стараются обеспечить комфортную работу с системой, то есть основные усилия уходят на проработку пользовательского ин­терфейса. Что касается эффективности организации вычислений, то она, видимо, тоже должна оцениваться с этих позиций. Если же считать системы Windows опе­рационными системами общего назначения, что тоже возможно, ибо эти системы повсеместно используют для решения самых разнообразных задач автоматизации, то также следует признать, что принятые в системах Windows стратегии обслужи­вания приводят к достаточно высокой эффективности вычислений. Некоторым даже удается использовать системы Windows NT/2000 для решения задач реаль­ного времени. Однако выбор этих операционных систем для таких задач скорее всего делается либо вследствие некомпетентности, либо из-за невысоких требова­ний ко времени отклика и гарантиям обслуживания со стороны самих систем ре­ального времени, которые реализуются на Windows NT/2000.

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

Например, в Windows 2000 можно открыть окно Свойства системы, перейти на вкладку Дополнительно, щелчком на кнопке Параметры быстродействия открыть од­ноименное окно и с помощью переключателя в разделе Отклик приложений уста­новить режим Оптимизировать быстродействие приложений. Это будет соответство­вать выбору такой стратегии диспетчеризации задач, в соответствии с которой приоритет на получение процессорного времени будут иметь задачи пользовате­ля, а не фоновые служебные вычисления. В предыдущей версии ОС — Windows NT 4.0 — для выбора нужной ему стратегии пользователь должен был на вкладке Быстродействие окна Свойства системы установить желаемое значение в поле Уско­рение приложения переднего плана. Это ускорение можно сделать максимальным (по умолчанию), а можно его свести к нулю. Последний вариант означал бы, что все запущенные пользователем приложения будут иметь одинаковый приори-

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

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

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

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

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

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

В концепции приоритетов имеем следующие варианты:

- приоритет, присвоенный задаче, является величиной постоянной;

- приоритет изменяется в течение времени решения задачи {динамический прио­ритет).

56__________________________________________ Глава 2, Управление задачами

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

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

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

Самой простой в реализации является дисциплина FCFS (First Come First Served — первым пришел, первым обслужен), согласно которой задачи обслуживаются «в по­рядке очереди», то есть в порядке их появления. Те задачи, которые были заблоки-

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

рованы в процессе работы (попали в какое-либо из состояний ожидания, напри­мер из-за операций ввода-вывода), после перехода в состояние готовности вновь ставятся в эту очередь готовности. При этом возможны два варианта. Первый (са­мый простой) — это ставить разблокированную задачу в конец очереди готовых к выполнению задач. Этот вариант применяется чаще всего. Второй вариант за­ключается в том, что диспетчер помещает разблокированную задачу перед теми задачами, которые еще не выполнялись. Другими словами, в этом случае образу­ется две очереди (рис. 2.2): одна очередь образуется из новых задач, а вторая оче­редь — из ранее выполнявшихся, но попавших в состояние ожидания. Такой под­ход позволяет реализовать стратегию обслуживания «по возможности заканчивать вычисления в порядке их появления». Эта дисциплина обслуживания не требует внешнего вмешательства в ход вычислений, при ней не происходит перераспреде­ления процессорного времени. Про нее можно сказать, что она относится к не вы­тесняющим дисциплинам¹.

Очередь новых задач Рис. 2.2. Дисциплина диспетчеризации FCFS

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

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

¹ Существующие дисциплины диспетчеризации процессов могут быть разбиты на два класса: вытес­няющие (preemptive) и не вытесняющие (non-preemptive). В первых пакетных операционных систе­мах часто реализовывали параллельное выполнение заданий без принудительного перераспределе­ния процессора между задачами. В большинстве современных ОС для мощных вычислительных систем, а также в ОС для персональных компьютеров, ориентированных на высокопроизводитель­ное выполнение приложений (Windows 9x/NT/2000/XP, Linux, OS/2), реализованы вытесняющие дисциплины диспетчеризации (вытесняющая многозадачность).

58__________________________________________ Глава 2. Управление задачами

столько же, сколько трудоемкие задания. Избежать этого недостатка позволяют дис­циплины SJN и SRT. Правило FCFS применяется и в более сложных дисциплинах диспетчеризации. Например, в приоритетных дисциплинах диспетчеризации, если имеется несколько задач с одинаковым приоритетом, которые стоят в очереди гото­вых к выполнению задач, то попадают они в эту очередь с учетом времени.

Дисциплина обслуживания SJN( Shortest Job Next — следующим выполняется са­мое короткое задание) требует, чтобы для каждого задания была известна оценка в потребностях машинного времени. Необходимость сообщать операционной сис­теме характеристики задач с описанием потребностей в ресурсах вычислительной системы привела к тому, что были разработаны соответствующие языковые сред­ства. В частности, ныне уже забытый язык]СL (Job Control Language — язык уп­равления заданиями) был одним из наиболее известных. Пользователи вынужде­ны были указывать предполагаемое время выполнения задачи и для того, чтобы они не злоупотребляли возможностью указать заведомо меньшее время выполне­ния (с целью возможности получить результаты раньше других), ввели подсчет реальных потребностей. Диспетчер задач сравнивал заказанное время и время вы­полнения и в случае превышения указанной оценки потребности в данном ресур­се ставил данное задание не в начало, а в конец очереди. Еще в некоторых операци­онных системах в таких случаях использовалась система штрафов, при которой в случае превышения заказанного машинного времени оплата вычислительных ре­сурсов осуществлялась уже по другим расценкам.

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

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

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

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

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

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

Для решения перечисленных проблем используется дисциплина обслуживания, называемая карусельной (Round Robin, RR), и приоритетные методы обслужи­вания.

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

Рис. 2.3. Карусельная дисциплина диспетчеризации

Величина кванта времени q выбирается как компромисс между приемлемым време­нем реакции системы на запросы пользователей (с тем, чтобы их простейшие запро­сы не вызывали длительного ожидания) и накладными расходами на частую смену контекста задач. Очевидно, что при прерываниях операционная система вынуждена выполнять большой объем работы, связанной со сменой контекста. Она должна со­хранить достаточно большой объем информации о текущем (прерываемом) процес­се, поставить дескриптор снятой задачи в очередь, занести в рабочие регистры про­цессора соответствующие значения для той задачи, которая теперь будет выполняться (ее дескриптор расположен первым в очереди готовых к исполнению задач). Если величина q велика, то при увеличении очереди готовых к выполнению задач реак­ция системы станет медленной. Если же величина q мала, то относительная доля

60__________________________________________ Глава 2. Управление задачами

накладных расходов на переключения контекста между исполняющимися задачами увеличится, и это ухудшит производительность системы.

В некоторых операционных системах есть возможность указывать в явном виде величину кванта времени или диапазон возможных значений, тогда система будет стараться выбирать оптимальное значение сама. Например, в операционной сис­теме OS/2 в файле CONFIG.SYS есть возможность с помощью оператора TIMESLICE указать минимальное и максимальное значения для кванта q. Так, например, стро­ка TIMESLICE=32,256 указывает, что минимальное значение равно 32 мс, а макси­мальное — 256. Если некоторая задача прервана, поскольку израсходован выде­ленный ей квант времени q, то следующий выделенный ей интервал будет увеличен на время, равное одному периоду таймера (около 32 мс), и так до тех пор, пока квант времени не станет равным максимальному значению, указанному в операто­ре TIMESLICE. Этот метод позволяет OS/2 уменьшить накладные расходы на пе­реключение задач в том случае, если несколько задач параллельно выполняют длительные вычисления. Следует заметить, что диспетчеризация задач в этой опе­рационной системе реализована, пожалуй, наилучшим образом с точки зрения ре­акции системы и эффективности использования процессорного времени.

Дисциплина карусельной диспетчеризации более всего подходит для случая, когда все задачи имеют одинаковые права на использование ресурсов центрального про­цессора. Однако как мы знаем, равенства в жизни гораздо меньше, чем неравенства. Одни задачи всегда нужно решать в первую очередь, тогда как остальные могут по­дождать. Это можно реализовать за счет того, что одной задаче мы (или диспетчер задач) присваиваем один приоритет, а другой задаче — другой. Задачи в очереди будут располагаться в соответствии с их приоритетами. Формирует очередь диспетчер за­дач. Процессор в первую очередь будет предоставляться задаче с самым высоким приоритетом, и только если ее потребности в процессоре удовлетворены или она попала в состояние ожидания некоторого события, диспетчер может предоставить его следующей задаче. Многие дисциплины диспетчеризации по-разному исполь­зуют основную идею карусельной диспетчеризации и механизм приоритетов.

Дисциплина диспетчеризации RR — это одна из самых распространенных дисцип­лин. Однако бывают ситуации, когда операционная система не поддерживает в яв­ном виде дисциплину карусельной диспетчеризации. Например, в некоторых опе­рационных системах реального времени используется диспетчер задач, работающий по принципу абсолютных приоритетов (процессор предоставляется задаче с мак­симальным приоритетом, а при равенстве приоритетов он действует по принципу очередности) [7, 11]. Другими словами, причиной снятия задачи с выполнения может быть только появление задачи с более высоким приоритетом. Поэтому если нужно организовать обслуживание задач таким образом, чтобы все они получали процессорное время равномерно и равноправно, то системный оператор может сам организовать эту дисциплину. Для этого достаточно всем пользовательским зада­чам присвоить одинаковые приоритеты и создать одну высокоприоритетную зада­чу, которая не должна ничего делать, но которая, тем не менее, будет по таймеру (через указанные интервалы времени) планироваться на выполнение. Благодаря высокому приоритету этой задачи текущее приложение будет сниматься с выпол­нения и ставиться в конец очереди, а поскольку этой высокоприоритетной задаче

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

на самом деле ничего делать не надо, то она тут же освободит процессор, и из оче­реди готовности будет взята следующая задача.

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

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

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

А есть дисциплины диспетчеризации, в которых ничто не может отобрать у задачи процессор, пока она сама его не освободит. Освобождение процессора в этом слу­чае, как правило, связано с тем, что задача попадает в состояние ожидания некото­рого события.

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

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

62 Глава 2. Управление задачами

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

Для пользователей это означает, что управление системой может теряться на не­который произвольный период времени, который определяется процессом выпол­нения приложения (а не системой, старающейся всегда обеспечить приемлемое время реакции на запросы пользователей) [27]. Если приложение тратит слишком много времени на выполнение какой-либо работы (например, на форматирование диска), пользователь не может переключиться с этой на другую задачу (например, на текстовый или графический редактор, в то время как форматирование продол­жалось бы в фоновом режиме). Эта ситуация нежелательна, так как пользователи обычно не хотят долго ждать, когда машина завершит свою задачу.

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

Например, в ныне уже забытой операционной среде Windows 3.x нативные 16-раз­рядные приложения этой системы разделяли между собой процессорное время именно таким образом. И именно программисты должны были обеспечивать «дру­жественное» отношение своей программы к другим выполняемым одновременно с ней программам, достаточно часто отдавая управление ядру системы. Крайним проявлением «недружественности» приложения является его зависание, приво­дящее к общему краху системы — прекращению всех вычислений. В системах с вы­тесняющей многозадачностью такие ситуации, как правило, исключены, так как центральный механизм д<