conditional variables

Joseph W. Seigh

unread,

Apr 29, 1997, 3:00:00 AM4/29/97

to

The class

//<plaintext>
// Copyright 1997 by Joseph W. Seigh

public class CondVar {
Object z;

public CondVar(Object z) {
this.z = z;
}

public void condWait() throws InterruptedException {

int n = 0; // monitor count

Monitor.monitorenter(this);
try {
Monitor.monitorexit(z); // must be held at least once
try {
for(n = 1;; n++)
Monitor.monitorexit(z);
}
catch (IllegalMonitorStateException e) {}
wait();
}
finally {
Monitor.monitorexit(this);
for(; n > 0; n--)
Monitor.monitorenter(z);
}
}

public void condWait(long timeout) throws InterruptedException {

int n = 0; // monitor count

Monitor.monitorenter(this);
try {
Monitor.monitorexit(z); // must be held at least once
try {
for(n = 1;; n++)
Monitor.monitorexit(z);
}
catch (IllegalMonitorStateException e) {}
wait(timeout);
}
finally {
Monitor.monitorexit(this);
for(; n > 0; n--)
Monitor.monitorenter(z);
}
}

public void condWait(long timeout, int nanos) throws
InterruptedException {

int n = 0; // monitor count

Monitor.monitorenter(this);
try {
Monitor.monitorexit(z); // must be held at least once
try {
for(n = 1;; n++)
Monitor.monitorexit(z);
}
catch (IllegalMonitorStateException e) {}
wait(timeout, nanos);
}
finally {
Monitor.monitorexit(this);
for(; n > 0; n--)
Monitor.monitorenter(z);
}
}

public synchronized void condNotify() {
notify();
}

public synchronized void condNotifyAll() {
notifyAll();
}

} // end CondVar

The Monitor class, you'll need a java assembler to do this
one, This is the javap -c output

public class Monitor extends java.lang.Object {
public static void monitorenter(java.lang.Object);
public static void monitorexit(java.lang.Object);
public Monitor();

Method void monitorenter(java.lang.Object)
0 aload_0
1 monitorenter
2 return

Method void monitorexit(java.lang.Object)
0 aload_0
1 monitorexit
2 return

Method Monitor()
0 aload_0
1 invokenonvirtual #11 <Method java.lang.Object.<init>()V>
4 return

}

A test application to show its usage.

import java.awt.*;
import java.applet.*;

public class procon2 extends Applet implements Runnable{

int free_head; // head of free buffer queue
int free_tail; // tail of free buffer queue
int full_head; // head of full buffer queue
int full_tail; // tail of full buffer queue

int queue[] = new int[6];

Object mutex;
CondVar free; // free queue conditional variable
CondVar full; // full queue conditional variable

Thread producer1;
Thread producer2;
Thread consumer;

public static void main(String argc[]) {
new procon2().start();
}

public void start() {

mutex = new Object();

free_head = 0;
free_tail = queue.length - 1;
full_head = 0;
full_tail = 0;

free = new CondVar(mutex);
full = new CondVar(mutex);

producer1 = new Thread(this);
producer2 = new Thread(this);
consumer = new Thread(this);

producer1.start();
producer2.start();
consumer.start();

try {producer1.join();} catch(InterruptedException e) {};
try {producer2.join();} catch(InterruptedException e) {};
try {consumer.join();} catch(InterruptedException e) {};

System.out.println("app completed");

}

public void stop() {
producer1.stop();
producer2.stop();
consumer.stop();
}

public void run() {
if (Thread.currentThread() == producer1)
run_producer(1);
else if (Thread.currentThread() == producer2)
run_producer(2);
else
run_consumer();
}

public void run_producer(int t) {
int z;
int i;
for(i = 0; i<10; i++) {
synchronized(mutex) {
while(free_head == free_tail)
try {free.condWait(); }
catch (InterruptedException e) {}
z = queue[free_head];
free_head = (free_head+1)%queue.length;
}

z = 100*t + i;
System.out.println("producer "+i+" "+z);
Thread.yield();

synchronized(mutex) {
queue[full_tail] = z;
full_tail = (full_tail+1)%queue.length;
full.condNotify();
}
}
}

public void run_consumer() {
int z;
int i;
for(i = 0; i<20; i++) {
synchronized(mutex) {
while(full_head == full_tail)
try {full.condWait(); }
catch (InterruptedException e) {}
z = queue[full_head];
full_head = (full_head+1)%queue.length;
}

System.out.println("consumer "+i+" "+z);
Thread.yield();

synchronized(mutex) {
queue[free_tail] = 0;
free_tail = (free_tail+1)%queue.length;
free.condNotify();
}
}
}

}

Joe Seigh

Mark Tillotson

unread,

Apr 30, 1997, 3:00:00 AM4/30/97

to

"Joseph W. Seigh" <se...@ultranet.com> wrote:
> Subject: conditional variables

Very minor point of nomenclature:

You are implementing "condition variables", not "conditional variables"

Slightly more major point:

I am fairly convinced that your code isn't correct, in that condNotify()s
on a condVar can be lost in the gap between the releasing of the
object's monitor and the wait() on the condVar - this would typically
manifest itself as deadlock between mutually dependent threads:

> public void condWait() throws InterruptedException {
>
> int n = 0; // monitor count
>
> Monitor.monitorenter(this);
> try {
> Monitor.monitorexit(z); // must be held at least once
> try {
> for(n = 1;; n++)
> Monitor.monitorexit(z);

From [here]

> }
> catch (IllegalMonitorStateException e) {}

to [here] another thread can get the monitor, do a condNotify() on this CV,
and it will be discarded (nothing is waiting). If the thread in
question was doing this in response to something this thread did
whilst holding this monitor (for instance perhaps this thread created
the other thread), then this lose of the notify() might be crucial.

> wait();

and after this we then deadlock, since here we wait() for a notify() that
has already been dropped on the floor.

> }
> finally {
> Monitor.monitorexit(this);
> for(; n > 0; n--)
> Monitor.monitorenter(z);
> }
> }

__Mark
[ ma...@harlequin.co.uk | http://www.harlequin.co.uk/ | +44(0)1954 785433 ]

Joe Seigh

unread,

Apr 30, 1997, 3:00:00 AM4/30/97

to

|> > public void condWait() throws InterruptedException {
|> >
|> > int n = 0; // monitor count
|> >
|> > Monitor.monitorenter(this);
|> > try {
|> > Monitor.monitorexit(z); // must be held at least once
|> > try {
|> > for(n = 1;; n++)
|> > Monitor.monitorexit(z);
|>

|> From [here]
|>
|> > }
|> > catch (IllegalMonitorStateException e) {}
|>
|> to [here] another thread can get the monitor, do a condNotify() on this CV,
|> and it will be discarded (nothing is waiting). If the thread in
|> question was doing this in response to something this thread did
|> whilst holding this monitor (for instance perhaps this thread created
|> the other thread), then this lose of the notify() might be crucial.
|>
|> > wait();
|>
|> and after this we then deadlock, since here we wait() for a notify() that
|> has already been dropped on the floor.
|>
|> > }

|> > finally {
|> > Monitor.monitorexit(this);
|> > for(; n > 0; n--)
|> > Monitor.monitorenter(z);
|> > }
|> > }

Typically, the way you would use condNotify would be to
acquire the monitor lock for the object beforehand although
I don't enforce it. Since the thread doing the conditional
wait acquires the CondVar object lock before releasing
the object lock, there's no way the notify could have
been done before that point if the notify thread had
tried to get the object lock first. Then it has
to get the CondVar object lock. That means it must
have both locks before doing the notify. And the
waiting thread always has a least one of those locks
at all times before doing the wait.

The reason for not enforcing the object lock to be
held in order to do the condNotify is that it is not
needed. Releasing the object lock and then doing
the condNotify is just as good as doing the condNotify
within the synchronized block. Moreover, there are
semi distributed algorithms where the thread doing
the notify doesn't need to use synchronized blocks
and getting a monitor lock just to do a notify is
unnecessary overhead.

Joe Seigh

Mark Tillotson

unread,

May 1, 1997, 3:00:00 AM5/1/97

to

I wrote:
|> Slightly more major point:
|>
|> I am fairly convinced that your code isn't correct, in that condNotify()s
|> on a condVar can be lost in the gap between the releasing of the
|> object's monitor and the wait() on the condVar - this would typically
|> manifest itself as deadlock between mutually dependent threads:

I was wrong - however I still have reservations about this
implementation.

se...@bose.com (Joe Seigh) replied:

> Typically, the way you would use condNotify would be to
> acquire the monitor lock for the object beforehand although
> I don't enforce it. Since the thread doing the conditional
> wait acquires the CondVar object lock before releasing
> the object lock, there's no way the notify could have
> been done before that point if the notify thread had
> tried to get the object lock first. Then it has

I think I got confused between the two monitors! You still don't
guarantee the condition is true to the thread returning from
condWait() - it will need to check that no other random thread
clobbered the aspect of the object's state that is supposed to be
encoded by the condition variable, and this check needs to be done
within the objects' monitor. If the check fails, you need to loop and
call condWait() again.

However this is probably not too burdensome, and most of the time
threads will be woken up at the right times.

> to get the CondVar object lock. That means it must
> have both locks before doing the notify. And the
> waiting thread always has a least one of those locks
> at all times before doing the wait.

> The reason for not enforcing the object lock to be
> held in order to do the condNotify is that it is not
> needed. Releasing the object lock and then doing
> the condNotify is just as good as doing the condNotify
> within the synchronized block. Moreover, there are

It is just as good because there is never was a guarantee that a notify is
in step with the object state.

> semi distributed algorithms where the thread doing
> the notify doesn't need to use synchronized blocks
> and getting a monitor lock just to do a notify is
> unnecessary overhead.

Indeed, but you do need to get the condVar lock before you can
notify(), to avoid dropping a vital notify on the floor. This
could lead to deadlock if the condWait() thread is of lower priority
than the condNotify() one, and the condNotify() has urgent other
work to do next.

Without assuming an implementation of monitorenter using
_priority-inheritance_ your implementation is rather "weak" (not that
you can do any better on the JVM spec!)
Proper condition-variable synchronization shouldn't risk stalling the
notifying thread at all if it is higher priority - this is a classic
deadlock situation. A partial solution is provided if the threads are
time-sliced, but this typically clobbers the performance of the
high-prioroty thread - almost as bad as deadlock for demanding
applications.

Joe Seigh

unread,

May 5, 1997, 3:00:00 AM5/5/97

to

In article <kxd8rb5...@zaphod.harlqn.co.uk>, ma...@harlequin.co.uk (Mark Tillotson) writes:

more stuff than inews will let me quote.

With regard to the point that the condition that was true when the
condNotify was executed may not be true when the waiting thread resumes
execution and regains the monitor lock. This is true of wait/notify also.
Hence the strong recommendations from JavaSoft to used loops there also.

As to lock contention between the waiting and notifying threads, again,
this is true of regular wait/notify also. Additionally the critical
regions used by the extra lock are short and fixed in size which does
limit the possible contention. The contention is more likely to occur
on the "outer" lock.

It would have been nice to not to have used the extra lock at all, but
JavaSoft has chosen not to provide efficient low level synchronization
primatives, so you have to work with what you have.

It could have been a lot worse, as I've said before, they could have
made semaphores the official Java synchronization mechanism.

To clarify my position on this implemtation of condition variables.
I'm not promoting CondVar as the ultimate solution. I'm just
posting it as an interm solution if anyone feels that they absolutely
cannot get along without it. If they want the official solution
they can wait for JavaSoft to put it in. Or they can not use it
at all. I haven't found any situations that couldn't be solved
cleanly without condition variables yet myself.

Joe Seigh