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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Задача об обедающих философах
• Состояние гонки

• Квиттнер П. Задачи, программы, вычисления, результаты. — М.: Мир, 1980. — 422 с.

• Deadlock Detection Agents
• Paper «Deadlock Detection in Distributed Object Systems» by Nima Kaveh and Wolfgang Emmerich
• Article «Distributed Deadlock Detection» by JoAnne L. Holliday and Amr El Abbadi
• Article «Deadlock detection in distributed databases» by Edgar Knapp
• Article «Advanced Synchronization in Java Threads» by Scott Oaks and Henry Wong
• Paper «Confirmation of Deadlock Potentials Detected by Runtime Analysis» by Saddek Bensalem, Jean-Claude Fernandez, Klaus Havelund and Laurent Mounier
• Coffman, E.G., M.J. Elphick, and A. Shoshani, System Deadlocks, ACM Computing Surveys, 3, 2, 67-78 (1971).
• Paper Eliminating Receive Livelock in an Interrupt-driven Kernel by Jeffrey C. Mogul, K. K. Ramakrishnan
• DeadLock at the Portland Pattern Repository
• Etymology of «Deadlock»
• ARCS — A Web Service approach to alleviating deadlock
• Взаимные блокировки Oracle

В статье есть список источников, но не хватает сносок. Без сносок сложно определить, из какого источника взято каждое отдельное утверждение. Вы можете улучшить статью, проставив сноски на источники, подтверждающие информацию. Сведения без сносок могут быть удалены. (31 января 2021)