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

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

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

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

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

Третий метод реализации взаимного исключения иллюстрирован на рис. 2.6. Этот фрагмент программного кода, как и многие другие в данной книге, написан на С. Язык С был выбран, поскольку практически все существующие операцион­ные системы написаны на С (или C++), а не на Java, Modula 3, Pascal и т. п. Язык С обладает всеми необходимыми свойствами для написания операцион­ных систем: это мощный, эффективный и предсказуемый язык программирова­ния. А язык Java, например, не является предсказуемым, поскольку у програм­мы, написанной на нем, может в критический момент закончиться свободная память, и она вызовет «сборщика мусора» в исключительно неподходящее вре­мя. В случае С это невозможно, поскольку в С процедура «сбора мусора» в прин­ципе отсутствует.

Рис. 2.6. Предлагаемое решение проблемы критической области: а — процесс 0; б — процесс 1. В обоих случаях необходимо удостовериться в наличии

точки с запятой, ограничивающей цикл while

На рис. 2.6 целая переменная 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. Получается, что метод поочередного доступа к критической области не слишком удачен, если один процесс существенно медленнее другого.

Эта ситуация нарушает третье из сформулированных нами условий: один про­цесс блокирован другим, не находящимся в критической области. Возвратимся к примеру с каталогом спулера: если заменить критическую область процедурой считывания/записи в каталог спулера, процесс 0 не сможет послать файл на пе­чать, поскольку процесс 1 занят чем-то другим.

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

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

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

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

Листинг 2.1. Решение Петерсона для взаимного исключения

#define FALSE О #define TRUE 1

#define N 2 /* Количество процессов */

int turn: /* Чья сейчас очередь? */

int interested[N]: /* Все переменные изначально

/* равны О (FALSE) */

void enter_region(int process): /* Процесс 0 или 1 */

{

int other: /* Номер второго процесса */

other = 1 - process: /* "противоположный" процесс */

interested[process] = TRUE: /* Индикатор интереса */

turn = process: /* Установка флага */

while (turn == process && interested[other] == TRUE) /* Пустой цикл */;

}

void leave__region(int process) /* Процесс, покидающий

/* критическую область */

{

interested[process] = FALSE: /* Индикатор выхода из

/* критической области */

}

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

Рассмотрим работу алгоритма более подробно. Исходно оба процесса нахо­дятся вне критических областей. Процесс 0 вызывает enter_region, задает элемен­ты массива и устанавливает переменную turn равной 0. Поскольку процесс 1 не заинтересован в попадании в критическую область, происходит возврат из про­цедуры. Теперь, если процесс 1 вызовет enter_region, ему придется подождать, пока interested [0] примет значение FALSE, а это произойдет только в тот момент, когда процесс 0 вызовет процедуру leave_region при покидании критической об­ласти.

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

Команда TSL

Рассмотрим решение, требующее участия аппаратного обеспечения. Многие компьютеры, особенно разработанные с расчетом на несколько процессоров, имеют команду Test and Set Lock (TSL) — «проверить и заблокировать», которая действует следующим образом. В регистр считывается содержимое слова памя­ти, а затем в этой ячейке памяти сохраняется ненулевое значение. Гарантирует­ся, что операция считывания слова и сохранения неделима — другой процесс не может обратиться к слову в памяти, пока команда не выполнена. Процессор, вы­полняющий команду tsl, блокирует шину памяти, препятствуя обращениям к па­мяти со стороны остальных процессоров.

Воспользуемся командой tsl. Пусть разделяемая переменная lock управляет доступом к общей памяти. Если значение lock равно 0, любой процесс может из­менить его на 1 и обратиться к общей памяти, а затем вернуть его обратно в 0, пользуясь обычной командой типа move.

Как использовать команду tsl для реализации взаимного исключения? Реше­ние приведено в листинге 2.2. Здесь представлена подпрограмма из четырех ко­манд, написанная на некотором обобщенном (но типичном) ассемблере. Первая команда копирует старое значение lock в регистр и затем устанавливает значение переменной в 1. Потом старое значение сравнивается с нулем. Если оно ненуле­вое, значит, блокировка уже была произведена, и проверка начинается сначала. Рано или поздно значение окажется нулевым (это означает, что процесс, нахо­дившийся в критической области, покинул ее), и подпрограмма вернет управле­ние в вызвавшую программу, установив блокировку. Сброс блокировки не пред­ставляет собой ничего сложного — просто помещается 0 в переменную lock. Специальной команды процессора не требуется.

Листинг 2.2. Вход и выход из критической области с помощью команды tsl

enter_region:

tsl register.lock /* значение lock копируется в регистр */

/* значение переменной устанавливается равным 1 */ cmp register.#0 /* Старое значение lock сравнивается с нулем */ jne enter_region /* Если оно ненулевое, значит, блокировка уже была */

/* установлена, поэтому цикл */
ret /* Возврат в вызывающую программу */

/* процесс вошел в критическую область */ leave_region;

move lock.#0 /* Сохранение 0 в переменной lock */ ret

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