Concorrenza Java: CAS vs Blocco

Question

Sto leggendo il libro Concorrenza Java in pratica. Nel capitolo 15, stanno parlando degli algoritmi di non blocco e del metodo confronto-e-swap (CAS).

È scritto che i CAS funzionano molto meglio dei metodi di blocco. Voglio chiedere alle persone che hanno già lavorato con entrambi questi concetti e mi piacerebbe sentire quando preferisci quale di questi concetti? È davvero molto più veloce?

Per me, l'utilizzo di serrature è molto più chiaro e più facile da capire e forse anche meglio per mantenere (per favore correggetemi se sbaglio). Dovremmo davvero concentrarci sulla creazione del nostro codice concorrente correlato al CAS rispetto ai lucchetti per ottenere un incremento delle prestazioni migliore o la sostenibilità è più importante?

So che forse non c'è una regola rigida quando usare cosa. Ma vorrei solo sentire alcune opinioni, esperienze con il nuovo concetto di CAS.

Answer 1

CAS è generalmente molto più veloce del blocco, ma dipende dal grado di contesa. Poiché CAS può forzare un nuovo tentativo se il valore cambia tra la lettura e il confronto, un thread può teoricamente rimanere bloccato in un busy-wait se la variabile in questione viene colpita duramente da molti altri thread (o se è costoso calcolare un nuovo valore dal vecchio valore (o entrambi)).

Il problema principale con CAS è che è molto più difficile da programmare correttamente rispetto al blocco. Intendiamoci, il blocco è, a sua volta, molto più difficile da usare correttamente rispetto al passaggio dei messaggi o allo STM, quindi non considerare questo come un segnale acustico per l'uso dei lucchetti.

Answer 2

È possibile osservare i numeri tra un ConcurrentLinkedQueue e un BlockingQueue. Quello che vedrete è che CAS è notevolmente più veloce con moderato (più realistico nelle applicazioni del mondo reale) thread conention.

La proprietà più interessante degli algoritmi di non blocco è il fatto che se un thread fallisce (cache miss o, peggio, seg fault), altri thread non noteranno questo errore e potranno continuare. Tuttavia, quando si acquisisce un blocco, se il thread di blocco ha qualche tipo di errore del sistema operativo, ogni altro thread in attesa del rilascio del blocco verrà colpito anche dall'errore.

Per rispondere alle vostre domande, sì algoritmi o insiemi di thread sicuri non bloccanti (ConcurrentLinkedQueue, ConcurrentSkipListMap/Set) possono essere notevolmente più veloci rispetto ai loro equivalenti di blocco. Come ha fatto notare Marcelo, ottenere algoritmi non bloccanti è molto difficile e richiede molta considerazione.

Si dovrebbe leggere su Michael and Scott Queue, questa è l'implementazione della coda per ConcurrentLinkedQueue e spiega come gestire una funzione atomica bidirezionale, thread-safe con un singolo CAS.

Answer 3

C'è buon libro fortemente legato al tema della concorrenza senza blocchi: "L'arte di programmazione multi-processore" di Maurice Herlihy

Answer 4

la velocità relativa delle operazioni è in gran parte un non-problema. Ciò che è rilevante è la differenza nella scalabilità tra algoritmi basati su lock e non bloccanti. E se stai usando un sistema core 1 o 2, smetti di pensare a queste cose.

Gli algoritmi di nonblocco generalmente scalano meglio perché hanno "sezioni critiche" più brevi rispetto agli algoritmi basati su lock.

Answer 5

Se stai cercando un confronto con il mondo reale, eccone uno. La nostra applicazione ha due (2) thread 1) Un thread di lettore per l'acquisizione di pacchetti di rete e 2) un thread di consumo che prende il pacchetto, lo conta e riporta le statistiche.

discussione # 1 scambi un singolo pacchetto alla volta con filo # 2

Risultato # 1 - utilizza una conversione basato CAS personalizzato utilizzando gli stessi principi SynchronousQueue, dove la nostra classe si chiama CASSynchronousQueue:

30,766,538 packets in 59.999 seconds :: 500.763Kpps, 1.115Gbps 0 drops 
libpcap statistics: recv=61,251,128, drop=0(0.0%), ifdrop=0 

Risultato # 2 - quando si sostituisce la nostra implementazione CAS con la Java Standard S ynchronousQueue:

8,782,647 packets in 59.999 seconds :: 142.950Kpps, 324.957Mbps 0 drops 
libpcap statistics: recv=69,955,666, drop=52,369,516(74.9%), ifdrop=0 

non credo che la differenza di prestazioni non potrebbe essere più chiaro.