Circular buffer

Um anel mostrando, conceitualmente, um buffer circular. Isso mostra visualmente que o buffer não tem um final real e pode fazer um loop ao redor do buffer. No entanto, como a memória nunca é criada fisicamente como um anel, geralmente é usada uma representação linear, como é feito abaixo.

Um buffer circular, fila circular, buffer cíclico ou buffer de anel é uma estrutura de dados que usa um único buffer de tamanho fixo como se estivesse conectado de ponta a ponta. Essa estrutura se presta facilmente ao buffer de fluxos de dados .

Assim, um algoritmo de leitura que leia a última posição do buffer e necessite continuar lendo irá retornar ao início do buffer e proceder a leitura a partir daí. O mesmo vale para algoritmos de escrita, sendo que a escrita numa posição não-vazia provoca a perda do conteúdo original.

Usos

A propriedade útil de um buffer circular é que ele não precisa ter seus elementos embaralhados quando um é consumido (se um buffer não circular fosse usado, seria necessário deslocar todos os elementos quando um deles fosse consumido). Por outras palavras, o tampão circular é bem adequado como um buffer FIFO enquanto um buffer padrão, não circular, é bem adequado como um buffer LIFO.

O buffer circular faz uma boa estratégia de implementação para uma fila que tenha tamanho máximo fixo. Se um tamanho máximo for adotado para uma fila, então um buffer circular é uma implementação completamente ideal; todas as operações da fila são constantes. No entanto, expandir um buffer circular requer a troca de memória, o que é relativamente caro. Para filas de expansão arbitrária, uma abordagem de lista ligada pode ser preferida.

Em algumas situações, o buffer circular sobrescrito pode ser usado, por exemplo, em multimídia. Se o buffer é usado como o buffer limitado no problema de produtores e consumidores, então é provavelmente desejável que o produtor (por exemplo, um gerador de áudio) sobrescreva dados antigos se o consumidor (por exemplo, a placa de som) não puder acompanhar momentaneamente. Além disso, a família LZ77 de algoritmos de compactação de dados sem perdas opera na suposição de que as cadeias vistas mais recentemente em um fluxo de dados têm maior probabilidade de ocorrer em breve no fluxo. Implementações armazenam os dados mais recentes em um buffer circular.

Como funciona

Um buffer circular de teclado de 24 bytes. Quando o ponteiro de gravação está prestes a alcançar o ponteiro de leitura - porque o microprocessador não está respondendo, o buffer irá parar de gravar os pressionamentos de tecla e - em alguns computadores - um bipe será reproduzido.

Um buffer circular primeiro começa vazio e de algum comprimento predefinido. Por exemplo, este é um buffer de 7 elementos:

Suponha que um 1 esteja escrito no meio do buffer (o local inicial exato não importa em um buffer circular):

Então, suponha que mais dois elementos sejam adicionados — 2 e 3 — que são acrescentados após o 1:

Se dois elementos forem removidos do buffer, os valores mais antigos dentro do buffer serão removidos. Os dois elementos removidos, neste caso, são 1 e 2, deixando o buffer com apenas 3:

Se o buffer tiver 7 elementos, ele estará completamente cheio:

Uma consequência do buffer circular é que quando ele está cheio e uma gravação subsequente é executada, ele começa a sobrescrever os dados mais antigos. Neste caso, mais dois elementos — A e B — são adicionados e eles substituem os 3 e 4:

Alternativamente, as rotinas que gerenciam o buffer podem evitar sobrescrever os dados e retornar um erro ou gerar uma exceção. Se os dados são ou não sobrescritos, é a semântica das rotinas de buffer ou o aplicativo que usa o buffer circular.

Finalmente, se dois elementos forem removidos, o que seria retornado não é 3 e 4, mas 5 e 6, porque A & B sobrescreveu o 3 e o 4 gerando o buffer com:

Otimização

Uma implementação de buffer circular pode ser otimizada mapeando o buffer subjacente para duas regiões contíguas de memória (naturalmente, o comprimento do buffer subjacente deve ser igual a um múltiplo do tamanho de página do sistema). A leitura e escrita no buffer circular pode então ser realizada com maior eficiência por meio do acesso direto à memória; os acessos que caem além do final da primeira região de memória virtual serão automaticamente agrupados no início do buffer subjacente. Quando o deslocamento de leitura é avançado na segunda região de memória virtual, os deslocamentos - leitura e gravação - são diminuídos pelo comprimento do buffer subjacente.

Ligações externas

• CircularBuffer no Repositório de Padrões de Portland
• Impulsionar: Recipiente de Buffer Circular Templado
• Buffer Circular
• Fila circular em C