В информатике кольцевой буфер , кольцевая очередь , циклический буфер или кольцевой буфер — это структура данных , которая использует один буфер фиксированного размера , как если бы он был соединен сквозным образом. Эта структура легко подходит для буферизации потоков данных . [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 работает на основе предположения, что строки, которые были недавно замечены в потоке данных, с большей вероятностью вскоре появятся в потоке. Реализации хранят самые последние данные в кольцевом буфере.
Кольцевой буфер можно реализовать с помощью указателя и трех целых чисел: [4]
На этом изображении показан частично заполненный буфер с длиной = 7:
На этом изображении показан полный буфер с четырьмя перезаписанными элементами (номера от 1 до 4):
В начале индексы end и start устанавливаются в 0. Операция записи в циклический буфер записывает элемент в конечную позицию индекса, а конечный индекс увеличивается до следующей позиции буфера. Операция чтения в циклическом буфере считывает элемент из начальной позиции индекса, а начальный индекс увеличивается до следующей позиции буфера.
Начальных и конечных индексов самих по себе недостаточно для различения состояния буфера: заполнен или пуст, при этом используются все слоты буфера, [5] но это возможно, если максимальный используемый размер буфера равен Length - 1. [6] В этом случае буфер пуст, если начальный и конечный индексы равны и заполнены, когда используемый размер равен Length - 1. Другое решение — иметь другой целочисленный счетчик, который увеличивается при операции записи и уменьшается при операции чтения. Тогда проверка на пустоту означает проверку счетчика на равенство 0, а проверка на заполненность означает проверку счетчика на равенство Length. [7]
Следующий исходный код представляет собой реализацию на языке C вместе с минимальным тестом. Функция put() помещает элемент в буфер, функция get() извлекает элемент из буфера. Обе функции заботятся о емкости буфера:
#include <stdio.h> enum { N = 10 }; // размер кольцевого буфера int buffer [ N ]; // примечание: в данный момент времени может быть сохранено только (N - 1) элементов int writeIndx = 0 ; int readIndx = 0 ; int put ( int item ) { if (( writeIndx + 1 ) % N == readIndx ) { // буфер заполнен, избегайте переполнения return 0 ; } buffer [ writeIndx ] = item ; writeIndx = ( writeIndx + 1 ) % N ; return 1 ; } int get ( int * value ) { if ( readIndx == writeIndx ) { // буфер пуст return 0 ; } * значение = буфер [ readIndx ]; readIndx = ( readIndx + 1 ) % N ; возврат 1 ; } int main () { // тест кольцевого буфера int value = 1001 ; while ( put ( value ++ )); while ( get ( & value )) printf ( "read %d \n " , value ); return 0 ; } Реализацию кольцевого буфера можно оптимизировать, сопоставив базовый буфер с двумя смежными областями виртуальной памяти . [8] [ discussed – discussion ] (Естественно, длина базового буфера должна тогда равняться некоторому кратному размеру страницы системы .) Чтение из и запись в кольцевой буфер могут затем выполняться с большей эффективностью посредством прямого доступа к памяти; те доступы, которые выходят за пределы конца первой области виртуальной памяти, будут автоматически переноситься в начало базового буфера. Когда смещение чтения продвигается во вторую область виртуальной памяти, оба смещения — чтения и записи — уменьшаются на длину базового буфера.
Пожалуй, наиболее распространенная версия кольцевого буфера использует в качестве элементов 8-битные байты.
Некоторые реализации кольцевого буфера используют элементы фиксированной длины, размер которых превышает 8 бит — 16-битные целые числа для аудиобуферов, 53-байтовые ячейки ATM для телекоммуникационных буферов и т. д. Каждый элемент является непрерывным и имеет правильное выравнивание данных , поэтому программное обеспечение, считывающее и записывающее эти значения, может работать быстрее, чем программное обеспечение, обрабатывающее несмежные и невыровненные значения.
Буферизацию по принципу пинг-понга можно считать весьма специализированным кольцевым буфером с двумя большими элементами фиксированной длины.
Буфер bip (двусторонний буфер) очень похож на кольцевой буфер, за исключением того, что он всегда возвращает смежные блоки, которые могут быть переменной длины. Это обеспечивает почти все преимущества эффективности кольцевого буфера, сохраняя при этом возможность использования буфера в API, которые принимают только смежные блоки. [9]
Сжатые кольцевые буферы фиксированного размера используют альтернативную стратегию индексации, основанную на элементарной теории чисел, для поддержания сжатого представления фиксированного размера всей последовательности данных. [10]