 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. A race condition is a situation that may occur inside a critical section

withdraw (account, amount) {

balance = get_balance(account);
balance = get_balance(account);

Execution flow on CPU

balance -= amount;
balance = balance - amount;
context switch
put balance(account, balance);
balance = get_balance(account);
} balance -= amount;
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 // assumption that this

instruction is atomic in nature.

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]); // If someone is choosing don’t
allow anyone to enter into CS
while( number[j] && (number[j],j) < (number[i],i) );
} critical section

number[i]=0;
reminder section

} while(TRUE) link – Youtube.

https://www.youtube.com/watch?v=Y7rBAWFQNR4&list=PLskQvPDUk0sJ6RRPdkgO2qziych6vQwZ1&index=8
NIT Rourkela Dr. Manmath N. Sahoo (CS) 16
Hardware Solutions to Critical Sections
 Enable and Disable Interrupt
 Test-and-set instruction
 Swap instruction

Motivating example why SW based solutions are not preferred:

while(true){
while(lock != false); Not atomic; hence violates
lock=true Mutual Exclusion

Critical section
lock = false
…reminder section
}

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

Enable and Disable Interrupt
Pi
do{
DI

critical section

EI

reminder section
} while(TRUE)

 May miss out some important system interrupts

 Not suitable for multi-processor systems
NIT Rourkela Dr. Manmath N. Sahoo (CS) 18
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) 19

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

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

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) 22
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) 23

Swap Instruction: Solution1
 global boolean lock;  Mutual exclusion: YES

 local boolean keyi;  Progress: YES

 lock & keyi initialized to FALSE  Bounded waiting: NO

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) 24
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) 25
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) 26

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) 27
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 28
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) 29

Counting Semaphore:
Spin-Lock/Busy-Wait Solution
Semaphore countSem;
countSem.value=3;

Pi  Mutual exclusion: YES

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

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

critical section
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) 31
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) 32
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) 33

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

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

P0

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

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

Dining Philosophers Problem:
Solution to deadlock
 Allow at most n-1 philosophers to seat.
 Allow a philosopher to grab the chopsticks only if both are
available. DI
P(Chopstick[i])
P(Chopstick[(i+1)%5])
EI

 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) 36
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) 37

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)
38
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) 39
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) 40

 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 reminder section
} while(TRUE) } while(TRUE)

Readers may starve !

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

Office

 Integer rcount
 Semaphore rlock
 Semaphore wSem
 Semaphore order_mutuex
NIT Rourkela 42
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) 43