Взаимная блокировка (F[gnbugx Qlktnjkftg)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/28/Process_deadlock.svg/200px-Process_deadlock.svg.png)
Взаи́мная блокиро́вка (сокращённо взаимоблокировка, англ. deadlock) — ситуация в многозадачной среде или СУБД, при которой несколько процессов находятся в состоянии ожидания ресурсов, занятых друг другом, и ни один из них не может продолжать свое выполнение[1].
Простейший пример взаимной блокировки
[править | править код]Шаг | Процесс 1 | Процесс 2 |
---|---|---|
0 | Хочет захватить A и B, начинает с A | Хочет захватить A и B, начинает с B |
1 | Захватывает ресурс A | Захватывает ресурс B |
2 | Ожидает освобождения ресурса B | Ожидает освобождения ресурса A |
3 |
Отладка взаимных блокировок, как и других ошибок синхронизации, усложняется тем, что для их возникновения нужны специфические условия одновременного выполнения нескольких процессов (в вышеописанном примере если бы процесс 1 успел захватить ресурс B до процесса 2, то ошибка не произошла бы).
Динамическая взаимоблокировка
[править | править код]Динамическая взаимоблокировка (англ. livelock) означает такую ситуацию: система не «застревает» (как в обычной взаимной блокировке), а занимается бесполезной работой, её состояние постоянно меняется — но, тем не менее, она «зациклилась», не производит никакой полезной работы.
Жизненный пример такой ситуации: двое встречаются лицом к лицу. Каждый из них пытается посторониться, но они не расходятся, а несколько секунд сдвигаются в одну и ту же сторону.
Обнаружение взаимных блокировок
[править | править код]Поиск взаимных блокировок осуществляется путём построения и анализа графа ожидания. В графе ожидания узлами отмечаются процессы и объекты. Блокировки отмечаются рёбрами, направленными от узла, соответствующего захваченному объекту, к узлу, соответствующему захватившему его процессу. Ожидания отмечаются рёбрами, направленными от узла, соответствующего ожидающему процессу, к узлу, соответствующему ожидаемому объекту.
Цикл в графе ожидания соответствует взаимной блокировке. Существует специальный алгоритм поиска циклов в графе.
Существуют алгоритмы удаления взаимной блокировки. В то же время, выполнение алгоритмов поиска удаления взаимных блокировок может привести к динамической взаимоблокировке — взаимная блокировка образуется, сбрасывается, снова образуется, снова сбрасывается и так далее.
Кроме того, эти алгоритмы реализуются диспетчером ресурсов — программой, отвечающей за блокировку и разблокировку. Если же часть занятых в блокировке ресурсов распределяется кем-то другим, обнаружение взаимной блокировки невозможно. К примеру, СУБД Oracle обнаруживает взаимную блокировку запросов к её базам данных, но если в приведенном примере объекты — это поле базы и, к примеру, файл на жестком диске, взаимная блокировка обнаружена не будет — СУБД этот файл не обрабатывает и для неё взаимной блокировки нет.
Практически об устранении взаимных блокировок надо заботиться ещё на этапе проектирования системы — это единственный более-менее надежный способ борьбы с ними. В крайнем случае, когда основная концепция не допускает возможности избежать взаимных блокировок, следует хотя бы строить все запросы ресурсов так, чтобы такие блокировки безболезненно снимались.
Предотвращение взаимной блокировки
[править | править код]Классический способ борьбы с проблемой — разработка иерархии блокировок: между блокировками устанавливается отношение сравнения и вводится правило о запрете захвата «большей» блокировки в состоянии, когда уже захвачена «меньшая». Таким образом, если процессу нужно несколько блокировок, ему нужно всегда начинать с самой «большой» — предварительно освободив все захваченные «меньшие», если такие есть — и затем в нисходящем порядке. Это может привести к лишним действиям (если «меньшая» блокировка нужна и уже захвачена, она освобождается только чтобы тут же быть захваченной снова), зато гарантированно решает проблему.
В некоторых случаях, особенно в поделенных на модули системах, это также усложняет архитектуру. Так, например, в межмодульном интерфейсе приходится вводить вызовы, которые не делают ничего, кроме захвата и освобождения неких блокировок в модуле. Такой подход используется в файловых системах Windows в их интерфейсе взаимодействия с подсистемами кэша и виртуальной памяти.
Прочие алгоритмы:
Список примеров в этой статье не основывается на авторитетных источниках, посвящённых непосредственно предмету статьи. |
Название | Условия Коффмана | Описание |
---|---|---|
Алгоритм Банкира[англ.] | взаимное исключение | Алгоритм Банкира — это алгоритм распределения ресурсов[англ.] и обхода взаимоблокировок, разработанный Э. Дейкстра. |
Алгоритм предотвращения рекурсивных блокировок | взаимное исключение | Предотвращает захват потоком одной и той же блокировки несколько раз. |
См. также
[править | править код]Примечания
[править | править код]- ↑ Квиттнер, 1980, с. 334—337.
Литература
[править | править код]- Квиттнер П. Задачи, программы, вычисления, результаты. — М.: Мир, 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
В статье есть список источников, но не хватает сносок. |