第五章 文件系統(tǒng)

1、第五章第五章 文件系統(tǒng)文件系統(tǒng)在現(xiàn)代計(jì)算機(jī)系統(tǒng)用，要用到大量的程在現(xiàn)代計(jì)算機(jī)系統(tǒng)用，要用到大量的程序和數(shù)據(jù)，因內(nèi)存容量有限，且不能長序和數(shù)據(jù)，因內(nèi)存容量有限，且不能長期保存，故而平時(shí)總是把它們以文件的期保存，故而平時(shí)總是把它們以文件的形式存放在外存中，需要時(shí)再隨時(shí)將它形式存放在外存中，需要時(shí)再隨時(shí)將它們調(diào)入內(nèi)存。們調(diào)入內(nèi)存。如果由用戶直接管理外存上的文件，需如果由用戶直接管理外存上的文件，需要用戶熟悉外存特性，了解各文件的屬要用戶熟悉外存特性，了解各文件的屬性，它們在外存上的位置，顯然用戶無性，它們在外存上的位置，顯然用戶無法承擔(dān)，因此，在操作系統(tǒng)上增加了文法承擔(dān)，因此，在操作系統(tǒng)上增加了文件

2、管理功能，即文件系統(tǒng)。件管理功能，即文件系統(tǒng)。第五章第五章 文件系統(tǒng)文件系統(tǒng)對大多數(shù)用戶來說，文件系統(tǒng)是操作系對大多數(shù)用戶來說，文件系統(tǒng)是操作系統(tǒng)中最直接可見的部分。計(jì)算機(jī)的重要統(tǒng)中最直接可見的部分。計(jì)算機(jī)的重要作用之一就是能快速處理大量信息作用之一就是能快速處理大量信息, ,從而從而信息的組織、存取和保管就成為一個(gè)極信息的組織、存取和保管就成為一個(gè)極為重要的內(nèi)容。文件系統(tǒng)是計(jì)算機(jī)組織、為重要的內(nèi)容。文件系統(tǒng)是計(jì)算機(jī)組織、存取和保存信息數(shù)據(jù)的重要手段。本章存取和保存信息數(shù)據(jù)的重要手段。本章主要討論文件的組織結(jié)構(gòu)、存取結(jié)構(gòu)、主要討論文件的組織結(jié)構(gòu)、存取結(jié)構(gòu)、保護(hù)以及文件系統(tǒng)空間管理等問題。保護(hù)以

3、及文件系統(tǒng)空間管理等問題。第五章第五章 文件系統(tǒng)文件系統(tǒng)文件結(jié)構(gòu)文件結(jié)構(gòu)文件目錄管理文件目錄管理文件存儲(chǔ)空間管理文件存儲(chǔ)空間管理文件共享與保護(hù)文件共享與保護(hù)目的與要求目的與要求：了解文件結(jié)構(gòu)，訪問方式，存：了解文件結(jié)構(gòu)，訪問方式，存儲(chǔ)結(jié)構(gòu)。掌握文件管理用的文件控制塊和儲(chǔ)結(jié)構(gòu)。掌握文件管理用的文件控制塊和文件目錄結(jié)構(gòu)。了解文件空間管理方法。文件目錄結(jié)構(gòu)。了解文件空間管理方法。重點(diǎn)與難點(diǎn)重點(diǎn)與難點(diǎn)：文件存放與訪問方式，文件目：文件存放與訪問方式，文件目錄結(jié)構(gòu)。錄結(jié)構(gòu)。第五章第五章 文件系統(tǒng)文件系統(tǒng) 為了方便使用、管理系統(tǒng)公共程序和數(shù)為了方便使用、管理系統(tǒng)公共程序和數(shù)據(jù)以及用戶自己的程序和數(shù)據(jù)而引入

4、文據(jù)以及用戶自己的程序和數(shù)據(jù)而引入文件。件。 為了對外存空間管理和對其上文件的按為了對外存空間管理和對其上文件的按名訪問而引入文件系統(tǒng)。名訪問而引入文件系統(tǒng)。第五章第五章 文件系統(tǒng)文件系統(tǒng)為什么引入文件和文件系統(tǒng)為什么引入文件和文件系統(tǒng)文件系統(tǒng)的功能文件系統(tǒng)的功能 (1) (1) 為了合理的存放文件，必需對磁盤等輔助存儲(chǔ)為了合理的存放文件，必需對磁盤等輔助存儲(chǔ)器空間器空間 ( (或稱文件空間或稱文件空間) ) 進(jìn)行統(tǒng)一管理。在用戶創(chuàng)進(jìn)行統(tǒng)一管理。在用戶創(chuàng)建新文件時(shí)為其分配空閑區(qū)，而在用戶刪除或修改建新文件時(shí)為其分配空閑區(qū)，而在用戶刪除或修改某個(gè)文件時(shí)某個(gè)文件時(shí), ,回收和調(diào)整存儲(chǔ)區(qū)?；厥蘸驼{(diào)整

5、存儲(chǔ)區(qū)。(2) (2) 實(shí)現(xiàn)按名存取，完成對存放在存儲(chǔ)設(shè)備上的文實(shí)現(xiàn)按名存取，完成對存放在存儲(chǔ)設(shè)備上的文件信息的查找。件信息的查找。(3) (3) 為了便于存放，文件在存儲(chǔ)設(shè)備上應(yīng)按一定的為了便于存放，文件在存儲(chǔ)設(shè)備上應(yīng)按一定的順序存放。這種存放方式被稱為文件的物理結(jié)構(gòu)。順序存放。這種存放方式被稱為文件的物理結(jié)構(gòu)。(4) (4) 完成文件的共享和提供保護(hù)功能。完成文件的共享和提供保護(hù)功能。5.1 5.1 文件組織結(jié)構(gòu)文件組織結(jié)構(gòu)5.1.15.1.1文件概念文件概念文件是由創(chuàng)建者所定義、具有文件名文件是由創(chuàng)建者所定義、具有文件名的一組相關(guān)的信息集合。的一組相關(guān)的信息集合。 文件的主要屬性：文件的

6、主要屬性： 文件名，文件類型，文件長度，創(chuàng)文件名，文件類型，文件長度，創(chuàng)建者，創(chuàng)建時(shí)間，修改時(shí)間，文件定建者，創(chuàng)建時(shí)間，修改時(shí)間，文件定位信息位信息 ，文件所包含的信息。，文件所包含的信息。5.1.2 5.1.2 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu) 操作系統(tǒng)感知文件信息的組織形式叫文件的邏操作系統(tǒng)感知文件信息的組織形式叫文件的邏輯結(jié)構(gòu)。它包括流式文件（無結(jié)構(gòu)文件）和記輯結(jié)構(gòu)。它包括流式文件（無結(jié)構(gòu)文件）和記錄式文件（有結(jié)構(gòu)文件）兩種，每種文件信息錄式文件（有結(jié)構(gòu)文件）兩種，每種文件信息的邏輯單位分別是字節(jié)和記錄。的邏輯單位分別是字節(jié)和記錄。 流式文件（無結(jié)構(gòu)文件）流式文件（無結(jié)構(gòu)文件）： 是指對文件

7、內(nèi)信息不再劃分單位，它是依次的一串是指對文件內(nèi)信息不再劃分單位，它是依次的一串字節(jié)流構(gòu)成的文件。字節(jié)流構(gòu)成的文件。 記錄式文件（有結(jié)構(gòu)文件）：記錄式文件（有結(jié)構(gòu)文件）： 是用戶把文件內(nèi)的信息按邏輯上獨(dú)立的含義是用戶把文件內(nèi)的信息按邏輯上獨(dú)立的含義劃分信息單位，每個(gè)單位稱為一個(gè)記錄。所劃分信息單位，每個(gè)單位稱為一個(gè)記錄。所有記錄通常都是描述一個(gè)實(shí)體集的，有著相有記錄通常都是描述一個(gè)實(shí)體集的，有著相同或不同數(shù)目的數(shù)據(jù)項(xiàng)，記錄的長度可分為同或不同數(shù)目的數(shù)據(jù)項(xiàng)，記錄的長度可分為定長和不定長記錄兩類。定長和不定長記錄兩類。 記錄是一組相關(guān)數(shù)據(jù)項(xiàng)的集合，用于描記錄是一組相關(guān)數(shù)據(jù)項(xiàng)的集合，用于描述一個(gè)對象在

8、某方面的屬性。一個(gè)記錄述一個(gè)對象在某方面的屬性。一個(gè)記錄應(yīng)包含哪些數(shù)據(jù)項(xiàng)，取決于需要描述對應(yīng)包含哪些數(shù)據(jù)項(xiàng)，取決于需要描述對象的哪個(gè)方面。象的哪個(gè)方面。一個(gè)學(xué)生，當(dāng)把他作為班上的一名學(xué)生一個(gè)學(xué)生，當(dāng)把他作為班上的一名學(xué)生時(shí)，時(shí)， 對他的描述應(yīng)使用學(xué)號、姓名、年對他的描述應(yīng)使用學(xué)號、姓名、年齡及所在系班，也可能還包括他所學(xué)過齡及所在系班，也可能還包括他所學(xué)過的課程的名稱、的課程的名稱、 成績等數(shù)據(jù)項(xiàng)。成績等數(shù)據(jù)項(xiàng)。 但若但若把學(xué)生作為一個(gè)醫(yī)療對象時(shí)，對他描述把學(xué)生作為一個(gè)醫(yī)療對象時(shí)，對他描述的數(shù)據(jù)項(xiàng)則應(yīng)使用諸如病歷號、的數(shù)據(jù)項(xiàng)則應(yīng)使用諸如病歷號、 姓名、姓名、 性別、性別、 出生年月、出生年月、

9、 身高、身高、 體重、體重、 血血壓及病史等項(xiàng)。壓及病史等項(xiàng)。顯然，對于流式的無結(jié)構(gòu)文件來說，查找文件顯然，對于流式的無結(jié)構(gòu)文件來說，查找文件中的基本信息單位，例如某個(gè)單詞，是比較困中的基本信息單位，例如某個(gè)單詞，是比較困難的。但反過來，流式的無結(jié)構(gòu)文件管理簡單，難的。但反過來，流式的無結(jié)構(gòu)文件管理簡單，用戶可以方便地對其進(jìn)行操作。所以，那些對用戶可以方便地對其進(jìn)行操作。所以，那些對基本信息單位操作不多的文件較適于采用流式基本信息單位操作不多的文件較適于采用流式的無結(jié)構(gòu)方式，例如，源程序文件、目標(biāo)代碼的無結(jié)構(gòu)方式，例如，源程序文件、目標(biāo)代碼文件等。文件等。記錄式的有結(jié)構(gòu)文件可把文件中的記錄按各

10、種記錄式的有結(jié)構(gòu)文件可把文件中的記錄按各種不同的方式排列，以便用戶對文件中的記錄進(jìn)不同的方式排列，以便用戶對文件中的記錄進(jìn)行修改、追加、查找和管理等操作，主要用于行修改、追加、查找和管理等操作，主要用于信息管理，如數(shù)據(jù)庫系統(tǒng)中。信息管理，如數(shù)據(jù)庫系統(tǒng)中。5.1.3 5.1.3 文件的物理結(jié)構(gòu)文件的物理結(jié)構(gòu) 邏輯文件在輔存的組織結(jié)構(gòu)稱為文件的物理結(jié)構(gòu)。如何邏輯文件在輔存的組織結(jié)構(gòu)稱為文件的物理結(jié)構(gòu)。如何組織它們主要依賴于文件存儲(chǔ)器的物理特性，以及用戶組織它們主要依賴于文件存儲(chǔ)器的物理特性，以及用戶對其文件的訪問方式。對其文件的訪問方式。 文件的訪問方式文件的訪問方式 順序訪問順序訪問 指用戶從文

11、件初始數(shù)據(jù)開始依次訪問文件中的信息。指用戶從文件初始數(shù)據(jù)開始依次訪問文件中的信息。經(jīng)常被順序訪問的文件應(yīng)該連續(xù)存儲(chǔ)在文件存儲(chǔ)器經(jīng)常被順序訪問的文件應(yīng)該連續(xù)存儲(chǔ)在文件存儲(chǔ)器上。操作系統(tǒng)自動(dòng)記錄文件訪問的當(dāng)前位置。上。操作系統(tǒng)自動(dòng)記錄文件訪問的當(dāng)前位置。 直接（隨機(jī)）訪問直接（隨機(jī)）訪問指用戶隨機(jī)訪問文件中的某段信息。讀指用戶隨機(jī)訪問文件中的某段信息。讀/ /寫時(shí)直接寫時(shí)直接給出要訪問數(shù)據(jù)的邏輯位置（如第幾個(gè)字節(jié)或第幾給出要訪問數(shù)據(jù)的邏輯位置（如第幾個(gè)字節(jié)或第幾個(gè)記錄）及長度，由個(gè)記錄）及長度，由OSOS將邏輯位置轉(zhuǎn)換成物理位置將邏輯位置轉(zhuǎn)換成物理位置并訪問之。并訪問之。 磁帶磁帶順序訪問設(shè)備順序

12、訪問設(shè)備要求文件順序存放于帶上。要求文件順序存放于帶上。 磁盤磁盤直接（隨機(jī)）訪問設(shè)備直接（隨機(jī)）訪問設(shè)備文件可順序、鏈接文件可順序、鏈接式或隨機(jī)（通過類似頁表的結(jié)構(gòu)訪問）存放式或隨機(jī)（通過類似頁表的結(jié)構(gòu)訪問）存放于設(shè)備上。于設(shè)備上。 5.1.3 5.1.3 文件的物理結(jié)構(gòu)文件的物理結(jié)構(gòu)為了便于存放于磁盤，文件可被等分成為了便于存放于磁盤，文件可被等分成塊塊文件系統(tǒng)將一個(gè)文件分塊存放于外存，文件系統(tǒng)將一個(gè)文件分塊存放于外存，文件控制塊將包含文件的定位信息文件控制塊將包含文件的定位信息 文件的物理結(jié)構(gòu)包括順序結(jié)構(gòu)（連續(xù)結(jié)文件的物理結(jié)構(gòu)包括順序結(jié)構(gòu)（連續(xù)結(jié)構(gòu)）、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)三種。構(gòu)）、鏈接結(jié)

13、構(gòu)、索引結(jié)構(gòu)三種。 順序結(jié)構(gòu)（連續(xù)結(jié)構(gòu)）順序結(jié)構(gòu)（連續(xù)結(jié)構(gòu)） 文件順序連續(xù)存放于文件存儲(chǔ)器上文件順序連續(xù)存放于文件存儲(chǔ)器上（如磁帶文件，光盤文件）。（如磁帶文件，光盤文件）。特點(diǎn)特點(diǎn): :實(shí)現(xiàn)簡單實(shí)現(xiàn)簡單順序訪問容易且速度快順序訪問容易且速度快要求有連續(xù)的存儲(chǔ)空間，外部碎片多要求有連續(xù)的存儲(chǔ)空間，外部碎片多必須事先知道文件的長度必須事先知道文件的長度012345678910111213141516171819202122232425262728293031文件名文件名 始址始址 塊數(shù)塊數(shù)count 0 2tr 14 3mail 19 6list 28 4f 6 2 文件目錄文件目錄countf

14、trmaillist磁盤空間磁盤空間（二）鏈接結(jié)構(gòu)（二）鏈接結(jié)構(gòu) 鏈接結(jié)構(gòu)鏈接結(jié)構(gòu)文件不連續(xù)地存放于文件存儲(chǔ)器上，但使文件不連續(xù)地存放于文件存儲(chǔ)器上，但使用指針按文件數(shù)據(jù)順序?qū)⑵滏溄悠饋?。用指針按文件?shù)據(jù)順序?qū)⑵滏溄悠饋怼Ｌ攸c(diǎn)：特點(diǎn)：提高了磁盤空間利用率提高了磁盤空間利用率, ,不存在外部碎片問不存在外部碎片問題；題；文件操作靈活（添加、刪除等），有利于文件操作靈活（添加、刪除等），有利于文件長度動(dòng)態(tài)變化。文件長度動(dòng)態(tài)變化。（二）鏈接結(jié)構(gòu)（二）鏈接結(jié)構(gòu)1 1、隱式鏈接、隱式鏈接文件名文件名 始址始址 末址末址jeep 9 25文件目錄文件目錄01234567891011121314151617

15、181920212223242526272829303111016-125磁盤空間磁盤空間隱式鏈接問題：隱式鏈接問題： 只適合順序訪問，對隨機(jī)訪問是低效的。只適合順序訪問，對隨機(jī)訪問是低效的。 可靠性差，因?yàn)橹灰渲腥魏我粋€(gè)指針出現(xiàn)可靠性差，因?yàn)橹灰渲腥魏我粋€(gè)指針出現(xiàn)問題，都會(huì)導(dǎo)致整個(gè)鏈斷開。問題，都會(huì)導(dǎo)致整個(gè)鏈斷開。 指針占用空間。指針占用空間。2. 2. 顯式鏈接顯式鏈接 把用于鏈接文件各物理塊的指針，顯式把用于鏈接文件各物理塊的指針，顯式地存放在內(nèi)存的一張鏈接表中。該表對地存放在內(nèi)存的一張鏈接表中。該表對應(yīng)整個(gè)磁盤，表的序號是物理盤塊號。應(yīng)整個(gè)磁盤，表的序號是物理盤塊號。在每個(gè)表項(xiàng)中存

16、放鏈接指針，即下一個(gè)在每個(gè)表項(xiàng)中存放鏈接指針，即下一個(gè)盤塊號。我們將該表稱為文件分配表盤塊號。我們將該表稱為文件分配表FAT。大大減少了訪問磁盤的次數(shù)，提高了檢大大減少了訪問磁盤的次數(shù)，提高了檢索速度。索速度。2. 2. 顯式鏈接顯式鏈接 012345物 理 塊 號2FCBFAT04516EOF11105EOF0123456789FATFCB A4FCB B9（三）索引結(jié)構(gòu)（三）索引結(jié)構(gòu)鏈接分配方式雖然解決了連續(xù)分配方式鏈接分配方式雖然解決了連續(xù)分配方式所存在的問題，所存在的問題， 但又出現(xiàn)了另外兩個(gè)問但又出現(xiàn)了另外兩個(gè)問題，題， 即：即： (1) 不能支持高效的直接存取。要對一個(gè)不能支持高效

17、的直接存取。要對一個(gè)較大的文件進(jìn)行直接存取，須首先在較大的文件進(jìn)行直接存取，須首先在FAT中順序地查找許多盤塊號。中順序地查找許多盤塊號。 (2) FAT需占用較大的內(nèi)存空間。需占用較大的內(nèi)存空間。（三）索引結(jié)構(gòu)（三）索引結(jié)構(gòu)索引結(jié)構(gòu)索引結(jié)構(gòu)文件不連續(xù)存放于文件存儲(chǔ)器上，文件不連續(xù)存放于文件存儲(chǔ)器上，使用一張索引表來定位文件中的數(shù)使用一張索引表來定位文件中的數(shù)據(jù)（類比頁表）據(jù)（類比頁表）特點(diǎn)：既能順序存取，又能隨機(jī)存取，特點(diǎn)：既能順序存取，又能隨機(jī)存取，支持文件長度動(dòng)態(tài)變化，外存利用率高，支持文件長度動(dòng)態(tài)變化，外存利用率高，但索引表需占額外空間。但索引表需占額外空間。單級索引結(jié)構(gòu)：單級索引結(jié)構(gòu)

18、： 為每個(gè)文件分配一個(gè)索引表，一個(gè)索引表就為每個(gè)文件分配一個(gè)索引表，一個(gè)索引表就是磁盤塊地址數(shù)組是磁盤塊地址數(shù)組, ,其中第其中第i i個(gè)條目指向文件個(gè)條目指向文件的第的第i i塊塊多級索引結(jié)構(gòu)：多級索引結(jié)構(gòu)：混合索引結(jié)構(gòu)：混合索引結(jié)構(gòu)：1 1、單級索引結(jié)構(gòu)、單級索引結(jié)構(gòu)012345678910111213141516171819202122232425262728293031文件名文件名 索引表地址索引表地址文件目錄文件目錄Jeep 19 917 11025 19文件jeep的單級索引表問題：問題：每建立一個(gè)文件，分配一個(gè)索引表，占每建立一個(gè)文件，分配一個(gè)索引表，占用較多的外存空間。用較多的

19、外存空間。對于中小文件，一個(gè)索引表需要占用一對于中小文件，一個(gè)索引表需要占用一個(gè)盤塊，空間浪費(fèi)。個(gè)盤塊，空間浪費(fèi)。2. 2. 多級索引結(jié)構(gòu)多級索引結(jié)構(gòu)3. 3. 混合索引結(jié)構(gòu)混合索引結(jié)構(gòu) 將多種索引方式相結(jié)合而形成的一種分配將多種索引方式相結(jié)合而形成的一種分配方式。方式。 例如，系統(tǒng)中即采用了直接地址，有采用例如，系統(tǒng)中即采用了直接地址，有采用了一級索引方式，或兩級索引方式，甚至了一級索引方式，或兩級索引方式，甚至還采用了三級索引。還采用了三級索引。 這種方式在這種方式在UNIX系統(tǒng)中采用。系統(tǒng)中采用。 在在Unix System V的索引點(diǎn)中，共設(shè)置了的索引點(diǎn)中，共設(shè)置了13個(gè)地址項(xiàng)，即個(gè)地

20、址項(xiàng)，即iaddr(0)iaddr(12)。它們。它們把所有的地址項(xiàng)分成兩類，即直接地址和把所有的地址項(xiàng)分成兩類，即直接地址和間接地址。間接地址。modeowners (2)time stamps (3)sizeblock counti.addr (0)i.addr (1)direct blockssingle indirectdouble indirecttriple indirectdatadatadatadatadatadatadatadatadatadata(1) (1) 直接地址直接地址 為了提高對文件的檢索速度，為了提高對文件的檢索速度， 在索引結(jié)點(diǎn)在索引結(jié)點(diǎn)中 可 設(shè) 置中 可

21、設(shè) 置 1 01 0 個(gè) 直 接 地 址 項(xiàng) ， 即 用個(gè) 直 接 地 址 項(xiàng) ， 即 用iaddr(0)iaddr(9)iaddr(0)iaddr(9)來存放直接地址。來存放直接地址。 換換言之，在這里的每項(xiàng)中所存放的是該文件言之，在這里的每項(xiàng)中所存放的是該文件數(shù)據(jù)的塊號。假如每個(gè)塊的大小為數(shù)據(jù)的塊號。假如每個(gè)塊的大小為 4 KB4 KB，當(dāng)文件不大于當(dāng)文件不大于40 KB40 KB時(shí)，便可直接從索引時(shí)，便可直接從索引結(jié)點(diǎn)中讀出該文件的全部塊號。結(jié)點(diǎn)中讀出該文件的全部塊號。(2) (2) 一次間接地址一次間接地址 對于大、對于大、 中型文件，中型文件， 只采用直接地址是只采用直接地址是不現(xiàn)實(shí)

22、的。不現(xiàn)實(shí)的。 為此，可再利用索引結(jié)點(diǎn)中為此，可再利用索引結(jié)點(diǎn)中的地址項(xiàng)的地址項(xiàng)iaddr(10)iaddr(10)來提供一次間接地址。來提供一次間接地址。這種方式的實(shí)質(zhì)就是一級索引分配方式。這種方式的實(shí)質(zhì)就是一級索引分配方式。圖中的一次間址塊也就是索引塊，系統(tǒng)將圖中的一次間址塊也就是索引塊，系統(tǒng)將分配給文件的多個(gè)塊號記入其中。在一次分配給文件的多個(gè)塊號記入其中。在一次間址塊中可存放間址塊中可存放1K1K個(gè)塊號，個(gè)塊號， 因而允許文因而允許文件長達(dá)件長達(dá)4 MB4 MB。 (3) (3) 多次間接地址。多次間接地址。 當(dāng)文件長度大于當(dāng)文件長度大于4 MB+40 KB4 MB+40 KB時(shí)時(shí)(

23、(一次間址與一次間址與1010個(gè)直接地址項(xiàng)個(gè)直接地址項(xiàng)) )， 系統(tǒng)還須采用二次間系統(tǒng)還須采用二次間址分配方式。這時(shí)，用地址項(xiàng)址分配方式。這時(shí)，用地址項(xiàng)iaddr(11)iaddr(11)提提供二次間接地址。該方式的實(shí)質(zhì)是兩級索供二次間接地址。該方式的實(shí)質(zhì)是兩級索引分配方式。系統(tǒng)此時(shí)是在二次間址塊中引分配方式。系統(tǒng)此時(shí)是在二次間址塊中記入所有一次間址塊的塊號。在采用二次記入所有一次間址塊的塊號。在采用二次間址方式時(shí)，文件最大長度可達(dá)間址方式時(shí)，文件最大長度可達(dá)4 GB4 GB。 同同理，地址項(xiàng)理，地址項(xiàng)iaddr(12)iaddr(12)作為三次間接地址，作為三次間接地址， 其所允許的文件最大

24、長度可達(dá)其所允許的文件最大長度可達(dá)4 TB4 TB。 習(xí)題一設(shè)文件索引節(jié)點(diǎn)有設(shè)文件索引節(jié)點(diǎn)有8 8個(gè)索引項(xiàng)，其中個(gè)索引項(xiàng)，其中4 4個(gè)個(gè)地址項(xiàng)是直接地址索引，地址項(xiàng)是直接地址索引，3 3個(gè)地址項(xiàng)是一個(gè)地址項(xiàng)是一級間接地址索引，級間接地址索引，1 1個(gè)地址項(xiàng)是二級間接個(gè)地址項(xiàng)是二級間接地址索引。每個(gè)地址項(xiàng)大小為地址索引。每個(gè)地址項(xiàng)大小為4 4個(gè)字節(jié)，個(gè)字節(jié)，若磁盤索引塊和磁盤數(shù)據(jù)塊大小均為若磁盤索引塊和磁盤數(shù)據(jù)塊大小均為256256字節(jié)，則可表示的單個(gè)文件的最大長度字節(jié)，則可表示的單個(gè)文件的最大長度為多少為多少KB?KB? 習(xí)題二普通文件采用普通文件采用UNIXUNIX三級索引結(jié)構(gòu)，即文件控制三

25、級索引結(jié)構(gòu)，即文件控制塊中給出塊中給出1313個(gè)磁盤地址，前個(gè)磁盤地址，前1010個(gè)磁盤地址指出個(gè)磁盤地址指出文件前文件前1010塊的物理地址，第塊的物理地址，第1111個(gè)磁盤地址指向個(gè)磁盤地址指向一級索引表，一級索引表給出一級索引表，一級索引表給出256256個(gè)磁盤地址，個(gè)磁盤地址，即指出該文件第即指出該文件第1111塊至第塊至第266266塊的物理地址；塊的物理地址；第第1212個(gè)磁盤地址指向二級索引表，二級索引表個(gè)磁盤地址指向二級索引表，二級索引表中指出中指出256256個(gè)一級索引表的地址；第個(gè)一級索引表的地址；第1313個(gè)磁盤個(gè)磁盤地址指向三級索引表，三級索引表中指出地址指向三級索引表

26、，三級索引表中指出256256個(gè)二級索引表的地址。個(gè)二級索引表的地址。文件文件K K的第的第72667266塊需要啟動(dòng)幾級索引？塊需要啟動(dòng)幾級索引？ 習(xí)題三普通文件采用普通文件采用UNIXUNIX三級索引結(jié)構(gòu)，即文件控制三級索引結(jié)構(gòu)，即文件控制塊中給出塊中給出1313個(gè)磁盤地址，前個(gè)磁盤地址，前1010個(gè)磁盤地址指出個(gè)磁盤地址指出文件前文件前1010塊的物理地址，第塊的物理地址，第1111個(gè)磁盤地址指向個(gè)磁盤地址指向一級索引表，一級索引表給出一級索引表，一級索引表給出256256個(gè)磁盤地址，個(gè)磁盤地址，即指出該文件第即指出該文件第1111塊至第塊至第266266塊的物理地址；塊的物理地址；第第

27、1212個(gè)磁盤地址指向二級索引表，二級索引表個(gè)磁盤地址指向二級索引表，二級索引表中指出中指出256256個(gè)一級索引表的地址；第個(gè)一級索引表的地址；第1313個(gè)磁盤個(gè)磁盤地址指向三級索引表，三級索引表中指出地址指向三級索引表，三級索引表中指出256256個(gè)二級索引表的地址。個(gè)二級索引表的地址。訪問文件訪問文件K K的第的第72667266塊需要啟動(dòng)幾次磁盤？塊需要啟動(dòng)幾次磁盤？（假設(shè)已經(jīng)找到了（假設(shè)已經(jīng)找到了K K文件的地址）文件的地址） 5.2 5.2 文件目錄管理文件目錄管理 建立文件系統(tǒng)的作用在于對文件信息的建立文件系統(tǒng)的作用在于對文件信息的“按名存取按名存取”，力求查找簡便，減少查找，力

28、求查找簡便，減少查找時(shí)間。為了能對這些文件實(shí)施有效的管理，時(shí)間。為了能對這些文件實(shí)施有效的管理，必須對它們加以妥善組織，這主要是通過必須對它們加以妥善組織，這主要是通過文件目錄實(shí)現(xiàn)的。文件目錄是一種數(shù)據(jù)結(jié)文件目錄實(shí)現(xiàn)的。文件目錄是一種數(shù)據(jù)結(jié)構(gòu)，用于標(biāo)識系統(tǒng)中的文件及其物理地址，構(gòu)，用于標(biāo)識系統(tǒng)中的文件及其物理地址，供檢索時(shí)使用。供檢索時(shí)使用。對目錄管理的要求如下：對目錄管理的要求如下：實(shí)現(xiàn)實(shí)現(xiàn)“按名存取按名存取”。 提高對目錄的檢索速度。提高對目錄的檢索速度。 文件共享。文件共享。 允許文件重名。允許文件重名。1 1、文件控制塊、文件控制塊 為了能對一個(gè)文件進(jìn)行正確的存取，必須為文件設(shè)置用為了

29、能對一個(gè)文件進(jìn)行正確的存取，必須為文件設(shè)置用于描述和控制文件的數(shù)據(jù)結(jié)構(gòu)，即文件控制塊。于描述和控制文件的數(shù)據(jù)結(jié)構(gòu)，即文件控制塊。 文件控制塊（文件控制塊（FCBFCB）的主要內(nèi)容的主要內(nèi)容 文件名文件名 創(chuàng)建者創(chuàng)建者 存放方式：說明該文件在輔存的結(jié)構(gòu)，如順序結(jié)構(gòu)、存放方式：說明該文件在輔存的結(jié)構(gòu)，如順序結(jié)構(gòu)、索引結(jié)構(gòu)。索引結(jié)構(gòu)。 文件物理位置信息：具體說明文件在輔存的物理位置文件物理位置信息：具體說明文件在輔存的物理位置和范圍，對于不同的物理結(jié)構(gòu)，應(yīng)做不同的說明，如和范圍，對于不同的物理結(jié)構(gòu)，應(yīng)做不同的說明，如索引表。索引表。 創(chuàng)建、修改時(shí)間、保存時(shí)間創(chuàng)建、修改時(shí)間、保存時(shí)間 口令：用于對文件

30、訪問進(jìn)行驗(yàn)證口令：用于對文件訪問進(jìn)行驗(yàn)證 操作限制：如讀、寫、執(zhí)行權(quán)限說明操作限制：如讀、寫、執(zhí)行權(quán)限說明文件目錄文件目錄：把所有的把所有的FCBFCB組織在一起，就組織在一起，就構(gòu)成了文件目錄，即文件控制塊的有序構(gòu)成了文件目錄，即文件控制塊的有序集合集合目錄項(xiàng)：構(gòu)成文件目錄的項(xiàng)目，即目錄項(xiàng)：構(gòu)成文件目錄的項(xiàng)目，即FCBFCB目錄文件：為了實(shí)現(xiàn)對文件目錄的管理，目錄文件：為了實(shí)現(xiàn)對文件目錄的管理，通常將文件目錄以文件的形式保存在外通常將文件目錄以文件的形式保存在外存，這個(gè)文件就叫目錄文件存，這個(gè)文件就叫目錄文件目錄主要是為了系統(tǒng)快速實(shí)現(xiàn)目錄主要是為了系統(tǒng)快速實(shí)現(xiàn)“按名存按名存取取”而引入的，查

31、目錄是文件系統(tǒng)最頻而引入的，查目錄是文件系統(tǒng)最頻繁的操作，因此目錄的合理組織很重要繁的操作，因此目錄的合理組織很重要. .文件目錄通常是存放在磁盤上的，當(dāng)文文件目錄通常是存放在磁盤上的，當(dāng)文件很多時(shí)，文件目錄可能要占用大量的件很多時(shí)，文件目錄可能要占用大量的盤塊。在查找目錄的過程中，先將存放盤塊。在查找目錄的過程中，先將存放目錄文件的第一個(gè)盤塊中的目錄調(diào)入內(nèi)目錄文件的第一個(gè)盤塊中的目錄調(diào)入內(nèi)存，然后把用戶所給定的文件名與目錄存，然后把用戶所給定的文件名與目錄項(xiàng)中的文件名逐一比較。若未找到指定項(xiàng)中的文件名逐一比較。若未找到指定文件，便再將下一個(gè)盤塊中的目錄項(xiàng)調(diào)文件，便再將下一個(gè)盤塊中的目錄項(xiàng)調(diào)入

32、內(nèi)存。入內(nèi)存。在檢索目錄文件的過程中，只用到了文在檢索目錄文件的過程中，只用到了文件名，僅當(dāng)找到了一個(gè)目錄項(xiàng)時(shí)，才需件名，僅當(dāng)找到了一個(gè)目錄項(xiàng)時(shí)，才需從該目錄項(xiàng)中讀出該文件的物理地址。從該目錄項(xiàng)中讀出該文件的物理地址。而其它一些對文件進(jìn)行描述的信息，在而其它一些對文件進(jìn)行描述的信息，在檢索目錄時(shí)一概不用。顯然這些信息在檢索目錄時(shí)一概不用。顯然這些信息在檢索目錄時(shí)不需要調(diào)入內(nèi)存。檢索目錄時(shí)不需要調(diào)入內(nèi)存。采用將文件名與文件描述信息分開的辦采用將文件名與文件描述信息分開的辦法，即形成索引結(jié)點(diǎn)。法，即形成索引結(jié)點(diǎn)。2. 2. 索引結(jié)點(diǎn)索引結(jié)點(diǎn)UNIX的文件目錄的文件目錄 文件名文件名索引結(jié)點(diǎn)編號索引

33、結(jié)點(diǎn)編號文件名文件名1文件名文件名2使文件描述信息單獨(dú)形成一個(gè)稱為索引使文件描述信息單獨(dú)形成一個(gè)稱為索引結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，簡稱為結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，簡稱為i i結(jié)點(diǎn)。結(jié)點(diǎn)。5.2.15.2.1一級目錄結(jié)構(gòu)一級目錄結(jié)構(gòu)在整個(gè)文件系統(tǒng)中只建立一張目錄表，在整個(gè)文件系統(tǒng)中只建立一張目錄表，每個(gè)文件占用一個(gè)目錄項(xiàng)。每個(gè)文件占用一個(gè)目錄項(xiàng)。每個(gè)目錄項(xiàng)就是一個(gè)文件的每個(gè)目錄項(xiàng)就是一個(gè)文件的FCBFCB。目錄表中包含所有文件的目錄表中包含所有文件的FCBFCB。當(dāng)要訪問當(dāng)要訪問一個(gè)文件時(shí)，先按文件名在目錄中找到一個(gè)文件時(shí)，先按文件名在目錄中找到對應(yīng)的文件對應(yīng)的文件FCBFCB。一級目錄結(jié)構(gòu)示意圖一級目錄結(jié)構(gòu)示意圖

34、FCB1 FCB2 FCB3 FCBn 文件 1 文件 2 文件 3 文件 n 優(yōu)點(diǎn)：優(yōu)點(diǎn)：簡單，易實(shí)現(xiàn)簡單，易實(shí)現(xiàn)缺點(diǎn)：缺點(diǎn)：限制了用戶對文件的命名限制了用戶對文件的命名（存在（存在“命名沖命名沖突突”問題）問題）檢索文件時(shí)平均檢索時(shí)間長檢索文件時(shí)平均檢索時(shí)間長不適于多用戶系統(tǒng)不適于多用戶系統(tǒng)5.2.25.2.2二級目錄結(jié)構(gòu)二級目錄結(jié)構(gòu) 為克服單級目錄結(jié)構(gòu)存在的命名沖突問題，為克服單級目錄結(jié)構(gòu)存在的命名沖突問題，并提高對目錄文件的檢索速度而引入。并提高對目錄文件的檢索速度而引入。目錄分為兩級：目錄分為兩級：一級稱為一級稱為主文件目錄主文件目錄MFDMFD ，給出用戶名，用戶子目錄所在的物理位

35、置；給出用戶名，用戶子目錄所在的物理位置；二級稱為二級稱為用戶文件目錄用戶文件目錄UFDUFD （又稱用戶子（又稱用戶子目錄），給出該用戶所有文件的目錄），給出該用戶所有文件的FCBFCB。每。每個(gè)個(gè)UFDUFD在在MFDMFD中均設(shè)置一項(xiàng)，用以描述中均設(shè)置一項(xiàng)，用以描述UFDUFD的用戶名及其物理位置。的用戶名及其物理位置。特點(diǎn)：解決了文件的重名問題特點(diǎn)：解決了文件的重名問題; ; 可用于多用戶系統(tǒng)可用于多用戶系統(tǒng); ; 順序查找時(shí)間降低。順序查找時(shí)間降低。FCB1FCB2FCB1FCB2 路徑名路徑名 將用戶名與文件名連到一起組成路將用戶名與文件名連到一起組成路經(jīng)名。例如：經(jīng)名。例如：/

36、/luoyu/test.cluoyu/test.c二級目錄解決了將不同用戶文件分開存二級目錄解決了將不同用戶文件分開存放并建目錄進(jìn)行索引的問題，但是如果放并建目錄進(jìn)行索引的問題，但是如果用戶文件太多，在一個(gè)子目錄下存放用用戶文件太多，在一個(gè)子目錄下存放用戶所有文件同樣也會(huì)存在戶所有文件同樣也會(huì)存在“重名重名”問題，問題，因此引入了樹形目錄（多級目錄）。因此引入了樹形目錄（多級目錄）。5.2.35.2.3樹形目錄結(jié)構(gòu)（多級目錄結(jié)構(gòu)）樹形目錄結(jié)構(gòu)（多級目錄結(jié)構(gòu)）對二級目錄簡單擴(kuò)充可得三級或三級以上的多對二級目錄簡單擴(kuò)充可得三級或三級以上的多級目錄結(jié)構(gòu)，即允許每一級目錄中的級目錄結(jié)構(gòu)，即允許每一級目

37、錄中的FCBFCB要么指要么指向文件，要么指向下一級子目錄即可。這是當(dāng)向文件，要么指向下一級子目錄即可。這是當(dāng)今主流今主流OSOS普遍采用的目錄結(jié)構(gòu)。普遍采用的目錄結(jié)構(gòu)。樹形目錄中有根目錄，樹中的每個(gè)文件具有唯樹形目錄中有根目錄，樹中的每個(gè)文件具有唯一的路徑名。一的路徑名。優(yōu)點(diǎn)優(yōu)點(diǎn)： 解決了命名沖突問題解決了命名沖突問題 層次結(jié)構(gòu)清晰，便于對文件分類管理層次結(jié)構(gòu)清晰，便于對文件分類管理 缺點(diǎn)：缺點(diǎn)：查找一個(gè)查找一個(gè)文件文件按按路徑名路徑名逐層檢查，由于逐層檢查，由于每個(gè)文件都放在外存，多次訪盤影響速度每個(gè)文件都放在外存，多次訪盤影響速度唯一確定文件的路徑名太長，故引入唯一確定文件的路徑名太長，

38、故引入當(dāng)前目錄當(dāng)前目錄 概念，提供相對于當(dāng)前目錄的相對路徑名可加概念，提供相對于當(dāng)前目錄的相對路徑名可加速文件速文件FCBFCB的查找。的查找。目錄查詢技術(shù)：目錄查詢技術(shù)：當(dāng)用戶要訪問一個(gè)已存在文件時(shí)，系統(tǒng)首當(dāng)用戶要訪問一個(gè)已存在文件時(shí)，系統(tǒng)首先利用用戶提供的文件名對目錄進(jìn)行查詢，先利用用戶提供的文件名對目錄進(jìn)行查詢，找出該文件的文件控制塊；然后，根據(jù)找出該文件的文件控制塊；然后，根據(jù)FCBFCB中所記錄的文件物理地址，啟動(dòng)磁盤，將中所記錄的文件物理地址，啟動(dòng)磁盤，將磁盤上的文件讀入內(nèi)存。磁盤上的文件讀入內(nèi)存。UNIXUNIX多級樹形目錄結(jié)構(gòu)多級樹形目錄結(jié)構(gòu)示意圖示意圖tty00devbinl

39、ibetcusrtty01shdate cc whopasswdUNIXfei1myfile.cgettyincludefei2testfile.c練習(xí)有一個(gè)文件系統(tǒng)有一個(gè)文件系統(tǒng), , 根目錄長駐內(nèi)存根目錄長駐內(nèi)存, , 如圖所示如圖所示: :目錄文件采用鏈接式目錄文件采用鏈接式, , 每個(gè)磁盤塊存放每個(gè)磁盤塊存放1010個(gè)下個(gè)下級文件的描述級文件的描述, , 最多存放最多存放4040個(gè)下級文件個(gè)下級文件. . 若下若下級文件為目錄文件級文件為目錄文件, , 上級目錄指向該目錄文件上級目錄指向該目錄文件的第一塊的第一塊, , 否則指向普通文件的文件控制塊否則指向普通文件的文件控制塊. .目錄

40、結(jié)構(gòu)中文件或子目錄按自左向右的次序排目錄結(jié)構(gòu)中文件或子目錄按自左向右的次序排列列. . 普通文件采用三級索引形式普通文件采用三級索引形式, , 文件控制塊中給文件控制塊中給出出1313個(gè)磁盤地址個(gè)磁盤地址, , 前前1010個(gè)磁盤地址指出前個(gè)磁盤地址指出前1010塊塊的物理地址的物理地址, , 第第1111個(gè)磁盤地址指向一級索引表個(gè)磁盤地址指向一級索引表, , 一級索引表給出一級索引表給出256256個(gè)磁盤地址個(gè)磁盤地址, , 即指出該文即指出該文件第件第1111塊至第塊至第266266塊的地址塊的地址; ; 第第1212個(gè)磁盤地址個(gè)磁盤地址指向二級索引表指向二級索引表, , 二級索引表中指出

41、二級索引表中指出256256個(gè)一個(gè)一級索引表的地址級索引表的地址; ; 第第1313個(gè)磁盤地址指向三級索個(gè)磁盤地址指向三級索引表引表, , 三級索引表中指出三級索引表中指出256256個(gè)二級索引表的個(gè)二級索引表的地址地址. .(1) (1) 該文件系統(tǒng)中的普通文件最大可有多少塊該文件系統(tǒng)中的普通文件最大可有多少塊? ?(2) (2) 若要讀文件若要讀文件/A/D/K/Q/A/D/K/Q中的某一塊中的某一塊, , 最少要最少要啟動(dòng)磁盤幾次啟動(dòng)磁盤幾次? ? 最多要啟動(dòng)磁盤幾次最多要啟動(dòng)磁盤幾次? ?(3)(3)訪問文件訪問文件Q Q的第的第72667266塊塊, ,最少要啟動(dòng)磁盤幾最少要啟動(dòng)磁盤

42、幾次次? ? 最多要啟動(dòng)磁盤幾次最多要啟動(dòng)磁盤幾次? ?5.3 5.3 文件存儲(chǔ)空間管理文件存儲(chǔ)空間管理l存儲(chǔ)空間管理是文件系統(tǒng)的重要任務(wù)之一。只存儲(chǔ)空間管理是文件系統(tǒng)的重要任務(wù)之一。只有有效地進(jìn)行存儲(chǔ)空間管理，才能保證多個(gè)用有有效地進(jìn)行存儲(chǔ)空間管理，才能保證多個(gè)用戶共享文件存儲(chǔ)設(shè)備和得以實(shí)現(xiàn)文件的按名存戶共享文件存儲(chǔ)設(shè)備和得以實(shí)現(xiàn)文件的按名存取。由于文件存儲(chǔ)設(shè)備是分成若干個(gè)大小相等取。由于文件存儲(chǔ)設(shè)備是分成若干個(gè)大小相等的物理塊，并以塊為單位來交換信息的，因此，的物理塊，并以塊為單位來交換信息的，因此，文件存儲(chǔ)空間的管理實(shí)質(zhì)上是一個(gè)空閑塊的組文件存儲(chǔ)空間的管理實(shí)質(zhì)上是一個(gè)空閑塊的組織和管理問

43、題，它包括空閑塊的組織，空閑塊織和管理問題，它包括空閑塊的組織，空閑塊的分配與空閑塊的回收等幾個(gè)問題。的分配與空閑塊的回收等幾個(gè)問題。l有下述有下述3 3種不同的空閑塊管理方法。它們是：種不同的空閑塊管理方法。它們是：(1) (1) 空閑表法空閑表法(2) (2) 位示圖法位示圖法(3) (3) 成組鏈接法成組鏈接法(1) (1) 空閑表法空閑表法l空閑表法屬于連續(xù)分配，它與內(nèi)存的動(dòng)態(tài)分配空閑表法屬于連續(xù)分配，它與內(nèi)存的動(dòng)態(tài)分配方式雷同，它為每個(gè)文件分配一塊連續(xù)的存儲(chǔ)方式雷同，它為每個(gè)文件分配一塊連續(xù)的存儲(chǔ)空間，即系統(tǒng)也為外存上的所有空閑區(qū)建立一空間，即系統(tǒng)也為外存上的所有空閑區(qū)建立一張空閑表

44、，每個(gè)空閑區(qū)對應(yīng)于一個(gè)空閑表項(xiàng)，張空閑表，每個(gè)空閑區(qū)對應(yīng)于一個(gè)空閑表項(xiàng)，其中包括表項(xiàng)序號，該空閑區(qū)的第一個(gè)塊號，其中包括表項(xiàng)序號，該空閑區(qū)的第一個(gè)塊號，該區(qū)的空閑塊數(shù)等信息。該區(qū)的空閑塊數(shù)等信息。l在系統(tǒng)為某個(gè)文件分配空閑塊時(shí)，首先掃描空在系統(tǒng)為某個(gè)文件分配空閑塊時(shí)，首先掃描空閑表，如找到合適的空閑區(qū)項(xiàng)，則分配給申請閑表，如找到合適的空閑區(qū)項(xiàng)，則分配給申請者，并把該項(xiàng)從空閑文件目錄中去掉。如果一者，并把該項(xiàng)從空閑文件目錄中去掉。如果一個(gè)空閑區(qū)項(xiàng)所含塊數(shù)超過申請者要求，則為申個(gè)空閑區(qū)項(xiàng)所含塊數(shù)超過申請者要求，則為申請者分配了所要的物理塊之后，再修改該表項(xiàng)。請者分配了所要的物理塊之后，再修改該表項(xiàng)

45、。序號序號第一空閑盤第一空閑盤塊號塊號空閑盤塊數(shù)空閑盤塊數(shù)12429331554l當(dāng)一個(gè)文件被刪除，釋放存儲(chǔ)物理塊時(shí)，系統(tǒng)當(dāng)一個(gè)文件被刪除，釋放存儲(chǔ)物理塊時(shí)，系統(tǒng)則把被釋放的塊號、長度以及第一塊塊號置入則把被釋放的塊號、長度以及第一塊塊號置入空閑表的新表項(xiàng)中。空閑表的新表項(xiàng)中。l顯然，在內(nèi)存管理時(shí)討論過有關(guān)空閑連續(xù)區(qū)分顯然，在內(nèi)存管理時(shí)討論過有關(guān)空閑連續(xù)區(qū)分配和釋放算法。只要稍加修改就可用于空閑表配和釋放算法。只要稍加修改就可用于空閑表的分配和回收。的分配和回收。l空閑表方法適用于連續(xù)文件結(jié)構(gòu)的文件存儲(chǔ)區(qū)空閑表方法適用于連續(xù)文件結(jié)構(gòu)的文件存儲(chǔ)區(qū)的分配與回收。的分配與回收。(2) (2) 位示圖

46、位示圖l位示圖是利用二進(jìn)制的一位來表示磁盤中一個(gè)位示圖是利用二進(jìn)制的一位來表示磁盤中一個(gè)盤塊的使用情況，當(dāng)值為盤塊的使用情況，當(dāng)值為0 0時(shí)，表示對應(yīng)的盤時(shí)，表示對應(yīng)的盤塊空閑；為塊空閑；為1 1時(shí)，表示已分配。時(shí)，表示已分配。l磁盤上的所有盤塊都有一個(gè)二進(jìn)制位與之對應(yīng)，磁盤上的所有盤塊都有一個(gè)二進(jìn)制位與之對應(yīng)，這樣，由所有盤塊所對應(yīng)的位構(gòu)成一個(gè)集合，這樣，由所有盤塊所對應(yīng)的位構(gòu)成一個(gè)集合，成為位示圖。成為位示圖。(3) (3) 成組鏈接法成組鏈接法成組鏈法首先把文件存儲(chǔ)設(shè)備中的所有空閑塊成組鏈法首先把文件存儲(chǔ)設(shè)備中的所有空閑塊按按5050塊劃分為一組。塊劃分為一組。其中，每組的第一塊用來存放

47、前一組中各塊的其中，每組的第一塊用來存放前一組中各塊的塊號和總塊數(shù)。由于第一組的前面已無其他組塊號和總塊數(shù)。由于第一組的前面已無其他組存在，因此，第一組的塊數(shù)為存在，因此，第一組的塊數(shù)為4949塊。不過，由塊。不過，由于存儲(chǔ)設(shè)備的空間塊不一定正好是于存儲(chǔ)設(shè)備的空間塊不一定正好是5050的整倍數(shù)，的整倍數(shù)，因而最后一組將不足因而最后一組將不足5050塊，且由于該組后面已塊，且由于該組后面已無另外的空閑塊組，所以，該組的物理塊號與無另外的空閑塊組，所以，該組的物理塊號與總塊數(shù)只能放在管理文件存儲(chǔ)設(shè)備用的文件資總塊數(shù)只能放在管理文件存儲(chǔ)設(shè)備用的文件資源表中。源表中。在成組鏈法對文件設(shè)備進(jìn)行了上述分組

48、之后，在成組鏈法對文件設(shè)備進(jìn)行了上述分組之后，系統(tǒng)可根據(jù)申請者的要求進(jìn)行空閑塊的分配，系統(tǒng)可根據(jù)申請者的要求進(jìn)行空閑塊的分配，并在釋放文件時(shí)回收空閑塊。下面我們介紹并在釋放文件時(shí)回收空閑塊。下面我們介紹成組鏈法的分配和釋放過程。成組鏈法的分配和釋放過程。l首先，系統(tǒng)在初啟時(shí)把文件資源表復(fù)制到內(nèi)存，首先，系統(tǒng)在初啟時(shí)把文件資源表復(fù)制到內(nèi)存，從而使文件資源表中放有最后一組空閑塊塊號從而使文件資源表中放有最后一組空閑塊塊號與總塊數(shù)的信息進(jìn)入內(nèi)存。與總塊數(shù)的信息進(jìn)入內(nèi)存。l與空閑塊塊號及總塊數(shù)相對應(yīng)，用于空閑塊分與空閑塊塊號及總塊數(shù)相對應(yīng)，用于空閑塊分配與回收是指針配與回收是指針PtrPtr，且，且P

49、trPtr的初值等于該組空的初值等于該組空閑塊的總塊數(shù)。當(dāng)申請者提出空閑塊要求閑塊的總塊數(shù)。當(dāng)申請者提出空閑塊要求n n時(shí)，時(shí)，按照后進(jìn)先出的原則，分配程序在取走按照后進(jìn)先出的原則，分配程序在取走PtrPtr所所指的塊號之后，再做指的塊號之后，再做PtrPtr-1PtrPtr-1的操作。這個(gè)的操作。這個(gè)過程一直持續(xù)到所要求的過程一直持續(xù)到所要求的n n塊都已分配完畢。塊都已分配完畢。當(dāng)內(nèi)存中只剩下最后一個(gè)空閑塊號時(shí)，系統(tǒng)啟當(dāng)內(nèi)存中只剩下最后一個(gè)空閑塊號時(shí)，系統(tǒng)啟動(dòng)設(shè)備管理程序，將該塊中存放的下一組的塊動(dòng)設(shè)備管理程序，將該塊中存放的下一組的塊號與總塊數(shù)讀入內(nèi)存之后將該塊分配給申請者。號與總塊數(shù)讀

50、入內(nèi)存之后將該塊分配給申請者。然后，系統(tǒng)重新設(shè)置然后，系統(tǒng)重新設(shè)置PtrPtr指針，并繼續(xù)為申請指針，并繼續(xù)為申請者進(jìn)程分配空閑塊。者進(jìn)程分配空閑塊。5.4 5.4 文件訪問系統(tǒng)調(diào)用文件訪問系統(tǒng)調(diào)用操作系統(tǒng)提供文件創(chuàng)建、刪除、打開、操作系統(tǒng)提供文件創(chuàng)建、刪除、打開、關(guān)閉、讀、寫等系統(tǒng)調(diào)用作為用戶編程關(guān)閉、讀、寫等系統(tǒng)調(diào)用作為用戶編程接口。接口。5.5 5.5 文件共享與文件保護(hù)文件共享與文件保護(hù)AABBBBBCCCCC根目錄?CCC包含有共享文件的文件系統(tǒng)包含有共享文件的文件系統(tǒng) 無環(huán)圖目錄結(jié)構(gòu)無環(huán)圖目錄結(jié)構(gòu) 可能會(huì)出現(xiàn)一個(gè)同樣的文件，用戶希望在可能會(huì)出現(xiàn)一個(gè)同樣的文件，用戶希望在不同的目錄中

51、都能訪問它。如果在樹形目不同的目錄中都能訪問它。如果在樹形目錄結(jié)構(gòu)中要達(dá)到這個(gè)要求，就必須生成兩錄結(jié)構(gòu)中要達(dá)到這個(gè)要求，就必須生成兩份文件副本，這樣顯然浪費(fèi)了存儲(chǔ)空間。份文件副本，這樣顯然浪費(fèi)了存儲(chǔ)空間。 引入無環(huán)圖目錄結(jié)構(gòu)實(shí)現(xiàn)文件的共享。在引入無環(huán)圖目錄結(jié)構(gòu)實(shí)現(xiàn)文件的共享。在樹形目錄結(jié)構(gòu)中增加一些未形成環(huán)路的鏈，樹形目錄結(jié)構(gòu)中增加一些未形成環(huán)路的鏈，當(dāng)需要共享文件或共享子目錄時(shí)，即可建當(dāng)需要共享文件或共享子目錄時(shí)，即可建立一個(gè)鏈的新目錄項(xiàng)。立一個(gè)鏈的新目錄項(xiàng)。 特點(diǎn)特點(diǎn) 方便文件共享。方便文件共享。 兩個(gè)或多個(gè)兩個(gè)或多個(gè)FCBFCB的一致性難保證，如刪除的一致性難保證，如刪除文件時(shí)，當(dāng)文件修改而引起文件時(shí)，當(dāng)文件修改而引起FCBFCB內(nèi)容變化內(nèi)容變化時(shí)。時(shí)。 root dict spell list root rade W7 list count p 無環(huán)圖目錄結(jié)構(gòu)示意圖無環(huán)圖目錄結(jié)構(gòu)示意圖為圖中每個(gè)結(jié)點(diǎn)設(shè)置一個(gè)訪問計(jì)數(shù)器，為圖中每個(gè)結(jié)點(diǎn)設(shè)置一個(gè)訪問計(jì)數(shù)器，每當(dāng)圖中增加了一條對某個(gè)結(jié)點(diǎn)的共享每當(dāng)圖中增加了一條對某個(gè)結(jié)點(diǎn)的共享鏈時(shí)，該結(jié)點(diǎn)的訪問計(jì)數(shù)器加鏈時(shí)，該結(jié)點(diǎn)的訪問計(jì)數(shù)器加1 1；每當(dāng)需；每當(dāng)需要?jiǎng)h除某個(gè)結(jié)點(diǎn)時(shí)，該結(jié)點(diǎn)的訪問計(jì)數(shù)要?jiǎng)h除某個(gè)結(jié)點(diǎn)時(shí)，該結(jié)