操作系统十大算法之可变分区存储管理

十大题型算法全实现——（二）可变分区存储管理方案中的内存分配作者名：不详出处：北京自考热线05年7月5日可变分区调度算法有:最先适应分配算法,最优适应分配算法,最坏适应算法用户提出内存空间的申请；系统根据申请者的要求，按照一定的分配策略分析内存空间的使用情况，找出能满足请求的空闲区，分给申请者；当程序执行完毕或主动归还内存资源时，系统要收回它所占用的内存空间或它归还的部分内存空间。1．程序运行时首先接收输入：空闲区数据文件，包括若干行，每行有两个数据项：起始地址、长度（均为整数），各数据项以逗号隔开。2．建立空闲区表并在屏幕上显示输出空闲区表内容，空闲区表中记录了内存中可供分配的空闲区的始址和长度，用标志位指出该分区是否是未分配的空闲区。3．从用户界面根据用户提示接收一个内存申请，格式为：作业名、申请空间的大小。4．按照最差（最坏）适配算法选择一个空闲区，分割并分配，修改相应的数据结构（空闲区表），填写内存已分配区表（起始地址、长度、标志位），其中标志位的一个作用是指出该区域分配给哪个作业。5．重复3、4，直到输入为特殊字符（0）。6．在屏幕上显示输出新的空闲区表和已分配区表的内容。本程序包括:FIFO,最优适应分配算法,最坏适应算法VC++调试通过(C)copyrightbyNeo欢迎大家测试请问题请Email:[e-mail]*/#includestdio.h#includeiostream.h#includestring.h#includeiomanip.hconstintMAXJOB=100;//定义表最大记录数typedefstructnode{intstart;intlength;chartag[20];}job;jobfrees[MAXJOB];//定义空闲区表intfree_quantity;joboccupys[MAXJOB];//定义已分配区表intoccupy_quantity;//初始化函数voidinitial(){inti;for(i=0;iMAXJOB;i++){frees[i].start=-1;frees[i].length=0;strcpy(frees[i].tag,free);occupys[i].start=-1;occupys[i].length=0;strcpy(occupys[i].tag,);}free_quantity=0;occupy_quantity=0;}//读数据函数intreadData(){FILE*fp;charfname[20];cout请输入初始空闲表文件名:;cinfname;if((fp=fopen(fname,r))==NULL){cout错误,文件打不开,请检查文件名endl;}else{while(!feof(fp)){fscanf(fp,%d,%d,&frees[free_quantity].start,&frees[free_quantity].length);free_quantity++;}return1;}return0;}//sortvoidsort(){inti,j,p;for(i=0;ifree_quantity-1;i++){p=i;for(j=i+1;jfree_quantity;j++){if(frees[j].startfrees[p].start){p=j;}}if(p!=i){frees[free_quantity]=frees[i];frees[i]=frees[p];frees[p]=frees[free_quantity];}}}//显示函数voidview(){inti;coutendl----------------------------------------------------------endl;cout当前空闲表:endl;cout起始地址长度状态endl;for(i=0;ifree_quantity;i++){cout.setf(2);cout.width(12);coutfrees[i].start;cout.width(10);coutfrees[i].length;cout.width(8);coutfrees[i].tagendl;}coutendl----------------------------------------------------------endl;cout当前已分配表:endl;cout起始地址长度占用作业名endl;for(i=0;ioccupy_quantity;i++){cout.setf(2);cout.width(12);coutoccupys[i].start;cout.width(10);coutoccupys[i].length;cout.width(8);coutoccupys[i].tagendl;}}//最先适应分配算法voidearliest(){charjob_name[20];intjob_length;inti,j,flag,t;cout请输入新申请内存空间的作业名和空间大小:;cinjob_name;cinjob_length;flag=0;for(i=0;ifree_quantity;i++){if(frees[i].length=job_length){flag=1;}}if(flag==0){coutendlSorry,当前没有能满足你申请长度的空闲内存,请稍候再试endl;}else{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].lengthjob_length){frees[i].start+=job_length;frees[i].length-=job_length;}else{for(j=i;jfree_quantity-1;j++){frees[j]=frees[j+1];}free_quantity--;cout内存空间成功:)endl;}}}//最优适应分配算法voidexcellent(){charjob_name[20];intjob_length;inti,j,flag,t;cout请输入新申请内存空间的作业名和空间大小:;cinjob_name;cinjob_length;flag=0;for(i=0;ifree_quantity;i++){if(frees[i].length=job_length){flag=1;}}if(flag==0){coutendlSorry,当前没有能满足你申请长度的空闲内存,请稍候再试endl;}else{t=0;i=0;while(t==0){if(frees[i].length=job_length){t=1;}i++;}i--;for(j=0;jfree_quantity;j++){if((frees[j].length=job_length)&&(frees[j].lengthfrees[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].lengthjob_length){frees[i].start+=job_length;frees[i].length-=job_length;}else{for(j=i;jfree_quantity-1;j++){frees[j]=frees[j+1];}free_quantity--;cout内存空间成功:)endl;}}}//最坏适应算法voidworst(){charjob_name[20];intjob_length;inti,j,flag,t;cout请输入新申请内存空间的作业名和空间大小:;cinjob_name;cinjob_length;flag=0;for(i=0;ifree_quantity;i++){if(frees[i].length=job_length){flag=1;}}if(flag==0){coutendlSorry,当前没有能满足你申请长度的空闲内存,请稍候再试endl;}else{t=0;i=0;while(t==0){if(frees[i].length=job_length){t=1;}i++;}i--;for(j=0;jfree_quantity;j++){if((frees[j].length=job_length)&&(frees[j].lengthfrees[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].lengthjob_length){frees[i].start+=job_length;frees[i].length-=job_length;}else{for(j=i;jfree_quantity-1;j++){frees[j]=frees[j+1];}free_quantity--;cout内存空间成功:)endl;}}}//撤消作业voidfinished(){charjob_name[20];inti,j,flag,p=0;intstart;intlength;cout请输入要撤消的作业名:;cinjob_name;flag=-1;for(i=0;ioccupy_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;ifree_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;for(j=i+1;jfree_quantity;j++){frees[j]=frees[j+1];}free_quantity--;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==