實驗4 可變分區(qū)的內(nèi)存分配算法

1、實驗4 可變分區(qū)的內(nèi)存分配算法模擬1. 實驗目的通過模擬可變分區(qū)的以下內(nèi)存分配算法，掌握連續(xù)分配存儲器管理的特點，掌握以下四種分配算法的優(yōu)缺點并進行對比。（1） 首次適應分配算法；（2） 循環(huán)適應分配算法；（3） 最佳適應分配算法；（4） 最壞適應分配算法。2. 實驗環(huán)境裝有操作系統(tǒng)Windows XP和開發(fā)工具VC+6.0，內(nèi)存在256M以上的微機；或者：裝有Linux(Fedora 7)操作系統(tǒng)和gcc編譯器，內(nèi)存在256M以上的微機。3. 實驗內(nèi)容（1） 用戶可用的內(nèi)存空間為64K，按下面的現(xiàn)有分區(qū)情況進行初始化，可在屏幕上顯示當前的內(nèi)存狀態(tài)。起始地址分區(qū)大小狀態(tài)0K10K未使用10K8

2、K未使用18K10K未使用28K6K未使用34K10K未使用44K20K未使用（2）接收用戶進程的內(nèi)存申請格式為：作業(yè)名、申請空間的大小。按照上述的一種分配算法進行分配，修改空閑分區(qū)表，并在屏幕上顯示分配后的內(nèi)存狀態(tài)。（3）用戶進程執(zhí)行完成后，或者從外部撤銷用戶進程，將內(nèi)存進行回收，修改空閑分區(qū)表，并在屏幕上顯示回收后的內(nèi)存狀態(tài)。4. 實驗要求(1) 將四種算法的源程序及程序執(zhí)行結果寫入實驗報告；(2) 將四種算法的工作機理寫入實驗報告。代碼：#include<iostream.h>#include<stdlib.h>#define Free 0 /空閑狀態(tài)#defin

3、e Busy 1 /已用狀態(tài)#define OK 1 /完成#define ERROR 0 /出錯#define MAX_length 64 /最大內(nèi)存空間為64KBtypedef int Status;int flag;typedef struct freearea/定義一個空閑區(qū)說明表結構 long size; /分區(qū)大小 long address; /分區(qū)地址 int state; /狀態(tài)ElemType;/ 線性表的雙向鏈表存儲結構typedef struct DuLNode ElemType data; struct DuLNode *prior; /前趨指針 struct DuLN

4、ode *next; /后繼指針DuLNode,*DuLinkList; DuLinkList block_first; /頭結點DuLinkList block_last; /尾結點Status alloc(int);/內(nèi)存分配Status free(int); /內(nèi)存回收Status First_fit(int);/首次適應算法Status Best_fit(int); /最佳適應算法Status Worst_fit(int); /最差適應算法void show();/查看分配Status Initblock();/開創(chuàng)空間表 Status Initblock()/開創(chuàng)帶頭結點的內(nèi)存空間鏈

5、表 block_first=(DuLinkList)malloc(sizeof(DuLNode); block_last=(DuLinkList)malloc(sizeof(DuLNode); block_first->prior=NULL; block_first->next=block_last; block_last->prior=block_first; block_last->next=NULL; block_last->data.address=0; block_last->data.size=MAX_length; block_last->

6、;data.state=Free; return OK; /分配主存Status alloc(int ch) int request = 0; cout<<"請輸入需要分配的主存大小(單位:KB)：" cin>>request; if(request<0 |request=0) cout<<"分配大小不合適，請重試！"<<endl; return ERROR; if(ch=2) /選擇最佳適應算法 if(Best_fit(request)=OK) cout<<"分配成功！&quo

7、t;<<endl; else cout<<"內(nèi)存不足，分配失敗！"<<endl; return OK; if(ch=3) /選擇最差適應算法 if(Worst_fit(request)=OK) cout<<"分配成功！"<<endl; else cout<<"內(nèi)存不足，分配失??！"<<endl; return OK; else /默認首次適應算法 if(First_fit(request)=OK) cout<<"分配成功！&quo

8、t;<<endl; else cout<<"內(nèi)存不足，分配失??！"<<endl; return OK; /首次適應算法Status First_fit(int request) /為申請作業(yè)開辟新空間且初始化 DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode); temp->data.size=request; temp->data.state=Busy; DuLNode *p=block_first->next; while(p) if(p->data.state

9、=Free && p->data.size=request) /有大小恰好合適的空閑塊 p->data.state=Busy; 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->prior->next=temp; p->prior

10、=temp; p->data.address=temp->data.address+temp->data.size; p->data.size-=request; return OK; break; p=p->next; return ERROR;/最佳適應算法Status Best_fit(int request) int ch; /記錄最小剩余空間 DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode); temp->data.size=request; temp->data.state=Busy; D

11、uLNode *p=block_first->next; DuLNode *q=NULL; /記錄最佳插入位置 while(p) /初始化最小空間和最佳位置 if(p->data.state=Free && (p->data.size>=request) ) if(q=NULL)q=p;ch=p->data.size-request;else if(q->data.size > p->data.size)q=p;ch=p->data.size-request; p=p->next; if(q=NULL) return

12、ERROR;/沒有找到空閑塊 else if(q->data.size=request) q->data.state=Busy; return OK; 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; return OK; /最差適應算法Sta

13、tus Worst_fit(int request) int ch; /記錄最大剩余空間 DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode); 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)

14、) if(q=NULL)q=p;ch=p->data.size-request;else if(q->data.size < p->data.size)q=p;ch=p->data.size-request; p=p->next; if(q=NULL) return ERROR;/沒有找到空閑塊 else if(q->data.size=request) q->data.state=Busy; return OK; else temp->prior=q->prior; temp->next=q; temp->data.ad

15、dress=q->data.address; q->prior->next=temp; q->prior=temp; q->data.address+=request; q->data.size=ch; return OK; return OK;/主存回收Status free(int flag) DuLNode *p=block_first;for(int i= 0; i <= flag; i+)if(p!=NULL)p=p->next;elsereturn ERROR;p->data.state=Free; if(p->prior

16、!=block_first && p->prior->data.state=Free)/與前面的空閑塊相連 p->prior->data.size+=p->data.size; p->prior->next=p->next; p->next->prior=p->prior;p=p->prior; if(p->next!=block_last && p->next->data.state=Free)/與后面的空閑塊相連 p->data.size+=p->next-

17、>data.size; p->next->next->prior=p; p->next=p->next->next; if(p->next=block_last && p->next->data.state=Free)/與最后的空閑塊相連 p->data.size+=p->next->data.size; p->next=NULL; return OK; /顯示主存分配情況void show()int flag = 0; cout<<"n主存分配情況:n" cou

18、t<<"+nn" DuLNode *p=block_first->next;cout<<"分區(qū)號t起始地址t分區(qū)大小t狀態(tài)nn" while(p) cout<<" "<<flag+<<"t" cout<<" "<<p->data.address<<"tt" cout<<" "<<p->data.size<<&

19、quot;KBtt" if(p->data.state=Free) cout<<"空閑nn" else cout<<"已分配nn" p=p->next; cout<<"+nn" /主函數(shù)void main() int ch;/算法選擇標記 cout<<"請輸入所使用的內(nèi)存分配算法：n" cout<<"(1)首次適應算法n(2)最佳適應算法n(3)最差適應算法n" cin>>ch;while(ch<

20、1|ch>3)cout<<"輸入錯誤，請重新輸入所使用的內(nèi)存分配算法：n"cin>>ch; Initblock(); /開創(chuàng)空間表 int choice; /操作選擇標記 while(1) show();cout<<"請輸入您的操作：" cout<<"n1: 分配內(nèi)存n2: 回收內(nèi)存n0: 退出n" cin>>choice; if(choice=1) alloc(ch); / 分配內(nèi)存 else if(choice=2) / 內(nèi)存回收 int flag; cout<<"請輸入您要釋放的分區(qū)號：" cin>