Synchronization

[Roy Wilson]

Hi,

The code I provided Patrick was developed  by Peter Welch at the University of Kent at
Canterbury. It was intended to illustrate just what Pat notes: the looseness of the Java
specification. Welch suggests tightening up the spec by using a library based on CSP.

Attached is my rewrite of the code using the JCSP library.

Roy Wilson
designrw at bellatlantic

Patrick Tullmann wrote:

> Roy Wilson <designrw at bellatlantic.net> pointed out to me in private
> email that Kaffe starves out threads that are contending for a lock.
> (I've attached his sample testcase --- somewhat modified).
>
> This behavior results from Kaffe's lock queues being LIFO.  Making the
> lock queue FIFO fixes his particular problem.  (I've attached the
> patch, too.)  The patch makes the releaser of a lock wake up the
> thread on the tail of the queue vs. the thread on the head of the
> queue.
>
> However, Godmar has pointed out to me that Kaffe's current
> implementation is within the specification (the spec makes no fairness
> or liveness guarantees).  Additionally, Kaffe breaks broken code
> "faster".  If you really want fairness, then you'll have to implement
> a queue of some sort above the Java primitives.
>
> Anyone else have thoughts on this (or references to JDC
> tips/bugs/documentation)?
>
> -Pat
>
> ----- ----- ---- ---  ---  --   -    -      -         -               -
> Pat Tullmann                                       tullmann at cs.utah.edu
>           This signature witticism intentionally left blank.
>
>  --8<---  TakeResource.Java
>
> class TakeResource {
>   public static final int HOLD_DELAY = 3000;
>   public static final int ACQUIRE_DELAY = 1000;
>   public static final int THREADSTART_DELAY = 1000;
>
>   public static void main (String argv[]) {
>     Resource resource = new Resource();
>     User[] user = new User[3];
>     user[0] = new User ("A  ", resource);
>     try { Thread.sleep(THREADSTART_DELAY); }
>     catch (InterruptedException e){}
>     user[1] = new User (" B ", resource);
>     try { Thread.sleep(THREADSTART_DELAY); }
>     catch (InterruptedException e){}
>     user[2] = new User ("  C", resource);
>   }
> }
>
> 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(TakeResource.ACQUIRE_DELAY); }
>       catch (InterruptedException e){}
>     }
>   }
> }
>
> class Resource {
>   public synchronized void take (String id) {
>     System.out.println ("User " + id + " has resource");
>     try { Thread.sleep(TakeResource.HOLD_DELAY); }
>     catch (InterruptedException e){}
>   }
> }
>
>  --8<---  TakeResource.Java
>
>  --8<---  Patch
>
> Index: kaffe/kaffevm/locks.c
> ===================================================================
> RCS file: /cvs/kaffe/kaffe/kaffe/kaffevm/locks.c,v
> retrieving revision 1.35
> diff -u -r1.35 locks.c
> --- kaffe/kaffevm/locks.c       2000/04/12 17:41:06     1.35
> +++ kaffe/kaffevm/locks.c       2000/05/15 18:59:11
> @@ -248,12 +248,43 @@
>          * time to tell them.
>          */
>         if (lk->mux != 0) {
> +#if 1 /* FAIRQUEUING */
> +               /* Special case: a single element list */
> +               if (unhand(lk->mux)->nextlk == NULL)
> +               {
> +                       tid = lk->mux;
> +                       lk->mux = NULL;
> +               }
> +               else
> +               {
> +                       Hjava_lang_Thread** prevTail;
> +
> +                       prevTail = &lk->mux;
> +
> +                       /* while there are still two more on the list */
> +                       while((unhand(*prevTail)->nextlk != NULL)
> +                             && (unhand(unhand(*prevTail)->nextlk)->nextlk) != NULL) {
> +                               prevTail = &(unhand(*prevTail)->nextlk);
> +                       }
> +
> +                       tid = unhand(*prevTail)->nextlk;
> +                       assert(unhand(tid)->nextlk == NULL);
> +                       unhand(*prevTail)->nextlk = NULL;
> +
> +                       /* lk->mux is head of queue, don't update */
> +               }
> +
> +               lk->holder = NULL;
> +               putHeavyLock(lkp, lk);
> +               ksemPut((Ksem*)(unhand(tid)->sem));
> +#else
>                 tid = lk->mux;
>                 lk->mux = unhand(tid)->nextlk;
>                 unhand(tid)->nextlk = 0;
>                 lk->holder = 0;
>                 putHeavyLock(lkp, lk);
>                 ksemPut((Ksem*)(unhand(tid)->sem));
> +#endif
>         }
>         /* If someone's waiting to be signaled keep the heavy in place */
>         else if (lk->cv != 0) {
>
>  --8<---  Patch
-------------- next part --------------
// This code involves minimal change to the original version, and guarantees
// fair thread scheduling by both SUN JDK 1.2.1 and  Kaffe 1.05 JVM's.
// This is made possible by the JCSP (Java Communicating Sequential Processes) 
// package developed at the University of Kent at Canterbury by P. Welch
// and P. Austin.
//
// The following code was created using SUN Forte for Java CE v1.0
// by Roy  Wilson, designrw at bellatlantic.net on 10 May 2000
// Although not shown, each file was declared as part of a package.

import jcsp.lang.*;
class TakeResource {
  public static void main (String argv[]) {
    Resource resource = new Resource();

// User is a JCSP-defined CSProcess, an active object that encapsulates its own thread(s)
    User[] user = new User[3];
    user[0] = new User ("A  ", resource);
    user[1] = new User (" B ", resource);
    user[2] = new User ("  C", resource);

// The JCSP-defined Parallel construct causes the User processes to execute concurrently

    new Parallel( user ).run();
  }
}

import jcsp.lang.*;
import java.util.Random;
public class User implements CSProcess {
  private String id;
  private Resource resource;

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

  public void run() {
    final Timer tim = new Timer ();
 
// As before, each User process takes control of the Resource object.
// The thread encapsulated within the User then sleeps.    
    while (true) {
	resource.take(id);
	tim.sleep(1000);
    }
  }
}

import jcsp.lang.*;
class Resource {
  public void take(String id) {
      Timer tim = new Timer ();

      System.out.println ("User " + id + " has resource");
// Once a User process has acquired the Resource object, it's thread
// sleeps for 3000 time units 
      tim.sleep(3000);
  }
}