C311 script14.txt -- 4/28/97

---

	  SYNCHRONIZATION MECHANISMS AND ERRORS WITH JAVA THREADS

---

Concurrency may be obtained using multiple

  PROCESSES, which do not share memory, and/or

  THREADS, which do share memory.

The term TASK usually refers to threads, but sometimes refers to processes.

A process may contain many threads.

The overhead cost of a CONTEXT SWITCH that transfers control of a processor
from one process or thread to another is much higher for processes.

A sequence of instruction execution that is uninterrupted, or ordered as if
it were uninterrupted, is referred to as a THREAD OF CONTROL.

At the machine level, instruction execution may be interrupted via hardware
INTERRUPTS that alter the usual instruction fetch-execute cycle.

TIME SHARING refers to the PREEMPTION of threads or processes if a unit of
time called a TIME SLICE expires while the thread or process has control of
the processor.  Time sharing is implemented via a REAL-TIME CLOCK that
generates interrupts.

If multiple threads are running on the same processor and each maintains
control until it is relinquished via a system call, the threads are said to
interact SYNCHRONOUSLY.  If threads or processes are running on separate
processors, or interrupts can cause control to switch from one to the
other, and they share state (usually memory), their interaction is
ASYNCHRONOUS.

---

When concurrent threads of control share any resource (such as memory),
SYNCHRONIZATION problems may arise.  These problems are much harder when
the threads interact asynchronously.

Java threads may interact synchronously or asynchronously, depending on the
implementation.

The following Java program illustrates a synchronization problem.

---
    public class ThreadEG {
      public static void main(String[] args) throws InterruptedException {
	Counter c1 = new Counter(100, 20);
	Counter c2 = new Counter(50, 40);
	c1.myThread.join();   // wait until couter1's thread dies
	c2.myThread.join();   // may throw InterruptedException
	Monitor m1 = new Monitor();
	Monitor m2 = new Monitor();
	Deadlocker d1 = new Deadlocker(m1, m2);
	Deadlocker d2 = new Deadlocker(m2, m1);
	d1.myThread.join();
	d2.myThread.join();
	System.out.println(); // will never get here if there is a deadlock
      }
    }

    class Counter implements Runnable {
      static int count = 0;
      Thread myThread = new Thread(this); // 'this' is cast to Runnable
      int delay;
      int numTimes;
      Counter(int delay, int numTimes) {
	this.delay = delay;
	this.numTimes = numTimes;
	myThread.start();
      }
      public void run() {
	for (int i = 0; i < numTimes; i++) {
	  bump();
	  System.out.print(count + " ");
	  try { Thread.sleep(delay); } // go to sleep for delay milliseconds
	  catch (InterruptedException e) {}
	}
      }
      static void bump() {  // add modifier synchronized to avoid lost bumps
	int temp = count;
	for (int j = 0; j < 10000; j++);
	Thread.yield();     // suspend the current thread
	for (int j = 0; j < Math.random()*10000; j++);
	count = temp + 1;
      }
    }

    class Deadlocker implements Runnable {
      Thread myThread = new Thread(this);
      Monitor m1;
      Monitor m2;
      Deadlocker(Monitor m1, Monitor m2) {
	this.m1 = m1;
	this.m2 = m2;
	myThread.start();
      }
      public void run() {
	m1.entry1(m2);
      }
    }

    class Monitor {
      static Rendezvous rdv = new Rendezvous();
      synchronized void entry1(Monitor m) {
	rdv.rdvWait();  
	// one thread is now in monitor1 and another in monitor2
	m.entry2(); // neither can enter the other monitor here
      }
      synchronized void entry2() {
	// never get here due to deadlock
      }
    }

    class Rendezvous {
      boolean waiting = false;
      synchronized public void rdvWait() {
	if (waiting) {
	  notify();        // release waiting thread
	  waiting = false;
	}
	else {
	  waiting = true;
	  try { wait(); }  // wait until notified
	  catch (InterruptedException e) {} 
	}
      }
    }

---

The last number printed varied in a few tests between 48 and 56.
With "synchronized static void bump() ...", the last number is always 60.

Monitors are a synchronization mechanism that may be used to avoid
syncrhonization bugs due to shared data that is protected by the monitor
(the instance variables of a Java monitor).

In Java, every object with a synchronized method is a MONITOR.  

Only one thread at a time is allowed in a synchronized method of a monitor.
When a thread enters a synchronized object, it obtains a LOCK on the
object.  Multiple locks may be held by the same thread.

Waiting threads relinquish their locks while they WAIT and must reaquire
them after being NOTIFIED and before continuing execution.

When there is a group of two or more processes that are all waiting
for a resource (such as a monitor) that is held by another process in the
group, the processes are DEADLOCKED.

A synchronization mechanism by which two threads must reach the same or
related positions in code before eather can proceed is called a 
RENDEZVOUS.  For example in a remote procedure call the caller
and callee must rendezvous to begin the call.  In the program above, two
threads must call the rdvWait() method before either can leave the method.

The Thread stop() method sends the Error ThreadDeath.  This allows the
thread to clean up with try finally clauses before it dies.  It is possible
to catch this error like any other, but if it is not thrown again the
thread may not be possible to kill (short of killing the entire java process).

---

Threads may undergo a number of state transitions.

BORN -> READY on a Thread start() call

READY -> RUNNING on a dispatch, using priority scheduling.

RUNNING -> SLEEP on a Thread sleep() call and SLEEP -> READY on sleep interval
timeout. 

RUNNING -> SUSPEND on a Thread suspend() call and SUSPEND -> READY on a
Thread resume() call.

RUNNING -> BLOCKED on an I/O request and BLOCKED to READY on completion of
the request.

RUNNING -> OBTAIN-LOCKS on entry to a synchronized method if the lock
cannot be aquired at that time.

RUNNING -> WAITING on an Object wait() call and WAITING -> OBTAIN-LOCKS
on an Ojbect notify() call.

OBTAIN-LOCKS -> READY if all necessary locks have been aquired.

RUNNING -> STOPPED when the ThreadDeath error is thrown from the task.
f
---

Perhaps the most widely used synchronization mechanism is semaphores.  They
are available, for example, in most operating systems for use at the
process level.

Semaphores are implemented in Java by the following Semaphore class.
Traditional semaphores, as in the Semaphore class, make a guarantee of
fairness, but not the order in which waiting threads are released by
signals.  The FifoSemaphore class maintains waiting processes in a FIFO
queue.

A deadlock setup similar to the monitor example (but in this case not
involving nested monitors) is used to demonstrate that semaphores share
the danger of deadlock if improperly used.  

Semaphores are a lower level mechanism than monitors, but their added
flexibility is sometimes important.  Fortunately they are not hard to
implement in Java.

---

    public class Semaphore {
      int n;
      Semaphore(int n) {
	if (n < 0) throw new Error();
	this.n = n;
      }
      synchronized public void semSignal() {
	if (++n <= 0) notify(); 
      }
      synchronized public void semWait() {
	if (--n < 0) {
	  try { wait(); } catch (InterruptedException e) {}
	}
      }
      public String toString() {
	return "<" + super.toString() + " value=" + n + ">";
      }
      public static void main(String[] args) throws InterruptedException {
	Semaphore s1 = new FifoSemaphore(0);
	Semaphore s2 = new FifoSemaphore(0);
	Deadlocker d1 = new Deadlocker(s1, s2);    
	Deadlocker d2 = new Deadlocker(s2, s1);    
	d1.myThread.join();
	d2.myThread.join();
	System.out.println(); // will never get here if there is a deadlock
      }
    }

    class FifoSemaphore extends Semaphore {
      private Queue q = new Queue();
      FifoSemaphore(int n) {
	super(n);
      }
      synchronized public void semSignal() {
	if (++n <= 0) (q.dequeueCE()).notify(); 
      }
      synchronized public void semWait() {
	if (--n < 0) {
	  q.enqueue(this);
	  try { wait(); } catch (InterruptedException e) {}
	}
      }
    }

    class Deadlocker implements Runnable {
      Thread myThread = new Thread(this);
      Semaphore sem1;
      Semaphore sem2;
      Deadlocker(Semaphore sem1, Semaphore sem2) {
	this.sem1 = sem1;
	this.sem2 = sem2;
	myThread.start();    
      }
      public void run() {
	sem1.semWait();   // deadlock here
	sem2.semSignal(); // ok if signal precedes wait
      }
    }

    class List {
      public Object head;
      public List tail;
      List (Object obj, List lst) {
	head = obj;
	tail = lst;
      }
    }

    class EmptyQueueException extends Exception {}

    class Queue {
      List head = null;
      List tail;
      public void enqueue(Object obj) {
	if (head == null) {
	  head = new List(obj, null);
	  tail = head;
	}
	else {
	  tail.tail = new List(obj, tail);
	  tail = tail.tail;
	}
      }
      public Object dequeue() throws EmptyQueueException {
	if (head == null) throw new EmptyQueueException();
	else {
	  Object result = head.head;
	  head = head.tail;
	  return result;
	}    
      }
      public Object dequeueCE() { // dequeue Catch Exception
	try { return dequeue(); }
	catch (EmptyQueueException e) { throw new Error(); }
      }
    }

---

END

---