第六章文件管理操作系統(tǒng)Page12023/2/3第六章文件管理文件和文件系統(tǒng)文件的邏輯結(jié)構(gòu)外存分配方式目錄管理文件存儲空間的管理文件共享與文件保護數(shù)據(jù)一致性控制Page22023/2/36.3外存分配方式

對于任何一個文件，都存在著以下兩種形式的結(jié)構(gòu)：

(1)文件的邏輯結(jié)構(gòu)(FileLogicalStructure)。

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