存储器管理实验报告

操作系统实验报告

2012 年 12 月 24 日

学 专

号 业

1008114124

姓

名

L 刘凯利 班 级

时

间

12 月 27 日 计科二班

计算机科学与技术

实验题目： 存储器管理 实验目的： 1.通过模拟实现最佳页面置换的算法，熟悉存储器管理方式； 2.掌握虚拟存储请求页式存储管理中几种页面置换算法的基本思想， 并用三 种至少三种算法来模拟实现； 3.比较对几种置换算法页面，对比他们的优缺点，并通过比较更换频率来对 比它们的效率； 实验原理： 为了提高内存利用率，提供了内外存进程对换机制， 内存空间的分配和回收 均以页为单位进行，一个进程只需将其一部分（段或页）调入内存便可运行。当 进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立 即提出请求（向 CPU 发出缺中断） 由系统将其所需页面调入内存。 如果进程的许多页是存放在外存的一个连续区域中， 则一次调入若干个相 邻的页， 会比一次 调入一页的效率更高效一些。 但如果调入的一批页面中的 大多数都未被访问， 则又是低效的。 可采用一种以预测为基础的预调页策略， 将那些预计在不久之后便会被访问的页面， 预先调 入内存。如果预测较准确， 那么，这种策略显然是很有吸引力的。但目前预调页的成功率仅 为 50%。且这 种策略主要用于进程的首次调入时，由程序员指出应该先调入哪些页。 当进程在运行中需要访问某部分程序和数据时， 若发现其所在的页面不在 内存，便即提出请求，由 OS 将其所需页面调入内存。由请示调页策略所确定调 入的页，是一定会被访问的， 再加之请求调页策略比较易于实现，故在目前的 虚拟存储器中，大多采用此策略。但这种策 略每次仅调入一页，故须花费较大 的系统开销，增加了磁盘 I/O 的启用频率。

实验步骤： 1. 先进先出(FIFO)置换算法 通过淘汰最先进入内存的页面， 即选淘汰在内存中驻留时间最久的页面。该 算法实现简单，只需把一个进程已调入内存的页面，按照先后次序 连接成一个 队列，并设置一个替换指针，使它总指向最老的页面。 2. 最近久未使用(LRU)置换算法 根据页面调入内存后的使用情况来进行决策的， 赋予每个页面一个访问字段， 用来记录一个页面自上次被访问 以来所经历的时间， 当需淘汰一个页面的时候 选择现有页面中其时间值最大的进行淘汰。 3. 最佳（OPT）置换算法 所选择的被淘汰的页面，将是以后不使用的，或者是在未来时间内不再被访 问的页面，采用最佳算法，通常可保证获得最低的缺页率。 常用函数：void FIFO( ):计算使用 FIFO 算法时的命中率，void LRU( ):计算使用 LRU 算

法时的命中率， void OPT( ):计算使用 OPT 算法时的命中率， total_pf: 用户进 int 程的内存页面数，int disaffect: 页面失效次数. 程序 Main.cpp: #include #include #include #include #include #include using namespace std; #define INVALID -1 const int TOTAL_INSTRUCTION(320); const int TOTAL_VP(32); const int CLEAR_PERIOD(50); #include 1;// 不在内存就加 1 统计缺页次数 if(_pFreepf_head==NULL) 第一个置换出。*/ { p=_pBusypf_head->m_pNext; _vDiscPages[_pBusypf_head->m_nPageNumber].m_nPageFaceNumber=INVALID;// 要置换出，所以置-1 _pFreepf_head=_pBusypf_head;/*每次都把忙队列的头给让出，则是先 来先服务*/ _pFreepf_head->m_pNext=NULL; _pBusypf_head=p; } p=_pFreepf_head->m_pNext;//有空闲页面 _pFreepf_head->m_pNext=NULL; _pFreepf_head->m_nPageNumber=_vPage[i]; _vDiscPages[_vPage[i]].m_nPageFaceNumber=_pFreepf_head->m_nPageFaceNumbe r; if(_pBusypf_tail==NULL) _pBusypf_head=_pBusypf_tail=_pFreepf_head; else { _pBusypf_tail->m_pNext=_pFreepf_head; _pBusypf_tail=_pFreepf_head; } _pFreepf_head=p; } /*无空闲页面，进行置换，找出忙队列的

} cout

#ifndef _PAGE_H #define _PAGE_H class CPage { public: int m_nPageNumber,//磁盘上的页号 m_nPageFaceNumber,//内存中的页号 m_nCounter, m_nTime; }; #endif 内存页面结构： PageControl.h: #ifndef _PAGECONTROL_H #define _PAGECONTROL_H

class CPageControl { public: int m_nPageNumber,m_nPageFaceNumber; class CPageControl * m_pNext; }; #endif

实验结果与分析： 1. 实验结果： FIFO: 0.534375 FIFO: 0.55 LRU: 0.534375 OPT:0.6375

LRU: 0.546875

OPT:0.6625 OPT:0.6875

FIFO: 0.56875

LRU: 0.559375

FIFO: 0.571875 FIFO: 0.590625 FIFO: 0.6125 FIFO: 0.628125 FIFO: 0.646875 FIFO: 0.659375 FIFO: 0.675 FIFO: 0.70625 FIFO: 0.721875 FIFO: 0.7375 FIFO: 0.753125 FIFO: 0.7625 FIFO: 0.765625 FIFO: 0.778125 FIFO: 0.79375 FIFO: 0.815625 FIFO: 0.815625 FIFO: 0.834375 FIFO: 0.859375 FIFO: 0.865625 FIFO: 0.86875 FIFO: 0.86875 FIFO: 0.875 FIFO: 0.88125 FIFO: 0.884375 FIFO: 0.9 2. 结果分析：

LRU: 0.56875 LRU: 0.58125

OPT:0.709375 OPT:0.73125

LRU: 0.6 OPT:0.75 LRU: 0.6125 LRU: 0.640625 LRU: 0.66875 OPT:0.765625 OPT:0.78125 OPT:0.796875

LRU: 0.68125

OPT:0.809375 OPT:0.821875

LRU: 0.690625

LRU: 0.709375 OPT:0.834375 LRU: 0.73125 OPT:0.84375 OPT:0.853125

LRU: 0.746875 LRU: 0.7625

OPT:0.859375 OPT:0.865625 OPT:0.871875 OPT:0.875 OPT:0.878125 OPT:0.88125 OPT:0.884375

LRU: 0.784375 LRU: 0.803125 LRU: 0.803125 LRU: 0.815625 LRU: 0.834375 LRU: 0.840625 LRU: 0.85 LRU: 0.8625 LRU: 0.875

OPT:0.8875 OPT:0.890625 OPT:0.89375 OPT:0.896875

LRU: 0.890625 LRU: 0.89375

OPT:0.9 OPT:0.9 OPT:0.9

LRU: 0.896875 LRU: 0.896875 OPT:0.9

LRU: 0.9

理论上，三种置换算法的命中率由高到底排列应该是 OPT>LRU>FIFO。 实际 上， 从实验数据观测得到， 存在这种由高到低的趋势， page=4 时可以观测到， 由

但是效果不是很明显。 效果不明显的原因： 推测与指令流的产生方式有关系。 因为指令流的产生方式要能体现局部性原 理，所以该指令流产生设计为：50%的指令是顺序执的，25%的指令是均匀分布在 前地址部分，25%的指令是均匀分布在后地址部分。但是这样的指令流设计方式 能否最佳地体现局部性原理，这还有待验证。 同时，估计和指令数量有关系。因为 320 条指令太少了，通常一个稍大点 的程序都几千行指令了。 而且由于随即数产生具有一定的波动性，该命中率的计算也有一定的波动 性。所以会有局部的实验数据与理论不符。改进方法是多次实验取平均值，这样 可以减小波动，让实验数据更加平滑。 唯一显著的是 OPT 算法的命中率与其他 2 个调度算法保持了比较大的差 距。到后期，由于 page 越来越大，因此越来越容易命中，因此各替换算法的命 中率差距变小了。这由最后几行命中率相似可以看出。 分析与体会： 页面置换算法，是属于存储器管理, 在进程运行过程中，若其访问的页面

不在内存而需把它们调入内存，但内存以已无空闲空间时，为了保证该进程能 正常的运行，系统必须从内存中调出一页程序或数据送磁盘的兑换区中，但应 将哪个页面调出，需根据一定的算法来确定。通常，把选择换成页面的算法称 为页面置换算法。通过本次课程设计，我对页面置换算法的了解更加的深刻。 主要有以下置换算法：OPT（最佳置换算法）、FIFO（先进先出置换算法）、LRU （最近最久未使用算法） 、简单 Clock 置换算法、LFU 最少使用置换算法） 。 （ 每种算法都有各自的优缺点，OPT 算法是实际中不能实现的，但是可以利用该 算法去评价其它算法；FIFO 算法与进程实际运行的规律不相适用，因为在进程 中，有些页面经常被访问；LRU 算法是根据页面调入内存后的使用情况进行决 策的；Clock 算法是 LRU 的近似算法，但它不要求太多的硬件支持；LFU 算法 并不能真正的反应页面的使用情况。在这次课程设计中，遇到了一些困难，例 如怎么实现可视化，如何接收数据，显示数据，及对数据的限制操作等，在遇 到这些困难的时候，我会去查阅资料，仔细看书，尝试用不同的方法解决，在

各种方法中选择一种最好的方法，有的时候会碰到不会用的控件或函数，我会 查看 MSDN，这次是用的Ｃ++语言做的，这次课程设计我最大的收获是学以致 用，通过这次设计我看到了自己学习的能力，我相信在以后的学习中，我会更 加的努力。

实验指导教师

李双群

实验成绩