1、虚拟存储器管理系统 操作系统课程设计第1章 设计任务分析本设计的目的是通过设计一个简单的虚拟存储器管理系统来模拟实际的页面调度算法与过程，以掌握这种有用的技术。要求将其输入/输出处理程序编成一个独立的进程模块并与其它请求输入/输出的进程并发运行。并要求加入设备管理子模块。11虚拟存储技术分析 1.1.1 虚拟存储技术概述 虚拟存储技术是随着计算机技术的发展而发展起来的。早在20世纪70年代，为了克服内存容量小成本高而不适应大型程序应用需要的矛盾，人们开发了虚拟内存技术。随着计算机技术及相关信息处理技术的不断发展，人们对存储的需求越来越大，单个大容量磁盘已不能适应应用的需要，虚拟存储技术又有进一
2、步的发展，如在操作系统下将一组硬盘捆绑成带区集（STRIP）作为单个逻辑存储单元供主机访问；磁盘冗余阵列（RAID）技术将多个物理磁盘通过一定的逻辑关系集合起来，成为一个大容量的虚拟磁盘。从某种意义上讲，SAN本身也是虚拟存储技术的应用。 1.1.2 虚拟存储技术的概念 所谓虚拟存储技术，是指把多个物理上独立存在的存储体通过软件或硬件的手段集中管理起来，形成一个逻辑上的虚拟存储单元供主机访问。这个虚拟逻辑单元的存储容量是它所集中管理的各物理存储体的存储容量之和，而它的访问带宽则在一定程度上接近各个物理存储体的访问带宽之和。虚拟存储实际上是逻辑存储，是一种智能、有效地管理存储数据的方式。虚拟存储
3、克服了物理存储的局限，它可以把物理设备变成完全不同的逻辑镜像，呈现给用户，既充分利用了物理设备的优势，如高性能、高可用，又打破了物理设备本身不可克服的局限性。从用户角度看，使用存储空间而不是使用物理存储硬件，管理存储空间而不是管理物理存储部件，这就是虚拟存储的概念。 1.1.3 虚拟存储技术的优势 虚拟存储技术不仅可以提高主机访问存储设备的性能，同时对于存储容量的扩展是非常方便的，可以保护原有投资，实现不影响正常数据访问的前提下的动态扩容。虚拟存储技术为实际应用带来的好处主要体现在以下几个方面： 1）虚拟存储技术使网络系统存储部分的重要指标单个逻辑单元的存储容量和访问带宽相对单个物理存储体大大
4、提高，适应了网络应用特别是视频网络应用的需要。 2）在虚拟存储环境下，无论后端物理存储体是什么设备，服务器及其应用系统看到的都是其熟悉的存储设备的逻辑镜像。即使物理存储体发生变化，其逻辑镜像也不发生变化，应用系统无需关心后端存储，只需专注于管理存储空间，使得存储管理变得轻松简单，便于灵活配置。 3）虚拟存储是一种智能化的系统，它允许客户以透明有效的方式在磁盘或磁带上存储数据，使客户的存储系统容纳更多的数据，也使更多的用户可以共享同一个系统。 虚拟存储器的效率是系统性能评价的重要内容，它与主存容量、页面大小、命中率，程序局部性和替换算法等因素有关。12使用算法分析：1.2.1 FIFO算法（先进
5、先出淘汰算法）1)什么是先进先出淘汰算法？该算法总是淘汰最先进入内存的页面，即悬着在内存中驻留时间最久的页面予以淘汰。2)实现方法系统保留一张次序表，该表记录了作业程序的各页面进入主存的先后次序。用数组作次序表可在主存中建立一个m(m是分配给该作业的存储块数)个元素的页号表和一个调换指针。如下图所示： 用存储分块表作次序表该次序表以块号为序，依次各块的分配情况。这里假定m4，且4，5，1，2页以依次装入2，6，7，4各存储块中。此时存储分块表如下图所示：（a）替换以前1.2.2 LRU算法（最久未使用淘汰算法）1)什么是最久未使用淘汰算法？当需要淘汰一页时，总是选择最长时间未被使用的那一页淘汰
6、。2)实现方法用硬件实现此算法每一页可以设置一个R位的寄存器；每次访问一页时，将该页所对应的寄存器的最左一位置1；每隔时间t将所有的R位寄存器右移一位。这样，在TRt时间内，方问过的页多对应的寄存器R内时一个不全为0的整数，而没有访问过的页相对应的R之值为0。当缺页中断时，选择R值最小的那页进行淘汰。用页号栈实现此算法设立一个页号栈，使栈顶元素为刚北访问的页面，而栈底元素为最久未被访问的页面。每当访问页面时，该页号栈需进行调整。一个页面被访问过，就立即将它的页号记在页号栈的顶部，而将栈中原有的页号依次下移。如果栈中原有的页号中有与新记入顶部的页号相重者，则将该重号抽出，且将页号栈内容进行紧凑压
7、缩。1.2.3 OPT算法（最佳淘汰算法）1)什么是最佳淘汰算法？当需要淘汰一页时，将选择以后永不使用的或许是在最长(未来)时间内不再被访问的页面。2)算法优势 采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。第2章 总设计方案 2.1 置换算法思想 2.2.1 最佳置换算法(Optimal)： 它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，
8、通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。 2.1.2 先进先出(FIFO)页面置换算法： 这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。2.1.3 LRU置换算法：LRU(Least Recently Used)置换算法的描述 FIFO置换算法性能之所以较差，是因为它所依据的条件是各
9、个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。 22 LRU置换算法的硬件支持 LRU置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，
10、以及如何快速地知道哪一页是最近最久未使用的页面，须有以下两类硬件之一的支持： 2.2.1 寄存器 为了记录某个进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为 R=Rn-1Rn-2Rn-3R2R1R0 当进程访问某物理块时，要将相应寄存器的Rn-1位置成1。此时，定时信号将每隔一定时间(例如100ms)将寄存器右移一位。如果我们把n位寄存器的数看作是一个整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。如图1示出了某进程在内存中具有8个页面，为每个内存页面配置一个8位寄存器时的LRU访问情况。这里，把8个内存页面的序号分别定为18。由图可以看出
11、，第7个内存页面的R值最小，当发生缺页时首先将它置换出去。 R 实 页 R7 R6 R5 R4 R3 R2 R1 R0 1 0 1 0 1 0 0 1 0 2 1 0 1 0 1 1 0 0 3 0 0 0 0 0 1 0 0 4 0 1 1 0 1 0 1 1 5 1 1 0 1 0 1 1 0 6 0 0 1 0 1 0 1 1 7 0 0 0 0 0 1 1 1 8 0 1 1 0 1 1 0 1 2.2.2 栈 可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号民，而栈底则是最近最久未
12、使用的页面的页面号。 第3章 程序设计结构图31虚拟存储管理器系统设计总框图 系统功能描述：通过设计操作系统中虚拟存储管理系统解决存储容量和存取速度矛盾，是管理存储设备的有效方法。使用FIFO，LRU，OPT，三种置换算法置换页面进行比较，选择适合虚拟存储管理系统理想的调度算法。32各模块功能N-S图寻找时间最长的页面功能模块：算法思想：通过寻找时间最长的页面，为进行FIFO，LRU,ORT三种调度算法运算提供前提条件。主要参数功能 :Pro *page 用来指向调入内存最长时间的页面 Max()函数N-S图内存页面输入功能模块：算法思想：通过输入内存页面，选择调度功能，并输入正确页面流文件名
13、，显示读入的页面流，如文件不符，则显示“错误，文件打不开，请检查文件名”。指针页面移动功能模块：算法思想：通过指针移动进行页面置换的工作。FIFO功能模块：算法思想：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。LRU功能模块：算法思想：最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予
14、以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。 OPT算法思想：选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。 第4章 程序测试结果第5章 设计心得通过近一个月的课程设计,加深了对操作系统的认识,了解了操作系统中各种资源分配算法的实现,特别是对虚拟
15、存储,页面置换有了深入的了解,并能够用高级语言进行模拟演示。这次的操作系统大作业的工作量比较大，我投入了很多的时间和精力才完成了系统的设计。不过这些付出都是值得的，因为我收获了更多。首先，我必须要了解虚拟内存的特性，通过到图书馆找资料，翻阅书本和网上搜索，理解到虚拟页式管理的基本原理是系统自动地将作业的地址空间分页，将系统的主存空间分块，页与块等大小，在作业运行前，只把初始需要的一部分页面装入内存块里，运行中需要访问自己地址空间中的当前不在内存的页面时产生缺页中断，由缺页中断服务程序将所需的页面调入内存，若此时内存中没有空闲物理块安置请求调入的新页面，则系统按预定的置换策略自动选择一个或一些在
16、内存的页面，把它们换出到外存。还有研究了主存页面的分配策略和页面调入时机。这对之后的算法编写有很大的帮助。其后，是要熟悉各算法的思想，我重新复习了操作系统页面调度中OPT、FIFO、LRU的算法，上网查阅各算法的资料，经过一段时间的研究，我开始编写算法的程序。虽然了解了各算法的思想，但到编写起程序来，还是有一点难度，又需要再复习C+的部分语法，如文件流的输入输出，因为对课堂知识只是了解，但实践中有些不常用的命令很容易会遗忘。开始时还是毫无头绪，参考到一些资料和网上有关的代码，经过跟组员研究后，试着写一段测试一段地，逐渐把程序完善。在此过程中，两种页面置换算法FIFO和LRU理解起来相当容易，但
17、在实际编程实现的时候需要注意各种细节，需要耐心细致，实际编程中遇到一些细节上的小问题确实需要仔细考虑才行。另外，先进先出页面置换和LRU算法两者各有特点，但是实践起来却很大，使自己对页面置换算法有了新的认识。在我做预设计的时候因为还没有完善好程序的功能，所以这方面我的工作做得不够完美，不够具体，在详细设计和编程中，我们都修复了这些缺点并进行了改善，像界面变得更美化些，程序上变得更简洁些容易修改些。然后是设计功能及界面，参考了许多相关的程序代码和书本的资料，以及按照指导书的要求，我初步设计了个轮廓，功能方面也只能按理想化设计，因为未有实际操作到，还不能预计到一些实际性的问题。在本次实验中，通过浏览、阅读有关的资料，学到了很多东西，同时也发现仅仅书本的知识是远远不够的，需要把知识运用到实践中去，能力才能得到提高。通过分工合作，发挥了同学互相帮助，团结合作精神，遇到不会的问题一起讨论，查资料，问老师，在老师的指导和同学的帮助下，我收益良多。参考文献1 计算机操作系统基础 汤晓丹 、梁红兵 西安电子工业出版社2 Linux 操作系统内核分析 陈莉君 北京人民邮电出版社3 网络操作系统 徐甲同 吉林大学出版社4 操作系统 孟庆昌 北京电子工业出版社
