Week 6Concurrent Programming: ThreadsCS 180Sunil PrabhakarDepartment of Computer Science Purdue UniversityAnnouncementsExam 1 October 5 6:30 pm -- 7:30 pm MTHW 210Topics: everything upto last week (Exception handling)Project 2Due September 30th, 9:00pm2ObjectivesThis week we will get introduced to concurrent programmingCreating a new thread of executionWaiting for threads to terminateThread states and schedulingsleep() and yield()Simple synchronization among threads3One-track mind?Often, in real life we do multiple tasks at the same timeDoing the laundryMaking a pot of coffeeThis is more efficient.Our programs thus far have had a single track (thread) of executionat any point in time, there is only one statement being executednot always efficient -- can stall (e.g., user input)4Multiple concurrent tasksConsider a game program that has to repeatedly redraw the sceneplay the game, record scores, ask the user if they want to play again.We don’t want to stop redrawing the scene while waiting for the user input.Solution: perform both tasks at the same time (concurrently) 5Multiple cores and processorsDue to the recent hardware trends, modern computers have multiple CPUs (cores or processors)If there is only a single thread of execution, only one CPU is used for our program.How do we exploit these other CPUs?Consider the initialization of a large arraysearching for an item in a large arraySplit array into pieces and initialize (search) each piece concurrently.6Game: sequential version7initializeGame();redrawScreen();boolean done=false;while(!done) {done = processNextMove();redrawScreen();updateScores();} terminateGame();initializeGame();redrawScreen();done = processNextMove();redrawScreen();updateScores();done?terminateGame();Screen frozen while waiting for user input.Game: concurrent version8initializeGame();redrawScreen();done = processNextMove();updateScores();terminateGame();Note: separate tasks (threads).No freezingdone?Array: sequential version9final int SIZE = 1000000;double[] rand = new double[SIZE];for(int i=0;i<SIZE;i++)rand[i]= Math.random();i=0;rand[i]=Math.random();i++i<SIZE?Only one thread -- may take long time;next statementArray: concurrent version10i=0;rand[i]=Math.random();i++i<mid?With concurrent execution -- may be twice as fast!i=mid;rand[i]=Math.random();j++j<SIZE?mid=SIZE/2;next statementNeed to wait for both threads before continuing.Motivation for concurrencyNeed for asynchronyneed to perform separate tasks e.g., game examplepotential for increased speed with multiple CPUs/corese.g, matrix exampleAchieving these goals is not straight-forward11Concurrent processingHow do we create a separate thread of execution?The Thread class provides a facility for creating separate threads.Declare a class to be a descendant of ThreadOverride the run() method to perform the necessary task(s) for the new threadWhen the start() method is called, the thread starts executing concurrently12Game: concurrent version13public class Game extends Thread{public static void main(String[] args){Game game = new Game();game.playGame();}public void playGame(){boolean done=false; initializeGame();this.start();while(!done) {done = processNextMove();updateScores();} terminateGame();}public void run(){while(true)redrawScreen();}}Game: concurrent version14public class Game extends Thread{public static void main(String[] args){Game game = new Game();game.playGame();}public void playGame(){boolean done=false; initializeGame();this.start();while(!done) {done = processNextMove();updateScores();} terminateGame();}public void run(){while(true)redrawScreen();}}Array: concurrent version15public class ProcessArray {static final int SIZE = 1000000;static int[] data = new int[SIZE];public static void main(String[] args){int mid = SIZE/2;InitArray thread1 = new InitArray(0,mid, data);InitArray thread2 = new InitArray(mid, SIZE, data);thread1.start();thread2.start();...}}public class InitArray extends Thread {int start, end;int array[];public InitArray(int from, int to, int[] array){start = from;end = to;this.array = array;}public void run(){for(int i=start;i<end;i++)array[i]= Math.random();}}Array: concurrent version16public class ProcessArray {static final int SIZE = 1000000;static int[] data = new int[SIZE];public static void main(String[] args){int mid = SIZE/2;InitArray thread1 = new InitArray(0,mid, data);InitArray thread2 = new InitArray(mid, SIZE, data);thread1.start();thread2.start();...}}public class InitArray extends Thread {int start, end;int array[];public InitArray(int from, int to, int[] array){start = from;end = to;this.array = array;}public void run(){for(int i=start;i<end;i++)array[i]= Math.random();}}Rejoining threadsIn the last example, it is necessary to wait for both threads to finish before moving on.This is achieved by calling the join() methodthe thread that calls join is suspended until the thread on which it is called terminates.this method can throw the (checked) InterruptedException so we should catch this exception17Array: concurrent version 218public class ProcessArray {static final int SIZE = 1000000;static int[] odd = new int[SIZE];public static void main(String[] args){int mid = SIZE/2;InitArray thread1 = new InitArray(0,mid);InitArray thread2 = new InitArray(mid, SIZE);thread1.start();thread2.start();try{thread1.join();thread2.join();} catch (InterruptedException e){System.out.println(“Error in thread”);}. . . }}public class InitArray extends Thread {int start, end;int array[];public InitArray(int from, int to, int[] array){start = from;end = to;this.array = array;}public void run(){for(int i=start;i<end;i++)array[i]= Math.random();}}The join() methodA call to the join method blocks (i.e., does not return) until the thread on which it is called terminatesreturns from its run() method, orpropagates an exception from run()While being blocked, the calling thread may get interrupted which is why the join method throws the exception.Do not use the stop() method to stop a thread -- deprecated.19SpeedupTwo key reasons for concurrency:liveness (e.g., game keeps redrawing screen)speedup (with more cores, programs run faster)Speedup can be measured using the System class methods:public static long currentTimeMillis()time elapsed since 1/1/1970 12:00am, in mspublic static long nanoTime()current value of