同步循環隊列

我正在執行一個非常簡單的同步Circular Queue，因爲它的後面，我的一個朋友說，它很容易deadlock！但我不這麼認爲，同步循環隊列

實際上，當一個線程想要出隊（輪詢）如果隊列是空的，它必須等到另一個線程入隊（提供）一個元素，反之亦然，如果隊列已滿，

我不是很擅長尋找死鎖代碼，你認爲它也容易出現死鎖嗎？

import java.util.ArrayList; 

class CircularQueue<T>{ 
    ArrayList<T> q; 
    int front , rear , size; 
    public CircularQueue(int size){ 
     q = new ArrayList<T>(); 
     for (int i = 0 ; i < size ; i++) 
      q.add(null); 
     front = 0; 
     rear =0; 
     this.size = size; 
    } 
    public void offer(T t) throws InterruptedException{ 
     synchronized(this){ 
      if ((rear + 1) % size == front) 
       this.wait();  
     } 
     rear = (rear + 1) % size; 
     q.set(rear, t); 
     this.notify(); 
    } 
    public T poll() throws InterruptedException{ 
     synchronized(this){ 
      if (rear == front) 
       this.wait(); 
     } 
     front = (front+1) % size; 
     T result = q.get(front); 
     this.notify(); 
     return result; 
    } 
}

來源

2013-06-21 Arian Hosseinzadeh

'this.notify（）'總會拋出'IllegalMonitorStateException'，因爲它是不同步的 –

也許我失去了一些東西，但是這不就是完全一樣的[界的BlockingQueue（HTTP：//文檔。 oracle.com/javase/6/docs/api/java/util/concurrent/ArrayBlockingQueue.html）？您的實現不同步導致意外行爲。例如，兩個線程可能會同時更改'poll（）'方法中的'front'。 – nif

@Adam Siemion：這是因爲可能沒有線程在等待？ –

有幾個問題與您的實現：

的notify()調用必須來自塊
你實現創建「卻還」內 - 一種Java內存泄漏，防止對象時從收集時間超過他們應該。要解決此問題，請將您從poll()返回的元素設置爲null。
您不需要使用ArrayList<T>並填入null s;一個普通的Object陣列就足夠了。您需要添加投射，但無論如何，無論有沒有ArrayList，您都可以將其移入代碼中。
You should not synchronize on this。

最後一點允許您的隊列的惡意用戶通過在隊列對象本身上進行同步並且不釋放鎖定來永久停止進度。

來源

2013-06-21 16:37:00 dasblinkenlight

不同意在'this'上同步：在像這樣的低級實用程序中，我不認爲這是個問題。雖然這個類的用戶應該總是私下實例化，以便沒有其他人可以鎖定它。 –

關於你的第三個音符，但是不可能實例化一個通用數組！是嗎？ –

@ArianHosseinzadeh：只要創建擦除類型，在這種情況下是對象的陣列。它會因陣列協方差而起作用，但你會得到一個警告，你將不得不壓制。 –

您需要同步整個方法，而不僅僅是wait（）調用。

想象一下，如果兩個線程同時嘗試提供（），並且還有兩個時隙，那麼會發生什麼情況。他們都可以通過同步塊，然後在下一行讀取不同的值。然後下一次調用poll（）會阻塞，但該值已經在那裏。

此代碼還有其他一些問題：您不處理虛假喚醒，並且在不保持監視器的情況下調用notify（）方法。此外，我會在這裏使用Object []而不是ArrayList，因爲固定大小的可變集合正是您想要的。

來源

2013-06-21 16:35:55

那麼你的意思是我必須使兩種方法（投票和報價）同步？那麼我需要等待什麼？因爲正如我所說，我想等到有人將某些東西排入隊列中（在出隊的情況下） –

在檢查條件時，您需要等待（）以循環中的超時。您不一定希望整個方法同步，但您需要同步讀取 - 修改 - 寫入操作，因此您不必競爭另一個線程。爲此，您可能會發現AtomicInteger類很方便。 –

同步循環隊列

回答

相關問題