Листинг 5.3. Алгоритм Петерсона для двух процессов

boolean flag[2];

int turn;

void P0()

{

while(true)

{

flag[0] = true;

turn = 1;

while(flag[l] && turn == 1)

/* Ничего не делать */;

/* Критический раздел */;

flag[0] = false;

/* Остальной код */;

}

}

void P1()

{

while(true)

{

flag[1] = true;

turn = 0;

while(flag [0] && turn == 0)

/* Ничего не делать */;

/* Критический раздел */;

flag[l] = false;

/* Остальной код */;

}

}

void main()

{

flag[0] = false;

flag[l] = false;

parbegin(P0,Pl);

}

Выполнение условий взаимоисключения легко показать. Рассмотрим процесс Р0. После того как flag[0] установлен им равным true, P1 войти в критический раздел не может. Если же Р1 уже находится в критическом разделе, то flag[l] = true и для Р0 вход в критический раздел заблокирован. Однако взаим­ная блокировка в данном алгоритме предотвращена. Предположим, что Р0 заблоки­рован в своем цикле while. Это означает, что flag[l] равен true, a turn = 1. Р0 может войти в критический раздел, когда либо flag[l] становится равным false, либо turn становится равным 0. Рассмотрим три исчерпывающих случая.

1. Р1 не намерен входить в критический раздел. Такой случай невозможен, поскольку при этом выполнялось бы условие flag[l] = false.

2. PI ожидает вход в критический раздел. Такой случай также невозможен, поскольку если turn = 1, то Р1 способен войти в критический раздел.

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

Следовательно, у нас имеется простое решение проблемы взаимных исклю­чений для двух процессов. Впрочем, алгоритм Петерсона легко обобщается на случай п процессов [HOFR90].

5.3. Взаимоисключения: аппаратная поддержка

Отключение прерываний

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

while (true)

{

/* Запрет прерываний */;

/* Критический раздел */;

/* Разрешение прерываний */;

/* Остальной код */;

}

Поскольку критический раздел не может быть прерван, выполнение взаи­моисключения гарантируется. Однако цена такого подхода высока. Эффектив­ность работы может заметно снизиться, поскольку при этом ограничена возмож­ность процессора по чередованию программ. Другая проблема заключается в том, что такой подход не будет работать в многопроцессорной архитектуре. Если вычислительная система включает несколько процессоров, то вполне возможно (и обычно так и бывает), что одновременно выполняются несколько процессов. В этом случае запрет прерываний не гарантирует выполнения взаимоисключений.