[TOC]

内核

PC机启动流程

以Ubuntu Linux + GRUB引导程序为例：

PC机加电后，加载BIOS固件，触发PC机BIOS固件发送指令检测和初始化CPU、内存及主板平台，加载引导设备(比如硬盘)中的第一个扇区数据到0x7c00地址开始的内存空间，再接着跳转到0x7c00处执行指令，加载GRUB引导程序，加载硬盘分区中的OS文件，启动操作系统。

内核结构分类

内核：计算机资源的管理者。计算资源分为硬件资源和软件资源

硬件资源：CPU、内存、硬盘、网卡、显卡、IO设备、总线，他们之间通过总线进行联系；
软件资源：对上述各种硬件资源的管理程序、设备的驱动程序

宏内核结构 - 类似单体服务

将上述所有软件资源进行整合，链接在一起，形成一个大的可执行程序，控制所有硬件资源。这个大程序会在处理器的特权模式下运行，对外提供系统调用函数，供其他程序、进程调用。

当应用层有程序要调用进行内存分配时，就会调用宏内核进行内存分配

应用程序调用内核内存分配API函数
处理器切换到特权模式，开始运行内核代码
内核的内存管理代码按照特定的算法，分配内存
内存分配函数把分配的内存块的首地址返回给应用程序
应用程序接收到返回后，处理器开始运行用户模式下的应用程序，应用程序使用得到的内存首地址，开始使用这块内存

优点：由于所有硬件管理程序都整合在一起，相互调用时性能极高

缺点：所有硬件管理程序都整合在一起，没有模块化，扩展性差，移植性差，牵一发而动全身，每次修改都需要重新安装，其中一个模块有问题就会影响其他模块。

Linux就属于宏内核

Linux 的基本思想是一切都是文件：每个文件都有确定的用途，包括用户数据、命令、配置参数、硬件设备等对于操作系统内核而言，都被视为各种类型的文件。Linux 支持多用户，各个用户对于自己的文件有自己特殊的权利，保证了各用户之间互不影响。多任务则是现代操作系统最重要的一个特点，Linux 可以使多个程序同时并独立地运行。

Linux使用宏内核架构，主要分为上述五大模块，模块间的通信通过函数调用，函数间的调用没有层次关系，所以函数的调用路径纵横交错，如果有函数出问题，那就会影响到调用它的模块，存在安全隐患，但优点是存内核调用，性能极高

Linux高清全结构图：https://makelinux.github.io/kernel/map/

微内核结构 - 类似微服务

内核仅处理进程调度、中断、内存空间映射、进程间通信等，控制硬件资源的软件资源，转成一个个服务进程，比如进程管理、内存管理、设备管理、文件管理等，和用户进程一样，只是它们提供了宏内核的那些功能。

微内核内，进程间通过消息进行通信，应用程序每次要申请资源都需要发送消息到微内核，微内核再把这条消息转发给相关服务进程，直到完成这次调用。

当应用层有程序要调用进行内存分配时

应用程序发送内存分配的消息（发送消息这个函数由微内核提供）
处理器切换到特权模式，执行内核代码
微内核让当前进程停止运行，并根据消息包中的数据，推送给对应的消息接收者，比如这里是内存管理服务进程。
内存管理服务进程收到消息，分配一块内存
内存管理服务进程，处理完成后，通过消息的形式返回分配内存块的地址给内核，然后继续等待下一条消息。
微内核把包含内存地址的消息返回发送给内存分配消息的应用程序
处理器开始运行用户模式下的应用程序，应用程序收到这条消息，得到内存首地址，开始使用这块内存。

优点：系统结构清晰，移植性、伸缩性、扩展性强，微内核代码少，容易替换，各种系统服务进程可随时替换

缺点：进程间消息依赖微内核进行消息传递，会频繁进行服务进程切换，模式切换，导致性能较差。

分离硬件的相关性

分离硬件的相关性其实就是屏蔽底层硬件操作细节，形成一个独立的软件抽象层，对外提供接口，方便应用层接入。

是内核设计的一种指导思想，所以在设计操作系统内核的时候，就可以分为

内核接口层：向应用层提供系统接口函数；
内核功能层：系统函数的主要实现，实现进程管理、内存管理、中断管理、设备管理、驱动、文件系统等；
内核硬件层：对硬件资源的操作，比如初始化CPU、内存、中断控制、其他IO设备

混合内核

混合内核在微内核的基础上进行改进，层次分明，动态加载模块到内核，兼具宏内核和微内核的优点。

Windows就属于混合内核。

CPU

中断：中断即中止执行当前程序，转而跳转到另一个特定的地址上，去运行特定的代码，响应外部事件。

硬件中断：中断控制器给CPU发送了一个电子信号，CPU对这个信号作出应答，随后中断控制器将中断号发给CPU。

软件中断：CPU执行INT指令，指令后带一个常数，该常数为软中断号。

位宽

32 位和 64 位 CPU 最主要区别在于一次能计算多少字节数据：

32 位 CPU 一次可以计算 4 个字节；

64 位 CPU 一次可以计算 8 个字节；

这里的 32 位和 64 位，通常称为 CPU 的位宽，代表的是 CPU 一次可以计算（运算）的数据量。

之所以 CPU 要这样设计，是为了能计算更大的数值，如果是 8 位的 CPU，那么一次只能计算 1 个字节 0~255 范围内的数值，这样就无法一次完成计算 10000 * 500 ，于是为了能一次计算大数的运算，CPU 需要支持多个 byte 一起计算，所以 CPU 位宽越大，可以计算的数值就越大，比如说 32 位 CPU 能计算的最大整数是 4294967295。

CPU 中的寄存器主要作用是存储计算时的数据，内存离 CPU 太远了，而寄存器就在 CPU 里，还紧挨着控制单元和逻辑运算单元，自然计算时速度会很快。

常见的寄存器种类：

通用寄存器，用来存放需要进行运算的数据，比如需要进行加和运算的两个数据。

程序计数器，用来存储 CPU 要执行下一条指令「所在的内存地址」，注意不是存储了下一条要执行的指令，此时指令还在内存中，程序计数器只是存储了下一条指令「的地址」。

指令寄存器，用来存放当前正在执行的指令，也就是指令本身，指令被执行完成之前，指令都存储在这里。

一个程序执行的时候：

CPU 会根据程序计数器里的内存地址（存的是指令的地址），从内存里面把需要执行的指令读取到指令寄存器里面（CPU通过控制单元操作地址总线获取要访问的内存地址，通过数据总线传输）
执行指令（分析指令的类型和参数，计算型的指令交给逻辑运算单元执行，存储类型的指令交给控制单元执行）
根据指令长度自增（自增的步长跟CPU的位宽有关，32位的CPU，指令是4字节，计数器的值就自增4），开始顺序读取下一条指令。

总线

总线是用于 CPU 和内存以及其他设备之间的通信，总线可分为 3 种：

地址总线，用于指定 CPU 将要操作的内存地址；

控制总线，用于发送和接收信号，比如中断、设备复位等信号，CPU 收到信号后自然进行响应，这时也需要控制总线；

数据总线，用于读写内存的数据；

当 CPU 要读写内存数据的时候，一般需要通过下面这三个总线：

首先要通过「地址总线」来指定内存的地址；

然后通过「控制总线」控制是读或写命令；

最后通过「数据总线」来传输数据；

CPU位宽与线路位宽

线路通过高低电压传输数据，一位一位串行传输，下一个bit必须等待上一个bit传输完成才能进行下一个，想要一次多传些数据，就要增加线路，实现并行传输。

CPU想要操作内存地址，就需要地址总线，比如，CPU想操作4G大的内存，就需要32条地址总线，因为2^32=4G。

一般来说，CPU的位宽要大于线路的位宽，操作起来才比较方便。

如果用 32 位 CPU 去计算两个 64 位大小的数字的和，就需要把这 2 个 64 位的数字分成 2 个低位 32 位数字和 2 个高位 32 位数字来计算，先加个两个低位的 32 位数字，算出进位，然后再计算两个高位的 32 位数字的和，最后再加上进位，就能算出结果了，可以发现 32 位 CPU 并不能一次性计算出加和两个 64 位数字的结果。

对于 64 位 CPU 就可以一次性算出加和两个 64 位数字的结果，因为 64 位 CPU 可以一次读入 64 位的数字，并且 64 位 CPU 内部的逻辑运算单元也支持 64 位数字的计算。

但是并不代表 64 位 CPU 性能比 32 位 CPU 高很多，很少应用需要算超过 32 位的数字，所以如果计算的数额不超过 32 位数字的情况下，32 位和 64 位 CPU 之间没什么区别的，只有当计算超过 32 位数字的情况下，64 位的优势才能体现出来。

另外，32 位 CPU 最大只能操作 4GB 内存，就算你装了 8 GB 内存条，也没用。而 64 位 CPU 寻址范围则很大，理论最大的寻址空间为 2^64。

通常来说 64 位 CPU 的地址总线是 48 位，而 32 位 CPU 的地址总线是 32 位，所以 64 位 CPU 可以寻址更大的物理内存空间。如果一个 32 位 CPU 的地址总线是 32 位，那么该 CPU 最大寻址能力是 4G，即使你加了 8G 大小的物理内存，也还是只能寻址到 4G 大小的地址，而如果一个 64 位 CPU 的地址总线是 48 位，那么该 CPU 最大寻址能力是 2^48，远超于 32 位 CPU 最大寻址能力。

如果 32 位指令在 64 位机器上执行，需要一套兼容机制，就可以做到兼容运行了。但是如果 64 位指令在 32 位机器上执行，就比较困难了，因为 32 位的寄存器存不下 64 位的指令；

硬件的 64 位和 32 位指的是 CPU 的位宽，软件的 64 位和 32 位指的是指令的位宽。

时钟周期

硬件参数，比如2GHz的CPU，时钟频率是2G，表示1秒内会产生2G次数的脉冲信号，每一次脉冲信号高低电平的转换就是一个周期，称为时钟周期，时钟周期时间就是1/2G，即0.5ns。程序的CPU执行时间 = 指令数 x 每条指令的平均时钟周期数 x 时钟周期时间

在一个时钟周期内，CPU 仅能完成一个最基本的动作，时钟频率越高，时钟周期就越短，工作速度也就越快。CPU在一个时钟周期内不一定能执行完一条指令。

CPU Cache

程序局部性原理：程序一旦编译完装载进内存中，它的地址就确定了，CPU大多数时间在执行相同的指令或者相邻的指令。

内存，从逻辑上看，是一个巨大的字节数组，内存地址就是这个数组的下标。相比与CPU，内存的数据量吞吐是很慢的，当CPU需要内存数据时，内存一时间给不了，CPU就只能等，让总线插入等待时钟周期，直到内存准备好。因此内存才是决定系统整体性能的关键。为了弥补CPU、内存、硬盘的读写速度差异，不让CPU每次都要等，因此利用程序局部性原理，引入了Cache，一般CPU Cache分成了三级L1，L2，L3：

Cache主要由高速的静态存储器、地址转换模块和Cache Line替换模块组成。

CPU在读取数据和指令时，会一层一层的读，读不到就从下一层进行加载，为了让CPU执行代码执行得更快，就需要利用好CPU Cache，使得缓存的命中率提高，缓存命中了，就不用去加载内存里的数据了。

CPU Cache由很多个Cache Line组成，一行大小通常为32字节或64字节，Cache Line是CPU从内存读取数据的基本单位，他们之间通过 直接映射Cache 把内存里数据的地址映射到Cache Line里。多个Cache Line又会形成一组，除了存储数据，还存储标志位，如脏位、回写位、访问位等；

CPU读取的是内存地址，通过内存地址根据映射策略，在Cache里找到对应的值，通过比较双方的组标记，判断这个地址是否对应这个值。

CPU Cache加载内存数据时，不是一个字节一个字节读取，是一次性读取一块一块的数据放到CPU Cache里的，比如CPU L1 Cache Line的大小是64字节，表示L1 Cache一次载入数据的大小是64字节，加载数据时会顺序加载，当有 int array[100]，载入array[0]时，由于int占4字节，不足64字节，因为数组在内存上是连续的，那CPU就会顺序加载数组元素array[0] ~ array[15]。

当CPU有多核时，线程可能在不同的CPU核心来回切换执行，这对CPU Cache不利，会导致各核心缓存重新加载，各个核心的缓存命中率变低，所以对于CPU密集型的任务，最好将线程绑定到同一个核心区处理，防止因为切换到不同的核心，导致缓存命中率下降的问题，以此来提升性能。

Cache虽提升了性能，但会产生数据一致性问题。Cache可以是一个独立硬件，也可以集成在CPU中，Cache通常有多级，每一级间都有可能产生数据一致性问题。

对于数据的写入，CPU都会先写入到Cache里，然后再在一个合适的时间写入内存，有写直达和写回两种策略，保持Cache和内存的数据一致性。

写直达Write Through：只要有数据写入，都会直接把数据写入内存，性能受限于内存的访问速度；
写回Write back：对于已缓存的Cache的写入，如果要写入的内存地址数据跟当前的一致，只需更新其数据，并标记为脏即可，不用写入到内存；

只有在需要把缓存里的脏数据交换出去的时候，才把数据同步到内存，比如再次写入的时候，发现Cache里存的是别的内存地址的数据，且被标记为脏，就需要先把这个脏数据写入内存，再从内存读入到缓存后才进行写入，并标记为脏；

当再次写入的时候，发现Cache存的是别的内存地址数据，但没有被标记为脏，则先从内存加载要更新的数据的内存地址，替换之前别的内存地址数据，然后写入更新数据，并标记为脏；

多核场景下的保持缓存一致性，需要满足下面两点：

写传播，当某个CPU核心发生写操作时，将该事件通过总线广播通知其他核心，如果其他核心有该缓存，则进行更新；
事务串行化，来保证更新顺序；

解决多核场景下一致性问题就需要数据同步协议，如MESI和MOESI。

基于总线嗅探的MESI协议，就满足上面两点，MESI指的是：已修改、独占、共享、已失效，实现有限状态机，对Cache Line 进行标记，判断缓存是否需要传播更新。为了避免两个不同的核心读取到同一块数据到Cache Line，但是各自又只用到了其中一部分的场景（因为这个时候如果发生修改，会导致缓存不起作用），此时需要将他们所需的数据放到两个不同的Cache Line里，避免更新时的相互干扰，通常的做法是根据Cache Line大小，为这两部分进行多余的数据填充，使其被加载到不同的Cache Line里，即内存对齐，空间换时间。

MESI：M（Modified已修改）、E（Exclusive独占）、S（Shared共享）、I（Invalida已无效）

最开始只有一个核读取了A数据，此时状态为E独占，数据是干净的，后来另一个核又读取了A数据，此时状态为S共享，数据还是干净的，接着其中一个核修改了数据A，此时会向其他核广播数据已被修改，让其他核的数据状态变为I失效，而本核的数据还没回写内存，状态则变为M已修改，等待后续刷新缓存后，数据变回E独占，其他核由于数据已失效，读数据A时需要重新从内存读到高速缓存，此时数据又共享了

以上这些逻辑都由 Cache 硬件独立实现，软件不用做任何工作，对软件是透明的。

工作模式

实模式

又称实地址模式，运行真正的指令，对指令的动作不作区分，直接执行指令的真实功能，另外，发往内存的地址是真实的，对任何地址不加限制地发往内存。

访问内存 - 分段内存管理模式：内存地址由段寄存器左移4位，再加上一个通用寄存器中的值或者常数形成地址，然后由这个地址去访问内存。仅支持16位地址空间，对指令不加限制地运行，对内存没有保护隔离作用。

中断实现，内存中存放一个中断向量表，该表的地址和长度由CPU的特定寄存器IDTR指向，一个条目由代码段地址和段内偏移组成，当出现中断号后，CPU就根据IDTR寄存器中的信息，计算出中断向量中的条目，进而装载CS（代码段基地址）、IP（代码段内偏移）寄存器，响应中断。

保护模式

保护模式是为了应对更高的计算量和内存量，CPU寄存器扩展为32位宽，使其能够寻址32位内存地址空间和32位的数据，还实现指令区分和访问内存地址限制。

为了区分哪些指令(如in、out、cli)和哪些资源(如寄存器、IO端口、内存地址)可以被访问，实现了特权级。特权级分为4级，R0~R3，R0最大，可以指向所有指令，之后依次递减，下一层是上一层的子集。内存访问则靠段描述符和特权级相互配合实现。

访问内存时使用平坦模型：为了应对分段模型的缺陷，在分段模型的基础上套多一层，简化分段模型，对内存段与段之间的访问严格检查，没有权限不会放行。

中断时由于要进行权限检测和特权级切换，需要扩展中断向量表的信息，每个中断用一个中断门描述符来表示，存于中断向量表中

长模式

又名AMD64模式，在保护模式的基础上，增加一些通用寄存器，扩展通用寄存器的位宽，所有的通用寄存器都是64位，还可单独使用低32位。低32位可以拆分成一个低16位寄存器，低16位又可以拆分为两个8位寄存器。

访问内存时需要开启分页模式，弱化段模式管理，仅保留权限级别的检查，忽略段基址和段长度，地址检查交给MMU。

中断时的中断向量表中的条目，中断描述符需要扩展，将其32位段内偏移扩展成支持64位

1、x86 CPU的位数越来越高，从16到32到64，每次进步都尽量的去兼容了之前的CPU架构，所以： A、16位时寻址能力不足，所以要借助额外的寄存器进行1M空间的寻址；32位时，每个程序都有自己独立的4G寻址空间，操作系统用低位的1G-2G，其余留给用户程序；64位后，暂时就遇不到寻址能力不足的事情了； B、前一代的寄存器尽量保留，不够用就扩展新的 C、寄存器的长度升级后，其低位可以兼容上一代的寄存器

2、CPU同时在安全性上也要提升，从只有实模式【可以随意执行全部CPU指令，内存可以直接通过物理地址访问，随意访问随意读写】，到了32的保护模式【将指令划分为ring0到ring3，CPU指令不是你想调用就能调用；内存不是你想访问就能访问，首先CPU要允许，而且操作系统允许】，而64的长模式在安全方面与32并没有本至区别；

3、从实模式到保护模式，访问内存时，需要访问的地址变大了，需要控制的内容变多了，于是引入了段描述符，所有的段描述符组成了描述符表，包括唯一的全局描述符GDT和多个局部描述符号LDT。GDT是操作系统特供，要重点关注。CPU寻址的时候，要通过段寄存器+GDTR寄存器定位到的内存中的描述符，判断是否允许访问。然后，再根据段描述符中地址进行访问。

4、同时内存中内存管理有段、页、段页三种常用模式。一般在应用层，程序员感受不太到，操作系统全给咱们做完了。

5、中断，其实是通过硬件或软件方式告诉CPU，来执行一段特殊的代码。比如咱们键盘输入，就是通过硬件中断的方式，告知操作系统的。在实模式下，中断是直接执行的。但到了保护模式和长模式下，就要特权级别校验通过才能执行，所以引入了中断门进行控制。在ring3调用中断一般是要通过操作系统切换到内核态ring0进行的，与内存类似，要通过中断向量表，确认中断门中权限是否允许，然后定位到指定代码执行。

6、BIOS引导后，系统直接进入最简单、特权最大的实模式；而后告知CPU，切换到保护模式，并运行在ring0。后续的用户进程，一般就在ring3，想执行特权指令要通过操作系统来执行

内核态和用户态

对于32位操作系统来说，寻址空间为4G(2的32次方)，即进程最大地址空间是4G。

内核独立于普通的应用程序，可以访问受保护的内存空间，还有底层硬件设备的所有权限，所以，为了保护内核安全，现在的操作系统一般都强制用户进程不能直接操作系统内核。

操作系统将虚拟地址空间划分为两部分，一部分为内核空间，另一部分为用户空间。针对 Linux 操作系统而言，最高的 1G 字节(从虚拟地址 0xC0000000 到 0xFFFFFFFF)由内核使用，称为内核空间。而较低的 3G 字节(从虚拟地址 0x00000000 到 0xBFFFFFFF)由各个进程使用，称为用户空间；内核态在0~4G范围的虚拟空间地址都可以操作，只是3~4G范围的虚拟空间地址必须由内核态去操作，所有进程的内核态都共享3~4G这个范围的数据。

之所以要分内核空间和用户空间，是因为有些CPU指令的权限比较大，可能导致系统崩溃，如果允许所有进程访问，容易出事，导致故障或崩溃，所以操作系统将CPU指令集分为两部分：特权指令和非特权指令，特权指令只允许操作系统及相关模块使用，非特权指令给普通应用程序使用。

Intenel的CPU将特权等级分为4个，Ring0~Ring3，Ring0权限最高，可以使用所有CPU指令集，Ring3权限最低，只能使用常规的CPU指令集，不能操作硬件资源的CPU指令集，比如IO读写、网卡访问、申请内存等操作；

Linux系统只用了Ring0和Ring3，Ring3不能访问Ring0的地址空间，当进程运行在Ring3级别时被称为运行在用户态，运行在Ring0级别被称为运行在内核态。

在内核态下，进程运行在内核地址空间中，此时 CPU 可以执行任何指令。运行的代码也不受任何的限制，可以自由地访问任何有效地址，也可以直接进行端口的访问。

在用户态下，进程运行在用户地址空间中，被执行的代码要受到 CPU 的诸多检查，它们只能访问映射其地址空间的页表项中规定的在用户态下可访问页面的虚拟地址，且只能对任务状态段(TSS)中 I/O 许可位图(I/O Permission Bitmap)中规定的可访问端口进行直接访问。

所以，即便是单个应用程序出现错误也不会影响到操作系统的稳定性，这样其它的程序还可以正常的运行，区分内核空间和用户空间本质上是要提高操作系统的稳定性及可用性。

内核会对这些特权指令集封装成一个个接口，供用户空间的应用程序使用，比如读写磁盘，分配内存、回收内存、从网络接口读写数据等。进程在用户态和内核态各有一个堆栈，用来保存在对应空间执行的上下文。应用程序要读磁盘数据，1. 首先通过特殊指令，从用户态进入内核态，执行特权指令，2. 从磁盘上读取数据到内核空间中，3. 再把数据拷贝到用户空间，并从内核态切换到用户态。

总共有三种方式可以从用户态切换到内核态：系统调用system call、软硬中断、异常。

从用户态到内核态的切换开销比较大，主要是因为：

保留用户态现场（上下文、寄存器、用户栈等）
复制用户态参数，用户栈切到内核栈，进入内核态
额外的检查（因为内核代码对用户不信任）
执行内核态代码
复制内核态代码执行结果，回到用户态
恢复用户态现场（上下文、寄存器、用户栈等）

CPU上下文

Linux是一个多任务操作系统，可以支持远大于CPU数量的任务同时进行，通过在短时间内分配CPU给任务运行实现并行的目的，因此CPU需要知道每个任务从哪里加载，哪里开始运行，需要事先帮它们设置好CPU寄存器和程序计数器，因此CPU寄存器和程序计数器就算CPU上下文。

CPU寄存器：CPU内置的容量小，但速度快的内存
程序计数器：存储CPU正在执行指令的位置，或者即将执行的下一条指令的位置

CPU上下文切换时，先把前一个任务的 CPU 上下文（也就是 CPU 寄存器和程序计数器）保存起来，然后加载新任务的上下文到这些寄存器和程序计数器，最后再跳转到程序计数器所指的新位置，运行新任务。

而这些保存下来的上下文，会存储在系统内核中，并在任务重新调度执行时再次加载进来。这样就能保证任务原来的状态不受影响，让任务看起来还是连续运行。

进程上下文切换

发生系统调用时，进程从用户态进入内核态，这个过程发生上下文切换：

1、保存 CPU 寄存器里原来用户态的指令位 2、为了执行内核态代码，CPU 寄存器需要更新为内核态指令的新位置。 3、跳转到内核态运行内核任务。 4、当系统调用结束后，CPU 寄存器需要恢复原来保存的用户态，然后再切换到用户空间，继续运行进程。

所以，一次系统调用过程，实际发生了两次CPU上下文切换，用户态 -> 内核态 -> 用户态，但系统调用过程中，不会涉及虚拟内存等进程用户态的资源，也不会切换进程，系统调用过程中一直是同一个进程在运行。

系统调用通常也称为特权模式切换，系统调用属于同进程内的CPU上下文切换。

进程上下文切换指的是两个不同的进程间的切换；

进程是由内核来管理和调度的，进程的切换只能发生在内核态。所以，进程的上下文不仅包括了虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈、寄存器等内核空间的状态。

进程的上下文切换就比系统调用时多了一步：在保存内核态资源（当前进程的内核状态和 CPU 寄存器）之前，需要先把该进程的用户态资源（虚拟内存、栈等）保存下来；而加载了下一进程的内核态后，还需要刷新进程的虚拟内存和用户栈，这个过程就比较耗资源了。

发生进程上下文切换的场景：

CPU将时间片轮流分配给各个进程，当某个进程的时间片被耗尽，就会被系统挂起，切换到其他正在等待CPU执行的进程；
进程在系统资源不足（比如内存不足）时进行等待，此时会被CPU挂起，并由系统调度其他进程运行；
当进程通过sleep函数主动挂起，此时会重新调度；
当有优先级更高的进程运行时，为了保证高优先级进程的运行，当前进程会被挂起，由高优先级进程来运行；
发生硬件中断时，CPU上的进程被中断挂起，转而执行内核中的中断服务程序；

线程上下文切换

内核中的任务调度，实际上调度的是线程，而进程只是给线程提供了共享的虚拟内存，全局变量等资源，线程本身也有自己的栈和寄存器，在上下文切换时也要保存。

切换场景：

前后两个属于不同进程的线程，因为资源不共享，在切换过程就跟进程上下文切换一样；
前后两个属于同一进程的线程，因为虚拟内存是共享的，在切换时，虚拟内存这些资源保存不动，只需切换线程的私有数据、寄存器等不共享的数据；

中断上下文切换

硬中断：处理硬件请求，负责耗时短的任务，快速执行，会打断当前正在执行的任务，立即执行中断；

软中断：由内核触发，负责硬中断中未完成的工作或者内核定义的一些中断事件，通常是耗时比较长的事情，延迟执行；Linux的软中断包括网络收发、定时、调度、RCU锁等各种类型

为了快速响应硬件的事件，中断处理会打断进程的正常调度和执行，转而调用中断处理程序，响应设备事件。而在打断其他进程时，就需要将进程当前的状态保存下来，这样在中断结束后，进程仍然可以从原来的状态恢复运行。

跟进程上下文不同，中断上下文切换并不涉及到进程的用户态。所以，即便中断过程打断了一个正处在用户态的进程，也不需要保存和恢复这个进程的虚拟内存、全局变量等用户态资源。中断上下文，其实只包括内核态中断服务程序执行所必需的状态，包括 CPU 寄存器、内核堆栈、硬件中断参数等。

对同一个 CPU 来说，中断处理比进程拥有更高的优先级，所以中断上下文切换并不会与进程上下文切换同时发生。

同步原语

常见的有：原子操作、控制中断、自旋锁、信号量。底层原子操作都是依靠支持原子操作的机器指令的硬件实现。

原子操作是对单一变量。
控制中断：可以作用复杂变量，一般用在单核CPU，同一时刻只有一个代码执行流，响应中断会导致代码执行流切换，此时如果两个代码执行流操作到同一个全局变量就会导致数据不一致，所以需要在操作全局变量时关闭中断，处理完开启进行控制。
自旋锁还有一个作用就是可以在多核CPU下处理全局变量，因为控制中断只能控制本地CPU的中断，无法控制其他CPU核心的中断，此时其他CPU是可以操作到该全局变量的。自旋需要保证读取锁变量和判断并加锁操作是原子的，且会导致CPU空转一段时间。
信号量的一个作用就是解决自旋锁空转造成CPU资源浪费的缺点。

Linux初始化

引导 boot

也是机器加电，BIOS自检，BIOS加载引导扇区，加载GRUB引导程序，最后由GRUB加载Linux内核镜像vmlinuz。

CPU被设计成只能运行内存中的程序，无法直接运行存储在硬盘或U盘中的操作系统程序，因为硬盘U盘等外部存储并不和CPU直接相连，访问机制和寻址方式与内存不一样。如果要运行硬盘或U盘中的程序，就必须先加载到内存。

由于内存RAM断电会丢失数据，BIOS不是存储在普通的内存中的，而是存储在主板上特定的一块ROM内存中，在硬件设计上规定加电瞬间，强制将CS寄存器的值设置位0xF000，IP寄存器的值设置为0xFFF0，该地址就是BIOS的启动地址了。

BIOS在初始化CPU和内存后进行检查，完了之后将自己的一部分复制到内存，最后跳转到内存中运行。之后枚举本地设备进行检查和初始化，调用设备的固件程序。当设备完成检查和初始化后，BIOS就会在内存中划定一个地址范围，存放和建立中断表和中断服务程序。

一般我们会把Linux镜像放在硬盘的第一个扇区中（MBR主启动记录，包含基本的GRUB启动程序和分区表），然后让硬盘作为BIOS启动后搜索到的第一个设备，当MBR被BIOS装载到0x7c00地址开始的内存空间中，BIOS会把控制权交给MBR，即GRUB。

GRUB所在的第一个扇区，只有512个字节，不足以装下GRUB这种大型的通用引导器，因此GRUB的加载被分成了多个步骤和多个文件，在启动时动态加载，先加载diskboot.img，然后读取剩下的core.img，识别出文件系统，使其能够访问/boot/grub目录，最后加载vmlinuz内核文件。

启动 startup

1.GRUB 加载 vmlinuz 文件之后，会把控制权交给 vmlinuz 文件的 setup.bin 的部分中 _start，它会设置好栈，清空 bss，设置好 setup_header 结构，调用 16 位 main ，调用BIOS中断，进行初始化设置，包括console、堆、CPU模式、内存、键盘、APM、显卡模式等，然后切换到保护模式，最后跳转到 1MB 处的 vmlinux.bin 文件中。

2.从 vmlinux.bin 文件中 startup32、startup64 函数开始建立新的全局段描述符表和 MMU 页表，切换到长模式下解压 vmlinux.bin.gz。释放出 vmlinux 文件之后，由解析 elf 格式的函数进行解析，释放 vmlinux 中的代码段和数据段到指定的内存。然后调用其中的 startup_64 函数，在这个函数的最后调用 Linux 内核的第一个 C 函数。 3.Linux 内核第一个 C 函数重新设置 MMU 页表，随后便调用 start_kernel 函数， start_kernel 函数中调用了大多数 Linux 内核功能性初始化函数，在最后调用 rest_init 函数建立了两个内核线程，在其中的 kernel_init 线程建立了第一个用户态进程

内存管理

虚拟地址

由于各个应用程序由不同的公司开发，且每台计算机的内存容量都不一样，如果应用程序在运行时使用的是真实地址，将会导致各个应用程序在使用内存地址时产生冲突。为了解耦内存真实地址和应用使用的内存地址，对不同的应用程序使用的内存进行隔离和保护，引出虚拟地址概念。

虚拟地址：让每个应用程序都各自享有一个从0开始到最大地址的空间，在每个应用程序独立且私有，其他应用程序无法观察到，再由操作系统将虚拟地址映射成真实的物理地址，实现内存的使用。

虚拟地址由链接器产生，应用程序经过编译后通过链接器的处理变成可执行文件，链接器会处理程序代码间的地址引用，形成程序运行的静态内存空间视图。

实模式下，多个进程共享所有地址空间太过危险，因此有了保护模式，保护模式下为了让各个应用程序能正确使用内存，使用了虚拟地址映射，让各个应用程序都有自己的地址空间，因此访问内存时不用考虑其他问题，访问时再经过MMU翻译得到对应的页表，不同的应用程序由于不同的页表，产生了进程地址空间隔离，但多个应用程序也可以共享某个页表，此时就涉及进程间的通信了。

关于内存对齐：因为cpu总是以多个字节的块为单位访问内存的，不与它的访问块地址边界对齐cpu就要多次访问。

虚拟内存有三个特征：多次性、对换性、虚拟性。它将程序分多次调入内存，使得在较小的用户空间可以执行较大的用户程序，所以同时容纳更多进程并发执行，从而提高系统吞吐量；发生缺页时取决于内存的存储管理方式，可以调入一个段，也可以调入一个页；虚拟性表示虚拟内存和物理内存的映射。

虚拟内存的核心原理是：为每个程序设置一段"连续"的虚拟地址空间，把这个地址空间分割成多个具有连续地址范围的页 (page)，并把这些页和物理内存做映射，在程序运行期间动态映射到物理内存（通过MMU管理）。当程序引用到一段在物理内存的地址空间时，由硬件立刻执行必要的映射；而当程序引用到一段不在物理内存中的地址空间时，由操作系统负责将缺失的部分装入物理内存并重新执行失败的指令。

在进程运行期间只分配映射当前使用到的内存，暂时不使用的数据则写回磁盘作为副本保存，需要用的时候再读入内存，动态地在磁盘和内存之间交换数据。

如果分配后的虚拟内存没有被访问的话，虚拟内存是不会映射到物理内存的，这样就不会占用物理内存了。

只有在访问已分配的虚拟地址空间的时候，操作系统通过查找页表，发现虚拟内存对应的页没有在物理内存中，就会触发缺页中断，然后进程会从用户态切换到内核态，将缺页中断交给内核的缺页中断函数，该函数会检查是否有空闲的物理内存，如果有，就进行分配，建立虚拟内存和物理内存之间的映射关系，如果没有，就回收空闲内存，如果回收后仍然不够分配，就会触发OOM，该机制会杀死物理内存占用最高的进程，以释放内存，直到内存足够分配。

作用

使得进程可以对运行内存使用超过物理内存的大小，如果超出内存大小，会使用swap，把不常用的内存换到磁盘
每个进程有自己的页表，每个进程的虚拟内存就是相互独立的，进程也没办法访问其他进程的页表，属于私有页表，解决多进程之间地址冲突问题
页表里的页表项除了物理地址外，还有一些标记属性的比特，比如控制一个页的读写权限，标记该页是否存在，为操作系统提供更好的安全性。

所需要的最基础的硬件支持

一位，用于特权模式和用户模式的切换
基址寄存器：用于虚拟地址与物理地址的转换；界限寄存器：用于地址的界限检查，防止用户程序访问到不属于它的地址
能转换虚拟地址并检查它是否越界
修改基址/界限寄存器的特权指令
注册异常处理程序的特权指令
能够触发异常
段寄存器，比如前两位拿来表示什么类型的段，比如栈、堆、代码区，用于计算段内的偏移量，配合基址寄存器和界限寄存器，计算出虚拟地址要映射的物理地址；设置保护位实现代码段共享；

内存划分与组织

内存碎片

内部内存碎片：由于采用固定大小的内存分区，当一个进程不能完全使用分给它的固定内存区域时就会产生内部内存碎片，这通常难以避免；

外部内存碎片：由于某些未分配的连续内存区域太小，以至于不能满足任意进程的内存分配请求，从而不能被进程利用的内存区域；

如果只是简单的通过基址和界限寄存器，将划分的虚拟内存区域一整块直接映射到物理内存，由于虚拟内存并不会完全用完，中间会空出一小块，对应到物理内存里也是，导致内存利用率不高，内存碎片的产生，所以才有了分段、分页、段页式等的内存分配方案；

现在普遍使用段页式内存分配方案，将内存分为不同的段，再将每一段分成固定大小的页，通过页表机制，使得段内的页可以不必连续处于同一内存区域，只分配必要的内存，提升内存空间的利用率。

分段

地址是二维的，一维是段号，二维是段内偏移量，每个段的长度不一样，且每个段偏移量都是从0开始编址，通过段号找到对应的段内描述符，再通过段基地址 + 段内偏移量，最终确定物理内存地址；
在分段管理中，每个段内部是连续的内存分配，但是段与段之间是离散分配的，存在一个逻辑地址到物理地址的映射，即段表机制；通过段表实现虚拟地址与物理地址的映射；
段的长度大小不一，可动态改变，好处是需要多少分配多少，产生连续的内存空间，坏处是不便于用一个统一的数据结构表示，容易产生外部内存碎片；
产生外部内存碎片后，如果产生多个不连续的内存片段，而新的程序无法使用它，就需要进行内存交换，内存交换需要用到磁盘，就涉及到访问速度的问题，内存交换的效率就低；
内存不足时，内存数据会写回硬盘来释放内存，由于段的长度大小不一，每段的读写时间就会不一样，导致性能抖动；

分段主要是为了程序和数据可以被划分为逻辑上独立的地址空间（比如分成代码、堆、栈这些段），有助于数据的共享和保护，比如数据共享、数据保护、动态链接等，需要程序员显式划分每个段。

分页

页的大小固定，可以用位图表示页的分配和释放，作为主存的基本单位，分页可以使得内存分配粒度变小，以此来减少外部内存碎片的产生，但如果程序需要的内存不足一页，由于最小分配单位是一页，就会造成内部内存碎片的情况出现；

页会产生内存碎片，但可以通过修改页表的方式，让连续的虚拟页面映射到非连续的物理页面，实现分段的效果；比如有1，2，3是空闲，4已被分配，5是空闲，可以通过映射让5接上3；
因为程序数据存储在不同的页中，而页又离散分布在内存中，因此需要一个页表来记录映射关系，页表也是存储在内存中的，通过内存管理单元MMU实现虚拟地址和物理地址的转换；

通过降低内存分配的粒度 + 页表映射，解决分段内存带来的外部内存碎片过大和内存交换效率低的问题。
分页的地址空间是一维的，分配的最小单位是页。页内的虚拟地址按位划分为页号和页内偏移，通过页号找到对应的页表，再通过页表上的物理页号找到对应的物理页，再通过页内偏移量 + 物理页的基地址，最终确定物理内存地址；

所以，访问分页系统中的内存数据需要两次访问，第一次确定物理内存的地址，第二次根据第一次得到的物理地址访问内存取出数据；

当进程访问虚拟地址在页表中查不到时，系统会产生一个缺页异常，进入系统内核空间分配物理内存，更新进程页表，最后再返回到用户空间，恢复进程运行；
操作系统在对内存管理时，使用一个数据结构描述一个内存页，每个数据结构包含相邻页的指针，多个内存页形成一个链表，Linux下每页大小是4KB。
内存不足时，内存数据会写回硬盘来释放内存（页置换算法），由于每页大小一致，每页的读写时间也会一致，内存交换效率相对比较稳定；
在完成虚拟内存和物理内存页之间的映射后，并不真的把页加载到物理内存里，而是只有在程序运行中，需要用到的对应虚拟内存页里面的指令和数据时，再加载到物理内存里；

多级页表

因为每个进程有自己的虚拟空间地址，如果每个进程都拥有自己的页表，那数量会非常庞大，比如在32位CPU、页大小4KB的环境下，一个进程，4GB的虚拟内存的单级页表就需要100万个，每个页表需要4个字节存储，4G的虚拟内存就需要占4MB，当进程有100个，就需要分配400MB的内存来存储页表，但实际上进程一次可能用不到这么多虚拟地址，于是操作系统使用多级页表解决这个问题。

多级页表，就是将单级页表进行分页，比如分为1024个一级页表，每个二级页表再分为1024个单表项（相乘就有100万个了），映射而成就需要4KB + 4MB内存空间，一级页表如果没被用到，二级页表就不需要创建了，所以可以省很多内存空间；

页表的作用就是将虚拟地址转换为物理地址，如果虚拟地址在页表中找不到对应的页表项，就会出问题，所以页表一定要覆盖全部虚拟地址；对于64位的系统，两级页表就不够用了，需要变成四级页表，以此类推成多级页表；

多级页表解决空间上的问题，但是虚拟地址到物理地址的转换就多了步骤，因为如果页表也是存在物理内存，那做虚拟地址转换时，需要先读页表所在的物理内存，得到转换后的物理地址，进而才能读到对应物理地址的值，多了一次额外的读取，降低地址转换效率，因此，需要额外的硬件来加速地址转换。

为了加速地址翻译，在CPU芯片中加入一个存放程序最常访问的页表项的Cache，叫TLB（translation lookaside buffer），又叫页表缓存、转址旁路缓存、快表，CPU芯片也会封装MMU，CPU寻址时，先查TLB，没找到再去查常规的页表，TLB会利用局部性原理，会加载相邻的地址。

段页式

将程序分为多个有逻辑意义的段，方便管理，比如地址范围为多少多少的内存区域就给硬件用，多少多少的给内核区，多少多少给应用区等，再对段内内存进行分页，划分成固定大小的页，从而更好的利用内存，减少内存碎片的产生。

段页式地址变换中要得到物理地址须经过三次内存访问：

第一次访问段表，得到页表起始地址；

第二次访问页表，得到物理页号；

第三次将物理页号与页内位移组合，得到物理地址。

可用软、硬件相结合的方法实现段页式地址变换，这样虽然增加了硬件成本和系统开销，但提高了内存的利用率。

组织内存页

为了能高效的分配内存，需要把内存区数据结构和内存页面数据结构关联起来，组织成一个内存分割合并的数据结构。

以2的N次方为页面数组织页面的原因：

1、内存对齐，提升CPU寻址速度 2、内存分配时，根据需求大小快速定位至少从哪一部分开始 3、内存分配时，并发加锁，分组可以提升效率 4、内存分配回收时，很多计算也更简单

MMU

虚拟地址转换为物理地址通过MMU(内存管理单元)实现，只能在保护模式或者长模式下开启。

MMU使用分页模型，即把虚拟地址空间和物理地址空间都分成同等大小的页，按照虚拟页和物理页进行转换，一个虚拟地址对应一个物理地址，一个虚拟页对应一个物理页，页大小一经配置就是固定，通过内存中存储的一个地址关系转换表（页表）实现转换。

为了增加灵活性和节约物理内存空间（因为页表是放在物理内存中的），所以页表中并不存放虚拟地址和物理地址的对应关系，只存放物理页面的地址，MMU 以虚拟地址为索引去查表返回物理页面地址，而且页表是分级的，总体分为三个部分：一个顶级页目录，多个中级页目录，最后才是页表。

分层的结构是根据页大小决定。

为了解决进程通过MMU访问内存比直接访问内存多了一次内存访问，导致性能下降的问题，引入TLB快表进行加速。TLB可以简单理解成页表的高速缓存，保存了最高频次被访问的页表项，一般由硬件实现，速度极快。

空闲空间管理

基本机制

分割与合并：根据请求的大小进行空闲空间分割，回收时，对被回收空间相邻的空间进行检查，如果也是空闲空间，则进行合并；
追踪已分配空间的大小：分配空间时，除了分配请求的大小，还会分配一块头部，记录已分配空间的元数据信息，方便查找和释放；
嵌入空闲列表：在空闲空间本身建立空闲空间列表，实现对空闲空间的管理；
内存增长：当当前的空闲空间内存耗尽，向操作系统申请更大的空闲空间

内存分配基本策略

最优匹配：遍历整个空闲列表，找到和请求大小一样或更大的空闲块，返回这组候选者中最小的一块，缺点是需要遍历查找，性能不高；
最差匹配：尝试找到最大的空闲块，根据请求大小进行分割，然后把剩余的空闲块加入空闲列表，缺点是同样需要遍历，且更容易产生内存碎片，一般不使用这种策略；
首次匹配：找到第一块满足请求的块，分配完后剩余空闲块加入空闲列表，这种方法不需要遍历所有空闲块，但不稳定，有时候会产生很多内存碎片，如何管理空闲列表的顺序就变得重要，一般是基于地址排序，通过保持空闲块按内存地址有序，方便合并，减少内存碎片；
下次匹配：不同于首次匹配每次都从列表头部开始遍历查找，下次匹配是从上次结束查找的位置开始查找，避免对列表开头进行频繁分割；
分离空闲列表：如果某个程序经常申请一种或几种大小相同的内存空间，就用一个独立的列表，只管理这样大小的对象，其他大小的对象则交给更通用的内存分配程序，像Go的内存分配就从mspan、mcache、mcentral里分配内存；

这种分配方式的好处是不会产生多余的内存碎片，也没有复杂的列表查找过程，内存的分配和释放都很快；

难点在于初始时要分配多少空间给这种空闲列表，常见的做法是先分配一小块内存，不够用时，向通用内存申请一块总量是页大小和对象大小的公倍数内存厚块，当内存厚快的对象引用计数为0时，则进行回收；
伙伴系统：空闲空间首先从概念上被当成 2^N 的大空间，当有一个内存分配请求时，空间空间系统被递归一分为二，直到刚好满足请求的大小，这种分配策略只允许分配2的整数次幂大小的空闲块，因此会有内部内存碎片，好处是当内存被释放时，可以递归检查，并且检查相邻空间，如果是则合二为一，直到合并整个内存区域，或者某一块的伙伴还不能被释放；

页置换算法

由于程序是分多次装入内存的，运行到一定时间，在地址映射过程中如果发现要访问的页不存在内存中，会发生缺页中断，此时操作系统必须在内存里选择一个页把它移除内存，为即将调入的页面让出空间，而选择淘汰哪一页就需要页面置换算法。

缺页中断与一般中断的区别：

缺页中断在指令执行「期间」产生和处理中断信号，而一般中断在一条指令执行「完成」后检查和处理中断信号；
缺页中断返回到该指令的开始重新执行「该指令」，而一般中断返回回到该指令的「下一个指令」执行。

如果第4步不能在物理内存找到空闲页时，说明此时物理内存已满，需要使用页置换算法，选择一个物理页，如果该物理页是脏页，则把它swap到磁盘，并把被置换出去的页表的状态改成无效，最后把正在访问的页转入这个物理页中。

常见的页面置换算法：

最佳页面置换算法OPT：

将当前页中未来最长时间不会被访问的页置换出去，该算法会计算内存中每个逻辑页面的下一次访问时间，然后比较，选择未来最长时间不访问的页面。由于很难预测每个页面在下一次访问前的等待时间，所以该算法只能用来衡量置换效率。
先进先出置换算法FIFO：

选择在内存驻留时间很长的页面进行置换，效率一般；
最近最久未使用算法LRU：

选择最长时间没有被访问的页面进行置换，开销较大，因为需要在内存中维护一个所有页面的链表，而且每次访问内存都必须更新整个链表，比较耗时，所以实际中比较少用；
最近最不常用算法LFU：

当发生缺页中断时，选择访问次数最少的页面，将其置换，很LRU一样，实现成本很高，需要为每个页面添加一个计数器，还需要查找链表，比较耗时，也比较少用；
时钟页面置换算法NRU（最近未使用算法）

将页面链接成一个环形列表，每个页有一个访问位0/1，1表示清除访问位，并把指针前移，重复这个过程直到找到位为0的页面；0表示需要淘汰该页面，并把新的页面插入到此位置，然后指针前移。

发生缺页中断后，指针遍历环形列表，会把沿途遇到的访问位为1的修改为0，直到遇到访问位为0的页面，将其淘汰，置换成新页，然后访问位置为1；

关于堆内存和栈内存

堆内存和栈内存是基于对象生命周期、分配、回收的时机进行划分

栈内存：一般是一种后进先出（LIFO）的数据结构，对连续内存的线性分配，用来存储函数调用时的局部变量、函数参数和返回值等临时性的数据简单高效，方便回收。

堆内存：动态分配的内存，用来存储程序运行时动态创建的对象、数组等数据，比如指针依赖，全局变量。由于堆内存的大小和生命周期都比较不确定，所以操作系统需要动态地管理它。在使用堆内存时，程序需要显式地申请内存空间，并在不再需要时释放它，否则就可能导致内存泄漏等问题。

内存分配与回收

系统调用函数

brk()：从用户态的堆中分配内存，只是将堆顶指针向高地址移动，获得新内存；c语言的malloc函数，当用户分配的内存小于128KB时会调用此方法；在free释放内存时，并不会把内存归还给操作系统，而是缓存在malloc的内存池，待下次使用；
mmap()：使用私有匿名映射的方式，在用户态的文件映射区分配一块内存；c语言的malloc函数，当用户分配的内存大于128KB时会调用此方法；在free释放内存时，会把内存归还给操作系统，内存得到真正的释放；

两者分配的都是虚拟内存，只有被访问到的时候才会触发缺页中断进行分配，建立映射，没访问到就不会申请。

内存分配过程

通过上面两个函数申请的内存都是虚拟内存，此时并不会分配物理内存，当应用程序读写了这块虚拟内存，CPU就会去访问这个虚拟内存，然后发现没有映射到物理内存，CPU就会产生缺页中断，进程从用户态切换到内核态，并将缺页中断交给内核的Page Fault Handler缺页中断函数处理。该函数会判断是否有空闲的物理内存，如果有，直接分配物理内存，并建立虚拟内存和物理内存的映射，如果没有空闲的物理内存，内核就会开始内存回收工作；

由于申请虚拟内存但不使用就不会分配物理内存，所以实际上是可以申请远超物理内存大小的内存，当然具体还得看CPU的位数，看具体能操作的最大范围。

在 32 位操作系统，因为进程最大只能申请 3 GB 大小的虚拟内存，所以直接申请 8G 内存，会申请失败。

在 64 位操作系统，因为进程最大只能申请 128 TB 大小的虚拟内存，即使物理内存只有 4GB，申请 8G 内存也是没问题，因为申请的内存是虚拟内存。

程序申请的虚拟内存，如果没有被使用，它是不会占用物理空间的。当访问这块虚拟内存后，操作系统才会进行物理内存分配。

如果申请物理内存大小超过了空闲物理内存大小，就要看操作系统有没有开启 Swap 机制：

如果没有开启 Swap 机制，程序就会直接 OOM；

如果有开启 Swap 机制，程序可以正常运行。

内存回收

后台内存回收：物理内存紧张时，唤醒kswapd内核线程异步回收内存，不会阻塞进程的执行；
直接内存回收：后台异步回收跟不上进程内存申请的速度，就会开始直接回收，此时是同步的，会阻塞进程的执行，可能造成长时间的延迟，CPU利用率过高；

如果直接内存回收后，空闲的物理内存仍然不够用，就会触发OOM机制，OOM Killer机制会根据算法选择一个占用物理内存较高的进程，将其杀死，释放内存资源，如果不够，就继续杀，直到释放足够的内存位置；

要想保护进程不被OOM Killer杀死，可以调大进程的oom_score_adj参数，范围是-1000~1000参数，让该进程的得分尽可能的低，比如设置为-1000，永远不会被杀死；

可被回收的内存类型

文件页：内核缓存的磁盘数据（Buffer）和内核缓存的文件数据（Page Cache），回收时，如果是脏页，就会刷回磁盘，再回收内存，如果是干净页，则直接释放内存即可；
匿名页：这部分内存没有实际载体，比如堆、栈数据，这部分内存很可能还要再次被访问，所以不能直接释放，而是通过Swap机制，交换到磁盘，再释放内存，等到需要再次使用时，从磁盘加载回去；

回收都是基于LRU算法，优先回收不常访问的内存；

因为可能会涉及到磁盘IO，如果内存回收很频繁，就可能有性能问题，常见的解决方式有：

调整文件页和匿名页的回收倾向：比如回收文件页如果是干净页，不涉及磁盘IO，那就可以设置的比例大些，匿名页的比例小一些；
尽早触发kswapd内核线程异步回收内存，调整这个线程的触发配置；

关于预读失效和缓存污染问题

进程读取文件数据时，会对读取的文件数据进行缓存，缓存在文件系统的PageCache中，起到加速访问数据的作用。由于Page Cache的大小是有限的，对于一些频繁访问的数据希望可以一直留在内存中，很少访问的数据希望能在某些时机被淘汰掉，所以一般是使用LRU算法来实现，但是传统的LRU算法无法解决两个问题，预读失效和缓存污染。

预读失效

基于局部性原理，Page Cache读缓存机制会进行预读，当那些预读进来的，被提前加载进来的页，实际上并没有被访问到，此时预读失效，但是这些不会被访问到的预读的页却占用了LRU链表前排的位置，而末尾淘汰的页，可能是热点数据，这样就大大降低了缓存的命中率。

Linux的解决方式：使用两个LRU链表，一个活跃的，一个非活跃的，预读的时候，预读页就会加入到非活跃LRU链表的头部，当页被真正访问到的时候，才会插入活跃LRU链表的头部，如果预读页一直没有被访问，就会从非活跃链表中移除，这样就不会影响活跃链表中的热点数据。

缓存污染

如果数据被访问了一次，就将数据加入到活跃LRU链表中，只解决了预读失效的问题，缓存污染的问题还没解决，比如，当批量读取数据的时候，由于这些数据被访问了一次，被加入到活跃LRU链表中，导致之前缓存在活跃链表中的热点数据被淘汰了，但是这些新加入的数据，只被读取了一次，之后很长一段时间都不会被访问了，就导致这个活跃LRU链表一点都不活跃，就是被污染了，当之前的热点数据被再次访问的时候，又会产生大量的磁盘IO，导致性能下降。

Linux的解决方式：提高加入到活跃LRU链表的门槛，保证活跃链表中的热点数据不会被轻易替换掉。比如内存页第一次访问的时候还是加入非活跃链表，第二次被访问的时候，才将页从非活跃链表中升级到活跃链表中。

Linux内存管理

虚拟内存空间

32 位机器上进程虚拟内存空间分布：

保留区：不可访问，数值较小的地址通常认为是不合法的地址，比如设置无效的指针为NULL，就指向这里；
代码段、数据段、BSS段：存储程序的二进制文件中的机器码，以及定义的有初始值的全局变量、静态变量放在数据段、没有初始值的放在BSS段；
堆和待分配区域：堆空间地址增长从低地址到高地址增长，申请新内存时，只需移动堆顶指针到待分配区即可，从而实现空间扩展；
文件映射和匿名映射区域：进程运行所依赖的动态链接库中的代码段、数据段和BSS段就加载在这里，mmap函数映射出来的虚拟内存地址也保存在这；
栈和待分配区域：用户程序函数运行过程所需要的局部变量，函数参数等调用信息存放在此，栈空间地址增长方向是从高到低增长；

64位机器上进程用户态虚拟内存空间分布类似，用低48位表示虚拟地址，高16位的128T表示内核虚拟内存空间，低16位的128T表示用户虚拟内存空间，中间16位空闲地址被称为 canonical address作为空洞，可用来扩展或者做非法访问用；

通过 fork() 函数创建出的子进程，它的虚拟内存空间以及相关页表相当于父进程虚拟内存空间的一份拷贝，直接从父进程中拷贝到子进程中。子进程共享父进程的虚拟内存空间，这样的子进程也就是线程了，在Linux中都是使用 task_struct 来表示他们，因为对内核来说他们是一样的；

32位机器上内核虚拟内存空间，其前 896M 区域是直接映射到物理内存中的前 896M 区域中的，直接映射区中的映射关系是一比一映射。映射关系是固定的不会改变。主要存放进程的调用链。

直接映射区有896M，由以下几部分组成：

前1M由系统占用，存放内核代码段、数据段、BSS段；
前16M由内核用来为DMA分配内存，称为ZONE_DMA；
16M到896M称为ZONE_NORMAL区，没有任何限制；
物理内存896M以上的部分为高端内存区ZONE_HIGHMEM，这部分会动态映射到虚拟内存内核态剩余的128M里；这128M里还会继续分：
- 有8M的内存空洞；
- vmalloc动态映射区，映射剩余的物理内存；
- 永久映射区，允许这段虚拟地址空间与物理高端内存建立长期的映射关系；
- 固定映射区，在此区域的虚拟内存地址可以自由映射到物理内存的高端地址上，但是与动态映射区以及永久映射区不同的是，在固定映射区中虚拟地址是固定的，而被映射的物理地址是可以改变的；
- 临时映射区，比如一些缓存页临时映射，用完就回收；

伙伴系统

Linux使用分页机制管理物理内存系统，把物理内存分成4KB大小的页面进行管理，通过一个Page结构体表示一个物理内存页面。

因为硬件的限制，Linux把属性相同的物理内存页面，归结到一个区，不同的硬件，划分不同的区。在32位的x86平台中，将0~16MB划分位DMA区，高内存区适用于要访问的物理地址空间大于虚拟地址空间，Linux内核不能建立直接映射的情况。物理内存中剩余的页面就划分位常规内存区，64位的x86平台则没有高内存区。

在很多服务器和大型计算机上，如果物理内存是分布式的，由多个计算节点组成，那么每个 CPU 核都会有自己的本地内存，CPU 在访问它的本地内存的时候就比较快，访问其他 CPU 核内存的时候就比较慢，这种体系结构被称为 Non-Uniform Memory Access（NUMA）

在内存区的上层，通过定义节点pglist_data，来包含多个区

连续且相同大小的Page组成伙伴，Linux在分配物理内存页面时，首先找到内存节点，接着找到内存区，然后是合适的空闲链表，最后在其中找到页的Page结构，完成物理内存页面的分配。

内存压缩不是指压缩内存中的数据，而是指移动内存页面，进行内存碎片整理，腾出更大的连续的内存空间。如果内存碎片整理了，还是不能成功分配内存，就要杀死进程以便释放更多内存页面

分配算法：关键字：快速分配路径、慢速分配路径，只有在快速分配路径失败之后，才会进入慢速分配路径，慢速分配路径中会进行内存回收相关的工作。最后，通过 expand 函数分割伙伴，完成页面分配。

SLAB

Linux使用SLAB来分配比页更小的内存对象。

SLAB分配器会把一个内存页面或者一组连续的内存页面，划分成大小相同的块，每一小块内存就是SLAB对象，在这一组连续的内存页面中除了SLAB对象，还有SLAB管理头和着色区。

着色区是一块动态的内存块，建立SLAB时才会设置它的大小，目的是为了错开不同的SLAB对象地址，降低硬件Cache行中地址的争用，避免抖动产生的性能下降。

Linux使用kmen_cache结构管理page对应内存页面上的小块内存对象，然后让该 page 指向 kmem_cache，由 kmem_cache_node 结构管理多个 page。

进程

进程是一个应用程序运行时刻的实例，是应用程序运行时所需资源的容器，是一堆数据结构。操作系统记录这个应用程序使用了多少内存，打开什么文件，控制资源不可用时进行睡眠，进程运行到哪了等等这些统计信息，放到内存中，抽象成进程。

进程为了让操作系统管理，需要有一个地址空间，该地址空间至少包含两部分内容：内核和用户的应用程序。

当 CPU 在 R0 特权级运行时，就运行在内核的地址空间中，当 CPU 在 R3 特权级时，就运行在应用程序地址空间中。各进程的虚拟地址空间是相同的，它们之间物理地址不同，是由 MMU 页表进行隔离的，所以每个进程的应用程序的代码绝对不能随意访问内核的代码和数据。

每个进程都有一个内核栈，指向同一个块内核内存区域，共享一份内核代码和内核数据。内核进程使用一份页表，用户进程两份页表，用户进程多了一份用户空间页表，与其它用户进程互不干扰。

由于应用程序需要内核提供资源，而内核需要控制应用程序的运行，让其能随时中断或恢复执行，因此需要保存应用程序的机器上下文和它运行时刻的栈。使用内核的功能时，会先停止应用程序代码的运行，进入内核地址空间运行内核代码，然后返回结果。

进程的机器上下文分为几个部分，一部分是 CPU 寄存器，一部分是内核函数调用路径。CPU 的通用寄存器，是中断发生进入内核时，压入内核栈中的，从中断入口处开始调用的函数，都是属于内核的函数。函数的调用路径就在内核栈中，整个过程是这样的：进程调度器函数会调用进程切换函数，完成切换进程这个操作，而在进程切换函数中会保存栈寄存器的值。

建立进程，其实就是创建进程结构体，分配进程的内核栈于应用程序栈，并对进程的内核栈进行初始化，最后将进程加入调度系统，以便投入运行。

进程的状态

关于挂起状态，是描述进程没有占用实际的物理内存空间的情况，而阻塞状态是等待某个事件的返回；

阻塞挂起状态：进程在外存（硬盘）并等待某个事件的出现；
就绪挂起状态：进程在外存（硬盘），但只要进入内存，立刻运行；

导致进程挂起状态的原因不止是所用内存空间不再物理内存，还可能是sleep让进程间歇性挂起，或者用户希望挂起，比如ctrl + Z。

进程的通信方式

匿名管道：半双工，单向，数据只能向一个方向流动，双方需要通信时，需要建立起两个管道；且只能用于有父子关系的进程；本质是一个内核缓冲区，可以看成是内存中的文件，但不属于某种文件系统，无需显示打开，创建时直接返回文件描述符，读写时需要确定对方的存在，否则将退出；以先进先出的方式存取数据，通信的双方需制定好数据的格式；

管道 = 内核里一串缓存，管道内数据没有格式的流和大小限制，匿名管道比如Linux中的 命令A | 命令B，此时会在shell进程下创建两个子命令进程，形成父子关系，实现通信；
有名管道：主要解决匿名管道只能作用与有父子关系的进程的问题，通过一个路径名关联，以文件形式存在于文件系统中，即使没有亲缘关系的进程也能通过访问路径实现通信；管道名字存在于文件系统中，内容存在内存中；打开时就得确定对方是否存在，否则将阻塞；

有名管道不受父子关系限制，他是提前创建了一个类型为管道的设备文件，通过这个文件实现通信；

管道通信时，FIFO，需要有接收者，否则发送者会阻塞，无法退出，生命周期随进程；
信号：操作系统提供的一种异步通信机制，可以在任何时候发给某一进程，而无需指定该进程的状态，如果该进程当前处于未执行状态，该信号就由内核保存起来，直到进程回复执行并传递为止；信号接收可以被阻塞，直到阻塞解除；本质是对中断机制的模拟，异步通信，在用户态和内核态之间交互；能携带的信息较少。

信号是进程间通信机制中唯一的异步通信机制，进程需要注册对于的信号处理函数，进行信号处理，一般有三种响应方式：默认、捕捉、忽略；
消息队列：存放在内核中的消息链表，消息体由用户自定义，每个消息体都是固定大小的存储块，只有在内核重启或显示地删除时，才会被真正的删除，与管道不同的是消息队列不需要确定接收进程是否存在；一般是FIFO，但也可以实现成随机查询；对消息格式，缓冲区大小等都能进行控制，比管道灵活；消息队列通信的速度不是最及时的，因为每次数据的写入和读取都需要经过用户态与内核态之间的拷贝过程。

消息队列不适合较大数据的传输，且通信不够及时，因为消息队列存在内核，so存在用户态和内核态数据的拷贝开销；
共享内存：没什么好说的，只是在访问共享内存时要依靠一些同步或互斥机制保证并发访问安全；两个进程在虚拟内存拿出一块地址空间，映射到同一块物理内存中；
信号量：计数器，一般用于多进程对共享内存访问的保护，内核中实现，保证原子操作，主要实现进程间的互斥和同步，不用于数据通信；
Socket通信：通信机制，可用在本机或者跨网络，由域、端口号、协议类型三个属性确定；域分为AF_INET，即网络，另一个是AF_UNIX，即文件系统；

线程、进程、协程

进程：可以简单理解为一个应用程序，进程是资源分配的基本单位。比如一个进程拥有自己的堆、栈、虚存空间、文件描述符等。
线程：线程是独立调度的基本单位，由CPU进行调度和执行的实体。一个进程中可以有多个线程，线程之间共享进程资源，每个线程又各自有一套独立的寄存器和栈，确保线程的控制流是相对独立的，是进程中的实际运作单位，相当于进程中的一条执行流程。

优点：一个进程中可以同时存在多个线程，各个线程可以并发执行，各个线程可以共享地址空间和文件等资源；

缺点：大部分情况下，当进程中的一个线程崩溃时，会导致其所属进程的所有线程崩溃，因为所有线程共享进程资源，当有线程崩溃时，可能污染了共享资源，为了避免其他线程访问出错，就直接使得整个进程崩溃，线程崩溃的时候通过信号传递给进程；所以，如果不想让进程崩溃，那就得有对应的信号处理函数来实现崩溃后的操作。

线程间的通信：

同个进程下的线程之间都是共享进程的资源，只要是共享变量都可以做到线程间通信，比如全局变量，所以对于线程间关注的不是通信方式，而是关注多线程竞争共享资源的问题，信号量也同样可以在线程间实现互斥与同步
协程：GoLang中的协程
- 在用户态层面，由线程控制，即用户应用层面自己控制，很难像抢占式调度那样强制CPU切换到其他线程/进程，只能是协作式调度，但同时也避免了上下文切换
- 内存消耗比线程小，比如go开启协程是几kb，java开启一个线程至少1MB
- 实现原理：在一个运行的线程上，起多个协程，每个协程会加入到调度队列中，线程会从调度队列里取出协程进行运行。队列个数默认取决于CPU的个数，协程间的切换会线程使用go提供的io函数进行控制。当有协程执行较慢时，会先将其挂起，然后唤醒其他线程，将未处理的协程队列转移到该线程，消费队列里的协程，当队列消费完成后，再切回原来的线程，继续执行刚刚挂起的协程。

参考：图解Go协程调度原理，小白都能理解

Golang 的 goroutine 是如何实现的？

进程与线程的区别

拥有资源

进程是资源分配的基本单位，线程不拥有资源，线程可以访问隶属进程的资源。

共享的资源：内存分配页表，共享内存地址，文件资源，IO设备资源，全局变量

独享的资源：寄存器，栈
调度

线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。
系统开销

由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程因为会共享一些进程的资源，切换时只需保存和设置少量寄存器内容，开销很小，具体体现在：
- 线程的创建时间比进程快，因为进程在创建的过程中，还需要资源管理信息，比如内存管理信息、文件管理信息，而线程在创建的过程中，不会涉及这些资源管理信息，而是共享它们；
- 线程的终止时间比进程快，因为线程释放的资源相比进程少很多；
- 同一个进程内的线程切换比进程切换快，因为线程具有相同的地址空间（虚拟内存共享），这意味着同一个进程的线程都具有同一个页表，那么在切换的时候不需要切换页表。而对于进程之间的切换，切换的时候要把页表给切换掉，而页表的切换过程开销是比较大的；
- 由于同一进程的各线程间共享内存和文件资源，那么在线程之间数据传递的时候，就不需要经过内核了，这就使得线程之间的数据交互效率更高了；
- 线程有一个程序计数器（PC），记录程序从哪获取指令，每个线程有自己的一组用于计算的寄存器。如果有两个线程运行在一个CPU上，线程切换必定发生上下文切换；对于进程，进程状态保存在进程控制块（PCB），每一个线程的状态保存在线程控制块（TCB），每一个线程有自己的栈空间（ThreadLocal）；与进程相比，线程切换时，地址空间保持不变，即不需要保持切换当前使用的页表，
通信方面

线程间可以通过直接读写同一进程中的数据进行通信，无需经过内核。在java中如使用共享变量、wait/notify机制、阻塞队列；但是进程通信需要借助管道、消息队列、共享内存、信号量、信号、套接字socket
上下文切换的开销

操作系统的任务调度，实际上的调度对象是线程，而进程只是给线程提供了虚拟内存，全局变量等资源，当两个线程不属于同一个进程，切换过程跟进程上下文切换一样；当两个线程属于同一个进程，因为有共享资源和私有资源，在切换线程时，只需要切换私有数据、寄存器等不共享的数据即可，开销就会小很多。

线程与协程的区别

一个线程可以有多个协程，一个进程也可以有多个协程
协程不被操作系统内核管理，完全由程序控制；线程是被分割的CPU资源，协程是组织好的程序内的代码，协程不会直接使用线程，协程直接利用的是执行器关联任意线程或线程池
协程能保留上一次调用时的状态

协程本质上可以看作是可挂起和恢复的用户态轻量级线程，可以在没有多线程环境下模拟并发，也可以在多线程环境下代替系统线程降低切换消息，支持更多并发。

操作系统最小的执行单位是线程，进程是线程的容器，操作系统是进程的容器。

并发与并行

并发：多个任务被处理，但同一时刻，只有一个任务在执行。单核处理器也可以做到并发，比如CPU时间分片轮转执行。
并行：多个任务在同一时刻同时执行，需要多核处理器才能完成。

两个线程分别对全局变量 i++ 100 次，可能出现什么结果？-

调度模型

CPU同一时刻只能运行一个进程，当一个进程不能获取某种资源导致它不能继续运行时，就应该让出CPU，因此面对多进程就需要一个合理的调度。

进程的等待和唤醒可以通过信号量实现。

每一个CPU都有一个空转进程，作为进程调度器最后的选择。空转进程会调用进程调度函数，在系统没有其他进程可以运行时又会调用空转进程，形成闭环。

用户空间线程和内核空间线程之间的映射关系：

N:1模型：多个用户空间线程在1个内核空间线程上运行。优势是上下文切换非常快，因为这些线程都在内核态运行，但是无法利用多核系统的优点。

1:1模型：1个内核空间线程运行一个用户空间线程。这种充分利用了多核系统的优势但是上下文切换非常慢，因为每一次调度都会在用户态和内核态之间切换。POSIX线程模型(pthread)就是这么做的。

M:N模型：内核空间开启多个内核线程，一个内核空间线程对应多个用户空间线程。效率非常高，但是管理复杂。

调度的时机和方式

时机：

进程从一个运行状态到另一个状态变化，会触发一次调度；
硬件时钟提供某个频率的周期性中断；

方式：

非抢占式：系统一旦开始执行某一进程，就会让该线程就会一直执行下去，直至阻塞、完成、退出，或者发生了其他事件导致系统放弃对该进程的执行后，才会去执行另外一个进程；
抢占式：系统执行某一进程，在其执行期间，系统可以立即停止当前进程，转而执行另外一个进程，待处理完后，重新回来继续执行之前停止的进程。这种抢占式调度处理，需要再时间间隔末端发生时钟中断，以便把CPU控制返回给调度程序进行调度，即时间片机制；

调度原则

CPU 利用率：调度程序应确保 CPU 是始终匆忙的状态，这可提高 CPU 的利用率；比如发生IO事件造成的阻塞，调度程序就要从就绪队列选择另一个进程来运行；

系统吞吐量：吞吐量表示的是单位时间内 CPU 完成进程的数量，长作业的进程会占用较长的 CPU 资源，因此会降低吞吐量，相反，短作业的进程会提升系统吞吐量；

周转时间：周转时间是进程运行+阻塞时间+等待时间的总和，一个进程的周转时间越小越好；

完成时间 - 到达时间，即有A、B、C三个任务同时到达，且他们的运行时间都是10s，在FIFO调度算法下，周转时间就是10s，20s，30s

等待时间：这个等待时间不是阻塞状态的时间，而是进程处于就绪队列的时间，等待的时间越长，用户越不满意；理论上就绪队列里的进程是可执行，所以可以优先考虑；

响应时间：用户提交请求到系统第一次产生响应所花费的时间，在交互式系统中，响应时间是衡量调度算法好坏的主要标准。

调度算法

FCFS 先来先服务调度算法，其实就是FIFO

每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行，但会导致排在后面的短任务等待时间过长；
SJF 最短作业优先调度算法

优先选择运行时间最短的进程来运行，可能会导致运行时间长的任务饿死，理论上只有当作业都同时到达时，SJF是一个最优的调度算法，但是事实上作业不会同时到达，如果运行时间长的作业先到，就退化成了FIFO；
STCF 最短完成时间优先

基于时钟中断和上下文切换，在SJF的基础上实现抢占，避免退化成FIFO的问题；虽然STCF的周转时间最优，但是响应时间不是，那对于交互类型的程序就不够友好；

SJF和STCF算法的问题，都是先需要知道作业的运行时间，但实际上这个很难获得；
RR 时间片轮询调度算法

每个进程被分配一个时间段，称为时间片，允许该进程在该时间段中运行，时间到了就切换进程运行，该算法对时间片的设定比较严格，如果时间片过短，会导致频繁的进程上下文切换，过长又会导致短任务等待时间过长；通常时间片设定为20ms~50ms；RR算法优化了响应时间，但是周转时间最差；
HPF 最高优先级调度算法

对进程设定优先级，比如设置静态优先级（进程运行时确定），动态优先级（随时间更新优先级），根据优先级进行调度，可能会导致低优先级的任务永远不会被运行到；
MLFQ 多级反馈队列调度算法

结合时间片轮询 + 最高优先级调度的算法，兼顾长度任务和响应时间，比较均衡，算是平衡了上述算法的优缺点，不需要提前知道作业的运行时间，难点在于设置队列的数量、每层队列的时间片配额，多久提升一次进程的优先级。

设置多个队列，每个队列有不同的优先级，每个优先级有不同的运行时间，从高到低排序，优先级越高，时间片越少，每个作业只会存在于一个队列中，一个队列中的作业使用RR进行调度；

作业进入系统时，放在最高优先级队列，如果第一级队列规定的时间片没运行完成，就转入第二级队列，直至完成；高优先级队列为空，才去调度低优先级队列中的进程；

如果作业在其时间片内主动释放CPU，则优先级不变，但是当运行的时间累计达到规定的配额时(无论中间释放了多少次)，还是要降级，主要是解决一些交互程序或者IO操作造成的优先级垄断问题；

经过一段时间后，系统将所有工作重新加入最高级优先级队列，解决长时间运行的作业一直处于最低级导致饿死的问题；
比例份额调度

彩票调度：为每个运行的作业设置不同的权重值，通过生成随机数落在哪个范围来决定运行哪个作业，得益于随机数，理论上在长时间运行后终于趋向于我们一开始设置的比例，且不用需要额外的变量来存在进度，比较简便，缺点是如果在短作业或者运行次数较少的场景，随机数调度就不是很公平；

步长调度：为每个作业设置运行步长，每次运行对步长进行累加，每次运行步长累加值最小的那个，通过这种方式解决彩票调度的公平性问题，缺点是需要额外的变量来记录每个作业的步长；

这两种调度都面临的问题是如何设置一个合理的权重值或者步长值，且也无法很好的应付IO问题

在多CPU场景下，需要考虑多CPU的cache和内存间的一致性、亲和度和同步问题，又分为两种不同的调度：

SQMS单队列调度

多个CPU共享一个调度队列，优点是简单，CPU负载均衡，不需要太多修改，就能将原有的策略用在多CPU上，缺点是缺乏可扩展性，且多CPU在访问队列时，需要加锁保证并发安全，性能较差，另外，因为作业有可能被多次调度到不同的CPU上，CPU缓存亲和问题没有得到很好的保障。
MQMS多队列调度：

为每个CPU分配一个调度队列，每个CPU调度相互独立，每个调度可以选择不同的调度规则，避免单队列的方式导致的数据共享和同步问题；但需要解决负载不均衡的问题，一般是使用工作窃取算法解决；

互斥和同步

一些常见的操作需要多个指令来完成，因为CPU存在中断的缘故，可能会导致多个指令无法原子执行，产生并发安全问题；

进程状态的转换，共享变量的访问，都需要PV操作 + 信号量来控制，P表示请求资源，V表示释放资源，两者必须成对出现，一般利用信号量 + PV操作实现进程的互斥和同步。

flag + cas实现锁，cas对应CPU提供的原子操作指令 Test-and-Set（测试和置位）
信号量 + 原子的PV函数，信号量为1就是一个互斥锁了
生产者-消费者，由三个信号量实现（互斥信号量、消费者资源信号量，生产者信号量）

锁的实现

实现锁需要考虑几个点：

锁的基本功能是互斥，能阻止多个线程进入临界区，但不能简单的暂停中断（暂停中断只对单CPU机器有用，但是暂停中断会影响其他应用程序的中断信号，也会导致当前线程一直占有CPU，导致无法切换）
公平性，每个竞争线程释放有公平的机会抢到锁，竞争的锁是否会饿死
性能，当只有一个线程，即没竞争的时候，抢锁和解锁的开销；一个CPU上有多个线程竞争的性能开销；多个CPU上有多个线程竞争的性能开销；

基本原理：

硬件提供原子指令支持，有三种，测试并设置(test-and-set)、比较并交换(compare-and-swap)、获取并增加(fetch-and-add)；

使用这三种指令其中之一，即可实现一个简单的锁，没有获取锁的线程会进入自旋，这种实现方式只是实现了互斥，但不保证公平，自旋的线程在竞态条件下可能会永远自旋，导致饿死，其次，在单CPU场景下，性能较差，当有一个线程获取到锁后，其他线程运行时都自旋一个时间片，浪费CPU周期，但在多CPU场景下，性能就不错，因为有其他CPU分摊运行压力。

另外，如果使用获取并增加指令，就可以实现公平锁，原理是每个线程lock时，会fetch-and-add得到一个编号，自旋时比较该编号判断是否可以获取锁。
除了自旋可以等待，线程也可以主动让出CPU，比如调用os的yield()函数，最起码不会浪费CPU时间片，但是仍然会发生上下文切换，性能有提升，但不多；
使用队列 + 线程挂起休眠，实现公平，避免饿死（如果同时存在未入队的线程和存在队列里的线程时，需要保证队首线程被唤醒的优先权高一些，避免队列里的线程被饿死），同时也能减少自旋带来的消耗，提升性能；
二阶段锁，实际上就是上面两种方案的组合，自旋不是无限自旋，而是自旋一定的次数，如果还获取不到锁，就将线程挂起。

其他同步原语

条件变量：A线程要等到B线程执行完才能继续执行，可以使用全局变量 + A线程自旋的方式实现，但是这种方案会浪费CPU时间，最好的方式是让线程A休眠，因此可以使用条件变量的wait()和signal()，条件变量的原理是队列 + 锁，当有条件不满足时，让线程加入队列等待，直到被唤醒，wait()和signal()的语义均要求在使用时需要持有锁；
生产者/消费者（有界缓冲区）：通过消息队列解决并发问题，本质Broker + 锁 + 条件变量实现，要注意，通过条件变量进行唤醒和休眠，只是暗示了条件发生变化，不保证运行前后的运行状态是一致的，所以最好需要再次检查状态；另外，条件信号需要有指向性，消费者只能唤醒生产者，生产者只能唤醒消费者；
信号量：使用一个信号量时，信号量的值为1，可以模拟锁；值为0，可以模拟join()，也可以+条件实现条件变量；信号量本身可以通过锁 + 条件变量 + 值来实现；

并发安全问题的产生

非死锁缺陷：共享变量没有原子性操作，共享变量的访问顺序问题，均容易产生并发安全问题
死锁缺陷：主要是要避免凑齐死锁条件

死锁

只有同时满足以下四个条件才会发生：

互斥：对资源的访问需要先持有锁，比如一个线程抢到了锁
持有并等待：在等待下一个资源的时候，不会释放已持有的锁，比如线程已经持有了锁，但同时在等待其他资源
非抢占：已上锁的资源，在自己使用完之前不会被其他线程获取到，比如线程获取到锁后，这个锁不能被其他线程抢占
循环等待：多个线程获取资源的顺序形成了环形链

死锁避免：破坏死锁的任一条件：

互斥破坏：使用lock-free，不使用锁，比如cas，或者通过调度避免死锁，比如将线程固定调度到某一个CPU
持有并等待破坏：通过原子的抢锁来避免
非抢占破坏：使用tryLock()先判断
循环等待破坏：使用资源时有序分配，不让它形成环依赖（最常见的破坏条件）

银行家算法避免死锁：银行家算法主要是避免资源分配不导致死锁，需要提前知道每个线程的最大资源需求，实现资源分配表和进程资源分配表，当有线程请求或释放资源时，银行家算法通过查表判断是否有足够的资源可供分配，有则分配，没有则等待，只有通过安全检查，才允许操作，否则分配会被拒绝。

Linux进程调度

Linux进程调度支持多种调度算法：基于优先级的调度算法、实时调度算法、完全公平调度算法CFQ；也支持多种不同的进程调度器：RT调度器、Deadline调度器、CFS调度器、Idle调度器。

进程优先级越高，占有CPU时间越长；调度优先级越高，调度系统选中它的概率就越大。

Linux的CFS调度器没有时间片概念，它是直接分配CPU使用时间的比例。CFS会按权重比例分配CPU时间，权重表示进程优先级，进程时间 = CPU总时间 * 进程权重 / 就绪队列所有进程权重之和。对外接口提供一个nice值，范围为-20~19，数值越小，权重越大，每降低一个nice值，就能多获得10%的CPU时间。

对于非实时，优先级不高的任务，Linux使用CFS完全公平调度算法，实现任务的调度；这里任务指的是线程或进程。

CFS分配给每个任务的CPU时间是一样的，每个任务安排一次虚拟运行时间vruntime，如果一个任务运行得越久，该任务的vruntime值越大，而没有被运行的任务，vruntime不会变化，CFS在调度的时候，会根据权重值，优先选择vruntime少的任务，以保证每个任务的公平性。虚拟运行时间vruntime += 实际运行时间 * nice常量 / 权重（nice值越低，权重值越大，计算出来的vruntime就会越小；优先级的范围是0~139，其中0~99是给实时任务用，100~139给普通任务用，值越低，优先级越高，nice值的范围是-20~19，新优先级 = 旧优先级 + nice值）。

每个CPU都有自己的运行队列，用于描述此CPU上运行的所有进程，一般包含三个运行队列：DeadLine运行队列，RealTime实时运行队列，CFS运行队列（用红黑树描述），调度的优先级从大到小

设备I/O

操作系统本身会对设备进行分类，定义一套对应设备的操作接口，由设备的驱动程序实现，而驱动程序实现对应设备的操作，从而达到操作系统与设备解耦的目的。

设备和设备驱动的信息会抽象成对应的数据结构，再通过设备表结构组织驱动和设备的数据结构。

总线是设备的基础，表示CPU与设备的连接，总线本身也是一个数据结构。

一个驱动程序开始是由内核加载运行，然后调用由内核提供的接口建立设备，最后向内核注册设备和驱动，完成驱动和内核的握手动作。

内核要求设备执行某项动作，就会调用设备的驱动程序函数，把相关参数传递给设备的驱动程序，由于参数很多，各种操作所需的参数又不相同，就会把这些需要的参数封装在一个数据结构中，称为I/O包。

在Linux中，各种设备是一个个文件，只是并不对应磁盘上的数据文件，而是对应着存在内存当中的设备文件，对这些文件的操作等同于对设备的操作。在目录 /sys/bus目录下能看到所有总线下的所有设备，总线目录下有设备目录，设备目录下是设备文件。

**中断：**中断用于减少CPU的开销，让CPU不在需要不断轮询设备，而是向设备发送一个请求，让对应进程睡眠，切换执行其他任务。

一般用在需要长时间处理的慢速设备上使用，让CPU在中断的这段时间可以执行其他任务，而不用一直轮询等待，但如果短时间内出现大量的中断（比如网络接收数据包），会使得系统过载，CPU不断的处理中断，引发活锁，导致无法切换执行其他任务，一般的会使用短时间轮询 + 中断（多次中断合并）的混合策略；

中断处理流程：

在 I/O 时，设备控制器如果已经准备好数据，则会通过中断控制器向 CPU 发送中断请求；

保护被中断进程的 CPU 上下文；

转入相应的设备中断处理函数；

进行中断处理；

恢复被中断进程的上下文；

DMA（Direct Memory Access） ：让设备在 CPU 不参与的情况下，自行完成把设备 I/O 数据放入到内存，目的是减少CPU参与数据拷贝的时间，让CPU无需参与数据拷贝，因此这段时间可以执行其他任务。

需要有「DMA 控制器」硬件的支持。

DMA处理流程

从键盘敲入字母时，操作系统发生了什么？

当用户输入了键盘字符，键盘控制器就会产生扫描码数据，并将其缓冲在键盘控制器的寄存器中，紧接着键盘控制器通过总线给 CPU 发送中断请求。

CPU 收到中断请求后，操作系统会保存被中断进程的 CPU 上下文，然后调用键盘的中断处理程序。

键盘的中断处理程序是在键盘驱动程序初始化时注册的，那键盘中断处理函数的功能就是从键盘控制器的寄存器的缓冲区读取扫描码，再根据扫描码找到用户在键盘输入的字符，如果输入的字符是显示字符，那就会把扫描码翻译成对应显示字符的 ASCII 码，比如用户在键盘输入的是字母 A，是显示字符，于是就会把扫描码翻译成 A 字符的 ASCII 码。

得到了显示字符的 ASCII 码后，就会把 ASCII 码放到「读缓冲区队列」，接下来就是要把显示字符显示屏幕了，显示设备的驱动程序会定时从「读缓冲区队列」读取数据放到「写缓冲区队列」，最后把「写缓冲区队列」的数据一个一个写入到显示设备的控制器的寄存器中的数据缓冲区，最后将这些数据显示在屏幕里。

显示出结果后，恢复被中断进程的上下文。

文件系统

文件系统是操作系统为了兼容不同的物理存储设备而存在。

关于文件和目录

存储虚拟化一个是文件，另一个是目录；

文件就是一个线性字节数组，每个字节可以读取或写入，每个文件有一个低级名称 inode，通过硬链接将文件名称与inode号连接起来；

而目录则包含一个对（inode号，供用户可读的名称）的列表，将用户可读的名称映射到 inode 号上，这个对会指向其他文件或目录，从而构建成目录树；

常见文件系统的实现

文件系统会把文件数据定义成一个动态的线性字节数组，将一段范围的字节数组整合成一个文件数据逻辑块，再映射成对应存储设备的物理存储块，从而解决不同物理存储设备有不同的物理存储块的问题。即线性字节数组 -> 文件数据逻辑存储块 -> 物理存储块。

可以通过位图来标识哪些逻辑存储块是空闲，哪些是已被分配占用。

通过一个包含文件系统标识、版本、状态、存储介质大小、文件系统逻辑存储块大小、位图所在存储块、根目录等信息的数据结构，作为文件系统的超级块或文件系统描述块。

文件系统的格式化，指的是在存储设备上重建文件系统的数据结构，一般是先设置文件系统的超级块、位图、根目录，三者是强顺序的。

Linux使用VFS虚拟文件系统作为中间层，抽象了文件系统共有的数据结构和操作函数集合，一个物理存储设备的驱动只要实现了这些函数就可以插入VFS中，从而可以同时支持各种不同的文件系统。

VFS包含四大数据结构：

超级块结构super_block：用来存储文件系统详细信息，如块个数、块大小、空闲块、文件系统的信息、inode表的开始位置等；当文件系统被挂载时进入内存，初始化各自参数，将卷加到文件系统中，这样系统才知道在哪查找磁盘上的结构；
目录项dentry：用来记录文件的名字，索引节点指针，以及其他目录项的层级关系，多个目录项关联起来就形成目录结构；目录项由内核维护，缓存在内存中，不存放于磁盘；

目录与目录项不一样，目录是文件，持久化存在磁盘中，也通过inode访问，因为频繁查询目录需要读磁盘，效率低，所以内核就会把读过的目录用目录项缓存在内存，提升读取效率；
文件索引节点结构inode：记录文件元信息（如inode编号、文件类型、文件大小、分配给它的块数、时间信息、访问权限、数据在磁盘的位置等），是文件的唯一标识，被存储在磁盘中，可以理解为inode是文件名的ID，通常有一个隐式的id用于找到inode在磁盘的位置，再通过inode找到存储的数据；

与目录项是一对多的关系；

硬链接：与源文件是同一份文件，inode节点号相同；硬链接算是源文件的一个入口；只有当硬链接和对应的源文件都删除，文件实体才会被删除，所以可以通过设置硬链接防止重要文件被删；因为每个文件系统都有各自的inode数据结构和列表，所以硬链接不可用于跨文件系统。

软链接：独立文件，与源文件不是同一份文件，inode不同，类似快捷方式，存储源文件的位置信息，指向源文件；删除源文件，软连接依然存在，至少无法访问；软链接可以跨文件系统；
进程打开文件实例结构file

磁盘读写最小单位是扇区，每个扇区只有512B大小，文件系统把多个扇区组成一个逻辑块，作为读写的最小单位，Linux中逻辑块大小为4KB，也就是一次性读写8个扇区，提升读写效率；

磁盘格式化时，会分为三个存储区，分别是超级块，索引节点区和数据块区，超级块和索引节点只有被使用时才会加载进内存；

Liunx 挂载文件系统时，会读取文件系统超级块，将超级块加载进内存，从超级块出发读取并构造全部目录结构，目录结构指向存储设备文件时，是一个个文件索引节点结构，当文件被访问时，才被加载进内存，文件系统的基本操作单位是数据块，用户进程读写文件时使用字节，通过文件系统，操作对应的数据块，实现文件的读写。

文件的存储

文件的数据存放在磁盘上，就像程序在内存中存放的方式一样，有两种：

连续空间存放方式

文件存放在磁盘连续的物理空间中，文件数据紧密相连，读写效率高，一次磁盘寻道就能读出整个文件，但存放时必须先知道一个文件的大小，才能分配对应的空间；

但是有磁盘空间碎片和文件长度不易扩展的缺点；
非连续空间存放方式
- 链表方式：通过链表离散和不连续的特点，解决磁盘碎片问题和文件动态扩展问题，提升磁盘空间利用率，但不支持直接访问。
  - 隐式链表：文件头包含第一块和最后一块的位置，每个数据块里存放指向下一个数据块的指针；缺点在于无法直接访问数据块，只能通过指针顺序访问，同时每个数据块还要消耗空间存储指针，如果指针丢失或损坏，会导致文件数据丢失；
  - 显式链接：把隐式链表里每个数据块的指针存在一个链接表中，解决隐式链表的缺点；这个链接表，称为文件分配表，存储在内存中，提升检索速度，大大减少访问磁盘的次数，但不使用于大磁盘；
- 索引方式：通过为每个文件创建一个索引数据块，存放指向文件数据块的指针列表，存放在文件头中，相当于目录，解决链表方式无法直接访问的问题，同时也解决磁盘碎片和文件不易扩展的问题，因为会为文件设置索引数据，如果文件很大，索引数据块也很大，所以只适用于小文件。
- 链表 + 索引组合的方式，比如链式索引块（在索引数据块留一个存放指向下一个索引块的指针），多级索引块（索引之上再创建索引，形成多级索引）

空闲空间管理

进行空闲空间管理，主要是为了快速找到可用空间，进行写入。

空闲表法：

为空闲空间建立一张表，表内容包括空闲区的第一个块号和该空闲区的块个数。当请求分配磁盘空间时，系统依次扫描空闲表里的内容，直到找到一个合适的空闲区域；用户撤销文件时，系统回收文件空间，也需要顺序扫描空闲表，寻找一个空闲表条目并释放空间的第一个物理块，以及它占用的块数填到这个条目；

这种方法释放建立连续文件，如果是有大量空闲小空间，比较碎片，查找效率就很低；
空闲链表法：

通过链表阻止空闲块，一个空闲块通过指针指向下一块，但是这种方式无法随机访问，每当链上增加或移动空闲块时需要做很多IO操作，每个空闲块需要存储指针也浪费空间，不适合大型文件系统；
位图法：

磁盘上所有盘块都有一个二进制位与之对应，0表示空闲，1表示已分配，Linux就采用这种，空闲块使用位图，inode也使用位图；

目录存储

目录文件的块里保存的是目录里面一项一项的文件信息（如文件名、文件inode、文件类型等），组合成列表，列表每一项就代表该目录下的文件的文件名和对应的inode，通过这个inode，就能找到真正的文件。为了查找方便，目录的格式改成了哈希表。

目录查询如果通过在磁盘上反复搜索，就要不断进行IO，开销较大，所以一般是把文件目录缓存在内存，查找的时候在内存中查找，降低磁盘操作次数，提高文件系统的访问速度。

访问和写入

假设一个文件系统包含这5个部分：

超级块：包含该特定文件系统的信息，如有多少个inode和数据块，inode表开始的位置，标识文件系统类型的幻数；
数据位图：记录数据块区的空闲和分配标记的空间管理；
inode位图：记录inode块区的空闲和分配标记的空间管理；
inode块区：每个inode由一个数字 i-number 隐式引用，从而计算出磁盘上相应节点的位置，取到对应的inode信息；每个inode包含关于文件的信息，如文件类型（是常规文件还是目录）、大小、分配给他的块数、保护信息（谁拥有以及谁可以访问）、时间信息（文件创建、修改、上次访问时间）、有关其数据块驻留在磁盘上的位置（比如数据指向磁盘对应位置的指针）；

一个inode指向的数据块大小是有限的，如果文件特别大，通常可以给inode设置多级索引解决，比如有一个inode不是直接指向用户的数据块的，而是包含该文件涉及到的多个inode位置；
数据块区：用户数据、目录数据存储、inode数据存储的位置；

操作：

打开文件：
- 假设通过open("/foo/bar", O_RDONLY)打开文件，首先会找到目录文件对应的inode对应的i-number，一般来说，会存储在超级块中，便于操作系统挂载文件系统时就能知道，一般根的inode的i-number是2；
- 根据访问路径，从根目录开始遍历路径名，找到对应目录的inode及其目录数据块，最后找到对应文件的inode号，读入内存；
- 文件系统做最后的权限检查，在每个进程打开的文件列表中，为此进程分配一个文件描述符，并返回给用户；
- open导致的IO量与路径名的长度成正比，文件所在的位置越深，IO量越多；
读取文件：
- 打开文件后，程序可以发出read()系统调用，从文件中读取，第一次读取将在文件的第一个块中读取（第一次的偏移量是0），查阅inode以查找这个块的位置；
- 读取也会用新的最后访问时间更新inode，更新此文件描述符在内存中打开的文件表，更新文件偏移量，以便下一次读取第二个文件块，读取每个块需要文件系统首先查询inode，然后读取该块，再写入更新inode的最后访问时间字段，此时会发生多次磁盘IO；
- 文件打开后，每次读取时，会读一次文件inode，读一次文件数据，写一次文件inode；
写入文件：
- 打开文件后，程序可以发出write()系统调用，往文件写入数据，写入分为两种，一种是创建文件并写入，另一种是写入覆盖；
- 覆盖写入比较简单，打开文件后，读取一次文件inode，读取一次数据位图，写入一次文件数据，写入一次数据位图，写入一次文件inode；
- 写入一个新文件时，每次写入操作不仅需要将数据写入磁盘，还需要决定将哪个块分配给文件，不仅要分配一个inode，还要在包含新文件的目录中分配空间，从而相应的更新磁盘的其他结构，所以每次写入文件逻辑上会发生5个IO，如果目录需要增长以容纳新条目，则还需要额外的IO；
  
  创建文件基本的5个IO：
  1. 读取inode位图，查找空闲的inode；
  2. 写入inode位图，将新分配的块标记为已分配；写入新的inode（将它本身的信息写入数据块区），进行初始化；
  3. 读取新inode信息，写入新inode对应的目录数据，将文件的高级名称链接到它的inode号；
  4. 写入这个新inode的目录inode，进行更新；
  5. 之后才说真正的数据块写入；
关闭文件：
- 释放文件描述符，此时不会有磁盘IO发生；

为了解决读取和写入时产生的大量IO导致的性能问题，引入系统内存来缓存重要的块，从而提升性能，比如第一次打开可能会产生很多IO来读取目录的inode和数据，但随后打开同一文件或同一目录中的文件，会命中缓存，不用IO，从而提升性能；

系统内存会划分为静态内存和动态内存：

静态内存：划定固定大小的缓存，在启动时进行分配，但这可能会导致浪费，缓存策略跟虚拟内存差不多，也可以使用LRU等进行维护；
动态内存：将虚拟内存页面和文件系统页面集成到统一页面缓存中，从而可以灵活的分配；

缓存对写入的影响：

通过延迟写入，文件系统可以将一批数据放入一个IO中完成，或者创建一个文件，inode位图被更新，稍后在创建另一个文件时又被更新，文件系统会在第一次更新后延迟写入，从而节省一次IO 等场景，合并IO写入，从而提升性能，但在未写入磁盘时，如果系统发生崩溃，更新就会丢失，所以对于对数据完整性比较高的数据，就需要强制写入磁盘，通过调用fsync() 或使用绕过缓存的直接 IO接口或使用原始磁盘接口并完全避免使用文件系统写入；

文件IO

缓冲 I/O ：利用标准库的缓存实现文件加速访问，而标准库再通过系统调用访问文件；

非缓冲 I/O：直接通过系统调用访问文件，不经过标准库缓存；
直接 I/O ：不使用内核缓存和用户程序之间的数据复制，直接经过文件系统访问磁盘文件；

非直接 I/O：读操作时，数据从内核缓存中拷贝给用户程序，写操作时，数据从用户程序拷贝给内核缓存，再由内核决定什么时候写入数据到磁盘；

决定刷盘的时机：内核发现缓存数据太多；用户主动调用sync函数；内存使用紧张；内核缓存缓存时间超过某个时间点；
阻塞IO：读取数据时，线程被阻塞，直到内核数据准备好，并把数据从内核缓冲区拷贝到应用程序缓冲区，才能被读取；

阻塞等待指的是 **「内核数据准备好」和「数据从内核态拷贝到用户态」**这两个过程

非阻塞IO：读取数据时，当数据未准备好，就立即返回，继续往下执行；当数据准备好，内核将数据拷贝到应用程序缓冲区，就能读取数据，本质上都要同步等待，只是非阻塞IO不会一直等而已；

Page Cache

Page Cache 的本质是由 Linux 内核管理的内存区域。我们通过 mmap 以及 buffered I/O 将文件读取到内存空间实际上都是读取到 Page Cache 中。

page 是内存管理分配的基本单位， Page Cache 由多个 page 构成。page 在操作系统中通常为 4KB 大小（32bits/64bits），而 Page Cache 的大小则为 4KB 的整数倍。但并不是所有 page 都被组织为 Page Cache。

Page Cache 与 buffer cache 的区别：Page Cache 用于缓存文件的页数据，是针对文件系统的文件缓存，属于逻辑层，最终需要映射到实际的物理磁盘；buffer cache 用于缓存块设备（如磁盘）的块数据，也就是在没有文件系统的情况下，直接对磁盘进行操作的数据的缓存。

页是逻辑上的概念，因此 Page Cache 是与文件系统同级的；

块是物理上的概念，因此 buffer cache 是与块设备驱动程序同级的。

他们都是用来加速IO：

写数据时首先写到缓存，将写入的页标记为 dirty，然后向外部存储 flush，也就是缓存写机制中的 write-back（另一种是 write-through，Linux 默认情况下不采用）；

读数据时首先读取缓存，如果未命中，再去外部存储读取，并且将读取来的数据也加入缓存。操作系统总是积极地将所有空闲内存都用作 Page Cache 和 buffer cache，当内存不够用时也会用 LRU 等算法淘汰缓存页。

Linux 2.4 版本以前的内核，这两者是分开的，但因为块设备大多是磁盘，磁盘上的数据又大都通过文件系统来组织，就会导致很多数据被缓存了两次，浪费内存，所以2.4之后的版本就融合在一起，如果一个文件的页加载到了Page Cache，那么同时buffer cache只需要维护指向页的指针即可，只有那些没有文件表示的块，或者绕过文件系统直接操作的块，才会真正放到buffer cache里。

Page Cache预读：

用户线程仅仅请求读取磁盘上文件 A 的 offset 为 0-3KB 范围内的数据，由于磁盘的基本读写单位为 block（4KB），于是操作系统至少会读 0-4KB 的内容，这恰好可以在一个 page 中装下。

但是操作系统出于局部性原理会选择将磁盘块 offset [4KB,8KB)、[8KB,12KB) 以及 [12KB,16KB) 都加载到内存，于是额外在内存中申请了 3 个 page；

关于Page Cache与文件持久化一致性：

Write Through（写穿）：向用户层提供特定接口，应用程序可主动调用接口来保证文件一致性；只要上层一旦调用写入，数据落盘，就不会丢失数据。

Write back（写回）：系统中存在定期任务（表现形式为内核线程），周期性地同步文件系统中文件脏数据块，这是默认的 Linux 一致性方案；当系统宕机时无法保证数据落盘，就会丢失数据。

优势：

加快数据读取，读取数据时，直接读取内存中的缓存，不需要通过磁盘IO。

减少IO访问次数，提高系统磁盘IO吞吐量，利用Page Cache缓存和预读得能力，又因为程序往往符合局部性原理，一次IO将多个page装入Page Cache来减少磁盘IO次数，提升磁盘IO吞吐量。

劣势：

Page Cache需要占用额外物理内存空间，可能会导致swap操作，最终反而导致磁盘IO负载上升。

Page Cache在内核，但是对应用层没有提供很好得管理API，使得不能很好进行自定义优化，只能在用户空间实现自己的page管理，利用不到Page Cacge。

在某些场景下，会比Direct IO多一次磁盘读IO和磁盘写IO，Direct IO可以使得用户态读取文件直接与磁盘交互，无需使用Page Cache层。（比如利用DMA技术）

当进程使用缓冲IO写文件时，如果写到一半进程崩溃，已写入的数据不会丢失，因为调用系统调用写入文件时，先写到内核的Page Cache，如果进程崩溃，文件数据还保留在内核的Page Cache中，内核会找个合适的时机，将Page Cache中的数据持久化到磁盘，但是如果是Page Cache里的文件数据在持久化到磁盘之前，系统崩溃，那就有可能丢失文件数据了。

崩溃与一致性

以一个简单文件系统为例，简单文件系统包含超级块、数据位图、inode位图、inode区块、数据块区，一次写入涉及到多个IO，当崩溃发生时，可能有如下场景产生不一致：

只有数据块写入磁盘，此时由于其他区块还没写入，所以不会有什么影响；
只有更新后的inode区块写入磁盘，此时由于数据区块还没写入，inode指针指向的数据区块就有问题；
只有更新后的数据位图写入磁盘，由于没有inode指向数据区块，数据位图指向的数据区块永远不会有人使用，此时导致空闲空间泄露；
更新后inode区块和数据位图写入磁盘，但数据区块没有写入磁盘，inode指针指向的数据区块就有问题；
更新后的inode区块和数据块写入磁盘，但数据位图没有写入磁盘，会导致数据区块被覆盖；
更新后的数据位图和数据区块写入磁盘，但inode区块没有写入磁盘，由于没有inode指向数据区块，数据位图指向的数据区块永远不会有人使用，此时导致空闲空间泄露；

崩溃恢复：

fsck：文件系统检查程序，它是一款工具，会在文件系统写入数据到磁盘的多个阶段运行检查，比如检查超级块、空闲块、inode状态、inode链接、重复指针（两个不太的inode指向同一个数据块）、坏块、目录检查等，判断他们是否不一致，如果是，则会进行修复；

这种方案虽然能进行崩溃恢复，但是比较原始，实现上也比较复杂，需要知道文件系统的底层原理，而且每次检查需要扫描正规磁盘，速度太慢，特别是当只有少数几个数据有问题时，扫描整个盘只为修复这几个数据，代价就特别大了。
日志：通过在将用户数据写入磁盘的时候，将相关信息记录到日志并刷盘，以实现崩溃后通过日志信息进行恢复。日志需要记录几个方面的内容，如事务开始标志、inode信息、位图信息、用户数据、事务结束标志，但是，日志写入也是要刷盘的，本身也存在崩溃导致不一致的问题，所以需要保证事务结束写入时，前面四个信息已经写入完成（它们之间的顺序可以不用保证，但一定要发生在事务结束标志写入之前完成），可以利用磁盘提供的原子性保证（磁盘会以一定块的大小一起写入，比如每次写入512字节的块），为此有两种日志方案：
- 数据日志：
  1. 日志写入：将事务内容（事务开始标志、inode信息、位图信息、用户数据）写入日志，等待写入完成；
  2. 日志提交：将事务结束标志写入日志，等待写入完成，此时事务被认为已提交；
  3. 加检查点：此时可以把用户相关的元数据和用户数据写入最终的磁盘位置；
  4. 释放出空闲空间：通过更新日志中的超级块，在日志中标记该事务为空闲；
  崩溃恢复时，就可以扫描日志，恢复加检查点之前的数据了，将扫描的日志按顺序重放，文件系统尝试将事务中的块写入它们最终的磁盘位置（因为日志本身已经包含了用户数据了）
- 元数据日志：数据日志中，还要记录用户数据，但检查点之后，用户数据刷盘，用户数据又存入了一次，导致额外空间浪费和开销做出的改进，通过只调整日志写入顺序，只写入一次用户数据实现：
  1. 用户数据写入：将用户数据写入最终位置，等待完成；
  2. 日志元数据写入：将事务开始标志和元数据写入日志，等待写入完成；
  3. 日志提交：将事务结束标志写入日志，等待写入完成，此时事务被认为已提交，其实只要保证1和2两个步骤在3之前完成即可；
  4. 加检查点元数据：将元数据更新的内容写入文件系统最终位置；
  5. 释放出空闲空间：更新日志中的超级块，在日志中标记该事务为空闲；
  这种方案有个问题就是数据块区的复用，假如先有事务和用户数据文件写入同一目录，然后又删除，又创建了一个新文件，新文件可能复用了之前目录上的其他文件相同的块（块号一样，但旧数据可能还没被删除），由于是元数据日志，只记录新文件的元数据，当发生崩溃恢复时，可能会导致新文件元数据指向旧文件数据区块，所以，在删除操作发生后，元数据日志也需要将删除导致的撤销记录也写入到日志，避免这种问题的发生；
- 日志记录优化：
  - 批处理：写日志时，不会一次一个向磁盘提交每个更新，而是先写进缓存，攒一定的量，定时提交刷盘，从而避免对磁盘写入过多流量；
  - 轮转日志，避免日志文件大小膨胀，导致崩溃恢复时时间变长，也提升磁盘利用率。一般来说，一旦事务被加检查点，检查点之前的日志就允许被轮转了，此时在日志的超级块中标记日志的最新和最旧事务用于区分即可；
对文件系统的所有写入进行排序，确保磁盘上的结构永远不会处于不一致的状态，比如先写入数据区块，再写入对应的inode区块，确保inode永远不会指向错误等这样的规则，但是实现上会比较复杂；
写时复制Copy on Write，比如日志文件系统的实现；
反向指针：写入之间不强制执行排序，但是写入的数据块都要引用它所属的inode，访问文件时，文件系统可以检查正向指针是否指向引用它的块，从而确定文件是否一致；
日志 + 乐观崩溃一致性：尽可能多地向磁盘发出写入，事务写入日志时，在开始和结束块中包含日志内容的校验和，使得文件系统可以立即写入整个事务，而不用产生等待，崩溃恢复期间，利用事务校验和，检测文件是否一致；

日志文件系统的实现

日志文件系统的诞生基于以下几个原因：

内存大小不断增长，可用缓存变大，磁盘流量更多的由写入操作组成，磁盘的性能瓶颈取决于写性能；
读时发生随机IO无法避免，但写入时随机IO性能比顺序IO性能差太多；
如果使用之前的位图、inode区块、数据区块这种组成，会导致磁盘出现很多短寻道和旋转延迟，性能远低于峰值顺序带宽；

基于这几个原因，引入日志文件系统，简单来说，就是写入磁盘时，首先将所有更新（包括元数据）缓存在内存段中，当段满时，顺序写入磁盘，并传输到磁盘未使用部分，日志文件系统永远不会覆写现有数据，而是始终将段写入空闲的位置，由于段比较大，使得写入性能接近峰值；

文件写入磁盘之前，首先会写入内存，写入的内容包括用户数据、inode、地址引用等元数据，不断的累积写入的块，直到缓存大小达到规定的段大小时，将该段一次性写入磁盘（当有多次写入时通常是先排用户数据、再排元数据的顺序写入），段的大小跟磁盘的传输速率和定位开销有关，计算出一个越接近峰值带宽的写入大小；

由于这种写入会导致inode分散再整个磁盘上（不像上面的格式，inode存储在固定位置，可以比较简单算出数据的磁盘地址），所以除了必要的元数据以外，还需要记录一个imap，用于根据给定的i-number号找到对应的inode，从而找到对应的磁盘地址；imap就写在相关inode元数据的旁边（不能写在固定位置，因为每次写入都要更新，如果存在固定位置，就又要有旋转寻道带来的消耗了）；

而为了快速找到imap和inode，则会在固定的位置（检查点区域，存在在磁盘的头部和尾部两个地方，写入时是交替写入）存储inode范围映射，用于快速找到inode所在的磁盘的映射片段，检查点区域仅定期更新（比如每30s），因此性能不会太受影响；

所以在平时，会先查询检查点区域，将整个inode映射片段加载进缓存，当发生读取操作时，根据i-number在缓存里查找inode映射片段，磁盘选择到对应片段，根据i-number在imap找到inode，根据inode找到用户数据的磁盘地址，开始读取文件数据，甚至可以直接缓存所有imap，快速查找；

由于日志文件系统的特性，数据总是顺序写入，不会覆写现有数据，所以可能存在同一个inode指向两个用户数据块，此时就有新旧两个用户数据块了，对于用户数据块的写入会产生版本号，所以在这种常见下，可以根据版本号进行区分，同时也方便删除恢复，对于旧的用户数据块，日志文件系统会有定时任务，定时清理这些旧数据，清理时会按段清理，将里面存活的数据块打包移动到新位置，非存活的数据块则释放，恢复成空闲空间；（copy on write）

对于崩溃恢复，日志文件系统本身也需要写入日志来实现崩溃恢复，原理是利用头尾两个检查点区域，并在每个段写入时指向要写入的下一个段，为了保证更新检查点以原子的方式，每次写入时，交替写入头尾两个检查点区域，并带上时间戳，当崩溃恢复时，比较头尾两个检查点区域的内容是否一致，来判断检查点区域的一致性；对于写入数据时的原子性，由于检查点是定时更新，如果间隔时间太久，可能会导致丢失太多数据，因此使用前滚技术，基本思想是从最后一个检查点区域开始，找到日志尾部的检查点区域，读取它的下一段，判断其中是否包含任何有效的更新，如果有，则恢复来当前检查点以来写入的数据和元数据；

关于数据完整性

数据存储在磁盘中，可能会因为磁头碰撞、磁头没接触到磁盘等问题，导致数据位不可读；宇宙射线等使得数据位翻转，导致各自内容不正确；因为磁盘固件问题，导致数据写入错误的位置等问题

一般使用校验和的方式进行验证，将校验和与数据块一起存到磁盘中，从磁盘获取数据时，计算出摘要，与存储的校验和进行比较，从而判断数据的完整性，常见的校验和函数：

异或方案：比如对一个数据块每4个字节进行异或，最终得到一个值作为这块数据的校验和；
累加方案：计算每个数据块上指向二进制补码加法，忽略溢出，计算出校验和；
CRC循环冗余检测，也用于网络传输的数据校验：将数据的二进制数除于多项式的二进制数得到一个余数，这个余数就是CRC校验码；比如给定数据的二进制数为10110011，多项式为 G(x)=x^4+x^3+1（多项式为双方事先约定的），多项式对应的二进制数是 10000+1000+1=11001，两者相除，取余数，这里是取4位，得到0100，即为CRC效验码；

对于数据写错位置的，则可以在数据写入时，也把位置信息也写入校验和中，读取时，将读取位置参与到摘要计算中，对比校验和，从而知道读取的数据的正确性；

对于丢失写入，经典的方法是写入后立即读取，就能判断，但是这种方案非常慢，还伴随双倍的IO，成本巨大；其他方案的，比如在文件系统的每个inode和间接块中，包含文件每个块的校验和，这样即使对数据块本身的写入丢失，inode内的校验和也不会和旧数据匹配，但也仍然存在两者同时丢失的情况；

网络

在Linux中，替代传输层以上协议实体的标准接口，称为套接字，负责实现传输层以上的所有功能，即套接字是一套通用的网络API，下层由多个协议栈实现。

网络IO模型

I / O操作通常包含以下两个步骤：

等待网络数据到达网卡(读就绪) / 等待网卡可写(写就绪) –> 读取/写入到内核缓冲区
从内核缓冲区复制数据 –> 用户空间(读) / 从用户空间复制数据 -> 内核缓冲区(写)

判断一个I/O模型是同步还是异步，主要看第二步在复制数据时是否会阻塞当前进程，即CPU能不能去执行其他线程。

Unix网络中的5种 I/O 模型：

同步阻塞 I / O：一次IO，内数据没有准备好时，调用方法会阻塞等待，直至完成；
同步非阻塞 I / O：一次IO内，数据没有准备好时不断间隔轮询，等到数据准备好的结果后拷贝到用户态，在轮询的间隔期可执行其他操作；
I / O多路复用：一个管道阻塞监听所有IO，内核数据是否准备好，事件驱动，监听到数据准备好后拷贝数据到用户态，如select、poll、epoll；

I / O多路复用实际上就是在非阻塞I/O的基础上，增加一个线程同时监听多个文件描述符（I/O事件）阻塞等待，并在某个文件描述符可读写时收到通知，I / O复用并不是复用IO连接，而是复用线程，让一个线程可以同时处理多个连接（I/O事件）
同步信号驱动 I / O：注册回调函数，内核数据准备好后进行回调，在此期间系统可以做其他事情，数据准备阶段是异步，数据拷贝阶段是同步；
异步 I / O：真正的异步，数据的准备和拷贝都是自动完成；

I/O多路复用

select

特点：

可监控的文件描述符个数取决于 sizeof(fd_set) 的值，默认是1024。假设服务器上 sizeof(fd_set)＝512，每 bit 表示一个文件描述符，则服务器上支持的最大文件描述符是 512*8=4096。

将 fd 加入 select 监控集的同时，还要再使用一个数据结构 array 保存放到 select 监控集中的 fd，一是用于在 select 返回后，array 作为源数据和 fd_set 进行 FD_ISSET 判断，二是 select 返回后会把以前加入的但并无事件发生的 fd 清空，则每次开始 select 前都要重新从 array 取得 fd 逐一加入（FD_ZERO 最先），扫描 array 的同时取得 fd 最大值 maxfd，用于 select 的第一个参数。

所以select 模型必须在 select 前循环 array（加 fd，取 maxfd），select 返回后循环 array（FD_ISSET 判断是否有事件发生）

缺点：

fd_set有个数限制，最大并发数限制：使用 32 个整数的 32 位，即 32*32=1024 来标识 fd；

每次调用 select，都需要把 fd 集合从用户态拷贝到内核态，这个开销在 fd 很多时会很大；

性能衰减严重：每次 kernel 都需要线性扫描整个 fd_set，所以随着监控的描述符 fd 数量增长，其 I/O 性能会线性下降；

总结：

用户态有一个fd_set，是一个bitmap，表示要监听哪些fd；
调用select时，从用户态把fd_set全量复制到内核态，由内核态遍历整个fd_set来判断是否有数据到来，置位表示有数据，把fd_set返回给用户态；
用户态再遍历整个fd_set，和原始的fd_set比较，才知道哪个监听的fd是有数据的；

fd_set不可重用，处理完这个fd_set后，还得reset整个fd_set，之所以不可重用，是因为fd_set在select前后有两层语义，select前把要监听的fd置为1，select后把有数据fd的置为1；

内核遍历判断这个fd_set时是阻塞的；

poll

poll 的实现和 select 非常相似，只是描述 fd 集合的方式不同，poll 使用 pollfd 结构而不是 select 的 fd_set 结构；

poll 解决了最大文件描述符数量限制的问题，但是同样需要从用户态拷贝所有的 fd 到内核态，也需要线性遍历所有的 fd 集合，所以它和 select 只是实现细节上的区分，并没有本质上的区别。

总结：poll工作原理和select一样，只是对select做了一定优化，重新对fd做了一个包装，不再使用fd_set，而是使用pollfd，里面有events表示要监听的状态，revents表示内核实际收到的状态，解决fd_set不可重用的问题；另外，fd_set是一个bitmap，长度限制在1024，pollfd是个链表，长度上限就高很多了；

epoll

虽然原理差不多，但select&poll 错误预估了一件事，当数十万并发连接存在时，可能每一毫秒只有数百个活跃的连接，同时其余数十万连接在这一毫秒是非活跃的。当进程认为需要找出有报文到达的活跃连接时，就会调用select&poll，所以select&poll在高并发时会被频繁调用，如果全部待监控的连接数很多，但活跃连接很少，就会有效率问题了。

epoll优化了select性能开销很大，文件描述符数量少的问题。

实现上，epoll分清了高频和低频调用，内部存储分为两种：

一个是监听列表，使用红黑树存储所有监听的fd，每个插入或删除的fd性能稳定，插入时会为该fd注册一个回调函数，保证了每个fd在其生命周期只拷贝一次

一个是就绪列表，使用链表存储，阻塞监听。当fd就绪时，就会触发回调函数由内核调用，把就绪的fd放到就绪链表里。

epoll会去检查就绪链表，保证每次拿到的都是可用的fd，所以epoll不需要把全部监听的fd集合都从用户态拷贝到内核态，只需要拷贝已就绪的fd。

select&poll 调用时会将全部监听的 fd 从用户态空间拷贝至内核态空间并线性扫描一遍找出就绪的 fd 再返回到用户态，epoll 内的实现只会直接返回已就绪 fd，因此 epoll 的 I/O 性能不会像 select&poll 那样随着监听的 fd 数量增加而出现线性衰减，实现高效。

事件触发模式：

边缘触发模式（ET），当被监控的 Socket 描述符上有可读事件发生时，服务器端只会从 epoll_wait 中苏醒一次，即使进程没有调用 read 函数从内核读取数据，也依然只苏醒一次，因此我们程序要保证一次性将内核缓冲区的数据读取完；一般和非阻塞 I/O 搭配使用

水平触发模式（LT），当被监控的 Socket 上有可读事件发生时，服务器端不断地从 epoll_wait 中苏醒，直到内核缓冲区数据被 read 函数读完才结束，目的是告诉我们有数据需要读取；

epoll 支持边缘触发和水平触发的方式，而 select/poll 只支持水平触发，一般而言，边缘触发的方式会比水平触发的效率高。

零拷贝

传统的Linux的标准IO接口基于数据拷贝操作，IO操作会导致数据在操作系统内核地址空间的缓冲区和用户进程地址空间定义的缓冲区之间传输。设置缓冲区最大的好处是可以减少磁盘 I/O 的操作，而传统的 Linux I/O 在数据传输过程中深度依赖 CPU去执行数据拷贝的操作，系统开销极大，限制了操作系统有效进行数据传输操作的能力。比如一次读取磁盘文件，到写入网卡，数据的拷贝和上下文切换都由CPU来完成。

所以出现了DMA技术，DMA技术就是为了解决CPU过多参与IO带来资源浪费问题，让每个IO设备都有自己的DMA控制器，由DMA控制器参与数据传输工作，CPU仅用来接收通知，在进行 I/O 设备和内存的数据传输的时候，数据搬运的工作全部交给 DMA 控制器，而 CPU 不再参与任何与数据搬运相关的事情，这样 CPU 就可以去处理别的事务。

Linux中传统的IO读写通过read()/write()系统调用完成。read()把数据从存储器（磁盘、网卡）等读取到用户缓冲区，write()把数据从用户缓冲区写到存储器。一次读取磁盘文件，到写入网卡，中间一共触发了4次用户态和内核态的上下文切换，分别是read()/write()调用和返回时的切换，2次DMA拷贝（硬件与内核态之间）、2次CPU拷贝（用户态与内核态之间）。

零拷贝就是指在执行IO操作时，让数据拷贝直接发生在内核，从而节省CPU周期和内存带宽。零拷贝技术基于Page Cache，利用其预读提升缓存数据访问性能，解决机械硬盘寻址慢的问题。

作用：

减少甚至完全避免操作系统内核和用户应用程序地址空间这两者之间进行数据拷贝操作，从而减少用户态 – 内核态上下文切换带来的系统开销。

减少甚至完全避免操作系统内核缓冲区之间进行数据拷贝操作。

帮助用户进程绕开操作系统内核空间直接访问硬件存储接口操作数据。

利用 DMA 而非 CPU 来完成硬件接口和内核缓冲区之间的数据拷贝，从而解放 CPU，使之能去执行其他的任务，提升系统性能。

零拷贝只适合那些数据不需要在用户态做修改的数据传输。

实现方式：

减少甚至避免用户空间和内核空间之间的数据拷贝：数据拷贝直接在内核完成，不经过用户态。在一些场景下，用户进程在数据传输过程中并不需要对数据进行访问和处理，那么数据在 Linux 的 Page Cache 和用户进程的缓冲区之间的传输就完全可以避免，让数据拷贝完全在内核里进行，甚至可以通过更巧妙的方式避免在内核里的数据拷贝。这一类实现一般是通过增加新的系统调用来完成的，比如 Linux 中的 mmap()，sendfile() 以及 splice() 等。

绕过内核的直接 I/O：允许在用户态进程绕过内核直接和硬件进行数据传输，内核在传输过程中只负责一些管理和辅助的工作。这种方式其实和第一种有点类似，也是试图避免用户空间和内核空间之间的数据传输，只是第一种方式是把数据传输过程放在内核态完成，而这种方式则是直接绕过内核和硬件通信，效果类似但原理完全不同。

内核缓冲区和用户缓冲区之间的传输优化：这种方式侧重于在用户进程的缓冲区和操作系统的页缓存之间的 CPU 拷贝的优化。这种方法延续了以往那种传统的通信方式，但更灵活。