LinkedBlockingQueue vs ConcurrentLinkedQueue

1. Introduction

LinkedBlockingQueue et ConcurrentLinkedQueue sont les deux files d'attente simultanées les plus fréquemment utilisées en Java . Bien que les deux files d'attente soient souvent utilisées comme une structure de données simultanée, il existe des caractéristiques subtiles et des différences de comportement entre elles.

Dans ce court didacticiel, nous discuterons de ces deux files d'attente et expliquerons leurs similitudes et leurs différences.

2. LinkedBlockingQueue

Le LinkedBlockingQueue est un éventuellement délimitée mise en oeuvre des files d'attente de blocage, ce qui signifie que la taille de la file d' attente peut être spécifié si nécessaire.

Créons une LinkedBlockingQueue qui peut contenir jusqu'à 100 éléments:

BlockingQueue boundedQueue = new LinkedBlockingQueue(100);

Nous pouvons également créer une LinkedBlockingQueue illimitée simplement en ne spécifiant pas la taille:

BlockingQueue unboundedQueue = new LinkedBlockingQueue();

Une file d'attente illimitée implique que la taille de la file d'attente n'est pas spécifiée lors de la création. Par conséquent, la file d'attente peut croître de manière dynamique à mesure que des éléments y sont ajoutés. Cependant, s'il n'y a plus de mémoire, la file d'attente renvoie une erreur java.lang.OutOfMemoryError.

Nous pouvons également créer une LinkedBlockingQueue à partir d'une collection existante:

Collection listOfNumbers = Arrays.asList(1,2,3,4,5); BlockingQueue queue = new LinkedBlockingQueue(listOfNumbers);

La classe LinkedBlockingQueue implémente l' interface BlockingQueue , qui lui fournit la nature de blocage .

Une file d'attente de blocage indique que la file d'attente bloque le thread d'accès s'il est plein (lorsque la file d'attente est limitée) ou devient vide. Si la file d'attente est pleine, l'ajout d'un nouvel élément bloquera le thread d'accès à moins qu'il y ait de l'espace disponible pour le nouvel élément. De même, si la file d'attente est vide, l'accès à un élément bloque le thread appelant:

ExecutorService executorService = Executors.newFixedThreadPool(1); LinkedBlockingQueue queue = new LinkedBlockingQueue(); executorService.submit(() -> { try { queue.take(); } catch (InterruptedException e) { // exception handling } });

Dans l'extrait de code ci-dessus, nous accédons à une file d'attente vide. Par conséquent, la méthode take bloque le thread appelant.

La fonctionnalité de blocage de LinkedBlockingQueue est associée à un certain coût. Ce coût est dû au fait que chaque opération put ou take est un verrou entre le producteur ou les threads consommateurs. Par conséquent, dans les scénarios avec de nombreux producteurs et consommateurs, mettre et prendre des mesures pourrait être plus lent.

3. ConcurrentLinkedQueue

Un ConcurrentLinkedQueue est une file d'attente illimitée, thread-safe et non bloquante.

Créons un ConcurrentLinkedQueue vide :

ConcurrentLinkedQueue queue = new ConcurrentLinkedQueue();

Nous pouvons également créer un ConcurrentLinkedQueue à partir d'une collection existante:

Collection listOfNumbers = Arrays.asList(1,2,3,4,5); ConcurrentLinkedQueue queue = new ConcurrentLinkedQueue(listOfNumbers);

Contrairement à LinkedBlockingQueue, un ConcurrentLinkedQueue est une file d'attente non bloquante . Ainsi, il ne bloque pas un thread une fois que la file d'attente est vide. Au lieu de cela, il renvoie null . Depuis son illimité, il lancera une java.lang.OutOfMemoryError s'il n'y a pas de mémoire supplémentaire pour ajouter de nouveaux éléments.

En plus d'être non bloquant, un ConcurrentLinkedQueue a des fonctionnalités supplémentaires.

Dans tout scénario producteur-consommateur, les consommateurs ne se contenteront pas des producteurs; cependant, plusieurs producteurs s'affronteront:

int element = 1; ExecutorService executorService = Executors.newFixedThreadPool(2); ConcurrentLinkedQueue queue = new ConcurrentLinkedQueue(); Runnable offerTask = () -> queue.offer(element); Callable pollTask = () -> { while (queue.peek() != null) { return queue.poll().intValue(); } return null; }; executorService.submit(offerTask); Future returnedElement = executorService.submit(pollTask); assertThat(returnedElement.get().intValue(), is(equalTo(element))); 

La première tâche, offerTask , ajoute un élément à la file d'attente et la deuxième tâche, pollTask, récupère un élément de la file d'attente. La tâche d'interrogation vérifie en outre d'abord la file d'attente pour un élément car ConcurrentLinkedQueue n'est pas bloquant et peut renvoyer une valeur nulle .

4. Similitudes

Les deux LinkedBlockingQueue et la ConcurrentLinkedQueue sont mises en œuvre et la file d' attente partagent certaines caractéristiques communes. Discutons des similitudes de ces deux files d'attente:

  1. Les deux implémentent l' interface de file d'attente
  2. Ils utilisent tous les deux des nœuds liés pour stocker leurs éléments
  3. Les deux conviennent aux scénarios d'accès simultané

5. Différences

Bien que ces deux files d'attente présentent certaines similitudes, il existe également des différences de caractéristiques substantielles:

Fonctionnalité LinkedBlockingQueue ConcurrentLinkedQueue
Bloquer la nature C'est une file d'attente de blocage et implémente l' interface BlockingQueue Il s'agit d'une file d'attente non bloquante et n'implémente pas l' interface BlockingQueue
Taille de la file d'attente Il s'agit d'une file d'attente éventuellement délimitée, ce qui signifie qu'il existe des dispositions pour définir la taille de la file d'attente lors de la création Il s'agit d'une file d'attente illimitée et il n'y a aucune disposition pour spécifier la taille de la file d'attente lors de la création
Verrouiller la nature C'est une file d'attente basée sur le verrouillage C'est une file d'attente sans verrou
Algorithme Il implémente son verrouillage basé sur un algorithme de file d'attente à deux verrous Il repose sur l' algorithme Michael & Scott pour les files d'attente non bloquantes et sans verrouillage
la mise en oeuvre Dans le mécanisme d'algorithme de file d'attente à deux verrous , LinkedBlockingQueue utilise deux verrous différents - le putLock et le takeLock . Les opérations put / take utilisent le premier type de verrou et les opérations take / poll utilisent l'autre type de verrou Il utilise CAS (Compare-And-Swap ) pour ses opérations
Comportement de blocage C'est une file d'attente bloquante. Ainsi, il bloque les threads d'accès lorsque la file d'attente est vide Il ne bloque pas le thread d'accès lorsque la file d'attente est vide et renvoie null

6. Conclusion

Dans cet article, nous avons découvert LinkedBlockingQueue et ConcurrentLinkedQueue.

Tout d'abord, nous avons discuté individuellement de ces deux implémentations de file d'attente et de certaines de leurs caractéristiques. Ensuite, nous avons vu les similitudes entre ces deux implémentations de file d'attente. Enfin, nous avons exploré les différences entre ces deux implémentations de file d'attente.

Comme toujours, le code source des exemples est disponible à l'adresse over sur GitHub.