Implementazioni della struttura dati LIFO thread-safe

1. Introduzione

In questo tutorial, discuteremo varie opzioni per le implementazioni della struttura dati LIFO thread-safe .

Nella struttura dati LIFO, gli elementi vengono inseriti e recuperati secondo il principio Last-In-First-Out. Ciò significa che l'ultimo elemento inserito viene recuperato per primo.

In informatica, stack è il termine usato per riferirsi a tale struttura di dati.

Uno stack è utile per affrontare alcuni problemi interessanti come la valutazione di espressioni, l'implementazione di operazioni di annullamento, ecc. Poiché può essere utilizzato in ambienti di esecuzione simultanea, potrebbe essere necessario renderlo thread-safe.

2. Capire le pile

Fondamentalmente, uno Stack deve implementare i seguenti metodi:

  1. push () - aggiunge un elemento in alto
  2. pop () - recupera e rimuove l'elemento superiore
  3. peek () - recupera l'elemento senza rimuoverlo dal contenitore sottostante

Come discusso in precedenza, supponiamo di volere un motore di elaborazione dei comandi.

In questo sistema, l'annullamento dei comandi eseguiti è una caratteristica importante.

In generale, tutti i comandi vengono inseriti nello stack e quindi l'operazione di annullamento può essere semplicemente implementata:

  • metodo pop () per ottenere l'ultimo comando eseguito
  • chiama il metodo undo () sull'oggetto comando estratto

3. Comprensione della sicurezza dei fili nelle pile

Se una struttura dati non è thread-safe, quando vi si accede contemporaneamente, potrebbe finire per avere condizioni di competizione .

Le race condition, in poche parole, si verificano quando la corretta esecuzione del codice dipende dai tempi e dalla sequenza dei thread. Ciò accade principalmente se più di un thread condivide la struttura dei dati e questa struttura non è progettata per questo scopo.

Esaminiamo un metodo di seguito da una classe Java Collection, ArrayDeque :

public E pollFirst() { int h = head; E result = (E) elements[h]; // ... other book-keeping operations removed, for simplicity head = (h + 1) & (elements.length - 1); return result; }

Per spiegare la potenziale condizione di competizione nel codice precedente, supponiamo che due thread eseguano questo codice come indicato nella sequenza seguente:

  • Il primo thread esegue la terza riga: imposta l'oggetto risultato con l'elemento all'indice 'head'
  • Il secondo thread esegue la terza riga: imposta l'oggetto risultato con l'elemento all'indice 'head'
  • Il primo thread esegue la quinta riga: reimposta l'indice "head" all'elemento successivo nell'array di supporto
  • Il secondo thread esegue la quinta riga: reimposta l'indice "head" all'elemento successivo nell'array di supporto

Oops! Ora, entrambe le esecuzioni restituiranno lo stesso oggetto risultato .

Per evitare tali condizioni di competizione, in questo caso, un thread non dovrebbe eseguire la prima riga finché l'altro thread non finisce di reimpostare l'indice 'head' alla quinta riga. In altre parole, l'accesso all'elemento all'indice "head" e il ripristino dell'indice "head" dovrebbero avvenire in modo atomico per un thread.

Chiaramente, in questo caso, la corretta esecuzione del codice dipende dalla tempistica dei thread e quindi non è thread-safe.

4. Stack thread-safe utilizzando lucchetti

In questa sezione, discuteremo due possibili opzioni per implementazioni concrete di uno stack thread-safe .

In particolare, tratteremo lo Stack Java e un ArrayDeque decorato thread-safe .

Entrambi utilizzano i blocchi per l'accesso che si escludono a vicenda .

4.1. Utilizzando lo Stack Java

Java Collections ha un'implementazione legacy per Stack thread-safe , basata su Vector che è fondamentalmente una variante sincronizzata di ArrayList.

Tuttavia, il documento ufficiale stesso suggerisce di considerare l'utilizzo di ArrayDeque . Quindi non entreremo troppo nei dettagli.

Although the Java Stack is thread-safe and straight-forward to use, there are major disadvantages with this class:

  • It doesn't have support for setting the initial capacity
  • It uses locks for all the operations. This might hurt the performance for single threaded executions.

4.2. Using ArrayDeque

Using the Deque interface is the most convenient approach for LIFO data structures as it provides all the needed stack operations.ArrayDeque is one such concrete implementation.

Since it's not using locks for the operations, single-threaded executions would work just fine. But for multi-threaded executions, this is problematic.

However, we can implement a synchronization decorator for ArrayDeque. Though this performs similarly to Java Collection Framework's Stack class, the important issue of Stack class, lack of initial capacity setting, is solved.

Let's have a look at this class:

public class DequeBasedSynchronizedStack { // Internal Deque which gets decorated for synchronization. private ArrayDeque dequeStore; public DequeBasedSynchronizedStack(int initialCapacity) { this.dequeStore = new ArrayDeque(initialCapacity); } public DequeBasedSynchronizedStack() { dequeStore = new ArrayDeque(); } public synchronized T pop() { return this.dequeStore.pop(); } public synchronized void push(T element) { this.dequeStore.push(element); } public synchronized T peek() { return this.dequeStore.peek(); } public synchronized int size() { return this.dequeStore.size(); } }

Note that our solution does not implement Deque itself for simplicity, as it contains many more methods.

Also, Guava contains SynchronizedDeque which is a production-ready implementation of a decorated ArrayDequeue.

5. Lock-free Thread-safe Stacks

ConcurrentLinkedDeque is a lock-free implementation of Deque interface. This implementation is completely thread-safe as it uses an efficient lock-free algorithm.

Lock-free implementations are immune to the following issues, unlike lock based ones.

  • Priority inversion – This occurs when the low-priority thread holds the lock needed by a high priority thread. This might cause the high-priority thread to block
  • Deadlocks – This occurs when different threads lock the same set of resources in a different order.

On top of that, Lock-free implementations have some features which make them perfect to use in both single and multi-threaded environments.

  • Per le strutture dati non condivise e per l' accesso a thread singolo, le prestazioni sarebbero alla pari con ArrayDeque
  • Per le strutture dati condivise, le prestazioni variano in base al numero di thread che accedono simultaneamente .

E in termini di usabilità, non è diverso da ArrayDeque poiché entrambi implementano l' interfaccia Deque .

6. Conclusione

In questo articolo, abbiamo discusso la struttura dei dati dello stack e i suoi vantaggi nella progettazione di sistemi come il motore di elaborazione dei comandi e gli analizzatori di espressioni.

Inoltre, abbiamo analizzato varie implementazioni dello stack nel framework delle raccolte Java e discusso le loro prestazioni e le sfumature della sicurezza dei thread.

Come al solito, è possibile trovare esempi di codice su GitHub.