 | Эта статья может быть слишком технической для понимания большинством читателей . ( Март 2019 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
 | Эта статья требует дополнительных ссылок для проверки . ( сентябрь 2014 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
В информатике , в кольцевом буфере , круговой очереди , циклический буфер или кольцевой буфер представляет собой структуру данных , которая использует единый, фиксированного размера буфера , как если бы он был подключен конец-к-концу. Эта структура легко поддается буферизации потоков данных .
Обзор [ править ]
Круговой буфер сначала пуст и имеет заданную длину. На диаграмме ниже представлен 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 .
Внешние ссылки [ править ]
- CircularBuffer в репозитории портлендских паттернов
- Boost: шаблонный круговой буферный контейнер
- Круговая буферизация
- Круговая очередь в C
