6 Synchronisation

Synchronisation

1. ProcessSynchronization
Background
TheCritical-SectionProblem
Peterson’sSolutionPeterson’sSolution
SynchronizationHardware
Semaphores
ClassicProblemsofSynchronization
Monitors

2. •Concurrentaccesstoshareddatamayresultindatainconsistency
•Maintainingdataconsistencyrequiresmechanismstoensurethe
orderlyexecutionofcooperatingprocesses
•A solution to the consumer-producer problem that fills all the
bufferscanhaveanintegercountthatkeepstrackofthenumber
offullbuffers. Initially,countissetto0.Itisincrementedbythe
producer after it produces a new buffer and is decremented by
theconsumerafteritconsumesabuffer.
1.Background
theconsumerafteritconsumesabuffer.
2Loganatahn R, CSE, HKBKCE
while(true){
while(count==BUFFER_SIZE)
;//donothing
buffer[in]=nextProduced;
in=(in+1)%BUFFER_SIZE;
count++;
}
while(true) {
while(count==0);//donothing
nextConsumed= buffer[out];
out=(out+1)%BUFFER_SIZE;
count--;
nextConsumed
}
Producer
Consumer

3. •Where several processes access and manipulate the same data concurrently
and the outcome of the execution depends on the particular order in which
theaccesstakesplace,iscalledaracecondition
•Toguardagainsttheracecondition,ensurethatonlyoneprocessatatimecan
bemanipulatingthedatawhich requirethattheprocessesbesynchronized
1.BackgroundContd…
•count++couldbeimplementedas
register1=count
register1=register1+1
count=register1
•count--couldbeimplementedas
register2=count
register2=register2-1
count=register2
3Loganatahn R, CSE, HKBKCE
count=register1
•The concurrent execution of "counter++" and "counter--" is equivalent to a
sequential execution where the lower-level statements are interleaved in
some arbitrary order but the order within each high-level statement is
preserved
•Considerthisexecutioninterleavingwith“count=5”initially:
S0: producer executeregister1 = count {register1 = 5}
S1: producer executeregister1 = register1 + 1{register1 = 6}
S2: consumer executeregister2 = count {register2 = 5}
S3: consumer executeregister2 = register2 - 1{register2 = 4}
S4: producer executecount = register1 {count = 6 }
S5: consumer executecount = register2 {count = 4}

4. •Eachprocessinasystemhasasegmentofcode,calledacritical
section, in which the process may be changing common
variables,updatingatable,writingafile,andsoon
•When one process is executing in itscritical section, no other
processistobeallowedtoexecuteinitscriticalsectionisknown
ascritical-sectionproblem
•Eachprocessmustrequestpermissiontoenteritscriticalsection
andthecodeimplementingthisrequestistheentrysection
•Thecriticalsectionisfollowedbyanexitsectionandthe
2.TheCritical-SectionProblem
•Thecriticalsectionisfollowedbyanexitsectionandthe
remainingcodeistheremaindersection
•Generalstructureofatypicalprocess
4Loganatahn R, CSE, HKBKCE
do{
critical section
remainder section
} while (TRUE);
entry section
exit section

5. •A solution to the critical-section problem must satisfy the following three
requirements
1.Mutual Exclusion- If processP
iis executing in its critical section, then no
otherprocessescanbeexecutingintheircriticalsections
2.Progress-Ifnoprocessisexecutinginitscriticalsectionandthereexistsome
processes that wish to enter their critical section, then only those processes
that are not executing in their remainder sections can participate in the
decision onwhich willenteritscriticalsectionnext, andthisselection cannot
bepostponedindefinitely
2.TheCritical-SectionProblemContd…
bepostponedindefinitely
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
requestisgranted
Assume that each process executes at a nonzero speed
No assumption concerning relative speed of theNprocesses
•TwoapproachesareusedtohandlecriticalsectionsinOS(1)preemptive
kernelsand(2)nonpreemptivekernels
5Loganatahn R, CSE, HKBKCE

6. •RestrictedtoTwoProcessonly
•TwodataitemssharedisbetweentheprocessP
1&P
2(P
i&P
j)
–intturn;
–Booleanflag[2]
•The variableturnindicates whose turn it is to enter the critical
section.Ifturn==i,thenprocessP
iisallowed
•Theflagarrayisusedtoindicateifaprocessisreadytoenterthe
criticalsection.flag[i]=trueimpliesthatprocessP
iisready
•AlgorithmforP
3.Peterson'sSolution
•AlgorithmforP
i
6Loganatahn R, CSE, HKBKCE
do {
flag[ i ] = TRUE;
turn = j ;
while(flag[j] && turn == j ) ;
critical section
flag[i] = FALSE;
remainder section
}while (TRUE);

7. •ToProve
1.Mutualexclusionispreserved.
–Pientersitscriticalsectiononlyifeitherflag[j]==falseor
turn=I
–ifbothprocessesareexecutingintheircriticalsectionsatthe
sametime,thenflag[i]==flag[j]==true(NOTPossible)
2.Theprogressrequirementissatisfied.
–SincePidoesnotchangethevalueofthevariableturnwhile
3.Peterson'sSolutionContd…
–SincePidoesnotchangethevalueofthevariableturnwhile
executingthewhilestatement,Pi-willenterthecritical
section
3.Thebounded-waitingrequirementismet.
–OncePjexitsitscriticalsection,itwillresetflag[j]tofalse,
allowingPitoenteritscriticalsection.
7Loganatahn R, CSE, HKBKCE

8. •Race conditions are prevented by requiring that critical
regionsbeprotectedbylocksi.e.,aprocessmustacquire
alockbeforeenteringacriticalsectionanditreleasesthe
lockwhenitexitsthecriticalsection.
4.SynchronizationHardware
do {
critical section
remainder section
} while (TRUE);
release lock
acquire lock
•Allthesesolutionsarebasedonthelocking,however,the
designofsuchlockscanbequitesophisticated
•Uniprocessors – If interrupts could be disabled during
criticalsection
•Modern machines provide special atomic( non-
interruptable)hardwareinstructions
–Eithertestmemorywordandsetvalue-TestAndSet()
–Orswapcontentsoftwomemorywords–Swap()
8Loganatahn R, CSE, HKBKCE
} while (TRUE);

9. TestAndndSetInstruction
•iftwoTestAndSet()instructionsareexecutedsimultaneously
(eachonadifferentCPU),theywillbeexecutedsequentiallyin
4.SynchronizationHardwareContd…
booleanTestAndSet(boolean*target)
{
booleanrv=*target;
*target=TRUE;
returnrv:
}
(eachonadifferentCPU),theywillbeexecutedsequentiallyin
somearbitraryorder
Mutual-exclusionimplementationwithTestAndSet()
9Loganatahn R, CSE, HKBKCE
while(true){
while(TestAndSet(&lock));
// criticalsection
lock=FALSE;
// remaindersection
}

10. Swap()instruction
Mutual-exclusionimplementationwiththeSwap()
•AglobalBooleanvariablelockisdeclaredandisinitializedtofalseandeach
4.SynchronizationHardwareContd…
voidSwap(boolean*a,boolean*b)
{
booleantemp=*a;
*a=*b;
*b=temp:
}
•AglobalBooleanvariablelockisdeclaredandisinitializedtofalseandeach
processhasalocalBooleanvariablekey
10Loganatahn R, CSE, HKBKCE
while(true) {
key=TRUE;
while(key==TRUE)
Swap(&lock,&key);
// criticalsection
lock=FALSE;
// remaindersection
}
The above both algorithms do
not satisfy the bounded-waiting
requirement

11. Bounded-waitingmutualexclusionwithTestAndSet().
4.SynchronizationHardwareContd…
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])
Common data structuresare initializedto false
booleanwaiting[n]; &booleanlock;
Toprove the mutualexclusion
Process Pi can enter its CS only if either waiting[i] = false or
key = false. The first process to execute the TestAndSet ()
will find key = false and all others must wait. The variable
waiting[i] can become false only if another process leaves
its critical section i.e. only one waiting [i] is set to false,
maintainingthe mutual-exclusionrequirement
Toprovethattheprogress(Sameasabove)
11Loganatahn R, CSE, HKBKCE
while ((j != i) && !waiting[j])
j = (j + 1) % n;
if (j == i)
lock = FALSE;
else
waiting[j] = FALSE;
// remainder section
} while (TRUE);
Toprovethattheprogress(Sameasabove)
Process exiting the CS either sets lock to false or sets
waiting[j] to false allow a process that is waiting to enter
its criticalsection to proceed
Toprove thatthe bounded-waiting
Process which leaves its CS, scans the array waiting in the
cyclic ordering (i+1, i+2,...,n-1, 0,..., i)Itdesignates the
first processin this ordering that is in the entry section
(waiting [j] =- true) as the next one to enter the critical
section. Any process waiting to enter its critical section
willdo so withinn-1turns

12. •Synchronizationtoolthatdoesnotrequirebusywaiting
•SemaphoreSis integer variable, apart from initialization, is accessed only by 2
standardatomicoperations:wait()andsignal()OriginallycalledP()andV()
•TheDefinitionof
•Whenoneprocessmodifiesthesemaphore,nootherprocesscanmodifyit
•5.1Usage
5.Semaphores
wait(S){
while(S<=0);//no-op
S--;
}
signal(S){
S++;
}
•5.1Usage
•Countingsemaphore–integervaluecanrangeoveranunrestricteddomain
•Binarysemaphore – integer value can range only between 0 and 1 and also
knownasmutexlocks,astheyarelocksthatprovidemutualexclusion
•Binary semaphores used in CS for multiple processesshare a semaphore,
mutex,initializedto1isorganized
12Loganatahn R, CSE, HKBKCE
do {
waiting(mutex);
// critical section
signal(mutex);
// remainder
section
}while (TRUE);

13. •Counting semaphores can be used to control access to a resource consisting of
afinitenumberofinstances.
•Thesemaphoreisinitializedtothenumberofresourcesavailable.
•Process that use a resource performs a wait() (decrementing S) and releases a
resourceperformsasignal()(incrementingS)
•When the count for the semaphore goes to 0, all resources are being used.
After that, processes that wish to use a resource will block until the count
becomesgreaterthan0.
5.2Implementation
5.SemaphoresContd…
5.2Implementation
•The disadvantage of the semaphore is it requiresbusy waitingi.e.while a
process is in its CS, other process that tries to enter its CS must loop
continuously(wastesCPUcycles)
•This type of semaphore is also called aspinlockbecause the process "spins"
whilewaitingforthelock(Advantage:nocontextswitch)
•Toovercomebusywaiting,thedefinitionofwait()andsignal()aremodified
•When semaphore value is not positive the process canblocksitself by block()
operation,whichmovesprocessto waitingqueueandrestarted byawakeup()
operationwhensomeotherprocessexecutesasignal()operation
13Loganatahn R, CSE, HKBKCE

14. •Toimplementsemaphoresunderthisdefinition
typedefstruct{
intvalue;
structprocess*list;
}semaphore;
•Implementationofwait():
wait(semaphore*S){
S->value--;
if(S->value <0){
//addthisprocesstoS->list;
5.SemaphoresContd…
//addthisprocesstoS->list;
block();
}
}
•Implementationofsignal:
signal(semaphore*S){
S->value++;
if(S->value <=0){
removeaprocessPfromS->list;
wakeup(P);
}
}
14Loganatahn R, CSE, HKBKCE

15. 5.3DeadlockandStarvation
•Deadlock– two or more processes are waiting indefinitely for an
eventthatcanbecausedbyonlyoneofthewaitingprocesses
•LetSandQbetwosemaphoresinitializedto1
P
0 P
1
wait (S); wait (Q);
wait (Q); wait (S);
. .
. .
. .
5.SemaphoresContd…
. .
signal (S); signal(Q);
signal (Q); signal(S);
•WhenP0executeswait(Q),itmustwaituntilP1executessignal(Q).
Similarly, when P1 executes wait(S), it must wait until Po executes
signal(S)
•These signal () operations cannot be executed, Po and Pi are
deadlocked.
•Starvation– indefinite blocking. A process may never be removed
fromthesemaphorequeueinwhichitissuspended.
15Loganatahn R, CSE, HKBKCE

16. •Large class of concurrency-control problems which are used for testing nearly
everynewlyproposed synchronization scheme.
–Bounded-BufferProblem
–Readersand WritersProblem
–Dining-PhilosophersProblem
6.1Bounded-BufferProblem
•Nbuffers, eachcanholdoneitem
•Semaphoremutexinitialized to the value 1 to provide mutual exclusion for
accessestothebuffer
•Semaphorefullinitializedtothevalue0
6.ClassicalProblemsofSynchronization
•Semaphorefullinitializedtothevalue0
•Semaphoreemptyinitialized tothevalueN.
16Loganatahn R, CSE, HKBKCE
Thestructure of the producer process
do{
// produce an item
wait (empty);
wait (mutex);
// add the item to the buffer
signal(mutex);
signal(full);
}while (true) ;
Thestructure of the consumerprocess
do{
wait (full);
wait (mutex);
// remove an item from buffer
signal(mutex);
signal(empty);
// consume the removed item
}while (true) ;

17. 6.ClassicalProblemsofSynchronizationContd..
6.2 Readers-WritersProblem
•Adatabaseissharedamonganumberofconcurrentprocesses
–Readers–onlyreadthedataset;theydonotperformanyupdates
–Writers –canbothreadandwrite.
•Problem–
•firstreaders-writersproblem,requiresthat,noreaderwillbekept
waitingunlessawriterhasalreadyobtainedpermissiontouse.
•secondreaders-writersproblem,requiresthat,onceawriterisready,
thatwriterperformsitswriteassoonaspossible
17
Loganatahn R, CSE, HKBKCE
thatwriterperformsitswriteassoonaspossible
•Thatisallowmultiplereaderstoreadatthesametime. Onlyone
singlewritercanaccesstheshareddataatthesametime.
•Solutiontofirstreaders-writersproblemSharesthefollowingdata
–Semaphoremutexinitializedto1.
–Semaphorewrtinitializedto1.
–Integerreadcountinitializedto0.
Thestructureofawriterprocess
while(true){
wait(wrt);
// writingisperformed
signal(wrt);
}

18. Thestructureofareaderprocess
do{
wait(mutex);
readcount++;
if(readcount==1)
6.ClassicalProblemsofSynchronizationContd..
• If a writer is in the critical section andn readers are waiting, then one
reader is queued on wrt, and n - 1 readersare queued on mutex.
• When a writer executes signal (wrt), It may resume the execution of
either the waiting readers or a single waiting writer
if(readcount==1)
wait(wrt);
signal(mutex);
//readingisperformed
wait(mutex);
readcount--;
if(readcount==0)
signal(wrt);
signal(mutex);
}while(TRUE);
18Loganatahn R, CSE, HKBKCE

19. 6.3TheDining-PhilosophersProblem
•A large class of concurrency-control problem i.e. It is a simple
representationof the needto allocate severalresources amongseveral
processesinadeadlock-freeandstarvation-freemanner
•Five philosophers who spend their lives thinking and eating share a
circulartablesurroundedbyfivechairsandInthecenterofthetableis
abowlofrice,andthetableislaidwithfivesinglechopsticks
•Fromtimetotime,aphilosophergetshungryandtriestopickupthe2
6.ClassicalProblemsofSynchronizationContd..
•Fromtimetotime,aphilosophergetshungryandtriestopickupthe2
chopsticksthatarebetweenhimandhisleftandrightneighbors)
19
Loganatahn R, CSE, HKBKCE
•A philosopher may pick up only one
chopstick at a time, he cannot pick up a
chopstick that is already in the hand of a
neighbor.
•When a hungry philosopher has both his
chopsticks at the same time, he eats
without releasing his chopsticks until
finishedeating

20. 6.ClassicalProblemsofSynchronizationContd..
•Simplesolutionistorepresenteachchopstickwithasemaphore
semaphorechopstick[5];andallareinitializedto1
•Aphilosophertriestograbachopstickbyexecutingawait()operationonthat
semaphore
•A philosopher releases the chopsticks by executing the signal() operation on
theappropriatesemaphores
Thestructureofphilosopher Pi
do{
wait(chopstick[i]);
• It could create a deadlock i.e. if all five
philosophers become hungry
simultaneously and each grabs left
chopstickmakingallthechopstick[]equal
20
Loganatahn R, CSE, HKBKCE
wait(chopstick[i]);
wait(chopstick[(i+1)%5]);
//eat
signal(chopstick[i]);
signal(chopstick[(i+1)%5]);
//think
}while(TRUE);
chopstickmakingallthechopstick[]equal
to 0, which delays to grab right chopstick
forever.
• Several possible remedies
- Allow at most four philosophers to be sitting
simultaneously at the table.
- Allow a philosopher to pick up her
chopsticks only if both chopsticks are
available
- Allow an odd philosopher to pick up first left chopstick and then right chopstick,
whereas an even philosopher picks up right chopstick and then left chopstick

21. 7.Monitors
•Incorrectuseofsemaphoreoperations:
1. Interchangestheorderofwait()andsignal()signal(mutex);
//criticalsection
wait(mutex);
2. replacessignal(mutex)withwait(mutex) wait(mutex);
//criticalsection
wait(mutex);
3. omitsthewait(mutex),orthesignal(mutex),orboth
To deal with such errors, researchers have developed high-level language
synchronizationconstructcalledthemonitortype
21
Loganatahn R, CSE, HKBKCE
synchronizationconstructcalledthemonitortype
7.1Usage
•A type, or abstract data type, encapsulates private data with public methods
tooperateonthatdata
•Presents a set of programmer-defined operations that are provided mutual
exclusionwithinthemonitor
•Aproceduredefinedwithinamonitorcanaccessonlythosevariablesdeclared
locallywithinthemonitoranditsformalparameters
•Onlyoneprocessmaybeactivewithinthemonitoratatime
•Thesyntaxofamonitorisshown

22. 7.MonitorsContd…
monitor monitor-name
{
// shared variable declarations
procedure P1 (…) { …. }
procedure P2 (…) { …. }
…
procedure Pn (…) {……}
Initialization code ( ….) { … }
…
Syntax of a monitor Schematic view of a monitor
22
Loganatahn R, CSE, HKBKCE
…
}
•Additional synchronization
mechanisms are provided in
monitor by thecondition
construct which define one
or more variables of type
condition
conditionx,y;

23. 7.MonitorsContd…
Monitor with Condition Variables
•Theonlyoperationsthatcanbeinvokedonaconditionvariablearewait()and
signal()
•x.wait() means that the process invoking this operation is suspended until
another process invokes x.signal() which resumes(if any)exactly one
suspendedprocess;
23
Loganatahn R, CSE, HKBKCE

24. monitor DP
7.MonitorsContd…
7.2Dining-PhilosophersSolutionUsingMonitors
•Philosopher i can set the variable state[i] = eating only if two neighbors are not
eating:(state[(i+4)%5]!=eating)and(state[(i+1)%5]!=eating)
•philosopherimust invoke the operationspickup()andputdown()in the
followingsequence: DP.pickup(i);
eat
DP.putdown(i);
•ThissolutionwillensurethatthereisNOdeadlocksbutstarvationmayoccur
monitor DP
{
enum {THINKING, HUNGRY, EATING}state [5] ;
condition self [5];
void pickup (int i) {
state[i] = HUNGRY;
test(i);
if (state[i] != EATING) self [i].wait;
}
void putdown (int i) {
state[i] = THINKING;
// test left and right neighbors
test((i + 4) % 5);
test((i + 1) % 5);
}
24Loganatahn R, CSE, HKBKCE
void test (int i) {
if ( (state[(i + 4) % 5] != EATING) &&
(state[i] == HUNGRY) &&
(state[(i + 1) % 5] != EATING) ) {
state[i] = EATING ;
self[i].signal() ;
}
}
initialization_code() {
for (int i = 0; i < 5; i++)
state[i] = THINKING;
}
}

25. 7.3Implementing a Monitor Using Semaphores
•Semaphoresand Variables
semaphoremutex; // (initially = 1)where processeswaiting to enterthe monitorwait
semaphorenext; // (initially = 0)where processesthatare within the monitorand
ready,wait to become the active process
intnext_count= 0;numberof processsuspended onnext
•EachprocedureFwill be replaced by
wait(mutex);
//body ofF;
if (next_count > 0) signal(next)
else signal(mutex);to ensure Mutual exclusion within a monitor
7.MonitorsContd…
else signal(mutex);to ensure Mutual exclusion within a monitor
•Foreach condition variablex, Semaphores and Variables
semaphorex_sem; // initially = 0
intx_count= 0;
•Theoperationx.waitcan be implemented as:
x_count++;
if (next_count > 0) signal(next);
elsesignal(mutex);
wait(x_sem);
x_count--;
25Loganatahn R, CSE, HKBKCE
•Theoperationx.signalcanbe
implementedas:
if(x_count>0){
next_count++;
signal(x_sem);
wait(next);
next_count--;
}

26. •If several processes are suspended on
condition x, and then x. signal () executed
by some process how to determine which
of the suspended processes should be
resumednext
•Using FCFS ordering scheme may not be
adequate
•Conditional-wait construct can be used
whichhastheform:x.wait(c);
7.MonitorsContd…
monitorResourceAllocator{
booleanbusy;
conditionx;
voidacquire(inttime){
if(busy)x.wait(time);
busy=TRUE;
}
voidrelease(){
7.4 Resuming Processes Within a Monitor Semaphores and Variables
whichhastheform:x.wait(c);
c is apriority numberortimerequired to
completetheprocess
•Forexampleaprocessthatneedstoaccess
the resource must observe the following
sequence: R.acquire(t);
accesstheresource;
R.release();
where R is an instance of type
ResourceAllocator
26Loganatahn R, CSE, HKBKCE
voidrelease(){
busy=FALSE;
x.signal();
}
Initialization_code(){
busy=FALSE;
}
}