Иерархические блокировки мьютексов в Java

Я хочу иметь возможность блокировки на основе иерархии файловой системы. Например:

Тема 1:

lock("/");
doStuff();
unlock();

Тема 2:

lock("/sub/foo");
doStuff();
unlock();

Тема 3:

lock("/sub/bar");
doStuff();
unlock();

Если Thread 1 получает блокировку сначала, то потоки 2 и 3 будут заблокированы до тех пор, пока не разблокируется Thread 1. Однако, если Thread 2 сначала получает блокировку, тогда Thread 3 должен иметь возможность выполнять в то же время, что и Thread 2. Общее правило заключается в том, что если есть блокировка в родительском каталоге, то поток должен блокироваться.

Есть ли в Java что-нибудь встроенное, которое может помочь в решении этой проблемы? Я хочу, чтобы избежать хранения блокировки для каждого каталога, потому что будут сотни тысяч каталогов.

Ответ 1

Я бы сохранил пути каталога в дереве следующим образом:

- /
 - sub
  - foo
  - bar

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

Эта схема гарантирует вам тупиковую свободу и стабильность соответствующих частей дерева.

Я не вижу особой проблемы, хранящей сотни тысяч блокировок. Вероятно, это будет потрачено, возможно, на 100 байт оперативной памяти за каждый замок. Но это упрощает архитектуру. Вы оценили, действительно ли это проблема?

В качестве альтернативы вы можете иметь карту с пути для блокировки. Все операции над этим словарем должны быть синхронизированы вызывающими. Это позволяет вам лениво инициализировать блокировки. Вы также можете периодически мусор собирать неиспользуемые блокировки, сначала беря блокировку записи в корне, которая выполняет все операции. Когда все будет тихо, вы отбросьте все блокировки, отличные от root.

Ответ 2

Может быть, более эффективное решение, но вот как я начну.

Я бы создал общий объект TreeAccess с помощью метода lock(path) и unlock(path). Этот метод должен был бы ввести синхронизированный блок, который будет зацикливаться до тех пор, пока путь не будет доступен. На каждой итерации, если она недоступна, она проверяет, доступен ли путь, а если нет, wait(), пока какой-либо другой поток не вызовет notifyAll(). Если путь доступен, он будет продолжен, и когда это будет сделано, вызовите метод unlock(), который будет notifyAll().

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

public void lock(String path) {
    synchronized (lock) {
        while (!available(path)) {
            lock.wait();
        }
        lockedPaths.add(path);
    }
}

public void unlock(String path) {
    synchronized (lock) {
        lockedPaths.remove(path);
        lock.notifAll();
    }
}

private boolean available(String path) {
    for (String lockedPath : lockedPaths) {
        if (isParentOrEqual(lockedPath, path) { // this method is left as an exercise
            return false;
        }
    }
    return true;
}