操作系統(tǒng)文原理6

第六章

文件系統(tǒng)程序和數(shù)據(jù)以文件的形式保留在外存中。本章主要討論文件的組織結(jié)構(gòu)，共享與保護(hù)以及文件系統(tǒng)空間管理。6．1

文件和文件系統(tǒng)文件系統(tǒng)的功能實(shí)現(xiàn)按名存取文件的物理結(jié)構(gòu)文件信息的檢索文件的共享和保護(hù)文件組織形式數(shù)據(jù)項(xiàng)：最低級(jí)的數(shù)據(jù)組織形式。基本數(shù)據(jù)項(xiàng)：一個(gè)對(duì)象的某種屬性的字符集，是數(shù)據(jù)組織中可以命名的最小邏輯單位。組合數(shù)據(jù)項(xiàng)：一個(gè)對(duì)象的若干個(gè)基本數(shù)據(jù)項(xiàng)的組合。記錄：一組相關(guān)數(shù)據(jù)項(xiàng)的集合。文件：文件是一個(gè)具有符號(hào)名字的一組相關(guān)元素的有序集合。有結(jié)構(gòu)文件（定長(zhǎng)和變長(zhǎng)文件）和無(wú)結(jié)構(gòu)文件（流式文件）文件的常用屬性文件類型文件長(zhǎng)度文件的物理位置文件的存取控制文件的建立時(shí)間文件的類型按文件的性質(zhì)和用途分為：系統(tǒng)文件，庫(kù)文件，用戶文件按文件中數(shù)據(jù)的形式分為：源文件、目標(biāo)文件、可執(zhí)行文件按組織形式分為：普通文件，目錄文件，特殊文件按文件的存取控制屬性分為：只讀，讀寫文件、只執(zhí)行文件。按文件的物理結(jié)構(gòu)分類：順序文件、鏈接文件、索引文件。文件系統(tǒng)OS中負(fù)責(zé)管理和存取文件信息的軟件機(jī)構(gòu)。負(fù)責(zé)文件的建立，撤消，存入，讀寫，修改和復(fù)制，還負(fù)責(zé)完成對(duì)文件的按名存取和進(jìn)行存取控制。使用文件系統(tǒng)的優(yōu)點(diǎn)使用的方便性數(shù)據(jù)的安全性接口的統(tǒng)一性文件系統(tǒng)模型用戶（程序）文件存儲(chǔ)空間的管理；文件目錄的管理；邏輯地址到物理地址的轉(zhuǎn)換；文件讀、寫管理；文件的共享與保護(hù)文件系統(tǒng)的模型對(duì)象及其屬性說明：文件、目錄和磁盤存儲(chǔ)空間。對(duì)對(duì)象操縱和管理的軟件集合：文件存儲(chǔ)空間、目錄的管理、從文件邏輯地址到系統(tǒng)物理地址的轉(zhuǎn)換、對(duì)文件的讀、寫及共享，保護(hù)等。文件系統(tǒng)的接口：命令接口和程序接口。文件操作

對(duì)文件最基本操作：創(chuàng)建、刪除、讀、寫截?cái)?、設(shè)置文件的讀寫位置。對(duì)文件“打開”和“關(guān)閉”O(jiān)S對(duì)文件的一般操作步驟：1、檢索文件目錄，找到指定文件的屬性及在外存上的位置；

2、對(duì)文件施加相應(yīng)的讀、寫操作。

打開(Open)：指系統(tǒng)將指定文件的屬性從外存拷貝到內(nèi)存打開文件表的一個(gè)表目中，并將表目的編號(hào)返回給用戶。

關(guān)閉（Close）：將把相應(yīng)的文件從打開文件表中的表目上刪除掉。6．2

文件的邏輯結(jié)構(gòu)

文件的邏輯結(jié)構(gòu)（文件的組織）：從用戶角度看到的文件組織形式，也就是它的記錄結(jié)構(gòu)，用戶可以直接處理。它獨(dú)立于文件物理特性。

文件的物理結(jié)構(gòu)（文件的存儲(chǔ)結(jié)構(gòu)）：文件在外存上的存儲(chǔ)組織形式，一般由操作系統(tǒng)決定和使用。它與存儲(chǔ)介質(zhì)有關(guān)，同時(shí)與外存的分配方式有關(guān)。邏輯結(jié)構(gòu)的類型（記錄式文件和流式文件）有結(jié)構(gòu)文件：定長(zhǎng)記錄和變長(zhǎng)記錄記錄的組織形式順序文件、索引文件、索引順序文件流式文件它是有序字符的集合，文件長(zhǎng)度等于該文件所包含的字符數(shù)。順序文件順序文件是記錄式文件串結(jié)構(gòu)（連續(xù)結(jié)構(gòu)）：按記錄生成的先后順序連續(xù)排列的邏輯結(jié)構(gòu)。順序結(jié)構(gòu)：把文件中的鍵（關(guān)鍵字）按規(guī)定的順序排列起來。使用各種查找算法可實(shí)現(xiàn)高效檢索。存取方法順?wptr=wptr+L；R序0

存取法R記1

錄的讀寫…?定長(zhǎng)：Rirptr=rptr+L；rptr變長(zhǎng)記錄不定長(zhǎng)：rptr=rptr+Li；wptr=wptr+Li；rptr節(jié)保留該記L0

用一字錄長(zhǎng)度R0L1R1…LiRi

索引文件：為文件中所有記錄建立一張索引表，每個(gè)記錄對(duì)應(yīng)一索引表項(xiàng)，用于記錄該記錄的

長(zhǎng)度及指向該記錄的指針（指向該記錄在邏輯

地址空間的首址）

索引順序結(jié)構(gòu)：將順序文件中所有記錄分為若干個(gè)組；為順序文件建立一張索引表，在索引表中為每組的第一個(gè)記錄建立一個(gè)索引項(xiàng)，其中含有該記錄的鍵值和指向該記錄的指針。

直接文件：根據(jù)給定的記錄鍵值，直接獲得指定記錄的物理地址。哈希（hash)文件：目前最為廣泛的一種直接文件，它利用Hash函數(shù)將記錄鍵值轉(zhuǎn)換為相應(yīng)記錄的地址。6．3

外存分配方法外存分配方式：連續(xù)分配、鏈接分配、索引分配。連續(xù)分配（順序文件）分配與回收分配：把一個(gè)邏輯上連續(xù)的文件信息依次存放在物理塊中?；厥眨核槠韱栴}。特點(diǎn)優(yōu)點(diǎn)：順序訪問容易，能很快進(jìn)行存取。缺點(diǎn)：要求有連續(xù)的存儲(chǔ)空間；不便于記錄的增，刪操作；必須事先知道文件長(zhǎng)度，不能動(dòng)態(tài)增長(zhǎng)，存在碎片問題。鏈接分配（串聯(lián)文件）：文件被離散放到磁盤的盤塊中。隱式鏈接在文件的目錄中記錄該文件的第一和最后一個(gè)盤塊的指針，每個(gè)塊中的指針指向文件的下一物理塊號(hào)。優(yōu)點(diǎn)：文件可動(dòng)態(tài)增長(zhǎng)，不需指明文件長(zhǎng)度，便于增刪記錄，節(jié)約空間。缺點(diǎn)：只適合順序存取，不宜于直接存取，查找效率低。由于設(shè)置鏈接字而破壞了物理信息的完整。改進(jìn)：將幾個(gè)盤塊組成簇（cluster），以簇為位分配。顯示鏈接將鏈接文件各物理塊的指針顯示地放在內(nèi)存的一張鏈接表中。該表整個(gè)磁盤中設(shè)一張，表的序號(hào)為盤塊號(hào)，在文件的FCB的物理地址中填寫其鏈?zhǔn)字羔標(biāo)鶎?duì)應(yīng)的盤塊號(hào)。FAT（File

Allocation

Table）：文件分配表，整個(gè)磁盤設(shè)置一張，放在內(nèi)存中。缺點(diǎn)：不能直接存??；FAT占較大內(nèi)存空間。FAT和NTFS技術(shù)FAT12、FAT16，F(xiàn)AT32以及NTFS的文件分配基本上都是采用類似顯示鏈接方法。1、FAT12：（每個(gè)表項(xiàng)占12bit）每個(gè)分區(qū)中都配有兩張文件分配表FAT1和FAT2，在FAT的每個(gè)表項(xiàng)中存放下一個(gè)盤塊號(hào)，而將文件的第一個(gè)盤塊號(hào)放在自己的FCB中。整個(gè)系統(tǒng)有一張文件分配表FAT。在FAT的每個(gè)表項(xiàng)中存放下一個(gè)盤塊號(hào)。簇：由一組連續(xù)的扇區(qū)構(gòu)成，在FAT中作為一個(gè)虛擬扇區(qū)，大小一般是2n個(gè)盤塊。FAT和NTFS技術(shù)2、FAT16：每個(gè)表項(xiàng)16位在FAT16中，每個(gè)簇中可以有的盤塊數(shù)可為4、8、16、32、64FAT16和FAT32都不支持長(zhǎng)文件名。3、FAT32：每個(gè)表項(xiàng)占32bit.在FAT32中，每個(gè)簇固定為4KB。FAT32比FAT16支持更小簇的更大的磁盤容量。同時(shí)支持長(zhǎng)文件名。FAT和NTFS技術(shù)4、NTFSNTFS使用64位磁盤地址；可以很好支持長(zhǎng)文件名，單個(gè)文件名限制在255個(gè)字符內(nèi)，全路徑名最長(zhǎng)為32767字符；具有系統(tǒng)容錯(cuò)功能，提供數(shù)據(jù)一致性。NTFS以簇作為磁盤分配的基本單位，具有了與磁盤物理扇區(qū)大小無(wú)關(guān)的獨(dú)立性。卷上簇的大小稱為卷因子，為盤塊的2n倍，最大64KB索引文件要求為每一文件建立一張索引表。每個(gè)表目指出文件邏輯記錄所在的物理塊號(hào)。特點(diǎn)：方便地進(jìn)行隨機(jī)存?。辉黾恿怂饕淼目臻g開銷，增加一次訪問操作。單級(jí)索引（串聯(lián)文件方式組織）多級(jí)索引（多重索引方式組織）綜合組織方式（混合索引）把索引表的頭幾項(xiàng)設(shè)計(jì)為直接尋址方式，存放物理塊號(hào)，后幾項(xiàng)設(shè)計(jì)成多重索引。綜合組織方式適用于順序存取和隨機(jī)存取。直接地址：

iaddr(0)

—

iaddr(9) 用于小于10盤塊的文件一次間接地址：iaddr(10)大、中型文件二次間接地址：iaddr(11)三次間接地址：iaddr(12)大、超大型文件6．3

文件目錄管理

一個(gè)文件的說明信息稱為該文件的目錄。用戶向系統(tǒng)提供符號(hào)名，系統(tǒng)根據(jù)文件的符號(hào)名找到它的物理地址。

功能：實(shí)現(xiàn)文件的按名存取，實(shí)現(xiàn)符號(hào)名與具體物理地址之間的轉(zhuǎn)換，文件的共享和保護(hù)。文件控制塊和索引結(jié)點(diǎn)文件的組成：文件說明（FCB）和文件體。FCB即為文件的目錄。文件與FCB一一對(duì)應(yīng)，F(xiàn)CB的有序集合通常稱為文件目錄。一個(gè)文件目錄也被看為一文件，稱為一個(gè)目錄文件。文件控制塊（File

Control

Block）基本信息：文件名、物理位置、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)。存取控制信息：存取權(quán)限使用信息：建立和修改的時(shí)間，當(dāng)前使用文件的進(jìn)程情況等。索引結(jié)點(diǎn)文件目錄的缺陷：FCB中有許多信息與文件的查找無(wú)關(guān)。索引結(jié)點(diǎn)的引入目錄：文件名和指向i結(jié)點(diǎn)的指針i結(jié)點(diǎn)：文件描述信息。文件名索引結(jié)點(diǎn)編號(hào)文件名1PTR1文件名2PTR2……磁盤索引結(jié)點(diǎn)：每個(gè)文件有唯一的磁盤索引結(jié)點(diǎn)。文件主標(biāo)識(shí)：擁有文件的個(gè)人或小組的標(biāo)識(shí)符。文件類型：正規(guī)文件、目錄文件、特別文件。文件存取權(quán)限：各類用戶對(duì)文件的存取權(quán)限。

文件物理地址：直接或間接的給出數(shù)據(jù)文件的盤塊號(hào)。文件長(zhǎng)度：文件的字節(jié)數(shù)。

文件連接計(jì)數(shù)：所有共享該文件的進(jìn)程（用戶）數(shù)。

文件存取時(shí)間：本文件最近被進(jìn)程存取的時(shí)間、最近被修改的時(shí)間及索引結(jié)點(diǎn)最近被修改的時(shí)間內(nèi)存索引結(jié)點(diǎn)（存放在內(nèi)存中的索引結(jié)點(diǎn)）文件被打開后，系統(tǒng)要將磁盤索引結(jié)點(diǎn)拷貝到內(nèi)存的索引結(jié)點(diǎn)中。索引結(jié)點(diǎn)編號(hào)：標(biāo)識(shí)內(nèi)存索引結(jié)點(diǎn)狀態(tài)：該結(jié)點(diǎn)i是否上鎖或被修改訪問計(jì)數(shù)：使用該結(jié)點(diǎn)的進(jìn)程數(shù)文件所在設(shè)備的邏輯設(shè)備號(hào)鏈接指針：空閑鏈表、散列隊(duì)列指針單級(jí)目錄（系統(tǒng)中只有一張目錄表）目錄內(nèi)容：文件名、物理地址、其它屬性。文件訪問過程：直接查表創(chuàng)建和刪除文件：直接修改目錄表項(xiàng)存在的問題重名問題：別名問題：文件數(shù)量過多時(shí)，查找效率低。兩級(jí)目錄結(jié)構(gòu)：系統(tǒng)由主目錄（MFD）和用戶目錄（UFD）構(gòu)成。文件的建立和文件的刪除：文件的查找：主目錄項(xiàng)+用戶目錄項(xiàng)樹型目錄多級(jí)樹型目錄結(jié)構(gòu)（結(jié)點(diǎn)與目錄）文件路徑名（路徑的唯一性）當(dāng)前目錄（工作目錄）增加和刪除目錄（刪除目錄，同時(shí)要?jiǎng)h除該目錄下所有文件和目錄的目錄項(xiàng)，同時(shí)使上一級(jí)目錄中對(duì)應(yīng)的目錄項(xiàng)為空）目錄的查詢技術(shù)過程根據(jù)文件名（全名）找到其FCB或索引結(jié)點(diǎn)；查找FCB或索引結(jié)點(diǎn)中的文件物理地址（盤塊號(hào)），換算為物理位置；啟動(dòng)磁盤驅(qū)動(dòng)程序，將文件讀入內(nèi)存。檢索方法順序查找法：二分查找法：Hash法：6．4

文件存儲(chǔ)空間管理

系統(tǒng)應(yīng)能自動(dòng)地為用戶分配存儲(chǔ)空間，管理系統(tǒng)和用戶的存儲(chǔ)空間，實(shí)現(xiàn)按名存取。

文件存儲(chǔ)空間的管理包括空閑塊的組織分配和回收?？臻e表空閑表把一個(gè)連續(xù)未分配區(qū)域稱為“空閑文件”，系統(tǒng)為所有“空閑文件”單獨(dú)建立一個(gè)目錄。表目?jī)?nèi)容：序號(hào)，第一個(gè)空白塊號(hào)，空白塊個(gè)數(shù)?？臻g分配和回收序號(hào)第一空閑盤塊號(hào)空閑盤塊數(shù)124293--空閑鏈表法空閑盤塊鏈（以盤塊為鏈的基本單位）分配和釋放順序：從頭分配，從尾回收。缺點(diǎn)：盤塊鏈可能很長(zhǎng)?？臻e盤區(qū)鏈（以空閑盤塊區(qū)為鏈的基本單位）分配：首次適應(yīng)算法回收：分配和回收的過程較復(fù)雜，且存在拼接問題位示圖為文件存儲(chǔ)器存儲(chǔ)空間建立一張位示圖，用以反映整個(gè)空間的分配情況。簡(jiǎn)單，速度快，占一定的空間。盤塊號(hào)與位示圖行列的分配與回收的轉(zhuǎn)換公式：成組鏈接法實(shí)現(xiàn)方法對(duì)所有的空白塊從尾倒著向前分組，每

組的塊數(shù)及相應(yīng)塊號(hào)記錄在前一組的第一塊中。(第一組99塊，隨后每組100塊)，最后一組（不足100塊）的數(shù)據(jù)登記在空閑盤塊棧（卷資源表）中。第二組的0號(hào)單元的值仍為100，1號(hào)單元值為0

（文卷卷尾標(biāo)志），表示無(wú)空閑塊可分配。假定系統(tǒng)中有349塊空閑盤塊：其組織方式如下：分配和釋放系統(tǒng)工作后，把磁盤文件卷的卷資源復(fù)制到內(nèi)存指定區(qū)域。資源表中登記空閑塊號(hào)的區(qū)域是一種棧結(jié)構(gòu)。其中，記載總塊數(shù)作為該空白塊棧的指針ptr。分配時(shí)，ptr-1，然后取出對(duì)應(yīng)項(xiàng)作為這次申請(qǐng)得到的物理塊。如此下去，直到棧底。當(dāng)ptr=0時(shí)，續(xù)入下一組的塊號(hào)及總數(shù)，并把該塊分配出去。當(dāng)ptr=0，且相應(yīng)此表目中的值為0時(shí)，表示遇到卷尾標(biāo)志。當(dāng)回收時(shí)，先登記塊號(hào)，然后ptr+1，當(dāng)填滿一組后，再回收一塊時(shí)，把前一組的內(nèi)容記入該塊內(nèi)，置ptr=0，并把這一塊的塊號(hào)記入相應(yīng)表目中。特點(diǎn)空白塊號(hào)的登記不占用額外空間。

絕大部分分配和釋放工作都在主存進(jìn)行。把總塊數(shù)作為空白塊棧的指針使用，是理想的存儲(chǔ)結(jié)構(gòu)。效率高。6．5

文件共享早期共享方法繞道法（當(dāng)訪問內(nèi)容不在本目錄下，則每一次都要指明訪問路徑）連訪法（鏈接法）

一個(gè)目錄中的表目直接指向另一個(gè)目錄表目，在要訪問的表目之間直接建立一條鏈接。

在FCB中必須增加“連訪屬性”和“用戶計(jì)數(shù)”項(xiàng)。基于索引結(jié)點(diǎn)的共享方法樹型目錄中文件共享的問題：將共享文件鏈接到兩個(gè)用戶的目錄中。用索引結(jié)點(diǎn)實(shí)現(xiàn)文件共享指向相同的索引結(jié)點(diǎn)鏈接計(jì)數(shù)器count文件共享的過程基于索引的共享共享的鏈接過程利用符號(hào)鏈實(shí)現(xiàn)文件共享實(shí)現(xiàn)B共享C的文件F，由系統(tǒng)創(chuàng)建LINK類型的新文件（也命名為F），它包含被C的F文件的路徑名（符號(hào)鏈），并寫入B的用戶目錄中。

只有文件主才擁有指向索引結(jié)點(diǎn)的指針，其它共享用戶通過路徑名訪問（可以解決指針懸空的問題）。問題

訪問速度慢；鏈接文件也要建立索引結(jié)點(diǎn)；同一文件有不同的文件名，導(dǎo)致多個(gè)副本存在。6．6

文件存取控制文件保護(hù)文件保護(hù)機(jī)構(gòu)的功能存取驗(yàn)證模塊的基本任務(wù)審定用戶的存取權(quán)限；比較用戶存取權(quán)限和本次存取要求；比較本次存取要求和被訪問文件的存取保護(hù)信息。保護(hù)域進(jìn)程僅在保護(hù)域內(nèi)執(zhí)行操作，同時(shí)保護(hù)域指明了進(jìn)程所能操作的對(duì)象。進(jìn)程與域的關(guān)系：靜態(tài)聯(lián)系：可用資源集在進(jìn)程的整個(gè)生命周期內(nèi)是固定的，在該方式下，應(yīng)允許修改域的內(nèi)容。動(dòng)態(tài)聯(lián)系：可用資源集在其整個(gè)生命周期內(nèi)是變化的。在該方式下，允許進(jìn)程

在不同時(shí)期，從一個(gè)域切換到另一個(gè)域。訪問（存取控制）矩陣實(shí)現(xiàn)方法用一個(gè)二維矩陣來實(shí)現(xiàn)存取控制，一維是所有的域（用戶或進(jìn)程），另一維列出全部文件。每個(gè)元素表示某一用戶對(duì)某一文件的存取控制權(quán)限。訪問（存取）控制表把有存取要求的用戶按某種關(guān)系或工程項(xiàng)目的類別分為若干組，同時(shí)規(guī)定每組的存取權(quán)限，得到文件的存取控制表。訪問權(quán)限表以用戶或用戶組為單位建立存取控制表，稱為用戶權(quán)限表。將一個(gè)用戶（組）所要存取的文件名集中起來存入一張表中，每個(gè)表目指明用戶對(duì)相應(yīng)文件的存取權(quán)限。分級(jí)安全管理（一般分為4級(jí)）系統(tǒng)級(jí)防止用戶非法進(jìn)入系統(tǒng)：注冊(cè)（系統(tǒng)管理員完成）、登錄（用戶完成）等。用戶級(jí)用戶分類的兩種類型文件主、伙伴和一般用戶。超級(jí)用戶、系統(tǒng)操作員、用戶和顧客。文件訪問權(quán)限：建立(C)、刪除(D)、打開(O)、讀(R)、寫(W)、查詢(S)、修改(M)和父權(quán)(P)。目錄級(jí)只有系統(tǒng)核心具有寫目錄的權(quán)利。保護(hù)系統(tǒng)目錄，與用戶權(quán)限無(wú)關(guān)。文件級(jí)通過對(duì)文件屬性（8種常用屬性）的設(shè)置，來控