操作系統(tǒng)原理英文版課件：Chapter 11 File System Implementation

Chapter11FileSystemImplementationOperatingSystemConceptsChapter11:FileSystemImplementationFileSystemStructureFileSystemImplementationDirectoryImplementationAllocationMethodsFree-SpaceManagementEfficiencyandPerformanceRecoveryLog-StructuredFileSystemsNFSOperatingSystemConceptsFile-SystemStructureFilestructureLogicalstorageunitCollectionofrelatedinformationFilesystemresidesonsecondarystorage(disks).Filesystemorganizedintolayers.Filecontrolblock–storagestructureconsistingofinformationaboutafile.OperatingSystemConceptsLayeredFileSystemOperatingSystemConceptsATypicalFileControlBlockOperatingSystemConceptsIn-MemoryFileSystemStructuresThefollowingfigureillustratesthenecessaryfilesystemstructuresprovidedbytheoperatingsystems.Figure12-3(a)referstoopeningafile.Figure12-3(b)referstoreadingafile.OperatingSystemConceptsIn-MemoryFileSystemStructuresOperatingSystemConceptsOperatingSystemConceptsOperatingSystemConceptsDirectoryImplementationLinearlistoffilenameswithpointertothedatablocks.simpletoprogramtime-consumingtoexecute

HashTable–linearlistwithhashdatastructure.decreasesdirectorysearchtimecollisions–situationswheretwofilenameshashtothesamelocationOperatingSystemConceptsOperatingSystemConceptsAllocationMethodsAnallocationmethodreferstohowdiskblocksareallocatedforfiles:ContiguousallocationLinkedallocationIndexedallocationOperatingSystemConceptsContiguousAllocationEachfileoccupiesasetofcontiguousblocksonthedisk.

Simple–onlystartinglocation(block#)andlength(numberofblocks)arerequired.

Randomaccess.

Wastefulofspace(dynamicstorage-allocationproblem).

Filescannotgrow.OperatingSystemConceptsContiguousAllocationofDiskSpaceOperatingSystemConceptsLinkedAllocationEachfileisalinkedlistofdiskblocks:blocksmaybescatteredanywhereonthedisk.pointerblock=OperatingSystemConceptsLinkedAllocation(Cont.)Simple–needonlystartingaddressFree-spacemanagementsystem–nowasteofspaceFilescangrowNorandomaccessEachblockcontainsapointer,wastingspaceBlocksscattereverywhereandalargenumberofdiskseeksmaybenecessaryReliability:whatifapointerislostordamaged?OperatingSystemConceptsLinkedAllocationLinkedAllocationOperatingSystemConceptsStoringafileasalinkedlistofdiskblocks.OperatingSystemConceptsFile-AllocationTableLinkedListAllocationUsingaFATinMemory

OperatingSystemConceptsThewholeFATmaybeverylarge(200GBdisk,1KBblock,200millionitems!)OperatingSystemConceptsIndexedAllocationBringsallpointerstogetherintotheindexblock.Afile’sdirectoryentrycontainsapointertoitsindex.Hence,theindexblockofanindexedallocationplaysthesameroleasthepagetable.Logicalview.indextableOperatingSystemConceptsExampleofIndexedAllocationExampleofIndexedAllocationOperatingSystemConceptsSpacesmallerthanFAT,why?(FAT正比于磁盤大小，inode正比于打開的文件數(shù))Anexamplei-node.OperatingSystemConceptsIndexedAllocation(Cont.)RandomaccessTheindexedallocationsuffersfromwastedspace.Theindexblockmaynotbefullyused(i.e.,internalfragmentation).Thenumberofentriesofanindextabledeterminesthesizeofafile.Toovercomethisproblem,wecanhavemultipleindexblocks,chainthemintoalinked-listmultipleindexblocks,butmakethematreejustliketheindexedaccessmethodAcombinationofbothOperatingSystemConceptsIndexedAllocation(Cont.)outer-indexindextablefileOperatingSystemConceptsCombinedScheme:UNIX(4Kbytesperblock)OperatingSystemConceptsFree-SpaceManagementHowdowekeeptrackfreeblocksonadisk?Afree-listismaintained.Whenanewblockisrequested,wesearchthislisttofindone.Thefollowingarecommonlyusedtechniques:BitVectorLinkedListLinkedList+GroupingLinkedList+Address+CountOperatingSystemConceptsBitvectorBitvector(nblocks)…012n-1bit[i]=1block[i]free0

block[i]occupiedBlocknumbercalculation(numberofbitsperword)*(numberof0-valuewords)+offsetoffirst1bitOperatingSystemConceptsFree-SpaceManagement(Cont.)Bitmaprequiresextraspace.Example: blocksize=212bytes disksize=230bytes(1gigabyte)

n=230/212=218bits(or32Kbytes)EasytogetcontiguousfilesLinkedlist(freelist)CannotgetcontiguousspaceeasilyNowasteofspaceOperatingSystemConceptsLinkedFreeSpaceListonDiskOperatingSystemConceptsGroupingThefirstfreeblockcontainstheaddressesofnotherfreeblocks.Foreachgroup,thefirstn-1blocksareactuallyfreeandthelast(i.e.,n-th)blockcontainstheaddressesofthenextgroup.Inthisway,wecanquicklylocatefreeblocks.OperatingSystemConceptsAddresscountingWecanmakethelistshortwiththefollowingtrick:BlocksareoftenallocatedandfreedingroupsWecanstoretheaddressofthefirstfreeblockandthenumberofthefollowingnfreeblocks.OperatingSystemConceptsEfficiencyandPerformanceEfficiencydependenton:diskallocationanddirectoryalgorithmstypesofdatakeptinfile’sdirectoryentryPerformancediskcache–separatesectionofmainmemoryforfrequentlyusedblocksfree-behindandread-ahead–techniquestooptimizesequentialaccessimp