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

Используя сочетание идеи очередности с идеей блокирующих и предупреждающих переменных, голландский математик Деккер (T. Dekker) стал первым, кто придумал программное решение проблемы взаимного исключения, не требующее четкой очередности.
Обсуждение алгоритма Деккера приведено в книге Дейкстры (Dijkstra, 1965). В 1981 году Петерсон придумал гораздо более простой способ достижения взаимного исключения, которое перевело решение Деккера в разряд устаревших. Алгоритм Петерсона показан в листинге 2.2. Этот алгоритм состоит из двух процедур, написанных на ANSI C, а это значит, что для всех определенных и используемых функций должны
быть предоставлены функции-прототипы. Но в целях экономии места мы не будем показывать прототипы ни в этом, ни в последующих примерах.

Листинг 2.2. Решение Петерсона, позволяющее добиться взаимного исключения #define FALSE 0

#define TRUE 1

#define N 2 /*

int turn; /*

int interested[N]; /*

void enter_region(int process); /*

{

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 не выйдет из своей критической области.

<< | >>
Источник: Э. ТАНЕНБАУМ Х. БОС. СОВРЕМЕННЫЕ ОПЕРАЦИОННЫЕ СИСТЕМ Ы 4-е ИЗДАНИЕ. 2015

Еще по теме Алгоритм Петерсона:

  1. МЕТОДИКА ПЕТЕРСОНОВ
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. АЛГОРИТМ
  4. АЛГОРИТМ УДАЧИ
  5. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  6. Алгоритм исцеления:
  7. Алгоритм избавления от боли
  8. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  9. Алгоритм обработки результатов.
  10. 2. Специфика и алгоритмы работы с источниками.
  11. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  12. 2. ИСТОЧНИКИ ИНФОРМАЦИИ. СПЕЦИФИКА И АЛГОРИТМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ. ДОСТУП К ИСТОЧНИКАМ ИНФОРМАЦИИ. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ.
  13. ЗАДАЧА: РЕШЕНИЕ
  14. Переживание
  15. Переживание
  16. Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание, 2007
  17. Замечания по структуре материала
  18. Прием структуризации психологического портрета.
  19. Работа с собой
  20. Работа с собой