Состояние, в котором участники блокируют друг друга
Оба процесса нуждаются в ресурсах для продолжения выполнения. P1 требует дополнительного ресурса R1 и владеет ресурсом R2, P2 требует дополнительного ресурса R2 и владеет R1; ни один процесс не может продолжаться.
Четыре процесса (синие линии) соревнуются за один ресурс (серый кружок), следуя политике «справа налево». Тупик возникает, когда все процессы блокируют ресурс одновременно (черные линии). Тупиковая ситуация может быть разрешена путем нарушения симметрии.
В параллельных вычислениях взаимоблокировка - это состояние, в котором каждый член группы ожидает другого члена, включая его самого, для выполнения действия, например отправки сообщения или, чаще всего, снятия блокировки . Тупик - распространенная проблема в многопроцессорных системах, параллельных вычислениях и распределенных системах, где программные и аппаратные блокировки используются для арбитража общих ресурсов и реализации синхронизация процессов.
В операционной системе взаимоблокировка возникает, когда процесс или поток входит в состояние ожидания из-за запрошенного системный ресурс удерживается другим ожидающим процессом, который, в свою очередь, ожидает другого ресурса, удерживаемого другим ожидающим процессом. Если процесс не может изменить свое состояние на неопределенный срок из-за того, что запрошенные им ресурсы используются другим ожидающим процессом, считается, что система находится в тупике.
В системе связи, взаимоблокировки возникают в основном из-за потерянных или поврежденных сигналов, а не из-за конфликта ресурсов.
Два процесса конкурируют за два ресурса в противоположном порядке.
- Проходит один процесс.
- Последующий процесс должен ждать.
- Тупиковая ситуация возникает, когда первый процесс блокирует первый ресурс одновременно с тем, как второй процесс блокирует второй ресурс.
- Тупиковая ситуация может быть разрешена путем отмены и перезапуска первого процесса.
Содержание
- 1 Необходимые условия
- 2 Обработка взаимоблокировок
- 2.1 Игнорирование взаимоблокировок
- 2.2 Обнаружение
- 2.3 Предотвращение
- 3 Livelock
- 4 Распределенная взаимоблокировка
- 5 См. Также
- 6 Ссылки
- 7 Дополнительная литература
- 8 Внешние ссылки
Необходимые условия
Ситуация тупика на ресурсе может возникнуть, если и только если в системе одновременно выполняются все следующие условия:
- Взаимное исключение : хотя бы один ресурс должен находиться в режиме, не допускающем совместного использования. В противном случае процессы не будут лишены возможности использовать ресурс при необходимости. Только один процесс может использовать ресурс в любой момент времени.
- Удержание и ожидание или удержание ресурса: процесс в настоящее время удерживает хотя бы один ресурс и запрашивает дополнительные ресурсы, которые удерживаются другими процессами.
- Нет вытеснение : ресурс может быть освобожден только добровольно процессом, удерживающим его.
- Циклическое ожидание: каждый процесс должен ждать ресурса, который удерживается другим процессом, который, в свою очередь, ждет, пока первый процесс освободит ресурс. Как правило, существует набор ожидающих процессов, P = {P 1, P 2,…, P N }, таким образом, что P 1 ожидает ресурса, удерживаемого P 2, P 2 ожидает ресурса, удерживаемого P 3 и так далее, пока P N не ожидает ресурса, удерживаемого P 1.
. Эти четыре условия известны как условия Коффмана из их первого описания в статье 1971 года Эдварда Г. Коффмана-младшего.
Хотя этих условий достаточно для возникновения тупика в системах ресурсов с одним экземпляром, они указывают только на возможность тупика в системах, имеющих несколько экземпляров ресурсов.
Обработка тупиков
Самые актуальные операционные системы не могут предотвратить взаимоблокировки. Когда возникает тупик, разные операционные системы реагируют на него по-разному нестандартным образом. Большинство подходов работают, предотвращая возникновение одного из четырех условий Коффмана, особенно четвертого. Основные подходы заключаются в следующем.
Игнорирование тупика
В этом подходе предполагается, что тупик никогда не произойдет. Это также применение алгоритма Страуса. Этот подход изначально использовался в MINIX и UNIX. Это используется, когда интервалы времени между возникновением взаимоблокировок велики, а потеря данных каждый раз допустима.
Игнорирование взаимоблокировок может быть безопасно выполнено, если взаимоблокировки формально доказаны, чтобы никогда не возникать. Примером может служить структура RTIC.
Обнаружение
При обнаружении взаимоблокировок допускается возникновение взаимоблокировок. Затем состояние системы проверяется на наличие тупиковой ситуации и впоследствии исправляется. Используется алгоритм, который отслеживает распределение ресурсов и состояния процессов, он выполняет откат и перезапускает один или несколько процессов, чтобы удалить обнаруженную взаимоблокировку. Обнаружение тупиковой ситуации, которая уже произошла, легко возможно, поскольку ресурсы, которые каждый процесс заблокировал и / или в настоящее время запрошены, известны планировщику ресурсов операционной системы.
После обнаружения тупиковой ситуации ее можно исправить с помощью одного из следующих методов:
- Завершение процесса: один или несколько процессов, вовлеченных в тупик, могут быть прерваны. Можно выбрать прерывание всех конкурирующих процессов , вовлеченных в тупик. Это гарантирует надежное и быстрое разрешение тупиковой ситуации. Но затраты высоки, так как частичные вычисления будут потеряны. Или можно выбрать прерывание по одному процессу за раз до разрешения тупиковой ситуации. Этот подход имеет высокие накладные расходы, потому что после каждого прерывания алгоритм должен определять, находится ли система по-прежнему в тупике. При выборе кандидата на завершение необходимо учитывать несколько факторов, таких как приоритет и возраст процесса.
- Вытеснение ресурсов: ресурсы, выделенные различным процессам, могут быть последовательно вытеснены и распределены другим процессам до тех пор, пока тупик не будет нарушен.
Предотвращение
(A) Два процесса, конкурирующие за один ресурс, следуют политике «первым пришел - первым обслужен». (B) Тупик возникает, когда оба процесса блокируют ресурс одновременно. (C) Тупиковая ситуация может быть разрешена нарушением симметрии блокировок. (D) Тупик можно предотвратить, нарушив симметрию запирающего механизма.
Предотвращение тупика работает, предотвращая возникновение одного из четырех условий Коффмана.
- Удаление условия взаимного исключения означает, что ни один процесс не будет иметь монопольного доступа к ресурсу. Это оказывается невозможным для ресурсов, которые не могут быть помещены в буфер. Но даже при использовании буферных ресурсов тупиковая ситуация может возникнуть. Алгоритмы, которые избегают взаимного исключения, называются алгоритмами неблокирующей синхронизации.
- Условия удержания и ожидания или удержания ресурсов могут быть сняты, требуя, чтобы процессы запрашивали все ресурсы, которые им потребуются, перед запуском (или перед тем, как приступить к определенному набору операций). Это предварительное знание часто бывает трудно удовлетворить, и в любом случае это неэффективное использование ресурсов. Другой способ - потребовать от процессов запрашивать ресурсы только тогда, когда их нет; Сначала они должны освободить все свои текущие удерживаемые ресурсы, прежде чем запрашивать все ресурсы, которые им понадобятся, с нуля. Это тоже часто непрактично. Это происходит потому, что ресурсы могут выделяться и оставаться неиспользованными в течение длительного времени. Кроме того, процессу, для которого требуется популярный ресурс, может потребоваться неопределенное время ожидания, поскольку такой ресурс всегда может быть выделен какому-либо процессу, что приводит к нехватке ресурсов. (Эти алгоритмы, такие как сериализации токенов, известны как алгоритмы «все или ничего».)
- Условие no приоритетного прерывания также может быть трудным или невозможным для избегайте, поскольку процесс должен иметь возможность иметь ресурс в течение определенного времени, иначе результат обработки может быть несовместимым, или может произойти перегрузка. Однако невозможность принудительного приоритетного прерывания может мешать алгоритму приоритета. Вытеснение «заблокированного» ресурса обычно подразумевает откат, и его следует избегать, поскольку это очень дорого обходится. Алгоритмы, которые разрешают приоритетное прерывание, включают алгоритмы без блокировок и ожидания и оптимистическое управление параллелизмом. Если процесс удерживает некоторые ресурсы и запрашивает какой-либо другой ресурс (-ы), который не может быть немедленно выделен ему, условие может быть снято путем освобождения всех удерживаемых в данный момент ресурсов этого процесса.
- Конечным условием является условие кругового ожидания. Подходы, позволяющие избежать циклического ожидания, включают отключение прерываний во время критических секций и использование иерархии для определения частичного упорядочивания ресурсов. Если очевидной иерархии не существует, даже адрес памяти ресурсов был использован для определения порядка, и ресурсы запрашиваются в порядке возрастания перечисления. Также можно использовать решение Дейкстры.
Livelock
Livelock похож на взаимоблокировку, за исключением того, что состояния процессов, вовлеченных в livelock, постоянно меняются по отношению друг к другу, ни один не прогрессирует.
Термин был введен в обращение в статье 1975 года в связи с исследованием систем бронирования авиабилетов. Livelock - это особый случай нехватки ресурсов ; общее определение указывает только на то, что конкретный процесс не выполняется.
Livelock - это риск для некоторых алгоритмов, которые обнаруживают и восстанавливают тупик. Если действие выполняется более чем одним процессом, он может запускаться повторно. Этого можно избежать, обеспечив выполнение действий только одним процессом (выбранным произвольно или по приоритету).
Распределенная взаимоблокировка
Распределенная взаимоблокировка может возникнуть в распределенных системах при используются распределенные транзакции или контроль параллелизма.
Распределенные взаимоблокировки могут быть обнаружены либо путем построения глобального графа ожидания из локальных графиков ожидания в детекторе взаимоблокировок, либо с помощью распределенного алгоритма типа Edge Chasing.
Фантомные взаимоблокировки - это взаимоблокировки, которые ложно обнаруживаются в распределенной системе из-за внутренних задержек системы, но фактически не существуют.
Например, если процесс освобождает ресурс R1 и выдает запрос для R2, а первое сообщение потеряно или задерживается, координатор (детектор взаимоблокировок) может ложно завершить взаимоблокировку (если запрос для R2 а наличие R1 вызовет тупик).
См. Также
ссылки
Дополнительная литература
- Каве, Нима; Эммерих, Вольфганг. «Обнаружение тупиковых ситуаций в распределенных объектных системах» (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.
- Mogul, Jeffrey C.; Ramakrishnan, KK (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. 7 (2): 74. doi : 10.1147 / sj.72.0074.
- Холлидей, JoAnne L.; Эль-Аббади, Амр. «Распределенное обнаружение тупиковых ситуаций». Энциклопедия распределенных вычислений. Архивировано из оригинала 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.
Внешние ссылки