Utilizzo di molte serrature mutex

Question

Ho una struttura ad albero grande su cui lavorano più thread contemporaneamente. Idealmente, mi piacerebbe avere un singolo blocco mutex per ogni cella.

Ho esaminato la definizione di pthread_mutex_t in bits/pthreadtypes.h ed è piuttosto breve, quindi l'utilizzo della memoria non dovrebbe essere un problema nel mio caso.

Tuttavia, c'è una penalità di prestazioni quando si utilizzano molti (diciamo qualche migliaio) diversi pthread_mutex_t s per solo 8 thread?

Answer 1

Se si blocca e si sblocca molto frequentemente, può esserci una penalità, dal momento che ottenere e rilasciare serrature richiede un po 'di tempo e può richiedere una discreta quantità di tempo se le serrature sono contese.

Quando si utilizzano molti blocchi in una struttura come questa, sarà necessario essere molto specifici su ciò che ogni blocco si blocca effettivamente, e assicurarsi di stare attenti ai blocchi di sicurezza di AB-BA. Ad esempio, se si modifica la struttura dell'albero durante un'operazione di blocco, sarà necessario bloccare tutti i nodi che verranno modificati, in un ordine coerente e assicurarsi che i thread che lavorano sui discendenti non vengano confusi.

Se si dispone di un numero molto elevato di blocchi, distribuiti in memoria, i problemi di memorizzazione nella cache potrebbero causare problemi di prestazioni, a seconda dell'architettura, poiché le operazioni di blocco generalmente invalidano almeno parte della cache.

La soluzione migliore è probabilmente quella di implementare una struttura di blocco semplice, quindi tracciarlo, quindi perfezionarlo per migliorare le prestazioni, se necessario. Non sono sicuro di cosa stai facendo con l'albero, ma un buon punto di partenza potrebbe essere un blocco di lettore-scrittore per l'intero albero, se ti aspetti di leggere molto più di quello che aggiorni.

"Dovremmo dimenticare le piccole efficienze, diciamo circa il 97% delle volte: l'ottimizzazione prematura è la radice di tutto il male." - Donald Knuth

Answer 2

I vostri schemi di blocco/accesso devono essere dichiarati per valutare correttamente questo. Se ogni thread contenesse solo uno o alcuni blocchi alla volta e la probabilità che due o più thread desiderassero lo stesso blocco allo stesso tempo è bassa (o un accesso casuale o 8 corridori su posizioni diverse su una traccia circolare). correndo all'incirca alla stessa velocità o ad altre cose più complicate), per lo più eviterai il caso peggiore in cui un thread deve dormire per ottenere un blocco (o in alcuni casi deve coinvolgere il sistema operativo per decidere chi vince) perché hai così pochi fili e tante serrature.

Se ogni thread può richiedere centinaia o migliaia di blocchi in qualsiasi momento, le cose inizieranno a cambiare.

Non toccherò l'eliminazione del deadlock perché non so nulla del contenitore che si sta utilizzando, ma è necessario essere consapevoli della necessità di evitarli.