CSAPP读书笔记(书已看完，剩下的读书笔记都在心里（逃。。)

读书笔记

决定花时间温习一遍CSAPP，本文是 CSAPP《深入理解计算机系统》的读书笔记。

第一章 计算机系统漫游

编译系统的组成

编译系统组成

硬件系统的基本组成

  • 总线
  • I/O设备
  • 主存
  • 处理器

总线

总线每次传送定长的字节块，称作字(word)，字中的字节数称为字长。字长是系统的基本参数，它的大小在不同计算机中不尽相同，常见的字长有4(32 bits)和8(64 bits)。

I/O设备

每个I/O设备都通过一个控制器或适配器与I/O总线相连。

主存

主存在物理上由一组动态随机存取存储器(DRAM)芯片组成，逻辑上它是一个线性的字节数组，每个字节都有唯一的地址（数组索引），从0开始。

处理器

处理器是解释和执行存储在主存中指令的引擎，它的核心是一个大小为一个字的存储设备（寄存器），称作程序计数器(PC)，在任何时刻，PC都指向主存中的某条机器语言指令，即PC保存的是主存中的某个地址。由此很容易理解为何计算机可寻址的内存大小和它的字大小密切相关，因为PC的容量即是该处理器的字长，能保存的最大主存地址也就是一个字。比如字长为4字节的32位计算机最大寻址只能到4GB(2^32 = 4GB)。

处理器一直在不断地执行PC指向指令，接着更新PC，将其指向下一条指令，下一条指令的地址和刚被执行的上一条指令的地址不一定是相邻的。

处理器中包含一些拥有固定名字的寄存器，这些寄存器的大小是单个字长。

处理器在指令的要求下可能会执行下面几个典型的操作：

  • 加载：从主存复制一个字节或一个字到寄存器，覆盖寄存器中原来的值。
  • 存储：从寄存器复制一个字节或一个字到主存的某个位置，覆盖主存中这个位置原来的值。
  • 操作：把两个寄存器的内容复制到ALU做算术运算，并将结果存放到另一个寄存器中，覆盖这个寄存器中原来的值。
  • 跳转：从指令中提取一个字，并将这个字复制到PC中覆盖PC中原来的值。

存储器层次结构

存储器层次结构呈金字塔状。从上至下，设备的访问速度越来越慢，容量越来越大，单位字节的造价越来越低。存储器层次结构的主要思想是上一层存储器作为下一层存储器的高速缓存。如下图：

存储器层次结构

操作系统管理硬件

操作系统是介于硬件和应用程序之间的一层软件系统，所有应用程序对硬件的操作都必须经过操作系统。

计算机系统的分层视图

操作系统的两个基本功能是：

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

操作系统提供了三个抽象概念来实现这两个基本功能：

  • 进程
  • 虚拟内存
  • 文件

操作系统提供的抽象

进程

操作系统提供了一种假象：系统上只有这个进程在运行，使程序看上去独占处理器、主存和I/O设备。实际上在一个系统上可以同时运行多个进程，进程数是可以多于CPU个数的。CPU通过在进程间快速切换来给人以所有进程都在并发执行的假象。

为了达到CPU在进程间切换的效果，操作系统负责管理进程运行的上下文，上下文包括PC、寄存器的当前值和主存的内容等。单处理器在任一时刻只能运行一个进程的代码。当操作系统决定要进行进程切换时，会先保存当前进程的上下文信息，然后将新进程的上下文恢复，并将控制权传递到新进程。新进程就会从它上次暂停的地方继续往下运行。

注：进程是操作系统进行资源分配的最小单位

线程

在操作系统中，一个进程可以又多个称为线程的执行单元构成，每个线程都运行在进程的上下文中。同一进程中的多个线程共享代码和全局数据。

注：线程是操作系统进行任务调度和执行的最小单位

虚拟内存

虚拟内存提供了一种假象：每个进程都在独占地使用内存。每个进程看到的内存都是一致的，称为虚拟地址空间。下图是Linux的虚拟地址空间示意图(以hello程序为例)：

进程虚拟地址空间

文件

文件就是字节序列。每个I/O设备，包括键盘、磁盘、显示器、打印机和网络都可以看成文件。系统中的所有输入输出都是通过调用一组称为Unix I/O的系统调用读写文件来实现的。

文件的概念简单而强大，它屏蔽了所有底层硬件的实现细节，通过一致的视图来操作这些硬件。这使得不同厂商提供的设备都能运行在同一台计算机上。

重要主题

Amdahl’s Law (阿姆达尔定律)

阿姆达尔定律的主要思想是，当我们对系统的某个部分加速时，其对系统整体性能的影响取决于该部分的重要性和加速程度。其公式如下：

S=1/(1-a+a/n)

其中a为被加速部分占原整体计算的比例，n为性能提升比例。

按照这个公式，可以推导出两个极端极端情况：

  • 当a=1时，S=n。整体计算没有串行部分而全部都是并行部分，加速比为n，此时可以通过增加处理节点来提高整体性能。
  • 当a=0时，S=1。整体计算全部都是串行部分，加速比为1，此时无法通过增加处理节点来提供整体性能。
  • 当n->+∞时，S=1/(1-a)。这是一种极限情况。举个例子假如a=0.6，n->+∞则S=2.5，也就是说当被优化部分的代码占整体计算的60%时，无论怎么优化这部分代码的性能，整体获得的加速比最高不超过2.5。

并发和并行

在系统中有三个层次的并发和并行：

  • 线程级并发
  • 指令级并行
  • 单指令、多数据并行

计算机系统中的抽象

第二章 信息的表示和处理

整数的表示虽然只能编码一个相对较小的数值范围，但这种表示是精确的；浮点数虽然能编码一个较大的数值范围，但这种表示是近似的。

信息存储

  • 计算机使用字节(byte, 1byte=8bits)而不是单独的位来作为最小寻址单位。
  • 机器级程序将内存视为一个非常大的字节数组，称为虚拟内存。内存的每个字节都由一个唯一的数字来标识，称为它的地址，所有可能的地址的集合就称为虚拟地址空间。
  • 虚拟地址空间是一个逻辑上的概念，实际上计算机将动态随机访问存储器(DRAM)、闪存、磁盘存储器、特殊硬件和操作系统软件结合起来，为程序提供一个看上去统一的字节数组。

十六进制表示法

由于二进制表示法太冗长，人们常用十六进制表示法，可用值为0-9A-F。人们常以0x开头表示十六进制值。

在十六进制和二进制之间相互转换非常容易，如果给定一个二进制序列要转换为十六进制，只需从低位到高位以4位一组分组，最左边的一组位数若不足4位可以在左边补0。然后将每个4位组直接转换为0-9A-F中的一个值即可。将十六进制转换为二进制就是将每一位以其相应的二进制位串代替即可。

字数据大小

字长(word size)指明了指针数据的标称大小，字长决定了虚拟地址空间的最大大小。对于一个字长为w的机器而言，其虚拟地址空间范围为0-2^w-1，程序最多访问2^w个字节。

寻址和字节顺序

有两种字节顺序：

  • 小端法(little endian)是最低有效字节在最前面。
  • 大端法(big endian)是最高有效字节在最前面。

比如一个int类型的变量值为0x01234567，位于地址0x100处，在两种字节顺序下的情况如下：

小端法：

1
2
... 0x100 0x101 0x102 0x103 ...
      67    45    23    01

大端法：

1
2
... 0x100 0x101 0x102 0x103 ...
      01    23    45    67

对于选择哪种字节顺序并没有任何技术上的理由。

表示字符串

C语言中的字符串被编码成一个以null(其值为0)字符结尾的字符数组，每个字符都由某个标准编码来表示，如最常见的ASCII字符编码。ASCII字符集适合编码英文文档，如果要支持多语言文字，就需要使用Unicode编码。

表示代码

不同机器类型使用不同的且不兼容的指令和编码方式，因此二进制代码是不兼容的。

布尔代数简介

布尔代数的操作符：

  • 非：~
  • 与：&
  • 或：|
  • 异或：^
~
0 1
1 0
& 0 1
0 0 0
1 0 1
| 0 1
0 0 1
1 1 1
^ 0 1
0 0 1
1 1 0

布尔代数的一些数学属性：

  • 布尔运算&对|的分配律：a&(b|c) 等价于 (a&b)|(a&c)。
  • 布尔运算|对&的分配律：a|(b&c) 等价于 (a|b)&(a|c)。
  • 对任何值a来说，有a^a=0，(a^b)^a=b。

位向量还可以用来表示有限集合，比如位向量a=[01101001]表示集合{0,3,5,6}。

C语言中的位级运算

  • 按位或：|
  • 按位与：&
  • 取反：~
  • 按位异或：^

C语言中的逻辑运算

  • 或：||
  • 与：&&
  • 非：!

逻辑运算认为所有非零的参数都表示TRUE，而参数0表示FALSE。逻辑运算的结果为1或0，表示TRUE或FALSE。

C语言中的移位运算

移位运算是从左至右可结合的，所以x<<j<<k等价于(x<<j)<<k

有3种移位运算：

  • 左移
  • 逻辑右移
  • 算数右移

右移分两种：逻辑右移和算数右移。逻辑右移x>>k是在左端补k个0，而算数右移x>>k是在左端补k个最高有效位的值。

实际上，几乎所有的编译器和机器组合都对有符号数使用算数右移，另外对于无符号数，右移必须是逻辑的。

整数表示

整型数据类型

32位程序上C语言整型数据类型的典型取值范围：

C数据类型 最小值 最大值
[signed] char -128 127
unsigned char 0 255
short -32768 32767
unsigned short 0 65535
int -2147483648 2147483647
unsigned 0 4294967295
long -2147483648 2147483647
ungigned long 0 4294967295
int32_t -2147483648 2147483647
uint32_t 0 4294967295
int64_t -9223372036854775808 9223372036854775807
uint64_t 0 18446744073709551615

64位程序上C语言整型数据类型的典型取值范围：

C数据类型 最小值 最大值
[signed] char -128 127
unsigned char 0 255
short -32768 32767
unsigned short 0 65535
int -2147483648 2147483647
unsigned 0 4294967295
long -9223372036854775808 9223372036854775807
ungigned long 0 18446744073709551615
int32_t -2147483648 2147483647
uint32_t 0 4294967295
int64_t -9223372036854775808 9223372036854775807
uint64_t 0 18446744073709551615

C语言的整型数据类型的保证的取值范围：

C数据类型 最小值 最大值
[signed] char -127 127
unsigned char 0 255
short -32767 32767
unsigned short 0 65535
int -32767 32767
unsigned 0 65535
long -2147483647 2147483647
ungigned long 0 4294967295
int32_t -2147483648 2147483647
uint32_t 0 4294967295
int64_t -9223372036854775808 9223372036854775807
uint64_t 0 18446744073709551615

另外，C/C++都支持有符号数（默认）和无符号数，Java只支持有符号数。

无符号数的编码

原理：无符号数编码的定义

无符号数编码的定义

无符号数的二进制表示有一个很重要的属性，即每个介于0-2^w-1之间的数都有唯一一个w位的值编码。

原理：无符号数编码的唯一性

补码编码

补码是最常见的计算机编码有符号数的方式（另外两种方式为反码和原码）。

原理：补码编码的定义

补码编码的定义

原理：补码编码的唯一性

一些重要的数字的补码表示：

数 8位字长 16位 32位 64位
UMax 0xFF
255		 0xFFFF
65535		 0xFFFFFFFF
4294967295		 0xFFFFFFFFFFFFFFFF
18446744073709551615
TMin 0x80
-128		 0x8000
-32768		 0x80000000
-2147483648		 0x8000000000000000
-9223372036854775808
TMax 0x7F
127		 0x7FFF
32767		 0x7FFFFFFF
2147483647		 0x7FFFFFFFFFFFFFFF
9223372036854775807
-1 0xFF 0xFFFF 0xFFFFFFFF 0xFFFFFFFFFFFFFFFF
0 0x00 0x0000 0x00000000 0x0000000000000000

以下几点值得注意：

  • 补码的取值范围是不对称的：|TMin| = |TMax| + 1
  • 最大的无符号数值刚好比补码的最大值的两倍大1：UMax = 2TMax + 1

C库文件<limits.h>中定义了一组常量来限定编译器运行的这台机器的不同整型数据类型的取值范围，比如INT_MAX、INT_MIN和UINT_MAX。

有符号数的其他表示方法：

  • 反码，除了最高有效位的权是-(2^w-1 - 1)而不是-2^w-1，其余和补码一样。

反码编码的定义

  • 原码，最高有效位是符号位。
    原码编码的定义

需要注意的是，反码和原码对0的编码表示有两种，[00…0]都解释为+0，而-0在原码中为[10…0]，在反码则为[11…1]。目前几乎所有现代机器都使用补码扁食有符号数。

读书笔记