《深入理解计算机系统》读书笔记

花了大概一个多月的时间，趁着实习的空闲把这本书看完了，感觉本书对于计算机的整个宏观讲的很不错，但在操作系统方面讲的还不够深入，自己看这本书主要是为了自己以后的校招做准备，弥补下自己在操作系统方面的短板。

1. 外壳是一个命令行解释器，它输出一个提示符，等待你输入一个命令行，然后执行这个命令。如果该命令行的第一个单词不是一个内置的外壳命令，那么外壳就假设这是一个可执行文件的名字，它将加载并运行这个文件。

2. 驱动计算机进步的两大动力：

   • 要计算机做的更多——并发（一个同时具有多个活动的系统）
   • 要计算机做的更快——并行（用并发使系统运行的更快）

3. 同变量类似，指针也有两个方面：

   • 值（表示某个对象的地址）
   • 类型（表示那个位置上存储的对象的类型）

4. 对于一个字长为w位的机器而言，虚拟地址的范围为$0\sim2^w$，程序最多访问$2^w$个字节。

5. 多字节对象都被存储为连续的字节序列，对象的地址为所使用字节的最小地址。

6. Unix外壳创建的每个进程开始时都有三个打开的文件：标准输入（0）、标准输出（1）和标准错误（2）。头文件<unistd.h>定义了常量STDIN_FILENO、STDOUT_FILENO和STDERR_FILENO，它们可用来代替显式的描述值。

7. Unix内核使用三个相关的数据结构来表示打开的文件。描述符表中的表项指向打开文件表中的表项，而打开文件表中的表项又指向v-node表。每个进程都有自己单独的描述符表，所有的进程共享同一个打开文件表和v-node表。

8. 客户端-服务器模型中的基本操作是事务（跟数据库事务完全不一样），它由四步组成：客户端发送请求；服务器处理请求；服务器发送响应；客户端处理响应。

9. 编写高效程序需要做到以下几点：

   • 必须选择一种合适的数据结构和算法。
   • 必须编写出编译器能够有效优化以转换成可执行代码的源代码。
   • 对处理运算量特别大的计算，将一个任务分成多个部分。

10. 在一个使用投机执行的处理器中，处理器会开始执行预测的分支目标处的指令,这样做会避免修改任何实际的寄存器或存储器位置，知道确定了实际的结果。如果预测是正确，那么处理器就会“提交”投机执行的指令的结果，把它们存储到寄存器或存储器中。如果预测是错误的，处理器必须丢弃掉所有投机执行的结果，在正确的位置，重新开始取指令的过程。这样做会引起预测错服除法，因为在产生又有用的结果前，必须重新填充指令流水线。为保证分之预测除法不会阻碍程序的效率，可以使用以下原则：

    • 不要过分关系可预测的分支。

    • 书写使用条件传送的代码，使用“功能式的”代码替代“命令式的”代码。

        #命令式
        if(a[i] > b[i]) {
          int t = a[i];
          a[i] = b[i];
          b[i] = t;
        }
        #功能式
        int min = a[i] < b[i] ? a[i] : b[i];
        int max = a[i] < b[i] ? b[i] : a[i];
        a[i] = min;
        b[i] = max;
      

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

    • 高级设计。为遇到的问题选择适当的算法和数据结构。
    • 基本编码原则。
      • 消除连续的函数调用，在可能时将循环移到循环外。
      • 消除不必要的存储器引用，引入临时变量来保存中间结果。
    • 低级优化。
      • 展开循环，降低开销。
      • 用功能的风格重写条件操作，使得编译采用条件数据传递。

12. Amdahl定律：考虑一个系统，在其中执行某个应用程序需要时间，假设系统的某个部分需要这个时间的百分比为$\alpha$，而我们将它的性能提高到了$k$倍，即这个部分原来$ \sum_{i=0}^n i^2 = \frac{(n^2+n)(2n+1)}{6} $需要时间$\alpha\bulletT_{old}$，而现在需要时间$\alphaT_{old}/k$ ，因此整个执行时间会是：
    $$T_{new}=(1-\alpha)T_{old}+(\alphaT_{old})/k$=T_{old}[(1-\alpha)+\alpha/k]$$
    据此，我们可以计算加速比$S=T_{old}/T_{new}$为：$S=\frac{1}{(1-\alpha)+\alpha/k}$。要想大幅度提高整个系统的速度，我们必须提高整个系统很大一部分的速度。

13. 一个编写良好的计算机程序常常具有良好的局部性，它们倾向于引用邻近于其他最近引用过的数据项的数据项，或者最近引用过的数据项本身，这种倾向性被称为局部性原理，这是一个持久的概念，对硬件和软件系统的设计和性能都有着极大的影响，分为时间局部性和空间局部性。

14. 量化评价程序局部性的原则：

    • 重复引用一个变量的程序有良好的时间局部性。
    • 对于具有步长为k的引用模式的程序，步长越小，空间局部性约好。具有步长为1的引用模式的程序有很好的空间局部性，在存储器中以大步长跳来跳去的程序空间局部性会很差。
    • 对于取指令来说，循环有好的时间和空间局部性。循环体越小，循环迭代次数越多，局部性越好。

15. 高速缓存的写操作：

    • 直写：立即将w的高速缓存块协会到紧接着的低一层中。虽然简单，但缺点是每次写都会引起总线流量。
    • 写回：尽可能的推迟存储器更新，只有当替换算法要驱逐更新过的块时，才把它写到紧接着的低一层中。能显著地减少总线流量，但是增加了复杂性。

16. 基本存储技术包括随机存储器(RAM)、非易失性存储器(ROM，只读存储器)和磁盘。RAM包括静态RAM(SRAM，贵、快，可作CPU芯片上的高速缓存，也可以用作芯片下的高速缓存)和动态RAM(DRAM，便宜、慢，用作主存和图形帧缓冲区)。

之后Unix外壳调用操作系统中的加载器函数，它拷贝可执行文件中的代码和数据到存储器，然后将控制转移到这个程序的开头。
18. 程序是一堆代码和数据，可以作为目标模块存放于磁盘上，或者作为段存在于地址空间中。进程是一个执行中的程序的实例。系统中的每个程序都是运行在某个进程的上下文的。上下文是由程序正确运行所需的状态组成的，包括存放在存储器中的程序的代码和数据，它的栈、通用目的寄存器的内容、程序计数器、环境变量以及打开文件描述符的集合。
19. 进程提供给应用程序的关键抽象：
* 一个独立的逻辑控制流，它提供一个假象，好像我们的程序独占地使用处理器。
* 一个私有的地址空间，它提供一个假象，好像我们的程序的独占地使用存储器系统。
20. 多个流并发地执行的一般现象称为并发，一个进程和其他进程轮流运行的概念称为多任务；
21. 上下文切换：
* 保存当前进程的上下文。
* 回复某个先前被抢占的进程的被保存的上下文。
* 将控制传递给这个新恢复的进程。
22. 一个终止了但还未被回首的进程称为僵死进程。
23. fork是一次调用两次返回：一次是在调用进程（父进程）中，返回子进程的pid；一次是在新创建的子进程中，返回0。因为子进程的pid总是非零的，返回值就提供一个明确的方法来分辨程序是在父进程还是在子进程中执行。
24. 虚拟存储器是硬件异常、硬件地址翻译、主存、磁盘文件和内核软件的完美交互，它为每个进程提供了一个大的、一致的和私有的地址空间。它有三个重要能力：
* 将主存看成是一个存储在磁盘上的地址空间的高速缓存，在主存中只包括活动区域，并根据需要在磁盘和主存见来回传送数据，高效地使用主存。
* 为每个进程提供了一致的地址空间，从而简化了存储器管理。
* 保护每个进程的地址空间不被其他进程破坏。
25. 对于C语言来说，常见的管理和使用虚拟存储器的错误有：
* 间接引用坏指针。
* 读取未初始化的存储器。
* 允许栈缓冲区溢出。
* 假设指针和它们指向的对象大小相同。
* 引用指针而不是它们所指向的对象。
* 误解指针运算。
* 引用不存在的变量，引起内存器泄漏。

注：12条公式错误没解决