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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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