操作系統(tǒng)磁盤管理

1、1 .需求分析（1）設計內(nèi)容和要求（包括原始數(shù)據(jù)、技術參數(shù)、條件、設計要求等） 設計內(nèi)容：1）采用空白文件目錄結構管理磁盤空間，實現(xiàn)磁盤空間的分配和回收；2）采用空白塊成組鏈接結構實現(xiàn)磁盤空間的分配和回收：3）采用位示圖結構實現(xiàn)磁盤空間的分配和回收?；疽螅?）具有創(chuàng)建文件、空間分配、刪除文件、釋放空間等基本功能；2）把文件目錄、磁盤空間管理的數(shù)據(jù)結構變化情況顯示出來。（2）需求分析內(nèi)容1）空白文件目錄是管理磁盤空間的一種方法,該方法將文件存儲設備上的每個連續(xù)空閑 區(qū)看作一個空白文件，系統(tǒng)為所有空白文件單獨建立一個目錄，每個空白文件在這個目錄中占 一個表目.表目的內(nèi)容至少包括第一個空白塊的地

2、址（物理塊號），空白塊的數(shù)目。2）位示圖是另一種常用的管理磁盤空間的方法，該方法通過建立一張位示圖來表示為1 時表示該塊己分配,當某位為0時表示該塊空閑。3）位示圖是利用二進制的一位來表示磁盤中的一個盤塊的使用情況。當其值為“0”時, 表示對應的盤塊空閑；為“1”時，表示己經(jīng)分配。有的系統(tǒng)把“0”作為盤塊已分配的標記, 把“1”作為空閑標志（它們的本質(zhì)上是相同的，都是用一位的兩種狀態(tài)標志空閑和已分配兩 種情況）磁盤上的所有盤塊都有個二進制位與之對應，這樣，由所行盤塊所對應的位構成一 個集合，稱為位示圖。1.1小組分工溫庭棟任務為：采用空白文件目錄結構管理磁盤空間；級子育任務為：采用空白塊成組鏈

3、接結構實現(xiàn)磁盤空間的分配和回收；衛(wèi)虹任務為：采用位示圖結構實現(xiàn)磁盤空間的分配和回收；2.總體設計（1）磁盤存儲空間管理是文件系統(tǒng)的重要內(nèi)容采用空白文件目錄結構管理磁盤空間，實現(xiàn)磁盤空間的分配和回收空白文件目錄法進行 空間分配時，需要建立相關的數(shù)據(jù)結構，記錄目前空白區(qū)域和已使用區(qū)域，假設開始時全部 區(qū)域空閑。當有文件需要存儲時，先檢查空白文件目錄，找到適合區(qū)域立即分配，并修改空9白文件目錄表和己使用區(qū)域分配表。為此需建立兩張表格，分別記錄相關數(shù)據(jù)。插入文件程序流圖如圖27；圖2-1刪除文件流程圖如圖2-2圖2-2（2）采用空白塊成組鏈接結構實現(xiàn)磁盤空間的分配和回收灼于要求將磁盤存儲空間的空閑塊成

4、組鏈接，我們可以設計幾個相應的一維數(shù)組，分別 表示磁盤的各個磁盤，數(shù)組中的元素表示每個磁盤的分塊，分配時，通過查空閑表MA,從中 找出空閑塊號，當一組的空閑塊只剩第一塊時，應把該塊中指出的下一組的空閑塊數(shù)和塊號 乂制到專用塊這，然后把該塊分配給申請者，當一組的空閑塊分配完后則把專用塊內(nèi)容（F 一組鏈接情況）復制到內(nèi)存，再為申請者分配。 回收時，輸入待回收的塊號，查找該塊是 否已被分配，若未分配，退出，否則，當前組不滿規(guī)定塊數(shù)時，將歸還塊登記入該組，若當 前組已滿，則另建一新組，這時歸還塊作為新一組的第一塊，應把內(nèi)存中登記的一組鏈接情 況MAS：制到歸還塊中，然后在MA這重新登記一個新組。1）假

5、定做盤存儲空間已被劃分成長度為n的等長塊，共有M塊可供使用。UNIX系統(tǒng) 采用空閑塊成組鏈接的方法來管理磁盤存儲空間，將磁盤中的每N個空閑塊（NM）分成一 組，最后一組可以不足N塊，每組的第一塊中登記了下一組空閑塊的塊數(shù)和塊號，第一組的塊數(shù)和塊號登記在專用塊中，登記的格式如下:表2-30空閑塊數(shù)k1空閑塊號12空閑塊號2M11MMK空閑塊號kMMMM當?shù)谝豁梼?nèi)容為“0”時，則第二項起指出的空閑塊是最后一組。2）開始時，空閑塊號是順序排列的，但經(jīng)若干次的分配和歸還操作后，空閑塊的鏈接就 未必按序排列了。用二維數(shù)組A： array 。MT of array 0nT來模擬管理磁盤空間， 用A口表示第

6、I塊，第。塊A0作為專用塊。3）成組鏈接的分組情況記錄在磁盤物理塊中，為了查找鏈接情況，必須把它們讀入主存, 故當磁盤初始化后，系統(tǒng)先將專用塊內(nèi)容復制到主存中。定義一個數(shù)組MA存放專用塊內(nèi)容, 即MA=A0。申請一塊磁盤空間時，查MA,從中找出空閑塊號，當一組的空閑塊只剩第一塊 時，則應把該塊中指出的卜一組的空閑塊數(shù)和塊號狂制到專用塊中，然后把該塊分配給申請 者。當一組的空閑塊分配完后則把專用塊內(nèi)容（下一組鏈接情況）復制到主存，再為申請者 分配。4）料還一塊時給出歸還的塊號，若當前組不滿規(guī)定塊數(shù)時，將歸還塊登記入該組：若當 前組已滿，則另建一新組，這時歸還塊作為新一組的第一塊，應把主存中登記的

7、一組鏈接情 況MA更制到歸還塊中，然后在MA重新登記一個新組。（3）采用位示圖結構實現(xiàn)磁盤空間的分配和回收磁盤存儲空間的分配有兩種方式，一種是分配連續(xù)的存儲空間，另一種是可以分配不連續(xù) 的存儲空間。為了表示哪些磁盤空間已被占用，哪些磁盤空間是空閑的，可用位示圖來指出。 位示圖由若干字節(jié)構成，每一位與磁盤上的一塊對應，“1”狀態(tài)表示相應塊已占用，“0” 狀態(tài)表示該塊為空閑。算法流程圖如下:分配流程圖如下圖分4：輸入文件名稱，所占物理塊圖2-1(2)釋放流程圖如圖:2-43,詳細設計1.采用空白文件目錄結構管理磁盤空間，實現(xiàn)磁盤空間的分配和回收文件存儲空間管理是文件系統(tǒng)的重要內(nèi)容。常用的管理思想有

8、空白文件目錄法、空白塊 鏈法和位示圖法。本實臉采用前兩種方法進行空間分配。空白文件目錄法進行空間分配時， 需要建立相關的數(shù)據(jù)結構，記錄目前空白區(qū)域和已使用區(qū)域，假設開始時全部區(qū)域空閑。當 有文件需要存儲時，先檢查空白文件目錄，找到適合區(qū)域立即分配，并修改空白文件目錄表 和已使用區(qū)域分配表。為此需建立兩張表格，分別記錄相關數(shù)據(jù)。表3-1：空白文件目錄表（初始）序號首空白塊號空白塊個數(shù)物理塊號標志0858, 9,10,11,12未分配115415, 16, 17, 18未分配220720,21,22, 23,24,25,26,27未分配330830,31,32, 33, 34, 35,36,37,

9、 38未分配4601360,61, 62, 63, 64, 65, 66,6, 68, 69, 70, 71, 72, 73未分配表3-2；空白文件目錄（中間）文件名首空白塊號空白快個數(shù)物理塊號備注核心代碼int alloc(int applyarea)/為文件分配存儲塊的函數(shù)，磁盤空間的分配int i,tag=0,j=0, flag=l;for( i=0 ; i applyarea & flag=l &freeblockZi. namewtd=NULL)freeblockti. startaddress = freeblock.i. startaddress + applyarea;free

10、blockti. size=freeblocki. size-applyarea;tag=1;/*有滿足條件的空閑區(qū)時，tag置1*/flag=0;freeblockij. namewtd=fname;printf ($ %c. n”, freeblocki. name);return freeblockEi. startaddress-applyarea;|elseif (freeblockEi. state=l & freeblockEi. size=applyarea & flag=l & freeblockli. namewtd=NULL) freeblockEi. startaddr

11、ess = freeblockEi. startaddress + applyarea;freeblockTi, size=freeblocki. size-applyarea;freeblockEi. state=0;flag=0;tag=1;/*有滿足條件的空閑區(qū)時，tag置1*freeblockEi. namewtdj=fnameif (tag二二0)return -1;)void setfree()/實現(xiàn)磁盤空間的回收int i, j, k;char s;printf(輸入要刪除的文件名：/、)；getchar0;scanf (飛c”, &s);for(j=0;j100 ;j+) if

12、(FMenuLj. Fname=s) break; for(i=0;iN;i-H-)(for(k=0;k100;k+)printf(%c %d n”, freeblockti. name, i);if(freeblocki. namek=s) freeblocki. state=l; freeblocki. startaddress=freeblockLi.startaddress - (int)ceil(FMenuj. size*l. 0/100);freeblocki. size=freeblocki. size + (：int)ceil(FMenuj. size*l. 0/100); )

13、void print ()打印輸出表 int i; printfCXn);printf (I序號第一個空白塊連續(xù)空閑塊個數(shù)狀態(tài)I*)； printf(*n*);printf( II)； printf(*n*);for(i=0;iN;i+)printf( |%3d%3d%3d%3d|”,i, freeblockCi. startaddress, freeblock.ij. size, freeblocktij. state); printf(n);printf(*);printf CnO ;guest -qEOz J subuntu:*$ cd Desktopguest-qEOzJSubuntu

14、:*/Desktop$ gcc l.c -Ir -o Rain guest-qEOzJSubuntu:-/Desktop$ ./natn分配前的空白文件目錄：序號第一個空白塊連續(xù)空閑塊個數(shù)狀態(tài)。8 5 1. 1 15 4 1.2 20 7 1.3 30 8 1 66 13每個空閨塊內(nèi)存為lee , e襄示空衰目. 1為可用空塊可選攆服務類型1調(diào)入新的文件2收回文件磁力空間露髓懿黯空表目6可用空塊圖3-3,初始化格式每個仝閑塊內(nèi)存為, e表示仝表目，1為可用仝塊 可選擇圈務類型1國入新的文件2收回文件由總空間 3退出空閑區(qū)狀態(tài);e表示空表目，】為可用空塊請選擇H0券類型1輸入所需出力大?。?5。

15、 分配后的空白文件目錄：輸入文件名:序號第一個空白塊連續(xù)空閑塊個數(shù)狀態(tài)e ie 3 i.2 26 73 3。 8解鮑。請選擇蜀務類駕：b勺返詰泛然肥努類型：2 輸入要刊除的文件名： 楸除后的空白文件目錄：圖3-4：分配磁盤序號第一個空白塊連續(xù)空閑塊個數(shù)狀態(tài)e 8 5 1.1 15 4 1.2 20 7 13 30 8 1 |4 60 13I請選擇服務類型；圖3-5：回收磁盤2.采用空白塊成組鏈接結構實現(xiàn)磁盤空間的分配和回收;(1)假定磁盤存儲空間已被劃分成長度為n的等長塊，共有M塊可供使用。UNIX系統(tǒng)中采用 空閑塊成組鏈接的方法來管理磁盤存儲空間，將磁盤中的每N個空閑塊(NM)分成一組， 最

16、后一組可以不足N塊，每組的第一塊中登記了下一組空閑塊的塊數(shù)和塊號，第一組的塊數(shù) 和塊號登記在專用塊中，登記的格式如下：當?shù)谝豁梼?nèi)容為“0”時，則第二項起指出的空閑塊是最后一組。(2)現(xiàn)模擬UNIX系統(tǒng)的空閑塊成組鏈接，假定共有8塊可供使用，每3塊為一組，則 空閑塊成組鏈接的初始狀態(tài)為：表3-7：初始化空閑快14開始時，空閑塊號是順序排列的，但經(jīng)若干次的分配和歸還操作后，空閑塊的鏈接就未 必按序排列了。用二維數(shù)組A： array O-M-1 of array 。nT來模擬管理磁盤空 間，用Ai表示第I塊，第。塊A0作為專用塊。(3)成組鏈接的分組情況記錄在磁盤物理塊中，為了查找鏈接情況，必須把它

17、們讀入主 存，故當磁盤初始化后，系統(tǒng)先將專用塊內(nèi)容狂制到主存中。定義一個數(shù)組MA存放專用 塊內(nèi)容，即MA: =A0o申請一塊磁盤空間時，查MA,從中找出空閑塊號，當一組的空 閑塊只剩第一塊時，則應把該塊中指出的卜一組的空閑塊數(shù)和塊號更制到專用塊中，然 后把該塊分配給申請者。當一組的空閑塊分配完后則把專用塊內(nèi)容(下一組鏈接情況) 更制到主存，冉者分配。(4)歸還一塊時給出歸還的塊號，且當前組不滿規(guī)定塊數(shù)時，將歸還塊登記入該組：芥 當前組己滿，則另建一新組，這時歸還塊作為新一組的第一塊，應把主存中登記的一組 鏈接情況MA更制到歸還塊中，然后在MA重新登記一個新組。(5)設計分配和歸還磁盤空間的程序

18、，能顯示或打印分配的磁盤空間的塊號，在完成一 次分 配或出還后能顯示或打印各空閑塊組的情況(各組的空閑塊數(shù)和塊號)。本實驗 省去了塊號與物理地址之間的轉(zhuǎn)換工作，而在實際的系統(tǒng)中必須進行塊號與物理地址的 轉(zhuǎn)換工作。(6)運行你所設計的程序，假定空閑塊鏈接的初始狀態(tài)如提示(2),現(xiàn)先分配4塊，再 依次歸還第2塊和第6塊。把執(zhí)行后分配到的塊號依次顯示或打印出來，且顯示或打印 空閑塊組的情況。在上次執(zhí)行的基礎上繼續(xù)分配3塊，然后歸還第1塊，再申請5塊， 顯示或打印依次分配到的塊號及空閑塊組情況。核心代碼IntA9 4 = 3,1,2, 3, 3, 4, 5,6, 0,0, 0,0, 0,0, 0, 0

19、, 3, 0, 7,8, 0, 0, 0, 0, 0,0,0.0, 0, 0, 0. 0, 0, 0, 0, 0; /*磁盤空間*/int mark9 :/*存放已分配的塊*/int No=0;/*已分配的塊數(shù)*/void display!()打印顯示結構 int i, j, temp, count;No=0;if(MAl!=0)i=MA01;printf(n 組 1：t);for(j=l;j=i;j+) printf(*%d;mark+NoZ=MAtj;)temp=MA1;count=2;while (AtempZ1!=0)printf (n 組%d： t , coun:);i=Atemp0

20、;for(j=l;j=i;j+) printf (*%d*, Atemp j)；mark+No=At empZj;count+;temp=Atemp1;)printf (n 組%d： t, count);i=Atemp0;for(j=2;j0)printf (飛dAtempJ j);markI+NoJ =AtempZj;)elsei = MAW;if(i=l)printf(n所有的快都已被分配！“);else printf(n 組 1;for(j=2;j=i;j+) printf(*%d MAj);mark+No=MAl j;)void display0 /*顯示分組情況*/ int i, j

21、;if(MA0!=0)displayl0;elsefor (j=0;j=3;j+) displayl0;int s, i;#void assign0/*分配空閑塊*/*若該組不止一個空閑塊*/ i=MAO;s=MAi;MAO;printf (*n 被分配的塊號：n%dn, s);)else if(MAO=l)/*只剩一個空閑塊*/ if(MAl !=0)/*還有其它空閑塊組*/ s=MAl;for(i=0;i=3;i+)MA0 ;printf (*n被分配的塊號八n%dn”, s);)else/*沒有其它空閑塊組*/printf (n沒有空閑空間！”)；return;)else/*當前組已分配

22、完*/for(i=0;i=3;i+)MAi=A0i;assignO ;)displayO;/*顯示分組情況*/)void callback0/*回收空閑塊*/ int i, j, temp;printf (*n請輸入你想回收的塊號:n);scanf&j);getchar0;/*得到待回收的空閑塊號*/for (temp=l; temp=No; temp+)if(marktemp=j)break;)if(tempNo+l)/*若該空閑塊已在，退出*/ printfCn該塊還未被分配!”)；return;)if(MA03)/*當前組不滿3塊*/i=MA01;MAi+l=j：MA0+;)else/*

23、已有3塊*/for(i=0;i=3;i+)Aji=MAi;MAO=1;MAl=j;)displayO ;/*顯示*/17 guest-muvK2Mubuntu: -/Desktopguest.nuvK2Hubuntu:pwd /tRp/guest-RuvKZMguest-muvK2Mubuntu:*$ cd Desktop guest*muvK2Hubuntu:-/Desktops gcc 321.c 321.c: in function dtsplayl:321.C： 13:12: warning: forRdt *df expects a matching St，arguRent pr t

24、ftt f ( M2 ta );Aguest-RUvK2Hubuntu:*/0esktop$ gcc 321.c guestnuvKPHubuntu:-/Desktops ./a.out 初始鏈接圖為：組1：123組2：456組 3：78請進行相應操作：(流入分配空間,世人L回收空間)：圖38：初始化視圖guest-nuvK2Mubuntu:-/Desktops ./a.out初始鏈接圖為：組1：123組 2：4 56組 3：7 8請進行相應操作：（鍵入、，分配空間，鍵入世，回收空間）: 被分配的塊號：3組 1：12組2：456組 3：78是否維續(xù)操作？（迎入、，維埃，灌入退出）:3-9：分配

25、塊25被分配的塊號: 3是否繼續(xù)操作？（灌入y繼續(xù)，譙入s退出）: y請進行相應操作：（鍍?nèi)耸糠峙淇臻g,鍵入，c，回收空間）: a被分配的塊號：2組1:1組2：456組 3：78是否繼續(xù)操作？（灌入y繼續(xù),灌入（，退出）:國311：分配塊是否繼續(xù)操作？（送入，繼續(xù)，溟入n,退出）:話進行相應操作：（設入“分配空間,鉆入，c,回收空間）:詩摘人你想回收的塊號:12 3 nrj rrrj g gw是否繼續(xù)操作？（濯人繼續(xù)，濯入退出）:圖312：回收塊3 .采用位示圖結構實現(xiàn)磁盤空間的分配和回收（1）為了提高能盤存儲空間的利用率，可在磁盤上組織成鏈接文件、索引文件，這類文件 可以把邏輯記錄存放在不連

26、續(xù)的存儲空間。為了表示哪些磁盤空間己被占用，哪些磁盤空間 是空閑的，可用位示圖來指出。位示圖由若干字節(jié)構成，每一位與磁盤上的一塊對應，“1” 狀態(tài)表示相應塊已占用，“0”狀態(tài)表示該塊為空閑。但要注意，對于主存儲空間和磁盤存儲 空間應該用不同的位示圖來管理，絕不可混用。（2）申請一塊磁盤空間時，由分配程序查位示圖，找出一個為“0”的位，計算出這一位對 應塊的磁盤物理地址，且把該位置成占用狀態(tài)1”。假設現(xiàn)在有一個盤組共8個柱面，每個 柱面有兩個磁道，每個磁道分成4個物理記錄。那么，當在位示圖中找到某一字節(jié)的某一位 為“0”時，這個空閑塊對應的磁盤物理地址為：柱面號一字節(jié)號物理記錄號二 位數(shù)mod4

27、（3）歸還一塊磁盤空間時，由回收程序根據(jù)歸還的磁盤物理地址計算出歸還塊在位示圖中的 對應位，把該位置成“0”。按照（2）中假設的盤組，歸還塊在位示圖中的位置計算如下：字節(jié)號二柱面號位數(shù)二磁道號x4+物理記錄號（4）設計申請一塊磁盤空間和歸還一塊磁盤空間的程序。要求能顯示或打印程序運行前運行 后的位示圖：分配時把分配到的磁盤空間的物理地址顯示或打印出來，歸還時把歸還塊對應 于位示圖的字節(jié)號和位數(shù)顯示或打印出來。源代碼void showbitmap （void） /showbitmap函數(shù)，功能打印位示圖信息printf (當前系統(tǒng)磁盤位示圖(0表示塊可用)：n)；用來和位示圖bitmap相與得到

28、某位的狀態(tài)printf (*第一磁道第二【滋道n);printf ( 。扇區(qū) 1扇區(qū) 2扇區(qū) 3扇區(qū)0扇區(qū) 1扇區(qū) 2扇區(qū) 3 扇區(qū)”)；for( int i = 0 ;ibitmapi);printf(n);system(pause);)void diskallocate (void) diskallocate 函數(shù)，分配物理塊給 (由用戶輸入需要的物理塊數(shù):int neednum;int i ;int busy = 0;char filestor32; 用戶名printf (輸入需要分配的塊數(shù):n);scanf (飛d”, &neednum);printf (檢入文件名：n);scanf

29、(飛s”, filestor);for( i=0;ibitmapi;if( 64-busyneednum )(printf(沒有足夠的空閑磁盤，分配失敗！”)；elseprintf (開始分配.n);for (i=o ： ibitmapi)(/ printf (分配塊物理地址為：第洞個柱面，t第洞個磁道，t第%d個 扇區(qū)n”, i/8+1, i%8/4, (i%8)%4);bitinfo-bitmapi = 1;strcpy(bitinfo-filenameli , filestor);neednum;)if( 0=neednum)break;printf (分配成功！ );showbitma

30、p 0;system(pause);)void diskreturn (void) /回收物理塊char filereturn32;int i;printf (“輸入要回收的文件名.)；scanf (飛s”, filereturn);for( i=O;ifilename _i_) (printf (此文件沒有被分配空間”)；break:else(bitinfo_bitmapi = 0;showbitmap();system(pause*);)G主頁i UbuntuIU創(chuàng)）G， guest-muvK2Mubuntu: */Desktopguest-nuvK2Mubuntu:*$ n組：wd n組

31、l:d: command not foundguest -nuvK2Mubuntu:-$ pwd/trp/guest-nuvK2Mguest nuvK2Mubuntu:*$ cd Desktopguest-nuvKZMubuntu:*/Desktops gcc 3.cguest-muvK2Mubjntu:*/Desktop$ ./a.out1：查看2:分配3：回收4:退出程序*所要執(zhí)行的功圖3J3：初始化圖3-11位示圖TerminatO - gue$t-muvK2M)ubuntu: -/Desktop所要執(zhí)行的功能2喻人需要分配的塊數(shù)：18輸人5件名：weniian開始分配.分配成功！當前系統(tǒng)磁盤位示限（。襄示塊可用主面 1柱面 后心 3柱面 4柱面 S拄面 6柱面 7柱面 sh: 1 sh: 1第一橫道。扇區(qū) 1扇區(qū)2