操作系統(tǒng)第7章

第7章文件系統(tǒng)7.1文件系統(tǒng)的概念7.2文件的邏輯結構與存取方法7.3文件的物理結構與存儲設備7.4文件存儲空間管理7.5文件目錄管理7.6文件存取控制7.7文件的使用7.8文件系統(tǒng)的層次模型本章小結習題7.1文件系統(tǒng)的概念1.文件系統(tǒng)的引入操作系統(tǒng)對計算機的管理包括兩個方面：硬件資源的管理和軟件資源的管理。圖7.1操作系統(tǒng)的軟硬件管理用戶的遇到的問題：(1)使用現(xiàn)有的軟件資源來協(xié)助完成自己的任務。(2)編制完成的或未完成的程序存放在什么地方,需要訪問的數(shù)據(jù)存放在什么地方，從而使得人們可以再利用已有的軟件資源。事實上，這兩個問題是一個怎樣對軟件資源（程序和數(shù)據(jù)）進行透明存放存儲器的出現(xiàn)，為程序和數(shù)據(jù)等軟件資源的透明存取提供了物質(zhì)基礎。這導致了對軟件資源管理質(zhì)的飛躍——文件系統(tǒng)的出現(xiàn)。文件系統(tǒng)必須完成下列工作：(1)為了合理的存放文件，必需對磁盤等輔助存儲器空間(或稱文件空間)進行統(tǒng)一管理。(2)為了實現(xiàn)按名存取，需要有一個用戶可見的文件邏輯結構，用戶按照文件邏輯結構所給定的方式進行信息的存取和加工。這種邏輯結構是獨立于物理存儲設備的。(3)為了便于存放和加工信息，文件在存儲設備上應按一定的順序存放。這種存放方式被稱為文件的物理結構。(4)完成對存放在存儲設備上的文件信息的查找。(5)完成文件的共享和提供保護功能。2.文件與文件系統(tǒng)的概念(1)文件在計算機系統(tǒng)中，文件被解釋為一組賦名的相關聯(lián)字符流的集合，或者是相關聯(lián)記錄(一個有意義的信息單位)的集合。流式文件記錄式文件(2)文件系統(tǒng)操作系統(tǒng)中與管理文件有關的軟件和數(shù)據(jù)稱為文件系統(tǒng)。它負責為用戶建立文件，撤消、讀寫、修改和復制文件，還負責完成對文件的按名存取和進行存取控制。文件系統(tǒng)具有以下特點：①友好的用戶接口，用戶只對文件進行操作，而不管文件結構和存放的物理位置。②對文件按名存取，對用戶透明。③某些文件可以被多個用戶或進程所共享。④文件系統(tǒng)大都使用磁盤、磁帶和光盤等大容量存儲器作為存儲介質(zhì)，因此，可存儲大量信息。3.文件的分類按文件的性質(zhì)和用途可以分為三類：(1)系統(tǒng)文件該類文件只允許用戶通過系統(tǒng)調(diào)用來執(zhí)行它們，而不允許對其進行讀寫和修改。這些文件主要由操作系統(tǒng)核心和各種系統(tǒng)應用程序和數(shù)據(jù)所組成。(2)庫文件該類文件允許用戶對其進行讀取、執(zhí)行，但不允許對其進行修改。庫文件主要由各種標準子程序庫組成。如C語言子程序庫、FORTRAN子程序庫等。(3)用戶文件用戶文件是用戶委托文件系統(tǒng)保存的文件。這類文件只由文件的所有者或所有者授權的用戶才能使用。用戶文件主要由源程序、目標程序、用戶數(shù)據(jù)庫等組成。另外，按組織形式，文件又可被畫分為以下三類：(1)普通文件普通文件既包括系統(tǒng)文件，也包括用戶文件和庫函數(shù)文件、實用程序文件。普通文件主要是指組織格式為系統(tǒng)中所規(guī)定的最一般格式的文件，例如由字符流組成的文件。(2)目錄文件目錄文件是由文件的目錄信息構成的特殊文件。即該文件的內(nèi)容不是各種程序或應用數(shù)據(jù)，而是用來檢索普通文件的目錄信息。(3)特殊文件在UNIX系統(tǒng)中，所有的輸入、輸出設備都被看作特殊文件。這組特殊文件在使用形式上與普通文件相同，如查找目錄、存取操作等。還可以按文件中的信息流向或文件的保護級別等分類。例如，按信息流向可把文件分為：輸入文件、輸出文件、以及輸入/輸出文件等。按文件的保護級別又可分為：只讀文件、讀寫文件、可執(zhí)行文件和不保護文件等。7.2文件的邏輯結構與存取方法7.2.1邏輯結構文件的邏輯結構可分為兩大類：字符流式的無結構文件和記錄式的有結構文件。選取文件的邏輯結構應遵循下述原則：(1)當用戶對文件信息進行修改操作時，給定的邏輯結構應能盡量減少對已存儲好的文件信息的變動。(2)當用戶需要對文件信息進行操作時，給定的邏輯結構應使文件系統(tǒng)在盡可能短的時間內(nèi)查找到需要查找的記錄或基本信息單位。(3)應使文件信息占據(jù)最小的存儲空間。(4)應是便于用戶進行操作的。字符流的無結構文件：查找文件中的基本信息單位，是比較困難的，但管理簡單，用戶可以方便地對其進行操作。所以，那些對基本信息單位操作不多的文件較適于采用字符流的無結構方式，例如，源程序文件、目標代碼文件等。記錄式的有結構文件可把文件中的記錄按各種不同的方式排列，構成不同的邏輯結構，以便用戶對文件中的記錄進行修改、追加、查找和管理等操作。記錄是一個具有特定意義的信息單位，它由該記錄在文件中的邏輯地址(相對位置)與記錄名所對應的一組鍵、屬性及其屬性值所組成。圖7.2是一個記錄的組成例。圖7.2記錄組成例常用的記錄式結構文件有以下幾種:(1)連續(xù)結構連續(xù)結構是一種把記錄按生成的先后順序連續(xù)排列的邏輯結構。連續(xù)結構的特點是適用性強，可用于所有文件，且記錄的排列順序與記錄的內(nèi)容無關。這有利于記錄的追加與變更。但是，連續(xù)結構文件的搜索性能較差，例如要找出某個指定鍵的記錄時，系統(tǒng)必須對文件全體進行搜索。(2)多重結構如果把記錄按鍵和記錄名排列成行列式結構圖7.3文件的記錄名和鍵構成的行列式把行列式中那些為零的項去掉，并以鍵Ki為隊首，以包含鍵Ki的記錄為隊列元素來構成一個記錄隊列。對于一個有m個鍵的隊列來說，這樣的隊列有m個。這m個隊列構成了該文件的多重結構(multi_list)。圖7.4文件的多重結構(3)轉(zhuǎn)置結構把所有與同一鍵對應的記錄的指針連續(xù)地置于目錄中該鍵的位置下。轉(zhuǎn)置結構最適合于給定鍵后的記錄搜索。(4)順序結構把文件中的鍵按規(guī)定的順序排列起來就形成了順序結構文件。7.2.2存取方法用戶通過對文件的存取來完成對文件的修改、追加和搜索等操作。常用的存取方法有三種：(1)順序存取法(2)隨機存取法(直接存取法)(3)按鍵存取法對文件的搜索包括兩種：鍵的搜索和記錄的搜索。圖7.6記錄Ri的搜索過程幾種搜索算法(1)線性搜索法(linearsearch)，(2)散列法(hashcoding)，(3)二分搜索法(binarysearchalgorithm)。(1)線性搜索法線性搜索法的搜索效率較低，在文件中記錄個數(shù)較多時不宜采用。(2)散列法散列法的核心思想是定義一個散列函數(shù)h(k)，使得對于給定的鍵k，散列函數(shù)h(k)將其變換為k所對應的邏輯地址。在使用散列函數(shù)進行搜索時，有時會出現(xiàn)兩個不同的輸入值變換到同一地址的問題。這種問題稱為散列沖突。解決散列沖突的方法是采用多次散列探索。(3)二分搜索法對于順序結構排列的鍵或記錄來說，二分搜索法具有較高的搜索效率。二分搜索法的好處是搜索效率高。與線性搜索法相比，當n(表長)=16時,它比線性搜索法約快二倍;當n=1024時，其平均搜索速度要快50倍。不過，二分搜索法需要事先把搜索對象按一定順序排列。圖7.7二分搜索法的搜索過程7.3文件的物理結構與存儲設備7.3.1文件的物理結構(1)連續(xù)文件連續(xù)文件是一種最簡單的物理文件結構，它把一個在邏輯上連續(xù)的文件信息依次存放到物理塊中。連續(xù)文件結構的優(yōu)點是存取速度快。缺點：不能動態(tài)增長。會留下無法使用的零頭空間。不宜用來存放經(jīng)常被修改的文件。圖7.8連續(xù)文件結構(2)串聯(lián)文件采用非連續(xù)的物理塊來存放文件信息。使得存放同一文件的物理塊鏈接成一個串聯(lián)隊列。圖7.9給出了串聯(lián)文件的物理結構。文件長度可以動態(tài)地增長，只要調(diào)整連接指針就可在任何一個信息塊之間插入或刪除一個信息塊。串聯(lián)文件結構的搜索效率較低。串連文件結構一般只適用于邏輯上連續(xù)的文件，且存取方法應該是順序存取的圖7.9串聯(lián)文件的物理結構(3)索引文件為每個文件建立一張索引表，表中每一欄目指出文件信息所在的邏輯塊號和與之對應的物理塊號。索引表的物理地址則由文件說明信息項給出。索引結構如圖7.10所示。索引文件結構既可以滿足文件動態(tài)增長的要求，又可以較為方便和迅速地實現(xiàn)隨機存取。索引結構的缺點是由于使用了索引表而增加了存儲空間的開銷。另外，在存取文件時需要至少訪問存儲器二次以上。一種改進的方法是，當對某個文件進行操作之前，系統(tǒng)預先把索引表放入內(nèi)存。圖7.10索引文件示意圖圖7.11多重索引結構7.3.2文件存儲設備以磁帶為代表的順序存儲設備以磁盤為代表的直接存儲設備1.順序存取設備-磁帶圖7.12磁帶的結構磁帶設備的存取速度或數(shù)據(jù)傳輸率與下列因素有關：(1)信息密度(字符數(shù)/英寸)(2)磁帶帶速(英寸/秒)(3)塊間間隙如果帶速高，信息密度大，且所需塊間隙(磁頭啟動和停止時間)小的話，則磁帶存取速度和數(shù)據(jù)傳輸率高，反之亦然。2.直接存取設備-磁盤磁盤上每個物理塊的位置可用柱面號、磁頭號和扇區(qū)號表示，這些地址和物理塊號一一對應。磁盤的結構如圖7.13所示。圖7.13磁盤的結構7.4文件存儲空間管理3種不同的空閑塊管理方法。它們是：(1)空閑文件目錄 (2)空閑塊鏈 (3)位示圖(1)空閑文件目錄最簡單的空閑塊管理方法就是把文件存儲設備中的空閑塊的塊號統(tǒng)一放在一個稱為空閑文件目錄的物理塊中。其中空閑文件目錄的每個表項對應一個由多個空閑塊構成的空閑區(qū)，它包括空閑塊個數(shù)，空閑塊號和第一個空閑塊號等?？臻e文件項方法適用于連續(xù)文件結構的文件存儲區(qū)的分配與回收(2)空閑塊鏈空閑塊鏈是一種較常用的空閑塊管理方法?？臻e塊鏈把文件存儲設備上的所有空閑塊鏈接在一起，當申請者需要空閑塊時，分配程序從鏈頭開始摘取所需要的空閑塊，然后調(diào)整鏈首指針。反之，當回收空閑塊時，把釋放的空閑塊逐個插入鏈尾上。常用的鏈接方法按空閑區(qū)大小順序鏈接的方法按釋放先后順序鏈接的方法按成組鏈接法(3)位示圖7.5文件目錄管理把文件名和對該文件實施控制管理的控制管理信息稱為該文件的文件說明，并把一個文件說明按一定的邏輯結構存放到物理存儲塊的一個表目中把一個文件的文件說明信息稱為該文件的目錄。對文件目錄的管理就是對文件說明信息的管理。7.5.1文件的組成從文件管理角度看，一個文件包括兩部分：文件說明和文件體。文件體指文件本身的信息，它可能是前面各節(jié)討論的記錄式文件或字符流式文件。文件說明有時也叫文件控制塊(FCB)，它至少包括文件名、與(物理結構是連續(xù)結構時)文件名相對應的文件內(nèi)部標識以及文件信息在文件存儲設備上第一個物理塊的地址（物理結構是邊連續(xù)結構時）。另外，根據(jù)系統(tǒng)要求不同，它還包括關于文件邏輯結構、物理結構、存取控制和管理信息等。這里的管理信息主要指訪問時間、以及記賬信息等。文件說明組成目錄文件。文件系統(tǒng)利用目錄文件完成按名存取和對文件信息的共享與保護。7.5.2文件目錄文件目錄可分為單級目錄、二級目錄和多級目錄。單級目錄是一種最簡單、最原始的目錄結構。文件系統(tǒng)為存儲設備的所有文件建立一張目錄表，每個文件在其中占有一項用來存放文件說明信息。單級目錄時的文件系統(tǒng)讀寫處理過程如圖7.15。命名沖突問題和目錄表的搜索速度圖7.15單級目錄的讀寫處理過程二級目錄結構圖7.16二級目錄結構另外，與單級目錄相比，如果單級目錄表的長度為n的話，則單級目錄時的搜索時間與n成正比;在二級目錄時，由于ｎ的目錄已被畫分為ｍ個子集，則二級目錄的搜索時間是與ｍ＋ｒ成正比的。這里的ｍ是用戶個數(shù)，ｒ是每個用戶的文件的個數(shù)。一般有ｍ＋ｒ≤ｎ，從而二級目錄的搜索時間要快于單級目錄。多級目錄圖7.17文件系統(tǒng)的樹形結構樹形結構多級目錄結構具有下列特點：(1)層次清楚。(2)解決了文件重名問題。(3)查找搜索速度快。7.5.3便于共享的文件目錄從系統(tǒng)管理的觀點看，有三種方法可以實現(xiàn)文件共享。即：(1)繞道法(2)鏈接法(3)基本文件目錄表BFD繞道法:用戶從當前目錄出發(fā)向上返回到與所要共享文件所在路徑的交叉點，再順序下訪到共享文件。繞道法需要用戶指定所要共享文件的邏輯位置或到達被共享文件的路徑。繞道法的原理如圖7.18所示。繞道法要繞彎路訪問多級目錄，搜索效率不高鏈接法：即將一個目錄中的鏈指針直接指向被共享文件所在的目錄。鏈接法仍然需要用戶指定被共享的文件和被鏈接的目錄。圖7.18繞道法實現(xiàn)文件共享的一種有效方法是采用基本文件目錄表BFD的方法。該方法把所有文件目錄的內(nèi)容分成兩部分：一部分包括文件的結構信息、物理塊號、存取控制和管理信息等，并由系統(tǒng)賦予唯一的內(nèi)部標識符來標識；另一部分則由用戶給出的符號名和系統(tǒng)賦給文件說明信息的內(nèi)部標識符組成。這兩部分分別稱為符號文件目錄表(SFD)和基本文件目錄表(BFD)。SFD中存放文件名和文件內(nèi)部標識符，BFD中存放除了文件名之外的文件說明信息和文件的內(nèi)部標識符。這樣組成的多級目錄結構如圖7.19。圖7.19采用基本文件目錄的多級目錄結構7.5.4目錄管理7.6文件存取控制文件的共享是指不同的用戶共同使用一個文件。文件保護則指文件本身需要防止文件的擁有者本人或其他用戶破壞文件內(nèi)容。文件保密指未經(jīng)文件擁有者許可，任何用戶不得訪問該文件。這三個問題實際上是一個用戶對文件的使用權限，即讀、寫、執(zhí)行的許可權問題。具體地說，文件系統(tǒng)的存取控制部分應做到：(1)對于擁有讀、寫或執(zhí)行權限的用戶，應讓其對文件進行相應的操作。(2)對于沒有讀、寫或執(zhí)行權限的用戶，應禁止他們對文件進行相應的操作。(3)應防止一個用戶冒充其他用戶對文件進行存取。(4)應防止擁有存取權限的用戶誤用文件。這些功能是由一組稱為存取控制驗證模塊的程序提供的。它們分三步驗證用戶的存取操作。(1)審定用戶的存取權限。(2)比較用戶權限的本次存取要求是否一致。(3)將存取要求和被訪問文件的保密性比較，看是否有沖突?？捎邢率觯磦€方式來驗證用戶的存取操作,它們是：(1)存取控制矩陣; (2)存取控制表;(3)口令; (4)密碼術。(1)存取控制矩陣存取控制矩陣方式以一個二維矩陣來進行存取控制。二維矩陣的一維是所有的用戶，另一維是所有的文件。對應的矩陣元素則是用戶對文件的存取控制權，包括讀Ｒ，寫Ｗ，和執(zhí)行Ｅ。如圖7.20所示。在占用內(nèi)存空間的大小上和對矩陣進行掃描的時間開銷上都是不合適的。圖7.20存取控制矩陣(2)存取控制表存取控制表以文件為單位，把用戶按某種關系畫分為若干組，同時規(guī)定每組的存取權限。這樣，所有用戶組對文件權限的集合就形成了該文件的存取控制表，如圖7.21所示。圖7.21存取控制表每個文件都有一張存取控制表。在實現(xiàn)時，該表存放在文件說明中，也就是