模擬UNIX系統(tǒng)成組鏈接法 實現(xiàn)磁盤存儲空間的管理

1、要求：模擬UNIX系統(tǒng)的空閑塊成組鏈接法，實現(xiàn)磁盤存儲空間的管理。提示：(1) 假定磁盤存儲空間已被劃分成長度為n的等長塊，共有M塊可供使用。UNIX系統(tǒng)中采用空閑塊成組鏈接的方法 來管理磁盤存儲空間，將磁盤中的每N個空閑塊（NM）分成一組，最后一組可以不足N塊，每組的第一塊中登記了下一組空閑塊的塊數(shù)和塊號，第一組的塊數(shù)和塊號登記在專用塊中，登記的格式如下：0空閑塊數(shù)k1空閑塊號12空閑塊號2MMMMK空閑塊號kMMMM當?shù)谝豁梼?nèi)容為“0”時，則第二項起指出的空閑塊是最后一組。(2) 現(xiàn)模擬UNIX系統(tǒng)的空閑塊成組鏈接，假定共有8塊可供使用，每3塊為一組，則空閑塊成組鏈接的初始狀態(tài)為：開始時，

2、空閑塊號是順序排列的，但經(jīng)若干次的分配和歸還操作后，空閑塊的鏈接就未必按序排列了。用二維數(shù)組A：array 0M-1 of array 0n-1來模擬管理磁盤空間，用Ai表示第I塊，第0塊A0作為專用塊。(3) 成組鏈接的分組情況記錄在磁盤物理塊中，為了查找鏈接情況，必須把它們讀入主存，故當磁盤初始化后，系統(tǒng)先將專用塊內(nèi)容復(fù)制到主存中。定義一個數(shù)組MA存放專用塊內(nèi)容，即MA: =A0。申請一塊磁盤空間時，查MA，從中找出空閑塊號，當一組的空閑塊只剩第一塊時，則應(yīng)把該塊中指出的下一組的空閑塊數(shù)和塊號復(fù)制到專用塊中，然后把該塊分配給申請者。當一組的空閑塊分配完后則把專用塊內(nèi)容（下一組鏈接情況）復(fù)制

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

4、鏈接的初始狀態(tài)如提示（2），現(xiàn)先分配4塊，再依次歸還第2塊和第6塊。把執(zhí)行后分配到的塊號依次顯示或打印出來，且顯示或打印空閑塊組的情況。實驗報告設(shè)計者日期測試者日期功能描述模擬UNIX系統(tǒng)的空閑塊成組鏈接法，實現(xiàn)磁盤存儲空間的管理。算法描述或流程圖1. 基本思想： 首先定義磁盤分配數(shù)組并初始化，9個一維數(shù)組分別表示9個空閑塊，程序運行時，先將專用塊A0復(fù)制到內(nèi)存中，然后進行功能選擇，分配時，查MA，從中找出空閑塊號，當一組的空閑塊只剩第一塊時，應(yīng)把該塊中指出的下一組的空閑塊數(shù)和塊號復(fù)制到專用塊這，然后把該塊分配給申請者，當一組的空閑塊分配完后則把專用塊內(nèi)容（下一組鏈接情況）復(fù)制到內(nèi)存，再為申請

5、者分配。 回收時，輸入待回收的塊號，查找該塊是否已被分配，若未分配，退出，否則，當前組不滿規(guī)定塊數(shù)時，將歸還塊登記入該組，若當前組已滿，則另建一新組，這時歸還塊作為新一組的第一塊，應(yīng)把內(nèi)存中登記的一組鏈接情況MA復(fù)制到歸還塊中，然后在MA這重新登記一個新組。顯示分組情況。 2. 程序流程： 建立磁盤分配并初始化 調(diào)用功能選擇函數(shù)進行分配或回收操作。3. 數(shù)據(jù)結(jié)構(gòu)及各子程序（1）int MA4; /*空閑塊數(shù)組*/（2）int 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; /*磁盤空間*

6、/（3）int mark9; /*存放已分配的塊*/int No=0; /*已分配的塊數(shù)*/（4）void display( )：顯示分組情況 形參：無 返回參數(shù)：無；（5）void assign( )：分配空閑塊 形參：無 返回參數(shù)：無；（6）void callback( )：回收空閑塊 形參：無 返回參數(shù)：無；（7）void menu( )：功能選擇函數(shù) 形參：無 返回參數(shù)：無；附：源程序#includeint MA4; /*空閑塊數(shù)組*/int 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

7、,0,0; /*磁盤空間*/int mark9; /*存放已分配的塊*/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 ,Atempj); mark+No=Atemp

8、j; count+; temp=Atemp1; printf(ngroup%d:,count); i=Atemp0; for(j=2;j0) 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+) printf(%d ,MAj); mark+No=MAj; void display() /*顯示分組情況*/ int i,j; if(MA0!=0) display1(); else i=M

9、A1; for(j=0;j1) /*若該組不止一個空閑塊*/ i=MA0; s=MAi; MA0-; printf(nnumber of the block:%d,s); else if(MA0=1) /*只剩一個空閑塊*/ if(MA1!=0) /*還有其它空閑塊組*/ s=MA1; for(i=0;i=3;i+) A0i=Asi; MA0-; printf(nnumber of the block:%d,s); else /*沒有其它空閑塊組*/ printf(nThere isnt any space); return; else /*當前組已分配完*/ for(i=0;i=3;i+)

10、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(temp=1;temp=No;temp+) if(marktemp=j) break; if(tempNo+1) /*若該空閑塊已在，退出*/ printf(nThe block is in the disk); return; i

11、f(MA03) /*當前組不滿3塊*/ i=MA0; MAi+1=j; MA0+; else /*已有3塊*/ for(i=0;i=3;i+) Aji=MAi; MA0=1; MA1=j; display(); /*顯示*/ void menu() /*功能選擇函數(shù)*/ int choice; char judge; printf(ninput your choice:(1-assign,2-callback):); scanf(%d,&choice); getchar(); if(choice=1) assign(); else if(choice=2) callback(); else printf(ninvalid command!); printf(ncontinue or not?(y-Yes,n-Not):); scanf(%c,&judg