动态分区分配算法的详细过程
动态分区分配算法的详细过程
#include
#include
#include
#define L 10
using namespace std;
typedef struct LNode
{int startaddress;
int size;
int state;
}LNode;
LNode P[L]={{120,40,0},{170,30,0},{20,60,0},{90,10,0},{220,50,0}};
int N=5;
void print() //输出
{int i;
printf("起始地址 地址长度 状态\n");
for(i=0;i
{printf("%8d %8d %4d\n",P[i].startaddress,P[i].size,P[i].state);}
}
void sort(int k) //排序
{int i,j;
LNode temp;
if(k==1) //起始地址递增
{for(i=0;i
for(j=i;j
{if(P[i].startaddress>P[j].startaddress)
{temp=P[i];P[i]=P[j];P[j]=temp;}
}
}
else if(k==2) //地址长度递减
{for(i=0;i
for(j=i;j
{if(P[i].size
{temp=P[i];P[i]=P[j];P[j]=temp;}
}
}
else //地址长度递增
{for(i=0;i
for(j=i;j
{if(P[i].size>P[j].size)
{temp=P[i];P[i]=P[j];P[j]=temp;}
}
}
}
void splice(int m) //拼接
{int i,j=0,n=P[0].startaddress,l=P[0].startaddress,s=P[0].size;
for(i=1;i
{if(j>P[i].startaddress)n=P[i].startaddress;
if(l
s+=P[i].size;
}
P[1].startaddress=l+P[N-1].size;P[1].state=1;
P[0].startaddress=n;P[0].size=s;P[0].state=0;
for(i=2;i
{P[i].size=0;P[i].startaddress=0;P[i].state=0;}
N=2;
if(P[0].size==m)
P[0].state=1;
else
{P[N].startaddress=P[0].startaddress+s;P[N].size=s-m;P[N].state=0;N++;}
printf("地址成功分配\n\n");printf("地址分配成功后的状态：\n");
}
int allocation(int k) //分配
{int i,l=0,m,f,s;
printf("\n输入请求分配分区的大小：");
scanf("%d",&m);
if(k==1||k==3)
for(i=0;i
{if(P[i].size
else if(P[i].size==m){P[i].state=1;l=1;break;}
else
{P[N].startaddress=P[i].startaddress+m;P[N].size=P[i].size-m;P[i].size=m;P[i].state=1;l=1;N++;break;}
}
else
{if(P[0].size>=m)
if(P[0].size==m){P[0].state=1;l=1;}
else
{f=P[0].size;P[0].size=m;P[0].state=1;P[N].startaddress=P[0].startaddress+m;P[N].size=f-m;l=1;N++;}
}
if(l==1||i
{for(i=0;i
{s+=P[i].size;}
if(s
printf("没有可以分配的地址空间\n");
else
{printf("拼接后有可以分配的地址空间\n");
splice(m);
}
}
}
void retire() //回收
{int i,j,address,size,n=N;
print();
printf("\n输入要回收的起始地址：");
scanf("%d",&address);
printf("输入要回收的地址长度：");
scanf("%d",&size);
for(i=0;i
{if(address
=P[i].startaddress+P[i].size)continue; if(address==P[i].startaddress) //从已分配的资源开始地址回收
if(P[i].size
{P[N].startaddress=P[i].startaddress+size;P[N].size=P[i].size-size;P[N].state=P[i].state; P[i].startaddress=address;P[i].size=size;P[i].state=0;N++;break;}
else
{P[i].state=0;break;}
else
if(address+size
{P[i].size=address-P[i].startaddress;P[N].startaddress=address;P[N].size=size;P[N].state=0;P[N+1].startaddress=P[N].startaddress+size;
P[N+1].size=P[N+1].startaddress-P[N].startaddress;P[N+1].state=1;N+=2;break;}
else
{P[N].startaddress=address;P[N].size=size;P[N].state=0;P[i].size=address-P[i].startaddress;N++;break;}
}
if(i==n) printf("资源回收失败!\n");
else {printf("\n资源回收后的状态为：\n");print();}
void First()
{printf("\n初始状态为：\n");
print();
sort(1);
printf("\n排序后的状态为：\n");
print();
allocation(1);
sort(1);
retire();
sort(1);
printf("\n排序后的状态为：\n");
print();
}
void Worst()
{printf("\n初始状态为：\n");
print();
sort(2);
printf("\n排序后的状态为：\n");
print();
allocation(2);
sort(2);
retire();
sort(2);
printf("\n排序后的状态为：\n");
print();
}
void Best()
{printf("\n初始状态为：\n");
print();
sort(3);
printf("\n排序后的状态为：\n");
print();
allocation(3);
sort(3);
retire();
sort(3);
printf("\n排序后的状态为：\n");
print();
}
{int k=0;
printf("多级反馈队列调度算法：");
while(k!=4)
{printf("\n1、首次适应算法\n2、最坏适应算法\n3、最佳适应算法\n4、退出\n"); printf("请选择算法：");
scanf("%d",&k);
switch(k)
{case 1:First();continue;
case 2:Worst();continue;
case 3:Best();continue;
case 4:break;
default:printf("选择错误，请重新选择。\n");
}
}
}
int main(int argc, char *argv[])
{input();
system("PAUSE");
return 0;
}