操作系統(tǒng)第6章文件管理(5)

1、Operating SystemOperating SystemPage 12022-1-14Operating SystemOperating SystemPage 22022-1-14q文件和文件系統(tǒng)文件和文件系統(tǒng)q文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)q外存分配方式外存分配方式q目錄管理目錄管理q文件存儲空間的管理文件存儲空間的管理q文件共享與文件保護文件共享與文件保護q數(shù)據(jù)一致性控制數(shù)據(jù)一致性控制Operating SystemOperating SystemPage 32022-1-146.5 文件存儲空間的管理文件存儲空間的管理 解決的問題：如何為新創(chuàng)建的文件分配存儲空間？解決的問題：如何為

2、新創(chuàng)建的文件分配存儲空間？解決的方法：（分配的基本單位都是磁盤塊）。解決的方法：（分配的基本單位都是磁盤塊）。1、分配方式：、分配方式：（1）連續(xù)分配：訪問速度高，但會產(chǎn)生外存零頭。）連續(xù)分配：訪問速度高，但會產(chǎn)生外存零頭。（2）離散分配：訪問速度慢，但能有效利用外存空間。）離散分配：訪問速度慢，但能有效利用外存空間。2、分配時數(shù)據(jù)結(jié)構(gòu)、分配時數(shù)據(jù)結(jié)構(gòu)3、分配回收算法、分配回收算法Operating SystemOperating SystemPage 42022-1-14q空閑表法和空閑鏈表法空閑表法和空閑鏈表法q位示圖法位示圖法q成組鏈接法成組鏈接法Operating SystemOper

3、ating SystemPage 52022-1-14q文件存儲空間管理的基本分配單位是盤塊文件存儲空間管理的基本分配單位是盤塊q空閑表法空閑表法v空閑表屬于空閑表屬于連續(xù)分配方式連續(xù)分配方式，與內(nèi)存的動態(tài)分配方，與內(nèi)存的動態(tài)分配方式雷同，為每個文件分配一個連續(xù)的存儲空間式雷同，為每個文件分配一個連續(xù)的存儲空間v為外存上的所有空閑區(qū)建立一張空閑表，每個空為外存上的所有空閑區(qū)建立一張空閑表，每個空閑區(qū)對應(yīng)于一個閑表項，將所有空閑區(qū)按起始盤閑區(qū)對應(yīng)于一個閑表項，將所有空閑區(qū)按起始盤塊號遞增的順序排列塊號遞增的順序排列v存儲空間的分配與回收可采用存儲空間的分配與回收可采用首次適應(yīng)算法、循首次適應(yīng)算法

4、、循環(huán)首次適應(yīng)算法環(huán)首次適應(yīng)算法等等v如對換方式中對如對換方式中對對換空間對換空間的分配就采用連續(xù)分配，的分配就采用連續(xù)分配，主要目的是提高速度，主要目的是提高速度，p113v系統(tǒng)中的系統(tǒng)中的較小文件較小文件也也采用連續(xù)采用連續(xù)分配方式，如分配方式，如“簇簇”O(jiān)perating SystemOperating SystemPage 62022-1-146.5 文件存儲空間的管理文件存儲空間的管理 6.5.1 空閑表法和空閑鏈表法空閑表法和空閑鏈表法 空閑表法空閑表法屬于連續(xù)分配，系統(tǒng)為外存上的所有空閑區(qū)建立一張空閑表，屬于連續(xù)分配，系統(tǒng)為外存上的所有空閑區(qū)建立一張空閑表，每個空閑區(qū)對應(yīng)一個空閑

5、表項，包括：每個空閑區(qū)對應(yīng)一個空閑表項，包括： 圖圖 6-20 空閑盤塊表空閑盤塊表 序號序號第一空閑盤塊號第一空閑盤塊號空閑盤塊數(shù)空閑盤塊數(shù)12429331554Operating SystemOperating SystemPage 72022-1-14q存儲空間的分配與回收存儲空間的分配與回收 空閑盤區(qū)的分配與內(nèi)存的動態(tài)分配類似，同樣是空閑盤區(qū)的分配與內(nèi)存的動態(tài)分配類似，同樣是采用首次適應(yīng)算法、循環(huán)首次適應(yīng)算法等采用首次適應(yīng)算法、循環(huán)首次適應(yīng)算法等q在系統(tǒng)為某新創(chuàng)建的文件分配空閑盤塊時，先順在系統(tǒng)為某新創(chuàng)建的文件分配空閑盤塊時，先順序地檢索空閑表的各表項，直至找到第一個其大序地檢索空閑表

6、的各表項，直至找到第一個其大小能滿足要求的空閑區(qū)，再將該盤區(qū)分配給用戶小能滿足要求的空閑區(qū)，再將該盤區(qū)分配給用戶(進程進程)，同時修改空閑表。系統(tǒng)在對用戶所釋放，同時修改空閑表。系統(tǒng)在對用戶所釋放的存儲空間進行回收時，也采取類似于內(nèi)存回收的存儲空間進行回收時，也采取類似于內(nèi)存回收的方法，即要考慮回收區(qū)是否與空閑表中插入點的方法，即要考慮回收區(qū)是否與空閑表中插入點的前區(qū)和后區(qū)相鄰接，對相鄰接者應(yīng)予以合并的前區(qū)和后區(qū)相鄰接，對相鄰接者應(yīng)予以合并Operating SystemOperating SystemPage 82022-1-142. 空閑鏈表法空閑鏈表法 將所有空閑盤區(qū)，拉成一條空閑鏈，根

7、據(jù)構(gòu)成鏈所用的將所有空閑盤區(qū)，拉成一條空閑鏈，根據(jù)構(gòu)成鏈所用的基本元素的不同，可把鏈表分成基本元素的不同，可把鏈表分成2種形式：種形式：（1） 將磁盤上所有空閑區(qū)空間，為盤塊為單位拉成一條鏈，將磁盤上所有空閑區(qū)空間，為盤塊為單位拉成一條鏈，當(dāng)用戶因創(chuàng)建文件而請求分配存儲空間時，系統(tǒng)從鏈首開始，當(dāng)用戶因創(chuàng)建文件而請求分配存儲空間時，系統(tǒng)從鏈首開始，依次摘下適當(dāng)數(shù)目的空閑盤塊鏈給用戶。當(dāng)用戶因刪除文件依次摘下適當(dāng)數(shù)目的空閑盤塊鏈給用戶。當(dāng)用戶因刪除文件而釋放存儲空間時，系統(tǒng)將回收的盤塊依次插入空閑盤塊鏈而釋放存儲空間時，系統(tǒng)將回收的盤塊依次插入空閑盤塊鏈的末尾。的末尾。：分配和回收一個盤塊的過程非

8、常簡單。分配和回收一個盤塊的過程非常簡單。：但在為一個文件分配盤塊時，可能要重復(fù)多次操作。但在為一個文件分配盤塊時，可能要重復(fù)多次操作。（2）Operating SystemOperating SystemPage 92022-1-142. 空閑鏈表法空閑鏈表法 將所有空閑盤區(qū)，拉成一條空閑鏈，根據(jù)構(gòu)成鏈所用的將所有空閑盤區(qū)，拉成一條空閑鏈，根據(jù)構(gòu)成鏈所用的基本元素的不同，可把鏈表分成基本元素的不同，可把鏈表分成2種形式：種形式：（1）：分配和回收一個盤塊的過程非常簡單。分配和回收一個盤塊的過程非常簡單。：但在為一個文件分配盤塊時，可能要重復(fù)多次操作。但在為一個文件分配盤塊時，可能要重復(fù)多次操

9、作。（2） 將磁盤上所有空閑盤區(qū)拉成一條鏈，在每個盤區(qū)上包含將磁盤上所有空閑盤區(qū)拉成一條鏈，在每個盤區(qū)上包含若干用于指示下一個空閑盤區(qū)的指針，指明盤區(qū)大小的信息。若干用于指示下一個空閑盤區(qū)的指針，指明盤區(qū)大小的信息。 分配盤塊時，通常采用首次適應(yīng)算法（顯式鏈接法）。分配盤塊時，通常采用首次適應(yīng)算法（顯式鏈接法）。 在回收時，要將回收區(qū)與空閑盤區(qū)相合并。在回收時，要將回收區(qū)與空閑盤區(qū)相合并。Operating SystemOperating SystemPage 102022-1-14q空閑表法和空閑鏈表法空閑表法和空閑鏈表法q位示圖法位示圖法q成組鏈接法成組鏈接法Operating Syste

10、mOperating SystemPage 112022-1-14q位示圖位示圖v用用二進制的一位二進制的一位來表示磁盤中一個盤塊的使用來表示磁盤中一個盤塊的使用情況情況v0表示盤塊空閑，表示盤塊空閑，1表示盤塊已分配表示盤塊已分配v由所有盤塊所對應(yīng)的二進制位構(gòu)成的一個集合由所有盤塊所對應(yīng)的二進制位構(gòu)成的一個集合稱為位示圖，通?？捎梅Q為位示圖，通?？捎胢*n個位數(shù)來構(gòu)成位示個位數(shù)來構(gòu)成位示圖，并使圖，并使m*n等于磁盤總塊數(shù)等于磁盤總塊數(shù)Operating SystemOperating SystemPage 122022-1-14Operating SystemOperating Syste

11、mPage 132022-1-14q盤塊的分配盤塊的分配v順序掃描位示圖，從中找出一個或一組其值為順序掃描位示圖，從中找出一個或一組其值為“0”的二進制位的二進制位(“0”表示空閑時表示空閑時)v將所找到的一個或一組二進制位，將所找到的一個或一組二進制位， 轉(zhuǎn)換成與之轉(zhuǎn)換成與之相應(yīng)的盤塊號。假定找到的其值為相應(yīng)的盤塊號。假定找到的其值為“0”的二進的二進制位，位于位示的第制位，位于位示的第i行、第行、第j列，則其相應(yīng)的列，則其相應(yīng)的盤塊號應(yīng)按下式計算盤塊號應(yīng)按下式計算b = n(i - 1) + jv修改位示圖，修改位示圖， 令令mapi,j=1Operating SystemOperatin

12、g SystemPage 142022-1-14q盤塊的回收盤塊的回收v將回收盤塊的盤塊號轉(zhuǎn)換成位示圖中的行號和列號。將回收盤塊的盤塊號轉(zhuǎn)換成位示圖中的行號和列號。 轉(zhuǎn)換公式為轉(zhuǎn)換公式為i = (b - 1) DIV n + 1j = (b - 1) MOD n + 1v修改位示圖，修改位示圖， 令令map i,j=0 （當(dāng)（當(dāng)“0”表示盤塊空閑時）表示盤塊空閑時）v如上例中，第如上例中，第16號物理塊，可計算得號物理塊，可計算得i = (16 - 1) DIV 16 + 1 = 1j = (16 - 1) MOD 16 + 1 = 16v同理，第同理，第17塊可計算得塊可計算得i = (17

13、 - 1) DIV 16 + 1 = 2j = (17 - 1) MOD 16 + 1 = 1 Operating SystemOperating SystemPage 152022-1-14q空閑表法和空閑鏈表法空閑表法和空閑鏈表法q位示圖法位示圖法q成組鏈接法成組鏈接法Operating SystemOperating SystemPage 162022-1-14q在大型文件系統(tǒng)中，空閑表或空閑鏈表太長，在在大型文件系統(tǒng)中，空閑表或空閑鏈表太長，在UNIX系統(tǒng)中，兩種方法結(jié)合形成系統(tǒng)中，兩種方法結(jié)合形成成組鏈接法成組鏈接法q空閑盤塊的組織空閑盤塊的組織v將將空閑表空閑表和和空閑鏈表空閑鏈表

14、結(jié)合形成的空閑盤塊管理方結(jié)合形成的空閑盤塊管理方法法v空閑盤塊號?？臻e盤塊號棧 用來存放當(dāng)前可用的一組空閑盤塊用來存放當(dāng)前可用的一組空閑盤塊號以及棧中尚有的空閑盤塊數(shù)號以及棧中尚有的空閑盤塊數(shù)Nv文件區(qū)中的所有空閑盤塊被分成若干個組，如文件區(qū)中的所有空閑盤塊被分成若干個組，如100塊塊/組組v將每組含的有盤塊數(shù)和該組所有盤塊號記入前一將每組含的有盤塊數(shù)和該組所有盤塊號記入前一組第一個盤塊中組第一個盤塊中v將第一組的空閑盤塊數(shù)和所有盤塊號記入空閑盤將第一組的空閑盤塊數(shù)和所有盤塊號記入空閑盤塊號棧塊號棧Operating SystemOperating SystemPage 172022-1-14

15、100400399301300100300299-202201299-100400399-20130110007999790179007899-78017999-7901空閑盤塊號?？臻e盤塊號棧S.free019899棧頂棧頂指針指針Operating SystemOperating SystemPage 182022-1-14q設(shè)每設(shè)每100盤塊為盤塊為1組，系統(tǒng)共組，系統(tǒng)共10000個盤塊，從個盤塊，從201至至7999用于文件區(qū)，則第用于文件區(qū)，則第1組為盤塊號組為盤塊號201-300，第，第2組為組為301-400，.，最后一組為，最后一組為7901-7999q每一組的盤塊總數(shù)每一組的

16、盤塊總數(shù)N和盤塊號記入前一組的第一和盤塊號記入前一組的第一個盤塊個盤塊S.free(0)S.free(99)q將第一組盤塊總數(shù)和盤塊號記入空閑盤塊號棧將第一組盤塊總數(shù)和盤塊號記入空閑盤塊號棧q最末一組的最末一組的S.free(0)為為“0”，表示空閑盤塊鏈，表示空閑盤塊鏈結(jié)束結(jié)束Operating SystemOperating SystemPage 192022-1-14q空閑盤塊的分配與回收空閑盤塊的分配與回收v分配分配檢查空閑盤塊號棧是否上鎖，如未上鎖，便檢查空閑盤塊號棧是否上鎖，如未上鎖，便從棧頂取出一空閑盤塊號，將與之對應(yīng)的盤從棧頂取出一空閑盤塊號，將與之對應(yīng)的盤塊分配給用戶，然后將

17、棧頂指針下移一格塊分配給用戶，然后將棧頂指針下移一格若該盤塊號已是棧底，若該盤塊號已是棧底， 即即S.free(0)，這是當(dāng)，這是當(dāng)前棧中最后一個可分配的盤塊號前棧中最后一個可分配的盤塊號調(diào)用磁盤讀過程，將棧底盤塊號所對應(yīng)盤塊調(diào)用磁盤讀過程，將棧底盤塊號所對應(yīng)盤塊的內(nèi)容讀入棧中，作為新的盤塊號棧的內(nèi)容，的內(nèi)容讀入棧中，作為新的盤塊號棧的內(nèi)容，并把原棧底對應(yīng)的盤塊分配出去并把原棧底對應(yīng)的盤塊分配出去分配一相應(yīng)的緩沖區(qū)分配一相應(yīng)的緩沖區(qū)把棧中的空閑盤塊數(shù)減把棧中的空閑盤塊數(shù)減1并返回并返回Operating SystemOperating SystemPage 202022-1-14q空閑盤塊的分

18、配與回收空閑盤塊的分配與回收v回收回收將回收盤塊的盤塊號記入空閑盤塊號棧的將回收盤塊的盤塊號記入空閑盤塊號棧的頂部，并執(zhí)行空閑盤塊數(shù)加頂部，并執(zhí)行空閑盤塊數(shù)加1操作操作當(dāng)棧已滿時，記入新回收的盤塊中，再將當(dāng)棧已滿時，記入新回收的盤塊中，再將其盤塊號作為新棧底其盤塊號作為新棧底Operating SystemOperating SystemPage 212022-1-14q文件和文件系統(tǒng)文件和文件系統(tǒng)q文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)q外存分配方式外存分配方式q目錄管理目錄管理q文件存儲空間的管理文件存儲空間的管理q文件共享與文件保護文件共享與文件保護q數(shù)據(jù)一致性控制數(shù)據(jù)一致性控制Operating

19、 SystemOperating SystemPage 222022-1-14q基于索引結(jié)點的共享方式基于索引結(jié)點的共享方式q利用符號鏈實現(xiàn)文件共享利用符號鏈實現(xiàn)文件共享q文件的保護機制文件的保護機制q磁盤容錯技術(shù)磁盤容錯技術(shù)Operating SystemOperating SystemPage 232022-1-14q 文件共享形式與目的文件共享形式與目的v定義：系統(tǒng)應(yīng)允許多個用戶共享同一份文件，定義：系統(tǒng)應(yīng)允許多個用戶共享同一份文件，在系統(tǒng)中只保留一份共享文件的備份在系統(tǒng)中只保留一份共享文件的備份v共享形式共享形式被多個用戶使用，由存取權(quán)限控制被多個用戶使用，由存取權(quán)限控制被多個程序使用

20、，但各用自己的讀寫指針被多個程序使用，但各用自己的讀寫指針被多個程序使用，但共享讀寫指針被多個程序使用，但共享讀寫指針多個用戶用相同或不同的名字來訪問同一多個用戶用相同或不同的名字來訪問同一文件文件v目的目的: :節(jié)省時間和存儲空間，減少了用戶工作節(jié)省時間和存儲空間，減少了用戶工作量；進程間通過文件交換信息量；進程間通過文件交換信息Operating SystemOperating SystemPage 242022-1-14Operating SystemOperating SystemPage 252022-1-14q文件共享的實現(xiàn)文件共享的實現(xiàn)v建立值班目錄建立值班目錄由系統(tǒng)目錄實現(xiàn)對文

21、件的共享由系統(tǒng)目錄實現(xiàn)對文件的共享用戶通過全路徑名共享地訪問這些文件用戶通過全路徑名共享地訪問這些文件v采用鏈訪技術(shù)采用鏈訪技術(shù)對要共享的文件進行連接對要共享的文件進行連接: : 通過通過“連接（連接（LinkLink）”命令，在用戶自己命令，在用戶自己的目錄項中對要共享的文件建立起相應(yīng)的的目錄項中對要共享的文件建立起相應(yīng)的表目，即建立兩個文件的等價關(guān)系表目，即建立兩個文件的等價關(guān)系Operating SystemOperating SystemPage 262022-1-14q基于索引結(jié)點共享基于索引結(jié)點共享v將諸如文件的物理地址和其它文件屬性等將諸如文件的物理地址和其它文件屬性等信息放在索

22、引結(jié)點中，在文件目錄中只設(shè)信息放在索引結(jié)點中，在文件目錄中只設(shè)置文件名及指向相應(yīng)索引結(jié)點的指針，另置文件名及指向相應(yīng)索引結(jié)點的指針，另外在索引結(jié)點中增加鏈接計數(shù)外在索引結(jié)點中增加鏈接計數(shù)count，表，表示共享的用戶數(shù)，刪除時必須示共享的用戶數(shù)，刪除時必須count=0，方可。方可。Operating SystemOperating SystemPage 272022-1-14Wang用用戶戶文文件件目目錄錄Test rLee用用戶戶文文件件目目錄錄Test rcount 2文文件件物物理理地地址址索索引引結(jié)結(jié)點點Test 基于索引結(jié)點的共享方式基于索引結(jié)點的共享方式 Operating Sy

23、stemOperating SystemPage 282022-1-14C的的目目錄錄owner ccount 1鏈鏈接接前前C的的目目錄錄owner ccount 2鏈鏈接接后后B的的目目錄錄B的的目目錄錄owner ccount 1擁擁有有者者刪刪除除文文件件后后進程進程B鏈接前后的情況鏈接前后的情況 Operating SystemOperating SystemPage 292022-1-14q基于索引結(jié)點的共享方式基于索引結(jié)點的共享方式q利用符號鏈實現(xiàn)文件共享利用符號鏈實現(xiàn)文件共享q文件的保護機制文件的保護機制q磁盤容錯技術(shù)磁盤容錯技術(shù)Operating SystemOperatin

24、g SystemPage 302022-1-14q為使為使B能共享能共享C的一個文件的一個文件F，可以由系統(tǒng)創(chuàng)建一，可以由系統(tǒng)創(chuàng)建一個個LINK類型的新文件類型的新文件，也取名為，也取名為F，以實現(xiàn)，以實現(xiàn)B的的目錄中與文件目錄中與文件F的鏈接。在新文件中只包含被鏈的鏈接。在新文件中只包含被鏈接文件接文件F的路徑名。這種鏈接方法稱為的路徑名。這種鏈接方法稱為符號鏈接符號鏈接（Symbolic Linking）q在利用符號鏈方式實現(xiàn)文件共享時，在利用符號鏈方式實現(xiàn)文件共享時， 只是文件主只是文件主才擁有指向其才擁有指向其索引結(jié)點索引結(jié)點的指針；而共享該文件的的指針；而共享該文件的其他用戶，則只有

25、該文件的路徑名，并不擁有指其他用戶，則只有該文件的路徑名，并不擁有指向其索引結(jié)點的指針向其索引結(jié)點的指針q可用于計算機網(wǎng)絡(luò)上共享文件可用于計算機網(wǎng)絡(luò)上共享文件Operating SystemOperating SystemPage 312022-1-14q符號鏈實現(xiàn)文件共享優(yōu)缺點符號鏈實現(xiàn)文件共享優(yōu)缺點v優(yōu)點：方便地鏈接任一文件（用路徑名）優(yōu)點：方便地鏈接任一文件（用路徑名）v缺點：訪問共享文件時開銷大（多次讀盤，缺點：訪問共享文件時開銷大（多次讀盤，消費盤空間），每一共享文件都要增加一文消費盤空間），每一共享文件都要增加一文件名（因路徑名各不相同件名（因路徑名各不相同）Operating S

26、ystemOperating SystemPage 322022-1-14q基于索引結(jié)點的共享方式基于索引結(jié)點的共享方式q利用符號鏈實現(xiàn)文件共享利用符號鏈實現(xiàn)文件共享q文件的保護機制文件的保護機制q磁盤容錯技術(shù)磁盤容錯技術(shù)Operating SystemOperating SystemPage 332022-1-14q文件保護用于提供安全性的特定的操作系統(tǒng)機文件保護用于提供安全性的特定的操作系統(tǒng)機制制q對擁有權(quán)限的用戶，應(yīng)該讓其進行相應(yīng)操作，對擁有權(quán)限的用戶，應(yīng)該讓其進行相應(yīng)操作，否則，應(yīng)禁止否則，應(yīng)禁止q防止其他用戶冒充對文件進行操作防止其他用戶冒充對文件進行操作q實現(xiàn)實現(xiàn)v用戶驗證用戶驗證

27、v存取控制存取控制Operating SystemOperating SystemPage 342022-1-14q基于索引結(jié)點的共享方式基于索引結(jié)點的共享方式q利用符號鏈實現(xiàn)文件共享利用符號鏈實現(xiàn)文件共享q文件的保護機制文件的保護機制q磁盤容錯技術(shù)磁盤容錯技術(shù)Operating SystemOperating SystemPage 352022-1-14q影響文件安全的主要因素影響文件安全的主要因素v人為因素人為因素v系統(tǒng)因素系統(tǒng)因素v自然因素自然因素q可采取的措施可采取的措施v通過通過存取控制存取控制機制來防止由人為因素所造成機制來防止由人為因素所造成的文件不安全性的文件不安全性v通過通過

28、磁盤容錯技術(shù)磁盤容錯技術(shù)，來防止由磁盤部分的故，來防止由磁盤部分的故障所造成的文件不安全性障所造成的文件不安全性v通過通過“后備系統(tǒng)后備系統(tǒng)”來防止由自然因素所造成來防止由自然因素所造成的不安全性的不安全性O(shè)perating SystemOperating SystemPage 362022-1-14q容錯技術(shù)容錯技術(shù)是通過在系統(tǒng)中是通過在系統(tǒng)中設(shè)置冗余設(shè)置冗余部件的辦法來部件的辦法來提高系統(tǒng)可靠性的一種技術(shù)提高系統(tǒng)可靠性的一種技術(shù)q磁盤容錯技術(shù)也稱為磁盤容錯技術(shù)也稱為系統(tǒng)容錯技術(shù)（系統(tǒng)容錯技術(shù)（System Fault Tolerance, SFT），是通過增加冗余的磁，是通過增加冗余的磁盤驅(qū)動器、磁盤控制器等方法來提高磁盤系統(tǒng)可盤驅(qū)動器、磁盤控制器等方法來提高磁盤系統(tǒng)可靠性的一種技術(shù)靠性的一種技術(shù)qSFT的級別的級別vSFT-I 低級磁盤容錯技術(shù)低級磁盤容錯技術(shù)，防止因磁盤表面發(fā)，防止因磁盤表面發(fā)生缺陷所引起的數(shù)據(jù)丟失生缺陷所引起的數(shù)