Циклічний буфер

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Циклічний буфер

Циклічний буфер або кільцевий буфер - це структура даних, яка має фіксований розмір і використовується так ніби кінець буферу і початок замкнені в кільце, тобто при досягненні кінця буфера знов переміщуються в його початок. Така структура дає можливість здійснювати буферизацію потоків даних.

Застосування[ред.ред. код]

Перевагою використання циклічного буфера є те, що при зчитуванні не потрібно переміщувати дані в буфері, тому що вказівник на поточну позицію переміщується сам. При використанні не кільцевих буферів було б необхідно переміщувати дані, коли його елементи стають непотрібними. Іншими словами кільцевий буфер добре застосовувати для реалізації буферу типу FIFO ("перший прийшов — першим пішов").

Циклічний буфер добре підходить для реалізації черг фіксованого розміру. Але якщо розмір черги є змінним, операція розширення кільцевого буфера є не ефективною, оскільки вимагає здійснення процедури переміщення пам’яті. В таких випадках краще використовувати зв'язаний список.

Такий тип буферу часто зустрічається при роботі з апаратним обладнанням та мікроконтролерами. При роботі з даними мультимедіа, обмежений циклічний буфер часто реалізує задачу постачальника-споживача, наприклад, при роботі зі звуковими картами[1]. Карта зчитує для відтворення звуку дані з буфера з постійною швидкістю, в той час як постачальник (наприклад, аудіо-генератор) може перезаписувати старі дані.

Принцип роботи[ред.ред. код]

В початковому стані буфер є пустим і має деяку визначену наперед довжину. Наприклад, так виглядає буфер для 7-ми елементів:

Circular buffer - empty.svg

Допустимо, що в середину буфера в якійсь позиції записано значення 1 (конкретна початкова позиція не має значення для циклічного буферу):

Circular buffer - XX1XXXX.svg

Потім допустимо ми додали ще два елементи зі значеннями 2 і 3 — в позиції після значення 1:

Circular buffer - XX123XX.svg

Якщо необхідно видалити елементи з буферу, видалятимуться ті, що були записані раніше. Допустимо, що треба видалити два елементи, в такому випадку, значення 1 і 2 будуть видалені, а в буфері залишиться значення 3:

Circular buffer - XXXX3XX.svg

Якщо буфер містить 7 елементів тоді він є повністю заповненим:

Circular buffer - 6789345.svg

Особливість кільцевого буфера полягає в тому, що коли він заповнений і відбувається новий запис даний, будуть перезаписані вже існуючі найстаріші елементи по колу. В такому випадку, два нових елементи — A і B — додаються і перезаписують значення 3 і 4:

Circular buffer - 6789AB5.svg

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

І нарешті, якщо видалити два елементи то видалені будуть не комірки зі значеннями 3 і 4, а 5 і 6 оскільки A і B перезаписали значення 3 і 4 і буфер матиме наступний вміст:

Circular buffer - X789ABX.svg

Примітки[ред.ред. код]

  1. www.alsa-project.org PCM Ring Buffer

Джерела[ред.ред. код]

Посилання[ред.ред. код]