第5章 文件管理

第5章文件管理5.1文件管理概述5.2文件結構5.3文件的存儲設備5.4文件目錄管理5.5文件共享與安全5.6文件使用本章結束！5.1文件管理概述5.1.1文件管理的主要任務

文件是指存儲在外存上的信息集合。在大多數(shù)計算機應用中，文件是主要的處理對象。

文件管理的主要任務是負責管理文件信息，并把對文件的存取、共享和保護等手段提供給操作系統(tǒng)和用戶。文件管理的主要目標是提高外存儲空間的利用率，其主要任務是對用戶文件和系統(tǒng)文件進行管理，方便用戶的使用，并保證文件的安全性。第5章文件管理5.1文件管理概述5.1.2文件管理的主要功能1．文件存儲空間管理文件都是存儲在磁盤上的，所以磁盤空間的管理是文件管理需要考慮的一個主要問題。要把文件保存到存儲介質上，必須知道哪些存儲空間已經使用，哪些存儲空間還沒有使用，文件只能保存到沒有使用的空閑的存儲空間，否則會破壞已保存的信息。

文件存儲空間管理是為每個文件分配必要的存儲空間，提高存儲空間的利用率，并能有助于提高文件系統(tǒng)的工作速度。由于文件存儲設備是以存儲塊為單位進行管理的，因此，文件存儲空間的管理實質上是對一個存儲塊的組織和管理問題，它包括存儲塊的組織，存儲塊的分配與存儲塊的回收。第5章文件管理5.1文件管理概述5.1.2文件管理的主要功能2．文件目錄管理目錄管理的任務是為每個文件建立目錄項，并對眾多的目錄加以組織，以實現(xiàn)文件的按名存取，實現(xiàn)文件的共享，提供快速的目錄查詢手段，提高文件的檢索速度。為實現(xiàn)文件的按名存取，每個文件應該具有一個文件名與之對應。一般來講，用戶文件名由用戶指定，系統(tǒng)文件和特殊文件名在系統(tǒng)設計時指定。為了有效地利用存儲空間并迅速準確地完成由文件名到文件物理位置的轉換，必須把與文件相關的文件名等信息按一定的組織結構進行排列，這主要是依賴于文件目錄來實現(xiàn)。

第5章文件管理5.1文件管理概述5.1.2文件管理的主要功能3．邏輯文件與物理文件的轉換用戶的大量信息都存放在磁盤或磁帶上，必須記住各種信息的分布情況及信息存放的物理位置，并啟動磁盤或磁帶機來保存或讀取信息。為了方便用戶，規(guī)定用戶直接使用的是邏輯文件，用戶使用文件時只要給出文件的名字和一些適當?shù)恼f明信息，文件系統(tǒng)就能按照用戶的要求把邏輯文件組織成物理文件存放到存儲介質上或者把存儲介質上的物理文件轉換成邏輯文件供用戶使用。文件系統(tǒng)還可以根據(jù)需要更換文件存放的位置而對用戶沒有任何影響。第5章文件管理5.1文件管理概述5.1.2文件管理的主要功能4．文件讀寫管理文件的讀寫控制是和文件的共享、保護和保密問題緊密相關的。這三個問題實際上是一個用戶對文件的使用權限，即讀、寫、執(zhí)行的許可權問題。文件系統(tǒng)讀寫控制的主要任務：一是，對擁有讀寫和執(zhí)行權限的用戶，允許他們對文件進行相應的操作。二是，對沒有相應權限的用戶，禁止他們對文件進行相應的操作。三是，防止一個用戶冒充其他用戶對文件進行讀寫操作。四是，防止擁有存取權限的用戶誤用文件。第5章文件管理5.1文件管理概述5.1.2文件管理的主要功能5．文件共享和安全的管理

文件共享是指不同的用戶共同使用同一個文件。在現(xiàn)代計算機系統(tǒng)中，有些文件是可以供多個用戶共享的，如編輯程序和函數(shù)等。在文件共享的系統(tǒng)中，只需要保存該共享文件的一個副本，就可以減少文件復制操作花費的時間，節(jié)省大量的存儲空間。在文件的使用過程中，一些人為因素、系統(tǒng)因素和自然因素都會導致文件被破壞或丟失。文件的安全管理即文件的保護，是解決對文件非法操作的關鍵。第5章文件管理5.1文件管理概述5.1.3文件系統(tǒng)的基本概念1．文件

文件是指存放在外存上的已命名的一組相關信息的集合，通常將程序和數(shù)據(jù)組織成文件。文件中的基本訪問單位是位、字節(jié)或記錄。文件的屬性包括文件類型、文件長度、文件的物理位置、文件的存取控制、文件的建立時間。第5章文件管理5.1文件管理概述5.1.3文件系統(tǒng)的基本概念2．記錄

記錄是一組相關數(shù)據(jù)項的集合，用于描述數(shù)據(jù)對象某方面的屬性。它是文件中數(shù)據(jù)處理的基本單位，是組成文件的基本元素。在一個由大量記錄組成的文件中，為了能惟一地標識一條記錄，可以在記錄的各個數(shù)據(jù)項中，確定出一個或幾個數(shù)據(jù)項，把它（或它們）稱為關鍵字（key）。如在描述學生的數(shù)據(jù)項中，學號可以做為關鍵字。

第5章文件管理5.1文件管理概述5.1.3文件系統(tǒng)的基本概念3．數(shù)據(jù)項

數(shù)據(jù)項是指描述一個對象的某種屬性的字符集，它是數(shù)據(jù)處理的最小單位。它可以分為基本數(shù)據(jù)項和組合數(shù)據(jù)項。

（1）基本數(shù)據(jù)項。基本數(shù)據(jù)項是用于描述一個對象的某種屬性的字符集，是數(shù)據(jù)組織中可以命名的最小邏輯數(shù)據(jù)單位，即原子數(shù)據(jù)，又稱為數(shù)據(jù)元素或字段。它的命名往往與其屬性一致。

（2）組合數(shù)據(jù)項。組合數(shù)據(jù)項由若干個基本數(shù)據(jù)項組成，簡稱組項。例如，工資就是一個組項，它由基本工資、工齡工資和獎勵工資等基本項組成。

第5章文件管理5.1文件管理概述5.1.3文件系統(tǒng)的基本概念4．文件類型（1）按性質和用途分類：系統(tǒng)文件、用戶文件和庫文件。（2）按文件中的數(shù)據(jù)形式分類：源文件、目標文件和可執(zhí)行文件。（3）按文件的存取控制屬性分類：只執(zhí)行文件、只讀文件和讀寫文件。（4）按文件的邏輯結構分類：有結構文件和無結構文件。（5）按文件的物理結構分類：順序文件、鏈接文件和索引文件。（6）按照文件的內容分類：普通文件、目錄文件和特殊文件。第5章文件管理5.1文件管理概述5.1.3文件系統(tǒng)的基本概念5．文件系統(tǒng)

文件系統(tǒng)是指含有大量文件及其屬性說明、對文件進行操作和管理的，向用戶提供使用接口的軟件集合。圖5-1表示了文件系統(tǒng)的組成。它分為三個層次，最低層是對象及其屬性說明；中間層是對對象進行操作和管理的軟件集合；最高層是文件系統(tǒng)提供給用戶的接口。第5章文件管理返回5.2文件結構5.2.1文件的邏輯結構1．文件邏輯結構的概念

文件的邏輯結構是用戶組織文件時可見的結構，即用戶所觀察到的文件組織形式。文件的邏輯結構是用戶可以直接處理的數(shù)據(jù)及其結構，它獨立于物理特性，又稱為文件組織。

選擇文件的邏輯結構主要有以下原則：

(1)提高檢索效率。根據(jù)給定的邏輯結構，應使文件系統(tǒng)在盡可能短的時間內找到所需要的記錄或基本信息單位。

(2)便于修改。便于在文件中增加、刪除和修改一條或多條記錄。

(3)降低文件存儲費用，使文件占用最小的存儲空間。

(4)便于用戶操作。第5章文件管理5.2文件結構5.2.1文件的邏輯結構2．文件邏輯結構的形式

文件的邏輯結構從形式上分為兩類：有結構的記錄式文件和無結構的流式文件。如圖5-2所示。

（1）有結構的記錄式文件。圖5-2左圖文件A為記錄式文件，它由若干條記錄構成，記錄可以按順序編號，對文件的訪問按記錄號進行；也可以為每條記錄指定一個或一組數(shù)據(jù)項作為關鍵字，然后按關鍵字進行訪問。記錄是用戶程序與文件系統(tǒng)交換信息的基本單位。

（2）無結構的流式文件。流式文件是指由字符流構成的文件。它內部的數(shù)據(jù)不再組成記錄，只是一串字符。對流式文件的存取需要指定起始字符和字符數(shù)。如圖5-2右文件B所示。

第5章文件管理5.2文件結構5.2.2文件的物理結構1．文件物理結構的概念

文件的物理結構，又稱為文件的存儲結構，它是指文件在外存上存儲時的組織結構。文件的物理結構與存儲介質的物理特性及用戶對文件的訪問方式有關。文件的物理結構通常劃分為大小相等的物理塊。這些物理塊也稱為物理記錄，它是文件分配及傳輸信息的基本單位。物理記錄的大小與物理設備有關，與邏輯記錄的大小無關。

第5章文件管理5.2文件結構5.2.2文件的物理結構2．文件物理結構的形式根據(jù)文件存儲設備的特性以及用戶對文件的訪問方式，可以在文件存儲器中使用以下三種：（1）順序結構。順序結構是最簡單的一種物理結構。順序結構將一個在邏輯上連續(xù)的文件信息依次存放在外存連續(xù)的物理塊中，即所謂的邏輯上連續(xù)，物理上也連續(xù)。如圖5-3所示。順序結構的優(yōu)點是管理簡單，存取速度快，適合于順序訪問。第5章文件管理5.2文件結構5.2.2文件的物理結構2．文件物理結構的形式

（2）鏈接結構。克服順序文件缺點的辦法之一是采用鏈接結構。鏈接結構將文件存放在外存的若干個物理塊中，這些物理塊不必連續(xù)，并且在每一個物理塊中設一個指針，指向下一個物理塊的位置，從而使得存放在同一個文件的物理塊鏈接起來。如圖5-4所示。

鏈接文件的優(yōu)點是文件的長度可以動態(tài)增長，增加和刪除記錄比較容易，只需要調整鏈表中的指針即可，外存的利用率高。其缺點是隨機訪問效率低。因此，鏈接文件的訪問方式應該是順序訪問。第5章文件管理5.2文件結構5.2.2文件的物理結構2．文件物理結構的形式

（3）索引結構。索引文件克服了順序文件和鏈接文件的缺點。索引結構將文件存放在外存的若干個物理塊中，并為每一個文件建立一張索引表，索引表中的每個表目存放文件信息的邏輯塊號和與之對應的物理塊號。索引表的物理地址由文件說明信息給出。索引結構如圖5-5所示。索引文件既適合順序訪問，又適合隨機訪問，應用范圍廣泛。但是，當文件的記錄數(shù)很多時，索引表就會很龐大從而降低檢索的速度。第5章文件管理5.2文件結構5.2.2文件的物理結構3．文件的訪問方式根據(jù)用戶對文件內數(shù)據(jù)的處理方法不同，文件的訪問方式可以分為：

（1）順序訪問。它是指用戶從文件初始數(shù)據(jù)開始依次訪問文件中的信息。對記錄式文件意味著按記錄的編號從小到大進行存取，對流式文件則意味著對文件從頭至尾進行存取。順序訪問的特點是訪問速度快，不需要計算訪問信息的位置，適合于數(shù)據(jù)的統(tǒng)計和匯總等。

（2）直接訪問。也稱為隨機訪問，是指用戶隨機地訪問文件中的某段信息。用戶在采用直接訪問方式訪問文件時，文件必須存放在可以支持快速定位的隨機存儲設備中。

第5章文件管理5.2文件結構5.2.3記錄的成組和分解每個用戶的文件是由用戶按照自己的需要組織的，邏輯記錄的大小是由文件的性質決定的。而存儲介質上的分塊是根據(jù)存儲介質的特性劃分的。所以，邏輯記錄的大小往往與存儲塊的大小不一致。為了節(jié)省存儲空間，提高主存的利用率，系統(tǒng)引入了記錄的成組和分解。如圖5-7所示。

第5章文件管理5.2文件結構5.2.3記錄的成組和分解1．記錄成組

記錄成組是指把若干條邏輯記錄合并成一組存入一個物理塊的過程。記錄的成組操作必須使用主存緩沖區(qū)，而一個緩沖區(qū)的長度等于最大邏輯記錄長度乘以成組的邏輯記錄個數(shù)。根據(jù)是否允許將一條邏輯記錄存儲于兩個物理塊上，可以把記錄成組分為跨塊方式和不跨塊方式。跨塊方式允許一條邏輯記錄存儲于兩個物理塊上，而不跨塊方式則不允許一條邏輯記錄存儲于兩個物理塊上。

特點：采用不跨塊方式進行記錄成組，操作簡單、易于實現(xiàn)，但是，會浪費一定的存儲空間；而采用跨塊方式進行記錄成組，提高了存儲空間的利用率，但是，操作復雜、不易實現(xiàn)。第5章文件管理5.2文件結構5.2.3記錄的成組和分解2．記錄分解

記錄分解是指從一條物理記錄中把邏輯記錄分離出來的過程。記錄成組存放后，當用戶需要某一條記錄時，必須把含有該條記錄的整塊信息讀出，再從這一組邏輯記錄中找出用戶所需要的記錄進行處理。記錄分解也需要使用主存緩沖區(qū)，如圖5-9所示。

采用記錄成組與分解操作可以提高存儲空間的利用率，有效地減少存儲設備的啟動次數(shù)。但是，記錄的成組與分解操作需要設立主存緩沖區(qū)，增加了系統(tǒng)開銷。第5章文件管理返回5.3文件的存儲設備5.3.1文件存儲設備的類型1．順序存儲設備

順序存儲設備是按信息的物理位置進行定位和讀/寫操作的存儲設備。在順序存儲設備中，只有前面的物理塊被存取之后，才能存取其后的物理塊。例如磁帶就是一種典型的順序存儲設備，它總是從磁帶的當前位置開始讀/寫。磁帶機上的塊不是用地址來標識的，而是用它在磁帶上的位置來標識的。為了在存取一個物理塊時讓磁帶機提前加速和不停止在下一個物理塊的位置上，磁帶的兩個相鄰的物理塊之間設計有一個間隙將它們隔開。磁帶的結構如圖5-10所示。第5章文件管理5.3文件的存儲設備5.3.1文件存儲設備的類型1．順序存儲設備。磁帶的存儲特性如下：（1）磁帶是一種順序存取的存儲設備，總是從磁頭的當前位置開始讀寫。（2）磁帶上的塊不由地址來標識，而由其在磁帶上的位置來識別。（3）塊與塊之間有間隙，磁帶上的物理塊就是通過間隙來區(qū)分的。（4）磁帶的存取速度與信息密度、磁帶帶速和塊間間隙有關。如果帶速高，信息密度大，且所需塊間隙小，則磁帶存取速度高。（5）磁帶的容量大，采用順序存取方式時存取速度高，采用隨機存取方式效率較低。第5章文件管理5.3文件的存儲設備5.3.1文件存儲設備的類型1．順序存儲設備。【例5-1】假定磁帶記錄密度為每英寸800字符，每一條邏輯記錄為160字符，塊間隙為0.6英寸。今有1500條邏輯記錄需要存儲，試計算磁帶的利用率？若要使磁帶空間利用率不少于50%，至少應以多少條邏輯記錄為一組？這說明了什么問題？【解】因磁帶記錄密度為每英寸800字符，則一條邏輯記錄占據(jù)的磁帶長度為：160/800=0.2英寸，1500條邏輯記錄要占據(jù)的磁帶長度為（0.2+0.6）*1500=1200英寸。磁帶的利用率為：0.2/（0.2+0.6）=25%。要使磁帶的利用率不少于50%，即磁帶利用率大于或等于50%，則一組邏輯記錄所占的磁帶長度應與間隙長度相等，所以一組中的邏輯記錄數(shù)至少為：0.6/0.2=3條。這說明記錄的成組可以提高外存空間的利用率。第5章文件管理5.3文件的存儲設備5.3.1文件存儲設備的類型2．直接存儲設備

直接存儲設備是允許文件系統(tǒng)直接存取對應存儲介質上的任意物理塊的存儲設備。如磁盤就是典型的直接存儲設備。磁盤設備允許文件系統(tǒng)直接存取磁盤上的任意物理塊。磁盤機一般由若干張磁盤片組成，這些盤片可以同時沿著一個固定方向高速旋轉。每個盤面對應一個磁頭，所有的讀寫磁頭被固定在惟一的磁臂上，這樣磁頭可以沿半徑方向同時移動，讀寫磁盤上不同位置上的信息。第5章文件管理5.3文件的存儲設備5.3.1文件存儲設備的類型2．直接存儲設備。與磁盤有關的概念。

（1）磁道。磁盤盤片上的一系列同心圓稱為磁道；為了描述磁道，對磁道由外向內進行編號，稱為磁道號（編號均從0開始）。即系統(tǒng)通過磁道號完成對磁道的操作。

（2）柱面。與盤片中心有相同距離的所有磁道組成一個柱面；當磁臂移動到某一位置時，所有的讀寫磁頭都在同一個柱面上，盤面上的磁道號即為柱面號；對于軟盤，一個柱面僅包含兩個磁道。

（3）扇區(qū)。磁道沿徑向又分成大小相等的若干個區(qū)域，每個區(qū)域稱為一個扇區(qū)，每個扇區(qū)可以存放相等字節(jié)數(shù)（一般為512字節(jié)）的信息，按照與磁盤旋轉相反的方向依次給扇區(qū)編號，稱為扇區(qū)號。

（4）磁頭號。所有的讀寫磁頭由上至下進行編號，稱為磁頭號。第5章文件管理5.3文件的存儲設備5.3.1文件存儲設備的類型2．直接存儲設備。磁盤的存儲特性如下：(1)磁盤是一種直接存?。ò吹刂罚┑拇鎯υO備。(2)磁盤空間的位置由三個因素決定：柱面號、磁頭號、扇區(qū)號。(3)在磁盤上信息是按柱面存放的，空間分配的基本單位是簇。(4)訪問磁盤的時間由三部分組成，即尋道時間、延遲時間和傳輸時間。其中尋道時間是指將磁頭從當前位置移動到指定磁道所經歷的時間，也稱為移臂時間；延遲時間是通過磁盤的旋轉將指定扇區(qū)移動到磁頭下面的時間，也稱為旋轉時間；傳輸時間是指將扇區(qū)上的數(shù)據(jù)從磁盤讀出或向磁盤寫入數(shù)據(jù)所經歷的時間。

(5)磁盤的容量大、訪問速度快，可以快速定位物理扇區(qū)，直接訪問，它是計算機系統(tǒng)的主要存儲介質。第5章文件管理5.3文件的存儲設備5.3.1文件存儲設備的類型2．直接存儲設備。【例5-2】某軟盤有40個磁道，磁頭從一個磁道移到另一個磁道需要6ms。文件在磁盤上非連續(xù)存放，邏輯上相鄰數(shù)據(jù)塊的平均距離為13磁道，每塊的旋轉延遲時間及傳輸時間分別為100ms、25ms，問讀取一個100塊的文件需要多少時間？如果系統(tǒng)對磁盤進行了整理，讓同一個磁盤塊盡可能靠攏，從而使邏輯上相鄰的數(shù)據(jù)塊的平均距離降為2磁道，這時讀取一個100塊的文件需要多少時間？第5章文件管理5.3文件的存儲設備5.3.1文件存儲設備的類型2．直接存儲設備。

【解】磁盤訪問時間=尋道時間+旋轉延遲時間+傳輸時間。（1）磁盤整理前，邏輯上相鄰的數(shù)據(jù)塊的平均距離為13磁道，讀取一個數(shù)據(jù)塊的時間為：13*6+100+25=203ms。因此，讀取100塊的文件需要的時間為：203*100=20300ms。（2）磁盤整理后，邏輯上相鄰的數(shù)據(jù)塊的平均距離為2磁道，讀取一個數(shù)據(jù)塊的時間為：2*6+100+25=137ms。因此，讀取100塊的文件需要的時間為：137ms*100=13700ms。第5章文件管理5.3文件的存儲設備5.3.2磁盤的驅動調度算法

磁盤的驅動調度就是要決定等待者的訪問次序，采用的調度策略稱為驅動調度算法。驅動調度是先進行移臂調度，以盡可能減少尋道時間；再進行旋轉調度，以減少延遲時間。

1．移臂調度移臂調度采用的算法有先來先服務（FCFS）、最短尋道時間優(yōu)先（SSTF）、掃描算法（SCAN）或電梯調度算法和循環(huán)掃描（CSCAN）調度算法。第5章文件管理5.3文件的存儲設備5.3.2磁盤的驅動調度算法

1．移臂調度

（1）先來先服務（FCFS）調度算法。它是按請求訪問者的先后次序啟動磁盤驅動器，而不考慮它們要訪問的物理位置。采用這種調度算法，只需要對訪問磁盤的作業(yè)排隊。新來的訪問者排在隊尾，始終從隊首取出訪問者訪問磁盤，直到該隊列為空。

特點：采用這種調度算法，實現(xiàn)起來比較簡單，但是在某些情況下會增加磁臂的移動次數(shù)，甚至大幅度地移動。第5章文件管理5.3文件的存儲設備5.3.2磁盤的驅動調度算法

1．移臂調度（2）最短尋道時間優(yōu)先（SSTF）調度算法?？偸亲岆x當前磁道最近的請求訪問者啟動磁盤驅動器，即讓查找時間最短的那個作業(yè)先執(zhí)行，而不考慮請求訪問者到來的先后次序，這樣就克服了先來先服務調度算法中磁臂移動過大的問題。該調度算法需要為請求訪問磁盤的作業(yè)設置一個隊列，隨著當前磁道的改變，不斷計算后續(xù)訪問者與當前磁道的距離，讓距離最短的訪問者訪問磁盤。當前磁道為最新訪問的磁道。

特點：該調度算法，雖然減少了磁臂的移動距離，但是，會經常改變磁臂的移動方向，花費時間多又影響機械部件，還會導致“饑餓”現(xiàn)象，即較遠距離的孤立的訪問者可能很長時間不能獲得訪問磁盤的機會。第5章文件管理5.3文件的存儲設備5.3.2磁盤的驅動調度算法

1．移臂調度

（3）掃描算法（SCAN）或電梯調度算法?？偸菑拇疟郛斍拔恢瞄_始，沿磁臂的移動方向去選擇離當前磁臂最近的那個柱面的訪問者。如果沿磁臂的方向無請求訪問時，就改變磁臂的移動方向。磁臂的移動類似于電梯，所以也稱它為電梯調度算法。采用這種調度算法，需要為訪問者設置兩個隊列，根據(jù)磁頭的移動方向，能訪問到的訪問者由近及遠排隊，背離磁頭移動方向的訪問者也由近及遠排為另一隊。先按磁頭移動方向隊列調度訪問者訪問磁盤，當該方向沒有訪問者時，再改變方向，選擇另一個訪問者隊列訪問磁盤。特點：較好地解決了尋道性能，又防止了“饑餓”現(xiàn)象。但是，會出現(xiàn)剛訪問過的柱面再次提出請求時，會等待較長的時間。第5章文件管理5.3文件的存儲設備5.3.2磁盤的驅動調度算法

1．移臂調度

（4）循環(huán)掃描（CSCAN）調度算法。它是在掃描算法的基礎上改進的。磁臂改為單向移動，由外向里。從當前位置開始沿磁臂的移動方向去選擇離當前磁臂最近的那個柱面的訪問者。如果沿磁臂的方向無請求訪問時，再回到最外，訪問柱面號最小的作業(yè)請求。該調度算法，需要為訪問者設置一個隊列，該隊列按磁道序號的升序排列，磁頭按磁道序號由小到大掃描一遍，被掃描到的訪問者可以訪問磁盤。被訪問過的磁道從該隊列中刪除，在掃描過程中，又有新的訪問者到來時，仍按訪問磁道序號的升序排列。前一遍掃描結束后，再從磁道序號最小的開始掃描。

特點：較好地解決了尋道性能，又防止了“饑餓”現(xiàn)象。不會讓剛訪問過的磁道再次提請訪問時等待較長的時間。但是，會出現(xiàn)磁臂的“黏著”現(xiàn)象，即在某一段時間內，始終訪問相鄰的幾個磁道或某一個磁道時，磁臂不移動的情況。第5章文件管理5.3文件的存儲設備5.3.2磁盤的驅動調度算法2．旋轉調度

旋轉調度采用的是延遲時間最短者優(yōu)先算法。當磁臂定位后，等待訪問該柱面的若干個訪問者可能要求訪問同一磁道上的不同扇區(qū)，也可能要求訪問不同磁道上的扇區(qū)。旋轉調度總是對先到達磁頭位置上的扇區(qū)進行信息傳送操作，若訪問的扇區(qū)號相同，則應分多次進行旋轉調度。

第5章文件管理5.3文件的存儲設備5.3.2磁盤的驅動調度算法【例5-3】若磁頭的當前位置在100磁道上，磁頭正向磁道號增加的方向移動。現(xiàn)有一磁盤讀寫請求隊列：23、376、205、132、19、61、190、398、29、4、18、40。若采用先來先服務、最短尋道時間優(yōu)先和掃描（電梯）調度算法，試計算平均尋道長度各為多少？【解】（1）先來先服務算法。訪問磁道的順序和移動的磁道數(shù)如下表所示：磁頭移動磁道總數(shù)為：

77+353+171+73+113+42+129+208+369+25+14+22=1596。平均移動道數(shù)為：1596/12=133。（2）最短尋道時間優(yōu)先算法。訪問磁道的順序和移動的磁道數(shù)如下表所示：磁頭移動磁道總數(shù)為：第5章文件管理5.3文件的存儲設備5.3.2磁盤的驅動調度算法32+58+15+144+21+11+6+4+1+14+372+22=700。平均移動道數(shù)為：700/12=58.3。（3）掃描（電梯）算法。訪問磁道的順序和移動的磁道數(shù)如下表所示：磁頭移動磁道總數(shù)為：

32+58+15+171+22+337+21+11+6+4+1+14=692。平均移動道數(shù)為：692/12=57.7。第5章文件管理5.3文件的存儲設備5.3.2磁盤的驅動調度算法【例5-4】磁盤請求以10、22、20、2、40、6、38柱面的次序到達磁盤驅動器。尋道時每個柱面移動需要6ms，計算以下算法的尋道次序和尋道時間。（1）先來先服務調度算法；（2）電梯調度算法（起始向磁道號大的方向移動）在所有情況下磁頭臂起始都位于柱面20號上。第5章文件管理5.3文件的存儲設備5.3.2磁盤的驅動調度算法【解】（1）先來先服務調度算法尋道次序：10、22、20、2、40、6、38柱面尋道時間：((20-10)+(22-10)+(22-20)+(20-2)+(40-2)+(40-6)+(38-6))*6=146*6=876ms（2）電梯調度算法（起始移動向上）尋道次序：22、38、40、20、10、6、2柱面尋道時間：((22-20)+(38-22)+(40-38)+(40-20)+(20-10)+(10-6)+(6-2))*6=58*6=348ms第5章文件管理5.3文件的存儲設備5.3.3存儲空間的分配與回收在文件系統(tǒng)中，存儲管理的主要任務是對存儲空間的分配與回收。

1．順序結構與連續(xù)分配（1）基本原理。順序結構將一個在邏輯上連續(xù)的文件信息依次存放在外存連續(xù)的物理塊中。連續(xù)分配要求為每一個文件分配一組相鄰接的盤塊。一組盤塊的地址定義了磁盤上的一段線性地址。因其采用空閑文件目錄登記磁盤的空閑區(qū)，所以該分配方法也稱為空閑文件目錄法。第5章文件管理5.3文件的存儲設備5.3.3存儲空間的分配與回收

1．順序結構與連續(xù)分配

（2）采用的數(shù)據(jù)結構。

①文件目錄。用于記錄文件在外存空間的存儲情況，包括文件名、始址、末址或長度。如圖5-11所示。

②空閑文件目錄。用于記錄外存空閑塊的基本情況。它將文件存儲設備上的每個連續(xù)空閑區(qū)看作一個空閑文件（又稱自由文件）。系統(tǒng)為所有空閑文件單獨建立一個目錄，每個空閑文件在這個目錄中占一個表目。表目的內容包括：起始空閑塊號、連續(xù)空閑塊個數(shù)和所包含的物理塊號，如表5-1所示。

第5章文件管理5.3文件的存儲設備5.3.3存儲空間的分配與回收

1．順序結構與連續(xù)分配（3）外存空間的分配與回收。當請求分配外存空間時，系統(tǒng)依次掃描空閑文件目錄的記錄，直到找到一個合適的空閑文件為止，在文件目錄中填入該文件的文件名和所分配的始址、末址，并修改空閑文件目錄中相應的表目。否則，系統(tǒng)提示空間不足。當用戶撤消一個文件時，系統(tǒng)會根據(jù)文件目錄，找到該文件在外存中的始址和末址，對空閑文件目錄進行調整。調整有四種情況，與可變分區(qū)管理的空閑區(qū)整理相同。最后，刪除該文件在文件目錄中的記錄。第5章文件管理5.3文件的存儲設備5.3.3存儲空間的分配與回收

1．順序結構與連續(xù)分配（4）特點：（1）它要求文件存儲在一個連續(xù)的磁盤空間中，這種以順序結構存放的文件稱為順序文件或連續(xù)文件。（2）文件順序訪問容易，存取速度快；對于記錄定長的順序文件，還可以隨機地訪問；當文件存儲空間只有少量空閑區(qū)時，效果較好。（3）這種存儲管理會產生碎片，不利于文件的動態(tài)擴充，而且必須事先知道文件的長度。第5章文件管理5.3文件的存儲設備5.3.3存儲空間的分配與回收2．鏈接結構與鏈接分配（1）基本原理

鏈接結構是將文件存放在外存的若干個物理塊中，這些物理塊不必連續(xù)，并且在每一個物理塊中設有一個指針，指向下一個物理塊的位置，從而將存放同一個文件的物理塊鏈接起來。因為磁盤空閑塊的管理是用空閑塊鏈的方法，所以這種存儲分配也稱為空閑塊鏈法。如圖5-12所示。

第5章文件管理5.3文件的存儲設備5.3.3存儲空間的分配與回收2．鏈接結構與鏈接分配（2）采用的數(shù)據(jù)結構：

①文件目錄。它用來記錄文件在外存空間的分配情況，包括文件名和首塊地址。

②空閑塊鏈。在文件存儲設備上的每個空閑塊中設立一個鏈接指針，指向下一個空閑塊，從而將所有的空閑塊鏈接在一起，并設立一個頭指針指向空閑塊鏈的第一個物理塊。

③鏈接指針。在每一個物理塊中設置一個指針，用于指向下一個物理塊。

第5章文件管理5.3文件的存儲設備5.3.3存儲空間的分配與回收2．鏈接結構與鏈接分配（3）外存空間的分配與回收當請求分配外存空間時，系統(tǒng)依次從空閑塊鏈中，取出幾塊分配給該文件，把最后一個物理塊的指針設為空值，并調整空閑塊鏈的頭指針。在文件目錄中增加一條記錄，填入該文件的文件名和首塊地址。若空間不足，則給出提示。當撤消一個文件時，系統(tǒng)根據(jù)文件目錄，收回其存儲空間，并將收回的空閑塊依次插入空閑塊鏈首，同時刪除該文件在文件目錄中的記錄。第5章文件管理5.3文件的存儲設備5.3.3存儲空間的分配與回收2．鏈接結構與鏈接分配（4）特點：（1）文件可以存放在一個不連續(xù)的外存空間中，這種以鏈接結構存放的文件稱為鏈接文件或串聯(lián)文件。（2）這種空間分配方法較好地解決了外存“碎片”的問題，提高了外存的利用率；文件可以實現(xiàn)動態(tài)增長；鏈接結構適用于順序存取的文件。（3）文件只能按照文件指針鏈順序訪問，查找效率低。

第5章文件管理5.3文件的存儲設備5.3.3存儲空間的分配與回收2．鏈接結構與鏈接分配

（5）空閑塊鏈的鏈接方法空閑塊鏈的鏈接方法因系統(tǒng)不同而不同，常用的鏈接方法有：按空閑區(qū)大小順序鏈接，按釋放先后順序鏈接，按成組鏈接。前兩種方法比較直觀，容易理解。這里主要介紹成組鏈接法。

成組鏈接法是將空閑塊分成若干組，其中每組空閑塊數(shù)可以相同也可以不同，再用指針將組與組鏈接起來，在這種鏈接法中，系統(tǒng)根據(jù)磁盤塊數(shù)，開辟若干塊來專門登記系統(tǒng)當前擁有的空閑塊的塊號。

第5章文件管理5.3文件的存儲設備5.3.3存儲空間的分配與回收3．索引結構與索引分配（1）基本原理索引結構將文件存放在外存的若干個物理塊中，并為每個文件建立一張索引表，索引表中的每條記錄存放文件信息的邏輯塊號和與之對應的物理塊號。系統(tǒng)通過文件索引表來完成對文件的操作。在這種方法中，因為磁盤存儲空間的管理采用的是位示圖，所以，這種存儲管理也稱為位示圖法。如圖5-14所示。

第5章文件管理5.3文件的存儲設備5.3.3存儲空間的分配與回收3．索引結構與索引分配（2）采用的數(shù)據(jù)結構

①文件目錄。記錄每個文件的文件名和索引表地址。

②索引表。記錄該文件中每個邏輯塊號和與之存儲對應的物理塊號。文件的邏輯塊與物理塊的大小相同。

③位示圖。用位示圖記錄外存空間的使用情況和剩余的空閑塊數(shù)，包括標志位和空閑塊數(shù)兩部分。標志位用一個二進制位表示其對應的一個物理塊的狀態(tài)，其值為“1”時表示塊已分配，為“0”時表示塊未分配。位示圖的大小由磁盤塊的總塊數(shù)決定。

第5章文件管理5.3文件的存儲設備5.3.3存儲空間的分配與回收3．索引結構與索引分配（3）外存空間的分配與回收。當文件請求分配外存空間時，首先計算該文件所需要的物理塊數(shù)（文件長度/塊的大小），然后用該塊數(shù)與位示圖中的空閑塊數(shù)比較。若文件塊數(shù)大于空閑塊數(shù)，則顯示外存空間不足的信息，拒絕分配外存空間；否則，系統(tǒng)為該文件建立一張索引表，在文件目錄中登記該文件的名字和索引表的起始地址，并順序掃描位示圖，找出一組值為“0”的二進制位。然后經過簡單的換算就可以得到物理盤塊號，填入該文件的索引表，并將位示圖中的這些位改為“1”。最后，修改位示圖中的空閑塊數(shù)，即減去文件所需要的存儲塊數(shù)。第5章文件管理5.3文件的存儲設備5.3.3存儲空間的分配與回收3．索引結構與索引分配（3）外存空間的分配與回收。當刪除文件，也就是回收磁盤空間時，通過文件目錄找到該文件的索引表，根據(jù)索引表找到該文件所有邏輯塊占用的物理塊號，計算出物理塊在位示圖中的行號和列號，將該位清“0”。最后，刪除該文件的索引表，并刪除文件目錄中的相應記錄。

第5章文件管理5.3文件的存儲設備5.3.3存儲空間的分配與回收3．索引結構與索引分配（4）特點：①文件可以通過索引表存放在一個不連續(xù)的外存空間，這種以索引結構存放的文件稱為索引文件。②較好地解決了磁盤“碎片”的問題，提高了外存的利用率，文件可以實現(xiàn)動態(tài)地增長，適宜文件記錄的增加和刪除操作，索引結構可用于順序存取和隨機存取的文件。

③索引表的引用增加了系統(tǒng)開銷。對于小文件，其索引表的利用率較少。第5章文件管理5.3文件的存儲設備5.3.4存儲空間分配舉例【例5-5】有一磁盤組共有10個盤面，每個盤面上有100個磁道，每個磁道有16個扇區(qū)。假定分配以扇區(qū)為單位，若使用位示圖管理磁盤空間，問位示圖需要占用多少空間？若空閑文件目錄的每條記錄占用5B，問何時空閑文件目錄所需要的空間大于位示圖？【解】因磁盤組扇區(qū)總數(shù)為：16*100*10=16000，所以位示圖的標志位需要16000位=2000B。位示圖中的空閑塊數(shù)的取值范圍為0～16000，可以用2B存儲。位示圖的大小為2000B+2B=2002B。而空閑文件目錄的每條記錄占5B，2002B可以存放的表目數(shù)為：2002/5≈400，所以，當空閑文件目錄數(shù)大于400時，空閑文件目錄所需要的空間大于位示圖。第5章文件管理5.3文件的存儲設備5.3.4存儲空間分配舉例【例5-6】設某文件為鏈接文件，由5條邏輯記錄組成，每條邏輯記錄的大小與磁盤塊大小相等，均為512B，并依次存放在50、121、75、80、63號盤塊上。若要存取文件的第1569邏輯地址處的信息，問要訪問哪一個磁盤塊？【解】要存取文件的第1569邏輯地址處的信息，應首先計算該信息所在的邏輯塊號：邏輯塊號=1569/512的商=3即要訪問的邏輯記錄號為3。根據(jù)文件的存儲順序，要訪問的物理盤塊號為80號磁盤塊。第5章文件管理返回5.4文件目錄管理

文件管理的主要目標是實現(xiàn)文件的按名存取。為此，系統(tǒng)必須為每個文件建立一個由文件名到物理地址的映射，這種映射信息及其他管理信息組成了該文件的文件說明。系統(tǒng)把若干個文件說明放在一張表格中，該表格就是文件目錄。5.4.1文件目錄的基本概念1．文件的組成從文件的管理角度看，一個文件包括兩部分：文件體和文件控制塊。文件體即文件本身。文件控制塊（FCB：FileControlBlock）也稱為文件說明，它是為文件設置的用于描述和控制文件的數(shù)據(jù)結構，其中包括文件名、文件類型、文件結構、文件的存儲位置、文件長度、文件的訪問權限、文件的建立日期和時間等屬性。文件管理程序借助于文件控制塊中的信息，實現(xiàn)對文件的各種操作。文件與文件控制塊一一對應。第5章文件管理5.4文件目錄管理5.4.1文件目錄的基本概念2．文件目錄

文件目錄是指存放文件有關信息的一種數(shù)據(jù)結構。它包含多條記錄，每條記錄為一個文件的文件控制塊（FCB）的有關信息。最簡單的記錄包含文件名和文件的起始地址，用以建立文件名和存儲地址的對應關系。較復雜的記錄包含文件控制塊的全部內容，此時，文件目錄就是文件控制塊的集合。

文件目錄是文件實現(xiàn)按名存取的重要手段。通常，一個文件目錄也被看成一個文件，稱為目錄文件，它一般建立在輔存上。文件目錄的管理形式可以分為一級目錄、二級目錄、多級目錄三種。

第5章文件管理5.4文件目錄管理5.4.1文件目錄的基本概念2．文件目錄。對文件目錄的管理有以下要求：

（1）實現(xiàn)“按名存取”。即用戶只需要提供文件名，就可以對文件進行存取。這是目錄管理中最基本的功能，也是文件系統(tǒng)向用戶提供的最基本的服務。

（2）提高對目錄的檢索速度。合理地組織目錄結構，可以加快對目錄的檢索速度，從而加快對文件的存取速度。這是在設計一個大、中型文件系統(tǒng)時，所追求的主要目標。

（3）文件共享。在多用戶系統(tǒng)中，應允許多個用戶共享一個文件，這樣，只需在外存中保留一份該文件的副本，就可以供不同的用戶使用。這樣，可以節(jié)省大量的外存空間。

（4）允許文件重名。系統(tǒng)應允許不同用戶對不同文件取相同的名字，以便于用戶按照自己的習慣命名和使用文件。第5章文件管理5.4文件目錄管理5.4.2一級目錄1．基本原理一級目錄，也稱為單級目錄，是一種最簡單、最原始的目錄結構。它采用的方法是為外存的全部文件建立一張如圖5-17所示的目錄表。表中包括全部文件的文件名、索引表的始址以及文件的其他屬性，如文件長度、文件類型等。每個文件占據(jù)表中的一條記錄。該目錄表存放在外存的某個固定區(qū)域，需要時系統(tǒng)將其全部或部分調入主存。第5章文件管理5.4文件目錄管理5.4.2一級目錄1．基本原理

文件系統(tǒng)通過該目錄表提供的信息對文件進行創(chuàng)建、查找和刪除等操作。（1）當建立一個新文件時，首先確定該文件在表目中是否惟一，若與已有文件同名，提示用戶重新起名或覆蓋已有的文件。若不與已有的文件同名，則從目錄表中找出一個空表目，將新文件的相關信息填入其中。（2）當刪除文件時，首先從目錄表中找到該文件的目錄項，從中找到該文件索引表的始址，刪除文件的索引表，然后清除該文件所占用的目錄項。（3）當對文件進行訪問時，系統(tǒng)首先根據(jù)文件名去查找文件目錄，以確定該文件是否存在。如果存在，根據(jù)該文件的索引表，經過合法性檢查后，完成對文件的操作；否則，顯示文件不存在的信息。第5章文件管理5.4文件目錄管理5.4.2一級目錄2．特點（1）目錄結構易于實現(xiàn)，管理簡單，只需要建立一個文件目錄，對文件的所有操作，都是通過該文件目錄實現(xiàn)的。（2）易發(fā)生重名問題。（3）當文件較多時，查找時間較長。（4）不便于實現(xiàn)文件共享，適用于PC機的單用戶系統(tǒng)。第5章文件管理5.4文件目錄管理5.4.3二級目錄1．基本原理為了克服單級目錄結構所存在的缺點，可以把單級目錄擴充為二級目錄。在二級目錄中，有主文件目錄和用戶文件目錄。在主文件目錄中，每個用戶文件目錄都占有一個目錄項，其中包括用戶名和指向該用戶目錄文件的指針。用戶文件的文件說明組成的目錄文件稱為用戶文件目錄，不同的用戶擁有不同的用戶文件目錄，這些文件目錄具有相似的結構，由用戶所有文件的文件控制塊組成。二級文件目錄結構如圖5-18所示。

第5章文件管理5.4文件目錄管理5.4.3二級目錄2．特點（1）提高了檢索目錄的速度。（2）可以解決用戶文件重名問題。（3）可以使不同用戶共享同一個文件。（4）可以實現(xiàn)對文件的保護和保密。（5）二級文件目錄雖然解決了不同用戶之間文件同名的問題，但是，同一用戶的文件不能同名。當一個用戶的文件很多時，這個矛盾就比較突出了。第5章文件管理5.4文件目錄管理5.4.4多級目錄1．基本原理

為了解決用戶文件同名的問題，可以把二級目錄的層次關系加以推廣，就形成了多級目錄。在二級目錄結構中，如果進一步允許用戶創(chuàng)建自己的子目錄并相應地組織自己的文件，即可以形成三級目錄結構，依此類推，還可以進一步形成多級目錄。通常把三級或三級以上的目錄結構稱為樹型目錄結構。在樹型目錄結構中，除了最低一級外，其他每一級存放的都是下一級目錄或文件的說明信息，最高層為根目錄，最低層為文件。UNIX和DOS系統(tǒng)中都采用了樹型目錄結構，如圖5-19所示。

第5章文件管理5.4文件目錄管理5.4.4多級目錄1．基本原理當要訪問某個文件時，往往使用路徑名來標識文件。文件的路徑名是從根目錄出發(fā)，直到所要找到的文件，將所經過的各目錄名用分隔符（通常是“\”）連接起來而形成的字符串。從根目錄出發(fā)的路徑稱為絕對路徑。當目錄的層次較多時，從根目錄出發(fā)查找文件很費時間。為此引入了當前目錄，即由用戶在一定時間內指定某個目錄為當前目錄，當用戶要訪問某個文件時，只需要給出從當前目錄出發(fā)到要查找的文件之間的路徑。從當前目錄出發(fā)的路徑稱為相對路徑。用相對路徑可以縮短搜索路徑，提高搜索速度。

第5章文件管理5.4文件目錄管理5.4.4多級目錄2．特點（1）層次清楚。（2）解決了用戶文件重名問題。（3）搜索速度快。

第5章文件管理5.4文件目錄管理5.4.5目錄管理舉例【例5-7】假定磁盤塊的大小為1KB，對于540MB的硬盤，其文件分配表FAT需要占用多少存儲空間？當硬盤容量為1.2GB時，F(xiàn)AT需要占用多少空間？【解】因硬盤的大小為540MB，磁盤塊的大小為1KB，所以該硬盤的總盤塊數(shù)為：540MB/1KB=540K（個）又因512K<540K<1024K，故540K個盤塊需要用20位二進制表示，即文件分配表的每個表目為2.5B。FAT需要占用的存儲空間總數(shù)為：2.5B*540K=1350KB。當硬盤大小為1.2GB時，硬盤共有盤塊數(shù)：1.2GB/1KB=1.2M個。需要用21位二進制表示。為了方便對文件分配表的存取，每個表目用24位二進制表示，即文件分配表的每個表目大小為3B。所以，F(xiàn)AT需要占用的存儲空間總數(shù)為：3B*1.2M=3.6MB。

第5章文件管理返回5.5文件共享與安全5.5.1文件共享1．基本概念

文件共享是指一個文件可以被多個授權的用戶共同使用。文件的共享不僅可以減少文件復制操作所花費的時間，節(jié)省大量的存儲空間，還能讓不同用戶完成各自的任務，實現(xiàn)用戶間的合作。但是，文件的共享是有條件的，是要加以控制的。文件的共享必須解決兩個問題：一是如何實現(xiàn)共享，二是如何對各類共享文件的用戶進行存取控制。文件的共享分兩種情況：第一種情況是任何時刻只允許一個用戶使用共享文件。另一種情況是允許多個用戶同時使用同一個共享文件。

第5章文件管理5.5文件共享與安全5.5.1文件共享2．實現(xiàn)文件共享的方法（1）繞彎路法。允許每個用戶獲得一個“當前目錄”，用戶訪問的所有文件都是相對于當前目錄的；當所訪問的文件不在其當前目錄下時，可以通過“向上走”的方式去訪問其上級目錄。這種文件共享方式是低效的，因為，為了訪問一個不在當前目錄下的共享文件時，通常需要花費很多時間去訪問多級目錄，也就是說要繞很大的彎路。

第5章文件管理5.5文件共享與安全5.5.1文件共享2．實現(xiàn)文件共享的方法（2）基本目錄法。早期實現(xiàn)文件共享的另一種有效方法，就是在文件系統(tǒng)中設置一個基本目錄，每個文件在該目錄中均占有一個目錄項，用于給出對應于該文件名的惟一標識符，以及該文件的有關說明信息。例如，文件的物理地址、存取控制和管理等信息。此外，每個用戶都有一個符號文件目錄，其中每一個目錄項中都含有該文件的符號名及其惟一的標識符。

第5章文件管理5.5文件共享與安全5.5.1文件共享2．實現(xiàn)文件共享的方法（3）連訪法。為了提高對共享文件的訪問速度，可以在相應的目錄項之間進行鏈接。具體方法是使一個目錄中的目錄項直接指向另一個目錄中的目錄項，在采用連訪方法實現(xiàn)文件共享時，應在文件說明中增加一連訪屬性，以指示文件說明中的物理地址是一個指向文件或共享文件的目錄項的指針，同時也應包括可以共享該文件的“用戶計數(shù)”，用來表示共有多少用戶需要使用此文件。當沒有任何用戶需要此文件時，可以將此共享文件撤消。

第5章文件管理5.5文件共享與安全5.5.2文件安全

文件安全是指避免合法用戶有意或無意的錯誤操作破壞文件，或非法用戶訪問文件。

影響文件安全性的主要因素有：（1）人為因素。（2）系統(tǒng)因素。（3）自然因素。為了確保文件系統(tǒng)的安全性，可以采取以下措施：（1）通過存取控制機制來防止由人為因素引起的文件不安全性。（2）通過系統(tǒng)容錯技術來防止系統(tǒng)部分的故障所造成的文件不安全性。（3）通過“后備系統(tǒng)”來防止由自然因素所造成的不安全性。第5章文件管理5.5文件共享與安全