第13講文件系統(tǒng)

第14講文件系統(tǒng)授課教師：馬立平聯(lián)系方式：maliping@SouthwestUniversityofScienceandTechnology提綱死鎖概念■死鎖處理方法■銀行家算法■死鎖檢測(cè)■進(jìn)程通信概念■信號(hào)和管道■消息隊(duì)列和共享內(nèi)存■提綱文件系統(tǒng)的概念■虛擬文件系統(tǒng)■文件緩存和打開文件■文件分配■空閑空間管理■冗余磁盤陣列RAID■提綱文件系統(tǒng)的概念文件系統(tǒng)和文件文件描述符目錄文件別名文件系統(tǒng)種類■虛擬文件系統(tǒng)■文件緩存和打開文件■文件分配■空閑空間管理■冗余磁盤陣列RAID■文件系統(tǒng)和文件文件系統(tǒng)是操作系統(tǒng)中管理持久性數(shù)據(jù)的子系統(tǒng)，提供數(shù)據(jù)存儲(chǔ)和訪問功能■文件是具有符號(hào)名，由字節(jié)序列構(gòu)成的數(shù)據(jù)項(xiàng)集合■組織、檢索、讀寫訪問數(shù)據(jù)大多數(shù)計(jì)算機(jī)系統(tǒng)都有文件系統(tǒng)Google也是一個(gè)文件系統(tǒng)文件系統(tǒng)的基本數(shù)據(jù)單位文件名是文件的標(biāo)識(shí)符號(hào)文件系統(tǒng)的功能分配文件磁盤空間■管理文件塊（位置和順序）管理空閑空間(位置)分配算法(策略)文件系統(tǒng)的功能分配文件磁盤空間■管理文件集合■定位：文件及其內(nèi)容命名：通過名字找到文件文件系統(tǒng)結(jié)構(gòu)：文件組織方式文件系統(tǒng)的功能分配文件磁盤空間■管理文件集合■數(shù)據(jù)可靠和安全■安全：多層次保護(hù)數(shù)據(jù)安全可靠持久保存文件避免系統(tǒng)崩潰、媒體錯(cuò)誤、攻擊等文件屬性文件頭：文件系統(tǒng)元數(shù)據(jù)中的文件信息■文件屬性■名稱、類型、位置、大小、保護(hù)、創(chuàng)建者、創(chuàng)建時(shí)間、最近修改時(shí)間、…文件屬性文件存儲(chǔ)位置和順序提綱文件系統(tǒng)的概念文件系統(tǒng)和文件文件描述符目錄文件別名文件系統(tǒng)種類■虛擬文件系統(tǒng)■文件緩存和打開文件■文件分配■空閑空間管理■冗余磁盤陣列RAID■打開文件和文件描述符文件訪問模式■進(jìn)程訪問文件數(shù)據(jù)前必須先“打開”文件f=open(name,flag);…read(f,…);…close(f);打開文件和文件描述符內(nèi)核跟蹤進(jìn)程打開的所有文件■文件訪問模式■進(jìn)程訪問文件數(shù)據(jù)前必須先“打開”文件操作系統(tǒng)為每個(gè)進(jìn)程維護(hù)一個(gè)打開文件表文件描述符是打開文件的標(biāo)識(shí)文件描述符打開文件表文件描述符操作系統(tǒng)在打開文件表中維護(hù)的打開文件狀態(tài)和信息■文件指針最近一次讀寫位置每個(gè)進(jìn)程分別維護(hù)自己的打開文件指針文件描述符操作系統(tǒng)在打開文件表中維護(hù)的打開文件狀態(tài)和信息■文件指針文件打開計(jì)數(shù)當(dāng)前打開文件的次數(shù)最后一個(gè)進(jìn)程關(guān)閉文件時(shí)，將其從打開文件表中移除文件描述符操作系統(tǒng)在打開文件表中維護(hù)的打開文件狀態(tài)和信息■文件指針文件打開計(jì)數(shù)文件的磁盤位置緩存數(shù)據(jù)訪問信息文件描述符操作系統(tǒng)在打開文件表中維護(hù)的打開文件狀態(tài)和信息■文件指針文件打開計(jì)數(shù)文件的磁盤位置訪問權(quán)限每個(gè)進(jìn)程的文件訪問模式信息文件的用戶視圖和系統(tǒng)視圖文件的用戶視圖■持久的數(shù)據(jù)結(jié)構(gòu)系統(tǒng)訪問接口■字節(jié)序列的集合(UNIX)系統(tǒng)不關(guān)心存儲(chǔ)在磁盤上的數(shù)據(jù)結(jié)構(gòu)操作系統(tǒng)的文件視圖■數(shù)據(jù)塊的集合數(shù)據(jù)塊是邏輯存儲(chǔ)單元，而扇區(qū)是物理存儲(chǔ)單元塊大小<>

扇區(qū)大小用戶視圖到系統(tǒng)視圖的轉(zhuǎn)換進(jìn)程讀文件■獲取字節(jié)所在的數(shù)據(jù)塊進(jìn)程寫文件■獲取數(shù)據(jù)塊修改數(shù)據(jù)塊中對(duì)應(yīng)部分文件系統(tǒng)中的基本操作單位是數(shù)據(jù)塊■例如,getc()和putc()即使每次只訪問1字節(jié)的數(shù)據(jù)，也需要緩存目標(biāo)數(shù)據(jù)4096字節(jié)返回?cái)?shù)據(jù)塊內(nèi)對(duì)應(yīng)部分寫回?cái)?shù)據(jù)塊訪問模式操作系統(tǒng)需要了解進(jìn)程如何訪問文件■順序訪問:按字節(jié)依次讀取■大多數(shù)的文件訪問都是順序訪問隨機(jī)訪問:從中間讀寫■不常用,但仍然重要例如,虛擬內(nèi)存中把內(nèi)存頁(yè)存儲(chǔ)在文件索引訪問:依據(jù)數(shù)據(jù)特征索引■通常操作系統(tǒng)不完整提供索引訪問數(shù)據(jù)庫(kù)是建立在索引內(nèi)容的磁盤訪問上索引文件示例Smith,Johnsocial-securityage數(shù)據(jù)文件AdamsArthurAsher…Smith索引位置索引文件文件內(nèi)部結(jié)構(gòu)無結(jié)構(gòu)■單詞、字節(jié)序列簡(jiǎn)單記錄結(jié)構(gòu)■分列固定長(zhǎng)度復(fù)雜結(jié)構(gòu)■格式化的文檔(如,MSWord,PDF)可變長(zhǎng)度可執(zhí)行文件…文件共享和訪問控制多用戶系統(tǒng)中的文件共享是很必要的■訪問控制■每個(gè)用戶能夠獲得哪些文件的哪些訪問權(quán)限訪問模式:讀、寫、執(zhí)行、刪除、列表等文件訪問控制列表(ACL)■<文件實(shí)體,權(quán)限>Unix模式■<用戶|組|所有人,讀|寫|可執(zhí)行>用戶標(biāo)識(shí)ID識(shí)別用戶,表明每個(gè)用戶所允許的權(quán)限及保護(hù)模式組標(biāo)識(shí)ID允許用戶組成組，并指定了組訪問權(quán)限語(yǔ)義一致性規(guī)定多進(jìn)程如何同時(shí)訪問共享文件■會(huì)話語(yǔ)義■寫入內(nèi)容只有當(dāng)文件關(guān)閉時(shí)可見Unix文件系統(tǒng)(UFS)語(yǔ)義■對(duì)打開文件的寫入內(nèi)容立即對(duì)其他打開同一文件的其他用戶可見共享文件指針允許多用戶同時(shí)讀取和寫入文件讀寫鎖■一些操作系統(tǒng)和文件系統(tǒng)提供該功能與同步算法相似因磁盤I/O和網(wǎng)絡(luò)延遲而設(shè)計(jì)簡(jiǎn)單提綱文件系統(tǒng)的概念文件系統(tǒng)和文件文件描述符目錄文件別名文件系統(tǒng)種類■虛擬文件系統(tǒng)■文件緩存和打開文件■文件分配■空閑空間管理■冗余磁盤陣列RAID■分層文件系統(tǒng)文件以目錄的方式組織起來■目錄是一類特殊的文件■目錄的內(nèi)容是文件索引表<文件名,指向文件的指針>目錄和文件的樹型結(jié)構(gòu)■早期的文件系統(tǒng)是扁平的(只有一層目錄)/spell/mail/prt/firststatmaildistpemailfindcounthexreorderspellbinprogramsrootprogcopyprtexplistfindreorderhexlistobjspellalllastfirstcount/programs/p/listspellmailprtfirstprogramsplist目錄操作典型目錄操作■搜索文件創(chuàng)建文件刪除文件操作系統(tǒng)應(yīng)該只允許內(nèi)核修改目錄■確保映射的完整性遍歷路徑應(yīng)用程序通過系統(tǒng)調(diào)用訪問目錄列目錄重命名文件目錄實(shí)現(xiàn)文件名的線性列表，包涵了指向數(shù)據(jù)塊的指針■編程簡(jiǎn)單執(zhí)行耗時(shí)哈希表

–哈希數(shù)據(jù)結(jié)構(gòu)的線性表■減少目錄搜索時(shí)間沖突–兩個(gè)文件名的哈希值相同固定大小文件別名兩個(gè)或多個(gè)文件名關(guān)聯(lián)同一個(gè)文件■軟鏈接:以“快捷方式”指向其他文件■通過存儲(chǔ)真實(shí)文件的邏輯名稱來實(shí)現(xiàn)硬鏈接:多個(gè)文件項(xiàng)指向一個(gè)文件■/dict/count/spell/countlistradew7listallwlistcountcountwordsspelldictrootdictcountspellcountdictwlistallwords/dict/w/list/dict/all/spell/words/list文件目錄中的循環(huán)更多實(shí)踐■限制路徑可遍歷文件目錄的數(shù)量如何保證沒有循環(huán)？■/avi/book/avi/book/avi/book/avi/book/avi/book/avi/book/avi/book/avi/book/avi/…只允許到文件的鏈接，不允許在子目錄的鏈接增加鏈接時(shí)，用循環(huán)檢測(cè)算法確定是否合理textmailcountbookmailhyptcrootjimaviavihexbookunhexcountunhexavibookavi名字解析（路徑遍歷）名字解析:把邏輯名字轉(zhuǎn)換成物理資源（如文件）■依據(jù)路徑名，在文件系統(tǒng)中找到實(shí)際文件位置遍歷文件目錄直到找到目標(biāo)文件舉例:解析“/bin/ls”■讀取根目錄的文件頭(在磁盤固定位置）讀取根目錄的數(shù)據(jù)塊，搜索“bin”項(xiàng)讀取bin的文件頭讀取bin的數(shù)據(jù)塊;搜索“l(fā)s”頂讀取ls的文件頭當(dāng)前工作目錄(PWD)■每個(gè)進(jìn)程都會(huì)指向一個(gè)文件目錄用于解析文件名允許用戶指定相對(duì)路徑來代替絕對(duì)路徑如，用PWD=“/bin”能夠解析“l(fā)s”掛載點(diǎn)文件系統(tǒng)掛載文件系統(tǒng)需要先掛載才能被訪問■未掛載的文件系統(tǒng)被掛載在掛載點(diǎn)上■未掛載文件系統(tǒng)suejaneprogdocusers文件系統(tǒng)種類磁盤文件系統(tǒng)■文件存儲(chǔ)在數(shù)據(jù)存儲(chǔ)設(shè)備上,如磁盤例如:FAT,NTFS,ext2/3,ISO9660,等數(shù)據(jù)庫(kù)文件系統(tǒng)■文件特征是可被尋址（辨識(shí)）的例如:WinFS日志文件系統(tǒng)■記錄文件系統(tǒng)的修改/事件網(wǎng)絡(luò)/分布式文件系統(tǒng)■例如:NFS,SMB,AFS,GFS特殊/虛擬文件系統(tǒng)■網(wǎng)絡(luò)/分布式文件系統(tǒng)文件可以通過網(wǎng)絡(luò)被共享■文件位于遠(yuǎn)程服務(wù)器客戶端遠(yuǎn)程掛載服務(wù)器文件系統(tǒng)標(biāo)準(zhǔn)系統(tǒng)文件訪問被轉(zhuǎn)換成遠(yuǎn)程訪問標(biāo)準(zhǔn)文件共享協(xié)議NFSforUnix,CIFSforWindows分布式文件系統(tǒng)的挑戰(zhàn)■客戶端和客戶端上的用戶辨別起來很復(fù)雜例如,NFS是不安全的一致性問題錯(cuò)誤處理模式提綱文件系統(tǒng)的概念■虛擬文件系統(tǒng)■文件緩存和打開文件■文件分配■空閑空間管理■冗余磁盤陣列RAID■文件系統(tǒng)的實(shí)現(xiàn)分層結(jié)構(gòu)■虛擬（邏輯）文件系統(tǒng)(VFS,VirtualFileSystem)特定文件系統(tǒng)模塊ext2fatiso9660nfssmb設(shè)備I/O網(wǎng)絡(luò)I/O虛擬文件系統(tǒng)文件/文件系統(tǒng)API虛擬文件系統(tǒng)(VFS)目的■對(duì)所有不同文件系統(tǒng)的抽象功能■提供相同的文件和文件系統(tǒng)接口管理所有文件和文件系統(tǒng)關(guān)聯(lián)的數(shù)據(jù)結(jié)構(gòu)高效查詢例程,遍歷文件系統(tǒng)與特定文件系統(tǒng)模塊的交互文件系統(tǒng)基本數(shù)據(jù)結(jié)構(gòu)文件卷控制塊(Unix:“superblock”)■每個(gè)文件系統(tǒng)一個(gè)文件系統(tǒng)詳細(xì)信息塊、塊大小、空余塊、計(jì)數(shù)/指針等文件系統(tǒng)基本數(shù)據(jù)結(jié)構(gòu)文件卷控制塊(Unix:“superblock”)■文件控制塊(Unix:“vnode”or“inode”)■每個(gè)文件一個(gè)文件詳細(xì)信息訪問權(quán)限、擁有者、大小、數(shù)據(jù)塊位置等文件系統(tǒng)基本數(shù)據(jù)結(jié)構(gòu)文件卷控制塊(Unix:“superblock”)■文件控制塊(Unix:“vnode”or“inode”)■目錄項(xiàng)(Linux:“dentry”)■每個(gè)目錄項(xiàng)一個(gè)(目錄和文件)將目錄項(xiàng)數(shù)據(jù)結(jié)構(gòu)及樹型布局編碼成樹型數(shù)據(jù)結(jié)構(gòu)指向文件控制塊、父目錄、子目錄等文件系統(tǒng)的組織視圖voldirdirdirdirdirdirdirfilefilefilefiledatablockdatablockdatablockdatablockdatablockdatablockdatablockdatablockdatablock文件系統(tǒng)的存儲(chǔ)結(jié)構(gòu)文件系統(tǒng)數(shù)據(jù)結(jié)構(gòu)■卷控制塊(每個(gè)文件系統(tǒng)一個(gè)）文件控制塊(每個(gè)文件一個(gè)）目錄節(jié)點(diǎn)(每個(gè)目錄項(xiàng)一個(gè)）持久存儲(chǔ)在外存中■存儲(chǔ)設(shè)備的數(shù)據(jù)塊中當(dāng)需要時(shí)加載進(jìn)內(nèi)存■卷控制模塊:當(dāng)文件系統(tǒng)掛載時(shí)進(jìn)入內(nèi)存文件控制塊:當(dāng)文件被訪問時(shí)進(jìn)入每次目錄節(jié)點(diǎn):在遍歷一個(gè)文件路徑時(shí)進(jìn)入內(nèi)存Disk文件系統(tǒng)的存儲(chǔ)視圖voldirdirdirdirdirdirdirfilefilefilefiledatablockdatablockdatablockdatablockdatablockdatablockdatablockdatablockdatablock提綱文件系統(tǒng)的概念■虛擬文件系統(tǒng)■文件緩存和打開文件■文件分配■空閑空間管理■冗余磁盤陣列RAID■多種磁盤緩存位置內(nèi)存虛擬盤內(nèi)存打開文件表數(shù)據(jù)塊緩存CPU磁盤控制器扇區(qū)緩存磁盤數(shù)據(jù)塊緩存數(shù)據(jù)塊按需讀入內(nèi)存■提供read()操作預(yù)讀:預(yù)先讀取后面的數(shù)據(jù)塊數(shù)據(jù)塊使用后被緩存■假設(shè)數(shù)據(jù)將會(huì)再次用到寫操作可能被緩存和延遲寫入兩種數(shù)據(jù)塊緩存方式■數(shù)據(jù)塊緩存頁(yè)緩存:統(tǒng)一緩存數(shù)據(jù)塊和內(nèi)存頁(yè)虛擬頁(yè)對(duì)換文件讀寫read()andwrite()頁(yè)緩存文件系統(tǒng)數(shù)據(jù)塊緩存數(shù)據(jù)塊緩存頁(yè)緩存在虛擬內(nèi)存中文件數(shù)據(jù)塊被映射成頁(yè)文件的讀/寫操作被轉(zhuǎn)換成對(duì)內(nèi)存的訪問可能導(dǎo)致缺頁(yè)和/或設(shè)置為臟頁(yè)問題:頁(yè)置換算法需要協(xié)調(diào)虛擬存儲(chǔ)和頁(yè)緩存間的頁(yè)面數(shù)虛擬頁(yè)式存儲(chǔ)■在虛擬地址空間中虛擬頁(yè)面可映射到本地外存文件中文件數(shù)據(jù)塊的頁(yè)緩存■虛擬內(nèi)存內(nèi)核中的存儲(chǔ)管理機(jī)構(gòu)主存外存對(duì)換文件頁(yè)緩存文件虛擬頁(yè)對(duì)換文件讀寫read()andwrite()文件系統(tǒng)頁(yè)緩存頁(yè)緩存文件系統(tǒng)中打開文件的數(shù)據(jù)結(jié)構(gòu)文件描述符■每個(gè)被打開的文件都有一個(gè)文件描述符文件狀態(tài)信息目錄項(xiàng)、當(dāng)前文件指針、文件操作設(shè)置等打開文件表■每個(gè)進(jìn)程一個(gè)進(jìn)程打開文件表一個(gè)系統(tǒng)級(jí)的打開文件表有文件被打開時(shí)，文件卷就不能被卸載打開文件表voldirdirdirdirdirdirdirfilefilefilefiledatablockdatablockdatablockdatablockdatablockdatablockdatablockdatablockdatablock系統(tǒng)打開文件表進(jìn)程打開文件表打開文件鎖一些文件系統(tǒng)提供文件鎖，用于協(xié)調(diào)多進(jìn)程的文件訪問■強(qiáng)制–根據(jù)鎖保持情況和訪問需求確定是否拒絕訪問勸告–進(jìn)程可以查找鎖的狀態(tài)來決定怎么做提綱文件系統(tǒng)的概念■虛擬文件系統(tǒng)■文件緩存和打開文件■文件分配■空閑空間管理■冗余磁盤陣列RAID■文件大小大多數(shù)文件都很小■需要對(duì)小文件提供很好的支持塊空間不能太大一些文件非常大■必須支持大文件(64位文件偏移）大文件訪問需要高效文件分配如何表示分配給一個(gè)文件數(shù)據(jù)塊的位置和順序■連續(xù)分配分配方式■鏈?zhǔn)椒峙渌饕峙浯鎯?chǔ)效率：外部碎片等指標(biāo)■讀寫性能：訪問速度連續(xù)分配文件頭指定起始?jí)K和長(zhǎng)度■最先匹配,最佳匹配,...分配策略■文件讀取表現(xiàn)好優(yōu)點(diǎn)■高效的順序和隨機(jī)訪問碎片！缺點(diǎn)■文件增長(zhǎng)問題預(yù)分配？按需分配？I鏈?zhǔn)椒峙湮募詳?shù)據(jù)塊鏈表方式存儲(chǔ)■文件頭包含了到第一塊和最后一塊的指針■創(chuàng)建、增大、縮小很容易優(yōu)點(diǎn)■沒有碎片無法實(shí)現(xiàn)真正的隨機(jī)訪問缺點(diǎn)■可靠性差破壞一個(gè)鏈，后面的數(shù)據(jù)塊就丟了I索引分配為每個(gè)文件創(chuàng)建一個(gè)索引數(shù)據(jù)塊■創(chuàng)建、增大、縮小很容易優(yōu)點(diǎn)■沒有碎片支持直接訪問IIB當(dāng)文件很小時(shí)，存儲(chǔ)索引的開銷缺點(diǎn)如何處理大文件?■指向文件數(shù)據(jù)塊的指針列表文件頭包含了索引數(shù)據(jù)塊指針■大文件的索引分配鏈?zhǔn)剿饕龎K(IB+IB+…)■IIBIBIB多級(jí)索引塊(IB*IB*…)■IIBIBIBIBUFS多級(jí)索引分配10個(gè)數(shù)據(jù)塊inoden個(gè)數(shù)據(jù)塊1級(jí)間接索引塊IBIBIBIBn2個(gè)數(shù)據(jù)塊2級(jí)間接索引塊n3個(gè)數(shù)據(jù)塊3級(jí)間接索引塊IBIBIBIBIBIBIBIBUFS多級(jí)索引分配文件頭包含13個(gè)指針■10個(gè)指針指向數(shù)據(jù)塊第11個(gè)指針指向索引塊第12個(gè)指針指向二級(jí)索引塊第13個(gè)指針指向三級(jí)索引塊效果■提高了文件大小限制閥值動(dòng)態(tài)分配數(shù)據(jù)塊，文件擴(kuò)展很容易小文件開銷小只為大文件分配間接數(shù)據(jù)塊，大文件在訪問數(shù)據(jù)塊時(shí)需要大量查詢提綱文件系統(tǒng)的概念■虛擬文件系統(tǒng)■文件緩存和打開文件■文件分配■空閑空間管理■冗余磁盤陣列RAID■空閑空間管理跟蹤記錄文件卷中未分配的數(shù)據(jù)塊■采用什么數(shù)據(jù)結(jié)構(gòu)表示空閑空間列表？空閑空間組織:位圖用位圖代表空閑數(shù)據(jù)塊列表■111111111111111001110101011101111...Di=0表明數(shù)據(jù)塊i是空閑,否則，表示已分配使用簡(jiǎn)單但是可能會(huì)是一個(gè)大的很大向量表■160GB磁盤->40M數(shù)據(jù)塊->5MB位圖假定空閑空間在磁盤中均勻分布，則找到“0”之前要掃描n/rn=磁盤上數(shù)據(jù)塊的總數(shù)r=空閑塊的數(shù)目

其他空閑空間組織方式鏈表■D鏈?zhǔn)剿饕鯠G下一組索引塊已分配數(shù)據(jù)塊空閑數(shù)據(jù)塊提綱文件系統(tǒng)的概念■虛擬文件系統(tǒng)■文件緩存和打開文件■文件分配■空閑空間管理■冗余磁盤陣列RAID■磁盤分區(qū)通常磁盤通過分區(qū)來最大限度減小尋道時(shí)間■分區(qū)是一組柱面的集合每個(gè)分區(qū)都可視為邏輯上獨(dú)立的磁盤A分區(qū)B分區(qū)一個(gè)典型的磁盤文件系統(tǒng)組織文件卷：一個(gè)擁有完整文件系統(tǒng)實(shí)例的外存空間通常常駐在磁盤的單個(gè)分區(qū)上目錄目錄1號(hào)磁盤Ａ分區(qū)B分區(qū)文件文件目錄2號(hào)磁盤3號(hào)磁盤C分區(qū)文件多磁盤管理冗余磁盤陣列(RAID,RedundantArrayofInexpensiveDisks)■多種磁盤管理技術(shù)RAID分類如,RAID-0,RAID-1,RAID-5使用多磁盤可改善■吞吐量(通過并行)可靠性和可用性(通過冗余)冗余磁盤陣列的實(shí)現(xiàn)■軟件：操作系統(tǒng)內(nèi)核的文件卷管理硬件：RAID硬件控制器(I/O)RAID-0：磁盤條帶化把數(shù)據(jù)塊分成多個(gè)子塊，存儲(chǔ)在獨(dú)立的磁盤中■

891011121314150123OS數(shù)據(jù)塊物理磁盤數(shù)據(jù)塊891011121213141530123通過獨(dú)立磁盤上并行數(shù)據(jù)塊訪問提供更大的磁盤帶寬RAID-1:磁盤鏡像x011