Synchronization MethodsMutual ExclusionHardware Mutex SupportExample of Test and SetEvaluating Test and SetSemaphoresProblems in SynchronizationMonitorsThe Producer/Consumer ProblemProducer/Consumer with SemaphoresProducer/Consumer with Semaphores (continued)Producer/Consumer with MonitorsProducer/Consumer with Monitors (continued)The Readers/Writers ProblemReaders/Writers with Semaphores (Polling Version)Readers/Writers with Semaphores (Polling continued)Slide 17Readers/Writers with MonitorsReaders/Writers with Monitors (continued)Slide 20DeadlockDining PhilosophersDrinking PhilosophersSynchronization MethodsSynchronization MethodsTopicsTopicsMutual-exclusion methodsProducer/consumer problemReaders/writers problemsemaphores.pptCS 105“Tour of the Black Holes of Computing”– 2 –CS 105Mutual ExclusionMutual ExclusionNeed ways to enforce critical sectionsNeed ways to enforce critical sectionsPrevent race conditions that cause errorsRequirements for mutual exclusionRequirements for mutual exclusionSafety: only one process/thread at a time inside CSProgress: if nobody has access and somebody wants in, somebody gets inNo starvation: if you want in, you will eventually get inDesirable properties:Desirable properties:Efficiency: can get into CS in relatively few instructionsLow load: waiting for CS doesn’t waste resourcesFairness: if you want in, nobody else gets in ahead of you twice– 3 –CS 105Hardware Mutex SupportHardware Mutex SupportTest and SetTest and SetRead word, set it nonzero, and set condition codesAll in one indivisible operationCompare and SwapCompare and SwapRead word, compare to register, store other register into wordAgain, indivisibleGeneralization of Test & Set– 4 –CS 105Example of Test and SetExample of Test and Setenter_critical_region:enter_critical_region:lealleallock, %eaxlock, %eax.L1:.L1:tsltsl(%eax)(%eax); Set lock NZ, set CC; Set lock NZ, set CCjnejne.L1.L1; Loop if was already NZ; Loop if was already NZ; We now have exclusive access; We now have exclusive accessretretleave:critical_region:leave:critical_region:xorxor%eax, %eax%eax, %eaxmovlmovl%eax, lock%eax, lockretret– 5 –CS 105Evaluating Test and SetEvaluating Test and Set+Very fast entry to unlocked regionVery fast entry to unlocked region+Easy to implementEasy to implement+Guarantees safety & progressGuarantees safety & progress-Wastes CPU when waiting (spin lock/busy wait)Wastes CPU when waiting (spin lock/busy wait)-Doesn’t make it easy for other threads to runDoesn’t make it easy for other threads to run-Extremely high memory (i.e., bus) trafficExtremely high memory (i.e., bus) traffic-Prone to errors (e.g., forget to unlock)Prone to errors (e.g., forget to unlock)-Prone to starvationProne to starvationFor these reasons, test & set is used only to implement For these reasons, test & set is used only to implement higher-level constructs.higher-level constructs.– 6 –CS 105SemaphoresSemaphoresHigher-level construct, discussed previouslyHigher-level construct, discussed previouslyInvented by Edsger DijkstraP(sem) or wait(sem) decrements and possibly waitsV(sem) or signal(sem) increments and lets somebody else inUsually implemented by operating systemUsually implemented by operating systemAllows scheduler to run different thread while waitingOS can guarantee fairness and no starvationOr can even enforce priority schemeMore flexibility for user (e.g., can count things)Still error-proneStill error-proneP’s and V’s must be matchedSingle extra V blows mutual exclusion entirely (compare TSL)– 7 –CS 105Problems in SynchronizationProblems in SynchronizationMany standard problems in concurrent programmingMany standard problems in concurrent programmingProducer/consumerReaders/writersDining philosophersDrinking philosophersEtc.Standard problems capture common situationsStandard problems capture common situationsAlso give way to evaluate proposed synchronization Also give way to evaluate proposed synchronization mechanismsmechanisms– 8 –CS 105MonitorsMonitorsHigh-level mutual-exclusion constructHigh-level mutual-exclusion constructInvented by C.A.R. “Tony” HoareDifficult or impossible to use incorrectlyLike Java/C++ class: combines data with functions needed to manage itKeys to monitor correctnessKeys to monitor correctnessData is available only to functions within monitorSpecific functions (gatekeepers) control accessOnly one process/thread allowed inside monitor at a timeQueues keep track of who is waiting for monitorTurns out to be hard to do certain things with monitorsTurns out to be hard to do certain things with monitorsProgrammers wind up standing on heads or implementing things like semaphores– 9 –CS 105The Producer/Consumer ProblemThe Producer/Consumer ProblemTwo processes communicateTwo processes communicateProducer generates things (e.g., messages) into a bufferConsumer takes those things and uses themCorrectness requirementsCorrectness requirementsProducer must wait if buffer is fullConsumer must not extract things from empty bufferSolutionsSolutionsCan be done with just load/store (but tricky)We have seen simple semaphore-based solutionPerfect application for monitors– 10 –CS 105Producer/Consumer with SemaphoresProducer/Consumer with Semaphoressemaphore mutex = 1, full = 0, empty = N;semaphore mutex = 1, full = 0, empty = N;void producer()void producer(){{while(1) {while(1) {message nextItem = produceItem();message nextItem = produceItem();P(&empty);P(&empty);P(&mutex);P(&mutex);enterInBuffer(nextItem);enterInBuffer(nextItem);V(&mutex);V(&mutex);V(&full);V(&full);}}}}– 11 –CS 105Producer/Consumer with Semaphores (continued)Producer/Consumer with Semaphores (continued)void consumer()void consumer(){{while(1) {while(1) {P(&full);P(&full);P(&mutex);P(&mutex);message nextItem = removeFromBuffer();message nextItem = removeFromBuffer();V(&mutex);V(&mutex);V(&empty);V(&empty);consumeItem(nextItem);consumeItem(nextItem);}}}}– 12 –CS 105Producer/Consumer with MonitorsProducer/Consumer with Monitorsmonitormonitor producerconsumermonitor; producerconsumermonitor;var var buffer[0..slots-1] buffer[0..slots-1] ofof message; message;slotsinuse: 0..slots;slotsinuse: 0..slots;nexttofill, nexttoempty: 0..slots-1;nexttofill, nexttoempty: 0..slots-1;bufferhasdata, bufferhasspace: condition;bufferhasdata, bufferhasspace:
View Full Document
Unlocking...