如果不对内存抽象，会面临两个问题。第一，用户程序可以很容易的破坏才做系统；第二，想要同时运行多个程序比较困难，需要对程序进行重定位。于是现代操作系统提出了一种对主存的抽象概念，叫做虚拟内存。
虚拟内存提供了三个重要的能力：
- 它将主存看成是一个存储在磁盘上的地址空间的高速缓存（地址空间即一套地址的集合）
- 它为每个进程提供了一致的地址空间，从而简化了内存管理
- 它保护了每个进程的地址空间不被进程破坏
1. 虚拟内存
1.1 页表
虚拟内存的基本思想是：每个进程拥有独立的地址空间，这个空间被分为大小相等的多个块，称为页(Page)。虚拟内存被组织为一个由存放在磁盘上的N个连续的字节大小的单元组成的数组。物理内存可以看做磁盘上虚拟内存的缓存，虚拟内存的页被映射到物理内存，在物理内存中对应的单元被称为页框，并不是所有的页都被放入主存中。为了建立从虚拟页到物理页之间的映射，我们需要一个名为页表的数据结构。
另外，操作系统为了提供手段来控制对内存系统的访问，在页表上增添了权限位。因为每次CPU生成一个地址时，地址反映硬件都会读一个页表项，因此很有效的实现了对内存访问的控制。
页面大小是操作系统可以选择的一个参数，页面过大或过小都不可以。
如果页面过大，会使得内部碎片过多（分配的页面没有被充分使用）；如果页表过小，页表项势必会增多，从磁盘到内存传输页表的时间必然会增多，另外这也会使得TLB的命中率降低。
1.2 地址翻译
页表提供了从虚拟页到物理页的映射关系，那么如何实现从虚拟地址到物理地址的转换呢？
实现地址翻译的是一个被被称为MMU的硬件单元，它接收CPU发出的虚拟地址指令，MMU通过计算得到页表项的地址，然后找到页表中的这个页表项，得到物理页号，将物理页号替代虚拟页号得到物理地址。
1.3 快表
在MMU中集成一个快表，含有少量表项。将一个虚拟地址放入MMU中进行转换时，硬件首先通过将该虚拟页号与TLB中所有表象进行匹配，判断页面是否在其中。如果在，则将页框取出而不必访问页表；否则，会进行正常的页表查询，接着从TLB中淘汰一个表项，然后用新找到的页表项代替它。
1.4 多级页表
考虑这样一个数字，对于一个32位的地址空间，4KB的页面大小和一个表项占4字节，则应该拥有2^32/2^12=2^20个表项，每个表项4字节，则该页表一共占有2^20*4=2^22=4MB，如果是64位系统则页表会更大。引入多级页表的原因是避免把全部页面一直保存在内存中。特别是那些从不需要的页表就不应该保留。
1.5 Linux中的虚拟内存
Linux的内存被划分为两大部分，其中一部分是被称为用户空间（图中的进程虚拟内存），另一部分被称为内核空间（内核虚拟内存）；用户空间在每个进程中都是不同的，而内核空间的代码，有一部分每个进程都是相同的，比如内核代码和数据以及物理内存（Linux将一组连续的虚拟页面映射到相应的一组连续的物理页面，内核可以访问物理内存中的任何特定的位置。）
内核为系统中的每个进程为何了一个单独的数据结构（task_struct），该数据结构中包含指向内核运行该进程所需要的所有信息（pid、程序计数器、可执行目标文件的名字等）
task_struct中的一个条目指向了mm_struct，它描述了虚拟内存的当前状态。其中pgd指向了页表的基址，当内核运行这个进程时，就将pgd存放在CR3控制寄存器中，而mmap则代表了虚拟内存空间中的每一个段
2. 页面置换算法
-
最佳（OPT）
所选择的被换出的页面将是最长时间内不再被访问，通常可以保证获得最低的缺页率。是一种理论上的算法，因为无法知道一个页面多长时间不再被访问。
举例：一个系统为某进程分配了三个物理块，并有如下页面引用序列：
7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1开始运行时，先将 7, 0, 1 三个页面装入内存。当进程要访问页面 2 时，产生缺页中断，会将页面 7 换出，因为页面 7 再次被访问的时间最长。
-
最近最久未使用（LRU）
虽然无法知道将来要使用的页面情况，但是可以知道过去使用页面的情况。LRU 将最近最久未使用的页面换出。
为了实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。
因为每次访问都需要更新链表，因此这种方式实现的 LRU 代价很高。
4，7，0，7，1，0，1，2，1，2，6
-
先进先出（FIFO）
选择换出的页面是最先进入的页面。
该算法会将那些经常被访问的页面也被换出，从而使缺页率升高。
3. 工作集与抖动
大部分进程对内存的访问都表现出局部性访问的行为。（空间局部：内存中被访问的页周围的页也很可能被访问；时间局部：最近被访问的页在不久的将来还会被访问）
一个进程当前正在使用的页面的集合称为它的工作集。如果整个工作集都被装入到内存中，那么就不会产生缺页。因此，如果内存太小无法容纳下整个工作集，便会导致大量的缺页，页面被频繁地换入和换出，使程序运行速度受到很大影响，我们称之为抖动。
导致抖动的原因除了上面提到的内存过小，加载的程序过多以外，还可能是不正确的页面置换算法导致的。
4. 分段
部分引用自cyc2018关于分段技术的总结
4.1 纯分段的实现
虚拟内存采用的是分页技术，也就是将地址空间划分成固定大小的页，每一页再与内存进行映射。
下图为一个编译器在编译过程中建立的多个表，有 4 个表是动态增长的，如果使用分页系统的一维地址空间，动态增长的特点会导致覆盖问题的出现。
分段的做法是把每个表分成段，一个段构成一个独立的地址空间。每个段的长度可以不同，并且可以动态增长。
4.2 段页式
程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。
在MULTICS系统中，一个地址由两部分构成：段和段内地址。段内地址又进一步分为页和页内的字。在进行内存访问时，执行下面的算法：
- 根据段号知道段描述符
- 检查该段的页表是否在内存中，如果在，则知道它的位置，如果不在，则产生一个段错误
- 检查所请求虚拟页面的页表项，如果该页面不在内存中则产生一个缺页中断，如果在内存就从页表项中取出这个页面在内存中的起始地址
- 把偏移量加到页面的起始地址上，得到要访问的字在内存中的地址
- 最后进行读或写操作
4.3 分段与分页的比较
- 对程序员的透明性：分页透明，但是分段需要程序员显式划分每个段。
- 地址空间的维度：分页是一维地址空间，分段是二维的。
- 大小是否可以改变：页的大小不可变，段的大小可以动态改变。
- 出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。
5. 内存映射
Linux通过将一个虚拟内存区域与一个磁盘上的对象关联起来，以初始化这个虚拟内存区域的内容（此时并没有在物理内存上分配，当你访问这段空间，CPU陷入OS内核执行异常处理，然后异常处理会在这个时间分配物理内存，并用文件的内容填充这片内存），这个过程称为内存映射。一个对象可以被映射到虚拟内存的一个区域，要么作为共享对象，要么作为私有对象。
更简单的说，mmap只是把fd映射到虚拟地址上，然后你可以像访问内存一样访问这个fd的资源。具体fd可以是很多东西，比如文件。关于何时在物理内存上分配内存，则是由缺页中断实现。
5.1 共享对象的映射
如果将一个进程将一个共享对象映射到它的虚拟地址空间的一个区域内，那么这个进程对这个区域的任何写操作，对于那些也把这个共享对象映射到它们虚拟内存的其他进程而言，也是可见的。
假设进程1将一个共享对象映射到自己的虚拟内存的一个区域中，此时进程2将同一个共享对象映射到它的地址空间中，因为每个对象都有一个唯一的文件名，内核可以迅速地判断进程1已经映射了这个对象，因而可以使进程2中的页表条目指向相应的物理页面。
5.2 私有对象的映射
对于一个映射到私有对象的区域做的改变，对于其他进程来说是不可见的，并且进程对这个区域所做的任何操作都不会反映到磁盘上的对象中。私有对象使用一种叫做写实复制的巧妙技术被映射到虚拟内存中。一个私有对象开始生命周期的方式基本与共享对象一样，在物理内存中只保存私有对象的一份副本。但是对于每一个映射私有对象的进程，相应私有区域的页表条目都被标记为只读，只要没有进程试图写它私有区域，他们就可以继续共享物理内存中对象的一个单独副本。然而，当有进程试图写私有区域内的某个页面时，这个写操作就会触发一个保护故障，它会在物理内存中创建这个页面的一个新副本，更新页表条目指向这个新的副本，然后恢复写权限。
5.3 再看fork函数
当fork函数被当前进程调用时，内核为新进程创建各种数据结构，并分配给它一个唯一的pid。为了给新的进程创建虚拟内存，它创建了当前进程的mm_struct、区域结构和页表的原样副本。它将两个进程中的每个页面都标记为只读，并将两个进程中的每个区域结构都标记为私有的写时复制。
5.4 再看execve函数
在当前进程中的程序执行了如下execve调用：
execve("a.out",NULL,NULL);
会有以下几个步骤：
- 删除已存在的用户区域：删除当前进程虚拟地址的用户部分中的已存在的区域结构（个人理解mm结构？）
- 映射私有区域：为新程序的代码、数据、bss和栈区域创建新的区域结构。所有这些新的区域都是私有的、写时复制的。
- 映射共享区域
- 设置程序计数器：execve做的最后一件事情就是设置当前进程上下文中的程序计数器，使之指向代码区域的入口点
