Czy ta (bez blokady) implementacja kolejki wątku jest bezpieczna?

Question

Próbuję utworzyć pozbawioną blokady implementację kolejki w Javie, głównie do osobistej nauki. Kolejka powinna być ogólna, pozwalając jednocześnie na dowolną liczbę czytników i/lub pisarzy.

Czy możesz ją przejrzeć i zasugerować wszelkie ulepszenia/problemy, które można znaleźć?

Dziękuję.

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; 
} 

Answer 1

Kod nie jest wątkowo bezpieczny. Rozważmy putObject(...):

public void putObject(T value) { 
    Node<T> newNode = new Node<T>(value); 
    Node<T> prevTailNode = tail.getAndSet(newNode); 
    prevTailNode.next = newNode; 
} 

The 2nd Oświadczenie dodaje nowy węzeł przed poprzednim węzła next wskaźnik został ustawiony. Tak dzieje się tylko w trzecim stwierdzeniu. Tak więc, istnieje okno, w którym next jest ; tj. stan wyścigu.

Nawet jeśli to naprawiono, istnieje bardziej podstępny problem. Wątek odczytujący pole next dla obiektu węzła nie będzie koniecznie widzieć wartości, którą właśnie napisał drugi wątek. To jest konsekwencja modelu pamięci Java. W tym przypadku, sposób zapewnić że następujący czytać zawsze widzi wcześniejszą pisemną wartość jest albo:

• zadeklarować next być volatile lub
• zrobić zarówno czytania i pisania w prymitywnym mutex na tym samym obiekcie.

EDIT: po odczytaniu kodu dla getObject() i putObject() dokładniej, widzę, że nic nie zmusza niezerową wartość next być zaczerwieniona pamięci w putObject, a siły nic getObject czytać next z głównym pamięć. Tak więc kod getObject może zobaczyć niewłaściwą wartość next, powodując, że zwróci null, gdy rzeczywiście jest element w kolejce.

Answer 2

widzę tylko dwa problemy z kodu:

• jeden jest problem z operacje pamięciowe zamawiania Stephen C wspomniano (może być rozwiązany poprzez uznanie next i valuevolatile) (Node: wartość ma ten sam problem)

• sekunda jest bardziej subtelna, a nie współbieżność: po zwróceniu obiektu w getObject, nadal zachowujesz swoje odniesienie z głowy. Może to doprowadzić do wycieku pamięci.

W przeciwnym razie algorytm jest OK. Niejasna demonstracja (zakładamy, że powyższe zostały naprawione):

L1: tail nie można usunąć z kolejki. Dzieje się tak, ponieważ gdy coś jest przechowywane w tail, ma ono wartość next == null.Ponadto, gdy przypisujesz coś do xxx.next (tylko w putObject), nie może to być tail, ze względu na atomowość getAndSet i kolejność między lotnym zapisywaniem a kolejnym czytaniem - zakładając, że czytasz wartość inną niż null tail.next, ta wartość musiała zostać zapisana przez putObject, a zatem dzieje się po w ostatnim wierszu. Oznacza to, że dzieje się po w poprzednim wierszu, co oznacza, że ​​wartość, którą odczytujemy, nie pochodzi z tail.

Konsekwencją tego jest to, że każdy obiekt w putObject będzie ostatecznie dostępny z poziomu head. Dzieje się tak, ponieważ łączymy się po tail, a ten węzeł może zostać usunięty dopiero po zapisaniu referencji nowego węzła do jego next, co oznacza, że ​​nowy węzeł jest osiągalny od head.

Dodane obiekty są banalnie sortowane przez operację getAndSet w putObject.

Wycofane obiekty są sortowane zgodnie z pomyślnymi operacjami compareAndSet w getObject.

Modele getObject/putObject są uporządkowane zgodnie z zapisem/odczytem dla pola zmiennego next.

Answer 3

wierzę, że masz NPE podczas próby do „uwolnienia wartość ...” jeśli zadzwonisz

new LockFreeQueue<?>().getObject(); 

ponieważ nie wykonywać żadnych kontroli nieważności na valueNode tam, mimo zabezpieczenia przed to powyżej.

Answer 4

Należy przyjrzeć się realizacji java.util.concurrent.ConcurrentLinkedQueue http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html Czyni dość dużo, co chce osiągnąć