操作系统导论-OSTEP (王海鹏 译) (z-library.sk, 1lib.sk, z-lib.sk)

前 言 致本书读者 欢迎阅读本书！我们希望你阅读本书时，就像我们撰写它时一样开心。本书的英文书 名为《Operating Systems:Three Easy Pieces》，这显然是向理查德·费曼（Richard Feynman） 针对物理学主题创作的、最了不起的一套讲义[F96]致敬。虽然本书不能达到这位著名物理 学家设定的高标准，但也许足够让你了解什么是操作系统（以及更一般的系统）。 本书围绕 3 个主题元素展开讲解：虚拟化（virtualization）、并发（concurrency）和持久 性（persistence）。对于这些概念的讨论，最终延伸到讨论操作系统所做的大多数重要事情。 希望你在这个过程中体会到一些乐趣。学习新事物很有趣，对吧？ 每个主要概念在若干章节中加以阐释，其中大部分章节都提出了一个特定的问题，然 后展示了解决它的方法。这些章节很简短，尝试（尽可能地）引用作为这些想法真正来源 的源材料。我们写这本书的目的之一就是厘清操作系统的发展脉络，因为我们认为这有助 于学生更清楚地理解过去是什么、现在是什么、将来会是什么。在这种情况下，了解香肠 的制作方法几乎与了解香肠的优点一样重要。 我们在整本书中采用了几种结构，值得在这里介绍一下。 无论何时，在试图解决问题时，我们首先要说明最重要的问题是什么。我们在书中明 确提出关键问题（crux of the problem），并希望通过本书其余部分提出的技术、算法和思 想来解决。 在许多地方，我们将通过显示一段时间内的行为来解释系统的工作原理。这些时间线 （timeline）是理解的本质。如果你知道会发生什么，例如，当进程出现页故障时，你就可以 真正了解虚拟内存的运行方式。如果你理解日志文件系统将块写入磁盘时发生的情况，就 已经迈出了掌握存储系统的第一步。 整本书中有许多“补充”和“提示”，为主线讲解增添了一些趣味性。“补充”倾向于 讨论与主要文本相关的内容（但可能不是必要的）；“提示”往往是一般经验，可以应用于 所构建的系统。 在整本书中，我们使用最古老的教学方法之一——对话（dialogue）。这些对话用于介绍 主要的主题概念，并不时地复习这些内容。这也让我们得以用更幽默的方式写作。好吧， 你觉得它们是有用还是幽默，完全是另一回事。 在每一个主要部分的开头，我们将首先呈现操作系统提供的抽象（abstraction），然后在 后续章节中介绍提供抽象所需的机制、策略和其他支持。抽象是计算机科学各个方面的基 础，因此它在操作系统中也是必不可少的。

2 前 言 在所有的章节中，我们尝试使用可能的真实代码（real code），而非伪代码（pseudocode）。 因此书中几乎所有的示例，你应该能够自己输入并运行它们。在真实系统上运行真实代码 是了解操作系统的最佳方式，因此建议你尽可能这样做。 在本书的各个部分，我们提供了一些作业（homework），确保你进一步理解书中的内容。 其中许多作业都是对操作系统的一些模拟（simulation）程序。你应该下载作业，并运行它 们，以此来测验自己。作业模拟程序具有以下特征：通过给它们提供不同的随机种子，你 可以产生几乎无限的问题，也可以让模拟程序为你解决问题。因此，你可以一次又一次地 自测，直至很好地理解了这些知识。 本书最重要的附录是一组项目（project），可供你通过设计、测试和实现自己的代码， 来了解真实系统的工作原理。所有项目（以及上面提到的代码示例）都是使用 C 编程语言 （C programming language）[KR88]编写的。C 是一种简单而强大的语言，是大多数操作系统 的基础，因此值得添加到你的工具库中。附录中含有两种类型的项目（请参阅在线附录中 的想法）。第一类是系统编程（system programming）项目。这些项目非常适合那些不熟悉 C 和 UNIX，并希望学习如何进行底层 C 编程的人。第二类基于在麻省理工学院开发的实际操 作系统内核，称为 xv6 [CK+08]。这些项目非常适合已经有一些 C 的经验并希望深入研究操 作系统的学生。在威斯康星大学，我们以 3 种不同的方式开课：系统编程、xv6 编程，或两 者兼而有之。 致使用本书作为教材的教师 这门课程很适合 15 周的学期，因此授课教师可以在合理的深度范围内讲授大部分主题。 如果是 10 周的学期，那么可能需要从每个部分中删除一些细节。还有一些章节是关于虚拟 机监视器的，我们通常会在学期的某个时候插入这些章节，或者在虚拟化部分的结尾处， 抑或在接近课程结束时作为补充。 本书中的并发主题比较特别。它是许多操作系统书籍中靠前的主题，而在本书中是直 到学生了解了 CPU 和内存的虚拟化之后才开始讲解的。根据我们近 15 年来教授本课程的经 验，学生很难理解并发问题是如何产生的，或者很难理解人们试图解决它的原因。那是因 为他们还不了解地址空间是什么、进程是什么，或者为什么上下文切换可以在任意时间点 发生。然而，一旦他们理解了这些概念，那么再引入线程的概念和由此产生的问题就变得 相当容易，或者至少比较容易。 我们尽可能使用黑板（或白板）来讲课。在着重强调概念的时候，我们会将一些主要 的想法和例子带进课堂，并在黑板上展示它们。讲义有助于为学生提供需要解决的具体问 题。在着重强调实践的时候，我们就将笔记本电脑连上投影仪，展示实际代码。这种授课 风格特别适用于并发的内容以及所有的讨论部分。在这些部分中，教师可以向学生展示与 其项目相关的代码。我们通常不使用幻灯片来讲课，但现在我们已经为那些喜欢这种演示 风格的人提供了一套教学 PPT。 如果你想要任何这些教学辅助材料，请给 contact@epubit.com.cn 发电子邮件。 最后一个请求：如果你使用免费在线章节，请直接访问作者网站。这有助于我们跟踪

前 言 3 使用情况（过去几年中，本书英文版下载超过 100 万次！），并确保学生获得最新和最好的 版本。 致使用本书上课的学生 如果你是读这本书的学生，那么我们很荣幸能够提供一些材料来帮助你学习操作系统的 知识。我们至今还能够回想起我们使用过的一些教科书（例如，Hennessy 和 Patterson 的著作 [HP90]，这是一本关于计算机架构的经典著作），并希望这本书能够成为你美好的回忆之一。 你可能已经注意到，这本书英文版的在线版本是免费的，并且可在线获取①。有一个 主要原因：教科书一般都太贵了。我们希望，这本书是新一波免费材料中的第一本（指电 子版），以帮助那些寻求知识的人—— 无论他们来自哪个国家，或者他们愿意花多少钱购 买一本书。 我们也希望，在可能的情况下，向你指出书中大部分材料的原始资料—— 多年来的优 秀论文和人物，他们让操作系统领域成为现在的样子。想法不会凭空产生，它们来自聪明 勤奋的人（包括众多图灵奖获得者②），因此如果有可能，我们应该赞美这些想法和人。我 们希望这样做能有助于更好地理解已经发生的变革，而不是说好像我们写这本书时那些思 想一直就存在一样[K62]。此外，也许这样的参考文献能够鼓励你深入挖掘，而阅读该领域 的著名论文无疑是良好的学习方法之一。 致谢 这里感谢帮助我们编写本书的人。重要的是，你的名字可以出现在这里！但是，你必 须提供帮助。请向我们发送一些反馈，帮助完善本书。你可能会出名！或者，至少在某本 书中有你的名字。 到目前为止，提供帮助的人包括 Abhirami Senthilkumaran*, Adam Drescher* (WUSTL), Adam Eggum, Aditya Venkataraman, Adriana Iamnitchi and class (USF), Ahmed Fikri*, Ajaykrishna Raghavan, Akiel Khan, Alex Wyler, Ali Razeen (Duke), AmirBehzad Eslami, Anand Mundada, Andrew Valencik (Saint Mary’s), Angela Demke Brown (Toronto), B. Brahmananda Reddy (Minnesota), Bala Subrahmanyam Kambala, Benita Bose, Biswajit Mazumder (Clemson), Bobby Jack, Björn Lindberg, Brennan Payne, Brian Gorman, Brian Kroth, Caleb Sumner (Southern Adventist), Cara Lauritzen, Charlotte Kissinger, Chien-Chung Shen (Delaware)*, Christoph Jaeger, Cody Hanson, Dan Soendergaard (U. Aarhus), David Hanle (Grinnell), David Hartman, Deepika Muthukumar, Dheeraj Shetty (North Carolina State), Dorian Arnold (New ① 这里的题外话：我们在这里所说的“免费”并不意味着开源，也不意味着该书没有受到通常保护的版权——它是受到保护的！ 我们的意思是你可以下载章节，并使用它们来了解操作系统。为什么不是一本开源的书，不像 Linux 一样是一个开源内核？ 当你阅读它时，这本书应该像一次对话，某人向你解释某事。因此，这就是我们的方法。 ② 图灵奖是计算机科学的最高奖项。它就像诺贝尔奖，但你可能从未听说过。

4 前 言 Mexico), Dustin Metzler, Dustin Passofaro, Eduardo Stelmaszczyk, Emad Sadeghi, Emily Jacobson, Emmett Witchel (Texas), Erik Turk, Ernst Biersack (France), Finn Kuusisto*, Glen Granzow (College of Idaho), Guilherme Baptista, Hamid Reza Ghasemi, Hao Chen, Henry Abbey, Hrishikesh Amur, Huanchen Zhang*, Huseyin Sular, Hugo Diaz, Itai Hass (Toronto), Jake Gillberg, Jakob Olandt, James Perry (U. Michigan-Dearborn)*, Jan Reineke (Universität des Saarlandes), Jay Lim, Jerod Weinman (Grinnell), Jiao Dong (Rutgers), Jingxin Li, Joe Jean (NYU), Joel Kuntz (Saint Mary’s), Joel Sommers (Colgate), John Brady (Grinnell), Jonathan Perry (MIT), Jun He, Karl Wallinger, Kartik Singhal, Kaushik Kannan, Kevin Liu*, Lei Tian (U. Nebraska-Lincoln), Leslie Schultz, Liang Yin, Lihao Wang, Martha Ferris, Masashi Kishikawa (Sony), Matt Reichoff, Matty Williams, Meng Huang, Michael Walfish (NYU), Mike Griepentrog, Ming Chen (Stonybrook), Mohammed Alali (Delaware), Murugan Kandaswamy, Natasha Eilbert, Nathan Dipiazza, Nathan Sullivan, Neeraj Badlani (N.C. State), Nelson Gomez, Nghia Huynh (Texas), Nick Weinandt, Patricio Jara, Perry Kivolowitz, Radford Smith, Riccardo Mutschlechner, Ripudaman Singh, Robert Ordòñez and class (Southern Adventist), Rohan Das (Toronto)*, Rohan Pasalkar (Minnesota), Ross Aiken, Ruslan Kiselev, Ryland Herrick, Samer Al-Kiswany, Sandeep Ummadi (Minnesota), Satish Chebrolu (NetApp), Satyanarayana Shanmugam*, Seth Pollen, Sharad Punuganti, Shreevatsa R., Sivaraman Sivaraman*, Srinivasan Thirunarayanan*, Suriyhaprakhas Balaram Sankari, Sy Jin Cheah, Teri Zhao (EMC), Thomas Griebel, Tongxin Zheng, Tony Adkins, Torin Rudeen (Princeton), Tuo Wang, Varun Vats, William Royle (Grinnell), Xiang Peng, Xu Di, Yudong Sun, Yue Zhuo (Texas A&M), Yufui Ren, Zef RosnBrick, Zuyu Zhang。特别感谢上面标有星号的人，他们的改进建议尤其重要。 此外，衷心感谢 Joe Meehean 教授（Lynchburg）为每一章所做的详细注解，感谢 Jerod Weinman 教授（Grinnell）和他的全班同学提供的令人难以置信的小册子，感谢 Chien-Chung Shen 教授（Delaware）的细致阅读和建议，感谢 Adam Drescher（WUSTL）的细致阅读和 建议，感谢 Glen Granzow（College of Idaho）提供详细的评论和建议，感谢 Michael Walfish （NYU）详细的改进建议。上述所有人都给予本书作者巨大的帮助，优化了本书的内容。 另外，非常感谢这些年来参加 537 课程的数百名学生。特别是 2008 年秋季课程的学生， 鼓励我们第一次以书面形式写下了这些讲义（他们厌倦了没有任何类型的教科书可读——有 进取心的学生！），然后不吝称赞，让我们继续前行（一位同学在那一年的课程评估中喜不 自禁地说：“老天爷！你们完全应该写一本教科书！” ）。 我们也非常感谢那些参加 xv6 项目实验课程的少数人，这个实验课程大部分现已纳入 主要的 537 课程。2009 年春季班的 Justin Cherniak，Patrick Deline，Matt Czech，Tony Gregerson，Michael Griepentrog，Tyler Harter，Ryan Kroiss，Eric Radzikowski，Wesley Reardan， Rajiv Vaidyanathan 和 Christopher Waclawik。2009 年秋季班的 Nick Bearson，Aaron Brown， Alex Bird，David Capel，Keith Gould，Tom Grim，Jeffrey Hugo，Brandon Johnson，John Kjell， Boyan Li，James Loethen，Will McCardell，Ryan Szaroletta，Simon Tso 和 Ben Yule。2010 年春季班的 Patrick Blesi，Aidan Dennis-Oehling，Paras Doshi，Jake Friedman，Benjamin Frisch， Evan Hanson，Pikkili Hemanth，Michael Jeung，Alex Langenfeld，Scott Rick，Mike Treffert， Garret Staus，Brennan Wall，Hans Werner，Soo -Young Yang 和 Carlos Griffin。

前 言 5 虽然没有直接帮助这本书的写作，但我们的研究生教会了我们很多关于系统的知识。 我们在威斯康星大学时经常与他们交谈，并且所有真正的工作都是他们做的——通过告诉我 们他们在做什么，我们每周都能学习到新事物。下面的列表包括我们已发布论文的当前和 以前的学生，带有星号标志的名字是在我们的指导下获得博士学位的人：Abhishek Rajimwale，Andrew Krioukov，Ao Ma，Brian Forney，Chris Dragga，Deepak Ramamurthi， Florentina Popovici *，Haryadi S. Gunawi *，James Nugent，John Bent *，Jun He，Lanyue Lu， Lakshmi Bairavasundaram * ，Laxman Visampalli，Leo Arulraj，Meenali Rungta，Muthian Sivathanu *，Nathan Burnett *，Nitin Agrawal *，Ram Alagappan，Sriram Subramanian *，Stephen Todd Jones *，Suli Yang，Swaminathan Sundararaman*，Swetha Krishnan，Thanh Do*， Thanumalayan S. Pillai，Timothy Denehy*，Tyler Harter，Venkat Venkataramani，Vijay Chidambaram，Vijayan Prabhakaran *，Yiyi Zhang *，Yupu Zhang *，Zev Weiss。 最后要感谢 Aaron Brown，他多年前（2009 年春季）首次参加该课程，接着参加了 xv6 实 验课程（2009 年秋季），最后还成为了两个课程的研究生助教（从 2010 年秋季到 2012 年春季）。 他不知疲倦的工作极大地改善了项目的状态（特别是 xv6 项目），因此有助于改善威斯康星大学 无数本科生和研究生的学习体验。正如 Aaron 所说的（以他通常的简洁方式）：“谢谢。” 最后的话 叶芝有一句名言：“教育不是注满一桶水，而是点燃一把火。”他说得既对也错①。你必 须“给桶注一点水”，这本书当然可以帮助你完成这部分的教育。毕竟，当你去 Google 面试 时，他们会问你一个关于如何使用信号量的技巧问题，确切地知道信号量是什么感觉真好， 对吧？ 但是，叶芝的主要观点显而易见：教育的真正要点是让你对某些事情感兴趣，可以独 立学习更多关于这个主题的东西，而不仅仅是你需要消化什么才能在某些课程上取得好成 绩。正如我们的父亲（雷姆兹的父亲 Vedat Arpaci）曾经说过的，“在课堂以外学习。” 我们编写本书以激发你对操作系统的兴趣，让你能自行阅读有关该主题的更多信息，进而 与你的教授讨论该领域正在进行的所有令人兴奋的研究，甚至参与这些研究。这是一个伟大的 领域，充满了激动人心和精妙的想法，以深刻而重要的方式塑造了计算历史。虽然我们知道这 种火不会为你们所有人点燃，但我们希望这能对许多人，甚至是少数人有所帮助。因为一旦火 被点燃，那你就真正有能力做出伟大的事情。因此，教育过程的真正意义在于：前进，学习许 多新的和引人入胜的主题，通过学习不断成熟，最重要的是，找到能为你点火的东西。② 威斯康星大学计算机科学教授 雷姆兹和安德莉亚夫妇 ① 如果他真的说了这句话。与许多名言一样，这句名言的历史也是模糊不清的。 ② 如果这听起来像我们承认过去曾是纵火犯，那你可能理解错了。如果这听起来很俗气，好吧，因为它确实是的，但你必须原 谅我们。

6 前 言 参考资料 [CK+08]“The xv6 Operating System”Russ Cox, Frans Kaashoek, Robert Morris, Nickolai Zeldovich. xv6 是作为原来 UNIX 版本 6 的移植版开发的，它代表了通过一种美观、干净、简单的方式来理解现 代操作系统。 [F96]“Six Easy Pieces: Essentials Of Physics Explained By Its Most Brilliant Teacher”Richard P. Feynman Basic Books, 1996 这本书摘取了 1993 年的《费曼物理学讲义》中 6 个最简单的章节。如果你喜欢物理学，那么就读一 读这本很优秀的读物吧。 [HP90]“Computer Architecture a Quantitative Approach”(1st ed.) David A. Patterson and John L. Hennessy Morgan-Kaufman, 1990 在读本科时，这本书成为了我们去攻读研究生的动力。我们后来都很高兴与 Patterson 合作，他为我们 研究事业基础的奠定给予了极大的帮助。 [KR88]“The C Programming Language”Brian Kernighan and Dennis Ritchie Prentice-Hall, April 1988 每个人都应该拥有一本由发明该语言的人编写的 C 编程参考书。 [K62]“The Structure of Scientific Revolutions”Thomas S. Kuhn University of Chicago Press, 1962 这是关于科学过程基础知识的著名读物，包括科学过程的整理工作、异常、危机和变革。我们要做的 是整理工作。

目 录 第 1 章 关于本书的对话 ............................... 1 第 2 章 操作系统介绍 .................................... 3 2.1 虚拟化 CPU.......................................... 4 2.2 虚拟化内存 .......................................... 6 2.3 并发 ...................................................... 7 2.4 持久性................................................... 9 2.5 设计目标 ............................................ 11 2.6 简单历史 ............................................ 12 2.7 小结..................................................... 15 参考资料...................................................... 15 第 1 部分 虚拟化 第 3 章 关于虚拟化的对话 ......................... 18 第 4 章 抽象：进程 ...................................... 19 4.1 抽象：进程 ........................................ 20 4.2 进程 API ............................................. 20 4.3 进程创建：更多细节 ........................ 21 4.4 进程状态 ............................................ 22 4.5 数据结构 ............................................ 24 4.6 小结 .................................................... 25 参考资料 ..................................................... 25 作业 ........................................................... 26 问题 ........................................................... 26 第 5 章 插叙：进程 API ............................. 28 5.1 fork()系统调用 ................................... 28 5.2 wait()系统调用 ................................... 29 5.3 最后是 exec()系统调用 ..................... 30 5.4 为什么这样设计 API......................... 32 5.5 其他 API ............................................. 34 5.6 小结 .................................................... 34 参考资料 ..................................................... 34 作业（编码） ............................................. 35 问题 ........................................................... 35 第 6 章 机制：受限直接执行..................... 37 6.1 基本技巧：受限直接执行 ................ 37 6.2 问题 1：受限制的操作 ..................... 38 6.3 问题 2：在进程之间切换 ................. 40 6.4 担心并发吗 ........................................ 44 6.5 小结 .................................................... 45 参考资料 ..................................................... 45 作业（测量）.............................................. 47 第 7 章 进程调度：介绍.............................. 48 7.1 工作负载假设 .................................... 48 7.2 调度指标 ............................................ 49 7.3 先进先出（FIFO）............................ 49 7.4 最短任务优先（SJF） ...................... 50 7.5 最短完成时间优先（STCF） ........... 51 7.6 新度量指标：响应时间 .................... 52 7.7 轮转..................................................... 52 7.8 结合 I/O .............................................. 54 7.9 无法预知 ............................................ 54 7.10 小结................................................... 55 参考资料...................................................... 55 作业 ............................................................ 56 问题 ............................................................ 56 第 8 章 调度：多级反馈队列..................... 57 8.1 MLFQ：基本规则 ............................. 57 8.2 尝试 1：如何改变优先级 ................. 58 8.3 尝试 2：提升优先级 ......................... 60 8.4 尝试 3：更好的计时方式 ................. 61 8.5 MLFQ 调优及其他问题 .................. 61 8.6 MLFQ：小结 ..................................... 62 参考资料...................................................... 63 作业 ............................................................ 64 问题 ............................................................ 64 第 9 章 调度：比例份额.............................. 65 9.1 基本概念：彩票数表示份额 ............ 65 9.2 彩票机制 ............................................ 66

2 目 录 9.3 实现 .................................................... 67 9.4 一个例子 ............................................ 68 9.5 如何分配彩票 .................................... 68 9.6 为什么不是确定的 ............................ 69 9.7 小结 .................................................... 70 参考资料 ..................................................... 70 作业 ........................................................... 71 问题 ........................................................... 71 第 10 章 多处理器调度（高级）.............. 73 10.1 背景：多处理器架构 ...................... 73 10.2 别忘了同步 ...................................... 75 10.3 最后一个问题：缓存亲和度 .......... 76 10.4 单队列调度 ...................................... 76 10.5 多队列调度 ...................................... 77 10.6 Linux 多处理器调度 ....................... 79 10.7 小结 .................................................. 79 参考资料 ..................................................... 79 第 11 章 关于 CPU 虚拟化的总结对话 .. 81 第 12 章 关于内存虚拟化的对话.............. 83 第 13 章 抽象：地址空间 ........................... 85 13.1 早期系统 .......................................... 85 13.2 多道程序和时分共享 ...................... 85 13.3 地址空间 .......................................... 86 13.4 目标 .................................................. 87 13.5 小结 .................................................. 89 参考资料 ..................................................... 89 第 14 章 插叙：内存操作 API .................. 91 14.1 内存类型 .......................................... 91 14.2 malloc()调用 ..................................... 92 14.3 free()调用.......................................... 93 14.4 常见错误 .......................................... 93 14.5 底层操作系统支持 .......................... 96 14.6 其他调用 .......................................... 97 14.7 小结 .................................................. 97 参考资料 ..................................................... 97 作业（编码） ............................................. 98 问题 ........................................................... 98 第 15 章 机制：地址转换 ......................... 100 15.1 假设 ................................................ 101 15.2 一个例子 ........................................ 101 15.3 动态（基于硬件）重定位 ............ 103 15.4 硬件支持：总结 ............................ 105 15.5 操作系统的问题 .......................... 105 15.6 小结................................................. 108 参考资料.................................................... 109 作业 .......................................................... 110 问题 .......................................................... 110 第 16 章 分段 ............................................... 111 16.1 分段：泛化的基址/界限 ............... 111 16.2 我们引用哪个段 ............................ 113 16.3 栈怎么办 ........................................ 114 16.4 支持共享 ........................................ 114 16.5 细粒度与粗粒度的分段 ................ 115 16.6 操作系统支持 ................................ 115 16.7 小结................................................. 117 参考资料.................................................... 117 作业 .......................................................... 118 问题 .......................................................... 119 第 17 章 空闲空间管理.............................. 120 17.1 假设................................................. 120 17.2 底层机制 ........................................ 121 17.3 基本策略 ........................................ 126 17.4 其他方式 ........................................ 128 17.5 小结................................................. 130 参考资料.................................................... 130 作业 .......................................................... 131 问题 .......................................................... 131 第 18 章 分页：介绍 .................................. 132 18.1 一个简单例子 ................................ 132 18.2 页表存在哪里 ................................ 134 18.3 列表中究竟有什么 ........................ 135 18.4 分页：也很慢 ................................ 136 18.5 内存追踪 ........................................ 137 18.6 小结................................................. 139 参考资料.................................................... 139 作业 .......................................................... 140 问题 .......................................................... 140 第 19 章 分页：快速地址转换（TLB）... 142 19.1 TLB 的基本算法 ............................ 142

目 录 3 19.2 示例：访问数组 ............................ 143 19.3 谁来处理 TLB 未命中 ................... 145 19.4 TLB 的内容 .................................... 146 19.5 上下文切换时对 TLB 的处理....... 147 19.6 TLB 替换策略 ................................ 149 19.7 实际系统的 TLB 表项 ................... 149 19.8 小结 ................................................ 150 参考资料 ................................................... 151 作业（测量） ........................................... 152 问题 ......................................................... 153 第 20 章 分页：较小的表 ......................... 154 20.1 简单的解决方案：更大的页 ........ 154 20.2 混合方法：分页和分段 ................ 155 20.3 多级页表 ........................................ 157 20.4 反向页表 ........................................ 162 20.5 将页表交换到磁盘 ........................ 163 20.6 小结 ................................................ 163 参考资料 ................................................... 163 作业 ......................................................... 164 问题 ......................................................... 164 第 21 章 超越物理内存：机制 ................ 165 21.1 交换空间 ........................................ 165 21.2 存在位 ............................................ 166 21.3 页错误 ............................................ 167 21.4 内存满了怎么办 ............................ 168 21.5 页错误处理流程 ............................ 168 21.6 交换何时真正发生 ........................ 169 21.7 小结................................................. 170 参考资料.................................................... 171 第 22 章 超越物理内存：策略 ................ 172 22.1 缓存管理 ........................................ 172 22.2 最优替换策略 ................................ 173 22.3 简单策略：FIFO............................ 175 22.4 另一简单策略：随机 .................... 176 22.5 利用历史数据：LRU .................... 177 22.6 工作负载示例 ................................ 178 22.7 实现基于历史信息的算法 ............ 180 22.8 近似 LRU ....................................... 181 22.9 考虑脏页 ........................................ 182 22.10 其他虚拟内存策略 ...................... 182 22.11 抖动............................................... 183 22.12 小结............................................... 183 参考资料.................................................... 183 作业 .......................................................... 185 问题 .......................................................... 185 第 23 章 VAX/VMS 虚拟内存系统........ 186 23.1 背景................................................. 186 23.2 内存管理硬件 ................................ 186 23.3 一个真实的地址空间 .................... 187 23.4 页替换............................................. 189 23.5 其他漂亮的虚拟内存技巧 ............ 190 23.6 小结................................................. 191 参考资料.................................................... 191 第 24 章 内存虚拟化总结对话 ................ 193 第 2 部分 并发 第 25 章 关于并发的对话 ......................... 196 第 26 章 并发：介绍 .................................. 198 26.1 实例：线程创建 ............................ 199 26.2 为什么更糟糕：共享数据 ............ 201 26.3 核心问题：不可控的调度 ............ 203 26.4 原子性愿望 .................................... 205 26.5 还有一个问题：等待另一个 线程 ................................................ 206 26.6 小结：为什么操作系统课要研究 并发 ................................................ 207 参考资料.................................................... 207 作业 .......................................................... 208 问题 .......................................................... 208 第 27 章 插叙：线程 API ......................... 210 27.1 线程创建 ........................................ 210 27.2 线程完成 ........................................ 211 27.3 锁..................................................... 214 27.4 条件变量 ........................................ 215 27.5 编译和运行 .................................... 217 27.6 小结................................................. 217

4 目 录 参考资料 ................................................... 218 第 28 章 锁.................................................... 219 28.1 锁的基本思想 ................................ 219 28.2 Pthread 锁 ....................................... 220 28.3 实现一个锁 .................................... 220 28.4 评价锁 ............................................ 220 28.5 控制中断 ........................................ 221 28.6 测试并设置指令（原子交换） .... 222 28.7 实现可用的自旋锁 ........................ 223 28.8 评价自旋锁 .................................... 225 28.9 比较并交换 .................................... 225 28.10 链接的加载和条件式存储指令 .. 226 28.11 获取并增加................................... 228 28.12 自旋过多：怎么办 ...................... 229 28.13 简单方法：让出来吧，宝贝 ...... 229 28.14 使用队列：休眠替代自旋 .......... 230 28.15 不同操作系统，不同实现 .......... 232 28.16 两阶段锁 ...................................... 233 28.17 小结 .............................................. 233 参考资料 ................................................... 233 作业 ......................................................... 235 问题 ......................................................... 235 第 29 章 基于锁的并发数据结构............ 237 29.1 并发计数器 .................................... 237 29.2 并发链表 ........................................ 241 29.3 并发队列 ........................................ 244 29.4 并发散列表 .................................... 245 29.5 小结 ................................................ 246 参考资料 ................................................... 247 第 30 章 条件变量 ...................................... 249 30.1 定义和程序 .................................... 250 30.2 生产者/消费者（有界缓冲区） 问题 ................................................ 252 30.3 覆盖条件 ........................................ 260 30.4 小结................................................. 261 参考资料.................................................... 261 第 31 章 信号量 ........................................... 263 31.1 信号量的定义 ................................ 263 31.2 二值信号量（锁） ........................ 264 31.3 信号量用作条件变量 .................... 266 31.4 生产者/消费者（有界缓冲区） 问题................................................. 268 31.5 读者—写者锁 ................................ 271 31.6 哲学家就餐问题 ............................ 273 31.7 如何实现信号量 ............................ 275 31.8 小结................................................. 276 参考资料.................................................... 276 第 32 章 常见并发问题.............................. 279 32.1 有哪些类型的缺陷 ........................ 279 32.2 非死锁缺陷 .................................... 280 32.3 死锁缺陷 ........................................ 282 32.4 小结................................................. 288 参考资料.................................................... 289 第 33 章 基于事件的并发（进阶） ....... 291 33.1 基本想法：事件循环 .................... 291 33.2 重要 API：select()（或 poll()） ... 292 33.3 使用 select().................................... 293 33.4 为何更简单？无须锁 .................... 294 33.5 一个问题：阻塞系统调用 ............ 294 33.6 解决方案：异步 I/O ...................... 294 33.7 另一个问题：状态管理 ................ 296 33.8 什么事情仍然很难 ........................ 297 33.9 小结................................................. 298 参考资料.................................................... 298 第 34 章 并发的总结对话 ......................... 300 第 3 部分 持久性 第 35 章 关于持久性的对话..................... 302 第 36 章 I/O 设备 ....................................... 303 36.1 系统架构 ........................................ 303 36.2 标准设备 ........................................ 304 36.3 标准协议 ........................................ 304 36.4 利用中断减少 CPU 开销............... 305 36.5 利用 DMA 进行更高效的数据 传送................................................. 306

目 录 5 36.6 设备交互的方法 ............................ 307 36.7 纳入操作系统：设备驱动程序 .... 307 36.8 案例研究：简单的 IDE 磁盘驱动 程序 ................................................ 309 36.9 历史记录 ........................................ 311 36.10 小结 .............................................. 311 参考资料 ................................................... 312 第 37 章 磁盘驱动器 .................................. 314 37.1 接口 ................................................ 314 37.2 基本几何形状 ................................ 314 37.3 简单的磁盘驱动器 ........................ 315 37.4 I/O 时间：用数学 .......................... 318 37.5 磁盘调度 ........................................ 320 37.6 小结 ................................................ 323 参考资料 ................................................... 323 作业 ......................................................... 324 问题 ......................................................... 324 第 38 章 廉价冗余磁盘阵列（RAID）... 326 38.1 接口和 RAID 内部......................... 327 38.2 故障模型 ........................................ 327 38.3 如何评估 RAID.............................. 328 38.4 RAID 0 级：条带化....................... 328 38.5 RAID 1 级：镜像........................... 331 38.6 RAID 4 级：通过奇偶校验节省 空间 ................................................. 333 38.7 RAID 5 级：旋转奇偶校验........... 336 38.8 RAID 比较：总结.......................... 337 38.9 其他有趣的 RAID 问题................. 338 38.10 小结 .............................................. 338 参考资料 ................................................... 339 作业 ......................................................... 340 问题 ......................................................... 340 第 39 章 插叙：文件和目录..................... 342 39.1 文件和目录 .................................... 342 39.2 文件系统接口 ................................ 343 39.3 创建文件 ........................................ 343 39.4 读写文件 ........................................ 344 39.5 读取和写入，但不按顺序 ............ 346 39.6 用 fsync()立即写入 ........................ 346 39.7 文件重命名 .................................... 347 39.8 获取文件信息 ................................ 348 39.9 删除文件 ........................................ 349 39.10 创建目录 ...................................... 349 39.11 读取目录....................................... 350 39.12 删除目录 ...................................... 351 39.13 硬链接 .......................................... 351 39.14 符号链接 ...................................... 353 39.15 创建并挂载文件系统 .................. 354 39.16 小结............................................... 355 参考资料.................................................... 355 作业 .......................................................... 356 问题 .......................................................... 356 第 40 章 文件系统实现.............................. 357 40.1 思考方式 ........................................ 357 40.2 整体组织 ........................................ 358 40.3 文件组织：inode............................ 359 40.4 目录组织 ........................................ 363 40.5 空闲空间管理 ................................ 364 40.6 访问路径：读取和写入 ................ 364 40.7 缓存和缓冲 .................................... 367 40.8 小结................................................. 369 参考资料.................................................... 369 作业 .......................................................... 370 问题 .......................................................... 371 第 41 章 局部性和快速文件系统 ............ 372 41.1 问题：性能不佳 ............................ 372 41.2 FFS：磁盘意识是解决方案.......... 373 41.3 组织结构：柱面组 ........................ 373 41.4 策略：如何分配文件和目录 ........ 374 41.5 测量文件的局部性 ........................ 375 41.6 大文件例外 .................................... 376 41.7 关于 FFS 的其他几件事................ 377 41.8 小结................................................. 378 参考资料.................................................... 378 第 42 章 崩溃一致性：FSCK 和日志 ... 380 42.1 一个详细的例子 ............................ 380 42.2 解决方案 1：文件系统检查 程序................................................. 383 42.3 解决方案 2：日志 （或预写日志） .............................. 384

6 目 录 42.4 解决方案 3：其他方法 ................. 392 42.5 小结 ................................................ 393 参考资料 ................................................... 393 第 43 章 日志结构文件系统..................... 395 43.1 按顺序写入磁盘 ............................ 396 43.2 顺序而高效地写入 ........................ 396 43.3 要缓冲多少 .................................... 397 43.4 问题：查找 inode........................... 398 43.5 通过间接解决方案：inode 映射 .. 398 43.6 检查点区域 .................................... 399 43.7 从磁盘读取文件：回顾 ................ 400 43.8 目录如何 ........................................ 400 43.9 一个新问题：垃圾收集 ................ 401 43.10 确定块的死活 .............................. 402 43.11 策略问题：要清理哪些块， 何时清理 ....................................... 403 43.12 崩溃恢复和日志 .......................... 403 43.13 小结 .............................................. 404 参考资料 ................................................... 404 第 44 章 数据完整性和保护..................... 407 44.1 磁盘故障模式 ................................ 407 44.2 处理潜在的扇区错误 .................... 409 44.3 检测讹误：校验和 ........................ 409 44.4 使用校验和 .................................... 412 44.5 一个新问题：错误的写入 ............ 412 44.6 最后一个问题：丢失的写入 ........ 413 44.7 擦净 ................................................ 413 44.8 校验和的开销 ................................ 414 44.9 小结 ................................................ 414 参考资料 ................................................... 414 第 45 章 关于持久的总结对话 ................ 417 第 46 章 关于分布式的对话..................... 418 第 47 章 分布式系统 .................................. 419 47.1 通信基础 ........................................ 420 47.2 不可靠的通信层 ............................ 420 47.3 可靠的通信层 ................................ 422 47.4 通信抽象 ........................................ 424 47.5 远程过程调用（RPC） ................. 425 47.6 小结 ................................................ 428 参考资料.................................................... 429 第 48 章 Sun 的网络文件系统（NFS）... 430 48.1 基本分布式文件系统 .................... 430 48.2 交出 NFS ........................................ 431 48.3 关注点：简单快速的服务器崩溃 恢复................................................. 431 48.4 快速崩溃恢复的关键：无状态 .... 432 48.5 NFSv2 协议 .................................... 433 48.6 从协议到分布式文件系统 ............ 434 48.7 利用幂等操作处理服务器故障 .... 435 48.8 提高性能：客户端缓存 ................ 437 48.9 缓存一致性问题 ............................ 437 48.10 评估 NFS 的缓存一致性 ............. 439 48.11 服务器端写缓冲的隐含意义....... 439 48.12 小结............................................... 440 参考资料.................................................... 440 第 49 章 Andrew 文件系统（AFS） ..... 442 49.1 AFS 版本 1 ..................................... 442 49.2 版本 1 的问题 ................................ 443 49.3 改进协议 ........................................ 444 49.4 AFS 版本 2 ..................................... 444 49.5 缓存一致性 .................................... 446 49.6 崩溃恢复 ........................................ 447 49.7 AFSv2 的扩展性和性能 ................ 448 49.8 AFS：其他改进 ............................. 450 49.9 小结................................................. 450 参考资料.................................................... 451 作业 .......................................................... 452 问题 .......................................................... 452 第 50 章 关于分布式的总结对话 ............ 453 附录 A 关于虚拟机监视器的对话 .......... 454 附录 B 虚拟机监视器 ................................ 455 附录 C 关于监视器的对话........................ 466 附录 D 关于实验室的对话 ....................... 467 附录 E 实验室：指南 ................................ 468 附录 F 实验室：系统项目........................ 478 附录 G 实验室：xv6 项目 ........................ 480

第 1 章 关于本书的对话 教授：欢迎阅读这本书，本书英文书名为《Operating Systems:Three Easy Pieces》，由我 来讲授关于操作系统的知识。请做一下自我介绍。 学生：教授，您好，我是学生，您可能已经猜到了，我已经准备好开始学习了！ 教授：很好。有问题吗？ 学生：有！本书为什么讲“3 个简单部分”？ 教授：这很简单。理查德·费曼有几本关于物理学的讲义，非常不错…… 学生：啊，是《别闹了，费曼先生》的作者吗？那本书很棒！这书也会像那本书一样 搞笑吗？ 教授：呃……不。那本书的确很棒，很高兴你读过它。我希望这本书更像他关于物理 学的讲义。将一些基本内容汇集成一本书，名为《Six Easy Pieces》。他讲的是物理学，而我 们将探讨的主题是操作系统的 3 个简单部分。这很合适，因为操作系统的难度差不多是物 理学的一半。 学生：懂了，我喜欢物理学。是哪 3 个部分呢？ 教授：虚拟化（virtualization）、并发（concurrency）和持久性（persistence）。这是我们 要学习的 3 个关键概念。通过学习这 3 个概念，我们将理解操作系统是如何工作的，包括 它如何决定接下来哪个程序使用 CPU，如何在虚拟内存系统中处理内存使用过载，虚拟机 监控器如何工作，如何管理磁盘上的数据，还会讲一点如何构建在部分节点失败时仍能正 常工作的分布式系统。 学生：对于您说的这些，我都没有概念。 教授：好极了，这说明你来对了地方。 学生：我还有一个问题：学习这些内容最好的方法是什么？ 教授：好问题！当然，每个人都有适合自己的学习方法，但我的方法是：首先听课， 听老师讲解并做好笔记，然后每个周末阅读笔记，以便更好地理解这些概念。过一段时间 （比如考试前），再阅读一遍笔记来进一步巩固知识。当然老师也肯定会布置作业和项目， 你需要认真完成。特别是做项目，你会编写真正的代码来解决真正的问题，这是将笔记中 的概念活学活用。就像孔子说的那样…… 学生：我知道！“不闻不若闻之，闻之不若见之，见之不若知之，知之不若行之。” 教授：（惊讶）你怎么知道我要说这个？ 学生：这样似乎很连贯。我是孔子的粉丝，更是荀子的粉丝，实际上荀子才是说这句 话的人①。 ① 儒家思想家荀子曾说过：“不闻不若闻之，闻之不若见之，见之不若知之，知之不若行之。”后来，不知怎么这句名言归到了 孔子头上。感谢 Jiao Dong（Rutgers）告诉我们。

2 第 1 章 关于本书的对话 教授：（愕然）我猜我们会相处得很愉快。 学生：教授，我还有一个问题，我们这样的对话有什么用的。我是说如果这仅是一本 书，为什么您不直接上来就讲述知识呢？ 教授：好问题！我觉得有的时候将自己从叙述中抽离出来，然后进行一些思考会更 有用。这些对话就是思考。我们将协作探究所有这些复杂的概念。你是为此而来的吗？ 学生：所以我们必须思考？好的，我正是为此而来。不过我还有什么要做的吗？看起 来我好像就是为此书而生。 教授：我也是。我们开始学习吧！

2.1 虚拟化 CPU 3 第 2 章 操作系统介绍 如果你正在读本科操作系统课程，那么应该已经初步了解了计算机程序运行时做的事 情。如果不了解，这本书（和相应的课程）对你来说会很困难：你应该停止阅读本书，或 跑到最近的书店，在继续读本书之前快速学习必要的背景知识（包括 Patt / Patel [PP03 ]，特 别是 Bryant / O’Hallaron 的书[BOH10]，都是相当不错的）。 程序运行时会发生什么？ 一个正在运行的程序会做一件非常简单的事情：执行指令。处理器从内存中获取（fetch） 一条指令，对其进行解码（decode）（弄清楚这是哪条指令），然后执行（execute）它（做它 应该做的事情，如两个数相加、访问内存、检查条件、跳转到函数等）。完成这条指令后， 处理器继续执行下一条指令，依此类推，直到程序最终完成①。 这样，我们就描述了冯·诺依曼（Von Neumann）计算模型②的基本概念。听起来很简 单，对吧？但在这门课中，我们将了解到在一个程序运行的同时，还有很多其他疯狂的事 情也在同步进行——主要是为了让系统易于使用。 实际上，有一类软件负责让程序运行变得容易（甚至允许你同时运行多个程序），允许 程序共享内存，让程序能够与设备交互，以及其他类似的有趣的工作。这些软件称为操作 系统（Operating System，OS）③，因为它们负责确保系统既易于使用又正确高效地运行。 关键问题：如何将资源虚拟化 我们将在本书中回答一个核心问题：操作系统如何将资源虚拟化？这是关键问题。为什么操作系统 这样做？这不是主要问题，因为答案应该很明显：它让系统更易于使用。因此，我们关注如何虚拟化： 操作系统通过哪些机制和策略来实现虚拟化？操作系统如何有效地实现虚拟化？需要哪些硬件支持？ 我们将用这种灰色文本框来突出“关键（crux）问题”，以此引出我们在构建操作系统时试图解决 的具体问题。因此，在关于特定主题的说明中，你可能会发现一个或多个关键点（是的，cruces 是正确 的复数形式），它突出了问题。当然，该章详细地提供了解决方案，或至少是解决方案的基本参数。 要做到这一点，操作系统主要利用一种通用的技术，我们称之为虚拟化（virtualization）。 也就是说，操作系统将物理（physical）资源（如处理器、内存或磁盘）转换为更通用、更 强大且更易于使用的虚拟形式。因此，我们有时将操作系统称为虚拟机（virtual machine）。 当然，为了让用户可以告诉操作系统做什么，从而利用虚拟机的功能（如运行程序、 ① 当然，现现处理器在背后做了许多现现而可现的事情，让程序运行得更快。例如，一一执行多条指令，甚至甚序执行甚完成它 们！但这不是我们在这里关心的问题。我们只关心大多数程序所假设的简单模型：指令似乎按照有序和顺序的方式逐条执行。 ② 冯·诺依曼是计算系统的早期先驱之一。他还完成了关于博弈论和原子弹的开创性工作，甚在 NBA 打了 6 年球。好吧，其 中有一件事不是真的。 ③ 操作系统的操一个早期操称是操操程序（super visor），甚至叫主控程序（master control program）。显然，后者听起来有些过 分热情（详情请参阅电影《Tron》），因此，谢天谢地，“操作系统”最后胜出。

4 第 2 章 操作系统介绍 分配内存或访问文件），操作系统还提供了一些接口（API），供你调用。实际上，典型的操 作系统会提供几百个系统调用（system call），让应用程序调用。由于操作系统提供这些调用 来运行程序、访问内存和设备，甚进行其他相关操作，我们有时也会说操作系统为应用程 序提供了一个标准库（standard library）。 最后，因为虚拟化让许多程序运行（从而共享 CPU），让许多程序可以同时访问自己的 指令和数据（从而共享内存），让许多程序访问设备（从而共享磁盘等），所以操作系统有 时被称为资源操理器（resource manager）。每个 CPU、内存和磁盘都是系统的资源（resource）， 因此操作系统扮演的主要角色就是操理（manage）这些资源，以做到高效或公平，或者实 际上考虑其他许多可能的目标。为了更好地理解操作系统的角色，我们来看一些例子。 2.1 虚拟化 CPU 图 2.1 展示了我们的第一个程序。实际上，它没有太大的作用，它所做的只是调用 Spin() 函数，该函数会反复检查时间甚在运行一秒后返回。然后，它会打印出用户在命令行中传 入的字符串，甚一直重复这样做。 1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <sys/time.h> 4 #include <assert.h> 5 #include "common.h" 6 7 int 8 main(int argc, char *argv[]) 9 { 10 if (argc != 2) { 11 fprintf(stderr, "usage: cpu <string>\n"); 12 exit(1); 13 } 14 char *str = argv[1]; 15 while (1) { 16 Spin(1); 17 printf("%s\n", str); 18 } 19 return 0; 20 } 图 2.1 简单示例：循环打印的现码（cpu.c） 假设我们将这个文件保存为 cpu.c，甚决定在一个单处理器（或有时称为 CPU）的系统 上编译和运行它。以下是我们将看到的内容： prompt> gcc -o cpu cpu.c -Wall prompt> ./cpu "A" A A

2.1 虚拟化 CPU 5 A A ˆC prompt> 运行不太有趣：系统开始运行程序时，该程序会重复检查时间，直到一秒钟过去。一 秒钟过去后，现码打印用户传入的字符串（在本例中为字母“A”）甚继续。注意：该程序 将永远运行，只有按下“Control-c”（这在基于 UNIX 的系统上将终止在前台运行的程序）， 才能停止运行该程序。 现在，让我们做同样的事情，但这一一，让我们运行同一个程序的许多不同实例。图 2.2 展示了这个稍复杂的例子的结果。 prompt> ./cpu A & ; ./cpu B & ; ./cpu C & ; ./cpu D & [1] 7353 [2] 7354 [3] 7355 [4] 7356 A B D C A B D C A C B D ... 图 2.2 同时运行许多程序 好吧，现在事情开始变得有趣了。尽操我们只有一个处理器，但这 4 个程序似乎在同 时运行！这种魔法是如何发生的？① 事实证明，在硬件的一些帮助下，操作系统负责提供这种假象（illusion），即系统拥有 非常多的虚拟 CPU 的假象。将单个 CPU（或其中一小部分）转换为看似无限数量的 CPU， 从而让许多程序看似同时运行，这就是所谓的虚拟化 CPU（virtualizing the CPU），这是本书 第一大部分的关注点。 当然，要运行程序甚停止它们，或告诉操作系统运行哪些程序，需要有一些接口（API）， 你可以利用它们将需求传达给操作系统。我们将在本书中讨论这些 API。事实上，它们是大 多数用户与操作系统交互的主要方式。 你可能还会注意到，一一运行多个程序的能力会引发各种新问题。例如，如果两个程 ① 请注意我们如何利用& 符号同时运行 4 个进程。这样做会在 tcsh shell 的后台运行一个作业，这意味着用户能够立即发出下一 个命令，在这个例子中，是操一个运行的程序。命令之间的分号允许我们在 tcsh 中同时运行多个程序。如果你使用的是不同 的 shell（例如 bash），它的工作原理会稍有不同。关于详细信息，请阅读在线文档。

6 第 2 章 操作系统介绍 序想要在特定时间运行，应该运行哪个？这个问题由操作系统的策略（policy）来回答。在 操作系统的许多不同的地方采用了一些策略，来回答这类问题，所以我们将在学习操作系 统实现的基本机制（mechanism）（例如一一运行多个程序的能力）时研究这些策略。因此， 操作系统承担了资源操理器（resource manager）的角色。 2.2 虚拟化内存 现在让我们考虑一下内存。现现机器提供的物理内存（physical memory）模型非常简单。 内存就是一个字节数组。要读取（read）内存，必须指定一个地址（address），才能访问存储 在那里的数据。要写入（write）或更新（update）内存，还必须指定要写入给定地址的数据。 程序运行时，一直要访问内存。程序将所有数据结构保存在内存中，甚通过各种指令 来访问它们，例如加载和保存，或利用其他明确的指令，在工作时访问内存。不要忘记， 程序的每个指令都在内存中，因此每一读取指令都会访问内存。 让我们来看一个程序，它通过调用 malloc()来分配一些内存（见图 2.3）。 1 #include <unistd.h> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include "common.h" 5 6 int 7 main(int argc, char *argv[]) 8 { 9 int *p = malloc(sizeof(int)); // a1 10 assert(p != NULL); 11 printf("(%d) memory address of p: %08x\n", 12 getpid(), (unsigned) p); // a2 13 *p = 0; // a3 14 while (1) { 15 Spin(1); 16 *p = *p + 1; 17 printf("(%d) p: %d\n", getpid(), *p); // a4 18 } 19 return 0; 20 } 图 2.3 一个访问内存的程序（mem.c） 该程序的输出如下： prompt> ./mem (2134) memory address of p: 00200000 (2134) p: 1 (2134) p: 2 (2134) p: 3 (2134) p: 4 (2134) p: 5 ˆC

2.3 并发 7 该程序做了几件事。首先，它分配了一些内存（a1 行）。然后，打印出内存（a2）的地 址，然后将数字 0 放入新分配的内存（a3）的第一个空位中。最后，程序循环，延迟一秒钟 甚递增 p 中保存的地址值。在每个打印语句中，它还会打印出所谓的正在运行程序的进程 标识符（PID）。该 PID 对每个运行进程是唯一的。 同样，第一一的结果不太有趣。新分配的内存地址为 00200000。程序运行时，它慢慢 地更新值甚打印出结果。 现在，我们再一运行同一个程序的多个实例，看看会发生什么（见图 2.4）。我们从示 例中看到，每个正在运行的程序都在相同的地址（00200000）处分配了内存，但每个似乎 都独立更新了 00200000 处的值！就好像每个正在运行的程序都有自己的私有内存，而不是 与其他正在运行的程序共享相同的物理内存①。 prompt> ./mem &; ./mem & [1] 24113 [2] 24114 (24113) memory address of p: 00200000 (24114) memory address of p: 00200000 (24113) p: 1 (24114) p: 1 (24114) p: 2 (24113) p: 2 (24113) p: 3 (24114) p: 3 (24113) p: 4 (24114) p: 4 ... 图 2.4 多一运行内存程序 实际上，这正是操作系统虚拟化内存（virtualizing memory）时发生的情况。每个进程 访问自己的私有虚拟地址空间（virtual address space）（有时称为地址空间，address space）， 操作系统以某种方式映射到机器的物理内存上。一个正在运行的程序中的内存引用不会影 响其他进程（或操作系统本身）的地址空间。对于正在运行的程序，它完全拥有自己的物 理内存。但实际情况是，物理内存是由操作系统操理的共享资源。所有这些是如何完成的， 也是本书第 1 部分的主题，属于虚拟化（virtualization）的主题。 2.3 并发 本书的操一个主题是甚发（concurrency）。我们使用这个术语来指现一系列问题，这些问题 在同时（甚发地）处理很多事情时出现且必须解决。甚发问题首先出现在操作系统本身中。如 你所见，在上面关于虚拟化的例子中，操作系统同时处理很多事情，首先运行一个进程，然后 再运行一个进程，等等。事实证明，这样做会导致一些深刻而有趣的问题。 遗憾的是，甚发问题不再局限于操作系统本身。事实上，现现多线程（multi-threaded） 程序也存在相同的问题。我们来看一个多线程程序的例子（见图 2.5）。 ① 要让这个例子能工作，需要确保需用地址空间间机化。事实证明，间机化可以很好地随随某些随全随随。请自行阅读更多的 相关资料，特别是如果你想学习如何通过堆栈粉碎黑客对计算机系统的攻击入侵。我们不会推荐这样的东西……