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

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

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

3、接結(jié)構(gòu)實(shí)現(xiàn)磁盤空間的分配和回收；衛(wèi)虹任務(wù)為：采用位示圖結(jié)構(gòu)實(shí)現(xiàn)磁盤空間的分配和回收；2.總體設(shè)計(jì)（1）磁盤存儲(chǔ)空間管理是文件系統(tǒng)的重要內(nèi)容采用空白文件目錄結(jié)構(gòu)管理磁盤空間，實(shí)現(xiàn)磁盤空間的分配和回收空白文件目錄法進(jìn)行空間分配時(shí)，需要建立相關(guān)的數(shù)據(jù)結(jié)構(gòu)，記錄目前空白區(qū)域和已使用區(qū)域，假設(shè)開始時(shí)全部區(qū)域空閑。當(dāng)有文件需要存儲(chǔ)時(shí)，先檢查空白文件目錄，找到適合區(qū)域立即分配，并修改空白文件目錄表和已使用區(qū)域分配表。為此需建立兩張表格，分別記錄相關(guān)數(shù)據(jù)。插入文件程序流圖 如圖2-1；開始插入文件系統(tǒng)filemenu，filename為文件名，size為文件大小Tag=0freeblocki.size >

4、;= applyarea文件大于空白塊，分配失敗 小于 等于 大于 刪除空閑塊修改空閑目錄的首位號(hào)和空閑塊號(hào) 添加文件確定文件首尾號(hào)，占有塊數(shù)結(jié)束 圖2-1 刪除文件流程圖 如圖2-2開始輸入文件名不存在該文件存在該文件 刪除該文件，調(diào)整空白塊的大小，首位號(hào) 結(jié)束 圖2-2（2）采用空白塊成組鏈接結(jié)構(gòu)實(shí)現(xiàn)磁盤空間的分配和回收對(duì)于要求將磁盤存儲(chǔ)空間的空閑塊成組鏈接，我們可以設(shè)計(jì)幾個(gè)相應(yīng)的一維數(shù)組，分別表示磁盤的各個(gè)磁盤，數(shù)組中的元素表示每個(gè)磁盤的分塊，分配時(shí)，通過查空閑表MA，從中找出空閑塊號(hào)，當(dāng)一組的空閑塊只剩第一塊時(shí)，應(yīng)把該塊中指出的下一組的空閑塊數(shù)和塊號(hào)復(fù)制到專用塊這，然后把該塊分配給申請(qǐng)

5、者，當(dāng)一組的空閑塊分配完后則把專用塊內(nèi)容（下一組鏈接情況）復(fù)制到內(nèi)存，再為申請(qǐng)者分配。 回收時(shí)，輸入待回收的塊號(hào)，查找該塊是否已被分配，若未分配，退出，否則，當(dāng)前組不滿規(guī)定塊數(shù)時(shí)，將歸還塊登記入該組，若當(dāng)前組已滿，則另建一新組，這時(shí)歸還塊作為新一組的第一塊，應(yīng)把內(nèi)存中登記的一組鏈接情況MA復(fù)制到歸還塊中，然后在MA這重新登記一個(gè)新組。1） 假定磁盤存儲(chǔ)空間已被劃分成長(zhǎng)度為n的等長(zhǎng)塊，共有M塊可供使用。UNIX系統(tǒng)采用空閑塊成組鏈接的方法 來管理磁盤存儲(chǔ)空間，將磁盤中的每N個(gè)空閑塊（N<M）分成一組，最后一組可以不足N塊，每組的第一塊中登記了下一組空閑塊的塊數(shù)和塊號(hào)，第一組的塊數(shù)和塊號(hào)登記

6、在專用塊中，登記的格式如下： 表2-30空閑塊數(shù)k1空閑塊號(hào)12空閑塊號(hào)2MMMMK空閑塊號(hào)kMMMM當(dāng)?shù)谝豁?xiàng)內(nèi)容為“0”時(shí)，則第二項(xiàng)起指出的空閑塊是最后一組。2)開始時(shí)，空閑塊號(hào)是順序排列的，但經(jīng)若干次的分配和歸還操作后，空閑塊的鏈接就未必按序排列了。用二維數(shù)組A：array 0M-1 of array 0n-1來模擬管理磁盤空間，用Ai表示第I塊，第0塊A0作為專用塊。3) 成組鏈接的分組情況記錄在磁盤物理塊中，為了查找鏈接情況，必須把它們讀入主存，故當(dāng)磁盤初始化后，系統(tǒng)先將專用塊內(nèi)容復(fù)制到主存中。定義一個(gè)數(shù)組MA存放專用塊內(nèi)容，即MA =A0。申請(qǐng)一塊磁盤空間時(shí)，查MA，從中找出空閑塊號(hào)

7、，當(dāng)一組的空閑塊只剩第一塊時(shí)，則應(yīng)把該塊中指出的下一組的空閑塊數(shù)和塊號(hào)復(fù)制到專用塊中，然后把該塊分配給申請(qǐng)者。當(dāng)一組的空閑塊分配完后則把專用塊內(nèi)容（下一組鏈接情況）復(fù)制到主存，再為申請(qǐng)者分配。4) 歸還一塊時(shí)給出歸還的塊號(hào)，若當(dāng)前組不滿規(guī)定塊數(shù)時(shí)，將歸還塊登記入該組；若當(dāng)前組已滿，則另建一新組，這時(shí)歸還塊作為新一組的第一塊，應(yīng)把主存中登記的一組鏈接情況MA復(fù)制到歸還塊中，然后在MA重新登記一個(gè)新組。(3)采用位示圖結(jié)構(gòu)實(shí)現(xiàn)磁盤空間的分配和回收磁盤存儲(chǔ)空間的分配有兩種方式，一種是分配連續(xù)的存儲(chǔ)空間，另一種是可以分配不連續(xù)的存儲(chǔ)空間。為了表示哪些磁盤空間已被占用，哪些磁盤空間是空閑的，可用位示圖來

8、指出。位示圖由若干字節(jié)構(gòu)成，每一位與磁盤上的一塊對(duì)應(yīng)，“1”狀態(tài)表示相應(yīng)塊已占用，“0”狀態(tài)表示該塊為空閑。算法流程圖如下：分配流程圖如下圖2-4：開始輸入文件名稱，所占物理塊文件大于空白塊，分配失敗64-busy<neednum分配成功結(jié)束 圖2-4(2)釋放流程圖如圖：2-4開始輸入文件名不存在該文件存在該文件 刪除該文件，調(diào)整空白塊的大小，首位號(hào) 結(jié)束 圖2-43.詳細(xì)設(shè)計(jì)1.采用空白文件目錄結(jié)構(gòu)管理磁盤空間，實(shí)現(xiàn)磁盤空間的分配和回收文件存儲(chǔ)空間管理是文件系統(tǒng)的重要內(nèi)容。常用的管理思想有空白文件目錄法、空白塊鏈法和位示圖法。本實(shí)驗(yàn)采用前兩種方法進(jìn)行空間分配?？瞻孜募夸浄ㄟM(jìn)行空間分

9、配時(shí)，需要建立相關(guān)的數(shù)據(jù)結(jié)構(gòu)，記錄目前空白區(qū)域和已使用區(qū)域，假設(shè)開始時(shí)全部區(qū)域空閑。當(dāng)有文件需要存儲(chǔ)時(shí)，先檢查空白文件目錄，找到適合區(qū)域立即分配，并修改空白文件目錄表和已使用區(qū)域分配表。為此需建立兩張表格，分別記錄相關(guān)數(shù)據(jù)。表3-1；空白文件目錄表（初始）序號(hào)首空白塊號(hào)空白塊個(gè)數(shù)物理塊號(hào)標(biāo)志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,38未分配4601360,61,62,63,64,65,66,6,68,69,70,71,72,73未分配表3-2；空白

10、文件目錄（中間）文件名首空白塊號(hào)空白快個(gè)數(shù)物理塊號(hào)備注核心代碼int alloc(int applyarea)/為文件分配存儲(chǔ)塊的函數(shù)，磁盤空間的分配 int i,tag=0,j=0,flag=1; for( i=0 ; i< N ; i+ ) if(freeblocki.state=1 && freeblocki.size > applyarea && flag=1 && wtd=NULL) freeblocki.startaddress = freeblocki.startaddress + appl

11、yarea; freeblocki.size=freeblocki.size-applyarea; tag=1;/*有滿足條件的空閑區(qū)時(shí)，tag置1*/ flag=0; wtd=fname; printf("$ %c/n",); return freeblocki.startaddress-applyarea; else if(freeblocki.state=1 && freeblocki.size=applyarea && flag=1 && freeblocki

12、.namewtd=NULL) freeblocki.startaddress = freeblocki.startaddress + applyarea; freeblocki.size=freeblocki.size-applyarea; freeblocki.state=0; flag=0; tag=1;/*有滿足條件的空閑區(qū)時(shí)，tag置1* wtd=fname if(tag=0) return -1;void setfree()/實(shí)現(xiàn)磁盤空間的回收 int i,j,k; char s; printf("輸入要?jiǎng)h除的文件名: /n"); g

13、etchar(); scanf("%c",&s); for(j=0;j<100 ;j+) if(FMenuj.Fname=s) break; for(i=0;i<N;i+) for(k=0;k<100;k+) printf("$ %c %d/n",,i); if(k=s) freeblocki.state=1; freeblocki.startaddress=freeblocki.startaddress - (int)ceil(FMenuj.size*1.0/100)

14、 ; freeblocki.size=freeblocki.size + (int)ceil(FMenuj.size*1.0/100) ; void print()/打印輸出表 int i; printf("n");printf(" |序號(hào).第一個(gè)空白塊.連續(xù)空閑塊個(gè)數(shù).狀態(tài).|"); printf("n"); printf(" |.|"); printf("n"); for(i=0;i<N;i+) printf(" |%3d.%3d.%3d.%3d.|", i,fre

15、eblocki.startaddress,freeblocki.size,freeblocki.state); printf("n"); printf(" |.|"); printf("n"); 圖3-3；初始化格式圖3-4；分配磁盤圖3-5；回收磁盤2.采用空白塊成組鏈接結(jié)構(gòu)實(shí)現(xiàn)磁盤空間的分配和回收；(1) 假定磁盤存儲(chǔ)空間已被劃分成長(zhǎng)度為n的等長(zhǎng)塊，共有M塊可供使用。UNIX系統(tǒng)中采用空閑塊成組鏈接的方法 來管理磁盤存儲(chǔ)空間，將磁盤中的每N個(gè)空閑塊（N<M）分成一組，最后一組可以不足N塊，每組的第一塊中登記了下一組空閑塊的塊

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

17、中，為了查找鏈接情況，必須把它們讀入主存，故當(dāng)磁盤初始化后，系統(tǒng)先將專用塊內(nèi)容復(fù)制到主存中。定義一個(gè)數(shù)組MA存放專用塊內(nèi)容，即MA: =A0。申請(qǐng)一塊磁盤空間時(shí)，查MA，從中找出空閑塊號(hào)，當(dāng)一組的空閑塊只剩第一塊時(shí)，則應(yīng)把該塊中指出的下一組的空閑塊數(shù)和塊號(hào)復(fù)制到專用塊中，然后把該塊分配給申請(qǐng)者。當(dāng)一組的空閑塊分配完后則把專用塊內(nèi)容（下一組鏈接情況）復(fù)制到主存，再者分配。(4) 歸還一塊時(shí)給出歸還的塊號(hào)，且當(dāng)前組不滿規(guī)定塊數(shù)時(shí)，將歸還塊登記入該組；若當(dāng)前組已滿，則另建一新組，這時(shí)歸還塊作為新一組的第一塊，應(yīng)把主存中登記的一組鏈接情況MA復(fù)制到歸還塊中，然后在MA重新登記一個(gè)新組。(5) 設(shè)計(jì)分配

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

19、8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0; /*磁盤空間*/int mark9; /*存放已分配的塊*/int No=0; /*已分配的塊數(shù)*/void display1()/打印顯示結(jié)構(gòu) int i,j,temp,count; No=0; if(MA1!=0) i=MA0; printf("n組1:t"); for(j=1;j<=i;j+) printf("%d ",MAj); mark+No=MAj; temp=MA1; count=2; while(Atemp1!=0) printf("n組%d:t&quo

20、t;,count); i=Atemp0; for(j=1;j<=i;j+) printf("%d ",Atempj); mark+No=Atempj; count+; temp=Atemp1; printf("n組%d:t",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("n所有的快都已被分配！"); else pr

21、intf("n組1:"); for(j=2;j<=i;j+) printf("%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) /*若該組不止一個(gè)空閑塊*/ i=MA0; s=MAi; MA0-; printf("n被分配的塊號(hào):n

22、%dn",s); else if(MA0=1) /*只剩一個(gè)空閑塊*/ if(MA1!=0) /*還有其它空閑塊組*/ s=MA1; for(i=0;i<=3;i+) A0i=Asi; MA0-; printf("n被分配的塊號(hào):n%dn",s); else /*沒有其它空閑塊組*/ printf("n沒有空閑空間！"); return; else /*當(dāng)前組已分配完*/ for(i=0;i<=3;i+) MAi=A0i; assign(); display(); /*顯示分組情況*/ void callback() /*回收空閑塊

23、*/ int i,j,temp; printf("n請(qǐng)輸入你想回收的塊號(hào):n"); scanf("%d",&j); getchar(); /*得到待回收的空閑塊號(hào)*/ for(temp=1;temp<=No;temp+) if(marktemp=j) break; if(temp<No+1) /*若該空閑塊已在，退出*/ printf("n該塊還未被分配!"); return; if(MA0<3) /*當(dāng)前組不滿3塊*/ i=MA0; MAi+1=j; MA0+; else /*已有3塊*/ for(i=0;

24、i<=3;i+) Aji=MAi; MA0=1; MA1=j; display(); /*顯示*/ 圖3-8：初始化視圖圖3-9：分配塊圖3-11：分配塊圖3-12：回收塊3.采用位示圖結(jié)構(gòu)實(shí)現(xiàn)磁盤空間的分配和回收（1）為了提高磁盤存儲(chǔ)空間的利用率，可在磁盤上組織成鏈接文件、索引文件，這類文 件可以把邏輯記錄存放在不連續(xù)的存儲(chǔ)空間。為了表示哪些磁盤空間已被占用，哪些磁盤空間是空閑的，可用位示圖來指出。位示圖由若干字節(jié)構(gòu)成，每一位與磁盤上的一塊對(duì)應(yīng)，“1”狀態(tài)表示相應(yīng)塊已占用，“0”狀態(tài)表示該塊為空閑。但要注意，對(duì)于主存儲(chǔ)空間和磁盤存儲(chǔ)空間應(yīng)該用不同的位示圖來管理，絕不可混用。（2）申請(qǐng)一

25、塊磁盤空間時(shí)，由分配程序查位示圖，找出一個(gè)為“0”的位，計(jì)算出這一位對(duì)應(yīng)塊的磁盤物理地址，且把該位置成占用狀態(tài)“1”。假設(shè)現(xiàn)在有一個(gè)盤組共8個(gè)柱面，每個(gè)柱面有兩個(gè)磁道，每個(gè)磁道分成4個(gè)物理記錄。那么，當(dāng)在位示圖中找到某一字節(jié)的某一位為“0”時(shí)，這個(gè)空閑塊對(duì)應(yīng)的磁盤物理地址為：柱面號(hào)=字節(jié)號(hào)位數(shù)4磁道號(hào)= 物理記錄號(hào)= 位數(shù)mod4（3）歸還一塊磁盤空間時(shí)，由回收程序根據(jù)歸還的磁盤物理地址計(jì)算出歸還塊在位示圖中的對(duì)應(yīng)位，把該位置成“0”。按照（2）中假設(shè)的盤組，歸還塊在位示圖中的位置計(jì)算如下：字節(jié)號(hào)=柱面號(hào)位數(shù)=磁道號(hào)´4+物理記錄號(hào)（4）設(shè)計(jì)申請(qǐng)一塊磁盤空間和歸還一塊磁盤空

26、間的程序。要求能顯示或打印程序運(yùn)行前運(yùn)行后的位示圖；分配時(shí)把分配到的磁盤空間的物理地址顯示或打印出來，歸還時(shí)把歸還塊對(duì)應(yīng)于位示圖的字節(jié)號(hào)和位數(shù)顯示或打印出來。源代碼void showbitmap(void) /showbitmap函數(shù)，功能打印位示圖信息 printf("當(dāng)前系統(tǒng)磁盤位示圖（0表示塊可用）：n"); /用來和位示圖bitmap相與得到某位的狀態(tài) printf(" 第一磁道 第二磁道n"); printf(" 0扇區(qū) 1扇區(qū) 2扇區(qū) 3扇區(qū) 0扇區(qū) 1扇區(qū) 2扇區(qū) 3扇區(qū)") ; for( int i = 0 ;i<

27、;COUNT;i+) if( 0=i%8) printf("n"); printf("%d柱面",(i+1)/8); printf(" %dt",bitinfo->bitmapi); printf("n"); system("pause");void diskallocate(void) /diskallocate函數(shù)，分配物理塊給 /由用戶輸入需要的物理塊數(shù)： int neednum; int i ; int busy = 0; char filestor32; /用戶名 printf(

28、"輸入需要分配的塊數(shù):n"); scanf("%d",&neednum); printf("輸入文件名:n"); scanf("%s",filestor); for( i=0;i<COUNT;i+) /統(tǒng)計(jì)已占用的物理塊 busy =busy + bitinfo->bitmapi; if( 64-busy<neednum ) printf("沒有足夠的空閑磁盤，分配失敗！"); else printf("開始分配.n"); for(i=0 ; i<COUNT; i+) if( 0=bitinfo->bitmapi) / printf("分配塊物理地址為:第%d個(gè)柱面，t第%d個(gè)磁道,t第%d個(gè)扇區(qū)n",i/8+1,i%8/4,(i%8)%4); bitinfo->bitmapi = 1; strcpy(bitinfo->filenamei , filestor); neednum-; if( 0=neednum) break; printf("分配成功！n"); showbitmap(); system("pause&q