Overview
为什么需要内存管理？
没有内存管理，面向物理地址编程非常不安全，并且难以实现多个程序同时运行。如新运行的程序 B 很有可能覆盖掉正在运行的程序 A 已占有的某一块内存，从而造成 A 的崩溃。甚至某些不怀好意的程序可能会侵犯操作系统的地盘，引发操作系统的崩溃。
在这种情形下，人们还是想到了同时运行多个程序的办法：静态重定位。即在将程序装入内存之前，给程序中的每一个地址都加上该程序在内存中的首地址的偏移量，整体向后推移一段距离，只要内存够大，足以装下多个程序，他们就不会发生冲突。但显然就目前来看内存永远不可能够用，这时就要使用到 虚拟内存 管理的技术。
程序中不是所有的地址都可以按照静态重定位的方法处理，如使用到的一些关键寄存器的地址。这时就要求程序要提供额外的信息来说明这个地址要不要重定位，无疑提高了编程难度，加大了开发人员的负担。
待解决的问题？
综上所述，可以看到想要同时运行多个程序，急需解决的两个问题是：内存保护 和 地址重定位。
下面为了引出 地址空间 的概念，简要说明不使用虚拟内存与分页存储管理时，是如何解决这两个问题的：
地址空间，可以类比变量的命名空间，每个进程都有自己独立的地址空间就好像独占了整块内存区域。但要保证不同地址空间的相同地址映射到物理内存时不会发生冲突，就要借助 基址寄存器 和 界限寄存器，使用 动态重定位 的方法。
区别于静态重定位，动态重定位不需要在程序装载时改变程序中编写的内存地址，而是在执行每一条指令时利用两个关键寄存器中的值 动态的算出 实际地址。基址寄存器用于存放程序装载到内存的起始地址，界限寄存器存放程序的长度。避免了静态重定位的麻烦，但是显而易见的缺点是每次执行相关指令都要进行计算，所以为了加快速度，一般这个计算实际地址的过程由专门的硬件来负责。
这个硬件被称为 内存管理单元（Memory Management Unit，MMU），MMU 位于 CPU 和地址总线之间，会在 CPU 访存之前进行虚拟地址到物理地址的映射。即 CPU 看到的都是程序中实际编写的虚拟地址，而程序在内存中的真实地址是什么，由 MMU 借助两个寄存器中的值来动态计算并将地址发送到地址总线上。
界限寄存器指定了某程序所能访问的地址范围，访存时会与其进行比较，超出它的范围则拒绝访问，从而保证了其他程序的安全。
在使用虚拟内存的分页存储管理中，不需要使用这俩寄存器，而是使用 页表 来记录映射转换信息。
内存管理器 VS 内存管理单元？
内存管理器：记录哪些内存正在使用，哪些内存是空闲的，及时的分配和回收内存的管理程序。
内存管理单元：位于 CPU 和地址总线之间的硬件，用于处理 CPU 的访存请求，负责虚拟地址到物理地址的映射、内存保护、CPU 高速缓存的控制等。
虚拟内存
前面我们提到只要内存够大，只需使用静态重定位给每个程序分配足够的空间就行，但显然内存永远不可能够用。当程序比内存大的时候就装不进去无法运行，这时候就提出了 虚拟内存 的概念。
虚拟内存是利用了程序在时间和空间上的 局部性 原理，将程序划分成若干碎片，按需不断地将碎片在内存和 交换区 间换入换出，让程序误认为它独享了连续的、和可寻址空间一样大的内存区域。
局部性：在一段时间内经常运行某些相同的代码片段；在空间上经常运行某些相同碎片上的代码片段。程序的局部性使得程序只装入部分就可以运行。
交换区：在磁盘上划分出的一片空闲区域，供正在活动的进程将其暂时不用的碎片换出。
区别于 交换技术，交换技术每次内存中只保留一个程序，运行一段时间将正在运行的程序换出到磁盘，再将下一个程序换入内存，IO 的这段时间 CPU 将空转。而有了虚拟内存，多个正在运行程序的部分碎片都同时存在于内存当中，当某个程序等待其他碎片换入时，切换到另一个程序运行，提高了 CPU 利用率。
内存管理策略
固定分区与可变分区
固定分区：将内存分成若干固定大小的分区，大小可以不相同，当一个程序装入时选择一个合理大小的分区给它。缺点是容易产生内碎片，内存利用率不高。
可变分区：按照装入程序的实际大小给它分配内存空间，消灭了内碎片，但程序回收后留下的空白可能随着时间变得小而多，即产生外碎片，这时就需要耗时的内存整理操作。
分页存储管理
分页：进程是操作系统分配资源的基本单位，分页就是将每个进程的逻辑地址空间分成若干 大小相等 的片，称为 页面，同时物理内存也将被分成与页面大小相等的 页框。分页存储管理的任务就是为一个个页面分配页框或回收页框，这个逻辑地址到物理地址的映射由 MMU 借助 页表 完成。
页表：记录页框的分配情况，借助页表 MMU 才能完成地址的映射；每个进程都有自己的页表，页表存放在内存中，一般为了加速还会在 MMU 中设立一个缓冲区，称为 转换检测缓冲区（Translation Lookaside Buffer，TLB），用于缓存经常访问的页表项。
映射工作的过程
如上图一个 64KB（216）的进程被分成 16（24）个 4KB（212）的页面记录在页表中，页号作为索引。当 CPU 访存时，MMU 将地址分为 页地址 和 页内偏移地址 两部分，前面 4 位页地址指示页号，后面 12 位页内偏移地址刚好指示一页内的可编程地址。
通过索引查询页表，判断该页在不在内存中：
若在，因为页框大小与页面大小一样，取出该页的页框号后面再添上页内偏移量即是真实的物理地址；
若不在，则会发生 缺页中断，操作系统将负责把缺少的页面换入内存中，再重新执行刚才 CPU 发出的指令。若有空闲的页框，则直接放入所需页面即可；若无空闲的页框则需要使用页面调度算法选出一个页面换出以腾出一个页框。若换出的页面修改过，则需要 刷脏页，将修改过的页面重新写回磁盘。
页表中的信息
从上面可以看出页表中需要 页号、页框号、是否在主存中 的标志位、是否修改过 的标志位…
有了这几个信息，我们已经解决了前面提出的地址重定位问题，除此之外还有内存保护的问题，因此就需要一个标志位指示该页 是否可读写。当然这只是访问类型上的保护，还有进程间的保护其实已经实现，因为每个进程有自己独立的页表。在这之上还有 页面共享 的问题，后面会记录。
还要置一个 访问位，指示该页正在被使用，以防止某页面在被使用中时被换出。
最后必须的还需要一个 是否允许高速缓存 的标志，保证某些信息的时效性。
多次访存问题
分页在查询页表时多了一次访存操作，而前面 overview 中提到的重定位只需在程序装入前或者指令执行前加上一个偏移量即可。为了解决这个问题，我们在 MMU 中引入一块缓冲区来缓存经常访问的页表项，即 转换检测缓冲区（Translation Lookaside Buffer，TLB），这一操作的合理性也源于程序的局部性原理。
TLB 中缓存了常访问的、计算好的页面、页框号等信息。当 CPU 访存时 MMU 首先在 TLB 中查找，若命中则可以直接找到对应的页框，减少了一次访存；若没有命中则再去也表中查找，选择性的淘汰、更新 TLB 中的页表项信息。
进程切换时，TLB 中的信息像 CPU 高速缓存中的信息一样都需要更新，这也是进程切换的一大开销。
页面共享问题
两个进程共享一部分页面可以避免内存中有一个页面的两份副本，提高内存的使用率。
如打开两个 Word 文档，这两个 Word 程序放置程序文本的页面应该是共享的（这些程序代码还是只读的），不同的只是各自的数据部分。两个不同的进程也有可能共享相同页面，如放置通用的图形用户界面组件的页面。
问题是：如何方便的划分出是否可以共享的页面？给每个页面设置一个共享标志位当然可以实现，但是页表的维护就变得复杂了。有一种方法在原有的分页管理基础上稍加改动就可以实现，即 区分指令空间和数据空间。
将进程原来的地址空间一分为二，一份 I 空间 存放程序文本，一份 D 空间 存放数据，都从零开始编址，两个地址空间像两个进程一样进行独立的分页、映射，拥有各自独立的页表，还让该进程的可用地址空间加倍。上面提到的两个 Word 程序就可以方便的共享 I 空间。（后面的段页式内存管理的思想和这个很相似）
将共享的粒度放大一些，如动态链接库，在 Windows 中就是 DLL 文件，第一次被使用时以页面的形式被装载进内存，后面一个进程想要使用它时先判断它是否已经被装载，避免重复装载，达成共享。DDL 是 内存映射文件（memory mapped file）思想的一种应用实例。
内存映射文件的具体做法是：将一个磁盘文件映射到某个进程的地址空间内，文件不必全部及时装入内存，而是使用时装入所需的页面，就像使用虚拟内存一样。如果两个进程同时映射到一个文件，就达成了共享。除此之外利用这种内存映射的思想还可以进行进程间的通信。
共享内存达成进程通信
内存映射文件将磁盘文件映射到某个进程的地址空间，可以达到共享也可以达到进程间通信，如进程 A 对映射文件进行修改后，进程 B 可取到进程 A 修改后的信息，但显然这样经过了磁盘 IO，不是我们想要的进程间直接通信。
我们可以利用这种内存映射的思想，将内存中的一块共享区域映射到两个进程中，实现进程间通信。好处就是不用经过内核缓冲区，数据不用经过额外的复制，直接读即可。但是也有坏处就是无法保证进程 B 会等待进程 A 写完才读，这时候就要用到信号量进行同步；还有就是这种通信方法是不安全的，如多个进程同时写就会发生冲突，难以协调。
分段、段页式存储管理
分段存储管理
在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。例如，有主程序段 MAIN、子程序段 X、数据段 D 及栈段 S 等。每个段都有自己的名字。为了实现简单起见，通常可用一个段号来代替段名，每个段都从 0 开始编址，并采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。整个作业的地址空间由于是分成多个段，因而是二维的，亦即，其逻辑地址由段号 (段名) 和段内地址所组成。
将程序和数据划分为逻辑上独立的地址空间，有助于共享和保护。但是缺点和非固定分区一样，会产生外碎片，需要耗时的内存整理。
段页式存储管理
段页式系统的基本原理，是基本分段存储管理方式和基本分页存储管理方式原理的结合，即先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。
其实就是将页面按照其作用组织起来，非常类似于分页中将地址空间划分为 I 空间 和 D 空间，方便共享与保护，提升了可编址空间，但系统复杂性提高。
页面置换算法
页面置换的 最优算法 是想办法预测进程未来会使用的页，然后再进程执行之前将这些页调入内存中。
最优算法难以实现，于是按照不同的倾向有了下面三条线路：FIFO、LRU、工作集算法，在每一类算法上提出改进优化的方案又演变出不同的算法，最后综合了每一类的特性提出了最合理的算法。
FIFO算法 像一个队列，每次都淘汰最老的页面，容易实现且比较公平，但有可能淘汰掉重要页面；于是在此之上有了 第二次机会算法，改进了 FIFO 但链表操作比较耗时；时钟算法 又对其进行改进但还不是最优的。
LRU算法 比较符合最优算法的思想，但是难以实现，于是有了 NRU、NFU 算法，但还不是很有效，最后提出 老化算法，已经是一个非常近似于 LRU 的高效算法。
工作集算法 实现起来开销太大，于是综合了时钟算法提出了有效的 工作集时钟算法。
综上所述，基于 LRU 的老化算法和基于工作集的时钟算法是比较好的算法。下面就分别记录一下这几种算法：
FIFO
FIFO 算法：维护一个队列，新来的页面依次链入队尾，需要淘汰页面时就出队列。优点是方便、公平；缺点是容易淘汰重要页面。
第二次机会算法：在 FIFO 算法上进行改进，使用了一个指示最近有没有被访问的标志位，避免了将经常使用的页面置换出去。
设标志位 R=1 指示最近被访问过，R=0 指示最近没有被访问过。当一个页面被访问时，R 置为 1。当要淘汰页面时，判断队首页面的 R 值，若 R＝0 则直接淘汰，若 R=1，则将 R 置 0 并将 R 出队列且链入队尾，当做是一个新来的页面，这就是所谓的第二次机会，然后再判断新的队首页面，重复该过程。显然缺点是链表操作降低了效率。
时钟算法：和第二次机会算法相同，只是使用一个循环队列和一个指示当前最老页面的指针，这样避免了 R=1 时移动链表。
LRU
由程序的局部性反推，我们可以知道很久没用的页面大概率在未来很长一段时间内也不会被使用，所以有了 最近最少使用算法（Least Recently Used，LRU），非常接近最优的算法。
LRU 算法：为了实现 LRU 算法，我们需要为内存中的所有页面维护一个有序的链表，每次访存都需要更新整个链表，代价十分之高。
下面看两个 LRU 的裁剪版，NRU 和 NFU。设两个标志位 R、M 分别指示页面是否最近被使用、页面是否被修改过，周期性的将 R 置为 0。
最近未使用算法（Not Recently Used，NRU）：根据这两个标志位将内存中的页面 按照回收代价 从低到高分为了四类：
- 没有被访问，没有被修改；
- 没有被访问，已被修改；
- 已被访问，没有被修改；
- 已被访问，已被修改；
每次回收都在代价最小的一类中随机挑选一个淘汰。
最不常使用算法（Not Frequently Used，NFU）：为每个页面都关联一个计数器，每次时钟中断，都给所有的计数器加上页面的标志位 R，计数器值越小说明最不常用。NFU 的一个缺点就是保留了太多历史因素，如滞留在内存中的不常用页面，其计数器值可能比新载入内存的最近常用的页面的值还要高，从而不能及时被淘汰。
老化算法：非常巧妙的解决了 NFU 的问题，可以说是最接近 LRU 的算法。NFU 的问题是往计数器上 +R，造成历史因素影响较大，老化算法就及时的排除了这个历史因素，它在每次时钟中断时先将原始值右移一位，再将 R 值加在最左端形成新值。
工作集
定义与原理
工作集：一个进程当前正在使用的页面的集合称为该进程的工作集。
请求调页：一个进程刚启动时，内存中没有属于它的页面，于是在刚开始运行的一段时间内会发生频繁的缺页中断，每次中断都请求一个页面，一段时间后缺页中断的发生率会下降，这个过程就叫做请求调页。同时适用于某个进程已经运行过一段时间，被调度出去又被调度回来的情形。
预先调页：我们无法确切预测一个进程未来要使用哪些页，但是由于程序的局部性原理，我们知道一个进程在过去一段时间内使用的页在未来一段时间内也有很大概率被使用到。根据这个特点，我们可以断言某个被调度回来的进程有很大概率要使用它被调度出去之前一段时间内所使用的页面，即工作集。在该进程继续运行之前，预先调入推测的工作集页面，可以大大降低缺页中断的发生率，称为预先调页。
工作集页面置换算法
任务：我们现在的任务就是找到一个有效的办法推测出进程的工作集。有两种方案：
取进程最近 k 次访问过的页面集合，这个方案实现起来比较复杂且效率不高。
设想我们需要一个大于等于 k 的表依次记录最近使用的页面号，表满的时候就弹出最早的元素，当缺页中断时需要先读出最近 k 个页面号，再去重，即为工作集。找到工作集之后还没完，还要遍历页表找到一个不在工作集内的页面换出，去重、判断页面是否在工作集中都比较耗时。
取最近 t 秒进程实际运行时间中访问过的页面集合，使用这个方案需要在页表项中额外记录一个信息指示上次使用该页面的近似时间。除了上次使用时间再设两个字段：R 位指示是否最近被访问、M 位指示是否被修改，定期自动将 R 位置 0。流程如下：
缺页中断时，处理每个页表项，检查 R 位，若 R=1，则修改上次使用时间为当前实际时间，即说明改页面正在被使用。（注意这一步，说明是在每次缺页中断时才更改时间）
若 R=0，说明该页面最近没有被访问，则计算它的已生存时间，即当前时间减去上次使用时间，然后与规定的 t 值作比较：
若 生存时间 > t 则说明已经挺久没有被使用了，不在工作集当中，可以被替换。这时还没有完，还要更新其他 R=1 的页表项的上次使用时间为当前实际时间，否则下一次缺页中断来临时会发现这些页面都会很老，即像 NFU 算法一样保留了历史因素。
若 生存时间＜t 则说明它还在工作集内，应当保留，但我们要记住这种情况下页面的上次使用时间，找出一个上次使用时间最小的，即在工作集时间 t 内最久未用的一页。因为有可能发生这样的情况，当我们查找完页表后发现所有内存中的页面的在工作集当中，这时候我们就要淘汰一个最老的页面。与之相对应，还有一个最坏的情况就是所有页面都被访问过，即 R=1，这时候就要随机选择一个被淘汰。
缺点：每次缺页中断都要扫描整个页表，因此效率是比较低的。
工作集时钟页面置换算法
工作集时钟算法，融合了时钟算法与工作集算法。每次缺页中断时，先检查当前指针指向的页面，若 R=1 则将 R 置为 0，更新上次使用时间，移动指针，继续判断。若 R=0，则判断生存时间，大于 t 则可以被替换，小于 t 则在工作集内。若走了一圈又回到起点说明都在工作集内，由于不像工作集算法找到了最小的上次使用时间信息，所以这时候只得随机选一个页面被淘汰。
注意：前面不管是工作集还是工作集时钟算法，我们都是只考虑了指示最近是否被使用的 R 标志位，实际上我们还要考虑其他的因素，如是否被修改，像 NRU 算法一样找到替换的代价最小的页面进行替换，因为要替换一个脏页面，需要写回磁盘，就会引起进程的切换，浪费性能。
总结：最有效的算法是老化算法和工作集时钟算法。老化算法淘汰了最不常用的页，从结果上来看符合最优算法；而工作集时钟算法预测了进程的工作集，不论是从过程还是从结果上看都非常接近最优算法。