Methods of synchronization and precautions to prevent deadlock.

Things that have the following mechanisms are called synchronization primitives (such as semaphores and monitors).

  • Exclusive access to shared resources
  • Thread wait/wakeup processing

Monitor

Java uses a mechanism called monitor as a synchronization primitive. A monitor wraps data to be shared between threads in methods, etc., makes it readable/writable only from inside those methods, and ensures only one thread can enter at a time. This allows exclusive access to the data inside the monitor. In Java, by adding the private modifier to shared data and the synchronized modifier to methods, monitors can be implemented on a per-method basis. Also, monitors are used to perform condition synchronization.

Java provides the following three methods for thread wait/wakeup, so we use these.

  • public final void notify()
    • Wakes up one thread waiting for the object
  • public final void notifyAll()
    • Wakes up all threads waiting for the object
  • public final void wait() throws InterruptedException
    • Waits to be woken up by another thread. All Synchronization locks related to the monitor are released.
    • After being woken up, must reacquire the monitor before resuming execution.

For example, a counter that moves between 0 and N is implemented as follows. In Counter::inc() and Counter::dec(), use while statements instead of if statements. (With if statements, the condition isn’t re-evaluated when waking from wait(), so it may have changed while sleeping) When you don’t know how many threads are waiting, wake them with notifyAll(). (To prevent unnecessary waiting)

public class Counter {
	private int count;
	private int N;
	
	public Counter(int max){
		count = 0;
		N = max;
	}
	
	public int get(){
		return count;
	}
	
	synchronized void inc() throws InterruptedException{
		while(count==N)
			wait();
		count++;
		notifyAll();
	}
	
	synchronized void dec() throws InterruptedException{
		while(count==0)
			wait();
		count--;
		notifyAll();
	}
}

public class IncRunnable implements Runnable{
	
	private Counter counter;
	
	public IncRunnable(Counter c){
		counter = c;
	}
	
	@Override
	public void run() {
		while(true){
			try {
				counter.inc();
			} catch (InterruptedException e) {}
		}
	}
}

public class DecRunnable implements Runnable{
    /* Omitted */
}

public class Main {
	public static void main(String[] args) {

		Counter counter = new Counter(10);
		new Thread(new IncRunnable(counter)).start();
		new Thread(new DecRunnable(counter)).start();
		
		for(int i=0;i<10000;i++)
			System.out.println(counter.get());
	}
}

Semaphore

By the way, a semaphore looks like this. In Semaphore::wait(), there’s no need to wake threads, so notify() isn’t called. Also, Semaphore::signal() only needs to wake one thread, so it uses notify().

public class Semaphore {
  private int n;

  public Semaphore(int n){
    this.n = n;
  }

  synchronized public void signal(){
    n++;
    notify();
  }

  synchronized public void  wait() throws InterruptedException{
    while(n==0)
      wait();
    n--;
  }
}

Nested Monitors

However, if you use semaphores to create a buffer like the following, you’ll run into trouble.

public void Buffer(){
  Semaphore s1,s2;
  ...

  public Buffer(int n){
    s1 = new Semaphore(0); // In use
    s2 = new Semaphore(n); // Empty
  }
  
  synchronized public void put(Object o) throws InterruptedException{
    s2.wait(); 
    /* Write processing */
    s1.signal();
  }

  synchronized public Object get() throws InterruptedException{
    s1.wait(); 
    /* Read processing */
    s2.signal();
  }
}

Actually, if you call get() when the buffer is empty (such as initial state), it will deadlock.

The cause seems to be the property of wait() that “Waits to be woken up by another thread. All Synchronization locks related to the monitor are released”.

Suppose thread 1 calls Buffer::get(), and then thread 2 calls Buffer::put().

  1. First, thread 1 sleeps at s1.wait().
  • Here, all Synchronization locks related to s1.wait() are released, but the Synchronization lock related to Buffer::get() is not released.
  1. Next, when thread 2 calls Buffer::put(), it deadlocks because the Buffer::get() lock hasn’t been released.

The cause is the double Synchronization lock, so if we eliminate the nesting as follows, it’s resolved. Good, good.

public Object get() throws InterruptedException{
  s1.wait(); 
  synchronized(this){
    /* Read processing */
  }
  s2.signal();
}