操作系统概念——虚拟内存

第九章 虚拟内存

9.1 背景
有些情况下进程的空间不需要全部都在内存当中,比如:部分异常处理代码不会被用到;
申请的内存如数组只用了较小的一部分;部分特性或模块一般不启用等.
即使全部都要用到,一般也不会在同一时间访问.
虚拟内存提供一种机制,让进程只有部分按需加载内存中运行,并且不受物理内存大小限制.
好处主要有:
a) 突破物理内存大小限制;统一逻辑空间视图,屏蔽开发者物理内存的底层问题.
b) 节省内存,提高cpu利用率和吞吐能力,而不影响进程原有的响应和运行时间.
c) 减少需要加载或swap的进程内容IO,加快执行速度.
虚拟内存与物理内存分离还能通过页共享实现文件或物理内存共享,成为共享库、共享内存、快速fork等的基础.

9.2 Demand Paging
Demand Paging即在内存页真正访问的时候才映射到物理内存,用于实现虚拟内存的常见方式.
通过只加载需要的用到的内存页,为系统节省了内存开销和加快了加载/换入的时间.

硬件上一般通过页表项的invalid位来表示该页是否在内存.
如果invalid为1则该页要么没分配,要么页表项内容表示其在磁盘上的位置(bin文件或Swap空间).
如果需要访问的页不在内存,则会产生缺页中断交给操作系统让其将目标页从磁盘加载进内存,更新页表,重启指令.

理论上有可能同一条指令可能导致多次缺页中断,但由于局部性原理很少发生.
但是对于个别修改多处地址的复杂指令,直接重启还不一定能保证正确性.
比如一条移动多个字符的指令,如果跨page并且源和目标地址重叠,发生缺页中断时,
可能源地址内容已被修改,直接重启指令可能会导致结果不正确,因为这种情况是不可重入的.
对此有2种处理方式,一种是执行前把最大和最小地址都访问一遍,事先把page加载进来;
另一种是先将被修改的部分保存起来,缺页处理后恢复被修改的部分再重新执行指令.
总之实现Demand Paging时要十分小心,并不是所有的指令集架构下都能直接增加Demand Paging的支持.

缺页中断对性能影响很大,一般访问物理内存需要100纳秒级别,但处理缺页要走磁盘IO在10ms级别.
因此需要保持一个很低的缺页中断率系统整体性能才能接受.

另外专门配合Demand Paging的Swap空间一般比其他文件系统要快速.
可以在程序文件启动前将其复制到Swap空间,也可以先从文件系统加载,在后续有页被替换出的时候才开始利用Swap空间.
一般地从文件系统读的是二进制文件的代码和只读数据,这部分数据换出时不需要写磁盘,后续换入只需重新加载.
而程序的堆和栈等动态内容对应的页如果有修改则一般换出到Swap空间.
这部分没有文件区域对应的内容一般叫做匿名内存(Anonymous Memory).
像手机操作系统一般就不支持Swap,但支持对代码等只读数据页的回收以在内存紧张时释放内存,后续再重新载入.
IOS对匿名页就从来不会回收或换出,除非程序主动释放内存或退出.

9.3 Copy-on-Write
Linux的fork系统调用采用Copy-on-Write来快速高效地创建进程:
fork时父子进程共享内存页,后续进程有写操作再为其单独复制到新的物理页.
只有可写的页才会设置为Copy-on-Write,其他都是父子进程共享的只读内容.
一般从系统维护的空闲页列表分配待复制的页,并且内容一般初始化为全0(Zero-fill-on-demand).

vfork系统调用下父进程会等待子进程,一般用于exec等执行新进程,也不会复制页,甚至可以共用页表,因此比fork更快.
但Linux下的fork实现特意让子进程先调度,也是针对exec做了优化(否则父进程先执行可能会产生不必要的copy-on-write).
因此vfork相对fork好处已经并不明显,当前就是少了一次页表复制,现已较少使用.

9.4 页置换算法
Demand Paging使得用户一般情况下可以超额使用内存,优化了系统的整体利用率和吞吐等,
但当并发程度越来越高时多个程序有可能同时在集中的时间访问大量内存,这时候物理内存就不够用了.
为了应对这种情况操作系统一般会提供相应的页置换机制,以及预防机制,使得系统稳定运行.
页置换加上Demand Paging才算构成完整的虚拟内存机制,系统运行真正对用户透明.

当置换页时,需要额外将victim页内容写到磁盘,并修改响应的页表,处理时长会加倍.
一个优化是,维护一个modify位,如果页的内容没有被修改过,则不用再写磁盘,直接替换即可.

由于涉及到缺页产生的IO,页置换策略尤其重要,一般通过算法产生的后续缺页率来衡量其效果:

a) FIFO算法
即维护一个队列,简单地将最早的页换出.
理解和实现简单,但效果一般不太好,并且可能出现Belady异常:增大物理内存反而提高了缺页次数.

b) 理论最优(OPT):将来最长不使用
把将来最长时间不使用的页作为victim,理论上是缺页率最优的算法.
直观上理解,就是尽量避免换出最近要用到的页.
缺点是没法准确预测,一般通过其他算法近似,或者用来做算法评估对比.

c) LRU算法
换出最长时间未使用的页. 即用历史行为来预测未来,效果较好,并以且不会出现Belady异常.
主要问题是如何实现,考虑以下2种做法:
计时器:每个页维护一个存储最近访问时间的寄存器,置换时选最小的那个.
使用栈:每个页访问时将其从栈中取出放到栈顶,置换时选位于栈底的页.
计时器方案维护时间比较高效(刷clock),但置换时需要遍历查找.
栈方案不用查找,但维护栈的操作相对较重.
直接实现LRU需要非常复杂的硬件支持,否则每次访问内存用软件维护开销过大.
因此实际一般是采用对LRU的近似实现.

d) LRU近似算法
reference位:页表项中用于表示本页最近有无被访问,由硬件设置,作为LRU的基本信息.
单个reference位的信息较少,有时候还提供额外的shift寄存器用于存reference的历史,如1个byte.
系统每隔一段时间产生中断,将byte每位向右移1位,并将reference内容复制到byte最高位:
中断前: |1| (ref bit) |1|0|0|1|0|0|0|1| (ref history)
中断后: |0| (ref bit) |1|1|0|0|1|0|0|0| (ref history)
这样置换时选最小的history即可,如果history相同则采用FIFO.

极端情况下,如果右侧history长度为0,则算法变为二次机会页置换算法
基于FIFO,一个指针轮训查找ref bit为0的页进行置换. 如果指向的页的ref bit为1,
则给其第二次机会,将其ref bit置为1后继续往下查找:
2nd_chance_page_replace
可以看出一个活跃的页可以长时间不被换出,而一个不活跃的页最多在第二遍循环时被算法选中.

一个优化是,考虑ref-bit的同时考虑modify-bit,按(ref-bit,modify-bit)分为以下四类:
(0,0)近期无访问,内容无修改:最佳置换对象.
(0,1)近期无访问,内容有修改:次佳选择,但换出时要写磁盘.
(1,0)近期有访问,内容无修改:次佳选中,但换出后可能短期又会命中缺页.
(1,1)近期有访问,内容有修改:尽量不要置换.
即如果可以,尽量只换出没有修改的页,减少IO的产生.

e) 其他基于计数的算法
LFU:置换访问频率最少的页,理由是活跃的页访问频率相对较高,反之较低.
MFU:置换访问频率最高的页,理由是频率少的页可能刚开始利用,后续会变活跃.
这两种可能对一些特定场景比较适应,但不适合做通用的置换策略.

在确定主要的置换策略后,系统一般还有一些常见的通用优化手段:
1) 系统预留一些空闲的物理页用作缓冲池,当发生置换时,直接从缓冲池选一个空闲页先填上缺页,
而victim页在后续时刻再异步写磁盘,并加入缓冲池. 好处是被中断的进程不用等victim换出,提高了响应速度.
2) 系统在磁盘空闲时提前将一些脏页同步,减少发生置换时需要写磁盘的比率.
3) 基于(1)的缓冲池,如果被置换到缓冲池的页马上又发生了缺页,由于此时页内容是最新的,可以直接使用,
而不用再重新读磁盘. 这对预测失败的置换算法是一个较好的补救措施.

可以看到优化的核心主要都是围绕如何减少IO操作.

最后有些应用可能需要操作系统提供的通用磁盘和虚拟内存管理,比如数据库系统.
这类应用一般根据其特定场景做了自行定制管理,因此效果比操作系统提供的通用策略要好.
比如文件系统,IO缓存等,不需要OS重复提供一套,否则浪费.
又比如数据仓库应用,循环读取大量数据到内存,轮训访问旧页,LRU可能不再适应.
因此一些系统提供给特殊应用直接操作裸设备的接口,绕过文件系统各模块服务如File IO Demand Paging等.

9.5 物理内存分配
一般内核的内存是独占的且不参与换页,应用程序的页从系统空闲帧列表分配.
内核内存页可以部分参与换页,从而给更多内存给用户程序.

一般地,每个进程的活跃页数除了受总物理内存限制外,还有一个最小页数,如单条指令最大可能涉及到的页数.
一些架构支持多级间接寻址,则对最大级数需要做限制,否则单条指令理论上能遍历全部内存.

进程间物理内存分配可以简单此采用均分,也可以根据虚拟内存大小按比例分配,还可以加入优先级因素.
针对内存分配有两类页置换方式:全局置换和局部置换.
全局置换指进程缺页时可以置换掉其他进程的页,局部置换指只能在本进程分配内存中置换.
两者可以配合使用,比如一个允许高优先级置换低优先级但不能反过来的系统.
局部置换下进程的空间分配是固定的,其性能表现不受其他进程影响,但可能有空间页得不到利用.
全局置换下进程的表现和环境因素相关,可能每次都有差异不稳定,但系统总体利用率更高.
因此一般采用全局置换的系统较多.

相比SMP,当前不少系统采用NUMA架构:多套cpu+内存的主板Group, 同一Group内内存访问比Group间更快.
对进程调度和内存分配都产生了一定的影响:
调度器尽量不在cpu间迁移进程,保持cache的热度.
内存分配尽量优先考虑进程所在的cpu的对应的内存区域.
thread使得情况变得复杂,因为thread是共享的内存但又期望用上多cpu.
因此系统内核设计时需要针对NUMA做优化考虑,即NUMA-friendly.
针对thread的情况,Solaris的做法是尽量在同一个逻辑group内分配资源.

9.6 Thrashing
Thrashing(内存抖动)的产生是当系统并发程序较高时,物理可用内存减少,
多个进程反复产生缺页和置换,导致系统大部分时间花在换页上,系统利用率低下:
thrashing
抖动的本质是内存不够,因此没法杜绝其发生,但系统需要有一些预防和事发处理的措施.
当发生抖动时,一般选一个进程换出并释放其内存,通过降低系统并发程度来防止抖动.

采用局部置换策略可以缓解抖动,但发生抖动的进程长时间占用IO排队,也会影响其他进程.
为了有效理解、预测和处理抖动,可以从工作集(Working-Set)的角度进行说明.
根据程序的局部性原理,一段时间内进程活跃的页是相对固定的,这些页构成了当前的工作集.
如果某个进程分配的内存小于其工作集大小,就会产生频繁缺页.
因此如果系统总内存小于当前所有进程的工作集之和,就有可能产生抖动.
因此系统可以追踪每个进程的当前工作集(通过ref-bit+history+中断),来判断释放会发生抖动.

另一个直接的做法是设置进程缺页中断率阈值.
如果中断率过高,则加大其内存分配,如果内存不足则换出一个进程.
如果中断率过低,则适当减少其内存并分配给高中断进程.

总之内存抖动会给系统性能造成极大影响,根本的解决办法还是尽量保证内存够用.

9.7 Memory-Mapped 文件
利用系统的虚拟内存机制,可以将文件内容以Demand Paging的映射到进程的内存页当中,
方便进程操作文件内容;mmap一般比open、read等系统调用更高效(为什么?)

mmap相对普通IO(read/write)的优势主要表现在应用程序层面:
a) 直接在用户空间操作,避免了反复read/write等系统调用切换开销.
b) 消除了read/write等调用需要的用户空间buffer和double copy的开销.
b) 除了私有+写,其他使用模式的内存可以被多个进程共享.
c) 不再需要lseek调用,消除了相关开销.

通过映射到同一个文件多个进程间可以实现内存共享和copy-on-write.

对高速设备来说同样可以实现Memory-Mapped IO:通过操作内存内容来写指令、数据寄存器等内容.
如可以把显示器内容映射到一片内存,更新显示内容就是更新内存.

9.8 内核内存分配
用户态内存是按页大小整块分配的,由开发者做进一步管理,并提供虚拟内存机制(Demand Paging + 页置换).
而内核使用的内存一般不参与Paging(不被换出,也不会占用用户内存),是常驻的物理内存,因此是越用越少的.
另外内核使用的内存一般要求是连续的,因为有些设备需要直接与连续的物理内存交互数据.
所以内核内存的利用率十分重要,加上内核各种大小不一的结构,需要有效地处理碎片问题.

a) 伙伴系统
伙伴系统采用2的幂次分配器,为每次请求分配一个最小的满足要求的内存块.
好处是分配和合并操作简单快速,缺点是内部碎片较多,利用率可能不高.
Linux内核最早是使用的伙伴系统内存分配.

b) slab分配
slab分配方案下每种内核结构都有一套对象cache,cache由slab组成,slab由连续的page构成.
每个cache下按定长对象实例来分配内存. 每个slab中的实例有个使用标记,方便快速分配和回收.
一共分为三类slab:Full所有对象都在用;Partial有一部分对象在用;Empty:对象都是空闲的.
分配对象时优先从Partial Slab中分配,其次从Empty类中分配.
如果没有空闲对象,则从连续内存中为cache分配新的slab.
slab分配方式有以下几个优势:
* 没有碎片问题,即内存一定能全部得到利用:
外部碎片:按定长对象池分配,不存在外部碎片.
内部碎片:slab固定块长度设置为具体的对象大小,不存在内部碎片.
* 由于采用pool+预分配的方式,对象内存分配和回收非常高效.

Linux从2.2开始采用slab分配器,后来又发展出了slob和slub分配器.
slob分配器主要针对小内存如嵌入式系统,从按大小分类的空闲链表中分配内存;
slub分配器对slab分配做了一些性能上的优化,从2.6.24开始取代了slab分配器.
主要优化包括slab元数据处理、去掉了per-CPU队列等,在多核机器上表现更优.

9.9 其他优化考虑
对虚拟内存的系统来说,首要考虑的是页置换算法和内存分配策略,其次还有很多考虑的细节.

预加载页:
对pure demand paging程序来说,启动时或者刚换入时可能集中产生较多的缺页中断,
因此最好能把当前的活跃工作集中的页全部一次性加载进来,
但如果预测错误可能导致把一些不会访问的页也加载到了内存.

页的大小:
较大的页可以提升IO吞吐,减少页表大小,降低缺页中断次数.
较小的页可以降低内部碎片,以及对局部工作集更高的精度表示.
另外可能还要考虑与磁盘扇区大小的关系等,因此没有统一定论.
总的历史发展趋势是页表大小是不断增长的.

TLB寻址范围
即能在TLB中命中的虚拟内存区域,理想情况下应该要能覆盖当前工作集.
TLB寻址大小等于页表大小*TLB容量.
多一些重内存的应用,TLB可能不够大造成查询页表较多,性能降低.
这时要么加大TLB容量,要么加大页表大小.
现在的系统一般都支持多种页表大小,需要操作系统软件和硬件的配合.
TLB软件支持一般会带来额外开销,但可由TLB寻址的提升带来的好处弥补.

倒排页表:
如前文所述,倒排页表的使用可以减少页表占用内存的大小.
但是在Demand Paging下,仅用倒排页表无法完整表示进程的虚拟地址信息,
如是未找到的目标页是否在磁盘上,还是根本没分配,从而无法处理缺页.
于是每个进程还是需要维护一份传统的页表,存储虚拟页的位置.
但是这些表一般仅需在发生缺页时才需要使用,因此平时可以page到磁盘上.

程序结构:
由于虚拟内存管理对应用程序是不可见的,因此一般不需要关注.
但程序如果局部性特征较好,则可以提升TLB命中、减少缺页以及提高整体系统利用率.
此外编译器和装载器页会影响到虚拟内存的行为,
如将代码和只读数据组成一页,则置换时不需要换出.
又如不跨页组织函数,相互调用次数较多的函数放在同一页等.
目标是使得跨页访问尽量降低,尤其当页较大时.

IO间隔锁和页锁
有些情况下的页不能被置换出内存,比如当进程在等IO时,如果设备后续直接写到用户物理地址,
这时目标页不能被替换. 一个办法是总是IO数据总是先写到内核空间,但会引入重复copy.
另一个做法是作为IO目标页的内存加上lock标记,在IO完成前禁止被置换.
系统还可以提供给应用程序锁内存的接口已满足其特定场景的需要,类似裸设备.
内核空间常驻内存一般也是锁定的.

锁内存的另一个应用场景在换页机制本身,比如进程A刚换入的页,ref-bit和dirty-bit都为0,
这时cpu切换到高优先级进程B执行,后者页产生缺页需要置换,有可能选中A刚换入的页,造成了工作的浪费.
这种情况可以把A的目标置换页锁定,保证其在至少被使用一次前不会又被换出.

9.10 操作系统举例
Windows:
Demand Paging使用clustering机制,一次换入多个连续的页.
每个进程创建时设置一个最小和一个最大工作集,用于物理内存分配参考.
系统维护一个空闲页列表,如果一个小于最大工作集的进程发生缺页,则系统为其分配新页,
如果达到了最大工作集的限制,则采用局部LRU算法进行页置换.
如果系统空闲内存低于阈值,则会启动页回收机制,在保证进程不低于其最低工作集前提下.
当系统内存恢复足够时,又会被用于用户进程内存分配.

Solaris:
发生缺页时系统总是从空闲内存列表分配,因此系统会强制维护空闲内存在一个基本水平.
当系统低于某个阈值时启动pageout程序,扫描每个页按LRU近似算法将不活跃的页换出.
系统内存越低,pageout扫描的频率越快;当内存进一步降低时,系统就开始swap out整个进程了.
被swapout的进程会释放所有内存,优先选择长时间空闲的进程.
另外最新的一些优化包括不换出共享页,以及区分对待进程空间页和文件映射页(priority paging)等.

发表评论

电子邮件地址不会被公开。