四川大學(xué)操作系統(tǒng)課件Chapter12

OperatingSystemsChapter12FileManagement2Agenda12.1Overview12.2FileOrganizationandAccess12.3FileDirectories12.4FileSharing12.5RecordBlocking12.6SecondaryStorageManagement12.7Summary3FileManagementFilemanagementsystemconsistsofsystemutilityprogramsthatrunasprivilegedapplications(特權(quán)程序)ProvidesameansofdataI/OInputtoapplicationsisbymeansofafileOutputissavedinafileforlong-termstorage4FileSystemProperties(文件系統(tǒng)的特性)Long-termexistence(長期存在)Sharablebetweenprocesses(進(jìn)程共享)Structure(結(jié)構(gòu)化存儲)Havespecificstructureaccordingtoapplication5FileOperations(文件操作)CreateDeleteOpenCloseReadWrite6TermsUsedwithFiles(文件術(shù)語)Field(域)Basicelementofdata(基本數(shù)據(jù)單元)ContainsasinglevalueCharacterizedbyitslengthanddatatypeRecord(記錄)Collectionofrelatedfields(相關(guān)域的集合)TreatedasaunitExample:employeerecord7TermsUsedwithFilesFile(文件)CollectionofsimilarrecordsTreatedasasingleentityHavefilenamesMayrestrictaccessDatabase(數(shù)據(jù)庫)CollectionofrelateddataRelationshipsexistamongelements8FileManagementSystems(文件管理系統(tǒng))Thewayauserofapplicationmayaccessfiles(用戶和程序使用文件的唯一方式)Programmerdoesnotneedtodevelopfilemanagementsoftware9FileManagementFunctionsIdentify(標(biāo)識)andlocate(定位)aselectedfileUsefilenametoidentifyfilesUseadirectory(目錄)todescribethelocationofallfilesplustheirattributes(屬性)Onasharedsystemdescribeuseraccesscontrol(存取控制)Blocking(塊化)foraccesstofilesManagefreeblocksAllocatefreeblockstofiles(空閑塊分配)Reclaimfreeblocks(空閑塊回收)10Agenda12.1Overview12.2FileOrganizationandAccess12.3FileDirectories12.4FileSharing12.5RecordBlocking12.6SecondaryStorageManagement12.7Summary1112.2FileOrganizationandAccess12.2.1CriteriaforFileOrganization12.2.2ThePile12.2.3TheSequentialFile12.2.4TheIndexedSequentialFile12.2.5TheIndexedFile12.2.6TheDirectorHashedFile12CriteriaforFileOrganization(文件管理的評價標(biāo)準(zhǔn))Shortaccesstime(短的存取時間)Easeofupdate(易于修改)Economyofstorage(存儲經(jīng)濟性)Simplemaintenance(維護簡單)Reliability(可靠性)1312.2FileOrganizationandAccess12.2.1CriteriaforFileOrganization12.2.2ThePile12.2.3TheSequentialFile12.2.4TheIndexedSequentialFile12.2.5TheIndexedFile12.2.6TheDirectorHashedFile14ThePile(堆文件)ThePileDataarecollectedintheordertheyarrivePurposeistoaccumulateamassofdataandsaveitRecordsmayhavedifferentfieldsNostructureRecordaccessisbyexhaustivesearch(窮舉搜索)15ThePile1612.2FileOrganizationandAccess12.2.1CriteriaforFileOrganization12.2.2ThePile12.2.3TheSequentialFile12.2.4TheIndexedSequentialFile12.2.5TheIndexedFile12.2.6TheDirectorHashedFile17TheSequentialFile(順序文件)Allfieldsthesame(orderandlength)FieldnamesandlengthsareattributesofthefileAllrecordsthesamelengthOnefieldisthekeyfiled(關(guān)鍵域，關(guān)鍵字)UniquelyidentifiestherecordRecordsarestoredinkeysequence18TheSequentialFileNewrecordsareplacedinalogfile(日志文件)ortransactionfile(事務(wù)文件)Batchupdate(成批更新)isperformedtomerge(合并)thelogfilewiththemasterfile19TheSequentialFile2012.2FileOrganizationandAccess12.2.1CriteriaforFileOrganization12.2.2ThePile12.2.3TheSequentialFile12.2.4TheIndexedSequentialFile12.2.5TheIndexedFile12.2.6TheDirectorHashedFile21TheIndexedSequentialFile(索引順序文件)Sequentialfile+index+overflowfileIndexprovidesalookupcapabilitytoquicklyreachthevicinityofthedesiredrecord(索引提供了快速接近目標(biāo)記錄的查詢能力)IndexcontainsakeyfieldandapointertothemainfileIndexedissearchedtofindhighestkeyvaluethatisequaltoorprecedesthedesiredkeyvalue(索引查找關(guān)鍵字小于或者等于目標(biāo)關(guān)鍵字的最大記錄)22TheIndexedSequentialFile(索引順序文件)ComparisonofsequentialandindexedsequentialExample:afilecontains1000000recordsOnaverage500000accessesarerequiredtofindarecordinasequentialfileIfanindexcontains1000entriesandeachentriescontains1000pointerstomainfile,itwilltakeonaverage500accessestofindthekey,followedby500accessesinthemainfile.Nowonaverageitis1000accesses23OverflowFileofTheIndexedSequentialFileNewrecordsareaddedtoanoverflowfile(溢出文件)RecordinmainfilethatprecedesitisupdatedtocontainapointertothenewrecordTheoverflowismerged(合并)withthemainfileduringabatchupdateMultiplelevelindexes(多級索引)forthesamekeyfieldcanbesetuptoincreaseefficiency24IndexedSequentialFile2512.2FileOrganizationandAccess12.2.1CriteriaforFileOrganization12.2.2ThePile12.2.3TheSequentialFile12.2.4TheIndexedSequentialFile12.2.5TheIndexedFile12.2.6TheDirectorHashedFile26TheIndexedFile(索引文件)UsesmultipleindexesfordifferentkeyfieldsMaycontainanexhaustiveindex(完全索引)thatcontainsoneentryforeveryrecordinthemainfileMaycontainapartialindex(部分索引)Indexfilesitselfaresequentialfile27

TheIndexedFile2812.2FileOrganizationandAccess12.2.1CriteriaforFileOrganization12.2.2ThePile12.2.3TheSequentialFile12.2.4TheIndexedSequentialFile12.2.5TheIndexedFile12.2.6TheDirectorHashedFile29TheDirectorHashedFile(直接文件或者散列文件)DirectlyaccessablockataknownaddressKeyfieldrequiredforeachrecordHashbasedonthekeyfield30Agenda12.1Overview12.2FileOrganizationandAccess12.3FileDirectories12.4FileSharing12.5RecordBlocking12.6SecondaryStorageManagement12.7Summary3112.3FileDirectories12.3.1Contents12.3.2Structure12.3.3Naming32FileDirectoriesContainsinformationaboutfilesAttributes(屬性)Location(位置)Ownership(所有者)Directoryitselfisafileownedbytheoperatingsystem(一個目錄本身是一個文件)Providesmappingbetweenfilenamesandthefilesthemselves(提供文件名和文件之間的映射)3312.3FileDirectories12.3.1Contents12.3.2Structure12.3.3Naming34SimpleStructureforaDirectory(簡單目錄結(jié)構(gòu))Representedbyasimplesequentialfilewiththenameofthefileservingasthekey(用順序文件代表目錄，該目錄下的文件名做該順序文件的關(guān)鍵字)Forcesusertobecarefulnottousethesamenamefortwodifferentfiles(文件不能重名)35Two-levelSchemeforaDirectory(兩級目錄方案)Amasterdirectory(主目錄)Onedirectoryforeachuser(用戶目錄)MasterdirectorycontainsentryforeachuserProvidesaddressandaccesscontrolinformationEachuserdirectoryisasimplelistoffilesforthatuserStillprovidesnohelpinstructuringcollectionsoffiles（不能建子目錄）36Hierarchical,orTree-StructuredDirectory(層次/樹狀結(jié)構(gòu)目錄)MasterdirectorywithuserdirectoriesunderneathitEachuserdirectorymayhavesubdirectoriesandfilesasentries373812.3FileDirectories12.3.1Contents12.3.2Structure12.3.3Naming39Hierarchical,orTree-StructuredDirectoryFilescanbelocated(文件定位)byfollowingapathfromtheroot,ormaster,directorydownvariousbranchesThisisthepathnameforthefileCanhaveseveralfileswiththesamefilename(文件同名)aslongastheyhaveuniquepathnames4041Hierarchical,orTree-StructuredDirectoryPathname(路徑名)Currentdirectoryistheworkingdirectory(工作目錄)Filesarereferencedrelativetotheworkingdirectory(相對路徑)42Agenda12.1Overview12.2FileOrganizationandAccess12.3FileDirectories12.4FileSharing12.5RecordBlocking12.6SecondaryStorageManagement12.7Summary43FileSharingInmultiusersystem,allowfilestobesharedamongusersTwoissuesAccessrights(存取權(quán)限)Managementofsimultaneousaccess(同時存取控制)44AccessRightsNone(無)UsermaynotknowoftheexistenceofthefileUserisnotallowedtoreadtheuserdirectorythatincludesthefileKnowledge(知道)Usercanonlydeterminethatthefileexistsandwhoitsowneris45AccessRightsExecution(執(zhí)行)TheusercanloadandexecuteaprogrambutcannotcopyitReading(讀)Theusercanreadthefileforanypurpose,includingcopyingandexecutionAppending(追加)Theusercanadddatatothefilebutcannotmodifyordeleteanyofthefile’scontents46AccessRightsUpdating(更新)Theusercanmodify,deleted,andaddtothefile’sdata.Thisincludescreatingthefile,rewritingit,andremovingallorpartofthedataChangingprotection(更改保護)UsercanchangeaccessrightsgrantedtootherusersDeletion(刪除)Usercandeletethefile47AccessRightsOwners（所有者）HasallrightspreviouslylistedMaygrantrightstoothersusingthefollowingclassesofusersSpecificuser(指定用戶)Usergroups(用戶組)Allforpublicfiles(所有用戶)48SimultaneousAccess(同時訪問)UsermaylockentirefilewhenitistobeupdatedUsermaylocktheindividualrecordsduringtheupdateMutualexclusionanddeadlockareissuesforsharedaccess49Agenda12.1Overview12.2FileOrganizationandAccess12.3FileDirectories12.4FileSharing12.5RecordBlocking12.6SecondaryStorageManagement12.7Summary50FixedBlocking51Variable-LengthSpannedBlocking52Variable-LengthUnspannedBlocking53Agenda12.1Overview12.2FileOrganizationandAccess12.3FileDirectories12.4FileSharing12.5RecordBlocking12.6SecondaryStorageManagement12.7Summary5412.6SecondaryStorageManagement(二級存儲管理)12.6.1FileAllocation12.6.2FreeSpaceManagement12.6.3Reliability55FileAllocationTable(FAT)FATisusedtotrackportionsallocatedtofiles56Preallocation(預(yù)分配)VSDynamicallocation(動態(tài)分配)PreallocationNeedthemaximumsizeforthefileatthetimeofcreationDifficulttoreliablyestimatethemaximumpotentialsizeofthefileDynamicallocationAllocatesspacetoafileinportionsasneeded.57Contiguousallocation(連續(xù)分配)Singlesetofblocksisallocatedtoafileatthetimeofcreation(文件創(chuàng)建時分配一組連續(xù)的塊)OnlyasingleentryinthefileallocationtableStartingblockandlengthofthefileExternalfragmentationwilloccurNeedtoperformcompaction58Contiguousallocation59Contiguousallocation60Chainedallocation(鏈?zhǔn)椒峙?Allocationonbasisofindividualblock(基于單個塊進(jìn)行分配)EachblockcontainsapointertothenextblockinthechainOnlysingleentryinthefileallocationtableStartingblockandlengthoffileNoexternalfragmentationBestforsequentialfiles(適合順序文件)Noaccommodationoftheprincipleoflocality(局部性原理不再適用)，soconsolidation(遷移、集結(jié))isneedtomoveblocksadjacenteachother61Chainedallocation62Chainedall