| Предыдущий раздел | Оглавление | Следующий раздел |
3.3.3.3. Алгоритм Петерсона
В 1981 году Петерсон придумал гораздо более простой способ достижения взаимного исключения, которое перевело решение Деккера в разряд устаревших. Алгоритм Пе¬терсона показан в листинге 3.1.
Листинг 3.1. Решение Петерсона, позволяющее добиться взаимного исключения
#define FALSE 0
#define TRUE 1
#define N 2 /* количество процессов */
int turn; /* чья очередь? */
int interested[N]; /* все исходные значения равны 0 (FALSE) */
void enter_region(int process); /* 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 заинтересованности во входе в критическую область не проявил, функция enter_region тотчас же возвращает управление. Теперь, если про-цесс 1 вызовет функцию enter_region, он зависнет до тех пор, пока interested[0]не получит значение FALSE, а это произойдет только в том случае, если процесс 0 вызовет функцию leave_region, чтобы выйти из критической области.
Теперь рассмотрим случай, когда оба процесса практически одновременно вызывают функцию enter_region. Оба они будут сохранять свой номер процесса в переменной turn. В расчет берется последнее сохранение, поскольку первое будет переписано и утрачено. Предположим, что процесс 1 сохранил свой номер последним и turn имеет значение 1. Когда оба процесса доберутся до оператора while, процесс 0 не выполнит его ни одного раза и войдет в свою критическую область. Процесс 1 войдет в цикл и не будет входить в свою критическую область до тех пор, пока процесс 0 не выйдет из своей критической области.
Однако алгоритм Петерсона имеет один недостаток — необходимость пребывания в режиме активного ожидания. По сути это решение сводится к следующему: когда процессу требуется войти в критическую область, он проверяет, разрешен ли этот вход. Если вход запрещен, процесс просто входит в короткий цикл, ожидая разрешения.
Этот подход не только приводит к пустой трате процессорного времени, но и может иметь совершенно неожиданные эффекты. Рассмотрим компьютер с двумя процессами: H с высокой степенью приоритета и L с низкой степенью приоритета. Правила планирования их работы предусматривают, что H выполняется сразу же после входа в состояние готовности. В определенный момент, когда L находится в критической области, H входит в состояние готовности (к примеру, после завершения операции ввода-вывода). Теперь H входит в режим активного ожидания, но поскольку, пока вы¬полняется процесс H, выполнение L не планируется, у L не остается шансов выйти из своей критической области, поэтому H пребывает в бесконечном цикле. На подобную ситуацию иногда ссылаются как на проблему инверсии приоритета.
| Предыдущий раздел | Оглавление | Следующий раздел |