Strategie di blocco mutex multiple e perché le librerie non utilizzano il confronto degli indirizzi

Question

Esiste un modo ampiamente noto di bloccare più blocchi, che si basa sulla scelta di ordini lineari fissi e blocchi di acquisizione in base a questo ordine.

Questo è stato proposto, ad esempio, nella risposta per "Acquire a lock on two mutexes and avoid deadlock". Soprattutto, la soluzione basata sul confronto degli indirizzi sembra essere abbastanza elegante ed evidente.

Quando ho provato a verificare come è effettivamente implementato, ho trovato, con mia sorpresa, che questa soluzione non è molto utilizzata.

Per citare il Kernel Docs - Unreliable Guide To Locking:

Libri di testo vi dirà che se si blocca sempre nello stesso ordine, è sarà mai ottenere questo tipo di situazione di stallo. La pratica ti dirà che questo approccio non è scalabile: quando creo un nuovo blocco, non capisco il numero del kernel per capire dove si trova nella gerarchia di blocchi 5000 .

Pthread non sembra avere un tale meccanismo integrato a tutti.

Boost.Thread venuta soluzione completamente differente, lock() per multiple (da 2 a 5) mutex si basa sul tentativo e bloccaggio altrettanti mutex quanto è possibile al momento.

Questo è il frammento del codice sorgente Boost.Thread (Boost 1.48.0, boost/filetto/locks.hpp: 1291):

template<typename MutexType1,typename MutexType2,typename MutexType3> 
void lock(MutexType1& m1,MutexType2& m2,MutexType3& m3) 
{  
    unsigned const lock_count=3; 
    unsigned lock_first=0; 
    for(;;) 
    {  
     switch(lock_first) 
     {  
     case 0: 
      lock_first=detail::lock_helper(m1,m2,m3); 
      if(!lock_first) 
       return; 
      break; 
     case 1: 
      lock_first=detail::lock_helper(m2,m3,m1); 
      if(!lock_first) 
       return; 
      lock_first=(lock_first+1)%lock_count; 
      break; 
     case 2: 
      lock_first=detail::lock_helper(m3,m1,m2); 
      if(!lock_first) 
       return; 
      lock_first=(lock_first+2)%lock_count; 
      break; 
     }  
    }  
}  

dove lock_helper rendimenti 0 sul successo e il numero di mutex che non sono stati chiusi con successo altrimenti.

Perché questa soluzione è migliore, rispetto al confronto di indirizzi o altri tipi di ID? Non vedo alcun problema con il confronto tra puntatori, che può essere evitato usando questo tipo di blocco "cieco".

Ci sono altre idee su come risolvere questo problema a livello di libreria?

Answer 1

Dal testo di taglie:

io non sono nemmeno sicuro di poter dimostrare la correttezza della soluzione Boost presentato, che sembra più difficile di quello con ordine lineare.

La soluzione Boost non può essere bloccata perché non attende mai mentre sta già tenendo una serratura. Tutti i blocchi ma i primi vengono acquisiti con try_lock. Se una qualsiasi chiamata try_lock non riesce ad acquisire il blocco, tutti i blocchi acquisiti in precedenza vengono liberati. Inoltre, nell'implementazione Boost il nuovo tentativo inizierà dal blocco non è riuscito ad acquisire la volta precedente e prima attenderà fino a quando sarà disponibile; è una decisione di design intelligente.

Come regola generale, è sempre meglio evitare di bloccare le chiamate mentre si tiene un lucchetto. Pertanto, la soluzione con try-lock, se possibile, è preferibile (secondo me). Come conseguenza particolare, in caso di ordine di blocco, il sistema potrebbe rimanere bloccato. Immagina che l'ultimo blocco (ad esempio quello con l'indirizzo più grande) sia stato acquisito da un thread che è stato quindi bloccato. Ora immagina che un altro thread abbia bisogno dell'ultimo blocco e di un altro blocco e, a causa dell'ordine, prima prenderà l'altro e attenderà l'ultimo blocco. Lo stesso può accadere con tutti gli altri blocchi e l'intero sistema non fa progressi finché non viene rilasciato l'ultimo blocco. Ovviamente si tratta di un caso estremo e piuttosto improbabile, ma illustra il problema intrinseco con l'ordine di blocco: maggiore è il numero di un lucchetto, maggiore è l'impatto indiretto che il lucchetto ha quando acquisito.

L'inconveniente della soluzione basata sul try-lock è che può causare livelock e, in casi estremi, l'intero sistema potrebbe rimanere bloccato per almeno un po 'di tempo. Pertanto è importante avere uno schema di backoff che faccia pause tra i tentativi di blocco più a lungo nel tempo e forse randomizzato.

Answer 2

A volte, il blocco A deve essere acquisito prima del blocco B. Il blocco B potrebbe avere un indirizzo inferiore o superiore, quindi in questo caso non è possibile utilizzare il confronto degli indirizzi.

Esempio: quando si dispone di una struttura dati ad albero e i thread tentano di leggere e aggiornare i nodi, è possibile proteggere l'albero utilizzando un blocco lettore-scrittore per nodo. Funziona solo se i tuoi thread acquisiscono sempre i blocchi top-down root-to-leave. In questo caso l'indirizzo delle serrature non è importante.

È possibile utilizzare solo il confronto degli indirizzi se non è importante quale blocco viene acquisito per primo. Se questo è il caso, il confronto degli indirizzi è una buona soluzione. Ma se questo non è il caso non puoi farlo.

Immagino che il kernel di Linux richieda che alcuni sottosistemi siano bloccati prima che lo siano gli altri. Questo non può essere fatto usando il confronto degli indirizzi.

Answer 3

Uno scenario in cui il confronto degli indirizzi avrà esito negativo è se si utilizza il modello proxy. È possibile delegare i blocchi allo stesso oggetto e gli indirizzi saranno diversi.

consideri il seguente esempio

template<typename MutexType> 
class MutexHelper 
{ 
    MutexHelper(MutexType &m) : _m(m) {} 
    void lock() 
    { 
    std::cout <<"locking "; 
    m.lock(); 
    } 

    void unlock() 
    { 
    std::cout <<"unlocking "; 
    m.unlock(); 
    } 

    MutexType &_m; 
}; 

se la funzione

template<typename MutexType1,typename MutexType2,typename MutexType3> 
void lock(MutexType1& m1,MutexType2& m2,MutexType3& m3); 

effettivamente utilizzare l'indirizzo confronta il seguente codice ca produrre un deadlock

Mutex m1; 
Mutex m1; 

Thread1

MutexHelper hm1(m1); 
MutexHelper hm2(m2); 

lock(hm1, hm2); 

Thread2:

MutexHelper hm2(m2); 
MutexHelper hm1(m1); 
lock(hm1, hm2); 

EDIT:

si tratta di una discussione interessante che condividono po 'di luce sulla realizzazione boost :: blocco thread-best-practice-to-lock-multiple-mutexes

Indirizzo confrontare non funziona per inter- elaborare i mutex condivisi (denominati oggetti di sincronizzazione).

Answer 4

Il "confronto degli indirizzi" e approcci simili, sebbene usati abbastanza spesso, sono casi particolari.Essi funziona bene se avete

1. un meccanismo senza blocchi per ottenere
2. due (o più) "voci" della stesso tipo o livello gerarchico
3. qualsiasi schema di ordinamento stabile tra questi articoli

Ad esempio: si dispone di un meccanismo per ottenere due "account" da un elenco. Supponiamo che l'accesso alla lista sia bloccato. Ora hai i puntatori di entrambi gli elementi e vuoi bloccarli. Dal momento che sono "fratelli" devi scegliere quale bloccare prima. Qui l'approccio usando gli indirizzi (o qualsiasi altro schema di ordinamento stabile come "ID account") è OK.

Ma il testo Linux collegato parla di "gerarchie di blocco". Questo significa non bloccare tra "fratelli" (dello stesso tipo) ma tra "genitore" e "figli" che potrebbero essere di tipi diversi. Questo può accadere anche nelle strutture ad albero reali in altri scenari. esempio inventato: Per caricare un programma è necessario

1. bloccare il file inode,
2. bloccare la tabella dei processi
3. bloccare la memoria di destinazione

Questi tre blocchi non sono "fratelli" non in una chiara gerarchia. Anche i blocchi non vengono presi direttamente uno dopo l'altro - ciascun sottosistema prenderà i blocchi a proprio piacimento. Se si considera tutti gli scenari in cui questi tre (e più) sottosistemi interagiscono, si vede che non esiste un ordine chiaro e stabile a cui si possa pensare.

La libreria Boost si trova nella stessa situazione: Si sforza di fornire soluzioni generiche. Quindi non possono assumere i punti dall'alto e devono ricorrere a una strategia più complicata.