第六章文件管理操作系統Page12023/2/3第六章文件管理文件和文件系統文件的邏輯結構外存分配方式目錄管理文件存儲空間的管理文件共享與文件保護數據一致性控制Page22023/2/36.3外存分配方式

對于任何一個文件，都存在著以下兩種形式的結構：

(1)文件的邏輯結構(FileLogicalStructure)。

(2)文件的物理結構，又稱為文件的存儲結構，是指文件在外存上的存儲組織形式。Page32023/2/3外存分配方式如何才能有效地利用外存空間?如何提高對文件的訪問速度?Page42023/2/3文件的物理結構外存的特點容量大，斷電后仍可保存信息，速度較慢，成本較低兩部分組成：驅動部分+存儲介質種類很多外存空間組織與地址與存取方式非常復雜I/O過程方式非常復雜Page52023/2/3文件的物理結構用戶對外存的要求使用：讀寫外存數據要求：方便、效率、安全在讀寫外存時不涉及硬件細節，使用邏輯地址和邏輯操作存取速度盡可能快，容量大且空間利用率高外存上存放的信息安全可靠，防止來自硬件的故障和他人的侵權方便地共享，動態擴縮，攜帶拆卸，了解存儲情況和使用情況以盡可能小的代價完成上述要求Page62023/2/3文件的物理結構文件的物理結構是指邏輯文件在存儲設備（外存）上的存儲組織形式，它與存儲介質的存儲特性有關一個文件存儲介質，格式化后就分成許多大小相等的單位——存儲塊（物理盤塊），一般來說，每個物理塊是一個磁盤的扇區，512B。并給每個存儲塊有個編號，稱為物理塊號物理塊是分配和傳輸信息的基本單位，其與外存設備有關，但與邏輯記錄大小無關，如扇區、簇文件在邏輯上都可看作是連續的，但在物理設備上存放時卻有不同的方式，如連續結構（順序結構）、鏈接結構（串聯結構）、索引結構、HASH文件等Page72023/2/36.1.2文件類型和文件系統模型1.文件類型5、按文件的物理結構分類（1）順序文件。它是指把邏輯文件中的記錄順序地存儲到連續的物理盤塊中。（2）鏈接文件。它是指文件中的各個記錄可以存放在不相鄰接的各個物理盤塊中，通過物理塊中的鏈接指針，將它們連接成一個鏈表。（3）索引文件。它是指文件中的各個記錄可存儲在不相鄰接的各個物理塊中。Page82023/2/3外存分配方式連續分配鏈接分配索引分配Page92023/2/3連續分配連續分配(ContinuousAllocation)要求為每一個文件分配一組相鄰接的盤塊。一組盤塊定義了磁盤上的一段線性地址在采用連續分配方式時，可把邏輯文件中的記錄順序地存儲到鄰接的各物理盤塊中，這樣所形成的文件結構稱為順序文件結構，此時的物理文件稱為順序文件Page102023/2/3連續分配Page112023/2/3連續分配連續分配的主要優缺點優點結構簡單，容易實現支持順序存取和隨機存取順序存取速度快所需的磁盤尋道次數和尋道時間最少缺點要求有連續的存儲空間，不利于動態擴充容易形成碎片，空間利用不充分必須事先知道文件的長度，用戶不方便Page122023/2/3外存分配方式連續分配鏈接分配索引分配Page132023/2/3鏈接分配鏈接分配（ChainedAllocation）可通過在每個盤塊上的鏈接指針，將同屬于一個文件的多個離散的盤塊鏈接成一個鏈表，把這樣形成的物理文件稱為鏈接文件這種文件結構不要求連續存放對于記錄式文件一塊中可包含一個邏輯記錄或多個邏輯記錄，也可以若干物理塊包含一個邏輯記錄鏈接方式隱式鏈接顯式鏈接Page142023/2/3鏈接分配隱式鏈接文件名始址末址jeep925文件目錄01234567891011121314151617181920212223242526272829303111016-125磁盤空間的鏈接式分配Page152023/2/3鏈接分配隱式鏈接每個物理塊的最末一個字(或第一個字)作為鏈接字，它指出后繼塊的物理地址。鏈首指針存放在該文件目錄中。文件的結尾塊的指針為“∧”優點離散存儲，空間利用率高順序存取效率高缺點隨機存取效率太低，若要訪問第i個物理塊，必須讀出前i-1個Page162023/2/3鏈接分配顯式鏈接為了克服鏈接文件的存取效率太低的問題，人們提出文件映照的技術，即把鏈接文件中的鏈接字集中在一結構中，這樣既保持了鏈接文件的優點，也克服了其缺點，DOS、WINDOWS系統就采用了這樣結構文件分配表（FileAllocationTable,FAT）Page172023/2/3鏈接分配文件分配表（FileAllocationTable,FAT）磁盤格式化后建立，從磁盤的第二個開始，有兩個相同的FAT用于記錄外存分配狀況，每個盤塊（或簇）占一項，放在內存中，整個系統一張FAT表的序號為物理盤塊號或簇號，從0至N-1分配給一個文件的所有物理塊都在該表中標出，文件的第一個盤塊號記入文件的FCB中Page182023/2/3鏈接分配顯式鏈接Page192023/2/3鏈接分配顯式鏈接在FAT中每個物理塊占一個表項，增加一個指針指向下一個物理塊，最末一個物理塊的指針為“∧”Page202023/2/3鏈接分配Page212023/2/3DOS磁盤盤區劃分表Page222023/2/3DOS磁盤訪問操作流程文件名磁盤目錄表FDT磁盤參數表文件位置分配表FAT磁盤扇區定位扇區物理操作磁盤基數表Page232023/2/3鏈接分配實例對于1.2M磁盤，每個物理塊大小為1KB，則共有1.2K個FAT表項，若每個表項占12位（1.5B），則共需1.8KB的空間來保存FAT。顯式鏈接分配優點便于快速查找缺點FAT很大，需較大的內存空間Page242023/2/3鏈接分配主要優缺點優點消除了外部碎片，提高外存利用率文件動態增長時，可動態地為它分配盤塊文件的增刪改方便，不需事先知道文件長缺點存取速度慢只適于順序存取，不適于隨機存取可靠性差，若某一塊指針出錯，則鏈斷開更多的尋道次數和尋道時間鏈接指針占用一定的空間Page252023/2/3外存分配方式連續分配鏈接分配索引分配Page262023/2/3索引分配一個文件的信息存放在若干不連續物理塊中，另一種形式的非連續文件，文件數據存放的存儲介質上的物理塊號與文件的邏輯塊號一一對應，系統為這樣對應關系建立一個專用數據結構--索引表索引表：一個文件所有記錄的關鍵字和其它地址的對照表一個索引表就是磁盤塊地址數組,其中第i個條目指向文件的第i塊Page272023/2/3索引分配單級索引分配鏈接分配存在的問題不能支持高效的直接存取，要對一個較大的文件進行直接存取，須首先在FAT中順序地查找許多盤塊號。FAT需占用較大的內存空間索引分配為每個文件分配一個索引塊，把分配給該文件的所有盤塊號都記錄在該索引塊中在建立一個文件時，便為之建立的目錄項中填上指向該索引塊的指針支持直接訪問對于大文件而言，該方式優于鏈式分配方式Page282023/2/3索引分配012345678910111213141516171819202122232425262728293031文件名索引表地址文件目錄Jeep1991611025-1-1-119Page292023/2/3索引分配若每個盤塊大小為1KB，每個盤塊號占4B，則索引塊中可存放256個盤塊號，即采用這種索引方式時每個文件大小不能超過256KB索引表組織鏈接模式:一個盤塊一個索引表,多個索引表鏈接起來多級索引:將一個大文件的所有索引表（二級索引)的地址放在另一個索引表（一級索引)中Page302023/2/3索引分配多級索引分配Page312023/2/3索引分配若每個盤塊大小為1KB，每個盤塊號占4B，則一級索引塊中可存放256個盤塊號，即對應256個二級索引塊每個二級索引塊可對應256個物理磁盤塊，采用這種索引方式時每個文件大小不能超過256*256*1KB=64MB若每個盤塊大小為4K，則最大文件大小為1K*1K*4K=4GBPage322023/2/3混合索引分配直接地址物理盤塊索引塊Page332023/2/3混合索引分配直接地址為了提高對文件的檢索速度，在索引結點中可設置10個直接地址項，即用iaddr(0)~iaddr(9)來存放直接地址一次間接地址對于大、中型文件，可再利用索引結點中的地址項iaddr(10)來提供一次間接地址。這種方式的實質就是一級索引分配方式多次間接地址當文件長度大于4MB+40KB時(一次間址與10個直接地址項)，系統還須采用二次間址分配方式。這時，用地址項iaddr(11)提供二次間接地址。該方式的實質是兩級索引分配方式Page342023/2/3索引分配UNIX系統采用索引文件結構，UNIX系統采用多級間接索引結構，對小型文件采用直接索引，對大型文件采用間接索引，從而，既保證絕大多數的文件有高的存取效率，又能適應存取一些大型文件。（既保證了文件系統的高效率，又使其有很寬的適應面）Page352023/2/3Page362023/2/3索引分配索引結構優缺點優點：保持了鏈接結構的優點,又解決了其缺點：即能順序存取,又能隨機存取，滿足了文件動態增長、插入刪除的要求，也能充分利用外存空間缺點：較多的尋道次數和尋道時間，索引表本身帶來了系統開銷，如：內外存空間，存取時間Page372023/2/3索引分配索引分配的主要問題需要較多外存空間來建立索引塊對于小文件，空間浪費嚴重Page382023/2/3文件物理結構的比較連續文件的優點是不需要額外的空間開銷，只要在文件目錄中指出文件的大小和首塊的塊號即可，對順序的訪問效率很高。適應于順序存取。缺點是動態地增長和縮小系統開銷很大；文件創建時要求用戶提供文件的大小；存儲空間浪費較大。鏈式文件克服了連續文件的不足之處，但文件的隨機訪問系統開銷較大。適應于順序訪問。DOS系統中改造了鏈式文件的結構，使其克服了鏈式文件的不足，但增加了系統的危險性。Page392023/2/3文件物理結構的比較索引文件既適應于順序存訪問，也適應于隨機訪問，