Взаимная блокировка

Взаи́мная блокиро́вка (англ. deadlock) — ситуация в многозадачной среде или СУБД, при которой несколько процессов находятся в состоянии бесконечного ожидания ресурсов, занятых самими этими процессами.

Простейший пример взаимной блокировки

Шаг	Процесс 1	Процесс 2
0	Хочет захватить A и B, начинает с A	Хочет захватить A и B, начинает с B
1	Захватывает ресурс A	Захватывает ресурс B
2	Ожидает освобождения ресурса B	Ожидает освобождения ресурса A
3	Взаимная блокировка

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

Livelock

Это слово означает такую ситуацию: система не «застревает» (как в обычной взаимной блокировке), а занимается бесполезной работой, её состояние постоянно меняется — но, тем не менее, она «зациклилась», не производит никакой полезной работы.

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

Обнаружение взаимных блокировок

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

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

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

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

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

Предотвращение взаимной блокировки

Классический способ борьбы с проблемой — разработка иерархии блокировок, установление правила, что некоторые блокировки никогда не могут захватываться в состоянии, в котором уже захвачены какие-то другие блокировки. Говоря точно, речь о разработке отношения сравнения между блокировками, и о запрете захвата «большей» блокировки в состоянии, когда уже захвачена «меньшая».

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

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

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

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

Есть способы избежания данной проблемы:

1. Не бери ложку, если не положил вилку
2. Бери ложку и вилку сразу (WaitForMultipleObjects)

Для того чтобы избежать взаимной блокировки можно использовать специальные алгоритмы и методы.

Алгоритмы и методы предотвращения взаимной блокировки

Название	Условия Коффмана (англ.)	Запатентован	Описание
Алгоритм Банкира (англ.)	взаимное исключение	н/д	Алгоритм Банкира — это алгоритм распределения ресурсов (англ.) и обхода взаимоблокировок, разработанный Э. Дейкстра.
Предотвращение рекурсивных блокировки	взаимное исключение	нет	Это предотвращает поток от входа в одну и ту же блокировку несколько раз.

См. также

• Состояние гонки

Ссылки

• [www-db.in.tum.de/research/projects/dda.html Deadlock Detection Agents]
• Paper «[www.cs.ucl.ac.uk/staff/w.emmerich/publications/ESEC01/ModelChecking/ Deadlock Detection in Distributed Object Systems]» by Nima Kaveh and Wolfgang Emmerich
• Article «[www.cse.scu.edu/~jholliday/dd_9_16.htm Distributed Deadlock Detection]» by JoAnne L. Holliday and Amr El Abbadi
• Article «[doi.acm.org/10.1145/45075.46163 Deadlock detection in distributed databases]» by Edgar Knapp
• Article «[www.onjava.com/pub/a/onjava/2004/10/20/threads2.html Advanced Synchronization in Java Threads]» by Scott Oaks and Henry Wong
• Paper «[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
• [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 [citeseer.ist.psu.edu/326777.html Eliminating Receive Livelock in an Interrupt-driven Kernel] by Jeffrey C. Mogul, K. K. Ramakrishnan
• DeadLock at the Portland Pattern Repository
• [www.etymonline.com/index.php?term=deadlock Etymology of «Deadlock»]
• [www.arcs.us ARCS — A Web Service approach to alleviating deadlock]
• [alldba.ru/index.php/stati/oracle/138-vsaimblok-oracle-1 Взаимные блокировки Oracle]

Отрывок, характеризующий Взаимная блокировка

Но граф в ту же минуту оправился от волнения.
– Ну, ну, – сказал он. – Вот воин еще! Глупости то оставь: учиться надо.
– Это не глупости, папенька. Оболенский Федя моложе меня и тоже идет, а главное, все равно я не могу ничему учиться теперь, когда… – Петя остановился, покраснел до поту и проговорил таки: – когда отечество в опасности.
– Полно, полно, глупости…
– Да ведь вы сами сказали, что всем пожертвуем.
– Петя, я тебе говорю, замолчи, – крикнул граф, оглядываясь на жену, которая, побледнев, смотрела остановившимися глазами на меньшого сына.
– А я вам говорю. Вот и Петр Кириллович скажет…
– Я тебе говорю – вздор, еще молоко не обсохло, а в военную службу хочет! Ну, ну, я тебе говорю, – и граф, взяв с собой бумаги, вероятно, чтобы еще раз прочесть в кабинете перед отдыхом, пошел из комнаты.
– Петр Кириллович, что ж, пойдем покурить…
Пьер находился в смущении и нерешительности. Непривычно блестящие и оживленные глаза Наташи беспрестанно, больше чем ласково обращавшиеся на него, привели его в это состояние.
– Нет, я, кажется, домой поеду…
– Как домой, да вы вечер у нас хотели… И то редко стали бывать. А эта моя… – сказал добродушно граф, указывая на Наташу, – только при вас и весела…
– Да, я забыл… Мне непременно надо домой… Дела… – поспешно сказал Пьер.
– Ну так до свидания, – сказал граф, совсем уходя из комнаты.
– Отчего вы уезжаете? Отчего вы расстроены? Отчего?.. – спросила Пьера Наташа, вызывающе глядя ему в глаза.
«Оттого, что я тебя люблю! – хотел он сказать, но он не сказал этого, до слез покраснел и опустил глаза.
– Оттого, что мне лучше реже бывать у вас… Оттого… нет, просто у меня дела.
– Отчего? нет, скажите, – решительно начала было Наташа и вдруг замолчала. Они оба испуганно и смущенно смотрели друг на друга. Он попытался усмехнуться, но не мог: улыбка его выразила страдание, и он молча поцеловал ее руку и вышел.
Пьер решил сам с собою не бывать больше у Ростовых.


Петя, после полученного им решительного отказа, ушел в свою комнату и там, запершись от всех, горько плакал. Все сделали, как будто ничего не заметили, когда он к чаю пришел молчаливый и мрачный, с заплаканными глазами.
На другой день приехал государь. Несколько человек дворовых Ростовых отпросились пойти поглядеть царя. В это утро Петя долго одевался, причесывался и устроивал воротнички так, как у больших. Он хмурился перед зеркалом, делал жесты, пожимал плечами и, наконец, никому не сказавши, надел фуражку и вышел из дома с заднего крыльца, стараясь не быть замеченным. Петя решился идти прямо к тому месту, где был государь, и прямо объяснить какому нибудь камергеру (Пете казалось, что государя всегда окружают камергеры), что он, граф Ростов, несмотря на свою молодость, желает служить отечеству, что молодость не может быть препятствием для преданности и что он готов… Петя, в то время как он собирался, приготовил много прекрасных слов, которые он скажет камергеру.
Петя рассчитывал на успех своего представления государю именно потому, что он ребенок (Петя думал даже, как все удивятся его молодости), а вместе с тем в устройстве своих воротничков, в прическе и в степенной медлительной походке он хотел представить из себя старого человека. Но чем дальше он шел, чем больше он развлекался все прибывающим и прибывающим у Кремля народом, тем больше он забывал соблюдение степенности и медлительности, свойственных взрослым людям. Подходя к Кремлю, он уже стал заботиться о том, чтобы его не затолкали, и решительно, с угрожающим видом выставил по бокам локти. Но в Троицких воротах, несмотря на всю его решительность, люди, которые, вероятно, не знали, с какой патриотической целью он шел в Кремль, так прижали его к стене, что он должен был покориться и остановиться, пока в ворота с гудящим под сводами звуком проезжали экипажи. Около Пети стояла баба с лакеем, два купца и отставной солдат. Постояв несколько времени в воротах, Петя, не дождавшись того, чтобы все экипажи проехали, прежде других хотел тронуться дальше и начал решительно работать локтями; но баба, стоявшая против него, на которую он первую направил свои локти, сердито крикнула на него:
– Что, барчук, толкаешься, видишь – все стоят. Что ж лезть то!
– Так и все полезут, – сказал лакей и, тоже начав работать локтями, затискал Петю в вонючий угол ворот.
Петя отер руками пот, покрывавший его лицо, и поправил размочившиеся от пота воротнички, которые он так хорошо, как у больших, устроил дома.
Петя чувствовал, что он имеет непрезентабельный вид, и боялся, что ежели таким он представится камергерам, то его не допустят до государя. Но оправиться и перейти в другое место не было никакой возможности от тесноты. Один из проезжавших генералов был знакомый Ростовых. Петя хотел просить его помощи, но счел, что это было бы противно мужеству. Когда все экипажи проехали, толпа хлынула и вынесла и Петю на площадь, которая была вся занята народом. Не только по площади, но на откосах, на крышах, везде был народ. Только что Петя очутился на площади, он явственно услыхал наполнявшие весь Кремль звуки колоколов и радостного народного говора.
Одно время на площади было просторнее, но вдруг все головы открылись, все бросилось еще куда то вперед. Петю сдавили так, что он не мог дышать, и все закричало: «Ура! урра! ура!Петя поднимался на цыпочки, толкался, щипался, но ничего не мог видеть, кроме народа вокруг себя.
На всех лицах было одно общее выражение умиления и восторга. Одна купчиха, стоявшая подле Пети, рыдала, и слезы текли у нее из глаз.
– Отец, ангел, батюшка! – приговаривала она, отирая пальцем слезы.
– Ура! – кричали со всех сторон. С минуту толпа простояла на одном месте; но потом опять бросилась вперед.
Петя, сам себя не помня, стиснув зубы и зверски выкатив глаза, бросился вперед, работая локтями и крича «ура!», как будто он готов был и себя и всех убить в эту минуту, но с боков его лезли точно такие же зверские лица с такими же криками «ура!».