实验4 可变分区的内存分配算法模拟
1. 实验目的
通过模拟可变分区的以下内存分配算法，掌握连续分配存储器管理的特点，掌握以下四种分配算法的优缺点并进行对比。
（1） 首次适应分配算法； （2） 循环适应分配算法； （3） 最佳适应分配算法； （4） 最坏适应分配算法。
2. 实验环境
装有操作系统Windows XP和开发工具VC++6.0，内存在256M以上的微机； 或者：装有Linux(Fedora 7)操作系统和gcc编译器，内存在256M以上的微机。
3. 实验内容
（1） 用户可用的内存空间为64K，按下面的现有分区情况进行初始化，可在屏幕上显示
当前的内存状态。 起始地址 0K 10K 18K 28K 34K 44K 分区大小 10K 8K 10K 6K 10K 20K 状态 未使用 未使用 未使用 未使用 未使用 未使用 （2）接收用户进程的内存申请格式为：作业名、申请空间的大小。按照上述的一种分配算法进行分配，修改空闲分区表，并在屏幕上显示分配后的内存状态。
（3）用户进程执行完成后，或者从外部撤销用户进程，将内存进行回收，修改空闲分区表，并在屏幕上显示回收后的内存状态。
4. 实验要求
(1) 将四种算法的源程序及程序执行结果写入实验报告； (2) 将四种算法的工作机理写入实验报告。
代码：
#include
#define Free 0 //空闲状态 #define Busy 1 //已用状态 #define OK 1 //完成 #define ERROR 0 //出错
#define MAX_length 64 //最大内存空间为64KB typedef int Status; int flag;
typedef struct freearea//定义一个空闲区说明表结构 {
long size; //分区大小 long address; //分区地址 int state; //状态 }ElemType;
// 线性表的双向链表存储结构 typedef struct DuLNode {
ElemType data;
struct DuLNode *prior; //前趋指针 struct DuLNode *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()//开创带头结点的内存空间链表 {
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->data.state=Free; return OK; }
//分配主存
Status alloc(int ch) {
int request = 0;
cout<<\请输入需要分配的主存大小(单位:KB)：\ cin>>request;
if(request<0 ||request==0) {
cout<<\分配大小不合适，请重试！\ return ERROR; }
if(ch==2) //选择最佳适应算法 {
if(Best_fit(request)==OK) cout<<\分配成功！\ else cout<<\内存不足，分配失败！\ return OK; } if(ch==3) //选择最差适应算法 {
if(Worst_fit(request)==OK) cout<<\分配成功！\ else cout<<\内存不足，分配失败！\ return OK; }
else //默认首次适应算法 {
if(First_fit(request)==OK) cout<<\分配成功！\ else cout<<\内存不足，分配失败！\ 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==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=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;
DuLNode *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 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; }
//最差适应算法
Status 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; //记录最佳插入位置