物理内存和虚拟内存
通常所说的物理内存就是计算机内存条上的实际内存容量，是实体的内存大小。计算机主存被组织成由M个连续的字节大小的单元组成的数组。每个字节有唯一的物理地址。CPU访问内存最自然的方式就是直接使用物理地址进行物理寻址。
虚拟内存是操作系统为作为内存使用的一部分磁盘空间，虚拟内存在磁盘上实际上就是一个硕大无比的文件，其不是实体存在的（为了满足物理内存的不足而提出的策略）。现在的操作系统大多数使用虚拟寻址来访问主存。大体过程就是CPU生成一个虚拟地址，虚拟地址在被送到内存之前会转换成适当的物理地址（地址翻译）。通过虚拟地址再进行物理寻址。
地址空间是由表示最大地址所需要的位数来描述的。如一个包含N=2^n个地址的地址空间就叫做一个n位的地址空间。
虚拟内存作为缓存工具
如之前所说，虚拟内存概念上就是存放在磁盘上的N个连续的字节大小的单元组成的数组。每个字节都有一个索引，称为虚拟地址。这个数组的部分内容会缓存在主存中(DRAM)。VM系统会将虚拟内存分成虚拟页，每个虚拟页的大小为P=2^p，类似的也有物理页（页帧）。
虚拟页可分成三种：
- 未分配的：VM系统还没有分配的页，就是还没有在磁盘上生成的，因此不占用任何磁盘空间。
- 缓存的：已经在物理内存中缓存的页。
- 未缓存的：没有缓存在物理内存中的页，就是虽然在磁盘上存在但是没有缓存到DRAM中。
虚拟页0和3没有分配，因此在磁盘上不存在，虚拟页1，4，6缓存在物理内存中，页2，5，7虽然被分配了（磁盘上已经有）但是没有缓存在主存中。
DRAM缓存的组织结构
使用SRAM表示位于CPU和主存之间的高速缓存，使用DRAM表示虚拟内存系统的缓存，就是在主存中缓存虚拟页。DRAM比SRAM慢大约10倍，磁盘比DRAM慢100000多倍。因此我们尽量从DRAM中取数据，因此需要做到以下：
- 更大的页尺寸：通常是4KB，有时可以达到4MB
- 全相联：每一个虚拟页可以放在任意的物理页中，没有限制。
页表
当有了虚拟内存后，我们需要知道虚拟页和物理页之间的映射关系，即虚拟页位于哪个物理页中，这就需要用到页表。在物理内存中有一个叫页表的数据结构，页表可以将虚拟页映射到物理页。页表就是一个页表条目（PTE）的数组，每个PTE是由一个有效位和一个n位地址字段组成。每次地址翻译硬件将一个虚拟地址转换成物理地址时，都会读取页表，操作系统负责维护页表的内容，以及在磁盘和DRAM之间来回传送页。页表结构如下所示：
虚拟页VP1,VP2,VP4和VP7被缓存在DRAM中，VP0和VP5未分配，VP3和VP6已分配但是未缓存。因为DRAM缓存是全相联的，因此任意物理页都可以包含任意虚拟页。
缺页
DRAM缓存不命中称为缺页，就是在DRAM中还没有缓存对应的虚拟页。这时会触发缺页异常，调用缺页异常处理程序，程序会在DRAM中选择一个牺牲页，将改牺牲页替换，并修改相应的页表条目。添加所缺页后会返回到导致缺页的指令，这时缺页已经在主存中了，便可以正常执行读取操作。下图以VP3缺页异常为例，VP4作为牺牲页。
虚拟内存作为内存管理工具
操作系统为每一个进程提供一个独立的页表，就是一个独立的虚拟地址空间。如下所示，进程i的页表将VP1映射到PP2,VP2映射到PP7。进程j的页表将VP1映射到PP7,VP2映射到PP10。多个虚拟页可以映射到同一个共享的物理页上。
除此之外，虚拟内存可以简化链接，简化加载，简化共享，简化内存分配。
虚拟内存作为内存保护的工具
计算机系统提供手段来控制对内存系统的访问权限，如用户进程，内核进程的访问权限，这些是通过虚拟内存实现的。在PTE上添加额外的控制位可以保护内存访问。如下所示，通过看许可位是否允许相应的访问来保护内存。
地址翻译
地址翻译就是虚拟地址空间中的元素和物理地址空间元素之间的映射。MMU利用页表可以实现这种映射。映射过程如下：
当发生页面命中时：
- CPU生成一个虚拟地址，并把它从传送给MMU
- MMU生成PTE地址，并从高速缓存/主存请求得到它
- 高速缓存/主存向MMU返回PTE
- MMU构造物理地址，并把它传送给高速缓存/主存
- 高速缓存/主存返回请求的数据字给CPU
当发生缺页时：
- 1-3步和命中时的1-3步相同
- PTE的有效位是0，触发异常，执行缺页异常处理程序
- 缺页处理确定在物理内存中的牺牲页，若该牺牲页已被修改，把其换出到磁盘
- 调入新的页面，更新内存中的PTE
- 返回到原来的进程，再次执行导致缺页的指令，这时即可正常读取。
TLB加速地址翻译
每次CPU产生一个虚拟地址，MMU必须查阅一个PTE（主存中），这会浪费时间。如果PTE正好缓存在L1中，就会快很多。因此可以在MMU中包括一个关于PTE的小缓存，这样就不用每次再读取PTE了，直接从MMU中获取即可，这个缓存称为缓存后备缓冲器（TLB）。其结构如下：
这样在地址翻译时，过程就会发生在芯片上的MMU中，速度会很快。
和PTE命中不同的就是在翻译的位置不同。
当虚拟内存位数过大时，保存虚拟页的页表就是一个大问题，为了解决这个问题，使用多级页表，这里就不过多解释。
动态内存分配
动态内存分配器维护着一个进程的虚拟内存区，称为堆。分配器把堆看作不同大小的块的集合来维护。每个块是一个连续的虚拟内存块，包括已分配的和空闲的。分配器有两种：
- 显式分配器：显式的分配和回收块。（malloc和free，new和delete）。
- 隐式分配器：只负责分配，自动回收。隐式分配器也称为垃圾收集器。
malloc和free函数
这里看下malloc和free是如何管理堆的。每个方框代表4字节的字，有阴影的是分配块，没阴影的是空闲块，双字对齐。
使用动态内存分配的原因是到程序运行时才知道这些内存的大小。其内存分配不是在编译期，而是在内存期。
分配器的要求和目标
要求：
- 处理任意请求序列
- 立即响应请求
- 只使用堆
- 对齐块
- 不修改已分配的块
目标：
- 最大化吞吐率
- 最大化内存使用率
碎片
内部碎片：已分配块大于有效载荷时发生，如内存对齐需要增加块来满足。
外部碎片：空闲内存合计起来足够满足一个分配请求，但是单个小空闲内存不满足。
实际的内存分配器需要解决的问题：
- 如何记录空闲块？
- 如何选择空闲块来放置新分配的块？
- 分配完块后，如何处理空闲块的剩余部分？
- 如何处理释放的块？
隐式空闲链表
一个简单的堆块的结构如上所示，假设有一个已分配的块，大小为24（0x18）字节，那么头部是0x18|0x1=0x19，一个40（0x28)字节的空闲块,其头部是0x28|0x0=0x28。填充部分是为了满足某些要求，如内存对齐。
隐式空闲链表如下所示:
放置已分配块
查找合适的分配位置时有三种方法：
- 首次适配：每次都从头进行搜索，找到第一个合适的块，优点是将大的空闲块留在链表后面，缺点是在链表开始处留下碎片，搜索时间长。
- 下一次适配：每次从上次搜索结束的位置继续搜索，速度较快，但可能会有更多碎片，内存利用率更加低。
- 最佳适配：检查每个空闲块，找到最合适的块，碎片较少，但是速度最慢。
分割空闲块
获取额外堆内存： 当分配器找不到合适的空闲块时，会合并相邻的空闲块，如果还是不够，会向内存申请额外的堆内存，将内存转化成空闲块并插入到空闲链表中，最后将请求的块放到这个空闲块中。
合并空闲块
当分配器释放一个分配块时，可能有其他空闲块与刚释放的块相邻，这样会产生假碎片。就是许多可用的空闲块被切割成小的无法使用的空闲块。这时我们需要将它们合并。
- 立即合并：在每次块被释放时，就立即合并相邻块。
- 推迟合并：等到某个稍晚的时候再合并空闲块。
为了能够合并前面的空闲块，在堆块增加一个标记。这样就能知道前面块的位置和状态。
垃圾收集
当申请的内存不使用时，需要回收。垃圾收集器是一种动态内存分配器，它自动释放程序不再需要的已分配块。在支持垃圾回收的系统中，应用显示分配堆块，但是不需要显示回收。
垃圾收集器的基本知识
垃圾回收器可以将内存看作一张有向可达图。如下所示：
当存在从根节点到达点p的有向路径时，就说p是可达的，不可达的节点对应为垃圾，垃圾回收器会释放这些不可达点将它们返回空闲链表，定期回收它们。