《深入理解计算机系统》是 Computer Systems: A Programmer’s Perspective 的中文译名,缩写为 CSAPP。英文书名可以直译为“从程序员的角度来理解计算机系统”,书中内容也确实是这么设计的。为了锻炼自己的英文阅读能力,选择了阅读 CSAPP,并希望通过写作来记录阅读的收获。
组成计算机的硬件速度越来越快、容量越来越大,软件占用的内存也越来越多🙃,组成计算机的底层原理却没有改变。CSAPP 通过讲述计算机组件的基本原理来让程序员更理解他们的作品,理解为什么程序会出错,学会如何提高程序的性能。
- 通过学习计算机表示数字的方式来避免数值计算错误;
- 利用处理器和存储系统的设计原理来巧妙地优化 C 代码;
- 学习并运用编译器对过程调用的实现机制来避免缓冲区溢出;
- 理解产生链接时错误的原因;
- 并发的好处和陷阱;
- ……
CSAPP 从每个程序员的第一个程序——Hello World 开始,带读者理解整个程序从诞生、运行到结束发生的所有。
第一章,计算机系统漫游
第一章的概念比较多,所以会有一些原文的个人翻译。
信息
信息是 bits 和其所在的上下文。Bits 就是一系列二进制数(0 和 1),上下文是解读数据的方式,同一串二进制数将其解释为无符号整数时是一个数,解释为一个整数的补码时可能就是另一个数了。Bits 是数据本身,上下文能让数据产生意义。
存放 Hello World 程序源代码的文件 hello.c
由一长串的 0 和 1 组成,每 8 位 0 或1 的序列组成一个字节,每个字节表示了源代码中的一个符号。Hello World 程序源代码只包含 ASCII 字符(每个字节对应的整数值在 0-127 之间),只包含 ASCII 字符的文件称为文本文件,而包含其他字符的文件都可以叫做二进制文件。
从源代码到机器指令
源代码是用人类可读的高级程序语言编写的,要想在计算机上运行程序,需要将源代码转换成机器能执行的低级机器语言指令,这些机器指令以可执行文件的形式保存为二进制文件。
在 Unix 系统上,将源代码转换为可执行文件的过程由编译器完成。编译器从源代码生成可执行文件需要 4 个步骤:
- 预处理。预处理器(cpp)处理以
#
号开始的指令。例如include
指令告诉预处理器将指定的头文件插入到源代码中。预处理完成后,将得到以.i
为文件名后缀的文本文件。 - 编译。编译器(cc1)将
hello.i
文件翻译为汇编语言,得到hello.s
。汇编语言是所有高级程序语言编译器的通用输出语言。 - 汇编。汇编器(as)将
hello.s
翻译成机器语言指令,并将其打包成可重定位目标文件(Relocatable Object Program),生成的目标文件为hello.o
。到这里,文件已经是一个二进制文件了,如果用文本编辑器打开,只会看到无意义的符号。 - 链接。Hello World 程序调用了
printf
函数,这个函数是 C 编译器提供的标准 C 函数库的一部分。printf
函数存放在一个已预先编译的printf.o
文件中,链接器(ld)会将这个文件与hello.o
合并,得到可执行文件。可执行文件可由系统读入内存并执行。
更详细的过程会在后面的章节中讲述。
理解编译系统如何工作大有益处
对于简单如 Hello World 的程序,我们相信编译器能够生成正确又高效的机器指令。而当程序变得复杂,理解编译系统是如何工作就显得有用起来了,文中举了三方面例子。
- 提高程序性能。编译工具十分复杂,虽然在大部分情况下都能生成比较好的程序,但为了得到更为高效的程序,理解机器语言级别的代码以及编译器如何将 C 代码生成机器指令就显得十分有用。有几个例子:
switch
语句一定比if-else
高效吗?- 一次函数调用会产生多少开销?
while
循环比for
循环好吗?- 指针引用一定比数组下标高效吗?
- 在循环中使用局部变量为什么会比使用传入的引用参数更快?
- 算术表达式中如何正确排列括号以加快计算?
- 理解链接错误。在编译程序时,很有可能会遇到链接器报出的错误,特别是一个软件用到很多链接库的时候。例如下面这些问题,这些问题将在第七章讨论。
- 链接器报告不能解决引用意味着什么?
- 静态变量和全局变量有什么区别?
- 在不同的 C 文件中定义两个名字相同的全局变量会怎么样?
- 静态库和动态库有什么区别?
- 编译时在命令行列出的链接库顺序会有什么影响?
- 最奇怪是——为什么一些和链接相关的错误直到程序运行时才会出现?
- 避免安全问题。很多年来,缓冲区溢出攻击一直都会在网络服务器上发生,这是因为程序员没有认识到从不可靠数据源接收数据时限制数据长度和格式的重要性。首先需要理解数据和控制流在栈上的存储方式,而后从汇编语言层面理解程序栈的用法,才会理解缓冲区溢出的原因。为了减少缓冲区溢出攻击,要掌握在编译器和操作系统层面可以采用的应对措施。
指令的存储、执行和中断
当 Hello World 程序编译完成,它便成为了一个磁盘上的可执行文件,比如说它的文件名是 hello
。在 Unix 系统上想要运行这个程序,一般会在 Shell 中输入 ./hello
,然后会出现程序的输出 Hello,World!
。
为什么程序员的第一个程序总是 Hello World 呢?这可能是因为这个程序足够简单,可以展示一门编程语言的基本语法,也能验证编译器已经正确安装。这里可以找到比较有名有姓的五十多种计算机程序语言编写的 Hello World。
我有一个更为大胆而浪漫的想法,一个程序仿佛是一个人工智能的缩影,当这个智能程序“组装”完毕,可以运行时,就像是一个婴儿初入人间,当然要向这个世界礼貌而谦卑地打个招呼,问声好:“你好,世界!”,向世界宣告自己的降临,现在“我”可以做任何事!
在 Shell 中输入程序名来运行程序看上去理所当然,实际上 Shell 也是一个程序,它在命令行打印一个提示,等待你输入一段命令,然后执行这个命令。如果输入的命令是一个 Shell 内置的命令,那么就执行这个命令;如果不是一个内置命令,Shell 会将其解释为一个可执行程序文件名,尝试加载并运行这个程序,并等待这个程序结束。
这个理所当然的过程里发生了很多事情,是计算机软硬件数据交互的典型。
总线 Bus
计算机系统中,不同组件之间的数据传输都要经过总线。总线通常以字(Word)为数据传输单位,一个字包含的字节数是一项计算机系统的基本参数,不同计算机系统之间可能有所区别。现在大部分计算机使用的字长为 4 字节(32 位)或 8 字节(64 位)。在不明确指出字长的情况下,都使用“字”这个词来指代这个参数。
输入输出(I/O)设备
输入输出设备是计算机系统与外界联系的媒介,典型的计算机系统会有键盘、鼠标作为输入设备,显示器作为输出设备,硬盘用于长期存放数据、程序,Hello World 就存储在硬盘上。每个输入输出设备都通过对应的控制器或适配器连接到总线上。控制器是在设备上或者系统主板上的芯片组,适配器是插在主板插槽上的卡。例如鼠标、键盘直接连接到主板上,而显示器直接连接在显卡上。通过控制器和适配器,输入输出设备可以向总线传输数据,也可以从总线获取数据。
主存
主存(Main Memory),一般叫做内存,是一个临时的存取设备,只能保存处理器正在执行中的程序本身和其所需的数据。之所以是临时存储设备,是因为内存所使用的存储元件是 DRAM(Dynamic Random Access Memory),DRAM 需要周期性充电以避免数据丢失。内存在逻辑上是连续的字节数组,每个数组元素可存储 1 个字节,每个元素用唯一的地址来标志,地址值起始于 0。
处理器
CPU,也就是处理器,基本的作用是解释并执行主存中的指令。在处理器内部的存储设备是是寄存器,寄存器只能存放一个字长的指令。寄存器会有很多个,其中有被称为程序计数器(Program Counter,PC)的寄存器。在任意时刻,PC 存放主存中的一条机器指令,这条指令将在当前正在执行的指令完成后执行。从计算机通电到关机,处理器都在执行 PC 中的指令并将 PC 更新为下一条指令。
处理器能够执行的所有指令由其指令集架构(Instruction Set Architecture)定义,指令以严格的次序执行,而每条指令的执行都可以分解为更基本的步骤,就像组成物质的分子可以分为原子,原子又可以分为更基本的原子核和电子……这些基本操作无外乎是对主存和寄存器的读写,以及操作算术/逻辑运算单元(Arithmetic/Logic Unit,ALU)。
寄存器是一组一次只能保存一个字的存储单元,每个寄存器都有名字。ALU 可以完成计算,得到新数据。一条指令可能会执行下面的 4 种基本操作。
- 读取(Load),从主存中读入一个字节或一个字的数据到寄存器,同时寄存器中先前的值将被覆盖。
- 保存(Store),将寄存器中的一个字节或一个字的数据写入到主存的一块区域,这块区域的值将被覆盖。
- 执行(Operate),将两个寄存器的值写入 ALU,ALU 对两个数执行算术运算并将结果保存到一个寄存器,覆盖这个寄存器中的值。
- 跳转(Jump),提取指令中的一个字并将字写入 PC,这会更新 PC 的值。
这些基本步骤虽然简单,但现代处理器会使用复杂的机制来加快指令执行。不同处理器指令集架构对每条机器指令的实现有所不同,用微架构这个词来区分处理器实际的实现方式。例如现在的家用处理器 Intel 和 AMD 使用相同的指令集架构,而两家处理器的微架构不同,同样是加法,各有各的实现方式。落到底层,可能是如何操作晶体管。第三、四、五章将有更详细的描述。
……在省略很多细节后,再来理解 Hello World 程序。Shell 本身就在执行指令,等待键盘输入的命令,当输入 ./hello
后,Shell 读取每个字符到寄存器中,再将这些字符写入主存。当按下回车键后,Shell 执行一系列指令以读取 hello
文件的内容到主存,其中就包括后面将会打印出来的 Hello,World!\n
这段数据。使用直接内存访问(Direct Memory Access,DMA)技术可以将数据直接从磁盘写入主存而不需要经过处理器。
缓存的重要性
从例子中可以发现,系统需要花费大量时间将数据从一个地方移动到另一个地方。Hello World 程序最初存放于磁盘,运行时,程序将读入主存。而后,处理器运行程序时,主存中的数据将进入处理器。Hello,World!\n
字符串从磁盘复制到主存,再从主存复制到显示设备。系统花费了大量时间来移动数据,而真正执行任务的时间只占很小一部分。因而,系统设计的主要目标是让复制操作执行地足够快。
存储空间越大的设备比存储空间小的设备更慢。处理器中的寄存器一共只能保存几百字节的数据,而主存的容量能达到数十亿字节,但是处理器能直接读取寄存器中的数据,速度是读取主存数据的百倍。尽管人类的半导体技术日新月异,提升主存速度还是没有提升处理器的速度来得那么容易。
为了缓解主存和处理器之间数据读取速度差别巨大带来的问题,人们在主存和处理器之间加入了缓存(Cache Memories)。缓存速度比主存更快,可以为处理器提供将来可能会用到的数据,避免读取主存带来的漫长等待。一级缓存(L1 Cache)最接近寄存器,能够缓存上千字节的数据;二级缓存(L2 Cache)可以提供上百万字节的空间,访问 L2 需要的时间可能是访问 L1 时间的 5 倍,但还是比直接访问主存快了 5-10 倍。现在的处理器还会有三级缓存(L3 Cache),容量更大。缓存使用的存储元件是 SRAM(Static Random Access Memory),不需要像主存 DRAM 一样周期性充电,代价就是 SRAM 更为昂贵。
程序很有可能访问与当前数据在同一块小区域中的数据(例如用循环遍历一个数组),如果将一小块邻近区域的数据放入缓存,下一次处理器将能更快地读到需要地数据,这是局部性原理。如果能在程序中用好缓存,程序性能可能会有巨大提升。
存储设备层级
从处理器内部的寄存器,到 L1、L2、L3,再到主存、本地磁盘和网络中的设备,设备的存储容量逐级提升,而访问速度递减,每一级的存储设备都是下一级存储的“缓存”。
操作系统管理硬件
在 Shell 载入 Hello World 程序到程序输出的过程中,使用到了键盘、显示器、磁盘和主存等设备。程序使用任何硬件设备都要通过操作系统提供的服务。操作系统实现了对硬件的抽象,是在硬件和应用程序之间的中间层。有了硬件的抽象,应用程序就不用应付不同硬件了。
操作系统中,文件是对输入输出设备的抽象,读写文件就是操作设备。虚拟地址空间是对输入输出设备(有一部分输入输出设备会映射到内存地址)和主存的抽象,每个程序有了独立的内存空间,互相隔离。而进程又是对输入输出设备、主存和处理器的抽象,对每个进程来说,都好像是独占了计算机的资源(处理器、主存和输入输出设备)。
进程
进程是操作系统对正在运行的程序的抽象。多个进程可以同时运行在一个系统中,每个进程可以“独占”硬件。对于只有单个处理器的计算机系统来说,一个时刻只有一个程序在运行,为了让每个程序交替使用处理器,操作系统用到了上下文切换机制。现在我们使用的处理器大多有多个逻辑核心,能够真正实现在同一时刻运行多个程序。为简化论述,这里只讨论单个处理器的情况。
操作系统会跟踪每个进程的所有信息,也就是进程的上下文。上下文包括进程使用的寄存器和主存。当执行上下文切换,准备运行另一个进程时,操作系统需要将控制权转移到新进程。控制权转移时,首先要保存当前进程的上下文,再载入新进程的上下文。
当 Shell 准备载入 Hello World 程序时,首先就要从磁盘读入程序的内容到内存中,读取文件需要与设备交互,与设备交互就需要操作系统介入。Shell 程序通过系统调用将控制权转移给操作系统内核,内核完成读取文件后,将操作返回给 Shell 进程。内核不是一个进程,而是一系列常驻内存、用于管理所有进程的代码和数据结构。
线程
在现代计算机系统中,一个进程通常会包含多个执行控制流,也就是线程。同一进程中的线程共享代码和全局变量。线程之间的数据共享比进程容易得多,也更适合需要高并发的网络服务器。多线程也是在多处理器条件下加快程序运行的手段。
虚拟内存
虚拟内存为进程提供了自己独占访问所有主存地址空间的假象。每个进程都有自己的虚拟内存映像,称为虚拟地址空间。在 Linux 操作系统中,虚拟地址空间的顶部区域用于存放操作系统的代码和数据,这段空间对所有进程来说都是一样的。较低的地址空间区域给用户进程存放代码和数据。地址空间按用途分为若干区域,这里有一个简要介绍。
- 程序代码和数据段。靠近地址空间的零地址部分,数据内容来自可执行文件本身。这段地址空间较高部分存放 C 程序中的全局变量。
- 堆。地址空间紧跟代码和数据段,不同的是,堆空间可以动态扩展和收缩(例如调用
malloc
和free
等 C 库函数时就会动态分配、释放内存空间)。 - 共享库。在靠近地址空间中部的位置是共享库的存放区域,例如标准 C 函数库就会存放在此处。
- 栈。在用户进程可以使用的地址空间顶部是栈空间。栈用于存放程序调用的先后关系,调用函数时入栈,栈地址增长;函数调用返回时出栈,栈地址减小。
- 内核。内核使用虚拟地址空间的顶部区域,应用程序没有权限读取、写入这块空间的数据,也不能直接调用定义在内核空间的函数。
为了能让虚拟地址空间正确工作,需要硬件和操作系统紧密协作。处理器会直接使用虚拟内存地址,实际读写时需要转换为物理内存地址。
文件
文件是一个或长或短的字节序列。所有的输入输出设备,甚至是网络都可以抽象为文件,因为输入输出设备符合文件能被读取和写入的特点。有了这一层抽象,程序员就能非常容易地让同一个读写文件的程序运行在不同系统上,而不需要关心计算机系统使用的磁盘是什么(例如固态硬盘、机械硬盘、软盘)。
计算机系统之间可以通过网络通信
现在的计算机系统一般都不是孤立的,网络是让大量计算机系统相互通信的途径。网络也可以看作是一种输入输出设备,当系统从主存复制字节序列到网络适配器时,数据流通过网络传输给其他机器,这与写入本地磁盘并没有本质不同。随着 Internet 的发展,从网络中的其他机器获得信息似乎成了计算机系统最主要的用途(手机)。
如果 Hello World 程序不在本地计算机中,而是在另一台计算机上,就可以通过网络来运行这个程序。存放 Hello World 程序的计算机可以称为服务器,客户端可以通过 telnet 等连接程序登录到服务端。在客户端输入的命令可以通过网络传输的服务端执行,在服务端程序的输出也可以通过网络在客户端上显示。
其他重要概念
上文对计算机系统做了一个简单的介绍,可以发现,计算机系统不是简单的硬件集合,为了能让程序运行起来这个“终极”目标,软件和硬件需要精密合作。书中的其他部分将介绍更多“精密合作”的细节。下面强调几个计算机系统中重要的概念。
Amdahl 定律
定律讲了提升系统一部分的速率对系统整体速率的影响程度取决于:
- 这个部分对于整个系统的重要程度;
- 这个部分速率提升了多少。
假设一个系统运行需要的时间为 \(T_{old}\),其中某组件运行的时间占整个系统运行时间的比例为 \(\alpha\)。现在这个组件的性能提高了 \(k\) 倍,也就是这个组件运行需要的时间变为 \((\alpha T_{old})/k\),那么系统整体运行的时间变为
\[\begin{aligned} T_{new} &=(1-\alpha)T_{old}+(\alpha T_{old})/k\\&=T_{old}[(1-\alpha)+\alpha/k] \end{aligned}\]系统加速比就是
\[\begin{aligned} S&=T_{old}/T_{new}\\ &=\frac{1}{(1-\alpha)+\alpha/k} \end{aligned}\]举例来说,如果组件原先消耗的时间占整体的 60%,现在这个组件加快了 3 倍,那么系统整体速率提升了 \(1.67\times\)。可以发现,虽然系统的一个组件提升的速率比较高,但系统整体速率并没有那么显著,也就是说,为了显著提升整个系统的执行速率,必须提升系统绝大部分组件的速率。
在如何表达性能提升的效果上,书中推荐用提升前的时间比上提升后的时间,如果结果大于 1,说明性能得到了提升。除此之外在比率值后添加一个乘号 \(\times\)。而用百分比来表示提升的比率会很含糊,难以区分比率是用时间差值比先前的时间还是现在的时间。
进一步地,如果将系统中一个部分的速率优化到极致,也就是这部分消耗的时间忽略不计,那么现在系统加快的比率就是
\[S_\infty = \frac{1}{1-\alpha}\]举例来说,如果系统原先 60% 的部分可以优化到几乎不消耗时间,那么系统整体的消耗时间将减少为原来的 \(\frac{2}{5}\),加速比为 \(2.5\times\)。最终效果并没有想象的那么快。
这个定律能够指导我们在优化程序时的方向——不要在小部分组件上花费大量成本提高性能,因为即使这部分性能显著提升,系统整体也不会有明显变化。如果要将性能提升两倍,需要优化大部分系统组件才行。
这让我想起了“土豆悖论”,说的是一筐 100 斤的土豆,其中有 99% 的水分。现在将土豆风干,如果想让这筐土豆的含水量降到 98%,那么要风干掉多少斤水?
答案有点违反直觉,要风干 50 斤水。总体上比率的一点点改变,其中的“部分”就要拿出很大的量变。这和 Amdahl 定律似乎有几分相像。
并发和并行
纵观计算机发展的历程,有两个需求推动了计算机的发展:1. 想要计算机能完成更多的任务;2. 想要计算机完成任务的速度更快。只要处理器能在同一时间执行更多的事情就能满足这两个需求。术语并发(Concurrency)表示在较短的时间内,系统能够同时处理多个任务;术语并行(Parallelism)表示使用并发来使系统运行更快的具体做法。在计算机系统中,并行可以在多个抽象层面上实现,这里列出三个从计算机系统最高层面到最低层面可以实现并行的例子。
线程层面的并发
有了进程这一抽象,可以让多个程序在人不能察觉的较短时间段内同时运行,这就是并发。有了线程以后,单个进程中都能够执行多条控制流,甚至不需要再创建额外进程。在单处理器系统上,并发是处理器通过快速切换执行程序来实现的。这种并发实现方式一直以来都工作得很好——单个网站服务器能够同时服务众多用户,个人电脑也可以同时运行多项任务。
多处理器系统从上世纪八十年代开始出现,不过普通用户接触更多的是多核处理器和超线程处理器。典型的多核处理器在单块芯片上集成多个核心,每个核心都有独立的一级缓存和二级缓存,并且一级缓存分为两个部分,一个用于存放指令,另一个存放数据。理论上,单块芯片能够集成上百个核心,希望有生之年能够看到。
超线程是一项让单个处理器同时执行多条控制流的技术。超线程处理器内部有多份寄存器,但用于执行计算的单元只需要一份。传统的处理器在切换线程执行时可能需要近 2 万个时钟周期,而超线程处理器可以在时钟周期间决定运行哪个线程。例如,如果一个线程需要等待数据,处理器就能去执行其他线程。
有了超线程处理器后,模拟并发的需求会降低,模拟并发本身就需要一定时间。进一步地,使用了多线程的程序也能够够运行地更快(如果代码写得合理的话)。
指令层面的并行
更底层的并行是指令的并行。较早的处理器执行一条指令需要多个时钟周期才能完成,而更新的处理器能够在单个时钟周期内完成 2-4 条指令。处理器用到了流水线技术,让处理器在单个时钟周期内执行多个指令。虽然这项技术会让单条指令执行的时间延长,但由于处理器能够同时执行上百条指令,算下来单个时钟周期能执行的指令就变多了!单个指令可能由多个阶段组成,每个阶段是由不同的硬件单元来完成的,不同硬件单元可以在同一时间共同工作,完成不同指令的不同阶段,以达到指令层面的并行。
在单个时钟周期内能执行超过一条指令的处理器称为超标量处理器,现代的处理器大多支持超标量技术。第五章中将使用这项技术来加快程序运行。
单指令、多数据流的并行
在最低层面,现代处理器的特殊硬件能够让一条指令在多个数据间同时执行,这就是单指令多数据流(Single-Instruction Multiple-Data,SIMD)。例如,单条加法指令能够同时对八对单精度浮点数进行计算,就像是对两个向量执行计算。这种计算多用于图像、音频或视频数据,GPU 在这些数据的并行计算上就做得很好。
计算机系统中抽象的重要性
复杂的系统需要抽象,就像现实社会中的组织机构层层分级、各司其职,维持整个社会的秩序,有了秩序人民群众才能生产。计算机系统中也是如此,合理的抽象可以隐藏底层的复杂性。优秀的程序库向外提供简单的编程接口,这样其他程序调用的时候就不必关系程序库内部是如何实现的,就如面向对象语言中的类和 C 语言中的函数原型。
上文中已经提到了几种抽象。
- CPU 指令集提供了对处理器的抽象,用机器语言编写的程序就不必关心具体的处理器型号,正确的程序在相同指令集的处理器上会有相同的结果。
- 操作系统提供了 3 种抽象:
- 文件。输出输出设备的抽象。
- 虚拟内存。进程内存空间的抽象。
- 进程。正在运行中的程序的抽象。
进一步的抽象就是虚拟机,提供对整个计算机的抽象,包括操作系统、处理器和程序。
本章小结
- 程序的运行需要计算机软硬件紧密合作。
- 信息就是一串 0 和 1,其表示的实际内容按其所处的上下文而定。
- 程序是从文本经编译器、链接器处理后得到的可执行文件。
- 处理器从主存中读取程序中的机器指令。
- 计算机有大量的时间都花在数据的搬运上,所以设计了多个层级的缓存系统来平衡速度和存储容量。
- 程序员如果好好利用了存储层级设计的特点,就能优化程序性能。
- 操作系统是应用程序和硬件之间的中间层,为程序提供了三种抽象:文件、虚拟内存、进程。
- 网络可以让计算机系统之间相互通信,网络也是一种输入输出设备。