Difference between revisions of "CSC352: Java Threads and Synchronization Examples"

From dftwiki3
Jump to: navigation, search
(A Synchronized Version of the Same Program)
(A Bash file to run the program automatically multiple times)
 
(11 intermediate revisions by the same user not shown)
Line 3: Line 3:
  
 
=A Badly Written (and Flawed) Multithreaded Computation of Pi=
 
=A Badly Written (and Flawed) Multithreaded Computation of Pi=
 +
<br />
 +
<bluebox>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.
 +
</bluebox>
 +
<br />
 
<br />
 
<br />
 
<source lang="java">
 
<source lang="java">
 +
/*
 +
* 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;
 
package DT;
  
 
public class UnsynchronizedThreadExample {
 
public class UnsynchronizedThreadExample {
  
static int sum = 0;
+
        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 );
 +
    }
 +
 
 +
}
 +
</source>
 +
<br />
 +
==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.
 +
 
 +
<br />
 +
=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.
 +
 
 +
<br />
 +
<source lang="java">
 +
package DT;
 +
 
 +
public class SynchronizedThreadExample {
 +
 
 +
int sum = 0;
 +
Integer lock =0;
 +
 +
//SynchronizedThreadExample() {
 +
// sum = 0;
 +
        //        lock = new Integer( 0 );
 +
//}
 
 
class PiThreadBad extends Thread {
+
class PiThreadGood extends Thread {
 
private int N; // the total number of samples/iterations  
 
private int N; // the total number of samples/iterations  
  
public PiThreadBad( int Id, int N ) {
+
public PiThreadGood( int Id, int N ) {
 
super( "Thread-"+Id ); // give a name to the thread
 
super( "Thread-"+Id ); // give a name to the thread
 
this.N = N;
 
this.N = N;
Line 22: Line 105:
 
public void run() {
 
public void run() {
 
for ( int i=0; i<N; i++ )
 
for ( int i=0; i<N; i++ )
sum ++;
+
synchronized( lock ) {
 +
sum++;
 +
}
 
}
 
}
 
}
 
}
 +
 +
 +
public void process( int N ) {
 +
long startTime = System.currentTimeMillis();
  
public void process( int N ) {
+
PiThreadGood t1 = new PiThreadGood( 0, N );
PiThreadBad t1 = new PiThreadBad( 0, N );
+
PiThreadGood t2 = new PiThreadGood( 1, N );
PiThreadBad t2 = new PiThreadBad( 1, N );
 
 
 
 
//--- start two threads ---
 
//--- start two threads ---
Line 43: Line 131:
 
 
 
System.out.println( "sum = " + sum );
 
System.out.println( "sum = " + sum );
 +
System.out.println( "Execution time: " + (System.currentTimeMillis()-startTime) + " ms" );
 
}
 
}
 
 
 
public static void main(String[] args) {
 
public static void main(String[] args) {
 
int N = 100000000;
 
int N = 100000000;
UnsynchronizedThreadExample U = new UnsynchronizedThreadExample();
+
SynchronizedThreadExample U = new SynchronizedThreadExample();
 
U.process( N );
 
U.process( N );
 
}
 
}
  
 
}
 
}
 +
 
</source>
 
</source>
 
<br />
 
<br />
 
==Output==
 
==Output==
 +
 +
sum = 200000000
 +
Execution time: 8448 ms
 +
 +
Note that the result is now correct.  However the execution time is 400 longer!
  
sum = 180612836
+
<br />
Execution time: 19 ms
+
=A second way of synchronizing the threaded computation=
 
 
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.
 
  
 
<br />
 
<br />
=A Synchronized Version of the Same Program=
+
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).
 
 
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.
 
 
 
 
<br />
 
<br />
 
<source lang="java">
 
<source lang="java">
 +
 
package DT;
 
package DT;
  
public class SynchronizedThreadExample {
+
public class SynchronizedThreadExample2 {
  
int sum = 0;
+
static int sum = 0;
Integer lock=0;
 
 
SynchronizedThreadExample() {
 
sum = 0;
 
}
 
 
 
class PiThreadBad extends Thread {
+
class PiThreadGood extends Thread {
 
private int N; // the total number of samples/iterations  
 
private int N; // the total number of samples/iterations  
  
public PiThreadBad( int Id, int N ) {
+
public PiThreadGood( int Id, int N ) {
 
super( "Thread-"+Id ); // give a name to the thread
 
super( "Thread-"+Id ); // give a name to the thread
 
this.N = N;
 
this.N = N;
Line 92: Line 176:
 
public void run() {
 
public void run() {
 
for ( int i=0; i<N; i++ )
 
for ( int i=0; i<N; i++ )
synchronized( lock ) {
+
incrementSum();
sum++;
 
}
 
 
}
 
}
 
}
 
}
 
 
 +
private synchronized void incrementSum() {
 +
sum++;
 +
}
 
 
 
public void process( int N ) {
 
public void process( int N ) {
 
long startTime = System.currentTimeMillis();
 
long startTime = System.currentTimeMillis();
  
PiThreadBad t1 = new PiThreadBad( 0, N );
+
PiThreadGood t1 = new PiThreadGood( 0, N );
PiThreadBad t2 = new PiThreadBad( 1, N );
+
PiThreadGood t2 = new PiThreadGood( 1, N );
 
 
 
//--- start two threads ---
 
//--- start two threads ---
Line 119: Line 204:
 
System.out.println( "sum = " + sum );
 
System.out.println( "sum = " + sum );
 
System.out.println( "Execution time: " + (System.currentTimeMillis()-startTime) + " ms" );
 
System.out.println( "Execution time: " + (System.currentTimeMillis()-startTime) + " ms" );
 +
 
}
 
}
 
 
 
public static void main(String[] args) {
 
public static void main(String[] args) {
 
int N = 100000000;
 
int N = 100000000;
SynchronizedThreadExample U = new SynchronizedThreadExample();
+
SynchronizedThreadExample2 U = new SynchronizedThreadExample2();
 
U.process( N );
 
U.process( N );
 
}
 
}
Line 131: Line 217:
 
</source>
 
</source>
 
<br />
 
<br />
 +
 
==Output==
 
==Output==
 
   
 
   
 
  sum = 200000000
 
  sum = 200000000
  Execution time: 8448 ms
+
  Execution time: 8620 ms
   
+
 
Note that the result is now correct. However the execution time is 400 longer!
+
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.
  
 
<br />
 
<br />
=A second way of synchronizing the threaded computation of Pi=
+
<br />
 +
 
 +
=A Third Synchronized Version of the Same Program=
 +
 
 +
Similar to the first synchronized solution, but this time using Objects instead of Integers.
  
 
<br />
 
<br />
 
<source lang="java">
 
<source lang="java">
 
 
package DT;
 
package DT;
  
public class SynchronizedThreadExample2 {
+
public class SynchronizedThreadExample3 {
  
static int sum = 0;
+
int sum = 0;
 +
Object lock;
 +
 +
SynchronizedThreadExample3() {
 +
sum = 0;
 +
                lock = new Object();
 +
}
 
 
class PiThreadBad extends Thread {
+
class PiThreadGood extends Thread {
 
private int N; // the total number of samples/iterations  
 
private int N; // the total number of samples/iterations  
  
public PiThreadBad( int Id, int N ) {
+
public PiThreadGood( int Id, int N ) {
 
super( "Thread-"+Id ); // give a name to the thread
 
super( "Thread-"+Id ); // give a name to the thread
 
this.N = N;
 
this.N = N;
Line 161: Line 257:
 
public void run() {
 
public void run() {
 
for ( int i=0; i<N; i++ )
 
for ( int i=0; i<N; i++ )
incrementSum();
+
synchronized( lock ) {
 +
sum++;
 +
}
 
}
 
}
 
}
 
}
 
 
private synchronized void incrementSum() {
 
sum++;
 
}
 
 
 
 
public void process( int N ) {
 
public void process( int N ) {
 
long startTime = System.currentTimeMillis();
 
long startTime = System.currentTimeMillis();
  
PiThreadBad t1 = new PiThreadBad( 0, N );
+
PiThreadGood t1 = new PiThreadGood( 0, N );
PiThreadBad t2 = new PiThreadBad( 1, N );
+
PiThreadGood t2 = new PiThreadGood( 1, N );
 
 
 
//--- start two threads ---
 
//--- start two threads ---
Line 189: Line 284:
 
System.out.println( "sum = " + sum );
 
System.out.println( "sum = " + sum );
 
System.out.println( "Execution time: " + (System.currentTimeMillis()-startTime) + " ms" );
 
System.out.println( "Execution time: " + (System.currentTimeMillis()-startTime) + " ms" );
 
 
}
 
}
 
 
 
public static void main(String[] args) {
 
public static void main(String[] args) {
 
int N = 100000000;
 
int N = 100000000;
SynchronizedThreadExample2 U = new SynchronizedThreadExample2();
+
SynchronizedThreadExample U = new SynchronizedThreadExample();
 
U.process( N );
 
U.process( N );
 
}
 
}
Line 202: Line 296:
 
</source>
 
</source>
 
<br />
 
<br />
 +
==Output==
 +
 +
sum = 200000000
 +
Execution time: 6666 ms
 +
 +
Note that the result is again correct.  However the execution time is still very long.
 +
 +
<br />
 +
=Creating an Array of Threads=
 +
<br />
 +
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:
 +
<br />
 +
javac DT/SynchronizedThreadExample4.java
 +
java DT.SynchronizedThreadExample4 100000000 10
 +
<br />
 +
==Source Code==
 +
<br />
 +
<source lang="java">
 +
/*
 +
* 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) );
 +
    }
 +
   
 +
}
 +
 +
 +
</source>
 +
<br />
 +
 +
==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
 +
 +
<br />
 +
==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$:
 +
<br />
 +
The code for the script can be created with emacs or your favorite text editor.  Here it is:
 +
<br />
 +
<source lang="bash">
 +
#! /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!"
 +
</source>
 +
<br />
 +
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.
 +
<br />
 +
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!
 +
 +
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
[[Category:CSC352]][[Category:Java]]

Latest revision as of 09:45, 11 September 2013

--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!