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

Взаимное исключение: никакие два процесса не находятся в своих критических секциях в одно и то же время.

Отсутствие взаимной блокировки: если процесс пытается войти в свою критическую секцию, тогда некоторый процесс (не обязательно тот же самый) в конечном итоге входит в критическую секцию.

Отсутствие голодания: если процесс пытается войти в свою критическую секцию, то этот процесс в конечном итоге входит в критическую секцию.

Требование отсутствие голодания является более сильным, чем требование отсутствия взаимной блокировки, однако оно все же позволяет процессам выполнять свою критическую секцию произвольное количество раз до того, как некоторый процесс- соискатель сможет выполнить свою критическую секцию. Подобное поведение можно предупредить при помощи следующего требования справедливости.

Первым вошел, первым вышел (First-in-first-out, FIFO): ни один если процесс не может войти в свою критическую секцию до процесса, который уже ожидает своей очереди для входа в критическую секцию.

В большинстве параллельных решений задачи предполагается наличие архитектуры, в которой n процессов асинхронно общаются друг с другом посредством совместно используемых объектов. Все архитектуры поддерживают атомарные регистры, которые являются совместно используемыми объектами, поддерживающими атомарные операции чтения и записи. В литературе также рассматривается более слабое относительно атомарного регистра понятие безопасного регистра. При работе с безопасным регистром операция чтения, выполняемая не одновременно с операцией записи, возвращает корректное значение, но если операция чтения выполняется одновременно с некоторой операцией записи, она возвращает произвольное значение. Большинство современных архитектур также поддерживают некоторую форму атомарности, более сильную, чем простые операции чтения и записи. Современные атомарные операции имеют специальные названия. В частности, имеются такие:

• Проверка и установка: принимает совместно используемый регистр r и значение val. Значение val присваивается регистру r, а старое значение r возвращается.

• Перестановка: принимает совместно используемый регистр r и локальный регистр I и при помощи атомарной операции меняет их значения местами.

• Выборка и приращение: принимает регистр r. Значение r увеличивается на 1, старое значение r возвращается.

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

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

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

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

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

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

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

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

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

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