A Sophomoric Introduction to Shared-Memory Parallelism and ConcurrencyLecture 4Shared-Memory Concurrency & Mutual ExclusionDan GrossmanLast Updated: August 2010For more information, see http://www.cs.washington.edu/homes/djg/teachingMaterials/Sophomoric Parallelism & Concurrency, Lecture 4Toward 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)2Sophomoric Parallelism & Concurrency, Lecture 4Concurrent 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 debugging3Sophomoric Parallelism & Concurrency, Lecture 4ExamplesMultiple 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?4Sophomoric Parallelism & Concurrency, Lecture 4Why 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 other5Sophomoric Parallelism & Concurrency, Lecture 4Sharing, 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 work6Sophomoric Parallelism & Concurrency, Lecture 4Canonical exampleCorrect code in a single-threaded world7class 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.}Sophomoric Parallelism & Concurrency, Lecture 4InterleavingSuppose:–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…8Sophomoric Parallelism & Concurrency, Lecture 4A bad interleavingInterleaved withdraw(100) calls on the same account–Assume initial balance 1509int 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 bankSophomoric Parallelism & Concurrency, Lecture 4Incorrect “fix”It is tempting and almost always wrong to fix a bad interleaving by rearranging or repeating operations, such as:10void withdraw(int amount) { if(amount > getBalance()) throw new WithdrawTooLargeException(); // maybe balance changed setBalance(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?Sophomoric Parallelism & Concurrency, Lecture 4Mutual 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!11Sophomoric Parallelism & Concurrency, Lecture 4Wrong!Why can’t we implement our own mutual-exclusion protocol?– It’s technically possible under certain assumptions, but won’t work in real languages anyway12class 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}Sophomoric Parallelism & Concurrency, Lecture 4Still just moved the problem!13while(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 bankSophomoric Parallelism & Concurrency, Lecture 4What 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
View Full Document
Unlocking...