兰州大学操作系统实验八存储管理模拟题目和答案,实验报告.docx

实验报告 实验八 实验名称：存储管理模拟实验目的：1. 掌握请求分页存储管理系统的基本原理2. 实现一个模拟的虚拟分页存储管理系统实验要求: 编写一个程序，模拟一个虚拟分页存储管理系统。其中，由系统随机产生进程；进程大小、进程到达次序、时间、进程执行轨迹（页面访问顺序）也随机生成，但进程之间必须有并发存在，进程执行时间需有限，进程调度采用时间片轮转算法（以页面模拟）；rss驻留集大小物理块分配策略采取固定分配局部置换；分配算法采用按比例分配算法；调页采用请求调页方式；置换分别采用FIFO、LRU(一直没用) 访问次数 和简单CLOCK算法（循环链表）标志 有没有被访问； 驻留集大小可调，观察驻留集大小对缺页率的影响。算法思想:FIFO 先进先出法LRU 最久未使用算法CLOCK 简单时钟算法命中率页面失效次数页地址流(序列)长度驻留集大小可调，观察驻留集大小对缺页率的影响。结构体定义页面控制表表结构 页面号指针页面控制结构单位时间访问次数页框号上次访问时间页面序号页面页框号包含链表：空闲页面表 忙页面表 包含数组：进程数组 页面号数组 开始流程图：引用块编号大于物理块？分配物理块为其分配页号随机得到进程指令序列 否页号在物理块内？是是是否完成？选择FIFO LRU CLOCK 置换算法置换是结束实验结果分析：观察数据可看出：横向：三种替换算法的命中率由高到底排列应该是LRU>CLOCK>FIFO。 纵向：进程的驻留级越大，其缺页率就越低。实验体会：1. 内存中进程的多少会影响驻留集大小和缺页中断率。如果内存中进程太多，将导致每个进程的驻留集太小，发生缺页中断的概率很大。相应地，系统发生抖动的可能性就会很大。如果在内存中保持太少的活动进程，那么所有活动进程同时处于阻塞状态的可能性就会很大，从而降低处理机的利用率。2. 置换算法的好坏将直接影响系统的性能，不适当的置换算法可能导致系统出现“抖动”现象。常用的页面置换算法：最佳置换算法、最近最少使用算法、先进先出算法和时钟算法等。最佳置换算法难以实现但可以成为核对其他算法的标准。3. 也应注意负载问题，解决系统应当保持多少个活动进程驻留在内存的问题，即控制多道程序系统的度。当内存中的活动进程数太少时，负载控制将增加新进程或激活一些挂起进程进入内存；反之，当内存中的进程数太多时，负载控制将暂时挂起一些进程，减少内存中的活动进程数。实验代码：#include <stdio.h>#include <stdlib.h>#include <unistd.h> #include <string.h>#define TRUE 1#define FALSE 0#define INVALID -1#define total_instruction 320 /指令流长#define total_vp 32 /页长#define clear_period 50 typedef struct /页面结构 int pn,/页面序号 pfn,/页面所在内存区的页框号counter,/单位时间内访问次数time;/上次访问的时间pl_type;pl_type pltotal_vp; /页面结构数组struct pfc_struct /页面控制结构 int pn,/页面号 pfn;/内存区页面的页框号 struct pfc_struct *next;/页面指针，用于维护内存缓冲区的链式结构;typedef struct pfc_struct pfc_type; /主存区页面控制结构别名pfc_type pfctotal_vp, /主存区页面控制结构数组*freepf_head, /主存区页面控制结构的空闲页面头指针*busypf_head, /主存区页面控制结构的忙页面头指针*busypf_tail; /主存区页面控制结构的忙页面尾指针int diseffect; /页错误计数器，初次把页面载入主存时也当做页错误int atotal_instruction; /随即指令流数组int pagetotal_instruction; /指令对应的页面号int offsettotal_instruction; /指令所在页面中的偏移量int initialize(int);/初始化页面结构数组和页面控制结构数组int FIFO(int);/先进先出算法int LRU(int);/最近最久未使用算法int CLOCK(int);/简单时钟(钟表)算法int main( ) int s;/随机数 int i; srand(10*getpid(); /*每次运行时进程号不同，用来作为初始化随机数队列的"种子"*/ s = (int)(float)(total_instruction-1)*(rand()/(RAND_MAX+1.0);printf("n-rand instructions queue-n"); for (i=0; i<total_instruction; i+=4) /产生指令队列 ai=s; /任选一指令访问点m ai+1=ai+1; /顺序执行一条指令 ai+2=(int)(float)ai*(rand()/(RAND_MAX+1.0); /执行前地址指令m ai+3=ai+2+1; /顺序执行一条指令 printf("%6d%6d%6d%6dn", ai,ai+1,ai+2,ai+3); s = (int)(float)(total_instruction-1)-ai+2)*(rand()/(RAND_MAX+1.0) + ai+2; printf("-n");for (i=0;i<total_instruction;i+) /将指令序列变换成页地址流 pagei=ai/10; offseti=ai%10; printf("compare the three methods:");printf("n-n"); printf(" Rsst FIFOt LRUt CLOCKn"); for(i=4;i<=32;i+) /用户内存工作区从4个页面到32个页面 printf(" %2d t",i); FIFO(i); LRU(i);CLOCK(i); printf("n"); return 0;/初始化页面结构数组和页面控制结构数组/total_pf; 用户进程的内存页面数int initialize(int total_pf) int i; diseffect=0; for(i=0;i<total_vp;i+)pli.pn=i;pli.pfn=INVALID; /置页面所在主存区的帧号为-1.表示该页不在主存中pli.counter=0;/置页面结构中的访问次数为0pli.time=-1;/置页面结构中的上次访问的时间为-1for(i=0;i<total_pf-1;i+)pfci.next=&pfci+1; /建立pfci-1和pfci之间的链接pfci.pfn=i; /初始化主存区页面的页框号pfctotal_pf-1.next=NULL;pfctotal_pf-1.pfn=total_pf-1;freepf_head=&pfc0;/主存区页面控制结构的空闲页面头指针指向pfc0return 0;/最近最久未使用算法/int total_pf; 用户进程的内存页面数int LRU (int total_pf) int MinT;/最小的访问时间，即很久没被访问过int MinPn;/拥有最小的访问时间的页的页号int i,j;int CurrentTime;/系统当前时间 initialize(total_pf);/初始化页面结构数组和页面控制结构数组 CurrentTime=0;diseffect=0;for(i=0;i<total_instruction;i+)if(plpagei.pfn=INVALID) /页面失效diseffect+;/页错误次数加 if(freepf_head=NULL) /无空闲页面 MinT=100000; for(j=0;j<total_vp;j+) /找出time的最小值，表明该页很久没被访问过 if(MinT>plj.time&&plj.pfn!=INVALID) MinT=plj.time; MinPn=j; freepf_head=&pfcplMinPn.pfn; /最久没被访问过的页被释放 plMinPn.pfn=INVALID; /最久没被访问过的页被换出主存 plMinPn.time=-1;/最久没被访问过的页的访问时间置为无效 freepf_head->next=NULL; plpagei.pfn=freepf_head->pfn; /有空闲页面,把相应的页面换入主存，并把pfn改为相应的页框号 plpagei.time=CurrentTime;/令访问时间为当前系统时间 freepf_head=freepf_head->next; /减少一个空闲页面elseplpagei.time=CurrentTime; /命中则刷新该单元的访问时间CurrentTime+; /系统当前时间加 printf("%6.3ft",1-(float)diseffect/320);return 0;/简单时钟算法/int total_pf; 用户进程的内存页面数int CLOCK(int total_pf)int i;int usetotal_vp; /使用位int swap;swap=0; /发生替换initialize(total_pf);pfc_type *pnext; /时钟指针pfc_type *head; /队列头指针pnext=freepf_head;head=freepf_head;for(i=0;i<total_vp;i+)usei=0; /初始化使用位为diseffect=0;for(i=0;i<total_instruction;i+)if (plpagei.pfn=INVALID) /页面失效,不在主存中diseffect+;/页错误次数加if(freepf_head=NULL) /无空闲页面while(usepnext->pfn=1) /若时钟指针指向的页的使用位为，则改为并跳过usepnext->pfn=0;pnext=pnext->next;if(pnext=NULL) pnext=head; /如果时钟指针到达队列尾部，重新返回头部/换出被替换的页plpnext->pn.pfn=INVALID;swap=1;if(usepnext->pfn=0) /如果使用位为，则换入相应的页plpagei.pfn=pnext->pfn; /页面结构中要标记页框号pnext->pn=pagei; /页面控制结构中要标记页号usepnext->pfn=1;/重置使用位为pnext=pnext->next;/时钟指针下移if(pnext=NULL) pnext=head;/如果时钟指针到达队列尾部，重新返回头部if(swap=0) freepf_head=freepf_head->next;else/页面在主存中useplpagei.pfn=1; /刷新使用位为printf("%6.3ft",1-(float)diseffect/320);return 0;/先进先出算法版本/int total_pf; 用户进程的内存页面数/实现细节由CLOCK算法退化而来，与FIFO同效果int FIFO(int total_pf)int i;int usetotal_vp;int swap=0;initialize(total_pf);pfc_type *pnext,*head;pnext=freepf_head;head=freepf_head;for(i=0;i<total_vp;i+)usei=0;diseffect=0;for(i=0;i<total_instruction;i+)if (plpagei.pfn=INVALID) /页面失效,不在主存中diseffect+;if(freepf_head=NULL) /无空闲页面while(usepnext->pfn=1)usepnext->pfn=0;pnext=pnext->next;if(pnext=NULL) pnext=head;/换出被替换的页plpnext->pn.pfn=INVALID;swap=1;if(usepnext->pfn=0) /如果使用位为，则换入相应的页plpagei.pfn=pnext->pfn; /页面结构中要标记页框号pnext->pn=pagei; /页面控制结构中要标记页号usepnext->pfn=1;/重置使用位为pnext=pnext->next;if(pnext=NULL) pnext=head;if(swap=0) freepf_head=freepf_head->next;printf("%6.3ft",1-(float)diseffect/320);return 0;