1CMSC330Multithreading2• Description – Multiple processing units (multiprocessor)– From single microprocessor to large compute clusters– Can perform multiple tasks in parallel simultaneously106K processor IBM BlueGene/L32 processor Pentium XeonIntel Core 2 Quad 66003Computation AbstractionsCPU 1 CPU 2p3p1 p2 p4t1t2t1t2t3t1t4t5A computerProcessesThreads4Processes vs. Threadsint x;foo() {…x…}int x;foo() {…x…}int x;foo() {…x…}foo() {…x…}Processes do notshare dataThreads share datawithin a process5So, What Is a Thread?• Conceptually– Parallel computation occurring within a process• Implementation view– A program counter and a stack– Heap and static area are shared among all threads• All programs have at least one thread (main)– Child threads are forked, and then join with main thread6Programming Threads• Thread creation is inexpensive• Threads reside on same physical processor• Threads share memory, resources– Except for local thread variables • Shared-memory programming paradigm– Threads communicate via shared data– Synchronization used to avoid data races• Limited scalability (10’s of threads)7Programming Processes• Process creation is expensive– Request to operating system• Processes may reside on separate processors• Processes do not share memory• Message-passing programming paradigm– Messages using I/O streams, sockets, network, files• Processes must cooperate to communicate– Actions performed to send and receive data• Highly scalable (1000’s of processors)8Java Threads Review (from CMSC 132)• Thread class & Runnable interface– Used to create / manipulate threads• Run-time scheduler– Preemptive / non-premptive– Thread states (new, runnable, blocked, dead)• Data race– Concurrent accesses to same shared object• Where at least one access is a write– Result may change depending on thread schedule– Very difficult to detect & correct9Java Threads Review (cont.)• Synchronization– Locks ensure exclusive access• Lock associated w/ every Java object– Use synchronized keyword to acquire lock• Code blocks – synchronized (o) { … }// lock for Object o• Methods – synchronized foo( ) { … } // lock for this– Thread blocks when trying to acquire locked lock• Thread returns when lock is finally acquired• May deadlock if threads try to acquire each other’s lock10Concurrency• A concurrent program– Program with multiple threads that may be active at the same time• Might run on one CPU (multi-tasking)– The CPU alternates between running different threads– The scheduler takes care of the details• Switching between threads might happen at any time• Might run in parallel on a multiprocessor machine– May have multiple threads per CPU11Concurrency and Shared Data• Concurrency is easy if threads don’t interact– Each thread does its own thing, ignoring other threads– Typically, however, threads need to communicate with each other• In multithreaded programs, communication is achieved by sharing data– In Java, different threads may access the heap simultaneously– But the scheduler might interleave threads arbitrarily– Problems can occur if we’re not careful12Data Race• Definition– Concurrent accesses to same shared variable, where at least one access is a write• Properties– Order of accesses may change result of program– May cause intermittent errors, very hard to debug13Data Race Examplepublic class Example extends Thread {private static intcnt = 0; // shared statepublic void run() {int y = cnt;cnt = y + 1;}public static void main(String args[]) {Thread t1 = new Example();Thread t2 = new Example();t1.start();t2.start();}}14Data Race Examplestatic int cnt = 0;t1.run() {int y = cnt;cnt = y + 1;}t2.run() {int y = cnt;cnt = y + 1;}cnt = 0Start: both threads ready torun. Each will increment theglobal cnt. Shared state15Data Race Examplestatic int cnt = 0;t1.run() {int y = cnt;cnt = y + 1;}t2.run() {int y = cnt;cnt = y + 1;}cnt = 0T1 executes, grabbingthe global counter value intoits own y.Shared statey = 016Data Race Examplestatic int cnt = 0;t1.run() {int y = cnt;cnt = y + 1;}t2.run() {int y = cnt;cnt = y + 1;}cnt = 1T1 executes again, storing itsvalue of y + 1 into the counter.Shared statey = 017Data Race Examplestatic int cnt = 0;t1.run() {int y = cnt;cnt = y + 1;}t2.run() {int y = cnt;cnt = y + 1;}cnt = 1T1 finishes. T2 executes, grabbing the globalcounter value into its own y.Shared statey = 0y = 118Data Race Examplestatic int cnt = 0;t1.run() {int y = cnt;cnt = y + 1;}t2.run() {int y = cnt;cnt = y + 1;}cnt = 2T2 executes, storing itsincremented cnt value intothe global counter.Shared statey = 0y = 119Data Race Example – 2ndTrystatic int cnt = 0;t1.run() {int y = cnt;cnt = y + 1;}t2.run() {int y = cnt;cnt = y + 1;}cnt = 0Start: both threads ready torun. Each will increment theglobal count. Shared state20Data Race Example – 2ndTrystatic int cnt = 0;t1.run() {int y = cnt;cnt = y + 1;}t2.run() {int y = cnt;cnt = y + 1;}cnt = 0T1 executes, grabbingthe global counter value intoits own y.Shared statey = 021static int cnt = 0;t1.run() {int y = cnt;cnt = y + 1;}t2.run() {int y = cnt;cnt = y + 1;}cnt = 0T1 is preempted. T2executes, grabbing the globalcounter value into its own y.Shared statey = 0y = 022static int cnt = 0;t1.run() {int y = cnt;cnt = y + 1;}t2.run() {int y = cnt;cnt = y + 1;}cnt = 1T2 executes, storing theincremented cnt value.Shared statey = 0y = 023static int cnt = 0;t1.run() {int y = cnt;cnt = y + 1;}t2.run() {int y = cnt;cnt = y + 1;}cnt = 1T2 completes. T1executes again, storing theincremented original countervalue (1) rather than what theincremented updated valuewould have been (2)!Shared statey = 0y = 024What Happened?• Different schedules led to different outcomes– This is a data race or race condition• A thread was preempted in the middle of an operation– Reading and writing cnt was supposed to be atomic• Execute with no interference from other threads– But the schedule (interleaving of threads) which was chosen allowed atomicity to be violated– These bugs can be extremely hard to reproduce, and so hard to debug• Depends on what scheduler chose to do, which is hard to predict25Question• If instead ofint y = cnt;cnt = y+1;• We had written– cnt++;• Would the result be any different?• Answer: NO!– Don’t depend on your intuition about atomicity26What’s Wrong with the Following?• Threads
View Full Document
Unlocking...