课程设计3

题目3：动态分区式存储管理的存储分配和回收

一、设计目的

1、理解动态分区式存储管理的工作原理

2、掌握分区分配的一下三算法：首先适应算法、最佳适应算法和最坏适应算法

3、掌握动态分区分配的存储分配和存储回收的过程

二、设计要求

1、建立空闲分区表数据文件，该文件包括两个字段：空闲区的起始地址和长度；该文件有若干个记录，表示目前系统有多个空闲分区；

2、建立已分配分区表数据文件，该文件包括三个字段：已分配分区的起始地址、长度、作业名称；该文件有若干个记录，表示目前系统有多个作业；

3、程序启动时读两分区表数据文件，并在屏幕上显示内存的使用状态

3、接受用户的内存申请，格式：作业名、申请空间的大小

4、分别按照三种内存分配算法，选择一个空闲分区，分割，修改空闲分区表、填写已分配分区表；

5、接收作业结束信息，回收分配给作业的分区，必要时合并空闲分区，改写两个分区表；

6、在接受用户的内存申请时，当申请空间的大小大于目前任意一个空闲分区而小于若干个空闲分区的大小之和时，分配前进行碎片整理

/*******题目3：动态分区式存储管理的存储分配和回收2010.1.1biao*******/
#include"stdafx.h"
#include<iostream>
#include<windows.h>
#include<stdlib.h>
usingnamespacestd;
constintMAXJOB=100;//定义表最大记录数
typedefstructnode{
intstart;//起始地址
intlength;//长度
chartag[20];//作业名称
}job;
jobfrees[MAXJOB];//定义空闲区表
intfree_quantity;
joboccupys[MAXJOB];//定义已分配区表
intoccupy_quantity;
voidinitial(){
//分配表//52204022共114
occupys[0].start=1;
occupys[0].length=52;
strcpy(occupys[0].tag,"A");
occupys[1].start=52;
occupys[1].length=20;//到72到97空闲
strcpy(occupys[1].tag,"B");
occupys[2].start=98;//72-98空闲区26
occupys[2].length=40;
strcpy(occupys[2].tag,"C");
occupys[3].start=148;
occupys[3].length=22;
strcpy(occupys[3].tag,"D");
//空闲表//261086共122
frees[0].start=72;
frees[0].length=26;
strcpy(frees[0].tag,"free");
frees[1].start=138;
frees[1].length=10;
strcpy(frees[1].tag,"free");
frees[2].start=170;
frees[2].length=86;//共256
strcpy(frees[2].tag,"free");
free_quantity=3;
occupy_quantity=4;
}
//使用冒泡算法的空闲分区进行排列
voidinitialSort(inta){
inti,j;
if(a==2){//102686空闲分区按其容量从小到大的顺序形成一空闲分区链
for(i=0;i<free_quantity;i++){
for(j=free_quantity-1;j>0;j--){
if(frees[j].length<frees[j-1].length){
frees[MAXJOB-1]=frees[j];
frees[j]=frees[j-1];
frees[j-1]=frees[MAXJOB-1];
}
}
}
}
if(a==3){//862610空闲分区按其容量从大到小的顺序形成一空闲分区链
for(i=0;i<free_quantity;i++){
for(j=free_quantity-1;j>0;j--){
if(frees[j].length>frees[j-1].length){
frees[MAXJOB-1]=frees[j];
frees[j]=frees[j-1];
frees[j-1]=frees[MAXJOB-1];
}
}
}
}
}

//使用冒泡算法的分配表进行排列按地址从小到大连接
voidoccupySort(){
inti,j;
for(i=0;i<occupy_quantity;i++){
for(j=occupy_quantity-1;j>0;j--){
if(occupys[j].start<occupys[j-1].start){
occupys[MAXJOB-1]=occupys[j];
occupys[j]=occupys[j-1];
occupys[j-1]=occupys[MAXJOB-1];
}
}
}
}
//使用冒泡算法的空闲表进行排列按地址从小到大连接
voidfreeSort(){
inti,j;
for(i=0;i<free_quantity;i++){
for(j=free_quantity-1;j>0;j--){
if(frees[j].start<frees[j-1].start){
frees[MAXJOB-1]=frees[j];
frees[j]=frees[j-1];
frees[j-1]=frees[MAXJOB-1];
}
}
}
}
//碎片整理处理进行碎片整理时，都对两个分区表进行按地址从小到大的排序。
intdefragmentation(intjob_length){
inti,flag;//作为是否需要紧凑的标志
intflag2=0;
intlengthAcount,k;//lengthAcount:计数空闲的大小K：计数多少个空闲分区才足够分配。
intM;//性质同k
intnumber=0;//分配表移动的次数
inttemp=0;
lengthAcount=0;
flag=0;
freeSort();//判断前先队空闲表按地址从小到大连接
for(i=0;i<free_quantity;i++){
lengthAcount+=frees[i].length;
if(lengthAcount>=job_length){
k=i+1;
M=k;
flag=1;
}
}
if(flag==0){
cout<<endl<<"Sorry,当前没有能满足你申请长度的空闲内存,请稍候再试"<<endl;
}else
{
cout<<endl<<"########你好！正在进行碎片整理,请稍候"<<endl;
Sleep(2000);
if(k==free_quantity){//须全部整理才能满足要求的情况
occupySort();
if(occupy_quantity>0){//确定分配表是有作业的
for(i=1;i<occupy_quantity;i++){
if(occupys[0].start!=1){
occupys[0].start=1;
}
occupys[i].start=occupys[i-1].start+occupys[i-1].length;
}
free_quantity=1;
frees[0].start=occupys[occupy_quantity-1].start+occupys[occupy_quantity-1].length;
frees[0].length=256-frees[0].start+1;
cout<<"########碎片整理成功！"<<endl;
return1;
}
}else{//须整理K个即可。
while(k>0){
if(occupys[0].start==1){
for(i=1;i<occupy_quantity;i++){
if(occupys[i].start!=occupys[i-1].start+occupys[i-1].length){//如果当前跳=的头不等于上一跳的尾巴，则前移
number++;//移动次数
if(occupys[i+1].start==occupys[i].start+occupys[i].length){//标志下一次的移动是没用的。
flag2=1;
}
occupys[i].start=occupys[i-1].start+occupys[i-1].length;//向前移动
if(flag2==0){//移动是有效的则减1
k--;
}
}
}
}else{
for(i=0;i<occupy_quantity;i++){
if(i==0){
if(occupys[1].start==occupys[0].start+occupys[0].length){//下一次无效
flag2=1;
}
number++;//移动次数加1
occupys[0].start=1;
k--;
}else{
if(occupys[i].start!=occupys[i-1].start+occupys[i-1].length){
number++;//移动次数加1
if(i>1){//第二次来的时候已又上一次作好判断了
if(occupys[i+1].start==occupys[i].start+occupys[i].length){//标志下一次的移动是没用的。
flag2=1;
}else{
flag2=0;
}
}
occupys[i].start=occupys[i-1].start+occupys[i-1].length;//向前移动
if(flag2==0){//移动是有效的则减1
k--;
}
}
}
}
}
}
//空闲分区表的处理
for(i=0;i<M;i++){//第一个空闲区的长度
temp+=frees[i].length;
}
frees[0].length=temp;
temp=0;
for(i=0;i<number;i++){
temp+=occupys[i].length;
}
frees[0].start=temp;//第一个空闲区的起始地址
for(i=1;i<free_quantity-M;i++){//移动空闲区
frees[i]=frees[M+i];
}
cout<<"########碎片整理成功！"<<endl;
return1;
}
}
return0;
}
//首先适应分配算法
voidearliest()
{
charjob_name[20];
intjob_length;
inti,j,flag,t;//flag:1表示找到符合要求的空间0表示未找到
cout<<"请输入新申请内存空间的作业名和空间大小:";
cin>>job_name;
cin>>job_length;

flag=0;
for(i=0;i<free_quantity;i++){
if(frees[i].length>=job_length){
flag=1;
}
}
if(flag==0){//未找到******************紧凑处理****************
flag=defragmentation(job_length);
}
if(flag==1){//找到处理
t=0;
i=0;
while(t==0){
if(frees[i].length>=job_length){
t=1;
}
i++;
}
i--;
occupys[occupy_quantity].start=frees[i].start;//处理第一个找到的满足要求的空闲区
strcpy(occupys[occupy_quantity].tag,job_name);
occupys[occupy_quantity].length=job_length;
occupy_quantity++;
//修改空闲区表
if(frees[i].length>job_length){//有剩余空闲单元
frees[i].start+=job_length;
frees[i].length-=job_length;
}
else{//无剩余空闲单元
for(j=i;j<free_quantity-1;j++){
frees[j]=frees[j+1];
}
free_quantity--;
}
cout<<"恭喜你，申请内存空间成功!"<<endl;
}
}
//最优适应分配算法
voidexcellent()
{
charjob_name[20];
intjob_length;
inti,j,flag,t;
cout<<"请输入新申请内存空间的作业名和空间大小:";
cin>>job_name;
cin>>job_length;

flag=0;
for(i=0;i<free_quantity;i++){
if(frees[i].length>=job_length){
flag=1;
}
}
if(flag==0){//
flag=defragmentation(job_length);
}
if(flag==1){
t=0;
i=0;
while(t==0){
if(frees[i].length>=job_length){
t=1;
}
i++;
}
i--;//i为找到空闲分区的位置。
for(j=0;j<free_quantity;j++){//============
if((frees[j].length>=job_length)&&(frees[j].length<frees[i].length)){
i=j;
}
}
occupys[occupy_quantity].start=frees[i].start;
strcpy(occupys[occupy_quantity].tag,job_name);
occupys[occupy_quantity].length=job_length;
occupy_quantity++;

if(frees[i].length>job_length){
frees[i].start+=job_length;
frees[i].length-=job_length;
}
else{
for(j=i;j<free_quantity-1;j++){
frees[j]=frees[j+1];
}
free_quantity--;
}
cout<<"恭喜你，申请内存空间成功!"<<endl;
initialSort(2);//得对空闲区进行重新排序
}
}

//最坏适应算法
voidworst()
{
charjob_name[20];
intjob_length;
inti,j,flag,t;
cout<<"请输入新申请内存空间的作业名和空间大小:";
cin>>job_name;
cin>>job_length;
flag=0;
for(i=0;i<free_quantity;i++){
if(frees[i].length>=job_length){
flag=1;
}
}
if(flag==0){
flag=defragmentation(job_length);
}
if(flag==1){
t=0;
i=0;
while(t==0){
if(frees[i].length>=job_length){
t=1;
}
i++;
}
i--;
for(j=0;j<free_quantity;j++){
if((frees[j].length>=job_length)&&(frees[j].length>frees[i].length)){
i=j;
}
}
occupys[occupy_quantity].start=frees[i].start;
strcpy(occupys[occupy_quantity].tag,job_name);
occupys[occupy_quantity].length=job_length;
occupy_quantity++;
if(frees[i].length>job_length){
frees[i].start+=job_length;
frees[i].length-=job_length;
}
else{
for(j=i;j<free_quantity-1;j++){
frees[j]=frees[j+1];
}
free_quantity--;
}
cout<<"恭喜你，申请内存空间成功!"<<endl;
initialSort(3);//得对空闲区进行重新排序
}
}
//显示函数
voidview()
{
inti;
cout<<"----------------------------------------------------------"<<endl;
cout<<"当前空闲表:"<<endl;
cout<<"起始地址/t长度/t状态/n";
for(i=0;i<free_quantity;i++){
cout<<frees[i].start<<"/t/t"<<frees[i].length<<'/t'<<frees[i].tag<<endl;
}

cout<<endl<<"----------------------------------------------------------"<<endl;
cout<<"当前已分配表:"<<endl;
cout<<"起始地址/t长度/t占用作业名/n";

for(i=0;i<occupy_quantity;i++){
cout<<occupys[i].start<<"/t/t"<<occupys[i].length<<'/t'<<occupys[i].tag<<endl;
}
}
//撤消作业此处该修改空闲区的flag的值
voidfinished(intwhichOne)//whichOne作为参数负责对处理后的空闲区表排序
{
charjob_name[20];
inti,j,flag,p=0;
intstart;//被撤消作业的起始位置
intlength;//被撤消作业的长度
cout<<"请输入要撤消的作业名:";
cin>>job_name;
flag=-1;
for(i=0;i<occupy_quantity;i++){
if(!strcmp(occupys[i].tag,job_name)){
flag=i;//标记该作业，删除处理。
start=occupys[i].start;
length=occupys[i].length;
}
}
if(flag==-1){
cout<<"没有这个作业名"<<endl;
}
else{//找到所要撤消的作业名，加入空闲表
for(i=0;i<free_quantity;i++){
if((frees[i].start+frees[i].length)==start){//情况一：所撤消的作业起始位置和前一个空闲区的尾巴相接
if(((i+1)<free_quantity)&&(frees[i+1].start==start+length)){//所释放的作业正好处于两块空闲区的中间，而且都接上了。
frees[i].length=frees[i].length+frees[i+1].length+length;//第i个地方合并。
for(j=i+1;j<free_quantity;j++){//从i的下一位开始往前移一位。
frees[j]=frees[j+1];
}
free_quantity--;//空闲区块数减少一块，是由于其他2个空闲的加一个释放的作业合并所制。
p=1;
}
else{
frees[i].length+=length;
p=1;
}
}
if(frees[i].start==(start+length)){//情况二：所撤消的作业末尾位置和下一个空闲区的起始位置相接
frees[i].start=start;
frees[i].length+=length;
p=1;
}
}
if(p==0){//情况三：未找到任何的连接，则添加到末尾处
frees[free_quantity].start=start;
frees[free_quantity].length=length;
strcpy(frees[free_quantity].tag,"free");//设置该分区为空闲
free_quantity++;
}
//删除分配表中的该作业
for(i=flag;i<occupy_quantity;i++){
occupys[i]=occupys[i+1];//直接将其替换，冲掉该作业的值即可
}
occupy_quantity--;
}
if(whichOne!=1){//只要不是第一种算法则进行排序
initialSort(whichOne);
}
}
/**********主函数***********/
intmain()
{
intt=1;
intchioce=0;
intflag0=1;
intflag=1;
inta;
cout<<"程序启动读两分区表，并在屏幕上显示内存的使用情况。"<<endl;
state:
initial();
view();

cout<<"请选择分区分配算法：1.首先适应算法2.最佳适应算法3.最坏适应算法"<<endl;
cin>>a;
if(a==2||a==3){
initialSort(a);
}
system("cls");
while(flag==1){
cout<<"========================================================="<<endl;
cout<<"动态分区式存储管理模拟系统"<<endl;
cout<<"========================================================="<<endl;
cout<<"1.申请空间2.撤消作业3.显示空闲表和分配表4.重新选择算法模拟0.退出"<<endl;
cout<<"请选择:";
cin>>chioce;
switch(chioce){
case1:
switch(a){
case1:earliest();break;
case2:excellent();break;
case3:worst();break;
}
break;
case2:
finished(a);
break;
case3:
view();
break;
case4:
system("cls");
gotostate;
break;
case0:
exit(1);
default:
cout<<"选择错误!"<<endl;
}
}
return0;
}

关于代码做个小小的总结：该代码在VC 6.0 下，运行无错误！不足：1.在做排序时所用的中间变量为数组的最后一个，没另外定义。2.关于作业名的唯一性没有进行检测。检测代码大概如下：（请自行调用）

//可改成相应的函数，以便调用
inttest=0;
intf=0;
while(test==0){
for(inti=0;i<occupy_quantity;i++){
if((strcmp(occupy[i].tag,job_name)!=-1){
cout<<"作业名已存在，请重新输入"<<endl;
f=1;
cin>>job_name;
break;
}
}
if(f==1){
test=0;
}else{
test=1;
}

}