操作系统原理11

Chapter11:FileSystemImplementation沈卓炜h@[e-mail]四牌楼校区文正楼南205，83790819-802九龙湖校区计算机楼316Chapter11:FileSystemIlttiImplementation„FileSstemStrctre„FileSystemStructure„FileSystemImplementationyp„DirectoryImplementationAlltiMthd„AllocationMethods„Free-SpaceManagementpg„EfficiencyandPerformance„Recovery„Log-StructuredFileSystemsSoutheastUniversity11.2OperatingSystemConceptsLogStructuredFileSystems„NFSFile-SystemStructureeSysteStuctue„Filestrctre„Filestructure‹Logicalstorageunit‹Collectionofrelatedinformation„Filesystemresidesonsecondarystorage„Filesystemresidesonsecondarystorage(disks).„Filesystemorganizedintolayers.„Filecontrolblock–storagestructure„Filecontrolblockstoragestructureconsistingofinformationaboutafile.SoutheastUniversity11.3OperatingSystemConceptsLayeredFileSystemSoutheastUniversity11.4OperatingSystemConceptsATypicalFileControlBlockypcaeCotoocSoutheastUniversity11.5OperatingSystemConceptsIn-MemoryFileSystemStructureseoyeSysteStuctues„Thefolloingfigreillstratesthenecessar„Thefollowingfigureillustratesthenecessaryfilesystemstructuresprovidedbytheoperatingsystems.„Figure12-3(a)referstoopeningafile.„Figure12-3(b)referstoreadingafile„Figure12-3(b)referstoreadingafile.SoutheastUniversity11.6OperatingSystemConceptsIn-MemoryFileSystemStructuresSoutheastUniversity11.7OperatingSystemConceptsSoutheastUniversity11.8OperatingSystemConceptsSoutheastUniversity11.9OperatingSystemConceptsDirectoryImplementationectoypeetato„Linearlistoffilenameswithpointertothedatablocksdatablocks.‹simpletoprogram‹time-consumingtoexecute„HashTable–linearlistwithhashdatastructurestructure.‹decreasesdirectorysearchtime‹collisions–situationswheretwofilenameshashtothesamelocationSoutheastUniversity11.10OperatingSystemConceptsSoutheastUniversity11.11OperatingSystemConceptsAllocationMethodsocatoetods„Anallocationmethodreferstohodisk„Anallocationmethodreferstohowdiskblocksareallocatedforfiles:„Contiguousallocation„Contiguousallocation„Linkedallocation„IndexedallocationSoutheastUniversity11.12OperatingSystemConceptsContiguousAllocation„Eachfileoccupiesasetofcontiguousblocksonthedisk.„Simple–onlystartinglocation(block#)and„Simpleonlystartinglocation(block#)andlength(numberofblocks)arerequired.„Randomaccess.„Wastefulofspace(dynamicstorage-allocationproblem).SoutheastUniversity11.13OperatingSystemConcepts„Filescannotgrow.ContiguousAllocationofDiskSpaceSoutheastUniversity11.14OperatingSystemConceptsExtent-BasedSystemstetasedSystes„Manynewerfilesystems(I.e.VeritasFileSystem)useamodifiedcontiguousSystem)useamodifiedcontiguousallocationscheme.„Extentbasedfilesystemsallocatedisk„Extent-basedfilesystemsallocatediskblocksinextents.„Anextentisacontiguousblockofdisks„Anextentisacontiguousblockofdisks.Extentsareallocatedforfileallocation.AfileconsistsofoneormoreextentsSoutheastUniversity11.15OperatingSystemConceptsconsistsofoneormoreextents.LinkedAllocationedocato„Eachfileisalinkedlistofdiskblocksblocks„Eachfileisalinkedlistofdiskblocks:blocksmaybescatteredanywhereonthedisk.pointerblock=SoutheastUniversity11.16OperatingSystemConceptsLinkedAllocation(Cont.)edocato(Cot)„Simple–needonlystartingaddressf„Free-spacemanagementsystem–nowasteofspacep„Filescangrow„Norandomaccess„Eachblockcontainsapointer,wastingspaceBlktthdlb„BlocksscattereverywhereandalargenumberofdiskseeksmaybenecessarySoutheastUniversity11.17OperatingSystemConcepts„Reliability:whatifapointerislostordamaged?LinkedAllocationSoutheastUniversity11.18OperatingSystemConceptsFile-AllocationTableeocatoabeSoutheastUniversity11.19OperatingSystemConceptsIndexedAllocationdeedocato„Bringsallpointerstogetherintotheindeblock„Bringsallpointerstogetherintotheindexblock.„Afile’sdirectoryentrycontainsapointertoitsyypindex.Hence,theindexblockofanindexedallocationplaysthesameroleasthepageallocationplaysthesameroleasthepagetable.Lili„Logicalview.SoutheastUniversity11.20OperatingSystemConceptsindextableExampleofIndexedAllocationapeodeedocatoSoutheastUniversity11.21OperatingSystemConceptsIndexedAllocation(Cont.)Rd„Randomaccess„TheindexedallocationsuffersfromwastedTheindexedallocationsuffersfromwastedspace.Theindexblockmaynotbefullyused(ieinternalfragmentation)(i.e.,internalfragmentation).„Thenumberofentriesofanindextabledeterminesthesizeofafile.Toovercomethisproblem,wecanhavep,‹multipleindexblocks,chainthemintoalinked-list‹multipleindexblocksbutmakethematreejustlike‹multipleindexblocks,butmakethematreejustliketheindexedaccessmethod‹AbitifbthSoutheastUniversity11.22OperatingSystemConcepts‹AcombinationofbothIndexedAllocation(Cont.)deedocato(Cot)Mouter-indexindextablefileSoutheastUniversity11.23OperatingSystemConceptsCombinedScheme:UNIX(4Kbytesperblock))SoutheastUniversity11.24OperatingSystemConceptsFree-SpaceManagementeeSpaceaageet„Howdowekeeptrackfreeblocksonadisk?„Howdowekeeptrackfreeblocksonadisk?„Afree-listismaintained.Whenanewblockisrequestedwesearchthislisttofindoneisrequested,wesearchthislisttofindone.„Thefollowingarecommonlyusedtechniques:techniques:‹BitVector‹LinkedList‹LinkedList‹LinkedList+Grouping‹Lin