《深入理解计算机系统》笔记
计算机系统漫游
信息就是位 + 上下文
系统中所有的信息，包括磁盘文件、内存中的程序、内存中存放的用户数据以及网络上传送的数据，都是由一串比特表示的。区分不同数据对象的唯一方法是我们读到这些数据对象时的上下文。
处理器读并解释储存在内存中的指令
贯穿整个系统的的是一组电子管道，称作 总线，它携带信息字节并负责在各个部件间传递。通常总线被设计成算传送定长的字节块，也就是 字（word）。字中的字节数（即 字长）一个基本的系统参数。
I/O（输入/输出）设备是系统与外部世界的联系通道。每个 I/O 设备都通过一个控制器或者适配器与 I/O 总线相连。
主存是一个临时存储设备，在处理器执行程序时，用来存放程序和程序处理的数据。从物理上来说，主存是由一个动态随机存取存储器（DRAM）芯片组成的。从逻辑上来说，存储器是一个线性的字节数组，每个字节都有其唯一的地址（数组索引）。
中央处理单元（CPU）简称处理器，是解释（或执行）存储在主存中指令的引擎。处理器的核心是一个大小为一个字的存储设备（或寄存器），称为程序计数器（PC）。在任何时刻，PC 都指向主存中的某条机器语言指令（即含有该条指令的地址）。
存储设备形成层次结构
存储器层次结构的主要思想是，上一层的存储器作为低一层存储器的高速缓存。
操作系统管理硬件
我们可以把操作系统看成是应用程序和硬件之间插入的一层软件。所有应用程序对硬件的操作尝试都必须通过操作系统。
操作系统有两个基本功能：防止硬件被失效的应用程序滥用，向应用程序提供简单一致的机制来控制复杂而又通常大不相同的低级硬件设备。操作系统通过几个基本的抽象概念来实现这两个功能：进程、虚拟内存和文件。文件是对 I/O 设备的抽象表示，虚拟内存是对主存和 I/O 设备的抽象表示，进程则是对处理器、主存和 I/O 设备的抽象表示。
进程是操作系统对一个正在运行的程序的一种抽象。在一个系统上可以同时运行多个进程，而每个进程都好像在独占地使用硬件。并发运行 则是说一个进程的指令和另一个进程的指令是交错执行的。操作系统实现这种交错执行的机制称为 上下文切换。
操作系统保持跟踪进程运行所需的所有状态信息。这种状态也就是 上下文，包括许多信息，比如 PC 和寄存器文件的当前值，以及主存的内容。在任何一个时刻，单处理器系统都只能执行一个进程的代码。当操作系统决定要把控制权从当前进程转移到某个新进程时，就会进行 上下文切换，即保存当前进程的上下文、恢复新进程的上下文，然后将控制权传递到新进程。
一个进程实际上可以由多个称为 线程 的执行单元组成，每个线程都运行在进程的上下文中，并共享同样的代码和全局数据。
虚拟内存是一个抽象概念，它为每个进程提供了一个假象，即每个进程都在独占地使用主存。每个进程看到的内存都是一致的，称为 虚拟地址空间。
文件就是字节序列，仅此而已。每个 I/O 设备，包括磁盘、键盘、显示器，甚至网络都可以看成是文件。
重要主题
术语 并发（concurrency）是一个通用的概念，指一个同时具有多个活动的系统。术语 并行（parallelism）指的是用并发来使一个系统运行得更快。
抽象的使用是计算机科学中最为重要的概念之一。
信息的表示和处理
信息存储
大多数计算机使用 8 位的块，或者 字节（byte），作为最小的可寻址的内存单元，而不是访问内存中单独的位。机器级程序将内存视为一个非常大的字节数组，称为虚拟内存。内存的每个字节都由一个唯一的数字来标识，称为它的地址，所有可能地址的集合就称为虚拟地址空间。
十六进制数使用数字 0 ~ 9 以及字符 A ~ F 表示 16 个可能的值。用十六进制书写，一个字节的值域为 00 ~ FF。
十六进制 -> 二进制：通过展开每个十六进制数字。
二进制 -> 十六进制：通过首先把它分为每 4 位一组来转换为十六进制。
十进制 -> 十六进制：将一个十进制数字 $x$ 转换为十六进制，可以反复地用 16 除 $x$，得到一个商 $q$ 和一个余数 $r$，也就是 $x=q*16+r$，然后我们用十六进制数字表示的 $r$ 作为最低位数字，并且通过对 $q$ 反复进行这个过程得到剩下的数字。
十六进制 -> 十进制：用相应的 16 的幂乘以每个十六进制数字。
每台计算机都有一个 字长（word size），指明指针数据的标称大小（nominal size）。
为了避免由于依赖典型大小和不同编译器设置带来的奇怪行为，ISO C99 引入了一类数据类型，其数据大小是固定的，不随编译器和机器设置而变化。其中就有数据类型 int32_t 和 int64_t，它们分别为 4 个字节和 8 个字节。
大部分数据类型都是编码为有符号数值，除非有前缀关键字 unsigned 或对确定大小的数据类型使用了特定的无符号声明。
多字节对象都被存储为连续的字节序列，对象的地址为所使用字节中最小的地址。
排列表示一个对象的字节有两个通用的规则。考虑一个 $w$ 位的整数，其位表示为 $[x_{w-1},x_{w-2},\dots,x_1,x_0]$，其中 $x_{w-1}$ 是最高有效位，而 $x_0$ 是最低有效位。最低有效字节在最前面的方式，称为 小端法（little endian），最高有效字节在最前面的方式，称为 大端法（big endian）。
假设变量 x 的类型为 int，位于地址 0x100 处，它的十六进制值为 0x01234567。地址范围 0x100 ～ 0x103 的字节顺序依赖于机器的类型：
C 语言中还提供了一组 逻辑运算符号：||、&&、!，分别对应于命题逻辑运算中的 OR、AND 和 NOT 运算。逻辑运算认为所有非零的参数都表示 TRUE，而参数 0 表示 FALSE。
如果对第一个参数求值就能确定表达式的结果，那么逻辑运算符就不会对第二个参数求值。
整数表示
对于向量 $\vec{x}=[x_{w-1},x_{w-2},\dots,x_{0}]$，无符号数编码 的定义 $B2U_w(\vec{x})=\sum_{i=0}^{w-1}x_i2^i$。
对于向量 $\vec{x}=[x_{w-1},x_{w-2},\dots,x_{0}]$，补码编码 的定义 $B2T_w(\vec{x})=-x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_i2^i$。最高有效位 $x_{w-1}$ 也称为 符号位，它的「权重」为 $-2^{w-1}$，是无符号表示中权重的负数。
对于大多数 C 语言的实现，处理同样字长的有符号数和无符号数之间互相转换的一般规则是：数值可能会改变，但是位模式不变。
对满足 $TMin_w\le x\le TMax_w$ 的 $x$，补码转换为无符号数 $T2U_w(x)=\begin{cases} x+2^w, & x\lt 0 \ x, & x\ge 0 \end{cases}$。
对满足 $0\le u\le UMax_w$ 的 $u$，无符号数转换为补码 $U2T_w(u)=\begin{cases} u, & u\le TMax_w \ u-2^w, & u\gt TMax_w \end{cases}$。
对于在范围 $0\le x\le TMax_w$ 之内的值 $x$ 而言，我们得到 $T2U_w(x)=x$ 和 $U2T_w(x)=x$。也就是说，在这个范围内的数字有相同的无符号和补码表示。对于这个范围以外的数值，转换需要加上或者减去 $2^w$。
当执行一个运算时，如果它的一个运算数是有符号的，而另一个是无符号的，那么 C 语言会隐式地将有符号参数强制类型转换为无符号数，并假设这两个数都是非负的，来执行这个运算。
无符号数的零扩展：定义宽度为 $w$ 的位向量 $\vec{u}=[u_{w-1},u_{w-2},\dots,u_{0}]$ 和宽度为 $w'$ 的位向量 $\vec{u'}=[0,\dots,0,u_{w-1},u_{w-2},\dots,u_{0}]$，其中 $w'\gt w$。则 $B2U_w(\vec{u})=B2U_{w'}(\vec{u'})$。
补码数的符号扩展：定义宽度为 $w$ 的位向量 $\vec{x}=[\textcolor{blue}{x_{w-1}},x_{w-2},\dots,x_{0}]$ 和宽度为 $w'$ 的位向量 $\vec{x'}=[\textcolor{blue}{x_{w-1},\dots,x_{w-1},x_{w-1}},x_{w-2},\dots,x_{0}]$，其中 $w'\gt w$。则 $B2T_w(\vec{x})=B2T_{w'}(\vec{x'})$。
无符号数的截断：令 $\vec{x}$ 等于位向量 $[x_{w-1},x_{w-2},\dots,x_{0}]$，而 $\vec{x'}$ 是将其截断为 $k$ 位的结果：$\vec{x'}=[x_{k-1},x_{k-2},\dots,x_{0}]$。令 $x=B2U_w(\vec{x})$，$x'=B2U_k(\vec{x'})$。则 $x'=x \bmod 2^k$。
补码数的截断：令 $\vec{x}$ 等于位向量 $[x_{w-1},x_{w-2},\dots,x_{0}]$，而 $\vec{x'}$ 是将其截断为 $k$ 位的结果：$\vec{x'}=[x_{k-1},x_{k-2},\dots,x_{0}]$。令 $x=B2U_w(\vec{x})$，$x'=B2T_k(\vec{x'})$。则 $x'=U2T_k(x \bmod 2^k)$。
有符号数到无符号数的隐式转换，会导致错误或者漏洞，避免这类错误的一种方式就是绝不使用无符号数。
当我们想要把数字仅仅看作是位的集合，而没有任何数字意义时，无符号数值是非常有用的。
整数运算
对满足 $0\le x,;y\lt 2^w$ 的 $x$ 和 $y$，无符号数加法 $x+_w^uy=\begin{cases} x+y, & x+y\lt 2^w & \text{Normal}\ x+y-2^w, & 2^w\le x+y\lt 2^{w+1} & \text{Overflow} \end{cases}$。
对满足 $0\le x\lt 2^w$ 的任意 $x$，其 $w$ 位的 无符号数求反 $-_w^ux=\begin{cases} x, & x=0\ 2^w-x, & x>0 \end{cases}$。
对满足 $-2^{w-1}\le x,;y\le2^{w-1}-1$ 的整数 $x$ 和 $y$，补码加法 $x+_w^ty=\begin{cases} x+y-2^w, & 2^{w-1}\le x+y & \text{Positive overflow}\ x+y, & -2^{w-1}\le x+y \lt 2^{w-1} & \text{Normal}\ x+y+2^w, & x+y\lt -2^{w-1} & \text{Negative overflow} \end{cases}$。
对满足 $TMin_w\le x\le TMax_w$ 的 ，其 $w$ 位的 补码求反 $-_w^tx=\begin{cases} TMin_w, & x=TMin_w\ -x, & x\gt TMin_w \end{cases}$。
执行位级别补码求反的一种方式是对每一位求反，然后再对结果加 1。在 C 语言中，我们可以说对于任意整数值 x，计算表达式 -x 和 ~x+1 得到的结果完全一致。
对满足 $0\le x,;y\le UMax_w$ 的 $x$ 和 $y$，无符号数乘法 $x_w^uy=(xy) \bmod2^w$。
对满足 $TMin_w\le x,;y\le TMax_w$ 的 $x$ 和! $y$，补码乘法 $x_w^ty=U2T_w((xy) \bmod 2^w)$。
计算机执行的整数运算实际上是一种 模运算形式，表示数字的有限字长限制了可能值的取值范围，运算结果可能溢出。
补码表示提供了一种既能表示负数，也能表示正数的灵活方法，同时使用了与执行无符号算数相同的位级实现，这些运算包括像加法、减法、乘法甚至除法，无论运算数是以无符号形式还是以补码形式表示的，都有完全一样或者非常类似的位级行为。
浮点数
对于 $b_{m}b_{m-1}\dots b_1b_0.b_{-1}b_{-2}\dots b_{-n-1}b_{-n}$ 的表示法，每个二进制位 $b_{i}$ 的取值范围是 0 和 1，浮点数编码 的定义 $b=\sum_{i=-n}^{m}b_{i}2^{i}$，符号点左边的位的权是 2 的正幂，右边的位的全是 2 的负幂。
形如 $0.11\dots 1_{2}$ 的数表示的是刚好小于 1 的数，例如 $0.111111_{2}$ 表示 $\frac{63}{64}$，表示法 $1.0-\varepsilon$ 用于表示这样的数值。
十进制表示法不能准确地表达像 $\frac{1}{3}$ 和 $\frac{5}{7}$ 这样的数，类似，小数的二进制表示法只能表示那些能够被写成 $x\times 2^y$ 的数。
IEEE 浮点数标准使用 $V=(-1)^{s} \times M \times 2^{E}$ 的形式来表示一个数：
符号 sign $s$ 决定这个数是负数（$s=1$）还是正数（$s=0$）；
尾数 significand $M$ 是一个二进制小数，它的范围是 $1～2-\varepsilon$ 或者是 $0～1-\varepsilon$；
指数 exponent $E$ 通过 2 的次幂对浮点数值进行加权。
IEEE 浮点数的位表示分为三个字段：
1 位的符号字段 $s$ 编码符号 $s$；
k 位的指数字段 $exp = e_{k-1}\dots e_{1}e_{0}$ 编码指数 $E$；
n 位的尾数字段 $frac=f_{n-1}\dots f_{1}f_{0}$ 编码尾数 $M$。
在单精度浮点格式（float）中，$s$、$exp$、$frac$ 分别占 1 位、8 位、23 位。在双精度浮点格式（double）中，$s$、$exp$、$frac$ 分别占 1 位、11 位、52 位。
当指数 $exp$ 的位模式不全为 0，也不全为 1 时，浮点数数值是规范化的。指数字段被解释为以偏移（biased）形式表示的有符号整数。指数的值是 $E=exp-Bias$，$exp$ 是由 $e_{k-1}\dots e_{1}e_{0}$ 表示的无符号数， $Bias$ 是 $2^{k-1}-1$ 的值（单精度是 127，双精度是 1023）。尾数 $frac$ 被解释为描述小数值 $f$，其中 $0\le f\lt1$，二进制表示为 $0.f_{n-1}\dots f_{1}f_{0}$。尾数的值是 $M=1+f$，因为总是能够调整指数 $E$，使得尾数 $M$ 的值在范围 $1\le M\lt2$ 之中，所以既然第一位总是等于 1，那么就不需要显式地表示它。
当指数 $exp$ 的位模式全为 0 时，浮点数数值是非规范化的。指数的值是 $E=1-Bais$，尾数的值是 $M=f$。非规范化数有两个用途：提供了表示数值 0 的方式、提供了表示非常接近于数值 0.0 的方式。
当指数 $exp$ 的位模式全为 1 时，浮点数数值表示特殊值。当时尾数 $frac$ 的位模式全为 0 时，此时浮点数值表示无穷。当时尾数 $frac$ 的位模式不全为 0 时，此时浮点数值表示 NaN，即不是一个数（Not a Number）。
最后更新于