Slide 1Toward sharing resources (memory)What could go wrong?Concurrent ProgrammingWhy threads?Canonical exampleInterleavingA bad interleavingIncorrect “fix”Mutual exclusionWrong!Still just moved the problem!What we needWhy that worksAlmost-correct pseudocodeSome potential Lock mistakesOther operationsOne (not very good) possibilityRe-entrant lockJava’s Re-entrant LockSynchronized: A Java convenienceExample of Java’s synchronizedImproving the JavaJava version #2Syntactic sugarJava version #3 (final version)CSE332: Data AbstractionsLecture 22: Shared-Memory Concurrency and Mutual ExclusionTyler RobisonSummer 20101Toward sharing resources (memory)2So far we’ve looked at parallel algorithms using fork-joinForkJoin algorithms all had a very simple structure to avoid race conditionsEach thread had memory “only it accessed”Example: array sub-rangeArray variable itself was treated as ‘read-only’ in parallel portionResult of forked process not accessed until after join() calledSo the structure (mostly) ensured that bad simultaneous access wouldn’t occurStrategy 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)We’ll need to coordinate resources for them to be of useWhat could go wrong?3Imagine 2 threads, running at the same time, both with access to a shared linked-list based queue (initially empty)enqueue(x) {if(back==null){back=new Node(x);front=back;}else{back.next = new Node(x); back = back.next; }}Each own program counter (and heap, etc.)Queue is shared, so they both indirectly use the same ‘front’ and ‘back’ (which is the whole point of sharing the queue)We have no guarantee what happens first between different threads; can (and will) arbitrarily ‘interrupt’ each otherMany things can go wrong: say, one tries to enqueue “a”, the other “b”, and both verify that back is ‘null’ before other sets backResult: One assignment of back will be ‘forgotten’In general, any ‘interleaving’ of results is possible if enqueue were called at the same time for bothConcurrent Programming4Concurrency: Allowing simultaneous or interleaved access to shared resources from multiple clientsRequires coordination, particularly synchronization to avoid incorrect simultaneous access: make somebody block (wait) until resource is freejoin isn’t going to work hereWe want to 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 debuggingWhy threads?5Use of threads not always to increase performance (though they can be)Also used for:Code structure for responsivenessExample: Respond to GUI events in one thread while another thread is performing an expensive computationFailure isolationConvenient structure if want to interleave multiple tasks and don’t want an exception in one to stop the otherCanonical example6Simple code for a bank accountCorrect in a single-threaded worldclass 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.}Interleaving7Suppose we have 2 threads, T1 & T2: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-slicingT1 runs for 50 ms, pauses somewhere, T2 picks up for 50msIf 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, weird things can occurA bad interleaving8Imagine two interleaved withdraw(100) calls on the same accountAssume initial balance 150From the code we saw before, this should cause a WithdrawTooLarge exceptionint b = getBalance();if(amount > b) throw new …;setBalance(b – amount);int b = getBalance();if(amount > b) throw new …;setBalance(b – amount);Thread 1Thread 2TimeInstead of an exception, we have a “Lost withdraw”But if we had ‘if(amount>getBalance())’ instead, this wouldn’t have happened… right?Incorrect “fix”9It is tempting and almost always wrong to fix a bad interleaving by rearranging or repeating operations, such as:void 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?Mutual exclusion10The sane fix: At most one thread withdraws from account A at a timeExclude other simultaneous operations on A too (e.g., deposit)Other combinations of simultaneous operations on ‘balance’ could break things‘One at a time’ is embodied in the idea of ‘mutual exclusion’Mutual exclusion: One thread doing something with a resource (here: an account) means another thread must waitDefine ‘critical sections’; areas of code that are mutually exclusiveProgrammer (that is, you) 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!Like with Thread start() & join(), you can’t implement these yourself in JavaWrong!11Why can’t we implement our own mutual-exclusion protocol?Say we tried to coordinate it ourselves, using ‘busy’:class 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!12while(busy) { }busy = true;int b = getBalance();if(amount > b) throw new