Тупик
В параллельных вычислениях тупик — это любая ситуация, в которой ни один член некоторой группы объектов не может продолжить работу, поскольку каждый из них ожидает, пока другой член, включая себя, предпримет действие, например отправит сообщение или, что чаще, снимет блокировку . [1] Взаимные блокировки — распространенная проблема в многопроцессорных системах, параллельных вычислениях и распределенных системах , поскольку в этих контекстах системы часто используют программные или аппаратные блокировки для арбитража общих ресурсов и реализации синхронизации процессов . [2]
В операционной системе взаимоблокировка возникает, когда процесс или поток ожидания, переходит в состояние поскольку запрошенный системный ресурс удерживается другим ожидающим процессом, который, в свою очередь, ожидает другого ресурса, удерживаемого другим ожидающим процессом. [3] Если процесс неопределенно долго не может изменить свое состояние, поскольку запрошенные им ресурсы используются другим процессом, который сам ожидает, то говорят, что система находится в тупике. [4]
В системе связи взаимоблокировки возникают в основном из-за потери или повреждения сигналов, а не из-за конкуренции за ресурсы. [5]
- Происходит единый процесс.
- Более поздний процесс должен подождать.
- Взаимная блокировка возникает, когда первый процесс блокирует первый ресурс в то же время, когда второй процесс блокирует второй ресурс.
- Взаимную блокировку можно разрешить, отменив и перезапустив первый процесс.
Индивидуально необходимые и совместно достаточные условия тупиковой ситуации [ править ]
Тупиковая ситуация на ресурсе может возникнуть только в том случае, если в системе одновременно возникают все следующие условия: [6]
- Взаимное исключение . По крайней мере, один ресурс должен храниться в закрытом режиме (мы предполагаем, что один ресурс может иметь несколько экземпляров); то есть ресурс может использовать только один процесс одновременно. [7] В противном случае процессам не будет запрещено использовать ресурс при необходимости. В любой момент времени только один процесс может использовать ресурс. [8]
- Удержание и ожидание или удержание ресурсов: процесс в настоящее время удерживает хотя бы один ресурс и запрашивает дополнительные ресурсы, которые удерживаются другими процессами.
- Никакого вытеснения : ресурс может быть освобожден только добровольно удерживающим его процессом.
- Циклическое ожидание: каждый процесс должен ожидать ресурса, удерживаемого другим процессом, который, в свою очередь, ожидает, пока первый процесс освободит ресурс. В общем, существует набор процессов ожидания P = { P 1 , P 2 , ..., P N }, таких, что P 1 ожидает ресурса, удерживаемого P 2 , P 2 ожидает ресурса, удерживаемого P 2 . на P 3 и так далее, пока P N не будет ждать ресурса, удерживаемого P 1 . [4] [9]
Эти четыре условия известны как условия Коффмана из-за их первого описания в статье Эдварда Г. Коффмана-младшего 1971 года. [9]
Хотя этих условий достаточно для возникновения тупиковой ситуации в системах с одним экземпляром ресурсов, они указывают только на возможность тупиковой ситуации в системах, имеющих несколько экземпляров ресурсов. [10]
Обработка тупиков [ править ]
Большинство современных операционных систем не могут предотвратить взаимоблокировки. [11] При возникновении взаимоблокировок разные операционные системы реагируют на них по-разному, нестандартно. Большинство подходов работают, предотвращая возникновение одного из четырех условий Коффмана , особенно четвертого. [12] Основные подходы заключаются в следующем.
Игнорирование тупика [ править ]
В этом подходе предполагается, что взаимоблокировки никогда не возникнут. Это также применение алгоритма Страуса . [12] [13] Этот подход первоначально использовался MINIX и UNIX . [9] Это используется, когда временные интервалы между возникновением взаимоблокировок велики и потеря данных, возникающая каждый раз, допустима.
Игнорирование взаимоблокировок можно безопасно выполнить, если формально доказано, что взаимоблокировки никогда не возникают. Примером является структура RTIC. [14]
Обнаружение [ править ]
При обнаружении взаимоблокировок допускается возникновение взаимоблокировок. Затем состояние системы проверяется на наличие взаимоблокировки и впоследствии исправляется. Используется алгоритм, который отслеживает распределение ресурсов и состояние процессов, откатывает и перезапускает один или несколько процессов, чтобы устранить обнаруженную взаимоблокировку. Обнаружить уже произошедшую взаимоблокировку легко, поскольку ресурсы, которые каждый процесс заблокировал и/или запрашивал в данный момент, известны планировщику ресурсов операционной системы. [13]
После обнаружения взаимоблокировки ее можно исправить одним из следующих способов: [ нужна цитата ]
- Завершение процесса: один или несколько процессов, вовлеченных в тупик, могут быть прерваны. Можно было бы решить прервать все конкурирующие процессы, вовлеченные в тупик. Это гарантирует, что тупиковая ситуация будет разрешена надежно и быстро. [ нужна цитата ] Но затраты высоки, поскольку частичные вычисления будут потеряны. Или можно прервать один процесс за раз, пока тупиковая ситуация не будет устранена. Этот подход имеет большие накладные расходы, поскольку после каждого прерывания алгоритм должен определить, находится ли система по-прежнему в тупике. [ нужна цитата ] При выборе кандидата на прекращение необходимо учитывать несколько факторов, таких как приоритет и давность процесса. [ нужна цитата ]
- Вытеснение ресурсов: ресурсы, выделенные различным процессам, могут последовательно вытесняться и выделяться другим процессам до тех пор, пока тупиковая ситуация не будет преодолена. [15] [ не удалось пройти проверку ]
Профилактика [ править ]
Предотвращение тупиковых ситуаций предотвращает возникновение одного из четырех условий Коффмана.
- Удаление условия взаимного исключения означает, что ни один процесс не будет иметь монопольного доступа к ресурсу. Это оказывается невозможным для ресурсов, которые не могут быть буферизованы . Но даже при использовании буферных ресурсов тупиковая ситуация все равно может возникнуть. Алгоритмы, избегающие взаимного исключения, называются алгоритмами неблокирующей синхронизации .
- Условия удержания и ожидания или удержания ресурсов можно устранить, потребовав от процессов запрашивать все необходимые им ресурсы перед запуском (или перед началом определенного набора операций). Эти предварительные знания зачастую трудно удовлетворить, и в любом случае они представляют собой неэффективное использование ресурсов. Другой способ — потребовать от процессов запрашивать ресурсы только тогда, когда их нет; Во-первых, они должны освободить все имеющиеся у них ресурсы, прежде чем запрашивать все ресурсы, которые им понадобятся, с нуля. Это тоже зачастую непрактично. Это происходит потому, что ресурсы могут быть выделены и оставаться неиспользованными в течение длительного периода времени. Кроме того, процессу, требующему популярный ресурс, возможно, придется ждать бесконечно, поскольку такой ресурс всегда может быть выделен какому-то процессу, что приведет к нехватке ресурсов . [16] (Эти алгоритмы, такие как сериализация токенов , известны как алгоритмы «все или ничего» .)
- Условие отсутствия вытеснения также может быть трудно или невозможно избежать, поскольку процесс должен иметь ресурс в течение определенного периода времени, иначе результат обработки может быть непоследовательным или может произойти перегрузка . Однако невозможность принудительного вытеснения может помешать алгоритму приоритета . Вытеснение «заблокированного» ресурса обычно подразумевает откат , и его следует избегать, поскольку оно требует очень больших затрат. Алгоритмы, допускающие вытеснение, включают алгоритмы без блокировок и без ожидания, а также оптимистическое управление параллелизмом . Если процесс, удерживающий некоторые ресурсы, и запрашивает какой-либо другой ресурс(ы), которые не могут быть ему немедленно выделены, это условие можно устранить, освободив все удерживаемые в данный момент ресурсы этого процесса.
- Последним условием является условие циклического ожидания . Подходы, позволяющие избежать циклического ожидания, включают отключение прерываний во время критических секций и использование иерархии для определения частичного упорядочения ресурсов. Если очевидной иерархии не существует, для определения порядка использовался даже адрес памяти ресурсов, и ресурсы запрашивались в возрастающем порядке перечисления. [4] раствор Дейкстры . Также можно использовать
Избежание тупиков [ править ]
Подобно предотвращению взаимоблокировок, подход предотвращения взаимоблокировок гарантирует, что в системе не возникнет взаимоблокировок. Термин «предотвращение тупиковых ситуаций» кажется очень близким к «предотвращению тупиковых ситуаций» в лингвистическом контексте, но они сильно отличаются в контексте обработки тупиковых ситуаций. Предотвращение тупиковой ситуации не накладывает никаких условий, как это видно при предотвращении, но здесь каждый запрос ресурса тщательно анализируется, чтобы увидеть, может ли он быть безопасно выполнен, не вызывая тупиковой ситуации.
Для предотвращения тупиковых ситуаций операционной системе заранее предоставляется дополнительная информация о том, какие ресурсы процесс будет запрашивать и использовать в течение своей жизни. Алгоритм предотвращения тупиковых ситуаций анализирует каждый запрос, проверяя, что нет возможности возникновения тупиковой ситуации в будущем, если запрошенный ресурс будет выделен. Недостатком этого подхода является требование заранее предоставить информацию о том, как ресурсы будут запрашиваться в будущем. Одним из наиболее часто используемых алгоритмов предотвращения тупиковых ситуаций является алгоритм Банкера . [17]
Лайвлок [ править ]
Активная блокировка аналогична тупиковой, за исключением того, что состояния процессов, участвующих в активной блокировке, постоянно меняются относительно друг друга, ни один из них не прогрессирует.
Этот термин был придуман Эдвардом А. Эшкрофтом в статье 1975 года. [18] в связи с проверкой систем бронирования авиабилетов. [19] Livelock — это частный случай нехватки ресурсов ; общее определение лишь констатирует, что конкретный процесс не прогрессирует. [20]
Livelock представляет собой риск, связанный с некоторыми алгоритмами , которые обнаруживают взаимоблокировку и восстанавливаются из нее . Если действие предпринимают более одного процесса, алгоритм обнаружения взаимоблокировок может запускаться повторно. Этого можно избежать, гарантируя, что только один процесс (выбранный произвольно или по приоритету) выполняет действие. [21]
Распределенный тупик [ править ]
Распределенные взаимоблокировки могут возникать в распределенных системах при распределенных транзакций или управления параллелизмом использовании .
Распределенные тупиковые ситуации могут быть обнаружены либо путем построения глобального графа ожидания из локальных графов ожидания в детекторе тупиковых ситуаций, либо с помощью распределенного алгоритма, такого как отслеживание ребер.
Фантомные взаимоблокировки — это взаимоблокировки, которые ошибочно обнаруживаются в распределенной системе из-за внутренних задержек системы, но на самом деле не существуют. Например, если процесс освобождает ресурс R1 и отправляет запрос на R2 , а первое сообщение теряется или задерживается, координатор (детектор взаимоблокировок) может ошибочно заключить о взаимоблокировке (если запрос R2 при наличии R1 приведет к тупик).
См. также [ править ]
- Апория
- Алгоритм Банкира
- Уловка-22 (логика)
- Круговая ссылка
- Проблема обедающих философов
- Блокировка файлов
- Затор (в автомобильном движении)
- Повесить (вычисление)
- Тупик
- Бесконечная петля
- Линеаризуемость
- Средство проверки модели можно использовать для формальной проверки того, что система никогда не войдет в тупик.
- Алгоритм страуса
- Инверсия приоритета
- Состояние гонки
- Блокировка чтения-писателя
- Проблема со спящим парикмахером
- Безвыходное положение
- Синхронизация (информатика)
- Маршрутизация ограничения поворота
Ссылки [ править ]
- ^ Кулурис, Джордж (2012). Концепции и проектирование распределенных систем . Пирсон. п. 716. ИСБН 978-0-273-76059-7 .
- ^ Падуя, Дэвид (2011). Энциклопедия параллельных вычислений . Спрингер. п. 524. ИСБН 9780387097657 . Архивировано из оригинала 18 апреля 2021 года . Проверено 16 октября 2020 г.
- ^ Фальсафи, Бабак; Мидкифф, Сэмюэл; Деннис, ДжекБ; Деннис, ДжекБ; Готинг, Амол; Кэмпбелл, Рой Х; Клаузекер, Кристоф; Кранцльмюллер, Дитер; Эмер, Джоэл; Фоссум, Трюггве; Смит, Бертон; Филипп, Бернар; Самех, Ахмед; Иригоэн, Франсуа; Фотрие, Поль; Праун, Кристоф фон; Боккино, Роберт Л.; Снир, Марк; Джордж, Томас; Зарин, Вивек; Янн, Джоефон (2011). «Тупики». Энциклопедия параллельных вычислений . Бостон, Массачусетс: Springer US. стр. 524–527. дои : 10.1007/978-0-387-09766-4_282 . ISBN 978-0-387-09765-7 . S2CID 241456017 .
Взаимная блокировка — это состояние, которое может возникнуть в системе, состоящей из нескольких процессов, имеющих доступ к общим ресурсам. Говорят, что взаимоблокировка возникает, когда два или более процесса ждут друг от друга освобождения ресурса. Ни один из процессов не может добиться прогресса.
- ^ Перейти обратно: а б с Зильбершац, Авраам (2006). Принципы операционной системы (7-е изд.). Вили-Индия. п. 237. ИСБН 9788126509621 . Архивировано из оригинала 25 января 2022 года . Проверено 16 октября 2020 г.
- ^ Шнайдер, Г. Майкл (2009). Приглашение в информатику . Cengage Обучение. п. 271. ИСБН 978-0324788594 . Архивировано из оригинала 18 апреля 2021 года . Проверено 16 октября 2020 г.
- ^ Зильбершац, Авраам (2006). Принципы операционной системы (7-е изд.). Вили-Индия. п. 239. ИСБН 9788126509621 . Архивировано из оригинала 18 апреля 2021 года . Проверено 16 октября 2020 г.
- ^ Концепции операционной системы . Уайли. 2012. с. 319. ИСБН 978-1-118-06333-0 .
- ^ «ECS 150, весна 1999 г.: четыре необходимых и достаточных условия тупиковой ситуации» . nob.cs.ucdavis.edu . Архивировано из оригинала 29 апреля 2018 года . Проверено 29 апреля 2018 г.
- ^ Перейти обратно: а б с Сибу, К. (2009). Введение во встраиваемые системы (1-е изд.). Тата МакГроу-Хилл Образование. п. 446. ИСБН 9780070145894 . Архивировано из оригинала 18 апреля 2021 года . Проверено 16 октября 2020 г.
- ^ «Операционные системы: Тупики» . www.cs.uic.edu . Архивировано из оригинала 28 мая 2020 года . Проверено 25 апреля 2020 г.
Если категория ресурсов содержит более одного экземпляра, то наличие цикла в графе распределения ресурсов указывает на возможность тупика, но не гарантирует его. Рассмотрим, например, рисунки 7.3 и 7.4 ниже:
- ^ Зильбершац, Авраам (2006). Принципы операционной системы (7-е изд.). Вили-Индия. п. 237. ИСБН 9788126509621 . Архивировано из оригинала 18 апреля 2021 года . Проверено 16 октября 2020 г.
- ^ Перейти обратно: а б Стюарт, Брайан Л. (2008). Принципы операционных систем (1-е изд.). Cengage Обучение. п. 446. ИСБН 9781418837693 . Архивировано из оригинала 18 апреля 2021 года . Проверено 16 октября 2020 г.
- ^ Перейти обратно: а б Таненбаум, Эндрю С. (1995). Распределенные операционные системы (1-е изд.). Пирсон Образование. п. 117. ИСБН 9788177581799 . Архивировано из оригинала 18 апреля 2021 года . Проверено 16 октября 2020 г.
- ^ «Предисловие — Параллелизм в реальном времени, управляемый прерываниями» . Архивировано из оригинала 18 сентября 2020 года . Проверено 1 октября 2020 г.
- ^ «Центр знаний IBM» . www.ibm.com . Архивировано из оригинала 19 марта 2017 года . Проверено 29 апреля 2018 г.
- ^ Зильбершац, Авраам (2006). Принципы операционной системы (7-е изд.). Вили-Индия. п. 244. ИСБН 9788126509621 . Архивировано из оригинала 18 апреля 2021 года . Проверено 16 октября 2020 г.
- ^ «Алгоритмы предотвращения тупиковых ситуаций в операционной системе (ОС)» . Электронный разум . 26 января 2022 г.
- ^ Эшкрофт, Э.А. (1975). «Доказательство утверждений о параллельных программах» . Журнал компьютерных и системных наук . 10 : 110–135. дои : 10.1016/S0022-0000(75)80018-3 .
- ^ Квонг, Ю.С. (1979). "Об отсутствии лайвлоков в параллельных программах". Семантика параллельных вычислений . Конспекты лекций по информатике. Том. 70. стр. 172–190. дои : 10.1007/BFb0022469 . ISBN 3-540-09511-Х .
- ^ Андерсон, Джеймс Х .; Ён Джик Ким (2001). «Взаимное исключение общей памяти: основные тенденции исследований с 1986 года» . Архивировано из оригинала 25 мая 2006 года.
- ^ Цёбель, Дитер (октябрь 1983 г.). «Проблема тупика: классифицирующая библиография» . Обзор операционных систем ACM SIGOPS . 17 (4): 6–15. дои : 10.1145/850752.850753 . ISSN 0163-5980 . S2CID 38901737 .
Дальнейшее чтение [ править ]
- Каве, Нима; Эммерих, Вольфганг. «Обнаружение тупиковых ситуаций в системах распределенных объектов» (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 Systems Journal . 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 в репозитории шаблонов Портленда
- Этимология слова «Тупик»
| Общий | |
|---|---|
| Процесс исчисления | |
| Классические задачи | |
