Лекция: Взаимное исключение с активным ожиданием

Активное ожидание — это постоянная проверка значения переменной в ожидании некоторого значения.

Спин-блокировка — это блокировка, использую­щая активное ожидание.

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

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

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

— переменные блокировки (программное решение: введение до­полнительной переменной, которая меняет свое значение в зависимости от состояния процесса; недостаток: возможен неверный вывод о состоянии процесса при переключении от одного процесса к другому);

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

— алгоритм Петерсона (Прежде чем обратиться к совместно используемым переменным (то есть перед тем, как войти в критическую область), процесс вызывает процедуру enter_region со своим номером (0 или 1) в качестве параметра. Поэтому процессу при необходимо­сти придется подождать, прежде чем входить в критическую область. После выхода из критической области процесс вызывает процедуру leave_region, чтобы обозначить свой выход и тем самым разрешить другому процессу вход в критическую область)

— Команда TSL

Решение, требующее участия аппаратного обеспечения. Многие ком­пьютеры, особенно разработанные с расчетом на несколько процессоров, имеют команду TSL RX, LOCK

(test and set lock— проверить и заблокировать), которая действует следующим образом. В регистр RX считывается содержимое слова памяти lock, а в ячейке памя­ти lock сохраняется некоторое ненулевое значение. Гарантируется, что операция считывания слова и сохранения неделима — другой процесс не может обратиться к слову в памяти, пока команда не выполнена. Процессор, выполняющий коман­ду ТSL, блокирует шину памяти, чтобы остальные процессоры не могли обратить­ся к памяти.

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

Недостатки:

— Неэффективное использование времени процесса

— проблема инверсии приоритета.

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