 Process Synchronization

Dr. Manmath N. Sahoo

Dept. of CSE, NIT Rourkela
Race Condition
 A condition when several processes access and manipulate
the same data-item; and final result depends on the order of
access.

withdraw (account, amount)

Execution flow on CPU

balance =
{
get_balance(account);
balance = balance -= amount;
get_balance(account); context switch
balance = balance - amount; balance =
get_balance(account);
put balance(account,
balance -= amount;
balance);
put_balance(account,
} balance); context switch
put_balance(account,
balance);

NIT Rourkela Dr. Manmath N. Sahoo (CS) 2

Critical Section
 Critical Section is a section of code where some
shared variable(s) is/are modified.
do {
...
...
entry section

critical section

exit section
reminder section
} while (TRUE);

Fig: General structure of a typical process with critical section

NIT Rourkela Dr. Manmath N. Sahoo (CS) 3

Solution to Critical-Section Problem
Criteria
 Mutual Exclusion – No more than one process
simultaneously inside CS.
 Progress –
 CS is free
 some processes wish to enter their CS then
 the selection of the process that will enter the CS next cannot be postponed
indefinitely
 Bounded Waiting – A bound must exist on the number of
times that other processes are allowed to enter their CS after
a process has made a request to enter its CS.

NIT Rourkela Dr. Manmath N. Sahoo (CS) 4

Two Processes: Solution – 1
 int turn
 shared between processes P1 and P2
 initialized to 1 or 2

P1 P2
do { do {

while(turn ≠ 1); while(turn ≠ 2);

critical section critical section

turn = 2; turn = 1;
reminder section reminder section
} while(TRUE) } while(TRUE)

NIT Rourkela Dr. Manmath N. Sahoo (CS) 5

Two Processes: Solution – 1
 Mutual Exclusion: Satisfied.
 Progress: Not Satisfied.
 turn=1 and P1 enters to its critical section.
 P1 makes turn=2 in its exit section.
 P1 wishes to enter to critical section but can’t.
 Bounded waiting: Satisfied

NIT Rourkela Dr. Manmath N. Sahoo (CS) 6

Two Processes: Solution – 2
 int flag[2] //initialized to FALSE

P1 P2
do { do {

flag[1] = TRUE; flag[2] = TRUE;

while(flag[2]); while(flag[1]);

critical section critical section

flag[1] = FALSE; flag[2] = FALSE;

reminder section reminder section

} while(TRUE) } while(TRUE)

NIT Rourkela Dr. Manmath N. Sahoo (CS) 7

Two Processes: Solution – 2
 Mutual Exclusion: Satisfied.
 Progress: Not Satisfied.
 P1 makes flag[1]=TRUE
 P2 makes flag[2]=TRUE

P1 can’t enter P2 can’t enter

 Bounded waiting: Satisfied

NIT Rourkela Dr. Manmath N. Sahoo (CS) 8
Two Processes: Solution – 3
P1 P2
do { do {

while(flag[2]); while(flag[1]);
flag[1] = TRUE; flag[2] = TRUE;

critical section critical section

flag[1] = FALSE; flag[2] = FALSE;

reminder section reminder section

} while(TRUE) } while(TRUE)

NIT Rourkela Dr. Manmath N. Sahoo (CS) 9

Two Processes: Solution – 3
 Mutual Exclusion: Not Satisfied.
 while(flag[2]); -- Pass
 while(flag[1]); -- Pass
 P1 makes flag[1] = TRUE; and enters into critical section
 P1 makes flag[2] = TRUE; and enters into critical section
 Progress: Satisfied.
 Bounded waiting: Not Satisfied
 P1 may continuously enter into the critical section even
when P2 is waiting in its while loop

NIT Rourkela Dr. Manmath N. Sahoo (CS) 10

 Two Processes: Solution – 4
[Peterson’s Solution]

P1 P2
do{ do{

flag[1] = TRUE; flag[2] = TRUE;

turn = 2; turn = 1;
while(flag[2] && turn==2); while(flag[1] && turn==1);
critical section critical section
flag[1] = FALSE; flag[2] = FALSE;

reminder section reminder section

} while(TRUE) } while(TRUE)

NIT Rourkela Dr. Manmath N. Sahoo (CS) 11

Two Processes: Solution – 4
[Peterson’s Solution]
 Mutual Exclusion: Satisfied.
 Progress: Satisfied.
 Bounded waiting: Satisfied

NIT Rourkela Dr. Manmath N. Sahoo (CS) 12

Multiple Processes Solution
[Bakery Algorithm]
 Smallest token no. will be served first

Token Counter Food Counter

NIT Rourkela Dr. Manmath N. Sahoo (CS) 13

Shared variables
int number[0:n-1]; //initialized to 0

Pi
do{

number[i] = max(number[0:n-1])+1

for j = 0 to n-1 {
while( number[j] && (number[j] < number[i] );
}

critical section

number[i]=0;
reminder section
} while(TRUE)

NIT Rourkela Numbers of multiple processes may be same => mutual exclusion will be violated14
Shared variables
int number[0:n-1]; //initialized to 0

Pi
do{

number[i] = max(number[0:n-1])+1

for j = 0 to n-1 {
while( number[j] && (number[j],pid[j]) < (number[i],pid[i]) );
}

critical section

number[i]=0;
reminder section
} while(TRUE)

NIT Rourkela mutual exclusion will be violated still 15

Shared variables
int number[0:n-1]; //initialized to 0
bool choosing[0:n-1] //initialized to false
Pi
do{
choosing[i] = TRUE;
number[i] = max(number[0:n-1])+1
choosing[i] = FALSE;
for j = 0 to n-1 {
while(choosing[j]);
while( number[j] && (number[j],j) < (number[i],i) );
}

critical section

number[i]=0;
reminder section
} while(TRUE)

NIT Rourkela Dr. Manmath N. Sahoo (CS) 16

Hardware Solutions to Critical Sections
 Test-and-set instruction
 Swap instruction

Motivating example why SW based solutions are not preferred:

while(true){
Not atomic; hence violates
while(lock != false); Mutual Exclusion
lock=true
Critical section
lock = false
…reminder section
}
NIT Rourkela Dr. Manmath N. Sahoo (CS) 17
Test-and-Set instruction
 Test-and-set instruction - defined below as if it
were a function
boolean Test-and-Set (boolean *target){
boolean rv = *target; // return value
*target = true; // set value of target
return(rv);
}

NIT Rourkela Dr. Manmath N. Sahoo (CS) 18

Test-and-Set instruction: Solution1
Pi  Shared lock initialized to
do{ FALSE.
while(Test-and-Set(&lock));  Mutual exclusion: YES

critical section
 Progress: YES
 Bounded waiting: NO
lock = FALSE;

reminder section
} while(TRUE)

NIT Rourkela Dr. Manmath N. Sahoo (CS) 19

Test-and-Set instruction: Solution2
 Variables used:
 global boolean waiting[n] //initialized to FALSE
 global boolean lock //initialized to FALSE
 local keyi

NIT Rourkela Dr. Manmath N. Sahoo (CS) 20

Test-and-Set instruction: Solution2
Pi  Mutual exclusion: YES
do{  Progress: YES
waiting[i] = TRUE; keyi = TRUE;  Bounded waiting: YES
while(waiting[i] && keyi)
keyi = Test-and-Set(&lock);
waiting[i]=FALSE;
critical section
j = (i+1) % n;
while(j!=i && waiting[j]==FALSE)
j = (j+1) % n;
if(j==i)
lock = FALSE;
else waiting[j] = FALSE;

reminder section
} while(TRUE)

NIT Rourkela Dr. Manmath N. Sahoo (CS) 21

Swap Instruction
 Swap instruction - defined below as if it were a
function
boolean Swap (boolean *a, *b){
boolean temp = *a;
*a = *b;
*b = temp;
}

NIT Rourkela Dr. Manmath N. Sahoo (CS) 22

Swap Instruction: Solution1
 Mutual exclusion: YES
 global boolean lock;
 Progress: YES
 local boolean keyi;
 Bounded waiting: NO
 lock & keyi initialized to FALSE

Pi Pj
do{ do{
keyi = TRUE; keyj = TRUE;
while(keyi) while(keyj)
Swap(&lock, &keyi); Swap(&lock, &keyj);
critical section critical section
lock = FALSE; lock = FALSE;

reminder section reminder section

} while(TRUE) } while(TRUE)

NIT Rourkela Dr. Manmath N. Sahoo (CS) 23

Swap instruction: Solution2
Pi  Mutual exclusion: YES
do{  Progress: YES
waiting[i] = TRUE; key = TRUE;  Bounded waiting: YES
while(waiting[i] && key)
Swap(&lock, &key);
waiting[i]=FALSE;

critical section
j = (i+1) % n;
while(j!=i && waiting[j]==FALSE)
j = (j+1) % n;
if(j==i)
lock = FALSE;
else waiting[j] = FALSE;

reminder section
} while(TRUE)

NIT Rourkela Dr. Manmath N. Sahoo (CS) 24

Semaphore
 A synchronization primitive proposed by
Dijkstra in 1968.
 Consists of an integer value
 Two operations
 P(S) or wait(S): waits for semaphore to become positive
 V(S) or signal(S): increments semaphore by 1
 P(S) and V(S) operations are atomic.
 Two Types: (i) Binary (ii) Counting

NIT Rourkela Dr. Manmath N. Sahoo (CS) 25

Binary Semaphore:
Spin-Lock/Busy-Wait Solution
 Can take two values: 1 or 0 (initialized to 1)
Struct Semaphore{ int value; };
Semaphore mutex;
mutex.value=1;
Pi
P(mutex)
do{
while(mutex.value ==
0);
mutex.value=0; V(mutex)
critical section
mutex.value++;  Mutual exclusion: YES
reminder section  Progress: YES
} while(TRUE)
 Bounded waiting: NO
NIT Rourkela Dr. Manmath N. Sahoo (CS) 26
Binary Semaphore:
Solution with Waiting List
Struct Semaphore{ Pi
int value; do{
Struct Process *List; if(mutex.value == 0){
}; Add Pi to mutex->List;
Semaphore mutex; block();
mutex.value=1; }
else mutex.value=0;
critical section
 Mutual exclusion: YES if(mutex->List is nonempty){
Remove Pj from mutex->List;
 Progress: YES wakeup(Pj);

}
Bounded waiting: YES else mutex.value++;
reminder section
} while(TRUE)

NIT Rourkela 27
Counting Semaphore
 Useful when we have multiple instances of same
shared resource.
 Initialized to the number of instances of the
resource. (e.g. printer)

NIT Rourkela Dr. Manmath N. Sahoo (CS) 28

Counting Semaphore:
Spin-Lock/Busy-Wait Solution
Semaphore countSem;
countSem.value=3;
 Mutual exclusion: YES
Pi
do{  Progress: YES
while(countSem.value == 0);  Bounded waiting: NO
countSem.value--;
critical section
countSem.value++;
reminder section
} while(TRUE)

NIT Rourkela Dr. Manmath N. Sahoo (CS) 29

Counting Semaphore:
Solution with Waiting List
Pi
do{
countSem.value--;
if(countSem.value < 0){

ES
:Y
Add Pi to countSem->List;

d w ES on

ES
:Y
de : Y s i
block();

un ss clu

ng
Bo ogre al ex

aiti
}

Pr utu
critical section

M
countSem.value++;
if(countSem.value <= 0){
Remove process Pj from countSem->List;
wakeup(Pj);
}
reminder section
} while(TRUE)

NIT Rourkela Dr. Manmath N. Sahoo (CS) 30

Bounded Buffer Problem
 AKA “producer/consumer” problem
 there is a buffer in memory with N entries
 producer threads insert entries into it (one at a time)
 consumer threads remove entries from it (one at a time)
 Threads are concurrent
 so, we must use synchronization constructs to control
access to shared variables describing buffer

tail head
NIT Rourkela Dr. Manmath N. Sahoo (CS) 31
Bounded Buffer Problem
 Constraints
 The consumer must wait if buffers are empty
(synchronization constraint)
 The producer must wait if buffers are full (synchronization
constraint)
 Only one thread can manipulate the buffer at a time
(mutual exclusion)

NIT Rourkela Dr. Manmath N. Sahoo (CS) 32

Bounded Buffer Problem:
Developing a Solution
 Each constraint needs a semaphore
Semaphore mutex = 1;
Semaphore nFreeBuffers = N;
Semaphore nLoadedBuffers = 0;

Producer Consumer

P(nFreeBuffers); P(nLoadedBuffers);
P(mutex); P(mutex);
// put 1 item in the buffer // take 1 item from buffer
V(mutex); V(mutex);
V(nLoadedBuffers); V(nFreeBuffers);

NIT Rourkela Dr. Manmath N. Sahoo (CS) 33

Dining Philosophers Problem
Pi
do{
P3
P(Chopstick[i])
4 3 P2 P(Chopstick[(i+1)%5])
EAT
P4
V(Chopstick[(i+1)%5])
0 V(Chopstick[i])
2
THINK
} while(TRUE)
P0 1
P1

 What if all the philosophers grab their left chopsticks!!

NIT Rourkela Dr. Manmath N. Sahoo (CS) 34

Dining Philosophers Problem:
Solution to deadlock
 Allow at most n-1 philosophers to seat.
 An odd philosopher grabs his left chopstick first then the
right chopstick. An even philosopher grabs his right
chopstick then the left chopstick.
P0 P1 P2 P3 P4
P(C[1]) P(C[1]) P(C[3]) P(C[3]) P(C[0])
P(C[0]) P(C[2]) P(C[2]) P(C[4]) P(C[4])

NIT Rourkela Dr. Manmath N. Sahoo (CS) 35

Readers Writers Problem
 A dataset is shared among a number of
concurrent processes
 Readers – only read; they do not perform any updates
 Writers – can both read and write.
 Conditions
 Any number of readers may simultaneously read the file.
 If a writer is writing to the file, no reader/writer is allowed
to access the file.

NIT Rourkela Dr. Manmath N. Sahoo (CS) 36

Readers Writers Problem: Solution 1 –
Preference to Readers
 Semaphore rlock initialized to 1.
 Integer rcount initialized to 0.
 Semaphore wSem initialized to 1.

Ri
do{
P(rlock);
rcount++;
if (rcount==1) P(wSem);
V(rlock); Wi
READ do{
P(rlock); P(wSem);
rcount--;
WRITE
if (rcount==0) V(wSem);
V(rlock); V(wSem);
} while(TRUE) } while(TRUE)
37
Readers Writers Problem: Solution 1 –
Preference to Readers

 Readers only
 All readers are allowed to READ
 Writers only
 One writer at a time
 Both readers and writers with read first
 Writer has to wait on P(wrt)
 Both readers and writers with write first
 Reader has to wait on P(wrt)
Writers may starve !
NIT Rourkela Dr. Manmath N. Sahoo (CS) 38
Readers Writers Problem: Solution 2 –
Preference to Writers
 Integer rcount – keeps track of number of readers.
 Integer wcount – keeps track of number of writers.
 Semaphore rlock – controls the updating of rdcount.
 Semaphore wlock – controls the updating of wrtcount.
 Semaphore rSem – inhibits all readers while there is at least one writer
desiring access to critical section.
 Semaphore wSem – inhibits all writers while there is at least one reader
desiring access to critical section.
 Semaphore rQueue – to avoid long queue on rSem. So that waiting
writer processes get preference.

NIT Rourkela Dr. Manmath N. Sahoo (CS) 39

 Readers Writers Problem: Solution 2 –
Preference to Writers

Ri Wi
do{ do{

P(rQueue); P(wlock);
P(rSem); wcount++;
P(rlock); if(wcount == 1) P(rSem);
rcount++; V(wlock);
if(rcount == 1) P(wSem);
V(rlock); P(wSem);
V(rSem);
V(rQueue); WRITE

READ V(wSem);

P(rlock); P(wlock);
rcount--; wcount--;
if (rcount == 0) V(wSem); if (wcount == 0) V(rSem);
V(rlock); V(wlock);
reminder section
} while(TRUE) reminder section
} while(TRUE)

Readers may starve !

NIT Rourkela 40
Readers Writers Problem: Solution 3 –
Based on the arrival order

Office

 Integer rcount
 Semaphore rlock
 Semaphore wSem
 Semaphore order_mutuex
NIT Rourkela 41
Readers Writers Problem: Solution 3 –
Based on the arrival order

Ri Wi
do{ do{
P(order_mutex);
P(order_mutex);
P(rlock); P(wSem));
rcount++; V(order_mutex);
if (rcount==1) WRITE
P(wSem));
V(rlock); V(wSem);
V(order_mutex); } while(TRUE)
READ
P(rlock);
rcount--;
if (rcount==0)
V(wSem);
V(rlock);
} while(TRUE)

NIT Rourkela Dr. Manmath N. Sahoo (CS) 42