в систему, для него запускается оболочка, способная выполнять пользовательские команды. Эти команды могут, в свою очередь, запускать новые процессы и т. д. Таким образом, все процессы в системе образуют единое дерево, корнем которого является процесс init.

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

Несмотря на то что процесс является независимым объектом, со своим счетчиком команд и внутренним состоянием, существует необходимость его взаимодействия с другими процессами. Например, выходные данные одного процесса могут служить входными данными для другого процесса. В команде оболочки cat chapterl chapter2 chapters grep tree

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

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

1. Активный (в этот конкретный момент использующий процессор).

2. Готовый к работе (процесс временно приостановлен, чтобы позволить выполняться другому процессу).

3. Заблокированный (процесс не может быть запущен прежде, чем произойдет некое внешнее событие).

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

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

НИИ из канала или специального файла (предположим, терминала) входные данные не были обнаружены.

1. Процесс блокируется, ожидая входных данных

2. Планировщик выбирает другой процесс

3. Планировщик выбирает этот процесс

4. Доступны входные данные

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

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

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

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

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

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

Процессы

Рис. 2.3. Нижний уровень операционной системы отвечает за прерывания и планирование. Выше расположены логически упорядоченные процессы

2.1.2. Реализация процессов

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

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

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