《实验八页面置换模拟程序设计C语言实验.docx》由会员分享，可在线阅读，更多相关《实验八页面置换模拟程序设计C语言实验.docx（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、试验八页面置换模拟程序设计一、【试验目的】加深对恳求页式存储治理实现原理的理解，把握页面置换算法。二、【试验内容】1. 假设分给一作业的内存块数为 4，每个页面中可存放 10 条指令。2. 用 C 语言设计一个程序，模拟一作业的执行过程。设该作业共有 320 条指令，即它的地址空间为 32 页，目前它的全部页面都还未调入内存。在模拟过程中， 假设所访问的指令已经在内存，则显示其物理地址，并转下一条指令。假设所访问的指令尚未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。假设 4 个内存块中均已装入该作业的虚页面，则需进展页面置换。最终显示其物理地址，并转下一条指令。在全部 32
2、0 条指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。3. 置换算法：请分别考虑 OPT、FIFO 和 LRU 算法。4. 作业中指令的访问次序要求按下述原则生成：50%的指令是挨次执行的。25%的指令是均匀分布在前地址即低地址局部。25%的指令是均匀分布在后地址即高地址局部。具体的实施方法是： 在0，319之间随机选取一条起始执行指令，其序号为 m； 挨次执行下一条指令，即序号为 m+1 的指令； 通过随机数，跳转到前地址局部0，m-1中的某条指令处，其序号为 m1； 挨次执行下一条指令，即序号为 m1+1 的指令； 通过随机数，跳转到后地址局部m1+2，319中的某条指令处，其序号
3、为 m2； 挨次执行下一条指令，即序号为 m2+1 的指令； 重复“跳转到前地址局部、挨次执行、跳转到后地址局部、挨次执行”的过程，直至执行完全部 320 条指令。5. 随机数产生方法，Linux或UNIX系统供给函数strand和rand,分别进展初始化和产生随机数。例如： strand ; 语句可初始化一个随机数； a0=10*rand/65535*319+1; a1=10*rand/65535*a0; 语句可用来产生a0 与a1中的随机数。三、【试验指导】本试验的程序设计根本上依据试验内容进展。即首先用srand和rand函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对
4、不同的算法计算出相应的命中率。相关定义如下：1 数据构造(1)页面类型typedef structint pn,pfn,counter,time;pl-type;其中pn 为页号,pfn为面号, counter为一个周期内访问该页面的次数, time为访问时间.(2) 页面掌握构造pfc-structint pn,pfn;struct pfc_struct *next;typedef struct pfc_struct pfc_type;pfc_type pfc_structtotal_vp,*freepf_head,*busypf_head; pfc_type *busypf_tail;其中
5、pfctotal_vp定义用户进程虚页掌握构造,*freepf_head为空页面头的指针,*busypf_head为忙页面头的指针,*busypf_tail为忙页面尾的指针.2. 函数定义（1） Void initialize( ):初始化函数,给每个相关的页面赋值.（2） Void FIFO( ):计算使用FIFO算法时的命中率.（3） Void LRU( ):计算使用LRU算法时的命中率.（4） Void OPT( ):计算使用OPT算法时的命中率.3. 变量定义 (1)int atotal_instruction: 指令流数据组. (2)int total_instruction: 每条
6、指令所属的页号.(3) int offsettotal_instruction: 每页装入10条指令后取模运算页号偏移值. (4)int total_pf: 用户进程的内存页面数.(5)int disaffect: 页面失效次数.4. 程序参考源码及结果 #include #include #include #define TRUE 1#define FALSE 0#define INVALID -1#define NUL 0#define total_instruction 320 /*指令流长*/ #define total_vp 32 /*虚页长*/#define clear_perio
7、d 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,atotal_instruction;int
8、 total_instruction, offsettotal_instruction; int main int S,i; srand(int)getpid);S=(int)rand%390; for(i=0;itotal_instruction;i+=1) /*产生指令队列*/ ai=S; /*任选一指令访问点*/ ai+1=ai+1; /*挨次执行一条指令*/ai+2=(int)rand%390; /*执行前地址指令m*/ ai+3=ai+2+1; /*执行后地址指令*/ S=(int)rand%390; for(i=0;itotal_instruction;i+) /*将指令序列变换成
9、页地址流*/ i=ai/10; offseti=ai%10; for(i=4;i=32;i+) /*用户内存工作区从4个页面到32个页面*/ printf(“%2d frames“,i);FIFO(i); LRU(i); OPT(i); printf(“n“); return 0; void FIFO(total_pf) /*FIFO(First in First out)ALGORITHM*/ int total_pf; /*用户进程的内存页面数*/ int i; pfc_type *p, *t; initialize(total_pf); /*初始化相关页面掌握用数据构造*/busypf_
10、head=busypf_tail=NUL; /*忙页面队列头，对列尾链接*/for(i=0;inext;plbusypf_head-pn.pfn=INVALID; /*释放忙页面队列中的第一个页面*/ freepf_head=busypf_head;freepf_head-next=NUL; busypf_head=p;p=freepf_head-next; /*按方式调页面入内存页面*/ freepf_head-next=NUL;freepf_head-pn=i; pli.pfn=freepf_head-pfn; if(busypf_tail=NUL) busypf_head=busypf_
11、tail=freepf_head; elsebusypf_tail-next=freepf_head; busypf_tail=freepf_head;freepf_head=p;printf(“FIFO:%6.4F“,1-(float)diseffect/320);void LRU(total_pf) int total_pf;int min,minj,i,j,present_time; initialize(total_pf);present_time=0; for(i=0;itotal_instruction;i+)if(pli.pfn=INVALID) /*页面失效*/diseffec
12、t+;if(freepf_head=NUL) /*无空闲页面*/min=32767; for(j=0;jplj.time&plj.pfn!=INVALID)min=plj.time; minj=j;freepf_head=&pfcplminj.pfn; plminj.pfn=INVALID; plminj.time=-1;freepf_head-next=NUL;pli.pfn=freepf_head-pfn; pli.time=present_time; freepf_head=freepf_head-next;else pli.time=present_time; present_time
13、+;printf(“LRU:%6.4f“,1-(float)diseffect/320);void OPT(total_pf) /*OPT(Optimal Replacement)ALGORITHM*/ int total_pf; int i,j,max,max,d,disttotal_vp; pfc_type *t;initialize(total_pf); for(i=0;itotal_instruction;i+) if(pli.pfn=INVALID) diseffect+; if(freepf_head=NUL) for(j=0;jtotal_vp;j+)if(plj.pfn!=IN
14、VALID) distj=32767; else distj=0; d=1; for(j=i+1;jtotal_instruction;j+) if(plj.pfn!=INVALID) distj=d; d+; max=-1;for(j=0;jtotal_vp;j+) if(maxnext=NUL; plmax.pfn=INVALID; pli.pfn=freepf_head-pfn; freepf_head=freepf_head-next; printf(“OPT:%6.4f“,1-(float)diseffect/320); void initialize(total_pf) /*初始化
15、相关数据构造*/ int total_pf; /*用户进程的内存页面数*/ int i; diseffect=0; for(i=0;itotal_vp;i+) pli.pn=i;pli.pfn=INVALID; /*置页面掌握构造中的页号，页面为空*/ pli.counter=0;pli.time=-1; /*页面掌握构造中的访问次数为0，时间为-1*/ for(i=1;itotal_pf;i+) pfci-1.next=&pfci;pfci-1.pfn=i-1;/*建立pfci-1和pfci之间的连接*/ pfctotal_pf-1.next=NUL;pfctotal_pf-1.pfn=total_pf-1; freepf_head=&pfc0; /*页面队列的头指针为pfc0*/