Алгоритмы предотвращения тупиковых ситуаций

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

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

Фантомные взаимоблокировки — это взаимоблокировки, которые обнаруживаются в распределенной системе из-за внутренних задержек системы, но на момент обнаружения фактически не существуют.

Существует множество различных способов увеличить параллелизм, где рекурсивные блокировки в противном случае привели бы к взаимоблокировкам. Но есть цена. И эта цена — либо производительность/накладные расходы, либо возможность повреждения данных, либо и то, и другое.

Вот несколько примеров: иерархии блокировок ^[1], подсчет ссылок на блокировки и вытеснение (используя либо управление версиями, либо допуская повреждение данных при вытеснении); алгоритмы Wait-For-Graph (WFG) [1], которые отслеживают все циклы, вызывающие взаимоблокировки (включая временные взаимоблокировки); и эвристические алгоритмы, которые не обязательно увеличивают параллелизм в 100% мест, где взаимоблокировки возможны, но вместо этого идут на компромисс, решая их в достаточном количестве мест, где соотношение производительности/накладных расходов и параллелизма является приемлемым.

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

• Для нерекурсивных блокировок блокировка может быть введена только один раз (при этом один поток, введенный дважды без разблокировки, вызовет взаимоблокировку или выдаст исключение для предотвращения циклического ожидания).
• Для рекурсивных блокировок только один поток может пройти через блокировку. Если какие-либо другие потоки входят в блокировку, они должны ждать, пока исходный поток, который прошел, не завершит n-ное количество раз, когда он входил.

Итак, проблема с первым в том, что он вообще не предотвращает взаимоблокировку. Второй не предотвращает распределенную взаимоблокировку. Но второй переопределен, чтобы предотвратить сценарий взаимоблокировки, который первый не решает.

Рекурсивно, только один поток может пройти через блокировку. Если другие потоки входят в блокировку, они должны ждать, пока исходный поток, который прошел, не завершится n раз. Но если количество потоков, входящих в блокировку, равно количеству заблокированных, назначьте один поток суперпотоком и разрешите ему работать (отслеживая количество раз, когда он входит/выходит из блокировки) только до его завершения.

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

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

Если существует сценарий взаимоблокировки, установите новый суперпоток и следуйте этой логике. В противном случае возобновите обычную блокировку.

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

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

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

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

Вот несколько примеров: расширение механизма блокировки распределенного суперпотока для рассмотрения каждого подмножества существующих блокировок; алгоритмы Wait-For-Graph (WFG) [2], которые отслеживают все циклы, вызывающие взаимоблокировки (включая временные взаимоблокировки); и эвристические алгоритмы, которые не обязательно увеличивают параллелизм в 100% мест, где возможны временные взаимоблокировки, но вместо этого идут на компромисс, решая их в достаточном количестве мест, где соотношение производительности/накладных расходов и параллелизма является приемлемым (например, для каждого доступного процессора работа над поиском циклов взаимоблокировок, меньших, чем количество процессоров + 1 в глубину).

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

Доказательство: Для возникновения взаимоблокировки T1 должен ожидать блокировки, удерживаемой T2, в то время как T2 ожидает (другой) блокировки, удерживаемой T1. Но T2, ожидающий T1, должен иметь более низкий приоритет, поэтому T2 умирает и взаимоблокировка предотвращается.

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