《拉钩课程 - 重学操作系统 - 计算机组成原理》

1、芯片是怎么工作的呢？电能供给给芯片，芯片中的一种电子元件晶振（也就是石英晶体）通电后产生震荡，震荡会产生频率稳定的脉冲信号。通常这是一种高频的脉冲信号，每秒可达百万次。然后，我们通过谐振效应发放这个信号，形成方波。再通过电子元件调整这种脉冲的频率，把脉冲信号转换为我们需要的频率，这就形成了驱动芯片工作的时钟信号。这种信号的频率，我们也称作芯片的时钟频率。最后，时钟信号驱动着芯片工作，就像人体的脉搏一样，每一次脉冲到来，都让芯片的状态发生一次变化，用这种方法，最终存储器中的指令被一行行执行。

2、最早在 19 世纪初，德国著名数学家希尔伯特提出：这个世界可以建立一套完善的公理体系，由少数几个公理出发，推导出所有的定理和推论。后来哥德尔提出了不完备性定理，反驳了这种观点：即便在完善的公理体系中仍然可以找到不能被证明也不能被证伪的命题。

3、图灵发现如果一个问题是可计算的，那么它的解决方案就必须可以被具化成一条条的指令，也就是可以使用图灵机处理。因此，不能使用图灵机处理的问题，都是不可计算的问题。

4、不可计算问题，比如 “素数是不是有无穷多个？”尽管我们可以通过有限的步骤计算出下一个素数，但是，我们还是不能回答“素数是不是有无穷多个”这样的问题。因为要回答这样的问题，我们会不停地寻找下一个素数。如果素数是无穷的，那么我们的计算就是无穷无尽的，所以这样的问题不可计算。

5、不可计算问题，比如停机问题。我们无法实现用一个通用程序去判断另一个程序是否会停止。比如你用运行这段程序来检查一个程序是否会停止时，你会发现不能因为这个程序执行了 1 天，就判定它不会停止，也不能因为这个程序执行了 10 年，从而得出它不会停止的结论。

6、可计算问题，其计算开销又分为时间复杂度和空间复杂度。

7、在所有可以计算的问题中，像 O(N^1000) 的问题，虽然现在的计算能力不够，但是相信在遥远的未来，我们会拥有能力解决。这种我们有能力解决的问题，统称为多项式时间（Polynomial time）问题。

8、另外，还有一类问题复杂度本身也是指数形式的问题，比如 O(2^N)的问题。这类型的问题随着规模 N 上升，时间开销的增长速度和人类计算能力增长速度持平甚至更快。因此虽然这类问题可以计算，但是当 N 较大时，因为计算能力不足，最终结果依然无法被解决。我们记为 NP 问题。

9、图灵机在计算机科学方面有两个巨大的贡献：

• 它清楚地定义了计算机能力的边界，也就是可计算理论；
• 它定义了计算机由哪些部分组成，程序又是如何执行的；

10、图灵机的内部构造：

• 图灵机拥有一条无限长的纸带，纸带上是一个格子挨着一个格子，格子中可以写字符，你可以把纸带看作内存，而这些字符可以看作是内存中的数据或者程序；
• 图灵机有一个读写头，读写头可以读取任意格子上的字符，也可以改写任意格子的字符；
• 读写头上面的盒子里是一些精密的零件，包括图灵机的存储、控制单元和运算单元；

11、冯诺依曼模型遵循了图灵机的设计，并提出了用电子元件构造计算机，约定了用二进制进行计算和存储，并且将计算机结构分为以下五个部分：

• 输入设备
• 输出设备
• 内存
• 中央处理器
• 总线

12、冯·诺依曼体系结构的要点是：计算机的数制采用二进制。计算机应该按照程序顺序执行。它采用存储程序方式，指令和数据不加区别，混合存储在同一个存储器中。数据和程序在内存中是没有区别的，它们都是内存中的数据。当 EIP 指针指向哪，CPU 就加载哪段内存中的数据。如果是不正确的指令格式，CPU 就会发生错误中断。

13、冯诺依曼模型中 CPU 负责控制和计算。为了方便计算较大的数值，CPU 每次可以计算多个字节的数据。

• 如果 CPU 每次可以计算 4 个 byte（寄存器），那么我们称作 32 位 CPU；
• 如果 CPU 每次可以计算 8 个 byte（寄存器），那么我们称作 64 位 CPU；

14、64 位的 CPU 和 32 位比较有哪些优势？

• 64 位 CPU 可以执行更大数字的运算，这个优势在普通应用上不明显，但是对于数值计算较多的应用就非常明显；
• 64 位 CPU 可以寻址更大的内存空间，但是也会受到地址总线条数的限制。比如和 64 位 CPU 配套工作的地址总线只有 40 条，那么可以寻址的范围就只有 1T，也就是 2^40。

15、CPU 离内存太远，需要一种离自己近的存储来存储将要被计算的数字，这种存储就是寄存器，寄存器就在 CPU 里，离控制单元和逻辑运算单元非常近，因此速度很快。

16、CPU 和内存以及其他设备之间，也需要通信，因此我们用一种特殊的设备进行控制，就是总线。总线分成 3 种：

• 地址总线。专门用来指定 CPU 将要操作的内存地址；
• 数据总线。用来读写内存中的数据。
• 控制总线。用来发送和接收关键信号，比如后面我们会学到的中断信号，还有设备复位、就绪等信号，都是通过控制总线传输。

17、CPU 的指令周期：

• 首先 CPU 通过 PC 指针读取对应内存地址的指令，我们将这个步骤叫做 Fetch，就是获取的意思。
• CPU 对指令进行解码。我们将这个部分叫做 Decode。
• CPU 执行指令，我们将这个部分叫做 execute。
• CPU 将结果存回寄存器或者将寄存器存入内存，我们将这个步骤叫做 Store。

18、一段代码 a = 11 + 15，它是怎么被 CPU 执行的呢？首先，这是一段高级语言，要被先编译成机器能识别的低级指令，这些指令和数据会被存储到专门的区域；然后 PC 会指向最开始的指令，依次执行：

• 0x200 位置的 load 指令将地址 0x100 中的数据 11 导入寄存器 R0；
• 0x204 位置的 load 指令将地址 0x104 中的数据 15 导入寄存器 R1；
• 0x208 位置的 add 指令将寄存器 R0 和 R1 中的值相加，存入寄存器 R2；
• 0x20c 位置的 store 指令将寄存器 R2 中的值存回数据区域中的 0x1108 位置。

19、CPU 指令从功能上来划分，大概可以分为以下 5 类：

• I/O 类型的指令，比如处理和内存间数据交换的指令 store/load 等；再比如将一个内存地址的数据转移到另一个内存地址的 mov 指令。
• 计算类型的指令，最多只能处理两个寄存器，比如加减乘除、位运算、比较大小等。
• 跳转类型的指令，用处就是修改 PC 指针。比如编程中大家经常会遇到需要条件判断+跳转的逻辑，比如 if-else，swtich-case、函数调用等。
• 信号类型的指令，比如发送中断的指令 trap。
• 闲置 CPU 的指令 nop，一般 CPU 都有这样一条指令，执行后 CPU 会空转一个周期。

20、CPU 是用石英晶体产生的脉冲转化为时钟信号驱动的，每一次时钟信号高低电平的转换就是一个周期，我们称为时钟周期。CPU 的主频，说的就是时钟信号的频率。比如一个 1GHz 的 CPU，说的是时钟信号的频率是 1G。

21、平时你编程做的事情，用机器指令也能做，所以从计算能力上来说它们是等价的，最终这种计算能力又和图灵机是等价的。如果一个语言的能力和图灵机等价，我们就说这个语言是图灵完备的语言。现在市面上的绝大多数语言都是图灵完备的语言，但也有一些不是，比如 HTML、正则表达式和 SQL 等。

22、我们把存储器分成几个级别：

1. 寄存器：访问速度非常快，一般要求在半个 CPU 时钟周期内完成，读写数量通常在几十到几百之间，每个寄存器可以用来存储一定字节（byte）的数据（32 位 CPU 存储 4 个字节；64 位 CPU 存储 8 个字节）。
2. L1-Cache：L1- 缓存在 CPU 中，相比寄存器，虽然它的位置距离 CPU 核心更远，但造价更低。通常 L1-Cache 大小在几十 Kb 到几百 Kb 不等，读写速度在 2~4 个 CPU 时钟周期。
3. L2-Cache：L2- 缓存也在 CPU 中，位置比 L1- 缓存距离 CPU 核心更远。它的大小比 L1-Cache 更大，具体大小要看 CPU 型号，有 2M 的，也有更小或者更大的，速度在 10~20 个 CPU 周期。
4. L3-Cache：L3- 缓存同样在 CPU 中，位置比 L2- 缓存距离 CPU 核心更远。大小通常比 L2-Cache 更大，读写速度在 20~60 个 CPU 周期。L3 缓存大小也是看型号的，比如 i9 CPU 有 512KB L1 Cache；有 2MB L2 Cache； 有16MB L3 Cache。
5. 内存：内存的主要材料是半导体硅，是插在主板上工作的。因为它的位置距离 CPU 有一段距离，所以需要用总线和 CPU 连接。因为内存有了独立的空间，所以体积更大，造价也比上面提到的存储器低得多。现在有的个人电脑上的内存是 16G，但有些服务器的内存可以到几个 T。内存速度大概在 200~300 个 CPU 周期之间。
6. SSD 和硬盘：SSD 也叫固态硬盘，结构和内存类似，但是它的优点在于断电后数据还在。内存、寄存器、缓存断电后数据就消失了。内存的读写速度比 SSD 大概快 10~1000 倍。以前还有一种物理读写的磁盘，我们也叫作硬盘，它的速度比内存慢 100W 倍左右。因为它的速度太慢，现在已经逐渐被 SSD 替代。

23、当 CPU 需要内存中某个数据的时候，如果寄存器中有这个数据，我们可以直接使用；如果寄存器中没有这个数据，我们就要先查询 L1 缓存；L1 中没有，再查询 L2 缓存；L2 中没有再查询 L3 缓存；L3 中没有，再去内存中拿。

24、CPU 会把内存中的指令预读几十条或者上百条到读写速度较快的 L1- 缓存中，因为 L1- 缓存的读写速度只有 2~4 个时钟周期，是可以跟上 CPU 的执行速度的。这里又产生了另一个问题：如果数据和指令都存储在 L1- 缓存中，如果数据缓存覆盖了指令缓存，就会产生非常严重的后果。因此，L1- 缓存通常会分成两个区域，一个是指令区，一个是数据区。（L2/L3 不需要划分指令区和数据区，因为它们不需要协助处理指令预读的事情）

25、据统计，L1 缓存的命中率在 80% 左右，L1/L2/L3 加起来的命中率在 95% 左右。因此，CPU 缓存的设计还是相当合理的。只有 5% 的内存读取会穿透到内存，95% 都能读取到缓存。 这也是为什么程序语言逐渐取消了让程序员操作寄存器的语法，因为缓存保证了很高的命中率，多余的优化意义不大，而且很容易出错。

26、SSD、内存和 L1 Cache 相比速度差多少倍？因为内存比 SSD 快 10~1000 倍，L1 Cache 比内存快 100 倍左右。因此 L1 Cache 比 SSD 快了 1000~100000 倍。所以你有没有发现 SSD 的潜力很大，好的 SSD 已经接近内存了，只不过造价还略高。这个问题告诉我们，不同的存储器之间性能差距很大，构造存储器分级很有意义，分级的目的是要构造缓存体系。

27、假设有一个二维数组，总共有 1M 个条目，如果我们要遍历这个二维数组，应该逐行遍历还是逐列遍历？

【解析】 二维数组本质还是 1 维数组。只不过进行了脚标运算。比如说一个 N 行 M 列的数组，第 y 行第 x 列的坐标是： x + y*M。因此当行坐标增加时，内存空间是跳跃的。列坐标增加时，内存空间是连续的。

当 CPU 遍历二维数组的时候，会先从 CPU 缓存中取数据。关键因素在于现在的 CPU 设计不是每次读取一个内存地址，而是读取每次读取相邻的多个内存地址（内存速度 200～300 CPU 周期，预读提升效率）。所以这相当于机器和人的约定，如果程序员不按照这个约定，就无法利用预读的优势。

另一方面当读取内存地址跳跃较大的时候，会触发内存的页面置换。

28、怎么用非递归算法实现斐波那契数列？

public class Call {

    public static void main(String[] args) {
        int fib = fib(4);
        System.out.println(fib);
        int fib2 = fib2(4);
        System.out.println(fib2);
    }

    static int fib(int n) {
        if (n == 1 || n == 2) {
            return n;
        }
        return fib(n - 1) + fib(n - 2);
    }

    private static int fib2(int n) {
        if (n == 1 || n == 2) {
            return n;
        }
        //初始化数据
        int[] stack = new int[n];
        int point = n - 3;
        stack[n - 1] = 1;
        stack[n - 2] = 2;
        //数组模拟出栈入栈
        while (point >= 0) {
            stack[point] = stack[point + 1] + stack[point + 2];
            point--;
        }
        return stack[0];
    }
}