《操作系统FIFO算法简化版.doc》由会员分享，可在线阅读，更多相关《操作系统FIFO算法简化版.doc（12页珍藏版）》请在三一文库上搜索。
1、操作系统 (2014 年秋季学期 )序号：实验报告系别：计算机学院班级：姓名：学号：实验名称：存储管理总成绩：评语：日期：操作系统实验报告实验名称存储管理实验序号2实验日期2014.12.25实验人一、实验目的、要求与环境1目的：（1）通过编写程序实现请求分页存储管理的 Optimal 、FIFO、LRU等页面置换算法中的一种，掌握虚拟存储管理中有关缺页处理方法等内容，巩固有关虚拟存储管理的教学内容。（ 2）理解内存分配原理，特别是以页面为单位的虚拟内存分配方法2. 要求：在 Windows XP、 Windows 2000 、 Win7、 Linux 等操作系统下，使用的VC、VB、 jav
2、a 或 C 等编程语言，实现请求分页存储管理的一种页面置换算法。3. 环境：1. 硬件设备： PC机一台2.软件环境：安装Windows 操作系统或者Linux操作系统，并安装相关的程序开发环境，如CC+Java等编程语言环境。二、相关背景知识关于操作系统的内存管理，如何节省利用容量不大的内存为最多的进程提供资源，一直是研究的重要方向。而内存的虚拟存储管理，是现在最通用，最成功的方式在内存有限的情况下，扩展一部分外存作为虚拟内存，真正的内存只存储当前运行时所用得到信息。这无疑极大地扩充了内存的功能，极大地提高了计算机的并发度。虚拟页式存储管理，则是将进程所需空间划分为多个页面，内存中只存放当前
3、所需页面，其余页面放入外存的管理方式。常用的页面置换算法有OPT、FIFO、LRU、Clock 、LFU、PBA等。这里重点介绍FIFO、OPT、 LRU（ 1）先进先出页面置换算法（FIFO）FIFO 算法这是最早出现的置换算法，该算法总是淘汰最先进入内存的页面，即选择在内存中驻时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。（ 2）最佳
4、置换算法（OPT）它是由 Belady 于 1966 年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长 ( 未来 ) 时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用此算法来评价其它算法。（ 3）最近最久未使用置换算法（LRU）最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU 置换算法是选择最近最久
5、未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t, ，当须淘汰一个页面时，选择现有页面中其t 值最大的， 即最近最久未使用的页面予以淘汰。三、实验设计说明选择置换算法，先输入所有页面号，为系统分配物理块，依次进行置换：FIFO 基本思想：是用队列存储内存中的页面，队列的特点是先进先出，与该算法是一致的，所以每当发生缺页时，就从队头删除一页，而从队尾加入缺页。或者借助辅助数组timemSIZE 记录物理块中对应页面的进入时间，每次需要置换时换出进入时间最小的页面。物理块数： mSize 页面引用个数：pSize ，全局静态变量物理块中的页号，页
6、面引用串和辅助数组并进行相关的初始化。打印函数print（），核心函数FIFO（）。缺页率访问缺页次数/ 访问总次数。四、实验设计的流程图实验流程图：开始FIFO 算法打印输出初始化设置输入分配物理块，页面Y选择操作N结束FIFO 模块流程图：新的指令页面内存内页面 time+1在物理块中？YNN内存内页面time+1载入新页面 time=0内存物理块满？Y选择 time 最大页面换出四、程序代码#include#include/*全局变量 */intmSIZE;/* 物理块数 */intpSIZE;/* 页面号引用串个数 */staticintmemery10=0;/* 物理块中的页号 */
7、staticintpage100=0;/* 页面号引用串 */staticinttemp10010=0;voidFIFO();/* 置换算法函数 */voidprint(unsigned int t);voiddesignBy();/* 主函数 */void main()inti,k,code;system( color 0A);designBy();printf( 欢迎使用 , 请按任意键进行初始化操作.n);/printf( );getchar();system( cls );system( color 0A);printf( 请输入物理块的个数(M=10)： );scanf_s( %d,
8、&mSIZE);printf( 请输入页面号引用串的个数(P=100) ： );scanf_s( %d,&pSIZE);puts( 请依次输入页面号引用串： );for (i=0;ipSIZE;i+)scanf_s(%1d,&pagei);system( cls );system( color 0A);doputs( 输入的页面号引用串为： );for (k=0;k=(pSIZE-1)/20;k+)for (i=20*k;(ipSIZE)&(i);getchar();system( cls); while (code!=2); getchar();/ 显示设计者信息void designBy(
9、)printf( n );printf( 实验：页面置换算法 n );printf(printf(printf(班级：信安 12姓名： n ); n );n );void print(unsignedintt )inti,j,k,l;intflag;for (k=0;k=(pSIZE-1)/20;k+)for (i=20*k;(ipSIZE)&(i20*(k+1);i+)if (i+1)%20=0)|(i+1)%20)&(i=pSIZE-1)printf(%dn ,pagei);elseprintf(%d,pagei);for (j=0;jmSIZE;j+)for (i=20*k;(imSIZ
10、E+20*k)&(i=j)printf( |%d|,tempij);elseprintf( |0|);for (i=mSIZE+20*k;(ipSIZE)&(i20*(k+1);i+)for (flag=0,l=0;lmSIZE;l+)if (tempil=tempi-1l)flag+;if (flag=mSIZE) /* 页面在物理块中 */printf(| |);elseprintf( |%d|,tempij);/* 每行显示 20个*/if (i%20=0)continue ;printf(n );printf(printf(printf(printf(-n 缺页次数： %dtt, t
11、+mSIZE); 缺页率： %d/%dn, t +mSIZE,pSIZE); 置换次数： %dtt, t ););printf(n-n);/* 先进先出页面置换算法*/void FIFO()intmemery10=0;inttime10=0;/* 记录进入物理块的时间inti,j,k,m;intmax=0;/* 记录换出页 */intcount=0;/* 记录置换次数 */for (i=0;imSIZE;i+)/* 前 mSIZE个数直接放入*/*/memeryi=pagei;timei=i;for (j=0;jmSIZE;j+)tempij=memeryj;for (i=mSIZE;ipSI
12、ZE;i+)/* 判断新页面号是否在物理块中*/for (j=0,k=0;jmSIZE;j+)if (memeryj!=pagei)k+;if (k=mSIZE) /* 如果不在物理块中 */count+;/* 计算换出页 */max=time0time1?0:1;for (m=2;mmSIZE;m+)if (timemtimemax)max=m;memerymax=pagei;timemax=i;/* 记录该页进入物理块的时间*/for (j=0;jmSIZE;j+)tempij=memeryj;elsefor (j=0;jmSIZE;j+)tempij=memeryj;print(count);五、编译过程截图实验中使用 visual studio 2013六、测试用例1. 演示示例：算法名内存块数访问顺序FIFO4123456785341六、实验结果1、FIFO四个内存块，十二个引用串个数：进行 FIFO 运算：