Introduzione a strutture dati prive di blocco con esempi Java

1. Introduzione

In questo tutorial, impareremo cosa sono le strutture dati non bloccanti e perché sono un'alternativa importante alle strutture dati simultanee basate su blocchi.

In primo luogo, andremo oltre alcuni termini come priva di ostruzioni , lock-libera e priva di attesa .

In secondo luogo, esamineremo gli elementi costitutivi di base degli algoritmi non bloccanti come CAS (compare-and-swap).

Terzo, esamineremo l'implementazione di una coda senza blocchi in Java e, infine, delineeremo un approccio su come ottenere la libertà di attesa .

2. Lock Versus Starvation

Per prima cosa, diamo un'occhiata alla differenza tra un thread bloccato e uno affamato.

Nell'immagine sopra, Thread 2 acquisisce un blocco sulla struttura dei dati. Quando il thread 1 tenta di acquisire anche un blocco, è necessario attendere finché il thread 2 non rilascia il blocco; non procederà prima di poter ottenere il blocco. Se sospendiamo il thread 2 mentre tiene il blocco, il thread 1 dovrà attendere per sempre.

L'immagine successiva mostra la fame di thread:

Qui, il thread 2 accede alla struttura dei dati ma non acquisisce un blocco. Il thread 1 tenta di accedere contemporaneamente alla struttura dei dati, rileva l'accesso simultaneo e ritorna immediatamente, informando il thread che non è stato possibile completare (in rosso) l'operazione. Il thread 1 riproverà quindi fino a quando non riesce a completare l'operazione (verde).

Il vantaggio di questo approccio è che non abbiamo bisogno di una serratura. Tuttavia, ciò che può accadere è che se il Thread 2 (o altri thread) accede alla struttura dei dati con alta frequenza, il Thread 1 necessita di un numero elevato di tentativi finché non riesce finalmente. Chiamiamo questa fame.

Più avanti vedremo come l'operazione di confronto e scambio raggiunge un accesso non bloccante.

3. Tipi di strutture dati non bloccanti

Possiamo distinguere tra tre livelli di strutture dati non bloccanti.

3.1. Senza ostruzioni

La libertà dagli ostacoli è la forma più debole di una struttura dati non bloccante. Qui, richiediamo solo che un thread sia garantito per procedere se tutti gli altri thread sono sospesi .

Più precisamente, un thread non continuerà a morire di fame se tutti gli altri thread vengono sospesi. Questo è diverso dall'uso dei blocchi in questo senso, che se il thread era in attesa di un blocco e un thread che contiene il blocco è sospeso, il thread in attesa aspetterebbe per sempre.

3.2. Senza blocco

Una struttura dati fornisce la libertà di blocco se, in qualsiasi momento, almeno un thread può procedere . Tutti gli altri thread potrebbero morire di fame. La differenza rispetto alla libertà dall'ostruzione è che c'è almeno un filo che non muore di fame anche se nessun filo è sospeso.

3.3. Senza aspettare

Una struttura dati è priva di attese se è priva di blocchi e ogni thread è garantito per procedere dopo un numero finito di passaggi, ovvero i thread non moriranno di fame per un numero "irragionevolmente elevato" di passaggi.

3.4. Sommario

Riassumiamo queste definizioni nella rappresentazione grafica:

La prima parte dell'immagine mostra la libertà di ostruzione poiché il thread 1 (thread superiore) può procedere (freccia verde) non appena sospendiamo gli altri thread (in basso in giallo).

La parte centrale mostra la libertà di blocco. Almeno il thread 1 può progredire mentre altri potrebbero morire di fame (freccia rossa).

L'ultima parte mostra la libertà di attesa. Qui, garantiamo che il thread 1 può continuare (freccia verde) dopo un certo periodo di fame (frecce rosse).

4. Primitive non bloccanti

In questa sezione, esamineremo tre operazioni di base che ci aiutano a creare operazioni senza blocchi sulle strutture di dati.

4.1. Confronta e scambia

Una delle operazioni di base utilizzate per evitare il blocco è l'operazione di confronto e scambio (CAS) .

L'idea di compare-and-swap è che una variabile viene aggiornata solo se ha ancora lo stesso valore di quando avevamo recuperato il valore della variabile dalla memoria principale. CAS è un'operazione atomica, il che significa che il recupero e l'aggiornamento insieme sono un'unica operazione :

Qui, entrambi i thread recuperano il valore 3 dalla memoria principale. Il thread 2 ha esito positivo (verde) e aggiorna la variabile a 8. Poiché il primo CAS del thread 1 prevede che il valore sia ancora 3, il CAS non riesce (rosso). Pertanto, il thread 1 recupera nuovamente il valore e il secondo CAS riesce.

La cosa importante qui è che CAS non acquisisce un blocco sulla struttura dei dati ma restituisce true se l'aggiornamento ha avuto successo, altrimenti restituisce false .

Lo snippet di codice seguente illustra come funziona CAS:

volatile int value; boolean cas(int expectedValue, int newValue) { if(value == expectedValue) { value = newValue; return true; } return false; }

Aggiorniamo il valore con il nuovo valore solo se ha ancora il valore atteso, altrimenti restituisce false . Il frammento di codice seguente mostra come chiamare CAS:

void testCas() { int v = value; int x = v + 1; while(!cas(v, x)) { v = value; x = v + 1; } }

Tentiamo di aggiornare il nostro valore finché l'operazione CAS non riesce, ovvero restituisce true .

Tuttavia, è possibile che un filo rimanga bloccato dalla fame . Ciò può accadere se altri thread eseguono un CAS sulla stessa variabile allo stesso tempo, quindi l'operazione non avrà mai successo per un particolare thread (o richiederà una quantità di tempo irragionevole per riuscire). Tuttavia, se il confronto e lo scambio fallisce, sappiamo che un altro thread è riuscito, quindi garantiamo anche il progresso globale, come richiesto per la libertà di blocco.

It's important to note that the hardware should support compare-and-swap, to make it a truly atomic operation without the use of locking.

Java provides an implementation of compare-and-swap in the class sun.misc.Unsafe. However, in most cases, we should not use this class directly, but Atomic variables instead.

Furthermore, compare-and-swap does not prevent the A-B-A problem. We'll look at that in the following section.

4.2. Load-Link/Store-Conditional

An alternative to compare-and-swap is load-link/store-conditional. Let's first revisit compare-and-swap. As we've seen before, CAS only updates the value if the value in the main memory is still the value we expect it to be.

However, CAS also succeeds if the value had changed, and, in the meantime, has changed back to its previous value.

The below image illustrates this situation:

Both, thread 1 and Thread 2 read the value of the variable, which is 3. Then Thread 2 performs a CAS, which succeeds in setting the variable to 8. Then again, Thread 2 performs a CAS to set the variable back to 3, which succeeds as well. Finally, Thread 1 performs a CAS, expecting the value 3, and succeeds as well, even though the value of our variable was modified twice in between.

This is called the A-B-A problem. This behavior might not be a problem depending on the use-case, of course. However, it might not be desired for others. Java provides an implementation of load-link/store-conditional with the AtomicStampedReference class.

4.3. Fetch and Add

Another alternative is fetch-and-add. This operation increments the variable in the main memory by a given value. Again, the important point is that the operation happens atomically, which means no other thread can interfere.

Java provides an implementation of fetch-and-add in its atomic classes. Examples are AtomicInteger.incrementAndGet(), which increments the value and returns the new value; and AtomicInteger.getAndIncrement(), which returns the old value and then increments the value.

5. Accessing a Linked Queue from Multiple Threads

To better understand the problem of two (or more) threads accessing a queue simultaneously, let's look at a linked queue and two threads trying to add an element concurrently.

The queue we'll look at is a doubly-linked FIFO queue where we add new elements after the last element (L) and the variable tail points to that last element:

To add a new element, the threads need to perform three steps: 1) create the new elements (N and M), with the pointer to the next element set to null; 2) have the reference to the previous element point to L and the reference to the next element of L point to N (M, respectively). 3) Have tail point to N (M, respectively):

What can go wrong if the two threads perform these steps simultaneously? If the steps in the above picture execute in the order ABCD or ACBD, L, as well as tail, will point to M. N will remain disconnected from the queue.

If the steps execute in the order ACDB, tail will point to N, while L will point to M, which will cause an inconsistency in the queue:

Of course, one way to solve this problem is to have one thread acquire a lock on the queue. The solution we'll look at in the following chapter will solve the problem with the help of a lock-free operation by using the CAS operation we've seen earlier.

6. A Non-Blocking Queue in Java

Let's look at a basic lock-free queue in Java. First, let's look at the class members and the constructor:

public class NonBlockingQueue { private final AtomicReference
    
      head, tail; private final AtomicInteger size; public NonBlockingQueue() { head = new AtomicReference(null); tail = new AtomicReference(null); size = new AtomicInteger(); size.set(0); } }
    

The important part is the declaration of the head and tail references as AtomicReferences, which ensures that any update on these references is an atomic operation. This data type in Java implements the necessary compare-and-swap operation.

Next, let's look at the implementation of the Node class:

private class Node { private volatile T value; private volatile Node next; private volatile Node previous; public Node(T value) { this.value = value; this.next = null; } // getters and setters }

Here, the important part is to declare the references to the previous and next node as volatile. This ensures that we update these references always in the main memory (thus are directly visible to all threads). The same for the actual node value.

6.1. Lock-Free add

Our lock-free add operation will make sure that we add the new element at the tail and won't be disconnected from the queue, even if multiple threads want to add a new element concurrently:

public void add(T element) { if (element == null) { throw new NullPointerException(); } Node node = new Node(element); Node currentTail; do { currentTail = tail.get(); node.setPrevious(currentTail); } while(!tail.compareAndSet(currentTail, node)); if(node.previous != null) { node.previous.next = node; } head.compareAndSet(null, node); // for inserting the first element size.incrementAndGet(); }

The essential part to pay attention to is the highlighted line. We attempt to add the new node to the queue until the CAS operation succeeds to update the tail, which must still be the same tail to which we appended the new node.

6.2. Lock-Free get

Similar to the add-operation, the lock-free get-operation will make sure that we return the last element and move the tail to the current position:

public T get() { if(head.get() == null) { throw new NoSuchElementException(); } Node currentHead; Node nextNode; do { currentHead = head.get(); nextNode = currentHead.getNext(); } while(!head.compareAndSet(currentHead, nextNode)); size.decrementAndGet(); return currentHead.getValue(); }

Again, the essential part to pay attention to is the highlighted line. The CAS operation ensures that we move the current head only if no other node has been removed in the meantime.

Java already provides an implementation of a non-blocking queue, the ConcurrentLinkedQueue. It's an implementation of the lock-free queue from M. Michael and L. Scott described in this paper. An interesting side-note here is that the Java documentation states that it's a wait-free queue, where it's actually lock-free. The Java 8 documentation correctly calls the implementation lock-free.

7. Wait-Free Queues

As we've seen, the above implementation is lock-free, however, not wait-free. The while loops in both the add and get method can potentially loop for a long time (or, though unlikely, forever) if there are many threads accessing our queue.

How can we achieve wait-freedom? The implementation of wait-free algorithms, in general, is quite tricky. We refer the interested reader to this paper, which describes a wait-free queue in detail. In this article, let's look at the basic idea of how we can approach a wait-free implementation of a queue.

A wait-free queue requires that every thread makes guaranteed progress (after a finite number of steps). In other words, the while loops in our add and get methods must succeed after a certain number of steps.

In order to achieve that, we assign a helper thread to every thread. If that helper thread succeeds to add an element to the queue, it will help the other thread to insert its element before inserting another element.

As the helper thread has a helper itself, and, down the whole list of threads, every thread has a helper, we can guarantee that a thread succeeds the insertion latest after every thread has done one insertion. The following figure illustrates the idea:

Of course, things become more complicated when we can add or remove threads dynamically.

8. Conclusion

In questo articolo abbiamo visto i fondamenti delle strutture dati non bloccanti. Abbiamo spiegato i diversi livelli e le operazioni di base come il confronto e lo scambio .

Quindi, abbiamo esaminato un'implementazione di base di una coda senza blocchi in Java. Infine, abbiamo delineato l'idea di come ottenere la libertà di attesa .

Il codice sorgente completo per tutti gli esempi in questo articolo è disponibile su GitHub.