MODERN OPERATING SYSTEMS Third Edition ANDREW S TANENBAUM ：现代操作系统第三版的安得烈Tanenbaum

MODERNOPERATINGSYSTEMSThirdEditionANDREWS.TANENBAUMChapter4FileSystemsTanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Essentialrequirementsforlong-terminformationstorage:Itmustbepossibletostoreaverylargeamountofinformation.Theinformationmustsurvivetheterminationoftheprocessusingit.Multipleprocessesmustbeabletoaccesstheinformationconcurrently.FileSystems(1)Tanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Thinkofadiskasalinearsequenceoffixed-sizeblocksandsupportingreadingandwritingofblocks.Questionsthatquicklyarise:Howdoyoufindinformation?Howdoyoukeeponeuserfromreadinganother’sdata?Howdoyouknowwhichblocksarefree?FileSystems(2)Tanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-1.Sometypicalfileextensions.FileNamingTanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-2.Threekindsoffiles.(a)Bytesequence.(b)Recordsequence.(c)Tree.FileStructureTanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-3.(a)Anexecutablefile.(b)Anarchive.FileTypesTanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-4a.Somepossiblefileattributes.FileAttributesTanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Themostcommonsystemcallsrelatingtofiles:FileOperationsTanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639 Append Seek GetAttributes SetAttributes Rename Create Delete Open Close Read WriteFigure4-5.Asimpleprogramtocopyafile.ExampleProgramUsingFileSystemCalls(1)Tanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639...Figure4-5.Asimpleprogramtocopyafile.ExampleProgramUsingFileSystemCalls(2)Tanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-6.Asingle-leveldirectorysystemcontainingfourfiles.HierarchicalDirectorySystems(1)Tanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-7.Ahierarchicaldirectorysystem.HierarchicalDirectorySystems(2)Tanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-8.AUNIXdirectorytree.PathNamesTanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Systemcallsformanagingdirectories:DirectoryOperationsTanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639 Readdir Rename Link Uplink Create Delete Opendir ClosedirFigure4-9.Apossiblefilesystemlayout.FileSystemLayoutTanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-10.(a)Contiguousallocationofdiskspacefor7files.(b)ThestateofthediskafterfilesDandFhavebeenremoved.ContiguousAllocationTanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-11.Storingafileasalinkedlistofdiskblocks.LinkedListAllocationTanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-12.Linkedlistallocationusingafileallocationtableinmainmemory.LinkedListAllocationUsingaTableinMemoryTanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-13.Anexamplei-node.I-nodesTanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-14.(a)Asimpledirectorycontainingfixed-sizeentrieswiththediskaddressesandattributesinthedirectoryentry.(b)Adirectoryinwhicheachentryjustreferstoani-node. ImplementingDirectories(1)Tanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-15.Twowaysofhandlinglongfilenamesinadirectory.(a)In-line.(b)Inaheap.ImplementingDirectories(2)Tanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-16.Filesystemcontainingasharedfile.SharedFiles(1)Tanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-17.(a)Situationpriortolinking.(b)Afterthelinkiscreated.(c)Aftertheoriginalownerremovesthefile.SharedFiles(2)Tanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639OperationsrequiredtoremoveafileinUNIX:Removethefilefromitsdirectory.Releasethei-nodetothepooloffreei-nodes.Returnallthediskblockstothepooloffreediskblocks.JournalingFileSystemsTanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-18.Positionofthevirtualfilesystem.VirtualFileSystems(1)Tanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-19.AsimplifiedviewofthedatastructuresandcodeusedbytheVFSandconcretefilesystemtodoaread.VirtualFileSystems(2)Tanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-20.Percentageoffilessmallerthanagivensize(inbytes).DiskSpaceManagementBlockSize(1)Tanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639DiskSpaceManagement(1) Darkline(lefthandscale)givesdatarateofadisk Dottedline(righthandscale)givesdiskspaceefficiency Allfiles2KBBlocksizeFigure4-22.(a)Storingthefreelistonalinkedlist.(b)Abitmap.KeepingTrackofFreeBlocks(1)Tanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-23.(a)Analmost-fullblockofpointerstofreediskblocksinmemoryandthreeblocksofpointersondisk.(b)Resultoffreeingathree-blockfile.(c)Analternativestrategyforhandlingthethreefreeblocks.Theshadedentriesrepresentpointerstofreediskblocks.KeepingTrackofFreeBlocks(2)Tanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-24.Quotasarekepttrackofonaper-userbasisinaquotatable.DiskQuotasTanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Backupstotapearegenerallymadetohandleoneoftwopotentialproblems:Recoverfromdisaster.Recoverfromstupidity.FileSystemBackups(1)Tanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-25.Afilesystemtobedumped.Squaresaredirectories,circlesarefiles.Shadeditemshavebeenmodifiedsincelastdump.Eachdirectoryandfileislabeledbyitsi-nodenumber.FileSystemBackups(2)Tanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-26.Bitmapsusedbythelogicaldumpingalgorithm.FileSystemBackups(3)Tanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-27.Filesystemstates.(a)Consistent.(b)Missingblock.(c)Duplicateblockinfreelist.(d)Duplicatedatablock.FileSystemConsistencyTanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-28.Thebuffercachedatastructures.Caching(1)Tanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639 Someblocks,suchasi-nodeblocks,arerarelyreferencedtwotimeswithinashortinterval.ConsideramodifiedLRUscheme,takingtwofactorsintoaccount:Istheblocklikelytobeneededagainsoon?Istheblockessentialtotheconsistencyofthefilesystem?Caching(2)Tanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-29.(a)I-nodesplacedatthestartofthedisk.(b)Diskdividedintocylindergroups,eachwithitsownblocksandi-nodes.ReducingDiskArmMotionTanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-30.TheISO9660directoryentry.TheISO9660FileSystemTanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639RockRidgeextensionfields:PX-POSIXattributes.PN-Majorandminordevicenumbers.SL-Symboliclink.NM-Alternativename.CL-Childlocation.PL-Parentlocation.RE-Relocation.TF-Timestamps.RockRidgeExtensionsTanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Jolietextensionfields:Longfilenames.Unicodecharacterset.Directorynestingdeeperthaneightlevels.DirectorynameswithextensionsJolietExtensionsTanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-31.TheMS-DOSdirectoryentry.TheMS-DOSFileSystem(1)Tanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-32.Maximumpartitionsizefordifferentblocksizes.Theemptyboxesrepresentforbiddencombinations.TheMS-DOSFileSystem(2)Tanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-33.AUNIXV7directoryentry.TheUNIXV7FileSystem(1)Tanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-34.AUNIXi-node.TheUNIXV7FileSystem(2)Tanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639Figure4-35.Thestepsinlookingup/usr/ast/mbox.TheUNIXV7FileSystem(3)Tanenbaum,ModernOperatingSystems3e,(c)2008Prentice-Hall,Inc.Allrightsreserved.0-13-6006639