DOC PREVIEW
Harvey Mudd CS 105 - Synchronization Methods

This preview shows page 1-2-21-22 out of 22 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 MethodsTopicsTopicsMutual-exclusion methodsProducer/consumer problemReaders/writers problemCS 105“Tour of the Black Holes of Computing”– 2 –CS 105Mutual ExclusionMutual ExclusionNeed ways to enforce critical sectionsNeed ways to enforce critical sectionsPrevent race conditions that cause errorsRequirements for mutual exclusionRequirements for mutual exclusionSafety: only one process/thread at a time inside CSProgress: if nobody has access and somebody wants in, somebody gets inNo starvation: if you want in, you will eventually get inDesirable properties:Desirable properties:Efficiency: can get into CS in relatively few instructionsLow load: waiting for CS doesn’t waste resourcesFairness: 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 rightFailure to protect critical sectionsIncorrect use of primitivesDeadlockProgrammer-friendliness is big plusProgrammer-friendliness is big plus– 4 –CS 105Hardware Mutex SupportHardware Mutex SupportTest and SetTest and SetRead word, set it nonzero, and set condition codesAll in one indivisible operationCompare and SwapCompare and SwapRead word, compare to register, if match then store second register into wordAgain, indivisibleGeneralization 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 previouslyInvented by Edsger DijkstraP(sem) or wait(sem) decrements and possibly waitsV(sem) or signal(sem) increments and lets somebody else inUsually implemented by operating systemUsually implemented by operating systemAllows scheduler to run different thread while waitingOS can guarantee fairness and no starvationOr can even enforce priority schemeMore flexibility for user (e.g., can count things)Still error-proneStill error-proneP’s and V’s must be matchedSingle extra V blows mutual exclusion entirely (compare Test & Set)– 8 –CS 105MonitorsMonitorsHigh-level mutual-exclusion constructHigh-level mutual-exclusion constructInvented by C.A.R. “Tony” HoareDifficult or impossible to use incorrectlyLike Java/C++ class: combines data with functions needed to manage itKeys to monitor correctnessKeys to monitor correctnessData is available only to functions within monitorSpecific functions (gatekeepers) control accessOnly one process/thread allowed inside monitor at a timeQueues 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 monitorsProgrammers 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 programmingProducer/consumerReaders/writersDining philosophersDrinking philosophersEtc.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 communicateProducer generates things (e.g., messages) into a bufferConsumer takes those things and uses themCorrectness requirementsCorrectness requirementsProducer must wait if buffer is fullConsumer must not extract things from empty bufferSolutionsSolutionsCan be done with just load/store (but tricky)We have seen simple semaphore-based solution for one-element bufferPerfect 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

Harvey Mudd CS 105 - Synchronization Methods

Documents in this Course
Processes

Processes

25 pages

Processes

Processes

27 pages

Load more
Download Synchronization Methods
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Synchronization Methods and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Synchronization Methods 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?