内存换入与换出

提示：以下是本篇文章正文内容

一、内存换入

executable->i_dev, nr); put_page(page, address);

先分配一个空闲页给page,然后将磁盘里面的页读到内存中，调用put_page建立映射，最后再次执行load[addr]

(4)建立映射put_page

二、内存换出 1.引入换出

由于物理内存大小是有限的，在内存换入多次后，物理内存就会满，因此必须换页，才能腾出空间给新换入的页。

换页的核心问题是需要选择一页淘汰，换出到磁盘，选择哪一页？类似于进程调度

2.FIFO算法

即每次缺页的时候就替换掉最开始的那一页（先进先出） 在第一次换D的时候将A换入，但是后面紧跟着又要换入A… 这种算法在这个方面肯定不是最好的算法，因为它没有任何机制保证替换次数尽可能少

3.MIN算法

选最远（不常用的）将使用的页淘汰， 是最优方案 但是，MIN需要知道将来发生的事，在实际中不可行

4.LRU算法

选最近最长一段时间没有使用的页淘汰(最近最少使用)

用过去的历史预测将来，可以通过前面调用的页的顺序来推测未来哪些页是常用的，理论基础就是程序的空间局部性。

实现一：时间戳

用时间戳来记录每页的访问时间 第一次将A放入页框中，并记录当前时间为1；第二次将B放入页框中，并记录当前时间为2；第三次将C放入页框中，并记录当前时间为3；第四次又是访问A页，更新A页访问时间，第五次访问B页，更新B页访问时间；第六次访问D页，不存在，那么就在A、B、C页中选择一个最早使用的也就是数字最小的替换，即C页。

理论上算法可行，但是，每次地址访问都需要修改时间戳， 需维护一个全局时钟， 需找到最小值 … 实现代价较大

实现二：页码栈

每次选择栈底换出 每次地址访问都需要修改栈(修改10次左右栈指针) … 实现代价仍然较大

5.Clock算法

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

实现这一算法：Second Chance Replacement（再给一次机会）

具体思想：每页增加一个引用位( R )，每一次访问该页时，就将该位置为1。当发生缺页时用一个指针查看每一页的引用位，如果是1则将其置为0，如果是0就直接淘汰。

每次访问一页时， 硬件自动设置该位 选择淘汰页： 扫描该位， 是1时清0， 并继续扫描； 是0时淘汰该页

这种方法提高了内存的效率，只要维护R位（在PCB中）

但是，如果缺页很少，可能会出现所以的R为1（在实际中，缺页的情况不会很多；如果缺页很多了，说明内存太小了或者算法不行）

当发生缺页时，指针转一圈之后将所有的页的引用位都置为0，没找到能替换的，继续转，这时候发现最开始的页引用位为0，将其换出，指针后移

然后又一段时间没有发生缺页，所有页的引用位都为1，当发生缺页之后，又会将这一轮最开始的页换出，然后指针后移，一段时间之后发生缺页，又会将这一轮最开始的页换出，这不就直接退化为FIFO了吗？

原因：记录了太长的历史信息

解决：定时清除R位 再加一个指针用来清除每一页的引用位（这个指针的移动速度要快），可以放在时钟中断里面，定时清除

三、帧frame

现在置换策略有了，但是还有一个问题：给进程分配多少个页框(帧frame)?

如果分配多，请求调页导致的内存高效利用就没有用。而且内存就那么大，如果每一个进程分配很多的话，跑的进程数量就少了。

如果分配的少，系统内进程增多，每个进程的缺页率增大，当缺页率大到一定程度，进程就会总等待调页完成，导致cpu利用率降低，这一现象为颠簸(thrashing)

所以，先给进程分配一定数量的页框，如果增加页框能增加cpu利用率，就缓慢增加，如果导致cpu利用率减少，就降低页框分配。当然实际情况下每个进程对应的页框数量肯定是得动态调整的。

总结

提示：这里对文章进行总结：

内存的换入与换出大致过程：