福州大学工程技术学院 实 验 报 告 课程名称： 操作系统 _ _ _ _ 学 号： x x _ _ _ _ 姓 名： x x _ _ _ _ _ 专 业： 计算机科学与技术 _ _ _ _ 年 级： 1 0 级 学 期： 2 0 1 0 年第 1 学期 _ 2 0 1 0 年 1 2 月 2 0 日 - 2 - 实验一 页面置换算法及其实现分析 一、实验目的 本实验主要对操作系统中应用的一些关键算法进行模拟。学生通过设计与实现相关算法，能够加强对相应理论的理解，并对了解操作系统内部的基本处理原理与过程也有很多益处。 二、实验要求 描述 Clo ck 算法的基本原理、必要的数据结构、算法执行流程图、编码实现。 三、实验内容 1、页面置换原理描述 在采用请求分页机制的操作系统中，当运行一个程序的时候，若要访问的页面不在内存中而需要把它们调入内存，但此时内存已无空闲空间，为了保证该进程能正常运行，需选择内存中暂时不用的页面调出到磁盘交换区。选择调出哪个页面，由页面算法决定。页面置换算法的好坏，直接影响系统的性能，所以一个好的页面置换算法，应尽可能选择调出较长时间内不会再访问的页面，以保证较低的缺页率。 改进型的 Clo ck 算法的思想：在将一个页面换出时，如果该页已被修改过，便须将它重新写到磁盘上；但如果该页未被修改过，则不必将它拷回磁盘。同时满足这两条件的页面作为首先淘汰的页。由访问位 A和修改位 M可以组合成下面四种类型的页面： 1 类（A=0，M=0）：表示该页最近既未被访问、又未被修改，是最佳淘汰页。 2 类（A=0，M=1）：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。 3 类（A=1，M=0）：最近已被访问，但未被修改，该页有可能再被访问。 4 类（A=1，M=1）：最近已被访问且被修改，该页有可能再被访问。 在内存中的每个页必定是这四类页面之一，在进行页面置换时，可采用与简单Clock算法相类似的算法，其差别在于须同时检查访问位和修改位，以确定该页是四类页面中的哪一种。此算法称为改进型Clock算法。其执行过程可分成以下三步： （1）从指针所指示的当前位置开始，扫描循环队列，寻找A=0且 M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位 A。 （2）如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找 A=0且 M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所...
