Implémentations Java Queue, lesquelles?

De Javadoc:

  • Un ConcurrentLinkedQueue est un choix approprié lorsque plusieurs threads partageront l’access à une collection commune. Cette queue n’autorise pas les éléments nuls.
  • ArrayBlockingQueue est un “tampon borné” classique dans lequel un tableau de taille fixe contient des éléments insérés par les producteurs et extraits par les consommateurs. Cette classe prend en charge une politique d’équité facultative pour la commande des threads producteurs et consommateurs en attente
  • LinkedBlockingQueue a généralement un débit plus élevé que les files d’attente basées sur des tableaux, mais des performances moins prévisibles dans la plupart des applications simultanées.

J’ai 2 scénarios, l’un nécessite que la queue prenne en charge de nombreux producteurs (threads l’utilisant) avec un consommateur et l’autre l’inverse.

Je ne comprends pas si je devrais utiliser ConcurrentLikedQueue ou les autres (les implémentations array ou linkedList). Wherent ‘toutes ces implémentations supposées être concurrentes? Je veux dire, quelqu’un peut-il m’expliquer quelle est la différence entre ConcurrentLikedQueue et LinkedBlockingQueue ?

En outre, quelle est la politique de justice optionnelle dans ArrayBlockingQueue s’il vous plaît?

    Fondamentalement, la différence entre eux sont les caractéristiques de performance et le comportement de blocage.

    En prenant d’abord le plus simple, ArrayBlockingQueue est une queue de taille fixe. Donc, si vous définissez la taille à 10 et que vous essayez d’insérer un élément 11, l’instruction insert sera bloquée jusqu’à ce qu’un autre thread supprime un élément. Le problème d’équité est ce qui se produit si plusieurs threads essaient d’insérer et de supprimer en même temps (en d’autres termes pendant la période où la queue a été bloquée). Un algorithme d’équité garantit que le premier thread qui demande est le premier thread qui obtient. Sinon, un thread donné peut attendre plus longtemps que les autres threads, provoquant un comportement imprévisible (parfois, un thread ne prendra que quelques secondes car les autres threads qui ont démarré plus tard ont été traités en premier). Le compromis est que cela prend du temps pour gérer l’équité, ce qui ralentit le débit.

    La différence la plus importante entre LinkedBlockingQueue et ConcurrentLinkedQueue est que si vous demandez un élément à un LinkedBlockingQueue et que la queue est vide, votre thread attendra qu’il y ait quelque chose. Un ConcurrentLinkedQueue retournera immédiatement avec le comportement d’une queue vide.

    Lequel dépend si vous avez besoin du blocage. Là où il y a beaucoup de producteurs et un consommateur, ça sonne comme ça. D’un autre côté, lorsque vous avez beaucoup de consommateurs et un seul producteur, vous n’avez peut-être pas besoin du comportement de blocage et vous pouvez simplement demander aux consommateurs de vérifier si la queue est vide et de continuer si c’est le cas.

    ConcurrentLinkedQueue signifie qu’aucun verrou n’est pris (c’est-à-dire pas d’appels synchronisés (this) ou Lock.lock ). Il utilisera une opération CAS – Compare and Swap pendant les modifications pour voir si le nœud head / tail est toujours le même qu’au démarrage. Si oui, l’opération réussit. Si le nœud tête / queue est différent, il tournera et essaiera à nouveau.

    LinkedBlockingQueue prendra un verrou avant toute modification. Ainsi, vos appels d’offres seraient bloqués jusqu’à ce qu’ils obtiennent le verrou. Vous pouvez utiliser la surcharge d’offre qui prend un TimeUnit pour dire que vous êtes seulement prêt à attendre X fois avant d’abandonner l’addition (généralement bon pour les files d’attente de type message où le message est périmé après X millisecondes).

    L’équité signifie que l’implémentation de Lock gardera les threads commandés. Ce qui signifie que le thread A entre et que le thread B entre, le thread A obtiendra le verrou en premier. Sans équité, c’est vraiment indéfini ce qui se passe. Ce sera probablement le prochain thread qui sera planifié.

    Quant à savoir lequel utiliser, cela dépend. J’ai tendance à utiliser ConcurrentLinkedQueue car le temps qu’il faut à mes producteurs pour mettre le travail en queue est varié. Je n’ai pas beaucoup de producteurs qui produisent exactement au même moment. Mais le côté consommateur est plus compliqué car le sondage ne va pas dans un bon état de sumil. Vous devez gérer cela vous-même.

    Le titre de votre question mentionne les files d’attente bloquantes. Cependant, ConcurrentLinkedQueue n’est pas une queue bloquante.

    Les BlockingQueue sont ArrayBlockingQueue , DelayQueue , LinkedBlockingDeque , LinkedBlockingQueue , PriorityBlockingQueue et SynchronousQueue .

    Certains d’entre eux ne sont clairement pas adaptés à votre objective ( DelayQueue , PriorityBlockingQueue et SynchronousQueue ). LinkedBlockingQueue et LinkedBlockingDeque sont identiques, sauf que ce dernier est une queue à double extrémité (il implémente l’interface Deque).

    ArrayBlockingQueue n’étant utile que si vous souhaitez limiter le nombre d’éléments, je m’en LinkedBlockingQueue à LinkedBlockingQueue .

    ArrayBlockingQueue a un encombrement mémoire inférieur, il peut réutiliser un nœud d’élément, pas comme LinkedBlockingQueue qui doit créer un object LinkedBlockingQueue $ Node pour chaque nouvelle insertion.

    1. SynchronousQueue (Extrait d’une autre question )

    SynchronousQueue est plus un transfert, alors que LinkedBlockingQueue ne permet qu’un seul élément. La différence étant que l’appel de put () à un SynchronousQueue ne retournera pas avant qu’il y ait un appel à take () correspondant, mais avec un LinkedBlockingQueue de taille 1, l’appel de put () à une queue vide sera renvoyé immédiatement. C’est essentiellement l’implémentation de BlockingQueue pour les cas où vous ne voulez pas vraiment de queue (vous ne souhaitez pas conserver de données en attente).

    2. LinkedBlockingQueue (implémentation LinkedList mais pas implémentation JDK de LinkedList Il utilise la classe interne statique Node pour maintenir les liens entre les éléments)

    Constructeur pour LinkedBlockingQueue

     public LinkedBlockingQueue(int capacity) { if (capacity < = 0) throw new IllegalArgumentException(); this.capacity = capacity; last = head = new Node< E >(null); // Maintains a underlying linkedlist. ( Use when size is not known ) } 

    Classe de noeud Utilisée pour gérer les liens

     static class Node { E item; Node next; Node(E x) { item = x; } } 

    3. ArrayBlockingQueue (implémentation de tableau)

    Constructeur pour ArrayBlockingQueue

     public ArrayBlockingQueue(int capacity, boolean fair) { if (capacity < = 0) throw new IllegalArgumentException(); this.items = new Object[capacity]; // Maintains a underlying array lock = new ReentrantLock(fair); notEmpty = lock.newCondition(); notFull = lock.newCondition(); } 

    La plus grande différence IMHO entre ArrayBlockingQueue et LinkedBlockingQueue est claire: le constructeur a une structure de données sous-jacente Array et une autre liste de liens .

    ArrayBlockingQueue utilise un algorithme à double condition de locking unique et LinkedBlockingQueue est une variante de l'algorithme "two lock queue" et possède 2 conditions de locking 2 (takeLock, putLock)

    ConcurrentLinkedQueue est sans verrou, LinkedBlockingQueue ne l’est pas. Chaque fois que vous appelez LinkedBlockingQueue.put () ou LinkedBlockingQueue.take (), vous devez d’abord acquérir le verrou. En d’autres termes, LinkedBlockingQueue a peu de concurrence. Si les performances vous intéressent, essayez ConcurrentLinkedQueue + LockSupport.