Кружни бафер
Кружни бафер (енгл. circular buffer), такође познат и као прстенасти или циклични бафер је термин који означава место у меморији које се користи за чување долазних података. То је структура података фиксне дужине најчешће намењена размени података између процеса.[1]
Имплементација уреди
Кружни бафер је дизајниран тако да омогући фиксни капацитет. Ако је капацитет попуњен, нови елемент ће бити уписан преко старог на почетак или крај бафера, зависно од тога која операција уметања елемента је коришћена. Кружни бафер алоцира меморијски простор који му је потребан само приликом креирања, експлицитног захтева за проширење капацитета или ако је неопходно да се проширењем прилагоди примењеној операцији. Постоје и реализације кружног бафера са оптимизацијом меморијског простора.
Подржан је насумични приступ итераторима, константно време операција уписа и брисања елемената са почетка или краја бафера.
Упис и читање података уреди
Кружни бафер се састоји од поља за смештање података, које је фиксне дужине, и два показивача - једног за упис а другог за читање. Показивач за упис показује на прву слободну локацију за упис података, а показивач за испис показује на први непрочитани податак. Када показивачи дођу до краја простора предвиђеног за упис они се враћају на почетак тог поља.
Упис нових елемената:
Празан бафер уреди
Бафер је празан када се показивач прочитаних података изједначи са показивачем учитаних података.
Пун бафер уреди
Бафер је пун и не може да прими податке без уписа преко већ постојећих података када показивач за упис достигне вредност показивача прочитаних података, односно кад показивач направи пун круг.
Карактеристике уреди
Подаци у кружни бафер могу бити уписивани и читани од стране већег броја процеса.
Дизајн кружног бафера је прављен тако да задовољи следеће услове:
- максималну ефикасност за предвиђене апликације
- погодност за општу намену
- интуитивно понашање
- могућност адаптације за специјализовану употребу (нпр. кружни бафер са оптимизацијом меморијског простора)
- лак за верификацију и дебаговање.
У циљу постизања максималне ефикасности, кружни бафер чува своје елементе на узастопним адресама у меморији. То обезбеђује следеће погодности:
- коришћење фиксног меморијског капацитета без имплицитне и неочекиване меморијске алокације
- константно и брзо време додавања и брисања нових елемената
- константан и брз приступ елементима
- погодан за апликације које раде у реалном времену (енгл. real time appplication) и перформансно критичне апликације.[2]
Примена уреди
Неке од примена овог бафера:
- складиштење најчешће коришћених узорака, при чему се нови узорци који стигну уписују преко најстаријих
- главно складиште код бафера са ограниченим меморијским простором
- кеш меморија
- ефикасна структура фиксног капацитета за имплементацију FIFO (енгл. First In First Out) политике
- ефикасна структура фиксног капацитета за имплементацију LIFO (енгл. Last In First Out) политике.
Види још уреди
Извори уреди
Литература уреди
- Конкурентно и дистрибуирано програмирање, Икодиновић Игор, Јовановић Зоран, Радивојевић Захарије, Академска мисао 2008.
- The art of computer programming, volume I, Donald E. Knuth, Stanford University 2009.