Operating System Three Pieces
第 9 章 调度：比例份额
关键问题：如何按比例分配 CPU
比例份额算法基于一个简单的想法：调度程序的最终目标，是确保每个工作获得一定比例的 CPU 时间，而不是优化周转时间和响应时间。
比例份额调度程序有一个非常优秀的现代例子，由 Waldspurger 和 Weihl 发现，名为彩 票调度（lottery scheduling） [WW94]。
彩票调度（lottery scheduling）
基本概念：彩票数表示份额
彩票数（ticket）代表了进程（或用户或其他）占有某个资源的份额。一个进程拥有的彩票数占总彩票数的百分比，就是它占有资源的份额。
彩票调度最精彩的地方在于利用了随机性（randomness）。当你需要做出决定时，采用随机的方式 常常是既可靠又简单的选择。
随机方法相对于传统的决策方式，至少有 3 点优势
1.随机方法常常可以避免奇怪的边角情况，较传统的算法可能在处理这些情况时遇到麻烦。例如 LRU 替换策略（稍后会在虚拟内存的章节详 细介绍）。虽然 LRU 通常是很好的替换算法，但在有重复序列的负载时表现非常差。但随机方法就没有这种最差情况；
2.随机方法很轻量，几乎不需要记录任何状态。在传统的公平份额调度算法中，记录每个进程已经获得了多少的 CPU 时间，需要对每个进程计时，这必须在每次运行结束后更新。而采用随机方式后每个进程只需要非常少的状态（即每个进程拥有的彩票号码）；
3.随机方法很快。只要能很快地产生随机数，做出决策就很快。因此，随机方式在对运行速度 要求高的场景非常适用。当然，越是需要快的计算速度，随机就会越倾向于伪随机。
彩票机制
彩票调度还提供了一些机制，以不同且有效的方式来调度彩票。
彩票货币（ticket currency）。这种方式允许拥有一组彩票的用户以他们喜欢的某种货币， 将彩票分给自己的不同工作。之后操作系统再自动将这种货币兑换为正确的全局彩票。
彩票转让（ticket transfer）。通过转让，一个进程可以临时将自己 的彩票交给另一个进程。这种机制在客户端/服务端交互的场景中尤其有用，在这种场景中， 客户端进程向服务端发送消息，请求其按自己的需求执行工作，为了加速服务端的执行， 客户端可以将自己的彩票转让给服务端，从而尽可能加速服务端执行自己请求的速度。服 务端执行结束后会将这部分彩票归还给客户端。
彩票通胀（ticket inflation）。利用通胀，一个进程可以临时提升或 降低自己拥有的彩票数量。当然在竞争环境中，进程之间互相不信任，这种机制就没什么 意义。一个贪婪的进程可能给自己非常多的彩票，从而接管机器。但是，通胀可以用于进 程之间相互信任的环境。在这种情况下，如果一个进程知道它需要更多 CPU 时间，就可以 增加自己的彩票，从而将自己的需求告知操作系统，这一切不需要与任何其他进程通信。
实现
实现简单，只需要一个不错的随机数生成器来选 择中奖彩票和一个记录系统中所有进程的数据结构（一个列表），以及所有彩票的总数。
如何分配彩票
系统的运行严重依赖于彩票的分配。假设用户自己知道如何分配，因此可以 给每个用户一定量的彩票，由用户按照需要自主分配给自己的工作。然而这种方案似乎什 么也没有解决——还是没有给出具体的分配策略。
为什么不是确定的
究竟为什么要利用随机性？从上面的内容可以看出，虽然随机方式 可以使得调度程序的实现简单（且大致正确），但偶尔并不能产生正确的比例，尤其在工作 运行时间很短的情况下。由于这个原因，Waldspurger 提出了步长调度（stride scheduling）， 一个确定性的公平分配算法[W95]。
待补充
第 10 章 多处理器调度（高级）
关键问题：如何在多处理器上调度工作
背景：多处理器架构
在单 CPU 系统中，存在多级的硬件缓存（hardware cache），一般来说会让处理器更快地执行程序。缓存是很小但很快的存储设备，通常拥有内存中最热的数据的备份。相比之下，内存很大且拥有所有的数据，但访问速度较慢。通过将频繁访问的数据放在缓存中， 系统似乎拥有又大又快的内存。
第 13 章 抽象：地址空间
关键问题：如何虚拟化内存
虚拟内存（VM）系统的一个主要目标是透明（transparency），另一个目标是效率（efficiency），第三个目标是保护（protection）
第 15 章 机制：地址转换
实现 CPU 虚拟化时，我们遵循的一般准则被称为受限直接访问（Limited Direct Execution，LDE）。
LDE思想：让程序运行的大部分指令直接访问硬件，只在 一些关键点（如进程发起系统调用或发生时钟中断）由操作系统介入来确保“在正确时间， 正确的地点，做正确的事”。
关键问题：如何高效、灵活地虚拟化内存
利用了一种通用技术，有时被称为基于硬件的地址转换（hardware-based address translation），简称为地址转换（address translation）。
利用地址转换，硬件对每次内存访问进行处理（即指令获取、数据读取或写 入），将指令中的虚拟（virtual）地址转换为数据实际存储的物理（physical）地址。因此， 在每次内存引用时，硬件都会进行地址转换，将应用程序的内存引用重定位到内存中实际 的位置。仅仅依靠硬件不足以实现虚拟内存，只是提供了底层机制来提高效率。
操作系统必须在关键的位置介入，设置好硬件，以便完成正确的地址转换。因此它必须管 理内存（manage memory），记录被占用和空闲的内存位置，并明智而谨慎地介入，保持对 内存使用的控制。
假设
先假设用户的地址空间必须连续地放在物理内存中。
动态（基于硬件）重定位
一个简单的思想，称为基址加界限 机制（base and bound），有时又称为动态重定位（dynamic relocation）：每个 CPU 需要两个硬件寄存器：基址（base）寄存器和界限（bound）寄存 器，有时称为限制（limit）寄存器。这组基址和界限寄存器，让我们能够将地址空间放在物理内存的任何位置，同时又能确保进程只能访问自己的地址空间。
1 | |
进程中使用的内存引用都是虚拟地址（virtual address），硬件接下来将虚拟地址加上基址寄存器中的内容，得到物理地址（physical address），再发给内存系统。
Example:
1 | |
程序计数器（PC）首先被设置为 128。当硬件需要获取这条指令时，它先将这个值加上基 址寄存器中的 32KB(32768)，得到实际的物理地址 32896，然后硬件从这个物理地址获取指令。 接下来，处理器开始执行该指令。这时，进程发起从虚拟地址 15KB 的加载，处理器同样将虚 拟地址加上基址寄存器内容（32KB），得到最终的物理地址 47KB，从而获得需要的数据。
界限寄存器的用处在于，它确保了进程产生的所有地址都在进程的地址“界限”中。界限寄存器确保了进程产生的所有地址都在进程的地址“界限”中，提供了访问保护。
在上面的例子中，界限寄存器被置为 16KB。如果进 程需要访问超过这个界限或者为负数的虚拟地址，CPU 将触发异常，进程最终可能被终止。
通常有两种使用方式。在一种方式中（像上面那样），它记 录地址空间的大小，硬件在将虚拟地址与基址寄存器内容求和前，就检查这个界限。另一种方 式是界限寄存器中记录地址空间结束的物理地址，硬件在转化虚拟地址到物理地址之后才去检 查这个界限。
操作系统的问题
支持动态重定位，硬件添加了新的功能，使得操作系统有了一些必须处理的新问题。
第一，在进程创建时，操作系统必须采取行动，为进程的地址空间找到内存空间。
第二，在进程终止时（正常退出，或因行为不端被强制终止），操作系统也必须做一些 工作，回收它的所有内存，给其他进程或者操作系统使用。在进程终止时，操作系统会将 这些内存放回到空闲列表，并根据需要清除相关的数据结构。
第三，在上下文切换时，操作系统也必须执行一些额外的操作。每个 CPU 毕竟只有一 个基址寄存器和一个界限寄存器，但对于每个运行的程序，它们的值都不同，因为每个程序被加载到内存中不同的物理地址。因此，在切换进程时，操作系统必须保存和恢复基础和界限寄存器。
第四，操作系统必须提供异常处理程序（exception handler），或要一些调用的函数，像上面提到的那样。操作系统在启动时加载这些处理程序（通过特权命令）。
带来的挑战
在我们当前的方式 中，即使有足够的物理内存容纳更多进程，但我们目前要求将地址空间放在固定大小的槽块 中，因此会出现内部碎片。内部碎片（internal fragmentation）， 指的是已经分配的内存单元内部有未使用的空间（即碎片），造成了浪费。以便更好地利用物理内存，避免 内部碎片。第一次尝试是将基址加界限的概念稍稍泛化，得到分段（segmentation）的概念。
第 16 章 分段
我们一直假设将所有进程的地址空间完整地加载到内存中。利用基址和 界限寄存器，操作系统很容易将不同进程重定位到不同的物理内存区域。但是，对于这些 内存区域，你可能已经注意到一件有趣的事：栈和堆之间，有一大块“空闲”空间。
关键问题：怎样支持大地址空间
分段：泛化的基址/界限
想法很简单，在 MMU 中引入不止 一个基址和界限寄存器对，而是给地址空间内的每个逻辑段（segment）一对。一个段只是 地址空间里的一个连续定长的区域，在典型的地址空间里有 3 个逻辑不同的段：代码、栈 和堆。
分段的机制使得操作系统能够将不同的段放到不同的物理内存区域，从而避免了虚拟地址空间中的未使用部分占用物理内存。
操作系统支持
分段的基本原理：系统运行时，地址空间中的不同段被重定位到物理内存中。与我们之前介绍的整个地址空间只有一个基址/界限寄存器对的方式相比， 大量节省了物理内存。具体来说，栈和堆之间没有使用的区域就不需要再分配物理内存， 让我们能将更多地址空间放进物理内存。
带来的问题
第一个是老问题：操作系统在上下文切换时应该做什么？你可能已经猜到了：各个段寄存器中的 内容必须保存和恢复。显然，每个进程都有自己独立的虚拟地址空间，操作系统必须在进 程运行前，确保这些寄存器被正确地赋值。
第二个问题更重要，即管理物理内存的空闲空间。新的地址空间被创建时，操作系统 需要在物理内存中为它的段找到空间。之前，我们假设所有的地址空间大小相同，物理内 存可以被认为是一些槽块，进程可以放进去。现在，每个进程都有一些段，每个段的大小也可能不同。物理内存很快充满了许多空闲空间的小洞，因而很难分配给新的段，或扩大已有的段。这种问题被称为外部碎片（external fragmentation）[R69]，
一种解决方案是紧凑（compact）物理内存，重新安排原有的段。另一种更简单的做法是利用空闲列表管理算法，试图保留大的内存块用于分配。
相关的算法包括传统的最优匹配（best-fit，从空闲链表中找最接近需要分配空 间的空闲块返回）、最坏匹配（worst-fit）、首次匹配（first-fit）以及像伙伴算法（buddy algorithm） [K68]这样更复杂的算法。
但遗憾的是，无论算法多么精妙，都无法完全消除外部碎片，因此，好的算法只是试图减小它。
小结
分段解决了一些问题，帮助我们实现了更高效的虚拟内存。不只是动态重定位，通过 避免地址空间的逻辑段之间的大量潜在的内存浪费，分段能更好地支持稀疏地址空间。它 还很快，因为分段要求的算法很容易，很适合硬件完成，地址转换的开销极小。分段还有 一个附加的好处：代码共享。如果代码放在独立的段中，这样的段就可能被多个运行的程 序共享。
第 17 章 空闲空间管理
如果需要管理的空间被划分为固定大小的单元，只需要维护这 些大小固定的单元的列表；
如果要管理的空闲空间由大小不同的单元构成，出现在用户级的内存分配库（如 malloc()和 free()），或者操作系统用分段（segmentation） 的方式实现虚拟内存。
在这两种情况下，出现了外部碎片（external fragmentation）的问题： 空闲空间被分割成不同大小的小块，成为碎片，后续的请求可能失败，因为没有一块足够 大的连续空闲空间，即使这时总的空闲空间超出了请求的大小。
关键问题：如何管理空闲空间
要满足变长的分配请求，应该如何管理空闲空间？什么策略可以让碎片最小化？不同方法的时间和 空间开销如何？
假设
假定基本的接口就像 malloc()和 free()提供的：函数返回一个指针（没有具体的类型， 在 C 语言的术语中是 void 类型），指向这样大小（或较大一点）的一块空间。对应的函数 void free(void *ptr)函数接受一个指针，释放对应的内存块。请注意该接口的隐含意义，在释 放空间时，用户不需告知库这块空间的大小。因此，在只传入一个指针的情况下，库必须能够弄清楚这块内存的大小。
该库管理的空间由于历史原因被称为堆，在堆上管理空闲空间的数据结构通常称为空 闲列表（free list）。该结构包含了管理内存区域中所有空闲块的引用。
当然，该数据结构不 一定真的是列表，而只是某种可以追踪空闲空间的数据结构。
第 18 章 分页：介绍
第 19 章 分页：快速地址转换（TLB）
第 20 章 分页：较小的表
第 21 章 超越物理内存：机制
第 22 章 超越物理内存：策略
第 23 章 VAX/VMS 虚拟内存系统
内存管理总结
独占式内存管理
在多任务并发运行时，每次任务切换都会涉及内存和磁盘之间的数据拷贝，效率低下；
最直观的解决方法是将程序的数据都常驻在内存中（假设内存足够），避免数据拷贝。但程序之间的内存地址空间是没有隔离的。引入虚拟化管理。
虚拟地址空间
OS为每个程序都虚拟化出一段内存空间，并映射到一段物理内存上。对程序而言，只看得到自己的虚拟地址空间。
程序内存管理
虚拟内存空间分为3个区域，Code区域存储的是程序代码的机器指令；Heap区域存储程序运行过程中动态申请的内存；Stack区域则是存储函数入参、局部变量、返回值等。Heap和Stack会在程序运行过程中不断增长，分别放置在虚拟内存空间的上方和下方，并往相反方向增长。
虚拟地址空间到物理地址空间的映射，需要一个转换。位于CPU芯片内的MMU（内存管理单元）负责。
MMU需要base和bound两个寄存器。其中base寄存器用来存储程序在物理内存上的基地址；bound寄存器（有时候也叫limit寄存器）则保存虚拟地址空间的Size，主要用来避免越界访问
物理地址 = 虚拟地址 + 基地址
但Heap，Stack区域之间有很大一部分空闲内存是“已申请，未使用”的空闲状态。但再也无法分配给其他程序使用，导致内存利用率低下的问题。为解决这个问题，引入段式内存管理。
段式内存管理
段（Segment）是逻辑上的概念，本质上是一块连续的、有一定大小限制的内存区域，前文中，我们一共提到过3个段：Code、Heap和Stack。
段式内存管理以段为单位进行管理，它允许OS将每个段灵活地放置在物理内存的空闲位置上，因此也避免了“已申请，未使用”的内存区域出现：
内存共享和保护
段式内存管理还可以很方便地支持内存共享，从而达到节省内存的目的。比如，如果存在多个程序都是同一个可执行文件运行起来的，那么这些程序是可以共享Code段的。为了实现这个功能，我们可以在虚拟地址上设置保护位，当保护位为只读时，表示该段可以共享。另外，如果程序修改了只读的段，则转换地址失败，因此也可以达到内存保护的目的。
内存碎片
段式内存管理的最明显的缺点就是容易产生内存碎片，这是因为在系统上运行的程序的各个段的大小往往都不是固定的，而且段的分布也不是连续的。当系统的内存碎片很多时，内存的利用率也会急剧下降，对外表现就是虽然系统看起来还有很多内存，却无法再运行起一个程序。
碎片整理的代价极大，一方面需要进行多次内存拷贝；另一方面，在拷贝过程中，正在运行的程序必须停止，这对于一些以人机交互任务为主的应用程序，将会极大影响用户体验。
页式内存管理
页式内存管理的思路，是将虚拟内存和物理内存都划分为多个固定大小的区域，这些区域我们称之为页（Page）。页是内存的最小分配单位，一个应用程序的虚拟页可以存放在任意一个空闲的物理页中。
物理内存中的页，我们通常称之为页帧（Page Frame）
因为页的大小是固定的，而且作为最小的分配单位，这样就可以解决段式内存管理中内存碎片的问题了。但页内仍然有可能存在内存碎片。