操作系统教程06

1、Chapter 6: Process SynchronizationBackgroundThe Critical-Section ProblemSynchronization HardwareSemaphoresClassic Problems of SynchronizationMonitorsSynchronization Examples Atomic TransactionsBackgroundConcurrent access to shared data = inconsistencyMaintaining data consistency = orderly execution

2、of cooperating processessolution to the consumer-producer problem:integer count = number of full buffersInitially, count is set to 0incremented by the producer after it produces a new buffer decremented by the consumer after it consumes a bufferProducer while (true) /* produce an item and put in nex

3、tProduced */ while (count = BUFFER_SIZE); / do nothing buffer in = nextProduced; in = (in + 1) % BUFFER_SIZE; count+; Consumer while (true) while (count = 0) ; / do nothing nextConsumed = bufferout; out = (out + 1) % BUFFER_SIZE; count-;/* consume the item in nextConsumed*/Race Conditioncount+ could

4、 be implemented as register1 = count register1 = register1 + 1 count = register1count- could be implemented as register2 = count register2 = register2 - 1 count = register2Consider this execution interleaving with “count = 5” initially:S0: producer execute register1 = count reg1 = 5S1: producer exec

5、ute register1 = register1 + 1 reg1 = 6 S2: consumer execute register2 = count reg2 = 5 S3: consumer execute register2 = register2 - 1 reg2 = 4 S4: producer execute count = register1 count = 6 S5: consumer execute count = register2 count = 4Solution to Critical-Section ProblemCritical sectionA segmen

6、t of code, in which the process may be changing common variables, updating a table, writing a file, and so on.Entry section request permission to enter CSExit section following the CSRemainder section the remaining code3 requirements to the CS problem:Mutual ExclusionIf process Pi is executing in it

7、s critical section, then no other processes can be executing in their critical sectionsSolution to Critical-Section ProblemProgressIf no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that wil

8、l enter the critical section next cannot be postponed indefinitelyBounded WaitingA bound must exist on the number of times that other processes are allowed to enter their critical sectionsAssumption Assume each process executes at a nonzero speed No assumption concerning relative speed of the n proc

9、essesPetersons Solution2 process solutionAssume LOAD & STORE instructions are atomicThe 2 processes share 2 variables:int turn; Boolean flag2;The variable turn indicates whose turn it is to enter the critical section. The flag array is used to indicate if a process is ready to enter the critical sec

10、tionflagi = true implies that process Pi is readyAlgorithm for Process Piwhile (true) flagi = TRUE; turn = j; while ( flagj & turn = j); CRITICAL SECTION flagi = FALSE; REMAINDER SECTION Synchronization HardwareMany systems provide hardware support for critical section codeUniprocessors disable inte

11、rruptsCurrently running code would execute without preemptionGenerally too inefficient on multiprocessor systemsMessage is passed to all processors, time consumingThe clock is kept updated by interruptsModern machines provide special atomic hardware instructionsEither test memory word and set valueO

12、r swap contents of two memory wordsTestAndSet Instruction Definition: boolean TestAndSet (boolean *target) boolean rv = *target; *target = TRUE; return rv: Solution using TestAndSetShared boolean variable lock, initialized to falseSolution: while (true) while ( TestAndSet (&lock ) ; /* do nothing /

13、critical section lock = FALSE; / remainder section SemaphoreLess complicatedDo not require busy waiting Semaphore S integer variableTwo standard operations modify Swait() signal()Originally called:P() from the Dutch proberen, “to test”V() from the Dutch verhogen, “to increment”Semaphore (cont.)Can o

14、nly be accessed via two indivisible (atomic) operationswait (S) while S value-;if (S-value listblock();Semaphore Implementation with no Busy waiting (Cont.)Implementation of signal:Signal (semaphore *S) S-value+;if (S-value list wakeup(P);May have negative semaphore valuesDeadlock and StarvationDead

15、lock two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processesLet S and Q be two semaphores initialized to 1P0P1 wait (S); wait (Q); wait (Q); wait (S);. signal (S); signal (Q); signal (Q); signal (S);Starvation indefinite blocking.Classic Pr

16、oblems of SynchronizationBounded-Buffer ProblemReaders and Writers ProblemDining-Philosophers ProblemBounded-Buffer ProblemN buffers, each can hold one itemSemaphore mutex initialized to the value 1Semaphore full initialized to the value 0Semaphore empty initialized to the value N.Bounded Buffer Pro

17、blem (Cont.)The structure of the producer processwhile (true) / produce an item wait (empty); wait (mutex); / add the item to the buffer signal (mutex); signal (full); Bounded Buffer Problem (Cont.)The structure of the consumer process while (true) wait (full); wait (mutex); / remove an item from bu

18、ffer signal (mutex); signal (empty); / consume the removed item Readers-Writers ProblemA data set is shared among a number of concurrent processesReaders only read the data set; they do not perform any updatesWriters can both read and writeAllow multiple readers to read at the same timeOnly 1 writer

19、 can access the shared data simultaneouslyReaders-Writers ProblemProblems1st readers-writers problemNo reader kept waiting unless a writer has already obtained permission to use the shared objecti.e., No reader should wait for other readers to finish simply because a writer is waiting2nd readers-wri

20、ters problemOnce a writer is ready, that writer performs its write as soon as possiblei.e. If a writer is waiting, no new readers may startReaders-Writers ProblemStarvation1st case, writers may starve2nd case, readers may starveSolution to starvation:Shared DataData setSemaphore mutex =1, ensure rea

21、dcount is updatedSemaphore wrt = 1, Integer readcount initialized to 0.Readers-Writers Problem (Cont.)The structure of a writer process while (true) wait (wrt) ; / writing is performed signal (wrt) ; Readers-Writers Problem (Cont.)The structure of a reader process while (true) wait (mutex) ; readcou

22、nt + ; if (readcount = 1) wait (wrt) ; signal (mutex) / reading is performed wait (mutex) ; readcount - - ; if (readcount = 0) signal (wrt) ; signal (mutex) ; Dining-Philosophers ProblemDining-Philosophers Problem5 philosophers spend their lives thinking & eatingShared dataBowl of rice (data set)Sem

23、aphore chopstick 5 initialized to 1When a philosopher gets hungry, she tries to pick up 2 chopsticksShe may pick up only 1 chopsticks at a timeShe cant pick up a chopstick in the hand of a neighborWhen grabbed 2 chopsticks can she eatAfter eating, she puts down chopsticks & thinkingDining-Philosophe

24、rs Problem (Cont.)The structure of Philosopher i:While (true) wait ( chopsticki ); wait ( chopStick (i + 1) % 5 ); / eat signal ( chopsticki ); signal (chopstick (i + 1) % 5 ); / thinkDining-Philosophers Problem (Cont.)Deadlock (each one pick up a chopstick & wait for the neighbors)Deadlock preventi

25、on:Allow at most 4 philosophers sitting at the tableAllow a philosopher to pick up her chopsticks only if both chopsticks are available(she must pick them up in a CS)Asymmetric solutionOdd philosopher picks up first her left chopsticks and then her right chopsticksEven philosopher picks up first her

26、 right chopsticks and then her left chopsticksGuard against starvationProblems with Semaphores Correct use of semaphore operations: signal (mutex) . wait (mutex)Mutual exclusion violated wait (mutex) wait (mutex)Deadlock will occur Omitting wait (mutex) or signal (mutex) (or both)Mutual exclusion vi

27、olatedDeadlock will occurMonitorsA high-level abstraction for process synchronizationOnly one active process within the monitor at a timemonitor monitor-name/ shared variable declarationsprocedure P1 () . procedure Pn () Initialization code ( .) Schematic view of a MonitorCondition VariablesConditio

28、n is defined to make monitor powerful condition x, y;Two operations on a condition variable:x.wait () a process that invokes the operation is suspendedx.signal () resumes one of processes (if any) that invoked x.wait ()Otherwise, nothing happensWhen P invoke x.signal() operation, 2 possibilitiesSign

29、al & wait P waits until Q leaves or waits another conditionSignal & continueQ waits until P leaves or waits another condition Monitor with Condition VariablesMonitor Implementation Using SemaphoresVariables semaphore mutex; / (initially = 1)semaphore next; / (initially = 0)int next_count = 0;Each ex

30、ternal procedure F will be replaced bywait(mutex); body of F; if (next_count 0)signal(next)else signal(mutex);Mutual exclusion within a monitor is ensured.Monitor ImplementationFor each condition variable x, we have:semaphore x_sem; / (initially = 0)int x_count = 0;The operation x.wait can be implem

31、ented as:x_count+;if (next_count 0)signal(next);elsesignal(mutex);wait(x_sem);x_count-;Monitor ImplementationThe operation x.signal can be implemented as:if (x_count 0) next_count+;signal(x_sem);wait(next);next_count-;Synchronization ExamplesWindows XPLinuxPthreadsWindows XP SynchronizationUses inte

32、rrupt masks to protect access to global resources on uniprocessor systemsUses spinlocks on multiprocessor systemsAlso provides dispatcher objects which may act as mutexes, semaphores, events and timersAn event acts much like a condition variableTimers are used to notify thread time expiredDispatcher

33、 objects may be in:A signaled state: object is availableA nonsignaled state: object is unavailable, thread blockedLinux SynchronizationLinux provides:semaphores: longer periodSpinlocks: On SMP, short durationEnabling & disabling kernel preemption: single-processorPthreads SynchronizationPthreads API

34、 is OS-independentIt provides:mutex lockscondition variablesRead-write locksNon-portable extensions include:semaphoresspin locksAtomic TransactionsSystem ModelLog-based RecoveryCheckpointsConcurrent Atomic TransactionsSystem ModelAssures that operations happen as a single logical unit of work, in it

35、s entirety, or not at allAssures atomicity despite computer system failuresTransaction - collection of instructions or operations that performs single logical functionchanges to stable storage diskTransaction is series of read and write operationsTerminated by commit or abort operationAborted transa

36、ction must be rolled backRelated to field of database systemsTypes of Storage MediaVolatile storage does not survive system crashesExample: main memory, cacheNonvolatile storage survives crashesExample: disk and tapeStable storage Information never lostapproximated via replication or RAID to devices

37、 with independent failure modesGoal is to assure transaction atomicity where failures cause loss of information on volatile storageLog-Based RecoveryRecord to stable storage information about all modifications by a transactionMost common is write-ahead loggingLog on stable storage, each log record d

38、escribes single transaction write operation, includingTransaction nameData item nameOld valueNew value written to log when transaction Ti starts written when Ti commitsLog entry must reach stable storage before operation on data occursLog-Based Recovery AlgorithmUsing the log, system can handle any

39、volatile memory errorsUndo(Ti) restores value of all data updated by TiRedo(Ti) sets values of all data in transaction Ti to new valuesUndo(Ti) and redo(Ti) must be idempotentMultiple executions must have the same result as one executionIf system fails, restore state of all updated data via logIf lo

40、g contains without , undo(Ti)If log contains and , redo(Ti)CheckpointsCheckpoints shorten log and recovery time.Checkpoint scheme:Output all log records currently in volatile storage to stable storageOutput all modified data from volatile to stable storageOutput a log record to the log on stable sto

41、rageNow recovery only includes Ti, such that Ti started executing before the most recent checkpoint, and all transactions after TiConcurrent TransactionsMust be equivalent to serial execution serializabilityCould perform all transactions in critical sectionInefficient, too restrictiveConcurrency-con

42、trol algorithms provide serializabilitySerializabilityConsider two data items A and BConsider Transactions T0 and T1Execute T0, T1 atomicallyExecution sequence called scheduleAtomically executed transaction order called serial scheduleFor N transactions, there are N! valid serial schedulesSchedule 1

43、: T0 then T1Nonserial ScheduleNonserial schedule allows overlapped executeDoes not necessarily imply an incorrect executionConflict - Consider schedule S, operations Oi, Ojif access same data item, with at least one writeIf Oi, Oj consecutive operations of S, different transactions, Oi and Oj dont c

44、onflictThen S with swapped order Oj, Oi equivalent to SIf S can become S via swapping nonconflicting operationsS is conflict serializableSchedule 2: Concurrent Serializable ScheduleLocking ProtocolEnsure serializability by associating lock with each data itemFollow locking protocol for access contro

45、lLocksShared Ti has shared-mode lock (S) on item Q, Ti can read Q but not write QExclusive Ti has exclusive-mode lock (X) on Q, Ti can read and write QRequire every transaction on item Q acquire appropriate lockIf lock already held, new request may have to waitSimilar to readers-writers algorithmTwo-phase Locking ProtocolGenerally ensures conflict seri