Тупик - Deadlock - Wikipedia

Не путать с Детлок или же Дреды.
Эта статья посвящена концепции информатики. Для использования в других целях см. Тупик (значения).
«Livelock» перенаправляется сюда. Для видеоигры см. Livelock (видеоигра).

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

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

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

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

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

Необходимые условия

Ситуация тупика на ресурсе может возникнуть тогда и только тогда, когда в системе одновременно выполняются все следующие условия:[5]

  1. Взаимное исключение: По крайней мере, один ресурс должен находиться в режиме без совместного использования. В противном случае процессы не будут лишены возможности использовать ресурс при необходимости. Только один процесс может использовать ресурс в любой момент времени.[6]
  2. Держись и жди или же ресурсный холдинг: в настоящее время процесс удерживает хотя бы один ресурс и запрашивает дополнительные ресурсы, которые удерживаются другими процессами.
  3. Нет упреждение: ресурс может быть освобожден только добровольно процессом, который его удерживает.
  4. Круговое ожидание: каждый процесс должен ждать ресурса, который удерживается другим процессом, который, в свою очередь, ожидает, пока первый процесс освободит ресурс. В общем, есть набор ожидающих процессов, п = {п1, п2, …, пN}, такие что п1 ждет ресурса, удерживаемого п2, п2 ждет ресурса, удерживаемого п3 и так до тех пор, пока пN ждет ресурса, удерживаемого п1.[3][7]

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

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

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

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

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

В этом подходе предполагается, что тупик никогда не произойдет. Это также приложение Страусиный алгоритм.[10][11] Этот подход изначально использовался МИНИКС и UNIX.[7] Это используется, когда интервалы времени между возникновением взаимоблокировок велики, а потеря данных каждый раз допустима.

Игнорирование взаимоблокировок можно безопасно выполнять, если они официально доказанный никогда не происходить. Примером является структура RTIC.[12]

Обнаружение

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

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

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

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

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

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

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

Livelock

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

Термин был придуман Эдвард А. Эшкрофт в статье 1975 года[15] в связи с проверкой систем бронирования авиакомпаний.[16] Livelock - это частный случай ресурсный голод; общее определение лишь утверждает, что конкретный процесс не продвигается.[17]

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

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

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

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

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

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

Смотрите также

Рекомендации

  1. ^ Кулурис, Джордж (2012). Концепции и дизайн распределенных систем. Пирсон. п. 716. ISBN  978-0-273-76059-7.
  2. ^ Падуя, Дэвид (2011). Энциклопедия параллельных вычислений. Springer. п. 524. ISBN  9780387097657. Получено 28 января 2012.
  3. ^ а б c Зильбершатц, Абрахам (2006). Принципы операционной системы (7-е изд.). Wiley-India. п. 237. ISBN  9788126509621. Получено 29 января 2012.
  4. ^ Шнайдер, Г. Майкл (2009). Приглашение в информатику. Cengage Learning. п. 271. ISBN  978-0324788594. Получено 28 января 2012.
  5. ^ Зильбершатц, Абрахам (2006). Принципы операционной системы (7-е изд.). Wiley-India. п. 239. ISBN  9788126509621. Получено 29 января 2012.
  6. ^ "ECS 150 Spring 1999: четыре необходимых и достаточных условия для тупика". nob.cs.ucdavis.edu. В архиве из оригинала 29 апреля 2018 г.. Получено 29 апреля 2018.
  7. ^ а б c Шибу, К. (2009). Введение во встроенные системы (1-е изд.). Тата Макгроу-Хилл Образование. п. 446. ISBN  9780070145894. Получено 28 января 2012.
  8. ^ «Операционные системы: взаимоблокировки». www.cs.uic.edu. Получено 25 апреля 2020. Если категория ресурсов содержит более одного экземпляра, то наличие цикла в графе распределения ресурсов указывает на возможность тупика, но не гарантирует его. Рассмотрим, например, рисунки 7.3 и 7.4 ниже:
  9. ^ Зильбершатц, Абрахам (2006). Принципы операционной системы (7-е изд.). Wiley-India. п. 237. ISBN  9788126509621. Получено 29 января 2012.
  10. ^ а б Стюарт, Брайан Л. (2008). Принципы работы операционных систем (1-е изд.). Cengage Learning. п. 446. ISBN  9781418837693. Получено 28 января 2012.
  11. ^ а б Таненбаум, Эндрю С. (1995). Распределенные операционные системы (1-е изд.). Pearson Education. п. 117. ISBN  9788177581799. Получено 28 января 2012.
  12. ^ https://rtic.rs/0.5/book/en/
  13. ^ «Центр знаний IBM». www.ibm.com. В архиве из оригинала 19 марта 2017 г.. Получено 29 апреля 2018.
  14. ^ Зильбершатц, Абрахам (2006). Принципы операционной системы (7-е изд.). Wiley-India. п. 244. ISBN  9788126509621. Получено 29 января 2012.
  15. ^ Эшкрофт, Э.А. (1975). «Доказательство утверждений о параллельных программах». Журнал компьютерных и системных наук. 10: 110–135. Дои:10.1016 / S0022-0000 (75) 80018-3.
  16. ^ Квонг, Ю.С. (1979). «Об отсутствии лайвлоков в параллельных программах». Семантика параллельных вычислений. Конспект лекций по информатике. 70. С. 172–190. Дои:10.1007 / BFb0022469. ISBN  3-540-09511-X.
  17. ^ Андерсон, Джеймс Н .; Ён Джик Ким (2001). «Взаимное исключение с общей памятью: основные направления исследований с 1986 года». В архиве из оригинала 25 мая 2006 г.
  18. ^ Зебель, Дитер (октябрь 1983 г.). «Проблема тупика: классифицирующая библиография». Обзор операционных систем ACM SIGOPS. 17 (4): 6–15. Дои:10.1145/850752.850753. ISSN  0163-5980. S2CID  38901737.

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

внешняя ссылка