計算機操作系統(tǒng)教程第六章：文件系統(tǒng)

第六章文件系統(tǒng)磁帶磁盤進入狀態(tài)退出狀態(tài)后備狀態(tài)運行狀態(tài)數(shù)據(jù)數(shù)據(jù)源程序作業(yè)說明書輸入設(shè)備輸入井輸出設(shè)備輸出井運行就緒等待數(shù)據(jù)文件管理文件系統(tǒng)6.1文件和文件系統(tǒng)

6.1.1文件、記錄和數(shù)據(jù)項數(shù)據(jù)項：在文件系統(tǒng)中，數(shù)據(jù)項是最低級的數(shù)據(jù)組織形式，分為：基本數(shù)據(jù)項：用于描述一個對象的某種屬性的字符集，又稱數(shù)據(jù)元素或字段；組合數(shù)據(jù)項：由若干個基本數(shù)據(jù)項組成。記錄：是一組相關(guān)數(shù)據(jù)項的集合，描述一個對象在某方面的屬性文件：由創(chuàng)建者所定義的、具有文件名的一組相關(guān)元素的有序集合第六章文件系統(tǒng)文件是具有名字的數(shù)據(jù)項的集合。文件名是文件的標識符號。相關(guān)字符流的集合或相關(guān)記錄的集合。文件包括兩部分：文件體：文件本身的信息；文件說明：文件存儲和管理信息；如：文件名、文件內(nèi)部標識、文件存儲地址、訪問權(quán)限、訪問時間等文件的屬性：包括文件類型、文件長度、文件的物理位置、文件的建立時間6.1文件和文件系統(tǒng)

6.1.1文件、記錄和數(shù)據(jù)項第六章文件系統(tǒng)文件、記錄與數(shù)據(jù)項的關(guān)系6.1文件和文件系統(tǒng)

6.1.1文件、記錄和數(shù)據(jù)項文件記錄1記錄2記錄m…數(shù)據(jù)項1數(shù)據(jù)項2數(shù)據(jù)項n…第六章文件系統(tǒng)文件類型

按用途分：系統(tǒng)文件、用戶文件、庫文件按數(shù)據(jù)形式分：源文件、目標文件、可執(zhí)行文件按存取控制屬性分：只執(zhí)行文件、只讀文件、讀寫文件按組織形式和處理方式分普通文件：ASCII碼或二進制碼組成的字符文件目錄文件：由文件目錄組成特殊文件：系統(tǒng)中各類I/O設(shè)備6.1文件和文件系統(tǒng)

6.1.2文件類型和文件系統(tǒng)模型第六章文件系統(tǒng)文件系統(tǒng)模型6.1文件和文件系統(tǒng)

6.1.2文件類型和文件系統(tǒng)模型文件系統(tǒng)接口對對象操縱和管理的軟件集合對象及其屬性用戶（程序）命令接口、程序接口對文件存儲空間的管理對文件目錄的管理邏輯、物理地址轉(zhuǎn)換機制文件讀寫管理文件共享與保護文件、目錄、磁盤存儲空間第六章文件系統(tǒng)文件系統(tǒng)模型基本操作：創(chuàng)建文件，刪除文件，讀文件，寫文件，截斷文件（將原文件長度設(shè)為0），設(shè)置文件讀、寫位置

文件打開與關(guān)閉其他文件操作：對文件屬性操作，對目錄操作，系統(tǒng)調(diào)用等6.1文件和文件系統(tǒng)

6.1.3文件操作第六章文件系統(tǒng)6.1文件和文件系統(tǒng)

6.1.4文件系統(tǒng)層次結(jié)構(gòu)磁盤設(shè)備驅(qū)動程序磁帶設(shè)備驅(qū)動程序基本文件系統(tǒng)基本I/O管理程序邏輯I/O堆順序索引順序索引哈希用戶程序負責啟動該設(shè)備上的I/O操作，處理I/O請求的完成處理與磁盤或磁帶交換的數(shù)據(jù)塊負責所有文件I/O的開始或結(jié)束使用戶和應用程序能夠訪問到記錄在應用程序和文件系統(tǒng)及保存數(shù)據(jù)的設(shè)備之間提供了一種標準接口數(shù)據(jù)塊記錄第六章文件系統(tǒng)6.1文件和文件系統(tǒng)

6.1.4文件系統(tǒng)層次結(jié)構(gòu)文件結(jié)構(gòu)用戶和程序命令操作，文件名目錄管理用戶訪問控制訪問方法文件操作函數(shù)記錄組塊主存緩沖區(qū)中的物理快輔存(磁盤)中的物理快磁盤調(diào)度文件分配自由空間管理I/O文件管理關(guān)注的問題操作系統(tǒng)關(guān)注的問題第六章文件系統(tǒng)按存放時限分類：根據(jù)系統(tǒng)保留文件的時間：臨時文件、永久文件和檔案文件。按設(shè)備類型分類：根據(jù)文件存儲介質(zhì)的設(shè)備類型：磁盤文件、磁帶文件、卡片文件和打印文件等。按文件的組織結(jié)構(gòu)分類:文件的邏輯結(jié)構(gòu)：從用戶觀點出發(fā)觀察到的文件組織文件的物理結(jié)構(gòu)：文件的存儲結(jié)構(gòu)，即文件在外存的存儲組織形式。涉及存儲介質(zhì)、外存分配方式6.2文件的邏輯結(jié)構(gòu)

6.2.1文件分類第六章文件系統(tǒng)文件組織結(jié)構(gòu)邏輯結(jié)構(gòu)物理結(jié)構(gòu)有結(jié)構(gòu)文件無結(jié)構(gòu)文件累積文件順序文件索引順序文件索引文件索引結(jié)構(gòu)連續(xù)結(jié)構(gòu)串聯(lián)結(jié)構(gòu)6.2文件的邏輯結(jié)構(gòu)

6.2.1文件分類第六章文件系統(tǒng)無結(jié)構(gòu)文件文件體為字節(jié)流，不劃分記錄，順序訪問，每次讀寫訪問可以指定任意數(shù)據(jù)長度當前操作系統(tǒng)中常用的文件組織6.2文件的邏輯結(jié)構(gòu)

6.2.2文件邏輯結(jié)構(gòu)類型第六章文件系統(tǒng)累積文件（pile堆文件）文件體為無結(jié)構(gòu)記錄序列，通過分隔符來劃分記錄，各記錄大小和組成可變。新記錄總是添加到文件末尾。如日志log，或電子郵件的郵箱文件(mailbox)。檢索必須從頭開始是一種簡單的文件組織方式，當數(shù)據(jù)難以組織時使用6.2文件的邏輯結(jié)構(gòu)

6.2.2文件邏輯結(jié)構(gòu)類型第六章文件系統(tǒng)累積文件（pile堆文件）6.2文件的邏輯結(jié)構(gòu)

6.2.2文件邏輯結(jié)構(gòu)類型第六章文件系統(tǒng)順序文件文件體為大小相同、格式固定的排序記錄序列由一個主文件和一個臨時文件組成記錄按某個關(guān)鍵字域排序，存放在主文件中新記錄暫時保存在臨時文件中，定期歸并入主文件，并按正確順序產(chǎn)生一個新文件訪問時需要順序搜索6.2文件的邏輯結(jié)構(gòu)

6.2.2文件邏輯結(jié)構(gòu)類型第六章文件系統(tǒng)順序文件6.2文件的邏輯結(jié)構(gòu)

6.2.2文件邏輯結(jié)構(gòu)類型第六章文件系統(tǒng)主文件臨時文件索引順序文件在順序文件（主文件）的基礎(chǔ)上，另外建立索引和溢出文件在索引文件中，可將關(guān)鍵字域中的取值劃分若干個區(qū)間，每個區(qū)間對應一個索引項，后者指向該區(qū)間的開頭記錄。新記錄暫時保存在溢出文件中，定期歸并入主文件6.2文件的邏輯結(jié)構(gòu)

6.2.2文件邏輯結(jié)構(gòu)類型第六章文件系統(tǒng)索引順序文件關(guān)鍵字邏輯地址ABZ索引文件姓名其它屬性AnBingAnKangAnQingBao

RongBiJingBonLong順序文件6.2文件的邏輯結(jié)構(gòu)

6.2.2文件邏輯結(jié)構(gòu)類型第六章文件系統(tǒng)索引主文件溢出文件索引文件將每種可能成為搜索條件的域都有一個索引，通過索引來訪問記錄記錄大小不必相同，不必排序，存放在主文件中另外建立索引，每個索引項指向一個記錄，索引項按照記錄中的某個關(guān)鍵字域排序?qū)ν恢魑募槍Σ煌年P(guān)鍵字域相應建立多個索引索引文件的記錄項通常較小，查找速度快，便于隨機訪問索引文件與索引順序文件的區(qū)別在于主文件不排序6.2文件的邏輯結(jié)構(gòu)

6.2.2文件邏輯結(jié)構(gòu)類型第六章文件系統(tǒng)索引文件6.2文件的邏輯結(jié)構(gòu)

6.2.2文件邏輯結(jié)構(gòu)類型第六章文件系統(tǒng)索引索引主文件索引索引哈希文件或直接文件、散列文件直接訪問磁盤中任何一個地址已知的塊記錄大小相同由主文件和溢出文件組成記錄位置由哈希函數(shù)確定檢索時給出記錄編號，通過哈希函數(shù)計算出該記錄在文件中的相對位置訪問速度快，通常一次只訪問一條記錄6.2文件的邏輯結(jié)構(gòu)

6.2.2文件邏輯結(jié)構(gòu)類型第六章文件系統(tǒng)用戶在一個文件上的操作：“讀”和“寫”讀：存儲介質(zhì)→內(nèi)存寫：內(nèi)存→存儲介質(zhì)順序存取法：按照文件信息的邏輯順序依次存取。按記錄的排列順序來存取。如：為了存取記錄Ri,必須先通過記錄R1R2…

Ri-1隨機存取法(直接存?。嚎梢园慈我獾拇涡?qū)ξ募M行讀寫操作。如可根據(jù)記錄的編號來直接存取文件中的任意一個記錄索引存取：對文件中的記錄按某個數(shù)據(jù)項的值進行排列，從而可以根據(jù)鍵值來快速存取。6.2文件的邏輯結(jié)構(gòu)

6.2.3文件的存取第六章文件系統(tǒng)文件目錄文件名 起始塊 長度

FileA 2 3

FileB 9 5

FileC 18 8

FileD 30 2

FileE 26 3為每個文件分配一組相鄰接的盤塊只需記錄第一個簇的位置，適用于預分配方法6.3外存分配方式

6.3.1連續(xù)分配第六章文件系統(tǒng)優(yōu)點順序訪問容易順序訪問速度快缺點要求有連續(xù)的存儲空間必須事先知道文件的長度6.3外存分配方式

6.3.1連續(xù)分配第六章文件系統(tǒng)隱式鏈接分配：在每個塊中有指向下一個塊的指針6.3外存分配方式

6.3.2鏈接分配文件目錄文件名 起始塊 最后塊

… … …

FileB 1 28… … …適用于連續(xù)訪問第六章文件系統(tǒng)顯式鏈接分配：把用于連接文件各物理塊的指針顯式地存放在內(nèi)存的一張鏈接表中6.3外存分配方式

6.3.2鏈接分配文件目錄文件名 起始塊 最后塊

… … …

FileB 1 28… … …0123481428814328-1............物理塊號FAT第六章文件系統(tǒng)例題：設(shè)磁盤塊大小為1KB，硬盤大小為500MB，采用顯式連接分配方式時，其FAT需占多少存儲空間？如果文件A占用硬盤的第11、12、16、14四個盤塊，試畫出文件A中各盤塊間的鏈接情況及FAT的情況。6.3外存分配方式

6.3.2鏈接分配500*1024=500K個盤塊，需要19位表示。

19*500K=9500K位=1187.5KB文件名起始塊最末塊

………A1114………1112131415161216-114............FAT第六章文件系統(tǒng)單級索引分配：文件的第一個簇中記錄了該文件的其他簇的位置6.3外存分配方式

6.3.3索引分配文件目錄文件名 索引塊

… …

FileB 24… …第六章文件系統(tǒng)多重索引分配：將一個大文件的所有索引表（二級索引）的地址放在另一個索引表（一級索引）中6.3外存分配方式

6.3.3索引分配3607401125...105106254356357985360740......105106254255356主索引二級索引磁盤空間第六章文件系統(tǒng)混合索引分配：將多種索引分配方式相結(jié)合直接地址：直接從索引節(jié)點中讀出文件盤塊號一次間接地址：一次間接地址塊也是索引塊多次間接地址6.3外存分配方式

6.3.3索引分配第六章文件系統(tǒng)混合索引分配索引數(shù)組i-addr[i]文件信息文件信息...文件信息...文件信息中型文件5KB-90KB...文件信息文件信息大型文件90KB-14.54MB...文件信息文件信息巨型文件14.54MB-1GB...文件信息一次間址二次間址三次間址第六章文件系統(tǒng)UNIX混合索引分配最大可達：10+256+2562+2563個物理塊第六章文件系統(tǒng).....................磁盤塊...尋址模式索引數(shù)組i-addr[i]一次間址二次間址三次間址直接地址0直接地址1直接地址2直接地址3直接地址4直接地址5直接地址6直接地址7直接地址8直接地址9.........每塊存放256個物理塊號如何管理文件目錄？第六章文件系統(tǒng)對目錄管理的要求實現(xiàn)“按名存取”：用戶只需向系統(tǒng)提供所需訪問的文件名字，便能快速準確地找到指定文件在外存上的存儲位置提高對目錄的檢索速度：通過合理地組織目錄結(jié)構(gòu)予以實現(xiàn)文件共享：允許多個用戶共享一個文件允許文件重名：允許不同用戶對不同文件采用相同的名字，對相同文件采用不同的名字6.4目錄管理第六章文件系統(tǒng)文件控制塊為文件設(shè)置的用于描述和控制文件的數(shù)據(jù)結(jié)構(gòu)，文件管理系統(tǒng)借助其中的信息，對文件施以各種操作文件與文件控制塊一一對應，文件控制塊的有序集合稱為文件目錄，一個文件控制塊即為一個文件目錄項一個文件目錄也可視為一個文件6.4目錄管理

6.4.1文件控制塊和索引節(jié)點第六章文件系統(tǒng)文件控制塊包含三類信息基本信息類：文件名、文件物理位置、文件邏輯結(jié)構(gòu)、文件物理結(jié)構(gòu)存取控制信息類：各類用戶的存取權(quán)限使用信息類：文件的建立日期和時間、上次修改的日期和時間、當前使用信息（已打開文件的進程數(shù)、是否被其他進程鎖住、文件在內(nèi)存中是否已被修改但尚未拷貝到盤上、…）6.4目錄管理

6.4.1文件控制塊和索引節(jié)點第六章文件系統(tǒng)索引節(jié)點引入：在檢索目錄文件時，只需文件名——文件名與文件描述信息分開，使文件描述信息單獨形成一個索引節(jié)點——i節(jié)點。在文件目錄中的每個目錄項僅由文件名和i節(jié)點指針構(gòu)成6.4目錄管理

6.4.1文件控制塊和索引節(jié)點

文件名索引節(jié)點編號文件名1文件名2………0131415UNIX的文件目錄第六章文件系統(tǒng)索引節(jié)點磁盤索引節(jié)點：存放在磁盤上，每個文件有唯一的磁盤索引節(jié)點。包括：文件主標識符：擁有該文件的個人或組標識文件類型：正規(guī)文件、目錄文件或特別文件文件存取權(quán)限：各類用戶對該文件的存取權(quán)限文件物理地址：直接或間接給出文件所在盤塊文件長度、文件鏈接計數(shù)、文件存取時間6.4目錄管理

6.4.1文件控制塊和索引節(jié)點第六章文件系統(tǒng)索引節(jié)點內(nèi)存索引節(jié)點：存放在內(nèi)存中，文件打開時，將磁盤索引節(jié)點拷貝到內(nèi)存的索引節(jié)點中。增加：索引節(jié)點編號：標識內(nèi)存索引節(jié)點狀態(tài)：指示i節(jié)點是否上鎖或被修改訪問計數(shù)：有進程訪問i節(jié)點時，計數(shù)加1文件所屬文件系統(tǒng)的邏輯設(shè)備號鏈接指針：指向空閑鏈表和散列隊列6.4目錄管理

6.4.1文件控制塊和索引節(jié)點第六章文件系統(tǒng)單級目錄結(jié)構(gòu)整個文件系統(tǒng)中只建立一張目錄表，每個文件占一個目錄項建立一個新文件時，先檢索所有目錄項，保證新文件名在目錄中的唯一性，再從目錄表中找出一個空白目錄項，填入新文件信息查找速度慢，不允許重名，不便于實現(xiàn)文件共享6.4目錄管理

6.4.2目錄結(jié)構(gòu)

文件名物理地址文件說明狀態(tài)位文件名1文件名2第六章文件系統(tǒng)兩級目錄結(jié)構(gòu)為每個用戶建立一個單獨的用戶文件目錄這些文件目錄由用戶所有文件的文件控制塊組成系統(tǒng)中再建立一個主文件目錄，其中每個用戶目錄文件占有一個目錄項（目錄名，指向子目錄指針）優(yōu)點提高了檢索目錄的速度不同的用戶目錄中可以使用相同的文件名不同用戶可以用不同的文件名訪問同一共享文件6.4目錄管理

6.4.2目錄結(jié)構(gòu)第六章文件系統(tǒng)兩級目錄結(jié)構(gòu)6.4目錄管理

6.4.2目錄結(jié)構(gòu)用戶名指向子目錄指針

WangZhang

GaoAlphaTestAlphaTestBetaDeviceMisxBetaDeviceMisxAlphaTestReportTestWang用戶目錄Zhang用戶目錄Gao用戶目錄主文件目錄

MFD用戶文件目錄

UFD第六章文件系統(tǒng)多級目錄結(jié)構(gòu)（樹形目錄結(jié)構(gòu)）主目錄——根節(jié)點，數(shù)據(jù)文件——葉節(jié)點6.4目錄管理

6.4.2目錄結(jié)構(gòu)ABCABDFEDJNKJMKAHFGAAC1234567891011121314151617192021221823第六章文件系統(tǒng)多級目錄結(jié)構(gòu)（樹形目錄結(jié)構(gòu)）路徑名：將全部目錄文件名與數(shù)據(jù)文件名依次用“/”連接起來當前目錄、工作目錄絕對路徑名、相對路徑名層次結(jié)構(gòu)清晰，查詢速度快，有益于文件的管理和保護查找文件時需按路徑名逐級訪問中間節(jié)點，增加了磁盤訪問次數(shù)6.4目錄管理

6.4.2目錄結(jié)構(gòu)第六章文件系統(tǒng)非循環(huán)圖目錄結(jié)構(gòu)允許一個文件或目錄在多個父目錄中占有項目，但并不構(gòu)成回路在MULTICS和UNIX系統(tǒng)中，這種結(jié)構(gòu)叫做鏈接6.4目錄管理

6.4.2目錄結(jié)構(gòu)root…dictspelllistnewcountlistwordslist1radcw7第六章文件系統(tǒng)增加或刪除目錄樹型目錄結(jié)構(gòu)中，用戶可為自己建立UFD，并可再創(chuàng)建子目錄樹型目錄結(jié)構(gòu)中，對于一個不再需要的目錄，考慮：目錄為空：直接刪除目錄非空先刪除目錄中所有文件，再刪除目錄刪除目錄，其子文件一同被刪除6.4目錄管理

6.4.2目錄結(jié)構(gòu)第六章文件系統(tǒng)線性檢索法：順序檢索單級目錄中，根據(jù)文件名直接在文件目錄中順序查找樹型目錄結(jié)構(gòu)中，文件名是由多個文件分量名組成的路徑，需對多級目錄查找。6.4目錄管理

6.4.3目錄查詢

例：查找/usr/ast/mbox1.1..4bin7dev14lib9etc6usr8temp目錄根目錄

132i節(jié)點節(jié)點6是/user的目錄6.1..19dick30erik51jim26ast45bal目錄132號盤塊是/user的目錄

496i節(jié)點節(jié)點26是/user/ast的目錄26.6..64grants92books60mbox81minik17src目錄496號盤塊是/user/ast的目錄第六章文件系統(tǒng)Hash方法如果建立了一張Hash索引文件目錄，便可利用Hash方法進行查詢將文件名變換為文件目錄的索引值，再利用該索引值到目錄中去查找（見6.2.2相關(guān)內(nèi)容）沖突：將n個不同的文件名轉(zhuǎn)換成相同的Hash值處理沖突的規(guī)則：查找時，如果相應目錄項為空，則系統(tǒng)中無指定文件如果目錄項中文件名與指定文件名匹配，找到文件物理地址如果目錄項中文件名與指定文件名不匹配，則“沖突”，須將其Hash值再加上一個常數(shù)（與目錄的長度互質(zhì)），形成新的索引值，重新查找6.4目錄管理

6.4.3目錄查詢第六章文件系統(tǒng)內(nèi)存所需表目6.5文件存儲空間的管理

6.5.1文件管理FCB主部文件號共享計數(shù)修改標志……………………系統(tǒng)打開文件表用戶打開文件表文件描述符打開方式讀寫指針系統(tǒng)打開文件表入口……………………第六章文件系統(tǒng)內(nèi)存所需表目6.5文件存儲空間的管理

6.5.1文件管理共享計數(shù)其它…………2………………其它系統(tǒng)打開文件表入口………其它系統(tǒng)打開文件表入口………系統(tǒng)打開文件表用戶打開文件表（P1）用戶打開文件表（P2）第六章文件系統(tǒng)空閑表法為磁盤上所有空閑區(qū)建立一張空閑表，每個空閑區(qū)對應一個空閑表項分配：類似于內(nèi)存的動態(tài)分配回收：類似于內(nèi)存的回收，相鄰者合并6.5文件存儲空間的管理

6.5.2空閑表法和空閑鏈表法

序號 第一空閑盤塊號空閑盤塊數(shù)

1 2 42 9 3315 54 - -第六章文件系統(tǒng)空閑鏈表法空閑盤塊鏈：在每個空白盤塊中建立一個指向下一個空白盤塊的鏈接指針，將所有空白盤塊鏈在一起空白盤區(qū)鏈：將磁盤上所有空白盤區(qū)（每個空白盤區(qū)包含若干個盤塊）鏈接在一起分配、回收6.5文件存儲空間的管理

6.5.2空閑表法和空閑鏈表法YWZ……

首指針XXYWZ第六章文件系統(tǒng)位示圖利用二進制的一位表示磁盤中一個盤塊的使用情況。0——空閑，1——已分配；（或相反）位示圖也可描述為一個二維數(shù)組map

Varmap:arrayofbit;6.5文件存儲空間的管理

6.5.3位示圖法

123456789101112131415161110001110010011020001111110000111311100011111100004…16第六章文件系統(tǒng)盤塊的分配順序掃描位示圖，從中找出一個或一組其值為0的二進制位（0表示空閑時）將所找到的一個或一組二進制位轉(zhuǎn)換成與之對應的盤塊號。設(shè)找到的其值為0的二進制位位于位示圖的第i行、第j列，對應盤號為b=n(i-1)+j（n為每行的位數(shù)）修改位示圖，令map[i,j]=16.5文件存儲空間的管理

6.5.3位示圖法第六章文件系統(tǒng)盤塊的回收將回收盤塊號轉(zhuǎn)換成位示圖中的行號和列號：

i=

(b-1)/n

+1j=(b-1)modn+1修改位示圖，令map[i,j]=06.5文件存儲空間的管理

6.5.3位示圖法第六章文件系統(tǒng)盤塊的組織把所有空閑盤塊按固定數(shù)量分組（設(shè)為n），組中第1塊為“組長”塊，第1組的n個空閑塊塊號放在第2組的“組長”塊中，第2組的n個空閑塊塊號放在第3組的“組長”塊中，以此類推，組、組之間形成鏈接。最后1組的塊號（可能不足n塊）通常放在內(nèi)存的一個專用棧結(jié)構(gòu)中，使通常對盤塊的分配和釋放在棧中進行6.5文件存儲空間的管理

6.5.4成組鏈接法第六章文件系統(tǒng)6.5文件存儲空間的管理

6.5.4成組鏈接法空閑塊號棧40150149148︰112111︰︰50200199198︰15114911150250249248︰20119915150039993998︰39513949390139993951012︰3839︰︰棧深1502003950組長塊第78組第77組第2組第1組…………………超級塊…UNIX系統(tǒng)的成組鏈接（每組50塊）第六章文件系統(tǒng)空閑塊的分配與回收6.5文件存儲空間的管理

6.5.4成組鏈接法分配Int

AllocateOneBlock(){ifS[0]==1thenifS[1]==0then分配失敗，進程等待；

else{r=S[1];

ReadABlock(S,r);returnr;}elser=S[S[0]];S[0]--;returnr;}查看超級塊中是否count==1；若不是，則彈出棧頂元素N，--count；若是，則彈出棧頂元素N，把空閑塊N中的棧（包括棧計數(shù)）讀入到內(nèi)存空閑塊棧中；返回空閑塊編號N空閑塊號棧40150149148︰112111︰︰50200199198︰15114911150250249248︰20119915150039993998︰39513949390139993951012︰3839︰︰棧深1502003950組長塊第78組第77組第2組第1組…………………超級塊…第六章文件系統(tǒng)空閑塊的分配與回收6.5文件存儲空間的管理

6.5.4成組鏈接法回收FreeABlock(int

BlockNo){ifS[0]==最大總塊數(shù)Nthen

wtire

堆棧S到塊BlockNo中；

S[0]=1；

S[1]=BlockNoelseS[0]++;S[S[0]]=BlockNo;}被釋放空閑塊為編號N。查看超級塊中是否棧已滿（如count==50）；若不是，則N入棧，++count；若是，則將超級塊中的棧（包括棧計數(shù)）寫入到空閑塊N，然后把N放入內(nèi)存空閑塊棧中的棧頂并置count為1?？臻e塊號棧40150149148︰112111︰︰50200199198︰15114911150250249248︰20119915150039993998︰39513949390139993951012︰3839︰︰棧深1502003950組長塊第78組第77組第2組第1組…………………超級塊…第六章文件系統(tǒng)例題：某個文件系統(tǒng)采用成組鏈接法管理磁盤空閑空間，目前磁盤的狀態(tài)如圖所示：

(1)該磁盤中目前還有多少空閑盤塊？

(2)在為某個文件分配3個盤塊后，系統(tǒng)要刪除另一文件，并回收它所占的5個盤塊，它們的盤塊號依次為700、711、703、788、701，請畫出回收后的盤塊鏈接情況2300299...

s_nfrees_free[0]s_free[1]s_free[98]s_free[99]100400399301

...

100500499401

...1000599501

...

.........空閑盤塊號棧300299400399301500499401599501解答：

(1)301塊

(2)見下頁第六章文件系統(tǒng)1300...

s_nfrees_free[0]s_free[1]s_free[98]s_free[99]100400399301

...100500499401

...1000599501

...

.........空閑盤塊號棧300400399301500499401599501初始

299第六章文件系統(tǒng)1300...

s_nfrees_free[0]s_free[1]s_free[98]s_free[99]100400399301

...100500499401

...1000599501

...

.........空閑盤塊號棧300400399301500499401599501分配1塊第六章文件系統(tǒng)100400399301...

s_nfrees_free[0]s_free[1]s_free[98]s_free[99]100500499401

...1000599501

...

.........空閑盤塊號棧400399301500499401599501分配2塊第六章文件系統(tǒng)99400399302...

s_nfrees_free[0]s_free[1]s_free[98]s_free[99]100500499401

...1000599501

...

.........空閑盤塊號棧400399302500499401599501分配3塊第六章文件系統(tǒng)100400399302700...

s_nfrees_free[0]s_free[1]s_free[98]s_free[99]100500499401

...1000599501

...

.........空閑盤塊號棧400399302500499401599501回收第700塊

700第六章文件系統(tǒng)1711

...

s_nfrees_free[0]s_free[1]s_free[98]s_free[99]100500499401

...1000599501

...

.........空閑盤塊號棧400399302500499401599501回收第711塊

700100400399700

...711第六章文件系統(tǒng)2711703

...

s_nfrees_free[0]s_free[1]s_free[98]s_free[99]100500499401

...1000599501

...

.........空閑盤塊號棧400399302500499401599501回收第703塊

700100400399700

...711

703第六章文件系統(tǒng)3711703788

...

s_nfrees_free[0]s_free[1]s_free[2]s_free[98]s_free[99]100500499401

...1000599501

...

.........空閑盤塊號棧400399302500499401599501回收第788塊

700100400399700

...711

703

788第六章文件系統(tǒng)4711703788701

...

s_nfrees_free[0]s_free[1]s_free[2]s_free[3]s_free[98]s_free[99]100500499401

...1000599501

...

.........空閑盤塊號棧400399302500499401599501回收第701塊

700100400399700

...711

703

788

701第六章文件系統(tǒng)一個文件可以讓指定的某些用戶共同使用節(jié)省空間免除系統(tǒng)復制文件的重復性工作減少訪問外存次數(shù)保證信息一致性6.6文件共享與文件保護

6.6.1共享動機第六章文件系統(tǒng)靜態(tài)文件共享繞彎路法：每個用戶有個“當前目錄”，用戶的所有操作都相對于自己的當前目錄基于基本目錄共享法：設(shè)置一個基本文件目錄，每個目錄相對應一個文件，記錄文件的唯一標識符ID、文件的存取控制管理信息、文件的物理地址等。6.6文件共享與文件保護

6.6.2共享方式第六章文件系統(tǒng)靜態(tài)文件共享基于基本目錄共享法0123456789

BFD序號9…FFD用戶名序號Wang 3Zhao 4文件名序號TC.exe 5

In.ppt 7文件名序號Out.txt 6ent.ppt 7TC.exe 8BFD： 基本文件目錄ID： 標識符FFD： 空閑文件目錄MFD： 主文件目錄SFD： 符號文件目錄MFDWang的目錄Zhao的目錄對應同一個物理文件SFDSFD如果還有其他用戶共享它，在其SFD中加上ID為7的表項第六章文件系統(tǒng)6.6文件共享與文件保護

6.6.2共享方式靜態(tài)文件共享基于索引節(jié)點共享：引用索引節(jié)點，文件的物理地址及其他的文件屬性等信息，不再放在目錄項中，而放在索引節(jié)點中。文件目錄中只設(shè)置文件名及指向相應索引節(jié)點的指針。6.6文件共享與文件保護

6.6.2共享方式TestrTestrcount=2文件物理地址索引節(jié)點第六章文件系統(tǒng)靜態(tài)文件共享基于索引節(jié)點共享6.6文件共享與文件保護

6.6.2共享方式Owner=cCount=1C的目錄鏈接前B的目錄Owner=cCount=2C的目錄鏈接后B的目錄Owner=cCount=1擁有者刪除文件后第六章文件系統(tǒng)靜態(tài)文件共享基于符號鏈共享方式：為使文件B能共享C的一個文件F，由系統(tǒng)創(chuàng)建一個Link類型的新文件，也取名為F，并將F寫入B的目錄中，以實現(xiàn)B的目錄與文件F的鏈接。新文件中只包含被鏈接文件F的路徑名。被鏈接文件的刪除和符號鏈接的刪除是相互獨立的（返回“被鏈接文件不存在”的錯誤）6.6文件共享與文件保護

6.6.2共享方式第六章文件系統(tǒng)動態(tài)文件共享當多個用戶同時打開某一文件對其訪問時，在內(nèi)存中建立打開文件結(jié)構(gòu)：進程打開文件表、系統(tǒng)打開文件表、文件的內(nèi)存索引節(jié)點。6.6文件共享與文件保護

6.6.2共享方式f-count:1f-inodef-count:1f-inodef-count:1f-inode獨享獨享獨享進程1打開文件表系統(tǒng)打開文件表第六章文件系統(tǒng)動態(tài)文件共享當多個用戶同時打開某一文件對其訪問時，在內(nèi)存中建立打開文件結(jié)構(gòu)：進程打開文件表、系統(tǒng)打開文件表、文件的內(nèi)存索引節(jié)點。6.6文件共享與文件保護

6.6.2共享方式f-count:2f-inodef-count:2f-inodef-count:1f-inodef-count:1f-inode共享共享獨享獨享進程1打開文件表系統(tǒng)打開文件表進程2打開文件表第六章文件系統(tǒng)共享語義：規(guī)定了一個用戶對共享數(shù)據(jù)的修改何時對另一個用戶可見，這種語義通常由文件系統(tǒng)功能決定UNIX語義：在單機系統(tǒng)中，共享文件隱含對所有文件的寫操作立即對所有共享用戶可見。在分布式系統(tǒng)中，所有對文件的寫操作立即通過網(wǎng)絡(luò)傳輸給相應文件會話語義：每個用戶在會話期間，同時打開同一個文件的多個用戶的寫操作彼此不可見（有各自的文件副本）。僅當文件關(guān)閉后，其修改才傳輸給原始文件并且對其他用戶可見6.6文件共享與文件保護

6.6.2共享方式第六章文件系統(tǒng)共享語義：規(guī)定了一個用戶對共享數(shù)據(jù)的修改何時對另一個用戶可見，這種語義通常由文件系統(tǒng)功能決定事務(wù)處理語義：在一個事務(wù)處理期間，對共享文件的用戶不可見，該事務(wù)一終止，立即對其他用戶可見永久共享文件語義：共享文件內(nèi)容只讀，不可修改。如要修改，立即產(chǎn)生一個新的版本。共享文件變成版本管理問題6.6文件共享與文件保護

6.6.2共享方式第六章文件系統(tǒng)訪問類型讀read：可讀出文件內(nèi)容寫write（修改update或添加append）：可把數(shù)據(jù)寫入文件執(zhí)行execute：可由系統(tǒng)讀出文件內(nèi)容，作為代碼執(zhí)行刪除delete：可刪除文件修改訪問權(quán)限changeprotection：修改文件屬主或訪問權(quán)限6.6文件共享與文件保護

6.6.3文件保護第六章文件系統(tǒng)訪問控制用戶范圍類型：指定用戶、用戶組、任意用戶訪問類型和用戶范圍的組合訪問矩陣：矩陣的一維是每個目錄和文件，另一維是用戶范圍，每個元素是允許的訪問方式6.6文件共享與文件保護

6.6.3文件保護

A B C …User1 rw r w …User2 e - - ……文件用戶第六章文件系統(tǒng)訪問控制用戶范圍類型：指定用戶、用戶組、任意用戶訪問類型和用戶范圍的組合存取控制表：以文件為單位，把用戶按某種關(guān)系劃分為若干組，同時規(guī)定每組的存取權(quán)限。實現(xiàn)時，該表放在文件說明中，打開文件時，被復制了內(nèi)存中；效率高口令和密碼6.6文件共享與文件保護

6.6.3文件保護

用戶a.c

文件主人RWEA組REB組E

wangRWE

其他None第六章文件系統(tǒng)UNIX一致性檢查工作過程兩張表，每塊對應一個表中的一個計數(shù)器，初值為0表一：記錄每塊在文件中出現(xiàn)的次數(shù)表二：記錄每塊在空閑塊表中出現(xiàn)的次數(shù)6.7數(shù)據(jù)一致性檢查塊號012345