解刨操作系统虚拟内存 (一)

从编程的角度看,虚拟内存可能是内存管理中最抽象、最重要的概念,但国内的教科书在内存管理相关章节,普遍对虚拟内存的知识一笔带过,相关的内容仅仅涉及到逻辑地址到物理地址的转换(事实上这部分属于 MMU),以及本地磁盘与内存的对换区(swap),该区域,在空闲内存达到门限值(threshold)时,用来与内存进行页面置换,但在 iOS 系统上没有该区域。

由于虚拟内存的内容非常庞杂,文章将分为两部分,该篇是第一部分,内容侧重从操作系统内存管理的底层开始,建立基本的内存管理以及运作的相关概念。第二部分,将结合苹果XNU内核,cctools, dyld的源码和Mach-O二进制文件进行分析,看清楚整个虚拟内存的创建过程。

问题


1: CPU 与存储系统的结构 ?
2: MMU 是什么,以及它是如何工作的 ?
3: 到底什么是虚拟内存,它是否真的存在于内存中 ?
4: 为什么 CPU 给出的访存地址总是虚拟地址 ?
5: 内存请求分页的过程和原理 ?

带着上述问题,我们进入计算机和操作系统的内部。

CPU 与存储器体系结构


从编程角度,以及宏观上,计算机可以被看做是一个多级缓存系统。主要组成有 CPU、寄存器、和各级缓存。各级缓存是个抽象概念,不是具体概念,可能各种书籍中也没有这个概念,但我觉得用这个词有助于理解整个存储系统。

各级缓存具体包括高速Cache层(硬件结构SRAM,可以有多级缓存)、主存(Memory,俗称的内存,也叫 RAM,硬件结构DRAM)、磁盘(disk)。运行速度依次递减:寄存器 -> Cache -> RAM -> Disk,与此同时造价也依次递减。但容量依次递增。当然,远程服务器的云盘,也可以看做是存储器体系结构的一部分,不过本篇不讨论。

CPU 只和寄存器直接通信

CPU 从不直接和除了寄存器以外的存储设备打交道,因为CPU嫌弃它们太慢。现代计算机CPU是个很泛的概念,本篇所说的CPU主要指由 ALU CU 组成的计算和控制单元。不同的体系架构(CISC、RISC),寄存器个数不同,不过怎么着也有近百个,后续会慢慢介绍各种寄存器。CPU也不会直接访问Cache和主存,这个工作交给MMU(Memory Manager Unit)来做。CPU更不会直接访问Disk,这个工作交给DMA或者I/O设备专用管道来做。

一些基本概念


下面从计算机硬件底层到上层,解释一些基本概念。

1、时钟周期、机器周期、指令周期

这部分不太影响对虚拟内存的理解,就放一张图。

2、中断

当我们每次滚动一下页面,操作系统都会提交一个外部中断给CPU,CPU会扔下手头的事情,立即做出响应,不然用户就会觉得电脑卡顿。处理完成后,CPU继续做原来的事情。中断和CPU时间片调度的方式,共同造就优秀的交互式计算机。中断是有内核程序处理的,用户级程序无法处理,只能提交给内核去做。中断有很多种,后文会提到缺页中断(page fault),也是一种中断。还有多线程底层的同步原语也是通过关中断和开中断,以及一些硬件结合来完成的。

3、字长与地址空间

平常所说的32位、64位操作系统,指的就是CPU的字长为32位或者64位。单位是bit,具体指CPU能够单次并行读取的bit数。CPU旁边还有一个数据寄存器(MDR)和地址寄存器(MAR),CPU每次要访存,都把地址交给MAR,数据则写入MDR。为了加快处理速度,一般让CPU字长和MAR与MDR的位数保持一致。

由此,MAR地址寄存器的长度(或者字长)就决定了CPU能够访存的地址空间,例如32位系统,地址空间就是2^32个地址单元,如果按字节(Byte)编址,那么最大的访存范围就是2^32个B,就是4GB,那么这个4GB就是地址空间,但这是理论上的,即虚拟地址空间,表示每个程序都可以映射4GB个虚拟内存空间,实际的真实大小受限于主存的大小。如果是64机器,按字节编址,地址空间就是2^64个B,这个数是2^32个4B,大的很。当然也可以按2B(半字)、4B(32位=字)编址,访存空间会更大。但一般来讲,计算机都是按照字节编址。

虚拟内存与请求分页


通常我们的机器的物理内存都是有限,例如 16GB、32GB 等。但可以运行的进程是无限多的,如果每开启一个进程,都要独占一部分物理内存,那么只要不停的打开程序,无论物理内存有多大,都不够用。这时候虚拟内存就派上用场了。

前边提到,对于32的机器,理论的可寻址范围是0-4GB(按字节编址 后同)。既然这样,就基于此给每个进程都创建 4GB 的虚拟地址空间,口头上答应每个进程你们每个人都有 4GB 内存可用,对于每个进程来讲,好像它们都独占了 4GB 的内存,但实际上的物理内存可能只有 1GB,比如 iPhone 6,32位机器,1GB物理内存。那么总共就 1GB 的物理内存,如何分配给那么多的口头上表示要占 4GB 内存的进程(这里是理论值,并不是真的每个进程都需要占用 4GB 内存)?操作系统内核会负责进行内存映射,将各个进程的虚拟内存映射在有限的物理内存上,让所有进程共享物理内存,但是对进程来讲,无法感知到。

程序局部性原理与内存分页

为什么操作系统内核敢这么大胆,口头上答应给每个进程远大于实际物理内存的内存空间?原因是基于程序的局部性原理(locality),局部性包含了时间局部性和空间局部性,虽然整个程序可能包含了很多数据和指令,但某一特定的时间内,程序总是执行某一特定区域的指令和数据。虽然这一特性不总是发生,但大多数情况下程序还是符合局部性原理,更别说,我们还设计了编译器和链接器,让生成的可执行文件,指令都保存在__TEXT,__text中,数据都保存在__DATA段中。这样,就更加提高了程序的局部性。

有了局部性原理的理论支撑,还需要实际的策略。为了能高效的利用内存,和便利的换入换出内存区域,现代操作系统都会采用请求分页机制来管理内存的分配和回收。即将 Cache、主存、磁盘,都分为大小相等的若干块小内存,每一小块称为一页;物理分页通常被做分块(block),或者页帧(frame),逻辑分页才被叫做分页 page。各种教材的取名五花八门,这里为了方便同一叫做内存分页。

以 iOS 或者 macOS 为例,在 32 位机器上,每一页大小是 4KB,2^12。64 位机器上,页大小为 16KB, 2^14。这个大小不是固定死的,但基本上别的操作系统也类似。

虚拟内存的结构

为了便于管理,内核在构建虚拟内存的时候,都会按照一些特定的格式,这个格式在各个操作系统上大同小异,主要把虚拟内存分为几个段。

具体每个段的作用,我将在下一篇结合xnu源码与Mach-O文件仔细讨论。这里我们看到了虚拟内存的基本结构,事实上整个程序的启动过程,大部分工作就是在构建这个虚拟内存结构。其中内核部分的虚拟内存,对用户程序不可见,每个进程的内核虚拟内存最终会被映射到同一片物理内存上。虚拟内存的起始指针被保存在PCB(进程控制块)中,而各个进程的PCB,被内核程序同一管理和调度。

MMU与页表

有了虚拟内存的结构以后,程序运行会完全跑在虚拟内存上,具体则是CPU的PC寄存器指向虚拟内存的__TEXT,__text区域,自增执行指令,所以CPU获得的地址全部是虚拟地址,那虚拟地址如何映射到具体的物理地址上? 这部分工作由 MMU(Memory Managerment Unit)和页表共同完成。页表中记录了每一个虚拟内存地址对应的物理内存块号。CPU会把该虚拟内存交给MMU,MMU负责将虚拟地址转换为实际的物理地址,然后从中取出指令交给CPU。一般意义的MMU,即包含了页表(软件结构),也包含了硬件解码器(计算主存块号和块内地址)。MMU 的硬件部分通常和CPU焊接在一起。

页表也是在程序装载的时候创建,页表基地址同样保存在 PCB 中,当发生进程切换时,操作系统内核把需要运行的进程PCB中页表基址载入页表寄存器中。方便后续的地址转换,地址转换过程中,MMU通过虚拟地址的页号来查询页表,找到对应的物理内存的块号。然后与虚拟内存地址的低位(块内偏移)相加得到真正的物理内存地址。为了加快寻址的过程,会将部分页表的内容缓存在TLB(Translation Lookaside Buffer),即快表,TLB硬件为 SRAM 结构,访问速度原高于主存(DRAM)。这时,MMU会优先访问快表,不命中的情况下,再次访问慢表(页表,相对快表而言就是慢表)。

上图为 MMU 的基本工作流程,这里以 32位机器为例,则低12位表示了页内偏移。如果是64位,则低14位为页内偏移。实际中,为了节省存储空间,一般会采用多级页表(常为4级)。

缺页中断、页面置换、抖动

当MMU访问页表后,发现页表项中没有对应的物理地址,就会产生缺页中断。这里大致可以分为三种情况

1: 该页面第一次被访问,还没有从磁盘调入物理主存中,或者是匿名逻辑地址,物理内存还没有被分配(例如堆 heap 的分配)。
2: 之前访问该页面,但是由于内存置换,该页面从物理内存置换到了磁盘的交换区。

上图中,2号逻辑页面,还指向磁盘,如果访问2号页面,就会产生缺页中断。无论哪种情况的缺页中断,进程都会通过陷入指令(trap)从用户态转为内核态,程序现场暂时保存,进程暂时阻塞,由内核负责调页,或者创建页面(均指物理内存),同时更新页表、TLB等,中断返回后,重新执行指令。当程序频繁的发生缺页,或者页面置换时,被称为页面颠簸,或者内存抖动,此时程序运行出现卡顿。操作系统需要调整当前进程的工作集大小,或者清除其他进程的物理内存。

下一步


下一篇,将结合XNU源码和Mach-O进行更加细致的分析上述过程。

参考


1: https://manybutfinite.com/post/anatomy-of-a-program-in-memory/
2: CMU操作系统公开课
3: https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/