Круговой буфер
В информатике циклический буфер , циклическая очередь , циклический буфер или кольцевой буфер — это структура данных , которая использует один буфер фиксированного размера , как если бы он был соединен сквозным соединением. Эта структура легко подходит для буферизации потоков данных . [1] Были первые аппаратные реализации кольцевого буфера. [2] [3]
Обзор
[ редактировать ]
Циклический буфер сначала пуст и имеет заданную длину. На схеме ниже представлен 7-элементный буфер:
Предположим, что 1 записана в центре кольцевого буфера (точное начальное местоположение в кольцевом буфере не важно):
Затем предположим, что в кольцевой буфер добавляются еще два элемента — 2 и 3 — которые помещаются после 1:
Если два элемента удалены, два самых старых значения внутри кольцевого буфера будут удалены. Циклические буферы используют FIFO ( первый вошел — первый вышел логику ). В этом примере 1 и 2 первыми вошли в кольцевой буфер, они первыми удаляются, оставляя 3 внутри буфера.
Если в буфере 7 элементов, то он полностью заполнен:
Свойством кольцевого буфера является то, что при его заполнении и последующей записи он начинает перезаписывать самые старые данные. В текущем примере добавляются еще два элемента — A и B, которые перезаписывают 3 и 4:
Альтернативно, процедуры, управляющие буфером, могут предотвратить перезапись данных и вернуть ошибку или вызвать исключение . Будут ли данные перезаписаны, зависит от семантики буферных процедур или приложения, использующего кольцевой буфер.
Наконец, если теперь удалить два элемента, то будут возвращены не 3 и 4 (или, скорее, теперь A и B), а 5 и 6, потому что 5 и 6 теперь являются самыми старыми элементами, что дает буфер с:
Использование
[ редактировать ]Полезное свойство циклического буфера заключается в том, что его элементы не нужно перемешивать при их использовании. (Если бы использовался нециклический буфер, тогда было бы необходимо сдвигать все элементы при их использовании.) Другими словами, кольцевой буфер хорошо подходит в качестве буфера FIFO ( первым вошел — первым вышел ), в то время как стандартный, Нециклический буфер хорошо подходит в качестве буфера LIFO ( последний вошел, первый вышел ).
Циклическая буферизация является хорошей стратегией реализации очереди с фиксированным максимальным размером. Если для очереди установлен максимальный размер, то кольцевой буфер является совершенно идеальной реализацией; все операции с очередью выполняются за постоянное время. Однако расширение кольцевого буфера требует смещения памяти, что обходится сравнительно дорого. Для произвольно расширяющихся очередей связанного списка вместо этого может быть предпочтительнее подход .
В некоторых ситуациях можно использовать перезапись кольцевого буфера, например, в мультимедиа. Если буфер используется в качестве ограниченного буфера в задаче производитель-потребитель , то, вероятно, желательно, чтобы производитель (например, аудиогенератор) перезаписывал старые данные, если потребитель (например, звуковая карта ) не может на мгновение справиться с этой задачей. . Кроме того, семейство алгоритмов сжатия данных без потерь LZ77 работает на предположении, что строки, замеченные совсем недавно в потоке данных, с большей вероятностью вскоре появятся в потоке. Реализации хранят самые последние данные в кольцевом буфере.
Механика круглого буфера
[ редактировать ]
Аппаратная реализация кольцевого буфера, патент США 3979733, рис.4
Циклический буфер можно реализовать с помощью указателя и трех целых чисел: [4]
- начало буфера в памяти
- емкость буфера (длина)
- запись в индекс буфера (конец)
- читать из индекса буфера (начало)
На этом изображении показан частично полный буфер с длиной = 7:
На этом изображении показан полный буфер с четырьмя перезаписанными элементами (номера от 1 до 4):
Вначале индексы end и start установлены в 0. Операция записи в кольцевой буфер записывает элемент в позицию конечного индекса, а конечный индекс увеличивается до следующей позиции в буфере. Операция чтения циклического буфера считывает элемент из позиции начального индекса, и начальный индекс увеличивается до следующей позиции в буфере.
Одних только начальных и конечных индексов недостаточно, чтобы различать состояние буфера: полный или пустой, а также использовать все слоты буфера. [5] но может быть, если максимальный используемый размер буфера составляет только длину - 1. [6] В этом случае буфер пуст, если начальный и конечный индексы равны, и заполнен, когда используемый размер равен длине — 1.Другое решение — иметь еще один счетчик целых чисел, который увеличивается при операции записи и уменьшается при операции чтения. Тогда проверка на пустоту означает, что счетчик тестов равен 0, а проверка на полноту означает, что счетчик тестов равен длине. [7]
Следующий исходный код представляет собой реализацию C вместе с минимальным тестом. Функция put() помещает элемент в буфер, функция get() получает элемент из буфера. Обе функции заботятся о емкости буфера:
#include <stdio.h>enum { N = 10 }; // size of circular bufferint buffer [N]; // note: only (N - 1) elements can be stored at a given timeint writeIndx = 0;int readIndx = 0;int put (int item) { if ((writeIndx + 1) % N == readIndx) { // buffer is full, avoid overflow return 0; } buffer[writeIndx] = item; writeIndx = (writeIndx + 1) % N; return 1;}int get (int * value) { if (readIndx == writeIndx) { // buffer is empty return 0; } *value = buffer[readIndx]; readIndx = (readIndx + 1) % N; return 1;}int main (){ // test circular buffer int value = 1001; while (put (value ++)); while (get (& value)) printf ("read %d\n", value); return 0;}Оптимизация
[ редактировать ]Реализация циклического буфера может быть оптимизирована путем сопоставления базового буфера с двумя смежными областями виртуальной памяти . [8] [ оспаривается – обсуждаем ] (Естественно, длина базового буфера должна в этом случае равняться некоторому размеру системной страницы .) Чтение и запись в кольцевой буфер может тогда выполняться с большей эффективностью посредством прямого доступа к памяти; те обращения, которые выходят за пределы первой области виртуальной памяти, автоматически переходят к началу базового буфера. Когда смещение чтения перемещается во вторую область виртуальной памяти, оба смещения — чтения и записи — уменьшаются на длину базового буфера.
Круговой буфер с элементами фиксированной длины и непрерывными блоками
[ редактировать ]Возможно, наиболее распространенная версия кольцевого буфера использует в качестве элементов 8-битные байты.
В некоторых реализациях кольцевого буфера используются элементы фиксированной длины, размер которых превышает 8-битные байты: 16-битные целые числа для аудиобуферов, 53-байтовые ячейки ATM для телекоммуникационных буферов и т. д. Каждый элемент является смежным и имеет правильное выравнивание данных . поэтому программное обеспечение, читающее и записывающее эти значения, может работать быстрее, чем программное обеспечение, которое обрабатывает несмежные и невыровненные значения.
Буферизацию пинг-понга можно рассматривать как очень специализированный кольцевой буфер ровно с двумя большими элементами фиксированной длины.
Буфер bip (двудольный буфер) очень похож на кольцевой буфер, за исключением того, что он всегда возвращает смежные блоки, длина которых может быть переменной. Это обеспечивает почти все преимущества эффективности кольцевого буфера, сохраняя при этом возможность использования буфера в API, которые принимают только смежные блоки. [9]
Сжатые кольцевые буферы фиксированного размера используют альтернативную стратегию индексации, основанную на теории элементарных чисел, для поддержания сжатого представления всей последовательности данных фиксированного размера. [10]
Ссылки
[ редактировать ]- ^ Арпачи-Дюссо, Ремзи Х.; Арпачи-Дюссо, Андреа К. (2014), Операционные системы: три простых части [Глава: Переменные состояния, рисунок 30.13] (PDF) , Arpaci-Dusseau Books
- ^ Хартл, Иоганн (17 октября 2011 г.). «Импульсвидерхолер — Телефонная станция (видео)» . Ютуб . Проверено 15 декабря 2021 г.
- ^ Фрейзер, Александр Гибсон. «Патент США 3979733 Пакетный коммутатор цифровой системы передачи данных» . Патент штата США . Проверено 15 декабря 2021 г.
- ^ Лю, З.; Ву, Ф.; Дас, Словакия (2021). Беспроводные алгоритмы, системы и приложения: 16-я Международная конференция WASA 2021, Нанкин, Китай, 25–27 июня 2021 г., Материалы, Часть II . Конспекты лекций по информатике. Международное издательство Спрингер. п. 117. ИСБН 978-3-030-86130-8 . Проверено 4 сентября 2023 г.
- ^ Чандрасекаран, Сиддхарт (16 мая 2014 г.). «Реализация кольцевого/кольцевого буфера во встроенном C» . Вставить журнал . Команда EmbedJournal. Архивировано из оригинала 11 февраля 2017 года . Проверено 14 августа 2017 г.
- ^ Круговые буферы kernel.org
- ^ Морин, Пэт . «ArrayQueue: очередь на основе массива» . Открытые структуры данных (в псевдокоде) . Архивировано из оригинала 31 августа 2015 года . Проверено 7 ноября 2015 г.
- ^ Майк Эш (17 февраля 2012 г.). «mikeash.com: Пятничные вопросы и ответы, 17 февраля 2012 г.: Кольцевые буферы и зеркальная память: Часть II» . mikeash.com . Архивировано из оригинала 11 января 2019 г. Проверено 10 января 2019 г.
- ^ Саймон Кук (2003), «Буфер Bip - круговой буфер с изюминкой»
- ^ Гюнтер, Джон К. (март 2014 г.). «Алгоритм 938: Сжатие кольцевых буферов». Транзакции ACM в математическом программном обеспечении . 40 (2): 1–12. дои : 10.1145/2559995 . S2CID 14682572 .
Внешние ссылки
[ редактировать ]- CircularBuffer в репозитории шаблонов Портленда
- Способствовать росту:
- CB в ядре Linux
- CB в DSP
- Круговая очередь на C. Архивировано 29 октября 2018 г. в Wayback Machine.