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

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


参考资料:


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

虚拟内存机制,让用户的视角中形成了每个进程都可以操作完整 4GB 内存的假象。比如从一个用户代码的角度,它可以随意使用计算机的全部内存地址,就像单独拥有内存(4G)一样。而后续虚拟内存向物理内存的映射,是对用户不可见的。
操作系统学习笔记9 | 内存的换入和换出插图1
这样就很容易产生一个问题:

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

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

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

    而当虚拟内存请求使用3G~4G地址时,换出之前内存上的数据,换入这部分的代码、数据,再将这部分由虚拟内存映射到物理内存上...

  • 通过动态出入物理内存的代码数据,来实现更大空间的虚拟内存映射。

    一个很恰当的例子就是:

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

2. 换入机制及其实现

2.1 换入机制

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

  • 用户代码中的逻辑地址=段号+偏移,此时用户眼中的可用空间是0~4G(32位操作系统);

    客户的商品意愿

  • 根据 学习笔记8 中的逻辑地址向虚拟地址的映射机制,得到虚拟地址:虚拟地址=页号+偏移;此时空用空间也是0~4G。

    客户的商品清单

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

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

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

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

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

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

问题:为什么采用请求调页而不是请求调段?

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

2.2 换入机制实现

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

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

    这部分参见我前面发过的操作系统学习笔记2的 int0x80 执行理解。

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

  4. 接着就是在IDT中找到处理缺页中断的功能代码。

    • 压栈保存现场,切换为内核数据段和代码段;

      这部分依旧参见:操作系统学习笔记2

    • cr2中保存的是引发缺页的地址(页错误线性地址),压栈作为 _do_no_page 的参数;

      虚拟地址也叫线性地址。

  5. 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 介绍的很详细(并且是远古高质量博文)

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

  6. put_page,建立虚拟内存到物理内存的映射,也就是修改页表。

    • 不断通过位运算,分别找到 页目录项 和 页表项
    • 将 读入内存的物理页 page 放入 页表项 page_table[(address>>12)&0x3ff]=page|7;

      右移12位是为了去掉页内偏移,再与 3FF与 是为了只保留页号。然后以 页号 作为索引在 page_table 找到这一页对应的表项。

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

2.3 总结

实现调页换入,主要就是三步:

  1. 申请空闲物理页;
  2. 从磁盘中读入;
  3. 建立映射,修改页表。

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

3. 换出机制及其实现

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

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

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

各个算法的评价准则应当是:缺页次数
操作系统学习笔记9 | 内存的换入和换出插图6

3.1 FIFO

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

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

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

3.2 MIN

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

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

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

3.3 LRU

Least Recently Used.

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

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

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

3.4 LRU的实现

3.4.1 全局时钟+时间戳

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

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

批注:

  1. 这里的关键是维护时机的问题;
  2. 如果不缺页,程序应该是直接通过MMU访问物理地址,内核没有机会进行时间戳或者栈的维护;
  3. 只有在缺页中断的时候内核才有机会接触处理页换出;
  4. 任何在不缺页的时候的数据结构维护都会带来巨大开销;

3.4.2 页码栈

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

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

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

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

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

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

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

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

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

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

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

操作系统学习笔记9 | 内存的换入和换出插图12
下面来分析这种算法:

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

    此时缺页时处理成本变大,并且不止于此:

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

    退化为了 FIFO

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

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

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

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

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

3.6 进程的页框分配问题

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

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

    因为单个进程使用的页框数 n 太大,则内存中能够驻留的进程数量少,系统并行率低

  • 分得太少,则缺页频繁,CPU等待换页时间变长,系统吞吐量太低;

    参考资料:操作系统-进程内存分配 - Jeff的技术栈,这部分对应该博文的 3.7 节页框分配策略。

  • 进程个数与CPU利用率的关系如下图的图像所示:
    • 这个图像的起伏背后的本质原因就是 缺页。
    • 只需要加入一条:内存一定,进程多则页框少。
    • 下图的现象就是 ”颠簸 thrashing“。有的地方也叫 抖动。

操作系统学习笔记9 | 内存的换入和换出插图14
如何合理地分配页框数量进而避免上述”颠簸“呢?这个问题有很多算法,下面提出一种:

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

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

4. 总结

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

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

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

  • 好处:实现了类似于 Windows 虚拟内存概念的超大内存;与Windows 不一样的地方在于,Win 可以自动调大,也可以通过设置关闭(关闭就可能发现内存不够用)。
  • 缺点:与 Windows 一样,实际上还是磁盘与内存之间的通信,速度还是较慢。

操作系统学习笔记9 | 内存的换入和换出插图15
回到最开始,换入换出的机制实现后,虚拟内存就可以投入使用,进而实现了 段页式内存管理

至此,操作系统的核心——内存管理和CPU管理都已了解完毕,后面继续了解设备驱动、文件系统、系统接口以及系统引导初始化,就是完整的 操作系统。

文章来源于互联网:操作系统学习笔记9 | 内存的换入和换出

THE END
分享
二维码