3

我正在实现一个非常简单的同步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;
     }
}
4

2 回答 2

1

您的实施存在几个问题：

  • 的调用notify()必须来自synchronized块内部
  • 您的实现会创建“滞留者”——一种 Java 内存泄漏，当对象被阻止收集的时间超过应有的时间时。要解决此问题，请将您返回的元素设置poll()为null。
  • 您不需要使用ArrayList<T>并用 s 填充它null；一个简单的数组Object就足够了。您需要添加强制转换，但无论如何它都会存在，无论有没有ArrayList，所以您不妨将它移到您的代码中。
  • 您不应该在this.

最后一点允许队列的恶意用户通过在队列对象本身上同步而不释放锁来永久停止进度。

于 2013-06-21T16:37:00.090 回答
0

您需要同步整个方法，而不仅仅是 wait() 调用。

想象一下，如果两个线程同时尝试提供（），当剩下两个插槽时会发生什么。他们都可以通过同步块，然后在下一行读取不同的值。然后对 poll() 的下一次调用将阻塞，但该值已经存在。

此代码还有一些其他问题：您不处理虚假唤醒，并且您在没有持有监视器的情况下在外面调用 notify()。另外，我会在这里使用 Object[] 而不是 ArrayList，因为固定大小的可变集合正是您想要的。

于 2013-06-21T16:35:55.567 回答