【文章內(nèi)容簡介】 2字節(jié) 。設物理塊大小 512字節(jié)。假設目錄文件有 128個目錄項。 63 文件目錄 若不分解目錄項，一個盤塊存放 5l2/48 =10目錄項，128個目錄項需要 13個盤塊 ，查找一個文件的平均訪問的盤塊數(shù)： (1+13)/2=7次 分解后一個盤塊存放 5l2/8=64個符號目錄項， 128個符號目錄項需要 2個盤塊 ，查找一個文件的平均訪問的盤塊數(shù)： (1十 2)/2= 64 文件系統(tǒng)的實現(xiàn) 641 打開文件表 當用戶申請打開一個文件時，系統(tǒng)要在內(nèi)存中為該用戶保存一些表目。在內(nèi)存中所需的表目有系統(tǒng)打開文件表和用戶打開文件表。 ? 系統(tǒng)打開文件表 該 “ 系統(tǒng)打開文件表 ” 放在內(nèi)存，用于保存已打開文件的目錄項。此外，還保存文件號、共享計數(shù)、修改標志等等 ? 用戶打開文件表 每個進程一個都有一個 “ 用戶打開文件表 ” 。該表的內(nèi)容有文件描述符，打開方式、系統(tǒng)打開文件表入口等等 ? 用戶打開文件表與系統(tǒng)打開文件表之間的關(guān)系 用戶打開文件表指向了系統(tǒng)打開文件表。如果多個進程共享同一個文件，則多個用戶打開文件表目對應系統(tǒng)打開文件表的同一入口 64 文件系統(tǒng)的實現(xiàn) 64 文件系統(tǒng)的實現(xiàn) ? 空閑塊表法 ? 數(shù)據(jù)結(jié)構(gòu) 系統(tǒng)為每個磁盤建立一張空 閑塊表，表中每個登記項記錄一 組連續(xù)空閑塊的首塊號和塊數(shù)， 空閑塊數(shù)為 “ 0”的登記項為 “ 空 ” 登記項 ? 分配回收算法 這種管理方式適合采用順序結(jié)構(gòu)的文件 ,分配和回收算法類似主存儲器的可變分區(qū)管理方式中采用的最先適應、最優(yōu)適應和最壞適應算法 思考：如何實現(xiàn)？ 64 文件系統(tǒng)的實現(xiàn) 642 外存空間管理 ? 空閑鏈表法 ? 空閑盤塊鏈 空閑盤塊鏈以盤塊為基本元素構(gòu)成一條鏈 分配時從鏈首開始，依次摘下適當數(shù)目的空閑盤塊分配給用戶，回收時將回收的盤塊依次鏈入空閑盤塊鏈 思考：如何實現(xiàn)？ 優(yōu)缺點：分配和回收一個盤塊的過程非常簡單，但是空閑盤塊鏈可能很大 64 文件系統(tǒng)的實現(xiàn) ? 空閑盤區(qū)鏈 將磁盤上的所有空閑盤區(qū)（每個盤區(qū)可包含若干個盤塊）拉成一條鏈 分配方法與內(nèi)存的動態(tài)分區(qū)分配類似，通常采用首次適應算法。在回收盤區(qū)時，同樣也要將與回收區(qū)鄰接的空閑盤區(qū)與之合并。 思考：如何實現(xiàn)？ 優(yōu)缺點：分配和回收過程較復雜，但空閑盤區(qū)鏈較短 64 文件系統(tǒng)的實現(xiàn) ? 位示圖法 ? 磁盤塊的組織 根據(jù)磁盤總塊數(shù)決定位示圖由多少字組成，位示圖中的每一位與一個磁盤塊對應，某位為 “ 1”狀態(tài)表示相應塊已被占用，為 “ 0”狀態(tài)的位所對應的塊是空閑塊 一般公式為： 塊號 =i 位示圖中的字長 +j 64 文件系統(tǒng)的實現(xiàn) ? 磁盤塊的分配 當有文件要存放到磁盤上時 ， 查位示圖中為 “ 0”的位 ，表示對應的磁盤塊空閑可供使用 。 根據(jù)查到的位所在的字號和位號可計算出對應的塊號 ， 同時在該位填上占用標志 “ 1” ? 磁盤塊的回收 當刪除文件歸還存儲空間時 ， 可以根據(jù)歸還塊的塊號推算出在位示圖中的位置： 塊號 =柱面號 每個柱面中的塊數(shù) +磁頭號 每個磁道的塊數(shù) +扇區(qū)號 字號 =[塊號 /位示圖中字長 ] 位號 =塊號 mod位示圖中字長 然后把這一位的 “ 1”清成 “ 0”，表示該塊成為空閑塊 思考：算法如何寫？ 64 文件系統(tǒng)的實現(xiàn) ? 成組鏈接法 ? 空閑塊的組織 把空閑塊分成若干組，每一組的第一個空閑塊中登記下一組空閑塊的塊號和空閑塊數(shù) 64 文件系統(tǒng)的實現(xiàn) 64 文件系統(tǒng)的實現(xiàn) ? 空閑塊的分配和回收 分配 系統(tǒng)初始化時先把專用塊內(nèi)容讀到主存儲器 ， 每分配一塊后把空閑塊數(shù)減 1。 但一組的第一個空閑塊分配之前應把登記在該塊中的下一組的塊號及塊數(shù)保存到專用塊中 。 分配一個空閑塊的算法 : 查詢 L單元內(nèi)容（空閑塊數(shù)）： 當空閑塊數(shù) l i=L+空閑塊數(shù)； 從 i單元得到一空閑塊號； 把該塊分配給申請者； 空閑塊數(shù)減 1； 當空閑塊數(shù) =1 取出 L+l單元內(nèi)容（第一塊塊號或 0）； 其值 =0 無空閑塊，申請者失??； 其值 ≠ 0 把該塊內(nèi)容復制到專用塊； 該塊分配給申請者； 把專用塊內(nèi)容讀到主存 L開始的區(qū)域。 64 文件系統(tǒng)的實現(xiàn) 回收 當歸還一塊時 ， 只要把歸還塊的塊號登記到當前組中且空閑塊數(shù)加 1。 如果當前組已滿 100塊 ， 則把主存中的內(nèi)容寫到歸還的那塊中 ， 該歸還塊作為新組的第一塊 歸還一塊的算法 : 查詢 L單元的空閑塊數(shù)： 當空閑塊數(shù)＜ 100 空閑塊數(shù)加 1； j=L+空閑塊數(shù)； 歸還塊號填入 j單元。 當空閑塊數(shù) =100 把主存中登記的信息寫入歸還塊中； 把歸還塊號填入 L+l單元； 將 L單元置成 1。 64 文件系統(tǒng)的實現(xiàn) 651 主要操作 文件系統(tǒng)與用戶的接口：第一類是與文件有關(guān)的操作命令或作業(yè)控制語言中與文件有關(guān)的語句 。第二類是提供給用戶程序使用的文件類系統(tǒng)調(diào)用指令 ? 建立 查文件目錄表，看有沒有同名文件存在，有則拒絕建立，給出錯誤信息，否則分配給該文件一空目錄項，并填入文件名和用戶提供的參數(shù)。 為要建立的文件分配存儲空間。 將新建文件的目錄項讀入打開文件表中（即完成打開文件的工作），為以后寫文件作好準備。 65 文件的使用 ? 打開 根據(jù)文件路徑名查目錄。 根據(jù)打開方式、共享說明和用戶身份檢查訪問合法性。 根據(jù)文件號查系統(tǒng)打開文件表，看文件是否已被打開。如果是，共享計數(shù)加 1，否則，信息填入系統(tǒng)打開文件表空表項，共享計數(shù)置為 1。 在用戶打開文件表中取一空表項，填寫打開方式等，并指向系統(tǒng)打開文件表對應表項。 ? 關(guān)閉 將打開文件表中該文件的 “ 當前使用用戶數(shù) ” 減 1，若為 0，則撤消此表目。 若打開文件表目內(nèi)容已被改過，則應先將表目內(nèi)容寫回輔存上相應表目中，以使文件目錄保待最新狀態(tài)；卷定位工作。 65 文件的