Transcript May 23

Process Synchronization
Continued
7.2 The Critical-Section Problem
Critical section
 That part of the program where shared
resources are accessed
 When a process executes code that
manipulates shared data (or resource), we
say that the process is in a critical section
(CS) (for that resource)
Framework for analysis of solutions
 Each process
executes at nonzero
speed but no
assumption on the
relative speed of n
processes
 General structure of a
process:
repeat
entry section
critical section
exit section
remainder section
forever
 No assumptions about
order of interleaved
execution
 The central problem is
to design the entry
and exit sections
Three Key Requirements for a Valid
Solution to the Critical Section Problem
 Mutual Exclusion: At any time, at most one process
can be executing critical section (CS) code
 Progress: If no process is in its CS and there are one
or more processes that wish to enter their CS, this
selection cannot be postponed indefinitely
• no process in its remainder section can participate in
this decision
 Bounded Waiting: After a process P has made a
request to enter its CS, there is a limit on the number
of times that the other processes are allowed to enter
their CS, before P’s request is granted
• (otherwise the process could suffer from starvation)
Types of Solutions
 No special OS mechanisms
(software approach.)
• algorithms whose correctness relies only on the
assumption that only one process at a time can
access a memory location
 Hardware solutions
• rely on special machine instructions for “locking”
 Operating System and Programming
Language solutions (e.g. Java)
• provide specific functions and data structures for
the programmer to use for synchronization
Software solutions
 Consider the 2 process case first
• First 2 algorithms have problems
• 3rd algorithm is correct (Peterson’s algorithm)
 Generalize to n processes
• the Bakery Algorithm
 Notation
• We start with 2 processes: P0 and P1
• When presenting process Pi, Pj always denotes
the other process (i != j)
Faulty Algorithm 1 - Turn taking
 The shared variable
turn is initialized (to 0
or 1) before executing
any Pi
 Pi’s critical section is
executed iff turn = i
 Pi is busy waiting if Pj
is in CS
Process Pi:
//i,j= 0 or 1
repeat
while(turn!=i){};
CS
turn:=j;
RS
forever
Process P0:
repeat
Process P1:
repeat
while(turn!=0){};
CS
turn:=1;
RS
forever
while(turn!=1){};
CS
turn:=0;
RS
forever
Faulty Algorithm 1 side-by-side view
Analysis
 Achieves Mutual Exclusion (busy wait)
 But Progress requirement is not satisfied
since it requires strict alternation of CS’s.
• If one process requires its CS more often than
the other, it can’t get it.
Faulty Algorithm 2 – Ready flag
 Keep a Boolean variable
for each process: flag[0]
and flag[1]
 Pi signals that it is ready
to enter its CS by:
flag[i]:=true but waits
until the other has
finished its CS.
Process Pi:
repeat
flag[i]:=true;
while(flag[j]){};
CS
flag[i]:=false;
RS
forever
Process P0:
repeat
flag[0]:=true;
Process P1:
repeat
flag[1]:=true;
while(flag[1]){};
CS
flag[0]:=false;
RS
forever
while(flag[0]){};
CS
flag[1]:=false;
RS
forever
Faulty Algorithm 2 side-by-side view
Analysis
 Mutual Exclusion is satisfied but not the
progress requirement
 For the (interleaved) sequence:
• flag[0]:=true
• flag[1]:=true
 Both processes will wait forever
Algorithm 3
(Peterson’s Algorithm)
 Initialization:
flag[0]:=flag[1]:=false
turn:= 0 or 1
 Wish to enter CS
specified by
Process Pi:
repeat
flag[i]:=true
flag[i]:=true;
 Even if both flags go
// I want in
up, and no matter how turn:=j;
the instructions are
// but you can go first!
while(flag[j]&& turn==j);
interleaved,
• ..turn will always end
up as either 0 or 1
CS
flag[i]:=false;
// I’m done
RS
forever
Peterson’s Algorithm
Process P0:
repeat
flag[0]:=true;
// 0 wants in
turn:= 1;
// 0 gives a chance to 1
while
(flag[1]&turn=1);
CS
flag[0]:=false;
// 0 is done
RS
forever
Process P1:
repeat
flag[1]:=true;
// 1 wants in
turn:=0;
// 1 gives a chance to 0
while
(flag[0]&turn=0);
CS
flag[1]:=false;
// 1 is done
RS
forever
Peterson’s algorithm side-by-side view
Peterson’s Algorithm: Proof of
Correctness
 Mutual exclusion holds since:
• For both P0 and P1 to be in their CS
 both flag[0] and flag[1] must be true and:
 turn=0 and turn=1 (at same time): impossible
Proof (“progress”)
 Progress requirement:
• Pi can be kept out of CS only if stuck in while loop
 flag[j] = true and turn = j.
• If Pj not ready to enter CS then flag[j] = false
 Pi can then enter its CS
• If Pj has set flag[j], it is also in its while loop, then either
Pi or Pj will go depending on value of turn
• Therefore the progress condition is met
Proof (“Bounded Waiting”)
• Suppose Pj gets to go this time
Process Pi:
repeat
flag[i]:=true;
// I want in
turn:=j;
// but you can go first!
while(flag[j]&& turn==j)
; //(loop)
CS
flag[i]:=false;
// I’m done
RS
forever
 Can it go a second time without
letting Pi go?
• If Pj enters CS , then turn=j
 but will then reset flag[ j]=false on
exit:
 allowing Pi to enter CS
• What if Pj tries again, and has
time to reset flag[ j]=true before Pi
gets to its CS?
 It must also set turn=i
• since Pi is (stuck) past the point
where it sets turn= j:
 Pi will get to enter CS
 after at most one CS entry by Pj
What About Process Failures?
 If all 3 criteria are satisfied, a valid solution will be
robust for failure of a process in its remainder
section (RS) since failure in RS is just like having
an infinitely long RS.
 However, no valid solution can provide
robustness against a process failing in its critical
section (CS).
 Therefore a process Pi that fails in its CS must
signal this fact to other processes.
N-Process Solution: Bakery Algorithm
 “Take a number for better service...”
 Before entering the CS, each Pi takes a number.
 Holder of smallest number enters CS next
• ..but more than one process can get the same number
 If Pi and Pj receive same number:
• lowest numbered process is served first
 Process resets its number to 0 in the exit section
 Notation:
• (a,b) < (c,d) if a < c or if a = c and b < d
• max(a0,...ak) is a number b such that:
b >= ai for i=0,..k
Bakery Algorithm
 Shared data:
• choosing: array[0..n-1] of boolean;
 initialized to false
• number: array[0..n-1] of integer;
 initialized to 0
Bakery Algorithm
Process Pi:
repeat
choosing[i]:=true;
number[i]:=max(number[0]..number[n-1])+1;
choosing[i]:=false;
for j:=0 to n-1 do {
while (choosing[j]);
while (number[j]!=0
and (number[j],j)<(number[i],i));
}
CS
number[i]:=0;
RS
forever