Диспетчеры операционных систем

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

Для того чтобы управление процессами было возможным, каждому процессу присваивается индивидуальный номер — идентификатор процесса. Вся информация, характеризующая процесс, помещается в специально отведенной области памяти, называемой блоком управления процессом (PCB, Process Control Block), рис. 1.

Рис. 1.

В состав PCB входят следующие данные:

• идентификатор процесса;
• состояние процесса;
• список ресурсов, выделенных процессу;
• другие данные, характеризующие процесс (адрес текущей команды, копия содержимого регистров процессора и т.п.).

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

Рис. 2.

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

Диспетчер процессов представляет собой программу (процесс), входящую в состав операционной системы. В распоряжении диспетчера имеется информация обо всех процессах, существующих в системе в данный момент (рис. 3).

Рис. 3.

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

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

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

Диспетчер активизируется таймером через заданные промежутки времени (рис. 4).

Рис. 4.

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

1. Перевод процессов из состояния блокировки в состояние готовности. Диспетчер анализирует список событий и определяет, какой из процессов можно перевести из состояния блокировки в состояние готовности в соответствии с каждым событием. Каждое событие связано с освобождением или занятием некоторого ресурса и при его наступлении процесс, ожидающий предоставления этого ресурса, может быть переведен в состояние готовности, если необходимый ему ресурс освободился. Если несколько процессов находятся в ожидании одного и того же ресурса, применяется схема приоритетов, позволяющая выбрать из конкурирующих процессов процесс с наивысшим приоритетом и перевести в состояние готовности именно его. Например, если один из заблокированных процессов ожидает сигнала готовности от ведомого устройства (случай асинхронного обмена), при обнаружении события поступления этого сигнала в списке событий диспетчер переводит этот процесс в состояние готовности. Перевод в состояние готовности заключается в то, что:
• Изменяется состояние процесса в PCB этого процесса (с L на R).
• Идентификатор этого процесса изымается из списка заблокированных процессов и помещается в список процессов, находящихся в состоянии готовности.
2. Перевод процессов из состояния готовности в активное состояние. Для всех процессов, находящихся в состоянии готовности, определяется приоритет. Процесс с максимальным приоритетом переводится в активное состояние (начинает выполняться на процессоре). Процесс, бывший до этого активным, переводится в состояние готовности и помещается в список готовых процессов. Определение приоритетов процессов происходит в соответствии с одной из типовых схем, например наибольший приоритет получает процесс, дольше всего находившийся в состоянии готовности (дольше всего не исполнявшийся) или использовавший суммарно наименьшее количество процессорного времени. Перевод процесса в активное состояние заключатся в следующем:
• Изменяется состояние процесса в PCB этого процесса (с R на A).
• Идентификатор этого процесса изымается из списка процессов, находящихся в состоянии готовности.

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

Понятие асинхронных процессов

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

Задача синхронизации асинхронных процессов возникает в следующих случаях:

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

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

Решение задачи синхронизации

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

Если процесс 1 начал выполнение своего критического участка (КУ), процесс 2 не должен начинать выполнение своего КУ до завершения первым процессом выполнения КУ. Такая ситуация получила название задачи взаимоисключения.

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

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

Следовательно, необходимо создание более гибких механизмов синхронизации. Попробуем познакомиться с такими механизмами на нескольких примерах. Сделаем следующие допущения:

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

В приведенных ниже примерах конструкция

означает, что процедуры Proc1 и Proc2 выполняются в двух параллельных потоках, принадлежащих двум асинхронным процессам.

Пример 1

Процедура (подпрограмма) Proc1 выполняется процессом 1, процедура Proc2 — процессом 2. Собственно критический блок представлен процедурами (подпрограммами) CrBlock1 для процесса 1 и CrBlock2 для процесса 2. Так как процессы должны знать, что один из них вошел в свой критический блок, вводится глобальная (доступная обоим процессам) переменная ProcNum, которая, по сути дела, определяет номер процесса, имеющего право на вход в КУ. Цикл {*} представляет собой проверку разрешения на вход в КУ. Если данному процессу вход запрещен, процесс ожидает в этом цикле до установки переменной ProcNum в разрешающее значение.

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

Пример 2

В прим. 2 каждый процесс имеет свою глобальную переменную, сообщающую о нахождении процесса в своем критическом блоке. Процесс, перед входом в критический блок, проверяет, не находится ли другой процесс уже внутри своего критического блока. Если находится — ждет, пока тот закончит выполнение КУ. Такая схема синхронизации является гибкой, так как процессы могут выполнять свои критические блоки в произвольном порядке (но не одновременно!).

Данный вариант механизма синхронизации имеет один серьезный недостаток. Так как процессы асинхронны, они оба одновременно могут подойти к выполнению строки {*}, выполнить проверку, увидеть, что конкурирующий процесс не выполняет критический блок и начать выполнение своего критического блока. То есть при одновременном выполнении процессами операции {*}, оба процесса одновременно входят в КУ и взаимоисключающая синхронизация нарушается.

Для выхода из создавшегося положения можно поменять местами операции {*} и {**}. Тогда процесс будет сигнализировать конкуренту о намерении выполнить КУ еще до проверки.

Пример 3

В случае прим. 3 возможны проблемы, так как оба процесса могут одновременно подойти к выполнению строки {**}, одновременно установить переменные CrB1 и CrB2 в True, а затем при выполнении строки {*} будет происходить бесконечное ожидание процессами друг друга (так называемый deadlock — взаимная блокировка).

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

Пример 4

Этот вариант предусматривает, что при намерении войти в КУ процесс сигнализирует конкуренту об этом. И если конкурент также пытается войти в КУ или находится в нем, "уступает" ему дорогу, вводя на случайное время задержку своего исполнения и сбросив на это время флаг Enter, сигнализирующий о намерении войти в КУ.

Вышеприведенная схема также не лишена недостатков. Если оба процесса одновременно подходят к выполнению строки {*} (а это вполне возможно в силу асинхронности выполнения процессов), они опять войдут в состояние взаимной блокировки, бесконечно "уступая" дорогу друг другу. Попробуем решить и эту проблему, введя приоритет, указывающий, какой из процессов должен "уступить" при попытке одновременного входа в КУ.

Пример 5

Последний пример, по сути дела, аналогичен прим. 4 за исключением того, что вводится новая глобальная переменная Pr_Choice. В случае если оба процесса одновременно подходят к своему КУ и сообщают о намерении войти в него, значение Pr_Choice определяет, какой из процессов "пропускает" конкурента при входе в КУ. Для того чтобы оба процесса имели равные права на вход в КУ, после выполнения КУ каждый процесс меняет приоритет, предоставляя в следующий раз другому процессу право на приоритетный вход в КУ.

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

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

Как правило, операционная система предоставляет процессам определенные средства для организации синхронизации. Наиболее распространенным из подобных средств являются семафоры.

Семафорная техника синхронизации асинхронных процессов

Семафор — специальный объект операционной системы, над которым определены две базовые операции: операция закрытия и операция открытия. Семафорный объект может быть доступен одновременно нескольким процессам (это обеспечивается операционной системой) и в этом смысле он представляет собой разделяемый ресурс.

Основой семафора является семафорная переменная S, которая в случае простейшего (двоичного) семафора может принимать значения 0 или 1. Значение 0 соответствует "закрытому" состоянию семафора, значение 1 — "открытому". Операции закрытия и открытия семафора изменяют значение семафорной переменной.

Действия, выполняемые операцией закрытия семафора:

1. Проверить значение семафорной переменной S.
2. Если S=1 (семафор открыт), присвоить S значение 0 ("закрыть" семафор).
3. Если S=0 (семафор уже закрыт), перевести процесс, пытающийся закрыть семафор, в состояние ожидания (состояние блокировки).

Действия, выполняемые операцией открытия семафора:

1. Если в списке заблокированных процессов находится процесс, ожидающий открытия данного семафора, перевести этот процесс в состояние готовности.
2. Если в списке заблокированных процессов нет процесса, ожидающего открытия данного семафора, присвоить S значение 1 ("открыть" семафор)

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

Как же используются семафоры? Посмотрим на следующий пример. Пусть Sem — объект типа "семафор", предоставленный операционной системой. Sem.Open — операция открытия семафора, Sem.Close — операция закрытия.

Пример 1

Как видно, техника использования семафоров предельно проста. Перед входом в КУ процесс закрывает семафор. При этом все другие процессы "засыпают" на закрытом семафоре при входе в свои КУ. После выхода из КУ процесс открывает семафор, давая возможность "заснувшим на входе" процессам войти в свои КУ.

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

Мониторы операционных систем

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

Рис. 1.

На входе в монитор решается задача взаимоисключения. Только один процесс может попасть в монитор в данный момент времени.

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

Рис. 2.

Пусть процесс претендует на использование ресурса . обращается к соответствующей процедуре Procedure L. При таком обращении возможны два варианта.

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

Рис. 3.

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

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

Condition — переменная, значение которой определяется тем, к какому ресурсу пытался получить доступ процесс . В соответствии с этим значением процедура Wait заносит процесс в ту или иную очередь.

Таким образом, процедура Wait выполняет следующие действия:

1. Вывод процесса из монитора.
2. Занесение идентификатора процесса в список процессов, ожидающих ресурса .
3. Перевод процесса в состояние блокировки (ожидания).

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

Рис. 4.

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

Процедура помечает ресурс как свободный и вызывает глобальную процедуру монитора

Процедура Signal выполняет следующие действия:

1. Выводит процесс из монитора.
2. Если очередь на получение данного ресурса не пуста, из нее, в соответствии с определенными правилами и приоритетами выбирается один из процессов и переводится в состояние готовности, получая при этом в свое распоряжения запрашиваемый ресурс. Ресурс помечается как занятый (рис. 5).

Рис. 5.

Рассмотрим пример простейшего монитора, осуществляющего распределение ресурсов.

Монитор работает в полном соответствии с описанной нами выше логикой. Данный простейший пример монитора обеспечивает доступ к одному ресурсу. Соответственно, имеются две процедуры: для запроса ресурса (Get_Res) и для освобождения ресурса (Put_Res). Глобальная процедура Res_busy фиксирует текущее состояние ресурса (занят или свободен), переменная Res_free является идентификатором ресурса, используемым в глобальных процедурах Wait и Signal для помещения процесса в соответствующую очередь ожидания ресурса (сами глобальные процедуры в нашем примере не рассматриваются).

Для захвата ресурса процесс вызывает процедуру Get_Res. Происходит проверка свободности ресурса, если он свободен — помечается как занятый и процесс выводится их монитора, получая ресурс в свое распоряжение. Если ресурс занят, вызывается глобальная процедура Wait, помещающая ресурс в очередь и переводящая его в состояние блокировки. Процесс, переведенный в состояние блокировки "засыпает" на выполнении процедуры Wait.

Для освобождения ресурса процесс вызывает процедуру Put_Res. Ресурс помечается как свободный, вызывается процедура Signal для опроса очереди ожидающих процессов и возможного перевода одного из них в состояние готовности.

Применение монитора для решения задачи "читатели-писатели"

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

Рис. 1.

Таким образом, мы имеем несколько процессов, записывающих информацию с общее ЗУ и несколько процессов, читающих информацию из общего ЗУ. Процессы первого типа получили название "процессов-писателей", процессы второго типа — "процессов-читателей". Процессы-писатели получают данные с датчиков и записывают в ЗУ, процессы-читатели читают данные из ЗУ и используют их для решения задачи управления.

Совершенно очевидно, что все процессы обращаются к общему ресурсу — ЗУ. Следовательно, должна быть предусмотрена их синхронизация. Правила синхронизации следующие:

• Не допускается одновременное обращение к ЗУ читателей и писателей.
• Только один процесс-писатель может иметь доступ к ЗУ в определенный момент времени.
• Несколько процессов-читателей могут иметь доступ к ЗУ в определенный момент времени.

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

Пример 1

По сути дела, в этом мониторе доступ по чтению и записи в ЗУ рассматриваются как два отдельных ресурса. Соответственно, мы имеем две пары процедур: Start_Read и Finish_Read для доступа по чтению, Start_Write и Finish_Write для доступа по записи.

Глобальные переменные:

• Read_Perm — идентификатор ресурса "доступ к ЗУ по чтению";
• Write_Perm — идентификатор ресурса "доступ к ЗУ по записи";
• Read_Queue — признак того, что в очередь процессов, ожидающих доступа по чтению, не пуста;
• Write_Queue — признак того, что в очередь процессов, ожидающих доступа по записи, не пуста;
• Somb_Write – признак того, что кто-то из процессов-писателей осуществляет запись в ЗУ в данный момент;
• Readers — количество процессов-читетелей, имеющих доступ к ЗУ в данный момент

Процедуры монитора:

• Start_Read. Вызывается процессом-читаталем при попытке получить доступ к ресурсу (ЗУ). Если в этот момент доступ имеет какой-либо процесс-писатель или хотя бы один процесс-писатель стоит в очереди, процесс-читатель, вызвавший эту процедуру, помещается в очередь и блокируется (глобальной процедурой Wait). Если же никто не пишет и не хочет писать, количество читателей (Readers) увеличивается на 1 и процесс получает доступ. Таким образом, данная процедура обеспечивает процессам-писателям приоритет в получении доступа к ресурсу.
• Finish_Read. Вызывается процессом-читаталем, закончившим чтение и желающим освободить ресурс. Уменьшает на 1 количество читателей (Readers), и если оно стало равно 0 (т.е. никто больше не читает), через глобальную процедуру Signal делается попытка предоставить доступ на запись какому-либо процессу-писателю, находящемуся в соответствующей очереди.
• Start_Write. Вызывается процессом-писателем при попытке получить доступ к ЗУ (ресурсу) для записи. Процедура разрешает доступ только если никто не читает (Readers=0) и никто не пишет (Somb_Write=False). В противном случае процесс-писатель, вызвавший эту процедуру, помещается в очередь и блокируется (глобальной процедурой Wait).
• Finish_Write. Вызывается процессом-писателем, закончившим запись и желающим освободить ресурс. После освобождения ресурса (Somb_Write:=False) проверяется, стоит ли какой-либо процесс в очереди на чтение. Если да — делается попытка перевести его в состояние ожидания через глобальную процедуру Signal, предоставив в его распоряжение ресурс. Если нет — через ту же процедуру Signal один из процессов писателей, находящихся в очереди, переводится в состояние готовности и получает ресурс.

Данный монитор обеспечивает приоритет "писателей" над "читателями". Это необходимо для того, чтобы вся информация, полученная "писателями" с датчиков, была записана в ЗУ. С другой стороны, ни один "читатель" не пропустит информацию, выданную ему "писателем".