Prof. Saman Amarasinghe, MIT. 1 6.189 IAP 2007 MIT6.189 IAP 2007Lecture 4Concurrent Programming2 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.In this lecture…● Study concurrent programming with an emphasis on correctness Parallel programs have the same correctness issues● Start with a simpler and easier machine/programming model Use Java as a language Use an Abstract Shared Memory Machine Model● Next Lecture.. Use C/C++ primitives (MPI) Study parallel programming with an emphasis on performance Using a distributed memory machine3 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.What is concurrency? ● What is a sequential program? A single thread of control that executes one instruction and when it is finished execute the next logical instruction● What is a concurrent program?  A collection of autonomous sequential threads, executing (logically) in parallel ● The implementation (i.e. execution) of a collection of threads can be:Multiprogramming– Threads multiplex their executions on a single processor.Multiprocessing– Threads multiplex their executions on a multiprocessor or a multicore systemDistributed Processing– Processes multiplex their executions on several different machines4 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.Concurrency and Parallelism● Concurrency is not (only) parallelism● Interleaved Concurrency Logically simultaneous processing Interleaved execution on a single processor● Parallelism Physically simultaneous processing Requires a multiprocessors or a multicore systemATimeBCATimeBC5 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.Account and Bankimport java.util.*;public class Account {String id; String password;int balance;Account(String id, String password, String balance) {this.id = id;this.password = password;this.balance = balance;}boolean is_password(String password) {return password == this.password;}int getbal() {return balance;}void post(int v) {balance = balance + v;}}import java.util.*;public class Bank {HashMap<String, Account> accounts;static Bank theBank = null;private Bank() {accounts = new HashMap<String, Account>();}public static Bank getbank() {if (theBank == null)theBank = new Bank();return theBank;}public Account get(String ID) {return accounts.get(ID);}…}6 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.ATMimport java.util.*;import java.io.*;public class ATM {static Bank bnk;PrintStream out;BufferedReader in;ATM(PrintStream out, BufferedReader in) {this.out = out;this.in = in;}public static void main(String[] args) {bnk = Bank.getbank();BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));ATM atm = new ATM(System.out, stdin);atm.run();}public void run() {while(true) {try {out.print("Account ID > “ );String id = in.readLine();String acc = bnk.get(id);if (acc == null) throw new Exception();out.print("Password > “ );String pass = in.readLine();if (!acc.is_password(pass)) throw new Exception();out.print(“your balance is “ + acc.getbal());out.print("Deposit or withdraw amount > “ );int val = in.read();if (acc.getbal() + val > 0) acc.post(val);elsethrow new Exception();out.print(“your balance is “ + acc.getbal());} catch(Exception e) {out.println("Invalid input, restart“ );}}}}7 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.Activity traceATM Account ID >allyssaPassword >MITROCKSYour account balance is 1000Deposit or Withdraw amount >-200Your account balance is 800Time8 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.ATMimport java.util.*;import java.io.*;public class ATM {static Bank bnk;PrintStream out;BufferedReader in;ATM(PrintStream out, BufferedReader in) {this.out = out;this.in = in;}public static void main(String[] args) {bnk = Bank.getbank();BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));ATM atm = new ATM(System.out, stdin);atm.run();}public void run() {while(true) {try {out.print("Account ID > “ );String id = in.readLine();String acc = bnk.get(id);if (acc == null) throw new Exception();out.print("Password > “ );String pass = in.readLine();if (!acc.is_password(pass)) throw new Exception();out.print(“your balance is “ + acc.getbal());out.print("Deposit or withdraw amount > “);int val = in.read();if (acc.getbal() + val > 0) acc.post(val);elsethrow new Exception();out.print(“your balance is “ + acc.getbal());} catch(Exception e) {out.println("Invalid input, restart“ );}}}}I need to run multiple ATM machines from my program, how do I do that?9 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.Concurrency in Java● Java has a predefined class java.lang.Thread which provides the mechanism by which threads are createdpublic class MyThread extends Thread {public void run() {}}● However to avoid all threads having to be subtypes of Thread, Java also provides a standard interfacepublic interface Runnable {public void run();}● Hence, any class which wishes to express concurrent execution must implement this interface and provide the run method● Threads do not begin their execution until the start method in the Thread class is called10 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.Why use Concurrent Programming?● Natural Application Structure The world is not sequential! Easier to program multiple independent and concurrent activities.● Increased application throughput and responsiveness Not blocking the entire application due to blocking IO● Performance from multiprocessor/multicore hardware Parallel execution● Distributed systems Single application on multiple machines Client/server type or peer-to-peer systems11 6.189 IAP 2007 MITProf. Saman Amarasinghe, MIT.Multiple ATMsimport java.util.*;import java.io.*;public class ATM {static Bank bnk;PrintStream out;BufferedReader in;ATM(PrintStream out, BufferedReader in) {this.out = out;this.in = in;}public static void main(String[] args) {bnk = Bank.getbank();BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));ATM atm = new ATM(System.out, stdin);atm.run();}public void run() {while(true) {try {out.print("Account ID > “ );String id = in.readLine();String acc = bnk.get(id);if (acc == null) throw new Exception();out.print("Password > “ );String pass = in.readLine();if (!acc.is_password(pass)) throw new Exception();out.print(“your balance is “ + acc.getbal());out.print("Deposit or withdraw amount > “ );int val = in.read();if (acc.getbal() + val > 0) acc.post(val);elsethrow new