В информатике , в кольцевом буфере , круговой очереди , циклический буфер или кольцевой буфер представляет собой структуру данных , которая использует единый, фиксированного размера буфера , как если бы он был подключен конец-к-концу. Эта структура легко поддается буферизации потоков данных .
Обзор
Круговой буфер сначала пуст и имеет заданную длину. На диаграмме ниже представлен 7-элементный буфер:
Предположим, что 1 записано в центре кругового буфера (точное начальное положение не имеет значения в круговом буфере):
Затем предположим, что в круговой буфер добавлены еще два элемента - 2 и 3 - которые помещаются после 1:
Если два элемента удалены, два самых старых значения внутри кругового буфера будут удалены. Круговые буферы используют логику FIFO (первый пришел - первый ушел). В примере 1 и 2 первыми вошли в круговой буфер, они были удалены первыми, оставив 3 внутри буфера.
Если в буфере 7 элементов, то он полностью заполнен:
Свойство кольцевого буфера заключается в том, что когда он заполнен и выполняется последующая запись, он начинает перезаписывать самые старые данные. В текущем примере добавляются еще два элемента - A и B, которые заменяют 3 и 4:
В качестве альтернативы подпрограммы, управляющие буфером, могут предотвратить перезапись данных и вернуть ошибку или вызвать исключение . Независимо от того, перезаписываются ли данные или нет, зависит от семантики подпрограмм буфера или приложения, использующего кольцевой буфер.
Наконец, если теперь удалить два элемента, то будут возвращены не 3 и 4, а 5 и 6, потому что A и B перезаписали 3 и 4, получив буфер с помощью:
Использует
Полезное свойство кольцевого буфера заключается в том, что ему не нужно перемещать элементы, когда один из них израсходован. (Если бы использовался некруговой буфер, тогда было бы необходимо сдвинуть все элементы, когда один из них израсходован.) Другими словами, кольцевой буфер хорошо подходит в качестве буфера FIFO (первый пришел , первый ушел), в то время как стандартный, Некруговой буфер хорошо подходит в качестве буфера LIFO (Last In, First Out).
Циклическая буферизация - хорошая стратегия реализации для очереди с фиксированным максимальным размером. Если для очереди будет принят максимальный размер, то идеальной реализацией будет кольцевой буфер; все операции с очередью - постоянное время. Однако расширение кольцевого буфера требует сдвига памяти, что является сравнительно дорогостоящим. Для произвольно расширяющихся очередей может быть предпочтительнее использовать связанный список .
В некоторых ситуациях может использоваться перезапись кольцевого буфера, например, в мультимедиа. Если буфер используется в качестве ограниченного буфера в проблеме производитель-потребитель, то, вероятно, для производителя (например, аудиогенератора) желательно перезаписать старые данные, если потребитель (например, звуковая карта ) не может на мгновение поддерживать . Кроме того, семейство алгоритмов сжатия данных без потерь LZ77 работает на основе предположения, что строки, которые недавно были замечены в потоке данных, с большей вероятностью вскоре появятся в потоке. Реализации хранят самые свежие данные в кольцевом буфере.
Механика кругового буфера
Круговой буфер может быть реализован с использованием четырех указателей или двух указателей и двух целых чисел:
- начало буфера в памяти
- конец буфера в памяти или емкость буфера
- начало действительных данных (индекс или указатель)
- конец действительных данных (индекс или указатель) или количество данных, находящихся в данный момент в буфере (целое число)
На этом изображении показан частично заполненный буфер:
На этом изображении показан полный буфер с четырьмя перезаписанными элементами (номера от 1 до 4):
Когда элемент перезаписывается, указатель начала увеличивается до следующего элемента.
При использовании полной емкости буфера со стратегией реализации, основанной на указателях, полное или пустое состояние буфера не может быть разрешено непосредственно путем проверки позиций начального и конечного индексов. [1] Следовательно, должен быть реализован дополнительный механизм для проверки этого. Один из распространенных способов справиться с этим при использовании двух указателей - разрешить буферу хранить только элементы (размер - 1). Когда оба указателя равны, буфер пуст, а когда конечный указатель на единицу меньше начального указателя, буфер заполнен.
Когда буфер вместо этого предназначен для отслеживания количества вставленных элементов n , проверка на пустоту означает проверку n = 0, а проверка на заполненность означает проверку того, равно ли n емкости. [2]
Увеличение и уменьшение адресных указателей кольцевого буфера выполняется программно с использованием следующих формул модуля:
increment_address_one = (адрес + 1)% длины
Decment_address_one = (адрес + длина - 1)% длины
В языках, в которых оператор по модулю применяет усеченное деление , требуется добавление дополнительной длины для уменьшения на одну операцию, чтобы предотвратить отрицательные результаты и обеспечить правильное изменение конечного адреса кольцевого буфера.
Оптимизация
Реализация кольцевого буфера может быть оптимизирована путем отображения нижележащего буфера на две смежные области виртуальной памяти . [3] (Естественно, длина нижележащего буфера должна тогда равняться некоторому кратному размеру страницы системы .) Чтение и запись в кольцевой буфер могут тогда выполняться с большей эффективностью посредством прямого доступа к памяти; те обращения, которые выходят за пределы конца первой области виртуальной памяти, автоматически переходят в начало нижележащего буфера. Когда смещение чтения продвигается во вторую область виртуальной памяти, оба смещения - чтение и запись - уменьшаются на длину нижележащего буфера.
Круговой буфер фиксированной длины и непрерывного блока
Возможно, наиболее распространенная версия кольцевого буфера использует в качестве элементов 8-битные байты.
В некоторых реализациях кольцевого буфера используются элементы фиксированной длины, превышающие 8-битные байты - 16-битные целые числа для звуковых буферов, 53-байтовые ячейки ATM для телекоммуникационных буферов и т. Д. Каждый элемент является смежным и имеет правильное выравнивание данных , поэтому программное обеспечение для чтения и записи этих значений может быть быстрее, чем программное обеспечение, которое обрабатывает несмежные и невыровненные значения.
Буферизацию пинг-понга можно рассматривать как очень специализированный кольцевой буфер с ровно двумя большими элементами фиксированной длины.
Bip Buffer (двудольный буфер) очень похож на кольцевой буфер, за исключением того, что он всегда возвращает смежные блоки, которые могут иметь переменную длину. Это предлагает почти все преимущества эффективности кольцевого буфера, сохраняя при этом возможность использования буфера в API, которые принимают только смежные блоки. [4]
Сжатые кольцевые буферы фиксированного размера используют альтернативную стратегию индексации, основанную на теории элементарных чисел, чтобы поддерживать сжатое представление фиксированного размера всей последовательности данных. [5]
Рекомендации
- ^ Чандрасекаран, Сиддхартха (2014-05-16). «Реализация кругового / кольцевого буфера во встроенном C» . Вставить журнал . Команда EmbedJournal. Архивировано 11 февраля 2017 года . Проверено 14 августа 2017 года .
- ^ Morin, Pat . «ArrayQueue: очередь на основе массивов» . Открытые структуры данных (в псевдокоде) . Архивировано 31 августа 2015 года . Проверено 7 ноября 2015 года .
- ^ Майк Эш (17 февраля 2012 г.). "mikeash.com: Пятница, вопросы и ответы, 17 февраля 2012: Кольцевые буферы и зеркальная память: Часть II" . mikeash.com . Архивировано 11 января 2019 года . Проверено 10 января 2019 .
- ↑ Саймон Кук (2003), «Буфер Bip - Круговой буфер с изгибом ». Архивировано 06.10.2012 в Wayback Machine.
- ^ Гюнтер, Джон С. (март 2014 г.). «Алгоритм 938: сжатие кольцевых буферов». Транзакции ACM на математическом программном обеспечении . 40 (2): 1–12. DOI : 10.1145 / 2559995 .