No subject

[Patrick Tullmann]

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