logo资料库

页面淘汰算法实验报告.doc

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：1.08M 资料格式：doc 举报 版权申诉
第1页 / 共33页
第2页 / 共33页
第3页 / 共33页
第4页 / 共33页
第5页 / 共33页
第6页 / 共33页
第7页 / 共33页
第8页 / 共33页
资料共33页，剩余部分请下载后查看
    操作系统实验报告 课题：页面淘汰算法 专 业： 班 级： 学 号： 姓 名： 年 月 日
    目 录 一 实验目的 …………………………………………………… 错 误！未定义书签。 二 实验要求 ……………………………………………………3 三 背景知识 ……………………………………………………3 四 总体设计 ……………………………………………………4 五 详细设计 …………………………………………………… 错 误！未定义书签。 六 运行结果分析 ………………………………………………9 七 心得体会 ………………………………………………………13 八 参考文献 ………………………………………………………14 附：源代码 ………………………………………………………15
    一、实验目的 本实验主要对操作系统中请求分页式内存管理及其应用的一些关键算法进 行模拟。学生通过设计与实现Clock算法，能够加强对相应理论的理解，并对了 解操作系统内部的基本处理原理与过程也有很多益处。利用简单的数据结构，模 拟实现操作系统中的页面置换机制，通过写程序模拟实现上述三种内存页面置换 算法，使学生进一步掌握内存页面置换的方法。对操作系统中内存的管理有一个 实践上的认识。 1、用 C 语言编写 OPT、FIFO、LRU 三种置换算法。 2、熟悉内存分页管理策略。 3、了解页面置换的算法。 4、掌握一般常用的调度算法。 5、根据方案使算法得以模拟实现。 6、锻炼知识的运用能力和实践能力。 二、实验要求  设计随机页面序号产生程序，并说明随机的性能和其性能可能对算法的 影响  编写页面淘汰算法(FIFO、OPT、LRU)  结果数据的显示或提取  结果数据的分析 几点说明：  设计并绘制算法流程，附加说明所需的数据结构  如何标记时间的先后、最久的将来、最久未被使用  描述Clock算法的基本原理、必要的数据结构、算法执行流程图、编码实 现。 1）初始化：输入作业可占用的总页框数，初始化置空。 2）输入请求序列：输入一个作业页号访问请求序列，依次占用相应页框，直 至全部占用； 3）Clock 算法：当页框全部占用后，对于后续新的页号访问请求，执行 Clock 算法，淘汰 1 个页面后装入新的页号。 4）显示当前分配淘汰序列：显示淘汰的页号序列。 三、背景知识：
    在操作系统当中，在进程运行过程中，若其访问的页面不在内存中而需把他 们调入内存，但内存已无空闲空间时，为了保证该进程能够正常的运行，系 统必须从内存中调出一页程序或数据送到磁盘的兑换区中，但是应该是哪个 页面被调出，需根据一定的算法来确定。通常，我们把这一类的算法称为“页 面置换算法”，页面置换算法执行效率的高低，往往直接影响到操作系统的 性能。 内存页面置换算法： 1、 <1> 先进先出调度算法（FIFO） 先进先出调度算法根据页面进入内存的时间先后选择淘汰页面。本算法实 现时需要将页面按进入内存的时间先后组成一个队列，每次置换掉最早进入的页 面。这是最早出现的置换算法，该算法总是淘汰最先进入内存的页面，即选择在 内存中驻留时间最长的页面换出，予以淘汰。 该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一 个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法 与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如， 含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘 汰。 <2>最近最久未使用的置换算法（LRU） 最近最久未使用的置换算法，是根据页面调入内存后的使用情况进行决 策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最 近的将来”的近似，因此，LRU 置换算法是选择最近最久未使用的页面予以淘汰。 该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历 的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未 使用的页面予以淘汰。 <3> 最佳置换算法（OPT） 最佳置换算法是可以说的一种理想的页面置换算法，它是由Belady于1966 年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许 是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得 最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一 个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用 此算法来评价其它算法。 <4>时钟页面置换算法
    时钟页面置换算法是把所有的页面都保存在一个类似钟面的环形链表中，一个表 针指向最老的页面，如图所示。 当发生缺页中断时，算法首先检查表针指向的页面，如果它的 R 位是 0 就淘汰该 页面，并把新的页面插入这个位置，然后把表针前移一个位置；如果 R 位是 1 就清除 R 位并把表针前移一个位置，重复这个过程直到找到了一个 R 位为 0 的页 面为止。 四、 总体设计  根据要求设计页面淘汰算法的活动图 运行程序进入主页面，在正上方，已经通过随机生成函数生成了页面 号，在其下方，显示可选项：0、退出程序 1、FIFO 算法 2、OPT 算法 3、 LRU 算法。根据需要，选择相应的 法，程序自动生成页面淘汰的先后顺序，以及置换次数和缺页次数，并打 印在下方，执行完 以后，再次进入主页面，到输入 0，退出程序。  算法流程图  FIFO算法流程图：
    OPT 算法流程图
    LRU 算法流程图：
    五、 详细设计 （一）、设计思想 1、 最佳置换算法(OPT) 用数组 Temppages[]存储当前物理块中页面信息，数组 TimeArry[]存 储当前在物理块中的页面的获得内存时的时间，当页面不在内存中时， 根据当前已获得物理块数的页面在所有的页面当中将来不在请求内存 或者很少请求内存的情况进行置换 2、 先进先出算法(FIFO) 用数组 Temppages[]存储当前物理块中页面信息，变量 temp 记录内存 中物理块页面置换状态，每进行一次置换，页面置换状态变化，便于 下一次的置换。 3、 最近最久未使用算法(LRU) 用数组 Temppages[]存储当前物理块中页面信息，数组 TimeArry[]存 储当前在物理块中的页面的获得内存时的时间，当页面不在内存中时， 选择 TimeArry[]数组中值最小并且对应物理块中的页面进行置换。 （二）、设计步骤 首先根据程序要求，我们分别定义两个宏，用以存放我们的物理块数 目以及页面数目，再定义一个结构体，用以物理块的存储，代码如下： #define MemPageCount 4 #define InstructionCount 20 struct page { int serial; //页面号 int time; //时间计数 }mempage[MemPageCount]; 其次，建立主函数，根据程序需要，定义相应的变量，建立 switch 语句，用以 算法的选择，部分定义如下： int i,j,k,m,n; int instruction[InstructionCount]; int mem_counter; //内存页面集合计数器 int switch_counter; //置换次数 //指令页面集合,可以考虑让页面指令集合随机生成 最后，根据算法流程图，实现相应算法的代码编写。 （三）、算法流程设计 主函数流程: STEP1:输入分配的页框数，页面访问次数和要访问的页面号序列 STEP2:内存页面初始化。内存中页面的数据结构为单循环链表，含有页号值 yehao 和访问位值 a。开始时页号均为-1，访问位为 0.
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料