Réponse.

Historique de la question

Le tampon circulaire (ring buffer, circular buffer) est souvent utilisé dans les systèmes à mémoire limitée, les pilotes de périphériques, les réseaux et les systèmes multitâches. Son concept a été utilisé dès les débuts du développement des systèmes d'exploitation, lorsque l'utilisation optimale de la mémoire était primordiale et qu'il était important de ne pas gaspiller des ressources sur le décalage des éléments après extraction.

Problème

Les difficultés typiques incluent la gestion correcte des conditions de "tampon plein" et "tampon vide", l'absence de protection contre l'écriture de données, et la synchronisation compliquée en multi-threading. Des erreurs peuvent survenir en cas de confusion sur les limites et des vérifications incorrectes des index.

Solution

L'objet tampon circulaire est implémenté par un tableau, deux index (head et tail), et, si nécessaire, une variable compteur ou une logique supplémentaire pour distinguer les états "plein" et "vide". La lecture et l’écriture se font selon le modulo de la taille du tampon.

#define BUF_SIZE 8
char buffer[BUF_SIZE];
int head = 0, tail = 0; // head – écriture, tail – lecture

// Écriture
if (((head + 1) % BUF_SIZE) != tail) {
    buffer[head] = data;
    head = (head + 1) % BUF_SIZE;
} else {
    // Tampon plein
}

// Lecture
if (head != tail) {
    char d = buffer[tail];
    tail = (tail + 1) % BUF_SIZE;
}

Caractéristiques clés :

Vérification des limites à l'aide d'opérations modulo
La distinction entre un tampon vide et plein nécessite un traitement ou un stockage particulier du nombre d'éléments
Facile à implémenter sans allocation dynamique de mémoire

Questions pièges.

Comment faire la différence entre un tampon complètement rempli et complètement vide ?

On détermine souvent un tampon vide par head == tail. Pour un tampon plein, on peut soit laisser une cellule inoccupée, soit stocker le nombre d'éléments dans un compteur explicite.

Peut-on utiliser le tampon dans un environnement multi-thread sans verrous ?

Non, dans le cas standard, lors de la lecture et de l'écriture simultanées, des courses peuvent se produire. Il faut soit utiliser des opérations atomiques, soit des verrous.

Que se passe-t-il si on ne contrôle pas le débordement de head ou tail ?

En cas de débordement, il y aura un dépassement des limites du tableau, ce qui entraînera un comportement indéfini et une possible corruption de la mémoire.

Erreurs typiques et anti-patterns

Absence de distinction entre "plein" et "vide" (head == tail), ce qui casse la sémantique de fonctionnement
Refus de l'arithmétique modulaire (erreurs dans le calcul des index)
Violation de la synchronisation lors de l'exécution multi-thread

Exemple de la vie réelle

Cas négatif

Un développeur a implémenté un tampon circulaire où head == tail était interprété comme "vide" et "plein" en même temps, ce qui a entraîné la perte de signal de débordement.

Avantages :

Simplicité du code

Inconvénients :

Il n'était pas possible de distinguer de manière claire l'état plein de l'état vide ; des données étaient perdues ou écrasées.

Cas positif

À la place, une variable compteur d'éléments a été ajoutée ou une case a été réservée, de sorte que head ne rattrape jamais complètement tail.