Are wait() and notify() unreliable despite of sync

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?

Answer 1

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!)

Answer 2

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.

Answer 3

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...

    }
}