现代操作系统课件：Chapter5-Disks

ModernOperatingSystems

Chapter5–DisksZhangYangSpring2013ContentoftheLecture5.4DisksDiskHardwareMagneticDisksDiskFormattingDiskArmSchedulingAlgorithmErrorHandlingStableStorageMagneticDisks(1)OrganizedintocylindersEachcylinderscontainstrackswhosenumberisequaltothenumberofheadsinthediskdriveEachtrackisdividedintoanumberofsectors.E.g.forfloppydisks,8-32sectors/track.

Thesectorsizeisusually512bytes.ThereareIDE,SCSI,FiberChannel,andSATAharddisks.OnecylinderOnetrackOnesectorMagneticDisks(2)MagneticDisks(3)Figure5-18DiskparametersfortheoriginalIBMPCfloppydiskandaWesternDigitalWD18300harddiskAHardDiskDiskArmArmmotionpathDiskHeadOneplatterMagneticDisks(4)MagneticDisks(5)Figure5-19(a)Physicalgeometryofadiskwithtwozones(b)ApossiblevirtualgeometryforthisdiskMagneticDisks(6)DiskAddressingMillionsofsectorsonthediskmustbelabeledTwopossibilitiesCylinder/head/sector(CHS)Sequentialnumbering(LBA)ModerndrivesusesequentialnumbersDisksmapsequentialnumbersintospecificlocationLogicalBlockAddressingorLBA

MappingmaybemodifiedbythediskRemapbadsectorsOptimizeperformanceHidetheexactgeometry,makinglifesimplerfortheOSMagneticDisks(7)DiskFormatting(1)Aftermanufacturing,thereisnoinformationonthediskJustemptybitsEachplatterneedtohaveAlow-levelformatAhigh-levelformatbeforediskcanbeused.Low-levelFormattingDividingadiskintosectorsthatthediskcontrollercanreadandwrite.Low-levelformattingisusuallydonebyvendorsDiskFormatting(2)Low-LevelFormatting(ctd.)Eachtrackshouldhaveformattedinthefollowingway:Sectorsandinter-sector-gapbetweenthemAsectorwillbehaveformatlikethefollowing:Preamble–data(512bytes)–ChecksumsectorsectorsectorpreambleData(512bytes)ECC(~16bytes)certainbitpatterncylindernumbersectornumberDiskFormatting(3)Low-LevelFormatting(ctd.)CylinderSkewWhenreadingsequentialblocks,theseektimecanresultinmissingblock0inthenexttrack.Diskcanbeformattedusingacylinderskewtoavoidthis.CylinderSkew:Startcylindersatdifferentpointstogivetheheadtimetojumpfromonetothenext.Example:10000rpmdiskdrive,300sectorspertrack,seektime800us,thecylinderskewis40sectors10000rpmDriverotatesin6msTrackhas300sectorsNewsectorevery20µsIftrackseektime800µs40sectorspassonseekDiskFormatting(4)0123456789101112131415161718192021222301234567910111213141516171819202122232401234567891011121314151617181920212223DirectionofrotationSweeppath>timetochangetrack(cyclinder)DiskFormatting(5)Low-LevelFormatting(ctd.)InterleavingIfwehaveONEsectorbufferinthediskcontrollerAfterwehavetransferredonesectorofdatafromhard-disktocontrollerbuffer:WewillcopythecontrollerbuffertothememoryDuringthistime,thedisk-headwillpassthestartofthenextsector.Therefore,thenextlogicalsector,shouldnotbethenextphysicalsectorinhard-disk.Thereshouldbesomeinterleaving.DiskFormatting(6)01234567910111213141516171819202122232401234567891011121314151617181920212223registersregistersCPUMEMORYDiskController1sectorbuffer(1)(2)(3)DiskFormatting(7)Low-LevelFormatting(ctd.)Interleaving(ctd.)(a)Nointerleaving(b)Singleinterleaving(morecommon)Skippingonesectorbetweenreads(c)DoubleinterleavingSkippingtwosectorsbetweenreadsDiskFormatting(8)Low-LevelFormatting(ctd.)Interleaving(ctd.)Moderndrivesovercomeinterleavingtypeissuesbysimplyreadingtheentiretrack(orpartthereof)intotheon-diskcontrollerandcachingit.DiskFormatting(9)DiskPartitioningEachpartitionislikeaseparatediskSector0isMBR

Containsbootcode+partitiontablePartitiontablehasstartingsectorandsizeofeachpartitionHigh-levelformattingDoneforeachpartitionSpecifiesbootblock,freelist,rootdirectory,emptyfilesystemWhathappensonboot?BIOSloadsMBR,bootprogramcheckstoseeactivepartitionReadsbootsectorfromthatpartitionthatthenloadsOSkernel,etcDiskFormatting(10)DiskPartitioning(ctd.)DiskFormatting(11)DiskPartitioning(ctd.)DiskQueues(1)DiskQueues(2)DiskSectorXMem

Ptr0nextentryEntry1SectorYMem

Ptr1nextentryEntry2SectorZMem

Ptr2nextentryEntry3headtailDiskArmScheduling(1)Howlongdoesittaketoreadablock(sector)PositioningTime+TransferTimePositioningTimeSeekTimeMovearmtothecorrectcylinderRotationalDelayWaituntilcorrectsectorcomesunderhead.ActualdatatransfertimeFormostsystems,theseektimedominatestheothertwotimes.DiskArmScheduling(2)Assumethediskisheavilyloaded.Therearealotofrequestsfordiskblocksthatarearrivingtotheharddiskdriver.Thedriversqueuestherequests.Thedriverknowsforeachblockrequest,whereinharddisktheblockshouldbestored(thecylindernumber).Sincemovingbetweencylinders(seektime)iscostly,weshouldtrytominimizetheseseektimes.DiskArmScheduling(3)DiskDriverKeepsatableofrequests.TableisindexedbythecylindernumberBlocksrequestsforthesamecylinderareputinalinkedlist.xxxxx05101520InitialpositionpendingrequestscylindernumberDiskArmSchedulingAlgorithmsFCFS(1)Servetherequestintheordertheyarrive(don’tlooktothecylindernumbers)ExampleAssumethecurrentpositioniscylinder11.Thefollowingrequestsarriveinthegiventimeorder:1,36,16,34,9,12Therequestwillbeservedinthesameorder.Theheadwillgoto:Cylinder1first(10cylindermotion)Cylinder36next(35cylindermotion)Cylinder16next(20)Cylinder34next(18)Cylinder9next(25)Cylinder12next(3)Totalof111cylindersareskipped.Cost=111FCFS(2)xxxxx

xx051015

20253035

Newrequestarrivalsequence:1,36,16,34,9,12Initialheadpositionxxxxx

xx051015

20253035

Newrequestarrivalsequence:1,36,16,34,9,12InitialheadpositionIssueThegoalsofminimalresponsetimeandfairnessareinconflicthere.Examplexxxxx

xx051015

20253035

Newrequestarrivalsequence:1,36,16,34,9,12InitialheadpositionAftergoingto16,anewrequestfor8ispresent,then13.ElevatorAlgorithm(1)AlsocalledSCANalgorithm.Dolikewhatanelevatordoes.1.Moveinonedirectionuntilallrequestinthatdirectionisserved2.Thenchangedirection.3.Moveinthenewdirectionuntilallrequestinthatdirectionareserver.Repeatsteps1,2,and3.InthepreviousexampleAssumeinitialpositionwas11andinitialdirectionwasup(goingtohighernumberedcylinders).ElevatorAlgorithm(2)Therequestareserverinthefollowingorder:12,16,34,36,9,1Armmotions(#ofcylinderskips)1,4,18,2,27,8Totalcost=60cylinders.Performsgoodandisfair.Softwareshouldmaintain1bittoknowthedirection.ElevatoralsoshouldknowwhetheritisgoingUPorDOWNElevatorAlgorithm(3)xxxxx

xx051015

20253035

Newrequestarrivalsequence:1,36,16,34,9,12InitialheadpositionC-SCAN(1)Providesamoreuni