操作系統(tǒng)原理第9章文件管理

1、2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章1操作系統(tǒng)原理操作系統(tǒng)原理Operating System Principles四川大學(xué)計(jì)算機(jī)學(xué)院段 磊20142022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章2第第9章章 文件管理文件管理n 存儲在外存上的信息的組織形式是文件n 文件系統(tǒng)是操作系統(tǒng)中管理信息資源的軟件n 說明存儲文件及其屬性n 控制和管理文件n 提供文件使用接口n 安全實(shí)現(xiàn)文件的共享與保護(hù)n 磁盤是重要的外存2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章3本章目錄n9.1 文件和文件的屬性 n9.2 文件結(jié)構(gòu)和文件實(shí)現(xiàn)n9.3 文件系統(tǒng)n9.4 目錄管理n9.5 磁盤存儲器管理n9.6 文件系

2、統(tǒng)性能和可靠性n9.7 文件的共享和保護(hù)2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章4本章目錄n9.1 文件和文件的屬性 n9.2 文件結(jié)構(gòu)和文件實(shí)現(xiàn)n9.3 文件系統(tǒng)n9.4 目錄管理n9.5 磁盤存儲器管理n9.6 文件系統(tǒng)性能和可靠性n9.7 文件的共享和保護(hù)2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章59.1.1 文件的概念n數(shù)據(jù)項(xiàng)n基本數(shù)據(jù)項(xiàng)：可命名的最小邏輯單位/字段n組合數(shù)據(jù)項(xiàng)：由若干基本數(shù)據(jù)項(xiàng)組成n基本數(shù)據(jù)項(xiàng)的類型和數(shù)據(jù)n記錄n一組相關(guān)數(shù)據(jù)項(xiàng)的集合n關(guān)鍵字：能唯一地標(biāo)識出記錄的基本/組合數(shù)據(jù)項(xiàng)n文件n由文件名標(biāo)注的一組信息的結(jié)合n用于邏輯上描述存儲在外存上的數(shù)據(jù)2022-4-20計(jì)

3、算機(jī)操作系統(tǒng)- 第9章6文件的概念n文件的存取方法n所謂文件的存取方法，是指讀寫文件存儲器上的一個(gè)物理塊的方法，是指操作系統(tǒng)為用戶程序提供的使用文件的技術(shù)和手段。n文件的存取方法不僅與文件的性質(zhì)有關(guān)，而且與用戶使用文件的方式有關(guān)。n通常有3類存取方法：順序存取法、直接存取法和按鍵存取法。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章7文件的概念n文件的存取方法n順序存取法：嚴(yán)格按物理記錄排列的順序依次存取 n直接存取法：允許用戶隨意存取文件中的任何一個(gè)物理記錄，而不管上次存取了哪一個(gè)記錄。 n按鍵存取法：實(shí)質(zhì)上也是直接存取法，它不是根據(jù)記錄編號或地址來存取，而是根據(jù)文件中各記錄內(nèi)容進(jìn)行存取的。

4、2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章8文件系統(tǒng)文件系統(tǒng)服務(wù)器文件系統(tǒng)服務(wù)器文件結(jié)構(gòu)定義文件結(jié)構(gòu)定義文件訪問控制文件訪問控制 安全、保護(hù)安全、保護(hù)磁盤空間分配磁盤空間分配磁盤數(shù)據(jù)存取磁盤數(shù)據(jù)存取 磁盤設(shè)備防護(hù)磁盤設(shè)備防護(hù)數(shù)據(jù)文件數(shù)據(jù)文件磁盤空間磁盤空間映映 射射應(yīng)用層觀點(diǎn)：邏輯抽象應(yīng)用層觀點(diǎn)：邏輯抽象物理層觀點(diǎn)：空間管理物理層觀點(diǎn)：空間管理2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章99.1.2 文件的分類n按用途分類：系統(tǒng)文件，用戶文件，庫文件。（用戶對以上三者的訪問權(quán)限不同）n按文件中的數(shù)據(jù)形式分類源，目標(biāo)，可執(zhí)行。n存取控制E，R，R/W2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章10文

5、件的分類n邏輯結(jié)構(gòu)n有結(jié)構(gòu)（記錄式）n無結(jié)構(gòu)（流式）n物理安排n順序文件：數(shù)據(jù)（連續(xù)放）n鏈接文件n索引文件n保存期限n臨時(shí)文件n永久文件n檔案文件2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章119.1.3 文件的屬性n屬性的含義n文件類型n文件長度n文件物理位置n文件建立時(shí)間n2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章12文件的屬性n常見文件屬性及其含義n保護(hù)：誰可以存取文件、以什么方式存取文件n口令：存取文件需要的口令n創(chuàng)建者：文件的創(chuàng)建者IDn所有者：當(dāng)前所有者n只讀標(biāo)志：0表示讀/寫；1表示只讀n隱藏標(biāo)志：0表示正常；1表示不在列表中顯示n系統(tǒng)標(biāo)志：0表示普通文件；1表示系統(tǒng)文件2022

6、-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章13文件的屬性n常見文件屬性及其含義n存檔標(biāo)志：0表示已經(jīng)備份；1表示需要備份nASCII/二進(jìn)制標(biāo)志：0表示ASCII文件；1表示二進(jìn)制文件n隨機(jī)存取標(biāo)志：0表示只允許順序存取；1表示隨機(jī)存取n臨時(shí)標(biāo)志：0表示正常；1表示進(jìn)程退出時(shí)刪除文件n加鎖標(biāo)志：0表示未加鎖；1表示已加鎖n記錄長度：1個(gè)記錄中的字節(jié)數(shù)n鍵的位置：每個(gè)記錄中鍵的偏移量2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章14文件的屬性n常見文件屬性及其含義n鍵的長度：鍵字段的字節(jié)數(shù)n創(chuàng)建時(shí)間：文件創(chuàng)建的日期和時(shí)間n最后一次存取時(shí)間：文件上一次存取的日期和時(shí)間n最后一次修改時(shí)間：文件上一次修改的日期和

7、時(shí)間n當(dāng)前大小：文件的字節(jié)數(shù)n最大長度：文件可能增長到的字節(jié)數(shù)2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章15本章目錄n9.1 文件和文件的屬性 n9.2 文件結(jié)構(gòu)和文件實(shí)現(xiàn)n9.3 文件系統(tǒng)n9.4 目錄管理n9.5 磁盤存儲器管理n9.6 文件系統(tǒng)性能和可靠性n9.7 文件的共享和保護(hù)2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章16n人們常以兩種不同的觀點(diǎn)去研究文件的結(jié)構(gòu)。n用戶的觀點(diǎn)n主要研究觀察到的文件組織形式，用戶可以直接處理其中的結(jié)構(gòu)和數(shù)據(jù)n常被稱為邏輯結(jié)構(gòu)n實(shí)現(xiàn)的觀點(diǎn)n主要研究存儲介質(zhì)上的實(shí)際文件結(jié)構(gòu)，是指文件在外存上的存儲組織形式n常被稱為物理結(jié)構(gòu)或存儲結(jié)構(gòu)9.2.1 文件的邏輯結(jié)

8、構(gòu)2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章17n人們常以兩種不同的觀點(diǎn)去研究文件的結(jié)構(gòu)。n用戶的觀點(diǎn)n主要研究觀察到的文件組織形式，用戶可以直接處理其中的結(jié)構(gòu)和數(shù)據(jù)n常被稱為邏輯結(jié)構(gòu)n實(shí)現(xiàn)的觀點(diǎn)n主要研究存儲介質(zhì)上的實(shí)際文件結(jié)構(gòu)，是指文件在外存上的存儲組織形式n常被稱為物理結(jié)構(gòu)或存儲結(jié)構(gòu)無論是邏輯還是物理結(jié)構(gòu)無論是邏輯還是物理結(jié)構(gòu) 都會影響到文件的檢索速度都會影響到文件的檢索速度9.2.1 文件的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)的概念：邏輯結(jié)構(gòu)的概念： 用戶所能觀察和訪問到的文件的數(shù)據(jù)結(jié)構(gòu)組織用戶所能觀察和訪問到的文件的數(shù)據(jù)結(jié)構(gòu)組織 獨(dú)立于物理特性，容易檢索和修改。獨(dú)立于物理特性，容易檢索和修改。2022-

9、4-20計(jì)算機(jī)操作系統(tǒng)- 第9章18文件的邏輯結(jié)構(gòu)n有結(jié)構(gòu)文件：記錄式文件n無結(jié)構(gòu)文件：流式文件n以字節(jié)為單位，利用讀/寫指針進(jìn)行訪問a a類：類：l 定長記錄定長記錄l 變長記錄變長記錄b b類：類：l 連續(xù)文件：按照記錄生成時(shí)間連續(xù)文件：按照記錄生成時(shí)間l 順序文件：通常是定長記錄順序文件：通常是定長記錄l 索引文件：索引文件：l 索引順序文件：順序組織多個(gè)組，索引順序文件：順序組織多個(gè)組，每組記錄中的第一個(gè)記錄設(shè)置一索每組記錄中的第一個(gè)記錄設(shè)置一索引項(xiàng)。引項(xiàng)。2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章19文件的邏輯結(jié)構(gòu)n順序文件n邏輯記錄的順序n按記錄錄入的時(shí)間排:串結(jié)構(gòu)n按關(guān)鍵字排序：

10、順序結(jié)構(gòu)n后一種情況更有利于提高查詢速度n對順序文件的讀/寫操作n定長記錄順序文件：例：順序讀n易于定位，甚至可隨機(jī)讀取。n變長記錄：不易定位，只能順序讀取。2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章20文件的邏輯結(jié)構(gòu)n順序文件-評價(jià)n批處理時(shí)效率是所有邏輯文件中最高的n可存在于磁帶上n交互應(yīng)用時(shí)“效率低”（如要查找單個(gè)記錄），尤其是對變長記錄的順序文件n增加、刪除記錄涉及到排序問題，開銷大n事務(wù)文件(log)，用于存放將更新到主文件的記錄2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章21文件的邏輯結(jié)構(gòu)n索引文件n由變長記錄組成的順序文件不容易直接存取，因此考慮為其建立一有序的索引表，對索引采用折

11、半查找，速度更快n特點(diǎn)：n提高了速度，增加了存儲開銷（存放索引文件）n增、刪記錄時(shí)，對索引表作相應(yīng)的修改。2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章22文件的邏輯結(jié)構(gòu)n索引順序文件n將順序文件中若干記錄分為一組，每組第一項(xiàng)在索引表中占一項(xiàng)。 n速度：n例1：10000個(gè)記錄順序文件：5000次查找索引順序文件：設(shè)100個(gè)記錄一組，索引表的找法設(shè)為順序法的情況下，則查找次數(shù)為50+50=100n例2：1000000個(gè)紀(jì)錄： 低級索引：（100個(gè)紀(jì)錄一組）：10000高級索引：100速度：50+50+50=1502022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章239.2.2 文件的物理結(jié)構(gòu)n在采用連續(xù)分

12、配方式時(shí)，可把邏輯文件中的記錄順序地存儲到鄰接的各物理盤塊中，這樣所形成的文件結(jié)構(gòu)稱為順序文件結(jié)構(gòu)，此時(shí)的物理文件稱為順序文件。n這種分配方式保證了邏輯文件中的記錄順序與存儲器中文件占用盤塊的順序的一致性。2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章24文件的物理結(jié)構(gòu)n順序文件（連續(xù)分配）n每個(gè)文件分配一組相鄰盤塊。n特點(diǎn)：簡單n順序訪問容易且速度快，因磁頭移動距離小，n要求連續(xù)空間，一段時(shí)間后需整理磁盤以消除外部碎片。n必須事先知道長度，文件不易動態(tài)增長和刪除。n文件對應(yīng)目錄項(xiàng)（屬性）中包含：始址、總塊數(shù)、最后一塊字節(jié)數(shù)。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章25文件的物理結(jié)構(gòu)n順序文件

13、（鏈接分配）n文件離散地分配于各盤塊中，以提高外存利用率，文件長度可變，易于增刪，只能順序存取。n對應(yīng)目錄項(xiàng)：鏈表的首指針n評價(jià)-優(yōu)點(diǎn)：n避免了順序文件要求連續(xù)分配存儲空間的問題，消除了物理塊的外部“碎片”，外存利用率更高。n通過指針將物理塊鏈接在一起，使得文件的邏輯記錄順序與外存中記錄的物理放置完全獨(dú)立開來，克服了外存連續(xù)分配不能適應(yīng)文件增長和縮短的缺點(diǎn)。2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章26文件的物理結(jié)構(gòu)n評價(jià)-缺點(diǎn)：n每次文件的訪問總是從文件的第1個(gè)物理塊開始，沿鏈接指針得到其他的物理塊。如果需要訪問第B塊，則每次總是要從第1個(gè)物理塊開始，直到第B塊，花費(fèi)的時(shí)間很長n鏈接指針信息

14、的存放需要存儲空間，使得存儲器可利用空間減少n需要更多的磁盤尋道次數(shù)和更長的磁盤尋道時(shí)間n鏈接指針的可信度是影響該方法的關(guān)鍵。操作系統(tǒng)可能會由于系統(tǒng)軟件或硬件發(fā)生故障，導(dǎo)致鏈接指針丟失或出錯(cuò)，最終引起文件內(nèi)容丟失或出錯(cuò)2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章279.2.2 文件的物理結(jié)構(gòu)n索引文件（索引分配）n單級索引分配n鏈接分配方式雖然解決了連續(xù)分配方式所存在的問題，但又出現(xiàn)了下述另外兩個(gè)問題：n不能支持高效的直接存取。要對一個(gè)較大的文件進(jìn)行直接存取，須首先在FAT中順序地查找許多盤塊號nFAT需占用較大的內(nèi)存空間2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章28文件的物理結(jié)構(gòu)n將每個(gè)文件所

15、對應(yīng)的盤塊號集中地放在一起n索引分配方法就是基于這種想法所形成的一種分配方法n它為每個(gè)文件分配一個(gè)索引塊(表)，再把分配給該文件的所有盤塊號都記錄在該索引塊中，因而該索引塊就是一個(gè)含有許多盤塊號的數(shù)組n在建立一個(gè)文件時(shí)，只需在為之建立的目錄項(xiàng)中填上指向該索引塊的指針v 多級索引的概念多級索引的概念2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章299.2.3 文件的實(shí)現(xiàn)n順序存取：按照文件邏輯記錄的順序進(jìn)行文件讀/寫操作的存取方式為順序存取方式。n直接存?。阂卜Q為隨機(jī)存取，指用戶按照記錄的編號進(jìn)行文件存取時(shí)，根據(jù)存取命令，把讀寫指針直接移到讀寫處進(jìn)行操作。直接存取適合磁盤文件。n索引存?。阂卜Q為關(guān)鍵

16、字存取。以索引作為文件記錄的指針，對文件進(jìn)行存取。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章309.2.4 文件的操作n對文件的操作n創(chuàng)建文件 n刪除文件 n打開文件 n讀文件 n寫文件 n關(guān)閉文件 n對目錄的操作n讀操作 n寫操作 n查找 n修改n插入 n刪除2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章31文件的操作n用戶的文件交系統(tǒng)管理后，為保證文件的安全、可靠，用戶使用文件的操作步驟如下：n讀一個(gè)文件信息時(shí)，依次調(diào)用：n“打開”文件n“讀”文件n“關(guān)閉”文件n寫一個(gè)文件信息時(shí)，依次調(diào)用：n“建立”文件n“寫”文件n“關(guān)閉”文件2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章32本章目錄n9.1

17、 文件和文件的屬性 n9.2 文件結(jié)構(gòu)和文件實(shí)現(xiàn)n9.3 文件系統(tǒng)n9.4 目錄管理n9.5 磁盤存儲器管理n9.6 文件系統(tǒng)性能和可靠性n9.7 文件的共享和保護(hù)2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章339.3.1 文件系統(tǒng)及其功能 1文件系統(tǒng)文件系統(tǒng) n操作系統(tǒng)中管理信息資源的軟件n實(shí)現(xiàn)文件及其屬性說明的存儲n實(shí)施對文件的控制和管理n保證對文件的共享和保護(hù)n提供用戶使用文件的接口n主要包含: 文件、管理文件的目錄以及分區(qū)。n文件目錄文件目錄對文件系統(tǒng)中的文件進(jìn)行組織，提供系統(tǒng)中所有文件的屬性和管理控制信息。n分區(qū)分區(qū)用于劃分目錄，實(shí)現(xiàn)目錄的組織形式。2022-4-20計(jì)算機(jī)操作系統(tǒng)-

18、第9章34文件系統(tǒng)及其功能2文件系統(tǒng)的功能文件系統(tǒng)的功能 實(shí)現(xiàn)文件按名存??； 提供用戶對文件的訪問和操作； 實(shí)現(xiàn)邏輯文件到物理文件的映射； 實(shí)現(xiàn)文件目錄的建立和維護(hù)； 有效組織和管理文件存儲空間； 實(shí)現(xiàn)文件共享與保護(hù)。2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章35文件系統(tǒng)及其功能n用戶看重的文件系統(tǒng)功能：n文件系統(tǒng)對文件的命名形式、文件的組織形式、文件的保護(hù)措施和對文件的操作等功能；n操作系統(tǒng)注重的文件系統(tǒng)功能：n文件目錄的實(shí)現(xiàn)方法、文件存儲空間的管理方法、文件存儲的結(jié)構(gòu)、文件系統(tǒng)與設(shè)備管理的接口以及文件系統(tǒng)的性能等。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章369.3.2 文件系統(tǒng)模型n在

19、操作系統(tǒng)中，文件系統(tǒng)處于用戶接口與輸入/輸出設(shè)備管理之間，之上是用戶接口，之下是輸入/輸出設(shè)備管理。 文件系統(tǒng)文件系統(tǒng)用戶接口輸入/輸出設(shè)備管理2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章37文件系統(tǒng)模型n按照文件系統(tǒng)的功能設(shè)計(jì)成一個(gè)6層的文件系統(tǒng)結(jié)構(gòu) 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章38文件系統(tǒng)模型n按照文件系統(tǒng)的功能設(shè)計(jì)成一個(gè)6層的文件系統(tǒng)結(jié)構(gòu) 接收用戶對文件的操作命令或系統(tǒng)調(diào)用，根據(jù)用戶對文件的存取要求將其轉(zhuǎn)換為統(tǒng)一格式的文件系統(tǒng)內(nèi)部調(diào)用 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章39文件系統(tǒng)模型n按照文件系統(tǒng)的功能設(shè)計(jì)成一個(gè)6層的文件系統(tǒng)結(jié)構(gòu) 根據(jù)文件名或文件路徑名建立或搜索文

20、件目錄，獲得文件內(nèi)部標(biāo)志和目錄中的文件屬性。 從目錄中的文件屬性確定訪問文件的用戶身份，驗(yàn)證存取權(quán)限，判定本次文件操作的合法性，實(shí)現(xiàn)文件的存取、共享、保護(hù)。2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章40文件系統(tǒng)模型n按照文件系統(tǒng)的功能設(shè)計(jì)成一個(gè)6層的文件系統(tǒng)結(jié)構(gòu) 根據(jù)文件內(nèi)部標(biāo)志將文件說明信息調(diào)入內(nèi)存，為訪問文件做準(zhǔn)備。變換指定的邏輯記錄地址成相應(yīng)的物理塊地址。對于流式文件，把指定的邏輯地址按塊長計(jì)算出相對塊號；對記錄式文件，先把記錄號變換成邏輯地址，再把邏輯地址轉(zhuǎn)換成相對塊號。2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章41文件系統(tǒng)模型n按照文件系統(tǒng)的功能設(shè)計(jì)成一個(gè)6層的文件系統(tǒng)結(jié)構(gòu) 根據(jù)文件

21、在內(nèi)存中的物理結(jié)構(gòu)信息，將相對塊號和塊內(nèi)地址變換為文件存儲器的物理塊號和塊內(nèi)地址。2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章42文件系統(tǒng)模型n按照文件系統(tǒng)的功能設(shè)計(jì)成一個(gè)6層的文件系統(tǒng)結(jié)構(gòu) 負(fù)責(zé)文件存儲空間的分配，動態(tài)地為文件的寫操作申請物理塊，實(shí)現(xiàn)文件緩沖區(qū)的管理。2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章43文件系統(tǒng)模型n按照文件系統(tǒng)的功能設(shè)計(jì)成一個(gè)6層的文件系統(tǒng)結(jié)構(gòu) 執(zhí)行I/O操作，為文件分配磁盤等物理介質(zhì)空間，實(shí)現(xiàn)文件信息的存取。2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章449.3.3 文件系統(tǒng)的實(shí)例n對常用的操作系統(tǒng)，如DOS操作系統(tǒng)的0號扇區(qū)是引導(dǎo)計(jì)算機(jī)的主引導(dǎo)記錄主引導(dǎo)記錄，在主

22、引導(dǎo)記錄之后是分區(qū)表分區(qū)表，分區(qū)表中存放的是每個(gè)分區(qū)的起始地址和結(jié)束地址。n磁盤被劃分為多個(gè)分區(qū)，其中有一個(gè)分區(qū)為活動分區(qū)活動分區(qū)。每個(gè)分區(qū)上都有一個(gè)獨(dú)立的文件系統(tǒng)。每個(gè)分區(qū)的布局為：引導(dǎo)塊、超級塊、空閑空間管理信息、索引節(jié)點(diǎn)信息、根目錄、文件和目錄。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章45文件系統(tǒng)的實(shí)例n計(jì)算機(jī)的引導(dǎo)過程有以下幾步引導(dǎo)操作系統(tǒng)nBIOS被讀入內(nèi)存并執(zhí)行主引導(dǎo)記錄，確定活動分區(qū)，讀入活動分區(qū)的引導(dǎo)塊并執(zhí)行引導(dǎo)操作系統(tǒng)的程序，將操作系統(tǒng)裝入內(nèi)存。讀入文件系統(tǒng)n在文件系統(tǒng)首次使用時(shí)，超級塊超級塊中的文件系統(tǒng)信息被讀入內(nèi)存。為文件分配空閑塊n根據(jù)位示圖或鏈接表形式給出的空閑塊

23、信息為文件分配空閑塊。 文件系統(tǒng)的所有關(guān)文件系統(tǒng)的所有關(guān)鍵參數(shù)，如文件系鍵參數(shù)，如文件系統(tǒng)類型標(biāo)志和文件統(tǒng)類型標(biāo)志和文件數(shù)據(jù)塊數(shù)量數(shù)據(jù)塊數(shù)量 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章46本章目錄n9.1 文件和文件的屬性 n9.2 文件結(jié)構(gòu)和文件實(shí)現(xiàn)n9.3 文件系統(tǒng)n9.4 目錄管理n9.5 磁盤存儲器管理n9.6 文件系統(tǒng)性能和可靠性n9.7 文件的共享和保護(hù)2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章47目錄管理n目錄是文件和子目錄的容器n文件系統(tǒng)負(fù)責(zé)n目錄的建立、維護(hù)和檢索n提供目錄的創(chuàng)建和刪除、列舉和查找、檢索和遍歷、拷貝和重命名n防止目錄之間的沖突2022-4-20計(jì)算機(jī)操作系統(tǒng)-

24、 第9章48目錄管理n文件目錄的主要功能：實(shí)現(xiàn)文件的按名存??；在文件存儲器中查找指定的文件；有效管理系統(tǒng)文件和用戶文件；實(shí)現(xiàn)文件的共享。n文件目錄作為文件的組織者和管理者，需要永久保存。因此，文件目錄本身也被組織成文件，為目錄文件，并存放在磁盤上。2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章499.4.1 文件控制塊n在文件目錄中每個(gè)文件都有一個(gè)相應(yīng)的數(shù)據(jù)項(xiàng)，該數(shù)據(jù)項(xiàng)稱為文件控制塊（File Control Block，F(xiàn)CB）。n文件目錄是文件控制塊的有序集合，文件和文件控制塊一一對應(yīng)。n文件控制塊中的信息用于描述文件和控制文件。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章50文件控制塊文件控

25、制塊包含下列信息： 文件存取控制信息文件存取控制信息：文件名、擁有文件的用戶名、文件存取權(quán)限、文件訪問權(quán)限、文件類型等。文件類型包括目錄文件、一般文件、塊設(shè)備文件、字符設(shè)備文件、管道文件、鏈接文件等。 文件結(jié)構(gòu)信息文件結(jié)構(gòu)信息：文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)信息。文件的邏輯結(jié)構(gòu)信息有記錄類型、記錄個(gè)數(shù)、記錄長度等。物理的物理結(jié)構(gòu)信息有文件所在設(shè)備名、物理結(jié)構(gòu)類型、文件第一塊的物理地址或文件索引地址等。 文件管理信息文件管理信息：文件創(chuàng)建時(shí)間、文件修改時(shí)間、文件訪問時(shí)間、文件保留時(shí)間、打開文件的進(jìn)程數(shù)等。2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章51典型的文件系統(tǒng) n文件控制塊與文件一樣，都存儲在磁盤

26、上 一個(gè)典型的文件系統(tǒng)2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章52文件名長度限制n早期的操作系統(tǒng)，文件目錄中文件名部分的長度僅有8個(gè)字符空間。文件名長度限制在8個(gè)字符以內(nèi)。n為了在基本目錄項(xiàng)不變的情況下，增加文件名長度，采用了如下兩種方式：n使用額外目錄項(xiàng)的空間來保存文件名中的額外字符；n在每個(gè)目錄中建立一個(gè)堆，長文件名采用從堆中分配字符塊的方式。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章539.4.2 文件索引節(jié)點(diǎn)n為了節(jié)約內(nèi)存和加快檢索文件目錄的時(shí)間，引入了索引節(jié)點(diǎn)機(jī)制索引節(jié)點(diǎn)機(jī)制 n將文件目錄中的文件名和文件的其它信息分離開來。在文件目錄中存放的僅是文件名和索引節(jié)點(diǎn)指針，在索引節(jié)點(diǎn)中

27、存放的是文件的其它信息。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章54文件目錄與索引節(jié)點(diǎn) n在檢索文件時(shí)，系統(tǒng)將文件目錄放入內(nèi)存，通過文件名檢索文件目錄中的文件索引節(jié)點(diǎn)指針，從指針指向位置將文件的索引節(jié)點(diǎn)調(diào)入內(nèi)存，查詢內(nèi)存中的文件索引節(jié)點(diǎn)得到文件的信息-文件的物理地址。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章55索引節(jié)點(diǎn)n為了改善文件的訪問速度，避免多次訪問外存，系統(tǒng)會將需要訪問文件的索引節(jié)點(diǎn)放入內(nèi)存。n當(dāng)文件打開后，系統(tǒng)會將磁盤上的索引節(jié)點(diǎn)拷貝到內(nèi)存中，稱為內(nèi)存索引節(jié)點(diǎn)。當(dāng)打開文件的最后一個(gè)用戶關(guān)閉文件時(shí)，文件在內(nèi)存索引結(jié)點(diǎn)中的內(nèi)容被寫到外存索引結(jié)點(diǎn)中，并釋放內(nèi)存索引結(jié)點(diǎn)。n將文件目錄

28、與索引節(jié)點(diǎn)分開，不僅加快了文件的檢索速度，而且，便于實(shí)現(xiàn)文件共享。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章56文件共享 n不同文件目錄下不同文件名，或者相同目錄下不同文件名，可以有相同的索引節(jié)點(diǎn)指針，實(shí)現(xiàn)了真正意義上的文件共享。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章579.4.3 單級目錄結(jié)構(gòu)2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章58單級目錄結(jié)構(gòu)n單級目錄最明顯的缺點(diǎn)有以下兩方面。（1）用戶文件不能重名n在多用戶環(huán)境下，不同用戶的文件不能用相同的名字，這樣，用戶對文件取名很難操作。因?yàn)椴煌脩粲貌煌止蚕硗粋€(gè)文件，這使得文件目錄表的結(jié)構(gòu)不是非常合理。（2）管理不便n所有用戶的

29、大量文件放在同一個(gè)目錄下，用戶管理自己的文件非常不方便。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章599.4.4 兩級目錄結(jié)構(gòu)2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章60兩級目錄結(jié)構(gòu)n二級目錄的主要優(yōu)點(diǎn)如下：通過主目錄限制，可以檢查用戶權(quán)限和文件訪問權(quán)限，避免非法用戶登錄系統(tǒng)，避免未經(jīng)授權(quán)的用戶訪問文件，實(shí)現(xiàn)了系統(tǒng)和文件的保護(hù)；不同用戶的文件可以取相同的文件名，方便了用戶使用；更有利于實(shí)現(xiàn)文件共享，對同一文件，不同的用戶，可以取不同的文件名，也可以取相同的文件名，而指向相同的文件物理地址。n兩級目錄的主要缺點(diǎn)是用戶目錄之間完全隔離，給用戶共享文件帶來不便。 2022-4-20計(jì)算機(jī)操作系統(tǒng)

30、- 第9章619.4.5 樹形目錄結(jié)構(gòu)2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章62樹形目錄結(jié)構(gòu)n樹形目錄的優(yōu)點(diǎn)有以下幾點(diǎn)：消除了文件名不能相同的限制。較好地反映了現(xiàn)實(shí)世界中數(shù)據(jù)集合的層次關(guān)系和文件之間的分支關(guān)系，用戶可以創(chuàng)建任意數(shù)量的子目錄?？梢苑奖愕膭?chuàng)建和刪除目錄。有的操作系統(tǒng)規(guī)定不能刪除非空目錄。易于規(guī)定不同層次或不同目錄的文件的不同存取權(quán)限，只要用戶有訪問許可權(quán)，就可以訪問其他用戶的目錄和文件。便于實(shí)現(xiàn)文件的保護(hù)和共享。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章639.4.6 非循環(huán)圖目錄結(jié)構(gòu)2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章64非循環(huán)圖目錄結(jié)構(gòu)n非循環(huán)圖目錄為用戶提供了更加

31、靈活的使用，也帶來了實(shí)現(xiàn)的復(fù)雜性，主要原因有以下幾方面。文件或目錄有多個(gè)父目錄，一個(gè)文件或目錄存在多個(gè)絕對路徑，因此，不同的文件名或目錄可能指的是相同的文件或目錄。如果要避免做多次備份，需要每次備份時(shí)都尋找、判斷匹配的目錄或文件是否存在，這樣時(shí)間開銷大。因?yàn)楣蚕淼哪夸浕蛭募嬖诙鄠€(gè)父目錄，非循環(huán)圖目錄結(jié)構(gòu)不能隨便刪除目錄或文件。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章659.4.7 一般圖目錄結(jié)構(gòu) n一般圖目錄結(jié)構(gòu)與非循環(huán)圖目錄結(jié)構(gòu)不同點(diǎn)在于目錄結(jié)構(gòu)中存在循環(huán)，與樹形目錄結(jié)構(gòu)不同點(diǎn)在于一般圖目錄結(jié)構(gòu)中一個(gè)子目錄或文件存在多個(gè)父目錄。 n需要解決的問題有如下兩點(diǎn)。n存在循環(huán)n嵌套刪除 202

32、2-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章669.4.8 目錄實(shí)現(xiàn)1目錄操作2目錄查詢 n線性檢索法 - 順序檢索法：檢索從文件名到索引值，從索引值到物理塊號的過程 nHash法 - 利用Hash函數(shù)（也稱為散列函數(shù)）進(jìn)行查詢。Hash函數(shù)根據(jù)需要檢索的情況和輸入值的需要進(jìn)行設(shè)計(jì)2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章67本章目錄n9.1 文件和文件的屬性 n9.2 文件結(jié)構(gòu)和文件實(shí)現(xiàn)n9.3 文件系統(tǒng)n9.4 目錄管理n9.5 磁盤存儲器管理n9.6 文件系統(tǒng)性能和可靠性n9.7 文件的共享和保護(hù)2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章68 磁盤存儲器管理n1 磁盤存儲器的物理結(jié)構(gòu) n2 磁盤

33、性能簡述n3 磁盤調(diào)度n4 磁盤高速緩存（Disk Cache）n5 提高磁盤I/O速度的其他方法n6 廉價(jià)磁盤冗余陣列2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章69 磁盤存儲器管理n1 磁盤存儲器的物理結(jié)構(gòu) n2 磁盤性能簡述n3 磁盤調(diào)度n4 磁盤高速緩存（Disk Cache）n5 提高磁盤I/O速度的其他方法n6 廉價(jià)磁盤冗余陣列n先來先服務(wù)先來先服務(wù)FCFSn最短尋道時(shí)間優(yōu)先最短尋道時(shí)間優(yōu)先SSTFSSTFn掃描算法掃描算法SCANn循環(huán)掃描算法循環(huán)掃描算法CSCANnN-Step-SCANnFSCAN2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章70磁道磁道扇區(qū)扇區(qū)磁盤結(jié)構(gòu)磁盤結(jié)構(gòu)20

34、22-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章71柱面柱面扇區(qū)扇區(qū)磁臂磁臂磁頭磁頭2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章72磁盤存儲器管理的主要任務(wù)n為文件分配存儲空間n合理地組織文件地存儲方式，以提高訪問速度n提高磁盤存儲空間地利用率n提高磁盤I/O速度，改善文件性能n確保文件系統(tǒng)的可靠性（備份） 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章739.5.3 磁盤格式化 n數(shù)據(jù)組織和格式 磁盤的格式化磁盤的格式化2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章74磁盤的類型n磁盤的類型n固定頭磁盤：這種磁盤在每條磁道上都有一讀/寫磁頭，所有的磁頭都被裝在一剛性磁臂中。通過這些磁頭可訪問所有各磁道，并進(jìn)行并

35、行讀/寫，有效地提高了磁盤的I/O速度。這種結(jié)構(gòu)的磁盤主要用于大容量磁盤上。n移動頭磁盤：每一個(gè)盤面僅配有一個(gè)磁頭，也被裝入磁臂中。為能訪問該盤面上的所有磁道，該磁頭必須能移動以進(jìn)行尋道?？梢姡苿哟蓬^僅能以串行方式讀/寫，致使其I/O速度較慢；但由于其結(jié)構(gòu)簡單，故仍廣泛應(yīng)用于中小型磁盤設(shè)備中。2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章759.5.4 磁盤的訪問時(shí)間n磁盤訪問時(shí)間：n尋道時(shí)間： 這是指把磁臂(磁頭)移動到指定磁道上所經(jīng)歷的時(shí)間。該時(shí)間是啟動磁臂的時(shí)間s與磁頭移動n條磁道所花費(fèi)的時(shí)間之和，即Ts=mn+s 其中，m是一常數(shù)，與磁盤驅(qū)動器的速度有關(guān)，對一般磁盤，m = 0.2；對高

36、速磁盤，m0.1,磁臂的啟動時(shí)間約為2ms。這樣，對一般的溫盤，其尋道時(shí)間將隨尋道距離的增加而增大，大體上是530 ms。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章76磁盤的訪問時(shí)間n磁盤訪問時(shí)間：n旋轉(zhuǎn)延遲時(shí)間T： 這是指定扇區(qū)移動到磁頭下面所經(jīng)歷的時(shí)間。對于硬盤，典型的旋轉(zhuǎn)速度大多為5400 r/min，每轉(zhuǎn)需時(shí)11.1 ms，平均旋轉(zhuǎn)延遲時(shí)間T為5.55 ms；對于軟盤，其旋轉(zhuǎn)速度為300 r/min或600 r/min，這樣，平均T為50100 ms。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章77磁盤的訪問時(shí)間n磁盤訪問時(shí)間：n傳輸時(shí)間Tt： 把數(shù)據(jù)從磁盤讀出或向磁盤寫入數(shù)據(jù)所經(jīng)歷

37、的時(shí)間。Tt的大小與每次所讀/寫的字節(jié)數(shù)b和旋轉(zhuǎn)速度有關(guān)： 其中， b：讀寫字節(jié)數(shù) N：每道上的字節(jié)數(shù)其中，其中，r r為磁盤每秒鐘的轉(zhuǎn)數(shù)；為磁盤每秒鐘的轉(zhuǎn)數(shù)；N N為為一條磁道上的字節(jié)數(shù)，一條磁道上的字節(jié)數(shù)， 當(dāng)一次讀當(dāng)一次讀/ /寫的字節(jié)數(shù)相當(dāng)于半條磁道上的字寫的字節(jié)數(shù)相當(dāng)于半條磁道上的字節(jié)數(shù)時(shí)，節(jié)數(shù)時(shí)，TtTt與與TT相同，相同，2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章78磁盤的訪問時(shí)間n磁盤訪問時(shí)間： r為磁盤每秒鐘的轉(zhuǎn)數(shù)；N為一條磁道上的字節(jié)數(shù)，當(dāng)一次讀/寫的字節(jié)數(shù)相當(dāng)于半條磁道上的字節(jié)數(shù)時(shí)，Tt與T相同，因此，可將訪問時(shí)間Ta表示為：2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章79

38、磁盤的訪問時(shí)間n對”磁盤訪問時(shí)間”的分析： 磁盤的尋道時(shí)間越長、磁盤訪問時(shí)間越長；磁盤的轉(zhuǎn)數(shù)越大，磁盤訪問時(shí)間越短；一次讀寫一條磁道上的字節(jié)數(shù)越多，磁盤的訪問時(shí)間越長。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章809.5.5 磁盤調(diào)度算法n目標(biāo)：減少尋道時(shí)間n典型算法nFCFS（First Come First Serve）n特點(diǎn)：簡單，尋道時(shí)間長，相當(dāng)于隨機(jī)訪問模式。nSSTF（最短尋道優(yōu)先）n掃描算法n1.進(jìn)程“饑餓現(xiàn)象” SSTF存在。n2.SCAN算法： 在移動方向固定的情況下采用了SSTF，以避免饑餓現(xiàn)象 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章81 FCFS調(diào)度算法 SSTF調(diào)

39、度算法100道開始道開始被訪問的下一被訪問的下一個(gè)磁道個(gè)磁道移動距離移動距離5545583391918219072160701501038112184146平均尋道長度：平均尋道長度：55.3100道開始道開始被訪問的下一被訪問的下一個(gè)磁道個(gè)磁道移動距離移動距離90105832553391638118201501321601018424平均尋道長度：平均尋道長度：27.52022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章82磁盤調(diào)度算法n進(jìn)程“饑餓”現(xiàn)象nSSTF算法雖然能獲得較好的尋道性能， 但卻可能導(dǎo)致某個(gè)進(jìn)程發(fā)生“饑餓”(Starvation)現(xiàn)象。因?yàn)橹灰粩嘤行逻M(jìn)程的請求到達(dá)，且其所要訪問的

40、磁道與磁頭當(dāng)前所在磁道的距離較近，這種新進(jìn)程的I/O請求必須優(yōu)先滿足。對SSTF算法略加修改后所形成的SCAN算法，即可防止老進(jìn)程出現(xiàn)“饑餓”現(xiàn)象。引入掃描算法（引入掃描算法（SCANSCAN）2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章83磁盤調(diào)度算法nSCAN算法n考慮要訪問的磁道與當(dāng)前磁道的距離；n考慮磁頭當(dāng)前的移動方向n下一個(gè)訪問對象n要訪問的磁道在當(dāng)前磁道以外，距離最近n自里向外訪問，直到?jīng)]有更外的磁道訪問時(shí)，將磁臂換為自外向里移動。n電梯調(diào)度算法2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章84磁盤調(diào)度算法nCSCAN算法n對SCAN的改進(jìn)；n磁頭始終按照一個(gè)方向移動2022-4-20計(jì)

41、算機(jī)操作系統(tǒng)- 第9章85 SCAN調(diào)度算法 CSCAN調(diào)度算法100道開始，磁道增加方向道開始，磁道增加方向被訪問的下一被訪問的下一個(gè)磁道個(gè)磁道移動距離移動距離1505016010184249094583255339163811820平均尋道長度：平均尋道長度：27.8100道開始道開始被訪問的下一被訪問的下一個(gè)磁道個(gè)磁道移動距離移動距離15050160101842418166382039155165839032平均尋道長度：平均尋道長度：35.82022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章86磁盤調(diào)度算法nNStepSCAN算法n粘臂現(xiàn)象：連續(xù)對某磁道訪問引起的壟斷訪問。n解決方案：n將磁盤

42、請求隊(duì)列分為長為N的子隊(duì)列m個(gè)；n磁盤調(diào)度將按FCFS算法依次處理這些子隊(duì)列，而每處理一個(gè)隊(duì)列時(shí)又是按SCAN算法，對一個(gè)隊(duì)列處理完后，再處理其他隊(duì)列。n當(dāng)正在處理某子隊(duì)列時(shí)，如果又出現(xiàn)新的磁盤I/O請求，便將新請求進(jìn)程放入其他隊(duì)列，這樣就可避免出現(xiàn)粘著現(xiàn)象。n當(dāng)N值取得很大時(shí)，會使N步掃描法的性能接近于SCAN算法的性能；當(dāng)N=1時(shí)， N步SCAN算法便蛻化為FCFS算法。2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章87磁盤調(diào)度算法nFSCAN算法nFSCAN算法實(shí)質(zhì)上是N步SCAN算法的簡化；n即FSCAN只將磁盤請求隊(duì)列分成兩個(gè)子隊(duì)列；n一個(gè)是由當(dāng)前所有請求磁盤I/O的進(jìn)程形成的隊(duì)列，由磁

43、盤調(diào)度按SCAN算法進(jìn)行處理；n在掃描期間，將新出現(xiàn)的所有請求磁盤I/O的進(jìn)程，放入另一個(gè)等待處理的請求隊(duì)列；n這樣，所有的新請求都將被推遲到下一次掃描時(shí)處理。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章88課堂練習(xí)n設(shè)有100個(gè)磁道，訪問序列如下： 23， 5， 98， 14， 66， 25， 78， 34， 66， 74，56， 87， 12， 39， 71， 49， 58 當(dāng)前磁頭在50道，上次訪問的磁道是18道。 請分別給出FCFS、SSTF、SCAN、CSCAN算法計(jì)算出平均尋道長度。2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章899.5.6 磁盤的分配和回收n解決如何為新創(chuàng)建的文件分

44、配磁盤存儲空間的問題。 n連續(xù)分配: 將文件連續(xù)順序存放在磁盤空間。n優(yōu)點(diǎn)：順序訪問時(shí)磁頭移動距離小，文件查找速度快，管理簡單。n要求文件長度固定，需要預(yù)先知道文件長度，不能適應(yīng)文件自動增長。n造成磁盤空間存在大量“碎片”，造成空間浪費(fèi)。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章90磁盤的分配和回收非連續(xù)分配：n把文件分割成固定大小的頁面，同樣將磁盤空間劃分為磁盤塊。n適應(yīng)文件的動態(tài)增長和收縮n磁盤空間的管理效率高 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章91磁盤的分配和回收磁盤塊的大小對系統(tǒng)性能有很大的影響n磁盤塊劃分過大 每個(gè)文件產(chǎn)生的“碎片”大，磁盤空間的浪費(fèi)大；n磁盤塊劃分過小 一

45、個(gè)文件由多個(gè)磁盤塊組成，訪問一個(gè)文件需要多次訪問磁盤塊，文件的訪問時(shí)間長。2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章92常用的磁盤塊組織形式n磁盤塊的分配和回收與磁盤塊的組織形式有關(guān)。n常用的磁盤塊組織形式有n空閑表法n空閑鏈表法n位示圖法n成組鏈接法 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章931空閑表法n空閑表法主要適合連續(xù)文件。將一個(gè)文件連續(xù)分配到磁盤存儲空間中。n系統(tǒng)通過一個(gè)空閑表管理磁盤的所有空閑區(qū)?？臻e表中包括表項(xiàng)序號、第一個(gè)空閑盤塊號、空閑區(qū)的空閑盤塊數(shù)等信息， 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章94空閑表法磁盤塊的分配和回收n根據(jù)磁盤空閑表為文件分配空閑區(qū)的方法與內(nèi)存

46、的空閑區(qū)分配方法相似n首次適應(yīng)算法、循環(huán)首次適應(yīng)算法、最佳適應(yīng)算法和最差適應(yīng)算法等n磁盤連續(xù)分配n優(yōu)點(diǎn)：尋道時(shí)間短、訪問速度快、磁盤I/O頻率較低n缺點(diǎn)：空閑表需要占用太大的存儲空間2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章95空閑表法n當(dāng)需要為一個(gè)文件分配磁盤空閑區(qū)時(shí)，系統(tǒng)首先找到空閑盤塊數(shù)適合文件大小的磁盤空閑區(qū)，將該磁盤空閑區(qū)分配給用戶進(jìn)程，并刪除該空閑區(qū)在空閑表中的記錄。n當(dāng)文件刪除，需要回收磁盤空間時(shí)，首先需要考慮該回收區(qū)是否與空閑表中的某個(gè)空閑區(qū)存在相鄰關(guān)系，以決定是否需要合并空閑區(qū)。n如果需要合并，則修改相鄰空閑區(qū)在空閑表中的信息；n如果不需要合并，則將回收的空閑區(qū)信息作為一條記

47、錄添加到空閑表中。2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章962空閑鏈表法（1）空閑鏈表n空閑鏈表分配方法屬于非連續(xù)分配方式。該分配方法需要在磁盤的每個(gè)空閑盤塊中設(shè)置一個(gè)指向下一個(gè)空閑塊的指針，指針將所有的空閑塊鏈接在一起。系統(tǒng)中保存有指向第一個(gè)空閑塊的指針。n空閑鏈有兩種形式：n空閑盤塊鏈：構(gòu)成元素是空閑盤塊n空閑盤區(qū)鏈：構(gòu)成元素是是空閑盤區(qū)2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章97空閑鏈表法（2）磁盤塊的分配和回收 系統(tǒng)中有一個(gè)指針指向第一個(gè)空閑盤塊(區(qū))，每個(gè)空閑盤塊(區(qū))中有指針，指向下一個(gè)空閑盤塊或空閑盤區(qū)。n分配：當(dāng)進(jìn)程為文件申請磁盤空間時(shí)，從鏈頭取出一個(gè)并修改鏈指針。n回收

48、：當(dāng)進(jìn)程需要釋放磁盤空間時(shí)，將回收回的空閑盤塊或空閑盤區(qū)鏈接到空閑鏈上。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章98空閑鏈表法n優(yōu)點(diǎn)：適合文件動態(tài)增長和收縮n缺點(diǎn)：效率較低。回收一個(gè)磁盤塊時(shí)，需要查找空閑鏈以決定回收的空閑塊在空閑鏈中的位置，訪問磁盤的次數(shù)多。nDOS操作系統(tǒng)采用的就是該種分配方法。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章993位示圖法 （1）位示圖用若干個(gè)字節(jié)構(gòu)成一個(gè)表，表中的每一字位表示一個(gè)磁盤塊的使用情況，字位的次序與磁盤物理塊的相對次序一致。字位為“0”，表示對應(yīng)的盤塊空閑；字位為“1”時(shí)表示對應(yīng)的盤塊已分配。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章100位

49、示圖法（2）磁盤塊的分配n掃描位示圖，找到文件所需的一個(gè)或一組值為0的空閑塊；n將所找的空閑塊轉(zhuǎn)換為盤塊號。如果找到的空閑塊為第i行，第j列，則盤塊號q為： q = n (i 1) + j 其中，n表示位示圖每行的位數(shù)。n將位示圖中相應(yīng)位置的狀態(tài)改為已分配(“0”變?yōu)椤?”)n例如，從磁盤中分配一個(gè)盤塊，查位示圖，得到第1行，第2列為0，即為空閑，位示圖中有16列。則對應(yīng)位示圖的磁盤塊號q為：q = n(i 1)+ j = 16(1 1) + 2 = 22022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章101位示圖法（2）磁盤塊的回收n將回收的盤塊號轉(zhuǎn)換為位示圖中的行和列號：i = (q 1)div

50、n + 1j = (q 1)mod n + 1n修改位示圖中相應(yīng)的字位，從“1”改為“0”，表示已經(jīng)回收為空閑。2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章102位示圖法n位示圖法的主要優(yōu)點(diǎn)是：n容易得到一個(gè)或一組相鄰的空閑磁盤塊n位示圖占用的空間少，可以保存在內(nèi)存中，減少了訪問磁盤的次數(shù) n通常情況下用位示圖比用空閑表表示更節(jié)省磁盤空間 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章1034成組鏈接法n成組鏈接分配方法將空閑塊進(jìn)行分組，以組為單位進(jìn)行鏈接。n每組空閑塊中的第一塊空閑塊中有下一組空閑塊的第一個(gè)空閑塊的物理塊號和下一組中的空閑塊數(shù)n最后一組空閑塊的第一空閑塊中以“0”作為標(biāo)志結(jié)束202

51、2-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章104成組鏈接法（2）磁盤塊的分配 n系統(tǒng)總是分配超級塊空閑表中的空閑塊，直到將最后一組空間塊物理塊號復(fù)制到超級塊空閑表中，超級塊空閑表中的空閑塊分配完畢后，如果還需空閑塊則系統(tǒng)會向操作員發(fā)出警告，表明空閑塊已經(jīng)用完。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章105成組鏈接法（2）磁盤塊的回收n如果超級塊空閑表沒有滿，則回收的空閑塊被掛在超級塊中。n如果超級塊空閑表已經(jīng)滿了，內(nèi)核將原來超級塊空閑表中的所有物理塊作為一個(gè)新空閑塊組，將回收的物理塊單獨(dú)放在超級塊空閑表中，并將超級塊空閑表指針指向產(chǎn)生的新空閑塊組。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章10

52、6成組鏈接法n空閑塊以組的方式鏈接，通過一次鏈接指針能夠得到一組空閑塊而不是一個(gè)空閑塊，使用鏈接指針訪問的次數(shù)減少，節(jié)約了時(shí)間，適合磁盤空間較大的情況；n空閑塊分配借助于內(nèi)存中的超級塊空閑表進(jìn)行，分配的速度更快。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章1079.5.7 磁盤可靠性n提高磁盤可靠性的方法有磁盤容錯(cuò)技術(shù)。磁盤容錯(cuò)技術(shù)又稱為系統(tǒng)容錯(cuò)技術(shù)，共分為三級：n低級磁盤容錯(cuò)技術(shù)n中級磁盤容錯(cuò)技術(shù)n系統(tǒng)容錯(cuò)技術(shù) 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章1081低級磁盤容錯(cuò)技術(shù)主要用于預(yù)防因磁盤本身的錯(cuò)誤而導(dǎo)致的損失n（1）雙份文件目錄和文件分配表（）雙份文件目錄和文件分配表（FAT）建立雙

53、份文件目錄和文件分配表，分別放在磁盤的不同區(qū)域或不同的磁盤n（2）熱修復(fù)重定向和寫后讀校驗(yàn)）熱修復(fù)重定向和寫后讀校驗(yàn)磁盤會受到損傷，補(bǔ)救措施：n熱修復(fù)重定向（hox-fix redirection）需要寫入的數(shù)據(jù)不能寫入時(shí)，系統(tǒng)可將數(shù)據(jù)放入熱修復(fù)重定向區(qū)并進(jìn)行登記管理。n寫后讀校驗(yàn)方式（read after write verification）每次寫入磁盤數(shù)據(jù)后，立即讀出磁盤中的數(shù)據(jù)，與原數(shù)據(jù)進(jìn)行比較。如果一致，則認(rèn)為成功；否則需要重新寫入。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章1092中級磁盤容錯(cuò)技術(shù)中級磁盤容錯(cuò)技術(shù)主要用于預(yù)防磁盤驅(qū)動器或磁盤控制器出錯(cuò)而導(dǎo)致的損失。n（1）磁盤鏡像

54、（）磁盤鏡像（disk mirroring）鏡像的兩個(gè)磁盤具有完全相同的功能。系統(tǒng)每次寫入數(shù)據(jù)，都需要寫入主盤與從盤。 n（2）磁盤雙工（）磁盤雙工（disk dupluxing）兩個(gè)通道，連接兩個(gè)磁盤控制器，每個(gè)磁盤控制器掛接單獨(dú)的磁盤。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章110中級磁盤容錯(cuò)技術(shù)磁盤鏡像磁盤鏡像磁盤雙工磁盤雙工2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章1113系統(tǒng)容錯(cuò)技術(shù)系統(tǒng)容錯(cuò)技術(shù)主要用于預(yù)防計(jì)算機(jī)系統(tǒng)出錯(cuò)而導(dǎo)致的系統(tǒng)癱瘓現(xiàn)象。n（1）雙機(jī)熱備份）雙機(jī)熱備份 計(jì)算機(jī)配備兩臺完全相同的計(jì)算機(jī)系統(tǒng)，這兩臺系統(tǒng)保持鏡像關(guān)系n（2）雙機(jī)互為備份）雙機(jī)互為備份兩臺系統(tǒng)各自完成

55、自己的任務(wù)，兩臺系統(tǒng)通過網(wǎng)絡(luò)連接在一起，相互備份 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章112系統(tǒng)容錯(cuò)技術(shù)雙機(jī)熱備份雙機(jī)熱備份雙機(jī)互為備份雙機(jī)互為備份2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章1139.5.8 獨(dú)立磁盤冗余陣列（RAID） 1構(gòu)成機(jī)理 n獨(dú)立磁盤冗余陣列RAID（Redundant Array of Independent Disk）由一組磁盤陣列控制器統(tǒng)一管理，并控制一組較小容量的、獨(dú)立的、可并行的磁盤驅(qū)動器工作，是一種速度快、可靠性高、性能價(jià)格比優(yōu)的大容量外存儲磁盤子系統(tǒng)。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章114獨(dú)立磁盤冗余陣列（RAID）n獨(dú)立磁盤冗余陣列起

56、初由6級組成，后來又?jǐn)U充到8級，但是具有如下的相同之處：n都是物理磁盤驅(qū)動，可以被看成操作系統(tǒng)的單一邏輯磁盤驅(qū)動；n數(shù)據(jù)被分布存放物理驅(qū)動器陣列上；1.使用冗余磁盤保存奇偶校驗(yàn)信息，當(dāng)磁盤出現(xiàn)錯(cuò)誤時(shí)，能夠恢復(fù)數(shù)據(jù)。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章115RAID各級特點(diǎn) RAID 0級：只有并行交叉存取，無冗余能力。RAID 1級：除具有并行交叉存取外，每條數(shù)據(jù)被存儲到兩個(gè)獨(dú)立的物理磁盤上，具有磁盤鏡像功能；冗余能力通過磁盤鏡像體現(xiàn)。RAID 2級：除具有并行交叉存取外，比磁盤鏡像減少了所需要的冗余磁盤數(shù)；采用海明糾錯(cuò)，糾錯(cuò)碼按照橫跨的每個(gè)數(shù)據(jù)盤的相應(yīng)位進(jìn)行計(jì)算，并存儲在多只校驗(yàn)盤的

57、相應(yīng)位的位置，RAID 2與RAID 1一樣，價(jià)格仍然很貴。RAID 3級：仍然具有并行交叉存??；但是，無論對于多大的磁盤陣列，只使用一只冗余磁盤作為簡單的奇偶校驗(yàn)盤完成容錯(cuò)功能；價(jià)格不再那么高了。RAID 4級：仍然具有并行交叉存取，使用一只冗余磁盤作為簡單的奇偶校驗(yàn)盤完成容錯(cuò)功能；增加的功能是使用了獨(dú)立存取，每個(gè)磁盤驅(qū)動器可以獨(dú)立地工作，獨(dú)立的I/O請求可并行執(zhí)行；適合有頻繁I/O請求的應(yīng)用。RAID 5級：與RAID 4的組織形式相似，差別在于采用螺旋式把奇偶校驗(yàn)碼橫跨存放在所有的磁盤上，避免了RAID 4每次寫數(shù)據(jù)都必須讀和寫校驗(yàn)盤一次的問題，改善了系統(tǒng)性能。RAID 6級和RAID

58、7級：屬于增強(qiáng)型的RAID，RAID 6中設(shè)置了專用快速異步校驗(yàn)磁盤，具有獨(dú)立的數(shù)據(jù)訪問通路，比低級RAID性能更好，但價(jià)格高；RAID 7對RAID 6作了改進(jìn)，陣列的所有磁盤都有較高的傳輸率，性能優(yōu)異，價(jià)格很高。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章116本章目錄n9.1 文件和文件的屬性 n9.2 文件結(jié)構(gòu)和文件實(shí)現(xiàn)n9.3 文件系統(tǒng)n9.4 目錄管理n9.5 磁盤存儲器管理n9.6 文件系統(tǒng)性能和可靠性n9.7 文件的共享和保護(hù)2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章1179.6.1 磁盤高速緩存 1磁盤高速緩存的引入 n磁盤高速緩存是內(nèi)存中專門為磁盤開辟的一個(gè)單獨(dú)的存儲空間，

59、其大小固定，不受應(yīng)用程序多少的影響。n系統(tǒng)首先檢查磁盤高速緩存中是否有所需要訪問的磁盤塊。n如果有，則系統(tǒng)直接訪問磁盤高速緩存，而不需要訪問磁盤；n如果沒有，則系統(tǒng)需要從磁盤上將需要的數(shù)據(jù)讀入并存放在磁盤高速緩存以備以后訪問。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章118磁盤高速緩存n讀磁盤高速緩存中的數(shù)據(jù)有兩種形式。直接交付將用戶進(jìn)程需要的數(shù)據(jù)直接傳送到用戶進(jìn)程區(qū)。指針交付將磁盤高速緩存中的數(shù)據(jù)地址指針傳送給用戶進(jìn)程，用戶進(jìn)程通過指針訪問磁盤高速緩存中的數(shù)據(jù)。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章119磁盤高速緩存2磁盤高速緩存的形式n磁盤高速緩存以鏈接方式進(jìn)行組織，與一般的內(nèi)存空

60、閑塊的鏈接方式相同。n在沒有空閑磁盤高速緩存情況下，系統(tǒng)需要對磁盤高速緩存進(jìn)行置換，置換方法與頁面置換方法相似。n采用磁盤高速緩存需要注意寫磁盤的頻率。太長時(shí)間沒有將已經(jīng)修改過的文件塊寫回磁盤，可能導(dǎo)致系統(tǒng)崩潰后文件系統(tǒng)的不一致性。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章1209.6.2 緩沖區(qū)的提前讀與延遲寫1塊提前讀n順序文件時(shí)，需要讀第k塊文件塊，在完成第k塊文件塊讀之后，會檢查緩沖區(qū)中是否有k+1塊。如果沒有，則將第k+1塊提前讀入緩沖區(qū)中。n塊提前讀只適合順序文件，對于鏈接文件和索引文件，塊提前讀可能造成文件系統(tǒng)的性能下降。 2022-4-20計(jì)算機(jī)操作系統(tǒng)- 第9章121緩沖區(qū)