实验报告书.docx

1、实验报告书实 验 报 告 书学 生 姓 名 张伟 学 号 11101020228 班 级 计11-2 2013 2014 学年 第 一 学期计算机操作系统实验报告实验名称存储管理实验实验序号2实验日期2013.11-2013.12实验人张伟一、实验目的和要求1实验目的 请求页式存储管理是一种常用的虚拟存储管理技术。本实验目的是通过请求页式存储管理中页面置换算法的模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。2实验要求及考核（1） 实验课与正常上课一样，要求按时出勤。（2） 实验须独立完成，可以查阅各种资料。（3） 实验完毕要求提交纸质实验报告，报告格式参照所提供的模板。

2、（4） 本次实验的验机时间为13周周三，实验报告应在13周周三统一提交。（5） 实验成绩由平时出勤、验机情况和实验报告三部分构成。二、相关背景知识1请求页式管理Linux系统中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页的存储管理方式。当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU发出缺中断），由系统将其所需页面调入内存。这种页面调入方式叫请求调页。为实现请求调页，核心配置了四种数据结构：页表、页帧（框）号、访问位、修改位、有效位、保护位等。页表

3、：表2-1 页表流程图：图2-1 流程图 中断位和外存始址用于标识出所缺页在外存的地址，改变位标识该页在内存时是否被修改过。2请求页式管理中的置换算法（主要介绍本次试验中的两种）（1）先进先出页面淘汰算法（FIFO）FIFO算法认为先调入内存的页不再被访问的可能性要比其它页大，因而选择最先调入内存的页换出。实现FIFO算法需要把各个已分配页面按分配时间顺序链接起来，组成FIFO队列，并设置一置换指针指向FIFO队列的队首页面。这样，当要进行置换时，只需把置换指针所指的FIFO队列前头的页顺次换出，而把换入的页链接在FIFO队尾即可。Belady现象:一般来说，对于任一作业或进程，如果给它分配的

4、内存页面数越接近于它所要求的页面数，则发生缺页的次数会越少。在极限情况下，这个推论是成立的。因为如果给一个进程分配了它所要求的全部页面，则不会发生缺页现象。但是，使用FIFO算法时，在未给进程或作业分配足它所要求的页面数时，有时会出现分配的页面数增多，缺页次数反而增加的奇怪现象。这种现象称为Belady现象。（2）最近最久未使用页面淘汰法（LRU）选择内存中最久未使用的页面被置换。这是局部性原理的合理近似，性能接近最佳算法。但由于需要记录页面使用时间的先后关系，硬件开销太大。硬件机构如：A一个特殊的栈：把被访问的页面移到栈顶，于是栈底的是最久未使用页面。B每个页面设立移位寄存器：被访问时左边最

5、高位置1，定期右移并且最高位补0，于是寄存器数值最小的是最久未使用页面。3. 随机数产生办法关于随机数产生办法，Linux或UNIX系统提供函数srand()和rand()，分别进行初始化和产生随机数。例如：srand ();语句可初始化一个随机数； a0=10*rand()/65535*319+1; a1=10*rand()/65535*a0;语句可用来产生a0与a1中的随机数。三、实验内容1通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：（1）50%的指令是顺序执行的；（2）25%的指令是均匀分布在前地址部分；（3）25%的指令是均匀分布在后地址部分；具体的实施方法是

6、：（1）在0，319的指令地址之间随机选取一起点m；（2）顺序执行一条指令，即执行地址为m+1的指令；（3）在前地址0，m+1中随机选取一条指令并执行，该指令的地址为m；（4）顺序执行一条指令，其地址为m+1；（5）在后地址m+2, 319中随机选取一条指令并执行；（6）重复上述步骤15，直到执行320次指令。2将指令序列变换成页地址流，设（1）页面大小为1K；（2）用户内存容量为4页到32页；（3）用户虚存容量为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中存放的方式为：第0条至第9条指令为第0页（对应虚存地址为0，9）；第10条至第19条指令为第1页（对应虚

7、存地址为10，19）；第310条至第319条指令为第31页（对应虚存地址为310，319）；按以上方式，用户指令可以组成32页。3计算并输出下述各种算法在不同内存容量下的命中率。（1）先进先出页面淘汰算法（FIFO）（2）最近最久未使用页面淘汰法（LRU）命中率=1 - 页面失效次数/页地址流长度在本实验中，页地址流长度为320，页面失效次数为每次访问相应指令时，该指令对应的页不在内存的次数。四、关键数据结构与函数的说明1srand( ) 与rand()函数rand()是真正的随机数生成器，而srand()会设置供rand()使用的随机数种子。如果你在第一次调用rand()之前没有调用sran

8、d()，那么系统会为你自动调用srand()。而使用同种子相同的数调用srand()会导致相同的随机数序列被生成。srand(unsigned)time(NULL)则使用系统定时/计数器的值做为随机种子。每个种子对应一组根据算法预先生成的随机数，所以，在相同的平台环境下，不同时间产生的随机数会是不同的，相应的，若将srand（unsigned）time(NULL)改为srand(TP)（TP为任一常量），则无论何时运行、运行多少次得到的“随机数”都会是一组固定的序列，因此srand生成的随机数是伪随机数。库函数中系统提供了两个函数用于产生随机数：srand()和rand()。原型为：函数一：i

9、nt rand(void)；从srand(seed)中指定的seed开始，返回一个seed,RAND_MAX（0x7fff）间的随机整数。函数二：void srand(unsigned seed)；参数seed是rand()的种子，用来初始化rand()的起始值。但是，要注意的是所谓的“伪随机数”指的并不是假的随机数。其实绝对的随机数只是一种理想状态的随机数，计算机只能生成相对的随机数即伪随机数。计算机生成的伪随机数既是随机的又是有规律的：一部份遵守一定的规律，一部份则不遵守任何规律。比如“世上没有两片形状完全相同的树叶”，这体现到了事物的特性：差异性；但是每种树的叶子都有近似的形状，这正是事

10、物的共性：规律性。从这个角度讲，我们就可以接受这样的事实了：计算机只能产生伪随机数而不是绝对的随机数。系统在调用rand（）之前都会自动调用srand()，如果用户在rand()之前曾调用过srand()给参数seed指定了一个值，那么rand()就会将seed的值作为产生伪随机数的初始值；而如果用户在rand()前没有调用过srand()，那么系统默认将1作为伪随机数的初始值。如果给了一个定值，那么每次rand()产生的随机数序列都是一样的。所以为了避免上述情况的发生我们通常用srand(unsigned)time(0)或者srand(unsigned)time(NULL)来产生种子。如果仍

11、然觉得时间间隔太小，可以在(unsigned)time(0)或者(unsigned)time(NULL)后面乘上某个合适的整数。例如,srand(unsigned)time(NULL)*10)另外，关于time_t time(0)：time_t被定义为长整型，它返回从1970年1月1日零时零分零秒到目前为止所经过的时间，单位为秒。2定义结构体typedef struct /页面结构 int pn, /页面序号 pfn, /页面所在内存区的帧号 time; /上次访问的时间pl_type;struct pfc_struct /页面控制结构 int pn, /页面号 pfn; /内存区页面的帧号

12、struct pfc_struct *next; /页面指针，用于维护内存缓冲区的链式结构;typedef struct pfc_struct pfc_type; /主存区页面控制结构别名3定义常量、变量#define totals 320 /指令流长#define total_page 32 /虚页长pl_type pltotal_page; /页面结构数组pfc_type pfctotal_page, /主存区页面控制结构数组*free_head; /主存区页面控制结构的空闲页面头指针int diseffect; /页错误计数器，初次把页面载入主存时也当做页错误int atotals; /

13、随即指令流数组int pagetotals; /指令对应的页面号int offsettotals; /指令所在页面中的偏移量4功能函数声明int initialize(int); /初始化页面结构数组和页面控制结构数组int FIFO(int); /先进先出算法int LRU(int); /最近最久未使用算法五、编译与执行过程截图执行后出现了随机指令序列，总共320条指令，如图5-1所示。图5-1然后调用FIFO函数与LRU函数计算命中率，显示其结果，如图5-2所示。图5-2六、实验结果与分析结果：由执行现象可得知，增加作业的内存块数，可以降低缺页率，对于不同的算法，增加物理块数都能降低缺页率

14、，只是效果有所不同。理论上，LRU具有比FIFO更好的性能，可是实验中在内存块数量相对少时，现象反应FIFO的性能比LRU好，当内存块数量越来越多时，LRU性能明显比FIFO更好。分析：指令流的产生方式要能体现局部性原理，本实验中指令流设计方式能否最佳地体现局部性原理，还有待验证，并且指令的数量相对较少。一般情况下，LRU具有比FIFO更好的性能。FIFO置换算法设计简单，容易理解。 但它的效率并不是总能达到令人满意的效果。 这种算法只有在顺序访问地址空间时才能达到理想效果， 但根据程序的局部性原理，那些常被访问的页面， 往往要在主存中停留得最久，FIFO算法却将会将其换出页面，留下的只是一些

15、新调入的指令，这将导致内存频繁换页。而LRU则选择在最近一段时间里最久没有使用过的页面予以置换，LRU算法是与每个页面最后使用的时间有关的。当必须置换一个页面时，LRU算法选择过去一段时间里最久未被使用的页面。这种算法以“最近的过去”作为“最近的将来”的近似，较好地利用了程序的局部性原理。一般情况下，能取得较好的效果，是经常采用的页面置换算法。七、调试时遇到的问题及解决方法（提供BUG截屏）1指针赋值时出错。解决办法：程序中定义的指针变量子在赋值时取得是地址，故需要加上取地址符“&”。2结果未达到预定效果，不正确，如图7-1，32page时命中率0.9。图7-1解决办法：在LRU算法中，Cur

16、rentTime应该自增，可是在代码中并没有，加上CurrentTime+，而且在FIFO算法中，指针的调用出现了问题，修改赋值即可。八、调试后的程序源代码#include #include #include /在window操作系统下要屏蔽此条指令#include #ifndef _UNISTD_H#define _UNISTD_H#include #include #endif#define totals 320 /指令流长#define total_page 32 /虚页长typedef struct /页面结构 int pn, /页面序号 pfn, /页面所在内存区的帧号 time;

17、/上次访问的时间pl_type;pl_type pltotal_page; /页面结构数组struct pfc_struct /页面控制结构 int pn, /页面号pfn; /内存区页面的帧号 struct pfc_struct *next; /页面指针，用于维护内存缓冲区的链式结构;typedef struct pfc_struct pfc_type; /主存区页面控制结构别名pfc_type pfctotal_page, /主存区页面控制结构数组*free_head; /主存区页面控制结构的空闲页面头指针int diseffect; /页错误计数器，初次把页面载入主存时也当做页错误int

18、 atotals; /随即指令流数组int pagetotals; /指令对应的页面号int offsettotals; /指令所在页面中的偏移量int initialize(int); /初始化页面结构数组和页面控制结构数组int FIFO(int); /先进先出算法int LRU(int); /最近最久未使用算法int main( ) int s; /随机数int i; srand(10*getpid(); /每次运行时进程号不同，用来作为初始化随机数队列的种子 s = (int)(float)(totals-1)*(rand()/(RAND_MAX+1.0); printf(n-Rand

19、ing-n); for (i=0; itotals; 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)(totals-1)-ai+2)*(rand()/(RAND_MAX+1.0) + ai+2; printf(-n); for (i=0;itotals;i+) /将指令序

20、列变换成页地址流 pagei=ai/10; offseti=ai%10; printf(n-Displaying Hit-n); printf(Paget FIFOt LRUn); for(i=4;i=32;i+) /用户内存工作区从个页面到个页面 printf( %2d t,i); FIFO(i); LRU(i); printf(n); return 0;/初始化页面结构数组和页面控制结构数组int initialize(int total_pf) int i; diseffect=0; for(i=0;itotal_page;i+) pli.pn=i; pli.pfn=-1; /置页面所在

21、主存区的帧号为-1.表示该页不在主存中 pli.time=-1; /置页面结构中的上次访问的时间为-1 for(i=0;itotal_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; free_head=&pfc0; /主存区页面控制结构的空闲页面头指针指向pfc0 return 0;/先进先出算法版本int FIFO(int total_pf)int i;int usetotal_page

22、; int swap=0; initialize(total_pf);pfc_type *pnext,*head; pnext=free_head;head=free_head; for(i=0;itotal_page;i+)usei=0; diseffect=0; for(i=0;ipfn=1) usepnext-pfn=0; pnext=pnext-next; if(pnext=NULL) pnext=head; /换出被替换的页 plpnext-pn.pfn=-1; swap=1; if(usepnext-pfn=0) /如果使用位为0，则换入相应的页 plpagei.pfn=pnext

23、-pfn; /页面结构中要标记帧号 pnext-pn=pagei; /页面控制结构中要标记页号 usepnext-pfn=1; /重置使用位为 pnext=pnext-next; if(pnext=NULL) pnext=head; if(swap=0) free_head=free_head-next; printf(%6.3ft,1-(float)diseffect/320); return 0;/最近最久未使用算法int LRU (int total_pf) int MinT; /最小的访问时间，即很久没被访问过 int MinPn; /拥有最小的访问时间的页的页号 int i,j;in

24、t CurrentTime; /系统当前时间 initialize(total_pf); /初始化页面结构数组和页面控制结构数组 CurrentTime=0;diseffect=0;for(i=0;itotals;i+) if(plpagei.pfn=-1) /页面失效 diseffect+; /页错误次数加 if(free_head=NULL) /无空闲页面 MinT=100000; for(j=0;jplj.time&plj.pfn!=-1) MinT=plj.time; MinPn=j; free_head=&pfcplMinPn.pfn; /最久没被访问过的页被释放 plMinPn.p

25、fn=-1; /最久没被访问过的页被换出主存 plMinPn.time=-1; /最久没被访问过的页的访问时间置为无效 free_head-next=NULL; plpagei.pfn=free_head-pfn; /有空闲页面,把相应的页面换入主存，并把pfn改为相应的帧号 plpagei.time=CurrentTime; /令访问时间为当前系统时间 free_head=free_head-next; /减少一个空闲页面 else plpagei.time=CurrentTime; /命中则刷新该单元的访问时间 CurrentTime+; /系统当前时间加 printf(%6.3ft,1-

26、(float)diseffect/320); return 0;九、实验体会1通过本次操作系统存储实验，使我对操作系统这门课程有了更进一步的认识和了解，通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟储技术的特点。通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。2在本次实验过程中，用到了许多C语言的基本知识和操作系统的基本原理，是对平时所学知识的一次考验，尽管这些知识都学过，但运用到实际时，却不知从何下手，而且错误不断，往往为了找一个错误而花了大量的时间，这是专业知识掌握不够，缺乏实践动手能力的表现。通过不断的纠正错误，上网查找相关资料，以及请教老师，终于完成了本次实验。在实验的过程中我发现了许多自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，以后还要多加努力。