第4章 文件系統(tǒng)

1、1File Systems第4章 文件系統(tǒng)4.1 文件 4.2 目錄 4.3 文件系統(tǒng)的實(shí)現(xiàn) 4.4 文件系統(tǒng)管理和優(yōu)化 2長期存儲(chǔ)信息能夠存儲(chǔ)大量信息使用信息的進(jìn)程終止時(shí)，信息仍舊存在多進(jìn)程能夠并發(fā)存取有關(guān)信息3長期存儲(chǔ)信息目前可把磁盤當(dāng)作一種固定塊大小的線性序列，并支持如下兩種操作： 讀塊k 寫塊k 原則上可解決長期存儲(chǔ)的問題4存在的問題 如何找到信息 如何防止一個(gè)用戶讀取另一個(gè)用戶的數(shù)據(jù) 如何知道哪些塊是空閑的5 一個(gè)新的抽象文件 文件是進(jìn)城創(chuàng)建的信息邏輯單元。 文件用來對(duì)磁盤建模，以代替對(duì)隨機(jī)存儲(chǔ)器的建模 可把文件看成一種地址空間6文件系統(tǒng)7文件命名文件結(jié)構(gòu)文件類型文件存取文件屬性文件

2、操作5.1 用戶視角下的文件8文件命名擴(kuò)展名擴(kuò)展名含義含義File.bak備份文件File.cC源程序文件File.gif符合圖形交換格式的圖像文件File.hlp幫助文件file.htmlWWW超文本標(biāo)記語言文檔File.jpg符合JPEG編碼標(biāo)準(zhǔn)的靜態(tài)圖片F(xiàn)ile.mp3符合MP3音頻編碼格式的音樂文件File.mpg符合MPEG編碼格式的電影File.o目標(biāo)文件（編譯器輸出格式，尚未連接）File.pdfPdf格式的文件File.psPostScript文件File.tex為TEX格式化程序準(zhǔn)備的輸入文件File.txt一般正文文件File.zip壓縮文件典型的文件擴(kuò)展名典型的文件擴(kuò)展名

3、9文件結(jié)構(gòu) 三種文件結(jié)構(gòu) 字節(jié)序列 記錄序列 樹10 其他文件1. 順序文件2.索引順序文件3.索引文件4 散列文件11順序文件 邏輯記錄的排序： 文件是記錄的集合。文件中的記錄可以是任意順序的，一般可歸納為以下兩種情況： 串結(jié)構(gòu)-記錄之間的順序與關(guān)鍵字無關(guān)。 順序結(jié)構(gòu)-文件中的所有記錄按關(guān)鍵字排序。 對(duì)順序結(jié)構(gòu)文件可有更高的檢索效率。 12順序文件的優(yōu)缺點(diǎn)順序文件的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)優(yōu)點(diǎn) 對(duì)諸記錄進(jìn)行批量存取時(shí)，存取效率最高； 只有順序文件才能存儲(chǔ)在磁帶上并能有效地工作； 缺點(diǎn)缺點(diǎn) 交互應(yīng)用時(shí)性能很差； 增加或修改一個(gè)記錄比較困難；為了解決這一問題，可以為順序文件配置一個(gè)運(yùn)行記錄文件(Log Fi

4、le)或稱為事務(wù)文件(Transaction File)，把試圖增加、刪除或修改的信息記錄于其中，規(guī)定每隔一定時(shí)間，例如4小時(shí),將運(yùn)行記錄文件與原來的主文件加以合并，產(chǎn)生一個(gè)按關(guān)鍵字排序的新文件。 13索引文件 對(duì)于定長記錄文件，如果要查找第 i 個(gè)記錄， 可直接根據(jù)下式計(jì)算來獲得第 i 個(gè)記 錄相對(duì)于第一個(gè)記錄首址的地址：A i =i L 對(duì)于變長記錄較難實(shí)現(xiàn)直接存取。為了解決這一問題，可為變長記錄文件建立一張索引表索引表。索引表本身是一個(gè)定長記錄的順序文件。索引文件組織圖如下： 14 在對(duì)索引文件進(jìn)行檢索時(shí)，首先是根據(jù)用戶（程序）提供的關(guān)鍵字，并利用折半查找法 去檢索索引表，從中找到相應(yīng)的

5、表項(xiàng)；再利用該表項(xiàng)中給出的指向記錄的指針值，去訪問所 需的記錄。 15索引順序文件 索引順序文件索引順序文件（Index Sequential File）有效地克服了變長記錄文件不便于直接存取 的缺點(diǎn)，且付出代價(jià)不算大。索引順序文件如下圖： 16keyLogical addressnameatrributeABZAn BingAn KangAn QingBao RongBi JingBon LongindexSequential file索引順序文件索引順序文件17 在對(duì)索引順序文件進(jìn)行檢索時(shí)，首先也是利用用戶（程序）所提供的關(guān)鍵字以及某種 查找方法，去檢索索引表，找到該記錄所在記錄組中第一個(gè)

6、記錄的表項(xiàng)，從中得到該記錄 組第一個(gè)記錄在主文件中的位置；然后，再利用順序查找法去查找主文件，從中找到記錄 18散列文件 利用散列存儲(chǔ)方式組織的文件，也叫直接存取文件。根據(jù)文件中關(guān)鍵字的特點(diǎn)，設(shè)計(jì)一個(gè)散列函數(shù)和沖突處理方法，將記錄散列到存儲(chǔ)設(shè)備上。19文件類型(a) 可執(zhí)行文件 (b) 存檔文件20文件存取 順序存取 從頭順序讀取文件的全部字節(jié)或記錄 不能跳過某一些內(nèi)容，不能不按順序讀取?？梢苑祷仄瘘c(diǎn)，必要時(shí)可多次讀取該文件。 存儲(chǔ)介質(zhì)是磁盤的情況下，順序文件很方便 隨機(jī)存取 可以任意順序讀取字節(jié)或記錄。 對(duì)數(shù)據(jù)庫系統(tǒng)是必要的 指示從何處開始讀取文件的兩種方法： 每次讀操作都給出開始讀文件的位

7、置 用一個(gè)特殊的seek操作設(shè)置當(dāng)前位置21文件屬性常用的文件屬性22文件操作 Create Delete Open Close Read Write Append Seek Get attributes Set Attributes Rename23使用文件系統(tǒng)調(diào)用的一個(gè)示例程序 (1/2)24使用文件系統(tǒng)調(diào)用的一個(gè)示例程序(2/2)25目錄一級(jí)目錄系統(tǒng) 單層目錄系統(tǒng) 含有四個(gè)文件 屬于3名用戶26兩層目錄系統(tǒng)字母表示文件和目錄的所有者27層次目錄系統(tǒng)28符號(hào)文件目錄的層次結(jié)構(gòu)2930UNIX目錄樹路徑名31目錄操作CreateDeleteOpendirClosedir Readdir Re

8、name Link Unlink32Windows 2000/UNIX API33文件系統(tǒng)的實(shí)現(xiàn) (實(shí)現(xiàn)者角度)一個(gè)可能的文件系統(tǒng)布局34文件的實(shí)現(xiàn) (1)(a) 為7個(gè)文件連續(xù)分配空間(b) 刪除文件D和F后磁盤的狀態(tài)35文件的實(shí)現(xiàn)(2)以磁盤塊的鏈表形式存儲(chǔ)文件36文件的實(shí)現(xiàn)(3)在內(nèi)存中使用文件分配表的鏈表分配37文件的實(shí)現(xiàn)(4)i結(jié)點(diǎn)的例子38A UNIX i-node ( V7 File System)An example i-node39目錄的實(shí)現(xiàn) (1)(a) 簡單目錄，包含固定大小的目錄項(xiàng)，在目錄項(xiàng)中有磁盤地址和屬性(b) 每個(gè)目錄項(xiàng)只引用i節(jié)點(diǎn)的目錄40目錄的實(shí)現(xiàn)(2) 在目

9、錄中處理長文件名的兩種方法： (a) 在行中 (b) 在堆中41The UNIX V7 File System (3)42共享文件 (1)有共享文件的文件系統(tǒng)43共享文件(2)(a) 連接之前的狀況(b) 創(chuàng)建連接之后(c) 當(dāng)所有者刪除文件后 44文件系統(tǒng)管理和優(yōu)化磁盤空間管理 (1) 實(shí)線 (左邊標(biāo)度) 給出磁盤數(shù)據(jù)率 虛線（右邊標(biāo)度）給出磁盤空間利用率Block size45磁盤空間管理(2)(a) 把空閑表存放在鏈表中(b) 位圖46磁盤空間管理(3)在配額表中記錄了每個(gè)用戶的配額47文件系統(tǒng)備份(1) 待轉(zhuǎn)儲(chǔ)的文件系統(tǒng)，方框代表目錄，圓圈代表文件。被陰影覆蓋的項(xiàng)目表示自上次轉(zhuǎn)儲(chǔ)以來未修改過。每個(gè)目錄和文件都被標(biāo)上其i節(jié)點(diǎn)號(hào)File that hasnot changed48文件系統(tǒng)備份(2)邏輯轉(zhuǎn)儲(chǔ)算法所使用的位圖49文件系統(tǒng)一致性 文件系統(tǒng)狀態(tài)(a) 一致(b) 塊丟失(c) 空閑表中有重復(fù)塊(d) 重復(fù)數(shù)據(jù)塊50文件系統(tǒng)性能 (1)緩沖區(qū)高速緩存數(shù)據(jù)結(jié)構(gòu)51文件系統(tǒng)性能(2) i節(jié)點(diǎn)放在磁盤開始位置 磁盤分為柱面組，每組有自己的塊和i節(jié)點(diǎn)52磁盤碎片整理 操作系統(tǒng)初始安裝后，從磁盤的開始位置連續(xù)安裝了程序與文件。 隨著文件被