XXXX大学实 验 报 告
|
|
实验四 存储器管理实验实验名称
操作系统课程名称 |
|
专业班级：:
学生姓名
学绩： 成 号： 指导教师：实验日期：
华 北 电 力 大 学 实 验 报 告
一、实验目的及要求 一、实验目的请求页式存储管存储器管理的主要功能是，合理地分配内存空间，数据存储和查询。其中，
理是一种具有虚拟空间技术的存储器管理系统。加深了解虚拟存储技术的特点，本实验的目的是， 设计请求页式存储管理中的页面置换算法， 掌握各种页面置换的算法。
二、实验要求 （１）通过随机数产生一个指令序列，共３２０条指令。指令的地址按下述原则生成：
５０％的指令是顺序执行的。
① ２５％的指令均匀分布在低地址部分。
② ２５％的指令均匀分布在高地址部分。③
具体实施的方法是： ① 在［０，３１９］的指令地址之间随机产生一个起点m； ② 顺序执行一条指令，即执行m＋１处的执行； 在地址［０，m＋１］中随机选取一条指令执行，该指令的地址为m１；③
④ 顺序执行一条指令，即执行m1＋１处的执行； ］中随机选取一条指令执行；m1＋2,319 ⑤在地址［ 重复上述步骤直到执行了３２０条指令为止。⑥
（２）将指令序列改变为页地址流，并假设： 页面尺寸为１Ｋ。
①
用户的内存容量为４页到３２页。
②
用户的虚存容量为３２Ｋ。
③
在用户虚存中，按每Ｋ存放１０条指令来排列虚存地址，即３２０条指令在虚存放方式为： ）。第０条～第９条为０号页（对应的虚存地址为［０，９］ ）。第１０条～第１９条为１号页（对应的虚存地址为［１０，１９］ … … … … 3１０，3１９］）。１号页（对应的虚存地址为［第3１０条～第3１９条为3 按上述方式，用户指令可组成32页。
（3）计算并输出下述各种算法在不同内存容量下的命中率。
。先进先出算法（FIFO）①
）。
② 最近最少使用算法（LRU 最佳淘汰算法。
③
最少访问页面算法（LFR）。
④
其中，命中率为： 页地址流长度缺页次数 命中率=(1+)/，页面失效次数为每次访问响应指令时，该指令对应的页本实验中，页的地址流长度为320
面不在内存中的次数。
3．随机数的产生方法
页 共 页 第
华 北 电 力 大 学 实 验 报 告
的作用是是一个种子，提srand() srand() and rand()。
在VC中设计到随机数有两个函数 根据种子而产生随机数。供每次获得随机数的基数而已，rand() 注意 srand() 里的值必须是动态变化的，否则得到的随机数就是一个固定数： 1 0-60的随机数那么可以写成 2：如果我们想得到一个int i;
srand(GetTickCount());
i=rand()`;
二、实验所需仪器、设备、材料 PC机 三、实验原理 1、分页请求系统
为了能实现请求调页和置换功能，系统必须提供必要的硬件支持，其中，最重要的是：
）请求分页的页表机制。它是在分页的页表机制上增加若干个项而形成的，作为请求分页的（1 数据结构；）缺页中断机构。每当用户程序要访问的页面尚未调入内存时，便产生一缺页中断，以请求2（ 将所缺的页面调入内存；OS ）地址变换机构。它同样是在分页的地址变换机构的基础上发展形成的。（3将所需的页从外存调入OS为了实现请求调页还须得到OS的支持，在实现请求调页功能时，石油 将内存的某些页调至外存。内存；在实现置换功能时，也是由OS 、页面置换算法2 ）置换算法一、最佳（Optimal但由于人们目前还无法预知一个进程在内存的采用最佳置换算法可保证获得最低的缺页率。
若干个页面中，哪一个页面是未来最长时间内不在被访问的，因而该算法也是无法实现的，但是示出了利用最佳置换算法时的置换图。由图可看出，采用可利用该算法去评价其它算法。图6-3 6次页面置换。最佳置换算法，只发生了 二、先进先出页面置换算法该该算法总是淘汰最先进入内存的页面，即选择在内存中的驻留时间最久的页面予以淘汰。
算法实现简单，只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老页面。但该算法与进程实际运行的规律不相适应，因为在置换算法并不能FIFO进程中，有些页面经常被访问，含有全局变量、常用函数、例程等的页面， 保证这些页面不被淘汰。
置换算法三、最近最久未使用LRU ）算法的描述（Least Recently Used1、LRU置换算法之所以性能较差，是因为它所依据的条件是各个页面调入内存的时间，而页 FIFO
，则是根LRU）的页面置换算法，面调入的先后并不能反映页面的使用情况。而最近最久未使用（据页面调入内存后的使用情况。由于无法预测各页面将来的使用情况，只能利用“最近的过去” 置换算法是选择最近最久未使用的页面予以淘汰。作为“最近的将来”的近似。因此，LRU LRU算法的硬件支持、2
页 共 页 第
华 北 电 力 大 学 实 验 报 告
但实现起算法作为页面置换算法是比较好的，它对于各种类型的程序都能适用， 把LRU
来有相当大的难度，因为它要求系统具有较多的支持硬件。所要解决的问题有： 1.一个进程在内存中的各个页面各有多久时间未被进程访问；
2. 如何快速地知道哪一页最近最久未使用的页面。为此，须利用以下两类支持硬件：
1）寄存器（ 用于记录某进程在内存中各页的使用情况。页实R7 R6 R5 R4 R3 R2 R1 R0 /R
0 1 0 1 1 0 1 0 0
0 0 2 1 0 1 1 0 1
0 3 1 0 0 0 0 O 0
1 0 1 1 0 4 1 0 1
0 1 1 5 0 1 0 1 1
1 6 0 1 1 0 1 0 0
1 1 1 0 0 7 0 0 0
1
0
1
8
1
0
1
1
0
（2）栈便将该每当进程访问某页面时， 可利用一个特殊的栈来保存当前使用的各个页面的页面号。
页面的页面号从栈中移出，将它压入栈顶。
置换算法四、Clock
置换算法Clock1、简单的在将内存中的所有页面都通过链接指针链算法时，只须为每页设置一位访问位，Clock 利用。置换算法在选择一页淘汰时，只须检查其成一个循环队列。当某页被访问时，其访问位被置1 访问位。
Clock置换算法、改进型2但如果该页未被修在将一个页面换出时， 如果该页已被修改过，便须将它重新写到磁盘上；M改过，则不必将它拷回磁盘。同时满足两条件的页面作为手癣淘汰的页。由访问位A和修改位 可以组合成下面四种类型的页面： 1 类（）。表示该页最近既未被访问、又未被修改，是最佳淘汰页。M=0A=0， ）。表示该页最近未被访问，但已被修改，并不是很好的淘汰页。M=1A=02 类（， 3 类（。最近已被访问，但未被修改，该页有可能再被访问。）M=0A=1， ）M=1A=14 类（，。最近已被访问且被修改，该页有可能再被访问。算法相在内存中的每个页必定是这四类页面之一， 在进行页面置换时，Clock可采用与简单
类似的算法，其差别在于须同时检查访问位和修改位，以确定该页是四类页面中的那一种。此算 法称为改进型Clock算法。其执行过程可分成以下三步：的第一类页面，将所1（M=0 且）从指针所指示的当前位置开始，扫描循环队列，寻找A=0 。A遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位且A=0）如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找2 （
页 共 页 第
华 北 电 力 大 学 实 验 报 告
的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有经过的M=1 0页面的访问位置。）如果第二步也失败，即未找到第二类页面，则将指针返回到开始的位置，并将所有的（3
。然后，重复第一步，如果仍失败，必要时在重复第二步，此时就一定能够找到被淘访问位复0 汰的页。
五、其它置换算法 Least Frequently Used）置换算法1、最少使用（用来记录该页面被访问的频在采用该算法时，应为在内存中的每个页面设置一移位寄存器，
率，该置换算法选择在最近时期使用最少的页面作为淘汰页。
Page Buffering Algorithm）2、页面缓冲算法（算法好，但它们都需要一定的硬件支持，置换一个已FIFO和Clock置换算法都比 虽然LRU修改的页的开销要大。而页面缓冲算法则既改善分页系统的性能，又可采用一种较简单的置换策 略。
六、请求分页系统的性能分析 、缺页率对有效访问的时间的影响1缺页中 ma+p 1-p） 缺页时须先调入该页的情况时，有效访问时间表示为：有效访问时间=（
断时间。
、缺页中断时间的组成2 1）缺页中断时间服务时间；（ 2）将缺页中断读入的时间；（ 3）进程重新执行时间。（而将一磁盘块读入内1ms;）和（3）两部分可以不超过速度很快，所以其中地（ 由于CUP1。由此可得知缺页24ms存的时间，则包括寻道时间、旋转时间和数据传送时间三部分，大体上是 将上述数据代入到工集。此处尚未考虑到进程可能因排队等待所花费的时间。中断时间约为25ms 有效访问时间 四：实验步骤 此实验尚未完全做出，程序无法正常运行。
页 共 页 第
华 北 电 力 大 学 实 验 报 告
实验心得语言这一种高级语言C操作系统的实验和数据结构的实验有不同也有相同之处，因为只掌握了 方式，所以在编程方式上和数据结构实验相同。更加侧重于计和计算机的操作原理中的进程调度有关，但是操作系统的实验问题更加专业化， 算机内部的程序和进程的运行。还在点滴之间学到了生活和学在一学期的操作系统课上，我们不仅仅学到了有关的专业知识，更加清楚地认识到了计算机专习的方式方法，也在老师的传递当中感触到了以后工作的境地和环境。而不能仅仅就是应该在大的方面了解自己的所学所用，作为一名计算机专业的学生，业的未来前途。只有在认识到自己将要去做些什么才能真正的拘泥于简单的专业知识不看到宏观的环境和就业前景。
去学习到对自己以后有用的东西。非常感谢宋老师在教会了我们专业课的前提下还能潜移默化一些对我们更加有用的知识所以， 和经验。希望在以后的学习中还有和老师合作的机会。
页 共 页 第
华 北 电 力 大 学 实 验 报 告
页 共 页 第