Are wait() and notify() unreliable despite of synchronized?

Question

I recently discovered that using synchronized won't prevent any dead locks.

E.g. within this code:

ArrayList <Job> task;
...

public void do(Job job){
    synchronized(tasks){
        tasks.add(job);
    }
    synchronized(this){
        notify();
    }
}

public void run(){
    while(true){
        for (int = 0;i<tasks.size();i++){
            synchronized(tasks){
                Job job = tasks.get(i);
            }
            //do some job here...
        }
        synchronized(this){
            wait(); //lock will be lost...
            notifier = false; //lock will be acquired again after notify()
        }
    }
}

Now, what is the problem? Well, if the running thread isn't waiting, he won't see any notifications (i.e. notify() calls), therefore he may run into a dead lock and not handle the tasks he received! (Or he may handle them too late...)

Therefore I implemented this code:

private volatile boolean notifier = false;
ArrayList <Job> task;
...

public void do(Job job){
    synchronized(tasks){
        tasks.add(job);
    }
    synchronized(this){
        notifier = true;
        notify();
    }
}

public void run(){
    while(true){
        for (int = 0;i<tasks.size();i++){
            synchronized(tasks){
                Job job = tasks.get(i);
            }
            //do some job here...
        }
        synchronized(this){
            if(!notifier){
                wait(); //lock will be lost...
                notifier = false; //lock will be acquired again after notify()
            }
        }
    }
}

Is this correct or am I missing something? And can it be done easier?

Disendow

Writing thread-safe code is hard. You should use an existing blocking queue (or just executor) instead re-inventing the wheel. – Geranium

I'm inclined to agree. For task lists like this, use an already-implemented threadsafe queue of some kind. Perhaps this one: docs.oracle.com/javase/7/docs/api/java/util/concurrent/… – Christensen

Hmmm, reinventing the wheel would rather be creating a new programming language. So no, I don't reinvent the wheel, also since writing code is rather designing cars than inventing wheels. But I like Ferrari instead of Peugeot, though, and Ferraris are all about speed and simplicity. ;) – Disendow

A BlockingQueue is a more efficient and better pattern @Disendow IMO. You should learn about them at least. – Hypoderma

Allright, I decided to accept your answer (because it's correct after all) and will write some tests to find out case which solution is most efficient. ;) – Disendow

Thanks. I'm not just saying it to get points Marcus. :-) – Hypoderma

Answer 1

Now, what is the problem? Well, if the running thread isn't waiting, he won't see any notifications (i.e. notify() calls), therefore he may run into a dead lock and not handle the tasks he received!

Right. This is not a case of being "unreliable" but rather a case of language definition. The notify() call does not queue up notifications. If no threads are waiting then the notify() will effectively do nothing.

can it be done easier?

Yes. I'd look into using BlockingQueue -- a LinkedBlockingQueue should work well for you. One thread call pull from the queue and the other can add to it. It will take care of the locking and signaling for you. You should be be able to remove a large portion of your hand written code once you start using it.

Hypoderma

+1 for recognizing this is a producer/consumer problem. – Amatol

Answer 2

I was tricked by your question at first. Your synchronize(this) on thread object don't make sense. I in the past also do this stuff to make wait() not throwing compilation error.

Only synchronize(tasks) make sense as you are waiting and want to acquire this resources.

Having a for loop, it is bad design. In the consumer-producer problem. get a job at the same time remove a job. better fetch a job once at a time.

public void do(Job job){
    synchronized(tasks){
        tasks.add(job);
        notify();
    }
}

public void run(){
    Job job;
    while(true){

        //This loop will fetch the task or wait for task notification and fetch again.
        while (true){
            synchronized(tasks){
                if(tasks.size()>0){
                    job = tasks.getTask(0);
                    break;
                }
                else
                    wait();

            }
        }

        //do some job here...

    }
}

Kaifeng

I'm sorry if you do not like this comment, but a wait(100) more seems like hotfixing code rather than providing an actual answer. – Anaemia

he can use semaphores or monitors for this problem too. 1 step at a time. Understand how to use wait and notify and its disadvantage and hence he will look for other better solution – Kaifeng

Can you carefully explain why it should be 100 in wait(100) then? – Anaemia

Agreed, it should be wait(0) for non-blocking thread, or something like wait(5) or so...but funny solution, a while-loop in a while-loop. ;) – Disendow

Revised. it should be what the way to call wait and notify – Kaifeng

Just to be clear: It must have been wait(1) or more, since wait(0) wouldn't do the job... – Disendow

Answer 3

The result actually isn't a dead lock, but rather a starvation of the task/job itself. Because no threads are "locked", the task just won't be done until another thread calls do(Job job).

Your code is almost correct - beside the missing exception handling when calling wait() and notify(). But you may put the task.size() within a synchronisation block, and you may block the tasks during the hole process because a deletion of a job within tasks by another thread would let the loop to fail:

...
while(true){
    synchronized(tasks){
        for (int = 0;i<tasks.size();i++){ //could be done without synchronisation
           Job job = tasks.get(i);        //if noone deletes any tasks
        }
        //do some job here...
    }
    ...

Just note that your code is blocking. Non-blocking might be faster and look like this:

ArrayList <Job> tasks;
...

public void do(Job job){
    synchronized(tasks){
        tasks.add(job);
    }
}

public void run(){
    while(true){
        int length;
        synchronized(tasks){
            length = tasks.size();
        }
        for (int = 0;i<length;i++){
            Job job = tasks.get(i); //can be done without synchronisation if noone deletes any tasks...otherwise it must be within a synchronized block
            //do some job here...
        }
        wait(1); //wait is necessary and time can be set higher but never 0!
    }
}

What can we learn? Well, within non-blocking threads no notify(), wait() and synchronized are needed. And setting wait(1) doesn't even use more CPU when idle (don't set wait(0) because this would be treated as wait().

However, be careful because using wait(1) may be slower than using wait() and notify(): Is wait(1) in a non-blocking while(true)-loop more efficient than using wait() and notify()? (In other words: Non-blocking might be slower than blocking!)

Disendow

One of the best tutorial about synchronisation can be found here: javamex.com/tutorials/… – Disendow