Slide 1Concurrency: where are weRacesExamplepeek, sequentially speakingpeek, concurrently speakingpeek and isEmptypeek and isEmptypeek and pushpeek and pushpeek and poppeek and peekpeek and peekThe fixThe wrong “fix”Example, again (no resizing or checking)Why wrong?Getting it right3 choicesThread-localImmutableThe restConsistent LockingConsistent Locking continuedBeyond consistent lockingLock granularityTrade-offsExample: HashtableCritical-section granularityExampleExampleExampleAtomicityDon’t roll your ownCSE332: Data AbstractionsLecture 23: Programming with Locks and Critical SectionsDan GrossmanSpring 2010Concurrency: where are weDone:–The semantics of locks–Locks in Java–Using locks for mutual exclusion: bank-account exampleThis lecture:–More bad interleavings (learn to spot these!)–Guidelines/idioms for shared-memory and using locks correctly–Coarse-grained vs. fine-grainedUpcoming lectures:–Readers/writer locks–Deadlock–Condition variables–Data races and memory-consistency modelsSpring 2010 2CSE332: Data AbstractionsRacesA race condition occurs when the computation result depends on scheduling (how threads are interleaved)Bugs that exist only due to concurrency–No interleaved scheduling with 1 threadTypically, problem is some intermediate state that “messes up” a concurrent thread that “sees” that stateSpring 2010 3CSE332: Data AbstractionsExampleSpring 2010 4CSE332: Data Abstractionsclass Stack<E> { … synchronized boolean isEmpty() { … } synchronized void push(E val) { … } synchronized E pop() { if(isEmpty()) throw new StackEmptyException(); … } E peek() { E ans = pop(); push(ans); return ans; }}peek, sequentially speaking•In a sequential world, this code is of questionable style, but unquestionably correct•The “algorithm” is the only way to write a peek helper method if all you had was this interface:Spring 2010 5CSE332: Data Abstractionsinterface Stack<E> { boolean isEmpty(); void push(E val); E pop();}class C { static <E> E myPeek(Stack<E> s){ ??? }}peek, concurrently speaking•peek has no overall effect on the shared data–It is a “reader” not a “writer”•But the way it’s implemented creates an inconsistent intermediate state–Even though calls to push and pop are synchronized so there are no data races on the underlying array/list/whatever•This intermediate state should not be exposed–Leads to several wrong interleavings…Spring 2010 6CSE332: Data Abstractionspeek and isEmpty•Property we want: If there has been a push and no pop, then isEmpty returns false•With peek as written, property can be violated – how?Spring 2010 7CSE332: Data AbstractionsE ans = pop();push(ans);return ans;push(x)boolean b = isEmpty()TimeThread 2Thread 1 (peek)peek and isEmpty•Property we want: If there has been a push and no pop, then isEmpty returns false•With peek as written, property can be violated – how?Spring 2010 8CSE332: Data AbstractionsE ans = pop();push(ans);return ans;push(x)boolean b = isEmpty()TimeThread 2Thread 1 (peek)peek and push•Property we want: Values are returned from pop in LIFO order•With peek as written, property can be violated – how?Spring 2010 9CSE332: Data AbstractionsE ans = pop();push(ans);return ans;push(x)push(y)E e = pop()TimeThread 2Thread 1 (peek)peek and push•Property we want: Values are returned from pop in LIFO order•With peek as written, property can be violated – how?Spring 2010 10CSE332: Data AbstractionsE ans = pop();push(ans);return ans;push(x)push(y)E e = pop()TimeThread 2Thread 1 (peek)peek and pop•Property we want: Values are returned from pop in LIFO order•With peek as written, property can be violated – how?Spring 2010 11CSE332: Data AbstractionsE ans = pop();push(ans);return ans;TimeThread 2Thread 1 (peek)push(x)push(y)E e = pop()peek and peek•Property we want: peek doesn’t throw an exception if number of pushes exceeds number of pops•With peek as written, property can be violated – how?Spring 2010 12CSE332: Data AbstractionsE ans = pop();push(ans);return ans;TimeThread 2E ans = pop();push(ans);return ans;Thread 1 (peek)peek and peek•Property we want: peek doesn’t throw an exception if number of pushes exceeds number of pops•With peek as written, property can be violated – how?Spring 2010 13CSE332: Data AbstractionsE ans = pop();push(ans);return ans;TimeThread 2E ans = pop();push(ans);return ans;Thread 1 (peek)The fix•In short, peek needs synchronization to disallow interleavings–The key is to make a larger critical section–Re-entrant locks allow calls to push and popSpring 2010 14CSE332: Data Abstractionsclass Stack<E> { … synchronized E peek(){ E ans = pop(); push(ans); return ans; }}class C { <E> E myPeek(Stack<E> s){ synchronized (s) { E ans = s.pop(); s.push(ans); return ans; } }}The wrong “fix”•Focus so far: problems from peek doing writes that lead to an incorrect intermediate state•Tempting but wrong: If an implementation of peek (or isEmpty) does not write anything, then maybe we can skip the synchronization?•Does not work due to data races with push and pop…Spring 2010 15CSE332: Data AbstractionsExample, again (no resizing or checking)Spring 2010 16CSE332: Data Abstractionsclass Stack<E> { private E[] array = (E[])new Object[SIZE]; int index = -1; boolean isEmpty() { // unsynchronized: wrong?! return index==-1; } synchronized void push(E val) { array[++index] = val; } synchronized E pop() { return array[index--]; } E peek() { // unsynchronized: wrong! return array[index]; }}Why wrong?•It looks like isEmpty and peek can “get away with this” since push and pop adjust the state “in one tiny step”•But this code is still wrong and depends on language-implementation details you cannot assume–Even “tiny steps” may require multiple steps in the implementation: array[++index] = val probably takes at least two steps–Code has a data race, allowing very strange behavior •Important discussion in future lecture•Moral: Don’t introduce a data race, even if every interleaving you can think of is correctSpring 2010 17CSE332: Data AbstractionsGetting it rightAvoiding race conditions on shared resources is difficult–Decades of bugs has led to some conventional wisdom: general techniques that are known to workRest of lecture distills key ideas and trade-offs–Parts paraphrased from “Java Concurrency in Practice”•Chapter 2 (rest of