计算机科 学 丛书 华章较育 P Pearson 原书第3版 深人理解计算机系统 兰德尔E.布莱恩特(Randal E.Bryant) 【关] 卡内基-御降人学 大卫R.奥哈拉伦(David R.O'Hallaron) 卡内基-降人学 龚奕利贷连译 Computer Systems A Programmer's Perspective Third Edition THIRD EDITION COMPUTER SYSTEMS A PROGRAMMER'S PERSPECTIVE BRYANT·O'HALLARON 机械工业出版社 China Machine Press
作者简介 兰德尔E.布莱恩特 (Randal E.Bryant) 1981年于麻省理工学院获得计算机博士学位， 1984年至今一直任教于卡内基-梅隆大学。现任卡 内基一梅隆大学计算机科学学院院长、教授，同时 还受邀任教于电子和计算机工程系。他从事本科生 和研究生计算机系统方面课程的教学近40年。他和 O'Hallaron教授一起在卡内基-梅隆大学开设了15- 213课程“计算机系统导论”，该课程即为本书的基 础。他还是ACM院士、IEEE院士、美国国家工程院 院士和美国人文与科学研究院院士。其研究成果被 Intel、.IBM、Fujitsu和Microsoft等主要计算机制造商 使用，他还因研究获得过Semiconductor Research Corporation、ACM、IEEE颁发的多项大奖。 大卫R.奥哈拉伦 David R.O'Hallaron 卡内基-梅隆大学电子和计算机工程系教授。 在弗吉尼亚大学获得计算机科学的博士学位，2007 年一2010年为Intel匹兹堡实验室主任。他教授本科 生和研究生的计算机系统方面的课程已有20余年， 并和Bryanta教授一起开设了“计算机系统导论”课 程。曾获得CMU计算机学院颁发的Herbert Simon杰 出教学奖。他主要从事计算机系统领域的研究，与 Quake:项目成员一起获得过高性能计算领域中的最高 国际奖项Gordon Bell奖。他目前的工作重点是 研究自动分级(autograding)概念，即评价其他程 序质量的程序
书（简称CS:APP)的主要读者是计算机科学家、计算机工程师，以及 那些想通过学习计算机系统的内在运作而能够写出更好程序的人。 我们的目的是解释所有计算机系统的本质概念，并向你展示这些概 念是如何实实在在地影响应用程序的正确性、性能和实用性的。其他的 系统类书籍都是从构建者的角度来写的，讲述如何实现硬件或系统软件， 包括操作系统、编译器和网络接口。而本书是从程序员的角度来写的， 讲述应用程序员如何能够利用系统知识来编写出更好的程序。当然，学 习一个计算机系统应该做些什么，是学习如何构建一个计算机系统的很 好的出发点，所以，对于希望继续学习系统软硬件实现的人来说，本书 也是一本很有价值的介绍性读物。大多数系统书籍还倾向于重点关注系 统的某一个方面，比如：硬件架构、操作系统、编译器或者网络。本书 前 则以程序员的视角统一覆盖了上述所有方面的内容。 如果你研究和领会了这本书里的概念，你将开始成为极少数的“牛 言 人”，这些“牛人”知道事情是如何运作的，也知道当事情出现故障时如 何修复。你写的程序将能够更好地利用操作系统和系统软件提供的功能， 对各种操作条件和运行时参数都能正确操作，运行起来更快，并能避免出 现使程序容易受到网络攻击的缺陷。同时，你也要做好更深人探究的准备， 研究像编译器、计算机体系结构、操作系统、嵌人式系统、网络互联和网络 安全这样的高级题目。 读者应具备的背景知识 本书的重点是执行x8664机器代码的系统。对英特尔及其竞争对手而 言，x86-64是他们自1978年起，以8086微处理器为代表，不断进化的最新 成果。按照英特尔微处理器产品线的命名规则，这类微处理器俗称为“x86”。 随着半导体技术的演进，单芯片上集成了更多的晶体管，这些处理器的计算 能力和内存容量有了很大的增长。在这个过程中，它们从处理16位字，发展 到引入IA32处理器处理32位字，再到最近的x8664处理64位字。 我们考虑的是这些机器如何在Liux操作系统上运行C语言程序。 Linux是众多继承自最初由贝尔实验室开发的Unix的操作系统中的一种。 这类操作系统的其他成员包括Solaris、FreeBSD和MacOS X。近年来
XII 由于Posix和标准Ux规范的标准化努力，这些操作系统保持了高度兼容性。因此，本书内 容几乎直接适用于这些“类Unix”操作系统。 文中包含大量已在Liux系统上编译和运行过的程序示例。我们假设你能访问一台这样的 机器，并且能够登录，做一些诸如切换目录之类的简单操作。如果你的计算机运行的是M crosoft Windows系统，我们建议你选择安装一个虚拟机环境（例如VirtualBox或者VMWare), 以便为一种操作系统（客户(OS)编写的程序能在另一种系统（宿主OS)上运行。 我们还假设你对C和C++有一定的了解。如果你以前只有Java经验，那么你需要付出更 多的努力来完成这种转换，不过我们也会帮助你。Java和C有相似的语法和控制语句。不过， 有一些C语言的特性（特别是指针、显式的动态内存分配和格式化I/O)在Java中都是没有的。 所幸的是，C是一个较小的语言，在Brian Kernighan和Dennis Ritchie经典的“K&R”文献中 得到了清晰优美的描述[61]。无论你的编程背景如何，都应该考虑将K&R作为个人系统藏书 的一部分。如果你只有使用解释性语言的经验，如Python、Ruby或Perl,那么在使用本书之 前，需要花费一些时间来学习C。 本书的前几章揭示了C语言程序和它们相对应的机器语言程序之间的交互作用。机器语言 示例都是用运行在x86-64处理器上的GNU GCC编译器生成的。我们不需要你以前有任何硬 件、机器语言或是汇编语言编程的经验。 给C语言初学者关于0编程语言的建议 为了帮助C语言编程背景薄弱（或全无背景）的读者，我们在书中加入了这样一些专门的 注释来突出C中一些特别重要的特性。我们假设你熟悉C++或Java。 如何阅读此书 从程序员的角度学习计算机系统是如何工作的会非常有趣，主要是因为你可以主动地做这 件事情。无论何时你学到一些新的东西，都可以马上试验并且直接看到运行结果。事实上，我 们相信学习系统的唯一方法就是做(do)系统，即在真正的系统上解决具体的问题，或是编写和 运行程序。 这个主题观念贯穿全书。当引人一个新概念时，将会有一个或多个练习题紧随其后，你应 该马上做一做来检验你的理解。这些练习题的解答在每章的末尾。当你阅读时，尝试自己来解 答每个问题，然后再查阅答案，看自己的答案是否正确。除第1章外，每章后面都有难度不同 的家庭作业。对每个家庭作业题，我们标注了难度级别： ·只需要几分钟。几乎或完全不需要编程
XIII ·可能需要将近20分钟。通常包括编写和测试一些代码。（许多都源自我们在考试中出 的题目。) 幸需要很大的努力，也许是1一2个小时。一般包括编写和测试大量的代码。 :一个实验作业，需要将近10个小时。 文中每段代码示例都是由经过GCC编译的C程序直接生成并在Liux系统上进行了测试， 没有任何人为的改动。当然，你的系统上GCC的版本可能不同，或者根本就是另外一种编译 器，那么可能生成不一样的机器代码，但是整体行为表现应该是一样的。所有的源程序代码都 可以从csapp.cs.cmu.edu上的CS:APP主页上获取。在本书中，源程序的文件名列在两条水平线的 右边，水平线之间是格式化的代码。比如，图1中的程序能在code/intro/目录下的hello.c文件中找 到。当遇到这些示例程序时，我们鼓励你在自己的系统上试着运行它们。 code/intro/hello.c 1 #include 2 int main() 4 printf("hello,world\n"); 6 return 0; code/intro/hello.c 图1一个典型的代码示例 为了避免本书体积过大、内容过多，我们添加了许多网络旁注(Web aside),包括一些对 本书主要内容的补充资料。本书中用CHAP:TOP这样的标记形式来引用这些旁注，这里 CHAP是该章主题的缩写编码，而T(OP是涉及的话题的缩写编码。例如，网络旁注DATA: BOOL包含对第2章中数据表示里面有关布尔代数内容的补充资料：而网络旁注ARCH: VLOG包含的是用Verilog硬件描述语言进行处理器设计的资料，是对第4章中处理器设计部 分的补充。所有的网络旁注都可以从CS:APP的主页上获取。 旁注什么是旁注 在整本书中，你将会通到很多以这种形式出现的旁注。旁注是附加说明，能使你对当前 讨论的主题多一些了解。旁注可以有很多用处。一些是小的历史故事。例如，C语言、 Linux和Internet是从何而来的？有些旁注则是用来澄清学生们经常感到疑惑的问题。例如， 高速缓存的行、组和块有什么区别？还有些旁注给出了一些现实世界的例子。例如，一个浮 点错误怎么毁掉了法国的一枚火箭，或是给出市面上出售的一个磁盘驱动器的几何和运行参 数。最后，还有一些旁注仅仅就是一些有趣的内容，例如，什么是“hoinky'”?
XIV 本书概述 本书由12章组成，旨在阐述计算机系统的核心概念。内容概述如下： ●第1章：计算机系统漫游。这一章通过研究“hello,world'”这个简单程序的生命周期， 介绍计算机系统的主要概念和主题。 ·第2章：信息的表示和处理。我们讲述了计算机的算术运算，重点描述了会对程序员有 影响的无符号数和数的补码表示的特性。我们考虑数字是如何表示的，以及由此确定对 于一个给定的字长，其可能编码值的范围。我们探讨有符号和无符号数字之间类型转换 的效果，还阐述算术运算的数学特性。菜鸟级程序员经常很惊奇地了解到（用补码表示的） 两个正数的和或者积可能为负。另一方面，补码的算术运算满足很多整数运算的代数特 性，因此，编译器可以很安全地把一个常量乘法转化为一系列的移位和加法。我们用C 语言的位级操作来说明布尔代数的原理和应用。我们从两个方面讲述了EEE标准的浮点 格式：一是如何用它来表示数值，一是浮点运算的数学属性。 对计算机的算术运算有深刻的理解是写出可靠程序的关键。比如，程序员和编译器 不能用表达式(x-y<0)来替代(×<y),因为前者可能会产生溢出。甚至也不能用表达式 (-y<-x)来替代，因为在补码表示中负数和正数的范围是不对称的。算术溢出是造成程 序错误和安全漏洞的一个常见根源，然而很少有书从程序员的角度来讲述计算机算术运 算的特性。 ●第3章：程序的机器级表示。我们教读者如何阅读由C编译器生成的x86-64机器代码。 我们说明为不同控制结构（比如条件、循环和开关语句）生成的基本指令模式。我们还讲述 过程的实现，包括栈分配、寄存器使用惯例和参数传递。我们讨论不同数据结构（如结构、 联合和数组)的分配和访问方式。我们还说明实现整数和浮点数算术运算的指令。我们还 以分析程序在机器级的样子作为途径，来理解常见的代码安全漏洞（例如缓冲区溢出），以 及理解程序员、编译器和操作系统可以采取的减轻这些威胁的措施。学习本章的概念能 够帮助读者成为更好的程序员，因为你们懂得程序在机器上是如何表示的。另外一个好 处就在于读者会对指针有非常全面而具体的理解。 ●第4章：处理器体系结构。这一章讲述基本的组合和时序逻辑元素，并展示这些元素如 何在数据通路中组合到一起，来执行x86-64指令集的一个称为“Y86-64”的简化子集。 我们从设计单时钟周期数据通路开始。这个设计概念上非常简单，但是运行速度不会太 快。然后我们引入流水线的思想，将处理一条指令所需要的不同步骤实现为独立的阶段。 这个设计中，在任何时刻，每个阶段都可以处理不同的指令。我们的五阶段处理器流水 线更加实用。本章中处理器设计的控制逻辑是用一种称为HCL的简单硬件描述语言来描 述的。用HCL写的硬件设计能够编译和链接到本书提供的模拟器中，还可以根据这些设计
XV 生成Verilog描述，它适合合成到实际可以运行的硬件上去。 ●第5章：优化程序性能。在这一章里，我们介绍了许多提高代码性能的技术，主要思想 就是让程序员通过使编译器能够生成更有效的机器代码来学习编写C代码。我们一开始 介绍的是减少程序需要做的工作的变换，这些是在任何机器上写任何程序时都应该遵循 的。然后讲的是增加生成的机器代码中指令级并行度的变换，因而提高了程序在现代 “超标量”处理器上的性能。为了解释这些变换行之有效的原理，我们介绍了一个简单 的操作模型，它描述了现代乱序处理器是如何工作的，然后给出了如何根据一个程序的 图形化表示中的关键路径来测量一个程序可能的性能。你会惊讶于对C代码做一些简单 的变换能给程序带来多大的速度提升。 ·第6章：存储器层次结构。对应用程序员来说，存储器系统是计算机系统中最直接可见 的部分之一。到目前为止，读者一直认同这样一个存储器系统概念模型，认为它是一个 有一致访问时间的线性数组。实际上，存储器系统是一个由不同容量、造价和访问时间 的存储设备组成的层次结构。我们讲述不同类型的随机存取存储器(RAM)和只读存储器 (R(OM),以及磁盘和固态硬盘的几何形状和组织构造。我们描述这些存储设备是如 何放置在层次结构中的，讲述访问局部性是如何使这种层次结构成为可能的。我们通 过一个独特的观点使这些理论具体化，那就是将存储器系统视为一个“存储器山”， 山脊是时间局部性，而斜坡是空间局部性。最后，我们向读者阐述如何通过改善程序 的时间局部性和空间局部性来提高应用程序的性能。 ·第7章：链接。本章讲述静态和动态链接，包括的概念有可重定位的和可执行的目 标文件、符号解析、重定位、静态库、共享目标库、位置无关代码，以及库打桩。 大多数讲述系统的书中都不讲链接，我们要讲述它是出于以下原因。第一，程序员 遇到的最令人迷惑的问题中，有一些和链接时的小故障有关，尤其是对那些大型软 件包来说。第二，链接器生成的目标文件是与一些像加载、虚拟内存和内存映射这 样的概念相关的。 。第8章：异常控制流。在本书的这个部分，我们通过介绍异常控制流（即除正常分 支和过程调用以外的控制流的变化)的一般概念，打破单一程序的模型。我们给出 存在于系统所有层次的异常控制流的例子，从底层的硬件异常和中断，到并发进程 的上下文切换，到由于接收Liux信号引起的控制流突变，到C语言中破坏栈原则 的非本地跳转。 在这一章，我们介绍进程的基本概念，进程是对一个正在执行的程序的一种抽 象。读者会学习进程是如何工作的，以及如何在应用程序中创建和操纵进程。我们 日直译应为固态驱动器，但固态硬盘一词已经被大家接受，所以沿用。一译者注
XVI 会展示应用程序员如何通过Liux系统调用来使用多个进程。学完本章之后，读者 就能够编写带作业控制的Linux shell了。同时，这里也会向读者初步展示程序的并 发执行会引起不确定的行为。 ·第9章：虚拟内存。我们讲述虚拟内存系统是希望读者对它是如何工作的以及它的特 性有所了解。我们想让读者了解为什么不同的并发进程各自都有一个完全相同的地址 范围，能共享某些页，而又独占另外一些页。我们还讲了一些管理和操纵虚拟内存的 问题。特别地，我们讨论了存储分配操作，就像标准库的malloc和free操作。阐述 这些内容是出于下面几个目的。它加强了这样一个概念，那就是虚拟内存空间只是一 个字节数组，程序可以把它划分成不同的存储单元。它可以帮助读者理解当程序包含 存储泄漏和非法指针引用等内存引用错误时的后果。最后，许多应用程序员编写自己 的优化了的存储分配操作来满足应用程序的需要和特性。这一章比其他任何一章都更 能展现将计算机系统中的硬件和软件结合起来阐述的优点。而传统的计算机体系结构 和操作系统书籍都只讲述虚拟内存的某一方面。 ●第10章：系统级I/O。我们讲述Unix I/O的基本概念，例如文件和描述符。我们 描述如何共享文件，1/O重定向是如何工作的，还有如何访问文件的元数据。我们 还开发了一个健壮的带缓冲区的I/O包，可以正确处理一种称为short counts的奇 特行为，也就是库函数只读取一部分的输入数据。我们阐述C的标准I/O库，以及 它与Linux I/O的关系，重点谈到标准I/O的局限性，这些局限性使之不适合网络 编程。总的来说，本章的主题是后面两章一网络和并发编程的基础。 ·第11章：网络编程。对编程而言，网络是非常有趣的I/O设备，它将许多我们前面 文中学习的概念（比如进程、信号、字节顺序、内存映射和动态内存分配）联系在一起。 网络程序还为下一章的主题一并发，提供了一个很令人信服的上下文。本章只是网 络编程的一个很小的部分，使读者能够编写一个简单的Wb服务器。我们还讲述位于 所有网络程序底层的客户端-服务器模型。我们展现了一个程序员对Internet的观点， 并且教读者如何用套接字接口来编写Internet客户端和服务器。最后，我们介绍超文 本传输协议(HTTP),并开发了一个简单的迭代式Web服务器。 ●第l2章：并发编程。这一章以Internet服务器设计为例介绍了并发编程。我们比较 对照了三种编写并发程序的基本机制（进程、I/O多路复用和线程），并且展示如何用 它们来建造并发Internet服务器。我们探讨了用P、V信号量操作来实现同步、线程 安全和可重人、竞争条件以及死锁等的基本原则。对大多数服务器应用来说，写并发 代码都是很关键的。我们还讲述了线程级编程的使用方法，用这种方法来表达应用程 序中的并行性，使得程序在多核处理器上能执行得更快。使用所有的核解决同一个计 算问题需要很小心谨慎地协调并发线程，既要保证正确性，又要争取获得高性能
XVII 本版新增内容 本书的第1版于2003年出版，第2版在2011年出版。考虑到计算机技术发展如此迅速， 这本书的内容还算是保持得很好。事实证明Intel x86的机器上运行Linux(以及相关操作系 统)，加上采用C语言编程，是一种能够涵盖当今许多系统的组合。然而，硬件技术、编译 器和程序库接口的变化，以及很多教师教授这些内容的经验，都促使我们做了大量的修改。 第2版以来的最大整体变化是，我们的介绍从以IA32和x86-64为基础，转变为完全 以x86-64为基础。这种重心的转移影响了很多章节的内容。下面列出一些明显的变化： ●第1章。我们将第5章对Amdahl定理的讨论移到了本章。 ·第2章。读者和评论家的反馈是一致的，本章的一些内容有点令人不知所措。因 此，我们澄清了一些知识点，用更加数学的方式来描述，使得这些内容更容易理 解。这使得读者能先略过数学细节，获得高层次的总体概念，然后回过头来进行更 细致深入的阅读。 ●第3章。我们将之前基于IA32和x86-64的表现形式转换为完全基于x86-64,还更 新了近期版本GCC产生的代码。其结果是大量的重写工作，包括修改了一些概念 提出的顺序。同时，我们还首次介绍了对处理浮点数据的程序的机器级支持。由于 历史原因，我们给出了一个网络旁注描述IA32机器码。 ·第4章。我们将之前基于32位架构的处理器设计修改为支持64位字和操作的设计。 .·第5章。我们更新了内容以反映最近几代x86-64处理器的性能。通过引入更多的功 能单元和更复杂的控制逻辑，我们开发的基于程序数据流表示的程序性能模型，其 性能预测变得比之前更加可靠。 ·第6章。我们对内容进行了更新，以反映更多的近期技术。 ·第7章。针对x86-64,我们重写了本章，扩充了关于用GOT和PLT创建位置无关 代码的讨论，新增了一节描述更加强大的链接技术，比如库打桩。 ·第8章。我们增加了对信号处理程序更细致的描述，包括异步信号安全的函数，编写 信号处理程序的具体指导原则，以及用sigsuspend等待处理程序。 ·第9章。本章变化不大。 ·第10章。我们新增了一节说明文件和文件的层次结构，除此之外，本章的变化 不大。 ●第ll章。我们介绍了采用最新getaddrinfo和getnameinfo函数的、与协议无 关和线程安全的网络编程，取代过时的、不可重人的gethostbyname和gethost byaddr函数
XVIII ●第12章。我们扩充了利用线程级并行性使得程序在多核机器上更快运行的内容。 此外，我们还增加和修改了很多练习题和家庭作业。 本书的起源 本书起源于1998年秋季，我们在卡内基-梅隆(CMU)大学开设的一门编号为15-213 的介绍性课程：计算机系统导论(Introduction to Computer System,ICS)[l4]。从那以 后，每学期都开设了ICS这门课程，每学期有超过400名学生上课，这些学生从本科二年 级到硕士研究生都有，所学专业也很广泛。这门课程是卡内基一梅隆大学计算机科学系 (CS)以及电子和计算机工程系(ECE)所有本科生的必修课，也是CS和ECE大多数高级 系统课程的先行必修课。 ICS这门课程的宗旨是用一种不同的方式向学生介绍计算机。因为，我们的学生中几 乎没有人有机会亲自去构造一个计算机系统。另一方面，大多数学生，甚至包括所有的计 算机科学家和计算机工程师，也需要日常使用计算机和编写计算机程序。所以我们决定从 程序员的角度来讲解系统，并采用这样的原则过滤要讲述的内容：我们只讨论那些影响用 户级C语言程序的性能、正确性或实用性的主题。 比如，我们排除了诸如硬件加法器和总线设计这样的主题。虽然我们谈及了机器语 言，但是重点并不在于如何手工编写汇编语言，而是关注C语言编译器是如何将C语言的 结构翻译成机器代码的，包括编译器是如何翻译指针、循环、过程调用以及开关(switch) 语句的。更进一步地，我们将更广泛和全盘地看待系统，包括硬件和系统软件，涵盖了包 括链接、加载、进程、信号、性能优化、虚拟内存、1/O以及网络与并发编程等在内的 主题。 这种做法使得我们讲授ICS课程的方式对学生来讲既实用、具体，还能动手操作，同 时也非常能调动学生的积极性。很快地，我们收到来自学生和教职工非常热烈而积极的反 响，我们意识到卡内基-梅隆大学以外的其他人也可以从我们的方法中获益。因此，这本 书从ICS课程的笔记中应运而生了，而现在我们对它做了修改，使之能够反映科学技术以 及计算机系统实现中的变化和进步。 通过本书的多个版本和多种语言译本，ICS和许多相似课程已经成为世界范围内数百 所高校的计算机科学和计算机工程课程的一部分。 写给指导教师们：可以基于本书的课程 指导教师可以使用本书来讲授五种不同类型的系统课程（见图2）。具体每门课程则有