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

《操作系统课程设计请求调页存储管理方式的模拟1.doc》由会员分享，可在线阅读，更多相关《操作系统课程设计请求调页存储管理方式的模拟1.doc（22页珍藏版）》请在三一办公上搜索。

1、课 程 设 计课程设计名称： 操作系统课程设计 专 业 班 级 ： 学 生 姓 名 ： 学 号 ： 指 导 教 师 ： 课程设计时间： 专业课程设计任务书学生姓名专业班级学号题 目请求调页存储管理方式的模拟1课题性质其它课题来源自拟课题指导教师同组姓名无主要内容1）假设每个页面中可存放10条指令，分配给作业的内存块数为4。2）用c语言模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果

2、4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。3）置换算法：采用先进先出（FIFO）置换算法。任务要求 通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。参考文献任满杰等操作系统原理实用教程 电子工业出版社 2006汤子瀛 计算机操作系统（修订版）西安电子科技大学出版社 2001张尧学 史美林计算机操作系统教程实验指导 清华大学出版社 2000 罗宇等 操作系统课程设计机械工业出版社 2005审查意见指导教师签字：教研室主任签字： 年 月 日 说明：本表

3、由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页1 需求分析 该设计使用C程序模拟请求调页存储管理方式，实现对页面、页表、地址转换和页面置换过程的模拟。要求能从终端接收需要分配给作业的内存块数，完成给定内存块数的作业模拟，在指令执行过程中能依次显示其物理地址，最后计算出作业运行的缺页率。另外要能对不同内存块数的作业模拟作出比较，分析它们的命中率有何不同，分析其规律。采用先进先出置换算法。2 概要设计假设每个页面中可存放10条指令，分配给作业的内存块数为4。用c语言模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟

4、过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。置换算法：采用先进先出（FIFO）置换算法。2.1 通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成： 50%的指令是顺序执行的； 25%的指令是均匀分布在前地址部分； 25%的指令是均匀分布在后地址部分；具体的实施方法是： 在0，319的指令地址之间随机选取一起点m； 顺序

5、执行一条指令，即执行地址为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）。

6、按以上方式，用户指令可组成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 页面的数据结

7、构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,*

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

9、uction：每页装入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=INVAL

10、ID; 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

11、_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

12、=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 主函数的算法设计ma

13、in() 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

14、_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个页面*/ prin

15、tf(内存块数:%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

16、页号, 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

17、_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)

18、; /*由于每次运行时进程号不同，故可以用来作为初始化随即数队列的种子*/ 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:给

19、定内存块数的作业模拟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; whil

20、e(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; /*释放忙页面队列中的第一个页面*/ fre

21、epf_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(指令

22、%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; /*置页面控制结构中的页号，页面为空*/ p

23、li.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）在对页面的数据结构设计时，本来是只想着实现先进先出算法，只需要有页号和块号就行了。后来在看一些参考书的时候，发现对页面数据结构的设计比较复杂，

24、有加进去了访问页面的次数和访问时间，数据结构如下：typedef struct /定义页面类型 int pn; /pn为页号 int pfn; /pfn为块号 int counter; /为一个周期内访问页面次数 int time; /为访问时间pl_type; 后来仔细一想，这样设计的话就会更加完善，虽然在先进先出算法中用不到，但是别的算法中会用到，比如最近最久未使用算法。这样的话就可以增加算法的通用性和可移植性。2）因为本程序是要求随机的产生一个个数为320的指令序列，这就要求程序能随机的产生320个随机数。可是在用rand()函数和srand()产生随机数的时候是要用到种子，而这个种子必

25、须要求在每次执行的时候的是不一样的。这着实让我费尽心思啊，后来经过参考一些资料，终于找到方法。我们可以用getpid()函数得到的进程号作为产生随机数的种子，由于每次运行时进程号不同，故可以用来作为初始化随即数队列的种子。3）在做主程序的功能实现是，我想要显示出每个指令的物理地址，又想把不同内存容量下的命中率做个比较。先开始把这些功能做在了一起，但是程序执行时要显示的东西太多了，太乱。后来想想，把这两个主要功能分开，用switch（）分支语句非别实现，这样的话目的就比较明确。4）在做初始化函数的设计时，先开始没有想到要把各个物理块链接起来，在先进先出的算法设计时就感觉很不对劲，感觉没有办法对物

26、理块之间进行操作。后来想想，应该在初始化对各个指针做好初始化，这样才能把各个内存上的物理块联系起来。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

27、张尧学 史美林计算机操作系统教程实验指导 清华大学出版社 2000 罗宇等 操作系统课程设计机械工业出版社 2005 心得体会我的实验的主要目的是完成请求调页存储管理方式的模拟，通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。主要功能是在用户给定分配给用户作业的内存空间后，随机产生个数是320的指令序列，在指令执行过程中显示其物理地址，最后计算过程中的缺页次数和缺页率。本程序中用到的页面置换算法是先进先出算法，算是比较简单的，在理论知识学习的时候就感觉比较简单。功能的实现还是主要依靠链表，来实现内存和外存的页面置换。因为在大一时就开始学习指针和链表，到

28、现在来说还是比较熟悉的，在应用过程中也没有遇到特别难解决的问题。虽然程序的算法比较简单些，但从中我还是学到了好多以前没学到的东西，那些被我认为没有用的知识和感觉自己已经会了的东西。通过这一周的实践学习，我认识到学好计算机要重视实践操作，不仅仅是学习操作系统，以及其它的计算机方面的知识都要重在实践，很多以前学过的东西，在运用时都不能很熟练，也说明理论知识和实践之间的差别。这就告诉了我们在以后的学习过程中要培养自己的动手能力，要将学过的知识转化为实践。作为一个计科专业的学生，通过这周的学习，使我更加明白了动手能力的重要性。在这次的课程设计中，我不断地去找书本知识和查阅其它有关资料，不仅巩固了对课本知识的掌握，还有利于以后更好的进步，提高了对课外知识的了解，虽然花费了不少时间，但只要学到有价值的东西，我认为都是值得的。在完成该试验的过程中，我问了同学和老师，还查阅了很多书籍，通过学习，翻看以前学过的知识，使我明白了我在学习知识上的很多不足。不过在此同时又重新复习了课本，从中学到了许多以前未学到的知识，感觉非常有成就感，让我对自己更加有信心，让我对操作系统这门课程也更感兴趣了，现在我也愿意去认真研究学习了。在以后的学习过程中，我要认真负责地对待课本中的每一个知识点，进一步充实自己，提高自己。最后还要感谢老师的辛勤指导。