La file d'attente LinkedBlocking a deux verrous, un pour mettre, un pour prendre. Lorsque la taille de la file d'attente est de 1, je pense que deux threads peuvent verrouiller et manipuler la file d'attente simultanément, ce qui entraînera un comportement indéfini. Est-ce que je me trompe?
// method put: // method take:
// put lock // take lock
putLocK.lockInterruptibly(); takeLock.lockInterruptibly();
... ...
while(count.get() == capacity){ while(count.get() == 0){
notFull.await(); notEmpty.await();
} }
enqueue(node); x = dequeue();
// method enqueue: // method dequeue:
last = last.next = node; Node<E> h = head;
... Node<E> first = h.next;
h.next = h;
head = first;
E x = first.item;
first.item = null;
return x;
Mettre clairement le thread et le thread de prise peuvent se verrouiller quand il n'y a qu'un seul élément dans la file d'attente, donc ils exécuteront respectivement des codes dans la mise en file d'attente de la méthode et la suppression de la file d'attente. Je veux dire si take thread entre dans la méthode dequeue, après toute cette modification du pointeur, ne heurte-t-il pas les codes en file d'attente?
Les liens ici indiquent "Cependant, lorsque la file d'attente est vide, la contention ne peut pas être évitée, et donc un code supplémentaire est nécessaire pour gérer ce cas commun 'edge' "
3 Réponses :
mettre l'implémentation d'un LinkedBlockingQueue
public void put(E e) throws InterruptedException {
// some lock and node code
// the part that matters here
try {
while (count.get() == capacity) {
notFull.await();
}
// put the item in the queue.
} finally {
// not important here
}
}
Fondamentalement, dans put , le thread appelant attendez que la capacité soit inférieure à la capacité maximale continue.
Même si le thread qui met la valeur sur la file d'attente saisit un verrou différent du thread de prise, il attend d'ajouter dans la file d'attente jusqu'à ce que la file d'attente ne soit pas pleine.
take a une implémentation similaire en ce qui concerne notEmpty au lieu de notFull code >.
Ce qu'Ivan dit est faux, LinkedBlockingQueue a deux verrous. Je veux juste savoir comment cela peut être thread-safe lorsque la taille est de 1.
S'ils saisissent respectivement leur propre verrou, qui est "putLock" et "takeLock". En théorie, les deux threads peuvent mettre et prendre le seul élément en même temps. MAIS en pratique, non, pourquoi?
Cela ne peut pas se produire en même temps car take ne peut prendre que s'il y a un élément dans la file d'attente, et put ne peut mettre que s'il n'y a aucun élément dans la file d'attente. Dans le cas où la taille est de 1, l'un des deux ne peut rien faire jusqu'à ce que l'autre se produise, c'est pourquoi il est sûr
@asapdiablo J'ai ajouté quelques modifications à ma réponse pour aider à mieux clarifier.
Si la mise ne se produit que dans la file d'attente vide, la sécurité des threads peut être garantie.
Vous avez raison. Encore une fois, cela suppose que la taille de la file d'attente est de 1.
non! Put peut se produire lorsque la file d'attente n'est pas vide. Si la mise ne peut pas se produire, le débit de la file d'attente sera très faible. Il y a donc une autre raison pour laquelle les threads sont sécurisés.
Par put peut arriver, je suppose que vous voulez dire que vous pouvez appeler put lorsque la file d'attente n'est pas vide. C'est vrai. Mais il bloquera ensuite le thread appelant et attendra que la file d'attente soit vide avant de placer l'élément.
Dans le code source, le thread put ne bloquera que si "count == capacity". Supposons ensuite qu'il y ait un élément dans la file d'attente et que la capacité soit de 5, maintenant prendre et mettre peuvent tous les deux obtenir leurs verrous. Si mon opinion est vraie, comment la file d'attente garantit-elle la sécurité des threads?
Le javadoc pour BlockingQueue (la superclasse de LinkedBlockingQueue) déclare ceci:
Les implémentations de
BlockingQueuesont thread-safe. Toutes les méthodes de mise en file d'attente produisent leurs effets de manière atomique en utilisant des verrous internes ou d'autres formes de contrôle d'accès concurrentiel.
Le mot "atomiquement" signifie que si deux opérations (par exemple un put et une take ) se produisent simultanément, alors l'implémentation s'assurera qu'elles se comportent selon le Contrat. L'effet sera comme si le put se produisait avant get ou vice-versa. Cela s'applique également aux cas limites, comme votre exemple de file d'attente avec un élément.
En fait, puisque put et get sont des opérations bloquantes, l'ordre relatif des deux opérations n'a pas d'importance. Avec offre / sondage ou add / remove la commande importe , mais vous ne peut pas le contrôler.
Veuillez noter que ce qui précède est basé uniquement sur ce que dit le javadoc. En supposant que j'ai correctement interprété le javadoc, cela s'applique à toutes les implémentations 1 BlockingQueue , qu'elles utilisent un ou deux verrous ... ou aucun. Si une implémentation de BlockingQueue ne se comporte pas comme ci-dessus, c'est un bug!
1 - Toutes les implémentations qui implémentent correctement l'API. Cela devrait couvrir toutes les classes Java SE.
La doc elle-même définit uniquement le comportement, je veux juste savoir comment l'implémentation garantit la sécurité des threads lorsque size = 1.
"Je veux juste savoir comment l'implémentation garantit la sécurité des threads lorsque size = 1." - Il est sans fil. Le javadoc le dit, et s'il y avait un bug d'implémentation qui l'empêchait d'être thread-safe, il aurait été trouvé il y a ans .
Après 2 jours de recherche, je comprends enfin ... Lorsque la file d'attente n'a qu'un seul élément, selon la conception de LinkedBlocking Queue, il y a en fait deux nœuds: la tête factice et vraiment l'élément (le dernier pointant vers lui). Il est vrai que put thread et take thread peuvent tous les deux obtenir leur verrou, mais ils modifient différentes parties de la file d'attente.
Put thread appellera
Node<E> h = head; Node<E> first = h.next; // first also points to the only item in queue h.next = h; head = first; E x = first.item; first.item = null; return x;
Take thread appellera
last = last.next = node; // last points to the only item in queue
L'intersection de ces deux threads est ce vers quoi le dernier pointe dans le thread put et ce vers quoi pointe le premier dans le thread take. Notez que put thread ne modifie que last.item et que take thread ne modifie que first.next. Bien que ces deux threads modifient la même instance d'objet, ils modifient les différents membres de celui-ci, et cela n'entraînera aucun conflit de thread.
Pour info: il n'y a pas de «simultané» lorsque vous parlez d'objets partagés et d'un système informatique multiprocesseur classique. Pour que les threads communiquent via des objets partagés, ils doivent lire et écrire des emplacements dans la mémoire principale du système. Un système conventionnel n'a qu'un seul bus mémoire, et chaque lecture et chaque écriture doivent passer par ce bus en un seul fichier. Une grande partie de la compréhension des problèmes multiprocesseurs consiste à comprendre et à anticiper les différentes façons dont les requêtes de lecture et d'écriture peuvent être sérialisées par le matériel lorsque les threads tentent d'utiliser le bus à le même temps.
Je pense que deux threads peuvent verrouiller et manipuler la file d'attente simultanément ... Non. Le but du verrouillage est que deux threads ne peuvent pas se verrouiller simultanément.
@shmosel Deux threads, deux verrous différents. On modifie la tête, on modifie la queue. LinkedBlockingQueue est conçu pour mettre et prendre en même temps.