Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску
Не путать с Детлоком или Дредлоком .
Эта статья посвящена концепции информатики. Для использования в других целях, см Тупик (значения) .

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

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

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

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

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

Необходимые условия [ править ]

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

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

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

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

Обработка тупиков [ править ]

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

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

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

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

Обнаружение [ править ]

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

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

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

Профилактика [ править ]

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

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

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

Livelock [ править ]

«Livelock» перенаправляется сюда. Для видеоигры см. Livelock (видеоигра) .

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

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

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

Распределенный тупик [ править ]

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

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

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

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

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

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

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

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

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

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

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

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