簡單的無鎖堆棧

Question

最近已經發現這樣的Java併發採訪任務：

寫了兩種方法簡單無鎖堆棧：push和pop。

我做了concent：

import java.util.concurrent.atomic.AtomicInteger; 


public class Stack { 
    private AtomicInteger count = new AtomicInteger(-1); 
    private Object[] data = new Object[1000]; 

    public void push(Object o) { 
     int c = count.incrementAndGet(); 
     data[c] = o; 
    } 

    public Object pop() { 
     Object top; 
     int c; 
     while (true) { 
      c = count.get(); 
      if (c == -1) return null; 
      top = data[c]; 
      if (count.compareAndSet(c, c-1)) 
       return top; 
     } 
    } 
} 

它是類似辦法預計？或者「無鎖棧」意味着不同的東西？請幫助一位java面試新手。

Answer 1

你已經開始朝着正確的方向思考如何使用Java的原子整數和原子函數。這將是一個無鎖棧，如下所示：沒有明確的鎖。但是，併發訪問仍然不正確，並且要證明：想象你的push（）線程在獲取計數和將新元素添加到堆棧之間阻塞（data [c] = o） ，同時一個pop（）線程出現，獲得更高的計數，並彈出...什麼？無論在堆棧中該位置的內存中發生了什麼，也不是Object o（因爲它尚未被插入）。

這就是無鎖，數組支持的堆棧的問題，你有兩件事理論上需要調整，特定單元的數量和內容，而且你不能同時在原子上同時執行時間。我不知道有任何無鎖陣列支持堆棧算法。

有鏈接列表支持的堆棧算法雖然是無鎖的，因爲在這種情況下，您可以創建一個新節點，爲其分配內容，並且只有一個操作以原子方式執行：更改頂部指針。

如果您對這個論點感興趣，最好的文學作品是Shavit和Herlihy的「多處理器編程藝術」，它描述了許多不同的數據結構，無論是無鎖還是基於鎖的。儘管Maged Michael在his SMR paper，第8頁，第4.2點和我自己完成了a C99 implementation，我現在無法找到任何描述「通常」無鎖棧算法的文章。

Answer 2

你可以使用BlockingQueue使用方法put（）來插入元素和方法drainTo（Collection c）來獲取元素。然後從c的末尾讀取元素。

Answer 3

public class MyConcurrentStack<T> 
{ 
private AtomicReference<Node> head = new AtomicReference<Node>(); 
public MyConcurrentStack() 
{ 

} 

public void push(T t) 
{ 
    Node<T> n = new Node<T>(t); 
    Node<T> current; 

    do 
    { 
     current = head.get(); 
     n.setNext(current); 
    }while(!head.compareAndSet(current, n)); 
} 

public T pop() 
{ 
    Node<T> currentHead = null; 
    Node<T> futureHead = null; 
    do 
    { 
     currentHead = head.get(); 
     if(currentHead == null) 
     { 
      return null; 
     } 
     futureHead = currentHead.next; 
    }while(!head.compareAndSet(currentHead, futureHead)); 

    return currentHead.data; 
} 

public T peek() 
{ 
    Node<T> n = head.get(); 
    if(n==null) 
    { 
     return null; 
    } 
    else 
    { 
     return n.data; 
    } 
} 

private static class Node<T> 
{ 
     private final T data; 
     private Node<T> next; 

     private Node(T data) 
     { 
      this.data = data; 
     } 

     private void setNext(Node next) 
     { 
      this.next = next; 
     } 
} 

public static void main(String[] args) 
{ 
    MyConcurrentStack m = new MyConcurrentStack(); 
    m.push(12); 
    m.push(13); 
    m.push(15); 

    System.out.println(m.pop()); 
    System.out.println(m.pop()); 
    System.out.println(m.pop()); 
    System.out.println(m.pop()); 
} 
} 

該代碼是不言自明的。請讓我知道是否有人需要解釋。 堆棧被形成爲按照以下圖：

...  ...  ... 
| |-->| | -->| | 
    ...  ...  ... 

^
    | 
current head 

Answer 4

import java.util.Random; 
import java.util.concurrent.atomic.AtomicReference; 

public class LockFreeStack { 

public static void main(String... args) { 
    LFStack<String> stack = new LFStack<String>(); 
    for (int i = 0; i < 10; i++) { 
     Thread t = new Thread(new RandomStackUse(stack)); 
     t.setName("My stack thread " + i); 
     t.start(); 
    } 
} 

private static class LFStack<E> { 
    private volatile AtomicReference<Node<E>> head = new AtomicReference<Node<E>>(); 

    public E peek() { 
     E payload = null; 
     Node<E> oldHeadNode = head.get(); 
     if (oldHeadNode != null) { payload = head.get().payload; } 
     return payload; 
    } 

    public E pop() { 
     E payload; 
     while (true) { 
      Node<E> oldHeadNode = head.get(); 
      if (oldHeadNode == null) { return null; } 
      payload = head.get().payload; 
      if (head.compareAndSet(oldHeadNode, oldHeadNode.next.get())) { break; } 
      //System.out.println("Retry"); 
     } 
     return payload; 
    } 

    public void push(E e) { 
     Node<E> oldHeadNode = new Node<E>(e); 

     while (true) { 
      Node<E> oldRootNode = head.get(); 
      if (oldRootNode != null) { oldHeadNode.next.set(oldRootNode); } 
      if (head.compareAndSet(oldRootNode, oldHeadNode)) { break; } 
      //System.out.println("Retry"); 
     } 
    } 
} 


//to be used as LinkedList chain <Node> => <Node> => <Node> => null 
private static class Node<E> { 
    private E payload; 
    private AtomicReference<Node<E>> next; 

    public Node(E e) { 
     payload = e; 
     next = new AtomicReference<Node<E>>(); 
    } 
} 

public static class RandomStackUse implements Runnable { 
    private LFStack<String> stack; 
    private Random rand = new Random(); 

    public RandomStackUse(LFStack<String> stack) {this.stack = stack;} 

    @Override 
    public void run() { 
     long counter = 0; 
     while (true) { 
      if (rand.nextInt() % 3 == 0) { 
       stack.push(String.valueOf(counter++)); 
       //System.out.println(String.format("%s pushed %d", Thread.currentThread().getName(), counter)); 
      } 
      if (rand.nextInt() % 3 == 1) { 
       String value = stack.pop(); 
       //System.out.println(String.format("%s pop %s", Thread.currentThread().getName(), value)); 
      } 
      if (rand.nextInt() % 3 == 2) { 
       String value = stack.peek(); 
       //System.out.println(String.format("%s peek %s", Thread.currentThread().getName(), value)); 
      } 
     } 
    } 
} 
}