Взаимное исключение

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

Общий ресурс — это объект данных , который два или более параллельных потока пытаются изменить (где разрешены две одновременные операции чтения, но не разрешены две одновременные операции записи или одна операция чтения и одна запись, поскольку это приводит к несогласованности данных). Алгоритмы взаимного исключения гарантируют, что если процесс уже выполняет операцию записи в объект данных [критический раздел], ни одному другому процессу/потоку не разрешается получать доступ к тому же объекту или изменять его до тех пор, пока первый процесс не завершит запись в объект данных [критический раздел] и освободил объект для чтения и записи другими процессами.

Требование взаимного исключения было впервые выявлено и решено Эдсгером В. Дейкстрой в его плодотворной статье 1965 года «Решение проблемы управления параллельным программированием». ^[1]^[2] которая считается первой темой в изучении параллельных алгоритмов. ^[3]

Простой пример того, почему взаимное исключение важно на практике, можно представить с помощью односвязного списка из четырех элементов, из которого необходимо удалить второй и третий. Удаление узла, находящегося между двумя другими узлами, выполняется путем изменения следующего указателя предыдущего узла, чтобы он указывал на следующий узел (другими словами, если узел $i$ удаляется, то следующий указатель узла $i - 1$ равен изменено, чтобы указать на узел $i + 1$ , тем самым удаляя из связанного списка любую ссылку на узел $i$ ). Когда такой связанный список используется несколькими потоками выполнения, два потока выполнения могут попытаться удалить два разных узла одновременно, при этом один поток выполнения изменяет указатель следующего узла $i - 1,$ чтобы он указывал на узел $i + 1$ , а другой – поток выполнения изменяет следующий указатель узла $i$ , чтобы он указывал на узел $i + 2$ . Хотя обе операции удаления завершаются успешно, желаемое состояние связанного списка не достигается: узел $i + 1$ остается в списке, поскольку следующий указатель узла $i - 1$ указывает на узел $i + 1$ .

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

Термин «взаимное исключение» также используется в отношении одновременной записи адреса памяти одним потоком, в то время как вышеупомянутый адрес памяти манипулируется или читается одним или несколькими другими потоками.

Описание проблемы [ править ]

Проблема, которую решает взаимное исключение, — это проблема совместного использования ресурсов: как программная система может контролировать доступ нескольких процессов к общему ресурсу, если каждому процессу при выполнении своей работы требуется эксклюзивный контроль над этим ресурсом? Решение на основе взаимного исключения делает общий ресурс доступным только тогда, когда процесс находится в определенном сегменте кода, называемом критическим разделом . Он контролирует доступ к общему ресурсу, контролируя каждое взаимное выполнение той части своей программы, где этот ресурс будет использоваться.

Успешное решение этой проблемы должно обладать как минимум этими двумя свойствами:

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

Свобода взаимоблокировок может быть расширена для реализации одного или обоих этих свойств:

Свобода от блокировки гарантирует, что любой процесс, желающий войти в критическую секцию, в конечном итоге сможет это сделать. Это отличается от предотвращения тупиковых ситуаций, которое требует, чтобы какой-либо ожидающий процесс мог получить доступ к критической секции, но не требует, чтобы каждый процесс получил ход. Если два процесса постоянно обмениваются ресурсами между собой, третий процесс может быть заблокирован и испытывать нехватку ресурсов , даже если система не находится в тупике. Если в системе нет блокировок, это гарантирует, что каждый процесс может получить ход в какой-то момент в будущем.
Свойство ожидания, ограниченное по k, дает более точное обязательство, чем свобода от блокировки. Свобода блокировки гарантирует, что каждый процесс в конечном итоге сможет получить доступ к критической секции: она не дает никаких гарантий относительно продолжительности ожидания. На практике процесс может быть обогнан другим процессом с более высоким приоритетом произвольное или неограниченное количество раз, прежде чем он дойдет до своей очереди. При свойстве ожидания с k -ограничением каждый процесс имеет конечное максимальное время ожидания. Это работает путем установки ограничения на количество раз, когда другие процессы могут прерываться в очереди, так что ни один процесс не может войти в критическую секцию более k раз, пока другой ожидает. ^[4]

Программу каждого процесса можно разделить на четыре раздела, что дает четыре состояния. Выполнение программы проходит через эти четыре состояния по порядку: ^[5]

Некритический раздел: Операция находится за пределами критической секции; процесс не использует и не запрашивает общий ресурс.

Пытающийся: Процесс пытается войти в критическую секцию.

Критический раздел: Процессу разрешен доступ к общему ресурсу в этом разделе.

Выход: Процесс покидает критическую секцию и делает общий ресурс доступным для других процессов.

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

Обеспечение взаимного исключения [ править ]

Аппаратные решения [ править ]

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

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

Для взаимного исключения структур данных можно использовать несколько других атомарных операций; наиболее заметным из них является метод сравнения и замены (CAS). CAS можно использовать для достижения без ожидания взаимного исключения для любой общей структуры данных путем создания связанного списка , где каждый узел представляет желаемую операцию, которую необходимо выполнить. Затем CAS используется для изменения указателей в связанном списке. ^[6]во время вставки нового узла. Только один процесс может быть успешным в своем CAS; всем остальным процессам, пытающимся добавить узел одновременно, придется повторить попытку. Затем каждый процесс может хранить локальную копию структуры данных и при перемещении по связанному списку выполнять каждую операцию из списка в его локальной копии.

Программные решения [ править ]

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

Алгоритм Деккера
Алгоритм Петерсона
Алгоритм пекарни Лэмпорта ^[7]
Алгоритм Шиманского
Алгоритм черно-белой выпечки Таубенфельда ^[2]
Алгоритм Маекавы

Эти алгоритмы не работают, если внеочередное выполнение на платформе, которая их выполняет, используется . Программистам приходится задавать строгий порядок операций с памятью внутри потока. ^[8]

Часто предпочтительнее использовать средства синхронизации, предоставляемые многопоточной библиотекой операционной системы , которая, если возможно, будет использовать преимущества аппаратных решений, но будет использовать программные решения, если аппаратных решений не существует. Например, когда блокировок используется библиотека операционной системы и поток пытается получить уже полученную блокировку, операционная система может приостановить поток с помощью переключателя контекста и заменить его другим потоком, готовым к запуску, или может поместить этот процессор в состояние пониженного энергопотребления, если нет другого потока, который можно запустить. Поэтому большинство современных методов взаимного исключения пытаются уменьшить задержку и ожидание занятости за счет использования очередей и переключений контекста. Однако если можно доказать, что время, затрачиваемое на приостановку потока и его последующее восстановление, всегда превышает время, необходимое для ожидания готовности потока к выполнению после блокировки в определенной ситуации, то спин-блокировки являются приемлемым решением. решение (только для этой ситуации). ^{[ нужна цитата ]}

проблемой взаимного с Связан исключения

Одного двоичного регистра test&set достаточно, чтобы обеспечить решение проблемы взаимного исключения без взаимоблокировок. Но решение, созданное с использованием регистра test&set, может привести к остановке некоторых процессов, которые попадают в раздел попытки. ^[4] Фактически, $\Omega ({\sqrt {n}})$ Чтобы избежать блокировки, необходимы отдельные состояния памяти. Чтобы избежать неограниченного ожидания, n различных состояний памяти. требуется ^[9]

Восстановимое взаимное исключение [ править ]

Большинство алгоритмов взаимного исключения разработаны с учетом того, что во время выполнения процесса внутри критической секции не происходит никаких сбоев. Однако на самом деле такие сбои могут быть обычным явлением. Например, внезапная потеря питания или неисправное межсоединение могут привести к тому, что процесс в критическом разделе столкнется с неисправимой ошибкой или по иным причинам не сможет продолжить работу. В случае возникновения такого сбоя традиционные, неотказоустойчивые алгоритмы взаимного исключения могут заблокироваться или иным образом нарушить ключевые свойства жизнеспособности. Для решения этой проблемы было предложено несколько решений с использованием механизмов аварийного восстановления. ^[10]

Типы устройств взаимного исключения [ править ]

Описанные выше решения можно использовать для создания приведенных ниже примитивов синхронизации:

Многие формы взаимного исключения имеют побочные эффекты. Например, классические семафоры допускают взаимоблокировки , при которых один процесс получает семафор, другой процесс получает второй семафор, а затем оба ждут освобождения другого семафора. Другие распространенные побочные эффекты включают голодание , при котором процесс никогда не получает достаточно ресурсов для завершения; инверсия приоритетов , при которой поток с более высоким приоритетом ожидает поток с более низким приоритетом; и высокая задержка, при которой реакция на прерывания не является быстрой.

Многие исследования направлены на устранение вышеуказанных эффектов, часто с целью гарантировать неблокирующий прогресс . Идеальной схемы не известно. Блокировка системных вызовов, которые приостанавливают весь процесс. До тех пор, пока такие вызовы не стали потокобезопасными , не существовало подходящего механизма для сна одного потока внутри процесса (см. опрос ). ^{[ нужна цитата ]}

См. также [ править ]

Ссылки [ править ]

^ Дейкстра, EW (1965). «Решение задачи управления параллельным программированием» . Коммуникации АКМ . 8 (9): 569. дои : 10.1145/365559.365617 . S2CID 19357737 .
^ Перейти обратно: ^а ^б Таубенфельд, «Алгоритм черно-белой выпечки» . В Proc. Распределенные вычисления, 18-я международная конференция, DISC 2004. Том 18, 56–70, 2004 г.
^ «Награда PODC Influential Paper Award: 2002» , Симпозиум ACM по принципам распределенных вычислений , получено 24 августа 2009 г.
^ Перейти обратно: ^а ^б Аттия, Хагит; Уэлч, Дженнифер (25 марта 2004 г.). Распределенные вычисления: основы, моделирование и дополнительные темы . Джон Уайли и сыновья, Inc. ISBN 978-0-471-45324-6 .
^ Лэмпорт, Лесли (26 июня 2000 г.), «Проблема взаимного исключения, часть II: Заявление и решения» (PDF) , Журнал Ассоциации вычислительной техники , 33 (2): 313–348, doi : 10.1145/5383.5384 , S2CID 12012739
^ Харрис, Тимоти Л. (2001). «Прагматичная реализация неблокирующих связанных списков» (PDF) . Распределенных вычислений . Конспекты лекций по информатике. 2180 : 300–314. дои : 10.1007/3-540-45414-4_21 . ISBN 978-3-540-42605-9 . Проверено 1 декабря 2022 г.
^ Лэмпорт, Лесли (август 1974 г.). «Новое решение проблемы параллельного программирования Дейкстры» . Коммуникации АКМ . 17 (8): 453–455. дои : 10.1145/361082.361093 . S2CID 8736023 .
^ Хольцманн, Джерард Дж.; Боснацкий, Драган (1 октября 2007 г.). «Разработка многоядерного расширения средства проверки моделей SPIN» (PDF) . Транзакции IEEE по разработке программного обеспечения . 33 (10): 659–674. дои : 10.1109/TSE.2007.70724 . S2CID 9080331 . Архивировано (PDF) из оригинала 9 октября 2022 года.
^ Бернс, Джеймс Э.; Пол Джексон, Нэнси А. Линч (январь 1982 г.), «Требования к данным для реализации взаимного исключения N-процессов с использованием одной общей переменной» (PDF) , Журнал Ассоциации вычислительной техники , 33 (2): 313–348
^ Голаб, Войцех; Рамараджу, Адитья (июль 2016 г.), «Восстановимое взаимное исключение» , Труды симпозиума ACM 2016 г. по принципам распределенных вычислений , стр. 65–74, doi : 10.1145/2933057.2933087 , ISBN 9781450339643 , S2CID 8621532

Дальнейшее чтение [ править ]

Мишель Рейналь: Алгоритмы взаимного исключения , MIT Press, ISBN 0-262-18119-3
Сунил Р. Дас, Прадип К. Шримани: Алгоритмы распределенного взаимного исключения , Компьютерное общество IEEE, ISBN 0-8186-3380-8
Томас В. Кристофер, Джордж К. Тируватукал: Высокопроизводительные вычисления на платформе Java , Прентис Холл, ISBN 0-13-016164-0
Гади Таубенфельд, Алгоритмы синхронизации и параллельное программирование , Пирсон/Прентис Холл, ISBN 0-13-197259-6

Внешние ссылки [ править ]

[1] Дейкстра, EW (1965). «Решение задачи управления параллельным программированием» . Коммуникации АКМ . 8 (9): 569. дои : 10.1145/365559.365617 . S2CID 19357737 .

[Taubenfeld:2004-2] Перейти обратно: ^а ^б Таубенфельд, «Алгоритм черно-белой выпечки» . В Proc. Распределенные вычисления, 18-я международная конференция, DISC 2004. Том 18, 56–70, 2004 г.

[3] «Награда PODC Influential Paper Award: 2002» , Симпозиум ACM по принципам распределенных вычислений , получено 24 августа 2009 г.

[Distributed_computing:_fundamentals,_simulations,_and_advanced_topics-4] Перейти обратно: ^а ^б Аттия, Хагит; Уэлч, Дженнифер (25 марта 2004 г.). Распределенные вычисления: основы, моделирование и дополнительные темы . Джон Уайли и сыновья, Inc. ISBN 978-0-471-45324-6 .

[5] Лэмпорт, Лесли (26 июня 2000 г.), «Проблема взаимного исключения, часть II: Заявление и решения» (PDF) , Журнал Ассоциации вычислительной техники , 33 (2): 313–348, doi : 10.1145/5383.5384 , S2CID 12012739

[6] Харрис, Тимоти Л. (2001). «Прагматичная реализация неблокирующих связанных списков» (PDF) . Распределенных вычислений . Конспекты лекций по информатике. 2180 : 300–314. дои : 10.1007/3-540-45414-4_21 . ISBN 978-3-540-42605-9 . Проверено 1 декабря 2022 г.

[7] Лэмпорт, Лесли (август 1974 г.). «Новое решение проблемы параллельного программирования Дейкстры» . Коммуникации АКМ . 17 (8): 453–455. дои : 10.1145/361082.361093 . S2CID 8736023 .

[8] Хольцманн, Джерард Дж.; Боснацкий, Драган (1 октября 2007 г.). «Разработка многоядерного расширения средства проверки моделей SPIN» (PDF) . Транзакции IEEE по разработке программного обеспечения . 33 (10): 659–674. дои : 10.1109/TSE.2007.70724 . S2CID 9080331 . Архивировано (PDF) из оригинала 9 октября 2022 года.

[9] Бернс, Джеймс Э.; Пол Джексон, Нэнси А. Линч (январь 1982 г.), «Требования к данным для реализации взаимного исключения N-процессов с использованием одной общей переменной» (PDF) , Журнал Ассоциации вычислительной техники , 33 (2): 313–348

[10] Голаб, Войцех; Рамараджу, Адитья (июль 2016 г.), «Восстановимое взаимное исключение» , Труды симпозиума ACM 2016 г. по принципам распределенных вычислений , стр. 65–74, doi : 10.1145/2933057.2933087 , ISBN 9781450339643 , S2CID 8621532

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]