Implementacja bufora pierścieniowego w Javie

1. Przegląd

W tym poradniku dowiemy się jak zaimplementować bufor pierścieniowy w Javie.

Bufor pierścieniowy

Bufor pierścieniowy (lub bufor kołowy) jest ograniczoną, kołową strukturą danych, która jest używana do buforowania danych pomiędzy dwoma lub więcej wątkami. Gdy kontynuujemy zapis do bufora pierścieniowego, zawija się on dookoła, gdy dochodzi do końca.

2.1. Jak to działa

Bufor pierścieniowy jest zaimplementowany przy użyciu tablicy o stałym rozmiarze, która zawija się na granicach.

Oprócz tablicy, śledzi on trzy rzeczy:

• kolejnego dostępnego slotu w buforze do wstawienia elementu,
• kolejnego nieprzeczytanego elementu w buforze,
• oraz końca tablicy – punktu, w którym bufor zawija się do początku tablicy

Mechanika tego, jak bufor pierścieniowy radzi sobie z tymi wymaganiami, różni się w zależności od implementacji. Na przykład, wpis w Wikipedii na ten temat pokazuje metodę wykorzystującą four-pointers.

Pożyczymy podejście z implementacji bufora pierścieniowego Disruptora przy użyciu sekwencji.

Pierwszą rzeczą, którą musimy znać, jest pojemność – ustalony maksymalny rozmiar bufora. Następnie użyjemy dwóch monotonicznie rosnących sekwencji:

• Sekwencja zapisu: zaczyna się od -1, zwiększa się o 1, gdy wstawiamy element
• Sekwencja odczytu: zaczyna się od 0, zwiększa się o 1, gdy zużywamy element

Możemy odwzorować sekwencję na indeks w tablicy za pomocą operacji mod:

arrayIndex = sequence % capacity

Operacja mod owija sekwencję wokół granic, aby wyprowadzić slot w buforze:

Zobaczmy, jak wstawilibyśmy element:

buffer = element

Wstępnie zwiększamy sekwencję przed wstawieniem elementu.

Aby skonsumować element wykonujemy postinkrementację:

element = buffer

W tym przypadku wykonujemy postinkrementację sekwencji. Konsumowanie elementu nie usuwa go z bufora – po prostu pozostaje on w tablicy, dopóki nie zostanie nadpisany.

2.2. Puste i pełne bufory

W miarę jak będziemy owijać się wokół tablicy, zaczniemy nadpisywać dane w buforze. Jeśli bufor jest pełny, możemy wybrać albo nadpisanie najstarszych danych bez względu na to, czy czytnik je skonsumował, albo uniemożliwienie nadpisania danych, które nie zostały odczytane.

Jeśli czytnik może sobie pozwolić na pominięcie pośrednich lub starych wartości (na przykład, notowania giełdowe), możemy nadpisać dane bez czekania, aż zostaną skonsumowane. Z drugiej strony, jeśli czytelnik musi skonsumować wszystkie wartości (jak w przypadku transakcji e-commerce), powinniśmy poczekać (block/busy-wait), aż bufor będzie miał dostępny slot.

Bufor jest pełny, jeśli rozmiar bufora jest równy jego pojemności, gdzie jego rozmiar jest równy liczbie nieprzeczytanych elementów:

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

Jeśli sekwencja zapisu pozostaje w tyle za sekwencją odczytu, bufor jest pusty:

isEmpty = writeSequence < readSequence

Bufor zwraca wartość null, jeśli jest pusty.

2.2. Zalety i wady

Bufor pierścieniowy jest wydajnym buforem FIFO. Wykorzystuje tablicę o stałym rozmiarze, która może być wstępnie przydzielona z góry i pozwala na efektywny wzorzec dostępu do pamięci. Wszystkie operacje buforowe są stałym czasem O(1), w tym konsumowanie elementu, ponieważ nie wymaga przesunięcia elementów.

Po stronie przeciwnej, określenie prawidłowego rozmiaru bufora pierścieniowego jest krytyczne. Na przykład operacje zapisu mogą blokować przez długi czas, jeśli bufor jest niewymiarowy, a odczyty są powolne. Możemy użyć dynamicznego wymiarowania, ale wymagałoby to przenoszenia danych i stracilibyśmy większość zalet omówionych powyżej.

Implementacja w Javie

Teraz, gdy rozumiemy, jak działa bufor pierścieniowy, przejdźmy do jego implementacji w Javie.

3.1. Inicjalizacja

Po pierwsze, zdefiniujmy konstruktor, który zainicjalizuje bufor z predefiniowaną pojemnością:

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

Tworzy to pusty bufor i zainicjalizuje pola sekwencji, jak omówiono w poprzedniej sekcji.

3.2. Offer

Następnie zaimplementujemy operację offer, która wstawia element do bufora w następnym dostępnym slocie i zwraca true w przypadku sukcesu. Zwraca ona false, jeśli bufor nie może znaleźć pustego slotu, czyli nie możemy nadpisać nieprzeczytanych wartości.

Zaimplementujmy metodę offer w Javie:

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

Więc inkrementujemy sekwencję zapisu i obliczamy indeks w tablicy dla następnego dostępnego slotu. Następnie zapisujemy dane do bufora i przechowujemy zaktualizowaną sekwencję zapisu.

Wypróbujmy to:

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

3.3. Poll

Na koniec zaimplementujemy operację poll, która pobiera i usuwa następny nieprzeczytany element. Operacja poll nie usuwa elementu, ale inkrementuje sekwencję odczytu.

Zaimplementujmy ją:

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

W tym miejscu odczytujemy dane w bieżącej sekwencji odczytu, obliczając indeks w tablicy. Następnie inkrementujemy sekwencję i zwracamy wartość, jeśli bufor nie jest pusty.

Przetestujmy to:

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

Problem producenta-konsumenta

Mówiliśmy o użyciu bufora pierścieniowego do wymiany danych między dwoma lub więcej wątkami, co jest przykładem problemu synchronizacji zwanego problemem producenta-konsumenta. W Javie możemy rozwiązać problem producenta-konsumenta na różne sposoby, używając semaforów, kolejek ograniczonych, buforów pierścieniowych itp.

Zaimplementujmy rozwiązanie oparte na buforze pierścieniowym.

4.1. lotne pola sekwencji

Nasza implementacja bufora pierścieniowego nie jest bezpieczna dla wątków. Zróbmy go thread-safe dla prostego przypadku pojedynczego producenta i pojedynczego konsumenta.

Producent zapisuje dane do bufora i inkrementuje writeSequence, podczas gdy konsument tylko czyta z bufora i inkrementuje readSequence. Tak więc, tablica podtrzymująca jest wolna od kontencji i możemy uciec bez żadnej synchronizacji.

Ale nadal musimy zapewnić, że konsument może zobaczyć najnowszą wartość pola writeSequence (widoczność) i że writeSequence nie jest aktualizowany, zanim dane są faktycznie dostępne w buforze (zamawianie).

Możemy uczynić bufor pierścieniowy współbieżnym i wolnym od blokad w tym przypadku poprzez uczynienie pól sekwencji lotnymi:

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

W metodzie offer, zapis do lotnego pola writeSequence gwarantuje, że zapisy do bufora zdarzają się przed aktualizacją sekwencji. Jednocześnie gwarancja widoczności volatile zapewnia, że konsument zawsze zobaczy najnowszą wartość writeSequence.

4.2. Producent

Zaimplementujmy prostego producenta Runnable, który zapisuje do bufora pierścieniowego:

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

Wątek producenta czekałby na pusty slot w pętli (busy-waiting).

4.3. Konsument

Zaimplementujemy konsumenta Callable, który odczytuje z bufora:

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

Wątek konsumenta kontynuuje bez drukowania, jeśli otrzyma wartość null z bufora.

Zapiszmy nasz kod sterownika:

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

Wykonanie naszego programu producent-konsument daje wynik jak poniżej:

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

Zakończenie

W tym tutorialu, nauczyliśmy się jak zaimplementować bufor pierścieniowy i zbadaliśmy jak można go wykorzystać do rozwiązania problemu producent-konsument.