stringtranslate.com

Тупик (компьютерные науки)

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

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

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

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

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

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

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

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

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

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

Обработка тупиковых ситуаций

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

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

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

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

Обнаружение

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

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

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

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

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

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

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

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

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

Livelock

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

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

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

Распределенная взаимоблокировка

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

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

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

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

Ссылки

  1. ^ Кулурис, Джордж (2012). Концепции и проектирование распределенных систем . Пирсон. стр. 716. ISBN 978-0-273-76059-7.
  2. ^ Падуа, Дэвид (2011). Энциклопедия параллельных вычислений. Springer. стр. 524. ISBN 9780387097657. Архивировано из оригинала 18 апреля 2021 г. . Получено 16 октября 2020 г. .
  3. ^ Falsafi, Babak; Midkiff, Samuel; Dennis, JackB; Dennis, JackB; Ghoting, Amol; Campbell, Roy H; Klausecker, Christof; Kranzlmüller, Dieter; Emer, Joel; Fossum, Tryggve; Smith, Burton; Philippe, Bernard; Sameh, Ahmed; Irigoin, François; Feautrier, Paul; Praun, Christoph von; Bocchino, Robert L.; Snir, Marc; George, Thomas; Sarin, Vivek; Jann, Joefon (2011). "Deadlocks". Энциклопедия параллельных вычислений . Бостон, Массачусетс: Springer US. стр. 524–527. doi :10.1007/978-0-387-09766-4_282. ISBN 978-0-387-09765-7. S2CID  241456017. Тупиковая ситуация — это состояние, которое может возникнуть в системе, состоящей из нескольких процессов, которые могут получать доступ к общим ресурсам. Тупиковая ситуация возникает, когда два или более процессов ждут друг от друга освобождения ресурса. Ни один из процессов не может добиться какого-либо прогресса.
  4. ^ abc Silberschatz, Abraham (2006). Принципы операционной системы (7-е изд.). Wiley-India. стр. 237. ISBN 9788126509621. Архивировано из оригинала 25 января 2022 . Получено 16 октября 2020 .
  5. ^ Шнайдер, Г. Майкл (2009). Приглашение в компьютерные науки. Cengage Learning. стр. 271. ISBN 978-0324788594. Архивировано из оригинала 18 апреля 2021 г. . Получено 16 октября 2020 г. .
  6. ^ Зильбершатц, Абрахам (2006). Принципы операционной системы (7-е изд.). Wiley-India. стр. 239. ISBN 9788126509621. Архивировано из оригинала 18 апреля 2021 г. . Получено 16 октября 2020 г. .
  7. ^ Концепции операционных систем . Wiley. 2012. стр. 319. ISBN 978-1-118-06333-0.
  8. ^ "ECS 150 Spring 1999: Four Necessary and Sufficient Conditions for Deadlock". nob.cs.ucdavis.edu . Архивировано из оригинала 29 апреля 2018 г. . Получено 29 апреля 2018 г. .
  9. ^ abc Шибу, К. (2009). Введение во встроенные системы (1-е изд.). Tata McGraw-Hill Education. стр. 446. ISBN 9780070145894. Архивировано из оригинала 18 апреля 2021 г. . Получено 16 октября 2020 г. .
  10. ^ "Operating Systems: Deadlocks". www.cs.uic.edu . Архивировано из оригинала 28 мая 2020 г. . Получено 25 апреля 2020 г. Если категория ресурсов содержит более одного экземпляра, то наличие цикла в графике распределения ресурсов указывает на возможность возникновения взаимоблокировки, но не гарантирует ее. Рассмотрим, например, рисунки 7.3 и 7.4 ниже:
  11. ^ Зильбершатц, Абрахам (2006). Принципы операционной системы (7-е изд.). Wiley-India. стр. 237. ISBN 9788126509621. Архивировано из оригинала 18 апреля 2021 г. . Получено 16 октября 2020 г. .
  12. ^ ab Стюарт, Брайан Л. (2008). Принципы операционных систем (1-е изд.). Cengage Learning. стр. 446. ISBN 9781418837693. Архивировано из оригинала 18 апреля 2021 г. . Получено 16 октября 2020 г. .
  13. ^ ab Tanenbaum, Andrew S. (1995). Распределенные операционные системы (1-е изд.). Pearson Education. стр. 117. ISBN 9788177581799. Архивировано из оригинала 18 апреля 2021 г. . Получено 16 октября 2020 г. .
  14. ^ "Предисловие - Параллелизм в реальном времени, управляемый прерываниями". Архивировано из оригинала 18 сентября 2020 г. Получено 1 октября 2020 г.
  15. ^ "IBM Knowledge Center". www.ibm.com . Архивировано из оригинала 19 марта 2017 г. Получено 29 апреля 2018 г.
  16. ^ Зильбершатц, Абрахам (2006). Принципы операционной системы (7-е изд.). Wiley-India. стр. 244. ISBN 9788126509621. Архивировано из оригинала 18 апреля 2021 г. . Получено 16 октября 2020 г. .
  17. ^ "Алгоритмы избежания тупиков в операционной системе (ОС)". Electronics Mind . 26 января 2022 г.
  18. ^ Эшкрофт, Э. А. (1975). «Доказательство утверждений о параллельных программах». Журнал компьютерных и системных наук . 10 : 110–135. doi : 10.1016/S0022-0000(75)80018-3 .
  19. ^ Kwong, YS (1979). «Об отсутствии динамических блокировок в параллельных программах». Семантика параллельных вычислений . Конспект лекций по информатике. Том 70. С. 172–190. doi :10.1007/BFb0022469. ISBN 3-540-09511-X.
  20. ^ Андерсон, Джеймс Х .; Ён-джик Ким (2001). «Взаимное исключение общей памяти: основные тенденции исследований с 1986 года». Архивировано из оригинала 25 мая 2006 года.
  21. ^ Zöbel, Dieter (октябрь 1983 г.). «Проблема тупика: классифицирующая библиография». ACM SIGOPS Operating Systems Review . 17 (4): 6–15. doi : 10.1145/850752.850753 . ISSN  0163-5980. S2CID  38901737.

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

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