操作系统课程设计--请求调页存储管理方式的模拟1.doc

课 程 设 计课程设计名称： 操作系统课程设计 专 业 班 级 ： 学 生 姓 名 ： 学 号 ： 指 导 教 师 ： 课程设计时间： 专业课程设计任务书学生姓名专业班级学号题 目请求调页存储管理方式的模拟1课题性质其它课题来源自拟课题指导教师同组姓名无主要内容1）假设每个页面中可存放10条指令，分配给作业的内存块数为4。2）用c语言模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。3）置换算法：采用先进先出（fifo）置换算法。任务要求 通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。参考文献任满杰等操作系统原理实用教程 电子工业出版社 2006汤子瀛 计算机操作系统（修订版）西安电子科技大学出版社 2001张尧学 史美林计算机操作系统教程实验指导 清华大学出版社 2000 罗宇等 操作系统课程设计机械工业出版社 2005审查意见指导教师签字：教研室主任签字： 年 月 日 说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页1 需求分析 该设计使用c程序模拟请求调页存储管理方式，实现对页面、页表、地址转换和页面置换过程的模拟。要求能从终端接收需要分配给作业的内存块数，完成给定内存块数的作业模拟，在指令执行过程中能依次显示其物理地址，最后计算出作业运行的缺页率。另外要能对不同内存块数的作业模拟作出比较，分析它们的命中率有何不同，分析其规律。采用先进先出置换算法。2 概要设计假设每个页面中可存放10条指令，分配给作业的内存块数为4。用c语言模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。置换算法：采用先进先出（fifo）置换算法。2.1 通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成： 50%的指令是顺序执行的； 25%的指令是均匀分布在前地址部分； 25%的指令是均匀分布在后地址部分；具体的实施方法是： 在0，319的指令地址之间随机选取一起点m； 顺序执行一条指令，即执行地址为m+1的指令； 在前地址0，m+1中随机选取一条指令并执行，该指令的地址为m； 顺序执行一条指令，其地址为m+1的指令； 在后地址m+2，319中随机选取一条指令并执行； 重复上述步骤，直到执行320次指令。2.2 将指令序列变换为页地址流 设页面大小为1k； 用户内存容量为4页到32页； 用户虚存容里为32k。在用户虚存中，按每k存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条第9条指令为第0页（对应虚存地址为0，9）；第10条第19条指令为第1页（对应虚存地址为10，19）；第310条第319条指令为第31页（对应虚存地址为310，319）。按以上方式，用户指令可组成32页。2.3 计算先进先出（fifo）算法在不同内存容量下的命中率。其中，命中率=1-页面失效次数/页地址流长度3 运行环境3.1 硬件环境pc3.2 软件环境（1）windows xp（2）microsoft visual c+6.04 开发工具和编程语言4.1 开发工具microsoft visual c+6.0 4.2 编程语言c语言5 详细设计5.1 全局变量的宏定义#define invalid -1#define total_instruction 320 /* 指令流长 */#define total_vp 32 /* 虚页长 */5.2 页面的数据结构typedef struct /定义页面类型 int pn; /pn为页号 int pfn; /pfn为块号 int counter; /为一个周期内访问页面次数 int time; /为访问时间pl_type;pl_type pltotal_vp; /页面结构数组5.3 页面控制的数据结构及相关变量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;/pfctotal_vp定义用户进程虚页控制结构/*freepf_head为空内存块号的头指针/*busypf_head为忙内存块的头指针/*busypf_tail为忙内存块的尾指针int diseffect, atotal_instruction;int pagetotal_instruction, offsettotal_instruction;/int atotal_instruction：指令流数组/int pagetotal_instruction：每条指令所属页号/int offsettotal_instruction：每页装入10条指令后取模运算页号偏移值/int diseffect：页面失效次数5.4 先进先出算法函数的设计void fifo(total_pf,j) /* fifo算法,计算使用fifo算法时的命中率*/ int total_pf; /* 用户进程的内存页面数*/ int j; int i; pfc_type *p; initialize(total_pf); /* 初始化相关页面控制用数据结构*/ busypf_head=busypf_tail=null; /* 忙页面队列头，队列尾链接*/ for(i=0;inext; plbusypf_head-pn.pfn=invalid; freepf_head=busypf_head; /*释放忙页面队列中的第一个页面*/ freepf_head-next=null; busypf_head=p; p=freepf_head-next; /*按fifo方式调新页面入内存页面*/ freepf_head-next=null; freepf_head-pn=pagei; plpagei.pfn=freepf_head-pfn; if(busypf_tail=null) busypf_head=busypf_tail=freepf_head; else busypf_tail-next=freepf_head; busypf_tail=freepf_head; freepf_head=p; if(j=1) printf(指令%3d的物理地址为%x ,i+1,&plpagei+offseti); if(i%2=1) printf(n); printf(缺页率:%6.4f 命中率:%6.4fn,(float)diseffect/320,1-(float)diseffect/320);5.5 初始化功能函数的设计void initialize(total_pf) /*初始化相关数据结构,给每个相关的页面赋值*/ 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=null;pfctotal_pf-1.pfn=total_pf-1; freepf_head=&pfc0; /*空页面队列的头指针为pfc0*/5.6 主函数的算法设计main() int s,i,j,temp; srand(getpid()*10); /*由于每次运行时进程号不同，故可以用来作为初始化随即数队列的种子*/ s=(float)319*rand()/rand_max+1; for(i=0;itotal_instruction;i+=4) /* 产生指令队列*/ ai=s; /*任选一指令访问点*/ ai+1=ai+1; /* 顺序执行一条指令*/ ai+2=(float)ai*rand()/rand_max;/* 执行前地址指令m*/ ai+3=ai+2+1; /* 执行后地址指令*/ s=(float)rand()*(318-ai+2)/rand_max+ai+2+2; do printf(*n); printf( 1:给定内存块数的作业模拟n); printf( 2:比较不同内存容量下的命中率n); printf( 3:退出n); printf(*n); printf(请选择需要实现的功能：); scanf(%d,&temp); printf(*n); switch(temp) case 1:printf(请输入给定的内存块数(4-32)：); scanf(%d,&j); printf(*n); fifo(j,1);break; case 2:for(i=4;i=32;i+) /* 用户内存工作区从4个页面到32个页面*/ printf(内存块数:%2d ,i); fifo(i,2); break; while(temp!=3);5.7 源代码如下#include #include #include /#include /#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; /*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;/*pfctotal_vp定义用户进程虚页控制结构 *freepf_head为空页面头的指针 *busypf_head为忙页面头的指针 *busypf_tail为忙页面尾的指针*/pfc_type pfctotal_vp,*freepf_head,*busypf_head,*busypf_tail;int diseffect, atotal_instruction; /*int atotal_instruction：指令流数组*/int pagetotal_instruction, offsettotal_instruction; /*pagetotal_instruction：每条指令所属页号,offsettotal_instruction：每页装入10条指令后取模运算页号偏移值*/void initialize();void fifo();main() int s,i,j,temp; srand(getpid()*10); /*由于每次运行时进程号不同，故可以用来作为初始化随即数队列的种子*/ s=(float)319*rand()/rand_max+1; for(i=0;itotal_instruction;i+=4) /* 产生指令队列*/ ai=s; /*任选一指令访问点*/ ai+1=ai+1; /* 顺序执行一条指令*/ ai+2=(float)ai*rand()/rand_max;/* 执行前地址指令m*/ ai+3=ai+2+1; /* 执行后地址指令*/ s=(float)rand()*(318-ai+2)/rand_max+ai+2+2; do printf(*n); printf( 1:给定内存块数的作业模拟n); printf( 2:比较不同内存容量下的命中率n); printf( 3:退出n); printf(*n); printf(请选择需要实现的功能：); scanf(%d,&temp); printf(*n); switch(temp) case 1:printf(请输入给定的内存块数(4-32)：); scanf(%d,&j); printf(*n); fifo(j,1);break; case 2:for(i=4;i=32;i+) /* 用户内存工作区从4个页面到32个页面*/ printf(内存块数:%2d ,i); fifo(i,2); break; while(temp!=3);void fifo(total_pf,j) /* fifo算法,计算使用fifo算法时的命中率*/ int total_pf; /* 用户进程的内存页面数*/ int j; int i; pfc_type *p; initialize(total_pf); /* 初始化相关页面控制用数据结构*/ busypf_head=busypf_tail=null; /* 忙页面队列头，队列尾链接*/ for(i=0;inext; plbusypf_head-pn.pfn=invalid; freepf_head=busypf_head; /*释放忙页面队列中的第一个页面*/ freepf_head-next=null; busypf_head=p; p=freepf_head-next; /*按fifo方式调新页面入内存页面*/ freepf_head-next=null; freepf_head-pn=pagei; plpagei.pfn=freepf_head-pfn; if(busypf_tail=null) busypf_head=busypf_tail=freepf_head; else busypf_tail-next=freepf_head; busypf_tail=freepf_head; freepf_head=p; if(j=1) printf(指令%3d的物理地址为%x ,i+1,&plpagei+offseti); if(i%2=1) printf(n); printf(缺页率:%6.4f 命中率:%6.4fn,(float)diseffect/320,1-(float)diseffect/320);void initialize(total_pf) /*初始化相关数据结构,给每个相关的页面赋值*/ 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=null;pfctotal_pf-1.pfn=total_pf-1; freepf_head=&pfc0; /*空页面队列的头指针为pfc0*/6 调试分析1）在对页面的数据结构设计时，本来是只想着实现先进先出算法，只需要有页号和块号就行了。后来在看一些参考书的时候，发现对页面数据结构的设计比较复杂，有加进去了访问页面的次数和访问时间，数据结构如下：typedef struct /定义页面类型 int pn; /pn为页号 int pfn; /pfn为块号 int counter; /为一个周期内访问页面次数 int time; /为访问时间pl_type; 后来仔细一想，这样设计的话就会更加完善，虽然在先进先出算法中用不到，但是别的算法中会用到，比如最近最久未使用算法。这样的话就可以增加算法的通用性和可移植性。2）因为本程序是要求随机的产生一个个数为320的指令序列，这就要求程序能随机的产生320个随机数。可是在用rand()函数和srand()产生随机数的时候是要用到种子，而这个种子必须要求在每次执行的时候的是不一样的。这着实让我费尽心思啊，后来经过参考一些资料，终于找到方法。我们可以用getpid()函数得到的进程号作为产生随机数的种子，由于每次运行时进程号不同，故可以用来作为初始化随即数队列的种子。3）在做主程序的功能实现是，我想要显示出每个指令的物理地址，又想把不同内存容量下的命中率做个比较。先开始把这些功能做在了一起，但是程序执行时要显示的东西太多了，太乱。后来想想，把这两个主要功能分开，用switch（）分支语句非别实现，这样的话目的就比较明确。4）在做初始化函数的设计时，先开始没有想到要把各个物理块链接起来，在先进先出的算法设计时就感觉很不对劲，感觉没有办法对物理块之间进行操作。后来想想，应该在初始化对各个指针做好初始化，这样才能把各个内存上的物理块联系起来。5）还有些其它方面的错误，不过只要看一眼，就能改正，是粗心造成的。7 测试结果1）给定内存块数的作业模拟，内存块数4块。运行结果如图1.1、图1.2、图1.3、图1.4图1.1 内存块数为4的作业模拟图1.2 内存块数为4的作业模拟图1.3 内存块数为4的作业模拟图1.4 内存块数为4的作业模拟2)不同内存容量下命中率的比较，运行结果如图2图2 不同内存容量下命中率的比较参考文献任满杰等操作系统原理实用教程 电子工业出版社 2006汤子瀛 计算机操作系统（修订版）西安电子科技大学出版社 2001