存储管理实验报告.doc

昆明理工大学信息工程与自动化学院学生实验报告（ 2012 2013 学年 第 二 学期 ）课程名称：操作系统 开课实验室： 年 月 日年级、专业、班学号姓名成绩实验项目名称存储管理指导教师杨云飞教师评语 教师签名： 年 月 日一、实验目的存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。通过本次实验，要求学生通过编写和调试地址转换过程的模拟程序以加强对地址转换过程的了解，通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。二、实验原理及基本技术路线图（方框原理图）用C或C+语言模拟实现请求式分页管理。要求实现：页表的数据结构、分页式内存空间的分配及回收（建议采用位图法）、地址重定位、页面置换算法（从FIFO,LRU,NRU中任选一种）。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 creatProcess();/创建进程Process* randomCreatPro(int n);/随机产生进程下面是各种方法简述：(1) 最优替换算法，即OPT算法。上面介绍的几种页面替换算法主要是以主存储器中页面调度情况的历史信息为依据的，它假设将来主存储器中的页面调度情况与过去一段时间内主存储器中的页面调度情况是相同的。显然，这种假设不总是正确的。最好的算法应该是选择将来最久不被访问的页面作为被替换的页面，这种替换算法的命中率一定是最高的，它就是最优替换算法。要实现OPT算法，唯一的办法是让程序先执行一遍，记录下实际的页地址流情况。根据这个页地址流才能找出当前要被替换的页面。显然，这样做是不现实的。因此，OPT算法只是一种理想化的算法，然而，它也是一种很有用的算法。实际上，经常把这种算法用来作为评价其它页面替换算法好坏的标准。在其它条件相同的情况下，哪一种页面替换算法的命中率与OPT算法最接近，那么，它就是一种比较好的页面替换算法。 (2)先进先出算法，即FIFO算法（First-In First-Out algorithm）。这种算法选择最先调入主存储器的页面作为被替换的页面。它的优点是比较容易实现，能够利用主存储器中页面调度情况的历史信息，但是，没有反映程序的局部性。因为最先调入主存的页面，很可能也是经常要使用的页面。(3) 最久没有使用算法，即LRU算法（Least Recently Used algorithm）。这种算法把近期最久没有被访问过的页面作为被替换的页面。它把LFU算法中要记录数量上的多与少简化成判断有与无，因此，实现起来比较容易。 (4) 近期最少使用算法，即LFU算法（Least Frequently Used algorithm）。这种算法选择近期最少访问的页面作为被替换的页面。显然，这是一种非常合理的算法，因为到目前为止最少使用的页面，很可能也是将来最少访问的页面。该算法既充分利用了主存中页面调度情况的历史信息，又正确反映了程序的局部性。但是，这种算法实现起来非常困难，它要为每个页面设置一个很长的计数器，并且要选择一个固定的时钟为每个计数器定时计数。在选择被替换页面时，要从所有计数器中找出一个计数值最大的计数器。因此，通常采用如下一种相对比较简单的方法。 (5) 最近未使用法缺页中断率 = 缺页中断次数总的页面引用次数*100%三、所用仪器、材料（设备名称、型号、规格等）。计算机一台4、 实验方法、步骤# include # include # include # include # include #define Size 4#define num 10typedef 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 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 1; 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 1;int displayProcess() cout -进程信息-endl;if(pro=NULL)cout进程未创建，请先创建进程endl;return 0;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 1;int applyforProcess() cout -申请进程-endl; int index; if(pro=NULL) cout进程未创建,请先创建进程endl;return 0; 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 1;int assignMemory(LinkList &head)/分配内存int n;Node flagNode;if(applyProcessNum=0|head=NULL)cout未申请进程或未建分区.endl;return 0;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.index; p-subarea.subareaSize+=subareaNode1-subarea.subareaSize;p-next=subareaNode1-next; while(p!=NULL) j+; p-subarea.index=j; p=p-next; int callbackMemory(LinkList &head, int index)char n;coutindex+1进程正在执行.endl;cout进程大小为setw(5)processSize 分配的分区号subareaIndexendl;docoutn;coutsubareaIndex);if(subareaNode2!=NULL) if(subareaNode0-status=1&subareaNode2-status=1) subareaNode0-status=0;else amendNodedata(subareaNode0,subareaNode2);else if(subareaNode0=NULL)if(subareaNode0-status=0)subareaNode0-subarea.subareaSize+=subareaNode1-subarea.subareaSize;subareaNode0-next=subareaNode2;elsesubareaNode0-status=0;return 1 ;elsecout您没结束进程,进程不释放,分区不回收endl;return 0;int lowAttemper(int *excursionPointer) cout -低级调度-endl;if(*excursionPointer0)cout没有已分配好资源的进程;return 0;elseint n;displayProcess();do coutn;coutendl;while(nProcessNum|(pro+n-1)-status!=2);(pro+n-1)-status=1;/进程状态改变exeIndex=n-1;coutCPU正在调度.endl;coutn进程获得处理机,开始执行!endl;return 1;int creatProcess() cout -创建进程-endl; coutProcessNum; applyIndex=new intProcessNum;/初始化进程申请队列 assignPointer=new intProcessNum;/初始化进程分配队列 maxApplyNum=ProcessNum; pro=randomCreatPro(ProcessNum); cout进程正在创建.endl; return 1;Process* randomCreatPro(int n)Process *process=new Processn; srand(unsigned)time(NULL);/播一次种for(int i=0;in;i+)cessSize=1+rand()%128;/随机产生进程的大小processi.status=0;/初始化进程状况 processi.subareaIndex=-1;/初始化分区号，-1未分配，进程在外存上return process;int main()int flg,i;LinkList head;flg=1;