CSE332: Data AbstractionsLecture 22: Shared-Memory Concurrency and Mutual ExclusionDan GrossmanSpring 2010Toward sharing resources (memory)Have been studying parallel algorithms using fork-join– Reduce span via parallel tasksAlgorithms all had a very simple structure to avoid race conditions– Each thread had memory “only it accessed”• Example: array sub-range–On fork, “loaned” some of its memory to “forkee” and did not access that memory again until after join on the “forkee”Strategy won’t work well when:– Memory accessed by threads is overlapping or unpredictable– Threads are doing independent tasks needing access to same resources (rather than implementing the same algorithm)Spring 2010 2CSE332: Data AbstractionsConcurrent ProgrammingConcurrency: Allowing simultaneous or interleaved access to shared resources from multiple clientsRequires coordination, particularly synchronization to avoid incorrect simultaneous access: make somebody block– join is not what we want– block until another thread is “done using what we need” not “completely done executing”Even correct concurrent applications are usually highly non-deterministic: how threads are scheduled affects what operations from other threads they see when– non-repeatability complicates testing and debuggingSpring 2010 3CSE332: Data AbstractionsExamplesMultiple threads:1. Processing different bank-account operations– What if 2 threads change the same account at the same time?2. Using a shared cache (e.g., hashtable) of recent files– What if 2 threads insert the same file at the same time?3. Creating a pipeline (think assembly line) with a queue for handing work to next thread in sequence?– What if enqueuer and dequeuer adjust a circular array queue at the same time?Spring 2010 4CSE332: Data AbstractionsWhy threads?Unlike with parallelism, not about implementing algorithms fasterBut threads still useful for:• Code structure for responsiveness– Example: Respond to GUI events in one thread while another thread is performing an expensive computation• Processor utilization (mask I/O latency)– If 1 thread “goes to disk,” have something else to do• Failure isolation– Convenient structure if want to interleave multiple tasks and don’t want an exception in one to stop the otherSpring 2010 5CSE332: Data AbstractionsSharing, againIt is common in concurrent programs that:• Different threads might access the same resources in an unpredictable order or even at about the same time• Program correctness requires that simultaneous access be prevented using synchronization• Simultaneous access is rare– Makes testing difficult– Must be much more disciplined when designing / implementing a concurrent program– Will discuss common idioms known to workSpring 2010 6CSE332: Data AbstractionsCanonical exampleCorrect code in a single-threaded worldSpring 2010 7CSE332: Data Abstractionsclass BankAccount {private int balance = 0;int getBalance() { return balance; }void setBalance(int x) { balance = x; } void withdraw(int amount) {int b = getBalance();if(amount > b)throw new WithdrawTooLargeException();setBalance(b – amount);}… // other operations like deposit, etc.}InterleavingSuppose:– Thread T1 calls x.withdraw(100)– Thread T2 calls y.withdraw(100)If second call starts before first finishes, we say the calls interleave– Could happen even with one processor since a thread can be pre-empted at any point for time-slicingIf x and y refer to different accounts, no problem– “You cook in your kitchen while I cook in mine”–But if x and y alias, possible trouble…Spring 2010 8CSE332: Data AbstractionsA bad interleavingInterleaved withdraw(100) calls on the same account– Assume initial balance 150Spring 2010 9CSE332: Data Abstractionsint b = getBalance();if(amount > b)throw new …;setBalance(b – amount);int b = getBalance();if(amount > b)throw new …;setBalance(b – amount);Thread 1Thread 2Time“Lost withdraw” –unhappy bankIncorrect “fix”It is tempting and almost always wrong to fix a bad interleaving by rearranging or repeating operations, such as:Spring 2010 10CSE332: Data Abstractionsvoid withdraw(int amount) {if(amount > getBalance())throw new WithdrawTooLargeException();// maybe balance changedsetBalance(getBalance() – amount);}This fixes nothing!• Narrows the problem by one statement• (Not even that since the compiler could turn it back into the old version because you didn’t indicate need to synchronize)• And now a negative balance is possible – why?Mutual exclusionThe sane fix: At most one thread withdraws from account A at a time– Exclude other simultaneous operations on A too (e.g., deposit)Called mutual exclusion: One thread doing something with a resource (here: an account) means another thread must wait–a.k.a. critical sections, which technically have other requirementsProgrammer must implement critical sections– “The compiler” has no idea what interleavings should or shouldn’t be allowed in your program– Buy you need language primitives to do it!Spring 2010 11CSE332: Data AbstractionsWrong!Why can’t we implement our own mutual-exclusion protocol?– It’s technically possible under certain assumptions, but won’t work in real languages anywaySpring 2010 12CSE332: Data Abstractionsclass BankAccount {private int balance = 0;private boolean busy = false;void withdraw(int amount) {while(busy) { /* “spin-wait” */ }busy = true;int b = getBalance();if(amount > b)throw new WithdrawTooLargeException();setBalance(b – amount);busy = false;}// deposit would spin on same boolean}Still just moved the problem!Spring 2010 13CSE332: Data Abstractionswhile(busy) { }busy = true;int b = getBalance();if(amount > b)throw new …;setBalance(b – amount);while(busy) { }busy = true;int b = getBalance();if(amount > b)throw new …;setBalance(b – amount);Thread 1Thread 2Time“Lost withdraw” –unhappy bankWhat we need• There are many ways out of this conundrum, but we need help from the language• One basic solution: Locks– Not Java yet, though Java’s approach is similar and slightly more convenient• An ADT with operations:– new: make a new lock– acquire: blocks if this lock is already currently “held”• Once “not held”, makes lock “held”– release: makes this lock “not held”• if >= 1 threads are blocked on it, exactly 1 will acquire itSpring 2010 14CSE332: Data