第五讲：虚拟存储器（Virtual Memory） 虚拟地址空间、虚拟存储器的实现

分页（Paging） 基本思想： 内存被分成固定长且比较小的存储块（页框、实页、物理页、PP） 每个进程也被划分成固定长的程序块（页、虚页、逻辑页、VP） 物理页与逻辑页通常保持同样大小 程序块可装到存储器中可用的存储块中 无需用连续页框来存放一个进程 三种页 Cached Uncached Unallocated

“主存--磁盘”的“Cache” 与“Cache--主存”层次相比： 页大小（2KB~64KB）比Cache中的Block大得多！ 采用全相联映射！ 因为缺页的开销比Cache缺失开销大的多！缺页时需要访问磁盘（约 几百万个时钟周期），而cache缺失时，访问主存仅需几十到几百个 时钟周期！因此，页命中率比cache命中率更重要！“大页面”和 “全相联”可提高页命中率。 通过软件来处理“缺页”！ 缺页时需要访问磁盘（约几百万个时钟周期），慢！不能用硬件实现。 采用Write Back写策略！ 避免频繁的慢速磁盘访问操作。 地址转换用硬件实现！ 加快指令执行

虚地址到物理地址的映射

页表 页表项示例

虚存与进程 虚存是每一进程具有独立的地址空间，同时支持不同进程对同一物理地址的共享访问。 虚存方便实现针对进程的页级内存访问保护。

页命中与页缺失处理流程

TLB - translation lookaside buffer 减少到内存查页表的次数！

TLB命中与缺失

一个简化的存储系统举例 假定以下参数，则虚拟地址和物理地址如何划分？共多少页表项？ 14-bit virtual addresses（虚拟地址14位） 12-bit physical address（物理地址12位） Page size = 64 bytes（页大小64B） 页表项数应为：214-6=256 13 12 11 10 9 8 7 6 5 4 3 2 1 VPO VPN Virtual Page Number Virtual Page Offset 11 10 9 8 7 6 5 4 3 2 1 PPO PPN Physical Page Number Physical Page Offset

一个简化的存储系统举例（续） 假定部分页表项内容（十六进制表示）如右： – 007 006 1 16 005 004 02 003 33 002 001 28 000 Valid PPN VPN 1 0D 02F 11 02E 2D 02D – 02C 02B 09 02A 17 029 13 028 Valid PPN VPN 假定部分页表项内容（十六进制表示）如右： 假定TLB如下：16 个TLB项，4路组相联，则TLBT和TLBI各占几位？ 13 12 11 10 9 8 7 6 5 4 3 2 1 VPO VPN TLBI TLBT – 02 1 34 0A 0D 03 07 3 06 08 2 04 2D 00 09 Valid PPN Tag Set

一个简化的存储系统举例（续） 假定Cache的参数和内容（十六进制）如下：16 行，主存块大小为4B，直接映射，则主存地址如何划分？ 11 10 9 8 7 6 5 4 3 2 1 PPO PPN CO CI CT 03 DF C2 11 1 16 7 – 31 6 1D F0 72 36 0D 5 09 8F 6D 43 32 4 3 08 04 02 00 1B 2 15 23 99 19 B3 B2 B1 B0 V Tag Idx – 14 F D3 1B 77 83 1 13 E 15 34 96 04 16 D 12 C 0B B 3B DA 93 2D A 9 89 51 00 3A 24 8 B3 B2 B1 B0 V Tag Idx

一个简化的存储系统举例（续） 假设该存储系统所在计算机采用小端方式， CPU执行某指令过程中要求访问一个16位数据，给出的逻辑地址为0x03D4，说明访存过程。 VPN ___ TLBI ___ TLBT ____ TLB Hit? __ Page Fault? __ PPN: ____ 物理地址为 CO ___ CI___ CT ____ cache Hit? __ 数据: ____ 13 12 11 10 9 8 7 6 5 4 3 2 1 VPO VPN TLBI TLBT 0x0F 0x3 0x03 Y N 0x0D 问题：逻辑地址为0x0A7A、0x0507时的访存过程如何？ TLB缺失/cache缺失、TLB缺失/缺页 11 10 9 8 7 6 5 4 3 2 1 PPO PPN CO CI CT 0x5 0x0D Y 0x7236

页表存储 大多数虚存实现方案将页表存储于虚存而不是实存（主存）中，即页表自身也会发生paging。 当一个进程运行时，至少一部分它的页表（包括当前执行使用到的页表项）要装入主存中 典型情况下，一个页表的最大尺寸与一页的大小相同 为减少页表的大小，一些处理器使用两级的页表组织： 第一级为页目录（page directory），其中每一目录项指向一个页表（第二级） 如果一页目录额长度为X且页表的最大长度为Y，则一个进程最大可访问X*Y个页

两级页表层次结构

两级页表结构实例（ARM处理器）

两级页表结构实例（Pentium处理器）

K级页表结构

段式虚拟存储器 Segmentation is usually visible to the programmer and is provided as a convenience for organizing programs and data and as a means for associating privilege and protection attributes with instructions and data. Segmentation allows the programmer to view memory as consisting of multiple address spaces or segments. 优点： 简化动态增长数据结构的处理 通过将程序分为多个段，可允许程序各部分独立进行修改和重编译，而无需整个程序重新链接和加载 易于共享和保护

Pentium II的多种虚存模式支持 The Pentium II includes hardware for both segmentation and paging. Both mechanisms can be disabled, allowing the user to choose from four distinct views of memory: Unsegmented unpaged memory: In this case, the virtual address is the same as the physical address. This is useful, for example, in low-complexity, high performance controller applications. Unsegmented paged memory: Here memory is viewed as a paged linear address space. Protection and management of memory is done via paging. This is favored by some operating systems (e.g., Berkeley UNIX). Segmented unpaged memory: Here memory is viewed as a collection of logical address spaces. The advantage of this view over a paged approach is that it affords protection down to the level of a single byte, if necessary. Segmented paged memory: Segmentation is used to define logical memory partitions subject to access control, and paging is used to manage the allocation of memory within the partitions. Operating systems such as UNIX System V favor this view.

页表存储——Inverted Page Table 虚地址中的虚页号部分通过一简单的Hash函数映射到一Hash值，该值指向inverted page table中的某一页表项 该inverted page table中为每一实存中的页框（注意不是虚存页）维护一个表项。因此无论虚地址空间多大，页表（及其所占存储）的大小是固定的。 由于多个虚地址可能映射到同一Hash表项，需要使用一种chaining机制来处理此种情况，同时为加快查找速度，该Hash函数将 chain保持在较短的长度（典型情况下介于1-2项之间）

Inverted Page Table Structure

第五讲：虚拟存储器（Virtual Memory） 存储器映射 动态存储器分配

存储器映射 通过将一个虚拟存储器区域与一个磁盘上的对象关联起来，实现虚拟存储器区域内容的初始化。 虚拟存储器区域可以映射到两种类型的磁盘对象： Unix文件系统中的普通文件：区域映射至普通磁盘文件的连续部分——文件的节划分为页面大小的块，其中包含虚存页的初始内容 匿名文件：第一次引用与之关联的虚存页时，由内核创建（即分配并初始化一全0 的物理页） 虚存页初始化后将在实存与内核维护的一交换文件/空间（swap file或swap space）之间换入和换出 任何时候，交换空间的大小决定了当前运行进程能够分配和访问的虚存页的总数

共享对象（Shared Objects） 虚存系统为每个进程提供了私有的虚拟地址空间，但不同进程可能包含同样的只读代码（文本）区域，例如printf库代码。 存储器映射提供了简洁清晰的机制来控制对象在多个进程间共享——共享对象 vs 私有对象 共享对象被映射到进程的虚拟地址空间中的一个区域。对该区域的写操作对其他同样映射了该共享对象的进程是可见的，并反映到磁盘中的原始对象上 对私有对象的改变对其他进程不可见，且之上的写操作不反映至磁盘

进程1和2将同一共享对象（由唯一的对象文件名标识）映射至自己的地址空间，并可能具有不同的虚拟地址（左图）。 物理存储器中只有共享对象的一个拷贝 私有对象的写时拷贝： 初始时进程共享私有对象在物理存储器中的同一拷贝（相应页表项标记为只读，区域结构标记为私有写时拷贝）。 一进程首次试图写该区域的某页面时，将触发保护故障 故障处理程序在物理存储器中创建该页面的一个新拷贝，并更新页表条目指向该拷贝并设置可写权限。

创建新进程——fork 当前进程调用fork 内核创建新进程的相关数据结构，分配唯一PID 创建当前进程的mm_struct、区域结构和页表的拷贝，并标记每个页为只读、每个区域结构为私有写时拷贝 当fork返回至新进程时，其虚拟存储器与fork调用前的当前进程的虚存一致。其后，任一进程进行写操作时，写时拷贝机制将创建新页面，使每一进程拥有私有的地址空间

加载和运行程序——execve 当前进程调用execve(“a.out”, NULL, NULL)，后者在当前进程中加载并运行a.out中的程序 删除当前进程虚拟地址的用户部分中已存在的区域 创建并映射新程序的私有区域（写时拷贝），其中bss区域映射到匿名文件 映射共享区域（如libc.so） 设置程序计数器（PC）指向代码入口点

用户级存储器映射 可使用mmap函数创建新的存储器区域，并将对象映射到区域 mmap函数请求内核创建一新的虚存区域，期望起始于地址start，并将文件描述符fd指定的对象的一个连续片（长度为length，开始于文件偏移量offset）映射到该新区域。 Prot指定区域的访问权限位：可读/可写/可执行 Flags指定被映射对象的类型：匿名对象、私有写时拷贝、共享对象 munmap函数删除指定区域

Mmap函数参数含义

动态存储器分配 动态存储分配器：维护进程的一个称为堆的虚拟存储器区域，紧接在bss区域后向更高地址生长。 内核维护一变量brk指向堆的顶部 分配器将堆视为一组不同大小的块的集合，块是连续的虚存片

malloc和free C标准库提供malloc显式分配器，供程序调用来从堆中分配块 malloc函数返回指向大小至少为size字节的存储器块的指针，并且该块按可能包含在块中的数据对象类型对齐（Unix系统上按8字节双字边界对齐） malloc不初始化分配的块 calloc函数将分配的存储器块初始化为0 realloc函数可以来改变已分配块的大小

malloc和free free函数释放已分配的堆块 实质上是将块标记为“free” malloc和free函数优点在于简单高效，缺点是可能造成两种类型的（存储器）碎片化“fragmentation” Internal fragmentation：malloc一次分配满足所需且为2的指数大小的存储器块，因此可能分配超出所需的额外的空间，从而导致对可用存储器的浪费 External fragmentation：free只是将释放的块比较为free，使得尽管总的空闲存储器满足分配请求，但可能分散于多个不连续的片（chunks）中，因此导致无法满足分配需求或被迫低效地转而分配更大的块（internal fragmentation）

使用mmap动态分配存储器 对于大块的存储器分配，可利用前述glibc的匿名存储器映射（anonymous memory mapping）来满足分配需求 可获得一大且初始化为0的内存块，可视为一个新的、一次性分配的堆 由于分配在堆外的存储器空间，不会造成堆空间的fragmentation 分配一由内核决定开始位置（start=NULL）的、可读可写的、匿名、私有的块在于简单高效，缺点是可能造成两、种类型的（存储器）碎片化“fragmentation”

使用mmap动态分配存储器 优点： 没有fragmentation问题。当程序不再需要分配的存储器空间时，可使用munmap将其立即释放返回给系统。 Anonymous memory mapping分配的块可修改大小、权限等属性 每次分配到的存储器空间位于不同的存储器映射中，无需维护一个全局堆 缺点： 分配的块大小为系统页面大小的整数倍，因此可能造成超出所需的空间的闲置浪费，尤其是在所需的空间相对（闲置部分）较小时 创建memory mapping比通过堆进行动态分配需要更多的处理开销 ，因前者需要与内核交互而后者无需。分配的块越小，该不利之处越突出。

IA32存储访问

IA-32的存储管理 按字节编址（通用计算机大都是） 在保护模式下，IA-32采用段页式虚拟存储管理方式 存储地址采用逻辑地址、线性地址和物理地址来进行描述，其中，逻辑地址和线性地址是虚拟地址的两种不同表示形式，描述的都是4GB虚拟地址空间中的一个存储地址 逻辑地址由48位组成，包含16位段选择符和32位段内偏移量（即有效地址） 线性地址32位（其位数由虚拟地址空间大小决定） 物理地址32位（其位数由存储器总线中的地址线条数决定） 分段过程实现将逻辑地址转换为线性地址 分页过程实现将线性地址转换为物理地址 Cache提供高速的访存

IA-32处理器的存储器寻址 x + + 段寄存器 基址寄存器 SS 变址寄存器 段选择符 CS 段表项(段描述符 ) 线性地址到主存地址转换再通过分页完成 段寄存器 基址寄存器 线性地址空间 SS 变址寄存器 段选择符 x CS 比例因子1/2/4/8 段表项(段描述符 ) 段限 偏移量8/16/32位 + 有效地址 基址 + 存取权限 线性地址 段限 段基址 如何从段寄存器获得段选择符，再从段选择符获得段描述符？

段选择符和段寄存器 段寄存器（16位），用于存放段选择符 CS(代码段)：程序代码所在段 SS(栈段)：栈区所在段 DS(数据段)：全局静态数据区所在段 其他3个段寄存器ES、GS和FS可指向任意数据段 段选择符各字段含义： TI=0，选择全局描述符表(GDT)，TI=1，选择局部描述符表(LDT) RPL=00，为第0级，位于最高级的内核态，RPL=11，为第3级，位 于最低级的用户态 高13位索引用来确定当前使用的段描述符在描述表中的位置 CS寄存器中的RPL字段表示CPU的当前特权级（Current Privilege Level，CPL）

段寄存器的含义 SS（栈段寄存器） ES/GS/FS（辅助段寄存器） DS（数据段寄存器） CS（代码段寄存器） brk %esp (栈顶) brk 0xC00000000 0x08048000 Kernel virtual memory Memory-mapped region for shared libraries Run-time heap (created by malloc) User stack (created at runtime) Unused Read/write segment (.data, .bss) Read-only segment (.init, .text, .rodata) SS（栈段寄存器） ES/GS/FS（辅助段寄存器） DS（数据段寄存器） CS（代码段寄存器）

段描述符和段描述符表 段描述符是一种数据结构，实际上就是段表项，分两类： 用户进程的代码段和数据段描述符 系统控制段描述符，又分两种： 特殊系统控制段描述符，包括：局部描述符表（LDT）描述符和任务状态段（TSS）描述符 控制转移类描述符，包括：调用门描述符、任务门描述符、中断门描述符和陷阱门描述符 描述符表实际上就是段表，由段描述符组成。有三种类型： 全局描述符表GDT：只有一个，用来存放系统内每个任务都可能访问的描述符，例如，内核代码段、内核数据段、用户代码段、用户数据段以及TSS（任务状态段）等都属于GDT中描述的段 局部描述符表LDT：存放某任务（即用户进程）专用的描述符 中断描述符表IDT：包含256个中断门、陷阱门和任务门描述符 IDT将在第7章介绍

段描述符的定义 当CPL>DPL时，说明当前特权级比所要求的最低等级更低，故访问越权 B31~B0： 32位基地址； L19~L0：20位限界，表示段中最大页号 G：粒度。G=1以页（4KB）为单位；G=0以字节为单位。因为界限为20位，故当G=0时最大的段为1MB；当G=1时，最大段为4KB×220 =4GB D：D=1表示段内偏移量为32位宽，D=0表示段内偏移量为16位宽 P：P=1表示存在，P=0表示不存在。Linux总把P置1，不会以段为单位淘汰 DPL：访问段时对当前特权级的最低等级要求。因此，只有CPL为0（内核态）时才可访问DPL为0的段，任何进程都可访问DPL为3的段（0最高、3最低） S：S=0系统控制描述符，S=1普通的代码段或数据段描述符 TYPE：段的访问权限或系统控制描述符类型 A：A=1已被访问过，A=0未被访问过。（通常A包含在TYPE字段中）

用户不可见寄存器 为支持分段机制，CPU中有多个用户进程不可访问的内部寄存器，操作系统通过特权指令可对寄存器TR、LDTR、GDTR和IDTR进行读写 每次段寄存器装入新选择符时，新描述符装入描述符cache，在逻辑地址到线性地址转换时，MMU直接用描述符cache中的信息，不必访问主存段表 TR(任务寄存器)存放TSS描述符的段选择符 LDTR(LDT寄存器)存放LDT描述符的段选择符 TSS描述符和LDT描述符在GDT中 LDT首地址 GDT和IDT只有一个，GDTR和IDTR指向各自起始处。例如，根据TR取GDT中的TSS描述符时，GDTR给出首址 GDT首地址

逻辑地址向线性地址转换 被选中的段描述符先被送至描述符cache，每次从描述符cache中取32位段基址，与32位段内偏移量（有效地址）相加得到线性地址 GDT LDT

IA-32/Linux中的分段机制 为使能移植到绝大多数流行处理器平台， Linux简化了分段机制 RISC对分段支持非常有限，因此Linux仅使用IA-32的分页机制，而对于分段，则通过在初始化时将所有段描述符的基址设为0来简化 若把运行在用户态的所有Linux进程使用的代码段和数据段分别称为用户代码段和用户数据段；把运行在内核态的所有Linux进程使用的代码段和数据段分别称为内核代码段和内核数据段，则Linux初始化时，将上述4个段的段描述符中各字段设置成下表中的信息： 初始化时，上述4个段描述符被存放在GDT中

IA-32中的分页与控制寄存器 控制寄存器保存机器的各种控制和状态信息，它们将影响系统所有任务的运行，操作系统进行任务控制或存储管理时使用这些控制和状态信息。 CR0：控制寄存器 ① PE: 1为保护模式。一旦在保护模式，不能再将PE清0，只能重启系统以回到实模式。② PG：1-启用分页；0-禁止分页，此时线性地址被直接作为物理地址使用。若要启用分页机制，则PE和PG都要置1。③任务切换位TS：任务切换时将其置1，切换完毕则清0，可用CLTS指令将其清0。④ 对齐屏蔽位AM。⑤ cache功能控制位NW（（Not Write-through）和CD（Cache Disable）。只有当NW和CD均为0时，cache才能工作。 CR2：页故障线性地址寄存器 存放引起页故障的线性地址。只有在CR0中的PG=1时，CR2才有效。 CR3：页目录基址寄存器 保存页目录表的起始地址。只有当CR0中的PG=1时，CR3才有效。

线性地址向物理地址转换 页目录项和页表项格式一样，有32位（4B）

页目录项和页表项 P：1表示页表或页在主存中；P=0表示页表或页不在主存，即缺页，此时需将页故障线性地址保存到CR2。 R/W：0表示页表或页只能读不能写；1表示可读可写。 U/S：0表示用户进程不能访问；1表示允许访问。 PWT：控制页表或页的cache写策略是全写还是回写（Write Back）。 PCD：控制页表或页能否被缓存到cache中。 A：1表示指定页表或页被访问过，初始化时OS将其清0。利用该标志，OS可清楚了解哪些页表或页正在使用，一般选择长期未用的页或近来最少使用的页调出主存。由MMU在进行地址转换时将该位置1。 D：修改位(脏位dirty bit)。页目录项中无意义，只在页表项中有意义。初始化时OS将其清0，由MMU在进行写操作的地址转换时将该位置1。 高20位是页表或页在主存中的首地址对应的页框号，即首地址的高20位。每个页表的起始位置都按4KB对齐。

补 充

Virtual Memory of a Linux Process Process-specific data structs (ptables, task and mm structs, kernel stack) Different for each process Kernel virtual memory Physical memory Identical for each process Kernel code and data User stack %esp Memory mapped region for shared libraries Process virtual memory brk Runtime heap (malloc) Uninitialized data (.bss) Initialized data (.data) 0x08048000 (32) 0x40000000 (64) Program text (.text)

Linux将虚存空间组织成“区域(area)”的集合 vm_next task_struct mm_struct pgd mm mmap vm_area_struct vm_end vm_prot vm_start Process virtual memory Text Data Shared libraries vm_flags 全局页目录地址 pgd: Page global directory address Points to L1 page table vm_prot: Read/write permissions for this area vm_flags Pages shared with other processes or private to this process 指向L1页表(装入CR3) 访问权限 是共享还是本进程私有

Linux Page Fault Handling read 1 write 2 3 vm_next vm_area_struct vm_end vm_prot vm_start Process virtual memory text data shared libraries vm_flags Linux页故障类型 Segmentation fault: accessing a non-existing page Normal page fault not in memory Protection exception: e.g., violating permission by writing to a read-only page (Linux reports as Segmentation fault)

Intel Core i7 Memory System Processor package Core x4 Registers Instruction fetch MMU (addr translation) L1 d-cache 32 KB, 8-way L1 i-cache 32 KB, 8-way L1 d-TLB 64 entries, 4-way L1 i-TLB 128 entries, 4-way L2 unified cache 256 KB, 8-way L2 unified TLB 512 entries, 4-way To other cores QuickPath interconnect 4 links @ 25.6 GB/s each To I/O bridge L3 unified cache 8 MB, 16-way (shared by all cores) DDR3 Memory controller 3 x 64 bit @ 10.66 GB/s 32 GB/s total (shared by all cores) Main memory

End-to-end Core i7 Address Translation CPU 32/64 L2, L3, and main memory Result Virtual address (VA) 36 12 VPN VPO L1 miss L1 hit 32 4 TLBT TLBI L1 d-cache (64 sets, 8 lines/set) TLB hit TLB miss ... ... L1 TLB (16 sets, 4 entries/set) 9 9 9 9 40 12 40 6 6 VPN1 VPN2 VPN3 VPN4 PPN PPO CT CI CO Physical address (PA) CR3 PTE PTE PTE PTE 页表项PTE：占64位=8B，512项x8B=4KB Page tables

Core i7 Level 1-3 Page Table Entries 下级页表的物理基地址 Unused G PS A CD WT U/S R/W P=1 51 12 11 9 8 7 6 5 4 3 2 1 XD Available for OS (page table location on disk) P=0 52 62 63 Each entry references a 4KB child page table P: Child page table present in physical memory (1) or not (0). R/W: Read-only or read-write access permission for all reachable pages. U/S: user or supervisor (kernel) mode access permission for all reachable pages. WT: Write-through or write-back cache policy for the child page table. CD: Caching disabled or enabled for the child page table. A: Reference bit (set by MMU on reads and writes, cleared by software). PS: Page size either 4 KB or 4 MB (defined for Level 1 PTEs only). G: Global page (don’t evict from TLB on task switch) Page table physical base address: 40 most significant bits of physical page table address (forces page tables to be 4KB aligned)

Core i7 Level 4 Page Table Entries 63 62 52 51 12 11 9 8 7 6 5 4 3 2 1 XD Unused 物理页(页框)的物理基地址 Unused G D A CD WT U/S R/W P=1 Available for OS (page table location on disk) P=0 Each entry references a 4KB child page P: Child page table present in physical memory (1) or not (0). R/W: Read-only or read-write access permission for all reachable pages. U/S: user or supervisor (kernel) mode access permission for all reachable pages. WT: Write-through or write-back cache policy for the child page table. CD: Caching disabled or enabled for the child page table. A: Reference bit (set by MMU on reads and writes, cleared by software). D: Dirty bit (set by MMU on writes, cleared by software) G: Global page (don’t evict from TLB on task switch) Page physical base address: 40 most significant bits of physical page address (forces pages to be 4KB aligned)

Core i7 Page Table Translation 9 9 9 9 12 Virtual address VPN 1 VPN 2 VPN 3 VPN 4 VPO L1 PT Page global directory L2 PT Page upper directory L3 PT Page middle directory L4 PT Page table 40 40 40 40 CR3 / / / / / Physical address of L1 PT 12 Offset into physical and virtual page L1 PTE L2 PTE L3 PTE L4 PTE Physical address of page 512 GB region per entry 1 GB region per entry 2 MB region per entry 4 KB region per entry 40 / 40 12 Physical address PPN PPO

Cute Trick for Speeding Up L1 Access Physical address (PA) CT CO 36 6 CI Virtual addres s (VA) VPN VPO 12 PPO PPN Address Translation No Change L1 Cache Tag Check Observation Bits that determine CI identical in virtual and physical address Can index into cache while address translation taking place Generally we hit in TLB, so PPN bits (CT bits) available next “Virtually indexed, physically tagged” Cache carefully sized to make this possible