lecture_15_file_system Implementation

《lecture_15_file_system Implementation》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

File-systemImplementationZhaoFangOperatingSystems-forthecollagestudents GoalforTodayFile-SystemStructureFile-SystemImplementationDirectoryImplementationFree-SpaceManagementUnixFileManagementLinuxVirtualFileSystemWindowsFileSystem ObjectivesTodescribethedetailsofimplementinglocalfilesystemsanddirectorystructuresTodescribetheimplementationofremotefilesystemsTodiscussblockallocationandfree-blockalgorithmsandtrade-offs File-SystemStructureFilestructureLogicalstorageunitCollectionofrelatedinformationFilesystemresidesonsecondarystorage(disks)Provideduserinterfacetostorage,mappinglogicaltophysicalProvidesefficientandconvenientaccesstodiskbyallowingdatatobestored,locatedretrievedeasily File-SystemStructureDiskprovidesin-placerewriteandrandomaccessI/Otransfersperformedinblocksofsectors(usually512bytes)Filecontrolblock–storagestructureconsistingofinformationaboutafileDevicedrivercontrolsthephysicaldeviceFilesystemorganizedintolayers Typicalsoftwareorganization DeviceDriversLowestlevelCommunicatesdirectlywithperipheraldevicesResponsibleforstartingI/OoperationsonadeviceProcessesthecompletionofanI/Orequest BasicFileSystemPhysicalI/OPrimaryinterfacewiththeenvironmentoutsidethecomputersystemDealswithexchangingblocksofdataConcernedwiththeplacementofblocksConcernedwithbufferingblocksinmainmemory BasicI/OSupervisorResponsibleforallfileI/Oinitiationandtermination.Controlstructuresdealwith•DeviceI/O,•Scheduling,•Filestatus.•SelectsandschedulesI/Owiththedevice LogicalI/OEnablesusersandapplicationstoaccessrecordsProvidesgeneral-purposerecordI/OcapabilityMaintainsbasicdataaboutfile ElementsofFileManagement File-SystemImplementationBootcontrolblockcontainsinfoneededbysystemtobootOSfromthatvolumeNeededifvolumecontainsOS,usuallyfirstblockofvolumeVolumecontrolblock(superblock,masterfiletable)containsvolumedetailsTotal#ofblocks,#offreeblocks,blocksize,freeblockpointersorarrayDirectorystructureorganizesthefilesNamesandinodenumbers,masterfiletable File-SystemImplementation(Cont.)Per-fileFileControlBlock(FCB)containsmanydetailsaboutthefileinodenumber,permissions,size,datesNFTSstoresintoinmasterfiletableusingrelationalDBstructures In-MemoryFileSystemStructuresMounttablestoringfilesystemmounts,mountpoints,filesystemtypesThefollowingfigureillustratesthenecessaryfilesystemstructuresprovidedbytheoperatingsystemsPlusbuffersholddatablocksfromsecondarystorageOpenreturnsafilehandleforsubsequentuseDatafromreadeventuallycopiedtospecifieduserprocessmemoryaddress In-MemoryFileSystemStructures PartitionsandMountingPartitioncanbeavolumecontainingafilesystem(“cooked”)orraw–justasequenceofblockswithnofilesystemRootpartitioncontainstheOS,otherpartitionscanholdotherOses,otherfilesystems,orberawMountedatboottimeOtherpartitionscanmountautomaticallyormanually VirtualFileSystemsVirtualFileSystems(VFS)onUnixprovideanobject-orientedwayofimplementingfilesystemsVFSallowsthesamesystemcallinterface(theAPI)tobeusedfordifferenttypesoffilesystemsSeparatesfile-systemgenericoperationsfromimplementationdetailsImplementsvnodeswhichholdinodesornetworkfiledetails VirtualFileSystems(Cont.)TheAPIistotheVFSinterface,ratherthananyspecifictypeoffilesystem VirtualFileSystemImplementationForexample,Linuxhasfourobjecttypes:inode,file,superblock,dentryVFSdefinessetofoperationsontheobjectsthatmustbeimplementedEveryobjecthasapointertoafunctiontableFunctiontablehasaddressesofroutinestoimplementthatfunctiononthatobject BlocksandrecordsRecordsarethelogicalunitofaccessofastructuredfileButblocksaretheunitforI/OwithsecondarystorageThreeapproachesarecommonFixedlengthblockingVariablelengthspannedblockingVariable-lengthunspannedblocking FixedBlockingFixed-lengthrecordsareused,andanintegralnumberofrecordsarestoredinablock.Unusedspaceattheendofablockisinternalfragmentation FixedBlocking VariableLengthSpannedBlockingVariable-lengthrecordsareusedandarepackedintoblockswithnounusedspace.SomerecordsmayspanmultipleblocksContinuationisindicatedbyapointertothesuccessorblock VariableBlocking:Spanned Variable-lengthunspannedblockingUsesvariablelengthrecordswithoutspanningWastedspaceinmostblocksbecauseoftheinabilitytousetheremainderofablockifthenextrecordislargerthantheremainingunusedspace. VariableBlocking:Unspanned SecondaryStorageManagementTheOperatingSystemisresponsibleforallocatingblockstofilesTworelatedissuesSpacemustbeallocatedtofilesMustkeeptrackofthespaceavailableforallocation Fileallocationissues1.Whenafileiscreated–isthemaximumspaceallocatedatonce?2.Spaceisaddedtoafileincontiguous‘portions’Whatsizeshouldbethe‘portion’?3.Whatdatastructureshouldbeusedtokeeptrackofthefileportions? PreallocationvsDynamicAllocationNeedthemaximumsizeforthefileatthetimeofcreationDifficulttoreliablyestimatethemaximumpotentialsizeofthefileTendtooverestimatedfilesizesoasnottorunoutofspace PortionsizeTwoextremes:PortionlargeenoughtoholdentirefileisallocatedAllocatespaceoneblockatatimeTrade-offbetweenefficiencyfromthepointofviewofasinglefile,ortheoverallsystemefficiency ContiguousAllocationFileblocksarestoredcontiguouslyondiskToallocateafile,SpecifythefilesizeSearchthediskallocationbitmapforconsecutivefreeblocksdatablocklocationnumberofblocksFileheader ContiguousAllocationMappingfromlogicaltophysicalQLA/512RBlocktobeaccessed=Q+startingaddressDisplacementintoblock=R ProsandConsofContiguousAllocation+Fastsequentialaccess+EaseofcomputingrandomfilelocationsAddinganoffsettothefirstdiskblocklocation-Externalfragmentation-Difficultyingrowingfiles Segment-BasedAllocationNeedsasegmenttabletoallocatemultiple,contiguousregionsofblocksbegin,endblocksbegin,endblocksFileheader ProsandConsofSegment-BasedAllocation+Relaxtherequirementsforlargecontiguousdiskregions-Fragmentation100%Segment-basedallocationIndexedallocation-Randomaccessesnotasfastaspurecontiguousallocation Linked-ListAllocationEachfileblockonadiskisassociatedwithapointertothenextblockAspecialmarkertoindicatetheendofthefilee.g.,MS-DOSfilesystemFileattributetable(FAT)datablocklocationnextblockentryFileheader ProsandConsofLinked-ListAllocation+Filescangrowdynamicallywithincrementalallocationofblocks-SequentialaccessmaysufferBlocksmaynotbecontiguous-HorriblerandomaccessesMayinvolvemultiplesequentialsearches-UnreliableAcorruptedpointercanleadtolossoftheremainingfile LinkedAllocation File-AllocationTable IndexedAllocationUsesapreallocatedindextodirectlytrackthefileblocklocationsdatablocklocationdatablocklocationFileheader ExampleofIndexedAllocation ProsandConsofIndexedAllocation+Fastlookupsandrandomaccesses-FileblocksmaybescatteredalloverthediskPoorsequentialaccessNeedsdefragmenter-Needstoreallocateindexasthefilesizeincreases MultilevelIndexedAllocationCertainindexentriespointtoindexblocks,asopposedtodatablocks(e.g.,Linuxext2)datablocklocationdatablocklocation12datablocklocationdatablocklocationindexblocklocationindexblocklocationindexblocklocationFileheader MultilevelIndexedAllocationAsingleindirectblockcontainspointerstodatablocksAdoubleindirectblockcontainspointerstosingleindirectblocksAtripleindirectblockcontainspointerstodoubleindirectblocks ProsandConsofMultilevelIndexedAllocation+OptimizedforsmallandlargefilesSmallfilesaccessedthroughthefirst12pointersLargefilescangrowincrementally-Multiplediskaccessestofetchadatablockundertripleindirectblock-Largestfilesizecappedbythenumberofpointers-Arbitraryfilesizeboundariesamonglevels HashedAllocationAllocatesadiskblockbyhashingtheblockcontenttoadisklocationdatablocklocationdatablocklocationdatablocklocationdatablocklocationOldfileheaderNewfileheader ProsandConsofHashedAllocation+Fileblocksofthesamecontentcansharethesamediskblocktosavestoragee.g.,emptyblocks+GoodforbackupsandarchivalSmallmodificationstoalargefileresultinonlyadditionalstorageofthechanges-Poordiskperformance FreeSpaceManagementJustasallocatedspacemustbemanaged,somusttheunallocatedspaceToperformfileallocation,weneedtoknowwhichblocksareavailable.Weneedadiskallocationtableinadditiontoafileallocationtable BitTablesThismethodusesavectorcontainingonebitforeachblockonthedisk.Eachentryofa0correspondstoafreeblock,andeach1correspondstoablockinuse.Advantages:WorkswellwithanyfileallocationmethodSmallaspossible ChainedFreePortionsThefreeportionsmaybechainedtogetherbyusingapointerandlengthvalueineachfreeportion.NegligiblespaceoverheadSuitedtoallfileallocationmethodsLeadstofragmentation IndexingtreatsfreespaceasafileandusesanindextableasitwouldforfileallocationForefficiency,theindexshouldbeonthebasisofvariable-sizeportionsratherthanblocks.Thus,thereisoneentryinthetableforeveryfreeportiononthedisk.Thisapproachprovidesefficientsupportforallofthefileallocationmethods. FreeBlockListEachblockisassignedanumbersequentiallythelistofthenumbersofallfreeblocksismaintainedinareservedportionofthedisk. VolumesAcollectionofaddressablesectorsinsecondarymemorythatanOSorapplicationcanusefordatastorage.Thesectorsinavolumeneednotbeconsecutiveonaphysicalstoragedevice;insteadtheyneedonlyappearthatwaytotheOSorapplication.Avolumemaybetheresultofassemblingandmergingsmallervolumes. UNIXFileManagementSixtypesoffilesRegular,orordinaryDirectorySpecialNamedpipesLinksSymboliclinks InodesIndexnodeControlstructurethatcontainskeyinformationforaparticularfile.SeveralfilenamesmaybeassociatedwithasingleinodeButanactiveinodeisassociatedwithonlyonefile,andEachfileiscontrolledbyonlyoneinode FreeBSDInodesinclude:ThetypeandaccessmodeofthefileThefile’sownerandgroup-accessidentifiersCreationtime,lastread/writetimeFilesizeSequenceofblockpointersNumberofblocksandNumberofdirectoryentriesBlocksizeofthedatablocksKernelandusersetableflagsGenerationnumberforthefileSizeofExtendedattributeinformationZeroormoreextendedattributeentries FreeBSDInodeandFileStructure FileAllocationFileallocationisdoneonablockbasis.AllocationisdynamicBlocksmaynotbecontiguousIndexmethodkeepstrackoffilesPartofindexstoredinthefileinode.InodeincludesanumberofdirectpointersAndthreeindirectpointers UNIXDirectoriesandInodesDirectoriesarefilescontaining:alistoffilenamesPointerstoinodes UNIXFileAccessControlFilesareassociatedwithpermissionsfor:UserIDGroupIDEveryoneelse UNIXFileAccessControl LinuxVirtualFileSystemUniformfilesysteminterfacetouserprocessesRepresentsanyconceivablefilesystem’sgeneralfeatureandbehaviorAssumesfilesareobjectsthatsharebasicpropertiesregardlessofthetargetfilesystem KeyingredientsofVFSStrategyAuserprocessissuesafilesystemcall(e.g.,read)usingtheVFSfilescheme.TheVFSconvertsthisintoaninternalfilesystemcallThenewcallispassedtoamappingfunctionforaspecificfilesystem TheroleofVFSwithintheKernel PrimaryObjectsinVFSSuperblockobjectaspecificmountedfilesystemInodeobjectaspecificfileDentryobjectaspecificdirectoryentryFileobjectanopenfileassociatedwithaprocess WindowsFileSystemKeyfeaturesofNTFSRecoverabilitySecurityLargedisksandlargefilesMultipledatastreamsJournalingCompressionandEncryption NTFSVolumeandFileStructureSectorThesmallestphysicalstorageunitonthediskAlmostalways512bytesClusterOneormorecontiguoussectorsVolumeLogicalpartitiononadisk EfficientwithLargeFilesVolumeSizeSectorsperClusterClusterSize512Mbyte1512bytes512Mbyte–1Gbyte21K1–2Gbyte42K2–4Gbyte84K4–8Gbyte168K8–16Gbyte3216K16–32Gbyte6432K>32Gbyte12864K NTFSVolumeLayoutEveryelementonavolumeisafile,andeveryfileconsistsofacollectionofattributes.Eventhedatacontentsofafileistreatedasanattribute. WindowsNTFSComponents Assignments1.Considerasystemthatsupportsthestrategiesofcontiguous,linked,andindexedallocation.Whatcriteriashouldbeusedindecidingwhichstrategyisbestutilizedforaparticularfile?2.ExplainhowtheVFSlayerallowsanoperatingsystemtosupportmultipletypesoffilesystemseasily.