Linux操作系统面试知识点总结

1. 操作系统基础

（1）操作系统特点：

• 并发性
• 共享性
• 虚拟性
• 异步性

（2）Windows 和 Linux 内核差异。对于内核的架构⼀般有这三种类型：

• 宏内核，包含多个模块，整个内核像⼀个完整的程序；
• 微内核，有⼀个最小版本的内核，⼀些模块和服务则由用户态管理；
• 混合内核，是宏内核和微内核的结合体，内核中抽象出了微内核的概念，也就是内核中会有⼀个小型的内核，其他模块就在这个基础上搭建，整个内核是个完整的程序；
• Linux 的内核设计是采用了宏内核，Window 的内核设计则是采用了混合内核。
• Linux 可执行文件格式叫作 ELF，Windows 可执行文件格式叫作 PE。

（3）键盘敲入字母时，期间发生了什么？

• 当用户输入了键盘字符，键盘控制器就会产生扫描码数据，并将其缓冲在键盘控制器的寄存器中，紧接着键盘控制器通过总线给 CPU 发送中断请求。
• CPU 收到中断请求后，操作系统会保存被中断进程的 CPU 上下文，然后调用键盘的中断处理程序。
• 键盘的中断处理程序是在键盘驱动程序初始化时注册的，其功能就是从键盘控制器的寄存器的缓冲区读取扫描码，再根据扫描码找到用户在键盘输入的字符，如果输入的字符是显示字符，那就会把扫描码翻译成对应显示字符的 ASCII 码，比如用户在键盘输入的是字母 A，是显示字符，于是就会把扫描码翻译成 A 字符的 ASCII 码。
• 得到了显示字符的 ASCII 码后，就会把 ASCII 码放到「读缓冲区队列」，接下来就是要把该字符显示屏幕了，显示设备的驱动程序会定时从「读缓冲区队列」读取数据放到「写缓冲区队列」，最后把「写缓冲区队列」的数据⼀个一个写入到显示设备控制器的寄存器中的数据缓冲区，最后将这些数据显示在屏幕里。
• 显示出结果后，恢复被中断进程的上下文。

2. 用户态 和 内核态

（1）陷入内核态方式：

1. 系统调用：系统调用是用户进程主动发起的操作。发起系统调用，陷入 内核，由操作系统执行系统调用，然后再返回到进程。系统调用实质上就是函数调用，只不过调用的是系统函数，处于内核态而已。 用户在调用系统调用时会向内核传递⼀个系统调用号，然后系统调用处理程序通过此号从系统调用表中找到相应的内核函数执行，最后返回。
2. 异常：异常包括程序运算引起的各种错误如除 0、缓冲区溢出、缺页等。异常是⼀种错误情况，是执行当前指令的结果，可能被错误处理程序修正，也可能直接终止应用程序。异常是同步的。
3. 中断：中断包括 I/O 设备发出的 I/O 中断、各种定时器引起的时钟中断、调试程序中设置的断点等引起的调试中断等。中断由处理器外部的 硬件 产生，不是执行某条指令的结果，也无法预测发生时机。由于中断独立于当前执行的程序，因此中断是异步事件。

（2）信号（高层次中断）：https://www.kirito.info/different-from-ctrl-c-and-kill/。

（3）更多详情见：https://imageslr.com/2020/07/09/trap-interrupt-exception.html。

（4）陷阱、中断、异常的比较：

2.1 执行系统调用时 OS 状态

1. 用户运行库函数（系统调用的封装），函数里面其实是执行的 int 0x80 指令。系统调用先把系统调用号保存在 eax 寄存器中，然后执行 int0x80 指令。
2. int 0x80 指令先进行切换堆栈，找到进程的堆栈，将寄存器值压入到内核栈中。
3. 然后查找相应 中断向量表 的中断处(system_call)并调用。
4. 随后 system_call 从 系统调用表 中找到相应的系统调用进行执行，调用结束后从 system_call 中返回。

2.2 CPU 中断

（1）CPU中断是什么：

1. 计算机处于执行期间，系统内发生了非预期的急需处理事件。
2. CPU暂时中断当前正在执行的程序而转去执行相应的事件处理程序。
3. 处理完毕后返回原来被中断处继续执行。

（2）CPU中断的作用：

1. 可以使CPU和外设同时工作，使系统可以 及时地响应 外部事件。
2. 可以允许多个外设同时工作，大大提高CPU的 利用率。
3. 可以使CPU及时处理各种软硬件故障。

2.3 零拷贝

（1）零拷贝的概念：

• 零拷贝指的是，从⼀个存储区域到另⼀个存储区域的 拷贝任务没有CPU参与。零拷贝通常用于网络文件传输，以减少CPU消耗和内存带宽占用，减少 用户空间（用户可以操作的内存缓存区域）与CPU内核空间（CPU可以操作的内存缓存区域及寄存器）的 拷贝过程，减少 用户上下文（用户状态环境）与CPU内核上下文（CPU内核状态环境）间的 切换，提高系统效率。

（2）传统拷贝方式：发生4次空间切换（1、4、5、7），发生4次copy（3、4、5、6），其中有2次CPU（4、5）参与。

（3）零拷贝方式：零拷贝是通过 sendfile 系统调用 实现的。发生2次空间切换(1、6)，发生3次copy（3、4、5），其中有0次CPU参与。（mmap零拷贝在此基础上增加用户空间与内核空间中内核缓冲区的共享，会多2次空间切换）DMA全称Direct Memory Access（直接内存存取），它允许不同速度的硬件装置来沟通，而不需要依赖于 CPU 的大量中断负载。DMA主要是解决外围设备可以直接访问内存，从中减少CPU参与。DMA方式（优先级高于中断）主要适用于⼀些高速的 I/O设备 。

（4）传输文件的时候，我们要根据文件的大小来使用不同的方式：

• 传输大文件的时候，使用「异步 I/O + 直接 I/O」。因为可能由于 PageCache 被大文件占据，而导致「热点」小文件无法利用到 PageCache，并且大文件的缓存命中率不高，这时就需要使用「异步 IO + 直接 IO 」的方式。
• 传输小文件的时候，则使用「零拷贝技术」；

3. 进程、线程、协程

（1）惊群效应：

• 是指多进程（多线程）在同时阻塞等待同⼀个事件的时候（休眠状态），如果等待的这个事件发生，那么他就会唤醒等待的所有进程（或者线程），但是最终却只能有⼀个进程（线程）获得这个事件的“控制权”，对该事件进行处理，而其他进程（线程）只能重新进入休眠状态，这种现象和性能浪费就叫做惊群效应。

（2）PCB 存储信息（进程的详细介绍见博客《Linux进程概念》）：

• 进程id。系统中每个进程有唯⼀的id，非负整数。
• 进程的状态。有就绪，运行，挂起，停止等状态。
• 进程切换时需要保存和恢复的⼀些CPU寄存器。
• 描述虚拟地址空间的信息。
• 描述控制终端的信息。
• 当前工作目录。
• umask掩码。
• 文件描述符表，包含很多指向结构体的指针。
• 和信号相关的信息。
• 用户id和组id。
• 会话（Session）和进程组。
• 进程可以使用的资源上限（Resource Limit）。

3.1 进程与线程的区别

（1）区别如下：

（2）一个进程最多可以创建多少个线程？

• 进程的虚拟内存空间上限，因为创建⼀个线程，操作系统需要为其分配⼀个栈空间，如果线程数量越多，所需的栈空间就要越大，那么虚拟内存就会占用的越多。
• 系统参数限制，虽然 Linux 并没有内核参数来控制单个进程创建的最大线程个数，但是有系统级别的参数来控制整个系统的最大线程个数。

3.2 线程的实现方式

（1）在引入线程的操作系统中，进程是资源分配的基本单位，线程是独立调度的基本单位。线程也像进程⼀样有多个状态：运行、就绪、阻塞… 从 Linux 内核的角度来看，线程和进程并没有被区别对待。无论线程还是进程，都是用 task_struct 结构表示的。线程的信息介绍见博客《多线程》。线程分为以下两种实现方式：

（2）用户级线程实现：

• 用户线程多见于⼀些历史悠久的操作系统，例如Unix操作系统。有关线程管理的所有工作都由应用程序完成，内核意识不到多线程的存在。用户级线程仅存在于用户空间中，此类线程的创建、撤销、线程之间的同步与通信功能，都无法利用系统调用来实现。
• 应用程序需要通过使用线程库来控制线程。 通常，应用程序从单线程起始，在该线程中开始运行，在其运行的任何时刻，可以通过调用线程库中的派生创建⼀个在相同进程中运行的新线程。由于线程在进程内切换的规则远比进程调度和切换的规则简单，不需要进行用户态/核心态切换，所以切换速度快。因为用户级线程驻留在用户空间，且管理和控制它们的线程也在用户空间，每个线程并不具有自身的线程上下文，所以它们对于操作系统是不可见的，这也就是它无法被调度到处理器内核的原因。

（3）用户线程的优点：

• 可以在不支持线程的操作系统中实现。
• 创建和销毁线程、线程切换代价等线程管理的代价比内核线程少, 因为保存线程状态的过程和调用程序都只是本进程空间的操作。
• 允许每个进程定制自己的调度算法，线程管理比较灵活。
• 线程能够利用的表空间和堆栈空间比内核级线程多。
• 不需要trap，不需要上下文切换（context switch），也不需要对内存高速缓存进行刷新，使得线程调用非常快捷。
• 线程的调度不需要内核直接参与，控制简单。

（4）用户线程的缺点：

• 如果线程发生I/O等阻塞从而引起系统调用时，由于内核不知道有多线程的存在，会阻塞整个进程进而阻塞所有线程, 因此同⼀进程中只能同时有一个线程在运行。
• ⼀个单独的进程内部，没有时钟中断，所以不可能用轮转调度的方式调度线程。
• 资源调度按照进程进行，多个处理机下，同⼀个进程中的线程只能在同⼀个处理机下分时复用，因此对于多线程并不能被多核系统加速。

（5）内核级线程实现：

• 内核线程建立和销毁都是在内核的支持下运行，由操作系统负责管理，通过系统调用完成的。线程管理的所有工作由内核完成，应用程序没有进行线程管理的代码，只有⼀个到内核级线程的编程接口。内核为进程及其内部的每个线程维护上下文信息，调度也是在内核基于线程架构的基础上完成。
• 内核线程驻留在内核空间，它们是内核对象。操作系统调度器管理、调度并分派这些线程。运行时库为每个用户级线程请求⼀个内核级线程，将用户进程映射或绑定到上⾯。用户线程在其生命期内都会绑定到该内核线程。⼀旦用户线程终止，两个线程都将离开系统。这被称作”⼀对⼀”线程映射。内核空间内为每⼀个内核支持线程设置了⼀个线程控制块（TCB），内核根据该控制块，感知线程的存在，并进行控制。

（6）内核线程的特点：

• 当某个线程希望创建⼀个新线程或撤销⼀个已有线程时，它进行⼀个系统调用。
• 多处理器系统中，内核能够并行执行同⼀进程内的多个线程。
• 如果进程中的⼀个线程被阻塞，能够切换同⼀进程内的其他线程继续执行（用户级线程不具备）。
• 所有能够阻塞线程的调用都以系统调用的形式实现，代价较大。

（7）用户级线程和内核级线程的区别：

• 内核级线程是OS内核可感知的，而用户级线程是OS内核不可感知的。
• 用户级线程的创建、撤消和调度不需要OS内核的支持；而内核级线程创建、撤消和调度都需OS内核提供支持，而且与进程的创建、撤消和调度大体是相同的。
• 用户级线程执行系统调用指令时将导致其所属进程被中断，而内核级线程执行系统调用指令时，只导致该线程被中断。
• 在只有用户级线程的系统内，CPU调度还是以进程为单位，处于运行状态的进程中的多个线程，由用户程序控制线程的轮换运行；在有内核级线程的系统内，CPU调度则以线程为单位，由OS的线程调度程序负责线程的调度。
• 用户级线程的程序实体是运行在用户态下的程序，而内核级线程的程序实体则是可以运行在任何状态下的程序。

3.3 线程安全

（1）线程安全：

• 如果代码所在的进程中有多个线程在同时运行，而这些线程可能会同时运行这段代码。如果每次运行结果和单线程运行的结果是⼀样的，而且其他的变量值也和预期的是⼀样的，就是线程安全的。线程安全问题都是由 全局变量 和 静态变量 引起的

（2）实现线程安全的方式：

1. 加锁。如标准库中的 mutex。
2. 原子操作 atomic。在多线程并发执行时，原子操作是不会被线程打断的执行片段。

3.4 线程的同步方式

（1）线程同步 是指多线程通过特定的设置来控制线程之间的执行顺序。详细的线程同步见博客《多线程》的第7小节。主要有以下四种方式：

1. 临界区：通过多线程的串行化来控制对公共资源的访问，速度快。在任意⼀个时刻只允许⼀个线程对共享资源进行访问。
2. 互斥对象：只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有⼀个，所以能保证公共资源不会被多个线程同时访问。
3. 信号量：它允许多个线程在同⼀时刻访问同⼀资源，但是需要限制在同⼀时刻访问此资源的最大线程数目。
4. 事件对象：利用通知的方式来保持线程的同步，还可以方便实现对多个线程的优先级比较操作。

3.5 进程状态

（1）进程的状态转换如下图：

（2）“挂起”是指将暂不执行的进程换出到外存，节省内存空间。“挂起”和“阻塞”都是进程暂停执行的状态，但是这是两个维度的概念：

• 阻塞表示进程正在等待⼀个事件的发生，阻塞状态下收到信号会切换为就绪状态。
• 挂起表示进程被换出到外存，挂起状态下被激活时会被载入到内存，切换为非挂起状态

（3）综上所属，挂起状态的进程按照是否阻塞可以分为：

• 挂起就绪状态：进程在外存中，但是只要被载入内存就可以执行。
• 挂起阻塞状态：进程在外存中并等待⼀个事件，即使被载入内存也无法运行。

（4）Linux 将进程的 阻塞状态 进一步细分为：暂停、浅睡眠、深睡眠。

• 其中，若不需要等待资源，则切换为“暂停”；若需要等待资源，切换为“睡眠”；如果睡眠状态能被信号唤醒，则是“浅睡眠”，否则是“深睡眠”。

3.6 进程/CPU调度算法

（1）进程的上下文切换不仅包含了虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈、寄存器等内核空间的资源。调度算法如下：

1. 先来先服务（First Come First Serverd，FCFS）：优点是易于理解，便于实现，只需⼀个就绪队列。缺点是对短作业不公平；对 I/O 密集型进程不利，长时间等待设备；响应时间不确定
2. 最短作业优先（Shortest Job First，SJF）：优点是提高平均周转时间。缺点是对长作业不公平；可能导致饥饿问题
3. 最高响应比优先算法（Highest Response Ratio Next，HRRN）：作业运行所需时间越小、作业等待时间越长，响应比越大。优点：同时考虑了等待时间和执行时间，既优先考虑短作业，也防止长作业无限等待的饥饿
4. 时间片轮转（Round Robin，RR）：优点：没有饥饿问题。问题：若时间片小，进程切换频繁，吞吐量低；若时间片长，则响应时间过长，实时性得不到保证
5. 最高优先级调度
6. 多级反馈队列（Multilevel Feedback Queue，MFQ）：优先级高的队列先执行；优先级越高，时间片越短；如果⼀个进程在当前队列规定的时间片内无法执行完毕，则移动到下⼀个队列的队尾。缺点：也有可能出现饥饿问题，比如不断有新的更高优先级的进程加入。可在⼀定时间后全部提升到优先级高的队列解决。
7. 最早截止时间优先算法：先把截止时间早的任务给完成，否则这个任务如果在截止时间后才完成，就没有意义了。
8. 最短剩余时间优先（Shortest Remaining Time Next，SRTN）：最短作业优先的抢占式版本，如果新作业比正在执行的作业剩余时间短，则它优先执行。缺点是对长作业不公平；可能导致饥饿问题。
9. 彩票法：向进程提供各种系统资源的彩票。调度时随机抽取彩票，拥有该彩票的进程得到资源。可给重要的进程更多的彩票；协作进程可以交换彩票。
10. 公平分享法：为每用户分配⼀定比例的 CPU 时间，而不是按照进程。各用户之间按照比例挑选进程。

3.7 进程的分类

（1）僵尸进程（详细的介绍见博客《Linux进程概念》第4小节）：

• 概念：僵尸进程是指终止但还未被回收的进程。如果子进程退出，而父进程并没有调用 wait() 或waitpid() 来回收，那么就会产生僵进程。僵尸进程是⼀个已经死亡的进程，但是其进程描述符仍然保存在系统的进程表中。
• 危害：占用进程号，系统所能使用的进程号是有限的，可能导致不能产⽣新的进程；占用⼀定的内存。

（2）如何避免产生僵尸进程：

1. 父进程调用 wait 或者 waitpid 等待子进程结束
2. 子进程结束时，内核会发送 SIGCHLD 信号给父进程。父进程可以注册⼀个信号处理函数，在该函数中调用 waitpid，等待所有结束的子进程；也可以用 signal(SIGCLD, SIG_IGN) 忽略 SIGCHLD信号，那么子进程结束后，内核会进行回收。
3. 杀死父进程，僵尸进程就会变成孤儿进程，由 Init 进程接管并处理。

（3）孤儿进程：

• 如果某个进程的父进程先结束了，那么它的子进程会成为孤儿进程。每个进程结束的时候，系统都会扫描是否存在子进程，如果有则用 Init 进程（pid = 1）接管，并由 Init 进程调用 wait 等待其结束，完成状态收集工作。孤儿进程不会对系统造成危害。

（4）守护进程：

• 守护进程是⼀种在后台执行的电脑程序。此类程序会被以进程的形式初始化。

（5）创建守护进程：

1. 在父进程中执行 fork 并退出父进程，子进程继续。
2. 在子进程中调用 setsid 函数创建新的会话。由于会话过程对控制终端的独占性，进程同时与控制终端脱离。
3. 在子进程中调用 chdir 函数，让根目录 “/” 成为子进程的工作目录。进程活动时，其工作目录所在的文件系统不能卸下，⼀般需要将工作目录改变到根目录。
4. 在子进程中关闭任何不需要的文件描述符。进程从创建它的父进程那里继承了打开的文件描述符。如不关闭，将会浪费系统资源，造成进程所在的文件系统无法卸下以及引起无法预料的错误。
5. 在子进程中调用 umask 函数，设置进程的 umask 为0。进程从创建它的父进程那里继承了文件创建掩模。它可能修改守护进程所创建的文件的存取位。为防止这⼀点，将文件创建掩模清除。

3.8 进程间的通信方式

3.8.1 信号 Signal

（1）信号的概念（详细的信号介绍见博客《进程间的信号》）：

• 信号是系统为响应某些条件而产生的⼀个事件，接收到该信号的进程可以采取事先自定义的行为。这是⼀种“订阅-发布”的模式。

（2）信号来源：

1. 硬件来源。如按下 CTRL+C、除 0、非法内存访问等等。
2. 软件来源。如 Kill 命令等等。

（3）进程如何发送信号：

1. 使用系统调用将信号放到目标进程的 信号队列 中。
2. 如果目标进程处于未执行状态，则该信号就由内核保存起来，直到该进程恢复执行并传递给它为止；如果⼀个信号被进程设置为阻塞，则该信号的传递被延迟，直到其阻塞被取消时才被传递给进程

（4）进程如何接收信号：

1. 把接收到的信息放入信号队列中；
2. 执行中的进程会在特定时刻（如从系统空间返回到⽤户空间之前）检查并处理自己的信号队列。

3.8.2 信号量 Semaphore

（1）信号量的概念（详细的介绍见博客《进程间通信》第9小节）：

• 信号量是⼀种特殊的变量，对它的操作都是原子的（屏蔽中断），有两种操作：V（signal()）和 P（wait()）。V 操作会增加信号量 S 的数值，P 操作会减少它。（信号量 S 的值相当于记录资源的个数）
• 底层实现：通过硬件提供的原子指令，如 Test And Set（上锁并检查）、Compare And Swap（比较并交换，仅当预期值与内存值相等时才修改，否则不操作） 等。
• 种类：整型信号量（通过PV操作访问）、记录型信号量（让权等待策略）、AND型信号量（资源⼀次性分配）、信号量集（⼀次申请多个资源，每次分配前都要测试资源数目，根据可分配下限值决定是否分配）

3.8.3 管道 Pipe

（1）管道的概念（详细的介绍见博客《进程间通信》第2小节）：

• 管道是⼀种半双工的通信方式，数据只能单向流动。如果想实现双向通信，那么需要建立两个管道。管道适合于传输大量信息，传输的内容是没有格式的字节流。
• 创建管道：通过 pipe() 系统调用来创建并打开⼀个管道，当最后⼀个使用它的进程关闭对他的引用时，pipe 将自动撤销。通过 pipe() 创建的是匿名管道，只能用于具有亲缘关系的进程之间（父子进程或兄弟进程）。
• 管道的实现：管道是⼀个由内核管理的缓冲区，缓冲区被设计为环形的数据结构，以便管道可被循环利用。
• 管道的同步：管道是⼀个具有特定大小的缓冲区，操作系统会通过加锁保证读写进程的同步，下游进程或者上游进程需要等另一方释放锁后才能操作管道。当管道为空时，下游进程读阻塞；当管道满时，上游进程写阻塞。

3.8.4 命名管道 FIFO

（1）命名管道的概念（详细的介绍见博客《进程间通信》第3小节）：

• 命名管道可用于任何有访问权的进程通过文件名将其打开和进行读写。Pipe 和 FIFO 除了建立、打开、删除的方式不同外，二者几乎⼀模⼀样。
• FIFO的实现：通过 mkfifo() 函数建立命名管道。命名管道实质上也是通过内核缓冲区来实现数据传输。建立命名管道时，会在磁盘中创建⼀个索引节点，命名管道的名字就相当于索引节点的文件名。索引节点设置了进程的访问权限，有访问权限的进程，可以通过磁盘的索引节点来读写这块缓冲区。当不
  再被任何进程使⽤时，命名管道在内存中释放，但磁盘节点仍然存在。

3.8.5 消息队列 Message Queue

（1）消息队列的概念（详细的介绍见博客《进程间通信》第8小节）：

• 消息队列是消息组成的链表，保存在内核中。消息队列中的消息是⼀个具有特定格式的数据块。操作系统中可以存在多个消息队列，每个消息队列有唯⼀的 key 进行标识。
• 优缺点：和信号相比，消息队列能够传递更多的信息。与管道相比，消息队列提供了有格式的数据。消息队列允许⼀个或多个进程向它写入与读取消息，消息队列是异步的。
• 实现：操作系统提供创建消息队列、取消息、发消息等系统调用。操作系统负责读写同步：若消息队列已满，则写消息进程排队等待；若取消息进程没有找到需要的消息，则在消息队列中轮询。

3.8.6 共享内存 Shared Memory

（1）共享内存的概念（详细的介绍见博客《进程间通信》第4、5小节）：

• 共享内存允许多个进程映射同⼀段物理空间，然后像访问普通内存⼀样访问它，并交换数据。

（2）优点：

• 访问共享内存区域和访问进程独有的内存区域⼀样快，原因是不需要系统调用，不涉及用户态到内核态的转换，也不需要对数据过多复制。
• 比如管道和消息队列，需要在内核和用户空间进行四次的数据拷贝（读输入文件、写到管道；读管道、写到输出文件），而共享内存则只拷贝两次：一次从输入文件到共享内存区，另⼀次从共享内存到输出文件。
• 消息队列的实现需要系统调用，也就经常需要用户态和内核态互相转换；而共享内存只在建立时需要系统调用，之后所有访问都可作为常规内存访问，无需借助内核。

（3）缺点：

• 存在并发问题，有可能出现多个进程修改同⼀块内存，因此共享内存⼀般与信号量结合使用。

（4）实现：

• mmap() 不是专门用来共享内存的，mmap() 系统调用的主要作用是将普通文件映射到进程的地址空间，然后可以像访问普通内存⼀样对⽂件进⾏访问，不必再调用 read()，write() 等操作。因此多个进程可以通过 mmap() 映射同⼀个普通文件，来实现共享内存。

3.8.7 套接字 Socket

（1）套接字的概念：

• 不同的计算机的进程之间通过 socket 通信，也可用于同⼀台计算机的不同进程。需要通信的进程之间首先要各自创建⼀个 socket，内容包括主机地址与端口号。进程通过 socket 把消息发送到网络层中，网络层通过主机地址将其发到目的主机，目的主机通过端口号发给对应进程。

（2）实现：操作系统提供创建 socket、发送、接收的系统调用，为每个 socket 设置发送缓冲区、接收缓冲区。

3.9 协程

• 协程是⼀个用户态的线程，用户在堆上模拟出协程的栈空间。当需要进行协程上下文切换的时候，主线程只需要交换栈空间和恢复协程的⼀些相关的寄存器的状态，就可以实现上下文切换。没有了从用户态转换到内核态的切换成本，协程的执行也就更加高效。和传统的线程不同的是：线程是抢占式执行，当发生系统调用或者中断的时候，交由OS调度执行；而协程是通过 yield 主动让出cpu所有权，切换到其他协程执行。

4. 锁

4.1 锁的类型

（1）以下是各种锁的用途（锁详细的介绍见博客《多线程》第4小节）：

• 互斥锁 加锁失败时，会用「线程切换」来应对，当加锁失败的线程再次加锁成功后的这⼀过程，会有两次线程上下文切换的成本，性能损耗比较大。
• 自旋锁 加锁失败时，并不会主动产生线程切换，而是⼀直忙等待，直到获取到锁。如果被锁住的代码执行时间很短，那这个忙等待的时间相对应也很短。
• 读写锁 允许多个读线程同时持有读锁，提高了读的并发性。根据偏袒读方还是写方，可以分为读优先锁和写优先锁，读优先锁并发性很强，但是写线程会被饿死，而写优先锁会优先服务写线程，读线程也可能会被饿死，那为了避免饥饿的问题，于是就有了公平读写锁，它是用队列把请求锁的线程排队，并保证先入先出的原则来对线程加锁，这样便保证了某种线程不会被饿死，通用性也更好。互斥锁和自旋锁都是最基本的锁，读写锁可以根据场景来选择这两种锁中的⼀个进行实现。
• 互斥锁、自旋锁、读写锁都属于 悲观锁，悲观锁认为并发访问共享资源时，冲突概率可能非常高，所以在访问共享资源前，都需要先加锁。
• 如果并发访问共享资源时，冲突概率非常低的话，就可以使用 乐观锁，它的工作方式是，在访问共享资源时，不用先加锁，修改完共享资源后，再验证这段时间内有没有发生冲突，如果没有其他线程修改资源，那么操作完成，如果发现有其他线程已经修改过这个资源，就放弃本次操作。但是一旦冲突概率上升，就不适合使用乐观锁，因为它解决冲突的重试成本非常高。

（2）CAS 不是乐观锁吗，为什么基于 CAS 实现的自旋锁是悲观锁？

• CAS 是乐观锁，但是基于 CAS 的自旋锁加了while 或者睡眠 CPU 的操作而产生自旋的效果，加锁失败会忙等待直到拿到锁，即需要先拿到锁才能修改数据，所以算悲观锁。

4.2 死锁

（1）死锁的概念：

• 死锁是指多个进程循环等待其他进程占有的资源而无限期地僵持下去的局面。当两个或两个以上的进程同时对多个互斥资源请求使用时，有可能导致死锁。

（2）造成死锁的必要条件：

1. 互斥条件。即某个资源在⼀段时间内只能由⼀个进程占有，不能同时被两个或两个以上的进程占有。
2. 不可抢占条件。进程所获得的资源在未使用完毕之前，资源申请者不能强行地从资源占有者手中夺取资源，而只能由该资源占有者进程自行释放。
3. 占有且申请条件。进程至少已占有⼀个资源，但又申请新资源；由于该资源已被另外进程占有，此时该进程阻塞；但是它在等待新资源的同时，仍继续占用已有的资源。
4. 循环等待条件。存在⼀个进程等待序列{P1, P2, P3…, Pn}，其中P1等待P2所占有的某⼀资源，P2等待P3占有的某⼀资源…，⽽Pn等待P1所占有的某⼀资源，形成⼀个进程循环等待环。

（3）死锁预防：死锁预防是保证系统不进入死锁状态的⼀种策略，基本思想是要求进程申请资源时遵循某种协议，从而打破产生死锁的必要条件中的⼀个或几个，保证系统不进入死锁状态。

1. 打破互斥条件。即允许进程同时访问某些资源。
2. 打破不可抢占条件。即允许进程强行从占有者那里夺取某些资源，就是说当⼀个进程已经占有了某些资源，而又申请新的资源，但又不能被立即满足时，它必须释放所占有的全部资源，以后再重新申请。它所释放的资源可以分配给其他进程，这就相当于该进程占有的资源被隐蔽地抢占了。该方法实现起来困难，会降低系统性能。
3. 打破占有且申请条件。可以实行资源预先分配策略，即进程在运行前⼀次性地向系统申请它所需要的全部资源，如果某个进程所需的全部资源得不到满足，则不分配资源，此进程暂不运行。只有当系统能够满足当前进程的全部资源需求时，才⼀次性地将所申请的资源全部分配给该进程。
4. 打破循环等待条件。实行资源有序分配策略，即把资源事先编号，按号分配。所有进程对资源的请求必须严格按资源序号递增的顺序提出，进程占用了小号资源，才能申请大号资源，就不会产生环路。

（4）在数据库层面，有两种设置参数策略通过「打破循环等待条件」来解除死锁状态：

• 设置事务等待锁的超时时间。当⼀个事务的等待时间超过该值后，就对这个事务进行回滚，于是锁就释放了。
• 开启主动死锁检测。主动死锁检测在发现死锁后，主动回滚死锁链条中的某一个事务，让其他事务得以继续执行。

（5）死锁避免：银行家算法。基本思想是分配资源之前，判断系统是否是安全的，若是则分配。即已知当前所有进程对各个资源的需求，以及现在已占用的资源，还有系统可用资源Available。

1. 求出每个进程当前还需要多少资源Need。
2. 选取 Need <= Availadble 的某进程分配，若无则等待更多资源释放到系统。
3. 执行安全性检测算法，若安全则进行分配，否则到第2步找其他进程。
4. 回收原进程已有资源和已分配的资源，找其他进程分配。

5. 虚拟内存

（1）内存管理理解文章：https://mp.weixin.qq.com/s/lx0vX-4wlQWxxfj017T9HA。

（2）直接使用物理内存会产生一些问题：

1. 内存空间利用率的问题：各个进程对内存的使用会导致内存碎片化，当要用 malloc 分配⼀块很⼤的内存空间时，可能会出现虽然有足够多的空闲物理内存，却没有足够大的连续空闲内存这种情况。
2. 读写内存的安全性问题：物理内存本身是不限制访问的，任何地址都可以读写。
3. 进程间的安全问题：各个进程之间没有独立的地址空间，⼀个进程由于执行错误指令或是恶意代码都可以直接修改其它进程的数据，甚至修改内核地址空间的数据，这是操作系统所不愿看到的。
4. 内存读写的效率问题：当多个进程同时运行，需要分配给进程的内存总和大于实际可用的物理内存时，需要将其他程序暂时拷贝到硬盘当中，然后将新的程序装⼊内存运行。由于大量的数据频繁装入装出，内存的使用效率会非常低

（3）虚拟内存：

• 虚拟内存是计算机系统内存管理的⼀种技术。它使得应用程序认为它拥有连续可用的内存，而实际上它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。

（4）虚拟内存有什么作用？

• 解决了多进程之间地址冲突的问题。由于每个进程都有自己的页表，进程也没有办法访问其他进程的页表，所以每个进程的虚拟内存空间就是相互独立的。
• 在内存访问方面，操作系统提供了更好的安全性。页表里的页表项中除了物理地址之外，还有⼀些标记属性，比如控制⼀个页的读写权限，标记该页是否存在等。

5.1 虚拟地址空间

（1）对于一个单一进程的概念，这个进程看到的将是地址从0开始的整个内存空间。虚拟存储器是⼀个抽象概念，它为每⼀个进程提供了⼀个假象，好像每个进程都在独占主存，每个进程看到的存储器是⼀致的，称为虚拟地址空间。在 Linux 操作系统中，虚拟地址空间的内部又被分为内核空间和用户空间两部分，不同位数的系统，地址空间的范围也不同。比如最常见的 32 位和 64 位系统，如下所示。虽然每个进程都各自有独立的虚拟内存，但是每个虚拟内存中的内核地址，其实关联的都是相同的物理内存。这样，进程切换到内核态后，就可以很方便地访问内核空间内存。详细的介绍见博客《Linux进程概念》的第7小节

（2）用户空间内存，从低到高分别是 6 种不同的内存段：

• 程序文件段（.text），包括⼆进制可执行代码；
• 已初始化数据段（.data），包括静态常量；
• 未初始化数据段（.bss），包括未初始化的静态变量；
• 堆段，包括动态分配的内存，从低地址开始向上增长；
• 文件映射段，包括动态库、共享内存等，从低地址开始向上增长；
• 栈段，包括局部变量和函数调用的上下文等。栈的大小是固定的，⼀般是 8 MB。当然系统也提供了参数，以便我们自定义大小；

5.2 虚拟内存实现思路

（1）具体实现如下：

1. 在系统中为每个程序定义⼀个虚拟地址空间，虚拟地址空间中的地址都是连续的。
2. 虚拟地址空间被分割成多个块，每块称为⼀个页或者页面。
3. 物理内存被分成和页面大小相同的多个区域，称作页框。
4. 程序加载时，可将任意⼀个页面放入内存中的任意⼀个页框。
5. CPU 的硬件负责将虚拟地址映射到物理内存中的地址（页面 -> 页框）。
6. 程序的整个地址空间无需全部载入物理内存，还有部分暂时存储在外存上，需要时再换入内存。
7. 如果程序引用到⼀部分不在虚拟地址时，会发生缺页中断，由操作系统负责将缺失的页面加载入页框中，并重新执行失败的指令。

（2）内存管理单元（MMU）：将CPU中 负责地址转换 的部分统称为内存管理单元。利用地址转换，操作系统就可以控制进程的所有内存访问，确保访问在地址空间的界限内。这个技术的关键是硬件支持，硬件可以快速地将内存访问操作中的虚拟地址转换为物理地址。对于⼀个页式内存地址转换，有三个步骤：

• 把虚拟内存地址，切分成页号和偏移量；
• 根据页号，从页表里面，查询对应的物理页号；
• 直接拿物理页号，加上前面的偏移量，就得到了物理内存地址。

（3）TLB 的原理：

• 现代操作系统中，页表的个数是很多的，而每次执行语句时都需要先查找页表，将虚拟地址转换为物理内存地址。这部分切换的时间开销是很大的。因此，解决方案是为计算机设置⼀个转换检测缓冲区（TLB，translation-lookaside buffer），是 MMU（内存管理单元）的⼀部分。它提供⼀个缓冲区，记录虚拟页面号到物理页框号的映射，这样可以在 O(1) 的时间里直接将虚拟页面映射到物理页框，不需要访问页表，从而节省时间。

（4）工作流程：如果页⾯号在 TLB 中，得到页框号，访问内存；否则，从内存中的页表中得到页框号，将其存入 TLB，访问内存。

5.3 内存管理方法

（1）段式内存管理：

• 按照逻辑意义将程序分成若干个段，每个段独里载入到内存的不同区间中，通过段表对物理地址进行映射。
  • 优点：按照逻辑关系划分，能产生连续的内存空间。
  • 缺点：每个段必须连续、全部加载到内存中，会产生内存碎片；连续空间不足，与硬盘交互导致内存交换的效率低的问题。

（2）页式内存管理：

• 页式管理把内存空间按页的大小划分成若干页面，然后把页式虚拟地址与内存地址建立⼀⼀对应的页表。而当进程访问的虚拟地址在页表中查不到时，系统会产生一个缺页异常，进入系统内核空间分配物理内存、更新进程页表，最后再返回用户空间，恢复进程的运行。
  • 优点：不存在外部碎片，只在每个进程的最后⼀个页中存在内部碎片。
  • 缺点：程序全部装入内存，要求有相应的硬件支持。例如地址转换模块缺页中断的产⽣和选择淘汰页面等都要求有相应的硬件⽀持。这增加了机器成本和系统开销。

（3）段页式内存管理：

• 把分段和分页两种方式结合，先把程序按照逻辑意义分成段，然后每个段再分成固定大小的页。这样，地址结构就由段号、段内页号和页内位移三部分组成。
• Linux 系统主要采用了分页管理，但是由于 Intel 处理器的发展史，Linux 系统无法避免分段管理。于是 Linux 就把所有段的基地址设为 0，也就意味着所有程序的地址空间都是线性地址空间（虚拟地址），相当于屏蔽了 CPU 逻辑地址的概念，所以段只被用于访问控制和内存保护。

5.4 页面放置算法

（1）空闲链表与内存池的文章：https://zhuanlan.zhihu.com/p/73468738。

（2）最佳适应算法：检查所有空闲分区，选择和新进程申请内存大小最接近的空闲分区。

• 优点：该算法保留大的空闲区。
• 缺点：检查所有空闲分区需要时间。外部碎片多：会留下许多难以利用的，很小的空闲分区，称为外部碎片。可以采用内存紧凑的方法，将被使用的分区都移动到⼀起，减少外部碎片。但是移动内存中的代码和数据也需要很多时间

（3）最差适应算法：每次为进程分配分区时，都选择最大的空闲分区分配。最差适应算法使链表中的结点大小趋于均匀，适用于请求分配的内存大小范围较窄的系统。

• 优点：该算法保留小的空闲区，尽量减少外部碎片的产生。
• 缺点：检查比较所有的空闲区间需要时间；系统中不会存在面积很大的空闲区间，难满足大进程的要求。

（4）首次适应法：只要发现能用的分区就分配。这种方法目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区。

• 优点：可以剩下大的分区。
• 缺点：外部碎片多，集中在低址部分；并且每次查找都是从低址部分开始的，这无疑又会增加查找可用空闲分区时的开销

（5）下次适应法：操作系统记住接下来该检查的空闲分区的位置，给进程分配分区时，系统从记录的分区开始依次向后查找直到碰到能用的分区为止，如果到链表尾还没有找到，就再从头开始。

• 缺点：很难剩下面积很大的区间，会使剩余分区的大小比较平均。

5.5 页面置换算法

（1）当出现缺页异常需调入新页面而内存已满时，选择被置换的物理页面，也就是说选择⼀个物理页面换出到磁盘，然后把需要访问的页面换⼊到物理页。

（2）最佳页面置换算法：置换在「未来」最长时间不访问的页面。最佳页面置换算法作用是为了衡量你的算法的效率，你的算法效率越接近该算法的效率，那么说明你的算法是高效的。

（3）先进先出置换算法（FIFO）：直接换出最早装入的页面。

• 优点：简单。
• 缺点：性能不是很好，因为它淘汰的可能是常用的页面。
• 适用场景：数据只用⼀次，将来不太可能使用；

（4）时钟置换法（Clock）：将页面保存在环形链表中，只需要后移队头指针。如果该位为 0，淘汰该页；如果该位为 1，将该位设为 0

• 优点：避免了移动链表节点的开销。

（5）最近最少使用法（LRU：Least Recently Used）：优先淘汰最久未被访问的页面。根据局部性原理，⼀个进程在⼀段时间内要访问的指令和数据都集中在⼀起。如果⼀个页面很久没有被访问，那么将来被访问的可能性也比较小。

• 优点：实验证明 LRU 的性能较好，能够降低置换频率。
• 缺点：存在缓存污染问题，即由于偶发性或周期性的冷数据批量查询，热点数据被挤出去，导致缓存命中率下降。
• 适用场景：访问分布未知的情况。

（6）最少频率使用法（LFU：Least Frequently Used）：优先淘汰最近访问频率最少的数据。

• 优点：能够避免缓存污染问题对 LRU 的命中影响。
• 缺点：存在访问模式问题，即如果访问内容发生较大变化，LFU 需要用更长的时间来适应，导致缓存命中率下降；维护相关数据结构的开销大。

（7）随机淘汰法（Random）：实现简单，不需要保留有关访问历史记录的任何信息。

• 适用场景：如果应用对于缓存的访问概率相等，则可以使用这个算法。

5.6 磁盘调度算法

（1）为了提高磁盘的访问性能，⼀般是通过优化磁盘的访问请求顺序来做到的。寻找的时间是磁盘访问最耗时的部分，如果请求顺序优化得当，必然可以节省⼀些不必要的寻道时间，从而提高磁盘的访问性能。

1. 先来先服务
2. 最短寻道时间优先（Shortest Seek First，SSF）算法：优先选择从当前磁头位置所需寻找时间最短的请求。但这个算法可能存在某些请求的饥饿
3. 扫描算法：为了防止上述饥饿问题，可以规定：磁头在⼀个⽅向上移动，访问所有未完成的请求，直到磁头到达该方向上的最后的磁道，才调换方向，这就是扫描（Scan）算法。
4. 循环扫描（Circular Scan, CSCAN ）：只有磁头朝某个特定方向移动时，才处理磁道访问请求，而返回时直接快速移动至最靠边缘的磁道，也就是复位磁头，这个过程是很快的，并且返回中途不处理任何请求，该算法的特点，就是磁道只响应⼀个方向上的请求。
5. LOOK 与 C-LOOK算法：扫描算法和循环扫描算法，都是磁头移动到磁盘「最始端或最末端」才开始调换方向。优化的思路就是磁头在移动到「最远的请求」位置，然后立即反向移动。

5.7 内存不足会发生什么

（1）如下图所示：

（2）主要有两类内存可以被回收，而且它们的回收方式也不同。文件页和匿名页的回收都是基于 LRU 算法，也就是优先回收不常访问的内存。

• 文件页：内核缓存的磁盘数据（Buffer）和内核缓存的文件数据（Cache）都叫作文件页。大部分文件页，都可以直接释放内存，以后有需要时，再从磁盘重新读取就可以了。而那些被应用程序修改过，并且暂时还没写入磁盘的数据（也就是脏页），就得先写入磁盘，然后才能进行内存释放。所以，回收干净页的方式是直接释放内存，回收脏页的方式是先写回磁盘后再释放内存。
• 匿名页：这部分内存没有实际载体，不像文件缓存有硬盘文件这样⼀个载体，比如堆、栈数据等。这部分内存很可能还要再次被访问，所以不能直接释放内存，它们回收的⽅式是通过 Linux 的Swap 机制，Swap 会把不常访问的内存先写到磁盘中，然后释放这些内存。再次访问这些内存时，重新从磁盘读入内存就可以了。

（3）在 4GB 物理内存的机器上，申请 8G 内存会怎么样？这个问题要考虑三个前置条件：

• 操作系统是 32 位的，还是 64 位的？因为 32 位操作系统，进程最多只能申请 3 GB 大小的虚拟内存空间，所以进程申请 8GB 内存的话，在申请虚拟内存阶段就会失败
• 申请完 8G 内存后会不会被使用？程序申请的是虚拟内存，如果没有被使用，它是不会占用物理空间的。当访问这块虚拟内存后，操作系统才会进行物理内存分配。
• 操作系统有没有使用 Swap 机制？如果没有开启 Swap 机制，程序就会直接 OOM（内存溢出简称OOM，是指应用系统中存在无法回收的内存或使用的内存过多，最终使得程序运行要用到的内存大于能提供的最大内存）；如果有开启 Swap 机制，程序可以正常运行。

6. 缓存区

（1）缓存区溢出：

• C 语言使用运行时栈来存储过程信息。每个函数的信息存储在⼀个栈帧中，包括寄存器、局部变量、参数、返回地址等。C 对于数组引用不进行任何边界检查，因此对越界的数组元素的写操作会破坏存储在栈中的状态信息，这种现象称为缓冲区溢出。缓冲区溢出会破坏程序运行，也可以被用来进行攻击计算
  机，如使用⼀个指向攻击代码的指针覆盖返回地址。

（2）防范缓冲区溢出攻击的机制：随机化、栈保护和限制可执行代码区域。

1. 随机化：使用缓冲区溢出进行攻击，需要知道攻击代码的地址。因此常见的防范方法有：

   1. 栈随机化：程序开始时在栈上分配⼀段随机⼤⼩的空间

   2. 地址空间布局随机化（Address-Space Layout Randomization，ASLR）：每次运行时程序的不同部分，包括代码段、数据段、栈、堆等都会被加载到内存空间的不同区域。

   3. 但是攻击者依然可以使用蛮力克服随机化，这种方式称为“空操作雪橇（nop sled）”，即在实际的攻击代码前插入很长的⼀段 nop 指令序列，执行这条指令只会移动到下⼀条指令。因此只要攻击者能够猜中这段序列的某个地址，程序就会最终经过这段序列，到达攻击代码。因此栈随机化和 ASLR 只能增加攻击⼀个系统的难度，但不能完全保证安全。

（2）栈保护：

• 在发生缓冲区溢出、造成任何有害结果之前，尝试检测到它。即在每个函数的栈帧的局部变量和栈状态之间存储⼀个随机产生的特殊的值，称为金丝雀值（canary）。在恢复寄存器状态和函数返回之前，程序检测这个金丝雀值是否被改变了，如果是，那么程序异常终至。

（3）限制可执行代码区域：

• 内存页的访问形式有三种：可读、可写、可执行。只有编译器产生的那部分代码所处的内存才是可执行的，其他页应当限制为只允许读和写。

7. I/O 模型

（1）为什么 Redis 单线程模型依然效率很高：多线程技术是为了充分利用 CPU 的计算资源，适用于下层存储慢速的场景。而 redis 是纯内存操作，读写速度非常快。所有的操作都会在内存中完成，不涉及任何I/O 操作，因此多线程频繁的上下文切换反而是⼀种负优化。Redis 选择基于非阻塞 I/O 的 I/O 多路复用机制，在单线程里并发处理客户端的多个连接，减少多线程带来的系统开销，同时也有更好的可维护性，方便开发和调试。

7.1 I/O 模型类型

（1）I/O 模型介绍如下（详细的介绍见博客《基础I/O》和《高级IO和5种IO模型》）：

• I/O 同步和异步的区别在于：将数据从内核复制到用户空间时，用户进程是否会阻塞。
• I/O 阻塞和⾮阻塞的区别在于：进程发起系统调用后，是会被挂起直到收到数据后再返回、还是立即返回成功或失败。
• I/O 模型类别：阻塞IO、⾮阻塞IO、IO复用模型、信号驱动IO模型、异步IO
• 水平触发（LT，Level Trigger）：当文件描述符就绪时，会触发通知，如果用户程序没有⼀次性把数据读/写完，下次还会发出通知。select 只支持水平触发。
• 边缘触发（ET，Edge Trigger）：仅当描述符从未就绪变为就绪时，通知⼀次，之后不会再通知。epoll 支持水平触发和边缘触发。当循环读取 recv 到没有数据时会出现 eagain 现象（LT 是多线程时可能会出现），默认跳过处理。

（2）针对网络IO的操作，可以分成两个阶段：

• **准备阶段（阻塞）：**等待数据是否可用，是在内核进程中完成的；
• 操作阶段（同步）：执行实际的IO调用，数据从内核缓冲区拷贝到用户进程缓冲区。

（3）五大IO类型：

• 阻塞IO：应用进程调用I/O操作时阻塞，只有等待要操作的数据准备好，并复制到应用进程的缓冲区中才返回；
• 非阻塞IO：应用进程调用I/O操作导致该进程进入阻塞状态时，该I/O调用返回⼀个错误。⼀般情况下，应用进程需要利用轮询的方式来检测某个操作是否就绪。数据就绪后，会等待数据复制到应用进程的缓冲区中以后才返回；
• IO复用：多路IO共用同⼀个同步阻塞接口，此时阻塞发生在 select/poll 的系统调用上，而不是阻塞在实际的I/O系统调用上。IO多路复用的高级之处在于，它能同时等待多个文件描述符，而这些文件描述符其中的任意⼀个进入读就绪状态，select等函数就可以返回。
• 信号驱动IO：注册⼀个IO信号事件，在数据可操作时通过信号通知线程。
• 异步IO: 应用进程通知内核开始⼀个异步I/O操作，并让内核在整个操作（包含将数据从内核复制到应用进程的缓冲区）完成后通知应用进程。

7.2 I/O 复用模型

（1）select 缺点（详细的介绍见博客《高级IO和5种IO模型》）：

1. 性能开销大：调用 select 时会陷入内核，这时需要将参数中的 fd_set 从用户空间拷贝到内核空间。内核需要遍历传递进来的 fd_set 的每⼀位，不管它们是否就绪。
2. 能够监听的文件描述符数量太少：受限于 sizeof(fd_set) 的大小，在编译内核时就确定了且无法更改，⼀般是 1024。

（2）poll：

• poll 和 select 几乎没有区别。poll 在用户态通过数组方式传递文件描述符，在内核会转为链表方式存储，没有最大数量的限制。

（3）epoll：

• select、poll 模型都只使用⼀个函数，而 epoll 模型使用三个函数：epoll_create、epoll_ctl（监听事件） 和 epoll_wait（相当于select，返回就绪数量）。
• 特点：
  1. 使用红⿊树存储文件描述符集合。
  2. 使用队列存储就绪的文件描述符。
  3. 每个⽂件描述符只需在添加时传入⼀次，之后调用 epoll_wait 不需要再次传递，提高了效率。
  4. 通过事件更改文件描述符状态。epoll_ctl 中为每个文件描述符指定了回调函数，并在就绪时将其加入到就绪列表，因此只需要判断就绪列表是否为空即可。

（4）三者区别：

1. select、poll 都是在用户态维护文件描述符集合，因此每次需要将完整集合传给内核；epoll 由操作系统在内核中维护⽂件描述符集合，因此只需要在创建的时候传入文件描述符。
2. 当连接数较多并且有很多的不活跃连接时，epoll 的效率高很多；当连接数较少并且都十分活跃的情况下，由于 epoll 需要很多回调，因此性能可能低于其它两者。
3. epoll 不支持跨平台，仅在 linux 上使用，而 select 可以在windows 和 linux 同时使用。

7.3 Reactor 与 Proactor 模式

（1）Reactor 与 Proactor 的区别：

• Reactor 是 非阻塞 同步 网络模式，感知的是 就绪可读写 事件。在每次感知到有IO事件发生（比如可读就绪事件）后，就需要应用进程主动调用read 方法来完成数据的读取，也就是要应用进程主动将socket 接收缓存中的数据读到应用进程内存中，这个过程是同步的，读取完数据后应用进程才能处理数据。
• Proactor 是 异步 网络模式， 感知的是 已完成的读写 事件。在发起异步读写请求时，需要传入数据缓冲区的地址（用来存放结果数据）等信息，这样系统内核才可以自动帮我们把数据的读写工作完成，这里的读写工作全程由操作系统来做，并不需要像 Reactor 那样还需要应用进程主动发起 read/write 来读写数据，操作系统完成读写工作后，就会通知应⽤进程直接处理数据。

（2）因此，Reactor 可以理解为「来了事件操作系统通知应用进程，让应用进程来处理」，而 Proactor 可以理解为「来了事件操作系统来处理，处理完再通知应用进程」。这里的「事件」就是有新连接、有数据可读、有数据可写的 I/O 事件；这里的「处理」包含从驱动读取到内核以及从内核读取到用户空间。无论是 Reactor，还是 Proactor，都是⼀种基于「事件分发」的网络编程模式，区别在于 Reactor 模式是基于「待完成」的 I/O 事件，而 Proactor 模式则是基于「已完成」的 I/O 事件。

8. Copy on Write

（1）写时复制概念如下：

• 写时复制（Copy-on-write，COW），有时也称为隐式共享（implicit sharing）。COW 将复制操作推迟到第⼀次写入时进行：在创建⼀个新副本（只复制其页表）时，不会立即复制资源，而是共享原始副本的资源；当修改时再执行复制操作。通过这种方式共享资源，可以显著减少创建副本时的开销，节省资源。

（2）实现原理：

• fork() 之后，内核会把父进程的所有内存页都标记为只读
• ⼀旦其中⼀个进程尝试写入某个内存页，就会触发⼀个保护故障（缺页异常），此时会陷入内核。
• 内核将写入操作拦截，并为尝试写入的进程创建这个页面的⼀个新副本，恢复这个页面的可写权限，然后重新执行这个写操作，这时就可以正常执行了。
• 内核会保留每个内存页面的引用数。每次复制某个页面后，该页面的引用数减⼀；如果该页面只有⼀个引用，就可以跳过分配，直接修改。

9. Linux

9.1 启动过程

1. BIOS开机自检：当打开电源后，首先是BIOS开机自检，按照BIOS中设置的启动设备（通常是硬盘）来启动。操作系统接管硬件以后，首先读入 /boot 目录下的内核文件。

2. 运行 init：init 进程是系统所有进程的起点，没有这个进程，系统中任何进程都不会启动。init 程序首先是需要读取配置⽂件 /etc/inittab。许多程序需要开机启动。它们在Windows叫做"服务"（service），在Linux就叫做"守护进程"（daemon）。init进程的一大任务，就是去运行这些开机启动的程序。Linux
   启动时根据"运行级别"，确定要运行哪些程序。Linux系统有7个运行级别(runlevel)：

   • 运行级别0：系统停机状态，系统默认运行级别不能设为0，否则不能正常启动
   • 运行级别1：单用户工作状态，root权限，用于系统维护，禁止远程登陆
   • 运行级别2：多用户状态(没有NFS)
   • 运行级别3：完全的多用户状态(有NFS)，登陆后进入控制台命令行模式
   • 运行级别4：系统未使用，保留
   • 运行级别5：X11控制台，登陆后进入图形GUI模式
   • 运行级别6：系统正常关闭并重启，默认运行级别不能设为6，否则不能正常启动

3. 系统初始化：执行 rc.sysinit 脚本，它主要是完成⼀些系统初始化的工作，rc.sysinit是每⼀个运行级别都要首先运行的重要脚本。它主要完成的工作有：激活交换分区，检查磁盘，加载硬件模块以及其它⼀些需要优先执行的任务。

4. 建立终端并登录：这时系统环境基本已经设置好了，各种守护进程也已经启动了。init接下来会打开6个终端，以便用户登录系统。

9.2 常用命令

（1）文件管理（详细的介绍见博客《Linux系统常见指令》）：

• ls: 显示当前目录下文件。
• pwd：显示当前工作目录的绝对路径
• cd + 路径：切换当前工作目录。（路径可以为相对路径也可以为绝对路径）
• touch：创建普通文件。
• rm：删除普通文件 rm -r：删除目录文件 -r（递归的意思）
• mkdir：创建目录文件
• rmdir：删除空目录
• mv：剪切、重命名
• cp：拷贝 cp -r
• chmod：修改文件权限
• tar：压缩文件

（2）进程管理：

• ps ：显示进程信息快照（-e 显示所有进程。 -f 全格式）
• kill pid ：结束进程
• kill -9 pid ：强制结束pid进程
• kill -stop pid ：挂起进程
• &：在后台运行进程

（3）系统管理：

• uptime：查询系统负载。
• top：实时显示系统中各个进程的资源占用状况，类似 于Windows 的任务管理器。
• free：可以显示当前系统未使用的和已使用的内存数目，还可以显示被内核使用的内存缓冲区。

（4）网络通讯命令：

• ping
• ifconfig
• tcpdump：抓包工具。
• netstat：打印本地网卡接口上的全部连接、路由表信息、网卡接口信息。常用：显示tcp连接以及状态。

10. 硬件结构

（1）如下图所示：

10.1 CPU 缓存一致性

（1）解决方法：

1. 写传播：当某个 CPU 核心发生写入操作时，需要把该事件广播通知给其他核心；
2. 事务的串行化：只有保证了这个，才能保障数据是真正⼀致的，程序在各个不同的核心上运行的结果也是⼀致的

（2）MESI 协议：基于总线嗅探机制实现了事务串行化，也用状态机机制降低了总线带宽压力，这个协议就是 MESI 协议，这个协议就做到了 CPU 缓存⼀致性。MESI 协议其实是 4 个状态单词的开头字母缩写，分别是：

• Modified，已修改
• Exclusive，独占。「独占」和「共享」的差别在于，独占状态的时候，数据只存储在⼀个 CPU 核心的 Cache 里，而其他 CPU 核心的 Cache 没有该数据。另外，在「独占」状态下的数据，如果有其他核心从内存读取了相同的数据到各自的 Cache ，那么这个时候，独占状态下的数据就会变成共享状态。
• Shared，共享。「共享」状态代表着相同的数据在多个 CPU 核心的 Cache ⾥都有，所以当要更新 Cache 里面的数据的时候，不能直接修改，而是要先向所有的其他 CPU 核心广播⼀个请求，要求先把其他核心的 Cache 中对应的 Cache Line 标记为「无效」状态，然后再更新当前 Cache 里面的数据。
• Invalidated，已失效

这四个状态来标记 Cache Line 四个不同的状态。

10.2 伪共享

（1）多个线程同时读写同⼀个 Cache Line 的不同变量时，而导致 CPU Cache 失效的现象称为伪共享（False Sharing）。解决方法：

• Cache Line 大小字节对齐：利用宏，以空间换时间的思想，浪费⼀部分 Cache 空间，从而换来性能的提升。
• 字节填充：如在类中增加占位的字符。

10.3 一致性哈希

• ⼀致性哈希算法解决了分布式系统在扩容或者缩容时，发生过多的数据迁移的问题。
• ⼀致性哈希是指将「存储节点」和「数据」都映射到⼀个首尾相连的哈希环上，如果增加或者移除⼀个节点，仅影响该节点在哈希环上顺时针相邻的后继节点，其它数据也不会受到影响。但是⼀致性哈希算法不能够均匀的分布节点，会出现大量请求都集中在⼀个节点的情况，在这种情况下进行容灾与扩容时，容易出现雪崩的连锁反应。
• 为了解决⼀致性哈希算法不能够均匀的分布节点的问题，就需要引入虚拟节点，对⼀个真实节点做多个副本。不再将真实节点映射到哈希环上，而是将虚拟节点映射到哈希环上，并将虚拟节点映射到实际节点，所以这里有「两层」映射关系。引入虚拟节点后，可以会提高节点的均衡度，还会提高系统的稳定性。
• 所以，带虚拟节点的⼀致性哈希方法不仅适合硬件配置不同的节点的场景，而且适合节点规模会发生变化的场景。