Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 2715-410, S’04- 1 -ReviewApr. 30, 2004Dave EckhardtDave EckhardtBruce MaggsBruce MaggsL38_Review15-410“...This is a transformative class...”15-410, S’04- 1 -SynchronizationP3 grading guidanceP3 grading guidanceWeights are approximate~70% shell works (no horrible hacks)~70% shell works (no horrible hacks)~20% tests~20% testsP3/P4 hurdle testsOther tests~10% structure/style~10% structure/style15-410, S’04- 1 -SynchronizationExam will be closed-bookExam will be closed-bookBut you may bring a 1-sided 8.5x11 sheet of notes6 point font or larger :-)Weakly non-cumulativeEmphasis on new material, design questionsYou will need to use some “old” knowledgeWe didn't really test on “P2 knowledge” (nor P3)15-410, S’04- 1 -SynchronizationFaculty evaluation formsFaculty evaluation formsAbout today's “review”About today's “review”More “reminders” than “course outline”Un-mentioned topic implies “text & lectures straightforward”Reading some of the textbook is advisable!15-410, S’04- 1 -Read Your CodeRe-read your P2Re-read your P2Re-read your P3Re-read your P3Go over feedbackGo over feedbackTalk about them with your partnerTalk about them with your partnerSchedule a timeYou should understand “the hard parts”You should understand “the hard parts”Focus on whichever part you know least well(or fear the most)15-410, S’04- 1 -“Concept” LecturesWe could ask a questionWe could ask a questionWe would give you some guidance/refresh your memoryExamplesExamplesAdvanced Disk SchedulingOS StructuresPlan 9Distributed clocks15-410, S’04- 1 -Core “Phase I” conceptsMachine modelMachine modelRegisters“regular”“special”Interrupt (vs. exception – how they differ, why)Process modelProcess modelYou should be a memory-map expertKernel space, user space, virtual memoryProcess vs. threadExactly what goes on a stack, where it comes from...15-410, S’04- 1 -Core “Phase I” conceptsMutual exclusionMutual exclusionmutex, cvar, what's inside, whyConcurrencyConcurrencyRace-condition expert!DeadlockDeadlockIngredientsVarious approaches to coping15-410, S’04- 1 -Virtual MemoryJobJobMaintain multiple illusions (aka “address spaces”)PlayersPlayersHigh-level info (COW, who uses which region)Mapping data structure (maybe chosen by processor)TLB – cache of v-to-p translations from that data structure“flush” - when, why, how?Game FeaturesGame FeaturesMappings are sparseThis explains the ways they're implemented15-410, S’04- 1 -Memory HierarchyWhy we must lieWhy we must lieWhy we can get away with itWhy we can get away with itLayering (“Pyramid of deception”)Layering (“Pyramid of deception”)Why layers can't be implemented the same wayLine size, placement, write-back, ...Line size, placement, write-back, ...Caches OS's typically manageCaches OS's typically manageCoherenceCoherence15-410, S’04- 1 -SchedulingRound-RobinRound-RobinThings people doThings people doMulti-level feedback queuesDubiousDubiousPriority““Priority Inheritance”Priority Inheritance”15-410, S’04- 1 -Disk schedulingSpinning platter/waving arm modelSpinning platter/waving arm modelSeek time vs. rotational latencySeek time vs. rotational latencyFCFS, SSTF, SCAN, LOOK, C-SCAN, C-LOOK, SPTF, FCFS, SSTF, SCAN, LOOK, C-SCAN, C-LOOK, SPTF, WSPTFWSPTFFairness, mean response time, variance, starvationFairness, mean response time, variance, starvationFreeblock schedulingFreeblock schedulingConcept15-410, S’04- 1 -Disk Array OverviewHistorical practicesHistorical practicesStriping, mirroringThe reliability problemThe reliability problemMore disks frequent array failuresCannot tolerate 1/N reliabilityParity, ECC, why parity is enoughParity, ECC, why parity is enoughErasure channelsGood terminology to display at parties15-410, S’04- 1 -Disk Array OverviewRAID “levels” (really: flavors)RAID “levels” (really: flavors)Understand RAID 0, 1, 4 vs. 5What they're good for, why15-410, S’04- 1 -File SystemsData access modelData access modelWhat it means for a file to be “open”Cache issuesCache issuesNamingNamingDirectory flavors, mountingCore problem: block mappingCore problem: block mappingCompare data structures to VM“Holes”ArchitectureArchitectureLayering to support multiple file system types, ...15-410, S’04- 1 -Distributed File SystemsClient-side redirectionClient-side redirectionWhich files are remote? How to operate remotely?CommunicationCommunicationRPC, XDRFlow of RPC operations to access a fileMount, lookup, accessBatching (what, why)Cache vs. consistency vs. locks15-410, S’04- 1 -IPCCommunicating process on one machineCommunicating process on one machineNamingNamingName server?File system?Message structureMessage structureSender id, priority, typeCapabilities: memory region, IPC rightsSynchronization/queueing/blockingSynchronization/queueing/blocking15-410, S’04- 1 -IPCGroup receiveGroup receiveCopy/share/transferCopy/share/transferA Unix surpriseA Unix surprisesendmsg()/recvmsg() pass file descriptors!15-410, S’04- 1 -RPC OverviewRPC = Remote RPC = Remote Procedure CallProcedure CallExtends IPC in two waysExtends IPC in two waysIPC = Inter-Process CommunicationOS-level: bytes, not objectsIPC restricted to single machineMarshallingMarshallingServer locationServer location15-410, S’04- 1 -RPC OverviewCall semanticsCall semanticsAsynch? Batch? Net/server failure?Client flow, server flowClient flow, server flowCleint stub routines, server dispatch skeletonJava RMIJava RMI(have some sense—obviously, we didn't make you use it)15-410, S’04- 1 -MarshallingValues must cross the networkValues must cross the networkMachine formats differMachine formats differSerialize/de-serializeFormat/packingType mismatch issues““The pointer problem”The pointer problem”15-410, S’04- 1 -Protection OverviewProtection vs. SecurityProtection vs. SecurityInside vs. outside “the box”Objects, operations, domainsObjects, operations, domainsAccess control Access control (least privilege)(least privilege)3 domain models3 domain
View Full Document