虚拟内存

虚拟内存提供了三个重要的能力：

它将主存看成是个存储在磁盘上的地址空间的高速缓存，在主存中只保存活动区域，并根据需要在磁盘和主存之间来回传送数据，通过这种方式，它高效地使用了主存
它为每个进程提供了一致的地址空间，从而简化了内存管理。
它保护了每个进程的地址空间不被其他进程破坏

物理和虚拟内存

将虚拟地址转换为物理地址的任务叫做地址翻译 (address translation)。

地址翻译需要 CPU 硬件和操作系统之间的紧密合作 CPU 芯片上叫做内存管理单元(Memory Management Unit, MMU) 的专用硬件，利用存放在主存中的查询表来动态翻译虚拟地址，该表的内容由操作系统管理。

地址空间

地址空间 (address space) 个非负整数地址的有序集合：

一个地址空间的大小是由表示最大地址所需要的位数来描述的。

虚拟地址空间：

一个包含 N=2**n个地址的虚拟地址空间就叫做一个n位地址空间，现代系统通常支持 32 位或者 64 位虚拟地址空间。
物理地址空间：对应于系统中物理内存的M个字节。

虚拟内存作为缓存的工具

VM 系统通过将虚拟内存分割为称为虚拟页 (Virtual Page, VP) 的大小固定的块。物理内存被分割为物理页 (Physical Page, PP) （物理页也被称为页帧 (page frame ))

在任意时刻，虚拟页面的集合都分为三个不相交的子集：

未分配的： VM 系统还未分配（或者创建）的页，未分配的块没有任何数据和它们相关联，因此也就不占用任何磁盘空间。
已缓存的：当前已缓存在物理内存中的已分配页
未缓存的：未缓存在物理内存中的已分配页

DRAM 缓存的组织结构

使用术语 SRAM 缓存来表示位于 CPU 和主存之间的 L1、L2、L3 高速缓存，并且用术语 DRAM 缓存来表示虚拟内存系统的缓存，它在主存中缓存虚拟页

页表

和一个存放在物理内存中叫做页表 (page table)的数据结构，页表将虚拟页映射到物理页。每次地址翻译硬件将一个虚拟地址转换为物理地址时，都会读取页表。

操作系统负责维护页表的内容，以及在磁盘与 DRAM 之间来回传送页。因DRAM 缓存是全相联的，所以任意物理页都可以包含任意虚拟页。

页表就是一个页表条目 (Page Table Entry, PTE) 的数组。虚拟地址空间中的每个页在页表中一个固定偏移处都有一个 PTE。

每个PTE 是由一个有效位(valid bit) 和一个n 位地址字段组成的。有效位表明了该虚拟页当前是否被物理内存缓存在DRAM 中。

页命中

因为设置了有效位，那么地址翻译硬件就知道VP 2 是缓存在内存中的了。所以它使用PTE 中的物理内存地址（该地址指向pp 1 中缓存页的起始位置），构造出这个字的物理地址。

缺页

即DRAM缓存不命中，触个缺页异常。缺页异常调用内核中的缺页异常处理程序。选择一个牺牲页，然后将需要的页替换掉牺牲页

在磁盘和内存之间传送页的活动叫做交换 (swapping)或者页面调度 (paging) 。
当有不命中发生时，才换入页面的这种策略称为按需页面调度 (demand paging)。

又是局部性救了我们

局部性性原则保证了在任意时刻，程序将趋向于在一个较小的活动页面 (active page) 集合上工作，这个集合叫做工作集 (working set) 或者常驻集合(resident set) 。
如果工作集的大小超出了物理内存的大小，那么程序将产生一种不幸的状态，叫做抖动 (thrashing), 这时页面将不断地换进换出。
可以利用 Linux getrusage 函数监测缺页的数量（以及许多其他的信息）

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

操作系统为每个进程提供了一个独立的页表，因而也就是一个独立的虚拟地址空间。

简化链接

不同段在虚拟位置的位置是固定的。这样的一致性极大地简化了链接器的设计和实现，允许链接器生成完全链接的可执行文件，这些可执行文件是独立于物理内存中代码和数据的最终位置的。
简化加载

虚拟内存还使得容易向内存中加载可执行文件和共享对象文件。

Linux 加载器为代码和数据段分配虚拟页，把它们标记为无效的（即未被缓存的），将页表条目指向目标文件中适当的位置。加载器从不从磁盘到内存实际复制任何数据。在每个页初次被引用时，虚拟内存系统会按照需要自动地调入数据页。

将一组连续的虚拟页映射到任意一个文件中的任意位示法称作内存映射 (memory mapping) Linux 提供一个称为 mmap 的系统调用，允许应用程序自己做内存映射。

简化共享

独立地址空间为操作系统提供了一个管理用户进程和操作系统自身之间共享的一致机制。

简化内存分配

由于页表工作的方式，操作系统没有必要分配连续的物理内存页面。页面可以随机地分散在物理内存中。

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

SUP 位表示进程是否必须运行在内核（超级用户）模式下才能访问该页。

如果一条指令违反了这些许可条件，那么 CPU 就触发一个一般保护故障，将控制传递给一个内核中的异常处理程序。 Linux shell 一般将这种异常报告为＂段错误 (segmentation fault)"

地址翻译

//TODO

结合高速缓存和虚拟内存

大多数系统是选择物理寻址的。使用物理寻址，多个进程同时在高速缓存中有存储块和共享来自相同虚拟页面的块成为很简单的事情。而且，高速缓存无需处理保护问题，因为访问权限的检查是地址翻译过程的一部分。

利用TLB加速地址翻译

翻译后备缓冲器（Translation Lookaside Buffer，简称TLB）是一个用于改进虚拟内存系统性能的硬件缓存。在操作系统中，TLB用来减少处理器处理内存时地址转换的延迟。

当CPU接收到一个虚拟地址时，它首先在TLB中查找。如果找到了对应的物理地址，那么就可以直接使用，这被称为TLB命中（TLB Hit）。如果没有找到，即TLB未命中（TLB Miss），系统就必须查询内存中的页表，并将结果存入TLB中以便后续使用。

多级页表

采用多层次的页表，虚拟内存地址被分成多个部分，每一部分用于索引不同级别的页表。

综合：端到端的地址翻译

//TODO

内存映射

内存映射(memory mapping)：将一个虚拟内存区域与一个磁盘上的对象(object) 关联起来

一个区域可以映射到一个普通磁盘文件的连续部分。
一个区域也可以映射到一个匿名文件，匿名文件是由内核创建的，包含的全是二进制零。匿名文件可用于内存分配、进程间通信（IPC）、性能优化、用户空间分配器、操作系统内核、沙箱环境、虚拟化技术。

再看共享对象

对象可被映射为共享对象和私有对象。
即使共享对象被映射到了多个共享区域，物理内存中也只需要存放共享对象的一个副本。

写时复制（copy-on-write）

当多个进程将一个私有对象映射到内存时，如图a所示，该页表条目被标记为只读，区域结构被标记为写时复制，只要没有进程执行写操作，就保持图a的状态。
当进程试图写该私有对象时，触发保护故障，进入故障处理程序,返回后进入图b状态。
通过延迟私有对象中的副本直到最后可能的时刻，写时复制最充分地使用了稀有的物理内存。

再看fork函数

当fork 函数被当前进程调用时，内核为新进程创建各种数据结构，并分配给它一个唯一的PID 。为了给这个新进程创建虚拟内存，它创建了当前进程的mm_struct 、区域结构和页表的原样副本。它将两个进程中的每个页面都标记为只读，并将两个进程中的每个区域结构都标记为私有的写时复制。
当fork 在新进程中返回时，新进程现在的虚拟内存刚好和调用fork 时存在的虚拟内存相同。当这两个进程中的任一个后来进行写操作时，写时复制机制就会创建新页面，因此，也就为每个进程保持了私有地址空间的抽象概念。

再看execve函数

删除已存在的用户区域。删除当前进程虚拟地址的用户部分中的已存在的区域结构。
映射私有区域。为新程序的代码、数据、bss 和栈区域创建新的区域结构。所有这些新的区域都是私有的、写时复制的。代码和数据区域被映射为a.out 文件中的.text和.data 区。bss 区域是请求二进制零的，映射到匿名文件，其大小包含在a.out 中。栈和堆区域也是请求二进制零的，初始长度为零。但是栈内存不是通过匿名文件映射来实现的，而是直接由内核管理的。当使用brk()和sbrk()时，堆内存的扩展是通过改变进程的program break来实现的，这并不涉及匿名文件映射。当使用mmap()来分配内存时，可以映射到匿名文件（anonymous file），这种方式称为匿名内存映射。这种映射不与磁盘上的实际文件关联，而是直接映射到虚拟内存中的区域。
映射共享区域。如果a.out 程序与共享对象（或目标）链接，比如标准C 库libc.so, 那么这些对象都是动态链接到这个程序的，然后再映射到用户虚拟地址空间中的共享区域内。
设置程序计数器(PC) 。execve 做的最后一件事情就是设置当前进程上下文中的程序计数器，使之指向代码区域的入口点。下一次调度这个进程时，它将从这个入口点开始执行。Linux 将根据需要换入代码和数据页面。

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

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

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

PROT_EXEC: 这个区域内的页面由可以被CPU执行的指令组成。
PROT_READ: 这个区域内的页面可读。
PROT _WRITE: 这个区域内的页面可写。
PROT _NONE: 这个区域内的页面不能被访问。

动态内存分配

动态内存分配器维护着一个进程的虚拟内存区域，称为堆(heap)。
对于每个进程内核维护着一个brk变量指向堆顶
显式内存分配器：C的malloc和free，C++的new和delete。
隐式内存分配器：通过垃圾回收器回收，如java。

malloc和free函数

#include <stdlib.h>

/* 分配指定大小的内存块，并返回指向该内存块起始地址的指针。分配的内存块中的内容是未初始化的。 */
void *malloc(size_t size);

/* 分配指定数量的指定大小的内存块，并将其内容初始化为零。 */
void *calloc(size_t nmemb, size_t size);

/* 重新分配之前分配的内存块的大小，并返回指向新内存块的指针。如果新分配的大小比旧分配的大小大，那么新分配的内存块可能与旧内存块相同，否则，它可能是一个新的内存块。 */
void *realloc(void *ptr, size_t size);

/* 释放 分配的内存块。注意：在释放内存块后，指向该内存块的指针将不再有效，任何对该指针的后续访问都可能导致未定义的行为。 */
void free(void *ptr);

#include <unistd.h>

/* 增加程序的数据段的大小，即在堆上分配一定大小的内存空间。通常在内部由 malloc() 等函数调用。 */
void *sbrk(intptr_t incr);

为什么要使用动态内存分配

因为只有直到程序实际实际运行时才知道某些数据结构的大小

分配器的要求和目标

要求：

处理任意请求序列。
立即响应请求。分配器必须立即响应分配请求。
不允许分配器为了提高性能重新排列或者缓冲请求。只使用堆。
对齐块（对齐要求）。分配器必须对齐块，使得它们可以保存任何类型的数据对象。

目标:

最大化吞吐率。
最大化内存利用率。

碎片

内部碎片：分配块大小和它们的有效载荷大小之差的和。在任意时刻，内部碎片的数量只取决于以前请求的模式和分配器的实现方式。
外部碎片：外部碎片是当空闲内存合计起来足够满足一个分配请求，但是没有一个单独的空闲块足够大可以来处理这个请求时发生的。不仅取决于以前请求的模式和分配器的实现方式，还取决千将来请求的模式。

放置已分配的块

首次适配：这种策略会搜索内存的第一个足够大的空闲块来满足请求。首次适配简单且执行速度快，但可能会导致内存碎片。
下一次适配：下一次适配不会每次都从内存列表的开始处查找，而是从上次分配的位置继续查找。这可以减少内存碎片，但性能上可能不如首次适配。
最佳适配：最佳适配策略寻找最接近所需大小的空闲内存块。这种方法可以最小化内存碎片。但是，最佳适配可能需要更多的时间来搜索合适的空闲块，因为它必须检查所有的空闲块以找到最佳匹配。

获取额外内存

通过sbrk函数

合并空闲块

立即合并
推迟合并

带边界标记的合并

通过在每一个块尾部添加一个脚部来实现块的合并（会增大内存开销），可分为以下四种情况：

综合：实现一个简单的分配器

malloc lab

显式空闲列表

通过添加祖先和后继节点加快分配时空闲块的访问速度。

分离的空闲列表

将{1}，{2}，{4}…..{2^10}等不同大小的空闲块按照2的幂分类，每个类组成一个空闲链表

简单分离存储：不对空闲块进行分割合并。因此只需要succ指针，最小块为一个字。但是会造成很多内部碎片和外部碎片。
分离适配：GNU malloc包采用此方法，即找到合适块后，（可选地）分割它，将剩余部分插入其他适当空闲链表。释放一个块，执行合并，将结果放置到对应地空闲链表中。
伙伴系统：
- 每个块都有一个伙伴，伙伴的大小相同，位置相邻。如果一个块位于地址A，那么它的伙伴就位于地址A±块大小。这样，内存就被组织成了一个伙伴对的双向链表。
- 当需要分配内存时，系统会查找大小最接近所需大小的块。如果找到的块太大，就会被分裂成两个较小的块，每个块都是原块大小的一半。这个过程会一直重复，直到找到大小合适的块为止。
- 当释放内存时，系统会检查释放的块的伙伴是否也是空闲的。如果是，那么这两个伙伴块会被合并成一个更大的块，并放回到块链表中。这个过程可能会递归进行，如果更大的伙伴块也是空闲的，它们也会被合并。
- 优点是能快速搜索和快速合并，缺点是可能导致显著的内存碎片。