Kružni bafer

Kružni bafer (engl. circular buffer), takođe poznat i kao prstenasti ili ciklični bafer je termin koji označava mesto u memoriji koje se koristi za čuvanje dolaznih podataka. To je struktura podataka fiksne dužine najčešće namenjena razmeni podataka između procesa.

Implementacija

Izgled kružnog bafera

Kružni bafer je dizajniran tako da omogući fiksni kapacitet. Ako je kapacitet popunjen, novi element će biti upisan preko starog na početak ili kraj bafera, zavisno od toga koja operacija umetanja elementa je korišćena. Kružni bafer alocira memorijski prostor koji mu je potreban samo prilikom kreiranja, eksplicitnog zahteva za proširenje kapaciteta ili ako je neophodno da se proširenjem prilagodi primenjenoj operaciji. Postoje i realizacije kružnog bafera sa optimizacijom memorijskog prostora.

Podržan je nasumični pristup iteratorima, konstantno vreme operacija upisa i brisanja elemenata sa početka ili kraja bafera.

Upis i čitanje podataka

Kružni bafer se sastoji od polja za smeštanje podataka, koje je fiksne dužine, i dva pokazivača - jednog za upis a drugog za čitanje. Pokazivač za upis pokazuje na prvu slobodnu lokaciju za upis podataka, a pokazivač za ispis pokazuje na prvi nepročitani podatak. Kada pokazivači dođu do kraja prostora predviđenog za upis oni se vraćaju na početak tog polja.

Upis novih elemenata:

Prazan bafer

Bafer je prazan kada se pokazivač pročitanih podataka izjednači sa pokazivačem učitanih podataka.

Pun bafer

Bafer je pun i ne može da primi podatke bez upisa preko već postojećih podataka kada pokazivač za upis dostigne vrednost pokazivača pročitanih podataka, odnosno kad pokazivač napravi pun krug.

Karakteristike

Podaci u kružni bafer mogu biti upisivani i čitani od strane većeg broja procesa.

Dizajn kružnog bafera je pravljen tako da zadovolji sledeće uslove:

• maksimalnu efikasnost za predviđene aplikacije
• pogodnost za opštu namenu
• intuitivno ponašanje
• mogućnost adaptacije za specijalizovanu upotrebu (npr. kružni bafer sa optimizacijom memorijskog prostora)
• lak za verifikaciju i debagovanje.
  

U cilju postizanja maksimalne efikasnosti, kružni bafer čuva svoje elemente na uzastopnim adresama u memoriji. To obezbeđuje sledeće pogodnosti:

• korišćenje fiksnog memorijskog kapaciteta bez implicitne i neočekivane memorijske alokacije
• konstantno i brzo vreme dodavanja i brisanja novih elemenata
• konstantan i brz pristup elementima
• pogodan za aplikacije koje rade u realnom vremenu (engl. real time appplication) i performansno kritične aplikacije.

Primena

Neke od primena ovog bafera:

• skladištenje najčešće korišćenih uzoraka, pri čemu se novi uzorci koji stignu upisuju preko najstarijih
• glavno skladište kod bafera sa ograničenim memorijskim prostorom
• keš memorija
• efikasna struktura fiksnog kapaciteta za implementaciju FIFO (engl. First In First Out) politike
• efikasna struktura fiksnog kapaciteta za implementaciju LIFO (engl. Last In First Out) politike.

Vidi još

• Bafer
• Struktura podataka

Literatura

• Konkurentno i distribuirano programiranje, Ikodinović Igor, Jovanović Zoran, Radivojević Zaharije, Akademska misao 2008.
• The art of computer programming, volume I, Donald E. Knuth, Stanford University 2009.