Параллельное и распределенное программирование на С++

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

Рис. 3.4. Состояния процессов и переходы между ними в средах UNIX/Linux

Когда процесс только создается, он готов к выполнению своих инструкций, но должен ожидать «своего часа» до тех пор, пока не освободится процессор. Каждому процессу единолично разрешается использовать процессор в течение дискретного временного интервала, именуемого квантом времени (time slice). Процессы, ожидающие использования процессора, «занимают» очередь, т.е. помещаются в очереди готовых процессов. Только из таких очередей планировщик выбирает процесс, который будет использовать процессорное время. Процессы, находящиеся в очередях готовых процессов, пребывают в состоянии работоспособности. Когда процессор становится доступным,

Таблица 3 .1 Переходы процессов из одного состояние в другое

Готовый > выполняющийся (загрузка) Процесс назначается процессору

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

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

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

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

Выполняющийся > остановленный Процесс отказывается от процессора из-за получения им сигнала останова

Остановленный > готовый Процесс получил сигнал продолжать и возвращается назад в очередь готовых процессов

Выполняющийся > «Зомби» Процесс прекращен и ожидает, пока родительский процесс не извлечет из таблицы процессов его статус завершения

«Зомби» > ВЫХОД Родительский процесс извлекает из таблицы процессов статус завершения и процесс-зомби покидает систему

Выполняющийся > ВЫХОД Процесс завершен, но он покидает систему после того как родительский процесс извлечет из таблицы процессов его статус завершения

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

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

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

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

Планирование процессов

Если готовых к выполнению процессов больше одного, планировщик должен определить, какой из них первым назначить процессору. С этой целью планировщик поддерживает структуры данных, которые позволяют наиболее эффективным образом распределять между процессами процессорное время. Каждый процесс получает класс (тип) приоритета и размещается в соответствующей очереди вместе с другими работоспособными процессами того же приоритетного класса. Поэтому существует несколько приоритетных очередей, которые представляют различные классы приоритетов, используемые системой. Эти приоритетные очереди упорядочиваются и помещаются в массив распределения, именуемый также многоуровневой приоритетной очередью (multilevel priority queue), показанной на рис. 3.5 . Каждый элемент этого массива связан с конкретной приоритетной очередью. Для выполнения процессором планировщик назначает тот процесс, который стоит в головной части непустой очереди, имеющей самый высокий приоритет.

Приоритеты могут быть динамическими или статическими. Однажды установленный статический приоритет процесса изменить нельзя, а динамические — можно. Процессы с самым высоким приоритетом могут монополизировать использование процессора. Если же приоритет процессора динамический, то его начальный уровень может быть заменен более высоким значением, в результате чего такой процесс будет переведен в очередь с более высоким приоритетом. Кроме того, процесс, который монополизирует процессор, может получить более низкий приоритет, или же другие процессы могут получить более высокий