Алгоритмы предотвращения тупиковых ситуаций - Deadlock prevention algorithms
В Информатика, алгоритмы предотвращения тупиковых ситуаций используются в параллельное программирование когда несколько процессов должны получить более одного общий ресурс. Если два или более параллельных процесса получают несколько ресурсов без разбора, может возникнуть ситуация, когда каждый процесс имеет ресурс, необходимый другому процессу. В результате ни один из процессов не может получить все необходимые ресурсы, поэтому дальнейшее выполнение всех процессов блокируется. Эта ситуация называется тупик. Предотвращение тупика алгоритм организует использование ресурсов каждым процессом, чтобы гарантировать, что хотя бы один процесс всегда может получить все необходимые ему ресурсы.
Обзор
| Имя | Условия Коффмана | Запатентованный | Описание |
|---|---|---|---|
| Банковский алгоритм | Взаимное исключение | Нет данных | В Банковский алгоритм это распределение ресурсов и тупик избегание алгоритм разработан Эдсгер Дейкстра. |
| Предотвращение рекурсивных блокировок | Взаимное исключение | Нет | Это предотвращает вход одного потока в одну и ту же блокировку более одного раза. |
Распределенный тупик
Распределенные взаимоблокировки могут возникать в распределенные системы когда распределенные транзакции или же контроль параллелизма используется. Распределенные взаимоблокировки можно обнаружить либо путем создания глобального график ожидания, из локальных графиков ожидания на детекторе тупика или распределенный алгоритм подобно погоня за краем.
Фантомные тупики это взаимоблокировки, которые обнаруживаются в распределенной системе из-за внутренних задержек системы, но больше не существуют на момент обнаружения.
Предотвращение тупиковых ситуаций
Есть много разных способов увеличить параллелизм, где рекурсивные блокировки в противном случае привели бы к взаимоблокировкам. Но есть цена. И эта цена - либо производительность / накладные расходы, возможность повреждения данных, либо и то, и другое.
Вот некоторые примеры: иерархии блокировок,[1] блокировка подсчета ссылок и вытеснения (либо с использованием управления версиями, либо с разрешением повреждения данных при вытеснении); Ждать график (WFG) [1] алгоритмы, отслеживающие все циклы, вызывающие взаимоблокировки (включая временные блокировки); и эвристические алгоритмы, которые не обязательно увеличивают параллелизм в 100% случаев, когда возможны взаимоблокировки, но вместо этого идут на компромисс, решая их в достаточном количестве мест, чтобы производительность / накладные расходы по сравнению с параллелизмом были приемлемыми.
Рассмотрим ситуацию «когда два поезда подходят друг к другу на перекрестке». Своевременная профилактика работает так, как если бы человек стоял на перекрестке (охранник) с переключателем, который позволяет только одному поезду перейти на «супер-рельсы», который проходит над другим ожидающим поездом (ами).
- Для нерекурсивных блокировок блокировка может быть введена только один раз (где один поток, входящий дважды без разблокировки, вызовет взаимоблокировку или вызовет исключение для принудительного предотвращения циклического ожидания).
- Для рекурсивных блокировок только один поток может пройти через блокировку. Если какие-либо другие потоки входят в блокировку, они должны ждать, пока начальный поток, который прошел, не завершит n количество входов.
Проблема с первым в том, что он вообще не предотвращает тупиковые ситуации. Второй не выполняет распределенную защиту от тупиков. Но второе определение переопределяется, чтобы предотвратить сценарий взаимоблокировки, который не рассматривается в первом.
Рекурсивно только один поток может проходить через блокировку. Если другие потоки входят в блокировку, они должны дождаться, пока начальный поток, который прошел, не завершит n количество раз. Но если количество потоков, которые входят в блокировку, равно количеству заблокированных, назначьте один поток в качестве суперпотока и разрешите ему запускаться (отслеживая количество раз, когда он входит / выходит из блокировки), пока он не завершится.
После завершения суперпотока условие возвращается к использованию логики рекурсивной блокировки, и выходящий суперпоток
- устанавливает себя как не супер-поток
- уведомляет шкафчик о том, что другие заблокированные, ожидающие потоки должны повторно проверить это условие
Если существует сценарий взаимоблокировки, установите новый суперпоток и следуйте этой логике. В противном случае возобновите обычную блокировку.
Вопросы, не рассмотренные выше
Много путаницы вращается вокруг проблема остановки. Но эта логика не решает проблему остановки, потому что условия, в которых происходит блокировка, известны и дают конкретное решение (вместо общего решения, которое требуется для решения проблемы остановки). Тем не менее, этот шкафчик предотвращает все взаимоблокировки, только учитывая блокировки, использующие эту логику. Но если он используется с другими механизмами блокировки, запущенная блокировка никогда не разблокируется (исключение выбрасывается без разблокировки, бесконечный цикл внутри блокировки или ошибка кодирования, когда не удается вызвать разблокировку), то взаимоблокировка очень возможна. Чтобы увеличить условие для включения их, потребуется решить проблему остановки, так как можно иметь дело с условиями, о которых никто ничего не знает и которые нельзя изменить.
Другая проблема заключается в том, что он не решает проблему временной блокировки (на самом деле это не взаимоблокировка, а убийца производительности), когда два или более потока блокируются друг на друге, пока выполняется другой несвязанный поток. Эти временные тупиковые ситуации могут иметь поток, работающий исключительно внутри них, что увеличивает параллелизм. Но из-за того, как распределенное обнаружение взаимоблокировок работает для всех блокировок, а не для их подмножеств, несвязанный запущенный поток должен завершиться перед выполнением логики суперпотока для устранения временной взаимоблокировки.
Сценарий временной блокировки в реальном времени можно увидеть выше. Если другой несвязанный запущенный поток начинается до выхода из первого несвязанного потока, произойдет другая длительность временной взаимоблокировки. Если это происходит постоянно (крайне редко), временная взаимоблокировка может быть продлена до выхода из программы, когда гарантированно завершатся другие несвязанные потоки (из-за гарантии, что один поток всегда будет выполняться до завершения).
Дальнейшее расширение
Это может быть дополнительно расширено за счет включения дополнительной логики для увеличения параллелизма там, где в противном случае могут возникнуть временные взаимоблокировки. Но на каждом этапе добавления логики мы добавляем дополнительные накладные расходы.
Несколько примеров включают: расширение механизма блокировки распределенного суперпотока для учета каждого подмножества существующих блокировок; Ждать график (WFG) [2] алгоритмы, отслеживающие все циклы, вызывающие взаимоблокировки (включая временные блокировки); и алгоритмы эвристики, которые не обязательно увеличивают параллелизм в 100% случаев, когда возможны временные взаимоблокировки, но вместо этого идут на компромисс, решая их в достаточном количестве мест, чтобы производительность / накладные расходы по сравнению с параллелизмом были приемлемыми (например, для каждого доступного процессора работайте над поиском взаимоблокировок) циклов меньше, чем количество процессоров + 1 глубина).
