Java's scheduling of objects waiting on a monitor

This document is a continuation of the monitor.htm document.

Peter Welch's reply (16Feb98)

In his posting on the synchronising/waiting behaviour of Java threads, Oyvind wrote:

However, I have some comments. Per Brinch Hansen writes:
Does this describe Java's waiting on a monitor: one queue for the object's monitor, and one ready-queue of threads to run? I imagine that the situation Brinch Hansen describes is notifyAll, since all are moved off Qe (please correct me here). Where lies the Java problem? Is it in the monitor queue administration (queue, stack, combination?) or is it when the monitor queue is transferred to the ready-queue (linear or swap or combination)?

Qv is the queue for the object's monitor (the object, in this case, being the shared variable `v'). Qe is the queue of threads that have previously acquired the monitor, been unable to proceed (because some necessary condition' is not right for it) and have been forced to wait for the `event' (the fixing of the `condition' by some other thread).

But there is a key item of undefinedness in the quotation from Brinch Hansen.

When he says: "all processes in the event queue, Qe, are transferred to the main queue" ... how are they attached to that main queue? I don't know if he clarifies that later???

After a `notifyAll', Sun's JVMs currently attach them to the *back* of that main queue -- which is the logical thing to do when adding things to a queue. But it leads to infinite starvation and is plain `unfair'(since those threads have already been through that main queue once!)

A fair thing would be for the notified threads queue, Qe, to barge into the *front* of the main queue, Qv. That still doesn't guarantee against infinite starvation though ... unless we abandon the `notifyAll' and only do single `notify' calls each time the producer (in Brinch Hansen's terminology) sets up the condition for which a thread is waiting. Or unless we fix things, as we do in the implementation of JavaPP channels, so that there can never be more than *one* thread in the waiting queue, Qe.

Hoare, in his seminal paper states that:
Isn't this postulate a requirement?

Yes! And Java monitors do *not* fulfil it. Most of Hoare's examples in that paper do not work if that requirement is not honoured. Java monitors are significantly different from Hoare monitors in this (and several other) respects.

When working with raw Java monitors, we cannot look to algorithmic guidelines /tricks/theory that were developed for those of Hoare. New ones have to be found. The literature (e.g. Gosling's "Java Programming Language" and Doug Lea's "Concurrent Programming in Java") comes up with the following:

  1. Never guard a `wait' with a simple `if' on the wait-condition. Just because you are notified by someone who set up the condition for you, doesn't mean it's still there when you wake up! Always `wait' within a while-loop that tests the wait-condition -- it must be re-tested whenever you wake up in case it's gone wrong again.
  2. Don't bother with calling `notify' -- we might as well always call `notifyAll'. Given rule 1 above, this is always perfectly safe.

The literature is right, given Java's monitor semantics. Rule 1 *has* to be followed and rule 2 is a consequence. However, while these rules guarantee that the monitor call will never proceed with an incorrect state in the monitor, it doesn't actually guarantee that any individual monitor call will *ever* proceed (i.e. get out of the rule 1 while-loop) no matter how often it's notified to do so ... as the "wot, no chickens?" example shows.

JavaPP channels are implemented with a different design pattern to the above. The `wait' *is* guarded by a simple if-test and we only ever `notify'. This is perfectly safe since we can guarantee that there will only ever be *one* waiting thread. So, there is *no* danger of the livelocking starvation striking JavaPP channels. But there remains a danger of passive starvation if the JVM *stacks* those initial synchronisations -- i.e. we don't have a main queue, Qv, we have a main stack, Sv!!! So, don't use JVMs that use stacks if you are working in a real-time environment -- unless you have lots of idle time guaranteed.

Using JavaPP channels with a queueing (or `weakly' queuing) JVM, we are safe from both passive and livelocking starvation. The user never has to worry about any design rules for monitors. The user *does* have to worry about deadlock though -- but that's another story and one for which we have a decent answer (thanks to 20 years work on CSP and occam).

Peter Welch.

Per Brinch Hansen's statements (17Feb98)

This tries to answer Peter's question and poses some new questions.

I think the answer is both in the figure only figure and in the text. All indented blockquotes are from [Per Brinch Hansen, Structured Multiprogramming, Comm.of ACM, July 1972, p.576-577]

Fig. 1. Scheduling of conditional critical regions V by means of process queues Qv and Qe.

After the quote in monitor, Brinch Hansen states:

It is possible that a consumer will be transferred in vain between Qv and Qe several times before its condition B holds. But this can only occur as frequently as producers change the desired variable. This controlled amount of busy waiting is the price we pay for the conceptual simplicity achieved by using arbitrary Boolean expressions as synchronizing conditions.

First, doesn't the arrowheads in the figure define a proper queue? I think so. But the two arrows going into Qv doesn't specify which should be ahead of the other. He gives a solution later in the document:

.. To simplify explicit scheduling, I suggest that processes reentering their critical regions from event queues take priority over processes entering critical regions directly through a main queue (see Figure 1).

This is exactly what Peter states would be a fair thing for Java!

Second, is the quote above the same thing as Peter cites Doug Lea for? ("Always `wait' within a while-loop that tests the wait-condition -- it must be re-tested"). Does this mean that Brinch Hansen's monitor is closer to Java's than Hoare's?

I'm afraid I don't understand all that Brinch Hansen says, so I may just introduce noise. But Brinch Hansen continues:

.. The conceptual simplicity of critical regions is achieved by ignoring details of scheduling: the programmer is unaware of the sequence in which waiting processes enter critical regions and access shared resources. This assumption is justified for processes which are so loosely connected that simultaneous requests for the same resource rarely occur.

I don't understand why he has to justify this. What happens if there are simultaneous requests? Does it matter? Is he thinking of starvation etc.?

More: (this is a footnote that refers to Wirth, The Programming Language Pascal, Acta Informatica 1, 1(1971)35-63):

.. The original solution includes the following refinement: when a writer decides to make a request at most one reader can complete a request ahead of it. This can be ensured by surrounding the reader request in Algorithm 2 with an additional critical region associated with a shared Boolean r.

Maybe this is so far back in history that I've lost contact completely and gone adrift -- anyway: "at most one" and Peter's "will only ever be *one* waiting thread" do look familiar. Are you really talking about the same thing?

Another question, how does JavaPP ensure "that there can never be more than *one* thread in the waiting queue, Qe"? I find two nested synchronized statements in the code, and inside is the wait that places the object on the queue -- or is it the first - or second synchronized that does the trick? (Example from Gerald H. Hilderink's code): 

boolean read(ClonableProtocol object)
throws Exception
{
  boolean result = false;
  synchronized (reader_monitor)
  {
    synchronized (this)
    {
      while(linkdriver.state == LinkDriver.EMPTY) 
      {
        waitingreaders++;    
        wait();
        waitingreaders--;    
      }
      result = linkdriver.read(object);
      notify();
    }
    return result;
  }
}

Last question: the dropping of notifyAll: could n notify's substitute a notifyAll? Perhaps not, because there would be schedulings in between?

Øyvind Teig