МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО
ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
ФАКУЛЬТЕТ АВТОМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ
КАФЕДРА ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ
_____________________________________________________________________
Л. А. КОРШИКОВА
ОПЕРАЦИОННЫЕ СИСТЕМЫ КАК
СИСТЕМЫ УПРАВЛЕНИЯ
ВЫЧИСЛИТЕЛЬНЫМИ РЕСУРСАМИ
Новосибирск
2007
В учебном пособии содержатся основные сведения об организации и функционировании многопользовательских, многозадачных (многопроцессных) операционных систем. Подробно рассмотрены принципы синхронизации вычислительных процессов. Приводятся сведения о концепциях UNIX System V Release и Windows NT. Для специалистов в области программного обеспечения, для использования в дисциплинах, изучающих принципы построения и функционирования операционных систем.
|
Новосибирский государственный технический университет, 2007 г.
Введение. Операционная система как система управления ресурсами
Операционные системы – комплекс программ, управляющих ресурсами вычислительной системы, обеспечивающий автоматизацию процесса подготовки и выполнения программ пользователем.
Наиболее важная задача операционной системы (ОС) заключается в определении правильных абстракций. Такие абстракции как процессы, файлы, потоки исполнения и абстракции, относящиеся к синхронизации, модели памяти, моделированию ввода – вывода, представляют собой понятия, связанные с функционированием многозадачных ОС ( многопользовательских ОС).
Каждая абстракция может быть реализована в виде конкретных структур данных. Пользователи могут создавать процессы, файлы, семафоры, и т. д. Управляют этими структурами данных при помощи примитивных операций, которые реализуются в виде системных вызовов. Итак, основа ОС формируется абстракциями, а операции над ними возможны при помощи системных вызовов. Операционные системы – комплекс программ, управляющих ресурсами вычислительной системы, обеспечивающий автоматизацию процесса подготовки и выполнения программ пользователем.
. В ОС широко используется концепция процессов с целью защиты от влияния пользователей друг на друга. При необходимости совместного использования пользователями данных и ресурсов, изоляция должна быть избирательной. Все это усложняет устройства ОС
ОС должна иметь дело с параллелизмом. В системе одновременно присутствует множество пользователей, работающих с множеством устройств ввода – вывода. Среди возникающих при этом проблем можно говорить о тупиковых ситуациях и состязаниях.
1. Классификация операционных систем
Операционные системы могут различаться особенностями реализации внутренних алгоритмов управления основными ресурсами компьютера (процессорами, памятью, устройствами), особенностями использованных методов проектирования, типами аппаратных платформ, областями использования и многими другими свойствами.
Ниже приведена классификация ОС по нескольким наиболее основным признакам.
Поддержка многозадачности. По числу одновременно выполняемых задач операционные системы могут быть разделены на два класса:
· однозадачные (например, MS-DOS, MSX) и
· многозадачные (OC EC, OS/2, UNIX, Windows 95).
Однозадачные ОС в основном выполняют функцию предоставления пользователю виртуальной машины, делая более простым и удобным процесс взаимодействия пользователя с компьютером. Однозадачные ОС включают средства управления периферийными устройствами, средства управления файлами, средства общения с пользователем. Многозадачные ОС, кроме вышеперечисленных функций, управляют разделением совместно используемых ресурсов, таких как процессор, оперативная память, файлы и внешние устройства.
Поддержка многопользовательского режима. По числу одновременно работающих пользователей ОС делятся на:
· однопользовательские (MS-DOS, Windows 3.x, ранние версии OS/2);
· многопользовательские (UNIX, Windows NT).
Главным отличием многопользовательских систем от однопользовательских является наличие средств защиты информации каждого пользователя от несанкционированного доступа других пользователей. Следует заметить, что не всякая многозадачная система является многопользовательской, и не всякая однопользовательская ОС является однозадачной.
Вытесняющая и невытесняющая многозадачность. Важнейшим разделяемым ресурсом является процессорное время. Способ распределения процессорного времени между несколькими одновременно существующими в системе процессами (или нитями) во многом определяет специфику ОС. Среди множества существующих вариантов реализации многозадачности можно выделить две группы алгоритмов:
· невытесняющая многозадачность (NetWare, Windows 3.x);
· вытесняющая многозадачность (Windows NT, OS/2, UNIX).
Основным различием между вытесняющим и невытесняющим вариантами многозадачности является степень централизации механизма планирования процессов. В первом случае механизм планирования процессов целиком сосредоточен в операционной системе, а во втором - распределен между системой и прикладными программами. При невытесняющей многозадачности активный процесс выполняется до тех пор, пока он сам, по собственной инициативе, не отдаст управление операционной системе для того, чтобы та выбрала из очереди другой готовый к выполнению процесс. При вытесняющей многозадачности решение о переключении процессора с одного процесса на другой принимается операционной системой, а не самим активным процессом.
Поддержка многонитевости. Важным свойством операционных систем является возможность распараллеливания вычислений в рамках одной задачи. Многонитевая ОС разделяет процессорное время не между задачами, а между их отдельными ветвями (нитями).
Многопроцессорная обработка. Другим важным свойством ОС является отсутствие или наличие в ней средств поддержки многопроцессорной обработки - мультипроцессирование. Мультипроцессирование приводит к усложнению всех алгоритмов управления ресурсами. В наши дни становится общепринятым введение в ОС функций поддержки многопроцессорной обработки данных. Такие функции имеются в операционных системах Solaris 2.x фирмы Sun, Open Server 3.x компании Santa Crus Operations, OS/2 фирмы IBM, Windows NT фирмы Microsoft и NetWare 4.1 фирмы Novell. Многопроцессорные ОС могут классифицироваться по способу организации вычислительного процесса в системе с многопроцессорной архитектурой: асимметричные ОС и симметричные ОС. Асимметричная ОС целиком выполняется только на одном из процессоров системы, распределяя прикладные задачи по остальным процессорам. Симметричная ОС полностью децентрализована и использует весь пул процессоров, разделяя их между системными и прикладными задачами.
Выше были рассмотрены характеристики ОС, связанные с управлением только одним типом ресурсов – процессором. Важное влияние на облик операционной системы в целом, на возможности ее использования в той или иной области оказывают особенности и других подсистем управления локальными ресурсами – подсистем управления памятью, файлами, устройствами ввода-вывода.
Специфика ОС проявляется и в том, каким образом она реализует сетевые функции: распознавание и перенаправление в сеть запросов к удаленным ресурсам, передача сообщений по сети, выполнение удаленных запросов. При реализации сетевых функций возникает комплекс задач, связанных с распределенным характером хранения и обработки данных в сети: ведение справочной информации о всех доступных в сети ресурсах и серверах, адресация взаимодействующих процессов, обеспечение прозрачности доступа, тиражирование данных, согласование копий, поддержка безопасности данных.
2. Особенности областей использования
операционных систем
Многозадачные ОС подразделяются на три типа в соответствии с использованными при их разработке критериями эффективности:
· системы пакетной обработки (например, OC EC);
· системы разделения времени (UNIX, VMS);
· системы реального времени (QNX, RT/11).
Системы пакетной обработки предназначались для решения задач в основном вычислительного характера, не требующих быстрого получения результатов. Главной целью и критерием эффективности систем пакетной обработки является максимальная пропускная способность, то есть решение максимального числа задач в единицу времени. Для достижения этой цели в системах пакетной обработки используются следующая схема функционирования: в начале работы формируется пакет заданий, каждое задание содержит требование к системным ресурсам; из этого пакета заданий формируется мультипрограммная смесь, то есть множество одновременно выполняемых задач. Для одновременного выполнения выбираются задачи, предъявляющие отличающиеся требования к ресурсам, так, чтобы обеспечивалась сбалансированная загрузка всех устройств вычислительной машины; так, например, в мультипрограммной смеси желательно одновременное присутствие вычислительных задач и задач с интенсивным вводом-выводом. Таким образом, выбор нового задания из пакета заданий зависит от внутренней ситуации, складывающейся в системе, то есть выбирается "выгодное" задание. Следовательно, в таких ОС невозможно гарантировать выполнение того или иного задания в течение определенного периода времени. В системах пакетной обработки переключение процессора с выполнения одной задачи на выполнение другой происходит только в случае, если активная задача сама отказывается от процессора, например, из-за необходимости выполнить операцию ввода-вывода. Поэтому одна задача может надолго занять процессор, что делает невозможным выполнение интерактивных задач. Таким образом, взаимодействие пользователя с вычислительной машиной, на которой установлена система пакетной обработки, сводится к тому, что он приносит задание, отдает его диспетчеру-оператору, а в конце дня после выполнения всего пакета заданий получает результат. Очевидно, что такой порядок снижает эффективность работы пользователя.
Системы разделения времени призваны исправить основной недостаток систем пакетной обработки - изоляцию пользователя-программиста от процесса выполнения его задач. Каждому пользователю системы разделения времени предоставляется терминал, с которого он может вести диалог со своей программой. Так как в системах разделения времени каждой задаче выделяется только квант процессорного времени, ни одна задача не занимает процессор надолго, и время ответа оказывается приемлемым. Если квант выбран достаточно небольшим, то у всех пользователей, одновременно работающих на одной и той же машине, складывается впечатление, что каждый из них единолично использует машину. Ясно, что системы разделения времени обладают меньшей пропускной способностью, чем системы пакетной обработки, так как на выполнение принимается каждая запущенная пользователем задача, а не та, которая "выгодна" системе, и, кроме того, имеются накладные расходы вычислительной мощности на более частое переключение процессора с задачи на задачу. Критерием эффективности систем разделения времени является не максимальная пропускная способность, а удобство и эффективность работы пользователя.
Системы реального времени применяются для управления различными техническими объектами, такими, например, как станок, спутник, научная экспериментальная установка или технологическими процессами, такими, как гальваническая линия, доменный процесс и т. п. Во всех этих случаях существует предельно допустимое время, в течение которого должна быть выполнена та или иная программа, управляющая объектом, в противном случае может произойти авария: спутник выйдет из зоны видимости, экспериментальные данные, поступающие с датчиков, будут потеряны, толщина гальванического покрытия не будет соответствовать норме. Таким образом, критерием эффективности для систем реального времени является их способность выдерживать заранее заданные интервалы времени между запуском программы и получением результата (управляющего воздействия). Это время называется временем реакции системы, а соответствующее свойство системы – реактивностью. Для этих систем мультипрограммная смесь представляет собой фиксированный набор заранее разработанных программ, а выбор программы на выполнение осуществляется исходя из текущего состояния объекта или в соответствии с расписанием плановых работ.
Некоторые операционные системы могут совмещать в себе свойства систем разных типов, например, часть задач может выполняться в режиме пакетной обработки, а часть – в режиме реального времени или в режиме разделения времени. В таких случаях режим пакетной обработки часто называют фоновым режимом.
Ниже приведена схема, иллюстрирующая все вышесказанное в компактном виде (рис. 1).
Схема формализации типов ОС
(классификация)
Рис. 1. Схема формализации типов ОС (классификация)
3. Управление процессами
Важнейшей частью операционной системы, непосредственно влияющей на функционирование вычислительной машины, является подсистема управления процессами. Процесс (или по-другому, задача) – абстракция, описывающая выполняющуюся программу. Для операционной системы процесс представляет собой единицу работы, заявку на потребление системных ресурсов. Подсистема управления процессами планирует выполнение процессов, то есть распределяет процессорное время между несколькими одновременно существующими в системе процессами, а также занимается созданием и уничтожением процессов, обеспечивает процессы необходимыми системными ресурсами, поддерживает взаимодействие между процессами. Таким образом, управление процессами связано с управлением основным вычислительным ресурсом – процессором.
3.1. Состояние процессов
В многозадачной (многопроцессной) системе процесс может находиться в одном из трех основных состояний:
- ВЫПОЛНЕНИЕ – активное состояние процесса, во время которого процесс обладает всеми необходимыми ресурсами и непосредственно выполняется процессором;
- ОЖИДАНИЕ – пассивное состояние процесса, процесс заблокирован, он не может выполняться по своим внутренним причинам, он ждет осуществления некоторого события, например, завершения операции ввода-вывода, получения сообщения от другого процесса, освобождения какого-либо необходимого ему ресурса;
- ГОТОВНОСТЬ – также пассивное состояние процесса, но в этом случае процесс заблокирован в связи с внешними по отношению к нему обстоятельствами: процесс имеет все требуемые для него ресурсы, он готов выполняться, однако процессор занят выполнением другого процесса.
В ходе жизненного цикла каждый процесс переходит из одного состояния в другое в соответствии с алгоритмом планирования процессов, реализуемым в данной операционной системе. Типичный граф состояний процесса показан на рис. 2.
 |
Рис.2. Граф состояний процесса в многозадачной среде
В состоянии ВЫПОЛНЕНИЕ в однопроцессорной системе может находиться только один процесс, а в каждом из состояний ОЖИДАНИЕ и ГОТОВНОСТЬ – несколько процессов, эти процессы образуют очереди соответственно ожидающих и готовых процессов. Жизненный цикл процесса начинается с состояния ГОТОВНОСТЬ, когда процесс готов к выполнению и ждет своей очереди. При активизации процесс переходит в состояние ВЫПОЛНЕНИЕ и находится в нем до тех пор, пока либо он сам освободит процессор, перейдя в состояние ОЖИДАНИЯ какого-нибудь события, либо будет насильно "вытеснен" из процессора, например, вследствие исчерпания отведенного данному процессу кванта процессорного времени. В последнем случае процесс возвращается в состояние ГОТОВНОСТЬ. В это же состояние процесс переходит из состояния ОЖИДАНИЕ, после того, как ожидаемое событие произойдет.
3.2. Планирование процессов
Планирование процессов включает в себя решение следующих задач:
- определение момента времени для смены выполняемого процесса;
- выбор процесса на выполнение из очереди готовых процессов;
- переключение контекстов "старого" и "нового" процессов.
Первые две задачи решаются программными средствами, а последняя в значительной степени аппаратно. Существует множество различных алгоритмов планирования процессов, по-разному решающих вышеперечисленные задачи, преследующих различные цели и обеспечивающих различное качество мультипрограммирования. Среди этого множества алгоритмов рассмотрим подробнее две группы наиболее часто встречающихся алгоритмов: алгоритмы, основанные на квантовании, и алгоритмы, основанные на приоритетах.
В соответствии с алгоритмами, основанными на квантовании, смена активного процесса происходит, если:
· процесс завершился и покинул систему,
· произошла ошибка,
· процесс перешел в состояние ОЖИДАНИЕ,
· исчерпан квант процессорного времени, отведенный данному процессу.
Процесс, который исчерпал свой квант, переводится в состояние ГОТОВНОСТЬ и ожидает, когда ему будет предоставлен новый квант процессорного времени, а на выполнение в соответствии с определенным правилом выбирается новый процесс из очереди готовых. Таким образом, ни один процесс не занимает процессор надолго, поэтому квантование широко используется в системах разделения времени. Кванты, выделяемые процессам, могут быть одинаковыми для всех процессов или различными. Кванты, выделяемые одному процессу, могут быть фиксированной величины или изменяться в разные периоды жизни процесса. Процессы, которые не полностью использовали выделенный им квант (например, из-за ухода на выполнение операций ввода-вывода), могут получить или не получить компенсацию в виде привилегий при последующем обслуживании. По-разному может быть организована очередь готовых процессов: циклически, по правилу "первый пришел – первый обслужился" (FIFO) или по правилу "последний пришел – первый обслужился" (LIFO). Другая группа алгоритмов использует понятие "приоритет" процесса. Приоритет – это число, характеризующее степень привилегированности процесса при использовании ресурсов вычислительной машины, в частности, процессорного времени: чем выше приоритет, тем выше привилегии. Приоритет может выражаться целыми или дробными, положительным или отрицательным значением. Чем выше привилегии процесса, тем меньше времени он будет проводить в очередях. Приоритет может назначаться директивно администратором системы в зависимости от важности работы или внесенной платы, либо вычисляться самой ОС по определенным правилам, он может оставаться фиксированным на протяжении всей жизни процесса либо изменяться во времени в соответствии с некоторым законом. В последнем случае приоритеты называются динамическими. Существует две разновидности приоритетных алгоритмов: алгоритмы, использующие относительные приоритеты, и алгоритмы, использующие абсолютные приоритеты. В обоих случаях выбор процесса на выполнение из очереди готовых осуществляется одинаково: выбирается процесс, имеющий наивысший приоритет. По-разному решается проблема определения момента смены активного процесса. В системах с относительными приоритетами активный процесс выполняется до тех пор, пока он сам не покинет процессор, перейдя в состояние ОЖИДАНИЕ (или же произойдет ошибка, или процесс завершится). В системах с абсолютными приоритетами выполнение активного процесса прерывается еще при одном условии: если в очереди готовых процессов появился процесс, приоритет которого выше приоритета активного процесса. В этом случае прерванный процесс переходит в состояние готовности. На рис. 3 показаны графы состояний процесса для алгоритмов с относительными (а) и абсолютными (б) приоритетами.
 |  |
Рис.3. Графы состояний процессов в системах
(а) с относительными приоритетами; (б)с абсолютными приоритетами
Во многих операционных системах алгоритмы планирования построены с использованием как квантования, так и приоритетов. Например, в основе планирования лежит квантование, но величина кванта и/или порядок выбора процесса из очереди готовых определяется приоритетами процессов.
3.3. Вытесняющие и невытесняющие алгоритмы планирования
Существует два основных типа процедур планирования процессов – вытесняющие (preemptive) и невытесняющие (non-preemptive).
Non-preemptive multitasking – невытесняющая многозадачность – это способ планирования процессов, при котором активный процесс выполняется до тех пор, пока он сам, по собственной инициативе, не отдаст управление планировщику операционной системы для того, чтобы тот выбрал из очереди другой, готовый к выполнению процесс.
Preemptive multitasking – вытесняющая многозадачность – это такой способ, при котором решение о переключении процессора с выполнения одного процесса на выполнение другого процесса принимается планировщиком операционной системы, а не самой активной задачей.
Вытесняющая и невытесняющая многозадачность – это более широкие понятия, чем типы приоритетности. Приоритеты задач могут как использоваться, так и не использоваться и при вытесняющих, и при невытесняющих способах планирования. Так в случае использования приоритетов дисциплина относительных приоритетов может быть отнесена к классу систем с невытесняющей многозадачностью, а дисциплина абсолютных приоритетов - к классу систем с вытесняющей многозадачностью. А бесприоритетная дисциплина планирования, основанная на выделении равных квантов времени для всех задач, относится к вытесняющим алгоритмам. Основным различием между preemptive и non-preemptive вариантами многозадачности является степень централизации механизма планирования задач. При вытесняющей многозадачности механизм планирования задач целиком сосредоточен в операционной системе, и программист пишет свое приложение, не заботясь о том, что оно будет выполняться параллельно с другими задачами. При этом операционная система выполняет следующие функции: определяет момент снятия с выполнения активной задачи, запоминает ее контекст, выбирает из очереди готовых задач следующую и запускает ее на выполнение, загружая ее контекст. При невытесняющей многозадачности механизм планирования распределен между системой и прикладными программами. Прикладная программа, получив управление от операционной системы, сама определяет момент завершения своей очередной итерации и передает управление ОС с помощью какого-либо системного вызова, а ОС формирует очереди задач и выбирает в соответствии с некоторым алгоритмом (например, с учетом приоритетов) следующую задачу на выполнение. Такой механизм создает проблемы как для пользователей, так и для разработчиков.
Для пользователей это означает, что управление системой теряется на произвольный период времени, который определяется приложением (а не пользователем). Если приложение тратит слишком много времени на выполнение какой-либо работы, например, на форматирование диска, пользователь не может переключиться с этой задачи на другую задачу, например, на текстовый редактор, в то время как форматирование продолжалось бы в фоновом режиме. Эта ситуация нежелательна, так как пользователи обычно не хотят долго ждать, когда машина завершит свою задачу. Поэтому разработчики приложений для non-preemptive операционной среды, возлагая на себя функции планировщика, должны создавать приложения так, чтобы они выполняли свои задачи небольшими частями. Например, программа форматирования может отформатировать одну дорожку дискеты и вернуть управление системе. После выполнения других задач система возвратит управление программе форматирования, чтобы та отформатировала следующую дорожку. Подобный метод разделения времени между задачами работает, но он существенно затрудняет разработку программ и предъявляет повышенные требования к квалификации программиста. Программист должен обеспечить "дружественное" отношение своей программы к другим выполняемым одновременно с ней программам, достаточно часто отдавая им управление. Крайним проявлением "недружественности" приложения является его зависание, которое приводит к общему краху системы. В системах с вытесняющей многозадачностью такие ситуации, как правило, исключены, так как центральный планирующий механизм снимет зависшую задачу с выполнения. Однако распределение функций планировщика между системой и приложениями не всегда является недостатком, а при определенных условиях может быть и преимуществом, потому что дает возможность разработчику приложений самому проектировать алгоритм планирования, наиболее подходящий для данного фиксированного набора задач. Так как разработчик сам определяет в программе момент времени отдачи управления, то при этом исключаются нерациональные прерывания программ в "неудобные" для них моменты времени. Кроме того, легко разрешаются проблемы совместного использования данных: задача во время каждой итерации использует их монопольно и уверена, что на протяжении этого периода никто другой не изменит эти данные. Существенным преимуществом non-preemptive систем является более высокая скорость переключения с задачи на задачу. Примером эффективного использования невытесняющей многозадачности является файл-сервер NetWare, в котором, в значительной степени благодаря этому, достигнута высокая скорость выполнения файловых операций. Менее удачным оказалось использование невытесняющей многозадачности в операционной среде Windows 3.х.
Однако почти во всех современных операционных системах, ориентированных на высокопроизводительное выполнение приложений (UNIX, Windows NT, OS/2, VAX/VMS), реализована вытесняющая многозадачность. В последнее время дошла очередь и до ОС класса настольных систем, например, OS/2 Warp и Windows 95. Возможно, в связи с этим вытесняющую многозадачность часто называют истинной многозадачностью.
3.4. Функции планировщика-диспетчера
Во многих ОС эти функции могут быть представлены неразрывной последовательностью, поэтому введем термин планировщик-диспетчер.
Планировщик – это программа, ответственная за постановку процессов в очередь-на-выполнение и управляющая этой очередью.
Диспетчер – это программа, которая выбирает процессы из очереди-на-выполнение, переводит их в активное состояние и передает им контроль над центральным процессором (CPU).
Основная функция планировщика-диспетчера – возможность управлять действиями большого числа процессов.
3.4.1. Приостановка процесса
В ходе своего выполнения системный процесс может установить, что требуемый ресурс занят или в данный момент процессу не требуется производить каких-либо действий. Тогда процесс может "сознательно" приостановить свое выполнение до момента активизации его другим процессом. При этой процедуре адрес блока управления процессом (БУП) записывается в стек, затем для активизации другого процесса вызывается системный планировщик. Результатом этого действия является то, что "приостановленный" процесс не помещается в очередь-на-выполнение, т. е. не активизируется (рис. 4).
Этот элемент не активный, т. е. он приостановлен, но связи в очереди процессов сохраняются
Рис. 4. Схемы очередей блоков управления процессами
до а) и после б) "приостановки"
Алгоритм "Приостановить процесс"
·НАЧАЛО
·Анализ прерывания
·procedure "ПРИОСТАНОВИТЬ"
· IF1<приостанавливаемый процесс не является системным и находится в ОП>
·блокировать процесс по условию выгрузки из ОП
·IF2<есть свободный блок запроса в очереди приостановок>
·создать блок запроса в очереди приостановок
·разблокировать процесс "откачки"
·формировать код возврата по удачному завершению
·передать управление диспетчеру
·FI2
·формирование кода возврата по перегрузке системы
· передать управление диспетчеру
·FI1
·формировать код возврата по невозможности приостановки
·передать управление диспетчеру
·КОНЕЦ
3.4.2. Отсрочка процесса
При выполнении длинных кодовых инструкций процесс может надолго занять CPU. Это означает, что за исключением прерываний никакой другой процесс не имеет доступ к CPU. Для облегчения доступа к CP процесс может осуществить повторное планирование, тем самым "отсрочить" свое выполнение.
При отсрочке процесса адрес блока управления помещается в стек процесса. Затем процесс выдает запрос на планирование, вызывая процедуру "Активизировать", с указанием адреса собственного БУП. Планировщик-диспетчер выбирает на выполнение следующий процесс из очереди.
Алгоритм "Возобновить Процесс"
·НАЧАЛО
·Анализ прерывания
·procedure "ВОЗОБНОВИТЬ"
·IF1<процесс не системный и был выгружен из ОП>
·IF2<есть свободные блоки запросов в очереди возобновлений>
·поместить блок запроса в очередь возобновлений
·разблокировать процесс подкачек
·блокировать процесс по условию загрузки в ОП
·формировать код возврата по удачному завершению
·переход к диспетчеру
·FI2
·формировать код возврата по перегрузке системы
· переход к диспетчеру
·FI1
·формировать код возврата по невозможности возобновления
·перейти к диспетчеру
·КОНЕЦ
3.4.3. Активизация процесса
Процесс, вызывающий отсроченный процесс, активизирует его процедурой "Активизировать" с указание адреса блока управления процессом.
Алгоритм "Активизировать процесс"
1. Процедура "Активизировать" помещает БУП в очередь-на-выполнение.
2. Проверяет, совпадают ли адрес БУП с адресом текущего выполняющегося процесса.
3. Если не совпадают, то процесс помещается в очередь-на-выполнение.
4. Если совпадает, то БУП уже находится в конце очереди-на-выполнение.
Общий вид алгоритма "Активизировать процесс", используемого при диспетчеризации
·НАЧАЛО
·procedure DISPATCH
·обновить БУП активного процесса
·выбрать следующий "Готовый" процесс для передачи ему управления
·IF1< "Готовый" процесс найден>
·пометить его как "активный"
·выделить квант времени, установить командой SETTAME – интервальный таймер
·передать управление выбранному процессу
·FI1
·перевести CPU в состояние простоя (режим "холостого хода")
·КОНЕЦ
При передаче управления от одного процесса к другому, прежде всего, надо сохранить информацию о состоянии активного процесса. Если процесс был заблокирован по причине Dt, то информация о состоянии процесса может быть найдена в рабочей области прерываний по таймеру.
После сохранения состояния предыдущего активного процесса диспетчер выбирает для активизации новый процесс.
Чтобы задать квант времени, выделяемый процессу, диспетчер устанавливает интервальный таймер. Затем диспетчер использует команду LPS (Load Process Status) (загрузка состояния процесса) для загрузки информации о состоянии данного процесса и осуществляет передачу управления.
Если процесса в состоянии готовности нет, то диспетчер переводит CPU в состояние простоя. Выбор следующего процесса для диспетчеризации осуществляется несколькими способами (например, используя дисциплину RR – "круговой алгоритм"). Диспетчер циклически просматривает все БУП-ы, выбирает следующий процесс из тех, что находятся в готовности. Каждому активизированному процессу предоставляет одинаковый квант времени.
В ОС UNIX диспетчеризация организована по принципу динамического приоритета.
3.4.4. Ведущие и разделяемые процессами планировщики-диспетчеры
Планировщик-диспетчер может разделяться процессами, т. е. планировщик вызывается путем обращений i-го процесса к данной системной программе S, что является косвенным результатом операции ядра ОС. Ядро и планировщик тогда потенциально содержатся в адресном пространстве всех процессов и выполняются в составе любого процесса (рис. 5).
 |
Рис. 5. Разделение планировщика-диспетчера (S - планировщик; P r i – процесс)
Другой тип планировщика считается отдельным процессом, он может непрерывно проверять заявки системы на планирование или может активизироваться соответствующими сигналами (рис. 6).
 |
Рис. 6. Централизация планировщика-диспетчера
Схема взаимодействия планировщика представлена на рис. 7.
Рис. 7. Схема взаимодействия планировщика-диспетчера со структурами
системных данных и примитивов ядра
На рис. 8 представлен список готовности процессов, который построен на приоритетном базисе и содержит все процессы в состояниях, соответствующих уровню их исполнения.
Планировщик вызывается примитивами ядра, при этом учитывается состояние дескрипторов процессов и структура процесса.
 |
Рис.8. Список готовности процессов
Планировщик работает со списком готовности процессов на основе дисциплины диспетчеризации с вытеснением.
Пример планирования и диспетчеризации в системе разделения времени
Предполагается наличие следующих структур:
· диспетчер – циклически проходит через очередь задач (процессов);
· программа инициализации – инициирует переменные и массивы;
· программа обработки входных данных – обрабатывает приходящие запросы на активацию (активизацию) процессов (задач) и на обновление файлов-дублей;
· программа управления таймером;
· программа обработки условных активаций – контролирует совпадающие пары запросов на активацию;
· предпланировщик реконфигурации – генерирует модификацию после получения всех запрошенных отчетов о состоянии управления ресурсами;
· планировщик процессов – выбирает из очереди с учетом приоритетов процесс и предоставляет процессор;
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 |
