Аноним

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

Материал из WEGA
 
(не показано 10 промежуточных версий 1 участника)
Строка 53: Строка 53:
'''Отсутствие голодания:''' ''если процесс пытается войти в свою критическую секцию, то этот процесс в конечном итоге входит в критическую секцию.''
'''Отсутствие голодания:''' ''если процесс пытается войти в свою критическую секцию, то этот процесс в конечном итоге входит в критическую секцию.''


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




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


Первые два требования (взаимного исключения и отсутствия взаимной блокировки) были изложены в оригинальной формулировке задачи Дейкстрой. Это минимальные требования, которые могут применяться в данном случае. В ходе решения задачи предполагается, что после того как процесс начал выполнение критической секции, он всегда завершает ее выполнение, независимо от действий других процессов. Задача взаимного исключения является одной из самых широко исследовавшихся в сфере межпроцессной синхронизации. Эта задача обманчива: на первый взгляд кажется, что решить ее очень просто.
Первые два требования (взаимного исключения и отсутствия взаимной блокировки) были изложены в оригинальной формулировке задачи Дейкстрой. Это минимальные требования, которые могут применяться в данном случае. В ходе решения задачи предполагается, что после того как процесс начал выполнение критической секции, он всегда завершает ее выполнение, независимо от действий других процессов. Задача взаимного исключения является одной из самых широко исследовавшихся в сфере межпроцессной синхронизации. Эта задача обманчива: на первый взгляд кажется, что решить ее очень просто.
Строка 66: Строка 66:
'''Атомарные операции'''
'''Атомарные операции'''


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


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


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


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


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




Строка 85: Строка 85:




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




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




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




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




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


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




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


== Применение ==
== Применение ==
Строка 111: Строка 111:




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


== См. также ==
== См. также ==
Строка 118: Строка 118:


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




Строка 150: Строка 150:


15. Taubenfeld, G.: Synchronization algorithms and concurrent programming. Pearson Education - Prentice-Hall, Upper Saddle River (2006) ISBN: 0131972596
15. Taubenfeld, G.: Synchronization algorithms and concurrent programming. Pearson Education - Prentice-Hall, Upper Saddle River (2006) ISBN: 0131972596
[[Категория: Совместное определение связанных терминов]]