#include<iostream>
#include<stdlib.h>
using namespace std;
#define Free 0
#define Busy 1
#define OK 1
#define ERROR 0
#define MAX_length 640
struct freepartition {
int ID;
int size;
int address;
int state;
};
typedef struct node {
freepartition data;
struct node *prior;
struct node *next;
} node,*Linklist;
Linklist first;
Linklist last;
int alloc(int);
int free(int);
int First_fit(int,int);
int Best_fit(int,int);
void show();
int Initblock();
int Initblock() {
first=(Linklist)malloc(sizeof(node));
last=(Linklist)malloc(sizeof(node));
first->prior=NULL;
first->next=last;
last->prior=first;
last->next=NULL;
last->data.address=0;
last->data.size=MAX_length;
last->data.ID=0;
last->data.state=Free;
return OK;
}
int allocation(int ch,int ID,int request) {
if(request<0 ||request==0) {
cout<<"分配大小不合适，请重试！"<<endl;
return ERROR;
}
if(ch==2) { //选择最佳适应算法
if(Best_fit(ID,request)==OK) cout<<"分配成功！"<<endl;
else cout<<"内存不足，分配失败！"<<endl;
return OK;
} else { //首次适应算法
if(First_fit(ID,request)==OK) cout<<"分配成功！"<<endl;
else cout<<"内存不足，分配失败！"<<endl;
return OK;
}
}
//------------------ 首次适应算法 -----------------------
int First_fit(int ID,int request) {
//传入作业名及申请的空间大小
//为申请作业开辟新空间且初始化
Linklist temp=(Linklist)malloc(sizeof(node));
temp->data.ID=ID;
temp->data.size=request;
temp->data.state=Busy;
node *p=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>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;
}
//--------------------最佳适应算法------------------------
int Best_fit(int ID,int request) {
int ch; //记录最小剩余空间
Linklist temp=(Linklist)malloc(sizeof(node));
temp->data.ID=ID;
temp->data.size=request;
temp->data.state=Busy;
node *p=first->next;
node *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) {
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->next;
}
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;
}
}
//----------------------- 主 存 回 收 --------------------
int free(int ID) {
cout<<"释放成功"<<endl;
node *p=first;
while(p) {
if(p->data.ID==ID) {
p->data.state=Free;
p->data.ID=Free;
if(p->prior->data.state==Free && p!=first->next) { //与前面的空闲块相邻
p->prior->data.size+=p->data.size;
p->prior->next=p->next;
p->next->prior=p->prior;
}
if(p->next->data.state==Free) { //与后面的空闲块相连
p->data.size+=p->next->data.size;
p->next->next->prior=p;
p->next=p->next->next;
}
break;
}
p=p->next;
}
return OK;
}
//--------------- 显示主存分配情况 ------------------
void show() {
node *p=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<<"分区大小："<<p->data.size<<" KB"<<endl;
cout<<"状 态：";
if(p->data.state==Free) cout<<"空闲"<<endl;
else cout<<"已分配"<<endl;
cout<<"--------------"<<endl;
p=p->next;
}
cout<<"**************************"<<endl;
}
//----------------------- 主 函 数---------------------------
int main() {
int ch; //算法选择
while(1) {
cout<<"1.首次适应算法2.最佳适应算法3.退出\n";
cout<<"请选择相应的操作：";
cin>>ch;
switch(ch) {
case 1:
Initblock(); //开创空间表
allocation(ch,1,130);
show();
allocation(ch,2,60);
show();
allocation(ch,3,100);
show();
free(2);
show();
allocation(ch,4,200);
show();
free(3);
show();
free(1);
show();
allocation(ch,5,140);
show();
allocation(ch,6,60);
show();
allocation(ch,7,50);
show();
free(6);
show();
break;
case 2:
Initblock(); //开创空间表
allocation(ch,1,130);
show();
allocation(ch,2,60);
show();
allocation(ch,3,100);
show();
free(2);
show();
allocation(ch,4,200);
show();
free(3);
show();
free(1);
show();
allocation(ch,5,140);
show();
allocation(ch,6,60);
show();
allocation(ch,7,50);
show();
free(6);
show();
break;
case 3:
exit(1);
break;
}
}
return 0;
}
