Ch4-Internal-Representation-of-Files高级操作系统(UNIX)课件

AdvancedOperatingSystem

--TheDesignoftheUNIXOperationSystemCh1GeneralOverviewoftheSystemCh2IntroductiontotheKernelCh3TheBufferCacheCh4InternalRepresentationofFilesCh5SystemcallsfortheFilesystemCh6TheStructureofProcessesCh7ProcessControlCh8ProcessSchedulingandTimeCh9MemoryManagementPolicies整体概述THEFIRSTPARTOFTHEOVERALLOVERVIEW,PLEASESUMMARIZETHECONTENT第一部分AdvancedOperatingSystem

--TheDesignoftheUNIXOperationSystemCh4InternalRepresentationofFilesTopicscovered4.1Inodes4.2StructureofaRegularFile4.3Directories4.4ConversionofaPathNametoanInode4.5SuperBlock4.6InodeAssignmenttoaNewFile4.7AllocationofDiskBlocksEveryfileonUNIXhasauniqueinodeTheinodecontainstheinformationnecessaryforaprocesstoaccessafileProcessesaccessfilesbysystemcallandspecifiesafilebyapathnameThekernelconvertsthepathnametothefile’sinode4.1InodesInodesexistinastaticformondiskThekernelreadsinodeintoanin-coreinodetomanipulatethem4.1Inodes-DefinitionDiskinodesconsistofthefollowingfields:FileowneridentifierownergroupsuperuserFiletypeRegular,directory,characterorblockspecial,orFIFO(pipes)Fileaccesspermissionsowner,groupowner,otherusers;read,write,executeFileaccesstimesLastmodified,lastaccessed,whentheinodewaslastmodifiedNumberoflinkstothefileThenumberofnamesthefilehasTableofcontentsforthediskaddresstodatainafileDiskblocksthatcontainthefile’sdataFilesizeStartfrombyteoffset04.1Inodes-Definition4.1Inodes-DefinitionWritethecontentsofafiletodiskThecontentsofafilechangeonlywhenwritingitWritethecontentsofaninodetodiskChangthecontentsofafileChangeitsowner,permission,orlinksettings…4.1Inodes-DefinitionThein-corecopyoftheinodecontainsthefollowingfieldsinadditiontothefieldsofthediskinode:Thestatusofthein-coreinodeThelogicaldevicenumberofFSthatcontainsthefileTheinodenumberPointerstootherin-coreinodesAreferencecount—indicatingthenumberofinstancesofthefilethatareactive(suchaswhenopen)4.1Inodes-DefinitionThestatusofthein-coreinode,indicatewhether:TheinodeislockedAprocessiswaitingfortheinodetobecomeunlockedThein-corerepresentationoftheinodediffersfromdiskcopyasaresultofachangetothedataintheinodeThein-corerepresentationofthefilediffersfromdiskcopyasaresultofachangetothefiledataThefileisamountpoint4.1Inodes-DefinitionManyfieldsinthein-coreinodeareanalogoustofieldsinthebufferheaderThedifference:in-corehaveareferencecountCountsthenumberofactiveinstancesofthefileAninodeisonthefreelistonlyitsreferencecountis0Thekernelcanreallocatethein-coreinodetoanotherdiskinodeIfaprocessattemptstoaccessafilewhoseinodeisnotcurrentlyinthein-coreinodepool,thekernelreallocateanin-coreinodefromthefreelistforitsuse.4.1Inodes-Accessigetallocateanin-corecopyofaninodeThekernelmapsthedevicenumberandinodenumberintoahashqueueSearchthequeuefortheinodeIfcannotfind,allocatesonefromthefreelistandlocksitThenreadthediskcopyintothein-corecopy4.1Inodes-AccessBlocknum=((inodenum-1)/numberofinodesperblock)+startblockofinodelistStartblockofinodelist:2Numberofinodesperblock:8Block0Block1inode1inode2inode8inode9inode16……Block2Block34.1Inodes-AccessByteoffsetoftheinodeintheblock:((inodenumber-1)mod(numberofinodesperblcok)*sizeofdiskinodeEachdiskinode:64bytesNumberofinodesperblock:8inode1inode2inode8…Block063641274485114.1Inodes-AccessThekernellocktheinodeduringexecutionofasystemcallThekernelreleasethelockattheconclusionofthesystemcallThekernelincrementsthereferencecountforeveryactivereferencetoafile(openthefile)Decrementthereferencecountwhenthereferencebecomeinactive(closethefile)ThelockisfreebetweensystemcallstoallowprocessestosharesimultaneousaccesstoafileThereferencecountremainsetbetweensystemcall4.1Inodes-igetigetAtthebeginningofsystemcallWhenaprocessfirstaccessafileReturnalockedinodewithreferencecount1greaterthanbeforeThekernelunlockstheinodebeforereturningfromthesystemcall4.1Inodes-igetiget4.1Inodes-iputiputReleasinginodesDecrementsitsin-corereferencecountIfthecount0,andthein-corecopydifferfromthediskcopy,thekernelwritetheinodetodiskPlacetheinodeonthefreelistofinodesReleasealldatablockassociatedwiththefile4.1Inodes-iputiput4.2StructureofaRegularFileEachblockonadiskisaddressablebynumberTheinodecontainthetableofcontentstolocateafile’sdataondisk4.2StructureofaRegularFileStoreinacontiguoussectionofdisk4.2StructureofaRegularFileThekernelallocatefilespaceoneblockatatimeandallowsthedatainafiletobespreadthroughoutthefilesystemThetablecouldconsistofalistofblocknumbersAlogicalblock=1k10kfileanindexof10blocknumbers100kfileanindexof100blocknumber4.2StructureofaRegularFileTheSystemVUNIX:13entriesintheinodetableofcontents10directblock1indirect1doubleindirect1tripleindirect4.2StructureofaRegularFile4.2StructureofaRegularFileAssume:Alogicalblock=1KbytesAblocknumber=32bit(4byte)integerAblockholdupto:256blocknumbers10directblock =10K1indirect =256*1K=256k1doubleindirect =256*256*1K=64M1tripleindirect =256*256*256*1K=16G4.2StructureofaRegularFileProcessesaccessdatainafilebybyteoffsetThekernelaccessfilebyblockThekernelaccesstheinodeandconvertsthelogicalfileblockintotheappropriatediskblockAlgorithmbmap4.2StructureofaRegularFile4.2StructureofaRegularFile4.2StructureofaRegularFileAdiskblock=1024bytesIfaprocesswantstoaccessbyteoffset9000:9000/1024=8…808Theblocknumber=367Theoffsetoftheblock=808Ifaprocesswantstoaccessbyteoffset35000:35000/1024=341…816341-(10+256)=753333:8164.2StructureofaRegularFileBlockentriesintheinodeare0:ThelogicalblockentriescontainnodataNoprocesseverwrotedataintothefileatanybyteoffsetscorrespondingtothoseblocksandhencetheblocknumbersremainattheirinitialvalue04.2StructureofaRegularFileTwoextensiontotheinodestructure:LargerlogicaldiskblockMoredatathekernelcanaccessonthediskinasingleoperation,thefasterfileaccessbecomeStorefiledataintheinodeExpandingtheinodetooccupyanentirediskblock4.3DirectoriesAdirectoryisafileItsdataisasequenceofentries:aninodenumber(2bytes)thenameofafilecontainedinthedirectory(14bytes)Everydirectorycontainsthefilenamesdotanddot-dot(“.”and“..”)Theinodenumbersarethoseofthedirectoryanditsparentdirectory4.3Directories4.3DirectoriesThekernelstoresdataforadirectoryjustasitstoresdataforanordinaryfileProcessesmayreaddirectoriesinthesamewaytheyreadregularfileThekernelreservesexclusiverighttowriteadirectoryTheaccesspermissionsofadirectory:Read:allowsaprocesstoreadadirectoryWrite:allowsaprocesstocreatenewdirectoryentries/removeoldone(creat,mknod,link,unlink)Execute:searchthedirectoryforafilename4.4ConversionofaPathNametoanInodeTheprocessaccesstoafilebyitspathnameThekernelworksinternallywithinoderatherthanwithpathnamesThekernelconvertsthepathnametoinode4.4ConversionofaPathNametoanInodeEveryprocessisassociatedwithacurrentdirectoryTheuareacontainsapointertothecurrentdirectoryinodeThecurrentdirectoryofthefirstprocess(process0),istherootdirectoryThecurrentdirectoryofeveryotherstartsoutasthecurrentdirectoryofitsparentprocessatthetimeitwascreated4.4ConversionofaPathNametoanInodenameiWorkinginode:nameiuseintermediateinodesasitparsesapathnameTheinodewherethesearchstartsisthefirstworkinginode.MakesuretheworkinginodeisadirectoryTheprocessmusthavepermissiontosearchthedirTheuserIDoftheprocessmustmatchtheownerorgroupIDofthefile4.4ConversionofaPathNametoanInodeThekerneldoesalinersearchofthedirectoryTrytomatchthepathnamecomponenttoadirectoryentryname.Iffindamatch,itrecordstheinodenumberofthematcheddirectoryentry,Allocatetheinodeofthematchedcomponent(iget).ThenewinodebecomestheworkinginodeThekernelrepeattheprocedureuntilitmatchesthepathname,oruntilitreachestheendofthedirectory4.4ConversionofaPathNametoanInode4.5SuperBlockSuperblockThesizeofthefilesystemThenumberoffreeblocksinthefilesystemAlistoffreeblocksavailableonthefilesystemTheindexofthenextfreeblockinthefreeblocklistThesizeofinodelistThenumberoffreeinodesinthefilesystemAlistoffreeinodesinthefilesystemTheindexofthenextfreeinodeinthefreelnodelistLockfieldsforthefreeblockandfreeinodelistsAflagindicatingthatthesuperblockhasbeenmodified4.6InodeAssignmenttoaNewFileigetAknowninode(inodenumberwaspreviouslydetermined)iallocAssignadiskinodetoanewlycreatedfile4.6InodeAssignmenttoaNewFileThefilesystemcontainsalinearlistofinodesAninodeisfreeifitstypefieldiszeroWhenaprocessneedsanewinode,thekernelsearchtheinodelistforafreeinodeFilesystemsuperblockcontainsanarraytocachethenumbersoffreeinodes.4.6InodeAssignmenttoaNewFileiallocIfthelistoffreeinodesisnotemptyAssignafreeinodenumberAllocateafreein-coreinodeforthisinode(iget)Copythediskinodetothein-corecopyInitializethefieldsintheinodeReturnthelockedinodeDecrem