1、在该实验中，采用可变分区方式完成对存储空间的管理（即存储空间的分配与回收工作）。
2、设计用来记录主存使用情况的数据结构：已分区表和空闲分区表或链表。
3、在设计好的数据结构上设计一个主存分配算法（循环首次适应算法）。
4、在设计好的数据结构上设计一个主存回收算法。其中，若回收的分区有上邻空闲分区和（或）下邻空闲分区，要求合并为一个空闲分区登记在空闲分区表的一个表项里。
注：该代码暂时有bug！
实验代码:
#include<iostream>
using namespace std;
int freeNUM;
struct AREA {
int address;
int size;
int state;
};
typedef struct LNode {
AREA data;
struct LNode *prior;
struct LNode *next;
} LNode, *LinkList;
LinkList AFIRST;
LinkList ALAST;
void alloc(LNode *p);
void free(int);
int NF(int,LNode *);
void ShowData();
void initLList();
void initLList(int MAX_length) {
AFIRST=new(LNode);
ALAST=new(LNode);
AFIRST->prior=NULL;
AFIRST->next=ALAST;
ALAST->prior=AFIRST;
ALAST->next=NULL;
ALAST->data.address=0;
ALAST->data.size=MAX_length;
ALAST->data.state=0;
}
void apply(LNode *p) {
int request;
cout<<"输入进程所需分配的空间大小：";
cin>>request;
if(request<0||request==0) cout<<"输入错误，内存大小不能小于等于0 请重新输入";
else {
if(NF(request,p)==1) cout<<"分配成功！";
else cout<<"内存不足分配失败！";
}
}
int NF(int request,LNode *p) {
LinkList temp =new(LNode);
temp->data.size=request;
temp->data.state=1;
while(p) {
if(p->data.state==0&&p->data.size==request) {
p->data.state=1;
return 1;
}
if(p->data.state==0&&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=p->data.size-request;
return 1;
}
p=p->next;
}
}
void free(int freeNUM) {
LNode *p = AFIRST;
for(int i=0; i<=freeNUM; i++) {
if(p!=NULL) {
p=p->next;
}
}
p->data.state=0;
if(p->next==NULL&&p->prior->data.state==0) {
p->prior->prior->data.size+=p->prior->data.size+p->data.size;
p->prior->prior->next=NULL;
}
if(p->prior->data.state==0&&p->next->data.state!=0) {
p->prior->data.size+=p->data.size;
p->prior->next=p->next;
p->next->prior=p->prior;
p=p->prior;
} else if(p->prior->data.state!=0&&p->next->data.state==0) {
p->next->data.size+=p->data.size;
p->next->data.address=p->data.address;
p->next->prior=p->prior;
p->prior->next=p->next;
p=p->next;
} else if(p->prior->data.state==0&&p->next->data.state==0) {
p->next->data.size+=p->data.size+=p->prior->data.size;
p->next->data.address=p->prior->data.address;
p->next->prior=p->prior->prior;
p->prior->prior->next=p->next;
p=p->next;
}
}
void ShowData() {
int freeNUM=0;
cout<<"\n主存分配情况：\n------------------------------------------------\n";
LNode *q=AFIRST->next;
cout<<"分区号\t起始地址\t分区大小\t状态\n";
while(q) {
cout<<" "<<freeNUM;
freeNUM++;
cout<<"\t"<<q->data.address;
cout<<"KB\t\t"<<q->data.size;
if(q->data.state==0) cout<<"\t\t空闲\n";
else cout<<"\t\t已分配\n";
q=q->next;
}
cout<<"------------------------------------------------\n";
}
int main() {
int c=1;
int MAX_length;
cout<<"输入初始空闲片的大小：";
cin>>MAX_length;
initLList(MAX_length);
int choice;
LNode *p = AFIRST->next;
while(1) {
cout<<"1: 分配内存 2:回收内存 3:退出系统 \n";
cout<<"输入您将进行的操作：";
cin>>choice;
if(choice==1) {
apply(p);
ShowData();
} else if(choice==2) {
cout<<"输入您想要回收的空闲块区号：";
cin>>freeNUM;
free(freeNUM);
ShowData();
} else if(choice==3) exit(1);
else cout<<"操作不存在 请重新输入！";
}
return 0;
}
运行结果:
输入初始空闲片的大小：100
1: 分配内存 2:回收内存 3:退出系统
输入您将进行的操作：1
请您输入进程所需分配的空间大小：10
分配成功！
主存分配情况：
分区号 起始地址 分区大小 状态
0 0KB 10 已分配
1 10KB 90 空闲
1: 分配内存 2:回收内存 3:退出系统
输入您将进行的操作：1
请您输入进程所需分配的空间大小：20
分配成功！
主存分配情况：
分区号 起始地址 分区大小 状态
0 0KB 10 已分配
1 10KB 20 已分配
2 30KB 70 空闲
1: 分配内存 2:回收内存 3:退出系统
输入您将进行的操作：1
请您输入进程所需分配的空间大小：30
分配成功！
主存分配情况：
分区号 起始地址 分区大小 状态
0 0KB 10 已分配
1 10KB 20 已分配
2 30KB 30 已分配
3 60KB 40 空闲
1: 分配内存 2:回收内存 3:退出系统
输入您将进行的操作：1
请您输入进程所需分配的空间大小：25
分配成功！
主存分配情况：
分区号 起始地址 分区大小 状态
0 0KB 10 已分配
1 10KB 20 已分配
2 30KB 30 已分配
3 60KB 25 已分配
4 85KB 15 空闲
1: 分配内存 2:回收内存 3:退出系统
输入您将进行的操作：2
输入您想要回收的空闲块区号：0
主存分配情况：
分区号 起始地址 分区大小 状态
0 0KB 10 空闲
1 10KB 20 已分配
2 30KB 30 已分配
3 60KB 25 已分配
4 85KB 15 空闲
1: 分配内存 2:回收内存 3:退出系统
输入您将进行的操作：2
输入您想要回收的空闲块区号：2
主存分配情况：
分区号 起始地址 分区大小 状态
0 0KB 10 空闲
1 10KB 20 已分配
2 30KB 30 空闲
3 60KB 25 已分配
4 85KB 15 空闲
1: 分配内存 2:回收内存 3:退出系统
输入您将进行的操作：2
输入您想要回收的空闲块区号：1
主存分配情况：
分区号 起始地址 分区大小 状态
0 0KB 60 空闲
1 60KB 25 已分配
2 85KB 15 空闲
1: 分配内存 2:回收内存 3:退出系统
输入您将进行的操作：3
