第一篇：实验三 存储器的分配与回收算法实现(二维数组)
实验三 存储器的分配与回收算法
◆实验名称：存储器的分配与回收算法实验 ◆仪器、设备：计算机
◆参考资料：操作系统实验指导书 ◆实验目的：
设计一个存储器的分配与回收算法管理方案，并编写模拟程序实现。◆实验内容：
1.模拟操作系统的主存分配，运用可变分区的存储管理算法设计主存分配和回收程序，并不实际启动装入作业。
2.采用最先适应法、最佳适应法、最坏适应法分配主存空间。
3.当一个新作业要求装入主存时，必须查空闲区表，从中找出一个足够大的空闲区。若找到的空闲区大于作业需要量，这是应把它分成二部分，一部分为占用区，加一部分又成为一个空闲区。
4.当一个作业撤离时，归还的区域如果与其他空闲区相邻，则应合并成一个较大的空闲区，登在空闲区表中。
5.运行所设计的程序，输出有关数据结构表项的变化和内存的当前状态。◆实验要求：
1． 详细描述实验设计思想、程序结构及各模块设计思路； 2． 详细描述程序所用数据结构及算法； 3． 明确给出测试用例和实验结果；
4． 为增加程序可读性，在程序中进行适当注释说明；
5． 认真进行实验总结，包括：设计中遇到的问题、解决方法与收获等； 6． 实验报告撰写要求结构清晰、描述准确逻辑性强；
实验过程中，同学之间可以进行讨论互相提高，但绝对禁止抄袭。◆实验过程记录（源程序、测试用例、测试结果及心得体会等
实验代码如下：
#include
int work[10][2];
//作业名字 大小
int idle[10][2];
//空闲区大小 地址
int free[10][3];
//已分配区域的名字 地址 大小
int num=0,b=1,d,ch1,ch2;void init(){
idle[0][0]=1;idle[0][1]=100;
free[0][0]=0;free[1][1]=0;free[1][2]=0;
work[0][0]=0;work[0][1]=0;
for(int i=1;i <=9;i++){ //初始化数组
idle[i][0]=0;idle[i][1]=0;
free[i][0]=0;free[i][1]=0;free[i][2]=0;
work[i][0]=0;work[i][1]=0;
} }
void jishu(){ //求空闲单元数
for(int i=0;i <9;i++)
if(idle[i][1]!=0)
num++;}
void jishu1(){ //求作业数
for(int i=0;i <9;i++)
if(work[i][1]!=0)
b++;
}
void zuixian(){ //最先适应法
jishu();
for(int i=0;i for(int j=i;j if(idle[j][0]>idle[j+1][0]){ int temp=idle[j][0]; idle[j][0]=idle[j+1][0]; idle[j+1][0]=temp; temp=idle[j][1]; idle[j][1]=idle[j+1][1]; idle[j+1][1]=temp; } } } } void zuijia(){ //最佳适应法 num=0; jishu(); for(int i=0;i for(int j=i;j if(idle[j][1]>idle[j+1][1]){ int temp=idle[j][0]; idle[j][0]=idle[j+1][0]; idle[j+1][0]=temp; temp=idle[j][1]; idle[j][1]=idle[j+1][1]; idle[j+1][1]=temp; } } } } void zuihuai(){ //最坏适应法 num=0; jishu(); for(int i=0;i for(int j=i;j if(idle[j][1] int temp=idle[j][0]; idle[j][0]=idle[j+1][0]; idle[j+1][0]=temp; temp=idle[j][1]; idle[j][1]=idle[j+1][1]; idle[j+1][1]=temp; } } } } void huishou(int name){ //回收进程函数 num=0; b=0; jishu(); jishu1(); int c=-1; for(int k=0;k <=b;k++){ if(free[k][0]==name){ c=k; break; } } if(c==-1)cout <<“要回收的作业不存在！” < else{ for(int i=0;i //将空闲单元排序{不包括新回收的} for(int j=i;j if(idle[j][0]>idle[j+1][0]){ int temp=idle[j][0]; idle[j][0]=idle[j+1][0]; idle[j+1][0]=temp; temp=idle[j][1]; idle[j][1]=idle[j+1][1]; idle[j+1][1]=temp; } } } for(int q=0;q if(free[c][1] <=idle[q][0]){ for(int j=num;j>=q;j--){ idle[j+1][0]=idle[j][0]; idle[j+1][1]=idle[j][1]; } idle[j][0]=free[c][1]; idle[j][1]=free[c][2]; b++; if(idle[j+1][0]==idle[j][0]+idle[j][1]){ idle[j][1]=idle[j][1]+idle[j+1][1]; for(int m=j+1;m <=num;m++){ idle[m][0]=idle[m+1][0]; idle[m][1]=idle[m+1][1]; } idle[m][0]=0; idle[m][1]=0; b--; } if(idle[j-1][0]==idle[j][0]){ idle[j-1][1]=idle[j-1][1]+idle[j][1]; for(int n=j;j <=num;j++){ idle[n][0]=idle[n+1][0]; idle[n][1]=idle[n+1][1]; } idle[n][0]=0; idle[n][1]=0; b--; } break; } } if(ch2==1)zuixian(); if(ch2==2)zuijia(); if(ch2==3)zuihuai(); for(int p=c;c free[c][0]=free[c+1][0]; free[c][1]=free[c+1][1]; free[c][2]=free[c+1][2]; work[c][0]=work[c+1][0]; work[c][1]=work[c+1][1]; } cout<<“该进程已被成功回收！”< } } void fp(){ int tag=0;//判断空闲区与请求区大小 num=0; b=0; jishu(); jishu1(); for(int j=0;j if(work[b][1] free[b][0]=work[b][0]; free[b][1]=idle[j][0]; free[b][2]=work[b][1]; idle[j][0]=idle[j][0]+work[b][1]; idle[j][1]=idle[j][1]-work[b][1]; tag=1; break; } else if(work[b][1]==idle[j][1]){ free[b][0]=work[b][0]; free[b][1]=idle[j][0]; free[b][2]=work[b][1]; tag=1; for(int i=j;i <=num-1;i++){ idle[i][0]=idle[i+1][0]; idle[i][1]=idle[i+1][1];} break;} else tag=0;} if(tag==0)cout <<“作业过大没有足够存储空间！” < void print(){ num=0; b=1; jishu(); jishu1(); cout <<“已分配表为:” < for(int i=0;i <=b;i++) if(free[i][2]!=0) cout <<“作业名:” < cout < cout <<“空闲区表为:” < for(int j=0;j if(idle[j][1]!=0) cout <<“起始地址:” < cout < void main(){ //主函数运行上面定义的函数 init(); int n; cout <<“1.分配空间；2.回收空间；” < cin>>ch1; cout < cout <<“1.最先适应法；2.最佳适应法；3.最坏适应法；” < cin>>ch2; cout < cout <<“请输入要分配内存的作业名及占用内存大小:”; cin>>work[b][0]>>work[b][1]; cout < if(ch2==1){ zuixian(); fp(); } else if(ch2==2){ zuijia(); fp();} else if(ch2==3){ zuihuai(); fp();} print();} cout <<“输入要回收的作业名：” < cin>>n; huishou(n); } 实验截图： 成功回收时： 回收失败时： 实验体会： 本次实验的难度较大，尤其是回收进程，主要编写几个算法和回收程序，最佳，最优，最坏算法和回收算法，我用的是数组，有工作数组，空闲数组，已分配数组。最后再编写算法，但是回收算法现在还是有些不清晰，需要进一步研究！ 实验报告 【实验名称】 首次适应算法和循环首次适应算法 【实验目的】 理解在连续分区动态的存储管理方式下，如何实现主存空间的分配与回收。 【实验原理】 首次适应（first fit，FF）算法 FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区即可。然后再按照作业的大小，从该分区中划出一块内存空间，分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则表明系统中已经没有足够大的内存分配给该进程，内存分配失败，返回。 循环首次适应（next fit，NF）算法 为避免低址部分留下许多很小的空闲分区，以及减少查找可用空闲分区的开销，循环首次适应算法在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块玉请求大小相等的内存空间分配给作业。 【实验内容】 实现主存空间的分配与回收： 1.采用可变式分区管理，使用首次适应算法实现主存空间的分配与回收； 2.采用可变式分区管理，使用循环首次适应算法实现主存空间的分配与回收。 数据结构和符号说明： typedef struct PCB//进程控制块 { char ProgressName[10]; //进程名称 int Startaddress; //进程开始地址 int ProgressSize; //进程大小 int ProgressState = 0; //进程状态 }; typedef struct FREE //空闲区结构体 { int Free_num; //空闲区名称 int Startaddress; //空闲区开始地址 int Endaddress; //空闲区结束地址 int Free_Space; //空闲区大小 }; 算法流程图： 首次适应算法 循环首次适应算法 程序代码及截图： #include #include #include #include #define N 1024 typedef struct PCB//进程控制块 { char ProgressName[10]; //进程名称 int Startaddress; //进程开始地址 int ProgressSize; //进程大小 int ProgressState = 0; //进程状态 }; typedef struct FREE //空闲区结构体 { int Free_num; //空闲区名称 int Startaddress; //空闲区开始地址 int Endaddress; //空闲区结束地址 int Free_Space; //空闲区大小 }; int count = 0; //当前内存中进程个数 bool ROM[N];//设置内存块 int p = 0;//循环首次使用需要标记当前的空闲区块 FREE FREE[100];//设置空闲区数组为100个 int FREE_counter = 0;//空闲区的个数 PCB num[20]; //作业队列 void init()//初始化操作 { for(int i=0; i i++) ROM[i] = 0; } void showProgress(PCB &a) { printf(“----------------------------------------------------------------------＼n“); printf(“进程名＼t＼t开始地址＼t＼t大小＼t＼t结束地址＼n“);//输出内存信息 printf(“----------------------------------------------------------------------＼n“); for(int i=0; i i++) for(int j=i; j j++) if(num[j].Startaddress>num[j+1].Startaddress) { a = num[j]; num[j] = num[j+1]; num[j+1] = a; } for(int i=0; i i++) if(num[i].ProgressState!=0) printf(“%s＼t＼t%d＼t＼t＼t%d＼t＼t%d＼t＼t＼n“,num[i].ProgressName,num[i].Startaddress,num[i].ProgressSize,num[i].ProgressSize+num[i].Startaddress-1); printf(“----------------------------------------------------------------------＼n“); } void showFree()//打印空闲区的情况 { printf(“----------------------------------------------------------------------＼n“); printf(“ 空闲区名＼t| 开始地址＼t| 大小 ＼t| 结束地址＼n“); printf(“----------------------------------------------------------------------＼n“); for (int i=1; i<= FREE_counter; i++) { printf(“＼t%1d＼t%8d＼t%11d＼t %d＼n“,FREE[i].Free_num,FREE[i].Startaddress,FREE[i].Free_Space,FREE[i].Endaddress); printf(“----------------------------------------------------------------------＼n“); } } void find_FREE() //寻找空闲区 { int i,j,p; //计数值 FREE_counter = 0;//预设空闲区数为0 for(i = 0; i N; i++) if(ROM[i] == 0) { p = i; for(j = i; j N; j++) { if(ROM[j]==0)//未找到空闲区，则将j赋值给i后继续循环 { i = j; continue; } if(ROM[j]==1)//找到空闲区 { FREE_counter++;//空闲区个数+1； FREE[FREE_counter].Free_num = FREE_counter;//设置空闲区编号 FREE[FREE_counter].Startaddress = p; FREE[FREE_counter].Endaddress = j-1; FREE[FREE_counter].Free_Space = j-p; i=j+1; break; } } if(j == N && ROM[j-1] == 0)//对最后一个内存进行特殊操作 { FREE_counter++; FREE[ FREE_counter].Free_num = FREE_counter;//对空闲区进行处理 FREE[ FREE_counter].Startaddress = p; FREE[ FREE_counter].Endaddress =j-1; FREE[ FREE_counter].Free_Space = j-p; } } } void First_Fit(PCB &a)//首次适应算法 { int i,j,k; for(i=0; i i++) if(ROM[i]==0) { for(j=i; j<=(i+a.ProgressSize)&&j j++)//查询第一个空闲区，并判断是否适合插入作业 if(ROM[j]==1) { i = j + 1; break; } if(j==i+a.ProgressSize+1) { a.Startaddress = i;//设置作业的开始地址 a.ProgressState = 1;//标记作业在内存中 for(k=i; k k++) ROM[k]=1; printf(“进程%s插入成功，进程%s的初始地址为%d,结束地址为%d＼n“,a.ProgressName,a.ProgressName,a.Startaddress,a.Startaddress+a.ProgressSize-1); return; } } if(i==N)//未查询到合适的区域 printf(“插入失败，无可用空间！＼n“); } void Next_Fit(PCB &a)//循环首次适应算法来实现作业调度 { int i,j,k; for(i=p; i i++)//从所标记的当前区域开始查询，查询到末内存 { if(ROM[i]==0) { for(j=i; j<=(i+a.ProgressSize)&&j j++) if(ROM[j]==1) { i = j+1; break; } if(j==i+a.ProgressSize+1)//找到合适的空闲区 { a.Startaddress=i; a.ProgressState=1; for(k=i; k k++) ROM[k]=1; printf(“插入成功，进程%s的初始地址为%d,结束地址为%d＼n“,a.ProgressName,a.Startaddress,a.Startaddress+a.ProgressSize-1); p=i+a.ProgressSize; return; } } } for(i=0; i i++)//当未找到时，从第一个空闲区开始查询，结束条件为小于所标记的P if(ROM[i]==0) { for(j=i; j<=(i+a.ProgressSize)&&j j++) if(ROM[j]==1) { i=j+1; break; } if(j==i+a.ProgressSize+1)//成功找到结束，并标记当前P为现在的作业的尾部 { a.Startaddress=i; a.ProgressState=1; for(k=i; k ROM[k]=1; printf(“插入成功，进程%s的初始地址为%d＼n“,a.ProgressName,a.Startaddress); p=i+a.ProgressSize; break; } } if(i==p)//查询两部分都未找到合适的区域，输出插入失败语句 printf(“插入失败，无可用空间＼n“); } void Delete(PCB &a)//删除作业，修改内存信息和初始化该作业信息 { int i; for(i=a.Startaddress; i i++) ROM[i]=0; a.ProgressState=0;//状态标记为未使用 printf(“进程%s删除成功＼n“,a.ProgressName); } int main() { int choose1,choose; char ProgressName[10]; PCB a; init(); printf(“＼t主存空间的分配与回收＼n“); printf(“---------------------------------------＼n“); printf(“＼t1、首次适应算法＼n“); printf(“＼t2、循环首次适应算法＼n“); printf(“---------------------------------------＼n“); printf(“请选择分配算法：“); scanf(“%d“,&choose1); system(“cls“); while(1) { w:system(“cls“); printf(“当前分配算法：“); if(choose1 == 1) printf(“首次适应算法＼n“); else printf(“循环首次适应算法＼n“); printf(“---------------------------------------＼n“); printf(“＼t1、插入进程＼n“); printf(“＼t2、删除进程＼n“); printf(“＼t3、显示进程的信息＼n“); printf(“＼t4、显示空闲区＼n“); printf(“---------------------------------------＼n“); printf(“请输入：“); scanf(“%d“,&choose); system(“cls“); switch(choose) { case 1: printf(“请输入进程名:“); scanf(“%s“,&a.ProgressName); printf(“请输入进程的大小：“); scanf(“%d“,&a.ProgressSize); for(int i = 0; i count; i++) if(strcmp(num[i].ProgressName,a.ProgressName)==0) { printf(“已存在同名进程，无法插入。＼n“); system(“pause“); goto w; } if(choose1==1)//首次适应算法 First_Fit(a); else Next_Fit(a);//循环首次适应算法 num[count++]=a; break; case 2: if(count == 0) { printf(“当前没有进程在内存中，无法删除！＼n“); system(“pause“); goto w; } printf(“输入删除的进程名字：“); scanf(“%s“,&ProgressName); for(int i=0; i i++) if(!strcmp(num[i].ProgressName,ProgressName)) Delete(num[i]); else printf(“没有找到对应进程，请重新输入。＼n“); break; case 3: showProgress(a); break; case 4: find_FREE(); showFree(); break; default: printf(“＼n无效的输入。＼n“); } system(“pause“); } return 0; } 主界面： 首次适应算法，初始空闲区： 插入进程： 插入3个进程： 空闲区信息： 删除进程2： 删除后空闲区状况： 再插入一个进程，可以看到其其初始地址为100： 循环首次适应算法,插入3个进程 删除进程2后： 再插入进程A，发现其从上次找到的空闲分区的下一个空闲分区开始查找，其初始地址为750而不是200：第二篇：操作系统实验四主存空间的分配与回收首次适应算法和循环首次适应算法
点击咨询 