动态可变分区存储管理模拟系统

青 岛 农 业 大 学 理学与信息科学学院

操 作 系 统 课 程 设 计 报 告

设 计 题 目 仿真实现动态可变分区存储管理模拟系统 —最佳适应算法和最先适应算法

学生专业班级 计算机科学与技术2011级03班

学生姓名（学号） 张明珠（H20110684 ）

设计小组其他同学姓名（学号） 刘玉婷（H20110661）

宋璇（H20110162）

指 导 教 师 牟春莲

完 成 时 间 2014. 06.15

实 习（设计）地点 信息楼218

2014年6月16日

一、课程设计目的

操作系统的理论知识只有通过操作系统的实际操作和编程才能真正地理解和掌握，没有实践操作系统的操作和编程，学习操作系统就是纸上谈兵。操作系统课程设计是在学习完《操作系统》课程后进行的一次全面、综合实习，是计算机科学与技术专业的重要实践性教学环节。通过课程设计，达到如下目的：

1、巩固和加深对操作系统原理的理解，提高综合运用本课程所学知识的能力。

2、培养学生选用参考书，查阅手册及文献资料的能力；培养独立思考、深入研究、分析问题、解决问题的能力。

3、通过实际操作系统的分析设计、编程调试，掌握系统软件的分析方法和工程设计方法。

4、能够按要求编写课程设计报告书，能正确阐述设计过程和实验结果、正确绘制系统和程序框图。

5、通过课程设计，培养学生严谨的科学态度、严肃认真的工作作风和团队协作精神。

二、设计任务

题目描述：

仿真实现动态可变分区存储管理模拟系统。内存调度策略可采用最先适应算法、最佳适应法等，并对各种算法进行性能比较。为了实现分区分配，系统中必须配置相应的数据结构，用来描述空闲区和已分配区的情况，为分配提供依据。常用的数据结构有两种形式：空闲分区表和空闲分区链。为把一个新作业装入内存，须按照一定的算法，从空闲分区表或空闲分区链中选出一个分区分配给该作业. 设计要求：

1．采用指定算法模拟动态分区管理方式的主存分配。能够处理以下的情形： ⑴ 随机出现的进程i申请jKB内存，程序能判断是否能分配，如果能分配，要求输出分配的首地址Faddress，并要求输出内存使用情况和空闲情况。

内存情况输出的格式为：Faddress该分区的首地址；Eaddress该分区的尾地址Len 分区长度；Process 如果使用，使用的进程号，否则为0。

⑵ 主存分配函数实现寻找空闲区、空闲区表的修改、已分配区表的修改功能。 成员分工：

张明珠 申请内存、查看进程之间的前后的区域状态、释放进程

刘玉婷 最先适应算法、将其释放的内存插入空闲块中、初始化 宋璇 最佳适应算法、将新项插入已分配表中、退出

张明珠 宋璇 刘玉婷 整个界面的优化 、界面设计、总体思路

三、分析与设计

1．设计思路

存储器是计算机的重要组成部分,存储空间是操作系统管理的宝贵资源,虽然其容量在不断扩大,但仍然远远不能满足软件发展的需要。对存储资源进行有效的管理,不仅关系到存储器的利用率,而且还对操作系统的性能和效率有很大的影响。

操作系统的存储管理的基本功能有：存储分配、地址转换和存储保护、存储共享、存储扩充。存储分配指为选中的多道运行的作业分配主存空间；地址转换是把逻辑地址空间中的用户程序通过静态重定位或动态重定位转换和映射到分给的物理地址空间中,以便用户程序的执行；存储保护指各道程序只能访问自己的存储区域,而不能互相干扰,以免其他程序受到有意或无意的破坏；存储共享指主存中的某些程序和数据可供不同用户进程共享。

最简单的单道系统中,一旦一个程序能装入主存,它将一直运行直到结束。如果程序长度超出了主存的实际容量,可以通过覆盖和交换的技术获得解决。更多的操作系统支持多个用户进程在主存同时执行,能满足多道程序设计需要的最简单的存储管理技术是分区方式,有分固定分区和可变分区。可变分区的分配（如图（1）所示）算法包括：最先适应、下次适应、最佳适应、最坏适应和快速适应等分配算法。

图（1）动态内存分配

采用分区方式管理存储器,每道程序总是要求占用主存的一个或几个连续的存储区域,主存中会产生许多碎片。因此,有时为了接纳一个新的作业而往往要移

动已在主存的信息,这不仅不方便,而且开销不小。现代计算机都有某种虚存硬设备支持,简单也是常用的虚存是请求分页式虚存管理,于是允许把一个进程的页面存放到若干不相邻的主存页框中。

从搜索速度上看，最先适应算法具有最佳性能。从回收过程来看，最先适应法也是最佳的。最先适应算法要求可用表或自由链接按起始地址递增的次序排列。该算法的最大特点是一旦找到大于或等于所要求内存的长度的分区，则搜索结束。其优点：

（1）、在释放内存分区时，如果有相邻的空白区就进行合并，使其成为一个较大的空白区；

（2）、本算法的实质是尽可能的利用存储器的低地址部分，在高地址部分则保留较多的或较大的空白区，以后如果需要较大的空白区，就容易能够满足。 最佳适应算法：从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区。

最佳适应算法将可利用空间表中一个大小不小于“请求”且最接近“请求”的空闲块的一部分分配给用户。分配与回收都需要对可利用空间表从头至尾查询一遍。为了避免每次分配都要查询整个链表，通常要求节点从大到小排序，由此只需找到第一个足够大的空闲块即可予以分配。但回收时，必须把回收的空闲块放置在符合大小顺序关系的链表位置。在分配时容易产生太小而无法利用的内存碎片，同时这种做法也保留了那些很大的内存块以备响应将来发生的内存量较大的用户“请求”，从而使整个链表逐渐趋向于节点大小差别甚远的状态。这种分配算法适合请求分配内存大小范围较广的系统，此算法比较费时间。

在进行内存分配时，从空闲分区表(或空闲分区链)首开始顺序查找，直到找到第一个能满足其大小要求的空闲分区为止。如果该空闲分区大于作业的大小，则从该分区中划出一块内存空间分配给请求者，将剩余空闲区仍然留在空闲分区表(或空闲分区链)中。最佳适应算法的特点：

按最佳适应算法为作业分配内存，就能把既满足作业要求又与作业大小最接近的空闲分区分配给作业。保留了大的空闲区，但分割后的剩余空闲区很小。

本课程设计就是分析动态分区法，与固定分区法相比，动态分区法在作业执行前并不建立分区，分区的建立是在作业的处理过程中进行的。且其大小可随作业或进程对内存的要求而改变分区的建立是在作业的处理过程中进行的。且其大小可随作业或进程对内存的要求而改变。这就改变了固定分区法中那种即使是小作业也要占据大分区的浪费现象，从而提高了内存的利用率。

2. 概要设计

动态分区分配是根据进程的实际需要，动态地为之分配内存空间。在实现可变分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配和回收操作这样三个问题。为了实现分区分配，系统中必须配置相应的数据结构，用来描述空闲区和已分配区的情况，为分配提供依据。常用的数据结构有两种形式：空闲分区表和空闲分区链。为把一个新作业装入内存，须按照一定的算法，从空闲分区表或空闲分区链中选出一个分区分配给该作业。目前常用的分配算法有：首次适应算法、循环首次适应算法、最佳适应算法、最坏适应算法和快速适应算法。在动态分区存储管理方式中，主要操作是分配内存和回收. 系统模块划分：

最 最 先 佳 适 适 应 应 图（2）各模块划分图 算 算 主流程图： 法 法 初 始 化 内 存 申 请 内 存 释 放 内 存 查 看 空 闲 区 查 看 已 分 配 区 查 看 内 存 状 态 退 出 动态可变分区存储管理模拟系统

图(9) 申请内存图

图（10）查看已分配区图

图（11）查看空闲区图

图（12）释放内存图

图（13）查看内存状态图

最佳算法和最先算法的比较：

图（13）两算法的对比图

五、程序清单 #include using namespace std; #include struct area {

int start; 定义分区的首地址 int end; 定义分区的尾地址 int len; 定义分区的长度 int sign;定义分区的进程号 struct area * next;定义进程的指针 };

struct area*freehead=NULL;声明 freehead 是型结构指针。 初始freehead指针为空。 struct area*usedhead=NULL;声明 usedhead 是型结构指针。初始usedhead指针为空。 void create();创建内存区 void print(area*); void ask(area*); void ask1(area*); void correct(area*,int);

area * delempty();初始化 void inserused(area *,int ,int ); void inserfree(area * ); void setfree();

void listID();//最先适应法 void listlen();/最优适应法 void swap(area *,area *); //初始化

area * delempty(){ }

//最优适应法 void listlen(){

int n=0; 初始为零

area *p9=freehead->next,*p0=freehead,*p11,*p12,*p13; while(p0!=NULL){不为空 }

p0=freehead;把空闲区赋值给p0 if (n==1)

return;

{

else

while(p9!=NULL)

p12=p0; 把p0空闲区给p12 p13=p9;把p9空闲区给p13 p0=p0->next; p0指向下一个地址 p0=p0->next;指向下一个地址 n++;n加一

area * p1=freehead;把空闲区首地址赋值给p1

if(p1->next==NULL)

if(p1->len==0){

return NULL; else { } }

p1=p1->next;指向下一个地址

}

}

p9=p9->next; { }

if((p12->len)>(p13->len)){如果p12长度>p13长度 }

p11=new area;//把p13给p11 p11->end=p13->end; p11->len=p13->len; p11->sign=p13->sign; p11->start=p13->start; p11->next=NULL;

swap(p13,p12);交换两个P13，P12 swap(p12,p11);交换两个P12，P11

while(p13!=NULL)//把空闲区按从小到大的顺序排列

p13=p13->next;

void swap(area *p13,area *p14) { }

//最先适应法 void listID(){

int n=0;

area *p9=freehead->next,*p0=freehead,*p11,*p12,*p13; while(p0!=NULL){ }

p0=freehead; if (n==1)

p0=p0->next; n++;

p13->len=p14->len; p13->sign=p14->sign; p13->end=p14->end; p13->start=p14->start;

}

return;

{

else

while(p9!=NULL) }

p12=p0; p13=p9; p0=p0->next; p9=p9->next; { }

if((p12->start)>(p13->start)){ }

p11=new area; p11->end=p13->end; p11->len=p13->len; p11->sign=p13->sign; p11->start=p13->start; p11->next=NULL; swap(p13,p12); swap(p12,p11);

while(p13!=NULL)//把地址按递增顺序排列

p13=p13->next;

void inserfree(area * p3){查看进程之间的前后的区域状态

int flag=0;

area *pf=freehead,*pe=freehead,*pe1; }

if(pf!=NULL){

flag=5;

}//flag=5 有前置空闲块

if(pf->end!=p3->start)//判断是否有前继空闲块 pf=pf->next;

while(pf!=NULL){

else break;

{ { }

else flag=1;//没有置1

while(pe!=NULL)//判断是否有后继空闲块

if(pe->start!=p3->end) pe1=pe; pe=pe->next;

else break; }

if(flag==5)

flag=6; else flag=4;

if(pe!=NULL) {

}//有前置且有后置FLAG=6，只有后置=4 else{

if(flag==1)

flag=2;

}//前后都没有置2

case 5:pf->end=pf->end+p3->len;前置空闲块

pf->len=pf->len+p3->len; break;

pe->len=pe->len+p3->len; break; p8=new area; p8->len=p3->len; p8->end=p3->end; p8->next=freehead;

switch(flag){

case 4:pe->start=pe->start-p3->len;只有后置

case 2: area* p8; p8->start=p3->start; p8->sign=0;

freehead=p8;

}

}

break;

pf->len=pf->len+pe->len+p3->len; if(pe->next==NULL){ } else {

if(pe==freehead){ } else { }

}

pe1->next=pe->next; delete pe; freehead=pe->next; delete pe;

pe1->next=NULL; delete pe;

case 6:pf->end=pe->end;有前置与后置

break;

default :break;

void setfree(){ 释放进程

int chose;

cout<<\选择一个要释放的任务 :\

cin>>chose;

area*p7=usedhead,*p2;

while( p7!=NULL) { //寻找有无此进程 }

if(p7==NULL){

if( p7->sign!=chose ){ p2=p7; p7=p7->next; } else break;

} }

}

cout<<\没有此进程，释放内存失败，返回修改!\return;

inserfree(p7);//将其释放的内存插入空闲块中 usedhead=NULL; if(p7->next==NULL){

p2->next=NULL; delete p7;

if(p7==usedhead &&p7->next==NULL) else{

}//将次进程从已分配表中删除 else { }

cout<<\成功释放所选任务的内存！当前内存状况为：\print(freehead); print(usedhead); cout<

if(p7==usedhead){ } else { }

p2->next=p7->next; delete p7;

usedhead=p7->next; delete p7;

void inserused(area *p3,int num,int need){//将新项插入已分配表中

area*p5;

if(usedhead==NULL){

p5=new area; p5->start=p3->start; p5->len=need;

p5->sign=num;

}

}

p5->end=p3->start+need; p5->next=NULL; usedhead=p5; p5=new area; p5->start=p3->start; p5->len=need;

p5->end=p3->start+need; p5->next=usedhead; usedhead=p5;

}

else{

p5->sign=num;

void correct(area*p3,int need1){修改列表 }

void create(){ 创建地址长度 }

void ask1(area*freehead){//读文件初始化，只用一次

int num,need; area*p3=freehead; ifstream infile(\while(infile>>num){ infile>>need;

if(p3->lenstart=0; p1->end=999; p1->len=999; p1->sign=0; p1->next=NULL; freehead= p1;

p3->len=p3->len-need1; p3->start=p3->start+need1;

} }

}

cout<<\内存不足，分配失败！\ return;

else }

int num,need;

cout<<\cin>>num; cin>>need; while( p3!=NULL){ }

inserused(p3,num,need); correct(p3,need);

cout<<\成功分配申请，当前内存状况为：\print(freehead); print(usedhead); cout<len

else break; }

cout<<\内存不足，分配失败！\return;

p31=p3; p3=p3->next; inserused(p3,num,need); correct(p3,need);

void ask(area*freehead){申请内存 area*p3=freehead,*p31=freehead;

if(p3==NULL){

freehead=delempty();

void print(area*pp){显示页面

}

area*p; p=pp;

cout<<\────────────────────────────\\n\if(p==NULL)

{cout<<\

cout<<\────────────────────────────else

do{

cout<<\ end:\ len:\

\\n\

sign:\

p=p->next;

}while(p!=NULL);

cout<<\───────────────────────────

─\\n\int main()

{ int yourchose,flag1=0,flag2=0; int what;

cout<<\现在初始化内存>>>>>>>\\n\

cout<<\请选择：1.手动初始化 2.读取文件初始化 :\ cin>>flag2; create();

if(flag2==2)ask1(freehead); cout<<\内存初始状态为：\\n\ print(freehead);

print(usedhead); cout<

cout<<\申请内存 2.释放作业的内存\\n\cout<<\查看空闲块链 4.查看已分配块链\\n\cout<<\查看内存状态 0.退出\\n\cout<<\while(flag1==0)

cout<<\菜单选项------------------\\n\

}

{ cout<<\请选择操作---- ：\ cin>>yourchose; switch(yourchose)

{ case 1: cout<<\选择哪种方式？1.最先适应 2.最优适应: \ cin>>what; } }

return 0;

if(what==1)listID(); else listlen(); break;

ask(freehead); case 2:setfree();.释放作业的内存

break; break; break;

print(usedhead); break; break;

case 3:print(freehead);查看空闲块链

case 4:print(usedhead);查看已分配块链\\

case 5: print(freehead);查看内存状态

case 0:flag1=1;退出 default: break;

六、总结与体会

在一开始老师布置这次的实验题目时，自己根本不知道要干什么，因为在上课时对动态分区分配这节内容不是太了解，所以在上机时不知道如何下手，后来，将本章内容反复的看了几遍之后，终于有了自己的思路。在模拟过程中，要充分理解操作系统上关于：

1、动态分区法：动态分区法在作业执行前并不建立分区，分区的建立是在作业的处理过程中进行的。且其大小可随作业或进程对内存的要求而改变分区的建立是在作业的处理过程中进行的。且其大小可随作业或进程对内存的要求而改

变。这就改变了固定分区法中那种即使是小作业也要占据大分区的浪费现象，从而提高了内存的利用率。

2、最先适应法：最先适应算法要求可用表或自由链接按起始地址递增的次序排列。该算法的最大特点是一旦找到大于或等于所要求内存的长度的分区，则搜索结束。 其优点：

（1）、在释放内存分区时，如果有相邻的空白区就进行合并，使其成为一个较大的空白区；

（2）、本算法的实质是尽可能的利用存储器的低地址部分，在高地址部分则保留较多的或较大的空白区，以后如果需要较大的空白区，就容易能够满足。

3、最佳适应法：将可利用空间表中一个大小不小于“请求”且最接近“请求”的空闲块的一部分分配给用户。分配与回收都需要对可利用空间表从头至尾查询一遍。为了避免每次分配都要查询整个链表，通常要求节点从大到小排序，由此只需找到第一个足够大的空闲块即可予以分配。 C++语言具有：

1、封装性：把数据和操作数据的函数组织在一起，不仅使程序结构紧凑，并且提高了类内部的安全性

2、继承性：增加了软件可扩充性和代码重用性。

3、多态性：使设计人员对问题可以进行更好的抽象，有利于代码维护和重用。完成了此次课程设计对C++语言又有了更新的认识，对C++语言更加充分的了解；对C++语言的特点有了更加深刻的体会。

通过这次课程设计，我把学到的操作系统的知识和C++程序的设计结合到一起。虽然在设计过程中也遇到了不少问题，但最后都能得到解决而在这种过程中也使我加深了内存分配概念的理解和掌握基本内存分配的方法。不但加深我对操作系统的理论知识的理解，更增强了我的实际编程能力，丰富了编程经验，锻炼了自己动手解决实际问题的能力。总之经过这次课程设计使我学到了很多在课堂上无法学到知识，增强了编程的实践经验，使把实际问题转换成抽象算法的能力增强，为我以后参加工作奠定了坚实的基础。同时十分感谢指导教师的指点，在老师的细心指点下使我对问题的理解更加的透彻，对编程起了至关重要的作用。并且本次课程设计更加锻炼了我的学习能力和自己收集资料的能力。总之，此次实习让我获益匪浅，希望在以后的学习中有更多的这样的锻炼机会。

七、参考文献

[1] 张尧学.《计算机操作系统教程（第3版）》 清华大学出版社 ,2001

[2] 张尧学.《计算机操作系统教程习题解答与实验指导》清华大学出版社 ,2004 [3] 闵联营 何克右.《C++程序设计教程》 武汉理工大学出版社 ,2005 [4] 汤子嬴 .《计算机操作系统（修订版）》，西安电子科技大学出版社，2001 [5] 滕艳平 .《计算机操作系统》，哈尔滨工业大学出版社，2008

[6] Anany Levitin(美) 潘彦 .译《算法设计与分析》，清华大学出版社，2004 [7] 王红梅 .《数据结构（C++版）》，清华大学出版社，2005

课程设计成绩评定表

学生姓名 专业班级 设计题目 指导教师评语及意见： 指导教师评阅成绩： 指导教师签字： 年 月 日 注：此表装订在课程设计之后。

本文来源：https://www.bwwdw.com/article/c7x5.html