Synchronizing Java Threads

The need of synchronization

The fact that a thread can execute in parallel with other threads is the main power of the concurrent programming. But this property causes usually a lot of trouble for programmers which must assure a correct sharing of the resources used in common by different threads. It means that the threads that execute in parallel and use common critical resources must be synchronized at some points to assure a correct functioning of the system. The correct functioning of a parallel or concurrent program is possible only if the conflicts of simultaneously performing a critical section operation by several threads are avoided. A critical section operation is an operation (a portion of the program code) that can not be done in parallel by several processes or treads, like incrementing a sheared counter, writing in a shared buffer, modifying a shared object, etc.

The synchronization means that a thread must wait for another thread to leave the critical section and to enter into this section using some security measures, e.g. locking the critical section when entering it.

To show a situation when the synchronization is strictly necessary consider the following program. The program creates two threads that use a shared object to count the total number of iterations done by both threads.

//Example 12.

public class CounterThread extends Thread {
        
  Counter counter;  

  public static void main(String[] args) {
    Counter counter = new Counter();
    CounterThread counterThread1 = new CounterThread(counter);
    CounterThread counterThread2 = new CounterThread(counter);
    counterThread1.start();
    counterThread2.start();
    try{
      counterThread1.join();
      counterThread2.join();
    } catch (InterruptedException e) {
      System.out.println("Error during join");
    }
    System.out.println("The variable i= " + counter.get() + ", the expected value i= 20");
  }
  
  public CounterThread(Counter counter) {
    this.counter = counter;
  }

  public void run() {
    counter.iterate();
  }
}

class Counter {
  private int i = 0;
  
  public void iterate() {
    for (int j=0; j<10; j++){
      i=inc(i);
      try{
        Thread.sleep((int) (Math.random()*10));
      } catch (InterruptedException e) {
        System.out.println("Error during sleep");
      }
    }
  }
  
  public int get(){
    return i;
  }

  private int inc(int n){
     return n+1;
  }
}

The threads call the method iterate() which increments the variable i 10 times. One can expect that the resulting value of the variable will be 20, but some runs of the programs print values that differ of 20. For example, when running this programs 10 times

$ for i in {1..10}; do java CounterThread; done;
the following output is obtained:

The variable i= 18, the expected value i= 20
The variable i= 20, the expected value i= 20
The variable i= 20, the expected value i= 20
The variable i= 19, the expected value i= 20
The variable i= 20, the expected value i= 20
The variable i= 20, the expected value i= 20
The variable i= 20, the expected value i= 20
The variable i= 20, the expected value i= 20
The variable i= 20, the expected value i= 20
The variable i= 20, the expected value i= 20

Why this programs prints different results ?

The answer comes from the fact that the threads execute in the same address space (memory). However, each thread uses its own stack to load data from memory, to execute the code and to save the data back into the memory. When accessing the shared address space, a thread can be interrupted by the operating system.

Consider, for example, the byte code of the method inc(int). When run in the two threads this code can be interrupted. Suppose it is interrupted as shown in the table below.
 
private int inc(int);
  Code:
   0:   iload_1
   1:   iconst_1
        <interrupt 1>
   2:   iadd
   3:   ireturn
 
private int inc(int);
  Code:
   0:   iload_1
   1:   iconst_1
   2:   iadd
        <interrupt 2>
   3:   ireturn
The bytecode command iload_1 loads the argument of method into the stack, the bytecode command icont_1 loads the constant 1 into the stack. The command iadd adds the two values from the top of the stack. Due to the fact that the interruption is done after the value i is loaded in two different stacks, the two copies of the loaded variable i are incremented independently. At the end, the two calls of the method inc(int) will return the same value i+1. But the incrementation was done two times. Thus, after these two calls the value should be i+2, not i+1.

In our case the two threads use the same object to increment a variable. But, as we have seen above, this operation should not be performed simultaneously by different threads. This operation is not thread-safe. Such operations are called critical sections and special synchronization restrictions must be imposed when executing them.

This program however imposes no synchronization restrictions on the two threads and the output of the program is unpredictably.

The Producer/Consumer example

To introduce the Java threads synchronization techniques we consider the Producer/Consumer example. We modified this example to allow the interactive interfering with Java threads.

The example consists of a class MyData0 which boxes an integer value and of two classes Producer and Consumer that access an object of MyData0 type. The Producer and Consumer classes implement the Runnable interface. Thus, they can be run in threads. The Producer thread writes consecutive integer values into the MyData0 object and the Consumer thread reads these values. The Producer and Consumer threads are created and started in the ProducerConsumer class.

The goal of the program is to synchronize the Producer and the Consumer so that the values are not lost (overwritten) when the Producer performs consecutive write operations, and the same value is not read multiple times when the Consumer performs consecutive read operations.

The first version of this program does not implement thread synchronization:
 
//Example 13.

//Producer/Consumer example. Version 0.

class MyData0 {
	protected int data;
	protected boolean ready;
	protected boolean taken;
	protected boolean yield;
  
	public void store(int data) {
		this.data = data;
	}
	public int load() {
		return this.data;
	}
}

class Producer implements Runnable {
	MyData0 data;
	int interval;
	int identifier;
  
	public Producer(MyData0 data, int identifier, int interval) {
		this.data = data;
		this.interval = interval;
		this.identifier = identifier;
	}
  
	public void run() {
		int i = 0;
		while(true) {
			data.store(i++);
			System.out.println("Producer "+identifier+": "+i);
			try {
				Thread.sleep((int) (Math.random()*interval));
			} catch (InterruptedException e) {
				System.out.println("Producer error\n");
			}
		}
	}
}
class Consumer implements Runnable {
	MyData0 data;
	int interval;
	int identifier;
  
	public Consumer(MyData0 data, int identifier, int interval) {
		this.data = data;
		this.interval = interval;
		this.identifier = identifier;
	}
  
	public void run() {
		int i;
		while(true) {
			System.out.println("        Consumer "+identifier+": "+data.load());
			try {
				Thread.sleep((int) (Math.random()*interval));
			} catch (InterruptedException e) {
				System.out.println("Consumer error\n");
			}
		}
	}
}
public class ProducerConsumer {
	public static void main (String[] argv) {
		MyData0 data;
		Thread Producers[];
		Thread Consumers[];
    
		if  (argv.length < 7 ) {
			System.out.print("Usage: \n> java producerConsumer <version>");
			System.out.print("<numberOfProducers> <numberOfConsumers>");
			System.out.print("<producersPriority> <consumersPriority>");
			System.out.println("<sleepInterval> <yieldFlag>");
			return;
		}
    
		boolean yield = (Integer.valueOf(argv[6]).intValue() !=0 );
    
		switch(Integer.valueOf(argv[0]).intValue()){
		case 0:
			data = new MyData0(); break;
		/* case 1: */
		/* 	data = new MyData1(yield); break; */
		/* case 2: */
		/* 	data = new MyData2(yield); break; */
		/* case 3: */
		/* 	data = new MyData3(yield); break; */
		/* case 4: */
		/* 	data = new MyData4(); break; */
		default: 
			data = new MyData0();
		};

		int producersCount = Integer.valueOf(argv[1]).intValue();
		int consumersCount = Integer.valueOf(argv[2]).intValue();
		int producersPriority = Integer.valueOf(argv[3]).intValue();
		int consumersPriority = Integer.valueOf(argv[4]).intValue();
		int interval = Integer.valueOf(argv[5]).intValue();
		Producers = new Thread[producersCount];
		Consumers = new Thread[consumersCount];

		for(int i = 0; i < producersCount; i++){
			Producers[i]=new Thread (new Producer(data, i, interval));
			Producers[i].setPriority(producersPriority);
			Producers[i].start();
		}
    
		for(int i = 0; i < consumersCount; i++) {
			Consumers[i]=new Thread (new Consumer(data, i, interval));
			Consumers[i].setPriority(consumersPriority);
			Consumers[i].start();
		}
	}
}   

In this example the boolean variables ready, taken and yield of the class MyData0 are not used. They will be used later in the classes MyData1, MyData2, MyData3, MyData4 which extend this class.

The ProdicerConsumer takes the following parameters in the command line:

version
The number of the version to run. The current version is the Version 0. But in general this program will be able to run 5 different versions. So the possible values for this parameter are 0,1,2,3,4.
numberOfProducers
The number of the Producer threads to run.
numberOfConsumers
The number of the Consumer threads to run.
producersPriority
The priority of the Producer threads.
consumersPriority
The priority of the Consumer threads.
sleepInterval
The sleeping duration between two consecutive writings or readings in the Producer and in the Consumer threads. This parameter can be any positive integer, which represents the duration in milliseconds.
yieldFlag
A 0/1 flag that allows introducing the call of the yield() method in the idle loops. This flag is used to experiment with the examples of the versions 1,2,3 when used in the non-preemptive operating systems. For other versions like 0, and 4 this parameter has no effect, but it must be present in the command line.

To compile the example Version 0 one has to comment the lines:
 
    case 1:
      data = new MyData1(yield); break;
    case 2:
      data = new MyData2(yield); break;
    case 3:
      data = new MyData3(yield); break;
    case 4:
      data = new MyData4(); break;

Each case must be uncommented when the corresponding version will be implemented.

If we run the example Version 0 with the command line:
 

> java ProducerConsumer 0 1 1 5 5 10 0

where the parameters are:

  1. the version 0 of the program,
  2. one Producer thread,
  3. one Consumer thread,
  4. the Producer's priority 5,
  5. the Consumer's priority 5,
  6. the sleeping duration 10 milliseconds,
  7. no yield() methods in idle loops (this option has no effect on Version 0),
we will obtain the following output:
 
Producer 0: 0
        Consumer 0: 0
        Consumer 0: 0
Producer 0: 1
Producer 0: 2
        Consumer 0: 2
        Consumer 0: 2
Producer 0: 3
Producer 0: 4
        Consumer 0: 4
Producer 0: 5
        Consumer 0: 5
        Consumer 0: 5
Producer 0: 6
Producer 0: 7
        Consumer 0: 7

	...

From this output it follows that there is no synchronization between the Producer and the Consumer. Namely the values 1 and 3 are lost and the values 2 and 5 are read twice by the Consumer.

The first attempt to correct this situation is to use two boolean variables ready and taken to control data access as presented below:
 
//Example 14.

//Producer/Consumer example. Version 1a.

class MyData1 extends MyData0 {
  
  public MyData1(boolean yield) {
    ready = false;
    taken = true;
    this.yield = yield;
  }
  
  public void store(int data) {
    while(!taken) {
    }
    this.data = data;
    taken = false;
    ready = true;
  }
 
  public int load() {
    int data;
    while(!ready) {
    }
    data = this.data;
    ready = false;
    taken = true;
    return data;
  }
}

...

The ready flag is used to signify that new data was produced and is ready to be consumed. The taken flag is used to signify that the data was consumed and it can be overwritten.

The ready and taken flags used in Version 1a of this program solves the problem: each value is consumed only once and the values are not lost. However this solution introduces a new problem, the busy-loops. Busy-loops cause this program not to work in non-preemptive operating systems, because they do not cause triggering events for the scheduler. For example, if we run this program in a non-preemptive operating system with the command line:
 

> java ProducerConsumer 1 1 1 5 5 10 0

we will get 6 iterations of the program and after that it will hang up:
 

Producer 0: 0
        Consumer 0: 0
Producer 0: 1
        Consumer 0: 1
Producer 0: 2
        Consumer 0: 2
Producer 0: 3
        Consumer 0: 3
Producer 0: 4
        Consumer 0: 4
Producer 0: 5
        Consumer 0: 5
Producer 0: 6
        Consumer 0: 6

The problem in this case is the fact that a thread that enters the busy loop do not give away the processor and, thus, another thread that should change the value will not be scheduled to run.

This specific problem can be solved by including the yield() method in the busy loop, like below:
 
//Example 15.

//Producer/Consumer example. Version 1b.

class MyData1 extends MyData0 {
  
  public MyData1(boolean yield) {
    ready = false;
    taken = true;
    this.yield = yield;
  }
  
  public void store(int data) {
    while(!taken) {
      if (yield == true) {
        Thread.yield();
      }
    }
    this.data = data;
    taken = false;
    ready = true;
  }
 
  public int load() {
    int data;
    while(!ready) {
      if (yield == true) {
        Thread.yield();
      }
    }
    data = this.data;
    ready = false;
    taken = true;
    return data;
  }
}

...

For example if we run this program in non-preemptive operating system with the command line:
 

> java ProducerConsumer 1 1 1 5 5 10 1

we will obtain an infinite and correct output:
 
Producer 0: 0
        Consumer 0: 0
Producer 0: 1
        Consumer 0: 1
Producer 0: 2
        Consumer 0: 2
Producer 0: 3
        Consumer 0: 3
Producer 0: 4
        Consumer 0: 4
Producer 0: 5
        Consumer 0: 5
Producer 0: 6
        Consumer 0: 6
Producer 0: 7
        Consumer 0: 7
Producer 0: 8
        Consumer 0: 8
Producer 0: 9
        Consumer 0: 9
Producer 0: 10
...

It is important to point out that the program Version 1b with idle loops hangs only in non-preemptive operating systems. On preemptive operating systems this program works quite well.

The program Version 1b is a possible solution of the Producer/Consumer problem but only for one producer and one consumer. Consider, for example, one producer and two consumers. Suppose the two consumers are waiting in the busy loops in load() method when accessing the MyData1 object. When ready becomes true both consumers start data reading operation. During this concurrent access both consumers may read the same value. It means the value is consumed twice and that may be not what we wanted. An application may require a value to be consumed only once. Thus, the Version 1b is not a solution for the problems with many producers and many consumers. Even for one producer and one consumer this solution is not efficient, because busy loops are consuming the processors time.

In this context Java provides special structures for synchronizing the activities of many threads. They are all based on the concept of monitors, a widely used synchronization scheme developed by C.A.R. Hoare. A monitor is essentially a lock. The lock is attached to a resource that many threads may need to access, but that should be accessed by only one thread at a time. The resource is like a room. If the resource is not being used, the thread can acquire the lock and access the resource. When the thread is done, it relinquishes the lock, just as a person unlock the door and leave it open for the next person. However, if another thread already has the lock for the resource, all other threads have to wait until the current thread finishes and releases the lock.

The most common need for synchronization among threads in Java is to serialize their access to some resource like in our example. In other words, the synchronization makes sure that only one thread at a time can perform certain operations. In Java, every object has a lock associated with it. To be more specific, every class and every instance of a class has its own lock. The synchronized keyword marks places where a thread must acquire the lock before proceeding.

Often, you want to synchronize multiple methods of the same class, so that only one of the methods modifies or examines parts of the class at a time. All static synchronized methods in a class use the same class object lock. By the same token, all instance methods in a class use the same instance object lock. In this way, Java can guarantee that only one of a set of synchronized methods is running at a time. For example, the Version 2 of our Producer/Consumer example can be implemented using synchronized methods as follows:
 
//Example 16.

//Producer/Consumer example. Version 2.

class MyData2 extends MyData0 {  
  public MyData2(boolean yield) {
    ready = false;
    taken = true;
    this.yield = yield;
  }
  
  public synchronized void store(int data) {
    while (!taken) {
      if (yield == true) {
        Thread.yield();
      }
    }
    this.data = data;
    taken = false;
    ready = true;
  }
  
  public synchronized int load() {
    int data;
    while(!ready) {
      if (yield == true){
        Thread.yield();
      }
    }
    data = this.data;
    ready = false;
    taken = true;
    return data;
  }
}

...

In this example, both methods store() and load() are marked as synchronized. When threads are synchronized, only one will be run at a time. If a thread is in the middle of executing store(int i) when another thread calls load(), the second thread waits until the first one is done executing store(int i) before it gets to run load(). This synchronization allows us to preserve the consistency of the Producer/Consumer program. And the best part is that all of this locking and waiting is handled by Java; it's transparent to the programmer.

Unfortunately, the code above contains a serious problem. The problem will occur when one thread will engage the busy-wait loop, still owning the monitor. The other thread will never be able to execute its code because it can not acquire the monitor. The two threads are in a deadlock: one of them waits for the value to change while blocking the other the access to change it.

For example if we run this program with the command line:
 

> java ProducerConsumer 2 1 1 5 5 10 1

we will get one iteration of the program and after that it will hang up:
 
Producer 0: 0
        Consumer 0: 0

To solve this problem we have to avoid waiting in a busy loop while being in the monitor. We can do this since synchronized keyword can be used in a special construct to guard arbitrary portions of code not the entire method. In this form the synchronized keyword takes an explicit argument that specifies the object the lock is to be acquired. The Version 3 is a possible solution to avoid deadlocks caused by busy loops in monitors. In this version the synchronized keyword protects only the critical code that needs mutual-exclusion:
 
//Example 17.

//Producer/Consumer example. Version 3.

class MyData3 extends MyData0 {  
  public MyData3(boolean yield) {
    ready = false;
    taken = true;
    this.yield = yield;
  }
  
  public void store(int data) {
    while (!taken) {
      if (yield == true) {
        Thread.yield();
      }
    }
    synchronized (this) {
      this.data = data;
      taken = false;
      ready = true;
    }
  }
  
  public int load() {
    while(!ready) {
      if (yield == true) {
        Thread.yield();
      }
    }
    synchronized (this) {
      ready = false;
      taken = true;
      return this.data;
    }
  }
}

...

However, the problem of the busy-wait loops remains. The busy loops are processor-expensive and might cause deadlocks on a non-preemptive systems.

For example if we run this program with the command line:
 

> java ProducerConsumer 3 1 1 5 5 10 0

we will get two iteration of the program and after that it will hang up:
 
Producer 0: 0
        Consumer 0: 0
Producer 0: 1
        Consumer 0: 1

There is a way to avoid the busy-wait loop. The solution is to use the wait() and notify() methods, which are members of the class Object. These methods works as follows: The wait() method makes a thread release the monitor and shifts from the runnable state to the non-runnable state. The thread will stay in a non-runnable state until it is waken up by a call to notify(). When a thread stops waiting, it re-acquires the monitor. The notify() method arbitrarily chooses a thread from those that are waiting and releases it from its wait state. Using wait() and notify() the Version 4 of our Producer/Consumer program can be written as follows:
 
//Example 18.

//Producer/Consumer example. Version 4.

class MyData4 extends MyData0 {
  
  public MyData4() {
    ready = false;
  }
  
  public synchronized void store(int data) {
    while (ready)
      try {
        wait();
      } catch (InterruptedException e) {}  
      this.data = data;
      ready = true;
      notify();
  }
  
  public synchronized int load() {
    int data;
    while(!ready)
      try {
        wait();
      } catch (InterruptedException e) {}  
      data = this.data;
      ready = false;
      notify();
      return data;
  }
}

...
Note that notify() and wait() methods can only be called within synchronized methods.

With the synchronized keyword, we can serialize the execution of complete methods and blocks of code. The wait() and notify() methods of the Object class extend this capability. Every object in Java is a subclass of Object, so every object inherits these methods. By using wait() and notify(), a thread can give up its hold on a lock at an arbitrary point, and then wait for another thread to give it back before continuing. All of the coordinated activity still happens inside of synchronized blocks, and still only one thread is executing at a given time.

By executing wait() from a synchronized block, a thread gives up its hold on the lock and goes to sleep. A thread might do this if it needs to wait for something to happen in another part of the application. Later, when the necessary event happens, the thread that is running it calls notify() from a block synchronized on the same object. Now the first thread wakes up and begins trying to acquire the lock again.

For each call to notify(), Java wakes up just one method that is asleep in a wait() call. If there are multiple threads waiting, Java picks the first thread on a first-in, first-out basis. The Object class also provides a notifyAll() call to wake up all waiting threads. In most cases, you'll probably want to use notifyAll() rather than notify().

Often, the waiter thread is waiting for a particular condition to change and in this case it is preferable to wait in a loop like the following:
 
... 
while (condition != true) 
    wait(); 
... 

Other synchronized threads call notify() or notifyAll() when they have modified the environment so that waiter can check the condition again. This is the a better alternative to polling and sleeping.

Exercises

  1. Study and try all the examples presented this document.
  2. Load the Threads Synchronization Applet and run the examples presented above from this applet.
  3. Write a multithreaded program to illustrate the interaction between two threads: a Producer and a Consumer. A producer thread creates messages and places them into a queue, while a consumer reads them out and displays them. The queue must have a fixed length. To make things realistic, you have to allow the consumer and the producer threads to run with random delays in their loops. For example, the consumer thread may be lazy and run much slower than the producer. This means that the Producer has to stop and wait occasionally for Consumer to put a new message in the queue.

Useful links and credits:

  1. Exploring Java: Chapter 6, Threads
  2. http://www.cs.technion.ac.il/~assaf/publications/parjava.doc.gz

Last Revised:

Back to Concurrent Programming Page