操作系统

Linux内核源码地址

Linux3.8.7内核源码链接

伟大的原理：局部性原理

程序在执行时呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分；相应的它所访问的空间也局限于某个区域
时间局部性：如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。
空间局部性：在最近的将来将用到的信息很可能与正在使用的信息在空间地址上是临近的。
顺序局部性：在典型程序中，除转移类指令外，大部分指令是顺序进行的。

初识操作系统

现代操作系统，内核⼀般会提供 4 个基本能⼒：
进程调度：决定哪个进程、线程使⽤ CPU，也就是进程调度的能⼒；
内存管理：决定内存的分配和回收，也就是内存管理的能⼒；
设管理备：为进程与硬件设备之间提供通信能⼒，也就是硬件通信能⼒；
系统调⽤：如果应⽤程序要运⾏更⾼权限运⾏的服务，那么就需要有系统调⽤，它是⽤户程序与操作系统之间的接⼝。

内核

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

• 宏内核，包含多个模块，一个完整的可执行程序，且拥有最高的权限；内核的所有代码，包括子系统（如内存管理、文件管理、设备驱动程序）都打包到一个文件中。内核中的每一个函数都可以访问到内核中所有其他部分。目前支持模块的动态装卸(裁剪)。宏内核的特征是系统内核的所有模块，比如进程调度、内存管理、文件系统、设备驱动等，都运行在内核态。
• 微内核，有一个最小版本的内核，一些模块和服务则由用户态管理；最基本的功能由中央内核（微内核）实现。所有其他的功能都委托给一些独立进程，这些进程通过明确定义的通信接口与中心内核通信
• 混合内核，是宏内核和微内核的结合体，内核中抽象出了微内核的概念，也就是内核中会有一个小型的内核，其他模块就在这个基础上搭建，整个内核是个完整的程序；

Window 的内核设计是混合型内核，Linux 的内核是宏内核

用户态->内核态的方式

1. 系统调用
   这是用户态进程主动要求切换到内核态的一种方式，用户态进程通过系统调用申请使用操作系统提供的服务程序完成工作，比如前例中fork()实际上就是执行了一个创建新进程的系统调用。而系统调用的机制其核心还是使用了操作系统为用户特别开放的一个中断来实现
2. 异常
   当CPU在执行运行在用户态下的程序时，发生了某些事先不可知的异常，这时会触发由当前运行进程切换到处理此异常的内核相关程序中，也就转到了内核态，比如缺页异常。
3. 外围设备的中断
   当外围设备完成用户请求的操作后，会向CPU发出相应的中断信号，这时CPU会暂停执行下一条即将要执行的指令转而去执行与中断信号对应的处理程序，如果先前执行的指令是用户态下的程序，那么这个转换的过程自然也就发生了由用户态到内核态的切换。比如硬盘读写操作完成，系统会切换到硬盘读写的中断处理程序中执行后续操作等。

Linux内核体系结构

系统调用接口、进程管理、内存管理、虚拟文件系统、网络堆栈、设备驱动程序、硬件架构的相关代码。

系统调用接口

SCI 层提供了某些机制执行从用户空间到内核的函数调用。正如前面讨论的一样，这个接口依赖于体系结构，甚至在相同的处理器家族内也是如此。SCI 实际上是一个非常有用的函数调用多路复用和多路分解服务。在 ./linux/kernel 中您可以找到 SCI 的实现，并在 ./linux/arch 中找到依赖于体系结构的部分。

进程管理

进程管理的重点是进程的执行。在内核中，这些进程称为线程，代表了单独的处理器虚拟化（线程代码、数据、堆栈和 CPU 寄存器）。在用户空间，通常使用进程 这个术语，不过 Linux 实现并没有区分这两个概念（进程和线程）。内核通过 SCI 提供了一个应用程序编程接口（API）来创建一个新进程（fork、exec 或 Portable Operating System Interface [POSIX] 函数），停止进程（kill、exit），并在它们之间进行通信和同步（signal 或者 POSIX 机制）。

进程管理还包括处理活动进程之间共享 CPU 的需求。内核实现了一种新型的调度算法，不管有多少个线程在竞争 CPU，这种算法都可以在固定时间内进行操作。这种算法就称为 O(1) 调度程序，这个名字就表示它调度多个线程所使用的时间和调度一个线程所使用的时间是相同的。O(1) 调度程序也可以支持多处理器（称为对称多处理器或 SMP）。您可以在 ./linux/kernel 中找到进程管理的源代码，在 ./linux/arch 中可以找到依赖于体系结构的源代码。

内存管理

内核所管理的另外一个重要资源是内存。为了提高效率，如果由硬件管理虚拟内存，内存是按照所谓的内存页 方式进行管理的（对于大部分体系结构来说都是 4KB）。Linux 包括了管理可用内存的方式，以及物理和虚拟映射所使用的硬件机制。不过内存管理要管理的可不止 4KB 缓冲区。Linux 提供了对 4KB 缓冲区的抽象，例如 slab 分配器。这种内存管理模式使用 4KB 缓冲区为基数，然后从中分配结构，并跟踪内存页使用情况，比如哪些内存页是满的，哪些页面没有完全使用，哪些页面为空。这样就允许该模式根据系统需要来动态调整内存使用。为了支持多个用户使用内存，有时会出现可用内存被消耗光的情况。由于这个原因，页面可以移出内存并放入磁盘中。这个过程称为交换，因为页面会被从内存交换到硬盘上。内存管理的源代码可以在 ./linux/mm 中找到。

虚拟文件系统

虚拟文件系统（VFS）是 Linux 内核中非常有用的一个方面，因为它为文件系统提供了一个通用的接口抽象。VFS 在 SCI 和内核所支持的文件系统之间提供了一个交换层（请参看图4）。

Linux文件系统层次结构

在 VFS 上面，是对诸如 open、close、read 和 write 之类的函数的一个通用 API 抽象。在 VFS 下面是文件系统抽象，它定义了上层函数的实现方式。它们是给定文件系统（超过 50 个）的插件。文件系统的源代码可以在 ./linux/fs 中找到。文件系统层之下是缓冲区缓存，它为文件系统层提供了一个通用函数集（与具体文件系统无关）。这个缓存层通过将数据保留一段时间（或者随即预先读取数据以便在需要是就可用）优化了对物理设备的访问。缓冲区缓存之下是设备驱动程序，它实现了特定物理设备的接口。

网络堆栈

网络堆栈在设计上遵循模拟协议本身的分层体系结构。回想一下，Internet Protocol (IP) 是传输协议（通常称为传输控制协议或 TCP）下面的核心网络层协议。TCP 上面是 socket 层，它是通过 SCI 进行调用的。socket 层是网络子系统的标准 API，它为各种网络协议提供了一个用户接口。从原始帧访问到 IP 协议数据单元（PDU），再到 TCP 和 User Datagram Protocol (UDP)，socket 层提供了一种标准化的方法来管理连接，并在各个终点之间移动数据。内核中网络源代码可以在 ./linux/net 中找到。

设备驱动程序

Linux 内核中有大量代码都在设备驱动程序中，它们能够运转特定的硬件设备。Linux 源码树提供了一个驱动程序子目录，这个目录又进一步划分为各种支持设备，例如 Bluetooth、I2C、serial 等。设备驱动程序的代码可以在 ./linux/drivers 中找到。

依赖体系结构的代码

尽管 Linux 很大程度上独立于所运行的体系结构，但是有些元素则必须考虑体系结构才能正常操作并实现更高效率。./linux/arch 子目录定义了内核源代码中依赖于体系结构的部分，其中包含了各种特定于体系结构的子目录（共同组成了 BSP）。对于一个典型的桌面系统来说，使用的是 x86 目录。每个体系结构子目录都包含了很多其他子目录，每个子目录都关注内核中的一个特定方面，例如引导、内核、内存管理等。这些依赖体系结构的代码可以在 ./linux/arch 中找到。

如果 Linux 内核的可移植性和效率还不够好，Linux 还提供了其他一些特性，它们无法划分到上面的分类中。作为一个生产操作系统和开源软件，Linux 是测试新协议及其增强的良好平台。Linux 支持大量网络协议，包括典型的 TCP/IP，以及高速网络的扩展（大于 1 Gigabit Ethernet [GbE] 和 10 GbE）。Linux 也可以支持诸如流控制传输协议（SCTP）之类的协议，它提供了很多比 TCP 更高级的特性（是传输层协议的接替者）。

Linux 还是一个动态内核，支持动态添加或删除软件组件。被称为动态可加载内核模块，它们可以在引导时根据需要（当前特定设备需要这个模块）或在任何时候由用户插入。

Linux 最新的一个增强是可以用作其他操作系统的操作系统（称为系统管理程序）。最近，对内核进行了修改，称为基于内核的虚拟机（KVM）。这个修改为用户空间启用了一个新的接口，它可以允许其他操作系统在启用了 KVM 的内核之上运行。除了运行 Linux 的其他实例之外， Microsoft Windows也可以进行虚拟化。惟一的限制是底层处理器必须支持新的虚拟化指令。

CPU

CPU三级缓存

cat /sys/devices/system/cpu/cpu0/cache/index3/size

CPU性能

CPU读取数据方式

CPU的缓存写入

在什么时机才把 Cache 中的数据写回到内存？
写直达：
把数据同时写入内存和 Cache 中

写回
写错时获取策略 ：当发生写操作时，新的数据仅仅被写入 Cache Block 里，只有当修改过的 Cache Block「被替换」时才需要写到内存中，减少了数据写回内存的频率

内存读取？
保持独占机制

CPU缓存一致性

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

解决方式
写失效：当一个CPU修改了数据，如果其他CPU有该数据，则通知其为无效；
写更新：当一个CPU修改了数据，如果其他CPU有该数据，则通知其更新新数据，（写更新会导致大量的更新操作）。

总线嗅探

属于写更新
当 A 号 CPU 核心修改了 L1 Cache 中 i 变量的值，通过总线把这个事件广播通知给其他所有的核心，然后每个 CPU 核心都会监听总线上的广播事件，并检查是否有相同的数据在自己的 L1 Cache 里面，如果 B 号 CPU 核心的 L1 Cache 中有该数据，那么也需要把该数据更新到自己的 L1 Cache

MESI 协议

属于写失效，写回

• Modified，已修改
  缓存行是脏的（dirty），与内存的值不同。如果别的CPU内核要读内存这块数据，该缓存行必须回写到内存，状态变为共享(S).
• Exclusive，独占
  缓存行只在当前缓存中，但是干净的——缓存数据相同于内存数据。当别的缓存读取它时，状态变为共享；当前写数据时，变为已修改状态。
• Shared，共享
  缓存行也存在于其它缓存中且是未修改的。缓存行可以在任意时刻抛弃。
• Invalidated，已失效
  缓存行是无效的

当块标记为M（已修改）时，其他高速缓存中块的副本必须标记为I（无效）。

1. 当一个处理器需要访问某个内存数据时，它首先会检查自己的缓存中是否有该数据的副本。如果缓存中没有该数据的副本，则会发出一个缓存不命中（miss）请求，从主内存中获取该数据的副本，并将该数据的副本存储到自己的缓存中。
2. 当一个处理器发出miss请求时，如果该数据的副本已经存在于另一个处理器或核心的缓存中（即处于共享状态），则该处理器可以从另一个处理器的缓存中复制该数据的副本。这个过程称为缓存到缓存复制（cache-to-cache transfer）。
3. 如果两个缓存都处于修改状态，那么必须先将其中一个缓存的数据写回到主内存，然后才能进行缓存到缓存复制。

CPU软中断

Linux 系统为了解决中断处理程序执行过长和中断丢失的问题，将中断过程分成了两个阶段，分别是「上半部和下半部分」。

上半部用来快速处理中断，一般会暂时关闭中断请求，主要负责处理跟硬件紧密相关或者时间敏感的事情。
下半部用来延迟处理上半部未完成的工作，一般以「内核线程」的方式运行。

内存管理

为什么要有虚拟内存？

局部性原理
单片机的 CPU 是直接操作内存的「物理地址」，要想在内存中同时运行两个程序是不可能的。如果第一个程序在某个位置写入一个新的值，将会擦掉第二个程序存放在相同位置上的所有内容

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

虚拟内存

内存分段

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

缺点：

1. 存在内存碎⽚的问题
   如果这个 256MB 不是连续的，被分成了两段 128 MB 内存，这就会导致没有空间再打开⼀个200MB 的程序。

解决外部内存碎⽚的问题就是内存交换。这个内存交换空间，在 Linux 系统⾥，也就是我们常看到的 Swap 空间，这块空间是从硬盘划分出来的，⽤于内存与硬盘的空间交换。

1. 可能内存交换的效率低的问题
   如果内存交换的时候，交换的是⼀个占内存空间很⼤的程序，这样整个机器都会显得卡顿。

   内存分页

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

虚拟地址与物理地址之间通过页表来映射，如下图：

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

详细转换如下图：

缺点：

内存碎片：
当进程访问的虚拟地址在⻚表中查不到时，系统会产⽣⼀个缺⻚异常，进⼊系统内核空间分配物理内存、更新进程⻚表，最后再返回⽤户空间，恢复进程的运⾏采⽤了分⻚，那么释放的内存都是以⻚为单位释放的，也就不会产⽣⽆法给进程使⽤的⼩内存。
但是，因为内存分页机制分配内存的最小单位是一页，即使程序不足一页大小，我们最少只能分配一个页，所以页内会出现内存浪费，所以针对内存分页机制会有内部内存碎片的现象。

空间上的缺陷：
在 32 位的环境下，虚拟地址空间共有 4GB，假设一个页的大小是 4KB（2^12），一个进程的页表需要装下 100 多万个「页表项」（2^20） ，每个「页表项」需要 4 个字节大小来存储，那么整个 4GB 空间的映射就需要有 4MB 的内存来存储页表。

这 4MB 大小的页表，看起来也不是很大。但是要知道每个进程都是有自己的虚拟地址空间的，也就说都有自己的页表。那么，100 个进程的话，就需要 400MB 的内存来存储页表

多级分页

将页表（一级页表）分为 1024 个页表（二级页表），每个表（二级页表）中包含 1024 个「页表项」，形成二级分页。如下图所示：

映射 4GB 地址空间需要 4KB（一级页表）+ 4MB（二级页表）的内存，更大的空间？（局部性原理的充分应用）
局部性原理：
每个进程都有 4GB 的虚拟地址空间，对于大多数程序来说，其使用到的空间远未达到 4GB，因为会存在部分对应的页表项都是空的，根本没有分配，
对于已分配的页表项，如果存在最近一定时间未访问的页表，在物理内存紧张的情况下，操作系统会将页面换出到硬盘，也就是说不会占用物理内存。

用时分配：
如果使用了二级分页，一级页表就可以覆盖整个 4GB 虚拟地址空间，但如果某个一级页表的页表项没有被用到，也就不需要创建这个页表项对应的二级页表了，即可以在需要时才创建二级页表。
例如：假设只有 20% 的一级页表项被用到了，那么页表占用的内存空间就只有 4KB（一级页表） + 20% * 4MB（二级页表）= 0.804MB < 4MB

总结：
页表一定要覆盖全部虚拟地址空间，不分级的页表就需要有 100 多万个页表项来映射，而二级分页则只需要 1024 个页表项（此时一级页表覆盖到了全部虚拟地址空间，二级页表在需要时创建）。

TLB技术

局部性原理的充分应用
所以，把最常访问的几个页表项存储到访问速度更快的硬件，在CPU 芯片中，加入了一个专门存放程序最常访问的页表项的 Cache，这个 Cache 就是 TLB ，通常称为页表缓存、转址旁路缓存、快表等

在CPU 中，封装了内存管理单元芯片，它用来完成地址转换和 TLB 的访问与交互。有了 TLB 后，那么 CPU 在寻址时，会先查 TLB，如果没找到，才会继续查常规的页表。TLB 的命中率其实是很高的，因为程序最常访问的页就那么几个。

段页式存储

Linux内核的内存管理方式

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

在 Linux 操作系统中，虚拟地址空间的内部又被分为内核空间和用户空间两部分

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

伙伴算法

unsigned long __init free_all_bootmem(void)

static unsigned long __init free_all_bootmem_core(bootmem_data_t *bdata)

• 内部碎片是已经被分配出去的（能明确指出属于哪个进程）内存空间大于请求所需的内存空间，不能被利用的空间就是内部碎片。
• 外部碎片是指还没分配出去（不属于任何进程），但是由于大小无法分配给申请内存空间的新进程的内存空闲块。

伙伴系统算法来解决内存外部碎片的问题。swap分区也为一种方法，把所有的空闲页框分组为 11 块链表，每一块链表分别包含大小为1，2，4，8，16，32，64，128，256，512 和 1024 个连续的页框。
假设系统中有 1MB 大小的内存需要动态管理，按照伙伴算法的要求：需要将这1M大小的内存进行划分。这里，我们将这1M的内存分为 64K、64K、128K、256K、和512K 共五个部分，如下图a所示

1. 此时，如果有一个程序A想要申请一块45K大小的内存，则系统会将第一块64K的内存块分配给该程序（产生内部碎片为代价），如图b所示；
2. 然后程序B向系统申请一块68K大小的内存，系统会将128K内存分配给该程序，如图c所示；
3. 接下来，程序C要申请一块大小为35K的内存。系统将空闲的64K内存分配给该程序，如图d所示；
4. 之后程序D需要一块大小为90K的内存。当程序提出申请时，系统本该分配给程序D一块128K大小的内存，但此时内存中已经没有空闲的128K内存块了，于是根据伙伴算法的原理，系统会将256K大小的内存块平分，将其中一块分配给程序D，另一块作为空闲内存块保留，等待以后使用，如图e所示；
5. 紧接着，程序C释放了它申请的64K内存。在内存释放的同时，系统还负责检查与之相邻并且同样大小的内存是否也空闲，由于此时程序A并没有释放它的内存，所以系统只会将程序C的64K内存回收，如图f所示；
6. 然后程序A也释放掉由它申请的64K内存，系统随机发现与之相邻且大小相同的一段内存块恰好也处于空闲状态。于是，将两者合并成128K内存，如图g所示；
7. 之后程序B释放掉它的128k，系统也将这块内存与相邻的128K内存合并成256K的空闲内存，如图h所示；
8. 最后程序D也释放掉它的内存，经过三次合并后，系统得到了一块1024K的完整内存，如图i所示。

总结

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

内存进阶

前言

Linux的用户空间和内核空间内存大小

用户空间内存从低到高分别是 6 种不同的内存段：代表了不同的含义

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

缺页中断

‌缺页中断‌是指在程序执行时，访问的页面不在当前内存页表中，需要从硬盘中调入到内存中的情况。这是虚拟内存管理的一部分。

缺页中断的发生场景

1. ‌页面首次访问‌
   当程序首次访问一个尚未加载到内存中的页面时，会触发缺页中断。这是因为操作系统并不会一次性将整个程序加载到内存，而是按需分页加载。
2. ‌页面置换‌
   当内存中的页面不足以存放当前需要访问的页面时，操作系统需要进行页面置换。如果需要访问的页面不在内存中，就会发生缺页中断，触发页面置换算法，将一个不再需要的页面调出内存，将需要访问的页面调入内存。
3. ‌写时复制‌
   在某些情况下，多个进程共享同一页面，当其中一个进程尝试写入该页面时，操作系统会将页面复制一份，然后进行写操作。如果写操作导致需要访问一个新的页面，就可能触发缺页中断。

缺页中断的处理步骤

1. ‌硬件陷入到内核‌
   当CPU发出的虚拟地址所对应的页面不在物理内存时，硬件会陷入到内核。
2. ‌保护通用寄存器‌
   保护通用寄存器的内容，以便在处理完缺页中断后能够恢复。
3. ‌操作系统判断所需的虚拟页面号‌
   操作系统需要判断所需的虚拟页面号是否存在。
4. ‌地址合法性检查‌
   操作系统检查地址的合法性。
5. ‌选择物理页面‌
   操作系统选择一个物理页面用来存放将要调入的页面。
6. ‌写盘操作‌
   如果选择的物理页面包含有未写入磁盘的内容，则首先进行写盘操作。
7. ‌更新页表‌
   更新页表以反映新的映射关系。
8. ‌恢复寄存器‌
   恢复通用寄存器的内容。
9. ‌程序继续运行‌
   处理完缺页中断后，程序可以继续运行。‌

malloc

malloc 是如何分配内存的？

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

• 方式二：通过 mmap() 系统调用在文件映射区域分配内存；也就是从文件映射区“偷”了一块内存

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

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

grep -i "DEFAULT_MMAP_THRESHOLD_MIN" malloc/malloc.c

malloc(1) 会分配多大的虚拟内存？

132K

#include <stdio.h>
#include <malloc.h>
#include <unistd.h>
int main()
{
    printf("使用cat /proc/%d/maps查看内存分配\n", getpid());

    // 申请1字节的内存
    void *addr = malloc(1);
    printf("此1字节的内存起始地址：%x\n", addr);
    printf("使用cat /proc/%d/maps查看内存分配\n", getpid());

    // 将程序阻塞，当输入任意字符时才往下执行
    getchar();

    // 释放内存
    free(addr);
    printf("释放了1字节的内存，但heap堆并不会释放\n");

    getchar();
    return 0;
}

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

#include <stdio.h>
#include <malloc.h>
#include <unistd.h>

int main() {
  //申请1字节的内存
  void *addr = malloc(128*1024);
  printf("此128KB字节的内存起始地址：%x\n", addr);
  printf("使用cat /proc/%d/maps查看内存分配\n",getpid());

  //将程序阻塞，当输入任意字符时才往下执行
  getchar();

  //释放内存
  free(addr);
  printf("释放了128KB字节的内存，内存也归还给了操作系统\n");

  getchar();
  return 0;
}

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

申请内存的操作应该避免频繁的系统调用，如果都用 mmap 来分配内存，等于每次都要执行系统调用。
另外，因为 mmap 分配的内存每次释放的时候，都会归还给操作系统，于是每次 mmap 分配的虚拟地址都是缺页状态的，然后在第一次访问该虚拟地址的时候，就会触发缺页中断。

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

随着系统频繁地 malloc 和 free ，尤其对于小块内存，堆内将产生越来越多不可用的碎片,导致“内存泄露”

free() 函数只传入一个内存地址，为什么能知道要释放多大的内存？

运行上述脚本代码可发现：打印的地址比实际程序地址多出来 0x10 （16字节）
多出来的 16 字节就是保存了该内存块的描述信息，比如有该内存块的大小。

内存对齐

原因

• 操作系统在数据读取的时候，其实并不是一字节一字节进行读取的，而是一段一段进行读取
• 我们假如是4bytes。假如我们要读取一个int，如果不对齐，这个int占用第1块的后3位和第2块的第1位，需要两次读取，将两次的数据组合起来。这样CPU将做出“多余操作”，严重影响处理速度。
• 因此需要进行内存对齐，从而提高CPU处理速率，而这项任务就交给编译器进行相应的地址分配和优化，编译器会根据提供参数或者目标环境进行相应的内存对齐。

结构体内存对齐的规则

未指定#pragma pack时：

1. 第一个成员起始于0偏移处；
2. 每个成员按其类型大小进行对齐；
3. 结构体总长度必须为最大类型参数的整数倍；
4. 对于数组，可以拆开看做n个数组元素

指定#pragma pack(n)时：

1. 第一个成员起始于0偏移处；
2. 每个成员按其类型大小和指定对齐参数n中较小的一个进行对齐；
3. 结构体总长度必须为最大类型参数大小和对齐参数中较小值的整数倍；
4. 对于数组，可以拆开看做n个数组元素

struct A {
    int a;
    char b;
    short c;
};
struct B {
    char b;
    int a;
    short c;
};

sizeof(A) = 8;sizeof(B) = 12。

	a	b	c
A的内存布局：	1111	1*	11
B的内存布局：	1*	1111	11**

其中星号*表示填充的字节。A中，b后面为何要补充一个字节？因为c为short，其起始位置要为2的倍数，就是原则1。c的后面没有补充，因为b和c正好占用4个字节，整个A占用空间为4的倍数，也就是最大成员int类型的倍数，所以不用补充。B中，b是char为1，b后面补充了3个字节，因为a是int为4，根据原则1，起始位置要为4的倍数，所以b后面要补充3个字节。c后面补充两个字节，根据原则3，整个B占用空间要为4的倍数，c后面不补充，整个B的空间为10，不符，所以要补充2个字节。

struct A {
    int a;
    double b;
    float c;
};
struct B {
    char e[2];
    int f;
    double g;
    short h;
    struct A i;
};

sizeof(A) = 24; 这个比较好理解，int为4，double为8，float为4，总长为8的倍数，补齐，所以整个A为24。
sizeof(B) = 48; 看看B的内存布局。

	e	f	g	h	i
B的内存布局	11**	1111	11111111	11	1111, 11111111, 1111

i其实就是A的内存布局。i的起始位置要为24的倍数，所以h后面要补齐。

大小端模式

• 大端存储是指低字节存储在高地址
• 小端存储是指低字节存储在低地址
  根据联合体来判断该系统是大端还是小端。因为联合体变量总是从低地址存储
  判断大小端的代码：

  int main() {
      union test {
          int i;
          char c;
      };
      test t;
      t.i = 1;
      if (t.c == 1) {
          cout << "big" << endl;
      } else {
          cout << "little" << endl;
      }
  }
  //1在内存中存储为0x000001
  //如果第一个字节为0，说明机器是大端存储，低位字节1存储在高位地址
  //如果第一个字节为1，说明机器是小端存储，低位字节1存储在低位地址

内存回收

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

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

哪些内存可以被回收？

• 文件页：内核缓存的磁盘数据（Buffer）和内核缓存的文件数据（Cache）都叫作文件页。大部分文件页，都可以直接释放内存，以后有需要时，再从磁盘重新读取就可以了。而那些被应用程序修改过，并且暂时还没写入磁盘的数据（也就是脏页），就得先写入磁盘，然后才能进行内存释放。回收干净页的方式是直接释放内存，回收脏页的方式是先写回磁盘后再释放内存。

• 匿名页：这部分内存没有实际载体，不像文件缓存有硬盘文件这样一个载体，比如堆、栈数据等。这部分内存很可能还要再次被访问，所以不能直接释放内存，它们回收的方式是通过 Linux 的Swap 机制，Swap 会把不常访问的内存先写到磁盘中，然后”释放”这些内存，给其他更需要的进程使用。再次访问这些内存时，重新从磁盘读入内存就可以了。

Linux 提供了一个 /proc/sys/vm/swappiness 选项，用来调整文件页和匿名页的回收倾向。数值越大，越积极使用 Swap

cat /proc/sys/vm/swappiness

基于LRU算法

维护着 active 和 inactive 两个双向链表，其中：
active_list 活跃内存页链表，这里存放的是最近被访问过（活跃）的内存页；
inactive_list 不活跃内存页链表，这里存放的是很少被访问（非活跃）的内存页；

cat /proc/meminfo | grep -i active | sort

如何保护一个进程不被 OOM 杀掉呢？

Linux 内核里有一个 oom_badness() 函数

// points 代表打分的结果
// process_pages 代表进程已经使用的物理内存页面数
// oom_score_adj 代表 OOM 校准值
// totalpages 代表系统总的可用页面数
points = process_pages + oom_score_adj*totalpages/1000

oom_score_adj。它是可以通过 /proc/[pid]/oom_score_adj 来配置的，设置 -1000 到 1000 之间的任意一个数值，-1000不会被杀死

swap机制的作用

在 32 位/64 位操作系统环境下，申请的虚拟内存超过物理内存后会怎么样？

在 32 位操作系统，因为进程最大只能申请 3 GB 大小的虚拟内存，所以直接申请 8G 内存，会申请失败。
在 64 位操作系统，因为进程最大只能申请 128 TB 大小的虚拟内存，即使物理内存只有 4GB，申请 8G 内存也是没问题，因为申请的内存是虚拟内存。
程序申请的虚拟内存，如果没有被使用，它是不会占用物理空间的。当访问这块虚拟内存后，操作系统才会进行物理内存分配。

如果申请物理内存大小超过了空闲物理内存大小，就要看操作系统有没有开启 Swap 机制：
如果没有开启 Swap 机制，程序就会直接 OOM；
如果有开启 Swap 机制，程序可以正常运行。

free -m    #linux
dir /A     #windows

内存的预读失效和缓存污染

预读失效：读磁盘多读了一些，但是没有用到（局部性原理的充分应用）
缓存污染：批量读，把热点数据挤出去

以上问题十分常见，包括操作系统，redis，mysql等
LRU算法是基于最近使用时间，其核心思想是淘汰最长时间未被使用的数据，这适用于访问模式具有时间局部性的场景；
LFU算法是基于访问频率，其核心思想是淘汰访问频率最低的数据，这适用于访问模式具有频率局部性的场景。

Redis实现 LFU 算法，MySql 和 Linux 操作系统是改进 LRU 算法

有关Redis如何实现LFU，请参照Redis—Redis的内存策略—LRU和LFU
有关MySql如何改进LRU，请参照MySql—内存篇

Linux 的 Page Cache 和 MySQL 的 Buffer Pool

解决预读失效

• Linux 操作系统实现两个了 LRU 链表：活跃 LRU 链表（active_list）和非活跃 LRU 链表（inactive_list）；
• 预读页就只需要加入到 inactive list 区域的头部，当页被真正访问的时候，才将页插入 active list 的头部。

• MySQL 的 Innodb 存储引擎是在一个 LRU 链表上划分来 2 个区域：young 区域 和 old 区域。
• 预读的页就只需要加入到 old 区域的头部，当页被真正访问的时候，才将页插入 young 区域的头部。
• 两个区域的分界点位置，一般叫做midpoint。在默认配置下，该位置在LRU列表长度的5／8处。由参数innodb_old_blocks_pct控制

解决缓存污染

Linux 操作系统：在内存页被访问第二次的时候，才将页从 inactive list 升级到 active list 里。
MySQL Innodb：在内存页被访问第二次的时候，并不会马上将该页从 old 区域升级到 young 区域，因为还要进行停留在 old 区域的时间判断

如果第二次的访问时间与第一次访问的时间在 1 秒内（默认值），那么该页就不会被从 old 区域升级到 young 区域；
如果第二次的访问时间与第一次访问的时间超过 1 秒，那么该页就会从 old 区域升级到 young 区域；

深入Linux内存

32位系统，用户态空间划分为3g大小：

/arch/x86/include/asm/page_32_types.h        PAGE_OFFSET

进程在内核中的描述符task_struct 结构

struct task_struct {
        // 进程id
	    pid_t				pid;
        // 用于标识线程所属的进程 pid
	    pid_t				tgid;
        // 进程打开的文件信息
        struct files_struct		*files;
        // 内存描述符表示进程虚拟地址空间
        struct mm_struct		*mm;

        .......... 省略 .......
}

在进程描述符 task_struct 结构中，有一个专门描述进程虚拟地址空间的内存描述符 mm_struct 结构，这个结构体中包含了进程虚拟内存空间的全部信息。

当我们调用 fork() 函数创建进程的时候，表示进程地址空间的 mm_struct 结构会随着进程描述符 task_struct 的创建而创建

long do_fork(unsigned long clone_flags,
	      unsigned long stack_start,
	      unsigned long stack_size,
	      int __user *parent_tidptr,
	      int __user *child_tidptr)


static struct task_struct *copy_process(unsigned long clone_flags,
					unsigned long stack_start,
					unsigned long stack_size,
					int __user *child_tidptr,
					struct pid *pid,
					int trace)
					


static int copy_mm(unsigned long clone_flags, struct task_struct *tsk)

通过 fork() 函数创建出的子进程，它的虚拟内存空间以及相关页表相当于父进程虚拟内存空间的一份拷贝，直接从父进程中拷贝到子进程中。
通过 vfork() 函数创建出的子进程，首先会设置 CLONE_VM 标识，这样来到 copy_mm 函数中就会进入 if (clone_flags & CLONE_VM) 条件中，在这个分支中会将父进程的虚拟内存空间以及相关页表直接赋值给子进程。这样一来父进程和子进程的虚拟内存空间就变成共享的了。也就是说父子进程之间使用的虚拟内存空间是一样的，并不是一份拷贝。
vfork() ：进程->线程，Linux 内核并不区别对待

内核的内存管理方式

点击此处跳转到：Linux内核的内存管理方式（段页式存储）
Linux作为一个通用的操作系统，需要兼容各种硬件体系，包括不同位数的CPU。对64位的CPU来说，两级页表仍然太少，一个页表会太大，这会占用太多宝贵的物理内存。Linux采用了通用的四级页表。实际采用几级页表则具体受硬件的限制。

四种页表分别称为： 页全局目录（pgd_t）、页上级目录（pud_t）、页中间目录（pmd_t）、页表（pte_t）。
对于32位x86系统，两级页表已经足够了。Linux通过使“页上级目录”位和“页中间目录”位全为0，彻底取消了页上级目录和页中间目录字段。不过，页上级目录和页中间目录在指针序列中的位置被保留，以便同样的代码在32位系统和64位系统下都能使用。

分段可以给每一个进程分配不同的线性地址空间，而分页可以把同一线性地址空间映射到不同的物理空间。

与分段相比，Linux更喜欢使用分页方式，因为：

1. 当所有进程使用相同的段寄存器时，内存管理变得更简单，也就是说它们能共享同样的一组线性地址；
2. Linux设计目标之一是可以把它移植到绝大多数流行的处理器平台上，然而，RISC体系结构对分段的支持很有限。

运行在用户态的所有Linux进程都使用一对相同的段来对指令和数据寻址，这一对段就是所谓的用户代码段和用户数据段。

线性地址段：PGDIR_SHIFT、PUD_SHIFT、PMD_SHIFT、PAGE_SHIFT等。
页表处理：pgd_t、pud_t、pmd_t、pte_t。

内核如何布局进程虚拟内存空间

在mm_struct中，定义了各个数据域的长度

内核如何管理虚拟内存区域

新的结构体 vm_area_struct，正是这个结构体描述了这些虚拟内存区域

include/linux/mm.h：

vm_flags	访问权限
VM_READ	可读
VM_WRITE	可写
VM_EXEC	可执行
VM_SHARD	可多进程之间共享
VM_IO	可映射至设备 IO 空间
VM_RESERVED	内存区域不可被换出
VM_SEQ_READ	内存区域可能被顺序访问
VM_RAND_READ	内存区域可能被随机访问

虚拟内存区域在内核中是如何被组织的

在进程虚拟内存空间中包含的内存区域 VMA 比较多的情况下，使用红黑树查找特定虚拟内存区域的时间复杂度是 O( logN ) ，可以显著减少查找所需的时间。
所以在内核中，同样的内存区域 vm_area_struct 会有两种组织形式，一种是双向链表用于高效的遍历，另一种就是红黑树用于高效的查找，每个 VMA 区域都是红黑树中的一个节点，通过 struct vm_area_struct 结构中的 vm_rb 将自己连接到红黑树中。

总结：mm_struct中的mmap为vm_area_struct类型，指向了每个域的开始和结束，并且同时以双向链表和红黑树存在，而mm_struct定义的start和end，标示了每个域的结束位置

进程调度

Linux的进程

0号进程

0号进程称为 idle 进程，其 pid 等于0。

每个进程都有struct task_struct。idle进程对应的PCB是 struct task_struct init_task。
idle进程是唯一一个没有通过fork或者kernel_thread产生的进程，因为 init_task 是静态变量（初始化了的全局变量），其他进程的PCB都是fork或者kernel_thread动态申请内存创建的。
每个进程都有对应的一个函数，idle进程的函数是 start_kernel()，start_kernel() 最后会调用 cpu_startup_entry() ，其内部是 while(1) {}

asmlinkage __visible void __init start_kernel(void)

1号进程

1号进程称为 init 进程，其 pid 等于1。

1号进程是0号进程通过调用 kernel_thread() 创建的，在运行 schedule_preempt_disabled() 内的 schedule() 后，就启动调度器进行进程切换，kernel_init() 也就得以运行。

kernel_thread(kernel_init, NULL, CLONE_FS);

kernel_init() 最后会启动用户态的处于根文件系统存储的 init 进程，从而实现 init 内核态到 init 用户态的转化。
init进程完成系统的初始化，是系统中所有其它用户进程的祖先进程。

2号进程

2号进程称为 kthreadd 进程，其 pid 等于2。
kthreadd进程由idle进程通过kernel_thread创建，并始终运行在内核空间, 负责所有内核线程的创建。

kthreadd利用for(;;)一直驻留在内存中运行：主要过程如下：
检查kthread_create_list为空时，kthreadd让出cpu的执行权
kthread_create_list不为空时，利用while循环遍历kthread_create_list链表
每取下一个链表节点后调用create_kthread，创建内核线程

kernel_thread()函数是通过调用do_fork()函数创建的线程，而do_fork()则是在应用层fork(), vfork()和clone()函数的系统调用；此外还需要在其执行函数里调用daemonize()进行资源的释放；该线程挂接在init进程下。
kthread_create()函数是通过工作队列workqueue创建的线程，此线程挂在kthreadd线程下。
kthread_run()函数本质上是调用了kthread_create()和wake_up_process(), 就是除了挂在工作队列上后，便唤醒进行工作。
kthread_create()是比较推崇的创建内核线程的方式。

写时复制

在Linux程序中，fork()会产生一个和父进程完全相同的子进程，但子进程在此后多会exec系统调用，出于效率考虑，linux中引入了“写时复制“技术，也就是只有进程空间的各段的内容要发生变化时，才会将父进程的内容复制一份给子进程
该技术是依赖硬件MMU的，没有MMU，就不支持 fork，只支持vfork。

#ifdef __ARCH_WANT_SYS_FORK
SYSCALL_DEFINE0(fork)
{
#ifdef CONFIG_MMU
	return do_fork(SIGCHLD, 0, 0, NULL, NULL);
#else
	/* can not support in nommu mode */
	return -EINVAL;                    //返回这个错误码需要被上层捕捉
#endif
}
#endif

#ifdef __ARCH_WANT_SYS_VFORK
SYSCALL_DEFINE0(vfork)
{
	return do_fork(CLONE_VFORK | CLONE_VM | SIGCHLD, 0,
			0, NULL, NULL);
}

//写时复制COW体现在这个函数中: copy_mm->dup_mm->dup_mmap->.......->copy_one_pte
static inline unsigned long
copy_one_pte(struct mm_struct *dst_mm, struct mm_struct *src_mm,
		pte_t *dst_pte, pte_t *src_pte, struct vm_area_struct *vma,
		unsigned long addr, int *rss)

• fork 函数之后，如果想要把子进程换成一个想要执行的进程，这时，就不得不使用 exec()函数了，这也是 fork()的意义所在。
• 常见的 fork()调用例子有很多，都是在利用exec系统调用将新产生的子进程完全替换成目标进程。

exec函数(#include )：
装载一个新的程序（可执行映像）覆盖当前进程内存空间中的映像，从而执行不同的任务。exec系列函数在执行时会直接替换掉当前进程的地址空间。

int execl(const char *path, const char *arg,.../* (char*)NULL*/);
int execlp(const char *file, const char *arg,.../* (char*)NULL*/);
int execle(const char *path, const char *arg,.../* (char*)NULL, char *const envp[]*/);
int execv(const char *path, char *const argv[]);
int execvp(const char *file, char *const argv[]);
int execvpe(const char *file, char *const argv[], char *const envp[]);
int execve(const char *path, char *const argv[], char *const envp[]);

• 在fork之后exec之前两个进程用的是相同的物理空间（内存区），子进程的代码段、数据段、堆栈都是指向父进程的物理空间，也就是说，两者的虚拟空间不同，但其对应的物理空间是同一个。当父子进程中有更改相应段的行为发生时，再为子进程相应的段分配物理空间
• 如果是因为exec，由于两者执行的代码不同，子进程的代码段也会分配单独的物理空间。
• 如果不是因为exec，内核会给子进程的数据段、堆栈段分配相应的物理空间（至此两者有各自的进程空间，互不影响），而代码段继续共享父进程的物理空间（两者的代码完全相同）。

写时复制的应用

1. 虚拟内存管理中的写时复制
   一般把这种被共享访问的页面标记为只读。当一个task试图向内存中写入数据时，内存管理单元（MMU）抛出一个异常，内核处理该异常时为该task分配一份物理内存并复制数据到此内存，重新向MMU发出执行该task的写操作。

2. Linux的文件管理系统使用了写时复制策略。

3. [数据库]服务器也一般采用了写时复制策略，为用户提供一份snapshot。

4. 软件应用中的写时复制
   [C++标准程序库]中的[std::string]类，在C++98/C++03标准中是允许写时复制策略。但在[C++11]标准中为了提高并行性取消了这一策略。 GCC从版本5开始，std::string不再采用COW策略。

孤儿进程与僵尸进程

孤儿进程：一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作，所以孤儿进程并不会有什么危害。

僵尸进程：一个进程使用fork创建子进程，如果子进程退出，而父进程并没有调用wait或waitpid获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中。这种进程称之为僵死进程。

• 父进程只管生成新的子进程，对子进程退出之后的事情，则一概不闻不问，系统运行一段时间后，系统中就会存在很多的僵死进程，用ps命令查看的话，就会看到很多状态为Z的进程。
• 僵死进程并不是问题的根源，罪魁祸首是产生出大量僵死进程的父进程。答案就是把产生大量僵死进程的那个元凶枪毙掉（通过kill发送SIGTERM或者SIGKILL信号）
• 枪毙了元凶进程之后，它产生的僵死进程就变成了孤儿进程，这些孤儿进程会被init进程接管，init进程会wait()这些孤儿进程，释放它们占用的系统进程表中的资源。

  守护进程

  守护进程（daemon）是后台运行的、系统启动是就存在的、不与任何终端关联的，用于处理一些系统级别任务的特殊进程。

创建守护进程

1. fork()创建子进程，父进程exit()退出；

• 由于守护进程是脱离控制终端的，完成这一步后就会在Shell终端里造成程序已经运行完毕的假象。之后的所有工作都在子进程中完成，而用户在Shell终端里则可以执行其他命令，从而在形式上做到了与控制终端的脱离，在后台工作。
• 由于父进程先于子进程退出，子进程就变为孤儿进程，并由 init 进程作为其父进程收养。

1. 在子进程调用setsid()创建新会话；
   在调用了 fork() 函数后，子进程全盘拷贝了父进程的会话期、进程组、控制终端等，虽然父进程退出了，但会话期、进程组、控制终端等并没有改变。这还不是真正意义上的独立开来，而 setsid() 函数能够使进程完全独立出来，摆脱其他进程的控制。

setsid()创建一个新会话，调用进程担任新会话的首进程，其作用有：

• 使当前进程脱离原会话的控制
• 使当前进程脱离原进程组的控制
• 使当前进程脱离原控制终端的控制

1. 在子进程中调用chdir()改变当前目录为根目录；
   使用fork创建的子进程继承了父进程的当前工作目录。由于守护进程在后台运行，开始于系统开启，终止于系统关闭，所以要将其目录改为系统的根目录下。进程在执行时，其文件系统不能被卸下。

2. 在子进程中调用umask()重设文件权限掩码为0；

• 文件权限掩码是指屏蔽掉文件权限中的对应位。比如，有个文件权限掩码是050，它就屏蔽了文件组拥有者的可读与可执行权限
• 由于使用fork函数新建的子进程继承了父进程的文件权限掩码，这就给该子进程使用文件带来了诸多的麻烦。因此把文件权限掩码重设为0即清除掩码（权限为777），这样可以大大增强该守护进程的灵活性。通常的使用方法为umask(0)。

1. 在子进程中close()不需要的文件描述符；

• 子进程从父进程那里继承了打开文件描述符。这些被打开的文件可能永远不会被守护进程读写，但它们一样消耗系统资源，而且可能导致所在的文件系统无法卸下。
• 在第二步之后，守护进程已经与控制终端失去了联系，终端输入的字符不可能达到守护进程，守护进程中用常规方法输出的字符也不可能在终端显示出来。所以，文件描述符为0、1和2 的3个文件（输入、输出和报错）已经失去了存在的价值，也应被关闭。

1. 守护进程退出处理
   当用户需要外部停止守护进程运行时，往往会使用 kill 命令停止该守护进程。守护进程中需要编码来实现 kill 发出的signal信号处理，达到进程的正常退出。

进程和线程

进程：

程序段： 存放程序代码；
数据段： 存放程序运行时使用、产生的运算数据，如全局变量、局部变量、宏定义的常量；
PCB（task_struct）： 存放操作系统对程序进行管理所需的各种信息，如进程描述信息、进程控制和管理信息、资源分配清单、处理机相关信息。

进程的组成

详细信息如下图：

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

并行和并发

虽然单核的 CPU 在某一个瞬间，只能运行一个进程。但在 1 秒钟期间，它可能会运行多个进程，这样就产生并行的错觉，实际上这是并发。

进程的状态

• 创建状态（new）：进程正在被创建时的状态；
• 结束状态（Exit）：进程正在从系统中消失时的状态；
• 运行状态（Running）：该时刻进程占用 CPU；
• 就绪状态（Ready）：可运行，由于其他进程处于运行状态而暂时停止运行；
• 阻塞状态（Blocked）：该进程正在等待某一事件发生（如等待输入/输出操作的完成）而暂时停止运行，这时，即使给它CPU控制权，它也无法运行；

线程：

线程是进程当中的一条执行流程**

• 同⼀个进程内多个线程之间可以共享代码段、数据段、打开的⽂件等资源，
• 但每个线程各自都有⼀套独⽴的寄存器和栈，这样可以确保线程的控制流是相对独⽴的

线程共享的环境

包括：进程代码段、进程的公有数据(利用这些共享的数据，线程很容易的实现相互之间的通讯)、进程打开的文件描述符、信号的处理器、进程的当前目录和进程用户ID与进程组ID。

线程的优点

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

线程的缺点

当进程中的一个线程崩溃时，会导致其所属进程的所有线程崩溃（这里是针对 C/C++ 语言，Java语言中的线程奔溃不会造成进程崩溃）。
举个例子，对于游戏的用户设计，则不应该使用多线程的方式，否则一个用户挂了，会影响其他同个进程的线程。

线程上下文切换

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

三种线程的实现⽅式

• ⽤户线程（User Thread）：在⽤户空间实现的线程，不是由内核管理的线程，是由⽤户态的线程库来完成线程的管理；
• 内核线程（Kernel Thread）：在内核中实现的线程，是由内核管理的线程；
• 轻量级进程（LightWeight Process）：在内核中来⽀持⽤户线程；

用户线程

用户线程的整个线程管理和调度，操作系统是不直接参与的，⽽是由⽤户级线程库函数来完成线程的管理，包括线程的创建、终⽌、同步和调度等。

⽤户线程的优点：

• 每个进程都需要有它私有的线程控制块（TCB）列表，⽤来跟踪记录它各个线程状态信息（PC、栈指针、寄存器），TCB 由⽤户级线程库函数来维护，可⽤于不⽀持线程技术的操作系统
• ⽤户线程的切换也是由线程库函数来完成的，⽆需⽤户态与内核态的切换，所以速度特别快；

⽤户线程的缺点：

• 由于操作系统不参与线程的调度，如果⼀个线程发起了系统调⽤⽽阻塞，那进程所包含的⽤户线程都不能执⾏了。
• 当⼀个线程开始运⾏后，除⾮它主动地交出 CPU 的使⽤权，否则它所在的进程当中的其他线程⽆法运⾏，因为⽤户态的线程没法打断当前运⾏中的线程，它没有这个特权，只有操作系统才有，但是⽤户线程不是由操作系统管理的。
• 由于时间⽚分配给进程，故与其他进程⽐，在多线程执⾏时，每个线程得到的时间⽚较少，执⾏会⽐较慢；

内核线程

内核线程是由操作系统管理的，线程对应的 TCB ⾃然是放在操作系统⾥的，这样线程的创建、终⽌和管理都是由操作系统负责。

内核线程的优点：

• 在⼀个进程当中，如果某个内核线程发起系统调⽤⽽被阻塞，并不会影响其他内核线程的运⾏；
• 分配给线程，多线程的进程获得更多的 CPU 运⾏时间；

内核线程的缺点：

• 在⽀持内核线程的操作系统中，由内核来维护进程和线程的上下⽂信息，如 PCB 和TCB；
• 线程的创建、终⽌和切换都是通过系统调⽤的⽅式来进⾏，因此对于系统来说，系统开销⽐较⼤；

轻量级进程

• 轻量级进程（LWP）是内核支持的用户线程，一个进程可有一个或多个 LWP，每个 LWP 是跟内核线程一对一映射的，也就是 LWP 都是由一个内核线程支持，而且 LWP 是由内核管理并像普通进程一样被调度。
• 轻量级进程通常共享相同的地址空间，但具有独立的堆栈和寄存器状态，从而实现了类似进程的隔离和并发执行。
• LWP与普通进程的区别也在于它只有一个最小的执行上下文和调度程序所需的统计信息
• 轻量级进程具有局限性。首先，大多数LWP的操作，如建立、析构以及同步，都需要进行系统调用，即在用户态和内核态进行切换。其次，每个LWP都需要有一个内核线程支持，因此LWP要消耗内核资源（内核线程的栈空间），所以一个系统不能支持大量的LWP。

线程与进程的⽐较

1. 进程是资源（包括内存、打开的⽂件等）分配的单位，线程是 CPU 调度的单位；
2. 进程拥有⼀个完整的资源平台，⽽线程只独享必不可少的资源，如寄存器和栈；
3. 线程同样具有就绪、阻塞、执⾏三种基本状态，同样具有状态之间的转换关系；
4. 线程能减少并发执⾏的时间和空间开销；

线程相⽐进程能减少开销

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

多线程和多进程的比较

1. 需要频繁创建销毁的优先用线程。
   实例：web服务器。来一个建立一个线程，断了就销毁线程。要是用进程，创建和销毁的代价是很难承受的。
2. 需要进行大量计算的优先使用线程。
   所谓大量计算，当然就是要消耗很多cpu，切换频繁了，这种情况先线程是最合适的。实例：图像处理、算法处理
3. 强相关的处理用线程，若相关的处理用进程。
   一般的server需要完成如下任务：消息收发和消息处理。消息收发和消息处理就是弱相关的任务，而消息处理里面可能又分为消息解码、业务处理，这两个任务相对来说相关性就要强多了。因此消息收发和消息处理可以分进程设计，消息解码和业务处理可以分线程设计。
4. 可能扩展到多机分布的用进程，多核分布的用线程。

协程

协程可以理解为用户态的轻量级的非抢占式的线程。可以在程序的某个点挂起，并在稍后恢复执行

原理：

• 我们知道操作系统在线程等待IO的时候，会阻塞当前线程，切换到其它线程，这样在当前线程等待IO的过程中，其它线程可以继续执行。
• 当线程数量非常多的时候，却产生了问题。一是系统线程会占用非常多的内存空间，二是过多的线程切换会占用大量的系统时间。
• 协程运行在线程之上，当一个协程执行完成后，可以选择主动让出，让另一个协程运行在当前线程之上。协程并没有增加线程数量，只是在线程的基础之上通过分时复用的方式运行多个协程，

特点：
用户态:协程是在用户态实现调度。
轻量级:协程不用内核调度，不被被操作系统内核所管理，不需要内核态与用户态之间切换。
非抢占:协程是由用户自己实现调度，并且同一时间只能有一个协程在执行，协程自己主动交出CPU的。

优点：
协程切换的时候开销小，用户态且轻量
非抢占式，不用加很多锁，减小复杂度，不用很复杂的处理线程同步问题。

缺点：
协程可以在单线程内处理高并发,但是协程不能同时使用单个CPU的多个核心，不能利用多核，只能使用单核。
假设协程运行在线程之上，并且协程调用了一个阻塞IO操作，操作系统会让线程进入阻塞状态，当前的协程和其它绑定在该线程之上的协程都会陷入阻塞而得不到调度，这往往是不能接受的。因此，协程只有和异步IO结合起来才能发挥出最大的威力。

进程的通信

管道

所谓的管道，就是内核里面的一串缓存，所谓的管道，就是内核里面的一串缓存

无名管道

int pipe(int fd[2]);

fd[0]为读而打开，fd[1]为写而打开

使用 fork 创建子进程，创建的子进程会复制父进程的文件描述符，但是管道只能一端写入，另一端读出，所以这种模式容易造成混乱，需要：
父进程关闭读取的 fd[0]，只保留写入的 fd[1]；
子进程关闭写入的 fd[1]，只保留读取的 fd[0]；

关闭后变为->

执行A | B发生了什么
A进程和 B 进程都是 shell 创建出来的子进程，A 和 B 之间不存在父子关系，它俩的父进程都是 shell。

命名管道

也被叫做 FIFO ，因为数据是先进先出的传输⽅式。在使⽤命名管道前，先需要通过 mkfifo 命令来创建，并且指定管道名字：

$ mkfifo myPipe

myPipe 就是这个管道的名称，基于 Linux ⼀切皆⽂件的理念，所以管道也是以⽂件的⽅式存在，我们可以⽤ ls 看⼀下，这个⽂件的类型是 p，也就是 pipe（管道） 的意思：

$ ls -l
prw-r--r--. 1 root root 0 Jul 17 02:45 myPipe

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

• 对于匿名管道，它的通信范围是存在⽗⼦关系的进程。因为管道没有实体，也就是没有管道⽂件，只能通过 fork 来复制⽗进程 fd ⽂件描述符，来达到通信的⽬的。
• 对于命名管道，它可以在不相关的进程间也能相互通信。因为命令管道，提前创建了⼀个类型为管道的设备⽂件，在进程⾥只要使⽤这个设备⽂件，就可以相互通信。

消息队列

msgget();

消息队列是保存在内核中的消息链表，消息队列不适合⽐较⼤数据的传输，
消息队列通信过程中，存在⽤户态与内核态之间的数据拷⻉开销，因为进程写⼊数据到内核中的消息队列时，会发⽣从⽤户态拷⻉数据到内核态的过程，同理另⼀进程读取内核中的消息数据时，会发⽣从内核态拷⻉数据到⽤户态的过程。

共享内存

shmget();

多个进程将同一个文件（内存的匿名段）映射到它们的地址空间
共享内存的机制，就是拿出⼀块虚拟地址空间来，映射到相同的物理内存中。

存储映射I/O（mmap）

mmap将一个文件或者其它对象映射进内存上
mmap操作提供了一种机制，让用户程序直接访问设备内存，这种机制，相比较在用户空间和内核空间互相拷贝数据，效率更高。在要求高性能的应用中比较常用。mmap映射内存必须是页面大小的整数倍，面向流的设备不能进行mmap，mmap的实现和硬件有关。

#include <sys/mman.h>
void *mmap(void *addr,size_t len,int prot,int flags,int fd,off_t off);

• 两个进程中通信
  两个程序映射同一个文件到自己的地址空间, 进程A先运行, 每隔两秒读取映射区域, 看是否发生变化. 进程B后运行, 它修改映射区域, 然后推出, 此时进程A能够观察到存储映射区的变化。

#include <sys/mman.h>  

#define BUF_SIZE 100  
  
int main(int argc, char **argv)  
{  
    int fd, nread, i;  
    struct stat sb;  
    char *mapped, buf[BUF_SIZE];  
  
    for (i = 0; i < BUF_SIZE; i++) {  
        buf[i] = '#';  
    }  
  
    /* 打开文件 */  
    if ((fd = open(argv[1], O_RDWR)) < 0) {  
        perror("open");  
    }  
  
    /* 获取文件的属性 */  
    if ((fstat(fd, &sb)) == -1) {  
        perror("fstat");  
    }  
  
    /* 将文件映射至进程的地址空间 */  
    if ((mapped = (char *)mmap(NULL, sb.st_size, PROT_READ |   
                    PROT_WRITE, MAP_SHARED, fd, 0)) == (void *)-1) {  
        perror("mmap");  
    }  
  
    /* 文件已在内存, 关闭文件也可以操纵内存 */  
    close(fd);  
      

    /* 进程A：每隔两秒查看存储映射区是否被修改 */  
    while (1) {  
        printf("%s\n", mapped);  
        sleep(2);  
    }

    /* 进程B：修改一个字符 */  
    mapped[20] = '9';  
  
    return 0;  
} 

信号量

semget();

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

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

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

• 信号初始化为 1 ，就代表着是互斥信号量，它可以保证共享内存在任何时刻只有⼀个进程在访问，这就很好的保护了共享内存
  进程 A 在访问共享内存前，先执⾏了 P 操作，由于信号量的初始值为 1，故在进程 A 执 ⾏ P 操作后信号量变为 0，表示共享资源可⽤，于是进程 A 就可以访问共享内存。
  若此时，进程 B 也想访问共享内存，执⾏了 P 操作，结果信号量变为了 -1，这就意味着临界资源已被占⽤，因此进程 B 被阻塞。
  直到进程 A 访问完共享内存，才会执⾏ V 操作，使得信号量恢复为 0，接着就会唤醒阻塞中的线程 B，使得进程 B 可以访问共享内存，最后完成共享内存的访问后，执⾏ V 操作，使信号量恢复到初始值 1。

• 信号初始化为 0 ，就代表着是同步信号量，它可以保证进程 A 应在进程 B 之前执⾏。
  如果进程 B ⽐进程 A 先执⾏了，那么执⾏到 P 操作时，由于信号量初始值为 0，故信号量会变为 -1，表示进程 A 还没⽣产数据，于是进程 B 就阻塞等待；
  接着，当进程 A ⽣产完数据后，执⾏了 V 操作，就会使得信号量变为 0，于是就会唤醒阻塞在 P 操作的进程 B；
  最后，进程 B 被唤醒后，意味着进程 A 已经⽣产了数据，于是进程 B 就可以正常读取数据了。

信号

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

$ kill -l
 1) SIGHUP 2) SIGINT 3) SIGQUIT 4) SIGILL 5)SIGTRAP
 6) SIGABRT 7) SIGBUS 8) SIGFPE 9) SIGKILL 10)SIGUSR1
11) SIGSEGV 12) SIGUSR2 13) SIGPIPE 14) SIGALRM 15)SIGTERM
16) SIGSTKFLT 17) SIGCHLD 18) SIGCONT 19) SIGSTOP 20)SIGTSTP
21) SIGTTIN 22) SIGTTOU 23) SIGURG 24) SIGXCPU 25)SIGXFSZ
26) SIGVTALRM 27) SIGPROF 28) SIGWINCH 29) SIGIO 30)SIGPWR
31) SIGSYS 34) SIGRTMIN 35) SIGRTMIN+1 36) SIGRTMIN+2 37)SIGRTMIN+3
38) SIGRTMIN+4 39) SIGRTMIN+5 40) SIGRTMIN+6 41) SIGRTMIN+7 42)SIGRTMIN+8
43) SIGRTMIN+9 44) SIGRTMIN+10 45) SIGRTMIN+11 46) SIGRTMIN+12 47)SIGRTMIN+13
48) SIGRTMIN+14 49) SIGRTMIN+15 50) SIGRTMAX-14 51) SIGRTMAX-13 52)SIGRTMAX-12
53) SIGRTMAX-11 54) SIGRTMAX-10 55) SIGRTMAX-9 56) SIGRTMAX-8 57)SIGRTMAX-7
58) SIGRTMAX-6 59) SIGRTMAX-5 60) SIGRTMAX-4 61) SIGRTMAX-3 62)SIGRTMAX-2

Ctrl+C 产⽣ SIGINT（2） （可被忽略）信号，表示终⽌该进程；
Ctrl+Z 产⽣ SIGTSTOP（19） 信号，表示挂起该进程，但还未结束；

唯⼀的异步通信机制。进程有三种⽅式响应信号 1. 执⾏默认操作、2. 捕捉信号、3. 忽略信号。有两个信号是应⽤进程⽆法捕捉和忽略的，即SIGKILL（9） 和 SEGSTOP（19） ，这是为了⽅便我们能在任何时候结束或停⽌某个进程

Socket

TCP网络编程

• 服务端和客户端初始化 socket ，得到⽂件描述符；
• 服务端调⽤ bind ，将绑定在 IP 地址和端⼝;
• 服务端调⽤ listen ，进⾏监听；
• 服务端调⽤ accept ，等待客户端连接；
• 客户端调⽤ connect ，向服务器端的地址和端⼝发起连接请求；
• 服务端 accept 返回⽤于传输的 socket 的⽂件描述符；
• 客户端调⽤ write 写⼊数据；服务端调⽤ read 读取数据；
• 客户端断开连接时，会调⽤ close ，那么服务端 read 读取数据的时候，就会读取到了EOF ，待处理完数据后，服务端调⽤ close ，表示连接关闭

线程的同步与互斥

如果要访问共享资源（内存，变量等），必须考虑互斥，保证一个线程在临界区执行时，其他线程应该被阻止进入

互斥量（互斥锁）

pthreadmutex**
确保同一时间只有一个线程访问数据

读写锁（共享互斥锁）

pthreadrwlock**
一次只有一个线程可以占有写模式的读写锁，多个线程可以同时占有读模式的读写锁

• 写加锁状态时，所有试图对这个锁加锁的线程都会被阻塞
• 读加锁状态时，所有试图以读模式对它加锁的线程都可以得到访问权，所有试图以写模式对它加锁的线程都会阻塞

条件变量

pthreadcond**

• 条件变量与互斥量一起使用时，允许线程以无竞争的方式等待特定的条件发生。
• 条件本身是由互斥量保护的。线程在改变条件状态之前必须首先锁住互斥量。其他线程在获得互斥量之前不会察觉到这种改变，因为互斥量必须在锁定以后才能计算条件。
• 传递给pthread_cond_wait的互斥量对条件变量进行保护。调用者把锁住的互斥量传给函数，函数然后自动把调用线程放到等待条件的线程列表上，对互斥量解锁。

自旋锁

pthreadspin**

• 互斥锁加锁失败后，线程会释放 CPU ，给其他线程；
• ⾃旋锁加锁失败后，线程会忙等待，直到它拿到锁；
• 当加锁失败时，互斥锁⽤「线程切换」来应对，⾃旋锁则⽤「忙等待」来应对
• 在单核CPU 上，需要抢占式的调度器（即不断通过时钟中断⼀个线程，运⾏其他线程）。否则，⾃旋锁在单 CPU 上⽆法使⽤，因为⼀个⾃旋的线程永远不会放弃 CPU。

屏障

pthreadbarrier**
是用户协调多个线程并行工作的同步机制。屏障允许每个线程等待，直到所有的合作线程都达到某一点，然后从该点继续执行。pthread_join函数就是一种屏障，允许一个线程等待，直到另一个线程退出。
但是屏障对象的概念更广，它们允许任意数量的线程等待，直到所有的线程完成处理工作，而线程不需要退出。所有线程达到屏障后可以接着工作。

信号量

P、V 操作，见上文信号量

信号

死锁

死锁的四个条件

互斥条件；互斥条件是指多个线程不能同时使⽤同⼀个资源。
持有并等待条件； 一个进程本身占有资源（一种或多种），同时还有资源未得到满足，等待其他进程释放该资源。
不可剥夺条件；当线程已经持有了资源 ，在⾃⼰使⽤完之前不能被其他线程获取，
环路等待条件；在死锁发⽣的时候，两个线程获取资源的顺序构成了环形链。

死锁预防

确保系统永远不会进入死锁状态
a、破坏“占有且等待”条件

1. 所有的进程在开始运行之前，必须一次性地申请其在整个运行过程中所需要的全部资源。
2. 允许进程只获得运行初期需要的资源，便开始运行，在运行过程中逐步释放掉分配到的已经使用完毕的资源，然后再去请求新的资源。

b、破坏“不可抢占”条件
当一个已经持有了一些资源的进程在提出新的资源请求没有得到满足时，它必须释放已经保持的所有资源，待以后需要使用的时候再重新申请。

c、破坏“循环等待”条件
可以通过定义资源类型的线性顺序来预防，可将每个资源编号，当一个进程占有编号为i的资源时，那么它下一次申请资源只能申请编号大于i的资源。

避免死锁

在分配资源时判断是否会出现死锁，只在不会出现死锁的情况下才分配资源。
两种避免办法：
1、如果一个进程的请求会导致死锁，则不启动该进程
2、如果一个进程的增加资源请求会导致死锁 ，则拒绝该申请。

避免死锁的具体实现通常利用银行家算法
可利用资源向量Available：用于表示系统里边各种资源剩余的数目。
最大需求矩阵Max：用于表示各个进程对各种资源的额最大需求量。
分配矩阵Allocation：就是用于表示已经分配给各个进程的各种资源的数目。也是一个nxm的矩阵。
需求矩阵Need：用于表示进程仍然需要的资源数目，用一个nxm的矩阵表示。

哲学家就餐问题

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

方案二：
用一个数组 state 来记录每一位哲学家的三个状态，分别是在进餐状态、思考状态、饥饿状态（正在试图拿叉子）。那么，一个哲学家只有在两个邻居都没有进餐时，才可以进入进餐状态。第 i 个哲学家的左邻右舍，则由宏 LEFT 和 RIGHT 定义：
LEFT : ( i + 5 - 1 ) % 5
RIGHT : ( i + 1 ) % 5
比如 i 为 2，则 LEFT 为 1，RIGHT 为 3。

悲观锁与乐观锁

1. 悲观锁做事⽐较悲观，它认为多线程同时修改共享资源的概率⽐较⾼，于是很容易出现冲突，所以访问共享资源前，先要上锁。
2. 乐观锁做事⽐较乐观，它假定冲突的概率很低，先修改完共享资源，再验证这段时间内有没有发⽣冲突，如果没有其他线程在修改资源，那么操作完成，如果发现有其他线程已经修改过这个资源，就放弃本次操作。
   应用：在线文档多人编辑

调度算法

调度的原则

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

进程调度算法

先来先服务调度算法

最短作业优先调度算法

高响应比优先调度算法

如果两个进程的「等待时间」相同时，「要求的服务时间」越短，「响应⽐」就越⾼，这样短作业的进程容易被选中运⾏；
如果两个进程「要求的服务时间」相同时，「等待时间」越⻓，「响应⽐」就越⾼，这就兼顾到了⻓作业进程，因为进程的响应⽐可以随时间等待的增加⽽提⾼，当其等待时间⾜够⻓时，其响应⽐便可以升到很⾼，从⽽获得运⾏的机会；

时间⽚轮转调度算法

如果时间⽚设得太短会导致过多的进程上下⽂切换，降低了 CPU 效率；如果设得太⻓⼜可能引起对短作业进程的响应时间变⻓。

最⾼优先级调度算法

静态优先级：创建进程时候，就已经确定了优先级了，然后整个运⾏时间优先级都不会变化；
动态优先级：根据进程的动态变化调整优先级，如果进程运⾏时间增加，则降低其优先级，如果进程等待时间（就绪队列的等待时间）增加，则升⾼其优先级，也就是随着时间的推移增加等待进程的优先级。
⾮抢占式：当就绪队列中出现优先级⾼的进程，运⾏完当前进程，再选择优先级⾼的进程。
抢占式：当就绪队列中出现优先级⾼的进程，当前进程挂起，调度优先级⾼的进程运⾏。
但是依然有缺点，可能会导致低优先级的进程永远不会运⾏。

多级反馈队列调度算法

设置了多个队列，赋予每个队列不同的优先级，每个队列优先级从⾼到低，同时优先级越⾼时间⽚越短；新的进程会被放⼊到第⼀级队列的末尾，按先来先服务的原则排队等待被调度，如果在第⼀级队列规定的时间⽚没运⾏完成，则将其转⼊到第⼆级队列的末尾，以此类推，直⾄完成；
当较⾼优先级的队列为空，才调度较低优先级的队列中的进程运⾏。如果进程运⾏时，有新进程进⼊较⾼优先级的队列，则停⽌当前运⾏的进程并将其移⼊到原队列末尾，接着让较⾼优先级的进程运⾏；

内存页面置换算法

最佳⻚⾯置换算法

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

先进先出置换算法

既然我们⽆法预知⻚⾯在下⼀次访问前所需的等待时间，那我们可以选择在内存驻留时间很⻓的⻚⾯进⾏中置换，这个就是「先进先出置换」算法的思想

最近最久未使⽤的置换算法

最近最久未使⽤（LRU）的置换算法的基本思路是，发⽣缺⻚时，选择最⻓时间没有被访问的⻚⾯进⾏置换，

LRU缓存

像浏览器的缓存策略、memcached的缓存策略都是使用LRU这个算法，LRU算法会将近期最不会访问的数据淘汰掉。

• 新数据插入到链表头部
• 每当缓存命中（即缓存数据被访问），则将数据移到链表头部
• 当链表满的时候，将链表尾部的数据丢弃

LRU Cache具备的操作：
set(key,value)：如果key在hashmap中存在，则先重置对应的value值，然后获取对应的节点cur，将cur节点从链表删除，并移动到链表的头部；若果key在hashmap不存在，则新建一个节点，并将节点放到链表的头部。当Cache存满的时候，将链表最后一个节点删除即可。
get(key)：如果key在hashmap中存在，则把对应的节点放到链表头部，并返回对应的value值；如果不存在，则返回-1。

LRU的c++实现：
LRU实现采用双向链表 + Map 来进行实现。这里采用双向链表的原因是：如果采用普通的单链表，则删除节点的时候需要从表头开始遍历查找，效率为O(n)，采用双向链表可以直接改变节点的前驱的指针指向进行删除达到O(1)的效率。使用Map来保存节点的key、value值便于能在O(logN)的时间查找元素,对应get操作。

双链表节点的定义：

struct CacheNode {
 int key;  // 键
 int value; // 值
 CacheNode *pre, *next; // 节点的前驱、后继指针
 CacheNode(int k, int v) : key(k), value(v), pre(NULL), next(NULL) {}
};

对于LRUCache这个类而言，构造函数需要指定容量大小

LRUCache(int capacity)
{
 size = capacity;  // 容量
 head = NULL;   // 链表头指针
 tail = NULL;   // 链表尾指针
}

双链表的节点删除操作：

void remove(CacheNode *node)
{
 if (node -> pre != NULL)
 {
 node -> pre -> next = node -> next;
 }
 else
 {
 head = node -> next;
 }
 if (node -> next != NULL)
 {
 node -> next -> pre = node -> pre;
 }
 else
 {
 tail = node -> pre;
 }
}

将节点插入到头部的操作：

void setHead(CacheNode *node)
{
 node -> next = head;
 node -> pre = NULL;
 
 if (head != NULL)
 {
 head -> pre = node;
 }
 head = node;
 if (tail == NULL)
 {
 tail = head;
 }
}

get(key)操作的实现比较简单，直接通过判断Map是否含有key值即可，如果查找到key，则返回对应的value，否则返回-1;

int get(int key)
{
 map<int, CacheNode *>::iterator it = mp.find(key);
 if (it != mp.end())
 {
 CacheNode *node = it -> second;
 remove(node);
 setHead(node);
 return node -> value;
 }
 else
 {
 return -1;
 }
}

set(key, value)操作需要分情况判断。如果当前的key值对应的节点已经存在，则将这个节点取出来，并且删除节点所处的原有的位置，并在头部插入该节点；如果节点不存在节点中，这个时候需要在链表的头部插入新节点，插入新节点可能导致容量溢出，如果出现溢出的情况，则需要删除链表尾部的节点。

void set(int key, int value)
{
 map<int, CacheNode *>::iterator it = mp.find(key);
 if (it != mp.end())
 {
 CacheNode *node = it -> second;
 node -> value = value;
 remove(node);
 setHead(node);
 }
 else
 {
 CacheNode *newNode = new CacheNode(key, value);
 if (mp.size() >= size)
 {
  map<int, CacheNode *>::iterator iter = mp.find(tail -> key);
  remove(tail);
  mp.erase(iter);
 }
 setHead(newNode);
 mp[key] = newNode;
 }
}

时钟⻚⾯置换算法

最不常⽤算法

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

磁盘调度算法

先来先服务算法

最短寻道时间优先算法

根据距离磁头最近的请求的算法

扫描算法（电梯算法）

磁头在⼀个⽅向上移动，访问所有未完成的请求，直到磁头到达该⽅向上的最后的磁道，才调换⽅向，这就是扫描（Scan）算法。

循环扫描算法

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

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

文件系统

一切皆文件

Linux的文件类型

1. 普通文件
   普通文件根据存放的内容的不同，又分为如下两种：

• 文本文件
  存放的都是文字编码，文本编辑器打开后，会将这些文字编码翻译为文字图形，以供人识别。
• 纯二进制文件（机器码）
  1. 比如经过编译后得到的可执行文件，里面放的是cpu执行的纯二进制机器码，由于文编编辑器只认识文字编码，所以用文本编辑器打开后，显示的内容无法是错乱的，无法辨识。命令cat就是一个二进制文件
  2. 其实不管存放的是文字编码，还是机器码，在计算机中存储时，其实都是以二进制形式存放的，只不过我们这里可刻意的把机器码这类非文字编码的数据，特意强调为了二进制数据。
  3. 对linux内核而言，这两种文件并无区别，至于文件中的数据如何解释，则由处理这些数据的应用程序（比如文本编辑器）来决定。
  4. 不管是文字编码数据，还是纯二进制数据，应用程序调用read、write读写文件时，没有任何区别。

1. 目录文件
   目录是一种特殊的文件，专门用于管理其它文件。第一个属性为 [d]，例如 [drwxrwxrwx]。
2. 字符设备文件
   字符设备文件，就是字符设备驱动程序，在上层的表现形式。
   当应用程序调用底层字符设备驱动程序，实现对某个字符设备进行读写时，上层就需要对接底层的字符驱动程序，字符设备驱动在上层，会以“字符设备文件”的形式表现出来，我们通过open、read、write去读写字符设备文件，就实现了和底层字符设备驱动程序的交互。
3. 块设备文件
   对应块设备（如磁盘等）。
   块设备文件，是块设备驱动程序在上层的表现形式。

• 字符设备与块设备有什么区别？
  1. 字符设备
     以字节为单位来操作数据。比如：键盘、鼠标、显示器都等是字符设备。
     1. 块设备
        块设备存储的数据量往往非常大，为了提高读写效率，都是以块（1024字节）为单位来操作数据。比如：电脑硬盘、移动硬盘、u盘等，凡是涉及大量数据存储的，都是以块为单位来操作数据的，都是块设备。

1. FIFO（fifo：p）
   管道文件，用于实现不同进程（程序）之间的通信，管道是OS提供的一种纯代码层面的通信机制。
   A进程 ————————> 管道文件 ————————>B进程
2. 套接字文件（socket：s）
   专门用于网络通信的文件。

文件的管理

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

磁盘读写的最小单位是扇区，扇区的大小只有 512B 大小，Linux 读写逻辑块，逻辑块大小为 4KB，也就是一次性读写 8 个扇区。

磁盘进行格式化的时候，会被分成三个存储区域，分别是超级块、索引节点区和数据块区。

• 超级块：用来存储文件系统的详细信息，比如块个数、块大小、空闲块等等。当文件系统挂载时进入内存。
• 索引节点区：用来存储索引节点；当文件被访问时进入内存
• 数据块区：用来存储文件或目录数据；

文件的存放方式

连续空间存放方式

缺陷：「磁盘空间碎片」和「文件长度不易扩展」

非连续空间存放方式：

链表方式

隐式链表

实现的方式是文件头要包含「第一块」和「最后一块」的位置，并且每个数据块里面留出一个指针空间，用来存放下一个数据块的位置，

缺点在于无法直接访问数据块，只能通过指针顺序访问文件，以及数据块指针消耗了一定的存储空间。隐式链接分配的稳定性较差，系统在运行过程中由于软件或者硬件错误导致链表中的指针丢失或损坏，会导致文件数据的丢失

显式链接

它指把用于链接文件各数据块的指针，显式地存放在内存的一张链接表中，该表在整个磁盘仅设置一张，每个表项中存放链接指针，指向下一个数据块号。
缺点是不适用于大磁盘

索引方式

单索引

链表+索引

多级索引块

Unix和Linux Ext 2/3

空闲空间管理

空闲表法

适用于建立连续文件

空闲链表法

位图法

在 Linux 文件系统就采用了位图的方式来管理空闲空间，不仅用于数据空闲块的管理，还用于 inode 空闲块的管理，

「位图 + 数据」
每位表示一个数据块，共可以表示 4 1024 8 = 2^15 个空闲块，由于 1 个数据块是 4K 大小，那么最大可以表示的空间为 2^15 4 1024 = 2^27 个 byte，也就是 128M。表示的大小过少，Linux使用块组结构

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

超级块和块组描述符表，这两个都是全局信息，而且非常的重要，这么做是有两个原因：
如果系统崩溃破坏了超级块或块组描述符，有关文件系统结构和内容的所有信息都会丢失。如果有冗余的副本，该信息是可能恢复的。
通过使文件和管理数据尽可能接近，减少了磁头寻道和旋转，这可以提高文件系统的性能。

目录的管理

目录文件的块里面保存的是目录里面一项一项的文件信息。

软链接(ln -s)和硬链接(ln -d）

硬链接

多个目录项中的「索引节点」指向一个文件，也就是指向同一个 inode。每个文件系统都有各自的 inode 数据结构和列表，所以硬链接是不可用于跨文件系统的。由于多个目录项都是指向一个 inode，那么只有删除文件的所有硬链接以及源文件时，系统才会彻底删除该文件。

软链接

相当于重新创建一个文件，这个文件有独立的 inode，但是这个文件的内容是另外一个文件的路径，所以访问软链接的时候，实际上相当于访问到了另外一个文件，所以软链接是可以跨文件系统的，甚至目标文件被删除了，链接文件还是在的，只不过指向的文件找不到了而已。

文件I/O

缓冲与非缓冲 I/O

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

• 缓冲 I/O，利用的是标准库的缓存实现文件的加速访问，而标准库再通过系统调用访问文件。
• 非缓冲 I/O，直接通过系统调用访问文件，不经过标准库缓存。
  这里所说的「缓冲」特指标准库内部实现的缓冲。

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

直接与非直接 I/O

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

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

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

非直接I/O下，什么时候刷盘？

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

阻塞与非阻塞I/O

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

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

同步与异步 I/O

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

是否阻塞一般指的是进程、线程状态，是否异步一般指的是是否依赖其它任务已经完成

• 如果这个进程、线程在等待当前函数返回时，仍在执行其他消息处理，那这种情况就叫做同步非阻塞；
• 如果这个进程、线程在等待当前函数返回时，没有执行其他消息处理，而是处于挂起等待状态，那这种情况就叫做同步阻塞；

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

异步I/O：

信号驱动式IO

信号驱动式I/O是指进程预先告知内核，使得当某个描述符上发生某事时，内核使用信号通知相关进程。当数据报到达时触发SIGIO信号，该信号通知数据已经到来，并没有将数据都入到应用程序的buffer中。因此，还需要我们在SIGIO信号处理函数中，手动的读取到来的数据，将其存放在buffer中。

总结

Page Cache

非直接I/O中，内核会找个合适的时机，将 page cache 中的数据持久化到磁盘。但是如果 page cache 里的文件数据，在持久化到磁盘化到磁盘之前，系统发生了崩溃，那这部分数据就会丢失了。

当然， 我们也可以在程序里调用 fsync 函数，在写文文件的时候，立刻将文件数据持久化到磁盘，这样就可以解决系统崩溃导致的文件数据丢失的问题。

cat /proc/meminfo

Buffers + Cached + SwapCached = Active(file) + Inactive(file) + Shmem + SwapCached

Page Cache 用于缓存文件的页数据，buffer cache 用于缓存块设备（如磁盘）的块数据。

文件持久化的一致性&可靠性

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

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

方法	含义
fsync(intfd)	fsync(fd)：将 fd 代表的文件的脏数据和脏元数据全部刷新至磁盘中。
fdatasync(int fd)	fdatasync(fd)：将 fd 代表的文件的脏数据刷新至磁盘，同时对必要的元数据刷新至磁盘中，这里所说的必要的概念是指：对接下来访问文件有关键作用的信息，如文件大小，而文件修改时间等不属于必要信息
sync()	sync()：则是对系统中所有的脏的文件数据元数据刷新至磁盘中

• 关于多线程的架构问题，Linux 内核采取了 Lighthttp 的做法，即系统中存在一个管理线程和多个刷新线程（每个持久存储设备对应一个刷新线程）。
• 管理线程监控设备上的脏页面情况，若设备一段时间内没有产生脏页面，就销毁设备上的刷新线程；若监测到设备上有脏页面需要回写且尚未为该设备创建刷新线程，那么创建刷新线程处理脏页面回写。
• 而刷新线程的任务较为单调，只负责将设备中的脏页面回写至持久存储设备中。

刷新线程刷新设备上脏页面大致设计如下：
每个设备保存脏文件链表，保存的是该设备上存储的脏文件的 inode 节点。所谓的回写文件脏页面即回写该 inode 链表上的某些文件的脏页面；

系统中存在多个回写时机:

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

缺页中断

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

设备管理

I/O 控制⽅式

1. 轮询等待
   让 CPU ⼀直查寄存器的状态，直到状态标记为完成，很明显，这种⽅式⾮常的傻⽠，它会占⽤ CPU 的全部时间。
2. 中断
   通知操作系统数据已经准备好了。我们⼀般会有⼀个硬件的中断控制器，当设备完成任务后触发中断到中断控制器，中断控制器就通知 CPU，⼀个中断产⽣了，CPU 需要停下当前⼿⾥的事情来处理中断。
   另外，中断有两种，⼀种软中断，例如代码调⽤ INT 指令触发，⼀种是硬件中断，就是硬件通过中断控制器触发的。
   但中断的⽅式对于频繁读写数据的磁盘，并不友好，这样 CPU 容易经常被打断，会占⽤CPU ⼤量的时间。对于这⼀类设备的问题的解决⽅法是使⽤ DMA功能，它可以使得设备在 CPU 不参与的情况下，能够⾃⾏完成把设备 I/O 数据放⼊到内存。那要实现 DMA 功能要有 「DMA 控制器」硬件的⽀持。

DMA技术

实现了文件I/O的第一道流程

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

1. ⽤户进程调⽤ read ⽅法，向操作系统发出 I/O 请求，请求读取数据到⾃⼰的内存缓冲区中，进程进⼊阻塞状态；
2. 操作系统收到请求后，进⼀步将 I/O 请求发送 DMA，然后让 CPU 执⾏其他任务；
3. DMA 进⼀步将 I/O 请求发送给磁盘；
4. 磁盘收到 DMA 的 I/O 请求，把数据从磁盘读取到磁盘控制器的缓冲区中，当磁盘控制器的缓冲区被读满后，向 DMA 发起中断信号，告知⾃⼰缓冲区已满；
5. DMA 收到磁盘的信号，将磁盘控制器缓冲区中的数据拷⻉到内核缓冲区中，此时不占⽤CPU，CPU 可以执⾏其他任务；
6. 当 DMA 读取了⾜够多的数据，就会发送中断信号给 CPU；
7. CPU 收到 DMA 的信号，知道数据已经准备好，于是将数据从内核拷⻉到⽤户空间，系统调⽤返回；

传统文件传输

两个系统调用：

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

4 次用户态与内核态的上下文切换， 4 次数据拷贝

零拷贝技术

• 要想提⾼⽂件传输的性能，就需要减少⽤户态与内核态的上下⽂切换和内存拷贝的次数。

1. 方案一：
   mmap（见上文共享内存） + write

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

mmap() 系统调用函数会直接把内核缓冲区里的数据「映射」到用户空间，可以减少一次数据拷贝，但是需要通过 CPU 把内核缓冲区的数据拷贝到 socket 缓冲区里，而且仍然需要 4 次上下文切换，因为系统调用还是 2 次，3次数据拷贝

1. 方案二：
   sendfile();

ssize_t sendfile(int out_fd, int in_fd, off_t *offset, size_t count);
//前两个参数分别是目的端和源端的文件描述符，后面两个参数是源端的偏移量和复制数据的长度，返回值是实际复制数据的长度。

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

1. 方案三（真正的零拷贝）：
   网卡需支持SG-DMA技术

   $ ethtool -k eth0 | grep scatter-gather
   scatter-gather: on

1. 通过 DMA 将磁盘上的数据拷⻉到内核缓冲区⾥；
2. 缓冲区描述符和数据⻓度传到 socket 缓冲区，这样⽹卡的 SG-DMA 控制器就可以直接将内核缓存中的数据拷⻉到⽹卡的缓冲区⾥，此过程不需要将数据从操作系统内核缓冲区拷⻉到 socket 缓冲区中，这样就减少了⼀次数据拷⻉；

零拷⻉技术的⽂件传输⽅式相⽐传统⽂件传输的⽅式，减少了 2 次上下⽂切换和数据拷⻉次数，只需要 2 次上下⽂切换和数据拷⻉次数，就可以完成⽂件的传输，⽽且 2 次的数据拷⻉过程，都不需要通过 CPU，2 次都是由 DMA 来搬运。

零拷贝技术的应用：Kafka、Nginx、Java NIO 库里的 transferTo方法

理想的文件传输方式

传输⽂件的时候，我们要根据⽂件的⼤⼩来使⽤不同的⽅式：
传输⼤⽂件的时候，使⽤「异步 I/O + 直接 I/O」；
传输⼩⽂件的时候，则使⽤「零拷⻉技术」；

I/O多路复用

select

select 实现多路复⽤的⽅式是，将已连接的 Socket 都放到⼀个⽂件描述符集合，然后调⽤select 函数将⽂件描述符集合拷⻉到内核⾥，让内核来检查是否有⽹络事件产⽣，检查的⽅式很粗暴，就是通过遍历⽂件描述符集合的⽅式，当检查到有事件产⽣后，将此 Socket 标记为可读或可写， 接着再把整个⽂件描述符集合拷⻉回⽤户态⾥，然后⽤户态还需要再通过遍历的⽅法找到可读或可写的 Socket，然后再对其处理。

所以，对于 select 这种⽅式，需要进行2 次「遍历」⽂件描述符集合，⼀次是在内核态⾥，⼀个次是在⽤户态⾥ ，⽽且还会发⽣ 2 次「拷⻉」⽂件描述符集合，先从⽤户空间传⼊内核空间，由内核修改后，再传出到⽤户空间中。
select 使⽤固定⻓度的 BitsMap，表示⽂件描述符集合，⽽且所⽀持的⽂件描述符的个数是有限制的。

poll

poll 不再⽤ BitsMap 来存储所关注的⽂件描述符，取⽽代之⽤动态数组，以链表形式来组织，突破了 select 的⽂件描述符个数限制，当然还会受到系统⽂件描述符限制。
但是 poll 和 select 并没有太⼤的本质区别，都是使⽤线性结构存储进程关注的 Socket集合，因此都需要遍历⽂件描述符集合来找到可读或可写的 Socket，时间复杂度为 O(n)，⽽且也需要在⽤户态与内核态之间拷⻉⽂件描述符集合，这种⽅式随着并发数上来，性能的损耗会呈指数级增⻓。

epoll

int s = socket(AF_INET, SOCK_STREAM, 0);
bind(s, ...);
listen(s, ...)

int epfd = epoll_create(...);
epoll_ctl(epfd, ...); //将所有需要监听的socket添加到epfd中

while(1) {
    int n = epoll_wait(...);
    for(接收到数据的socket){
        //处理
    }
}

epoll事件集合
EPOLLIN ：表示对应的文件描述符可以读（包括对端SOCKET正常关闭）；
EPOLLOUT：表示对应的文件描述符可以写；
EPOLLPRI：表示对应的文件描述符有紧急的数据可读（这里应该表示有带外数据到来）；
EPOLLERR：表示对应的文件描述符发生错误；
EPOLLHUP：表示对应的文件描述符被挂断；
EPOLLET： 将EPOLL设为边缘触发(Edge Triggered)模式，这是相对于水平触发(Level Triggered)来说的。
EPOLLONESHOT：只监听一次事件，当监听完这次事件之后，如果还需要继续监听这个socket的话，需要再次把这个socket加入到EPOLL队列里

首先创建一个epoll对象，然后使用epoll_ctl对这个对象进行操作，把需要监控的描述添加进去，这些描述如将会以epoll_event结构体的形式组成一颗红黑树，接着阻塞在epoll_wait，进入大循环，当某个fd上有事件发生时，内核将会把其对应的结构体放入到一个链表中，返回有事件发生的链表。

• 第⼀点，epoll 在内核⾥使⽤红⿊树来跟踪进程所有待检测的⽂件描述字，把需要监控的socket 通过 epoll_ctl() 函数加⼊内核中的红⿊树⾥，红⿊树是个⾼效的数据结构，增删查⼀般时间复杂度是 O(logn) ，通过对这棵⿊红树进⾏操作，这样就不需要像 select/poll 每次操作时都传⼊整个 socket 集合，只需要传⼊⼀个待检测的 socket，减少了内核和⽤户空间⼤量的数据拷贝和内存分配
• 第⼆点， epoll 使⽤事件驱动的机制，内核⾥维护了⼀个链表来记录就绪事件，当某个socket 有事件发⽣时，通过回调函数内核会将其加⼊到这个就绪事件列表中，当⽤户调⽤epoll_wait() 函数时，只会返回有事件发⽣的⽂件描述符的个数，不需要像 select/poll 那样轮询扫描整个 socket 集合，⼤⼤提⾼了检测的效率。
• 第三点，使用__put_user 函数，将数据从内核拷贝到用户空间，而非共享内存

两种事件触发模式

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

如果使⽤边缘触发模式，在收到通知后应尽可能地读写数据，以免错失读写的机会。如果是阻塞的，没有数据可读写时，进程会阻塞在读写函数那⾥，程序就没办法继续往下执⾏。所以，边缘触发模式⼀般和⾮阻塞 I/O 搭配使⽤，程序会⼀直执⾏ I/O 操作，直到系统调⽤（如 read 和 write ）返回错误，错误类型为EAGAIN 或 EWOULDBLOCK 。

⼀般来说，边缘触发的效率⽐⽔平触发的效率要⾼,因为边缘触发可以减少 epoll_wait 的系统调⽤次数，系统调⽤也是有⼀定的开销的的，毕竟也存在上下⽂的切换。

内核实现方式

• 在epoll_wait的时候，阻塞等待事件发生， 事件发生时通过回调挂到ready list链表中
• epoll_wait返回， 处理ready list, 返回事件给调用者
• 此时ET模式已经将事件从ready list中删除，LT模式中还存在
• 此时假设应用程序处理完了事件， 再次epoll_wait. ET模式继续阻塞
• LT模式由于ready list中依然存在事件则不会阻塞， 对这些socket调用poll方法获取最新的事件信息，如果确认没事件了才会删除。

//该结构存储在文件结构的"private_data"成员中，代表eventpoll接口的主数据结构。
struct eventpoll {
    //添加到eventpoll接口的每个文件描述符都有一个链接到“rbr”RB树的这种类型的条目。避免增加该结构体的大小，服务器上可能有数千个这样的结构体，我们不希望它占用另一条缓存线。
    struct epitem{
    }
}

io_epoll_ctl()->do_epoll_ctl()->ep_insert()

//将当前项添加到RB树中。所有RB树操作都由"mtx"保护，并且ep_insert()调用时持有"mtx"。
static void ep_rbtree_insert(struct eventpoll *ep, struct epitem *epi)//红黑树插入

//这个回调函数用于将等待队列添加到目标文件唤醒列表中。
static void ep_ptable_queue_proc(struct file *file, wait_queue_head_t *whead,poll_table *pt)

//这是传递给等待队列唤醒机制的回调。 当存储的文件描述符有事件要报告时，就会调用它。
//该回调使用读取锁，以避免与另一个文件描述符的并发事件发生冲突，因此对 ->rdllist 或 ->ovflist 的所有修改都是无锁的。  读锁与来自 ep_start/done_scan() 的写锁配对，可停止所有列表修改，确保正确查看列表状态。
//另一个值得一提的是，如果轮询表中有多个等待队列条目，那么不同 CPU 可以同时调用 ep_poll_callback()来唤醒同一个 @epi。  不同 CPU 对单个等待队列的多次唤醒是通过 wq.lock 序列化的，但如果使用了多个等待队列，则应进行相应检测。  这种情况可通过 cmpxchg() 操作进行检测。
static int ep_poll_callback(wait_queue_entry_t *wait, unsigned mode, int sync, void *key)

//以无锁的方式向列表尾部添加新条目，即允许多个cpu并发调用此函数。
static inline bool list_add_tail_lockless(struct list_head *new,struct list_head *head)

//ET和LT在ready list的区别
if (!(epi->event.events & ~EP_PRIVATE_BITS))
    goto out_unlock;

水平触发的问题

不必要的唤醒
内核：收到一个新建连接的请求
内核：由于 “惊群效应” ，唤醒两个正在 epoll_wait() 的线程 A 和线程 B
线程A：epoll_wait() 返回
线程B：epoll_wait() 返回
线程A：执行 accept() 并且成功
线程B：执行 accept() 失败，accept() 返回 EAGAIN

边缘触发的问题

不必要的唤醒

1.内核：收到第一个连接请求。线程 A 和 线程 B 两个线程都在 epoll_wait() 上等待。
由于采用边缘触发模式，所以只有一个线程会收到通知。这里假定线程 A 收到通知
2.线程A：epoll_wait() 返回
3.线程A：调用 accpet() 并且成功
4.内核：此时 accept queue 为空，所以将边缘触发的 socket 的状态从可读置成不可读
5.内核：收到第二个建连请求
6.内核：此时，由于线程 A 还在执行 accept() 处理，只剩下线程 B 在等待 epoll_wait()，
于是唤醒线程 B。
7.线程A：继续执行 accept() 直到返回 EAGAIN
8.线程B：执行 accept()，并返回 EAGAIN，此时线程 B 可能有点困惑(“明明通知我有事件，结果却返回 EAGAIN”)
9.线程A：再次执行 accept()，这次终于返回 EAGAIN

饥饿
1.内核：接收到两个建连请求。线程 A 和 线程 B 两个线程都在等在 epoll_wait()。
由于采用边缘触发模式，只有一个线程会被唤醒，我们这里假定线程 A 先被唤醒
2.线程A：epoll_wait() 返回
3.线程A：调用 accpet() 并且成功
4.内核：收到第三个建连请求。由于线程 A 还没有处理完(没有返回 EAGAIN)，
当前 socket 还处于可读的状态，由于是边缘触发模式，所有不会产生新的事件
5.线程A：继续执行 accept() 希望返回 EAGAIN 再进入 epoll_wait() 等待，
然而它又 accept() 成功并处理了一个新连接
6.内核：又收到了第四个建连请求
7.线程A：又继续执行 accept()，结果又返回成功

ET和LT模式各自应用场景是什么？为什么有了高效的ET还需要LT？

1. LT的编程更符合用户直觉，业务层逻辑更简单，不易出错，但效率较低；
2. ET的编程可以做到更加简洁，某些场景下更加高效，但另一方面容易遗漏事件，容易产生bug；
3. 对于nginx这种高性能服务器，ET模式是很好的，Redis使用的是LT，避免使用的过程中出现bug；
4. 当并发量比较小时，比较推荐LT，因为LT模式下应用的读写逻辑比较简单，不容易遗漏事件，代码不易出错好维护，而且性能损失不大。当并发量非常大时，推荐使用ET模式，可以有效提升EPOLL效率。

(1)在ET模式下，一个文件描述符上有数据可读（EPOLLIN触发），线程开始处理数据，而在处理过程中又有新数据加入。当旧数据开始处理时，文件描述符仍然保持在就绪状态。但当有新的数据写入时，文件描述符会从就绪状态变为未就绪状态，然后再次变为就绪状态，触发一次新的 EPOLLIN 事件。这样可以确保即使在旧数据处理过程中有新的数据写入，应用程序也能及时地得到通知，并读取新的数据。因此，在单线程上，此时只要程序循环读取数据就不会造成新数据的丢失
(2)但是对于多线程就需要特殊处理（EPOLLONESHOT）。当一个线程处理一个socket时有新数据写入，此时另外一个线程被唤醒读取这些数据，于是出现了两个线程同时操作一个socket的情况。EPOLLONESHOT解决了多个线程同时操作一个socket的问题，对于注册了EPOLLONESHOT的事件，操作系统最多触发其上注册的一个可读可写异常事件，且只触发一次。这样，一个线程在操作这个socket时，其他线程不可能有机会操作该socket。但反过来思考，注册了EPOLLONESHOT事件的socket，一旦被某个线程处理完毕，要及时修改为EPOLLIN或其他事件，以确保下次这个socket可读时，其事件能够被触发，进而让其他线程有机会继续处理
(3)在 LT 模式下，新数据的写入不会改变文件描述符的状态码。如果文件描述符上有数据可读，它的状态码会一直保持就绪状态，直到所有的数据都被读取完毕才会变为未就绪。即使在读取数据的过程中有新的数据写入，文件描述符的状态码仍然会保持就绪状态，不会因为新数据的写入而改变

其它知识

Shell

1. 什么是shell？

• shell是linux的一个外壳，它包在linux内核的外面，为用户和内核之间的交互提供了一个接口。
• 当用户下达指令给该操作系统的时候，实际上是把指令告诉shell，经过shell解释，处理后让内核做出相应的动作。
• 系统的回应和输出的信息也由shell处理，然后显示在用户的屏幕上

1. 为什么使用shell脚本？

• 适合处理操作系统底层的业务，有众多系统命令为其做支撑（还有文本处理三兄弟：grep，sed，awk）
• 适合处理纯文本文件，linux中许多服务配置文件，启动脚本，都是纯文本文件（如：httpd，nfs，mysql，nginx，lvs）
• linux系统脚本用shell开发更简单，简言之，shell脚本操作更加方便，快捷，高效。

1. shell脚本与编程语言的区别？

• shell脚本是能运行的文本，它包含命令和运行逻辑关系 。与C语言、C++、C#等编程语言不同。
• shell脚本不需要编译、连接及生成可执行文件，直接由相应的解释器（最常用的解释器为bash） 解释执行即可。
• 它的优点是可批量，多次执行（使用）。简言之，shell脚本是解释性语言，而c语言则是编译性语言。

Handle

句柄

Windows是一个以虚拟内存为基础的操作系统，进程的代码和数据并不全部装入内存，进程的某一段装入内存后，还可能被换出到外存，当再次需要时，再装入内存。两次装入的地址绝大多数情况下是不一样的。

系统为每个进程在内存中分配一定的区域，用来存放各个句柄，即一个个无符号整型。每个无符号整型值相当于一个指针，指向内存中的另一个区域A。而区域A中存放的正是对象在内存中的地址。当对象在内存中的位置发生变化时，区域A的值被更新，变为当前时刻对象在内存中的地址，而在这个过程中，区域A的位置以及对应句柄的值是不发生变化的。

1. 所谓“唯一”、“不变”是指在程序的一次运行中。如果本次运行完，关闭程序，再次启动程序运行，那么这次运行中，同一对象的句柄的值和上次运行时比较，一般是不一样的。
2. 句柄是对象生成时系统指定的，属性是只读的，程序员不能修改句柄。
3. 不同的系统中，句柄的大小（字节数）是不同的，可以使用sizeof()来计算句柄的大小。
4. 通过句柄，程序员只能调用系统提供的服务（即API调用），不能像使用指针那样，做其它的事。

Linux网络传输

Linux 接收⽹络包的流程

• ⽹卡是计算机⾥的⼀个硬件，专⻔负责接收和发送⽹络包，当⽹卡接收到⼀个⽹络包后，会通过 DMA 技术，将⽹络包放⼊到 Ring Buffer，这个是⼀个环形缓冲区。
• Linux 内核在 2.6 版本中引⼊了 NAPI 机制，它是混合「中断和轮询」的⽅式来接收⽹络包，它的核⼼概念就是不采⽤中断的⽅式读取数据，⽽是⾸先采⽤中断唤醒数据接收的服务程序，然后 poll 的⽅法来轮询数据
• ⽐如，当有⽹络包到达时，⽹卡发起硬件中断，于是会执⾏⽹卡硬件中断处理函数，中断处理函数处理完需要「暂时屏蔽中断」，然后唤醒「软中断」来轮询处理数据，直到没有新数据时才恢复中断，这样⼀次中断处理多个⽹络包，于是就可以降低⽹卡中断带来的性能开销。

高性能网络模式：Reactor 和 Proactor

Reactor

1. 单 Reactor 单进程 / 线程

Reactor 对象的作用是监听和分发事件；Acceptor 对象的作用是获取连接；Handler 对象的作用是处理业务；对象里的 select、accept、read、send 是系统调用函数，dispatch 和 「业务处理」是需要完成的操作，其中 dispatch 是分发事件操作。

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

但是，这种方案存在 2 个缺点：

1. 因为只有一个进程，无法充分利用 多核 CPU 的性能；
2. Handler 对象在业务处理时，整个进程是无法处理其他连接的事件的，如果业务处理耗时比较长，那么就造成响应的延迟；
   所以，单 Reactor 单进程的方案不适用计算机密集型的场景，只适用于业务处理非常快速的场景。

2. 单 Reactor 多线程 / 多进程

• Reactor 对象通过 select （IO 多路复⽤接⼝） 监听事件，收到事件后通过 dispatch 进⾏分发，具体分发给 Acceptor 对象还是 Handler 对象，还要看收到的事件类型；
• 如果是连接建⽴的事件，则交由 Acceptor 对象进⾏处理，Acceptor 对象会通过 accept⽅法 获取连接，并创建⼀个 Handler 对象来处理后续的响应事件；
• 如果不是连接建⽴事件， 则交由当前连接对应的 Handler 对象来进⾏响应；
• Handler 对象不再负责业务处理，只负责数据的接收和发送，Handler 对象通过 read 读取到数据后，会将数据发给⼦线程⾥的 Processor 对象进⾏业务处理；
• ⼦线程⾥的 Processor 对象就进⾏业务处理，处理完后，将结果发给主线程中的 Handler对象，接着由 Handler 通过 send ⽅法将响应结果发送给 client；

「单 Reactor」的模式能够充分利用多核 CPU 的能力，但是有个问题，因为⼀个 Reactor 对象承担所有事件的监听和响应，⽽且只在主线程中运⾏，在⾯对瞬间⾼并发的场景时，容易成为性能的瓶颈的地⽅。

3. 多 Reactor 多进程 / 线程

• 主线程中的 MainReactor 对象通过 select 监控连接建⽴事件，收到事件后通过 Acceptor对象中的 accept 获取连接，将新的连接分配给某个⼦线程；
• ⼦线程中的 SubReactor 对象将 MainReactor 对象分配的连接加⼊ select 继续进⾏监听，并创建⼀个 Handler ⽤于处理连接的响应事件。
• 如果有新的事件发⽣时，SubReactor 对象会调⽤当前连接对应的 Handler 对象来进⾏响应。
• Handler 对象通过 read -> 业务处理 -> send 的流程来完成完整的业务流程。
• 主线程和⼦线程分⼯明确，主线程只负责接收新连接，⼦线程负责完成后续的业务处理。
• 主线程和⼦线程的交互很简单，主线程只需要把新连接传给⼦线程，⼦线程⽆须返回数据，直接就可以在⼦线程将处理结果发送给客户端。

Netty 和 Memcache 都采用了「多 Reactor 多线程」的方案。采用了「多 Reactor 多进程」方案的开源软件是 Nginx，不过方案与标准的多 Reactor 多进程有些差异

Proactor

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