Come posso scrivere una struttura senza blocchi?

Question

Nella mia applicazione multithread vedo un forte conflitto di blocchi, che impedisce una buona scalabilità su più core.Ho deciso di utilizzare la programmazione senza blocchi per risolvere questo problema.

Come posso scrivere una struttura senza blocchi?

Answer 1

La risposta breve è:

Non puoi.

La risposta lunga è:

Se ti stai ponendo questa domanda, probabilmente non ne sai abbastanza per poter creare una struttura senza blocchi.Creare strutture senza blocchi è estremamente difficile e solo gli esperti in questo campo possono farlo.Invece di scriverne uno tuo, cerca un'implementazione esistente.Quando lo trovi, controlla quanto è ampiamente utilizzato, quanto è ben documentato, se è ben provato, quali sono le limitazioni - anche alcune strutture senza blocchi pubblicate da altre persone sono rotte.

Se non trovi una struttura priva di blocchi corrispondente alla struttura che stai attualmente utilizzando, adatta piuttosto l'algoritmo in modo da poterne utilizzare uno esistente.

Se insisti ancora nel creare la tua struttura senza blocchi, assicurati di:

• inizia con qualcosa di molto semplice
• comprendere il modello di memoria della piattaforma di destinazione (inclusi i vincoli di riordino di lettura/scrittura, quali operazioni sono atomiche)
• studiare molto sui problemi incontrati da altre persone durante l'implementazione di strutture senza blocchi
• non limitarti a indovinare se funzionerà, dimostralo
• testare pesantemente il risultato

Altre letture:

Blocca algoritmi gratuiti e attendi gratuiti su Wikipedia

Sutter alle erbe:Codice senza serratura:Un falso senso di sicurezza

Answer 2

Utilizza una libreria come Gli elementi costitutivi del threading di Intel, contiene parecchie strutture e algoritmi privi di blocchi.Non consiglierei davvero di tentare di scrivere da solo il codice senza blocchi, è estremamente soggetto a errori e difficile da ottenere correttamente.

Answer 3

Scrivere codice senza blocco thread-safe è difficile;Ma questo articolo di Herb Sutter ti farà iniziare.

Answer 4

COME schietto sottolineato, se tutti gli oggetti sono immutabili, di sola lettura, non devi preoccuparti del blocco, tuttavia, ciò significa che potresti dover copiare molto oggetti.La copia di solito coinvolge malloc e malloc usa il blocco per sincronizzare le allocazioni di memoria tra i thread, quindi gli oggetti immutabili potrebbero costarti meno di quanto pensi (malloc stesso si adatta piuttosto male e malloc è lento;se esegui molto malloc in una sezione critica per le prestazioni, non aspettarti buone prestazioni).

Quando è necessario aggiornare solo variabili semplici (ad es.32 o 64 bit int o puntatori), esegui semplicemente operazioni di addizione o sottrazione su di essi o semplicemente scambia i valori di due variabili, la maggior parte delle piattaforme offre "operazioni atomiche" per questo (inoltre GCC offre anche queste). Atomic non è la stessa cosa di thread-safe.Tuttavia, atomic si assicura che se, ad esempio, un thread scrive un valore a 64 bit in una posizione di memoria e un altro thread legge da esso, quello in lettura ottiene il valore prima dell'operazione di scrittura o dopo l'operazione di scrittura, ma mai un rotto valore intermedio tra l'operazione di scrittura (ad es.uno in cui i primi 32 bit sono già i nuovi, gli ultimi 32 bit sono ancora il vecchio valore!Ciò può accadere se non si utilizza l'accesso atomico su tale variabile).

Tuttavia, se hai una struttura C con 3 valori, che desideri aggiornare, anche se li aggiorni tutti e tre con operazioni atomiche, queste sono tre operazioni indipendenti, quindi un lettore potrebbe vedere la struttura con un valore già aggiornato e due non lo sono aggiornato.Qui avrai bisogno di un lucchetto se devi assicurarti che il lettore veda tutti i valori nella struttura come valori vecchi o nuovi.

Un modo per rendere i blocchi scalabili molto migliori è utilizzare i blocchi R/W.In molti casi gli aggiornamenti ai dati sono piuttosto poco frequenti (operazioni di scrittura), ma l'accesso ai dati è molto frequente (lettura dei dati), si pensi alle raccolte (hashtable, alberi).In tal caso i blocchi R/W ti offriranno un enorme guadagno in termini di prestazioni, poiché molti thread possono mantenere un blocco di lettura contemporaneamente (non si bloccheranno a vicenda) e solo se un thread vuole un blocco di scrittura, tutti gli altri thread sono bloccati per il tempo in cui viene eseguito l'aggiornamento.

Il modo migliore per evitare problemi nei thread è non condividere alcun dato tra i thread.Se ogni thread si occupa per la maggior parte del tempo di dati a cui nessun altro thread ha accesso, non sarà necessario alcun blocco per tali dati (e nemmeno operazioni atomiche).Quindi prova a condividere il minor numero di dati possibile tra i thread.Quindi hai solo bisogno di un modo veloce per spostare i dati tra i thread se proprio necessario (ITC, Inter Thread Communication).A seconda del sistema operativo, della piattaforma e del linguaggio di programmazione (purtroppo non ci hai detto nessuno di questi), potrebbero esistere vari metodi potenti per l'ITC.

Infine, un altro trucco per lavorare con i dati condivisi ma senza alcun blocco è assicurarsi che i thread non accedano alle stesse parti dei dati condivisi.Per esempio.se due thread condividono un array, ma uno accederà sempre e solo agli indici pari, l'altro solo agli indici dispari, non è necessario alcun blocco.Oppure se entrambi condividono lo stesso blocco di memoria e uno ne utilizza solo la metà superiore, l'altro solo quella inferiore, non è necessario alcun blocco.Anche se non è detto che ciò porti a buone prestazioni;soprattutto non su CPU multi-core.Le operazioni di scrittura di un thread su questi dati condivisi (in esecuzione su un core) potrebbero forzare lo svuotamento della cache per un altro thread (in esecuzione su un altro core) e questi svuotamenti della cache rappresentano spesso il collo di bottiglia per le applicazioni multithread in esecuzione su moderne CPU multi-core.

Answer 5

Come ha detto alla classe il mio professore (Nir Shavit di "The Art of Multiprocessor Programming"):Per favore, non farlo.Il motivo principale è la testabilità: non è possibile testare il codice di sincronizzazione.Puoi eseguire simulazioni e persino eseguire stress test.Ma nella migliore delle ipotesi è una approssimativa approssimazione.Ciò di cui hai veramente bisogno è la prova della correttezza matematica.E pochissimi sono in grado di capirli, per non parlare di scriverli.Quindi, come avevano detto altri:utilizzare le librerie esistenti. Il blog di Joe Duffy esamina alcune tecniche (sezione 28).Il primo che dovresti provare è la suddivisione degli alberi: suddividi in compiti più piccoli e combinali.

Answer 6

L'immutabilità è un approccio per evitare il blocco.Vedere La discussione di Eric Lippert e l'implementazione di cose come stack e code immutabili.

Answer 7

in re.La risposta di Suma, Maurice Herlithy mostra in The Art of Multiprocessor Programming che in realtà nulla può essere scritto senza lock (vedi capitolo 6).iirc, Ciò comporta essenzialmente la suddivisione delle attività in elementi del nodo di elaborazione (come una chiusura di funzione) e l'accodamento di ciascuno di essi.I thread calcoleranno lo stato seguendo tutti i nodi a partire dall'ultimo memorizzato nella cache.Ovviamente questo potrebbe, nel peggiore dei casi, comportare prestazioni sequenziali, ma ha importanti proprietà senza blocco, prevenendo scenari in cui i thread potrebbero essere programmati per lunghi periodi di tempo quando mantengono i blocchi.Herlithy raggiunge anche prestazioni teoriche senza attesa, il che significa che un thread non finirà per aspettare per sempre per vincere l'accodamento atomico (si tratta di un codice molto complicato).

Una coda/stack multi-thread è sorprendentemente difficile (controlla il file Problema dell'ABA).Altre cose potrebbero essere molto semplici.Abituati a while(true) { atomicCAS finché non l'ho scambiato } blocchi;sono incredibilmente potenti.Un'intuizione di ciò che è corretto con CAS può aiutare lo sviluppo, anche se dovresti usare buoni test e forse strumenti più potenti (forse SCHIZZO, prossimo MIT Kendo, O rotazione?) per verificarne la correttezza se è possibile ridurlo ad una struttura semplice.

Per favore pubblica di più sul tuo problema.È difficile dare una buona risposta senza dettagli.

modificare l'immutabilità è bella ma la sua applicabilità è limitata, se ho capito bene.In realtà non supera i rischi di scrittura dopo lettura;considera due thread che eseguono "mem = NewNode(mem)";potevano leggerlo entrambi e poi scriverlo entrambi;non è corretto per una classica funzione di incremento.Inoltre, probabilmente è lento a causa dell'allocazione dell'heap (che deve essere sincronizzata tra i thread).

Answer 8

L’immutabilità avrebbe questo effetto.Le modifiche all'oggetto danno come risultato un nuovo oggetto.Lisp funziona in questo modo sotto le coperte.

Articolo 13 del Java efficace spiega questa tecnica.

Answer 9

Cliff Click ha condotto alcune importanti ricerche sulle strutture dati prive di blocchi utilizzando macchine a stati finiti e ha anche pubblicato molte implementazioni per Java.Puoi trovare i suoi articoli, diapositive e implementazioni sul suo blog: http://blogs.azulsystems.com/cliff/

Answer 10

Utilizza un'implementazione esistente, poiché quest'area di lavoro è il regno degli esperti del settore e dei dottorandi (se vuoi che sia fatto bene!)

Ad esempio c'è una libreria di codice qui:

http://www.cl.cam.ac.uk/research/srg/netos/lock-free/

Answer 11

La maggior parte degli algoritmi o delle strutture senza blocchi iniziano con alcune operazioni atomiche, ad es.una modifica in una posizione di memoria che una volta iniziata da un thread verrà completata prima che qualsiasi altro thread possa eseguire la stessa operazione.Hai un'operazione del genere nel tuo ambiente?

Vedere Qui per il documento canonico su questo argomento.

Prova anche questo articolo di Wikipedia articolo per ulteriori idee e collegamenti.

Answer 12

Il principio di base per la sincronizzazione senza blocchi è questo:

• ogni volta che stai leggendo la struttura, segui la lettura con un test per vedere se la struttura è stata mutata da quando hai iniziato la lettura, e riprova finché non riesci a leggere senza che qualcos'altro arrivi e muti mentre lo fai;

• ogni volta che si modifica la struttura, si organizzano l'algoritmo e i dati in modo che ci sia un singolo passaggio atomico che, se eseguito, fa sì che l'intera modifica diventi visibile agli altri thread e si organizzano le cose in modo che nessuna modifica sia visibile a meno che quel passo è fatto.Utilizzi qualsiasi meccanismo atomico senza blocco esistente sulla tua piattaforma per quel passaggio (ad es.confronta e imposta, carica collegato+memorizza condizionale, ecc.).In quel passaggio devi quindi verificare se qualche altro thread ha modificato l'oggetto dall'inizio dell'operazione di mutazione, eseguire il commit in caso contrario e ricominciare da capo se lo ha fatto.

Ci sono moltissimi esempi di strutture senza lucchetti sul web;senza sapere di più su cosa stai implementando e su quale piattaforma è difficile essere più specifici.

Answer 13

Se stai scrivendo le tue strutture dati senza blocchi per una CPU multi-core, non dimenticare le barriere di memoria!Inoltre, considera di esaminare Memoria delle transazioni software tecniche.

Answer 14

Beh, dipende dal tipo di struttura, ma devi fare in modo che la struttura rilevi e gestisca attentamente e silenziosamente eventuali conflitti.

Dubito che tu possa realizzarne uno privo di blocchi al 100%, ma, ancora una volta, dipende dal tipo di struttura che devi costruire.

Potrebbe anche essere necessario suddividere la struttura in modo che più thread funzionino su singoli elementi e quindi sincronizzarli/ricombinarli successivamente.

Answer 15

Come accennato, dipende davvero dal tipo di struttura di cui stai parlando.Ad esempio, puoi scrivere una coda senza blocchi limitata, ma non una che consenta l'accesso casuale.

Answer 16

Ridurre o eliminare lo stato mutabile condiviso.

Answer 17

In Java, utilizza i pacchetti java.util.concurrent in JDK 5+ invece di scriverne di tuoi.Come accennato in precedenza, questo è davvero un campo per esperti e, a meno che tu non abbia un anno o due liberi, crearne uno tuo non è un'opzione.

Answer 18

Puoi chiarire cosa intendi per struttura?

In questo momento, suppongo che tu intenda l'architettura complessiva.Puoi realizzarlo non condividendo la memoria tra i processi e utilizzando un modello di attore per i tuoi processi.

Answer 19

Dai un'occhiata al mio collegamento ConcurrentLinkedHashMap per un esempio di come scrivere una struttura dati senza blocchi.Non si basa su documenti accademici e non richiede anni di ricerca come altri suggeriscono.Ci vuole semplicemente un'attenta progettazione.

La mia implementazione utilizza ConcurrentHashMap, che è un algoritmo lock-per-bucket, ma non si basa su tale dettaglio di implementazione.Potrebbe essere facilmente sostituito con l'implementazione senza blocchi di Cliff Click.Ho preso in prestito un'idea da Cliff, ma usata in modo molto più esplicito, è quella di modellare tutte le operazioni CAS con una macchina a stati.Ciò semplifica notevolmente il modello, poiché vedrai che ho pseudo-blocchi tramite gli stati 'ing.Un altro trucco è permettere la pigrizia e risolversi secondo necessità.Lo vedrai spesso tornando indietro o lasciando che altri thread "aiutino" a ripulire.Nel mio caso, ho deciso di consentire che i nodi morti dell'elenco vengano sfrattati quando raggiungono la testa, piuttosto che affrontare la complessità di rimuoverli dal centro dell'elenco.Potrei cambiarlo, ma non mi fidavo completamente del mio algoritmo di backtracking e volevo rimandare un cambiamento importante come l'adozione di un approccio di blocco a 3 nodi.

Il libro "The Art of Multiprocessor Programming" è un ottimo manuale.Nel complesso, tuttavia, consiglierei di evitare progetti senza blocchi nel codice dell'applicazione.Spesso è semplicemente eccessivo laddove altre tecniche, meno soggette a errori, sono più adatte.

Answer 20

Se vedi un conflitto di blocchi, proverei prima a utilizzare blocchi più granulari sulle tue strutture dati piuttosto che algoritmi completamente privi di blocchi.

Ad esempio, attualmente lavoro su un'applicazione multithread, che dispone di un sistema di messaggistica personalizzato (elenco di code per ciascun thread, la coda contiene messaggi da elaborare per il thread) per passare informazioni tra thread.C'è un blocco globale su questa struttura.Nel mio caso, non ho così tanto bisogno di velocità, quindi non ha molta importanza.Ma se questo blocco diventasse un problema, potrebbe essere sostituito, ad esempio, da blocchi individuali su ogni coda.Quindi l'aggiunta/rimozione di elementi alla/dalla coda specifica non influirebbe sulle altre code.Ci sarebbe ancora un blocco globale per l'aggiunta di nuove code e simili, ma non sarebbe così tanto conteso.

Anche una singola coda multi-produzione/consumatore può essere scritta con un blocco granulare su ciascun elemento, invece di avere un blocco globale.Ciò potrebbe anche eliminare la contesa.

Answer 21

Se leggi diverse implementazioni e documenti riguardanti l'argomento, noterai che esiste il seguente tema comune:

1) Gli oggetti con stato condiviso sono immutabili in stile lisp/clojure:cioè tutte le operazioni di scrittura vengono implementate copiando lo stato esistente in un nuovo oggetto, apportando modifiche al nuovo oggetto e quindi tentando di aggiornare lo stato condiviso (ottenuto da un puntatore allineato che può essere aggiornato con la primitiva CAS).In altre parole, non modificherai MAI MAI un oggetto esistente che potrebbe essere letto da più del thread corrente.L'immutabilità può essere ottimizzata utilizzando la semantica Copy-on-Write per oggetti grandi e complessi, ma questo è un altro albero di noci

2) si specifica chiaramente quali transizioni consentite tra lo stato corrente e quello successivo sono valide:Quindi verificare che l'algoritmo sia valido diventa più semplice per ordini di grandezza

3) Gestire i riferimenti scartati negli elenchi di puntatori di pericolo per thread.Una volta che gli oggetti di riferimento sono al sicuro, riutilizzarli se possibile

Vedi un altro mio post correlato in cui parte del codice implementato con semafori e mutex è (parzialmente) reimplementato in uno stile senza blocchi:Mutua esclusione e semafori