东华大学操作系统存储管理实验报告

东华大学计算机学院

操作系统实验报告

实验名称：存储管理问题 姓名：姜元杰

学 号： 111310228

班 级：计算机1102 指导老师：李继云

报告日期： 2013/11/2

一、 实验概述

1. 实验目标

存储管理的主要功能之一是合理地分配空间。请求页式管理是一种

常用的虚拟存储管理技术。本实验的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。

2. 实验要求

1) 通过随机数产生一个指令序列，共320条指令，指令的地址按下述

原则生成：

● 50%的指令是顺序执行的；

● 25%的指令是均匀分布在前地址部分。

● 25%的指令是均匀分布在后地址部分。

2) 将指令序列变换成页地址流

● 页面大小 = 10条指令

● 4页

● 用户虚存容量 = 32页；

● 在用户虚存中，按每K存放10条指令排列虚存地址

3) 计算并输出下述各种算法在不同内存容量下的命中率。

● 先进先出的算法（FIFO）；

● 最近最少使用算法（LRU）；

● 最佳淘汰算法（OPT）；

● 命中率=1-页面失效次数/页地址流长度；

输出以表结构输出，行头是页码，列头是对应替换算法。在本实验

中，页地址流长度为320，页面失效次数为每次访问相应指令时，该

指令所对应的页不在内存的次数。

二、 实验内容

1. 设计思路

总体思路：

设计存储管理类（class StorageManagemen），封装FIFO，LRU,OPT算法实现函数与各自所需公共或个体数据机构和公共代码部分，实现“TOP-DOWN”的程序设计思想，增强代码结构性和可读性。

1) 先进先出的算法（FIFO）：FIFO是最简单的页置换算法，FIFO的页置

换的算法为每个页记录着该页调入内存的时间。当必须置换一页时，将选择最旧的页。注意并不需要记录调入一页的确切时间，可以创建一个FIFO队列来管理内存中的所有页。队列中的首页将被置换。当需要调入页时，将它加入到队列的尾部。FIFO的页置换算法很好理解和实现，但是，其性能并不是很好。所替代的页可能是很久以前使用的、现已不再使用的初始化模块，另一方面，所替代的页可能包含一个以前初始化的并且不断使用的常用变量。

2) 最近最少使用算法（LRU）：选择最近最长时间未访问过的页面予以淘

汰，默认过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。本实验实现算法通过为每个页面设置一个访问字段，用来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。尽管各类参考书声明LRU算法为堆栈类算法，但本实验通过优先队列完全可以实现。

3) 最佳淘汰算法（OPT）：最佳置换算法所选择的被淘汰页面将是以后永不

使用，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。本实验实现算法通过为每个页面设置一个CPU使用“间隔”——即表示CPU将在未处理的页面序列中第几步处理到该页面，如果页面不再被CPU处理，赋值为极大值（INT_MAX），淘汰页面时选择现有页面中值最大的予以淘汰。本实验同LRU一样，通过优先队列实现。

2. 主要数据结构

1) 公共部分：

class StorageManagement：

◆ const int MAX_OP_NUM：操作页面最大数，默认320

◆ const int MAX_MEMORY_PAGE：用户内存存储物理块数最大值，默认32 ◆ int Page_OP[MAX_OP_NUM]：访问页面序列，随机生成

◆ double Miss：每次访问相应指令时，该指令所对应的页不在内存的次数

◆ double Total：页面置换次数

◆ int TMAX_MEMEORY_PAGE：用户内存存储物理块数

◆ bool isEmpty：内存是否占满

2) 先进先出的算法（FIFO）：

◆ queue q：内存存储队列，先进先出

3) 最近最少使用算法（LRU）：

◆ struct Lpage：

◆ Lpage lPage[MAX_MEMORY_PAGE]：FIFO LRU进程页面

◆ priority_queue q：内存存储优先队列，最近使用次数大者优先级高 ◆ queue qq：LRU中用于修改最近使用时间函数的临时队列

4) 最佳淘汰算法（OPT）：

◆ struct Opage：

◆ Opage oPage[MAX_MEMORY_PAGE]：OPT进程页面

◆

priority_queue q

：内存存储优先队列，CPU使用间隔大者优先级高

◆ queue qq：OPT中用于修改使用间隔的临时队列

3. 主要代码结构

1) 公共部分：

◆ int main()：Main函数菜单界面

◆ void Initial(int n)：用于初始化各算法参数的函数

◆ void Output(int n)：控制输出函数

2) 最近最少使用算法（LRU）：

◆ void alterLateUse(priority_queue&q, int Pos)：

LRU中用于修改内存中页面最近使用时间

3) 最佳淘汰算法（OPT）：

◆ alterDist(priority_queue&q, int n, int *Page_OP)：

OPT中用于修改内存中页面使用间隔 4. 主要代码段分析()

1) 公共部分：

按照实验要求，随机生成320

条随机数指令流，同时转换为页地址流 （分析部分见注释）

2) 先进先出的算法（FIFO）：

主要代码控制部分（（分析部分见注释）：

3) 最近最少使用算法（LRU）：

a) 主要代码控制部分：

b) 修改最近使用时间函数：

◆ 片段1：当待访问页面不在内存存储中，无论内存存满与否，内存中所有页面

最近使用次数增加；

◆ 片段2：

当待访问页面已在内存存储中，对应内存存储页最近使用次数清

0；

4) 最佳淘汰算法（OPT）：

a) 主要代码控制部分：

b) 修改CPU使用间隔函数：

片段1：当待访问页面不在内存存储中且内存已满，需要进行页面置换时，遍

历未处理页面序列，找出内存中

CPU

永不处理页面并替换，否则替换CPU使用

时间最晚（CPU使用间隔）的页面；

片段2：对于内存中CPU永不处理页面，对应CPU使用间隔赋极大值INT_MAX，

实现在优先队列中优先弹出，实现页面置换；

三、 实验结果

1. 基本数据：程序内随机生成。

2. 源代码行数：代码共274行。

3. 完成实验投入时间：累计共12小时

4. 讨论次数：0次

5. 测试结果分析：

测试结果分析：综上比较，帧较少时，OPT算法命中率较高。其次是LRU。

四、 实验体会

1. 实验过程中遇到问题及解决过程

问题：初次完成代码后，发现LRU算法和OPT算法命中率相同。

解决过程：初始阶段，一直在调试OPT算法，后来通过模拟数据，调试发现LRU算法有几处Bug后，之后OPT算法根据结果调试了

很久终于解决问题。

2.

实验体会和收获

页面替换算法实际早在计算机组成原理课中上过，当时仅仅局限于理论理解，

操作系统实验报告

没有进行上机模拟，所以理解比较肤浅，故实验前着重熟悉了各置换算法的原理和实现方式。所谓“谋定而后动”，上机实践还是遵循着程序设计=数据结构+算法的原则，成熟的算法和理想的数据结构可以使程序设计事半功倍。在认真温习原理和设定算法后，基于算法设计数据结构，本实验中根据各置换算法不同特点，分别选用普通队列，优先队列来实现算法。通过实践操作即加深了对于页面置换算法的深刻理解，又熟悉掌握了常用数据结构的用法。尽管调试代码，发现bug非常煎熬（熬夜到半夜才修复所有Bug），但是最后圆满解决问题的成就感也是无与伦比的。

五、 参考文献

[1]. 汤小丹，梁红兵等著. 《计算机操作系统（第三版）》

[2]. 王道论坛组编.

《2013年计算机操作系统联考复习指导》

- 10 -