Quelle implémentation de file d'attente concurrente dois-je utiliser en Java ?

Question

Extrait des JavaDocs :

• A File d'attente simultanée (ConcurrentLinkedQueueue) est un choix approprié lorsque plusieurs threads partagent l'accès à une collection commune. Cette file d'attente n'autorise pas les éléments nuls.
• ArrayBlockingQueue est un "tampon limité" 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é optionnelle pour ordonner les fils d'attente des producteurs et des consommateurs
• LinkedBlockingQueue ont 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 concurrentes.

J'ai deux scénarios, l'un exige que la file d'attente supporte de nombreux producteurs (threads qui l'utilisent) avec un seul consommateur et l'autre est dans l'autre sens.

Je ne comprends pas quelle implémentation utiliser. Quelqu'un peut-il m'expliquer quelles sont les différences ?

Par ailleurs, quelle est la "politique d'équité optionnelle" dans le cadre de la ArrayBlockingQueue ?

Answer 1

File d'attente simultanée (ConcurrentLinkedQueueue) signifie qu'aucun verrou n'est pris (c'est-à-dire qu'il n'y a pas de synchronized(this) ou de [Lock.lock](http://java.sun.com/javase/6/docs/api/java/util/concurrent/locks/Lock.html#lock()) ). Il utilisera un CAS - Comparer et échanger pendant les modifications pour voir si le nœud de tête/queue est toujours le même qu'au début. Si c'est le cas, l'opération réussit. Si le nœud tête/queue est différent, l'opération tourne sur elle-même et recommence.

LinkedBlockingQueue sera verrouillé avant toute modification. Vos appels d'offres se bloqueront donc jusqu'à ce qu'ils obtiennent le verrou. Vous pouvez utiliser la surcharge d'offre qui prend une unité de temps pour dire que vous n'êtes prêt à attendre que X temps avant d'abandonner l'ajout (c'est 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 du verrouillage maintiendra l'ordre des threads. Cela signifie que si le thread A entre et que le thread B entre ensuite, le thread A obtiendra le verrou en premier. En l'absence d'équité, ce qui se passe n'est pas vraiment défini. Il est fort probable que ce soit le prochain thread qui soit programmé.

Quant à savoir lequel utiliser, cela dépend. J'ai tendance à utiliser File d'attente simultanée (ConcurrentLinkedQueueue) parce que le temps qu'il faut à mes producteurs pour obtenir du travail à mettre dans la file d'attente est varié. Je n'ai pas beaucoup de producteurs qui produisent exactement au même moment. Du côté des consommateurs, c'est plus compliqué, car les sondages ne se mettent pas en veilleuse. Il faut s'en occuper soi-même.

Answer 2

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

En prenant le plus facile d'abord, ArrayBlockingQueue est une file d'attente de taille fixe. Donc, si vous réglez la taille à 10, et essayez d'insérer une 11ème élément, l'instruction insert bloqué jusqu'à ce qu'un autre thread supprime un élément. L'équité, la question est de savoir ce qui se passe si plusieurs threads tentent d'insérer et de supprimer en même temps (en d'autres termes, pendant la période où la File d'attente a été bloqué). Un surveillant de l'équité algorithme garantit que le premier thread qui demande, c'est que le premier thread qui l'obtient. Sinon, un thread peut attendre plus longtemps que d'autres threads, ce qui entraîne un comportement imprévisible (parfois un seul fil suffit de prendre plusieurs secondes parce que les autres threads qui a commencé plus tard, reçu traité en premier). Le compromis, c'est qu'il prend des frais généraux pour gérer l'équité, de ralentir le débit.

La différence la plus importante entre LinkedBlockingQueue et ConcurrentLinkedQueue est que si vous demandez un élément à partir d'un LinkedBlockingQueue et la file d'attente est vide, votre fil d'attente jusqu'à ce qu'il y a quelque chose là-bas. Un ConcurrentLinkedQueue sera de retour tout de suite avec le comportement d'un vide de la file d'attente.

Qui dépend de si vous avez besoin du blocage. Lorsque vous avez de nombreux producteurs et consommateurs, on dirait qu'elle. D'autre part, lorsque vous avez de nombreux consommateurs et un seul producteur, vous ne pouvez pas besoin du comportement de blocage, et peut-être heureux d'avoir juste les consommateurs de vérifier si la file d'attente est vide, et se déplacer sur si il est.

Answer 3

Le titre de votre question mentionne les files d'attente bloquantes. Cependant, ConcurrentLinkedQueue es pas une file d'attente bloquante.

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

Certains d'entre eux ne sont manifestement pas adaptés à votre objectif ( DelayQueue , PriorityBlockingQueue et SynchronousQueue ). LinkedBlockingQueue y LinkedBlockingDeque sont identiques, sauf que cette dernière est une file d'attente à double extrémité (elle implémente l'interface Deque).

Depuis ArrayBlockingQueue n'est utile que si vous voulez limiter le nombre d'éléments, je m'en tiendrai à LinkedBlockingQueue .

Answer 4

ArrayBlockingQueue a une empreinte mémoire plus faible, il peut réutiliser un nœud d'élément, contrairement à LinkedBlockingQueue qui doit créer un objet LinkedBlockingQue$Node pour chaque nouvelle insertion.

Answer 5

1. SynchronousQueue (Tiré d'un autre question )

SynchronousQueue est plutôt un transfert, alors que le LinkedBlockingQueue n'autorise qu'un seul élément. La différence est que l'élément put() appel à un SynchronousQueue ne reviendra pas tant qu'il n'y aura pas de take() mais avec un LinkedBlockingQueue de taille 1, le put() (vers une file d'attente vide) sera renvoyé immédiatement. Il s'agit essentiellement de la méthode BlockingQueue pour les cas où vous ne voulez pas vraiment de file d'attente (vous ne voulez pas maintenir de données en attente).

2. LinkedBlockingQueue ( LinkedList Mise en œuvre mais pas exactement Mise en œuvre 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 nœuds utilisée pour maintenir les liens

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

3 . ArrayBlockingQueue ( Mise en œuvre d'un 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();
}

IMHO La plus grande différence entre ArrayBlockingQueue y LinkedBlockingQueue est clair dans le constructeur, on a structure de données sous-jacente Array et autres linkedList .

ArrayBlockingQueue utilise algorithme de double condition à verrouillage unique y LinkedBlockingQueue est une variante de l'algorithme "two lock queue" et comporte 2 verrous 2 conditions ( takeLock , putLock)