Synchronization MethodsMutual ExclusionAdditional RequirementsHardware Mutex SupportExample of Test and SetEvaluating Test and SetSemaphoresMonitorsProblems in SynchronizationThe Producer/Consumer ProblemProducer/Consumer with MonitorsProducer/Consumer with Monitors (continued)The Readers/Writers ProblemReaders/Writers with Semaphores (Polling Version)Readers/Writers with Semaphores (Polling continued)Slide 16Readers/Writers with MonitorsReaders/Writers with Monitors (continued)Slide 19Dining PhilosophersDeadlock and StarvationDrinking PhilosophersSynchronization MethodsSynchronization MethodsTopicsTopicsMutual-exclusion methodsProducer/consumer problemReaders/writers problemCS 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 105Additional RequirementsAdditional RequirementsSynchronization is tricky to get rightSynchronization is tricky to get rightFailure to protect critical sectionsIncorrect use of primitivesDeadlockProgrammer-friendliness is big plusProgrammer-friendliness is big plus– 4 –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, if match then store second register into wordAgain, indivisibleGeneralization of Test & Set– 5 –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– 6 –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.– 7 –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 Test & Set)– 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 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– 10 –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 solution for one-element bufferPerfect application for monitors– 11 –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: condition;procedureprocedure fillslot( fillslot(var var data: message) data: message) beginbeginif if slotsinuse = slots;slotsinuse = slots;then then wait(bufferhasspace);wait(bufferhasspace);buffer[nexttofill] := data;buffer[nexttofill] := data;nexttofill := (nexttofill + 1) nexttofill := (nexttofill + 1) modmod slots; slots; slotsinuse := slotsinuse + 1;slotsinuse := slotsinuse + 1;signal(bufferhasdata);signal(bufferhasdata);end;end;– 12 –CS 105Producer/Consumer with Monitors
View Full Document