操作系统总结

总结自小林coding 及《现代操作系统》

硬件结构

存储器结构

• 寄存器；
• CPU Cache；
  1. L1-Cache；
  2. L2-Cache；
  3. L3-Cahce；
• 内存；
• SSD/HDD 硬盘

寄存器

最靠近CPU控制单元和逻辑计算单元.最快。

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

CPU Cache

CPU Cache 用的是一种叫 SRAM（*Static Random-Access* Memory，静态随机存储器） 的芯片。

分级

CPU 的高速缓存，通常可以分为 L1、L2、L3 这样的三层高速缓存，也称为一级缓存、二级缓存、三级缓存。

1. L1 高速缓存

   L1 高速缓存访问速度2~4时钟周期，大小几十到几百KB

   每个CPU有自己的L1,指令和数据分开存放，所以 L1 高速缓存通常分成指令缓存和数据缓存。

   查看大小：

   1. 数据：cat /sys/devices/system/cpu/cpu0/cache/index0/size
   2. 指令：cat /sys/devices/system/cpu/cpu0/cache/index1/size

2. L2 高速缓存

   L2 高速缓存同样每个 CPU 核心都有，离CPU更远，访问也更慢

   查看大小：cat /sys/devices/system/cpu/cpu0/cache/index2/size

3. L3高速缓存

   L3 高速缓存通常是多个 CPU 核心共用的，位置比 L2 高速缓存距离 CPU 核心 更远，大小也会更大些

   查看大小：cat /sys/devices/system/cpu/cpu0/cache/index3/size

结构和读取过程

CPU Cache由很多Cache Line（缓存块）组成，Cache Line 是 CPU 从内存读取数据的基本单位，而 Cache Line 是由各种标志（Tag）+ 数据块（Data Block）组成：

CPU每次优先从Cache读，没有就从内存读一个缓存块到Cache，然后再从Cache读。

提升缓存命中率

1. 数据缓存命中率

   按照内存布局来遍历元素。

2. 指令缓存的命中率

   CPU可以根据历史记录预测分支语句的结果，可以提前读取相应分支的指令。

   有规律的条件分支语句能够让 CPU 的分支预测器发挥作用，进一步提高执行的效率

3. 多核CPU缓存命中率

   当有多个同时执行「计算密集型」的线程，为了防止因为切换到不同的核心，而导致缓存命中率下降的问题，我们可以把线程绑定在某一个 CPU 核心上

缓存写入内存

写直达

保持内存与 Cache 一致性最简单的方式是，把数据同时写入内存和 Cache 中，这种方法称为写直达（*Write Through*）。问题就是每次都会写入内存，性能会有影响。

写回

在写回机制中，当发生写操作时，新的数据仅仅被写入 Cache Block 里，只有当修改过的 Cache Block「被替换」时才需要写到内存中，减少了数据写回内存的频率，这样便可以提高系统的性能。

1. 写时，如果数据在cache中就更新cache，标记block为dirty（数据不一致）
2. 如果cache没有去找block，查看是不是dirty
   1. 如果是dirty则需要先把当前存的数据写入内存，再从内存读然后再写入block，最后标记为dirty,(为了数据一致性)
   2. 如果不是dirty就直接写入block，然后标记为dirty

缓存一致性问题

由于 L1/L2 Cache 是多个核心各自独有的，那么会带来多核心的缓存一致性（*Cache Coherence*） 的问题，如果不能保证缓存一致性的问题，就可能造成结果错误。

为了同步不同核心的缓存数据，需要保证：

1. 写传播：某CPU核心内Cache更新数据时必须传播到其他核心的Cache

2. 事务穿行化：某个核心内对数据的操作顺序对其他核心而言也是一样的。

   引入锁。

基于总线嗅探机制的 MESI 协议，就满足上面了这两点，因此它是保障缓存一致性的协议。

MESI 协议，是已修改、独占、共享、已失效这四个状态的英文缩写的组合。整个 MSI 状态的变更，则是根据来自本地 CPU 核心的请求，或者来自其他 CPU 核心通过总线传输过来的请求，从而构成一个流动的状态机。另外，对于在「已修改」或者「独占」状态的 Cache Line，修改更新其数据不需要发送广播给其他 CPU 核心。

伪共享问题

两个核心的线程读取的Cache line有重叠区域，当一个线程写数据时就会把其他核心的Cache标记为失效，其他线程修改时需要先把之前修改的数据写入内存，然后再读取数据到Cache然后标记失效，一直循环下去。

解决方法：使变量按照Cache line对齐（内存换时间）

内存

内存使用的是一种叫作 DRAM （*Dynamic Random Access Memory*，动态随机存取存储器） 的芯片。

每个存储器只和相邻的一层存储器设备打交道，并且存储设备为了追求更快的速度，所需的材料成本必然也是更高，也正因为成本太高，所以 CPU 内部的寄存器、L1\L2\L3 Cache 只好用较小的容量，相反内存、硬盘则可用更大的容量，这就我们今天所说的存储器层次结构

当 CPU 需要访问内存中某个数据的时候，如果寄存器有这个数据，CPU 就直接从寄存器取数据即可，如果寄存器没有这个数据，CPU 就会查询 L1 高速缓存，如果 L1 没有，则查询 L2 高速缓存，L2 还是没有的话就查询 L3 高速缓存，L3 依然没有的话，才去内存中取数据

0.1+0.2！=0.3

负数为什么要用补码方式来表示

如果负数不是使用补码的方式表示，则在做基本对加减法运算的时候，还需要多一步操作来判断是否为负数，如果为负数，还得把加法反转成减法，或者把减法反转成加法。

十进制小数与二进制的转换

十进制转二进制采用除 2 取余法

小数转二进制采用乘2取整

由于计算机的资源是有限的，所以是没办法用二进制精确的表示 0.1，只能用「近似值」来表示，就是在有限的精度情况下，最大化接近 0.1 的二进制数，于是就会造成精度缺失的情况。

存储小数

• 符号位：表示数字是正数还是负数，为 0 表示正数，为 1 表示负数；
• 指数位：指定了小数点在数据中的位置，指数可以是负数，也可以是正数，指数位的长度越长则数值的表达范围就越大；
• 尾数位：小数点右侧的数字，也就是小数部分，比如二进制 1.0011 x 2^(-2)，尾数部分就是 0011，而且尾数的长度决定了这个数的精度，因此如果要表示精度更高的小数，则就要提高尾数位的长度；

所以，你会看到在计算机中 0.1 + 0.2 并不等于完整的 0.3。

这主要是因为有的小数无法可以用「完整」的二进制来表示，所以计算机里只能采用近似数的方式来保存，那两个近似数相加，得到的必然也是一个近似数。

CPU指令集

指令集是 C P U 实现软件指挥硬件执行的媒介，具体来说每一条汇编语句都对应了一条 C P U 指令，而非常非常多的 C P U 指令 在一起，可以组成一个、甚至多个集合，指令的集合叫 C P U 指令集。

同时CPU指令集也有权限分级，因为CPU指令集是直接操作硬件的，如果操作不当会影响这个计算机运行。

中断

包含一段int 0x80指令的代码，int 0x80去访问IDT表跳到对应中断（故意将那个中断的DPL设置为3），然后将CPL设为0，再去跳转到指定系统调用函数去执行。

分类：

1. 外部中断（硬中断）：由硬件产生的，比如，像磁盘，网卡，键盘，时钟等。每个设备或设备集都有它自己的 IRQ（中断请求）
   1. 非屏蔽中断：就像这种中断类型的字面意思一样，这种中断是不可能被 CPU 忽略或取消的。NMI 是在单独的中断线路上进行发送的，它通常被用于关键性硬件发生的错误，如内存错误，风扇故障，温度传感器故障等。
   2. 可屏蔽中断：这些中断是可以被 CPU 忽略或延迟处理的。当缓存控制器的外部针脚被触发的时候就会产生这种类型的中断，而中断屏蔽寄存器就会将这样的中断屏蔽掉。我们可以将一个比特位设置为 0，来禁用在此针脚触发的中断。
2. 内部中断
   1. 软中断：软件主动发起的中断。主要是系统调用，调试，越界等。
   2. 异常：CPU内部的错误产生。
      1. Fault，也称故障。属于可被修复的一种类型，当发生此类异常时，CPU 将机器状态恢复到异常之前的状态，之后调用中断处理程序，通常都能够被解决。缺页异常就属于此种异常
      2. Trap，也称陷阱。此异常通常在调试中。
      3. Abort，也称终止。程序发生了此类异常通常就无法继续执行下去，操作系统会将此程序从进程表中去除。

内存管理

虚拟内存

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

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

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

虚拟内存的作用

• 第一，虚拟内存可以使得进程对运行内存超过物理内存大小，因为程序运行符合局部性原理，CPU 访问内存会有很明显的重复访问的倾向性，对于那些没有被经常使用到的内存，我们可以把它换出到物理内存之外，比如硬盘上的 swap 区域。
• 第二，由于每个进程都有自己的页表，所以每个进程的虚拟内存空间就是相互独立的。进程也没有办法访问其他进程的页表，所以这些页表是私有的，这就解决了多进程之间地址冲突的问题。
• 第三，页表里的页表项中除了物理地址之外，还有一些标记属性的比特，比如控制一个页的读写权限，标记该页是否存在等。在内存访问方面，操作系统提供了更好的安全性。

内存分段

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

分段机制下，虚拟地址和物理地址如何映射？

虚拟地址：段选择因子+段内偏移量

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

缺点：

1. 内存碎片

   但是由于每个段的长度不固定，所以多个段未必能恰好使用所有的内存空间，会产生了多个不连续的小物理内存，导致新的程序无法被装载，所以会出现外部内存碎片的问题。

2. 频繁的内存交换

   为了解决内存碎片问题，需要将之前的内存写入磁盘，然后再充分在内存上分配空间写入（Swap）。但是每次写入都需要把整个程序都写入磁盘，所以效率很低。

内存分页

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

虚拟地址与物理地址之间通过页表来映射

记录一条关联信息的就是页表项

• 状态位：用于表示该页是否有效，也就是说是否在物理内存中，供程序访问时参考。
• 访问字段：用于记录该页在一段时间被访问的次数，供页面置换算法选择出页面时参考。
• 修改位：表示该页在调入内存后是否有被修改过，由于内存中的每一页都在磁盘上保留一份副本，因此，如果没有修改，在置换该页时就不需要将该页写回到磁盘上，以减少系统的开销；如果已经被修改，则将该页重写到磁盘上，以保证磁盘中所保留的始终是最新的副本。
• 硬盘地址：用于指出该页在硬盘上的地址，通常是物理块号，供调入该页时使用。

页表是存储在内存里的，内存管理单元 （MMU）就做将虚拟内存地址转换成物理地址的工作。

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

分页机制下，虚拟地址和物理地址是如何映射的？

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

优点：

1. 解决了外部内存碎片和内存交换效率低

   内存分页将内存空间预先分配好，所以不会出现间隙非常小的碎片。

   如果内存不够，有些进程会被挂起，占用的内存会被换出，需要时换入。所以一次写入和读取磁盘的只有部分页，所以效率高。

2. 程序运行时不需要加载全部内存，需要使用的再进行加载。

缺点：

1. 给进程分配的内存可能比实际需要的大

2. 简单的分页会导致页表占用空间大

   页表一定要覆盖全部虚拟地址空间，不分级的页表就需要有 100 多万个页表项来映射，而二级分页则只需要 1024 个页表项

   32位：虚拟空间：4G，一页：4KB，需要2^20个页，每个页表项4Byte，页表占用：4MB

   因为每个页都需要使用页表项进行绑定。

多级页表

我们把这个 100 多万个「页表项」的单级页表再分页，将页表（一级页表）分为 1024 个页表（二级页表），每个表（二级页表）中包含 1024 个「页表项」，形成二级分页。如下图所示：

如果使用了二级分页，一级页表就可以覆盖整个 4GB 虚拟地址空间，但如果某个一级页表的页表项没有被用到，也就不需要创建这个页表项对应的二级页表了，即可以在需要时才创建二级页表。

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

• 全局页目录项 PGD（Page Global Directory）；
• 上层页目录项 PUD（Page Upper Directory）；
• 中间页目录项 PMD（Page Middle Directory）；
• 页表项 PTE（Page Table Entry）；

TLB

虚拟地址到物理地址的转换就需要很多道工序

我们就可以利用这一特性，把最常访问的几个页表项存储到访问速度更快的硬件，于是计算机科学家们，就在 CPU 芯片中，加入了一个专门存放程序最常访问的页表项的 Cache，这个 Cache 就是 TLB（Translation Lookaside Buffer） ，通常称为页表缓存、转址旁路缓存、快表等。

有了 TLB 后，那么 CPU 在寻址时，会先查 TLB，如果没找到，才会继续查常规的页表。

段栈式内存管理

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

• 先将程序划分为多个有逻辑意义的段，也就是前面提到的分段机制；
• 接着再把每个段划分为多个页，也就是对分段划分出来的连续空间，再划分固定大小的页；

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

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

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

linux下地址空间

在 Linux 操作系统中，虚拟地址空间的内部又被分为内核空间和用户空间两部分，不同位数的系统，地址空间的范围也不同。比如最常见的 32 位和 64 位系统，如下所示：

通过这里可以看出：

• 32 位系统的内核空间占用 1G，位于最高处，剩下的 3G 是用户空间；
• 64 位系统的内核空间和用户空间都是 128T，分别占据整个内存空间的最高和最低处，剩下的中间部分是未定义的。

通过这张图你可以看到，用户空间内存，从低到高分别是 6 种不同的内存段：

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

在这 7 个内存段中，堆和文件映射段的内存是动态分配的。比如说，使用 C 标准库的 malloc() 或者 mmap() ，就可以分别在堆和文件映射段动态分配内存。

用户态和内核态

操作系统将虚拟内存分割为用户态和内核态，内核指令运行在内核态，用户指令运行在用户态，主要通过CPL和RPL存储当前指令所在权限，每次执行指令时硬件会检查这两个寄存器来确定权限。

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

malloc如何分配内存

malloc 是如何分配内存的？

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

• 方式一：通过 brk () 系统调用从堆分配内存

  将brk堆顶指针向上移动即可。

  

• 方式二：通过 mmap () 系统调用在文件映射区域分配内存

  通过 mmap () 系统调用中「私有匿名映射」的方式，在文件映射区分配一块内存，也就是从文件映射区 “偷” 了一块内存。

  

malloc () 源码里默认定义了一个阈值：

• 如果用户分配的内存小于 128 KB，则通过 brk () 申请内存；
• 如果用户分配的内存大于 128 KB，则通过 mmap () 申请内存；

malloc () 分配的是物理内存吗？

malloc分配的是虚拟内存，如果没有被访问则不会映射到物理内存。只有在访问时通过查找页表触发缺页中断然后再建立与物理内存的关系。

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

1. brk () 方式会把空间还给程序（缓存）
2. mmap 方式申请的内存，free 释放内存后就会归归还给操作系统

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

1. 向操作系统申请内存需要通过系统调用引起状态切换
2. mmap申请的内存在访问时会引起缺页异常

brk()内部进行缓存，减少了系统调用的次数。

缺点：每次都申请大内存会导致free了的内存无法重复使用，必须向操作系统申请，慢慢就会"内存泄露"

内存不足会怎么样

malloc时申请虚拟内存，当读写时触发缺页中断，如果没有就给分配物理内存，建立连接。

没有则开始进行内存回收。

• 后台内存回收（kswapd）：在物理内存紧张的时候，会唤醒 kswapd 内核线程来回收内存，这个回收内存的过程异步的，不会阻塞进程的执行。
• 直接内存回收（direct reclaim）：如果后台异步回收跟不上进程内存申请的速度，就会开始直接回收，这个回收内存的过程是同步的，会阻塞进程的执行。（会引起CPU利用升高，系统负载增加）

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

OOM会选择一个占用物理内存较高的进程然后杀死。

哪些内存可以回收

• 文件页：干净页直接释放，脏页就先写入再释放
• 匿名页：比如堆栈等没有实际物理映射，则通过swap将其写入磁盘。

采用LRU算法，就是优先回收不常访问的内存。LRU 回收算法，实际上维护着 active 和 inactive 两个双向链表，其中：

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

越接近链表尾部，就表示内存页越不常访问。这样，在回收内存时，系统就可以根据活跃程度，优先回收不活跃的内存。

分配超过物理内存的内存

• 在 32 位操作系统，因为进程最大只能申请 3 GB 大小的虚拟内存，所以直接申请 8G 内存，会申请失败。
• 在 64 位 位操作系统，因为进程最大只能申请 128 TB 大小的虚拟内存，即使物理内存只有 4GB，申请 8G 内存也是没问题，因为申请的内存是虚拟内存。如果这块虚拟内存被访问了，要看系统有没有 Swap 分区：
  • 如果没有 Swap 分区，因为物理空间不够，进程会被操作系统杀掉，原因是 OOM（内存溢出）；
  • 如果有 Swap 分区，即使物理内存只有 4GB，程序也能正常使用 8GB 的内存，进程可以正常运行；

避免预读失效和缓存污染

如何改进LRU算法

LRU 算法一般是用「链表」作为数据结构来实现的，链表头部的数据是最近使用的，而链表末尾的数据是最久没被使用的。那么，当空间不够了，就淘汰最久没被使用的节点，也就是链表末尾的数据，从而腾出内存空间。

LRU存在下面的问题：

「预读失效」导致缓存命中率下降

CPU Cache在从内存读取数据时会读取整个cache line单位的数据。减少IO次数，提高吞吐量。

但是如果这些被提前加载进来的页，并没有被访问，相当于这个预读工作是白做了，这个就是预读失效。

如果使用传统的 LRU 算法，就会把预读页放在LRU最前端，而末尾则可能时热点数据。

预读失败改善方法：

改进：活跃LRU链表和非活跃LRU链表

都是将数据分为了冷数据和热数据，然后分别进行 LRU 算法

预读页只需要添加到非活跃链表，当其真正被访问时再插入到活跃链表

「缓存污染」导致缓存命中率下降（对应第二个题目）

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

改进：提高进入活跃链表的门槛

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

进程管理

基本概念

https://cloud.tencent.com/developer/article/1339562

https://www.icourse163.org/learn/XIYOU-1461809182?tid=1468347451#/learn/content?type=detail&id=1250283325&cid=1278373872&replay=true

这个也讲的挺好

进程

操作系统资源分配和调度的单位。linux下只有一种类型的进程task_struct

状态

创建态：初始化进程资源

就绪态：可运行，等待CPU

运行态：正在被CPU执行。

阻塞态：等待某一事件执行完（IO，时间片，错误）

结束态：退出状态释放该线程所分配的资源。

挂起态：描述进程没有占用实际的物理内存空间的情况

进程控制块（PCB）内核中就是task_struct

进程描述信息：

• 进程标识符：标识各个进程，每个进程都有一个并且唯一的标识符；
• 用户标识符：进程归属的用户，用户标识符主要为共享和保护服务；

进程控制和管理信息：

• 进程当前状态，如 new、ready、running、waiting 或 blocked 等；
• 进程优先级：进程抢占 CPU 时的优先级；

资源分配清单：

• 有关内存地址空间或虚拟地址空间的信息，所打开文件的列表和所使用的 I/O 设备信息。

CPU 相关信息：

• CPU 中各个寄存器的值，当进程被切换时，CPU 的状态信息都会被保存在相应的 PCB 中，以便进程重新执行时，能从断点处继续执行。

进程上下文切换

进程的上下文切换不仅包含了虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈、寄存器等内核空间的资源。，这些信息通常会保存在PCB中，也就是PCB的切换。

线程

单进程无法充分利用CPU资源，多进程创建，切换和终止时开销太大。所以引入线程

信息共享

1. 共享

   1. 代码区（也就是进程中的任何函数都可以被某一个线程执行）
   2. 堆区（malloc或new出的变量，只要有它的地址，就可以被任何线程访问）
   3. 程序运行过程中打开的文件也可以被共享

2. 非共享

   1. 线程的栈区、
   2. 程序计数器、
   3. 栈指针以及函数运行使用的寄存器，
   4. 线程局部存储（可以让你使用一个独属于线程的全局变量）

TCB

线程状态、调度算法、CPU 寄存器、PC 计数器，两个栈

多处理器：每个CPU上独立的映射表，

多核：多个CPU共用一个映射表

线程本地存储（TLS）：为每个线程提供独立的同名全局变量

这些变量相对于TLS起始地址不同，但是偏移量相同。切换线程时也需要切换对应TLS起始地址。

用户级线程

完全建立在用户空间，创建，调度，同步，销毁都由用户空间的线程库控制。

• 处理器竞争：单纯的用户线程是建立在用户空间，其对内核是透明的，因此其所属进程单独参与处理器的竞争，而进程的所有线程参与竞争该进程的资源。
• 使用资源：与所属进程共享进程地址空间和系统资源。
• 调度：由在用户空间实现的线程库，在所属进程内进行调度

优点：

1. 调度不需要内核参与，消耗小,接近 1K
2. 无需考虑操作系统是否支持多线程

缺点：

1. 同一进程中只能有一个线程运行，如果一个线程阻塞，整个进程都会被阻塞。
2. 无法利用多核CPU并行处理的能力。

调度：

只需要在TCB中保存每个线程的栈信息，通过切换TCB来切换栈即可。实现简单。

内核级线程

因为用户级线程无法发挥多核的能力，所以引入内核级线程。

内核线程就是内核的分身，一个分身可以处理一件特定事情。这在处理异步事件如异步 IO 时特别有用。内核线程的使用是廉价的，唯一使用的资源就是内核栈和上下文切换时保存寄存器的空间。

内核线程只运行在内核态，不受用户态上下文的拖累。

• 处理器竞争：可以在全系统范围内竞争处理器资源；
• 使用资源：唯一使用的资源是内核栈和上下文切换时保持寄存器的空间，共享内核区。
• 调度：调度的开销可能和进程自身差不多昂贵
• 同步效率：资源的同步和数据共享比整个进程的数据同步和共享要低一些。

优点：

1. 多处理器下，一个进程的多个线程可以并行
2. 内核线程堆栈小切换快。

缺点：

频繁的模式切换导致内核开支。

调度：

需要两套栈进行切换

1. 通过中断进入内核态

   通过int指令切换到内核（push SS,SP,源PC,源CS到内核栈）

2. 进行系统调用

   system_call（push用户态寄存器，调用中断处理函数）

3. 阻塞，切换内核栈

   阻塞，找到下一个线程的TCB，并切换其中的内核栈

4. 返回用户态

   然后通过ret弹出SS,SP,PC,CS，然后通过iret返回用户态运行

映射关系

1. 多对一

   1. 用户线程切换发生在用户态，切换效率高
   2. 一个用户线程阻塞，整个进程阻塞
   3. 无法充分利用多核CPU并行能力

2. 一对一

   1. 可以并行，一个用户线程阻塞，不影响其他线程。
   2. 每一个用户线程都对应一个内核线程，切换开销大。

3. 多对多

   大部分的线程上下文发生在用户空间，且多个线程又可以充分利用多核 CPU 的资源。

轻量级进程 (LWP)

轻量级进程 (LWP) 是一种由内核支持的用户线程。它是基于内核线程的高级抽象，因此只有先支持内核线程，才能有 LWP 。

每一个 LWP 可以支持一个或多个用户线程，每个 LWP 由一个内核线程支持。

内核线程与 LWP 之间的模型实际上就是一对一线程模型。在这种实现的操作系统中， LWP 相当于用户线程。 由于每个 LWP 都与一个特定的内核线程关联，因此每个 LWP 都是一个独立的线程调度单元。即使有一个 LWP 在系统调用中阻塞，也不会影响整个进程的执行。

• 处理器竞争：因与特定内核线程关联，因此可以在全系统范围内竞争处理器资源
• 使用资源：与父进程共享进程地址空间
• 调度：像普通进程一样调度

1. 大多数 LWP 的操作，如建立、析构以及同步，都需要进行系统调用。系统调用的代价相对较高：需要在用户态和内核态切换。
2. 每个 LWP 都需要有一个内核线程支持，因此 LWP 要消耗内核资源（内核线程的栈空间）。因此一个系统不能支持大量的 LWP

go中的协程（类似用户线程 + LWP）

操作系统提供了 LWP 作为用户线程和内核线程之间的桥梁。LWP 还是和前面提到的一样，具有内核线程支持，是内核的调度单元，并且用户线程的系统调用要通过 LWP，因此进程中某个用户线程的阻塞不会影响整个进程的执行。

用户线程库将建立的用户线程关联到 LWP 上，LWP 与用户线程的数量不一定一致。当内核调度到某个 LWP 上时，此时与该 LWP 关联的用户线程就被执行。

总结

其实就是共享的资源不同导致出现他们的分类。

进程调度

调度时机

以下状态的改变都会引发调度：

• 从就绪态 -> 运行态：当进程被创建时，会进入到就绪队列，操作系统会从就绪队列选择一个进程运行；
• 从运行态 -> 阻塞态：当进程发生 I/O 事件而阻塞时，操作系统必须选择另外一个进程运行；
• 从运行态 -> 结束态：当进程退出结束后，操作系统得从就绪队列选择另外一个进程运行；

操作系统需要考虑如何来进行调度

1. 非抢占式调度

   选择一个进程，让其运行直到阻塞或退出才会调用其他进程，不理会时间中断。

2. 抢占式调度

   选择一个进程，让该进程只运行一段时间，之后就切换到其他进程。（执行完一条指令后需要在最后一个时钟周期查看是否有中断）。时间片机制。

调度原则

1. IO阻塞导致切换

   CPU 利用率：调度程序应确保 CPU 是始终匆忙的状态，这可提高 CPU 的利用率；

2. 衡量长任务和短任务进程的运行数量

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

3. 进程的周转时间（等待+执行时间）

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

4. 就绪队列进程等待时间

   等待时间：这个等待时间不是阻塞状态的时间，而是进程处于就绪队列的时间，等待的时间越长，用户越不满意；

5. 交互性程序的响应时间

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

进程间通信

进程之间的物理地址是隔离的，所以通信必须通过操作系统进行操作。

管道

1. 匿名管道

   A | B 单向，用完即销毁

2. 命名管道

   先进先出（FIFO）

   通过mkfifo创建的一个位于内核的缓存空间

   

   对于匿名管道，其原理是通过创建一个新的进程来实现通信。

消息队列

消息队列通信过程中，存在用户态与内核态之间的数据拷贝开销，因为进程写入数据到内核中的消息队列时，会发生从用户态拷贝数据到内核态的过程，同理另一进程读取内核中的消息数据时，会发生从内核态拷贝数据到用户态的过程。

共享内存

共享内存的机制，就是拿出一块虚拟地址空间来，映射到相同的物理内存中。

多进城同时修改一个共享内存会导致冲突。

信号量

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

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

信号量表示资源的数量，有两种控制方式

1. P 将信号量-1,如果发现结果< 0则阻塞等待，否则继续执行
2. V 将信号量+1，如果发现结果>= 0，则唤醒一个阻塞进程。

信号

对于异常情况下的工作模式，就需要用「信号」的方式来通知进程。

只有第9种信号(SIGKILL)才可以无条件终止进程，其他信号进程都有权利忽略， 下面是常用的信号：

1
2
3
4
5
6
7

HUP     1    终端断线
INT     2    中断（同 Ctrl + C）
QUIT    3    退出（同 Ctrl + \）
TERM   15    终止
KILL    9    强制终止
CONT   18    继续（与STOP相反， fg/bg命令）
STOP   19    暂停（同 Ctrl + Z）

信号是进程间通信中唯一的异步通信机制，应用进程在接收到信号后可以如下进行处理：

1. 执行默认操作。Linux 对每种信号都规定了默认操作，例如，上面列表中的 SIGTERM 信号，就是终止进程的意思。

2. 捕捉信号。我们可以为信号定义一个信号处理函数。当信号发生时，我们就执行相应的信号处理函数。

3. 忽略信号。当我们不希望处理某些信号的时候，就可以忽略该信号，不做任何处理。有两个信号是应用进程无法捕捉和忽略的，即 SIGKILL 和 SEGSTOP，它们用于在任何时候中断或结束某一进程。

Socket

想跨网络与不同主机上的进程之间通信，就需要 Socket 通信了。

1

int socket(int domain, int type, int protocal)

三个参数分别代表：

• domain 参数用来指定协议族，比0如 AF_INET 用于 IPV4、AF_INET6 用于 IPV6、AF_LOCAL/AF_UNIX 用于本机；
• type 参数用来指定通信特性，比如 SOCK_STREAM 表示的是字节流，对应 TCP、SOCK_DGRAM 表示的是数据报，对应 UDP、SOCK_RAW 表示的是原始套接字；
• protocal 参数原本是用来指定通信协议的，但现在基本废弃。因为协议已经通过前面两个参数指定完成，protocol 目前一般写成 0 即可；

根据创建 socket 类型的不同，通信的方式也就不同：

• 实现 TCP 字节流通信： socket 类型是 AF_INET 和 SOCK_STREAM；
• 实现 UDP 数据报通信：socket 类型是 AF_INET 和 SOCK_DGRAM；
• 实现本地进程间通信： 「本地字节流 socket 」类型是 AF_LOCAL 和 SOCK_STREAM，「本地数据报 socket 」类型是 AF_LOCAL 和 SOCK_DGRAM。另外，AF_UNIX 和 AF_LOCAL 是等价的，所以 AF_UNIX 也属于本地 socket；

TCP建立流程：

服务端和客户端初始化Socket得到文件描述符

服务端bind自身IP+端口

1. 服务端Listen
2. 服务端accept等待连接
3. 客户端connect传输自身IP+端口去请求建立连接
4. 服务端accept返回用于传输的socket文件描述符
5. 客户端write写入数据，服务端read读取数据
6. 客户端断开连接后调用close，服务端read到EOF，处理完数据后服务端close

UDP 连接模型

UDP不需要建立连接，只需要端口+IP即可进行通信。

本地通信模型

本地 socket 被用于在同一台主机上进程间通信的场景：

• 本地 socket 的编程接口和 IPv4 、IPv6 套接字编程接口是一致的，可以支持「字节流」和「数据报」两种协议；
• 本地 socket 的实现效率大大高于 IPv4 和 IPv6 的字节流、数据报 socket 实现；

对于本地字节流 socket，其 socket 类型是 AF_LOCAL 和 SOCK_STREAM。

对于本地数据报 socket，其 socket 类型是 AF_LOCAL 和 SOCK_DGRAM。

本地字节流 socket 和 本地数据报 socket 在 bind 的时候，不像 TCP 和 UDP 要绑定 IP 地址和端口，而是绑定一个本地文件，这也就是它们之间的最大区别。

锁

互斥锁和自旋锁

1. 互斥锁加锁失败后会阻塞自己，释放CPU

2. 自旋锁加锁失败后会一直尝试加锁。

   通常使用硬件支持的CAS机制+while来实现，常用于代码执行时间短的情况

读写锁

写阻塞读写，读阻塞写

适用于读多写少情况

乐观锁

互斥锁、自旋锁、读写锁都是悲观锁，修改之前都会加锁

而乐观锁则是在修改后检查是否被其他线程修改过。

所以只有在冲突概率非常低，且加锁成本非常高的场景时，才考虑使用乐观锁。

go排查死锁

https://blog.csdn.net/u013536232/article/details/107868474

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

与两个东西有关

1. 进程虚拟内存空间：栈空间。

   ulimit -a

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

   -t: cpu time (seconds) unlimited -f: file size (blocks) unlimited -d: data seg size (kbytes) unlimited -s: stack size (kbytes) 8192 -c: core file size (blocks) unlimited -m: resident set size (kbytes) unlimited -u: processes 62661 -n: file descriptors 1024 -l: locked-in-memory size (kbytes) 8192 -v: address space (kbytes) unlimited -x: file locks unlimited -i: pending signals 62661 -q: bytes in POSIX msg queues 819200 -e: max nice 0 -r: max rt priority 0 -N 15: rt cpu time (microseconds) unlimited

   可以查看一个线程分配多大的栈空间

   32位系统一个进程虚拟空间给3G用户态，一个线程占8M，大概可以开380多线程

2. 系统参数限制

   但是对于64位系统，肯定不可能无限开，所以有系统限制

   • /proc/sys/kernel/threads-max，表示系统支持的最大线程数，默认值是 14553；
   • /proc/sys/kernel/pid_max，表示系统全局的 PID 号数值的限制，每一个进程或线程都有 ID，ID 的值超过这个数，进程或线程就会创建失败，默认值是 32768；
   • /proc/sys/vm/max_map_count，表示限制一个进程可以拥有的 VMA (虚拟内存区域) 的数量，具体什么意思我也没搞清楚，反正如果它的值很小，也会导致创建线程失败，默认值是 65530。

线程崩溃，进程会崩溃吗

非法访问内存

如果线程因为非法访问内存，进程肯定会崩溃，因为线程之间会共享内存，可能会导致其他线程出现问题。

1. 只读内存写入数据
2. 访问无权限访问的地址空间
3. 访问不存在的内存

进程如何崩溃

通过系统调用发送信号给相关进程

1. CPU 执行正常的进程指令
2. 调用 kill 系统调用向进程发送信号
3. 进程收到操作系统发的信号，CPU 暂停当前程序运行，并将控制权转交给操作系统
4. 调用 kill 系统调用向进程发送信号（假设为 11，即 SIGSEGV，一般非法访问内存报的都是这个错误）
5. 操作系统根据情况执行相应的信号处理程序（函数），一般执行完信号处理程序逻辑后会让进程退出

进程可以注册自己的信号处理函数，它收到 kill 信号后会执行自己的信号处理函数，可以调用 exit () 来退出，但也可以使用 sigsetjmp，siglongjmp 这两个函数来恢复进程的执行

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// 自定义信号处理函数示例

#include <stdio.h>
#include <signal.h>
#include <stdlib.h>
// 自定义信号处理函数，处理自定义逻辑后再调用 exit 退出
void sigHandler(int sig) {
  printf("Signal %d catched!\n", sig);
  exit(sig);
}
int main(void) {
  signal(SIGSEGV, sigHandler);
  int *p = (int *)0xC0000fff;
  *p = 10; // 针对不属于进程的内核空间写入数据，崩溃
}

// 以上结果输出: Signal 11 catched!

也可以忽略信号，但是无法无视kill -9

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

#include <stdio.h>
#include <signal.h>
#include <stdlib.h>

int main(void) {
  // 忽略信号
  signal(SIGSEGV, SIG_IGN);

  // 产生一个 SIGSEGV 信号
  raise(SIGSEGV);

  printf("正常结束");
}

Java进程为什么不会崩溃呢

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

调度算法

进程调度算法

先来先服务（非抢占式）

对于长计算任务有利，对于交互IO任务不利

最短作业优先（非抢占式）

不利于长作业。

高响应比优先调度算法（理论下）

根据响应比优先级进行调度

所以等的越久，服务时间越短优先级越高

时间片轮转调度算法

需要设置合理的时间片时间

最高优先级调度算法

希望调度程序能从就绪队列中选择最高优先级的进程进行运行，这称为最高优先级调度算法。

优先级分为静态优先级和动态优先级

  1. 静态优先级：创建进程的时候就确认了，之后不会改变
  2. 动态优先级： 如果运行时间增加降低优先级，等待时间增加则减少优先级。

可能会导致低优先级进程饥饿

多级反馈队列调度算法

时间片轮转+最高优先级的发展

  1. 多级：多个队列优先级由高到低，但高优先级时间片也相对短
  2. 反馈：表示如果有新的进程加入优先级高的队列时，调度执行新的队列。

新的进程会被放到一级队列等待执行，如果在一级队列没执行完时间片则转入二级队列。

当高优先级队列为空才去执行低优先级进程，运行时发现有高优先级进程出现就转去执行。

页面置换算法

缺页异常（缺页中断）：当 CPU 访问的页面不在物理内存时，便会产生一个缺页中断，请求操作系统将所缺页调入到物理内存。

缺页异常和其他中断的区别：

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

具体执行流程：

如果操作系统找不到空闲页呢？

找不到空闲页说明此时内存已经满了，这时候就需要页面置换选择一个物理页，如果该页是脏页就换出去，然后把正在访问的页面填入这个物理页。

所以页面置换算法就是在出现缺页异常时选择一个合适的页。那其算法目标则是，尽可能减少页面的换入换出的次数，常见的页面置换算法有如下几种：

最佳页面置换算法 OPT

最佳页面置换算法基本思路是，置换在「未来」最长时间不访问的页面。

最开始有3个空闲物理页：

但这只是理论中存在的算法。

先进先出置换算法 FIFO

我们可以选择在内存驻留时间很长的页面进行中置换，这个就是「先进先出置换」算法的思想。

最近最久未使用的置换算法 LRU

发生缺页时，选择最长时间没有被访问的页面进行置换，也就是说，该算法假设已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用。

LRU通过历史来推测未来。

但是需要维护所有页的链表，开销大。

时钟页面置换算法 Lock

把所有的页面都保存在一个类似钟面的「环形链表」中，一个表针指向最老的页面。

当发生缺页中断时，算法首先检查表针指向的页面：

• 如果它的访问位位是 0 就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置；
• 如果访问位是 1 就清除访问位，并把表针前移一个位置，重复这个过程直到找到了一个访问位为 0 的页面为止；

最不常用置换算法 LFU

当发生缺页中断时，选择「访问次数」最少的那个页面，并将其淘汰。

每个页都设置一个访问计数器，每次被访问就+1，遇到换页异常时就淘汰访问最少的页。

缺点：硬件成本大，耗时长，容易将现在才频繁访问的页淘汰。

磁盘调度算法

常见的机械磁盘是上图左边的样子，中间圆的部分是磁盘的盘片，一般会有多个盘片，每个盘面都有自己的磁头。右边的图就是一个盘片的结构，盘片中的每一层分为多个磁道，每个磁道分多个扇区，每个扇区是 512 字节。那么，多个具有相同编号的磁道形成一个圆柱，称之为磁盘的柱面，如上图里中间的样子。

所以磁盘调度算法就是规划遍历磁道的顺序

假设有下面一个请求序列，每个数字代表磁道的位置：

98，183，37，122，14，124，65，67

初始磁头当前的位置是在第 53 磁道。

先来先服务

先到来的请求，先被服务。

那么，磁盘的写入顺序是从左到右，如下图：

最短寻道时间优先

优先选择从当前磁头位置所需寻道时间最短的请求

请求序列是65，67，37，14，98，122，124，183

容易出现饥饿，有些距离远的请求可能不会被执行

扫描算法（走到底）

最短寻道时间优先算法会产生饥饿的原因在于：磁头有可能再一个小区域内来回得移动。

为了防止这个问题，可以规定：磁头在一个方向上移动，访问所有未完成的请求，直到磁头到达该方向上的最后的磁道，才调换方向，这就是扫描算法。

这种算法也叫做电梯算法，比如电梯保持按一个方向移动，直到在那个方向上没有请求为止，然后改变方向。

排序后：37，14，0，65，67，98，122，124，183

扫描调度算法性能较好，不会产生饥饿现象，但是中间磁道的访问频率会大于两端。

循环扫描算法（走到底转到最边缘再走）

扫描算法使得每个磁道响应的频率存在差异，那么要优化这个问题的话，可以总是按相同的方向进行扫描，使得每个磁道的响应频率基本一致。

循环扫描规定：只有磁头朝某个特定方向移动时，才处理磁道访问请求，而返回时直接快速移动至最靠边缘的磁道，也就是复位磁头，这个过程是很快的，并且返回中途不处理任何请求，该算法的特点，就是磁道只响应一个方向上的请求。

调度后：65，67，98，122，124，183，199，0，14，37

循环扫描算法相比于扫描算法，对于各个位置磁道响应频率相对比较平均。

LOOK 与 C-LOOK 算法

我们前面说到的扫描算法和循环扫描算法，都是磁头移动到磁盘「最始端或最末端」才开始调换方向。

那这其实是可以优化的，优化的思路就是磁头在移动到「最远的请求」位置，然后立即反向移动。反向移动中可以接受请求

而针 C-SCAN 算法的优化则叫 C-LOOK，它的工作方式，磁头在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的最始端或最末端，反向移动的途中不会响应请求。

磁盘管理

文件IO

文件的读写方式各有千秋，对于文件的 I/O 分类也非常多，常见的有

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

缓冲与非缓冲 I/O

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

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

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

直接与非直接 I/O

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

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

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

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

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

阻塞与非阻塞 I/O VS 同步与异步 I/O

先来看看阻塞 I/O，当用户程序执行 read ，线程会被阻塞，一直等到内核数据准备好，并把数据从内核缓冲区拷贝到应用程序的缓冲区中，当拷贝过程完成，read 才会返回。

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

非阻塞 I/O，非阻塞的 read 请求在数据未准备好的情况下立即返回，可以继续往下执行，此时应用程序不断轮询内核，直到数据准备好，内核将数据拷贝到应用程序缓冲区，read 调用才可以获取到结果。这里最后一次 read 调用，获取数据的过程，是一个同步的过程，是需要等待的过程。这里的同步指的是内核态的数据拷贝到用户程序的缓存区这个过程

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

这个做法大大改善了 CPU 的利用率，因为当调用了 I/O 多路复用接口，如果没有事件发生，那么当前线程就会发生阻塞，这时 CPU 会切换其他线程执行任务，等内核发现有事件到来的时候，会唤醒阻塞在 I/O 多路复用接口的线程，然后用户可以进行后续的事件处理。

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

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

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

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

PageCache

PageCache

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

page 与 Page Cache

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

另一方面，并不是所有 page 都被组织为 Page Cache。

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

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

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

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

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

Swap 与缺页中断

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

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

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

Linux 通过一个 swappiness 参数来控制 Swap 机制：这个参数值可为 0-100，控制系统 swap 的优先级：

• 高数值：较高频率的 swap，进程不活跃时主动将其转换出物理内存。
• 低数值：较低频率的 swap，这可以确保交互式不因为内存空间频繁地交换到磁盘而提高响应延迟。

最后，为什么 SwapCached 也是 Page Cache 的一部分？

这是因为当匿名页（Inactive (anon) 以及 Active (anon)）先被交换（swap out）到磁盘上后，然后再加载回（swap in）内存中，由于读入到内存后原来的 Swap File 还在，所以 SwapCached 也可以认为是 File-backed page，即属于 Page Cache。这个过程如下图所示。

Page Cache 与 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 等算法淘汰缓存页。

在 Linux 2.4 版本的内核之前，Page Cache 与 buffer cache 是完全分离的。但是，块设备大多是磁盘，磁盘上的数据又大多通过文件系统来组织，这种设计导致很多数据被缓存了两次，浪费内存。

所以在 2.4 版本内核之后，两块缓存近似融合在了一起：如果一个文件的页加载到了 Page Cache，那么同时 buffer cache 只需要维护块指向页的指针就可以了。只有那些没有文件表示的块，或者绕过了文件系统直接操作（如 dd 命令）的块，才会真正放到 buffer cache 里。

Page Cache 与预读

操作系统为基于 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 数据的读取。

PageCache 的优点主要是两个：

• 缓存最近被访问的数据；

  通常，刚被访问的数据在短时间内再次被访问的概率很高，于是我们可以用 PageCache 来缓存最近被访问的数据，当空间不足时淘汰最久未被访问的缓存。

• 预读功能；

Page Cache和文件持久化和可靠性

我们考虑如下一致性问题：如果发生写操作并且对应的数据在 Page Cache 中，那么写操作就会直接作用于 Page Cache 中，此时如果数据还没刷新到磁盘，那么内存中的数据就领先于磁盘，此时对应 page 就被称为 Dirty page。

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

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

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

Page Cache优劣

优点

1. 加快数据访问

如果数据能够在内存中进行缓存，那么下一次访问就不需要通过磁盘 I/O 了，直接命中内存缓存即可。

由于内存访问比磁盘访问快很多，因此加快数据访问是 Page Cache 的一大优势。

2. 减少 I/O 次数，提高系统磁盘 I/O 吞吐量

得益于 Page Cache 的缓存以及预读能力，而程序又往往符合局部性原理，因此通过一次 I/O 将多个 page 装入 Page Cache 能够减少磁盘 I/O 次数， 进而提高系统磁盘 I/O 吞吐量。

缺点

page cache 也有其劣势，最直接的缺点是需要占用额外物理内存空间，物理内存在比较紧俏的时候可能会导致频繁的 swap 操作，最终导致系统的磁盘 I/O 负载的上升。

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

“直接” 在这里还有另一层语义：其他所有技术中，数据至少需要在内核空间存储一份，但是在 Direct I/O 技术中，数据直接存储在用户空间中，绕过了内核。

此时用户空间直接通过 DMA 的方式与磁盘以及网卡进行数据拷贝。

Direct I/O 的读写非常有特点：

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

网络系统

零拷贝

DMA

DMA：直接内存访问

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

传统文件传输

传统 I/O 的工作方式是，数据读取和写入是从用户空间到内核空间来回复制，而内核空间的数据是通过操作系统层面的 I/O 接口从磁盘读取或写入。

期间共发生了 4 次用户态与内核态的上下文切换

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

实现零拷贝

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

• mmap + write
• sendfile
• sendfile+网卡 SG-DMA

mmap + write

将一片内核空间映射在用户空间来充当缓存区，减少两次（内核到用户，用户到内核），增加一次（内核到内核）。总共3次拷贝，4次切换。

sendfile

该系统调用，可以直接把内核缓冲区里的数据拷贝到 socket 缓冲区里，不再拷贝到用户态。

这样就只有 2 次上下文切换，和 3 次数据拷贝。

sendfile+网卡 SG-DMA

只需要 2 次上下文切换和数据拷贝次数，就可以完成文件的传输，而且 2 次的数据拷贝过程，都不需要通过 CPU，2 次都是由 DMA 来搬运。

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

大文件传输

大文件的传输不应该使用 PageCache，因为可能由于 PageCache 被大文件占据，而导致「热点」小文件无法利用到 PageCache。

所以在高并发的场景下，针对大文件的传输的方式，应该使用「异步 I/O + 直接 I/O」来替代零拷贝技术。

直接 I/O 应用场景常见的两种：

• 应用程序已经实现了磁盘数据的缓存，那么可以不需要 PageCache 再次缓存，减少额外的性能损耗。在 MySQL 数据库中，可以通过参数设置开启直接 I/O，默认是不开启；
• 传输大文件的时候，由于大文件难以命中 PageCache 缓存，而且会占满 PageCache 导致「热点」文件无法充分利用缓存，从而增大了性能开销，因此，这时应该使用直接 I/O。

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

• 传输大文件的时候，使用「异步 I/O + 直接 I/O」；
• 传输小文件的时候，则使用「零拷贝技术」；

Linux网络Server并发模型

原文

单线程Accept(无IO复用)

一个请求完了才能请求别的请求。

单线程Accept+多线程读写业务（无IO复用）

每次来一个请求就新开一个线程负责进行通信。

但是随着客户端增加，线程数也会增加，切换成本大。

单线程多路IO复用

可以单线程监听多个客户端，但是同一时间只能处理一个读写业务，大量的请求会有延迟现象。

单线程多路IO复用+多线程读写业务(业务工作池)（常用）

业务交给工作池去执行，主线程负责所有客户端的读写操作。业务并发数由worker工作池决定，缩短了读写的时间。

但是读写成为瓶颈，请求和结果都需要排队。

单线程IO复用+多线程IO复用(链接线程池)

来一个请求分发到不同线程来进行监听并进行读写操作，提高了读写效率和监听数量。

但是读写依旧有瓶颈，而且单线程内的连接会有延迟。

(进程版)、单进程多路I/O复用+多进程多路I/O复用(进程池)

主进程监听请求但不连接，分发请求信号，子进程抢占并连接。资源独立，安全性高，其他和上一个差不多。

但是占用内存大。

单线程多路I/O复用+多线程多路I/O复用+多线程

主线程分发连接给子线程，子线程对于每个请求开线程来进行读写操作。保证响应的并发性和读写的并发性。

缺点：过于理想化，要求CPU核心数非常大。

一致性hash

负载均衡

引入一个中间的负载均衡层，让它将外界的请求「轮流」的转发给内部的集群

考虑到每个节点的硬件配置有所区别，我们可以引入权重值，将硬件配置更好的节点的权重值设高，然后根据各个节点的权重值，按照一定比重分配在不同的节点上，让硬件配置更好的节点承担更多的请求，这种算法叫做加权轮询。

当我们想提高系统的容量，就会将数据水平切分到不同的节点来存储，也就是将数据分布到了不同的节点。比如一个分布式 KV（key-valu） 缓存系统，某个 key 应该到哪个或者哪些节点上获得，应该是确定的，不是说任意访问一个节点都可以得到缓存结果的。

hash算法

如果客户端要获取指定 key 的数据，通过下面的公式可以定位节点：

1

hash(key) % 3

但是有一个很致命的问题，如果节点数量发生了变化，也就是在对系统做扩容或者缩容时，必须迁移改变了映射关系的数据，否则会出现查询不到数据的问题。

一致性hash

一致哈希算法也用了取模运算，但与哈希算法不同的是，哈希算法是对节点的数量进行取模运算，而一致哈希算法是对 2^32 进行取模运算，是一个固定的值。

我们把这个圆想象成由 2^32 个点组成的圆，这个圆环被称为哈希环

一致性哈希要进行两步哈希：

• 第一步：对存储节点进行哈希计算，也就是对存储节点做哈希映射，比如根据节点的 IP 地址进行哈希；
• 第二步：当对数据进行存储或访问时，对数据进行哈希映射；

所以，一致性哈希是指将「存储节点」和「数据」都映射到一个首尾相连的哈希环上。

1
2
3
4
5
6
7
8
9

一致性哈希算法将 key 映射到 2^32 的空间中，将这个数字首尾相连，形成一个环.
   1. 计算节点/机器(通常使用节点的名称、编号和 IP 地址)的哈希值，放置在环上。
   2. 计算 key 的哈希值，放置在环上，顺时针寻找到的第一个节点，就是应选取的节点/机器。
优点:
   一致性哈希算法，在新增/删除节点时，只需要重新定位该节点附近的一小部分数据，而不需要重新定位所有的节点
问题:数据倾斜
解决:使用虚拟节点扩充节点数
   1. 计算虚拟节点的 Hash 值，放置在环上。
   2. 计算 key 的 Hash 值，在环上顺时针寻找到应选取的虚拟节点，例如是 peer2-1，那么就对应真实节点 peer2。

linux命令

• tail -f xx.out 查看日志（动态显示日志）

• netstat -anp | grep 端口号 查看端口使用情况

• ps -elf|grep xxx 显示进程pid

• kill 使用kill命令来终结进程。先使用ps命令找到进程id，使用kill -9命令，终止进程。

  1 2 3 4 5 6 7 8

  # 只有第9种信号(SIGKILL)才可以无条件终止进程，其他信号进程都有权利忽略。 HUP 1 终端挂断 INT 2 中断（同 Ctrl + C） QUIT 3 退出（同 Ctrl + \） KILL 9 强制终止 TERM 15 终止 CONT 18 继续（与STOP相反，fg/bg命令） STOP 19 暂停（同 Ctrl + Z）

• tar –xvf file.tar 解压 tar包

• unzip file.zip 解压zip

• unrar e file.rar 解压rar

• free -m 查看服务器内存使用情况

• less 按需加载文件

• wc -l 统计行数