操作系统_页面置换算法

• 最佳置换算法
• 先进先出(FIFO)置换算法
• 最近最少未使用(LRU)算法

1.最佳置换算法（理想化算法）

淘汰最久不被访问的页面
例题：
系统为某进程分配3个物理块，进程访问页面的顺序是0，7，6，5，7，4，7，3，5，4，7，4，5，6，5，7，6，0，7，6

访问页面	0	7	6
物理块	0	0	0
		7	7
			6

接下来，最佳置换算法的语法就是淘汰最久不被访问的，所以下一个进入的数字是5
（为什么是5，因为看到题目的进程访问页面顺序了吗，就是按着0，7，6，5，7....的顺序来访问的），
那么物理块就只有三个，分别放着0，7，6；那么5要进来，就只能淘汰掉0，7，6中的其中一个，
（为什么？因为物理块只有三个，只能放三个页面啊！！！）
那么问题来了？我5要进来，我是要淘汰谁啊？
我们用的是最佳页面置换算法，这个算法的
语法就是，淘汰掉最久不被访问的那个，
那么我们来看一下
0，7，6我要淘汰最久没被访问的页面，那么我们看访问页面的顺序，会发现
0在第18次再访问，
7在第5 次再访问，
6在第14次再访问，
所以，我们要置换掉0，因为0 是最久未的访问的
结果：

访问页面	0	7	6	5
物理块	0	0	0	5
		7	7	7
			6	6

按照这样的规律就可以最后得到以下的结果:

访问页面	0	7	6	5	7	4	7	3	5	4	7	4	5	6	5	7	6	0	7	6
物理块	0	0	0	5	5	5	5	5	5	5	5	5	5	5	5	5	5	0	0	0
		7	7	7	7	7	7	3	3	3	7	7	7	7	7	7	7	7	7	7
			6	6	6	4	4	4	4	4	4	4	4	6	6	6	6	6	6	6
缺页中断	×	×	×	×		×		×			×			×				×

接下来，我们需要了解一个新的概念

缺页中断：在请求分页系统中，可以通过查询页表中的状态位来确定所要访问的页面是否存在于内存中。每当所要访问的页面不在内存时，会产生一次缺页中断，此时操作系统会根据页表中的外存地址在外存中找到所缺的一页，将其调入内存。

举个通俗的例子:上表有三个物理块，每次往物理块添加数据就会产生一次缺页中断,ok，上表也写上了
所以上表一共发生9次缺页中断

页面置换：就是有页面被置换，所以上表中页面置换是6次
(一开始三个物理块都是空的，添加进076，发生三次缺页中断，0次页面置换，后来的就会发生缺页中断的同时也会发生页面置换，因为三个物理块沾满了吗，所以每添加进新的页面就只能是置换了)

2.先进先出(FIFO)置换算法

闻其名知其意，这个算法就是先进入的页面先被淘汰
Belady想象：一般来说分配的物理块越多，发生的缺页越少，但是FIFO就是这么奇葩，有时候分配的物理块多了，但缺页反而增多，这就是所谓的Belady现象

3.最近最少未使用(LRU)算法

算法：LRU这个算法的名字很多，也有一种叫法叫做最近最久未使用置换算法，这个名字比较好，因为闻其名就知道这个算法怎么搞

这个算法就是看在物理块中的页面，哪个是最久没有被使用的，就把它over掉

接下来来看看例题

访问页面	2	3	4	1
物理块	2	3	4
		2	3
			2

看上面的表，接下来这个1要添加到哪里呢？
432要淘汰那个呢？
看这个算法怎么说：淘汰最近最久未使用的，
首先我们先来看看我们最近使用的是432，那么在这个432里面最近最久没使用的就是2，因为2第一个添加进来，接下来34，都没有使用到2，所以2就是最近最久未使用的，
所以就淘汰2

所以

访问页面	2	3	4	1
物理块	2	3	4	1
		2	3	4
			2	3

ok，接下来，这个最近最久未使用的算法懂了把