Synchronization Algorithms

and Concurrent Programming

Gadi Taubenfeld
Chapter 1
Introduction

Version: June 2014

Chapter 1 Synchronization Algorithms and Concurrent Programming 1
Gadi Taubenfeld © 2014
 Synchronization Algorithms
and Concurrent Programming
ISBN: 0131972596, 1st edition

A note on the use of these power-point slides:

I am making these slides freely available to all (faculty, students, readers).
They are in PowerPoint form so you can add, modify, and delete slides and slide
content to suit your needs. They obviously represent a lot of work on my part.
In return for use, I only ask the following:

q That you mention their source, after all, I would like people to use my book!
q That you note that they are adapted from (or perhaps identical to)
my slides, and note my copyright of this material.

Thanks and enjoy!

Gadi Taubenfeld
All material copyright 2014
Gadi Taubenfeld, All Rights Reserved

To get the most updated version of these slides go to:

[Link]
Chapter 1 Synchronization Algorithms and Concurrent Programming 2
Gadi Taubenfeld © 2014
 Synchronization
q Type of synchronization
Contention
m
m Coordination
q Why synchronization is Difficult?
m Easy between humans
m Communication between
computers is restricted
• reading and writing of notes
• sending and receiving messages

Chapter 1 Synchronization Algorithms and Concurrent Programming 3

Gadi Taubenfeld © 2014
 Too Much Milk
Section 1.2.2

Chapter 1 Synchronization Algorithms and Concurrent Programming 4

Gadi Taubenfeld © 2014
 The Too-Much-Milk Problem
Time Alice Bob
5:00 Arrive Home
5:05 Look in fridge; no
milk
5:10 Leave for grocery
5:15 Arrive home
5:20 Arrive at grocery Look in fridge; no milk
5:25 Buy milk Leave for grocery
5:30 Arrive home; put
milk in fridge
3:40 Buy milk
3:45 Arrive home; too much
milk!

Chapter 1 Synchronization Algorithms and Concurrent Programming 5

Gadi Taubenfeld © 2014
 Solving the Too-Much-Milk Problem

Correctness properties Communication primitives

q Mutual Exclusion: q Leave a note
Only one person buys (set a flag)
milk “at a time” q Remove a note
q Progress: (reset a flag)
Someone always buys q Read a note
milk if it is needed (test the flag)

Chapter 1 Synchronization Algorithms and Concurrent Programming 6

Gadi Taubenfeld © 2014
 Important Distinction

q Safety Property
m Nothing bad happens ever
m Example: mutual exclusion
q Liveness Property
m Something good happens eventually
m Example: progress

Chapter 1 Synchronization Algorithms and Concurrent Programming 7

Gadi Taubenfeld © 2014
 Solution 1
Alice Bob
if (no note) { if (no note) {
if (no milk) { if (no milk) {
leave Note leave Note
buy milk buy milk
remove note remove note
} }
} }

Does it work? C mutual exclusion

No, may end up with too üprogress
much milk.
Chapter 1 Synchronization Algorithms and Concurrent Programming 8
Gadi Taubenfeld © 2014
 Solution 2
Using labeled notes

Alice Bob
leave note A leave note B
if (no note B) { if (no note A) {
if (no milk) {buy milk} if (no milk) {buy milk}
} }
remove note A remove note B

Does it work? ümutual exclusion

No, may end up with no milk. C progress

Chapter 1 Synchronization Algorithms and Concurrent Programming 9

Gadi Taubenfeld © 2014
 Solution 3 Bob’s code is
as before

Alice Bob
leave note A leave note B
while (note B) {skip} if (no note A) {
if (no milk) {buy milk} if (no milk) {buy milk}
}
remove note A remove note B

Does it work? ümutual exclusion

No ! a timing assumption is needed C progress

Chapter 1 Synchronization Algorithms and Concurrent Programming 10

Gadi Taubenfeld © 2014
 Is solution #3 a good solution?
No

q A timing assumption is needed!

q Unfair to one of the processes
q It is asymmetric and complicated
q Alice is busy waiting – consuming CPU cycles
without accomplishing useful work

Chapter 1 Synchronization Algorithms and Concurrent Programming 11

Gadi Taubenfeld © 2014
 Alice code is
as before Solution 3+ BUT, Bob may
forever get stuck
in the repeat-until
Alice Bob loop !!!

leave note A repeat

while (note B) {skip} leave note B
Additional requirement [informal definition]
if (no milk) {buy milk} if (note A) {
Thirst-freedom: Nobody ever gets stuck forever.
remove note B;
(Both Alice and Bob eventually complete their programs.)
remove note A while (note A) {skip} }
until (note B)
if (no milk) {buy milk}
Does it work?
remove note B

Yes, BUT … ümutual exclusion

üprogress
Chapter 1 Synchronization Algorithms and Concurrent Programming 12
Gadi Taubenfeld © 2014
 Solution 4
Using 4 labeled notes

A1 A2 B2 B1

the fridge’s door

Chapter 1 Synchronization Algorithms and Concurrent Programming 13

Gadi Taubenfeld © 2014
 Solution 4
Notations

solid line without color:

we do not care if there is
a note

color: dotted line:

there is a note A1 A2
X B2
X B2 there is no note

Alice’s turn

who will buy milk ?

Chapter 1 Synchronization Algorithms and Concurrent Programming 14

Gadi Taubenfeld © 2014
 Solution 4

A1 A2
X B2
X B2 A1 A2 B2 B1 A1 A2 B2 B1

Alice’s turn Alice’s turn Alice’s turn

B2 A2
X B2
X B1 A1 A2 B2 B1 A1 A2 B2 B1

Bob’s turn Bob’s turn Bob’s turn

Chapter 1 Synchronization Algorithms and Concurrent Programming 15

Gadi Taubenfeld © 2014
 Solution 4
Alice Bob
leave A1 leave B1
if B2 {leave A2} else {remove A2} if (no A2) {leave B2} else {remove B2}
while B1 and ((A2 and B2) or while A1 and ((A2 and no B2) or
(no A2 and no B2)) (no A2 and B2))
{skip} {skip}
if (no milk) {buy milk} if (no milk) {buy milk}
remove A1 remove note B1

A correct, fair, symmetric algorithm!

ü mutual exclusion
ü progress
ü both Alice and Bob eventually
complete their programs
Chapter 1 Synchronization Algorithms and Concurrent Programming 16
Gadi Taubenfeld © 2014
 A variant of Solution 4
The order of the first two statements is replaced
Is it correct ?

Alice Bob
if B2 {leave A2} else {remove A2} if (no A2) {leave B2} else {remove B2}
leave A1 leave B1
while B1 and ((A2 and B2) or while A1 and ((A2 and no B2) or
(no A2 and no B2)) (no A2 and B2))
{skip} {skip}
if (no milk) {buy milk} if (no milk) {buy milk}
remove A1 MILK
remove note B1 MILK

No, may end up with two milk. C mutual exclusion

üprogress A1 B2 B1

Chapter 1 Synchronization Algorithms and Concurrent Programming 17

Gadi Taubenfeld © 2014
 Question
Alice and Bob have a daughter C.
Make it work for all the three of them.

In Chapter 2, we solve a generalization of

the too-much-milk problem, called the
mutual exclusion problem, for any number of
participants (not just two or three).

Chapter 1 Synchronization Algorithms and Concurrent Programming 18

Gadi Taubenfeld © 2014
 Question
x is an atomic register, initially 0 0

Process A Process B
for i = 1 to 5 { x:=x+1 } for i = 1 to 5 { x:=x+1 }

Q: What are all the possible values for x

after both processes terminate?

A: 2 through 10 inclusive.

Chapter 1 Synchronization Algorithms and Concurrent Programming 19

Gadi Taubenfeld © 2014
 The smallest value is 2

0 1 10 1
2

A B

4
3
5
2
0
1

Chapter 1 Synchronization Algorithms and Concurrent Programming 20

Gadi Taubenfeld © 2014
 Question
x is an atomic register, initially 0 0

Process A Process B Process C

x:=x+1; x:=x+1; x:=10
x:=x+1 x:=x+1

Q: What are all the possible values for x

after the three processes terminate?

A: 2,3,4,10,11,12,13,14.

Chapter 1 Synchronization Algorithms and Concurrent Programming 21

Gadi Taubenfeld © 2014
 The Coordinated Attack Problem
Section 1.2.3

Chapter 1 Synchronization Algorithms and Concurrent Programming 22

Gadi Taubenfeld © 2014
 The coordinated attack problem
• Blue army wins if both blue camps attack simultaneously
• Design an algorithm to ensure that both blue camps attack
simultaneously

1 2

Enemy

The problem is due to Jim Gray (1977)

Chapter 1 Synchronization Algorithms and Concurrent Programming 23
Gadi Taubenfeld © 2014
 The coordinated attack problem
• Communication is done by sending messengers across the valley
• Messengers may be lost or captured by the enemy L

1 2

Enemy

Chapter 1 Synchronization Algorithms and Concurrent Programming 24

Gadi Taubenfeld © 2014
 The coordinated attack problem
Theorem: There is no algorithm that solves the problem !

Proof:
• Assume to the contrary that such an algorithm exits.
• Let P be an algorithm that solves with fewest # of
messages, when no message is lost.
• P should work even when the last messenger is captured.
• So P should work even if the last messenger is never sent.
• But this is a new algorithm with one less message.
• A contradiction.
è The (asynchronous) model is too weak.

Chapter 1 Synchronization Algorithms and Concurrent Programming 25

Gadi Taubenfeld © 2014
 Synchronization
Contention vs. coordination

Chapter 1 Synchronization Algorithms and Concurrent Programming 26

Gadi Taubenfeld © 2014
 Synchronization
Contention Coordination
m Too-much-milk (1) m The coordinated attack (1)
m mutual exclusion (2,3,4)
m barrier synchronization (5)
m Concurrent Data
m Concurrent Data
Structures (4)
Structures (4)
m l-exclusion (6)
m producer-consumer (8)
m multiple resources:
dinning philosophers (7) m Choice Coordination (8)

m readers & writer (8) m Consensus (data

m group-exclusions (8) coordination) (9)
m ... m ....

(The numbers refer to chapters in the book.)

Chapter 1 Synchronization Algorithms and Concurrent Programming 27

Gadi Taubenfeld © 2014
 Chapters 2+3
The mutual exclusion problem

The first problem we cover in detail.

A generalization of the too-much-milk problem.

Chapter 1 Synchronization Algorithms and Concurrent Programming 28

Gadi Taubenfeld © 2014
 Chapter 4

Blocking and Non-blocking Synchronization

Concurrent data structures
counter, stack, queue, link list

P1 P2 P3

data structure

Chapter 1 Synchronization Algorithms and Concurrent Programming 29

Gadi Taubenfeld © 2014
 Chapter 4

Blocking

P1 P2 P3

data structure

Chapter 1 Synchronization Algorithms and Concurrent Programming 30

Gadi Taubenfeld © 2014
 Chapter 4

Non-blocking

P1 P2 P3

data structure

Chapter 1 Synchronization Algorithms and Concurrent Programming 31

Gadi Taubenfeld © 2014
 Coarse-Grained Locking

Easier to program, but not scalable.

Chapter 1 Synchronization Algorithms and Concurrent Programming 32

Gadi Taubenfeld © 2014
 Fine-Grained Locking

Efficient and scalable, but

too complicated (deadlocks, etc.).
Chapter 1 Synchronization Algorithms and Concurrent Programming 33
Gadi Taubenfeld © 2014
 Chapter 5

Barrier Synchronization

P1 P1 P1

P2 P2 P2

Barrier

Barrier

Barrier
P3 P3 P3
P4 P4 P4

time

four processes all except Once all

approach the P4 arrive arrive, they
barrier continue

Chapter 1 Synchronization Algorithms and Concurrent Programming 34

Gadi Taubenfeld © 2014
 Example: Prefix Sum

begin a b c d e f

time

a+b+c a+b+c
end a a+b a+b+c a+b+c+d
+d+e +d+e+f
Chapter 1 Synchronization Algorithms and Concurrent Programming 35
Gadi Taubenfeld © 2014
 Example: Sequential Prefix Sum

begin a b c d e f

a a+b c d e f

a a+b a+b+c d e f
time

a a+b a+b+c a+b+c+d e f

a a+b a+b+c a+b+c+d a+b+c+d+e f

a+b+c a+b+c
end a a+b a+b+c a+b+c+d
+d+e +d+e+f
Chapter 1 Synchronization Algorithms and Concurrent Programming 36
Gadi Taubenfeld © 2014
 Example: Parallel Prefix Sum

begin a b c d e f

a a+b b+c c+d d+e e+f

time

a a+b a+b+c a+b+c+d b+c+d+e c+d+e+f

a+b+c a+b+c
end a a+b a+b+c a+b+c+d
+d+e +d+e+f
Chapter 1 Synchronization Algorithms and Concurrent Programming 37
Gadi Taubenfeld © 2014
 Example: Parallel Prefix Sum

begin a b c d e f

barrier

a a+b b+c c+d d+e e+f

time
barrier

a a+b a+b+c a+b+c+d b+c+d+e c+d+e+f

a+b+c a+b+c
end a a+b a+b+c a+b+c+d
+d+e +d+e+f
Chapter 1 Synchronization Algorithms and Concurrent Programming 38
Gadi Taubenfeld © 2014
 Chapter 9

Consensus

1 0 1 1 0 1 0

1 1 1 1 1 1 1

requirements:
q validity
q agreement
q termination

Chapter 1 Synchronization Algorithms and Concurrent Programming 39

Gadi Taubenfeld © 2014
 Impossibility of Consensus
with One Faulty Process

Theorem: There is no algorithm that solve the

consensus problem using atomic read/write registers
in the presence of a single faulty process.

We give a detailed proof of this important result in

Chapter 9 of the book.

What can be done?

q Strong primitives.

q Timing assumptions.
q Randomizations.

Chapter 1 Synchronization Algorithms and Concurrent Programming 40

Gadi Taubenfeld © 2014
 Models of Computation
Section 1.4

Chapter 1 Synchronization Algorithms and Concurrent Programming 41

Gadi Taubenfeld © 2014
 Communication
models of computation

Concurrent programming è Shared memory

m safe registers
m atomic registers (read/write)
m test&set
m swap
m compare-and-swap
m load-link/store-conditional
m read-modify-write
m semaphore
m monitor

What is the relative power of these communication primitives?

Answer: see Chapter 9.

Chapter 1 Synchronization Algorithms and Concurrent Programming 42

Gadi Taubenfeld © 2014
 Communication
models of computation

Message passing
m send/receive
m multi-cast
m broadcast
m network topology

Distributed message passing systems

are not covered in the book

Chapter 1 Synchronization Algorithms and Concurrent Programming 43

Gadi Taubenfeld © 2014
 Time
models of computation

This book

Synchronous Partially Asynchronous

(CRCW, EREW) synchronous • less powerful
• extremely powerful
• realistic
• unrealistic

Parallel Concurrent/
Distributed
What is the relative power of these timing models?

Chapter 1 Synchronization Algorithms and Concurrent Programming 44

Gadi Taubenfeld © 2014
 Shared Memory Models
models of computation

P ... P P ... P P ... P

C C M M

M M

Simple Coherent Distributed

Shared Caching Shared
Memory Memory

Chapter 1 Synchronization Algorithms and Concurrent Programming 45

Gadi Taubenfeld © 2014
 Fault-tolerance
models of computation

What can fail? How many can fail ?

m processes m constant, n/3, ...
m shared memory
m links Wait-freedom,
Non-blocking,
Type of faults Lock-freedom
m crash m what is it ?
m omission
m Byzantine Self-stabilization
m what is it ?

Chapter 1 Synchronization Algorithms and Concurrent Programming 46

Gadi Taubenfeld © 2014
 Processes & Concurrency
models of computation

q # of Processes: known, unknown, infinite

Chapter 1 Synchronization Algorithms and Concurrent Programming 47

Gadi Taubenfeld © 2014
 Processes & Concurrency
models of computation

q Processes: known, unknown, infinite

q Concurrency: finite, bounded, unbounded

Chapter 1 Synchronization Algorithms and Concurrent Programming 48

Gadi Taubenfeld © 2014
 Processes & Concurrency
models of computation

q Processes: known, unknown, infinite

q Concurrency: finite, bounded, unbounded
q Faults: known, unknown

Chapter 1 Synchronization Algorithms and Concurrent Programming 49

Gadi Taubenfeld © 2014
 Processes & Concurrency
models of computation

q Processes: known, unknown, infinite

q Concurrency: finite, bounded, unbounded
q Faults: known, unknown
q Participation: required / not required

Chapter 1 Synchronization Algorithms and Concurrent Programming 50

Gadi Taubenfeld © 2014
 Model Summary
q Multiple processes (or threads)
q Shared memory
q Communication via shared objects
q Unpredictable asynchronous delays

q Cover all the classical synchronization problems

q Focus more on principles, less on performance
q Look for simple elegant short algorithms

Chapter 1 Synchronization Algorithms and Concurrent Programming 51

Gadi Taubenfeld © 2014
 Processes, Threads and Scheduling
Section 1.5

Chapter 1 Synchronization Algorithms and Concurrent Programming 52

Gadi Taubenfeld © 2014
 Terminology

q Hardware
m Processors
q Software
m Threads, processes
q Sometimes OK to confuse them,
sometimes not.
q Scheduler

Chapter 1 Synchronization Algorithms and Concurrent Programming 53

Gadi Taubenfeld © 2014
 Processes and Threads
A process is a program in execution

Process 1 Process 1 Process 1 Process

User
space

Threads Threads

Kernel
space Kernel Kernel

Three processes each with One process with three threads

one or more threads

In this book it is always ok to confuse between processes and threads.

Chapter 1 Synchronization Algorithms and Concurrent Programming 54

Gadi Taubenfeld © 2014
 Processes and Threads
A process is a program in execution

q Shared by all threads in a process

m Address space, global variables, open files, ...
q Private to each thread
m Program counter, registers, stack.
q User-level threads
m Thread management is done by the application.
q Kernel-level threads
m Threads are managed by the kernel (but run in
user space).

Chapter 1 Synchronization Algorithms and Concurrent Programming 55

Gadi Taubenfeld © 2014
 Five states a process can be in

CPU scheduler picks CPU scheduler picks

this process another process

admit exit
New Ready Running terminated

event waits for I/O

occurs or other event
Blocked

Chapter 1 Synchronization Algorithms and Concurrent Programming 56

Gadi Taubenfeld © 2014
 Processes and Scheduling

0 1 n -1 n

Scheduler

q Non-preemptive º the scheduler can not

interrupt a running process.
q Preemptive º the scheduler can interrupt
a running process.

Chapter 1 Synchronization Algorithms and Concurrent Programming 57

Gadi Taubenfeld © 2014
 Scheduling Algorithms

q First-come-first-served
schedules processes in the order they become ready.
q Shortest-job-first
schedule the process with the shortest time.
q Priority scheduling
schedule the process with the highest priority.
q Round robin –
each process is scheduled for a small number of time
units (milliseconds).
q Many other possibilities exist.

Chapter 1 Synchronization Algorithms and Concurrent Programming 58

Gadi Taubenfeld © 2014
 Scheduling
The Priority Inversion Problem

q Process P1 with priority 5 enters its CS,

and is preempted before releasing it.
q Process P2 with priority 10 is scheduled but
can not enter its CS and busy-waits.
q Process P1 wants to release its critical
section (to enable P2 to enter) but never
gets scheduled.

In the sequel, we will assume that

processes have the same priority.

Chapter 1 Synchronization Algorithms and Concurrent Programming 59

Gadi Taubenfeld © 2014
 Problems & Models
Problems Models

mutex
read/write

barrier test&set

readers&
swap
writers

consensus LL/SC

q Algorithms
q Upper and lower bounds
q Impossibility results
q Simulations & Implementations

Chapter 1 Synchronization Algorithms and Concurrent Programming 60

Gadi Taubenfeld © 2014
 The Mutual Exclusion Problem
The first problem we cover in detail
A generalization of the too-much-milk problem

Chapter 1 Synchronization Algorithms and Concurrent Programming 61

Gadi Taubenfeld © 2014
 The mutual exclusion problem

remainder 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 deadlock-freedom
properties are satisfied.

Chapter 1 Synchronization Algorithms and Concurrent Programming 62

Gadi Taubenfeld © 2014
 The mutual exclusion problem
q Mutual Exclusion: No two processes are in
their critical section at the same time.

remainder
q Deadlock-freedom: If a process is trying
to enter its critical section, then some
process, not necessarily the same one, entry code
eventually enters its critical section.
critical
q Starvation-freedom: If a process is section
trying to enter its critical section, then
this process must eventually enter its
exit code
critical section.

Chapter 1 Synchronization Algorithms and Concurrent Programming 63

Gadi Taubenfeld © 2014
 Question: true or false ? Algorithm C

Algorithm A Algorithm B remainder

entry code of A

remainder entry code of B

entry code critical

section
critical exit code of B
section
exit code exit code of A

Chapter 1 Synchronization Algorithms and Concurrent Programming 64

Gadi Taubenfeld © 2014
 Question: true or false ? Algorithm C

q A and B are deadlock-free è C is

deadlock-free. remainder
q A and B are starvation-free è C is
starvation-free. entry code of A
q A or B satisfies mutual exclusion è
C satisfies mutual exclusion. entry code of B
q A is deadlock-free and B is critical
starvation-free è C is starvation- section
free. exit code of B
q A is starvation-free and B is
deadlock-free è C is starvation- exit code of A
free.

Chapter 1 Synchronization Algorithms and Concurrent Programming 65

Gadi Taubenfeld © 2014
 Properties & complexity
q Time complexity
m Fast
m Adaptive
q Fairness
m FIFO, ...
q Fault-tolerance
q Local-spinning
q Space complexity
q Communication primitives

Chapter 1 Synchronization Algorithms and Concurrent Programming 66

Gadi Taubenfeld © 2014
 Complexity Measures
q Counting steps
m process step complexity
m process time complexity
m contention-free time complexity
q Counting time units
m system response time
m process response time
q Counting communications
m distributed shared memory
m coherent caching
q Space complexity

Chapter 1 Synchronization Algorithms and Concurrent Programming 67

Gadi Taubenfeld © 2014
 History of the mutex problem
q 1965
m Defined by Dijkstra
m First solution by Dekker
m General solution by Dijkstra
q Fischer, Knuth, Lynch, Rabin, Rivest, ...
q 1974 Lamport’s bakery algorithm
q 1981 Peterson’s solution
q There are hundreds of published
solutions
E. W. Dijkstra
[Link]/users/EWD/ q Lots of related problems
(Photo by Hamilton Richards 2002)

Chapter 1 Synchronization Algorithms and Concurrent Programming 68

Gadi Taubenfeld © 2014
 Next Chapter
In Chapter 2 we will start looking
at basic solutions to the mutual
exclusion problem using atomic
registers.

-- Gadi

Chapter 1 Synchronization Algorithms and Concurrent Programming 69

Gadi Taubenfeld © 2014