9000字总结，一文掌握737页程序员圣经《深入理解计算机系统》（第三版）重点数据结构与算法Light.T的博客-

一、处理器体系结构

1.CPU中的时序电路

1. 指令集体系结构：一个处理器支持的指令和指令的字节级编码
2. RISC和CISC：RISC：复杂指令集计算机；CISC：精简指令集计算机
3. 逻辑门是数字电路的基本计算单元。
4. 将很多的逻辑门组成一个网就能构建计算块，称为组合电路。
5. 构建组合电路的限制：
   1. 每个逻辑门的输入必须连接到下述选项之一：
      • 一个系统输入（称为主输入）
      • 某个存储器单元的输出
      • 某个逻辑门的输出
   2. 两个或多个逻辑门的输出不能连接在一起。
   3. 这个网必须是无环的。
6. 时序电路：有状态并且在这个状态上进行计算的系统。

2.单周期处理器的设计

1. 取指：从内存读取指令字节，地址为程序计数器（PC）的值

2. 译码：从寄存器文件读入最多两个操作数得到值valA和/或valB。

3. 执行：ALU要么执行指令指明的操作，计算内存引用的有效地址，要么增加或减少栈指针。

4. 访存：将数据写入内存或从内存读取数据。

5. 写回：最多可以写两个结果到寄存器文件。

6. 更新PC：将PC设置成下一条指令的地址。

3.流水线处理器的基本原理

1. 流水线化的一个重要特性就是提高系统的吞吐量
2. 吞吐量：单位时间内执行的指令条数，即指令数除以运行时间。单位是GIPS每秒千兆条指令（每秒十亿条指令）。
3. 延迟：从头到尾执行一条指令所需要的时间
4. 流水线的局限性：
   1. 不一致的划分，系统的吞吐量受最慢阶段的速度所限制
   2. 流水线过深，受益反而下降，由寄存器更新引起的延迟成为一个限制因素。

4.Data Hazard的处理

1. 冒险就是一条指令的位置或者操作数依赖于其他仍在流水线中的指令。
2. 数据相关：下一条指令会用到这一条指令计算出的结果。
3. 控制相关：一条指令会确定下一条指令的位置。
4. 数据冒险出现的原因：流水线化的处理器在译码阶段从寄存器文件中读取指令的操作数。
5. 如何避免数据冒险：
   1. 用暂停来避免数据冒险
   2. 用转发来避免数据冒险
6. 控制冒险：会发生在ret指令和跳转指令（只有在条件跳转方向预测错误时才会造成麻烦）
7. 分支预测：猜测分支方向并根据猜测开始取指的技术。

5.流水线设计中的其他问题

1. 加载/使用数据冒险【处理用加载互锁和转发技术结合起来】

2. 处理ret【流水线停顿三个时钟周期，直到ret指令经过访存阶段，读出返回地址】

3. 预测错误的分支【控制逻辑在译码和执行阶段插入气泡】

4. 异常 【解决方法如下：

   1. 禁止执行阶段中的指令设置条件码
   2. 向内存阶段中插入气泡，以禁止向数据内存写入
   3. 当写回阶段中有异常指令时，暂停写回阶段，因而暂停了流水线。】

二、优化程序性能

1.优化程序性能

1. 程序员要编写清晰简洁的代码，编写高效程序需要做到以下两点：

   1. 必须选择一组适当的算法和数据结构。
   2. 必须编写出编译器能够有效优化以转换成高效可执行代码的源代码。

2. 优化程序性能的步骤如下：

   1. 消除不必要的工作，让代码尽可能有效地执行所期望的任务。这包括消除不必要的函数调用、条件测试和内存引用。这些优化不依赖于目标机器的任何具体属性。
   2. 利用处理器提供的指令级并行能力，同时执行多条指令。

   【关键路径是在循环的反复执行过程中形成的数据相关链】

2.优化编译器的能力和局限性以及表示程序性能

1. 最简单的优化控制是指定优化级别，编译器对程序只使用安全的优化。

2. 妨碍优化的因素包括内存别名使用和函数调用。【两个指针指向同一个内存位置的情况】

3. 度量标准每元素的周期数CPE可作为一种表示程序性能并指导代码改进的方法，表示执行了多少条指令。

3.特定体系结构或应用特性的性能优化

1. 消除不必要的工作，方法如下：

   1. 消除循环带来的低效，使用代码移动解决，
   2. 减少过程调用。
   3. 消除不必要的内存引用。
   4. 理解现代处理器
   5. 循环展开
   6. 提高并行性【使用多个累积变量，重新结合变换】

2. 代码移动指识别要执行多次但计算结果不会改变的计算，可将计算移动到代码前面不会被多次求值的部分。

3. 利用处理器微体系结构的优化

4. 程序的最大性能描述：

   1. 延迟界限（代码中的数据相关限制了处理器利用指令级并行的能力）
   2. 吞吐量界限（处理器功能单元的原始计算能力）。

5. 循环展开是一种程序变换，通过增加每次迭代计算的元素的数量，减少循环的迭代次数。提高并行性，使用多个累计变量，重新结合变换。

6. 重新结合变换能减少计算中关键路径上的操作数量，通过更好地利用功能单元的流水线能力得到更好的性能。

4.限制因素

1. 寄存器溢出

2. 分支预测和预测错误处罚

3. 分支预测通用原则：

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

5.确认和消除性能瓶颈

1. 程序剖析运行程序的一个版本，其中插入了工具代码，以确定程序的各个部分需要多少时间。可以使用剖析程序来指导优化。

2. Unix系统提供了一个剖析程序GPROF，这个程序产生两种形式的信息，

   1. 确定程序中每个函数花费了多少CPU时间。
   2. 计算每个函数被调用的次数，以执行调用的函数来分类。

3. GPROF的属性：

   1. 计时不是很准确
   2. 假设没有执行内联替换，则调用信息相当可靠。
   3. 默认情况下不会显示对库函数的计时。

三、存储器结构及虚拟存储器

1.局部性

1. 时间局部性：被引用过一次的内存位置可在不远的将来再被多次引用。

2. 空间局部性：如果一个内存位置被引用了一次，那么程序可能在不远的将来引用附近的一个内存位置。

3. 评价局部性原则：

   1. 重复引用相同变量有良好的时间局部性
   2. 对于具有步长为1的引用模式的程序有很好的空间局部性。
   3. 对于取指令来说，循环有好的时间和空间局部性，循环体越小，循环迭代次数越多，局部性越好。

2.存储器层级结构

1. 组织存储器系统的方法：

   1. CPU寄存器
   2. 高速缓存SRAM
   3. 主存DRAM
   4. 本地二级存储（本地磁盘）

3.计算机高速缓存器原理

1. 存储器层次结构的中心思想：

   对于每个k,位于k层的更快更小的存储设备作为位于k+1层的更大更慢的存储设备的缓存。

2. 缓存不命中的种类：

   1. 强制性不命中
   2. 冲突不命中
   3. 容量不命中

3. 高速缓存可分为：直接映射高速缓存、组相联高速缓存、全相联高速缓存

   1. 直接映射高速缓存：每个组只有一行的高速缓存。【抽取出被请求的字的过程分为三步：1.组选择2.行匹配3.字抽取】
   2. 组相联高速缓存：每个组都保存有多于一个的高速缓存行。
   3. 全相联高速缓存：一个包含所有高速缓存行的组。

4. 抖动是指高速缓存反复地加载和驱逐相同的高速缓存块的组。

5. 有关写的问题：

   1. 直写法：将w的高速缓存块写回到紧接着的低一层中。
   2. 写回法：只有要驱逐块时才写入，需要额外的一个修改位。
   3. 写分配：加载相应的低一层中的块到高速缓存，然后更新这个高速缓存块。
   4. 非写分配：避开高速缓存，直接把这个字写到低一层中。

6. 直写高速缓存通常是非写分配的，写回高速缓存通常是写分配的。

4.高速缓存对性能的影响

1. 衡量指标：不命中率、命中率、命中时间、不命中惩罚

   1. 高速缓存大小的影响【较大的高速缓存提高命中率，增加命中时间。】
   2. 块大小的影响【空间局部性好，提高命中率，行数少损害时间局部性差的命中率】
   3. 相联度的影响【高相联度降低抖动的可能性，高相联度意味着高成本，增加命中时间，增加不命中惩罚】
   4. 写策略的影响【传送时间增加使减少传送的数量变的更重要，高速缓存越往下层，越可能使用写回而不是直写】

2. 代码高速缓存友好的方法：

   1. 让最常见的情况运行得快。
   2. 尽量减小每个循环内部的缓存不命中数量。

3. 编写高速缓存友好代码的重要问题：

   1. 对局部变量的反复引用是好的。【因为编译器能将它们缓存在寄存器文件中（时间）】
   2. 步长为1的引用模式是好的。【缓存都是将数据存储为连续的块（空间）】

5.地址空间

1. 地址空间是一个非负整数地址的有序集合。

2. 地址空间区分了数据对象（字节）和它们的属性（地址）。

3. 虚拟内存为每个进程提供了一个大的一致的和私有的地址空间。

4. 虚拟内存的作用：

   1. 它将主存看成是一个存储在磁盘上的地址空间的高速缓存。

   2. 为每个进程提供了一致的地址空间。

   3. 保护了每个地址空间不被其他进程破坏。

6.虚拟存储器

1. SRAM缓存是CPU和主存之间的L1L2L3高速缓存。

2. DRAM缓存是虚拟内存系统的缓存，在主存中缓存页。【因为大的不命中惩罚，DRAM缓存是全相联的，任何物理页都可以包含任何虚拟页】

3. 页表将虚拟地址页映射到物理页，每次地址翻译硬件将一个虚拟地址转换为物理地址时都会读取页表。

4. 缺页：DRAM缓存不命中称为缺页。

5. 交换页面调度：在磁盘和内存之间传送页的活动。

7.虚拟内存的管理

1. 虚拟内存作为内存管理的工具

   1.简化链接

   2.简化加载

   3.简化共享

   4.简化内存分配

2. 虚拟内存作为内存保护的工具

8.翻译和映射

1. 地址翻译是一个虚拟地址空间到物理地址空间之间的映射。

2. 内存映射是将一个虚拟内存区域与一个磁盘上的对象关联起来，以初始化这个虚拟内存区域的内容。

9.TLB

1. TLB是翻译后备缓冲器，一个小的虚拟寻址的缓存。
2. TLB通常具有高度的相联度。
3. TLB索引由VPN（虚拟地址）的t个最低位组成，TLB标记由VPN中剩余的位组成。

10.动态存储器分配和垃圾收集

1. 动态内存分配器分为显式分配器和隐式分配器，隐式分配器也叫垃圾回收器
2. 垃圾回收是指自动释放未使用的已分配的块的过程。
3. 内部碎片：在已分配块比有效荷载大时发生，只取决于以前请求的模式和分配器的实现方式。
4. 外部碎片：空闲内存合计起来足够满足一个分配请求，但是没有一个单独的空闲块足够大可以来处理这个请求时发生。

四、链接、进程及并行编程

1.静态链接

1. 链接是将各种代码和数据片段收集并组合成为一个单一文件的过程，这个文件可被加载（复制）到内存并执行。链接可执行于编译时，加载时，运行时。链接由链接器自动执行，这使分离编译成为可能。
2. 静态链接器以一组可重定位目标文件和命令行参数作为输入，生成一个完全链接的，可以加载和运行的可执行目标文件作为输出。链接器有符号解析和重定位两个任务。目标文件是字节块的集合，链接器将这些块连接起来，确定被连接块的运行时位置，并且修改代码和数据块中的各种位置。

2.目标文件

1. 目标文件有三种形式：可重定位目标文件、可执行目标文件、共享目标文件
   1. 编译器、汇编器生成可重定位目标文件。
   2. 链接器生成可执行目标文件。
   3. 一个目标模块就是一个字节序列，一个目标文件是一个以文件形式存放在磁盘中的目标模块。

3.符号和符号表

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

   1. 由模块m定义并能被其他模块引用的全局符号。全局链接器符号对应于非静态的C函数和全局变量。
   2. 由其他模块定义并被模块m引用的全局符号。这些符号称之为外部符号，对应于在其他模块中定义的非静态C函数和全局变量。
   3. 只被模块m定义和引用的局部符号。对应于带static属性的C函数和全局变量。这些符号在模块m中任何位置都可见，但是不能被其他模块引用。

2. 符号表是由汇编器构造的，使用编译器输出到汇编语言.s文件中的符号。.symtab节记录符号表信息，是一个结构数组。

3. 符号解析：

   1. 符号解析指把代码中的每个符号引用和与它输入的可重定位目标文件的符号表中的一个确定的符号定义关联起来。

   2. 函数和已初始化的全局变量是强符号，未初始化的全局变量是弱符号。通

   3. 过符号解析可以了解到目标模块中的代码节和数据节的确切大小。

4. 根据强弱规则的定义，使用下列规则处理多重定义的符号名：

   规则1：不允许有多个同名的强符号。

   规则2：如果有一个强符号和多个弱符号同名，那么选择强符号。

   规则3：如果有多个弱符号同名，那么从这些弱符号中任意选择一个。

4.重定位和加载

1. 重定位

   1. 重定位将合并输入模块，并为每个符号分配运行时地址。

   2. 由两步组成：重定位节和符号定义。

   3. 链接器将所有相同类型的节合并为同一类型的新的聚合节，并将运行时内存地址赋给新的聚合节。

   4. 重定位节中的符号引用，链接器修改代码节和数据节中对每个符号的引用，使它们指向正确的运行时地址。重定位的主要类型有PC相对地址和绝对地址。

2. 加载：加载器将可执行目标文件中的代码和数据从磁盘复制到内存汇总，然后通过跳转到程序的第一条指令或入口点来运行该程序。这个将程序复制到内存并运行的过程叫做加载。

5.动态链接库

1. 动态链接库是一个目标模块，在运行或加载的时候，可以加载到任意的内存地址，并和一个在内存中的程序链接起来。这个过程叫做动态链接，由动态链接器执行。

6.异常与进程

​ 1. 异常是控制流中的突变，用来响应处理器状态中的某些变化。

​ 2. 异常可以分为中断、陷阱、故障和终止，

​ 3. 中断是异步发生的，是来自处理器外部的I/O设备的信号的结果，硬件中断的异常处理程序被称为中断处理程序。

​ 4. 其他三个是同步发生的，是执行当前指令的结果，我们把这类指令叫做故障指令。

​ 5. 陷阱是有意的异常，最重要的用途是在用户和程序中提供一个像过程一样的接口，叫系统调用。

​ 6. 故障由错误情况引起，经典示例是缺页异常，处理程序要么重新执行当前指令，要么终止。

​ 7. 终止是不可恢复的致命错误造成的结果。

​ 8. 进程是一个执行中程序的实例，进程轮流使用处理器，可抽象为它在独立使用处理器的假象，

​ 9. 多个流并发地执行的一般现象被称为并发，

​ 10. 进程有运行、停止、终止三种状态。

7.进程控制和信号

1. 当内核选择一个新的进程运行时，我们说内核调度了这个进程，调度后抢占当前进程，并使用一种称为上下文切换的机制来将控制转移到新的进程。

   • 获取进程ID可以用getpid函数和getppid函数。
   • 父进程通过调用fork函数创建一个新的运行的子进程，fork函数调用一次返回两次，并发执行，拥有相同但是独立的地址空间，共享文件。
   • 可以调用waitpid函数等待它的子进程终止或者停止。
   • sleep函数将一个进程挂起一段指定的时间，pause函数让调用函数休眠，直到该进程收到一个信号。
   • execve函数在当前进程的上下文中加载并运行一个新程序，execve调用一次并从不返回。

2. 信号是一种软件中断的形式，允许进程和内核中断其他进程，一个信号就是一条小消息，它通知进程系统中发生了一个某种类型的事件，信号提供了一种机制，通知用户发生了这些异常。

8.进程间的通信

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

   1. 发送信号。内核通过更新目的进程上下文中的某个状态，发送一个信号给目的进程。

      ① 用/bin/kill程序可以向另外的进程发送任意的信号；

      ② 从键盘发送信号；

      ③ 进程通过调用kill函数发送信号给其他进程（包括它们自己）；

      ④ 进程可以通过调用alarm函数向它自己发送SIGALRM信号。

   2. 接受信号。当目的进程被内核强迫以某种方式对信号的发送做出反应是，它就接收了信号。进程通过执行信号处理程序捕获这个信号。每个信号类型都有一个预定义的默认行为：进程终止、进程终止并转储内存、进程停止（挂起）直到被SIGCONT信号重启、进程忽略该信号。

9.进程间信号量的控制

1. 使用信号量可以实现互斥，调度共享资源，提高并行性。

10.信号量

1. 信号量是具有非负整数值的全局变量，只能由两种特殊的操作来处理，这两种操作称为P和V，

2. P（s）:如果s是非零的，那么P将s减1并立即返回。如果s为零那么就挂起这个进程直到s变为非零，而一个V操作会重启这个线程。

3. V（s）:V操作将s加1。

4. 可以使用信号量来实现互斥、来调度资源

11.各种并发编程模式

1. 并发：逻辑控制流在时间上重叠，并发的好处：

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

2. 并发程序：使用应用级并发的应用程序，三种构造并发程序的方法：

   1. 基于进程的并发编程

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

   3. 基于线程的并发编程

3. 基于进程的并发编程

   1. 进程有独立的虚拟地址空间，需使用进程间通信机制。
   2. 在父子进程之间共享状态信息，进程有一个非常清晰的模型：共享文件表但不共享用户地址空间。
   3. 用户有独立的地址空间有优缺点：优点是不会覆盖另一个进程，缺点是使为了共享信息必须使用显式的IPC（进程间通信）机制，以及慢。

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

   1. 所有的流都共享同一个地址空间。
   2. I/O多路复用的基本思路就是使用select函数，要求内核挂起进程，只有在一个或多个I/O事件发生后，才将控制返回给应用程序。
   3. I/O多路复用可以用做并发事件驱动程序的基础，一般的思路是将逻辑流转化为状态机。
   4. 状态机就是一组状态、输入事件和转移。转移就是将状态和输入事件映射到状态。
   5. 优点：1.给了程序员更多对程序行为的控制2.每个逻辑流能访问该进程的全部地址空间。3.比基于进程更高效。
   6. 缺点：1.编码复杂 2.不能充分利用多核处理器。

5. 基于线程的并发编程，

   1. 线程是运行在一个单一进程上下文中的逻辑流，由内核进行调度。
   2. 线程是其他两种方式的混合体，像进程流一样由内核进行调度，像I/O多路复用流一样共享同一个虚拟地址空间。
   3. 线程是可结合或者分离的，一个可结合的线程能被其他线程回收和杀死，分离的线程不能被其他线程回收和杀死，它的内存资源在它终止时由系统自动释放。

12.共享变量和线程同步

1. 互斥：每个线程在执行它的临界区域中的指令是拥有对共享变量的互斥的访问。

2. 共享变量：当且仅当有多个线程引用这个变量的某个实例时，这个变量是共享的。

3. 不安全区：两个临界区的交集形成的状态空间区域称为不安全区。

13.其他并行问题

1. 其他并行问题:

   1. 线程安全
   2. 可重入性
   3. 在线程化的程序中使用已存在的库函数
   4. 竞争
   5. 死锁

2. 四个线程不安全函数类：

   1. 不保护共享变量的函数【使用PV操作保护共享变量】
   2. 保持跨越多个调用的状态的函数【重写】
   3. 返回指向静态变量的指针的函数【1.重写 2.使用加锁-复制技术】
   4. 调用线程不安全函数的函数【2类重写；1、3类使用互斥锁保护】

3. 可重入性的属性：当他们被多个函数调用时不会引用任何共享数据。

4. 竞争：一个程序的正确性依赖于一个线程要在另一个线程到达y点之前到达它的控制流中的x点时，就会发生竞争。

5. 死锁：一组线程被阻塞了，等待一个永远也不会为真的条件。

五、系统及I/O和网络编程

1.I/O相关概念

1. 输入/输出（I/O）是在主存和外部设备（例如磁盘驱动器、终端和网络）之间复制数据的过程。输入操作是从I/O设备复制数据到主存，输出操作是从主存复制数据到I/O设备。

2.文件及文件操作

1. 文件都有一个类型来表明它在系统中的角色：普通文件、目录、套接字。

   • 普通文件，包含任意数据，应用程序常常要区分文本文件和二进制文件
   • 目录，是包含一组链接的文件，每个链接都将一个文件名映射到一个文件
   • 套接字，用来与另一个进程进行跨网络通信的文件。

2. 文件操作

   1. 进程通过调用open函数来打开一个已存在的文件或者创建一个新文件。【打开文件】
   2. 调用close函数关闭一个打开的文件。【关闭文件】
   3. 通过调用read和write函数执行输入和输出。【读和写文件】
   4. 通过调用lseek函数显示地修改当前文件的位置。【改变当前文件的位置】
   5. 通过调用stat函数和fstat函数，检索到关于文件的信息（元数据）。【读取文件元数据】
   6. 用readdir系列函数来读取目录的内容。【读取目录文件】

3.共享文件

1. 内核用描述符表、文件表、v-node表三个数据结构表示打开的文件。

2. 每个进程都有它自己单独的描述符表。

3. 打开文件的集合是由一张文件表来表示的，所有的进程共享同一个打开文件表。

4. 所有的进程共享一张v-code表。

5. 共享文件指多个描述符可以通过不同的文件表表项来引用同一个文件。

4.网络编程

1. 所有的网络应用都是基于相同的基本编程模型，有相似的整体网络逻辑结构，并且依赖相同的编程接口。

2. 主机序：主机字节顺序，小端法存放。网络序：大端法存放。

3. 最低有效字节在地址排序最前面的方法叫小端法，

4. 最高有效字节在地址排序最前面的方法叫大端法。

5.客户端-服务器模型

1. 模型由一个服务器进程和一个或多个客户端进程组成。

2. 服务器管理某种资源，并且通过操作这种资源来为它的客户端提供某种服务。

3. 模型中的基本操作是事务，事务由发送请求、处理请求、发送响应、处理响应四步组成。

4. IPv4和IPv6：因特网协议版本4，采用32位地址。因特网协议版本6，采用128位地址。

6.套接字接口

1. 套接字接口是一组函数，用以创建网络应用。

2. 客户端和服务器通过使用套接字接口建立连接。

3. 一个套接字就是通信的一个端点，从程序角度套接字就是一个有相应描述符的打开文件。

7.HTTP请求

1. HTTP请求组成如下：一个请求行，后面跟随零个或更多个请求报头，再跟随一个空的文本行来终止报头列表。

2. HTTP响应组成如下：一个响应行，后面跟随0或者更多的响应报头，在跟随一个终止报头的空行，在跟随一个响应主体。

8.Web服务器

1. Web客户端和服务器之间的交互用的是一个基于文本的应用级协议HTTP，

2. Web内容是与一个MIME类型相关的字节序列。

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

   1. 取一个磁盘文件，并将它的内容（静态内容）返回给客户端；
   2. 运行一个可执行文件，并将它的输出（动态内容）返回给客户端。

六、补充知识

1. 硬件单元与各个处理阶段相关联，分为取指、译码、执行、访存、写回、更新PC。
   1. 取指：将程序计数器寄存器作为地址，指令内容读取指令的字节。
   2. 译码：寄存器文件有两个读端口A、B,从这两个端口同时读寄存器值 valA和valB。
   3. 执行：执行阶段会根据指令的类型，将算术/逻辑单元（ALU）用于不同的目的。
   4. 访存：在执行访存操作时，数据内存读出或写入一个内存字
   5. 写回：寄存器文件有两个写端口。端口E用来写ALU计算出来的值，端口M用来写从数据内存中读出来的值。
   6. 更新PC：程序计数器的新值选择自：valP,下一条指令的地址。ValC，调用指令或跳转指令指定的目标地址，valM，从内存读取的返回地址。