imported>Sldst-bot: В ш:Список примеров добавлена дата установки: 2015-01-18

2025-03-02T00:49:01Z

В ш:Список примеров добавлена дата установки: 2015-01-18

Новая страница

[[Файл:Process deadlock.svg|thumb|right|200px|Взаимная блокировка двух процессов P1 и P2 нуждающихся в двух ресурсах.]]

'''Взаи́мная блокиро́вка''' (сокращённо '''взаимоблокировка''', {{lang-en|deadlock}}) — ситуация в многозадачной среде или [[СУБД]], при которой несколько [[Процесс (информатика)|процессов]] находятся в состоянии ожидания [[Вычислительные ресурсы|ресурсов]], занятых друг другом, и ни один из них не может продолжать свое выполнение{{sfn|Квиттнер|с=334—337|1980}}.

== Простейший пример взаимной блокировки ==
{| class="standard"
!Шаг!!Процесс 1 !! Процесс 2
|-
|0||Хочет захватить A и B, начинает с A || Хочет захватить A и B, начинает с B
|-
|1||Захватывает ресурс A || Захватывает ресурс B
|-
|2||Ожидает освобождения ресурса B || Ожидает освобождения ресурса A
|-
|3|| colspan=2|<center> Взаимная блокировка</center>
|}

Отладка взаимных блокировок, как и других ошибок синхронизации, усложняется тем, что для их возникновения нужны специфические условия одновременного выполнения нескольких [[Процесс (информатика)|процессов]] (в вышеописанном примере если бы процесс 1 успел захватить ресурс B до процесса 2, то ошибка не произошла бы).

== Динамическая взаимоблокировка ==
Динамическая взаимоблокировка ({{lang-en|livelock}}) означает такую ситуацию: система не «застревает» (как в обычной взаимной блокировке), а занимается бесполезной работой, её состояние постоянно меняется — но, тем не менее, она «[[зацикливание|зациклилась]]», не производит никакой полезной работы.

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

== Обнаружение взаимных блокировок ==
Поиск ''взаимных блокировок'' осуществляется путём построения и анализа [[граф ожидания|графа ожидания]]. В графе ожидания узлами отмечаются процессы и объекты. ''Блокировки'' отмечаются рёбрами, направленными от узла, соответствующего захваченному объекту, к узлу, соответствующему захватившему его процессу. ''Ожидания'' отмечаются рёбрами, направленными от узла, соответствующего ожидающему процессу, к узлу, соответствующему ожидаемому объекту.

Цикл в графе ожидания соответствует ''взаимной блокировке''. Существует специальный алгоритм поиска [[Цикл (теория графов)|циклов в графе]].

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

Кроме того, эти алгоритмы реализуются диспетчером ресурсов — программой, отвечающей за [[Блокировка (программирование)|блокировку]] и разблокировку. Если же часть занятых в блокировке ресурсов распределяется кем-то другим, обнаружение ''взаимной блокировки'' невозможно. К примеру, [[СУБД Oracle]] обнаруживает взаимную [[Блокировка (СУБД)|блокировку]] запросов к её базам данных, но если в приведенном примере объекты — это поле базы и, к примеру, файл на жестком диске, взаимная блокировка обнаружена не будет — СУБД этот файл не обрабатывает и для неё взаимной блокировки нет.

Практически об устранении взаимных блокировок надо заботиться ещё на этапе проектирования системы — это единственный более-менее надежный способ борьбы с ними. В крайнем случае, когда основная концепция не допускает возможности избежать взаимных блокировок, следует хотя бы строить все запросы ресурсов так, чтобы такие блокировки безболезненно снимались.

== Предотвращение взаимной блокировки ==
Классический способ борьбы с проблемой — разработка иерархии блокировок: между блокировками устанавливается отношение сравнения и вводится правило о запрете захвата «большей» блокировки в состоянии, когда уже захвачена «меньшая». Таким образом, если процессу нужно несколько блокировок, ему нужно всегда начинать с самой «большой» — предварительно освободив все захваченные «меньшие», если такие есть — и затем в нисходящем порядке. Это может привести к лишним действиям (если «меньшая» блокировка нужна и уже захвачена, она освобождается только чтобы тут же быть захваченной снова), зато гарантированно решает проблему.

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

Прочие алгоритмы:

{{список примеров|дата=2015-01-18}}
{| class="wikitable" border="1"
|+ Алгоритмы и методы предотвращения взаимной блокировки
|-
! scope="col" | Название
! scope="col" | Условия Коффмана
! scope="col" | Описание
|-
| {{iw|Banker%27s_algorithm|Алгоритм Банкира}} || [[взаимное исключение]] || '''Алгоритм Банкира''' — это алгоритм {{iw|Resource allocation|распределения ресурсов}} и обхода взаимоблокировок, разработанный [[Дейкстра, Эдсгер Вибе|Э. Дейкстра]].
|-
| Алгоритм предотвращения рекурсивных блокировок || [[взаимное исключение]] || Предотвращает захват потоком одной и той же блокировки несколько раз.
|}

== См. также ==
* [[Задача об обедающих философах]]
* [[Состояние гонки]]

== Примечания ==
{{Примечания}}

== Литература ==
* {{книга | автор = Квиттнер П. | заглавие = Задачи, программы, вычисления, результаты | место = М. | издательство = Мир
| год = 1980 | страниц = 422 | isbn = | ref = Квиттнер}}

== Ссылки ==
* [https://web.archive.org/web/20050504052535/http://www-db.in.tum.de/research/projects/dda.html Deadlock Detection Agents]
* Paper «[http://www.cs.ucl.ac.uk/staff/w.emmerich/publications/ESEC01/ModelChecking/ Deadlock Detection in Distributed Object Systems]» by Nima Kaveh and Wolfgang Emmerich
* Article «[https://web.archive.org/web/20151102065120/http://www.cse.scu.edu/~jholliday/dd_9_16.htm Distributed Deadlock Detection]» by JoAnne L. Holliday and Amr El Abbadi
* Article «[http://doi.acm.org/10.1145/45075.46163 Deadlock detection in distributed databases]» by Edgar Knapp
* Article «[http://www.onjava.com/pub/a/onjava/2004/10/20/threads2.html Advanced Synchronization in Java Threads]» by Scott Oaks and Henry Wong
* Paper «[http://www.havelund.com/Publications/padtad06.pdf Confirmation of Deadlock Potentials Detected by Runtime Analysis]» by Saddek Bensalem, Jean-Claude Fernandez, Klaus Havelund and Laurent Mounier
* [http://www.cs.umass.edu/~mcorner/courses/691J/papers/TS/coffman_deadlocks/coffman_deadlocks.pdf Coffman, E.G., M.J. Elphick, and A. Shoshani, System Deadlocks, ACM Computing Surveys, 3, 2, 67-78 (1971)].
* Paper [http://citeseer.ist.psu.edu/326777.html Eliminating Receive Livelock in an Interrupt-driven Kernel] by Jeffrey C. Mogul, K. K. Ramakrishnan
* [[c2:DeadLock|DeadLock]] at the Portland Pattern Repository
* [http://www.etymonline.com/index.php?term=deadlock Etymology of «Deadlock»]
* [https://web.archive.org/web/20170918211548/http://arcs.us/ ARCS — A Web Service approach to alleviating deadlock]
* [http://zhidba.ru/index.php/stati/oracle/138-vsaimblok-oracle-1 Взаимные блокировки Oracle]
{{Нет сносок в данной статье|дата=2021-01-31}}{{Внешние ссылки}}

[[Категория:Ошибки программирования]]
[[Категория:Управление конкурентными потоками]]

Взаимная блокировка - История изменений

imported>Sldst-bot: В ш:Список примеров добавлена дата установки: 2015-01-18