ConcurrentLinkQueue实现陷入死锁

Question

我正在学习并发编程，并使用AtomicReference编写了这个concurrentLinkeQueue。

以下示例进入死锁。 请看。

 package concurrent.AtomicE;
 import java.util.concurrent.atomic.AtomicReference;
 public class ConcurrentLinkQueue<V> {
private AtomicReference<Node> head = new AtomicReference<Node>();
public void offer(final V data) {
    final Node<V> newNode = new Node<V>(data,Thread.currentThread().getName());
    System.out.println("*********** NEW "+ newNode);
    AtomicReference<Node> pointer = head;
    for(;;){
         if(pointer.get() == null){ // Threads wait here for infinite time
             final boolean success = pointer.compareAndSet(null,newNode);
             System.out.println(Thread.currentThread().getName() +" " + success);
             if(success)
             {
                 System.out.println(Thread.currentThread().getName() +"Returning");
                 return;
             }else{
                 final Node<V> current = pointer.get();
                 pointer = current.next;
                 System.out.println(Thread.currentThread().getName() +" Next Pointer");
             }
        }
    }
}
public void printQueueData(){
    AtomicReference<Node> pointer = head;
    for(;pointer!=null;){
        final Node node = pointer.get();
        System.out.println(node);
        pointer = node.next;
    }
}
private static class Node<V>{
    private AtomicReference<Node> next;
    private volatile V data = null;
    private String threadName = "";
    Node(V data1,String threadName){
        this.data = data1;
        this.threadName = threadName;
    }
    @Override
    public String toString() {
        return  "threadName=" + threadName +
                ", data=" + data;
    }
    private AtomicReference<Node> getNext() {
        return next;
    }
    private void setNext(AtomicReference<Node> next) {
        this.next = next;
    }
    private V getData() {
        return data;
    }
    private void setData(V data) {
        this.data = data;
    }
}

}

      package concurrent.AtomicE;
 import java.util.concurrent.Executors;
 import java.util.concurrent.atomic.AtomicIntegerFieldUpdater;
 public class Main {
private static final ConcurrentLinkQueue<Integer> clq =  new ConcurrentLinkQueue<Integer>();
public static void main(String[] args) throws InterruptedException {
    Task t = new Task();
    Thread t1 = new Thread(t); t1.setName("t1");
    Thread t2 = new Thread(t); t2.setName("t2");
    //Thread t3 = new Thread(t); t3.setName("t3");
    //Thread t4 = new Thread(t); t4.setName("t4");
    //Thread t5 = new Thread(t); t5.setName("t5");
    t1.start();
    t2.start();
    //t3.start();
    //t4.start();
    //t5.start();
    t1.join();
    t2.join();
    //t3.join();
    //t4.join();
    //t5.join();

}
private static class Task implements Runnable{
    @Override
    public void run() {
        for(int i=0;i<5;++i){
            clq.offer(i);
        }
    }
}

}

进行线程转储后，它显示线程在下一行永远等待

 if(pointer.get() == null){ // Threads wait here for infinite time

你能帮忙为什么线程永远在这里等待吗？

[编辑]解决了--->

 public class ConcurrentLinkQueue<V> {
  private final AtomicReference<Node> firstNodePointer = new AtomicReference<Node>();
public void offer(final V data) {
    final Node<V> newNode = new Node<V>(data,Thread.currentThread().getName());
    System.out.println(newNode);
    final Node<Integer> firstNode = firstNodePointer.get();
    if(firstNode == null){
        if(firstNodePointer.compareAndSet(null,newNode) == true)
            return;
    }
    boolean success = false;
    Node<Integer> nodePointer = firstNode;
    AtomicReference<Node> atomicRefPointer = firstNodePointer;
    while(!success){
        atomicRefPointer = nodePointer.getNext();
        if(atomicRefPointer.get() == null){
            success = atomicRefPointer.compareAndSet(null,newNode);
        }else{
            nodePointer = atomicRefPointer.get();
        }
    }
}

}

另一种解决方案->

      public void fastOffer(final V data){
    final Node<V> newNode = new Node<V>(data,Thread.currentThread().getName());
    System.out.println(newNode);
    AtomicReference<Node> pointer = firstNodePointer;
    for(;;){
            if(pointer.compareAndSet(null,newNode)){
                return;
            }
        pointer = pointer.get().getNext();
    }
}

Answer 1

在您的

示例条件中，pointer.get() == null总是返回false除了将其分配给head时的第一种情况，因为Node类中它null。您可以为其分配默认值并删除空检查。

我建议你改变一点 Node 类，使其不可变：

 private static class Node<V> {
        private final AtomicReference<Node> next = new AtomicReference<>();
        private final V data;
        private final String threadName;
        Node(V data1, String threadName) {
            this.data = data1;
            this.threadName = threadName;
        }
    }

然后，您可以简单地浏览所有元素：

private final AtomicReference<Node> head = new AtomicReference<>();
@SuppressWarnings("unchecked")
public void offer(final V data) {
    // create new Node
    final Node<V> newNode = new Node<>(data, Thread.currentThread().getName());
    // set root element if it's null
    if (head.compareAndSet(null, newNode)) {
        return;
    }
    // else pass trough all elements and try to set new
    Node<V> pointer = head.get();
    for (;;) {
        if (pointer.next.compareAndSet(null, newNode)) {
            break;
        }
        pointer = pointer.next.get();
    }
}

并更改打印方法：

    @SuppressWarnings("unchecked")
    public void printQueueData() {
        AtomicReference<Node> pointer = head;
        while (pointer.get() != null) {
            System.out.println(pointer.get().data);
            pointer = pointer.get().next;
        }
    }