Implementazione di un Ring Buffer in Java

1. Panoramica

In questo tutorial, impareremo come implementare un Ring Buffer in Java.

Ring Buffer

Ring Buffer (o Circular Buffer) è una struttura dati circolare delimitata che viene utilizzata per il buffering dei dati tra due o più thread. Continuando a scrivere in un ring buffer, esso si avvolge quando raggiunge la fine.

2.1. Come funziona

Un Ring Buffer è implementato usando un array di dimensioni fisse che si avvolge ai confini.

Oltre all’array, tiene traccia di tre cose:

• il prossimo slot disponibile nel buffer per inserire un elemento,
• il prossimo elemento non letto nel buffer,
• e la fine dell’array – il punto in cui il buffer si avvolge all’inizio dell’array

La meccanica di come un ring buffer gestisce questi requisiti varia con l’implementazione. Per esempio, la voce di Wikipedia sull’argomento mostra un metodo che usa quattro puntatori.

Prenderemo in prestito l’approccio dall’implementazione di Disruptor del ring buffer usando sequenze.

La prima cosa che dobbiamo sapere è la capacità – la dimensione massima fissa del buffer. Poi, useremo due sequenze monotonicamente crescenti:

• Scrittura della sequenza: inizia a -1, aumenta di 1 quando inseriamo un elemento
• Lettura della sequenza: inizia a 0, aumenta di 1 quando consumiamo un elemento

Possiamo mappare una sequenza ad un indice nell’array usando un’operazione mod:

arrayIndex = sequence % capacity

L’operazione mod avvolge la sequenza intorno ai confini per ricavare uno slot nel buffer:

Vediamo come inserire un elemento:

buffer = element

Preincrementiamo la sequenza prima di inserire un elemento.

Per consumare un elemento facciamo un post-incremento:

element = buffer

In questo caso, eseguiamo un post-incremento sulla sequenza. Consumare un elemento non lo rimuove dal buffer – rimane semplicemente nell’array finché non viene sovrascritto.

2.2. Buffer vuoti e pieni

Come ci avvolgiamo intorno all’array, inizieremo a sovrascrivere i dati nel buffer. Se il buffer è pieno, possiamo scegliere di sovrascrivere i dati più vecchi indipendentemente dal fatto che il lettore li abbia consumati o evitare di sovrascrivere i dati che non sono stati letti.

Se il lettore può permettersi di perdere i valori intermedi o vecchi (per esempio, un ticker del prezzo delle azioni), possiamo sovrascrivere i dati senza aspettare che vengano consumati. D’altra parte, se il lettore deve consumare tutti i valori (come nelle transazioni di commercio elettronico), dovremmo aspettare (block/busy-wait) che il buffer abbia uno slot disponibile.

Il buffer è pieno se la dimensione del buffer è uguale alla sua capacità, dove la sua dimensione è uguale al numero di elementi non letti:

size = (writeSequence - readSequence) + 1isFull = (size == capacity)

Se la sequenza di scrittura è in ritardo rispetto alla sequenza di lettura, il buffer è vuoto:

isEmpty = writeSequence < readSequence

Il buffer ritorna un valore nullo se è vuoto.

2.2. Vantaggi e svantaggi

Un ring buffer è un efficiente buffer FIFO. Utilizza una matrice di dimensioni fisse che può essere preallocata in anticipo e permette un efficiente schema di accesso alla memoria. Tutte le operazioni del buffer sono a tempo costante O(1), compreso il consumo di un elemento, poiché non richiede uno spostamento di elementi.

Al rovescio, determinare la dimensione corretta del ring buffer è fondamentale. Per esempio, le operazioni di scrittura possono bloccarsi a lungo se il buffer è sottodimensionato e le letture sono lente. Possiamo usare un dimensionamento dinamico, ma richiederebbe lo spostamento dei dati e perderemmo la maggior parte dei vantaggi discussi sopra.

Implementazione in Java

Ora che abbiamo capito come funziona un ring buffer, procediamo ad implementarlo in Java.

3.1. Inizializzazione

Primo, definiamo un costruttore che inizializzi il buffer con una capacità predefinita:

public CircularBuffer(int capacity) { this.capacity = (capacity < 1) ? DEFAULT_CAPACITY : capacity; this.data = (E) new Object; this.readSequence = 0; this.writeSequence = -1;}

Questo creerà un buffer vuoto e inizializzerà i campi sequenza come discusso nella sezione precedente.

3.2. Offer

Prossimo, implementeremo l’operazione offer che inserisce un elemento nel buffer al prossimo slot disponibile e restituisce true al successo. Restituisce false se il buffer non trova uno slot vuoto, cioè non possiamo sovrascrivere valori non letti.

Implementiamo il metodo offer in Java:

public boolean offer(E element) { boolean isFull = (writeSequence - readSequence) + 1 == capacity; if (!isFull) { int nextWriteSeq = writeSequence + 1; data = element; writeSequence++; return true; } return false;}

Allora, incrementiamo la sequenza di scrittura e calcoliamo l’indice nell’array per il prossimo slot disponibile. Poi, scriviamo i dati nel buffer e memorizziamo la sequenza di scrittura aggiornata.

Proviamola:

@Testpublic void givenCircularBuffer_whenAnElementIsEnqueued_thenSizeIsOne() { CircularBuffer buffer = new CircularBuffer<>(defaultCapacity); assertTrue(buffer.offer("Square")); assertEquals(1, buffer.size());}

3.3. Poll

Infine, implementeremo l’operazione di polling che recupera e rimuove il prossimo elemento non letto. L’operazione di polling non rimuove l’elemento ma incrementa la sequenza di lettura.

Implementiamo:

public E poll() { boolean isEmpty = writeSequence < readSequence; if (!isEmpty) { E nextValue = data; readSequence++; return nextValue; } return null;}

Qui, stiamo leggendo i dati nella sequenza di lettura corrente calcolando l’indice nell’array. Poi, incrementiamo la sequenza e restituiamo il valore, se il buffer non è vuoto.

Proviamolo:

@Testpublic void givenCircularBuffer_whenAnElementIsDequeued_thenElementMatchesEnqueuedElement() { CircularBuffer buffer = new CircularBuffer<>(defaultCapacity); buffer.offer("Triangle"); String shape = buffer.poll(); assertEquals("Triangle", shape);}

Producer-Consumer Problem

Abbiamo parlato dell’uso di un ring buffer per lo scambio di dati tra due o più thread, che è un esempio di un problema di sincronizzazione chiamato Producer-Consumer problem. In Java, possiamo risolvere il problema produttore-consumatore in vari modi usando semafori, code limitate, ring buffer, ecc.

Implementiamo una soluzione basata su un ring buffer.

4.1. Volatile Sequence Fields

La nostra implementazione del ring buffer non è thread-safe. Rendiamola thread-safe per il semplice caso di singolo produttore e singolo consumatore.

Il produttore scrive dati nel buffer e incrementa la writeSequence, mentre il consumatore legge solo dal buffer e incrementa la readSequence. Quindi, l’array di supporto è libero da contese e possiamo cavarcela senza alcuna sincronizzazione.

Ma dobbiamo ancora assicurarci che il consumatore possa vedere l’ultimo valore del campo writeSequence (visibilità) e che la writeSequence non sia aggiornata prima che i dati siano effettivamente disponibili nel buffer (ordinamento).

Possiamo rendere il buffer ad anello concorrente e privo di lock in questo caso rendendo i campi della sequenza volatili:

private volatile int writeSequence = -1, readSequence = 0;

Nel metodo dell’offerta, una scrittura al campo volatile writeSequence garantisce che le scritture al buffer avvengano prima di aggiornare la sequenza. Allo stesso tempo, la garanzia di visibilità volatile assicura che il consumatore vedrà sempre l’ultimo valore di writeSequence.

4.2. Producer

Implementiamo un semplice Runnable produttore che scrive sul ring buffer:

public void run() { for (int i = 0; i < items.length;) { if (buffer.offer(items)) { System.out.println("Produced: " + items); i++; } }}

Il thread produttore aspetterebbe uno slot vuoto in un ciclo (busy-waiting).

4.3. Consumatore

Impiegheremo un Callable consumatore che legge dal buffer:

public T call() { T items = (T) new Object; for (int i = 0; i < items.length;) { T item = buffer.poll(); if (item != null) { items = item; System.out.println("Consumed: " + item); } } return items;}

Il thread consumatore continua senza stampare se riceve un valore nullo dal buffer.

Scriviamo il codice del nostro driver:

executorService.submit(new Thread(new Producer<String>(buffer)));executorService.submit(new Thread(new Consumer<String>(buffer)));

L’esecuzione del nostro programma produttore-consumatore produce un output come quello che segue:

Produced: CircleProduced: Triangle Consumed: CircleProduced: Rectangle Consumed: Triangle Consumed: RectangleProduced: SquareProduced: Rhombus Consumed: SquareProduced: Trapezoid Consumed: Rhombus Consumed: TrapezoidProduced: PentagonProduced: PentagramProduced: Hexagon Consumed: Pentagon Consumed: PentagramProduced: Hexagram Consumed: Hexagon Consumed: Hexagram

Conclusione

In questo tutorial, abbiamo imparato come implementare un Ring Buffer ed esplorato come può essere usato per risolvere il problema produttore-consumatore.