操作系统课程设计_动态分区分配存储管理_动态分区存储管理实例
操作系统课程设计_动态分区分配存储管理由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“动态分区存储管理实例”。
操作系统课程设计
设计题目 动态分区分配存储管理
学生姓名学
号 专业班级 指导教师
吕 霆
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 #include #include using namespace std;ofstream stream;//输出流对象 int ary1[20][4];//内存分配状态 int ary2[20][3];//空闲分区状态 int ary3[10];//进程分配状态
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
} 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 >choice2;q=choice2;cout
} cout>j;ary3[i]=j;
}
//内存信息的手动生成 int create_fenqu(){
}
//首次适应算法 void first_fit()int k,x,y,o=0;int a=0;cout>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]
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=ary3[i])&&(e>ary2[s][1]))//满足分配要求 { e=ary2[s][1];} j=s;for(i=0;i
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=ary3[i])&&(e
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
} 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
cout
} 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
} 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
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
} 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
}
}
} if((ary1[recycle-2][3]==2)&&(ary1[recycle][3]==2))//空闲区上下邻接的都是已分配盘块 {
} ary1[recycle-1][3]=0;k=0;for(j=0;j
} vision();//cout
}
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
}
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 id1=0;//记录已经分配的内存数量 int 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
}
//主函数入口
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>choice1;
} 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
create_zuoye();create_fenqu();
} }
cout>o;flag=o;
cout>id1;if(id1==1)if(id1==2)if(id1==3)if(id1==4)if(id1==5)
} {first_fit();} {next_fit();} {best_fit();} {worst_fit();} { compact();} if(id1==6){ cout>recycle;if((recycle>m)||(recycle
} cout
} if(id2==-9999){ apply_recycle();} if(ary2[i][0]==recycle){
}
cout
