操作系统课程设计报告 内存管理算法模拟.doc

课程设计说明书操作系统课程设计题目: 操作系统 院 系： 专业班级： 学 号： 学生姓名： 指导教师： 2010年 5月 15日 安徽理工大学课程设计（论文）任务书 计算机 院系 软件 教研室学 号学生姓名专业（班级）设计题目内存管理算法模拟设计技术参数了解内存分配方式掌握动态分区分配的一些算法首次适应算法(FIRST FIT)循环首次适应算法(NEXT FIT)最佳适应算法(BEST FIT)快速适应算法(QUICK FIT)用高级语言模拟内存管理算法程序设计要求(1) 对内存管理算法用高级语言进行模拟。(2)对程序的一些部分要有较详细的分析说明。(3)源代码格式要规范。(4)设计合适的测试用例对程序进行测试。(5)总结要深刻，能说明问题。(6)按期提交完整的程序代码、可执行程序和课程设计报告。工作量课程设计任务要求不少于10页的报告，要赋有模块图或流程图。工作计划第一周：查找相关资料，并绘制草图！第二周：确定选用VC为编程语言。第三周：写需求分析报告。第四周：着手进行编程，实现算法，并调试程序。第五周：测试程序并优化功能，最终完成设计报告。参考资料1汤小丹 梁红兵 哲凤屏 汤子瀛 计算机操作系统（第三版）西安电子科技大学出版社，20072杨克昌 王岳斌 计算机导论（第二版）M中国水电出版社，20053徐孝凯 C+语言基础教程（第二版）M 清华大学出版社，20074何钦铭 颜晖 C语言程序设计 M 浙江大学出版社，2004指导教师签字教研室主任签字 年 月 日 指导教师评语：成绩： 指导教师： 年 月 日课程设计（论文）成绩评定表摘要动态分区分配是根据进程的实际需要，动态的为之分配内存空间。在实现可变分区时，将涉及到分区分配中所用的数据结构、分区分配算法与回收操作等问题。为了实现分区分配，系统中必须配置相应的数据结构。数据结构包括空闲分区表和空闲分区链。为把一个新作业装入内存，必须按照一定的分配方法，从空闲分区表或空闲分区链中选出一分区分配给作业。常用的分配算法有五种，首次适应算法(FIRST FIT)、循环首次适应算法(NEXT FIT)、最佳适应算法(BEST FIT)、快速适应算法(QUICK FIT)和最坏适应算法(WORST FIT)。关键词：动态分区分配 内存 分配算法目录1系统分析11.1问题描述11.2算法描述11.3设计目的12 系统设计22.1设计要求22.2设计原理22.3设计流程图33系统实现63.1数据结构63.2函数声明与定义63.3运行结果114总结16参考文献17251系统分析1.1问题描述用高级语言编写一个模拟内存分配算法的程序，设计过程中应选择适当的数据结构。功能有以下几个，利用分区分配算法为作业分配内存空间，可以对已分配的内存空间进行回收，并可以查看分配的情况。1.2算法描述动态分区分配是根据进程的实际需要，动态的为之分配内存空间。在实现可变分区时，将涉及到分区分配中所用的数据结构、分区分配算法与回收操作等问题。为了实现分区分配，系统中必须配置相应的数据结构。数据结构包括空闲分区表和空闲分区链。为把一个新作业装入内存，必须按照一定的分配方法，从空闲分区表或空闲分区链中选出一分区分配给作业。常用的分配算法有五种，首次适应算法(FIRST FIT)、循环首次适应算法(NEXT FIT)、最佳适应算法(BEST FIT)、快速适应算法(QUICK FIT)和最坏适应算法(WORST FIT)。 本程序采用的是首次适应算法，我们以空闲分区链为例来说明采用首次适应算法的分配情况。算法要求空闲分区链以地址递增的次序链接。在分配内存过程中，从链首开始顺序查找，直到找到一个大小能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个满足要求的分区，则此次分区失败，返回。该算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲分区。1.3设计目的设计目的比较明确，主要有以下几个：1.了解动态分区分配；2.了解分区分配中的数据结构；3.掌握分区分配算法；4.掌握分区分配算法实现过程；5.会用高级语音模拟内存分配。2 系统设计2.1设计要求1.对内存管理算法用高级语言进行模拟。2.对程序的一些部分要有较详细的分析说明。3.源代码格式要规范。4.设计合适的测试用例对程序进行测试。5.总结要深刻，能说明问题。6.对程序中个功能模块进行说明。7.按期提交完整的程序代码、可执行程序和课程设计报告。2.2设计原理1.首次适应算法思路：先我们以空闲分区链为例来说明采用首次适应算法的分配情况。算法要求空闲分区链以地址递增的次序链接。在分配内存过程中，从链首开始顺序查找，直到找到一个大小能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个满足要求的分区，则此次分区失败，返回。该算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲分区。程序中定义了两个数据结构，typedef struct kxjied和typedef struct yyjied用来产生空闲分区链freetable和作业分区链usedtable。在分配空间给作业时首先判断是否有空闲区，有的话用首次适应算法分配找到所需大小分区。请求分区大小为jobsize,它与空闲分区大小p-length比较，若p-lengthaddress = 0;空闲分区表长度 freetable-length = 1024;3.首次适应算法： (1)作业发出请求申请空间：作业名jobname,作业大小jobsize。(2)每个空闲分区大小为p-length，并且要求空闲分区链以地址递增次序链接。从头开始检索表，若从链首直至链尾都不能找到一个满足要求的分区，则此次分区失败，返回。(3) 若p-lengthlength- = jobsize，此时分区表首地址p-address +=jobsize。(4) 如果找不到有足够空间的分区可以做扩展，utable x = new uarea。4.：回收作业空间(1) 如果没有作业则返回。(2) 将回收后的空间加入到空闲区。(3) 对分区进行合并。(4) 对作业删除的操作。当程序运行完毕释放内存时，系统根据回收区的首地址，从空闲区表中找到相应的插入点，此时可能出现以下几种情况：(1) 回收区与插入点的前一个分区相邻接。此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改前一分区的大小。(2) 回收区与插入点的后一个分区相邻接。此时也可以将两分区合并，形成新的空闲分区，但用回收区的首地址作为新空闲区的首地址，大小为两者之和。(3) 回收区与插入点的前、后两个分区相邻接。此时将三个分区合并，使用前的表项和首地址，取消后面的，大小为三者之和。(4) 回收区与前后都不邻接。这时应为回收区单建一个新表项，填写回收区的首地址和大小，并根据其首地址适当的插入空闲分区中。2.3设计流程图根据程序结构分析本程序整体流程图如图2-1所示： Main()Init()空闲分区表初始化jobcallback()作业回收jobrequest()作业请求statePrint() allot( )作业分配函数回收作业空间callback()状态显示图2-1程序整体流程图内存分配流程图如图2-2所示：从头开始查表p-lengthjobsieNY从该分区中划出jobsizeNY返回检索完否？返回YN继续p-length-jobsizesize?修改有关数据结构修改有关数据结构图2-1程序整体流程图3系统实现3.1数据结构程序使用的变量：int choice; /选项，用于实现主函数对不同函数的调用int t=1; /循环条件与退出标识long address; /作业区链表地址double length; /作业区链表长度int flag; /标识作业名ftable p = freetable; /为p申请空闲分区表utable x = new uarea; /为x新建分区3.2函数声明与定义本程序中用到的函数：void jobrequest(); /作业请求函数函数代码如下：void jobrequest()int jobname; int jobsize; cout jobname; cout jobsize;if( allot( jobname , jobsize ) = 4 )printf(该进程已成功获得所要求内存空间n);elseprintf(该进程没有成功获得所要求空间n);int allot( jobname , jobsize ) /分配空间给作业函数代码如下：int allot( int jobname , double jobsize )/判断是否有空闲区if( freetable = NULL ) return 1;ftable p = freetable;ftable q = p;/找首次适应算法分配空闲区while( p != NULL & p-length next;/如果找不到有足够空间的分区if( p = NULL )return 2;utable x = new uarea;x-address = p-address; x-length = jobsize; x-flag = jobname; x-next = NULL;/如果该分区大于作业需求，空间大小减去作业大小if( p-length jobsize )p-length -= jobsize; p-address += (long)jobsize;/如果该分区等于作业大小，删除该分区elseif( p = freetable )freetable = NULL;elseq-next = p-next;delete p;/作业加入“作业表”中utable r = usedtable;utable t = r;while( r != NULL & r-address address )t = r;r = r-next;if( usedtable = NULL )usedtable = x;elsex-next = r;t-next = x;return 4;Init(); /空闲分区表初始化函数代码如下：int Init()freetable = new farea; freetable-address = 0; freetable-length = 1024; freetable-next = NULL;return 1;void statePrint() /显示内存状态函数代码如下：void statePrint()ftable p = freetable; utable q = usedtable;int x , y;while( p | q )if( p )x = p-address;elsex = 0 x7fffffff;if( q )y = q-address;elsey = 0 x7fffffff;if( x y )coutaddressendl已分配(上)endl;cout空闲(下)endllengthnext;if( x y ) q = q-next;void jobcallback(); /作业回收函数代码如下：void jobcallback()int jobname; coutjobname;int result = callback( jobname );if( result = 4 )printf(该进程已回收成功n);else if( result = 2 | result = 1 )printf(系统没有进程或该进程不存在n);int callback( int jobname ) /通过作业名回收作业函数代码如下：int callback( int jobname )if( usedtable = NULL )return 1;utable p = usedtable;utable q = p;while( p != NULL & p-flag != jobname )q = p;p = p-next;/如果没有该作业if( p = NULL )return 2;/回收后的空间加入到空闲区ftable r = freetable;ftable t = r;ftable x;while( r != NULL & r-address address )t = r;r = r-next;x = new farea; x-address = p-address; x-length = p-length; x-next = NULL;if( r = freetable )x-next = r;freetable = x;t = freetable;elsex-next = r; t-next = x;/对分区进行合并while( t-next != NULL & t-address + t-length = t-next-address )t-length += t-next-length; r = t-next; t-next = t-next-next;delete r;/对作业删除的操作if( p = usedtable )usedtable = usedtable-next;elseq-next = p-next;delete p;return 4;3.3运行结果运行结果如下所示：如图3-1所示为程序的主界面图3-1程序主界面如图3-2所示为模拟内存的分配图3-2模拟内存的分配如图3-3所示为内存分配成功图3-3内存分配成功如图3-4所示为内存分配状况图3-4内存分配状况如图3-5为创建第二个进程图3-5创建第二个进程如图3-6为此时内存分配状况图3-6此时内存分配情况如图3-7所示为模拟内存的回收图3-7模拟内存的回收如图3-8为回收后内存的状况图3-8回收后内存的状况4总结本次课程设计我做的是内存管理算法模拟，我才用的分区分配算法是首次适应算法，因为这种算法实现起来相对简单一些。算法要求空闲分区链以地址递增的次序链接。在分配内存过程中，从链首开始顺序查找，直到找到一个大小能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个满足要求的分区，则此次分区失败，返回。为了实现分区分配，系统中必须配置相应的数据结构。好的数据结构可以降低算法的时间与空间复杂度 。我以前对数据结构的了解不是太深入，因此遇到了很大的障碍。此次课程设计我体会到深刻理解数据结构的重要性。只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。本次试验遇到的最大的困难是内存的问题。刚开始实现的程序不能进行内存回收，当调用内存回收程序时系统会报错，相当令人头疼。后来没有办法了只有请求高手帮忙，经过一番奋斗之后才知有几处指针出现了问题。其实，我最不喜欢指针了，它指来指去很难把握。今后会对指针问题特别关注的，以为有时候它使用起来确实很方面。参考文献1徐孝凯.C+语言基础教程（第二版）.北京:清华大学出版社,20072徐孝凯.数据结构应用教程（第二版）.北京:清华大学出版社,20073何钦铭 颜晖 .C语言程序设计 M.浙江: 浙江大学出版社，2004 4汤小丹 梁红兵 哲凤屏 汤子瀛编.计算机操作系统（第三版）.西安:西安电子科技大学出版社,20075黄干平 陈洛资编.计算机操作系统.北京:科学出版社,19896李勇 刘恩林.计算机体系结构. 长沙:国防科技大学出版社,19877黄祥喜.计算机操作系统实验教程.广州:清中山大学出版社,19948尤晋元.UNIX操作系统教程.西安: 西安电子科技大学出版社,19959孟庆昌.操作系统教程 .北京:电子工业出版社,200410陈向群 杨芙清.操作系统教程(第二版).北京:北京大学出版社，2006全部代码：#include#includetypedef struct kxjiedlong address; double length; struct kxjied *next;farea , *ftable;typedef struct yyjiedlong address;double length; int flag; struct yyjied *next;uarea , *utable;/作业区链表utable usedtable = NULL;/空闲区链表ftable freetable = NULL;/分配空间给作业int allot( int jobname , double jobsize )/如果没有空闲区if( freetable = NULL )return 1;ftable p = freetable;ftable q = p;/找首次适应算法分配空闲区while( p != NULL & p-length next;/如果找不到有足够空间的分区if( p = NULL )return 2;utable x = new uarea;x-address = p-address; x-length = jobsize; x-flag = jobname; x-next = NULL;/如果该分区大于作业需求，空间大小减去作业大小if( p-length jobsize )p-length -= jobsize; p-address += (long)jobsize;/如果该分区等于作业大小，删除该分区elseif( p = freetable )freetable = NULL;elseq-next = p-next;delete p;/作业加入“作业表”中utable r = usedtable;utable t = r;while( r != NULL & r-address address )t = r;r = r-next;if( usedtable = NULL )usedtable = x;elsex-next = r;t-next = x;return 4;/回收作业空间/jobname: 作业名int callback( int jobname )if( usedtable = NULL )return 1;utable p = usedtable;utable q = p;while( p != NULL & p-flag != jobname )q = p;p = p-next;/如果没有该作业if( p = NULL )return 2;/回收后的空间加入到空闲区ftable r = freetable;ftable t = r;ftable x;while( r != NULL & r-address address )t = r;r = r-next;x = new farea; x-address = p-address; x-length = p-length; x-next = NULL;if( r = freetable )x-next = r;freetable = x;t = freetable;elsex-next = r; t-next = x;/对分区进行合并while( t-next != NULL & t-address + t-length = t-next-address )t-length += t-next-length; r = t-next; t-next = t-next-next;delete r;/对作业删除的操作if( p = usedtable )usedtable = usedtable-next;elseq-next = p-next;delete p;return 4;int Init()freetable = new farea; freetable-address = 0; freetable-length = 1024