第一篇：操作系统课程设计_动态分区分配存储管理
操作系统课程设计
设计题目 动态分区分配存储管理
学生姓名学
号 专业班级 指导教师
吕 霆
20102675 计算机10-01班
第一章
课程设计概述
1.1 设计任务: 动态分区分配存储管理
1.2 设计要求
建立描述内存分配状况的数据结构； 建立描述进程的数据结构； 使用两种方式产生进程：（a）自动产生，（b）手工输入； 在屏幕上显示内存的分配状况、每个进程的执行情况； 建立分区的分配与回收算法，支持紧凑算法； 时间的流逝可用下面几种方法模拟：（a）按键盘，每按一次可认为过一个时间单位；(b)响应WM_TIMER；
将一批进程的执行情况存入磁盘文件，以后可以读出并重放；
支持算法：首次适应算法、循环首次适应算法、最佳适应算法：最坏适应算法。
1.3 设计目的
旨在让我们更好的了解动态分区管理方面的知识.第二章 原理及算法描述
2.1动态分区分配算法原理
首次适应算法
* 算法概述：分配内存时，从链首开始顺序查找，找到满足的空闲分区则划出空间分配，余下的空闲空间仍保留在空闲链表中
* 实现方法：分配时从数组第一个元素开始比较，若符合条件则将该元素减去对应作业的值
循环首次适应算法
* 算法概述：由首次适应算法演变，只是每次分配改为由上一次找到的空闲分区开始查找
* 实现方法：在首次适应算法的基础上增加一个值用于记录找到的空闲分区的位置
最佳适应算法
* 算法概述：每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区
分配给作业
* 实现方法：我们决定每次分配先把空闲分区按从小到大的顺序排列，然后将第一个匹配分区分配给作业
最坏适应算法
* 算法概述：每次为作业分配内存时，总是挑选一个最大的空闲分区分割给作业使用
* 实现方法：算法与最佳适应算法几乎相同，仅在排序时把空闲分区表按从大到小的顺序排列，所以未作详细注释
回收分区
当进程运行完毕释放内存时,系统根据回收区的首址,从空闲区链(表)中找到相应的插入点,此时可能出现以下四种情况之一;1)回收区与插入点的前一个空闲分区F1相邻接,此时应将回收区与插入点的前一分区合并,不必为回收区分配新表项,而只需修改其前一分区F1的大小.2)回收分区与插入点的后一空闲分区F2相邻接,此时也可将两分区合并,形成新的空闲分区,但用回收区的首址作为新空闲区的首址,大小为两者之和.3)回收区同时与插入点的前,后两个分区邻接,此时将三个分区合并,使用F1的表项和F1的首址,取消F2的表项,大小为三者之和.4)回收区既不与F1相邻接,又不与F2邻接.这时应为回收区单独建立一新表项,填写回收区的首址和大小,并根据其首址插入到空闲链中的适当位置.紧凑算法
通过移动内存中的作业的位置,以把原来多个分散的小分区拼接成一个大分区的方法.第三章 开发环境
此程序是本人利用c++语言在vs2012的开发环境中实现的第四章 程序实现--数据结构
#include
int recycle;//需要回收的盘块序号 int id1;//算法选择号 int m;//内存区数 int n;//空闲区数 int q;//进程数
int r=0;//循环首次适应算法：对应的这次查找到的空闲分区序号 //打印输出函数 void vision(){
int i;int j;if(id1==1)stream.open(“first_fit.txt”, ios::app);if(id1==2)stream.open(“nextfirst_fit.txt”, ios::app);if(id1==3)stream.open(“best_fit.txt”,ios::app);if(id1==4)stream.open(“worst_fit.txt”, ios::app);if(id1==5)stream.open(“compact.txt”,ios::app);if(id1==6)stream.open(“huishou.txt”,ios::app);cout<<“-------------内存分配状态-------------”< } cout < } cout < } //作业信息的自动产生 void create_pro(){ } //作业的手动生成 void create_zuoye(){ int j;int choice2;int id3=rand()%10;m=id3;//内存区数量 cout<<“产生”< } ary3[0]=42;ary3[1]=86;ary3[i]=rand()%100;if(ary3[i]==0){i--;} { } cout<<“--------------------------”< } //内存信息的自动产生 void create_apply(){ int k=0;//空闲区数量 for(i=0;i if(ary1[i][3]!=2){ary2[k][0]=ary1[i][0];ary2[k][1]=ary1[i][1];ary2[k][2]=ary1[i][2];k++;} int i;for(i=0;i } ary1[i][0]=i+1;ary1[i][1]=rand()%100;if(i==0){ } ary1[i][3]=rand()%3;//cout < } cout<<“你创建了”< } //内存信息的手动生成 int create_fenqu(){ } //首次适应算法 void first_fit()int k,x,y,o=0;int a=0;cout<<“输入想创建的内存分区块数 : ”;cin>>k; cout<<“输入”< } cout<<“输入内存块的分配状态”< } ary1[0][2]=0;ary1[1][2]=ary1[0][1];for(int i=2;i for(int i=0;i } n=a;return m,n;if(ary1[i][3]!=2){ } ary2[a][0]=ary1[i][0];ary2[a][1]=ary1[i][1];ary2[a][2]=ary1[i][2];a++;ary1[i][2]=ary1[i-1][2]+ary1[i-1][1];//起始地址 cin>>y;if(y==2){ } ary1[i][3]=y;//状态 n++;ary1[i][0]=i;//序号 cin>>x;ary1[i][1]=x;//大小 } n=k;//空闲块数量 { vision();int i;int j;int k;int l;int d;//用来保存第k个的值 int id2=0;for(i=0;i for(j=0;j if(ary2[j][1]>=ary3[i])//进程占用空间小于等于其中一个空闲区的大小 { cout<<“[”< ary1[ary2[j][0]-1][3]=2;for(k=j+1;k ary2[k-1][0]=ary2[k][0];ary2[k-1][1]=ary2[k][1];ary2[k-1][2]=ary2[k][2];} n--; }else//否则的话，空闲链对应的地方盘块大小小了进程占用的大小，并且内存分配从对应的 { l=ary2[j][0];d=ary1[l-1][1];//大小 ary1[l-1][1]=ary3[i];ary1[l-1][3]=2;m++;for(k=m;k>ary2[j][0]+1;k--){ ary1[k-1][0]=ary1[k-2][0]+1;ary1[k-1][1]=ary1[k-2][1];ary1[k-1][2]=ary1[k-2][2];ary1[k-1][3]=ary1[k-2][3];那一项开始增加一项 } l=ary2[j][0]; } } { if(ary1[id2][3]!=2) } } n=k;} break;} else { } cout<<“[”< { ary2[k][0]=ary1[id2][0];ary2[k][1]=ary1[id2][1];ary2[k][2]=ary1[id2][2];k++;} ary1[l][0]=l+1;ary1[l][1]=d-ary3[i];ary1[l][2]=ary1[l-1][1]+ary1[l-1][2];ary1[l][3]=0;k=0;for(id2=0;id2 //首次循环适应算法 void next_fit(){ vision();int i;int j;int k;int s;int d;int id2;for(i=0;i { for(j=r;j if(ary3[i]<=ary2[j][1]){ cout<<“[”< { } else//对应的空闲块大小大于进程需要大小 { //-----改变内存分配情况-----r=(r+1)%n;//改变第k块的内容 k=ary2[j][0];d=ary1[k-1][1];ary1[k-1][1]=ary3[i];ary1[k-1][3]=2;//从k+1之后所有向后移一格 m++;//内存块数增加1 for(s=m-1;s>k;s--){ ary1[s][0]=ary1[s-1][0]+1;ary1[s][1]=ary1[s-1][1];ary1[s][2]=ary1[s-1][2];//---改变内存分配---k=ary2[j][0];//得到对应空闲块对应内存块的序号 k--;ary1[k][3]=2;//把对应内存块标志位上改成已分配 //------------------//--改变空闲块表：把从这块空闲块以下的所有空闲块向上移一格--n--;for(k=j;k } vision();//------------------break;ary2[k][0]=ary2[k+1][0];ary2[k][1]=ary2[k+1][1];ary2[k][2]=ary2[k+1][2];stream<<“[”< } } //思路：先把空闲列表检索一遍，选出最佳答案，进行分配 void best_fit()//最佳算法--按顺序检索，把与进程要求内存大小最接近的快分配给进程 { int i;int s;int j=-9999;//用来保存最接近的答案 int e;//用来存放进行比较时的中间结果 } { if(ary1[id2][3]!=2) } } else{ } cout<<“[”< { ary2[k][0]=ary1[id2][0];ary2[k][1]=ary1[id2][1];ary2[k][2]=ary1[id2][2];k++;} ary1[s][3]=ary1[s-1][3];} //改变第k+1块内容：对应的数组是ary1[k] ary1[k][0]=ary1[k-1][0]+1;ary1[k][1]=d-ary1[k-1][1];ary1[k][2]=ary1[k-1][1]+ary1[k-1][2];//--------------------------//----改变空闲表分配情况----k=0;for(id2=0;id2 }else { cout<<“[”< for(s=0;s } if(j<0){ cout<<“[”< if(ary2[j][1]==ary3[i]){ } else for(l=k;l } n--;ary2[l-1][0]=ary2[l][0];ary2[l-1][1]=ary2[l][1];ary2[l-1][2]=ary2[l][2];ary1[k-1][3]=2;k=ary2[j][0]; } //最坏适应算法 void worst_fit() } { if(ary1[id2][3]!=2) } } vision();n=k; } for(k=j+1;k { ary2[k][0]=ary1[id2][0];ary2[k][1]=ary1[id2][1];ary2[k][2]=ary1[id2][2];k++;} { //把对应的内存分配进行更改 k=ary2[j][0];d=ary1[k-1][1];ary1[k-1][1]=ary3[i];ary1[k-1][3]=2;m++;for(l=m;l>ary2[j][0]+1;l--){ } k=ary2[j][0];ary1[k][0]=k+1;ary1[k][1]=d-ary1[k-1][1];ary1[k][2]=ary1[k-1][1]+ary1[k-1][2];ary1[k][3]=0;k=0;ary1[l-1][0]=ary1[l-2][0]+1;ary1[l-1][1]=ary1[l-2][1];ary1[l-1][2]=ary1[l-2][2];ary1[l-1][3]=ary1[l-2][3];for(id2=0;id2 { }else { cout<<“[”< int e=-9999;//用来存放进行比较时的中间结果 int k;int l;int d;int id2;vision();{ j=-9999;e=-9999;for(s=0;s } if(j<0){ cout<<“[”< if(ary2[j][1]==ary3[i]){ k=ary2[j][0]; ary1[k-1][3]=2; for(l=k;l { if(ary1[id2][3]!=2) } } vision();n=k; } for(k=j+1;k { ary2[k][0]=ary1[id2][0];ary2[k][1]=ary1[id2][1];ary2[k][2]=ary1[id2][2];k++;} } else { //把对应的内存分配进行更改 k=ary2[j][0];d=ary1[k-1][1];ary1[k-1][1]=ary3[i];ary1[k-1][3]=2;m++;for(l=m;l>ary2[j][0]+1;l--){ } k=ary2[j][0];ary1[k][0]=k+1;ary1[k][1]=d-ary1[k-1][1];ary1[k][2]=ary1[k-1][1]+ary1[k-1][2];ary1[k][3]=0;k=0;ary1[l-1][0]=ary1[l-2][0]+1;ary1[l-1][1]=ary1[l-2][1];ary1[l-1][2]=ary1[l-2][2];ary1[l-1][3]=ary1[l-2][3];} n--;ary2[l-1][2]=ary2[l][2];for(id2=0;id2 } //回收内存算法： /* 有共计八种情况，1.（1）回收区上邻接着空闲盘块，下连接着已分配盘块（2）回收区下邻接着空闲盘块，上邻接着已分配盘块(3)回收区上下连接的都是空闲盘块（4)空闲区上下邻接的都是已分配盘块 （5）要回收的盘块就是第一个盘块，并且向下邻接着空闲盘块(6)要回收的盘块就是第一个盘块，但是向下邻接着已分配盘块(7)要回收的盘块就是最后一个盘块，并且向上邻接的是空闲盘块(8)要回收的盘块就是最后一个盘块，但是向上邻接的是已分配盘块 */ void apply_recycle(){ ary1[0][1]=ary1[0][1]+ary1[1][1];ary1[0][3]=0;for(i=1;i if(recycle==1){ //cout< if(ary1[1][3]!=2){ cout<<“要回收的盘块就是第一个盘块，并且向下邻接着空闲盘块”< } else { ary1[0][3]=0;n++;ary2[0][0]=1;ary2[0][1]=ary1[0][1];ary2[0][2]=ary1[0][2];vision();} stream<<“要回收的盘块就是第一个盘块，并且向下邻接着空闲盘块”< ary2[k][0]=ary1[j][0]; ary1[0][3]=0;k=0;for(j=0;j //cout<<“ary1[j][3]”< } else{ cout<<“要回收的盘块就是第一个盘块，但是向下邻接着已分配盘块”< } n=k;vision(); } ary2[k][0]=ary1[j][0];ary2[k][1]=ary1[j][1];ary2[k][2]=ary1[j][2];k++; { } m--;// cout<<“" k=0;vision();//cout<<”ary1[0][3]“< cout<<”ary1[j][3]“< } else{ cout<<”要回收的盘块就是最后一个盘块，但是向上邻接的是已分配盘块“< } n=k;vision(); } ary2[k][0]=ary1[j][0];ary2[k][1]=ary1[j][1];ary2[k][2]=ary1[j][2];k++; ary1[recycle-2][3]=0;ary1[recycle-2][1]=ary1[recycle-2][1]+ary1[recycle-1][1];m--;k=0;for(j=0;j //cout<<”ary1[j][3]“< } else if(recycle==m){ if(ary1[recycle-2][3]!=2){ cout<<”要回收的盘块就是最后一个盘块，并且向上邻接的是空闲盘块“< } n=k;vision(); } ary2[k][1]=ary1[j][1];ary2[k][2]=ary1[j][2];k++;stream<<”要回收的盘块就是最后一个盘块，并且向上邻接的是空闲盘块“< ary2[k][0]=ary1[j][0];ary2[k][1]=ary1[j][1];ary2[k][2]=ary1[j][2];k++; } else{//剩下比较复杂的四种情况 if((ary1[recycle-2][3]!=2)&&(ary1[recycle][3]==2))//回收区上邻接着空闲盘块，下连接着{cout<<”回收区上邻接着空闲盘块，下连接着已分配盘块“< } } n=k;vision(); } ary2[k][0]=ary1[j][0];ary2[k][1]=ary1[j][1];ary2[k][2]=ary1[j][2];k++; ary1[recycle-1][3]=0;k=0;for(j=0;j //cout<<”ary1[j][3]“< stream<<”回收区上邻接着空闲盘块，下连接着已分配盘块“< ary1[recycle-2][1]=ary1[recycle-2][1]+ary1[recycle-1][1];for(i=recycle-1;i } m--;k=0;for(j=0;j //cout<<”ary1[j][3]“< } if((ary1[recycle-2][3]!=2)&&(ary1[recycle][3]!=2))//回收区上下连接的都是空闲盘块 { cout<<”回收区上下连接的都是空闲盘块“< } vision(); } ary2[k][0]=ary1[j][0];ary2[k][1]=ary1[j][1];ary2[k][2]=ary1[j][2];k++; } n=k;vision();} if((ary1[recycle][3]!=2)&&(ary1[recycle-2][3]==2))//回收区下邻接着空闲盘块，上邻接着{ cout<<”回收区下邻接着空闲盘块，上邻接着已分配盘块“< stream<<”回收区下邻接着空闲盘块，上邻接着已分配盘块“< ary1[recycle-2][3]=0;ary1[recycle-2][1]=ary1[recycle-2][1]+ary1[recycle-1][1];for(i=recycle-1;i } m--;k=0;for(j=0;j //cout<<”ary1[j][3]“< } } } if((ary1[recycle-2][3]==2)&&(ary1[recycle][3]==2))//空闲区上下邻接的都是已分配盘块 { } ary1[recycle-1][3]=0;k=0;for(j=0;j } vision();//cout<<”ary1[j][3]“< } ary2[k][0]=ary1[j][0];ary2[k][1]=ary1[j][1];ary2[k][2]=ary1[j][2];k++;cout<<”回收区上下连接的都是空闲盘块“< } m=m-2;k=0;for(j=0;j } vision();//cout<<”ary1[j][3]“< } ary2[k][0]=ary1[j][0];ary2[k][1]=ary1[j][1];ary2[k][2]=ary1[j][2];k++;ary1[recycle-1][0]=ary1[recycle+1][0]-2;ary1[recycle-1][1]=ary1[recycle+1][1];ary1[recycle-1][2]=ary1[recycle+1][2];ary1[recycle-1][3]=ary1[recycle+1][3];n=k;n=k; } //紧凑算法 void compact(){ num_avl=0;for(id2=0;id2 int num_avl;//记录空闲盘块数量 int sum_avl=0;//总共空闲区大小 int num_apl=0;//统计总共空闲区有多大 vision();for(id2=0;id2 } //最后一块空闲块 ary1[num_apl][0]=num_apl+1;ary1[num_apl][1]=sum_avl;ary1[num_apl][2]=ary1[num_apl-1][1]+ary1[num_apl-1][2];ary1[num_apl][3]=0;m=num_apl+1;//包括最后一个空闲区 if(ary1[id2][3]==2){ } ary1[num_apl][0]=num_apl+1;ary1[num_apl][1]=ary1[id2][1];if(num_apl==0){ } ary1[num_apl][3]=2;num_apl++;//cout<<”num_apl“< } //主函数入口 void main(){ if(choice1==1){ } num=rand()&10;q=num;int id3=2+rand()%8;m=id3;//内存区数量 create_apply();create_pro();int i;int j;int num;int choice1;//操作选择标记 int choice2;int flag=1;//标记是否再执行 while(flag==1){ cout<<”********************************************“< } n=num_avl;vision(); } ary2[num_avl][0]=ary1[id2][0];ary2[num_avl][1]=ary1[id2][1];ary2[num_avl][2]=ary1[id2][2];num_avl++;if(choice1==2){ } vision(); cout<<”**------------------请选择处理算法----------------------**“< } } cout<<”**************************** “< cout<<”**1首次适应算法-----2循环首次适应算法-----3最佳适应算法 **“< } {first_fit();} {next_fit();} {best_fit();} {worst_fit();} { compact();} if(id1==6){ cout<<”*******************生成内存状态******************“< } cout<<”错误:内存中不存在此块！“< } if(id2==-9999){ apply_recycle();} if(ary2[i][0]==recycle){ } cout<<”错误：输入的为空闲盘块！"< 实 验 报 告 课程名称________操作系统试验____________ 实验名称________ 动态分区分配___________ 实验类型_________验证型_________________ 实验地点___机房___实验日期__2011_ 指导教师__________________________ 专 业_计算机科学与技术_ 班 级__________ 学 号______________ 姓 名____________ 成绩________________ XX大学计算机与通信工程学院 实验3 动态分区分配 一．实验目的用高级语言编写和调试一个内存分配模拟程序，以加深对动态分区的概念及内存分配原理的理解。 二．实验原理 可变分区调度算法有:最先适应分配算法,最优适应分配算法,最坏适应算法。 用户提出内存空间的申请；系统根据申请者的要求，按照一定的分配策略分析内存空间的使用情况，找出能满足请求的空闲区，分给申请者；当程序执行完毕或主动归还内存资源时，系统要收回它所占用的内存空间或它归还的部分内存空间。 每当一个进程被创建时，内存分配程序首先要查找空闲内存分区表（链），从中寻找一个合适的空闲块进行划分，并修改空闲内存分区表（链）。当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区表（链）中找到相应的插入点，此时出现如下四种情况： 1) 回收区与插入点的前一个空闲分区F1相邻接，此时可将回收区直接与F1合并，并修改F1的大小； 2) 回收区与插入点的后一个空闲分区F2相邻接，此时可将回收区直接与F2合并，并用回收区的首址最为新空闲区的首址，大小为二者之和； 3) 回收区同时与插入点的前、后两个空闲分区邻接，此时需将三者合并； 4) 回收区不与任何一个空闲区邻接，此时应建一新的表项。 三．实验内容 编写并调试一个模拟的内存分配程序。具体做法为：使用一个循环，根据提示，由用户选择随时创建一个新的进程，并为其分配存储空间，也随时可以撤销一个进程，可以根据需要随时打印空闲分区表（链）以及打印系统中内存使用情况。 四．实验环境 软件环境:Visual C++6.0 五．实验方案 六．实验步骤 1、流程图 2、程序源代码 八．实验中遇到的问题及解决方法 九．实验总结（见封皮） 【实验总结】 【指导教师评语及成绩】 成绩： 指导教师（签字）： ****年**月**日 计算机操作系统 实验报告 实验二 实验题目：存储器管理 系别：计算机科学与技术系 班级： 姓名： 学号：2 一、实验目的 深入理解动态分区存储管理方式下的内存空间的分配与回收。 二、实验内容 编写程序完成动态分区存储管理方式下的内存分配和回收的实现。具体内容包括： 确定用来管理内存当前使用情况的数据结构； 采用首次适应算法完成内存空间的分配； 分情况对作业进行回收； 编写主函数对所做工作进行测试。 三、实验原理 分配：动态分区存储管理方式把内存除OS占用区域外的空间看作一个大的空闲区。当作业要求装入内存时，根据作业需要内存空间的大小查询内存中各个空闲区，当从内存中找到一个大于或等于该作业大小的内存空闲区时，选择其中一个空闲区，按作业要求划出一个分区装入该作业。 回收：作业执行完后，它所占用的内存空间被收回，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。 四、实验方法 实现动态分区的分配与回收，主要考虑三个问题： 第一、设计记录内存使用情况的数据表格，用来记录空闲区和作业占用的区域(利用结构体类型数组来保存数据)； 第二、在设计的数据表格基础上设计内存分配算法（采用首次适应算法找合适的分区（对空闲分区表进行排序），分配时要考虑碎片问题）； 第三、在设计的数据表格基础上设计内存回收算法（分四种情况进行回收（上邻、下邻、上下邻和无相邻分区）。 五、实验步骤 第一，设计记录内存使用情况的数据表格 已分配分区表：起始地址、长度、标志（0表示“空表项”，1表示“已分配”） 空闲分区表： 起始地址、长度、标志（0表示“空表项”，1表示“未分配”） struct used_table { float address; //已分分区起始地址 float length; //已分分区长度，单位为字节 int flag; //已分配表区登记栏标志，用0表示空栏目，char zuoyename;}; //已分配区表 Struct free_table[ { float address; //空闲分区起始地址 float length; //空闲分区长度，单位为字节 int flag; //空闲分区表登记栏目用0表示空栏目，1表示未配 };//空闲分区表 第二，在设计的表格上进行内存分配 首次适应算法：为作业分配内存，要求每次找到一个起始地址最小的适合作业的分区（按起始地址递增排序）。 最大碎片size：要求当找到的空闲分区－作业的大小的值小于或等于size时，将该分区全部分配给作业（数组后面元素向前移）； 否则，给作业分割出一部分空间时，其余部分仍作为新的空闲分区登记（空闲分区长度=空闲分区长度-作业长度, 空闲分区起始地址=空闲分区起始地址+作业长度 第三，在设计的表格上进行内存回收。 1、上邻：条件:回收作业的始址=某个空闲区的始址+长度 操作：空闲区的长度=空闲区的长度+作业的大小 2、下邻：条件:回收作业的始址+作业的长度=某个空闲区的始址 操作： 空闲区的始址=回收作业的始址 空闲区的长度=空闲区的长度+作业的长度 3、上下邻：条件:1，2条件同时成立 操作：空闲区的始址=上邻的始址 空闲区的长度=上邻的长度+作业的长度+下邻的长度 删除下邻 4、无上下邻： 操作：找flag=0的行 空闲区的始址=回收作业的始址 空闲区的长度=作业的长度 六、实验代码 # include #define SADDRESS 200 //空闲分区初始的起始地址 #define SLENGTH 150000 //空闲分区的初始长度 struct used_t{ float address;//已分分区起始地址 float length;//已分分区长度 int flag;//已分配表区登记栏标志，用0表示空栏目 }used_table[N];struct free_t{ float address;//空闲分区起始地址 float length;//空闲分区长度 int flag;//空闲分区表登记栏目用0表示空栏目，1表示未分配 }free_table[M];//空闲分区表 void allocate(char,float);//分配算法子程序 void reclaim(char);//回收算法子程序 void main(){ int i,a;float zyl;char zyn;//空闲分区表初始化 free_table[0].address=SADDRESS;//空闲分区表的起始地址 free_table[0].length=SLENGTH;//空闲分区表的长度 free_table[0].flag=1;//标志位置1表示未分配 for(i=1;i free_table[i].length=0; free_table[i].flag=0;} //0表示空栏目 //已分分区表初始化 for(i=0;i used_table[i].length=0; used_table[i].flag=0;} while(1){cout<<“请选择功能项：”< <<“1-分配主存”< <<“2-回收主存”< <<“3-显示主存”< <<“0-退出”< <<“选择功能项(0-3):”; cin>>a;switch(a){case 0: //当选择0时退出程序 return; case 1: { //a=1 分配主存空间 cout<<“n请输入作业名zyn和作业所需长度zyl(作业名为一个字符，长度zyl要小于”< cin>>zyn>>zyl; allocate(zyn,zyl);//为作业zyn分配主存空间 break; } case 2:{ // a=2 回收主存空间 cout<<“n请输入要回收分区的作业名：”; cin>>zyn; reclaim(zyn);//回收作业zyn的主存空间 break;} case 3: { //a=3 显示主存情况，输出空闲区表和已分配区表 cout<<“n输出空闲区表：”< <<“ 起始地址 分区长度 标志”< for(i=0;i if(free_table[i].flag!=0)cout< cin.get(); cout<<“n输出已分配区表：”< <<“ 起始地址 分区长度 标志”< for(i=0;i cout< < break;} default:{ cout<<“n没有该选项！”< break; }}} cin.get()}//分配算法子程序 void allocate(char zyn,float zyl){ float ad;int k=-1;int i=0;while(i if(free_table[i].length>=zyl&&free_table[i].flag==1) k=i; i++;} if(k==-1){ //未找到可用空闲区，返回 cout<<“无可用空闲区！”< return;} /*找到可用空闲区，开始分配：若空闲区大小与作业要求分配的空间差小于MIN,则将找到的空闲区全部分配给该作业；若空闲区大小与要求分配的空间的差大于minisize,则从空闲区划出一部分分配给作业。*/ if(free_table[k].length-zyl<=MIN){ free_table[k].flag=0;ad=free_table[k].address;zyl=free_table[k].length;for(i=k;i free_table[i]=free_table[i+1];} else{ free_table[k].length=free_table[k].length-zyl;ad=free_table[k].address;free_table[k].address=free_table[k].address+zyl;} /*修改已分配区表*/ i=0;while(used_table[i].flag!=0&&i s++;//找到作业zyn在以分配表中的表目s if(s>=N){ cout<<“找不到该作业！”< S=used_table[s].address;//取作业zyn在内存中的首地址 L=used_table[s].length;//取作业zyn所分配到的内存的长度 j=-1;k=-1;i=0;//寻找回收分区的上下邻空闲区，上邻表目k，下邻表目j while(i if(free_table[i].address==S+L)j=i;} i++;} if(k!=-1){ //有上邻空闲区 if(j!=-1){ //有下邻空闲区 即有上下邻空闲区，三项合并 free_table[k].length=free_table[k].length+free_table[j].length+L; free_table[j].flag=0;} else //上邻空闲区，下邻非空闲区，与上邻合并 free_table[k].length=free_table[k].length+L;}//if else { //k==-1 无上邻空闲区 if(j!=-1){ //无上邻空闲区，有下邻空闲区，与下邻合并 free_table[j].address=S;free_table[j].length=free_table[j].length+L;} else{ //j==-1 上下邻均为非空闲区，回收区域直接填入 t=0;//在空闲区表中寻找空栏目 while(free_table[t].flag==1&&t cout<<“主存空闲表没有空间，回收失败！”< return; } free_table[t].address=S; free_table[t].length=L; free_table[t].flag=1;}} for(i=0;i<=M-1;i++)for(int j=i;j 七、实验结果 1、总的存储空间 2、分配空间 3、回收空间（1）有上下邻 （2）有上邻 （3）有下邻 （4）无上下邻，回收7 八、实验总结 1、通过实验学会了理解动态分区存储管理方式下的内存空间的分配与回收 2、学会了回收的四种方式 3、实验过程中遇到了问题，学会了与同学探讨解决 实验三 可变分区存储管理方式的内存分配回收 一．实验目的 （1）深入了解可变分区存储管理方式的内存分配回收的实现。 二．实验内容 编写程序完成可变分区存储管理方式的内存分配回收，要求有内存空间分配表，并采用最优适应算法完成内存的分配与回收。 三．实验原理 在可变分区模式下，在系统初启且用户作业尚未装入主存储器之前，整个用户区是一个大空闲分区，随着作业的装入和撤离，主存空间被分成许多分区，有的分区被占用，而有的分区时空闲的。为了方便主存空间的分配和去配，用于管理的数据结构可由两张表组成：“已分配区表”和“未分配区表”。在“未分配表中”将空闲区按长度递增顺序排列，当装入新作业时，从未分配区表中挑选一个能满足用户进程要求的最小分区进行分配。这时从已分配表中找出一个空栏目登记新作业的起始地址和占用长度，同时修改未分配区表中空闲区的长度和起始地址。当作业撤离时已分配区表中的相应状态变为“空”，而将收回的分区登记到未分配区表中，若有相邻空闲区再将其连接后登记。可变分区的回收算法较为复杂，当一个作业撤离时，可分为4种情况：其临近都有作业（A和B），其一边有作业（A或B），其两边均为空闲区。尤其重要的是，在程序中利用“new类型T（初值列表）”申请分配用于存放T类型数据的内存空间，利用“delete指针名”释放指针所指向的内存空间。 四．实验部分源程序 #include int start,end;// 起始，结束 int length;// 长度大小 struct SNode *next;// 指向下一结点的指针 }* SP;SP Head=(SP)malloc(sizeof(SNode));// 全局变量，内存空间头结 void DispSpace(){ // 显示内存空间分配情况 SP p=Head->next; cout<<“n 空闲区说明表 n” <<“---地址--长度---n”; while(p) { cout<<“ ”< start <<“ ”< length< p=p->next; } cout<<“----------------n”;} void Initial(){ // 初始化说明表 SP p,q; p=(SP)malloc(sizeof(SNode)); q=(SP)malloc(sizeof(SNode)); p->start=14;p->length=12;p->end=26; q->start=32;q->length=96;q->end=128;// 指导书上的作业分配 Head->next=p;// 与头结点连接 p->next=q; q->next=NULL; DispSpace();} void Allocation(int len){ // 分配内存给新作业 SP p=Head->next,q; while(p){ if(p->length < len) p=p->next; else if(p->length > len) { p->start=p->start+len; p->length=p->length-len; cout<<“分配成功!n”; DispSpace();return; } else {//当两者长度相等 q=p->next; p->next=q->next; cout<<“分配成功!n”; DispSpace();return; } } cout<<“分配失败!n”; DispSpace();return;} void CallBack(int sta,int len){ // 回收内存 SP p=Head,q=p->next,r;// 开始地址和长度 p->end=0; int en=sta+len; while(q){ if(sta == 0){ // 初始地址为0 if(en == q->start){ // 正好回收 q->start=0; q->length=q->end; return; } else { r=(SP)malloc(sizeof(SNode)); r->start=sta;r->length=len;r->end=en; p->next=r; r->next=q; return; } } else if((p->end < sta)&&(q->start > en)){ // 上邻区 r=(SP)malloc(sizeof(SNode)); r->start=sta;r->length=len;r->end=en; p->next=r; r->next=q; return; } else if((p->end < sta)&&(q->start == en)){ // 邻区相接 q->start=sta; q->length=q->end-sta; return; } else if((p->end == sta)&&(q->start < en)){ // 下邻区 p->end=en; p->length=en-p->start; return; } else if(p->end==sta && q->start==en){ // 邻区相接 p->end=q->end; p->length=p->end-p->start; p->next=q->next; return; } else { p=p->next; q=q->next; } } } void main(){ Initial(); cout<<“现在分配大小为 6K 的作业 4 申请装入主存: ”; Allocation(6);// 分配时参数只有长度 //--------指导书测试数据演示---------- cout<<“现回收作业 3(起址10,长度4)n”; CallBack(10,4); DispSpace(); cout<<“现回收作业 2(起址26,长度6)n”; CallBack(26,6); DispSpace(); //---------------演示结束------------- system(“pause”);} 五．实验结果与体会 我的体会： 河南师范大学计算机与信息技术学院实验报告 实验五 存储管理 一、实验目的、加深对操作系统存储管理的理解、能过模似页面调试算法，加深理解操作系统对内存的高度管理 二、总的设计思想、环境语言、工具等总的设计思想： 1、编写函数计算并输出下述各种算法的命中率 ① OPT页面置换算法 OPT所选择被淘汰的页面是已调入内存，且在以后永不使用的，或是在最长时间内不再被访问的页面。因此如何找出这样的页面是该算法的关键。可为每个页面设置一个步长变量，其初值为一足够大的数，对于不在内存的页面，将其值重置为零，对于位于内存的页面，其值重置为当前访问页面与之后首次出现该页面时两者之间的距离，因此该值越大表示该页是在最长时间内不再被访问的页面，可以选择其作为换出页面。② FIFO页面置换算法 FIFO总是选择最先进入内存的页面予以淘汰，因此可设置一个先进先出的忙页帧队列，新调入内存的页面挂在该队列的尾部，而当无空闲页帧时，可从该队列首部取下一个页帧作为空闲页帧，进而调入所需页面。③ LRU页面置换算法 LRU是根据页面调入内存后的使用情况进行决策的，它利用“最近的过去”作为“最近的将来”的近似，选择最近最久未使用的页面予以淘汰。该算法主要借助于页面结构中的访问时间time来实现，time记录了一个页面上次的访问时间，因此，当须淘汰一个页面时，选择处于内存的页面中其time值最小的页面，即最近最久未使用的页面予以淘汰。 ④ LFU页面置换算法 LFU要求为每个页面配置一个计数器（即页面结构中的counter），一旦某页被访问，则将其计数器的值加1，在需要选择一页置换时，则将选择其计数器值最小的页面，即内存中访问次数最少的页面进行淘汰。⑤ NUR页面置换算法 NUR要求为每个页面设置一位访问位（该访问位仍可使用页面结构中的counter表示），当某页被访问时，其访问位counter置为1。需要进行页面置换时，置换算法从替换指针开始（初始时指向第一个页面）顺序检查处于内存中的各个页面，如果其访问位为0，就选择该页换出，否则替换指针下移继续向下查找。如果内存中的所有页面扫描完毕未找到访问位为0的页面，则将替换指针重新指向第一个页面，同时将内 河南师范大学计算机与信息技术学院实验报告 存中所有页面的访问位置0，当开始下一轮扫描时，便一定能找到counter为0的页面。 2、在主函数中生成要求的指令序列，并将其转换成页地址流；在不同的内存容量下调用上述函数使其计算并输出相应的命中率。 环境语言：Linux下的GNU 编译环境 三、数据结构与模块说明 程序中用到的数据结构、类型定义及主要的函数原型如下： 1、数据结构 （1）页面结构 typedef struct{ int pn, pfn, counter, time;} pl_type;pl_type pl[total_vp];其中pn为页面号（页号），pfn为页帧号（物理块号），counter为一个周期内访问该页面的次数，time为访问时间；pl[total_vp]为页面结构数组，由于共有320条指令，每页可装入10条指令，因此虚页长total_vp的值为32。 （2）页帧控制结构 struct pfc_struct{ int pn, pfn;struct pfc_struct *next;};typedef struct pfc_struct pfc_type;pfc_type pfc[total_vp], *freepf_head, *busypf_head, *busypf_tail;其中pfc[total_vp]定义用户进程的页帧控制结构数组，在该实验中，用户内存工作区是动态变化的，最多可达到用户进程的虚页数目，即32个物理块。 *freepf_head为空闲页帧头的指针 *busypf_head为忙页帧头的指针 *busypf_tail忙页帧尾的指针 2、变量定义 (1)int a[total_instruction]: 指令流数组(2)int diseffect: 页面失效次数 (3)int page[total_instruction]: 每条指令所属页面号 (4)int offset[total_instruction]: 每页装入10条指令后取模运算得出的页内偏移地址(5)int total_pf: 用户进程的内存页帧数 河南师范大学计算机与信息技术学院实验报告 3、主要函数 (1)void initialize(int): 初始化函数 该函数主要对页面结构数组pl和页帧结构数组pfc进行初始化，如置页面结构中的页面号pn，初始化页帧号pfn为空，访问次数counter为0，访问时间time为-1；同样对页帧数组进行初始化，形成一个空闲页帧队列。 (2)void OPT(int): 计算使用最佳页面算法时的命中率 (3)void FIFO(int): 计算使用先进先出页面置换算法时的命中率(4)void LRU(int): 计算使用最近最久未使用页面置换算法时的命中率(5)void LFU(int): 计算使用最少使用置换算法时的命中率(6)void NUR(int): 计算使用最近未使用置换算法时的命中率 四、主要算法的设计与实现 void FIFO(int total_pf)/*先进先出页面置换算法*/ { int i,j;pfc_type *p;initialize(total_pf);busypf_head=busypf_tail=NULL;for(i=0;i if(pl[page[i]].pfn==INVALID)/*页面失效*/ { diseffect=diseffect+1; if(freepf_head==NULL)/*无空闲页帧*/ { } p=freepf_head->next;//有空闲页帧 freepf_head->next=NULL;freepf_head->pn=page[i];/* 将所需页面调入空闲页帧 */ pl[page[i]].pfn=freepf_head->pfn;if(busypf_tail==NULL)/* 若忙页帧队列为空，则将其头尾指针都指向刚调入页p=busypf_head->next;pl[busypf_head->pn].pfn=INVALID;//将忙页帧队首页面作为换出页面 freepf_head=busypf_head;freepf_head->next=NULL;busypf_head=p;//忙页帧头指针后移 面所在的页帧 */ 河南师范大学计算机与信息技术学院实验报告 busypf_head=busypf_tail=freepf_head;else{ //否则，将刚调入页面所在的页帧挂在忙页帧队列尾部 } freepf_head=p;//空闲页帧头指针后移 busypf_tail->next=freepf_head;busypf_tail=freepf_head;} } printf(“FIFO:%6.4f ”,1-(float)diseffect/320);} void LRU(int total_pf)/*最近最久未使用页面置换算法*/ { int i,j;int min,minj,present_time;initialize(total_pf);present_time=0;for(i=0;i if(pl[page[i]].pfn==INVALID)/*页面失效*/ { diseffect++;if(freepf_head==NULL)/*无空闲页帧*/ { min=32767;for(j=0;j } freepf_head=&pfc[pl[minj].pfn];//腾出一个单元 pl[minj].pfn=INVALID;pl[minj].time=-1;freepf_head->next=NULL;if(min>pl[j].time && pl[j].pfn!=INVALID){ } min=pl[j].time;minj=j;面*/ } pl[page[i]].pfn=freepf_head->pfn;//有空闲页面,改为有效 pl[page[i]].time=present_time;//修改页面的访问时间 河南师范大学计算机与信息技术学院实验报告 } freepf_head=freepf_head->next;//减少一个free 页面 else pl[page[i]].time=present_time;//命中则修改该单元的访问时间 present_time++;} printf(“LRU:%6.4f ”,1-(float)diseffect/320);} void NUR(int total_pf)/* 最近未使用页面置换算法 */ { int i,j,dp,cont_flag,old_dp;initialize(total_pf);dp=0;for(i=0;i if(pl[page[i]].pfn==INVALID)/*页面失效*/ { diseffect++;if(freepf_head==NULL)/*无空闲页帧*/ { cont_flag=TRUE;old_dp=dp;while(cont_flag){ if(pl[dp].counter==0&&pl[dp].pfn!=INVALID) cont_flag=FALSE;//找到位于内存且未被访问的页面 else { dp++; if(dp==total_vp)dp=0;//将替换指针重新指向第一个页面 if(dp==old_dp) {/* 若内存中所有页面扫描完毕未找到访问位为0的页面，将内存中所有页面的访问位置0 */ } freepf_head=&pfc[pl[dp].pfn];//腾出一个单元 } } for(j=0;j pl[j].counter=0; 河南师范大学计算机与信息技术学院实验报告 } pl[dp].pfn=INVALID;freepf_head->next=NULL; } pl[page[i]].pfn=freepf_head->pfn;//有空闲页面,改为有效 freepf_head=freepf_head->next;//减少一个free 页面 else pl[page[i]].counter=1;//命中则将访问位置1 if(i%clear_period==0)//清零周期到，将所有访问位清零 { for(j=0;j } } } void OPT(int total_pf)/* 最佳页面置换算法 */ { int i,j,max,maxpage,d,dist[total_vp];initialize(total_pf);for(i=0;i for(j=0;j } d=1;/* 对于位于内存且在当前访问页面之后将再次被访问的页面，dist重置为当前页 面与之后首次出现该页面时两者之间的距离 */ for(j=i+1;j dist[j]=32767;printf(“NUR:%6.4f ”,1-(float)diseffect/320); else //不在内存的页面该变量则置为0 dist[j]=0; 河南师范大学计算机与信息技术学院实验报告 } } if(pl[page[j]].pfn!=INVALID && dist[page[j]]==32767) dist[page[j]]=d; d++;max=-1;//查找dist变量值最大的页面作为换出页面 for(j=0;j } freepf_head=&pfc[pl[maxpage].pfn];//腾出一个单元 freepf_head->next=NULL;pl[maxpage].pfn=INVALID;if(max } max=dist[j];maxpage=j; } } pl[page[i]].pfn=freepf_head->pfn;//有空闲页面,改为有效 freepf_head=freepf_head->next;//减少一个free 页面 printf(“OPT:%6.4f ”,1-(float)diseffect/320);} void LFU(int total_pf)/* 最少使用页面置换算法 */ { int i,j,min,minpage;initialize(total_pf);for(i=0;i min=32767;for(j=0;j if(min>pl[j].counter&&pl[j].pfn!=INVALID){ 河南师范大学计算机与信息技术学院实验报告 } } } min=pl[j].counter;minpage=j;pl[j].counter=0; freepf_head=&pfc[pl[minpage].pfn];//腾出一个单元 pl[minpage].pfn=INVALID;freepf_head->next=NULL; pl[page[i]].pfn=freepf_head->pfn;//有空闲页面,改为有效 pl[page[i]].counter++;//增加页面访问次数 freepf_head=freepf_head->next;//减少一个free 页面 } else pl[page[i]].counter++;//命中增加页面访问次数 } printf(“LFU:%6.4f ”,1-(float)diseffect/320);} 五、运行结果 本实验的运行结果如下图所示（以OPT、FIFO、LRU为例）： 从上述结果可知，随着内存页面数的增加，三种算法的访问命中率逐渐增大。在内存页面数为4~25个页面之间时，三种算法的命中率大致在56%至88%之间变化，但是，OPT算法和其他两种算法之间的差别一般在6~12个百分点左右。在内存页面为25~32个页面时，由于用户进程的所有指令基本上都已装入内存，从而命中率增加较大，各种算法之间的差别不大。 河南师范大学计算机与信息技术学院实验报告 比较上述三种算法，OPT算法的命中率最高，LRU算法和FIFO算法的命中率则较为接近。 六、总结 经过测试结果完全正常。经过编写和学习让我对操作系统方面的知识更深一步的得到了理解和巩固。让我在今后的学习中可以更好的去理解和体会。第二篇：操作系统试验动态分区分配
第三篇：计算机操作系统动态分区存储管理方式下的内存空间的分配与回收实验报告
第四篇：操作系统实验报告-可变分区存储管理方式的内存分配回收
第五篇：操作系统存储管理实验介绍
点击咨询 