Взаи?мная блокиро?вка (сокращённо взаимоблокировка , англ.   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 )