《现代操作系统课件：Chapter4-FileSysManagement》由会员分享，可在线阅读，更多相关《现代操作系统课件：Chapter4-FileSysManagement（70页珍藏版）》请在金锄头文库上搜索。
1、ModernOperatingSystemsChapter4FileSystemZhangYangSpring2013ContentoftheLecturen4.4FileSystemManagementandOptimizationn4.5ExampleFileSystemsFileSystemManagementandOptimizationnDiskSpaceManagementnFileSystemBackupsnFileSystemConsistencynFileSystemPerformanceDiskSpaceManagementnBlockSizenKeepingTrackof
2、FreeBlocksnDiskQuotasBlockSize(1)nMustchooseadiskblocksize.=PageSize?=SectorSize?=Tracksize?nLargeblocksizesInternalfragmentationLastblockhas(onaverage)1/2wastedspaceLotsofverysmallfiles;wasteisgreater.nSmallblocksizesMoreseeks;fileaccesswillbeslower.BlockSize(2)Figure4-20.Percentageoffilessmallerth
3、anagivensize(inbytes).Figure4-21.Thesolidcurve(left-handscale)givesthedatarateofadisk.Thedashedcurve(right-handscale)givesthediskspaceefficiency.Allfilesare4KB.BlockSize(3)nPerformanceandspaceutilizationareinherentlyinconflict.Higherblocksize:higherdatarate,lowerspaceutilizationLowerblocksize:lowerd
4、atarate,higherspaceutilizationdataratediskspaceutilizationBlockSize(4)nTypicalBlockSizesUnixnTypically1Kbytesn2sectors=1blockMS-DOSnVariable,N*512(“clustersize”)nDeterminedbyotherissuesnLimitednumberofbitsforblockaddressesnToaccommodatelargerdisksizes-usebiggerblocksFAT-12:512,1K,2K,4KFAT-16:2K,4K,8
5、K,16K,32KFAT-32:4K,8K,16K,32KKeepingTrackofFreeBlocks(1)nLinkedListEachblockholdsasmanyfreediskblocknumbersaswillfit.Example:16GBdiskhas2241-KBblockandrequires224/255=65793blocks.(32-bitblocknumber)nBitMapAdiskwithnblocksrequiresabitmapwithnbitsFreeblocksarerepresentedby1sAllocatedblocksrepresentedb
6、y0sExample:16GBdiskhas2241-KBblockandrequires224bits2048blocksKeepingTrackofFreeBlocks(2)(a)Storingthefreelistonalinkedlist(b)AbitmapKeepingTrackofFreeBlocks(3)nLinkedListProblemOnlyoneblockofpointersneedbekeptinmainmemory.Undercertaincircumstance,thismethodleadstounnecessarydiskI/O.nWhentheblockofp
7、ointersisalmostempty,aseriesofshort-livedtemporaryfilescancausealotofdiskI/O.SolutionnKeepmostofthepointerblocksondiskfull(tominimizediskusage),butkeeptheoneinmemoryabouthalffull.KeepingTrackofFreeBlocks(4)(a)Almost-fullblockofpointerstofreediskblocksinRAM-threeblocksofpointersondisk(b)Resultoffreei
8、nga3-blockfile(c)Alternativestrategyforhandling3freeblocks-shadedentriesarepointerstofreediskblocksDiskQuotas(1)nPreventspeoplefromgettingtoomuchdiskspace.nUseasecondtableintheopenfiletablestructure.Foreachuser.OSwillmaintainarecord.ExamplenAmountofdiskspaceused(inblocks)CurrentMaximumallowablenNumb
9、eroffilesCurrentMaximumallowableSoftLimitsnWhenexceeded,printawarningHardLimitsnMaynotbeexceededDiskQuotas(2)Figure4-24QuotasforkeepingtrackofeachusersdiskuseSettingDiskQuotasFileSystemReliabilitynFileSystemBackUpDatainafilesystemshouldbepermanentImplementedthroughbackupandreplicationnFileSystemCons
10、istencyDatainafilesystemshouldbegoodImplementedthroughlogging,transactions,andshadowingFileSystemBackups(1)nBackupConsiderationsEntirefilesystemorjustpartofitIncrementalDumporCompleteDumpnE.g.Onceamonth,backuptheentirefilesystem.Onceaday,makeacopyofallfilesthathavechangedCompressornotSnapshotNontech
11、nicalproblemnTwoStrategiesforDumpingaDisktoTapePhysicalDumpLogicalDumpFileSystemBackups(2)nPhysicalDumpApproachnStartatblock0onthedisknCopyeachblock,inorderConcernsnBlocksonthefreelist?ShouldavoidcopyingthemnBadsectorsondisk?ControllerremapsbadsectorsBackuputilityneednotdoanythingspecial!OShandlesba
12、dsectorsBackuputilitymustavoidcopyingthem!FileSystemBackups(3)nPhysicalDump(ctd.)AdvantagesnSimplenGreatspeed(runatthespeedofdisk)DisadvantagesnInabilitytoskipselecteddirectoriesnInabilitytomakeincrementaldumpnInabilitytorestoreindividualfilesuponrequestFileSystemBackups(4)nLogicalDumpStartatoneormo
13、respecifieddirectoriesandrecursivelydumpsallfilesanddirectoriesfoundtherethathavechangedsincesomegivenbasedate.MostcommonformnIncrementaldumpingoffilesanddirectoriesWillcopyonlyfilesthathavebeenmodifiedsincelastincrementalbackup.Mustalsocopythedirectoriescontaininganymodifiedfiles.FileSystemBackups(
14、5)nLogicalDumpAlgorithmPhase1:beginatthestartingdirectoryandexaminesalltheentriesinit.Markedeachmodifiedfileandeachdirectory(whetherornotmodified).Phase2:recursivelywalksthedirectorytree,unmarkinganydirectoriesthathavenomodifiedfilesordirectoriesinthemorunderthem.Phase3:dumpallthemarkeddirectoriesPh
15、ase4:dumpallthemarkedfilesFileSystemBackups(6)Figure4-25Afilesystemtobedumpedsquaresaredirectories,circlesarefilesshadeditems,modifiedsincelastdumpeachdirectory&filelabeledbyi-nodenumberFile that hasnot changedFileSystemBackups(7)Figure4-26BitmapsusedbythelogicaldumpingalgorithmFileSystemConsistency
16、(1)nMulti-stepupdatescauseproblemsforconsistencyIfcrashhappensinthemiddlenE.g.transfer$100frommyaccounttoJanets(1)deduct$100frommyaccount(2)add$100toJanetsaccountnWhathappensifyoucrashbetweenstep1and2?FileSystemConsistency(2)nMostsystemshaveautilityprogramthatchecksfilesystemconsistencyWindows:scand
17、iskUNIX:fscknfsck:checkingblocksReadsallthei-nodesandmarkusedblocks.Examinesthefreelistandmarkfreeblocks.EachdiskblockmustbenInafile(ordirectory),ornOnthefreelistFileSystemConsistency(3)nBlockInconsistentStatesSomeblockisnotinafileoronfreelist(“missingblock”)nAddittothefreelist.Someblockisonthefreel
18、istmorethanoncenCanthappenwhenusingabitmapforfreeblocks.nFixthefreelistsotheblockappearsonlyonce.SomeblockisinmorethanonefilenAllocateanotherblock.nCopytheblock.nPuteachblockineachfile.nNotifytheuserthatonefilemaycontaindatafromanotherfile.SomeblockisonfreelistandisinsomefilenRemoveitfromthefreelist
19、.FileSystemConsistency(4)Figure4-27FileSystemStates(a)consistent(b)missingblock(c)duplicateblockinfreelist(d)duplicatedatablockFileSystemConsistency(5)nExerciseProblem:ConsiderFig.4-27.Isitpossiblethatforsomeparticularblocknumberthecountersinbothlistshavethevalue2?Solution:nItshouldnothappen,butduet
20、oabugsomewhereitcouldhappen.Itmeansthatsomeblockoccursintwofilesandalsotwiceinthefreelist.nThefirststepinrepairingtheerroristoremovebothcopiesfromthefreelist.Nextafreeblockhastobeacquiredandthecontentsofthesickblockcopiedthere.Finally,theoccurrenceoftheblockinoneofthefilesshouldbechangedtorefertothe
21、newlyacquiredcopyoftheblock.Atthispointthesystemisonceagainconsistent.FileSystemConsistency(6)nfsck:checkingdirectoriesRecursivelydescendsthetreefromtherootdirectory,forfilecountingthenumberoflinkseachfile.Comparethesenumberswiththelinkcountsstoredinthei-nodesinodes.Thereferencecountineachi-nodemust
22、beequaltothenumberofhardlinkstothefile.ABCXYFGCD1:D2:D3:FileSystemConsistency(6)nDirectoryInconsistentStateReferencecountistoolargenThe“rm”commandwilldeleteahardlink.nWhenthecountbecomeszero,theblocksarefreed.nPermanentlyallocated;blockscanneverbereused.ReferencecountistoosmallnWhenlinksareremoved,t
23、hecountwillgotozerotoosoon!nTheblockswillbeaddedtothefreelist,eventhoughthefileisstillinsomedirectory!SolutionnForcethelinkcountinthei-nodetotheactualnumberofdirectoryentries.FileSystemPerformance(1)nCachingAvoiddiskI/OoverheadnBlockReadAheadImprovebuffercachehitratenReducingDiskArmMotionAvoidseekov
24、erheadCaching(1)nObservationsOnceablockhasbeenreadintomemoryitcanbeusedtoservicesubsequentread/writerequestswithoutgoingtodiskMultiplefileoperationsfromoneprocessmayhitthesamefileblockFileoperationsofmultipleprocessesmayhitthesamefileblocknIdeaMaintainablockcacheorbuffercacheinmemoryAcacheisacollect
25、ionofblocksthatlogicallybelongonthediskbutarebeingkeptinmemoryforperformancereasons.WhenaprocesstriestoreadablockcheckthecachefirstCaching(2)nIdea(ctd.)Ifitis,thereadrequestcanbesatisfiedwithoutadiskaccess.Iftheblockisnotinthecache,itisfirstreadintothecache,andthencopiedtowhereveritisneeded.nCacheOr
26、ganizationManyblocks(e.g.,1000s)IndexedonblocknumberForefficiency,useahashtabledevice block#keyCaching(3)1.Collisionchain2.Bidirectionallist:runningthroughalltheblocksintheorderofrecentlyusedusage,withtheleastrecentlyusedblockonthefrontofthislistandthemostrecentlyusedblockattheendofthelist.Theblockc
27、achedatastructuresCaching(4)nLRUisareasonableblock replacement policynBUT:ifacriticalblock(suchasFileControlBlock,ori-node)isreadintothecacheandmodified,butnotre-writtentothedisk,acrashwillleavethefilesysteminaninconsistentstate.nCriticalblocksmustbewrittenimmediately.Caching(5)nNeedtowriteablock?Mo
28、difytheversionintheblockcache.nWhatifsystemcrashes?Canthefilesystembecomeinconsistent?Writedirectoryandi-nodeinfoimmediatelyOkaytodelaywritestofilesnBackgroundprocesstowritedirtyblocksnButwhenshouldwewriteitbacktodisk?ImmediatelynMS-DOS“Write-through cache”30secondsLaternTheUnix“synch”syscallBlockRe
29、adAhead(1)nThismethodmeansTrytogetblocksintothecachebeforetheyareneededIncreasehitratebyprefetchinganticipatedblocksnApproachUserrequestskblockFSgetskblockFSchecksofk+1blockisincache,ifnot,FSwillgetk+1blockfromdiskanticipatingthatitwillbeneededinthefuturenAdvantageIfuserneedsk+1block,theaccessisfast
30、greatmethodforvideoplaybacknDisadvantageIfuserdoesnotneedk+1block,extraunnecessaryworkhasbeendoneBlockReadAhead(2)nThistechniquehelpsonlyifaccessissequential.nWhatifthefileisnot beingreadsequentially?FSkeepstrackofaccesspatternstoopenfilesnSequentialaccessmodenRandomaccessmodeFSmayuseabitassociatedw
31、itheachfiletokeeptrackofaccesspattern(1forsequentialaccess,0forrandomaccess)ReducingDiskArmMotion(1)nSeektimedominatesdiskaccesstimeReducingdiskarmmotionimprovedperformanceReducingdiskarmmotionbyputtingblocksthatarelikelytobeaccessedinsequenceclosetoeachother,preferablyinthesamecylinder.nIfthesystem
32、usesabitmapforthefreelist,itcanallocateanewblockforafileclosetothepreviousblock(guessingthatthefilewillbeaccessedsequentially).nThesystemcanperformallocationsinsuper-blocks,consistingofseveralcontiguousblocks.TheblockcacheandI/Orequestsarestillinblocksnotsuper-blocks.Ifthefileisaccessedsequentially,
33、consecutiveblocksofasuper-blockwillbeaccessedinsequenceandthesearecontiguousonthedisk.ReducingDiskArmMotion(2)nInsystemsusingi-nodesoranythingequivalenttoi-nodesNormallyalli-nodesgotogether,andalldatagotogetherIdeaistoputi-nodeclosertoactualfiledatanImprovementPutthei-nodesinthemiddleofthedisk,thusr
34、educingtheaverageseekbetweenthei-nodeandthefirstblockbyafactoroftwo.Breakdiskintoregions-“CylinderGroups”.Putblocksthatare“closetogether”inthesamecylindergroupnTrytoallocatei-nodeandblocksinthefilewithinthesamecylindergroupReducingDiskArmMotion(3)Figure4-29(a)i-nodesplacedatthestartofthedisk(b)Diskd
35、ividedintocylindergroups,eachwithitsownblocksandi-nodesExampleFileSystemsnTheMS-DOSFileSystemnWindows98FileSystemnWindowsNTFileSystemnUNIXV7FileSystemFigure11-1.MajorreleasesinthehistoryofMicrosoftoperatingsystemsfordesktopPCs.HistoryofVista(1)Figure11-4.SplitclientandserverreleasesofWindows.History
36、ofVista(2)TheMS-DOSFileSystem(1)nUse8+3filenamesnDOS1.0limitedtoonedirectorynLaterversionsallowshierarchicalfilesystemDirectorycannestedtoanarbitrarydepthnDirectoriesarevariablesizednButdirectoryentriesarefixedsizeof32bytesTheMS-DOSFileSystem(2)Figure4-31TheMS-DOSdirectoryentryTime:hours(5bits),minu
37、tes(6bits),seconds(5bits)Date:year(7bits),month(4bits),day(5bits)Size:intheorycanbe4GB,butinfact2GBorless.TheMS-DOSFileSystem(3)nThehighestexpressibleyearinMS-DOSis2107Thecounterstartsat1980nUsefileallocationtabletokeeptrackoffileaddressesnEachdirectoryentryonlygivesthefirstblocknumberWhichisusedtoi
38、ndexintotheFATtableTheMS-DOSFileSystem(4)nFATfilesystemhasthreeversionsforMS-DOS:FAT-12,FAT-16,FAT-32EachdiffersfromthebitsadiskaddresscontainsFAT-32introducedwith2ndreleaseofWindows95nDiskblocknumbersaremultiplesof512bytesCanbedifferentforeachpartitionnAllowableblocksizedifferingbyvariantsTheMS-DOS
39、FileSystem(5)nMaximumpartitionfordifferentblocksizesnTheemptyboxesrepresentforbiddencombinationsTheMS-DOSFileSystem(6)nAdvantagesofFAT-32overFAT-16SupportlargerdisksAn8-GBdiskusingFAT-32canbeasinglepartition.UsingFAT-16hastobefourpartitions.Foragivensizediskpartition,asmallerblocksizecanbeused.TheMS
40、-DOSFileSystem(7)nExerciseProblem:TheMS-DOSFAT-16tablecontains64Kentries.Supposethatoneofthebitshadbeenneededforsomeotherpurposeandthatthetablecontainedexactly32768entriesinstead.Withnootherchanges,whatwouldthelargestMS-DOSfilehavebeenunderthiscondition?Solution:Thelargestblockis32,768.With32,768oft
41、heseblocks,thebiggestfilewouldbe1GB.TheWindows98FileSystem(1)nToaccommodatelongfilenamesUpto255charactersnToprovidebackwardscompatibilitytoMS-DOSfilesMustusetheMS-DOSdirectorystructurenIdea:keeptwonamesforeachfileCreateaMS-DOSnamefromthegiven(long)nameBothnamearethenstoredinthedirectorystructureTheW
42、indows98FileSystem(2)TheextendedMOS-DOSdirectoryentryusedinWindows98NT:compatibilitywithWindowsNTSec:solvetheproblemthatitisnotpossibletostorethetimeofdayina16-bitfield.(Creationtimeisaccurateto10msec)LastaccessUpper16bitsofstartingblockBytesTheWindows98FileSystem(3)Anentryfor(partof)alongfilenamein
43、Windows98sequence:6bit.Themaximumfilename=63*13=819.Butinfactlimitedto260charsforhistoricalreasons.BytesChecksumTheWindows98FileSystem(4)AnexampleofhowalongnameisstoredinWindows98TheWindowsNTFileSystem(1)nNTFSFundamentalConceptsNTFSprovidesafull64-bitfilesystem,theoreticallycapableofscalingtolargesi
44、zes.However,otherlimitationsresultinapracticallimitof2TBforasinglefilesystem.FilenamescanconsistofanyUNICODE(multi-national)characters,whileFATonlyconsistsofASCII(English/American).Fullysupportscase-sensitivefilenames.TheWindowsNTFileSystem(2)nNTFSFundamentalConcepts(ctd.)AnNTFSfileisnotjustalinears
45、equenceofbytes.Itconsistsofmultipleattributes,eachofwhichisrepresentedbyastreamofbytes.NTFSisahierarchicalfilesystem.nNTFSFileSystemStructureEachNTFSvolume(e.g.,diskpartition)containsfiles,directories,bitmaps,andotherdatastructure.Eachvolumeisorganizedasalinearsequenceofblocks.(typicallyblocksizeis4
46、KB)ThemaindatastructureineachvolumeistheMFT(MasterFileTable),whichisalinearsequenceoffixed-size1KBrecords.TheWindowsNTFileSystem(3)nNTFSFileSystemStructure(ctd.)EachMFTrecorddescribesonefileoronedirectory.Ifafileisextremelylarge,itissometimesnecessarytousetwoormoreMFTrecords.EachMFTrecordconsistsofa
47、sequenceof(attributeheader,value)pairs.NTFSdefines13attributesthatcanappearinMFTrecords.Figure11-41.TheNTFSmasterfiletable.TheWindowsNTFileSystem(4)Figure11-42.TheattributesusedinMFTrecords.TheWindowsNTFileSystem(5)TheUNIXV7FileSystem(1)nIntroducedinPDP-11nOrganizedintheformofatreestartingfromrootnF
48、ilenamesareupto14charactersandcancontainanyASCIIcharactersexcept/andNUL.nEachdirectoryentryhastwofields:Filename,andthe#ofi-nodeforthatfile(2bytes)nNumberoffilesinthefilesystemlimitedto64KTheUNIXV7FileSystem(2)Figure4-33AUNIXV7directoryentryTheUNIXV7FileSystem(3)Figure4-13AnExamplei-nodenFileAttribu
49、tes:FilesizeCreation,lastaccess,lastmodificationtimeOwnerGroupProtectionCountTheUNIXV7FileSystem(4)Figure4-34AUNIXi-nodeTheUNIXV7FileSystem(5)nThestepsinlookingup/usr/ast/mbox:Thefilesystemlocatestherootdirectory.Itcanbeanywhereonthedisk,butitsi-nodeislocatedatafixedplace.Thefilesystemlooksupthefirs
50、tcomponentofthepath(usr)andfinditsi-nodenumber.Fromthisi-node,thesystemlocatesthedirectoryfor/usrandlooksupthenextcomponent(ast)init.Whentheentryforastisfoundindirectory/usr,i-nodeforthedirectory/usr/astcanbeobtained.Fromthisi-nodeitcanfindthedirectoryitselfandlookupmbox.Thei-nodeforthisfileisthenre
51、adintomemoryandkeptthereuntilthefileisclosed.TheUNIXV7FileSystem(6)Figure4-35Thestepsinlookingup/usr/ast/mboxTheUNIXV7FileSystem(7)nExerciseProblem1:AUnixfilesystemhas1KBblocksand4bytediskaddress.Whatisthemaximumfilesizeifi-nodescontain10directentries,andonesingle,doubleandtripleindirectentryeach?So
52、lution:Thei-nodeholds10pointers.Thesingleindirectblockholds256pointers.Thedoubleindirectblockisgoodfor2562pointers.Thetripleindirectblockisgoodfor2563pointers.Addingtheseup,wegetamaximumfilesizeof16,843,018blocks,whichisabout16.06GB.TheUNIXV7FileSystem(8)nExerciseProblem2:Howmanydiskoperationsarenee
53、dedtofetchthei-nodeforthefile/usr/ast/course/os/handout.t?Assumethatthei-nodefortherootdirectoryisinmemory,butnothingelsealongthepathisinmemory.Alsoassumethatalldirectoriesfitinonediskblock.TheUNIXV7FileSystem(9)nExerciseSolution:Thefollowingdiskreadsareneeded:ndirectoryfor/ni-nodefor/usrndirectoryfor/usrni-nodefor/usr/astndirectoryfor/usr/astni-nodefor/usr/ast/coursesndirectoryfor/usr/ast/coursesni-nodefor/usr/ast/courses/osndirectoryfor/usr/ast/courses/osni-nodefor/usr/ast/courses/os/handout.tIntotal,10diskreadsarerequired.HomeworknP32520,32,34
