Кружни бафер

Из Википедије, слободне енциклопедије

Кружни бафер (енгл. circular buffer), такође познат и као прстенасти или циклични бафер је термин који означава место у меморији које се користи за чување долазних података. То је структура података фиксне дужине најчешће намењена размени података између процеса.[1]

Имплементација[уреди]

Изглед кружног бафера

Кружни бафер је дизајниран тако да омогући фиксни капацитет. Ако је капацитет попуњен, нови елемент ће бити уписан преко старог на почетак или крај бафера, зависно од тога која операција уметања елемента је коришћена. Кружни бафер алоцира меморијски простор који му је потребан само приликом креирања, експлицитног захтева за проширење капацитета или ако је неопходно да се проширењем прилагоди примењеној операцији. Постоје и реализације кружног бафера са оптимизацијом меморијског простора.

Подржан је насумични приступ итераторима, константно време операција уписа и брисања елемената са почетка или краја бафера.

Упис и читање података[уреди]

Кружни бафер се састоји од поља за смештање података, које је фиксне дужине, и два показивача - једног за упис а другог за читање. Показивач за упис показује на прву слободну локацију за упис података, а показивач за испис показује на први непрочитани податак. Када показивачи дођу до краја простора предвиђеног за упис они се враћају на почетак тог поља.

Упис нових елемената:

Kruzni bafer01.png
Kruzni bafer02.png
Kruzni bafer03.png
Kruzni bafer04.png
Kruzni bafer05.png
Kruzni bafer06.png
Kruzni bafer07.png

Празан бафер[уреди]

Бафер је празан када се показивач прочитаних података изједначи са показивачем учитаних података.

Prazan kruzni bafer01.png
Prazan kruzni bafer01.png

Пун бафер[уреди]

Бафер је пун и не може да прими податке без уписа преко већ постојећих података када показивач за упис достигне вредност показивача прочитаних података, односно кад показивач направи пун круг.

Pun kruzni bafer01.png
Pun kruzni bafer01.png

Карактеристике[уреди]

Подаци у кружни бафер могу бити уписивани и читани од стране већег броја процеса.

Дизајн кружног бафера је прављен тако да задовољи следеће услове:

  • максималну ефикасност за предвиђене апликације
  • погодност за општу намену
  • интуитивно понашање
  • могућност адаптације за специјализовану употребу (нпр. кружни бафер са оптимизацијом меморијског простора)
  • лак за верификацију и дебаговање.

У циљу постизања максималне ефикасности, кружни бафер чува своје елементе на узастопним адресама у меморији. То нам обезбеђује следеће погодности:

  • коришћење фиксног меморијског капацитета без имплицитне и неочекиване меморијске алокације
  • константно и брзо време додавања и брисања нових елемената
  • константан и брз приступ елементима
  • погодан за апликације које раде у реалном времену (енгл. real time appplication) и апликације са критичним перформансама.[2]

Примена[уреди]

Неке од примена овог бафера:

  • складиштење најчешће коришћених узорака, при чему се нови узорци који стигну уписују преко најстаријих
  • главно складиште код бафера са ограниченим меморијским простором
  • кеш меморија
  • ефикасна структура фиксног капацитета за имплементацију FIFO (енгл. First In First Out) политике
  • ефикасна структура фиксног капацитета за имплементацију LIFO (енгл. Last In First Out) политике.

Види још[уреди]

Извори[уреди]

  1. ^ www.link-elearning.com/predavanja/PRV11_09_p.pdf
  2. ^ http://www.boost.org/doc/libs/1_55_0/doc/html/circular_buffer.html
  • Конкурентно и дистрибуирано програмирање, Икодиновић Игор, Јовановић Зоран, Радивојевић Захарије, Академска мисао 2008.
  • The art of computer programming, volume I, Donald E. Knuth, Stanford University 2009.