Лекция
Привет, Вы узнаете о том , что такое кольцевой буфер, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое кольцевой буфер, кольцевой буфер , настоятельно рекомендую прочитать все из категории Структуры данных.
кольцевой буфер , или циклический буфер (англ. ring-buffer) — это структура данных, использующая единственный буфер фиксированного размера таким образом, как будто бы после последнего элемента сразу же снова идет первый. Такая структура легко предоставляет возможность буферизации потоков данных.
Кольцевой буфер создается пустым, с некоторой заранее определенной длиной. Например, это семиэлементный буфер:
Предположим, что в середину буфера записывается «1» (в кольцевом буфере точная начальная ячейка не имеет значения):
Затем предположим, что после единицы были добавлены еще два элемента — «2» и «3»:
Если после этого два элемента должны быть удалены из буфера, то выбираются два наиболее старых элемента. В нашем случае удаляются элементы «1» и «2», в буфере остается только «3»:
Если в буфере находится 7 элементов, то он заполнен:
Если продолжить запись в буфер, не принимая во внимание его заполненность, то новые данные начнут перезаписывать старые данные. В нашем случае, добавляя элементы «A» и «B», мы перезапишем «3» и «4»:
В другом варианте реализации процедуры, обслуживающие буфер, могут предотвратить перезапись данных и вернуть ошибку или выбросить исключение. Об этом говорит сайт https://intellect.icu . Перезапись или ее отсутствие оставляется на усмотрение обслуживающих процедур буфера или приложения, использующего кольцевой буфер.
Наконец, если теперь удалить из буфера два элемента, то удалены будут не «3» и «4», а «5» и «6», потому что «A» и «B» перезаписали элементы «3» и «4»; буфер придет в состояние:
Реализацию кольцевого буфера можно оптимизировать, сопоставив базовый буфер с двумя смежными областями виртуальной памяти . (Естественно, длина базового буфера должна тогда равняться некоторому кратному размеру страницы системы .) Чтение из и запись в кольцевой буфер могут затем выполняться с большей эффективностью посредством прямого доступа к памяти; те обращения, которые выходят за пределы конца первой области виртуальной памяти, будут автоматически переноситься в начало базового буфера. Когда смещение чтения продвигается во вторую область виртуальной памяти, оба смещения — чтения и записи — уменьшаются на длину базового буфера.
Пожалуй, наиболее распространенная версия кольцевого буфера использует в качестве элементов 8-битные байты.
Некоторые реализации кольцевого буфера используют элементы фиксированной длины, размер которых превышает 8 бит — 16-битные целые числа для аудиобуферов, 53-байтовые ячейки ATM для телекоммуникационных буферов и т. д. Каждый элемент является непрерывным и имеет правильное выравнивание данных , поэтому программное обеспечение, считывающее и записывающее эти значения, может работать быстрее, чем программное обеспечение, обрабатывающее несмежные и невыровненные значения.
Буферизацию «пинг-понг» можно считать весьма специализированным кольцевым буфером с двумя большими элементами фиксированной длины.
Буфер bip ( двухдольный буфер) очень похож на кольцевой буфер, за исключением того, что он всегда возвращает смежные блоки, которые могут быть переменной длины. Это обеспечивает почти все преимущества эффективности кольцевого буфера, сохраняя при этом возможность использования буфера в API, которые принимают только смежные блоки.
Сжатые кольцевые буферы фиксированного размера используют альтернативную стратегию индексации, основанную на элементарной теории чисел, для поддержания сжатого представления фиксированного размера всей последовательности данных.
Реализация кольцевого буфера в аппаратном обеспечении, патент США 3979733, рис.4
Кольцевой буфер можно реализовать с помощью указателя и трех целых чисел:
На этом изображении показан частично заполненный буфер с длиной = 7:
На этом изображении показан полный буфер с четырьмя перезаписанными элементами (номера от 1 до 4):
В начале индексы end и start устанавливаются в 0. Операция записи в циклический буфер записывает элемент в конечную позицию индекса, а конечный индекс увеличивается до следующей позиции буфера. Операция чтения в циклическом буфере считывает элемент из начальной позиции индекса, а начальный индекс увеличивается до следующей позиции буфера.
Начальный и конечный индексы сами по себе недостаточны для различения состояния буфера: полный или пустой, при этом используются все слоты буфера, но могут быть, если буфер имеет только максимальный используемый размер Length - 1. В этом случае буфер пуст, если начальный и конечный индексы равны и заполнены, когда используемый размер равен Length - 1. Другое решение - иметь другой целочисленный счетчик, который увеличивается при операции записи и уменьшается при операции чтения. Тогда проверка на пустоту означает проверку счетчика на равенство 0, а проверка на заполненность означает проверку счетчика на равенство Length.
Кольцевой буфер находит очень широкое применение в том числе при программировании микроконтроллеров. Данные структуры часто используют для организации различных очередей сообщений и буферов приема-передачи различных коммуникационных интерфейсов. Популярность КБ обусловлена тем, что это один из самых простых и эффективных способов организовать FIFO (англ. first in — first out, «первым пришел — первым вышел») без использования динамической памяти. Существует множество разновидностей КБ.
Исследование, описанное в статье про кольцевой буфер, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое кольцевой буфер, кольцевой буфер и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Структуры данных
Из статьи мы узнали кратко, но содержательно про кольцевой буфер
Комментарии
Оставить комментарий
Структуры данных
Термины: Структуры данных