№  Слайд  Текст 
1 

Mutual ExclusionBy Shiran Mizrahi 
2 

Critical Sectionclass Counter { private int value = 1; //counter starts at one public Counter(int c) { //constructor initializes counter value = c; } public int inc() { //increment value & return prior value int temp = value; //start of danger zone value = temp+1; //end of danger zone return temp; } 
3 

Critical SectionThe problem occurs if two threads both read the value field at the line marked “start of danger zone”, and then both update that field at the line marked “end of danger zone”. int temp = value; value = temp+1; 
4 

Critical Section2 3 2 Value read 1 read 2 write 2 write 3 read 1 write 2 time int temp = value; value = temp+1; 
5 

The mutual exclusion problemremainder code entry code critical section exit code The problem is to design the entry and exit code in a way that guarantees that the mutual exclusion and deadlockfreedom properties are satisfied. 
6 

Good propertiesMutual Exclusion: No two threads are in their critical sections at the same time. Deadlockfreedom: If a thread is trying to enter its critical section, then some thread, not necessarily the same one, eventually enters its critical section. Starvationfreedom: If a thread is trying to enter its critical section, then this thread must eventually enter its critical section. Starvationfreedom is a stronger property than Deadlockfreedom. 
7 

Discussion TopicsThe mutual exclusion problem and proposed algorithms Peterson’s algorithm Kessels’ singlewriter algorithm Tournament algorithms The Filter algorithm The Bakery algorithm 
8 

Proposed solutions for two threadsWe begin with two inadequate but interesting algorithms 
9 

Some notationsA ? B event A precedes event B CSA thread A is in the critical section writeA(x=v) the event in which thread A writes to x readA(x==v) the event in which thread A reads from x 
10 

Algorithm 1Thread 0 flag[0] = true while (flag[1]) {} critical section flag[0]=false Thread 1 flag[1] = true while (flag[0]) {} critical section flag[1]=false 
11 

Mutual ExclusionAlgorithm 1 satisfies mutual exclusion 
12 

ProofAssume in the contrary that two threads can be in their critical section at the same time. From the code we can see: write0(flag[0]=true) ? read0(flag[1]==false) ? CS0 write1(flag[1]=true) ? read1(flag[0]==false) ? CS1 From the assumption: read0(flag[1]==false) ? write1(flag[1]=true) Thread 0 flag[0] = true while (flag[1]) {} critical section flag[0]=false Thread 1 flag[1] = true while (flag[0]) {} critical section flag[1]=false 
13 

ProofWe get: write0(flag[0]=true) ? read0(flag[1]==false) ? write1(flag[1]=true) ? read1(flag[0]==false) That means that thread 0 writes (flag[0]=true) and then thread 1 reads that (flag[0]==false), a contradiction. Thread 0 flag[0] = true while (flag[1]) {} critical section flag[0]=false Thread 1 flag[1] = true while (flag[0]) {} critical section flag[1]=false 
14 

Deadlock freedomAlgorithm 1 fails deadlock freedom: Concurrent execution can deadlock. If both threads write flag[0]=true and flag[1]=true before reading (flag[0]) and (flag[1]) then both threads wait forever. Thread 0 flag[0] = true while (flag[1]) {} critical section flag[0]=false Thread 1 flag[1] = true while (flag[0]) {} critical section flag[1]=false 
15 

Algorithm 2Thread 0 victim = 0; while (victim == 0) {}; critical section Thread 1 victim = 1; while (victim == 1) {}; critical section 
16 

Mutual ExclusionAlgorithm 2 satisfies mutual exclusion 
17 

ProofAssume in the contrary that two threads can be in their critical section at the same time. From the code we can see: write0(victim=0) ? read0(victim==1) ?CS0 write1(victim=1) ? read1(victim==0) ? CS1 Thread 0 victim = 0; while (victim == 0) {}; critical section Thread 1 victim = 1; while (victim == 1) {}; critical section 
18 

ProofSince thread 1 must assign 1 to victim between the events write0(victim=0) and read0(victim==1), and since this assignment is the last, we get: write0(victim=0) ? write1(victim=1) ? read0(victim==1) Once victim is set to 1, it does not change, so every read will return 1, and this is a contradiction to the former equation: write1(victim=1) ? read1(victim==0) ? CS1 Thread 0 victim = 0; while (victim == 0) {}; critical section Thread 1 victim = 1; while (victim == 1) {}; critical section 
19 

Deadlock freedomAlgorithm 2 also fails deadlock freedom. It deadlocks if one thread runs completely before the other. Thread 0 victim = 0; while (victim == 0) {}; critical section Thread 1 victim = 1; while (victim == 1) {}; critical section 
20 

Algorithms for Two ThreadsWe’ll describe two algorithms that solve the mutual exclusion problem for two Threads. They are also deadlockfree and starvation free. 
21 

Peterson’s AlgorithmThread 0 flag[0] = true victim = 0 while (flag[1] and victim == 0) {skip} critical section flag[0] = false Thread 1 flag[1] = true victim = 1 while (flag[0] and victim == 1) {skip} critical section flag[1] = false 
22 

Peterson’s Algorithm0/1 indicates that the thread is contending for the critical section by setting flag[0]/flag[1] to true. victim shows who got last Then if the value of flag[i] is true then there is no contending by other thread and the thread can start executing the critical section. Otherwise the first who writes to victim is also the first to get into the critical section Thread 0 flag[0] = true victim = 0 while (flag[1] and victim == 0) {skip} critical section flag[0] = false Thread 1 flag[1] = true victim = 1 while (flag[0] and victim == 1) {skip} critical section flag[1] = false 
23 

Schematic for Peterson’s mutual exclusion algorithmThe structure shows that the first thread to cross the barrier is the one which gets to enter the critical section. When there is no contention a thread can enter the critical section immediately. Indicate contending flag[i] := true Barrier victim := i no / maybe First to cross the barrier? victim = j ? Contention? flag[j] = true ? yes no yes critical section exit code flag[i] = false 
24 

Mutual ExclusionPeterson’s algorithm satisfies mutual exclusion 
25 

ProofAssume in the contrary that two threads can be in their critical section at the same time. From the code we see: (*) write0(flag[0]=true) ? write0(victim=0) ? read0(flag[1]) ? read0(victim) ? CS0 write1(flag[1]=true) ? write1(victim=1) ? read1(flag[0]) ? read1(victim) ? CS1 Thread 0 flag[0] = true victim = 0 while (flag[1] and victim == 0) {skip} critical section flag[0] = false Thread 1 flag[1] = true victim = 1 while (flag[0] and victim == 1) {skip} critical section flag[1] = false 
26 

ProofAssume that the last thread to write to victim was 0. Then: write1(victim=1) ? write0(victim=0) This implies that thread 0 read that victim=0 in equation (*) Since thread 0 is in the critical section, it must have read flag[1] as false, so: write0(victim=0) ? read0(flag[1]==false) Thread 0 flag[0] = true victim = 0 while (flag[1] and victim == 0) {skip} critical section flag[0] = false Thread 1 flag[1] = true victim = 1 while (flag[0] and victim == 1) {skip} critical section flag[1] = false 
27 

ProofThen, we get: write1(flag[1]=true) ? write1(victim=1) ? write0(victim=0) ? read0(flag[1]==false) Thus: write1(flag[1]=true) ? read0(flag[1]==false) There was no other write to flag[1] before the critical section execution and this yields a contradiction. Thread 0 flag[0] = true victim = 0 while (flag[1] and victim == 0) {skip} critical section flag[0] = false Thread 1 flag[1] = true victim = 1 while (flag[0] and victim == 1) {skip} critical section flag[1] = false 
28 

Starvation freedomPeterson’s algorithm is starvationfree 
29 

ProofAssume to the contrary that the algorithm is not starvationfree Then one of the threads, say thread 0, is forced to remain in its entry code forever Thread 0 flag[0] = true victim = 0 while (flag[1] and victim == 0) {skip} critical section flag[0] = false Thread 1 flag[1] = true victim = 1 while (flag[0] and victim == 1) {skip} critical section flag[1] = false 
30 

ProofThis implies that at some later point thread 1 will do one of the following three things: 1. Stay in its remainder forever 2. Stay in its entry code forever, not succeeding and proceeding into its critical section 3. Repeatedly enter and exit its critical section We’ll show that each of the three possible cases leads to a contradiction. Thread 0 flag[0] = true victim = 0 while (flag[1] and victim == 0) {skip} critical section flag[0] = false Thread 1 flag[1] = true victim = 1 while (flag[0] and victim == 1) {skip} critical section flag[1] = false 
31 

ProofIn the first case flag[1] is false, and hence thread 0 can proceed. The second case is impossible since victim is either 0 or 1, and hence it always enables at least one of the threads to proceed. In the third case, when thread 1 exit its critical section and tries to enter its critical section again, it will set victim to 1 and will never change it back to 0, enabling thread 0 to proceed. Thread 0 flag[0] = true victim = 0 while (flag[1] and victim == 0) {skip} critical section flag[0] = false Thread 1 flag[1] = true victim = 1 while (flag[0] and victim == 1) {skip} critical section flag[1] = false 
32 

Kessels’ singlewriter AlgorithmWhat if we replace the multiwriter register victim with two single writer registers. What is new algorithm? Answer (Kessels’ Alg.) victim = 0 ? victim[0] =victim[1] victim = 1 ? victim[0] ?victim[1] 
33 

Kessels’ singlewriter AlgorithmThread 0 flag[0] = true local[0] = victim[1] victim[0] = local[0] while (flag[1] and local[0]=victim[1]) {skip} critical section flag[0] = false Thread 1 flag[1] = true local[1]=1victim[0] victim[1] = local[1] while (flag[0] and local[1] ? victim[0])) {skip} critical section flag[1] = false Thread 0 can write the registers victim[0] and flag[0] and read the registers victim[1] and flag[1] Thread 1 can write the registers victim[1] and flag[1] and read the registers victim[0] and flag[0] 
34 

Solutions for Many ThreadsHow can we use a twothread algorithm to construct an algorithm for many threads? 
35 

Tournament Algorithms1 2 3 4 5 6 7 8 
36 

Tournament AlgorithmsA simple method which enables the construction an algorithm for n threads from any given algorithm for two threads. Each thread is progressing from the leaf to the root, where at each level of the tree it participates in a two thread mutual exclusion algorithm. As a thread advanced towards the root, it plays the role of thread 0 when it arrives from the left subtree, or of thread 1 when it arrives from the right subtree. 
37 

The Filter Algorithm for n ThreadsA direct generalization of Peterson’s algorithm to multiple threads. The Peterson algorithm used a twoelement boolean flag array to indicate whether a thread is interested in entering the critical section. The filter algorithm generalizes this idea with an Nelement integer level array, where the value of level[i] indicates the latest level that thread i is interested in entering. ncs cs level n1 
38 

FilterThere are n1 “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 level 0 level n1 
39 

The Filter AlgorithmThread i for (int L = 1; L < n; L++) { level[i] = L; victim[L] = i; while (($ k != i level[k] >= L) and victim[L] == i ) {} } critical section level[i] = 0; 
40 

FilterThread i for (int L = 1; L < n; L++) { level[i] = L; victim[L] = i; while (($ k != i level[k] >= L) and victim[L] == i ) {} } critical section level[i] = 0; One level at a time 
41 

FilterThread i for (int L = 1; L < n; L++) { level[i] = L; victim[L] = i; while (($ k != i level[k] >= L) and victim[L] == i ) {} } critical section level[i] = 0; Announce intention to enter level L 
42 

FilterThread i for (int L = 1; L < n; L++) { level[i] = L; victim[L] = i; while (($ k != i level[k] >= L) and victim[L] == i ) {} } critical section level[i] = 0; Give priority to anyone but me (at every level) 
43 

FilterThread i for (int L = 1; L < n; L++) { level[i] = L; victim[L] = i; while (($ k != i level[k] >= L) and victim[L] == i ) {} } critical section level[i] = 0; Wait as long as someone else is at same or higher level, and I’m designated victim. Thread enters level L when it completes the loop. 
44 

ClaimThere are at most nL threads enter level L Proof: by induction on L and by contradiction At L=0 – trivial Assume that there are at most nL+1 threads at level L1. Assume that there are nL+1 threads at level L Let A be the last thread to write victim[L] and B any other thread at level L 
45 

Proof structureB A ncs cs Assumed to enter L1 nL+1 = 4 nL+1 = 4 Last to write victim[L] By way of contradiction all enter L Show that A must have seen B at level L and since victim[L] == A could not have entered 
46 

ProofFrom the code we get: From the assumption: writeB(level[B]=L)?writeB(victim[L]=B) writeA(victim[L]=A)?readA(level[B]) writeB(victim[L]=B)?writeA(victim[L]=A) for (int L = 1; L < n; L++) { level[i] = L; victim[L] = i; while (($ k != i level[k] >= L) and victim[L] == i ) {} } critical section level[i] = 0; 
47 

ProofWhen combining all we get: Since B is at level L, when A reads level[B], it reads a value greater than or equal L and so A couldn’t completed its loop and still waiting (remember that victim=A), a contradiction. writeB(level[B]=L) ?readA(level[B]) for (int L = 1; L < n; L++) { level[i] = L; victim[L] = i; while (($ k != i level[k] >= L) and victim[L] == i ) {} } critical section level[i] = 0; 
48 

A conclusionThe filter algorithm satisfies mutual exclusion At level n1 there are at most n(n1)=1 threads, which means at most one thread in the critical section 
49 

StarvationfreedomFilter Lock satisfies properties: Just like Peterson algorithm at any level So no one starves 
50 

FairnessStarvation freedom guarantees that if a thread is trying to enter its critical section, it will eventually do so There is no guarantee about how long it will take We wish for fairness: if thread A enters the entry code before thread B, then A should enter the critical section first 
51 

Bounded waitingWe divide our method into two parts: Doorway interval:  Written DA  always finishes in finite steps Waiting interval:  Written WA  may take unbounded steps remainder entry code critical section exit code 
52 

The mutual exclusion problemMutual Exclusion Deadlockfreedom Starvationfreedom FIFO 
53 

rBounded WaitingFor threads A and B: If DAk ? DB j A’s kth doorway precedes B’s jth doorway Then CSAk ? CSBj+r A’s kth critical section precedes B’s (j+r)th critical section B cannot overtake A by more than r times Firstcomefirstserved means r = 0. 
54 

Fairness in Filter AlgorithmFilter satisfies properties: No one starves But very weak fairness Not rbounded for any r! That’s pretty lame… 
55 

Bakery AlgorithmThe idea is similar to a line at the bakery A customer takes a number greater than numbers of other customers Each of the threads gets a unique identifier 
56 

Bakery AlgorithmThread i flag[i]=true; number[i] = max(number[0], …,number[n1])+1; while ($ k!= i flag[k] && (number[i],i) > (number[k],k)) {}; critical section flag[i] = false; 
57 

Bakery Algorithmflag[i]=true; number[i] = max(number[0], …,number[n1])+1; while ($ k!= i flag[k] && (number[i],i) > (number[k],k)) {}; critical section flag[i] = false; Doorway 
58 

Bakery Algorithmflag[i]=true; number[i] = max(number[0], …,number[n1])+1; while ($ k!= i flag[k] && (number[i],i) > (number[k],k)) {}; critical section flag[i] = false; I’m interested 
59 

Bakery Algorithmflag[i]=true; number[i] = max(number[0], …,number[n1])+1; while ($ k!= i flag[k] && (number[i],i) > (number[k],k)) {}; critical section flag[i] = false; Take an number numbers are always increasing! 
60 

Bakery Algorithmflag[i]=true; number[i] = max(number[0], …,number[n1])+1; while ($ k!= i flag[k] && (number[i],i) > (number[k],k)) {}; critical section flag[i] = false; Someone is interested 
61 

Bakery Algorithmflag[i]=true; number[i] = max(number[0], …,number[n1])+1; while ($ k!= i flag[k] && (number[i],i) > (number[k],k)) {}; critical section flag[i] = false; There is someone with a lower number and identifier. pair (a,b) > (c,d) if a>c, or a=c and b>d (lexicographic order) 
62 

Deadlock freedomThe bakery algorithm is deadlock free Some waiting thread A has a unique least (number[A],A) pair, and that thread can enter the critical section 
63 

FIFOThe bakery algorithm is firstcomefirstserved If DA ? DB then A’s number is earlier writeA(number[A]) ? readB(number[A]) ? writeB(number[B]) ? readB(flag[A]) So B is locked out while flag[A] is true flag[i]=true; number[i] = max(number[0], …,number[n1])+1; while ($ k!= i flag[k] && (number[i],i) > (number[k],k)) {}; critical section flag[i] = false; 
64 

Starvation freedomThe bakery algorithm satisfies deadlock freedom and firstcomefirstserved and those properties implies starvation freedom 
65 

Mutual ExclusionSuppose A and B in CS together Suppose A has an earlier number When B entered, it must have seen flag[A] is false, or number[A] > number[B] flag[i]=true; number[i] = max(number[0], …,number[n1])+1; while ($ k!= i flag[k] && (number[i],i) > (number[k],k)) {}; critical section flag[i] = false; 
66 

Mutual Exclusionnumbers are strictly increasing so B must have seen (flag[A] == false) numberingB ? readB(flag[A]) ? writeA(flag[A]) ? numberingA Which contradicts the assumption that A has an earlier number flag[i]=true; number[i] = max(number[0], …,number[n1])+1; while ($ k!= i flag[k] && (number[i],i) > (number[k],k)) {}; critical section flag[i] = false; 
67 

The End 
«Нуль 1 класс петерсон» 