Mutual Exclusion
Mutual Exclusion Companion slides for The Art of Multiprocessor Programming by Maurice Herlihy & Nir Shavit
Mutual Exclusion
Art of Multiprocessor Programming 2 Mutual Exclusion • We will clarify our understanding of mutual exclusion • We will also show you how to reason about various properties in an asynchronous concurrent setting
Mutual Exclusion
Mutual Exclusion In his 1965 paper E. W. Dijkstra wrote: "Given in this paper is a solution to a problem which, to the knowledge of the author, has been an open question since at least 1962, irrespective of the solvability. [...] Although the setting of the problem might seem somewhat academic at first, the author trusts that anyone familiar with the logical problems that arise in computer coupling will appreciate the significance of the fact that this problem indeed can be solved." Art of Multiprocessor Programming 3
Mutual Exclusion
Art of Multiprocessor Programming 4 Mutual Exclusion • Formal problem definitions • Solutions for 2 threads • Solutions for n threads • Fair solutions • Inherent costs
Warning
Art of Multiprocessor Programming 5 Warning • You will never use these protocols – Get over it • You are advised to understand them – The same issues show up everywhere – Except hidden and more complex
Why is Concurrent Programming so Hard?
Art of Multiprocessor Programming 6 Why is Concurrent Programming so Hard? • Try preparing a seven-course banquet – By yourself – With one friend – With twenty-seven friends … • Before we can talk about programs – Need a language – Describing time and concurrency
Time
Art of Multiprocessor Programming 7 • “Absolute, true and mathematical time, of itself and from its own nature, flows equably without relation to anything external.” (I. Newton, 1689) • “Time is, like, Nature’s way of making sure that everything doesn’t happen all at once.” (Anonymous, circa 1968) Time time
Events
Art of Multiprocessor Programming 8 time • An event a 0 of thread A is – Instantaneous – No simultaneous events (break ties) a 0 Events
Threads
Art of Multiprocessor Programming 9 time • A thread A is (formally) a sequence a 0 , a 1 , ... of events – “Trace” model – Notation: a 0 a 1 indicates order a 0 Threads a 1 a 2 …
Example Thread Events
Art of Multiprocessor Programming 10 • Assign to shared variable • Assign to local variable • Invoke method • Return from method • Lots of other things … Example Thread Events
Threads are State Machines
Art of Multiprocessor Programming 11 Threads are State Machines Events are transitions a 0 a 1 a 2 a 3
States
Art of Multiprocessor Programming 12 States • Thread State – Program counter – Local variables • System state – Object fields (shared variables) – Union of thread states
Concurrency
Art of Multiprocessor Programming 13 time • Thread A Concurrency
Concurrency
Art of Multiprocessor Programming 14 time time • Thread A • Thread B Concurrency
Interleavings
Art of Multiprocessor Programming 15 time Interleavings • Events of two or more threads – Interleaved – Not necessarily independent (why?)
Intervals
Art of Multiprocessor Programming 16 time • An interval A 0 =(a 0 ,a 1 ) is – Time between events a 0 and a 1 a 0 a 1 Intervals A 0
Intervals may Overlap
Art of Multiprocessor Programming 17 time Intervals may Overlap a 0 a 1 A 0 b 0 b 1 B 0
Intervals may be Disjoint
Art of Multiprocessor Programming 18 time Intervals may be Disjoint a 0 a 1 A 0 b 0 b 1 B 0
Precedence
Art of Multiprocessor Programming 19 time Precedence a 0 a 1 A 0 b 0 b 1 B 0 Interval A 0 precedes interval B 0
Precedence
Art of Multiprocessor Programming 20 Precedence • Notation: A 0 B 0 • Formally, – End event of A 0 before start event of B 0 – Also called “ happens before ” or “ precedes ”
Precedence Ordering
Art of Multiprocessor Programming 21 Precedence Ordering • Remark: A 0 B 0 is just like saying – 1066 AD 1492 AD , – Middle Ages Renaissance , • Oh wait, – what about this week vs this month ?
Precedence Ordering
Art of Multiprocessor Programming 22 Precedence Ordering • Never true that A A • If A B then not true that B A • If A B & B C then A C • Funny thing: A B & B A might both be false!
Partial Orders (review)
Art of Multiprocessor Programming 23 Partial Orders (review) • Irreflexive: – Never true that A A • Antisymmetric: – If A B then not true that B A • Transitive: – If A B & B C then A C
Total Orders (review)
Art of Multiprocessor Programming 24 Total Orders (review) • Also – Irreflexive – Antisymmetric – Transitive • Except that for every distinct A , B , – Either A B or B A
Repeated Events
Art of Multiprocessor Programming 25 Repeated Events while (mumble) { a 0 ; a 1 ; } a 0 k k -th occurrence of event a 0 A 0 k k -th occurrence of interval A 0 =(a 0 ,a 1 )
Implementing a Counter
Art of Multiprocessor Programming 26 Implementing a Counter public class Counter { private long value; public long getAndIncrement() { temp = value; value = temp + 1; return temp; } } Make these steps indivisible using locks
Locks (Mutual Exclusion)
Art of Multiprocessor Programming 27 Locks (Mutual Exclusion) public interface Lock { public void lock(); public void unlock(); }
Locks (Mutual Exclusion)
Art of Multiprocessor Programming 28 Locks (Mutual Exclusion) public interface Lock { public void lock(); public void unlock(); } acquire lock
Locks (Mutual Exclusion)
Art of Multiprocessor Programming 29 Locks (Mutual Exclusion) public interface Lock { public void lock(); public void unlock(); } release lock acquire lock
Using Locks
Art of Multiprocessor Programming 30 Using Locks public class Counter { private long value; private Lock lock ; public long getAndIncrement () { lock.lock(); try { int temp = value; value = value + 1; } finally { lock.unlock(); } return temp; }}
Using Locks
Art of Multiprocessor Programming 31 Using Locks public class Counter { private long value; private Lock lock ; public long getAndIncrement() { lock.lock(); try { int temp = value; value = value + 1; } finally { lock.unlock(); } return temp; }} acquire Lock
Using Locks
Art of Multiprocessor Programming 32 Using Locks public class Counter { private long value; private Lock lock ; public long getAndIncrement() { lock.lock(); try { int temp = value; value = value + 1; } finally { lock.unlock(); } return temp; }} Release lock (no matter what)
Using Locks
Art of Multiprocessor Programming 33 Using Locks public class Counter { private long value; private Lock lock ; public long getAndIncrement() { lock.lock(); try { int temp = value; value = value + 1; } finally { lock.unlock(); } return temp; }} critical section
Mutual Exclusion
Art of Multiprocessor Programming 34 Mutual Exclusion • Let CS i k be thread i ’s k -th critical section execution
Mutual Exclusion
Art of Multiprocessor Programming 35 Mutual Exclusion • Let CS i k be thread i ’s k -th critical section execution • And CS j m be thread j ’s m -th critical section execution
Mutual Exclusion
Art of Multiprocessor Programming 36 Mutual Exclusion • Let CS i k be thread i ’s k -th critical section execution • And CS j m be j ’s m -th execution • Then either – or
Mutual Exclusion
Art of Multiprocessor Programming 37 Mutual Exclusion • Let CS i k be thread i ’s k -th critical section execution • And CS j m be j ’s m -th execution • Then either – or CS i k CS j m
Mutual Exclusion
Art of Multiprocessor Programming 38 Mutual Exclusion • Let CS i k be thread i ’s k -th critical section execution • And CS j m be j ’s m -th execution • Then either – or CS i k CS j m CS j m CS i k
Deadlock-Free
Art of Multiprocessor Programming 39 Deadlock-Free • If some thread calls lock() – And never returns – Then other threads must complete lock() and unlock() calls infinitely often • System as a whole makes progress – Even if individuals starve
Starvation-Free
Art of Multiprocessor Programming 40 Starvation-Free • If some thread calls lock() – It will eventually return • Individual threads make progress
Two-Thread vs n-Thread Solutions
Art of Multiprocessor Programming 41 Two-Thread vs n -Thread Solutions • 2 -thread solutions first – Illustrate most basic ideas – Fits on one slide • Then n -thread solutions
Two-Thread Conventions
Art of Multiprocessor Programming 42 class … implements Lock { … // thread-local index, 0 or 1 public void lock() { int i = ThreadID.get(); int j = 1 - i; … } } Two-Thread Conventions
Two-Thread Conventions
Art of Multiprocessor Programming 43 class … implements Lock { … // thread-local index, 0 or 1 public void lock() { int i = ThreadID.get(); int j = 1 - i; … } } Two-Thread Conventions Henceforth: i is current thread, j is other thread
LockOne
LockOne class LockOne implements Lock { private boolean[] flag = new boolean[2]; public void lock() { flag[i] = true ; while (flag[j]) {} }
LockOne
LockOne class LockOne implements Lock { private boolean[] flag = new boolean[2]; public void lock() { flag[i] = true; while (flag[j]) {} } Each thread has flag
LockOne
LockOne class LockOne implements Lock { private boolean[] flag = new boolean[2]; public void lock() { flag[i] = true ; while (flag[j]) {} } Set my flag
LockOne
LockOne class LockOne implements Lock { private boolean[] flag = new boolean[2]; public void lock() { flag[i] = true; while (flag[j]) {} } Wait for other flag to become false
LockOne Satisfies Mutual Exclusion
Art of Multiprocessor Programming 48 • Assume CS A j overlaps CS B k • Consider each thread's last ( j -th and k -th) read and write in the lock() method before entering • Derive a contradiction LockOne Satisfies Mutual Exclusion
From the Code
Art of Multiprocessor Programming 49 • write A (flag[A]=true) read A (flag[B]==false) CS A • write B (flag[B]=true) read B (flag[A]==false) CS B From the Code class LockOne implements Lock { … public void lock() { flag[i] = true ; while (flag[j]) {} }
From the Assumption
Art of Multiprocessor Programming 50 • read A (flag[B]==false) write B (flag[B]=true) • read B (flag[A]==false) write A (flag[A]=true) From the Assumption
Combining
Art of Multiprocessor Programming 51 • Assumptions: – read A (flag[B]==false) write B (flag[B]=true) – read B (flag[A]==false) write A (flag[A]=true) • From the code – write A (flag[A]=true) read A (flag[B]==false) – write B (flag[B]=true) read B (flag[A]==false) Combining
Combining
Art of Multiprocessor Programming 52 • Assumptions: – read A (flag[B]==false) write B (flag[B]=true) – read B (flag[A]==false) write A (flag[A]=true) • From the code – write A (flag[A]=true) read A (flag[B]==false) – write B (flag[B]=true) read B (flag[A]==false) Combining
Combining
Art of Multiprocessor Programming 53 • Assumptions: – read A (flag[B]==false) write B (flag[B]=true) – read B (flag[A]==false) write A (flag[A]=true) • From the code – write A (flag[A]=true) read A (flag[B]==false) – write B (flag[B]=true) read B (flag[A]==false) Combining
Combining
Art of Multiprocessor Programming 54 • Assumptions: – read A (flag[B]==false) write B (flag[B]=true) – read B (flag[A]==false) write A (flag[A]=true) • From the code – write A (flag[A]=true) read A (flag[B]==false) – write B (flag[B]=true) read B (flag[A]==false) Combining
Combining
Art of Multiprocessor Programming 55 • Assumptions: – read A (flag[B]==false) write B (flag[B]=true) – read B (flag[A]==false) write A (flag[A]=true) • From the code – write A (flag[A]=true) read A (flag[B]==false) – write B (flag[B]=true) read B (flag[A]==false) Combining
Combining
Art of Multiprocessor Programming 56 • Assumptions: – read A (flag[B]==false) write B (flag[B]=true) – read B (flag[A]==false) write A (flag[A]=true) • From the code – write A (flag[A]=true) read A (flag[B]==false) – write B (flag[B]=true) read B (flag[A]==false) Combining
Cycle!
Art of Multiprocessor Programming 57 Cycle! Impossible in a partial order
Deadlock Freedom
Art of Multiprocessor Programming 58 Deadlock Freedom • LockOne Fails deadlock-freedom – Concurrent execution can deadlock – Sequential executions OK flag[i] = true ; flag[j] = true ; while (flag[j]){} while (flag[i]){}
LockTwo
Art of Multiprocessor Programming 59 LockTwo public class LockTwo implements Lock { private int victim; public void lock() { victim = i; while (victim == i) {}; } public void unlock() {} }
LockTwo
Art of Multiprocessor Programming 60 LockTwo public class LockTwo implements Lock { private int victim; public void lock() { victim = i; while (victim == i) {}; } public void unlock() {} } Let other go first
LockTwo
Art of Multiprocessor Programming 61 LockTwo public class LockTwo implements Lock { private int victim; public void lock() { victim = i; while (victim == i) {}; } public void unlock() {} } Wait for permission
LockTwo
Art of Multiprocessor Programming 62 LockTwo public class Lock2 implements Lock { private int victim; public void lock() { victim = i; while (victim == i) {}; } public void unlock() {} } Nothing to do
LockTwo Claims
Art of Multiprocessor Programming 63 public void LockTwo() { victim = i; while (victim == i) {}; } LockTwo Claims • Satisfies mutual exclusion – If thread i in CS – Then victim == j – Cannot be both 0 and 1 • Not deadlock free – Sequential execution deadlocks – Concurrent execution does not
Peterson’s Algorithm
Art of Multiprocessor Programming 64 Peterson’s Algorithm public void lock() { flag[i] = true ; victim = i; while (flag[j] && victim == i) {}; } public void unlock() { flag[i] = false ; }
Peterson’s Algorithm
Art of Multiprocessor Programming 65 Peterson’s Algorithm public void lock() { flag[i] = true ; victim = i; while (flag[j] && victim == i) {}; } public void unlock() { flag[i] = false; } Announce I’m interested
Peterson’s Algorithm
Art of Multiprocessor Programming 66 Peterson’s Algorithm public void lock() { flag[i] = true ; victim = i; while (flag[j] && victim == i) {}; } public void unlock() { flag[i] = false; } Announce I’m interested Defer to other
Peterson’s Algorithm
Art of Multiprocessor Programming 67 Peterson’s Algorithm public void lock() { flag[i] = true ; victim = i; while (flag[j] && victim == i) {}; } public void unlock() { flag[i] = false; } Announce I’m interested Defer to other Wait while other interested & I’m the victim
Peterson’s Algorithm
Art of Multiprocessor Programming 68 Peterson’s Algorithm public void lock() { flag[i] = true ; victim = i; while (flag[j] && victim == i) {}; } public void unlock() { flag[i] = false ; } No longer interested Announce I’m interested Defer to other Wait while other interested & I’m the victim
Mutual Exclusion
Art of Multiprocessor Programming 69 Mutual Exclusion (1) write B (Flag[B]=true) write B (victim=B) public void lock() { flag[i] = true ; victim = i; while (flag[j] && victim == i) {}; } From the Code
Also from the Code
Art of Multiprocessor Programming 70 Also from the Code (2) write A (victim=A) read A (flag[B]) read A (victim) public void lock() { flag[i] = true; victim = i; while (flag[j] && victim == i) {}; }
Assumption
Art of Multiprocessor Programming 71 Assumption W.L.O.G. assume A is the last thread to write victim (3) write B (victim=B) write A (victim=A)
Combining Observations
Art of Multiprocessor Programming 72 Combining Observations (1) write B (flag[B]=true) write B (victim=B) (3) write B (victim=B) write A (victim=A) (2) write A (victim=A) read A (flag[B]) read A (victim)
Combining Observations
Art of Multiprocessor Programming 73 Combining Observations (1) write B (flag[B]=true) write B (victim=B) (3) write B (victim=B) write A (victim=A) (2) write A (victim=A) read A (flag[B]) read A (victim)
Combining Observations
Art of Multiprocessor Programming 74 Combining Observations (1) write B (flag[B]=true) write B (victim=B) (3) write B (victim=B) write A (victim=A) (2) write A (victim=A) read A (flag[B]) read A (victim) A read flag[B] == true and victim == A , so it could not have entered the CS ( QED)
Deadlock Free
Art of Multiprocessor Programming 75 Deadlock Free • Thread blocked – only at while loop – only if other’s flag is true – only if it is the victim • Solo: other’s flag is false • Both: one or the other not the victim public void lock() { … while (flag[j] && victim == i) {};
Starvation Free
Art of Multiprocessor Programming 76 Starvation Free • Thread i blocked only if j repeatedly re-enters so that flag[j] == true and victim == i • When j re-enters – it sets victim to j . – So i gets in public void lock( ) { flag[i] = true ; victim = i; while (flag[j] && victim == i) {}; } public void unlock() { flag[i] = false ; }
The Filter Algorithm for n Threads
Art of Multiprocessor Programming 77 The Filter Algorithm for n Threads There are n-1 “waiting rooms” called levels • At each level – At least one enters level – At least one blocked if many try • Only one thread makes it through ncs cs
Filter
Art of Multiprocessor Programming 78 Filter class Filter implements Lock { int[] level; // level[i] for thread i int[] victim; // victim[L] for level L public Filter(int n) { level = new int[n]; victim = new int[n]; for ( int i = 1; i < n; i++) { level[i] = 0; }} … } level victim n -1 n -1 0 1 0 0 0 0 0 0 4 2 2 Thread 2 at level 4 0 4
Filter
Art of Multiprocessor Programming 79 Filter class Filter implements Lock { … public void lock(){ for ( int L = 1; L < n; L++) { level[i] = L; victim[L] = i; while (( k != i level[k] >= L) && victim[L] == i ) {}; }} public void unlock() { level[i] = 0; }}
Filter
Art of Multiprocessor Programming 80 class Filter implements Lock { … public void lock() { for ( int L = 1; L < n; L++) { level[i] = L; victim[L] = i; while (( k != i) level[k] >= L) && victim[L] == i) {}; }} public void release(int i) { level[i] = 0; }} Filter One level at a time
Filter
Art of Multiprocessor Programming 81 class Filter implements Lock { … public void lock() { for (int L = 1; L < n; L++) { level[i] = L; victim[L] = i; while (( k != i) level[k] >= L) && victim[L] == i) {}; // busy wait }} public void release(int i) { level[i] = 0; }} Filter Announce intention to enter level L
Filter
Art of Multiprocessor Programming 82 class Filter implements Lock { int level[n]; int victim[n]; public void lock() { for (int L = 1; L < n; L++) { level[i] = L; victim[L] = i; while (( k != i) level[k] >= L) && victim[L] == i) {}; }} public void release(int i) { level[i] = 0; }} Filter Give priority to anyone but me
Filter
Art of Multiprocessor Programming 83 class Filter implements Lock { int level[n]; int victim[n]; public void lock() { for (int L = 1; L < n; L++) { level[i] = L; victim[L] = i; while (( k != i) level[k] >= L) && victim[L] == i) {}; }} public void release(int i) { level[i] = 0; }} Filter Wait as long as someone else is at same or higher level, and I’m designated victim
Filter
Art of Multiprocessor Programming 84 class Filter implements Lock { int level[n]; int victim[n]; public void lock() { for (int L = 1; L < n; L++) { level[i] = L; victim[L] = i; while (( k != i) level[k] >= L) && victim[L] == i) {}; }} public void release(int i) { level[i] = 0; }} Filter Thread enters level L when it completes the loop
Claim
Art of Multiprocessor Programming 85 Claim • Start at level L=0 • At most n-L threads enter level L • Mutual exclusion at level L=n-1 ncs cs L=n-1 L=1 L=n-2 L=0
Induction Hypothesis
Art of Multiprocessor Programming 86 Induction Hypothesis • Assume all at level L -1 enter level L • A last to write victim[L] • B is any other thread at level L • No more than n-(L-1) at level L-1 • Induction step: by contradiction ncs cs L-1 has n-(L-1) L has n-L assume prove
Proof Structure
Art of Multiprocessor Programming 87 Proof Structure ncs cs Assumed to enter L-1 By way of contradiction all enter L n-L+1 = 4 n-L+1 = 4 A B Last to write victim[L] Show that A must have seen B in level[L] and since victim[L] == A could not have entered
Just Like Peterson
Art of Multiprocessor Programming 88 Just Like Peterson (1) write B (level[B]=L) write B (victim[L]=B) public void lock() { for (int L = 1; L < n; L++) { level[i] = L; victim[L] = i; while (( k != i) level[k] >= L) && victim[L] == i) {}; }} From the Code
From the Code
Art of Multiprocessor Programming 89 From the Code (2) write A (victim[L]=A) read A (level[B]) read A (victim[L]) public void lock() { for (int L = 1; L < n; L++) { level[i] = L; victim[L] = i; while (( k != i) level[k] >= L) && victim[L] == i) {}; }}
By Assumption
Art of Multiprocessor Programming 90 By Assumption By assumption, A is the last thread to write victim[L] (3) write B (victim[L]=B) write A (victim[L]=A)
Combining Observations
Art of Multiprocessor Programming 91 Combining Observations (1) write B (level[B]=L) write B (victim[L]=B) (3) write B (victim[L]=B) write A (victim[L]=A) (2) write A (victim[L]=A) read A (level[B]) read A (victim[L])
Combining Observations
Art of Multiprocessor Programming 92 Combining Observations (1) write B (level[B]=L) write B (victim[L]=B) (3) write B (victim[L]=B) write A (victim[L]=A) (2) write A (victim[L]=A) read A (level[B]) read A (victim[L])
Combining Observations
Art of Multiprocessor Programming 93 Combining Observations (1) write B (level[B]=L) write B (victim[L]=B) (3) write B (victim[L]=B) write A (victim[L]=A) (2) write A (victim[L]=A) read A (level[B]) read A (victim[L]) A read level[B] ≥ L , and victim[L] = A , so it could not have entered level L !
No Starvation
Art of Multiprocessor Programming 94 No Starvation • Filter Lock satisfies properties: – Just like Peterson Alg at any level – So no one starves • But what about fairness? – Threads can be overtaken by others
Bounded Waiting
Art of Multiprocessor Programming 95 Bounded Waiting • Want stronger fairness guarantees • Thread not “overtaken” too much • If A starts before B, then A enters before B? • But what does “start” mean? • Need to adjust definitions ….
Bounded Waiting
Art of Multiprocessor Programming 96 Bounded Waiting • Divide lock() method into 2 parts: – Doorway interval: • Written D A • always finishes in finite steps – Waiting interval: • Written W A • may take unbounded steps
First-Come-First-Served
Art of Multiprocessor Programming 97 • For threads A and B : – If D A k D B j • A ’s k -th doorway precedes B ’s j -th doorway – Then CS A k CS B j • A ’s k -th critical section precedes B ’s j -th critical section • B cannot overtake A First-Come-First-Served
Fairness Again
Art of Multiprocessor Programming 98 Fairness Again • Filter Lock satisfies properties: – No one starves – But very weak fairness • Can be overtaken arbitrary # of times – That’s pretty lame…
Bakery Algorithm
Art of Multiprocessor Programming 99 Bakery Algorithm • Provides First-Come-First-Served • How? – Take a “number” – Wait until lower numbers have been served • Lexicographic order – (a,i) > (b,j) • If a > b , or a = b and i > j
Bakery Algorithm
Art of Multiprocessor Programming 100 Bakery Algorithm class Bakery implements Lock { boolean[] flag; Label[] label; public Bakery ( int n) { flag = new boolean[n]; label = new Label[n]; for ( int i = 0; i < n; i++) { flag[i] = false ; label[i] = 0; } } …
Bakery Algorithm
Art of Multiprocessor Programming 101 Bakery Algorithm class Bakery implements Lock { boolean[] flag; Label[] label; public Bakery (int n) { flag = new boolean[n]; label = new Label[n]; for (int i = 0; i < n; i++) { flag[i] = false; label[i] = 0; } } … n -1 0 f f f f t f t 2 f 0 0 0 0 5 0 4 0 6 CS
Bakery Algorithm
Art of Multiprocessor Programming 102 Bakery Algorithm class Bakery implements Lock { … public void lock() { flag[i] = true ; label[i] = max(label[0], …,label[n-1])+1; while ( k flag[k] && (label[i],i) > (label[k],k)); }
Bakery Algorithm
Art of Multiprocessor Programming 103 Bakery Algorithm class Bakery implements Lock { … public void lock() { flag[i] = true ; label[i] = max(label[0], …,label[n-1])+1; while ( k flag[k] && (label[i],i) > (label[k],k)); } Doorway
Bakery Algorithm
Art of Multiprocessor Programming 104 Bakery Algorithm class Bakery implements Lock { … public void lock() { flag[i] = true ; label[i] = max(label[0], …,label[n-1])+1; while ( k flag[k] && (label[i],i) > (label[k],k)); } I’m interested
Bakery Algorithm
Art of Multiprocessor Programming 105 Bakery Algorithm class Bakery implements Lock { … public void lock() { flag[i] = true; label[i] = max(label[0], …,label[n-1])+1; while ( k flag[k] && (label[i],i) > (label[k],k)); } Take increasing label (read labels in some arbitrary order)
Bakery Algorithm
Art of Multiprocessor Programming 106 Bakery Algorithm class Bakery implements Lock { … public void lock() { flag[i] = true; label[i] = max(label[0], …,label[n-1])+1; while ( k flag[k] && (label[i],i) > (label[k],k)); } Someone is interested
Bakery Algorithm
Art of Multiprocessor Programming 107 Bakery Algorithm class Bakery implements Lock { boolean flag[n]; int label[n]; public void lock() { flag[i] = true; label[i] = max(label[0], …,label[n-1])+1; while ( k flag[k] && (label[i],i) > (label[k],k)); } Someone is interested … … whose (label,i ) in lexicographic order is lower
Bakery Algorithm
Art of Multiprocessor Programming 108 Bakery Algorithm class Bakery implements Lock { … public void unlock() { flag[i] = false ; } }
Bakery Algorithm
Art of Multiprocessor Programming 109 Bakery Algorithm class Bakery implements Lock { … public void unlock() { flag[i] = false ; } } No longer interested labels are always increasing
No Deadlock
Art of Multiprocessor Programming 110 No Deadlock • There is always one thread with earliest label • Ties are impossible (why?)
First-Come-First-Served
Art of Multiprocessor Programming 111 First-Come-First-Served • If D A D B then – A ’s label is smaller • And: – write A (label[A]) – read B (label[A]) – write B (label[B]) read B (flag[A]) • So B sees – smaller label for A – locked out while flag[A] is true class Bakery implements Lock { public void lock() { flag[i] = true ; label[i] = max (label[0], …,label[n-1])+1; while ( k flag[k] && (label[i],i) > (label[k],k)); }
Mutual Exclusion
Art of Multiprocessor Programming 112 Mutual Exclusion • Suppose A and B in CS together • Suppose A has earlier label • When B entered, it must have seen – flag[A] is false , or – label[A] > label[B] class Bakery implements Lock { public void lock() { flag[i] = true ; label[i] = max (label[0], …,label[n-1])+1; while ( k flag[k] && (label[i],i) > (label[k],k)); }
Mutual Exclusion
Art of Multiprocessor Programming 113 Mutual Exclusion • Labels are strictly increasing so • B must have seen flag[A] == false
Mutual Exclusion
Art of Multiprocessor Programming 114 Mutual Exclusion • Labels are strictly increasing so • B must have seen flag[A] == false • Labeling B read B (flag[A]) write A (flag[A]) Labeling A
Mutual Exclusion
Art of Multiprocessor Programming 115 Mutual Exclusion • Labels are strictly increasing so • B must have seen flag[A] == false • Labeling B read B (flag[A]) write A (flag[A]) Labeling A • Which contradicts the assumption that A has an earlier label
Bakery Y232K Bug
Art of Multiprocessor Programming 116 Bakery Y2 32 K Bug class Bakery implements Lock { … public void lock() { flag[i] = true ; label[i] = max (label[0], …,label[n-1])+1; while ( k flag[k] && (label[i],i) > (label[k],k)); }
Bakery Y232K Bug
Art of Multiprocessor Programming 117 Bakery Y2 32 K Bug class Bakery implements Lock { … public void lock() { flag[i] = true; label[i] = max (label[0], …,label[n-1])+1; while ( k flag[k] && (label[i],i) > (label[k],k)); } Mutex breaks if label[i] overflows
Does Overflow Actually Matter?
Art of Multiprocessor Programming 118 Does Overflow Actually Matter? • Yes – Y2K – 18 January 2038 (Unix time_t rollover) – 16-bit counters • No – 64-bit counters • Maybe – 32-bit counters
Timestamps
Art of Multiprocessor Programming 119 Timestamps • Label variable is really a timestamp • Need ability to – Read others’ timestamps – Compare them – Generate a later timestamp • Can we do this without overflow?
The Good News
Art of Multiprocessor Programming 120 • One can construct a – Wait-free (no mutual exclusion) – Concurrent – Timestamping system – That never overflows The Good News
The Good News
Art of Multiprocessor Programming 121 • One can construct a – Wait-free (no mutual exclusion) – Concurrent – Timestamping system – That never overflows The Good News This part is hard Bad
Instead …
Art of Multiprocessor Programming 122 Instead … • We construct a Sequential timestamping system – Same basic idea – But simpler • As if we use mutex to read & write atomically • No good for building locks – But useful anyway
Precedence Graphs
Art of Multiprocessor Programming 123 Precedence Graphs 0 1 2 3 • Timestamps form directed graph • Edge x to y – Means x is later timestamp – We say x dominates y
Unbounded Counter Precedence Graph
Art of Multiprocessor Programming 124 Unbounded Counter Precedence Graph 0 1 2 3 • Timestamping = move tokens on graph • Atomically – read others’ tokens – move mine • Ignore tie-breaking for now
Unbounded Counter Precedence Graph
Art of Multiprocessor Programming 125 Unbounded Counter Precedence Graph 0 1 2 3
Unbounded Counter Precedence Graph
Art of Multiprocessor Programming 126 Unbounded Counter Precedence Graph 0 1 2 3 takes 0 takes 1 takes 2
Two-Thread Bounded Precedence Graph
Art of Multiprocessor Programming 127 Two-Thread Bounded Precedence Graph 0 1 2
Two-Thread Bounded Precedence Graph
Art of Multiprocessor Programming 128 Two-Thread Bounded Precedence Graph 0 1 2
Two-Thread Bounded Precedence Graph
Art of Multiprocessor Programming 129 Two-Thread Bounded Precedence Graph 0 1 2
Two-Thread Bounded Precedence Graph
Art of Multiprocessor Programming 130 Two-Thread Bounded Precedence Graph 0 1 2
Two-Thread Bounded Precedence Graph T2
Art of Multiprocessor Programming 131 Two-Thread Bounded Precedence Graph T 2 0 1 2 and so on …
Three-Thread Bounded Precedence Graph?
Art of Multiprocessor Programming 132 Three-Thread Bounded Precedence Graph? 1 2 0 3
Three-Thread Bounded Precedence Graph?
Art of Multiprocessor Programming 133 Three-Thread Bounded Precedence Graph? 1 2 0 3 What to do if one thread gets stuck?
Graph Composition
Art of Multiprocessor Programming 134 Graph Composition 0 1 2 0 1 2 Replace each vertex with a copy of the graph T 3 =T 2 *T 2
Three-Thread Bounded Precedence Graph T3
Art of Multiprocessor Programming 135 Three-Thread Bounded Precedence Graph T 3 2 0 1 2 1 0 1 2 0 0 1 2
Three-Thread Bounded Precedence Graph T3
Art of Multiprocessor Programming 136 Three-Thread Bounded Precedence Graph T 3 2 0 1 2 1 0 1 2 0 0 1 2 20 02 12 < <
Three-Thread Bounded Precedence Graph T3
Art of Multiprocessor Programming 137 Three-Thread Bounded Precedence Graph T 3 2 0 1 2 1 0 1 2 0 0 1 2 and so on…
In General
Art of Multiprocessor Programming 138 In General T k = T 2 * T k-1 K threads need 3 k nodes label size = Log 2 (3 k ) = 2k
Deep Philosophical Question
Art of Multiprocessor Programming 139 Deep Philosophical Question • The Bakery Algorithm is – Succinct, – Elegant, and – Fair. • Q: So why isn’t it practical? • A: Well, you have to read N distinct variables
Shared Memory
Art of Multiprocessor Programming 140 Shared Memory • Shared read/write memory locations called Registers (historical reasons) • Come in different flavors – Multi-Reader-Single-Writer ( Flag[] ) – Multi-Reader-Multi-Writer ( Victim [] ) – Not that interesting: SRMW and SRSW
Theorem
Art of Multiprocessor Programming 141 Theorem At least N MRSW (multi-reader/single- writer) registers are needed to solve deadlock-free mutual exclusion. N registers like Flag[] …
Proving Algorithmic Impossibility
Art of Multiprocessor Programming 142 Proving Algorithmic Impossibility CS write C • To show no algorithm exists: • assume by way of contradiction one does, • show a bad execution that violates properties: • in our case assume an alg for deadlock free mutual exclusion using < N registers
Proof: Need N-MRSW Registers
Art of Multiprocessor Programming 143 Proof: Need N-MRSW Registers Each thread must write to some register …can’t tell whether A is in critical section write CS CS CS write A B C
Upper Bound
Art of Multiprocessor Programming 144 Upper Bound • Bakery algorithm – Uses 2N MRSW registers • So the bound is (pretty) tight • But what if we use MRMW registers? – Like victim[] ?
Bad News Theorem
Art of Multiprocessor Programming 145 Bad News Theorem At least N MRMW multi-reader/ multi- writer registers are needed to solve deadlock-free mutual exclusion. (So multiple writers don’t help)
Theorem (For 2 Threads)
Art of Multiprocessor Programming 146 Theorem (For 2 Threads) Theorem: Deadlock-free mutual exclusion for 2 threads requires at least 2 multi-reader multi-writer registers Proof: assume one register suffices and derive a contradiction
Two Thread Execution
Art of Multiprocessor Programming 147 Two Thread Execution • Threads run, reading and writing R • Deadlock free so at least one gets in B A CS Write(R) CS R
Covering State for One Register Always Exists
Art of Multiprocessor Programming 148 Covering State for One Register Always Exists Write(R) B In any protocol B has to write to the register before entering CS, so stop it just before
Proof: Assume Cover of 1
Art of Multiprocessor Programming 149 Proof: Assume Cover of 1 A B Write(R) CS A runs, possibly writes to the register, enters CS
Proof: Assume Cover of 1
Art of Multiprocessor Programming 150 Proof: Assume Cover of 1 A B CS B Runs, first obliterating any trace of A , then also enters the critical section Write(R) CS
Theorem
Art of Multiprocessor Programming 151 Theorem Deadlock-free mutual exclusion for 3 threads requires at least 3 multi-reader multi-writer registers
Proof: Assume Cover of 2
Art of Multiprocessor Programming 152 Proof: Assume Cover of 2 Write(R B ) B Write(R C ) C A Only 2 registers
Run A Solo
Art of Multiprocessor Programming 153 Run A Solo Write(R B ) B Write(R C ) C A Writes to one or both registers, enters CS CS
Obliterate Traces of A
Art of Multiprocessor Programming 154 Obliterate Traces of A Write(R B ) B Write(R C ) C A Other threads obliterate evidence that A entered CS CS
Mutual Exclusion Fails
Art of Multiprocessor Programming 155 Mutual Exclusion Fails Write(R B ) B Write(R C ) C A CS CS CS looks empty, so another thread gets in
Proof Strategy
Art of Multiprocessor Programming 156 Proof Strategy • Proved : a contradiction starting from a covering state for 2 registers • Claim : a covering state for 2 registers is reachable from any state where CS is empty
Covering State for Two
Art of Multiprocessor Programming 157 • If we run B through CS 3 times, B must return twice to cover some register, say R B Covering State for Two Write(R B ) B Write(R A ) A
Covering State for Two
Art of Multiprocessor Programming 158 Covering State for Two • Start with B covering register R B for the 1 st time • Run A until it is about to write to uncovered R A • Are we done? Write(R B ) B Write(R A ) A
Covering State for Two
Art of Multiprocessor Programming 159 Covering State for Two • NO! A could have written to R B • So CS no longer looks empty to thread C Write(R B ) B Write(R A ) A
Covering State for Two
Art of Multiprocessor Programming 160 Covering State for Two • Run B obliterating traces of A in R B • Run B again until it is about to write to R B • Now we are done Write(R B ) B Write(R A ) A
Inductively We Can Show
Art of Multiprocessor Programming 161 Inductively We Can Show • There is a covering state – Where k threads not in CS cover k distinct registers – Proof follows when k = N-1 Write(R B ) B Write(R C ) C Write(R A ) A
Summary of Lecture
Art of Multiprocessor Programming 162 Summary of Lecture • In the 1960’s several incorrect solutions to starvation-free mutual exclusion using RW-registers were published… • Today we know how to solve FIFO N thread mutual exclusion using 2N RW- Registers
Summary of Lecture
Art of Multiprocessor Programming 163 Summary of Lecture • N RW-Registers inefficient – Because writes “cover” older writes • Need stronger hardware operations – that do not have the “covering problem” • In next lectures - understand what these operations are…
Art of Multiprocessor Programming 164   creativecommons.org/licenses/by-sa/2.5/ Creative Commons Attribution-ShareAlike 2.5 License . • You are free : – to Share — to copy, distribute and transmit the work – to Remix — to adapt the work • Under the following conditions : – Attribution . You must attribute the work to “The Art of Multiprocessor Programming” (but not in any way that suggests that the authors endorse you or your use of the work). – Share Alike . If you alter, transform, or build upon this work, you may distribute the resulting work only under the same, similar or a compatible license. • For any reuse or distribution, you must make clear to others the license terms of this work. The best way to do this is with a link to – http://creativecommons.org/licenses/by-sa/3.0/. • Any of the above conditions can be waived if you get permission from the copyright holder. • Nothing in this license impairs or restricts the author's moral rights.