计算机底层的秘密摘抄笔记

https://www.bookstack.cn/read/webxiaohua-gitbook/README.md

大部分是摘抄

机器指令需要加载到内存中执行，因此需要记录下内存的起始地址和长度；同时要找到函数的入口地址并写到PC寄存器中，想一想这是不是需要一个数据结构来记录下这些信息：

struct *** {
    void* start_addr;
    int len;
    void* start_point;
};

这个数据结构就叫进程(Process)

进程的缺点在于只有一个入口函数，也就是main函数，因此进程中的机器指令只能被一个CPU执行，main函数的特殊之处无非就在于是CPU执行的第一个函数，除此之外再无特别之处，我们可以把PC寄存器指向main函数，就可以把PC寄存器指向任何一个函数。

当我们把PC寄存器指向非main函数时，线程就诞生了。多个CPU可以在同一个屋檐下(进程占用的内存区域)同时执行属于该进程的多个入口函数，也就是说现在一个进程内可以有多个执行流了。

I/O就是简单的数据Copy，仅此而已。内存与外部设备之间的数据copy就是I/O（Input/Output）

一般情况下I/O数据是要首先copy到操作系统内部，然后操作系统再copy到进程空间中。因此我们可以看到这里其实还有一层经过操作系统的copy，对于性能要求很高的场景其实也是可以绕过操作系统直接进行数据copy的，这也是本文描述的场景，这种绕过操作系统直接进行数据copy的技术被称为Zero-copy，也就零拷贝，高并发、高性能场景下常用的一种技术

实际上所有的I/O设备都被抽象为了文件这个概念，一切皆文件，Everything isFile，磁盘、网络数据、终端，甚至进程间通信工具管道pipe等都被当做文件对待。

在进行I/O时，我们并不知道该文件描述对应的I/O设备是否是可读的、是否是可写的，在外设的不可读或不可写的状态下进行I/O只会导致进程阻塞被暂停运行。

将要监听的文件描述符交给内核，当有可以读写的时候内核通知应用程序，这就是I/O多路复用， I/O multiplexing

所谓I/O多路复用指的是这样一个过程：

我们拿到了一堆文件描述符(不管是网络相关的、还是磁盘文件相关等等，任何文件描述符都可以)
通过调用某个函数告诉内核：“这个函数你先不要返回，你替我监视着这些描述符，当这堆文件描述符中有可以进行I/O读写操作的时候你再返回”
当调用的这个函数返回后我们就能知道哪些文件描述符可以进行I/O操作了。

Linux有三个函数进行I/O多路复用：

select：数量有限<1024，文件描述符需拷贝到内核，不告知哪个文件描述符满足要求
poll：解决了文件描述符不能超过1024个的限制
epoll：共享内存，解决文件描述符需拷贝到内核的问题，记录哪个文件描述符满足了要求

内核设计者创建了一个叫做空闲任务的进程，这个进程就是Windows 下的“系统空闲进程”，在 Linux 下就是第 0号进程。

当其它进程都处于不可运行状态时，调度器就从队列中取出空闲进程运行，显然，空闲进程永远处于就绪状态，且优先级最低。

使用halt指令进行空闲任务

如果程序大量使用malloc申请内存那么该程序注定无法获得高性能。

简单来说，内存池技术一次性获取到大块内存，然后在其之上自己管理内存的申请和释放，这样就绕过了标准库以及操作系统。通过内存池，一次内存的申请再也不用去绕一大圈了。

除此之外，我们可以根据特定的使用模式来进一步优化，比如在服务器端，每次用户请求需要创建的对象可能就那几种，那么这时我们就可以在自己的内存池上提前创建出这些对象，当业务逻辑需要时就从内存池中申请已经创建好的对象，使用完毕后还回内存池。

因此我们可以看到，这种为某些应用场景定制的内存池相比通用的比如malloc内存分配器会有大的优势。

一种线程安全的内存池

线程局部存储，Thread Local Storage，即在每个线程中都有副本，变量指向的值是线程私有的，相互之间不会干扰。将内存池设定为线程局部存储，这样每个线程都只会操作属于自己的内存池，这样就再也不会有锁竞争问题了。

__thread int global_num = 100;

三种内存池设计方案：

提前创建出一堆需要的对象(数据结构)，自己维护好哪些对象(数据结构)可用哪些已被分配；
可以申请任意大小的内存空间，使用过程中只申请不释放，最后一次性释放。这两种内存池天然适用于服务器端编程。
提前申请出一大段内存，然后将这一大段内存切分为大小相同的小内存块。自己来维护这些被切分出来的小内存块哪些是空闲的哪些是已经被分配的。程序申请的最大内存不能超过这里内存块的大小

一块内存属于哪个线程的信息保存在大段内存的最后

线程运行的本质就是函数的执行，那么函数运行时信息就都保存在栈区，每个线程都有一个私有的栈区，因此在栈上分配的局部变量就是线程私有的

剩下的区域就是共享资源了，这包括：

用于动态分配内存的堆区，我们用C/C++中的malloc或者new就是在堆区上申请的内存
全局区，这里存放的就是全局变量
文件，我们知道线程是共享进程打开的文件

代码区和动态链接库，这两个区域是不能被修改的，也就是说这两个区域是只读的，因此多个线程使用是没有问题的

对共享资源的使用不能妨碍到其它线程，抓住了线程私有资源和共享资源这个主要矛盾也就抓住了解决线程安全问题的核心。

即便我们传入的参数是在堆上(heap)用malloc或new出来的，依然可能会有问题，因为堆上的资源也是所有线程可共享的。

假如有两个线程调用func函数时传入的指针(引用)指向了同一个堆上的变量，那么该变量就变成了这两个线程的共享资源，在这种情况下func函数依然不是线程安全的。

函数返回值：

class S {
    public:
    static S& getInstance() {//单例模式
        static S instance;
        return instance;
    }
    private: S() {} // 其它省略
}

和普通函数只有一个返回点不同，协程可以有多个返回点。协程之所以神奇就神奇在当我们从协程返回后还能继续调用该协程，并且是从该协程的上一个返回点后继续执行。

函数只是协程的一种特例

线程也可以被暂停，操作系统保存线程运行状态然后去调度其它线程，此后该线程再次被分配CPU时还可以继续运行，就像没有被暂停过一样。

只不过线程的调度是操作系统实现的，这些对程序员都不可见，而协程是在用户态实现的，对程序员可见。

这就是为什么有的人说可以把协程理解为用户态线程的原因。

当你在协程中写下yield的时候就是想要暂停该协程，当使用next()时就是要再次运行该协程。现在你应该理解为什么说函数只是协程的一种特例了吧，函数其实只是没有挂起点的协程而已。

协程的实现：在堆区（长时间——进程生命周期——存储数据）中申请一段空间，把协程的运行需要的栈帧空间直接开辟在堆区中

栈区存放普通函数的函数栈帧

使用协程理论上我们可以开启无数并发执行流，只要堆区空间足够，同时还没有创建线程的开销，所有协程的调度、切换都发生在用户态，这就是为什么协程也被称作用户态线程的原因所在。

十个内存引发的大坑：返回局部变量地址、错误的理解指针运算、解引用有问题的指针、读取未初始化的内存、内存泄漏、引用已被释放的内存、循环遍历是0开始的、指针大小与指针所指向对象的大小不同、栈缓冲器溢出、操作指针所指对象而非指针本身

精简指令集下，一条机器指令操作的数据必须来存放在寄存器中，不能直接操作内存数据，因此RISC下，数据必须先从内存搬运到寄存器，这就是为什么RISC下会有特定的Load/Store访存指令

而x86下无此限制，一条机器指令操作的数据可以来自于寄存器也可以来自内存，因此这样一条机器指令在执行过程中会首先从内存中读取数据。

CPU执行指令的速度>>将数据从内存读到CPU的速度

CPU执行指令符合28定律，大部分时间都在执行那一少部分指令，这一现象的发现奠定了精简指令集设计的基础。而程序操作的数据也符合类似的定律，只不过不叫28定律，而是叫principle of locality，程序局部性原理。如果我们访问内存中的一个数据A，那么很有可能接下来再次访问到，同时还很有可能访问与数据A相邻的数据B，这分别叫做时间局部性和空间局部性。

将那些经常使用到的数据集中存放到比内存（DRAM）更快的缓存Cache（SRAM）中

可以同步/异步更新缓存：

16.CPU是如何读写内存的？ - 图11

现代计算机系统CPU和内存之间其实是有一个cache的层级结构的。

拥有一堆核心的CPU其实是没什么用的，关键需要有配套的多线程程序才能真正发挥多核的威力，当CPU有多个核心后就会面临多核Cache一致性的问题

CPU读写内存时不但要维护cache和内存的一致性，同样需要维护多核间cache的一致性。

CPU需要处理机器指令以此来指挥整个计算机系统工作。处理一条机器指令大体上可以分为四个步骤：取指、译码、执行、回写，这几个阶段分别由特定的硬件来完成 (注意，真实 CPU 内部可能会将执行一条指令分解为数十个阶段)。

当一条跳转指令还没有完成时后面的指令就需要进入到流水线，因此问题来了：

跳转指令需要依赖自身的执行结果来决定到底要不要跳转，那么在跳转指令没有执行完的情况下 CPU 怎么知道后面哪个分支的指令能进入到流水线呢？

mov ax, bx
jz jumpto ;跳转指令没执行完，是第3行还是第5行代码进入流水线

;下面的代码要进流水线了
add ax, 2
jumpto:
add ax, 3

CPU 会根据特定策略（比如可能会基于执行跳转指令的历史）猜一下 if 语句可能会走哪个分支，如果猜对了流水线照常继续，如果猜错了，流水线上已经执行的后续指令全部作废，因此我们可以看到如果CPU猜错了会有性能损耗。

现代 CPU 将“猜”的这个过程称为分支预测。

比如给一个数组，要得到所有大于某值的元素的和，如果是有序的，CPU分支预测就会大概率成功，省去了指令作废的性能损耗，比无序数组更快。

实际上现代 CPU 的分支预测是很聪明的，对于非核心部分的if 语句分支预测失败带来的性能损失可以忽略不计。

但是对于文章开头提到的代码，程序的大部分时间都用在了 for 循环中，这时你就要注意了，当然前提还是这段代码对时间要求非常严苛，否则你也没必要为了这点性能去优化。

如果给定的数组是无序的，那么上面提到的这段该怎么优化呢？

实际上非常简单，只需要移除 if 语句就可以，该怎么移除呢？

没有 if 语句的话，那么 sum 每次都必须加上一个数，如果arr[i]比256大，那么 sum 加上差值，否则sum 加 0即可，这样就消除了if 判断。

我们计算arr[i] - 256的值，并将其向右移动31位:
(arr[i] - 256) >> 31
这样得到的数不是0 (0x00000000)，就是 -1 (0xffffffff)，然后我们对其取反，再次与上 arr[i] 即可：
sum += ~((arr[i] - 256) >> 31) & arr[i];
也就是说如果arr[i] - 256 大于0 的话那么差值会与上 0xffffffff，其结果就是保持不变，否则会与上0，其结果就是sum会加上0，这样就不需要 if 判断了。

利用位运算，即使数组是无序的也不会有性能问题，代价就是代码可读性会降低很多，这里，我们再一次看到天下没有免费的午餐。

每种类型的CPU都要自己的能力圈，只不过CPU的能力圈有一个特殊的名字，叫做 Instruction Set Architecture ，ISA，也就是指令集，指令集中包含各种各样的指令，是CPU告诉程序员该怎么让自己工作的。

不同的CPU会有不同类型的指令集，指令集的类型除了影响程序员写汇编程序之外还会影响CPU的硬件设计

复杂指令集，Complex Instruction Set Computer，简称CISC，最先诞生的指令集类型。当今普遍存在于桌面PC以及服务器端的x86架构就是基于复杂指令集CISC

在程序员普遍写汇编的时代，大家普遍认为指令集应该更加丰富一些、指令本身功能更强大一些，程序员常用的操作最好都有对应的特定指令，毕竟大家都在直接用汇编语言来写程序，如果指令集很少或者指令本身功能单一，那么程序员用汇编指令写起程序会会非常繁琐

同时，当时珍贵的内存也迫使人们：

一条机器指令尽可能完成更多的任务，这样就能用较少的内存完成较多的工作
机器指令长度不固定，也就是变长机器指令，简单的指令占据更少的空间
机器指令高度编码(encoded)，提高代码密度，节省空间

基于对程序员方便编写汇编语言以及节省代码存储空间的需要，直接促成了复杂指令集的设计，因此我们可以看到复杂指令集是这一时期必然的选择，该指令集就这样诞生了并开始成为主流。

对于指令集中的每一条机器指令都有一小段对应的程序，这些程序存储在CPU中，这些程序都是由更简单的指令组成，这些指令就是所谓的微代码，Microcode。

18.CPU进化论：复杂指令集的诞生 - 图6

就这样CPU的指令集可以添加更多的指令，代价仅仅是再多一些简单的微代码而已

一般我们认为CPU直接执行机器指令，严格来说这是不正确的，对于含有微代码设计的CPU来说，CPU直接执行的并不是机器指令，而是微代码，微代码是CPU以及机器指令的中间层，机器指令相对于微代码来说是“更高级的语言”，机器指令对程序员来说可见，但微代码对程序员来说不可见，程序员无法直接使用微代码来控制CPU。

问题：修复微代码的bug要比修复普通程序的bug困难的多，你无法像普通程序那样来测试、调试微代码，这一切都太复杂了。而且微代码设计非常消耗晶体管，1979年代的Motorola 68000 处理器就采用该设计，其中三分之一的晶体管都用在了微代码上。

精简指令集思想不是说指令集中指令的数量变少，而是说一条指令背后代表的动作更简单了。

精简指令集的另一个特点就是编译器对CPU的控制力更强。在复杂指令集下，CPU会对编译器隐藏机器指令的执行细节，就像微代码一样，编译器对此无能为力。而在精简指令集下CPU内部的操作细节暴露给编译器，编译器可以对其进行控制

精简指令集下的指令只能操作寄存器中的数据，不可以直接操作内存中的数据，在精简指令集下有专用的 load 和 store 两条机器指令来负责内存的读写，其它指令只能操作CPU内部的寄存器，这是和复杂指令集一个很鲜明的区别。

RISC设计的初衷不是让程序员直接使用汇编语言来写程序，而是把这项任务交给编译器，让编译器来生成机器指令。

如果流水线每个阶段的耗时不同，将显著影响流水线的处理能力。假设组装车辆的每个步骤需要10分钟，而其中一个步骤，安装电池，需要20分钟，那么安装电池的前一个和后一个步骤就会有10分钟的空闲，这显然不能充分利用资源。

精简指令集的设计者们当然也明白这个道理，因此他们尝试让每条指令执行的时间都差不多一样，尽可能让流水线更高效的处理机器指令，而这也是为什么在精简指令集中存在Load和Store两条访问内存指令的原因。

由于复杂指令集指令与指令之间差异较大，执行时间参差不齐，没办法很好的以流水线的方式高效处理机器指令(后续我们会看到复杂指令集会改善这一点)。

CPU的核心数和线程个数没有什么必然的关系。

单个核心上可以跑任意多个线程，只要你的内存够就行；计算机系统内也可以有任意多核数，只要你有钱就行。

用户读硬盘，操作系统先将硬盘对应区域拷贝到内存，用户再读内存中内容，相较于操作内存，操作硬盘更复杂、麻烦，而mmap将硬盘中一段地址空间的数据映射到内存了，用户访问这段地址空间时，操作系统会检测对应内存，没有数据就从硬盘中拷贝、填充到内存，用户修改完后操作系统会在背后将修改内容写回磁盘。

标准I/O写时需要将数据从内存的用户态拷贝到内核态、读时要把数据拷贝到用户态。而基于mmap读写磁盘文件不会招致系统调用以及额外的内存copy开销

而mmap需要创建并维护地址空间和文件的映射关系，内核中需要有特定的数据结构来实现这一映射。用mmap将文件映射到进程地址空间后，当我们引用的一段其对应的文件内容还没有真正加载到内存后就会产生中断，这个中断就是缺页，page fault，操作系统检测到这一信号后把相应的文件内容加载到内存，缺页中断也会有性能损耗，同时根据不同内核的实现机制，缺页中断的性能开销也不同。

在处理大文件时，即使该文件大小超过物理内存也可以直接把这个大文件映射到你的进程地址空间中，这就是虚拟内存的巧妙之处了，当物理内存的空闲空间所剩无几时虚拟内存会把你进程地址空间中不常用的部分扔出去，这样你就可以继续在有限的物理内存中处理超大文件了，这个过程对程序员是透明的，程序员根本就意识不要，虚拟内存都给你处理好了。

mmap最好的应用场景：动态链接库。很多进程的运行都依赖于此文件，而且还是有一个特定，那就是这些进程是以只读(read-only)的方式依赖于此文件。

用mmap把该库直接映射到各个进程的地址空间中，尽管每个进程都认为自己地址空间中加载了该库，但实际上该库在内存中只有一份。

21.你管这破玩意叫mmap？ - 图11

计算机处理的任务大体可以分为两类：CPU密集型（多计算）与IO密集型（多交互）

当前流行的互联网技术其实也就是网络应用，更多的属于IO密集型，涉及：软件部分的操作系统与数据库，以及硬件部分的磁盘与网络，这些软硬件显然是在内核态，用户态部分只是冰山一角。当遇到IO后，多线程的魔法就消失了，因为相对于CPU速度来说，瓶颈往往出现在IO设备上，这时候任凭你有再多核再多线程都没有用了。

为什么IO接口要基于数据拷贝：操作系统将应用程序和硬件隔离开来，以便于更好地进行应用程序的开发，然而这导致的问题就是首先把东西交给操作系统，操作系统再转手交给硬件，这就必然涉及到数据拷贝

数据拷贝不只涉及CPU一个模块，还包括内存、总线，现代计算机系统中普遍采用DMA技术，这类技术可以在没有CPU的参与下实现软件和硬件之间的数据拷贝，从而减轻CPU负担，然而用户态和内核态这类软件和软件之间的数据拷贝则无此机制，在这种情况下数据拷贝依然需要CPU的参与。

以从文件中读取数据后将数据通过网卡转发出去为例：

然而内核态并没有对数据进行修改，仅仅是转发，这就催生了零拷贝技术的诞生：直接在内核态从磁盘给到用户态内存

使用零拷贝后，数据拷贝三种情况：

用户态不需要真正的去访问数据，用户态根本不需要知道buf里面装的是什么。在这种情况下无需把数据从内核态拷贝到用户态然后再把数据从用户态拷贝回内核态。数据无需用户态感知，数据拷贝完全发生在内核态。
内核态不要真正的去访问数据，用户态程序可以绕过内核直接和硬件交互，这样就避免了内核的参与，从而减少数据拷贝的可能
如果内核态和用户态不得不进行数据交互，则优化用户态与内核态数据的交互方式

实现零拷贝的设计：

mmap：仅仅将文件内容映射到了进程地址空间中，并没有真正的拷贝到进程地址空间，这节省了一次从内核态到用户态的数据拷贝。同样的，当调用write时数据直接从内核buf拷贝给了socket buf，而不是像read/write方法中把用户态数据拷贝给socket buf

22.彻底理解零拷贝 - 图9

sendfile：这一系统调用的目的是在两个文件描述之间拷贝数据，但值得注意的是，数据拷贝的过程完全是在内核态完成，使用sendfile将节省两次数据拷贝，因为数据无需传输到用户态

内存态的那一次数据拷贝也是没必要的，sendfile加上DMA Gather Copy可以实现零拷贝

DMA Gather Copy：让DMA可以从多个源头DMA Copy收集数据到目标地址

有了这一特性，无需再将内核文件buf中的数据拷贝到socket buf，而是网卡利用DMA Gather Copy机制将消息头以及需要传输的数据等直接组装在一起发送出去。在这一机制的加持下，CPU甚至完全不需要接触到需要传输的数据，而且程序利用sendfile编写的代码也无需任何改动，这进一步提升了程序性能。

高效IO的秘诀其实很简单：尽量少让CPU参与进来。

实际上sendfile的使用场景是比较受限的，大前提是用户态无需看到操作的数据，并且只能从文件描述符往socket中传输数据，而且DMA Gather Copy也需要硬件支持

splice：既然用户态无需对该数据有任何操作，那么为什么不让数据传输直接在内核态中进行呢？借助Linux世界中用于进程间通信的管道实现，pipe

22.彻底理解零拷贝 - 图16

实际上后来sendfile系统调用就是基于splice实现的，为了支持老版本应用才一直保留

内核仅仅是操作系统的一部分，是真正与硬件交互的那部分软件，与硬件交互包括读写硬盘、读写网盘、读写内存以及任何连接到系统中的硬件。

除了与硬件交互外，内核还负责分配资源，比如CPU时间、内存、IO等等。

内核通过虚拟化的方法，将资源以进程的形式分配资源，因为计算机系统内的资源是有限的，我们只有几个CPU核心、几个G的内存，但却要同时运行几百几千个进程

23.操作系统与内核有什么区别？ - 图5

通过系统调用，我们可以像使用普通函数那样向操作系统请求服务，当然，直接使用系统调用是非常繁琐的，因此通常会在这之上提供一层封装。

指针是内存地址的更高一级抽象

间接寻址

int *a;
*a = 3;

mov bx, 0x00
mov [bx], 3

在汇编语言下你必须能意识到这一层间接寻址，因为在汇编语言中是没有变量这个概念的。

指针这个概念首次出现在 PL/I 语言中，当时是为了增加链表处理能力，值得一提的是，Multics操作系统就是 PL/I 语言实现的，这也是第一个用高级语言实现的操作系统

实际上通常用数组来存储堆中的元素，但是我们却可以把数组中元素视为树

35.彻底理解堆 - 图1

虽然我们是在数组中存储的堆元素，但是这里面有一条隐藏的规律，如果你仔细看上图就会发现：

每一个左子树节点的下标是父节点的2倍
每一个右子树节点的下标是父节点的2倍再加1

堆这种数据结构最棒的地方在于我们无需像树一样存储左右子树的信息，而只需要通过下标运算就可以轻松的找到一个节点的左子树节点、右子树节点以及父节点，相对于树这种数据结构来说堆更加节省内存。

int parent(int i){ // 计算给定下标的父节点
    return i/2;
}
int left(int i){ // 计算给定下标的左子树节点
    return 2*i;
}
int right(int i){ // 计算给定下标的右子树节点
    return 2*i+1;
}