4.2 物理内存管理
换页机制
换页
不知道大家有没有设置过电脑的虚拟内存. 这个虚拟内存其实是操作系统向磁盘借了一块空间, 用来放放不下的东西.
比如说我现在要跑两个都需要 3GB 的程序, 但是我只有 4GB 的内存, 这个时候就轮到虚拟内存登场了. 当出现这种物理内存放不下的情况, 操作系统会把一些看上去暂时用不上的物理页放到磁盘上, 这就是 换页机制 . 当然, 程序是感知不到的, 对于程序来说能用的空间还是那么大, 毕竟虚拟内存不受物理内存大小限制.
操作系统会在磁盘上划分专门的 swap 分区, 之后触发缺页异常, 如果是已经分配了但是没找到对应的物理地址, 那就会触发物理内存页的换入换出.
不过物理页的换入不会等到物理内存耗尽了才进行, 物理内存快满的时候就开始了. 这样可以腾出更多的内存空间.
优劣势
换入和换出时的位置可能不太一样, 这样可以实现物理内存的按需分配, 节约内存资源.
不过代价是缺页异常会导致访问延迟增加, 毕竟要从磁盘里读. 从磁盘读是很慢的, 比从内存还要慢.
平衡手段
为了取得平衡,
应用程序访存应该具有时空局限性
在缺页异常处理函数中采用预取(prefetching)机制
要精心设计换出策略, 尽量减少缺页异常的次数
页替换策略
理想情况
先来假定一个非常理想的情况, 那就是操作系统清楚地知道哪些物理页会被访问, 并且知道它们的顺序.
比如现在有 6 个物理页在磁盘里, 从 1 到 6 编号, 它们的访问顺序是这样的:
3, 2, 3, 1, 4, 3, 5, 4, 2, 3, 4, 3
但是内存空间只能容纳三个物理页, 接下来应该依次换出哪些页, 才能实现最少的缺页异常?
那么现在浅浅分配一下. 首先访问 3, 那肯定要先换人 3
现在物理内存里有物理页 3
然后访问 2, 2 换进来
3, 2
然后还是 3, 不用换入
3, 2
然后是 1 了
3, 2, 1
MIN 策略
到了这里要访问 4 了, 但是物理内存放不下, 应该要把其中一个换出来了. 在这里有很多策略, 首先是 MIN 策略 :
很明显未来不再访问 1 了, 可以放心地把 1 换出去.
MIN 策略就是选择未来不会再访问的页, 或者最长时间内不再访问的页.
3, 2, 4
然后是 3, 不用换入
3, 2, 4
然后是 5 了, 234 之后都要访问, 不过最晚访问的是 3, 等到那个时候再换入吧, 现在先换出 3.
5, 2, 4
然后是 4, 不用换入
5, 2, 4
然后是 2
5, 2, 4
要访问 3 了, 后面 5 不再访问了, 可以把 5 换出去
3, 2, 4
接下来 4 和 3 都不再发生换入或换出
这就是 MIN 策略, 但是缺点也挺明显的, 我必须要知道未来发生的事情才能完美地解决换入换出问题. 这是很难的. 不过我听说现在有研究利用机器学习什么的, 预测未来的物理页访问情况, 不过我对机器学习没什么兴趣呢.
FIFO 策略
FIFO 策略, 先进先出. 字面意思, 把最先进来的换出去. 这是偏向实际的策略.
还是访问 4, 要换出了. 最先进来的是 3, 那就把 3 换出去吧.
2, 1, 4
接下来访问 3, 最先进来的是 2, 那就换出 2 吧.
1, 4, 3
FIFO 策略就不多写了, 反正是先进先出.
Second Chance 策略
Second Chance 策略是 FIFO 策略的改进版. 顾名思义, 给原本要换出的物理页第二次机会.
当访问一个物理页时, 如果这个物理页已经换入到物理内存了, 那就给这个物理页一个标记. 之后如果要换出这个物理页, 把它放到队尾, 再给它一次机会.
现在从头开始, 先访问 3
3
然后 2
3, 2
又是访问 3, 给物理页 3 做个标记
, 2
访问 1
, 2, 1
现在访问 4 了, 要换出. 如果按照 FIFO 策略的话要换出 3 了, 但是 3 有标记, 那再给 3 一次机会吧. 把 3 放到队尾, 把 2 换出去
2, 3, 4
现在又访问 3 了, 再给 3 一个标记
2,
4
访问 5, 要换出 2. 2 没有标记, 那就直接换出了.
, 4, 5
LRU 策略
LRU, 全称 Least Recently Used, 选择最久没有被访问的页.
LRU 要求维护一个链表, 用链表来记录访问过程, 新访问的移动到尾端, 要换出时换出首端页.
现在再一次从头开始吧.
访问 3
3
访问 2
3, 2
访问 3, 新访问的放到尾端
2, 3
访问 1
2, 3, 1
访问 4, 把首端换出来
3, 1, 4
访问 3
1, 4, 3
之后都是这样子.
手写 LRU 策略
虽然我对操作系统挺感兴趣的, 不过还是改日吧.
MRU 策略
MRU 策略是选择最近被访问过的页, 跟 LRU 相反呢.
页替换策略的评估
如果页替换策略选择不好, 就可能出现物理页刚被换出去, 就要被换入了. 这样频繁的换入换出严重降低性能, 叫 颠簸现象(thrashing) .
直接原因
过于频繁的缺页异常(物理内存总需求过大)
大部分 CPU 时间都被用来处理缺页异常了. 一直在等待慢的要死的磁盘 IO, 只有一小部分时间在工作.
我也想做这样的 CPU, 可以一直摸鱼
调度器造成问题加剧, 等待磁盘 IO 导致 CPU 利用率下降, 调度器载入更多进程想要提高 CPU 利用率, 然后触发更多的缺页异常, 进一步降低 CPU 利用率, 导致连锁反应
说起缺页异常, 今天看到一个神奇的东西. windows 系统对于一些希望在后台运行且不影响前台的应用做了限制, 比如内存只分配 32MiB 物理内存, 不过没写在文档里. 于是某些应用由于只有 32MiB 物理内存, 因此一直在触发缺页异常, 导致 CPU 跑满但是啥都没做.
工作集模型
工作集模型是现代操作系统中常用的方法, 避免颠簸. 它的想法是, 上一个时间段用到的物理页, 下一个时间段大概率也会用到.
这里假设应用在 t 时刻的工作集 W 是[t-x, t]时间内使用的所有物理页集合.
操作系统会周期性地扫描所有物理页, 对于访问位为 1 的物理页, 说明它们曾被访问过; 在时刻
这个策略需要硬件支持, 访问页表时可以自动设置访问位为 1.
这里据说也可以用机器学习的方法来预测工作集的大小.