operatingsystem《操作系统》ch11-filesystemimplementa

Chapter11:FileSystemImplementation,ChapterObjectives,TodescribethedetailsofimplementinglocalfilesystemsanddirectorystructuresTodescribetheimplementationofremotefilesystemsTodiscussblockallocationandfree-blockalgorithmsandtrade-offs,ContentOverview,File-SystemStructureFile-SystemImplementationDirectoryImplementationAllocationMethodsFree-SpaceManagementEfficiencyandPerformanceRecoveryLog-StructuredFileSystemsNFSExample:WAFLFileSystem,11.1File-SystemStructure,FilestructureLogicalstorageunitCollectionofrelatedinformationFilesystemresidesonsecondarystorage(disks)FilesystemorganizedintolayersFilecontrolblockstoragestructureconsistingofinformationaboutafile,LayeredFileSystem,11.2ATypicalFileControlBlock,In-MemoryFileSystemStructures,Thefollowingfigureillustratesthenecessaryfilesystemstructuresprovidedbytheoperatingsystems.Figure12-3(a)referstoopeningafile.Figure12-3(b)referstoreadingafile.,In-MemoryFileSystemStructures,VirtualFileSystems,VirtualFileSystems(VFS)provideanobject-orientedwayofimplementingfilesystems.VFSallowsthesamesystemcallinterface(theAPI)tobeusedfordifferenttypesoffilesystems.TheAPIistotheVFSinterface,ratherthananyspecifictypeoffilesystem.,SchematicViewofVirtualFileSystem,11.3DirectoryImplementation,Linearlistoffilenameswithpointertothedatablocks.simpletoprogramtime-consumingtoexecuteHashTablelinearlistwithhashdatastructure.decreasesdirectorysearchtimecollisionssituationswheretwofilenameshashtothesamelocationfixedsize,11.4AllocationMethods,Anallocationmethodreferstohowdiskblocksareallocatedforfiles:ContiguousallocationLinkedallocationIndexedallocation,ContiguousAllocation,EachfileoccupiesasetofcontiguousblocksonthediskSimpleonlystartinglocation(block#)andlength(numberofblocks)arerequiredRandomaccessWastefulofspace(dynamicstorage-allocationproblem)Filescannotgrow,ContiguousAllocationofDiskSpace,Extent-BasedSystems,Manynewerfilesystems(I.e.VeritasFileSystem)useamodifiedcontiguousallocationschemeExtent-basedfilesystemsallocatediskblocksinextentsAnextentisacontiguousblockofdisksExtentsareallocatedforfileallocationAfileconsistsofoneormoreextents.,LinkedAllocation,Eachfileisalinkedlistofdiskblocks:blocksmaybescatteredanywhereonthedisk.,LinkedAllocation(Cont.),SimpleneedonlystartingaddressFree-spacemanagementsystemnowasteofspaceNorandomaccess,File-allocationtable(FAT)disk-spaceallocationusedbyMS-DOSandOS/2.,LinkedAllocation,File-AllocationTable,IndexedAllocation,Bringsallpointerstogetherintotheindexblock.Logicalview.,indextable,ExampleofIndexedAllocation,IndexedAllocation(Cont.),NeedindextableRandomaccessDynamicaccesswithoutexternalfragmentation,buthaveoverheadofindexblock.,IndexedAllocationMapping(Cont.),outer-index,indextable,file,CombinedScheme:UNIX(4Kbytesperblock),11.5Free-SpaceManagement,Bitvector(nblocks),0,1,2,n-1,biti=,1blockifree0blockioccupied,Blocknumbercalculation,(numberofbitsperword)*(numberof0-valuewords)+offsetoffirst1bit,Free-SpaceManagement(Cont.),BitmaprequiresextraspaceExample:blocksize=212bytesdisksize=230bytes(1gigabyte)n=230/212=218bits(or32Kbytes)EasytogetcontiguousfilesLinkedlist(freelist)CannotgetcontiguousspaceeasilyNowasteofspaceGroupingCounting,LinkedFreeSpaceListonDisk,11.6EfficiencyandPerformance,Efficiencydependenton:diskallocationanddirectoryalgorithmstypesofdatakeptinfilesdirectoryentryPerformancediskcacheseparatesectionofmainmemoryforfrequentlyusedblocksfree-behindandread-aheadtechniquestooptimizesequentialaccessimprovePCperformancebydedicatingsectionofmemoryasvirtualdisk,orRAMdisk,PageCache,ApagecachecachespagesratherthandiskblocksusingvirtualmemorytechniquesMemory-mappedI/OusesapagecacheRoutineI/Othroughthefilesystemusesthebuffer(disk)cacheThisleadstothefollowingfigure,I/OWithoutaUnifiedBufferCache,UnifiedBufferCache,Aunifiedbuffercacheusesthesamepagecachetocachebothmemory-mappedpagesandordinaryfilesystemI/O,I/OUsingaUnifiedBufferCache,11.7Recovery,Consistencycheckingcomparesdataindirectorystructurewithdatablocksondisk,andtriestofixinconsistenciesUsesystemprogramstobackupdatafromdisktoanotherstoragedevice(floppydisk,magnetictape,othermagneticdisk,optical)Recoverlostfileordiskbyrestoringdatafrombackup,11.8LogStructuredFileSystems,Logstructured(orjournaling)filesystemsrecordeachupdatetothefilesystemasatransactionAlltransactionsarewrittentoalogAtransactionisconsideredcommittedonceitiswrittentothelogHowever,thefilesystemmaynotyetbeupdatedThetransactionsinthelogareasynchronouslywrittentothefilesystemWhenthefilesystemismodified,thetransactionisremovedfromthelogIfthefilesystemcrashes,allremainingtransactionsinthelogmuststillbeperformed,11.9TheSunNetworkFileSystem(NFS),AnimplementationandaspecificationofasoftwaresystemforaccessingremotefilesacrossLANs(orWANs)TheimplementationispartoftheSolarisandSunOSoperatingsystemsrunningonSunworkstationsusinganunreliabledatagramprotocol(UDP/IPprotocolandEthernet,NFS(Cont.),Interconnectedworkstationsviewedasasetofindependentmachineswithindependentfilesystems,whichallowssharingamongthesefilesystemsinatransparentmannerAremotedirectoryismountedoveralocalfilesystemdirectoryThemounteddirectorylookslikeanintegralsubtreeofthelocalfilesystem,replacingthesubtreedescendingfromthelocaldirectorySpecificationoftheremotedirectoryforthemountoperationisnontransparent;thehostnameoftheremotedirectoryhastobeprovidedFilesintheremotedirectorycanthenbeaccessedinatransparentmannerSubjecttoaccess-rightsaccreditation,potentiallyanyfilesystem(ordirectorywithinafilesystem),canbemountedremotelyontopofanylocaldirectory,NFS(Cont.),NFSisdesignedtooperateinaheterogeneousenvironmentofdifferentmachines,operatingsystems,andnetworkarchitectures;theNFSspecificationsindependentofthesemediaThisindependenceisachievedthroughtheuseofRPCprimitivesbuiltontopofanExternalDataRepresentation(XDR)protocolusedbetweentwoimplementation-independentinterfacesTheNFSspecificationdistinguishesbetweentheservicesprovidedbyamountmechanismandtheactualremote-file-accessservices,ThreeIndependentFileSystems,MountinginNFS,Mounts,Cascadingmounts,NFSMountProtocol,EstablishesinitiallogicalconnectionbetweenserverandclientMountoperationincludesnameofremotedirectorytobemountedandnameofservermachinestoringitMountrequestismappedtocorrespondingRPCandforwardedtomountserverrunningonservermachineExportlistspecifieslocalfilesystemsthatserverexportsformounting,alongwithnamesofmachinesthatarepermittedtomountthemFollowingamountrequestthatconformstoitsexportlist,theserverreturnsafilehandleakeyforfurtheraccessesFilehandleafile-systemidentifier,andaninodenumbertoidentifythemounteddirectorywithintheexportedfilesystemThemountoperationchangesonlytheusersviewanddoesnotaffecttheserverside,NFSProtocol,Providesasetofremoteprocedurecallsforremotefileoperations.Theproceduressupportthefollowingoperations:searchingforafilewithinadirectoryreadingasetofdirectoryentriesmanipulatinglinksanddirectoriesaccessingfileattributesreadingandwritingfilesNFSserversarestateless;eachrequesthastoprovideafullsetofarguments(NFSV4isjustcomingavailableverydifferent,stateful)Modifieddatamustbecommittedtotheserversdiskbeforeresultsarereturnedtotheclient(loseadvantagesofcaching)TheNFSprotocoldoesnotprovideconcurrency-controlmechanisms,ThreeMajorLayersofNFSArchitecture,UNIXfile-systeminterface(basedontheopen,read,write,andclosecalls,andfiledescriptors)VirtualFileSystem(VFS)layerdistinguisheslocalfilesfromremoteones,andlocalfilesarefurtherdistinguishedaccordingtotheirfile-systemtypesTheVFSactivatesfile-system-specificoperationstohandlelocalrequestsaccordingtotheirfile-systemtypesCallstheNFSprotocolproceduresforremoterequestsNFSservicelayerbottomlayerofthearchitectureImplementstheNFSprotocol,SchematicViewofNFSArchitecture,NFSPath-NameTranslation,PerformedbybreakingthepathintocomponentnamesandperformingaseparateNFSlookupcallforeverypairofcomponentnameanddirectoryvnodeTomakelookupfaster,adirectorynamelookupcacheontheclientssideholdsthevnodesforremotedirectorynames,NFSRemoteOperations,Ne