青岛农业大学理学与信息科学学院操作系统课程设计报告设计题目仿真实现动态可变分区存储管理模拟系统—最佳适应算法和最先适应算法学生专业班级计算机科学与技术2011级03班学生姓名（学号）明珠（H20110684 ）设计小组其他同学姓名（学号）玉婷（H20110661）宋璇（H20110162）指导教师牟春莲完成时间2014. 06.15实习（设计）地点信息楼2182014年6月16日一、课程设计目的操作系统的理论知识只有通过操作系统的实际操作和编程才能真正地理解和掌握，没有实践操作系统的操作和编程，学习操作系统就是纸上谈兵。
操作系统课程设计是在学习完《操作系统》课程后进行的一次全面、综合实习，是计算机科学与技术专业的重要实践性教学环节。
通过课程设计，达到如下目的：1、巩固和加深对操作系统原理的理解，提高综合运用本课程所学知识的能力。
2、培养学生选用参考书，查阅手册及文献资料的能力；培养独立思考、深入研究、分析问题、解决问题的能力。
3、通过实际操作系统的分析设计、编程调试，掌握系统软件的分析方法和工程设计方法。
4、能够按要求编写课程设计报告书，能正确阐述设计过程和实验结果、正确绘制系统和程序框图。
5、通过课程设计，培养学生严谨的科学态度、严肃认真的工作作风和团队协作精神。
二、设计任务题目描述：仿真实现动态可变分区存储管理模拟系统。
存调度策略可采用最先适应算法、最佳适应法等，并对各种算法进行性能比较。
为了实现分区分配，系统中必须配置相应的数据结构，用来描述空闲区和已分配区的情况，为分配提供依据。
常用的数据结构有两种形式：空闲分区表和空闲分区链。
为把一个新作业装入存，须按照一定的算法，从空闲分区表或空闲分区链中选出一个分区分配给该作业. 设计要求：1．采用指定算法模拟动态分区管理方式的主存分配。
能够处理以下的情形：⑴随机出现的进程i申请jKB存，程序能判断是否能分配，如果能分配，要求输出分配的首地址Faddress，并要求输出存使用情况和空闲情况。
存情况输出的格式为：Faddress该分区的首地址；Eaddress该分区的尾地址Len 分区长度；Process 如果使用，使用的进程号，否则为0。
⑵主存分配函数实现寻找空闲区、空闲区表的修改、已分配区表的修改功能。
成员分工：明珠申请存、查看进程之间的前后的区域状态、释放进程玉婷最先适应算法、将其释放的存插入空闲块中、初始化宋璇最佳适应算法、将新项插入已分配表中、退出明珠宋璇玉婷整个界面的优化、界面设计、总体思路三、分析与设计1．设计思路存储器是计算机的重要组成部分,存储空间是操作系统管理的宝贵资源,虽然其容量在不断扩大,但仍然远远不能满足软件发展的需要。
对存储资源进行有效的管理,不仅关系到存储器的利用率,而且还对操作系统的性能和效率有很大的影响。
操作系统的存储管理的基本功能有：存储分配、地址转换和存储保护、存储共享、存储扩充。
存储分配指为选中的多道运行的作业分配主存空间；地址转换是把逻辑地址空间中的用户程序通过静态重定位或动态重定位转换和映射到分给的物理地址空间中,以便用户程序的执行；存储保护指各道程序只能访问自己的存储区域,而不能互相干扰,以免其他程序受到有意或无意的破坏；存储共享指主存中的某些程序和数据可供不同用户进程共享。
最简单的单道系统中,一旦一个程序能装入主存,它将一直运行直到结束。
如果程序长度超出了主存的实际容量,可以通过覆盖和交换的技术获得解决。
更多的操作系统支持多个用户进程在主存同时执行,能满足多道程序设计需要的最简单的存储管理技术是分区方式,有分固定分区和可变分区。
可变分区的分配（如图（1）所示）算法包括：最先适应、下次适应、最佳适应、最坏适应和快速适应等分配算法。
图（1）动态存分配采用分区方式管理存储器,每道程序总是要求占用主存的一个或几个连续的存储区域,主存中会产生许多碎片。
因此,有时为了接纳一个新的作业而往往要移动已在主存的信息,这不仅不方便,而且开销不小。
现代计算机都有某种虚存硬设备支持,简单也是常用的虚存是请求分页式虚存管理,于是允许把一个进程的页面存放到若干不相邻的主存页框中。
从搜索速度上看，最先适应算法具有最佳性能。
从回收过程来看，最先适应法也是最佳的。
最先适应算法要求可用表或自由按起始地址递增的次序排列。
该算法的最大特点是一旦找到大于或等于所要求存的长度的分区，则搜索结束。
其优点：（1）、在释放存分区时，如果有相邻的空白区就进行合并，使其成为一个较大的空白区；（2）、本算法的实质是尽可能的利用存储器的低地址部分，在高地址部分则保留较多的或较大的空白区，以后如果需要较大的空白区，就容易能够满足。
最佳适应算法：从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。
为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。
该算法保留大的空闲区，但造成许多小的空闲区。
最佳适应算法将可利用空间表中一个大小不小于“请求”且最接近“请求”的空闲块的一部分分配给用户。
分配与回收都需要对可利用空间表从头至尾查询一遍。
为了避免每次分配都要查询整个链表，通常要求节点从大到小排序，由此只需找到第一个足够大的空闲块即可予以分配。
但回收时，必须把回收的空闲块放置在符合大小顺序关系的链表位置。
在分配时容易产生太小而无法利用的存碎片，同时这种做法也保留了那些很大的存块以备响应将来发生的存量较大的用户“请求”，从而使整个链表逐渐趋向于节点大小差别甚远的状态。
这种分配算法适合请求分配存大小围较广的系统，此算法比较费时间。
在进行存分配时，从空闲分区表(或空闲分区链)首开始顺序查找，直到找到第一个能满足其大小要求的空闲分区为止。
如果该空闲分区大于作业的大小，则从该分区中划出一块存空间分配给请求者，将剩余空闲区仍然留在空闲分区表(或空闲分区链)中。
最佳适应算法的特点：按最佳适应算法为作业分配存，就能把既满足作业要求又与作业大小最接近的空闲分区分配给作业。
保留了大的空闲区，但分割后的剩余空闲区很小。
本课程设计就是分析动态分区法，与固定分区法相比，动态分区法在作业执行前并不建立分区，分区的建立是在作业的处理过程中进行的。
且其大小可随作业或进程对存的要求而改变分区的建立是在作业的处理过程中进行的。
且其大小可随作业或进程对存的要求而改变。
这就改变了固定分区法中那种即使是小作业也要占据大分区的浪费现象，从而提高了存的利用率。
2.概要设计动态分区分配是根据进程的实际需要，动态地为之分配存空间。
在实现可变分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配和回收操作这样三个问题。
为了实现分区分配，系统中必须配置相应的数据结构，用来描述空闲区和已分配区的情况，为分配提供依据。
常用的数据结构有两种形式：空闲分区表和空闲分区链。
为把一个新作业装入存，须按照一定的算法，从空闲分区表或空闲分区链中选出一个分区分配给该作业。
目前常用的分配算法有：首次适应算法、循环首次适应算法、最佳适应算法、最坏适应算法和快速适应算法。
在动态分区存储管理方式中，主要操作是分配存和回收.系统模块划分：图（2）各模块划分图主流程图：图（3）主流程图各程序模块的调用层次：图（4）各程序调用图 3．详细设计、 数据结构 结构体定义进程 struct area { int start; int end;int len; int sign;struct area * next;};5个数据成员，分别为：start（分区的首地址）、end、（分区尾地址）len （分区的长度）、sign（标志进程状态）、next（指针用来指向下一个进程）。
存分配表的图类似与图（5）所示：图（5）存分配图最先适应算法流程如下图所示请求SIZE大小的分区：否图（6）最先适应算法流程图最佳适应算法流程如下图所示：图（7）最佳适应算法流程图四、系统实施在模拟过程中，没有充分理解操作系统教程上关于动态分区法、最先适应法、最优适应法的概念，造成了对设计的目的设计不清楚，不能很好地表达出此设计的功能寻找空白区方法的不同：分区分配是对可用表（或自由链）数据结构进行操作，空闲区表可以按空闲区大小的升序（降序）和空闲区首址升序（降序）两种方法进行组织。
才开始并没有理解这两种分配方式对这最佳适应算法和最先适应算法的影响，导致混淆，出现了错误。
对题目理解有误，对模块之间的关系设计不是很清晰。
图（8）初始化图图(9) 申请存图图（10）查看已分配区图图（11）查看空闲区图图（12）释放存图图（13）查看存状态图最佳算法和最先算法的比较：图（13）两算法的对比图五、程序清单#include<iostream>using namespace std;#include<fstream>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(){area * p1=freehead;把空闲区首地址赋值给p1if(p1->len==0){if(p1->next==NULL)return NULL;else {p1=p1->next;指向下一个地址}}}//最优适应法void listlen(){int n=0; 初始为零area *p9=freehead->next,*p0=freehead,*p11,*p12,*p13;while(p0!=NULL){不为空p0=p0->next;指向下一个地址n++;n加一}p0=freehead;把空闲区赋值给p0if (n==1)return;elsewhile(p9!=NULL) {p12=p0; 把p0空闲区给p12p13=p9;把p9空闲区给p13p0=p0->next; p0指向下一个地址p9=p9->next;while(p13!=NULL)//把空闲区按从小到大的顺序排列{if((p12->len)>(p13->len)){如果p12长度>p13长度p11=new area;//把p13给p11p11->end=p13->end;p11->len=p13->len;p11->sign=p13->sign;p11->start=p13->start;p11->next=NULL;swap(p13,p12);交换两个P13，P12swap(p12,p11);交换两个P12，P11}p13=p13->next;}}}void swap(area *p13,area *p14){p13->len=p14->len;p13->sign=p14->sign;p13->end=p14->end;p13->start=p14->start;}//最先适应法void listID(){int n=0;area *p9=freehead->next,*p0=freehead,*p11,*p12,*p13;while(p0!=NULL){p0=p0->next;n++;}p0=freehead;if (n==1)return;elsewhile(p9!=NULL) {p12=p0;p13=p9;p0=p0->next;p9=p9->next;while(p13!=NULL)//把地址按递增顺序排列{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);}p13=p13->next;}}}void inserfree(area * p3){查看进程之间的前后的区域状态int flag=0;area *pf=freehead,*pe=freehead,*pe1;while(pf!=NULL){if(pf->end!=p3->start)//判断是否有前继空闲块pf=pf->next;else break;}if(pf!=NULL){flag=5;}//flag=5 有前置空闲块else flag=1;//没有置1while(pe!=NULL)//判断是否有后继空闲块{if(pe->start!=p3->end){pe1=pe;pe=pe->next;}else break;}if(pe!=NULL) {if(flag==5)flag=6;else flag=4;}//有前置且有后置FLAG=6，只有后置=4else{if(flag==1)flag=2;}//前后都没有置2switch(flag){case 5:pf->end=pf->end+p3->len;前置空闲块pf->len=pf->len+p3->len;break;case 4:pe->start=pe->start-p3->len;只有后置pe->len=pe->len+p3->len;break;case 2: area* p8;p8=new area;p8->start=p3->start;p8->len=p3->len;p8->sign=0;p8->end=p3->end;p8->next=freehead;freehead=p8;break;case 6:pf->end=pe->end;有前置与后置pf->len=pf->len+pe->len+p3->len;if(pe->next==NULL){pe1->next=NULL;delete pe;}else {if(pe==freehead){freehead=pe->next;delete pe;}else {pe1->next=pe->next;delete pe;}}break;default :break;}}void setfree(){ 释放进程int chose;cout<<"选择一个要释放的任务:";cin>>chose;area*p7=usedhead,*p2;while( p7!=NULL) { //寻找有无此进程if( p7->sign!=chose ){p2=p7;p7=p7->next;}else break;}if(p7==NULL){cout<<"没有此进程，释放存失败，返回修改!"<<endl;return;}inserfree(p7);//将其释放的存插入空闲块中if(p7==usedhead &&p7->next==NULL)usedhead=NULL;else{if(p7->next==NULL){p2->next=NULL;delete p7;}//将次进程从已分配表中删除else {if(p7==usedhead){usedhead=p7->next;delete p7;}else {p2->next=p7->next;delete p7;}}}cout<<"成功释放所选任务的存！当前存状况为："<<endl;print(freehead);print(usedhead);cout<<endl;}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; }else{p5=new area;p5->start=p3->start;p5->len=need;p5->sign=num;p5->end=p3->start+need;p5->next=usedhead;usedhead=p5;}}void correct(area*p3,int need1){修改列表p3->len=p3->len-need1;p3->start=p3->start+need1;}void create(){ 创建地址长度area* p1;p1=new area;p1->start=0;p1->end=999;p1->len=999;p1->sign=0;p1->next=NULL;freehead= p1;}void ask1(area*freehead){//读文件初始化，只用一次int num,need;area*p3=freehead;ifstream infile("123.TXT");while(infile>>num){infile>>need;if(p3->len<need){cout<<"存不足，分配失败！"<<endl;return;}elseinserused(p3,num,need);correct(p3,need);}}void ask(area*freehead){申请存int num,need;area*p3=freehead,*p31=freehead;cout<<"input num and need! "<<endl;cin>>num;cin>>need;while( p3!=NULL){if(p3->len<need){p31=p3;p3=p3->next;}else break;}if(p3==NULL){cout<<"存不足，分配失败！"<<endl;return;}inserused(p3,num,need);correct(p3,need);freehead=delempty();cout<<"成功分配申请，当前存状况为："<<endl;print(freehead);print(usedhead);cout<<endl;}void print(area*pp){显示页面area*p;p=pp;cout<<"────────────────────────────\n";if(p==NULL){cout<<"empty list!"<<endl;cout<<"────────────────────────────\n";return;}elsedo{cout<<"start:"<<p->start<<" end:"<<p->end<<" len:"<<p->len<<" sign:"<<p->sign<<endl;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<<endl;cout<<"-------------菜单选项------------------\n";cout<<"1.申请存 2.释放作业的存\n";cout<<"3.查看空闲块链 4.查看已分配块链\n";cout<<"5.查看存状态0.退出\n";cout<<"---------------------------------------"<<endl;; while(flag1==0){ cout<<"-----请选择操作---- ：";cin>>yourchose;switch(yourchose){ case 1: cout<<"选择哪种方式？1.最先适应2.最优适应: ";cin>>what;if(what==1)listID();else listlen();ask(freehead);break;case 2:setfree();.释放作业的存break;case 3:print(freehead);查看空闲块链break;case 4:print(usedhead);查看已分配块链\break;case 5: print(freehead);查看存状态print(usedhead);break;case 0:flag1=1;退出break;default: break;}}return 0;}六、总结与体会在一开始老师布置这次的实验题目时，自己根本不知道要干什么，因为在上课时对动态分区分配这节容不是太了解，所以在上机时不知道如何下手，后来，将本章容反复的看了几遍之后，终于有了自己的思路。