Проблемы взаимодействия процессов
В конце концов правильные алгоритмы решена задачи взаимного исключения предложили сначала Деккер (его алгоритм довольно запутанный, что часто случается с первыми решениями сложных задач), затем Питерсон, чей алгоритм проще и понятнее.
Для любознательных приводим решение Питерсона. В нем используются булевы переменные flagA, flagB, изначально равные false, и переменная перечисляемого типа turn: A..B.
|
Процесс A: |
Процесс B: |
|
. . . flagA := true; turn := B; while flagB and turn = B do ; (критическая секция A) flagA := false; . . . |
. . . flagB := true; turn := A; while flagA and turn = A do ; (критическая секция B) flagB := false; . . . |
Приведенный алгоритм действительно решает проблему, однако у него есть два существенных недостатка. Во-первых, если в конкуренции за критическую секцию участвуют не два процесса, а три или более, то программа становится очень громоздкой. Во-вторых, решение Питерсона основано на использовании активного ожидания.
Еще одним направлением в реализации взаимного исключения стало включение специальных машинных команд в наборы команд новых процессоров. Поскольку опасность, как мы видели, связана с разделением по времени операций проверки и присваивания, то были предложены команды, выполняющие одновременно проверку и присваивание. Такие команды есть, например, у процессоров Pentium. С их помощью действительно можно проще реализовать взаимное исключение, но для этого все равно требуется активное ожидание.
предыдущаяследующая