Blocchi mutex gerarchici in Java

Question

Voglio essere in grado di bloccare in base a una gerarchia di filesystem. Ad esempio:

filettatura 1:

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

filettatura 2:

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

filetto 3:

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

Se filettatura 1 acquisisce la serratura prima poi fili 2 e 3 sarà essere bloccato fino a quando il Thread 1 non si sblocca. Tuttavia, se Thread 2 acquisisce prima il blocco, quindi Thread 3 dovrebbe essere in grado di eseguire contemporaneamente al thread 2. La regola generale è che se c'è un blocco su una directory padre, il thread deve bloccarsi.

Java ha qualcosa di integrato che può aiutare a risolvere questo? Voglio evitare di memorizzare un blocco per directory perché ci saranno centinaia di migliaia di directory.

Answer 1

sarei memorizzare i percorsi di directory in un albero come questo:

-/
- sub 
    - foo 
    - bar 

Quando è necessario per bloccare nulla in quell'albero si scende dalla radice e acquisire una lettura-lock su tutto tranne il bersaglio nodo stesso. Il nodo di destinazione ottiene un blocco di scrittura.

Questo schema garantisce la libertà di stallo e la stabilità delle parti rilevanti dell'albero.

Non vedo un problema particolare che memorizza centinaia di migliaia di serrature. Questo probabilmente sta andando a sprecare forse 100 byte di RAM per blocco. Ma semplifica l'architettura. Hai misurato se effettivamente è un problema?

In alternativa è possibile avere una mappa dal percorso per bloccare. Tutte le operazioni su quel dizionario devono essere sincronizzate dai chiamanti. Ciò consente di inizializzare i blocchi in modo pigramente. Puoi anche raccogliere periodicamente i blocchi non utilizzati prima di prendere un blocco di scrittura sulla radice che abbandona tutte le operazioni. Una volta che tutto è silenzioso, scarti tutti i blocchi non di radice.

Answer 2

Potrebbe esserci una soluzione più efficiente, ma ecco come vorrei iniziare.

Vorrei creare un oggetto TreeAccess condiviso, con un lock(path) e un metodo unlock(path). Questo metodo dovrebbe entrare in un blocco sincronizzato che andrebbe in loop fino a quando il percorso è disponibile. Ad ogni iterazione, se non disponibile, verificherebbe se il percorso è disponibile, e in caso contrario, wait() fino a quando qualche altro thread chiama notifyAll(). Se il percorso è disponibile, allora procederebbe e, una volta terminato, chiamare il metodo unlock() che sarebbe notifyAll().

Prima di procedere, è necessario memorizzare il percorso bloccato in una struttura dati. E prima di notificare, devi rimuovere il percorso sbloccato da questa struttura dati. Per verificare se un percorso è disponibile, è necessario trovare se esiste qualche percorso in questa struttura dati che è uguale o è un antenato del percorso che si desidera bloccare.

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; 
}