Synchronized Circular Queue

Question

I am implementing a very simple synchronized Circular Queue as it follows , a friend of mine says that it's prone to deadlock ! but I don't believe so ,

actually when a thread wants to dequeue (poll) if the queue is empty it has to wait until another thread enqueue (offer) an element and vice versa if the queue is full ,

I am not very good at finding deadlock-prone codes, do you think that it's prone to deadlock too ?

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;
     }
}

`this.notify()` will always throw `IllegalMonitorStateException` because it is not synchronized — Adam Siemion, Jun 21 '13 at 16:31
Maybe I'm missing something, but isn't this quite the same as a [bounded BlockingQueue](http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/ArrayBlockingQueue.html)? Your implementation is under-synchronized leading to unintended behaviour. For example, two threads may concurrently change `front` in the `poll()` method. — nif, Jun 21 '13 at 16:36
@Adam Siemion : Is this because it's possible that no thread is waiting ? — Arian, Jun 21 '13 at 16:36

score 1 · Accepted Answer · edited May 23 '17 at 12:29

1

There are several issues with your implementation:

The call of notify() must come from inside a synchronized block
Your implementation creates "lingerers" - a kind of Java memory leak, when objects are prevented from being collected for longer than they should be. To fix this, set the element that you return from poll() to null.
You do not need to use ArrayList<T> and fill it with nulls; a plain array of Object would be sufficient. You would need to add casting, but it's going to be there anyway, with or without ArrayList, so you might as well move it into your code.
You should not synchronize on this.

This last point allows malicious users of your queue permanently stall the progress by synchronizing on the queue object itself, and not releasing a lock.

edited May 23 '17 at 12:29

Community

1
1

answered Jun 21 '13 at 16:37

Sergey Kalinichenko

714,442
84
1,110
1,523

Disagree about synchronizing on `this`: in a low-level utility like this one I don't think it's a problem. A user of this class should always instantiate it privately so that no one else can get a lock on it, though. – Daniel Pryden Jun 21 '13 at 16:39
regarding your third note , but it's not possible to instantiate a generic array ! is it ? – Arian Jun 21 '13 at 16:40
@ArianHosseinzadeh: just create an array of the erased type, which in this case is Object. It will work due to array covariance, but you'll get a warning you'll have to suppress. – Daniel Pryden Jun 21 '13 at 16:41
So you mean something like this : T[] q = (T[])new Object[size]; – Arian Jun 21 '13 at 16:43
@DanielPryden It's better be safe than sorry: an extra `Object myLock = new Object()` is a small price to pay for making some of your implementation details inaccessible to outsiders. – Sergey Kalinichenko Jun 21 '13 at 16:43
2

@ArianHosseinzadeh Or even `Object[] q = new Object[size]()` and `T result = (T)q[front];` – Sergey Kalinichenko Jun 21 '13 at 16:44
1

@ArianHosseinzadeh: Yes. You'll need a `@SuppressWarnings("unchecked")` as well, to tell the compiler you know what you're doing. Or, as dasblinkenlight says, just cast at the point of access. – Daniel Pryden Jun 21 '13 at 16:44
@dasblinkenlight: conversely, though, synchronizing on `this` allows other classes to perform multiple operations on objects of this class in a thread-safe way. This is why many of the Java standard library classes synchronize on `this`. So I don't think it's strictly wrong, although I agree that it's better to be safe than sorry. – Daniel Pryden Jun 21 '13 at 16:48

score 0 · Answer 2 · answered Jun 21 '13 at 16:35

0

You need to synchronize your entire methods, not just the wait() calls.

Imagine what would happen if two threads both tried to offer() at the same time, when there are two slots left. They could both pass the synchronized block and then read different values for rear on the next line. Then the next call to poll() would block but the value would already be there.

There are a few other issues with this code as well: you don't handle spurious wakeups and you call notify() outside without holding the monitor. Also, I would use an Object[] instead of an ArrayList here, since a fixed-size mutable collection is exactly what you want.

answered Jun 21 '13 at 16:35

Daniel Pryden

59,486
16
97
135

So do you mean that I have to make both of the methods (poll & offer) as synchronized ? what do I have to wait on then ? because as I said I want to wait until someone enqueues something into the queue (in case of dequeuing) – Arian Jun 21 '13 at 16:45
You need to wait() with a timeout in a loop, while checking the condition. You don't necessarily want the whole method synchronized, but you need to synchronize the read-modify-write operation so you don't have to race another thread. You may find the AtomicInteger class handy for this purpose. – Daniel Pryden Jun 21 '13 at 16:54

Synchronized Circular Queue

2 Answers2