Lecture 28: ConcurrencyKenneth M. AndersonUniversity of Colorado, BoulderCSCI 4448/5448 — Lecture 28 — 12/03/2009© University of Colorado, 20091Goals for this Lecture• Briefly review concepts behind concurrency in software systems• See examples of how to make use of concurrency in OO systems• Look at some of the problems that occur• Look at one non-OO approach to concurrency that avoids some of the problems2Why worry?• Concurrency is hard and I’ve only ever needed single-threaded programs• Why should I care about it?• Answer: multi-core computers• Growth rates for chip speed are flattening• You can no longer say “lets wait a year and our system will run faster!”• Instead, chips are becoming “wider”• more cores, wider bus (more data at a time), more memory on chip• As chip are not getting faster (the same way they used to), a single-threaded, single process application is not going to see any significant performance gains from new hardware3New Model• Instead, the way in which software will see performance gains with new hardware is if they are designed to get faster the more processors they have available• This is not easy: the computations that an application performs has to be amenable to parallelization (that is, being split up into multiple parts that can be computed separately)• If so, such an application will see noticeable speed improvements as it is put on machines with more and more processors.• Laptops currently have 2-cores, will soon have 4-cores, and for high-end machines Intel has an 80-core beast waiting in the wings• A system written for n-cores could potentially see an 80x speed-up when run on such a machine 45Basics: Single Thread, Single Process, Single MachineMachineProcessThreadData/CodeMachine6Basics: Multiple Thread, Single Process, Single MachineProcessThreadData/CodeThreadMachine7Basics: Single Thread, Multiple Process, Single MachineProcessThreadData/CodeProcessThreadData/CodeProcessThreadData/Code8Basics: Multi-thread, Multi-Process, Single MachineMachineProcessThreadData/CodeThreadProcessThreadData/CodeThreadProcessThreadData/CodeThreadNote: You can have way more than just two threads per process.9Basics: Multi-everythingMachineProcessThreadData/CodeThreadProcessThreadData/CodeThreadProcessThreadData/CodeThreadMachineProcessThreadData/CodeThreadProcessThreadData/CodeThreadProcessThreadData/CodeThreadApplications are Dead! Long Live Applications!10Due to the ability to have multiple threads, multiple processes, and multiple machines work together on a single problem, the notion of an application is changing. It used to be that:ProcessThreadData/CodeApplication ==Now… we might refer to this as “an application”11MachineProcessThreadData/CodeThreadProcessThreadData/CodeThreadProcessThreadData/CodeThreadMachineProcessThreadData/CodeThreadProcessThreadData/CodeThreadProcessThreadData/CodeThreadMachine6Basics: Multiple Thread, Single Process, Single MachineProcessThreadData/CodeThreadFor instance,“Google”Terminology•When we execute a program, we create a process•A sequential program has a single thread of control•A concurrent program has multiple threads of control• A single computer can have multiple processes running at once• If that machine, has a single processor, then the illusion of multiple processes running at once is just that: an illusion• That illusion is maintained by the operating system that coordinates access to the single processor among the various processes•If a machine has more than a single processor, then true parallelism can occur: you can have N processes running simultaneously on a machine with N processors12Another View: Sequential Program321984765main.java foo.javabar.javabaz.javadb.java ui.java13Another View: Concurrent Program32198476531524main.java foo.javabar.javabaz.javadb.java ui.java14The problem with concurrency?32198476531524main.java foo.javabar.javabaz.javadb.java ui.javaThe potential for interactions… two threads hitting the same method at the same time, potentially corrupting a shared data structure15Output for Non Thread-Safe Singleton Code• s9 = Singleton@45d068• s8 = Singleton@45d068• s3 = Singleton@45d068• s6 = Singleton@45d068• s1 = Singleton@45d068• s0 = Singleton@ab50cd• s5 = Singleton@45d068• s4 = Singleton@45d068• s7 = Singleton@45d068• s2 = Singleton@45d068Whoops!Thread 0 created an instance of the Singleton class at memory location ab50cd at the same time that another thread (we don’t know which one) created an additional instance of Singleton at memory location 45d068!16Remember this slide from Lecture 22?(Program on next slide)Program to Test Thread Safetypublic class Creator implements Runnable {12 private int id;34 public Creator(int id) {5 this.id = id;6 }78 public void run() {9 try {10 Thread.sleep(200L);11 } catch (Exception e) {12 }13 Singleton s = Singleton.getInstance();14 System.out.println("s" + id + " = " + s);15 }1617 public static void main(String[] args) {18 Thread[] creators = new Thread[10];19 for (int i = 0; i < 10; i++) {20 creators[i] = new Thread(new Creator(i));21 }22 for (int i = 0; i < 10; i++) {23 creators[i].start();24 }25 }2627}2829Creates a “runnable” object that can be assigned to a thread.When its run, its sleeps for a short time, gets an instance of the Singleton, and prints out its object id.The main routine, creates ten runnable objects, assigns them to ten threads and starts each of the threads17Since we didn’t protect Singleton.getInstance(), this program is not safe.18Concurrency: processes & threads 25©Magee/Kramer 2nd Editionthreads in JavaA Thread class manages a single sequential thread of control.Threads may be created and deleted dynamically.Thread run()MyThread run()The Thread class executes instructions from its methodrun(). The actual code executed depends on theimplementation provided for run() in a derived class.class MyThread extends Thread {public void run() {//......}}Creating a thread object:Thread a = new MyThread();19Concurrency: processes & threads 26©Magee/Kramer 2nd Editionthreads in JavaSince Java does not permit multiple inheritance, we oftenimplement the run() method in a class not derived from Thread butfrom the interface Runnable.Runnablerun()MyRunrun()public interface Runnable {public abstract void run();}class MyRun implements Runnable{public void run()