Основной задачей процессора является выполнение машинных команд, которые находятся в основной памяти и составляют программу. В предыдущей главе объяснялось, что с целью повышения эффективности и облегчения процесса программирования процессор может одновременно выполнять несколько программ, чередуя их во времени.
Ранее упоминалось, что для каждой программы, которая должна быть выполнена, создается свой процесс, или задание. С точки зрения процесса его работа состоит в выполнении определенного набора команд; последовательность выполнения этих команд задается адресами, которые заносятся в счетчик команд. Через некоторое время счетчик команд может адресовать код других программ, которые являются частями других процессов, но с точки зрения данной программы ее выполнение состоит из последовательного выполнения ее команд.
Поведение процесса можно охарактеризовать, последовательно перечислив выполненные в ходе его работы команды. Такой перечень выполненных команд процесса называется его следом (trace). Поведение процессора можно охарактеризовать, показав, как чередуются следы различных процессов.
Рассмотрим очень простой пример. На рис. 3.1 показано расположение в памяти трех процессов. Чтобы упростить обсуждение, предположим, что виртуальная память не используется; таким образом, все три процесса представлены программами, которые полностью загружены в основную память. Кроме этих программ в памяти находится небольшая программа-диспетчер, выполняющая переключение с одного процесса на другой. В листинге 3.1 показаны следы трех рассматриваемых процессов на ранних стадиях их выполнения. Представлены первые 12 выполненных команд в процессах А и С; в процессе В выполнено четыре команды, и мы считаем, что эти команды включают в себя операцию ввода-вывода, завершения которой должен ожидать процесс.
Рис. 3.1 Состояние системы в момент выполнения 13-го командного цикла (см. листинг 3.2)
Листинг 3.1. Следы процессов, изображенных на рис. 3.1
Теперь рассмотрим эти следы с точки зрения процессора. В листинге 3.2 показаны чередующиеся следы, получившиеся в результате выполнения первых 52 командных циклов (для удобства они пронумерованы). Предположим, что операционная система позволяет непрерывно выполнять не более шести командных циклов одного и того же процесса, после чего процесс прерывается — это предотвращает монопольное использование всего процессорного времени одним из процессов. Из листинга 3.2 видно, что после первых шести команд процесса А следует перерыв, в течение которого выполняется некоторый код диспетчера, состоящий из шести команд, после чего управление передается процессу В.3 Выполнив четыре команды, процесс В запрашивает операцию ввода-вывода и должен ожидать ее завершения. Поэтому процессор прекращает выполнять процесс Вис помощью диспетчера переходит к выполнению процесса С. После очередного перерыва процессор возобновляет выполнение процесса А. По истечении отведенного этому процессу времени процесс В все еще ожидает завершения операции ввода-вывода, поэтому диспетчер снова передает управление процессу С
Листинг. 3.2. Составной след процессов, изображенных на рис. 3.1
100 - начальный адрес программы-диспетчера Заштрихованные области - выполнение команд диспетчера В первом столбце указаны номера командных циклов, во втором - адреса выполняемых команд
Модель процесса с двумя состояниями
Основной задачей операционной системы является управление выполнением процессов; в эту задачу входит определение схемы чередования процессов и выделения им ресурсов. Первый шаг, который следует предпринять при составлении программы, предназначенной для управления процессами, состоит в описании ожидаемого поведения процессов.
Самую простую модель можно построить, исходя из того, что в любой момент времени процесс либо выполняется, либо не выполняется. Таким образом, процесс может быть в одном из двух состояний: выполняющийся или не выполняющийся (рис. 3.2,а). Создав новый процесс, операционная система вводит его в систему в состоянии не выполняющегося. Созданный процесс, о существовании которого известно операционной системе, ждет, пока он сможет быть запущен. Время от времени выполняющиеся процессы будут прерываться, и та часть операционной системы, которая выполняет функции диспетчера, будет выбирать для выполнения другой процесс. Выполняющийся перед этим процесс перейдет из состояния выполняющегося в состояние не выполняющийся, а в состояние выполняющегося перейдет один из ожидающих процессов.
Анализируя эту простую модель, можно сделать некоторые выводы относительно архитектуры операционной системы. Необходим способ, с помощью которого будет представлен каждый процесс, чтобы операционная система могла следить за ним. С каждым процессом нужно связать определенную информацию, в которую будет входить его текущее состояние процессов и размещение в памяти. Не выполняющиеся процессы следует организовать в какую-то очередь, где они ожидали бы своего выполнения. Один из возможных вариантов предложен на рис. 3.2,6. Здесь имеется одна очередь, ее элементами являются указатели на процессы. Можно предложить и другую схему, в которой очередь состоит из связанного списка блоков данных, где каждый блок представляет отдельный процесс; позже мы вернемся к исследованию этой реализации.
Диспетчеризация
6) Диаграмма использования очереди
Рис. 3.2. Модель процесса с двумя состояниями
Поведение диспетчера можно описать следующим образом. Процесс, работа которого прервана, переходит в очередь процессов, ожидающих выполнения. Если же процесс завершен, он выводится из системы. В любом случае для выполнения диспетчер выбирает из очереди следующий процесс.
Модель с пятью состояниями
Если бы все процессы всегда были готовы к выполнению, то очередь на рис. 3.2,6 могла бы работать вполне эффективно. Такая очередь работает по принципу обработки в порядке поступления, а процессор обслуживает имеющиеся в наличии процессы круговым (round-robin)5 методом (каждому процессу в очереди отводится определенный промежуток времени, по истечении которого процесс возвращается обратно в очередь, если он не был блокирован). Однако даже в таком простом примере, который был описан выше, подобная реализация не является адекватной: некоторые из не выполняющихся процессов готовы к выполнению, в то время как другие являются заблокированными и ждут окончания операции ввода-вывода. Таким образом, при наличии только одной очереди диспетчер не может просто выбрать для выполнения первый процесс из очереди. Перед этим он должен будет просмотреть весь список, отыскивая незаблокированный процесс, который находится в очереди дольше других.
Естественнее было бы разделить все не выполняющиеся процессы на два типа: готовые к выполнению и заблокированные. Такая схема показана на рис. 3.3. Здесь добавлены еще два состояния, которые окажутся полезными в дальнейшем. Опишем каждое из пяти состояний процессов, представленных на диаграмме.
Выполняющийся. Процесс, который выполняется в текущий момент времени. В настоящей главе предполагается, что на компьютере установлен только один процессор, поэтому в этом состоянии может находиться только один процесс.
Готовый к выполнению. Процесс, который может быть запущен, как только для этого представится возможность.
Блокированный. Процесс, который не может выполняться до тех пор, пока не произойдет некоторое событие, например завершение операции ввода-вывода.
Новый. Только что созданный процесс, который еще не помещен операционной системой в пул выполнимых процессов. Обычно это новый процесс, который еще не загружен в основную память.
Завершающийся. Процесс, удаленный операционной системой из пула выполнимых процессов.
Рис. 3.3. Модель с пятью состояниями
Состояния "новый" и "завершающийся" представляют собой полезные конструкции для управления процессами. Первое из них соответствует процессу, который был только что определен. Например, если новый пользователь пытается войти в систему с разделением времени или в систему поступает новое пакетное задание, операционная система может определить новый процесс в два этапа. Во-первых, она выполняет всю необходимую рутинную работу: процессу присваивается идентификатор, формируются все необходимые для управления процессом таблицы. В этот период времени процесс находится в состоянии нового. Это означает, что операционная система выполнила необходимые для создания процесса действия, но еще не приготовилась к его запуску. Например, операционная система может иметь ограничения по количеству одновременно выполняющихся процессов. Такие ограничения устанавливаются, например, чтобы не снижать производительность системы (или не переполнять основную память). Таблицы управления новыми процессами с необходимой операционной системе информацией содержатся в основной памяти, однако самих процессов там еще нет, т.е. код программы, которую нужно выполнить, не загружен в память, и данным, относящимся к этой программе, не выделено пространство. Отвечающая такому процессу программа остается во вторичной памяти (обычно это диск).
Выход процесса из системы также происходит в два этапа. Во-первых, процесс переходит в состояние завершающегося при достижении точки естественного завершения, а также когда он останавливается из-за возникновения неустранимой ошибки или когда его останавливает другой процесс, обладающий необходимыми для этого полномочиями. После этого момента процесс больше не может выполняться. Операционная система временно сохраняет таблицы и другую информацию, связанную с этим заданием, так что вспомогательные программы могут получить все необходимые сведения о завершившемся процессе (например, эти данные могут понадобиться программе, ведущей учет использования процессорного времени и других ресурсов). После того как эти программы извлекут всю необходимую информацию, операционной системе больше не нужно хранить данные, связанные с процессом, и он полностью удаляется из системы.
На рис. 3.3 показаны типы событий, соответствующие каждому из возможных переходов из одного состояния в другое. Возможны следующие переходы.
Нулевое состояние —> Новый. Для выполнения программы создается новый процесс. Это событие может быть вызвано однойиз причин, перечисленных в табл. 3.1.
Новый —> Готовый. Операционная система переводит процесс из состояния нового в состояние готового к выполнению, когда она будет готова к обработке дополнительных процессов. В большинстве систем устанавливается ограничение на количество существующих процессов или на объем выделяемой для процессов виртуальной памяти. Таким образом предотвращается снижение производительности, которое может произойти, если будет загружено слишком много активных процессов.
Готовый —> Выполняющийся. Когда наступает момент выбора нового процесса для запуска, операционная система выбирает один из готовых для выполнения процессов. Принцип этого выбора обсуждается в четвертой части книги.
Выполняющийся —> Завершающийся. Если процесс сигнализирует об окончании своей работы или происходит его аварийное завершение, операционная система прекращает его выполнение.
Выполняющийся —> Готовый. Этот переход чаще всего происходит из-за того, что процесс выполняется в течение максимального промежутка времени, отведенного для непрерывной работы одного процесса. Подобная стратегия планирования используется практически во всех многозадачных операционных системах. Такой переход возможен и по некоторым другим причинам, зависящим от конкретной операционной системы. Например, если операционная система назначает разным процессам различные приоритеты, то может случиться так, что процесс будет выгружен из-за появления процесса с более высоким приоритетом. Предположим, что выполняется процесс А, имеющий определенный приоритет, а процесс В, приоритет которого выше, блокирован. Когда операционная система обнаружит, что произошло событие, ожидаемое процессом В, она переведет этот процесс в состояние готовности, в результате чего процесс А может быть прерван и управление перейдет к процессу В. Говорят, что операционная система вытесняет (preempt) процесс А. Наконец, процесс сам по себе может отказаться от использования процессора.
Выполняющийся —> Блокированный. Процесс переводится в заблокированное состояние, если для продолжения работы требуется наступление некоторого события. Посылаемый операционной системе запрос обычно имеет вид вызова какой-нибудь системной службы, т.е. вызова процедуры, являющейся частью кода операционной системы.
Процесс может запросить ресурс (например, файл или совместно используемую ячейку виртуальной памяти), который окажется временно недоступным, и потребуется подождать его освобождения. Кроме того, возможна ситуация, в которой для продолжения процесса требуется выполнить некоторое действие, например операцию ввода-вывода. Если процессы обмениваются информацией друг с другом, один из них может быть блокирован в состоянии ожидания ввода или сообщения от другого процесса.
Блокированный —> Готовый. Заблокированный процесс переходит в состояние готовности к выполнению в тот момент, когда происходит ожидаемое им событие.
Готовый —> Завершающийся. Чтобы не усложнять картину, этот переход на диаграмме состояний не показан. В некоторых системах родительский процесс может в любой момент прервать выполнение дочернего процесса. Кроме того, дочерние процессы могут прекратиться при завершении родительского процесса.
Блокированный —> Завершающийся. См. комментарии к предыдущему пункту.
Возвратимся к нашему простому примеру. На рис. 3.4 показаны переходы каждого из трех рассматриваемых процессов в различные состояния. На рис. 3.5,а предложен один из способов реализации порядка очередности. Имеется две очереди: очередь готовых к выполнению процессов и очередь заблокированных процессов. Каждый процесс, поступающий в систему для обработки, помещается в очередь готовых к выполнению процессов. Когда операционной системе приходит время выбрать для выполнения другой процесс, она выбирает его из этой очереди. Если схема приоритетов отсутствует, эта очередь может работать по принципу "первым вошел — первым вышел".
Когда выполнение процесса прерывается, он, в зависимости от обстоятельств, может либо завершиться, либо попасть в одну из двух очередей (готовых к выполнению или блокированных процессов). И, наконец, после того как произойдет событие, все ожидающие его процессы из очереди заблокированных перемещаются в очередь готовых к выполнению процессов.
Рис. 3.4. Состояние процессов из листинга 3.2
б) Схема с несколькими очередями блокированных процессов
Рис. 3.5. Модель, представленная на рис. 3.3, с использованием очередей
Такая организация приводит к тому, что после любого события операционная система должна сканировать всю очередь блокированных процессов, отыскивая среди них те, которые ожидают именно этого события. В большой операционной системе в подобной очереди может пребывать несколько сотен или даже тысяч процессов. Поэтому эффективнее организовать несколько очередей, для каждого события — свою. Тогда при каком-то событии все процессы из соответствующей очереди можно будет перевести в очередь готовых к выполнению процессов (см. рис. 3.5,6).
И последнее усовершенствование: если диспетчеризация осуществляется с использованием приоритетов, то было бы удобно организовать несколько очередей готовых к выполнению процессов. В такой схеме каждая очередь соответствовала бы своему уровню приоритета. Тогда операционной системе легко было бы определять готовый для выполнения процесс с наивысшим приоритетом, который ждет своей очереди дольше всех остальных.
