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

1、Operating SystemOperating SystemPage 12022-3-15Operating SystemOperating Systemq文件和文件系統(tǒng)文件和文件系統(tǒng)q文件的邏輯結構文件的邏輯結構q外存分配方式外存分配方式q目錄管理目錄管理q文件存儲空間的管理文件存儲空間的管理q文件共享與文件保護文件共享與文件保護q數(shù)據(jù)一致性控制數(shù)據(jù)一致性控制Page 22022-3-15Operating SystemOperating System6.3 外存分配方式外存分配方式 對于任何一個文件，都存在著以下兩種形式的結構：對于任何一個文件，都存在著以下兩種形式的結構： (1) 文

2、件的文件的(File Logical Structure)。 (2) 文件的文件的， 又稱為文件的存儲結構，又稱為文件的存儲結構， 是指文件是指文件在外存上的存儲組織形式。在外存上的存儲組織形式。 Page 32022-3-15Operating SystemOperating System如何才能有效地利用外存空間如何才能有效地利用外存空間?如何提高對文件的訪問速度如何提高對文件的訪問速度?Page 42022-3-15Operating SystemOperating Systemq外存的特點外存的特點v容量大，斷電后仍可保存信息，速度較慢，容量大，斷電后仍可保存信息，速度較慢，成本較低成

3、本較低v兩部分組成：驅(qū)動部分兩部分組成：驅(qū)動部分+ +存儲介質(zhì)存儲介質(zhì)v種類很多種類很多v外存空間組織與地址與存取方式非常復雜外存空間組織與地址與存取方式非常復雜vI/O過程方式非常復雜過程方式非常復雜Page 52022-3-15Operating SystemOperating Systemq用戶對外存的要求用戶對外存的要求v使用：讀寫外存數(shù)據(jù)使用：讀寫外存數(shù)據(jù)v要求：方便、效率、安全要求：方便、效率、安全q在讀寫外存時不涉及硬件細節(jié)，使用邏輯地址在讀寫外存時不涉及硬件細節(jié)，使用邏輯地址和邏輯操作和邏輯操作q存取速度盡可能快，容量大且空間利用率高存取速度盡可能快，容量大且空間利用率高q外存

4、上存放的信息安全可靠，防止來自硬件的外存上存放的信息安全可靠，防止來自硬件的故障和他人的侵權故障和他人的侵權q方便地共享，動態(tài)擴縮，攜帶拆卸，了解存儲方便地共享，動態(tài)擴縮，攜帶拆卸，了解存儲情況和使用情況情況和使用情況q以盡可能小的代價完成上述要求以盡可能小的代價完成上述要求Page 62022-3-15Operating SystemOperating Systemq文件的物理結構是指邏輯文件文件的物理結構是指邏輯文件在存儲設備在存儲設備（外存）（外存）上的上的存儲組織形式存儲組織形式，它與存儲介質(zhì)的存儲特性有，它與存儲介質(zhì)的存儲特性有關關q一個文件存儲介質(zhì)，格式化后就分成許多大小相一個文件

5、存儲介質(zhì)，格式化后就分成許多大小相等的單位等的單位存儲塊（物理盤塊），一般來說，存儲塊（物理盤塊），一般來說，每個物理塊是一個磁盤的扇區(qū)，每個物理塊是一個磁盤的扇區(qū)，512B。并給每。并給每個存儲塊有個編號，稱為物理塊號個存儲塊有個編號，稱為物理塊號q物理塊是物理塊是分配和傳輸分配和傳輸信息的信息的基本單位基本單位，其與外存，其與外存設備有關，但與邏輯記錄大小無關，如設備有關，但與邏輯記錄大小無關，如扇區(qū)、簇扇區(qū)、簇q文件在邏輯上都可看作是連續(xù)的，但在物理設備文件在邏輯上都可看作是連續(xù)的，但在物理設備上存放時卻有不同的方式，如上存放時卻有不同的方式，如連續(xù)結構（順序結連續(xù)結構（順序結構）、鏈接

6、結構（串聯(lián)結構）、索引結構、構）、鏈接結構（串聯(lián)結構）、索引結構、HASH文件文件等等Page 72022-3-15Operating SystemOperating System6.1.2 文件類型和文件系統(tǒng)模型文件類型和文件系統(tǒng)模型 1. 文件類型文件類型 （1）。它是指把邏輯文件中的記錄順序地存儲到它是指把邏輯文件中的記錄順序地存儲到連續(xù)的物理盤塊中。連續(xù)的物理盤塊中。（2）。它是指文件中的各個記錄可以存放在不相它是指文件中的各個記錄可以存放在不相鄰接的各個物理盤塊中，通過物理塊中的鏈接指針，將它鄰接的各個物理盤塊中，通過物理塊中的鏈接指針，將它們連接成一個鏈表。們連接成一個鏈表。（3）

7、。它是指文件中的各個記錄可存儲在不相鄰它是指文件中的各個記錄可存儲在不相鄰接的各個物理塊中。接的各個物理塊中。Page 82022-3-15Operating SystemOperating Systemq連續(xù)分配連續(xù)分配q鏈接分配鏈接分配q索引分配索引分配Page 92022-3-15Operating SystemOperating Systemq連續(xù)分配連續(xù)分配(Continuous Allocation)要求為每要求為每一個文件分配一個文件分配一組相鄰接的盤塊一組相鄰接的盤塊。一組盤塊定。一組盤塊定義了磁盤上的一段線性地址義了磁盤上的一段線性地址q在采用連續(xù)分配方式時，可把邏輯文件中的

8、記在采用連續(xù)分配方式時，可把邏輯文件中的記錄順序地存儲到鄰接的各物理盤塊中，這樣所錄順序地存儲到鄰接的各物理盤塊中，這樣所形成的文件結構稱為形成的文件結構稱為順序文件結構順序文件結構，此時的物，此時的物理文件稱為理文件稱為順序文件順序文件Page 102022-3-15Operating SystemOperating System1230567491011813141512171819162122232025262724list29303128mailcountfilestartlengthcount02tr143mail196list284f62目 錄trfPage 112022-3-15

9、Operating SystemOperating Systemq 連續(xù)分配的主要優(yōu)缺點連續(xù)分配的主要優(yōu)缺點v優(yōu)點優(yōu)點結構簡單，容易實現(xiàn)結構簡單，容易實現(xiàn)支持順序存取和隨機存取支持順序存取和隨機存取順序存取速度快順序存取速度快所需的磁盤尋道次數(shù)和尋道時間最少所需的磁盤尋道次數(shù)和尋道時間最少v缺點缺點要求有連續(xù)的存儲空間，不利于動態(tài)擴充要求有連續(xù)的存儲空間，不利于動態(tài)擴充容易形成容易形成碎片，空間利用不充分碎片，空間利用不充分必須事先知道文件的長度，用戶不方便必須事先知道文件的長度，用戶不方便Page 122022-3-15Operating SystemOperating Systemq連續(xù)分

10、配連續(xù)分配q鏈接分配鏈接分配q索引分配索引分配Page 132022-3-15Operating SystemOperating Systemq鏈接分配（鏈接分配（Chained Allocation）v可通過在每個盤塊上的鏈接指針，將同屬于一可通過在每個盤塊上的鏈接指針，將同屬于一個文件的多個個文件的多個離散的離散的盤塊鏈接成一個盤塊鏈接成一個鏈表鏈表，把，把這樣形成的物理文件稱為這樣形成的物理文件稱為鏈接文件鏈接文件q這種文件結構這種文件結構不要求連續(xù)存放不要求連續(xù)存放q對于記錄式文件一塊中可包含一個邏輯記錄或多對于記錄式文件一塊中可包含一個邏輯記錄或多個邏輯記錄，也可以若干物理塊包含一個

11、邏輯記個邏輯記錄，也可以若干物理塊包含一個邏輯記錄錄q鏈接方式鏈接方式v隱式鏈接隱式鏈接v顯式鏈接顯式鏈接Page 142022-3-15Operating SystemOperating Systemq隱式鏈接隱式鏈接文件名文件名 始址始址 末址末址jeep 9 25文件目錄文件目錄01234567891011121314151617181920212223242526272829303111016-125磁盤空間的鏈接式分配磁盤空間的鏈接式分配Page 152022-3-15Operating SystemOperating Systemq隱式鏈接隱式鏈接v每個物理塊的最末一個字每個物理塊

12、的最末一個字(或第一個字或第一個字)作為鏈作為鏈接字，它指出后繼塊的物理地址。鏈首指針存接字，它指出后繼塊的物理地址。鏈首指針存放在該文件目錄中。文件的結尾塊的指針為放在該文件目錄中。文件的結尾塊的指針為“”v優(yōu)點優(yōu)點離散存儲，空間利用率高離散存儲，空間利用率高順序存取效率高順序存取效率高v缺點缺點隨機存取效率太低，若要訪問第隨機存取效率太低，若要訪問第i個物理塊，個物理塊，必須讀出前必須讀出前i-1個個Page 162022-3-15Operating SystemOperating Systemq顯式鏈接顯式鏈接v為了克服鏈接文件的存取效率太低的問題，人為了克服鏈接文件的存取效率太低的問題

13、，人們提出們提出文件映照的技術文件映照的技術，即把鏈接文件中的鏈，即把鏈接文件中的鏈接字集中在一結構中，接字集中在一結構中，這樣既保持了鏈接文件這樣既保持了鏈接文件的優(yōu)點，也克服了其缺點的優(yōu)點，也克服了其缺點，DOS、WINDOWS系統(tǒng)就采用了這樣結構系統(tǒng)就采用了這樣結構q文件分配表（文件分配表（File Allocation Table, FAT）Page 172022-3-15Operating SystemOperating Systemq文件分配表（文件分配表（File Allocation Table, FAT）v磁盤格式化后建立，從磁盤的第二個開始，磁盤格式化后建立，從磁盤的第二個

14、開始，有兩個相同的有兩個相同的FATv用于記錄外存分配狀況，每個盤塊（或簇）用于記錄外存分配狀況，每個盤塊（或簇）占一項，放在內(nèi)存中，整個系統(tǒng)一張占一項，放在內(nèi)存中，整個系統(tǒng)一張FATv表的序號為物理盤塊號或簇號，從表的序號為物理盤塊號或簇號，從0至至N-1v分配給一個文件的所有物理塊都在該表中標分配給一個文件的所有物理塊都在該表中標出，文件的第一個盤塊號記入文件的出，文件的第一個盤塊號記入文件的FCB中中Page 182022-3-15Operating SystemOperating Systemq顯式鏈接顯式鏈接012345物理塊號物理塊號2FCBFAT0451Page 192022-3

15、-15Operating SystemOperating Systemq顯式鏈接顯式鏈接v在在FAT中每個物理塊占一個表項，增加中每個物理塊占一個表項，增加一個指針指向下一個物理塊，最末一個一個指針指向下一個物理塊，最末一個物理塊的指針為物理塊的指針為“”Page 202022-3-15Operating SystemOperating System6EOF11105EOF0123456789FATFCB A4FCB B9Page 212022-3-15Operating SystemOperating SystemPage 222022-3-15Operating SystemOperati

16、ng SystemPage 232022-3-15Operating SystemOperating Systemq實例實例v對于對于1.2M磁盤，每個物理塊大小為磁盤，每個物理塊大小為1KB，則共有則共有1.2K個個FAT表項，若每個表項占表項，若每個表項占12位（位（1.5B），則共需），則共需1.8KB的空間來保存的空間來保存FAT。q顯式鏈接分配顯式鏈接分配v優(yōu)點優(yōu)點便于快速查找便于快速查找v缺點缺點FAT很大，需較大的內(nèi)存空間很大，需較大的內(nèi)存空間Page 242022-3-15Operating SystemOperating Systemq主要優(yōu)缺點主要優(yōu)缺點v優(yōu)點優(yōu)點消除了外部

17、碎片，提高外存利用率消除了外部碎片，提高外存利用率文件動態(tài)增長時，可動態(tài)地為它分配盤塊文件動態(tài)增長時，可動態(tài)地為它分配盤塊文件的增刪改方便，不需事先知道文件長文件的增刪改方便，不需事先知道文件長v缺點缺點存取速度慢存取速度慢只適于只適于順序存取順序存取，不適于隨機存取不適于隨機存取可靠性差，若某一塊可靠性差，若某一塊指針指針出錯，則鏈斷開出錯，則鏈斷開更多的尋道次數(shù)和尋道時間更多的尋道次數(shù)和尋道時間鏈接指針占用一定的空間鏈接指針占用一定的空間Page 252022-3-15Operating SystemOperating Systemq連續(xù)分配連續(xù)分配q鏈接分配鏈接分配q索引分配索引分配Pa

18、ge 262022-3-15Operating SystemOperating Systemq一個文件的信息存放在若干不連續(xù)物理塊中，另一個文件的信息存放在若干不連續(xù)物理塊中，另一種形式的非連續(xù)文件，文件數(shù)據(jù)存放的存儲介一種形式的非連續(xù)文件，文件數(shù)據(jù)存放的存儲介質(zhì)上的物理塊號與文件的邏輯塊號一一對應，系質(zhì)上的物理塊號與文件的邏輯塊號一一對應，系統(tǒng)為這樣對應關系統(tǒng)為這樣對應關系建立一個專用建立一個專用數(shù)據(jù)結構數(shù)據(jù)結構-索引索引表表q索引表：一個文件所有記錄的關鍵字和其它地址索引表：一個文件所有記錄的關鍵字和其它地址的對照表的對照表q一個索引表就是磁盤塊地址數(shù)組一個索引表就是磁盤塊地址數(shù)組, ,其

19、中第其中第i i個條目個條目指向文件的第指向文件的第i i塊塊Page 272022-3-15Operating SystemOperating Systemq單級索引分配單級索引分配v鏈接分配存在的問題鏈接分配存在的問題不能支持高效的直接存取不能支持高效的直接存取，要對一個，要對一個較大的文較大的文件件進行進行直接存取直接存取，須首先在，須首先在FAT中順序地查找中順序地查找許多盤塊號。許多盤塊號。FAT需需占用較大占用較大的的內(nèi)存內(nèi)存空間空間v索引分配索引分配為為每個文件分配一個索引塊每個文件分配一個索引塊，把分配給該文件，把分配給該文件的所有盤塊號都記錄在該索引塊中的所有盤塊號都記錄在該

20、索引塊中在建立一個文件時，便為之建立的目錄項中填在建立一個文件時，便為之建立的目錄項中填上指向該索引塊的指針上指向該索引塊的指針v支持直接訪問支持直接訪問對于大文件而言，該方式優(yōu)于鏈式分配方式對于大文件而言，該方式優(yōu)于鏈式分配方式Page 282022-3-15Operating SystemOperating System012345678910111213141516171819202122232425262728293031文件名文件名 索引表地址索引表地址文件目錄文件目錄Jeep 19 916 11025 -1 -1 -119Page 292022-3-15Operating Syst

21、emOperating Systemq若每個盤塊大小為若每個盤塊大小為1KB，每個盤塊號占，每個盤塊號占4B，則索引塊中可存放則索引塊中可存放256個盤塊號，即采用這種個盤塊號，即采用這種索引方式時每個文件索引方式時每個文件大小不能大小不能超過超過256KBq索引表組織索引表組織v鏈接模式鏈接模式: :一個盤塊一個索引表一個盤塊一個索引表, ,多個索引多個索引表鏈接起來表鏈接起來v多級索引多級索引: :將一個大文件的所有索引表（二將一個大文件的所有索引表（二級索引級索引) )的地址放在另一個索引表（一級索的地址放在另一個索引表（一級索引引) )中中Page 302022-3-15Operati

22、ng SystemOperating Systemq多級索引分配多級索引分配012-105106254356357985105106254740356357-1125985360740-1125-主索引主索引360第二級索引第二級索引磁盤空間磁盤空間Page 312022-3-15Operating SystemOperating Systemq若每個盤塊大小為若每個盤塊大小為1KB，每個盤塊號占，每個盤塊號占4B，則一，則一級索引塊中可存放級索引塊中可存放256個盤塊號，即對應個盤塊號，即對應256個個二級索引塊二級索引塊q每個二級索引塊可對應每個二級索引塊可對應256個物理磁盤塊，采用個物

23、理磁盤塊，采用這種索引方式時每個文件大小不能超過這種索引方式時每個文件大小不能超過256*256*1KB=64MBq若每個盤塊大小為若每個盤塊大小為4K，則最大文件大小為，則最大文件大小為1K*1K*4K=4GBPage 322022-3-15Operating SystemOperating Systemmodeowners (2)time stamps (3)sizeblock counti.addr (0)i.addr (1)direct blockssingle indirectdouble indirecttriple indirectdatadatadatadata-datadat

24、a-datadatadatadata直接地址物理盤塊索引塊Page 332022-3-15Operating SystemOperating Systemq直接地址直接地址v為了提高對文件的檢索速度，為了提高對文件的檢索速度， 在索引結點中可在索引結點中可設置設置10個直接地址項，個直接地址項， 即用即用iaddr(0)iaddr(9)來存放直接地址來存放直接地址q一次間接地址一次間接地址v對于大、對于大、 中型文件，可再利用索引結點中的地中型文件，可再利用索引結點中的地址項址項iaddr(10)來提供一次間接地址。這種方式來提供一次間接地址。這種方式的實質(zhì)就是一級索引分配方式的實質(zhì)就是一級索

25、引分配方式q多次間接地址多次間接地址v當文件長度大于當文件長度大于4 MB+40 KB時時(一次間址與一次間址與10個直接地址項個直接地址項)， 系統(tǒng)還須采用二次間址分配系統(tǒng)還須采用二次間址分配方式。這時，用地址項方式。這時，用地址項iaddr(11)提供二次間接提供二次間接地址。該方式的實質(zhì)是兩級索引分配方式地址。該方式的實質(zhì)是兩級索引分配方式Page 342022-3-15Operating SystemOperating SystemqUNIX系統(tǒng)采用索引文件結構，系統(tǒng)采用索引文件結構，UNIXUNIX系統(tǒng)采用多系統(tǒng)采用多級間接索引結構，對小型文件采用直接索引，對級間接索引結構，對小型文

26、件采用直接索引，對大型文件采用間接索引，從而，既保證絕大多數(shù)大型文件采用間接索引，從而，既保證絕大多數(shù)的文件有高的存取效率，又能適應存取一些大型的文件有高的存取效率，又能適應存取一些大型文件。（既保證了文件系統(tǒng)的高效率，又使其有文件。（既保證了文件系統(tǒng)的高效率，又使其有很寬的適應面）很寬的適應面）Page 352022-3-15Operating SystemOperating SystemPage 362022-3-15Operating SystemOperating Systemq索引結構優(yōu)缺點索引結構優(yōu)缺點v優(yōu)點：優(yōu)點： 保持了鏈接結構的優(yōu)點保持了鏈接結構的優(yōu)點, ,又解決了其缺又解決

27、了其缺點：即能順序存取點：即能順序存取, ,又能隨機存取，滿足了又能隨機存取，滿足了文件動態(tài)增長、插入刪除的要求，也能充文件動態(tài)增長、插入刪除的要求，也能充分利用外存空間分利用外存空間v缺點：缺點： 較多的尋道次數(shù)和尋道時間，索引表較多的尋道次數(shù)和尋道時間，索引表本身帶來了系統(tǒng)開銷，如：內(nèi)外存空間，本身帶來了系統(tǒng)開銷，如：內(nèi)外存空間，存取時間存取時間Page 372022-3-15Operating SystemOperating Systemq索引分配的主要問題索引分配的主要問題v需要較多外存空間來建立索引塊需要較多外存空間來建立索引塊v對于小文件，空間浪費嚴重對于小文件，空間浪費嚴重Page 382022-3-15Operating SystemOperating Systemq連