Стальнов А.Ф., Фомин А.И. Операционные системы. Учебное пособие

Подождите немного. Документ загружается.

121

Средства контроля процессора

Системный таймер

Магнитные диски

Сетевое оборудование

Терминалы

Программные прерывания

Внешние

устройства

Высокий

приоритет

Низкий

приоритет

Рис. 3.3. Распределение прерываний по уровням приоритета

Наличие сигнала прерывания не обязательно должно вызывать преры-

вание исполняющейся программы. Процессор может обладать средствами

защиты от прерываний: отключение системы прерываний, маскирование

(запрет) отдельных сигналов прерывания. Программное управление этими

средствами (существуют специальные команды для управления работой

системы прерываний) позволяет операционной системе регулировать об

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

по приходу, откладывать их обработку на некоторое время или полностью

игнорировать. Обычно операция прерывания выполняется только после

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

ния возникают в произвольные моменты времени, то на момент прерыва-

ния может существовать несколько сигналов прерывания, которые могут

быть обработаны только последовательно. Чтобы обработать сигналы

прерывания в разумном порядке им присваиваются приоритеты. Сигнал с

более высоким приоритетом обрабатывается в первую очередь, обработка

остальных сигналов прерывания откладывается.

Программное управление специальными регистрами маски (маскиро-

вание сигналов прерывания) позволяет реализовать различные дисципли-

ны обслуживания:

с относительными приоритетами, то есть обслуживание не прерыва

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

окончания обслуживания данного запроса обслуживается запрос с наи-

высшим приоритетом. Для организации такой дисциплины необходимо в

программе обслуживания данного запроса наложить маски на все осталь-

ные сигналы прерывания или просто отключить систему прерываний;

с абсолютными приоритетами, то есть всегда обслуживается

преры-

вание с наивысшим приоритетом. Для реализации этого режима необхо-

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

низким приоритетом. При этом возможно многоуровневое прерывание, то

122

есть прерывание программ обработки прерываний. Число уровней преры-

вания в этом режиме изменяется и зависит от приоритета запроса;

по принципу стека (по правилу LCFS), то есть запросы с более низким

приоритетом могут прерывать обработку прерывания с более высоким

приоритетом. Для этого необходимо не накладывать маски ни на один

сигнал прерывания и не

выключать систему прерываний.

Следует особо отметить, что для правильной реализации последних

двух дисциплин нужно обеспечить полное маскирование системы преры-

ваний при выполнении шагов 1-4 и 6-7. Это необходимо для того, чтобы

не потерять запрос и правильно его обслужить. Многоуровневое прерыва-

ние должно происходить на этапе собственно обработки прерывания, а не

на этапе

перехода с одного процесса на другой.

Управление ходом выполнения задач со стороны ОС заключается в ор-

ганизации реакций на прерывания, в организации обмена информацией

(данными и программами), предоставлении необходимых ресурсов, в ди-

намике выполнения задачи и в организации сервиса. Причины прерываний

определяет ОС (модуль, который называют супервизором прерываний),

она же

и выполняет действия, необходимые при данном прерывании и в

данной ситуации. Поэтому в состав любой ОС реального времени прежде

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

стояний задач и событий, синхронизации задач, средства распределения

памяти и управления ею, а уже потом средства организации данных (с по-

мощью файловых систем и

т. д.). Следует, однако, заметить, что совре-

менная ОС реального времени должна вносить в аппаратно-программный

комплекс нечто большее, нежели просто обеспечение быстрой реакции на

прерывания.

Итак, при появлении запроса на прерывание система прерываний иден-

тифицирует сигнал и, если прерывания разрешены, управление передается

на соответствующую подпрограмму обработки. В подпрограмме обработ-

ки прерывания имеются две служебные секции (рис. 3.2). Это – первая

секция, в которой осуществляется сохранение контекста прерванной зада-

чи, который не смог быть сохранен на 2-м шаге, и последняя, заключи-

тельная секция, в которой, наоборот, осуществляется восстановление кон-

текста. Для того чтобы система прерываний не среагировала повторно на

сигнал запроса на прерывание

, она обычно автоматически “закрывает”

(отключает) прерывания, поэтому необходимо потом в подпрограмме об-

работки прерываний вновь включать систему прерываний. Установка рас-

смотренных режимов обработки прерываний (с относительными и абсо-

лютными приоритетами, и по правилу LCFS) осуществляется в конце пер-

вой секции подпрограммы обработки. Таким образом, на время вы-

полнения центральной секции (в

случае работы в режимах с абсолютными

приоритетами и по дисциплине LCFS) прерывания разрешены. На время

работы заключительной секции подпрограммы обработки система преры-

ваний должна быть отключена и после восстановления контекста вновь

123

включена. Поскольку эти действия необходимо выполнять практически в

каждой подпрограмме обработки прерываний, во многих операционных

системах первые секции подпрограмм обработки прерываний выделяются

в специальный системный программный модуль, называемый супервизо-

ром прерываний.

Супервизор прерываний прежде всего сохраняет в дескрипторе теку-

щей задачи рабочие регистры процессора, определяющие контекст преры-

ваемого вычислительного процесса. Далее

он определяет ту подпрограм-

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

стоящего (текущего) запроса на прерывание. Наконец, перед тем как пере-

дать управление этой подпрограмме, супервизор прерываний устанавли-

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

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

зору, на этот раз уже

на тот модуль, который занимается дис-

петчеризацией задач. И уже диспетчер задач, в свою очередь, в соответст-

вии с принятым режимом распределения процессорного времени (между

выполняющимися процессами) восстановит контекст той задачи, которой

будет решено выделить процессор. Рассмотренная схема проиллюстриро-

вана на рис. 3.4.

Прерывание

Исполняемая

программа

Отключение прерываний,

сохранение контекста

прерванной программы,

установка режима системы

прерываний (маскирование)

Определение адреса

программного модуля,

обслуживающего запрос

на прерывание, и передача

управления на него

Супервизор прерываний

Выбор готовой к

выполнению задачи

(на основе принятой

дисциплины

обслуживания)

Восстановление контекста

задачи, установка

прежнего режима работы

системы прерываний и

передача управления

этой задаче

Диспетчер задач

Выполнение кода

подпрограммы обработки

прерывания

Эта подпрограмма уже не

заботится о сохранении

контекста прерванного

процесса

Рис. 3.4. Обработка прерывания при участии супервизоров ОС

Из рассмотренной схемы (рис. 3.4) видно, что здесь нет непосредствен-

ного возврата в прерванную ранее программу прямо из самой подпро-

граммы обработки прерывания. Для прямого непосредственного возврата

достаточно адрес возврата сохранить в стеке, что и делает аппаратура

124

процессора. При этом стек легко обеспечивает возможность возврата в

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

ну LCFS (last come – first served).

В конкретных процессорах и в конкретных ОС могут существовать не-

которые отступления от рассмотренной схемы и/или дополнения к ней.

Например, в современных процессорах часто имеются специальные аппа-

ратные возможности для сохранения контекста

прерываемого процесса

непосредственно в его дескрипторе, то есть дескриптор процесса (по

крайней мере, его часть) становится структурой данных, которую под-

держивает аппаратура.

3. Диспетчеризация и синхронизация процессов

При рассмотрении вопросов диспетчеризации и синхронизации про-

цессов мы не будем разделять понятия процесс (process) и поток (thread),

вместо этого используя как бы обобщающий

термин task (задача). В об-

щем случае под задачей или процессом следует понимать практически од-

но и то же. Сейчас же мы будем говорить о разделении ресурса централь-

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

потока.

Операционная система выполняет следующие основные функции, свя-

занные с управлением задачами

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

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

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

Система управления задачами обеспечивает прохождение их через

компьютер. Создание и удаление задач осуществляется по соответствую-

щим запросам от пользователей или от самих задач. Задача может поро-

дить новую задачу. При этом между процессами появляются

“родствен-

ные” отношения.

При создании современных приложений, позволяющих использовать

все возможности операционных систем в плане организации параллель-

ных и распределенных вычислений, одной из важнейших проблем являет-

ся проблема синхронизации взаимодействия параллельных вычислитель-

ных процессов, обмена между ними данными. Существующие методы

синхронизации и обмена сообщениями различаются по таким параметрам,

как удобство

использования при программировании параллельных про-

цессов, стоимость реализации, эффективность функционирования создан-

ных приложений и всей вычислительной системы в целом.

Операционные системы имеют в своем составе различные средства

синхронизации. Знание этих средств и их правильное использование по-

зволяет создавать программы, которые при своей работе осуществляют

125

корректный обмен информацией, а также исключают возможность воз-

никновения тупиковых ситуаций.

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

Основным подходом к организации того или иного метода управления

процессами, обеспечивающего эффективную загрузку ресурсов или вы-

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

сов и ресурсов.

На распределение ресурсов влияют

конкретные потребности тех задач,

которые должны выполняться параллельно. Другими словами, можно

столкнуться с ситуациями, когда невозможно эффективно распределять

ресурсы с тем, чтобы они не простаивали. Таким образом, возникает зада-

ча подбора такого множества процессов, что при выполнении они будут

как можно реже конфликтовать из-за имеющихся в системе ресурсов. Та-

кая задача называется планированием вычислительных процессов.

Задача планирования процессов возникла еще в первых пакетных ОС

при планировании пакетов задач, которые должны были выполняться на

ЭВМ и оптимально использовать ее ресурсы. В настоящее время актуаль-

ность этой задачи не так велика. На первый план уже давно вышли задачи

динамического (или краткосрочного)

планирования, то есть текущего наи-

более эффективного распределения ресурсов, возникающего практически

при каждом событии. Задачи динамического планирования стали называть

диспетчеризацией.

Очевидно, что планирование осуществляется гораздо реже, чем задача

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

сами и потоками. Основное отличие между долгосрочным и краткосроч-

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

краткосрочный пла-

нировщик, например, может запускаться каждые 30 или 100 мс, долго-

срочный – один раз за несколько минут.

Долгосрочный планировщик решает, какой из процессов, находящихся

во входной очереди, должен быть переведен в очередь готовых процессов

в случае освобождения ресурсов памяти. Он выбирает процессы из вход-

ной очереди с целью создания неоднородной мультипрограммной смеси

Это означает, что в очереди готовых к выполнению процессов должны на-

ходиться – в разной пропорции – как процессы, ориентированные на

ввод/вывод, так и процессы, ориентированные на преимущественную ра-

боту с центральным процессором.

Краткосрочный планировщик решает, какая из задач, находящихся в

очереди готовых к выполнению, должна быть передана на исполнение. В

большинстве современных ОС долгосрочный планировщик отсутствует.

126

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

При рассмотрении стратегий планирования, как правило, идет речь о

краткосрочном планировании, то есть о диспетчеризации.

Стратегия планирования определяет, какие процессы мы планируем на

выполнение для того, чтобы достичь поставленной цели. Известно боль-

шое количество различных стратегий выбора процесса, которому необхо-

димо предоставить процессор. Среди них, прежде всего, можно

назвать

следующие стратегии:

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

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

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

3) предоставлять всем пользователям (процессам пользователей) оди-

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

Когда говорят о стратегии обслуживания, всегда имеют в виду

понятие

процесса, а не понятие задачи, поскольку процесс, как мы уже знаем, мо-

жет состоять из нескольких потоков (задач).

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

Известно большое количество правил (дисциплин диспетчеризации), в

соответствии с которыми формируется список (очередь) готовых к выпол-

нению задач. Различают два больших класса дисциплин обслуживания

(рис. 3.5) – бесприоритетные и приоритетные

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

Бесприоритетные Приоритетные

С фиксированным

приоритетом

С динамическим

приоритетом

Линейные Циклические

В порядке

очереди

Случайный выбор

процесса

Циклический

алгоритм

Многоприоритетный

циклический алгоритм

С относительным

приоритетом

Адаптивное

обслуживание

Приоритет зависит от

времени ожидания

С абсолютным

приоритетом

Приоритет зависит от

времени обслуживания

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

127

При бесприоритетном обслуживании выбор задачи производится в не-

котором заранее установленном порядке без учета их относительной важ-

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

обслуживания отдельным задачам предоставляется преимущественное

право попасть в состояние исполнения. При этом приоритет, присвоенный

задаче, может являться величиной постоянной либо может изменяться в

процессе ее решения

Диспетчеризация с динамическими приоритетами требует дополни-

тельных расходов на вычисление значений приоритетов исполняющихся

задач, поэтому во многих ОС реального времени используются методы

диспетчеризации на основе статических (постоянных) приоритетов. Одна-

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

вания задач.

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

мые) дисциплины диспетчеризации.

Самой простой

в реализации является дисциплина FCFS (first come –

first served), согласно которой задачи обслуживаются “в порядке очереди”,

то есть в порядке их появления. Те задачи, которые были заблокированы в

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

из-за операций ввода/вывода), после перехода в состояние готовности ста-

вятся в эту очередь готовности перед теми задачами, которые еще

не вы-

полнялись. Другими словами, образуются две очереди (рис. 3.6): одна оче-

редь образуется из новых задач, а вторая очередь – из ранее выполняв-

шихся, но попавших в состояние ожидание.

Процессор

Блокирование

Выполненные задачи

Очередь задач, вновь готовых к исполнению

Очередь новых задач

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

128

Такой подход позволяет реализовать стратегию обслуживания “по воз-

можности заканчивать вычисления в порядке их появления”. Эта дисцип-

лина обслуживания не требует внешнего вмешательства в ход вычисле-

ний, при ней не происходит перераспределение процессорного времени.

Существующие дисциплины диспетчеризации процессов могут быть раз-

биты на два класса – вытесняющие (preemptive) и не вытесняющие (non-

preemptive). В

первых пакетных ОС часто реализовывали параллельное

выполнение заданий без принудительного перераспределения процессора

между задачами. В большинстве современных ОС для мощных вычисли-

тельных систем, а также и в ОС для ПК, ориентированных на высокопро-

изводительное выполнение приложений (Windows NT, OS/2, Linux), реа-

лизована вытесняющая многозадачность. Можно сказать, что рассмотрен-

ная дисциплина относится к не вытесняющим.

Достоинства

этой дисциплины: простота реализации и малые расходы

системных ресурсов на формирование очереди задач.

Недостатки: при увеличении загрузки вычислительной системы рас-

тет и среднее время ожидания обслуживания, причем короткие задания

(требующие небольших затрат машинного времени) вынуждены ожидать

столько же, сколько и трудоемкие задания. Избежать этого недостатка по-

зволяют дисциплины SJN и SRT.

Дисциплина

обслуживания SJN (shortest job next, что означает: следую-

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

задания была известна оценка в потребностях машинного времени. Дис-

циплина обслуживания SJN предполагает, что имеется только одна оче-

редь заданий, готовых к выполнению. И задания, которые в процессе сво-

его исполнения были временно заблокированы (например, ожидали за-

вершения операций

ввода/вывода), вновь попадают в конец очереди гото-

вых к выполнению наравне с вновь поступающими. Это приводит к тому,

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

шения, вынуждены ожидать процессор наравне с длительными работами,

что не всегда хорошо.

Для устранения этого недостатка и была предложена дисциплина SRT

(shortest remaining time, следующее задание требует меньше всего времени

для своего завершения).

Все эти три дисциплины обслуживания могут использоваться для па-

кетных режимов обработки, когда пользователь не вынужден ожидать ре-

акции системы, а просто сдает свое задание и через несколько часов полу-

чает свои результаты вычислений. Для интерактивных же вычислений же-

лательно прежде

всего обеспечить приемлемое время реакции системы и

равенство в обслуживании, если система является мультитерминальной.

Если же это однопользовательская система, но с возможностью мульти-

программной обработки, то желательно, чтобы те программы, с которыми

пользователь непосредственно работает, имели лучшее время реакции,

нежели фоновые задания. При этом пользователь может пожелать, чтобы

129

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

(например, программа получения электронной почты), тем не менее га-

рантированно получали необходимую им долю процессорного времени.

Для решения подобных проблем используется дисциплина обслуживания,

называемая RR (round robin, круговая, карусельная), и приоритетные ме-

тоды обслуживания.

Дисциплина обслуживания RR

(рис. 3.7) предполагает, что каждая зада-

ча получает процессорное время квантами. После окончания кванта вре-

мени – задача снимается с процессора и он передается следующей задаче.

Снятая задача ставится в конец очереди задач, готовых к выполнению.

Для оптимальной работы системы необходимо правильно выбрать закон,

по которому кванты времени выделяются задачам.

Процессор

Выполненные задачи

Очередь готовых к исполнению задач Новые задачи

Рис. 3.7. Карусельная дисциплина диспетчеризации (round robin)

Величина кванта времени выбирается как компромисс между приемле-

мым временем реакции системы на запросы пользователей (с тем, чтобы

их простейшие запросы не вызывали длительного ожидания) и накладны-

ми расходами на частую смену контекста задач. Очевидно, что при преры-

ваниях ОС вынуждена сохранить достаточно большой объем информации

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

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

дескриптор был первым в очереди готовых к исполнению). Если величина

кванта времени велика, то при увеличении очереди готовых к выполнению

задач реакция системы станет плохой. Если же она мала, то относительная

доля

накладных расходов на переключения между исполняющимися зада-

чами станет большой и это ухудшит производительность системы.

Дисциплина диспетчеризации RR – это одна из самых распространен-

ных дисциплин. Однако бывают ситуации, когда ОС не поддерживает в

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

130

торых ОС реального времени используется диспетчер задач, работающий

по принципам абсолютных приоритетов (процессор предоставляется зада-

че с максимальным приоритетом, а при равенстве приоритетов он дейст-

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

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

этому если нужно организовать обслуживание задач

таким образом, чтобы

все они получали процессорное время равномерно и равноправно, то сис-

темный оператор может сам организовать эту дисциплину. Для этого дос-

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

ты и создать одну высокоприоритетную задачу, которая не должна ничего

делать, но которая, тем не менее, будет по таймеру (через

указанные ин-

тервалы времени) планироваться на выполнение. Эта задача снимет с вы-

полнения текущее приложение, оно будет поставлено в конец очереди, и

поскольку этой высокоприоритетной задаче на самом деле ничего делать

не надо, то она тут же освободит процессор и из очереди готовности будет

взята следующая задача.

В своей простейшей реализации

дисциплина карусельной диспетчери-

зации предполагает, что все задачи имеют одинаковый приоритет. Если же

необходимо ввести механизм приоритетного обслуживания, то это, как

правило, делается за счет организации нескольких очередей. Процессор-

ное время будет предоставляться в первую очередь тем задачам, которые

стоят в самой привилегированной очереди. Если она пустая, то диспетчер

задач

начнет просматривать остальные очереди. Именно по такому алго-

ритму действует диспетчер задач в операционных системах OS/2 и Win-

dows NT.

Вытесняющие и не вытесняющие алгоритмы диспетчеризации

Диспетчеризация без перераспределения процессорного времени, то

есть не вытесняющая многозадачность (non-preemptive multitasking) – это

такой способ диспетчеризации процессов, при котором активный процесс

выполняется до тех пор, пока он сам, что называется “по собственной

инициативе”, не отдаст управление диспетчеру задач для выбора из очере-

ди другого, готового к выполнению процесса или потока. К не

вытесняю-

щим относятся дисциплины обслуживания FCFS, SJN, SRT.

Диспетчеризация с перераспределением процессорного времени между

задачами, то есть вытесняющая многозадачность (preemptive multitasking)

– это такой способ, при котором решение о переключении процессора с

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

ся диспетчером задач, а не самой активной задачей. При вытесняющей

многозадачности механизм диспетчеризации задач целиком сосредоточен

в операционной системе, и программист может писать свое приложение,

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

дачами. При этом операционная система выполняет следующие функции:

определяет момент снятия с выполнения текущей задачи, сохраняет ее

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