实验请求页式存储管理页面置换算法

1、操作系统实验报告班级:计科0801班 姓名：韩伟伟 学号:08407106时间：2018-5-25实验五请求页式存储管理的页面置换算法一.实验目的通过请求页式存储管理中页面置换算法模拟程序，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。二实验属性设计三.实验内容1通过随机数产生一个指令序列，共320条指令，指令的地址按下述原则生产：50 %的指令是顺序执行的；25%的指令是均匀分布在前地址部分；25%的指令是均匀分布在后地址部分。2将指令序列变换成为页地址流设页面大小为1K;用户内存容量为 4页到32页；用户虚存容量为 32K。在用户虚存中，按每 K存放10条指令排列虚存地址，即

2、320条指令在虚存中的存放方式为：第0条至第9条指令为第0页；第10条至19条指令为第1页；第310条至319条 指令为第31页。3计算并输出下述各种算法在不同内存容量下的命中率。(1先进先出算法FIFO )(2最近最少使用算法LRU )(3最佳使用算OPT)命中率=1页面失效次数/页地址流长度本实验中，页地址流长度为320,页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。四思路关于随机数的产生办法。首先要初始化设置随机数，产生序列的开始点，例如，通 过下列语句实现：srand ( 400 ；(1计算随机数，产生 320条指令序列m = 160 ；for (i = 0； i

3、80； i+ =j = i * 4； aj = m； aj+1 = m+1 ；aj+2 = aj * 1.0 * rand( /32767 ；aj+3 = aj+2+1m= aj+3+(319-aj+3* 1.0 * rand( /32767 ；(2将指令序列变换成为页地址流for ( k = 0; kv 320; k+>pt = ak/10 ;pd= ak%10 ;(3>计算不同算法的命中率rate= 1-1.0 * U/320 ;其中U为缺页中断次数，320是页地址流长度。(4>输出格式k fifo 1ru4 0.23 0.2532 1.0 1.0五实验报告1.写出你编写

4、的C语言程序。#in clude<c oni o.h>#in clude<stdio.h>#in clude<stdlib.h>#in clude<stri ng.h>#defi ne Mypri ntf printf("|-+-+-+-+-+-+-+-+-+-+-+-+-+|n"> /*#defi ne bsize 4/#defi ne psize 16/表格控制*/ 物理块大小进程大小typedef struct pageint num 。/*记录页面号*/int time/*记录调入内存时间*/Page。/*Pag

5、e bbsize 。/*int cbsizepsize 。/*/页面逻辑结构，结构为方便算法实现设计 内存单元数*/暂保存内存当前的状态：缓冲区 */int queue100/* 记录调入队列*/int K 。/*调入队列计数变量*/in t phbbsize=0/物理块标号int propsize=0 int flagbsize = 0 int i = 0, j = 0,k = 0 int m = -1, n = -1/ 进程序列号。/进程等待次数（存放最久未被使用的进程标志。/i表示进程序列号,j表示物理块号/ 物理块空闲和进程是否相同判断标志int max = -1,maxflag =

6、0/标记替换物理块进程下标int count = 0。/统计页面缺页次数/*/*/随机产生序列号函数*int* build(>printf(”随机产生一个进程序列号为：n">。int i = 0。for(i=0。 ivpsize 。 i+>proi = 10*ra nd(>/(RAND_MAX+1>+1。prin tf("%d ”,proi>。prin tf("n">。return(pro> 。/* 物理块*查找空闲int searchpb(>for(j=0 。j<bsize 。j+>if

7、(phbj = 0>m = j。return m 。break。return -1。/*进程未*查找相同int searchpro(>for(j = 0 o j < bsize 。 j+>if(phbj = proi>n = j。return j 。return -1。*初始化内存*void empty(>for(i=0 。i<bsize 。i+>phbi=O。coun t=0。/计数器置零/*页面置换算法/*/*先进先出i+>。j+>不存在相同进程存在空闲物理块。/ 进程号填入该空闲物理块j+>不存在空闲物理块。j+>v

8、oid FIFO(>for(i = 0。 i<psize m=searchpb(> 。 n=searchpro(> 。/找flag值最大的 for(j = 0o j < bsizeif(flagj>maxflag> maxflag = flagj max = j。if(n = -1>/ if(m != -1>/phbm = proicoun t+。flagm = 0。for(j = 0。j <= mflagj+。m = -1。else/phbmax = proi。flagmax = 0。for(j = 0。j < bsizefl

9、agj+。max = -1。maxflag = 0。coun t+。else/存在相同的进程phb n = proi 。for(j = 0。 j < bsize 。 j+>flagj+ 。n = -1。for(j = 0。 j < bsize 。 j+>prin tf("%d ",phbj>。prin tf("n">。printf("缺页次数为：%dn",count> 。prin tf("n">。*/*初始化内存单元、缓冲区*/void In it(Page *b,i

10、 nt cbsizepsize>int i,j。for(i=0。 i<psize 。 i+>bi. nu m=-1。bi.time=psize-i-1。for(i=0 。 i<bsize 。 i+>for(j=0。j<psize 。j+>cij=-1。/*取得在内存中停留最久的页面，默认状态下为最早调入的页面*/int GetMax(Page *b>int i 。int max=-1 。int tag=O 。for(i=0 。 i<bsize 。 i+>if(bi.time>max> max=bi.time tag=i。r

11、eturn tag。/*判断页面是否已在内存中*/int Equati on (i nt fold,Page *b>int i 。for(i=0 。 i<bsize 。 i+>if (fold=bi. num>return ireturn -1。/*LRU核心部分*/void Lruu(i nt fold,Page *b>int i 。int val 。val=Equati on( fold,b>。if (val>=0>bval.time=0。i+>/*记录调入页面*/for(i=0。 i<bsizeif (i!=val>bi.

12、time+elsequeue+K=fold val=GetMax(b>。bval .num=fold bval.time=0。for(i=0。i<bsizeif (i!=val>bi.time+。void LRU(>int i,j。K=-1。In it(b, c>。for(i=0 。 ivpsize 。 i+>Lruu(proi,b>。c0i=proi。/*记录当前的内存单元中的页面*/for(j=0。jvbsize 。j+>cji=bj. num。/* 结果输出*/printf("内存状态为：n"> 。Mypri nt

13、f。for(j=0 。j<psize 。j+>prin tf("|%2d ",proj>。prin tf("|n">。Mypri ntf。for(i=0 。 i<bsize 。 i+> for(j=0。j<psize 。j+>if(cij=-1>prin tf("|%2c ",32>。elseprin tf("|%2d ",cij>。prin tf("|n">。Mypri ntf。printf("n调入队列为:&q

14、uot;> 。for(i=0 。 i<K+1。i+>prin tf("%3d",queuei>。prin tf("n缺 页 次 数 为 ：%6dn 缺 页率：16.6f',K+1,(float>(K+1>/psize>。主函数*void mai n(>int seidoprintf("tttttt">printf("ttt A-A 欢迎进入操作系统界面A-A ttt">printf("ttttttn">。prin tf("

15、tttttt">。prin tf("ttt虚拟内存 ttt">。prin tf("ttt ttt">。prin tf("ttt1、产生随机序列ttt">。prin tf("ttt ttt">。printf("ttt2、最久未使用(LRU>ttt">。prin tf("ttt ttt">。printf("ttt3、先进先出(FIFOttt">。prin tf("ttt ttt"

16、;>。printf("ttt4、最佳置换算法(OPT>ttt">。prin tf("ttt ttt">。prin tf("ttt5、三种算法的比较(>ttt">。prin tf("ttt ttt">。printf("ttt0、退出(Exitttt">。prin tf("ttttttn">。printf(”请选择所要执行的操作(0/1/2/3/4/5>:">。scan f("%d",

17、 &sel>。switch(sel>case0:printf("tttA-A再见！ a_a tttn">。 system("pause"> 。break 。case 1:build(> 。 break。case 2:printf("最久未使用算 n"> 。 LRU(>。empty(>。 printf("n">。break。case 3:printf("先进先出算 n"> 。 FIFO(>。 empty(>。 prin

18、tf("n">。break。case 5:printf("先进先出算法 n"> 。 FIFO(>。 empty(>。printf("最久未使用算法 n"> 。 LRU(>。empty(>。 break。default: printf("请输入正确的选项号！">。printf("nn">。break。while(sel!=O>产生的随机序列：«'II » I I I J !U J ! I I y B I I随机

19、产生二个进程序列号为:162965499S29B641最近最少使用算法执行结果如下:作 一 6 操 -; 的 一 ? 虐+-， aw k 2 要用为1 I 所使态一 6 俘乘L ; 霎帝一 1 清氏I8 I 6 ! 4 ： 18 264 ! 9 I 9 ： 9 5 9 : 9为为 籟: 队枕率 入页页先进先出FIFO算法执行结果:2 总结体会请求页式存储管理的实现原理。请求页式管理的基本原理是将逻辑地址空间分成大小相同的页，将存储地址空间分 块，页和块的大小相等，通过页表进行管理。页式系统的逻辑地址分为页号和页内位移 量。页表包括页号和块号数据项，它们一一对应。根据逻辑空间的页号，查找页表对应

20、项 找到对应的块号，块号乘以块长，加上位移量就行成存储空间的物理地址。每个作业的逻 辑地址空间是连续的，重定位到内存空间后就不一定连续了。3.写出这三种页面置换算法的实现思想。FIFO算法总是淘汰最先调入主存的页面，即淘汰在主存中驻留时间最长的页面，认为 驻留时间最长的页不再使用的可能性较大。LRU算法淘汰的页面是最近一段时间内最久未被访问的那一页，它是基于程序局部性 原理来考虑的，认为那些刚被使用过的页面可能还要立即被使用，而那些在较长时间内未 被使用的页面可能不会立即使用。OPT算法，当要调入一页而必须淘汰旧页时，应该淘汰以后不再访问的页，或距现在 最长时间后要访问的页面。4对不同算法的性

21、能进行评价。FIFO算法较易实现，对具有线性顺序特征的程序比较适用，而对具有其他特征的程序 则效率不高，此算法还可能出现抖动现象<Belady）异常。LRU算法基于程序的局部性原理，所以适用用大多数程序，此算实现必须维护一个特殊的队列一一页面淘汰队列。OPT算法虽然产生的缺页数最少，然而，却需要预测程序的页面引用串，这是无法预知的，不 可能对程序的运行过程做出精确的断言，不过此理论算法可用做衡量各种具体算法的标 准。Whe n you are old and grey and full of sleep, And nodding by the fire, take dow n this

22、book, And slowly read, and dream of the soft look Your eyes had on ce, and of their shadows deep; How many loved your mome nts of glad grace, And loved your beauty with love false or true, But one man loved the pilgrim soul in you, And loved the sorrows of your cha nging face;And bending dow n beside the glow ing bars, Murmur, a little sadly