磁盤存儲空間的分配和回收

1、實習六磁盤存儲空間的分配和回收一、實習內(nèi)容模擬磁盤空閑空間的表示方法，以及模擬實現(xiàn)磁盤空間的分配和回收。二、實習目的磁盤初始化時把磁盤存儲空間分成許多塊（扇區(qū)） ，這些空間可以被多個用戶共享。用戶作業(yè)在執(zhí)行期間常常要在磁盤上建立文件或把已經(jīng)建立在磁盤上的文件刪去，這就涉及到磁盤存儲空間的分配和回收。一個文件存放到磁盤上，可以組織成順序文件（連續(xù)文件）、鏈接文件（串聯(lián)文件）、索引文件等，因此，磁盤存儲空間的分配有兩種方式，一種是分配連續(xù)的存儲空間， 另一種是可以分配不連續(xù)的存儲空間。怎樣有效地管理磁盤存儲空間是操作系統(tǒng)應解決的一個重要問題，通過本實習使學生掌握磁盤存儲空間的分配和回收算法。三、實

2、習題目本實習模擬三種磁盤存儲空間的管理方法。第一題：連續(xù)的磁盤存儲空間的分配和回收。提示：(1) 要在磁盤上建立順序文件時， 必須把按序排列的邏輯記錄依次存放在磁盤的連續(xù)存儲空間中?？杉俣ù疟P初始化時，已把磁盤存儲空間劃分成若干等長的塊（扇區(qū)），按柱面號和盤面號的順序給每一塊確定一個編號。 隨著文件的建立、 刪除、磁盤存儲空間被分成許多區(qū)（每一區(qū)包含若干塊），有的區(qū)存放著文件，而有的區(qū)是空閑的。當要建立順序文件時必須找到一個合適的空閑區(qū)來存放文件記錄， 當一個文件被刪除時， 則該文件占用的區(qū)應成為空閑區(qū)。為此可用一張空閑區(qū)表來記錄磁盤存儲空間中尚未占用的部分，格式如下：序起始空閑空閑塊個狀號塊

3、號數(shù)態(tài)156未分配2143未分配32130未分配4空表目MMMMMMMM(2)要建立文件時，先查找空閑區(qū)表，從狀態(tài)為 “未分配” 的登記欄目中找出一個塊數(shù)能滿足要求的區(qū)， 由起始空閑塊號能依次推得可使用的其它塊號。若不需要占用該區(qū)的所有塊時， 則剩余的塊仍應為未分配的空閑塊，這時要修改起始空閑塊號和空閑塊數(shù)。若占用了該區(qū)的所有塊，則相應登記欄中的狀態(tài)修改成“空表目”。刪除一個文件時，從空閑區(qū)表中找一個狀態(tài)為“空表目”的登記欄目，把歸還的起始塊號和塊數(shù)填入對應的位置。磁盤存儲空間的分配和回收算法類似于主存儲器的可變分區(qū)方式的分配和回收。同學們可參考實習四的第一題。(3) 當找到空閑塊后， 必須啟

4、動磁盤把信息存放到指定的塊中， 啟動磁盤必須給出由三個參數(shù)組成的物理地址： 柱面號、 磁道號和物理記錄號。 故必須把找到的空閑塊號換算成磁盤的物理地址。為了減少移臂次數(shù)，磁盤上的信息按柱面上各磁道順序存放?，F(xiàn)假定一個盤組共有200個柱面，（編號0-199 ）每個柱面有20 個磁道（編號0-19 ，同一柱面上的各磁道分布在各盤面上，故磁道號即盤面號。），每個磁道被分成等長的6 個物理記錄（編號0-5 ，每個盤面被分成若干個扇區(qū)，故每個磁道上的物理記錄號即為對應的扇區(qū)號。）。那么，空閑塊號與磁盤物理地址的對應關系如下：假設 M=空閑塊號，m= 空閑塊號66則物理記錄號= mM磁道號 = 20柱面號

5、M=20(4) 刪除一個文件時， 從文件目錄表中可得到該文件在磁盤上的起始地址和邏輯記錄個數(shù)，假定每個邏輯記錄占磁盤上的一塊，則可推算出歸還后的起始空閑塊號和塊數(shù)，登記到空閑區(qū)表中。換算關系如下：起始空閑塊號=（柱面號20+磁道號）6+物理記錄號空閑塊數(shù) =邏輯記錄數(shù)(5)請設計磁盤存儲空間的分配和回收程序，要求把分配到的空閑塊轉(zhuǎn)換成磁盤物理地址，把歸還的磁盤空間轉(zhuǎn)換成空閑塊號。假定空閑區(qū)表的初值如提示（1）中指出，現(xiàn)有一文件要占用10 塊，運行你所設計的分配程序， 顯示或打印分配后的空閑區(qū)表以及分配到的磁盤空間的起始物理地址。然后，有一文件被刪除，它占用的磁盤空間為：1 號柱面 2 號磁道，

6、 0 號物理記錄開始的4 塊，運行你所設計的回收程序，顯示或打印回收后的空閑區(qū)表。第二題：用位示圖管理磁盤存儲空間提示：(1) 為了提高磁盤存儲空間的利用率， 可在磁盤上組織成鏈接文件、 索引文件， 這類文件可以把邏輯記錄存放在不連續(xù)的存儲空間。 為了表示哪些磁盤空間已被占用， 哪些磁盤空間是空閑的， 可用位示圖來指出。 位示圖由若干字節(jié)構成， 每一位與磁盤上的一塊對應， “ 1” 狀態(tài)表示相應塊已占用，“ 0”狀態(tài)表示該塊為空閑。位示圖的形式與實習四中的位示圖一樣，但要注意，對于主存儲空間和磁盤存儲空間應該用不同的位示圖來管理，絕不可混用。(2)申請一塊磁盤空間時，由分配程序查位示圖，找出一

7、個為“0”的位，計算出這一位對應塊的磁盤物理地址，且把該位置成占用狀態(tài)“ 1”。假設現(xiàn)在有一個盤組共80 個柱面，每個柱面有兩個磁道， 每個磁道分成 4 個物理記錄。 那么， 當在位示圖中找到某一字節(jié)的某一位為“ 0”時，這個空閑塊對應的磁盤物理地址為：柱面號 =字節(jié)號磁道號 = 位數(shù)4物理記錄號 = 位數(shù)4(3) 歸還一塊磁盤空間時， 由回收程序根據(jù)歸還的磁盤物理地址計算出歸還塊在位示圖中的對應位，把該位置成“ 0”。按照（ 2）中假設的盤組，歸還塊在位示圖中的位置計算如下：字節(jié)號=柱面號位數(shù) =磁道號4+物理記錄號(4)設計申請一塊磁盤空間和歸還一塊磁盤空間的程序。要求能顯示或打印程序運行

8、前和運行后的位示圖；分配時把分配到的磁盤空間的物理地址顯示或打印出來，歸還時把歸還塊對應于位示圖的字節(jié)號和位數(shù)顯示或打印出來。(5) 假定已有如表 6-1 的磁盤空間被占用了， 現(xiàn)在要申請五塊磁盤空間， 運行分配程序，按（ 4）中要求顯示或打印運行的結果。然后再歸還如表6-2 的空間， 運行回收程序， 按（ 4）中的要求顯示或打印運行結果。表 6-1柱面磁道物理記錄號號號001002010013100112表 6-2柱面磁道物理記錄號號號002010101第三題：模擬UNIX系統(tǒng)的空閑塊成組鏈接法，實現(xiàn)磁盤存儲空間的管理。提示：(1) 假定磁盤存儲空間已被劃分成長度為n 的等長塊，共有 M塊可

9、供使用。 UNIX 系統(tǒng)中采用空閑塊成組鏈接的方法來管理磁盤存儲空間，將磁盤中的每N 個空閑塊 （N<M）分成一組， 最后一組可以不足N 塊，每組的第一塊中登記了下一組空閑塊的塊數(shù)和塊號，第一組的塊數(shù)和塊號登記在專用塊中，登記的格式如下：0 空閑塊數(shù) k1 空閑塊號 12 空閑塊號 2MMMMK 空閑塊號 kMMMM當?shù)谝豁梼?nèi)容為“0”時，則第二項起指出的空閑塊是最后一組。(2)現(xiàn)模擬 UNIX 系統(tǒng)的空閑塊成組鏈接，假定共有8 塊可供使用，每3 塊為一組，則空閑塊成組鏈接的初始狀態(tài)為：開始時， 空閑塊號是順序排列的，但經(jīng)若干次的分配和歸還操作后，空閑塊的鏈接就未必按序排列了。用二維數(shù)組

10、A： array 0 M-1 of array0 n-1 來模擬管理磁盤空間，用Ai 表示第 I 塊，第 0 塊 A0 作為專用塊。(3)成組鏈接的分組情況記錄在磁盤物理塊中，為了查找鏈接情況，必須把它們讀入主存，故當磁盤初始化后，系統(tǒng)先將專用塊內(nèi)容復制到主存中。定義一個數(shù)組MA存放專用塊內(nèi)容，即 MA: =A0 。申請一塊磁盤空間時，查MA，從中找出空閑塊號，當一組的空閑塊只剩第一塊時， 則應把該塊中指出的下一組的空閑塊數(shù)和塊號復制到專用塊中，然后把該塊分配給申請者。當一組的空閑塊分配完后則把專用塊內(nèi)容（下一組鏈接情況）復制到主存，再為申請者分配。分配算法如圖6-1 。圖 6-1采用成組鏈接

11、的分配算法(4) 歸還一塊時給出歸還的塊號， 叵當前組不滿規(guī)定塊數(shù)時， 將歸還塊登記入該組； 若當前組已滿， 則另建一新組， 這時歸還塊作為新一組的第一塊， 應把主存中登記的一組鏈接情況 MA復制到歸還塊中，然后在MA重新登記一個新組。歸還一塊的算法如圖6-2 。圖 6-2采用成組鏈接的回收算法(5)設計分配和歸還磁盤空間的程序，能顯示或打印分配的磁盤空間的塊號，在完成一次分配或歸還后能顯示或打印各空閑塊組的情況（各組的空閑塊數(shù)和塊號）。本實習省去了塊號與物理地址之間的轉(zhuǎn)換工作，而在實際的系統(tǒng)中必須進行塊號與物理地址的轉(zhuǎn)換工作。(6) 運行你所設計的程序，假定空閑塊鏈接的初始狀態(tài)如提示（ 2）

12、，現(xiàn)先分配 4 塊，再依次歸還第 2 塊和第 6 塊。把執(zhí)行后分配到的塊號依次顯示或打印出來， 且顯示或打印空閑塊組的情況。在上次執(zhí)行的基礎上繼續(xù)分配3 塊，然后歸還第1 塊，再申請 5 塊，顯示或打印依次分配到的塊號及空閑塊組情況。四、相關數(shù)據(jù)結構及說明struct freeblock int FBbegin;n");elseprintf("分配磁盤成功!n該文件的物理地址：n柱面號 t磁道號 t物理塊號n");printf("->addr_note);%dt%dt%dn",File->addr_cylinder,File->

13、;addr_track,Fileintdeletelfree()建文件n");printf("ttt2.刪除文件n");printf("ttt3.查看磁盤n");printf("ttt4.查看文件n");printf("ttt5.退出n");printf("請選擇：");scanf("%c",&ch);switch(ch)case'1':getmalloc();system("pause");break;case'

14、2':deletelfree();system("pause");break;case'3':dispfree();system("pause");break;case'4':dispfile();system("pause");break;case'5':exit(1);break;default:printf("輸入錯誤 ! 請重新輸入 .n");printf("n");getchar();while(ch!=4);return0;1、

15、題二源代碼：#include<>#include<>voidInitbitmap(intmap88)intcylinder,track,sector;charchoice='Y'printf("初始化位視圖.n");while(choice='y'|choice='Y')printf("柱面號 :");scanf("%d",&cylinder);printf("磁道號:");scanf("%d",&track

16、);printf("物理記錄號:");scanf("%d",&sector);mapcylinder4*track+sector=1;printf("contiune");getchar();scanf("%c",&choice);voidallocate(intmap88)inti,j;intflag=0;intcylinder,track,sector;for(i=0;i<8;i+) for(j=0;j<8;j+) if(mapij=0)mapij=1;flag=1;break;if

17、(flag=1)break;if(flag=1)cylinder=i;track=j/4;sector=j%4;printf("分配到的柱面號、磁道號、物理記錄數(shù)");printf("%dt%dt%d",cylinder,track,sector);printf("n");elseprintf("空間不足，分配失敗!");voidreclaim(intmap88)intcylinder,track,sector;printf("柱面號:");scanf("%d",&c

18、ylinder);printf("磁道號 :");scanf("%d",&track);printf("物理記錄號 :");scanf("%d",&sector);if(mapcylinder4*track+sector=0)printf("此塊為未分配塊！回收出錯！");getchar();elsemapcylinder4*track+sector=0;printf("回收塊對應的字節(jié)號:%4dt位數(shù):%4dn",cylinder,4*track+secto

19、r);voidmain()intbitmap88;inti,j;intor(i=0;i<8;i+)for(j=0;j<8;j+)bitmapij=0;Initbitmap(bitmap);while(1)choice;printf("n請輸入選擇 :");printf("1-分配， 2- 回收， 3-scanf("%d",&choice);case1:allocate(bitmap);break;case2:reclaim(bitmap);break;case3:for(i=0;i<8;i+)顯示位示圖， switch

20、(choice)0-退出 n");for(j=0;j<8;j+)printf("%8d",bitmapij);printf("n");break;case0:exit(0);default:printf("錯誤選擇！ ");break;3、第三題源程序：#include<>int MA4;int/*空閑塊數(shù)組 */A94=3,1,2,3,3,4,5,6,0,0,0,0,0,0,0,0,3,0,7,8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0; /*磁盤空間*/int mark9;/*存

21、放已分配的塊*/int No=0; /*已分配的塊數(shù)void display1()*/ int i,j,temp,count, No=0; if(MA1!=0) i=MA0; printf("ngroup1:");for(j=1;j<=i;j+) printf("%d ",MAj);mark+No=MAj;temp=MA1;count=2;while(Atemp1!=0) printf("ngroup%d:",count); i=Atemp0; for(j=1;j<=i;j+) printf("%d "

22、,Atempj);mark+No=Atempj; count+;temp=Atemp1; printf("ngroup%d:",count); i=Atemp0;for(j=2;j<=i+1;j+)if(Atempj>0)printf("%d",Atempj);mark+No=Atempj;else i=MA0; if(i=1)printf("nThe blocks are all assigned"); else printf("ngroup1:");for(j=2;j<=i;j+) print

23、f("%d ",MAj); mark+No=MAj; void display() /*顯示分組情況*/ int i,j; if(MA0!=0) display1(); else i=MA1; for(j=0;j<=3;j+) MAj=Aij;display1();void assign()/*分配空閑塊*/int s,i;if(MA0>1)/*若該組不止一個空閑塊i=MA0;s=MAi;MA0-;*/printf("nnumber of the block:%d",s);else if(MA0=1)/*只剩一個空閑塊*/if(MA1!=0)

24、/*還有其它空閑塊組*/ s=MA1; for(i=0;i<=3;i+)A0i=Asi;MA0-;printf("nnumber of the block:%d",s);else /* 沒有其它空閑塊組 printf("nThere isn't any space"); return; */else/*當前組已分配完*/ for(i=0;i<=3;i+) MAi=A0i;assign();display();/*顯示分組情況*/void callback()/*回收空閑塊 */int i,j,temp;printf("ninput the No. of the block you want to callback:");scanf("%d",&j);getchar();/*得到待回收的空閑塊號*/for(te