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

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

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

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

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

Три алгоритма с локальным вращением представлены в источниках [4, 8, 11]. Эти алгоритмы используют сильные атомарные операции (выборки и приращения, перестановки, сравнения и перестановки) и также называются масштабируемыми алгоритмами, поскольку им одновременно с локальным вращением присуща адаптивность. В результате исследований эффективности было выявлено, что эти алгоритмы отлично масштабируются по мере роста конкуренции. Алгоритмы с локальным вращением, использующие только атомарные регистры, были предложены в [1, 3, 14].

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

В 1968 году Эдсгер Вибе Дейкстра опубликовал свою знаменитую статью «Взаимодействие последовательных процессов», с которой началась эпоха параллельного программирования. Задача о взаимном исключении была впервые сформулирована и решена Дейкстрой в работе [6], в которой были изложены первое решение для двух процессов, предложенное Деккером, и первое решение для n процессов, разработанное Дейкстрой. В работе [ ] приводится обзор некоторых ранних алгоритмов взаимного исключения. В [15] представлены десятки алгоритмов для решения задач о взаимном исключении и широкого спектра других задач синхронизации и проведен анализ их эффективности относительно точных мер сложности.