内存置换算法

‘壹’ 操作系统课程设计，用C#实现内存页面的置换。实现算法间比较

页面置换算法

一．题目要求：

通过实现页面置换算法的FIFO和LRU两种算法，理解进程运行时系统是怎样选择换出页面的，对于两种不同的算法各自的优缺点是哪些。

要求设计主界面以灵活选择某算法，且以下算法都要实现 1) 最佳置换算法(OPT)：将以后永不使用的或许是在最长(未来)时间内不再被访问的页面换出。

2) 先进先出算法(FIFO)：淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

3) 最近最久未使用算法(LRU)：淘汰最近最久未被使用的页面。 4) 最不经常使用算法(LFU) 二．实验目的：

1、用C语言编写OPT、FIFO、LRU，LFU四种置换算法。 2、熟悉内存分页管理策略。 3、了解页面置换的算法。 4、掌握一般常用的调度算法。 5、根据方案使算法得以模拟实现。 6、锻炼知识的运用能力和实践能力。 三、设计要求

1、编写算法，实现页面置换算法FIFO、LRU；

2、针对内存地址引用串，运行页面置换算法进行页面置换； 3、算法所需的各种参数由输入产生（手工输入或者随机数产生）； 4、输出内存驻留的页面集合，页错误次数以及页错误率；

四．相关知识：

1．虚拟存储器的引入：

局部性原理：程序在执行时在一较短时间内仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域，它主要表现在以下两个方面：时间局限性和空间局限性。

2．虚拟存储器的定义：

虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。

3．虚拟存储器的实现方式：

分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。

请求分段系统，它是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。

4．页面分配：

平均分配算法，是将系统中所有可供分配的物理块，平均分配给各个进程。 按比例分配算法，根据进程的大小按比例分配物理块。

考虑优先的分配算法，把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据个进程的优先权，适当的增加其相应份额后，分配给各进程。

5．页面置换算法：

常用的页面置换算法有OPT、FIFO、LRU、Clock、LFU、PBA等。 五、设计说明

1、采用数组页面的页号

2、FIFO算法，选择在内存中驻留时间最久的页面予以淘汰；

分配n个物理块给进程，运行时先把前n个不同页面一起装入内存，然后再从后面逐一比较，输出页面及页错误数和页错误率。

3、LRU算法，根据页面调入内存后的使用情况进行决策；

同样分配n个物理块给进程，前n个不同页面一起装入内存，后面步骤与前一算法类似。

选择置换算法，先输入所有页面号，为系统分配物理块，依次进行置换： 六．设计思想：

OPT基本思想：

是用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。数组next[mSIZE]记录物理块中对应页面的最后访问时间。每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。

FIFO基本思想：

是用队列存储内存中的页面，队列的特点是先进先出，与该算法是一致的，所以每当发生缺页时，就从队头删除一页，而从队尾加入缺页。或者借助辅助数组time[mSIZE]记录物理块中对应页面的进入时间，每次需要置换时换出进入时间最小的页面。

LRU基本思想：

是用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。数组flag[10]标记页面的访问时间。每当使用页面时，刷新访问时间。发生缺页时，就从物理块中页面标记最小的一页，调出该页，换入所缺的页面。 七．流程图：

如下页所示

六．运行结果： 1. 按任意键进行初始化：

2. 载入数据：

3. 进入置换算法选择界面：

4.运算中延迟操作：

5.三种算法演示结果：

‘贰’ 请简述什么是置换算法和替代算法，并分别给出置换算法和替代算法的实例

LRU是Least Recently Used的缩写，即最近最少使用页面置换算法，是为虚拟页式存储管理服务的。
LRU算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个，就是着名的局部性原理——比内存速度还要快的cache，也是基于同样的原理运行的。因此，我们只需要在每次调换时，找到最近最少使用的那个页面调出内存。这就是LRU算法的全部内容。
这是一个相当好的算法，它是理想算法很好的近似。

‘叁’ 虚拟内存 (页面置换算法的模拟实现)

问计算机老师去

‘肆’ 请分别给出三种不同的页面置换算法,并简要说明他们的优缺点

[fifo.rar]
-
操作系统中内存页面的先进先出的替换算法fifo
[先进先出页面算法程序.rar]
-
分别实现最佳置换算法(optimal)、先进先出(fifo)页面置换算法和最近最久未使用（LRU）置换算法，并给出各算法缺页次数和缺页率。
[0022.rar]
-
模拟分页式虚拟存储管理中硬件的地址转换和缺页中断，以及选择页面调度算法处理缺页中断
[Change.rar]
-
用java实现操作系统的页面置换
其中包括
最佳置换算法(Optimal)、先进先出算法（First-in,
First-out）
、最近最久不用的页面置换算法（LeastRecently
Used
Replacement）三种算法的实现
[M_Management.rar]
-
操作系统中内存管理页面置换算法的模拟程序，采用的是LRU置换算法
[detail_of_44b0x_TCPIP.rar]
-
TCPIP
程序包加载到44b0x
的ADS1.2工程文件的说明书。说名了加载过程的细节和如何处理演示程序和代码。演示代码已经上传，大家可以搜索
[.rar]
-
java操作系统页面置换算法：
（1）进先出的算法（fifo）
（2）最近最少使用的算法（LRU）
（3）最佳淘汰算法(OPT)
（4）最少访问页面算法(LFU)
（注：由本人改成改进型Clock算法）
（5）最近最不经常使用算法(NUR)

‘伍’ lru算法是什么呢

LRU算法是最少使用页面置换算法（Least Recently Used），首先置换近期最长时间以来没被访问的页面，是为虚拟页式存储管理服务的。

LRU算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。

LRU原理

该思想最初用于计算机操作系统中，内存中的容量较有限，为了能更加合理的利用内存中的性能，对用户的使用作出假设，最近最少使用的越不重要，最近使用的越有可能使用到，使得该元素更容易获取到。

如果元素当前容量超过了内存最大容量，则需要删除掉最近最少使用的元素。在其之后，许多缓存及许多分布式系统都采用才思想。

‘陆’ 内存页面置换算法代码

没有仔细看，但发现了一个很容易发生的错误，即函数参数的传递问题。
Init()的最后一句insert(node,head),因为C语言里函数参数采用值传递，那么insert函数执行前head为NULL，执行时，程序会生成一个临时的值为NULL的指针变量作为参数来处理,函数执行完后,head仍为NULL，没有任何改变。因此，就算循环执行了20次，head仍为NULL.

‘柒’ FIFO调度算法和LRU算法

FIFO：先进先出调度算法
LRU：最近最久未使用调度算法

两者都是缓存调度算法，经常用作内存的页面置换算法。

打一个比方，帮助你理解。

你有很多的书，比如说10000本。
由于你的书实在太多了，你只能放在地下室里面。
你看书的时候不会在地下室看书，而是在书房看书。
每次，你想看书都必须跑到地下室去找出来你想看的书，
然后抱回来放到书桌上，之后才开始看。
还有就是，有一些书你会反复的看，今天看了也许过几天又要看。
总之，你自己是不知道你哪天会需要看哪本书的。
你的老师每天下课的时候会给你布置一个书单，让你晚上回去去看哪本书。
（假设你老师让你看的书在你的地下室里面都有）

跑地下室当然是非常麻烦的，所以你希望你的经常看的那些书最好放在书桌上。
但是你的书房的书桌同时只能摆放10本书（这个是假设的啊）。
那么，问题来了。
到底把哪些说留在书桌上最好呢？
这里说的最好，就是说你尽量少的跑地下室去找书。

为了解决这个问题，人们发明了很多的算法。
其中，比较常见的就是上面这两种：FIFO算法和LRU算法。

FIFO算法
很简单，我把书桌上的10本书按照放置时间先后堆放成一堆。
这里的放置时间，就是说这本书在我的书桌上放了几天了。
每次要看书的时候，我先在书桌上找，找到就直接可以读了。
读完之后放回原来的位置就可以，不打乱顺序。
如果书桌上面没有我要读的书，就去地下室找。
找来之后，我就把书桌上放的时间最长的那本（也就是
书堆里面最下面的那本书）放回地下室。
然后把我今天需要看的这本书放在书堆的最上面。

LRU算法
也不难，我把书桌上的10本书按照阅读时间先后堆放成一堆。
这里的阅读时间，就是说我最近一次读这本书是几天之前。
每次要看书的时候，我先在书桌上找，找到就直接可以读了。
读完之后放在书堆的最上面。
如果书桌上面没有我要读的书，就去地下室找。
找来之后，我就把书桌上最久没有阅读的那本
（也就是书堆里面最下面的那本书）放回地下室。
然后把我今天需要看的这本书放在书堆的最上面。

上面这个比方，相信你可以看明白吧。
这里的地下室对应内存，书桌对应缓存，书对应页面。

‘捌’ 采用首次适应算法和最优置换算法,对内存的分配和回收速度会造成什么不同的影响

首次适应分配算法(FF):
对空闲分区表记录的要求是按地址递增的顺序排列的，每次分配时，总是从第1条记录开始顺序查找空闲分区表，找到第一个能满足作业长度要求的空闲区，分割这个空闲区，一部分分配给作业，另一部分仍为空闲区。
最佳置换算法（OPT):
选择以后永不使用或在最长时间内不再被访问的内存页面予以淘汰。

‘玖’ FIFO和LRU置换算法的问题

FIFO 先进先出
-------------
刚开始内存为空 null, null, null
使用2，缺页读入 2, null, null
使用3，缺页读入 2, 3, null
使用2，直接使用 2, 3, null
使用1，缺页读入 2, 3, 1
使用5，缺页读入 3, 1, 5 因为2是最先读入的，所以就把它删掉
使用2，缺页读入 1, 5, 2
使用4，缺页读入 5, 2, 4
使用5，直接使用 5, 2, 4
使用3，缺页读入 2, 4, 3
使用2，直接使用 2, 4, 3
使用5，缺页读入 4, 3, 5
使用2，缺页读入 3, 5, 2

共9次缺页
========================

LRU 会删除最不常访问的
----------------------
刚开始内存为空 null, null, null
使用2，缺页读入 2, null, null
使用3，缺页读入 3, 2, null
使用2，直接使用 2, 3, null
使用1，缺页读入 1, 2, 3
使用5，缺页读入 5, 1, 2 因为最近1和2都访问过而3是很早之前用过的，所以就把它删掉
使用2，直接使用 2, 5, 1
使用4，缺页读入 4, 2, 5
使用5，直接使用 5, 4, 2
使用3，缺页读入 3, 5, 4
使用2，缺页读入 2, 3, 5
使用5，直接使用 5, 2, 3
使用2，直接使用 2, 5, 3

共7次缺页

‘拾’ 虚拟存储器采用的页面调度算法是“先进先出”（FIFO）算法吗

虚拟存储器采用的页面调度算法是“先进先出”（FIFO）算法吗。常见的替换算法有4种。

①随机算法：用软件或硬件随机数产生器确定替换的页面。

②先进先出：先调入主存的页面先替换。

③近期最少使用算法（LRU，Least Recently Used）：替换最长时间不用的页面。

④最优算法：替换最长时间以后才使用的页面。这是理想化的算法，只能作为衡量其他各种算法优劣的标准。

虚拟存储器的效率是系统性能评价的重要内容，它与主存容量、页面大小、命中率，程序局部性和替换算法等因素有关。

(10)内存置换算法扩展阅读

虚拟存储器地址变换基本上有3种形虚拟存储器工作过程式：全联想变换、直接变换和组联想变换。任何逻辑空间页面能够变换到物理空间任何页面位置的方式称为全联想变换。每个逻辑空间页面只能变换到物理空间一个特定页面的方式称为直接变换。

组联想变换是指各组之间是直接变换，而组内各页间则是全联想变换。替换规则用来确定替换主存中哪一部分，以便腾空部分主存，存放来自辅存要调入的那部分内容。

在段式虚拟存储系统中，虚拟地址由段号和段内地址组成，虚拟地址到实存地址的变换通过段表来实现。每个程序设置一个段表，段表的每一个表项对应一个段，每个表项至少包括三个字段：有效位(指明该段是否已经调入主存)、段起址(该段在实存中的首地址)和段长(记录该段的实际长度)。