虚拟存储器管理设计

《虚拟存储器管理设计》由会员分享，可在线阅读，更多相关《虚拟存储器管理设计（22页珍藏版）》请在金锄头文库上搜索。

1、摘要虚拟存储技术是随着计算机技术的发展而发展起来的。早在20世纪70年代， 为了克服内存容量小成本高而不适应大型程序应用需要的矛盾，人们开发了虚拟 内存技术。本文采用模块化系统设计方法，对磁盘调度进行模拟实现，主要完成 了 FIFO （先进先出算法）、LRU （最近最久未使用算法）以及OPT （最佳置换算法） 的调度实现。系统采用从文件读取进程信息的方式，并提供用户自行选择调度算 法，并提供算法对比，以便用户明显看出算法的优劣。本文包含采用了结构体等数据结构，编写了寻找时间最长页面功能模块、页 面读入功能模块、FIFO功能模块、LRU功能模块等。基本实现虚拟存储器调度 的模拟实现，达到本系统设

2、计要求。关键字： 虚拟存储器、页面调度、管理系统目录摘要I一、设计任务分析 11.1 虚拟存储技术分析： 11.1.1 虚拟存储技术概述 11.1.2虚拟存储技术的概念 11.2 使用算法分析： 21.2.1 FIFO算法（先进先出淘汰算法）21.2.2 LRU算法（最久未使用淘汰算法）31.2.3 OPT算法（最佳淘汰算法）3二、总设计方案 42.1、 置换算法思想 42.2、 LRU置换算法的硬件支持5三、程序设计结构图 63.1虚拟存储管理器系统设计总框图 63.2各模块功能N-S图73.2.1 寻找时间最长的页面功能模块：73.2.2 内存页面输入功能模块： 7四、项目截图 10五、设

3、计程序源代码 1151 源代码 11五、设计心得 18六、参考文献 19虚拟存储器管理系统设计一、设计任务分析本设计的目的是通过设计一个简单的虚拟存储器管理系统来模拟实际的页 面调度算法与过程，以掌握这种有用的技术。要求将其输入/输出处理程序编成 一个独立的进程模块并与其它请求输入/输出的进程并发运行。并要求加入设备 管理子模块。1.1 虚拟存储技术分析：1.1.1 虚拟存储技术概述虚拟存储技术是随着计算机技术的发展而发展起来的。早在 20世纪70年 代，为了克服内存容量小成本高而不适应大型程序应用需要的矛盾，人们开发了 虚拟内存技术。随着计算机技术及相关信息处理技术的不断发展，人们对存储的

4、需求越来越大，单个大容量磁盘已不能适应应用的需要，虚拟存储技术又有进一 步的发展，如在操作系统下将一组硬盘捆绑成带区集（STRIP）作为单个逻辑存 储单元供主机访问；磁盘冗余阵列（RAID）技术将多个物理磁盘通过一定的逻辑 关系集合起来，成为一个大容量的虚拟磁盘。从某种意义上讲， SAN 本身也是虚 拟存储技术的应用。1.1.2虚拟存储技术的概念所谓虚拟存储技术，是指把多个物理上独立存在的存储体通过软件或硬件的 手段集中管理起来，形成一个逻辑上的虚拟存储单元供主机访问。这个虚拟逻辑 单元的存储容量是它所集中管理的各物理存储体的存储容量之和，而它的访问带 宽则在一定程度上接近各个物理存储体的访问

5、带宽之和。虚拟存储实际上是逻辑 存储，是一种智能、有效地管理存储数据的方式。虚拟存储克服了物理存储的局 限，它可以把物理设备变成完全不同的逻辑镜像，呈现给用户，既充分利用了物 理设备的优势，如高性能、高可用，又打破了物理设备本身不可克服的局限性。 从用户角度看，使用存储空间而不是使用物理存储硬件，管理存储空间而不是管 理物理存储部件，这就是虚拟存储的概念。1.2 使用算法分析：1.2.1 FIFO 算法（先进先出淘汰算法）1） 什么是先进先出淘汰算法？当需要淘汰一页时，总是选择主存中居留时间最长（即最老）的一页淘汰。2） 实现方法系统保留一张次序表，该表记录了作业程序的各页面进入主存的先后次序

6、。用数组作次序表可在主存中建立一个m（m是分配给该作业的存储块数）个用存储分块表作次序表该次序表以块号为序，依次各块的分配情况。这里 假定m=4,且4, 5, 1, 2页以依次装入2, 6, 7, 4各存储块中。此时存 储分块表如下图所示：当需要笫6页时将替换第4页1.2.2 LRU算法（最久未使用淘汰算法）1） 什么是最久未使用淘汰算法？ 当需要淘汰一页时，总是选择最长时间未被使用的那一页淘汰。2） 实现方法用硬件实现 此算法每一页可以设置一个 R 位的寄存器； 每次访问一页时，将该页所对应的寄存器的最左一位置 1； 每隔时间 t 将所有的 R 位寄存器右移一位。这样，在T = Rt时间内，

7、方问过的页多对应的寄存器R内时一个不全为0的整数, 而没有访问过的页相对应的R之值为0。当缺页中断时，选择R值最小的那页进 行淘汰。1.2.3 OPT算法（最佳淘汰算法）1） 什么是最佳淘汰算法？当需要淘汰一页时，将选择以后永不使用的或许是在最长(未来)时间内不再 被访问的页面。2) 算法优势采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预 知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问 的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。二、总设计方案2.1、置换算法思想 最佳置换算法(Optimal):它是由Belady于1966年提出的一种

8、理论上的算法。 其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被 访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前 还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再 被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。 先进先出(FIFO)页面置换算法：这是最早出现的置换算法。该算法总是淘汰最 先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现 简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一 个指针，称为替换指针，使它总是指向最老的页面。 LRU置换算法：LRU(Lea

9、st Recently Used)置换算法的描述：FIFO置换算法 性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调 入的先后并不能反映页面的使用情况。最近最久未使用(LRU )置换算法，是根 据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情 况，只能利用“最近的过去”作为“最近的将来”的近似，因此， LRU 置换算法 是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用 来记录一个页面自上次被访问以来所经历的时间t,当须淘汰一个页面时，选 择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。2.2、LRU 置换算法的硬件支持L

10、RU置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。为 了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速 地知道哪一页是最近最久未使用的页面，须有以下两类硬件之一的支持：1）寄存器为了记录某个进程在内存中各页的使用情况，须为每个在内存中的页面配置一 个移位寄存器，可表示R=Rn-lRn-2Rn-3R2R1R0当进程访问某物理块时，要 将相应寄存器的Rn-1位置成1。此时，定时信号将每隔一定时间（例如100ms） 将寄存器右移一位。如果我们把n位寄存器的数看作是一个整数，那么具有最小 数值的寄存器所对应的页面，就是最近最久未使用的页面。如图1示出了某进程 在内存

11、中具有8个页面，为每个内存页面配置一个8位寄存器时的LRU访问情况。 这里，把8个内存页面的序号分别定为18。由图可以看出，第7个内存页面 的R值最小，当发生缺页时首先将它置换出去。表2.1寄存器使用状况2）栈可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某 页面时，便将页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新 被访问页面的编号民，而栈底则是最近最久未使用的页面的页面号。三、程序设计结构图3.1虚拟存储管理器系统设计总框图退出三种算法比较OPT算法L R U算法输入内存页面数系统荒功能描述：通过设计操作系统页面进行比较，选择适合虚拟存储管理系统理想的调度算法

12、。计算羯汰页和缺页计算羯汰页和缺a计算羯汰页和缺页流程图3.2各模块功能N-S图3.2.1 寻找时间最长的页面功能模块算法思想：通过寻找时间最长的页面，为进行FIFO, LRU,ORT三种调度算法运算 提供前提条件。主要参数功能 :Pro *page 用来指向调入内存最长时间的页面int Max (Pro +pagel)Pro +page=new ProN; page=pagel; int e=page 0.ti rri巳 i 二0; while( iN憑出离现在时间最长的页面)if (epagei.time )e=pagei.time; i+；for( i=0;ifriame;一-一_ if

13、 (fp=fopen (fria mer )=NULL )一一一thenelsecout错误文件打不开.请检杳文件名乌图3.2输入模块while( !feof(fp)fecanfffpj %d , Squeue F );N-S 图+；cout读入的页面流二for( i=0;iF;i+)coLJtqueuei7coutri；return F ;入的页FIFO功能模块：算法思想：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久 的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次 序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。算法思想：最近最

14、久未使用（LRU）置换算法，是根据页面调入内存后的使用情 况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去” 作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面 予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问 以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的， 即最近最久未使用的页面予以淘汰。图 3.4 LRU N-S 图四、项目截图图4丄孑刖入可用页数虚拟存储管理器的页面调度请输入功能号 =lH C: User jboss.Desktopzhao.zhao. exe3I请输入功能号5巧：.CB C: VEersjboEEBeEktopzh.aozhao. exe11 2 012 35 2 35 4 35 4 63 4 63 163 154 154 6 54 6 78 6 7缺页次数：13 缺页率：0-722222rn.| II| I|IIIi I. TH II iJl I I I rt