LinkedBlockingQueue vs ConcurrentLinkedQueue

Cette question mérite une meilleure réponse.

Java ConcurrentLinkedQueue est basé sur le célèbre algorithme de Maged M. Michael et Michael L. Scott for non-blocking lock-free queues.

"Non-blocking" comme un terme ici pour une ressource contestée (notre file d'attente) signifie que peu importe ce que fait l'ordonnanceur de la plateforme, comme interrompre un thread, ou si le thread en question est tout simplement trop lent, d'autres threads rivalisant pour la même ressource pourront encore progresser. Si une serrure est impliquée par exemple, le fil qui retient la serrure pourrait être interrompu et tous les fils qui attendent cette serrure seraient bloqués. Les serrures intrinsèques (le mot-clé synchronized ) en Java peuvent également être assorties d'une pénalité sévère pour les performances-comme lorsque biased locking est en cause et que vous avez des problèmes, ou lorsque la VM décide de "gonfler" la serrure après un délai de grâce de spin et bloc en soutenant des threads ... c'est pourquoi dans de nombreux contextes (scénarios de conflit faible/moyen), faire des comparaisons sur les références atomiques peut être beaucoup plus efficace et c'est exactement ce que font de nombreuses structures de données non bloquantes.

Java ConcurrentLinkedQueue n'est pas seulement non-bloquant, mais il a la propriété impressionnante que le producteur ne conteste pas avec le consommateur. Dans un scénario producteur unique / consommateur unique (SPSC), cela signifie vraiment qu'il n'y aura pas contention pour en parler. Dans un scénario de producteurs multiples et de consommateurs uniques, le consommateur ne fera pas face aux producteurs. Cette file d'attente est contestée lorsque plusieurs producteurs tentent de offer() , mais c'est la concurrence par définition. C'est essentiellement un but général et une file d'attente non bloquante efficace.

quant au fait qu'il ne s'agisse pas d'un BlockingQueue , bien, bloquer un fil pour attendre sur une file d'attente est une façon affreusement terrible de concevoir des systèmes concurrents. Ne le faites pas. Si vous ne pouvez pas comprendre comment utiliser un ConcurrentLinkedQueue dans un scénario de consommateur/producteur, puis passer à des abstractions de plus haut niveau, comme un bon cadre d'acteur.

LinkedBlockingQueue bloque le consommateur ou le producteur lorsque la file d'attente est vide ou pleine et que le fil respectif du consommateur/producteur est endormi. Mais cette fonction de blocage a un coût: chaque opération de put or take est un lock disputé entre les producteurs ou les consommateurs (si plusieurs), donc dans les scénarios avec de nombreux producteurs/consommateurs, l'opération pourrait être plus lente.

ConcurrentLinkedQueue n'utilise pas de serrures, mais CAS , sur ses opérations de put / take possibilité de réduire les conflits avec de nombreux fils conducteurs de producteurs et de consommateurs. Mais étant une structure de données "sans attente", ConcurrentLinkedQueue ne bloquera pas une fois vide, ce qui signifie que le consommateur devra traiter avec le take() retour null valeurs par "attente occupée", par exemple, avec le fil de consommation manger JUSQU'à CPU.

ainsi, qui est "meilleur" dépend du nombre de fils de consommation, de la vitesse qu'ils consomment/produisent, etc. Une référence est nécessaire pour chaque scénario.

un cas particulier d'utilisation où le ConcurrentLinkedQueue est nettement meilleur est lorsque les producteurs produisent d'abord quelque chose et finir leur travail en plaçant le travail dans la file d'attente et seulement après les consommateurs commencent à consommer, sachant qu'ils seront faits quand la file d'attente est vide. (il n'y a pas de concurrence entre producteur-consommateur, mais seulement entre Producteur-Producteur et consommateur-consommateur)

une autre solution (qui n'est pas à bonne échelle) est les canaux de rendez-vous : java.util.simultaneousqueue synchrone

si votre file d'attente n'est pas extensible et ne contient qu'un fil producteur/consommateur. Vous pouvez utiliser la file d'attente lockless (vous n'avez pas besoin de verrouiller l'accès aux données).