The property of a thread to execute in parallel with the application's main thread or with other threads is the main feature of the Java 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 notion of correct functioning in concurrent and parallel programming means avoiding conflicts of simultaneously performing by several threads same operation which could not be performed in parallel, like writing in a buffer, modifying a common variable, etc. The fragments of program code which perform such operations are called critical sections. In this context the synchronization means that a thread must wait for another thread to leave the critical section, if it has already entered this section, and to enter into this section using some security measures.
To show a situation when the synchronization is strictly necessary consider the following program:
//Example 12.
public class CounterThread extends Thread {
Counter c;
public static void main(String[] args) {
Counter c = new Counter();
CounterThread ct1 = new CounterThread(c);
CounterThread ct2 = new CounterThread(c);
ct1.start();
ct2.start();
try{
ct1.join();
ct2.join();
} catch (InterruptedException e) {System.out.println("Error during join");}
System.out.println("The variable i= "+c.get()+", the expected value i= 20");
}
public CounterThread(Counter c) {
this.c = c;
}
public void run() {
c.count();
}
}
class Counter {
int i = 0;
public void count() {
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){
try{
Thread.sleep((int) (Math.random()*5));
} catch (InterruptedException e) {System.out.println("Error during sleep");}
return n+1;
}
}
This program uses two threads to increment a variable of the same object Counter, which has three methods:
Since two threads call the method count() which increments 10 times the variable i one can expect that the resulting value of the variable will be 20, but different runs of the programs will print different values which are different of 20, as presented bellow:
The variable i= 11, the expected value i= 20 The variable i= 14, the expected value i= 20 The variable i= 11, the expected value i= 20 The variable i= 10, the expected value i= 20 The variable i= 13, the expected value i= 20 The variable i= 13, the expected value i= 20 The variable i= 12, the expected value i= 20 The variable i= 11, the expected value i= 20 The variable i= 14, the expected value i= 20
Why this programs prints different results ?
The answer comes from the fact that every thread has a life of its own. Normally, a thread goes about its business without any regard for what other threads in the application are doing. Threads may be time-sliced, which means they can run in arbitrary spurts and bursts as directed by the operating system.
In our case two threads use the same object to increment a variable, that is they modify the value of the same variable. But this operation should not be performed simultaneously by different processes, that is this operation is a critical section. This program however imposes no restriction for the two processes do the incrementation simultaneously. In result, the output of the program is unpredictably.
This page is about synchronizing the activities of two or more threads, so that they can work together and not conflict in their use of the same objects.
To introduce systematically the Java threads synchronization techniques consider the Producer/Consumer example, proposed in http://www.cs.technion.ac.il/~assaf/publications/parjava.doc.gz. We modified this example to facilitate the practical experimentation of the analyzed synchronization ideas.
The example consists of a class MyData0 that stores an integer value and of two threads of the classes Producer and Consumer. The Producer writes in an infinite loop consecutive integer values into the MyData0 object and the Consumer reads in an infinite loop these values. The Producer and Consumer threads are created and initialized in the ProducerConsumerDriver class.
The task is to synchronize the Producer and the Consumer so that the values will not be lost when the Producer performs two consecutive writings, and the values will not be duplicated when the Consumer will performs to consecutive readings.
Consider first the first Version of this example without any 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 ProducerConsumerDriver
{
public static void main (String[] argv)
{
MyData0 data;
Thread Producers[];
Thread Consumers[];
int ProducersNumber;
int ConsumersNumber;
int producersPriority;
int consumersPriority;
int interval;
boolean Yield;
if (argv.length < 7 ) {
System.out.print("Usage: \n> java ProducerConsumerDriver <dataObject> ");
System.out.print("<NumberOfProducers> <NumberOfConsumers> ");
System.out.println("<ProducersPriority> <ConsumersPriority>");
System.out.println("<SleepInterval> <YieldFlag> ");
return;
}
if (Integer.valueOf(argv[6]).intValue()==0) Yield=false;
else Yield=true;
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();
};
ProducersNumber=Integer.valueOf(argv[1]).intValue();
ConsumersNumber=Integer.valueOf(argv[2]).intValue();
producersPriority = Integer.valueOf(argv[3]).intValue();
consumersPriority = Integer.valueOf(argv[4]).intValue();
interval=Integer.valueOf(argv[5]).intValue();
Producers = new Thread[ProducersNumber];
Consumers = new Thread[ConsumersNumber];
for(int i=0;i<ProducersNumber;i++){
Producers[i]=new Thread (new Producer(data, i, interval));
Producers[i].setPriority(producersPriority);
Producers[i].start();
}
for(int i=0;i<ConsumersNumber;i++) {
Consumers[i]=new Thread (new Consumer(data, i, interval));
Consumers[i].setPriority(consumersPriority);
Consumers[i].start();
}
}
}
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;
for(i=0;;i++)
{
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;
for(;;)
{
System.out.println(" Consumer "+identifier+": "+data.load());
try
{
Thread.sleep((int) (Math.random()*interval));
} catch (InterruptedException e) {System.out.println("Consumer error\n");}
}
}
}
In this example the boolean variables Ready, Taken and Yield of the class MyData0 are not used. They will be used in the classes derived from this class MyData1, MyData2, MyData3, MyData4 which are stepwise improvements of this example.
The ProdicerConsumerDriver takes as input the following parameters in the command line:
To compile the example Version 0 one has to delete from the driver 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 afterwards be included when the corresponding version will be analyzed.
If we run the example Version 0 on a SPARC/SunOS 5.5 machine with the command line:
> java ProducerConsumerDriver 0 1 1 5 5 10 0which means that we use the parameters:
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 synchronisation 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 as flags to control data access as presented below:
//Example 14.
//Producer/Consumer example. Version 1.
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;
}
}
...
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.
This example 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 on non-preemptive platforms. For example, if we run this example on a Debian GNU Linux 2.0.33 platform with the command line:
> java ProducerConsumerDriver 1 1 1 5 5 10 0we 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 idle 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. For example if we run this program on a Debian GNU Linux 2.0.33 platform with the command line:
> java ProducerConsumerDriver 1 1 1 5 5 10 1we 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 example Version 1 does not work with idle loops only on non-preemptive platforms like:
On preemptive platforms like DEC Alpha/OSF1 V4.0, Windows NT this program works quite well.
The program Version 1 is a possible but not an efficient solution of the Producer/Consumer problem. In this context Java provides a few simple structures for synchronizing the activities of 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, namely an object. In other words, synchronization makes sure only one thread at a time can perform certain activities that manipulate an object. 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 15.
//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 flaw. 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 one from changing it.
For example if we run this program on a DEC Alpha/OSF1 V4.0 machine with the command line:
> java ProducerConsumerDriver 2 1 1 5 5 10 1we will get one iteration of the program and after that it will hang up:
Producer 0: 0
Consumer 0: 0
What we need is to acquire the monitor after waiting for the flag. We can do this since synchronized keyword can be used in a special construct to guard arbitrary blocks of code. In this form it also takes an explicit argument that specifies the object for which it is to acquire a lock. The Version 3 is a possible solution when the synchronized keyword protects only the critical code segment that needs mutual-exclusion:
//Example 16.
//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;
}
}
}
...
One more problem arises in the program above - the busy-wait loops, which are processor-expensive on a preemptive implementation, and might cause deadlock on a non-preemptive one.
For example if we run this program on a DEC Alpha/OSF1 V4.0 machine with the command line:
> java ProducerConsumerDriver 3 1 1 5 5 10 0we 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 17.
//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 civilized alternative to polling and sleeping.