实验4可变分区的内存分配算法

1、实验4 可变分区的内存分配算法模拟1. 实验目的通过模拟可变分区的以下内存分配算法，掌握连续分配存储器管理的特点，掌握以下四种分配算法的优缺点并进行对比。（1） 首次适应分配算法；（2） 循环适应分配算法；（3） 最佳适应分配算法；（4） 最坏适应分配算法。2. 实验环境装有操作系统Windows XP和开发工具VC+6.0，内存在256M以上的微机；或者：装有Linux(Fedora 7)操作系统和gcc编译器，内存在256M以上的微机。3. 实验内容（1） 用户可用的内存空间为64K，按下面的现有分区情况进行初始化，可在屏幕上显示当前的内存状态。起始地址分区大小状态0K10K未使用10K8

2、K未使用18K10K未使用28K6K未使用34K10K未使用44K20K未使用（2）接收用户进程的内存申请格式为：作业名、申请空间的大小。按照上述的一种分配算法进行分配，修改空闲分区表，并在屏幕上显示分配后的内存状态。（3）用户进程执行完成后，或者从外部撤销用户进程，将内存进行回收，修改空闲分区表，并在屏幕上显示回收后的内存状态。4. 实验要求(1) 将四种算法的源程序及程序执行结果写入实验报告；(2) 将四种算法的工作机理写入实验报告。代码：#include<iostream.h>#include<stdlib.h>#define Free 0 /空闲状态#defin

3、e Busy 1 /已用状态#define OK 1 /完成#define ERROR 0 /出错#define MAX_length 64 /最大内存空间为64KBtypedef int Status;int flag;typedef struct freearea/定义一个空闲区说明表结构 long size; /分区大小 long address; /分区地址 int state; /状态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);/内存分配Status free(int); /内存回收Status First_fit(int);/首次适应算法Status Best_fit(int); /最佳适应算法Status Worst_fit(int); /最差适应算法void show();/查看分配Status Initblock();/开创空间表 Status Initblock()/开创带头结点的内存空间链

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<<"内存不足，分配失败！"<<endl; return OK; if(ch=3) /选择最差适应算法 if(Worst_fit(request)=OK) cout<<"分配成功！"<<endl; else cout<<"内存不足，分配失败！"<<endl; return OK; else /默认首次适应算法 if(First_fit(request)=OK) cout<<"分配成功！&quo

8、t;<<endl; else cout<<"内存不足，分配失败！"<<endl; return OK; /首次适应算法Status First_fit(int request) /为申请作业开辟新空间且初始化 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<<"分区号t起始地址t分区大小t状态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" /主函数void main() int ch;/算法选择标记 cout<<"请输入所使用的内存分配算法：n" cout<<"(1)首次适应算法n(2)最佳适应算法n(3)最差适应算法n" cin>>ch;while(ch<

20、1|ch>3)cout<<"输入错误，请重新输入所使用的内存分配算法：n"cin>>ch; Initblock(); /开创空间表 int choice; /操作选择标记 while(1) show();cout<<"请输入您的操作：" cout<<"n1: 分配内存n2: 回收内存n0: 退出n" cin>>choice; if(choice=1) alloc(ch); / 分配内存 else if(choice=2) / 内存回收 int flag; cout<<"请输入您要释放的分区号：" cin>