Взаимное исключение и критические участки

Несмотря на то, что физические и логические ресурсы можно использовать совместно, они обычно в каждый момент времени доступны только одному процессу. Ресурс, который допускает обслуживание только одного процесса за один раз, называется критическим ресурсом. Если несколько процессов хотят пользоваться совместно некоторым ресурсом, то им следует синхронизировать свои действия таким образом, чтобы этот ресурс всегда находился в распоряжении не более одного из них (один процесс пользуется ресурсом, остальные ожидают его освобождения). В этом случае говорят, что процессы используют ресурс в режиме взаимногоисключения (mutual exclusion). Если нам удастся избежать одновременного нахождения двух процессов в критических областях, мы сможем избежать состязаний.

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

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

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

1. В любой момент времени только один процесс может находиться внутри критического по отношению к данному ресурсу участка (mutual exclusion).

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

3. Должно существовать ограничение на интервал времени, прошедший от запроса на вход в критический участок до фактического разрешения входа (bounded waiting).

Критические участки могут вкладываться друг в друга, когда требуется одновременный доступ к нескольким ресурсам.

Синхронизация с помощью элементарных приемов нижнего уровня

Запрещение прерываний

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

Переменные блокировки

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

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

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

Строгое чередование

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

Структура процесса выглядит следующим образом:

Repeat

...

while turn<>0 do

no-op;

критический участок

turn:= l;

...

until false;

Структура процесса выглядит симметрично

Repeat

...

while turn<>1 do

no-op;

критический участок

turn:= 0;

...

until false;

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

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

Неожиданно процесс 0 завершает работу вне критической области и возвращается к началу цикла. Но на большее он не способен, поскольку значение turn равно 1, и процесс 1 находится вне критической области. Процесс 0 «зависнет» в своем цикле while, ожидая, пока процесс 1 изменит значение turn на 0. Получается, что метод поочередного доступа к критической области не слишком удачен, если один процесс существенно медленнее другого.

Фактически этот метод требует, чтобы два процесса попадали в критические области строго по очереди.

Алгоритм Петерсона

Датский математик Деккер (Т. Dekker) был первым, кто разработал программное решение проблемы взаимного исключения, не требующее строгого чередования.

В 1981 году Петерсон (G. L. Peterson) придумал существенно более простой алгоритм взаимного исключения. С этого момента вариант Деккера стал считаться устаревшим.

Алгоритм Петерсена использует две переменных, разделяемых двумя процессами и :

var turn:integer;

interested: array[0..1] of Boolean;

Переменная turn определяет какому процессу разрешен вход в критический участок. Массив interested используется, для того, чтобы определить, готов ли процесс войти в критический участок.

Исходно оба процесса находятся вне критических областей. Чтобы войти в критический участок процесс сначала устанавливает значение interested равным true, а затем устанавливает переменную turn равной 1- i, чтобы дать возможность другому процессу войти в критический участок, если это тому необходимо.

Repeat

...

j= 1-i;

interested[i]:= true;

turn:= j;

while interested[j] and turn=j do

no-op;

критический участок

interested[i]:= false;

...

until false;

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