華東理工815操作系統(tǒng)第20講

課程主要內容操作系統(tǒng)引論（第1章）進程管理（第2-3章）存儲器管理（第4章）設備管理（第5章）文件管理（第6章）操作系統(tǒng)接口（第7章）UNIX操作系統(tǒng)（第10章）第6章文件管理文件系統(tǒng)的功能/需解決的問題從系統(tǒng)角度看：負責為用戶建立、刪除、讀、寫、修改和復制文件。從用戶的角度看：實現了按名存取文件系統(tǒng)的功能：提供高效、快速、方便的信息存儲和訪問功能。文件和文件系統(tǒng)文件邏輯結構外存分配方式目錄管理文件存儲空間的管理文件共享與文件保護數據一致性控制第6章文件管理文件、記錄和數據項（域或字段---數據的基本單位）文件類型和文件系統(tǒng)模型文件操作6.1文件和文件系統(tǒng)一、數據的組成數據項（最低級的數據組織形式）基本數據項（最小的邏輯數據單位）用于描述一個對象的某種屬性的字符集，是數據組織中可以命名的最小邏輯單位組合數據項由若干個基本數據項組成，簡稱組項記錄是一組相關數據項的集合，

用于描述一個對象在某方面的屬性文件例如：用于描述學生的基本數據項-學號、姓名、年齡等工資是個組項，由基本工資、工齡工資和獎勵工資等基本項組成文件文件在文件系統(tǒng)中是一個最大的數據單位是指記錄在外存上的具有文件名的一組相關信息的集合。可分為有結構文件和無結構文件兩種。有結構文件由若干個相關記錄組成，而無結構文件則被看成一個字符流。文件屬性文件名、文件類型、文件長度、文件的物理位置、文件的建立日期以及用戶對該文件的存取權限等文件、記錄和數據項間的層次關系文件記錄1記錄n記錄2…數據項1數據項2數據項n…二、文件類型（1）

---文件名.擴展名按用途分類系統(tǒng)文件-由系統(tǒng)軟件構成的文件用戶文件-用戶的源代碼、目標文件、可執(zhí)行文件或數據庫文件-由標準子例程和常用的例程構成按數據形式分類源文件目標文件可執(zhí)行文件按存取控制屬性只讀文件讀寫文件只執(zhí)行文件二、文件類型（2）

---文件名.擴展名按組織形式和處理方式分類普通文件-由ASCII碼或二進制碼組成的字符文件目錄文件-由文件目錄組成，用來管理和實現文件系統(tǒng)功能的系統(tǒng)文件特殊文件-特指系統(tǒng)中的各類I/O設備按文件的邏輯結構分類有結構文件（記錄式文件）無結構文件（流式文件）按文件的物理結構分類順序文件鏈接文件索引文件三、文件系統(tǒng)模型（1）文件系統(tǒng)接口（命令接口、系統(tǒng)調用接口）對對象操縱和管理的軟件集合對象(文件、目錄及磁盤存儲空間)及其屬性說明用戶（程序）對文件存儲空間的管理對文件目錄的管理將文件的邏輯地址轉換為物理地址的機制對文件的讀和寫管理對文件的共享和保護三、文件系統(tǒng)模型（2）1)對象及其屬性文件管理系統(tǒng)管理的對象有：①文件：它作為文件管理的直接對象。②目錄：為了方便用戶對文件的存取和檢索，在文件系統(tǒng)中必須配置目錄。對目錄的組織和管理是方便用戶和提高對文件存取速度的關鍵。③磁盤(磁帶)存儲空間：文件和目錄必定占用存儲空間，對這部分空間的有效管理，不僅能提高外存的利用率，而且能提高對文件的存取速度。三、文件系統(tǒng)模型（3）2)對對象操縱和管理的軟件集合這是文件管理系統(tǒng)的核心部分。文件系統(tǒng)的功能大多是在這一層實現的，其中包括：對文件存儲空間的管理對文件目錄的管理用于將文件的邏輯地址轉換為物理地址的機制對文件讀和寫的管理對文件的共享與保護等功能三、文件系統(tǒng)模型（4）3)文件系統(tǒng)的接口為方便用戶使用文件系統(tǒng)，文件系統(tǒng)通常向用戶提供兩種類型的接口：

①

命令接口。這是指作為用戶與文件系統(tǒng)交互的接口。用戶可通過鍵盤終端鍵入命令，取得文件系統(tǒng)的服務。

②

程序接口（系統(tǒng)調用接口）。這是指作為用戶程序與文件系統(tǒng)的接口。用戶程序可通過系統(tǒng)調用來取得文件系統(tǒng)的服務。四、文件操作

用戶通過文件系統(tǒng)所提供的系統(tǒng)調用實施對文件的操作。最基本的操作有：對文件的操作最基本的：創(chuàng)建、打開、關閉、刪除、讀、寫、截斷、設置文件的讀寫位置（將順序存取改為隨機存?。┢渌模何募傩灶惒僮?、目錄類操作四、文件操作文件的“打開”和“關閉”操作

“打開”：系統(tǒng)將文件的屬性（目錄信息）從外存復制到內存打開文件表中，并返回該表目的編號給用戶，建立了用戶與文件間的聯系。以后若再訪問此文件，則利用編號直接在內存中檢索，從而節(jié)省大量的檢索開銷，提高了文件的操作速度。

“關閉”：當用戶不再需要對該文件的操作時，系統(tǒng)利用關閉文件將文件的屬性從內存打開表中刪除，從而切斷用戶與文件之間的聯系。6.2文件邏輯結構

文件系統(tǒng)設計的關鍵要素：

對任一文件存在著兩種形式的結構：文件的邏輯結構（文件的組織）從用戶觀點出發(fā)，所觀察到的文件組織形式，是用戶可以直接處理的數據及結構，它獨立于物理特性。文件的物理結構（文件的存儲結構）是指文件在外存上的存儲組織形式，與存儲介質的存儲性能有關，還和所采用的外存分配方式有關。（分為順序、鏈接及索引結構）注：文件的邏輯結構和物理結構都將影響文件的檢索速度。記錄構成文件的方法將文件存儲到外存的方法6.2文件邏輯結構

對文件的邏輯結構提出的基本要求：提高檢索速度；便于修改；降低文件存儲費用。文件邏輯結構的類型順序文件索引文件索引順序文件一、文件邏輯結構的類型（1）有結構的記錄式文件文件構成：由一個以上的記錄構成。記錄長度：分為定長和變長。分類（按記錄的組織方式）：

順序文件-定長（也可以是變長）記錄按某種順序排列形成

索引文件-針對變長記錄

索引順序文件-為文件建立一張索引表，為每組記錄的第一個記錄設置一個表項一、文件邏輯結構的類型（2）無結構的流式文件文件構成：由字符流構成。大量的源程序、可執(zhí)行文件、庫函數等，所采用的就是無結構的文件形式，即流式文件。長度：以字節(jié)為單位（通用計算機尋址的最小單位）訪問：對流式文件的訪問，則是采用讀寫指針來指出下一個要訪問的字符。注：在UNIX系統(tǒng)中，所有的文件都被看作是流式文件；即使是有結構文件，也被視為流式文件；系統(tǒng)不對文件進行格式處理?？梢园蚜魇轿募醋魇怯涗浭轿募囊粋€特例。好處：更加方便、OS代碼更加可靠、靈活，用戶編程也更加方便有的計算機支持半字節(jié)尋址(NibbleAddressing)二、順序文件（1）邏輯記錄的排序串結構：記錄順序與關鍵字無關，按存入時間的先后排列。最先存入的記錄作為第一個記錄，其次存入的為第二個記錄，……

依此類推。順序結構：所有記錄按關鍵字（詞）排列?？梢园搓P鍵詞的長短從小到大排序，也可以從大到小排序；或按其英文字母順序排序。對順序文件的讀、寫操作記錄為定長的順序文件記錄為變長的順序文件二、順序文件（2）圖6-3定長和變長記錄文件其中Li占用一個字節(jié)，用來指明記錄i的長度順序文件的優(yōu)缺點優(yōu)點順序存取速度較快（批量存?。?。對定長記錄，還可方便實現直接存取（隨機存?。?。只有順序文件才能存儲在磁帶上，并能有效地工作。缺點對變長記錄，直接存取低效。例如，有一個含有104個記錄的順序文件，如果對它采用順序查找法去查找一個指定的記錄，則平均需要查找5×103個記錄；如果是可變長記錄的順序文件，則為查找一個記錄所需付出的開銷將更大，這就限制了順序文件的長度。不利于文件的動態(tài)增長。文件的訪問方式：順序訪問和隨機訪問（直接訪問）三、索引文件引入為解決對變長記錄文件難以進行直接存取的問題。索引文件為變長記錄文件建立一張索引表。索引號長度m指針ptr0m01m1…

imi…r0r1…ri…邏輯文件索引表索引文件的特點優(yōu)點通過索引表可方便地實現直接存取，具有較快的檢索速度。易于進行文件的增刪。缺點索引表的使用增加了存儲費用；索引表的查找策略對文件系統(tǒng)的效率影響很大。注：若索引表很大，可建立多級索引四、索引順序文件引入為解決變長記錄文件的直接存取低效且存儲費用增加的問題。索引文件為順序文件建立一張索引表。索引順序文件的特點優(yōu)點通過索引表可方便地實現直接存取，具有較快的檢索速度。（檢索過程見P212）易于進行文件的增刪。缺點索引表的查找策略對文件系統(tǒng)的效率影響很大.五、直接文件和哈希文件（1）1.直接文件對于直接文件，則可根據給定的記錄鍵值，直接獲得指定記錄的物理地址。換言之，記錄鍵值本身就決定了記錄的物理地址。這種由記錄鍵值到記錄物理地址的轉換被稱為鍵值轉換(Keytoaddresstransformation)。組織直接文件的關鍵，在于用什么方法進行從記錄值到物理地址的轉換。2.哈希文件是目前應用最為廣泛的一種直接文件。五、直接文件和哈希文件（2）A=H(K)Hash文件的邏輯結構6.3

外存分配方式文件的物理結構即文件的外存分配方式，是從系統(tǒng)的角度來看文件，從文件在物理介質上的存放方式來研究文件。要考慮的主要問題：目前常用的外存分配方法：（1）連續(xù)分配（順序分配）－>順序文件結構（2）鏈接分配－>鏈接文件結構（3）索引分配－>索引文件結構如何有效地利用外存空間如何提高對文件的訪問速度（1）外存分配方式-連續(xù)/順序分配（1）圖6-7磁盤空間的連續(xù)分配

采用連續(xù)分配方式時，可把邏輯文件中的記錄順序地存儲到鄰接的各個物理盤塊中，這樣所形成的文件結構叫做順序文件結構，此時的物理文件稱為順序文件。（1）外存分配方式-連續(xù)/順序分配（2）為每一個文件分配一片連續(xù)的磁盤塊只需要起始塊號和長度，適用于預分配方法可以隨機存取文件不能增長從邏輯地址映射到物理地址較簡單浪費空間：動態(tài)存儲分配問題可以通過緊縮(compact)將外存空閑空間合并成連續(xù)的區(qū)域。連續(xù)/順序分配的主要優(yōu)缺點主要優(yōu)點順序訪問容易順序訪問速度快主要缺點要求有連續(xù)的存儲空間必須事先知道文件的長度（2）外存分配方式-鏈接分配（1）1.隱式鏈接圖6-8磁盤空間的鏈接式分配

采用鏈接分配方式時，可通過在每個盤塊上的鏈接指針，將同屬于一個文件的多個離散的盤塊鏈接成一個鏈表，這樣形成的文件稱為鏈接文件。（2）外存分配方式-鏈接分配（2）每個文件是磁盤塊的鏈接列表：塊可以分散在磁盤各處按所需分配磁盤塊，鏈接在一起在每個塊中有指向下一個塊的指針只需要起始地址可以通過合并(consolidation)將幾個盤塊組成一個簇，以簇為單位進行盤塊分配，以提高I/O訪問性能。Block(512B)=Pointer(4B)(508B)（2）外存分配方式-鏈接分配（3）2.顯式鏈接圖6-9顯式鏈接結構把用于鏈接的指針顯式存放在內存的一張表中，查找在內存中進行。整個磁盤設置一張表。文件分配表FAT—圖6-10文件分配表FAT用于鏈接文件各物理塊的鏈接指針，顯式地存放在內存的一張鏈接表中。該表在整個磁盤僅設置一張。表序號為整個磁盤的物理塊號（0~(n-1)）表項存放鏈接指針，即下一個塊號。文件的首塊號存入相應文件的目錄項（FCB）中。查找是在內存的FAT中進行，故提高了檢索速度，同時又減少磁盤的訪問次數。被MS-DOS和OS/2等所采用。P217圖6-10鏈接分配的優(yōu)缺點優(yōu)點

1、無外部碎片，沒有磁盤空間浪費

2、無需事先知道文件大小。文件動態(tài)增長時，可動態(tài)分配空閑盤塊。對文件的增、刪、改十分方便。缺點

1、不能支持高效隨機/直接訪問，僅適合于順序存取

2、需為指針分配空間。（隱式鏈接）

3、可靠性較低（指針丟失/損壞）

4、文件分配表FAT（顯式鏈接）

FAT需占用較大的內存空間（如何計算FAT表所占的內存空間：P217）。

計算FAT表所占的內存空間整個系統(tǒng)有一張FAT表，在FAT的每個表項中存放下一個盤塊號。對于1.2M的軟盤，每個盤塊的大小為512B，在FAT表中共有2.4K個表項，每個FAT表項占12位，所以FAT表占用3.6KB的存儲空間。若磁盤大小為20GB，盤塊大小為4KB，計算FAT表的大小。若給作業(yè)A依次分配了3、6、2、5四個物理塊，畫出分配后的FAT圖。（3）外存分配方式-索引分配（1）鏈接分配方式雖然解決了連續(xù)分配方式所存在的問題，但又出現了另外兩個問題，即：

(1)不能支持高效的直接存取。要對一個較大的文件進行直接存取，必須首先在FAT中順序地查找許多盤塊號。

(2)FAT需占用較大的內存空間。為每一個文件分配一個索引塊（表），再把分配給該文件的所有塊號，都記錄在該索引塊中。故索引塊就是一個含有許多塊號地址的數組。該索引塊的地址由該文件的目錄項指出。支持隨機/直接存取。不會產生外部碎片。適用于文件較大時。（3）外存分配方式-索引分配（2）圖6-12索引分配方式1.單級索引分配（3）外存分配方式-索引分配（3）2.多級索引分配圖6-13兩級索引分配（3）外存分配方式-索引分配（4）

假設每個盤塊大小為1KB，每個盤塊號占4個字節(jié)，則在一個索引塊中可放256個文件物理塊的盤塊號。在兩級索引時，最多可包含的存放文件的盤塊的盤塊號總數為256*256=64K個盤塊號?？梢缘贸觯翰捎脙杉壦饕龝r，所允許的文件最大長度為64MB。

（3）外存分配方式-索引分配（5）3.混合索引方式

UNIX文件系統(tǒng)采用的是混合索引結構(綜合模式)。每個文件的索引表為13個索引項。最前面10項直接登記存放文件信息的物理塊號（直接尋址） 如果文件大于10塊，則利用第11項指向一個物理塊，假設每個盤塊大小為4KB，每個盤塊號占4個字節(jié)，該塊中最多可放1K個盤塊號（一次間接尋址）。對于更大的文件還可利用第12和第13項作為二次和三次間接尋址。 （3）外存分配方式-索引分配（6）圖6-14混合索引方式(1)直接地址為了提高對文件的檢索速度，在索引結點中可設置10個直接地址項，即用iaddr(0)~iaddr(9)來存放直接地址。即每項中所存放的是該文件數據所在盤塊的盤塊號。假如每個盤塊的大小為4KB，當文件不大于40KB時，就可以直接從索引結點中讀出該文件的全部盤塊號。（3）外存分配方式-索引分配（7）(2)一次間接地址對于大、中型文件，只采用直接地址是不現實的?？稍倮盟饕Y點中的地址項iaddr(10)來提供一次間接地址。這種方式的實質就是一級索引分配方式。圖中的一次間址塊也就是索引塊，系統(tǒng)將分配給文件的多個盤塊號記入其中。在一次間址塊中可存放1K個盤塊號（4KB/4B)，因而允許文件長達4MB。（3）外存分配方式-索引分配（8）(3)多次間接地址當文件長度大于4MB+40KB時(一次間址與10個直接地址項)，系統(tǒng)還須采用二次間址分配方式。這時，用地址項iaddr(11)提供二次間接地址。該方式的實質是兩級索引分配方式。系統(tǒng)此時是在二次間址塊中記入所有一次間址塊的盤號。在采用二次間址方式時，文件最大長度可達4GB（4KB*1K*1K）。同理，地址項iaddr(12)作為三次間接地址，其所允許的文件最大長度可達4TB（4KB*1K*1K*1K）。（3）外存分配方式-索引分配（9）6.4

目錄管理對文件目錄的管理要求實現“按名存取”提高對目錄的檢索速度文件共享允許文件重名6.4目錄管理文件控制塊和索引結點單級目錄結構兩級目錄結構樹型目錄結構目錄查詢技術文件控制塊和索引結點

從文件管理角度看，文件由FCB和文件體（文件本身）兩部分組成。

文件控制塊（FCB-FileControlBlock）文件控制塊是操作系統(tǒng)為管理文件而設置的數據結構，存放了文件的有關說明信息，記錄了系統(tǒng)對文件進行管理所需要的全部信息。FCB是文件存在的標志。FCB保存在文件目錄中，一個FCB就是一個目錄項。文件控制塊和索引結點文件控制塊（FCB）（續(xù)）FCB中的信息基本信息類：文件名、文件長度、類型、屬性、文件物理位置存取控制信息類：文件存取權限、用戶名、口令、共享計數使用信息類：文件的建立日期、最后修改日期、保存期限、最后訪問日期文件控制塊（FCB）文件目錄把所有的FCB組織在一起，就構成了文件目錄，即文件控制塊的有序集合。目錄項構成文件目錄的項目（目錄項就是FCB）目錄文件為了實現對文件目錄的管理，通常將文件目錄以文件的形式保存在外存，這個文件就叫目錄文件。索引結點索引結點索引結點引入設目錄文件所占的盤塊數是

N，則查找一個目錄項平均

需要調入盤塊（N+1）/2次。假設一個FCB為64B,盤塊大小為1KB，則每個盤塊中只能存放1KB/64B=16個FCB;若一個文件目錄共有640個FCB，需占用640/16=40個盤塊，平均查找一個文件需啟動磁盤20次。文件名索引結點編號文件名1文件名2…………索引結點索引結點索引結點引入在目錄檢索的過程中，只用到了文件名，僅當找到一個目錄項時，才需從該目錄項中讀出文件的物理地址。UNIX系統(tǒng)中，采用了把文件名和文件描述信息分開的方法，把文件描述信息單獨形成一個數據結構，叫索引結點。文件名索引結點編號文件名1文件名2…………索引結點索引結點索引結點引入在文件目錄中的每個目錄項

僅由文件名和指向該文件所對應的i結點（即索引結點）的指針構成。UNIX系統(tǒng)中，一個目錄項只占16個字節(jié)（14字節(jié)為文件名，2個字節(jié)為指向i結點的指針）。在1KB的盤塊中可存放1KB/16B=64個目錄項，如果一個文件目錄中共有640個目錄項，只占用640/64=10個盤塊，平均啟動磁盤10/2=5次，減少到原來（平均啟動20次）的1/4，大大節(jié)省了開銷。文件名i

結點編號索引結點索引結點磁盤索引結點存放在磁盤上的

索引結點，每個文件有唯一的磁盤索引結點。

(主標識、類型、存取權限、物理地址、長度、連接計數、存取時間)內存索引結點存放在內存上的索引結點。當文件被打開時，要將磁盤索引結點復制到內存的索引結點中，增加以下內容：

(索引結點編號、狀態(tài)、訪問計數、邏輯設備號、鏈接指針)文件名索引結點編號文件名1文件名2…………Unix系統(tǒng)磁盤索引結點中的信息單級目錄結構在整個系統(tǒng)中只建立一張目錄表優(yōu)點:簡單，易實現按名存取缺點:限制了用戶對文件的命名（即易重名）文件平均檢索時間長(查找速度慢)

不便于實現文件共享只適用于單用戶環(huán)境文件名狀態(tài)位物理地址文件其它屬性AlphaReportText……兩級目錄結構在整個系統(tǒng)中建立兩級目錄為每個用戶建立一個單獨的用戶文件目錄（UFD）系統(tǒng)中為所有用戶建立一個主文件目錄（MFD）AlphatestAlphatestWang用戶目錄ReporttesttestreportZhang用戶目錄misxbetaGao用戶目錄betamisx用戶名指向用戶目錄指針WangZhangGao主文件目錄兩級目錄結構優(yōu)點:提高了檢索目錄的速度；不同用戶目錄中可重名；不同用戶可用不同文件名來訪問系統(tǒng)中一個共享文件缺點:限制了各用戶對文件的共享增加了系統(tǒng)開銷，缺乏靈活性，無法反映真實世界復雜的文件結構形式。樹型目錄結構（1）在兩級目錄中若允許用戶建立自己的子目錄，則形成3級或多級目錄結構（即樹型目錄結構）樹型目錄結構（2）有共享的子目錄和文件樹型目錄結構路徑名訪問數據文件的一條路徑。絕對路徑、相對路徑當前目錄增加和刪除目錄優(yōu)點層次結構清晰,實現分組,便于管理和保護；解決重名問題；查找速度加快缺點查找一個文件按路徑名逐層檢查,由于每個文件都放在外存,多次訪盤影響速度目錄查詢技術數據文件（按名存?。┑牟樵儾襟E根據用戶提供的文件名，對文件目錄進行查詢，找到該文件的FCB（索引結點）根據FCB（索引結點）所記錄的磁盤盤塊號，換算出文件在磁盤上的物理位置啟動磁盤驅動程序，讀該數據文件至內存中。對目錄進行查詢的方式線性檢索法（順序檢索法）Hash方法目錄查詢技術-線性檢索法（順序檢索法）

/usr/ast/mbox圖6-20查找/usr/ast/mbox的步驟6.5

文件存儲空間的管理（1）1.空閑表法和空閑鏈表法

空閑表法

序號第一空閑盤塊號空閑盤塊數12429331554——圖6-21空閑盤塊表6.5

文件存儲空間的管理（2）1.空閑表法和空閑鏈表法

空閑鏈表法

6.5

文件存儲空間的管理（3）存儲空間的分配與回收

空閑盤區(qū)的分配與內存的動態(tài)分配類似，同樣是采用首次適應算法、循環(huán)首次適應算法等。例如，在系統(tǒng)為某新創(chuàng)建的文件分配空閑盤塊時：先順序地檢索空閑表的各表項，直至找到第一個其大小能滿足要求的空閑區(qū)；再將該盤區(qū)分配給用戶(進程)，同時修改空閑表。系統(tǒng)在對用戶所釋放的存儲空間進行回收時：也采取類似于內存回收的方法，即要考慮回收區(qū)是否與空閑表中插入點的前區(qū)和后區(qū)相鄰接，對相鄰接者應予以合并。6.5

文件存儲空間的管理（4）2.位示圖法

位示圖法圖6-22位示圖6.5

文件存儲空間的管理（5）盤塊的分配

(1)順序掃描位示圖，從中找出一個或一組其值為“0”的二進制位(“0”表示空閑)。

(2)將所找到的一個或一組二進制位，轉換成與之相對應的盤塊號。假定找到的值為“0”的二進制位，位于位示圖的第i行、第j列，則其相應的盤塊號（假設塊號從1開始）應按下式計算：

b=n(i-1)+j

式中，n代表每行的位數。

(3)修改位示圖，令map［i,j］=1。6.5

文件存儲空間的管理（6）盤塊的回收

(1)將回收盤塊的盤塊號轉換成位示圖中的行號和列號。轉換公式為：

i=(b-1)DIVn+1j=(b-1)MODn+1(2)修改位示圖。令map［i,j］=0。6.5

文件存儲空間的管理（7）3.成組鏈接法

空閑盤塊的組織6.5

文件存儲空間的管理（8）空閑盤塊的分配與回收當系統(tǒng)要為用戶分配文件所需的盤塊時，應調用盤塊分配過程來完成。1、首先檢查空閑盤塊號棧是否上鎖（互斥訪問），如未上鎖，便從棧頂取出一空閑盤塊號，將與它對應的盤塊分配給用戶，然后將棧頂指針下移一格。2、若該盤塊號已是棧底，即S.free(0)，這是當前棧中最后一個可分配的盤塊號。6.5

文件存儲空間的管理（9）空閑盤塊的分配與回收3、由于在該盤塊號所對應的盤塊中記有下一組可用的盤塊號，因此，應調用磁盤讀過程，將棧底盤塊號所對應盤塊的內容讀入棧中，作為新的盤塊號棧的內容，并把原棧底對應的盤塊分配出去(其中的有用數據已讀入棧中)。4、然后，再分配一相應的緩沖區(qū)(作為該盤塊的緩沖區(qū))。5、最后，把棧中的空閑盤塊數減1并返回。6.5

文件存儲空間的管理（10）

在系統(tǒng)回收空閑盤塊時，應調用盤塊回收過程進行回收：將回收盤塊的盤塊號記入空閑盤塊號棧的頂部，并執(zhí)行空閑盤塊數加1的操作。當棧中空閑盤塊號數目已達到100時，表示棧已滿，便將現有棧中的100個盤塊號，記入新回收的盤塊中，再將其盤塊號作為新的棧底。6.5

文件存儲空間的管理（11）

例題：

參看右圖，在UNIX系統(tǒng)中，現有某進程的文件要釋放四個物理塊，其塊號為150#，152#，172#，177#，試給出其釋放過程和釋放后的空閑盤塊號棧filsys的情況；其后，又有一個文件要分配6個空閑塊，試給出其分配過程和分配后的filsys的情況。s.free97[0]120[1]121…

……

…[96]145

空閑盤塊號棧filsys6.5

文件存儲空間的管理（12）6.6

文件共享文件共享：不同用戶之間共同使用某些文件早期實現文件共享的方法繞彎路法（低效）允許每個用戶獲得一“當前目錄”，用戶所訪問的所有文件均相對于當前目錄，若不在，則“向上走”繞彎路去訪問其上級目錄，如圖所示：連訪法利用基本文件目錄實現文件共享基于索引結點的共享方式利用符號鏈實現文件共享假定當前目錄7，需共享文件9。(用＊表示父結點)其路徑名：＊:＊:cacb主目錄ab用戶Aid=2xt用戶Cid=4id=9id=10id=1cd用戶Bid=3ac目錄c

id=7id=11id=12id=14id=13hf目錄d

id=8id=6id=5連訪法CBADEFAGKMJDBACAKNJFHAa

用戶可在自己的文件目錄中對要共享的文件建立相應的目錄項，直接指向被共享文件所在的目錄項，而不是直接指向文件。利用基本文件目錄實現文件共享

在早期，實現文件共享的一種有效方法，是在文件系統(tǒng)中設置一個基本目錄，每個文件在該目錄中均占有一個目錄項，用于給出系統(tǒng)賦予的、對應于該文件名的唯一標識符（整數），以及該文件的有關說明信息。如下圖所示：利用基本文件目錄實現文件共享…98765432104zhang3wang空閑文件目錄…6beta5sqrt…90af8report6alpha7mistsqrtbetaalphamist0afreport主文件目錄基本文件目錄符號名IDZhang的文件目錄wang的文件目錄基于索引結點的共享方式（1）注：任何用戶對文件進行附加操作或修改，所引起的相應索引結點內容的改變，對其它共享用戶均是可見，從而可提供其他用戶共享。

將文件的物理地址和文件屬性等信息放在索引結點中，在文件目錄中，有文件名及指向索引結點的指針，另外在索引結點中增加鏈接計數count,表示共享的用戶數，刪除時必須count=0才可以。rTestwang的文件目錄Lee的文件目錄rTestcount=2文件物理地址test索引結點基于索引結點的共享方式（2）C的目錄Owner=cCount=1鏈接前B的目錄C的目錄Owner=cCount=2建立鏈接后B的目錄Owner=cCount=1若擁有者C刪除文件，會引起指針懸空，故C不能刪除利用符號鏈實現文件共享（1）

共享某文件test時，創(chuàng)建一新文件fd，并加到用戶目錄中，該文件僅包含被鏈接文件test的路徑名，稱該鏈接方法為符號鏈接。該方式中，只有文件主才擁有指向其索引結點的指針，其它共享的用戶只有該文件的路徑名。testrWang的文件目錄Lee的文件目錄fd文件物理地址testfdfd文件內容：Wang\test文件物理地址符號鏈索引結點索引結點利用符號鏈實現文件共享（2）優(yōu)點當文件主刪除一共享文件時，其它共享文件的用戶不會留下一個懸空指針。可鏈接世界上任何地方的機器中的文件。缺點根據給定的文件路徑名去查找目錄，將使訪問文件的開銷大，啟動磁盤頻率較高。每一共享文件將具有幾個文件名，這將增加遍歷共享文件的次數。符號鏈文件雖然簡單，但仍要為它配置一個索引結點，耗費一定的磁盤空間6.7文件保護影響文件安全性的主要因素人為因素系統(tǒng)因素自然因素確保文件系統(tǒng)安全性的措施存取控制機制------人為因素系統(tǒng)容錯技術------系統(tǒng)因素后備系統(tǒng)------------自然因素6.7文件保護---存取控制機制保護域訪問矩陣訪問矩陣的修改（拷貝權、所有權、控制權）訪問矩陣的實現（訪問控制表、訪問權限表）分級安全管理系統(tǒng)級安全管理用戶級安全管理目錄級安全管理文件級安全管理磁盤容錯技術保護域進程與域之間的聯系靜態(tài)聯系進程的可用資源集在進程的整個生命中是固定的動態(tài)聯系進程的可用資源集在進程的整個生命中是變化的F1[R]F2[RW]域1F3[R]F4[RWE]F5[RW]域1F6[RWE]ploter2[W]域1Printer1[w]訪問矩陣用以描述系統(tǒng)存取控制的矩陣訪問矩陣中的行代表域，列代表對象，矩陣中每一項由一組訪問權組成。R---讀；W---寫；E----執(zhí)行訪問權access(i,j)定義了在域Di中執(zhí)行的進程能對對象施加的操作集。訪問權通常由資源的擁有者或管理者所決定。

文件A

文件B

文件C打印機域D1R,WRW域D2W,REW域D3R，WW訪問矩陣

文件A

文件B

文件C打印機域D1域D2域D3域D1R,WRWS域D2W,REWS域D3R，WW進程擁有切換權時，可將進程從一個保護域切換到另一保護域，以實現進程和域之間的動態(tài)聯系。訪問矩陣保護實現：當進程向文件系統(tǒng)提出存取請求時，系統(tǒng)就根據存取控制矩陣將本次請求和該進程對文件的存取權限進行比較，若不匹配就拒絕執(zhí)行。特點：對整個系統(tǒng)中所有文件的訪問權限進行集中控制。缺點：當用戶和文件較多時，存取控制矩陣就較大，占據的存儲空間就較多；查找花費時間較長。

訪問矩陣的修改-拷貝權，所有權，控制權

進程在某個域中對某對象擁有的訪問權可通過拷貝將訪問權擴展到其它域（同一列即同一對象）中。F1F2F3D1E

W*D2ER*ED3EF1F2F3D1E

W*D2ER*ED3ERW

利用所有權（O）可實現訪問權的擴展、增加和刪除（同一列即同一對象）。F1F2F3D1O,E

W

D2

R*,OR*,O,WD3E

F1F2F3D1O,E

W

D2

R*,O,W*R*,O,WD3E

WW訪問矩陣的修改-拷貝權，所有權，控制權

可改變矩陣中同一行（同一域即不同對象）的訪問權。F1F2F3F4F5打印機1繪圖儀2D1D2D3D1RR,WD2R,ER,WW

controlD3R,W,EWW

訪問矩陣的修改-拷貝權，所有權，控制權

訪問矩陣的實現--訪問控制表將訪問矩陣按列（對象）劃分，為每一列建立一張訪問控制表ACL。在該表中無原矩陣中的空項。由有序對（域，權集）組成。對象為文件時，常將ACL存放于該文件的FCB/索引結點中，作為存取控制信息?？啥x缺省的訪問權集。將訪問矩陣按行（域）劃分，形成一行一張訪問權限表。類型權力對象文件R--指向文件3的指針

文件RWE指向文件4的指針

文件RW-指向文件5的指針

打印機-W-指向打印機1的指針

訪問矩陣的實現--訪問控制表分級安全管理-系統(tǒng)級安全管理主要任務不允許未經核準的用戶進入系統(tǒng)主要方法注冊登錄其它措施系統(tǒng)級安全管理用戶級安全管理目錄級安全管理文件級安全管理注冊主要目的使系統(tǒng)管理員能夠掌握要使用系統(tǒng)的諸用戶的情況，并保證用戶名在系統(tǒng)中的唯一性。實現系統(tǒng)中保存一張用戶表。用戶使用前須占用用戶表一空項注冊。用戶使用后須由管理員將該用戶從用戶表中刪除。一旦刪除，該用戶便不能再進入系統(tǒng)，除非再次登錄。用戶表中用戶有限。注冊用戶表用戶1用戶2用戶3用戶2表用戶名口令上機時間終端號登錄主要目的通過核實該用戶的注冊名及口令來檢查該用戶使用系統(tǒng)的合法性。實現輸入注冊用戶名。系統(tǒng)將注冊用戶名與用戶表中的注冊名比較。若用戶名正確，則輸入用戶口令?？诹钫_，則登錄成功。用戶可使用系統(tǒng)。注冊用戶表用戶1用戶2用戶3用戶2表用戶名口令上機時間終端號其它措施規(guī)定用戶定