1、精選優質文檔-傾情為你奉上動態分區分配算法一實驗內容與要求 內容：動態分區分配是根據進程的實際需要，動態地為之分配內存空間，而在分配時，須按照一定的分配算法，從空閑分區表或空閑分區鏈中選出一分區分配給該作業。在本實驗中運用了三種分配算法，分別是1.首次適應算法，2.循環首次適應算法，3.最佳適應算法。 要求：動態分區算法也稱為可變分區分配算法，常見的空閑區查找算法有首次適應算法，循環首次適應算法，最佳適應算法。特別注意分區回收時，相鄰空閑分區需要合并。(1) 參考操作系統教材理解這3種分配算法以及回收算法。(2) 實現3種分配算法以及回收算法。(3) 已知作業申請內存和釋放內存的序列，給出內存

2、的使用情況。(4) 作業申請內存和釋放內存的序列可以存放在文本文件中。(5) 設計簡單的交互界面，演示所設計的功能。(可以使用MFC進行界面的設計)(6) 可根據自己能力，在完成以上基本要求后，對程序功能進行適當擴充。二、需求分析 本次實驗通過用C語言進行編程并調試、運行，形象地表現出動態分區的分配方式，直觀地展現了首次適應算法和最佳適應算法對內存的釋放和回收方式之間的區別。加深了我們對兩種算法優缺點的理解，幫助我們了解一些數據結構和分配算法，進一步加深我們對動態分區存儲器管理方式及其實現過程的理解。主要的問題在于，如何解決兩種算法對內存的釋放和回收空間的表示。 動態分區分配：又稱為可變分區分

3、配，這種分配方式并不事先先將主存劃分成一塊塊的分區，而是在作業進入主存時，根據作業的大小動態地建立分區。并使分區的大小正好適應作業的需要。因此系統中分區的大小是可變的，分區的數目也是可變的。 分區分配算法：1.首次適應法： 為作業選擇分區時總是按地址從高到低搜索，只要找到可以容納該作業的空白塊，就把該空白塊分配給該作業。特點：優先利用內存中底地址部分的空閑分區 (將所有空閑區,按其地址遞增的順序鏈接)2.循環首次適應算法該算法是由首次適應算法演變而成，在為進程分配內存空間時，不再是每次都從第一個空間開始查找，而是從上次找到的空閑分區的下一個空閑分區開始查找，直至找到第一個能滿足要求的空閑分區，

4、從中劃出一塊與請求大小相等的內存空間分配給作業，為實現本算法，設置一個全局變量f，來控制循環查找，當f%N=0時，f=0；若查找結束都不能找到一個滿足要求的分區，則此次內存分配失敗。3.最佳適應算法： 接到內存申請時，在空閑塊表中找到一個不小于請求的最小空塊進行分配;為作業選擇分區時總是尋找其大小最接近于作業所要求的存儲區域。三、概要設計 動態分區常用的數據結構有空閑分區表和空閑分區鏈，用來記錄內存的使用情況，此題中我采用的是空閑分區鏈的結構，用鏈指針將所有的分區鏈接成一條鏈，每個分區的結構如下所示：typedef struct freearea/定義一個空閑區說明表結構int ID; /分區

5、號long size; /分區大小long address; /分區地址int state; /狀態ElemType;typedef struct DuLNode /double linked listElemType data; struct DuLNode *prior; /前趨指針struct DuLNode *next; /后繼指針DuLNode,*DuLinkList;前向指針和后向指針分別用于與當前分區的前后分區相鏈接，address用于說明當前分區的起始地址，狀態字為0時表示當前分區空閑，為1時表示已分配，id為分配的作業號，size表示分配的內存大小。流程圖：開始讀入文件選擇算

6、法首次循環最佳選擇操作根據選擇算法做出相應操作顯示結果到達文件尾部顯示結果選擇根據要求，請求釋放內存空進顯示結果結束四、詳細設計 #include <iostream>#include<stdio.h>#include <fstream>#include<stdlib.h>using namespace std; #define Free 0 /空閑狀態#define Busy 1 /已用狀態#define OK 1 /完成#define ERROR 0 /出錯#define MAX_length 640 /最大內存空間為640KBtypedef

7、 int Status; typedef struct freearea/定義一個空閑區說明表結構int ID; /分區號long size; /分區大小long address; /分區地址int state; /狀態ElemType; /- 線性表的雙向鏈表存儲結構 -typedef struct DuLNode /double linked listElemType data; struct DuLNode *prior; /前趨指針struct DuLNode *next; /后繼指針DuLNode,*DuLinkList; DuLinkList block_first; /頭結點Du

8、LinkList block_mid;DuLinkList block_last; /尾結點 Status alloc(int);/內存分配Status alloc2(int);/內存分配2Status free(int); /內存回收Status First_fit(int,int); /首次適應算法Status CycleFirst_fit(int,int);/循環首次適應算法Status Best_fit(int,int); /最佳適應算法void show();/查看分配Status Initblock();/開創空間表int ID,request;long adds=0; Statu

9、s Initblock()/開創帶頭結點的內存空間鏈表block_first=(DuLinkList)malloc(sizeof(DuLNode);block_last=(DuLinkList)malloc(sizeof(DuLNode);block_mid=(DuLinkList)malloc(sizeof(DuLNode);block_first->prior=NULL;block_first->next=block_mid;block_mid->next=block_last;block_mid->prior=block_first;block_last->

10、prior=block_mid;block_last->next=NULL;block_mid->data.address=0;block_mid->data.size=MAX_length;block_mid->data.ID=0;block_mid->data.state=Free;return OK; /- 分 配 主 存 -Status alloc(int ch)if(request<0 |request=0) cout<<"分配大小不合適，請重試！"<<endl;return ERROR; switch(

11、ch) case 1:if(First_fit(ID,request)=OK) cout<<"分配成功！"<<endl;else cout<<"內存不足，分配失敗！"<<endl;ID=0;request=0;return OK;break;case 2:if(CycleFirst_fit(ID,request)=OK) cout<<"分配成功！"<<endl;else cout<<"內存不足，分配失敗！"<<endl;

12、ID=0;request=0;return OK;break;case 3:if(Best_fit(ID,request)=OK) cout<<"分配成功！"<<endl;else cout<<"內存不足，分配失敗！"<<endl;ID=0;request=0;return OK;break;default:cout<<"*ERROR!*"Status alloc2(int ch)int ID,request;cout<<"請輸入作業(分區號)：&quo

13、t; cin>>ID;cout<<"請輸入需要分配的主存大小(單位:KB)：" cin>>request;if(request<0 |request=0) cout<<"分配大小不合適，請重試！"<<endl;return ERROR; switch(ch) case 1:if(First_fit(ID,request)=OK) cout<<"分配成功！"<<endl;else cout<<"內存不足，分配失敗！"

14、<<endl;return OK;break;case 2:if(CycleFirst_fit(ID,request)=OK) cout<<"分配成功！"<<endl;else cout<<"內存不足，分配失敗！"<<endl;return OK;break;case 3:if(Best_fit(ID,request)=OK) cout<<"分配成功！"<<endl;else cout<<"內存不足，分配失敗！"<

15、<endl;return OK;break;default:cout<<"*ERROR!*"/- 首次適應算法 -Status First_fit(int ID,int request)/傳入作業名及申請量/為申請作業開辟新空間且初始化DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode); temp->data.ID=ID; temp->data.size=request;temp->data.state=Busy; DuLNode *p=block_first->next;while

16、(p)if(p->data.state=Free && p->data.size=request)/有大小恰好合適的空閑塊p->data.state=Busy;p->data.ID=ID;return OK;break;if(p->data.state=Free && p->data.size>request)/有空閑塊能滿足需求且有剩余"temp->prior=p->prior;temp->next=p; temp->data.address=p->data.address;p-

17、>prior->next=temp; p->prior=temp;p->data.address=temp->data.address+temp->data.size;p->data.size-=request;return OK;break;p=p->next;return ERROR;/- 循環首次適應算法 -Status CycleFirst_fit(int ID,int request)/傳入作業名及申請量/為申請作業開辟新空間且初始化DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode);

18、temp->data.ID=ID; temp->data.size=request;temp->data.state=Busy; DuLNode *p=block_first->next;while(p)if(p->data.state=Free && p->data.size=request)/有大小恰好合適的空閑塊p->data.state=Busy;p->data.ID=ID;return OK;break;if(p->data.state=Free && p->data.size>requ

19、est&&p->data.address=adds)/有空閑塊能滿足需求且有剩余"temp->prior=p->prior;temp->next=p; temp->data.address=p->data.address;p->prior->next=temp; p->prior=temp;p->data.address=temp->data.address+temp->data.size;adds=p->data.address;p->data.size-=request;cout&

20、lt;<adds<<endl;return OK;break;if(request>p->next->data.size&&p->next->data.state=Free)if(First_fit(ID,request)=OK)return OK;p=p->next;return ERROR;/- 最佳適應算法 -Status Best_fit(int ID,int request)int ch; /記錄最小剩余空間DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode); te

21、mp->data.ID=ID; temp->data.size=request;temp->data.state=Busy;DuLNode *p=block_first->next;DuLNode *q=NULL; /記錄最佳插入位置while(p) /初始化最小空間和最佳位置if(p->data.state=Free &&(p->data.size>request | p->data.size=request) )q=p;ch=p->data.size-request;break;p=p->next;while(p)

22、if(p->data.state=Free && p->data.size=request)/空閑塊大小恰好合適p->data.ID=ID;p->data.state=Busy;return OK;break;if(p->data.state=Free && p->data.size>request)/空閑塊大于分配需求if(p->data.size-request<ch)/剩余空間比初值還小ch=p->data.size-request;/更新剩余最小值q=p;/更新最佳位置指向p=p->nex

23、t;if(q=NULL) return ERROR;/沒有找到空閑塊else/找到了最佳位置并實現分配temp->prior=q->prior;temp->next=q;temp->data.address=q->data.address;q->prior->next=temp;q->prior=temp;q->data.address+=request;q->data.size=ch;return OK; /- 主 存 回 收 -Status free(int ID)DuLNode *p=block_first;while(p)if

24、(p->data.ID=ID)p->data.state=Free;p->data.ID=Free;if(p->prior->data.state=Free&&p->next->data.state=Free)/前后都有空閑塊p->prior->data.size+=p->data.size;p->prior->data.size+=p->next->data.size;p->prior->next=p->next->next;p->next->next-&g

25、t;prior=p->prior;adds=p->prior->data.address;cout<<"回收成功n"break;if(p->prior->data.state=Free)/與前面的空閑塊相連p->prior->data.size+=p->data.size;p->prior->next=p->next;p->next->prior=p->prior;adds=p->prior->data.address;if(p->next->data.s

26、tate=Free)/與后面的空閑塊相連 p->data.size+=p->next->data.size;p->next->next->prior=p;p->next=p->next->next;adds=p->prior->data.address;cout<<"回收成功n"break;p=p->next;return OK; /- 顯示主存分配情況 -void show()cout<<"+n"cout<<"+ 主 存 分 配 情 況

27、 +n"cout<<"+n"DuLNode *p=block_first->next;while(p)cout<<"分 區 號："if(p->data.ID=Free) cout<<"Free"<<endl;else cout<<p->data.ID<<endl;cout<<"起始地址："<<p->data.address<<endl;cout<<"分區

28、大小："<<p->data.size<<" KB"<<endl;cout<<"狀 態："if(p->data.state=Free) cout<<"空 閑"<<endl;else cout<<"已分配"<<endl;cout<<""<<endl;p=p->next;if(p=block_last)break; /- 主 函 數-void main()

29、int OpNum;int Sqe100100;FILE *fp;fp=fopen("input.txt","r");if(!fp)cout<<"無法打開文件input.txt"exit(1);fscanf(fp,"%d",&OpNum);for(int ii=0;ii<OpNum;ii+)for(int jj=0;jj<3;jj+)fscanf(fp,"%d",&Sqeiijj);int ch;/算法選擇標記cout<<" 動態分區

30、分配方式的模擬 n"cout<<"*n"cout<<"* 1.首次適應算法 *n"cout<<"* 2.循環首次適應算法 *n"cout<<"* 3.最佳適應算法 *n"cout<<"* 0.退出程序 *n"cout<<"*n"cout<<"請選擇分配算法："cin>>ch;if(ch=0)exit(0);Initblock(); /開創空間表int

31、choice; /操作選擇標記for(int nn=0;nn<OpNum;nn+) cout<<"*n"cout<<"* 1.下一操作 *n"cout<<"* 2.查看分配 *n"cout<<"* 0.退出程序 *n" cout<<"*n" cout<<"請輸入您的操作 ：" cin>>choice;if(choice=1) ID=Sqenn0;request=Sqenn2;if(Sqe

32、nn1=0)cout<<"作業"<<ID<<"申請"<<request<<"KB內存"<<endl;alloc(ch);/操作符為0，則開始分配內存if(Sqenn1=1)cout<<"作業"<<ID<<"釋放"<<request<<"KB內存"<<endl;free(ID);/操作符為1，則釋放內存else if(choice=2)