《页面置换算法实验报告68721》由会员分享，可在线阅读，更多相关《页面置换算法实验报告68721（25页珍藏版）》请在金锄头文库上搜索。
1、操作系统课程设计报告 课课程程名名称称： 操操作作系系统统课课程程设设计计 课程设计题目课程设计题目： 页面置换算法页面置换算法 学院：学院： 计算机科学与技术学院计算机科学与技术学院 专专业业： 科科技技 小小组组成成员员 : : 庞庞思思慧慧 E E0 01 11 11 14 40 08 81 1 王王蒙蒙 E E0 01 11 11 14 41 16 61 1 慧慧乔乔 E E0 01 11 11 14 43 34 49 9 朱朱潮潮潮潮 E E0 01 11 11 14 44 40 08 8 指导老师：指导老师： 邱剑锋邱剑锋 目录目录 1实验目的实验目的 .3 2实验要求实验要求 .
2、3 3实验容与步骤实验容与步骤 .3 4算法思想算法思想 .4 5模块设计模块设计 .4 6程序设计程序设计 .5 7测试结果测试结果 .7 8结果分析结果分析 .9 9程序代码程序代码 .9 10课程设计小结课程设计小结 .24 页面置换算法模拟设计页面置换算法模拟设计 1.1.实验目的实验目的 （1）通过模拟实现几种基本页面置换的算法，了解虚拟存储技术的特点。 （2）掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想，并至少用三种 算法来模拟实现。 （3）通过对几种置换算法命中率的比较，来对比他们的优缺点。 2.2.实验要求实验要求 计算并输出下述各种算法在不同存容量下的命中率。
3、 A A 先进先出的算法（FIFO） B B 最近最少使用算法（LRU） C C 最佳淘汰算法（OPT） 3.3.实验容与步骤实验容与步骤 (1)通过随机数产生一个指令序列，共 320 条指令，具体的实施方法是： A 0，319的指令地址之间随机选取一起点 M; B 顺序执行一条指令，即执行地址为 M+1 的指令； C 在前地址0，M+1中随机选取一条指令并执行，该指令的地址为 M; D 顺序执行一条指令，其地址为 M+1； E 在后地址M+2，319中随机选取一条指令并执行； F重复 AE，直到执行 320 次指令。 (2)指令序列变换成页地址流 A.页面大小为 1K； B.用户存容量为 4
4、 页到 32 页； C.用户虚存容量为 32K。 在用户虚存中，按每 K 存放 10 条指令排列虚存地址，即 320 条指令在虚存中的 存放方式为： 第 0 条第 9 条指令为第 0 页（对应虚存地址为0，9） ； 第 10 条第 19 条指令为第 1 页（对应虚存地址为10，19） ； 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 第 310 条第 319 条指令为第 31 页（对应虚存地址为310，319） ； (3)计算并输出上述各种算法在不同存容量下的命中率。 命中率=1-缺页次数/页地址流长度 4.4.算法思想算法思想 在进程运行过程中，若其所要
5、访问的页面不在存而需把它们调入存，但存已无空闲空 间时，为了保证该进程能正常运行，系统必须从存中调出一页程序或数据，送磁盘的对换 区中。但应将哪 个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称 为页面置换算法。一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应 将那些以后不再会访问的页面换出，或将那些在较长时间不会再访问的页面调出。 1.先进先出算法 FIFO： 这是最早出现的置换算法。该算法总是淘汰最先进入存的页面，即选择在存中驻留时间 最久的页面予以淘汰。该算法实现简单只需把一个进程已调入存的页面，按先后次序成一 个队列，并设置一个指针，称为替换指针，使它总是
6、指向最老的页面。 2.最近最久未使用算法 LRU（least recently used）： 算法的基本思想：当需要淘汰某一页时，选择离当前时间最近的一段时间最久没有使用过 的页先淘汰。该算法的主要出发点是，如果某页被访问了，则它可能马上还被访问。或者 反过来说，如果某页很长时间未被访问，则它在最近一段时间不会被访问。 3.最佳淘汰算法 OPT 其所选择的被淘汰的页面将是以后永不使用，或许是未来最长时间不使用的页面，该算法 可保证获得最低的淘汰率，但在实际运用中无法实现，可用来评价其他算法的命中率。 5.5.模块设计模块设计 入口 产生随机数、要调入的页面、离现在处理时间最长的页面、 最长的页
7、面 初始化页面情况 t1N 根据选择的算法进行 置换，缺页数加 1 计算缺页率，并输出数 据 结束 Y N 直接存入内存 开始 输入内存数 调用各种置换算法， ，并显示地址流、 页面流、页面置换过程和命中率 命中率比较 结束结束 总模块图总模块图 主程序图 6.6.程序设计程序设计 struct Pro /存页的结构体 int num； /记录页面号 int time； /页面从未被利用的时间 ; #define M 320 /定义指令条数 Pro PM; /产生的随机指令数组 void Input() /产生随机数 int s; /随机数 int i; srand(time(0); s =
8、rand()%M; /coutn-随机产生指令流-n; for (i=0; iM; i+=4) /产生指令队列 pi.num=s; /任选一指令访问点 m pi+1.num=pi.num+1; /顺序执行一条指令 pi+2.num=(int)(float)pi.num*(rand()/(RAND_MAX+1.0); /执行前地址指令 m pi+3.num=pi+2.num+1; /顺序执行一条指令 s=(int)(float)(319-pi+2.num)*(rand()/(RAND_MAX+1.0) + pi+2.num; for(i=0;iM;i+) pi.time=0; int Searc
9、h(int e,Pro*page1,int N) /查找存中是否存在要调入的页面 int t; Pro*page=new ProN; page=page1; for(int i=0;iN;i+) t=e/10; if(t=pagei.num) return i; return -1; int Max(Pro*page1,int N)/查找最久最久未被使用的页面 Pro*page=new ProN; page=page1; int e=page0.time,i=0; while(iN) if(epagei.time) e=pagei.time; /找最长时间 i+; for(i=0;iN;i+)
10、 if(e=pagei.time) return i; /找最长时间的下标 return -1; int Compfu(Pro*page1,int i,int t,Pro pM) /找到最久不使用的页面 Pro*page=new ProN; page=page1; int count=0; for(int j=i;jLRUCLOCKFIFO。实际上， 在存页面数较少（45 页面）时，3 种算法的命中率差别不大，可是 50%左右。在存页面为 725 个页面之间时，3 种算法的访命中率大致在 52%至 87%之间变化。在存页面为 2532 个 页面时，由于用户进程的所有指令基本上都已装入存，从而命中率已较大。从而算法之间 的差别不大。 9.9.程序代码程序代码 / 页面置换算法模拟设计 Dlg.cpp : implementation file #include stdafx.h #include 页面置换算法模拟设计.h #include 页面置换算法模拟设计 Dlg.h #ifdef _DEBUG #define new DEBUG_NEW #undef THIS_FILE static char THIS_FILE = _FILE_; #endif /
