Implémentations de la structure de données Thread Safe LIFO

1. Introduction

Dans ce didacticiel, nous aborderons diverses options pour les implémentations de structure de données LIFO sécurisées pour les threads .

Dans la structure de données LIFO, les éléments sont insérés et récupérés selon le principe du dernier entré, premier sorti. Cela signifie que le dernier élément inséré est récupéré en premier.

En informatique, pile est le terme utilisé pour désigner une telle structure de données.

Une pile est pratique pour traiter certains problèmes intéressants comme l'évaluation des expressions, l'implémentation d'opérations d'annulation, etc. Comme elle peut être utilisée dans des environnements d'exécution simultanés, nous pourrions avoir besoin de la rendre sûre pour les threads.

2. Comprendre les piles

Fondamentalement, une pile doit implémenter les méthodes suivantes:

  1. push () - ajoute un élément en haut
  2. pop () - récupère et supprime l'élément supérieur
  3. peek () - récupère l'élément sans le retirer du conteneur sous-jacent

Comme indiqué précédemment, supposons que nous voulons un moteur de traitement de commandes.

Dans ce système, l'annulation des commandes exécutées est une fonctionnalité importante.

En général, toutes les commandes sont poussées sur la pile, puis l'opération d'annulation peut simplement être implémentée:

  • méthode pop () pour obtenir la dernière commande exécutée
  • appeler la méthode undo () sur l'objet de commande popped

3. Comprendre la sécurité des threads dans les piles

Si une structure de données n'est pas thread-safe, lorsqu'elle est accédée simultanément, elle peut finir par avoir des conditions de concurrence .

Les conditions de concurrence, en un mot, se produisent lorsque l'exécution correcte du code dépend du timing et de la séquence des threads. Cela se produit principalement si plus d'un thread partage la structure de données et que cette structure n'est pas conçue à cet effet.

Examinons une méthode ci-dessous à partir d'une classe Java Collection, ArrayDeque :

public E pollFirst() { int h = head; E result = (E) elements[h]; // ... other book-keeping operations removed, for simplicity head = (h + 1) & (elements.length - 1); return result; }

Pour expliquer la condition de concurrence potentielle dans le code ci-dessus, supposons que deux threads exécutent ce code comme indiqué dans la séquence ci-dessous:

  • Le premier thread exécute la troisième ligne: définit l'objet résultat avec l'élément à l'index 'head'
  • Le deuxième thread exécute la troisième ligne: définit l'objet résultat avec l'élément à l'index 'head'
  • Le premier thread exécute la cinquième ligne: réinitialise l'index 'head' à l'élément suivant dans le tableau de sauvegarde
  • Le deuxième thread exécute la cinquième ligne: réinitialise l'index 'head' à l'élément suivant dans le tableau de sauvegarde

Oops! Désormais, les deux exécutions renverraient le même objet de résultat .

Pour éviter de telles conditions de concurrence, dans ce cas, un thread ne doit pas exécuter la première ligne tant que l'autre thread n'a pas fini de réinitialiser l'index «head» à la cinquième ligne. En d'autres termes, accéder à l'élément à l'index «head» et réinitialiser l'index «head» devrait se faire de manière atomique pour un thread.

Clairement, dans ce cas, l'exécution correcte du code dépend du timing des threads et n'est donc pas sûre pour les threads.

4. Piles sans fil à l'aide de verrous

Dans cette section, nous discuterons de deux options possibles pour les implémentations concrètes d'une pile thread-safe .

En particulier, nous aborderons la pile Java et un ArrayDeque décoré thread-safe .

Les deux utilisent des verrous pour un accès mutuellement exclusif .

4.1. Utilisation de la pile Java

Java Collections a une implémentation héritée de Stack thread-safe , basée sur Vector qui est essentiellement une variante synchronisée de ArrayList.

Cependant, la documentation officielle elle-même suggère d'envisager d'utiliser ArrayDeque . Par conséquent, nous n'entrerons pas trop dans les détails.

Bien que Java Stack soit thread-safe et simple à utiliser, cette classe présente des inconvénients majeurs:

  • Il ne prend pas en charge la définition de la capacité initiale
  • Il utilise des verrous pour toutes les opérations. Cela peut nuire aux performances des exécutions à thread unique.

4.2. Utilisation d' ArrayDeque

L'utilisation de l' interface Deque est l'approche la plus pratique pour les structures de données LIFO car elle fournit toutes les opérations de pile nécessaires. ArrayDeque est l'une de ces implémentations concrètes .

Comme il n'utilise pas de verrous pour les opérations, les exécutions à un seul thread fonctionneraient très bien. Mais pour les exécutions multithreads, c'est problématique.

Cependant, nous pouvons implémenter un décorateur de synchronisation pour ArrayDeque. Bien que cela fonctionne de la même manière que la classe Stack de Java Collection Framework , le problème important de la classe Stack , le manque de paramètre de capacité initial, est résolu.

Jetons un coup d'œil à cette classe:

public class DequeBasedSynchronizedStack { // Internal Deque which gets decorated for synchronization. private ArrayDeque dequeStore; public DequeBasedSynchronizedStack(int initialCapacity) { this.dequeStore = new ArrayDeque(initialCapacity); } public DequeBasedSynchronizedStack() { dequeStore = new ArrayDeque(); } public synchronized T pop() { return this.dequeStore.pop(); } public synchronized void push(T element) { this.dequeStore.push(element); } public synchronized T peek() { return this.dequeStore.peek(); } public synchronized int size() { return this.dequeStore.size(); } }

Notez que notre solution n'implémente pas Deque lui-même pour plus de simplicité, car elle contient beaucoup plus de méthodes.

En outre, Guava contient SynchronizedDeque qui est une implémentation prête pour la production d'un ArrayDequeue décoré .

5. Piles sans fil sans verrouillage

ConcurrentLinkedDeque is a lock-free implementation of Deque interface. This implementation is completely thread-safe as it uses an efficient lock-free algorithm.

Lock-free implementations are immune to the following issues, unlike lock based ones.

  • Priority inversion – This occurs when the low-priority thread holds the lock needed by a high priority thread. This might cause the high-priority thread to block
  • Deadlocks – This occurs when different threads lock the same set of resources in a different order.

On top of that, Lock-free implementations have some features which make them perfect to use in both single and multi-threaded environments.

  • Pour les structures de données non partagées et pour l' accès à un seul thread, les performances seraient au pair avec ArrayDeque
  • Pour les structures de données partagées, les performances varient en fonction du nombre de threads qui y accèdent simultanément .

Et en termes de convivialité, ce n'est pas différent de ArrayDeque car les deux implémentent l' interface Deque .

6. Conclusion

Dans cet article, nous avons discuté de la structure des données de la pile et de ses avantages dans la conception de systèmes tels que le moteur de traitement de commandes et les évaluateurs d'expression.

En outre, nous avons analysé diverses implémentations de pile dans le cadre des collections Java et discuté de leurs performances et des nuances de sécurité des threads.

Comme d'habitude, des exemples de code peuvent être trouvés sur GitHub.