前言
本文是针对Remzi H. Arpaci-Dusseau等人专著的《Operating Systems: Three Easy Pieces》(中文译名《操作系统导论》)的英文原版的阅读笔记。主要为本人方便利用博客文章目录功能进行回阅总结用，本文大多是直接利用CopyTranslator对原文进行机翻而得。因此本文将毫无阅读体验。如果能读完本书，大概再做个总结。
1、绪论
本书操作系统学习包括三个部分：
- 虚拟化 (Virtualization)
- 并发性 (Concurrency)
- 持久化 (Persistence)
2、操作系统介绍
程序运行过程：处理器从内存提取指令，解码后再执行该指令
操作系统（OS）：看作是一堆软件，使程序能容易地运行。负责管理资源（CPU，内存和磁盘）。
虚拟化：OS把物理资源（如处理器，内存，磁盘）转为容易使用的虚拟形式。所以OS也称为虚拟机。
虚拟化CPU
CPU虚拟化：将单个CPU（或小规模CPU集群）转变为像是无限个CPU，像是可以一次同时运行多个程序。
虚拟化内存
每个进程都访问自己的私有虚拟地址空间（有时也称为进程的地址空间），操作系统将进程的虚拟地址空间以某种方式映射到计算机的物理内存上。
一个例子：有两个进程中都有一个指针变量指向地址0x200000，两个进程会独立地对他们进程内的这个0x200000地址上的数据进行操作，而不互相影响。因为0x200000并不是在实际硬件上的真实地址，而是进程各自的虚拟地址空间。
并发
一个多线程的例子：
|
|
两个线程执行counter++的次数各为loops次，设置loops的次数为N后，最后counter的值并非2N。
|
|
原因：
一次仅执行一条指令，而增加counter的指令分为3条：（1）从内存读取counter的值存进寄存器；（2）counter加1；（3）将counter的值存回内存。这三条指令的执行不具有原子性（Atomicity）（一次性全部执行完）。
持久化
因为掉电或崩溃后，内存中的数据将会丢失，因此需要能够持久保存数据的硬件和软件。硬件以I/O设备的形式，主要有硬盘和SSD；在OS中，管理磁盘的软件称为文件系统。
第一部分：虚拟化
虚拟化：假设系统只有一个物理CPU，让运行在系统上的多个应用认为它们都有自己的一个CPU，实际上这些CPU只是虚拟CPU。将一个物理CPU变成多个虚拟CPU的过程称为虚拟化。
4、进程（process）
进程：运行中的程序
分时技术：用一个资源（CPU）运行一个进程，然后停止运行这个进程，转而用该资源运行另一个进程。OS利用分时技术实现虚拟化。
抽象概念：进程
进程的机器状态（machine state）：
- 进程可寻址的内存，即地址空间
- 寄存器
- 记录当前进程打开的文件列表的I/O信息
5、进程API
- 创建进程
- 强制杀死进程
- 等待进程停止运行
- 暂停进程，之后恢复该进程
- 获取进程信息，如运行时间或状态
创建进程
程序是如何转变为进程的？（腾讯后台开发的面试题）
- OS读取磁盘上的可执行程序中的代码和静态数据（初始化的变量），并载入到内存，即进程的地址空间中。
- OS为程序的运行时栈（即栈（stack））分配内存。C程序用堆栈存放局部变量，函数参数和返回地址
- OS可能会分配内存给程序的堆（heap）。堆用存放显示请求的动态分配数据，这些数据涉及到链表，哈希表，树等数据结构。需要在程序中调用 malloc() 来分配内存给堆，调用 free() 来释放内存。随着进程的运行，通过 malloc() 请求的内存越多，OS需要分配更多的内存给进程。
- OS还将执行其他一些初始化任务，尤其是与I/O相关的初始化任务。 例如，在UNIX系统中，每个进程默认都有三个文件描述符，分别用于标准输入，输出和错误。这些描述符使程序可以轻松地从终端读取输入，并将输出打印到屏幕。
- 通过进入 main（），OS将CPU的控制权转移给新创建的进程，因此程序开始执行
进程状态
三种进程状态：
- 执行状态：进程运行在处理器上，正在执行指令
- 就绪状态：进程准备好执行了， 但OS并未选择执行它
- 阻塞状态：在阻塞状态下，进程执行了某种操作，直到发生其他事件（如完成I/O）才准备运行。一个常见的示例：当某个进程向磁盘发起I/O请求时，它会被阻塞，因此某些其他进程可以使用该处理器。
数据结构
操作系统中充满了各种重要的数据结构，我们将在这些说明中进行讨论。进程列表（也称为任务列表）是第一个这样的结构。进程列表是比较简单的一种数据结构，可以同时运行多个程序的任何OS都将具有类似于此结构的某种形式，以便跟踪系统中所有正在运行的程序。
作业
5、进程API
fork（）系统调用
fork（）系统调用用于创建新进程。
|
|
运行以上代码得：
|
|
当它第一次开始运行时，该过程将打印出一个hello world消息。 该消息中包含的是其进程标识符，也称为PID。 该进程的PID为29146； 在UNIX系统中，如果要对进程执行某项操作，则使用PID来命名该进程。
该进程调用fork（），OS提供的是一种创建新进程的方式。奇怪的是：创建的进程（几乎）是运行进程的副本。这意味着对于OS，现在看起来好像有两个正在运行的程序p1。新创建的进程（与创建父进程区分，称为子进程）不会像您期望的那样在main（）上开始运行（请注意，“ hello，world”消息仅被打印一次）。
wait（）系统调用
|
|
以上代码，父进程中调用了wait()，父进程会等子进程执行完毕后再执行。
exec（）系统调用
为什么？ 激励API
进程控制和用户
有用的工具
总结
作业
6、机制：受限直接执行
解决问题：（1）性能：如何在不增加系统开销的情况下实现虚拟化？（2）控制：如何在保持对CPU的控制的同时高效地运行进程？
基本技术：受限直接执行
这个想法的“直接执行”部分很简单：直接在CPU上运行程序。
因此，当OS希望启动程序运行时，它会在进程列表中为其创建一个进程条目，为其分配一些内存，将该程序代码加载到内存中（从磁盘），找到其入口点（即main()或其它类似入口）。
但是这种方法在我们寻求虚拟化CPU的过程中引起了一些问题。 第一个很简单：如果我们只运行一个程序，那么操作系统如何确保该程序没有执行我们不希望做的任何事情，而仍然有效地运行它？ 第二个：当我们运行一个进程时，操作系统如何阻止它运行并切换到另一个进程，从而实现虚拟化CPU所需的分时？
问题1：限制操作
直接执行的明显优势是速度快。 该程序可以在硬件CPU上本地运行，因此可以按照预期的速度执行。 但是在CPU上运行会带来一个问题：如果进程希望执行某种受限操作，例如向磁盘发出I/O请求，或者获得对更多系统资源（如CPU或内存）的访问权限，该怎么办？
进程必须能够执行I/O和其他一些受限制的操作，但又不能完全控制系统。操作系统和硬件如何一起工作才能做到这一点？
您可能想知道为什么对系统调用（例如open（）或read（））的调用看起来完全像C中的典型过程调用；为什么？ 也就是说，如果它看起来像过程调用，那么系统如何知道它是系统调用，并且做所有正确的事情？ 原因很简单：这是一个过程调用，但是隐藏在该过程调用中的是著名的陷阱指令。 更具体地说，例如，当您调用open（）时，您正在执行对C库的过程调用。 其中，无论对于open（）还是提供的任何其他系统调用，该库都使用与内核达成共识的调用约定，将参数放入open（）的已知位置（例如，在堆栈上或在 特定寄存器），也将系统调用号码也放入一个众所周知的位置（再次放在堆栈或寄存器中），然后执行上述陷阱指令。 陷阱解压缩后，库中的代码将返回值解压缩，并将控制权返回给发出系统调用的程序。 因此，进行系统调用的C库部分在组装时是经过手工编码的，因为它们需要仔细遵循约定以正确处理参数和返回值，以及执行特定于硬件的陷阱指令。 现在，您知道了为什么您个人无需编写汇编代码即可陷入操作系统； 有人已经为您编写了该程序集。
一种方法就是简单地让任何进程根据I / O和其他相关操作执行所需的操作。 但是，这样做会阻止构造许多所需的系统。 例如，如果我们希望构建一个在授予文件访问权限之前检查权限的文件系统，我们不能简单地让任何用户进程向磁盘发出I / O指令； 如果这样做的话，一个进程可以简单地读取或写入整个磁盘，从而失去所有保护。
因此，我们采用的方法是引入一种新的处理器模式，即用户模式。 在用户模式下运行的代码在功能上受到限制。 例如，在用户模式下运行时，进程无法发出I/O请求； 这样做将导致处理器引发异常； 这样操作系统可能会终止该进程。
与用户模式相反，内核模式运行在操作系统（或内核）上。在这种模式下，运行的代码可以执行自己喜欢的事情，包括特权操作（如发出I / O请求和执行所有类型的受限指令） 。
但是，我们仍然面临挑战：用户进程希望执行某种特权操作（例如从磁盘读取）时应该做什么？ 为此，几乎所有现代硬件都为用户程序提供了执行系统调用的能力。
硬件通过提供不同的执行模式来协助OS。 在用户模式下，应用程序无法完全访问硬件资源。 在内核模式下，操作系统可以访问计算机的全部资源。 还提供了捕获到内核并从捕获返回到用户模式程序的特殊指令，以及允许OS告知硬件陷阱表在内存中的位置的指令。
要执行系统调用，程序必须执行特殊的陷阱指令。 该指令同时跳入内核并将特权级别提升到内核模式； 一旦进入内核，系统现在就可以执行所需的任何特权操作（如果允许），从而完成调用过程所需的工作。 完成后，操作系统将调用特殊的陷阱返回指令，如您所料，它会返回到正在调用的用户程序，同时将特权级别降低回用户模式。
执行陷阱时，硬件必须有点小心，因为它必须确保保存足够的调用方寄存器，以便在OS发出陷阱返回指令时能够正确返回。 例如，在x86上，处理器会将程序计数器，标志和其他一些寄存器压入每个进程的内核堆栈中。 return-from-trap会将这些值弹出堆栈，并继续执行用户模式程序（有关详细信息，请参阅英特尔系统手册[I11]）。 其他硬件系统使用不同的约定，但各个平台的基本概念相似。
讨论中遗漏了一个重要的细节：陷阱如何知道要在OS内部运行哪些代码？ 显然，调用过程无法指定要跳转到的地址（就像进行过程调用时一样）； 这样做会使程序跳入内核的任何地方，这显然是一个非常糟糕的主意。 因此，内核必须仔细控制在陷阱上执行什么代码。
内核通过在引导时设置陷阱表来实现。 机器启动时，它将以特权（内核）模式启动，因此可以根据需要自由配置机器硬件。 因此，操作系统要做的第一件事就是告诉硬件，当某些异常事件发生时要运行什么代码。 例如，当发生硬盘中断，发生键盘中断或程序进行系统调用时，应该运行什么代码？
最后一点：能够执行指令以告知硬件陷阱表在哪里是一项非常强大的功能。 因此，您可能已经猜到了，它也是特权操作。 如果您尝试在用户模式下执行此指令，则硬件将无法让您执行操作，并且您可能会猜测会发生什么（提示：adios，违规程序）。 指向思考：如果您可以安装自己的陷阱表，那么对系统会做哪些可怕的事情？ 你能接管机器吗？
时间线（随着时间向下增加，在图6.2中）概述了协议。 我们假定每个进程都有一个内核堆栈，在移入和移出内核时，会将寄存器（包括通用寄存器和程序计数器）保存到其中（或通过硬件从中恢复）。
受限直接执行（LDE）协议分为两个阶段。在第一个阶段，内核初始化陷阱表，CPU记住其位置以备后用。 内核通过特权指令来执行此操作（所有特权指令均以粗体突出显示）。在第二步（运行进程时）中，内核在使用返回陷阱指令开始执行进程之前先设置了一些内容（例如，在进程列表上分配节点，分配内存）; 这会将CPU切换到用户模式并开始运行该进程。当进程希望发出系统调用时，它会捕获回OS，由OS进行处理，然后再次通过陷阱返回将控制权返回给进程。 然后，该过程完成其工作，并从main（）返回； 通常，这将返回一些存根代码，这些存根代码将正确退出程序（例如，通过调用进入操作系统的exit（）系统调用）。 至此，操作系统清理完毕，我们就完成了。
问题2：在进程之间切换
直接执行的下一个问题是实现进程之间的切换。 进程之间的切换应该很简单，对吧？ 操作系统应只决定停止一个进程并启动另一个进程。 有什么大不了的？ 但这实际上有点棘手：特别是，如果某个进程正在CPU上运行，则按照定义，这意味着OS没有运行。 如果操作系统没有运行，怎么办呢？ （提示：不可能）虽然这听起来几乎是哲学上的，但这是一个实际的问题：如果操作系统不在CPU上运行，则显然没有办法采取措施。 因此，我们得出了问题的症结所在。
操作系统如何重新获得对CPU的控制权，以便可以在进程之间进行切换？
协作方法：等待系统调用
某些系统过去采用的一种方法（例如，Macintosh操作系统的早期版本[M11]或旧的Xerox Alto系统[A79]）被称为协作方法。 操作系统以这种方式信任系统的进程以合理地运行。 假定运行时间过长的进程会定期放弃CPU，以便OS可以决定运行其他任务。
因此，您可能会问，在这个乌托邦世界中，友好的进程是如何放弃CPU的？ 事实证明，大多数进程都会通过进行系统调用来频繁地将CPU的控制权转移到OS，例如，打开文件并随后读取文件，或向另一台机器发送消息，或创建新进程。这样的系统通常包括一个显式的yield系统调用，该调用除了将控制权转移到OS之外不执行任何操作，因此它可以运行其他进程。
因此，在协作调度系统中，OS通过等待系统调用或某种非法操作来重新获得对CPU的控制。 您可能还会想：这种被动的方法是否不尽如人意？ 例如，如果某个进程（无论是恶意的还是仅是充满错误的）最终陷入无限循环而从不进行系统调用，会发生什么情况？ 操作系统可以做什么？
非合作方式：操作系统控制
事实证明，如果没有硬件的任何其他帮助，当进程拒绝进行系统调用（或错误）并因此将控制权交还给操作系统时，操作系统根本无法做任何事情。 实际上，在协作方法中，当进程陷入无限循环时，您唯一的求助方法是对计算机系统中的所有问题求助于古老的解决方案：重新启动计算机。 因此，我们再次遇到了获得CPU控制权的一般问题。
即使进程不协作，OS如何获得对CPU的控制？ 操作系统可以做些什么来确保流氓进程不会接管机器？
答案很简单，并在很多年前被许多构建计算机系统的人发现：定时器中断。 可以对计时器设备进行编程，使其每隔这么多毫秒就产生一次中断。 当引发中断时，当前正在运行的进程将停止，并且OS中预配置的中断处理程序将运行。此时，操作系统已重新获得了对CPU的控制权，因此可以执行自己喜欢的事情：停止当前进程，然后启动另一个进程。
Tips:计时器中断的添加使OS能够在CPU上再次运行，即使进程以非合作方式运行也是如此。 因此，此硬件功能对于帮助OS保持对计算机的控制至关重要。
正如我们之前在系统调用中讨论的那样，当定时器中断发生时，操作系统必须通知硬件要运行的代码。 因此，在引导时，操作系统正是这样做的。 其次，同样在引导过程中，操作系统必须启动计时器。一旦计时器开始计时，操作系统就可以放心了，因为最终该控制权限将返回给它，因此操作系统可以自由运行用户程序。 计时器也可以关闭（也是特权操作），稍后将在更详细地了解并发性时进行讨论。
请注意，硬件在发生中断时有一定的责任，特别是要保存足够的中断发生时正在运行的程序状态，以便随后的return-from-trap指令将能够正确恢复正在运行的程序。这组动作与在显式系统调用陷阱到内核期间的硬件行为非常相似，因此各种寄存器被保存（例如，保存到内核堆栈中），因此可以通过陷阱返回指令轻松恢复 。
保存和还原上下文
现在，操作系统已重新获得控制权，无论是通过系统调用来协作，还是通过计时器中断来更强行地控制，都必须做出一个决定：是继续运行当前正在运行的进程，还是切换到另一个进程。 该决定是由操作系统的一部分（称为调度程序）做出的。 在接下来的几章中，我们将详细讨论调度策略。
如果决定切换，则操作系统将执行一段底层代码，我们将其称为上下文切换。 上下文切换在概念上很简单：所有OS要做的就是为当前正在执行的进程保存一些寄存器值（例如，到其内核堆栈上），并为即将要执行的进程恢复一些寄存器值（从其内核堆栈）。 这样，OS可以确保在最终执行从陷阱返回指令时，而不是返回到正在运行的进程，系统将恢复另一个进程的执行。
为了保存当前正在运行的进程的上下文，操作系统将执行一些低级汇编代码以保存通用寄存器PC和当前正在运行的进程的内核堆栈指针，然后还原所述寄存器PC 并切换到即将执行的进程的内核堆栈。 通过切换堆栈，内核在一个进程（被中断的进程）的上下文中输入对切换代码的调用，并在另一个进程（即将执行的进程）的上下文中返回。当操作系统最终执行陷阱返回指令时，即将执行的进程成为当前正在运行的进程。从而上下文切换完成。
整个过程的时间表如图6.3所示。 在此示例中，进程A正在运行，然后被计时器中断中断。 硬件将其寄存器保存到内核堆栈中，然后进入内核（切换到内核模式）。 在计时器中断处理程序中，操作系统决定从正在运行的进程A切换到进程B。这时，它将调用switch（）例程，该例程小心地将当前寄存器值保存到A的进程结构中，并还原其中的寄存器。 进程B（从其进程结构条目开始），然后切换上下文，特别是通过将堆栈指针更改为使用B的内核堆栈（而不是A的内核堆栈）来切换上下文。 最后，操作系统从陷阱返回，这将恢复B的寄存器并开始运行它。
请注意，在此协议期间发生两种类型的寄存器保存/恢复。 首先是定时器中断发生。 在这种情况下，正在运行的进程的用户寄存器由硬件使用该进程的内核堆栈隐式保存。 第二个是操作系统决定从A切换到B时； 在这种情况下，内核寄存器由软件（即OS）显式保存，但是这次是在进程的进程结构中保存到内存中。 后一个动作使系统从好像从A被捕获到内核中一样运行，就像从B被捕获到内核一样。
为了使您更好地了解如何执行此切换，图6.4显示了xv6的上下文切换代码。 看看您是否可以理解它（您必须了解一些x86和一些xv6）。 旧的和新的上下文结构分别在新旧流程的流程结构中找到。
担心并发吗？
你们中的一些人，如专心和体贴的读者，现在可能会想：“嗯……在系统调用期间发生定时器中断时会发生什么？” 或“当您处理一个中断而另一个中断发生时会发生什么？ 难道在内核中难于处理吗？” 好问题-我们真的对您有希望！
答案是肯定的，如果在中断或陷阱处理期间发生另一个中断，操作系统确实确实需要关注会发生什么。实际上，这是本书第二章有关并发的确切主题。 在此之前，我们将进行详细的讨论。
为了激发您的胃口，我们将简要介绍操作系统如何处理这些棘手情况的一些基础知识。 操作系统可能做的一件简单的事情就是在中断处理过程中禁用中断。 这样可以确保一个中断正在处理时，其他任何中断都不会传递给CPU。当然，操作系统在执行此操作时必须谨慎。 禁用中断时间过长可能会导致中断丢失，从技术上来讲，这是很糟糕的。
操作系统还开发了许多复杂的锁方案，以保护对内部数据结构的并发访问。这样可以使多个活动同时在内核中进行，这在多处理器上特别有用。 但是，正如我们将在本书的下一篇关于并发的内容中所看到的那样，这种锁定可能很复杂，并且会导致各种有趣且难以发现的错误。
总结
我们已经描述了实现CPU虚拟化的一些关键的底层机制，这是我们统称为受限直接执行的一组技术。 基本思想很简单：只需运行要在CPU上运行的程序，但首先请确保设置硬件，以限制在没有操作系统协助的情况下该进程可以执行的操作。
现实生活中也采用了这种通用方法。 例如，您中那些有小孩，或者至少听说过小孩的人可能熟悉婴儿房的概念：上锁装有危险物品的柜子并盖上电源插座。 当房间准备就绪后，您可以让宝宝自由漫游，并确保房间最危险的部分已经被限制。
通过类似的方式，OS首先通过（在引导时间期间）设置陷阱处理程序并启动中断计时器，然后仅以受限模式运行进程来“证明” CPU。 这样，操作系统就可以确信进程可以高效运行，只需要操作系统干预即可执行特权操作，或者当它们垄断了CPU太长时间而需要将其关闭时。
因此，我们拥有就地虚拟化CPU的基本机制。但是有一个主要问题没有解决：我们应该在给定的时间运行哪个进程？ 调度程序必须回答这个问题，因此是我们研究的下一个主题。
作业
7、排程：简介
到现在为止，应该清楚运行进程的底层机制（例如上下文切换）； 如果不是，请返回一两章，然后阅读有关该内容如何工作的描述。 但是，我们尚未了解OS调度程序采用的高级策略。 现在，我们将介绍一系列调度策略（有时称为学科），这些策略是各种聪明而勤奋的人们多年来发展起来的。
调度的起源实际上早于计算机系统。 早期方法来自运营管理领域，并应用于计算机。 这种现实不足为奇：装配线和许多其他人类工作也需要计划，并且其中存在许多相同的问题，包括类似激光的对效率的渴望。 因此，我们的问题是：我们应该如何为思考调度策略开发一个基本框架？ 主要假设是什么？ 哪些指标很重要？ 最早的计算机系统中使用了哪些基本方法？
工作量假设
在探讨可能的策略之前，让我们首先对系统中运行的流程进行一些简化的假设，有时统称为工作量。 确定工作负载是构建策略的关键部分，您对工作负载的了解越多，对策略的调整就越多。
我们将对系统中正在运行的进程（有时称为作业）做出以下假设：
- 1.每个作业运行相同的时间。
- 2.所有作业都同时到达。
- 3.一旦开始，每个作业就会运行完成。
- 4.所有作业仅使用CPU（即不执行I / O）。
- 5.知道每个作业的运行时间。
排程指标
除了做出工作负载假设之外，我们还需要做更多的事情来使我们能够比较不同的调度策略：调度指标。指标只是我们用来衡量事物的指标，在计划中有许多不同的指标很有意义。
但是，现在，让我们通过简单地使用一个度量标准（周转时间）来简化我们的生活。 作业的周转时间定义为该作业完成的时间减去该作业到达系统的时间。
您应注意，周转时间是性能指标，这将是本章的重点。 另一个令人关注的指标是公平性。性能和公平性在调度中经常是矛盾的。 例如，调度程序可以优化性能，但是以阻止运行一些作业为代价，从而降低了公平性。 这个难题向我们表明，生活并不总是完美的。
先进先出（FIFO）
我们可以实现的最基本的算法称为先进先出（FIFO）调度，有时也称为先来先服务（FCFS）。
FIFO具有许多积极特性：显然很简单，因此易于实现。 而且，根据我们的假设，它可以很好地运行。
让我们一起做一个简单的例子。 想象一下，三个作业大致同时（Aarrival = 0）到达系统A，B和C。 由于FIFO必须优先处理某些工作，因此，假设它们同时到达时，A比B更早到一些，B比C更早到一些。还假定每个作业运行10秒。 这些工作的平均周转时间是 $\frac{10+20+30}{3}=20$
现在，让我们放宽我们的假设之一。 特别是，让我们放宽假设1，从而不再假设每个作业运行相同的时间。 FIFO现在如何执行？您可以构造什么样的工作量来使FIFO性能不佳？如：先执行用时长的作业。
平均周转时间变为 $\ frac {100 + 110 + 120} {3} = 110$ 此问题通常称为车队效应，其中资源的多个相对较短的潜在使用者排队等候在重量级资源消耗者后面。
那我们该怎么办？ 我们如何开发更好的算法来应对新的现实，这些新现实需要运行不同的时间？
最短工作优先（SJF）
事实证明，非常简单的方法可以解决此问题。这种新的调度规则称为最短作业优先（SJF），它的名称应该很容易记住，因为它非常完整地描述了策略：首先运行最短的作业，然后再运行下一个最短的作业，依此类推。
实际上，考虑到所有作业都是同时到达的假设，我们可以证明SJF确实是一种最佳调度算法。
因此，我们找到了一种使用SJF进行调度的好方法，但是我们的假设仍然相当不切实际。 让我们放松一下。 特别是，我们可以将假设2作为目标，现在假设作业可以随时到达而不是一次全部到达。 这会导致什么问题？
在这里我们可以用一个例子再次说明这个问题。 这次，假设A到达t = 0并需要运行100秒，而B和C到达t = 10且每个都需要运行10秒。使用纯SJF，即使B和C在A之后不久到达，他们仍然被迫等到A完成之后，从而遭受同样的车队问题。
最短完成时间优先（STCF）
为了解决这个问题，我们需要放宽假设3（即工作必须完成）。 在调度程序本身中，我们还需要一些机器。 您可能已经猜到了，鉴于我们之前对定时器中断和上下文切换的讨论，调度程序当然还可以做其他事情：当B和C到达时，它可以抢占作业A并决定执行其他作业，也许以后再继续A。 根据我们的定义，SJF是非抢占式调度程序，因此存在上述问题。
幸运的是，有一个调度程序可以做到这一点：将抢占添加到SJF中，称为**最短完成时间优先（STCF）或抢占式最短作业优先（PSJF）**调度程序。 每当新作业进入系统时，STCF调度程序都会确定剩下的剩余作业（包括新作业）中剩余的时间最少，并对其进行调度。 因此，在我们的示例中，STCF将抢占A并运行B和C直至完成； 只有完成后，A的剩余时间才能安排好。
新指标：响应时间
因此，如果我们知道作业的长度，并且作业仅使用CPU，而我们唯一的度量标准是周转时间，那么STCF将是一个很好的策略。 实际上，对于许多早期的批处理计算系统，这些类型的调度算法是有意义的。 但是，分时共享计算机的引入改变了这一切。 现在，用户将坐在终端上，并要求系统也具有交互性能。 因此，一个新的指标诞生了：响应时间。
响应时间：定义为从作业到达系统到其首次被调度的时间。
例如，如果我们有上述时间表（A在时间0到达，B和C在时间10到达），则每个作业的响应时间如下：作业A的响应时间为0，B的响应时间为0，C的响应时间为10（ 平均：3.33）。
您可能会想，STCF和相关学科对于响应时间并不是特别好。 例如，如果三个作业同时到达，则第三个作业必须等待前两个作业全部运行，然后才被调度一次。 虽然这种方法对周转时间很有用，但对于响应时间和交互性却很不利。 的确，想象一下坐在码头上打字，不得不等待10秒钟才能看到系统的响应，只是因为其他工作已经安排在您的面前了：不太愉快。
轮询调度
为了解决这个问题，我们将介绍一种新的调度算法，通常称为轮询调度（Round Robin (RR)）。 基本思想很简单：RR不运行作业以完成任务，而是运行一个时间片（有时称为调度时间）的作业，然后切换到运行队列中的下一个作业。 它会反复执行直到作业完成。 因此，RR有时称为时间分片。 注意，时间片的长度必须是计时器中断周期的倍数； 因此，如果计时器每10毫秒中断一次，则时间片可能是10毫秒，20毫秒或10毫秒的任何其他倍数。
为了更详细地了解RR，我们来看一个示例。 假设三个作业A，B和C在系统中同时到达，并且他们每个人希望运行5秒钟。 SJF调度程序将每个作业运行至完成，然后再运行另一个作业（图7.6）。 相比之下，时间切片为1秒的RR将快速循环完成这些工作（图7.7）。RR的平均响应时间为 $/frac{0+1+2}{3}=1$, SJF的为 $/frac{0+5+10}{3}=5$。
如您所见，时间片的长度对于RR至关重要。 它越短，在响应时间指标下的RR性能就越好。 但是，将时间片设置得太短是个问题：上下文切换的成本突然将主导整体性能。 因此，确定时间片的长度给系统设计者带来了一个折衷，使其花费了足够长的时间来摊销切换成本，而又没有使系统响应时间太长。
请注意，上下文切换的成本并非仅来自于保存和还原一些寄存器的OS操作。 程序运行时，它们会在CPU高速缓存，TLB，分支预测器和其他片上硬件中建立大量状态。 切换到另一个作业会导致刷新此状态并引入与当前正在运行的作业相关的新状态，这可能会导致明显的性能成本。
如果响应时间是我们唯一的度量标准，那么具有合理时间片的RR是出色的调度程序。 但是周转时间呢？ 让我们再次看一下上面的示例。 A，B和C的运行时间均为5秒，它们是同时到达的，而RR是具有（长）1秒时间片的调度程序。 从上图可以看出，A以13结束，B以14结束，C以15结束，平均周转时间为14。
因此，如果周转时间是我们的指标，那么RR确实是最糟糕的政策之一，这也就不足为奇了。 从直觉上讲，这应该是有道理的：RR所做的就是通过在运行下一个作业之前只运行一小段时间来尽可能延长每个作业。 由于周转时间只在乎作业何时完成，因此RR几乎是最小的，甚至在许多情况下甚至比简单的FIFO还差。
更一般而言，任何公平的策略（例如RR），即在很小的时间范围内将CPU均匀地划分为活动进程的策略，在诸如周转时间之类的指标上的效果都会很差。 确实，这是一种内在的权衡：如果您不公平，您可以运行较短的工作以完成任务，但要花响应时间。 如果您反而重视公平，响应时间缩短了，但要花费周转时间。 这种权衡在系统中很常见。
我们开发了两种类型的调度程序。 第一种类型（SJF，STCF）可优化周转时间，但不利于响应时间。 第二种（RR）优化了响应时间，但不利于周转。 而且，我们还有两个需要放松的假设：假设4（作业没有I / O）和假设5（每个作业的运行时间已知）。 接下来让我们解决这些假设。
整合I/O
首先，我们将放松假设4 —当然所有程序都执行I/O。
调度程序显然有一项决定要在作业启动I / O请求时做出，因为当前正在运行的作业在I / O期间不会使用CPU。在等待其I/O请求被完成前该作业被阻塞。 如果将I / O发送到硬盘驱动器，则该过程可能会阻塞几毫秒或更长时间，具体取决于驱动器的当前I / O负载。 因此，调度程序可能应该在那时在CPU上调度另一个作业。
I/O完成时，调度程序还必须做出决定。 发生这种情况时，将引发一个中断，并且操作系统将运行，并将发出I / O的进程从阻塞状态移回就绪状态。 当然，它甚至可以决定在那时运行该作业。 操作系统应如何对待每项工作？
为了更好地理解此问题，让我们假设我们有两个作业A和B，每个作业需要50毫秒的CPU时间。 但是，有一个明显的区别：A每运行10毫秒，然后发出一个I / O请求（假设每个I/O花费10毫秒），而B仅使用CPU 50毫秒，并且不执行I / O。 调度程序首先运行A，然后运行B（图7.8）。
一种常见的方法是将A的每个10毫秒子作业视为独立作业。 因此，当系统启动时，其选择是安排10毫秒A还是50毫秒B。对于STCF，选择很明确：选择较短的那个（在这种情况下为A）。 A的作业已完成，仅剩下B，并且开始运行。 然后提交A的新子作业，它抢占B并运行10毫秒。 这样做会产生重叠，一个进程正在使用CPU，而另一个进程的I/O等待完成。 因此可以更好地利用该系统（见图7.9）。
不再假设了
有了基本的I/O方法，我们得出了最终的假设：调度程序知道每个作业的时间。 如前所述，这可能是我们可能做出的最糟糕的假设。 实际上，在通用操作系统（如我们关心的操作系统）中，该操作系统通常对每个作业的时间了解很少。 因此，在没有先验知识的情况下，如何构建行为类似于SJF / STCF的方法？ 此外，我们如何将我们在RR调度程序中看到的一些想法纳入其中，以使响应时间也相当好？
总结
我们介绍了调度背后的基本思想，并开发了两种方法。 首先运行剩余的最短作业，从而优化周转时间。 第二个在所有作业之间切换，从而优化了响应时间。一者效果好的时候另一者效果不好，这是系统中固有的折衷。 我们还看到了如何将I/O整合到排程中，但是仍然没有解决OS根本无法预见未来的问题。 很快，我们将了解如何通过构建使用最近的过去来预测未来的调度程序来克服此问题。 该调度程序称为多级反馈队列，它是下一章的主题。
作业
8、排程：多级反馈队列
在本章中，我们将解决开发最著名的调度方法之一即**多级反馈队列（MLFQ）**的问题。
MLFQ试图解决的根本问题有两个。 首先，它想优化周转时间，正如我们在前面的笔记中所看到的，这是通过首先运行较短的作业来完成的； 不幸的是，操作系统通常不知道作业将运行多长时间，而这恰恰是SJF（或STCF）之类的算法需要的知识。 其次，MLFQ希望使系统对交互用户（即，用户坐在屏幕上凝视着屏幕，等待过程完成）感到有响应，从而将响应时间降至最低； 不幸的是，Round Robin之类的算法减少了响应时间，但周转时间却很糟糕。 因此，我们的问题是：鉴于我们通常对流程一无所知，我们如何构建调度程序来实现这些目标？ 调度程序如何在系统运行时了解正在运行的作业的特征，从而做出更好的调度决策？
我们如何设计一个调度程序，既可以使交互式作业的响应时间最短，又可以在事先不知道作业长度的情况下最大程度地缩短周转时间？
MLFQ：基本规则
在我们的处理中，MLFQ有许多不同的队列，每个队列分配了不同的优先级。 在任何给定时间，准备运行的作业都在单个队列中。 MLFQ使用优先级来决定应在给定时间运行哪个作业：选择优先级较高的作业（即，较高优先级队列中的作业）运行。
当然，给定队列中可能有多个作业，因此具有相同的优先级。 在这种情况下，我们将仅在这些作业之间使用轮询调度(RR)。
因此，我们得出了MLFQ的前两个基本规则：
- 规则1：如果优先级(A) > 优先级(B)，则A运行（B不运行）。
- 规则2：如果优先级(A) = 优先级(B)，则A和B在RR中运行。
因此，MLFQ调度的关键在于调度程序如何设置优先级。 MLFQ不会为每个作业赋予固定的优先级，而是根据其观察到的行为来改变其优先级。 例如，如果某个作业在等待键盘输入时反复放弃CPU，则MLFQ将保持其优先级，因为这是交互过程的行为方式。 相反，如果作业长时间大量使用CPU，则MLFQ将降低其优先级。 这样，MLFQ将尝试了解流程的运行情况，从而使用作业的历史记录来预测其未来的行为。
尝试1：如何更改优先级
现在，我们必须确定MLFQ将如何在作业的整个生命周期内更改作业的优先级级别（以及该作业处于哪个队列中）。 为此，我们必须牢记我们的工作量：短期运行（可能经常放弃CPU）的交互式作业的混合，以及运行时间较长的“受CPU限制”的作业，这些作业需要大量的CPU时间，但 响应时间不重要的地方。 这是我们对优先级调整算法的首次尝试：
- 规则3：当作业进入系统时，它被置于最高优先级（最高队列）。
- 规则4a：如果作业在运行时用尽了整个时间片，则会降低其优先级（即，将其向下移动一个队列）。
- 规则4b：如果作业在时间片结束前就放弃了CPU，则它将保持相同的优先级。
示例1：单个长期运行的作业
让我们看一些例子。首先，我们来看一下系统中长期运行的工作会发生什么。 图8.2显示了在三队列调度程序中，随着时间的流逝，该作业会发生什么情况。
在示例中可以看到，作业以最高优先级（Q2）进入。 经过10 ms的单个时间片后，调度程序将作业的优先级降低了一个，因此该作业在Q1上。 在Q1上运行了一个时间片之后，该作业最终被降低到系统中最低的优先级（Q0），并保留在那里。 很简单，不是吗？
示例2：短期工作
现在，让我们看一个更复杂的示例，并希望看到MLFQ如何尝试近似SJF。 在此示例中，有两个作业：A，它是长时间运行的CPU密集型作业，而B是一个短期运行的交互式作业。 假设A已经运行了一段时间，然后B到达了。 会发生什么？ MLFQ是否会为B近似SJF？
图8.3绘制了此方案的结果。 最低优先级队列中有一个（以黑色显示）（与所有长时间运行的CPU密集型作业一样）； B（以灰色显示）在时间T = 100到达，因此是插入最高队列； 由于B的运行时间很短（仅20毫秒），因此B在两个时间段内到达底部队列之前完成； 然后A恢复运行（低优先级）。
从这个例子中，您可以希望理解该算法的主要目标之一：因为它不知道某项工作是短期工作还是长期工作，因此它首先假定它可能是短期工作，因此得出 工作优先。 如果实际上是一项短期工作，它将快速且完整地运行； 如果这不是一项短期工作，它将慢慢地移到队列中，因此很快证明自己是一个长期运行的，更像批处理的过程。以这种方式，MLFQ近似为SJF
示例3：I/O呢？
现在让我们看一个带有一些I / O的示例。 如上面的规则4b所述，如果某个进程在用完其时间片之前就放弃了处理器，我们将其保持在相同的优先级。 该规则的意图很简单：例如，如果一个交互式作业正在执行大量I / O（例如，等待来自键盘或鼠标的用户输入），它将在CPU的时间片完成之前放弃CPU；否则，它将放弃CPU。 在这种情况下，我们不希望对工作进行惩罚，而只是将其保持在同一水平。
图8.4显示了一个工作方式的示例，其中交互式作业B（以灰色显示）仅需要1 ms的CPU才能执行与长时间运行的批处理作业A竞争CPU的I / O（以黑色显示） ）。 MLFQ方法将B保持在最高优先级，因为B不断释放CPU。 如果B是交互式作业，则MLFQ进一步实现了快速运行交互式作业的目标。
我们当前的MLFQ存在的问题
因此，我们有一个基本的MLFQ。 它看起来做得相当不错，可以在长时间运行的作业之间公平地共享CPU，并且可以让短时间或I / O密集型的交互式作业快速运行。 不幸的是，到目前为止，我们开发的方法存在严重缺陷。 你能想到什么吗？
首先，存在饥饿的问题：如果系统中的“交互式”作业过多，它们将合并消耗所有CPU时间，因此长时间运行的作业将永远不会获得任何CPU时间（它们饿死了）。 即使在这种情况下，我们也想在这些工作上取得一些进展。
其次，聪明的用户可以重写他们的程序来玩调度程序。 游戏调度程序通常指的是偷偷摸摸地欺骗调度程序，以使您获得比您合理分配的资源更多的想法。 我们描述的算法容易受到以下攻击：在时间片结束之前，执行I / O操作（对您不关心的某个文件），从而放弃CPU； 这样做可以使您保留在同一队列中，从而获得更高的CPU时间百分比。 如果做得正确（例如，在放弃CPU之前运行了99％的时间片），则作业几乎可以垄断CPU。
最后，程序可能会随着时间而改变其行为。 CPU绑定的内容可能会过渡到交互阶段。 使用我们当前的方法，这样的工作将是不走运的，不会像系统中的其他交互式工作一样被对待。
尝试2：优先级提升
如何解决饥饿问题？这里的简单想法是定期提高系统中所有作业的优先级。 有很多方法可以做到这一点，但让我们做一些简单的事情：将它们全部放入最上面的队列； 因此，一条新规则：
- 规则5：在一段时间S之后，将系统中的所有作业移到最上面的队列。
我们的新规则可以立即解决两个问题。 首先，确保进程不会挨饿：通过坐在最前面的队列，作业将以循环方式与其他高优先级作业共享CPU，从而最终获得服务。其次，如果与CPU绑定的作业已变为交互式，则调度程序在收到优先级提升后将对其进行正确处理。
尝试3：更好的会计
现在，我们还有一个要解决的问题：如何防止调度程序出现游戏问题？ 您可能已经猜到，真正的罪魁祸首是规则4a和4b，它们可以通过在时间片到期之前放弃CPU来保持作业的优先级。 那我们该怎么办？
此处的解决方案是在MLFQ的每个级别上更好地计算CPU时间。 调度程序不应忘记在给定级别使用多少时间段的进程，而应保持跟踪。 一旦进程使用了它的分配，它就会降级到下一个优先级队列。 它是在一个长脉冲串中使用时间片还是在多个小脉冲片中使用都无所谓。 因此，我们将规则4a和4b重写为以下单个规则：
- 规则4：作业在给定级别用完时间分配后（无论已放弃CPU多少次），其优先级就会降低（即，将其向下移动一个队列）。
调整MLFQ和其他问题
总结
我们已经描述了一种称为多级反馈队列（MLFQ）的调度方法。 希望您现在能明白为什么要这样称呼它：它具有多个队列级别，并使用反馈来确定给定作业的优先级。历史就是它的指南：注意工作随时间的变化，并相应地对待它们。
完善的MLFQ规则：
- 规则1：如果优先级（A）>优先级（B），则A运行（B不运行）。
- 规则2：如果优先级（A）= 优先级（B），则A和B使用给定队列的时间片（量子长度）以轮询调度方式运行。
- 规则3：当作业进入系统时，它被置于最高优先级（最高队列）。
- 规则4：作业在给定级别用完时间分配后（无论已放弃CPU多少次），其优先级就会降低（即，将其向下移动一个队列）。
- 规则5：在一段时间S之后，将系统中的所有作业移到最上面的队列。
MLFQ之所以有趣是因为以下原因：与其观察工作的本质不要求先验知识，而是观察工作的执行并对工作进行优先排序。 通过这种方式，它设法实现了两全其美：它可以为短期运行的交互式作业提供出色的整体性能（类似于SJF / STCF），并且在长期运行的CPU密集型工作负载方面是公平的并取得了进步。 因此，许多系统，包括BSD UNIX派生词，Solaris，Windows NT和后续的Windows操作系统，都使用MLFQ形式作为其基本调度程序。
作业
9、排程：按比例分配
在本章中，我们将研究另一种类型的调度程序，称为比例份额调度程序，有时也称为公平份额调度程序。 比例份额基于一个简单的概念：调度程序可能没有尝试优化周转时间或响应时间，而是尝试确保每个作业获得一定百分比的CPU时间。
我们如何设计调度程序以按比例共享CPU？ 这样做的关键机制是什么？ 它们的效果如何？
基本概念：票证代表您的份额
底层的彩票调度是一个非常基本的概念：票证，票证用于表示流程（或用户或其他任何人）应接收的资源份额。进程拥有的票证百分比表示其在相关系统资源中的份额。
让我们来看一个例子。想象一下两个进程A和B，A占有0-74的票证，而B占有75-99的票证。调度程序会随机落在0-99中，执行拥有所落票证的进程。
票务机制
彩票调度还提供了许多以不同的，有时是有用的方式操纵彩票的机制。一种方法是使用票证货币的概念。货币允许拥有票证的用户以自己想要的货币在自己的工作中分配票证；然后，系统会自动将所述货币转换为正确的全球价值。
例如，假设用户A和B分别获得了100张票证。 使用者A执行两个工作，分别为A1和A2，并分别以A的货币给他们500张票（总共1000张票）。 用户B仅运行1个作业，并给它10张票（总共10张票）。 系统将A1和A2的分配从A货币中的每个500转换为全球货币中的每个50； 同样，B1的10张票转换为100张票。 然后，以全球票证货币（总计200种）持有彩票，以确定运行哪个作业。
另一个有用的机制是票证转让。 通过转移，一个进程可以暂时将其票证移交给另一个进程。此功能在客户端/服务器设置中特别有用，在该设置中，客户端进程向服务器发送一条消息，要求其代表客户端进行一些工作。 为了加快工作速度，客户端可以将票证传递给服务器，从而在服务器处理客户端的请求时尝试最大化服务器的性能。完成后，服务器会将票证传送回客户端，一切如前所述。
最后，门票涨价有时可能是有用的技术。 随着通货膨胀，一个流程可以暂时提高或降低其拥有的门票数量。 当然，在竞争过程中彼此不信任的情况下，这毫无意义。 一个贪婪的过程可能会给自己带来大量门票，并接管机器。 相反，通货膨胀可以应用在一组进程相互信任的环境中。 在这种情况下，如果任何一个进程知道它需要更多的CPU时间，它就可以提高其工单价值，从而将其反映到系统中，而无需与任何其他进程进行通信。
实现
彩票调度最令人惊奇的事情可能是其实现的简单性。 您只需要一个好的随机数生成器来挑选中奖彩票，一个跟踪系统流程的数据结构（例如列表）和彩票总数。
假设我们将流程保存在列表中。 这是一个由三个过程A，B和C组成的示例，每个过程都有一定数量的凭单。
要做出计划决策，我们首先必须从总彩票数量（400）中选择一个随机数（获胜者）。假设我们选择了第300张彩票。然后，我们只需遍历列表，并使用一个简单的计数器 帮助我们找到赢家。
该代码遍历进程列表，将每个票证值添加到计数器，直到该值超过获胜者为止。 在这种情况下，当前列表元素将成为赢家。 以我们的中奖彩票为300的示例为例，发生以下情况。 首先，将计数器增加到100以说明A的票证； 因为100小于300，循环将继续。 然后计数器将更新为150（B的票），但仍少于300，因此我们再次继续。 最终，计数器被更新为400（明显大于300），因此我们突破了循环，最终指向C（获胜者）。
为了使此过程最有效，通常最好按从最高票数到最低票数的排序顺序组织列表。 排序不影响算法的正确性； 但是，它可以确保总体上确保最少的列表迭代次数，尤其是在少数几个进程拥有大多数票证的情况下。
一个例子
如何分配票证？
为什么不能确定性？
Linux完全公平调度程序（CFS）
**完全公平调度（CFS）**的调度程序实现了公平共享调度，并且以高效且可扩展的方式进行。
基本操作
尽管大多数调度程序都是基于固定时间片的概念，但CFS的操作略有不同。 它的目标很简单：在所有竞争的进程之间平均分配CPU。 它通过称为**虚拟运行时（vruntime）**的基于计数的简单技术来实现。
在每个进程运行时，它将累积vruntime。 在最基本的情况下，每个进程的虚拟运行时以相同的速率增长，与物理时间成比例。 当发生调度决策时，CFS将选择运行时间最低的进程，然后再运行。
这就提出了一个问题：调度程序如何知道何时停止当前正在运行的进程，然后运行下一个进程？ 这里的压力很明显：如果CFS切换得太频繁，公平性就会增加，因为CFS会确保每个进程即使在很小的时间窗口内也能获得其CPU份额，但这是以性能为代价（上下文切换太多）的； 如果CFS切换的频率降低，则性能会提高（上下文切换会减少），但会以近期公平为代价。
CFS通过各种控制参数来管理这种决策。首先是预定的延迟。CFS使用此值来确定一个进程在考虑切换之前应运行多长时间（有效地确定其时间段，但以动态方式）。 典型的计划等待时间值为48（毫秒）。 CFS将该值除以CPU上运行的进程数（n）来确定一个进程的时间片，从而确保在这段时间内CFS将完全公平。
例如，如果正在运行n = 4个进程，则CFS将调度等待时间的值除以n，得出每个进程的时间片为12 ms。 然后，CFS计划第一个作业并运行它，直到它使用了12毫秒的（虚拟）运行时为止，然后检查是否有一个具有较低vruntime的作业要运行。 在这种情况下，CFS将切换到其他三个作业之一，依此类推。
但是，如果运行的进程“太多”怎么办？ 那会不会导致时间片太小，从而导致上下文切换过多？好问题！答案是肯定的。
为了解决此问题，CFS添加了另一个参数最小粒度，通常设置为6 ms之类的值。CFS永远不会设置进程的时间片小于此值，以确保在安排开销方面不会花费太多时间。
例如，如果有十个进程在运行，我们的原始计算将调度的等待时间除以十以确定时间片（结果：4.8毫秒）。 但是，由于最小粒度，CFS会将每个进程的时间片设置为6 ms。 尽管CFS在48毫秒的目标调度延迟（调度延迟）上并不能（完全）公平，但在达到较高CPU效率的同时，它还是很接近的。
请注意，CFS利用周期性的计时器中断，这意味着它只能以固定的时间间隔做出决定。 此中断频繁关闭（例如，每1毫秒一次），使CFS有机会唤醒并确定当前作业是否已达到运行结束。如果作业的时间片不是计时器中断间隔的完美倍数，则可以；CFS精确跟踪vruntime，这意味着从长远来看，它将最终接近理想的CPU共享。
加权（友善度）
CFS还可以控制进程优先级，从而使用户或管理员可以为某些进程分配更高的CPU份额。 它不是使用票证而是通过经典的UNIX机制（称为进程的友善级别）来完成此任务。 可以将进程的友善参数设置为-20到+19之间的任意值，默认值为0。正的友善值表示优先级较低，而负的值表示优先级较高； 当您太友善时，您只会得到很少的（安排）注意力。
CFS将每个进程的友善值映射为权重。这些权重使我们能够计算每个进程的有效时间片（就像我们之前所做的一样），但是现在考虑了它们的优先级差异。这样做的公式如下：
$time_slice_k = \frac{weight_k}{\sum\limits_{i=0}^{n-1}{weight_i}}*sched_latency$
让我们做一个例子，看看它是如何工作的。假设有两个作业A和B。A，因为它是我们最宝贵的工作，所以给它分配了一个友善值-5，从而得到了更高的优先级。B，因为我们讨厌它，所以它具有默认优先级（友善值等于0）。 这意味着weightA（从表中）为3121，而weightB为1024。如果然后计算每个作业的时间片，您会发现A的时间片约为计划延迟的3/4（因此为36 ms），并且 B大约为1/4（因此为12 ms）。
使用红黑树
如上所述，CFS的一个主要重点是效率。 对于调度程序而言，效率有很多方面，但其中一个很简单：当调度程序必须找到要运行的下一个作业时，它应该尽快完成。 像列表这样的简单数据结构无法扩展：现代系统有时由数千个进程组成，因此每隔几毫秒搜索一个长列表是很浪费的。
CFS通过将进程保留在红黑树中来解决此问题。 红黑树是许多平衡树中的一种。 与简单的二叉树（在最坏情况下的插入模式下可能退化为类似列表的性能）相反，平衡树做了一些额外的工作来保持较低的深度，从而确保操作在时间上是对数的（而不是线性的）。
CFS不会将所有进程都保留在此结构中； 而是仅将运行（或可运行）进程保留在其中。 如果某个进程进入睡眠状态（例如，等待I/O完成，或等待网络数据包到达），则会将其从树中删除并跟踪其他位置。
让我们看一个例子，以使这一点更加清楚。 假设有十个作业，并且它们具有以下vruntime值：1、5、9、10、14、18、17、21、22和24。如果我们将这些作业保留在有序列表中，查找下一个要运行的工作很简单：只需删除第一个元素。 但是，当将该作业放回列表中时（按顺序），我们将不得不扫描列表，寻找合适的位置将其插入，执行O（n）操作。 任何搜索的效率也很低，平均也要花费线性时间。
在红黑树中保持相同的值可使大多数操作更高效。 进程按vruntime在树中排序，并且大多数操作（例如插入和删除）在时间上都是对数的，即O（log n）。 当n为数千时，对数的效率明显高于线性的效率。
处理I/O和睡眠进程
选择要运行的最低vruntime的一个问题是长时间休眠的作业引起的。 想象一下两个过程，A和B，其中一个过程（A）连续运行，另一个过程（B）长时间睡眠（例如10秒）。 当B醒来时，其运行时间将比A落后10秒钟，因此（如果我们不小心的话），B在追赶时将在接下来的10秒钟内独占CPU，有效地使A饿了。
CFS通过在作业唤醒时更改其运行时间来处理这种情况。具体来说，CFS将该作业的vruntime设置为在树中找到的最小值（请记住，该树仅包含正在运行的作业）。这样，CFS避免了饥饿，但并非没有代价：短时间睡眠的工作经常无法获得CPU的应有份额。
总结
我们介绍了比例份额调度的概念，并简要讨论了三种方法：彩票调度，步幅调度和Linux的完全公平调度（CFS）。CFS是本章中讨论的唯一“真正的”调度程序，有点像带有动态时间片的加权轮询调度，但是可以在负载下扩展和良好地运行。 据我们所知，它是当今最广泛使用的公平份额调度程序。
CFS使用红黑树来保存进程
作业
10、多处理器调度（高级）
本章将介绍多处理器调度的基础。 由于该主题相对较高级，因此最好在详细研究并发主题（即，本书的第二个主要“容易的部分”）之后再进行介绍。
背景：多处理器架构
不要忘记同步
最后一个问题：缓存关联性
单队列调度
多队列调度
Linux多处理器调度程序
总结
我们已经看到了用于多处理器调度的各种方法。 单队列方法（SQMS）的构建非常简单，可以很好地平衡负载，但是固有地很难扩展到许多处理器并具有缓存相似性。 多队列方法（MQMS）可以更好地扩展并且可以很好地处理缓存相似性，但是在负载不平衡方面存在麻烦，并且更加复杂。 无论采用哪种方法，都没有简单的答案：构建通用调度程序仍然是一项艰巨的任务，因为小的代码更改可能会导致巨大的行为差异。 仅当您确切地知道自己在做什么或者至少为此而赚了很多钱时，才进行这样的练习。
作业
11、总结：CPU虚拟化
教授：那么，学生，您学到了什么吗？
学生：好的，教授，这似乎是个很棘手的问题。 我想您只想让我说“是”。
教授：是的。 但这也是一个诚实的问题。 来吧，请教授休息一下，好吗？
学生：好的，好的。 我想我确实学到了一些东西。 首先，我了解了一些有关操作系统如何虚拟化CPU的知识。 为了理解这一点，我必须理解很多重要的机制：陷阱和陷阱处理程序，计时器中断，以及在进程之间切换时OS和硬件如何必须仔细保存和恢复状态。
教授：好，好！
学生：所有这些交互似乎都有些复杂； 我该如何学习？
教授：嗯，这是一个很好的问题。 我认为无可替代。 仅阅读这些内容并不能完全正确地理解。做课堂项目，我敢打赌最后这一切都是有道理的。
学生：听起来不错。 我还能告诉你什么？
教授：嗯，在您了解操作系统的基本机制时，您是否对操作系统的哲学有所了解？
学生：嗯…我是这样认为的。 看来操作系统是相当偏执的。 它希望确保由机器负责。 虽然OS希望程序尽可能高效地运行（因此直接执行受到限制的整个原因），但OS还希望能够说“啊！ 如果发生错误或恶意的程序，请不要这么快。 偏执狂掌管着一天，并且肯定让操作系统负责机器。 也许这就是为什么我们将操作系统视为资源管理器。
教授：是的，的确如此-听起来您已经开始把它们放在一起！ 真好
学生：谢谢。
教授：那这些机制之上的政策又如何呢？那里有什么有趣的教训？
学生：那里肯定有一些教训。 也许有些明显，但明显可以是好的。 就像将短期工作放在队列中的想法一样，我知道这是一个好主意，因为有一次我在商店里买口香糖，而我前面的那个人有一张无效的信用卡。他不是空头，我告诉你。
教授：对那个可怜的家伙听起来很粗鲁。 还有什么？
学生：好吧，您可以构建一个智能调度程序，使其一次看起来像SJF和RR一样-MLFQ非常简洁。 建立一个真正的调度程序似乎很困难。
教授：确实是。 这就是为什么在今天使用哪种调度程序方面仍然存在争议。 例如，请参见Linux在CFS，BFS和O（1）调度程序之间的斗争。 不，我不会说出BFS的全名。
学生：我不会问你！ 这些政策战似乎可能永远持续下去。 真的有正确的答案吗？
教授：可能不会。 毕竟，即使是我们自己的指标也存在矛盾：如果您的调度程序在周转时间方面表现出色，那么在响应时间方面就表现不好，反之亦然。正如兰普森所说，也许目标不是找到最佳解决方案，而是避免灾难。
学生：有点令人沮丧。
教授：好的工程就是这样。 而且也可以令人振奋！确实，这只是您的观点。 我个人认为，务实是一件好事，实用主义者意识到，并非所有问题都有解决方案。 还有其他吸引您的想法吗？
学生：我真的很喜欢游戏调度程序的概念。 当我下次在Amazon EC2服务上运行作业时，似乎需要研究一下。 也许我可以从其他一些毫无戒心（更重要的是，对操作系统不了解）的客户那里窃取一些信息！
教授：看来我可能创造了一个怪物！ 弗兰肯斯坦教授不是我想要的名字。
学生：但这不是这个主意吗？ 为了让我们对某件事感到兴奋，以至于我们自己去研究它？ 点燃火等吗？
教授：我想是的。 但我认为这行不通！
12、绪论：内存虚拟化
学生：那么，我们完成虚拟化了吗？
教授：不！
学生：嘿，没有理由变得如此兴奋。 我只是问一个问题。 学生应该这样做，对吗？
教授：嗯，教授总是会这么说，但实际上他们的意思是：问问题，如果它们是好问题，实际上您已经对它们进行了一点思考。
学生：好吧，那一定会使风吹散。
教授：任务完成了。 无论如何，我们几乎都无法完成虚拟化！ 而是，您刚刚看到了如何虚拟化CPU，但是壁橱中确实有一个巨大的怪物在等待：内存。 虚拟化内存非常复杂，需要我们了解有关硬件和操作系统如何交互的更多复杂细节。
学生：听起来不错。 为什么这么难？
教授：好，有很多细节，您必须直截了当地，才能真正建立出正在发生的事情的心理模型。 我们将从基本/边界等非常基本的技术开始，然后逐渐增加复杂性以应对新的挑战，包括有趣的主题（如TLB和多级页表）。 最终，我们将能够描述功能齐全的现代虚拟内存管理器的工作原理。
学生：整齐！ 对这名贫困学生的任何小贴士，都被所有这些信息所淹没，并且普遍缺乏睡眠？
教授：对于睡眠不足，这很容易：多睡（少聚会）。为了理解虚拟内存，从此开始：用户程序生成的每个地址都是一个虚拟地址。 操作系统只是给每个进程提供了一种错觉，像是它拥有自己的大型私有内存。 在某些硬件帮助下，OS会将这些伪装的虚拟地址转换为真实的物理地址，从而能够找到所需的信息。
学生：好的，我想我可以记住…（自我）用户程序中的每个地址都是虚拟的，用户程序中的每个地址都是虚拟的，每个…
教授：你在抱怨什么？
学生：哦，什么都没有。…（尴尬的停顿）…无论如何，为什么操作系统要再次提供这种错觉？
教授：大多数情况下易于使用：操作系统会给每个程序一个视图，即它有很大的连续地址空间可用于将其代码和数据放入其中。 因此，作为一名程序员，您不必担心“我应该在哪里存储此变量？”之类的问题。 因为程序的虚拟地址空间很大，并且有足够的空间容纳这种事情。 如果您不得不担心将所有代码数据放入一个很小的拥挤的内存中，那么对于程序员而言，生活变得更加棘手。
学生：为什么呢？
教授：隔离和保护也很重要。 我们不希望一个错误的程序能够读取或更糟的是覆盖其他程序的内存，是吗？
学生：大概不会。 除非是您不喜欢的人编写的程序。
教授：嗯。。。我认为我们可能需要在下学期的课程表中增加一门道德和道德课。 也许OS类无法正确传达信息。
学生：也许我们应该。 但是请记住，不是我教会我们，操作系统对错误进程行为的正确响应是杀死有问题的进程！
13、抽象概念：地址空间
早期系统
从内存的角度来看，早期的机器并没有为用户提供太多抽象。
操作系统是一组位于内存中的例程（实际上是一个库）（在此示例中从物理地址0开始），并且当前有一个正在运行的程序（进程）在物理内存中（从物理地址开始），并使用了其余的内存。
多程序和时间共享
一段时间之后，由于机器价格昂贵，人们开始更有效地共享机器。 因此，多重编程时代诞生了，在该时代中，多个进程准备在给定的时间运行，并且OS将在它们之间切换，例如，当一个人决定执行I/O时。 这样做可以提高CPU的有效利用率。 在每台机器花费数十万甚至数百万美元的那些日子里，这种效率的提高尤其重要。
然而，很快人们就开始要求更多的机器，而时间共享时代就此诞生了。 具体来说，许多人意识到批处理的局限性，特别是对程序员本人，他们厌倦了漫长的（因此无效的）程序调试周期。 交互性的概念变得很重要，因为许多用户可能正在同时使用计算机，每个用户都在等待（或希望）他们当前正在执行的任务的及时响应。
实现时间共享的一种方法是短暂运行一个进程，使其完全访问所有内存，然后停止它，将其所有状态保存到某种磁盘（包括所有物理内存）中。加载其他进程的状态，运行一段时间，从而实现对机器的某种粗略共享。
不幸的是，这种方法存在一个大问题：它太慢了，特别是随着内存的增长。虽然保存和恢复寄存器级状态（PC，通用寄存器等）相对较快，但将整个内存内容保存到磁盘上却是残酷的。 因此，我们宁愿将进程留在内存中，同时在它们之间进行切换，从而使操作系统能够有效地实现时间共享。
随着时间共享变得越来越流行，您可能会猜到对操作系统提出了新的要求。 特别是，允许多个程序同时驻留在内存中使保护成为一个重要问题。 您不希望某个进程能够读取，或者更糟的是，写入其他进程的内存。
地址空间
但是，我们必须牢记那些讨厌的用户，并且这样做需要操作系统创建易于使用的物理内存抽象。 我们称这种抽象为地址空间，它是运行程序在系统中的内存视图。了解内存的基本操作系统抽象是了解如何虚拟化内存的关键。
进程的地址空间包含正在运行的程序的所有内存状态。 例如，程序代码（指令）必须驻留在内存中的某个位置，因此它们位于地址空间中。该程序在运行时会使用栈来跟踪它在函数调用链中的位置，以及分配局部变量，并在例程之间传递参数以及返回值。 最后，堆用于动态分配的，用户管理的内存，例如，您可能会从C语言中的malloc（）调用或以面向对象的语言（如C++或Java）中收到对new的调用中收到。 当然，其中也有其他内容（例如，静态初始化的变量），但是现在让我们仅假设这三个组件：代码，栈和堆。
在图13.3的示例中，我们有一个很小的地址空间（只有16KB）。程序代码位于地址空间的顶部（在此示例中，从0开始，并打包到地址空间的前1K中）。代码是静态的（因此很容易放在内存中），因此我们可以将其放在地址空间的顶部，并知道在程序运行时它不需要任何空间。
接下来，我们在程序运行时拥有地址空间的两个区域，它们可能会增长（和收缩）。 这些是堆（在顶部）和栈（在底部）。 我们之所以这样放置它们，是因为这两者都希望能够增长，通过将它们放在地址空间的相对两端，我们可以允许这种增长：它们只需要朝相反的方向增长即可。 这样，堆就在代码之后（1KB）开始并向下增长（例如，当用户通过malloc（）请求更多内存时）； 栈从16KB开始并向上增长（例如，当用户进行过程调用时）。但是，这种栈和堆的放置只是一个约定。您可以根据需要以不同的方式安排地址空间（我们将在后面看到，当一个地址空间中同时存在多个线程时，再也没有一种很好的方法来划分地址空间了，可惜）。
当然，当我们描述地址空间时，我们所描述的是操作系统为正在运行的程序提供的抽象。该程序实际上不在内存中的物理地址0到16KB； 而是将其加载到某个任意物理地址。因此，问题是：操作系统如何在单个物理内存之上为多个正在运行的进程（所有进程共享内存）构建私有的，潜在的大型地址空间的抽象？
当操作系统执行此操作时，我们说操作系统正在虚拟化内存，因为正在运行的程序认为它已加载到特定地址（例如0）的内存中，并且具有很大的地址空间（例如32位或64位）; 现实是完全不同的。
例如，进程A尝试在地址0（我们将其称为虚拟地址）上执行加载时，以某种方式，操作系统与某些硬件支持相结合，将必须确保加载实际上并没有转到物理地址0，而是物理地址320KB（内存中A实际所在位置）。这是内存虚拟化的关键，而内存虚拟化是世界上每个现代计算机系统的基础。
目标
虚拟内存（VM）系统的一个主要目标是透明度。操作系统应以对正在运行的程序不可见的方式实现虚拟内存。 因此，程序不应意识到内存已虚拟化。 而是，程序的行为就像具有自己的专用物理内存一样。 在后台，操作系统（和硬件）完成了所有工作，以在许多不同的作业之间多路复用内存，从而实现了这种错觉。
VM的另一个目标是效率。 操作系统应努力在时间（即不让程序运行得更慢）和空间（即不为支持虚拟化的结构使用过多的内存）方面使虚拟化尽可能高效。 在实现高效的虚拟化时，操作系统将不得不依赖硬件支持，包括诸如TLB的硬件功能（我们将在适当的时候进行了解）。
最后，第三个VM目标是保护。操作系统应确保互相保护进程，以及操作系统本身应防止进程相互影响。 当一个进程执行加载，存储或指令提取时，它不应以任何方式访问或影响任何其他进程或OS本身（即，其地址空间之外的任何内容）的内存内容。 因此，保护使我们能够在流程之间提供隔离的特性。每个进程都应在自己的隔离茧中运行，以免遭受其他故障甚至恶意进程的破坏。
在下一章中，我们将重点研究虚拟化内存所需的基本机制，包括硬件和操作系统支持。 我们还将研究您在操作系统中会遇到的一些更相关的策略，包括如何管理可用空间以及当空间不足时要从内存中踢出哪些页面。这样一来，我们将加深您对现代虚拟内存系统的工作原理的理解。
总结
我们已经看到了一个主要的OS子系统的引入：虚拟内存。VM系统负责为程序提供庞大，稀疏的专用地址空间的幻觉，这些程序将其所有指令和数据保存在其中。 操作系统将在一些硬件帮助下获取每个虚拟内存引用，并将它们转换为物理地址，可以将其提供给物理内存，以获取所需的信息。 操作系统将一次对许多进程执行此操作，并确保相互保护程序并保护操作系统。 整个方法需要大量的机制（很多底层机制）以及一些关键的策略才能起作用。 我们将从头开始，首先描述关键机制。 因此，我们继续！
旁白：您看到的每个地址都是虚拟的
是否曾经编写过一个打印指针的C程序？ 您看到的值（一些较大的数字，通常以十六进制打印）是一个虚拟地址。 有没有想过在哪里找到您的程序的代码？ 您也可以打印出来，是的，如果可以打印，它也是一个虚拟地址。实际上，作为程序员，您可以看到的用户级程序的任何地址都是虚拟地址。 只有操作系统通过其虚拟化内存的棘手技术，才能知道这些指令和数据值位于计算机的物理内存中。 因此，永远不要忘记：如果您在程序中打印出一个地址，那是一个虚拟的地址，这是对事物在内存中的布局的一种幻想；只有操作系统（和硬件）才知道真实情况。
一个例子，它打印出main()例程（代码所在的位置）的地址，从malloc()分配的值在堆上的地址值以及整数在栈上的地址：
|
|
在64位Mac上运行时，我们得到以下输出：
|
|
由此可见，代码首先出现在地址空间中，然后出现在堆中，而栈一直到此大虚拟空间的另一端。所有这些地址都是虚拟的，将由OS和硬件进行转换，以便从其真实的物理位置获取值。
作业
14、插曲：内存API
内存类型
malloc（）调用
free（）调用
常见错误
底层操作系统支持
其他调用
总结
作业
15、机制：地址翻译
在开发CPU的虚拟化过程中，我们集中于一种称为**受限直接执行（LDE）**的通用机制。 LDE背后的想法很简单：在大多数情况下，让程序直接在硬件上运行； 但是，在某些关键的时间点（例如，当进程发出系统调用或发生计时器中断时），请安排好操作系统，以确保“正确”的事情发生。 因此，在几乎没有硬件支持的情况下，操作系统将尽最大努力摆脱正在运行的程序，从而提供有效的虚拟化。 但是，通过在这些关键的时间点进行插入，OS可以确保它保持对硬件的控制。 效率和控制是任何现代操作系统的两个主要目标。
在虚拟化内存中，我们将采用类似的策略，在提供所需的虚拟化的同时实现效率和控制力。 效率要求我们利用硬件支持，起初您会很基本（例如，只有几个寄存器），但会变得相当复杂（例如，TLB，页表支持等）。控制意味着操作系统确保任何应用程序除其自身的内存外不能访问其它任何内存； 因此，为了保护应用程序彼此之间以及操作系统与应用程序之间的相互保护，我们在这里也需要硬件的帮助。 最后，就灵活性而言，我们将需要从VM系统中获取更多信息。 具体来说，我们希望程序能够以任意方式使用其地址空间，从而使系统更易于编程。因此，我们得出了精要的关键问题：我们如何建立有效的内存虚拟化？ 我们如何提供应用程序所需的灵活性？ 我们如何保持对应用程序可以访问哪些内存位置的控制，从而确保适当限制应用程序的内存访问？ 我们如何有效地完成所有这些工作？
我们将使用的通用技术是有限直接执行的通用方法的补充，它被称为基于硬件的地址转换，或者简称为地址转换。 借助地址转换，硬件将转换每个存储器访问（例如，取指令，加载或存储指令），将指令提供的虚拟地址更改为所需信息实际所在的物理地址。 因此，在每个内存引用上，硬件都会执行地址转换，以将应用程序内存引用重定向到它们在内存中的实际位置。
当然，仅硬件本身不能虚拟化内存，因为它只是提供了低级机制来有效地进行虚拟化。 操作系统必须在关键点介入以设置硬件，以便进行正确的转换。 因此，它必须管理内存，跟踪哪些位置空闲以及正在使用哪些位置，并明智地进行干预以保持对内存使用方式的控制。
所有这些工作的目标再次是营造一种美好的幻想：该程序具有自己的私有内存，并且自己的代码和数据驻留在该内存中。虚拟现实的背后隐藏着丑陋的物理事实：当一个或多个CPU在运行一个程序与运行另一个程序之间切换时，许多程序实际上在同时共享内存。通过虚拟化，该操作系统（在硬件的帮助下）将丑陋的机器现实变成了有用，强大且易于使用的抽象。
假设条件
具体来说，我们现在假设用户的地址空间必须连续放置在物理内存中。 为了简单起见，我们还将假定地址空间的大小不是太大； 具体来说，它小于物理内存的大小。 最后，我们还将假定每个地址空间的大小完全相同。 如果这些假设听起来不切实际，请不要担心； 我们将在使用过程中放松它们，从而实现逼真的内存虚拟化。
一个例子
为了更好地理解实现地址转换我们需要做的事情以及为什么需要这种机制，我们来看一个简单的例子。 想象有一个进程的地址空间如图15.1所示。 我们将在这里检查的是一个简短的代码序列，该序列从内存中加载一个值，将其增加三，然后将该值存储回内存中。 您可以想象此代码的C语言表示形式可能如下所示：
|
|
编译器将这一行代码转换为汇编，可能看起来像这样（在x86汇编中）。在Linux上使用objdump或在Mac上使用otool进行反汇编：
|
|
该代码段相对简单。 假定x的地址已放置在寄存器ebx中，然后使用movl指令（用于“ longword”移动）将该地址的值加载到通用寄存器eax中。 下一条指令将eax加3，最后一条指令将eax中的值存储在同一位置的内存中。
在图15.1中，观察代码和数据在流程的地址空间中的布局方式； 三指令代码序列位于地址128（在顶部附近的代码部分）中，变量x的值位于地址15 KB（在底部附近的栈中）。在图中，x的初始值为3000，如其在栈中的位置所示。
当这些指令运行时，从过程的角度来看，将进行以下内存访问。
- 在地址128处取指令
- 执行此指令（从地址15 KB加载）
- 在地址132取指令
- 执行该指令（无存储器引用）
- 在地址135取指令
- 执行该指令（存储到地址15 KB）
从程序的角度来看，其地址空间从地址0开始，最大增加到16 KB； 它生成的所有内存引用都应在这些范围之内。 但是，为了虚拟化内存，OS希望将进程放置在物理内存中的其他位置，而不必放在地址0上。因此，我们遇到了一个问题：如何以一种对进程透明的方式将该进程重新放置在内存中？ 当地址空间实际上位于其他物理地址时，我们如何提供从0开始的虚拟地址空间的错觉？
在图15.2中找到了一个示例，该示例的地址空间放置在内存中后，物理内存的外观将如何。在图中，您可以看到OS本身使用了物理内存的第一个插槽，并且它已将上述示例中的过程重新定位到从32 KB物理内存地址开始的插槽中。 其他两个插槽是空闲的（16 KB - 32 KB 和 48 KB - 64 KB）。
动态（基于硬件）重定位
为了对基于硬件的地址转换有一定的了解，我们将首先讨论其第一代产品。 在1950年代末期的第一台分时机中引入了一个简单的概念，即基准和边界。 该技术也称为动态重定位； 我们将两个术语互换使用。
具体来说，我们在每个CPU中需要两个硬件寄存器：一个称为基址寄存器，另一个称为边界寄存器（有时称为限制寄存器）。 这对寄存器将使我们能够将地址空间放置在物理内存中所需的任何位置，并确保进程只能访问自己的地址空间。
在这种设置中，每个程序都被编写和编译，就好像加载到地址零一样。 但是，当程序开始运行时，操作系统会决定将其加载到物理内存中的哪个位置，并将基址寄存器设置为该值。 在上面的示例中，操作系统决定将进程加载到32 KB的物理地址，因此将基址寄存器设置为该值。
进程运行时，有趣的事情开始发生。现在，当进程生成任何内存引用时，处理器将以以下方式对其进行转换：
|
|
进程生成的每个内存引用都是一个虚拟地址。硬件又将基址寄存器的内容添加到该地址，结果是可以发布给存储系统的物理地址。
为了更好地理解这一点，让我们追溯执行一条指令时发生的情况。具体来说，让我们看一下先前序列中的一条指令：
|
|
程序计数器（PC）设置为128； 当硬件需要提取此指令时，它首先将该值加到32 KB（32768）的基址寄存器值中，以得到32896的物理地址； 然后，硬件从该物理地址获取指令。 接下来，处理器开始执行指令。 然后，在某个时候，该过程从虚拟地址15 KB发出负载，处理器将其加载，并再次添加到基址寄存器（32 KB），从而获得47 KB的最终物理地址，从而获得所需的内容。
将虚拟地址转换为物理地址正是我们称为地址转换的技术。 也就是说，硬件获取进程认为正在引用的虚拟地址，并将其转换为数据实际驻留的物理地址。 因为地址的这种重定位发生在运行时，并且因为即使进程开始运行后我们也可以移动地址空间，所以该技术通常称为动态重定位。
基于硬件的动态重定位：使用动态重定位，只需少量硬件即可。 即，基址寄存器用于将虚拟地址（由程序生成）转换为物理地址。 边界（或限制）寄存器确保此类地址在地址空间的范围内。 它们一起提供了简单有效的内存虚拟化。
硬件支持：总结
现在让我们总结一下硬件所需的支持。 首先，正如有关CPU虚拟化的章节所讨论的，我们需要两种不同的CPU模式。 操作系统以特权模式（或内核模式）运行，在该模式下，它可以访问整个计算机。 应用程序在用户模式下运行，在此模式下他们只能做有限制的操作。 单个位（可能存储在某种处理器状态字中）指示CPU当前正在运行的模式。 在某些特殊场合（例如系统调用或某种其他类型的异常或中断），CPU会切换模式。
动态重定位：硬件要求
| 硬件要求 | 笔记 |
|---|---|
| 特权模式(内核态) | 需要防止用户模式进程执行特权操作 |
| 基数/边界寄存器 | 每个CPU需要一对寄存器来支持地址转换和边界检查 |
| 能够翻译虚拟地址并检查是否在范围内 | 进行翻译和检查限制的电路 |
| 特权指令以更新基数/界限 | 操作系统必须能够设置这些值，然后才能运行用户程序 |
| 注册异常处理程序的特权指令 | 如果发生异常，则操作系统必须能够告诉硬件要运行什么代码 |
| 提出例外的能力 | 当进程尝试访问特权指令或越界内存时 |
硬件还必须自己提供基址和边界寄存器。 因此，每个CPU都有另外一对寄存器，它们是CPU的**内存管理单元（MMU）**的一部分。 当用户程序运行时，硬件将通过将基值添加到用户程序生成的虚拟地址中来转换每个地址。 硬件还必须能够检查地址是否有效，这可以通过使用边界寄存器和CPU中的某些电路来完成。
硬件应提供特殊指令来修改基址和界限寄存器，从而允许OS在运行不同进程时更改它们。 这些指令具有特权。 仅在内核（或特权）模式下才能修改寄存器。 想象一下，如果用户进程在运行时可以任意更改基址寄存器，那么它可能会造成严重破坏。 想象一下！ 然后迅速将这些黑暗的想法从您的脑海中冲洗掉，因为它们是制造噩梦的可怕东西。
最后，在用户程序试图非法访问内存（地址“超出范围”）的情况下，CPU必须能够生成异常。 在这种情况下，CPU应该停止执行用户程序，并安排OS“越界”异常处理程序运行。 然后，操作系统处理程序可以弄清楚如何做出反应，在这种情况下，可能会终止进程。 同样，如果用户程序试图更改（特权）基数和界限寄存器的值，则CPU应引发异常并运行“在用户模式下尝试执行特权操作”处理程序。 CPU还必须提供一种方法来通知这些处理程序的位置。 因此，需要更多特权指令。
操作系统问题
正如硬件提供了支持动态重定位的新功能一样，OS现在也必须处理新的问题。 硬件支持和OS管理的结合导致实现了简单的虚拟内存。 具体来说，在一些关键时刻，操作系统必须介入以实现我们的虚拟内存基础版本。
首先，操作系统必须在创建进程时采取措施，在内存中为其地址空间找到空间。 幸运的是，假设我们每个地址空间（a）小于物理内存的大小，并且（b）相同的大小，那么对于OS来说这很容易； 它可以简单地将物理内存视为一组插槽，并跟踪每个插槽是空闲的还是正在使用的。 创建新进程时，操作系统将必须搜索数据结构（通常称为自由列表）以找到用于新地址空间的空间，然后将其标记为已使用。 使用可变大小的地址空间，生活会更加复杂，但是我们将在以后的章节中继续关注该问题。
动态重定位：操作系统职责
| 操作系统要求 | 笔记 |
|---|---|
| 内存管理 | 需要为新进程分配内存； 从终止的进程中回收内存； 通常通过空闲列表管理内存 |
| 基础/边界管理 | 在上下文切换时必须正确设置基准/边界 |
| 异常处理 | 在出现异常时运行的代码； 可能的行动是终止违规程序 |
让我们来看一个例子。 在图15.2中，您可以看到OS本身使用了物理内存的第一个插槽，并且它已将上述示例中的过程重新定位到从32 KB物理内存地址开始的插槽中。 其他两个插槽是空闲的（16 KB-32 KB和48 KB64 KB）； 因此，空闲列表应包含这两个条目。
其次，操作系统必须在进程终止时（即，它正常退出或由于行为不当而被强制杀死）做一些工作，回收其所有内存以供其他进程或操作系统使用。 进程终止后，操作系统将其内存放回空闲列表，并根据需要清除所有关联的数据结构。
第三，发生上下文切换时，操作系统还必须执行一些其他步骤。 毕竟，每个CPU上只有一对基址和边界寄存器，并且它们的值对于每个正在运行的程序都是不同的，因为每个程序都加载到内存中不同的物理地址。 因此，操作系统必须在进程之间进行切换时保存并恢复“基限对”。 具体地说，当OS决定停止运行某个进程时，它必须以某种按进程的结构（例如，进程结构或进程控制块（PCB））将基址和边界寄存器的值保存到内存中。 类似地，当OS恢复正在运行的进程（或第一次运行它）时，它必须将CPU的基数和边界值设置为此过程的正确值。
我们应该注意的是，当进程停止（即未运行）时，操作系统可能很容易将地址空间从内存中的一个位置移动到另一个位置。 要移动进程的地址空间，操作系统首先需要对进程进行调度。 然后，操作系统将地址空间从当前位置复制到新位置； 最后，操作系统会更新已保存的基址寄存器（在过程结构中）以指向新位置。 恢复该过程后，将恢复其（新的）基本寄存器，并再次开始运行，而不必担心其指令和数据现在位于内存中的全新位置。
第四，操作系统必须提供异常处理程序或要调用的功能，如上所述。 操作系统会在引导时（通过特权说明）安装这些处理程序。 例如，如果某个进程试图访问其边界之外的内存，则CPU将引发异常；否则，CPU将引发异常。 操作系统必须准备好在出现此类异常时采取措施。 操作系统的普遍反应将是敌意之一：它可能会终止违规程序。 操作系统应该对正在运行的计算机进行高度保护，因此，它对于尝试访问内存或执行不应执行的指令的过程没有帮助。 再见，行为异常； 很高兴认识您。
图15.5和15.6说明了时间轴上的许多硬件/操作系统交互。 第一个图显示了操作系统在引导时为准备使用机器所做的工作，第二个图显示了当进程（进程A）开始运行时发生的情况。 请注意，在没有操作系统干预的情况下，硬件如何处理其内存转换。 在某个时间点（第二个数字的中间），发生计时器中断，并且操作系统切换到进程B，该进程执行“错误的加载”（到非法的内存地址）。 到那时，操作系统必须参与进来，终止进程并通过释放B的内存并将其条目从进程表中删除来进行清理。 从图中可以看出，我们仍然遵循有限直接执行的基本方法。 在大多数情况下，操作系统只是适当地设置硬件，然后让进程直接在CPU上运行； 仅当流程异常时，才必须介入操作系统。
总结
在本章中，我们通过虚拟内存中使用的一种称为地址转换的特定机制扩展了有限直接执行的概念。 通过地址转换，OS可以控制进程中的每个内存访问，从而确保访问保持在地址空间的范围内。 这项技术效率的关键是硬件支持，它可以为每次访问快速执行转换，将虚拟地址（进程的内存视图）转换为物理地址（实际的视图）。 所有这些都以对已重定位的流程透明的方式执行； 该过程不知道其内存引用正在被翻译，从而产生了奇妙的幻想。
我们还看到了一种特殊的虚拟化形式，称为基础和边界或动态重定位。 基本边界虚拟化非常有效，因为只需要一点硬件逻辑就可以将基本寄存器添加到虚拟地址并检查进程生成的地址是否在边界。 上下限也提供保护； OS和硬件相结合，以确保没有进程可以在其自己的地址空间之外生成内存引用。 保护无疑是操作系统最重要的目标之一。 没有它，操作系统将无法控制机器（如果进程可以自由地覆盖内存，则它们可以轻松地执行令人讨厌的事情，例如覆盖陷阱表并接管系统）。
不幸的是，这种简单的动态重定位技术确实没有效率。 例如，如您在图15.2（第5页）中所看到的，重定位的过程正在使用32 KB到48 KB的物理内存； 但是，由于进程堆栈和堆不是太大，因此两者之间的所有空间都被浪费掉了。 这种类型的浪费通常称为内部碎片，因为分配单元内部的空间并没有全部用完（即被碎片化），因此被浪费了。 在我们目前的方法中，尽管可能有足够的物理内存用于更多进程，但我们目前仅限于将地址空间放置在固定大小的插槽中，因此可能会产生内部碎片。 因此，我们将需要更复杂的机制，以尝试更好地利用物理内存并避免内部碎片。 我们的第一个尝试是对基数和范围进行细微的概括，即分割，我们将在下面讨论。
作业
16、分段
到目前为止，我们已经将每个进程的整个地址空间放入内存中。 借助基数和边界寄存器，操作系统可以轻松地将进程重定位到物理内存的不同部分。 但是，您可能已经注意到了有关我们这些地址空间的一些有趣信息：在堆栈和堆之间的中间有一大块“可用”空间。
尽管进程没有使用堆栈和堆之间的空间，但是当我们将整个地址空间重新放置在物理内存中的某个位置时，它仍在占用物理内存。 因此，使用基数和边界寄存器对来虚拟化内存的简单方法很浪费内存的。 当整个地址空间都无法容纳到内存中时，这也使得运行程序变得非常困难。 因此，基数和界限并不像我们所希望的那样灵活。
分段：广义基址/边界
为了解决这个问题，一个想法诞生了，它被称为分段。 这是一个很老的想法，至少可以追溯到1960年代初期。 这个想法很简单：为什么在我们的MMU中不仅有一对基址/边界寄存器对，而且为什么每个地址空间的逻辑段都没有基址/边界寄存器对？ 段只是特定长度的地址空间的连续部分，在我们的规范地址空间中，我们具有三个逻辑上不同的段：代码，栈和堆。 分段允许操作系统执行的操作是将这些分段中的每个分段放置在物理内存的不同部分中，从而避免用未使用的虚拟地址空间填充物理内存。
让我们来看一个例子。通过每个段的基址/边界对，我们可以将每个段独立地放置在物理内存中。 例如，请参见图16.2。在那里，您看到一个64KB的物理内存，其中有代码，栈，堆三个段（为OS保留了头部的16KB）。
从图中可以看到，只有已使用的内存才在物理内存中分配了空间，因此可以容纳具有大量未使用地址空间的大型地址空间（有时称为稀疏地址空间）。
从图中可以看到，代码段位于物理地址32KB，大小为2KB，堆段位于34KB，大小为3KB。 段的大小与前面介绍的边界寄存器完全相同； 它准确地告诉硬件在该段中有多少字节有效（因此，使硬件能够确定程序何时在那些界限之外进行了非法访问）。
假设引用了虚拟地址100。 进行引用后（例如，在指令提取时），硬件会将基值添加到此段的偏移量中（在这种情况下为100），以达到所需的物理地址：100 + 32KB或32868。然后它将检查该地址是否在范围之内（100小于2KB），找到该地址，然后发出对物理内存地址32868的引用。
现在，让我们看一下堆中的一个地址，虚拟地址4200。如果仅将虚拟地址4200添加到堆的底部（34KB），则会得到一个物理地址39016，这不是正确的物理地址。 我们首先要做的是将偏移量提取到堆中，即地址指向该段中的哪个字节。 因为堆从虚拟地址4KB（4096）开始，所以4200的偏移量实际上是4200减去4096或104。然后，我们将此偏移量（104）并将其添加到基址寄存器物理地址（34K）中以获得所需的结果 ：34920。
如果我们试图引用一个超出堆末尾的非法地址（即7KB或更大的虚拟地址）怎么办？ 您可以想象会发生什么：硬件检测到地址超出范围，陷入操作系统，可能导致违规进程终止。现在您知道了所有C程序员都学过的著名术语的起源：分段违规或分段错误。
我们指的是哪个分段？
硬件在转换期间使用段寄存器。如何知道一个段的偏移量，以及地址指向哪个段？
一种常见的方法（有时称为显式方法）是根据虚拟地址的前几位将地址空间划分为多个段。此技术已在VAX/VMS系统中使用。在上面的示例中，我们分为三个部分：因此，我们需要两位来完成我们的任务。如果我们使用14位虚拟地址的高两位选择该段，则我们的虚拟地址如下所示：
然后，在我们的示例中，如果高两位为00，则硬件知道虚拟地址在代码段中，因此使用代码库和代码对将地址重新定位到正确的物理位置。 如果高两位为01，则硬件知道地址在堆中，因此使用堆的基数和边界。让我们以上面的示例堆虚拟地址（4200）为例，并对其进行转换，以确保其清晰可见。可以在此处看到二进制形式的虚拟地址4200：
从图片中可以看到，高两位（01）告诉硬件我们所指的是哪个段。最低的12位是段中的偏移量：0000 0110 1000，或十六进制0x068，或十进制104。因此，硬件仅使用前两位来确定要使用的段寄存器，然后将接下来的12位用作段中的偏移量。通过将基址寄存器添加到偏移量，硬件将到达最终的物理地址。请注意，偏移量也使边界检查变得容易：我们可以简单地检查偏移量是否小于边界；因此，只需检查偏移量即可。如果不是，则该地址是非法的。
您可能还已经注意到，当我们使用前两位时，并且只有三个段（代码，堆，栈），地址空间的一个段没有使用。 为了充分利用虚拟地址空间（并避免使用未使用的段），某些系统将代码与堆放在同一段中，因此仅使用一位来选择要使用的段。
使用顶部这么多的最高位来选择段的另一个问题是，它限制了虚拟地址空间的使用。具体来说，每个段都被限制为最大大小，在我们的示例中为4KB（使用前两位选择段意味着16KB的地址空间被分成四部分，在本示例中为4KB）。 如果正在运行的程序希望将某个段（例如堆或栈）扩展到该最大值以外，则该程序不走运。
硬件还有其他方法来确定特定地址位于哪个段中。在隐式方法中，硬件通过注意地址的形成方式来确定段。例如，如果该地址是从程序计数器生成的（即它是一条指令提取），则该地址在代码段之内； 如果该地址基于栈或基址指针，则它必须在栈段中；任何其他地址都必须在堆中。
栈呢？
到目前为止，我们省略了地址空间的一个重要组成部分：栈。在上图中，栈已重定位到物理地址28KB，但有一个关键的区别：它向后增长（即向较低的地址）。在物理内存中，它从28KB开始，然后增长回26KB，对应于16KB至14KB的虚拟地址。翻译必须以不同的方式进行。
我们需要的第一件事是额外的硬件支持。硬件不仅需要基值和边界值，还需要知道段增长的方式（例如，当段向正方向增长时，将其设置为1，将负方向设置为0）。
有了硬件的了解，即段可能会朝负方向增长，因此硬件现在必须稍微不同地转换此类虚拟地址。让我们以栈虚拟地址为例，并对其进行翻译以了解该过程。
在此示例中，假设我们希望访问虚拟地址15KB，该地址应映射到物理地址27KB。因此，我们的虚拟地址采用二进制形式，如下所示：11 1100 0000 0000（十六进制0x3C00）。硬件使用最高的两位（11）来指定段，但随后我们留下了3KB的偏移量。为了获得正确的负偏移，我们必须从3KB中减去最大的段大小：在此示例中，一个段可以为4KB，因此正确的负偏移为3KB减去4KB，等于-1KB。 我们只需将负偏移量（-1KB）加到基数（28KB）即可得出正确的物理地址：27KB。可以通过确保负偏移的绝对值小于或等于段的当前大小（在这种情况下为2KB）来计算边界检查。
支持分享
随着对分段的支持的增加，系统设计人员很快意识到，只要多一点硬件支持，他们就可以实现新型的效率。具体来说，为了节省内存，有时在地址空间之间共享某些内存段很有用。特别是，代码共享是常见的，并且仍在当今的系统中使用。
为了支持共享，我们需要硬件以保护位的形式提供一些额外的支持。基本支持在每个段上增加了几位，指示程序是否可以读取或写入段，或者执行段内的代码。通过将代码段设置为只读，可以在多个进程之间共享同一代码，而不必担心隔离问题。尽管每个进程仍认为自己正在访问自己的私有内存，但是OS秘密地共享了无法被进程修改的内存，因此保留了这种幻觉。
使用保护位，前面所述的硬件算法也必须更改。除了检查虚拟地址是否在范围内之外，硬件还必须检查是否允许特定访问。如果用户进程尝试写入只读段或从不可执行段执行，则硬件应引发异常，从而让OS处理有问题的进程。
细粒度与粗粒度分段
到目前为止，我们的大多数示例都集中在只有几个段（即代码，栈，堆）的系统上； 我们可以认为这种分段是粗粒度的，因为它将地址空间切分为相对较大的粗块。但是，某些早期的系统（例如Multics）更灵活，并且允许地址空间由大量较小的段组成，这称为细粒度段。
支持许多段需要进一步的硬件支持，并将某种类型的段表存储在内存中。 这样的段表通常支持大量段的创建，因此使系统能够以比我们到目前为止讨论的方式更灵活的方式使用段。例如，诸如Burroughs B5000之类的早期机器已经支持数千个段，并期望编译器将代码和数据分成单独的段，然后OS和硬件将支持它们。当时的想法是，通过拥有细粒度的段，操作系统可以更好地了解正在使用的段以及哪些未使用的段，从而更有效地利用主内存。
操作系统支持
总结
分段解决了许多问题，并帮助我们构建了更有效的内存虚拟化。除了动态重定位之外，分段还可以避免地址空间逻辑段之间巨大的潜在内存浪费，从而更好地支持稀疏地址空间。它也很快，因为进行算术分段所需的操作简单且非常适合硬件。翻译的开销很小。附带的好处也出现了：代码共享。如果将代码放在单独的段中，则可能会在多个正在运行的程序之间共享该段。
但是，据我们了解，在内存中分配可变大小的段会导致一些我们需要克服的问题。如上所述，第一个是外部碎片。由于段是可变的，因此空闲内存会被切成奇数大小的片段，因此很难满足内存分配请求。可以尝试使用智能算法或定期压缩内存，但是问题是根本的，很难避免。
第二个也许是更重要的问题是，分段仍然不够灵活，无法支持我们完全通用的稀疏地址空间。 例如，如果我们在一个逻辑段中都有一个很大但稀疏使用的堆，则整个堆仍必须驻留在内存中才能被访问。换句话说，如果我们关于地址空间使用方式的模型与底层细分的支持方式完全不匹配，那么细分就不能很好地工作。因此，我们需要找到一些新的解决方案。
作业
17、空闲空间管理
在本章中，我们从对内存虚拟化的讨论中走一段弯路，以讨论任何内存管理系统的基本方面，无论是malloc库（管理进程堆的页面）还是OS本身（管理进程地址空间的某些部分）。具体来说，我们将讨论有关空闲空间管理的问题。
让我们使问题更具体。正如我们在讨论分页的概念时将看到的那样，管理可用空间肯定很容易。将您要管理的空间划分为固定大小的单元很容易；在这种情况下，您只需保留这些固定尺寸单位的列表即可；当客户端请求其中一个时，返回第一个条目。
当您管理的自由空间由大小可变的单元组成时，自由空间管理会变得更加困难（有趣）。当使用分段实现虚拟内存时，这会在用户级内存分配库（如malloc（）和free（）中）以及管理物理内存的OS中出现。无论哪种情况，存在的问题都称为外部碎片：空闲空间被切成不同大小的小碎片，因此碎片化；后续请求可能会失败，因为即使可用空间总量超过了请求的大小，也没有单个连续的空间可以满足请求。
上图显示了此问题的示例。在这种情况下，可用的总可用空间为20个字节。不幸的是，它被分成两个大小为10的块。结果，即使有20个可用字节，对15个字节的请求也将失败。因此，我们得出了本章要解决的问题。
假设条件
底层机制
基本策略
其他方法
总结
在本章中，我们讨论了最基本的内存分配器形式。这样的分配器无处不在，它链接到您编写的每个C程序，也位于管理其自身数据结构的内存的底层OS中。与许多系统一样，在构建这样的系统时需要做出很多权衡，并且您对分配给分配器的确切工作量了解得越多，您就可以做得越多，就需要对其进行优化以使其更好地适应该工作量。在现代计算机系统中，如何使快速，节省空间，可扩展的分配器能够很好地适用于各种工作负载仍然是一个持续的挑战。
作业
18、分页：简介
有时，在解决大多数空间管理问题时，操作系统会采用两种方法之一。第一种方法是将事物切成可变大小的片段，如我们在虚拟内存中的分段所见。不幸的是，该解决方案具有固有的困难。特别地，当将空间划分为不同大小的块时，空间本身可能会变得碎片化，因此随着时间的推移分配变得更具挑战性。
因此，可能值得考虑第二种方法：将空间切成固定大小的碎片。在虚拟内存中，我们称这种想法为分页，它可以追溯到早期的重要系统Atlas。我们没有将进程的地址空间划分为多个可变大小的逻辑段（例如代码，堆，栈），而是将其划分为固定大小的单元，每个单元称为一个页面。相应地，我们将物理内存视为固定大小的插槽数组，称为页帧。每一个页帧都可以包含一个虚拟内存页面。
一个简单的例子和概述
为了使这种方法更清晰，让我们以一个简单的示例进行说明。 图18.1提供了一个很小的地址空间的示例，该地址空间的总大小仅为64字节，具有四个16字节的页面（虚拟页面0、1、2和3）。 当然，实际的地址空间要大得多，通常是32位，因此是4 GB的地址空间，甚至64位。在本书中，我们经常会使用一些小例子来简化它们。
如图18.2所示，物理内存还由多个固定大小的插槽组成，在这种情况下为八个页面帧（用于128字节的物理内存，也非常小）。如您在图中所看到的，虚拟地址空间的页面已放置在整个物理内存的不同位置。 该图还显示了操作系统本身使用了一些物理内存。
就像我们将看到的那样，分页与以前的方法相比具有许多优点。可能最重要的改进将是灵活性：通过完全开发的分页方法，该系统将能够有效地支持地址空间的抽象化，而与进程如何使用地址空间无关。例如，我们不需假设堆和栈的增长方向以及如何使用它们。
另一个优点是分页提供的自由空间管理的简单性。例如，当操作系统希望将我们的微小的64字节地址空间放入八页的物理内存中时，它只会找到四个空闲页；也许操作系统为此保留了所有空闲页面的空闲列表，而只是从该列表中抢走了前四个空闲页面。在该示例中，操作系统将**地址空间（AS）**的虚拟页面0放置在物理帧3中，将AS的虚拟页面1放置在物理帧7中，将页面2放置在帧5中，并将页面3放置在帧2中。物理帧4和6当前空闲。
为了记录地址空间的每个虚拟页在物理内存中的放置位置，操作系统通常保留每个进程的数据结构，称为页表。页表的主要作用是为地址空间的每个虚拟页存储地址转换，从而使我们知道每个页在物理内存中的位置。对于我们的简单示例（图18.2），页表将具有以下四个条目：（虚拟页0 (VP 0) → 物理帧3 (PF 3)），（VP 1 → PF 7），（VP 2 → PF 5）和 （VP 3 → PF 2）。
重要的是要记住，此页表是按进程的数据结构（我们讨论的大多数页表结构都是按进程的结构；我们要谈的例外是反向页表）。 如果在上面的示例中要运行另一个进程，则操作系统将不得不为其管理一个不同的页面表，因为其虚拟页面显然映射到了不同的物理页面（对正在进行的任何共享进行模运算）。
为了转换进程生成的虚拟地址，我们必须首先将其分为两个部分：虚拟页码（VPN）和页面内的偏移量。对于此示例，由于进程的虚拟地址空间为64个字节，因此我们的虚拟地址总共需要6位（2^6 = 64）。 因此，可以将我们的虚拟地址概念化如下：
在此图中，Va5是虚拟地址的最高位，而Va0是虚拟地址的最低位。因为我们知道页面大小（16字节），所以我们可以按以下方式进一步划分虚拟地址：
在64字节的地址空间中，页面大小为16字节。 因此，我们需要能够选择4个页面，而地址的高2位恰好可以做到这一点。因此，我们有一个2位虚拟页码（VPN）。其余的位告诉我们我们感兴趣的页面字节，在这种情况下为4位。我们称其为偏移量。
当进程生成虚拟地址时，操作系统和硬件必须结合起来才能将其转换为有意义的物理地址。例如，让我们假设上面的生成的虚拟地址是21。
将“21”转换为二进制形式，我们得到“010101”，因此我们可以检查该虚拟地址，并查看其如何分解为虚拟页码（VPN）和偏移量：
因此，虚拟地址“21”在虚拟页面“01”（或1）的第5（第“0101”）字节上。使用我们的虚拟页码，我们现在可以索引我们的页表并找到虚拟页1驻留在哪个物理帧中。在页表上方，物理帧号（PFN）（有时也称为物理页号或PPN）为7（二进制111）。因此，我们可以通过用PFN替换VPN来转换此虚拟地址，然后将负载发布到物理内存（图18.3）
请注意，偏移量保持不变（即不进行翻译），因为偏移量仅告诉我们所需页面中的哪个字节。我们的最终物理地址为1110101（十进制为117），正是我们希望加载从中获取数据的位置（图18.2）。
考虑到此基本概述，我们现在可以问（并希望回答）有关分页的一些基本问题。 例如，这些页表存储在哪里？页表的典型内容是什么，表有多大？分页是否会使系统变慢？ 这些和其他令人困惑的问题至少在以下文本中得到了回答。 继续阅读！
页表存储在哪里？
页表可能变得非常大，比我们之前讨论的小段表或基/边界对要大得多。例如，想象一个典型的32位地址空间，具有4KB页面。该虚拟地址分为20位VPN和12位偏移量（请注意，对于1KB页面大小，将需要10位，而只需再增加2位即可达到4KB）。
20位VPN表示操作系统必须为每个进程管理2^20项转换（大约一百万）； 假设每个**页表条目（PTE）**需要4个字节来保存物理转换以及任何其他有用的东西，我们将为每个页表获得4MB的巨大内存！那是很大的。现在想象有100个进程正在运行：这意味着OS仅需要所有这些地址转换就需要400MB内存！即使在机器拥有千兆字节内存的现代时代，将很大一部分内存用于翻译也似乎有些疯狂，不是吗？而且，我们甚至都不会考虑这样的页表对于64位地址空间会有多大；那太可怕了，也许会完全吓到你。
由于页表太大，因此我们在MMU中没有保留任何特殊的片上硬件来存储当前正在运行的进程的页表。相反，我们将每个进程的页表存储在内存中的某个位置。现在，假设页表位于操作系统管理的物理内存中；稍后我们将看到很多OS内存本身可以被虚拟化，因此页表可以存储在OS虚拟内存中（甚至交换到磁盘上），但是现在太混乱了，因此我们将其忽略。 图18.4（第5页）中显示了OS内存中的页表。在那里看到很小的翻译吗？
页面表中实际上是什么？
分页：太慢
内存跟踪
总结
我们引入了分页的概念来解决我们虚拟化内存的挑战。与以前的方法（例如分段）相比，分页具有许多优势。首先，它不会导致外部碎片，因为分页（根据设计）将内存分为固定大小的单元。其次，它非常灵活，可以稀疏使用虚拟地址空间。
但是，不加注意地实现分页支持将导致机器速度变慢（具有许多额外的内存访问权来访问页表）以及内存浪费（内存被页表填充，而不是有用的应用程序数据）。因此，我们将不得不更加努力地想出一种不仅有效而且可以很好运行的分页系统。幸运的是，接下来的两章将向我们展示如何做到这一点。