Тупик

Не путать с Детлоком или Дредлоком .

Эта статья о концепции информатики. Чтобы узнать о других значениях, см. Тупик (значения) .

Оба процесса нуждаются в ресурсах для продолжения выполнения. P1 требует дополнительного ресурса R1 и владеет ресурсом R2 , P2 требует дополнительного ресурса R2 и владеет R1 ; ни один процесс не может продолжаться.

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

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

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

В системе связи взаимоблокировки возникают в основном из-за потери или повреждения сигналов, а не из-за конкуренции за ресурсы.

Два процесса конкурируют за два ресурса в противоположном порядке.

1. Происходит единый процесс.
2. Более поздний процесс должен подождать.
3. Взаимная блокировка возникает, когда первый процесс блокирует первый ресурс в то же время, когда второй процесс блокирует второй ресурс.
4. Взаимную блокировку можно разрешить, отменив и перезапустив первый процесс.

Индивидуально необходимые и совместно достаточные условия тупиковой ситуации

Тупиковая ситуация на ресурсе может возникнуть только в том случае, если в системе одновременно возникают все следующие условия:

1. Взаимное исключение . По крайней мере, один ресурс должен храниться в закрытом режиме (мы предполагаем, что один ресурс может иметь несколько экземпляров); то есть ресурс может использовать только один процесс одновременно. В противном случае процессам не будет запрещено использовать ресурс при необходимости. В любой момент времени только один процесс может использовать ресурс.
2. Удержание и ожидание или удержание ресурсов: процесс в настоящее время удерживает хотя бы один ресурс и запрашивает дополнительные ресурсы, которые удерживаются другими процессами.
3. Никакого вытеснения : ресурс может быть освобожден только добровольно удерживающим его процессом.
4. Циклическое ожидание: каждый процесс должен ожидать ресурса, удерживаемого другим процессом, который, в свою очередь, ожидает, пока первый процесс освободит ресурс. В общем, существует набор процессов ожидания P = { P ₁ , P ₂ , ..., P _N }, таких, что P ₁ ожидает ресурса, удерживаемого P ₂ , P ₂ ожидает ресурса, удерживаемого P 2 . на P ₃ и так далее, пока P _N не будет ждать ресурса, удерживаемого P ₁ .

Эти четыре условия известны как условия Коффмана из-за их первого описания в статье Эдварда Г. Коффмана-младшего 1971 года.

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

Обработка тупиков

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

Игнорирование тупика

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

Игнорирование взаимоблокировок можно безопасно выполнить, если формально доказано, что взаимоблокировки никогда не возникают. Примером является структура RTIC.

Обнаружение

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

После обнаружения взаимоблокировки ее можно исправить одним из следующих способов:

1. Завершение процесса: один или несколько процессов, вовлеченных в тупик, могут быть прерваны. Можно было бы решить прервать все конкурирующие процессы, вовлеченные в тупик. Это гарантирует, что тупиковая ситуация будет разрешена надежно и быстро. Но затраты высоки, поскольку частичные вычисления будут потеряны. Или можно выбрать прерывание одного процесса за раз, пока тупиковая ситуация не будет разрешена. Этот подход имеет большие накладные расходы, поскольку после каждого прерывания алгоритм должен определить, находится ли система по-прежнему в тупике. При выборе кандидата на прекращение необходимо учитывать несколько факторов, таких как приоритет и давность процесса.
2. Вытеснение ресурсов: ресурсы, выделенные различным процессам, могут последовательно вытесняться и выделяться другим процессам до тех пор, пока тупиковая ситуация не будет преодолена.

Профилактика

Основная статья: Алгоритмы предотвращения тупиков

(А) Два процесса конкурируют за один ресурс, следуя политике «первым пришел — первым обслужен». (Б) Тупиковая ситуация возникает, когда оба процесса одновременно блокируют ресурс. (C) Тупик можно разрешить , нарушив симметрию замков. (D) Тупиковую ситуацию можно предотвратить , нарушив симметрию запорного механизма.

Предотвращение тупиковых ситуаций предотвращает возникновение одного из четырех условий Коффмана.

• Удаление условия взаимного исключения означает, что ни один процесс не будет иметь монопольного доступа к ресурсу. Это оказывается невозможным для ресурсов, которые не могут быть буферизованы . Но даже при использовании буферных ресурсов тупиковая ситуация все равно может возникнуть. Алгоритмы, избегающие взаимного исключения, называются алгоритмами неблокирующей синхронизации .
• Условия удержания и ожидания или удержания ресурсов можно устранить, потребовав от процессов запрашивать все необходимые им ресурсы перед запуском (или перед началом определенного набора операций). Эти предварительные знания зачастую трудно удовлетворить, и в любом случае они представляют собой неэффективное использование ресурсов. Другой способ — потребовать от процессов запрашивать ресурсы только тогда, когда их нет; Во-первых, они должны освободить все имеющиеся у них ресурсы, прежде чем запрашивать все ресурсы, которые им понадобятся, с нуля. Это тоже зачастую непрактично. Это происходит потому, что ресурсы могут быть выделены и оставаться неиспользованными в течение длительного периода времени. Кроме того, процессу, требующему популярный ресурс, возможно, придется ждать бесконечно, поскольку такой ресурс всегда может быть выделен какому-то процессу, что приведет к нехватке ресурсов . (Эти алгоритмы, такие как сериализация токенов , известны как алгоритмы «все или ничего» .)
• Условие отсутствия вытеснения также может быть трудно или невозможно избежать, поскольку процесс должен иметь ресурс в течение определенного периода времени, иначе результат обработки может быть непоследовательным или перегрузка может произойти . Однако невозможность принудительного вытеснения может помешать алгоритму приоритета . Вытеснение «заблокированного» ресурса обычно подразумевает откат , и его следует избегать, поскольку оно требует очень больших затрат. Алгоритмы, допускающие вытеснение, включают алгоритмы без блокировок и без ожидания, а также оптимистическое управление параллелизмом . Если процесс, удерживающий некоторые ресурсы, и запрашивает какой-либо другой ресурс(ы), которые не могут быть ему немедленно выделены, это условие можно устранить, освободив все удерживаемые в данный момент ресурсы этого процесса.
• Последним условием является условие циклического ожидания . Подходы, позволяющие избежать циклического ожидания, включают отключение прерываний во время критических секций и использование иерархии для определения частичного упорядочения ресурсов. Если очевидной иерархии не существует, для определения порядка использовался даже адрес памяти ресурсов, и ресурсы запрашивались в возрастающем порядке перечисления. раствор Дейкстры . Также можно использовать

Избежание тупиков

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

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

Лайвлок

«Livelock» перенаправляется сюда. Чтобы узнать о видеоигре, см. Livelock (видеоигра) .

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

Этот термин был придуман Эдвардом А. Эшкрофтом в статье 1975 года. в связи с проверкой систем бронирования авиабилетов. Livelock — это частный случай нехватки ресурсов ; общее определение лишь констатирует, что конкретный процесс не прогрессирует.

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

Распределенный тупик

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

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

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

См. также

• Апория
• Алгоритм Банкира
• Уловка-22 (логика)
• Круговая ссылка
• Проблема обедающих философов
• Блокировка файлов
• Затор (в автомобильном движении)
• Повесить (вычисление)
• Тупик
• Бесконечный цикл
• Линеаризуемость
• Средство проверки модели можно использовать для формальной проверки того, что система никогда не войдет в тупик.
• Алгоритм страуса
• Инверсия приоритета
• Состояние гонки
• Блокировка чтения-писателя
• Проблема со спящим парикмахером
• Тупик
• Синхронизация (информатика)
• Маршрутизация ограничения поворота

Дальнейшее чтение

• Каве, Нима; Эммерих, Вольфганг. «Обнаружение тупиковых ситуаций в системах распределенных объектов» (PDF) . Лондон: Университетский колледж Лондона. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
• Бенсалем, Саддек; Фернандес, Жан-Клод; Хавелунд, Клаус; Мунье, Лоран (2006). «Подтверждение потенциалов тупиковой ситуации, обнаруженных с помощью анализа времени выполнения». Материалы семинара 2006 г. «Параллельные и распределенные системы: Тестирование и отладка» . АКМ. стр. 41–50. CiteSeerX   10.1.1.431.3757 . дои : 10.1145/1147403.1147412 . ISBN  978-1595934147 . S2CID   2544690 .
• Коффман, Эдвард Дж. младший; Элфик, Майкл Дж.; Шошани, Арье (1971). «Системные тупики» (PDF) . Обзоры вычислительной техники ACM . 3 (2): 67–78. дои : 10.1145/356586.356588 . S2CID   15975305 .
• Могул, Джеффри С.; Рамакришнан, К.К. (1997). «Устранение блокировки приема в ядре, управляемом прерываниями». Транзакции ACM в компьютерных системах . 15 (3): 217–252. CiteSeerX   10.1.1.156.667 . дои : 10.1145/263326.263335 . ISSN   0734-2071 . S2CID   215749380 .
• Хавендер, Джеймс В. (1968). «Как избежать тупиковых ситуаций в многозадачных системах» . Системный журнал IBM . 7 (2): 74. дои : 10.1147/sj.72.0074 . Архивировано из оригинала 24 февраля 2012 года . Проверено 27 января 2009 г.
• Холлидей, Джоэнн Л.; Эль-Аббади, Амр. «Распределенное обнаружение взаимоблокировок» . Энциклопедия распределенных вычислений . Архивировано из оригинала 2 ноября 2015 года . Проверено 29 декабря 2004 г.
• Кнапп, Эдгар (1987). «Обнаружение тупиков в распределенных базах данных». Обзоры вычислительной техники ACM . 19 (4): 303–328. CiteSeerX   10.1.1.137.6874 . дои : 10.1145/45075.46163 . ISSN   0360-0300 . S2CID   2353246 .
• Лин, Ибэй; Чен, Шиган; Чанг, Джейсон (2006). «Об оптимальном планировании обнаружения тупиковых ситуаций». Транзакции IEEE на компьютерах . 55 (9): 1178–1187. CiteSeerX   10.1.1.259.4311 . дои : 10.1109/tc.2006.151 . S2CID   7813284 .

Внешние ссылки

• « Расширенная синхронизация в потоках Java », Скотт Оукс и Генри Вонг.
• Агенты обнаружения тупиковых ситуаций
• DeadLock в репозитории шаблонов Портленда
• Этимология слова «Тупик»