ется, что метод поочередного доступа к критической области не слишком удачен, если один процесс существенно медленнее другого.

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

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

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

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

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

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

#define FALSE О #define TRUE 1

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

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

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

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

void enter region(int process): /* Процесс О или 1 */

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

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

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

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

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

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

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

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

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

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

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

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

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

Команда TSL

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

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

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

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

enter region:

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

/* значение переменной устанавливается равным 1 */

стр register.#0 /* Старое значение lock сравнивается с нулем */

jne enter region /* Если оно ненулевое, значит, блокировка уже была */ /* установлена, поэтому цикл */

ret /* Возврат в вызывающую программу */

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

leave region:

move 1оск.#0 /* Сохранение О в переменной lock */

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

2.2.4. Примитивы межпроцессного взаимодействия

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

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

Теперь рассмотрим некоторые примитивы межпроцессного взаимодействия, применяемые вместо циклов ожидания (в которых лишь напрасно расходуется процессорное время). Эти примитивы блокируют процессы в случае запрета на вход в критическую область. Одной из простейших является пара примитивов sleep и wakeup. Примитив sleep - системный запрос, в результате которого вызывающий процесс блокируется, пока его не запустит другой процесс. Запрос wakeup ожидает один аргумент - идентификатор запускаемого процесса. Также