Implémentation d’un tampon en anneau en Java

1. Aperçu

Dans ce tutoriel, nous allons apprendre à mettre en œuvre un Ring Buffer en Java.

Ring Buffer

Le Ring Buffer (ou Buffer circulaire) est une structure de données circulaire délimitée qui est utilisée pour mettre en mémoire tampon les données entre deux ou plusieurs threads. Comme nous continuons à écrire dans un tampon circulaire, il s’enroule autour comme il atteint la fin.

2.1. Comment cela fonctionne

Un tampon en anneau est mis en œuvre en utilisant un tableau de taille fixe qui s’enroule aux frontières.

A part le tableau, il garde la trace de trois choses :

• le prochain emplacement disponible dans le tampon pour insérer un élément,
• le prochain élément non lu dans le tampon,
• et la fin du tableau – le point auquel le tampon s’enroule jusqu’au début du tableau

La mécanique de la façon dont un tampon en anneau gère ces exigences varie avec l’implémentation. Par exemple, l’entrée Wikipedia sur le sujet montre une méthode utilisant quatre pointeurs.

Nous emprunterons l’approche de l’implémentation de Disruptor du tampon en anneau en utilisant des séquences.

La première chose que nous devons connaître est la capacité – la taille maximale fixe du tampon. Ensuite, nous utiliserons deux séquences à croissance monotone :

• Séquence d’écriture : commençant à -1, s’incrémente de 1 lorsque nous insérons un élément
• Séquence de lecture : commençant à 0, s’incrémente de 1 lorsque nous consommons un élément

Nous pouvons mapper une séquence à un index dans le tableau en utilisant une opération mod :

arrayIndex = sequence % capacity

L’opération mod enroule la séquence autour des limites pour dériver un slot dans le tampon:

Voyons comment nous insérerions un élément:

buffer = element

Nous préincrémentons la séquence avant d’insérer un élément.

Pour consommer un élément, nous effectuons une post-incrémentation:

element = buffer

Dans ce cas, nous effectuons une post-incrémentation sur la séquence. Consommer un élément ne le supprime pas du tampon – il reste simplement dans le tableau jusqu’à ce qu’il soit écrasé.

2.2. Tampons vides et pleins

A mesure que nous nous enroulons autour du tableau, nous allons commencer à écraser les données dans le tampon. Si le tampon est plein, nous pouvons choisir soit d’écraser les données les plus anciennes, que le lecteur les ait consommées ou non, soit d’empêcher l’écrasement des données qui n’ont pas été lues.

Si le lecteur peut se permettre de manquer les valeurs intermédiaires ou anciennes (par exemple, un téléscripteur de cours de bourse), nous pouvons écraser les données sans attendre qu’elles soient consommées. En revanche, si le lecteur doit consommer toutes les valeurs (comme dans le cas des transactions de commerce électronique), nous devrions attendre (block/busy-wait) que le tampon ait un slot disponible.

Le tampon est plein si sa taille est égale à sa capacité, où sa taille est égale au nombre d’éléments non lus :

size = (writeSequence - readSequence) + 1isFull = (size == capacity)

Si la séquence d’écriture est en retard sur la séquence de lecture, le tampon est vide :

isEmpty = writeSequence < readSequence

Le tampon renvoie une valeur nulle s’il est vide.

2.2. Avantages et inconvénients

Un tampon en anneau est un tampon FIFO efficace. Il utilise un tableau de taille fixe qui peut être pré-alloué en amont et permet un modèle d’accès à la mémoire efficace. Toutes les opérations du tampon sont en temps constant O(1), y compris la consommation d’un élément, car il ne nécessite pas de décalage d’éléments.

D’un autre côté, déterminer la bonne taille du tampon en anneau est critique. Par exemple, les opérations d’écriture peuvent bloquer pendant un long moment si le tampon est sous-dimensionné et que les lectures sont lentes. Nous pouvons utiliser un dimensionnement dynamique, mais cela nécessiterait de déplacer les données et nous manquerions la plupart des avantages discutés ci-dessus.

Implémentation en Java

Maintenant que nous comprenons comment fonctionne un tampon en anneau, procédons à son implémentation en Java.

3.1. Initialisation

D’abord, définissons un constructeur qui initialise le tampon avec une capacité prédéfinie:

public CircularBuffer(int capacity) { this.capacity = (capacity < 1) ? DEFAULT_CAPACITY : capacity; this.data = (E) new Object; this.readSequence = 0; this.writeSequence = -1;}

Cela créera un tampon vide et initialisera les champs de séquence comme discuté dans la section précédente.

3.2. Offre

Puis, nous implémenterons l’opération offre qui insère un élément dans le tampon au prochain slot disponible et retourne true en cas de succès. Elle renvoie false si le tampon ne trouve pas de slot vide, c’est-à-dire que nous ne pouvons pas écraser les valeurs non lues.

Mettons en œuvre la méthode offer en Java :

public boolean offer(E element) { boolean isFull = (writeSequence - readSequence) + 1 == capacity; if (!isFull) { int nextWriteSeq = writeSequence + 1; data = element; writeSequence++; return true; } return false;}

Donc, nous incrémentons la séquence d’écriture et calculons l’index dans le tableau pour le prochain slot disponible. Ensuite, nous écrivons les données dans le tampon et stockons la séquence d’écriture mise à jour.

Essayons-le :

@Testpublic void givenCircularBuffer_whenAnElementIsEnqueued_thenSizeIsOne() { CircularBuffer buffer = new CircularBuffer<>(defaultCapacity); assertTrue(buffer.offer("Square")); assertEquals(1, buffer.size());}

3.3. Poll

Enfin, nous allons implémenter l’opération poll qui récupère et supprime le prochain élément non lu. L’opération poll ne supprime pas l’élément mais incrémente la séquence de lecture.

Mettons-la en œuvre :

public E poll() { boolean isEmpty = writeSequence < readSequence; if (!isEmpty) { E nextValue = data; readSequence++; return nextValue; } return null;}

Ici, nous lisons les données à la séquence de lecture actuelle en calculant l’index dans le tableau. Ensuite, nous incrémentons la séquence et retournons la valeur, si le tampon n’est pas vide.

Testons-le :

@Testpublic void givenCircularBuffer_whenAnElementIsDequeued_thenElementMatchesEnqueuedElement() { CircularBuffer buffer = new CircularBuffer<>(defaultCapacity); buffer.offer("Triangle"); String shape = buffer.poll(); assertEquals("Triangle", shape);}

Problème producteur-consommateur

Nous avons parlé de l’utilisation d’un tampon en anneau pour échanger des données entre deux ou plusieurs threads, ce qui est un exemple de problème de synchronisation appelé le problème producteur-consommateur. En Java, nous pouvons résoudre le problème producteur-consommateur de différentes manières en utilisant des sémaphores, des files d’attente bornées, des tampons en anneau, etc.

Mettons en œuvre une solution basée sur un tampon en anneau.

4.1. Champs de séquence volatils

Notre mise en œuvre du tampon en anneau n’est pas thread-safe. Rendons-la thread-safe pour le cas simple d’un seul producteur et d’un seul consommateur.

Le producteur écrit des données dans le tampon et incrémente la writeSequence, tandis que le consommateur ne fait que lire le tampon et incrémente la readSequence. Ainsi, le tableau de backing est sans contention et nous pouvons nous en sortir sans aucune synchronisation.

Mais nous devons encore nous assurer que le consommateur peut voir la dernière valeur du champ writeSequence (visibilité) et que le writeSequence n’est pas mis à jour avant que les données soient effectivement disponibles dans le tampon (ordonnancement).

Nous pouvons rendre le tampon en anneau concurrent et sans verrou dans ce cas en rendant les champs de séquence volatils :

private volatile int writeSequence = -1, readSequence = 0;

Dans la méthode d’offre, une écriture dans le champ volatile writeSequence garantit que les écritures dans le tampon se produisent avant la mise à jour de la séquence. En même temps, la garantie de visibilité volatile assure que le consommateur verra toujours la dernière valeur de writeSequence.

4.2. Producteur

Mettons en œuvre un Runnable producteur simple qui écrit dans le tampon annulaire:

public void run() { for (int i = 0; i < items.length;) { if (buffer.offer(items)) { System.out.println("Produced: " + items); i++; } }}

Le thread producteur attendrait un slot vide dans une boucle (busy-waiting).

4.3. Consommateur

Nous implémenterons un Callable consommateur qui lit dans le tampon:

public T call() { T items = (T) new Object; for (int i = 0; i < items.length;) { T item = buffer.poll(); if (item != null) { items = item; System.out.println("Consumed: " + item); } } return items;}

Le thread consommateur continue sans imprimer s’il reçoit une valeur nulle du tampon.

Ecrivons notre code pilote:

executorService.submit(new Thread(new Producer<String>(buffer)));executorService.submit(new Thread(new Consumer<String>(buffer)));

L’exécution de notre programme producteur-consommateur produit une sortie comme ci-dessous:

Produced: CircleProduced: Triangle Consumed: CircleProduced: Rectangle Consumed: Triangle Consumed: RectangleProduced: SquareProduced: Rhombus Consumed: SquareProduced: Trapezoid Consumed: Rhombus Consumed: TrapezoidProduced: PentagonProduced: PentagramProduced: Hexagon Consumed: Pentagon Consumed: PentagramProduced: Hexagram Consumed: Hexagon Consumed: Hexagram

Conclusion

Dans ce tutoriel, nous avons appris à mettre en œuvre un tampon en anneau et exploré comment il peut être utilisé pour résoudre le problème producteur-consommateur.