OSTEP笔记2–内存虚拟化

大部分截图来自原书,贴出书的官方主页: 《Operating Systems: Three Easy Pieces
(作者Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau)。感谢原作者这么好的书。

本篇笔记是书的第一部分(Virtualization)的下半部分,讲述了操作系统是怎么通过地址空间的抽象,将内存资源进行虚拟化的。

第一节 地址空间

1.1 内存虚拟化

多进程OS的资源共享策略

本书上半部分讲了CPU的共享策略:通过进程(process)这个抽象,OS将时间片分给进程。

对于内存资源的共享:为了让昂贵的计算机能够支持多个程序同时运行,如果在切换某个进程时将内存数据从磁盘换入(进程共享磁盘,内存和寄存器都不共享),由于磁盘IO太慢,不现实。所以现在的系统,都是将相对较快的寄存器换入换出 ,所有进程数据共享内存资源( 寄存器不共享,内存共享 )。为了实现这种想法,并更好地管理内存, 地址空间(Address Space) 的抽象被引入(如下图),相对为每个程序固定分配一定大小的内存空间更灵活,用地址空间进行管理更加灵活。

地址空间在 结构 上主要分为Code、Heap和Stack,Code部分用来存程序运行的代码,Heap是用户程序动态分配内存(malloc/free)所使用空间,Stack是变量使用的空间。除非程序递归很多,一般Stack都是够用的;如果程序视图访问非法地址,可能出现Segmentation fault的错误。

每个进程都会有一个自己地址空间,且每个进程都认为自己的地址空间是从0开始的,并且地址空间的地址也不必和物理地址相等,甚至地址空间的总大小可以大于物理内存大小,这就体现了一种 内存虚拟化 的概念,OS的内存管理系统也可以称为 虚拟内存系统(virtual memory system, VM) 。因此,我们编写的程序中,所有我们可以得到的地址也都是虚拟地址,并非物理地址。

VM系统设计的三个目标:透明(transparency)、高效(efficency)保护(protection) 。其中保护即隔离(isolation),进程间的地址空间需要隔离,进程和OS间也需要隔离,(甚至在有些微内核操作系统中,OS的一部分和OS的另一部分也进行了隔离),这样可以保证安全性。

1.2. memory API

对于用户程序,Stack中的变量是自动管理的,比如用int声明一个整数变量,而Heap中的内存是由程序(程序员)负责的,什么时候malloc/free都要程序员进行考虑,所以要格外小心一些常见的malloc错误,比如忘记分配内存、分配的不够导致buffer overflow、忘记初始化所分配内存内容、忘记free等。 purifyvalgrind 这两个工具可以协助检测内存分配的问题。

1.3. malloc、free和mmap的关系**

要注意 malloc/free并不是系统调用 ,它们是基于brk和sbrk等系统调用的库函数,但我们使用时不应该直接使用brk等,而应该坚持使用malloc/free函数。

传入某些参数后, mmap 函数也可以从OS申请内存,OS会在你的程序中创建匿名(anonymous)内存区域(一个和swap space相关的区域,而不是某个文件),这个区域可以像Heap一样进行管理。

需要注意的是,mmap是系统调用,mmap也是malloc函数分配给用户程序内存时所基于的系统调用之一。在嵌入式领域,mmap可以将外设寄存器的地址(物理地址),映射到用户内存空间。实现在用户态下操作寄存器,进而实现用户态下驱动程序的作用。[1]

1.4 地址转换机制

由于地址空间的地址是虚拟地址,需要进行虚拟和物理地址间的转换,硬件的介入(interposition)可以加速这种转换。(“介入”不只在硬件,软件层次中也经常用到,以透明的方法两个层次的中间加入功能或改进性能)

1. 软件实现: 在硬件加速出现之前是 software-based static relocatin ,方法是OS有一段称为loader程序负责转换地址。但这样缺点是进程间没有保护,而且一旦地址空间被放置,以后很难进行重新放置。

2. 硬件实现(base and bound): 50年代进行”hardware-based dynamic relocation”的思路是通过 base and bound 硬件寄存器进行辅助,物理地址一般就是base地址加上虚拟地址,bound寄存器用于存储地址空间对应区域的大小或者结束地址,用于检测转换后的地址是否合法。辅助内存管理的硬件称为 MMU(memory management unit) ,base和bound寄存器就属于MMU。

为了实现base and bound,OS需要在进程 创建、结束或切换 时进行对应的操作。创建进程时时需要找到空闲足够的物理地址空间(最简单的,OS可以用 free-list 实现);结束进程时,需要进行内存的回收;进程切换时,需要保存和恢复(save and restore)base和bound寄存器的内容,将要切换出的进程寄存器会保存到对应的PCB(process control block)中。这种硬件实现还可以方便地址空间的随时移动,一个没有正在运行的程序,只需要将地址空间拷贝到新的地方,然后更新PCB中base寄存器的内容即可。

第二节 segmentation(分段)管理

2.1 地址空间分段

上述的地址空间这个抽象,是内存虚拟化最基础的思路。但是这种最基本的结构有个显著的缺陷:internal fragmentation(内部碎片) ,即某个地址空间中如果stack和heap之间有很多空间没有使用,一旦分配,也不能给别的进程使用,这便造成了空间的浪费。

于是,60年代,人们引入了 分段segamentation 的思路,即将地址空间分成code、heap和stack三个逻辑段,每个段分别有一对对应的base和bound。(我们常见的segamentation fault错误,就是源于访问了非法的内存空间地址)有了段,我们可以在物理上将三个段分开放置,解决了内部碎片问题。

2.2 分段地址转换

引入分段后,虚拟地址可以看成两部分组成(如图):段地址(segment)和偏移量(offset)。这样如果一个地址空间分了3个段,就相当于原来的地址分了前两位出来表示段,offset的作用和原来的地址作用类似。

2.3 外部碎片问题和空闲空间管理

引入分段,虽然解决了内部碎片问题,但是会导致 外部碎片 问题(空闲空间都不连续)。为解决外部碎片问题,可以定期进行段移动整理碎片(compaction),但是这样性能开销很大;或者用free-list采用best-fit、worst-fit、first-fit等短发进行空闲空间的管理。

其实不管是上述讨论的OS的内存的分段管理,还是malloc/free这种进程heap的内存管理,都可能导致外部碎片(相对内部碎片,我们更担心的外部碎片),需要进行 free space management 。本书以malloc/free内存分配库为例进行了讲解:(详见课本)

1. low-level机制: 最简单的,free-list通过malloc时的 分割(splitting) 和free时的 合并(coalescing) 进行管理,但是在内存分配库中,无法用malloc进行free-list节点的空间的分配,这时,需要用mmap申请内存,并将free-list的结构嵌入到整个所申请的内存中。

2. 基本策略: 策略有best fit、worst fit、first fit、next fit等。其他的策略还有segregate list、伙伴算法等,伙伴系统可以避免外部碎片,但是由于所分配只能是2的倍数,无法避免内部碎片。后来有些系统考虑到list搜索效率低带来低scaling的问题,引入了平衡树等结构来构建空闲内存管理。

第三节 paging(分页)

分段带来的碎片问题很让人头疼,所以在很早的60年代,人们也提出了分页(paging)的思路,将内存分成固定大小的页,这比分段更灵活和简单。

3.1 地址转换

分页也是在虚拟地址空间上进行的,为了进行地址转换,基本思路是每个进程会配有一个 page table ,存有虚拟页号VPN(virtual page number)到物理页框PFN(physical frame number)的映射。

地址的格式和分段类似,也是有若干位被分出来作为VPN,进行转换时,类似分段借助base寄存器,分页则借助于page table,offset为页内地址,不用转换,如下图:

page table 由 page-table entry(PTE)组成,一个x86的PTE如下:

一个PTE可以有很多内容,比如:valid bit用于标注虚拟地址存在(在地址空间中),但是没有被使用的项,这样OS就可以不去为其分配实际的物理空间,节省了内存占用;protection bits(R/W U/S)标注一个页是否可以写、读或者执行;present bit(P)指明页是在内存中了还是磁盘中了(被swap出去了);dirty bit (D)用于说明某个页是否被修改过;reference bit(或access bit)(A)用来记录一个页是不是被访问过了,这对判断一个页是不是热的很有用,可以为页面换出提供参考。PWT, PCD, PAT和G用于决定硬件的cache方法。

Page Table 很大切在内存中,它会引起更多的内存范文,拖慢运行速度。比如,对于每条指令,都应该先从page table中将code中这条指令的虚拟地址转换成物理地址,然后再去物理地址访问,这就导致一次访问放大为两次。如果涉及mov等指令,不只指令本身需要增加一次转换,如果操作数中包括数组地址,对数组地址也需要一次虚拟到物理的转换,进一步拖慢了速度。

所以分页虽然能减小外部碎片,但是却让内存访问次数增多,系统运行速度变慢。

3.2 TLB(translation lookaside buffer)硬件加速

类似分段中用base-and-bound硬件寄存器来辅助地址转换,分页中用的是硬件cache加速的方法:即TLB(translation-lookaside buffer),TLB也属于MMU。

TLB和其他cache的思想是一样的,也是利用了spatical locality和temporal locality。页长越大,因为PTE的个数少了,TLB命中率会越高。而之所以不能把所有page table都放入TLB,是因为越快的存储硬件,面积也会越小,所以大容量和高速是个悖论。

TLB中一般有几十(32、64、128等)项,且是全相联(fully associative)的,即任何项可以被存储到任意一个位置,查找命中时并行搜索,所以在硬件中,TLB也被称为fully-associative cache,一个TLB项由和PTE类似的VPN、PFN和一些标志位组成。

因为存在进程切换,所以进行进程切换时,需要防止正在运行的进程访问其他进程留下的缓存项。有两种方法:1)切换时将所有项的TLB的valid bit置零,并把部分项进行必要的flush(软件TLB可以直接执行相应的硬件指令,硬件TLB可以在存储page table的register改变时进行);2)可以在TLB项中加入ASID(address space identifer)位,来标注这个缓存项属于哪个进程。

TLB是cache,当然还涉及到置换算法的选择,比如LRU等,这方面和其他的cache很类似。

作者详细介绍了一种MIPS的TLB项,如下图:

global bit(G)用于标注是否是项是否被多个进程共享;3个Coherence(C) bit,用来指示怎么被硬件cache;dirty(D)用来指示项是否被更改过;Valid(V)用来表示该项的转换是否可用;还有一个图中没有标注的page mask区域,用来支持不同的页长。

TLB的大小对性能影响很大,如果TLB没有通过时间和空间局部性将要访问的PTE项cache到,那么就会引起性能的损失,所以作者指出: RAM isn’t always RAM. 即可以设想如果过于随机地访问内存会造成TLB miss,会损失性能。大的page size不仅可以减小page table的总大小,也可以提升TLB的命中率,这种大页更适用于DBMS这种拥有大页和随机访问需求的系统。

TLB也可能造成对CPU pipeline性能,因为如果CPU的cache是physically indexed cache的话,虚拟到物理地址的转换就要在CPU cache之前,造成性能下降;所以人们提出了virtually indexed cache,但这又会给硬件设计带来新的问题。

3.3 高级页表(Advanced Page Tables)

分段解决了内存空间被浪费的问题,但是不能解决外部碎片的问题;分页解决了内存管理中外部碎片的问题,但分页管理的page table占用空间太大。(比如刚刚为一个进程分配若干内存地址空间后,就要创建相应数量的PTE,这造成page table在开始时空间利用率很低,造成内存的浪费,尤其是每个进程都有一个page table,当系统进程多时,会造成内存的紧张。)

解决的page table太大的方法之一是上节提到的 增大页长, 但是太大的页长会导致 内部碎片 问题产生,即页内空间利用效率低。很多商用高端系统和DBMS会用多种页长,这也会相应的导致内存管理特别复杂。

3.3.1 段页式(Hybrid Approch: segements and paging)

本节主要讲了用分页和分段进行混合(hybrid)的方法。具体思路是:每个逻辑段有一个page table,并且MMU中的base寄存器指向段的page table的起始地址(而不是原来的段起始地址),bound寄存器存有对应段中最大的有效页号。如果我们将进程内存分为code、stack、heap三段,则我们有3对base和bound寄存器。

如下图是一个简单的段页式地址格式:

Seg用于决定用那一对base/bound寄存器;VPN用于在相应page table中查找并转换为PFN;Offset不用转换,是实际访问的页中偏移量。

但是段页式仍旧可能存在page table浪费内存的问题:在最原始的地址空间中,我们讨论的内存浪费直接指heap和stack之间的未利用空间无法被其他进程分配,在段页式管理中,内存浪费指的是page table中有不必要的内存分配(比如某个段很稀疏,但是最小和最大的项里的较远,中间仍旧有很多无效的PTE),即 内部碎片 问题;并且虽然数据以固定长度的页单位存储,但page table的大小却是任意的,这再次引入了 外部碎片 问题,将导致不容易找到一个合适的存储空间来存储page table。

这里讨论的内外部碎片问题或浪费内存空间的问题,指page table数据;而上几节中讨论的碎片和内存浪费问题,指的是进程数据,但道理都是一样的。

3.3.2 多级页表(multi-level page tables)

接着上节,为了解决page table的内存空间利用问题,缩减page table的占用的无效空间,多级页表被提出。其基本思路是将page table分成按固定页长分开,然后引入page directory的概念,其中的项PDE记录的都是存有page table的页的地址。传统页表和多级页表的对比如下:

可以看到,如果PDE中对应的Page Table页中没有一项,可以将PDE的valid bit置零,这样对应的page table 页就不用被分配,节省了内存;而传统的线性page table中,

如果说段页式是segamentation+paging,那么多级页表就是paging+paging,将page table的table就是page directory。本质上,多级页表在分页管理PT到page间接的基础上,又多加入了一层PD到PT的间接(level of indirection),这种间接可以压缩原本稀疏存储,但是肯定会带来性能损失,而且会使实现的复杂性增加,也就是一对time-space trade-off。

可以想到,道理上还可以增加更多的间接,形成更多级的页表,这也许在有些极端情况有用,具体问题需要具体分析。甚至,还有一种倒排页表(inverted page table)有时也会发挥其作用,其用一个单独的page table记录每个物理页由哪个进程使用,并记录了对应的虚拟地址。

第四节 交换空间(Swap Space)

swap 机制 可以让软件产生拥有磁盘级别的巨大内存的幻觉,其实就是在内存空间吃紧的时候,将不常用的内存页换到磁盘上预先划分的swap space中。PTE中有一个present bit,如果为0时,则会产生page fault,说明此页有可能已经被换出到磁盘上了。为了访问磁盘取回换出页,换出时,需要将目标磁盘位置记录到page table 的PTE中。

当需要换出时,肯定需要由一些 策略 ,这时,又要决定使用哪种页面置换算法了,比如LRU等。

第五节 实例:VAX/VMS内存管理系统

在实际中,一个VM管理系统需要具有一般性、通用性,所以通常不会为单一的硬件优化,在某一硬件上达到最优。

VAX的VMS的地址空间可分为用户部分和系统内核部分,其中用户部分随进程切换而改变,而内核部分不变且被映射到每一个进程的地址空间中。因为内核和用户在一个地址空间,所以加入了pretection bits将内核和用户程序分成不同优先级进行保护。

为了解决一个进程占用过多的内存的问题,进行换入换出时,可以采用segemted FIFO,即每个进程都有一个最大的page数的FIFO队列;为了保证性能,又再次基础上增加了second-chance lists(进一步分为clean-page free list和dirty-page list),这些second-chance lists越大,其实就越接近于LRU算法。

clustering 的被引入到了dirty page 的flush中,可以减少些的次数,提升性能。

demand zeroing 优化的是为了保证安全在分配前做的物理内存清零操作,demand zeroing 用了懒惰的办法,在进程真正读写一个页时,才trap到内核进行清零,这样减少了不必要的性能开销。

copy-on-write 主要用于优化页在内存中的拷贝,尤其是在Unix系统中,fork和exec经常使用,且fork后一般很快会执行exec覆盖掉fork的进程的地址空间,如果每次fork后马上拷贝一份新的地址空间再返回是没有必要的。因此COW可以在内存拷贝时进行映射,并将新的虚拟页标上只读标记,在写虚拟页时陷入内核再进行真的拷贝。


[1] linux mmap匿名映射的作用是什么? https://www.zhihu.com/question/57653599

发表评论

电子邮件地址不会被公开。 必填项已用*标注