【正文】 文件管理 空閑表法和空閑鏈表法 ? 空閑鏈表法 ? 空閑盤塊鏈 ? 將磁盤上的所有空閑空間，以盤塊為單位拉成一條鏈。分配時(shí)從鏈?zhǔn)组_始，依次摘下適當(dāng)數(shù)目的空閑盤塊分配給用戶，回收時(shí)，將回收的盤塊依次插入鏈末尾。分配和回收一個(gè)盤塊非常簡(jiǎn)單，但分配多個(gè)盤塊時(shí)要重復(fù)操作多次。 ? 空閑盤區(qū)鏈 ? 將磁盤上的所有空閑盤區(qū) (每個(gè)盤區(qū)可包含若干個(gè)盤塊 )拉成一條鏈。包含指向下一分區(qū)的指針還包括指明本區(qū)盤塊數(shù)的信息。分配與內(nèi)存動(dòng)態(tài)分區(qū)類似。 文件管理 位示圖法 ? 位示圖法： 1 1 1 0 0 0 1 1 1 0 0 1 0 0 1 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 2 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 3 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 0 4 … 16 位示圖 文件管理 位示圖法 ? 盤塊的分配 ： ? 1) 順序掃描位示圖，從中找出一個(gè)或一組其值為“ 0”的二進(jìn)制位 (“0”表示空閑時(shí) )。 ? 2) 將所找到的一個(gè)或一組二進(jìn)制位， 轉(zhuǎn)換成與之相應(yīng)的盤塊號(hào)。假定找到的其值為“ 0”的二進(jìn)制位，位于位示的第 i行、第 j列，則其相應(yīng)的盤塊號(hào)應(yīng)按下式計(jì)算： ? b=n( i1)+ j 式中， n ? 3) 修改位示圖， 令 map［ i, j］ =1。 文件管理 位示圖法 ? 盤塊的回收 ： ? 將回收盤塊的盤塊號(hào)轉(zhuǎn)換成位示圖中的行號(hào)和列號(hào)。 轉(zhuǎn)換公式為： ? i=(b1)DIV n+1 ? j=(b1)MOD n+1 ? 修改位示圖。 令 map ［ i,j］ =1。 文件管理 位示圖法 ? 一磁盤有 6400塊，每塊長(zhǎng)度為 1024字節(jié)，塊號(hào)記作 1—6400，現(xiàn)用 400個(gè)16位 (Bit)的字作該磁盤的位示圖，試問第 2999塊對(duì)應(yīng)于位示圖中的第幾字的第幾位 (字、位均從 0開始計(jì) )；而第 299字的第 7位 (同上，從 0開始 )又對(duì)應(yīng)第幾塊？ ? 解： 1) ∵ 2999 / 16 = 187 …… 7 ∴ 第 2999塊對(duì)應(yīng)于位示圖中第 187字的第 6位； 2) ∵ 299*16+8=4792 ∴ 第 299字的第 7位對(duì)應(yīng)于第 4792塊。 文件管理 位示圖法 ? 位示圖 (bitmap)特點(diǎn)： ? 位示圖描述能力強(qiáng)，占用空間小，可以復(fù)制到內(nèi)存，使查找既方便又快速 ? 位示圖需要常駐內(nèi)存 ? 窮舉式搜索會(huì)降低文件系統(tǒng)的性能。大多數(shù)使用位示圖的文件系統(tǒng)都有輔助數(shù)據(jù)結(jié)構(gòu)，用于匯總表的子區(qū)域的內(nèi)容。例：可在邏輯上化分成許多個(gè)子區(qū)域，對(duì)于每個(gè)子區(qū)域，匯總表中包括它的自由塊的數(shù)目和連續(xù)自由塊的最大數(shù)目 文件管理 成組鏈接法 ? 成組鏈接法： ? 空閑表法和空閑鏈表法，都不適用于大型文件系統(tǒng)，因?yàn)檫@使得空閑表或空閑鏈太長(zhǎng)。 UNIX將這兩種方法結(jié)合 ——成組鏈接法。 ? 兼?zhèn)淞松鲜鰞煞N方法的優(yōu)點(diǎn)而克服了兩種方法的缺點(diǎn)： ? 表太長(zhǎng) 文件管理 成組鏈接法 ? 空閑盤塊的組織： ? 空閑盤塊號(hào)棧 ? 包括：用來存放當(dāng)前可用的一組空閑盤塊的盤塊號(hào) (最多含 100個(gè)號(hào) )，以及棧中尚有的空閑盤塊號(hào)數(shù) N。 N還兼作棧頂指針用。棧是臨界資源，系統(tǒng)為棧設(shè)置了一把鎖。 ? 文件區(qū)中的所有空閑盤塊，被分成若干個(gè)組。 ? 將每一組含有的盤塊總數(shù) N和該組所有的盤塊號(hào)，記入其前一組的第一個(gè)盤塊的 S_free(0) S_free(99)中。 ? 將第一組的盤塊總數(shù)和所有的盤塊號(hào)，記入空閑盤塊號(hào)棧中。 ? 最末一組只有 99個(gè)盤塊，在 S_free（ 0）中則存放“ 0”。 文件管理 成組鏈接法 100400399301300100300299…202201299…100400399…201 301………9907999790179007899…78017999…7901空 閑 盤 塊號(hào)棧S . f r e e019899文件管理 成組鏈接法 ? 空閑盤塊的分配： ? 當(dāng)系統(tǒng)為用戶分配文件所需的盤塊時(shí)，調(diào)用盤塊分配過程來完成。 ? 首先檢查空閑盤塊號(hào)棧是否上鎖，如未上鎖便從棧頂取出一空閑盤塊號(hào)，將與之對(duì)應(yīng)的盤塊分配給用戶，然后將棧頂指針下移一格。 ? 若該盤塊號(hào)已是棧底， 即 (0)，當(dāng)前棧中最后一個(gè)可分配的盤塊號(hào)。 ? 調(diào)用磁盤讀過程，將棧底盤塊號(hào)所對(duì)應(yīng)盤塊的內(nèi)容讀入棧中，作為新的盤塊號(hào)棧的內(nèi)容，并把原棧底對(duì)應(yīng)的盤塊分配出去 )。 ? 然后，再分配一相應(yīng)的緩沖區(qū) (作為該盤塊的緩沖區(qū) )。 ? 最后，把棧中的空閑盤塊數(shù)減 1并返回。 文件管理 成組鏈接法 ? 空閑盤塊的回收： ? 當(dāng)系統(tǒng)為用戶分配文件所需的盤塊時(shí)，調(diào)用盤塊回收過程來完成。 ? 將回收盤塊的盤塊號(hào)記入空閑盤塊號(hào)棧的頂部，并執(zhí)行空閑盤塊數(shù)加 1操作 ? 當(dāng)空閑盤塊號(hào)數(shù)目已經(jīng)達(dá)到 100時(shí)，表示棧已滿，便將現(xiàn)有棧中的 100個(gè)盤塊號(hào)，記入新回收的盤塊中，再將其盤塊號(hào)作為新的棧底。 文件管理 文件共享與文件保護(hù) ? 在現(xiàn)代計(jì)算機(jī)系統(tǒng)中，必須提供文件共享手段，即指系統(tǒng)應(yīng)允許許多用戶（進(jìn)程）共享同一文件。 ? 基于索引結(jié)點(diǎn)的共享方式 ? 利用符號(hào)鏈實(shí)現(xiàn)文件共享 ? 磁盤容錯(cuò)技術(shù) 文件管理 基于索引節(jié)點(diǎn)的共享方式 ? 基于索引節(jié)點(diǎn)的共享方式： ? 在樹型結(jié)構(gòu)的目錄中，當(dāng)有兩個(gè)（或多個(gè)）用戶要共享一個(gè)子目錄或文件時(shí)，必須將共享文件或子目錄鏈接到兩個(gè)（或多個(gè)）用戶的目錄中，才能方便地找到該文件。 文件管理 基于索引節(jié)點(diǎn)的共享方式 ? 基于索引節(jié)點(diǎn)的共享方式： A B C B C C C D A C ? B B C E C 根目錄 如何建立 B目錄與共享文件之間的鏈接呢？ 文件管理 基于索引節(jié)點(diǎn)的共享方式 ? 基于索引節(jié)點(diǎn)的共享方式： ? 如果在文件目錄中包含了文件的物理地址，即文件所在盤塊的盤塊號(hào)，則在鏈接時(shí)，必須將文件的物理地址拷貝到 B目錄中去。 而新增加的部分內(nèi)容已不能共享 為解決這個(gè)問題，可引用索引節(jié)點(diǎn)。在文件目錄中只設(shè)置文件名及指向相應(yīng)索引節(jié)點(diǎn)的指針。 索引節(jié)點(diǎn)中增加一個(gè)鏈接計(jì)數(shù) count ，用于表示鏈接到本索引節(jié)點(diǎn)上的用戶目錄項(xiàng)的數(shù)目。 文件管理 基于索引節(jié)點(diǎn)的共享方式 Test r Test r Wang用戶文件目錄 Lee用戶文件目錄 Count=2 文件物理地址 索引節(jié)點(diǎn) Test 基于索引節(jié)點(diǎn)的共享方式 文件管理 基于索引節(jié)點(diǎn)的共享方式 C的目錄 B的目錄 C的目錄 B的目錄 owner=c count=1 owner=c count=2 owner=c count=1 鏈接前 建立鏈接后 擁有者刪除文件后 進(jìn)程 B鏈接前后的情況 如果用戶 C不再需要此文件，是否能將此文件刪除呢？ 不能 文件管理 利用符號(hào)鏈實(shí)現(xiàn)文件共享 ? 利用符號(hào)鏈實(shí)現(xiàn)文件共享： ? 為使 B能共享 C的一個(gè)文件 F，可以由系統(tǒng)創(chuàng)建一個(gè) LINK類型的新文件，也取名為 F，并將 F寫入 B的目錄中，以實(shí)現(xiàn) B的目錄與文件 F的鏈接。在新文件中只包含被鏈接文件 F的路徑名。這樣的鏈接方法被稱為 符號(hào)鏈接 （ Symbolic Linking）。 文件管理 利用符號(hào)鏈實(shí)現(xiàn)文件共享 ? 利用符號(hào)鏈實(shí)現(xiàn)文件共享： ? 在利用符號(hào)鏈方式實(shí)現(xiàn)文件共享時(shí)， 只是文件主才擁有指向其索引結(jié)點(diǎn)的指針；而共享該文件的其他用戶，則只有該文件的路徑名，并不擁有指向其索引結(jié)點(diǎn)的指針。 ? 不會(huì)發(fā)生在文件主刪除一共享文件后留下一懸空指針的情況。 當(dāng)文件的擁有者把一個(gè)共享文件刪除后， 其他用戶試圖通過符號(hào)鏈去訪問一個(gè)已被刪除的共享文件時(shí)，會(huì)因系統(tǒng)找不到該文件而使訪問失敗，于是再將符號(hào)鏈刪除，此時(shí)不會(huì)產(chǎn)生任何影響。 文件管理 利用符號(hào)鏈實(shí)現(xiàn)文件共享 ? 利用符號(hào)鏈實(shí)現(xiàn)文件共享： ? 符號(hào)鏈的共享方式存在的問題： ? 當(dāng)其他用戶去讀共享文件時(shí)，系統(tǒng)是根據(jù)給定的文件路徑名，逐個(gè)分量 (名 )地去查找目錄，直至找到該文件的索引節(jié)點(diǎn) (或找不到 )。 ? 在每次訪問共享文件時(shí)，都可能要多次地讀盤，開銷大！而且，為每個(gè)共享用戶創(chuàng)建一條符號(hào)鏈， (一個(gè)索引結(jié)點(diǎn) )，耗費(fèi)空間。