操作系统专业课程设计方案报告动态分区分配.doc

青岛理工大学
操作系统课程设计报告

院（系）： 计算机工程学院
专业： 计算机科学与技术专业
学生姓名： ＿＿牛利利
班级：＿＿ 计算073 ＿学号： 　07106 　
题目： ＿动态分区别配模仿＿＿＿＿
起迄日期： ＿7月5日至7月16日 ＿
设计地点： 2号实验楼402室　　
指 导 教 师： 李 兰

— 第 2 学期
完毕日期： 年 7 月 16 日

一、 课程设计目
操作系统是最重要计算机系统软件，同步也是最活跃学科之一。计算机系统由硬件和软件两某些构成。操作系统是配备在计算机硬件上第一层软件，是对硬件初次扩充。本次课程设计重要目是在学习操作系统理论知识基本上，对操作系统整体一种模仿。也是对本学期所学知识一种总体检测，使理论知识应用到实际编程中，依照理论算法来实现详细编程操作。同步通过本次课程设计加深对操作系统理论知识各个某些管理功能感性结识，进一步分析和理解各个某些之间联系和功能，最后达到对完整系统理解。同步，可以提高运用操作系统知识和解决实际问题能力；并且锻炼自己编程能力、创新能力以及开发软件能力；还能提高自己调查研究、查阅文献、资料以及编写软件设计文档能力并提高分析问题能力。
操作系统课程设计重要任务是研究计算机操作系统基本原理和算法，掌握操作系统存储器管理、设备管理、文献管理和进程管理基本原理和算法。使学生掌握基本原理和办法，最后达到对完整系统理解。
二、 课程设计内容
仿真实现动态可变分区存储管理模仿系统。内存调度方略可采用初次适应算法、循环初次适应算法和最佳适应法等，并对各种算法进行性能比较。为了实现分区别配，系统中必要配备相应数据构造，用来描述空闲区和已分派区状况，为分派提供根据。惯用数据构造有两种形式：空闲分区表和空闲分区链。为把一种新作业装入内存，须按照一定算法，从空闲分区表或空闲分区链中选出一种分区别配给该作业。
三、 系统分析与设计
1、系统分析：
动态分区别配是依照进程实际需要，动态地为之分派内存空间。在实现可变分区别配时，将涉及到分区别配中所用数据构造、分区别配算法和分区别配和回收操作这样三个问题。为了实现分区别配，系统中必要配备相应数据构造，用来描述空闲区和已分派区状况，为分派提供根据。惯用数据构造有两种形式：空闲分区表和空闲分区链。为把一种新作业装入内存，须按照一定算法，从空闲分区表或空闲分区链中选出一种分区别配给该作业。当前惯用分派算法有：初次适应算法、循环初次适应算法、最佳适应算法、最坏适应算法和迅速适应算法。在动态分区存储管理方式中，重要操作是分派内存和回收内存。
2、系统设计：
系统运用某种分派算法，从空闲分区表中找到所需大小分区。设祈求分区大小为u.size，表中每个空闲分区大小可表达为m.size，若 m.size-u.size≤size（size为事先规定不再切割剩余分区大小）成立，则阐明多余某些太小，可不再切割，将整个分区别配给祈求者；否则，从该分区中按祈求大小划分出一块内存空间分派出去，余下某些留在空闲区表中，然后将分派区首址返回给调用者。当进程运营完毕释放内存时，系统依照回收区首址，从空闲区表中找到相应插入点，并且按照四种状况进行插入。
3、模块设计：
(1) 空闲区阐明表构造：把空闲区定义为构造体变量，涉及空闲区始址，空闲区大小和空闲区状态，用0表达空表目，1为可用空闲块。
struct freearea
{
int startaddress;/*空闲区始址*/
int size;/*空闲区大小*/
int state;/*空闲区状态:0为空表目，1为可用空闲块*/
}freeblock[N]= {{1,20,20,1},{2,80,50,1},{3,150,30,1},{4,300,30,1},{5,500,10,1}}；(2) 为作业分派主存空间函数alloc()，三个算法分别相应三个分派主存空间算法。applyarea为作业申请量，tag为检查与否有满足作业需要空闲区标志。
初次适应算法:
检查空闲区阐明表与否有满足作业规定空闲区时,如果不不大于作业规定,则分派给作业,修改地址和空闲区大小,并将tag置“1”,表达有满足作业规定空闲区,返回为作业分派主存地址.程序如下所示：
if(freeblock[i].state==1&&freeblock[i].size>applyarea)
{
freeblock[i].startaddress=freeblock[i].startaddress+applyarea;
freeblock[i].size=freeblock[i].size-applyarea;
tag=1;
return freeblock[i].startaddress-applyarea;
}
如果空闲区等于作业规定，则分派给作业,修改地址和空闲区大小,并将tag置“1”,表达有满足作业规定空闲区,返回为作业分派主存地址.
if(freeblock[i].state==1&&freeblock[i].size==applyarea)
{freeblock[i].state=0;
tag=1;
return freeblock[i].startaddress;
}
如果没有满足条件空闲区，分派不成功，返回-1
if(tag==0)return -1;
循环初次适应算法alloc()函数与初次适应算法alloc()函数区别在于从哪里开始找与否有满足作业规定空闲区，它是从上次找到空闲区下一种空闲分区开始找，只需要变化for循环条件即可。
for(i=s;i<N;i++)
最佳适应算法：该算法总是把满足规定、又是最小空闲区别配给作业。检查空闲区阐明表与否有满足作业规定空闲区，也分为三种状况：不不大于，等于，不大于。若检查到有“等于”状况，就可以直接分派，若没有，则继续检查与否有“不不大于”状况：
if(freeblock[i].state==1&&freeblock[i].size==applyarea)
{
freeblock[i].state=0;
tag=1;
return freeblock[i].startaddress;
}
检查“不不大于”状况：先把所有不不大于所规定空闲区放入数组,
for(i=0;i<N;i++)
{
if(freeblock[i].state==1&&freeblock[i].size>applyarea)a[j++]=i;
}
再从数组中挑出最小那个：
果数组中元素不不大于一种，则需要一种个比较过去，然后取出最小那个分派给作业：
if(j>1)
{
h=a[0];
min=freeblock[h];
for(k=1;k<j;k++)
{
h=a[k];
if(freeblock[h].size<min.size)
{
mid.size=freeblock[h].size;
mid.state=freeblock[h].state;
mid.startaddress=freeblock[h].startaddress;
freeblock[h].size=min.size;
freeblock[h].state=min.state;
freeblock[h].startaddress=min.startaddress;
min.size=mid.size;
min.state=mid.state;
min.startaddress=mid.startaddress;
}
}
min.startaddress=min.startaddress+applyarea;
min.size=min.size-applyarea;
tag=1;
return min.startaddress-applyarea;
}
如果数组中只有一种元素，则直接分派给作业：
if(j==1)
{
h=a[0];
min=freeblock[h];
min.startaddress=min.startaddress+applyarea;
min.size=min.size-applyarea;
tag=1;
return min.startaddress-applyarea;
}
如果没有满足条件空闲区，分派不成功，返回-1
if(tag==0)return -1;
(3) 主存回收函数setfree()：tag1代表释放区高地址与否邻接一种空闲区，tag2代表释放区高低地址与否都邻接一种空闲区，tag3代表释放区低地址与否邻接一种空闲区。分为四种状况：
回收分区上邻和下邻分区都不是空闲，则直接将回收区有关信息记录在空闲区表中。
if(tag3==0)
{
for(j=0;j<N;j++)
{ if(freeblock[j].state==0)
{
freeblock[j].startaddress=s;
freeblock[j].size=l;
freeblock[j].state=1;
break;
}
}
}
回收分区上邻分区是空闲，需要将这两个相邻空闲区合并成一种较大空闲区， 然后修改空闲区表。
if(freeblock[i].startaddress==s+l&&freeblock[i].state==1)
{
l=l+freeblock[i].size;
tag1=1;
}
回收分区下邻分区是空闲区，需要将这两个相邻空闲区合并成一种空闲区，并修改 闲区表。
if(freeblock[i].startaddress+freeblock[i].size==s&&freeblock[i].state==1)
{
freeblock[i].size=freeblock[i].size+l;
tag3=1;
break;
}
回收分区上邻和下邻都是空闲区，则需要将这三个空闲区合并成一种更大空闲区， 然后修改空闲区表。先判断有上邻空闲区（如所示），再判断有下邻空闲区（如所示），若均有，则将tag2置1。
(4) 对空闲区表中空闲区调节函数adjust()：使空闲区按始地址从小到大排列，空表目放在最背面。
(5) 打印空闲区阐明表函数：print()
(6) 初次适应算法函数First_fit():若有作业需要分派内存，则对空闲区表中空闲区进行调节，调用调节函数adjust()，再将其打印出来；输入作业申请量，调用alloc()函数为作业分派空间，分派结束后，要进行主存回收，再次调节空闲区表后，打印出来。循环执行直到没有作业为止。
(7) 循环初次适应算法Next_fit():与初次适应算法不同是，循环初次适应算法要记录上次找到空闲区地址，并在下次分派时从这个地址开始。
(8) 最佳时应算法Best_fit():该算法在分派内存时，把所有满足规定空闲区中最小那个空闲区别配给祈求进程。
（9）主函数main()：重要用于调用各个函数来实现各项功能和显示主界面。
4、数据构造阐明：
(1) 空闲区阐明表构造struct freearea：把空闲区定义为构造体变量，涉及空闲区始址，空闲区大小和空闲区状态，用0表达空表目，1为可用空闲块。
(2) 为作业分派主存空间函数alloc()，三个算法分别相应三个分派主存空间算法。applyarea为作业申请量，tag为检查与否有满足作业需要空闲区标志。
(3) 主存回收函数setfree()：tag1代表释放区高地址与否邻接一种空闲区，tag2代表释放区高低地址与否都邻接一种空闲区，tag3代表释放区低地址与否邻接一种空闲区。分为四种状况。
(4) 对空闲区表中空闲区调节函数adjust()：使空闲区按始地址从小到大排列，空表目放在最背面。
(5) 打印空闲区阐明表函数：print()
(6) 初次适应算法函数First_fit():若有作业需要分派内存，则对空闲区表中空闲区进行调节，调用调节函数adjust()，再将其打印出来；输入作业申请量，调用alloc()函数为作业分派空间，分派结束后，要进行主存回收，再次调节空闲区表后，打印出来。循环执行直到没有作业为止。
(7) 循环初次适应算法Next_fit():与初次适应算法不同是，循环初次适应算法要记录上次找到空闲区地址，并在下次分派时从这个地址开始。
(8) 最佳时应算法Best_fit():该算法在分派内存时，把所有满足规定空闲区中最小那个空闲区别配给祈求进程。
（9）主函数main()：重要用于调用各个函数来实现各项功能和显示主界面。
5、算法流程图
否
是
否
是
否
是
从头开始查表
检索完毕？
m.size>u.size?
m.size-u.size≤size？
从该分区中划出u.size大小分区
将该分区别配给祈求者并修改关于数据构造
返回
返回
继续检索下一种表项
将该分区从表中移出

内存分派流程
是
否
是
否
是
是
否
是
否
否
是
是
开始
ch=1?
First_fit()
ch=2?
Next_fit()
ch=3?
Best_fit()
Choice=0?
choice=1?
分派内存
Choice=2?
回收内存
Choice=3?
查看空闲区表
结束

主函数流程图

四、 模块调试与系统测试
1、模块调试
l 输入形式和输入值范畴
一方面打开主界面输入整形常数选取所要使用算法，再依照界面上提示内容进行输入整形常数选取所要进行操作，重要涉及作业申请量、释放起始地址、释放区大小。
l 输出形式
输出形式重要涉及空闲区表状态、申请作业起始地址和作业申请量。
l 程序所能达到功能
程序所能达到功能重要涉及：初始化空闲区表状态，按照初次适应算法、循环初次适应算法和最佳适应算法对内存空间进行分派，对内存空间进行回收并输出进行各项操作后空闲区表状态。
2、系统测试
l 测试办法
本系统采用黑盒测试办法进行测试。
l 测试数据及测试报告
试用例数据
预测成果
实际成果
与否相符
合法：
输入1—3进行算法选取
成功进入下一步
成功进入下一步
相符
非法：
输入1—3以外数据
显示出错提示“有误，请重新输入”
显示出错提示“有误，请重新输入”
相符
合法：
输入0—3选取操作
成功选取所要进行操作
成功选取所要进行操作
相符
非法：
输入1—3以外数据
显示“输入有误，请重试”
显示“输入有误，请重试”
相符

合法：
输入分派内存操作下申请量为20
显示：申请作业起始地址、申请量和内存分派成功
显示：申请作业起始地址、申请量和内存分派成功
相符
非法：
输入内存分派操作下申请量为60
显示：作业申请量过大，分派失败
显示：作业申请量过大，分派失败
相符

3、调试分析：
在调试过程中定义为作业分派主存空间函数alloc2()时程序浮现错误，重要因素是由于for循环编写浮现错误，由于alloc2()与alloc()重要差别就在于for循环，最后通过查阅课本从主线上理解了初次适应算法和循环初次适应算法本质区别，最后使错误得以解决程序对的运营。在编写alloc3()时，引入数组将总体状况分为大两种，并在数组中又分为两种小状况。但是在考虑所有不不大于所规定空闲区放入数组时，落拉了只有一种数组状况，最后通过自己仔细检查和同窗协助使错误得以解决。
在编写主存回收函数setfree()时由于对在空闲表中恰当位置进行插入时状况考虑不全面，使得其中一种状况落拉导致编程浮现错误，最后通过仔细阅读课本和同窗协助并在网上收索有关知识使得错误得以解决。在编写对空闲区表中空闲区调节函数adjust（）时也多次浮现 错误，最后通过同窗协助和在网上收索有关知识，借鉴别人算法使得错误得以解决。
五、 顾客手册
本系统是用C++语言编写，使用Microsoft Visual C++平台开发，不需要安装。经运营验证本程序可正常运营。详细使用环节如下：
（1） 通过编译、链接无误后便可正常运营，浮现主界面
依照主界面上显示选取所要使用动态分区别配算法。
（2） 选取所要使用算法之后就会显示所要进行各项操作如下
① 若选取1分派内存则依照界面提示输入作业申请量则会弹出申请作业起始地址和作业申请量
② 若选取2回收内存则界面提示输入释放区起始地址和释放区大小，输入之后则会自动显示空闲区表状态
③ 若选取3查看空闲区表则输入3之后界面就会自动显示当前空闲区表状态
④ 若选取0退出则系统会回到刚开始初始界面状态重新选取动态分区别配算法
六、 程序清单
/*动态分区别配与回收演示程序*/
#include <iostream.h>
#include <stdio.h>
#define N 5
int start;//存储首址

struct freearea /*定义一种空闲区阐明表构造，并初始化变量*/
{
int ID;/*分区号*/
int startaddress;/*空闲区始址*/
int size;/*空闲区大小*/
int state;/*空闲区状态:0为空表目，1为可用空闲块*/
}freeblock[N]={{1,20,20,1},{2,80,50,1},{3,150,30,1},{4,300,30,1},{5,500,10,1}};
/*定义为作业分派主存空间函数alloc(),给初次适应算法调用*/
int alloc(int applyarea)
{
int i,tag=0; /*applyarea为作业申请量,tag为检查与否有满足作业需要空闲区标志*/
for(i=0;i<N;i++) /*检查空闲区阐明表与否有满足作业规定空闲区*/
if(freeblock[i].state==1&&freeblock[i].size>applyarea)
{
freeblock[i].startaddress=freeblock[i].startaddress+applyarea;
freeblock[i].size=freeblock[i].size-applyarea;
tag=1; /*有满足条件空闲区时，tag置1*/
return freeblock[i].startaddress-applyarea； /*返回为作业分派主存地址*/
}
else
if(freeblock[i].state==1&&freeblock[i].size==applyarea)
{
freeblock[i].state=0;
tag=1; /*有满足条件空闲区时，tag置1*/
return freeblock[i].startaddress; /*返回为作业分派主存地址*/
}
if(tag==0)
return -1; /*没有满足条件空闲区，分派不成功，返回-1*/
}

/*定义为作业分派主存空间函数alloc2(),给循环初次适应算法调用*/
int alloc2(int applyarea,int s) /*applyarea为作业申请量*/
{
int i,tag=0; /*tag为检查与否有满足作业需要空闲区标志*/
for(i=s;i<N;i++)/*检查空闲区阐明表与否有满足作业规定空闲区,从上次找到空闲去下一种空闲分区开始找*/
if(freeblock[i].state==1&&freeblock[i].size>applyarea)
{
freeblock[i].startaddress=freeblock[i].startaddress+applyarea;
freeblock[i].size=freeblock[i].size-applyarea;
tag=1; /*有满足条件空闲区时，tag置1*/
start=freeblock[i].startaddress-applyarea;
return i;
}
else
if(freeblock[i].state==1&&freeblock[i].size==applyarea)
{
freeblock[i].state=0;
tag=1; /*有满足条件空闲区时，tag置1*/
start=freeblock[i].startaddress; /*返回为作业分派主存地址*/
return i;
}
if(tag==0)
return -1; /*没有满足条件空闲区，分派不成功，返回-1*/

}
/*定义为作业分派主存空间函数alloc3(),给最佳适应算法调用*/
int alloc3(int applyarea) /*applyarea为作业申请量*/
{
int i,k,h,flag,tag=0,j=0; /*tag为检查与否有满足作业需要空闲区标志*/
int a[N];
struct freearea min;
struct freearea mid;
for(i=0;i<N;i++) /*检查空闲区阐明表与否有满足作业规定空闲区*/
{
if(freeblock[i].state==1&&freeblock[i].size==applyarea)//大小刚好相等
{
freeblock[i].state=0;
tag=1; /*有满足条件空闲区时，tag置1*/
return freeblock[i].startaddress; /*返回为作业分派主存地址*/
}
}
for(i=0;i<N;i++)//把所有不不大于所规定空闲区放入数组,挑出最小那个
{
if(freeblock[i].state==1&&freeblock[i].size>applyarea)a[j++]=i;
}
if(j>1)
{
h=a[0];
min=freeblock[h];
//min.startaddress=freeblock[h].startaddress;
//min.size=freeblock[h].size;
//min.state=freeblock[h].stat

for(k=1;k<j;k++)
{
h=a[k];
if(freeblock[h].size<min.size)
{
mid.size=freeblock[h].size;
mid.state=freeblock[h].state;
mid.startaddress=freeblock[h].startaddress;
freeblock[h].size=min.size;
freeblock[h].state=min.state;
freeblock[h].startaddress=min.startaddress;
min.size=mid.size;
min.state=mid.state;
min.startaddress=mid.startaddress;
}
}
min.startaddress=min.startaddress+applyarea;
min.size=min.size-applyarea;
tag=1; /*有满足条件空闲区时，tag置1*/
return min.startaddress-applyarea;
}
else if(j==1)
{
h=a[0];
min=freeblock[h];
min.startaddress=min.startaddress+applyarea;
min.size=min.size-applyarea;
tag=1; /*有满足条件空闲区时，tag置1*/
return min.startaddress-applyarea;
}

if(tag==0)
return -1; /*没有满足条件空闲区，分派不成功，返回-1*/
}
/*定义主存回收函数：setfree()
tag1代表释放区高地址与否邻接一种空闲区，
tag2代表释放区高低地址与否都邻接一种空闲区，
tag3代表释放区低地址与否邻接一种空闲区*/
void setfree()
{
int s,l,tag1=0,tag2=0,tag3=0,i,j;
printf("请输入释放区起始地址:");
scanf("%d",&s); /*输入释放区开始地址*/
printf("请输入释放区大小:");
scanf("%d",&l); /*输入释放区大小*/
printf("************回收内存后空闲区表状态如下**********\n");

for(i=0;i<N;i++)
{
if(freeblock[i].startaddress==s+l&&freeblock[i].state==1)
{
l=l+freeblock[i].size;
tag1=1; /*有与释放区高地址邻接空闲区，tag1置1*/
for(j=0;j<N;j++)
if(freeblock[j].startaddress+freeblock[j].size==s&&freeblock[j].state==1)
{
freeblock[i].state=0;
freeblock[j].size=freeblock[j].size+l;
tag2=1;/*有与释放区上下都邻接空闲区，tag2置1*/
break;
}
if(tag2==0) /*无与释放区高低地址邻接空闲区*/
{
freeblock[i].startaddress=s;
freeblock[i].size=l;
break;
}
}
}

if(tag1==0) /*无与释放区高地址邻接空闲区，并检查与否低地址有邻接空闲区*/
{
for(i=0;i<N;i++)
if(freeblock[i].startaddress+freeblock[i].size==s&&freeblock[i].state==1)
{
freeblock[i].size=freeblock[i].size+l;
tag3=1; /*有与释放区低地址邻接空闲区*/
break;
}
if(tag3==0) /*无与释放区低地址邻接空闲区*/
for(j=0;j<N;j++)
if(freeblock[j].state==0)/*找一种空表目，将释放区放入表中*/
{
freeblock[j].startaddress=s;
freeblock[j].size=l;
freeblock[j].state=1;
break;
}
}
}
/*定义对空闲区表中空闲区调节函数adjust(),
使空闲区按始地址从小到大排列，空表目放在最背面*/
void adjust()
{
int i,j;
struct freearea middata;
for(i=0;i<N;i++) /*将空闲区按始地址顺序在表中排列*/
for(j=0;j<N;j++)
if(freeblock[j].startaddress>freeblock[j+1].startaddress)
{
middata.startaddress=freeblock[j].startaddress;
middata.size=freeblock[j].size;
middata.state=freeblock[j].state;
freeblock[j].startaddress=freeblock[j+1].startaddress;
freeblock[j].size=freeblock[j+1].size;
freeblock[j].state=freeblock[j+1].state;
freeblock[j+1].startaddress=middata.startaddress;
freeblock[j+1].size=middata.size;
freeblock[j+1].state=middata.state;
}
for(i=0;i<N;i++) /*将空表目放在表背面*/
for(j=0;j<N;j++)
if(freeblock[j].state==0&&freeblock[j+1].state==1)
{
middata.startaddress=freeblock[j].startaddress;
middata.size=freeblock[j].size;
middata.state=freeblock[j].state;
freeblock[j].startaddress=freeblock[j+1].startaddress;
freeblock[j].size=freeblock[j+1].size;
freeblock[j].state=freeblock[j+1].state;
freeblock[j+1].startaddress=middata.startaddress;
freeblock[j+1].size=middata.size;
freeblock[j+1].state=middata.state;
}
}
/*定义打印空闲区阐明表函数：print()*/
void print()
{
int i;
printf(" |---------------------------------------------------------------|\n");
printf(" | ID start size state |\n");
printf(" |---------------------------------------------------------------|\n");
for(i=0;i<N;i++)
{
printf(" | %3d %3d %3d %3d |\n",
freeblock[i].ID,freeblock[i].startaddress,freeblock[i].size,freeblock[i].state);
printf(" |---------------------------------------------------------------|\n");
}
}

//初次
void First_fit()
{
int applyarea,start;
{
printf("请输入作业申请量:");
scanf("%d",&applyarea);/*输入作业申请量*/
start=alloc(applyarea);/*调用alloc()函数为作业分派空间，start为返回始地址*/
if(start==-1) /*alloc()分派不成功时，返回-1*/
printf("作业申请量过大，空闲区表中存储空间无法满足，分派失败\n");
else
{
adjust();
printf("申请作业起始地址为:%d\n",start);
printf("作业申请量为:%d\n",applyarea);
printf("内存分派成功\n");
}
}
}

//循环初次
void Next_fit()
{
int appl