下文中存储器(Memory)指主存,即内存。

虚拟内存

虚拟内存(VM):一种对存储空间的抽象。它也能存东西,而且它的大小一般可以远远超过内存条的实际容量。(最大取决于你的 CPU 的字长)

你可以把虚拟内存当作一种超大数组。当虚拟内存的占用超过物理内存大小时,虽然对于用户(进程)而言好像还能往里面放东西,但实际上这个时候,虚拟内存管理程序会把一些不常用的东西移动到更慢的存储介质(比如硬盘)中,从而腾出空间放新的东西。这种移动的过程称为页面置换,移动的策略称为置换策略,每次移动的最小单位称为虚拟页。后面详细说。

寻址方式

早期计算机采用物理寻址:

image-20211125193947384

现代计算机采用虚拟寻址:

image-20211125194008600

变化在于增加了 MMU(存储器管理单元),负责将 VA(虚拟地址) 转换为 PA(物理地址)。

MMU 寻址过程

TLB:页表缓存。一个从虚拟地址到物理地址的散列表,便于查询。

在 MMU 启用的情况下,CPU 访问只使用虚拟地址,MMU 根据虚拟地址查询物理地址。MMU 首先通过虚拟地址在 TLB 中查找物理地址,找到则返回;没有找到,就会通过虚拟地址从页表基地址寄存器(PTBR)保存的页表基地址开始查询多级页表,最终查询到找到相应表项,并将表项缓存到 TLB 中,然后返回物理地址。

function mmu_trans(virtual_addr) {
    let tlb : Map<VirtualAddr, PhysicalAddr> = this.tlb;
	let physical_addr = tlb[virtual_addr]
    if(NOT_FOUND != physical_addr){
        return physical_addr;
    }
    physical_addr = PTBR.search(virtual_addr)
    tlb[virtual_addr] = physical_addr;
	return physical_addr;
}

分页

虚拟内存和物理内存被分割为固定大小的片段,就像一本书被分成很多页。所以虚拟内存分割后就有了虚拟页,物理内存分割后就有了物理页(PP or PF,Physical Page or Page Frame)

物理页也叫页帧

**虚拟页(VP)**是主存和外存之间置换数据的最小单位。

也就是说,即便你只是读取了 1 个字节的数据,一旦引发页面置换,也必须得交换整整一页数据。

分页的大小如何确定?

拜托,不要啥都想要个计算公式!操作系统爱咋定咋定,一般是 4KB 的整数倍。Linux 默认是 4KB。

重要的是,物理页大小 == 虚拟页大小

扇区:由磁盘的物理特性决定。扇区是磁盘的** 物理 存储单元**。读写磁盘的最小单位是扇区。

簇 / 块(Block):文件系统的文件存储单元。(簇是微软家的说法,其实就是块)每个块由 $2^n$ 个扇区组成,具体多大文件系统自己定,但不能超过页的大小。(这也是磁盘是块设备的原因)读写文件的最小单位是块 / 簇。

是内存管理的概念。将一个文件读入内存,占用的最小单位是页。

对于任意虚拟页面,其状态有:

  • 未分配:也即空闲的。
  • 已分配:
    • 未缓存:仅加载到磁盘
    • 已缓存:已经加载到主存

SRAM 缓存:CPU 和主存之间的 L1、L2、L3 高速缓存

DRAM 缓存:主存中的缓存

直写(Write through):数据从 CPU 写入高速缓存,并写入低速缓存。即一致性更强,效率更低。

回写(Write back):数据从 CPU 写入高速缓存,当高速中数据被换出时,才写入低速缓存。一致性更弱,效率更高。

高速缓存 = SRAM,低速缓存 = DRAM 而言,通常两种策略都有采用。而对于 高速缓存 = DRAM,低速缓存 = 硬盘 而言,只采用回写法,因为直写太慢了!

Linux 的页设计

原始代码见:mm_types.h - include/linux/mm_types.h - Linux source code (v5.15.5) - Bootlin

Linux 内核用 page 结构体表示每个页框:

struct page {
	unsigned long		flags;
    atomic_t			_count;
    atomic_t			_mapcount;
    unsigned long		private;
    struct address_space *mapping;
    pgoff_t				index;
    struct list_head	lru;
    void				*virtual;
}
  • flag 域用来存放页的状态。这些状态包括页是不是脏的,是不是被锁定在内存中等。
  • _count 域存放页的引用计数。-1 表示不被引用。其它代码通过 page_count () 函数进行检查。
  • virtual 域是页的虚拟地址。
  • mapping 指向页高速缓存。详情见 【内核】address_space 与基树 - visayafan - 博客园 (cnblogs.com)

分区

Linux 内核把页划分为不同的区(zone),从而将性质相同的页放在一起。

  • 一些硬件只能用某些特定的内存地址来执行 DMA(直接内存访问)。
  • 一些体系结构的内存的物理寻址范围比虚拟寻址范围大得多。这样,就有一些内存不能永久地映射到内核空间上。

Linux 主要使用了四种区:

  • ZONE_DMA 这个区包含的页能用来执行 DMA 操作。
  • ZONE_DMA32 和 ZONE_DMA 类似,该区包含的页面可用来执行 DMA 操作;而和 ZONE_DMA 不同之处在于,这些页面只能被 32 位设备访问。在某些体系结构中,该区将比 ZONE_DMA 更大。
  • ZONE_NORMAL 这个区包含的都是能正常映射的页。
  • ZONE_HIGHEM 这个区包含 “高端内存”,其中的页并不能永久地映射到内核地址空间。

Linux 内核直接映射空间最多映射 896M 物理内存,而现代计算机往往使用远大于此的内存,比如高达 1TB 内存。因此,通过高端内存相关设计,就能够间接访问到那些更大的内存。

相关源码见:mmzone.h - include/linux/mmzone.h - Linux source code (v5.15.5) - Bootlin

下图是 Linux 的内存组织。

image-20211125220902606

  • task_struct 是进程表项即 PCB,每个进程一个
  • mm_struct mm 是虚拟内存。
    • pgd 指向第一级页表(页全局目录)的基址
    • mmap 指向一个 vm_area_structs(内存分区)的链表

页表

页表是操作系统负责维护的,位于物理内存中的数据结构。由页表项(PTE,Page table entry)组成。

页表项

操作系统可以自由决定页表项的设计。

CSAPP 的页表项设计

在 CSAPP 一书的抽象中,每个 PTE 由 有效位 | 地址(页框号) 组成:

image-20211125210150645

有效位(又称存在位)表示是否已缓存。

  • 无效,无地址:表示未分配
  • 无效,有地址:表示未缓存,数据在磁盘中。
  • 有效,有地址:表示已缓存,数据在主存中。

MOS 的页表项设计

《现代操作系统》的页表项设计:

image-20211125210712456

  • 页框号:可以看作向物理内存的指针。
  • 存在位(也称有效位、驻留位、中断位):表示是否已缓存(是否在主存中)。
  • 保护位:表示访问权限。0 表示允许读写,1 表示只读。或者用三位,分别表示读、写、执行。
  • 修改位(脏位):表示页面是否被修改过。从而决定是否要回写到磁盘。
  • 访问位:在访问后设置。从而置换时,未访问过的优先换出。
  • 缓存禁用位:例如特殊 I/O 设备,不应当被缓存,则应该设置此位。

如果页表页在内存中不连续存放,则需要对页表页进行索引。这个索引表称为页目录(Page Directory)

二级页表结构

  • 页目录(每个进程一个):表项为页表 i 的地址
  • 页表 i:表项为 PTE,包含页框号等,页框号指向物理内存。
  • 物理内存

这种情况下,虚拟地址的构成是:页目录偏移 | 页表偏移 | 页内偏移

  • 页目录偏移,确定了页目录表项
  • 页表偏移,确定了页框号
  • 页框号和页内偏移经过拼接,形成物理地址

二级页表最大可以表示 4G 的虚拟空间。所以目前主流采用的是四级页表。

运行 Linux 的 Core i7 的页表结构

image-20211125214353034

image-20211125220442070

Core i7 采用四级页表结构

位数    9    9    9    9             12
      VPN1 VPN2 VPN3 VPN4(页框号) OFFSET(页内偏移)

VPN:虚拟页号

VPN1~4,每部分占 9 位。每一级的表项都是下一级的指针。最后到了四级页表,就查到了页框号,页框号(PPN),拼接页内偏移(PPO),就得到物理地址。

另外如果 TLB 命中,则可以直接得到 PPN,拼接 PPO,同样得到物理地址。

四级页表结构,一共 48 位,因此 Core i7 只支持 48 位(256TB)虚拟地址空间。

PPN+PPO 一共 52 位,因此 Core i7 只支持 52 位的物理地址空间。

拿到物理地址,并不是直接就去访存了。接下来是去访问 SRAM,未命中,才访问 DRAM。

Core i7 的第四级页表条目

image-20211125215301709

此 PTE 有三个访问位(权限位):

  • R/W 控制读 / 写权限
  • U/S 是否能在用户 / 内核模式中访问
  • XD 禁止从某些内存页取指令,防止缓冲区溢出攻击。

Linux 进程的虚拟空间

image-20211125220605700

从右侧看,进程地址空间分为内核虚拟内存和进程虚拟内存。

  • 内核虚拟内存包含内核中的代码和数据结构。
    • 内核虚拟内存的某些区域被映射到所有进程共享的物理页面。例如,每个进程共享内核的代码和全局数据结构。
    • 内核虚拟内存的其他区域包含每个进程都不相同的数据,比如说页表和内核在进程的上下文中执行代码时使用的栈,以及记录虚拟地址空间当前组织的各种数据结构。
  • 进程虚拟内存 包括进程的代码和数据段、堆和共享库以及栈段。

有趣的是,Linux 也将一组连续的虚拟页面(大小等于 DRAM)映射到相应的一组连续的物理页面,为内核提供了便利的方法来访问物理内存中的任何特定位置

而看地址空间的布局:

  1. 首先是用户栈,以 SP 为栈顶。其内容为栈帧。其大小随函数的调用和返回向下增减。
  2. 库内存映射区。存放诸如 GLIBC 的动态库,由动态链接器装载。可参考 链接、装载与库 — 动态链接 | Technology Blog (markrepo.github.io)
  3. 堆区。动态分配,向上增减。用于存一些独立于函数之间的状态。
  4. bss。存放编译阶段无法确定的全局数据,包括未初始化的全局变量和静态变量。
  5. data。存放编译时就能确定的全局数据,包括已初始化的全局变量和静态变量。可读可写。
  6. rodata。存放只读数据,比如字符串常量、全局 const 变量。常量区在程序中大小确定;在进程中内存只读。
  7. text。存放程序代码。

Linux 缺页异常处理

image-20211125221345937

当引发缺页中断时,内核的缺页处理程序,进行如下处理:

  • (1)判断虚拟地址 A 合法性。缺页处理程序搜索内存分区链表(在链表中构建树来查找),如果不合法,触发一个段错误(经典 Segmentation Fault),终止进程。对应图中情况 1
  • (2)试图进行的内存访问是否合法?权限对吗?出错触发页错误,对应图中情况 2
  • (3)如果是对合法虚拟地址的合法操作,那么就选择一个牺牲(被置换)页面,如果这个牺牲页面被修改过,就将它交换出去。换入新的页面并更新页表。

Linux 的内存映射

Linux 说白了就是把一个虚存区域对应到一个文件(未必是磁盘文件,比如可以是显存)。支持如下文件:

  • 普通文件映射:一个区域可以映射到一个普通磁盘文件的连续部分,例如一个可执行的目标文件。文件区被分成页大小的片,每一片包含一个虚拟页面的初始内容。因为按需进行页面调度,所以这些虚拟页面没有实际交换进入物理内存,直到 CPU 第一次引用到页面。如果区域比文件区要大,那么就用零来填充这个区域的余下部分。
  • 匿名文件映射:一个区域也可以映射到一个匿名文件,匿名文件是由内核创建的,包含的全是二进制零。CPU 第一次引用这样一个区域内的虚拟页面时,内核就在物理内存中找到一个合适的牺牲页面,如果该页面被修改过,就将这个页面换出来,用二进制零覆盖牺牲页面并更新页面表,将该页面标记为是驻留在内存中的。注意在磁盘和内存之间并没有实际的数据传送。因为这个原因,映射到匿名文件的区域中的页面有时也叫做请求二进制零的页。

匿名映射这里可能不太好理解。说白了就是把一块内存区域当作文件使用,而我们不需要实现创建这个文件。通过这个方法可以实现进程之间的共享内存。

GDT 和内存分段机制

段式内存管理

在早期内存较小的时候,可以通过物理地址直接访问内存。后来在 8086 处理器上,寄存器只有 16 位,而地址总线是 20 位。为了访问这个地址,就引入了 段寄存器,用于存放段基地址。

实际访存地址 = 段基地址 << 4 + 段内偏移

但后来有了保护模式,需要判断地址是否允许访问。全局描述符表用于存放段描述符,其中主要包含:

  • 属性
  • 段基地址
  • 段界限

GDT

全局描述符表 (GDT) 是 x86 架构用于内存定界的数据结构,它的作用是描述内存分段。又称段描述符表。格式如下:

struct gdt_entry {
    uint16_t limit_low;       
    uint16_t base_low;
    uint8_t base_middle;
    uint8_t access;
    unsigned limit_high: 4;
    unsigned flags: 4;
    uint8_t base_high;
} __attribute__((packed));

而引入段描述符之后,段寄存器不再存放段基地址,而是存放选择器,相当于段描述符指针(索引)。指向 GDT 中的一个段描述符。当某个进程访存时,段描述符选择器指向该程序的段描述符,CPU 会检查内存地址是否在段描述符所限定的区域内,从而避免了非法访问。

GDT 的入口地址通过 GDTR 寄存器告知 x86 CPU.

LDT

相对于全局的 GDT,LDT 是局部描述符表,只对单个进程可见。操作系统可以自行决定 LDT 的存放位置,并告诉 CPU。每个任务最多可以拥有一个 LDT。另外,每一个 LDT 自身作为一个段存在,它们的段描述符被放在 GDT 中。

类比多级分页,你可以理解 GDT 和 LDT 构成二级内存分段。

LDT 的入口地址放在 LDTR。

段选择器结构

段选择器是一个 16 位的结构体:

15                       3    2    1  0
+--------------------------+----+-----+
|          Index           | TI | RPL | 
+--------------------------+----+-----+
  • RPL:请求特权级别,通俗的讲我用什么权限来请求。
  • TI,Table Indicator:TI=0 时,查 GDT 表;TI=1 时,查 LDT 表。
  • Index:处理器将索引值 « 3 + DT 表入口基地址(位于 LDTR/GDTR),就是要加载的段描述符。

参考

(1)Computer Systems: A Programmer’s Perspective, 3/E (CS:APP3e) p837

(2)《现代操作系统》3.3

(3)linux 的高端内存是什么? - 知乎 (zhihu.com)

(4)页表及页表项的设计 - 存储模型(2) | Coursera

(5)[第 9 章 虚拟内存之 Linux 内存系统 | 野渡 的博客 (wendeng.github.io)](https://wendeng.github.io/2019/05/22 / 操作系统 / 第 9 章 虚拟内存之 Linux 内存系统 /)

(6)文件页和匿名页 - yooooooo - 博客园 (cnblogs.com)