页面置换算法地实验报告材料

1、实用标准操作系统课程设计报告院（系）：衡阳师范学院专业：计算机科学与技术姓名 :陈建元齐欢班级：1103 班学号 :11190301 11190316题目：页面置换算法指导教师 :王玉奇2013年 12月 10日至 12月 28日文档大全实用标准目录摘要3第一章设计任务和需求41.1 课程设计任务41.2 课程设计需求4第二章概要设计42.1 系统分析42.2 调页策略5何时调入页面5请求调页策略5从何处调入页面52.3 模块设计6第三章详细设计73.1 系统设计73.2 算法思想及流程图7主程序流程图7先进先出 (FIFO) 页面置换算法8最佳页面置换置换算法（OPT）9最近最久未使用页面置

2、换算法（LRU ）10第四章源程序结构分析114.1 程序结构114.2 源代码分析11第五章调试16第六章体会与自我评价18第七章参考文献19文档大全实用标准摘要操作系统（英语；Operating System，简称 OS）是一管理电脑硬件与软件资源的程序，同时也是计算机系统的内核与基石。操作系统身负诸如管理与配置内存、决定系统资源供需的优先次序、 控制输入与输出设备、 操作网络与管理文件系统等基本事务。操作系统是管理计算机系统的全部硬件资源包括软件资源及数据资源;控制程序运行 ;改善人机界面 ;为其它应用软件提供支持等，使计算机系统所有资源最大限度地发挥作用，为用户提供方便的、有效的、友善

3、的服务界面。操作系统是一个庞大的管理控制程序，大致包括 5个方面的管理功能 :进程与处理机管理、作业管理、存储管理、设备管理、文件管理。在地址映射过程中， 若在页面中发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法（ Page-Replacement Algorithms ）。关键词 ：操作系统； OPT 页面置换算法； FIFO 先进先出的算法； LRU 最近最久未使用夜面置换算法文档大全实用标准第一章设计任务和需求1.1 课程设计任务深入掌握内存调度算法的概念原

4、理和实现方法。编写程序实现：（ 1） 先进先出页面置换算法（ FIFO）（ 2） 最近最久未使用页面置换算法（ LRU ）（ 3） 最佳置换页面置换算法（ OPT）设计一个虚拟存储区和内存工作区，编程序演示以上三种算法的具体实现过程，并计算访问命中率。演示页面置换的三种算法。通过随机数产生一个指令序列，将指令序列转换成为页地址流。计算并输出各种算法在不同内存容量下的缺页率。1.2 课程设计需求在各种存储器管理方式中， 有一个共同的特点， 即它们都要求将一个作业全部装入内存方能运行，但是有两种情况： （ 1） 有的作业很大，不能全部装入内存，致使作业无法运行； （2） 有大量作业要求运行，但内存

5、容量不足以容纳所有这些作业。 而虚拟内存技术正式从逻辑上扩充内存容量， 将会解决以上两个问题。 从内存中调出一页程序或数据送磁盘的对换区中，通常，把选择换出的页面的算法称为页面置换算法（ Page-Replacement Algorithms）。进而页面置换算法程序能客观的将其工作原理展现在我们面前。第二章概要设计2.1 系统分析由于分区式管理尽管实现方式较为简单， 但存在着严重的碎片问题使得内存的利用率不高。再者， 分区式管理时， 由于各作业或进程对应于不同的分区以及在分区内各作业或进程连续存放， 进程的大小或内存可用空间的限制。 而且分区式管理也不利于程序段和数据段的共享。 页式管理正是为

6、了减少碎片以及为了只在内存存放那些反复执行或即将执行的程序段与数据部分， 而把那些不经常执行文档大全实用标准的程序段和数据存放于外存待执行时调入， 以提高内存利用率而提出来的页式管理有动态页式管理和静态页式管理之分， 动态页式管理是在静态页式管理的基础上发展起来的。 请求页式管理属于动态页式管理中的一种， 它的地址变换过程与静态页式管理时的相同， 也是通过页表查出相应的页面号， 由页面号与页内相对地址相加而得到实际物理地址。 有关的地址变换部分是由硬件自动完成的。 当硬件变换机构发现所要求的页不在内存时， 产生缺页中断信号， 由中断处理程序做出相应的处理。 中断处理程序是由软件实现的。 除了在

7、没有空闲页面时要按照置换算法选择出被淘汰页面之外， 还要从外存读入所需要的虚页。 这个过程要启动相应的外存和涉及到文件系统。因此， 请求页式管理是一个十分复杂的过程， 内存利用率的提高是以牺牲系统开销的代价换来的。 这里用到了置换算法。 它是在内存中没有空闲页面时被调用。 目的是选出一个被淘汰的页面。 如果内存中有足够的空闲页面存放所调入的页， 则不必使用置换算法。 把内存和外存统一管理的真正目的是把那些被访问概率非常高的页存放在内存中。 因此，置换算法应该置换那些被访问概率低的页，将它们移出内存。2.2 调页策略何时调入页面如果进程的许多页是存放在外存的一个连续区域中， 则一次调入若干个相邻

8、的页，会比一次调入一页的效率更高效一些。 但如果调入的一批页面中的大多数都未被访问，则又是低效的。 可采用一种以预测为基础的预调页策略， 将那些预计在不久之后便会被访问的页面，预先调入内存。如果预测较准确，那么，这种策略显然是很有吸引力的。但目前预调页的成功率仅为 50%。且这种策略主要用于进程的首次调入时，由程序员指出应该先调入哪些页。请求调页策略当进程在运行中需要访问某部分程序和数据时， 若发现其所在的页面不在内存，便即提出请求，由 OS将其所需页面调入内存。由请示调页策略所确定调入的页，是一定会被访问的， 再加之请求调页策略比较易于实现， 故在目前的虚拟存储器中，大多采用此策略。 但这种

9、策略每次仅调入一页， 故须花费较大的系统开销，增加了磁盘 I/O 的启用频率。从何处调入页面文档大全实用标准在请求分页系统中的外存分为两部分： 用于存放文件的文件区和用于存放对换页面的对换区。通常， 由于对换区是采用连续分配方式， 而事件是采用离散分配方式，故对换区的磁盘 I/O 速度比文件区的高。这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况：系统拥有足够的对换区空间， 这时可以全部从对换区调入 所需页面，以提高调页速度。为此，在进程运行前，便须将与该进程有关的文件，从文件区拷贝到对换区。系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换

10、出这些页面时，由于它们未被修改而不必再将它们换出时，以后需要时，再从对换区调入。 UNIX 方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。由于 UNIX系统允许页面共享，因此，某进程所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调入。2.3 模块设计运行程序页面置换算法的主界面输入页面序列和物理块数OLFPRIFTUO缺页次数和缺页率文档大全实用标准第三章详细设计3.1 系统设计在进程运行过程中， 若其所要访问的页面不在内存而需把它们调入内存， 但内存已无空

11、闲空间时， 为了保证该进程能正常运行， 系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪 个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法 (Page_Replacement Algorithms)。 一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲， 应将那些以后不再会访问的页面换出， 或将那些在较长时间内不会再访问的页面调出。3.2 算法思想及流程图主程序流程图如图（ 3 2 1）所示开始输入页面序列输入物理块数调用各种置换算法，OPT ，LRU ，FIFO 页面置换算法计算缺页次数和缺页率结束主流程图（图 3 2 1）文档大全实用标准

12、先进先出 (FIFO)页面置换算法算法的基本思想：这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序存入一个时间数组，并将其中时间值最大的页面进行淘汰，并替换入新的页面就可以实现。算法流程图：如图（ 3 2 2）所示入口初始化数据i 指向下一个页面Y页面是否存在N输出当前页 ,i+Y物理块是否有空闲N将页面放到空选择最先进入的页面闲的物理块处作为淘汰页Yi< 页面长度N计算缺页率， 并输出数据结束FIFO 置换算法（图 322）文档大全实用标准最佳页面置换置换算法（OPT）算法的基本

13、思想：其所选择的被淘汰页面，将是永不使用的，或者是在最长时间内不再被访问的页面。 可保证获得最低的缺页率。 但由于人们目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法也是无法实现的。但是可利用该算法去评价其它算法。算法流程图：如图（ 3 2 3）所示入口初始化数据i 指向下一个页面Y页面是否存在N输出当前页 ,Y物理块是否有空闲Ni+将页面放到空闲的选择以后最长时间内（未来）物理块处不在被访问的页面作为淘汰页i< 页面长度YN计算缺页率， 并输出数据结束文档大全实用标准OPT页面置换算法（图3 2 3）最近最久未使用页面置换算法LRU算法的基

14、本思想： 当需要淘汰某一页时， 选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。该算法的主要出发点是，如果某页被访问了， 则它可能马上还被访问。 或者反过来说，如果某页很长时间未被访问，则它在最近一段时间不会被访问。算法流程图：如图（ 3 2 4）所示入口初始化数据i 指向下一个页面Y页面是否存在N输出当前页 ,i+Y物理块是否有空闲N将页面放到空选择最近最久未使用闲的物理块处的页面作为淘汰页Yi< 页面长度N计算缺页率，并输出数据结束LRU页面置换算法（图324）文档大全实用标准第四章源程序结构分析4.1 程序结构Input(int m,Pro pL)/打印页面走向状态sran

15、d(j);/ 以时钟时间 j 为种子，初始化随机数发生器void print(Pro *page1)/ 打印当前的页面int Search(int e,Pro *page1 )/ 寻找内存块中与 e 相同的块号 int Max(Pro *page1)/ 寻找最近最长未使用的页面int Count(Pro *page1,int i,int t,Pro pL)/记录当前内存块中页面离下次使用间隔长度4.2 源代码分析#include<iostream.h>#include <stdlib.h>#include <time.h>#include <stdio

16、.h>#define L 20/ 页面长度最大为20int M; / 内存块struct Pro/ 定义一个结构体int num,time;Input(int m,Pro pL)/打印页面走向状态cout<<" 请输入页面长度(10 20)： "docin>>m;if(m>20|m<10)cout<<endl;cout<<" 页面长度必须在1020 之间 "<<endl<<endl;cout<<" 请重新输入L ： "else bre

17、ak;while(1);int i,j;j=time(NULL);/取时钟时间srand(j);/ 以时钟时间j 为种子，初始化随机数发生器cout<<endl;cout<<" 输出随机数 : "<<endl;cout<<endl;for(i=0;i<m;i+)pi.num=rand( )%10;/ 产生 0 到 9 之间的随机数放到数组p 中文档大全实用标准pi.time=0;cout<<pi.num<<" "cout<<endl<<endl;retu

18、rn m;void print(Pro *page1)/ 打印当前的页面Pro *page=new ProM;page=page1;for(int i=0;i<M;i+)cout<<pagei.num<<" "cout<<endl;int Search(int e,Pro *page1 )/ 寻找内存块中与e 相同的块号Pro *page=new ProM;page=page1;for(int i=0;i<M;i+)if(e=pagei.num)return i;/返回 i 值return -1;int Max(Pro *pa

19、ge1)/ 寻找最近最长未使用的页面Pro *page=new ProM;page=page1;int e=page0.time,i=0;while(i<M) / 找出离现在时间最长的页面if(e<pagei.time)e=pagei.time;i+;for( i=0;i<M;i+)if(e=pagei.time)return i;/ 找到离现在时间最长的页面返回其块号 return -1;int Count(Pro *page1,int i,int t,Pro pL)/记录当前内存块中页面离下次使用间隔长度Pro *page=new ProM;page=page1;int

20、count=0;for(int j=i;j<L;j+)if(paget.num=pj.num )break;/ 当前页面再次被访问时循环结束 else count+;/ 否则 count+1return count;/ 返回 count 的值文档大全实用标准int main()int c;int m=0,t=0;float n=0;Pro pL;m=Input(m,p);/ 调用 input 函数，返回m 值cout<<" 请输入分配的物理块m(2 6): "cout<<endl<<endl;docin>>M;if(M&

21、gt;6|M<2)cout<<endl;cout<<" 物理块 m 必须在 2 6 之间 "<<endl<<endl;cout<<" 请重新输入m： "else break;while(1);Pro *page=new ProM;dofor(int i=0;i<M;i+)/初始化页面基本情况 pagei.num=0;pagei.time=m-1-i;i=0;cout<<endl;cout<<"1:FIFO 页面置换 "<<end

22、l<<endl;cout<<"2:LRU页面置换 "<<endl<<endl;cout<<"3:OPT 页面置换 "<<endl<<endl;cout<<" 请选择页面置换算法："<<endl<<endl;cin>>c;system("cls");if(c=1)/FIFO页面置换n=0;cout<<" FIFO 算法页面置换情况如下: "<<

23、endl;cout<<endl;while(i<m)if(Search(pi.num,page)>=0) / 当前页面在内存中cout<<pi.num<<" " /输出当前页pi.numcout<<" 不缺页 "<<endl;i+; /i 加 1else /当前页不在内存中文档大全实用标准if(t=M)t=0;elsen+; / 缺页次数加1paget.num=pi.num; / 把当前页面放入内存中cout<<pi.num<<" "pri

24、nt(page); / 打印当前页面t+; / 下一个内存块i+; / 指向下一个页面cout<<endl;cout<<" 缺页次数： "<<n<<"缺页率： "<<n/m<<endl<<endl;if(c=2)/LRU页面置换n=0;cout<<" LRU算法页面置换情况如下: "<<endl;cout<<endl;while(i<m)int a;t=Search(pi.num,page);if(t>=

25、0)/ 如果已在内存块中paget.time=0;/ 把与它相同的内存块的时间置0for(a=0;a<M;a+)if(a!=t)pagea.time+;/其它的时间加1cout<<pi.num<<" "cout<<" 不缺页 "<<endl;else /如果不在内存块中n+; / 缺页次数加1t=Max(page); / 返回最近最久未使用的块号赋值给tpaget.num=pi.num; / 进行替换paget.time=0; / 替换后时间置为0cout<<pi.num<<&

26、quot; "print(page);for(a=0;a<M;a+)if(a!=t)pagea.time+; / 其它的时间加1i+;cout<<endl;文档大全实用标准cout<<" 缺页次数： "<<n<<"缺页率： "<<n/m<<endl<<endl;if(c=3)/OPT页面置换n=0;cout<<" OPT 算法置换情况如下:"<<endl;cout<<endl;while(i<m

27、)if(Search(pi.num,page)>=0)/ 如果已在内存块中cout<<pi.num<<" "cout<<" 不缺页 "<<endl;i+;else/如果不在内存块中int a=0;for(t=0;t<M;t+)if(paget.num=0)a+;/记录空的内存块数if(a!=0) / 有空内存int q=M;for(t=0;t<M;t+)if(paget.num=0&&q>t)q=t;/ 把空内存块中块号最小的找出来 pageq.num=pi.num;

28、n+;cout<<pi.num<<" "print(page);i+;elseint temp=0,s;for(t=0;t<M;t+)/寻找内存块中下次使用离现在最久的页面if(temp<Count(page,i,t,p)temp=Count(page,i,t,p);s=t; / 把找到的块号赋给spages.num=pi.num;n+;cout<<pi.num<<" "print(page);i+;文档大全实用标准cout<<endl;cout<<" 缺页次数

29、： "<<n<<"缺页率： "<<n/m<<endl<<endl;while(c=1|c=2|c=3);return 0;第五章调试程序在运行的情况下，进入主界面输入菜单，如图（41）所示：页面长度：输入16，分配的物理块：输入4，主界面（图 41）选 1，进入 FIFO 算法页面置换，如图（ 42）所示文档大全实用标准FIFO 算法置换（图4 2）选 2，进入 LRU 算法页面置换，如图（ 43）所示LRU 算法置换（图 43）选 3，进入 OPT 算法页面置换，如图（ 4 4）所示文档大全实用标准OPT 算法置换（图4 4）第