地址重定位
为了保证 CPU 执行命令时可以正确的访问内存单元，需要将用户程序中的逻辑地址转换为运行时可以供机器直接寻址的物理地址，这一过程被成为地址重定位（又称地址转换、地址变换、地址翻译、地址映射）。
- 逻辑地址（相对地址、虚拟地址）：用户程序经过编译、汇编后形成的目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余地址都相对于首地址而编址。逻辑地址不能用来读取内存中的信息。
- 物理地址（绝对地址、实地址）：内存中存储单元的地址。物理地址可以直接寻址。
地址重定位可以分为静态重定位和动态重定位：
- 静态重定位：当用户程序加载到内存时，一次性实现逻辑地址到物理地址的转换，一般通过软件来实现。
- 动态重定位：在进程执行的过程中进行地址的转换，即逐条指令执行的时候完成转换，一般通过硬件部件（重定位寄存器）支持。
物理内存的管理
空闲内存的划分方法有两种：
- 等长划分：使用位图的数据结构进行存储，每一个分配单元对应于位图中的一位，0 表示空闲，1 表示占用；
- 不等长划分：使用空闲区表、已分配区表或者空闲块链表的方式存储，空闲区表和已分配区表的结构相同，表中的每一项记录了空闲区/已分配区的起始地址、长度、标志。空闲块链表则是将表项使用链表的方式串接起来。
内存分配的算法
- 首次分配（first fit）：在空闲表中找到找到第一个满足进程要求的空闲区；
- 下次适配（next fit）：从上次找到的空闲区接着寻找第一个满足进程要求的空闲区；
- 最佳适配（best fit）：查找整个空闲区表，找到能够满足进程要求的最小空闲区；
- 最差适配（worst fit）：总是分配满足进程要求的最大空闲区，将最大的空闲区分为两个部分，一部分提供给进程使用，另一部分形成新的空闲区；
伙伴系统
伙伴系统是一种经典的内存分配方案，是 Linux 底层内存管理采用的方案，也是一种特别的“分离适配”算法。
将内存按照 2 的幂进行划分，组成若干空闲块链表；查找该链表找到能满足进程要求的最佳匹配块。
算法过程：
- 首先将整个可以用的内存空间看作一整块：$2^U$；
- 假设当前进程需要的内存空间大小为 S，如果满足 $2^{U-1}<S\le2^U$，则分配整个块；否则，将内存块划分为两个大小相等的伙伴，大小为$2^U-1$；
- 一直划分直到产生了大于或等于 S 的最小块；
基本内存管理方案 1
单一连续区
内存分为了系统区和用户区，系统区仅仅给操作系统使用，在系统区之外的空间就是给用户提供的用户区。一段时间内只有一个进程在内存中，简单但是内存的利用率较低。
固定分区
把内存空间分为若干份，称为分区，每个分区的大小可以相同也可以不同，但是分区的大小是固定不变的，每个分区只能放入一个进程。
这种方式有两个缺点：一是如果进程太大，无法装入；二是内存使用的效率低，产生内部碎片严重。
可变分区
这种方法在进程进入到内存中时，根据进程的大小动态建立相同大小的内存分区，分配给进程，同时剩余的空间成为新的空闲空间。
可变分区不会产生内部碎片，但是容易产生外部碎片。外部碎片是很小的、不易利用的空闲区，会导致内存的利用率下降。
可以通过紧缩技术，在内存中移动程序，将所有小的空闲区合并为较大的空闲区处理外部碎片。但是紧缩技术需要考虑系统的开销和程序移动的时机两个问题。
基本内存管理方案 2
一个进程进入内存中若干不连续的区域
页式存储管理方案
- 页（page）：又名页面，用户进程地址空间中被划分为等长的部分，从 0 开始编号。
- 页框（page frame）：内存空间中按照同样大小划分的等长部分，从 0 开始编号。
典型的页面尺寸：4K 或 4M
内存分配规则：以页为单位进行分配，并按进程需要的页数来分配；逻辑上相邻的页，物理上不一定相邻。
页表
页表项记录了逻辑页号和页框号的对应关系，每个进程一个页表，存放在内存。
地址转换
CPU 取到逻辑地址，自动划分为页号和页内地址；用页号查页表，得到页框号，再与页内偏移拼接成为物理地址。
如果进程的最后一条指令只占用了最后一页的很小内存空间，会导致内碎片问题。
段式存储管理方案
将用户进程地址空间按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段号。内存空间被动态划分为若干长度不相同的区域， 称为物理段，每个物理段由起始地址和长度确定。
内存分配规则：以段为单位进行分配，每段在内存中占据连续空间，但各段之间可以不相邻。
段表
段表每一项记录了段号、段首地址和段长度之间的关系，每个进程一个段表，存放在内存。
地址转换
CPU 取到逻辑地址，自动划分为段号和段内地址；用段号查段表，得到该段在内存的起始地址，与段内偏移地址计算出物理地址。
段页式存储管理方案
将用户进程地址空间先按段进行划分，每一段再按页面进行划分，每个程序段都有一个段号，一个段号包含了多个页号。内存划分和页式存储管理方案相同。
内存分配规则：以页为单位进行分配。
段页式的存储表
段表记录了每一段的页起始地址和页表长度，页表记录了逻辑页号和页框号的对应关系。每一个段有一张页表，一个进程有多个页表。
地址转换
CPU 先用段号得到对应的段内地址，分为页号和页内地址。然后用页号查询页表得到页框号，最后和页内地址拼接成最后的地址。
覆盖技术
把一个程序划分为一系列功能相对独立的程序段，让执行时不要求同时装入内存的程序段组成一组（称为覆盖段），共享同一块内存区域 ，这种内存扩充技术就是覆盖技术。
程序段先保存在磁盘上，当有关程序段的前一部分执行结束，把后续程序段调入内存，覆盖前面的程序段。
一般要求作业各模块之间有明确的调用结构，程序员要向系统指明覆盖结构，然后由操作系统完成自动覆盖。
交换技术
内存空间紧张时，系统将内存中某些进程暂时移到外存，把外存中某些进程换进内存，占据前者所占用的区域（进程在内存与磁盘之间的动态调度）。
交换区
一般系统会指定一块特殊的磁盘区域作为交换空间，包含连续的磁道，操作系统可以使用底层的磁盘读写操作对其高效访问
交换时机
当进程不再使用或者很少使用的时候，或者内存存在空间不足的可能时，就需要发生交换。需要和调度器结合使用。
考虑进程的各种属性，不应该交换正在处于 I/O 状态的进程。
虚拟存储技术
所谓虚拟存储技术是指：当进程运行时，先将其一部分装入内存，另一部分暂留在磁盘，当要执行的指令或访问的数据不在内存时，由操作系统自动完成将它们从磁盘调入内存的工作。
- 虚拟地址空间：分配给进程的虚拟内存
- 虚拟地址：在虚拟内存中指令或数据的位置， 该位置可以被访问，仿佛它是内存的一部分
- 虚拟内存：把内存与磁盘有机地结合起来使用，从而得到一个容量很大的“内存”
存储保护
- 确保每个进程都有独立的地址空间；
- 确保进程访问合法的地址范围；
- 确保进程的操作是合法的；
虚拟页式存储管理系统
虚拟页式即将虚拟存储技术和页式存储管理方案结合起来，以CPU时间和磁盘空间换取昂贵内存空间。具体分为请求调页和预先调页。
基本思想：进程开始运行之前，不是装入全部页面， 而是装入一个或零个页面，之后，根据进程运行的需要，动态装入其他页面。当内存空间已满，而又需要装入新的页面时，则根据某种算法置换内存中的某个页面，以便装入新的页面。
页表表项设计
- 页框号：内存块号、物理页面号、页帧号；
- 有效位（驻留位、中断位）：表示该页是在内存中还是在磁盘中，通常使用0或1表示；
- 访问位：页框中的内容在内存中被访问过；
- 修改位：此页在内存中是否被修改过；
- 保护位：读或可读写；
二级页表结构及地址映射
页表页在内存中若不连续存放，则需要引入页表页的地址索引表—页目录。不管是页目录还是页表，都存放在一个页面中。
为什么要使用多级页表
假设一个页面的大小为 4KB，一个页表项的大小为 4B，那么一个页面中可以存放 1K 个页表项。所以顶级页表虽然只有一个页面但是可以存放 1K 个页表项，其中每一个页表项对应的是下一级的 1K 个页表项。所以可以存放的最大空间是 1K1K *4KB = 4GB 内存。
4GB 的虚拟地址，如果使用一级页表，那么需要 1M个 页表项，总大小为 4MB，用页面来存放就需要 1K个连续的页面空间；如果使用二级页表，就不需要页面空间连续，但是需要 1K 个页表项，总大小为4KB，刚好放入到一个页面中。每次寻址时，先通过一级页表（4KB）找到二级页表位置，然后可能使用若干二级页表（n4KB），页表的总消耗为 4KB+n4KB，这样子就避免每次都加载 4MB 大小的页表。
系统分配给每个进程的虚拟地址都是 4G，那么采用一级页表需要 4G／4K = 2^20 个表项，如果每个页表项是 4B，那么需要 4MB 的内存空间。但是大多数程序根本用不到 4G 的虚拟内存空间，比如 hello world程序，这样一个几 kb 的程序却需要 4MB 的内存空间是很浪费的。如果采用二级页表，那么一级页表只需要 4KB 的空间用来索引二级页表的地址，像 hello world 这样的程序可能只需要一个物理页，也就是4KB，所以这样只需要 8KB 就能解决问题。
反转（倒排）页表
地址转换：从虚拟地址空间出发：虚拟地址->查页表->得到页框号->形成物理地址，每个进程一张页表。
- 从物理地址空间出发，系统建立一张页表；
- 页表项记录进程i的某虚拟地址（虚页号）与页框号的映射关系；
- 将虚拟地址的页号部分映射到一个散列值；
- 散列值指向一个反转页表；
- 反转页表大小与实际内存成固定比例，与进程数量无关；
MMU：内存管理单元
内存管理单元管理着地址空间和物理内存的转换，其中的页表（Page table）存储着页（程序地址空间）和页框（物理内存空间）的映射表。
一个虚拟地址分成两个部分，一部分存储页面号，一部分存储偏移量。
以一级页表为例，其中存放着 16 个页，这 16 个页需要用 4 个比特位来进行索引定位。例如对于虚拟地址0010 000000000100，前 4 位是存储页面号 2，读取表项内容为110 1，页表项最后一位表示是否存在于内存中，1 表示存在。后 12 位存储偏移量。这个页对应的页框的地址为110 000000000100。
TLB：快表
TLB：Translation Lookaside Buffer
页表一般都很大，并且存放在内存中，所以处理器引入 MMU 后，读取指令、数据需要访问两次内存：首先通过查询页表得到物理地址，然后访问该物理地址读取指令、数据。由于 CPU 的指令处理速度与内存指令的访问速度差异大，CPU 的速度得不到充分利用，为了减少因为 MMU 导致的处理器性能下降，引入了 TLB。
TLB 转换检测缓冲区相当于页表的缓存，利用程序访问的局部性原理改进虚拟地址到物理地址的转换速度。TLB 保存正在运行进程的页表的子集(部分页表项)，只有在 TLB 无法完成地址转换任务时，才会到内存中查询页表，这样就减少了页表查询导致的处理器性能下降。
缺页异常
缺页异常是一种页错误（Page Fault）
在地址映射过程中，硬件检查页表时发现所要访问的页面不在内存，则产生缺页异常，操作系统执行缺页异常处理程序：获得磁盘地址，启动磁盘，将该页调入内存。此时分为两种情况：
- 如果内存中有空闲页框，则分配一个页框， 将新调入页装入，并修改页表中相应页表项的有效位及相应的页框号。
- 若内存中没有空闲页框，则要置换内存中某一页框；若该页框内容被修改过，则要将其写回磁盘。
软件策略
驻留集
驻留集通常指操作系统给进程分配多少的页框，分配的策略主要有固定分配策略和可变分配策略两种。
固定分配策略指在进程创建时确认页框的数量，可以根据进程类型（交互、批处理、应用类）或者基于程序员或系统管理员的需要来确认。可变分配策略是通过缺页率评估进程的局部性表现，缺页率高时增加分配的页框数，缺页率低时减少分配的页框数。可变分配策略可能会带来额外的系统开销。
置换范围
- 局部置换：仅在产生本次缺页的进程的驻留集中选择置换页。
- 全局置换：将内存中的所有未锁定的页框都作为置换的候选。
分页守护进程
清除是指从进程的驻留集中收回页框。一个虚拟页式系统工作的最佳状态是发生缺页异常时，系统中有大量的空闲页框。在系统中保存一定数目的空闲页框供给比使用所有内存并在需要时搜索一个页框有更好的性能。
Linux 系统中设计了一个分页守护进程（paging daemon），该进程多数时间处于休眠，可以定期唤醒以检查内存的状态。如果空闲的页框过少，分页守护进程通过预定的页面置换算法选择页面交换出内存。如果页面装入内存后被修改过，则将它们写入磁盘，保证所有的空闲页框都是“干净”的。
页面缓冲技术
当一个进程需要使用一个已置换出的页框时，如果该页框还没有被新的内容覆盖，将它从空闲页框集合中移出就可以恢复该页面。
页面缓冲技术不丢弃置换出的页，而是将它们放入两个表之一：如果未被修改，则放到空闲页链表中，如果修改了，则放到修改页链表中。被修改的页定期写回磁盘。每次写入多个页面可以大大减少 I/O 操作的数量，从而减少了磁盘访问时间。被置换的页仍然保留在内存中，一旦进程又要访问该页，可以迅速将它加入该进程的驻留集中（代价很小）。
页面置换算法
OPT：最佳页面置换算法
置换以后不再需要的或者最远的将来才会用到的页面。
OPT 是一种理论上的算法，因为无法直到一个页面多长时间不再被访问，所以它作为一个标准来衡量其他算法的性能。
FIFO：先进先出算法
选择在内存中驻留时间最长的页并置换它。
该算法会让经常被访问的页面被还出，从而使缺页率升高。
SCR：第二次机会算法
SCR：Second Chance
当页面被访问 (读或写) 时设置该页面的 R 位为 1。需要替换的时候，检查最老页面的 R 位。如果 R 位是0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是 1，就将 R 位清 0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续从链表的头部开始搜索。
第二次机会算法是对 FIFO 算法的改进，不会将经常使用的页面置换出去。
CLOCK：时钟算法
第二次机会算法需要在链表中不断移动页面，开销很大并且效率很低。时钟算法使用环形链表将页面连接起来，再使用一个指针指向最老的页面。
NRU：最近未使用算法
NRU：Not Recently Used
选择在最近一段时间内未使用过的一页并置换。
每个页面都有两个状态位：R 与 M，当页面被访问时设置页面的 R=1，当页面被修改时设置 M=1。其中 R 位会定时被清零。可以将页面分成以下四类：
- R=0，M=0
- R=0，M=1
- R=1，M=0
- R=1，M=1
当发生缺页中断时，NRU 算法随机地从类编号最小的非空类中挑选一个页面将它换出。
NRU 算法优先换出已经被修改的脏页面（R=0，M=1），而不是被频繁使用的干净页面（R=1，M=0）。
LRU：最近最久未使用算法
LRU：Least Recently Used
为了充分实现 LRU，需要在内存中维护一个包含所有页面的链表。最近使用的页面在前面，最久未使用的页面排在最后。该算法实现的困难在每次内存引用都必须更新链表：每当一个页面被访问时，就需要把这个页面移到链表表头。
LRU 的性能接近 OPT，但因为每次访问都需要更新链表，因此这种方式实现的 LRU 代价很高。
LRU 一种硬件实现是通过矩阵，矩阵大小随着页面数量增加而增大，所以当页面数量很大时很难实现。
NFU：最不经常使用算法
该算法选择访问次数最少的页面置换。
因为 LRU 算法的实现比较麻烦而且开销很大，所以提出了用软件来模拟 LRU 算法的NFU算法：为每一页设置一个软件计数器，初值为0，每次时钟中断的时候就将计数器加R，发生缺页中断时选择计数器值最小的一页置换。
AGING：老化算法
在 NFU 算法中存在一个问题：在第一次时钟中断的时候其中一页可能被访问了很多次，之后再未被访问过，然而在以后的时钟中断这一页计数器的值仍然高于其它页，因此其虽然长时间未被访问也不会被置换出去。
为了更好地模拟 LRU 算法，老化算法对 NFU 进行了改进，计数器在加 R 前先右移一位，R 位加到计数器的最左端。
工作集算法
基本思想：根据程序的局部性原理，一般情况下，进程在一段时间内总是能集中访问一些页面，这些页面称为活跃页面，如果分配给一个进程的物理页面数太少了，使该进程所需的活跃页面不能全部装入内存，则进程在运行过程中将频繁发生中断。如果能为进程提供与活跃页面数相等的物理页框数，则可以减少缺页中断次数。
工作集 W(t, Δ) = 该进程在过去的 Δ 个虚拟时间单位中访问到的页面的集合。
工作集算法就是找出一个不在工作集中的页面并置换它。具体过程为：
- 扫描所有的页表项，如果一个页面的 R 位是 1，则将该页面的最后一次访问时间设为当前时间，并将 R 位清零；
- 如果一个页面的 R 位是 0，则检查该页面的访问时间是否在“当前时间 - T”之前：
- 如果是，则该页面为被置换的页面；
- 如果不是，记录当前所有被扫描过页面的最后访问时间里的最小值，扫描笑一个页面并重复上述过程。