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

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