操作系統(tǒng)文件系統(tǒng)

1、12022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽主講教師：楊武杰楊武杰聯(lián)系電話電子郵件： 操作系統(tǒng)操作系統(tǒng)22022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽第六章第六章 文件管理文件管理6.1 文件和文件系統(tǒng)6.2 文件的邏輯結(jié)構(gòu)6.3 外存分配方式6.4 文件存儲(chǔ)空間管理6.5 目錄管理6.6 文件共享與保護(hù)6.7 數(shù)據(jù)一致性控制32022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.1 文件和文件系統(tǒng)6.1.1 文件管理目標(biāo)及功能6.1.2 文件、記錄和數(shù)據(jù)項(xiàng)6.1.3 文件類型6.1.4 文件系統(tǒng)模型6.1.5 文件操作42022年6月6日星期

2、一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽文件管理目標(biāo)及功能q文件管理目標(biāo)方便用戶方便用戶、保證安全存取快速、資源利用q文件管理功能管理在外存上的文件提供文件存取、共享和保護(hù)手段q文件系統(tǒng)技術(shù)手段分析目錄、索引結(jié)點(diǎn)、“結(jié)構(gòu)” 優(yōu)化存取控制矩陣、容錯(cuò)技術(shù)52022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.1 文件和文件系統(tǒng)6.1.1 文件管理目標(biāo)及功能6.1.2 文件、記錄和數(shù)據(jù)項(xiàng)6.1.3 文件類型6.1.4 文件系統(tǒng)模型6.1.5 文件操作62022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽文件、記錄和數(shù)據(jù)項(xiàng)文件記錄1記錄2記錄n數(shù)據(jù)項(xiàng)1數(shù)據(jù)項(xiàng)2數(shù)據(jù)項(xiàng)m 基本數(shù)據(jù)項(xiàng) 組合數(shù)據(jù)項(xiàng)關(guān)鍵字文件名

3、及其它屬性72022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.1 文件和文件系統(tǒng)6.1.1 文件管理目標(biāo)及功能6.1.2 文件、記錄和數(shù)據(jù)項(xiàng)6.1.3 文件類型6.1.4 文件系統(tǒng)模型6.1.5 文件操作82022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽文件類型v為方便文件存取及管理控制而引入q按文件性質(zhì)與用途分類系統(tǒng)文件、用戶文件、庫文件q按文件中的數(shù)據(jù)形式分類源文件、目標(biāo)文件、可執(zhí)行文件q按存取控制屬性分類只執(zhí)行文件、只讀文件、讀寫文件q按文件邏輯/物理結(jié)構(gòu)分類常對(duì)應(yīng)擴(kuò)展名92022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.1 文件和文件系統(tǒng)6.1.1 文件管理目標(biāo)及

4、功能6.1.2 文件、記錄和數(shù)據(jù)項(xiàng)6.1.3 文件類型6.1.4 文件系統(tǒng)模型6.1.5 文件操作102022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽文件系統(tǒng)模型文件管理軟件集合基本文件系統(tǒng)層(物理I/O層)I/O控制層(設(shè)備驅(qū)動(dòng)程序?qū)?基本I/O管理程序?qū)?文件組織模塊層)邏輯文件系統(tǒng)層文件系統(tǒng)接口（命令/圖形化用戶接口、程序接口）硬件對(duì)象（磁盤等輔助存儲(chǔ)器）112022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.1 文件和文件系統(tǒng)6.1.1 文件管理目標(biāo)及功能6.1.2 文件、記錄和數(shù)據(jù)項(xiàng)6.1.3 文件類型6.1.4 文件系統(tǒng)模型6.1.5 文件操作122022年6月6日星期

5、一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽文件操作q創(chuàng)建/刪除文件q讀/寫文件q截?cái)辔募設(shè)置文件讀/寫位置文件描述符、文件讀寫指針文件描述符、文件讀寫指針文件指針文件指針q打開/關(guān)閉文件內(nèi)存打開文件表、用戶文件描述符表內(nèi)存打開文件表、用戶文件描述符表q文件屬性設(shè)置與獲取q目錄操作、文件共享及其它操作132022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽UNIX文件描述符表與文件表文件描述符表與文件表A進(jìn)程U區(qū)fp1 fp2 fp3 fp4 fp5文件表f_offsetf_inodef_flagf_countf_offsetf_inodef_flagf_count內(nèi)存索引結(jié)點(diǎn)i#內(nèi)存索引結(jié)點(diǎn)j#內(nèi)存

6、索引結(jié)點(diǎn)k#內(nèi)存索引結(jié)點(diǎn)B進(jìn)程U區(qū)fp1 fp2 fp3 fp4 fp5142022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.1 文件和文件系統(tǒng)6.1.1 文件管理目標(biāo)及功能6.1.2 文件、記錄和數(shù)據(jù)項(xiàng)6.1.3 文件類型6.1.4 文件系統(tǒng)模型6.1.5 文件操作152022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽作業(yè)題作業(yè)題q6.1 闡述文件管理的目標(biāo)、功能及技術(shù)手段，并就文件系統(tǒng)層次結(jié)構(gòu)模型進(jìn)行討論。q6.2 分別就數(shù)據(jù)項(xiàng)、記錄、關(guān)鍵字和文件的概念進(jìn)行解釋，并就文件的分類展開討論。q6.3 通常，文件系統(tǒng)應(yīng)提供哪些基本文件操作類型？并就其功能實(shí)現(xiàn)分別進(jìn)行簡(jiǎn)要說明。1620

7、22年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽第六章第六章 文件管理文件管理6.1 文件和文件系統(tǒng)6.2 文件的邏輯結(jié)構(gòu)6.3 外存分配方式6.4 文件存儲(chǔ)空間管理6.5 目錄管理6.6 文件共享與保護(hù)6.7 數(shù)據(jù)一致性控制172022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.2 文件的邏輯結(jié)構(gòu)6.2.1 文件邏輯結(jié)構(gòu)及設(shè)計(jì)要求6.2.2 文件邏輯結(jié)構(gòu)類型6.2.3 順序文件6.2.4 索引文件6.2.5 索引順序文件182022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽文件邏輯結(jié)構(gòu)及設(shè)計(jì)要求q提高檢索效率文件記錄或數(shù)據(jù)檢索速度及效率q方便修改文件記錄或數(shù)據(jù)的增、刪、修改q降低

8、文件存儲(chǔ)成本減少文件占用存儲(chǔ)空間摒棄存儲(chǔ)空間連續(xù)性要求？192022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.2 文件的邏輯結(jié)構(gòu)6.2.1 文件邏輯結(jié)構(gòu)及設(shè)計(jì)要求6.2.2 文件邏輯結(jié)構(gòu)類型6.2.3 順序文件6.2.4 索引文件6.2.5 索引順序文件202022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽文件邏輯結(jié)構(gòu)的類型q有結(jié)構(gòu)文件（記錄式文件）v定長(zhǎng)記錄和不定長(zhǎng)記錄順序文件索引文件索引順序文件q無結(jié)構(gòu)文件基于讀寫指針和字符進(jìn)行存取212022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.2 文件的邏輯結(jié)構(gòu)6.2.1 文件邏輯結(jié)構(gòu)及設(shè)計(jì)要求6.2.2 文件邏輯結(jié)構(gòu)類型6.2

9、.3 順序文件6.2.4 索引文件6.2.5 索引順序文件222022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽順序文件q邏輯記錄的排序串結(jié)構(gòu)與順序結(jié)構(gòu)q順序文件讀寫操作v讀寫指針RWptr對(duì)應(yīng)記錄邏輯地址定長(zhǎng)記錄 RWptr += recordLength變長(zhǎng)記錄 RWptr += currentRecordLengthq順序文件評(píng)析適于批量存取及磁帶介質(zhì)交互應(yīng)用場(chǎng)合單個(gè)記錄操作低效與關(guān)鍵字次序與關(guān)鍵字次序一致與否一致與否解決方案？解決方案？232022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽順序文件直接存取分析R0R1R2R3Ril0lll2ll3l4lli*l(i+1)*lRW

10、ptr定長(zhǎng)記錄順序文件l0R0l1R1li0l0l0+1RWptr變長(zhǎng)記錄順序文件Rilil1l0+ l1+ 2i-1(lk+ 1)i (lk+ 1)242022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.2 文件的邏輯結(jié)構(gòu)6.2.1 文件邏輯結(jié)構(gòu)及設(shè)計(jì)要求6.2.2 文件邏輯結(jié)構(gòu)類型6.2.3 順序文件6.2.4 索引文件6.2.5 索引順序文件252022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽索引文件組織及檢索機(jī)制R0R1R2R3Ri主數(shù)據(jù)文件關(guān)鍵字key0key1key2keyi記錄長(zhǎng)度ll0l1l2li指針ptr索引表（定長(zhǎng)記錄順序文件）262022年6月6日星期一北京交

11、通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.2 文件的邏輯結(jié)構(gòu)6.2.1 文件邏輯結(jié)構(gòu)及設(shè)計(jì)要求6.2.2 文件邏輯結(jié)構(gòu)類型6.2.3 順序文件6.2.4 索引文件6.2.5 索引順序文件272022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽索引順序文件組織及檢索機(jī)制主數(shù)據(jù)文件索引表（定長(zhǎng)記錄順序文件）姓名An KangAn QiBaoLuoBaoRong關(guān)鍵字An KangBaoLuoChenLin其它屬性指針ptr282022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽索引順序文件檢索效率分析q對(duì)于擁有N條記錄的主數(shù)據(jù)文件，若基于順序查找法來檢索具有指定關(guān)鍵字的記錄，不同文件組織方式下的系統(tǒng)檢索開銷

12、比較順序文件組織方式 (N+1)/2條索引文件組織方式 (N+1)/2條索引順序文件組織方式 sqrt(N)+1條v 分組大小分組大小 sqrt(N)條記錄條記錄q舉例說明(N=10000)292022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽基于多級(jí)索引的索引順序文件q建立多級(jí)索引以進(jìn)一步提高檢索效率q舉例說明(N=106)索引順序文件組織方式 v 檢索開銷 1001條v 分組大小 1000 條記錄兩級(jí)索引順序文件組織方式v 主文件分組大小 100 條記錄CubicRoot(N)v 低級(jí)索引表分組大小 100 條記錄CubicRoot(N)v 檢索開銷 151.5條1.5*CubicRo

13、ot(N)+1.5302022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.2 文件的邏輯結(jié)構(gòu)6.2.1 文件邏輯結(jié)構(gòu)及設(shè)計(jì)要求6.2.2 文件邏輯結(jié)構(gòu)類型6.2.3 順序文件6.2.4 索引文件6.2.5 索引順序文件312022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽作業(yè)題作業(yè)題q6.4 什么是文件的邏輯結(jié)構(gòu)？其基本設(shè)計(jì)要求是什么？并就主要的文件邏輯結(jié)構(gòu)類型特別是順序文件、索引文件、索引順序文件等展開簡(jiǎn)明扼要的說明和討論。322022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽第六章第六章 文件管理文件管理6.1 文件和文件系統(tǒng)6.2 文件的邏輯結(jié)構(gòu)6.3 外存分配方式6.4

14、文件存儲(chǔ)空間管理6.5 目錄管理6.6 文件共享與保護(hù)6.7 數(shù)據(jù)一致性控制332022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.3 外存分配方式6.3.1 文件物理結(jié)構(gòu)與外存分配6.3.2 連續(xù)分配6.3.3 鏈接分配6.3.4 索引分配6.3.5 直接文件和散列文件342022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽文件物理結(jié)構(gòu)與外存分配q文件物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）文件在外存上的存儲(chǔ)組織形式q外存空間分配方法設(shè)計(jì)目標(biāo)空間利用及文件訪問速度q外存分配方式與文件物理結(jié)構(gòu)連續(xù)分配順序文件結(jié)構(gòu)鏈接分配鏈接式文件結(jié)構(gòu)索引分配索引式文件結(jié)構(gòu)直接文件與散列文件352022年6月6日星期一北京

15、交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.3 外存分配方式6.3.1 文件物理結(jié)構(gòu)與外存分配6.3.2 連續(xù)分配6.3.3 鏈接分配6.3.4 索引分配6.3.5 直接文件和散列文件362022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽連續(xù)分配示意圖file start lengthcount 0 2 tr 14 3 mail 19 6 list 28 4 f 6 2文件目錄048121620242815913172125292610141822263037111519232731counttrmaillistf372022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽連續(xù)分配評(píng)析q外部碎片問題磁盤空

16、間分割后形成的較小的無法存儲(chǔ)文件的連續(xù)區(qū)緊湊方法緊湊方法q主要優(yōu)點(diǎn)順序訪問容易且速度快支持直接存取q主要缺點(diǎn)要求有連續(xù)的存儲(chǔ)空間，空間利用率低必須事先知道文件的長(zhǎng)度382022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.3 外存分配方式6.3.1 文件物理結(jié)構(gòu)與外存分配6.3.2 連續(xù)分配6.3.3 鏈接分配6.3.4 索引分配6.3.5 直接文件和散列文件392022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽鏈接分配q基本思想支持離散分配方式，通過盤塊上的指針實(shí)現(xiàn)同一文件多個(gè)離散盤塊的鏈接q優(yōu)點(diǎn)評(píng)析消除了外部碎片，外存空間利用率高按需分配，且無需事先知道文件長(zhǎng)度支持文件動(dòng)態(tài)增長(zhǎng)，方

17、便文件增刪改q鏈接方式隱式鏈接/顯式鏈接402022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽隱式鏈接示意圖file start endjeep 9 25文件目錄1625-1101048121620242815913172125292610141822263037111519232731412022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽隱式鏈接問題及對(duì)策q主要問題只適合順序訪問，對(duì)隨機(jī)存取極其低效僅通過鏈接指針實(shí)現(xiàn)離散各盤塊的鏈接，只要其中任何一個(gè)指針出現(xiàn)問題，都會(huì)導(dǎo)致整條鏈的斷開，所以可靠性較差q為了提高檢索速度和減少指針?biāo)加玫拇鎯?chǔ)空間，可將幾個(gè)盤塊組成一個(gè)簇，以簇為單位進(jìn)行盤

18、塊分配缺點(diǎn)：內(nèi)部碎片增大422022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽顯式鏈接與文件分配表FAT6EOF11105EOF4901234567891011FCB AFCB B盤塊號(hào)文件分配表FAT物理地址物理地址432022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽文件分配表空間開銷計(jì)算q設(shè)定盤塊大小為1KB對(duì)于1.2MB的軟盤，共有盤塊1.2MB/1KB = 1.2K （28, 212） 故文件分配表表項(xiàng)取12位即1.5B 所以FAT共需空間1.2K1.5B = 1.8KB對(duì)于200MB的硬盤，共有盤塊200MB/1KB = 200K （216, 220） 故文件分配表表項(xiàng)取2

19、0位即2.5B 所以FAT共需空間200K2.5B = 500KB442022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.3 外存分配方式6.3.1 文件物理結(jié)構(gòu)與外存分配6.3.2 連續(xù)分配6.3.3 鏈接分配6.3.4 索引分配6.3.5 直接文件和散列文件452022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽索引分配的引入及基本思想q鏈接分配方式的缺陷不能支持高效地直接存取v若對(duì)一個(gè)較大的文件進(jìn)行直接存取，須首先在FAT中順序地查找許多盤塊號(hào)FAT占用內(nèi)存空間較大及文件所占盤塊號(hào)隨機(jī)q基本思想文件打開僅須把該文件所占用盤塊編號(hào)調(diào)入內(nèi)存即可，故可將每個(gè)文件所對(duì)應(yīng)的盤塊號(hào)集中地存放

20、一個(gè)所謂的索引塊中，形成一個(gè)索引表索引塊文件文件目錄項(xiàng)索引塊指針對(duì)于小文件，索引塊利用率極低462022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽索引分配示意圖file 序號(hào)jeep 19文件目錄04812162024281591317212529261014182226303711151923273191610251-1-119索引塊472022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽兩/多級(jí)索引分配q基本思想對(duì)于太大的文件和索引塊太多時(shí)，直接用鏈接指針來鏈接索引塊的方法顯然是低效的，為此應(yīng)引入多級(jí)索引分配方式q允許文件最大長(zhǎng)度兩級(jí)索引、盤塊大小1KB、盤塊號(hào)占4B則一個(gè)索引塊可含

21、 1KB/4B=256個(gè)盤塊號(hào)，于是兩級(jí)索引最多可含256256 = 64K個(gè)盤塊號(hào)，允許文件最大長(zhǎng)度為64MB482022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽混合分配方式示意圖modeowners(2)time stamp(3)sizeblock counti.addr(0)i.addr(1)i.addr(9)i.addr(10)i.addr(11)i.addr(12)DataDataDataDataDataDataDataDataDataDataDataDataDataDataDataDataData492022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽混合分配方式(UNIX

22、系統(tǒng))q直接尋址v直接地址項(xiàng)存放對(duì)應(yīng)文件數(shù)據(jù)的盤塊的盤塊號(hào)盤塊大小4KB、盤塊號(hào)占4B，則支持長(zhǎng)度在4KB10 = 40KB以內(nèi)的文件q一次間接尋址vi.addr(10)指向?qū)?yīng)文件的一級(jí)索引塊一級(jí)索引塊可含4KB/4B = 1K個(gè)盤塊號(hào)，故支持長(zhǎng)度在(4KB1K=4MB)+40KB 以內(nèi)的文件q多次間接尋址vi.addr(11)、 i.addr(12)分別指向?qū)?yīng)文件的兩級(jí)索引塊和三級(jí)索引塊，所以支持文件長(zhǎng)度可達(dá)(4KB1K1K 1K=4TB)+(4KB1K1K=4GB)+4MB+40KB502022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽UNIX文件操作地址轉(zhuǎn)換過程I.將字節(jié)偏移量轉(zhuǎn)

23、換為文件邏輯盤塊號(hào)LogicBlk# = Offset / SizeOfBlkII.將邏輯盤塊號(hào)轉(zhuǎn)換為物理盤塊號(hào)A.確定物理盤塊號(hào)所在地址項(xiàng)或索引盤塊B.確定物理盤塊號(hào)所在索引盤塊及位置q舉例說明Offset 9000B = LogicBlk# 8 = i.addr(8)Offset 14000B = LogicBlk# 13 = 對(duì)應(yīng)i.addr(10)的索引盤塊中的第3個(gè)盤塊號(hào)512022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.3 外存分配方式6.3.1 文件物理結(jié)構(gòu)與外存分配6.3.2 連續(xù)分配6.3.3 鏈接分配6.3.4 索引分配6.3.5 直接文件和散列文件522022年

24、6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽直接文件和散列文件q直接文件記錄鍵值 = 物理地址q散列文件（Hash文件）散列函數(shù)及目錄表201#目錄表鍵值KH(K)散列函數(shù)物理塊號(hào)0123456201#346#塊因子塊因子？532022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.3 外存分配方式6.3.1 文件物理結(jié)構(gòu)與外存分配6.3.2 連續(xù)分配6.3.3 鏈接分配6.3.4 索引分配6.3.5 直接文件和散列文件542022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽作業(yè)題作業(yè)題q6.5 什么是文件的物理結(jié)構(gòu)？其基本設(shè)計(jì)要求是什么？并就主要的文件物理結(jié)構(gòu)類型及外存分配方式展開簡(jiǎn)明扼

25、要的說明和討論。552022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽第六章第六章 文件管理文件管理6.1 文件和文件系統(tǒng)6.2 文件的邏輯結(jié)構(gòu)6.3 外存分配方式6.4 文件存儲(chǔ)空間管理6.5 目錄管理6.6 文件共享與保護(hù)6.7 數(shù)據(jù)一致性控制562022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.4 文件存儲(chǔ)空間管理6.4.1 管理目標(biāo)與技術(shù)要領(lǐng)6.4.2 空閑表法6.4.3 空閑鏈表法6.4.4 位示圖法6.4.5 成組鏈接法572022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽管理目標(biāo)與技術(shù)要領(lǐng)q文件存儲(chǔ)空間管理目標(biāo)外存空間利用與文件訪問速度q文件存儲(chǔ)空間管理技術(shù)要領(lǐng)連

26、續(xù)分配與離散分配優(yōu)劣各異文件物理結(jié)構(gòu)與存儲(chǔ)組織方式分配以掌握空間使用情況為前提A.存儲(chǔ)空間使用情況數(shù)據(jù)結(jié)構(gòu)B.存儲(chǔ)空間的分配與回收C.基本分配單位為磁盤塊582022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.4 文件存儲(chǔ)空間管理6.4.1 管理目標(biāo)與技術(shù)要領(lǐng)6.4.2 空閑表法6.4.3 空閑鏈表法6.4.4 位示圖法6.4.5 成組鏈接法592022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽空閑表法q屬于連續(xù)分配方式q空閑盤區(qū)的分配首次適應(yīng)算法循環(huán)首次適應(yīng)算法最佳適應(yīng)算法最壞適應(yīng)算法q空閑盤區(qū)的回收考慮回收區(qū)域插入點(diǎn)前后盤塊區(qū)是否相鄰接，相鄰則予合并序號(hào)第一空閑盤塊號(hào)空閑盤塊數(shù)0

27、3318521623空閑盤塊（區(qū)）表適用場(chǎng)合適用場(chǎng)合？602022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.4 文件存儲(chǔ)空間管理6.4.1 管理目標(biāo)與技術(shù)要領(lǐng)6.4.2 空閑表法6.4.3 空閑鏈表法6.4.4 位示圖法6.4.5 成組鏈接法612022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽空閑鏈表法q將所有空閑盤塊區(qū)拉成一條空閑鏈空閑盤塊鏈v 以盤塊為基本元素鏈接v 分配與回收空閑盤區(qū)鏈v 以盤區(qū)為基本元素鏈接，且每個(gè)盤區(qū)除含有指示下一個(gè)盤塊區(qū)的指針外，還應(yīng)標(biāo)有指明本盤區(qū)大小的信息v 分配與回收v 為提高對(duì)空閑盤區(qū)的檢索速度，可采用顯式鏈接方式622022年6月6日星期一北京

28、交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.4 文件存儲(chǔ)空間管理6.4.1 管理目標(biāo)與技術(shù)要領(lǐng)6.4.2 空閑表法6.4.3 空閑鏈表法6.4.4 位示圖法6.4.5 成組鏈接法632022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽位示圖q利用位示圖（即二維數(shù)組Mapm, n）的一位（0/1）來表示磁盤中一個(gè)盤塊的使用情況，磁盤上所有盤塊都與一個(gè)二進(jìn)制位相對(duì)應(yīng)1 1 0 0 0 1 0 0 1 0 1 0 0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 0 1 1 1 11 1 0 1 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1

29、 01 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1612316642022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽盤塊的分配Var Map: array 1.m, 1.n of bit;q順序掃描位示圖，找出一個(gè)或一組其值均為空閑的二進(jìn)制位q將所找到的一個(gè)或一組二進(jìn)制位Mapi, j的行/列號(hào)轉(zhuǎn)換為與之對(duì)應(yīng)的盤塊號(hào)b：b = n(i-1) + j-1q按盤塊號(hào)分配盤塊，同時(shí)修改位示圖652022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽盤塊的回收I.將回收盤塊的盤塊號(hào)b轉(zhuǎn)換為位示圖中的行號(hào)i和列號(hào)j：A.i = b DIV n + 1;B.j = b MO

30、D n + 1;II.按盤塊號(hào)回收盤塊III.根據(jù)回收盤塊對(duì)應(yīng)二進(jìn)制位的行/列號(hào)修改位示圖662022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.4 文件存儲(chǔ)空間管理6.4.1 管理目標(biāo)與技術(shù)要領(lǐng)6.4.2 空閑表法6.4.3 空閑鏈表法6.4.4 位示圖法6.4.5 成組鏈接法672022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽成組鏈接法100300299202201019899空閑盤塊號(hào)棧S.free100400399301100500499401100079997901201#299#300#399#400#7900#7899#7999#301#7801#7901#68202

31、2年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽空閑盤塊的分配I.檢查空閑盤塊號(hào)棧是否上鎖：a)如未上鎖，則從棧頂取出一空閑盤塊號(hào)，1)若其不是棧底S.free(0)即空閑盤塊號(hào)數(shù)N1，則將其對(duì)應(yīng)盤塊分配給用戶，然后將棧頂指針下移一格，亦即做N的減1操作2)若其是棧底S.free(0)即N=1且其值為0，則分配失敗返回；否則調(diào)用磁盤讀過程，將棧底盤塊號(hào)所對(duì)應(yīng)盤塊的內(nèi)容讀入棧中作為新的空閑盤塊號(hào)棧的內(nèi)容，同時(shí)將該盤塊號(hào)對(duì)應(yīng)的盤塊分配給用戶b)如上鎖，則等待II.分配盤塊緩沖，然后返回692022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽空閑盤塊的回收I.檢查空閑盤塊號(hào)棧，若未上鎖：a)若棧中

32、空閑盤塊號(hào)數(shù)N100即棧未滿，則執(zhí)行空閑盤塊號(hào)數(shù)N的加1操作，并將回收盤塊的盤塊號(hào)記入空閑盤塊號(hào)棧的棧頂b)否則，若棧中空閑盤塊號(hào)數(shù)N已達(dá)100即棧已滿，應(yīng)將空閑盤塊號(hào)棧的當(dāng)前內(nèi)容包括盤塊數(shù)及所有盤塊號(hào)記入新回收的盤塊中，同時(shí)將新回收盤塊的盤塊號(hào)作為S.free(0)即棧底，并置空閑盤塊號(hào)棧的空閑盤塊數(shù)N為1c)返回II.否則已上鎖，等待702022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽UNIX文件卷組織結(jié)構(gòu)q系統(tǒng)引導(dǎo)塊 0#用于系統(tǒng)引導(dǎo)或空閑q超級(jí)塊 1#文件系統(tǒng)結(jié)構(gòu)信息(盤塊及磁盤索引結(jié)點(diǎn))q磁盤索引結(jié)點(diǎn)塊 2# K#存放磁盤索引結(jié)點(diǎn)q文件數(shù)據(jù)塊 (K+1)# N#存放文件數(shù)據(jù)71

33、2022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.4 文件存儲(chǔ)空間管理6.4.1 管理目標(biāo)與技術(shù)要領(lǐng)6.4.2 空閑表法6.4.3 空閑鏈表法6.4.4 位示圖法6.4.5 成組鏈接法722022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽作業(yè)題作業(yè)題q6.6 文件存儲(chǔ)空間管理的基本目標(biāo)是什么？關(guān)于空閑存儲(chǔ)空間的管理通?？苫谀男?shù)據(jù)結(jié)構(gòu)及方法進(jìn)行描述和管理？并逐一進(jìn)行簡(jiǎn)要說明。732022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽第六章第六章 文件管理文件管理6.1 文件和文件系統(tǒng)6.2 文件的邏輯結(jié)構(gòu)6.3 外存分配方式6.4 文件存儲(chǔ)空間管理6.5 目錄管理6.6 文件共享

34、與保護(hù)6.7 數(shù)據(jù)一致性控制742022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.5 目錄管理6.5.1 目錄管理基本要求6.5.2 文件控制塊6.5.3 索引結(jié)點(diǎn)6.5.4 目錄結(jié)構(gòu)6.5.5 目錄查詢技術(shù)752022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽目錄管理功能及要求q目錄引入理由文件的有效管理與組織要求基于文件名便能快速、準(zhǔn)確地找到指定文件q文件目錄管理的功能及要求實(shí)現(xiàn)“按名存取”（文件名外存地址）提高目錄檢索速度及文件存取速度文件共享（外存保留一份文件副本）允許文件重名，以便于文件使用762022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.5 目錄管理6.5.

35、1 目錄管理基本要求6.5.2 文件控制塊6.5.3 索引結(jié)點(diǎn)6.5.4 目錄結(jié)構(gòu)6.5.5 目錄查詢技術(shù)772022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽文件控制塊q基本概念文件文件控制塊文件目錄項(xiàng)文件目錄文件控制塊有序集合目錄文件q主要信息內(nèi)容基本信息（文件名、物理位置、結(jié)構(gòu)類型）存取控制信息（各類用戶存取權(quán)限）使用信息（建立/上次修改日期及時(shí)間）v 當(dāng)前使用信息（當(dāng)前已打開該文件的進(jìn)程數(shù)、是否被其它進(jìn)程鎖住、文件在內(nèi)存是否已修改但尚未拷貝到盤上）782022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽MS-DOS文件控制塊內(nèi)容一覽q文件控制塊長(zhǎng)度為32字節(jié)文件名及文件擴(kuò)展名共1

36、1個(gè)字符q對(duì)于360KB的軟盤，總共含有112個(gè)FCB，故占有4KB的存儲(chǔ)空間文件名文 件擴(kuò)展名文件屬性備 用文件建立時(shí) 間文件建立日 期文件所在第一盤塊號(hào)文件長(zhǎng)度(盤塊數(shù))792022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.5 目錄管理6.5.1 目錄管理基本要求6.5.2 文件控制塊6.5.3 索引結(jié)點(diǎn)6.5.4 目錄結(jié)構(gòu)6.5.5 目錄查詢技術(shù)802022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽索引結(jié)點(diǎn)的引入q必要性文件目錄存放在磁盤上，且可能要占用大量盤塊N ，檢索開銷很大（盤塊調(diào)入次數(shù) N+1 /2 ）q可行性只有文件名對(duì)目錄檢索有用文件名索引結(jié)點(diǎn)編號(hào)文件名1文件名2

37、文件名3文件描述控制信息索引結(jié)點(diǎn)（i結(jié)點(diǎn)）集合UNIX文件目錄812022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽索引結(jié)點(diǎn)檢索開銷分析q舉例說明盤塊大小1KB，文件目錄共3200個(gè)FCBq引入索引結(jié)點(diǎn)前FCB占64B，每盤塊包含16個(gè)FCB，文件目錄共需占用200個(gè)盤塊，故查找一個(gè)文件平均需啟動(dòng)磁盤100.5次q引入索引結(jié)點(diǎn)后目錄項(xiàng)僅占16B（文件名和索引結(jié)點(diǎn)指針分別占用14B和2B），每盤塊包含64個(gè)目錄項(xiàng)，文件目錄共需占用50個(gè)盤塊，故查找一個(gè)文件平均需啟動(dòng)磁盤25.5+1次822022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽磁盤索引結(jié)點(diǎn)與內(nèi)存索引結(jié)點(diǎn)q磁盤索引結(jié)點(diǎn)文件磁盤索引

38、結(jié)點(diǎn)主要內(nèi)容（文件主標(biāo)識(shí)、文件類型、文件存取權(quán)限、文件長(zhǎng)度、文件存取時(shí)間、文件物理地址、文件連接計(jì)數(shù)）q內(nèi)存索引結(jié)點(diǎn)文件打開時(shí)對(duì)磁盤索引結(jié)點(diǎn)在內(nèi)存的拷貝專有內(nèi)容（索引結(jié)點(diǎn)編號(hào)、索引結(jié)點(diǎn)狀態(tài)、索引結(jié)點(diǎn)訪問計(jì)數(shù)、文件所述文件系統(tǒng)邏輯設(shè)備號(hào)、空閑鏈表/散列隊(duì)列指針）832022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.5 目錄管理6.5.1 目錄管理基本要求6.5.2 文件控制塊6.5.3 索引結(jié)點(diǎn)6.5.4 目錄結(jié)構(gòu)6.5.5 目錄查詢技術(shù)842022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽單級(jí)目錄結(jié)構(gòu)q文件創(chuàng)建目錄檢索申請(qǐng)空目錄項(xiàng)屬性設(shè)置q文件刪除目錄檢索外存空間回收目錄項(xiàng)回收q缺

39、點(diǎn)查找速度慢、不允許重名、不便于文件共享文件名狀態(tài)位狀態(tài)位 物理地址文件其它屬性Alpha.wpsReport.pptText.dat852022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽兩級(jí)目錄結(jié)構(gòu)示意圖用戶名指向用戶子目錄的指針ZhaiGaoShouAlphaTestZhai用戶目錄ReportTestGao用戶目錄BetaDeviceMisxShou用戶目錄AlphaTestBetaDeviceMisxReportTest主文件目錄MFD862022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽兩級(jí)目錄結(jié)構(gòu)評(píng)析q優(yōu)點(diǎn)提高了目錄檢索速度v MFD含n個(gè)UFD，UFD最多有m個(gè)目錄項(xiàng)，則

40、為找到指定文件最多需檢索n+m個(gè)目錄項(xiàng)；對(duì)于單級(jí)目錄結(jié)構(gòu)，最多需檢索nm個(gè)目錄項(xiàng)不同用戶目錄可使用相同的文件名不同用戶可用不同名稱訪問同一共享文件q缺點(diǎn)用戶隔離不便于文件共享和用戶間協(xié)作872022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽樹型目錄結(jié)構(gòu)示意圖ABC16DEF2FED34GH5ICJNK12LMN13OHP147891011151618192122201723882022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽樹型目錄結(jié)構(gòu)實(shí)現(xiàn)機(jī)制及評(píng)析q路徑名（絕對(duì)路徑名）從根目錄到各數(shù)據(jù)文件之間只有唯一的通路，該路徑上的全部目錄文件名與數(shù)據(jù)文件名用“/”連接形成特定數(shù)據(jù)文件的路徑名q

41、相對(duì)路徑名當(dāng)前目錄當(dāng)前目錄（工作目錄）從當(dāng)前目錄開始逐級(jí)通過中間目錄文件最后到達(dá)所訪問數(shù)據(jù)文件的路徑名稱為相對(duì)路徑名q目錄增刪目錄檢索作為第一步目錄刪除處理方法（是否允許刪除非空目錄）q滿足目錄管理的所有要求892022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.5 目錄管理6.5.1 目錄管理基本要求6.5.2 文件控制塊6.5.3 索引結(jié)點(diǎn)6.5.4 目錄結(jié)構(gòu)6.5.5 目錄查詢技術(shù)902022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽文件存取及目錄查詢技術(shù)q實(shí)現(xiàn)文件按名存取的基本步驟1. 系統(tǒng)根據(jù)用戶提供的文件名，對(duì)文件目錄進(jìn)行查詢，找出該文件的文件控制塊或索引結(jié)點(diǎn)2. 按照對(duì)

42、應(yīng)文件控制塊或索引結(jié)點(diǎn)中所記錄的文件物理地址（盤塊號(hào)），計(jì)算出文件在磁盤上的物理地址3. 啟動(dòng)磁盤驅(qū)動(dòng)程序，將所存取的文件讀入內(nèi)存進(jìn)行具體讀寫操作q目錄查詢技術(shù)線性檢索法（順序檢索法）和散列方法沖突處理沖突處理？912022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽目錄查詢舉例說明:/usr/ast/mbox1.1.4bin7dev14lib9etc6usr8tmp根目錄6.1.19dick30erik51jim26ast45bal132#盤塊/usr子目錄i.addr(0)132i.addr(0) 496索引結(jié)點(diǎn)集結(jié)點(diǎn)6結(jié)點(diǎn)2626.6.64grants92books60mbox81mi

43、nix17src496#盤塊/usr/ast子目錄(1)(2)(3)(4)(5)(6)922022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.5 目錄管理6.5.1 目錄管理基本要求6.5.2 文件控制塊6.5.3 索引結(jié)點(diǎn)6.5.4 目錄結(jié)構(gòu)6.5.5 目錄查詢技術(shù)932022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽作業(yè)題作業(yè)題q6.7 文件目錄管理的基本要求有哪些？從索引結(jié)點(diǎn)和目錄結(jié)構(gòu)等兩方面闡述目錄管理技術(shù)的演化發(fā)展，并就樹形目錄結(jié)構(gòu)中文件的按名存取和目錄檢索技術(shù)展開詳細(xì)說明。942022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽第六章第六章 文件管理文件管理6.1 文件

44、和文件系統(tǒng)6.2 文件的邏輯結(jié)構(gòu)6.3 外存分配方式6.4 文件存儲(chǔ)空間管理6.5 目錄管理6.6 文件共享與保護(hù)6.7 數(shù)據(jù)一致性控制952022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.6 文件共享與保護(hù)6.6.1 文件共享概念與發(fā)展6.6.2 基于索引結(jié)點(diǎn)的共享方式6.6.3 利用符號(hào)鏈實(shí)現(xiàn)文件共享6.6.4 文件系統(tǒng)安全保護(hù)6.6.5 磁盤容錯(cuò)技術(shù)962022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽文件共享概念及必要性q概念指系統(tǒng)應(yīng)允許多個(gè)用戶（進(jìn)程）共享同一份文件，從而在系統(tǒng)中只需保存該共享文件的一個(gè)副本即可q必要性如果系統(tǒng)不能提供文件共享功能，就意味著凡是需要該文件的

45、用戶，都須各自備有此文件的副本，因此必然會(huì)造成存儲(chǔ)空間的極大浪費(fèi)972022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽繞彎路法ABC16ABD2FED34GA5ACJNK12JMK13AHF14789101115161718202119 3F17J: * E J 3F9A: * * C Aq (相對(duì)/絕對(duì))路徑ba982022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽連訪法ABC16ABD2FED34GA5ACJNK12JMK13AHF14789101115161718202119ba 3F17J: b 3F(D)9A: * D F(a) q 連訪屬性及用戶計(jì)數(shù)992022年6月6日星

46、期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽基于基本文件目錄實(shí)現(xiàn)文件共享0 1 2 3 4 5 6 7 8 9 ID物理物理位置位置基本文件目錄空閑文件目錄基本文件目錄空閑文件目錄主文件目錄OafReportMistBeta(Wang)/Alpha(Zhang)SqrtSqrt5Beta6 Mist7Alpha 6Report 8Oaf9 Zhang 3Wang 4用戶符號(hào)文件子目錄Wang用戶符號(hào)文件子目錄ZhangIDID符號(hào)名符號(hào)名符號(hào)名符號(hào)名ID符號(hào)名符號(hào)名q 基本文件目錄q 符號(hào)文件目錄其它其它信息信息1002022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.6 文件共享與保護(hù)6.6.1

47、 文件共享概念與發(fā)展6.6.2 基于索引結(jié)點(diǎn)的共享方式6.6.3 利用符號(hào)鏈實(shí)現(xiàn)文件共享6.6.4 文件系統(tǒng)安全保護(hù)6.6.5 磁盤容錯(cuò)技術(shù)1012022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽基于索引結(jié)點(diǎn)的文件共享q不同文件目錄與共享文件間關(guān)系的建立FCB在不同目錄文件中的拷貝v 一旦文件發(fā)生改變，則一致性難以保證符號(hào)目錄與索引結(jié)點(diǎn)相結(jié)合v 指針懸空問題用戶C目錄Owner = CCount = 1用戶C目錄Owner = CCount = 2用戶B目錄用戶B目錄Owner = CCount = 1鏈接前鏈接后擁有者刪除文件后文件刪除否？1022022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)

48、學(xué)院 翟高壽6.6 文件共享與保護(hù)6.6.1 文件共享概念與發(fā)展6.6.2 基于索引結(jié)點(diǎn)的共享方式6.6.3 利用符號(hào)鏈實(shí)現(xiàn)文件共享6.6.4 文件系統(tǒng)安全保護(hù)6.6.5 磁盤容錯(cuò)技術(shù)1032022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽基于符號(hào)鏈的文件共享qLINK類型文件僅包含被共享文件的路徑名即符號(hào)鏈文件操作由系統(tǒng)根據(jù)文件類型區(qū)別處理q評(píng)析只有文件主才擁有其索引結(jié)點(diǎn)的指針，從而避免了指針懸空問題可用于鏈接網(wǎng)絡(luò)中任何地方計(jì)算機(jī)中的文件系統(tǒng)開銷問題v文件操作多次讀盤與磁盤啟動(dòng)v符號(hào)鏈索引結(jié)點(diǎn)及文件空間開銷v整個(gè)文件系統(tǒng)遍歷操作的復(fù)雜度和工作量加大整個(gè)文件系統(tǒng)遍歷操作的復(fù)雜度和工作量加大

49、1042022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.6 文件共享與保護(hù)6.6.1 文件共享概念與發(fā)展6.6.2 基于索引結(jié)點(diǎn)的共享方式6.6.3 利用符號(hào)鏈實(shí)現(xiàn)文件共享6.6.4 文件系統(tǒng)安全保護(hù)6.6.5 磁盤容錯(cuò)技術(shù)1052022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽文件安全性影響因素及對(duì)策q人為因素存取控制機(jī)制存取控制機(jī)制q系統(tǒng)因素系統(tǒng)容錯(cuò)技術(shù)q自然因素后備系統(tǒng)1062022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽保護(hù)域及與進(jìn)程間聯(lián)系方式域1域2域31072022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽訪問矩陣及切換權(quán)引入域 對(duì)象文件F1 文件F2 文件F

50、3 文件F4 文件F5 文件F6打印機(jī)1 繪圖儀2D1RRWD2RRWERWWD3RWEWW域 對(duì)象文件F1文件F2文件F3文件F4文件F5文件F6打印機(jī)1 繪圖儀2 D1 D2 D3D1RRWSD2RRWE RWWSD3RWEWW1082022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽拷貝權(quán)與所有權(quán)域 對(duì)象文件F1 文件F2 文件F3D1EW*D2ER*ED3E域 對(duì)象文件F1 文件F2 文件F3D1EW*D2ER*ED3ERW域 對(duì)象文件F1 文件F2 文件F3D1OEWD2R*O R*OWD3E域 對(duì)象文件F1 文件F2 文件F3D1OED2R*OW* R*OWD3WW1092022

51、年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽控制權(quán)（保護(hù)域之間）域 對(duì)象文件F1文件F2文件F3文件F4文件F5文件F6打印機(jī)1 繪圖儀2 D1 D2 D3D1RRWD2RRWE RWWCD3REWWW1102022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽訪問矩陣的簡(jiǎn)化策略q必要性與可行性訪問矩陣存儲(chǔ)開銷及其稀疏性特征q簡(jiǎn)化對(duì)策訪問控制表訪問權(quán)限表訪問權(quán)限表兼有式實(shí)現(xiàn)機(jī)制對(duì)象類型 訪問權(quán)限 對(duì)象指針文件RptrF3文件RWEptrF4文件RWptrF5打印機(jī)WptrPrn0123索引結(jié)點(diǎn)編號(hào)1112022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽文件系統(tǒng)安全管理體系q系統(tǒng)級(jí)安全管理

52、注冊(cè)與登陸（注冊(cè)用戶表）q用戶級(jí)安全管理用戶分類及訪問權(quán)設(shè)定q目錄級(jí)安全管理目錄的讀/寫/執(zhí)行許可權(quán)q文件級(jí)安全管理文件屬性及有效訪問權(quán)1122022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.6 文件共享與保護(hù)6.6.1 文件共享概念與發(fā)展6.6.2 基于索引結(jié)點(diǎn)的共享方式6.6.3 利用符號(hào)鏈實(shí)現(xiàn)文件共享6.6.4 文件系統(tǒng)安全保護(hù)6.6.5 磁盤容錯(cuò)技術(shù)1132022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽磁盤容錯(cuò)技術(shù)q基本概念設(shè)置冗余部件以提高系統(tǒng)可靠性q低級(jí)磁盤容錯(cuò)技術(shù)SFT-I雙份目錄與雙份文件分配表熱修復(fù)重定向、寫后讀校驗(yàn)q中級(jí)磁盤容錯(cuò)技術(shù)SFT-II磁盤鏡像與磁盤雙

53、工1142022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.6 文件共享與保護(hù)6.6.1 文件共享概念與發(fā)展6.6.2 基于索引結(jié)點(diǎn)的共享方式6.6.3 利用符號(hào)鏈實(shí)現(xiàn)文件共享6.6.4 文件系統(tǒng)安全保護(hù)6.6.5 磁盤容錯(cuò)技術(shù)1152022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽第六章第六章 文件管理文件管理6.1 文件和文件系統(tǒng)6.2 文件的邏輯結(jié)構(gòu)6.3 外存分配方式6.4 文件存儲(chǔ)空間管理6.5 目錄管理6.6 文件共享與保護(hù)6.7 數(shù)據(jù)一致性控制1162022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.7 數(shù)據(jù)一致性控制6.7.1 數(shù)據(jù)一致性問題及技術(shù)6.7.2 事

54、務(wù)概念及恢復(fù)算法6.7.3 檢查點(diǎn)及恢復(fù)算法改進(jìn)6.7.4 并發(fā)控制技術(shù)6.7.5 重復(fù)數(shù)據(jù)的一致性問題1172022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽數(shù)據(jù)的一致性問題q當(dāng)一個(gè)數(shù)據(jù)被分別存儲(chǔ)到多個(gè)文件中時(shí)，便會(huì)出現(xiàn)數(shù)據(jù)的一致性問題商品進(jìn)價(jià)（流水賬、付費(fèi)帳、分類賬、總帳），修改中系統(tǒng)發(fā)生故障q硬件支持-穩(wěn)定存儲(chǔ)器理論上不會(huì)出現(xiàn)故障和錯(cuò)誤而實(shí)際上高度可靠的存儲(chǔ)器系統(tǒng)采用冗余技術(shù)，即將一份信息同時(shí)駐留在多個(gè)獨(dú)立的非易失性的存儲(chǔ)器上1182022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.7 數(shù)據(jù)一致性控制6.7.1 數(shù)據(jù)一致性問題及技術(shù)6.7.2 事務(wù)概念及恢復(fù)算法6.7.3 檢查

55、點(diǎn)及恢復(fù)算法改進(jìn)6.7.4 并發(fā)控制技術(shù)6.7.5 重復(fù)數(shù)據(jù)的一致性問題1192022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽事務(wù)概念及恢復(fù)算法q事務(wù)的定義用于訪問和修改各種數(shù)據(jù)項(xiàng)的一個(gè)程序單位可分散在多個(gè)文件中“原子性”特征（提交操作/夭折操作）q事務(wù)記錄（運(yùn)行記錄）事務(wù)名、數(shù)據(jù)項(xiàng)名、舊值、新值、q恢復(fù)算法已完成事務(wù)Redo(Ti) /夭折事務(wù)Undo(Ti)1202022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.7 數(shù)據(jù)一致性控制6.7.1 數(shù)據(jù)一致性問題及技術(shù)6.7.2 事務(wù)概念及恢復(fù)算法6.7.3 檢查點(diǎn)及恢復(fù)算法改進(jìn)6.7.4 并發(fā)控制技術(shù)6.7.5 重復(fù)數(shù)據(jù)的一致性問

56、題1212022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽檢查點(diǎn)q檢查點(diǎn)作用事務(wù)記錄清理工作經(jīng)常化，減少恢復(fù)開銷根據(jù)記錄來執(zhí)行恢復(fù)操作q恢復(fù)算法改進(jìn)查找事務(wù)記錄表，確定在最近檢查點(diǎn)以前開始執(zhí)行的最后事務(wù)Ti針對(duì)Ti以后開始執(zhí)行的事務(wù)集T中的事務(wù)Tk區(qū)別不同情況分別執(zhí)行恢復(fù)操作Redo(Tk) /Undo(Tk)1222022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽6.7 數(shù)據(jù)一致性控制6.7.1 數(shù)據(jù)一致性問題及技術(shù)6.7.2 事務(wù)概念及恢復(fù)算法6.7.3 檢查點(diǎn)及恢復(fù)算法改進(jìn)6.7.4 并發(fā)控制技術(shù)6.7.5 重復(fù)數(shù)據(jù)的一致性問題1232022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽并發(fā)控制q用于實(shí)現(xiàn)事務(wù)順序性的技術(shù)q利用互斥鎖來實(shí)現(xiàn)順序性共享對(duì)象互斥鎖簡(jiǎn)單易行，但效率不高效率不高q利用互斥鎖和共享鎖來實(shí)現(xiàn)順序性共享文件具有只允許一個(gè)事務(wù)去寫但卻允許多個(gè)事務(wù)同時(shí)讀的特點(diǎn)類似于讀者與寫者問題解決方案1242022年6月6日星期一北京交通大學(xué)計(jì)算機(jī)學(xué)