【书摘】深入理解计算机系统(第二版)

这是我之前自学时的笔记,本文的内容为第二版。

Notes from Da Wang, Feb.2 2015


从程序员的角度来学习计算机系统是如何工作的会非常有趣,主要是因为你可以主动地来做这件事情。无论何时你学到一些新的东西,都可以马上试验并且直接看到运行结果。事实上,我们相信学习系统的唯一方法就是做(do)系统,即再真正的系统上解决具体的问题,或是编写和运行程序。

本书起源于1998年秋季,作者在 CMU 开设的编号为15-213的介绍性课程:计算机系统导论(Introduction to Computer Systems, ICS),是大多数高级系统课程的先行必修课。宗旨是用一种不同的方式向学生介绍计算机,只讨论那些影响用户级 C 语言程序的性能、正确性或实用性的主题。

计算机系统漫游

我们通过跟踪 helloworld 程序的生命周期来开始对系统的学习——从它被程序员创建,到在系统上运行,输出简单的消息,然后终止。

信息就是位 + 上下文

csapp1.1

hello.c 程序以字节序列的方式存储在文件中。每个字节都有一个整数值,而该整数值对应于某个字符。

csapp1.2

hello.c 的表示方法说明了一个基本的思想:系统中所有的信息——包括磁盘文件、存储器中的程序、存储器中存放的用户数据以及网络上传送的数据,都是由一串位表示的。区分不同数据对象的唯一方式是我们读到这些数据对象时的上下文。

C 编程语言的起源

  • 贝尔实验室的 Dennis Ritchie 于 1969-1973 年创建
  • C 语言与 Unix 操作系统关系密切
  • C 语言小而简单
  • C 语言是为实践目的而设计的
  • C 语言是系统级编程的首选,同时它也非常适用于应用级程序的编写。然而,它也并非适用于所有的程序员和所有的情况。C 语言的指针是造成困惑和程序错误的一个常见原因。同时,C 语言还缺乏对非常有用的抽象(类、对象和异常)的显式支持。

程序被其他程序翻译成不同的格式

hello 程序的生命周期是从一个高级 C 语言程序开始的,因为这种形式能够被人读懂。为了在系统上运行,每条 C 语句都必须被其他程序转化为一系列的低级机器语言指令。然后这些指令按照一种称为可执行目标程序的格式打好包,并以二进制磁盘文件的形式存放起来。目标程序也称为可执行目标文件

在 Unix 系统上,从源文件到目标文件的转化是由编译器驱动程序完成的:

unix> gcc -o hello hello.c

这个翻译过程可分为四个阶段。这行这四个阶段的程序(预处理器cpp、编译器ccl、汇编器as和链接器ld)一起构成了编译系统(compilation system)。

csapp1.3

GNU 项目

GCC 是 GNU(GNU’s Not Unix) 项目开发出来的众多有用工具之一。GNU 项目已经开发出了一个包含 Unix 操作系统的所有主要部件的环境,但内核除外,内核是由 Linux 项目独立发展而来的。GNU 环境包括 EMACS 编辑器、GCC 编译器、GDB 调试器、汇编器、链接器、处理二进制文件的工具以及其他一些部件。

了解编译系统如何工作是大有益处的

知道编译系统是如何工作非常重要,原因如下:

  • 优化程序性能。了解一些机器代码以及编译器将不同的 C 语句转换为机器代码的方式。
    • 一个 switch 语句是否总是比一系列 if-else 语句高效得多?
    • 一个函数调用的开销有多大?
    • while 循环比 for 循环更有效吗?
    • 指针引用比数组索引更有效吗?
  • 理解链接时出现的错误。一些最令人困扰的程序错误往往都与链接器操作有关,尤其是当你试图构建大型的软件系统时。
    • 无法解析一个引用是什么意思?
    • 静态变量和全局变量的区别是什么?
    • 在不同 C 文件中定义的名字相同的两个全局变量会发生什么?
    • 静态库和动态库的区别是什么?
    • 我们在命令行上排列库的顺序有什么影响?
  • 避免安全漏洞。学习安全变成的第一步就是理解数据和控制信息存储在程序栈上的方式会引起的后果。

处理器读并解释存储在存储器中的指令

要想在 Unix 系统上运行可执行目标文件 hello,将文件名输入到 shell 中:

unix> ./hello
hello, world
unix>

shell 是一个命令行解释器,它输出一个提示符,等待你输入一个命令行,然后执行这个命令。如果该命令行的第一个单词不是一个内置的 shell 命令,那么 shell 就会假设这是一个可执行文件的名字,它将加载并运行这个文件。

系统的硬件组成

下图是 Intel Pentium 系统产品系列的模型:

csapp1.4

  1. 总线:贯穿整个系统的电子管道,携带信息字节并负责在各个部件间传递。通常总线呗设计成传送定长的字节块,也就是字(word)。假设字长为 4 个字节,并且总线每次只传送 1 个字。
  2. I/O 设备:系统与外部世界的联系通道。每个 I/O 设备都通过一个控制器适配器与 I/O 总线相连。控制器和适配器之间的区别主要在于它们的封装方式。控制器是置于 I/O 设备本身的或者系统的主板上的芯片组,而适配器则是一块插在主板插槽上的卡。
  3. 主存:临时存储设备,由一组动态随机存取存储器(DRAM)芯片组成。从逻辑上来说,存储器是一个线性的字节数组,每个字节都有其唯一地址。
  4. 处理器:解释(或执行)存储在主存中指令的引擎。核心是一个字长的存储设备(或寄存器),称为程序计数器(PC)。在任何时刻,PC 都指向主存中的某条机器语言指令。从系统痛点开始,直到系统断电,处理器一直在不断地执行程序计数器指向的指令,在更新程序计数器,使其指向下一条指令。

运行 hello 程序

当我们输入“./hello”后,shell 程序将字符逐一读入寄存器,再把它存放到存储器中,如下图所示:

csapp1.5

利用直接存储器存取(DMA)技术,数据可以不通过处理器而直接从磁盘到达主存

csapp1.6

一旦目标文件中的代码和数据被加载到主存,处理器就开始执行 hello 程序的 main 程序中的机器语言指令。这些指令将“hello, world\n”字符串中的字节从主存复制到寄存器文件,再从寄存器文件中复制到显示设备,最终显示在屏幕上。

csapp1.7

高速缓存至关重要

这个简单的例子揭示了一个重要的问题,即系统花费了大量的时间把信息从一个地方挪到另一个地方。因此,系统设计者的一个主要目的就是使这些复制操作尽可能快地完成。

csapp1.8

较大的存储设备要比较小的存储设备运行得慢,而快速设备的造价远高于同类的低速设备。针对这种差异,系统设计者采用了更小、更快的存储设备,即高速缓存存储器,作为暂时的集结区域,用一种叫**做静态随机访问存储器(SRAM)**的硬件技术实现。

存储设备形成层次结构

从上至下,设备的访问速度越来越慢、容量越来越大,每字节的造价也越来越便宜。

csapp1.9

操作系统管理硬件

我们可以把操作系统看成是应用程序和硬件之间插入的一层软件,所有应用程序对硬件的操作尝试都必须通过操作系统。操作系统有两个基本功能:

  1. 防止硬件被失控的应用程序滥用。
  2. 向应用程序提供简单一致的机制来控制复杂而又通常大相径庭的低级硬件设备。

csapp1.10

操作系统通过几个基本的抽象概念(进程、虚拟存储器和文件)来实现这两个功能。

Unix 和 Posix

20 世纪 60 年代是大型、复杂操作系统盛行的年代,如 IBM 的 OS/360 和 Honeywell 的 Multics 系统。贝尔实验室曾经是 Multics 项目的最初参与者,但是因为项目复杂和缺乏进展于 1969 年退出。这之后一组贝尔实验室的研究人员(Ken Thompson, Dennis Ritchie, Doug Mcllroy & Joe Ossanna)从1969年开始在 DEC PDP-7 计算机上完全用机器语言编写了一个简单得多的系统,1970 年 Brian Kernighan 命名为“Unix”。1973 年用 C 语言重新编写内核,1974年开始对外发布。

发布之后不同的 Unix 厂商加入新的、往往不兼容的特性来使它们的程序与众不同,也带来很多麻烦,为了阻止这种趋势,IEEE 开始努力标准化 Unix 的开发,后来由 Richard Stallman 命名为“Posix”,称为 Posix 标准。

进程

进程是操作系统对一个正在运行的程序的一种抽象。在一个系统上可以同时运行多个进程,而每个进程都好像在独占地使用硬件。无论是在单核还是多核系统中,一个 CPU 看上去都像是在并发地执行多个进程,这是通过处理器在进程间切换来实现的,这种交错执行的机制称为上下文切换

操作系统保持跟踪进程运行所需的所有状态信息。这种状态,也就是上下文,它包括许多信息,例如 PC 和寄存器文件的当前值,以及主存的内容。

csapp1.12

线程

一个进程实际上可以由多个称为线程的执行单元组成,每个线程都运行在进程的上下文中,并共享同样的代码和全局数据。由于网络服务器对并行处理的需求,线程称为越来越重要的编程模型,因为多线程之间比多进程之间更容易共享数据,一般来说也更高效。

虚拟存储器

虚拟存储器是一个抽象概念,它为每个进程提供了一个假象,即每个进程都在独占地使用主存。每个进程看到的是一致的存储器,称为虚拟地址空间

在 Linux 中,地址空间最上面的区域是为操作系统中的代码和数据保留的,这对所有进程来说都是一样的。地址空间的底部区域存放用户进程定义的代码和数据,请注意,图中的地址是从下往上增大的。

csapp1.13

从最低的地址开始,逐步向上介绍:

  • 程序代码和数据。对于所有的进程来说,代码是从同一固定地址开始,紧接着是和 C 全局变量相对应的数据位置。代码和数据区是直接按照可执行目标文件的内容初始化的。
  • 。代码和数据区后紧随着的是运行时堆。代码和数据区是在进程一开始运行就被规定了大小,与此不同,当调用如 mallocfree 这样的 C 标准库函数时,对可以在运行时动态地扩展和收缩。
  • 共享库。大约在地址空间的中间部分是一块用来存放像 C 标准库和数学库这样共享库的代码和数据的区域。共享库的概念非常强大,也相当难懂。
  • 。位于用户虚拟地址空间顶部的是用户栈,编译器用它来实现函数调用。和堆一样,用户栈在程序执行期间可以动态地扩展和收缩。
  • 内核虚拟存储器。内核总是主流在内存中,是操作系统的一部分。地址空间顶部的区域是为内核保留的,不允许应用程序读写这个区域的内容或者直接调用内核代码定义的函数。

文件

文件就是字节序列,仅此而已。这个简单而精致的概念拥有极其丰富的内涵,它向应用程序提供了一个统一的视角,来看待系统中可能含有的所有 I/O 设备。

系统之间利用网络通信

从一个单独的系统来看,网络可视为一个 I/O 设备。当系统从主存将一串字节复制到网络适配器时,数据流经过网络到达另一台机器,而不是其他地方。相似地,系统可以读取从其他机器发送来的数据,并把数据复制到自己的主存。

csapp1.14

重要主题

系统不仅仅只是硬件,而是硬件和系统软件互相交织的集合体,它们必须共同协作以达到运行应用程序的最终目的。下面是几个贯穿计算机系统所有方面的重要概念:

并发和并行

**并发(concurrency)**是一个通用的概念,指一个同时具有多个活动的系统;**并行(parallelism)**指的是用并发使一个系统运行得更快。并行可以在计算机系统的多个抽象层次上运用。

1.线程级并发

传统意义上,这种并发执行只是模拟出来的,是通过正在执行的进程间快速切换的方式实现的,这种配置称为单处理器系统

csapp1.16

当构建一个由单操作系统内核控制的多处理器组成的系统时,就得到了一个多处理器系统。超线程,有时称为同时多线程(simultaneous multi-threading),是一项允许一个 CPU 执行多个控制流的技术。

csapp1.17

多处理器的使用可以从两个方面提高系统性能。首先,它减少了在执行多个任务时模拟并发的需要。其次,它可以使应用程序运行得更快。

2.指令级并行

在较低的抽象层次上,现代处理器可以同时执行多条指令的属性称为指令级并行。流水线(pipelining)的引入使得指令并行成为可能。如果处理器可以达到比一个周期一条指令更快的执行速率,就称之为**超标量(superscalar)**处理器。

3.单指令、多数据并行

在最低层次上,许多处理器拥有特殊的硬件,允许一条指令产生多个可以并行执行的操作,即 SIMD 并行。

计算机系统中抽象的重要性

抽象的使用是计算机科学中最为重要的概念之一。

csapp1.18

在处理器里,指令集结构提供了对实际处理器硬件的抽象。在操作系统中:文件是对 I/O 的抽象,虚拟存储器是对程序存储器的抽象,而进程是对一个正在运行的程序的抽象。虚拟机则是对整个计算机(包括操作系统、处理器和程序)的抽象。


第一部分:程序结构和执行

计算机由处理器和存储器子系统组成。在核心部分,我们需要方法来表示基本数据类型,比如整数和实数运算的近似值。然后,我们考虑机器级指令如何操作这样的数据,以及编译器如何将 C 程序翻译成这样的指令。这一部分将帮助你深入了解如何表示和执行应用程序。

信息的表示和处理

单个 bit 不是非常有用,然而,当把 bit 组合在一起,再加上某种解释(interpretation),即给不同的可能位模式赋予含义,就能够表示任何有限集合的元素。计算机的表示法适用有限数量的 bit 来对一个数字编码,因此,当结果太大以至于不能表示时,某些运算就会溢出(overflow)

浮点运算有完全不同的数学属性,由于精度有限,浮点运算是不可结合的。整数的表示虽然只能编码一个相对较小的数值范围,但这种表示是精确的;而浮点数虽然可以编码一个较大的数值范围,但这种表示只是近似的。

C 编程语言的演变

C -> ANSI C -> ISO C90 -> ISO C99

GNU 编译器套装(GNU Compiler Collection, GCC)可以基于不同的命令行选项,依照多个不同版本的 C 语言规则来编译程序。

csapp2.1

信息存储

大多数计算机使用8位的块,或者 byte 作为最小的可寻址的存储器单位,而不是在存储器中访问单独的 bit。机器级程序将存储器视为一个非常大的字节数组,称为虚拟存储器(virtual memory)。存储器的每个字节都由一个唯一的数字来标识,称为它的地址(address),所有可能的地址集合称为虚拟地址空间(virtual address space)

十六进制表示法

一个 byte 由 8 个 bit 组成。在二进制表示法中,它的值域是 00000000(2) ~ 11111111(2);如果用十进制整数表示,它的值域就是 0 ~ 255。用十六进制书写,一个字节的值域为 00(16) ~ FF(16)。

csapp2.2

每台计算机都有一个字长(word size),指明整数和指针数据的标称大小(nominal size)。因为虚拟地址是以这样一个字来编码的,所以字长决定的最重要的系统参数就是虚拟地址空间的最大大小。也就是说,对于一个字长尾 w 位的机器而言,虚拟地址的范围为 0 ~ 2^(w-1),程序最多访问 2^w 个字节。现在的 32 位机器指的就是字长是 32 位,就限定了虚拟地址空间为 4GB。

数据大小

计算机和编译器支持多种不同方式编码的数字格式,如整数和浮点数,以及其他长度的数字。

csapp2.3

程序员应该力图使他们的程序在不同的机器和编译器上是可移植的。可移植性的一个方面就是使程序对不同数据类型的确切大小不敏感。

寻址和字节顺序

对于跨越多字节的程序对象,我们必须建立两个规则:这个对象的地址是什么,以及在存储器中如何排列这些字节。

某些机器选择在存储器中按照从最低有效字节到最高有效字节的顺序存储对象,而另一些机器则按照从最高有效字节到最低有效字节的顺序存储。前一种规则——最低有效字节在最前面的方式,称为小端法(little endian)。后一种规则——最高有效字节在最前面的方式,称为大端法(big endian)。许多比较新的微处理器使用双端法(bi-edian),也就是说可以把它们配置成作为大端或者小端的机器运行。

几种机器所使用的字节顺序会成为问题的情况:

  1. 在不同类型的机器之间通过网络传送二进制数据。
  2. 当阅读表示整数数据的字节序列时,字节顺序也很重要。
  3. 当编写规避正常的类型的系统时。

使用 typedef 命名数据类型

C 语言中的 typedef 声明提供了一种给数据类型命名的方式。这能够极大地改善代码的可读性,因为深度嵌套的类型声明很难读懂。typedef 的语法与声明变量的语法十分相似,除了它使用的是类型名,而不是变量名。

表示字符串

C 语言中字符串被编码为一个以 null(其值为 0)字符结尾的字符数组。每个字符都由某个标准编码来表示,最常见的是 ASCII 字符码。在使用 ASCII 码作为字符码的任何系统上都将得到相同的结果,与字节顺序和字大小规则无关,因此文本数据比二进制数据具有更强的平台独立性。

csapp0.2

表示代码

考虑下面的 C 函数:

int sum(int x, int y) {
    return x + y;
}

当我们在示例机器上编译时,生成如下字节表示的机器代码:

csapp0.3

可以看到指令编码是不同的。不同的机器类型使用不同的且不兼容的指令和编码方式。因此二进制代码是不兼容的。二进制代码很少能在不同机器和操作系统组合之间移植。

布尔代数简介

二进制是计算机编码、存储和操作信息的核心,所以围绕 0 和 1 的研究演化出了丰富的数学知识体系。

csapp2.7

C 语言中的位级运算

C 语言支持按位布尔运算,确定一个位级表达式的结果最好的方法,就是将十六进制的参数扩展成二进制并执行二进制运算,然后转换回十六进制。

位级运算的一个常见用法就是实现掩码运算,这里的掩码是一个位模式,表示从一个字中选出的位的集合。

C 语言中的逻辑运算

C 语言还提供了一组逻辑运算符 ||、&& 和 !,分别对应于命题逻辑中的 OR、AND 和 NOT 运算。

C 语言中的移位运算

C 语言还提供了一组移位运算,以便向左或者向右移动位模式:<<、>>。

x << k 会生成一个值,x 向左移动 k 位,丢弃最高的 k 位,并在右端补 k 个 0。

右移 x >> k 比较微妙,一般而言,机器支持两种形式的右移:逻辑右移(补 0)和算术右移(补 1)。对于无符号数据,右移必须是逻辑的。对于有符号数据,几乎所有的编译器 / 机器组合都使用算术右移。

整数表示

整型数据类型

C 语言支持多种整型数据类型——表示有限范围的整数。C 语言标准定义了每种数据类型必须能够表示的最小的取值范围。

csapp2.8

csapp2.9

csapp2.10

无符号数的编码

假设一共有 w 位,每个介于 0 ~ 2^w -1 之间的数都有唯一一个 w 位的值编码,即这个函数映射是一个双射。

补码(two’s-complement)编码

字的最高有效位解释为负权(negative weight)。

csapp2.13

C 语言标准并没有要求用补码形式来表示有符号整数,但是几乎所有的机器都是这么做的。

其他的表示方法有反码(ones’ complement)原码(sign-magnitude),这两种表示方法都有一个奇怪的属性,就是对于数字 0 有两种不同的编码方式。

有符号数和无符号数之间的转换

csapp2.17

C 语言中的有符号数与无符号数

C 语言允许无符号数和有符号数之间的转换。转换的原则是底层的位表示保持不变。

csapp2.18

扩展一个数字的位表示

将一个无符号数转换为一个更大的数据类型,我们只需要简单地在表示的开头添加 0,这种运算称为零扩展(zero extension)。将一个补码数字转换为一个更大的数据类型可以执行符号扩展(sign extension),规则是在表示中添加最高有效位的值的副本。

截断数字

截断一个数字可能会改变它的值——溢出的一种形式。

关于有符号树与无符号数的建议

有符号数到无符号数的隐式强制类型转换导致了某些非直观的行为。而这些非直观的特性经常导致程序错误,并且这种包含隐式强制类型转换细微差别的错误很难被发现。因为这种强制类型转换是在代码中没有明确指示的情况下发生的,程序员经常忽视了它的影响。

避免这类错误的一种方法就是绝不使用无符号数。实际上,除了 C 以外,很少有语言支持无符号整数。

整数运算

理解计算机运算的细微之处能够帮助程序员编写更可靠的代码。

无符号加法

考虑两个非负整数 x 和 y,满足 $0 ≤ x, y ≤ 2^w - 1$。每个数都能表示为 w 位无符号数字。如果计算它们的和,我们就有一个可能的范围 $0 ≤ x + y ≤ 2^(w+1) - 2$,表示这个和可能需要 w + 1位。无符号运算可以被视为一种模运算形式。

补码加法

必须确定当结果太大(为正)或者太小(为负)时,应该做些什么。

csapp2.24

补码乘法

csapp2.26

乘以常数

在大多数机器上,整数乘法指令相当慢,需要 10 个或者更多的时钟周期,然而其他整数运算(例如加法、减法、位级运算和移位)只需要 1 个时钟周期。因此,编译器使用了一项重要的优化,试着用移位和加法运算的组合来代替乘以常数因子的乘法。

例如,假设一个程序包含表达式 x * 14。利用等式 $14 = 2^3 + 2^2 + 2^1$,编译器会将乘法重写为 (x << 3) + (x << 2) + (x << 1),实现了将一个乘法替换为三个移位和两个加法。更好的方法是 $14 = 2^4 - 2^1$,将乘法重写为(x << 4) - (x << 1),这时只需要两个移位和一个减法。

除以 2 的幂

在大多数机器上,整数除法要比整数乘法更慢——需要 30 个或者更多的周期。除以 2 的幂也可以用移位运算右移来实现,无符号和补码数分别使用逻辑移位和算术移位来达到目的。

关于整数运算的最后思考

计算机执行“整数”运算实际上是一种模运算形式。表示数字的有限字长限制了可能的值的取值范围,结果运算可能溢出。补码表示提供了一种既能表示负数也能表示正数的灵活方法,同时使用了与执行无符号算术相同的位级实现。

浮点数

浮点表示对形如 V = x * 2^y 的有理数进行编码,IEEE 标准 754 规定了如何表示浮点数及其运算。

二进制小数

csapp2.30

增加二进制表示的长度可以提高表示的精度。

IEEE 浮点表示

用 V = (-1)^s * M * 2^E 的形式来表示一个数:

  • 符号(sign) s决定这个数是负数(s=1)还是正数(s=0),对于数值 0 的符号位解释作为特殊情况处理。
  • 尾数(significand) M 是一个二进制小数,它的范围是 1 ~ 2 - ε,或者是 0 ~ 1 - ε。
  • 阶码(exponent) E 的作用是对浮点数加权,这个权重是 2 的 E 次幂(可能是负数)

将浮点数的位表示划分为三个字段,分别对这些值进行编码:

  • 一个单独的符号位 s 直接编码符号 s。
  • k 位的阶码字段 exp = e(k-1)…e(1)e(0) 编码阶码 E。
  • n 位小数字段 frac = f(n-1)…f(1)f(0) 编码尾数 M,但是编码出来的值也依赖于阶码字段的值是否等于 0。

csapp2.31

csapp2.32

2.4.3 数字示例

csapp2.33

csapp2.34

2.4.4 舍入(rounding)

因为表示方法限制类浮点数的范围和精度,浮点运算只能近似地表示实数运算。因此,对于值 x,我们一般想用一种系统的方法,能够找到“最接近的”匹配值,这就是舍入运算的任务。

2.4.5 浮点运算

浮点加法不具有结合性。浮点乘法在加法上不具备分配性。对于科学计算程序员和编译器编写者来说,这是很严重的问题,即使为了在三维空间中确定两条线是否交叉而写代码这样看上去很简单的任务,也可能成为一个很大的挑战。

2.4.6 C 语言中的浮点数

float 和 double。在 int、float 和 double 格式之间进行强制类型转换时,程序改变数值和位模式的原则如下(假设 int 是 32 位的):

  • 从 int 转换成 float,不会溢出,可能被舍入。
  • 从 int 或 float 转换成 double,能够保留精确的数值。
  • 从 double 转换成 float,可能溢出成为正无穷或负无穷,也可能被舍入。
  • 从 float 或者 double 转换成 int,值会向零舍入。例如 1.999 将被转换成 1。

小结

计算机将信息按位编码,通常组织成字节序列。用不同的编码方式表示整数、实数和字符串。不同的计算机模型在编码数字和多字节数据中的字节排序时使用不同的约定。

由于编码的长度有限,与传统整数和实数运算想必,计算机运算具有完全不同的属性。当超出表示范围时,有限长度能够引起数值溢出。当浮点数非常接近于 0.0,从而转换成零时,也会瞎溢。

必须非常小心地使用浮点运算,因为浮点运算只有有限的范围和精度,而且不遵守普遍的算术属性,比如结合性。

程序的机器级表示

计算机执行机器代码,用字节序列编码低级的操作,包括处理数据、管理存储器、读写存储设备上的数据,以及利用网络通信。编译器基于编程语言的原则、目标机器的指令集和操作系统遵循的规则,经过一系列的阶段产生机器代码。GCC C 语言汇编器以汇编代码的形式产生输出,汇编代码是机器代码的文本表示,给出程序中的每一条指令。然后 GCC 调用汇编器链接器,从而根据汇编代码生成可执行的机器代码。

历史观点

Intel 处理器系列俗称 x86,经历了一个长期的、不断进化的发展过程。

程序编码

假设一个 C 程序,有两个文件 p1.c 和 p2.c。我们在一台 IA32 机器上,用 Unix 命令行编译这些代码如下:

unix> gcc -O1 -o p p1.c p2.c

编译选项 -O1 告诉编译器使用第一级优化。使用更高级别的优化产生的代码会严重改变形式,以至于产生的机器代码和初始源代码之间的关系非常难以理解。实际中,从得到的程序性能方面考虑,第二级优化(-O2)被认为是较好的选择。

实际上 gcc 命令调用了一系列程序,将源代码转化成可执行代码。首先,C 预处理器扩展源代码,插入所有用 #include 命令指定的文件,并扩展所有用 #define 声明指定的宏。然后,编译器产生两个源代码的汇编代码,名字分别为 p1.s 和 p2.s。接下来,汇编器将汇编代码转化成二进制目标代码,文件名为 p1.o 和 p2.o。目标代码是机器代码的一种形式,它包含所有指令的二进制表示,但是还没有填入地址的全局值。最后,链接器将两个目标代码文件与实现库函数(例如 printf )的代码合并,并产生最终的可执行代码文件 p。

机器级代码

对于机器级变成来说,有两种抽象非常重要。第一种是机器级程序的格式和行为,定义为指令集体系结构(Instruction set architecture, ISA),它定义了处理器状态、指令的格式,以及每条指令对状态的影响。第二种抽象是,机器级程序使用的存储器地址是虚拟地址,提供的存储器模型看上去是一个非常大的字节数组。

在整个编译过程中,编译器会完成大部分的工作,将把用 C 语言提供的相对比较抽象的执行模型表示的程序转化成处理器执行的非常基本的指令。汇编代码非常接近于机器代码,与机器代码的二进制格式相比,汇编代码有一个主要特点,即它用可读性更好的文本格式来表示。能够理解汇编代码和它与原始的 C 代码的联系,是理解计算机如何执行程序的关键一步。

IA32 机器代码和原始的 C 代码差别非常大。一些通常对 C 语言程序员隐藏的处理器状态是可见的:

  • 程序计数器(PC,用 %eip 表示)指示将要执行的下一条指令在存储器中的地址。
  • 整数寄存器文件包含 8 个命名的位置,分别存储 32 位的值。这些寄存器可以存储地址(对应于 C 语言的指针)或证书数据。有的寄存器被用来记录某些重要的程序状态,而其他的寄存器则用来保存临时数据。
  • 条件码寄存器保存着最近执行的算术或逻辑指令的状态信息。它们用来实现控制或数据流中的条件变化。
  • 一组浮点寄存器存放浮点数据。

汇编代码不区分有符号或无符号整数,不区分各种类型的指针,甚至不区分指针和整数。

程序存储器(program memory)包含:程序的可执行机器代码,操作系统需要的一些信息,用来管理过程调用和返回的运行时栈,以及用户分配的存储器块。

一条指令只执行一个非常基本的操作。例如,将存放在寄存器中的两个数字相加,在存储器和寄存器之间传送数据,或是条件分支转移到新的指令地址。编译器必须产生这些指令的序列,从而实现(像算术表达式求值、循环或过程调用和返回这样的)程序结构。

代码示例

假设我们写了一个 C 语言代码文件 code.c,内容如下:

int accum = 0;

int sum(int x, int y){
    int t = x + y;
    accum += t;
    return t;
}

在命令行上使用 -S 选项,就能得到 C 语言编译器产生的汇编代码:

unix> gcc -O1 -S code.c

GCC 会运行编译器,产生一个汇编文件 code.s,但是不做其他进一步的工作。如果我们使用 -c 命令行选项,GCC 会编译并汇编该代码:

unix> gcc -O1 -c code.c

这就会产生目标代码文件 code.o,它是二进制格式,无法直接查看。机器实际执行的程序只是对一系列指令进行编码的字节序列。及其对产生这些指令的源代码几乎一无所知。

关于格式的注释

所有以 . 开头的行都是指导汇编器和链接器的命令,我们通常可以忽略这些行。

数据格式

由于是从 16 位体系结构扩展成 32 位的,Intel 用术语 word 表示 16 位数据类型。因此,称 32 位数为 double words,称 64 位数为 quad words。后面遇到的大多数指令都是对 word 或者 double words 操作的。

csapp3.1

访问信息

一个 IA32 CPU 包含一组 8 个存储 32 位值的寄存器。这些寄存器用来存储整数数据和指针。它们的名字都以 %e 开头,不过它们都另有特殊的名字。

csapp3.2

对前三个寄存器(%eax, %ecx, %edx)的保存和恢复惯例不同于接下来的三个寄存器(%ebx, %edi, %esi)。最后两个寄存器(%ebp, %esp)保存着指向程序栈中重要位置的指针。只有根据栈管理的标准惯例才能修改这两个寄存器中的值。

字节操作指令可以独立地读写前 4 个寄存器的 2 个低位字节。8086 中提供这样的特性是为了兼容 8008 和 8080。当一条字节指令更新这些单字节“寄存器元素”中的一个时,余下的 3 个字节不会改变。

操作数指示符

大多数指令有一个或多个操作数(operand),指示出执行一个操作中要引用的源数据值,以及放置结果的目标位置。操作数可能被分为三种类型:

  1. 立即数(immediate),也就是常数值
  2. 寄存器(register),表示某个寄存器的内容
  3. 存储器(memory)引用,它会根据计算出来的地址访问某个存储器位置

csapp3.3

数据传送指令

将数据从一个位置复制到另一个位置的指令是最频繁使用的指令。操作数表示的通用性使得一条简单的数据传送指令能够完成在许多机器中要好几条指令才能完成的功能。

csapp3.4

算术和逻辑操作

给出的每个指令类都有对字节、字和双字数据进行操作的指令。这些操作被分为四组:加载有效地址、亿元操作、二元操作和移位。

加载有效地址

加载有效地址(load effective address)指令 leal 实际上是 movl 指令的变形。它的指令形式是从存储器读数据到寄存器,但实际上它根本就没有引用存储器。它的第一个操作数看上去是一个存储器引用,但该指令并不是从指定的位置读入数据,而是将有效地址写入到目的操作数。

csapp3.7

一元操作和二元操作

一元操作:一个操作数既是源又是目的

二元操作:第二个操作数既是源又是目的

移位操作

先给出移位量,第二项给出的是要移位的位数,可以进行算术和逻辑右移。

讨论

csapp3.8

特殊的算术操作

csapp3.9

控制

机器代码提供两种基本的低级机制来实现有条件的行为:测试数据值,然后根据测试的结果来改变控制流或者数据流。

条件码

除了整数寄存器,CPU 还维护着一组单个 bit 的条件码(condition code) 寄存器,他们描述了最近的算术或逻辑操作的属性。

csapp0.4

csapp3.10

访问条件码

条件码通常不会直接读取,常用的使用方法有三种:

  1. 可以根据条件码的某个组合,将一个字节设置为 0 或者 1
  2. 可以条件跳转到程序的某个其他的部分
  3. 可以有条件地传送数据

csapp3.11

跳转指令及其编码

跳转(jump)指令会导致执行切换到程序中的一个全新的位置。在汇编代码中,这些跳转的目的地通常用一个标号(label)指明。

csapp3.12

翻译条件分支

将条件表达式和语句从 C 语言翻译成机器代码,最常用的方式是结合有条件和无条件跳转

csapp3.13

循环

汇编中没有循环结构的指令存在,可以用条件测试和跳转组合起来实现循环的效果。大多数汇编器根据一个循环的 do-while形式来产生循环代码,即使在实际程序中这种形式用得相对较少。

csapp3.14

csapp3.15

条件传送指令

实现条件操作的传统方法是利用控制的条件转移。当条件满足时,程序沿着一条执行路径进行,反之走另一条路径。这种机制简单而通用,但是在现代处理器上,它可能会非常低效率。

数据的条件转移是一种替代的策略。这种方法先计算一个条件操作的两种结果,然后再根据条件是否满足从而选取一个。只有在一些受限制的情况下,这种策略才可行,但是如果可行,就可以用一条简单的条件传送指令来实现它。条件传送指令更好地匹配了现代处理器的性能特征。

csapp3.16

这个机制和分支预测紧密相关。

csapp3.17

switch 语句

switch 语句可以根据一个整数索引值进行多重分支(multi-way branching)。不仅提高了 C 代码的可读性,而且通过使用**跳转表(jump table)**和使用一组很长的 if-else 语句相比,使用跳转表的优点是执行开关语句的时间与开关情况的数量无关。GCC 根据开关情况的数量和开关情况值的 sprsity 来翻译开关语句。

csapp3.18

过程

一个过程调用包括将数据和控制从代码的一部分传递到另一部分。另外,它还必须在进入时为过程的局部变量分配空间,并在退出时释放这些空间。大多数机器,包括 IA32,只提供转移控制到过程和从过程转移出控制这种简单的指令。数据传递、局部变量的分配和释放通过操纵程序栈来实现。

栈帧结构

IA32 程序用程序栈来支持过程调用。机器用栈来传递过程参数、存储返回信息、保存寄存器用于以后回复,以及本地存储。为单个过程分配的那部分栈称为栈帧(stack frame)

csapp3.21

假设过程 P(调用者)调用过程 Q(被调用者),则 Q 的参数放在 P 的栈帧中。另外,当 P 调用 Q 时,P 中的返回地址被压入栈中,形成 P 的栈帧的末尾。返回地址就是当程序从 Q 返回时应该继续执行的地方。

转移控制

csapp3.22

寄存器使用惯例

程序寄存器组是唯一能够被所有过程共享的资源。虽然在给定时刻只能有一个过程是活动的,但是我们必须保证当一个过程调用另一个过程时,被调用者不会覆盖某个调用者稍后会使用的寄存器的值。

根据惯例,寄存器 %eax、%edx、%ecx 被划分为调用者保存寄存器。当过程 P 调用 Q 时,Q 可以覆盖这些寄存器,而不会破坏任何 P 所需要的数据。另一方面, 寄存器 %ebx、%esi、%edi 被划分为被调用者保存寄存器。

过程示例

csapp3.24

递归过程

csapp3.25

csapp3.27

数组分配和访问

C 语言实现数组的方式非常简单,因此很容易翻译成机器代码。C 语言一个不同寻常的特点是可以产生指向数组中元素的指针,并对这些指针进行运算。在机器代码中,这些指针会被翻译成地址计算。

优化编译器非常善于简化数组索引所使用的地址计算。不过这使得 C 代码和它机器代码的翻译之间的对应关系有些难以理解。

基本原则

对于数据类型 T 和整型常数 N,声明如下:

T A[N];

它有两个效果。首先,它在存储器中分配一个 L*N 字节的连续区域;这里 L 是数据类型 T 的大小(单位为字节)。可以用从 0 到 N-1 之间的整数索引来访问数组元素。数组元素 i 会被存放在地址为 xa + L * i 的地方(xa 为指向数组开头的指针)

csapp0.5

指针运算

C 语言允许对指针进行运算,而计算出来的值会根据该指针引用的数据类型的大小进行伸缩。也就是说,如果 p 是一个指向类型为 T 的数据的指针,p 的值为 xp,那么表达式 p+i 的值为 xp+L*i,这里 L 是数据类型 T 的大小。

csapp0.6

嵌套的数组

int A[5][3];

等价于下面的声明

typedef int row3_t[3];
row3_t A[5];

数据类型row3_t被定义为一个 3 个整数的数组。数组 A 包含 5 个这样的元素,每个元素需要 12 个字节来存储 3 个整数。整个数组的大小就是 4x5x3=60 字节。

csapp0.7

定长数组

C 语言编译器能够优化定长多维数组上的操作代码。

csapp3.28

变长数组

csapp3.29

异质的数据结构

C 语言提供了两种结合不同类型的对象来创建数据类型的机制:结构(structure),用关键字struct声明,将多个对象集合到一个单位中;联合(union),用关键字union声明,允许用几种不同的类型来引用一个对象。

结构

创建一个数据类型,将可能不同类型的对象聚合到一个对象中。结构的各个组成部分用名字来引用。类似于数组的实现,结构的所有组成部分都存放在存储器中一段连续的区域内,而指向结构的指针就是结构第一个字节的地址。编译器维护关于每个结构类型的信息,指示每个字段(field)的字节偏移。它以这些偏移作为存储器引用指令中的位移,从而产生对结构元素的引用。

联合

提供了一种方式,能够规避 C 语言的类型系统,允许以多种类型来引用一个对象。联合声明的语法与结构的语法一样,只不过语义相差比较大。它们是用不同的字段来引用相同的存储器块。

数据对齐

许多计算机系统对基本数据类型合法地址做出了一些限制,要求某种类型对象的地址必须是某个值 K(通常是 2、4、8)。这种对齐限制简化了形成处理器和存储器系统之间接口的硬件设计

强制对齐的情况

对于大多数 IA32 指令来说,保持数据对齐能够提高效率,但是它不会影响程序的行为。另一方面,如果数据未对齐,有些实现多媒体操作的 SSE 指令就无法正确工作。

综合:理解指针

指针是 C 语言的一个重要特征。它们以一种统一方式,对不同数据结构中的元素产生引用。这里介绍一些指针和它们映射到机器代码的关键原则。

  • **每个指针都对应一个类型。**这个类型表明指针指向哪一类对象。
  • **每个指针都有一个值。**这个值是某个指定类型对象的地址。特殊的 NULL(0) 值表示该指针没有指向任何地方
  • **指针用 & 运算符创建。**这个运算符可以应用到任何 lvalue 类的 C 表达式上。
  • **操作符用于指针的间接引用。**其结果是一个值,它的类型与该指针的类型相关。间接引用是通过存储器引用来实现的,要么是存储到一个指定的地址,要么是从指定的地址读取。
  • **数组与指针紧密联系。**一个数组的名字可以像一个指针变量一样引用(但是不能修改)。数组引用与指针运算和间接引用有一样的效果。数组引用和指针运算都需要用对象大小对偏移量进行伸缩。
  • **将指针从一种类型强制转换成另一种类型,只改变它的类型,而不改变它的值。强制类型转换的一个效果是改变指针运算的伸缩。来看一个例子,如果 p 是一个 char* 类型的指针,那么表达式(int)p+7 计算为 p+28, 而(int)(p+7)计算为 p+7。
  • 指针也可以指向函数。这提供了一个很强大的存储和向代码传递引用的功能,这些引用可以被程序的某个其他部分调用。

函数指针

假如我们有一个函数int fun(int x, int *p),然后我们可以声明一个指针fp,将它赋值为这个函数:

(int)(*fp)(int, int *);
fp = fun;

然后用以下真真来调用这个函数

int y = 1;
int result = fp(3, &y);

应用:使用 GDB 调试器

启动 GDB:

unix> gdb prog

存储器的越界引用和缓冲区溢出

C 对于数组引用不进行任何边界检查,而局部变量和状态信息,都存放在栈中。这两种情况结合到一起就可能导致严重的程序错误,对越界的数组元素的写操作会破坏存储在栈中的状态信息。当程序使用这个被破坏的状态,试图重新加载寄存器或执行 ret 指令时,就会出现很严重的错误。

缓冲区溢出的一个更加致命的使用就是让程序执行它本来不愿意执行的函数。这是一种最常见的通过计算机网络攻击系统安全的方法。通常,输入和程序一个字符串,这个字符串包含一些可执行代码的字节编码,称为**攻击代码(exploit code),另外还有一些字节会用一个指向攻击代码的指针覆盖返回地址。那么执行 ret 指令的效果就是跳转到攻击代码。

一种攻击形式,攻击代码会使用系统调用启动一个外壳程序,给攻击者提供一组操作系统函数。另一种攻击形式是,攻击代码会执行一些未授权的任务,修复对栈的破坏,然后第二次执行 ret 指令,(表面上)正常返回给调用者。

对抗缓冲区溢出攻击

1.栈随机化

为了在系统中插入攻击代码,攻击者不但要插入代码,还需要插入指向这段代码的指针,这个指针也是攻击字符串的一部分。产生这个指针需要知道这个字符串放置的栈地址。在过去,程序的栈地址非常容易预测。对于所有运行同样程序和操作系统版本的系统来说,在不同的机器之间,栈的位置是相当固定的。用传染病来打比方,许多系统都容易受到同一种病毒的攻击,这种现象常称作安全单一化(security monoculture)

栈随机化的思想使得栈的位置在程序每次运行时都有变化。因此,即使许多机器都运行同样的代码,它们的栈地址都是不同的。实现的方式是:程序开始时,在栈上分配一段 0-n 字节之间的随机大小的空间。

在 Linux 系统中,栈随机化已经变成了标准行为。它是更大一类技术中的一种,这类技术称为**地址空间布局随机化(Address-Space Layout Randomization),或者简称 ASLR。

然而一个执着的攻击者总是能够用蛮力克服随机化,他可以反复地用不同的地址进行攻击。一种常见的把戏就是在实际的攻击代码前插入很长一段的 nop 指令。执行这种指令除了对程序计数器加一,使指针指向下一条指令之外,没有任何的效果。只要攻击者能够猜中这段序列中的某个地址,程序就会经过这个序列,到达攻击代码。这个序列常用的术语是“空操作雪橇”(nop sled)。

2.栈破坏检测

栈保护者(stack protector)机制,用来检测缓冲区越界。其思想是在栈帧中任何局部缓冲区与栈状态之间存储一个特殊的金丝雀(canary)值,也称为哨兵值(guard value),如下图所示。这个值是在程序每次运行时随机产生的,因此,攻击者没有简单的办法能够知道它是什么。在恢复寄存器状态和从函数返回之前,程序检查这个金丝雀值是否被该函数的某个操作或者该函数调用的某个函数的某个操作改变了。如果是,那么程序异常终止。

3.限制可执行代码区域

消除攻击者向系统中插入可执行代码的能力,只有保存编译器产生的代码的那部分妇女初期才是可执行的,其他部分可以被限制为只允许读和写

csapp3.33

x86-64: 将 IA32 扩展到 64 位

IA32 的 32 位字长已经成为限制微处理器能力不断增长的主要因素。最重要的是,机器的字长定义了程序能够使用的虚拟地址范围,32 位字长就是 4GB 虚拟地址空间。现在机器很容易就可以配置 4G 以上 RAM,但是系统却不能有效利用它。

Intel 和 AMD 提供的新硬件和以这些为目标的 GCC 新版本的组合,使得 x86-64 代码与为 IA32 机器生成的代码有极大的不同。主要特性如下:

  • 指针和长整数是 64 位长。整数运算支持 8/16/32/64 位数据类型
  • 通用目的寄存器组从 8 个扩展到 16 个
  • 许多程序状态都保存在寄存器中,而不是栈上
  • 如果可能,条件操作用条件传送指令实现,会得到比传统分支代码更好的性能
  • 浮点操作用面向寄存器的指令集来实现

csapp3.34

浮点程序的机器级表示

我们把存储模型、指令和传递规则的组合称为机器的浮点体系结构。由于 x86 处理器有很长的发展演变历史,它提供了多种浮点体系结构,目前有两种还在使用:x87 和 SSE

小结

机器级程序和它们的汇编代码表示,与 C 程序的差别很大。在汇编语言程序中,各种数据类型之间的差别很小。程序是以指令序列来表示的,每条指令都完成一个单独的操作。部分程序状态,如寄存器和运行时栈,对程序员来说是直接可见的。

C 语言中缺乏边界检查,使得许多程序容易出现缓冲区溢出。虽然最近的运行时系统提供了安全保护,而且编译器帮助使得程序更加安全,但是这已经使许多系统容易收到入侵者的恶意攻击。

处理器体系结构

现代微处理器可以称得上时人类创造的最复杂的系统之一。一个处理器支持的指令和指令的字节级编码称为它的指令集体系结构(Instruction-Set Architecture, ISA)。不同的处理器家族,有不同的 ISA。一个程序编译成在一种机器上运行。

注:这一章偏硬件实现部分将较为简略,具体参看原书。

Y86 指令集体系结构

定义一个指令集体系结构,包括定义各种状态元素、指令集和它们的编码、一组编程规范和异常事件处理。

程序员可见的状态

如下图所示,Y86 程序中的每条指令都会读取或修改处理器状态的某些部分,这称为程序员可见状态。在处理器视线中,只要我们保证机器级程序能够访问程序员可见状态,就不需要完全按照 ISA 隐含的方式来表示和组织这个处理器状态。

csapp4.1

Y86 处理器有 8 个程序寄存器(每个存储一个字,%esp 被入栈、出栈、调用和返回指令作为栈指针),3 个一位的条件码(保存最近的算术或逻辑指令所造成影响的有关信息),程序计数器 PC 存放当前正在执行指令的地址。

存储器,从概念上说就是一个很大的数组,保存这程序和数据。 Y86 程序使用虚拟地址来引用存储器位置。硬件和操作系统软件联合起来将虚拟地址翻译成实际或物理地址,指明数据实际保存在存储器中的哪个地方。

状态码 Stat 表明程序执行的总体状态,它会指示是正常运行,还是出现了某种异常。

Y86 指令

csapp4.2

具体说明

  • 4 个 movl 相关指令,显式指明源和目的的格式。源可以是立即数(i)、寄存器(r)或存储器(m)。指令名字的第一个字母表明了源的类型,第二个字母指明了目的类型
  • 4 个整数操作指令,即上图的 OPl,它们是 addl、subl、andl 和 xorl。它们只对寄存器数据进行操作,并设置 3 个条件码 ZF、SF 和 OF(零、符号和一处)
  • 7 个跳转指令,即上图的 jXX,它们是 jmp、jle、jl、je、jne、jge 和 jg。根据分支指令的类型和条件码的设置来选择分支
  • 6 个条件传送指令,即上图的 cmovXX:cmovle、cmovl、cmove、cmovne、cmovge 和 cmovg,只有当条件码满足所需要的约束时,才会更新目的寄存器的值
  • call 指令将返回地址入栈,然后跳到目的地址。ret 指令从这样的过程调用中返回
  • pushl 和 popl 指令实现了入栈和出栈
  • halt 指令停止指令的执行

指令编码

每条指令需要 1~6 个字节不等,每条指令的第一个字节表明指令的类型。这个字节分为两个部分,每部分 4 位:高 4 位是代码(code)部分,低 4 位是功能(function)部分

csapp4.3

CISC vs RISC

csapp0.8

逻辑设计和硬件控制语言 HCL

在硬件设计中,用电子电路来计算来计算对位进行运算的函数,以及在各种存储器元素中存储位。大多数现代电路技术都用信号线上的高电压或低电压来表示不同的位值。

逻辑门

逻辑门是数字电路的基本计算元素。它们产生的输出,等于它们输入位值的某个布尔函数。

组合电路和 HCL 布尔表达式

将很多的逻辑门组合成一个网,就能构建计算块(computational block),称为组合电路(combinational circuits)。构建这些网有两条限制:

  • 两个或多个逻辑门的输出不能连接在一起。否则它们可能会使线上的信号矛盾,可能会导致一个不合法的电压或电路故障
  • 这个网必须是无环的。也就是在网中不能有路径经过一系列的门而形成一个回路,这样的回路会导致该网络计算的函数有歧义。

字级的组合电路和 HCL 整数表达式

通过将逻辑门组合成大的网,可以构造出能计算更加复杂函数的组合电路。

Y86 的顺序实现

将处理组织成阶段

取指(fetch)、译码(decode)、执行(execute)、访存(memory)、写回(write back)、更新 PC(PC update)

流水线的通用原理

参考 Foundation of Computer Architecture,此略

小结

有关处理器设计的几个重要经验:

  • 管理复杂性是首要问题。想要优化使用硬件资源,在最小的成本下获得最大的性能
  • 我们不需要直接实现 ISA
  • 硬件设计人员必须非常谨慎小心

优化程序性能

你能获得的对程序最大的加速比就是当你第一次让它工作起来的时候。 —— John K.Ousterhout

写程序最主要的目标就是使它在所有可能的情况下都正确工作。程序员必须写出清晰简洁的代码,这样做不仅是为了程序员能够看懂代码,也是为了在检查代码和今后需要修改代码时,其他人能够读懂和理解代码。

编写高效程序需要几类活动:第一,我们必须选择一组合适的算法和数据结构。第二,我们必须编写出编译器能够有效优化以转换成搞笑可执行代码的源代码。对于第二点,理解优化编译器的能力和局限性是很重要的。

在程序开发和优化的过程中,我们必须考虑代码使用的方式,以及影响它的关键因素。通常,程序员必须在实现和维护程序的简单性与它的运行速度之间做出权衡。

程序优化的第一步就是消除不必要的内容,让代码尽可能有效地执行它期望的工作。这包括消除不必要的函数调用、条件测试和存储器引用。这些优化不依赖于目标机器的任何具体属性。

研究程序的汇编代码表示,是理解编译器,以及产生的代码如何运行的最有效的手段之一。仔细研究内循环的代码是一个很好的开端。

优化编译器的能力和局限性

现代编译器运用复杂精细的算法来确定一个程序中计算的是什么值,以及它们是被如何使用的。然后它们会利用一些机会来简化表达式,在几个不同的地方使用同一个计算,以及降低一个给定的计算必须被执行的次数。

限制编译器只进行安全的优化,消除了一些造成不希望的运行时行为的可能原因,但这也意味着程序员必须花费更大的力气写出程序使编译器能够将之转换成有效机器代码。请看下面这个例子

void twiddle1(int *xp, int *yp){
    *xp += *yp;
    *xp += *yp;
}

void twiddle2(int *xp, int *yp){
    *xp += 2* *yp
}

初看这两个函数似乎有相同的行为,都是将存储在由指针 yp 指示的位置除的值两次加到指针 xp 指示的位置处的值。另一方面,函数 twiddle2 的效率更高一些,它只要求 3 次存储器引用(读 *xp,读 *yp,写 *xp),而 twiddle1 需要 6 次。不过,当 xp 等于 yp 时,这两个函数的执行结果则会不一致,twiddle1 使 xp 的值增加 4 倍,而 twiddle2 则是 3 倍,因此,编译器不能产生 twiddle2 风格的代码作为 twiddle1 的优化版本。

这种两个指针可能指向同一个存储器位置的情况称为存储器别名使用(memory aliasing)。在只执行安全的优化中,编译器必须假设不同的指针可能会指向存储器中同一个位置。

第二个妨碍优化的因素是函数调用,例如:

int f();

int func1(){
    return f() + f() + f() + f();
}

int func2(){
    return 4*f();
}

最初看上去两个过程计算都是相同的结果,但是 func2 只调用 f1 一次,比 func2 的四次要好。不过,考虑下面 f 的代码:

int counter = 0;

int f(){
    return counter++;
}

这个函数有个副作用——它修改了全局程序状态的一部分。改变调用它的次数会改变程序的行为。所以,编译器会假设最早的情况,并保持所有函数调用不变。

表示程序性能

我们引入度量标准每元素的周期数(Cycles Per Element, CPE)作为一种表示性能并指导我们改进代码的方法。处理器活动的顺序是由时钟控制的,时钟提供了某个频率的规律信号,通常用千兆赫兹(GHz),即十亿周期每秒来表示。CPE 越小越好。

许多过程含有在一组元素上迭代的循环。如下图中的函数 psum1 和 psum2 计算都是一个长度为 n 的向量的前置和(prefix sum),对于向量 a={a0,a1,…,an-1},前置和 p={p0,p1,…pn-1}定义为

p0 = a0
pi = pi-1 + ai, 1<= i < n

函数 psum1 每次迭代计算结果向量的一个元素,第二个函数使用**循环展开(loop unrolling)**的技术,每次迭代计算两个元素。

csapp5.1

我们发现,psum1 和 psum2 的运行时间(以时钟周期为单位)分辨近似于等式 496+10.0n 和 500+6.5n。

csapp5.2

程序示例

考虑如下图所示的简单向量数据结构,由两个存储器块表示:头部和数据数组。头部是一个声明如下的结构

csapp5.3

这个声明用数据类型 data_t 作为基本元素的数据类型。例如 typedef int data_t

csapp5.4

对向量元素求和

#define IDENT 0
#define OP +

对向量元素求积

#define IDENT 1
#define OP *

csapp5.5

我们会进行一组变换,发现有很多智能带来很小的性能提高,而其他的能带来更巨大的效果。确定该使用哪些变换的组合确实是编写快速代码的魔术(black art)。

未经优化的代码是从 C 语言代码到机器代码的直接翻译,通常有明显的低效率。简单地使用命令行选项 -O1,就会进行一些基本的优化,可以显著提高性能。

消除循环的低效率

可以观察到,过程 combine1 调用函数 vec_length 作为 for 循环的测试条件。我们其实可以只计算一次向量的长度,然后在我们的测试条件中都使用这个值。如下图所示:

csapp5.6

这个优化是一类常见的优化的一个例子,称为代码移动(code motion)。这类优化包括识别要执行多次(例如在循环里)但是计算结果不会改变的计算。因而可以将计算移动到代码前面不会被多次求值的部分。

编程时一个常见的问题就是一个看上去无足轻重的代码片段有隐藏的渐进低效率(asymptotic inefficiency)

减少过程调用

过程调用会代码相当大的开销,而且妨碍大多数形式的程序优化。从上图可以看出,每次循环迭代都会调用 get_vec_element 来获取下一个向量元素。我们可以直接访问数组,而不是利用函数调用并加上边界检查:

csapp5.9

消除不必要的存储器引用

累加过程中其实没有必要每次都把结果写入到 dest 中,可以使用一个临时变量,消除不必要的存储器引用:

csapp5.10

理解现代处理器

要想获得充分提高的性能,需要仔细地分析程序,同时代码的生成也要针对目标处理器进行调整。由于可以将大量的晶体管继承到一块新品啊上,现代微处理器采用了复杂的硬件,试图使程序性能最大化。带来的一个后果就是处理器的实际操作与观察机器级程序锁察觉到的大相径庭。在代码级上,看上去似乎是一次执行一条指令,每条指令都包括从寄存器或存储器取值,执行一个操作,并把结果存回到一个寄存器或存储器位置。在实际的处理器中,是同时对多条指令求值,这个现象称为指令级并行。现代微处理器取得的了不起的功绩之一是:它们采用复杂而奇异的微处理器结构,其中,多条指令可以并行地执行,同时又呈现一种简单地顺序执行指令的表象。

两种下界描述了程序的最大性能。当一系列操作必须按照严格顺序执行时,就会遇到延迟界限(latency bound),因为在下一条指令开始之前,这条指令必须结束。当代码中的数据相关限制了处理器利用指令级并行的能力时,延迟界限能够限定程序性能。**吞吐量界限(throughput bound)**刻画了处理器功能单元的原始计算能力。这个界限是程序性能的终极限制。

整体操作

Nehalem 微体系结构是 20 世纪 90 年代以来,许多制造商生产的典型的高端处理器。在工业界称为超标量(superscalar),意思是可以在每个时钟周期执行多个操作,而且是乱序的(out-of-order),意思就是指令执行的顺序不一定要与它们在机器级程序中的顺序一致。整个设计有两个主要部分:指令控制单元(Instruction Control Unit, ICU)和执行单元(Execution Unit, EU)。前者负责从存储器中读出指令序列,并根据这些指令序列生成一组针对程序数据的基本操作;而后执行这些操作。

ICU 从指令高速缓存(instruction cache)中读取指令。指令高速缓存是一个特殊的高速缓存存储器,它包含最近访问的指令。通常,ICU 会在当前正在的指令很早之前取指,这样它才有足够的时间对指令译码,并把操作发送到 EU。不过,一个问题是党程序遇到分支时,程序有两个可能的前进方向。一种可能会选择分支,控制被传递到分支目标。另一种可能是,不选择分支,控制被传递到指令序列的下一条指令。现代处理器采用了一种称为分支预测(branch prediction)的技术,处理区会猜测是否会选择分支,同时还预测分支的目标地址。使用投机执行(speculative execution)**的技术,处理器会开始取出位于它预测的分支会跳到的地方的指令,并对指令译码,甚至在它确定分支预测是否正确之前就开始执行这些操作。如果过后确定分支预测错误,会将状态重新设置到分支点的状态,并开始取出和执行另一个方向上的指令。

功能单元的特性

每个运算都是由两个周期计数值来刻画的:一个是延迟(latency),它表示完成运算所需要的总时间;另一个是发射时间(issue time),它表示两个连续的同类型运算之间需要的最小时钟周期数。随着字长的增加,对于更复杂的数据类型,对于更复杂的运算,延迟也会增加。

处理器操作的抽象模型

我们会使用程序的数据流(data-flow)表示,作为分析在现代处理器上执行的机器级程序性能的一个工具,这是一种图形化的表示方法,展现了不同操作之间的数据相关是如何限制它们的执行顺序的。这种限制形成了图中的关键路径(critical path),这是执行一组机器指令所需时钟周期数的一个下界。

循环展开

循环展开是一种程序变换,通过增加每次迭代计算的元素的数量,减少循环的迭代次数。循环展开能够从两个方面改善程序的性能。首先,它减少了不直接有助于程序结果的操作的数量,例如循环索引计算和条件分支。其次,它提供了一些方法,可以进一步变化代码,减少整个计算中关键路径上的操作数量。

提高并行性

对于一个可结合和可交互的合并运算来说,比如说整数加法或乘法,我们可以通过将一组合并运算分割成两个或更多的部分,并在最后合并结果来提高性能。

一些限制因素

  • 寄存器溢出
  • 分支预测和预测错误处罚

通用原则:

  • 不要过分关心可预测的分支
  • 书写适合用条件传送实现的代码

csapp0.9

理解存储器性能

现代处理器有专门的功能单元来执行加载和存储操作,这些单元有内部的缓冲区来保存未完成的存储器操作请求集合。

加载的性能

一个包含加载操作的程序的性能既依赖于流水线的能力,也依赖于加载单元的延迟

存储的性能

存储操作将一个寄存器值写到存储器。

应用:性能提高技术

  1. 高级设计。为遇到的问题选择适当的算法和数据结构。要特别警觉,避免使用那些会渐进地产生糟糕性能的算法或编码技术。
  2. 基本编码原则。避免限制优化的因素,这样编译器就能产生高效的代码。
    • 消除连续的函数调用。在可能时,将计算移到循环外。考虑有选择地拖鞋程序的模块性以获得更大的效率
    • 消除不必要的存储器引用。引入临时变量来保存中间结果。只有在最后的值计算出来时,才将结果存放到数组或全局变量中
  3. 低级优化
    • 展开循环,降低开销,并且使得进一步的优化成为可能
    • 通过使用多个累积变量和重新结合等技术,找到方法提高指令级并行
    • 用功能的风格重写条件操作,使得编译采用条件数据传送

确定和消除性能瓶颈

系统优化的通用原则:Amdahl’s law

Unix 的程序剖析(profiling)工具 GPROF。这个程序产生两种形式的信息。首先,它确定程序中每个函数花费了多少 CPU 时间。其次,它计算每个函数被调用的次数,以执行调用的函数来分类。

运行时需要三个步骤

  1. 程序必须为剖析而编译和链接,加上 -pg: unix> gcc -O1 -pg prog.c -o prog
  2. 然后像往常一样执行:unix> ./prog file.txt,会产生额外的文件 gmon.out
  3. 调用 GPROF 来分析 gmon.out 中的数据:unix> gprof prog

具体的用法请参考书本或者网上的例子,此略

小结

没有任何编译器能用一个好的算法或数据结构代替低效率的算法或数据结构,因此程序设计时的这些方面仍然应该是程序员主要关心的。

存储器层次结构

存储器系统(memory system)是一个具有不同容量、成本和访问时间的存储设备的层次结构。CPU 寄存器保存着最常用的数据。靠近 CPU 的晓得、快速的**高速缓存存储器(cache memory)**作为一部分存储在相对慢速的主存储器(main memory)中的数据和指令的缓冲区域。主存暂时存放在容量较大的、慢速磁盘上的数据,而这些磁盘常常又作为存储在通过网络连接的其他机器的磁盘或磁带上的区域的缓冲区域。

如果你理解了系统是如何将数据在存储器层次结构中上上下下移动的,那么你就可以编写你的应用程序,使得它们的数据项存储在层次结构中较高的地方,在那里 CPU 能更快地访问到它们。

这个思想围绕着计算机程序的一个称为**局部性(locality)**的基本属性。具有良好局部性的程序倾向于一次又一次地访问相同的数据项集合,或是倾向于访问临近的数据项集合。

存储技术

计算机技术的成功很大程度上源自于存储技术的巨大进步。

随机访问存储器

随机访问存储器 (Random-Access Memory, RAM)分为两类:静态的和懂啊提的。SRAM 比 DRAM 更快,但也贵得多。SRAM 用来作为高速缓存存储器,既可以在 CPU 芯片上,也可以在片下。DRAM 用来作为主存以及图形系统的帧缓冲区。

固态硬盘

固态硬盘(Solid State Disk, SSD)是一种基于闪存的存储技术。一个 SSD 包由一个或多个闪存芯片和闪存翻译层(flash translation layer)组成,闪存芯片代替传统旋转磁盘中的机械驱动器,而闪存翻译层是一个硬件/固件设备,扮演与磁盘控制器相同的角色,将对逻辑块的清酒翻译成对底层物理设备的访问。

csapp6.16

SSD 有着与旋转磁盘不同的性能特征。顺序读和写性能相当,不过,当按照随机顺序访问逻辑块时,写比读慢一个数量级。随机读和写的性能差别是由底层闪存基本属性决定的。如上图所示,一个闪存由 B 个块的序列组成,每个块由 P 页组成。通常,页的大小是 512~4KB,块是由 32~128 页组成的,块的大小为 16~512 KB。数据是以页为单位读写的。只有在一页所属的块整个被擦除之后,才能写这一页。不过,一旦一个块被擦除了,块中的每一个页都可以不需要再进行擦除就写一次。在大约进行 100000 次重复写之后,块就会磨损坏。

存储技术趋势

  • 不同的存储技术有不同的价格和性能折中
  • 不同的存储技术的价格和性能属性一截然不同的速率变化着
  • DRAM 和磁盘的性能滞后于 CPU 的性能

局部性

一个编写良好的计算机程序常常具有良好的局部性(locality)。也就是说,它们倾向于引用临近于其他最近引用过的数据项的数据项,或者最近引用过的数据项本身。这种倾向性,被称为局部性原理(principle of locality),是一个持久的概念,对硬件和软件系统的设计和性能都有着极大的影响。

局部性通常有两种不同的形式:时间局部性(temporal locality)空间局部性(spatial locality)。有良好局部性的程序比局部性差的程序运行得更快。

  • 重复引用同一个变量的程序有良好的时间局部性
  • 对于具有步长为 k 的引用模式的程序,步长越小,空间局部性越好
  • 对于取指令来说,循环有好的时间和空间局部性。循环体越小,循环迭代次数越多,局部性越好

存储器层次结构

存储器层次结构(memory hierarchy)如下图所示

csapp6.23

存储器层次结构中的缓存

一般而言,高速缓存(cache)是一个小而快速的存储设备。使用高速缓存的过程称为缓存(caching)。

存储器层次结构的中心思想是,对于每个 k,位于 k 层的更快更小的存储设备作为位于 k+1 层的更大更慢的存储设备的缓存。换句话说,层次结构中的每一次都缓存来自较低一层的数据对象。

数据总是以块大小为**传送单元(transfer unit)**在第 k 层和第 k+1 层之间来回拷贝的。虽然在层次结构中任何一对相邻的层次之间块大小是固定的,但是其他的层次对之间可以用不同的块大小。一般而言,层次结构较低的层(离 CPU 较远)的设备访问时间较长,因此为了补偿这些较长的访问时间,倾向于使用较大的块。

csapp6.24

缓存命中

当程序需要第 k+1 层的某个数据对象 d 时,它首先在当前存储的第 k 层的一个块中查找 d。如果 d 刚好缓存在第 k 层中,那么就是缓存命中(cache hit)

缓存不命中

如果第 k 层中没有缓存数据对象 d,那么就是缓存不命中(cache miss)。当发生 cache miss 时,会从下一次取出包含 d 的那个块,如果第 k 层的缓存已经满了的话,可能就会覆盖现存的一个块。

覆盖一个现存的块的过程称为替换(replacing)驱逐(evicting)。被驱逐的看这个块有时也称为牺牲块(victim block)。决定该替换那个块是由缓存的**替换策略(replacement policy)**来控制的。(LRU, LFU 等等替换策略在这里可以使用)

缓存不命中的种类

一个空的缓存有时称为冷缓存(cold cache),此类不命中称为compulsory misscold miss

只要发生了 cache miss,第 k 层的缓存就必须执行某个放置策略(placement policy),确定把它从第 k+1 层中取出的块放在哪里。一般来说是用映射来确定放在哪里,如果两个不同的块映射到同一个位置,就引起了 conflict miss。当工作集的大小超过缓存的大小时,就会有 capacity miss。

csapp6.25

高速缓存存储器

早期计算机系统的存储器结构只有三层:CPU 寄存器、DRAM 主存储器和磁盘存储。不过,由于 CPU 和主存之间逐渐增大的差距,系统设计者被迫在 CPU 寄存器文件和主存之间插入了一个小的 SRAM 高速缓存存储器,称为 L1 高速缓存。之后又插入了一个更大的高速缓存,称为 L2 高速缓存,之后还有 L3 高速缓存。周期数:L1(2~4), L2(~10), L3(~30~40)

编写高速缓存友好的代码

  • 让最常见的情况运行得快
  • 在每个循环内部缓存不命中数量最小

综合:高速缓存对程序性能的影响

存储器山

一个程序从存储系统中读数据的速率称为度吞吐量(read throughput),或者有时称为读带宽(read bandwidth)

csapp6.43

重新排列循环以提高空间局部性

矩阵的循环优化,略

在程序中利用局部性

  • 将你的注意力集中在内循环上,大部分计算和存储器访问都发生在这里
  • 通过按照数据对象存储在存储器中的顺序、以步长为 1 的来读数据,从而使得程序中的空间局部性最大
  • 一旦从存储器中读入了一个数据对象,就尽可能多地使用它,从而使得程序中的时间局部性最大

小结

程序员可以通过编写有良好空间和时间局部性的程序来显著地改进程序的运行时间。利用基于 SRAM 的高速缓存存储器特别重要。

链接

链接(linking)是将各种代码和数据部分收集起来并组合成为一个单一文件的过程,这个文件可被加载到存储器并执行。链接可以执行于编译时(compile time),也可以执行于加载时(load time),甚至执行于运行时(run time)。

链接器在软件开发中扮演着一个关键的角色,因为它们使得分离编译(separate compilation)成为可能。

编译器驱动程序

大多数编译系统提供编译驱动程序(compiler driver),它代表用户在需要时调用语言预处理器、编译器、汇编器和链接器。

静态连接

静态链接器(static linker)以一组可重定位目标文件和命令行参数作为输入,生成一个完全链接的可以加载和运行的可执行目标文件作为输出。输入的可重定位目标文件由各种不同的代码和数据节(section)组成。指令在一个 section 中,初始化的全局变量在另一个 section 中,而未初始化的变量又在另一个 section 中。

csapp7.2

为了构造可执行文件,链接器必须完成两个主要任务:

  • 符号解析(symbol resolution)。目标文件定义和引用符号。符号解析的目的是将每个符号引用刚好和一个符号定义联系起来。
  • 重定位(relocation)。编译器和汇编器生成从地址 0 开始的代码和数据节。链接器通过把每个符号定义域一个存储器位置联系起来,然后修改所有对这些符号的引用,使得它们指向这个存储器位置,从而重定位这些节。

关于链接器的一些基本事实:目标文件纯粹是字节块的集合。这些块中,有些包含程序代码,有些则包含程序数据,而其他的则包含指导链接器和加载器的数据结构。链接器将这些块连接起来,确定被连接块的运行时位置,并且修改代码和数据块中的各种位置。链接器对目标机器了解甚少。产生目标文件的编译器和汇编器已经完成了大部分工作。

目标文件

目标文件有三种形式:

  • 可重定位目标文件。包含二进制代码和数据,其形式可以在编译时与其他可重定位目标文件合并起来,创建一个可执行目标文件。
  • 可执行目标文件。包含二进制代码和数据,其形式可以被直接拷贝到存储器并执行。
  • 共享目标文件。一种特殊类型的可重定位目标文件,可以在加载或者运行时被动态地加载到存储器并链接。

可重定位目标文件

下图是一个典型的 ELF 可重定位目标文件的格式。ELF 头(ELF header)以一个 16 字节的序列开始,这个序列描述了生成该文件的系统的字的大小和字节顺序。

csapp7.3

符号和符号表

每个可重定位目标模块 m 都有一个符号表,它包含 m 所定义和引用的符号的信息。在链接器的上下文中,有三种不同的符号:

  • 由 m 定义并能被其他模块引用的全局符号。全局链接器符号对应于非静态的 C 函数以及被定义为不带 C static 属性的全局变量
  • 由其他模块定义的并被模块 m 引用的全局符号。这些符号称为外部符号(external),对应于定义在其他模块中的 C 函数和变量。
  • 只被模块 m 定义和引用的本地符号。有的本地链接器符号对应于带 static 属性的 C 函数和全局变量。

C 程序员使用 static 属性在模块内部隐藏变量和函数声明。

符号解析

链接器解析符号引用的方法是将每个引用与它输入的可重定位目标文件的符号表中的一个确定的符号定义联系起来。对那些和引用定义在相同模块中的本地符号的引用,符号解析是非常简单明了的。编译器只允许每个模块中每个本地符号只有一个定义。编译器还确保静态本地变量,它们也会有本地链接器符号,拥有唯一的名字。

重定位

一旦链接器完成了符号解析这一步,它就把代码中的每个符号引用和确定的一个符号定义联系起来。在此时,链接器就知道它的输入目标模块中的代码节和数据节的确切大小。重定位由两步组成:

  • 重定位节和符号定义
  • 重定位节中的符号引用

可执行目标文件

可执行目标文件的格式类似于可重定位目标文件的格式,如下图所示。ELF 头部描述文件的总体格式。它还包括程序的入口点(entry point),也就是当程序要执行的第一条指令的地址。

csapp7.11

加载可执行目标文件

要允许可执行目标文件 p,可以在 Unix 外壳的命令行中输入它的名字

unix> ./p

因为 p 不是一个内置的外壳命令,所以外壳会认为 p 是一个可执行目标文件,通过调用某个驻留在存储器中称为加载器(loader)的操作系统代码来运行它。任何 Unix 程序都可以通过调用 execve 函数来调用加载器。加载器将可执行目标文件中的代码和数据从磁盘拷贝到存储器,然后通过跳转到程序的第一条指令或入口点(entry point)来运行该程序。这个将程序拷贝到存储器并运行的过程叫做加载(loading)。

csapp7.13

每个 Unix 程序都有一个运行时存储器映像,如上图所示。在 32 位 Linux 系统中,代码段总是从地址 0x08048000 处开始。数据段是在接下来的下一个 4KB 对齐的地址处。运行时再读/写段之后接下来的第一个 4KB 对齐的地址处,并通过调用 malloc 库往上增长。还有一个段是为共享库保留的。用户栈总是从最大的合法用户地址开始,向下增长的(向低存储器地址方向增长)。从栈的上部开始的段是为操作系统主流存储器的部分(也就是内核)的代码和数据保留的。

动态链接共享库

共享库(shared library)是致力于解决静态库缺陷的一个现代创新产物。共享库是一个目标模块,在运行时,可以加载到任意的存储器地址,并和一个在存储器中的程序链接起来。这个过程称为动态链接(dynamic linking),是由一个叫做动态链接器的程序来执行的。

共享库也称为共享目标(shared object),在 Unix 系统中通常用 .so 后缀来表示。微软的操作系统大量地利用了共享库,它们称为 DLL。

csapp7.15

共享库是以两种不同方式来“共享”的。首先,在任何给定的文件系统中,对于一个库只有一个 .so 文件。所有引用该库的可执行目标文件共享这个 .so 文件中的代码和数据,而不是像静态库的内容那样被拷贝和嵌入到引用它们的可执行的文件中。

与位置无关的代码(PIC)

PIC 数据引用;PIC 函数调用

处理目标文件的工具

在 Unix 系统中有大量可用的工具可以帮助你理解和处理目标文件。特别的,GNU binutils 包尤其有帮助,而且可以运行在每个 Unix 平台上。

  • AR: 创建静态库,插入、删除、列出和提取成员
  • STRINGS: 列出一个目标文件中所有可打印的字符串
  • STRIP: 从目标文件中删除符号表信息
  • NM: 列出一个目标文件的符号表中定义的符号
  • SIZE: 列出目标文件中节的名字和大小
  • READELF: 显示一个目标文件的完整结构,包括 ELF 头中编码的所有信息。包含 SIZE 和 NM 的功能
  • OBJDUMP: 二进制工具之母。能够显示一个目标文件中所有的信息。它最大的作用是反汇编 .text 节中的二进制命令
  • LDD: 列出一个可执行文件在运行时所需要的共享库

小结

链接可以在编译时由静态编译器来完成,也可以在加载时和运行时由动态链接器来完成。链接器处理称为目标文件的二进制文件,它又三种不同的形式:可重定位的、可执行的和共享的。可重定位的目标文件由静态链接器合并成一个可执行的目标文件,它可以加载到存储器中并执行。共享目标文件(共享库)是在运行时由动态链接器链接和加载的,或者隐含地在调用程序被加载和开始执行时,或者根据需要在程序调用 dlopen 库的函数时。

链接器的两个主要任务是符号解析和重定位,符号解析将目标文件中的每个全局符号都绑定到一个唯一的定义,而重定位确定每个符号的最终存储器地址,并修改对那些目标的引用。

静态链接器是由像 GCC 这样的编译驱动器调用的。它们将多个可重定位目标文件合并成一个单独的可执行目标文件。多个目标文件可以定义相同的符号,而链接器用来悄悄地解析这些多重定义的规则可能在用户程序中引入的微妙错误。

多个目标文件可以被连接到一个单独的静态库中。链接器用库来解析其他目标模块中的符号引用。许多链接器通过从左到右的顺序扫描来解析符号引用,这是另一个引起迷惑的链接时错误来源。

加载器将可执行文件的内容映射到存储器,并运行这个程序。链接器还可能生成部分链接的可执行目标文件,这样的文件中有对定义在共享库中的程序和数据的未解析的引用。在加载时,加载器将部分链接的可执行文件映射到存储器,然后调用动态链接器,它通过加载共享库和重定位程序中的引用来完成链接任务。

被编译为位置无关代码的共享库可以加载到任何地方,也可以在运行时被多个进程共享。为了加载、链接和访问共享库的函数和数据,应用程序还可以在运行时使用动态链接器。

异常控制流

系统必须能够对系统状态的变化做出反应,这些系统状态不是被内部程序变量捕获的,而且也不一定要和程序的执行相关。比如,一个硬件定时器定期产生信号,这个事件必须得到处理。当子进程终止时,创造这些子进程的父进程必须得到通知。

线代系统通过使控制流发生突变来对这些情况做出反应。一般而言,我们把这些突变称为异常控制流(Exceptional Control Flow, ECF)。异常控制流发生在计算机系统的各个层次。比如,在硬件层,硬件检测到的事件会触发控制突然转移到异常处理程序。在操作系统层,内核通过上下文转换将控制从一个用户进程转移到另一个用户进程。在应用层,一个进程可以发送信号到另一个进程,而接受者会将控制突然转移到它的一个信号处理程序。一个程序可以通过回避通常的栈规则,并执行到其他函数中任意位置的非本地跳转来对错误做出反应。

异常

异常是异常控制流的一种形式,它一部分是由硬件实现的,一部分是由操作系统实现的。因为它们有一部分是由硬件实现的,所以具体细节将随系统的不同而有所不同。然而,对于每个系统而言,基本的思想都是相同的。

异常(exception)就是控制流中的突变,用来响应处理器状态中的某些变化。如下图所示:

csapp8.1

在图中,当处理器状态中发生一个重要的变化时,处理器正在执行某个当前指令。在处理器中,状态被编码为不同的位和信号。状态变化称为事件(event)。事件可能和当前指令的执行直接相关。比如,发生虚拟存储器缺页、算术溢出,或者一条指令试图除以零。另一方面,事件也可能和当前指令的执行没有关系。比如,一个系统定时器产生信号或者一个 I/O 请求完成。

在任何情况下,当处理器检测到有事件发生时,它就会通过一张叫做**异常表(exception table)**的跳转表,进行一个间接过程调用(异常),到一個专门设计用来处理这类事件的操作系统子程序(异常处理程序, exception handler)

当异常处理程序完成处理后,根据引起异常的事件的类型,会发生以下三种情况中的一种:

  1. 处理程序将控制返回给当前指令 I(curr),即当事件发生时正在执行的指令。
  2. 处理程序将控制返回给 I(next),即如果没有发生异常将会执行的下一条指令。
  3. 处理程序被中断的程序

异常处理

系统中可能的每种类型的异常都分配了一个唯一的非负整数的异常号(exception number)。其中一些号码是由处理器的设计者分配的,其他号码是由操作系统内核的设计者分配的。前者的示例包括被零除、缺页、存储器访问违例以及算术溢出。后者的示例包括系统调用和来自外部 I/O 设备的信号。

在系统启动时,操作系统分配和初始化一张称为异常表的跳转表,使得条目 k 包含异常 k 的处理程序的地址。如下图所示

csapp8.2

在运行时,处理器检测到发生了一个事件,并且确定了相应的异常号 k。随后,处理器触发异常,方法是执行间接过程调用,通过异常表的条目 k 转到相应的处理程序。下图展示了处理器如何使用异常表来形成适当的异常处理程序的地址。异常号是到异常表中的索引,异常表的起始地址放在一个叫做**异常表基址寄存器(exception table base register)**的特殊 CPU 寄存器里。

csapp8.3

异常的类别

异常可以分为四类:中断(interrupt)、陷阱(trap)、故障(fault)和终止(abort)。下图是一些总结

csapp8.4

中断

中断是异步发生的,是来自处理器外部的 I/O 设备的信号的结果。硬件中断不是由任何一条专门的指令造成的,从这个意义上来说它是异步的。硬件中断的异常处理程序通常称为中断处理程序(interrupt handler)

csapp8.5

剩下的异常类型(陷阱、故障和终止)是同步发生的,是执行当前指令的结果。我们把这类指令叫做故障指令(faulting instruction)。

陷阱和系统调用

陷阱是有意的异常,是执行一条指令的结果。就像中断处理程序一样,陷阱处理程序将控制返回到下一条指令。陷阱最重要的用途是在用户程序和内核之间提供一个像过程一样的接口,叫做系统调用

用户程序经常需要向内核请求服务,比如读一个文件(read)、创建一个新的进程(fork)、记在一个新的程序(execve),或者终止当前进程(exit)。为了允许对这些内核服务的受控范文,处理器提供一条特殊的 syscall n 指令,当用户程序想要请求服务 n 时,可以执行这条指令。执行 syscall 指令会导致一个到异常处理程序的陷阱,这个处理程序对参数解码,并调用适当的内核程序。

csapp8.6

故障

故障由错误情况引起,它可能能够被故障处理程序修正。当故障发生时,处理器将控制转移给故障处理程序。如果处理程序能够修正这个错误情况,它就将控制返回到引起故障的指令,从而重新执行它。否则,处理程序返回到内核中的 abort 例程,abort 例程会终止引起故障的应用程序,如下图所示:

csapp8.7

一个经典的故障示例是缺页异常,当指令引用一个虚拟地址,而与该地址相对应的物理页面不在存储器中,因此必须从磁盘中取出时,就会发生故障。就像我们将在第 9 章中看到的那样,一个页面就是虚拟存储器的一个连续的块。缺页处理程序从磁盘加载适当的页面,然后将控制返回给引起故障的指令。当指令再次执行时,相应的物理页面已经驻留在存储器中了,指令就可以没有故障地运行完成了。

终止

终止是不可恢复的致命错误造成的结果,通常是一些硬件错误,比如 DRAM 或者 SRAM 位被损坏时发生的奇偶错误。终止程序从不将控制返回给应用程序。如下图所示

csapp8.8

Linux/IA32 系统中的异常

IA32 系统有高达256种不同的异常类型。0-31的号码对应的是由 Intel 架构师定义的异常,因此对任何 IA32 系统都是一样的。32-255的号码对应的是操作系统定义的终端和陷阱,如下图所示

csapp8.9

Linux/IA32 故障和终止

  • 除法错误。当应用试图除以零时,或者当一个除法指令的结果对于目标操作数来说太大的时候,就会发生除法错误(异常0)。Unix 不会试图从除法错误中恢复,而是选择终止程序。Linux shell 通常会把除法错误报告为浮点异常(Floating exception)。
  • 一般保护故障。许多原因都会导致不为人知的一般保护故障(异常13),通常是因为一个程序引用了一个未定义的虚拟存储器区域,或者因为程序视图写一个只读的文本段。Linux 不会尝试恢复这类故障。Linux shell 通常会把这种一般保护故障报告为段故障(Segmentation fault)。
  • 缺页(异常14)是会重新执行产生故障的指令的一个异常示例。
  • 机器检查(异常18)是在导致故障的指令中检测到致命的硬件错误时发生的。机器检查处理程序从不返回控制给应用程序

Linux/IA32 系统调用

每个系统调用都有一个唯一的整数号,对应于一个到内核中跳转表的偏移量。

csapp8.10

进程

异常是允许操作系统提供**进程(process)**的概念所需要的基本构造块,进程是计算机可续重最深刻最成功的概念之一。当我们在一个现代系统上运行一个程序时,会得到一个假象,就好像我们的程序是系统中当前运行着的唯一的程序。

进程的经典定义就是一个执行中的程序的实例。系统中的每个程序都是运行在某个进程的**上下文(context)**中的。上下文是由程序正确运行所需的状态组成的。这个状态包括存放在存储器中的程序的代码和数据,它的栈、通用目的寄存器的内容、程序计数器、环境变量以及打开文件描述符的集合。

每次用户通过向外壳输入一个可执行目标文件的名字,并运行一个程序时,shell 就会创建一个新的进程,然后在这个新进程的上下文中运行这个可执行目标文件。应用程序也能够创建新进程,且在这个新进程的上下文中运行它们自己的代码或其他应用程序。

逻辑控制流

即使在系统中通常有许多其他程序在运行,进程也可以向每个程序提供一种假象,好像它在独占地使用处理器。如果想用调试器单步执行程序,我们会看到一系列的程序计数器(PC)的值,这些值唯一地对应于包含在程序的可执行目标文件中的指令,或者是包含在运行时动态链接到程序的共享对象的指令。这个 PC 值的序列叫做逻辑控制流,或者简称逻辑流

csapp8.12

每个进程执行它的流的一部分,然后被抢占(preempted,暂时挂起),然后轮到其他进程。

并发流

一个逻辑流的执行在时间上与另一个流重叠,称为并发流(concurrent flow),这两个流被称为并发地运行。更准确地说,流 X 和 Y 互相并发,当且仅当 X 在 Y 开始之后和 Y 结束之前开始,或者 Y 在 X 开始之后和 X 结束之前开始。

多个流并发地执行的一般现象称为并发(concurrency)。一个进程和其他进程轮流运行的概念称为多任务(multitasking)。一个进程执行它的控制流的一部分的每一时间段叫做时间片(time slice)。因此,多任务也叫做时间分片(time slicing)

注意,并发的思想与流运行的处理器核数或者计算机无关。如果两个流再时间上重叠,那么它们就是并发的,即使它们是运行在同一个处理器上的。如果两个流并发地运行在不同的处理器核或者计算机上,那么我们称它们为并行流(parallel flow)

私有地址空间

进程也为每个程序提供一种假象,好像它独占地使用系统地址空间。尽管和每个私有地址空间相关联的存储器的内容一般是不同的,但是每个这样的空间都有相同的通用结构,如下图所示。

csapp8.13

用户模式和内核模式

为了使操作系统内核提供一个无懈可击的进程抽象,处理器必须提供一种机制,限制一个应用可以执行的指令以及它可以访问的地址空间范围。

处理器通常是用某个控制寄存器中的一个模式位(mode bit)来提供这种功能的,该寄存器描述了进程当前享有的特权。当设置了模式位,进程就运行在内核模式(超级用户模式)。一个运行在内核模式的进程可以执行指令集中的任何指令,并且可以访问系统中任何存储器位置。

没有设置模式位时,进程就运行在用户模式中。用户模式中的进程不允许执行特权指令(priviledged instruction),比如停止处理器、改变位模式,或者发起一个 I/O 操作。也不允许用户模式中的进程直接引用地址空间中内核区内的代码和数据。任何这样的尝试都会导致致命的保护故障。反之,用户程序必须通过系统调用接口间接地访问内核代码和数据。

Linux 提供了一种聪明的机制,叫做 /proc 文件系统,它允许用户模式进程访问内核数据结构的内容。/proc文件系统将许多内核数据结构的内容输出为一个用户程序可以读的文本文件的层次结构。

上下文切换

操作系统内核使用一种称为**上下文切换(context switch)**的较高层形式的异常控制流来实现多任务。上下文切换机制是建立在8.1节中那些较低层异常机制之上的。

内核为每个进程维持一个上下文(context)。上下文就是内核重新启动一个被抢占的进程所需的状态。它由一些对象的值组成,这些对象包括通用目的寄存器、浮点寄存器、程序计数器、用户栈、状态寄存器、内核栈和各种内核数据结构,比如描绘地址空间的页表、包含有关当前进程信息的进程表,以及包含进程已打开文件的信息的文件表

在进程执行的某些时刻,内核可以决定抢占当前进程,并重新开始一个先前被抢占的进程。这种决定就叫做调度(schedule),是由内核中称为**调度器(scheduler)**的代码处理的。当内核选择一个新的进程运行时,我们就说内核调度了这个进程。

csapp8.14

系统调用错误处理

当 Unix 系统级函数遇到错误时,它们典型地会返回 -1,并设置全局帧数变量 errno 来表示什么出错了。通过使用**错误处理包装(error-handling wrapper)**函数,可以简化错误处理代码。

进程控制

Unix 提供了大量从 C 程序中操作进程的系统调用。

获取进程 ID

每个进程都有一个唯一的正数进程 ID(PID)。getpid 函数返回调用进程的 PID。getppid 函数返回它的父进程的 PID。

#include <sys/types.h>
#include <unistd.h>

pid_t getpid(void);
pit_t getppid(void);

创建和终止进程

从程序员的角度,我们可以认为进程总是处于下面三种状态之一:

  • 运行。进程要么在 CPU 上执行,要么在等待被执行且最终会被内核调度。
  • 停止。进程的执行被挂起(suspend),且不会被调度。当收到 SIGSTOPSIGTSTPSIDTTIN 或者 SIGTTOU 信号时,进程就停止,并且保持停止直到它收到一个 SIGCONT 信号,在这个时刻,进程再次开始运行。
  • 终止。进程永远地停止了。进程会因为三种原因终止:1)收到一个默认行为是终止进程的信号,2)从主程序返回,3)调用 exit 函数

该程序无返回值,exit 函数以 status 退出来终止进程。

#include <stdlib.h>

void exit(int status);

父进程通过调用 fork 函数创建一个新的运行子进程,子进程返回0,父进程返回子进程的 PID,如果出错则为 -1。

#include <sys/types.h>
#include <unistd.h>

pid_t fork(void);

新创建的子进程几乎但不完全与父进程相同。子进程得到与父进程用户级虚拟地址空间相同的(但是独立的)一份拷贝,包括文本、数据和 bss 段、以及用户栈。子进程还获得与父进程任何打开文件描述符相同的拷贝。父进程和新创建的子进程最大的区别在于他们有不同的 PID。

fork 函数只被调用一次,却会返回两次(父进程与子进程)。因为子进程的 PID 总是非零的,返回值就提供一个明确的方法来分辨程序是在父进程还是在子进程中执行。

csapp8.15

  • 调用一次,返回两次
  • 并发执行。顺序不能保证
  • 相同但是独立的地址空间,所以变量是分别独立的
  • 共享文件,输出是指向同一个地方

csapp8.16

回收子进程

当一个进程由于某种原因终止时,内核并不是立即把它从系统中清除。相反,进程被保持在一中已终止的状态中,直到被它的父进程回收(reap)。当父进程回收已终止的子进程时,内核将子进程的退出状态传递给父进程,然后抛弃已终止的进程。一个终止了但还未被回收的进程称为僵死进程(zombie)

如果父进程没有回收它的僵死子进程就终止了,那么内核就会安排 init 进程来回收它们。init 进程的 PID 为 1,并且是在系统初始化时由内核创建的。长时间运行的程序,比如 shell 或者服务器,总是应该回收它们的僵死子进程。即使僵死子进程没有运行,它们仍然小号系统的存储器资源。

一个进程可以通过调用 waitpid 函数来等待它的子进程终止或者停止。如果成功,则返回子进程的 PID,如果 WHOHANG ,则为 0,如果其他错误,则为 -1。

#include <sys/types.h>
#include <sys/wait.h>

pit_t waitpid(pid_t pid, int *status, int options);

具体用法略

让进程休眠

sleep 函数让一个进程挂起一段指定的时间。返回还要休眠的秒数。

#include <unistd.h>
unsigned int sleep(unsigned int secs);

如果请求的时间量已经到了,sleep返回 0,否则返回还剩下要休眠的秒数。我们会发现很有用的另一个函数是 pause 函数,该函数让调用函数休眠,直到该进程收到一个信号。总是返回 -1。

#include <unistd.h>
int pause(void);

加载并运行程序

execve 函数子啊当前进程的上下文中加载并运行一个新程序。如果成功则不返回,如果错误,则返回 -1。

#include <unistd.h>

int execve(const char *filename, const char *argv[], const char *envp[]);

execve 函数加载并运行可执行目标文件 filename,且带参数列表 argv 和环境变量列表 envp。只有当出现错误时,execve 才会返回到调用程序。execve 调用一次并从不返回。

csapp8.19

main 开始在一个 32 位 Linux 进程中执行时,用户栈有如下图所示的组织结构。

csapp8.21

程序与进程

程序是一堆代码和数据;程序可以作为目标模块存在于磁盘上,或者作为段存在于地址空间中。进程执行中程序的一个具体的实例;程序总是运行在某个进程的上下文中。fork函数在新的子进程中运行相同的程序,新的子进程是父进程的一个复制品。execve 函数在当前进程的上下文中加载并运行一个新的程序,会覆盖当前进程的地址空间,但并没有创建一个新进程。新的程序仍然拥有相同的 PID,并且继承了调用 execve 函数时已打开的所有文件描述符。

利用 fork 和 execve 运行程序

Shell 是一个交互型的应用级程序,它代表用户运行其他程序。最早的 shell 是 sh 程序,后面出现了一些变种,比如 csh, tcsh, ksh 和 bash。Shell 执行一系列的**读/求值(read/evaluate)**步骤,然后终止。读步骤读取来自用户的一个命令行。求值步骤解析命令行,并代表用户运行程序。

信号

一个信号就是一条小消息,它通知进程系统中发生了一个某种类型的事件。下图是 Linux 系统支持的 30 种不同类型的信号。在 shell 中输入 man 7 signal 就能得到这个列表。

csapp8.25

每种信号类型都对应于某种系统事件。低层的硬件异常是由内核异常处理程序处理的,正常情况下,对用户进程而言是不可见的。信号提供了一种机制,通知用户进程发生了这些异常。比如,如果一个进程试图除以 0,那么内核就发送给他一个 SIGFPE 信号(8)。其他信号对应于内核或者其他用户进程中较高层的软件事件。比如,如果当进程在前台运行时,按下 ctrl-c,那么内核就会发送一个 SIGINT 信号(2)给这个前台进程。

信号术语

传送一个信号到目的进程是由两个不同步骤组成的:

  • 发送信号。内核通过更新目的进程上下文中的某个状态,发送一个信号给目的进程。发送信号可以用如下两个原因:1)内核检测到一个系统事件,比如被零除错误或者子进程终止。2)一个进程调用 kill 函数,显式地要求内核发送一个信号给目的进程。一个进程可以发送信号给它自己。
  • 接收信号。当目的进程被内核强迫以某种方式对信号的发送做出反应时,目的进程就接收了信号。进程可以忽略这个信号,终止或者通过执行一个称为**信号处理程序(signal handler)**的用户层函数捕获这个信号。如下图所示

csapp8.26

一个只发出而没有被接收的信号叫做待处理信号(pending signal)。在任何时刻,一种类型至多只会有一个待处理信号。如果一个进程有一个类型为 k 的待处理信号,那么任何接下来发送到这个进程的类型为 k 的信号都不会排队等待,它们只是被简单地丢弃。一个进程可以有选择地阻塞接收某种信号。当一种信号被阻塞时,它仍可以被发送,但是产生的待处理信号不会被接收,直到进程取消对这种信号的阻塞。

一个待处理信号最多只能被接收一次。内核为每个进程在 pending 位向量中维护着待处理信号的集合,而在 blocked 位向量中维护着被阻塞的信号集合。只要传送了一个类型为 k 的信号,内核就会设置 pending 中的第 k 位,而只要接收了一个类型为 k 的信号,内核就会清除 pending 中的第 k 位。

发送信号

Unix 系统提供了大量向进程发送信号的机制。所有这些机制都是基于**进程组(process group)**这个概念的。

进程组

每个进程都只属于一个进程组,进程组是由一个正整数进程组 ID 来标识的。getpgrp 函数返回当前进程的进程组 ID。

#include <unistd.h>

pid_t getpgrp(void);

默认的,一个子进程和它的父进程同属一个进程组。一个进程可以通过使用 setpgid 函数来改变自己或者其他进程的进程组,成功则返回 0,否则返回 -1。

#include <unistd.h>

int setpgid(pid_t pid, pid_t pgid);

用 /bin/kill 程序发送信号

/bin/kill 程序可以向另外的进程发送任意的信号。比如

unix> /bin/kill -9 15213

发送信号9(SIGKILL)给进程 15213。

从键盘发送信号

Unix shell 使用**作业(job)**这个抽象概念来表示为对一个命令行求值而创建的进程。在任何时刻,至多只有一个前台作业和 0 个或多个后台作业。比如:

unix> ls | sort

创建一个由两个进程组成的前台作业,这两个进程是通过 Unix 管道连接起来的:一个进程运行 ls 程序,另一个运行 sort 程序。Shell 为每个作业创建一个独立的进程组。

用 kill 函数发送信号

进程通过调用 kill 函数发送信号给其他进程(包括它们自己)。如果 pid 大于零,那么 kill 函数发送信号 sig 给进程 pid。如果 pid 小于零,那么 kill 发送信号 sig 给进程组 abs(pid) 中的每个进程。

csapp8.28

用 alarm 函数发送信号

进程可以通过调用 alarm 函数向它自己发送 SIGALRM 信号。返回前一次闹钟剩余的秒数,若以前没有设定闹钟,则为 0。

#include <unistd.h>

unsigned int alarm(unsigned int secs);

接收信号

当内核从一个异常处理程序返回,准备将控制传递给进程 p 时,它会检查进程 p 的未被阻塞的待处理信号的集合(pending&~blocked)。如果这个集合为空(通常情况下),那么内核将控制传递到 p 的逻辑控制流中的下一条指令。

信号处理问题

当一个程序要补货多个信号时,一些细微的问题就产生了:

  • 待处理信号被阻塞
  • 待处理信号不会排队等待
  • 系统调用可以被中断

不可以用信号来对其他进程中发生的事件计数。

可移植的信号处理

不同系统之间,信号处理语义的差异是 Unix 信号处理的一个缺陷。为了处理这个问题,Posix 标准定义了 sigaction 函数,它允许用户明确指定他们想要的信号处理语义。

显式地阻塞和取消阻塞信号

使用 sigprocmask 函数

同步流以避免讨厌的并发错误

竞争(race),经典同步错误

非本地跳转

C 语言提供了一种用户级一场控制流形式,称为非本地跳转(nonlocal jump),它将控制直接从一个函数转移到另一个当前正在执行的函数,而不需要经过正常的调用——返回序列,通过 setjmplongjmp 函数来提供的。

#include <setjmp.h>

int setjmp(jmp_buf env);
int sigsetjmp(sigjmp_buf env, int savesigs);

setjmp 函数在 env 缓冲区中保存当前调用环境,以供后面 longjmp 使用,并返回 0。调用环境包括程序计数器、栈指针和通用目的寄存器。

#include <setjmp.h>

void longjmp(jmp_buf env, int retval);
void siglongjmp(sigjmp_buf env, int retval);

longjmp 函数从 env 缓冲区中恢复调用环境,然后触发一个从最近一次初始化 env 的 setjmp 调用的返回。然后 setjmp 返回,并带有非零的返回值 retval。

setjmp 函数只被调用一次,但是返回多次:一次是当第一次调用 setjmp,而调用环境保存在缓冲区 env 时;一次是为每个相应的 longjmp 调用。另一方面,longjmp 函数被调用一次,但从不返回。

非本地跳转的一个重要应用就是允许从一个深层嵌套的函数调用中立即返回,通常是由检测到某个错误情况引起的。如果在一个深层嵌套的函数调用中发现了一个错误,我们可以使用非本地跳转直接返回到一个普通的本地化的错误处理程序,而不是费力地解开调用栈。

非本地跳转的另一个重要应用是使一个信号处理程序分支到一个特殊的代码位置,而不是返回到被信号到达中断了的指令的位置。

csapp8.39

操作进程的工具

Linux 系统提供了大量的监控和操作进程的有用工具:

  • STRACE:打印一个正在运行的程序和它的子进程调用的每个系统调用的轨迹。用 -static 编译你的程序,能得到一个更干净的、不带有大量与共享库相关的输出的 trace
  • PS:列出当前系统中的进程(包括僵死进程)
  • TOP:打印出关于当前进程资源使用的信息
  • PMAP:显示进程的存储器映射
  • /proc:一个虚拟文件系统,以 ASCII 文本格式输出大量内核数据结构的内容,用户可以读取这些内容

小结

异常控制流(ECF)发生在计算机系统的各个层次,是计算机系统中提供并发的基本机制。

在硬件层,异常是由处理器中的事件触发的控制流中的突变。控制流传递给一个软件处理程序,该处理程序进行一些处理,然后返回控制给被中断的控制流。

有四种不同类型的异常:中断、故障、终止和陷阱。

在操作系统层,内核用 ECF 提供进程的基本概念。进程提供给应用两个重要的抽象:1)逻辑控制流,它提供给每个程序一个假象,好像它是在独占地使用处理器,2)私有地址空间,它提供给每个程序一个假象,好像它是在独占地使用主存。

在操作系统和应用程序之间的接口处,应用程序可以创建子进程,等待它们的子进程停止或者终止,运行新的程序,以及不活来自其他进程的信号。信号处理的语义是微妙的,并且随着系统不同而不同。然而,在与 Posix 兼容的系统上存在着一些机制,允许程序清楚地指定期望的信号处理语义。

虚拟存储器

一个系统中的进程是与其他进程共享 CPU 和主存资源的。然而,共享主存会形成一些特殊的挑战。随着对 CPU 需求的增长,进程以某种合理的平滑方式慢了下来。但是如果太多的进程需要太多的存储器,那么它们中的一些就根本无法运行。当一个程序没有空间可用时,那就是它运气不好了。存储器还很容易被破坏。如果某个进程不小心写了另一个进程使用的存储器,它就可能以某种完全和程序逻辑无关的令人迷惑的方式失败。

为了更加有效地管理存储器并且少出错,现代系统提供了一种对主存的抽象概念,叫做虚拟存储器(VM)。虚拟存储器是硬件异常、硬件地址翻译、主存、磁盘文件和内核软件的完美交互,它为每个进程提供了一个大的、一致的和私有的地址空间。通过一个很清晰的机制,虚拟存储器提供了三个重要的能力:1)它将主存看成是一个存储在磁盘上的地址空间的高速缓存,在主存中只保存活动区域,并根据需要在磁盘和主存之间来回传送数据,通过这种方式,它高效地使用了主存。2)它为每个进程提供了一致的地址空间,从而简化了存储器管理。3)它保护了每个进程的地址空间不被其他进程破坏。

虚拟存储器是计算机系统最重要的概念之一。它成功的一个主要原因就是因为它是沉默地、自动地工作的,不需要应用程序员的任何干涉。

物理和虚拟寻址

计算机系统的主存被组织成一个由 M 个连续的字节大小的单元组成的数组。每字节都有一个唯一的物理地址(Physical Address, PA)。第一个字节的地址为 0,接下来的字节地址为 1,再下一个为 2,以此类推。给定这种简单的结构,CPU 访问存储器的最自然的方式就是使用物理地址。我们把这种方式称为物理寻址(physical addressing)。如下图所示

csapp9.1

当 CPU 执行这条加载指令时,它会生成一个有效物理地址,通过存储器总线,把它传递给主存。主存取出从物理地址 4 处开始的 4 字节的字,并将它返回给 CPU,CPU 会将它存放在一个寄存器里。

早起的 PC 使用 物理寻址,现代处理器使用的是一种称为**虚拟寻址(virtual addressing)**的寻址形式,如下图所示:

csapp9.2

使用虚拟寻址时,CPU 通过生成一个虚拟地址(Virtual Address, VA)来访问主存,这个虚拟地址在被送到存储器之前先转换成适当的物理地址。将一个虚拟地址转换为物理地址的任务叫做地址翻译(address translation)。就像异常处理一样,地址翻译需要 CPU 硬件和操作系统之间的紧密合作。CPU 芯片上叫做**存储器管理单元(Memory Management Unit, MMU)**的专用硬件,利用存放在主存中的查询表来动态翻译虚拟地址,该表的内容是由操作系统管理的。

地址空间

地址空间(address space)是一个非负整数地址的有序集合:{0, 1, 2, …}。如果地址空间中的整数是连续的,那么我们说它是一个线性地址空间(linear address space)

地址空间的概念是很重要的,因为它清楚地区分了数据对象(字节)和它们的属性(地址)。

虚拟存储器作为缓存的工具

概念上而言,虚拟存储器(VM)被组织为一个由存放在磁盘上的 N 个连续的字节大小的单元组成的数组。每字节都有一个唯一的虚拟地址,这个唯一的虚拟地址是作为到数组的索引的。VM 系统通过将虚拟存储器分割为虚拟页(Virtual Page, VP)的大小固定的块来处理这个问题。每个虚拟页的大小为 P=2^p 字节。类似地,物理存储器被分割为物理页(Physical Page, PP),大小也为 P 字节(物理页也称为页帧(page frame))。

在任意时刻,虚拟页面的集合部分都分为三个不相交的子集:

  • 未分配的:VM 系统还未分配(或者创建)的页。未分配的块没有任何数据和它们相关联,因此也就不占用任何磁盘空间。
  • 缓存的:当前缓存在物理存储器中的已分配页。
  • 未缓存的:没有缓存在物理存储器中的已分配页。

csapp9.3

DRAM 缓存的组织结构

这里用SRAM 缓存来表示位于 CPU 和主存之间的 L1, L2 和 L3 高速缓存,并且用DRAM 缓存来表示虚拟存储器系统的缓存,它在主存中缓存虚拟页。

DRAM 缓存的组织结构完全是由巨大的不命中开销驱动的。因为大的不命中处罚和访问第一字节的开销,虚拟页往往很大,典型地是 4KB-2MB。由于大的不命中处罚,DRAM 缓存是全相连的,也就是说,任何虚拟页都可以放置在任何的物理页中。不命中时的替换策略也很重要,因为替换错了虚拟页的出发也非常高。因此,与硬件对 SRAM 缓存相比,操作系统对 DRAM 缓存使用了更复杂精密的替换算法。最后,因为对磁盘的访问时间很长,DRAM 缓存总是使用写回(write back),而不是直写。

页表

同任何缓存一样,虚拟存储器系统必须有某种方法来判定一个虚拟页是否存放在 DRAM 中的某个地方。如果是,系统还必须确定这个虚拟页存放在哪个物理页中。如果不命中,系统必须判断这个虚拟页存放在磁盘的哪个位置,在物理存储器中选择一个牺牲页,并将虚拟页从磁盘拷贝到 DRAM 中,替换这个牺牲页。

这些功能是由许多软硬件联合提供的,包括操作系统软、MMU(存储器管理单元)中的地址翻译硬件和一个存放在物理存储器中叫做**页表(page table)**的数据结构,页表将虚拟页映射到物理页。每次地址翻译硬件将一个虚拟地址转换为物理地址时都会读取页表。操作系统负责维护页表的内容,以及在磁盘与 DRAM 之间来回传送页。

下图展示了一个页表的基本组织结构。页表就是一个**页表条目(Page Table Entry, PTE)**的数组。虚拟地址空间中的每个页在页表中一个固定偏移量处都有一个 PTE。

csapp9.4

页命中

csapp9.5

缺页

DRAM 缓存不命中称为缺页(page fault)。在虚拟存储器的习惯说法中,块被称为页。在磁盘和存储器之间传送页的活动叫做交换(swapping)或者页面调度(paging)

csapp9.6

csapp9.7

分配页面

csapp9.8

又是局部性救了我们

尽管在整个运行过程中程序引用的不同页面的总数可能超出物理存储器总的大小,但是局部性原则保证了在任意时刻,程序往往在一个较小的活动页面(active page)集合上工作,这个集合叫做工作集(working set)或者常驻集(resident set)

虚拟存储器作为存储器管理的工具

操作系统为每个进程提供了一个独立的页表,因为也就是一个独立的虚拟地址空间。如下图所示:

csapp9.9

虚拟存储器作为存储器保护的工具

如果一条指令违反了许可操作,那么 CPU 就出发一个一般保护故障,将控制传递给一个内核中的异常处理程序。Unix shell 一般将这种异常报告为段错误(sgmentation fault)

csapp9.10

地址翻译

地址翻译的基础知识。

csapp9.11

csapp9.12

后面的暂略,几乎很少接触

系统级 I/O

输入/输出是在主存和外部设备之间拷贝数据的过程。所有语言的运行时系统都提供执行 I/O 的较高级别的工具。

Unix I/O

一个 Unix 文件就是一个 m 字节的序列。所有的 I/O 设备,如网络、磁盘和终端,都被模型化为文件,而所有的输入和输出都被当作对相应文件的读和写来执行。这种将设备优雅地映射为文件的方式,允许 Unix 内核引出一个简单、低级的应用接口,称为 Unix I/O,这使得所有的输入和输出都能以一种统一且一致的方式来执行:

  • 打开文件:一个应用程序通过要求内核打开相应的文件,来宣告它想要访问一个 I/O 设备。内核返回一个小的非负整数,叫做描述符,它在后续对此文件的所有操作中标识这个文件。内核记录有关这个打开文件的所有信息。应用程序只需记住这个描述符。
  • 改变当前的文件位置。
  • 读写文件
  • 关闭文件

打开和关闭文件

进程是通过调用 open 函数来打开一个已存在的文件或者创建一个新文件的。若成功则返回新文件描述符,否为返回 -1。

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

int open(char *filename, int flags, mode_t mode);

进程通过调用 close 函数关闭一个打开的文件。若成功则返回 0,否则 -1。

#include <unistd.h>

int close(int fd);

读和写文件

应用程序是通过分别调用 readwrite 函数来执行输入和输出的。

#include <unistd.h>

ssize_t read(int fd, void *buf, size_t n);
ssize_t write(int fd, const void *buf, size_t n);

用 RIO 包健壮地读写

提供两类不同的函数:无缓冲的输入输出函数与带缓冲的输入函数。

读取文件元数据

应用程序能够通过调用 statfstat 函数,检索到关于文件的信息,有时也称为文件的元数据(metadata)

#include <unistd.h>
#include <sys/stat.h>

int stat(const char *filename, struct stat *buf);
int fstat(int fd, struct stat *buf);

csapp10.8

共享文件

可以用许多不同的方式来共享 Unix 文件。内核用三个相关的数据结构来表示打开的文件:

  • 描述符表(descriptor table)。每个进程都有它独立的描述符表,它的表项是由进程打开的文件描述符来索引的。每个打开的描述符表指向文件表中的一个表项。
  • 文件表(file table)。打开文件的集合是由一张文件表来表示的,所有的进程共享这张表。每个文件表的表项包括当前的文件位置、**引用计数(reference count),以及一个指向 v-node 表中对应表项的指针。
  • v-node 表(v-node table)。同文件表一样,所有的进程共享这张表。每个表项包含 stat 结构中的大多数信息。

csapp10.11

csapp10.12

csapp10.13

I/O 重定向

Unix shell 提供了 I/O 重定向操作符,允许用户将磁盘文件和标准输入输出联系起来,例如

unix> ls > foo.txt

csapp10.14

标准 I/O

ANSI C 定义了一组高级输入输出函数,称为标准 I/O 库,为程序员提供了 Unix I/O 的较高级别的替代。这个库(libc)提供了打开和关闭文件的函数(fopenfclose),读和写字节的函数(freadfwrite),读和写字符串的函数(fgetsfputs),以及复杂的格式化的 I/O 函数(scanfprintf)。

标准 I/O 库将一个打开的文件模型化为一个。对于程序员而言,一个流就是一个指向 FILE 类型的结构的指针。

综合:该使用哪些 I/O 函数

csapp10.15

标准 I/O 流,从某种意义上而言是全双工的,因为程序能够在同一个流上执行输入和输出。然而,对流的限制和对套接字的限制,有时候会互相冲突:

  • 限制一:跟在输出函数之后的输入函数。如果中间没有插入对 fflush, fseek, fsetpos 或者 rewind 的调用,一个输入函数不能跟随在一个输出函数之后。fflush 函数清空与流相关的缓冲区。后三个函数使用 Unix I/O lseek 函数来重置当前的文件位置。
  • 限制二:跟在输入函数之后的输出函数。如果中间没有插入对 fseek, fsetpos 或者 rewind 的调用,一个输出函数不能跟随在一个输入函数之后,除非该输入函数遇到了一个 EOF。

这些限制给网络应用带来了一个问题,因为对套接字使用 lseek 函数是非法的,所以在网络套接字上不要使用标准 I/O 进行输入和输出,而要使用健壮的 RIO 函数。

小结

Unix 提供了少量的系统级函数,它们允许应用程序打开、关闭、读和写文件,提取文件的元数据,以及执行 I/O 重定向。 Unix 的读和写操作会出现不足值,应用程序必须能正确地预计和处理这种情况。应用程序不应直接调用 Unix I/O 函数,而应该使用 RIO 包,RIO 包通过反复执行读写操作,直到传送完所有的请求数据,自动处理不足值。

Unix 内核使用三个相关的数据结构来表示打开的文件。描述符表中的表项指向打开文件表中的表项,而打开文件表中的表项又指向 v-node 表中的表项。

标准 I/O 库是基于 Unix I/O 实现的,并提供了一组强大的高级 I/O 例程。对于大多数应用程序而言,标准 I/O 更简单,是优于 Unix I/O 的选择。然而,因为对标准 I/O 和网络文件的一些相互不兼容的限制,Unix I/O 比标准 I/O 更适用于网络应用程序。

网络编程

网络应用随处可见。有趣的是,所有的网络应用都是基于相同的基本编程模型,有着相似的整体逻辑结构,并且一来相同的编程接口。

网络应用依赖于很多在系统研究正已经学习过的概念,例如,进程、信号、字节顺序、存储器映射以及动态存储分配,都扮演着重要的角色。

客户端-服务器编程模型

每个网络应用都是基于客户端-服务器模型模型的。采用这个模型,一个应用是由一个服务器进程和一个或者多个客户端进程组成。服务器管理某种资源,并且通过操作这种资源来为它的客户端提供某种服务

客户端-服务器模型中的基本操作是事务(transaction),由四步组成,如下图所示:

csapp11.1

网络

客户端和服务器通常运行在不同的主机上,并且通过计算机网络的硬件和软件资源来通信。对于一台主机而言,网络只是又一种 I/O 设备,作为数据源和数据接收方,如下图所示。

csapp11.2

物理上而言,网络是一个按照地理远近组成的层次系统。最底层是 LAN(Local Area Network, 局域网),在一个建筑或者校园范围内。迄今为止,最流行的局域网技术是以太网(Ethernet)

每个以太网适配器都有一个全球唯一的 48 位地址,一台主机可以发送一段位,称为帧(frame),到这个网段内的其他任何主机。每个帧包括一些固定数量的头部(header)位,用来标识此帧的源和目的地址以及此帧的长度,伺候紧随的就是数据位的有效载荷。每个主机适配器都能看到这个帧,但是只有目的主机实际读取它。

使用一些电缆和叫做网桥(bridge)的小盒子,多个以太网段可以连接成较大的局域网,称为**桥接以太网(bridged Ethernet),如下图所示:

csapp11.4

在层次更高的级别中,多个不兼容的局域网可以通过叫做路由器(router)的忒书计算机连接起来,组成一个internet(互联网络)

csapp11.6

协议软件消除了不同网络之间的差异,必须具备两种基本能力:命名机制和传送机制。

每台因特网主机都运行实现 **TCP/IP 协议(Transmission Control Protocol/Internet Protocol)**的软件,几乎每个现代计算机系统都支持这个协议。

csapp11.8

TCP/IP 实际上是一个协议族,其中每一个都提供不同的功能。从程序员角度,我们可以把因特网看做一个世界范围的主机集合,满足以下特性:

  • 主机集合被映射为一组 32 位的 IP 地址
  • 这组 IP 地址被映射为一组称为**因特网域名(Internet domain name)**的标识符
  • 因特网主机上的进程能够通过**连接(connection)**和任何其他因特网主机上的进程通信

IP 地址

一个 IP 地址就是一个 32 位无符号整数。IP 地址通常是以一种称为点分十进制表示法来表示的,这里,每个字节由它的十进制值表示,并且用句点和其他字节间分开。

因特网程序使用 inet_atoninet_ntoa 函数来实现 IP 地址和点分十进制串之间的转换

#include <arpa/inet.h>

int inet_aton(const char *cp, struct in_addr *inp);
char *inet_ntoa(struct in_addr in);

n 表示网络(network),a 表示应用(application)。

因特网域名

域名集合形成了一个层次结构,每个域名编码了它在这个层次中的位置。

csapp11.10

因特网连接

因特网客户端和服务器通过在连接上发送和接收字节流来通信。从连接一对进程的意义上而言,连接是点对点的。从数据可以同时双向流动的角度来说,它是全双工的。并且由源进程发出的字节流最终被目的进程以它发出的顺序收到它的角度来说,它是可靠的。

一个套接字是连接的一个端点。每个套接字都有相应的套接字地址,是由一个因特网地址和一个 16 位的整数端口组成的,用地址:端口来表示。当客户端发起一个连接请求时,客户端套接字地址中的端口是由内核自动分配的,称为临时端口(ephemeral port)。然而,服务器套接字地址中的端口通常是某个知名的端口,是和这个服务相对应的。例如,Web 服务器通常使用端口 80,而电子邮件服务器使用端口 25。在 Unix 机器上,文件 /etc/services 包含一张这台机器提供的服务以及它们的知名端口号的综合列表。

一个连接由它两端的套接字地址唯一确定。这对套接字地址叫做套接字对(socket pair),由下列元组来表示:

(cliaddr:cliport, servaddr:servport)

csapp11.13

套接字接口

**套接字接口(socket interface)**是一组函数,它们和 Unix I/O 函数结合起来,用以创建网络应用。

csapp11.14

套接字地址结构

从 Unix 内核的角度来看,一个套接字就是通信的一个端点。从 Unix 程序的角度来看,套接字就是一个有相应描述符的打开文件。

socket 函数

客户端和服务器使用 socket 函数来创建一个套接字描述符(socket descriptor)

#include <sys/types.h>
#include <sys/socket.h>

int socket(int domain, int type, int protocol);

connect 函数

客户端通过调用 connect 函数来建立和服务器的连接。

#include <sys/socket.h>

int connect(int sockfd, struct sockaddr *serv_addr, int addrlen);

剩下还有bind, listen, accept 等函数,略

Web 服务器

Web 基础

Web 客户端和服务器之间的交互用的是一个基于文本的应用级协议,叫做 HTTP(Hypertext Transfer Protocol)。HTTP 是一个简单的协议。一个 Web客户端打开一个到服务器的因特网连接,并且请求某些内容。服务器响应所请求的内容,然后关闭连接。浏览器读取这些内容,并把它显示在屏幕上。

Web 内容

对于 Web 客户端和服务器而言,内容是一个与 MIME(Multipurpose Internet Mail Extensions)类型相关的字节序列。

csapp11.22

Web 服务器以两种不同的方式向客户端提供内容:

  • 取一个磁盘文件,并将它的内容返回给客户端。磁盘文件称为静态内容(static content),而返回文件给客户端的过程称为服务静态内容(serving static content)
  • 运行一个可执行文件,并将它的输出返回给客户端。运行时可执行文件产生的输出称为动态内容(dynamic content),而运行程序并返回它的输出到客户端的过程称为服务动态内容(serving dynamic content)

每条由 Web 服务器返回的内容都是和它管理的某个文件相关联的。这些文件中的每一个都有一个唯一的名字,叫做 URL(Universal Resource Locator)。

关于服务器如何解释一个 URL 的后缀,以下几点需要理解:

  • 确定一个 URL 指向的是静态内容还是动态内容没有标准的规则。每个服务器对它所管理的文件都有自己的规则。一种常见方法是,确定一组目录,例如 cgi-bin,所有的可执行文件都必须存放这些目录中。
  • 后缀中的最开始的那个 / 不表示 Unix 的根目录。相反,它表示的是被请求内容类型的主目录。例如,可以将一个服务器配置成这样:所有的静态内容存放在目录 /usr/httpd/html 下。
  • 最小的 URL 后缀是 / 字符,所有服务器将其扩展为某个默认的主页,例如 /index.html。这解释了为什么在浏览器中键入一个域名就可以取出一个网站的主页。浏览器在 URL 后添加缺失的 /,之后服务器把 / 扩展到某个默认的文件名。

HTTP 事务

因为 HTTP 是基于在因特网连接上传送的文本行的,我们可以使用 Unix 的 TELNET 程序来和因特网上的任何 Web 服务器执行事务。

csapp11.23

HTTP 请求

一个 HTTP 请求的组成是这样的:一个请求行(request line)(line 5),后面跟随零个或更多个请求报头(request header)(line 6),在跟随一个空的文本行来终止报头列表(line 7)。一个请求行的形式是

<method> <url> <version>

HTTP 支持不同的方法,包括 GET, POST, OPTIONS, HEAD, PUT, DELETE 和 TRACE。主要应用的是 GET 方法。

HTTP 响应

HTTP 响应和 HTTP 请求是相似的。一个 HTTP 响应的组成是这样的:一个响应行(response line)(line 8)后面跟随着零个或者更多的响应报头(response header)(line 9-13),再跟随一个终止报头的空行(line 14),在跟随一个响应主体(response body)(line 15-17)。一个响应行的格式是

<version> <status code> <status message>

版本字段描述的是响应所遵循的 HTTP 版本。**状态码(status code)**是一个三位数的正整数,指明对请求的处理。**状态消息(status message)**给出与错误代码等价的英文描述。第9-13行的响应报头提供了关于响应的附加信息。针对我们的目的,两个最重要的报头是 Content-Type(line 12),它告诉客户端响应主体中内容 MIME 类型;以及 Content-Length(line 13),用来指示响应主体的字节大小。

csapp11.24

小结

Web 服务器使用 HTTP 协议和它们的客户端彼此通信。浏览器向服务器请求静态或者动态内容。CGI 标准提供了一组规则,来管理客户端如何将程序参数传递给服务器,服务器如何将这些参数以及其他信息传递给子进程,以及子进程如何将它的输出发送会客户端。

并发编程

应用级并发在以下情况下很有用:

  • 访问慢速 I/O 设备
  • 与人交互
  • 通过推迟工作以降低延迟
  • 服务多个网络客户端
  • 在多核机器上进行并行计算

使用应用级并发的应用程序称为并发程序(concurrent program)。现代操作系统提供了三种基本的构造并发程序的方法:

  • 进程。用这种方法,每个逻辑控制流都是一个进程,由内核来调度和维护。因为进程有独立的虚拟地址空间,想要和其他流通信,控制流必须使用某种显式的**进程间通信(interprocess communication, IPC)机制。
  • I/O 多路复用。在这种形式的并发编程中,应用程序在一个进程的上下文中显式地调度它们自己的逻辑流。逻辑流被模型化为状态机,数据到达文件描述符后,主程序显式地从一个状态转换到另一个状态。因为程序是一个单独的进程,所以所有的流都共享同一个地址空间。
  • 线程。线程是运行在一个单一进程上下文中的逻辑流,由内核进行调度。你可以把线程看成是其他两种方式的混合体,像进程流一样由内核进行调度,而像 I/O 多路复用一样共享同一个虚拟地址空间。

基于进程的并发编程

构造并发程序最简单的方法就是用进程,使用那些大家都很熟悉的函数,像 fork, execwaitpid

csapp12.1

csapp12.2

csapp12.3

csapp12.4

对于在父、子进程间共享状态信息,进程有一个非常清晰的模型:共享文件表,但是不共享用户地址空间。进程有独立的地址空间既是优点也是缺点。这样一来,一个进程不可能不小心覆盖另一个进程的虚拟存储器,这就消除了许多令人迷惑的错误。

另一方面,独立的地址空间使得进程共享状态信息变得更加困难。为了共享信息,它们必须使用显式的 IPC 机制。基于进程的设计的另一个缺点是,它们往往比较慢,因为进程控制和 IPC 的开销很高。

基于 I/O 多路复用的并发编程

I/O 多路复用可以用作并发事件驱动(event-driven)程序的基础,在事件驱动程序中,流是因为某种事件而前进的。一般概念是将逻辑流模型化为状态机。不严格地说,一个状态机(state machine)就是一组状态(state)输入事件(input event)转移(transition),其中转移就是将状态和输入事件映射到状态。每个状态都将一个(输入状态,输入事件)对映射到一个输出状态。**自循环(self-loop)**是同一组输入和输出状态之间的转移。通常把状态机花城有向图,其中节点表示状态,有向弧表示转移,而弧上的标号表示输入事件。一个状态机从某种初始状态开始执行。每个输入事件都会引发一个从当前状态到下一状态的转移。

事件驱动设计的一个优点是,它比基于进程的设计给了程序员更多的对程序行为的控制。另一个优点是在流之间共享数据变得很容易,而且事件驱动设计常常比基于进程的设计要高效得多,因为它们不需要进程上下文切换来调度新的流。

事件驱动设计的一个明显的缺点就是编码复杂,另一重大缺点时它们不能充分利用多核处理器。

基于线程的并发编程

线程(thread)就是运行在进程上下文中的逻辑流,由内核自动调度。每个线程都有它自己的线程上下文(thread context),包括一个唯一的整数线程ID(Thread ID, TID)、栈、栈指针、程序计数器、通用目的寄存器和条件码。所有的运行在一个进程里的线程共享该进程的整个虚拟地址空间。

csapp12.12

多线程程序中的共享变量

从一个程序员的角度来看,线程很有吸引力的一个方面就是多个线程很容易共享相同的程序变量。然而,这种共享也是很棘手的。

线程存储器模型

一组并发线程运行在一个进程的上下文中。每个线程都有它自己独立的线程上下文,包括线程 ID、栈、栈指针、程序计数器、条件码和通用目的寄存器。每个线程和其他线程一个共享进程上下文的剩余部分。这包括整个用户虚拟地址空间,它是由只读文本(代码)、读/写数据、堆以及所有的共享库代码和数据区域组成的。

从实际操作的角度来说,让一个线程去读写另一个线程的寄存器是不可能的。寄存器是从不共享的,而虚拟存储器总是共享的。

将变量映射到存储器

线程化的 C 程序中变量根据它们的存储类型被映射到虚拟存储器:

  • 全局变量:在运行时,虚拟存储器的读/写区域只包含每个全局变量的一个实例,任何线程都可以引用
  • 本地自动变量:定义在函数内部但是没有 static 属性的变量。在运行时,每个线程的栈都包含它自己的所有本地自动变量的实例
  • 本地静态变量:定义在函数内部并有 static 属性的变量,和全局变量一样

用信号量同步线程

共享变量是十分方便的,但是它们也引入了**同步错误(synchronization error)**的可能性。一般而言,你没有办法预测操作系统是否将为你的线程选择一个正确的顺序。

一些关键词:进度图,信号量,使用信号量来实现互斥,生产者-消费者问题,两类读者-写者问题

其他并发问题

这些典型问题是任何类型的并发流操作共享资源时都会出现的。

线程安全

四个(不相交的)线程不安全函数类:

  • 不保护共享变量的函数
  • 保持跨越多个调用的状态的函数
  • 返回指向静态变量的指针的函数
  • 调用线程不安全函数的函数

可重入性

其特点在于当被多个线程调用时,不会引入任何共享数据。

csapp12.37

在线程化的程序中使用已存在的库函数

大多数 Unix 函数,包括定义在标准 C 库中的函数都是线程安全,只有一小部分是例外:

csapp12.39

竞争

当一个程序的正确性依赖于一个线程要在另一个线程达到 y 点之前达到它的控制流中的 x 点时,就会发生竞争(race)

死锁

指的是一组线程被阻塞了,等待一个永远也不会为真的条件。进度图对于理解死锁是一个无价的工具。

csapp12.42

csapp12.43

重叠的禁止区域引起了一组称为**死锁区域(deadlock region)**的状态。

小结

无论哪种并发机制,同步对于共享数据的并发访问都是一个困难的问题。提出对信号的 P 和 V 操作就是为了帮助解决这个问题。信号量操作可以用来提供对共享数据的互斥访问,也对诸如生产者-消费者程序中有限缓冲区和读者-写者系统中的共享对象这样的资源访问进行调度。

并发也引入了其他一些困难的问题。被线程调用的函数必须具有一种称为线程安全的属性。竞争和死锁是并发程序中出现的另一些困难的问题。当程序员错误地假设逻辑流该如何调度时,就会发生竞争。当一个流等待一个永远不会发生的事件时,就会产生死锁。