存储器管理报告

上机报告姓名学号专业班级计科普1002课程名称网络操作系统指导教师机房名称（I515）上机日期2012年12月20日上机项目名称上机步骤及内容：1实验目的(1)加深对可变分区的存储管理的理解；(2)提高用C语言编制大型系统程序的能力，特别是掌握C语言编程的难点：指针和指针作为函数参数；(3)掌握用指针实现链表和在链表上的基本操作。2实验要求首先向系统申请内存空间，初始化空闲表，输出命令菜单（分配内存，释放内存，退出程序）；按用户的选择，分别进行内存分配、内存释放或退出程序的操作；若未选择退出程序，则操作完成后输出新的空闲表并回到命令菜单。3实验内容3.1数据结构结点：classNode{public:char*addr;//空闲内存起始地址unsignedintsize;//空闲内存大小Node*next;//下一个空闲内存节点Node*prior;//上一个空闲内存节点Node();//构造函数voidDisplay(inti);//显示这个节点（减去初始地址i，以显示相对地址）};列表：classList{Node*first;//链表中的第一个节点Node*now;//下一个要搜索的空闲内存节点public:List();voidInsert(Node*n,char*a,unsignedints);//在节点i之后插入一个起始地址为a，大小为s的节点voidChangeFirst(char*a,unsignedints);//在first前面插入起始地址为a，大小为s的节点voidDelete(Node*n);//删除节点iNode*FindSize(unsignedinti);//从节点now开始找到下一个大小大于i的节点Node*FindAddr(char*a);//查找内存单元a所在的已分配内存块之前的节点boolInNodes(char*a);//判断内存地址a是否在某个节点所指向的空闲块中char*lmalloc(unsignedints);//从节点n指向的起始地址开始分配i个内存单元voidlfree(char*a,unsignedints);//释放起始地址为a，大小为s的内存块voidTraverse(inti);//显示整个线性表，i是初始地址};3.2框图图一总体框架图开始向系统申请内存空间初始化空闲表，创建一个List类的对象，建立头指针和起始查找指针。显示菜单xm让用户输入要分配的内存大小(s)f输入数据是否越界yn让用户输入要释放的内存的起始地址(a)输入地址越界或未被分配？yyn让用户输入要释放的内存大小(s)退出输入数据是否越界调用List::lmalloc(unsignedints)n调用List::lfree(char*a,unsignedints)显示空闲内存表图二内存分配框图char*lmalloc(unsignedints)遍历空闲内存表，看是否有size=s的节点y把该节点的起始地址加上s，大小减去s。n显示已经没有可分配的内存了，然后退出。该节点大小是否为0返回找到的节点原来的起始地址删除该节点yn图三循环首次适应法4实验任务阅读并调试循环首次适应算法；循环首次适应算法(NextFit)是首次适应算法的变种。在分配内存空间时，不再每次从表头（链首）开始查找，而是从上次找到空闲区的下一个空闲开始查找，直到找到第一个能满足要求的的空voidlfree(char*a,unsignedints)空闲内存表是否为空新建节点，其起始地址为a，大小为s。将头指针和起始查找指针指向它。然后退出yn找到a之前的空闲块节点na在头节点的起始地址之前？yna+s在头节点起始地址之前？若(a+s)==first-addr则令first-addr=a，first-size加s，否则创建一个起始地址为a，大小为s的节点，将头指针和起始查找指针指向它。yn是尾节点？若n-addr+n-size==a则n-size加s，否则创建一个起始地址为a，大小为s的节点作为尾节点。a+s在n-next的起始地址之前？报错并退出ynyn要释放的内存块与前后都相连？要释放的内存块与后面相连？要释放的内存块与前面相连？yn-size加上(n-next-size+s)，删除n-nextyynnn令n-next-addr=a;n-next-size加上s;在n之后创建一个起始地址为a，大小为s的节点。n-size加上s闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。该算法能使内存中的空闲区分布得较均匀。编写首次适应算法、最佳适应算法、最坏适应算法其中的一个。首次适应算法代码：Node*List::FindSizeFirst(unsignedints){if(first==NULL)returnNULL;//如果空闲表为空，则返回空elseif(now-next==now)//如果空闲表只有一个节点，且这个节点的大小不小于s，则返回这个节点，否则返回空{if(now-size=s)returnnow;elsereturnNULL;}else//否则遍历整个表，寻找第一个合适的节点{Node*e=first;Node*aa=first;do{if(aa-size=s)break;elseaa=aa-next;}while(aa!=e-prior);if(aa-size=s)returnaa;elsereturnNULL;}}图四效果图图五效果图结果分析与体会：本次实验主要是让大家了解上面的几个算法，循环首次适应算法、首次适应算法、最佳适应算法、最坏适应算法。了解它们各自的算法，以及知道他们的流程图，知道他们之间的区别，这样我们才能够真正的理解这次实验的主要内容。最佳适应算法（BestFit）从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区。最坏适应分配算法要扫描整个空闲分区或链表，总是挑选一个最大的空闲分区分割给作业使用。该算法要求将所有的空闲分区按其容量从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求。优点：可使剩下的空闲分区不至于太小，产生碎片的几率最小，对中、小作业有利，同时该算法查找效率很高。缺点：会使存储器中缺乏大的空闲分区。最坏适应算法与首次适应算法、循环首次适应算法、最佳适应算法一起，也称为顺序搜索法。上机成绩、评语指导教师签名批改日期