Implementering av en ringbuffert i Java

1. Översikt

I den här handledningen lär vi oss hur man implementerar en ringbuffert i Java.

Ringbuffert

Ringbuffert (eller cirkulär buffert) är en avgränsad cirkulär datastruktur som används för att buffra data mellan två eller flera trådar. När vi fortsätter att skriva till en ringbuffert, så rullar den runt när den når slutet.

2.1. Hur den fungerar

En ringbuffert implementeras med hjälp av en array med fast storlek som sveps runt vid gränserna.

Avsevärt från arrayen håller den reda på tre saker:

• nästa tillgängliga plats i bufferten för att infoga ett element,
• nästa olästa element i bufferten,
• och arrayens slut – den punkt där bufferten sveper runt till arrayens början

Mekaniken för hur en ringbuffert hanterar dessa krav varierar med implementationen. Till exempel visar Wikipedias post i ämnet en metod som använder sig av four-pointers.

Vi lånar tillvägagångssättet från Disruptors implementering av ringbufferten med hjälp av sekvenser.

Det första vi behöver veta är kapaciteten – den fasta maximala storleken på bufferten. Därefter använder vi två monotont ökande sekvenser:

• Write Sequence: börjar vid -1, ökas med 1 när vi lägger in ett element
• Read Sequence: börjar vid 0, ökas med 1 när vi konsumerar ett element

Vi kan mappa en sekvens till ett index i arrayen genom att använda en mod-operation:

arrayIndex = sequence % capacity

Mod-operationen sveper sekvensen runt gränserna för att härleda en plats i bufferten:

Vi kan se hur vi skulle infoga ett element:

buffer = element

Vi förincrementerar sekvensen innan vi infogar ett element.

För att konsumera ett element gör vi en post-inkrementering:

element = buffer

I det här fallet utför vi en post-inkrementering på sekvensen. Att konsumera ett element tar inte bort det från bufferten – det stannar bara kvar i matrisen tills det skrivs över.

2.2. Tomma och fulla buffertar

När vi sveper runt arrayen kommer vi att börja skriva över data i bufferten. Om bufferten är full kan vi välja att antingen skriva över de äldsta uppgifterna oavsett om läsaren har förbrukat dem eller förhindra att vi skriver över de uppgifter som inte har lästs.

Om läsaren har råd att missa de mellanliggande eller gamla värdena (t.ex. en aktiekurstittare) kan vi skriva över uppgifterna utan att vänta på att de ska förbrukas. Om läsaren däremot måste konsumera alla värden (t.ex. vid e-handelstransaktioner) bör vi vänta (blockera/busy-wait) tills bufferten har en ledig plats.

Bufferten är full om buffertstorleken är lika med dess kapacitet, där dess storlek är lika med antalet olästa element:

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

Om skrivsekvensen släpar efter lässekvensen är bufferten tom:

isEmpty = writeSequence < readSequence

Bufferten returnerar ett nollvärde om den är tom.

2.2. Fördelar och nackdelar

En ringbuffert är en effektiv FIFO-buffert. Den använder en array med fast storlek som kan förallokeras i förväg och tillåter ett effektivt minnesåtkomstmönster. Alla buffertoperationer har konstant tid O(1), inklusive förbrukning av ett element, eftersom den inte kräver någon förskjutning av element.

På baksidan är det kritiskt att bestämma rätt storlek på ringbufferten. Skrivoperationer kan till exempel blockera under lång tid om bufferten är för liten och läsningarna är långsamma. Vi kan använda dynamisk storlek, men det skulle kräva att data flyttas runt och vi går miste om de flesta av de fördelar som diskuterats ovan.

Implementering i Java

Nu när vi har förstått hur en ringbuffert fungerar, låt oss fortsätta med att implementera den i Java.

3.1. Initialisering

Först definierar vi en konstruktör som initialiserar bufferten med en fördefinierad kapacitet:

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

Detta kommer att skapa en tom buffert och initialisera sekvensfälten enligt vad som diskuterades i det föregående avsnittet.

3.2. Offer

Nästan ska vi implementera offereringsoperationen som infogar ett element i bufferten vid nästa tillgängliga plats och returnerar true vid framgång. Den returnerar falskt om bufferten inte kan hitta en tom plats, det vill säga vi kan inte skriva över olästa värden.

Låt oss implementera offer-metoden i 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;}

Så, vi ökar skrivsekvensen och beräknar indexet i arrayen för nästa tillgängliga plats. Sedan skriver vi data till bufferten och lagrar den uppdaterade skrivsekvensen.

Låt oss prova det:

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

3.3. Poll

Slutligen ska vi implementera poll-operationen som hämtar och tar bort nästa olästa element. Poll-operationen tar inte bort elementet utan ökar den lästa sekvensen.

Låt oss implementera den:

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

Här läser vi data vid den aktuella lässekvensen genom att beräkna indexet i arrayen. Sedan ökar vi sekvensen och returnerar värdet, om bufferten inte är tom.

Låt oss testa det:

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

Producer-Consumer Problem

Vi har talat om användningen av en ringbuffert för att utbyta data mellan två eller flera trådar, vilket är ett exempel på ett synkroniseringsproblem som kallas Producer-Consumer problem. I Java kan vi lösa producent-konsumentproblemet på olika sätt med hjälp av semaforer, avgränsade köer, ringbuffertar etc.

Låt oss implementera en lösning baserad på en ringbuffert.

4.1. Volatila sekvensfält

Vår implementering av ringbufferten är inte trådsäker. Låt oss göra den trådsäker för det enkla fallet med en enda producent och en enda konsument.

Producenten skriver data till bufferten och ökar writeSequence, medan konsumenten bara läser från bufferten och ökar readSequence. Så backing arrayen är fri från konflikter och vi kan klara oss utan synkronisering.

Men vi måste ändå se till att konsumenten kan se det senaste värdet av writeSequence-fältet (synlighet) och att writeSequence inte uppdateras innan data faktiskt finns tillgängliga i bufferten (beställning).

Vi kan göra ringbufferten samtidig och låsfri i det här fallet genom att göra sekvensfälten flyktiga:

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

I offermetoden garanterar en skrivning till det flyktiga fältet writeSequence att skrivningarna till bufferten sker innan sekvensen uppdateras. Samtidigt garanterar den flyktiga synlighetsgarantin att konsumenten alltid kommer att se det senaste värdet av writeSequence.

4.2. Producer

Låt oss implementera en enkel producent Runnable som skriver till ringbufferten:

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

Producenttråden skulle vänta på en tom plats i en slinga (busy-waiting).

4.3. Konsument

Vi implementerar en konsument Callable som läser från bufferten:

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;}

Konsumenttråden fortsätter utan att skriva ut om den får ett nollvärde från bufferten.

Låt oss skriva vår drivrutinskod:

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

Exekvering av vårt producent-konsumentprogram ger utdata som nedan:

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

Slutsats

I den här handledningen har vi lärt oss hur man implementerar en ringbuffert och utforskat hur den kan användas för att lösa producent-konsumentproblemet.