同步循环队列

我正在执行一个非常简单的同步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类很方便。 –

同步循环队列

回答

相关问题