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

1、兰州大学操作系统实验八存储 管理模拟题目和答案-实验报告实验报告实验八实验名称：存储管理模拟实验目的：.掌握请求分页存储管理系统的基本原理.实现一个模拟的虚拟分页存储管理系统 实验要求：编写一个程序，模拟一个虚拟分页存储管理系 统。其中，由系统随机产生进程；进程大小、进程到达次序、时间、进程执行轨 迹（页面访问顺序）也随机生成，但进程之间 必须有并发存在，进程执行时间需有限，进程 调度采用时间片轮转算法（以页面模拟）；rss 驻留集大小物理块分配策略采取固定分配局 部置换；分配算法采用按比例分配算法；调页 采用请求调页方式；置换分别采用FIFO、LRU（ 一直没用）访问次数 和简单CLOCK算

2、 法（循环链表）标志 有没有被访问； 驻留集大小可调，观察驻留集大小对缺页率的 影响。算法思想：FIFO先进先出法LRU最久未使用算法CLOCK简单时钟算法命中率=1 -页面失效次数/页地址流（序列）长度驻留集大小可调，观察驻留集大小对缺页率的影 响。结构体定义页面序号页页框号页框号包含链表：空闲页面表 忙页面表包含数组：进程数组页面号数组流程图:开始引用块否C页号在/ 是是选择 FIFO LRU CLOCK结束实验结果分析：观察数据可看出：横向：三种替换算法的命中率 由高到底排列应该是 LRUCLOCKFIFO 。纵向：进程的驻留级越大，其缺页率就越低息tngkxqa1biiotLi ：_/

3、香|atnstructlonSb 利e3$砧州 211恰16931321S141幅 2721t3J 3B2舞21729301B1ias1611ine i1必133iM 77262ZM ZS12499IK 163177171M X151154H 54176IS 11421U 61;21227575029a2912M 之日写362ii lit粉7M2m i2i，滥22617717H2542552 豳29792122107let42*3S1M AS3123132&Z2E3JSft州。m no31251Sm i213D6-JOTZZfl Z29311312123124compare the three

4、 methods:RssFIFOLRU40,5660,50650.522O.SZZ60.547 .5417白.5550.S5680*5750,572gCL 5810,597100.5910 . 606110*6690.616129.6150,628130.5470,637140.6590.653150.(56016046780.672170,7130,697180.7190.713190.7440.71920047090.722210*7720,744220.7810.77223CL 784CL 794243.8220.806Z504819260.8250.841270.866Q + 8532

5、80.8660.859290.8650.865300.87rB0,684310.9090 . 894320 . 9006.960CLOCK O,50G .519 0.547 6.553 6,578 0 + 591 0.600 6.616 0*622 0.644 0.656 04672 0.6780,7030,722%Fl、77G d9-T i丸,7T,6r9,781队、7919.0.9,B,7,8,8,8Q9223 c4Z54Q d3,3. B,0.,Q ,8 ，呼 ,96& 06J940实验体会：.内存中进程的多少会影响驻留集大小和缺页中断率。如果内存中进程太多，将导致每个进 程的驻留集太小

6、，发生缺页中断的概率很 大。相应地，系统发生抖动的可能性就会很 大。如果在内存中保持太少的活动进程， 那么所有活动进程同时处于阻塞状态的可能性 就会很大，从而降低处理机的利用率。.置换算法的好坏将直接影响系统的性能，不适当的置换算法可能导致系统出现“抖动”现象。常用的页面置换算法：最佳置换算法、最近最 少使用算法、先进先出算法和时钟算法等。最 佳置换算法难以实现但可以成为核对其他算 法的标准。.也应注意负载问题，解决系统应当保持多少个 活动进程驻留在内存的问题，即控制多道程序 系统的度。当内存中的活动进程数太少时，负 载控制将增加新进程或激活一些挂起进程进 入内存；反之，当内存中的进程数太多时

7、，负 载控制将暂时挂起一些进程，减少内存中的活 动进程数。实验代码：#include #include #include #include #define TRUE 1#define FALSE 0 #define INVALID -1#define total_instruction 320 指令流长#define total_vp 32#define clear_periodtypedef struct构int pn, pfn,内存区的页框号counter, time;pl_type;pl_type pltotal_vp;页长50页面结构数组struct pfc_struct制结构int

8、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

9、 atotal_instruction;int pagetotal_instruction;号int offsettotal_instruction;中的偏移量int initialize(int);随即指令流数组指令对应的页面指令所在页面初始化页面结构数int FIFO(int);先进先出算法组和页面控制结构数组intLRU(int);最近最久未使用算法int CLOCK(int);简单时钟(钟表)算法int main()int s; 随机数int i;srand(10*getpid(); /*每次运行时进程号不 同，用来作为初始化随机数队列的种子*/s=(int)(float)(total

10、_instruction-1)*(rand()/(RAND_MAX+1.0);printf(nrandinstructionsqueuen);for (i=0; itotal_instruction; i+=4) 产生指 令队列ai=s; 任选一指令访问点 mai+1=ai+1;/顺序执行一条指令ai+2=(int)(float)ai*(rand()/(RAND_MAX+1.0)；/执行前地址指令mai+3=ai+2+1; 顺序执行一条指令 printf(%6d%6d%6d%6dn, ai,ai+1,ai+2,ai+3);s=(int)(float)(total_instruction-1)-

11、ai+2)*(rand()/ (RAND_MAX+1.0) + ai+2;printf(n);for (i=0;itotal_instruction;i+)将指令序列变换成页地址流pagei=ai/10;offseti=ai%10;printf(compare the three methods:);printf(nn);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;初始化页面结构数

12、组和页面控制结构数组/total_pf;用户进程的内存页面数int initialize(int total_pf)int i;diseffect=0;for(i=0;itotal_vp;i+)pli.pn=i;pli.pfn=INV ALID;置页面所在主存区的帧号为-1.表示该页不在主存中pli.counter=0;置页面结构中的访问次数为0pli.time=-1;置页面结构中的上次访问的时间为-1for(i=0;itotal_pf-1;i+)pfci.next=&pfci+1; 建立 pfci-1和 pfci之间的链接pfci.pfn=i;初始化主存区页面的页框号pfctotal_pf-

13、1.next=NULL;pfctotal_pf-1.pfn=total_pf-1;fre叩f_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

14、;itotal_instruction;i+)if(plpagei.pfn=INV ALID)页面失效diseffect+;/页错误次数加if(freepf_head=NULL)无空闲页面MinT=100000;for(j=0;jplU.time&plj.pfn!=INV ALID) MinT=plj.time; MinPn=j; freepf_head=&pfcplMinPn.pfn;最久没被访问过的页被释放plMinPn.pfn=INV ALID;/最久没被访问过的页被换出主存plMinPn.time=-1;最久没被访问过的页的访问时间置为无效 freepf_head-next=NULL;

15、 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)in

16、t 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;itotal_vp;i+)usei=0;初始化使用位为diseffect=0;for(i=0;ipfn=1) 若时钟指针指向的页的使用位为，则改为并跳过usepnext-pfn=0;pnext=pnext-next;if(pnext=NULL) pnext=head; /如果时钟指针到达队列尾部，重新返

17、回头部换出被替换的页plpnext-pn.pfn=INV ALID;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;刷新

18、使用位为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;itotal_vp;i+)usei=0;diseffect=0;for(i=0;ipfn=1)usepnext-pfn=0;pnext=pnext-next;if(pnext=NULL) pnext=hea