进程和线程是什么?

进程是程序的一次执行过程，是系统运行程序和资源分配调度的基本单位，是资源分配的最小单位。一个进程可以有多个线程，至少有一个线程。进程在执行过程中拥有独立的地址空间，多个线程共享该进程的地址空间。
- 进程创建时会分配哪些资源：
  - 内存
  - FD表
  - 外设
  - 信号量
  - 消息队列
  - PCB（progress control block），进程控制块，里面包含了很多进程相关的信息。
  - 。。。
线程是进程的子任务是CPU调度的最小单位，线程必须要依赖进程存在。
- 线程包含哪些资源：
  - 栈
  - 程序计数器
  - 堆内存
  - 所属进程的资源
  - 。。。

协程是什么？

协程是线程下面的概念，一个线程包含多个协程。
协程是在线程基础之上，比线程更加轻量级的微线程，协程是一个线程之内的，由程序员通过代码来控制协程间的调度，是用户态行为，并不由操作系统来调度，所以不需要上下文切换，也不需要线程之间锁的竞争，效率更高。
线程默认的栈大小是MB级别，而协程是KB级别，更加轻量。
协程拥有自己的寄存器上下文（PC / SP / DX）和栈，协程间切换需要保存和改变的数据量更少。协程调度切换时，将寄存器上下文和栈保存到线程的堆区。
适用于高并发的同步阻塞的场景。例如出现长时间的IO操作时，可以通过让出这个等待IO的协程，去执行其他协程，提高CPU利用率和减少线程上下文切换带来的开销。
代码层面再来理解协程：
- 先讲讲函数：函数都是通过栈来实现层级调用的，比如A调用B，B又调用了C，C执行完毕返回，B执行完毕返回，最后是A执行完毕。函数的调用总是一个入口一个返回，调用顺序是明确的。
- 而协程则不同，它是个特殊一点的函数，在这个特殊函数中可以随时中断挂起，去执行另一个函数，等时机合适时再接着回来执行，类似于中断机制，不存在栈式调用。

并发与并行的区别

并发：一段时间内交替执行多件事，但在某一时刻只能执行一件事
并行：同一时刻同时执行同时多件事

同步和异步的区别

同步：发出一个调用时，在没得到结果前不能返回，需要一直等待
异步：发出一个调用后，不需要等待结果就可以返回

进程有哪几种状态？

跟线程非常像。5种状态：

创建（create）
就绪（ready）
运行（running）
阻塞（waiting）
结束（terminated）

进程是怎么被控制管理的?

在操作系统中，用进程控制块（process control block，PCB）这样的数据结构来描述一个进程的。PCB 是进程存在的唯一标识，一个进程存在，必然会有一个 PCB，如果进程消失了， PCB 也会随之消失。

PCB包含了哪些信息？

进程描述信息：
- 进程标识符：标识各个进程，每个进程都有一个并且唯一的标识符；
- 用户标识符：进程归属的用户，用户标识符主要为共享和保护服务；
进程控制和管理信息：
- 进程当前状态，如 new、ready、running、waiting 或 blocked 等；
- 进程优先级：进程抢占 CPU 时的优先级；
资源分配清单：
- 有关内存地址空间或虚拟地址空间的信息，所打开文件的列表和所使用的 I/O 设备信息。
CPU 相关信息（进程上下文切换时的上下文数据）：
- CPU 中各个寄存器的值，当进程被切换时，CPU 的状态信息都会被保存在相应的 PCB 中，以便进程重新执行时，能从断点处继续执行。
。。。

PCB是如何组织的？

通常是通过链表的方式进行组织，把具有相同状态的进程链在一起，组成各种队列。如：就绪队列、阻塞队列等。（除了链表，还有索引方式：将同一状态的进程组织在一个索引表中，索引表项指向相应的 PCB，不同状态对应不同的索引表。但一般会选择链表，因为进程状态是多变的，链表能够更加灵活的插入和删除。）

进程的控制就是内核通过操作各个队列上的pcb来实现。

进程的上下文切换

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

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

进程间通信（IPC）有哪些方法？

每个进程的用户地址空间都是独立的，一般而言是不能互相访问的，但内核空间是每个进程都共享的，所以进程之间要通信必须通过内核。

有7种：

管道/匿名管道（pipe）：
- 没有名字，用完就销毁。
- 只支持半双工通信。
- 遵循先进先出。
- 匿名管道是特殊的文件，只存在于内存，是内核的一串缓存，不存于文件系统中（没有实际载体）。
- 通过系统调用创建一个匿名管道，并返回了两个fd：
```
int pipe(int fd[2])
```
- 若要实现进程间通信，就需要创建两组fd/两个管道，可以使用 fork 创建子进程，创建的子进程会复制父进程的文件描述符，这样就做到了两个进程各有两个「 fd[0] 与 fd[1]」，两个进程就可以通过各自的 fd 写入和读取同一个管道文件实现跨进程通信了。
- 只能在父子进程或兄弟进程间通信。
```
ps auxf | grep mysql 
#「|」竖线就是一个管道，它的功能是将前一个命令（ps auxf）的输出，作为后一个命令（grep mysql）的输入
# 这里的ps和grep是shell创建的两个子进程，两者属于兄弟进程
```

命名管道（FIFO）：
- 有名字。
- 可实现任意两个进程间的通信。
- 遵循先进先出。
- 通过**系统调用mkfifo()**创建命名管道：
```
int mkfifo(const char *path, mode_t mode);
```
- 命名管道是特殊的文件，名字存在于文件系统中（有实际载体），内容存放在内核的缓存中。
- 常用于client-server应用程序中，FIFO 用作汇聚点，在客户进程和服务器进程之间传递数据。
信号（signal）：
- 是对中断机制的一种模拟。
- 是一种异步通信机制。
- 用于通知某个进程某个事件已经发生。
消息队列（message queue）：
- 独立于进程存在，是保存在内核中的消息链表。
- 可随机、选择性地读取，不一定要FIFO。避免了管道和命名管道的同步阻塞问题。
信号量（semaphore）：
- 是一个整数计数器，表示当前还能被使用的资源数量，通过pv操作来进行控制。
- 用于多个进程对同一个共享数据的访问，对这些访问做同步处理（做线程安全处理）。
共享内存（shared memory）：
- 拿出一块虚拟地址空间来，映射到相同的物理内存中。
- 多个进程共享同一块内存空间，某个进程对这内存上的数据进行修改能保证对所有进程可见。
- 数据不需要进程间的拷贝，是最快的一种IPC。
- 对共享数据的操作需要同步处理，要通过互斥锁或信号量等方式。
socket：
- 主要用于不同主机间（上面那些都是同一主机上不同进程）的进程间通信。
- 通过网络进行通信。
- socket只能实现一对一的通信。IO多路复用能实现一监听多。

进程调度算法有哪些？

6种：

不同环境的调度算法目标不同，因此需要针对不同环境来讨论调度算法。

批处理系统（服务器）

批处理系统没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量和周转时间（从提交到终止的时间）。所以没有进程间的轮转。

先来先服务算法：
- 最先进入就绪队列的进程先执行，完全执行完了再执行下一个进程。
- 利于长作业，不利于短作业，短作业要等待较长的时间。
短作业优先算法：
- 就绪队列中预估执行时间最短的进程先执行，完全执行完了再执行下一个进程。
- 不利于长作业，若一直有短作业进入就绪队列，长作业就会饿死。
最短剩余时间优先算法：
- ~~将新到达的进程的整体执行时间与正在执行的进程的剩余执行时间做比较，若新到达的进程的执行时间更短，就阻塞当前进程，去执行这个新进程。~~
高响应比优先算法
- 权衡了短作业和长作业。
- 每次进行进程调度时，先计算「响应比优先级」，然后把「响应比优先级」最高的进程投入运行。
- 具体公式如下，等待时间是进程到现在为止阻塞等待了多久。

交互式系统（pc）

交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速响应，所以需要轮转。

时间片轮转算法：（用得最广）
- 每个进程只能在拿到时间片时，在时间片内被cpu执行。
- 效率取决于时间片大小该分多长。一般为20ms-50ms比较好。
优先级调度算法：
- 每个进程都分配一个优先级，优先级高的先执行。其可以分成非抢占式和抢占式的。
- 为了防止优先级低的线程饿死，可以随着等待时间的增大而提高优先级。
多级反馈队列算法：
- 多级反馈队列是为需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,…。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，一个需要轮转100次的进程只需要轮转 7 次就能执行完。
- 每个队列优先级也不同，最上面的优先级最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。
- 可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

死锁

什么是死锁？

多个进程/线程同时阻塞，它们中的一个或者全部都在等待某个资源的释放，它们在无限期地等待，程序不能运行下去。

死锁的必要条件有哪些？

4个：必须同时满足才能出现死锁

互斥：一次只能有一个进程/线程占有该资源。
占有并等待：一个进程/线程至少占有一个资源，且阻塞等待另一个进程/线程占有的资源。
非抢占：资源不能被抢占，只能等占有资源的进程/线程释放资源。
循环等待：有一组等待进程 {P0, P1,..., Pn}， P0 等待的资源被 P1 占有，P1 等待的资源被 P2 占有，…，Pn-1 等待的资源被 Pn 占有，Pn 等待的资源被 P0 占有。

如何避免死锁的发生？

只需破坏上面的其中一个条件就行。常见的方法是资源有序分配法，来破坏循环等待的条件。也就是多个线程都是按同样的顺序来依次获取多个资源。如：当线程 A 是先尝试获取资源 s1，然后尝试获取资源 s2 ，线程 B 同样也是先尝试获取资源 A，然后尝试获取资源 B。

用户态vs内核态

用户态和内核态是操作系统层面的概念，并不是某个地方，对应到CPU层面就是CPU处于什么工作模式/工作状态。所以，进入内核态并不是进入了某个地方，而是CPU工作模式的切换。当进入用户态时，程序只能访问用户空间；当进入内核态时，才可以访问内核空间。
内核态是CPU的特权模式，拥有最高权限，能执行操作硬件的所有指令。用户态就是用户（普通）模式，最低权限，只能执行一部分指令。
因特尔X86的CPU分为4个权限/工作模式，Ring0-Ring3，R0是最高权限模式，可以执行所有指令，R3是最低权限模式，只能执行指令集中的一部分指令。而在Linux操作系统里只有两种权限等级，R0和R3，R0就是内核态，R3就是用户态。
为什么这样设计？最大的原因就是为了防止用户程序越级去直接使用操作系统的敏感的高权限的指令，从而影响程序运行和操作系统安全。（操作系统本身也是个程序）
用户态切换内核态的3种方式：
- 系统调用：属于软中断。
- (硬)中断：外设，属于硬中断。
- 异常：如缺页异常。

内存管理是干啥的？

主要管理内存的分配和回收，以及虚拟内存和物理内存之间的映射操作等。

常见的内存管理机制有哪些？

连续分配管理（分配给一个应用程序用的内存是连续的一整块）
- 块式管理：把内存分成多个固定大小的块，一个应用程序就用这一整块，若程序需要的内存比较小，就浪费了很多内存（碎片）。
非连续分配管理（一个应用程序用的内存是离散分布的）
- 页式管理：
  - 把内存分成多个固定大小的页，页比较小，提供细粒度的内存管理，减少内存碎片。
  - 通过页表来维护虚拟内存与物理内存的映射关系。
  - 页的大小固定（在 Linux 下，每一页的大小为 4KB），操作系统决定，程序员不能修改。
  - 缺点：页比较小，页的数量就比较多，页表也就变得比较大，而且每个进程都有自己的页表，所有页表就要占用很大的空间了，所以也就设计出了多级页表来优化。
- 段式管理：
  - 一个段拥有一个独立的地址空间，每个段长度可以不同，也可以动态增长，取决于运行的程序。可以由程序员显式地划分。
  - 每个段可以代表某个具体的意义，且地址独立，段与段之间不会随着长度的动态增长而互相覆盖。
  - 通过段表来维护虚拟段与物理段的映射关系。
  - 缺点：比较容易产生内存碎片。解决办法是内存交换：某进程使用的内存数据转到硬盘的Swap 空间上，再将其装载到内存中，并紧挨着已使用的内存后面，如果要交换的内存比较大，效率就会比较低，系统会出现卡顿，所以在虚拟内存的设计中，分页是主流方案，因为要交换的内存大小是比较小的。
- 段页式管理：
  - 内存分成若干段，每个段内又分成多个固定大小的页，段与段之间和段内都是离散的。
  - 既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。
  - 地址结构就由段号、段内页号和页内位移三部分组成。每一个程序一张段表，每个段又建立一张页表，段表中的地址是页表的起始地址，而页表中的地址则为某页的物理页号。
- 分段和分页的比较：
  - 两者都能提高内存利用率。两者都是离散存储。但页内和段内都是连续的。
  - 对程序员的透明性：分页透明，但是分段需要程序员显式划分每个段。
  - 地址空间的维度：分页是一维地址空间，分段是二维的。
  - 大小是否可以改变：页的大小不可变，段的大小可以动态改变。
  - 出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。

什么是虚拟内存？

虚拟内存其实是有分段和分页的，只不过分页的效率更高，用的比较多。

虚拟内存为每个进程提供了一块等大（大小可设置，可以设置得比物理内存大）的连续完整的私有的内存空间（让程序误以为它独占一整个内存），把内存空间扩展到硬盘空间。有了虚拟内存能够运行多个程序，使进程能互相隔离互不影响（单片机没有操作系统，cpu直接操作内存的物理地址，所以不能运行多个程序）。
虚拟内存分成若干页，这些页被映射到物理内存的帧上（不需要连续，也不需要物理内存中真实存在），当程序引用到不在物理内存中的页时，会触发缺页异常，将缺失的页从硬盘换入（swap in）物理内存中并重新执行指令。

分页的方式使得我们在加载程序的时候，不再需要一次性都把程序加载到物理内存中。我们完全可以在进行虚拟内存和物理内存的页之间的映射之后，并不真的把页加载到物理内存里，而是只有在程序运行中，需要用到对应虚拟内存页里面的指令和数据时，再加载到物理内存里面去。

通过页表来维护虚拟内存（页）和物理内存（帧）的映射关系。如果物理内存空间不够，就会通过页面置换算法（类似于内存淘汰）把一些页换出（swap out）到硬盘中的swap分区（swap机制）。
CPU通过虚拟地址访问物理内存，需要通过MMU（内存管理单元）将虚拟地址转换成物理地址，再用物理地址去访问物理内存。

页面置换算法有哪些？

OPT（最佳）：所选择的被换出的页面将是最长时间内不再被访问的，通常可以保证获得最低的缺页率。是一种理论上的算法，无法实现，因为无法知道一个页面多长时间不再被访问。
FIFO（先进先出）：缺页率很高。
LRU（最近最久未使用）：需要维护LRU链表，且链表上的操作性能比较差，比较少用。
LFU（最不常用）：需要统计某个页被访问的频率。
CLOCK（时钟置换算法）

多级页表

避免把全部页表一直放在内存中占用过多空间，特别是那些根本就不需要的页表就不需要保留在内存中，应用了空间局部性原理。
时间换空间。
一级页表（并不是真正的“页表”，可以理解成二级页表的目录）就可以覆盖整个 4GB 虚拟地址空间，但如果某个一级页表的页表项没有被用到，也就不需要创建这个页表项对应的二级页表了，即在需要时才创建二级页表。下面是32位系统：

对于 64 位的系统，两级分页肯定不够了，就变成了四级分页，分别是：
- 全局页目录项 PGD（Page Global Directory）；
- 上层页目录项 PUD（Page Upper Directory）；
- 中间页目录项 PMD（Page Middle Directory）；
- 页表项 PTE（Page Table Entry）；

TLB

（不是redis数据结构那个快表）

多级页表解决了空间占用高的问题，但这也使地址转换的速度降低了，TLB就是页表的缓存来提高速度，它是CPU 芯片中一个专门存放程序最常访问的页表项的 Cache。
空间换时间。
有了 TLB 后，那么 CPU 在寻址时，会先查 TLB，如果没找到，才会继续查常规的页表。TLB 的命中率其实是很高的，因为程序最常访问的页就那么几个。

malloc()是如何分配内存的？

linux的用户空间的内存分布：

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

在这 6 个内存段中，堆和文件映射段的内存是动态分配的，即使用 C 标准库的 malloc() 或者 mmap()来动态分配内存。

malloc 申请内存的时候，会有两种方式向操作系统申请堆内存。

如果用户分配的内存小于 128 KB，通过 brk() 系统调用从堆分配内存；
如果用户分配的内存大于 128 KB，通过 mmap() 系统调用在文件映射区域分配内存；

不同的 glibc 版本定义的阈值也是不同的。

malloc() 分配的是虚拟内存，只有在访问已分配的虚拟地址空间时，触发缺页中断，操作系统才会建立虚拟内存和物理内存的映射关系。
malloc() 在分配内存的时候，并不是老老实实按用户预期申请的字节数来分配内存空间大小，而是会预分配更大的空间作为内存池。

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

malloc 通过 brk() 方式申请的内存，free 释放内存的时候，并不会把内存归还给操作系统，而是缓存在 malloc 的内存池中，待下次使用；（页表中还存在虚拟内存页和物理帧的映射关系，只是不使用了而已）
malloc 通过 mmap() 方式申请的内存，free 释放内存的时候，会把内存归还给操作系统，内存得到真正的释放。（页表中虚拟内存页和物理帧的映射关系取消了，如同完全没有被分配过一样）

为什么不全部使用 mmap 来分配？

如果频繁通过 mmap 分配的内存话，不仅每次都会发生运行态的切换，还每次在第一次访问虚拟地址后都发生缺页中断（因为free的时候内存直接释放了），这样会导致 CPU 消耗较大。

通过 brk() 系统调用在堆空间申请内存的时候，由于堆空间是连续的，所以直接预分配更大的内存来作为内存池，当内存释放的时候，就缓存在内存池中。等下次在申请内存的时候，就直接从内存池取出对应的内存块就行了，而且可能这个内存块的虚拟地址与物理地址的映射关系还存在，这样不仅减少了系统调用的次数，也减少了缺页中断的次数，这将大大降低 CPU 的消耗。

为什么不全部使用 brk 来分配？

频繁的malloc和free容易出现内存碎片。如果我们连续申请了 10k，20k，30k 这三片内存，如果 10k 和 20k 这两片释放了，变为了空闲内存空间，如果下次申请的内存小于 30k，那么就可以重用这个空闲内存空间。但是如果下次申请的内存大于 30k，没有可用的空闲内存空间，必须向 OS 申请，实际使用内存继续增大。

因此，随着系统频繁地 malloc 和 free ，尤其对于小块内存，堆内将产生越来越多不可用的碎片，导致“内存泄露”。而这种“泄露”现象使用 valgrind 是无法检测出来的。

物理内存满了会发生什么?

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

后台内存回收（kswapd）：在物理内存紧张的时候，会唤醒 kswapd 内核线程来回收内存，这个回收内存的过程异步的，不会阻塞进程。
直接内存回收（direct reclaim）：如果后台异步回收跟不上进程内存申请的速度，就会开始直接回收，这个回收内存的过程是同步的，会阻塞进程。

有点像jvm的minor gc和major gc

如果直接内存回收后，空闲的物理内存仍然无法满足此次物理内存的申请（申请了很大的内存），那么内核就会放最后的大招了 ——触发 OOM （Out of Memory）机制。

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

内存回收是回收什么？哪些内存可以被回收？

Linux 系统上供用户可访问的内存分为两个类型，内存回收主要针对这两种内存，它们的回收方式不同：

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

Linux Kill进程后内存会不会回收？谁来回收？怎么回收？

不会立即回收内存，有专门的内存回收机制。

Linux采用了一种称为“按需分页”的内存管理机制，即只有在需要时才会将内存分配给进程，并在不再需要时将其回收。当进程被杀死后，其所占用的内存会被标记为可回收。Linux内核会定期扫描，将可回收的内存页添加到可用内存池中。这个过程由操作系统的内存管理模块执行。
Linux内核还实现了一种称为“内存压缩”的机制，用于尽可能地延迟对内存的真正回收。内存压缩可以将不常用的内存页压缩成更少的页，从而释放出更多的可用内存。

回收内存带来的性能影响

文件备份页的脏页回收和匿名页的回收都会发生磁盘I/O，影响性能。优化性能的方法有：

可以调整文件备份页和匿名页的回收倾向swapness，使匿名页的回收少一些。
尽早触发后台内存回收 kswapd，尽量减少直接内存回收（direct reclaim）。

kswapd和direct reclaim的触发条件是什么？

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

页高水位（pages_high）
页低水位（pages_low）
页最小水位（pages_min）

当剩余内存小于页低水位，就会触发 kswapd ，一直回收到剩余内存页大于页高水位。
当剩余内存小于页最小水位，就会触发direct reclaim ** ，一直回收到剩余内存页大于页高水位**。

Page Cache

Page Cache 是由 Linux 内核管理的内存区域，受文件系统管理，是硬盘的缓存，常说的内核缓冲区就包含page cache区域。我们通过 mmap 以及 buffered I/O 将文件从硬盘读取到内存就是读取到 Page Cache 中。

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

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

下图代表了操作系统的预读机制，应用程序利用 read 系统调用读取 4KB 数据，实际上内核使用 readahead 机制完成了 16KB 数据的读取。

Page Cache 与 buffer cache

**Page Cache 用于缓存文件的页数据，buffer cache 用于缓存块设备（如磁盘）的块数据。**页是逻辑上的概念，因此 Page Cache 是与文件系统同级的；块是物理上的概念，因此 buffer cache 是与块设备驱动程序同级的。
buffer cache与page cache两块缓存如今已近似融合在一起：如果一个文件的页加载到了 Page Cache，那么同时 buffer cache 只需要维护块指向页的指针就可以了，只有那些没有文件表示的块，或者绕过了文件系统直接操作（如dd命令）的块，才会真正放到 buffer cache 里。所以可以将两者统称为Page Cache。

预读机制

Linux操作系统（文件系统）层面的基于page cache的PAGE_READAHEAD。
MySQL数据库有buffer pool。
。。。。

如何解决预读失效？

预读失效：预读进来的数据后续不被访问，同时还把热点数据给挤出缓存区了，降低了命中率。是传统lru算法的弊端。

Linux 和 MySQL 对传统的 LRU 链表做了改进：

Linux 操作系统实现两个了 LRU 链表：活跃 LRU 链表（active list）和非活跃 LRU 链表（inactive list）。
- 活跃链表放相对热点的数据。
- 预读进来的数据只会放到非活跃链表的头部，等要被访问的时候才会加入到活跃链表。

MySQL Innodb 存储引擎是在一个 LRU 链表上划分来 2 个区域：young 区域和 old 区域。
- young区相当于活跃链表
- old区相当于非活跃链表
- young : old是63:37（默认）的比例

但是如果还是使用「只要数据被访问一次，就将数据加入到活跃 LRU 链表头部（或者 young 区域）」这种方式的话，那么还存在缓存污染的问题。

如何解决缓存污染？

缓存污染：当我们批量读取数据时，由于数据被访问了一次，这些大量数据都会被加入到「活跃 LRU 链表」（或young区）里，把之前的热点数据全部都给淘汰了，如果这些大量的数据在很长一段时间都不会被访问的话，那么整个活跃 LRU 链表（或者 young 区）就被污染了。

Linux 操作系统和 MySQL Innodb 存储引擎都提高升级为热点数据的门槛：

Linux 操作系统：在内存页被访问第二次的时候，才将页从 inactive list 升级到 active list 里。
MySQL Innodb：在内存页被访问第二次的时候，并不会马上将该页从 old 区升级到 young 区，因为还要进行停留在 old 区的时间判断：
- 如果第二次被访问且在 old 区域停留时间在 1 秒内（默认值），那么该页就不会被从 old 区升级到 young 区；
- 如果第二次被访问且在 old 区域停留时间超过 1 秒，那么该页就会从 old 区升级到 young 区；

通过提高了进入 active list （或者 young 区）的门槛后，就很好了避免缓存污染带来的影响。

存储器的层次结构

每一种存储器设备只与它相邻的存储器设备打交道。比如，CPU Cache 的数据是从内存加载过来的，写回数据的时候也只写回到内存，CPU Cache 不会直接把数据写到硬盘，也不会直接从硬盘加载数据，而是先加载到内存，再从内存加载到 CPU Cache 中。
当 CPU 需要访问内存中某个数据的时候，如果寄存器有这个数据，CPU 就直接从寄存器取数据即可，如果寄存器没有这个数据，CPU 就会查询 L1 高速缓存，如果 L1 没有，则查询 L2 高速缓存，L2 还是没有的话就查询 L3 高速缓存，L3 依然没有的话，才去内存中取数据。所以，存储层次结构也形成了缓存的体系。

寄存器（Register）

速度最快，价格最贵，数量最少，数量通常在几十到几百之间，每个寄存器可以用来存储一定的字节（byte）的数据。比如：

32 位 CPU 中大多数寄存器可以存储 4 个字节；
64 位 CPU 中大多数寄存器可以存储 8 个字节。

CPU Cache

CPU Cache 用的是一种叫 SRAM（Static Random-Access Memory，静态随机存储器） 的芯片。
SRAM 之所以叫「静态」存储器，是因为只要有电，数据就可以保持存在，而一旦断电，数据就会丢失了。在 SRAM 里面，一个 bit 的数据，通常需要 6 个mos管，所以 SRAM 的存储密度不高，不过也因为 SRAM 的电路简单，所以访问速度非常快。
通常可以分为 L1、L2、L3 三层高速缓存，也称为一级缓存、二级缓存、三级缓存。

L1

每个 CPU 核处理器都有一块属于自己的 L1 高速缓存，指令和数据在 L1 是分开存放的，所以 L1 高速缓存通常分成指令缓存和数据缓存。

比如 1+1=2 这个运算，+ 就是指令，会被放在「指令缓存」中，而输入数字 1 则会被放在「数据缓存」里。

L2

每个core都有一块独有的L2高速缓存，但速度比L1要慢。

L3

所有core共有一块L3高速缓存。

Cache Line

Cache Line 是 CPU 从主存读取数据到cache的最小单位，由有效位（valid bit）+ 组标记（Set Tag）+ 数据块（Data Block）组成。
如果valid bit表示无效，则整个line上的数据都无效，需要到主存中重新读取整个line。
Data Block里面又分了多个字（word），字是cpu从cache读取、加工数据的最小单位（这个最小单位别跟上面的搞混了），多少位的系统，一个字就是多少位，如果要读取某个数据，需要偏移量block offset来定位。
一个Cache Line目前多为64字节。

如何在cache中找到想要的数据？

有三种策略：

直接映射（Direct-Mapped）：每个组只有一个line，选中组之后不需要和组中的每个line比对，因为只有一个line。
组相连（Set Associative）：多个组，每个组多个line，需要在组中对比才能找到想要的line。
全相连（Fully Associative）：不分组，挨个对比，耗时比较久。

内存地址的结构组成跟cache line的结构对应才能找到数据：

具体的寻找过程如下：

通过内存地址的set index找到cache中对应的组
一个个对比内存地址的tag和cache中组的tag，一样的话就证明找到了那一line
再检验有效位是否有效，如果失效就到主存中重新加载数据
如果有效，就根据偏移量读取对应的字

内存（memory）

内存使用的是一种叫作 DRAM （Dynamic Random Access Memory，动态随机存取存储器） 的芯片。
相比于SRAM，DRAM 的结构更简单，密度更高，功耗更低，有更大的容量，而且造价比 SRAM 芯片便宜很多。DRAM 存储一个 bit 数据，只需要一个mos管和一个电容，但是因为数据会被存储在电容里，电容会不断漏电，所以需要**「定时刷新」电容**，才能保证数据不会被丢失，这就是 DRAM 之所以被称为「动态」存储器的原因，只有不断刷新，数据才能被存储起来。
DRAM的速度慢于SRAM

SSD/HDD 硬盘（Disk）

SSD（Solid-state disk）也就是固态硬盘，使用浮栅晶体管，但是它相比内存的优点是断电后数据还是存在的，而内存、寄存器、高速缓存断电后数据都会丢失。内存的读写速度比 SSD 大概快 10~1000 倍。
HDD（Hard Disk Drive）就是机械硬盘，它是通过物理读写的方式来访问数据的，因此它访问速度是非常慢的，它的速度比内存慢 10W 倍左右。
- 磁盘一般会有多个盘片，每个盘面都有自己的磁头。盘片中的每一层分为多个磁道，每个磁道分多个扇区，每个扇区是 512B。多个具有相同编号的磁道形成一个圆柱，称之为磁盘的柱面。
- 文件系统把多个扇区组成了一个数据块，每次读写的最小单位就是数据块，Linux 中的数据块大小为 4KB，也就是一次性读写 8 个扇区，这将大大提高了磁盘的读写的效率。
- 磁头移动到相应磁道称为寻道，寻道完后盘片旋转称为寻址。寻道是最耗时的操作，所以磁盘调度算法就是寻道的调度策略

磁盘调度算法

先来先服务：简单粗暴，寻道时间最长。
最短寻道优先：优先选择从当前磁头所在位置到下一个位置所需寻道时间最短的请求。但会存在饥饿问题，假设是一个动态的请求，一直是小范围内的数据，那么比较远的请求就很久不被访问。
扫描算法（scan）：磁头在一个方向上移动，访问所有未完成的请求，直到磁头到达该方向上的最后的磁道，才调换方向。不会产生饥饿现象，但是中间部分的磁道会比较占便宜，即每个磁道的响应频率存在差异。
循环扫描算法（c-scan）：只有磁头朝某个特定方向移动时，才处理磁道访问请求，而返回时直接快速移动至最靠边缘的磁道，也就是复位磁头，这个过程是很快的，并且返回中途不处理任何请求，磁道只响应一个方向上的请求。各个位置磁道响应频率相对比较平均。
LOOK 与 C-LOOK算法：是对scan和c-sacn算法的优化，**磁头在移动到「最远的请求」位置，然后立即反向移动。**对 SCAN 的优化叫 LOOK 算法，对 C-SCAN 的优化叫 C-LOOK算法。

cpu 缓存一致性

需要一种机制，来同步两个不同core的cache数据，要保证做到下面这 2 点：

某个 CPU 核心里的 Cache 数据更新时，必须要传播到其他核心的 Cache，称为写传播（Write Propagation）；
某个 CPU 核心里对数据的操作顺序，必须在其他核心看起来执行顺序是一样的，这个称为事务的串行化（Transaction Serialization）。

总线嗅探

总线嗅探（Bus Snooping）机制来实现写传播。
当 A core修改了 L1 Cache 中变量 x 的值，通过总线把这个事件广播通知给其他所有的core，然后每个 core都会监听总线上的广播事件，并检查是否有相同的数据在自己的 L1 Cache 中，如果有该数据，就更新自己的L1 cache的这一缓存行。
可以发现，总线嗅探方法很简单，每个core都需要每时每刻监听总线上的一切活动，不管别的core的 Cache 是否缓存相同的数据，都需要发出一个广播事件，这无疑会加重总线的负载。因为缓存一致性需要不断地总线嗅探和CAS循环，当某个数据被多个CPU共享时，会造成大量的缓存一致性流量，占用有限的总线带宽，导致CPU处理能力下降，系统卡顿，也就是总线风暴问题。
另外，总线嗅探只是保证了某个core的 Cache 更新数据这个事件能被其他 core知道，但是并不能保证事务串行化。

MESI 协议

MESI协议基于总线嗅探机制实现了事务串行化，也用有限状态机降低了总线带宽压力，实现了 CPU 缓存一致性。

MESI 协议其实是 4 个状态单词的开头字母缩写，来标记缓存行的4种状态，分别是：

Modified，已修改。该 Cache line上的数据已被更新过，但是未写到主存中。
Exclusive，独占。代表数据是一致的，可以读。数据只存在于这一个core的cache里，不存在一致性问题，不需要广播事件。
Shared，共享。代表数据是一致的，可以读。数据在多个core的cache中都有，更新该数据时，要先向所有的其他 core广播一个请求，要求先把其他core的 Cache 中对应的 Cache Line 标记为「无效」状态，然后再更新当前 Cache 里面的数据。
Invalidated，已失效。该 Cache line上的数据已失效，不可读，只能到主存中去读取。

当 Cache Line 状态是「已修改」或者「独占」状态时，直接更新其数据，不需要发送广播给其他core，这在一定程度上减少了总线带宽压力。如果Cache Line 要被「替换」，发现 Cache Line 状态是「已修改」状态，就会在替换前先把数据同步到主存。

整个 MESI 的状态可以用一个有限状态机来表示它的状态流转，状态转换图如下：

缓存行伪共享与缓存行填充

缓存行（cache line）：CPU Cache中可分配、操作（如从主存中读取数据）的最小存储单元。操作系统多少位，就有多少字节，64位系统就是64字节。
伪共享问题（false sharing）：多核多线程并发场景下，多核处理器要操作的不同变量（data block）处于同一缓存行，某处理器更新缓存行中的某个数据，并将其写回主存，同时其他处理器会使该缓存行失效，如需使用，还需从主存中重新加载，使得互相独立的两个线程的性能受对方影响，性能差。
缓存行填充（cache line padding）：空间换时间，某缓存行中仅存储一个目标变量，其余空间用“无意义”的数据把该缓存行的data block填满，把该缓存行填充补齐至64字节，解决伪共享问题。

因为类中的变量都是连续分配的，就会出现伪共享问题。下面的代码就能确保a，b，c变量所在的缓存行中只有它自己一个有用的变量。或者使用jdk1.8中的@sun.misc.Contended注解，就不需要手动写padding。

public static class MyClassPadding {
    public static long p1, p2, p3, p4, p5, p6, p7; // cache line padding
    // @sun.misc.Contended
    public static long a;
    public static long p8, p9, p10, p11, p12, p13, p14; //cache line padding
    // @sun.misc.Contended
    public static long b;
    public static long p15, p16, p17, p18, p19, p20, p21; // cache line padding
    // @sun.misc.Contended
    public static long c;
    public static long p22, p23, p24, p25, p26, p27, p28; // cache line padding
}

/**
 * 三个线程分别自增a、b、c
 * 会产生缓存行伪共享问题，需要cache line padding
 */
public class ThreadTest4 {
    public static void main(String[] args) throws InterruptedException {
        MyClass test = new MyClass();

        Thread thread1 = new Thread(()->{
            for (int i = 0; i < 1000000000; i++) {
                test.a++;
            }
        });

        Thread thread2 = new Thread(()->{
            for (int i = 0; i < 1000000000; i++) {
                test.b++;
            }
        });

        Thread thread3 = new Thread(()->{
            for (int i = 0; i < 1000000000; i++) {
                test.c++;
            }
        });

        long begin = System.currentTimeMillis();

        thread1.start();
        thread2.start();
        thread3.start();

        // 这三行代码表示的是主线程等待这3个线程都执行完之后再往下执行，
        // 但这三个线程之间不会互相阻塞，join是调用方和被调用方之间的关系，与其他线程无关
        thread1.join();
        thread2.join();
        thread3.join();

        long end = System.currentTimeMillis();

        System.out.println(test.a);
        System.out.println(test.b);
        System.out.println(test.c);
        System.out.println(end - begin);

    }
}

class MyClass {
    @sun.misc.Contended
    public int a = 0;

    @sun.misc.Contended
    public int b = 0;

    @sun.misc.Contended
    public int c = 0;
}

文章作者: XiaooooooBawang

文章连结: xiaoooooobawang.xyz/archives/cao-zuo-xi-tong-yu-ji-suan-ji-zu-cheng-yuan-li

微信扫一扫