Quais são os usos do tampão circular?

Question

Quais são alguns dos usos do tampão circular?

Quais são os benefícios de usar um tampão circular?

É uma alternativa para a lista dupla vinculada?

Answer 1

Eu o usei para um log na memória com um tamanho restrito. Por exemplo, o aplicativo escreveria entradas de log ao processar solicitações de usuário. Sempre que ocorreu uma exceção (isso seria perturbador para o processamento), os registros de log atualmente na memória seriam despejados junto com ele.

O benefício de um buffer circular é que você não precisa de quantidades infinitas de memória, pois as entradas mais antigas são substituídas automaticamente. O "Challange" é que você precisa encontrar um tamanho adequado para a sua USECASE. No exemplo acima, seria muito lamentável quando o registro de log com as informações mais vitais sobre a exceção já tivesse sido substituído.

Alguns sistemas/aplicativos possuem ferramentas para permitir que você extraia o conteúdo atual do buffer sob demanda, e não apenas quando seria extraído automaticamente (se é que alguma vez).

Eu acredito Etw e os clrs log de estresse, entre muitos outros rastreamentos/registro de alto desempenho de outros sistemas, são implementados dessa maneira.

O conceito de usar esses buffers para rastreamento/registro na memória é realmente bastante comum (para não dizer que esse é o único uso - certamente não), porque é muito mais rápido do que os registros escritos para um arquivo/banco de dados que você nunca pode ser Interessado a menos que ocorra um erro. E em uma nota relacionada, ele conserva o espaço de disco rígido.

Answer 2

Os tampões circulares são bons para fluxos de dados em série em sistemas incorporados. Os microcontroladores geralmente têm um UART para lidar com um byte em série, que precisam ser armazenados em ordem e lidados posteriormente (os bytes geralmente chegam a um ritmo mais rápido do que podem ser tratados).

O buffer divide efetivamente a resposta crítica de tempo necessária (quando os bytes entram, em microssegundos) à resposta não crítica de tempo a toda a mensagem (por exemplo, exibindo a mensagem que entrou, em milissegundos), por exemplo:

1) Após o recebimento de um byte, o UART pode gerar uma interrupção à qual o software responde rapidamente pegando o byte recebido e o empurra no final do buffer.

2) As rotinas de software em segundo plano podem verificar regularmente se o buffer ainda tem algo nele e esvaziá -lo conforme necessário.

Como o tamanho do tampão circular pode ser definido antes da compilação, o tamanho é então limitado. Isso ajuda a melhorar a eficiência do espaço e deve eliminar a corrupção da memória em uma troca de quantos bytes podem ser recebidos antes que os dados comecem a se perder.

Answer 3

Um tampão circular é um bom mecanismo para manter com eficiência uma lista deslizante/móvel de valores/itens de maneira ordenada. Um exemplo pode ser manter uma média deslizante dos últimos n itens. Suponha que você queira rastrear o custo médio das últimas 100 operações de calcular algum valor. Para fazer isso, você precisaria remover o custo mais antigo e adicionar o custo mais recente.

Sem um tampão circular, um mecanismo caro para fazer isso (estilo c) seria ter uma matriz de 100 elementos. Cada vez que um novo custo é calculado, você pode memizar os 99 elementos e colocar o novo na última posição. Isso é obviamente caro. Usando uma ideia de buffer circular, você apenas rastreia o "final" do buffer (posição 0-99). Marcaria a posição do item de custo mais antigo (ou mais novo ... o que você escolher). Depois de ler o valor antigo (para atualizar a média de execução), você o substitui pelo valor mais recente e incrementa a posição do buffer (se estiver em 99, você o coloca novamente para 0 ... assim, a parte circular).

Compará -lo a uma lista duplamente vinculada não faz sentido. Um buffer circular certamente poderia ser implementado com uma lista duplamente vinculada (ou mesmo uma lista individual). Mas compará -los é um pouco como comparar maçãs e laranjas, por assim dizer.

Answer 4

Eu sei que isso é trapaça, mas a Wikipedia tem uma explicação muito boa.

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

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

Um exemplo que poderia usar um tampão circular de substituição é com multimídia. Se o buffer for usado como o buffer limitado no problema do consumidor do produtor, provavelmente será desejado para o produtor (por exemplo, um gerador de áudio) para substituir dados antigos se o consumidor (por exemplo, a placa de som) não conseguir manter momentaneamente o número . Outro exemplo é o método de síntese de guia de ondas digital que usa tampões circulares para simular com eficiência o som de cordas vibratórias ou instrumentos de vento.

Com relação às listas de ligações duplas, imagino que isso realmente dependa do que você está usando a lista para ... A implementação de buffers circulares parece ser mais complexa, por favor (novamente) consulte a página wiki; Isso explica a implementação, considerações etc. e também mostra código de exemplo.

Obrigado, Neil

Answer 5

Eu o usei como uma maneira fácil de implementar o agendamento de robin. Basicamente, eu tinha um monte de objetos diferentes que podem produzir um valor que um consumidor poderia processar. Eu coloquei todos os produtores em um anel e perguntei a cada um por sua vez.

Answer 6

Eu usei um buffer de anel no código multithread. Basicamente, se todos os slots estiverem cheios, o (s) produtor (s) precisará esperar. Os consumidores simplesmente processam itens em slots "cheios".

Aqui está um tópico que eu comecei nele. Tem alguns bons conselhos sobre implementação.

.NET Acesso variável multithread