操作系統(tǒng)課件第六章3

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

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

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

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