Transcript May 26

Process Synchronization
Continued
7.2 Critical-Section Problem
7.3 Synchronization Hardware
7.4 Semaphores
Critical section
 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
repeat
entry section
critical section
exit section
remainder section
forever
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, it
must be possible for those processes to negotiate
who will proceed next into CS
• No deadlock
• 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
• Deterministic algorithm, otherwise the process could
suffer from starvation
turn := 0;
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 – Turn taking
ok for mutual exclusion, but processes MUST strictly
alternate turns
flag[0]:=false;
Process P0:
repeat
flag[0]:=true;
flag[1]:=false;
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 - ready flag
Mutual exlusion ok, but not progress
(interleaving flag[1]:=true and flag[0]:=true means
neither can enter CS)
Peterson’s Algorithm
flag[0],flag[1]:=false
turn := 0;
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 – proved to be correct
Turn can only be 0 or 1 even if both flags are set to
true
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
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
Important Observation about Process
Interleaving
 Even a simple high level language
assignment statement can be interleaved
One HLL statement
Two Machine instructions:
load R1, B
A := B;
store R1, A
This is why it is possible to two processes to “take” the same
number
Bakery Algorithm: Proof
 Mutual Exclusion:
• If Pi is in CS and Pk has already chosen its
number, then (number[i],i) < (number[k],k)
 If they both had their numbers before the
decision, this must be true or Pi would not have
been chosen
 If Pi entered its CS before Pk got its number, Pk
got a bigger number
 So Pk cannot enter its CS until Pi exits.
 Progress, Bounded Waiting:
• Processes enter CS in FCFS order
Drawbacks of Software Solutions
 Complicated to program
 Busy waiting (wasted CPU cycles)
 It would be more efficient to block
processes that are waiting (just as if they
had requested I/O).
• This suggests implementing the
permission/waiting function in the Operating
System
 But first, let’s look at some hardware
approaches (7.3 Synchronization
Hardware):
Hardware Solution 1: Disable Interrupts
Process Pi:
repeat
disable interrupts
critical section
enable interrupts
remainder section
forever
 On a uniprocessor, mutual exclusion is preserved: while
in CS, nothing else can run
• because preemption impossible
 On a multiprocessor: mutual exclusion is not achieved
• Interrupts are “per-CPU”
 Generally not a practical solution for user programs
 But could be used inside an OS
Hardware Solution 2: Special Machine
Instructions
 Normally, the memory system restricts access to
any particular memory word to one CPU at a time
 Useful extension:
• machine instructions that perform 2 actions atomically on
the same memory location (ex: testing and writing)
 The execution of such an instruction is mutually
exclusive on that location (even with multiple CPUs)
 These instructions can be used to provide mutual
exclusion
• but need more complex algorithms for satisfying the
requirements of progress and bounded waiting
The Test-and-Set Instruction
 Test-and-Set
expressed in “C”:
 An algorithm that uses
testset for Mutual
Exclusion:
 Shared variable lock is
initialized to 0
 Only the first Pi who
sets lock enters CS
int testset(int &i)
{
int rv;
rv = *i;
*i = 1;
Process Pi:
return rv;
repeat
}
while(testset(&lock));
Non Interruptible
CS
(atomic)!
lock:=0;
One instruction reads then
RS
writes the same memory
forever
location
Test-and-Set Instruction
 Mutual exclusion is assured: if Pi enters CS, the
other Pj are busy waiting
 Satisfies progress requirement
 When Pi exits CS, the selection of the next Pj to
enter CS is arbitrary: no bounded waiting (it’s a
race!).
• Starvation is possible.
• See Fig 7.10 for (complicated) solution
 Some processors (ex: Pentium) provide an atomic
Swap(a,b) instruction that swaps the content of a
and b.
• (Same drawbacks as Test-and-Set)
Using Swap for Mutual Exclusion
 Shared variable lock
is initialized to 0
 Each Pi has a local
variable key
 The only Pi that can
enter CS is the one
which finds lock=0
 This Pi excludes all
other Pj by setting
lock to 1
• (Same effect as testand-set)
Process Pi:
repeat
key:=1
repeat
swap(lock,key)
until key=0;
CS
lock:=0;
RS
forever
Operating Systems or Programming
Language Support for Concurrency
 Solutions based on machine instructions
such as test and set involve tricky coding.
 We can build better solutions by providing
synchronization mechanisms in the
Operating System or Programming
Language (7.4 – Semaphores).
 (This leaves the really tricky code to
systems programmers)
Semaphores
 A Semaphore S is an integer variable that, apart
from initialization, can only be accessed through 2
atomic and mutually exclusive operations:
• wait(S)
 sometimes called P()
• Dutch proberen: “to test”
• signal(S)
 sometimes called V()
• Dutch verhogen: “to increment”
Busy Waiting Semaphores
 The simplest way to
implement
semaphores.
 Useful when critical
sections last for a
short time, or we have
lots of CPUs.
 S initialized to positive
value (to allow
someone in at the
beginning).
wait(S):
while S<=0 do ;
S--;
signal(S):
S++;
Atomicity in Semaphores
 The test-and-decrement
sequence in wait must
be atomic, but not the
loop.
 Signal is atomic.
 No two processes can be
allowed to execute
atomic
atomic sections
simultaneously.
 This can be implemented
by other mechanisms (in
the OS)
• test-and-set, or
• disable interrupts.
wait(S):
T
S <= 0
F
S--
Using semaphores for solving critical
section problems
 For n processes
 Initialize semaphore
“mutex” to 1
 Then only one process
is allowed into CS
(mutual exclusion)
 To allow k processes
into CS at a time,
simply initialize mutex
to k
Process Pi:
repeat
wait(mutex);
CS
signal(mutex);
RS
forever
Semaphores in Action
Initialize mutex to 1
Process Pi:
repeat
wait(mutex);
CS
signal(mutex);
RS
forever
Process Pj:
repeat
wait(mutex);
CS
signal(mutex);
RS
forever
Synchronizing Processes using
Semaphores
 Two processes:
• P1 and P2
 Statement S1 in P1
needs to be
performed before
statement S2 in P2
 We want a way to
make P2 wait
• until P1 tells it it is
OK to proceed
 Define a semaphore
“synch”
• Initialize synch to 0
 Put this in P2:
wait(synch);
S2;
 And this in in P1:
S1;
signal(synch);
Busy-Waiting Semaphores:
Observations
 When S>0:
• the number of processes that can execute
wait(S) without being blocked = S
 When S=0: one or more processes are
waiting on S
 Semaphore is never negative
 When S becomes >0, the first process that
tests S enters enters its CS
• random selection (a race)
• fails bounded waiting condition