Process Synchronization

Dr. N.Nalini
SCOPE
VIT
 Process
• Processes can execute concurrently
• CPU scheduler switches rapidly between processes to provide concurrent execution
– A process may be interrupted at any time, partially completing execution
• Concurrent(parallel) access to shared data may result in data inconsistency.
• Maintaining data consistency requires mechanisms to ensure the orderly execution of
cooperating processes. Process synchronization and coordination are necessary.
• Outcome of the execution depends on the particular order, in which order process
access takes place. (Can be different each time processes are run).
 Interprocess Communication
• Processes within a system may be independent or cooperating
• Cooperating process can affect or be affected by other processes, including
sharing data
• Reasons for cooperating processes:
– Information sharing
– Computation speedup
– Modularity
– Convenience
• Cooperating processes need interprocess communication (IPC)
• Two models of IPC
– Shared memory
– Message passing
Communications Models
 Cooperating Processes
• Independent process cannot affect or be affected by the execution of another process
• Cooperating process can affect or be affected by the execution of another process
• Advantages of process cooperation
– Information sharing
– Computation speed-up
– Modularity
– Convenience
 Race Condition
• We would arrive at this incorrect state because we allowed both
processes to manipulate the variable counter concurrently.

• Race condition: The situation where several processes access and

manipulate shared data concurrently. The final value of the shared data
depends upon which process finishes last.

• To prevent race conditions, concurrent processes must be

synchronized. It is necessary to encure that only one process at a
time can be manipulating the variable counter.
 Bounded Buffer producer-consumer problem

 Given producer, consumer routines are correct separately, but

they may not function correctly when executed concurrently.

 The statements

counter = counter + 1;
counter = counter - 1;

must be performed atomically.

 Atomic operation means an operation that completes in its

entirety without interruption.
 Race Condition
 count++ could be implemented as

register1 = count
register1 = register1 + 1
count = register1
 count-- could be implemented as

register2 = count
register2 = register2 - 1
count = register2
 Consider this execution interleaving with “count = 5” initially:
S0: producer execute register1 = count {register1 = 5}
S1: producer execute register1 = register1 + 1 {register1 = 6}
S2: consumer execute register2 = count {register2 = 5}
S3: consumer execute register2 = register2 - 1 {register2 = 4}
S4: producer execute count = register1 {count = 6 }
S5: consumer execute count = register2 {count = 4}
 The outcome of concurrent thread/process execution depends on the particular order
in which the access takes place  race condition!
 Race Condition
• Processes P0 and P1 are creating child processes using the fork() system call
• Race condition on kernel variable next_available_pid which represents the next available
process identifier (pid)

• Unless there is a mechanism to prevent P0 and P1 from accessing the variable

next_available_pid the same pid could be assigned to two different processes!
 Critical Section Problem
• Consider system of n processes {p0, p1, … pn-1}
• No assumptions may be made about speeds or the number of CPUs.
• n processes competing to use some shared data.
• Each process has critical section segment of code
– Process may be changing common variables, updating table, writing file,
etc.
– When one process in critical section, no other may be in its critical
section
• Critical section problem is to design protocol to solve this
• Each process must ask permission to enter critical section in entry section,
may follow critical section with exit section, then remainder section
 Critical Section
• General structure of process Pi
• The section of code implementing this request is called the
Entry Section (ES).
• The critical section (CS) might be followed by a Leave/Exit
Section (LS).
• The remaining code is the Remainder Section (RS).
• The critical section problem is to design a protocol that the
processes can use so that their action will not depend on the
order in which their execution is interleaved (possibly on
many processors).

• Processes may share some common variables

to synchronize their actions.
 Critical-Section Problem (Cont.)
Requirements for solution to critical-section problem When entering CS

1. Mutual Exclusion (Safety)

2. Progress (Liveness)
③ Bounded times
3. Bounded Waiting
• Mutual Exclusion - If process Pi is executing in its ② Pick up a process to enter
critical section, then no other processes can be
Critical Section
executing in their critical sections
Implications: ① only one process
• Critical sections better be focused and short.
• Better not get into an infinite loop in there.
• If a process somehow halts/waits in its When exiting from CS
critical section, it must not interfere with
other processes
 Critical-Section Problem (Cont.)
• Progress - If no process is executing in its critical section and there exist some
processes that wish to enter their critical section, then the selection of the process
that will enter the critical section next cannot be postponed indefinitely
• Are not executing in their reminder section – can participate in the decision (what is next)
• If only one process wants to enter, it should be able to.
• If two or more want to enter, one of them should succeed.
• Bounded Waiting - A bound must exist 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
• Assume that each process executes at a nonzero speed
• No assumption concerning relative speed of the n processes
• This is required to make sure that no process suffers starvation
• Is this condition sufficient to guarantee that there will be no startvation?
 Types of solutions to CS problem
• Software solutions
– Algorithms whose correctness does not rely on any other assumptions, beside
those stated in the framework
• Hardware solutions
– Special machine instructions are provided
• Operation system solutions
– Special functions and data structures are provided to the programmer through
system/library calls.
• Programming Language solutions
– Linguistic constructs provided as part of a language.
 Software Solutions
• We consider first the case of 2 processes:
– Algorithm 1 - Strict Alternation Approach.
– Peterson’s algorithm
• Then we generalize to n processes:
– The Bakery algorithm.
 Software Solution
• Two process solution
• Assume that the load and store machine-language instructions
are atomic; that is, cannot be interrupted
• The two processes share one variable:
– int turn;
• The variable turn indicates whose turn it is to enter the critical
section
• initially, the value of turn is set to i
 Algorithm 1 – Strict Alternation Approach
 Shared variables:
 int turn; //who’s turn P0 or P1
initially turn = 0 //initial value of turn is zero
 turn = i  Pi can enter its critical section

Process Pi
Process Pj
do { do {
while (turn == j) ; while (turn == i) ;
critical section critical section
turn = j; turn = i;
reminder section reminder section
} while (true); } while (true);
 Algorithm 1 – Strict Alternation Approach
 Mutual Exclusion: Variable turn shows which process can enter its CS; it has value
either 0 or 1. So only one of the processes(P0 or P1) can be in its CS. (Satisfied)
 If turn=0, P1 waits, P0 enters its CS. If turn=1, P0 waits P1 enters its CS.
 Progress: This solution does not satisfy the progress requirement: If Pi wants to enter
its critical section, and turn is j, then it can not even if Pj may be executing in its
remainder section. (Not Satisfied)
 If P1 wants to enter its CS and turn is 0 and P0 is running outside of its CS (RS), is
not satisfied for P1.
 Progress is not guaranteed in this mechanism. If Pi doesn't want to get enter into
the critical section on its turn then Pj got blocked for infinite time. Pj has to wait
for so long for its turn since the turn variable will remain 0 until Pi assigns it to j.
 Bounded waiting: other process is allowed to enter its critical section only once after a
process has made a request to enter its critical section and before that request is
granted.
 turn = 0, P0 enters its CS, after exit, turn = 1, P1 enters its CS, after exit turn = 0.
Operating System Concepts
 Peterson’s Solution
• Two process solution
• Assume that the load and store machine-language instructions
are atomic; that is, cannot be interrupted
• The two processes share two variables:
– int turn;
– boolean flag[2]
• The variable turn indicates whose turn it is to enter the critical
section
• The flag array is used to indicate if a process is ready to enter
the critical section.
– flag[i] = true implies that process Pi is ready!
– Initially flag [0] = flag [1] = false.
 Peterson’s Algorithm
 Process Pi
Shared variables
 bool flag[2]={false, false};
 int turn=0;
 turn = i  Pi can enter its critical section
 flag [i] = true  Pi ready to enter its critical section
do {
flag [i] = true;
turn = j; //give priority to other process
while (flag [ j ] and turn == j) ; //wait
critical section
flag [i] = false; //allow other process to enter CS
remainder section
} while (true);
 What about the three requirements?
 turn=i turn=i

Operating System Concepts

Peterson’s Solution preserves all three
conditions
• Mutual Exclusion is assured as only one process can
access the critical section at any time.
• Progress is also assured, as a process outside the
critical section does not block other processes from
entering the critical section.
• Bounded Waiting is preserved as every process gets
a fair chance.
 Disadvantages of Peterson’s solution
• It involves busy waiting.(In the Peterson’s solution, the code
statement- “while(flag*j+ && turn == j);” is responsible for this.
Busy waiting is not favored because it wastes CPU cycles that
could be used to perform other tasks.)
• It is limited to 2 processes.
• Peterson’s solution cannot be used in modern CPU architectures.
 Multiple-process Solutions:
Bakery Algorithm
Critical section for n processes (process names are unique)

 Before entering its critical section, each process receives a ticket

number(bakery/priority). Holder of the smallest ticket number enters
the critical section.

 If processes Pi and Pj receive the same ticket number(the algorithm

does not guarantee that all processes will receive different numbers)
and i < j, then Pi is served first(the process with he lowest name); else
Pj is served first.

 The numbering scheme always generates numbers in increasing order

of enumeration; i.e., 1,2,3,3,3,3,4,5...
Operating System Concepts
 Bakery Algorithm

 Choosing a number:
 max (a0,…, an-1) is a number k, such that k  ai for i = 0, …, n – 1
 Notation: “<“  lexicographical order (ticket #, process id #)
 (a,b) < (c,d) if a < c or if a = c and b < d
 There is no pair of processes having (ticket #, process id #) equal to
each other!!!
 Shared data :
bool choosing[n]={false};
int number[n]={0};
 Process Pi: Bakery Algorithm
do {
choosing[i] = true; // show interest in critical section
number[i] = max(number[0], number[1], …, number [n – 1])+1; // get a token number
choosing[i] = false;
for (j = 0; j < n; j++) {
while (choosing[ j ]) ; // busy wait until process Pj receives its token number
while (number[ j ] != 0 && (number[ j ],j) < (number[ i ],i)) ; // token comparison
}
critical section
number[i] = 0; //exit section
remainder section
} while (true);
Arrival of
process
P3,P4,P5,P2
 The Bakery algorithm meets all the requirements of the
critical section problem

• Mutual Exclusion: we know that when no process is executing in its critical section, a process with the
lowest number is allowed to enter its critical section. Suppose two processes have the same token
number. In that case, the process with the lower process ID among these is selected as the process ID
of each process is distinct, so at a particular time, there will be only one process executing in its critical
section. Thus the requirement of mutual Exclusion is met.
• Progress: After selecting a token, a waiting process checks whether any other waiting process has
higher priority to enter its critical section. If there is no such process, P will immediately enter its critical
section. Thus meeting progress requirements.
• Bounded Waiting: As awaiting, the process will enter its critical section when no other process is in its
critical section and
– If its token number is the smallest among other waiting processes.
– If token numbers are the same, it has the lowest process ID among other waiting processes.
 Synchronization Hardware
• Many systems provide hardware support for implementing the critical section code.
• Uniprocessors – could disable interrupts
– Currently running code would execute without preemption
– Generally too inefficient on multiprocessor systems
• Operating systems using this not broadly scalable
• We will look at forms of hardware support:
1. Hardware instructions
2. Atomic variables
• Modern machines provide special atomic hardware instructions
• Atomic = non-interruptable
– Test memory word and set value
– Swap contents of two memory words
 Hardware Instructions
• Special hardware instructions that allow us to either test-and-
modify the content of a word, or to swap the contents of two
words atomically (uninterruptedly.)
– Test-and-Set instruction
– Compare-and-Swap instruction
 The test_and_set Instruction
• Definition
boolean test_and_set (boolean *target)
{
boolean rv = *target;
*target = true;
return rv:
}
• If two TestAndSet instructions are executed simultaneously (each on a different
CPU), they will be executed sequentially (i.e. atomically) in some arbitrary order.
• Properties
– Executed atomically
– Returns the original value of passed parameter
– Set the new value of passed parameter to true
 Solution Using test_and_set()
• Shared boolean variable lock, initialized to false
• Solution:
do {
while (test_and_set(&lock)); /* do nothing */

/* critical section */

lock = false;
/* remainder section */
} while (true);
• Does it solve the critical-section problem?
 ML – statisfied
 BW – Not statisfied
 Another Algorithm using TestAndSet
(satisfies all CS requirements)
• Shared data:
bool waiting[n]={false};
bool lock = false;

Process Pi
do {
waiting[i] = true;
key = true;
while(waiting[i] && key)
key = TestAndSet(lock);
waiting[i] = false;

critical section

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

remainder section
} while(true);
 Synchronization Hardware – Swap function
 Atomically swaps two variables.

void Swap (bool &a, bool &b)

{
bool temp = a;
a = b;
b = temp;
}

 Alternatively,

void Swap (bool *a, bool *b)

{
bool temp = *a;
*a = *b;
*b = temp;
}
 The compare_and_swap Instruction
 Definition
int compare_and_swap(int *value, int expected, int new_value)
{
int temp = *value;
if (*value == expected)
*value = new_value;
return temp;
}
 Properties
 Executed atomically
 Returns the original value of passed parameter value
 Set the variable value the value of the passed parameter new_value but only if
*value == expected is true. That is, the swap takes place only under this
condition.
 Solution using compare_and_swap
 Shared integer lock initialized to 0;
 Solution:
while (true){
while (compare_and_swap(&lock, 0, 1) != 0)
; /* do nothing */

/* critical section */

lock = 0;

/* remainder section */
}
 Does it solve the critical-section problem?
 ML – not statisfied
 Progress – not statisfied
 BW – not statisfied
 Bounded-waiting with compare-and-swap

while (true) {
waiting[i] = true;
key = 1;
while (waiting[i] && key == 1)
key = compare_and_swap(&lock,0,1);
waiting[i] = false;
/* critical section */
j = (i + 1) % n;
while ((j != i) && !waiting[j])
j = (j + 1) % n;
if (j == i)
lock = 0;
else
waiting[j] = false;
Does it solve the critical-section problem?
/* remainder section */
} ML – statisfied
Progress - statisfied
BW – statisfied
 Mutex Locks
• Previous solutions are complicated and generally inaccessible to application
programmers
• OS designers build software tools to solve critical section problem
• Simplest is mutex lock
– Boolean variable indicating if lock is available or not
• Protect a critical section by
– First acquire() a lock
– Then release() the lock
• Calls to acquire() and release() must be atomic
– Usually implemented via hardware atomic instructions such as compare-
and-swap.
• But this solution requires busy waiting
– This lock therefore called a spinlock
 Solution to CS Problem Using Mutex Locks

while (true) {
acquire lock

critical section

release lock

remainder section
}