Odpowiedź.

Historia pytania

Bufor cykliczny (ring buffer, circular buffer) często jest stosowany w systemach z ograniczoną pamięcią, sterownikach urządzeń, sieciach i systemach wielozadaniowych. Jego koncepcja była wykorzystywana już na wczesnych etapach rozwoju systemów operacyjnych, kiedy ważne było optymalne wykorzystanie pamięci i unikanie marnowania zasobów na przesuwanie elementów po ich usunięciu.

Problem

Typowe trudności — poprawna obsługa warunków „bufor pełen” i „bufor pusty”, brak zabezpieczeń przed nadpisywaniem danych, skomplikowana synchronizacja w przypadku wielowątkowości. Błędy mogą wystąpić przy pomieszaniu granic i niepoprawnym sprawdzaniu indeksów.

Rozwiązanie

Obiekt bufora cyklicznego jest realizowany jako tablica, z dwoma indeksami (head i tail) i, w razie potrzeby, zmienną licznika lub dodatkowymi mechanizmami do różnicowania stanów „pełen” i „pusty”. Odczyt i zapis wykonywane są modulo rozmiaru bufora.

#define BUF_SIZE 8
char buffer[BUF_SIZE];
int head = 0, tail = 0; // head – zapisujemy, tail – odczytujemy

// Zapis
if (((head + 1) % BUF_SIZE) != tail) {
    buffer[head] = data;
    head = (head + 1) % BUF_SIZE;
} else {
    // Bufor pełen
}

// Odczyt
if (head != tail) {
    char d = buffer[tail];
    tail = (tail + 1) % BUF_SIZE;
}

Kluczowe cechy:

Sprawdzenie granic z użyciem operacji modulo
Rozróżnienie między pustym a pełnym buforem wymaga szczególnej obsługi lub przechowywania liczby elementów
Łatwe do zaimplementowania bez dynamicznego przydzielania pamięci

Pytania z pułapką.

Jak odróżnić całkowicie wypełniony bufor od całkowicie pustego?

Po head == tail najczęściej określa się pusty bufor. Aby stwierdzić, że bufor jest pełny, można pozostawić jedną komórkę wolną lub przechowywać liczbę elementów w wyraźnym liczniku.

Czy można używać bufora w środowisku wielowątkowym bez blokad?

Nie, w standardowym przypadku, przy jednoczesnym odczycie i zapisie, mogą wystąpić wyścigi. Należy używać operacji atomowych lub blokad.

Co się stanie, jeśli nie kontrolować przepełnienia head lub tail?

W przypadku przepełnienia dojdzie do wyjścia poza granice tablicy, co prowadzi do undefined behavior i możliwej korupcji pamięci.

Typowe błędy i anty-wzorce

Brak różnicy między „pełnym” a „pustym” (head == tail), co łamie semantykę działania
Rezygnacja z arytmetyki modulo (błędy w obliczaniu indeksów)
Naruszenie synchronizacji w pracy wielowątkowej

Przykład z życia

Negatywna sytuacja

Programista zaimplementował bufor cykliczny, w którym head == tail uznawano zarówno za „pusty”, jak i „pełny” jednocześnie, przez co sygnał o przepełnieniu został utracony.

Zalety:

Prostota kodu

Wady:

Nie można jednoznacznie oddzielić stanu pełnego od pustego; dane były tracone lub nadpisywane

Pozytywna sytuacja

Zamiast tego dodano zmienną licznika elementów lub zarezerwowano jeden slot, aby head nigdy nie doganiał taila całkowicie.