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

1、實(shí)習(xí)六 磁盤存儲(chǔ)空間的分配和回收 1、 實(shí)習(xí)內(nèi)容模擬磁盤空閑空間的表示方法，以及模擬實(shí)現(xiàn)磁盤空間的分配和回收。2、 實(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è)重要問(wèn)題，通過(guò)本實(shí)習(xí)使學(xué)生掌握磁盤存儲(chǔ)空間的分配和回

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

3、起始空閑塊號(hào)空閑塊個(gè)數(shù)狀 態(tài)156未 分 配2143未 分 配32130未 分 配4  空 表 目MM MM MM MM  (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ǔ)空間的

4、分配和回收算法類似于主存儲(chǔ)器的可變分區(qū)方式的分配和回收。同學(xué)們可參考實(shí)習(xí)四的第一題。(3) 當(dāng)找到空閑塊后，必須啟動(dòng)磁盤把信息存放到指定的塊中，啟動(dòng)磁盤必須給出由三個(gè)參數(shù)組成的物理地址：柱面號(hào)、磁道號(hào)和物理記錄號(hào)。故必須把找到的空閑塊號(hào)換算成磁盤的物理地址。為了減少移臂次數(shù)，磁盤上的信息按柱面上各磁道順序存放。現(xiàn)假定一個(gè)盤組共有200個(gè)柱面，（編號(hào)0-199）每個(gè)柱面有20個(gè)磁道（編號(hào)0-19，同一柱面上的各磁道分布在各盤面上，故磁道號(hào)即盤面號(hào)。），每個(gè)磁道被分成等長(zhǎng)的6個(gè)物理記錄（編號(hào)0-5，每個(gè)盤面被分成若干個(gè)扇區(qū)，故每個(gè)磁道上的物理記錄號(hào)即為對(duì)應(yīng)的扇區(qū)號(hào)。）。那么，空閑塊號(hào)與磁盤物理地址

5、的對(duì)應(yīng)關(guān)系如下：空閑塊號(hào)6空閑塊號(hào)6假設(shè)M= ， m=  M20則 物理記錄號(hào) = m磁道號(hào)= M20柱面號(hào)=  (4) 刪除一個(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)行你所

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

7、空間和磁盤存儲(chǔ)空間應(yīng)該用不同的位示圖來(lái)管理，絕不可混用。(2) 申請(qǐng)一塊磁盤空間時(shí)，由分配程序查位示圖，找出一個(gè)為“0”的位，計(jì)算出這一位對(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)位數(shù)4磁道號(hào)= 位數(shù)4物理記錄號(hào)=  (3) 歸還一塊磁盤空間時(shí)，由回收程序根據(jù)歸還的磁盤物理地址計(jì)算出歸還塊在位示圖中的對(duì)應(yīng)位，把該位置成“0”。按照（2）中假設(shè)的盤組，歸還塊在位示圖中的位置計(jì)算如下：字節(jié)號(hào)=柱面

8、號(hào)位數(shù)=磁道號(hào)´4+物理記錄號(hào)(4) 設(shè)計(jì)申請(qǐng)一塊磁盤空間和歸還一塊磁盤空間的程序。要求能顯示或打印程序運(yùn)行前和運(yùn)行后的位示圖；分配時(shí)把分配到的磁盤空間的物理地址顯示或打印出來(lái)，歸還時(shí)把歸還塊對(duì)應(yīng)于位示圖的字節(jié)號(hào)和位數(shù)顯示或打印出來(lái)。(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 第三題：

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

10、鏈接的初始狀態(tài)為：  開(kāi)始時(shí)，空閑塊號(hào)是順序排列的，但經(jīng)若干次的分配和歸還操作后，空閑塊的鏈接就未必按序排列了。用二維數(shù)組A：array 0M-1 of array 0n-1來(lái)模擬管理磁盤空間，用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)，當(dāng)一組的空閑塊只剩第一塊時(shí)，則應(yīng)把該塊中指出的下一組的空閑塊數(shù)和塊號(hào)復(fù)制到專用塊中，然后把該塊分配給申請(qǐng)者。當(dāng)一組的

11、空閑塊分配完后則把專用塊內(nèi)容（下一組鏈接情況）復(fù)制到主存，再為申請(qǐng)者分配。分配算法如圖6-1。圖6-1 采用成組鏈接的分配算法(4) 歸還一塊時(shí)給出歸還的塊號(hào)，叵當(dāng)前組不滿規(guī)定塊數(shù)時(shí)，將歸還塊登記入該組；若當(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)換工作，而

12、在實(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)依次顯示或打印出來(lái)，且顯示或打印空閑塊組的情況。在上次執(zhí)行的基礎(chǔ)上繼續(xù)分配3塊，然后歸還第1塊，再申請(qǐng)5塊，顯示或打印依次分配到的塊號(hào)及空閑塊組情況。4、 相關(guān)數(shù)據(jù)結(jié)構(gòu)及說(shuō)明 struct freeblock int FBbegin;/起始空閑塊號(hào) int num;/空閑塊數(shù) char state;/狀態(tài) struct freeblock *next; struct filetowrite  

13、       char name10;/文件名         int size;/文件大小        int addr_cylinder;/裝入磁盤的首地址_柱面號(hào)        int addr_track;/裝入磁盤的首地址_磁道號(hào)

14、0;       int addr_note;/裝入磁盤的首地址_物理記錄號(hào)        struct filetowrite *next;   六、源代碼及注釋1、 題一源代碼：#include<stdlib.h>#include<stdio.h>int getmalloc()/分配磁盤空間     

15、 int flag=0; struct freeblock *p=FBhead;     struct filetowrite *File; File=(struct filetowrite *)malloc(sizeof(struct filetowrite);     printf("輸入要裝入的文件名：");    

16、60;scanf("%s",File->name);  printf("輸入所需的磁盤空間大小：");     scanf("%d",&File->size); for(p=FBhead->next;p!=NULL;p=p->next)         if(File->size)<=(p->num)/分配空間

17、0;                       flag=1;              File->addr_cylinder=(p->FBbegin)/6)/20; File->addr_track=(p-

18、>FBbegin)/6)%20;              File->addr_note=(p->FBbegin)%6;              File->next=Filehead->next;/加入文件鏈表      &

19、#160;        Filehead->next=File;              if(File->size)<(p->num)/修改該快的起始地址和塊數(shù)                

20、;                 p->FBbegin=p->FBbegin+File->size;                  p->num=p->num-File->size;  &

21、#160;                         else p->state='U'              break;   

22、0;          if(flag=0)         printf("抱歉!目前沒(méi)有足夠的磁盤空間分配給該文件.n");     else       printf("分配磁盤成功!n該文件的物理地址：n柱面號(hào)t磁道號(hào)t物理塊號(hào)n "

23、;);         printf("  %dt  %dt  %dn",File->addr_cylinder,File->addr_track,File->addr_note);       int deletelfree()/回收磁盤空間      char

24、0;name10;     int flag=0;     struct filetowrite *p; printf("輸入要?jiǎng)h除的文件名：");     scanf("%s",&name); for(p=Filehead;p->next!=NULL;p=p->next)     

25、60; if(strcmp(p->next->name,name)=0)/找到該文件 flag=1; int funion=0,nunion=0;              int m=p->next->addr_cylinder;             

26、; int n=p->next->addr_track;              int k=p->next->addr_note;  int addr=(m*20+n)*6+k;/起始空閑塊號(hào)              int

27、60;tail=p->next->size+addr;  struct freeblock *pnode,*qnode,*tnode,*snode;              pnode=FBhead->next;    while(pnode!=NULL)/先考慮和后面的部分或許有合并的情況     

28、0;           if(pnode->FBbegin)=tail)                    pnode->FBbegin=addr;   pnode->num=pnode->num+p->next->s

29、ize;                        nunion=1;                        

30、;break;                     pnode=pnode->next;               qnode=FBhead->next;  while(qnode!=NULL)/再考慮

31、是否和前面的可以合并                   if(qnode->FBbegin+qnode->num)=addr)                      

32、60; if(nunion=0)                              qnode->num=qnode->num+p->next->size;        

33、60;                     funion=1;break;                          

34、                        else                         &#

35、160;  qnode->num=qnode->num+pnode->num;                              tnode=FBhead;   while(tnode->next!=pnode)

36、60;                             tnode=tnode->next;                 

37、             tnode->next=pnode->next;                              free(pnode);

38、                              funion=1;                  

39、60;           break;                                     

40、60;          qnode=qnode->next;               if(funion=0&&nunion=0)/若沒(méi)有和前面的或后面的進(jìn)行合并，則新建一個(gè)表目            

41、   snode=(struct freeblock *)malloc(sizeof(struct freeblock);                    snode->FBbegin=addr;           

42、         snode->num=p->next->size;                    snode->state='F'           

43、;         if(FBhead->next=NULL)                      FBhead->next=snode;           &

44、#160;              snode->next=NULL;                                

45、;             else                        snode->next=FBhead->next;FBhead->next=snode;   &#

46、160;                                 struct filetowrite *q;           

47、   q=p->next;/除該文件 p->next=p->next->next;              free(q);              break;       

48、60;         if(flag=0)  printf("沒(méi)有該文件!n");     else printf("文件刪除成功!n");  int dispfree()/顯示磁盤空閑區(qū)表      int i=1; struct freeblock *p

49、=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->state)='F')    &#

50、160; printf(" %dt      %dtt     %dtt未分配n",i+,p->FBbegin,p->num);         else   printf(" %dttttt空表目n",i+);      &#

51、160;int dispfile()     char name10; struct filetowrite *p=Filehead;     printf("輸入要查看的文件名：");     scanf("%s",&name);  for(p=Filehead->next;p!=NULL;p=p->next)

52、60;        if(strcmp(p->name,name)=0)           printf("該文件的物理地址：n柱面號(hào)t磁道號(hào)t物理塊號(hào)n ");   printf("  %dt  %dt  %dn",p->addr_cylinder,p

53、->addr_track,p->addr_note);             break;                   if(p=NULL)  printf("沒(méi)有該文件!n");  int

54、0;main()  int n,i,AMAX,BMAX;/AMAX表示起始空閑塊號(hào)，BMAX表示空閑塊個(gè)數(shù)      char ch;     struct freeblock *pnew; FBhead=(struct freeblock *)malloc(sizeof(struct freeblock);     FBhead->

55、;next=NULL; printf("輸入磁盤空閑區(qū)個(gè)數(shù)：");     scanf("%d",&n);     for(i=1;i<=n;i+)              pnew=(struct freeblock *)malloc(sizeof(struct 

56、;freeblock);              pnew->next=NULL;pnew->next=FBhead->next;         FBhead->next=pnew;         printf("起始空閑塊號(hào)："

57、);         scanf("%d",&pnew->FBbegin);         printf("空閑塊個(gè)數(shù)：");         scanf("%d",&pnew->num);    &

58、#160;    pnew->state='F'         pnew=pnew->next;                Filehead=(struct filetowrite *)malloc(sizeof(struct filetowri

59、te);      Filehead->next=NULL;      do              system("cls"); printf("ntt       * 主菜單 *nn");

60、         printf("ttt1.新建文件n");         printf("ttt2.刪除文件n");         printf("ttt3.查看磁盤n");       

61、60; printf("ttt4.查看文件n");         printf("ttt5.退出n");         printf("請(qǐng)選擇：");         scanf("%c",&ch);  &#

62、160;      switch(ch)                       case '1':getmalloc();system("pause");break;       

63、0;      case '2':deletelfree();system("pause");break;              case '3':dispfree();system("pause");break;       

64、60;      case '4':dispfile();system("pause");break;               case '5':exit(1);break;  default:printf("輸入錯(cuò)誤!請(qǐng)重新輸入.n");   

65、;printf("n");         getchar();     while(ch!=4);     return 0; 2、 題二源代碼：#include <stdio.h> #include <process.h>  void Initbitmap(int map

66、88)   int cylinder,track,sector;  char choice='Y'  printf("初始化位視圖.n");  while(choice='y'|choice='Y')   printf("柱面號(hào):");   scanf("%d",&cylinder);  &#

67、160;printf("磁道號(hào):");   scanf("%d",&track);   printf("物理記錄號(hào):");   scanf("%d",&sector);   mapcylinder4*track+sector=1;   printf("contiune?");   getchar();&

68、#160;  scanf("%c",&choice);      void allocate(int map88)    int i,j;   int flag=0;   int cylinder,track,sector;    for(i=0;i<8;i+)   

69、;     for(j=0;j<8;j+)         if(mapij=0) mapij=1;flag=1;break;          if(flag=1) break;          if(flag=1) &

70、#160;        cylinder=i;     track=j/4;     sector=j%4; printf("分配到的柱面號(hào)、磁道號(hào)、物理記錄數(shù)");     printf("%dt%dt%d",cylinder,track,sector);printf("n"); &#

71、160; else printf("空間不足，分配失敗!");   void reclaim(int map88)  int cylinder,track,sector;   printf("柱面號(hào):");   scanf("%d",&cylinder);   printf("磁道號(hào):");  

72、60;scanf("%d",&track);   printf("物理記錄號(hào):");   scanf("%d",&sector);  if(mapcylinder4*track+sector=0)       printf("此塊為未分配塊！回收出錯(cuò)！"); getchar();     &#

73、160;else     mapcylinder4*track+sector=0; printf("回收塊對(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+)

74、0;   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);   

75、0; 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");