ArrayBlockingQueue utilizza un unico blocco per l'inserimento e la rimozione ma LinkedBlockingQueue utilizza 2 blocchi separati

Question

Stavo passando attraverso il codice sorgente di ArrayBlockingQueue e LinkedBlockingQueue. LinkedBlockingQueue ha un putLock e un takeLock rispettivamente per l'inserimento e la rimozione, ma ArrayBlockingQueue utilizza solo 1 blocco. Credo che LinkedBlockingQueue sia stato implementato in base alla progettazione descritta in Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. In questo articolo, menzionano che mantengono un nodo fittizio in modo che gli encouer non debbano mai accedere alla testa e i dequeuers non debbano mai accedere a tail che eviti scenari di deadlock. Mi stavo chiedendo perché ArrayBlockingQueue non prende in prestito la stessa idea e usa invece 2 blocchi.

Answer 1

ArrayBlockingQueue deve evitare di sovrascrivere le voci in modo che sia necessario sapere dove si trova l'inizio e la fine. Un LinkedBlockQueue non ha bisogno di saperlo poiché lascia che il GC si preoccupi di ripulire i nodi nella coda.

Answer 2

Mi chiedevo perché ArrayBlockingQueue non prende in prestito la stessa idea e utilizza invece 2 blocchi.

Poiché lo ArrayBlockingQueue utilizza una struttura dati molto più semplice per contenere gli elementi della coda.

Il ArrayBlockingQueue memorizza i dati in un array private final E[] items;. Affinché più thread possano gestire lo stesso spazio di archiviazione, se si aggiunge o si rimuove dalla coda, devono utilizzare lo stesso blocco. Questo non è solo a causa della barriera di memoria, ma a causa della protezione mutex poiché stanno modificando lo stesso array.

LinkedBlockingQueue d'altra parte è un elenco collegato di elementi di coda che è completamente diverso e consente la possibilità di avere un doppio blocco. È la memoria interna degli elementi nella coda che ha abilitato le diverse configurazioni di blocco.

Answer 3

Penso che sia possibile per ABQ prendere in prestito la stessa idea di LBQ. Si prega di fare riferimento al mio codice http://pastebin.com/ZD1uFy7S e una domanda simile ho chiesto su SO ArrayBlockingQueue: concurrent put and take.

Il motivo per cui non l'hanno usato, è principalmente a causa della complessità nell'implementazione, in particolare gli iteratori e il compromesso tra complessità e guadagno in termini di prestazioni non era così redditizio.

Per ulteriori riferimenti si prega di dare un'occhiata a http://jsr166-concurrency.10961.n7.nabble.com/ArrayBlockingQueue-concurrent-put-and-take-tc1306.html.

Answer 4

2 blocchi sono utilizzati in LBQ per limitare l'accesso alla testa e bloccare contemporaneamente. Il blocco della testa non consente di rimuovere contemporaneamente due elementi e il blocco della coda non consente l'aggiunta simultanea di due elementi alla coda. i due blocchi insieme impediscono le razze.