Симметричное и асимметричное мультипроцессирование

 

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

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

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

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

Асимметричное мультипроцессирование – наиболее простой способ организации вычислительного процесса в системах с несколькими процессора­ми. Этот способ часто называют также “ведущий-ведомый”.

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

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

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

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

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

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

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

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

ПЛАНИРОВАНИЕ ПРОЦЕССОВ И ПОТОКОВ

 

3.1. Понятия “процесс” и “поток”

 

Выше мы уже рассмотрели определения и подробное описание отличий между понятиями “процесс” “поток”. Однако для изучения вопроса планирования процессов и потоков следует обратить внимание на следующие моменты.

Для того чтобы управлять тем или иным процессом, он сначала должен быть создан. Создать процесс – это прежде всего означает создать описатель процесса, в каче­стве которого выступает одна или несколько информационных структур, содержащих все сведения о процессе, необходимые операционной системе для управ­ления им. В число таких сведений могут входить, например, идентификатор про­цесса, данные о расположении в памяти исполняемого модуля, степень привиле­гированности процесса (приоритет и права доступа) и т. п. Примерами описателей процесса являются блок управления задачей (ТСВ – Task Control Block) в OS/360, управляющий блик процесса (РСВ – Process Control Block) в OS/2, де­скриптор процесса в UNIX, объект-процесс (object-process) в Windows NT. После создания процесса в системе появляется новый претендент на вычислительные ресурсы, потребности которого ОС обязана учитывать при решении задач распределения ресурсов между процессами.

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

В многопоточной системе при создании процесса ОС создает для каждого про­цесса как минимум один поток выполнения. При создании потока так же, как и при создании процесса, операционная система генерирует специальную инфор­мационную структуру – описатель потока, который содержит идентификатор потока, данные о правах доступа и приоритете, о состоянии потока и другую ин­формацию. В исходном состоянии поток (или процесс, если речь идет о системе, в которой понятие “поток” не определяется) находится в приостановленном со­стоянии. Момент выборки потока на выполнение осуществляется в соответст­вии с принятым в данной системе правилом предоставления процессорного вре­мени и с учетом всех существующих в данный момент потоков и процессов.

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

Рассмотрим в качестве примера создание процессов в популярной версии опера­ционной системы UNIX System V Release 4. В этой системе потоки не поддержи­ваются, в качестве единицы управления и единицы потребления ресурсов высту­пает только процесс.

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

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

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

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

После выполнения системного вызова fork оба процесса продолжают выполне­ние с одной и той же точки. Чтобы процесс мог опознать, является он родитель­ским процессом или процессом-потомком, системный вызов fork возвращает в качестве своего значения в породивший процесс идентификатор порожденного процесса, а в порожденный процесс – NULL. Идентификатор потомка может быть присвоен переменной, входящей в контекст родительского процесса. Так как контекст процесса наследуется его потомками, то потомки могут узнать идентификаторы своих “старших братьев”, таким обра­зом сумма знаний наследуется при порождении и может быть распространена между родственными процессами. На независимости идентификатора процесса от выполняемой процессом программы построен механизм, позволяющий про­цессу перейти к выполнению другой программы с помощью системного вызова ехес.

Таким образом, в UNIX порождение нового процесса происходит в два этапа – сначала создается копия процесса-родителя, затем у нового процесса произво­дится замена кодового сегмента на заданный.

Вновь созданному процессу операционная система присваивает целочисленный идентификатор, уникальный на весь период функционирования системы.

 

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

 

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

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

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

- выбор для выполнения потока из очереди готовых потоков.

Существует множество различных алгоритмов планирования потоков, по-своему решающих каждую из задач. Алгоритмы планирования мо­гут преследовать различные цели и обеспечивать разное качество мультипро­граммирования. Например, в одном случае выбирается такой алгоритм планирования, при котором гарантируется, что ни один поток/процесс не будет занимать процессор дольше определенного времени, в другом случае целью является мак­симально быстрое выполнение “коротких” задач, а в третьем случае – преиму­щественное право занять процессор получают потоки интерактивных приложе­ний. Именно особенности реализации планирования потоков в наибольшей степени определяют специфику операционной системы, в частности, является ли она сис­темой пакетной обработки, системой разделения времени или системой реально­го времени.

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

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

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

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

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

- сохранение контекста текущего потока, который требуется сменить;

- загрузка контекста нового потока, выбранного в результате планирования;

- запуск нового потока на выполнение.

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

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

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

ОС выполняет планирование потоков, принимая во внимание их состояние. В мультипрограммной системе поток может находиться в одном из трех основ­ных состояний:

- выполнение – активное состояние потока, во время которого поток обладает всеми необходимыми ресурсами и непосредственно выполняется процессором;

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

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

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

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

В однопроцессорной системе, как уже было замечено ранее, в состоянии выполнения может находиться не бо­лее одного потока, а в каждом из состояний ожидания и готовности – несколько потоков. Эти потоки образуют очереди соответственно ожидающих и готовых потоков. Очереди потоков организуются путем объединения в списки описателей отдельных потоков. Таким образом, каждый описатель потока, кроме всего прочего, содержит по крайней мере один указатель на другой описатель, соседствующий с ним в очереди. Такая организация очередей позволяет легко их переупорядочивать, включать и исключать потоки, переводить потоки из одного состояния в другое. Если предположить, что на рис.4 показана очередь готовых потоков, то заплани­рованный порядок выполнения выглядит так: А, В, Е, D, С.

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

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

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

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

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

Почти во всех современных операционных системах, ориентированных на высо­копроизводительное выполнение приложений (UNIX, Windows NT/2000, OS/2, VAX/VMS), реализованы вытесняющие алгоритмы планирования потоков (про­цессов). В последнее время дошла очередь и до ОС класса настольных систем, например OS/2 Warp и Windows 95/98.

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

- ThreadSwitch – поток, вызвавший эту функцию, считает себя готовым к немед­ленному выполнению, но отдает управление для того, чтобы могли выпол­няться и другие потоки;

- ThreadSwitchWithDelay – функция аналогична предыдущей, но поток считает, что будет готов к выполнению только через определенное количество пере­ключений с потока на поток;

- Delay – функция аналогична предыдущей, но задержка дается в миллисекундах;

- ThreadSwitchLowPiority – функция отдачи управления, отличается от ThreadSwitch тем, что поток просит поместить его в очередь готовых к выполнению, но низкоприоритетных потоков.

Планировщик NetWare использует несколько очередей готовых потоков (рис.5). Только что созданный поток попадает в конец очереди RunList, которая содержит готовые к выполнению потоки. После отказа от процессора поток попадает в ту или иную очередь в зависимости от того, какой из системных вызовов был ис­пользован при передаче управления. Поток поступает в конец очереди RunList при вызове ThreadSwitch, в конец очереди DelayedworkToDoList при вызовах Thread­SwitchWithDe1ay или Delay или же в конец очереди LowPrioriyRunList при вызове ThreadSwitchLowPriority.

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

Потоки, находящиеся в очереди DelayedworkToDoList, после завершения условия ожидания перемещаются в конец очереди RunList.

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

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

Описанный невытесняющий механизм организации многопоточной работы в ОС NetWaку 3.х и NetWale 4.х потенциально очень производителен, так как отличается небольшими накладными расходами ОС на диспетчеризацию потоков за счет простых алгоритмов планирования и иерархии контекстов. Но для дости­жения высокой производительности и к разработчикам приложении для ОС Net­Ware предъявляются высокие требования, так как распределение процессорного времени между различными приложениями зависит в конечном счете от искус­ства программиста.

В основе многих вытесняющих алгоритмов планирования лежит концепция квантования. В соответствии с этой концепцией каждому потоку поочередно для выполнения предоставляется ограниченный непрерывный период процессорно­го времени – квант. Смена активного потока происходит, если:

- поток завершился и покинул систему,

- произошла ошибка,

- поток перешел в состояние ожидания,

- исчерпан квант процессорного времени, отведенный данному потоку.

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

Кванты, выделяемые потокам, могут быть одинаковыми для всех потоков или различными. Рассмотрим, например, случай, когда всем потокам предоставляют­ся кванты одинаковой длины q (рис.7). Если в системе имеется n потоков, то время, которое поток проводит в ожидании следующего кванта, можно грубо оце­нить как q (n– 1). Чем больше потоков в системе, тем больше время ожидания, тем меньше возможности вести одновременную интерактивную работу нескольким пользователям. Но если величина кванта выбрана очень небольшой, то значение произведения q (n– 1) все равно будет достаточно мало для того, чтобы пользова­тель не ощущал дискомфорта от присутствия в системе других пользователей. Типичное значение кванта в системах разделения времени составляет десятки миллисекунд.

Если квант короткий, то суммарное время, которое проводит поток в ожидании процессора, прямо пропорционально времени, требуемому для его выполнения (т.е. времени, которое потребовалось бы для выполнения этого потока при монопольном использовании вычислительной системы). Действительно, поскольку время ожидания между двумя циклами выполнения равно q (n– 1), а количество циклов B / q, где В – требуемое время выполнения, то W = B (n– 1). За­метим, что эти соотношения представляют собой весьма грубые оценки, осно­ванные на предположении, что В значительно превышает q. При этом не учиты­вается, что потоки могут использовать кванты неполностью, что часть времени они могут тратить на ввод-вывод, что количество потоков в системе может ди­намически меняться и т.д.

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

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

Потоки получают для выполнения квант времени, но некоторые из них ис­пользуют его не полностью, например из-за необходимости выполнить ввод или вывод данных. В результате возникает ситуация, кода потоки с интенсивными обращениями к вводу-выводу используют только небольшую часть выделенного им процессорного времени. Алгоритм планирования может ис­править эту “несправедливость”. В качестве компенсации за неиспользован­ные полностью кванты потоки получают привилегии при последующем об­служивании. Для этого планировщик создает две очереди готовых потоков (рис. 8). Очередь 1 образована потоками, которые пришли в состояние го­товности в результате исчерпания кванты времени, а очередь 2 – потоками, у которых завершилась операция ввода-вывода. При выборе потока для выполнения прежде всего просматривается вторая очередь, и только если она пуста, квант выделяется потоку из первой очереди.

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

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

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

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

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

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

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

В качестве примера рассмотрим схему назначения приоритетов потокам, приня­тую в операционной системе Windows NT (рис.9). В системе определено 32 уровня приоритетов и два класса потоков – потоки реального времени и по­токи с переменными приоритетами. Диапазон от 1 до 15 включительно отведен для потоков с переменными приоритетами, а от 16 до 31 – для более критичных ко времени потоков реального времени (приоритет 0 зарезервирован для систем­ных целей).

При создании процесса он в зависимости от класса получает по умолчанию ба­зовый приоритет в верхней или нижней части диапазона. Базовый приоритет процесса в дальнейшем может быть повышен или понижен операционной систе­мой. Первоначально поток получает значение базового приоритета из диапазона базового приоритета процесса, в котором он был создан. Пусть, например, значе­ние базового приоритета некоторого процесса равно К. Тогда все потоки данного процесса получат базовые приоритеты из диапазона [К–2, К+2]. Отсюда видно, что, изменяя базовый приоритет процесса, ОС может влиять на базовые приори­теты его потоков.

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

Существуют две разновидности приоритетного планирования: обслуживание с относительными приоритетами и обслуживание с абсолютными приоритетами.

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

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

В системах, в которых планирование осуществляется на основе относительных приоритетов, с одной стороны, минимизируются затраты на переключения процессора с одной ра­боты на другую. С другой стороны, здесь могут возникать ситуации, когда одна задача занимает процессор долгое время. Ясно, что для систем разделения вре­мени и реального времени такая дисциплина обслуживания не подходит: интер­активное приложение может ждать своей очереди часами, пока вычислительной задаче не потребуется ввод-вывод. А вот в системах пакетной обработки (в том числе известной ОС OS/360) относительные приоритеты используются широко.

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

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

Рассмотрим более подробно алгоритм планирования в операционной системе UNIX System V Release 4. В этой ОС понятие “поток” отсутствует, и планирова­ние осуществляется на уровне процессов. В системе UNIX System V Release 4 реализована вытесняющая многозадачность, основанная на использовании при­оритетов и квантования.

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

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

Процессы разделения времени были до появления UNIX System V Release 4 един­ственным классом процессов, и по умолчанию UNIX System V Release 4 назнача­ет новому процессу именно этот класс. Состав класса процессов разделения вре­мени наиболее неопределенный и часто меняющийся в отличие от системных процессов и процессов реального времени. Для справедливого распределения времени процессора между процессами в этом классе используется стратегия ди­намических приоритетов. Величина приоритета, назначаемого процессам разде­ления времени, вычисляется пропорционально значениям двух составляющих: пользовательской части и системной части. Пользовательская часть приоритета может быть изменена администратором и владельцем процесса, но в последнем случае только в сторону его снижения.

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

Другой пример относится к операционной системе OS/2. Планирование здесь основано на использовании квантования и абсолютных динамических приори­тетов. На множестве потоков определены приоритетные классы – критический (time critical), серверный (server), стандартный (regular) и остаточный (idle), в каждом из которых имеется 32 приоритетных уровня. Потоки критического класса имеют наивысший приоритет. В этот класс могут быть отнесены, напри­мер, системные потоки, выполняющие задачи управления сетью. Следующий по приоритетности класс предназначен, как это следует из его названия, для потоков, обслуживающих серверные приложения. К стандартному классу могут быть отнесены потоки обычных приложений. Потоки, входящие в остаточный класс, имеют самый низкий приоритет. К этому классу относится, например, по­ток, выводящий на экран заставку, когда в системе не выполняется никакой ра­боты.

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

Приоритеты могут изменяться планировщиком в следующих случаях:

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

- если поток ушел на выполнение операции ввода-вывода, то после ее заверше­ния он получит наивысшее значение приоритета своего класса;

- приоритет потока автоматически повышается, когда он поступает на выпол­нение.

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

Благодаря такому алгоритму планирования в OS/2 ни один поток не будет “за­быт” системой и получит достаточно процессорного времени.

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

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

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

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

При рассмотрении в качестве примеров подсистем планирования потоков/процессов в операционных системах Windows NT, OS/2 и UNIX System V Release 4 было отмечено, что во всех этих системах имеется приоритетный класс реального времени. Для пото­ков/процессов, относящихся к этому классу, каждая из вышеназванных систем не гаран­тирует выполнение заданных временных ограничений, а лишь обеспечивает предпочтение в скорости обслуживания. Следовательно, эти ОС могут быть основой для построения мягких систем реального времени, но непригодны для жестких систем реального времени.

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

Предположим, что имеется периодический набор задач { Тi } с периодами р i, пре­дельными сроками d iи требованиями ко времени выполнения с i. Для проверки возможности существования расписания достаточно проанализировать расписа­ние на периоде времени, равном по крайней мере наименьшему общему множи­телю периодов этих задач. Необходимым критерием существования расписания для набора периодических задач является следующее достаточно очевидное ут­верждение: сумма коэффициентов использования i = c i/ p iдолжна быть меньше или равна k, где k – количество доступных процессоров:

.

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

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

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

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

- введение ограничивающих предположений о поведении набора задач.

При таком подходе планирование приближается к статическому.

Возвращаясь к планированию независимых задач, рассмотрим классический ал­горитм для жестких систем реального времени с одним процессором, разрабо­танный в 1973 году Лью (Liu) и Лейландом (Layland). Алгоритм является дина­мическим, т.е. он использует вытесняющую многозадачность и основан на относительных статических (неизменяемых в течение жизни задачи) приори­тетах. Алгоритм основан на следующих предположениях:

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

- все задачи независимы. Между любой парой задач не существует никаких ог­раничений на предшествование или на взаимное исключение;

- срок выполнения каждой задачи равен ее периоду p i;

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

- время переключения контекста можно игнорировать;

- максимальный суммарный коэффициент загрузки процессора при су­ществовании n задач не превосходит n (21/n–1). Эта величина при стремле­нии n к бесконечности приблизительно равна ln2, т.е. 0,7.

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

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

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

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

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

- активная задача выполнила системный вызов, связанный с запросом на ввод-вывод или на доступ к ресурсу, который в настоящий момент занят (напри­мер, файл данных). Планировщик переводит задачу в состояние ожидания и выполняет перепланирование;

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

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

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

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

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

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

Следующая передача управления планировщику была осуществлена в результате выполнения потоком 3 системного запроса на ввод-вывод (событие I/O). Плани­ровщик перевел этот поток в состояние ожидания, а затем переключил процес­сор на поток 2. Поток 2 полностью использовал свой квант, произошло прерыва­ние от таймера, и планировщик активизировал поток 1.

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

В следующем цикле работы планировщик активизировал поток 4, а затем, после истечения кванта и сигнала от таймера, управление получил поток 2. Этот поток не успел использовать свой квант, так как был снят с выполнения в результате возникшей ошибки (событие ER).

Далее планировщик предоставлял процессорное время потокам 1, 4 и снова 1. Во время выполнения потока 1 произошло прерывание S от вне