ch07Process Synchronization

1、Silberschatz, Galvin and Gagne 20027.1Operating System ConceptsChapter 7: Process SynchronizationnBackgroundnThe Critical-Section ProblemnSynchronization HardwarenSemaphoresnClassical Problems of SynchronizationnCritical RegionsnMonitorsnSynchronization in Solaris 2 & Windows 2000Silberschatz, G

2、alvin and Gagne 20027.2Operating System ConceptsBackgroundnConcurrent access to shared data may result in data inconsistency.nMaintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes.nShared-memory solution to bounded-butter problem (Chapter 4) allows

3、 at most n 1 items in buffer at the same time. A solution, where all N buffers are used is not simple.FSuppose that we modify the producer-consumer code by adding a variable counter, initialized to 0 and incremented each time a new item is added to the bufferSilberschatz, Galvin and Gagne 20027.3Ope

4、rating System ConceptsBounded-Buffer nShared data#define BUFFER_SIZE 10typedef struct . . . item;item bufferBUFFER_SIZE;int in = 0;int out = 0;int counter = 0;Silberschatz, Galvin and Gagne 20027.4Operating System ConceptsBounded-Buffer nProducer process item nextProduced;while (1) while (counter =

5、BUFFER_SIZE); /* do nothing */bufferin = nextProduced;in = (in + 1) % BUFFER_SIZE;counter+;Silberschatz, Galvin and Gagne 20027.5Operating System ConceptsBounded-Buffer nConsumer process item nextConsumed;while (1) while (counter = 0); /* do nothing */nextConsumed = bufferout;out = (out + 1) % BUFFE

6、R_SIZE;counter-;Silberschatz, Galvin and Gagne 20027.6Operating System ConceptsBounded BuffernThe statementscounter+;counter-;must be performed atomically.nAtomic operation means an operation that completes in its entirety without interruption.Silberschatz, Galvin and Gagne 20027.7Operating System C

7、onceptsBounded BuffernThe statement “count+” may be implemented in machine language as:register1 = counterregister1 = register1 + 1counter = register1nThe statement “count” may be implemented as:register2 = counterregister2 = register2 1counter = register2Silberschatz, Galvin and Gagne 20027.8Operat

8、ing System ConceptsBounded BuffernIf both the producer and consumer attempt to update the buffer concurrently, the assembly language statements may get interleaved.nInterleaving depends upon how the producer and consumer processes are scheduled.Silberschatz, Galvin and Gagne 20027.9Operating System

9、ConceptsBounded BuffernAssume counter is initially 5. One interleaving of statements is:producer: register1 = counter (register1 = 5)producer: register1 = register1 + 1 (register1 = 6)consumer: register2 = counter (register2 = 5)consumer: register2 = register2 1 (register2 = 4)producer: counter = re

10、gister1 (counter = 6)consumer: counter = register2 (counter = 4)nThe value of count may be either 4 or 6, where the correct result should be 5.Silberschatz, Galvin and Gagne 20027.10Operating System ConceptsRace ConditionnRace condition: The situation where several processes access and manipulate sh

11、ared data concurrently. The final value of the shared data depends upon which process finishes last.nTo prevent race conditions, concurrent processes must be synchronized.Silberschatz, Galvin and Gagne 20027.11Operating System ConceptsThe Critical-Section Problemnn processes all competing to use som

12、e shared datanEach process has a code segment, called critical section, in which the shared data is accessed.nProblem ensure that when one process is executing in its critical section, no other process is allowed to execute in its critical section.Silberschatz, Galvin and Gagne 20027.12Operating Sys

13、tem ConceptsSolution to Critical-Section Problem1. Mutual Exclusion. If process Pi is executing in its critical section, then no other processes can be executing in their critical sections.2. Progress. If no process is executing in its critical section and there exist some processes that wish to ent

14、er their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely.3. 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

15、 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.Silberschatz, Galvin and Gagne 20027.13Operating System ConceptsInitial Attempts to Solve ProblemnOnly 2 processes, P0 and

16、 P1nGeneral structure of process Pi (other process Pj)do entry sectioncritical sectionexit sectionreminder section while (1);nProcesses may share some common variables to synchronize their actions.Silberschatz, Galvin and Gagne 20027.14Operating System ConceptsAlgorithm 1nShared variables: Fint turn

17、;initially turn = 0Fturn - i Pi can enter its critical sectionnProcess Pido while (turn != i) ;critical sectionturn = j;reminder section while (1);nSatisfies mutual exclusion, but not progressSilberschatz, Galvin and Gagne 20027.15Operating System ConceptsAlgorithm 2nShared variablesFboolean flag2;i

18、nitially flag 0 = flag 1 = false.Fflag i = true Pi ready to enter its critical sectionnProcess Pido flagi := true;while (flagj) ;critical sectionflag i = false;remainder section while (1);nSatisfies mutual exclusion, but not progress requirement.Silberschatz, Galvin and Gagne 20027.16Operating Syste

19、m ConceptsAlgorithm 3nCombined shared variables of algorithms 1 and 2.nProcess Pido flag i:= true;turn = j;while (flag j and turn = j) ;critical sectionflag i = false;remainder section while (1);nMeets all three requirements; solves the critical-section problem for two processes.Silberschatz, Galvin

20、 and Gagne 20027.17Operating System ConceptsBakery AlgorithmnBefore entering its critical section, process receives a number. Holder of the smallest number enters the critical section.nIf processes Pi and Pj receive the same number, if i j, then Pi is served first; else Pj is served first.nThe numbe

21、ring scheme always generates numbers in increasing order of enumeration; i.e., 1,2,3,3,3,3,4,5.Critical section for n processesSilberschatz, Galvin and Gagne 20027.18Operating System ConceptsBakery Algorithm nNotation lexicographical order (ticket #, process id #)F(a,b) c,d) if a c or if a = c and b

22、 dFmax (a0, an-1) is a number, k, such that k ai for i - 0, , n 1nShared databoolean choosingn;int numbern; Data structures are initialized to false and 0 respectivelySilberschatz, Galvin and Gagne 20027.19Operating System ConceptsBakery Algorithm do choosingi = true;numberi = max(number0, number1,

23、, number n 1)+1;choosingi = false;for (j = 0; j n; j+) while (choosingj) ; while (numberj != 0) & (numberj,j numberi,i) ;critical sectionnumberi = 0;remainder section while (1);Silberschatz, Galvin and Gagne 20027.20Operating System ConceptsSynchronization HardwarenTest and modify the content of

24、 a word atomically.boolean TestAndSet(boolean &target) boolean rv = target;tqrget = true;return rv;Silberschatz, Galvin and Gagne 20027.21Operating System ConceptsMutual Exclusion with Test-and-SetnShared data: boolean lock = false;nProcess Pido while (TestAndSet(lock) ;critical sectionlock = fa

25、lse;remainder sectionSilberschatz, Galvin and Gagne 20027.22Operating System ConceptsSynchronization Hardware nAtomically swap two variables.void Swap(boolean &a, boolean &b) boolean temp = a;a = b;b = temp;Silberschatz, Galvin and Gagne 20027.23Operating System ConceptsMutual Exclusion with

26、 SwapnShared data (initialized to false): boolean lock;boolean waitingn;nProcess Pido key = true;while (key = true) Swap(lock,key);critical sectionlock = false;remainder sectionSilberschatz, Galvin and Gagne 20027.24Operating System ConceptsSemaphoresnSynchronization tool that does not require busy

27、waiting.nSemaphore S integer variablencan only be accessed via two indivisible (atomic) operationswait (S): while S 0 do no-op;S-;signal (S): S+;Silberschatz, Galvin and Gagne 20027.25Operating System ConceptsCritical Section of n ProcessesnShared data: semaphore mutex; /initially mutex = 1nProcess

28、Pi: do wait(mutex); critical section signal(mutex); remainder section while (1); Silberschatz, Galvin and Gagne 20027.26Operating System ConceptsSemaphore ImplementationnDefine a semaphore as a recordtypedef struct int value; struct process *L; semaphore;nAssume two simple operations:Fblock suspends

29、 the process that invokes it.Fwakeup(P) resumes the execution of a blocked process P.Silberschatz, Galvin and Gagne 20027.27Operating System ConceptsImplementationnSemaphore operations now defined as wait(S):S.value-;if (S.value 0) add this process to S.L;block;signal(S): S.value+;if (S.value = 0) r

30、emove a process P from S.L;wakeup(P);Silberschatz, Galvin and Gagne 20027.28Operating System ConceptsSemaphore as a General Synchronization ToolnExecute B in Pj only after A executed in PinUse semaphore flag initialized to 0nCode:PiPj Await(flag)signal(flag)BSilberschatz, Galvin and Gagne 20027.29Op

31、erating System ConceptsDeadlock and StarvationnDeadlock two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes.nLet S and Q be two semaphores initialized to 1P0P1wait(S); wait(Q);wait(Q); wait(S); signal(S);signal(Q);signal(Q)signal(S);nSt

32、arvation indefinite blocking. A process may never be removed from the semaphore queue in which it is suspended.Silberschatz, Galvin and Gagne 20027.30Operating System ConceptsTwo Types of SemaphoresnCounting semaphore integer value can range over an unrestricted domain.nBinary semaphore integer valu

33、e can range only between 0 and 1; can be simpler to implement.nCan implement a counting semaphore S as a binary semaphore.Silberschatz, Galvin and Gagne 20027.31Operating System ConceptsImplementing S as a Binary SemaphorenData structures:binary-semaphore S1, S2;int C: nInitialization:S1 = 1S2 = 0C

34、= initial value of semaphore SSilberschatz, Galvin and Gagne 20027.32Operating System ConceptsImplementing Snwait operationwait(S1);C-;if (C 0) signal(S1);wait(S2);signal(S1);nsignal operationwait(S1);C +;if (C = 0)signal(S2);elsesignal(S1);Silberschatz, Galvin and Gagne 20027.33Operating System Con

35、ceptsClassical Problems of SynchronizationnBounded-Buffer ProblemnReaders and Writers ProblemnDining-Philosophers ProblemSilberschatz, Galvin and Gagne 20027.34Operating System ConceptsBounded-Buffer ProblemnShared datasemaphore full, empty, mutex;Initially:full = 0, empty = n, mutex = 1Silberschatz

36、, Galvin and Gagne 20027.35Operating System ConceptsBounded-Buffer Problem Producer Processdo produce an item in nextp wait(empty);wait(mutex); add nextp to buffer signal(mutex);signal(full); while (1);Silberschatz, Galvin and Gagne 20027.36Operating System ConceptsBounded-Buffer Problem Consumer Pr

37、ocessdo wait(full)wait(mutex); remove an item from buffer to nextc signal(mutex);signal(empty); consume the item in nextc while (1);Silberschatz, Galvin and Gagne 20027.37Operating System ConceptsReaders-Writers ProblemnShared datasemaphore mutex, wrt;Initiallymutex = 1, wrt = 1, readcount = 0Silber

38、schatz, Galvin and Gagne 20027.38Operating System ConceptsReaders-Writers Problem Writer Processwait(wrt); writing is performed signal(wrt);Silberschatz, Galvin and Gagne 20027.39Operating System ConceptsReaders-Writers Problem Reader Processwait(mutex);readcount+;if (readcount = 1)wait(rt);signal(m

39、utex); reading is performed wait(mutex);readcount-;if (readcount = 0)signal(wrt);signal(mutex):Silberschatz, Galvin and Gagne 20027.40Operating System ConceptsDining-Philosophers ProblemnShared data semaphore chopstick5;Initially all values are 1Silberschatz, Galvin and Gagne 20027.41Operating Syste

40、m ConceptsDining-Philosophers Problem nPhilosopher i:do wait(chopsticki)wait(chopstick(i+1) % 5) eat signal(chopsticki);signal(chopstick(i+1) % 5); think while (1);Silberschatz, Galvin and Gagne 20027.42Operating System ConceptsCritical RegionsnHigh-level synchronization constructnA shared variable

41、v of type T, is declared as:v: shared TnVariable v accessed only inside statementregion v when B do Swhere B is a boolean expression.nWhile statement S is being executed, no other process can access variable v. Silberschatz, Galvin and Gagne 20027.43Operating System ConceptsCritical RegionsnRegions

42、referring to the same shared variable exclude each other in time.nWhen a process tries to execute the region statement, the Boolean expression B is evaluated. If B is true, statement S is executed. If it is false, the process is delayed until B becomes true and no other process is in the region asso

43、ciated with v.Silberschatz, Galvin and Gagne 20027.44Operating System ConceptsExample Bounded BuffernShared data:struct buffer int pooln;int count, in, out;Silberschatz, Galvin and Gagne 20027.45Operating System ConceptsBounded Buffer Producer ProcessnProducer process inserts nextp into the shared b

44、ufferregion buffer when( count 0) nextc = poolout;out = (out+1) % n;count-;Silberschatz, Galvin and Gagne 20027.47Operating System ConceptsImplementation region x when B do SnAssociate with the shared variable x, the following variables:semaphore mutex, first-delay, second-delay; int first-count, se

45、cond-count;nMutually exclusive access to the critical section is provided by mutex.nIf a process cannot enter the critical section because the Boolean expression B is false, it initially waits on the first-delay semaphore; moved to the second-delay semaphore before it is allowed to reevaluate B.Silb

46、erschatz, Galvin and Gagne 20027.48Operating System ConceptsImplementationnKeep track of the number of processes waiting on first-delay and second-delay, with first-count and second-count respectively.nThe algorithm assumes a FIFO ordering in the queuing of processes for a semaphore.nFor an arbitrar

47、y queuing discipline, a more complicated implementation is required.Silberschatz, Galvin and Gagne 20027.49Operating System ConceptsMonitorsnHigh-level synchronization construct that allows the safe sharing of an abstract data type among concurrent processes.monitor monitor-nameshared variable decla

48、rationsprocedure body P1 () . . .procedure body P2 () . . . procedure body Pn () . . . initialization codeSilberschatz, Galvin and Gagne 20027.50Operating System ConceptsMonitorsnTo allow a process to wait within the monitor, a condition variable must be declared, ascondition x, y;nCondition variabl

49、e can only be used with the operations wait and signal.FThe operationx.wait();means that the process invoking this operation is suspended until another process invokesx.signal();FThe x.signal operation resumes exactly one suspended process. If no process is suspended, then the signal operation has n

50、o effect.Silberschatz, Galvin and Gagne 20027.51Operating System ConceptsSchematic View of a MonitorSilberschatz, Galvin and Gagne 20027.52Operating System ConceptsMonitor With Condition VariablesSilberschatz, Galvin and Gagne 20027.53Operating System ConceptsDining Philosophers Examplemonitor dp en

51、um thinking, hungry, eating state5;condition self5;void pickup(int i) / following slidesvoid putdown(int i) / following slidesvoid test(int i) / following slidesvoid init() for (int i = 0; i 0)signal(next)else signal(mutex);nMutual exclusion within a monitor is ensured.Silberschatz, Galvin and Gagne

52、 20027.57Operating System ConceptsMonitor ImplementationnFor each condition variable x, we have:semaphore x-sem; / (initially = 0)int x-count = 0;nThe operation x.wait can be implemented as:x-count+;if (next-count 0)signal(next);elsesignal(mutex);wait(x-sem);x-count-;Silberschatz, Galvin and Gagne 20027.58Operating System ConceptsM