深入理解计算机系统

第 1 章计算机系统漫游¶

1.1 基础知识¶

1字节 = 8位
只由ASCII字符构成的文件称为“文本文件”，所有其他文件都称为“二进制文件”

C编程语言的起源： C语言是贝尔实验室的Dennis Ritchie于1969年 ~ 1973年间创建的。美国美国标准学会（ANSI）在1989年颁布了ANSI C标准，后来使C语言标准化成为了国际标准化组织（ISO）的责任。这些标准定义了C语言和一系列函数库，即所谓的“C标准库”。Kernighan和Richie在它们的经典著作中描述了ANSIC，这本著作中描述了ANSI C，这本著作被人们满怀感情地称为“[K&R]”。用Ritchie的话来说，C语言是“古怪的、有缺陷的，但也是一个巨大的成功”。但是为什么会成功呢？主要有以下几点：

C语言与UNIX操作系统关系密切：C语言从一开始就是作为一种用于Unix系统的程序设计语言而开发出来的。大部分Unix内核，以及所有支撑工具和函数库都是用C语言编写的。20世纪70年代后期到80年代初期，Unix在高等院校兴起，许多人开始接触C语言并喜欢上了它。因为Unix几乎全部是用C编写的，所以可以很方便地移植到新的机器上，这种特点为C和Unix赢得了更为广泛的支持。

C语言小而简单：掌控C语言设计的是一个人而非一个协会，因此这是一个简洁明了、没有什么冗余的一致设计。[K&R]这本书用了大量的例子和练习描述了完整的C语言及其标准库，而全书不过261页。C语言的简单使它相对而言易于学习，也易于移植到不同的计算机上。

C语言是为了实践目的设计的：C语言是为实现Unix操作系统而设计的。后来，其他人发现能够用这门语言无障碍地编写他们想要的程序。 C语言是系统级编程的首选，同时它也非常适用于应用级程序的编写。然而，它也并非适用于所有的程序员和所有情况。C语言的指针是造成困惑和程序错误的一个常见原因。同时，C语言还缺乏对非常有用的抽象（例如类、对象和异常）的显示支持。像C++和Java这样针对应用级程序的新程序设计语言解决了这些问题。

编译系统：
- 预处理阶段：预处理器（cpp）根据以字符'#'开头的命令，修改原始的C程序，比如：展开头文件。结果就得到了hello.i
- 编译阶段：编译器（cc1）将文本文件“hello.i”翻译成文本文件“hello.s”，它包含一个“汇编语言程序”。
- 汇编阶段：汇编器（as）将hello.s翻译成机器语言指令，把这些指令打包成一种叫做“可重定位目标程序（relocatable object program）的格式，并将结果保存在目标文件hello.o中。
- 链接阶段：负责将“*.o”和库进行合并，生成hello可执行程序

GNU项目： GCC是GNU（GNU是GNU's Not Unix的缩写）项目开发出来的众多有用工具之一。GNU项目是1984年由Richard Stallman发起的一个免税的慈善项目。该项目的目标非常宏大，就是开发出一个完整的类Unix的系统，其源代码能够不受限制地被修改和传播。GNU项目已经开发出了一个包含Unix操作系统的所有主要部件的环境，但内核除外，内核是由Linux项目独立发展而来的。GNU环境包括EMACS编译器、GCC编译器、GDB调试器、汇编器、链接器、处理二进制文件的工具以及其他一些部件。GCC编译器已经发展到支持许多不同的语言，能够针对许多不同的机器生成代码。支持的语言包括C、C++、Fortran、Java、Pascal、面向对象C语言（Objetive-C）和Ada。 GNU项目取得了非凡的成绩，但是却常常被忽略。现代开放源码运动（通常和Linux联系在一起）的思想起源是GNU项目中自由软件（free software）的概念。而且Linux如此受欢迎在很大程度上还要归功于GNU工具，因为它们给Linux内核提供了环境。

1.2 典型系统的硬件组成¶

总线：贯穿整个系统的是一组电子管，称作“总线”。
I/O设备：系统与外部世界的联系通道。
- 每个“I/O设备都通过一个控制器或适配器与I/O总线相连。控制器和适配器之前的区别主要在于它们的封装方式：
  - 控制器：置于I/O设备本身或者系统的主板上的芯片组
  - 适配器：一块插在主板插槽上的卡
主存：一个临时存储设备，在处理器执行程序时，用来存放程序和程序处理的数据。
- 从物理上来说，主存是由一组“动态随机存取存储器（DRAM）芯片组成的。
- 从逻辑上来说，存储器是个线性的字节数组，每个字节都有其唯一的地址。
处理器：
- 中央处理单元（CPU），简称处理器是解释（或执行）存储在主存中指令的引擎。处理器的核心是一个资产的存储设备（或寄存器），称为“程序计数器（PC）”。在任何时刻，PC都指向存储中的某条机器语言指令（即含有该条指令的地址）
- 寄存器文件时一个小的存储设备，由一些1字长的寄存器组成，每个寄存器都有唯一的名字。ALU计算新的数据和地址值。CPU可能会执行以下操作：
  - 加载：把一个字节或一个字从主存复制到寄存器，以覆盖寄存器原来的内容。
  - 存储：把一个字节或一个字从寄存器复制到主存的某个位置，以覆盖这个位置上原来的内容。
  - 操作：把两个寄存器的内容复制到ALU，ALU对着两个字做算数操作，并将结果存放到一个寄存器中，以覆盖该寄存器中原来的内容。
  - 跳转：从指令本身中抽取一个字，并将这个字复制到PC中，以覆盖PC中原来的值。
- 指令集结构：描述的是每条机器代码指令的效果。
- 微体系结构：描述的是处理器实际上是如何实现的。

1.3 运行hello程序¶

从键盘上读取hello命令
当我们敲了回车后，外壳程序会加载对应的可执行的hello文件，将hello目标文件中的代码和数据从磁盘复制到主存：利用“直接存储器存取（DMA）技术，可以不通过CPU直接从磁盘到达主存。
接着运行程序代码后，会将程序中的printf("hello, world\n")输出到屏幕上：

1.4 高速缓存至关重要¶

高速缓存存储器（简称高速缓存），作为暂时的集结区域，用来存放处理器近期可能会需要的信息。正常分为：L1、L2、L3；其中它们是用一种叫做“静态随机访问存储器（SRAM）”的硬件技术实现的。
- L1：访问速度几乎和访问寄存器文件一样快。
- L2：进程访问L2的时间要比访问L1的时间长5倍，但这仍比访问主存的时间快5 ~ 10倍。
使用缓存结构的原因是：利用了高速缓存的局部性原理，即程序具有访问局部区域黎的数据和代码的趋势。
我们可以利用高速缓存将程序的性能提高一个数量级。
存储器层次结构：
- 存储器层次结构的主要思想是：上一层的存储器作为低一层存储器的高速缓存。

1.5 操作系统¶

操作系统有两个基本功能：
- 防止硬件被失控的应用程序滥用。
- 向应用程序提供简单一致的机制来控制复杂而又通常大相径庭的低级硬件设备。

Unix和Posix： 20世纪60年代是大型、复杂操作系统盛行的年代，如IBM的OS/360和Honeywell的Multics系统。OS/360是历史上最成功的软件项目之一，而Multics虽然持续存在了多年，缺从来没有被广泛应用。贝尔实验室曾经是Multics项目的最初参与者，但是考虑到该项目的复杂性和缺乏进展于1969年推出。鉴于Multics项目部愉快的经理，一组贝尔实验室的研究人员——Ken Thompson、Dennis Ritchie、Doug Mcllroy和JoeOssanna，从1969年开始在DECPDP-7计算机上完全用机器语言编写了一个简单得多的操作系统。这个心系统中的很多思想，如层次文件系统、作为用户及进程的外壳概念，都是来自于Multics，只不过在一个更小、更简单的程序包里实现。1970年，Brian Kemighan给新系统命名为“Unix”，这也是一个双关语，暗指“Multics”的复杂性。1973年用C语言重新编写其内核，1974年，Unix开始正式对外发布。贝尔实验室以慷慨的条件向学校提供源代码，所以Unix在大专院校里获得了很多支持并继续发展。最优影响的工作是20世纪70年代晚期到80年代早期，在美国加州大学伯克利分销，伯克利的研究人员在一系列发布版中增加了虚拟存储器和Internet协议，称为Unix 4.xBSD。于此同时，贝尔实验室也在发布自己的版本，即System V Unix。其他厂商的版本，如Sun Microsystems的Solaris系统，则是从这些最初的版本BSD和System V中衍生而来的。 20世纪80年代中期，Unix厂商试图通过加入新的、往往不兼容的特性来使它们的程序与众不同，麻烦也就随之而来了。为了阻止这种趋势，IEEE开始努力标准化Unix的开发，后来由Richard Stallman命名为“Posix”。结果就得到了一系列的标准，称作Posix标准。这套标准涵盖了很多方面，比如Unix系统调用的C语言接口、外壳程序和工具、线程及网络编程。随着越来越多的系统日益完全地遵从Posix标准，Unix版本之间的差异正在逐渐消失。

操作系统保持跟踪进程运行所需要的所有状态信息，这种状态，也就是上下文。
在任何一个时刻，单处理器系统都只能执行一个进程的代码。当操作系统决定要把控制权从当前进程转移到某个新进程时，就会进行“上下文切换”，即保存当前进程的上下文、恢复新进程的上下文，然后将控制权传递到新进程。
虚拟存储器是一个抽象概念，它为每个进程提供了一个假象，即每个进程都在独占地使用主存。每个进程看到的是一致的存储器，称为“虚拟地址空间”。
- 程序代码和数据：对于所有进程来说，代码时从同一固定地址开始，紧接着的是和C全局变量相对应的数据位置。代码和数据区是直接按照可执行目标文件的内容初始化的。
- 堆：当调用malloc和free这样的C标准库函数时，堆可以在运行时动态扩展和收缩。
- 共享库：大约在地址空间的中间部分是用一块用来存放像C标准库和数学库这样共享库的代码和数据的区域。
- 堆：位于用户虚拟地址空间顶部的是“用户栈”，编译器用它来实现函数调用。和堆一样，用户栈在程序执行期间可以动态地扩展和收缩。
- 内核虚拟存储器：内核总是驻留在内存中，是操作系统的一部分。地址空间顶部的区域时为内核保留的，不允许应用程序读写这个区域的内容或者直接调用内核代码定义的函数。

1.6 并发和并行¶

并发（concurrency）是一个通用的概念，指一个同时具有多个活动的系统；
并行（parallelism）指的是用并发使一个系统运行得更快。
超线程：有时称为同时多线程，是一项允许一个CPU执行多个控制流的技术。如果有4核，那么利用此技术可以并行的执行8个线程
Inter Core i7的组织结构：
- 多处理器的使用可以从两个方面提高系统性能：
  1. 减少了在执行多个任务时模拟并发的需要
  2. 可以使应用程序运行得更快 # 总觉得这句跟没说一样
指令级并行：现代处理器可以同时执行多条指令的属性称为指令级并行。
- 超标量：处理器可以达到比一个周期一条指令更的执行速度
单指令、多数据并行：通过特殊的硬件允许一条指令产生多个可以并行执行的操作，称为SIMD（单指令、多数据）
计算机系统提供的一些抽象：
- 文件：对I/O的抽象
- 虚拟储存器：对程序存储器的抽象
- 进程：对一个正在运行的程序的抽象
- 虚拟机：提供对整个计算机的抽象

第 2 章信息的表示和处理¶

三种数字
- 无符号（unsigned）：编码基于传统的二进制表示法，表示大于或等于0的数字。
- 补码（two's-complement）：编码是表示有符号整数的最常见的方式，有符号整数就是可以为正或者为负的数字。
- 浮点数（floating-point）：编码是表示实数的科学记数法的以2为基数的版本。
C编程语言的演变 > > - 国际标准化组织接管了对C语言进行标准化的任务，1990年推出了几乎和ANSI C一样的版本，称为“ISO C90”。该组织在1999年又对C语言做了更新，得到“ISO C99”。 > - 当前模式使用“ISO C90”编译C代码，可以显示的指定编译标准：% gcc -std=c99 pro.c
虚拟存储器：机器级程序将存储器视为一个非常大的字节数组
地址：存储器的每个字节都由一个唯一的数字标识，该标识就是地址
虚拟地址空间：所有可能地址的集合
程序对象：程序数据、指令和控制信息
每台计算机都有一个字长（word size），指明整数和指针数据的标称大小。对于一个字节为 $w$ 位的机器而言，虚拟地址的范围为：$0 ~ (2^w - 1)$
C语言中数字数据类型的字节数：

C声明 32位机器 64位机器

char 1 1

short int 2 2

int 4 4

long int 4 8

long long int 8 8

char * 4 8

float 4 4

double 8 8
生成ASCII字符码表：% man ascii
在不提供的机器类型和不同的系统中会有不同的编码规则因此二进制代码时不兼容的。二进制代码很少能再不同的机器和操作系统组合之间移植。

2.1 进制间的转换¶

$2^n$ 转16进制：将n转化为 $i + 4j$ 的形式，j的值代表的是16进制中多少个0，随后i以 $2^i$ 翻译即可。比如 $x = 2^{11}$ 转化成16进制的结果为：

\[ \begin{aligned} 因为&: 11 = 3 + 4 * 2 \\ 因此&: i = 3, j = 2 \\ 所以&: x = \text{0x800} \end{aligned} \]
10 => 16：反复除16取余
10 => 2：反复除2取余
2 => 10：

\[ y = \sum_{i = 0}^{n}x_i \cdot 2^i \]
16 => 10：

\[ y = \sum_{i = 0}^{n}x_i \cdot 16^i \]
可以推理除，任意进制 $a$ => 10：

\[ y = \sum_{i = 0}^{n}x_i \cdot a^i \]

2.2 寻址和字节顺序¶

小端法（little endian）：最低有效位在最前面的方式（口诀：低低小）
- 大多数Intel兼容机都采用这种规则。
大端法（big endian）：最高有效位在最前面的方式
- 大多数IBM和Sun Microsystems的机器都采用这种规则。
许多比较新的微处理器使用双端法（bi-endian）

2.3 位级运算¶

布尔运算&和|互分配律：
- a & (b | c) = (a & b) | (a & c)
- a | (b & c) = (a | b) & (a | c)
布尔的每个加法逆元运算符是^，因此加法逆元本身，比如1的加法逆元运算：1 ^ 1 = 0
任意值与0异或等于本身，与1异或则取反
位向量 $[a_{w-1}, ..., a_1, a_0]$ 可以用来表示有限集合，其中 $a_i = 1$ 当且仅当 $i \in A$。
移位操作，右移支持两种形式：
- 逻辑右移：左端补0
  - C语言中，无符号右移采用此形式
- 算术右移：左端补最高有效位的值
  - C语言中，有符号右移采用此形式

2.4 整数表示¶

整数的取值范围不对称，负数的范围比整数大1： $|TMin| = |TMax| + 1$
- 原因是0占用了1个数
无符号数的编码：
- \[ B2U_w(\vec{x}) \doteq \sum_{i=1}^{w-1}{x_i2^i} \]
- 最大值（相当于 $x$ 为1）：
  
  \[ UMax_w \doteq \sum_{i=0}^{w-1}2^i = 2^w - 1 \]
- $B2U_w$ 是一个双射：每一个长度为w的位向量都有一个值与之对应；反过来，在0 ~ $2^w$ -1 之间的每一个整数都有一个唯一的长度为 $w$ 的位向量。比如：$7_4$ <=> [0111]
补码（two's-complement)编码：将字的最高有效位解释为负权
- \[ B2T_w(\vec{x}) \doteq -x_{w-1}2^{w-1} + \sum_{i=0}^{w-2}{x_i2^i} \]
- 最小值：
  
  \[ TMin_w \doteq -2^{w-1} \]
- 最大值：
  
  \[ TMax \doteq \sum_{i=0}^{w-2}{2^i} = 2^{w-1} - 1 \]
- $B2T_w$ 也是一个双射
- 之所以是tow's的原因是： $ -x = 2^w - x $
  - 这里很好理解，因为最高位的权重从负转到正，相当于是2倍的 $2^{w-1}$ 即 $ 2 \cdot 2^{w-1} = 2^w $
反码（Ones' Complement）编码：
- \[ B2O_w(\vec{x}) \doteq -x_{w-1}(2^{w-1} - 1) + \sum_{i=0}^{w-2}{x_i2^i} \]
- 补 = 反 + 1：最高权重位差1
- 之所以是ones'的原因是：$-x = [111...1]-x$
原码（Sign-Magnitude）编码：
- \[ B2S_w(\vec{x}) \doteq (-1)^{x_{w-1}} \cdot (\sum_{i=0}^{w-2}{x_i2^i}) \]
无符号转符号：先转二进制，再转有符号（如果 $x$ 原本的最高位是1的话，则相当于最高位的权重减少 $2^w$）

\[ U2T_w = B2T_w(U2B_w(x)) = -x_{w-1}2^w + x = \begin{cases} x &, x < 2^{w-1} \\ x-2^w &, x \ge 2^{w-1} \end{cases} \]
符号转无符号：先转二进制，再转无符号（如果 $x$ 原本是负数的话，则相当于最高位的权重增加 $2^w$）

\[ T2U_w(x) = B2U_w(T2B_w(x)) = x_{w-1}2^w + x = \begin{cases} x + 2^w &, x < 0 \\ x &, x \ge 0 \end{cases} \]
由于正负最大值之间的不对称，因此会有以下诡异的行为：
```
#define INT_MIN (-INT_MAX - 1)
```
- 这里之所以不直接写成-2147483648的原因是，在int中无法存放那么大的值，因此在32位的计算机只能将该值转化为unsigned int，因此如果这么做的话，INT_MIN实际上的值是一个unsigned int，且值为2147483649。
- 而用-INT_MAX则避免了这种情况，32位计算机可以正常的处理。

2.5 扩展数字¶

小 -> 大：
- 有两种扩展方式：
  - 零扩展：将**无符号**扩展成更大的数通常采用此方式
  - 符号扩展：将**符号**扩展成更大的数，通常采用此方式
大 -> 小：直接基于二进制截断即可
如果出现了即扩展大小，又改变符号：先扩展大小，再进行符号转换。
当两个不同大小的数字进行比较时，以大的为主，计算机通常会隐式的进行转换。

2.6 整数加法运算¶

整数的加法运算具备“阿尔贝群”的性质：
无符号运算：相加后并截断（mod $2^w$）
- 溢出判断条件：$ x + y < x $
- 加法逆元：
  
  \[ -^u_wx = \begin{cases} x &, x = 0 \\ 2^w - x &, x > 0 \end{cases} \]
补码运算：先以无符号的形式相加，并截断（mod $2^w$），再进行符号转换（$U2T_w$）

\[ x +^t_wy = \begin{cases} x + y - 2^w &, 2^{w-1} \le x + y &, 正溢出 \\ x + y &, -2^{w-1} \le x + y < 2^{w-1} &, 正常 \\ x + y + 2^w &, x + y < -2^{w-1} &, 负溢出 \end{cases} \]
- 溢出判断条件：
```
int tadd_ok(int x, int y)
{
    int s = x + y;

    /* !(正溢出 || 负溢出) */
    return !((x < 0 && y < 0 && s > 0) || (x > 0 && y > 0 && s < 0));
}
```
- 补码的非（加法逆元）：唯一特殊的是 $TMin_w$ ，该特殊值的非是其本身，其证明是通过**负溢出**得到的（-
  
  \[ -^t_wx = \begin{cases} -2^{w-1} &, x = -2^{w-1} \\ -x &, x > -2^{w-1} \end{cases} \]
  - -x的等效表示：~x + 1（补 = 反 + 1）

2.7 整数乘法运算¶

$+^u_w$、$-^u_w$、$*^u_w$ 和 $+^t_w$、$-^t_w$、$*^t_w$ 在位级上有相同的结果
无符号乘法：

\[ x *^u_w y = (x \cdot y)\ mod\ 2^w \]
补码乘法：

\[ x *^t_w y = U2T_w((x \cdot y)\ mod\ 2^w) \]
对于无符号和补码的乘法来说，运算的位级表示都是一样的（假设 $x\rq$ 和 $y\rq$ 表示有符号，$x$ 和 $y$ 则表示无符号）： $$ \begin{aligned} (x\rq \cdot y\rq) &= [(x + x_{w-1}2^w) \cdot (y + y_{w-1}2^w)] mod 2^w \ &= [x \cdot y + (x_{w-1}y + y_{w-1}x)2^w + x_{w-1}y_{w-1}2^{2w}] mod 2^w \ &= (x \cdot y) mod 2^w \end{aligned} $$

溢出条件：

int tmult_ok(int x, int y)
{
    int p = x * y;

    /* 除法不存在溢出，因此可以反着算 */
    return !x || p / x == y;
}

在大多数机器上，乘法指令相当慢，需要10个或则更多的时钟周期，因此编译器往往会尝试使用移位和加法运算组合来代替乘法
对于乘以一个具有连续1表示的数，可以有两种简要形式去转化：假定 $x$ 乘以 [(0...0) (1...1) (0...0)]，我们约定，n为连续1的起始位置，m为连续1的末尾，n > m，则：
- A：$(x << n) + (x << n - 1) + ... + (x << m)$
- B：$(x << n + 1) - (x << m)$
关于A和B该如何选有以下判断： $$ \begin{cases} A &: n - m = 1 \ B &: n - m > 1 \ A/B &: n - m = 0 \end{cases} $$

2.8 整数除法运算¶

整数除法总是舍入到零
无符号：对于 $x \ge y$ 和 $y > 0$，结果是$\lfloor x/y \rfloor$，这里对于任何实数 $a$ ，$\lfloor a \rfloor$定义为唯一的整数 $a\rq$，使得 $a\rq \le a < a\rq + 1$。例如：$\lfloor 3.14 \rfloor = 3$
补码：
- 当 $x < 0$ 和 $y > 0$，移位导致结果向下舍入：$\lfloor -3.14 \rfloor = -4$
- 而我们期望的结果应当是 $\lceil x/y \rceil$，即对于任意实数 $a$，$\lceil a \rceil$定义为唯一的证书 $a\rq$，使得 $a\rq - 1 < a \le a\rq$。
- 为了纠正对补码移位导致的向下舍入，引入了“偏置(biasing)”值：对于整数 $x$ 和任意 $y > 0$的 $y$，有$\lceil x/y \rceil = \lfloor (x + y - 1) / y \rfloor$
  - 证明： $$ \begin{aligned} 假设&: x=ky + r \ 所以&：(x + y - 1) / y = k + (r + y - 1) / y \ 因此&：\lfloor (x + y - 1) / y \rfloor = k + \lfloor (r + y - 1) / y \rfloor \begin{cases} r = 0，\lfloor (x + y - 1) / y \rfloor = k \ r > 0，\lfloor (x + y - 1) / y \rfloor = k + 1 \ \end{cases} \end{aligned} $$
  - 因此，对于 $ x < 0 $，如果在右移之前，先将 $x$ 加上 $2^k - 1$，那么我们就会得到正确舍入的结果了。
  - 对于不需要舍入的情况，加上偏置量只影响那些被移掉的位。
  - 对于需要舍入的情况，加上偏置量导致较高的位加1，所以结果会向零舍入。

2.9 二进制小数¶

十进制小数表示：$d = \sum_{i=-n}^m 10^i \times d_i$
二进制小数表示：$d = \sum_{i=-n}^m 2^i \times b_i$
用 $1.0 - \varepsilon$ 表示：$0.11...1_2$

2.10 IEEE浮点表示¶

IEEE浮点标准：$V = (-1)^s \times M \times 2^E$
- 符号（sign）：$s$ 决定这个数是负数（s=1）还是正数（s=0），而对于数值0的符号位解释作为特殊情况处理
- 尾数（significand）：M是一个二进制小数，它的范围是 $1 \backsim 2 - \varepsilon$，或则是 $0 \backsim 1 - \varepsilon$
- 阶码（exponent）：E的作用是对浮点数的加权，这个权重是2的E次幂（可能是负数）
标准浮点格式：
- 单精度：
- 双精度：
浮点值说明（以单精度为例）：
- 规格化的：
  - $E = e - Bias$：e 是无符号数 $e_{k-1}...e_1e_0$，Bias的值为 $2^{k-1} - 1$，因此单精度E的范围为“-126 ~ +127”，双精度为“-1022 ~ +1023”
  - $f$ 为小数值，$0 \le f < 1$，二进制表示为“ $0.f_{n-1}...f_1f_0$ ”，而M的值为“ $M = 1 + f$ ”
- 非规格化的：
  - $E = 1 - Bias$，$M = f$
  - 用处1：这么设计偏置值的原因是提供了一种从非规格化平滑转换到规格化值得方法。
    - +1相当于向左偏移一位，来补偿规格化M多出的1。
  - 用处2：提供了一种表示数值0的方法
    - +0：$s=0,\ e=0,\ f=0$
    - -0：$s=1,\ e=0,\ f=0$
  - 用处3：表示那些非常接近于0.0的数。提供了一种属性，称为“逐渐溢出”，其中，可能的数值分布均匀地接近于0.0
- 无穷大
- NaN（Not a Number）
数值1的位级表示：$s=0,\ e=01..1,\ f=0..0$
这样编排的浮点值，正数被解释成无符号整数就会具有升序的属性。而负数则有降序的属性，当然也能通过对符号位的独立判断，来转化负数成升序。
浮点值得舍入采用的是“向偶舍入”，即向最低有效位为0舍入。
浮点加法
- 除了特殊值外，具有阿尔贝群的属性，有加法逆元，具有交换性，但不具备结合性
- 除了NaN外，具有单调性：$x + a \ge x + b$
- $NaN + x = NaN$
- $+\infin -\infin = NaN$
浮点加法
- 具备交换性，但不具备结合性
- 除了NaN外，具有单调性：
  - $a \ge b 且 c \ge 0 \rArr a *^f c \ge b *^f c$
  - $a \ge b 且 c \le 0 \rArr a *^f c \le b *^f c$
  - $a \ne NaN \rArr a *^f a \ge 0$
浮点类型之前进行强制类型转换：
- 从int转float，数字不会溢出，但是可能被舍入
- 从int或float转double，能够保留精确的数值
- 从double转float，由于范围较小，因此可能溢出为$+ \infin$和$- \infin$，由于精度较小，可能发生舍入
- 从float或则double转换成int，值会向零舍入（实际上，C语言没有给定固定的结果。

第 4 章处理器体系结构¶

4.1 Y86-64¶

重要性质：字节编码必须有唯一的解释。

程序寄存器标识符¶

指令编码¶

指令的功能编码：

4.2 逻辑设计和HCL¶

时序电路：有状态且在这个状态上进行计算的系统。

4.3 Y86-64 的顺序实现¶

阶段：

取址（fetch）
译码（decode）
执行（execute）
访存（memory）
写回（write back）
更新PC（PC update）

5 优化程序性能¶

代码移动（code motion）：识别要执行多次但是计算结果不会改变的值，并将其移动到循坏外面。
消除函数调用，直接访问向量数据
- 编译器很难判断函数是否有副作用
将结果累积到局部变量中
- 编译器很难判断返回变量是否在循环中被改动，因此只能每次都去加载内存

延迟界限（latency bound）：指令级并行，但操作必须顺序执行时会出现。即在下一条指令开始之前，这条指令必须结束。

吞吐量界限（throughput bound）：刻画了处理器功能单元的原始计算能力。该界限是程序性能的终极限制。

超标量（superscalar）：每个时钟周期执行多个操作，而且是乱序的（out-of-order）：

指令控制单元（Instruction ControlUnit，ICU）：负责读出指令序列，并生成一组针对程序数据的基本操作
执行单元（Execution Unit，EU）：执行操作

不要过分关心可预测的分支：现代处理器的分支预测逻辑非常善于辨别不同的分支指令的有规律的模式和长期的趋势。可以说分支预测的问题已经被解决了。

书写适合用条件传送实现的代码

对于寄存器操作，在指令被译码成操作的时候，处理器就可以确定哪些指令会影响其他哪些指令。另一方面，对于内存操作，只有到计算出加载和存储的地址被计算出来之后，处理器才能确定哪些指令会影响其他哪些指令。高效地处理内存操作对许多程序的性能来说至关重要。

优化程序性能的基本策略：

高级设计：为遇到的问题选择适当的算法和数据结构。要特别警觉，避免使用那些会渐进地产生糟糕性能的算法或编码技术。
基本编码原则：避免限制优化的因素，这样编译器就可以产生更高效的代码。
- 消除连续的函数调用
- 消除不必要的内存引用
- 内存别名（memory aliasing）：指的是两个指针指向同一个内存位置。要避免内存别名，可以使用restrict关键字。
低级优化：结构化代码以利用硬件功能
- 展开循环，降低开销，并且使得进一步的优化成为可能
- 通过使用例如多个积累变量和重新结合等技术，找到方法提高指令级并行性
  - 将数值保存在局部变量中，使得他们可以存放在寄存器中
- 用功能性的风格重写条件操作，使得编译器可以使用条件传送指令
- 使分支更容易预测，例如，通过重排循环中的测试，使得循环的主体总是被执行

程序剖析（Profiling）：

GPROF
VTUNE
VALGRIND

第 6 章存储器层次结构¶

程序员理解存储器层次结构的重要性

作为一个程序猿，你需要理解存储器层次结构，因为它对应用程序的性能有着巨大的影响。如果你的程序需要的数据是存储在CPU寄存器中的，那么在指令的执行期间，在0个周期内就能访问到它们。如果存储在高速缓存中，需要4～75个周期。如果存储在主存中，需要上百个周期。而如果存储在磁盘上，需要大约几千万个周期！

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

重点概念“局部性”：具有良好局部性的程序倾向于一次又一次地访问相同的数据项，或者是访问邻近的数据项。

6.1 存储技术¶

6.1.1 随机访问存储器（Random Access Memory，RAM）¶

静态RAM（Static RAM，SRAM）：双稳态

双稳态

一个双稳态元件有两个稳定的状态，分别对应着两个不同的电压值。当电压值为低时，元件处于低电压状态；当电压值为高时，元件处于高电压状态。当电压值在低电压状态和高电压状态之间切换时，元件会保持在原来的状态，直到电压值超过一个临界值，此时元件会切换到另一个状态。

只要有电，就会永远地保持它的值。即使有干扰来扰乱典雅，当干扰消除时，电路就会恢复到稳定值。

动态RAM（Dynamic RAM，DRAM）：对干扰非常敏感。当电容的电压被扰乱后，它就永远都不会恢复了。因此它需要频繁的读写。

SRAM vs DRAM：

无需刷新
存取更快
抗干扰能力更强
密集度更低
更贵
功耗更大

DRAM的内部结构：

DRAM芯片中的单元（位）被分成 $d$ 个超单元（supercell），每个超单元都由 $w$ 个DRAM单元组成。一个 $d \times w$ 的DRAM芯片总共存储了 $dw$ 位信息。超单元被组织成一个 $r$ 行 $c$ 列的长方形阵列，这里 $rc = d$。

如上图所示的 $16x8$ 的DRAM芯片，它有 $16$ 个超单元，每个超单元有 $8$ 个DRAM单元。它被组织成一个 $4x4$ 的阵列，其中 $r = 4$ 行，$c = 4$ 列，$rc = 16 = d$。
特定超单元的表达方式为“$(r, c)$”，它由内存控制器输入，如图由2个引脚的addr输入。在这里 $r$ 和 $c$ 共用addr的2个引脚，因此addr的宽度为$\log_2\text{max}(r, c)$。
内存控制器首先输入 $r$ 给DRAM芯片，此时DRAM芯片会拷贝整个 $r$ 行进入到“内部行缓冲区”，然后再输入 $c$ 给DRAM芯片，此时DRAM芯片会将“内部行缓冲区”的 $c$ 列通过 data 输出给内存控制器，在此图中为8个引脚。其中 $r$ 的地址称为“行访问选通脉冲（RAS，Row Access Strobe）”，$c$ 的地址称为“列访问选通脉冲（CAS，Column Access Strobe）”：

电路设计者将DRAM组织成二维阵列而不是线性数组的一个原因是 降低芯片上地址引脚的数量；缺点是 必须分两步发送地址，这增加了访问时间。

内存模块： DRAM芯片封装在“内存模块”中，它插到主板的插槽上。

图中由8个64 Mbit 的 8M x 8 的DRAM芯片组成，因此总内存大小为 $ \text{Total Memory} = 8 \times 8 MB = 64 MB$；
每个超单元提供一个字节的数据，共同组成主存中的64位数据；
提取方式是，内存控制器将 A 地址翻译成 $(i, j)$，然后广播到每个DRAM芯片中。作为响应，每个DRAM输出它们的 $(i, j)$ 上的内容给内存控制器。内存模块中的电路收集这些输出并合并成一个64位字，然后返回给内存控制器；
通过将多个内存模块连接到内存控制器，聚合成主存。

增强DRAM：

快页模式DRAM（Fast Page Mode DRAM，FPM DRAM）扩展数据输出DRAM（Extended Data Out DRAM，EDO DRAM）

FPM 允许对同一行连续地访问；即要从一个读取一行中的4个超单元，只需要发送一次RAS/CAS，随后跟三个CAS。

FPM 的增强；

同步DRAM（Synchronous DRAM，SDRAM）
双倍数据速度同步DRAM
视频RAM（Video RAM, VRAM）

6.1.2 非易失性存储器¶

DRAM 和 SRAM 在断电后都会丢失信息，因此它们是 易失的。非易失存储器（Nonvolatile Memory）可以在断电后保持信息。

ROM（Read-Only Memory）：ROM 以它们能够被重写次数和重新编程的机制进行区分

PROM（Programmable ROM）：只能被变成一次。PROM的每个存储器单元有一种熔丝，只能用高电流熔断一次。
EPROM（Erasable Programmable ROM）：
- 可以被擦除并重新编程；
- EPROM的每个存储器单元有一种称为浮栅的结构，可以用紫外线擦除；
- 它的需要用到特殊设备将1写入；
- 可擦写次数达1000次。
EEPROM（Electrically Erasable Programmable ROM）：可以通过电子擦除，而不需要紫外线。可编程次数的数量级可以达到 $ 10^5 $。
闪存（Flash memory）：是一种EEPROM，它可以被分成更大的块，每个块可以被独立地擦除。基于闪存的磁盘驱动器称为“固态硬盘（Solid State Disk，SSD）”，

存储在 ROM 设备中的程序通常称为 固件（firmware）。当一个计算机系统通电后会运行存储在 ROM 中的固件。

6.1.3 访问主存¶

数据流通过 Bus 的共享电子电路在处理器和 DRAM 主存之间来回传输。每次 CPU 和主存之间的数据传送都通过一系列步骤完成，这些步骤称为“总线事务（Bus transaction）”。

读事务：从主存传送数据到 CPU
写事务：从 CPU 传送数据到主存

Bus 是一组并行的导线，能携带地址、数据和控制信号。

关于总线设计的注释

总线设计是计算机系统一个复杂而且变化迅速的方面。不同的厂商提出了不通的总线体系结构，作为产品差异化的一种方法。例如，Intel 系统使用称为 “北桥” 和 “南桥” 的芯片组分别将 CPU 连接到内存和I/O设备。在比较老的 Pentium 和 Core2 系统中，前端总线（Front Side Bus，FSB）将 CPU 连接到北桥，。来自 AMD 的系统将 FSB 替换为超传输（Hyper Transport）互联，而更新一些的 Intel Core i7 系统使用的是快速通道（QuickPath）互联。

6.1.4 磁盘存储¶

磁盘构造：

磁盘由盘片（platter）组成，每个盘片由两面（surface），表面覆盖着磁性记录材料。盘片中央由一个可以旋转的主轴（spindle），它使得盘片以固定旋转速率（rotational rate）旋转，通常是 5400 ~ 15 000 转每分钟（Revolution Per Minute，RPM）。
每个表面由一组同心圆的磁道（track）组成。每个磁道被划分为一组扇区（sector）。每个扇区包含相等数量的数据位（通常是512字节），这些数据编码在扇区上的磁性材料中。扇区之间由一些间隙（gap）分隔开，这些间隙中不存储数据位。间隙存储用来标识扇区的格式化位。
柱面是所有盘片表面上到主轴中心的距离相等的磁道的集合。

磁盘容量：一个磁盘可以记录的最大位数称为它的最大容量，容量由以下技术因素决定：

记录密度（recording density）（位/英寸）：磁道一英寸的段中可以放入的位数；
磁道密度（track density）（道/英寸）：从盘片中心出发半径上一英寸的段内可以有的磁道数；
面密度（areal density）（位/平方英寸）：记录密度和磁道密度的乘积

$$ 磁盘容量 = \frac {字节数} {扇区} \times \frac {平均扇区数} {磁道} \times \frac {磁道数} {表面} \times \frac {表面数} {盘片} \times \frac {盘片数} {磁盘} $$·

注意

制造商以 GB 或 TB 位单位表达磁盘容量，这里 $ 1 GB = 10^9 B，1 TB = 10^{12} B $

磁盘操作：磁盘以扇区大小的块来读写数据，对扇区访问时间主要有以下三个部分

寻道时间：
旋转时间：
传送时间：

不要过分关心可预测的分支：现代处理器的分支预测逻辑非常善于辨别不同的分支指令的有规律的模式和长期的趋势。可以说分支预测的问题已经被解决了。 书写适合用条件传送实现的代码：

对于寄存器操作，在指令被译码成操作的时候，处理器就可以确定哪些指令会影响其他哪些指令。另一方面，对于内存操作，只有到计算出加载和存储的地址被计算出来之后，处理器才能确定哪些指令会影响其他哪些指令。高效地处理内存操作对许多程序的性能来说至关重要。

优化程序性能的基本策略：

高级设计：为遇到的问题选择适当的算法和数据结构。要特别警觉，避免使用那些会渐进地产生糟糕性能的算法或编码技术。
基本编码原则：避免限制优化的因素，这样编译器就可以产生更高效的代码。
- 消除连续的函数调用
- 消除不必要的内存引用
- 内存别名（memory aliasing）：指的是两个指针指向同一个内存位置。要避免内存别名，可以使用restrict关键字。
低级优化：结构化代码以利用硬件功能
- 展开循环，降低开销，并且使得进一步的优化称为可能
- 通过使用例如多个积累变量和重新结合等技术，找到方法提高指令级并行性
  - 将数值保存在局部变量中，使得他们可以存放在寄存器中
- 用功能性的风格重写条件操作，使得编译器可以使用条件传送指令
- 使分支更容易预测，例如，通过重排循环中的测试，使得循环的主体总是被执行

程序剖析（Profiling）：

GPROF
VTUNE
VALGRIND

第 6 章存储器层次结构¶

程序员理解存储器层次结构的重要性

作为一个程序猿，你需要理解存储器层次结构，因为它对应用程序的性能有着巨大的影响。如果你的程序需要的数据是存储在CPU寄存器中的，那么在指令的执行期间，在0个周期内就能访问到它们。如果存储在高速缓存中，需要4～75个周期。如果存储在主存中，需要上百个周期。而如果存储在磁盘上，需要大约几千万个周期！

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

重点概念“局部性”：具有良好局部性的程序倾向于一次又一次地访问相同的数据项，或者是访问邻近的数据项。

6.1 存储技术¶

随机访问存储器（Random Access Memory，RAM）：

静态RAM（Static RAM，SRAM）：双稳态

双稳态

一个双稳态元件有两个稳定的状态，分别对应着两个不同的电压值。当电压值为低时，元件处于低电压状态；当电压值为高时，元件处于高电压状态。当电压值在低电压状态和高电压状态之间切换时，元件会保持在原来的状态，直到电压值超过一个临界值，此时元件会切换到另一个状态。

SRAM
- 只要有电，就会永远地保持它的值。即使有干扰来扰乱典雅，当干扰消除时，电路就会恢复到稳定值。
动态RAM（Dynamic RAM，DRAM）：对干扰非常敏感。当电容的电压被扰乱后，它就永远都不会恢复了。因此它需要频繁的读写。

SRAM vs DRAM：

无需刷新
存取更快
抗干扰能力更强
密集度更低
更贵
功耗更大

DRAM的内部结构：

DRAM芯片中的单元（位）被分成 $d$ 个超单元（supercell），每个超单元都由 $w$ 个DRAM单元组成。一个 $d \times w$ 的DRAM芯片总共存储了 $dw$ 位信息。超单元被组织成一个 $r$ 行 $c$ 列的长方形阵列，这里 $rc = d$。

如上图所示的 $16x8$ 的DRAM芯片，它有 $16$ 个超单元，每个超单元有 $8$ 个DRAM单元。它被组织成一个 $4x4$ 的阵列，其中 $r = 4$ 行，$c = 4$ 列，$rc = 16 = d$。
特定超单元的表达方式为“$(r, c)$”，它由内存控制器输入，如图由2个引脚的addr输入。在这里 $r$ 和 $c$ 共用addr的2个引脚，因此addr的宽度为$\log_2\text{max}(r, c)$。
内存控制器首先输入 $r$ 给DRAM芯片，此时DRAM芯片会拷贝整个 $r$ 行进入到“内部行缓冲区”，然后再输入 $c$ 给DRAM芯片，此时DRAM芯片会将“内部行缓冲区”的 $c$ 列通过 data 输出给内存控制器，在此图中为8个引脚。其中 $r$ 的地址称为“行访问选通脉冲（RAS，Row Access Strobe）”，$c$ 的地址称为“列访问选通脉冲（CAS，Column Access Strobe）”：

电路设计者将DRAM组织成二维阵列而不是线性数组的一个原因是 降低芯片上地址引脚的数量；缺点是 必须分两步发送地址，这增加了访问时间。

内存模块： DRAM芯片封装在“内存模块”中，它插到主板的插槽上。

图中由8个64 Mbit 的 8M x 8 的DRAM芯片组成，因此总内存大小为 $ \text{Total Memory} = 8 \times 8 MB = 64 MB$；
每个超单元提供一个字节的数据，共同组成主存中的64位数据；
提取方式是，内存控制器将 A 地址翻译成 $(i, j)$，然后广播到每个DRAM芯片中。作为响应，每个DRAM输出它们的 $(i, j)$ 上的内容给内存控制器。内存模块中的电路收集这些输出并合并成一个64位字，然后返回给内存控制器；
通过将多个内存模块连接到内存控制器，聚合成主存。

增强DRAM：

快页模式DRAM（Fast Page Mode DRAM，FPM DRAM）：
扩展数据输出DRAM（Extended Data Out DRAM，EDO DRAM）：
同步DRAM（Synchronous DRAM，SDRAM）：
双倍数据速度同步DRAM

引用¶

书本配套资源

C声明	32位机器	64位机器
char	1	1
short int	2	2
int	4	4
long int	4	8
long long int	8	8
char *	4	8
float	4	4
double	8	8

深入理解计算机系统

第 1 章 计算机系统漫游¶

1.1 基础知识¶

1.2 典型系统的硬件组成¶

1.3 运行hello程序¶

1.4 高速缓存至关重要¶

1.5 操作系统¶

1.6 并发和并行¶

第 2 章 信息的表示和处理¶

2.1 进制间的转换¶

2.2 寻址和字节顺序¶

2.3 位级运算¶

2.4 整数表示¶

2.5 扩展数字¶

2.6 整数加法运算¶

2.7 整数乘法运算¶

2.8 整数除法运算¶

2.9 二进制小数¶

2.10 IEEE浮点表示¶

第 4 章 处理器体系结构¶

4.1 Y86-64¶

程序寄存器标识符¶

指令编码¶

4.2 逻辑设计和HCL¶

4.3 Y86-64 的顺序实现¶

5 优化程序性能¶

第 6 章 存储器层次结构¶

6.1 存储技术¶

6.1.1 随机访问存储器（Random Access Memory，RAM）¶

6.1.2 非易失性存储器¶

6.1.3 访问主存¶

6.1.4 磁盘存储¶

第 6 章 存储器层次结构¶

6.1 存储技术¶

引用¶

评论

第 1 章计算机系统漫游¶

第 2 章信息的表示和处理¶

第 4 章处理器体系结构¶

第 6 章存储器层次结构¶

第 6 章存储器层次结构¶