操作系統(tǒng)實驗四報告-主存空間分配和回收(共27頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 計算機 學(xué)院 計算機科學(xué)與技術(shù) 專業(yè) 班學(xué)號 姓名 教師評定_ 實驗題目 主存空間的分配和回收 一、實驗?zāi)康氖煜ぶ鞔娴姆峙渑c回收。理解在不同的存儲管理方式下，如何實現(xiàn)主存空間的分配與回收。掌握動態(tài)分區(qū)分配方式中的數(shù)據(jù)結(jié)構(gòu)和分配算法及動態(tài)分區(qū)存儲管理方式及其實現(xiàn)過程。二、實驗內(nèi)容和要求主存的分配和回收的實現(xiàn)是與主存儲器的管理方式有關(guān)的。所謂分配，就是解決多道作業(yè)或多進程如何共享主存空間的問題。所謂回收，就是當(dāng)作業(yè)運行完成時將作業(yè)或進程所占的主存空間歸還給系統(tǒng)?？勺兎謪^(qū)管理是指在處理作業(yè)過程中建立分區(qū)，使分區(qū)大小正好適合作業(yè)的需求，并且分區(qū)個數(shù)是可以調(diào)整的。當(dāng)要裝入一個

2、作業(yè)時，根據(jù)作業(yè)需要的主存量查看是否有足夠的空閑空間，若有，則按需要量分割一個分區(qū)分配給該作業(yè)；若無，則作業(yè)不能裝入，作業(yè)等待。隨著作業(yè)的裝入、完成，主存空間被分成許多大大小小的分區(qū)，有的分區(qū)被作業(yè)占用，而有的分區(qū)是空閑的。實驗要求使用可變分區(qū)存儲管理方式，分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)采用空閑分區(qū)表和空閑分區(qū)鏈來進行，分區(qū)分配中所用的算法采用首次適應(yīng)算法、最佳適應(yīng)算法、最差適應(yīng)算法三種算法來實現(xiàn)主存的分配與回收。同時，要求設(shè)計一個實用友好的用戶界面，并顯示分配與回收的過程。同時要求設(shè)計一個實用友好的用戶界面,并顯示分配與回收的過程。三、實驗主要儀器設(shè)備和材料實驗環(huán)境硬件環(huán)境：IBM-PC或兼容機軟

3、件環(huán)境：VC+ 6.0四、實驗原理及設(shè)計分析某系統(tǒng)采用可變分區(qū)存儲管理，在系統(tǒng)運行當(dāng)然開始，假設(shè)初始狀態(tài)下，可用的內(nèi)存空間為640KB，存儲器區(qū)被分為操作系統(tǒng)分區(qū)（40KB）和可給用戶的空間區(qū)（600KB）。 （作業(yè)1 申請130KB、 作業(yè)2 申請60KB、 作業(yè)3 申請100KB 、 作業(yè)2 釋放 60KB 、 作業(yè)4 申請 200KB、 作業(yè)3釋放100KB、 作業(yè)1 釋放130KB 、 作業(yè)5申請140KB 、 作業(yè)6申請60KB 、作業(yè)7申請50KB） 當(dāng)作業(yè)1進入內(nèi)存后，分給作業(yè)1（130KB），隨著作業(yè)1、2、3的進入，分別分配60KB、100KB，經(jīng)過一段時間的運行后，作業(yè)2運

4、行完畢，釋放所占內(nèi)存。此時，作業(yè)4進入系統(tǒng)，要求分配200KB內(nèi)存。作業(yè)3、1運行完畢，釋放所占內(nèi)存。此時又有作業(yè)5申請140KB，作業(yè)6申請60KB，作業(yè)7申請50KB。為它們進行主存分配和回收。1、采用可變分區(qū)存儲管理，使用空閑分區(qū)鏈實現(xiàn)主存分配和回收?？臻e分區(qū)鏈：使用鏈指針把所有的空閑分區(qū)鏈成一條鏈，為了實現(xiàn)對空閑分區(qū)的分配和鏈接，在每個分區(qū)的起始部分設(shè)置狀態(tài)位、分區(qū)的大小和鏈接各個分區(qū)的前向指針，由狀態(tài)位指示該分區(qū)是否分配出去了；同時，在分區(qū)尾部還設(shè)置有一后向指針，用來鏈接后面的分區(qū)；分區(qū)中間部分是用來存放作業(yè)的空閑內(nèi)存空間，當(dāng)該分區(qū)分配出去后，狀態(tài)位就由“0”置為“1”。設(shè)置一個內(nèi)存

5、空閑分區(qū)鏈，內(nèi)存空間分區(qū)通過空閑分區(qū)鏈來管理，在進行內(nèi)存分配時，系統(tǒng)優(yōu)先使用空閑低端的空間。設(shè)計一個空閑分區(qū)說明鏈，設(shè)計一個某時刻主存空間占用情況表，作為主存當(dāng)前使用基礎(chǔ)。初始化空間區(qū)和已分配區(qū)說明鏈的值，設(shè)計作業(yè)申請隊列以及作業(yè)完成后釋放順序，實現(xiàn)主存的分配和回收。要求每次分配和回收后顯示出空閑內(nèi)存分區(qū)鏈的情況。把空閑區(qū)說明鏈的變化情況以及各作業(yè)的申請、釋放情況顯示打印出來。2.采用可變分區(qū)存儲管理，分別采用首次適應(yīng)算法、最佳適應(yīng)算法和最壞適應(yīng)算法實現(xiàn)主存分配和回收。3、主存空間分配 （1）首次適應(yīng)算法在該算法中，把主存中所有空閑區(qū)按其起始地址遞增的次序排列。在為作業(yè)分配存儲空間時，從上次找

6、到的空閑分區(qū)的下一個空閑分區(qū)開始查找，直到找到第一個能滿足要求的空閑區(qū)，從中劃出與請求的大小相等的存儲空間分配給作業(yè)，余下的空閑區(qū)仍留在空閑區(qū)鏈中。（2）最佳適應(yīng)算法在該算法中，把主存中所有空閑區(qū)按其起始地址遞增的次序排列。在為作業(yè)分配存儲空間時，從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，直到找到一個能滿足要求的空閑區(qū)且該空閑區(qū)的大小比其他滿足要求的空閑區(qū)都小，從中劃出與請求的大小相等的存儲空間分配給作業(yè)，余下的空閑區(qū)仍留在空閑區(qū)鏈中（3）最壞適應(yīng)算法在該算法中，把主存中所有空閑區(qū)按其起始地址遞增的次序排列。在為作業(yè)分配存儲空間時，從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，直到找到一個

7、能滿足要求的空閑區(qū)且該空閑區(qū)的大小比其他滿足要求的空閑區(qū)都大，從中劃出與請求的大小相等的存儲空間分配給作業(yè)，余下的空閑區(qū)仍留在空閑區(qū)鏈中。4、主存空間回收 當(dāng)一個作業(yè)執(zhí)行完成撤離時，作業(yè)所占的分區(qū)應(yīng)該歸還給系統(tǒng)。歸還的分區(qū)如果與其它空閑區(qū)相鄰，則應(yīng)合成一個較大的空閑區(qū)，登記在空閑區(qū)說明鏈中，此時，相鄰空閑區(qū)的合并問題，要求考慮四種情況：（1） 釋放區(qū)下鄰空閑區(qū)（低地址鄰接）（2） 釋放區(qū)上鄰空閑區(qū)（高地址鄰接）（3） 釋放區(qū)上下都與空閑區(qū)鄰接（4） 釋放區(qū)上下鄰都與空閑區(qū)不鄰接五、程序流程圖main函數(shù)里的流程圖初始化first和end整理分區(qū)序號顯示空閑分區(qū)鏈選擇算法aa=1，首次適應(yīng)算法a

8、=2，最佳適應(yīng)算法a=3，最壞適應(yīng)算法選擇操作ii=1，分配空間函數(shù)ai=0，退出程序i=2，回收空間函數(shù)結(jié)束分配空間里的流程圖p->data.length=request分配不成功分配空間函數(shù)a=1a=2a=3輸入申請內(nèi)存大小按順序找空閑塊初始化q，使它指向空閑塊中長度小的一塊輸入申請內(nèi)存大小初始化q，使它指向空閑塊中長度大的一塊p->data.length>requestp的狀態(tài)為已分配剩下p->data.length-=request輸入申請內(nèi)存大小YYNN返回到整理分區(qū)序號回收空間里的流程圖p的狀態(tài)改為空閑回收p，p的前一個為firstp的后一個是endp的后一

9、個狀態(tài)空與后面空閑塊相連將p 的狀態(tài)改為空閑將p 的狀態(tài)改為空閑回收空間函數(shù)p的后一個是endYNYNYNp的前一個狀態(tài)空p的前一個狀態(tài)空p的后一個狀態(tài)空p的后一個狀態(tài)空p的后一個狀態(tài)空p的后一個狀態(tài)空YYYNNN與前面空閑塊相連p的狀態(tài)改為空閑與前面空閑塊相連與后面空閑塊相連YN返回到整理分區(qū)序號六、相關(guān)數(shù)據(jù)結(jié)構(gòu)及關(guān)鍵函數(shù)說明本程序采用了一個struct free_table數(shù)據(jù)結(jié)構(gòu)，里面包含分區(qū)序號（num）、起始地址（address）、分區(qū)長度（length）和分區(qū)狀態(tài)（state）。還用了線性表的雙性鏈表存儲結(jié)構(gòu)（struct Node），里面包含前區(qū)指針（prior）和后繼指針（ne

10、xt）。一開始定義一條（含有first和end）的鏈，用開始指針和尾指針開創(chuàng)空間鏈表。然后分別按三種算法進行分配和回收。在該程序中關(guān)鍵函數(shù)有，sort（）、allocation（）、recovery（）、和First_fit（）、Best_fit（）、Worst_fit（）；其中sort（）函數(shù)是用來整理分區(qū)序號的，如在刪序號3時，她與前面序號2相連在一起了，然后序號2中的長度總滿足申請的內(nèi)存大小，就會在序號2中分配，然后序號在2的基礎(chǔ)上加1，一直加，加到與原本序號3的下一個序號也就是4相等，這時sort（）就開始有明顯的工作了；allocation（）是分配空間的，也是過渡到三個算法中的，當(dāng)

11、三個算法中滿足或者不滿足分配請求，都會又返回值給allocation（）；recovery（）是用來回收內(nèi)存的，里面包含了四種情況相連結(jié)果，即釋放區(qū)上與空閑區(qū)鄰接、釋放區(qū)下與空閑區(qū)鄰接、釋放區(qū)上下都與空閑區(qū)鄰接、釋放區(qū)上下都與空閑區(qū)不鄰接這四種情況的結(jié)果。七、源代碼#include<stdio.h>#include<stdlib.h>#define OK 1 /完成#define ERROR 0 /出錯typedef int Status;typedef struct free_table/定義一個空閑區(qū)說明表結(jié)構(gòu) int num; /分區(qū)序號 long address

12、; /起始地址 long length; /分區(qū)大小 int state; /分區(qū)狀態(tài)ElemType;typedef struct Node/ 線性表的雙向鏈表存儲結(jié)構(gòu) ElemType data; struct Node *prior; /前趨指針 struct Node *next; /后繼指針Node,*LinkList; LinkList first; /頭結(jié)點LinkList end; /尾結(jié)點int flag;/記錄要刪除的分區(qū)序號Status Initblock()/開創(chuàng)帶頭結(jié)點的內(nèi)存空間鏈表 first=(LinkList)malloc(sizeof(Node); end=(

13、LinkList)malloc(sizeof(Node); first->prior=NULL; first->next=end; end->prior=first; end->next=NULL; end->data.num=1; end->data.address=40; end->data.length=600; end->data.state=0; return OK;void sort()/分區(qū)序號重新排序 Node *p=first->next,*q; q=p->next; for(;p!=NULL;p=p->nex

14、t) for(q=p->next;q;q=q->next) if(p->data.num>=q->data.num) q->data.num+=1; /顯示主存分配情況void show() int flag=0;/用來記錄分區(qū)序號 Node *p=first; p->data.num=0; p->data.address=0; p->data.length=40; p->data.state=1; sort(); printf("ntt主存空間分配情況n"); printf("*nn"); p

15、rintf("分區(qū)序號t起始地址t分區(qū)大小t分區(qū)狀態(tài)nn"); while(p) printf("%dtt%dtt%d",p->data.num,p->data.address,p->data.length); if(p->data.state=0) printf("tt空閑nn"); else printf("tt已分配nn"); p=p->next; printf("*nn");/首次適應(yīng)算法Status First_fit(int request) /為申請作

16、業(yè)開辟新空間且初始化 Node *p=first->next; LinkList temp=(LinkList)malloc(sizeof(Node); temp->data.length=request; temp->data.state=1; p->data.num=1; while(p) if(p->data.state=0)&&(p->data.length=request) /有大小恰好合適的空閑塊 p->data.state=1; return OK; break; else if(p->data.state=0) &

17、amp;& (p->data.length>request) /有空閑塊能滿足需求且有剩余 temp->prior=p->prior; temp->next=p; temp->data.address=p->data.address; temp->data.num=p->data.num; p->prior->next=temp; p->prior=temp; p->data.address=temp->data.address+temp->data.length; p->data.leng

18、th-=request; p->data.num+=1; return OK; break; p=p->next; return ERROR;/最佳適應(yīng)算法Status Best_fit(int request) int ch; /記錄最小剩余空間 Node *p=first; Node *q=NULL; /記錄最佳插入位置 LinkList temp=(LinkList)malloc(sizeof(Node); temp->data.length=request; temp->data.state=1; p->data.num=1; while(p) /初始化最

19、小空間和最佳位置 if(p->data.state=0) && (p->data.length>=request) ) if(q=NULL) q=p; ch=p->data.length-request; else if(q->data.length > p->data.length) q=p; ch=p->data.length-request; p=p->next; if(q=NULL) return ERROR;/沒有找到空閑塊 else if(q->data.length=request) q->data

20、.state=1; return OK; else temp->prior=q->prior; temp->next=q; temp->data.address=q->data.address; temp->data.num=q->data.num; q->prior->next=temp; q->prior=temp; q->data.address+=request; q->data.length=ch; q->data.num+=1; return OK; return OK;/最差適應(yīng)算法Status Wor

21、st_fit(int request) int ch; /記錄最大剩余空間 Node *p=first->next; Node *q=NULL; /記錄最佳插入位置 LinkList temp=(LinkList)malloc(sizeof(Node); temp->data.length=request; temp->data.state=1; p->data.num=1; while(p) /初始化最大空間和最佳位置 if(p->data.state=0 && (p->data.length>=request) ) if(q=NUL

22、L) q=p; ch=p->data.length-request; else if(q->data.length < p->data.length) q=p; ch=p->data.length-request; p=p->next; if(q=NULL) return ERROR;/沒有找到空閑塊 else if(q->data.length=request) q->data.length=1; return OK; else temp->prior=q->prior; temp->next=q; temp->data

23、.address=q->data.address; temp->data.num=q->data.num; q->prior->next=temp; q->prior=temp; q->data.address+=request; q->data.length=ch; q->data.num+=1; return OK; return OK;/分配主存Status allocation(int a) int request;/申請內(nèi)存大小 printf("請輸入申請分配的主存大小(單位:KB):"); scanf(&qu

24、ot;%d",&request); if(request<0 |request=0) printf("分配大小不合適，請重試！"); return ERROR; switch(a) case 1: /默認(rèn)首次適應(yīng)算法 if(First_fit(request)=OK) printf("t*分配成功！*"); else printf("t*內(nèi)存不足，分配失??！*"); return OK;break; case 2: /選擇最佳適應(yīng)算法 if(Best_fit(request)=OK) printf("

25、t*分配成功！*"); else printf("t*內(nèi)存不足，分配失??！*"); return OK; break;case 3: /選擇最差適應(yīng)算法 if(Worst_fit(request)=OK) printf("t*分配成功！*"); else printf("t*內(nèi)存不足，分配失敗！*"); return OK;break; Status deal1(Node *p)/處理回收空間 Node *q=first; for(;q!=NULL;q=q->next) if(q=p) if(q->prior-&

26、gt;data.state=0&&q->next->data.state!=0) q->prior->data.length+=q->data.length; q->prior->next=q->next; q->next->prior=q->prior; q=q->prior; q->data.state=0; q->data.num=flag-1; if(q->prior->data.state!=0&&q->next->data.state=0) q

27、->data.length+=q->next->data.length; q->next=q->next->next; q->next->next->prior=q; q->data.state=0; q->data.num=flag; if(q->prior->data.state=0&&q->next->data.state=0) q->prior->data.length+=q->data.length; q->prior->next=q->nex

28、t; q->next->prior=q->prior; q=q->prior; q->data.state=0; q->data.num=flag-1; if(q->prior->data.state!=0&&q->next->data.state!=0) q->data.state=0; return OK;Status deal2(Node *p)/處理回收空間 Node *q=first; for(;q!=NULL;q=q->next) if(q=p) if(q->prior->data.

29、state=0&&q->next->data.state!=0) q->prior->data.length+=q->data.length; q->prior->next=q->next; q->next->prior=q->prior; q=p->prior; q->data.state=0; q->data.num=flag-1; if(q->prior->data.state!=0&&q->next->data.state=0) q->dat

30、a.state=0; if(q->prior->data.state=0&&q->next->data.state=0) q->prior->data.length+=q->data.length; q->prior->next=q->next; q->next->prior=q->prior; q=q->prior; q->data.state=0; q->data.num=flag-1; if(q->prior->data.state!=0&&q-&g

31、t;next->data.state!=0) q->data.state=0; return OK;/主存回收Status recovery(int flag) Node *p=first; for(;p!=NULL;p=p->next) if(p->data.num=flag) if(p->prior=first) if(p->next!=end)/當(dāng)前P指向的下一個不是最后一個時 if(p->next->data.state=0) /與后面的空閑塊相連 p->data.length+=p->next->data.length

32、; p->next->next->prior=p; p->next=p->next->next; p->data.state=0; p->data.num=flag; else p->data.state=0; if(p->next=end)/當(dāng)前P指向的下一個是最后一個時 p->data.state=0; /結(jié)束if(p->prior=block_first)的情況 else if(p->prior!=first) if(p->next!=end) deal1(p); else deal2(p); /結(jié)束if

33、(p->prior!=block_first)的情況 /結(jié)束if(p->data.num=flag)的情況 printf("t*回收成功*"); return OK; /主函數(shù)void main() int i; /操作選擇標(biāo)記 int a;/算法選擇標(biāo)記 printf("*n"); printf("tt用以下三種方法實現(xiàn)主存空間的分配n"); printf("t(1)首次適應(yīng)算法t(2)最佳適應(yīng)算法t(3)最差適應(yīng)算法n");printf("*n"); printf("n

34、"); printf("請輸入所使用的內(nèi)存分配算法:"); scanf("%d",&a); while(a<1|a>3) printf("輸入錯誤，請重新輸入所使用的內(nèi)存分配算法:n"); scanf("%d",&a); switch(a) case 1:printf("nt*使用首次適應(yīng)算法：*n");break; case 2:printf("nt*使用最佳適應(yīng)算法：*n");break; case 3:printf("nt*使用最壞適應(yīng)算法：*n");break; Initblock(); /開創(chuàng)空間表 while(1) show(); printf("t1: 分配內(nèi)存t2: 回收內(nèi)存t0: 退出n"); printf("請輸入您的操作："); scanf("%d",&i); if(i=1) allocation(a); / 分配內(nèi)存 else if(i=2) / 內(nèi)存回收 printf("請輸入您要釋放的