OPERATING SYSTEMS

PROCESS SYNCHRONIZATION

[Link]
Associate Professor – (SITE)
VIT University
 Introduction to Cooperating Processes

 Processes within a system may be independent or

cooperating

 Independent process cannot affect or be affected by the

execution of another process

 Cooperating process can affect or be affected by other

processes, including sharing data
Suppose that two processes A and B have access to a shared
variable “Balance”:

PROCESS A:

Balance = Balance - 100

PROCESS B:

Balance = Balance - 200

Further, assume that Process A and Process B are executing

concurrently in a time-shared, multi-programmed system.
Race Condition:

 If Several processes access and manipulate the shared data

concurrently, then the outcome of the execution depends on the
particular order in which the access takes place.
Race Condition: Solution

 To prevent race conditions, concurrent processes must be

synchronized.
 The Critical-Section

 A section of code Common to ‘n’ cooperating processes, in

which the processes may be accessing ‘common variables’

A critical section environment contains:

1. Entry Section: Code requesting entry into the critical section.

2. Critical Section: Code in which only one process can execute at

any one time.

3. Exit Section: The end of the critical section, releasing or

allowing others in.

4. Remainder Section: Rest of the code AFTER the critical section

General Structure of a Typical Process

do {
entry section

critical section

exit session

remainder section

} while (TRUE);
 Critical-Section Problem – General Rules

The critical section solutions must ENFORCE all the 3 rules:

(1) Mutual
Exclusion

(2) Progress

(3) Bounded
Waiting
1. Mutual Exclusion – If process Pi is executing in its critical section, then
no other processes can be executing in their critical sections.

(i.e. no two processes will simultaneously be inside the same CS)

2. Progress – If no process is executing in its critical section and some

processes wish to enter their critical sections, then only those processes
that are not executing in their remainder sections can participate in the
decision on which will enter its critical section next, and this selection
cannot be postponed indefinitely.

3. Bounded Waiting – There exists a bound, or limit, on the number of

times that other processes are allowed to enter their critical sections after
a process has made a request to enter its critical section and before that
request is granted.
 Algorithm 1

 Shared variables:

int turn;
initially turn = i (or ) j

 Structure of Process Pi :  Structure of Process Pj :

while (turn != i); //do nothing; /*busy while (turn != j); //do nothing /*busy
wait*/ wait*/
critical section critical section
turn = j; turn = i;
remainder section remainder section
 Algorithm 1

Drawback 1: processes must strictly alternate

Drawback 2: if one processes fails other process is

permanently blocked

 This solution guarantees mutual exclusion

 Algorithm 2
Shared variables:

boolean flag[2];
initially flag [i] = flag [j] = false

flag [i] = true  Pi ready to enter its critical section

Structure of Process Pi : Structure of Process Pj:

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

while (flag[ j ]); //do nothing; while (flag[ i ]); //do nothing;
critical section critical section
flag [i] = false; flag [j] = false;
remainder section remainder section
 Algorithm 2

 This solution guarantees mutual exclusion

Drawback 1:This approach may lead to dead lock

 What is wrong with this implementation ?

Dead lock occurs because each process can insist on its right to
enter critical section
 Algorithm 3 (PETERSON ALGORITHM)

 Combined shared variables of algorithms 1 and 2

Process Pi Process Pj

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

turn = j; turn = i;
while (flag [j] and turn = j); while (flag [i] and turn = i);
// do nothing; // do nothing;
critical section critical section
flag [i] = false; flag [j] = false;
remainder section remainder section

 Meets all three requirements; solves the critical-section problem

for two processes
 Bakery Algorithm

Critical section for n processes:

 Before entering its critical section, process receives a number.

 Holder of the smallest number enters the critical section.

 If processes Pi and Pj receive the same number, if i < j, then Pi is

served first; else Pj is served first.

 The numbering scheme always generates numbers in increasing

order of enumeration; i.e., 1,2,3,4,5...
 Bakery Algorithm
 Shared data:

boolean choosing[n];

int number[n];

 Data structures are initialized to false and 0

respectively

 choosing array =>indicate that a process wants to

enter it's critical section

 number array => contains the numbers associated

with each process.
 Bakery Algorithm
{

choosing[i] = true;
number[i] = max(number[0], number[1], …, number [n – 1])+1;
choosing[i] = false;

for (j = 0 to n-1) do begin

{
while (choosing[j]) do no-op ;
while ((number[j] != 0) && ((number[ j ], j ) < (number[ i ], i ) ))
do no-op ;
}

critical section

number[i] = 0;

remainder section

};
 Semaphores

 Semaphore is a variable that has an integer value

 May be initialized to a nonnegative number

 Can only be accessed via two indivisible (atomic) operations

wait (S):
S --;

signal (S):
S ++;

 Wait operation decrements the semaphore value

 Signal operation increments semaphore value

 Two Types of Semaphores

(1) Counting semaphore – Scenarios in which more than one

processes need to execute in critical section simultaneously.

 In this mechanism, the entry and exit in the critical section are
performed on the basis of the value of counting semaphore

 A process which wants to enter in the critical section first

decrease the semaphore value by 1 and then check whether it gets
negative or not.

 If it gets negative then the process is pushed in the list of blocked

processes, otherwise it gets enter in the critical section.
 Two Types of Semaphores

(2) Binary semaphore – It is a semaphore whose integer value range

over 0 and 1.

Here 0 means Locked (busy), a process or a thread is in the critical

section(i.e. it is accessing the shared resource), while the other
process or thread should wait for it to.

On the other hand, 1 means that no process is accessing the shared

resource, and the critical section is free.
 Implementation

 Semaphore operations are now defined as:

wait(mutex):

[Link]--;
if ([Link] < 0)
{
add this process to S.L;
block;
}
 Implementation

signal(mutex):

[Link]++;
if ([Link] <= 0)
{
remove a process P from S.L;
wakeup(P);
}

 Value of semaphore can be negative and represents

the number of processes waiting on it
Classical Problems of Synchronization

 Bounded-Buffer Problem

 Dining-Philosophers Problem

 Readers-Writers Problem
 (1) Bounded-buffer Problem

Shared data:

semaphore full, empty, mutex ;

Initially: Number of Full & Number of Empty

full = 0, empty = n, mutex = 1

 Buffer size is n

 Mutex provides exclusive access to the buffer

 Consumers wait on full

 Producers wait on empty

Bounded-buffer Problem: Producer Process

produce an item

wait(empty);
wait(mutex);

add Item to buffer

signal(mutex);
signal(full);
Bounded-buffer Problem: Consumer Process

wait(full)
wait(mutex);

remove an item from buffer

signal(mutex);
signal(empty);

consume the item

 (2) Dining-philosophers Problem

 To start eating, a philosopher needs two chopsticks

 After eating, the philosopher releases both the
chopsticks
Shared data:
semaphore chopstick[5];
(Initially all values are 1)
Philosopher i :
do {
wait(chopstick[i])
wait(chopstick[(i+1) % 5])
…
eat
…
signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);
…
think
…
} while (1);
  The solution is not deadlock free!!

=> All philosophers pick up left chopsticks!!

Solution:

Allow at most 4 philosophers to be sitting on the table

An odd philosopher picks up first the left and then the
right chopstick while a even philosopher does the
reverse
 (3) Readers-Writers Problem

 Two readers can access the shared data item

simultaneously

 A writer requires exclusive access

 No reader should wait unless a writer is already in

critical section

Shared data:

var mutex, wrt : semaphore (=1);

readcount : integer (=0);
 Readers-Writers Problem

 wrt is common to both readers and writers.

 It functions as mutual exclusion semaphore for writers.

 It is also used by first and last reader that enters or exits the CS.

 readcount keeps track of how many readers are

currently accessing the object.

 mutex provides mutual exclusion for updating

readcount.
 Readers-Writers Problem

Writer process

wait(wrt);
…
writing is performed
…
signal(wrt);
 Readers-Writers Problem

Reader process
wait(mutex);
readcount := readcount +1;
if readcount = 1 then wait(wrt);
signal(mutex);
…
reading is performed
…
wait(mutex);
readcount := readcount – 1;
if readcount = 0 then signal(wrt);
signal(mutex):
Hardware Solution for Critical Section
Problems
 Initially ,
lock value = 0
(lock Open)
Monitors
 Monitors - Syntax

monitor monitor-name

variable declarations

procedure1 (…);
procedure 2 (…);
procedure n (…);

initialization code
 Monitor Module- Example

monitor sharedcounter

Int counter;

function add() { counter++;}

function sub() { counter--;}

init() { counter=0; }

}
Producer/Consumer using Monitors

Full