è questo (Lock-Free) Attuazione coda thread-safe?

Question

Sto cercando di creare una coda di implementazione senza blocchi in Java, soprattutto per l'apprendimento personale. La coda dovrebbe essere di carattere generale, che consente un numero illimitato di lettori e/o scrittori contemporaneamente.

La prego quindi di rivederlo, e qualsiasi proposta di miglioramento/problemi che si trovano?

Grazie.

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

Il codice non è thread-safe. Considerare putObject(...):

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

La seconda istruzione aggiunge il nuovo nodo prima che il puntatore del nodo precedente next è stata impostata. Questo succede solo nella 3a affermazione. Pertanto, v'è una finestra in cui la next è null; cioè una condizione di gara.

Anche se viene confermato che, c'è un problema più insidioso. Un thread che legge il campo next per un oggetto Node non sarà necessariamente vedere il valore che ha appena scritto un secondo thread. Questa è una conseguenza del modello di memoria Java. In questo caso, il modo per garantire che la seguente leggere sempre vede il valore scritto in precedenza è a uno:

• dichiarano next essere volatile, o
• fare entrambe le cose la lettura e la scrittura in un mutex primitiva sullo stesso oggetto.

EDIT: a leggere il codice per getObject() e putObject() più in dettaglio, posso vedere che nulla obbliga il valore non nullo di next da lavare a memoria putObject, e le forze nulla getObject leggere next da main memoria. Quindi il codice getObject potrebbe vedere il valore errato di next, provocando la restituzione di null quando c'è davvero un elemento nella coda.

Answer 2

Vedo solo due problemi con il suo codice:

• uno è il problema con operazioni di memoria ordinare Stephen C menzionato (può essere risolto dichiarando next e valuevolatile) (Node: valore ha lo stesso problema

• secondo è uno più sottile e non correlato alla concorrenza: dopo aver restituito un oggetto in getObject, si mantiene ancora il suo riferimento dalla testa. Ciò potrebbe causare una perdita di memoria.

Altrimenti l'algoritmo è OK. Una dimostrazione vaga (supponiamo che quanto sopra sia corretto):

L1: tail non può mai essere cancellato dalla coda. Ciò vale perché quando qualcosa è memorizzato in tail, ha next == null.Inoltre, quando si assegna qualcosa da xxx.next (solo in putObject), non può essere tail, a causa di atomicità della getAndSet e l'ordine tra i scrittura volatile e lettura successiva - Assumere si legge un non nullo tail.next, questo valore deve essere stato scritto da putObject e quindi succede dopo l' l'ultima riga di esso. Ciò significa che si verifica dopo la riga, il che significa che il valore che stiamo leggendo non è compreso tra tail.

Ne consegue che ogni oggetto in putObject sarà eventualmente raggiungibile da head. Questo perché ci stiamo connettendo dopo tail e questo nodo può essere eliminato solo dopo aver scritto il riferimento del nuovo nodo al suo next, il che significa che il nuovo nodo è raggiungibile da head.

Gli oggetti aggiunti sono banalmente ordinati dall'operazione getAndSet in putObject.

Gli oggetti in dequeued vengono ordinati in base alle operazioni effettuate con successo compareAndSet in getObject.

Gli getObject/putObject vengono ordinati in base alla scrittura/lettura sul campo volatile next.

Answer 3

credo che ci si ottiene un NPE quando si tenta di "liberare il valore ..." se si chiama

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

dal momento che non si esegue alcun controllo sulla nullità valueNode lì, nonostante la guardia contro sopra.

Answer 4

Si dovrebbe dare un'occhiata alla realizzazione di java.util.concurrent.ConcurrentLinkedQueue http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html Lo fa più o meno quello che si sta tentando di raggiungere