problem with implementing a simple work queue

I am having troubles with implementing a simple work queue. Doing some analysis, I am facing a subtle problem. The work queue is b开发者_运维技巧acked by a regular linked list. The code looks like this (simplified):

0. while (true)  
    1. while (enabled == true)  
        2. acquire lock on the list and get the next action to be executed (blocking operation)  (store it in a local variable)  
        3. execute the action (outside the lock on the list on previous line)
    4. get lock on this work queue  
        5. wait until this work queue has been notified (triggered when setEnabled(true) has been callled)

The setEnabled(e) operation looks like this (simplified):

enabled = e
if (enabled == true)
    acquire lock on this work queue and do notify()

Although this works, there is a condition in which a deadlock occurs. It happens in the following rare situation:

• while an action is being executed during step (3), setEnabled(false) is called
• just before step (4) is entered, setEnabled(true) is called
• now step (5) keeps waiting forever, because this work queue has already been notified but we missed it

How do I solve this? I have been looking at this for some time, but I cannot come up with a solution.

Please note I am fairly new to thread synchronization.

Thanks a lot.

Not sure how the multithreaded memory model is on mobile Java. For Desktop Java I am pretty sure it had some serious bugs all the way up to Java 1.5.

Would be easier to troubleshoot with real Java code over psuedocode.. but I wouldn't be surprised if this was a Java 1.1 bug and not a code bug...

If you think that the problem is a missed notification, then just store another boolean flag, such as "wasNotified". Then at step 5, do a synchronized check of wasNotified. If you were notified, then repeat step 1, otherwise wait for another notification.

You might also look into using a condition variable to implement this (although the Condition class might not be available to you if you are limited to 1.1).

You should make sure that you check and wait for conditions in a loop, otherwise you may cancel the wait prematurely and that can lead to a deadlock later on:

change this:

if ( ! condition )
{
    wait( );
}

to this:

while ( ! condition )
{
    wait( );
}

This comes straight from the documentation for wait.

You are trying to create a worker which can be enabled/disabled which is different from a worker which processes tasks when available. You need to synchronize around the enabled state, not the queue.

while (true)  
    synchronize (enabled)
        while (!enabled)
            enabled.wait();
    task = taskList.take();
    task.run();

You can reduce the synchronization of enabled (if you are willing to accept visibility problems) by first doing an if(!enabled) check prior to the synchronize block. Basically, the broken paradigm known as double check locking.

I believe that the following 2 changes will fix the deadlock bug:

1) change setEnabled as follows:

setEnabled(e){
    acquire lock on Q{
        enabled = e 
        if (enabled == true) 
             do Q.notify() 
    }
}

2) Add condition to step 5:

if enabled=false, wait until this work queue has been notified (Q.wait())

This approach guarantees that the wait of step 5 will occur only if the enabled flag is currently down.