现代操作系统 Chapter 4.ppt

Chapter4Filesystems 2 Contents 4 1Files4 2Directories4 3FileSystemImplementation4 4FileSystemManagementandOptimization4 5ExampleFileSystems 3 FileSystems Essentialrequirementsforlong terminformationstorage Itmustbepossibletostoreaverylargeamountofinformation Theinformationmustsurvivetheterminationoftheprocessusingit Multipleprocessesmustbeabletoaccesstheinformationconcurrently 4 FileSystems Filesarelogicalunitsofinformationcreatedbyprocesses ThatpartoftheOSdealingwithfilesisknownasthefilesystem 5 4 1Files 4 1 1FilenamingWhenaprocesscreatesafile itgivesthefileaname Whentheprocessterminates thefilecontinuestoexistandcanbeaccessedbyotherprocessesusingitsname Therulesoffilenaming 文件命名规则 Fileextension 文件扩展名 6 Figure4 2 Threekindsoffiles a Bytesequence b Recordsequence c Tree 4 1 2Filestructure 7 4 1 3FileTypes Regularfile 普通文件 ASCIIfilesBinaryfilesSpecialfile 特殊文件 Characterspecialfile arerelatedtoinput outputandusedtomodelserialI OdevicesBlockspecialfile areusedtomodeldisks 8 4 1 4Fileaccess Sequentialaccess 顺序存取 Aprocesscouldreadallthebytesorrecordsinafileinorder startingatthebeginning butcouldnotskiparoundandreadthemoutoforder Randomaccess 随机存取 Thebytesorrecordsinthesefilescanbereadinanyorder 9 4 1 5Fileattributes Figure4 4 Somepossiblefileattributes 10 4 1 6FileOperations CreateDeleteOpenCloseReadWrite AppendSeekGetattributesSetattributesRename 11 4 1 7Anexampleprogramusingfilesystemcalls 1 12 Anexampleprogramusingfilesystemcalls 2 13 4 2Directories 1 Single levelDirectorysystemsAdvantages SimplicityTheabilitytolocatefilequickly 14 Directories 2 Hierarchical 层次 directorysystems Advantages cangroupfilesinnaturalways 15 Directories 3 PathnamesAbsolutepathname 绝对路径 consistingofthepathfromtherootdirectorytothefile Italwaysstartattherootdirectoryandareunique Relativepathname 相对路径 itisusedinconjunctionwiththeconceptoftheworkingdirectory 16 Directories 4 DirectoryOperationsCreateDeleteOpendirClosedirReaddirRenameLinkUnlink 17 4 3FileSystemImplementation 4 3 1FileSystemLayout4 3 2ImplementingFiles4 3 3Implementingdirectories4 3 4Sharedfiles4 3 5JournalingFileSystems JFS 4 3 6VirtualFileSystems VFS 18 4 3 1FileSystemLayout 布局 Sector0ofthediskiscalledtheMBR MasterBootRecord 主引导记录 andisusedtobootthecomputer TheendoftheMBRcontainsthepartitiontable 19 4 3 2ImplementingFiles Themostimportantissueinimplementingfilestorageiskeepingtrackofwhichdiskblocksgowithwhichfile Contiguousallocation 连续分配 Linkedlistallocation 链表分配 Linkedlistallocationusingatableinmemoryi nodes 20 1 Contiguousallocation Thesimplestallocationschemeistostoreeachfileasacontiguousrunofdiskblocks 21 Contiguousallocation Figure4 10 a Contiguousallocationofdiskspacefor7files b ThestateofthediskafterfilesDandFhavebeenremoved 22 Contiguousallocation Advantages Itissimpletoimplement Thereadperformanceisexcellent Disadvantage Overthecourseoftime thediskbecomesfragmented Anexampleofcontiguousallocation CD ROM 23 2 Linkedlistallocation Linkedlistallocation Thefirstwordofeachblockisusedasapointertothenextone Therestoftheblockisfordata 24 Linkedlistallocation Figure4 11 Storingafileasalinkedlistofdiskblocks 25 Linkedlistallocation Advantage everydiskblockcanbeused Nospaceislosttodiskfragmentation exceptforinternalfragmentationinthelastblock Disadvantage randomaccessisextremelyslowTheamountofdatastorageinablockisnolongerapoweroftwobecausethepointertakesupafewbytes 26 3 Linkedlistallocationusingatableinmemory Bothdisadvantagesofthelinkedlistallocationcanbeeliminatedbytakingthepointerwordfromeachdiskblockandputtingitinatableinmemory SuchatableinmainmemoryiscalledaFAT FileAllocationTable 文件分配表 27 Linkedlistallocationusingatableinmemory Figure4 12 Linkedlistallocationusingafileallocationtableinmainmemory Disadvantage theentiretablemustbeinmemoryallthetimetomakeitwork TheFATideadoesn tscalewelltolargedisks 28 4 i nodes Figure4 13 Anexamplei node Associatewitheachfileadatastructurecalledani node whichliststheattributesanddiskaddressesofthefile sblocks Advantage thei nodeneedonlybeinmemorywhenthecorrespondingfileisopen 29 4 3 3Implementingdirectories Whenafileisopened theOSusesthepathnamesuppliedbytheusertolocatethedirectoryentry Thedirectoryentryprovidestheinformationneededtofindthediskblocks ThemainfunctionofthedirectorysystemistomaptheASCIInameofthefileontotheinformationneededtolocatethedata 30 Implementingdirectories Whereshouldtheattributesbestored 1 Oneobviouspossibilityistostorethemdirectlyinthedirectoryentry 31 Implementingdirectories 2 Forsystemsthatusei nodes anotherpossibilityforstoringtheattributesisinthei nodes ratherthaninthedirectoryentries 32 Implementingdirectories Sofarwehavemadetheassumptionthatfileshaveshort fixed lengthnames However nearlyallmodernOSsupportlonger variable lengthfilenames Howcanthesebeimplemented Method1 tosetalimitonfilenamelength typically255characters andthenuseoneofthedesignsofFig4 14 Thisapproachwastesagreatdealofdirectoryspace sincefewfileshavesuchlongnames 33 Method2 eachdirectoryentrycontainsafixedportion typicallystartingwiththelengthoftheentry andthenfollowedbydatawithafixedformat usuallyincludingthefileattributes Thisfixed lengthheaderisfollowedbytheactualfilename Implementingdirectories 34 Implementingdirectories Method3 makethedirectoryentriesthemselvesallfixedlengthandkeepthefilenamestogetherinaheap 堆 attheendofthedirectory 35 4 3 4Sharedfiles Whenseveralusersareworkingtogetheronaproject theyoftenneedtosharefiles 36 Sharedfiles Solution1 diskblocksarenotlistedindirectories butini node ThisistheapproachusedinUNIX Hardlink 硬链接 Solution2 BlinkstooneofC sfilesbyhavingthesystemcreateanewfile oftypeLINK Thenewfilecontainsjustthepathnameofthefiletowhichitislinked Symboliclink 符号链接 37 Disadvantagesofthetwosolutions Hardlink Symboliclink requireextraoverhead 38 4 3 5JournalingFileSystems JFS Thebasicideaistokeepalogofwhatthefilesystemisgoingtodobeforeitdoesit sothatifthesystemcrashesbeforeitcandoitsplannedwork uponrebootingthesystemcanlookinthelogtoseewhatwasgoingonatthetimeofthecrashandfinishthejob Journalingfilesystems 日志文件系统 Microsoft sNTFSsystemTheLinuxext3filesystem 39 Anexample OperationsrequiredtoremoveafileinUNIX Removethefilefromitsdirectory Releasethei nodetothepooloffreei nodes Returnallthediskblockstothepooloffreediskblocks WhattheJFSdoesisfirstwritealogentrylistingthethreeactionstobecompleted Thelogentryisthenwrittentodisk Onlyafterthelogentryhasbeenwritten dothevariousoperationsbegin Aftertheoperationscompletesuccessfully thelogiserased 40 4 3 6VirtualFileSystems VFS MostUNIXsystemshaveusedtheconceptofaVFS 虚拟文件系统 totrytointegratemultiplefilesystemsintoanorderlystructure Fig 4 18PositionoftheVFS 41 VFS ThekeyideaofVFSistoabstractoutthatpartofthefilesystemthatiscommontoallfilesystemsandputthatcodeinaseparatelayerthatcallstheunderlyingconcretefilesystemstoactualmanagethedata AllsystemcallsrelatingtofilesaredirectedtotheVFSforinitialprocessing Thesecalls comingfromuserprocesses arethestandardPOSIXcalls suchasopen read write andsoon ThustheVFShasan upper interfacetouserprocessesanditisthewell knownPOSIXinterface 42 VFS TheVFSalsohasa lower interfacetotheconcretefilesystems whichislabeledVFSinterfaceinFig 4 18 Thisinterfaceconsistsofseveraldozenfunctioncalls ThustocreateanewfilesystemthatworkswiththeVFS thedesignersofthenewfilesystemmustmakesurethatitsuppliesthefunctioncallstheVFSrequires 43 4 4FileSystemManagementandOptimization 4 4 1DiskSpaceManagement4 4 2FileSystemBackup4 4 3FileSystemConsistency4 4 4FileSystemPerformance4 4 5DefragmentingDisks 44 4 4 1DiskSpaceManagement Twopossiblestrategiesforstoringannbytesfile nconsecutive 连续的 bytesofdiskspaceareallocated Thefileissplitupintoanumberof notnecessarily contiguousblocks Problems Nearlyallfilesystemschop 砍 分割 filesupintofixed sizeblocksthatneednotbeadjacent 相邻的 45 1 BlockSize Howbigtheblockshouldbe Largeblocksize Everyfile evena1 bytefile tiesupanentireblock Smallfileswastealargeamountofdiskspace Smallblocksize Mostfileswillspan 跨越 multipleblocksandthusneedmultipleseeksandrotationaldelays 旋转延迟 toreadthem reducingperformance 46 BlockSize Historically filesystemshavechosensizeinthe1 KBto4 KBrange butwithdisksnowexceeding1TB itmightbebettertoincreasetheblocksizeto64KBandacceptthewasteddiskspace 47 2 Keepingtrackoffreeblocks Twomethods Usingalinkedlistofdiskblocks witheachblockholdingasmanyfreediskblocknumbersaswillfit Bitmap Adiskwithnblocksrequiresabitmapwithnbits 48 Figure4 22 a Storingthefreelistonalinkedlist b Abitmap Keepingtrackoffreeblocks 49 3 DiskQuotas 磁盘配额 Topreventpeoplefromhogging 贪婪攫取 toomuchdiskspace multi userOSoftenprovideamechanismforenforcingdiskquotas Theideaisthatthesystemadministratorassignseachuseramaximumallotmentoffilesandblocks andtheOSmakesurethattheusersdonotexceedtheirquotas 50 Figure4 24 Quotasarekepttrackofonaper userbasisinaquotatable DiskQuotas 51 Perquotatwolimits SoftandHardsoftlimit 用户可以使用超过softlimit的空间 这时系统会对用户发出警告 要求用户清理自己的文件以释放空间 若用户在限期内没有释放出空间 将不能再保存任何文件 hardlimit 是分配给每个用户的最大空间 如果用户超过这个限制就不能再保存文件 Graceperiod 限期 identifieshowlongthesoftlimitmaybeexceededAfterthatperiod ausergetserrorsinsteadofwarnings DiskQuotas 52 Exampleofquota 53 4 4 2FileSystemBackup Ifacomputer sfilesystemisirrevocably 不能取消的 无可挽回的 lost restoringalltheinformationwillbedifficult timeconsuming andinmanycases impossible FileSystemBackup 54 FileSystemBackup 1 Shouldtheentirefilesystembebackeduporonlypartofit Itisusuallydesirabletobackuponlyspecificdirectoriesandeverythinginthemratherthantheentirefilesystem 2 Itiswastefultobackupfilesthathavenotchangedsincethepreviousbackup whichleadstotheideaofincrementaldumps 增量转储 55 FileSystemBackup 3 Itmaybedesirabletocompressthedatabeforewritingthemtothetape 4 Itisdifficulttoperformabackuponanactivefilesystem Soalgorithmshavebeendevisedformakingrapidsnapshotsofthefilesystemstatebycopyingcriticaldatastructures andthenrequiringfuturechangestofilesanddirectoriestocopytheblocksinsteadofupdatingtheminplace 5 Backuptapesshouldbekeptoff site 56 FileSystemBackup Twostrategiescanbeusedfordumpingadisktotape Aphysicaldump 物理转储 Alogicaldump 逻辑转储 57 Physicaldump Aphysicaldumpstartsatblock0ofthedisk writeallthediskblocksontotheoutputtapeinorder andstopswhenithascopiedthelastone Advantages SimplicityGreatspeedDisadvantages TheinabilitytoskipselecteddirectoriesTheinabilitytomakeincrementaldumpsTheinabilitytorestoreindividualfilesuponrequest 58 Logicaldump Alogicaldumpstartsatoneormorespecifieddirectoriesandrecursively 递归地 dumpsallfilesanddirectoriesfoundtherethathavechangedsincesomegivenbasedate 基准日期 59 4 4 3FileSystemConsistency 文件系统的一致性 Manyfilesystemsreadblocks modifythem andwritethemoutlater Ifthesystemcrashesbeforeallthemodifiedblockshavebeenwrittenout thefilesystemcanbeleftinaninconsistentstate Todealwiththeproblemofinconsistentfilesystems mostcomputershaveautilityprogramthatchecksfilesystemconsistency UNIXhasfsckWindowshasscandisk 60 FileSystemConsistency Twokindsofconsistencychecks Blocks 块的一致性检查 Files 文件的一致性检查 1 CheckforblockconsistencyTheprogrambuildstwotables eachonecontainingacounterforeachblock initiallysetto0 Thecountersinthefirsttablekeeptrackofhowmanytimeseachblockispresentinafile Thecountersinthesecondtablerecordhowofteneachblockispresentinthefreelist 61 1 Checkforblockconsistency Figure4 27 Filesystemstates a Consistent b Missingblock c Duplicateblockinfreelist d Duplicatedatablock 62 2 Checkforfileconsistency Italsousesatableofcounters buttheseareperfile ratherthanperblock Itstartsattherootdirectoryandrecursivelydescendsthetree inspectingeachdirectoryinthefilesystem Foreveryi nodeineverydirectory itincrementsacounterforthatfile susagecount Wh