Каково использование кольцевого буфера?
Что такое часть использования кольцевого буфера?
Что преимущества использования являются кольцевым буфером?
действительно ли это - альтернатива для удвоения связанного списка?
6 ответов
Я использовал его для журнала в памяти с ограниченным размером. Например, приложение будет записывать записи в журнал при обработке пользовательских запросов. Всякий раз, когда возникает исключение (которое может нарушить обработку), записи журнала, находящиеся в настоящее время в памяти, сбрасываются вместе с ним.
Преимущество кольцевого буфера в том, что вам не нужно бесконечное количество памяти, поскольку старые записи автоматически заменяются. Проблема в том, что вам нужно найти подходящий размер для вашего случая использования. В приведенном выше примере было бы очень прискорбно, если бы запись журнала с наиболее важной информацией об исключении уже была бы переопределена.
В некоторых системах / приложениях есть инструменты, позволяющие извлекать текущее содержимое буфера по запросу, а не только тогда, когда оно будет извлекаться автоматически (если вообще будет).
Я полагаю, что ETW и CLR журнал напряжений , среди многих других системного ядра или высокопроизводительной трассировки / ведения журнала, реализованы таким образом.
Идея использования таких буферов для трассировки / ведения журнала в памяти на самом деле довольно распространена (не сказать, что это единственное использование - конечно, нет), потому что это намного быстрее, чем записи в файл / базу данных, которые вы может никогда не заинтересовать, если не произойдет ошибка. И, кстати, это экономит место на жестком диске.
Круговой буфер - хороший механизм для эффективного обслуживания скользящего / перемещающегося списка значений / элементов в упорядоченном виде. Одним из примеров может быть поддержание скользящего среднего для последних N элементов. Предположим, вы хотите отслеживать среднюю стоимость последних 100 операций вычисления некоторого значения. Для этого вам нужно удалить самую старую стоимость и добавить самую новую стоимость.
Без кольцевого буфера дорогостоящим механизмом для этого (стиль C) было бы наличие массива из 100 элементов. Каждый раз, когда вычисляется новая стоимость, вы можете переместить 99 элементов вниз и поместить новый в последнюю позицию. Очевидно, это дорого. Используя идею кольцевого буфера, вы просто отслеживаете «конец» буфера (позиции 0-99). Он будет отмечать позицию самой старой (или самой новой… в зависимости от того, что вы выберете). После считывания старого значения (для обновления текущего среднего) вы заменяете его самым новым значением и увеличиваете позицию буфера (если оно равно 99, вы устанавливаете его обратно на 0… таким образом, круговая часть).
Сравнивать его с двусвязным списком не имеет смысла.Кольцевой буфер, безусловно, может быть реализован с двусвязным списком (или даже односвязным списком). Но сравнивать их все равно, что сравнивать, так сказать, яблоки и апельсины.
Я знаю, что это обман, но в Википедии есть очень хорошее объяснение.
http://en.wikipedia.org/wiki/Circular_buffer
Кольцевой буфер, циклический буфер или кольцевой буфер - это структура данных, которая использует один фиксированный размер буфер, как если бы был подключен сквозной. Эта структура легко поддается буферизации потоков данных
. Примером, в котором возможно использование циклического буфера перезаписи , является мультимедиа . Если буфер используется как ограниченный буфер в проблеме производитель-потребитель, то он, вероятно, желателен для производителя (например, аудиогенератор) для перезаписи старых данных, если потребитель (например, звуковая карта) не может на мгновение поспевать за ними. Другим примером является метод синтеза цифровых волноводов , в котором используются кольцевые буферы для эффективного имитации звука вибрирующих струн или духовых инструментов.
Что касается сравнения с двусвязными списками, я полагаю, это действительно зависит от того, для чего вы используете этот список ... Реализация кольцевых буферов кажется более сложной, пожалуйста (снова) обратитесь к вики-странице; это объясняет реализацию, соображения и т. д., а также показывает пример кода.
Спасибо, Нил
Я использовал его как простой способ реализации циклического планирования. По сути, у меня была куча разных объектов, которые могут давать значение, которое затем мог обработать потребитель. Я собрал всех продюсеров в кольцо и спросил каждого по очереди.
Я использовал кольцевой буфер в многопоточном коде. Обычно, если все слоты заполнены, производителю (-ам) приходится ждать. Потребители просто обрабатывают товары в "заполненных" слотах.
Я начал обсуждать эту тему. В нем есть несколько хороших советов по реализации.
Круглые буферы хороши для последовательных потоков данных во встроенных системах. Микроконтроллеры часто имеют UART для обработки поступающего последовательного байта, они должны храниться по порядку и обрабатываться позже (байты часто поступают с большей скоростью, чем они могут быть обработаны).
Буфер эффективно разделяет требуемый критически важный по времени ответ (когда байты поступают в микросекундах) на некритичный по времени ответ на все сообщение (например, отображение пришедшего сообщения в миллисекундах), например:
1) После получения байта UART может сгенерировать прерывание, на которое программа реагирует, быстро взяв полученный байт и поместив его в конец буфера.
2) Фоновые программные процедуры могут затем регулярно проверять, есть ли что-нибудь в буфере, и очищать его по мере необходимости.
Поскольку размер кольцевого буфера может быть определен перед компиляцией, размер затем ограничивается. Это помогает повысить эффективность использования пространства и должно исключить повреждение памяти за счет того, сколько байтов можно получить до того, как данные начнут теряться.