操作系统
 1. 硬件结构
 1.1. 冯-诺伊曼模型-计算机硬件
 1.1.1. 内存
 1.1.2. 中央处理器
 1.1.3. 总线
 1.1.4. 输入、输出设备
 1.2. 线路位宽与 CPU 位宽
 1.3. 指令
 2. 操作系统
 2.1. 内核
 2.2. 核心态与用户态
 3. 内存管理
 3.1. 虚拟内存
 3.2. 内存分段
 3.3. 内存分页
 3.3.1. 多级分表
 3.3.2. TLB
3.4. 段页式内存管理
 3.5. Linux 内存管理
 3.6. 两种分配内存的调用
 3.7. 内存分配过程
 3.7.1. 内存回收类型
 3.7.2. 内存回收优化
 3.7.3. OOM Killer
3.8. Swap机制
 4. 进程管理
 4.1. 进程
 4.2. 线程
 4.3. 线程与进程比较
 4.4. 上下文切换
 4.4.1. CPU上下文切换
 4.4.2. 进程上下文切换
 4.4.3. 线程上下文切换
 4.5. 处理器调度
 4.5.1. 调度基本原则
 4.5.2. 调度算法
 4.6. 进程通信
 4.6.1. 管道通信
 4.6.2. 消息队列
 4.6.3. 共享内存
 4.6.4. 信号量
 4.6.5. 信号
 4.6.6. Socket
4.7. 并发
 4.8. 经典同步问题
 4.8.1. 生产者-消费者问题
 4.8.2. 哲学家就餐问题
 4.8.3. 读者-写者问题
 4.9. 死锁
 4.10. 锁
 4.10.1. 互斥锁
 4.10.2. 自旋锁
 4.10.3. 读写锁
 4.10.4. 乐观锁与悲观锁
 5. 文件系统
 5.1. 文件系统组成
 5.2. 虚拟文件系统
 5.3. 文件使用
 5.4. 文件存储
 5.5. 文件系统结构
 5.6. 软链接和硬链接
 5.7. 文件/网络IO
5.7.1. 缓冲与非缓冲 I/O
5.7.2. 直接与非直接 I/O
5.7.3. 阻塞与非阻塞 I/O VS 同步与异步 I/O
5.7.4. IO多路复用
 5.7.4.1. select/poll
5.7.4.2. epoll
5.7.5. Reactor
5.7.6. Proactor
5.8. page cache
5.8.1. page与page cache
5.8.2. Page Cache 与 buffer cache
5.8.3. Page Cache 与预读
 5.8.4. 持久化的一致性&可靠性
 5.8.5. page cache 优劣势
 5.8.6. 参考资料
 5.9. 直接内存访问
 5.10. 零拷贝
 5.10.1. mmap + write
5.10.2. sendfile
计算机组成原理
 1. 局部性原理
 中间件设计资料

操作系统 [Top]

参考资料：大量参考=>小林coding-图解系统介绍

硬件结构 [Top]

冯-诺伊曼模型-计算机硬件 [Top]

计算机的硬件(或称为冯-诺伊曼模型)组成：

主机部分：运算器、存储器、控制器
外设部分：输入设备、输出设备

没有配置软件的计算机成为裸机，裸机仅仅构成了计算机系统的硬件基础。
计算机硬件、软件以及软件的各个部分是一种层次关系。硬件在最底层，其上层是操作系统。通过操作系统供的资源管理功能和方便用户使用的各种功能，把裸机改造成功能更加强大、使用更方便的机器(通常称为虚拟机)。

各种实用程序和应用程序在操作系统之上，这些程序都在均以操作系统作为支撑，并向用户提供各种服务。

内存 [Top]

我们的程序和数据都是存储在内存，存储的区域是线性的。

计算机最小的存储单位是字节(byte)，1 字节等于 8 位(8 bit)。每一个字节都对应一个内存地址。

内存的地址是从 0 开始编号的，然后自增排列，最后一个地址为内存总字节数 - 1，这种结构好似我们程序里的数组，所以内存的读写任何一个数据的速度都是一样的。

中央处理器 [Top]

央处理器也就是我们常说的 CPU，32 位和 64 位 CPU 最主要区别在于一次能计算多少字节数据：

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

32 位和 64 位，通常称为 CPU 的位宽。

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

CPU 内部还有一些组件，常见的有寄存器、控制单元和逻辑运算单元等。其中，控制单元负责控制 CPU 工作，逻辑运算单元负责计算，而寄存器可以分为多种类，每种寄存器的功能又不尽相同。

CPU 中的寄存器主要作用是存储计算时的数据，你可能好奇为什么有了内存还需要寄存器？原因很简单，因为内存离 CPU 太远了，而寄存器就在 CPU 里，还紧挨着控制单元和逻辑运算单元，自然计算时速度会很快。

常见的寄存器种类：

通用寄存器，用来存放需要进行运算的数据，比如需要进行加和运算的两个数据。
程序计数器，用来存储 CPU 要执行下一条指令「所在的内存地址」，注意不是存储了下一条要执行的指令，此时指令还在内存中，程序计数器只是存储了下一条指令的地址。
指令寄存器，用来存放程序计数器指向的指令，也就是指令本身，指令被执行完成之前，指令都存储在这里。

总线 [Top]

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

地址总线，用于指定 CPU 将要操作的内存地址；
数据总线，用于读写内存的数据；
控制总线，用于发送和接收信号，比如中断、设备复位等信号，CPU 收到信号后自然进行响应，这时也需要控制总线；

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

首先要通过「地址总线」来指定内存的地址；
然后通过「控制总线」控制是读或写命令；
最后通过「数据总线」来传输数据；

输入、输出设备 [Top]

输入设备向计算机输入数据，计算机经过计算后，把数据输出给输出设备。期间，如果输入设备是键盘，按下按键时是需要和 CPU 进行交互的，这时就需要用到控制总线了。

线路位宽与 CPU 位宽 [Top]

数据是如何通过线路传输的呢？其实是通过操作电压，低电压表示 0，高压电压则表示 1。

如果构造了高低高这样的信号，其实就是 101 二进制数据，十进制则表示 5，如果只有一条线路，就意味着每次只能传递 1 bit 的数据，即 0 或 1，那么传输 101 这个数据，就需要 3 次才能传输完成，这样的效率非常低。这样一位一位传输的方式，称为串行，下一个 bit 必须等待上一个 bit 传输完成才能进行传输。

为了避免低效率的串行传输的方式，线路的位宽最好一次就能访问到所有的内存地址。

CPU 要想操作的内存地址就需要地址总线：

如果地址总线只有 1 条，那每次只能表示「0 或 1」这两种地址，所以 CPU 能操作的内存地址最大数量为 2(2^1)个(注意，不要理解成同时能操作 2 个内存地址)；
如果地址总线有 2 条，那么能表示 00、01、10、11 这四种地址，所以 CPU 能操作的内存地址最大数量为 4(2^2)个。

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

对于 64 位 CPU 就可以一次性算出加和两个 64 位数字的结果，因为 64 位 CPU 可以一次读入 64 位的数字，并且 64 位 CPU 内部的逻辑运算单元也支持 64 位数字的计算。但是并不代表 64 位 CPU 性能比 32 位 CPU 高很多，很少应用需要算超过 32 位的数字，所以如果计算的数额不超过 32 位数字的情况下，32 位和 64 位 CPU 之间没什么区别的，只有当计算超过 32 位数字的情况下，64 位的优势才能体现出来。

指令 [Top]

流水线的方式来执行指令: Fetch -> Decode -> Execution -> Store

指令周期(Instruction Cycle)：CPU 的工作就是一个周期接着一个周期，周而复始。

四个阶段的具体含义：

CPU 通过程序计数器读取对应内存地址的指令，这个部分称为 Fetch(取得指令)；
CPU 对指令进行解码，这个部分称为 Decode(指令译码)；
CPU 执行指令，这个部分称为 Execution(执行指令)；
CPU 将计算结果存回寄存器或者将寄存器的值存入内存，这个部分称为 Store(数据回写)；

不同的阶段其实是由计算机中的不同组件完成的：

取指令的阶段，我们的指令是存放在存储器里的，实际上，通过程序计数器和指令寄存器取出指令的过程，是由控制器操作的；
指令的译码过程，也是由控制器进行的；
指令执行的过程，无论是进行算术操作、逻辑操作，还是进行数据传输、条件分支操作，都是由算术逻辑单元操作的，也就是由运算器处理的。但是如果是一个简单的无条件地址跳转，则是直接在控制器里面完成的，不需要用到运算器。

指令的执行速度

程序CPU的运行时间 = CPU 时钟周期数(CPU Cycles) * 时钟周期时间(Clock Cycle Time)

时钟周期时间：就是CPU主频，主频越高说明CPU的工作速度就越快。2.4GHz就是电脑的主频，时钟周期时间就是 1/2.4G。

CPU时钟周期数可以进一步拆解成：CPU时钟周期数 = 指令数 * 每条指令的平均时钟周期数(Cycles Per Instruction，简称 CPI)

指令数：表示执行程序所需要多少条指令，以及哪些指令。这个层面是基本靠编译器来优化。
每条指令的平均时钟周期数 CPI：表示一条指令需要多少个时钟周期数，现代大多数 CPU 通过流水线技术(Pipeline)，让一条指令需要的 CPU 时钟周期数尽可能的少；
时钟周期时间：表示计算机主频，取决于计算机硬件。

操作系统 [Top]

操作系统是裸机上的第一层软件，是对硬件功能的首次扩充。引入操作系统的目的：

提供一个计算机用户和计算机硬件系统之间的接口，使计算机易于使用。
有效的控制和管理计算机系统中的中硬件和软件资源，使之得到更有效的利用。
合理地组织计算机系统的工作流程，以改善系统性能。

操作系统的特征：

并发性：
- 并行性：指两个或多个事件在同一时刻发生。宏观上在一段时间内有多道程序同时运行，但单处理器其实是交替运行，故微观上是交替执行。
- 并发性：指两个或多个事件在同一时间间隔内发生。如哲学家思考和用餐是可以同时进行的，即两个任务并行执行。
共享性。资源共享是指系统中的硬件和软件不再为某个程序所独占，而是供多个用户共同使用的。
- 互斥共享：系统中可供共享的某些资源，一段时间内只能供一个作业使用。如打印机、队列等。
- 同时访问：系统中另一类资源如磁盘、可重入代码，可以供多个作业同时访问。
并发和共享是操作系统最基本的特征，二者互为存在的条件。一方面，资源共享是以程序并发执行为条件的。另一方面，若系统不能对共享资源进行有效管理，会影响到程序的并发执行。
虚拟性：操作系统中，虚拟指的是一个物理上的实体变为若干个逻辑上的对应物，前者是实际存在的，而后者是虚拟的。
异步性

操作系统基本功能

处理器管理
存储器管理
设备管理
文件管理
用户接口

内核 [Top]

内核的作用主要是：作为应用连接硬件设备的桥梁，应用程序只需关心与内核交互，不用关心硬件的细节。

现代操作系统，内核一般会提供 4 个基本能力：

管理进程、线程，决定哪个进程、线程使用 CPU，也就是进程调度的能力；
管理内存，决定内存的分配和回收，也就是内存管理的能力；
管理硬件设备，为进程与硬件设备之间提供通信能力，也就是硬件通信能力；
提供系统调用，如果应用程序要运行更高权限运行的服务，那么就需要有系统调用，它是用户程序与操作系统之间的接口。

对于内核的架构一般有这三种类型：

宏内核，包含多个模块，整个内核像一个完整的程序；
微内核，有一个最小版本的内核，一些模块和服务则由用户态管理；微内核架构的内核只保留最基本的能力，比如进程调度、虚拟机内存、中断等，把一些应用放到了用户空间，比如驱动程序、文件系统等。
混合内核，是宏内核和微内核的结合体，内核中抽象出了微内核的概念，也就是内核中会有一个小型的内核，其他模块就在这个基础上搭建，整个内核是个完整的程序；

微内核内核功能少，可移植性高，相比宏内核有一点不好的地方在于，由于驱动程序不在内核中，而且驱动程序一般会频繁调用底层能力的，于是驱动和硬件设备交互就需要频繁切换到内核态，这样会带来性能损耗。华为的鸿蒙操作系统的内核架构就是微内核。

Linux 的内核设计是采用了宏内核，Window 的内核设计则是采用了混合内核。这两个操作系统的可执行文件格式也不一样， Linux 可执行文件格式叫作 ELF，Windows 可执行文件格式叫作 PE。

内核是怎么工作的？

内核具有很高的权限，可以控制 cpu、内存、硬盘等硬件，而应用程序具有的权限很小，因此大多数操作系统，把内存分成了两个区域：

内核空间，这个内存空间只有内核程序可以访问；
用户空间，这个内存空间专门给应用程序使用；

核心态与用户态 [Top]

用户空间的代码只能访问一个局部的内存空间，而内核空间的代码可以访问所有内存空间。因此，当程序使用用户空间时，我们常说该程序在用户态执行，而当程序使内核空间时，程序则在内核态执行。应用程序如果需要进入内核空间，就需要通过系统调用。

内核程序执行在内核态，用户程序执行在用户态。当应用程序使用系统调用时，会产生一个中断。发生中断后， CPU 会中断当前在执行的用户程序，转而跳转到中断处理程序，也就是开始执行内核程序。内核处理完后，主动触发中断，把 CPU 执行权限交回给用户程序，回到用户态继续工作。

为了避免操作系统及其关键数据(如PCB等)收到用户程序有意或无意的破坏，通常将处理器的执行状态分为两种：核心态和用户态。

核心态(管态、系统态)：是操作系统管理程序执行时机器所处的状态。具有较高的权限，能执行包括特权指令等一切的指令，能访问所有寄存器和存储区。
用户态(目态)：是用户程序执行时机器所处的状态，具有较低特权的执行状态，它只能执行规定的指令，只能访问指定的寄存器和存储区。

特权指令：只能由操作系统内核部分使用，不允许用户直接使用的指令，如I/O指令、设置中断屏蔽指令、清内存指令、存储保护指令和设置时钟指令。

用户态程序不能直接调用核心态程序，而是通过执行访问核心态的命令，引起中断，由中断系统传入操作系统相关的程序，例如在系统调用时，由用户态转核心态。

内核的指令操作工作在核心态，主要以下几个方面：

时钟管理。向用户提供标准的系统时间。通过时钟中断的管理，可以实现进程的切换，如时间片轮转调度。
中断机制。中断机制中，只有一小部分属于内核，负责保护和恢复中断现场的信息，转移控制权到相关的处理程序中。(键盘鼠标的输入、进程的管理和调度、设备驱动、文件访问)
原语。原语是一些关闭中断的公用小程序。
- 处于操作系统最底层，是最接近硬件的部分。
- 程序执行具有原子性。
- 这些程序的运行时间较短，调用频繁。
系统控制的数据结构及处理。如进程控制块、缓存区、内存分配表。

系统调用(System call):系统调用把用户程序的请求传到内核，调用相应的内核函数完成所需的处理，并将处理结果返回给对应的应用程序。

操作系统提供的系统调用通常包括：进程管理、文件系统控制(文件读写操作和文件系统操作)、系统控制、内存管理、网络控制、socket控制、用户管理及进程间通信(信号、消息、管道、信号量和共享内存)

内存管理 [Top]

虚拟内存 [Top]

单片机是没有操作系统的，所以每次写完代码，都需要借助工具把程序烧录进去，这样程序才能跑起来。

单片机的 CPU 是直接操作内存的物理地址。常见的单片机程序就是跑马灯了，通过控制高低电平，循环及等待进而控制LED灯的亮暗。

由于单片机直接操作的是系统内存，在这种情况下，要想在内存中同时运行两个程序是不可能的。如果第一个程序在 2000 的位置写入一个新的值，将会擦掉第二个程序存放在相同位置上的所有内容，所以同时运行两个程序是根本行不通的，这两个程序会立刻崩溃。

操作系统会提供一种机制，将不同进程的虚拟地址和不同内存的物理地址映射起来。

如果程序要访问虚拟地址的时候，由操作系统转换成不同的物理地址，这样不同的进程运行的时候，写入的是不同的物理地址，这样就不会冲突了。

于是，这里就引出了两种地址的概念：

我们程序所使用的内存地址叫做虚拟内存地址(Virtual Memory Address)
实际存在硬件里面的空间地址叫物理内存地址(Physical Memory Address)。

操作系统引入了虚拟内存，进程持有的虚拟地址会通过 CPU 芯片中的内存管理单元(MMU)的映射关系，来转换变成物理地址，然后再通过物理地址访问内存。

操作系统是管理虚拟地址与物理地址，主要有两种方式，分别是内存分段和内存分页

内存分段 [Top]

程序是由若干个逻辑分段组成的，如可由代码分段、数据分段、栈段、堆段组成。不同的段是有不同的属性的，所以就用分段(Segmentation)的形式把这些段分离出来。

分段机制下的虚拟地址由两部分组成，段选择因子和段内偏移量。

段选择子就保存在段寄存器里面。段选择子里面最重要的是段号，用作段表的索引。段表里面保存的是这个段的基地址、段的界限和特权等级等。
虚拟地址中的段内偏移量应该位于 0 和段界限之间，如果段内偏移量是合法的，就将段基地址加上段内偏移量得到物理内存地址。

分段机制会把程序的虚拟地址分成 4 个段，每个段在段表中有一个项，在这一项找到段的基地址，再加上偏移量，于是就能找到物理内存中的地址。但它也有一些不足之处：

第一个就是内存碎片的问题。
第二个就是内存交换的效率低的问题。

存在两部分的内存碎片

外部内存碎片，也就是产生了多个不连续的小物理内存，导致新的程序无法被装载；
内部内存碎片，程序所有的内存都被装载到了物理内存，但是这个程序有部分的内存可能并不是很常使用，这也会导致内存的浪费；

解决外部内存碎片的问题就是内存交换:
可以把音乐程序占用的那 256MB 内存写到硬盘上，然后再从硬盘上读回来到内存里。不过再读回的时候，我们不能装载回原来的位置，而是紧紧跟着那已经被占用了的 512MB 内存后面。这样就能空缺出连续的 256MB 空间，于是新的 200MB 程序就可以装载进来。
这个内存交换空间，在 Linux 系统里，也就是我们常看到的 Swap 空间，这块空间是从硬盘划分出来的，用于内存与硬盘的空间交换。

分段为什么会导致内存交换效率低的问题？

对于多进程的系统来说，用分段的方式，内存碎片是很容易产生的，产生了内存碎片，那不得不重新 Swap 内存区域，这个过程会产生性能瓶颈。如果内存交换的时候，交换的是一个占内存空间很大的程序，这样整个机器都会显得卡顿。

内存分页 [Top]

分段的好处就是能产生连续的内存空间，但是会出现内存碎片和内存交换的空间太大的问题。

内存分页(Paging): 分页是把整个虚拟和物理内存空间切成一段段固定尺寸的大小。这样一个连续并且尺寸固定的内存空间，称为页(Page)。在 Linux 下，每一页的大小为4KB。

当需要进行内存交换的时候，让需要交换写入或者从磁盘装载的数据更少一点

虚拟地址与物理地址之间通过页表来映射
页表是存储在内存里的，内存管理单元(MMU)就做将虚拟内存地址转换成物理地址的工作。

而当进程访问的虚拟地址在页表中查不到时，系统会产生一个缺页异常，进入系统内核空间分配物理内存、更新进程页表，最后再返回用户空间，恢复进程的运行。

分页是怎么解决分段的内存碎片、内存交换效率低的问题？

由于内存空间都是预先划分好的，也就不会像分段会产生间隙非常小的内存，这正是分段会产生内存碎片的原因。而采用了分页，那么释放的内存都是以页为单位释放的，也就不会产生无法给进程使用的小内存。

换出(Swap Out): 如果内存空间不够，操作系统会把其他正在运行的进程中的「最近没被使用」的内存页面给释放掉，也就是暂时写在硬盘上。
换入(Swap In): 将从内存页面释放而暂存在硬盘上的数据，重新加载进来。

内存分页相比内存分段好处:

对于需要内存交换的情况，一次性写入磁盘的也只有少数的一个页或者几个页，不会花太多时间，内存交换的效率就相对比较高。
分页的方式使得我们在加载程序的时候，不再需要一次性都把程序加载到物理内存中。我们完全可以在进行虚拟内存和物理内存的页之间的映射之后，并不真的把页加载到物理内存里，而是只有在程序运行中，需要用到对应虚拟内存页里面的指令和数据时，再加载到物理内存里面去。

在分页机制下，虚拟地址分为两部分，页号和页内偏移。页号作为页表的索引，页表包含物理页每页所在物理内存的基地址，这个基地址与页内偏移的组合就形成了物理内存地址

多级分表 [Top]

对于一个内存地址转换，简单的三个步骤总结：

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

简单分页管理的缺陷？在 32 位的环境下，虚拟地址空间共有 4GB，假设一个页的大小是 4KB(2^12)，那么就需要大约 100 万 (2^20) 个页，每个「页表项」需要 4 个字节大小来存储，那么整个 4GB 空间的映射就需要有 4MB 的内存来存储页表。
这 4MB 大小的页表，看起来也不是很大。但是要知道每个进程都是有自己的虚拟地址空间的，也就说都有自己的页表。
那么，100 个进程的话，就需要 400MB 的内存来存储页表，这是非常大的内存了，更别说 64 位的环境了。

多级页表(Multi-Level Page Table)
在 32 位和页大小 4KB 的环境下，一个进程的页表需要装下 100 多万个「页表项」，并且每个页表项是占用 4 字节大小的，于是相当于每个页表需占用 4MB 大小的空间。
我们把这个 100 多万个「页表项」的单级页表再分页，将页表(一级页表)分为 1024 个页表(二级页表)，每个表(二级页表)中包含 1024 个「页表项」，形成二级分页。

进一步节省内存方案：如果某个一级页表的页表项没有被用到，也就不需要创建这个页表项对应的二级页表了，即可以在需要时才创建二级页表。

做个简单的计算，假设只有 20% 的一级页表项被用到了，那么页表占用的内存空间就只有 4KB(一级页表) + 20% * 4MB(二级页表)= 0.804MB，这对比单级页表的 4MB 是不是一个巨大的节约？

对于 64 位的系统，两级分页肯定不够了，就变成了四级目录，分别是：

全局页目录项 PGD(Page Global Directory)
上层页目录项 PUD(Page Upper Directory)
中间页目录项 PMD(Page Middle Directory)
页表项 PTE(Page Table Entry)

TLB [Top]

多级页表虽然解决了空间上的问题，但是虚拟地址到物理地址的转换就多了几道转换的工序，这显然就降低了这俩地址转换的速度，也就是带来了时间上的开销。

程序是有局部性的，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域。

TLB(Translation LookAside Buffer): 在 CPU 芯片中，加入了一个专门存放程序最常访问的页表项的 Cache，通常称为页表缓存、转址旁路缓存、快表等。

在 CPU 芯片里面，封装了内存管理单元(Memory Management Unit)芯片，它用来完成地址转换和 TLB 的访问与交互。有了 TLB 后，那么 CPU 在寻址时，会先查 TLB，如果没找到，才会继续查常规的页表。

段页式内存管理 [Top]

内存分段和内存分页并不是对立的，它们是可以组合起来在同一个系统中使用的，那么组合起来后，通常称为段页式内存管理。

段页式内存管理实现的方式：

先将程序划分为多个有逻辑意义的段，也就是前面提到的分段机制；
接着再把每个段划分为多个页，也就是对分段划分出来的连续空间，再划分固定大小的页；这样，地址结构就由段号、段内页号和页内位移三部分组成。

用于段页式地址变换的数据结构是每一个程序一张段表，每个段又建立一张页表，段表中的地址是页表的起始地址，而页表中的地址则为某页的物理页号

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

第一次访问段表，得到页表起始地址；
第二次访问页表，得到物理页号；
第三次将物理页号与页内位移组合，得到物理地址。

Linux 内存管理 [Top]

Linux 内存主要采用的是页式内存管理，但同时也不可避免地涉及了段机制。这主要是Intel 处理器发展历史导致的

Linux 系统中的每个段都是从 0 地址开始的整个 4GB 虚拟空间(32 位环境下)，也就是所有的段的起始地址都是一样的。这意味着，Linux 系统中的代码，包括操作系统本身的代码和应用程序代码，所面对的地址空间都是线性地址空间(虚拟地址)，这种做法相当于屏蔽了处理器中的逻辑地址概念，段只被用于访问控制和内存保护。

每个进程都各自有独立的虚拟内存，每个虚拟内存中的内核地址，其实关联的都是相同的物理内存。进程切换到内核态后，就可以很方便地访问内核空间内存。

看看用户空间分布的情况，以 32 位系统为例。其中用户态的分布：代码段、全局变量、BSS、函数栈、堆内存、映射区。

两种分配内存的调用 [Top]

C 库里的函数malloc()，用于动态分配内存。malloc 申请内存的时候，会有两种方式向操作系统申请堆内存。

通过 brk() 系统调用从堆分配内存。类似与碰撞指针，直接用指针移位表示内存占用。
通过 mmap() 系统调用在文件映射区域分配内存；

malloc 申请的内存，free 释放内存会归还给操作系统吗？

malloc 通过 brk() 方式申请的内存，free 释放内存的时候，并不会把内存归还给操作系统，而是缓存在 malloc 的内存池中，待下次使用；
malloc 通过 mmap() 方式申请的内存，free 释放内存的时候，会把内存归还给操作系统，内存得到真正的释放。

mmap与brk分配对比：

mmap 分配的内存每次释放的时候，都会归还给操作系统，于是每次 mmap 分配的虚拟地址都是缺页状态的，然后在第一次访问该虚拟地址的时候，就会触发缺页中断。也就是说，频繁通过 mmap 分配的内存话，不仅每次都会发生运行态的切换，还会发生缺页中断(在第一次访问虚拟地址后)，这样会导致 CPU 消耗较大。

brk的分配方式，调用在堆空间申请内存的时候，由于堆空间是连续的，所以直接预分配更大的内存来作为内存池，当内存释放的时候，就缓存在内存池中。
等下次在申请内存的时候，就直接从内存池取出对应的内存块就行了，而且可能这个内存块的虚拟地址与物理地址的映射关系还存在，这样不仅减少了系统调用的次数，也减少了缺页中断的次数，这将大大降低 CPU 的消耗。
brk的分配方式问题在于，如果申请的空间没办法复用，那么将会导致堆内将产生越来越多不可用的碎片，导致“内存泄露”。

内存分配过程 [Top]

应用程序通过 malloc 函数申请内存的时候，实际上申请的是虚拟内存，此时并不会分配物理内存。当应用程序读写了这块虚拟内存，CPU 就会去访问这个虚拟内存，这时会发现这个虚拟内存没有映射到物理内存， CPU 就会产生缺页中断，进程会从用户态切换到内核态，并将缺页中断交给内核的Page Fault Handler(缺页中断函数)处理。

缺页中断处理函数会看是否有空闲的物理内存，如果有，就直接分配物理内存，并建立虚拟内存与物理内存之间的映射关系。

如果没有空闲的物理内存，那么内核就会开始进行回收内存的工作，回收的方式主要是两种：直接内存回收和后台内存回收。

后台内存回收(kswapd)：在物理内存紧张的时候，会唤醒 kswapd 内核线程来回收内存，这个回收内存的过程异步的，不会阻塞进程的执行。
直接内存回收(direct reclaim)：如果后台异步回收跟不上进程内存申请的速度，就会开始直接回收，这个回收内存的过程是同步的，会阻塞进程的执行。如果直接内存回收后，空闲的物理内存仍然无法满足此次物理内存的申请，那么内核就会触发OOM(Out of Memory)机制。

内存回收类型 [Top]

主要有两类内存可以被回收，而且它们的回收方式也不同。

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

文件页和匿名页的回收都是基于 LRU 算法，也就是优先回收不常访问的内存。LRU 回收算法，实际上维护着 active 和 inactive 两个双向链表，其中：

active_list 活跃内存页链表，这里存放的是最近被访问过(活跃)的内存页；
inactive_list 不活跃内存页链表，这里存放的是很少被访问(非活跃)的内存页；

活跃和非活跃的内存页，按照类型的不同，又分别分为文件页和匿名页

文件页的回收：对于干净页是直接释放内存，这个操作不会影响性能，而对于脏页会先写回到磁盘再释放内存，这个操作会发生磁盘 I/O 的，这个操作是会影响系统性能的。
匿名页的回收：如果开启了 Swap 机制，那么 Swap 机制会将不常访问的匿名页换出到磁盘中，下次访问时，再从磁盘换入到内存中，这个操作是会影响系统性能的。

回收内存的操作基本都会发生磁盘 I/O 的，如果回收内存的操作很频繁，意味着磁盘 I/O 次数会很多。文件页的回收操作对系统的影响相比匿名页的回收操作会少一点，因为文件页对于干净页回收是不会发生磁盘 I/O 的，而匿名页的 Swap 换入换出这两个操作都会发生磁盘 I/O。

内存回收优化 [Top]

Linux 提供了一个 /proc/sys/vm/swappiness 选项，用来调整文件页和匿名页的回收倾向。swappiness 的范围是 0-100，数值越大，越积极使用 Swap，也就是更倾向于回收匿名页；数值越小，越消极使用 Swap，也就是更倾向于回收文件页。
一般建议 swappiness 设置为 0(默认值是 60)，这样在回收内存的时候，会更倾向于文件页的回收，但是并不代表不会回收匿名页。

可以通过尽早的触发后台内存回收来避免应用程序进行直接内存回收。

内核定义了三个内存阈值(watermark，也称为水位)，用来衡量当前剩余内存(pages_free)是否充裕或者紧张，分别是：

页最小阈值(pages_min)
页低阈值(pages_low)
页高阈值(pages_high)

橙色区域：剩余内存(pages_free)在页低阈值(pages_low)和页最小阈值(pages_min)之间，说明内存压力比较大，剩余内存不多了。这时 kswapd0 会执行内存回收，直到剩余内存大于高阈值(pages_high)为止
红色区域：如果剩余内存(pages_free)小于页最小阈值(pages_min)，说明用户可用内存都耗尽了，此时就会触发直接内存回收。

页低阈值(pages_low)可以通过内核选项 /proc/sys/vm/min_free_kbytes (该参数代表系统所保留空闲内存的最低限)来间接设置。与其他参数的关系如下：

pages_min = min_free_kbytes
pages_low = pages_min*5/4
pages_high = pages_min*3/2

OOM Killer [Top]

OOM Killer 机制会根据算法选择一个占用物理内存较高的进程，然后将其杀死，以便释放内存资源，如果物理内存依然不足，OOM Killer 会继续杀死占用物理内存较高的进程，直到释放足够的内存位置。

oom_badness() 函数，它会把系统中可以被杀掉的进程扫描一遍，并对每个进程打分，得分最高的进程就会被首先杀掉。

进程得分的结果受下面这两个方面影响：

第一，进程已经使用的物理内存页面数。
第二，每个进程的 OOM 校准值 oom_score_adj。它是可以通过 /proc/[pid]/oom_score_adj 来配置的。我们可以在设置 -1000 到 1000 之间的任意一个数值，调整进程被 OOM Kill 的几率。

Swap机制 [Top]

Swap 机制指的是当物理内存不够用，内存管理单元(Memory Management Unit，MMU)需要提供调度算法来回收相关内存空间，然后将清理出来的内存空间给当前内存申请方。

Swap 机制存在的本质原因是 Linux 系统提供了虚拟内存管理机制，每一个进程认为其独占内存空间，因此所有进程的内存空间之和远远大于物理内存。所有进程的内存空间之和超过物理内存的部分就需要交换到磁盘上。

缺页中断：操作系统以 page 为单位管理内存，当进程发现需要访问的数据不在内存时，操作系统可能会将数据以页的方式加载到内存中。上述过程被称为缺页中断，当操作系统发生缺页中断时，就会通过系统调用将 page 再次读到内存中。

页面替换(Page Replacement): 主内存的空间是有限的，当主内存中不包含可以使用的空间时，操作系统会从选择合适的物理内存页驱逐回磁盘，为新的内存页让出位置，选择待驱逐页的过程在操作系统中叫做页面替换(Page Replacement)，替换操作又会触发 swap 机制。

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

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

如果没有开启 Swap 机制，程序就会直接 OOM；
如果有开启 Swap 机制，程序可以正常运行。

Swap 就是把一块磁盘空间或者本地文件，当成内存来使用，它包含换出和换入两个过程：

换出(Swap Out) ，是把进程暂时不用的内存数据存储到磁盘中，并释放这些数据占用的内存；
换入(Swap In)，是在进程再次访问这些内存的时候，把它们从磁盘读到内存中来；

Linux 中的 Swap 机制会在内存不足和内存闲置的场景下触发：

内存不足：当系统需要的内存超过了可用的物理内存时，内核会将内存中不常使用的内存页交换到磁盘上为当前进程让出内存，保证正在执行的进程的可用性，这个内存回收的过程是强制的直接内存回收(Direct Page Reclaim)。直接内存回收是同步的过程，会阻塞当前申请内存的进程。
内存闲置：应用程序在启动阶段使用的大量内存在启动后往往都不会使用，通过后台运行的守护进程(kSwapd)。我们可以将这部分只使用一次的内存交换到磁盘上为其他内存的申请预留空间。kSwapd 是 Linux 负责页面置换(Page replacement)的守护进程，它也是负责交换闲置内存的主要进程，它会在空闲内存低于一定水位(opens new window)时，回收内存页中的空闲内存保证系统中的其他进程可以尽快获得申请的内存。kSwapd 是后台进程，所以回收内存的过程是异步的，不会阻塞当前申请内存的进程。

进程管理 [Top]

进程 [Top]

进程：在计算机操作系统中，进程是资源分配的基本单元，也是独立运行的基本单元。

进程特征：

动态性：进程是程序在处理器上的一次执行过程，过程是动态的。
并发性：多个进程在内存同时存在，并可以并发执行。
独立性：进程是资源分配的基本单元，也是独立运行的基本单元。
异步性
结构特征：为了描述和记录进程的运动变化过程，为每个进程分配一个进程控制快(PCB,process control block)，每个进程都由程序段、数据段和一个进程控制块组成。

进程的组成：

进程控制块(PCB)：每个进程均有一个PCB，是一个既能标识进程存在、又能刻画执行瞬间特征的数据结构。
程序段：进程中能被调度程序调度到CPU上执行的程序代码段。
数据段
进程标识符(PID)：区别系统内其他进程
进程状态
进程优先级
CPU现场保护区：当进程因某种原因释放处理器时，CPU现场信息(如指令计数器、状态寄存器、通用寄存器等)被保存在PCB的该区域中，以便重新获得处理器后继续执行
通信信息：和其他进程的通信情况
家族信息：子进程
占有资源清单

进程状态：就绪状态、执行状态、阻塞状态、创建状态、结束状态

进程控制块(process control block，PCB): PCB 是进程存在的唯一标识，用来来描述进程的数据结构。

PCB通常是通过链表的方式进行组织，把具有相同状态的进程链在一起，组成各种队列。

将所有处于就绪状态的进程链在一起，称为就绪队列
把所有因等待某事件而处于等待状态的进程链在一起就组成各种阻塞队列

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

32 位系统，用户态的虚拟空间只有 3G，如果创建线程时分配的栈空间是 10M，那么一个进程最多只能创建 300 个左右的线程。
64 位系统，用户态的虚拟空间大到有 128T，理论上不会受虚拟内存大小的限制，而会受系统的参数或性能限制。

线程 [Top]

线程是进程内一个相对独立的、可调度的执行单元，是 CPU 调度的最小单位。线程基本上不拥有资源，只拥有在运行时必不可少的资源(如程序计数器、一组寄存器和栈)，但它可以和其他线程共享进程拥有的全部资源。

线程的实现：

内核级线程(Kernel Thread)：依赖于内核，由操作系统内核完成创建和撤销工作的线程。内核维护进程和线程的上下文信息并完成线程切换工作。

一个内核级线程由于I/O操作而阻塞时，不会影响其他线程的运行。这时，处理器时间片分配的对象为线程。
用户级线程(User Thread)：不依赖于操作系统核心，由应用程序利用线程库提供创建、同步、调度和管理线程的函数来控制线程。

用户级线程维护由应用程序完成，内核不需要了解用户级线程存在。用户级线程切换不需要内核特权，通常应用程序的线程调度使用非抢占式或更简单的规则。这时候处理器的时间片是分配给进程的。
轻量级进程(Light-weight process，LWP)：在内核中来支持用户线程；是内核支持的用户线程，一个进程可有一个或多个 LWP，每个 LWP 是跟内核线程一对一映射的，也就是 LWP 都是由一个内核线程支持。

轻量级进程(Light-weight process，LWP)是内核支持的用户线程，LWP 只能由内核管理并像普通进程一样被调度，Linux 内核是支持 LWP 的典型例子。

在大多数系统中，LWP与普通进程的区别也在于它只有一个最小的执行上下文和调度程序所需的统计信息。一般来说，一个进程代表程序的一个实例，而 LWP 代表程序的执行线程，因为一个执行线程不像进程那样需要那么多状态信息，所以 LWP 也不带有这样的信息。

在 LWP 之上也是可以使用用户线程的，那么 LWP 与用户线程的对应关系就有三种：

1 : 1，即一个 LWP 对应一个用户线程；
N : 1，即一个 LWP 对应多个用户线程；
M : N，即多个 LWP 对应多个用户线程；

多线程模型：

多对一模型：多个用户级线程映射到同一个内核线程。

优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小、效率高
缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并发运行

多个用户线程对应一个内核线程,该模型的线程管理是由用户空间的线程库来完成的,因此效率更高,并且高效的上下文切换和几乎无限制的线程数量.不过,如果一个线程执行阻塞系统调用,那么整个进程将会阻塞.再者,因为任一时间只有一个线程可以访问内核,所以多个线程不能并行运行在多处理核系统上.

一对一模型：一个用户级线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。

优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可以在多核处理机下并行执行
缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大

每个用户线程对应一个内核线程,该模型在一个线程执行阻塞系统调用时,能够允许另一个线程继续执行,所以对于IO密集型的场景，CPU、磁盘IO、网卡等资源利用率还是非常友好的,提供了更好的并发功能.但是对于CPU计算密集型的,会导致上下文切换,结合上面内核线程的劣势.
Java的内存模型就是一对一模型

多对多模型：n个用户级线程映射到m个内核级线程。每个用户进程对应m个内核级线程。

优点：克服了多对一模型并发度不高的缺点，又可服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点

多个用户线程对应多个内核线程,使得库和操作系统都可以管理线程,用户线程由运行时库调度器管理,内核线程由操作系统调度器管理,可运行的用户线程由运行时库分派并标记为准备好执行的可用线程,操作系统选择用户线程并将它映射到可用内核线程.

线程与进程比较 [Top]

拥有资源：进程为拥有系统资源的基本单元，而线程不拥有系统资源，但是线程可以访问隶属进程的系统资源
并发性：进入线程的操作系统，不仅进程可以并发，而且统一进程的线程也可以并发。系统的并发度更高，大大提高了系统的吞吐量。
调度：统一进程中的线程切换不会引起进程切换，而不同进程的线程切换会引起进程切换。
系统开销：
- 创建或撤销开销：由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O设备等。操作系统所付出的代价远大于创建或撤销线程是的开销。
- 切换开销：进程切换时，涉及整个当前进程CPU环境的保存以及新进程的CPU环境的设置。而线程上下文的切换，只需要保存和设置少量寄存器的内容。多线程的同步和通信因为共享同一进程，甚至无需操作系统干预。

线程相比进程能减少开销，体现在：

线程的创建时间比进程快，因为进程在创建的过程中，还需要资源管理信息，比如内存管理信息、文件管理信息，而线程在创建的过程中，不会涉及这些资源管理信息，而是共享它们；
线程的终止时间比进程快，因为线程释放的资源相比进程少很多；
同一个进程内的线程切换比进程切换快，因为线程具有相同的地址空间(虚拟内存共享)，这意味着同一个进程的线程都具有同一个页表，那么在切换的时候不需要切换页表。而对于进程之间的切换，切换的时候要把页表给切换掉，而页表的切换过程开销是比较大的；
由于同一进程的各线程间共享内存和文件资源，那么在线程之间数据传递的时候，就不需要经过内核了，这就使得线程之间的数据交互效率更高了；

线程崩溃，进程一定会崩溃吗？

如果线程是因为非法访问内存引起的崩溃，那么进程肯定会崩溃，为什么系统要让进程崩溃呢，这主要是因为在进程中，各个线程的地址空间是共享的，那么某个线程对地址的非法访问就会导致内存的不确定性，进而可能会影响到其他线程。进程是崩溃主要通过信号机制来实现的。

为什么线程崩溃不会导致 JVM 进程崩溃?

原因其实就是JAVA虚拟机内部定义了信号处理函数，而在信号处理函数中对这两者做了额外的处理以让 JVM 不崩溃，另一方面也可以看出如果 JVM 不对信号做额外的处理，最后会自己退出并产生 crash 文件 hs_err_pid_xxx.log(可以通过-XX:ErrorFile=/var/log/hs_err.log这样的方式指定)，这个文件记录了虚拟机崩溃的重要原因。

上下文切换 [Top]

CPU上下文切换 [Top]

CPU 寄存器和程序计数是 CPU 在运行任何任务前，所必须依赖的环境，这些环境就叫做 CPU 上下文。

CPU 寄存器是 CPU 内部一个容量小，但是速度极快的内存(缓存)
程序计数器则是用来存储 CPU 正在执行的指令位置、或者即将执行的下一条指令位置。

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

系统内核会存储保持下来的上下文信息，当此任务再次被分配给 CPU 运行时，CPU 会重新加载这些上下文，这样就能保证任务原来的状态不受影响，让任务看起来还是连续运行。

上面说到所谓的「任务」，主要包含进程、线程和中断。所以，可以根据任务的不同，把 CPU 上下文切换分成：进程上下文切换、线程上下文切换和中断上下文切换。

进程上下文切换 [Top]

各个进程之间是共享 CPU 资源的，在不同的时候进程之间需要切换，让不同的进程可以在 CPU 执行，那么这个一个进程切换到另一个进程运行，称为进程的上下文切换。

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

进程是由内核管理和调度的，所以进程的切换只能发生在内核态。

通常，会把交换的信息保存在进程的 PCB，当要运行另外一个进程的时候，我们需要从这个进程的 PCB 取出上下文，然后恢复到 CPU 中，这使得这个进程可以继续执行。

发生进程上下文切换有哪些场景？

为了保证所有进程可以得到公平调度，CPU 时间被划分为一段段的时间片，这些时间片再被轮流分配给各个进程。这样，当某个进程的时间片耗尽了，进程就从运行状态变为就绪状态，系统从就绪队列选择另外一个进程运行；

进程在系统资源不足(比如内存不足)时，要等到资源满足后才可以运行，这个时候进程也会被挂起，并由系统调度其他进程运行；
当进程通过睡眠函数 sleep 这样的方法将自己主动挂起时，自然也会重新调度；
当有优先级更高的进程运行时，为了保证高优先级进程的运行，当前进程会被挂起，由高优先级进程来运行；
发生硬件中断时，CPU 上的进程会被中断挂起，转而执行内核中的中断服务程序；

线程上下文切换 [Top]

线程与进程最大的区别在于：线程是调度的基本单位，而进程则是资源拥有的基本单位。 所以，所谓操作系统的任务调度，实际上的调度对象是线程，而进程只是给线程提供了虚拟内存、全局变量等资源。

当进程只有一个线程时，可以认为进程就等于线程；
当进程拥有多个线程时，这些线程会共享相同的虚拟内存和全局变量等资源，这些资源在上下文切换时是不需要修改的；

线程上下文切换的是什么？

这还得看线程是不是属于同一个进程：

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

处理器调度 [Top]

高级调度：即作业调度，按照一定策略将选择磁盘上的程序装入内存，并建立进程。
中级调度：即交换调度，按照一定策略在内外存之间进行数据交换。
低级调度：即CPU调度(进程调度)，按照一定策略选择就绪进程，占用cpu执行。

调度基本原则 [Top]

原则一：如果运行的程序，发生了 I/O 事件的请求，那 CPU 使用率必然会很低，因为此时进程在阻塞等待硬盘的数据返回。这样的过程，势必会造成 CPU 突然的空闲。所以，为了提高 CPU 利用率，在这种发送 I/O 事件致使 CPU 空闲的情况下，调度程序需要从就绪队列中选择一个进程来运行。
原则二：有的程序执行某个任务花费的时间会比较长，如果这个程序一直占用着 CPU，会造成系统吞吐量(CPU 在单位时间内完成的进程数量)的降低。所以，要提高系统的吞吐率，调度程序要权衡长任务和短任务进程的运行完成数量。
原则三：从进程开始到结束的过程中，实际上是包含两个时间，分别是进程运行时间和进程等待时间，这两个时间总和就称为周转时间。进程的周转时间越小越好，如果进程的等待时间很长而运行时间很短，那周转时间就很长，这不是我们所期望的，调度程序应该避免这种情况发生。
原则四：处于就绪队列的进程，也不能等太久，当然希望这个等待的时间越短越好，这样可以使得进程更快的在 CPU 中执行。所以，就绪队列中进程的等待时间也是调度程序所需要考虑的原则。
原则五：对于鼠标、键盘这种交互式比较强的应用，我们当然希望它的响应时间越快越好，否则就会影响用户体验了。所以，对于交互式比较强的应用，响应时间也是调度程序需要考虑的原则。

CPU 利用率：调度程序应确保 CPU 是始终匆忙的状态，这可提高 CPU 的利用率；
系统吞吐量：吞吐量表示的是单位时间内 CPU 完成进程的数量，长作业的进程会占用较长的 CPU 资源，因此会降低吞吐量，相反，短作业的进程会提升系统吞吐量；
周转时间：周转时间是进程运行+阻塞时间+等待时间的总和，一个进程的周转时间越小越好；
等待时间：这个等待时间不是阻塞状态的时间，而是进程处于就绪队列的时间，等待的时间越长，用户越不满意；
响应时间：用户提交请求到系统第一次产生响应所花费的时间，在交互式系统中，响应时间是衡量调度算法好坏的主要标准。

调度算法 [Top]

先来先服务调度算法(first-come first-serverd,FCFS)
短作业优先调度算法(shortest job first,SJF) : 把处理器分配给最快完成的作业，会导致长作业饿死。
优先级调度算法：确定优先级进行调度，调度方式还可以分为抢占和非抢占的调度方式
时间片轮转调度算法：一个进程在一个时间片未执行完毕，插入到队尾等待，循环直到处理完成
高响应比优先算法(highest response ratio first,HSRF)：通过设置响应比公式：响应比=(作业等待时间+估计运行时间)/估计运行时间，解决长作业饿死问题
多级队列调度算法：多个队列每个队列使用一种调度算法
多级反馈队列调度算法：时间片轮转调度算法和优先级调度算法的综合，动态调整队列优先级和时间片大小。进程所在队列的优先级越高时间片越小。可兼顾多方面的系统目标，如为提高系统吞吐量和缩短平均响应周期而照顾端线程。

适用于作业调度的算法：先来先服务调度算法、短作业优先调度算法、优先级调度算法、高响应比优先算法
适用于进程调度的算法：先来先服务调度算法、短作业优先调度算法、优先级调度算法、时间片轮转调度算法、多级队列调度算法、多级反馈队列调度算法

进程通信 [Top]

管道通信 [Top]

管道通信: 所谓的管道，就是内核里面的一串缓存。从管道的一段写入的数据，实际上是缓存在内核中的，另一端读取，也就是从内核中读取这段数据。

管道传输数据是单向的，如果想相互通信，需要创建两个管道才行。
管道这种通信方式效率低，不适合进程间频繁地交换数据

匿名管道：对于匿名管道，它的通信范围是存在父子关系的进程。因为管道没有实体，也就是没有管道文件，只能通过 fork 来复制父进程 fd 文件描述符，来达到通信的目的。
匿名管道的生命周期，是随进程的创建而建立，随进程的结束而销毁。

$ ps auxf | grep mysql

命名管道：对于命名管道，它可以在不相关的进程间也能相互通信。因为命令管道，提前创建了一个类型为管道的设备文件，在进程里只要使用这个设备文件，就可以相互通信。

mkfifo myPipe

$ echo "hello" > myPipe  // 将数据写进管道 block


$ cat < myPipe  // 读取管道里的数据
hello

消息队列 [Top]

消息队列是保存在内核中的消息链表。
在发送数据时，会分成一个一个独立的数据单元，也就是消息体(数据块)，消息体是用户自定义的数据类型，消息的发送方和接收方要约定好消息体的数据类型，所以每个消息体都是固定大小的存储块，不像管道是无格式的字节流数据。如果进程从消息队列中读取了消息体，内核就会把这个消息体删除。

消息队列生命周期随内核，如果没有释放消息队列或者没有关闭操作系统，消息队列会一直存在。
消息队列不适合比较大数据的传输。在内核中每个消息体都有一个最大长度的限制，同时所有队列所包含的全部消息体的总长度也是有上限。
消息队列通信过程中，存在用户态与内核态之间的数据拷贝开销

共享内存 [Top]

共享内存的机制，就是拿出一块虚拟地址空间来，映射到相同的物理内存中。这样这个进程写入的东西，另外一个进程马上就能看到了，都不需要拷贝来拷贝去，传来传去，大大提高了进程间通信的速度。

消息队列的读取和写入的过程，都会有发生用户态与内核态之间的消息拷贝过程。那共享内存的方式，就很好的解决了这一问题。

信号量 [Top]

用了共享内存通信方式，带来新的问题，那就是如果多个进程同时修改同一个共享内存，很有可能就冲突了。例如两个进程都同时写一个地址，那先写的那个进程会发现内容被别人覆盖了。

了防止多进程竞争共享资源，而造成的数据错乱，所以需要保护机制，使得共享的资源，在任意时刻只能被一个进程访问。正好，信号量就实现了这一保护机制。

信号量其实是一个整型的计数器，主要用于实现进程间的互斥与同步，而不是用于缓存进程间通信的数据。

信号量表示资源的数量，控制信号量的方式有两种原子操作：

P 操作，这个操作会把信号量减去 1，相减后如果信号量 < 0，则表明资源已被占用，进程需阻塞等待；相减后如果信号量 >= 0，则表明还有资源可使用，进程可正常继续执行。
V 操作，这个操作会把信号量加上 1，相加后如果信号量 <= 0，则表明当前有阻塞中的进程，于是会将该进程唤醒运行；相加后如果信号量 > 0，则表明当前没有阻塞中的进程；

P 操作是用在进入共享资源之前，V 操作是用在离开共享资源之后，这两个操作是必须成对出现的。

互斥信号量，它可以保证共享内存在任何时刻只有一个进程在访问，这就很好的保护了共享内存，信号初始化为 1。使得两个进程互斥访问共享内存。
同步信号量，它可以保证进程 A 应在进程 B 之前执行，信号量初始化为0。进程 A 是负责生产数据，而进程 B 是负责读取数据，这两个进程是相互合作、相互依赖的。

信号 [Top]

管道、消息队列、共享内存、信号量的进程间通信，都是常规状态下的工作模式。对于异常情况下的工作模式，就需要用「信号」的方式来通知进程。

Ctrl+C 产生 SIGINT 信号，表示终止该进程；
Ctrl+Z 产生 SIGTSTP 信号，表示停止该进程，但还未结束；
kill -9 1050 ，表示给 PID 为 1050 的进程发送 SIGKILL 信号，用来立即结束该进程；

信号是进程间通信机制中唯一的异步通信机制，因为可以在任何时候发送信号给某一进程，一旦有信号产生，就有下面这几种，用户进程对信号的处理方式。

执行默认操作。Linux 对每种信号都规定了默认操作，例如，SIGTERM 信号，就是终止进程的意思。
捕捉信号。我们可以为信号定义一个信号处理函数。当信号发生时，我们就执行相应的信号处理函数。
忽略信号。当我们不希望处理某些信号的时候，就可以忽略该信号，不做任何处理。有两个信号是应用进程无法捕捉和忽略的，即 SIGKILL 和 SEGSTOP，它们用于在任何时候中断或结束某一进程。

Socket [Top]

前面提到的管道、消息队列、共享内存、信号量和信号都是在同一台主机上进行进程间通信，那要想跨网络与不同主机上的进程之间通信，就需要 Socket 通信了。

实际上，Socket 通信不仅可以跨网络与不同主机的进程间通信，还可以在同主机上进程间通信。

并发 [Top]

竞争条件(race condition)

不确定性(indeterminate)

临界区(critical section)，它是访问共享资源的代码片段，一定不能给多线程同时执行。

互斥(mutual exclusion)的，也就说保证一个线程在临界区执行时，其他线程应该被阻止进入临界区

同步，就是并发进程/线程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通信息称为进程/线程同步。

原子操作就是要么全部执行，要么都不执行，不能出现执行到一半的中间状态

忙等待锁(自旋锁spin lock)：当获取不到锁时，线程就会一直 while 循环，不做任何事情。
无等待锁：顾明思议就是获取不到锁的时候，不用自旋。既然不想自旋，那当没获取到锁的时候，就把当前线程放入到锁的等待队列，然后执行调度程序，把 CPU 让给其他线程执行。

经典同步问题 [Top]

生产者-消费者问题 [Top]

生产者-消费者问题(Producer-consumer problem)，也称有限缓冲问题(Bounded-buffer problem)，是一个多线程同步问题的经典案例。该问题描述了共享固定大小缓冲区的两个线程——即所谓的“生产者”和“消费者”——在实际运行时会发生的问题。生产者的主要作用是生成一定量的数据放到缓冲区中，然后重复此过程。与此同时，消费者也在缓冲区消耗这些数据。该问题的关键就是要保证生产者不会在缓冲区满时加入数据，消费者也不会在缓冲区中空时消耗数据。

哲学家就餐问题 [Top]

哲学家就餐的问题描述： 5 个哲学家，围绕着一张圆桌吃面；这个桌子只有 5 支叉子，每两个哲学家之间放一支叉子；哲学家围在一起先思考，思考中途饿了就会想进餐；
这些哲学家要两支叉子才愿意吃面，也就是需要拿到左右两边的叉子才进餐；吃完后，会把两支叉子放回原处，继续思考；

方案1：每个哲学家都先拿左边的叉子，再拿右边的叉子。使用信号量方式实现，充当每个叉子的信号量。

缺陷：假设五位哲学家同时拿起左边的叉子，桌面上就没有叉子了，这样就没有人能够拿到他们右边的叉子，发生死锁现象。

方案2：只要有一个哲学家进入了「临界区」，也就是准备要拿叉子时，其他哲学家都不能动，只有这位哲学家用完叉子了，才能轮到下一个哲学家进餐。使用互斥信号量，只有一个哲学家获取这个互斥信号量才能去拿叉子。

缺陷：每次进餐只能有一位哲学家，而桌面上是有 5 把叉子，按道理是能可以有两个哲学家同时进餐的，所以从效率角度上，这不是最好的解决方案。

方案3：让偶数编号的哲学家「先拿左边的叉子后拿右边的叉子」，奇数编号的哲学家「先拿右边的叉子后拿左边的叉子」。

方案4：用一个数组 state 来记录每一位哲学家的三个状态，分别是在进餐状态、思考状态、饥饿状态(正在试图拿叉子)。

读者-写者问题 [Top]

读者只会读取数据，不会修改数据，而写者即可以读也可以修改数据。

读者-写者的问题描述：

「读-读」允许：同一时刻，允许多个读者同时读
「读-写」互斥：没有写者时读者才能读，没有读者时写者才能写
「写-写」互斥：没有其他写者时，写者才能写

死锁 [Top]

在多线程编程中，我们为了防止多线程竞争共享资源而导致数据错乱，都会在操作共享资源之前加上互斥锁，只有成功获得到锁的线程，才能操作共享资源，获取不到锁的线程就只能等待，直到锁被释放。那么，当两个线程为了保护两个不同的共享资源而使用了两个互斥锁，那么这两个互斥锁应用不当的时候，可能会造成两个线程都在等待对方释放锁，在没有外力的作用下，这些线程会一直相互等待，就没办法继续运行，这种情况就是发生了死锁。

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

互斥条件；
持有并等待条件；
不可剥夺条件；
环路等待条件；

互斥条件是指多个线程不能同时使用同一个资源。
持有并等待条件是指，当线程 A 已经持有了资源 1，又想申请资源 2，而资源 2 已经被线程 C 持有了，所以线程 A 就会处于等待状态，但是线程 A 在等待资源 2 的同时并不会释放自己已经持有的资源 1。
不可剥夺条件是指，当线程已经持有了资源，在自己使用完之前不能被其他线程获取，线程 B 如果也想使用此资源，则只能在线程 A 使用完并释放后才能获取。
环路等待条件指的是，在死锁发生的时候，两个线程获取资源的顺序构成了环形链。

避免死锁

避免死锁问题就只需要破环其中一个条件就可以，最常见的并且可行的就是使用资源有序分配法，来破环环路等待条件。

线程 A 和线程 B 获取资源的顺序要一样，当线程 A 是先尝试获取资源 A，然后尝试获取资源 B 的时候，线程 B 同样也是先尝试获取资源 A，然后尝试获取资源 B。也就是说，线程 A 和线程 B 总是以相同的顺序申请自己想要的资源。

死锁问题的产生是由两个或者以上线程并行执行的时候，争夺资源而互相等待造成的。

死锁只有同时满足互斥、持有并等待、不可剥夺、环路等待这四个条件的时候才会发生。

所以要避免死锁问题，就是要破坏其中一个条件即可，最常用的方法就是使用资源有序分配法来破坏环路等待条件。

锁 [Top]

互斥锁 [Top]

互斥锁是一种「独占锁」，比如当线程 A 加锁成功后，此时互斥锁已经被线程 A 独占了，只要线程 A 没有释放手中的锁，线程 B 加锁就会失败，于是就会释放 CPU 让给其他线程，既然线程 B 释放掉了 CPU，自然线程 B 加锁的代码就会被阻塞。

对于互斥锁加锁失败而阻塞的现象，是由操作系统内核实现的。当加锁失败时，内核会将线程置为「睡眠」状态，等到锁被释放后，内核会在合适的时机唤醒线程，当这个线程成功获取到锁后，于是就可以继续执行。

互斥锁加锁失败时，会从用户态陷入到内核态，让内核帮我们切换线程，虽然简化了使用锁的难度，但是存在一定的性能开销成本。那这个开销成本是主要是两次线程上下文切换成本：

当线程加锁失败时，内核会把线程的状态从「运行」状态设置为「睡眠」状态，然后把 CPU 切换给其他线程运行；
当锁被释放时，之前「睡眠」状态的线程会变为「就绪」状态，然后内核会在合适的时间，把 CPU 切换给该线程运行。

线程的上下文切换的是什么？当两个线程是属于同一个进程，因为虚拟内存是共享的，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程的私有数据、寄存器等不共享的数据。

上下切换的耗时据统计，大概在几十纳秒到几微秒之间，如果你锁住的代码执行时间比较短，那可能上下文切换的时间都比你锁住的代码执行时间还要长。

所以，如果你能确定被锁住的代码执行时间很短，就不应该用互斥锁，而应该选用自旋锁，否则使用互斥锁。

自旋锁 [Top]

自旋锁是通过 CPU 提供的 CAS 函数(Compare And Swap)，在「用户态」完成加锁和解锁操作，不会主动产生线程上下文切换，所以相比互斥锁来说，会快一些，开销也小一些。

一般加锁的过程，包含两个步骤：

第一步，查看锁的状态，如果锁是空闲的，则执行第二步；
第二步，将锁设置为当前线程持有； CAS 函数就把这两个步骤合并成一条硬件级指令，形成原子指令，这样就保证了这两个步骤是不可分割的，要么一次性执行完两个步骤，要么两个步骤都不执行。

在单核 CPU 上，需要抢占式的调度器(即不断通过时钟中断一个线程，运行其他线程)。否则，自旋锁在单 CPU 上无法使用，因为一个自旋的线程永远不会放弃 CPU。
在多核系统下一般不会主动产生线程切换，适合异步、协程等在用户态切换请求的编程方式，但如果被锁住的代码执行时间过长，自旋的线程会长时间占用 CPU 资源

读写锁 [Top]

读写锁：由「读锁」和「写锁」两部分构成，如果只读取共享资源用「读锁」加锁，如果要修改共享资源则用「写锁」加锁。读写锁适用于能明确区分读操作和写操作的场景。

读写锁适用于能明确区分读操作和写操作的场景。

「读优先锁」：当读线程 A 先持有了读锁，写线程 B 在获取写锁的时候，会被阻塞，并且在阻塞过程中，后续来的读线程 C 仍然可以成功获取读锁，最后直到读线程 A 和 C 释放读锁后，写线程 B 才可以成功获取写锁。
「写优先锁」：当读线程 A 先持有了读锁，写线程 B 在获取写锁的时候，会被阻塞，并且在阻塞过程中，后续来的读线程 C 获取读锁时会失败，于是读线程 C 将被阻塞在获取读锁的操作，这样只要读线程 A 释放读锁后，写线程 B 就可以成功获取写锁。
「公平读写锁」：用队列把获取锁的线程排队，不管是写线程还是读线程都按照先进先出的原则加锁即可，这样读线程仍然可以并发，也不会出现「饥饿」的现象。

乐观锁与悲观锁 [Top]

悲观锁认为多线程同时修改共享资源的概率比较高，于是很容易出现冲突，所以访问共享资源前，先要上锁。

乐观锁认为假定冲突的概率很低，它的工作方式是：先修改完共享资源，再验证这段时间内有没有发生冲突，如果没有其他线程在修改资源，那么操作完成，如果发现有其他线程已经修改过这个资源，就放弃本次操作。

乐观锁虽然去除了加锁解锁的操作，但是一旦发生冲突，重试的成本非常高，所以只有在冲突概率非常低，且加锁成本非常高的场景时，才考虑使用乐观锁。

文件系统 [Top]

文件系统组成 [Top]

Linux 文件系统会为每个文件分配两个数据结构：索引节点(index node)和目录项(directory entry)，它们主要用来记录文件的元信息和目录层次结构。

索引节点，用来记录文件的元信息，比如 inode 编号、文件大小、访问权限、创建时间、修改时间、数据在磁盘的位置等等。索引节点是文件的唯一标识，它们之间一一对应，也同样都会被存储在硬盘中，所以索引节点同样占用磁盘空间。
目录项，用来记录文件的名字、索引节点指针以及与其他目录项的层级关联关系。多个目录项关联起来，就会形成目录结构，但它与索引节点不同的是，目录项是由内核维护的一个数据结构，不存放于磁盘，而是缓存在内存。

由于索引节点唯一标识一个文件，而目录项记录着文件的名，所以目录项和索引节点的关系是多对一，也就是说，一个文件可以有多个别字。比如，硬链接的实现就是多个目录项中的索引节点指向同一个文件。

目录项和目录是一个东西吗？
目录是个文件，持久化存储在磁盘，而目录项是内核一个数据结构，缓存在内存。如果查询目录频繁从磁盘读，效率会很低，所以内核会把已经读过的目录用目录项这个数据结构缓存在内存，下次再次读到相同的目录时，只需从内存读就可以，大大提高了文件系统的效率。

扇区: 磁盘读写的最小单位是扇区，扇区的大小只有512B大小。
逻辑块(数据块): 文件系统把多个扇区组成了一个逻辑块，每次读写的最小单位就是逻辑块(数据块)，Linux 中的逻辑块大小为4KB，也就是一次性读写 8 个扇区，这将大大提高了磁盘的读写的效率。
超级块，用来存储文件系统的详细信息，比如块个数、块大小、空闲块等等。
索引节点区，用来存储索引节点；
数据块区，用来存储文件或目录数据；

超级块及索引节点区当需要使用的时候，才将其加载进内存，它们加载进内存的时机是不同超级块：当文件系统挂载时进入内存；索引节点区：当文件被访问时进入内存；

虚拟文件系统 [Top]

虚拟文件系统：文件系统的种类众多，而操作系统希望对用户提供一个统一的接口，于是在用户层与文件系统层引入了中间层，这个中间层就称为虚拟文件系统(Virtual File System，VFS)。

VFS 定义了一组所有文件系统都支持的数据结构和标准接口，这样使用方不需要了解文件系统的工作原理，只需要了解 VFS 提供的统一接口即可。

Linux 文件系统中，用户空间、系统调用、虚拟机文件系统、缓存、文件系统以及存储之间的关系

文件系统首先要先挂载到某个目录才可以正常使用，比如 Linux 系统在启动时，会把文件系统挂载到根目录。

文件使用 [Top]

打开了一个文件后，操作系统会跟踪进程打开的所有文件，就是操作系统为每个进程维护一个打开文件表，文件表里的每一项代表「文件描述符」，所以说文件描述符是打开文件的标识。

操作系统在打开文件表中维护着打开文件的状态和信息：

文件指针：系统跟踪上次读写位置作为当前文件位置指针，这种指针对打开文件的某个进程来说是唯一的；
文件打开计数器：文件关闭时，操作系统必须重用其打开文件表条目，否则表内空间不够用。因为多个进程可能打开同一个文件，所以系统在删除打开文件条目之前，必须等待最后一个进程关闭文件，该计数器跟踪打开和关闭的数量，当该计数为 0 时，系统关闭文件，删除该条目；
文件磁盘位置：绝大多数文件操作都要求系统修改文件数据，该信息保存在内存中，以免每个操作都从磁盘中读取；
访问权限：每个进程打开文件都需要有一个访问模式(创建、只读、读写、添加等)，该信息保存在进程的打开文件表中，以便操作系统能允许或拒绝之后的 I/O 请求；

用户和操作系统对文件的读写操作是有差异的，用户习惯以字节的方式读写文件，而操作系统则是以数据块来读写文件，那屏蔽掉这种差异的工作就是文件系统了。

读文件和写文件的过程：

当用户进程从文件读取 1 个字节大小的数据时，文件系统则需要获取字节所在的数据块，再返回数据块对应的用户进程所需的数据部分。
当用户进程把 1 个字节大小的数据写进文件时，文件系统则找到需要写入数据的数据块的位置，然后修改数据块中对应的部分，最后再把数据块写回磁盘。

文件系统的基本操作单位是数据块

文件存储 [Top]

连续空间存放方式：文件存放在磁盘「连续的」物理空间中，文件的数据都是紧密相连，读写效率很高，因为一次磁盘寻道就可以读出整个文件。

使用连续存放的方式有一个前提，必须先知道一个文件的大小，这样文件系统才会根据文件的大小在磁盘上找到一块连续的空间分配给文件。所以，文件头里需要指定「起始块的位置」和「长度」
缺陷:「磁盘空间碎片」和「文件长度不易扩展」

非连续空间存放方式分为「链表方式」和「索引方式」。

链表方式

链表的方式存放是离散的，不用连续的，于是就可以消除磁盘碎片，可大大提高磁盘空间的利用率，同时文件的长度可以动态扩展。根据实现的方式的不同，链表可分为「隐式链表」和「显式链接」两种形式。

「隐式链表」的方式存放的话，实现的方式是文件头要包含「第一块」和「最后一块」的位置，并且每个数据块里面留出一个指针空间，用来存放下一个数据块的位置，这样一个数据块连着一个数据块，从链头开始就可以顺着指针找到所有的数据块，所以存放的方式可以是不连续的。缺点：缺点在于无法直接访问数据块，只能通过指针顺序访问文件，以及数据块指针消耗了一定的存储空间。隐式链接分配的稳定性较差，系统在运行过程中由于软件或者硬件错误导致链表中的指针丢失或损坏，会导致文件数据的丢失。

「显式链接」，它指把用于链接文件各数据块的指针，显式地存放在内存的一张链接表中，该表在整个磁盘仅设置一张，每个表项中存放链接指针，指向下一个数据块号。
查找记录的过程是在内存中进行的，因而不仅显著地提高了检索速度，而且大大减少了访问磁盘的次数。但也正是整个表都存放在内存中的关系，它的主要的缺点是不适用于大磁盘，因为大磁盘需要建立链接表占用内存空间过大。

索引方式

索引的实现是为每个文件创建一个「索引数据块」，里面存放的是指向文件数据块的指针列表。

另外，文件头需要包含指向「索引数据块」的指针，这样就可以通过文件头知道索引数据块的位置，再通过索引数据块里的索引信息找到对应的数据块。

索引的方式优点在于：

文件的创建、增大、缩小很方便；
不会有碎片的问题；
支持顺序读写和随机读写；

缺点：存储索引带来的开销。如果文件很小，但还是需要额外分配一块来存放索引数据

「链式索引块」，它的实现方式是在索引数据块留出一个存放下一个索引数据块的指针，于是当一个索引数据块的索引信息用完了，就可以通过指针的方式，找到下一个索引数据块的信息。
「多级索引块」，实现方式是通过一个索引块来存放多个索引数据块，一层套一层索引。

文件系统结构 [Top]

引导块，在系统启动时用于启用引导，接着后面就是一个一个连续的块组了，块组的内容如下：

超级块，包含的是文件系统的重要信息，比如 inode 总个数、块总个数、每个块组的 inode 个数、每个块组的块个数等等。
块组描述符，包含文件系统中各个块组的状态，比如块组中空闲块和 inode 的数目等，每个块组都包含了文件系统中「所有块组的组描述符信息」。
数据位图和 inode 位图，用于表示对应的数据块或 inode 是空闲的，还是被使用中。
inode 列表，包含了块组中所有的 inode，inode 用于保存文件系统中与各个文件和目录相关的所有元数据。
数据块，包含文件的有用数据。

软链接和硬链接 [Top]

给某个文件取个别名，那么在 Linux 中可以通过硬链接(Hard Link) 和软链接(Symbolic Link)的方式来实现

硬链接是多个目录项中的「索引节点」指向一个文件

硬链接是不可用于跨文件系统的。由于多个目录项都是指向一个 inode，那么只有删除文件的所有硬链接以及源文件时，系统才会彻底删除该文件。

软链接相当于重新创建一个文件，这个文件有独立的 inode，但是这个文件的内容是另外一个文件的路径，所以访问软链接的时候，实际上相当于访问到了另外一个文件，

软链接是可以跨文件系统的，甚至目标文件被删除了，链接文件还是在的，只不过指向的文件找不到了而已。

文件/网络IO [Top]

缓冲与非缓冲 I/O
直接与非直接 I/O
阻塞与非阻塞 I/O VS 同步与异步 I/O

缓冲与非缓冲 I/O [Top]

文件操作的标准库是可以实现数据的缓存，那么根据「是否利用标准库缓冲」，可以把文件 I/O 分为缓冲 I/O 和非缓冲 I/O。

缓冲 I/O，利用的是标准库的缓存实现文件的加速访问，而标准库再通过系统调用访问文件。
非缓冲 I/O，直接通过系统调用访问文件，不经过标准库缓存。

很多程序遇到换行时才真正输出，而换行前的内容，其实就是被标准库暂时缓存了起来，这样做的目的是，减少系统调用的次数，毕竟系统调用是有 CPU 上下文切换的开销的。

直接与非直接 I/O [Top]

Linux 内核为了减少磁盘 I/O 次数，在系统调用后，会把用户数据拷贝到内核中缓存起来，这个内核缓存空间也就是「页缓存」，只有当缓存满足某些条件的时候，才发起磁盘 I/O 的请求。

根据是「否利用操作系统的缓存」，可以把文件 I/O 分为直接 I/O 与非直接 I/O：

直接 I/O，不会发生内核缓存和用户程序之间数据复制，而是直接经过文件系统访问磁盘。
非直接 I/O，读操作时，数据从内核缓存中拷贝给用户程序，写操作时，数据从用户程序拷贝给内核缓存，再由内核决定什么时候写入数据到磁盘。

如果你在使用文件操作类的系统调用函数时，指定了 O_DIRECT 标志，则表示使用直接 I/O。如果没有设置过，默认使用的是非直接 I/O。

如果用了非直接 I/O 进行写数据操作，内核什么情况下才会把缓存数据写入到磁盘？

以下几种场景会触发内核缓存的数据写入磁盘：

在调用 write 的最后，当发现内核缓存的数据太多的时候，内核会把数据写到磁盘上；
用户主动调用 sync，内核缓存会刷到磁盘上；
当内存十分紧张，无法再分配页面时，也会把内核缓存的数据刷到磁盘上；
内核缓存的数据的缓存时间超过某个时间时，也会把数据刷到磁盘上；

阻塞与非阻塞 I/O VS 同步与异步 I/O [Top]

I/O 是分为两个过程的：

数据准备的过程
数据从内核空间拷贝到用户进程缓冲区的过程

阻塞 I/O: 当用户程序执行 read ，线程会被阻塞，一直等到内核数据准备好，并把数据从内核缓冲区拷贝到应用程序的缓冲区中，当拷贝过程完成，read 才会返回。
阻塞等待的是「内核数据准备好」和「数据从内核态拷贝到用户态」这两个过程。

非阻塞 I/O，非阻塞的 read 请求在数据未准备好的情况下立即返回，可以继续往下执行，此时应用程序不断轮询内核，直到数据准备好，内核将数据拷贝到应用程序缓冲区，read 调用才可以获取到结果。

最后一次 read 调用，获取数据的过程，是一个同步的过程，是需要等待的过程。这里的同步指的是内核态的数据拷贝到用户程序的缓存区这个过程。

为了解决NIO这种轮询方式改善了应用进程对 CPU 的利用率，于是 I/O 多路复用技术就出来了，如 select、poll，它是通过 I/O 事件分发，当内核数据准备好时，再以事件通知应用程序进行操作。

使用 select I/O 多路复用过程。注意，read 获取数据的过程(数据从内核态拷贝到用户态的过程)，也是一个同步的过程，需要等待

阻塞I/O、非阻塞I/O，还是基于非阻塞I/O的多路复用都是同步调用。因为它们在 read 调用时，内核将数据从内核空间拷贝到应用程序空间，过程都是需要等待的，也就是说这个过程是同步的，如果内核实现的拷贝效率不高，read 调用就会在这个同步过程中等待比较长的时间。

异步 I/O 是「内核数据准备好」和「数据从内核态拷贝到用户态」这两个过程都不用等待。

当我们发起 aio_read 之后，就立即返回，内核自动将数据从内核空间拷贝到应用程序空间，这个拷贝过程同样是异步的，内核自动完成的，和前面的同步操作不一样，应用程序并不需要主动发起拷贝动作。

用故事去理解这几种 I/O 模型举个你去饭堂吃饭的例子，你好比用户程序，饭堂好比操作系统。
阻塞 I/O 好比，你去饭堂吃饭，但是饭堂的菜还没做好，然后你就一直在那里等啊等，等了好长一段时间终于等到饭堂阿姨把菜端了出来(数据准备的过程)，但是你还得继续等阿姨把菜(内核空间)打到你的饭盒里(用户空间)，经历完这两个过程，你才可以离开。
非阻塞 I/O 好比，你去了饭堂，问阿姨菜做好了没有，阿姨告诉你没，你就离开了，过几十分钟，你又来饭堂问阿姨，阿姨说做好了，于是阿姨帮你把菜打到你的饭盒里，这个过程你是得等待的。
基于非阻塞的 I/O 多路复用好比，你去饭堂吃饭，发现有一排窗口，饭堂阿姨告诉你这些窗口都还没做好菜，等做好了再通知你，于是等啊等(select 调用中)，过了一会阿姨通知你菜做好了，但是不知道哪个窗口的菜做好了，你自己看吧。于是你只能一个一个窗口去确认，后面发现 5 号窗口菜做好了，于是你让 5 号窗口的阿姨帮你打菜到饭盒里，这个打菜的过程你是要等待的，虽然时间不长。打完菜后，你自然就可以离开了。
异步 I/O 好比，你让饭堂阿姨将菜做好并把菜打到饭盒里后，把饭盒送到你面前，整个过程你都不需要任何等待。

IO多路复用 [Top]

一个进程虽然任一时刻只能处理一个请求，但是处理每个请求的事件时，耗时控制在 1 毫秒以内，这样 1 秒内就可以处理上千个请求，把时间拉长来看，多个请求复用了一个进程，这就是多路复用，这种思想很类似一个 CPU 并发多个进程，所以也叫做时分多路复用。

select/poll/epoll 是内核提供给用户态的多路复用系统调用，进程可以通过一个系统调用函数从内核中获取多个事件。

select/poll/epoll 在获取事件时，先把所有连接（文件描述符）传给内核，再由内核返回产生了事件的连接，然后在用户态中再处理这些连接对应的请求即可。

select/poll [Top]

select 实现多路复用的方式是，将已连接的 Socket 都放到一个文件描述符集合，然后调用 select 函数将文件描述符集合拷贝到内核里，让内核来检查是否有网络事件产生。
检查方式：通过遍历文件描述符集合的方式，当检查到有事件产生后，将此 Socket 标记为可读或可写，接着再把整个文件描述符集合拷贝回用户态里，然后用户态还需要再通过遍历的方法找到可读或可写的 Socket，然后再对其处理。

对于 select 这种方式，需要进行 2 次「遍历」文件描述符集合，一次是在内核态里，一个次是在用户态里，而且还会发生 2 次「拷贝」文件描述符集合，先从用户空间传入内核空间，由内核修改后，再传出到用户空间中。

select 使用固定长度的BitsMap，表示文件描述符集合，而且所支持的文件描述符的个数是有限制的，在 Linux 系统中，由内核中的 FD_SETSIZE 限制，默认最大值为 1024，只能监听 0~1023 的文件描述符。

poll 不再用 BitsMap 来存储所关注的文件描述符，取而代之用动态数组，以链表形式来组织，突破了 select 的文件描述符个数限制，当然还会受到系统文件描述符限制。

poll 和 select 并没有太大的本质区别，都是使用「线性结构」存储进程关注的 Socket 集合，因此都需要遍历文件描述符集合来找到可读或可写的 Socket，时间复杂度为 O(n)，而且也需要在用户态与内核态之间拷贝文件描述符集合，这种方式随着并发数上来，性能的损耗会呈指数级增长。

epoll [Top]

epoll 通过两个方面，很好解决了 select/poll 的问题。epoll 是解决 C10K 问题的利器。

第一点，epoll 在内核里使用红黑树来跟踪进程所有待检测的文件描述字，增删改一般时间复杂度是 O(logn)。
第二点， epoll 使用事件驱动的机制，内核里维护了一个链表来记录就绪事件。给每个fd注册一个回调函数，当某个 socket 有事件发生时，通过回调函数内核会将其加入到这个就绪事件列表中。以此达到O（1）的时间复杂度

边缘触发和水平触发

使用边缘触发模式时，当被监控的 Socket 描述符上有可读事件发生时，服务器端只会从 epoll_wait 中苏醒一次，即使进程没有调用 read 函数从内核读取数据，也依然只苏醒一次，因此我们程序要保证一次性将内核缓冲区的数据读取完；
使用水平触发模式时，当被监控的 Socket 上有可读事件发生时，服务器端不断地从 epoll_wait 中苏醒，直到内核缓冲区数据被 read 函数读完才结束，目的是告诉我们有数据需要读取；

水平触发的意思是只要满足事件的条件，比如内核中有数据需要读，就一直不断地把这个事件传递给用户；而边缘触发的意思是只有第一次满足条件的时候才触发，之后就不会再传递同样的事件了。

简单说——水平触发代表了一种“状态”。边沿触发代表了一个“事件”。

select/poll 只有水平触发模式，epoll 默认的触发模式是水平触发，但是可以根据应用场景设置为边缘触发模式。一般来说，边缘触发的效率比水平触发的效率要高，因为边缘触发可以减少 epoll_wait 的系统调用次数，系统调用也是有一定的开销的的，毕竟也存在上下文的切换。

边缘触发模式一般和非阻塞 I/O 搭配使用，程序会一直执行 I/O 操作，直到系统调用（如 read 和 write）返回错误，错误类型为 EAGAIN 或 EWOULDBLOCK。 多路复用 API 返回的事件并不一定可读写的，如果使用阻塞 I/O，那么在调用 read/write 时则会发生程序阻塞，因此最好搭配非阻塞 I/O，以便应对极少数的特殊情况。

Reactor [Top]

单Reactor单进程/线程

进程里有 Reactor、Acceptor、Handler 这三个对象：

Reactor 对象的作用是监听和分发事件；
Acceptor 对象的作用是获取连接；
Handler 对象的作用是处理业务；

介绍下「单 Reactor 单进程」这个方案：

Reactor 对象通过 select （IO 多路复用接口）监听事件，收到事件后通过 dispatch 进行分发，具体分发给 Acceptor 对象还是 Handler 对象，还要看收到的事件类型；
如果是连接建立的事件，则交由 Acceptor 对象进行处理，Acceptor 对象会通过 accept 方法获取连接，并创建一个 Handler 对象来处理后续的响应事件；
如果不是连接建立事件，则交由当前连接对应的 Handler 对象来进行响应；
Handler 对象通过 read -> 业务处理 -> send 的流程来完成完整的业务流程。

2 个缺点：

第一个缺点，因为只有一个进程，无法充分利用 多核 CPU 的性能；
第二个缺点，Handler 对象在业务处理时，整个进程是无法处理其他连接的事件的，如果业务处理耗时比较长，那么就造成响应的延迟；

单 Reactor 单进程的方案不适用计算机密集型的场景，只适用于业务处理非常快速的场景。

单 Reactor 多线程 / 多进程

前三个步骤和单 Reactor 单线程方案是一样的，接下来的步骤：

Handler 对象不再负责业务处理，只负责数据的接收和发送，Handler 对象通过 read 读取到数据后，会将数据发给子线程里的 Processor 对象进行业务处理；
子线程里的 Processor 对象就进行业务处理，处理完后，将结果发给主线程中的 Handler 对象，接着由 Handler 通过 send 方法将响应结果发送给 client；

单 Reactor 多线程的方案优势在于能够充分利用多核 CPU 的性能，那既然引入多线程，那么自然就带来了多线程竞争资源的问题。

「单 Reactor」的模式还有个问题，因为一个 Reactor 对象承担所有事件的监听和响应，而且只在主线程中运行，在面对瞬间高并发的场景时，容易成为性能的瓶颈的地方。

多 Reactor 多进程 / 线程

方案详细说明如下：

主线程中的 MainReactor 对象通过 select 监控连接建立事件，收到事件后通过 Acceptor 对象中的 accept 获取连接，将新的连接分配给某个子线程；
子线程中的 SubReactor 对象将 MainReactor 对象分配的连接加入 select 继续进行监听，并创建一个 Handler 用于处理连接的响应事件。
如果有新的事件发生时，SubReactor 对象会调用当前连接对应的 Handler 对象来进行响应。
Handler 对象通过 read -> 业务处理 -> send 的流程来完成完整的业务流程。

两个开源软件 Netty 和 Memcache 都采用了「多 Reactor 多线程」的方案。

Proactor [Top]

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

Reactor 可以理解为「来了事件操作系统通知应用进程，让应用进程来处理」，而 Proactor 可以理解为「来了事件操作系统来处理，处理完再通知应用进程」

无论是 Reactor，还是 Proactor，都是一种基于「事件分发」的网络编程模式，区别在于 Reactor 模式是基于「待完成」的 I/O 事件，而 Proactor 模式则是基于「已完成」的 I/O 事件。

page cache [Top]

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

page与page cache [Top]

page 是内存管理分配的基本单位， Page Cache 由多个 page 构成。page 在操作系统中通常为 4KB 大小(32bits/64bits)，而 Page Cache 的大小则为 4KB 的整数倍。

Linux 系统上供用户可访问的内存分为两个类型，即：

File-backed pages：文件备份页也就是 Page Cache 中的 page，对应于磁盘上的若干数据块；对于这些页最大的问题是脏页回盘；
Anonymous pages：匿名页不对应磁盘上的任何磁盘数据块，它们是进程的运行是内存空间(例如方法栈、局部变量表等属性)；

内存是一种珍惜资源，当内存不够用时，内存管理单元(Memory Management Unit)需要提供调度算法来回收相关内存空间。内存空间回收的方式通常就是 swap，即交换到持久化存储设备上。

File-backed pages(Page Cache)的内存回收代价较低。Page Cache 通常对应于一个文件上的若干顺序块，因此可以通过顺序 I/O 的方式落盘。另一方面，如果 Page Cache 上没有进行写操作(所谓的没有脏页)，甚至不会将 Page Cache 回盘，因为数据的内容完全可以通过再次读取磁盘文件得到。

Anonymous pages 的内存回收代价较高。这是因为 Anonymous pages 通常随机地写入持久化交换设备。另一方面，无论是否有写操作，为了确保数据不丢失，Anonymous pages 在 swap 时必须持久化到磁盘。

Page Cache 与 buffer cache [Top]

~ free -m
             total       used       free     shared    buffers     cached
Mem:        128956      96440      32515          0       5368      39900
-/+ buffers/cache:      51172      77784
Swap:        16002          0      16001

cached 列表示当前的页缓存(Page Cache)占用量，buffers 列表示当前的块缓存(buffer cache)占用量。

Page Cache 用于缓存文件的页数据，buffer cache 用于缓存块设备(如磁盘)的块数据。页是逻辑上的概念，因此 Page Cache 是与文件系统同级的；块是物理上的概念，因此 buffer cache 是与块设备驱动程序同级的。

Page Cache 与 buffer cache 的共同目的都是加速数据 I/O：写数据时首先写到缓存，将写入的页标记为 dirty，然后向外部存储 flush，也就是缓存写机制中的 write-back(另一种是 write-through，Linux 默认情况下不采用)；读数据时首先读取缓存，如果未命中，再去外部存储读取，并且将读取来的数据也加入缓存。操作系统总是积极地将所有空闲内存都用作 Page Cache 和 buffer cache，当内存不够用时也会用 LRU 等算法淘汰缓存页。

Page Cache 中的每个文件都是一棵基数树(radix tree，本质上是多叉搜索树)，树的每个节点都是一个页。根据文件内的偏移量就可以快速定位到所在的页

基数树

Page Cache 与预读 [Top]

操作系统为基于 Page Cache 的读缓存机制提供预读机制(PAGE_READAHEAD)，一个例子是：

用户线程仅仅请求读取磁盘上文件 A 的 offset 为 0-3KB 范围内的数据，由于磁盘的基本读写单位为 block(4KB)，于是操作系统至少会读 0-4KB 的内容，这恰好可以在一个 page 中装下。
但是操作系统出于局部性原理会选择将磁盘块 offset [4KB,8KB)、[8KB,12KB) 以及 [12KB,16KB) 都加载到内存，于是额外在内存中申请了 3 个 page；

持久化的一致性&可靠性 [Top]

任何系统引入缓存，就会引发一致性问题。文件 = 数据 + 元数据。元数据用来描述文件的各种属性，也必须存储在磁盘上。因此，保证文件一致性其实包含了两个方面：数据一致+元数据一致。

当前 Linux 下以两种方式实现文件一致性：

Write Through(写穿)：向用户层提供特定接口，应用程序可主动调用接口来保证文件一致性；
Write back(写回)：系统中存在定期任务(表现形式为内核线程)，周期性地同步文件系统中文件脏数据块，这是默认的 Linux 一致性方案；

系统中存在多个回写时机，第一是应用程序主动调用回写接口(fsync，fdatasync 以及 sync 等)，第二管理线程周期性地唤醒设备上的回写线程进行回写，第三是某些应用程序/内核任务发现内存不足时要回收部分缓存页面而事先进行脏页面回写，设计一个统一的框架来管理这些回写任务非常有必要。

Write Through 与 Write back 在持久化的可靠性上有所不同：

Write Through 以牺牲系统 I/O 吞吐量作为代价，向上层应用确保一旦写入，数据就已经落盘，不会丢失；
Write back 在系统发生宕机的情况下无法确保数据已经落盘，因此存在数据丢失的问题。不过，在程序挂了，例如被 kill -9，Page Cache 中的数据操作系统还是会确保落盘；

page cache 优劣势 [Top]

Page Cache 的优势

加快数据访问。如果数据能够在内存中进行缓存，那么下一次访问就不需要通过磁盘 I/O 了，直接命中内存缓存即可。
减少 I/O 次数，提高系统磁盘 I/O 吞吐量。得益于 Page Cache 的缓存以及预读能力，而程序又往往符合局部性原理，因此通过一次 I/O 将多个 page 装入 Page Cache 能够减少磁盘 I/O 次数，进而提高系统磁盘 I/O 吞吐量。

Page Cache 的劣势

需要占用额外物理内存空间，物理内存在比较紧俏的时候可能会导致频繁的 swap 操作，最终导致系统的磁盘 I/O 负载的上升。
在传输大文件(GB 级别的文件)的时候，PageCache 会不起作用。其他「热点」的小文件可能就无法充分使用到 PageCache，于是这样磁盘读写的性能就会下降了；
对应用层并没有提供很好的管理 API，几乎是透明管理。应用层即使想优化 Page Cache 的使用策略也很难进行。因此一些应用选择在用户空间实现自己的 page 管理，而不使用 page cache，例如 MySQL InnoDB 存储引擎以 16KB 的页进行管理。
Page Cache 最后一个缺陷是在某些应用场景下比 Direct I/O 多一次磁盘读 I/O 以及磁盘写 I/O。

缓存文件 I/O：用户空间要读写一个文件并不直接与磁盘交互，而是中间夹了一层缓存，即 page cache；

直接文件 I/O：用户空间读取的文件直接与磁盘交互，没有中间 page cache 层；

Direct I/O ：

Write 操作：由于其不使用 page cache，所以其进行写文件，如果返回成功，数据就真的落盘了(不考虑磁盘自带的缓存)；
Read 操作：由于其不使用 page cache，每次读操作是真的从磁盘中读取，不会从文件系统的缓存中读取。

参考资料 [Top]

Linux 的 Page Cache

直接内存访问 [Top]

在没有 DMA (Direct Memory Access)技术前，I/O 的过程是这样的：

CPU 发出对应的指令给磁盘控制器，然后返回；
磁盘控制器收到指令后，于是就开始准备数据，会把数据放入到磁盘控制器的内部缓冲区中，然后产生一个中断；
CPU 收到中断信号后，停下手头的工作，接着把磁盘控制器的缓冲区的数据一次一个字节地读进自己的寄存器，然后再把寄存器里的数据写入到内存，而在数据传输的期间 CPU 是无法执行其他任务的。

DMA直接内存访问(Direct Memory Access): 在进行 I/O 设备和内存的数据传输的时候，数据搬运的工作全部交给 DMA 控制器，而 CPU 不再参与任何与数据搬运相关的事情，这样 CPU 就可以去处理别的事务。

具体过程：

用户进程调用 read 方法，向操作系统发出 I/O 请求，请求读取数据到自己的内存缓冲区中，进程进入阻塞状态；
操作系统收到请求后，进一步将 I/O 请求发送 DMA，然后让 CPU 执行其他任务；
DMA 进一步将 I/O 请求发送给磁盘；
磁盘收到 DMA 的 I/O 请求，把数据从磁盘读取到磁盘控制器的缓冲区中，当磁盘控制器的缓冲区被读满后，向 DMA 发起中断信号，告知自己缓冲区已满；
DMA 收到磁盘的信号，将磁盘控制器缓冲区中的数据拷贝到内核缓冲区中，此时不占用 CPU，CPU 可以执行其他任务；
当 DMA 读取了足够多的数据，就会发送中断信号给 CPU；
CPU 收到 DMA 的信号，知道数据已经准备好，于是将数据从内核拷贝到用户空间，系统调用返回；

整个数据传输的过程，CPU 不再参与数据搬运的工作，而是全程由 DMA 完成，但是 CPU 在这个过程中也是必不可少的，因为传输什么数据，从哪里传输到哪里，都需要 CPU 来告诉 DMA 控制器。

零拷贝 [Top]

read(file, tmp_buf, len);
write(socket, tmp_buf, len);

期间共发生了 4 次用户态与内核态的上下文切换，因为发生了两次系统调用，一次是 read() ，一次是 write()，每次系统调用都得先从用户态切换到内核态，等内核完成任务后，再从内核态切换回用户态。

发生了 4 次数据拷贝，其中两次是 DMA 的拷贝，另外两次则是通过 CPU 拷贝的：

第一次拷贝，把磁盘上的数据拷贝到操作系统内核的缓冲区里，这个拷贝的过程是通过 DMA 搬运的。
第二次拷贝，把内核缓冲区的数据拷贝到用户的缓冲区里，于是我们应用程序就可以使用这部分数据了，这个拷贝到过程是由 CPU 完成的。
第三次拷贝，把刚才拷贝到用户的缓冲区里的数据，再拷贝到内核的 socket 的缓冲区里，这个过程依然还是由 CPU 搬运的。
第四次拷贝，把内核的 socket 缓冲区里的数据，拷贝到网卡的缓冲区里，这个过程又是由 DMA 搬运的。

上下文切换到成本并不小，一次切换需要耗时几十纳秒到几微秒，虽然时间看上去很短，但是在高并发的场景下，这类时间容易被累积和放大，从而影响系统的性能。要想提高文件传输的性能，就需要减少「用户态与内核态的上下文切换」和「内存拷贝」的次数。

优化的思路：

要想减少上下文切换的次数，就要减少系统调用的次数。
因为文件传输的应用场景中，在用户空间我们并不会对数据「再加工」，所以数据实际上可以不用搬运到用户空间，因此用户的缓冲区是没有必要存在的。

零拷贝技术实现的方式通常有 2 种：

mmap + write
sendfile

mmap + write [Top]

buf = mmap(file, len);
write(sockfd, buf, len);

通过使用 mmap() 来代替 read()，可以减少一次数据拷贝的过程。

mmap() 系统调用函数会直接把内核缓冲区里的数据「映射」到用户空间，这样，操作系统内核与用户空间就不需要再进行任何的数据拷贝操作。

具体过程如下：

应用进程调用了 mmap() 后，DMA 会把磁盘的数据拷贝到内核的缓冲区里。接着，应用进程跟操作系统内核「共享」这个缓冲区；
应用进程再调用 write()，操作系统直接将内核缓冲区的数据拷贝到 socket 缓冲区中，这一切都发生在内核态，由 CPU 来搬运数据；
最后，把内核的 socket 缓冲区里的数据，拷贝到网卡的缓冲区里，这个过程是由 DMA 搬运的。

但这还不是最理想的零拷贝，因为仍然需要通过 CPU 把内核缓冲区的数据拷贝到 socket 缓冲区里，而且仍然需要 4 次上下文切换，因为系统调用还是 2 次。

sendfile [Top]

sendfile()系统调用不需要将数据拷贝或者映射到应用程序地址空间中去，所以 sendfile() 只是适用于应用程序地址空间不需要对所访问数据进行处理的情况

sendfile()系统调用，可以直接把内核缓冲区里的数据拷贝到 socket 缓冲区里，不再拷贝到用户态，这样就只有 2 次上下文切换，和 3 次数据拷贝

网卡支持 SG-DMA(The Scatter-Gather Direct Memory Access)技术(和普通的 DMA 有所不同)，可以进一步减少通过 CPU 把内核缓冲区里的数据拷贝到 socket 缓冲区的过程。

零拷贝(Zero-copy)技术，因为我们没有在内存层面去拷贝数据，也就是说全程没有通过 CPU 来搬运数据，所有的数据都是通过 DMA 来进行传输的。

零拷贝技术的文件传输方式相比传统文件传输的方式，减少了 2 次上下文切换和数据拷贝次数，只需要 2 次上下文切换和数据拷贝次数，就可以完成文件的传输，而且 2 次的数据拷贝过程，都不需要通过 CPU，2 次都是由 DMA 来搬运。所以，总体来看，零拷贝技术可以把文件传输的性能提高至少一倍以上

零拷贝技术的应用: Kafka。使用了零拷贝能够缩短 65% 的时间，大幅度提升了机器传输数据的吞吐量。

计算机组成原理 [Top]

局部性原理 [Top]

// TODO 计算机组成原理：局部性原理

中间件设计资料 [Top]

通常在大部分组件设计时，往往会选择一种主要介质来存储、另一种介质作为辅助使用。就拿 redis 来说，它主要采用内存存储数据，磁盘用来做辅助的持久化。拿 RabbitMQ 举例，它也是主要采用内存存储消息，但也支持将消息持久化到磁盘。而 RocketMQ、Kafka、Pulsar 这种，则是数据主要存储在磁盘，通过内存来主力提升系统的性能。关系型数据库例如 mysql 这种组件也是主要采用磁盘组织数据，合理利用内存提升性能。

针对采用内存存储数据的方案而言，难点一方面在于如何在不降低访问效率的情况下，充分利用有限的内存空间来存储尽可能多的数据，这个过程中少不了对数据结构的选型、优化；另一方面在于如何保证数据尽可能少的丢失，我们可以看到针对此问题的解决方案通常是快照+广泛意义的 wal 文件来解决。此类典型的代表就是 redis 啦。

针对采用磁盘存储数据的方案而言，难点一方面在于如何根据系统所要解决的特点场景进行合理的对磁盘布局。读多写少情况下采用 b+树方式存储数据；写多读少情况下采用 lsm tree 这类方案处理。另一方面在于如何尽可能减少对磁盘的频繁访问，一些做法是采用 mmap 进行内存映射，提升读性能；还有一些则是采用缓存机制缓存频繁访问的数据。还有一些则是采用巧妙的数据结构布局，充分利用磁盘预读特性保证系统性能。

总的来说，针对写磁盘的优化，要不采用顺序写提升性能、要不采用异步写磁盘提升性能(异步写磁盘时需要结合 wal 保证数据的持久化，事实上 wal 也主要采用顺序写的特性)；针对读磁盘的优化，一方面是缓存、另一方面是 mmap 内存映射加速读。

上述这些存储方案上权衡的选择在 kafka、RocketMQ、Pulsar 中都可以看到。其实抛开消息队列而言，这些存储方案的选择上无论是关系型数据库还是 kv 型组件都是通用的。

消息队列背后的设计思想

Files

OPERATING_SYSTEM.md

Latest commit

History

OPERATING_SYSTEM.md

File metadata and controls