Каковы виды использования кольцевого буфера?

Question

Каковы некоторые из вариантов использования кольцевого буфера?

Каковы преимущества использования кольцевого буфера?

это альтернатива двойному связанному списку?

Answer 1

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

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

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

Я полагаю, ETW и CLR Журнал стресса , среди многих других системных ядер или высокопроизводительной трассировки / журналирования, реализованы именно таким образом.

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

Answer 2

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

Буфер эффективно разделяет требуемый критический по времени отклик (когда поступают байты в микросекундах) на некритический по времени отклик на все сообщение (например, отображает поступившее сообщение в миллисекундах), например:

1) После получения байта UART может генерировать прерывание, на которое программа реагирует, быстро беря полученный байт и помещая его в конец буфера.

2) Фоновые программные процедуры могут затем регулярно проверять, есть ли в буфере что-либо еще, и очищать его по мере необходимости.

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

Answer 3

Круговой буфер - хороший механизм для эффективного ведения скользящего / движущегося списка значений / элементов в упорядоченном виде. Одним из примеров может быть поддержание скользящего среднего последних N элементов. Предположим, вы хотите отследить среднюю стоимость последних 100 операций вычисления некоторой стоимости. Для этого вам нужно будет удалить самую старую стоимость и добавить самую новую.

Без циклического буфера дорогостоящий механизм для этого (стиль C) будет иметь массив из 100 элементов. Каждый раз, когда вычисляется новая стоимость, вы можете запомнить 99 элементов и поместить новую в последнюю позицию. Это явно дорого. Используя идею кругового буфера, вы бы просто отслеживали «конец» буфера (позиция 0-99). Он будет отмечать позицию самой старой (или самой новой ... какой бы вы ни выбрали) статьи затрат. После считывания старого значения (для обновления скользящего среднего) вы заменяете его на самое новое значение и увеличиваете позицию буфера (если оно равно 99, вы устанавливаете его обратно в 0… таким образом, круглая часть).

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

Answer 4

Я знаю, что это обман, но в Википедии есть очень хорошее объяснение.

http://en.wikipedia.org/wiki/Circular_buffer

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

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

Что касается сравнения списков с двойной связью, я думаю, что это действительно зависит от того, для чего вы используете список ... Реализация циклических буферов кажется более сложной, пожалуйста (снова) обратитесь к странице вики; это объясняет реализацию, соображения и т. д., а также показывает пример кода.

Спасибо, Нил

Answer 5

Я использовал кольцевой буфер в многопоточном коде. В основном, если все слоты заполнены, производители должны ждать. Потребители просто обрабатывают товары в слотах, которые заполнены.

Вот нить, которую я начал на этом. Есть несколько полезных советов по реализации.

Многопоточный доступ к .NET

Answer 6

Я использовал его как простой способ реализации циклического планирования. По сути, у меня было несколько различных объектов, которые могут создавать значение, которое потребитель мог бы обработать. Я засунул всех продюсеров в кольцо и спросил каждого по очереди.