系统中的进程与其他进程共享CPU和主存。首先进程多需要的内存也多，其次内存易被破坏，如进程A不小心写入进程B使用的内存。为更有效管理内存且少出错，系统提供对主存的抽象概念叫虚拟内存。虚拟内存是硬件异常、硬件地址翻译、主存、磁盘文件和内核的完美交互，为每个进程提供大的、一致的和私有的地址空间，虚拟内存提供三个重要能力：
使用主存更有效率：用 DRAM 作为部分的虚拟地址空间的缓存简化内存管理：每个进程都有统一的线性地址空间隔离地址空间：进程间不会相互影响；用户程序不能访问内核信息和代码1 地址空间
物理地址通常应用在“简单”的嵌入式微控制器中（汽车、电梯等），内存管理较简单，但现代计算机，包括其他智能设备如笔记本电脑、智能手机等，需要较复杂的内存管理机制，因此虚拟地址必不可少，它是计算机科学中最伟大的ideas之一。
2 虚拟内存作为缓存工具
概念上来说，虚拟内存就是存储在磁盘上的 N 个连续字节的数组。磁盘上数组的内容被缓存在物理内存上（DRAM缓存）），其中的每个缓存块(cache block)就称为页(page)，如下图所示：
任何时刻，虚拟页都可分为三个部分：
具体看上图：0和3未分配，1、4、6被缓存在物理内存linux 电子书，2、5、7被分配但未缓存在主存
2.1 DRAM缓存组织
和之前的 cache memory类似，将访问速度快的作为访问速度慢的缓存深入理解linux虚拟内存管理，利用DRAM比磁盘快一万倍，将磁盘数据尽量缓存在DRAM中（同样DRAM比SRAM慢10倍，也可将SRAM作为缓存），所以需尽可能从 DRAM中拿数据。为此需要：
2.2 页表
页表是一个元素为页表项(PTE, page table entry)的数组，页表项把虚拟页映射到物理页上。PTE由1个有效位和n个地址字段组成。在 DRAM 中，每个进程都有自己的页表，具体如下：
2.2.1 页命中
访问的虚拟地址的页在DRAM缓存中，则叫页命中，命中时由于在 DRAM 中有对应的数据，可直接访问。不命中时，由于DRAM中没有对应数据，所以需从磁盘复制到DRAM中，具体为：
2.2.2 处理页错误
在磁盘和内存之间传送页的活动叫交换或页面调度。页从磁盘换入（或页面调入）DRAM和从DRAM换出（或页面调出）磁盘。一直等待直到最后时刻，当不命中发生时才换入页面的策略叫按需页面调度，所有现代操作系统都使用按需页面调度方式。
2.2.3 完成页错误
页错误处理程序执行返回中断指令（iret）返回：
2.2.4 分配页
只有当出现 page fault 的时候才将数据拷贝到内存，即按需页面调度
2.2.5 局部性原理3 作为内存管理工具
每个进程都有自己的虚拟地址空间，这些地址空间可以看作是简单的线性空间（但实际上在物理内存中可能是间隔、分散的），映射函数通过物理内存分散地址，好的映射函数可提升局部性，具体的映射过程如图：
作为内存管理工具：
4 作为内存保护工具
任何现代计算机系统必须为操作系统提供手段控制对内存系统的访问，不应允许进程修改只读代码段，也不许读或修改任何内核中的代码和数据结构。不许读或改其他进程私有地址，不许改任何与其他进程共享的虚拟页面，除非所有共享者都显式允许这么做（通过调用明确的进程间通信系统调用）
使用权限位扩展PTEs，高位是表示权限的位，MMU 检查这些位进行权限控制（读、写、执行），如下图所示：
5 地址翻译5.1 地址翻译符号
地址空间可分为：
地址翻译：MAP: V → P U {}
开始之前先来了解以下参数：
虚拟地址(VA, Virtual Address)中的元素：
物理地址(PA, physical address)中的元素：
5.2 用页表进行地址翻译
具体的访问过程为：
通过虚拟地址找到页表(page table)中对应的条目检查有效位(valid bit)，是否需要触发页错误(page fault)根据页表中的物理页编号(physical page number)找到内存中对应地址把实际地址和虚拟页偏移(virtual page offset)拼接即为最终的物理地址
这里又分两种情况：Page Hit 和 Page Fault
5.2.1 page hit
处理器生成一个虚拟地址，并把它传给MMUMMU生成PTE地址，并从高速缓存/主存请求得到它高速缓存/主存向MMU返回PTEMMU构造物理地址并把它传送给高速缓存/内存高速缓存/内存返回所请求的数据字给处理器5.2.2 page fault
处理器生成一个虚拟地址，并把它传给MMUMMU生成PTE地址，并从高速缓存/主存请求得到它高速缓存/主存向MMU返回PTE有效位为零，所以MMU触发页故障异常，传递CPU控制到系统内核中缺页异常处理程序处理程序寻找被置换页(如果页脏，则将其换出到磁盘)处理程序从磁盘找到对应页并载入内存/缓存并更新内存中的PTE处理程序返回到原始进程，重启出错指令，CPU将引起缺页的虚拟地址重新发给MMU，由于已缓存在主存故会命中5.3 结合虚拟内存和高速缓存
在既有虚拟内存又有SRAM高速缓存的系统中，是使用虚拟地址还是物理地址访问SRAM高速缓存的讨论有很多，但大多数系统用物理寻址，这样多个进程共享虚拟页和存储的值，无需处理保护问题，因为访问权限的检查是地址翻译过程的一部分。虽然缓存已经很快了，但还能更快，主要思路是地址翻译发生在高速缓存查找之前，直接在 MMU和内存之间加上L1缓存，于是就有了另外一种设计，如图：
页表条目(PTE)像任何其他内存中的数据一样缓存在L1中，PTE可能被其他数据驱逐；PTE命中仍然需要一个小的L1延迟，解决办法是使用Translation Lookaside Buffer(TLB)。TLB可以认为是页表在处理芯片上的缓存，是MMU中的小型集关联硬件缓存，将虚拟页号映射到物理页号，大多数页表条目位于L1高速缓存，但被称为TLB的页表条目的片上高速缓存，包含少量页的完整页表条目，通常回消除访问L1上的页表条目的开销。MMU使用虚拟地址的VPN部分位访问TLB：
如图是TLB命中和不命中的两种情况：
若TLB不命中时，MMU必须从L1缓存中取出相应的PTE，新取出的PTE存放在TLB中可能覆盖已存在的条目（这里未画出L1缓存，下面Interl Core i7部分画出cpu中的L1缓存和MMU的TLB）
这里顺便复习下前面的缓存结构：
这里 VPN + VPO 就是虚拟地址，同样分成三部分，分别用于匹配标签、确定集合，若TLB命中，直接返回对应页表项(PTE)，否则，就要从缓存/内存中获取，并更新 TLB 的对应集合。幸好不命中很少发生
5.4 多级页表
因为虚拟地址的位数比物理内存的位数要大得多，所以保存页表项(PTE) 所需要的空间也是一个问题。例如：
假设每个页的大小是 4KB（2的12次方），每个地址有 48 位，一条 PTE 记录有 8 个字节，那么要全部保存下来，需要的大小是：
2^48×2^−12×2^3=2^39bytes = 512G
所以采用多层页表，第一层的页表中的条目指向第二层的页表，一个一个索引下去，最终寻找具体的物理地址，如图是二级页表：
K级页表翻译过程如下：
5.5 地址翻译实例
来看一个简单的例子，我们的内存系统设定如下：
简单内存系统的TLB的配置为：
简单内存系统页表：
简单内存系统缓存：
虚拟地址：0x03D4，在TLB中找到index为3的set，且其tag为3的PPN为0D，加上前面的虚拟地址的VPO即为最终的物理地址
得到物理地址，在缓存中找到idx为，tag为0D，且CO为0，则值为36
虚拟地址为0x0020，虽然TLB中去找到编号为0的set且tag为0的缓存，但为0，所以TLB Miss了，从页表中找到缓存PPN为2，则物理地址为0x0A20
接下来找到idx为8的缓存，但tag不匹配，故未命中缓存，只能重新读取
5.6 Intel Core i7内存系统
5.6.1 Intel Core i7 内存翻译
5.6.2 Core i7 1-3层页表项
5.6.3 Core i7 4级页表项
5.6.4 加速技巧
将1）MMU将地址翻译成物理地址2）将物理地址传送到L1高速缓存。这两步骤部分重叠，故也加速对L1高速缓存的访问。
6 Linux进程中的虚拟地址
Linux为每个进程维护单独的虚拟地址空间，包括内核虚拟内存和进程虚拟内存。前者某些区域被映射到所有进程共享的物理页面，如每个进程共享内核的代码和全局数据结构。有趣的是，Linux也将一组连续的虚拟页面（大小等于系统中DRAM的总量）映射到相应的一组连续的物理页面，为内核提供便利的方法访问物理内存中特定位置。
6.1 Linux将虚拟内存组织为“区域”集合
Linux将虚拟内存组织称一些区域（也叫段）的集合，区域就是已经存在着的（已分配的）虚拟内存的连续片，这些页以某种方式相关联。如代码段、数据段、堆、共享库段以及用户栈都市不同区域，每个存在的虚拟页都抱存在某个区域中，而不属于某个区域的虚拟页是不存在的，且不能被进程引用。区域的概念很重要，因为它允许虚拟地址空间有间隙，内核不用记录那些不存在的虚拟页，而这样的页也不占用内存、磁盘或内核本身中的任何资源。
6.2 Linux页异常处理
缺页异常步骤：
虚拟地址A是否和法：缺页处理程序搜索区域结构的链表，把A和每个区域结构中的vm_start和vm_end做比较，若该指令不合法，则缺页处理程序就出发一个段错误，从而终止该进程，对应下图中的1内存访问是否合法：进程是否有读、写或执行这个区域内页面的权限，如是不是因为运行在用户模式的进程试图从内核虚拟内存中读取字造成，若访问不合法则触发缺页异常，从而终止该进程，对应图中的2合法虚拟地址进行合法操作：按调度算法选择一个页，若该页被修改过，将其交换出去换入新页并更新页表。缺页处理程序返回时，CPU重新启动引起缺页的指令，该指令再次发A到MMU，这次就能正常翻译A
6.3 内存映射
将虚拟内存的areas与磁盘对象关联并初始化的机制叫内存映射。area可通过磁盘的普通文件（如可执行文件），初始化来自文件的一部分为页，或者匿名文件，首次错误将分配一个写满0的物理页，一旦页被写（脏）就跟其他页一样。无论哪种情况，一旦虚拟页面被初始化了，它就在由内核维护的专门的交换文件间换来换取，任何时刻，交换空间都限制着当前运行着的进程能分配的虚拟页面的总数。
6.3.1 共享对象
若虚拟内存系统可集成到传统的文件系统中，就能提供一种简单而高效的把程序和数据加载到内存中的方法。
很多进程都有同样的只读代码区域，且许多程序需访问只读运行时库代码的相同副本，如每个C程序都需标准C库的printf函数，若每个进程都在主存中保持这些代码的副本，就极端浪费。
一个对象可被映射到虚拟内存的一个区域，要么作为共享对象，要么作为私有对象（非共享）。
多个进程可共享相同的对象，虚拟地址可以有差异，但差异必须是页大小的倍数
6.3.2 私有的写时复制对象
对于每个映射私有对象的进程，相应私有区域的页表条目都被标记为只读，且该区域被标记为私有的写时复制。一旦写入则触发保护错误，处理程序在主存中创建试图写私有的写时复制区域中的一个页面该页面的信服本，更新页表条目指向该新副本，再恢复该页面可写权限。指令在处理程序返回时重新执行，拷贝尽可能被推迟。
再看fork函数，当被当前进程调用时，创建当前进程的mm_struct、区域结构和页表的原样副本。将两个进程中的每个页面都标记为只读，并将两进程中每个区域结构都标记为私有的写时复制。fork返回时，新进程虚拟内存和调用fork时存在的虚拟内存相同，当两进程中任一个后来进行写操作，写时复制机制就创建新页面，因此也就为每个进程保持私有地址空间的抽象概念。
再看execve假设执行execve("a.out",NULL,NULL)该函数在当前进程中加载并运行包含在可执行目标文件a.out中的程序，用a.out替代当前程序，需以下步骤：
6.3.3 找到可共享的页
内核相同页归并：
6.3.4 用户模式的内存映射
函数void *mmap(void *start, int len,int prot, int flags, int fd, int offset)，从文件描述副fd指定的文件偏移量offset，从start地址（可能为0）开始映射len字节，prot表示权限（PROT_READ、PROT_WRITE、 PROT_EXEC），flags表示映射权限（MAP_ANON、 MAP_PRIVATE、MAP_SHARED等），返回映射区域开始的指针（可能不是start）
6.3.5 mmap的使用
使用分页机制将大文件读入内存，共享数据结构，当调用带MAP_SHARED的标签时，多进程可访问相同内存区域，很危险。基于文件的数据结构例如数据库，将prot设置为PROT_READ和PROT_WRITE，当解除映射时，文件通过写入被更新，通过文件加载/更新/写回文件实现。
6.3.6 用mmap实现attack lab
当机器堆栈不能执行时，如何通过代码注入进行攻击，解决方法是使用mmap分配内存并标记为可执行，转移堆栈到该区域，执行攻击代码，恢复原来堆栈，移除映射区域。
7 动态内存分配
程序员通过动态内存分配器（如 malloc）让程序在运行时得到虚拟内存，因为程序经常直到实际运行时才知道某些数据结构大小。动态内存分配器管理一个虚拟内存区域，称为堆(heap)。
分配器以块为单位来维护堆，可分配或释放。有两种类型的分配器：
7.1 相关函数
先来看看一个简单的使用 malloc 和 free 的例子
#include
#include
void foo(int n) {
int i, *p;
/* Allocate a block of n ints */
p = (int *) malloc(n * sizeof(int));
if (p == NULL) {
perror("malloc");
exit(0);
}
/* Initialize allocated block */
for (i=0; i<n; i++)
p[i] = i;
/* Return allocated block to the heap */
free(p);
}为了讲述方便，我们做如下假设：
例如：
可以用任意的顺序发送 malloc 和 free 请求，但free 请求必须作用与已被分配的 block。
显式分配器的限制：
7.2 性能指标
假设给定 malloc 和 free 的请求的序列：
R0,R1,...,Rk,...,Rn−1R0,R1,...,Rk,...,Rn−1
目标是尽可能提高吞吐量以及内存利用率（注意，这两个目标常常是冲突的）
吞吐量是在单位时间内完成的请求数量。假设在 10 秒中之内进行了 5000 次 malloc 和 5000 次 free 调用，那么吞吐量是 1000 operations/second
另外一个目标是 Peak Memory Utilization，就是最大的内存利用率。其次最小化开销，定义总负载Pk表示请求Rk完成时的当前已分配的载荷之和，当前堆大小Hk（假定Hk是单调非递减），则K+1次请求的开销Ok = Hk / (maxi≤k P i ) – 1.0
7.3 内存碎片
影响内存利用率的主要因素就是『内存碎片』，分为内部碎片和外部碎片两种。
内部碎片
内部碎片指的是存储的数据(payload)小于块大小，就会因对齐和维护堆所需的数据结构或明确的决策（如返回大块满足小的请求）的缘故而出现无法利用的空间，例如：
内部碎片只依赖于之前的请求的具体模式
外部碎片
内存中有足够的空间，但是空间不连续，所以成为了碎片，取决于未来请求的模式
实现细节
如何实现高效的内存分配算法？在具体实现之前，需要考虑以下问题：
如何实现回收
标准方法：在块开头记录块的长度（包括块头），每个分配的块需额外的字节
具体这部分书中提到了四种方法：
隐式列表 Implicit List：在首部记录长度，链接所有块显式列表 Explicit List：用指针的空闲块的显式列表分离的空闲列表 Segregated Free List：不同大小的不同链表按大小对块排序 Blocks Sorted by Size：使用平衡树（如红黑树），每个空闲块都有指针，长度作为键8 跟踪自由块8.1 隐式空闲列表
每个块都记录大小和分配状态，只需一个字节，当块对齐时linux删除文件夹，一些低阶地址位总是0，与其存储始终为0的位，不如将其作为已分配/空闲标志。当读取Size字节时，必须屏蔽该位
8.1.1 数据结构
8.1.2 头访问
8.1.3 遍历链表
8.1.4 找到一个空闲块
如何确定哪部分空间合适，有三种方法：
First Fit: 每次都从头进行搜索，找到第一个合适的块，线性查找Next Fit: 每次从上次搜索结束的位置继续搜索，避免重复搜索没有帮助的块，速度较快，但可能会有更多碎片，一些研究表明碎片化教糟糕Best Fit: 每次遍历列表，找到剩余字节最少最合适的块，碎片较少，通常可提高内存利用率，但是速度最慢，仍是贪婪算法，没最优保证
8.1.5 分配空闲块
由于已分配空间可能小于空闲空间，可以分割块
8.1.6 释放块
最简单的实现方式是清除“已分配”的标记，但可能导致错误的碎片化
8.1.7 合并
若下一个/前一个块是空闲的，则连接合并
8.1.8 双向合并
在前面的基础上，在空闲块的“底部”记录块的大小，允许反向遍历列表，但需额外空间，边界标签（Knuth73）
8.1.9 通过footers实现
8.1.10 常数时间合并
总共四种情况，这里以第一种为例：
注意：对于头和尾需要加上"dummy footer"，标记为已分配，防止在释放第一块和最后一块时意外合并
8.1.11 高层malloc/free代码
malloc/free不常用，因为线性时间分配深入理解linux虚拟内存管理，多用于特殊目的应用
const size_t dsize = 2*sizeof(word_t);
void *mm_malloc(size_t size)
{
size_t asize = round_up(size + dsize, dsize);
block_t *block = find_fit(asize);
if (block == NULL)
return NULL;
size_t block_size = get_size(block);
write_header(block, block_size, true);
write_footer(block, block_size, true);
split_block(block, asize);
return header_to_payload(block);
}
void mm_free(void *bp)
{
block_t *block = payload_to_header(bp);
size_t size = get_size(block);
write_header(block, size, false);
write_footer(block, size, false);
coalesce_block(block);
}8.1.12 边界标签缺点
导致内部碎片，footer标签能被优化，未使用一位代表已分配/未分配，除次之外使用多一位表示前一块是否分配
也有四种情况，这里以第一种情况为例：
8.2 显式空闲列表
维护空闲列表块，而不是所有块，下一个/上一个空闲块可能在任何地方，所以需存储前向/后向指针，而不仅是块大小，合并仍需边界标签，根据记忆顺序找到相邻的块
8.2.1 释放块
在空闲列表的什么地方放新释放的块？
同样对于释放内存块也有4种情况，这里以第四种情况做简要说明：
8.2.2 一些实现的技巧建议
使用循环双向链表，但数据结构支持多种方法，要么保持自由指针固定要么作为搜索列表移动
8.2.3 显式空闲列表总结
分配是空闲块数量的线性时间，而不是所有块。由于需在列表中插入和取出块，因此分配和自由更复杂。但需要额外的链接空间
8.3 分割列表分配器
每个大小块类都有自己的空闲列表
8.3.1 分割分配器
给定一个自由列表数组，每个都是一定大小的类，分配一个大小为n的块，搜索大小为m>n的块，若找到合适的块，分割块并放碎片在适当的列表，若没有块被发现，尝试下个更大的种类。重复直到块被找到。用sbrk从系统请求额外的堆内存，从该新内存分配n个字节的块，将剩余的块作为一个单独的空闲块放在适当大小的类中。
8.3.2 分割分配器优点8.4 内存陷阱
关于内存的使用需要注意避免以下问题：
8.4.1 解引用错误指针
没有引用对应的地址，少了 &
int val;
...
scanf("%d", val);8.4.2 读取未初始化的内存
不能假设堆中的数据会自动初始化为 0，如：
/* return y = Ax */
int *matvec(int **A, int *x) {
int *y = malloc(N * sizeof(int));
int i, j;
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
y[i] += A[i][j] * x[j];
return y;
}8.4.3 覆盖内存
第一种是分配错误的大小，下面的例子中，一开始不能用 sizeof(int)，因为指针的长度不一定和 int 一样。
int **p;
p = malloc(N * sizeof(int));
for (i = 0; i < N; i++)
p[i] = malloc(M * sizeof(int));第二个问题是超出分配的空间，下面代码的 for 循环中，因为使用了
