Week 7Concurrent Programming: Thread SynchronizationCS 180Sunil PrabhakarDepartment of Computer Science Purdue UniversityTuesday, December 8, 2009AnnouncementsExam 1 tonight 6:30 pm - 7:30 pmMTHW 2102Tuesday, December 8, 2009OutcomesUnderstand race conditionsCritical sections and mutual exclusionSynchronization mechanismsynchronized methods, block of codewait() and notify()Understand potential problemsbusy waitingdeadlocklivelock3Tuesday, December 8, 2009Thread SchedulingRememberOnce a thread is runnable it can be scheduled at any timeIt is hard to predict the actual orderingWith multiple threads, we must ensure that any possible interleaving of threads would still be a correct execution4Tuesday, December 8, 2009Race ConditionsIf the result of a computation changes depending upon the actual ordering of threads we call it a race condition.Can occur even with very simple concurrent programs.Consider a program that simply increments a single variable, count 100000 timesthe task is divided among multiple threads5Tuesday, December 8, 2009Race Example6public class RaceCondition extends Thread {private static int counter = 0;public static final int THREADS = 4;public static final int COUNT = 10000000; public static void main(String[] args){RaceCondition[] threads = new RaceCondition[THREADS];for(int i=0;i<THREADS;i++) {threads[i] = new RaceCondition();threads[i].start();}try{for(int i=0;i<THREADS;i++)threads[i].join();} catch (InterruptedException e) {e.printStackTrace();}System.out.println(“Counter: “ + counter);}public void run(){for(int i=0;i<COUNT/THREADS;i++)counter++;}}Tuesday, December 8, 2009RaceWithout multiple threads, always correct.With multiple threads, often incorrect!Why?multiple threads modifying the same valuecounter++ is not atomicAtomic operationsA java statement translates to multiple machine level statementsthe thread can be swapped in the middle of these machine level statements7Tuesday, December 8, 2009CPUThe memory hierarchy8ALUCacheCache (MB)RegistersMain Memory (GB)SpeedSizeCostTuesday, December 8, 2009Multi Core possibility9Cache (MB)CoreALUCacheRegistersMain Memory (GB)CoreALUCacheRegistersCPUTuesday, December 8, 2009CPUMulti Core possibility 210Cache (MB)Main Memory (GB)CoreALURegistersCoreALURegistersTuesday, December 8, 2009CPUMulti CPU possibility11CPUALUCacheRegistersMain Memory (GB)ALUCacheRegistersCache (MB)Cache (MB)ALUCacheRegistersProgram DataTuesday, December 8, 2009Atomic operations and CachingData is operated on in ALUsregister = count;register++;count = register;Thus if a thread is swapped out just before the last statement, and another thread swapped in, then we have a “lost update”The memory hierarchy caches data values.If multiple threads are using some data, it gets copied into multiple cachesthis can cause different threads to not see all changes made by other threads!12Tuesday, December 8, 2009Shared mutable stateHow do we ensure correct behavior?Many problems of synchronization can be traced to data that is concurrently read and written by multiple threadsshared mutable stateif no thread writes -- no problemsFor example, the variable count is shared mutable state.Only one thread should modify at a given time, and no thread should read the value during this time.13Tuesday, December 8, 2009Critical SectionA section of code that should not be accessed by multiple threads concurrentlyWe need to guarantee mutual exclusion in these sectionsJava solution:use a lock that only one thread holds at a timealso called a monitorany object can be locked14Tuesday, December 8, 2009Synchronized The synchronized keyword can be used to declare a method or block of code as a critical sectioni.e., only one thread can be executing any statements in that method or block of code.15public synchronized int methodA(){. . .//Critical section }public int methodA(){. . .synchronized (someObject) {. . . //Critical section}}Tuesday, December 8, 2009Method vs. block of codeWhen synchronized is used with a block of code, we explicitly specify what object should be used for locking;can arbitrarily limit the critical sectioncan have independent locks for different code.A synchronized method implicitly locks the object (this) on which the method is calledthe class, in the case of static methods16Tuesday, December 8, 2009(No) Race Condition17public class NoRaceCondition extends Thread {private static int counter = 0;public static final int THREADS = 4;public static Object lock = new Object();public static final int COUNT = 1000000; public static void main(String[] args){NoRaceCondition[] threads = new NoRaceCondition[THREADS];for(int i=0;i<THREADS;i++) {threads[i] = new NoRaceCondition();threads[i].start();}try{for(int i=0;i<THREADS;i++)threads[i].join();} catch (InterruptedException e) {e.printStackTrace();}System.out.println(“Counter: “ + counter);}public void run(){for(int i=0;i<COUNT/THREADS;i++){synchronized(NoRaceCondition.lock){counter++;}}}}Note: lock is static.Note: not entire method or for loop!Tuesday, December 8, 2009SynchronizationAny code that is synchronized can only be executed by a thread that holds the appropriate lockOnly one thread can hold the lock for a given objectAny changes made in a critical section will be visible to all threads once they get the lock (ensured by Java)18Tuesday, December 8, 2009AnnouncementsNo class on MondayNo labs next week19Tuesday, December 8, 2009Producer-ConsumerA very common scenarioa producer process creates dataa consumer process processes data (and deletes it)e.g., networking, unix pipes, device driversA shared data structure (buffer) is used to hold data before processinglimited sizeif empty -- consumer waitsif full -- produce waits20Tuesday, December 8, 200921import java.util.*;public class ProducerConsumer extends Thread{ private static Buffer buffer = new Buffer(); private boolean isConsumer;public ProducerConsumer(boolean isC){isConsumer=isC;}public static void main ( String[] args ) { ProducerConsumer consumer = new ProducerConsumer(true);ProducerConsumer producer = new ProducerConsumer(false);consumer.start();producer.start();try{consumer.join();producer.join();} catch (InterruptedException e) {e.printStackTrace(); }}// run method}Producer-ConsumerTuesday, December 8, 200922public void