9.1 物理和虚拟寻址

计算机系统的主存被组织成一个由M个连续字节大小的单元组成的数组。每个字节都有一个唯一的物理地址。

image.png

当CPU执行加载指令时，会生成一个有效物理地址，通过内存总线传递给主存。主存取出物理地址的内容返回给CPU，CPU会将它存放在一个寄存器里。

9.3 虚拟内存作为缓存的工具

磁盘上数组被分割成块。VM系统通过将虚拟内存分割为称为虚拟页的大小固定的块。

9.3.1 DRAM缓存的组织结构

DRAM比SRAM慢大约10倍，磁盘比DRAM慢大约100000多倍。因此DRAM缓存中的不命中比SRAM缓存中的不命中昂贵的多，因为DRAM缓存不命中要由磁盘来服务。 从磁盘的一个扇区读取第一个字节的时间开销比起读这个扇区中连续的字节要慢大约100000倍。

因为大的不命中触发和访问第一个字节的开销，虚拟页往往很大。DRAM缓存是全相联的，任何虚拟页都可以放在任何的物理页中

9.3.2 页表

  • 页表：存放在物理内存中的数据结构，是一个页表条目(PTE)的数组。

假设每个PTE由一个有效位和一个n位地址字段组成。有效位表明该虚拟页当前是否被缓存在DRAM中，如果设置有效位，地址字段标识DRAM中相应物理也的起始位置；如果没有设置有效位。一个空地址标识这个虚拟页还未被分配，否则这个地址就指向该虚拟页在磁盘上的起始位置。

image.png

9.3.4 缺页

  • 缺页：DRAM缓存不命中称为缺页。

缺页异常调用内核中的缺页异常处理程序，选择一个牺牲页，将它复制回磁盘；再从磁盘复制缺的那一页到内存中，并更新页表中对应的PTE。异常处理程序返回时，重启导致缺页的指令，该指令把导致缺页的虚拟地址重发送到地址翻译硬件。

9.3.5 分配页面

例如 调用malloc时；页面的分配过程是在磁盘上创建空间并更新PTE n，使它指向磁盘上这个新创建的页面。

9.4 虚拟内存作为内存管理工具

多个虚拟页面可以映射到同一个共享物理页面上：

image.png

一般而言，每个进程都有自己私有的代码、数据、堆以及栈区域，是不和其他进程共享的。这种情况下，OS创建页表，将相应的虚拟页映射到不连续的物理页面。

9.5 虚拟内存作为内存保护的工具

通过在PTE上添加一些额外的许可位来控制对一个虚拟页面内容的访问十分简单。

image.png

SUP位标识晋城市否必须运行在内核模式下才能访问该页。

如果一条指令违反了许可条件，CPU就触发一个一般保护故障。Linux shell一般将这种一场报告为”段错误”(segmentation fault)

9.6 地址翻译

n位虚拟地址包含两个部分：一个p位的虚拟页面偏移和一个(n-p)位的虚拟页号

image.png

9.6.2 利用TLB加速地址翻译

在MMU中包括了一个关于PTE的小的缓存，称为翻译后备缓冲器(TLB)

TLB中每一行都保存着一个由单个PTE组成的块。

image.png

TLB索引是由VPN的t个最低位组成，TLB标记由VPN剩余的位组成的。

9.6.3 多级页表

image.png

第k级页表中的每个PTE包含某个物理页面的PPN

页表：VPN并不是页表的一部分，也不储存在内存中。

9.8 内存映射

Linux通过将一个虚拟内存区域与一个磁盘上的对象关联起来，以初始化这个虚拟内存区域的内容，虚拟内存可以映射到两种类型的对象：

image.png

9.8.1 共享对象

一个对象可以被映射到虚拟内存的一个区域，要么作为共享对象，要么作为私有对象。

  • 一个进程对共享区域的任何写操作，对那些把该共享对象映射到它们虚拟内存的进程而言，也是可见的。而且这些变化会反映在磁盘的原始对象中。
  • 对一个映射到私有对象的区域做改变，对于其他进程来说是不可见的。也不会反映在磁盘上的起始位置对象中。

image.png

  • 私有对象使用写时复制(copy-on-write)技术被映射到虚拟内存中。

image.png

对于每个映射私有对象的进程，相应私有区域的页表条目都被标记为只读，并且区域结构被标记为私有的写时复制。只要没有进程试图写它自己的宿友区域，它们就可以共享物理内存中对象的一个单独副本。只要有一个进程试图写私有区域的某个页面，这个写操作就会触发保护故障。

故障处理程序：在物理内存中创建这个页面的一个新副本。更新页表条目指向这个新的副本。然后恢复这个页面的可写权限。当故障处理程序返回时，CPU重新执行写操作，就可以在新创建的页面上执行写操作了。

然后，进程2进程会修改复制出来的页面，而不是属于进程1的页面。显然，当使用写时复制技术时，仅复制任何一进程修改的页面，所有未修改的页面可以由两个进程共享。

9.8.2 再看fork函数

当fork函数被当前进程调用时，内核为新进程创建各种数据结构并分配一个唯一的PID。它将两个进程中的每个页面都标记为只读，并将两个进程中每个区域结构都标记为私有的写时复制。

当fork在新进程中返回时，新进程现在的虚拟内存刚好和调用fork时存在的虚拟内存相同。当两个进程中的人一个后来进行写操作时，写时复制机制就会创建新页面，因此，就位每个进程保持了私有地址空间的抽象概念。

9.8.3 再看execve函数

在当前进程执行：

  1. execve("a.out",NULL,NULL);

execve函数在当前进程中加载并运行包含在可执行目标文件中的程序，用该程序代替当前程序。

记载并运行a.out需要以下步骤：

  • 删除已存在的用户区域：删除当前进程虚拟地址的用户部分中的已存在的区域结构
  • 映射私有区域：为新程序的代码、数据、bss和栈区域创建新的区域结构。所有这些新的区域都是私有的、写时复制的。image.png
  • 映射共享区域：如果a.out程序与共享对象链接，比如标准C库libc.so，那么这些对象都是动态链接到该程序的，然后再映射到用户虚拟地址空间中的共享区域内。
  • 设置程序计数器(PC)：设置当前进程上下文中的程序计数器，使之指向代码区域的入口点。

image.png

9.8.4 使用mmap函数的用户级内存映射

Linux进程可以使用mmap函数创建新的虚拟内存区域，将对象映射到这些区域中：

  1. #include<unistd.h>
  2. #include<sys/mman.h>
  4. void *mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset);

mmap函数要求内核创建一个新的虚拟内存区域，最好是从地址start开始的一个区域，并将文件描述符fd指定的对象的一个连续的片映射到这个新的区域。连续的对象片大小为length字节，从距文件开始处偏移量为offset字节的地方开始。start地址仅仅是一个暗示，通常被定义为NULL

image.png

参数prot包含描述新映射的虚拟内存区域的访问权限位(即在相应区域结构中的vm_prot位)。

  • PROT_EXEC：这个区域内的页面可以被CPU执行的指令组成。
  • PROT_READ：这个区域的页面可读。
  • PROT_WRITE：这个区域内的页面可写。
  • PROT_NONE：这个区域内的页面不能被访问。

参数flags由描述被映射对象类型的位组成。

image.png

让内核创建一个新的包含size字节的只读、私有、请求二进制零的虚拟内存区域。若调用成功，那么bufp包含新区域的地址。

Hint：文件描述符fd有0、1、2。0：stdin，1：stdout，2：stderr。

9.9 动态内存分配

动态内存分配器维护一个进程的虚拟内存区域——堆。堆是一个请求二进制零的区域，进阶在未初始化的数据区域后开始，并向上增长。对于每个进程，内核维护一个变量brk，指向堆的顶部。

image.png

9.9.1 malloc和free函数

  1. #include<stdlib.h>
  3. void *malloc(size_t size);

malloc函数返回一个指针，指向大小至少为size字节的内存块，这个块会为可能包含在这个块内的任何数据对象类型做对齐。在32位模式中，**malloc**返回的块的地址总是8的倍数；在64位中，总是16的倍数。

malloc不初始化它返回的内存。calloc是一个基于malloc的瘦包装函数，将分配的内存初始化为零。realloc可以改变一个以前已分配块的大小。

通过free函数释放已分配的堆块。

9.9.3 分配器的要求和目标

image.png

9.9.4碎片

造成堆利用率低的主要原因是碎片现象。分为内部碎片和外部碎片。

  • 内部碎片：在一个已分配块比有效载荷大时发生的。
  • 外部碎片：当空闲内存合计起来足够满足一个分配请求，但是没有一个单独的空闲块足够大可以来处理这个请求。

9.9.11 带边界标记的合并

合并内存中下一个空闲快很简单、高效，但是合并前面的块就不同了，正常需要搜索整个链表，记住前面的块的位置，直到到达当前块。

使用隐式空闲链表意味着每次调用free需要的时间都与堆的大小成线性关系。

边界标记：允许在常数时间内进行对前面块的合并。在每个块的结尾处加一个脚部(边界标记)，其中脚部就是头部的一个副本。如果每个块都包含这样一个脚部，那么就可以通过检查它的脚部来判断前面一个块的起始位置和状态。

image.png

当分配器释放当前块时所有可能存在的情况：

  1. 前面的块和后面的块都是已分配的。
  2. 前面的块是已分配的，后面的块时空闲的。
  3. 前面的块是空闲的，而后面的块时已分配的。
  4. 前面的和后面的块都是空闲的。

image.png

9.9.14 分离的空闲链表

一种更好的方法是将空闲块组织为某种形式的显式数据结构。堆可以组织成一个双向链表，在每个空闲块中都包含一个pred和一个succ指针。

image.png

使用双向链表而不是隐式空闲链表，使首次适配的分配时间从块总数的限行时间减少到空闲块数量的限行时间。

由于需要在空闲块中多包含两个指针，所以导致了更大的最小块大小，提高了内部碎片的程度。

9.10 垃圾收集

9.10.1 垃圾收集器的基本知识

垃圾收集器将内存视为一张有向可达图，分为一组根节点和一组堆节点。每个堆节点对应于堆中的一个已分配块。根节点对应于不在堆中的位置，包含指向堆中的指针。

image.png

无论何时需要堆空间，应用都会用通常的方式调用malloc。如果malloc找不到合适的空闲块，那么它就调用垃圾收集器，希望能够回收一些垃圾到空闲链表。