Разработайте класс, обеспечивающий блокировку так, чтобы предотвратить возникновение мертвой блокировки

Существует несколько общих способов предотвратить мертвые блокировки. Один из самых популярных — обязать процесс явно объявлять, в какой блокировке он нуждается. Тогда мы можем проверить, будет ли созданная блокировка мертвой, и если так, можно прекратить работу.

Давайте разберемся, как обнаружить мертвую блокировку. Предположим, что мы запрашиваем следующий порядок блокировок:

А = {1, 2, 3, 4}
В = {1, 3, 5}
С = {7, 5, 9, 2}

Это приведет к мертвой блокировке, потому что:

А блокирует 2, ждет 3
В блокирует 3, ждет 5
С блокирует 5, ждет 2

Можно представить этот сценарий в виде графа, где 2 соединено с 3, а 3 соединено с 5, а 5 соединено с 2. Мертвая блокировка описывается циклом. Ребро (w, v) существует в графе, если процесс объявляет, что он запрашивает блокировку v немедленно после блокировки w. В предыдущем примере в графе будут существовать следующие ребра:

(1, 2), (2, 3), (3, 4), (1, 3), (3, 5), (7, 5), (5, 9), (9, 2).

«Владелец» ребра не имеет значения.

Этот класс будет нуждаться в методе declare, который использует потоки и процессы для объявления порядка, в котором будут запрашиваться ресурсы. Метод declare будет проверять порядок объявления, добавляя каждую непрерывную пару элементов (v, w) к графу. Впоследствии он проверит, не появилось ли циклов. Если возник цикл, он удалит добавленное ребро из графика и выйдет.

Нам нужно обсудить только один нюанс. Как мы обнаружим цикл? Мы можем обнаружить цикл с помощью поиска в глубину через каждый связанный элемент (то есть через каждый компонент графа). Существуют сложные компоненты, позволяющие выбрать все соединенные компоненты графа, но наша задача не настолько сложна.

Мы знаем, что если возникает петля, то виновато одно из ребер. Таким образом, если поиск в глубину затрагивает эти ребра, мы обнаружим петлю.

Псевдокод для этого обнаружения петли примерно следующий:

В данном коде можно сделать несколько поисков в глубину, но touchedNodes нужно инициализировать только один раз. Мы выполняем итерации, пока все значения в touchedNodes равны false.

Приведенный далее код более подробен. Для простоты мы предполагаем, что все блокировки и процессы (владельцы) последовательно упорядочены.

Разбор взят из перевода книги Г. Лакман Макдауэлл и предназначен исключительно для ознакомления.
Если он вам понравился, то рекомендуем купить книгу «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию».