操作系统内存换出---15

有换入，就应该有换出!
小结

有换入，就应该有换出!

上一节主要讲了内存的换入，那么有换入就必须要有换出。

要换出就需要考虑该将当前物理内存中那一部分数据换出，这就涉及到相关算法，就和进程的调度算法一样。

get_free_page

get_free_page用于向物理内存申请一个新的空闲页面，该函数中肯定就包含了换出的逻辑，因此我们来研究一下该函数的实现:

page=get_free_page();
bread_page(page, current->executable->i_dev, nr);
1
2

并不能总是获得新的页，内存是有限的
在这里插入图片描述

FIFO页面置换

在这里插入图片描述
FIFO算法好吗?

评价一个算法的好坏，要看该算法在当前场景下，是否符合我们的优化目标，我们的目标是换出一个最不经常会被使用到的页，尽可能减少缺页次数。

但是FIFO算法在挑选要换出的页时候，并没有考虑到当前页是否经常被使用到，因此FIFO算法并不适合当前的场景。

MIN页面置换

在这里插入图片描述
min算法需要知道将来每个页的使用时间，将最晚使用到的页先换出，但是这也是该算法的致命缺陷，因为我们无法知道某个页将来什么时候会被使用到。

LRU页面置换

在这里插入图片描述
LRU算法高效的原因很大程度上也是因为利用了程序的局部性特点。

LRU的准确实现，用时间戳

在这里插入图片描述
每执行一条指令，都需要进行地址翻译，还要去修改上面这张表中的时间戳，并且还需要考虑溢出情况，这样的实现代价显然过于大了。

前面无论是多级页表还是TLB，都是为了尽可能减少访存次数，从而提高指令执行效率，因此这里换出算法的设计也必须要考虑到这一点。

LRU准确实现，用页码栈

在这里插入图片描述
每执行一条指令，需要额外访存多次，显然也不是我们想要的结果。

LRU近似实现 - 将时间计数变为是和否

在这里插入图片描述

一开始，所有物理页对应的引用位都为0，表示最近都没有被使用过
当程序访问了其中某个页的时候，会将其对应的引用位设置为1，表示最近使用了
而当需要进行换出页时，就将当前指针指向的引用位为1的页清零(下次如果还没被使用，就淘汰你)，然后如果遇到了引用位为0的页，就进行淘汰

Clock算法的分析与改造

在这里插入图片描述
由于程序的局部性原理，导致产生缺页现象会比较少。

缺页产生的比较少，就会导致大量页的引用位被设置为了1，这样当产生了缺页后，整个Clock 算法就退化了FIFO算法了，这显然不合适。

原始的Clock 算法其实是用最近没有使用的思想来近似最近最少使用，但是这样容易导致算法退化了FIFO。

为了体现最近最少使用的思想，就额外引入了一个定时清除R位的指针，定时清除指针会定时将当前指向页面的引用位设置为0，然后往后移动一格。

引入了定时清除指针之后，就可以将那些最近没有被使用到的页的引用位清零，这样就避免由于淘汰指针移动过慢，导致大量近期没有被使用到的页的引用位依旧为0，和近期被使用的页的引用位一样，那么当需要进行页淘汰时，就无法区分出哪一个页是最近最少使用的了，加入定时清除R位后，就符合最近最少使用的思想了，大家好好体会一下。