monitor

Java's scheduling of objects waiting on a `monitor`

Ø.Teig, 4.Feb.1998

This paper in an extract of communication between P.H.Welch (phw@ukc.ac.uk) and Øyvind Teig (oyvind.teig@autronica.no).

It is an html-file partly because the norwegian character set clashes with english curly brackets. This will make the document whole, so to speak.

We have run two Java programs on different platforms: College.java and Take_Res.java.

The new College.java is based on Peter's original College.java, and has nothing more than make-up to it: it summarizes in a table how many chickens each philosopher eats. This table is printed to screen when you run the program.

Take_Res.java has been written after Peter's specifications in a comment in original College. Again make-up by Øyvind: an implementation of Take_Res after Peter's spec.

I have done some measurements on PCs. Peter has also done some measurements, they are scattered around.

The interesting thing is Peter's conclusion below.

However, I have some comments. Per Brinch Hansen writes:

All processes waiting for one condition or another on variable v enter the same event queue.When another process (here called the producer) changes v by a statement S2 inside a critical region, it is possible that one or more of the conditions expected by processes in the event queue will be satisfied. So, after completion of a critical region, all processes in the event queue Qe are transferred to the main queue Qv to enable them to reenter their critical regions and inspect the shared variable v again. [Structured Multiprogramming, Comm.of ACM, July 1972, p.576]

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

Hoare, in his seminal paper states that:

"If more than one program is waiting on a condition, we postulate that the signal operation will reactivate the longest waiting program. This gives a simple neutral queuing discipline which ensures that every program will eventually get its turn". [Monitors: An Operating System Structuring Concept, Comm.of ACM, 549-557, 1974]

Isn't this postulate a requirement?

Peters's conclusion

{{{  Peters's conclusion
Oyvind,

Wow!  You've been working hard!!

Your results seem to be as predicted ... and the conclusions remain that:

  1. Starvation is hard (impossible?) to eliminate if you synchronise
     via a stack -- even worse if you wait via a stack as well.  Shared
     JavaPP channels cannot be defended against starvation in this case.

     The Kaffe Virtual Machine (on Linux and SunOS) uses such stacks.

  2. Starvation *can* be eliminated if you synchronise and wait via a queue.
     The normal programming pattern for monitors (waiting in a loop that
     always retests the wait condition) does not guarantee against
     starvation and brings in livelock danger as well.  JavaPP channels
     (including shared ones) do not introduce starvation or livelock
     (although, of course, they could be introduced at the application
     level).

     Sun's and the Symantic Java Virtual Machines (on '95 and SunOS/Solaris)
     use queues.

Do you have any time to forward our emails on this to java-threads?

Cheers,

Peter.
}}}

Øyvind's measurements

{{{  Øyvind's conclusion
Peter
3Feb98

Here are the results of my tests:

Runtime A: Sun 1.1.5
           Windows 95
           (Loaded from Sun, produced by Sun. Actually, on
           Sun's "Java Developer's Companion" CD that I ordered
           and paid over internet)

Runtime B: Symantec Java! JustInTime Compiler
           Windows 95
           Version 210.063 for JDK 1.1.3
           (Bought from Symantec, part of "Visual Cafe")

Runtime C: Kaffe Virtual Machine, T.J.Wilkinson & Ass. London
           JIT 0.92, java 1.1.2
           Linux on PC

College
  Also called "GreedyPhilsopher"
  The greedy philosopher gets nothing or very little compared with the rest.
  Same behaviour in runtime A and B.
  Runtime C: The Greedy get very much, nobody starves
Take_Res
  Competing for resource without waits.
  Both A,B and C get the resource.
  Same behaviour in runtime A and B.
  Runtime C: B gets nothing!

Conclusion:
  Sun and Symantec on Win95 have queue.
  Kaffe on Linux has stack.
}}}

New College.java

I have kept the file folding information (which leaves the code not very readable here).

{{{  College.java
{{{  Constants
class Constants{
   private int noOfPhilosophers;
   private int idOfGreedyPhilosopher;
   private int noOfChickens;
   private int canteenPlaceAndHoldQueue_ms;
   private int cookByChef_ms;
   private int thinkByHumblePhilosophers_ms;

   public Constants (Constants constants){
      this.noOfPhilosophers             = constants.getNoOfPhilosophers();
      this.idOfGreedyPhilosopher         = constants.getIdOfGreedyPhilosopher();
      this.noOfChickens                 = constants.getNoOfChickens();
      this.canteenPlaceAndHoldQueue_ms  = constants.getCanteenPlaceAndHoldQueue_ms();
      this.cookByChef_ms                = constants.getCookByChef_ms();
      this.thinkByHumblePhilosophers_ms = constants.getThinkByHumblePhilosophers_ms();
   }
   public Constants (int noOfPhilosophers,
      int idOfGreedyPhilosphe,
      int noOfChickens,
      int canteenPlaceAndHoldQueue_ms,
      int cookByChef_ms,
      int thinkByHumblePhilosophers_ms){

      this.noOfPhilosophers             = noOfPhilosophers;
      this.idOfGreedyPhilosopher         = idOfGreedyPhilosopher;
      this.noOfChickens                 = noOfChickens;
      this.canteenPlaceAndHoldQueue_ms  = canteenPlaceAndHoldQueue_ms;
      this.cookByChef_ms                = cookByChef_ms;
      this.thinkByHumblePhilosophers_ms = thinkByHumblePhilosophers_ms;
   }
   public int getNoOfPhilosophers(){
      return (noOfPhilosophers);
   }
   public int getIdOfGreedyPhilosopher(){
      return (idOfGreedyPhilosopher);
   }
   public int getNoOfChickens(){
       return (noOfChickens);
   }
   public int getCanteenPlaceAndHoldQueue_ms(){
       return (canteenPlaceAndHoldQueue_ms);
   }
   public int getCookByChef_ms(){
       return (cookByChef_ms);
   }
   public int getThinkByHumblePhilosophers_ms(){
       return (thinkByHumblePhilosophers_ms);
   }
}
}}}  
class Canteen{ // Passive
   {{{  Comment
   //
   // Philosphers eat chickens.  They queue up at the canteen to use the `get'
   // method.  Inside the `get' method, they get served straight away so long
   // as there are some chickens ready.  Otherwise they `wait' on stand-by.
   //
   // The chef cooks chickens.  When he has a batch ready, he also queues up
   // at the canteen in order to use the `put' method.  This involves setting
   // down the batch -- which takes around 3 seconds -- and clearing the stand-by
   // queue (of philosophers waiting for chickens) by calling `notifyAll'.
   //
   {{{  note 1
   //
   // Clearly, the Chef should not have to queue up with the Philosophers to
   // get into the Canteen.  The Philosophers should have their own queue and
   // the Chef should only have to contend with one Philospher when dealing with
   // the chickens in the canteen.  Such a separate queue for the Philosophers is
   // just like the seperate queues for readers/writers that we needed for the
   // securely shared Channel or Buffer class.  However, we are modelling this
   // Canteen on the CubbyHole class (to show the danger of starvation it contains)
   // and CubbyHole has its queue shared by both readers and writers.
   //
   }}}  
   {{{  note 2
   //
   // All methods, apart from the `run' method, are executed as part of the thread
   // of control of their calling objects.  This is particularly clear here, where
   // we see them speaking *as* those calling objects.  For instance, the `get'
   // method is part of the life of the calling Philosopher and `put' is part of
   // the life of the Chef.  So, this Canteen "object" has bits of Philosopher-
   // algorithm and bits of Chef-algorithm for its methods -- a somewhat confused
   // set of roles for something that's supposed to be a Canteen.  There's nothing
   // in these methods that are oriented towards the life of the Canteen.
   //
   // So, alongside the semantic imprecision of `wait/notify' and alongside the
   // non-compositional (or, if you prefer, non-referentially-transparent) semantics
   // of methods in general, we have to come to terms with the idea that no methods
   // (apart from `run') are oriented towards the "objects" of which they are
   // supposed to be a part.  So much for "object-orientation" in the formal, and
   // quite arbitrary, definition of the term!  I believe that the first two
   // problems referenced in this paragraph are a direct consequence of the third.
   // These problems are not special to this Canteen, but are universal across
   // all passive objects.
   //
   // The Canteen should, of course, be implemented as an active object connected
   // to the philosophers and the chef via simple channels or buffers.  Then, we
   // wouldn't have the problems arising from this design.  This is left as an
   // exercise!
   //
   }}}  
   }}}  
   {{{  Declarations
   private int noOfChickens = 0;
   private Constants constants;
   private int noOfMeals[];
   private boolean report = true;
   }}}  
   {{{  Canteen
   public Canteen (Constants constants){
      this.constants = new Constants(constants);
      noOfMeals = new int[constants.getNoOfPhilosophers()];

      for (int i = 0; i < constants.getNoOfPhilosophers(); i++){
         noOfMeals[i] = 0;
      }
   }
   }}}  
   {{{  report
   public synchronized void report (boolean report){
      this.report = report;
      if (report == false){
         System.out.println
            ("\nWILL NOW REPORT NUMBER OF EATEN CHICKENS FOR EACH PHILOSOPHER" +
             "\nSince printing is more rare, this may affect scheduling ... " +
             "\n");
      }
   }
   }}}  
   {{{  Canteen get (contains the only "wait")
   public synchronized int get (int id){
      while (noOfChickens == 0){
         if (report){
            // moan
            System.out.println ("(" + System.currentTimeMillis() + ") " +
               "Phil " + id + ": wot, no chickens? I'll wait ... WAITING ...");
         }

         // get on stand-by queue, letting in the next philosopher (or chef)
         // First and only "wait" is here in Canteen.get
         try {wait();} catch (InterruptedException e){}

      }
      if (report){
         // thanks
         System.out.println ("(" + System.currentTimeMillis() + ") " +
            "Phil " + id + ": those chickens look good ... one please ... ");
      }
      noOfChickens = noOfChickens - 1;

      noOfMeals[id]++;
      StringBuffer stringBuffer = new StringBuffer();
      stringBuffer.append("(" + System.currentTimeMillis() + ") ");

      for (int i = 0; i < constants.getNoOfPhilosophers(); i++){
         stringBuffer.append (noOfMeals[i] + " ");
      }
      if (report == false){
         System.out.println (stringBuffer.toString());
      }
      return 1;
   }
   }}}  
   {{{  Canteen put (contains only "notify" or "notifyAll")
   public synchronized void put (int noOfChickensToAdd){
      // bring in the tray
      if (report){
         System.out.println ("(" + System.currentTimeMillis() + ") " +
            "Chef  : ouch ... make room ... this dish is very hot ... ");
      }

      // take 3 seconds to set down the dish (meanwhile a queue may be developing)
      try {Thread.sleep(constants.getCanteenPlaceAndHoldQueue_ms());} catch (InterruptedException e){}

      noOfChickens = noOfChickens + noOfChickensToAdd;
      if (report){
         // announce arrival of more chickens
         System.out.println ("(" + System.currentTimeMillis() + ") " +
            "Chef  : more chickens ... " + noOfChickens + " now available ... NOTIFYING ...");
      }

      // Put any waiting philosophers back on the main queue
      // First and only notify or notifyAll is here in Canteen.put
      notifyAll();
   }
   }}}  
}
class Chef extends Thread{ // Active
   {{{  Comment
   //
   // A chef is an active object.  He cooks chickens in batches of four -- taking
   // around 2 seconds per batch -- and then takes then to the canteen.
   //
   // This cycle continues indefinitely.
   }}}  
   {{{  Declarations
   private Canteen canteen;
   private Constants constants;
   private boolean report = true;
   }}}  
   {{{  Chef
   public Chef (Canteen canteen, Constants constants){
      this.canteen = canteen;
      this.constants = new Constants(constants);
      start();
   }
   }}}  
   {{{  report
   public synchronized void report (boolean report){
      this.report = report;
   }
   }}}  
   {{{  run
   public void run(){
      if (report){
         System.out.println ("(" + System.currentTimeMillis() + ") " +
            "Chef  : starting ... ");
      }
      while (true){
         // cook 4 chickens
         if (report){
            System.out.println ("(" + System.currentTimeMillis() + ") " +
               "Chef  : cooking ... ");
         }

         // cook for around 2 seconds
         try {Thread.sleep(constants.getCookByChef_ms());} catch (InterruptedException e){}

         if (report){
            System.out.println ("(" + System.currentTimeMillis() + ") " +
               "Chef  : " + constants.getNoOfChickens() + " chickens, ready-to-go ... ");
         }
         canteen.put(constants.getNoOfChickens());
      }
   }
   }}}  
}
class Phil extends Thread{ // Active
   {{{  Comment
   //
   // A philosopher thinks for a while -- around 3 seconds -- and then goes to the
   // canteen for food, consuming what he gets straight away.   This cycle continues
   // indefinitely.
   //
   // Except, that is, for philosopher 0 ...  who refuses to think and just keeps
   // going to the canteen.  He will get his come-uppance shortly.
   //
   }}}  
   {{{  Declarations
   private int id;
   private Canteen canteen;
   private boolean report = true;
   private Constants constants;
   }}}  
   {{{  Phil
   public Phil (int id, Canteen canteen, Constants constants){
      this.id = id;
      this.canteen = canteen;
      this.constants = new Constants(constants);
      start();
   }
   }}}  
   {{{  report
   public synchronized void report (boolean report){
      this.report = report;
   }
   }}}  
   {{{  run
   public void run(){
      int chicken;

      if (report){
         System.out.println ("(" + System.currentTimeMillis() + ") " +
            "Phil " + id + ": starting ...");
      }
      while (true){
         // everyone, bar the greedy philosopher (0), has a little think
         if (id != constants.getIdOfGreedyPhilosopher()){
            // think for around 3 seconds
            try {Thread.sleep(constants.getThinkByHumblePhilosophers_ms());} catch (InterruptedException e){}
         }
         if (report){
            System.out.println ("(" + System.currentTimeMillis() + ") " +
               "Phil " + id + ": gotta eat ... ");
         }

         // want chicken
         chicken = canteen.get(id);

         // consume chicken
         if (report){
           System.out.println ("(" + System.currentTimeMillis() + ")" +
              " Phil " + id + ": mmm ... that's good ... ");
         }

      }
   }
   }}}  
}
public class College{
   {{{  Comment
   //
   // The College consists of 5 Philosophers, a Chef and the Canteen.  The Chef and
   // the Philosophers are "active" objects.  The Canteen is a "passive" object
   // through which the Philosophers and the Chef have to interact.
   //
   // The Canteen is implemented in the style of the CubbyHole example from Sun's
   // Java Tutorial.  As such, it exposes each Philosopher to the danger of
   // starvation (by infinite overtaking by fellow Philosophers).  Sadly, this
   // does happen with the particular circumstances of timing set up in this
   // demonstration.  Happily, it's the greedy Philosopher that starves -- he
   // never even gets one meal, despite being in the Canteen the whole time!
   //
   }}}  
   {{{  main
   public static void main (String argv[]){

      int noOfPhilosophers              =  5;
      int idOfGreedyPhilosopher         =  0;
      int noOfChickens                  =  4;
      int canteenPlaceAndHoldQueue_sec  =  3;
      int cookByChef_sec                =  2;
      int thinkByHumblePhilosophers_sec =  3;
      int reportOff_sec                 = 30;
      int k = 1000;

      System.out.println ("");
      System.out.println ("Analyser of scheduling of objects waiting on monitor");
      System.out.println ("College version 2.0 - 30.Jan.1998");
      System.out.println ("  Idea and coded by Peter Welch, University of Kent at Canterbury, UK");
      System.out.println ("  Make-up by Oyvind Teig, Autronica, Norway");
      System.out.println ("");
      System.out.println ("  noOfPhilosophers:              " + noOfPhilosophers);
      System.out.println ("  idOfGreedyPhilosopher:         " + idOfGreedyPhilosopher);
      System.out.println ("  noOfChickens:                  " + noOfChickens);
      System.out.println ("  canteenPlaceAndHoldQueue_sec:  " + canteenPlaceAndHoldQueue_sec);
      System.out.println ("  cookByChef_sec:                " + cookByChef_sec);
      System.out.println ("  thinkByHumblePhilosophers_sec: " + thinkByHumblePhilosophers_sec);
      System.out.println ("  reportOff_sec:                 " + reportOff_sec);
      System.out.println ("");
      System.out.println ("  Terminate with Ctrl-C");
      System.out.println ("");

      try {Thread.sleep(10 * k);} catch (InterruptedException e){}

      Constants constants =
         new Constants (
            noOfPhilosophers,
            idOfGreedyPhilosopher,
            noOfChickens,
            canteenPlaceAndHoldQueue_sec * k,
            cookByChef_sec * k,
            thinkByHumblePhilosophers_sec * k);

      Canteen canteen = new Canteen(constants);
      Chef chef = new Chef(canteen, constants);
      Phil[] phil = new Phil[noOfPhilosophers];

      for (int i = 0; i < noOfPhilosophers; i++){
         phil[i] = new Phil (i, canteen, constants);
      }
      try {Thread.sleep(reportOff_sec * k);} catch (InterruptedException e){}

      for (int i = 0; i < noOfPhilosophers; i++){
         phil[i].report(false);
      }
      canteen.report(false);
      chef.report(false);
   }
   }}}  
}
}}}

Take_Res.java

{{{  Take_Res.java
// Proposed by Peter Welch in e-mail to me on 29Jan98
// Programmed by Øyvind Teig

// Both A,B and C get the resource

// We have the same behaviour with
// 1. Symantec Java! JustInTime Compiler Version 210.063 for JDK 1.1.3
//    Copyright (C) 1996-97 Symantec Corporation
//    Running on Window-95
// 2. JVM 1.1.5
//    Running on Window-95

{{{  Resource
class Resource {
   public synchronized void take (String id) {
      System.out.println ("User " + id + " has resource");
      try {Thread.sleep(3000);} catch (InterruptedException e){}
   }
}
}}}  
{{{  User
class User extends Thread {
   private String id;
   private Resource resource;

   public User (String id, Resource resource) {
      this.id = id;
      this.resource = resource;
      System.out.println ("User " + id + " started");
      start();
   }

   public void run() {
      while (true) {
         resource.take(id);
         try {Thread.sleep(1000);} catch (InterruptedException e){}
      }
   }
}
}}}  

class Take_Res {
   {{{  main
   public static void main (String argv[]) {
      Resource resource = new Resource();

      User[] user = new User[3];

      user[0] = new User ("A  ", resource);
      try {Thread.sleep(1000);} catch (InterruptedException e){}
      user[1] = new User (" B ", resource);
      try {Thread.sleep(1000);} catch (InterruptedException e){}
      user[2] = new User ("  C", resource);
   }
   }}}  
}
}}}

Original College.java