1 of 81

Mutual Exclusion

Companion slides for

The Art of Multiprocessor Programming

by Maurice Herlihy & Nir Shavit

2 of 81

Mutual Exclusion

Formal problem definitions
Solutions for 2 threads
Solutions for n threads
Fair solutions
Inherent costs

Art of Multiprocessor Programming

2

3 of 81

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

Art of Multiprocessor Programming

3

4 of 81

Events

An event a₀ of thread A is

Instantaneous
No simultaneous events (break ties)

Art of Multiprocessor Programming

4

time

a₀

5 of 81

Threads

A thread A is (formally) a sequence a₀, a₁, ...of events

“Trace” model
Notation: a₀ 🡺 a₁indicates order

Art of Multiprocessor Programming

5

time

a₀

a₁

a₂

…

6 of 81

Example Thread Events

Assign to shared variable
Assign to local variable
Invoke method
Return from method
Lots of other things …

Art of Multiprocessor Programming

6

7 of 81

Threads are State Machines

Art of Multiprocessor Programming

7

Events are transitions

a₀

a₁

a₂

a₃

8 of 81

States

Thread State

Program counter
Local variables

System state

Object fields (shared variables)
Union of thread states

Art of Multiprocessor Programming

8

9 of 81

Concurrency

Thread A

Thread B

Art of Multiprocessor Programming

9

time

10 of 81

Interleavings

Events of two or more threads

Interleaved
Not necessarily independent (why?)

Art of Multiprocessor Programming

10

time

11 of 81

Intervals

An interval A₀=(a₀,a₁) is

Time between events a₀and a₁

Art of Multiprocessor Programming

11

time

a₀

a₁

A₀

12 of 81

Intervals may Overlap

Art of Multiprocessor Programming

12

time

a₀

a₁

A₀

b₀

b₁

B₀

13 of 81

Intervals may be Disjoint

Art of Multiprocessor Programming

13

time

a₀

a₁

A₀

b₀

b₁

B₀

14 of 81

Precedence

Interval A₀ precedes interval B₀

Art of Multiprocessor Programming

14

time

a₀

a₁

A₀

b₀

b₁

B₀

A₀🡺 B₀

15 of 81

Precedence

Notation: A₀🡺 B₀
Formally,

End event of A₀ before start event of B₀
Also called “happens before” or “precedes”

Art of Multiprocessor Programming

15

16 of 81

Precedence Ordering

Never true that A🡺 A
If A🡺Bthen not true that B🡺A
If A🡺B& B🡺Cthen A🡺C
Funny thing: A🡺B& B🡺Amight both be false!

Art of Multiprocessor Programming

16

17 of 81

Partial Orders�(review)

Irreflexive:

Never true that A🡺 A

Antisymmetric:

If A🡺 Bthen not true that B🡺 A

Transitive:

If A🡺 B& B🡺 Cthen A🡺 C

Art of Multiprocessor Programming

17

18 of 81

Total Orders�(review)

Also

Irreflexive
Antisymmetric
Transitive

Except that for every distinct A, B,

Either A🡺 Bor B🡺 A

Art of Multiprocessor Programming

18

19 of 81

Repeated Events

while (mumble) {

a₀; a₁;

}

Art of Multiprocessor Programming

19

a₀^k

k-th occurrence of event a₀

A₀^k

k-th occurrence of interval A₀=(a₀,a₁)

20 of 81

Implementing a Counter

Art of Multiprocessor Programming

20

public class Counter {

private long value;

public long getAndIncrement() {

temp = value;

value = temp + 1;

return temp;

}

Make these steps indivisible using locks

21 of 81

Locks (Mutual Exclusion)

Art of Multiprocessor Programming

21

public interface Lock {

public void lock();

public void unlock();

}

22 of 81

Locks (Mutual Exclusion)

Art of Multiprocessor Programming

22

public interface Lock {

public void lock();

public void unlock();

}

acquire lock

23 of 81

Locks (Mutual Exclusion)

Art of Multiprocessor Programming

23

public interface Lock {

public void lock();

public void unlock();

}

release lock

acquire lock

24 of 81

Using Locks

Art of Multiprocessor Programming

24

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;

}}

25 of 81

Using Locks

Art of Multiprocessor Programming

25

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

26 of 81

Using Locks

Art of Multiprocessor Programming

26

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)

27 of 81

Using Locks

Art of Multiprocessor Programming

27

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

28 of 81

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

Art of Multiprocessor Programming

28

CS_i^k 🡺 CS_j^m

CS_j^m 🡺 CS_i^k

29 of 81

Deadlock-Free

If some thread calls lock()

And never acquires the lock
Then other threads must complete lock() and unlock() calls infinitely often

System as a whole makes progress

Even if individuals starve

Art of Multiprocessor Programming

29

30 of 81

Starvation-Free

If some thread calls lock()

It will eventually acquire the lock

Individual threads make progress

Art of Multiprocessor Programming

30

31 of 81

Two-Thread vs n -Thread Solutions

2-thread solutions first

Illustrate most basic ideas
Fits on one slide

Then n-thread solutions

Art of Multiprocessor Programming

31

32 of 81

The ThreadID class

Art of Multiprocessor Programming

32

public class ThreadID {

static final AtomicInteger idSeq =

new AtomicInteger(0);

static final ThreadLocal<Integer> idStore =

new ThreadLocal<>() {

@Override

protected Integer initialValue() {

return idSeq.getAndIncrement();

}

};

public static int get() {

return idStore.get();

}

33 of 81

Two-Thread Conventions

Art of Multiprocessor Programming

33

class … implements Lock {

…

// thread-local index, 0 or 1

public void lock() {

int i = ThreadID.get();

int j = 1 - i;

…

}

34 of 81

Two-Thread Conventions

Art of Multiprocessor Programming

34

class … implements Lock {

…

// thread-local index, 0 or 1

public void lock() {

int i = ThreadID.get();

int j = 1 - i;

…

}

Henceforth: i is current thread, j is other thread

LockOne Satisfies Mutual Exclusion

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

((flag[i]==true && flag[j]==false)

&& (flag[j]==true && flag[i]==false))==true

Art of Multiprocessor Programming

39

40 of 81

Deadlock Freedom

LockOne Fails deadlock-freedom

Concurrent execution can deadlock

Sequential executions OK

Art of Multiprocessor Programming

40

flag[i] = true; flag[j] = true;

while (flag[j]){} while (flag[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

Art of Multiprocessor Programming

45

public void LockTwo() {

victim = i;

while (victim == i) {};

}

46 of 81

Peterson’s Algorithm

Art of Multiprocessor Programming

46

public void lock() {

flag[i] = true;

victim = i;

while (flag[j] && victim == i) {};

}

public void unlock() {

flag[i] = false;

}

47 of 81

Peterson’s Algorithm

Art of Multiprocessor Programming

47

public void lock() {

flag[i] = true;

victim = i;

while (flag[j] && victim == i) {};

}

public void unlock() {

flag[i] = false;

}

Announce I’m interested

48 of 81

Peterson’s Algorithm

Art of Multiprocessor Programming

48

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

49 of 81

Peterson’s Algorithm

Art of Multiprocessor Programming

49

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

50 of 81

Peterson’s Algorithm

Art of Multiprocessor Programming

50

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

51 of 81

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

Art of Multiprocessor Programming

51

public void lock() {

…

while (flag[j] && victim == i) {};

52 of 81

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

Art of Multiprocessor Programming

52

public void lock() {

flag[i] = true;

victim = i;

while (flag[j] && victim == i) {};

}

public void unlock() {

flag[i] = false;

}

53 of 81

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

Art of Multiprocessor Programming

53

ncs

cs

54 of 81

Filter

Art of Multiprocessor Programming

54

class Filter implements Lock {

int[] level; // level[i] for thread i

int[] victim; // victim[L] for level L

public Filter(int n) {

int i = ThreadID.get();

level = new int[n];

victim = new int[n];

for (int i = 1; i < n; i++) {

level[i] = 0;

}}

…

}

level

victim

n-1

0

1

0

4

2

Thread 2 at level 4

0

4

55 of 81

Filter

Art of Multiprocessor Programming

55

class Filter implements Lock {

…

public void lock(){

int i = ThreadID.get();

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;

}}

56 of 81

Filter

Art of Multiprocessor Programming

56

class Filter implements Lock {

…

public void lock() {

int i = ThreadID.get();

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;

}}

One level at a time

57 of 81

Filter

Art of Multiprocessor Programming

57

class Filter implements Lock {

…

public void lock() {

int i = ThreadID.get();

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;

}}

Announce intention to enter level L

58 of 81

Filter

Art of Multiprocessor Programming

58

class Filter implements Lock {

int level[n];

int victim[n];

public void lock() {

int i=ThreadID.get();

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;

}}

Give priority to anyone but me

59 of 81

Filter

Art of Multiprocessor Programming

59

class Filter implements Lock {

int level[n];

int victim[n];

public void lock() {

int i = ThreadID.get();

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;

}}

Wait as long as someone else is at same or higher level, and I’m designated victim

60 of 81

Filter

Art of Multiprocessor Programming

60

class Filter implements Lock {

int level[n];

int victim[n];

public void lock() {

int i=ThreadID.get();

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;

}}

Thread enters level L when it completes the loop

61 of 81

Claim

Start at level L=1
At most n-L threads enter level L
Mutual exclusion at level L=n

Art of Multiprocessor Programming

61

ncs

cs

L=n-1

L=2

L=n-2

L=1

62 of 81

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

Art of Multiprocessor Programming

62

63 of 81

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 ….

Art of Multiprocessor Programming

63

64 of 81

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

Art of Multiprocessor Programming

64

65 of 81

First-Come-First-Served

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

Art of Multiprocessor Programming

65

66 of 81

Fairness Again

Filter Lock satisfies properties:

No one starves
But very weak fairness

Can be overtaken arbitrary # of times

That’s pretty lame…

Art of Multiprocessor Programming

66

67 of 81

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

Art of Multiprocessor Programming

67

68 of 81

Bakery Algorithm

Art of Multiprocessor Programming

68

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;

}

…

69 of 81

Bakery Algorithm

Art of Multiprocessor Programming

69

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

t

f

t

2

f

0

5

0

4

0

6

CS

Bakery Algorithm

Art of Multiprocessor Programming

75

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

With lower (label,i) in lexicographic order

76 of 81

Bakery Algorithm

Art of Multiprocessor Programming

76

class Bakery implements Lock {

…

public void unlock() {

flag[i] = false;

}

77 of 81

Bakery Algorithm

Art of Multiprocessor Programming

77

class Bakery implements Lock {

…

public void unlock() {

flag[i] = false;

}

No longer interested

labels are always increasing

78 of 81

No Deadlock

There is always one thread with earliest label
Ties are impossible (why?)

Art of Multiprocessor Programming

78

79 of 81

First-Come-First-Served

If D_A 🡺 D_Bthen 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 is locked out while flag[A] is true

Art of Multiprocessor Programming

79

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));

}

80 of 81

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]

(either impossible)

Art of Multiprocessor Programming

80

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));

}

81 of 81

Art of Multiprocessor Programming

81

�This work is licensed under a 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.