Управление процессами

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

Рис. 7.3. Производительность однопрограммной (а) и мультипрограммной (б) системы

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

Производительность системы часто измеряется числом заданий, выполненных за временной интервал; эта величина называется пропускной способностью системы. Чтобы показать, каким образом совмещение обработки и ввода-вывода в режиме ПДП может улучшить пропускную способность системы, рассмотрим два процесса. Типичные действия однопрограммной системы показаны на рис. 7.3,а. Процесс 1 начинается и продолжается до точки А, где ему потребовался ввод-вывод. Здесь инициируется ввод-вывод, а обработка продолжается параллельно с ним до тех пор, пока для обработки не потребовались входные данные (точка В); ЦП должен ожидать завершения ввода-вывода. Обработка возобновляется, когда ввод-вывод закончен (точка С). Аналогичная ситуация возникает в точках D, Е и F. По окончании процесса 1 начинается процесс 2; он выполняется также, как и процесс 1. Кроме "перемешивания" нескольких действий ввода-вывода, мультипрограммная система может одновременно обслуживать нескольких пользователей. Пользователи поочередно управляют ЦП, когда каждому из них выделяется временной квант — получается система с разделением времени.

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

1. Выполнение процесса. Процесс выполняется центральным процессором.

2. Блокировка. Выполнение процесса продолжать невозможно, так как он ожидает появления некоторого события, например завершения операции ввода-вывода.

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

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

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

Рис. 7.4. Смена состояний процесса во времени

Реализация очереди процессов, находящихся в состоянии готовности, зависит от стратегии планирования. Простейшая стратегия «первый пришел, первый вышел» (FIFO) назначает всем процессам одинаковые приоритеты и всегда выбирает для выполнения процесс, который находится в очереди дольше всех. Структура списка готовности, опирающаяся на планирование FIFO и связанный список, представлена на рис. 7.5. Указатель первого элемента показывает, какой процесс находится в вершине очереди, а указатель последнего элемента — процесс в низу очереди. Указатель последнего элемента необходим для того, чтобы в очередь можно было помещать новые процессы без просмотра всего списка. В примере предполагается, что каждый процесс имеет ID (идентификатор), который совпадает с позицией в массиве, содержащем связанный список. Предполагается также, что очередь состоит из процессов 3, 6, 2, 8 и 5 (именно в таком порядке). Следовательно, указатель первого элемента содержит 3, указатель последнего элемента содержит 5, а процессы 2, 3, 5, 6 и 8 находятся в состоянии готовности. Остальные элементы в таблице процессов либо заняты выполняемыми или заблокированными процессами, либо в данное время не используются. Если число 0 применяется для указания конца списка, его нельзя употреблять в качестве ID процесса. Если ID процессов представлены одним байтом и не может быть процесса 0, то максимальное число процессов, которые могут находиться в системе одновременно, равно 255.

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

Рис. 7.5. Структура очереди процессов

Когда ЦП переключается с одного выполняющегося процесса на другой, монитор должен:

1. Запомнить машинное состояние выполняемого процесса в управляющем блоке процесса.

2. Модифицировать остальную часть блока управления процесса.

3. Взять ID следующего выполняемого процесса из указателя первого элемента.

4. Удалить процесс, только что переведенный в состояние выполнения, посредством установки указателя первого элемента равным fqp удаляемого элемента. Если текущая выполняемая программа должна быть в очереди процессов, находящихся в состоянии готовности, ее необходимо поместить в низ очереди и модифицировать указатель последнего элемента.

5. Изменить состояние процесса, только что выбранного из списка готовности, на состояние выполнения и восстановить машинное состояние данного процесса.

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

1. Сохранить ID этого процесса в ftp текущего последнего элемента (элемента, адресуемого указателем последнего элемента) и в указатель последнего элемента.

2. Сбросить fqp в элементе таблицы данного процесса.

3. Модифицировать управляющий блок этого процесса.

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

Для выбора следующего выполняемого процесса планировщик должен просматривать приоритетную таблицу, начиная с наивысшего приоритета, до обнаружения ненулевого указателя первого элемента, а затем удалить этот процесс из очереди готовности. Преимущество использования bpq заключается в возможности динамического изменения приоритета данного процесса. Предположим, что приоритет процесса x необходимо изменить на приоритет y. Сначала процесс x удаляется из его текуoей приоритетной цепочки с помощью следующих операций:

fqp(bqp(x)) <- fqp(x),

bqp(fqp(x)) <- bpq(x)

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

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