Параллельное программирование, взаимное исключение
Ключевые слова и синонимы
Задача о критической секции
Постановка задачи
Параллелизм, синхронизация и распределение ресурсов
Параллельная система представляет собой множество процессоров, которые общаются друг с другом посредством чтения из общей памяти и записи в нее. Распределенная система – это множество процессоров, которые общаются друг с другом посредством пересылки сообщений по сети коммуникаций. Такие системы используются по различным причинам: чтобы использовать большое число процессоров для решения одной задачи намного быстрее, чем это по силам одному процессору; чтобы обеспечить возможность распределения данных по нескольким местоположениям; чтобы позволить разным процессорам совместно использовать такие ресурсы, как элементы данных, принтеры или диски; или, наконец, просто для того, чтобы дать возможность пользователям обмениваться электронными сообщениями.
Процесс соответствует конкретному вычислению. Иначе говоря, при наличии некоторой программы ее исполнение является процессом. Иногда удобнее называть процессом код самой программы. Процесс выполняется на процессоре, который представляет собой компонент физического оборудования. На одном и том же может процессоре выполняться несколько процессов, хотя в таком случае в конкретный момент времени может быть активен только один из них. Настоящий параллелизм возникает в случае, когда несколько процессов одновременно выполняются на нескольких процессорах.
Процессам в параллельной системе часто бывает необходимо синхронизировать свои действия. Синхронизация между процессорами бывает двух типов: кооперация или конкуренция. Типичным примером кооперации является случай, в котором имеются два множества процессоров, называемых производителями и потребителями; производители создают элементы данных, а потребители их впоследствии используют.
Конкуренция возникает в случаях, когда несколько процессов конкурируют за эксклюзивное использование общих ресурсов – таких как элементы данных, файлы, диски, принтеры и т.п. К примеру, целостность данных может быть нарушена, если два процесса одновременно обновляют общий файл, из-за чего будут потеряны данные о депозитах и снятиях средств или пропадут подтвержденные брони. В подобных случаях иногда бывает важно дать только одному процессу возможность использовать определенный ресурс в любое конкретное время.
Распределение ресурсов относится к взаимодействию между процессами, включающему соперничество. Задача заключается в том, как разрешить конфликты, возникающие в случаях, когда несколько процессов пытаются использовать общие ресурсы. Или, иначе говоря, как распределить общие ресурсы по конкурирующим процессам. Специальным случаем общей задачи распределения ресурсов является задача о взаимном исключении, в которой доступен только один ресурс.
Задача о взаимном исключении
Задача о взаимном исключении, впервые сформулированная Эдсгером Дейкстрой в 1965 году, обеспечивает взаимно исключающий доступ нескольких конкурирующих процессов к единственному общему ресурсу [6]. Эта задача актуальна для операционных систем, систем управления базами данных, параллельных суперкомпьютеров и компьютерных сетей, в которых необходимо разрешать конфликты, возникающие из-за попыток использования общих ресурсов несколькими процессами. Она имеет высокую важность, поскольку лежит в основе многих задач межпроцессной синхронизации.
Формальное определение задачи выглядит следующим образом. Предполагается, что каждый процесс выдает последовательность команд в бесконечном цикле. Команды разделяются на четыре непрерывных участка кода: остаток, вход, критическая секция и выход. Таким образом, структура решения для задачи взаимного исключения выглядит следующим образом:
бесконечный цикл
код остатка;
код входа;
код критической секции;
код выхода;
конец цикла
Процесс начинается с исполнения кода остатка. В некоторый момент времени процессу потребуется выполнить код из своей критической секции. Для доступа к критической секции процессу необходимо пройти через код входа, который гарантирует, что во время выполнения критической секции ни одному другому процессу не будет позволено выполнять его критическую секцию. После того как процесс завершает свою критическую секцию, он выполняет код выхода, в котором уведомляет остальные процессы о том, что работа в критической секции завершена. После выполнения кода выхода процесс возвращается к коду остатка.
Задача взаимного исключения заключается в написании кода для входа и выхода таким образом, чтобы удовлетворялись следующие два базовых ограничения.
Взаимное исключение: никакие два процесса не находятся в своих критических секциях в одно и то же время.
Отсутствие взаимной блокировки: если процесс пытается войти в свою критическую секцию, тогда некоторый процесс (не обязательно тот же самый) в конечном итоге входит в критическую секцию.
Свойство отсутствия взаимной блокировки гарантирует, что система в целом продолжает двигаться вперед. Однако при соблюдении этого свойства возможно «голодание» некоторых процессов. Это происходит в случае, когда процесс пытается войти в критическую секцию, но не получает такой возможности и бесконечно ждет на этапе кода входа. Более строгое требование, исключающее возможность голодания, можно определить следующим образом.
Отсутствие голодания: если процесс пытается войти в свою критическую секцию, то этот процесс в конечном итоге входит в критическую секцию.
Требование отсутствие голодания является строго более сильным, чем требование отсутствия взаимной блокировки, однако оно все же позволяет процессам выполнять свою критическую секцию произвольное количество раз до того, как некоторый процесс-соискатель сможет выполнить свою критическую секцию. Подобное поведение можно предупредить при помощи следующего требования справедливости.
Первым вошел, первым вышел (First-in-first-out, FIFO): ни один процесс не может войти в свою критическую секцию до процесса, который уже ожидает своей очереди для входа в критическую секцию.
Первые два требования (взаимного исключения и отсутствия взаимной блокировки) были изложены в оригинальной формулировке задачи Дейкстрой. Это минимальные требования, которые могут применяться в данном случае. В ходе решения задачи предполагается, что после того как процесс начал выполнение критической секции, он всегда завершает ее выполнение, независимо от действий других процессов. Задача взаимного исключения является одной из самых широко исследовавшихся в сфере межпроцессной синхронизации. Эта задача обманчива: на первый взгляд кажется, что решить ее очень просто.
Основные результаты
После публикации этой задачи Дейкстрой в 1965 году [6] было предложено множество решений. В силу ее важности и благодаря разработке нового оборудования и программного обеспечения новые решения задачи разрабатываются до сих пор. Перед обсуждением результатов упомянем некоторые модели межпроцессной коммуникации.
Атомарные операции
В большинстве параллельных решений задачи предполагается наличие архитектуры, в которой n процессов асинхронно общаются друг с другом посредством совместно используемых объектов. Все архитектуры поддерживают атомарные регистры, которые являются совместно используемыми объектами, поддерживающими атомарные операции чтения и записи. В литературе также рассматривается более слабое относительно атомарного регистра понятие безопасного регистра. При работе с безопасным регистром операция чтения, выполняемая не одновременно с операцией записи, возвращает корректное значение, но если операция чтения выполняется одновременно с некоторой операцией записи, она возвращает произвольное значение. Большинство современных архитектур также поддерживают некоторую форму атомарности, более сильную, чем простые операции чтения и записи. Современные атомарные операции имеют специальные названия. В частности, имеются следующие:
• Проверка и установка: принимает совместно используемый регистр r и значение val. Значение val присваивается регистру r, а старое значение r возвращается.
• Перестановка: принимает совместно используемый регистр r и локальный регистр I и при помощи атомарной операции меняет их значения местами.
• Выборка и приращение: принимает регистр r. Значение r увеличивается на 1, старое значение r возвращается.
• Сравнение и перестановка: принимает регистр r и два значения – новое и старое. Если текущее значение регистра r равно старому, то значением r становится новое и возвращается true; в противном случае значение r остается неизменным и возвращается false.
В современных операционных системах (таких как Unix и Windows) внедрены механизмы синхронизации (например, семафоры), упрощающие реализацию блокировок взаимного исключения и, следовательно, разработку параллельных приложений. Кроме того, в современных языках программирования (таких как Modula и Java) встроено понятие монитора, представляющего собой модуль программы, обеспечивающий исключительный доступ к ресурсам.
Алгоритмы и нижние границы
Для решения этой задачи разработаны сотни удачных алгоритмов, некоторые из них очень эффективны. Ниже будет упомянуто несколько таких алгоритмов. Вначале обсудим алгоритмы, использующие только атомарные или даже безопасные регистры.
Алгоритм пекарни. Это один из самых известных и элегантных алгоритмов взаимного исключения, использующий только безопасные регистры [9]. Алгоритм удовлетворяет требованию FIFO, однако использует регистры неограниченного размера. Его модифицированная версия, называемая черно-белым алгоритмом пекарни, удовлетворяет требованию FIFO и использует ограниченное количество атомарных регистров ограниченного размера [14].
Нижние границы. Нижняя граница по памяти при решении задачи о взаимном исключении с использованием только атомарных регистров выглядит следующим образом: любой алгоритм взаимного исключения с отсутствием взаимной блокировки для n процессов должен использовать не менее n совместно используемых регистров [5]. В той же работе было показано, что эта граница является точной. Нижняя граница по времени для любого алгоритма взаимного исключения, использующего атомарные регистры, выглядит следующим образом: не существует априорной границы количества шагов, выполненных процессом на этапе кода входа, до того как он войдет в свою критическую секцию (шаги подсчитываются только тогда, когда ни один другой процесс не находится в критической секции или на этапе выполнения кода выхода) [2]. Для задачи о взаимном исключении найдено немало других любопытных границ.
Быстрый алгоритм. При выполнении быстрого алгоритма взаимного исключения в отсутствие конкуренции требуется только константное количество обращений к общей памяти – в виде совместно используемых регистров – для входа в критическую секцию и выхода из нее. В работе [10] описан быстрый алгоритм взаимного исключения в ситуации наличия конкуренции; в нем процесс-победитель должен проверить статус всех остальных n процессов, прежде чем ему будет позволено войти в свою критическую секцию. Естественным образом возникает вопрос – можно ли улучшить вышеупомянутый алгоритм в случае наличия конкуренции.
Адаптивные алгоритмы. Поскольку другие процессы-соперники ждут победителя, особенно важно ускорить их вход в критическую секцию благодаря построению адаптивного алгоритма взаимного исключения, временная сложность которого не зависит от общего количества процессов и определяется только текущим уровнем конкуренции. Известно несколько весьма сложных адаптивных алгоритмов, использующих атомарные регистры [1,3,14]. (Отметим, что из вышеупомянутого значения нижней границы по времени следует, что не существует адаптивного алгоритма, использующего только атомарные регистры, если время измеряется посредством подсчета всех шагов).
Алгоритмы с локальным вращением. Многие алгоритмы включают циклы активного ожидания. Идея заключается в том, что во время ожидания процесс вращается вокруг флагового регистра до тех пор, пока некоторый другой процесс не завершит вращение при помощи единичной операции записи. К сожалению, в условиях конкуренции подобное вращение может генерировать значительные объемы трафика в сети межсоединений из-за обмена сообщениями между процессом и памятью. Алгоритм удовлетворяет требованию локального вращения, если ему требуется только этот тип вращения; иначе говоря, он вращается только на локально доступных регистрах. Совместно используемые регистры могут быть локально доступными в результате когерентного кэширования либо при использовании распределенной совместно используемой памяти, если она физически распределена между процессорами.
Три алгоритма с локальным вращением представлены в источниках [4, 8, 11]. Эти алгоритмы используют сильные атомарные операции (выборки и приращения, перестановки, сравнения и перестановки) и также называются масштабируемыми алгоритмами, поскольку им одновременно с локальным вращением присуща адаптивность. В результате исследований эффективности было выявлено, что эти алгоритмы отлично масштабируются по мере роста конкуренции. Алгоритмы с локальным вращением, использующие только атомарные регистры, были предложены в [1, 3, 14].
Здесь упомянуты лишь несколько значимых вариантов. Существуют десятки других интересных алгоритмов и нижних границ. Все вышеописанные варианты и многие другие представлены в работе [15]. Также было разработано несколько алгоритмов для решения задачи о взаимном исключении в распределенных системах передачи сообщений [13].
Применение
Синхронизация – одна из главных проблем компьютерных наук. Она является самой важной задачей в контексте параллельного программирования на современных архитектурах, а также разработки распределенных и параллельных систем.
Параллельный доступ к ресурсами, совместно используемым несколькими процессами, требует синхронизации во избежание интерференции между конфликтующими операциями. Алгоритмы блокировок взаимного исключения фактически являются механизмами управления параллелизмом в параллельных приложениях: процесс обращается к ресурсу только из кода критической секции, при выполнении которого процессу гарантирован исключительный доступ. Популярность этого подхода объясняется главным образом относительно простой моделью программирования блокировок и доступностью эффективных и масштабируемых реализаций алгоритмов. В сущности, все параллельные программы, включая операционные системы, используют различные типы блокировок взаимного исключения для синхронизации.
При использовании блокировок для защиты доступа к ресурсу, представляющему собой большую структуру данных либо базу данных, очень важна гранулярность, или зернистость, синхронизации. Использование одного блока для защиты всей структуры данных, позволяющего единомоментно обращаться к ней только одному процессу, служит примером крупнозернистой синхронизации. Мелкозернистая синхронизация позволяет блокировать небольшие фрагменты структуры данных, обеспечивая возможность одновременного доступа к ней нескольких процессов, операции которых не влияют друг на друга. Крупнозернистая синхронизация проще для программирования, однако менее эффективна и не слишком ошибкоустойчива в сравнении с мелкозернистой. Использование блокировок может снижать эффективность, поскольку процессы вынуждены ждать снятия блока. В случае использования простых структур данных (таких как очереди, стеки и счетчики) использования блокировок можно избежать, используя неблокирующие структуры данных.
См. также
Литература
В 1968 году Эдсгер Вибе Дейкстра опубликовал свою знаменитую статью «Взаимодействие последовательных процессов», с которой началась эпоха параллельного программирования. Задача о взаимном исключении была впервые сформулирована и решена Дейкстрой в работе [6], в которой были изложены первое решение для двух процессов, предложенное Деккером, и первое решение для n процессов, разработанное Дейкстрой. В работе [ ] приводится обзор некоторых ранних алгоритмов взаимного исключения. В [15] представлены десятки алгоритмов для решения задач о взаимном исключении и широкого спектра других задач синхронизации и проведен анализ их эффективности относительно точных мер сложности.
1. Afek, Y., Stupp, G., Touitou, D.: Long lived adaptive splitter and applications. Distrib. Comput. 30,67-86 (2002)
2. Alur, R., Taubenfeld, G.: Results about fast mutual exclusion. In: Proceedings of the 13th IEEE Real-Time Systems Symposium, December 1992, pp. 12-21
3. Anderson, J.H., Kim, Y.-J.: Adaptive mutual exclusion with local spinning. In: Proceedings of the 14th international symposium on distributed computing. Lect. Notes Comput. Sci. 1914, 29-43, (2000)
4. Anderson, T.E.: The performance of spin lock alternatives for shared-memory multiprocessor. IEEE Trans. Parallel Distrib. Syst. 1(1),6-16(1990)
5. Burns, J.N., Lynch, N.A.: Bounds on shared-memory for mutual exclusion. Inform. Comput. 107(2), 171-184(1993)
6. Dijkstra, E.W.: Solution of a problem in concurrent programming control. Commun. ACM 8(9), 569 (1965)
7. Dijkstra, E.W.: Co-operating sequential processes. In: Genuys, F. (ed.) Programming Languages, pp. 43-112. Academic Press, New York (1968). Reprinted from: Technical Report EWD-123, Technological University, Eindhoven (1965)
8. Graunke, G., Thakkar, S.: Synchronization algorithms for shared-memory multiprocessors. IEEE Comput. 28(6), 69-69 (1990)
9. Lamport, L.: A new solution of Dijkstra's concurrent programming problem. Commun. ACM 17(8), 453^55 (1974)
10. Lamport, L.: A fast mutual exclusion algorithm. ACM Trans. Comput.Syst. 5(1), 1-11 (1987)
11. Mellor-Crummey, J.M., Scott, M.L.: Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Trans. Comput. Syst. 9(1), 21-65 (1991)
12. Raynal, M.: Algorithms for mutual exclusion. MIT Press, Cambridge (1986). Translation of: Algorithmique du parallelisme, (1984)
13. Singhal,M.: A taxonomy of distributed mutual exclusion. J. Parallel Distrib. Comput. 18(1), 94-101 (1993)
14. Taubenfeld, G.: The black-white bakery algorithm. In: 18th international symposium on distributed computing, October (2004). LNCS, vol. 3274, pp. 56-70. Springer, Berlin (2004)
15. Taubenfeld, G.: Synchronization algorithms and concurrent programming. Pearson Education - Prentice-Hall, Upper Saddle River (2006) ISBN: 0131972596