页面置换算法操作系统课程设计

《页面置换算法操作系统课程设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、安徽大学江淮学院《操作系统课程设计报告》专业：计算机班级：网络工程班姓名：赵娜指导教师：江东学号：JW目录1.课程设计目的……………………………………………………22.课程设计题目描述和要求………………………………………33.课程设计内容……………………………………………………33.1页面置换原理描述………………………………………………33.2模拟页面置换算法的代码……………………………………64.课程设计实验总结………………………………………………85.参考文献…………………………………………………………9Clock页面置换算法1.课程设计目的本实验主要对操作系统中应用的一些关键算

2、法进行模拟。学生通过设计与实现相关算法，能够加强对相应理论的理解，并对了解操作系统内部的基本处理原理与过程也有很多益处。2.课程设计题目描述和要求基本要求：描述Clock算法的基本原理、必要的数据结构、算法执行流程图、编码实现。1）初始化：输入作业可占用的总页框数，初始化置空。2）输入请求序列：输入一个作业页号访问请求序列，依次占用相应页框，直至全部占用；3）Clock算法：当页框全部占用后，对于后续新的页号访问请求，执行Clock算法，淘汰1个页面后装入新的页号。4）显示当前分配淘汰序列：显示淘汰的页号序列。3.课程设计内容3.1页面置换原理描述在采用请求分页机制的操作系统中，当运

3、行一个程序的时候，若要访问的页面不在内存中而需要把它们调入内存，但此时内存已无空闲空间，为了保证该进程能正常运行，需选择内存中暂时不用的页面调出到磁盘交换区。选择调出哪个页面，由页面算法决定。页面置换算法的好坏，直接影响系统的性能，所以一个好的页面置换算法，应尽可能选择调出较长时间内不会再访问的页面，以保证较低的缺页率。改进型的Clock算法的思想：在将一个页面换出时，如果该页已被修改过，便须将它重新写到磁盘上；但如果该页未被修改过，则不必将它拷回磁盘。同时满足这两条件的页面作为首先淘汰的页。由访问位A和修改位M可以组合成下面四种类型的页面：1类（A=0，M=0）：表示该页最近既未被

4、访问、又未被修改，是最佳淘汰页。2类（A=0，M=1）：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。3类（A=1，M=0）：最近已被访问，但未被修改，该页有可能再被访问。4类（A=1，M=1）：最近已被访问且被修改，该页有可能再被访问。在内存中的每个页必定是这四类页面之一，在进行页面置换时，可采用与简单Clock算法相类似的算法，其差别在于须同时检查访问位和修改位，以确定该页是四类页面中的哪一种。此算法称为改进型Clock算法。其执行过程可分成以下三步：（1）从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在

5、第一次扫描期间不改变访问位A。（2）如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有经过的页面的访问位置0。（3）如果第二步也失败，即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。然后，重复第一步，如果仍失败，必要时再重复第二步，此时就一定能够找到被淘汰的页。3.2流程图实现输入页面置换该页面第二次扫描，是否存在A为1，M为0的页面，将扫面后的A置1输入页面，置换页面第一次扫描，看是否存在A=0，M=1页面把需要修改的页面的标志位修改为1是否修改页面初始化n

6、个页面算法开始输入页面号输入页面为n3.2模拟页面置换算法的代码（1）定义页面表的数据结构，它包括页号（info）,访问位（A），修改标志（M）和指针4个属性。代码如下：templateclassNode//结点类模板，不同数据类型，编译时生成不同的类{public:Tinfo;//定义三个变量intA;//访问页变量，引用位的值intM;//修改页变量，引用位的值Node*link;//定义类的基地址};（2）通过界面接收的页面数（K），在主程序中先对K个页面通过调用方法Insertrear(Tdata)进行初始化，代码如下：while(1){if(n<

7、k){cout<<"请输入要访问的页面号："<>num;cout<Insertrear(num);n++;}}（3）初始化页面之后会提示是否对内存中存在的页面进行修改，选择Y，就会调用方法change(),并对你选择的页面的修改标志（M）进行修改，把它改为1（说明该页面已被修改过了）。选择N，就会提示你“请输入访问的页面号”，当你输入一个页面号：a、通过调用方法find0(Tdata)判断你输入的页面号是否跟内存中