CSC352: Java Threads and Synchronization Examples

--D. Thiebaut (talk) 21:12, 4 September 2013 (EDT)

---

A Badly Written (and Flawed) Multithreaded Computation of Pi

Note: we have removed the function that computes 1/1+x^2 to simplify the code. The correct output of the program is simply 2,000,000 in all cases.

/*
 * 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

sum = 180612836
Execution time: 19 ms

Note that the sum should really be 200000000, as both threads increment sum 100000000 times. The result is certainly incorrect.

Note also that the execution time is quite fast: 19 ms.

A Synchronized Version of the Same Program

We decide to put the statement that increments the variable sum into a function, and ask Java to synchronize around the function, i.e. make sure than only one thread at a time runs through this function. In other word, the synchronized function becomes atomic for threads.

package DT;

public class SynchronizedThreadExample {

	int sum = 0;
	Integer lock =0;
	
	//SynchronizedThreadExample() {
	//	sum = 0;
        //        lock = new Integer( 0 );
	//}
	
	class PiThreadGood extends Thread {
		private int N;			// the total number of samples/iterations 

		public PiThreadGood( 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++ )
				synchronized( lock ) {
					sum++;
				}
		}
	}
	
	
	public void process( int 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) {
		int N = 100000000;
		SynchronizedThreadExample U = new SynchronizedThreadExample();
		U.process( N );
	}

}

Output

sum = 200000000
Execution time: 8448 ms

Note that the result is now correct. However the execution time is 400 longer!

A second way of synchronizing the threaded computation

This time, instead of creating a synchronized method (by the way, the synchronized method should not be one of the thread's method, but a method outside the inherited thread class), we synchronize on an object global to the threads and the main program. This object cannot be a simple type (such as int), but a real object (e.g. Integer).

package DT;

public class SynchronizedThreadExample2 {

	static int sum = 0;
	
	class PiThreadGood extends Thread {
		private int N;			// the total number of samples/iterations 

		public PiThreadGood( 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++ )
				incrementSum();
		}
	}
	
	private synchronized void incrementSum() {
		sum++;
	}
	
	public void process( int 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) {
		int N = 100000000;
		SynchronizedThreadExample2 U = new SynchronizedThreadExample2();
		U.process( N );
	}

}

Output

sum = 200000000
Execution time: 8620 ms
 

Similar behavior as the first version. The synchronization code definitely add a serious overhead to the computation. Sometimes it is a necessary solution for a problem. In other cases, such as in the computation of Pi, we can find an approach that is safe but does not require synchronization.

A Third Synchronized Version of the Same Program

Similar to the first synchronized solution, but this time using Objects instead of Integers.

package DT;

public class SynchronizedThreadExample3 {

	int sum = 0;
	Object lock;
	
	SynchronizedThreadExample3() {
		sum = 0;
                lock = new Object();
	}
	
	class PiThreadGood extends Thread {
		private int N;			// the total number of samples/iterations 

		public PiThreadGood( 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++ )
				synchronized( lock ) {
					sum++;
				}
		}
	}
	
	
	public void process( int 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) {
		int N = 100000000;
		SynchronizedThreadExample U = new SynchronizedThreadExample();
		U.process( N );
	}

}

Output

sum = 200000000
Execution time: 6666 ms

Note that the result is again correct. However the execution time is still very long.

Creating an Array of Threads

In this example we pass the number N of iterations to the application, as well as the number of threads desired. Typical use of the application:

javac DT/SynchronizedThreadExample4.java 
java DT.SynchronizedThreadExample4 100000000 10 

Source Code

/*
 * SynchronizedThreadExample4.java
 * D. Thiebaut
 * A programmable multithreaded loop-runner.  Note: this is NOT the best way to do what 
 * we're doing.   This is just a simple example of how several threads could increment a global
 * variable sum.   The better approach would be to have all the threads increment their own 
 * local sum variable, and add it to the global AT THE END of the computation.   This would also
 * require synchronization, but the threads would have to synchronize only once, instead of 
 * every time through the loop as they are doing here.
 */
package DT;

import java.util.ArrayList;

public class SynchronizedThreadExample4 {

    int sum;
    Object lock;
    int noThreads = 2;

    class PiThread extends Thread {
        private int N;                  // the total number of samples/iterations 
        
        public PiThread( int Id, int N ) {
            super( "Thread-"+Id ); // give a name to the thread
            this.N          = N;
        }
        
        @Override
        public void run() {
        	System.out.println( getName() + " started!" );
            for ( int i=0; i<N; i++ ) 
                synchronized( lock ) {
                    sum ++;
                }
            System.out.println( getName() + " done!" );
        }
    }

    SynchronizedThreadExample4() {
        sum = 0;
        lock = new Object();
    }

    public void process( int N, int noThreads ) {
        
        ArrayList<PiThread> threads = new ArrayList<PiThread>();

        //--- create and start threads ---
        int samples = 0;
        for ( int t=0; t<noThreads; t++ ) {
            //--- assign N/noThreads sample to all but the last thread, which receives what is left over ---
            PiThread T = new PiThread( t, (t==noThreads-1)? N-samples: N/noThreads );

            //--- keep track of the thread
            threads.add( T );

            //--- start it ---
            T.start();

            //--- keep track of how many samples we've given out so far ---
            samples += N/noThreads;
        }
        
        //--- wait till ALL the threads finish ---
        for ( PiThread T : threads ) 
            try {
                T.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }        
    }
    
    public static void main(String[] args) {
    	long startTime = System.currentTimeMillis();

    	int N = 10000000;
        int   noThreads  = 8;
        
        if ( args.length >= 1 ) N = Integer.parseInt( args[0] );
        if ( args.length >=2 ) noThreads = Integer.parseInt( args[1] );

        SynchronizedThreadExample4 S4 = new SynchronizedThreadExample4();
        S4.process( N, noThreads );

        //--- output result in columnar fashion for easy copy/paste into spreadsheet ---
        long endTime = System.currentTimeMillis();
        System.out.println( S4.sum + " " + noThreads + " " + (endTime-startTime) );
    }
    
}

Output

java DT.SynchronizedThreadExample4 100000000 10
Thread-1 started!
Thread-2 started!
Thread-3 started!
Thread-4 started!
Thread-5 started!
Thread-6 started!
Thread-7 started!
Thread-8 started!
Thread-9 started!
Thread-1 done!
Thread-6 done!
Thread-4 done!
Thread-9 done!
Thread-2 done!
Thread-8 done!
Thread-0 done!
Thread-5 done!
Thread-3 done!
Thread-7 done!
100000000 10 5204

A Bash file to run the program automatically multiple times

This assumes that you are working in a terminal/shell window. In this case we can create a script that will automatically run our java program multiple times, giving it a different number of threads every time. This is the way it would look like when we run it (the user input is in bold):

[09:30:08] ~/public_html/classes/352/multithread$: ./runSyncho4.sh 
100000000 2 1390
100000000 3 1673
100000000 4 1776
100000000 5 1957
100000000 6 1929
100000000 7 2074
100000000 8 2008
100000000 9 2124
100000000 10 2039
100000000 11 2116
100000000 12 2084
100000000 13 2072
100000000 14 2074
100000000 15 2079
100000000 16 2140
Done!
[beowulf]
[09:30:41] ~/public_html/classes/352/multithread$:

The code for the script can be created with emacs or your favorite text editor. Here it is:

#! /bin/bash
# runSynchro4.sh
# D. Thiebaut
# runs the java application synchronizedThreadExample4.java 
# for different number of threads
#

for t in 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ; do
    java DT.SynchronizedThreadExample4 100000000 $t
done

echo "Done!"

The first line is required. It indicates which Linux shell to use in order to decode the rest of the script. Bash is very popular with programmers, and is recommended. All the other lines with # signs at the beginning are comments. The for loop in bash defines a variable, here t, and all the values that it must take. Here it's all the values between 2 and 16 (we don't do 1, which can be interesting as a test-case, but if we want to run with 1 thread, especially if we want to measure the speedup as a function of the number of threads, we need to write a non threaded application.
To make the script executable, use the Linux command chmod:

chmod a+x runSynchro4.sh

which specifies that all users (you, in your group, and all the users on beowulf) can execute this script.

Output

To run the script, make sure you are in the same directory where it resides, and type:

./runSynchro4.sh

and the for-loop will run your program and give it 100000000 as the value of N, and 2 to 16 as the number of threads. Here's the output for a second run of the script. Note that the times are different, probably because the second time more users were using beowulf.

./runSyncho4.sh 
100000000 2 3186
100000000 3 3719
100000000 4 3966
100000000 5 3827
100000000 6 4076
100000000 7 3999
100000000 8 4301
100000000 9 4506
100000000 10 4207
100000000 11 4508
100000000 12 4337
100000000 13 4483
100000000 14 4413
100000000 15 4412
100000000 16 4415
Done!