實現雙鎖併發隊列

我試圖在Java中實現一個雙鎖併發隊列，但是我無法讓它通過自動化測試。請讓我知道在我的代碼中的錯誤：實現雙鎖併發隊列

private static class Link<L> { 
    L val; 
    Link<L> next; 
    Link(L val) { this.val = val; this.next = null; } 
} 
T v; 
private Link<T> initNode = new Link<T> (v); 
private Link<T> first = initNode; 
private Link<T> last = initNode; 

public void enque(T val) { 
    Link<T> newLink = new Link<T> (val); 
    synchronized (this.last) { 
     last.next = newLink; 
     last = newLink; 
    } 
} 

public T deque() { 
    synchronized (this.first) { 
     Link<T> new_head = first.next; 
     if (new_head == null) 
      return null; 
     T rtnVal = new_head.val; 
     first = new_head; 
     return rtnVal; 
    } 
}

來源

2010-11-16 segfault

這功課嗎？ – 2010-11-16 21:00:42

如果我沒有用任意節點初始化隊列，我會在synchronized（）部分獲得NullPointerException。 – segfault 2010-11-16 21:03:08

@Mike：是的，但所有的代碼都是我自己編寫的。 – segfault 2010-11-16 21:03:51

這裏最大的問題是，你正在改變該對象被上保持同步。最終發生的事實是不確定的。

在你synchronized塊你有：

synchronized (this.last) { 
    last.next = newLink; 
    last = newLink; 
}

自去年被改變，另一個線程可以進入enque方法，並在同一時間進入synchronized塊。最好的辦法是有兩個對象，以阻止在：

private final Object ENQUEUE_LOCK = new Object(); 
private final Object DEQUEUE_LOCK = new Object();

我不知道這是必然爲什麼你的測試失敗，但它會解決的併發性問題。

編輯：事實證明，對我和我的測試，至少有兩個專用的鎖確實可以解決我在隊列中看到的奇怪問題。

來源

2010-11-16 21:46:51

我不相信這會有幫助，考慮到情況，列表是空的，首先/最後是newLink，現在兩個線程在同一時間，一個獲得ENQUEUE_LOCK，另一個DEQUEUE_LOCK，兩者都將着手修改newLink和接下來會發生什麼是未定義的... – Nim 2010-11-16 21:54:12

我站在更正，顯然它確實與兩個鎖一起工作，這似乎是算法：http://www.cs.rochester.edu/research/synchronization/pseudocode/queues。 HTML – Nim 2010-11-16 23:05:18

實現雙鎖併發隊列

回答

相關問題