Quanto è efficiente bloccare un mutex sbloccato? Qual è il costo di un mutex?

In un linguaggio di basso livello (C, C ++ o qualsiasi altra cosa): ho la possibilità di scegliere tra un gruppo di mutex (come quello che pthread mi dà o qualunque sia la libreria di sistema nativa) o uno singolo per un object.

Quanto è efficace bloccare un mutex? Cioè quante istruzioni assembler ci sono probabilmente e quanto tempo impiegano (nel caso in cui il mutex è sbloccato)?

Quanto costa un mutex? È un problema avere davvero molti mutex? Oppure posso semplicemente inserire tutte le variabili mutex nel mio codice perché ho variabili int e non ha molta importanza?

(Non sono sicuro di quante differenze ci siano tra hardware diversi. Se c’è, mi piacerebbe anche conoscerle, ma soprattutto sono interessato all’hardware comune.)

Il punto è, usando molti mutex che coprono solo una parte dell’object invece di un singolo mutex per l’intero object, potrei tranquillamente molti blocchi. E mi chiedo quanto dovrei andare su questo. Dovrei provare a mettere al sicuro ogni ansible blocco il più lontano ansible, non importa quanto sia molto più complicato e quanto più mutex significhi?

Ho la possibilità di scegliere tra un gruppo di mutex o uno singolo per un object.

Se si hanno molti thread e l’accesso all’object avviene spesso, i blocchi multipli aumenterebbero il parallelismo. Al costo della manutenibilità, dal momento che più blocchi significa più debug del blocco.

Quanto è efficace bloccare un mutex? Cioè quante istruzioni assembler ci sono probabilmente e quanto tempo impiegano (nel caso in cui il mutex è sbloccato)?

Le precise istruzioni assembler sono il minimo sovraccarico di un mutex – le garanzie di coerenza della memoria / cache sono le spese generali principali. E meno spesso viene preso un blocco particolare – meglio.

Mutex è composto da due parti principali (semplificazione eccessiva): (1) un indicatore che indica se il mutex è bloccato o meno e (2) coda di attesa.

Il cambio della bandiera è solo un numero limitato di istruzioni e normalmente viene effettuato senza chiamata di sistema. Se mutex è bloccato, syscall accadrà per aggiungere il thread chiamante nella coda di attesa e avviare l’attesa. Sbloccare, se la coda di attesa è vuota, è economica, ma necessita altrimenti di un syscall per triggersre uno dei processi di attesa. (Su alcuni sistemi syscalls economici / veloci vengono utilizzati per implementare i mutex, diventano chiamate di sistema lente (normali) solo in caso di contesa.)

Il blocco di mutex sbloccato è davvero economico. Sbloccare mutex senza contesa è anche economico.

Quanto costa un mutex? È un problema avere davvero molti mutex? Oppure posso semplicemente inserire tutte le variabili mutex nel mio codice perché ho variabili int e non ha molta importanza?

Puoi inserire tutte le variabili mutex nel tuo codice come desideri. Sei limitato dalla quantità di memoria che l’applicazione può allocare.

Sommario. I blocchi dello spazio utente (e in particolare i mutex) sono economici e non soggetti a limiti di sistema. Ma troppi di loro rappresentano un incubo per il debugging. Tavolo semplice:

  1. Meno blocchi significa più contese (slow syscalls, CPU stall) e minor parallelismo
  2. Meno blocchi significa meno problemi nel debug di problemi multi-thread.
  3. Più serrature significano meno contese e maggiore parallelismo
  4. Più serrature significano più possibilità di imbattersi in deadlock inimmaginabili.

Dovrebbe essere trovato e mantenuto uno schema di blocco bilanciato per l’applicazione, generalmente in equilibrio tra il n. 2 e il n.


(*) Il problema con i mutex meno spesso bloccati è che se si blocca troppo nella propria applicazione, causa gran parte del traffico inter-CPU / core per svuotare la memoria mutex dalla cache di altre CPU per garantire il coerenza della cache. Gli svuotamenti della cache sono come interruzioni leggere e gestiti dalle CPU in modo trasparente, ma introducono le cosiddette stalle (cerca “stallo”).

E le bancarelle sono ciò che rende il codice di blocco per funzionare lentamente, spesso senza alcuna indicazione apparente perché l’applicazione è lenta. (Alcuni arch forniscono le statistiche del traffico inter-CPU / core, altri no.)

Per evitare il problema, le persone ricorrono generalmente a un numero elevato di serrature per ridurre la probabilità di contenimento del blocco e per evitare lo stallo. Questo è il motivo per cui esiste il blocco dello spazio utente economico, non sobject ai limiti del sistema.

Dipende da ciò che chiamate “mutex”, modalità OS e così via.

Almeno è un costo di un’operazione di memoria interbloccata. È un’operazione relativamente pesante (rispetto ad altri primitivi comandi assembler).

Tuttavia, questo può essere molto più alto. Se ciò che chiamate “mutex” è un object kernel (cioè – object gestito dal sistema operativo) ed eseguito in modalità utente – ogni operazione su di esso porta ad una transazione in modalità kernel, che è molto pesante.

Ad esempio sul processore Intel Core Duo, Windows XP. Operazione interbloccata: richiede circa 40 cicli CPU. Chiamata in modalità kernel (cioè chiamata di sistema) – circa 2000 cicli CPU.

In questo caso, puoi prendere in considerazione l’utilizzo di sezioni critiche. È un ibrido di un mutex del kernel e un accesso di memoria interbloccato.

Volevo sapere la stessa cosa, quindi l’ho misurato. Sulla mia scatola (AMD FX ™ -8150 Processore Eight-Core a 3.612361 GHz), il blocco e lo sblocco di un mutex sbloccato che si trova nella propria linea cache ed è già memorizzato nella cache, richiede 47 clocks (13 ns).

A causa della sincronizzazione tra due core (ho usato CPU # 0 e # 1), ho potuto chiamare una coppia di lock / unlock solo una volta ogni 102 ns su due thread, quindi una volta ogni 51 ns, da cui si può concludere che ci vogliono circa 38 ns per ripristinare dopo un thread fa uno sblocco prima che il thread successivo possa bloccarlo di nuovo.

Il programma che ho utilizzato per indagare su questo può essere trovato qui: https://github.com/CarloWood/ai-statefultask-testsuite/blob/b69b112e2e91d35b56a39f41809d3e3de2f9e4b8/src/mutex_test.cxx

Nota che ha alcuni valori hardcoded specifici per il mio box (xrange, yrange e rdtsc overhead), quindi probabilmente dovrai sperimentarlo prima che funzioni per te.

Il grafico che produce in quello stato è:

inserisci la descrizione dell'immagine qui

Questo mostra il risultato delle esecuzioni di benchmark sul seguente codice:

 uint64_t do_Ndec(int thread, int loop_count) { uint64_t start; uint64_t end; int __d0; asm volatile ("rdtsc\n\tshl $32, %%rdx\n\tor %%rdx, %0" : "=a" (start) : : "%rdx"); mutex.lock(); mutex.unlock(); asm volatile ("rdtsc\n\tshl $32, %%rdx\n\tor %%rdx, %0" : "=a" (end) : : "%rdx"); asm volatile ("\n1:\n\tdecl %%ecx\n\tjnz 1b" : "=c" (__d0) : "c" (loop_count - thread) : "cc"); return end - start; } 

Le due chiamate rdtsc misurano il numero di orologi necessari per bloccare e sbloccare `mutex ‘(con un overhead di 39 clock per le chiamate rdtsc sulla mia casella). Il terzo asm è un ciclo di ritardo. La dimensione del ciclo di ritardo è 1 conteggio inferiore per il thread 1 rispetto a quello per il thread 0, quindi il thread 1 è leggermente più veloce.

La funzione di cui sopra è chiamata in un ciclo stretto di dimensioni 100.000. Nonostante la funzione sia leggermente più veloce per il thread 1, entrambi i loop si sincronizzano a causa della chiamata al mutex. Questo è visibile nel grafico dal fatto che il numero di orologi misurati per la coppia di blocco / sblocco è leggermente più grande per la filettatura 1, per tenere conto del ritardo più breve nel ciclo sottostante.

Nel grafico sopra il punto in basso a destra è una misura con un ritardo del loop_count di 150, e quindi seguendo i punti in basso, verso sinistra, il conto del ciclo viene ridotto di uno ogni misura. Quando diventa 77 la funzione viene chiamata ogni 102 ns in entrambi i thread. Se successivamente loop_count viene ridotto ulteriormente, non è più ansible sincronizzare i thread e il mutex inizia a essere bloccato per la maggior parte del tempo, con un conseguente aumento della quantità di clock necessari per eseguire il lock / unlock. Anche il tempo medio della chiamata alla funzione aumenta a causa di ciò; quindi i punti della trama ora salgono di nuovo verso destra.

Da ciò possiamo concludere che bloccare e sbloccare un mutex ogni 50 ns non è un problema sulla mia scatola.

Tutto sumto la mia conclusione è che la risposta alla domanda di OP è che l’aggiunta di più mutex è migliore fintanto che ciò si traduce in una minore contesa.

Prova a bloccare i mutex il più breve ansible. L’unica ragione per metterli -say- al di fuori di un ciclo sarebbe se il ciclo si ripetesse più velocemente di una volta ogni 100 ns (o meglio, il numero di thread che vogliono eseguire quel ciclo nello stesso momento per 50 ns) o quando 13 ns volte la dimensione del loop è più ritardata del ritardo che si ottiene dalla contesa.

EDIT: Sono diventato molto più informato sull’argomento ora e inizio a dubitare della conclusione che ho presentato qui. Prima di tutto, CPU 0 e 1 risultano essere hyper-threaded; anche se AMD afferma di avere 8 core reali, c’è sicuramente qualcosa di molto interessante perché i ritardi tra due altri core sono molto più grandi (ad esempio, 0 e 1 formano una coppia, come fanno 2 e 3, 4 e 5, e 6 e 7 ). In secondo luogo, lo std :: mutex è implementato in modo tale da far girare i blocchi per un po ‘prima di effettuare effettivamente le chiamate di sistema quando non riesce a ottenere immediatamente il blocco su un mutex (che senza dubbio sarà estremamente lento). Quindi quello che ho misurato qui è il situtation assoluto più ideale e in pratica il blocco e lo sblocco potrebbero richiedere drasticamente più tempo per blocco / sblocco.

In conclusione, un mutex è implementato con l’atomica. Per sincronizzare l’atomica tra i core, è necessario bloccare un bus interno che blocca la linea della cache corrispondente per diverse centinaia di cicli di clock. Nel caso in cui non sia ansible ottenere un blocco, è necessario eseguire una chiamata di sistema per mettere il thread in stop; questo è ovviamente estremamente lento. Normalmente non è un problema, perché quel thread deve dormire comunque, ma potrebbe essere un problema con un alto conflitto dove un thread non può ottenere il lock per il tempo che normalmente gira e così fa la chiamata di sistema, ma CAN prendi il lucchetto poco dopo. Ad esempio, se più thread bloccano e sbloccano un mutex in un loop stretto e ognuno mantiene il lock per 1 microsecondo o giù di lì, allora potrebbero essere rallentati enormemente dal fatto che sono costantemente addormentati e svegliati di nuovo.

Il costo varierà a seconda dell’implementazione ma dovresti tenere a mente due cose:

  • il costo sarà probabilmente minimo poiché è un’operazione alquanto primitiva e sarà ottimizzata il più ansible a causa del suo schema di utilizzo (usato molto ).
  • non importa quanto sia costoso dal momento che è necessario utilizzarlo se si desidera un’operazione sicura multi-thread. Se ne hai bisogno, allora ne hai bisogno.

Sui sistemi a processore singolo, generalmente è sufficiente disabilitare gli interrupt per un tempo sufficiente a modificare i dati atomicamente. I sistemi multiprocessore possono utilizzare una strategia test-and-set .

In entrambi i casi, le istruzioni sono relativamente efficienti.

Se sia necessario fornire un singolo mutex per una massiccia struttura di dati, o avere molti mutex, uno per ogni sezione di esso, è un atto di bilanciamento.

Avendo un singolo mutex, si ha un rischio maggiore di contesa tra più thread. Puoi ridurre questo rischio avendo un mutex per sezione ma non vuoi entrare in una situazione in cui un thread deve bloccare 180 mutex per fare il suo lavoro 🙂