磁盤存儲(chǔ)空間的分配和回收

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

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

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

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

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

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

7、對(duì)應(yīng)塊的磁盤物理地址，且把該位置成占用狀態(tài)“ 1”。假設(shè)現(xiàn)在有一個(gè)盤組共80 個(gè)柱面，每個(gè)柱面有兩個(gè)磁道， 每個(gè)磁道分成 4 個(gè)物理記錄。 那么， 當(dāng)在位示圖中找到某一字節(jié)的某一位為“ 0”時(shí)，這個(gè)空閑塊對(duì)應(yīng)的磁盤物理地址為：柱面號(hào) =字節(jié)號(hào)磁道號(hào) = 位數(shù)4物理記錄號(hào) = 位數(shù)4(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)一塊磁盤空間和歸還一塊磁盤空間的程序。要求能顯示或打印程序運(yùn)行前.和運(yùn)行后的位示圖；分配

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

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

10、來模擬管理磁盤空間，用 Ai 表示第 I 塊，第 0 塊 A0 作為專用塊。(3) 成組的分組情況記錄在磁盤物理塊中，為了查找情況， 必須把它們讀入主存， 故當(dāng)磁盤初始化后，系統(tǒng)先將專用塊容復(fù)制到主存中。定義一個(gè)數(shù)組MA存放專用塊容，即MA:=A0 。申請(qǐng)一塊磁盤空間時(shí)，查 MA，從中找出空閑塊號(hào)，當(dāng)一組的空閑塊只剩第一塊時(shí)，則應(yīng)把該塊中指出的下一組的空閑塊數(shù)和塊號(hào)復(fù)制到專用塊中，然后把該塊分配給申請(qǐng)者。當(dāng)一組的空閑塊分配完后則把專用塊容（下一組情況）復(fù)制到主存，再為申請(qǐng)者分配。分配算法如圖6-1 。圖 6-1采用成組的分配算法.(4) 歸還一塊時(shí)給出歸還的塊號(hào)， 叵當(dāng)前組不滿規(guī)定塊數(shù)時(shí)， 將

11、歸還塊登記入該組； 若當(dāng)前組已滿， 則另建一新組， 這時(shí)歸還塊作為新一組的第一塊，應(yīng)把主存中登記的一組情況MA復(fù)制到歸還塊中，然后在MA重新登記一個(gè)新組。歸還一塊的算法如圖6-2 。圖 6-2采用成組的回收算法(5)設(shè)計(jì)分配和歸還磁盤空間的程序，能顯示或打印分配的磁盤空間的塊號(hào)，在完成一次分配或歸還后能顯示或打印各空閑塊組的情況 （各組的空閑塊數(shù)和塊號(hào)） 。本實(shí)習(xí)省去了塊號(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)依次顯示或打印出來

12、， 且顯示或打印空閑塊組的情況。在上次執(zhí)行的基礎(chǔ)上繼續(xù)分配 3 塊，然后歸還第 1 塊，再申請(qǐng) 5 塊，顯示或打印依次分配到的塊號(hào)及空閑塊組情況。四、相關(guān)數(shù)據(jù)結(jié)構(gòu)及說明struct freeblock int FBbegin;/起始空閑塊號(hào)int num;/空閑塊數(shù)char state;/狀態(tài)struct freeblock *next; struct filetowrite char name10;/文件名int size;/文件大小int addr_cylinder;/裝入磁盤的首地址_柱面號(hào)int addr_track;/裝入磁盤的首地址_磁道號(hào)int addr_note;/裝入磁盤的首

13、地址_物理記錄號(hào)struct filetowrite *next; .六、源代碼及注釋1、題一源代碼：#include<stdlib.h>#include<stdio.h>int getmalloc()/分配磁盤空間int flag=0;struct freeblock *p=FBhead;struct filetowrite *File;File=(struct filetowrite *)malloc(sizeof(struct filetowrite);printf("輸入要裝入的文件名：");scanf("%s",File

14、->name);printf("輸入所需的磁盤空間大?。?quot;);scanf("%d",&File->size);for(p=FBhead->next;p!=NULL;p=p->next)if(File->size)<=(p->num)/分配空間flag=1;File->addr_cylinder=(p->FBbegin)/6)/20;File->addr_track=(p->FBbegin)/6)%20;File->addr_note=(p->FBbegin)%6;Fil

15、e->next=Filehead->next;/加入文件鏈表Filehead->next=File;if(File->size)<(p->num)/修改該快的 起始地址和塊數(shù)p->FBbegin=p->FBbegin+File->size;p->num=p->num-File->size;else p->state='U'break;if(flag=0)printf("抱歉 ! 目前沒有足夠的磁盤空間分配給該文件.n");elseprintf("分配磁盤成功!n該文件的物

16、理地址：n柱面號(hào) t磁道號(hào) t物理塊號(hào)n ");printf(" %dt %dt %dn",File->addr_cylinder,File->addr_track,File->addr _note); int deletelfree()/回收磁盤空間char name10;int flag=0;struct filetowrite *p;printf("輸入要?jiǎng)h除的文件名：");scanf("%s",&name);for(p=Filehead;p->next!=NULL;p=p->ne

17、xt)if(strcmp(p->next->name,name)=0)/找到該文件flag=1;int funion=0,nunion=0;int m=p->next->addr_cylinder;int n=p->next->addr_track;.int k=p->next->addr_note;int addr=(m*20+n)*6+k;/起始空閑塊號(hào)int tail=p->next->size+addr;struct freeblock *pnode,*qnode,*tnode,*snode;pnode=FBhead->

18、next;while(pnode!=NULL)/先考慮和后面的部分或許有合并的情況if(pnode->FBbegin)=tail)pnode->FBbegin=addr;pnode->num=pnode->num+p->next->size;nunion=1;break;pnode=pnode->next;qnode=FBhead->next;while(qnode!=NULL)/再考慮是否和前面的可以合并if(qnode->FBbegin+qnode->num)=addr)if(nunion=0)qnode->num=qnod

19、e->num+p->next->size;funion=1;break;elseqnode->num=qnode->num+pnode->num; t node=FBhead;while(tnode->next!=pnode)tnode=tnode->next;tnode->next=pnode->next;free(pnode);funion=1;break;qnode=qnode->next;if(funion=0&&nunion=0)/若沒有和前面的或后面的進(jìn)行合并，則新建一個(gè)表目snode=(struct

20、 freeblock *)malloc(sizeof(struct freeblock);snode->FBbegin=addr;snode->num=p->next->size;snode->state='F'if(FBhead->next=NULL)FBhead->next=snode;snode->next=NULL;else.snode->next=FBhead->next;FBhead->next=snode;struct filetowrite *q;q=p->next;/除該文件p->n

21、ext=p->next->next;free(q);break;if(flag=0)printf("沒有該文件 !n");else printf("文件刪除成功 !n"); int dispfree()/顯示磁盤空閑區(qū)表int i=1;struct freeblock *p=FBhead;printf("n磁盤空閑區(qū)表n");printf(" 序號(hào) t 起始空閑塊號(hào) t 空閑塊個(gè)數(shù) t 狀態(tài) n"); for(p=FBhead->next;p!=NULL;p=p->next) if(p-&g

22、t;state)='F')printf(" %dt%dtt%dtt未分配n",i+,p->FBbegin,p->num);elseprintf(" %dttttt空表目 n",i+); int dispfile()char name10;struct filetowrite *p=Filehead;printf("輸入要查看的文件名：");scanf("%s",&name);for(p=Filehead->next;p!=NULL;p=p->next)if(strcm

23、p(p->name,name)=0)printf(" 該文件的物理地址： n 柱面號(hào) t 磁道號(hào) t 物理塊號(hào) n "); printf(" %dt %dt %dn",p->addr_cylinder,p->addr_track,p->addr_note);break;if(p=NULL)printf("沒有該文件 !n"); int main() int n,i,AMAX,BMAX;/AMAX表示起始空閑塊號(hào)，BMAX表示空閑塊個(gè)數(shù)char ch;struct freeblock *pnew;FBhead=(

24、struct freeblock *)malloc(sizeof(struct freeblock);FBhead->next=NULL;printf("輸入磁盤空閑區(qū)個(gè)數(shù)：");scanf("%d",&n);for(i=1;i<=n;i+)pnew=(struct freeblock *)malloc(sizeof(struct freeblock);pnew->next=NULL;pnew->next=FBhead->next;FBhead->next=pnew;.printf("起始空閑塊號(hào)：&

25、quot;);scanf("%d",&pnew->FBbegin);printf("空閑塊個(gè)數(shù)： ");scanf("%d",&pnew->num);pnew->state='F'pnew=pnew->next;Filehead=(struct filetowrite *)malloc(sizeof(struct filetowrite);Filehead->next=NULL;dosystem("cls");printf("ntt*主菜單 *

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

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

28、turn 0;2、題二源代碼：#include <stdio.h>#include <process.h>void Initbitmap(int map88) int cylinder,track,sector;char choice='Y'printf("初始化位視圖.n");while(choice='y'|choice='Y') printf("柱面號(hào) :");scanf("%d",&cylinder);printf("磁道號(hào) :"

29、;);scanf("%d",&track);printf("物理記錄號(hào) :");scanf("%d",&sector);mapcylinder4*track+sector=1;printf("contiune?");getchar();scanf("%c",&choice); void allocate(int map88) int i,j;.int flag=0;int cylinder,track,sector;for(i=0;i<8;i+) for(j=0;j

30、<8;j+) if(mapij=0)mapij=1;flag=1;break;if(flag=1) break;if(flag=1)cylinder=i;track=j/4;sector=j%4;printf("分配到的柱面號(hào)、磁道號(hào)、物理記錄數(shù)");printf("%dt%dt%d",cylinder,track,sector);printf("n"); else printf("空間不足，分配失敗!"); void reclaim(int map88) int cylinder,track,sector;

31、 printf(" 柱面號(hào) :"); scanf("%d",&cylinder); printf(" 磁道號(hào) :"); scanf("%d",&track); printf(" 物理記錄號(hào) :"); scanf("%d",&sector);if(mapcylinder4*track+sector=0)printf("此塊為未分配塊！回收出錯(cuò)！");getchar();elsemapcylinder4*track+sector=0;p

32、rintf("回收塊對(duì)應(yīng)的字節(jié)號(hào):%4dt位數(shù):%4dn",cylinder,4*track+sector); void main() int bitmap88; int i,j; int choice;or(i=0;i<8;i+)for(j=0;j<8;j+)bitmapij=0; Initbitmap(bitmap);while(1) printf("n請(qǐng)輸入選擇 :");printf("1-分配， 2- 回收， 3- 顯示位示圖， 0- 退出 n");scanf("%d",&choice)

33、;switch(choice)case 1:allocate(bitmap);break;case 2:reclaim(bitmap);break;case 3:for(i=0;i<8;i+)for(j=0;j<8;j+)printf("%8d",bitmapij);printf("n");break;case 0:exit(0);default:printf("錯(cuò)誤選擇！ ");break; .3、第三題源程序：#include<stdio.h>int MA4;/*空閑塊數(shù)組 */intA94=3,1,2,3

34、,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;/*存放已分配的塊*/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)

35、printf("ngroup%d:",count); i=Atemp0; for(j=1;j<=i;j+) printf("%d ",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;elsei=MA0;if(i=1)printf("nThe blocks

36、are all assigned");elseprintf("ngroup1:");for(j=2;j<=i;j+)printf("%d",MAj);mark+No=MAj; void display() /*顯示分組情況*/int i,j;if(MA0!=0)display1();elsei=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("nnumber of the block:%d",s);else if(MA0=1)/*只剩一個(gè)空閑塊*/if(MA1!=0)/*還有其它空