Concurrent co-operating processes.
·
Processes
are concurrent if they exist at the same time.concurrent process can function
completely indepently to one another.
Need for interprocess synchronization
·
If different processes are dealing
with commonly shared variables
Synchronization should be there.
Eg:Let P1 and P2 be two processes
works one sane commly shared variable’lines entered’
Ø P1 increments ‘lines entered’
Ø P2 increments ‘lines entered’
If both simultaneously tries to
access ‘linesentered’ there can be
problems.
So to avoid this p1 and p2 need to
communicate(this is known as interprocess synchronization..(when one work other
shoud not work).
Critical section
Ø A process is said to be in its
critical section when it is accessing shared modifiable data, when a process is
in critical section other processes are out side its critical section.
Mutual Exclusion
Ø When one works other does not.
Mutual Exclusion algorithms
1.Dekkers
Algorithm
2.Semaphore
3.test and
set
Dekkers
algorithm
Algorithm1
Program version one
Var processnumber integer
Procedure
processone
Begin
Begin
While processnumber=2do;
Criticalsectionone
Processnumber=2
Otherstuffone;
End
End
Procedure
processtwo
Begin
Begin
While processnumber=1do;
Criticalsectiontwo
Processnumber=1
Otherstuffone;
End
End
Begin
processnumber=1
parbegin
processone
processtwo
parend
End
Advantage: Mutual exclusion is guaranteed.
Disadvantage: First proceess1 itself should be executed b’cause
(processs number=1 initially).
·
Here
there was only one synchronization variable processnumber
·
We
try to rectify the problem in the next algorithm by bu sing two
Synchronization variables
Algorithm2
Program version two
Var p1 inside,p2 inside:boolean
Procedure
processone
Begin
While true
do
Begin
While p2 inside do;
P1 inside=true
criticalsectionone
p1inside=false
Otherstuffone;
End
End
Procedure
processtwo
Begin
While p1 inside do;
P2 inside=true
criticalsectionone
p2inside=false
Otherstuffone;
End
End
Begin
P1inside=false
P2inside=false
Parbegin
processone
processtwo
parend
End
Disadvantage:If both tries at the same time both will enter critical section no mutual
exclusion.
Algorithm3
Program
version three
Var p1 inside,p2 inside:boolean
Procedure
processone
Begin
While true
do
Begin
P1wantstoenter=true
While p2wantstoenter do;
Criticalsectionone
P1wantstoenter=false
Otherstuffone;
End
End
Procedure
processtwo
Begin
P2wantstoenter=true
While p1wantstoenter do;
Criticalsectionone
P2wantstoenter=false
Otherstuffone;
End
End
Begin
P1wantstoenter=false
P2wantstoenter=false
Parbegin
processone
processtwo
parend
End
Dsiadv:If
both tries at the same time both waits indefinitely(deadlock happens)\
To avoid the deadlock in algorithm 3 the
delay concept is used .
Program
version four
Var p1 wantstoenter,p2watstoenter:boolean
Procedure
processone
Begin
While true do
Begin
P1wantstoenter=true
While p2wantstoenter do
Begin
P1wantstoenter=false
Delay(random few cycles)
P1wantstoenter=true
End
Criticalsectionone
P1watstoenter=false
Otherstuffone;
End
End
Procedure
processtwo
Begin
While true do
Begin
P2wantstoenter=true
While p1wantstoenter do
Begin
P2wantstoenter=false
Delay(random few
cycles)
P2wantstoenter=true
End
Criticalsectiontwo
P2watstoenter=false
Otherstuffone;
End
End
Begin
P1wantstoenter=false
P2wantstoenter=false
Parbegin
processone
processtwo
parend
End
.
Advantage
·
:Mutual
exclusion is guaranteed and deadlock will not occur.
Disadv
·
Sometimes
indefinite delay may occur(especially when simultaneous
Access is attempted random delay generated if same)
·
So
we make use of another alogorithm .
·
It
makes use of a variable ‘favouved process’
Program dekkers
algorithm
Var favouredprocess(first,second)
p1 wantstoenter,p2watstoenter:boolean
Procedure
processone
Begin
While true do
Begin
P1wantstoenter=true
{ If favoured
process=second then
Begin
P1wantstoenter=false
While
favouredprocess=second do;//if so waits
P1wantstoenter=true
End
}
Criticalsectionone
favouredprocess=second
p1wantstoenter=false
Otherstuffone;
End
End
Procedure
processtwo
Begin
While true do
Begin
P2wantstoenter=true
While p1wantstoenter do
{
If favoured
process=first then
Begin
P2wantstoenter=false
While
favouredprocess=first do;
P2wantstoenter=true
End
}
Criticalsectiontwo
favouredprocess=first
p2wantstoenter=false
Otherstufftwo;
End
End
Begin
P1wantstoenter=false
P2wantstoenter=false
Favoured
process=first
Parbegin
processone
processtwo
parend
End
Semaphore
A semaphore
is a protected variable which is used for mutual exclusion .
It can be
altered by only two operations
P and S
P(S)
Is S>0
then S=S-1
Else (wait on S)
V (S)
If (one or
more processers are waiting on s)
Then (let
one of these processes proceed)
Else s-s+1
Binary
semaphore
.assumes value 0 or 1
Counting semaphore
·
Can
assume non negative values.
Program
semaphoreexampleone
Procedure processone
Begin
While true do
Begin
preliminarystuffone=true
p(active)
criticalsectionone;
v(active)
otherstuffone;
End
Program
semaphoreexampleone
Procedure
processtwo
Begin
While true do
Begin
preliminarystufftwo=true
p(active)
criticalsectiontwo;
v(active)
otherstuffone;
End
Begin
Semaphoreinitialize(active,1)
Parbegin
processone
processtwo
parend
End
Process P1
Repeat
{
While test
&set(lock) do no op;
Test
&set(lock)
Critical
section
Lock=false
}
Until false
Process P2
Repeat
{
While test
&set(lock) do no op;
Test and
set(lock)
Critical
section
Lock=false
}
Until false
Lock=false
Begin
Process p1
Process p2
End
Test
&set sets lock =true by the following technique
Function Test
&set (var target :Boolean):Boolean
Begin
Test&set
=target
Target =true
End
No comments:
Post a Comment