§ 2.1.Общиепринципыорганизациимногозадачности
2.1.1. Основные понятия и определения
Как было указано выше понятие процесса было введено для реализации идей мно-
гозадачности. Необходимо различать системныеуправляющиепроцессы, представ-
ляющие работу супервизора операционной системы и занимающиеся распределением и
управлением ресурсов, от всех других. Для системных управляющих процессов в боль-
шинстве операционных систем ресурсы распределяются изначально и однозначно. Эти
процессы управляют ресурсами системы, поэтому обычно их не принято называть зада-
чами. Термин же задача обычно употребляют только по отношению к процессам поль-
зователей. Но это справедливо не для всех ОС. Например, в так называемых «микро-
ядерных» ОС (в качестве примера можно привести ОС реального времени QNX)
большинство управляющих программных модулей самой системы и даже драйверы
имеют статус высокоприоритетных процессов, для выполнения которых необходимо
выделить соответствующие ресурсы. Аналогично и в UNIX-системах выполнение сис-
темных программных модулей тоже имеет статус системных процессов, которые полу-
чают ресурсы для своего исполнения.
Если обобщать и рассматривать не только обычные ОС общего назначения, но и,
например, ОС реального времени, то можно сказать, что процесс может находиться в
активном и пассивном состоянии. В активномсостоянии процесс может участвовать
в конкуренции за использование ресурсов вычислительной системы, а в пассивном - он
только известен системе, но в конкуренции не участвует (хотя его существование в сис-
теме и сопряжено с предоставлением ему оперативной и/или внешней памяти).
В свою очередь, активныйпроцесс может быть в одном из следующих состояний
[2, 5]:
• выполнения - все затребованные процессом ресурсы выделены. В этом состоянии в
каждый момент времени может находиться только один процесс, если речь идет об
однопроцессорной вычислительной системе;
• готовностиквыполнению - ресурсы могут быть предоставлены, тогда процесс пе-
рейдет в состояние выполнения;
• блокирования или ожидания - затребованные ресурсы не могут быть предоставле-
ны, или не завершена операция ввода/вывода.
В большинстве операционных систем последнее состояние, в свою очередь, под-
разделяется на множество состояний ожидания, соответствующих определенному виду
ресурса, из-за отсутствия которого процесс переходит в заблокированное состояние.
В обычных ОС, как правило, процесспоявляетсяпризапускекакой-нибудьпро-
граммы. Система создает для нового процесса соответствующий дескриптор (описа-
тель) процесса, и он начинает выполняться. Поэтому пассивного состояния в обычных
ОС не существует. В ОС реального времени (ОСРВ) ситуация иная. Обычно при проек-
тировании системы реального времени уже заранее известен состав программ, которые
должны будут выполняться. Известны и многие их параметры, которые необходимо
учитывать при распределении ресурсов (например, объем памяти, приоритет, средняя
длительность выполнения, открываемые файлы, используемые устройства и т. п.). По-
этому для них заранее заводят дескрипторы задач с тем, чтобы впоследствии не тратить
драгоценное время на организацию дескриптора и поиск для него необходимых ресур-
сов. Таким образом, в ОСРВ многие процессы (задачи) могут находиться в состоянии
бездействия, что показано на рис.2.1 пунктиром [2].
Рис.2.1. Граф состояний процесса
За время своего существования процесс может неоднократно совершать переходы
из одного состояния в другое. Это обусловлено обращениями к операционной системе с
запросами ресурсов и выполнения системных функций, которые предоставляет опера-
ционная система, взаимодействием с другими процессами, появлением сигналов преры-
вания от таймера, каналов и устройств ввода/вывода, а также других устройств. Воз-
можные переходы процесса из одного состояния в другое отображены в виде графа
состояний на рис. 1. Рассмотрим эти переходы более подробно.
Процесс из состояниябездействия может перейти в состояниеготовности в
следующих случаях [2]:
• по команде пользователя. Имеет место в тех диалоговых операционных системах,
где программа может иметь статус задачи, а не просто быть исполняемым файлом и
только на время исполнения получать статус задачи;
• при выборе из очереди планировщиком, что характерно для операционных систем,
работающих в пакетном режиме;
• по вызову из другой задачи;
• по прерыванию от внешнего инициативного устройства;
• при наступлении запланированного времени запуска программы.
Последние два способа запуска задачи, при которых процесс из состояния бездей-
ствия переходит в состояние готовности, характерны для ОСРВ.
Процесс, который может исполняться, как только ему будет предоставлен процес-
сор, находитсявсостоянииготовности. Считается, что такому процессу уже выделе-
ны все необходимые ресурсы за исключением процессора.
Из состояниявыполнения процесс может выйти по одной из следующих причин
[2, 5]:
• процесс завершается, при этом он посредством обращения к супервизору передает
управление операционной системе и сообщает о своем завершении. В результате
этих действий супервизор либо переводит его в список бездействующих процессов,
либо уничтожает. В состояние бездействия процесс может быть переведен принуди-
тельно: по команде пользователя, или путем обращения к супервизору операцион-
ной системы из другой задачи с требованием остановить данный процесс;
• процесс переводится супервизором операционной системы в состояние готовности к
исполнению в связи с появлением более приоритетной задачи или в связи с оконча-
нием выделенного ему кванта времени;
• процесс блокируется (переводится в состояние ожидания) либо вследствие запроса
операции ввода/вывода (которая должна быть выполнена прежде, чем он сможет
продолжить исполнение), либо в силу невозможности предоставить ему ресурс, за-
прошенный в настоящий момент, а также по команде оператора на приостановку за-
дачи или по требованию через супервизор от другой задачи.
При наступлении соответствующего события (завершилась операция ввода/вывода,
освободился затребованный ресурс, в оперативную память загружена необходимая
страница виртуальной памяти и т. д.) процесс деблокируется и переводится в состояние
готовностикисполнению.
Таким образом, движущей силой, меняющей состояния процессов, являются со-
бытия. Одним из основных видов событий являются прерывания, которые будут рас-
смотрены далее.
Для того чтобы операционная система могла управлять процессами, она должна
располагать всей необходимой для этого информацией. С этой целью на каждый про-
цесс заводится специальная информационная структура, называемая дескриптором
процесса (описателем задачи, блоком управления задачей). В общем случае дескриптор
процесса содержит следующую информацию [2]:
• идентификатор процесса (так называемый PID - process identificator);
• тип (или класс) процесса, который определяет для супервизора некоторые правила
предоставления ресурсов;
• приоритет процесса, в соответствии с которым супервизор предоставляет ресурсы. В
рамках одного класса процессов в первую очередь обслуживаются более приоритет-
ные процессы;
• переменную состояния, которая определяет, в каком состоянии находится процесс
(готов к работе, в состоянии выполнения, ожидание устройства ввода/вывода и т.
д.);
• защищенную область памяти (или адрес такой зоны), в которой хранятся текущие
значения регистров процессора, если процесс прерывается, не закончив работы. Эта
информация называется контекстомзадачи;
• информацию о ресурсах, которыми процесс владеет и/или имеет право пользоваться
(указатели на открытые файлы, информация о незавершенных операциях вво-
да/вывода и т. п.);
• место (или его адрес) для организации общения с другими процессами;
• параметры времени запуска (момент времени, когда процесс должен активизиро-
ваться, и периодичность этой процедуры);
• в случае отсутствия системы управления файлами - адрес задачи на диске в ее ис-
ходном состоянии и адрес на диске, куда она выгружается из оперативной памяти,
если ее вытесняет другая.
Дескрипторы задач, как правило, постоянно располагаются в оперативной памяти
с целью ускорить работу супервизора, который организует их в списки (очереди) и ото-
бражает изменение состояния процесса перемещением соответствующего описателя из
одного списка в другой. Для каждого состояния ОС ведет соответствующий список за-
дач, находящихся в этом состоянии. Для состояния ожидания может быть не один спи-
сок, а столько, сколько различных видов ресурсов могут вызывать состояние ожидания.
В некоторых операционных системах количество дескрипторов определяется же-
стко и заранее (на этапе генерации варианта операционной системы или в конфигураци-
онном файле, который используется при загрузке ОС), в других - по мере необходимо-
сти система может выделять участки памяти под новые дескрипторы. Например, в OS/2
максимально возможное количество дескрипторов задач определяется в конфигураци-
онном файле CONFIG.SYS, а в Windows NT оно в явном виде не задается.
В ОСРВ чаще всего количество процессов фиксируется и, следовательно, целесо-
образно заранее определять (на этапе генерации или конфигурирования ОС) количество
дескрипторов. Для использования таких ОС в качестве систем общего назначения обыч-
но количество дескрипторов берется с некоторым запасом, и появление новой задачи
связывается с заполнением этой информационной структуры. Поскольку дескрипторы
процессов постоянно располагаются в оперативной памяти, то их количество не должно
быть очень большим. При необходимости иметь большое количество задач один и тот
же дескриптор может в разное время предоставляться для разных задач, но это сильно
снижает скорость реагирования системы.
Для более эффективной обработки данных в системах реального времени целесо-
образно иметь постоянные задачи, полностью или частично всегда существующие в сис-
теме независимо от того, поступило на них требование или нет [2]. Каждая постоянная
задача обладает некоторой собственной областью оперативной памяти (ОЗУ-
резидентные задачи) независимо от того, выполняется задача в данный момент или нет.
Эта область, в частности, может использоваться для хранения данных, полученных зада-
чей ранее. Данные могут храниться в ней и тогда, когда задача находится в состоянии
ожидания или даже в состоянии бездействия.
Для аппаратной поддержки работы операционных систем с этими информацион-
ными структурами (дескрипторами задач) в процессорах могут быть реализованы соот-
ветствующие механизмы. Так, например, в микропроцессорах Intel 80х86, начиная с по-
коления 80286, имеется специальный регистр TR (task register), указывающий
местонахождение TSS (сегмента состояния задачи), в котором при переключении с зада-
чи на задачу автоматически сохраняется содержимое регистров процессора.
Как ранее было указано процесс - отдельная задача, для которой операционная
системы выделяет необходимые ресурсы, такие как виртуальную память, процессорное
время и т.д. Такая обособленность нужна для того, чтобы защитить один процесс от дру-
гого, поскольку они, совместно используя все ресурсы вычислительной системы, конку-
рируют друг с другом. В общем случае процессы просто никак не связаны между собой
и могут принадлежать даже разным пользователям, разделяющим одну вычислительную
систему.
Однако желательно иметь еще и возможность задействовать внутренний паралле-
лизм, который может быть в самих процессах. Такой внутренний параллелизм встреча-
ется достаточно часто и его использование позволяет ускорить их решение. Например,
некоторые операции, выполняемые приложением, могут требовать для своего исполне-
ния достаточно длительного использования центрального процессора. В этом случае при
интерактивной работе с приложением пользователь вынужден долго ожидать заверше-
ния заказанной операции и не может управлять приложением до тех пор, пока операция
не выполнится до самого конца. Такие ситуации встречаются достаточно часто, напри-
мер, при обработке больших изображений в графических редакторах. Если же про-
граммные модули, исполняющие такие длительные операции, оформлять в виде само-
стоятельных «подпроцессов» (потоков, тредов), которые будут выполняться
параллельно с другими «подпроцессами», то у пользователя появляется возможность
параллельно выполнять несколько операций в рамках одного приложения (процесса).
Операционная система не создает для потоков полноценную виртуальнуюмашину. Эти
задачи неимеютсвоихсобственныхресурсов, они развиваются в том же виртуальном
адресном пространстве, могут пользоваться теми же файлами, виртуальными устройст-
вами и иными ресурсами, что и данный процесс. Единственное, что им необходимо
иметь в самостоятельном пользовании - это процессорныйресурс. В однопроцессорной
системе потоки разделяют между собой процессорное время так же, как это делают
обычные процессы, а в мультипроцессорной системе могут выполняться одновременно,
если не встречают конкуренции из-за обращения к иным ресурсам.
Главное, что обеспечивает многопоточность - это возможность параллельно вы-
полнять несколько видов операций в одной прикладной программе. Особенно эффек-
тивно можно использовать многопоточность для выполнения распределенных приложе-
ний; например, многопоточный сервер может параллельно выполнять запросы сразу
нескольких клиентов. В операционной системе OS/2 одной из первых среди ОС, исполь-
зуемых на ПК, была введена многопоточность. В середине девяностых годов для этой
ОС было создано очень большое количество приложений, в которых использование ме-
ханизмов многопоточной обработки приводило к существенному увеличению скорости
выполнения вычислений.
Каждый процесс всегда состоит по крайней мере из одного потока, и только если
имеется внутренний параллелизм, программист может разделить один поток на несколь-
ко параллельных. Потоки выполняются строго последовательно и имеют свой собствен-
ный программный счетчик и стек. Потоки, как и процессы, могут порождать потоки-
потомки. Подобно традиционным процессам (то есть процессам, состоящим из одного
потока), каждый поток может находится в одномизактивныхсостояний. Покаодин
потокзаблокирован (илипростонаходитсявочередиготовыхкисполнениюзадач),
другойпотоктогожепроцессаможетвыполняться. Потоки разделяют процессор-
ное время по тем же принципам, как это делают обычные процессы, т.е. в соответствии с
механизмами, заложенными в различных дисциплинах диспетчеризации.
2.1.2. Планирование и диспетчеризация
Операционная система выполняет следующие основные функции, связанные с
управлением процессами и потоками (задачами) [2]:
• создание и удаление;
• планирование процессов и диспетчеризация;
• синхронизация задач, обеспечение их средствами коммуникации.
Система управления задачами обеспечивает прохождение их через компьютер. В
зависимости от состояния процесса ему должен быть предоставлен тот или иной ресурс.
Например, новый процесс необходимо разместить в основной памяти - следовательно,
ему необходимо выделить часть адресного пространства. Новый порожденный поток
текущего процесса необходимо включить в общий список задач, конкурирующих между
собой за ресурсы центрального процессора.
Создание и удаление задач осуществляется по соответствующим запросам от поль-
зователей или от самих задач. Задача может породить новую задачу. При этом между
процессами появляются «родственные» отношения. Порождающая задача называется
предком, родителем, а порожденная - потомком или дочернейзадачей. Родитель мо-
жет приостановить или удалить свою дочернююзадачу, тогда как потомок не может
управлять предком.
Основным подходом к организации того или иного метода управления процессами,
обеспечивающего эффективную загрузку ресурсов или выполнение каких-либо иных
целей, является организацияочередей процессов и ресурсов. Очевидно, что на распре-
деление ресурсов влияют конкретные потребности тех задач, которые должны выпол-
няться параллельно, т.е можно столкнуться с ситуациями, когда невозможно эффектив-
но распределять ресурсы с тем, чтобы они не простаивали. Например, всем
выполняющимся процессам требуется некоторое устройство с последовательным досту-
пом. Но поскольку оно не может распределяться между параллельно выполняющимися
процессами, то процессы вынуждены будут очень долго ждать своей очереди. Таким об-
разом, недоступность одного ресурса может привести к тому, что длительное время не
будут использоваться и многие другие ресурсы.
Если же запустить задачи, которые не будут конкурировать между собой за нераз-
деляемые ресурсы при параллельном выполнении, то процессы смогут выполниться бы-
стрее, при этом имеющиеся в системе ресурсы будут использоваться более эффективно.
Таким образом, актуальной является задача подбора такого множества процессов, что
бы при выполнении они как можно реже конфликтовали из-за имеющихся в системе ре-
сурсов. Такая задача называется планированием вычислительных процессов [2].
Задача планирования процессов возникла очень давно - в первых пакетных ОС при
планировании пакетов задач, которые должны были выполняться на компьютере и оп-
тимально использовать его ресурсы. В настоящее время актуальность этой задачи не так
велика. На первый план уже очень давно вышли задачи динамического (или краткосроч-
ного) планирования, то есть текущего наиболее эффективного распределения ресурсов,
возникающего практически при каждом событии. Задачи динамического планирования
стали называть диспетчеризацией [2].
Очевидно, что планирование осуществляется гораздо реже, чем задача текущего
распределения ресурсов между уже выполняющимися процессами и потоками. Первая
операция выполняется раз в несколько минут, вторая может запускаться каждые 30 или
100 мс.
При рассмотрении стратегийпланирования, как правило, идет речь о кратко-
срочном планировании, то есть о диспетчеризации. Долгосрочное планирование, как
было отмечено ранее, заключается в подборе таких вычислительных процессов, которые
бы меньше всего конкурировали между собой за ресурсы вычислительной системы.
Стратегияпланирования определяет, какие процессы планируются на выполне-
ние для того, чтобы достичь поставленной цели. Известно большое количество различ-
ных стратегий выбора процесса, которому необходимо предоставить центральный про-
цессор. Среди них, прежде всего, можно назвать следующие стратегии [2]:
• по возможности заканчивать вычислительные процессы в том же самом порядке, в
котором они были начаты;
• отдавать предпочтение более коротким процессам;
• предоставлять всем процессам одинаковые услуги, в том числе и одинаковое время
ожидания.
Когда говорят о диспетчеризации, то всегда в явном или неявном виде имеют в
виду понятие потока. Если ОС не поддерживает механизм потоков, то можно использо-
вать понятие процесса. Известно большое количество правил (дисциплин диспетчериза-
ции), в соответствии с которыми формируется очередь готовых к выполнению задач.
Различают два больших класса дисциплин обслуживания - бесприоритетные и
приоритетные. При бесприоритетном обслуживании выбор задачи производится в
некотором заранее установленном порядке без учета их относительной важности и вре-
мени обслуживания. При реализации приоритетных дисциплин обслуживания отдель-
ным задачам предоставляется преимущественное право попасть в состояние исполне-
ния. Перечень дисциплин обслуживания и их классификация приведены на рис.2.2.
Диспетчеризация с динамическимиприоритетами требует дополнительных рас-
ходов на вычисление значений приоритетов исполняющихся задач, поэтому во многих
ОСРВ используются методы диспетчеризации на основе статических (постоянных) при-
оритетов. При этом следует отметить, что динамические приоритеты позволяют реали-
зовать гарантии обслуживания задач. Рассмотрим кратко некоторые наиболее часто ис-
пользуемые дисциплины диспетчеризации [2].
Рис.2.2. Дисциплины диспетчеризации
Самой простой в реализации является дисциплина FCFS (first come - first served),
согласно которой задачи обслуживаются «в порядке очереди», то есть в порядке их по-
явления. Те задачи, которые были заблокированы в процессе работы (попали в какое-
либо из состояний ожидания, например, из-за операций ввода/вывода), после перехода в
состояние готовности ставятся в эту очередь готовности перед теми задачами, которые
еще не выполнялись. Другими словами, образуются две очереди (рис.2.3): одна очередь
образуется из новых задач, а вторая очередь - из ранее выполнявшихся, но попавших в
состояние ожидание. Такой подход позволяет реализовать стратегию обслуживания «по
возможности заканчивать вычисления в порядке их появления». Эта дисциплина обслу-
живания не требует внешнего вмешательства в ход вычислений, при ней не происходит
перераспределение процессорного времени.
Рис.2.3. Дисциплина диспетчеризации FCFS
К достоинствам этой дисциплины, прежде всего, можно отнести простоту реали-
зации и малые расходы системных ресурсов на формирование очереди задач.
Однако эта дисциплина приводит к тому, что приувеличениизагрузкивычисли-
тельнойсистемырастетисреднеевремяожиданияобслуживания, причем корот-
кие задания (требующие небольших затрат машинного времени) вынуждены ожидать
столько же, сколько и трудоемкие задания. Избежать этого недостатка позволяют дис-
циплины SJN и SRT.
Дисциплинаобслуживания SJN (shortest job next, что означает: следующим будет
выполняться кратчайшее задание) требует, чтобы для каждого задания была известна
оценка в потребностях машинного времени. Необходимость сообщать ОС характеристи-
ки задач, в которых описывались бы потребности в ресурсах вычислительной системы,
привела к тому, что были разработаны соответствующие языковые средства. Язык JCL
(job control language, язык управления заданиями) был одним из наиболее известных.
Пользователи вынуждены были указывать предполагаемое время выполнения, и для то-
го, чтобы они не злоупотребляли возможностью указать заведомо меньшее время вы-
полнения (с целью получить результаты раньше других), ввели подсчет реальных по-
требностей. Диспетчер задач сравнивал заказанное время и время выполнения и в случае
превышения указанной оценки в данном ресурсе ставил данное задание не в начало, а в
конец очереди. Еще в некоторых ОС в таких случаях использовалась система штрафов,
при которой в случае превышения заказанного машинного времени оплата вычисли-
тельных ресурсов осуществлялась уже по другим расценкам.
Дисциплинаобслуживания SJN предполагает, что имеется только одна очередь
заданий, готовых к выполнению. И задания,которыевпроцессесвоегоисполнения
быливременнозаблокированы (например, ожидали завершения операций вво-
да/вывода), вновь попадают в конец очереди готовых к выполнению наравне с вновь по-
ступающими. Это приводило к тому, что задания, которым требуется очень немного
времени для своего завершения, вынуждены ожидать процессор наравне с длительными
работами, что не всегда хорошо.
Для устранения этого недостатка и была предложена дисциплина SRT (shortest re-
maining time, следующее задание требует меньше всего времени для своего завершения).
Все три вышеуказанные дисциплины обслуживания могут использоваться для па-
кетных режимов обработки, когда пользователь не вынужден ожидать реакции системы,
а просто сдает свое задание и через несколько часов получает свои результаты вычисле-
ний. Для интерактивных вычислений желательно прежде всего обеспечить приемлемое
время реакции системы и равенство в обслуживании, если система является мультитер-
минальной. Если же это однопользовательская система, но с возможностью мультипро-
граммной обработки, то желательно, чтобы те программы, с которыми производится не-
посредственная работа, имели лучшее время реакции, нежели фоновые задания. При
этом желательно, чтобы некоторые приложения, выполняясь без непосредственного
участия пользователя (например, программа получения электронной почты, использую-
щая модем и коммутируемые линии для передачи данных), гарантированно получали бы
необходимую часть процессорного времени. Для решения подобных проблем использу-
ется дисциплина обслуживания, называемая RR (round robin, круговая, карусельная), и
приоритетные методы обслуживания.
Дисциплинаобслуживания RR предполагает, что каждая задача получает процес-
сорное время порциями (говорят: квантамивремени, q). После окончания кванта вре-
мени q задача снимается с процессора и он передается следующей задаче. Снятая задача
ставится в конец очереди задач, готовых к выполнению. Эта дисциплина обслуживания
иллюстрируется рис.2.4. Для оптимальной работы системы необходимо правильно вы-
брать закон, по которому кванты времени выделяются задачам.
Рис.2.4. Карусельная (round robin) дисциплина диспетчеризации
Величина кванта времени q выбирается как компромисс между приемлемым вре-
менем реакции системы на запросы пользователей (с тем, чтобы их простейшие запросы
не вызывали длительного ожидания) и накладными расходами на частую смену контек-
ста задач. Очевидно, что при прерываниях ОС вынуждена сохранить достаточно боль-
шой объем информации о текущем (прерываемом) процессе, поставить дескриптор сня-
той задачи в очередь, загрузить контекст задачи, которая теперь будет выполняться.
Если величина q велика, то при увеличении очереди готовых к выполнению задач реак-
ция системы станет плохой. Если же величина мала, то относительная доля накладных
расходов на переключения между исполняющимися задачами станет большой и это
ухудшит производительность системы. В некоторых ОС есть возможность указывать в
явном виде величину q либо диапазон ее возможных значений.
Дисциплина диспетчеризации RR - это одна из самых распространенных дисцип-
лин. Однако бывают ситуации, когда ОС не поддерживает в явном виде дисциплину ка-
русельной диспетчеризации. Например, в некоторых ОС реального времени использует-
ся диспетчер задач, работающий по принципам абсолютных приоритетов (процессор
предоставляется задаче с максимальным приоритетом, а при равенстве приоритетов он
действует по принципу очередности). Другими словами, снять задачу с выполнения мо-
жет только появление задачи с более высоким приоритетом. Поэтому если нужно орга-
низовать обслуживание задач таким образом, чтобы все они получали процессорное
время равномерно и равноправно, то системный оператор может сам организовать такую
дисциплину. Для этого достаточно всем пользовательским задачам присвоить одинако-
вые приоритеты и создать одну высокоприоритетную задачу, которая не должна ничего
делать, но которая, тем не менее, будет по таймеру через указанные интервалы времени
планироваться на выполнение. Эта задача снимет с выполнения текущее приложение,
оно будет поставлено в конец очереди, и поскольку этой высокоприоритетной задаче на
самом деле ничего делать не надо, то она тут же освободит процессор и из очереди го-
товности будет взята следующая задача.
Рассмотренные дисциплины диспетчеризации процессов могут быть разбиты на
два класса - вытесняющие (preemptive) и невытесняющие (non preemptive) [5]. В
большинстве современных ОС для мощных вычислительных систем, а также и в ОС для
ПК, ориентированных на высокопроизводительное выполнение приложений (Windows
NT, OS/2, Linux), реализована вытесняющаямногозадачность.
Диспетчеризация без перераспределения процессорного времени называется не
вытесняющаямногозадачность (non-preemptive multitasking). Это такой способ дис-
петчеризации процессов, при котором активный процесс выполняется до тех пор, пока
он сам, что называется «по собственной инициативе», не отдаст управление диспетчеру
задач для выбора из очереди другого, готового к выполнению процесса или потока.
Дисциплины обслуживания FCFS, SJN, SRT относятся к невытесняющим.
Диспетчеризация с перераспределением процессорного времени между задачами
называется вытесняющаямногозадачность (preemptive multitasking). Это такой спо-
соб, при котором решение о переключении процессора с выполнения одного процесса на
выполнение другого процесса принимается диспетчером задач, а не самой активной за-
дачей. При вытесняющей многозадачности механизм диспетчеризации задач целиком
сосредоточен в операционной системе, и программист может писать свое приложение,
не заботясь о том, как оно будет выполняться параллельно с другими задачами. При
этом операционная система выполняет следующие функции: определяет момент снятия
с выполнения текущей задачи, сохраняет ее контекст в дескрипторе задачи, выбирает из
очереди готовых задач следующую и запускает ее на выполнение, предварительно за-
грузив ее контекст. Дисциплина RR и многие другие, построенные на ее основе, отно-
сятся к вытесняющим.
Одна из проблем, которая возникает при выборе подходящей дисциплины обслу-
живания, - это гарантия обслуживания. Дело в том, что при некоторых дисциплинах, на-
пример при использовании дисциплины абсолютных приоритетов, низкоприоритетные
процессы оказываются обделенными многими ресурсами и, прежде всего, процессор-
ным временем. Возникает реальная дискриминация низкоприоритетных задач, и ряд та-
ких процессов, имеющих к тому же большие потребности в ресурсах, могут очень дли-
тельное время откладываться или, в конце концов, вообще могут быть не выполнены.
Поэтому вопрос гарантии обслуживания является очень актуальным. Существуют раз-
личные дисциплиныдиспетчеризации, учитывающие жесткие временные ограничения,
но не существует дисциплин, которые могли бы предоставить больше процессорного
времени, чем может быть в принципе выделено.
Планирование с учетом жестких временных ограничений легко реализовать, орга-
низуя очередь готовых к выполнению процессов в порядке возрастания их временных
ограничений. Основным недостатком такого простого упорядочения является то, что
процесс (за счет других процессов) может быть обслужен быстрее, чем это ему реально
необходимо. Для того чтобы избежать этого, проще всего процессорное время выделять
все-таки квантами. С учетом сказанного выше гарантироватьобслуживаниеможно
следующимитремяспособами [2]:
• выделять минимальную долю процессорного времени некоторому классу процессов,
если по крайней мере один из них готов к исполнению. Например, можно отводить
20 % от каждых 10 мс процессам реального времени, 40 % от каждых 2 сек - инте-
рактивным процессам и 10 % от каждых 5 мин - фоновым процессам;
• выделять минимальную долю процессорного времени некоторому конкретному
процессу, если он готов к выполнению;
• выделять столько процессорного времени некоторому процессу, чтобы он мог вы-
полнить свои вычисления к сроку.
Для сравнения алгоритмов диспетчеризации обычно используются следующие
критерии [2]:
• Загрузка центрального процессора (CPU utilization). В большинстве персональных
систем средняя загрузка процессора не превышает 2-3%, доходя в моменты выпол-
нения сложных вычислений и до 100 %. В реальных системах, где компьютеры вы-
полняют очень много работы, например, в серверах, загрузка процессора колеблется
в пределах 15-40 % для легко загруженного процессора и до 90-100 % - для сильно
загруженного процессора.
• Пропускная способность (CPU throughput). Пропускная способность процессора
может измеряться количеством процессов, которые выполняются в единицу време-
ни.
• Время оборота (turnaround time). Для некоторых процессов важным критерием явля-
ется полное время выполнения, то есть интервал от момента появления процесса во
входной очереди до момента его завершения. Это время названо временем оборота и
включает время ожидания во входной очереди, время ожидания в очереди готовых
процессов, время ожидания в очередях к оборудованию, время выполнения в про-
цессоре и время ввода/вывода.
• Время ожидания (waiting time). Под временем ожидания понимается суммарное
время нахождения процесса в очереди готовых процессов.
• Время отклика (response time). Для интерактивных программ важным показателем
является время отклика или время, прошедшее от момента попадания процесса во
входную очередь до момента первого обращения к терминалу. Очевидно, что про-
стейшая стратегия краткосрочного планировщика должна быть направлена на мак-
симизацию средних значений загруженности и пропускной способности, времени
ожидания и времени отклика.
Правильное планирование