操作系統(tǒng)PPT教學課件-第6章_文件管理.ppt

第六章 文 件 管 理,6.1 文件和文件系統(tǒng) 6.2 文件的邏輯結構 6.3 外存分配方式 6.4 目錄管理 6.5 文件存儲空間的管理 6.6 文件共享與文件保護 6.7 數(shù)據(jù)一致性控制,基本點、重點、難度分析,1、基本名詞：文件、記錄、數(shù)據(jù)項（基本點） 2、文件類型、文件系統(tǒng)模型（基本點、重點） 3、文件操作（基本點） 4、文件的邏輯結構、連續(xù)分配（基本點） 5、鏈接分配和索引分配（重點、難點） 6、目錄管理（重點） 7、文件存儲空間的管理：位示圖法（重點）、成組鏈接法（難點） 8、文件共享與文件保護（基本點） 9、數(shù)據(jù)一致性控制（基本點）,在現(xiàn)代計算機系統(tǒng)中，要用到大量的程序和數(shù)據(jù)，由于內(nèi)存容量有限，且不可能長期保存，故平時總是把它們以文件的形式存放在外存中，在需要時再將它們隨時調(diào)入內(nèi)存。 為了保持數(shù)據(jù)的安全性和一致性，在操作系統(tǒng)中增加了文件管理功能，即構成一個文件系統(tǒng)，負責管理在外存上的文件，并把對文件的存取、共享和保護等手段提供給用戶，這不僅方便了用戶，保證了文件的安全性，還可有效地提高系統(tǒng)資源的利用率。,6.1 文件和文件系統(tǒng),在現(xiàn)代os中，幾乎毫不例外地是通過文件系統(tǒng)來組織和管理計算機中所存儲的大量程序和數(shù)據(jù)；或者說，文件系統(tǒng)的管理功能，是通過把它所管理的程序和數(shù)據(jù)組織成一系列文件的方法來實現(xiàn)的。而文件則是指具有文件名的若干相關元素的集合。元素通常是記錄，而記錄又是一組有意義的數(shù)據(jù)項的集合?？梢姡谖募到y(tǒng)的概念，可以把數(shù)據(jù)組成分為數(shù)據(jù)項、記錄和文件三級。,6.1.1 文件、記錄和數(shù)據(jù)項,1. 數(shù)據(jù)項,在文件系統(tǒng)中，數(shù)據(jù)項是最低級的數(shù)據(jù)組織形式，可以把它分成以下兩種類型： (1) 基本數(shù)據(jù)項。這是用于描述一個對象的某種屬性的字符集，是數(shù)據(jù)組織中可以命名的最小邏輯數(shù)據(jù)單位， 即原子數(shù)據(jù)，又稱為數(shù)據(jù)元素或字段。它的命名往往與其屬性一致。例如，用于描述一個學生的基本數(shù)據(jù)項有： 學號、 姓名、 年齡、 所在班級等。,(2) 組合數(shù)據(jù)項。它是由若干個基本數(shù)據(jù)項組成的，簡稱組項。例如，經(jīng)理便是個組項，它由正經(jīng)理和副經(jīng)理兩個基本項組成。又如，工資也是個組項，它可由基本工資、工齡工資和獎勵工資等基本項所組成。 基本數(shù)據(jù)項除了數(shù)據(jù)名外，還應有數(shù)據(jù)類型。因為基本項僅是描述某個對象的屬性，根據(jù)屬性的不同，需要用不同的數(shù)據(jù)類型來描述。例如，在描述學生的學號時，應使用整數(shù)； 描述學生的姓名則應使用字符串(含漢字)；描述性別時，可用邏輯變量或漢字?？梢?，由數(shù)據(jù)項的名字和類型兩者共同定義了一個數(shù)據(jù)項的“型”。 而表征一個實體在數(shù)據(jù)項上的數(shù)據(jù)則稱為“值”。例如，學號/30211、姓名/王有年、性別/男等。,2. 記錄 記錄是一組相關數(shù)據(jù)項的集合，用于描述一個對象在某方面的屬性。一個記錄應包含哪些數(shù)據(jù)項，取決于需要描述對象的哪個方面。而一個對象，由于它所處的環(huán)境不同可把它作為不同的對象。 例如，一個學生，當把他作為班上的一名學生時， 對他的描述應使用學號、姓名、年齡及所在系班，也可能還包括他所學過的課程的名稱、 成績等數(shù)據(jù)項。 但若把他作為一個醫(yī)療對象時，對他描述的數(shù)據(jù)項則應使用諸如病歷號、 姓名、 性別、 出生年月、 身高、 體重、 血壓及病史等項。 在諸多記錄中，為了能惟一地標識一條記錄，必須在一條記錄的各個數(shù)據(jù)項中，確定出一個或幾個數(shù)據(jù)項，把它們的集合稱為關鍵字?；蛘哒f，關鍵字是惟一能標識一條記錄的數(shù)據(jù)項。,3. 文件,文件是指由創(chuàng)建者所定義的、 具有文件名的一組相關元素的集合，可分為有結構文件和無結構文件兩種。 在有結構的文件中，文件由若干個相關記錄組成；而無結構文件則被看成是一個字符流。文件在文件系統(tǒng)中是一個最大的數(shù)據(jù)單位，它描述了一個對象集。例如，可以將一個班的學生記錄作為一個文件。一個文件必須要有一個文件名， 它通常是由一串a(chǎn)scii碼或(和)漢字構成，名字的長度因系統(tǒng)不同而異。如在有的系統(tǒng)中把名字規(guī)定為8個字符，而在有的系統(tǒng)中又規(guī)定可用14個字符。用戶利用文件名來訪問文件，即實現(xiàn)按名存取。,圖 6-1 文件、 記錄和數(shù)據(jù)項之間的層次關系,文件應具有自己的屬性，這些屬性可以包括： (1) 文件類型。 (2) 文件長度。 (3) 文件的物理位置。 (4) 文件的建立時間。 圖6-1示出了文件、記錄和數(shù)據(jù)項之間的層次關系,6.1.2 文件類型和文件系統(tǒng)模型,1. 文件類型,為了便于管理和控制文件而將文件分成若干種類型。同樣，為了方便系統(tǒng)和用戶了解文件的類型，在許多os中都把文件類型作為擴展名而綴在文件名的后面，在文件名和擴展名之間用“.”隔開。下面是常用的幾種文件分類方法。 1) 按用途分類 根據(jù)文件的性質(zhì)和用途的不同，可將文件分為三類： (1) 系統(tǒng)文件。這是指由系統(tǒng)軟件構成的文件。大多數(shù)的系統(tǒng)文件只允許用戶調(diào)用，但不允許用戶去讀，更不允許修改；有的系統(tǒng)文件甚至不直接對用戶開放。 (2) 用戶文件。指由用戶的源代碼、目標文件、可執(zhí)行文件和數(shù)據(jù)等所構成的文件。用戶將這些文件委托給系統(tǒng)保管。 (3) 庫文件。這是由標準子例程及常用的例程等所構成的文件，這類文件只允許用戶調(diào)用，但不允許修改。,2) 按文件中數(shù)據(jù)的形式分類,按照這種方式分類，也可將文件分為三類： (1) 源文件。 這是指由源程序和數(shù)據(jù)構成的文件。通常由終端或輸入設備輸入的源程序和數(shù)據(jù)所形成的文件都屬于源文件。它通常由ascii碼或漢字所組成的。 (2) 目標文件。這是指把源程序經(jīng)過相應語言的編譯程序編譯過，但尚未經(jīng)過鏈接程序鏈接的目標代碼所構成的文件。它屬于二進制文件。通常，目標文件所使用的后綴名是“.obj”。 (3) 可執(zhí)行文件。也屬于二進制文件，這是指編譯后所產(chǎn)生的目標代碼再經(jīng)過鏈接程序鏈接后形成的文件。以“.exe”為擴展名。,4) 按組織形式和處理方式分類 根據(jù)文件的組織形式和系統(tǒng)對其的處理方式，可將文件分為三類： (1) 普通文件。由ascii碼或二進制碼組成的字符文件。如用戶建立的源程序文件、數(shù)據(jù)文件、目標代碼文件及操作系統(tǒng)自身的代碼文件、庫文件等都是普通文件，它們通常存儲在外存儲設備上。 (2) 目錄文件。由文件目錄組成的，用來管理和實現(xiàn)文件系統(tǒng)功能的系統(tǒng)文件，通過目錄文件可以對其它文件的信息進行檢索。由于目錄文件也是由字符序列構成，因此對其可進行與普通文件一樣的文件操作。 (3) 特殊文件。特指系統(tǒng)中的各類i/o設備。為了便于統(tǒng)一管理，系統(tǒng)將所有的i/o設備都視為文件，按文件方式提供給用戶使用，與普通文件的操作類似，只是對這些文件的操作是和設備驅(qū)動程序緊密相連的，系統(tǒng)將這些操作轉(zhuǎn)為對具體設備的操作。,2. 文件系統(tǒng)模型,圖6-2示出了文件系統(tǒng)的模型?？蓪⒃撃Ｐ头譃槿齻€層次，其最底層是對象及其屬性；中間層是對象進行操縱和管理的軟件集合；最高層是文件系統(tǒng)提供給用戶的接口。,圖 6-2 文件系統(tǒng)模型,1) 對象及其屬性 文件管理系統(tǒng)管理的對象有： 文件。 它作為文件管理的直接對象。 目錄。為了方便用戶對文件的存取和檢索，在文件系統(tǒng)中必須配置目錄。對目錄的組織和管理是方便用戶和提高對文件存取速度的關鍵。 磁盤(磁帶)存儲空間。 文件和目錄必定占用存儲空間，對這部分空間的有效管理，不僅能提高外存的利用率，而且能提高對文件的存取速度。 2) 對對象操縱和管理的軟件集合 這是文件管理系統(tǒng)的核心部分。文件系統(tǒng)的功能大多是在這一層實現(xiàn)的，其中包括：對文件存儲空間的管理、對文件目錄的管理、用于將文件的邏輯地址轉(zhuǎn)換為物理地址的機制、對文件讀和寫的管理，以及對文件的共享與保護等功能。,3) 文件系統(tǒng)的接口 為方便用戶使用文件系統(tǒng)，文件系統(tǒng)通常向用戶提供兩種類型的接口： (1) 命令接口。這是指作為用戶與文件系統(tǒng)交互的接口。 用戶可通過鍵盤終端鍵入命令，取得文件系統(tǒng)的服務。 (2) 程序接口。這是指作為用戶程序與文件系統(tǒng)的接口。 用戶程序可通過系統(tǒng)調(diào)用來取得文件系統(tǒng)的服務。,6.1.3 文件操作,用戶通過文件系統(tǒng)所提供的系統(tǒng)調(diào)用實施對文件的操作。最基本的文件操作有：創(chuàng)建文件、刪除文件、讀文件、寫文件、截斷文件、設置文件的讀/寫位置。但對于一個實際的os，為了方便用戶使用文件而提供了更多的對文件的操作。 1. 最基本的文件操作 (1) 創(chuàng)建文件。在創(chuàng)建一個新文件時，系統(tǒng)首先要為新文件分配必要的外存空間，并在文件系統(tǒng)的目錄中，為之建立一個目錄項。目錄項中應記錄新文件的文件名及其在外存的地址等屬性。 (2) 刪除文件。當已不再需要某文件時，可將它從文件系統(tǒng)中刪除。在刪除時，系統(tǒng)應先從目錄中找到要刪除文件的目錄項，使之成為空項，然后回收該文件所占用的存儲空間。 (3) 讀文件。在讀入一個文件時，須在相應系統(tǒng)調(diào)用中給出文件名和相應讀入的內(nèi)存目標地址，此外，系統(tǒng)同樣要查找目錄，找到指定的目錄項，從中得到被讀文件在外存中的位置。在目錄項中，還有一個讀/寫指針用于控制對文件的讀/寫。,(4) 寫文件。在寫一個文件時，須在相應系統(tǒng)調(diào)用中給出該文件名及該文件在內(nèi)存中的(源)地址。為此，也同樣須先查找目錄，找到指定文件的目錄項，再利用目錄中的讀/寫指針進行寫操作。 (5) 截斷文件。如果一個文件的內(nèi)容已經(jīng)陳舊而需要全部更新時，一種方法就是將此文件刪除，再重新創(chuàng)建一個新文件。若其文件名及其屬性沒有發(fā)生變化時，可采用截斷文件的辦法，即將原有文件的長度設置為0，或者說是放棄原有的文件內(nèi)容。 (6) 設置文件的讀/寫位置。文件的讀/寫操作只提供了對文件的順序存取手段，即每次都是從文件的起始位置開始讀或?qū)憽６O置文件的讀/寫位置的操作，是用于設置文件讀/寫指針的位置，以便每次讀/寫文件時，不是從其開始位置而是從所設置的位置開始操作。只有這樣才能改順序存取為隨機存取。,2. 文件的“打開”和“關閉”操作,當前os所提供的大多數(shù)對文件的操作，其過程大致都是這樣兩步：第一步是通過檢索文件目錄來找到指定文件的屬性及其在外存上的位置；第二步是對文件實施相應的操作，如讀/寫文件等。為了避免多次讀/寫文件所引起的多次重復地檢索目錄，在大多數(shù)os中都引入了“打開”（open）這一文件系統(tǒng)調(diào)用，當用戶第一次請求對某文件進行操作時，先利用open系統(tǒng)調(diào)用將該文件打開。,所謂“打開”，是指系統(tǒng)將指名文件的屬性(包括該文件在外存上的物理位置)從外存拷貝到內(nèi)存打開文件表的一個表目中，并將該表目的編號(或稱為索引)返回給用戶。以后， 當用戶再要求對該文件進行相應的操作時，便可利用系統(tǒng)所返回的索引號向系統(tǒng)提出操作請求。系統(tǒng)這時便可直接利用該索引號到打開文件表中去查找，從而避免了對該文件的再次檢索。這樣不僅節(jié)省了大量的檢索開銷，也顯著地提高了對文件的操作速度。如果用戶已不再需要對該文件實施相應的操作時，可利用“關閉”(close)系統(tǒng)調(diào)用來關閉此文件，os將會把該文件從打開文件表中的表目上刪除掉。,3. 其它文件操作 為了方便用戶使用文件，通常，os都提供了數(shù)條有關文件操作的系統(tǒng)調(diào)用，可將這些調(diào)用分成若干類：最常用的一類是有關對文件屬性進行操作的，即允許用戶直接設置和獲得文件的屬性，如改變已存文件的文件名、改變文件的擁有者(文件主)、改變對文件的訪問權，以及查詢文件的狀態(tài)(包括文件類型、大小和擁有者以及對文件的訪問權等)；另一類是有關目錄的，如創(chuàng)建一個目錄，刪除一個目錄，改變當前目錄和工作目錄等；此外，還有用于實現(xiàn)文件共享的系統(tǒng)調(diào)用和用于對文件系統(tǒng)進行操作的系統(tǒng)調(diào)用等。,6.2 文件的邏輯結構,通常，文件是由一系列的記錄組成的。文件系統(tǒng)設計的關鍵要素是指將這些記錄構成一個文件的方法，以及將一個文件存儲到外存上的方法。對于任何一個文件，都存在著以下兩種形式的結構： (1) 文件的邏輯結構。這是從用戶觀點出發(fā)所觀察到的文件組織形式，是用戶可以直接處理的數(shù)據(jù)及其結構，它獨立于文件的物理特性，又稱為文件組織。 (2) 文件的物理結構， 又稱為文件的存儲結構， 是指文件在外存上的存儲組織形式。這不僅與存儲介質(zhì)的存儲性能有關，而且與所采用的外存分配方式有關。 無論采用哪種文件結構，都會影響對文件的檢索速度。本節(jié)主要介紹文件的邏輯結構。,對文件邏輯結構所提出的基本要求，首先是能提高檢索速度，即在將大批記錄組成文件時，應有利于提高檢索記錄的速度和效率；其次是便于修改，即便于在文件中增加、刪除和修改一個或多個記錄；第三就是降低文件的存儲費用，即減少文件占用的存儲空間，不要求文件占用大片的連續(xù)存儲空間。,6.2.1 文件邏輯結構的類型,文件的邏輯結構可分為兩大類，一類是有結構文件，這是指由一個以上的記錄構成的文件，故又把它稱為記錄式文件；其二是無結構文件，這是指由字符流構成的文件，故又稱為流式文件。 1. 有結構文件 在記錄式文件中，每個記錄都用于描述實體集中的一個實體，各記錄有著相同或不同數(shù)目的數(shù)據(jù)項。記錄的長度可分為定長和不定長兩類。 (1) 定長記錄。這是指文件中所有記錄的長度都是相同的，所有記錄中的各數(shù)據(jù)項都處在記錄中相同的位置，具有相同的順序和長度。文件的長度用記錄數(shù)目表示。,(2) 變長記錄。這是指文件中各記錄的長度不相同。產(chǎn)生變長記錄的原因，可能是由于一個記錄中所包含的數(shù)據(jù)項數(shù)目并不相同，例如著書的作者、論文中的關鍵詞等；也可能是數(shù)據(jù)項本身的長度不定，例如病歷記錄中的病因、病史等。 根據(jù)用戶和系統(tǒng)管理上的需要，可采用多種方式來組織這些記錄，形成下述的幾種文件： (1) 順序文件。這是由一系列記錄按某種順序排列所形成的文件。其中的記錄通常是 定長記錄，因而便于快速查找。 (2) 索引文件。當記錄為可變長度時，通常為之建立一張索引表，并為每個記錄設置一個表項，以加快對記錄檢索的速度。 (3) 索引順序文件。這是上述兩種文件構成方式的結合。它為文件建立一張索引表，為每一組記錄中的第一個記錄設置一個表項。,2. 無結構文件 如果說大量的數(shù)據(jù)結構和數(shù)據(jù)庫，是采用有結構的文件形式的話，則大量的源程序、 可執(zhí)行文件、 庫函數(shù)等， 所采用的就是無結構的文件形式，即流式文件。 其長度以字節(jié)為單位。對流式文件的訪問，則是采用讀寫指針來指出下一個要訪問的字符?？梢园蚜魇轿募醋魇怯涗浭轿募囊粋€特例。在unix系統(tǒng)中，所有的文件都被看作是流式文件；即使是有結構文件，也被視為流式文件；系統(tǒng)不對文件進行格式處理。,6.2.2 順序文件,1. 邏輯記錄的排序,文件是記錄的集合。文件中的記錄可以是任意順序的，因此，它可以按照各種不同的順序進行排列。一般地，可歸納為以下兩種情況： 第一種是串結構， 各記錄之間的順序與關鍵字無關。 通常的辦法是由時間來決定，即按存入時間的先后排列， 最先存入的記錄作為第一個記錄，其次存入的為第二個記錄， 依此類推。 第二種情況是順序結構，指文件中的所有記錄按關鍵字(詞)排列?？梢园搓P鍵詞的長短從小到大排序，也可以從大到小排序；或按其英文字母順序排序。 對順序結構文件可有更高的檢索效率，因為在檢索串結構文件時，每次都必須從頭開始，逐個記錄地查找，直至找到指定的記錄，或查完所有的記錄為止。而對順序結構文件，則可利用某種有效的查找算法，如折半查找法等，來提高檢索效率。,2. 對順序文件(sequential file)的讀/寫操作,順序文件中的記錄可以是定長的，也可以是變長的。對于定長記錄的順序文件，如果已知當前記錄的邏輯地址，便很容易確定下一個記錄的邏輯地址。在讀一個文件時，可設置一個讀指針rptr，令它指向下一個記錄的首地址，每當讀完一個記錄時，便執(zhí)行： rptr:=rptr+l 操作，使之指向下一個記錄的首地址，其中l(wèi)為記錄的長度。類似地，在寫一個文件時，也應設置一個寫指針wptr，使之指向要寫的記錄的首地址。同樣，在每寫完一個記錄時，又須執(zhí)行以下操作： wptr:=wptr+l,對于變長記錄的順序文件，在順序讀或?qū)憰r的情況相似，只是在每次讀或?qū)懲暌粋€記錄后，須將讀或?qū)懼羔樇由蟣i，li是剛讀或?qū)懲甑挠涗浀拈L度。圖6-3所示為定長和變長記錄文件。,圖 6-3 定長和變長記錄文件,3. 順序文件的優(yōu)缺點,順序文件的最佳應用場合，是在對諸記錄進行批量存取時， 即每次要讀或?qū)懸淮笈涗?。此時，對順序文件的存取效率是所有邏輯文件中最高的；此外，也只有順序文件才能存儲在磁帶上， 并能有效地工作。 在交互應用的場合，如果用戶(程序)要求查找或修改單個記錄，為此系統(tǒng)便要去逐個地查找諸記錄。 這時， 順序文件所表現(xiàn)出來的性能就可能很差， 尤其是當文件較大時， 情況更為嚴重。 例如，有一個含有104個記錄的順序文件，如果對它采用順序查找法去查找一個指定的記錄，則平均需要查找5103個記錄； 如果是可變長記錄的順序文件，則為查找一個記錄所需付出的開銷將更大，這就限制了順序文件的長度。,順序文件的另一個缺點是， 如果想增加或刪除一個記錄， 都比較困難。 為了解決這一問題， 可以為順序文件配置一個運行記錄文件(log file)或稱為事務文件(transaction file)， 把試圖增加、 刪除或修改的信息記錄于其中， 規(guī)定每隔一定時間， 例如4小時，將運行記錄文件與原來的主文件加以合并， 產(chǎn)生一個按關鍵字排序的新文件。,6.2.3 索引文件,對于定長記錄文件，如果要查找第i個記錄， 可直接根據(jù)下式計算來獲得第i個記錄相對于第一個記錄首址的地址： ai=il 然而，對于可變長度記錄的文件，要查找其第i個記錄時，須首先計算出該記錄的首地址。為此，須順序地查找每個記錄，從中獲得相應記錄的長度li，然后才能按下式計算出第i個記錄的首址。假定在每個記錄前用一個字節(jié)指明該記錄的長度，則,可見，對于定長記錄，除了可以方便地實現(xiàn)順序存取外，還可以方便地實現(xiàn)直接存取。 對于變長記錄則較難實現(xiàn)直接存取，因為使用直接存取方法來訪問變長記錄文件中的一個記錄是十分低效的，其檢索時間也很難令人接受。 為了解決這一問題，可為變長記錄文件建立一張索引表，對主文件中的每個記錄，在索引表中設有一個相應的表項，用于記錄該記錄的長度l及指向該記錄的指針（指向該記錄在邏輯地址空間的首址）。由于索引表是按記錄鍵（又稱該記錄的主鍵）排序的，因此，索引表本身是一個定長記錄的順序文件，從而也就可以方便地實現(xiàn)直接存取。圖6-4示出了索引文件的組織形式。,圖 6-4 索引文件的組織,索引表的數(shù)據(jù)結構可以用線性表或鏈表表示。,對于索引文件進行檢索時，首先是根據(jù)用戶（程序）提供的關鍵字，并利用折半查找法去檢索索引表，從中找到相應的表項；在利用該表項中給出的指向記錄的指針，去訪問所需的記錄。而每當要向索引文件中增加一個新記錄時，便須對索引表進行修改。 優(yōu)點：索引文件有較快的檢索速度。 缺點：索引文件除了有主文件外，還須配置一張索引表，且每個記錄都要有一個索引項，因此增加了存儲費用。 使用場合：主要用于對信息處理的及時性要求較高的場合，例如檢票、訂票系統(tǒng)。,6.2.4 索引順序文件,索引順序文件可能是最常見的一種邏輯文件形式。它有效地克服了變長記錄文件不便于直接存取的缺點，而且所付出的代價也不算太大。它是順序文件和索引文件相結合的產(chǎn)物。它將順序文件中的所有記錄分為若干個組（如，50個記錄為一組）；為順序文件建立一張索引表，在索引表中為每組中的第一個記錄建立一個索引項，其中含有該記錄的鍵值和指向該記錄的指針。索引順序文件如圖6-5所示。,圖 6-5 索引順序文件,對索引順序文件進行檢索時，首先也是利用用戶（程序）所提供的關鍵字以及某種查找算法去檢索索引表，找到該記錄所在記錄組中第一個記錄的表項，從中得到該記錄組第一個記錄在主文件中的位置；然后，再利用順序查找法去查找主文件，從中找到所要求的記錄。 如果在一個順序文件中所含有的記錄數(shù)為n，則為檢索到具有指定關鍵字的記錄，平均須查找n/2個記錄；但對于索引順序文件，則為能檢索到具有指定關鍵字的記錄，平均只要查找 個記錄數(shù)，因而其檢索效率s比順序文件約提高 倍。 對于一個非常大的文件，為找到一個記錄而須查找的記錄數(shù)仍然很多，為了進一步提高檢索效率，可以為順序文件建立多級索引，即為索引文件再建立一張索引表，從而形成兩級索引表，甚至可以建立多級索引。,6.2.5 直接文件和哈希文件,1. 直接文件,采用前述幾種文件結構對記錄進行存取時，都須利用給定的記錄鍵值，先對線性表或鏈表進行檢索，以找到指定記錄的物理地址。 而對于直接文件，則可根據(jù)給定的記錄鍵值，直接獲得指定記錄的物理地址。換言之，記錄鍵值本身就決定了記錄的物理地址。這種由記錄鍵值到記錄物理地址的轉(zhuǎn)換被稱為鍵值轉(zhuǎn)換(key to address transformation)。組織直接文件的關鍵， 在于用什么方法進行從記錄值到物理地址的轉(zhuǎn)換。,這是目前應用最為廣泛的一種直接文件。它利用hash函數(shù)將記錄鍵值轉(zhuǎn)換為相應記錄的地址。但為了能實現(xiàn)文件存儲空間的動態(tài)分配，通常由hash函數(shù)所求得的并非是相應記錄的地址，而是指向一目錄表相應表目的指針，該表目的內(nèi)容指向相應記錄所在的物理塊。如圖6-6所示。例如，若令k為記錄鍵值，用a作為通過hash函數(shù)h的轉(zhuǎn)換所形成的該記錄在目錄表中對應表目的位置，即有關系a=h(k)。通常，把hash函數(shù)作為標準函數(shù)存于系統(tǒng)中，供存取文件時調(diào)用。,2. 哈希(hash)文件,圖 6-6 hash文件的邏輯結構,6.3 外存分配方式,由于磁盤具有可直接訪問的特性，故當利用磁盤來存放文件時，具有很大的靈活性。在為文件分配外存空間時所要考慮的主要問題是：怎樣才能有效地利用外存空間和如何提高對文件的訪問速度。 目前，常用的外存分配方法有連續(xù)分配、鏈接分配和索引分配三種，通常在一個系統(tǒng)中，僅采用一種方法來為文件分配外存空間。文件的物理結構直接與外存分配方式有關。在采用不同的分配方式時，將形成不同的文件物理結構。,6.3.1 連續(xù)分配,1. 連續(xù)分配方式 連續(xù)分配要求為每一個文件分配一組相鄰的盤塊。一組盤塊的地址定義了磁盤上的一段線性地址。例如，第一個盤塊的地址為b，則第二個盤塊的地址為b+1，第三個盤塊的地址為b+2，。通常，它們位于同一條磁道上，在進行讀/寫時，不必移動磁頭，僅當訪問到磁道的最后一個盤塊后，才需要移到下一條磁道，于是又去連續(xù)地讀/寫連續(xù)的盤塊。 在采用連續(xù)分配方式時，可把邏輯文件中的記錄順序地存儲到相鄰的物理塊中，這樣所形成的文件結構稱為順序文件結構，此時的物理文件稱為順序文件。 這種分配方式保證了邏輯文件中的記錄順序與存儲器中文件占用盤塊順序的一致性。為使系統(tǒng)能找到文件存放的地址，應在目錄項“文件物理地址”字段中，記錄該文件第一個記錄所在的盤塊號和文件長度（以盤塊數(shù)進行計量）。圖6-7示出了連續(xù)分配的情況。,圖 6-7 磁盤空間的連續(xù)分配,如同內(nèi)存的動態(tài)分區(qū)分配一樣，隨著文件建立時空間的分配和文件刪除時空間的收回，將使磁盤空間被分割成許多小塊，這些較小的盤塊難以用來存儲文件，此即外存碎片。同樣，我們可以利用緊湊的方法，將盤塊上所有的文件緊靠在一起，把所有的碎片拼接成一大片連續(xù)的存儲空間，此即碎片整理。 由于外存容量通常比內(nèi)存大得多，因此，為了將外存上的空閑空間進行一次緊湊，所花費的時間遠比內(nèi)存緊湊一次所花費的時間多得多。,2. 連續(xù)分配的主要優(yōu)缺點,連續(xù)分配的主要優(yōu)點如下： (1) 順序訪問容易。 (2) 順序訪問速度快。 連續(xù)分配的主要缺點如下： (1) 要求有連續(xù)的存儲空間。容易造成外存碎片，嚴重降低了外存空間的利用率，定期緊湊，又需花費大量的機器時間。 (2) 必須事先知道文件的長度。實際應用中估計的文件長度不是一件容易的事，且難以用于動態(tài)增長的文件。,6.3.2 鏈接分配,連續(xù)分配所存在的問題在于：必須為一個文件分配連續(xù)的磁盤空間。如果將文件裝到多個離散的盤塊中，這樣就可以消除上述的缺點。在采用鏈接分配方式時，可通過在每個盤塊上的鏈接指針，將同屬于一個文件的多個離散的盤塊鏈接成一個鏈表，把這樣形成的物理文件稱為鏈接文件。 鏈接分配采用的是離散分配的方式，消除了外存碎片，故而顯著地提高了外存空間的利用率；又可以根據(jù)文件的當前需要，為其分配必需的盤塊，當文件動態(tài)增長時，可動態(tài)地再為它分配盤塊，故而無需事先知道文件的大小。此外，對文件的操作如增、刪、改等也十分方便。 鏈接方式可以分為隱式鏈接和顯示鏈接兩種形式。,1. 隱式鏈接,在采用隱式鏈接分配方式時，在文件目錄的每個目錄項中，都須含有指向鏈接文件第一個盤塊和最后一個盤塊的指針，而在每個盤塊中都設置了一個指向下一個盤塊的指針。 如果指針占用4個字節(jié)，則對于盤塊大小為512字節(jié)的磁盤，則每個盤塊中實際只有508個字節(jié)供用戶使用。 圖6-8示出了一個占用5個盤塊的隱式鏈接式文件。,圖 6-8 磁盤空間的鏈接式分配,隱式鏈接分配方式的主要問題在于： 它只適合順序訪問，它對隨機訪問是極其低效的。例如，如果要訪問文件所在的第i個盤塊時，必須先讀出文件的第一個盤塊，然后順序地找到第i塊，如果i的值很大時，這顯然花費了很大的磁頭啟動時間。 只通過鏈接指針來將一大批離散的盤塊鏈接起來，其可靠性較差，因為只要其中的任何一個指針出現(xiàn)問題，都會導致整個鏈的斷開。 為了提高檢索速度和減少指針所占用的存儲空間，可以將幾個盤塊組成一個簇，例如一簇可包括4個盤塊；在進行盤塊分配時，是以簇為單位進行的、在鏈接文件中的每個元素也是以簇為單位。這樣將會成倍地減少查找指定盤塊的時間，而且也可以減少指針所占用的存儲空間，但是，此種方法可增加外存碎片，且改進辦法也是非常有限的。,2. 顯式鏈接,這是指把用于鏈接文件各物理塊的指針，顯式地存放在內(nèi)存的一張鏈接表中。該表在整個磁盤僅設置一張，表的序號是物理盤塊號，從0開始，直至n-1；n為盤塊總數(shù)。在每個表項中存放鏈接指針，即下一個盤塊號。在該表中，凡是屬于某一文件的第一個盤塊號，或者說是第一條鏈的鏈首指針所對應的盤塊號，均作為文件首地址被填入相應文件的fcb的“物理地址”字段中。由于查找記錄的過程是在內(nèi)存中進行的，因而不僅顯著地提高了檢索速度，而且大大減少了訪問磁盤的次數(shù)。由于分配給文件的所有盤塊號都放在該表中，故把該表稱為文件分配表fat（file allocation table）。圖6-9示出了顯示鏈接結構。,圖 6-9 顯式鏈接結構,6.3.4 索引分配,1. 單級索引分配 鏈接分配方式雖然解決了連續(xù)分配方式所存在的問題， 但又出現(xiàn)了另外兩個問題， 即： (1) 不能支持高效的直接存取。要對一個較大的文件進行直接存取，須首先在fat中順序地查找許多盤塊號。 (2) fat需占用較大的內(nèi)存空間。即當磁盤容量較大時，fat將占用數(shù)找字節(jié)以上的內(nèi)存空間。 事實上，在打開某個文件時，只需要把該文件所占用的盤塊號集中地放在一起即可，沒必要將整個fat調(diào)入內(nèi)存。為此應將每個文件所對應的盤塊號集中地放在一起。索引分配方法就是基于這種思想所形成的一種分配方法。它為每個文件分配一個索引塊（表），再把分配給該文件的所有盤塊號都記錄在該索引塊中，因而該索引塊就是一個含有許多盤塊號的數(shù)組（各項初值均為-1）。在建立一個文件時，只需在為之建立的目錄項中填上指向該索引塊的指針即可。圖6-12示出了磁盤空間的索引分配圖。,圖 6-12 索引分配方式,索引分配方式支持直接訪問。當要讀文件的第i個盤塊時，可以方便地直接從索引塊中找到第i個盤塊的盤塊號；此外，索引分配方式不會產(chǎn)生外存碎片。當文件較大時，索引分配明顯優(yōu)于鏈接分配方式。 索引分配方式的主要問題是：可能要花費較多的外存空間。即每當建立一個文件時，都要為之分配一個索引塊，將分配給該文件的所有盤塊號記錄于其中。如果系統(tǒng)中中、小型文件較多時，無疑會增加索引塊的數(shù)目，降低了索引塊的利用率，同時也造成了外存空間的浪費。,2. 多級索引分配,當os為一個大文件分配磁盤空間時，如果所分配出去的盤塊的盤塊號已經(jīng)裝滿一個索引塊時，os便為該文件分配另一個索引塊，用于記錄后續(xù)所分配的盤塊號，依此類推，然后再通過鏈接指針將各索引塊按序鏈接起來。顯然，當文件太大時，其索引塊太多時，采用單索引分配方式是低效的。此時，應為這些索引塊再建立一級索引，稱為第一級索引，即系統(tǒng)再分配一個索引塊，作為第一級索引的索引塊，將第一塊、第二塊等索引塊的盤塊號填入此索引塊中，這樣便形成了兩級索引分配方式。如果文件非常大時，還可以用三級、四級等多級索引分配方式。,圖 6-13 兩級索引分配,若每個盤塊的大小為1kb，每個盤塊號占4b，則在一個索引塊中可存放256個盤塊號。這樣，在兩級索引時，最多可包含的存放文件的盤塊的盤塊號總數(shù)n=256256=64k個盤塊號。由此可見：采用兩級索引時，所允許的文件最大長度為64mb。若盤塊的大小為4kb，則在采用單級索引時所允許的最大文件長度為4mb；而在二級索引時，所允許的最大文件長度可達4。,2. 混合索引分配方式,所謂混合索引分配方式，是指將多種索引分配方式相結合而形成的一種分配方式。例如，系統(tǒng)既采用了直接地址（鏈接分配或連續(xù)分配），又采用了一級索引分配方式，或者二級索引分配方式，甚至還采用了三級索引分配方式。這種混合索引分配方式已在unix系統(tǒng)中采用。在unix系統(tǒng)的索引結點中，共設置了13個地址項，即iaddr(0)iaddr(12)，并將它們分成兩類，即直接地址和間接地址。圖6-14示出了混合索引分配方式。,圖 6-14 混合索引方式,(1) 直接地址。 為了提高對文件的檢索速度， 在索引結點中可設置10個直接地址項， 即用iaddr(0)iaddr(9)來存放直接地址。 換言之，在這里的每項中所存放的是該文件數(shù)據(jù)的盤塊的盤塊號。假如每個盤塊的大小為 4 kb，當文件不大于40 kb時，便可直接從索引結點中讀出該文件的全部盤塊號。 (2) 一次間接地址。 對于大、 中型文件， 只采用直接地址是不現(xiàn)實的。 為此，可再利用索引結點中的地址項iaddr(10)來提供一次間接地址。這種方式的實質(zhì)就是一級索引分配方式。圖中的一次間址塊也就是索引塊，系統(tǒng)將分配給文件的多個盤塊號記入其中。在一次間址塊中可存放1k個盤塊號， 因而允許文件長達4 mb。,(3) 多次間接地址。 當文件長度大于4 mb+40 kb時(一次間址與10個直接地址項)， 系統(tǒng)還須采用二次間址分配方式。這時，用地址項iaddr(11)提供二次間接地址。該方式的實質(zhì)是兩級索引分配方式。系統(tǒng)此時是在二次間址塊中記入所有一次間址塊的盤號。在采用二次間址方式時，文件最大長度可達4 gb。 同理，地址項iaddr(12)作為三次間接地址， 其所允許的文件最大長度可達4 tb。,6.4 目 錄 管 理,在現(xiàn)代計算機系統(tǒng)中，都存放著大量的文件，為了能對這些文件實施有效地管理，必須對它們加以妥善組織，這主要是通過文件目錄實現(xiàn)的。文件目錄也是一種數(shù)據(jù)結構，用于標識系統(tǒng)中的文件及其物理地址，供檢索時使用。對目錄管理的要求如下： (1) 實現(xiàn)“按名存取”。即用戶只須提供所要訪問文件的名字，便能快速準確地找到指定文件在外存上的存儲位置。這是目錄管理中最基本的功能，也是文件系統(tǒng)向用戶提供的最基本的服務。 (2) 提高對目錄的檢索速度。通過合理地組織目錄結構，可以加快對目錄的檢索速度，從而提高對文件的存取速度。 (3) 文件共享。在多用戶系統(tǒng)中，應允許多個用戶共享一個文件。這樣就須在外存中只保留一份該文件的副本，供不同的用戶使用，以節(jié)省大量的存儲空間，并方便用戶和提高文件利用率。 (4) 允許文件重名。應允許不同用戶對不同文件采用相同的名字，以便于用戶按照自己的習慣給文件命名和使用文件。,6.4.1 文件控制塊和索引結點,為了能對一個文件進行正確的存取，必須為文件設置用于描述和控制文件的數(shù)據(jù)結構，稱之為“文件控制塊(fcb)”。文件管理程序可以借助于fcb中的信息，對文件施以各種操作。文件與文件控制塊一一對應，而人們把文件控制塊的有序集合稱之為文件目錄，即一個文件控制塊就是一個文件目錄項。通常，一個文件目錄也被看做是一個文件，稱為目錄文件。,1. 文件控制塊 為了能對系統(tǒng)中的大量文件施以有效地管理，在fcb中，通常應含有三類信息，即基本信息、存取控制信息及使用信息。 (1) 基本信息類 文件名：即用于標識一個文件的符號，在每個系統(tǒng)中，每一個文件都必須有唯一的名字，用戶利用文件名對文件按名存取。 文件物理位置：指文件在外存上的存儲位置，它包括存放文件的設備名、文件的起始盤塊號、文件長度等。 文件邏輯結構：用于指示文件是流式文件還是記錄式文件、記錄個數(shù)、文件是定長文件還是不定常文件等。 文件的物理結構：指示文件是順序文件，還是鏈接文件，還是索引文件。 (2) 存取控制信息類 存取控制信息類包括：文件主的存取權限、核準用戶的存取權限以及一般用戶的存取權限。,圖 6-15 ms-dos的文件控制塊,(3) 使用信息類 使用信息類包括：文件的建立日期和時間、文件上一次修改的日期和時間及當前使用的信息（包括當前已打開文件的進程數(shù)、進程運行狀態(tài)及文件在內(nèi)存中是否被修改等）。 通常，fcb的長度為32個字節(jié)。 圖6-15示出了ms-dos中的文件控制塊，其中含有文件名、文件所在的第一個盤塊號、文件屬性等。,2. 索引結點,1) 索引結點的引入,文件目錄通常是存放在磁盤上的，當文件很多時，文件目錄可能要占用大量的盤塊。在查找目錄的過程中，先將存放目錄文件的第一個盤塊中的目錄調(diào)入內(nèi)存，然后把用戶所給定的文件名與目錄項中的文件名逐一比較。若未找到指定文件，便再將下一個盤塊中的目錄調(diào)入內(nèi)存。設目錄文件所占用的盤塊數(shù)為n，按此方法查找，則查找一個目錄項平均需要調(diào)入盤塊(n+1)/2次。(為了減少文件查找時需要啟動磁盤的次數(shù)) 同時，在檢索目錄文件的過程中，只用到了文件名，僅當找到一個目錄項（即其中的文件名與指定要查找的文件名相匹配）時，才需要從該目錄項中讀出該文件的物理地址。而其它一些對文件進行描述的信息，在檢索目錄時一概不用。顯然，這些信息在檢索目錄時不需要調(diào)入內(nèi)存。(為了減少查找文件時的內(nèi)存占用率。),為此，在有的os中，如unix系統(tǒng)，便采用了把文件名與文件描述信息分開的辦法，亦即，使文件描述信息單獨形成一個稱為索引點的數(shù)據(jù)結構，簡稱i結點。在文件目錄中的每個目錄項僅由文件名和指向該文件所對應的i結點的指針構成。 在unix系統(tǒng)中一個目錄僅占16個字節(jié)，其中14個字節(jié)是文件名，2個字節(jié)為i結點指針。在1kb的盤塊中可做64個目錄項，這樣，為了找到一個文件，可使平均啟動磁盤次數(shù)減少到原來的1/4，大大節(jié)省了系統(tǒng)開銷。圖6-16示出了unix的文件目錄項。,圖 6-16 unix的文件目錄,2) 磁盤索引結點,這是存放在磁盤上的索引結點。每個文件有惟一的一個磁盤索引結點，它主要包括以下內(nèi)容： (1) 文件主標識符，即擁有該文件的個人或小組的標識符。 (2) 文件類型，包括正規(guī)文件、目錄文件和特別文件。 (3) 文件存取權限，指各類用戶對該文件的存取權限。 (4) 文件物理地址，每一個索引結點中含有13個地址項，即iaddr(0)iaddr(12)，它們以直接或間接方式給出數(shù)據(jù)文件所在的盤塊的編號。 (5) 文件長度，指以字節(jié)為單位的文件長度。 (6) 文件連接計數(shù)，表明在本文件系統(tǒng)中所有指向該文件的文件名的指針計數(shù)。 (7) 文件存取時間，指本文件最近被進程存取的時間、最近被修改的時間及索引結點最近被修改的時間。,3) 內(nèi)存索引結點 這是存放在內(nèi)存中的索引結點。當文件被打開時，要將磁盤索引結點拷貝到內(nèi)存的索引結點中，便于以后使用。在內(nèi)存索引結點中又增加了一下內(nèi)容： (1) 索引結點編號。 用于標識內(nèi)存索引結點。 (2) 狀態(tài)。 指示i結點是否上鎖或被修改。 (3) 訪問計數(shù)。 每當有一進程要訪問此i結點時， 將該訪問計數(shù)加1， 訪問完再減1。 (4) 文件所屬文件系統(tǒng)的邏輯設備號。 (5) 鏈接指針。 設置有分別指向空閑鏈表和散列隊列的指針。,6.4.2 目錄結構,目錄結構的組織，關系到文件系統(tǒng)的存取速度，也關系到文件的共享性和安全性。因此，組織好文件的目錄，是設計好文件系統(tǒng)的重要環(huán)節(jié)。目前常用的目錄結構形式有單級目錄、兩級目錄和多級目錄。,1. 單級目錄結構,這是最簡單的目錄結構。在整個文件系統(tǒng)中只建立一張目錄表，每個文件占一個目錄項，目錄項中含有文件名、文件擴展名、文件長度、文件類型、文件物理地址及其它文件屬性。此外，為表明每個目錄項是否空閑，又設置了一個狀態(tài)位。 圖6-17示出了單級目錄結構。,圖 6-17 單級目錄,每當要建立一個新文件時，必須先檢索所有的目錄項，以保證新文件名在目錄項中是惟一的。然后再從目錄表中找出一個空白目錄項，填入新文件的文件名及其它說明信息，并置狀態(tài)位為1。刪除文件時，先從目錄中找到該文件的目錄項，回收該文件所占用的存儲空間，然后再清除該目錄項。 單級目錄的優(yōu)點是簡單且能實現(xiàn)目錄管理的基本功能按名存取，但卻存在下述一些缺點： (1) 查找速度慢 (2) 不允許重名 (3) 不便于實現(xiàn)文件共享，為了實現(xiàn)文件共享，應允許不同用戶使用不同的文件名來訪問同一個文件。 單級目錄機構只能滿足對目錄管理的四點要求中的第一點，因此，它只能適用于單用戶環(huán)境。,2. 兩級目錄,為了克服單級目錄所存在的缺點，可以為每一個用戶建立一個單獨的用戶文件目錄ufd (user file directory)。這些文件目錄具有相似的結構，它由用戶所有文件的文件控制塊組成。此外，在系統(tǒng)中再建立一個主文件目錄mfd(master file directory)；在主文件目錄中，每個用戶目錄文件都占有一個目錄項，其目錄項中包括用戶名和指向該用戶目錄文件的指針。 圖6-18示出了兩級目錄結構。,圖 6-18 兩級目錄結構,在兩級目錄結構中，如果用戶希望有自己的用戶文件目錄ufd，可以請求系統(tǒng)為自己建立一個用戶文件目錄；如果自己不再需要ufd，也可以請求系統(tǒng)管理員將它撤銷。具體如下： 在有了ufd后，用戶可以根據(jù)自己的需要創(chuàng)建新文件。每當此時，os只需要檢查該用戶的ufd，判定在改ufd中是否已有同名的另一個文件。若有，用戶必須為新文件重新命名；若無，便在ufd中建立一個新目錄項，將新文件名及其相關屬性填入目錄項中，并置其狀態(tài)位為“1”。當用戶要刪除一個文件時，os也只需要查找該用戶的ufd，從中找出指定文件的目錄項，在回收該文件所占用的存儲空間后，將該目錄項刪除。,兩級目錄結構基本上克服了單級目錄的缺點，并具有以下優(yōu)點： (1) 提高了檢索目錄的速度。 (2) 在不同的用戶目錄中， 可以使用相同的文件名。只要在用戶自己的ufd中，每個文件名都是惟一的。 (3) 不同用戶還可使用不同的文件名來訪問系統(tǒng)中的同一個共享文件。 采用兩級目錄結構也存在一些問題：該結構雖然能有效地將多個用戶隔開，在各用戶之間完全無關時，這種隔離是一個優(yōu)點；但當多個用戶之間相互合作去完成一個大任務，且一用戶有需去訪問其他用戶的文件時，這種隔離便成了一個缺點，因為這中隔離會使諸用戶之間不便于文件共享。,3. 多級目錄結構,1) 目錄結構,對于大型文件系統(tǒng)，通常采用三級或三級以上的目錄結構，以提高對目錄的檢索速度和文件系統(tǒng)的性能。多級目錄結構又稱為樹型目錄結構，主目錄在這里被稱為根目錄，把數(shù)據(jù)文件稱為樹葉，用圓圈表示，其它的目錄均作為樹的結點，用方框表示。圖6-19示出了多級目錄結構。 為了提高文件系統(tǒng)的靈活性，應允許在一個目錄文件中的目錄項既是作為目錄文件的fcb，又是數(shù)據(jù)文件的fcb，這一信息可用目錄項中的一位來指示。例如圖6-19中，用戶a的總目錄中，目錄項a是目錄文件的fcb，而目錄項b和d則是數(shù)據(jù)文件的fcb。,圖 6-19多級目錄結構,2) 路徑名。 在樹形目錄結構中， 從根目錄到任何數(shù)據(jù)文件， 都只有一條惟一的通路。 在該路徑上從樹的根(即主目錄)開始， 把全部目錄文件名與數(shù)據(jù)文件名，依次地用“/”連接起來， 即構成該數(shù)據(jù)文件的路徑名(path name)。 系統(tǒng)中的每一個文件都有惟一的路徑名。 例如，在圖 6-19 中用戶b為訪問文件j， 應使用其路徑名/b/f/j來訪問。,3) 當前目錄(current directory)。 當一個文件系統(tǒng)含有許多級時，每訪問一個文件，都要使用從樹根開始直到樹葉(數(shù)據(jù)文件)為止的、包括各中間結點(目錄)名的全路徑名。 這是相當麻煩的事，同時由于一個進程運行時所訪問的文件，大多僅局限于某個范圍，因而非常不便。 基于這一點，可為每個進程設置一個“當前目錄”，又稱為“工作目錄”。進程對各文件的訪問都相對于“當前目錄”而進行。此時各文件所使用的路徑名， 只需從當前目錄開始， 逐級經(jīng)過中間的目錄文件，最后到達要訪問的數(shù)據(jù)文件。把這一路徑上的全部目錄文件名與數(shù)據(jù)文件名用“/”連接形成路徑名，如用戶b的當前目錄是f，則此時文件j的相對路徑名僅是j本身。 這樣， 把從當前目錄開始直到數(shù)據(jù)文件為止所構成的路徑名，稱為相對路徑名(relative path name)；而把從樹根開始的路徑名稱為絕對路徑名(absolute path name)。,多級目錄與兩級目錄而言，其查詢速度更快，同時層次結構更清晰，能夠更加有效地進行文件的管理和保護。在多級目錄中，不同性質(zhì)、不同用戶的文件可以構成不同的目錄子樹，不同層次、不同用戶的文件分別呈現(xiàn)在系統(tǒng)目錄樹中的不同層次或不同子樹中，可以容易地賦予不同的存取權限。 但是，在多級目錄中查找一個文件，需要按路徑名逐級訪問中間節(jié)點，這就增加了磁盤訪問次數(shù)，無疑將影響查詢速度。 目前，大多數(shù)的操作系統(tǒng)如unix、linux和windows系列都采用了多級目錄結構。,4. 增加和刪除目錄,在樹型目錄結構中，用戶可為自己建立ufd，并可再創(chuàng)建子目錄。在用戶要創(chuàng)建一個新文件時，只需查看在自己的ufd及其子目錄中有無與新文件同名的，若無，便可在ufd或其某個子目錄中增加一個新目錄項。 在樹型目錄中，對于一個已不再需要的目錄，應如何刪除其目錄項，必須視情況而定。這時，如果所要刪除的目錄是空的，即在該目錄項中已不再有任何文件，就可簡單地將該目錄項刪除，使它在其上一級目錄中對應的目錄項為空；如果要刪除的目錄不為空，即其中尚有幾個文件或子目錄，則可采用下述兩種方法處理：,(1) 不刪除非空目錄。當目錄(文件)不空時， 不能將其刪除，而為了刪除一個非空目錄，必須先刪除目錄中的所有文件，使之先成為空目錄， 后再予以刪除。如果目錄中還包含有子目錄，還必須采取遞歸調(diào)用方式來將其刪除， 在ms-dos中就是采用這種刪除方式。 (2) 可刪除非空目錄。當要刪除一目錄時，如果在該目錄中還包含有文件，則目錄中的所有文件和子目錄也同時被刪除。 以上兩種方法實現(xiàn)起來都比較容易，第二種方法則更為方便，但比較危險。因為整個目錄結構雖然用一條命令即能刪除，但如果是一條錯誤命令，其后果則可能很嚴重。,6.4.3 目錄查詢技術,基本原理如下：當用戶要訪問一個已經(jīng)存在的文件時，系統(tǒng)首先利用用戶提供的文件名對目錄進行查詢，找出該文件的文件控制塊或?qū)饕Y點；然后，根據(jù)fcb或索引結點中所記錄的文件物理地址（盤塊號），換算出文件在磁盤上的物理位置；最后，再通過磁盤驅(qū)動程序，將所需要的文件讀入內(nèi)存。目前對目錄進行查詢的方式有兩種：線性檢索法和hash查找方法。 1. 線性檢索法 線性檢索法又稱為順序檢索法。在單級目錄中，利用用戶提供的文件名，用順序查找法直接從文件目錄中找到指名文件的目錄項。在樹型目錄中，用