Википедия

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

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

Взаимная блокировка двух процессов P1 и P2 нуждающихся в двух ресурсах.

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

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

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

Динамическая взаимоблокировка править

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также править

Примечания править

  1. ↑ Квиттнер, 1980, с. 334—337.

Литература править

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

Ссылки править

Источник — https://ru.wikipedia.org/w/index.php?title=Взаимная_блокировка&oldid=129888523