操作系统课程设计-虚拟存储器管理设计系统.doc

佛山科学技术学院课程设计用纸课程设计说明书设计名称： 操作系统课程设计 题 目： 虚拟存储器管理设计系统 学生姓名： 专 业： 计算机科学与技术 班 级： 08 学 号： 指导教师： 日 期： 2011年5月5日 课程设计任务书计算机科学与技术 专业 08 年级 2 班 一、 设计题目虚拟存储器管理系统设计二、 主要内容设计一个简单的虚拟存储器管理系统，模拟实际的页面调度算法与过程，通过该系统的设计，掌握页面调度的几种主要算法。 三、 具体要求本课程设计共2周，采取集中方式。主要设计内容1、进程调度2、存储管理3、文件管理操作系统分项设计设计三：虚拟存储器管理系统设计本设计的目的是通过设计一个简单的虚拟存储器管理系统来模拟实际的页面调度算法与过程，以掌握这种有用的技术。要求将其输入/输出处理程序编成一个独立的进程模块并与其它请求输入/输出的进程并发运行。并要求加入设备管理子模块。具体分析为：页面调度算法主要有FIFO、最近最少使用调度算法（LRU）、最近最不常用调度算法（LFU）、最佳算法（OPT）等。题目要求： 实现三种算法：1、先进先出；2、OPT；3、LRU 页面序列从指定的文本文件（DAT文件）中取出 输出：第一行：每次淘汰的页面号，第二行：显示缺页的总次数 四、 进度安排1、教师下达设计任务书(半天)任务书内容包括题目、主要技术指标和要求、给定条件及原始数据、所用仪器设备和参考资料及文献等。教师讲授必要的设计思路和设计方法。2、学生完成预设计(1天半)本阶段学生通过查阅资料及文献（主要自学），明确任务，掌握工程设计基本方法，确定设计方案，进行设计分析，完成预设计。3、实验阶段(7天)经教师审查通过预设计方案后，即可进行编程调试。实验由学生独立完成，教师定时指导。4、设计总结阶段(1天)本阶段学生要认真完成课程设计报告书，整理技术资料，并尽可能写出课程设计的心得体会和改进意见。五、 完成后应上交的材料课程设计报告书包括：设计任务及主要技术指标、设计方案及论证结果、系统的原理框图、设计程序、实验结果、实验中主要问题及故障现象的分析及设计结论等。附实验数据、系统软硬件环境、使用说明及参考资料。六、 总评成绩指导教师 签名日期 年 月 日系 主 任 审核日期 年 月 日21目录一、设计任务分析2虚拟存储器管理系统设计211虚拟存储技术分析：2虚拟存储技术概述2虚拟存储技术的概念2虚拟存储技术的优势312使用算法分析：3121 FIFO算法（先进先出淘汰算法）3122 LRU算法（最久未使用淘汰算法）5123OPT算法（最佳淘汰算法）6二、总设计方案81查阅相关资料及文献，按设计要求刻画程序的基本思想；8 最佳置换算法(Optimal)：8 先进先出(FIFO)页面置换算法：8 LRU置换算法：LRU(Least Recently Used)置换算法的描述92、LRU置换算法的硬件支持81）寄存器92)栈9三、程序设计结构图1031虚拟存储管理器系统设计总框图1032各模块功能N-S图11寻找时间最长的页面功能模块：12内存页面输入功能模块：12指针页面移动功能模块：13FIFO功能模块：14LRU功能模块：15OPT算法思想：16四、设计程序结果18五、设计心得19六、参考文献25一、设计任务分析虚拟存储器管理系统设计本设计的目的是通过设计一个简单的虚拟存储器管理系统来模拟实际的页面调度算法与过程，以掌握这种有用的技术。要求将其输入/输出处理程序编成一个独立的进程模块并与其它请求输入/输出的进程并发运行。并要求加入设备管理子模块。11虚拟存储技术分析：虚拟存储技术概述 虚拟存储技术是随着计算机技术的发展而发展起来的。早在20世纪70年代，为了克服内存容量小成本高而不适应大型程序应用需要的矛盾，人们开发了虚拟内存技术。随着计算机技术及相关信息处理技术的不断发展，人们对存储的需求越来越大，单个大容量磁盘已不能适应应用的需要，虚拟存储技术又有进一步的发展，如在操作系统下将一组硬盘捆绑成带区集（STRIP）作为单个逻辑存储单元供主机访问；磁盘冗余阵列（RAID）技术将多个物理磁盘通过一定的逻辑关系集合起来，成为一个大容量的虚拟磁盘。从某种意义上讲，SAN本身也是虚拟存储技术的应用。虚拟存储技术的概念所谓虚拟存储技术，是指把多个物理上独立存在的存储体通过软件或硬件的手段集中管理起来，形成一个逻辑上的虚拟存储单元供主机访问。这个虚拟逻辑单元的存储容量是它所集中管理的各物理存储体的存储容量之和，而它的访问带宽则在一定程度上接近各个物理存储体的访问带宽之和。虚拟存储实际上是逻辑存储，是一种智能、有效地管理存储数据的方式。虚拟存储克服了物理存储的局限，它可以把物理设备变成完全不同的逻辑镜像，呈现给用户，既充分利用了物理设备的优势，如高性能、高可用，又打破了物理设备本身不可克服的局限性。从用户角度看，使用存储空间而不是使用物理存储硬件，管理存储空间而不是管理物理存储部件，这就是虚拟存储的概念。虚拟存储技术的优势虚拟存储技术不仅可以提高主机访问存储设备的性能，同时对于存储容量的扩展是非常方便的，可以保护原有投资，实现不影响正常数据访问的前提下的动态扩容。虚拟存储技术为实际应用带来的好处主要体现在以下几个方面：1）虚拟存储技术使网络系统存储部分的重要指标单个逻辑单元的存储容量和访问带宽相对单个物理存储体大大提高，适应了网络应用特别是视频网络应用的需要。2）在虚拟存储环境下，无论后端物理存储体是什么设备，服务器及其应用系统看到的都是其熟悉的存储设备的逻辑镜像。即使物理存储体发生变化，其逻辑镜像也不发生变化，应用系统无需关心后端存储，只需专注于管理存储空间，使得存储管理变得轻松简单，便于灵活配置。3）虚拟存储是一种智能化的系统，它允许客户以透明有效的方式在磁盘或磁带上存储数据，使客户的存储系统容纳更多的数据，也使更多的用户可以共享同一个系统。虚拟存储器的效率是系统性能评价的重要内容，它与主存容量、页面大小、命中率，程序局部性和替换算法等因素有关。12使用算法分析：121 FIFO算法（先进先出淘汰算法）1) 什么是先进先出淘汰算法？该算法总是淘汰最先进入内存的页面，即悬着在内存中驻留时间最久的页面予以淘汰。2) 实现方法系统保留一张次序表，该表记录了作业程序的各页面进入主存的先后次序。用数组作次序表可在主存中建立一个m(m是分配给该作业的存储块数)个元素的页号表和一个调换指针。如下图所示： 替换指针 页号 指向最老一页 2 451 用存储分块表作次序表该次序表以块号为序，依次各块的分配情况。这里假定m4，且4，5，1，2页以依次装入2，6，7，4各存储块中。此时存储分块表如下图所示：（a）替换以前122 LRU算法（最久未使用淘汰算法）1) 什么是最久未使用淘汰算法？当需要淘汰一页时，总是选择最长时间未被使用的那一页淘汰。2) 实现方法用硬件实现此算法每一页可以设置一个R位的寄存器；每次访问一页时，将该页所对应的寄存器的最左一位置1；每隔时间t将所有的R位寄存器右移一位。这样，在TRt时间内，方问过的页多对应的寄存器R内时一个不全为0的整数，而没有访问过的页相对应的R之值为0。当缺页中断时，选择R值最小的那页进行淘汰。用页号栈实现此算法设立一个页号栈，使栈顶元素为刚北访问的页面，而栈底元素为最久未被访问的页面。每当访问页面时，该页号栈需进行调整。一个页面被访问过，就立即将它的页号记在页号栈的顶部，而将栈中原有的页号依次下移。如果栈中原有的页号中有与新记入顶部的页号相重者，则将该重号抽出，且将页号栈内容进行紧凑压缩。123 OPT算法（最佳淘汰算法）1) 什么是最佳淘汰算法？当需要淘汰一页时，将选择以后永不使用的或许是在最长(未来)时间内不再被访问的页面。2) 算法优势 采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。二、总设计方案1查阅相关资料及文献，按设计要求刻画程序的基本思想；置换算法思想 最佳置换算法(Optimal)： 它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。 先进先出(FIFO)页面置换算法： 这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。 LRU置换算法：LRU(Least Recently Used)置换算法的描述 FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。 2、LRU置换算法的硬件支持 LRU置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有以下两类硬件之一的支持： 1）寄存器 为了记录某个进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为 R=Rn-1Rn-2Rn-3R2R1R0 当进程访问某物理块时，要将相应寄存器的Rn-1位置成1。此时，定时信号将每隔一定时间(例如100ms)将寄存器右移一位。如果我们把n位寄存器的数看作是一个整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。如图1示出了某进程在内存中具有8个页面，为每个内存页面配置一个8位寄存器时的LRU访问情况。这里，把8个内存页面的序号分别定为18。由图可以看出，第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)栈 可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号民，而栈底则是最近最久未使用的页面的页面号。 三、程序设计结构图31虚拟存储管理器系统设计总框图关于作者保存页面流系统功能描述：通过设计操作系统中虚拟存储管理系统解决存储容量和存取速度矛盾，是管理存储设备的有效方法。使用FIFO，LRU，OPT，三种置换算法置换页面进行比较，选择适合虚拟存储管理系统理想的调度算法。32各模块功能N-S图寻找时间最长的页面功能模块：算法思想：通过寻找时间最长的页面，为进行FIFO，LRU,ORT三种调度算法运算提供前提条件。主要参数功能 :Pro *page 用来指向调入内存最长时间的页面 Max()函数N-S图内存页面输入功能模块：算法思想：通过输入内存页面，选择调度功能，并输入正确页面流文件名，显示读入的页面流，如文件不符，则显示“错误，文件打不开，请检查文件名”。指针页面移动功能模块：算法思想：通过指针移动进行页面置换的工作。FIFO功能模块：算法思想：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。LRU功能模块：算法思想：最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。 OPT算法思想：选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。 四、设计程序结果五、设计心得通过两周的课程设计,加深了对操作系统的认识,了解了操作系统中各种资源分配算法的实现,特别是对虚拟存储,页面置换有了深入的了解,并能够用高级语言进行模拟演示。这次的操作系统大作业的工作量比较大，我投入了很多的时间和精力才完成了系统的设计。不过这些付出都是值得的，因为我收获了更多。首先，我必须要了解虚拟内存的特性，通过到图书馆找资料，翻阅书本和网上搜索，理解到虚拟页式管理的基本原理是系统自动地将作业的地址空间分页，将系统的主存空间分块，页与块等大小，在作业运行前，只把初始需要的一部分页面装入内存块里，运行中需要访问自己地址空间中的当前不在内存的页面时产生缺页中断，由缺页中断服务程序将所需的页面调入内存，若此时内存中没有空闲物理块安置请求调入的新页面，则系统按预定的置换策略自动选择一个或一些在内存的页面，把它们换出到外存。还有研究了主存页面的分配策略和页面调入时机。这对之后的算法编写有很大的帮助。其后，是要熟悉各算法的思想，我重新复习了操作系统页面调度中OPT、FIFO、LRU的算法，上网查阅各算法的资料，经过一段时间的研究，我开始编写算法的程序。虽然了解了各算法的思想，但到编写起程序来，还是有一点难度，又需要再复习C+的部分语法，如文件流的输入输出，因为对课堂知识只是了解，但实践中有些不常