CSC352 Synchronization and Java Threads
--D. Thiebaut (talk) 14:10, 9 September 2013 (EDT)
This page treats of the concepts of synchronization of parallel programs in general, applied to the Java platform in particular. Note, in all programming examples we have changed the computation to simply be the increment of a global variable sum that is incremented some multiple of 1,000,000 times by both thread. The normal, error-free result of the computation should be a multiple of 2,000,000.
Contents
References
A good source of information for the material presented here is
The programs covered in this page can be found in this page:
- Computing Pi and Synchronization programs
Declaring a Thread in Java
Here is a simple example program that starts one thread only. The thread prints a message, waits one second, prints another message, then stops.
class MyThread extends Thread{ public void run(){ System.out.println( "thread is running..." ); try { Thread.sleep( 1000 ); // 1 sec } catch (InterruptedException ie) { ie.printStackTrace(); } System.out.println( "thread is done..." ); } } public class SimpleThreadDemo { public static void main(String args[]){ // declare a new thread MyThread t1=new MyThread(); // start a new thread t1.start(); // wait for the thread to be done try { t1.join(); } catch (InterruptedException ie) { ie.printStackTrace(); } // Exit System.out.println( "Done!" ); } }
Output
aurora:~/handout> java SimpleThreadDemo thread is running... thread is done... Done! aurora:~/handout>
Passing Arguments to Java Threads
To pass arguments to a thread, we simply need to pass them through the constructor, as illustrated in the example below.
/* SimpleThreadDemoWithArgs.java D. Thiebaut Same as SimpleThreadDemo, but this one illustrates how main can pass arguments to the thread. */ class MyThread extends Thread{ int Id = 0; // The Id of the thread public MyThread( int id ){ Id = id; } public void run(){ System.out.println( "thread "+Id+" is running..." ); try { Thread.sleep( 1000 ); // 1 sec } catch (InterruptedException ie) { ie.printStackTrace(); } System.out.println( "thread "+Id+" is done..." ); } } public class SimpleThreadDemoWithArgs { public static void main(String args[]){ // declare a new thread with Id 33 MyThread t1=new MyThread( 33 ); // start a new thread t1.start(); // wait for the thread to be done try { t1.join(); } catch (InterruptedException ie) { ie.printStackTrace(); } // Exit System.out.println( "Done!" ); } }
Output
aurora:~/handout> java SimpleThreadDemoWithArgs thread 33 is running... thread 33 is done... Done! aurora:~/handout>
It all starts at the Lowest Level: Assembly Language (again)
Let's look at a different parallel computation of Pi. Imagine that the two threads in the ParallelPi program updated a global sum variable by doing something like this?
public void run() {
for ( int i=0; i<N; i++ )
sum ++;
}
where sum is a static variable defined in the thread class. Since only 1 such variable will exist, all the thread objects will have access to just one variable, which plays the role of our global variable. The actual program can be found here.
- Question 1
- Figure out the assembly language for the java statement above
- Question 2
- Assume that main memory is a stack of index cards. One index card is sum. Two people in the class represent two different processors. Their notebook represent their registers. Execute these instructions simultaneously and figure out if there's a way for their simultaneous operation to fail.
- Question 3
- What makes the code fail? What is the processor missing?
- Question 4
- What is a way around the problem, such that two parallel updates of the variable sum will increment it by 2 every time?
First we're going to look at what NOT to do, understand why, and see what tools Java gives us to get around the problem.
A Badly Synchronized Parallel Program
/* * UnsynchronizedThreadExample.java * D. Thiebaut * Undocumented code that computes Pi with 2 threads, but is terribly * flawed in the way it updates the global sum... */ package DT; public class UnsynchronizedThreadExample { static int sum = 0; class PiThreadBad extends Thread { private int N; // the total number of samples/iterations public PiThreadBad( int Id, int N ) { super( "Thread-"+Id ); // give a name to the thread this.N = N; } @Override public void run() { for ( int i=0; i<N; i++ ) sum ++; } } public void process( int N ) { long startTime = System.currentTimeMillis(); PiThreadBad t1 = new PiThreadBad( 0, N ); PiThreadBad t2 = new PiThreadBad( 1, N ); //--- start two threads --- t1.start(); t2.start(); //--- wait till they finish --- try { t1.join(); t2.join(); } catch (InterruptedException e) { e.printStackTrace(); } System.out.println( "sum = " + sum ); System.out.println( "Execution time: " + (System.currentTimeMillis()-startTime) + " ms" ); } public static void main(String[] args) { int N = 100000000; UnsynchronizedThreadExample U = new UnsynchronizedThreadExample(); U.process( N ); } }
Output
java DT.UnsynchronizedThreadExample sum = 198846243 Execution time: 25 ms
Critical Section
A series of instructions that are executed in an atomic fashion.
- Question
- We have seen this before, but just to make sure we all remember this: how can we create a critical section in assembly?
- More challenging question
- What should happen in Java when two threads attempt to modify a shared resource (variable or object). Specifically, what should happen with the thread that is first to grab the resource, and what should happen with the slower thread?
The Concept of a Lock
- Intrinsic Lock = Monitor Lock =Monitor (most common definition)
- In Java each object contains a Lock
- Exclusive access to the object can be performed by acquiring the lock.
- A thread locking an object must release it when it's done updating it.
Example With Locks
/* SynchronizedLockThreadExample.java D. Thiebaut This threaded java code uses locks to serialize access to the shared variable. */ import java.util.concurrent.locks.ReentrantLock; public class SynchronizedLockThreadExample { static long sum = 0; private ReentrantLock lock = new ReentrantLock(); class PiThreadGood extends Thread { private long N; // the total number of samples/iterations public PiThreadGood( int Id, long N ) { super( "Thread-"+Id ); // give a name to the thread this.N = N; } @Override public void run() { for ( long i=0; i<N; i++ ) { lock.lock(); try{ sum++; } finally { lock.unlock(); } } } } public void process( long N ) { long startTime = System.currentTimeMillis(); PiThreadGood t1 = new PiThreadGood( 0, N ); PiThreadGood t2 = new PiThreadGood( 1, N ); //--- start two threads --- t1.start(); t2.start(); //--- wait till they finish --- try { t1.join(); t2.join(); } catch (InterruptedException e) { e.printStackTrace(); } System.out.println( "sum = " + sum ); System.out.println( "Execution time: " + (System.currentTimeMillis()-startTime) + " ms" ); } public static void main(String[] args) { long N = 1000000000l; SynchronizedLockThreadExample S = new SynchronizedLockThreadExample(); S.process( N ); } }
Output
aurora:~/handout> java SynchronizedLockThreadExample sum = 2000000000 Execution time: 14972 ms aurora:~/handout>
Synchronized Sections
Locks allow fine-grain control of shared variables and data structures, but maintaining them correctly in the code requires very careful attention, especially if the locked section calls other functions, and several conditions may exist for releasing the lock.
Fortunately, Java offers a simpler (though less flexible) way of locking whole methods or sections of code with the keyword synchronized.
- The keyword synchronized( ) is used to
- define an object whose lock is going to be used
- define a section of code between { and } that is critical and should be executed in an atomic matter (but atomicity is not actually required any longer... can you see why?)
Example 1
Assume that you create your own list that will contain Strings. You use ArrayList<String> as your basic data structure, name it myList, and add more functionality with additional methods. This list will typically be instantiated as a single object, and shared by several threads that will attempt to add new strings to it in parallel.
public void addNewCustomerMethod( String name ) {
name = name.trim().toUpper();
synchronized( this ) {
myList.add( name );
}
}
Example 2
Assume that you do not need to trim() or change the strings to uppercase, then the whole body of the method is a critical section. In this case you can make the whole method synchronized:
public synchronized void addNewCustomerMethod( String name ) {
myList.add( name );
}
Example 3
In some cases you may have several variables/data structures that you need to modify, but they do not depend on each other, and updating one is a completely independent operation from updating the other. In this case you can create your own locks. This example is take from the Oracle tutorial pages:
public class MsLunch {
private long c1 = 0;
private long c2 = 0;
private Object lock1 = new Object();
private Object lock2 = new Object();
public void inc1() {
synchronized(lock1) {
c1++;
}
}
public void inc2() {
synchronized(lock2) {
c2++;
}
}
}
Challenge 1 |
Modify the flawed program above that computes Pi by using some form of lock. Verify that it outputs the correct value of 2,000,000.
Challenge 2 |
Measure the execution time of your solution. Compare it to the original computation of Pi of a few lectures ago. Comment on your discovery!
|
Challenge 3 |
Modify the program so that the computation returned is actually an approximation of Pi and not 2,000,000. Measure it's speedup as a function of the number of threads N, for N ranging from 1 to 10.
Solutions
You can find solutions to these challenges here.
Some comments and definitions
- When a thread is stopped because of a particular condition that it is waiting on (for example a queue is empty and the thread is designed to pull elements from the queue and process them), then the thead is said to be blocked.
- When a thread is stopped because it has attempted to lock an object but an other thread held the lock, we say that this thread is stalled.
- When a shared object is the object that is most utilized by thread, it is said to be the bottleneck object.
- Liveliness: the ability of a threaded/parallel application to execute in a timely manner. When an application does not present liveliness of operation, it is usually due to one of several potential problems
- Deadlock
- Starvation
- Livelock
- Deadlock: a situation where two or more threads are blocked forever, waiting on each other.
- Starvation: a situation where a thread is unable to get access to a resource and is unable to progress. This is often due to greedy threads.
- Livelock: a situation where threads are not blocked, are running, but are waiting on each other before continuing. This often occurs because a thread my test whether a resource is available or not using a non-blocking function, and will busy itself with other work if the resource is not available.
- The dining philosophers problem, and the associated applet
Important Rule for avoiding deadlocks: If a thread needs several locks to operate, it should try acquiring all of them, one after the other. If it can't acquire one of them, it should release them all, wait some random amount of time, and try again. This will prevent the dining-philosopher potential deadlock.
- Sleep: A thread can sleep for some interval of time using the sleep function
sleep( m ); // where m is some integer number of milliseconds
Note that the operating system is in charge of figuring out how close to m milliseconds the thread actually sleeps. Usually the amount of sleep it is > m ms, never exact to that amount.
- Reentrant Code/Reentrancy: A thread might acquire a lock, do some work on the locked data structure, and call another method that needs to be synchronized as well. Java allows a thread to automatically re-acquire a lock that it holds. This property is called reentrancy of the code.
