stringtranslate.com

Круговой буфер

Кольцо, концептуально изображающее кольцевой буфер. Это визуально показывает, что у буфера нет реального конца и он может зацикливаться вокруг буфера. Однако, поскольку память никогда физически не создается в виде кольца, обычно используется линейное представление, как показано ниже.

В информатике циклический буфер , циклическая очередь , циклический буфер или кольцевой буфер — это структура данных , которая использует один буфер фиксированного размера , как если бы он был соединен сквозным соединением. Эта структура легко подходит для буферизации потоков данных . [1] Раньше существовали аппаратные реализации кольцевого буфера. [2] [3]

Обзор

24-байтовый кольцевой буфер клавиатуры. Когда указатель записи приближается к указателю чтения (поскольку микропроцессор не отвечает), буфер прекращает запись нажатий клавиш. На некоторых компьютерах раздавался звуковой сигнал.

Циклический буфер сначала пуст и имеет заданную длину. На схеме ниже представлен 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> перечисление { N = 10 }; // N элементов кольцевого буфера      int буфер [ N ]; int writeIndx = 0 ; int readIndx = 0 ;        int put ( int item ) { if (( writeIndx + 1 ) % N == readIndx ) { // буфер заполнен, избегайте переполнения return 0 ; } буфер [ writeIndx ] = элемент ; writeIndx = ( writeIndx + 1 ) % N ; вернуть 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 ( «прочитать %d \n » , значение ); вернуть 0 ; }

Оптимизация

Реализация циклического буфера может быть оптимизирована путем сопоставления базового буфера с двумя смежными областями виртуальной памяти . [8] [ оспаривается – обсуждается ] (Естественно, длина базового буфера должна в этом случае равняться некоторому размеру системной страницы .) Чтение и запись в кольцевой буфер может тогда выполняться с большей эффективностью посредством прямого доступа к памяти; те обращения, которые выходят за пределы первой области виртуальной памяти, автоматически переходят к началу базового буфера. Когда смещение чтения перемещается во вторую область виртуальной памяти, оба смещения — чтения и записи — уменьшаются на длину базового буфера.

Круговой буфер с элементами фиксированной длины и непрерывными блоками

Возможно, наиболее распространенная версия кольцевого буфера использует в качестве элементов 8-битные байты.

В некоторых реализациях кольцевого буфера используются элементы фиксированной длины, размер которых превышает 8-битные байты: 16-битные целые числа для аудиобуферов, 53-байтовые ячейки ATM для телекоммуникационных буферов и т. д. Каждый элемент является смежным и имеет правильное выравнивание данных . поэтому программное обеспечение, читающее и записывающее эти значения, может работать быстрее, чем программное обеспечение, которое обрабатывает несмежные и невыровненные значения.

Буферизацию пинг-понга можно рассматривать как очень специализированный кольцевой буфер ровно с двумя большими элементами фиксированной длины.

Буфер bip (двудольный буфер) очень похож на кольцевой буфер, за исключением того, что он всегда возвращает смежные блоки, длина которых может быть переменной. Это обеспечивает почти все преимущества эффективности циклического буфера, сохраняя при этом возможность использования буфера в API, которые принимают только смежные блоки. [9]

Сжатые кольцевые буферы фиксированного размера используют альтернативную стратегию индексации, основанную на теории элементарных чисел, для поддержания сжатого представления всей последовательности данных фиксированного размера. [10]

Рекомендации

  1. ^ Арпачи-Дюссо, Ремзи Х.; Арпачи-Дюссо, Андреа К. (2014), Операционные системы: три простых части [Глава: Переменные состояния, рисунок 30.13] (PDF) , Arpaci-Dusseau Books
  2. ↑ Хартл, Иоганн (17 октября 2011 г.). «Импульсвидерхолер - Телефонная станция (видео)». YouTube . Проверено 15 декабря 2021 г.
  3. ^ Фрейзер, Александр Гибсон. «Патент США 3979733 Пакетный коммутатор цифровой системы передачи данных». Патент штата США . Проверено 15 декабря 2021 г.
  4. ^ Лю, З.; Ву, Ф.; Дас, Словакия (2021). Беспроводные алгоритмы, системы и приложения: 16-я Международная конференция WASA 2021, Нанкин, Китай, 25–27 июня 2021 г., Материалы, Часть II. Конспекты лекций по информатике. Международное издательство Спрингер. п. 117. ИСБН 978-3-030-86130-8. Проверено 4 сентября 2023 г.
  5. ^ Чандрасекаран, Сиддхарт (16 мая 2014 г.). «Реализация кольцевого/кольцевого буфера во встроенном C». Вставить журнал . Команда EmbedJournal. Архивировано из оригинала 11 февраля 2017 года . Проверено 14 августа 2017 г.
  6. ^ Круговые буферы kernel.org
  7. ^ Морен, Пэт . «ArrayQueue: очередь на основе массива». Открытые структуры данных (в псевдокоде) . Архивировано из оригинала 31 августа 2015 года . Проверено 7 ноября 2015 г.
  8. ^ Майк Эш (17 февраля 2012 г.). «mikeash.com: Пятничные вопросы и ответы, 17 февраля 2012 г.: Кольцевые буферы и зеркальная память: Часть II». mikeash.com . Архивировано из оригинала 11 января 2019 г. Проверено 10 января 2019 г.
  9. ^ Саймон Кук (2003), «Буфер Bip - круговой буфер с изюминкой»
  10. ^ Гюнтер, Джон К. (март 2014 г.). «Алгоритм 938: Сжатие кольцевых буферов». Транзакции ACM в математическом программном обеспечении . 40 (2): 1–12. дои : 10.1145/2559995. S2CID  14682572.

Внешние ссылки