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

• ''Сравнение и перестановка'': принимает регистр r и два значения – новое и старое. Если текущее значение регистра r равно старому, то значением r становится новое и возвращается «true»; в противном случае значение r остается неизменным и возвращается «false».

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

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

Быстрый алгоритм. При выполнении быстрого алгоритма взаимного исключения в отсутствие конкуренции требуется только константное количество обращений к общей памяти в виде совместно используемых регистров – для входа в критическую секцию и выхода из нее. В работе [10] описан быстрый алгоритм взаимного исключения в ситуации наличия конкуренции; в нем процесс-победитель должен проверить статус всех остальных n процессов, прежде чем ему будет позволено войти в свою критическую секцию. Естественным образом возникает вопрос – можно ли улучшить вышеупомянутый алгоритм в случае наличия конкуренции.

Адаптивные алгоритмы. Поскольку другие процессы-соперники ждут победителя, особенно важно ускорить их вход в критическую секцию благодаря построению адаптивного алгоритма взаимного исключения, временная сложность которого не зависит от общего количества процессов и определяется только текущим уровнем конкуренции. Известно несколько весьма сложных адаптивных алгоритмов, использующих атомарные регистры [1,3,14]. (Отметим, что из вышеупомянутого значения нижней границы по времени следует, что не существует адаптивного алгоритма, использующего только атомарные регистры, если время измеряется посредством подсчета всех шагов).

Алгоритмы с локальным вращением. Многие алгоритмы включают циклы активного ожидания. Идея заключается в том, что во время ожидания процесс вращается вокруг флагового регистра до тех пор, пока некоторый другой процесс не завершит вращение при помощи единичной операции записи. К сожалению, в условиях конкуренции подобное вращение может генерировать значительные объемы трафика в сети межсоединений из-за обмена сообщениями между процессом и памятью. Алгоритм удовлетворяет требованию локального вращения, если ему требуется такой тип вращения; иначе говоря, он вращается только на локально доступных регистрах. Совместно используемые регистры могут быть локально доступными в результате когерентного кэширования либо при использовании распределенной совместно используемой памяти, если она физически распределена между процессорами.