3.1. Состояния процессов

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

В главе 2, "Обзор операционных систем" упоминалось, что для каждой программы, которая должна быть выполнена, создается свой процесс, или задание. С точки зрения процесса его работа состоит в выполнении определенного набора команд; последовательность выполнения этих команд задается адресами, которые заносятся в счетчик команд. Через некоторое время счетчик команд может адресовать код других программ, которые являются частями других процессов, но с точки зрения данной программы ее выполнение состоит из последовательного выполнения ее команд.

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

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

² Иногда в русскоязычной литературе используются термины траектория и трасса, — Прим, перев.

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

Листинг 3.1. Следы процессов, изображенных на рис. 3.1

5000	8000	12000
5001	8001	12001
5002	8002	12002
5003	8003	12003
5004		12004
5005		12005
5006		12006
5007		12007
5008		12008
5009		12009
5010		12010
5011		12011
а) След	б) След	в) След
процесса А	процесса В	процесса С

5000 - начальный адрес процесса А

8000 - начальный адрес процесса В

12000 - начальный адрес процесса С

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

Листинг. 3.2. Составной след процессов, изображенных на рис. 3.1

1	5000	27	12004
2	5001	28	12005
3	5002		---тайм-аут
5	5003	29	D0
6	5004	30	D1
6	5005	31	D2
	--- тайм-аут	32	D3
7	100	33	D4
8	101	34	D5
9	102	35	5006 5
10	103	36	5007
11	104	37	5008
12	105	38	5009
13	8000	39	5010
14	8001	40	5011
15	8002	41	100
16	8003	42	101
17	100	43	102
18	101	44	103
19	102	45	104
20	103	46	105
21	104	47	12006
22	105	48	12007
23	12000	49	12008
24	12001	50	12009
25	12002	51	12010
26	12003	52	12011

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

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

Модель процесса с двумя состояниями

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

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

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

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

Создание и завершение процессов

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

Создание процессов

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

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

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

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

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

Когда один процесс порождает другой, то порождающий процесс называется родительским, или предком (parent), а порождаемый процесс — дочерним, или потомком (child). Обычно "родственные" процессы обмениваются между собой информацией и взаимодействуют друг с другом. Организация такого взаимодействия является достаточно трудной задачей для программиста (эта тема рассматривается в главе 5, "Параллельные вычисления: взаимоисключения и многозадачность").

Завершение процессов

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

Таблица3.2 Причины завершения процессов

Обычное завершение	Процесс вызывает службу операционной системы, чтобы сообщить, что он завершил работу.
Превышение лимита отведенного программе времени	Общее время выполнения процесса превышает заданное предельное значение. Это время может измеряться несколькими способами. Одним из них является учет полного времени, затраченного на выполнение ("по настенным часам"); при выполнении интерактивного процесса время можно отсчитывать с момента последнего ввода данных пользователем
Недостаточный объем памяти	Для работы процесса требуется больше памяти, чем имеется в системе
Выход за пределы отве­денной области памяти	Процесс пытается получить доступ к ячейке памяти, к которой у него нет прав доступа
Ошибка защиты	Процесс пытается использовать недоступный для него ресурс или файл, или пытается сделать это недопустимым образом — например, производит попытку записи в файл, открытый только для чтения
Арифметическая ошибка	Процесс пытается выполнить запрещенную арифметическую операцию, например, деление на ноль, или пытается использовать число, превышающее возможности аппаратного обеспечения
Излишнее ожидание	Процесс ждет наступления определенного события дольше, чем задано в параметрах системы
Ошибка ввода-вывода	Во время ввода или вывода происходит ошибка. Например, не удается найти нужный файл или выполнить чтение или запись за максимально возможное количество попыток (когда, например, на магнитном носителе попался дефектный участок) или производится попытка выполнить недопустимую операцию (например, чтение с печатающего устройства)
Неверная команда	Процесс пытается выполнить несуществующую команду (часто это бывает, если процесс переходит в область данных и пытается интерпретировать их как команду)
Команда с недоступны­ми привилегиями	Процесс пытается использовать команду, зарезервированную для операционной системы
Неправильное исполь­зование данных	Часть данных принадлежит не к тому типу или не инициализирована
Вмешательство опера­тора или операционной системы	По какой-либо причине операционная система может завершить процесс (например, в случае взаимоблокировки)
Завершение родительского процесса	При завершении родительского процесса операционная система может автоматически прекращать все его дочерние процессы
Запрос со стороны родительского процесса	Обычно родительский процесс имеет право прекращать любой из своих дочерних процессов

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

⁴Наконец, в некоторых операционных системах процесс может быть завершен процессом, который его породил, а также при завершении самого родительского процесса.

Модель с пятью состояниями

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

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

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

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

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

• Блокированный. Процесс, который не может выполняться до тех пор, пока не произойдет некоторое событие, например завершение операции ввода-вывода.

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

• Завершающийся. Процесс, удаленный операционной системой из пула выполнимых процессов.

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

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

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

• Нулевое состояние —> Новый. Для выполнения программы создается новый процесс. Это событие может быть вызвано одной из причин, перечисленных в табл. 3.1.

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

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

• Выполняющийся —> Завершающийся. Если процесс сигнализирует об окончании своей работы или происходит его аварийное завершение, операционная система прекращает его выполнение.

• Выполняющийся —> Готовый. Этот переход чаще всего происходит из-за того, что процесс выполняется в течение максимального промежутка времени, отведенного для непрерывной работы одного процесса. Подобная стратегия планирования используется практически во всех многозадачных операционных системах. Такой переход возможен и по некоторым другим причинам, зависящим от конкретной операционной системы. Например, если операционная система назначает разным процессам различные приоритеты, то может случиться так, что процесс будет выгружен из-за появления процесса с более высоким приоритетом. Предположим, что выполняется процесс А, имеющий определенный приоритет, а процесс В, приоритет которого выше, блокирован. Когда операционная система обнаружит, что произошло событие, ожидаемое процессом В, она переведет этот процесс в состояние готовности, в результате чего процесс А может быть прерван и управление перейдет к процессу В. Говорят, что операционная система вытесняет (preempt) процесс А. Наконец, процесс сам по себе может отказаться от использования процессора.

• Выполняющийся —> Блокированный. Процесс переводится в заблокированное cостояние, если для продолжения работы требуется наступление некоторого события. Посылаемый операционной системе запрос обычно имеет вид вызова

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

• Блокированный -> Готовый. Заблокированный процесс переходит в состояние готовности к выполнению в тот момент, когда происходит ожидаемое им событие.

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

• Блокированный --> Завершающийся. См. комментарии к предыдущему пункту.

Возвратимся к нашему простому примеру. На рис. 3.4 показаны переходы каждого из трех рассматриваемых процессов в различные состояния. На рис. 3.5,а предложен один из способов реализации порядка очередности. Имеется две очереди: очередь готовых к выполнению процессов и очередь заблокированных процессов. Каждый процесс, поступающий в систему для обработки, помещается в очередь готовых к выполнению процессов. Когда операционной системе приходит время выбрать для выполнения другой процесс, она выбирает его из этой очереди. Если схема приоритетов отсутствует, эта очередь может работать по принципу "первым вошел — первым вышел". Когда выполнение процесса прерывается, он, в зависимости от обстоятельств, может либо завершиться, либо попасть в одну из двух очередей (готовых к выполнению или блокированных процессов). И, наконец, после того как произойдет событие, все ожидающие его процессы из очереди заблокированных перемещаются в очередь готовых к выполнению процессов.

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

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

Приостановленные процессы

Необходимость свопинга

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

Можно привести убедительные аргументы в пользу добавления в модель и других состояний. Чтобы понять, какие выгоды могут дать эти новые состояния, рассмотрим систему, не использующую виртуальную память, в которой каждый процесс перед выполнением нужно загрузить в основную память. Таким образом, все процессы, представленные на рис. 3.5,б, должны находиться в основной памяти.

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

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

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

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

Если в модель поведения процессов ввести описанный свопинг, то нам придется ввести и новое состояние — состояние приостановленного процесса (рис. 3.6,а). Когда все процессы в основной памяти находятся в блокирован­ном состоянии, операционная система может приостановить один из процессов, переведя его в приостановленное состояние и сбросив на диск. Освобо­дившееся в основной памяти пространство можно будет использовать для за­грузки другого процесса.

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

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

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

• Готовый. Процесс, который находится в основной памяти и готов к выполнению.

• Блокированный. Процесс, находящийся в основной памяти и ожидающий какого-то события.

• Блокированный/Приостановленный. Процесс, находящийся во вторичной памяти (на диске) и ожидающий какого-то события.

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

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

А теперь рассмотрим модель переходов состояний, представленную на рис. 3.6,6 (пунктирными линиями показаны переходы, которые возможны, но не являются обязательными). Среди новых переходов наиболее важными являются следующие:

• Блокированный —> Блокированный/Приостановленный. Если к выполнению не готов ни один процесс, то по крайней мере один блокированный процесс выгружается из памяти, чтобы освободить место для другого процесса, который не является блокированным. Этот переход можно выполнять и при наличии гото­вых к выполнению процессов, если операционная система определит, что для выполняющегося в настоящее время процесса или процесса, управление к ко­торому перейдет в ближайшее время, нужно увеличить объем основной памяти для обеспечения адекватной производительности.

• Блокированный/Приостановленный —> Готовый/Приостановленный. Процесс в состоянии блокированного приостановленного переходит в состояние готового к выполнению приостановленного процесса, если происходит событие, которого ожидал этот процесс. Заметим, что для такого перехода операционная система должна иметь доступ к информации о состоянии приостановленных процессов.

• Готовый/Приостановленный —> Готовый. Когда в основной памяти нет готовых к выполнению процессов, операционной системе для продолжения вычислений требуется загрузить процесс в память. Может случиться и так, что у готового к выполнению приостановленного процесса окажется более высокий приоритет, чем у любого другого из готовых к выполнению процессов. В такой ситуации разработчик операционной системы может решить, что важнее обеспечить приоритет процесса, чем минимизировать свопинг.

• Готовый —> Готовый/Приостановленный. Обычно операционная система предпочитает приостанавливать не готовый, а заблокированный процесс, поскольку к выполнению готового процесса можно приступить немедленно, а блокированный процесс только зря занимает основную память, поскольку не может быть выполнен. Однако иногда оказывается, что единственный способ освободить достаточно большой блок основной памяти — это приостановить готовый к выполнению процесс. Операционная система может также вместо блокированного процесса с более высоким приоритетом приостановить готовый к выполнению процесс с более низким приоритетом, если блокированный процесс достаточно скоро будет готов к выполнению.

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

• Новый —> Готовый/Приостановленный и Новый —> Готовый. После создания нового процесса этот процесс может быть добавлен либо в очередь готовых к выполнению, либо в очередь готовых к выполнению приостановленных процессов. В любом из этих случаев операционная система должна создать таблицы для управления процессом и выделить ему адресное пространство. Лучше выполнить эти действия на ранних этапах, чтобы иметь больший запас неблокированных процессов. Однако если придерживаться этой стратегии, то в основной памяти может не хватить места для нового процесса. По этой причине предусмотрен переход нового процесса в состояние приостановленного готового к выполнению. С другой стороны, создание процесса в "последний момент" приводит к уменьшению непроизводительных затрат и позволяет операционной системе выполнять свои обязанности по созданию процессов даже тогда, когда она переполнена блокированными процессами.

• Блокированный/Приостановленный —> Блокированный. На первый взгляд может показаться, что учитывать такой переход бессмысленно. Зачем, в конце концов, загружать в память процесс, который не готов к выполнению? Однако рассмотрим такой сценарий: завершился некоторый процесс, освободив при этом определенную часть основной памяти. В очереди заблокированных приостановленных процессов находится процесс, приоритет ко­торого выше, чем у любого процесса из очереди готовых к выполнению, но приостановленных процессов. Кроме того, операционная система располагает аргументами в пользу того, что довольно скоро произойдет событие, которое снимет блокировку с этого высокоприоритетного процесса. При таких обстоятельствах резонно отдать предпочтение блокированному процессу перед готовыми к выполнению, загрузив в основную память именно его.

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

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

Другие использования приостановки

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

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

1. Этот процесс не может быть запущен в данный момент.

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

3. Процесс приостанавливается самостоятельно, операционной системой или родительским процессом.

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

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

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

Таблица 3.3. Причины, по которым процессы переходят в состояние приостановленных

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

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

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

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

3.2. ОПИСАНИЕ ПРОЦЕССОВ

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

Эта концепция проиллюстрирована на рис. 3.7. Пусть в многозадачной среде имеется несколько процессов (P_{1, . . .,} Р_n), которые уже созданы и загружены в

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

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

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

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

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

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

• объем основной памяти, отведенной процессу;

• объем вторичной памяти, отведенной процессу;

• все атрибуты защиты блоков основной или виртуальной памяти, как, например, указание, какой из процессов имеет доступ к той или иной совместно используемой области памяти;

• вся информация, необходимая для управления виртуальной памятью.

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

Таблицы ввода-вывода (I/O tables) используются операционной системой для управления устройствами ввода-вывода и каналами компьютерной системы. В каждый момент времени устройство ввода-вывода может быть либо свободно, либо отдано в распоряжение какому-то определенному процессу. Если выполняется операция ввода-вывода, операционная система должна иметь информацию о ее состоянии и о том, какие адреса основной памяти задействованы в этой операции в качестве источника вывода или места, куда передаются данные при вводе. Управление вводом-выводом рассматривается в главе 11, "Управление вво­дом-выводом и дисковое планирование".

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

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

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

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

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

Местоположение процесса

Перед тем как перейти к рассмотрению вопроса о размещении процесса или о его атрибутах, зададим себе еще более фундаментальный вопрос: в чем заключаются физические проявления процесса? Как минимум, в процесс входит про­грамма или набор программ, которые нужно выполнить. С этими программами связан набор ячеек памяти, в которых хранятся локальные и глобальные переменные и константы. Таким образом, процессу должен быть выделен такой объ­ем памяти, в котором поместились бы программа и данные, принадлежащие процессу. Кроме того, при работе программы обычно используется стек, с помо­щью которого реализуются вызовы процедур и передача параметров. Наконец, с каждым процессом связано несколько атрибутов, которые используются операционной системой для управления этим процессом. Обычно такой набор атрибутов называется управляющим блоком процесса (process control block).⁸ Множество, в которое входят программа, данные, стек и атрибуты, называется образом процесса (process image) (табл. 3.4).

⁸ Часто используются другие названия этой структуры данных — блок управле­ния задачей, дескриптор процесса, дескриптор задачи.

Таблица 3.4. Типичные элементы образа процесса

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

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

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

Таблица 3.5.

Информация о состоянии процесса

Регистры, Доступные пользователю

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

Управляющие регистры и регистры состояния

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

• Счетчик команд. В этом регистре хранится адрес очередной извлекающейся команды.

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

• Информация о состоянии. Сюда входят флаги разрешения прерываний и информация о режиме выполнения.

Указатели на стек

С каждым процессом связаны один или несколько системных стеков. В стеке хранятся параметры и адреса вызовов процедур и системных служб. Указатель стека указывает на его вершину.

Управляющая информация процесса Информация по планированию и состоянию

Эта информация нужна операционной системе для выполнения планирования и обычно включает следующее.

• Состояние процесса. Определяет готовность планируемого процесса к выполнению (т.е. выполняющийся, готовый к выполнению, ожидающий какого-то события или приостановленный).

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

• Информация, связанная с планированием. Эта информация зависит от используемого алгоритма планирования. В качестве примера можно привести такие по­казатели, как время ожидания или время, в течение которого процесс выполнялся при последнем запуске.

• Информация о событиях. Идентификация события, наступление которого позволит продолжить выполнение процесса, находящегося в состоянии ожидания.

Структурирование данных

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

Обмен информацией между процессами

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

Привилегии процессов

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

Управление памятью

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

Владение ресурсами и их использование

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

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

• информация по идентификации процесса;

• информация по состоянию процесса;

• информация, используемая при управлении процессом.

Что касается идентификации процесса (process identification), то почти во всех операционных системах каждому процессу присваивается числовой идентификатор, который может быть просто индексом в первичной таблице процессов (рис. 3.8). В любом случае должно иметься некоторое отображение, позволяющее операционной системе найти по идентификатору процесса соответствующие ему таблицы. Идентификаторы могут использоваться в разных ситуациях. В частности, они используются для реализации перекрестных ссылок на таблицы процес­сов из других таблиц, находящихся под управлением операционной системы. Например, таблицы памяти могут предоставлять информацию об основной па­мяти с указанием всех областей, выделенных каждому из процессов, указывае­мому посредством его идентификатора. Аналогичные ссылки могут быть и в таблицах ввода-вывода или таблицах файлов. Если процессы обмениваются между собой информацией, их идентификаторы указывают операционной системе участников такого обмена. При создании нового процесса идентификаторы ука­зывают родительский и дочерние процессы.

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

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

Следует заметить, что в процессорах любого вида имеется регистр или набор регистров, известных под названием "слово состояния программы" (program status word — PSW), в которых содержится информация о состоянии и кодах условий. Хорошим примером слова состояния процессора является регистр EFLAGS (показан на рис. 3.9 и описан в табл. 3.6), имеющийся в процессорах Pentium. Этот регистр используют все операционные системы, работающие на компьютерах Pentium.

Таблица 3.6. Биты регистра EFLAGS процессора Pentium

Управляющие биты Биты режима работы

Флаг проверки выравнивания

(Alignment check — AC)

Флаг устанавливается при адресации одинарного или двойного слова, не выровненного на границу слова или двойного слова.

Флаг идентификации

(Identification flag — IF)

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