java notify() does not release lock in for waiting object in a loop

Question

The problem is: there are two threads, one is a writer to a List another is a reader from the List. Sometimes reader gets stuck if loop in the writer has large amount of iterations. That reader in that case becomes Blocked (not Waiting), which means that it received notification, but writer did not released monitor?

So, why so? What is the best to do with this? (is sleep fine?)

import java.util.LinkedList;
import java.util.List;

public class Main {

    private List<Object> m_calls =  new LinkedList<Object>();

    public void startAll(){

        Thread reader = new Thread(new Runnable() {           
            @Override
            public void run() {
                while(true){
                    synchronized(m_calls){
                        while (m_calls.size() == 0) {
                            try {
                                System.out.println("wait");
                                m_calls.wait();
                            } catch (InterruptedException e) {                               
                                return;
                            }
                        }
                        m_calls.remove(0);
                        System.out.println("remove first");
                    }
                }
            }
        });

        Thread writer = new Thread(new Runnable() {           
            @Override
            public void run() {

                for(int i = 0; i < 15; i++){

                    // UN-comment to have more consistent behavior
                    /*try {
                        Thread.sleep(1);
                    } catch (InterruptedException e) {
                        // TODO Auto-generated catch block
                        e.printStackTrace();
                    }*/
                    synchronized(m_calls){
                        m_calls.add(new Object());
                        m_calls.notifyAll();
                        System.out.println("sent");
                    }
                }
            }
        });

        reader.start();
        writer.start();
    }

    public static void main(String[] args) {     
        new Main().startAll();       
    } 
}

Running of the code above gives different results:

---------------------------------- 1st attempt

wait
sent
sent
sent
sent
sent
sent
sent
sent
sent
sent
sent
sent
sent
sent
sent
remove first
remove first
remove first
remove first
remove first
remove first
remove first
remove first
remove first
remove first
remove first
remove first
remove first
remove first
remove first
wait

---------------------------------- 2nd attempt

wait
sent
sent
sent
sent
sent
sent
remove first
remove first
remove first
remove first
remove first
remove first
wait
sent
sent
remove first
remove first
wait
sent
sent
sent
sent
sent
sent
sent
remove first
remove first
remove first
remove first
remove first
remove first
remove first
wait

------------------------------ Uncommented sleep() - works us expected

wait
sent
remove first
wait
sent
remove first
wait
sent
remove first
wait
sent
remove first
wait
sent
remove first
wait
sent
remove first
wait
sent
remove first
wait
sent
remove first
wait
sent
remove first
wait
sent
remove first wait
sent
remove first
wait
sent
remove first
wait
sent
remove first
wait
sent
remove first
wait
sent
remove first
wait

Edit 1: The reader thread (one of them) seems to be not waiting any more, rather it's blocked, which looks like its monitor received notification (after notifyAll()) but writer thread do not release lock in its loop, what is confusing...

Answer 1

Your particular situation would be better done using a BlockingQueue. Blocking queues will block the take thread (the reader) until something is put in the queue (by a writer).

Here's your modified code using a blocking queue:

public class Main {

    private BlockingQueue<Object> m_calls =  new LinkedBlockingQueue<Object>();

    public void startAll(){

        Thread reader = new Thread(new Runnable() {           
            @Override
            public void run() {
                while(!Thread.currentThread().isInterrupted()) {
                    try {
                        Object obj = m_calls.take();
                        System.out.println("obj taken");
                    } catch(InterruptedException ex) {
                        // Let end
                    }
                }
            }
        });

        Thread writer = new Thread(new Runnable() {           
            @Override
            public void run() {
                try {
                    for(int i = 0; i < 15; i++){
                        m_calls.put(new Object());
                        System.out.println("obj put");
                    }
                } catch (InterruptedException ex) {
                    // Let end
                }
            }
        });

        reader.start();
        writer.start();
    }

    public static void main(String[] args) {     
        new Main().startAll();       
    }
}

The output:

obj put
obj taken
obj put
obj taken
obj put
obj taken
obj put
obj taken
obj put
obj taken
obj put
obj taken
obj put
obj taken
obj put
obj taken
obj put
obj taken
obj put
obj taken
obj put
obj taken
obj put
obj taken
obj put
obj taken
obj put
obj taken
obj put
obj taken

This will be much safer than a) using a plain LinkedList and b) trying to use your own wait/notify. Your wait/notify was also pretty vulnerable to race conditions. If the writer thread called notify before the reader called wait, then the reader could wait indefinitely on the last entry.

I might also add that this solution is safe for multiple reader and writer threads. Multiple threads can put and take all at the same time, and the LinkedBlockingQueue will handle the concurrency for you.

The only thing to be careful about is if Object accesses some shared resource, but this is another problem that's related to concurrent access of a group of objects. (Along the lines of "can I access obj1 and obj2 at the same time from two different threads?") This is another problem entirely, so I won't detail a solution here.

Answer 2

A better way to synchronize in such szenarios is to use java.util.concurrent.* in your case perhaps a CountDownLatch.

Maybe try this first before looking for a reason for the deadlock.

EDIT: And Peter is right. It seems to be running ok?

EDIT 2: OK, whole different story after the additional info. I suggest you work with timeouts to force at least one try in reading even if there is more to write after a certain timespan. wait even has a version with timeout ... http://docs.oracle.com/javase/1.4.2/docs/api/java/lang/Object.html#wait(long)

But again: personally I'd prefer using the concurrancy API.

Answer 3

Its worth nothing that nothing happens immediately and when it comes to threads, you cannot be sure when independent events happen. (Which one of the reasons synchronisation is required)

final long start = System.nanoTime();
new Thread(new Runnable() {
    @Override
    public void run() {
        System.out.printf("Took %,d ns to start this thread%n", System.nanoTime() - start);
    }
}).start();

prints

Took 2,807,336 ns to start this thread

This might not sounds like a long time, but at 3.2 GHz this is almost 9 million clock cycle. A computer can do an awful lot in that time. In your case, a short lived thread can run to completion before the second thread even starts.

In the second case, what you are seeing is that locking is not fair (i.e. fair means the one waiting the longest gets the lock first) The reason for this is it is much slower to implement this properly e.g. 10x slower or more. For this reason, a lock tends to be given the the thread which has it last as this is far more efficient in most cases. You can get fair locks using Lock lock = new ReentrantLock(true); but this is generally not used unless required as it is slower for little gain most of the time.

You can try -XX:-UseBiasedLocking to make locking slightly fairer.

---

To do much the same thing with ExecutorService you can code it like

ExecutorService service = Executors.newSingleThreadExecutor();
// writer
for (int i = 0; i < 15; i++) {
    service.submit(new Runnable() {
        @Override
        public void run() {
            // reader
            System.out.println("remove first");
        }
    });
    System.out.println("sent");
}
service.submit(new Runnable() {
    @Override
    public void run() {
        System.out.println("wait");
    }
});
service.shutdown();

prints

sent
remove first
sent
sent
remove first
sent
remove first
sent
remove first
sent
remove first
sent
remove first
sent
remove first
sent
remove first
sent
remove first
sent
remove first
sent
remove first
sent
remove first
sent
remove first
sent
remove first
remove first
wait