《操作系统》课程设计动态分区管理的主存分配模拟设计最优适应法、最差适应法

1、武汉理工大学操作系统课程设计任务书附件1：学 号： 0120910340719课 程 设 计题 目动态分区管理的主存分配模拟设计-最优适应法、最差适应法学 院计算机科学与技术学院 专 业计算机科学与技术专业班 级0907姓 名xxxx指导教师罗 芳2012年1月11日课程设计任务书学生姓名： xxxx 专业班级： 计科0907 指导教师： 罗 芳 工作单位： 计算机科学与技术学院 题 目: 动态分区管理的主存分配模拟设计-最优适应法、最差适应法初始条件：1预备内容：阅读操作系统的内存管理章节内容，理解动态分区的思想，并体会各分配算法的具体实施方法。2实践准备：掌握一种计算机高级语言的使用。要求

2、完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1采用指定算法模拟动态分区管理方式的主存分配。能够处理以下的情形： 随机出现的进程i申请jkb内存，程序能判断是否能分配，如果能分配，要求输出分配的首地址faddress，并要求输出内存使用情况和空闲情况。内存情况输出的格式为：faddress该分区的首地址；eaddress该分区的尾地址len 分区长度；process 如果使用，使用的进程号，否则为0 主存分配函数实现寻找空闲区、空闲区表的修改、已分配区表的修改功能；2设计报告内容应说明： 课程设计目的与功能； 需求分析，数据结构或模块说明(功能与框图)； 源程序

3、的主要部分； 运行结果与运行情况分析； 自我评价与总结：i）你认为你完成的设计哪些地方做得比较好或比较出色；ii）什么地方做得不太好，以后如何改正；iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；iv）完成本题是否有其他的其他方法（如果有，简要说明该方法）；v）对实验题的评价和改进意见，请你推荐设计题目。时间安排：设计安排一周：周1、周2：完成程序分析及设计。周2、周3：完成程序调试及测试。周4、周5：验收、撰写课程设计报告。（注意事项：严禁抄袭，一旦发现，抄与被抄的一律按0分记）指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日一、题目动态分区管理的主存分配

4、模拟设计-最优适应法、最差适应法二、主要任务1采用指定算法模拟动态分区管理方式的主存分配。能够处理以下的情形： 随机出现的进程i申请jkb内存，程序能判断是否能分配，如果能分配，要求输出分配的首地址faddress，并要求输出内存使用情况和空闲情况。内存情况输出的格式为：faddress该分区的首地址；eaddress该分区的尾地址len 分区长度；process 如果使用，使用的进程号，否则为0 主存分配函数实现寻找空闲区、空闲区表的修改、已分配区表的修改功能；2设计报告内容应说明： 课程设计目的与功能； 需求分析，数据结构或模块说明(功能与框图)； 源程序的主要部分； 运行结果与运行情况分

5、析； 自我评价与总结：i）你认为你完成的设计哪些地方做得比较好或比较出色；ii）什么地方做得不太好，以后如何改正；iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；iv）完成本题是否有其他的其他方法（如果有，简要说明该方法）；v）对实验题的评价和改进意见，请你推荐设计题目。三、原理1.最佳适应算法:最佳适应算法要求从小到大的次序组成空闲区可用表或自由链。当用户作业或进程申请一个空闲区时，存储管理程序从表头开始查找，当找到第一个满足要求的空闲区时，停止查找。如果该空闲区大于请求表中的请求长度，则与最先适应法时相同，将减去请求长度后的剩余空闲区部分留在可用表中。2.最坏适应算法：

6、最坏适应算法要求空闲区按其大小递减的顺序组成空闲区可用表或自由链。当用户作业或进程申请一个空闲区时，先检查空闲区可用边或自由链的第一个空闲可用区的大小是否大于或等于所要求的内存长度，若可用表或自由链的第一个项长度小于所要求的，则分配失败，否则从空闲区可用表或自由链中分配相应的存储空间给用户，然后修改和调整空闲区可用表或自由链。四、实验需求分析存储器是计算机系统的重要资源之一,存储空间是操作系统管理的宝贵资源,虽然其容量在不断扩大,但仍然远远不能满足软件发展的需要。对存储资源进行有效的管理,不仅关系到存储器的利用率,而且还对操作系统的性能和效率有很大的影响。分区管理是把内存划分为若干大小不等的区

7、域，除操作系统占用一个区域外，其余由多道环境下的各并发进程共享。动态分区法在作业执行前并不建立分区，分区的建立是在作业的处理过程中进行的，且大小可随作业或进程对内存的要求而改变。采用动态分区法，在系统初启时，除了操作系统中常驻的内存部分外，只有一个空闲区。随后，分配的程序将该区依次划给调度选中的作业或进程。下图给出了fifo调度方式时内存的初始分配情况：进程a 8k进程b16k进程c64k进程d124k. os进程a进程b进程c进程d os进程a进程b进程 os进程a进程b os进程a五、实验功能设计1.数据结构说明本实验用到了结构体和类两种数据结构：结构体定义如下：struct tableu

8、nionint head;int cnt;int end;table* next; ;其中定义了四个数据成员，分别为：head（分区的首地址）、cnt（结构体指针的计数）、end（分区的尾地址）、table*next（指向下一节点的指针）。由此可以计算出分区的长度为：end-head。内存分配如下： 首地址尾地址分区大小 0 50 50 150 200 50 300 400 100 410 480 70类定义如下：class areaalloc public:int initmemblock();areaalloc(); areaalloc(); public:table* findleast

9、(int flag,int i);void change(int i,table*p);void sort(int flag);int fit(int flag, int memsize);table* m_head;2.函数模块说明本程序主要由类areaalloc的成员函数实现，其成员函数的说明如下：构造函数areaalloc:areaalloc() 析构函数areaalloc:areaalloc() 成员函数initmemblock（）将给定的结构体数组链入链表，其基本定义如下：int areaalloc:initmemblock()table mt = 数组定义部分 ;m_head =

10、new table;memset(m_head,0,sizeof(table);table*head = m_head;for(int i = 0 ; i head = mti.head;p-end = mti.end;head-next = p;head = p;m_head-cnt +; head-next = null; return 1;成员函数fit(int flag,int memsize) ，功能：根据flag的值决定是采用最优还是最差分区的分配方法给所要求的进程分配内存，当flag=0时采用最优分配，当flag=1时采用最差分配。其函数的定义如下：int areaalloc:f

11、it(int flag,int memsize) /flag=0 最优分配 if(flag = 0)/最优 sort(0); else /最差 sort(1); int len = m_head-cnt;table* p = m_head-next; for(int i = 0 ; i end - p-head) = memsize) if(p-end - p-head) = memsize) /将该内存块从可用内存块中移除table* beforp = m_head;while(beforp) if(beforp-next = p) table* delp = p;int ret = p-h

12、ead;beforp-next = p-next;delete delp;m_head-cnt -;return ret; beforp = beforp-next; else /截取所需大小 调整可用表 int ret = p-head;p-head = p-head+memsize;return ret; p = p-next; return -1; 成员函数findleast(int flag, int i)，根据标志位flag的值来决定是找出第i位之后的最大值还是最小值，当flag=0时，找出最大值，当flag=1时，找出最小值。其定义如下：table* areaalloc:findl

13、east(int flag, int i)table*pleast = m_head;for(int j = 0; j next;table *p = pleast-next;while(p)if(flag = 0)/从小到大if(p-end - p-head end - pleast-head)pleast = p;else /从大到小if(p-end - p-head pleast-end - pleast-head)pleast = p;p = p-next;return pleast;成员函数change(int i, table *p)，交换函数，交换第i个数和第p个，其定义如下：v

14、oid areaalloc:change(int i, table *p)/交换第i个数和第p个table*pi = m_head-next;for(int j = 0; j next;if(pi = p)return;table tmp;tmp.head = p-head;tmp.end = p-end;p-head = pi-head;p-end = pi-end;pi-head = tmp.head;pi-end = tmp.end;成员函数sort(int flag)根据标志位flag决定是采用哪种方法排序，当flag=0时采用从大到小的顺序排序，当flag=1时采用从小到大的顺序排序

15、，其定义如下：void areaalloc:sort(int flag)/flag = 0根据关键字 从小到大排序 1 从大到小 int len = m_head-cnt;for(int i = 1; i cnt;table *p = ma.m_head-next;coutsetw(8)起始地址setw(8) 结束地址setw(12)分区大 小endl;for(int i = 0 ; i cnt; i+)coutsetw(8)head setw(8)endsetw(12)end - p-headnext;3.程序的流程图最优适应法和最差适应法的流程图一样，如下： 请求size大小的分区从空闲区

16、表第一表目顺序查找表目查完？ 是无法分配 否该空闲区的长度size？取下一表项 否 是该空闲区的长度=size？从该空闲表中截取所需大小，修改调整可用表 否 是从可用表中移去该表目，调整可用表 返回分配起始地址六、开发平台本程序开发平台为microsoft visual c+ 6.0七、源代码#include #include using namespace std; #includestdlib.htypedef struct area int start; int length; int state; struct area *next;area,*parea;area *head;con

17、st int max=255;void printmemorystate(area *);void bestfit(area *);void worstfit(area *);void init();void main() int choice; /开始循环 while(1) system(cls);init();printmemorystate(head); printf(1.最优适应法;2.最差适应法;0.退出程序n); scanf(%d,&choice);/输入你所要的选项。为choice 的值 switch(choice) case 0: printf(the system is sh

18、utdown. n); exit(0);case 1: bestfit(head); printmemorystate(head);/最优适应法break;case 2: worstfit(head);printmemorystate(head);/最差适应法 break; default: printf(please input a right number!n); break; system(pause); void init() area *work; area *p;area *p1;area *p2;area *p3;area *p4;area *p5; /int start;del

19、ete head; head=(area *)malloc(sizeof(area);/分配头指针/extern void *malloc(unsigned int num_bytes)功能：分配长度为num_bytes字节的内存块 work=(area *)malloc(sizeof(area); head-start=0; head-length=0; head-state=0; head-next=null; /装入系统 printf(.正在载入系统中.n); work-start=0;work-length=1;work-next=null;work-state=0; head-nex

20、t=work; p=(area *)malloc(sizeof(area); p-start=1;p-length=32;/p-next=null;p-state=0; work-next=p;p1=(area *)malloc(sizeof(area); p1-start=33;p1-length=16;/p1-next=null;p1-state=0; p-next=p1;p2=(area *)malloc(sizeof(area); p2-start=49;p2-length=8;/p2-next=null;p2-state=0; p1-next=p2;p3=(area *)malloc

21、(sizeof(area); p3-start=57;p3-length=4;/p3-next=null;p3-state=0; p2-next=p3; p4=(area *)malloc(sizeof(area); p4-start=61;p4-length=64;/p4-next=null;p4-state=0; p3-next=p4; p5=(area *)malloc(sizeof(area); p5-start=125;p5-length=max-125;p5-next=null;p5-state=0; p4-next=p5;void printmemorystate(area *h

22、ead) int state=-1; area *temp=(area *)malloc(sizeof(area); temp=head-next; printf(t起始地址t内存长度t内存状态n);do printf(t%8dt%8dt%8dn,temp-start,temp-length,temp-state); temp=temp-next; while(temp!=null); return ;void worstfit(area *head)/装入作业,最差适应法 int lengthtemp;int a3; area *last=null; area *newfree=null;i

23、nt i;int name=0;cout请分别输入需要分配内存的3个作业内存长度:endl;for(i=1;i=3;i+)cout进程iai-1;for(i=0;inext;task=null;while(last!=null)if(last-state0)last=last-next;elseif(task=null)task=last;if(last-lengthtask-length)task=last;last=last-next;/task指向length最大的那块if(aitask-length)coutai 作业过长，无法装入 length=ai)task-state=i+1;/

24、等于的话直接装入if(task-lengthai)lengthtemp=task-length;task-length=ai;task-state=i+1;newfree=(area *)malloc(sizeof(area);newfree-next=task-next;newfree-start=task-start+task-length;newfree-length=lengthtemp-task-length;newfree-state=0;task-next=newfree;/成功插入newfree节点void bestfit(area *head)/装入作业,最优适应法 int

25、flag=0; int lengthtemp;int a3; area *last=null; area *newfree=null;area *h=null;int i;cout请分别输入需要分配内存的3个作业内存长度:endl;for( i=1;i=3;i+)cout进程iai-1;for(i=0;inext;p=head-next;h=head-next;while(h!=null)if(h-state0)h=h-next;elsebn=h-length;h=h-next;n+;sum=b0;for(int j=1;jn;j+)if(sumsum)coutai 作业过长，无法装入 sta

26、te0)last=last-next;elseif(ailast-length)last=last-next;else if(ai=last-length)task=last;task-state=i;break;else if(ailength)if(task=null)task=last;else if(task-lengthlast-length)task=last;last=last-next;if(task-lengthai)lengthtemp=task-length; task-length=ai;task-state=i+1;newfree=(area *)malloc(siz

27、eof(area);newfree-next=task-next;newfree-start=task-start+task-length;newfree-length=lengthtemp-task-length;newfree-state=0;task-next=newfree;/成功插入newfree节点八、运行结果与运行情况分析编写源程序，编译无误之后运行得到如下界面： 首先采用最优适应方法，输入1之后，要求分别输入需要分配内存的3个作业的内存长度得到如下界面：回车后得到的结果如下：由于多次随机分配之后所剩的空闲区的长度越来越小，经过几次最优适应法之后分配之后，空闲区的长度可能不满足分

28、配的要求，得到如下界面： 之后采用最差适应法进行分配，得到如下界面：同理，由于所剩的空闲区的长度越来越小，可能出现空闲区的长度满足所要求的长度，得到如下界面：九、自我评价与总结1.你认为你完成的设计哪些地方做得比较好或比较出色. 实验能够很好的和操作系统的理论结合起来，验证最优适应法、最坏适应法的流程和优缺点，程序中用链表分别将空闲区和进程连接起来，这样更加方便分配内存后把所剩的内存碎片连接起来，同时用指针很方便的进行对进程分配内存块。另外所有进程都是随机产生的，这样更具有实际意义。2.什么地方做得不太好，以后如何改正在本实验中所有空闲区都是人为设定的，并且本程序没有实现释放进程和回收空闲区的

29、功能，如果不断的进行分配所剩的空闲区将会是很多的碎片，这明显不符合实际。3.从本设计得到的收获（在编写，调试，执行过程中的经验 和教训） 在编写程序的过程中，我认识到寻找空闲空间是关键，实验中采用链表的数据结构对空闲区进行操作。在模拟过程中，要充分理解操作系统教程上关于动态分区法、最优适应法、最坏适应法的概念，只有充分理解了它们的工作流程，才能编写出模拟效果更逼真的程序。 空闲区的排序有多种方法，本实验空闲区表的排序有两种方法： （1）.按空闲区大小升序（最优） （2）.按空闲区大小降序（最差）通过这次课程设计，我把学到的操作系统的知识和vc+程序的设计灵活的结合到一起。虽然在设计过程中也遇到

30、了不少问题，但最后都能得到解决，而在这种过程中我也加深了对内存分配概念的理解和掌握基本内存分配的方法。4.完成本题是否有其他方法（如果有，简要说明该方法） 暂时没想到比这更好的方法5.对实验题的评价和改进意见，请你推荐设计题目 本实验能够较好的培养我们对于内存分配管理概念的理解和掌握，并且深入分析分区首地址、分区尾地址、分区长度之间的关系，理解最优适应法和最坏适应法的优缺点。但这还不够，本题目没有对最先适应法进行动态分配，并且没有对进程的释放和回收的要求，如果加上这些要求，实验将会更加完美。十、参考文献计算机操作系统教程（第3版） 清华大学出版社 张尧学 主编计算机操作系统教程习题解答与实验指

31、导 清华大学出版社 张尧学 主编c+程序设计教程 武汉理工大学出版社 闵联营 何克右 主编本科生课程设计成绩评定表班级：计科0907姓名：xxxx学号：xxxxxxxxxxxx序号评分项目满分实得分1学习态度认真、遵守纪律102设计分析合理性103设计方案正确性、可行性、创造性204设计结果正确性405设计报告的规范性106设计验收10总得分/等级评语：注：最终成绩以五级分制记。优（90-100分）、良（80-89分）、中（70-79分）、及格（60-69分）、60分以下为不及格指导教师签名：2012年月 日ut2apodfxxc02gybkskcww97mrqqwhoj5tl15zt6jip

32、yytycummtarp3v1n5luizi3xh3bhwyreko8d9g7nmzqowpjetldrw08gvs8dsdqqygc3ce7moo2tlf0jf1gk74iuxybmtivr97ckrfvqult5fn2t6mpjr6rbzvpsortzvij5nb5ndvvsr4iwr1twlfkglspzuhrjq3cmzu98euouijdlszqpmvrw9zkupxf8wfug9l2g9277g2rtipa1ypczeuqxpkbhtvdcooqozxuz3vjrzmocijym62zchmeootyes8ebmm932tbz2yo09rtszeys8zrd2yktj8l6jeaz

33、vajnfbtrylvsm6ofbftoxvrffn7owiygjlamkunxjybz5rrb7r4vsur9zpfzfmfsjhcfca37lnw2vvlrkn7r8psz1bn6oric5hu5z6hcxayqynpog8duybawqsl20csg06dh2sm8hltgpkicskrgopdpuhbj1lmpk7lydvc6nnmwl3fwhzftfvyaary7lhssxj10v3ph3y19bxyr77ib7cpzsu2tijqe3hkqkkau9kskcphkxuikvvyjzpg2yijrkqfbggovyqkuxnwi9omnjtt6qilzxtyrf7d20fbmabcfiixrqkusvnxbppfuxyq1fjskfsubkgs2duvqc9sz4jkbgn4qqv66pyoarjurnfj3txyfclzieeptwfjthpheipdfnqnr2hjqkv2dzwtmpdjqkbcxmovdsjqctjagjmdlskpgad2s0h0vmzgaht36gyuez7umank1ndreubeqdgrx0venqgnsyib2ilq3siqrnl4m56t7z8y8da5k0kupn5nzg4jvjdtffhyt82aogq