J'essaie de créer une mise en œuvre de la file d'attente sans verrouillage en Java, principalement pour l'apprentissage personnel. La file d'attente doit être générale, autorisant simultanément n'importe quel nombre de lecteurs et / ou d'écrivains.
Voulez-vous l'examiner et suggérer des améliorations / problèmes que vous trouvez? P>
Merci. P> Merci. P> Merci. P >
import java.util.concurrent.atomic.AtomicReference; public class LockFreeQueue<T> { private static class Node<E> { E value; volatile Node<E> next; Node(E value) { this.value = value; } } private AtomicReference<Node<T>> head, tail; public LockFreeQueue() { // have both head and tail point to a dummy node Node<T> dummyNode = new Node<T>(null); head = new AtomicReference<Node<T>>(dummyNode); tail = new AtomicReference<Node<T>>(dummyNode); } /** * Puts an object at the end of the queue. */ public void putObject(T value) { Node<T> newNode = new Node<T>(value); Node<T> prevTailNode = tail.getAndSet(newNode); prevTailNode.next = newNode; } /** * Gets an object from the beginning of the queue. The object is removed * from the queue. If there are no objects in the queue, returns null. */ public T getObject() { Node<T> headNode, valueNode; // move head node to the next node using atomic semantics // as long as next node is not null do { headNode = head.get(); valueNode = headNode.next; // try until the whole loop executes pseudo-atomically // (i.e. unaffected by modifications done by other threads) } while (valueNode != null && !head.compareAndSet(headNode, valueNode)); T value = (valueNode != null ? valueNode.value : null); // release the value pointed to by head, keeping the head node dummy if (valueNode != null) valueNode.value = null; return value; }
4 Réponses :
Le code n'est pas du thread-coffre-fort. Considérons L'instruction 2ND ajoute le nouveau nœud avant que le pointeur même si vous avez réparé cela, il y a un problème plus insidieux. Un fil de lecture Le champ Edit: En lisant le code de putobject (...) code>:
suivant de la noeud précédent code> a été défini. Cela n'arrive que dans la 3ème déclaration. Ainsi, il y a une fenêtre dans laquelle le
suivant code> est
null code>; C'est-à-dire une condition de course. P>
suivant code> pour un objet de nœud ne sera pas nécessairement em> voir la valeur qu'un deuxième thread vient d'écrire. C'est une conséquence du modèle de mémoire Java. Dans ce cas, la voie à s'assurer que la lecture suivante voit toujours la valeur écrite précédente est de: p>
suivant code> pour être
volatile code> ou li>
getObject () code> et
putobject () code> plus en détail, je peux voir que rien ne force la valeur non nulle de
Suivant code> pour être rincé à la mémoire dans
putobject code>, et rien ne force
getObject code> Pour lire
Suivant code> de la mémoire principale. Donc, le code
getObject code> peut voir la valeur erronée de
suivant code>, ce qui lui permet de retourner
null code> quand il y a vraiment un élément de la file d'attente. p> p>
Désolé, mais vous vous trompez avec la prochaine version nulle. En fait, Tail.Next est toujours nul, et cela ne fait aucun problème. Si la prochaine est NULL dans GetObject, la boucle se termine et NULL est renvoyée (la file d'attente est vide). En outre, la boucle de getObject ne peut tourner que si un autre thread a écrit la tête avec succès - par exemple. L'autre thread a réussi, ce que nous voulons d'algorithmes sans verrouillage.
Désolé, mais il est toujours incorrect, dans de nombreux domaines (l'ensemble Edit2, par exemple, indique que vous n'avez pas remarqué que la file d'attente contient toujours au moins un nœud factice).
Merci de votre aide. J'ai mis à jour mon code pour créer suivant code> volatiles et renommé
NextNode code> à
Valuenode code> dans
getObject () code> pour faire son but plus clair. Mais je suppose que la lecture d'une valeur fade dans le fil de lecteur ne fait pas le code "pas thread-coffre-fort"; C'est juste une question de performance, non?
@Hosam - Non, je pense que getObject () code> peut retourner
null code> quand il y a vraiment un élément de la file d'attente. En fait, cela peut le faire à plusieurs reprises.
@Stephen C: Oui, cela peut, mais cela ne fait que retarder le traitement de cet élément. Je suppose que cela dépend de la manière dont nous le considérons, si la disponibilité d'un élément de la file d'attente est requise immédiatement i> ou peut être reçue ultérieurement. Je l'ai réparé quand même (je pense), alors merci de le pointer.
@Hosam - 1) Il est théoriquement possible qu'un thread particulier ait toujours i> vu une valeur obsolète de la prochaine lorsqu'il appelle getObject () code>. 2) Je dirais que la méthode
getObject () code> qui renvoyée occasionnellement
null code> pour une file d'attente non vide enfreint le principe de la moins surprise.
@Stephen: Tu as raison. C'est certainement vrai. Avez-vous d'autres suggestions ou notes sur le code?
Je ne vois que deux problèmes avec votre code: P>
On est le problème avec les opérations de mémoire Commander Stephen C mentionné (peut être résolu en déclarant second est un élément plus subtil et non associé à la concurrence: après avoir renvoyé un objet dans Sinon, l'algorithme est correct. Une démonstration vague (supposer que ce qui précède est fixe): p>
l1: En conséquence, c'est que chaque objet dans Les objets ajoutés sont commandés de manière triviale par le Les objets de déséquilibre sont commandés conformément au succès Le Suivant code> et
de valeur code>
volatile code>) ( Nœud: la valeur a le même problème) p> li>
getObject code>, vous conservez toujours sa référence de la tête. Cela pourrait conduire à une fuite de mémoire. P> li>
ul>
queue code> ne peut jamais être supprimé de la file d'attente. Cela tient parce que quelque chose est stocké dans
queue code>, il a
suivant == null code>. En outre, lorsque vous attribuez quelque chose à
xxx.next code> (uniquement dans
putobject code>), il ne peut pas être
queue code>, en raison de l'atomicité du getAndset et de la commande entre l'écriture volatile et la lecture suivante - supposons que vous lisez un
non NULL code>, cette valeur doit avoir été écrite par
putobject code> et donc arrive-après em> la dernière ligne de celui-ci. Cela signifie qu'il arrive-après em> la ligne précédente, ce qui signifie que la valeur que nous lisons n'est pas de
queue code>. P>.
putobject code> sera éventuellement accessible de
tête code>. C'est parce que nous nous connectons après
queue code>, et ce nœud ne peut être supprimé qu'après que nous écrivions la référence du nouveau nœud à son
suivant code>, ce qui signifie que le nouveau nœud est accessible depuis
tête code>. p>
getAndset code> dans
putobject code>. p>
comparaisant des opérations code> dans
getObject code>. p>
getObject code> /
putobject code> est commandé en fonction de l'écriture / lecture au champ volatile
suivant code>. p>.
Comment voulez-vous dire "tu conserve toujours sa référence de la tête"? Head Code> est défini sur
NEXTNODE code> dans cette méthode.
Je veux dire, la valeur code> dans
newnode code> est renvoyée et retenue via
tête code>. Si aucun autre élément n'est pris à partir de la file d'attente (comme si la file d'attente est vide par la suite), la référence à la valeur renvoyée n'est jamais libérée.
Merci! J'ai corrigé la question de la fuite de mémoire et j'ai effectué suivant code> volatile. Mais je ne comprends pas encore pourquoi
la valeur code> doit être volatile. Pourriez-vous s'il vous plaît expliquer plus loin?
Je pense que vous obtiendrez une NPE lorsque vous essayez de "libérer la valeur ..." si vous appelez puisque vous n'effectuez aucune vérification de nullité sur valuenode code> là, malgré la protection contre elle ci-dessus. p> p>
Tu as raison. J'avais manqué ça totalement! Je l'ai réparé maintenant. Merci!
Vous devriez jeter un oeil à la mise en œuvre de Java.Util.ConCurrent.ConCurrentLinkedQueue http: //java.sun. COM / J2SE / 1.5.0 / DOCS / API / JAVA / UTIL / Concurrent / ConcurrentLinkedQueue.html Il fait à peu près ce que vous essayez d'atteindre p>
Merci. Je vais vérifier pour plus d'idées. Cependant, le ConcurrentLinkedqueue code> est trop complexe, car il prend en charge de nombreuses méthodes, tandis que ma file d'attente est beaucoup plus simple, ce qui me permet de faire plus d'hypothèses et d'essayer de plus d'optimisations.
Il y a un argument selon lequel le code sans verrouillage est complexe par nature. ;)
Portée à Code Review à codereview.stackexchange.com/questions/224/...