Podczas tworzenia urządzeń wbudowanych z pewnością natknąłeś się, a jeśli nie, to na pewno natkniesz się na konieczność buforowania danych, czyli tymczasowego ich przechowywania w obszarze pamięci nazywanej buforem.
Zastosowanie buforów umożliwia zebranie określonej ilości danych i dopiero wtedy wykonania na nich określonych operacji oraz zapobiega utracie danych przychodzących, których nie możemy na bieżąco obsłużyć. Możemy wyróżnić dwa typy buforów:
- FIFO (First In First Out) – jak sama nazwa wskazuje, dane które jako pierwsze zostały zapisane do bufora – jako pierwsze zostają z niego odczytane. Nowe dane dopisywane są na końcu bufora. Możesz to sobie porównać do kolejki w sklepie – osoba, która jest pierwsza w kolejce zostaje obsłużona jako pierwsza, a nowe osoby ustawiają się na końcu kolejki. Stąd pochodzi nazwa takiej struktury danych, czyli kolejka (ang. queue),
- LIFO (Last In First Out) – działa odwrotnie, czyli dane które zostały zapisane do bufora jako ostatnie, zostają odczytane jako pierwsze. Możesz to sobie wyobrazić jako stos książek położonych jedna na drugiej. Jeśli otrzymasz nową książkę, dokładasz ją na samej górze. Jeśli chcesz zdjąć książkę ze stosu zdejmujesz tą, która jest na samej górze, czyli tą, która została położona jako ostatnia. Stąd nazwa takiej struktury danych, czyli stos (ang. stack). W ten sposób działa m.in. stos w mikrokontrolerze.
Zasada działania bufora kołowego
W tym artykule opiszę zasadę działania bufora kołowego (ang. circular buffer, ring buffer), który jest przykładem implementacji bufora FIFO.
W systemach wbudowanych bardzo często zachodzi konieczność transmisji danych między mikrokontrolerem, a urządzeniami peryferyjnymi. To właśnie w takich sytuacjach bardzo przydatne są bufory cykliczne, dzięki którym możemy zoptymalizować ten proces, a co za tym idzie – zwiększyć wydajność naszej aplikacji.
Bufor cykliczny jest strukturą, która składa się z obszaru pamięci, w którym będą przechowywane dane oraz dwóch wskaźników:
- head – wskazuje początek bufora cyklicznego – miejsce gdzie przechowywana jest ostatnio zapisana wartość,
- tail – wskazuje koniec bufora cyklicznego – miejsce gdzie przechowywana jest najdawniej zapisana wartość – ta którą będziemy odczytywać jako pierwszą.
W przypadku zapisu danych do bufora inkrementowany jest wskaźnik head, a w przypadku odczytu danych inkrementowany jest wskaźnik tail. Zakłada się, że wartość raz odczytana jest już niepotrzebna i może być ona nadpisana przez inną, nową wartość. Dzięki temu, jeśli podczas zapisu danych do bufora dojdziemy do końca zarezerwowanego obszaru pamięci, możemy przeskoczyć na jego początek i tam kontynuować zapis. Tak samo jest z odczytem – jeśli wskaźnik tail dojdzie do końca obszaru pamięci, przeskakuje na jego początek i tam kontynuujemy odczyt. Wyobraź sobie, że koniec i początek obszaru pamięci są ze sobą połączone tworząc koło. Dobrze ilustruje to poniższa animacja:
Teraz nasuwa się pytanie, co w przypadku, gdy nie nadążamy z odczytem zapisywanych danych i bufor się zapełni? W takiej sytuacji mamy trzy opcje: albo nadpisywać dane, których nie zdążyliśmy odczytać, albo czekać z zapisem, aż zwolni się miejsce w buforze, albo pomijać nowe dane. Każdy z tych sposobów jest w wielu przypadkach nie do zaakceptowania, dlatego powinniśmy zapobiegać takim sytuacjom, poprzez rezerwację odpowiednio dużej ilości pamięci.
Sposób implementacji
Do implementacji bufora kołowego najwygodniej będzie wykorzystać tablicę, a rolę wskaźników head i tail będą pełniły indeksy o takich samych nazwach. Istotna uwaga: początek i koniec naszego bufora są w miejscach head i tail i zmieniają się wraz z zapisem i odczytem kolejnych danych. Nie należy ich mylić z początkiem i końcem tablicy!
Jak stwierdzić, że są jakieś dane do odczytania? Najprostszym sposobem i najbardziej intuicyjnym jest dodanie dodatkowej zmiennej, która przechowywałaby aktualne wypełnienie bufora. Przy zapisie danych byłaby ona inkrementowana, a przy odczycie dekrementowana. Sprawa byłaby banalnie prosta: bufor jest pusty, jeśli zmienna przyjmuje wartość 0. Natomiast, jeśli przyjmuje wartość wielkości tablicy oznacza to, że bufor jest pełny. Niestety przy takiej implementacji pojawia się mały problem. Jeśli chcielibyśmy korzystać z bufora w przerwaniach (a zazwyczaj będziemy chcieli) to należy zwrócić uwagę na fakt, że zmienna ta będzie współdzielona w przerwaniu i programie głównym, a więc konieczne jest zapewnienie wyłącznego dostępu (ang. mutual exclusion). Jest to bardzo istotny temat i nie chcę go opisywać pobieżnie – wolę mu kiedyś poświęcić oddzielny wpis. Poza tym, nie to jest tematem tego artykułu.
Innym sposobem jest porównywanie indeksów head i tail. Tutaj także pojawia się mały kłopot, ponieważ jeśli indeks head jest równy indeksowi tail to może to zarówno oznaczać, że bufor jest pusty, jak i pełny. Możemy to jednak łatwo rozwiązać poświęcając jeden bajt z bufora i przyjmując, że:
- bufor jest pusty, jeśli indeksy head i tail są takie same,
- bufor jest pełny, jeśli następny indeks head, czyli (head + 1) będzie odpowiadał indeksowi tail.
Zalety
Jak widzisz, zasada działania bufora kołowego jest bardzo prosta. Co jednak istotniejsze stosowanie bufora cyklicznego niesie ze sobą szereg zalet:
- jego działanie jest bardzo szybkie – zapis i odczyt wiąże się wyłącznie z inkrementacją i dekrementacją indeksów head i tail oraz sprawdzeniem kilku warunków,
- pozwala zaoszczędzić pamięć, dzięki swojej kołowej strukturze i nadpisywaniu odczytanych wartości,
- jest bardzo wygodny w użyciu.
To tyle w ramach wstępu. Zapraszam Cię do kolejnej części serii, w której zajmiemy się implementacją bufora kołowego w języku C: