操作系统学习笔记9 | 内存的换入和换出

分段和分页是内存管理的最重要的两个机制，而虚拟内存是实现分段和分页结合的重要方法。为了实现虚拟内存，就必须要有换入和换出机制。

参考资料：

课程：哈工大操作系统（本部分对应 L24 && L25）
实验：操作系统原理与实践_Linux - 蓝桥云课 (lanqiao.cn)
笔记：操作系统学习导引 · 语雀 (yuque.com)

1. 为什么要引入换入和换出

虚拟内存机制，让用户的视角中形成了每个进程都可以操作完整 4GB 内存的假象。比如从一个用户代码的角度，它可以随意使用计算机的全部内存地址，就像单独拥有内存（4G）一样。而后续虚拟内存向物理内存的映射，是对用户不可见的。

这样就很容易产生一个问题：

每个进程的虚拟内存加起来是很可能大于物理内存的，比如下图中，虚拟内存高达4G，物理内存仅有1G，怎么办？

答：用换入、换出实现用户眼中的 “超大内存”：

比如下图中：当虚拟内存请求使用0G~1G地址时，将相应的代码、数据从磁盘换入物理内存，将这部分地址由虚拟内存映射到物理内存上，进行读写操作；

而当虚拟内存请求使用3G~4G地址时，换出之前内存上的数据，换入这部分的代码、数据，再将这部分由虚拟内存映射到物理内存上...
通过动态出入物理内存的代码数据，来实现更大空间的虚拟内存映射。

一个很恰当的例子就是：

厂房（磁盘）很大，而店面（内存）很小，不见得把所有的商品都上架，而当客户（虚拟内存、操作系统）请求某件商品（某段代码、数据）时，快速实现从厂房到店面的切换，就能够满足用户需求。

2. 换入机制及其实现

2.1 换入机制

首先不考虑原先内存的代码和数据。

用户代码中的逻辑地址=段号+偏移，此时用户眼中的可用空间是0~4G（32位操作系统）；

客户的商品意愿
根据学习笔记8 中的逻辑地址向虚拟地址的映射机制，得到虚拟地址：虚拟地址=页号+偏移；此时空用空间也是0~4G。

客户的商品清单
当虚拟内存发出请求，发现地址所在的页不在内存中，则产生缺页中断，执行页错误处理程序，请求调页，从磁盘中读出数据放入内存中，并更新页表；

客户的商品清单中的东西店面上没有，到仓库取换商品。

注意一定有请求，有请求才会有调页。

这有一个小机制可以抠一下：即进程在 load [addr] 时发现地址所在页不在内存中时产生中断，但中断返回后通常是执行中断语句的下一句，即 load [addr] 的下一句

但此处是回来继续执行 load [addr]，只需要在硬件层面加上一些限制，使其在内存缺页中断的时候不自动执行PC+1即可。

问题：为什么采用请求调页而不是请求调段？

请求调页的粒度更细，可以提高内存效率。

2.2 换入机制实现

在代码执行/进程前进的过程中，寻址是硬件 MMU 来做的，一旦在内存中没找到就会中断，软件层面需要考虑的事情就是缺页中断的处理机制。

设置中断：查找硬件手册，看看缺页中断对应的是几号---14号 Page fault. 在系统初始化时，就应当设置14号中断的处理函数；
系统启动时：trap_init，设置14号中断的处理函数：set_trap_gate(14,&page_fault);
set_trap_gate 实现：设置IDT表，在IDT表中初始化缺页中断的处理代码

这部分参见我前面发过的操作系统学习笔记2的 int0x80 执行理解。
接着就是在IDT中找到处理缺页中断的功能代码。
- 压栈保存现场，切换为内核数据段和代码段；
  
  这部分依旧参见：操作系统学习笔记2
- cr2中保存的是引发缺页的地址（页错误线性地址），压栈作为 _do_no_page 的参数；
  
  虚拟地址也叫线性地址。
do_no_page，实现读磁盘换入页并完成映射的功能代码。
- address 是上文cr2 传入的形参，为缺页地址。
- address&=0xfffff000; 得到虚拟页号；
- get_free_page(); 申请物理空闲页；
- bread_page(); 到磁盘上去读入数据到刚分配的页中；
  - bread: block-read，磁盘是一种块设备。
  - current->executable->i_dev，当前进程对应的可执行文件所在的磁盘设备。
- put_page(page,address); 将物理页 page 和虚拟地址 address 建立映射，即填写页表。
  当然下面代码中还有判断是否需要载入 代码和数据的语句，如果不是代码和数据，调用 get_empty_page() 取得一页空闲内存并映射到指定线性地址处。
  - 与 get_free_page() 不同。get_free_page() 仅是申请取得了主内存区的一页物理内存。
    
    而该函数不仅是获取一页物理内存页，还进一步调用 put_page()，将物理页面映射到指定的线性地址处
  - 这里调用该函数的意义是：
    
    若请求调页的进程刚刚开始创建（也符合其地址在内存中找不到的特点，根据缺页中断也会调度到这里，需要考虑这种情况），那么直接获取物理页并映射即可；
    
    另一种可能是，进程已有的页不再满足需要，需要申请新的内存空间，也需要批一片新的物理内存，并映射。
  - 具体判断条件及其参数，详见参考资料：linux0.11内核源码剖析:第一篇内存管理、memory.c_
    
    这一篇博文对于 memory.c 介绍的很详细（并且是远古高质量博文）
put_page，建立虚拟内存到物理内存的映射，也就是修改页表。
- 不断通过位运算，分别找到页目录项和页表项
- 将读入内存的物理页 page 放入页表项 page_table[(address>>12)&0x3ff]=page|7;
  
  右移12位是为了去掉页内偏移，再与 3FF与是为了只保留页号。然后以页号作为索引在 page_table 找到这一页对应的表项。

2.3 总结

实现调页换入，主要就是三步：

申请空闲物理页；
从磁盘中读入；
建立映射，修改页表。

这三件事完成，就实现了用户眼中的超大内存。

3. 换出机制及其实现

有换入必然有换出。前文提到，14号中断的处理程序中page = get_free_page(); ，可以申请获得空闲的物理内存页，但是不断地换入总有一天会将内存占满，这时就需要选择一页换出到磁盘。（提到选择就会有算法）；所以本部分代码应当就在 get_free_page() 中。

常见的基础置换算法如下：

FIFO，先进先出，但是刚换入的页需要被马上换出的情况无法顾及到；
MIN
LRU，本部分重点介绍。

各个算法的评价准则应当是：缺页次数。

3.1 FIFO

如下图所示，假设一个内存仅有 3 个页，在执行ABC时分别放入
接下来继续遇到 ABC时，继续保有其在内存的占用即可；
遇到D时，就需要考虑替换，FIFO 算法中换出最先进入的，即A。
而下图页考虑了一种可能：D刚把A换出去，A又要申请内存；

每次申请都需要磁盘读和分页建表，效率就不高。如下图，FIFO导致了7次缺页。

3.2 MIN

FIFO 算法虽然简单但并不好，那么在上述序列中，换谁最合适？

MIN 算法，选最远使用的页淘汰，这是个最优方案，缺页次数仅为5；
但是这种算法肉眼可见需要预测将来的序列，这在实际的操作系统中是基本不可能完成的；因为无法预测哪一页最晚使用。

3.3 LRU

Least Recently Used.

MIN 算法是一种最优方案，但是它不太可能被实现，因为未来无法准确预测。但就像生活中人们可以通过历史推测未来一样，操作系统也可以根据历史执行情况来判断未来的情况。

LRU，选最近最长时间没有使用的页淘汰，也即最近最少使用；
这也利用了 局部性原理；最近一段时间总被使用的页将来也会频繁使用；
LRU是公认的很好的页置换算法，LRU的缺页次数为 5；

3.4 LRU的实现

3.4.1 全局时钟+时间戳

建立一个全局时钟，每页维护维护一个时间戳，表示这一页的最近使用时刻，每使用该页就更新这个时间戳；
若出现需要页面换出的情况，选择最近使用时间最早的页淘汰，也即上述时间戳最小的页；
这种算法很容易实现，但在实际的操作系统中不大可行：
- 每次执行指令访存时都需要更新时间戳（需要考虑时间戳溢出）
- 换页时还需要遍历找到最小值，而这里的遍历是访存遍历，时间复杂度太高；

批注：

这里的关键是维护时机的问题；

如果不缺页，程序应该是直接通过MMU访问物理地址，内核没有机会进行时间戳或者栈的维护；

只有在缺页中断的时候内核才有机会接触处理页换出；

任何在不缺页的时候的数据结构维护都会带来巨大开销；

3.4.2 页码栈

结合栈这种数据结构来简化算法。

新来的页，如果栈空间还够，就加到栈顶；如果栈空间不够，则淘汰栈底元素，新来的加再加入栈顶
如果内存已有的页又被使用，从栈中原来的位置上浮到栈顶；
这样我们建立的栈，从栈顶到栈底，就是按照最近使用时间戳从大到小的顺序排列的；

注意这里的栈并不是严格意义上的数据结构中的栈，因为在内存中，栈顶指针和栈尾指针可以灵活的控制栈的移动。

下面来看看这个算法的局限性：

首先不能用数组做，因为涉及上浮、删除首元素、尾部加入元素这些操作，如用数组会涉及大量拷贝操作；
用链表 / 指针的话，需要修改指针的次数太多：每次地址访问都需要修改10次左右的栈指针，实现代价很大
因此 LRU算法的准确实现 在实际操作系统中用的很少。

3.5 LRU 近似实现：SCR算法/Clock算法

想法是，在 3.4.1 的基础上，将时间戳改为引用位是和否，采用 ”再给一次机会“ 的策略进行淘汰：

每个页加一个引用位；
每次访问一页时，硬件自动将这个引用位设置为1，在不缺页的情况下维护代价较小（而不缺页正是绝大多数情况）；
需要淘汰页时，扫描每一页的引用位，碰到1则置为0，碰到0则淘汰该页

这里有一点像一把牌进行反转。

LRU是最近最少使用，这种算法是最近没有使用

下面来分析这种算法：

如果缺页很少，那可能会出现所有的引用位 R=1，那么下一次缺页需要淘汰页的时候，需要扫描一圈，把所有的 1 置为 0，然后才能把第一个0的页淘汰掉；

此时缺页时处理成本变大，并且不止于此：

每次扫描都需要扫描几乎一圈，下一次淘汰页时，如果像时钟一样继续从下一个位置开始扫描的话，淘汰的就是下一个位置的页（因为它是0）

退化为了 FIFO
产生的原因：在缺页很少的情况下，历史信息一直没有被清零，记录了太长的历史信息，就无法反映出“最近”这段时间的情况；
所以可以想到的解决方法也就是：定时清除标记位，再加一个扫描指针用于清除，并且这个清除标记指针移动速度要快于页面淘汰指针，很像一个时钟。

Leetcode中有一些算法题，经常会涉及快慢双指针，没想到在这里碰到如此经典且优美的一个应用场景。如下图右下角所示，时针代表使用，分针代表最近：

这也是 SCR 被称为 Clock 算法的原因。

在实际系统中，定时清除历史标记位的分针程序，可以放在时钟中断中，而负责缺页淘汰的时针程序，则放在缺页中断的 get_free_page() 中。两部分配合，就完成了页面选择换出。

3.6 进程的页框分配问题

整个换出机制还有一点漏洞，即：我们应当为一个进程分配多少页框呢？

分多了，那么根据内存的换入换出实现的内存高效利用就没啥用了

因为单个进程使用的页框数 n 太大，则内存中能够驻留的进程数量少，系统并行率低。
分得太少，则缺页频繁，CPU等待换页时间变长，系统吞吐量太低；

参考资料：操作系统-进程内存分配 - Jeff的技术栈，这部分对应该博文的 3.7 节页框分配策略。
进程个数与CPU利用率的关系如下图的图像所示：
- 这个图像的起伏背后的本质原因就是缺页。
- 只需要加入一条：内存一定，进程多则页框少。
- 下图的现象就是 ”颠簸 thrashing“。有的地方也叫抖动。

如何合理地分配页框数量进而避免上述”颠簸“呢？这个问题有很多算法，下面提出一种：

局部性原理；
一个程序在某一段时间内，用到的数据具有空间局部性。我们经常使用一个局部空间内的数据，如果我们分配的页框的数量可以覆盖这个局部空间的大小，那就是足够的；
可想而知，求解局部空间并不容易，但也有许多算法；比如求工作集：这里课程不再细说，详见操作系统-进程内存分配 - Jeff的技术栈
当然，颠簸这个现象在进程过多的时候是无法用算法避免的，所以OS应当限制同时进行的进程的最大数目。

当页框分配完成，再根据 3.5 中的 Clock 算法组成循环链表/环形数组（表盘），通过快慢两个指针进行换出。

4. 总结

换入换出的整体机制其实很好理解。

程序运行，某逻辑地址要求访问内存，MMU 硬件管理单元发现这个逻辑地址在内存中找不到对应位置，启用缺页中断，从磁盘中读页进来。如果内存没有空闲位置可供磁盘读入，则需要 Clock算法选择页进行换出；换出后，有空闲位置，则可继续读入需要的页。

如果安装过Ubuntu（博主反复安装过很多次），需要在磁盘上分配一个 swap 分区，这就是 Linux 的虚拟内存分区。当物理内存不够用的时候，操作系统会从内存中取出一部分暂时不用的数据，放在交换分区swap 中，相当于将这部分磁盘虚拟化成内存使用，从而为当前运行的程序腾出足够的内存空间。