【正文】 索速度 查找一個(gè)文件的平均訪(fǎng)盤(pán)次數(shù) 74 2022/8/17 第六章 文件系統(tǒng) 目錄操作 目錄創(chuàng)建 目錄刪除 文件檢索 目錄打開(kāi) 目錄關(guān)閉 75 2022/8/17 第六章 文件系統(tǒng) 線(xiàn)性表算法 最簡(jiǎn)單的算法，每個(gè)表項(xiàng)由文件名和指向數(shù)據(jù)塊的指針組成。 缺點(diǎn)：線(xiàn)性搜索 76 2022/8/17 第六章 文件系統(tǒng) 哈希表算法 目錄項(xiàng)信息存放在一個(gè)哈希表中。 優(yōu)點(diǎn)：大幅減少搜索時(shí)間 缺點(diǎn)：哈希表的長(zhǎng)度和哈希函數(shù)難以選擇。 常見(jiàn)塊大?。?512B， 1KB或 2KB 79 2022/8/17 第六章 文件系統(tǒng) 如何記錄空閑塊 1. 空閑塊表 （空白文件目錄） 將所有空閑塊記錄在一個(gè)表中，即空閑塊表 2. 空閑塊鏈表 把所有空閑塊鏈成一個(gè)鏈 3. 位圖法 用一串二進(jìn)制位反映磁盤(pán)空間中分配使用情況 , 每個(gè)物理塊對(duì)應(yīng)一位 , 如： 分配物理塊為 1，否則為 0 ? UNIX的成組鏈接法 80 2022/8/17 第六章 文件系統(tǒng) 空白塊表 僅當(dāng)有少量的空白區(qū)時(shí)才有較好的效果 如果存取空間中有著大量的小的空白區(qū) ， 則其目錄變得很大 ， 因而效率大為降低 。 序號(hào) 第一空白塊號(hào) 空白塊個(gè)數(shù) 物理塊號(hào) 1 2 4 （ 2， 3， 4， 5） 2 9 3 （ 9， 10， 11） 3 15 5 （ 15， 16， 17，18， 19） 4 — — — 81 2022/8/17 第六章 文件系統(tǒng) 2. 空閑塊鏈 把所有的 “空白塊 ” 鏈在一起 。 回收文件時(shí)回收塊鏈到空白鏈上 。 例：物理塊 1K， 200M的磁盤(pán)需要有200K位來(lái)映射，即只需 25個(gè)塊。 N還可兼作棧頂指針用。 成鏈 將每一組含有的盤(pán)塊總數(shù) N和該組所有的盤(pán)塊號(hào)記入其前一組的第一個(gè)盤(pán)塊的(0)— S． free(99)。 85 2022/8/17 第六章 文件系統(tǒng) 86 2022/8/17 第六章 文件系統(tǒng) 空閑盤(pán)塊的分配與回收 分配 首先 檢查空閑盤(pán)塊號(hào)棧是否上鎖。 若該盤(pán)塊號(hào) A已是棧底 ，調(diào)用磁盤(pán)讀過(guò)程將該盤(pán)塊號(hào)所對(duì)應(yīng)的盤(pán)塊中保存的下一組可用的盤(pán)塊號(hào)讀入盤(pán)塊號(hào)棧中；并把盤(pán)塊號(hào) A（棧底）對(duì)應(yīng)的盤(pán)塊分配出去。 87 2022/8/17 第六章 文件系統(tǒng) ? 回收 將回收盤(pán)塊的盤(pán)塊號(hào)，記入空閑盤(pán)塊號(hào)棧的頂部，并執(zhí)行空閑盤(pán)塊數(shù)加 1操作。 88 2022/8/17 第六章 文件系統(tǒng) 所謂文件共享指系統(tǒng)允許多個(gè)用戶(hù)或進(jìn)程共享同一份文件。 如果系統(tǒng)不能提供文件共享功能，就意味著凡是需要該文件的用戶(hù)都要自備此文件的副本。 這里需要擴(kuò)充目錄項(xiàng)，增加：用戶(hù)計(jì)數(shù)。 硬鏈接 91 2022/8/17 第六章 文件系統(tǒng) 92 2022/8/17 第六章 文件系統(tǒng) 利用符號(hào)鏈實(shí)現(xiàn)文件共享 用戶(hù) A為了共享用戶(hù) B的 Bboot目錄下的一個(gè)文件 ， 可以創(chuàng)建一個(gè) LINK類(lèi)型的新文件 x， 新文件 x中僅包含被鏈接文件。 軟鏈接 優(yōu)勢(shì)：計(jì)算機(jī)網(wǎng)絡(luò)環(huán)境下可用 問(wèn)題：系統(tǒng)開(kāi)銷(xiāo)大 93 2022/8/17 第六章 文件系統(tǒng) 文件 x的內(nèi)容： /Bboot/ 94 2022/8/17 第六章 文件系統(tǒng) 實(shí)例： ? 各實(shí)際 OS是否提供鏈接技術(shù) ? DOS ?Windows √（ 快捷方式） ?Unix √（ 硬鏈接 /軟鏈接） 95 2022/8/17 第六章 文件系統(tǒng) 文件的保護(hù) (了解） 對(duì)擁有權(quán)限的用戶(hù)，應(yīng)該讓其進(jìn)行相應(yīng)操作，否則，應(yīng)禁止。 通常將用戶(hù)分成三類(lèi) : ? 文件主 ? 文件主的同組用戶(hù)或合作用戶(hù) ? 其它用戶(hù) 97 2022/8/17 第六章 文件系統(tǒng) 2 對(duì)訪(fǎng)問(wèn)權(quán)限分類(lèi) 對(duì)文件的訪(fǎng)問(wèn)系統(tǒng)首先要檢查訪(fǎng)問(wèn)權(quán)限 ， 只允許合法的用戶(hù)訪(fǎng)問(wèn) 。 ? 僅允許讀 (R)。 98 2022/8/17 第六章 文件系統(tǒng) 3 用訪(fǎng)問(wèn)控制矩陣實(shí)現(xiàn)文件保護(hù) 一維代表所有用戶(hù) ， 一維代表系統(tǒng)中的所有文件 。 99 2022/8/17 第六章 文件系統(tǒng) 100 2022/8/17 第六章 文件系統(tǒng) 4 存取控制表實(shí)現(xiàn)文件保護(hù) 101 2022/8/17 第六章 文件系統(tǒng) 5 用戶(hù)權(quán)限表實(shí)現(xiàn)文件保護(hù) 102 2022/8/17 第六章 文件系統(tǒng) 6 用口令實(shí)現(xiàn)文件保護(hù) 用戶(hù)為自己的每個(gè)文件規(guī)定一個(gè)口令 ， 有口令者才能訪(fǎng)問(wèn)文件 。 ? 不易改變存取控制權(quán)限。 (2) 通過(guò) 磁盤(pán)容錯(cuò) 技術(shù) ， 來(lái)防止由 磁盤(pán) 部分的故障所造成的文件不安全性 。 104 2022/8/17 第六章 文件系統(tǒng) SFT－ I ? 低級(jí)磁盤(pán)容錯(cuò)，解決磁盤(pán)表面發(fā)生問(wèn)題引起的數(shù)據(jù)丟失。 ? FAT（ 文件分配表）：記錄文件屬性，物理地址等。 ? 熱修復(fù)重定向：在磁盤(pán)中劃出一部分作為熱修復(fù)重定向區(qū)，存放壞磁道的待寫(xiě)數(shù)據(jù) ? 寫(xiě)后讀校驗(yàn)：寫(xiě)盤(pán)后，馬上從盤(pán)讀出與內(nèi)存校驗(yàn)看是否一致，不一致，重寫(xiě)入熱修復(fù)重定向區(qū)，標(biāo)記壞盤(pán)塊。 1)磁盤(pán)鏡像 ：增設(shè)一個(gè)完全相同的磁盤(pán)驅(qū)動(dòng)器。 缺點(diǎn)：磁盤(pán)的利用率為 50％。 ? 特點(diǎn)：每個(gè)磁盤(pán)有自己獨(dú)立的通道，可同時(shí)將數(shù)據(jù)寫(xiě)入，加塊數(shù)據(jù)讀取速度。 ? 事務(wù)也可以被看作是一系列相關(guān)讀和寫(xiě)操作 。事務(wù)名：用于標(biāo)識(shí)該事務(wù)的惟一名字； 110 2022/8/17 第六章 文件系統(tǒng) 3. 恢復(fù)算法 (1) undo〈 Ti〉 ： 該過(guò)程把所有被事務(wù) Ti修改過(guò)的數(shù)據(jù) ， 恢復(fù)為修改前的值 。 如果系統(tǒng)發(fā)生故障，系統(tǒng)應(yīng)對(duì)以前所發(fā)生的事務(wù)進(jìn)行清理。當(dāng)出現(xiàn)檢查點(diǎn)時(shí)，利用 undo/redo過(guò)程實(shí)現(xiàn)恢復(fù)功能。 恢復(fù)例程首先查找事務(wù)記錄表 ， 確定在最近檢查點(diǎn)以前開(kāi)始執(zhí)行的最后的事務(wù) Ti。 如果把所有在事務(wù) Ti以后開(kāi)始執(zhí)行的事務(wù)表示為事務(wù)集 T， 則新的恢復(fù)操作要求：對(duì)所有在 T中的事務(wù)TK, 如果在事務(wù)記錄表中出現(xiàn)了 〈 TK托付 〉 記錄 ， 則執(zhí)行 redo〈 TK〉 操作；反之 ， 如果在事務(wù)記錄表中并未出現(xiàn) 〈 TK托付 〉 記錄 ， 則執(zhí)行 undo〈 TK〉 操作 。） 114 2022/8/17 第六章 文件系統(tǒng) 重復(fù)數(shù)據(jù)的數(shù)據(jù)一致性問(wèn)題 1. 重復(fù)文件的一致性 UNIX類(lèi)型的文件目錄中，每個(gè)目錄項(xiàng)中含有一個(gè)索引結(jié)點(diǎn)號(hào)，指向該文件的索引結(jié)點(diǎn)。 UNIX類(lèi)型的目錄 115 2022/8/17 第六章 文件系統(tǒng) 2. 盤(pán)塊號(hào)一致性的檢查 * 檢查盤(pán)塊號(hào)一致性情況 116 2022/8/17 第六章 文件系統(tǒng) 檢查盤(pán)塊號(hào)一致性情況 117 2022/8/17 第六章 文件系統(tǒng) 3. 鏈接數(shù)一致性檢查 UNIX中 ， 索引結(jié)點(diǎn)在目錄中出現(xiàn)的次數(shù) ， 和索引結(jié)點(diǎn)中的鏈接計(jì)數(shù)應(yīng)該一致 。 檢查時(shí) ， 從根目錄開(kāi)始查找 ， 當(dāng)在目錄中遇到該索引結(jié)點(diǎn)號(hào)時(shí) ， 在該計(jì)數(shù)器表中相應(yīng)文件的表項(xiàng)上加 1。 當(dāng)鏈接計(jì)數(shù)值與索引結(jié)點(diǎn)號(hào)計(jì)數(shù)值不一致時(shí) ， 應(yīng)將count值置為正確值