Параллельное программирование, взаимное исключение: различия между версиями

''Алгоритм пекарни''. Это один из самых известных и элегантных алгоритмов взаимного исключения, использующий только безопасные регистры [ ]. Алгоритм удовлетворяет требованию FIFO, однако использует регистры неограниченного размера. Его модифицированная версия, называемая черно-белым алгоритмом пекарни, удовлетворяет требованию FIFO и использует ограниченное количество атомарных регистров ограниченного размера [14].

''Нижние границы''. Нижняя граница по памяти при решении задачи о взаимном исключении с использованием только атомарных регистров выглядит следующим образом: любой алгоритм взаимного исключения с отсутствием взаимной блокировки для n процессов должен использовать не менее n совместно используемых регистров [ ]. В работе [5] также было показано, что эта граница является точной. Нижняя граница по времени для любого алгоритма взаимного исключения, использующего атомарные регистры, выглядит следующим образом: не существует априорной границы количества шагов, выполненных процессом во время выполнения кода входа, до того как он войдет в свою критическую секцию (шаги подсчитываются только тогда, когда ни один другой процесс не находится в критической секции или на этапе выполнения кода выхода) [2]. Для задачи о взаимном исключении найдено немало других любопытных границ.

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