1、第七章 文件系統 OS 實現系統資源管理: 硬件資源、軟件資源; 軟件資源: 程序、數據; 文件管理: 軟件資源以文件形式存于外存空間, 軟件資源管理通常稱為文件管理; 文件管理由文件系統來完成; 文件系統在設備管理之上。文件的概念 文件: 具有符號名而且在邏輯上具有完整意義的 信息項的有序序列。7.1 文件與文件系統7.1.1 文 件編號:01kn-1信息項信息項信息項信息項文件名: 符號名, 文件創建時確定, 訪問時用;信息項: 構成文件的基本單位; 等長或不等長; 有順序關系;讀/寫指針: 信息項的讀/寫位置;讀/寫指針文件分類系統文件, 用戶文件; 臨時文件, 永久文件; 只讀文件,

2、只寫文件, 讀/寫文件;磁盤文件, 磁帶文件, 磁鼓文件; 目錄文件, 普通文件; 程序文件, 數據文件;程序文件 源文件, 目標文件, 可執行文件, 頭文件, 庫文件。7.1.1 文 件 UNIX文件分類普通文件: 內容可以是程序、數據、圖象等, 保存在磁盤塊中;目錄文件: 文件描述信息(文件名, 文件號)序列, 保存在磁盤塊中;特殊文件: 將各種設備作為文件處理。 界面統一, 使用文件與使用設備命令相同, 申請設備open, 釋放close, 讀read, 寫write; 利用文件保護功能可以保護設備。7.1.1 文 件7.1.2 文件系統文件系統: 文件與管理信息資源的程序集合 稱為文件

3、系統。 為用戶提供按名存取文件的手段; 文件的組織形式; 外存空間的管理; 處于設備管理上層。7.2 文件的訪問方式7.2.1 順序訪問: 磁帶 從文件起始位置開始順序訪問; 從文件中間某處開始順序訪問。7.2.2 隨機訪問: 磁盤、光盤 按信息項編號隨機訪問; 按關鍵字(key)隨機訪問。7.3 文件的組織 文件的組織: 又稱文件結構; 邏輯組織: 外部組織形式, 用戶看到的文件組織形式。 物理組織: 內部組織形式, 物理存儲設備上的組織形式。 OS完成邏輯組織形式到物理組織形式的轉換。7.3.1 文件的邏輯組織流式文件非結構形式的字節序列(UNIX, Windows, etc);構成文件的

4、基本單位是字節。用戶可以對非結構的流式文件 按自定義的結構來處理。編號:01kn-1字節字節字節字節讀/寫指針7.3.1 文件的邏輯組織(Cont.)記錄式文件: 記錄的序列等長記錄(優點: 處理方便, 速度快; 缺點: 空間浪費);不等長記錄(優點: 省空間; 缺點: 處理不便, 速度慢);流式文件是記錄式文件的特例。編號:01kn-1記錄記錄記錄記錄讀/寫指針7.3.2 文件的物理組織 物理組織: 邏輯組織到磁盤塊的映射。文件: 記錄(字節)序列磁盤: 塊(block)序列考慮因素:記錄格式: 等長或不等長, 流式不必考慮;空間開銷: 除保存文件內容之外的存儲開銷;訪問速度: 順序/隨機訪

5、問速度;長度變化: 動態增長/減少。組織形式: 順序結構、鏈接結構、索引結構、散列結構、倒排結構。7.3.2 文件的物理組織(Cont.) 順序結構 又稱連續結構。一個文件占有若干連續的磁盤塊。FCB首塊號28塊數4塊28塊29塊30塊31磁盤空間優 點: 速度快, 節省空間; 缺 點: 長度變化困難。 鏈接結構：又稱串聯結構, 一文件可存于不連續塊中, 塊間以指針相連。7.3.2 文件的物理組織(Cont.)優 點: 長度變化容易。缺 點: 隨機訪問速度慢。FCB首塊號28塊數4塊28塊30塊45塊46磁盤空間7.3.2 文件的物理組織(Cont.) 索引結構 一文件可存于不連續塊中, 塊號

6、記在索引塊中。優 點: 隨機訪問速度快; 長度變化容易。缺 點: 額外需要索引塊, 存儲開銷大; FCB索引塊號28塊數4塊43塊87塊97塊98磁盤空間0431872973984索引塊287.3.2 文件的物理組織(Cont.) 散列結構 適用于定長記錄和按鍵隨機查找的訪問方式; 通常用于構造文件目錄, 一個記錄內容就是一個目錄項。 計算地址: hash(key)=addr (在磁盤或文件中的存放位置)7.3.2 文件的物理組織(Cont.) 問 題: 給定 key1 key2 , 有 hash(key1) = addr1 , hash(key2) = addr2 , 若addr1=addr

7、2 , 則發生conflict 。 Conflict resolution: 順序探查法: 如發生沖突, 則在沖突位置開始 順序探查第一個空閑的存儲位置。 記錄中增加兩個域: 沖突計數; 記錄位置的空閑標志。7.3.2 文件的物理組織(Cont.) 保存記錄: 保存記錄的鍵值為 key .地址空閑標志沖突計數addr:12鍵值key記錄內容1鍵值key1記錄內容Hash(key)=addr文件空間保存記錄 key計算hash(key) addr, adaddr對應的記錄位置沖突記數加1位置 ad 空閑?ad指向下一個記錄位置ad記錄位置標記為占用記錄key內容ad記錄位置保存記錄 key結束F

8、T7.3.2 文件的物理組織(Cont.) 查找記錄: 查找鍵值為key的記錄。查找記錄keyhash(key)ad,addr取ad對應記錄的沖突記數countad記錄鍵值=keycount-count=0找到結束未找到結束ad記錄空閑hash(ad.key)=addrcount=0ad指向下一個記錄位置FFFFFTTTTT7.3.2 文件的物理組織(Cont.) 刪除記錄: 刪除鍵值為key的記錄。刪除記錄key調用“查找記錄key”找到key?記錄key不存在返回addr=hash(key)ad.空閑標志=0addr.沖突計數減1刪除記錄key返回FT特點:按關鍵字檢索速度快。用途:常用于

9、目錄檢索。注意:Hash空間可循環使用, 滿時保存失敗。7.3.2 文件的物理組織(Cont.)倒排結構 鍵: 記錄中的域稱為鍵;主鍵: 記錄中能唯一區分文件中所有記錄的鍵 稱為主鍵; 其它鍵稱為次鍵。倒排結構: 以鍵值和記錄地址構成的索引結構 稱為倒排結構。主索引: 鍵值為主鍵的索引稱為主索引;次索引: 鍵值為次鍵的索引稱為次索引。7.3.2 文件的物理組織(Cont.)表7-1 各種文件物理結構的主要特性特性 物理 結構長度變化內存開銷外存開銷順序訪問速度按號隨機訪問速度按鍵隨機訪問速度定長變長定長變長定長變長順序結構難小小快快快慢慢慢鏈接結構易小小快快慢慢慢慢索引結構易大大快快快慢慢慢散

10、列結構易小小快倒排結構易大大快快UNIX文件物理結構 P389390)i_addr0i_addr9i_addr10i_addr11i_addr12i_node文件最大長度=10+256+2562+2563(塊)多級索引+鏈接結構信息塊索引塊7.3.2 文件的物理組織(Cont.)例：在UNIX系統中，設磁盤物理塊大小為1KB，每個索引塊可以 保存256個索引項。假設某UNIX文件大小為1028KB。 請畫出該UNIX文件的物理結構； 計算訪問以下邏輯塊號（邏輯塊號從0開始）時， 需要多少次I/O傳輸： 265； 266； 1025。解： 零級索引和一級索引能保存的塊數10256266塊； 剩下

11、的1028266762塊，可用二級索引。 7622562+250，即占用二級索引的3個索引項。 該文件的UNIX物理結構如圖所示。 根據文件的物理結構，訪問邏輯塊號 265需要2次I/O； 266需要3次I/O ； 1025需要3次I/O7.3.2 文件的物理組織(Cont.)i_addr0i_addr9i_addr10i_addr11i_addr12i_nodenull。邏輯塊0邏輯塊9邏輯塊10邏輯塊265。邏輯塊266邏輯塊521邏輯塊522邏輯塊777邏輯塊778邏輯塊1027。null250塊256塊256塊256塊給定的UNIX文件的物理結構7.3.2 文件的物理組織(Cont.)

12、7.4 文件目錄7.4.1 文件控制塊與目錄項文件控制塊(FCB) 文件存在的標志, 其中保存系統管理文件需要的全部信息; 每個文件一個FCB, 保存在外存; 建立文件時創建, 刪除文件時撤銷。 目錄項 目錄文件中的一項, 內容為FCB; 通常目錄項名為文件名。7.4.2 文件目錄與目錄文件文件目錄 用于檢索文件的目錄; 目錄項構成的有序序列; 給定一個文件名, 通過查找文件目錄找到相應的目錄項(FCB)。 目錄文件 內容為目錄項的文件, 長度固定的記錄式文件; 實現文件目錄的管理。文件控制塊FCB文件名文件號用戶名文件地址文件長度記錄大小文件類型文件屬性共享說明文件邏輯結構文件物理結構建立日

13、期保存日期最后修改日期和時間最后訪問日期和時間口令其它目錄項1(FCB1)目錄項2 (FCB2)目錄項n (FCBn)目錄文件 目錄, 文件圖示 :文件目錄7.4.2 文件目錄與目錄文件(Cont.)7.4.3 單級目錄與多級目錄單級目錄(Single-Level Directory) 整個系統只有一個目錄, 所有文件均登記在該目錄中。FCB1FCB2FCBiFCBnfile1file2fileifilen目錄文件普通文件單級目錄結構缺點: Naming problem; Grouping problem Protection problem.單級目錄例:7.4.3 單級目錄與多級目錄(Con

14、t.) 二級目錄(Two-Level Directory) 系統目錄(公共目錄), 用戶目錄(私用目錄); 為每個用戶單獨設置目錄。FCB1FCBj用戶目錄普通文件USER1USERiUSERkFCB1FCBmFCB1FCBn系統目錄二級目錄結構7.4.3 單級目錄與多級目錄(Cont.)二級目錄例:特點: Path name; Can have the same file name for different user; Efficient searching; No grouping capability.7.4.3 單級目錄與多級目錄(Cont.) 多級目錄(Multi-Level Di

15、rectory) 目錄為樹形結構; 葉結點是一般文件或目錄文件; 非葉結節點是目錄文件; 根結點稱作根目錄文件。優點: 便于文件分類; 查找速度快(由于每個文件目錄下文件少); 可以實現文件連接(Link)。7.4.3 單級目錄與多級目錄(Cont.)多級目錄例:rootUnixbinusrlibdevetcVIusersWangLiSd1d2f1flibclibCClpConsolebinYaccPasswordf27.4.3 單級目錄與多級目錄(Cont.) 將FCB分為次部和主部兩部分。次部: (文件名, 文件號) 長度固定(UNIX 16 bytes);保存在目錄文件中。主部: (其它

16、, 連接記數)記錄長度固定(UNIX 32 bytes);保存在外存固定區域, 打開時讀入內存;給定文件號, 可計算主部位置。改進的好處可以提高查找速度(順序查找)可以實現文件連接(link)7.4.4 文件目錄的改進改進的文件目錄圖示:文件號FCB主部1FCB1主部2FCB2主部nFCBn主部目錄項1(FCB1次部)目錄項2 (FCB2次部)目錄項n (FCBn次部)文件目錄目錄文件7.4.4 文件目錄的改進(Cont.)順序查找n個記錄， 找到一個記錄的平均查找記錄的次數 =(1+2+n)/n=(n+1)/2設未分次部和主部的FCB構成的文件目錄占n個磁盤塊， 則順序查找文件目錄，找到一個

17、文件目錄的平均訪問磁盤塊的次數=(n+1)/2 設次部構成的文件目錄占m個磁盤塊，則順序查找文件目錄，找到一個文件的平均訪盤次數(m+1)/2+17.4.4 文件目錄的改進(Cont.)7.4.5 根目錄與當前目錄根目錄 樹狀結構(多級目錄)文件系統中, 根結點對應的目錄稱為根目錄; 根目錄保存在外存空間固定位置。當前目錄 目前正在使用的工作目錄稱為當前目錄。查找路徑 由根目錄開始查找; 由當前目錄開始查找。查找算法 順序查找(UNIX); hash查找; 對分查找(要求文件名排序)。7.4.6 文件目錄的查找7.5 文件的共享文件共享: 多個進程共用系統中的同一個文件; 操作系統和文件使用者

18、共同完成文件共享控制。7.5.1 文件共享的目的 節省存儲空間: cc, vi, yacc 的共享; 進程相互通信7.5.2 文件共享的模式異步使用同一文件: 任意時刻只能有一個進程使用一個文件;同時使用同一文件: 多個進程可以同時使用同一個文件(R/W規則)。7.5.3 文件共享的實現公共目錄: 系統設若干所有用戶都能訪問的公共目錄, 共享文件登記在公共目錄中;連 接: 通過連接使一個文件具有多個名字, 不同用戶通過不同名字訪問同一個文件;共享說明: 創建文件時規定共享用戶及其使用權限。7.5 文件的共享(Cont.)7.5 文件的共享(Cont.)文件共享實現鏈接例:rootusruser

19、swanglid1d2f1f2, 15f1, 15i_number=15link(“/usr/users/wang/d2/f1”, “/usr/users/li/f2”);unlink(“/usr/users/wang/d2/f1”);7.6 文件的保護、保密與安全 保護: 防止用戶對文件進行非授權的訪問。 保密: 防止文件內容泄露。 安全: 防止文件被破壞。 自然因素 人為因素7.6.1 文件的保護(Protection)File owner/creator should be able to control: what can be done; by whom .Types of acce

20、ss Read Write Execute Append Delete List7.6.1 文件的保護(Protection) 存取控制矩陣: amn ， m個用戶, n個文件。f1fjfnu1a11a1ja1nuiai1aijainumam1amjamnaij :rweamd特點: 權限規定細, 過于繁瑣, 占較多存儲空間。7.6.1 文件的保護(Protection) 用戶分成若干類; 同類用戶對同一文件訪問權限相同; 不同類用戶對同一文件訪問權限不同; UNIX 用戶分類 4類: 文件主, 同組用戶, 其它用戶, 特權用戶。 訪問權限說明 RWERWERWE文件主權限同組用戶權限其他用戶

21、權限特權用戶權限訪問權限說明7.6.1 文件的保護(Protection) 分級目錄 多級目錄系統中, 規定不同用戶對同一子目錄的訪問權限; 如果用戶不能訪問某一目錄, 即該用戶不能訪問該目錄下的任何文件。7.6.2 文件的保密 口令 創建文件時用戶規定一個口令, 系統將其記在FCB中; 訪問文件要求給出口令, 并與FCB中口令比較。 特點: 簡單; 保密性不強(eg. 對系統操作員不保密)。 密碼 保存時加密(key); 讀取時解密(key). 特點: 對文件內容加密, 速度慢; 效果好。文件加/解密簡單實現 保存時, 用一個key啟動一個隨機數發生器, 產生一個 隨機數序列, 將其依次“添

22、加”到文件的各個字中。 讀取時, 用同一個key啟動同一個隨機數發生器, 產生 相同隨機數序列, 將其依次由文件的各個字中”減去” 。 線性同余法產生偽隨機數： void random(int *key) *key = (*key)*C1+C2) % C3; 7.6.2 文件的保密(Cont.)C1, C2是質數常量, C3是隨機數范圍(0C3-1);key通常叫隨機源, 也叫種子, 它決定產生的隨機數序列的隨機性。7.6.3 文件系統的安全 Backup 定期將磁盤上文件備份到磁帶上; 發生故障時由磁帶恢復(limited recovery)。 實現方法 轉儲: 文件由磁盤備份到磁帶的過程;

23、 完全轉儲: 定期將磁盤上文件全部備份到磁帶上; 增量轉儲: 開始時做一次完全轉儲; 之后, 每次只對與上次不同的數據進行備份。 差分轉儲: 開始時做一次完全轉儲; 之后, 每次只對與第一次不同的數據進行備份。磁盤整理 利用轉儲和恢復可以對磁盤進行整理。 (使文件物理塊連續, 空閑盤塊連續)7.7 文件系統的實現7.7.1 內存所需的表目 系統打開文件表(系統一個): 存于OS空間FCB主部文件號共享計數修改標志 文 件 號 : 用于確定FCB主部在外存中的位置; 共享計數 : 記錄使用該文件的進程個數, 為0時表示該表項為空表項; 修改標志 : 若FCB被修改過, 則關閉文件時需要把內存的F

24、CB寫回外存。7.7.1 內存所需的表目(Cont.) 用戶打開文件表文件描述符打開方式讀寫指針入口(地址)0n-1 文件描述符就是用戶打開文件表項位置(非負整數), 打開文件時返回給進程; 用戶打開文件表位置存在進程PCB中; 系統可以單設空間, 也可以放在進程的PCB中。讀寫指針應該是文件的邏輯地址，初值應為0，隨著讀寫調整。 用戶打開文件表/系統打開文件表的聯系文件描述符打開方式讀寫指針入 口kl用戶打開文件表進程Pi文件描述符k進程Pj文件描述符lPCB共享計數其它2系統打開文件表7.7.1 內存所需的表目(Cont.) 表項: (首空閑塊號, 空閑塊數); 表尾標記: 空閑塊數為0;

25、 分配方式: 最先適應, 下次適應、最佳適應, 最壞適應等; 存放位置: 平時外存, 使用時讀入內存系統區。 空閑塊表: 適于連續物理組織結構的文件系統。 空閑塊鏈 所有空閑塊連成一個鏈; 申請/釋放以塊為單位, 都對鏈頭操作; 節省空間, 但速度慢(申請/釋放都需要1次I/O);7.7.2 外存空間的管理7.7.2 外存空間的管理(Cont.) 位示圖: 字位映像圖 位示圖的 1 位表示外存一塊的狀態; 申請: 找到位示圖中為 0 的字位, 將該字位改為 1 , 返回該字位對應的塊號; 釋放: 將位示圖中釋放塊號對應的字位置 0; 存放位置: 平時外存, 使用時讀入內存, 若有修改寫回外存。

26、 成組鏈接(Unix): 空閑塊鏈與空閑塊表的結合。 多個(最多100個) 空閑塊為1組, 組之間相互鏈接; 最前面的組緩沖到內存; 該組稱作超級塊。 超級塊結構(P393394):struct filesys int s_nfree; /組中空閑塊個數(100); int s_free100; /s_free0指向下一組; /其它為本組中空閑塊號; super_block;7.7.2 外存空間的管理(Cont.)空閑塊的成組鏈接圖示:s_nfree100s_free0s_free1n11s_free99n199100n21n299100n31n399Knj1njK-1超級塊空閑塊組表空閑塊的

27、成組鏈接例: P394圖13.14空閑塊組表空閑塊組表7.7.2 外存空間的管理(Cont.)上述結構表示：磁盤中共有 1(j-1)100(K-1)個空閑塊.初始超級塊如下：s_nfree1s_free0s_free1nulls_free99null100n21n299100n31n399Knj1njK-1超級塊空閑塊組表空閑塊組表空閑塊組表100n11n199空閑塊組表7.7.2 外存空間的管理(Cont.)s_nfree39s_free050s_free140s_free381210015014951#50100350349251#250100250249151#15087NULL4493

28、51#350#351#449#40#12#149#51#249#151#349#251內存超級塊7.7.2 外存空間的管理(Cont.)成組鏈接的空閑塊管理: 超級塊已讀入內存。 申請: s_nfree1, 取塊號s_free-s_nfree分配; s_nfree=1, 將s_free0所指連接塊讀入內存 (作為超級塊), 分配塊號s_free0。 釋放: s_nfree100, s_frees_nfree+=釋放塊號; s_nfree=100, 將s_nfree和s_free拷貝到釋放塊中, 將該塊號記錄到s_free0, s_nfree=1。7.7.2 外存空間的管理(Cont.)7.8

29、文件系統的界面 創建文件: creat(path_name, fcb_args)參數說明path_name: 文件路徑名;fcb_args: FCB參數。執行步驟:為此文件分配一個FCB主部, 初始化;將文件名和文件號作為FCB次部填到末級目錄中;以寫方式打開。例如: creat(“/usr/li/d1/f1”, mode) 打開文件: fd=open ( path_name, mode )參數說明: path_name: 文件路徑名; mode: 打開方式.執行步驟根據文件路徑名查目錄找到FCB次部;合法性檢查(根據打開方式、共享說明、用戶身份);根據文件號查系統打開文件表看該文件是否已被打

30、開, 如是則共享計數加1; 否則找一個空閑的系統打開文件表項, 并將外存中FCB主部等信息填入此表項, 共享計數置為1;在用戶打開文件表中找一空表項, 填寫打開方式和 讀寫指針(初值為0), 并指向系統打開文件表的對應表項。返回信息: fd: 文件描述符(用戶打開文件表入口), 一個非負整數。7.8 文件系統的界面(Cont.) 關閉文件: close ( fd ) 參數說明: fd: 文件描述符。 執行步驟:由 fd 查用戶打開文件表, 找到系統打開文件表入口;系統打開文件表中共享計數減 1 ; 如減 1 后的值為0且修改標志為 1 , 則將此 FCB 由內存寫回外存FCB主部;將 fd 所

31、對應的用戶打開文件表項置為空閑。 7.8 文件系統的界面(Cont.) 指針定位: seek ( fd, offset )參數說明: fd: 文件描述符; offset: 新的指針位置。執行步驟: 由 fd 查用戶打開文件表, 找到對應的入口; 檢查參數合法性; 將用戶打開文件表中文件讀寫指針位置設定為offset, 后續讀寫命令由該指針處存取文件內容。7.8 文件系統的界面(Cont.) 讀文件: read ( fd , nrd , buf ) 參數說明:fd: 文件描述符;nrd: 讀入記錄個數;buf: 內存起始位置。 執行步驟:由 fd 查用戶打開文件表, 找到對應的系統打開文件表入口

32、;合法性檢查(用戶打開文件表中所記錄的打開方式、存取方式);根據讀寫指針和文件物理結構，計算讀寫指針對應的磁盤物理地址 addr(物理塊號, 偏移);把從addr開始的 nrd 個記錄讀入內存中由 buf 起始的區域；調整文件讀寫指針為：當前讀指針sizeof(記錄結構)nrd。7.8 文件系統的界面(Cont.) 寫文件: write ( fd, nwt , buf )參數說明: fd: 文件描述符; nwt : 寫出記錄個數; buf: 內存起始位置。 執行步驟: 由 fd 查用戶打開文件表, 找到對應的入口;合法性檢查(用戶打開文件表中所記錄的打開方式、存取方式);根據讀寫指針及文件物理

33、結構計算當前讀寫指針對應的 磁盤物理地址(物理塊號I, offset);如果：塊號I=文件最末塊號& offsetsizeof(記錄結構)nwt磁盤塊大小; 則需要： 申請磁盤塊; 修改文件物理結構表；將內存中由 buf 起始的 nwt 個記錄 寫到地址(物理塊號I, offset)起始的磁盤區域;調整讀寫指針：當前讀寫指針sizeof(記錄結構)nwt 。7.8 文件系統的界面(Cont.) 建立連接: link (old_name , new_name )參數說明: old_name: 已存在的文件路徑名; new_name: 欲連接的文件路徑名。執行步驟: 查目錄找到文件old_name

34、的FCB次部, 由此得到文件號; 查目錄找到文件new_name的末級目錄; 將文件號與new_name中末級名字合起來構成一個 新的目錄項, 將其填入new_name的末級目錄文件中; 將FCB主部中的連接計數加1. 例如: link(“/usr/Li/f1”, “/usr/Zhang/d2/f2”)7.8 文件系統的界面(Cont.) 斷開連接: unlink ( path_name ) 參數說明: path_name: 文件路徑名. 執行步驟:查目錄找到文件 path_name 的FCB主部;將連接計數值減 1;如減 1 后的值為 0, 則歸還該文件所占用的全部存儲塊, 該文件將被撤銷;

35、將FCB次部由上級目錄中清除. 例如: unlink(“/usr/Zhang/d2/f2”)7.8 文件系統的界面(Cont.)UNIX文件系統的實現內存所需表目(UNIX)用戶打開文件表u_ofile (每個進程一個)file (整個系統一個)系統打開文件表Inode (整個系統一個)外存空間的管理空閑塊表字位映像圖(Linux)成組連接 (UNIX approach)UNIX內存表目：1. u_ofile (每進程一個)struct user int u_ofileNOFILE; #define NOFILE 15 2. file (系統一個)struct file char f_flag

36、; /R,W,PIPE char f_count; /使用該文件進程家族的進程個數 int f_inode; /指向inode表項 char *f_offset; /字符讀寫指針 fileNFILE#define NFILE 100UNIX文件系統的實現(Cont.)u_ofile的下標為文件描述符fd，u_ofilefd指向file表的表項。目錄項為UNIX系統的FCBstruct inode /(P395;外存;共32 bytes，外存塊大小512 bytes) int i_mode; /文件類型和用戶權限 char i_nlink; /文件鏈接計數 char i_uid; /文件主id

37、char i_gid; /同組用戶id char i_size0; /most significant of size char *i_size1; /least significant of size int i_addr8; /i_addr0 i_addr5為0級索引， / i_addr6為一級索引； i_addr7為二級索引； int i_atime2; /最后訪問時間 int i_mtime2; /最后修改時間UNIX文件系統的實現(Cont.)UNIX文件系統的實現(Cont.)struct inode (內存：P395396 ) int i_flag; /主部修改標志 char i

38、_count; /打開該文件的次數；file表項指向該inode表項的個數 char i_dev; char i_number; char i_mode; char i_nlink; /連接計數 char i_uid; char i_gid; char i_size0; char *i_size1; int i_addr8; int i_lastr; i_nodeNINODE;表間聯系：u_ofile file (n) (1)file inode (n) (1)read(4,)read(4,)write(6,)用戶空間u_ofileu_ofilefilei_node磁盤空間系統空間.數據塊.i

39、_list表間聯系UNIX外存空間管理：0 1 2 k k+1 n-1導引塊超級塊 inode區域每塊16個inode, 從0起依次編號 文件存儲區域(普通文件,目錄文件)超級塊(super block)： (1) 記載文件卷上k+1塊到n-1塊中所有空閑塊， (2) inode區中100個空閑inode. (緩存) 文件安裝(mount)后超級塊讀入內存。注：占用區域已經記載在各個文件的inode中。Struct filesys int s_isize; /size in blocks of i list int s_fsize; /size in blocks of entire volu

40、me int s_nfree; /number of in core free blocks int s_free100; /in core free blocks int s_ninode; /number of in core I list int s_inode100; /in core free I nodes char s_flock; /free list locking char s_ilock; /i list locking char s_fmod; /super block modified flag char s_ronly; /mounted read only fla

41、g char s_time2; /current date of last update int pad50;空閑塊管理：100個空閑塊為一組，組之間相互鏈接。s_nfree=88s_free0s_free1.s_free87.Super block .特點：速度快，空間省。空閑塊管理：申請時： (1) s_nfree1, 取s_free-s_nfree; (2) s_nfree=1, 將s_free0所指連接塊讀入內存,分配s_free0.釋放時: (1) s_nfree0, 取s_inode-s_ninode; (2) s_ninode=0, 由磁盤inode區順取100個空閑I節點(i_

42、nlink=0) 將其編號填入s_inode表中，修改s_ninode，然后分配。釋放時： (1) s_ninode100, s_inodes_ninode+=i_number (釋放的); (2) s_ninode=100, 丟棄。文件系統界面(UNIX系統調用)creatopencloseseekreadwritelinkunlinkpipemknodesmountsumountchmodchownerstatefstatechdirfd=creat(pathname,mode)pathname: 路徑名；mode: 共享說明；1. 在外存分配一個主部inodei_number, 初始化(

43、i_size=0, i_mode=mode, i_nlink=1,i_uid=u_uid, i_gid=u_gid ),;2. 填寫目錄項(name, i_number)；3. 以寫方式打開,填寫系統打開文件表i_nodenum 和用戶打開文件表、filen2表項：.f_inode=num; . f_flag=w; .f_offset=0; f_count=1; u_ofilefd=n2；4. 返回文件描述符fd。例子：creat(“d1/d2/f1”, mode) 假定分配i_number=15, (f1,15)d2中(?,-1)文件系統界面(UNIX系統調用)fd=open(pathnam

44、e,mode)pathname: 路徑名；mode: 打開方式；返回值：fd: 文件描述符(u_ofile表的入口, u_ofile的下標)1. 查目錄找inode(移入內存i_count=1, 如已在內存i_count+);2. 權限檢查(mode打開方式, i_mode共享說明, i_uid, i_gid文件 主（組）, u_uid, u_gid用戶身份);3. 在file表中分配一個filen表項，指向該內存i_node; 初始化 f_count=1; f_offset=0; f_flag=mode;4. 取一空閑u_ofilefd表目，u_ofilefd=n指向file表中對應表目;5

45、. 返回文件描述符fd(在u_ofile表中的入口)。文件系統界面(UNIX系統調用)close(fd)fd: 文件描述符；1. 由fd查u_ofile找到對應入口；2. 由u_ofilefd找到file表對應入口；3. f_count-, 如0,則轉6；(同一家族的其它進程還沒結束)4. 由f_inode找到對應inode；4. i_count-, 如為0，i_flag標志有修改，寫回外存inode區；6. u_ofilefd=-1(空閑標志）文件系統界面(UNIX系統調用)seek(fd, whence, offset)fd: 文件描述符；whence: 相對位置(0,1,2,3,4,5)

46、=(頭,尾,當前位置)offset: 整數，移動量；1. 由u_ofilefd找到file表入口；2. 由f_inode找到內存inode;3. 檢查參數合法性(i_size0, i_size1, f_offset, offset, whence);4. 按參數要求調整f_offset指針。文件系統界面(UNIX系統調用)Whence：0,1,2為字節，3,4,5為塊nrd=read(fd,buf,count)fd: 文件描述符；buf: 進程空間接收區地址；count: 讀字節數；1. 由u_ofilefd，找到file表對應入口；2. 檢查訪問權限(f_flag, READ);3. 由f_

47、inode找到內存inode入口；4. 由f_offset, count和i_addr計算訪問磁盤塊號(可能多個塊) ; (bmap函數)5. 啟動IO設備讀取盤塊到系統緩沖區中(如buffer無,切換進程);6. 緩沖區信息復制到進程空間(iomove)；7. 返回實際傳輸字節數nrd；8. 調整讀寫指針f_offset：f_offset+=nrd.文件系統界面(UNIX系統調用)nwt=write(fd,buf,count)fd: 文件描述符；buf:進程空間發送地址；count: 寫字節數；1. 由u_ofilefd，找到file表對應入口；2. 檢查訪問權限(f_flag, WRITE

48、);3. 由f_inode找到內存inode入口；4. 由f_offset, count和i_addr計算磁盤地址塊號(可能分盤塊）；5. 申請系統緩沖區，將buf起始count數據送到緩沖區(可多次)；6. 緩沖區鏈到設備IO鏈上, 如設備空閑啟動設備；7. 修改inode中文件長度i_size; (覆蓋時可能不修改)8. 返回實際傳輸字節數nwt;9. 調整讀寫指針f_offset：f_offset+=nwt.文件系統界面(UNIX系統調用)pipe(fd)int fd2;1. 分配一個inode(i_count=2);2. 分配2個file表目(f_flag分別為pipeR和pipeW，

49、讀/寫指針f_offset為0）3. 分配2個u_ofile表目, 分別指向2個file表目；4. 返回2個文件描述符fd0,fd1, 分別為u_ofile中的2個入口。文件系統界面(UNIX系統調用)Pipe文件同步與互斥pipe讀寫同步寫滿：寫者等待，讀出后喚醒讀空：讀者等待，寫入后喚醒讀寫關閉所有讀者關閉：寫時返回錯誤信號所有寫者關閉：讀者立即返回讀寫互斥i_flag|ILOCK i_addr i_count (2) f_flag (R pipe)f_offset=0f_inodepf_count =1f_flag (W pipe)f_offset=0f_inodepf_count =1

50、內存inode表內存file表fd0fd1u_ofile表進程執行pipe(fd)之后 i_addr i_count (2) f_flag (R pipe)f_offset=0f_inodepf_count =2f_flag (W pipe)f_offset=0f_inodepf_count =2內存inode表內存file表fd0fd1u_ofile表fork創建子進程1（讀者）之后fd0fd1父進程:子進程1: i_addr i_count (2) f_flag (R pipe)f_offset=0f_inodepf_count =3f_flag (W pipe)f_offset=0f_i

51、nodepf_count =3內存inode表內存file表fd0fd1u_ofile表fork創建子進程2（寫者）之后fd0fd1父進程:子進程1:子進程2:fd0fd1 i_addr i_count (2) f_flag (R pipe)f_offsetf_inodepf_count =2f_flag (W pipe)f_offsetf_inodepf_count =2)內存inode表內存file表fd0fd1u_ofile表父進程close(fd0),close(fd1)fd0fd1父進程:子進程1:子進程2:fd0fd1 i_addr i_count (2) f_flag (R pi

52、pe)f_offset=0f_inodepf_count =2f_flag (W pipe)f_offset=0f_inodepf_count =1內存inode表內存file表fd0fd1u_ofile表子進程1(讀者) : close(fd1)fd0fd1父進程:子進程1:子進程2:fd0fd1 i_addr i_count (2) f_flag (R pipe)f_offset=0f_inodepf_count =1f_flag (W pipe)f_offset=0f_inodepf_count =1內存inode表內存file表fd0fd1u_ofile表子進程2(寫者) : clos

53、e(fd0)fd0fd1父進程:子進程1:子進程2:fd0fd1 i_addr i_count (2) f_flag (R pipe)f_offset=count0f_inodepf_count =1f_flag (W pipe)f_offset=count1f_inodepf_count =1內存inode表內存file表u_ofile表子進程2(寫) : write(fd1,buf1,count1)子進程1(讀) : read(fd0,buf0,count0)父進程:子進程1:子進程2:fd0fd1fd0fd1fd0fd1write(fd1,)read(fd0,) 盤塊(有緩沖) i_ad

54、dr i_count (1) f_flag (R pipe)f_offsetf_inodepf_count =1f_flag (W pipe)f_offsetf_inodepf_count =0內存inode表內存file表u_ofile表子進程2(寫完) :close(fd1)父進程:子進程1:子進程2:fd0fd1fd0fd1fd0fd1close(fd1)read(fd0,) 盤塊(有緩沖) i_addr i_count (0) f_flag (R pipe)f_offsetf_inodepf_count (0)f_flag (W pipe)f_offsetf_inodepf_count

55、 (0)內存inode表內存file表u_ofile表子進程1(讀完) :close(fd0)父進程:子進程1:子進程2:fd0fd1fd0fd1fd0fd1close(fd1)close(fd0)Pipe文件同步與互斥pipe讀寫同步寫滿：寫者等待，讀出后喚醒讀空：讀者等待，寫入后喚醒讀寫關閉所有讀者關閉：寫時返回錯誤信號所有寫者關閉：讀者立即返回讀寫互斥i_flag|ILOCK管道通訊的局限性只有相關進程(同一家族進程)能通訊先創建管道再創建子進程, 子進程繼承父進程打開的文件(包括管道文件)管道是沒有名字的文件所有進程都關閉后即被撤銷命名管道(FIFO)長久性通訊機構具有文件名可被打開、

56、讀寫、關閉和刪除任何進程都能找到它即使是不同祖先的進程，也可以利用命名管道進行通信。讀取和寫入遵循FIFO原則阻塞：管道讀: 假如沒有線程實行寫管道操作，讀線程將一直阻塞，直到有線程往里面寫為止；管道寫: 假如沒有線程實行讀操作，寫線程將一直阻塞，直到有線程讀數據為止。不阻塞：管道讀：假如沒有線程實行寫管道操作，讀線程將立即返回；管道寫：假如沒有線程實行讀操作，寫線程將立即返回，返回不正確碼-1。link(oldpathname, newpathname)oldpathname: 已存在文件名；newpathname: 待連接文件名；1. 查目錄找到oldpathname(inode);2.

57、查目錄找到newpathname的末級目錄；3. 檢查操作合法性；4. Inode的i_nlink+；5. (name, i_number)newpathname的末級目錄。例子：link(“d1/d2/f1”,“d1/d3/f2”)d1,d2,f1: 存在；d1,d3: 存在，f2: 不存在，文件系統界面(UNIX系統調用)unlink(pathname)pathname: 文件路徑名；1. 查目錄找到pathname(inode);2. i_nlink-; 如結果為0, 釋放所有磁盤塊 (刪除文件)；3. 清除末級文件名在末級目錄中的登記。例子：unlink(“d1/d2/f1”) 假定：

58、f1文件號i_number=15; 操作后：f1的i_nlink-, d2中原(f1, 15)改為(f1, -1)文件系統界面(UNIX系統調用)mknode(pathname, type and permissions, dev)pathname: 節點名；type and permissions: 節點類型和訪問權限；dev: 主次設備號；1. 如非特權用戶，失敗；2. 建立一個i_node, 初始化(i_addr0=dev);文件系統界面(UNIX系統調用)struct mount int m_dev; int *m_bufp; /超級塊 int *m_inodep;mountNMOUN

59、T;#define NMOUNT 5devrootrk01Makenode創建usrLid01安裝: smount(“/dev/rk01”, “/usr/Li/d01”, 0)卸下: sumount(“/dev/rk01”)i_flag =| FMOUNT文件系統界面(UNIX系統調用)bit: 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Set uidSet gid大文件00普通01字符10目錄11塊型i_mode: i_flag:ILOCKIUPDIACCIMOUNTIWANTITEXT執行該文件進程的身份暫時改為文件主的身份即: u_uid = i_uid

60、smount(special_pathname, directory_pathname, roflag)special_pathname: 特殊文件名directory_pathname: 目錄文件名（安裝節點）roflag: 只讀標志1. 檢查是否超級用戶；2. 找到special_pathname文件的inode(用mknode建立);3. 合法性檢查（特殊塊型文件）；4. 找到directory_pathname節點的inode;5. 如非目錄或引用數大于，錯返；6. 讀入super block到buf，按filesys格式解釋.7. 安裝節點inode的i_addr0=設備文件i_ad