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

1、第五章第五章 文件系統(tǒng)文件系統(tǒng)在現(xiàn)代計算機系統(tǒng)用，要用到大量的程在現(xiàn)代計算機系統(tǒng)用，要用到大量的程序和數(shù)據(jù)，因內(nèi)存容量有限，且不能長序和數(shù)據(jù)，因內(nèi)存容量有限，且不能長期保存，故而平時總是把它們以文件的期保存，故而平時總是把它們以文件的形式存放在外存中，需要時再隨時將它形式存放在外存中，需要時再隨時將它們調(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)中最直接可見的部分。計算機的重要統(tǒng)中最直接可見的部分。計算機的重要作用之一就是能快速處理大量信息作用之一就是能快速處理大量信息, ,從而從而信息的組織、存取和保管就成為一個極信息的組織、存取和保管就成為一個極為重要的內(nèi)容。文件系統(tǒng)是計算機組織、為重要的內(nèi)容。文件系統(tǒng)是計算機組織、存取和保存信息數(shù)據(jù)的重要手段。本章存取和保存信息數(shù)據(jù)的重要手段。本章主要討論文件的組織結(jié)構(gòu)、存取結(jié)構(gòu)、主要討論文件的組織結(jié)構(gòu)、存取結(jié)構(gòu)、保護以及文件系統(tǒng)空間管理等問題。保護以

3、及文件系統(tǒng)空間管理等問題。第五章第五章 文件系統(tǒng)文件系統(tǒng)文件結(jié)構(gòu)文件結(jié)構(gòu)文件目錄管理文件目錄管理文件存儲空間管理文件存儲空間管理文件共享與保護文件共享與保護目的與要求目的與要求：了解文件結(jié)構(gòu)，訪問方式，存：了解文件結(jié)構(gòu)，訪問方式，存儲結(jié)構(gòu)。掌握文件管理用的文件控制塊和儲結(jié)構(gòu)。掌握文件管理用的文件控制塊和文件目錄結(jié)構(gòu)。了解文件空間管理方法。文件目錄結(jié)構(gòu)。了解文件空間管理方法。重點與難點重點與難點：文件存放與訪問方式，文件目：文件存放與訪問方式，文件目錄結(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) 為了合理的存放文件，必需對磁盤等輔助存儲為了合理的存放文件，必需對磁盤等輔助存儲器空間器空間 ( (或稱文件空間或稱文件空間) ) 進行統(tǒng)一管理。在用戶創(chuàng)進行統(tǒng)一管理。在用戶創(chuàng)建新文件時為其分配空閑區(qū)，而在用戶刪除或修改建新文件時為其分配空閑區(qū)，而在用戶刪除或修改某個文件時某個文件時, ,回收和調(diào)整存儲區(qū)。回收和調(diào)整

5、存儲區(qū)。(2) (2) 實現(xiàn)按名存取，完成對存放在存儲設(shè)備上的文實現(xiàn)按名存取，完成對存放在存儲設(shè)備上的文件信息的查找。件信息的查找。(3) (3) 為了便于存放，文件在存儲設(shè)備上應(yīng)按一定的為了便于存放，文件在存儲設(shè)備上應(yīng)按一定的順序存放。這種存放方式被稱為文件的物理結(jié)構(gòu)。順序存放。這種存放方式被稱為文件的物理結(jié)構(gòu)。(4) (4) 完成文件的共享和提供保護功能。完成文件的共享和提供保護功能。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)建時間，修改時間，文件定建者，創(chuàng)建時間，修改時間，文件定位信息位信息 ，文件所包含的信息。，文件所包含的信息。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)的信息按邏輯上獨立的含義是用戶把文件內(nèi)的信息按邏輯上獨立的含義劃分信息單位，每個單位稱為一個記錄。所劃分信息單位，每個單位稱為一個記錄。所有記錄通常都是描述一個實體集的，有著相有記錄通常都是描述一個實體集的，有著相同或不同數(shù)目的數(shù)據(jù)項，記錄的長度可分為同或不同數(shù)目的數(shù)據(jù)項，記錄的長度可分為定長和不定長記錄兩類。定長和不定長記錄兩類。 記錄是一組相關(guān)數(shù)據(jù)項的集合，用于描記錄是一組相關(guān)數(shù)據(jù)項的集合，用于描述一個對象在

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

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

10、種記錄式的有結(jié)構(gòu)文件可把文件中的記錄按各種不同的方式排列，以便用戶對文件中的記錄進不同的方式排列，以便用戶對文件中的記錄進行修改、追加、查找和管理等操作，主要用于行修改、追加、查找和管理等操作，主要用于信息管理，如數(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)。如何組織它們主要依賴于文件存儲器的物理特性，以及用戶組織它們主要依賴于文件存儲器的物理特性，以及用戶對其文件的訪問方式。對其文件的訪問方式。 文件的訪問方式文件的訪問方式 順序訪問順序訪問 指用戶從文

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

12、訪問設(shè)備要求文件順序存放于帶上。要求文件順序存放于帶上。 磁盤磁盤直接（隨機）訪問設(shè)備直接（隨機）訪問設(shè)備文件可順序、鏈接文件可順序、鏈接式或隨機（通過類似頁表的結(jié)構(gòu)訪問）存放式或隨機（通過類似頁表的結(jié)構(gòu)訪問）存放于設(shè)備上。于設(shè)備上。 5.1.3 5.1.3 文件的物理結(jié)構(gòu)文件的物理結(jié)構(gòu)為了便于存放于磁盤，文件可被等分成為了便于存放于磁盤，文件可被等分成塊塊文件系統(tǒng)將一個文件分塊存放于外存，文件系統(tǒng)將一個文件分塊存放于外存，文件控制塊將包含文件的定位信息文件控制塊將包含文件的定位信息 文件的物理結(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ù)存放于文件存儲器上文件順序連續(xù)存放于文件存儲器上（如磁帶文件，光盤文件）。（如磁帶文件，光盤文件）。特點特點: :實現(xiàn)簡單實現(xiàn)簡單順序訪問容易且速度快順序訪問容易且速度快要求有連續(xù)的存儲空間，外部碎片多要求有連續(xù)的存儲空間，外部碎片多必須事先知道文件的長度必須事先知道文件的長度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ù)地存放于文件存儲器上，但使文件不連續(xù)地存放于文件存儲器上，但使用指針按文件數(shù)據(jù)順序?qū)⑵滏溄悠饋?。用指針按文件?shù)據(jù)順序?qū)⑵滏溄悠饋?。特點：特點：提高了磁盤空間利用率提高了磁盤空間利用率, ,不存在外部碎片問不存在外部碎片問題；題；文件操作靈活（添加、刪除等），有利于文件操作靈活（添加、刪除等），有利于文件長度動態(tài)變化。文件長度動態(tài)變化。（二）鏈接結(jié)構(gòu)（二）鏈接結(jié)構(gòu)1 1、隱式鏈接、隱式鏈接文件名文件名 始址始址 末址末址jeep 9 25文件目錄文件目錄01234567891011121314151617

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

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

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

18、：為每個文件分配一個索引表，一個索引表為每個文件分配一個索引表，一個索引表就是磁盤塊地址數(shù)組就是磁盤塊地址數(shù)組, ,其中第其中第i i個條目指向文個條目指向文件的第件的第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的單級索引表問題：問題：每建立一個文件，分配一個索引表，占每建立一個文件，分配一個索引表，占用較多的外存空間。用較多的外

19、存空間。對于中小文件，一個索引表需要占用一對于中小文件，一個索引表需要占用一個盤塊，空間浪費。個盤塊，空間浪費。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的索引點中，共設(shè)置了的索引點中，共設(shè)置了13個地址項，即個地址

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

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

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

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

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

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

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

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

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

29、對一個文件進行正確的存取，必須為文件設(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)建、修改時間、保存時間創(chuàng)建、修改時間、保存時間 口令：用于對文件訪

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

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

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

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

34、CB1 FCB2 FCB3 FCBn 文件 1 文件 2 文件 3 文件 n 優(yōu)點：優(yōu)點：簡單，易實現(xiàn)簡單，易實現(xiàn)缺點：缺點：限制了用戶對文件的命名限制了用戶對文件的命名（存在（存在“命名沖命名沖突突”問題）問題）檢索文件時平均檢索時間長檢索文件時平均檢索時間長不適于多用戶系統(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。每。每個個UFDUFD在在MFDMFD中均設(shè)置一項，用以描述中均設(shè)置一項，用以描述UFDUFD的用戶名及其物理位置。的用戶名及其物理位置。特點：解決了文件的重名問題特點：解決了文件的重名問題; ; 可用于多用戶系統(tǒng)可用于多用戶系統(tǒng); ; 順序查找時間降低。順序查找時間降低。FCB1FCB2FCB1FCB2 路徑名路徑名 將用戶名與文件名連到一起組成路將用戶名與文件名連到一起組成路經(jīng)名。例如：經(jīng)名。例如：/ /

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

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

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

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

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

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

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

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

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

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

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

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

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

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

50、內(nèi)存之后將該塊分配給申請者。然后，系統(tǒng)重新設(shè)置然后，系統(tǒng)重新設(shè)置PtrPtr指針，并繼續(xù)為申請指針，并繼續(xù)為申請者進程分配空閑塊。者進程分配空閑塊。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 文件共享與文件保護文件共享與文件保護AABBBBBCCCCC根目錄?CCC包含有共享文件的文件系統(tǒng)包含有共享文件的文件系統(tǒng) 無環(huán)圖目錄結(jié)構(gòu)無環(huán)圖目錄結(jié)構(gòu) 可能會出現(xiàn)一個同樣的文件，用戶希望在可能會出現(xiàn)一個同樣的文件，用戶希望在不同的目錄中都

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