操作系统内存管理模拟系统的实现.doc

摘 要操作系统的内存管理是指系统软件对其他应用程序使用内存时所作的管理，是一种统筹关系。本设计采用活动分区方案，但不采用紧凑算法。假设系统内存容量为100KB。能处理内存回收的时候上下邻合并的问题；对随机出现的进程i申请jKB内存，程序能判断是否能分配；释放随机的首地址为Handle的内存块；同时输出内存使用情况和空闲情况。关键字：内存资源；分配；存储管理；回收目 录1 概述61.1设计任务61.2 设计思想61.3 基础知识62 各模块伪码算法72.1主程序82.2 创建进程模块92.3 进程信息模块102.4 进程申请模块112.5 分区创建模块122.6 内存分配模块132.7 低级调度模块153函数关系调用图164测试结果174.1 主界面调试结果174.2 创建进程调试结果184.3 进程信息调试结果184.4 进程申请调试结果194.5 分区创建调试结果204.6 内存分配调试结果204.7 内存回收调试结果214.8 打印分区调试结果224.9 低级调度调试结果235源程序246总结44参考文献45致 谢46摘 要操作系统的内存管理是指系统软件对其他应用程序使用内存时所作的管理，是一种统筹关系。本设计采用活动分区方案，但不采用紧凑算法。假设系统内存容量为100KB。能处理内存回收的时候上下邻合并的问题；对随机出现的进程i申请jKB内存，程序能判断是否能分配；释放随机的首地址为Handle的内存块；同时输出内存使用情况和空闲情况。关键字：内存资源；分配；存储管理；回收1 概述1.1设计任务应用内存管理实现内存管理的分配和回收。能处理内存回收的时候上下邻合并的问题以及输出内存使用情况和空闲情况。采用活动分区方案，但不采用紧凑算法。假设系统内存容量为100KB。要能处理内存回收的时候上下邻合并的问题；对随机出现的进程i申请jKB内存，程序能判断是否能分配；释放随机的首地址为Handle的内存块；要求输出内存使用情况和空闲情况。根据给定的动态分区分配算法流程图，用熟悉的计算机编程语言编写一程序，该程序实现内存的合理分配后回收。1.2 设计思想通过本次课程设计，学习如何进行内存的分区管理，强化了对首次适应分配算法和分区回收算法的理解。此课设需要随机产生进程或者由用户输入进程相应信息，实现动态内存管理：设计主界面以灵活选择某算法。主要实现的算法有：首次适应算法、最佳适应算法、最坏适应算法和循环适应算法。实现的主要功能有：创建进程，查看进程信息，进程申请，分区创建，内存分配，内存回收，打印分区，低级调度等。分析设计要求，根据老师给出的要求，我们需创建进程和分区，然后申请进程，然后再进行内存的分配与回收。1.3 基础知识内存是现代计算机系统运转的核心.内存由一大片连续的字或字节组 成,每个字或字节都有自己的地址,CPU根据程序计数器的值从内存中取出指令,而取出的指令可能引发额外的操作,例如读取或存储特定的内存地址.举个例子,一个典型的指令执行周期如下:首先从内存中读取一条指令,然后解码这条指令,解码时可能会从内存中读取这条指令(例如间接地址运算)的操作数(operand),当这条指令完成对操作数的运算后,运算结果可能被存储到内存中.2 各模块伪码算法最先适应算法循环适应算法最佳适应算法最坏适应算法内存管理创建进程进程信息内存分配分区创建进程申请内存回收打印分区低级调度前后两分区都不是空闲分区前未空闲后空闲前空闲后未空闲前后两分区都是空闲分区图2.1 总体结构流程图图2.1为总体结构流程图2.1主程序主函数既是程序的入口，又是程序的出口，通常我们还可以指定一个exit code再退出，以表明程序最后的结果是什么样的。由于主函数肩负着入口和出口的重任，所以最好不要把太多的细节方面的逻辑直接放在主函数内，这样不利于维护和扩展。主函数应该尽量简洁，具体的实现细节应该封装到被调用的子函数里面去。此主函数中包括很多功能模块，其中各功能模块用菜单方式选择，为我们提供了九个功能选项。如图2.1所示显示一系列功能模块输入数字，判断数字是否为19根据数字的值调用各功能模块函数开始结束N Y 图2.1 主程序流程图2.2 创建进程模块进程的创建也就有两种方式：一是由操作系统创建，二是由父进程创建。在系统启动时，操作系统会创建一些进程，他们承担着管理和分配系统资源的任务，这些进程通常被称为系统进程。系统允许一个进程创建新进程，新进程即为子进程，子进程还可以创建新的子进程，形成进程树结构。此创建进程模块可以输入自己想创建的进程数进而实现进程创建。如图2.2所示开始输入创建进程的个数初始化进程申请队列初始化进程分配队列创建进程结束 图2.2 创建进程流程图coutProcessNum;tapplyIndex=new inProcessNum;初始化进程申请队列 assignPointer=new intProcessNum;/初始化进程分配队列 maxApplyNum=ProcessNum; pro=randomCreatPro(ProcessNum);创建成功2.3 进程信息模块进程又称任务，是一个动态的使用系统资源、处于活动状态的应用程序。进程的管理由进程控制块PCB、进程调度、中断管理、任务队列等组成，它是linux文件系统、存储管理、设备管理和驱动程序的基础。进程控制块PCB中包含了进程的所有信息，主要包括进程PID、进程所占有的内存区域、文件描述符和进程环境等信息。如图2.3所示开始进程是否创建输出该进程信息结束NY 图2.3 进程信息流程图Ifpro=NULLreturn ERRORForint i=0;istatus=0coutstatus=1/进程状态coutstatus=-1else ifpro-status=2coutstatus=-2cout未就绪coutnextcout.fill( )Whilep!=NULLcout.width(3)cout分区的大小p=p-next; return 创建成功end2.6 内存分配模块常见内存分配算法如下：首次适应算法，从空闲分区链首开始查找。循环适应算法，从上次找到的空闲分区开始查找。最佳适应算法，是最小的空闲分区分配给作业。最差适应算法，最差适应算法中，该算法按大小递减的顺序形成空闲区链，内存分配，第一次分配，从头结点开始，其他重上次分配的节点开始，然后从分配资源的进程开始分配，若分配的进程进已分配进程队列，则申请进程的偏移指针回首址，修改分配数。如图2.6所示伪代码Node p=head-next返回最大空闲结点计数 countif(p=NULL) 则cout 空闲链表不存在否则 doif(p-status=0) 则Cout+if(count=1) 则 p=q否则 if(p-subarea.subareaSizeq-subarea.subareaSize)YYNN该分区空闲吗？分区长=SIZE?度=SIZE?将状态位置为正在使用返回分区号取下一表项开始选择所要的适应算法要求按SIZE大小分区取分区说明表第一项表结束吗？无法分配NY图2.6内存分配模块流程图2.7 低级调度模块低级调度又称为进程调度、短程调度，它决定就绪队列中的哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作。在批处理，分时，实时三类系统中，进程调度必须被配置，因而是一种最基本的调度。与中级调度交换，高级调度作业调度相对应。低级调度的功能：保存处理机的现场信息。按某种算法选取进程。把处理器分配给进程。如图2.7所示开始是否存在已分配好资源的进程选择一个就绪进程进入CPUCPU正在调度进程获得处理机,开始执行结束NY图2.7低级调度模块流程图Displayprocess()Createlinklist()Creatprocess()Assignmemory()Display()Callbackmemory()Main()3函数关系调用图如图3.1所示，为函数关系调用图，主函数main（）调用其他九个模块，Cowattemper()调用Displyprocess()，Creatprocess()调用Randomcreatpro()总体结构流程如下图所示。 Cowattemper()Applyforprocess()Menu()Randomcrearpro()4测试结果所谓程序调试是指对程序的查错与排错。在编写完一个源程序之后，不要立即进行编译，而应对程序进行全面的人工检查一遍，检查无误后可以开始进行程序调试。由编译系统进行检查、发现错误，根据编译系统提示的错误类型和警告及出现的位置，我们可以定位到错误地点进行修改，然后再编译，如此反复进行，直至不再出现错误位置，最后才进行程序的连接于运行调试完以后，下一步就是对程序进行测试，运行程序，向程序中输入数据，根据输出结果是否正确（是否符合自己的想法）来判断程序是否正确，如果不正确或不符合自己的目的，就需要对程序进行修改。然后再调试，再测试，直至结果无误或符合要求后，测试才算结束，此时，程序才算是满足题目要求的正确程序。4.1 主界面调试结果主界面调试结果是运行程序后出现的主界面，它包括了内存管理中的一系列应用，它主要包括，创建进程，进程信息，进程申请，分区创建，内存分配，内存回收，打印分区，低级调度等应用，我们可以选择1-9的数字进行相应的操作，如果写入除1-9以外的数字，程序运行将自动退出，不再运行。 图4.1主界面调试结果图4.2 创建进程调试结果创建进程运行结果，我们可以根据主界面显示结果，选择数字1，进而进行创建进程，创建进程时，需要你先输入想要创建进程的数目，然后再创建进程。其中创建的进程里面包括进程的大小和其运行状态。如果写入除1-9以外的数字，程序运行将自动退出，不再运行。 图4.2 创建进程调试结果图4.3 进程信息调试结果进程信息调试结果。我们可以根据主界面显示结果，选择数字2，进而可以查看进程的信息，进程的信息里面包括所创建进程的大小和进程的状态。如果我们选择1和3-9的数字则进行相应的操作，如果写入除1-9以外的数字，程序运行将自动退出，不再运行。图4.3 进程信息调试结果图4.4 进程申请调试结果进程申请调试结果，我们可以根据主界面显示结果，选择数字3，然后根据主界面的提示输入所要申请进程的数目，如果输入的申请进程的数目大于所创建进程的数目，则退出提示重新输入申请进程的数目。然后再根据申请数目输入所要申请的进程，申请成功之后退出到主界面。如果我们选择1，2和4-9的数字则进行相应的操作，如果写入除1-9以外的数字，程序运行将自动退出，不再运行。图4.4 进程申请调试结果图4.5 分区创建调试结果分区创建调试结果，我们可以根据主界面显示结果，选择数字4，然后进程随机分配内存的大小，进而创建分区。如果我们选择1，2，3和5-9的数字则进行相应的操作，如果写入除1-9以外的数字，程序运行将自动退出，不再运行。图4.5 分区创建调试结果图4.6 内存分配调试结果内存分配调试结果，我们可以根据主界面显示结果，选择数字5，然后根据程序中所输入的内存分配算法：首次适应算法，循环适应算法，最佳适应算法和最坏适应算法中选择其中一种分配算法，然后进行内存的分配。如果我们选择1-4和6-9的数字则进行相应的操作，如果写入除1-9以外的数字，程序运行将自动退出，不再运行。图4.6 内存分配调试结果图4.7 内存回收调试结果内存回收调试结果，我们可以根据主界面显示结果，选择数字6，然后调试结果就会显示正在执行的进程数，以及正在执行进程的大小和分配的分区号。然后程序会提示你是否结束进程，如果选择是，程序调试将会继续显示主界面，如果选择否，程序调试会直接退出。如果我们选择1-5和7-9的数字则进行相应的操作，如果写入除1-9以外的数字，程序运行将自动退出，不再运行。 图4.7 内存回收调试结果图4.8 打印分区调试结果打印分区调试结果，我们可以根据主界面显示结果，选择数字7，然后程序调试就会显示分区的大小，分区的开始地址以及此分区是否空闲等信息。程序自动会进行分区的打印。如果我们选择1-6和8-9的数字则进行相应的操作，如果写入除1-9以外的数字，程序运行将自动退出，不再运行。 图4.8 打印分区调试结果图4.9 低级调度调试结果低级调度调试结果，我们可以根据主界面显示结果，选择数字8，然后运行界面就会显示所创建进程的信息，然后我们可以选择所创建进程中的一个就绪进程进入cpu，然后cpu进行调度，最后获得处理机进行低级调度的执行。如果我们选择1-7和9的数字则进行相应的操作，如果写入除1-9以外的数字，程序运行将自动退出，不再运行。图4.9 低级调度调试结果图5源程序#include#include#include#include#define Size 4#define num 10#define SUCCESS 1#define ERROR -1typedef int byte;typedef struct byte subareaSize;/分区大小int startLoc;/起始地址int index;/ 分区号SubareaTable;/分区表typedef struct node/ 结点 SubareaTable subarea;/ 分区 struct node *next; int status;/状态位0(空闲)1(使用)*Node,*LinkList;typedef struct byte processSize;int subareaIndex;/保存分区号int status;/进程状态,0(新建)1(执行)-1(终止)-2(未绪。申请但没有分配内存)2(就绪，已分配内存)Process;/进程int subareaSizenum=8,12,16,32,24,16,64,128,40,64;/分区大小Process *pro=NULL;/保持进程信息int ProcessNum=0;/进程数目int applyProcessNum=0;/每次申请进程数目int maxApplyNum=0;/最大可申请数目int *applyIndex=NULL;/申请进程队列int totalApplyNum=0;/申请总数int *assignPointer=NULL;/已分配内存的进程队列int assignFlag=0;/分配索引，表示已申请队列已分配的进程数int exeIndex;/执行的进程号Node *subareaNode=new Node3;/分区回收时，进程所在分区及其前，后分区信息LinkList createLinkList(int n );/建立空闲分区链Node firstFit(LinkList &head,Process pro);/首次适应算法Node nestFit(LinkList &head,Process pro,Node flag);/循环适应算法Node bestFit(LinkList &head,Process pro);/最佳适应算法Node worstFit(LinkList &head,Process pro);/最坏适应算法Node assign(LinkList &head,int orderIndex,int index,Node flagNode);/一次分区分配int assignMemory(LinkList &head);/内存分配void insertNode(LinkList &head,Node q,int index);/插入节点Node deleteNode(LinkList &head,int index);/删除节点int display(LinkList &head);/打印分区分配情况int lowAttemper(int *excursionPointer);/低级调度int findSubarea(LinkList &head,int index);/回收内存int menu();/菜单int creatProcess();/创建进程Process* randomCreatPro(int n);/随机产生进程LinkList createLinkList(int n)/建立空闲分区链cout -创建分区-endl;LinkList head; Node p; head=(LinkList)malloc(sizeof(node); if(head=NULL) cout头结点分配错误next=NULL;/链表尾巴设置为NULL LinkList q=head; int start=0; for(int i=1;i=n;i+) p=(Node)malloc(sizeof(node); if(p=NULL) cout节点分配错误next=q-next; q-next=p; q=p; p-subarea.index=i; p-subarea.subareaSize=subareaSizei-1;/分区表赋值大小 p-subarea.startLoc=start; p-status=0; start+=subareaSizei-1; cout分区创建成功!next;/遍历结点，返回结点,从第一个结点开始遍历 if(p=NULL) cout空闲链表不存在status=0&p-subarea.subareaSize=cessSize) break; p=p-next; while(p!=NULL); if(p=NULL)/没找到合适的结点 return head; return p; Node nestFit(LinkList &head,Process pro,Node flag)/循环适应算法Node p=flag-next;/遍历结点while(p!=NULL)if(p-status=0&p-subarea.subareaSize=cessSize)break;p=p-next;if(p=NULL)/遍历到链表结尾p=head;/从头开始遍历while(p!=flag)/标记结点 p=p-next; if(p-status=0&p-subarea.subareaSize=cessSize) break;if(p=flag)/正常跳出循环，没有合适的结点可分配 return head;elsereturn p;/ 在flag结点前找到一合适的结点分配else return p;/ 在flag结点后找到一合适的结点分配Node bestFit(LinkList &head,Process pro)/最佳适应算法 Node p=head-next;/遍历结点，返回结点,从第一个结点开始遍历 Node q;/返回最佳空闲结点 int leave;/剩余空间 int count=0;/计数器 if(p=NULL) cout空闲链表不存在status=0&p-subarea.subareaSize=cessSize) count+;if(count=1)/第一个可以分配的空闲分区 leave=p-subarea.subareaScessSize; q=p;else if(count1)if(p-subarea.subareaScessSizesubarea.subareaScessSize; q=p; p=p-next;while(p!=NULL); return q; Node worstFit(LinkList &head,Process pro)/最坏适应算法 Node p=head-next;/遍历结点，返回结点,从第一个结点开始遍历 Node q;/返回最大空闲结点 int count=0;/计数器 if(p=NULL) cout空闲链表不存在status=0) count+;if(count=1)/第一个空闲区q=p;else/非第一个空闲区if(p-subarea.subareaSizeq-subarea.subareaSize)/当前结点大于前面最大结点 q=p; p=p-next; while(p!=NULL); if(q-subarea.subareaSize=cessSize) return q; else cout进程大小大于最大分区，无法分配endl; return head; void insertNode(LinkList &head,Node q,int index) Node p;/遍历结点 int j=1;if(head=NULL)coutnext; for(;p;p=p-next) j+; if(j=index) break; q-next=p-next; p-next=q;/插入完成 j=q-subarea.index;/j保持q的分区号 q=q-next;/开始修改分区号 j=q-subarea.index; while(q!=NULL) q-subarea.index=j+1; q=q-next; j+; Node deleteNode(LinkList &head,int index)Node q;/保存要删掉的节点Node p=head;/遍历的节点 int count=0; while(p&countnext; count+; q=p-next; p-next=q-next;return q;int findSubarea(LinkList &head,int index) Node p=head-next;/遍历结点 if(p=NULL) cout空闲链表不存在next; if(j=index-1)break; for(int i=0;inext; return SUCCESS; int display(LinkList &head)/打印分区分配情况 cout -分区信息-endl; Node p;if(head=NULL)cout分区未创建,请先创建分区next;cout.fill( );while(p!=NULL)cout.width(3);coutsubarea.index分区的大小:setw(5)subarea.subareaSizeKB 分区开始位置:setw(6)subarea.startLoc是否空闲:setw(4)statusnext; return SUCCESS;int displayProcess() cout -进程信息-endl;if(pro=NULL)cout进程未创建，请先创建进程endl;return ERROR;for(int i=0;iProcessNum;pro+,i+)couti+1号进程大小:setw(6)processSize 进程状况:status=0)coutstatus=1)/进程状态coutstatus=-1)coutstatus=2)coutstatus=-2)cout未绪;coutendl;pro-=ProcessNum;return SUCCESS;int applyforProcess() cout -申请进程-endl; int index; if(pro=NULL) cout进程未创建,请先创建进程endl;return ERROR; coutapplyProcessNum;while(applyProcessNummaxApplyNum)/申请数目大于最大可申请数目cout申请进程数目大于可申请进程数目，不合法endl;coutapplyProcessNum;displayProcess();for(int i=0;iapplyProcessNum;) coutindex; pro+=(index-1);/修改指针 if(pro-status=0) coutindex号进程申请成功status=-2;/改状态 i+; maxApplyNum-; else coutindex号进程不为创建状态，重新申请endl; pro-=(index-1);/回首址totalApplyNum+=applyProcessNum; return SUCCESS;int assignMemory(LinkList &head)/分配内存int n;Node flagNode;if(applyProcessNum=0|head=NULL)cout未申请进程或未建分区.endl;return ERROR;do cout*内存分配*endl;coutsetw(10)1.首次适应算法endl;coutsetw(10)2.循环适应算法endl;coutsetw(10)3.最佳适应算法endl;coutsetw(10)4.最坏适应算法endl;cout*endl;coutn;while(n4); int count=0;/第一次分配，从头结点开始，其他重上次分配的节点开始applyIndex+=assignFlag;/从分配资源的进程开始分配for(int i=assignFlag;isubareaIndex=assignNode-subarea.index;/保存进程分配的分区号pro-status=2;/修改状态pro-=index;/指针回到起始位置if(assignNode!=NULL)/找到分配分区if(assignNode-subarea.subareaScessSizesubarea.subareaSize=cessSize;/修改分区大小 else if(assignNode-subarea.subareaScessSizeSize)/可再划分分区 Node node=(Node)malloc(sizeof(node); SubareaTable *subarea=(SubareaTable*)malloc(sizeof(SubareaTable);/划分新的分区 subarea-index=assignNode-subarea.index+1;/分区号subarea-subareaSize=assignNode-subarea.subareaScessSize;/分区大小 subarea-startLoc=assignNode-subarea.startLoc+cessSize; node-status=0;/分区状态 node-subarea=*subarea; insertNode(head, node, assignNode-subarea.index+1);/插入空闲链表assignNode-status=1;/ 修改分区使用return assignNode;else return NULL;void amendNodedata(Node p,Node q)if(p-status=0&q-status=0)/ 前后两分区都不是空闲分区int j=p-subarea.index;/分区号p-subarea.subareaSize+=(q-subarea.subareaSize+subareaNode1-subarea.subareaSize);/修改分区大小 p-next=q-next;/修改指针; while(p!=NULL) j+; p-subarea.index=j; p=p-next; else if(p-status=1&q-status=0)/前未空闲后空闲p=subareaNode1; int j=p-subarea.index; p-subarea.subareaSize+=q-subarea.subareaSize; p-next=q-next; while(p!=NULL) j+; p-subarea.index=j; p=p-next; else if(p-status=0&q-status=1)/前空闲后未空闲 int j=p-subarea.