csapp阅读笔记

笔记规范

这样表示一些强调和自己的注释

这样表示一些强调和自己的注释

前言

其他的系统类书籍都是从$\color{green}{\text{构建者}}$的角度来写的，讲述如何实现硬件或系统软件，包括操作系统、编译器和网络接口。而本书是从$\color{green}{\text{程序员}}$的角度来写的，讲述应用程序员如何能够利用系统知识来编写出更好的程序。

本书的重点是执行 x86-64 机器代码的系统。

所幸的是，C 是一个较小的语言，在 Brian Keraighan 和 Dermis Ritchie 经典的“K&R”文献中得到了清晰优美的描述[61]。

计算机系统漫游

信息就是位+ 上下文

C 编程语言的起源
C语言与 Unix 操作系统关系密切
C语言小而简单
C语言是为实践目的设计的

高速缓存至关重要

这个简单的示例揭示了一个重要的问题，即系统花费了大量的时间把信息从一个地方挪到另一个地方。hello 程序的机器指令最初是存放在磁盘上，当程序加载时，它们被复制到主存；当处理器运行程序时，指令又从主存复制到处理器。相似地，数据串“hello,world\n”开始时在磁盘上，然后被复制到主存，最后从主存上复制到显示设备。从程序员的角度来看，这些$\color{green}{\text{复制}}$就是$\color{green}{\text{开销}}$，减慢了程序“真正”的工作。因此，系统设计者的一个主要目标就是使这些复制操作尽可能快地完成。

就好像程序间值拷贝会占据非常大的时间一样

本书得出的重要结论之一就是，意识到高速缓存存储器存在的应用程序员能够利用高速缓存将程序的性能提高一个数量级。

操作系统管理硬件

让我们回到 hello程序的例子。当 shell 加载和运行 hello 程序时，以及 hello 程序输出自己的消息时，shell 和 hello 程序都没有
直接访问键盘、显示器、磁盘或者主存。取而代之的是，它们依靠操作系统提供的服务。我们可以把操作系统看成是应用程序和硬件之间插人的一层软件，如图 1-10 所示。所有应用程序对硬件的操作尝试都必须通过操作系统。

操作系统有两个基本功能：（1)防止硬件被失控的应用程序滥用；（2)向应用程序提供简单一致的机制来控制复杂而又通常大不相同的低级硬件设备。操作系统通过几个基本的抽象概念（进程、虚拟内存和文件）来实现这两个功能。如图 1-11 所示，文件是对I/O 设备的抽象表示，虚拟内存是对主存和磁盘 I/O 设备的抽象表示，进程则是对处理器、主存和 I/O 设备的抽象表示。我们将依次讨论每种抽象表示。

图 1-11 操作系统提供的抽象表示

进程

像 hello这样的程序在现代系统上运行时，操作系统会提供一种假象，就好像系统上只有这个程序在运行。程序看上去是独占地使用处理器、主存和 I/O设备。处理器看上去就像在不间断地一条接一条地执行程序中的指令，即该程序的代码和数据是系统内存中唯一的对象。这些假象是通过进程的概念来实现的，$\color{green}{\text{进程}}$是计算机科学中最重要和最成功的概念之一。

$\color{green}{\text{进程}}$是操作系统对一个正在运行的程序的一种$\color{green}{\text{抽象}}$。

线程

虚拟内存

文件

文件就是字节序列，仅此而已。

文件这个简单而精致的概念是非常强大的，因为它向应用程序提供了一个统一的视图，来看待系统中可能含有的所有各式各样的 I/O 设备。例如，处理磁盘文件内容的应用程序员可以非常幸福，因为他们无须了解具体的磁盘技术。进一步说，同一个程序可以在使用不同磁盘技术的不同系统上运行。

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

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

信息的处理和表示

例如，在今天的大多数计算机上(使用 32 位来表示数据类型 int),计算表达式 200 300 400 * 500 会得出结果-884 901 888。这违背了整数运算的特性，计算$\color{green}{\text{一组正数}}$的乘积不应产生一个$\color{green}{\text{负}}$的结果。

读者注：这里讲的是整数运算

另一方面，整数的计算机运算满足人们所熟知的真正整数运算的许多性质。例如，利用乘法的结合律和交换律，计算下面任何一个 C 表达式，都会得出结果- 884 901 888:

(500 400) (300 200)
((500 400) 300) 200
((200 500) 300) 400
(200 (300 * 500))

浮点运算有完全不同的数学属性。虽然溢出会产生特殊的值$+\infty$, 但是一组正数的乘积总是正的。由于表示的精度有限，浮点运算是不可结合的。例如，在大多数机器上，C表达式(3.14+1e20)-1e20 求得的值会是0.0，而 3.14+(le20-le20)求得的值会是 3.14。整数运算和浮点数运算会有不同的数学属性是因为它们处理数字表示有限性的方式不同棗整数的表示虽然只能编码一个相对较小的数值范围，但是这种表示是精确的；而浮点数虽然可以编码一个较大的数值范围，但是这种表示只是近似的。

浮点数表示范围较大，但是近似。整数表示范围小，但是这种表示是精确的

信息存储

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

在接下来的几章中，我们将讲述编译器和运行时系统是如何将存储器空间划分为更可管理的单元，来存放不同的程序对象（program object), 即程序数据、指令和控制信息。可以用各种机制来分配和管理程序不同部分的存储。这种管理完全是在虚拟地址空间里完成的。例如，C 语言中一个指针的值（无论它指向一个整数、一个结构或是某个其他程序对象)都是某个存储块的第一个字节的虚拟地址。C 编译器还把每个指针和类型信息联系起来，这样就可以根据指针值的类型，生成不同的机器级代码来访问存储在指针所指向位置处的值。尽管 C 编译器维护着这个类型信息，但是它生成的实际机器级程序并不包含关于数据类型的信息。每个程序对象可以简单地视为一个字节块，而程序本身就是一个字节序列。

C 编译器维护着这个类型信息，但是它生成的实际机器级程序并不包含关于数据类型的信息

在 C 语言中，以 0x 或 0X 开头的数字常量被认为是十六进制的值。字符A~F既可以是大写，也可以是小写。例如，我们可以将数字 $\text{FA1D37B}_{16}$写作 0xFA1D37B，或者0xfa1d37b，甚至是大小写混合，比如，0xFa1D37b。

字数据字长

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

这里跟王道考研书的定义不一样，王道考研的计算机字长是「指数据运算的基本单位长度，是计算机的位数」，感觉这里像是存储字长和操作系统的位数

32 位字长限制虚拟地址空间为 4 千兆字节(写作 4GB)

大多数 64 位机器也可以运行为 32 位机器编译的程序，这是一种向后兼容。

这里的后不是指「后代，更先进的机器」，而是指「落后，以前的旧机器」

因此，我们将程序称为“32 位程序”或 “64 位程序”时，区别在于该程序是如何编译的，而不是其运行的机器类型。

随着 64 位机器的日益普及，在将这些程序移植到新机器上时，许多隐藏的对字长的依赖性就会显现出来，成为错误。比如，许多程序员假设一个声明为 int 类型的程序对象能被用来存储一个指针。这在大多数 32 位的机器上能正常工作，但是在一台 64 位的机器上却会导致问题。

int在32位和64位系统中都是4字节，但是char * 在32位是4字节，在64位是8字节

寻址和字节顺序

对于跨越多字节的程序对象，我们必须建立两个规则：这个对象的地址是什么，以及在内存中如何排列这些字节。在几乎所有的机器上，多字节对象都被存储为连续的字节序列，对象的地址为所使用字节中最小的地址。

图片详情

大端法：人类书写时候的表示的顺序相同（人为大）

对于大多数应用程序员来说，其机器所使用的字节顺序是完全不可见的。无论为哪种类型的机器所编译的程序都会得到同样的结果。不过有时候，字节顺序会成为问题。首先是在不同类型的机器之间通过网络传送二进制数据时，一个常见的问题是当小端法机器产生的数据被发送到大端法机器或者反过来时，接收程序会发现，字里的字节成了反序的。为了避免这类问题，网络应用程序的代码编写必须遵守已建立的关于字节顺序的规则，以确保发送方机器将它的内部表示转换成网络标准，而接收方机器则将网络标准转换为它的内部表示。

这条指令是把一个字长的数据加到一个值上，该值的存储地址由0x200b43 加上当前程序计数器的值得到，当前程序计数器的值即为下一条将要执行指令的地址。

当前程序计数器的值即为下一条将要执行指令的地址

代码

还能将指针使用为字节数组
在C 语言中，我们能够用数组表示法来引用指针，同时我们也能用指针表示法来引用数组元素。在这个例子中引用 start[i]表示我们想要读取以 start 指向的位置为起始的第 i 个位置处的字节。

课本描述的结果

菜鸟在线工具的结果

浮点数和整数的字节码

表示字符串

Java 编程语言使用 Unicode 来表示字符串。对于.C 语言也有支持 Unicode 的程序库。

？还能对字符加减，和ascii一样的结果

表示代码

我们发现指令编码是不同的。不同的机器类型使用不同的且不兼容的指令和编码方式。即使是完全一样的进程，运行在不同的操作系统上也会有不同的编码规则，因此二进制代码是不兼容的。二进制代码很少能在不同机器和操作系统组合之间移植。

计算机系统的一个基本概念就是，从机器的角度来看，程序仅仅只是字节序列。机器没有关于原始源程序的任何信息，除了可能有些用来帮助调试的辅助表以外。在第 3 章学习机器级编程时，我们将更清楚地看到这一点。

布尔代数简介

^的逆元是这个数本身

C 语言中的位级运算

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

例如，表达式 a&&5/a 将不会造成被零除，而表达式 p&&*p++也不会导致间接引用空指针。

C 语言中的移位运算

C语言标准并没有明确定义对于有符号数应该使用哪种类型的右移— 算术右移或者逻辑右移都可以。不幸地，这就意味着任何假设一种或者另一种右移形式的代码都可能会遇到可移植性问题。然而，实际上，几乎所有的编译器/机器组合都对有符号数使用算术右移，且许多程序员也都假设机器会使用这种右移。另一方面，对于无符号数，右移必须是逻辑的。

逻辑右移补0，算术右移补最高位，算术右移使得它对有符号数和无符号数的扩展都不改变数的大小

与 C 相比，Java 对于如何进行右移有明确的定义。表达是 x>>k 会将 x 算术右移 k 个
位置，而 x>>>k 会对 x 做逻辑右移。

图片详情

java的右移会对移位取模

整数表示

整型数据类型

负数的范围比整数的范围大 1。当我们考虑如何表示负数的时候，会看到为什么会这样。

2-9 32程序c语言的类型取值

c标准和典型取值不一样(2-10,2-11)

C和C++都支持有符号(默认)和无符号数。Java只支持有符号数。

无符号数的编码

2-1 无符号数编码的定义

用条长理解无符号数的编码

无符号数编码的唯一性
函数$\text{B2U}_w$是一个双射

补码编码

2-3 补码的编码定义

补码的条状图表示

补码的范围是不对称的：$\lvert \text{TMin} \rvert = \lvert \text{TMax} \rvert + 1$是因为一半的位模式(符号位设置为 1 的数）表示负数，而另一半(符号位设置为0的数)表示非负数。因为0是非负数，也就意味着能表示的整数比负数少一个。

最大的无符号数值刚好比补码的最大值的两倍大一点：$\text{UMax}_w = 2\text{TMax}_w + 1$。补码表示中所有负数的位模式在无符号表示中都变成了正数。

注意-1和$\text{UMax}$有相同的位表示—一个全1的串。

数值0在两种表示方式中都是全0的串。

关于整数数据类型的取值范围和表示，Java 标准是非常明确的。它要求采用补码表示，取值范围与图 2-10 中 64 位的情况一样。在 Java 中，单字节数据类型称为 byte而不是 char这些非常具体的要求都是为了保证无论在什么机器上运行，Java 程序都能表现地完全一样。

我们将看到在浮点数中有使用原码编码。

图片详情

对于大多数 C 语言的实现，处理同样字长的有符号数和无符号数之间相互转换的一般规则是：数值可能会改变，但是位模式不变。

有符号数和无符号数的相互映射

由于 C 语言对同时包含有符号和无符号数表达式的这种处理方式，出现了一些奇特的行为。当执行一个运算时，如果它的一个运算数是有符号的而另一个是无符号的，那么 C语言会隐式地将有符号参数强制类型转换为无符号数，并假设这两个数都是非负的，来执行这个运算。就像我们将要看到的，这种方法对于标准的算术运算来说并无多大差异，但是对于像<和>这样的关系运算符来说，它会导致非直观的结果。

2-19 c语言的升级规则的效果(隐式类型转换导致的bool运算产生非自然语义性)

在进行布尔运算时，C语言会隐式地将有符号参数强制类型转换为无符号数
为什么tmin要写成-2147483647-1而不是-2147483648，按照补充材料描述的，c语言的编译器在遇到一个常数-X时，会按照一个$\color{green}{\text{规则}}$找到一个$\color{green}{\text{数据类型}}$把X先转换成能表示他$\color{green}{\text{这个数据类型}}$,常数-2147483648来按照这个$\color{green}{\text{规则}}$会在c90标准32位机器上变成unsigned数据类型，造成(-2147483648 > 0)的真值位1的情况

扩展一个数字的位表示

要将一个无符号数转换为一个更大的数据类型，我们只要简单地在表示的开头添加 0。这种运算被称为零扩展（zero extension), 表示原理如下

无符号数的零扩展

补码数的符号扩展

2-20补码数的符号扩展的直观表示

补码数值符号扩展的推导

值得一提的是，从一个数据大小到另一个数据大小的转换，以及无符号和有符号数字之间的转换的相对顺序能够影响一个程序的行为。考虑下面的代码：

图片详情

截断数字

无符号数的截断

补码的截断

该原理背后的直觉就是所有被截去的位其权重(The intuition behind this principle is simply that all of the bits that were
truncated have weights of the form)
这个地方感觉不应该翻译成直觉,中文的有一种「不知道为什么但是就是这样子」，英文语境下的intuition，往往是中文语境下的的这层含义「有一种显而易见的技巧」，重点在「显然」和「巧」上

这里的B2U啥的函数都可以理解为隐式类型转换