Подобно каждому гражданину в известный, ныне ушедший в прошлое
период нашей истории, каждый процесс всю свою жизнь проводит в
очередях. Для управления процессами ОС организует следующие
очереди:
Очередь заданий (job queue)– содержит множество всех процессов в
системе. В нее попадает каждый новый процесс и остается в ней в
течение всего пребывания в системе. Очередь готовых процессов
(ready queue)– наиболее часто используемая и изменяемая очередь,
содержащая множество всех процессов, находящихся в основной памяти
и готовых к выполнению. В нее попадает каждый новый процесс,
который система допускает к выполнению, а также каждый процесс
после выполнения ввода-вывода или наступление ожидаемого события.
Очереди процессов, ожидающих ввода-вывода (device queues)–
множества процессов, ожидающих результата работы устройств
ввода-вывода (для каждого устройства организуется своя очередь).
Управление процессами операционной системой и поведение процессов в
системе можно рассматривать как миграцию между различными
очередями.
На рис. 8.4 изображена схема организации очереди готовых процессов
и очередей к устройствам ввода-вывода.
Рис. 8.4. Очередь готовых процессов и очереди к устройствам
ввода-вывода.
Как видно из схемы, в очереди готовых процессов находятся те
процессы, ввод-вывод в которых завершен. Процессы, выполняющие
ввод-вывод или ждущие возможности его выполнить (освобождения
соответствующего устройства) стоят в очереди к устройству.
Некоторые устройства могут быть свободны, другие – содержать более
одного процесса в очереди. Следует также обратить внимание на
организацию очереди, с точки зрения представления данных. Полезный
прием состоит в том, что для очереди хранится не только ссылка на
начало (голову), но и ссылка на конец (хвост), что позволяет более
эффективно управлять очередями (например, быстро добавить элемент в
конец очереди). Место процесса в очереди определяется его
приоритетом, о котором речь ниже. Более подробно алгоритмы работы с
очередями (как с одной из классических структур данных) описаны в
монографии Д. Кнута [15].
Схема диспетчеризации процессов и работа с очередями представлена
на рис. 8.5.
Рис. 8.5. Графическое представление диспетчеризации процессов.
Из очереди готовых процессов каждый процесс в конце концов попадает
на процессор и выполняется. При выполнении могут возникнуть
следующие ситуации, при которых выполнение приостанавливается:
запрос на синхронный ввод-вывод, исчерпание выделенного процессу
кванта времени, прерывание или создание дочернего процесса. Особого
пояснения требует, пожалуй, лишь последняя ситуация. В классической
схеме UNIX при создании дочернего процесса системным вызовом fork
для дочернего процесса создается новое пространство виртуальной
памяти, в которую копируется содержимое памяти процесса-родителя.
После этого процесс-родитель уступает процессор дочернему процессу.
Подобная схема создания дочернего процесса, разумеется, не всегда
удобна. Стратегии распараллеливания процессов рассмотрены в
следующей лекции.