操作系统-请求页式存储管理实验报告.doc

1、操作系统 - 请求页式存储管理实验报告1111. 实验目的存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本实验的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。2. 实验内容(1) 通过随机数产生一个指令序列，共 320 条指令指令的地址按下述原则生成：a) 50% 的指令是顺序执行的；b) 25% 的指令是均匀分布在前地址部分；c) 25% 的指令是均匀分布在后地址部分；具体的实施方法是：1a) 在0，319的指令地址之间随机选取一起点 m；b) 顺序执行一条指令，即执行地址为 m+1 的指令；

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

3、310 条第 319 条指令为第 31 页（对应虚存地址为310，319）。按以上方式，用户指令可以组成32 页。2(3) 计算并输出下述各种算法在不同内存容量下的命中率a) 先进先出的算法（ FIFO ）；b) 最近最少使用算法（ LRU ）；c) 最佳淘汰算法（ OPT ）；3命中率 =1-页面失效次数 /页地址流长度在本实验中，页地址流长度为 320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。3. 随机数产生办法关于随机数产生办法，可以采用操作系统提供的函数，如 Linux 或 UNIX 系统提供函数 srand()和 rand()，分别进行初始化和产生随机数。例

4、如：srand();语句可以初始化一个随机数；a0=10*rand()/32767*319+1;a1=10*rand()/32767*a0;语句可以用来产生a0与 a1中的随机数。环境说明此实验采用的是Win7 下 Code:blocks 10.05编译器编程。此 word 实验文档中采用 notepad+的语法高亮。44. 程序设计说明4.1.全局变量constintmaxn= 320;/ 序列个数constintmax= maxn+20 ; /数组大小constintmaxp= max/10; /最大页数intinst max ;/指令序列intpage max ;/页地址流intsize

5、;/内存能容纳的页数boolin maxp ;/该页是否在内存里，提高效率intpin maxp ;/现在在内存里的页其中 in数组是为了方便直接判断该页是否在内存里，而不用遍历内存里所有页来判断。fault_n 用来记录缺页次数。4.2.随机指令序列的产生按照实验要求的写了，但是由于没有考虑细节，开始时出了点问题。（1） 当 m=319 时，我们顺序执行 m+1 会产生第 32 页的页地址，从而使页地址没能按要求限制在 0, 31之间。解决方法：采用循环模加来避免超出范围。（ 2） 但是这样之后有可能出现模 0 的问题。所以我索性将等于 0 的模数都赋值为 160.最后的程序如下。voidp

6、roduce_inst()5intm , n ;intnum=0 ;while( num maxn )m= rand()% maxn;inst num+=( m+ 1)% maxn ;if( num= maxn)break;m= ( m+ 2 )% maxn;if( m =0)m =160 ;n= rand()% m ;inst num+=( n + 1)% maxn ;if( num= maxn)break;n= ( n+ 2 )% maxn;m= maxn-n ;if( m =0)m =160 ;m= rand()% m+ n ;inst num+= m ;4.3.FIFO 算法定义变量

7、ptr。一开始先预调页填满内存。在这一部分， ptr 指向下一个要存放的位置。之后继续执行剩下的指令。此时， ptr 表示队列最前面的位置，即最先进来的位置，也就是下一个要被替换的位置。ptr 用循环加，即模拟循环队列。4.4.LRU算法定义数组 ltu,即 last_time_use来记录该页最近被使6用的时间。定义变量 ti模拟时间的变化，每执行一次加一。这个算法，我没有预调页，而是直接执行所有指令。若当前需要的页没在内存里， 就寻找最近最少使用的页，也就是 ltu 最小的页，即最近一次使用时间离现在最久的页，然后替换掉它。或者在内存还未满时，直接写入，这个我以初始化内存里所有页为-1 来

8、实现。若已经在内存里了，则只遍历内存内的页，把当前页的最近使用时间改一下即可。4.5.OPT算法定义数组 ntu, 即 next_time_use来记录下一次被使用的时间，即将来最快使用时间。初始化为 -1.开始时预调页填满内存里的页。 同样利用变量 ptr 来表示下一个要存放的位置从而控制预调页的过程。接着初始化 ntu 数组为 -1。然后求出每一页下一次被使用的指令号，以此代替使用时间。如果所有剩下的序列都没有用该页时，则还是 -1.这种值为 -1 的页显然是最佳替换对象。然后执行所有剩下的指令。当该页不在内存里时，遍历ntu 数组，遇到 -1 的直接使用该页，没有则用ntu值最大的，也就

9、是最晚使用的。7无论该页在不在内存里，因为这一次已经被使用了，所以都应该更新这个页的 ntu，只需往前看要执行的页流，记录下第一个遇到的该页即可。如果没有找到同样添 -1 即可。5. 编程实现（ 源程序 ）：#include #include #include #include usingnamespacestd;constintmaxn=320 ;/序列个数constintmax= maxn + 20 ; /数组大小constintmaxp= max / 10 ;/最大页数intinst max ;/指令序列intpage max ;/页地址流intsize;/内存能容纳的页数boolin

10、maxp ;/该页是否在内存里，提高效率intpin maxp ;/现在在内存里的页voidwelcome ()printf( *n);printf( *By schneeOn2011-12-06*n);printf( *班级 :09211311班内序号： 30*n);printf( *nn);voidinput_hint()printf( n1-create new instruction sequence 2-set memory page number(4 to32)n);printf( 3-solve by FIFO algorithm4-solve by LRU algorithmn

11、);printf( 5-solve by OPT algorithm0-exitn);printf( *Please input Your choice: );8/* 通过随机数产生一个指令序列，共320 条指令 */void produce_inst()intm ,n ;intnum=0 ;while( num maxn )m= rand()% maxn;inst num+=( m+ 1)% maxn ;if( num= maxn)break;m=( m+ 2 ) % maxn;if( m =0)m =160 ;n= rand()% m ;inst num+=( n + 1)% maxn ;

12、if( num= maxn)break;n=( n+ 2 ) % maxn;m= maxn-n ;if( m =0)m =160 ;m= rand()% m+ n ;inst num+= m ;/* 将指令序列变换成为页地址流*/voidturn_page_address()for( inti= 0 ; imaxn ; i+)page i = inst i /10 ;voidFIFO_solve()memset( in ,false,sizeof( in );intfault_n=0; /缺页率intptr, i;/ 预调页填满空间ptr=0 ;/下一个要放的位置for( i =0 ; i m

13、axn& ptrsize; i+)if(! in page i )pin ptr+= page i ;in page i =true;9fault_n+;/ 继续执行剩下的指令ptr=0 ; /队列里最先进来的位置，即下一个要被替换的位置for(;i maxn ; i+)if(! in page i )in pin ptr=false;in page i =true;pin ptr= page i ;fault_n+;ptr=( ptr+ 1 )% size;printf( nBy FIFO algorithm, the fault-page number is: %dn, fault_n);

14、printf( the hit ratio is : %.2lfn,( 1 -( fault_n+0.0 )/320.0);voidLRU_solve()intltu maxp ;/last_time_useintti=1 ;/模拟时间intfault_n=0;memset( ltu,0 ,sizeof( ltu);memset( in ,false,sizeof( in );memset( pin ,- 1 ,sizeof( pin );intmin, ptr, i, j;for( i =0 ; i maxn ; i+)if(! in page i )/寻找 lrumin=1000000;

15、ptr= 0 ;for( j = 0; j size; j+)if( ltu j min)min= ltu j ;ptr= j;/ 替换或写入if( pin ptr!=- 1 )in pin ptr=false;10in page i=true;pin ptr= page i;fault_n+;ltu ptr= ti+;else/已经在内存里则只需更改最近使用时间for( j = 0; j size; j+)if( pin j = page i )ltu j = ti+;break;printf( nBy LRU algorithm, the fault-page number is: %dn

16、, fault_n);printf( the hit ratio is : %.2lfn,( 1 -( fault_n+0.0 )/320.0);voidOPT_solve()intntu maxp ;/next_time_useintfault_n=0;inti, j;memset( in ,false,sizeof( in );memset( ntu ,- 1 ,sizeof( ntu );/ 预调页填满intptr=0 ;for( i =0 ; i maxn& fault_n size; i+)if(! in page i )in page i =true;pin ptr= page i

17、 ;fault_n+;ptr+;/ 初始化 ntu 数组ptr=0 ;for( j =i ; j maxn& ptr32 ; j+)if( ntu page j =- 1)11ntu page j = j;ptr+;intmax ;for(;i maxn ; i+)if(! in page i )max=0; ptr=0 ;for( j = 0; j max )max= ntu pin j ;ptr= j;in pin ptr=false;in page i =true;pin ptr= page i ;fault_n+;ntu page i =- 1 ;for( j =i + 1; j ma

18、xn ; j+)if( page j = page i )ntu page i = j;break;printf( nBy OPT algorithm, the fault-page number is: %dn, fault_n);printf( the hit ratio is : %.2lfn,( 1 -( fault_n+0.0 )/320.0);intmain()12srand( time( NULL );welcome();intchoice;while( 1 )input_hint();scanf( %d ,&choice);printf( n);if( choice=0 )printf( BYE-BYE!n);break;if( choice=1 )produce_inst();turn_page_address();printf( New page address sequence is set OK!n);elseif( choice=2 )printf( Please i