操作系统

进程和线程

线程与进程区别

线程与协程区别

• 协程是一种用户态的轻量级线程，一个线程可以有多个协程，其特性在于CPU的执行权是由协程主动让出的，相比内核态线程而言，调度协程的时机开发者是比较清楚的
• 创建开销：协程的栈空间占用只有 2k~4k，在一个地址空间中可以运行 10w 级别的协程
• 切换开销：进程和线程切换时都涉及内核切换（陷入内核态运行调度程序）；而协程调度由用户程序控制，只需要保存寄存器上下文和栈，不涉及内核切换的开销，提高了性能，但也失去了使用多CPU的能力
• 同步问题：
  • 从狭义的角度来看，因为调度协程的线程只有一个，所以不存在数据竞态（多线程并发访问共享资源），不需要类似线程锁的机制保障安全
  • 从用户进程的角度看，调度协程时虽然是主动让出CPU的，但如果a协程在让出CPU之前引用了全局变量，随后执行b协程时修改了全局变量，等调度回协程a时就可能导致运行结果不符预期。所以也需要通过编程上的一些技巧来避免协程调度的过程中产生的数据污染（比如引用全局变量的一个副本等）

进/线程间同步方式

1. 临界区：让多个线程串行化访问公共资源或代码，在有一个线程进入后其他访问临界区的线程将被挂起，以CRITICAL_SECTION结构对象保护共享资源
   • 优点：方法简便，速度快
   • 缺点：不能同步多个进程中的线程
2. 互斥量：跟临界区相似但更复杂，互斥对象只有一个，只有拥有互斥对象的线程才能访问资源
   • 优点：可以在不同应用程序的线程之间实现资源共享
   • 缺点：互斥量是可以命名的，可以跨越进程使用，但创建所需的资源更多，所以只在进程内使用时不如临界区速度快、资源占用少；不能允许多个线程同时对资源的访问
3. 信号量：允许多个线程同时访问一资源，并限制在同一时刻访问此资源的最大线程数目。互斥量是信号量的一种特殊情况，当信号量的最大资源数=1就是互斥量了
   • 优点：适用于对 Socket 程序中线程的同步
   • 缺点：基于公共内存，不能用于分布式操作系统；P-V 操作分散在各用户程序的代码中， 读写和维护都很困难，加重了编码负担；
4. 事件：用来通知线程有一些事件已发生，从而启动后继任务的开始。事件处于激发或未激发状态，分为两类：①手动设置：只能手动设置事件对象，事件发生后手动重置对象；②自动恢复：事件发生并处理后，自动恢复，无需手动设置
   • 优点：通过通知操作可以实现不同进程中的线程同步。

进程间的通信方式

1. 匿名管道：一种半双工的通信方式，数据单向流动，简单但是只能在有亲缘关系的进程间使用（父子、兄弟）
2. 命名管道：一种半双工的通信方式，它允许无亲缘关系进程间的通信
   • 缺点：缓冲区有限；命名管道在使用完后依然存在于文件系统中，不会自动删除
3. 信号量：允许多个进程同时访问一资源，并限制在同一时刻访问此资源的最大进程数目
4. 信号：信号是在软件层次上对中断机制的一种模拟，一种异步通信方式。信号可以让一个正在运行的进程被另一个异步进程中断，转而处理某个突发事件
   • 缺点：不能传递复杂消息，只能用来同步
5. 消息队列：是存放在内核中的消息链表，每个消息队列由消息队列标识符标识
   • 优点：可以实现任意进程间的通信，通过系统调用函数来实现消息发送和接收之间的同步，无需考虑同步
   • 缺点：信息的复制需要额外消耗 CPU 的时间，不适宜于信息量大或操作频繁的场合
6. 共享内存：将不同进程的虚拟内存地址映射到相同的物理内存地址，所有的进程都可以访问共享内存中的地址，一个进程对共享内存所做的改动将立即影响到其他进程，Linux共享内存最多128个
   • 优点：无须复制，快捷，信息量大
   • 缺点：并未提供同步机制；只能由同一个计算机系统中的进程共享，不方便网络通信
7. 套接字：可用于不同计算机间的进程通信
   • 优点：传输数据为字节级，传输数据可以自定义；客户端服务器之间信息实时交互；可以加密，安全性强
   • 缺点：需对传输的数据进行解析，转化成应用级的数据。

线程间的通信方式

1. 锁机制：包括互斥锁、读写锁、自旋锁、条件变量

   详见 “线程的几种锁“

2. 信号量：无名线程信号量、命名线程信号量

3. 信号：类似进程间的信号处理，用法：处理signal(SIGINT, fun)，忽略signal(SIGINT, SIG_IGN)

   • SIGINT 中断信号，Ctrl+C
   • SIGTERM 终止信号，kill -15，可以被捕获处理
   • SIGKILL 强制终止信号，kill -9
   • SIGSEGV 段错误信号，访问了未分配内存
   • SIGCHILD 子进程状态变化信号，当子进程终止或停止时发送给父进程

线程的几种锁

• 互斥锁：一次只能一个线程拥有互斥锁，抢锁失败的线程主动放弃CPU并进入睡眠状态
• 读写锁：允许多个线程同时读共享数据，而写操作是互斥的，写优先于读（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）
• 自旋锁：线程无法取得锁时不会立刻放弃CPU，而是一直循环尝试获取锁。如果别的线程长时期占有锁，那么自旋会浪费CPU，一般应用于加锁时间很短的场景，此时效率比较高
• 条件变量：直到某个特定条件为真为止，以原子的方式阻塞进程。条件测试是在互斥锁的保护下进行的，若条件不满足，线程解开互斥锁并阻塞线程，等到某个线程改变了条件变量时，他将通知相应的条件变量唤醒被阻塞线程。互斥锁是线程间互斥的机制，条件变量是同步机制
• 递归锁：也叫可重⼊锁，在一个线程在不解锁的情况下多次锁定同一个递归锁，而且不会产生死锁

进程与线程的切换（3.5μs）

进程切换

1. 切换页表以使用新的地址空间，一旦切换上下文，处理器中所有已缓存的内存地址一瞬间都作废了
2. 切换内核栈和硬件上下文

线程切换

1. 切换内核栈和硬件上下文（地址空间不变）

为什么虚拟地址空间切换比较耗时？

• 每个进程都有自己的虚拟地址空间和页表，所以进程切换后页表也要进行切换。页表切换后TLB失效，Cache失效导致命中率降低，虚拟地址转换物理地址速度变慢，最终表现为程序运行变慢。
• 线程切换不会导致TLB失效，因为线程共享所在进程的虚拟地址空间，无需切换地址空间，因此线程切换快。

进程调度算法

1. 先来先服务 FCFS

   按照请求的先后顺序进行调度，是非抢占式的调度算法。利于长作业但不利于短作业，因为短作业必须等待前面的长作业执行完毕才能执行，造成等待时间过长。

2. 短作业优先 SPF

   选择估计运行时间最短的作业，将它们调入内存运行。但长作业的运行得不到保证。

3. 优先级调度

   为每个进程分配一个优先级，按优先级进行调度。为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。

4. 高响应比优先

   选择响应比最大的作业执行，响应比=(等待时间+要求服务时间)/要求服务时间。既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务，但每次调度前对响应比的计算会增加系统开销。

5. 时间片轮转 RR

   将所有就绪进程按 FCFS 的原则排成一个队列，每次让队首进程执行一个时间片，当时间片用完后计时器发出时钟中断，调度程序便停止执行该进程并送往就绪队列的末尾，再把 CPU时间分配给新的队首进程。

   算法效率和时间片大小有关：因为进程切换都要保存和载入进程信息，如果时间片太小，会导致进程切换太频繁、浪费时间，如果时间片过长则不能保证实时性。

6. 多级反馈队列 MLFQ

   设置多个就绪队列，每个队列的优先级不同，进程执行时间片的大小也不同。

   首先将进程放入第一队列的末尾，按 FCFS 原则排队等待调度。若在时间片内未执行完，调度程序便将该进程转入第二队列的末尾，再同样按 FCFS 原则等待调度…… 若最终降到第 n 队列则采取时间片轮转方式。

   仅当前 i 个队列均空时，才会调度第 i 队列中的进程运行。如果正在处理第 i 队列某进程时，有新进程进入优先权较高的队列，则新进程将抢占处理机，由调度程序把正在运行的进程放回原队列末尾。

守护进程、孤儿进程和僵尸进程

• 守护进程：指在后台运行的，没有控制终端与之相连的进程。它独立于控制终端，周期性地执行某种任务。Linux的大多数服务器就是用守护进程的方式实现的，如web服务器进程http等
• 孤儿进程：如果父进程退出而子进程还在运行，则子进程成为孤儿进程。孤儿进程将被 init 进程接收并完成状态收集工作
  避免：⽗进程调⽤ wait 或者 waitpid 函数等待⼦进程完成再退出
• 僵尸进程：如果子进程退出而父进程还在运行，那么子进程必须等到父进程捕获到了其退出状态才真正结束，否则这个时候子进程就成为僵尸进程。设置僵尸进程的目的是维护子进程的信息，以便父进程在以后某个时候获取子进程ID、终止状态等
  避免：⼦进程退出时向⽗进程发送 SIGCHILD 信号，⽗进程处理 SIGCHILD 信号。在信号处理函数中调⽤ wait 进⾏处理僵⼫进程

中断

内中断

1. 内中断的产生

• 除法错误:0
• 单步执行:1
• 执行 into 指令:4
• 执行 int 指令,格式为int n ,n为字节型立即数,是中断类型码

2. 中断过程

由中断类型码找到中断向量,并自动用它设置 CS和IP，随后执行中断处理程序

1. 从中断信息取得中断类型码N
2. pushf //标志寄存器入栈(中断过程中值改变)
3. TF=0,IF=0 //设置标志寄存器的TF、IF位
4. push CS push IP
5. (IP)=(N*4),(CS)=(N*4+2)

3. 中断向量表

中断向量表是中断处理程序入口地址的列表，在内存0000:0000到0000:03FF的1024个单元中存放，一个表项存放一个中断向量,占两个字,高地址存放段地址,低地址存放偏移地址

4. 中断处理程序

中断处理程序必须一直存储在内存某段空间之中，而中断向量必须存储在对应的中断向量表表项中。中断处理程序常规的步骤:

1. 保存用到的寄存器;
2. 处理中断;
3. 恢复用到的寄存器;
4. 用 iret 指令返回。

外中断

外设随时都可能发⽣需要CPU及时处理的事件，这种中断来⾃于CPU的外部，当CPU外部有需要处理的事情发⽣的时候，⽐如说，外设的输⼊到达，相关芯⽚将向CPU发出相应的中断信息。CPU在执⾏完当前指令后，可以检测到发送过来的中断信息，引发中断过程，处理外设输⼊。

在PC系统中，外中断源⼀共有以下两类。

• 可屏蔽中断

  • 当CPU检测到可屏蔽中断信息时，如果IF=1，则CPU在执⾏完当前指令后响应中断，引发中断过程：如果IF=0，则不响应可屏蔽中断。

  • 可屏蔽中断所引发的中断过程，除在第1步的实现上有所不同外，基本上和内中断的中断过程相同。因为可屏蔽中断信息来⾃于CPU外部，中断类型码是通过数据总线送⼊CPU的；⽽内中断的中断类型码是在CPU内部产⽣的。

  • 故中断过程中将IF置为0的原因：在进⼊中断处理程序后，禁⽌其他的可屏蔽中断。当然，如果在中断处理程序中需要处理可屏蔽中断，可以⽤指令将IF置1。指令：sti ，设置IF=1；cli ，设置IF=0

• 不可屏蔽中断

  • 当CPU检测到不可屏蔽中断信息时，则在执⾏完当前指令后，⽴即响应，引发中断过程。

  • 不可屏蔽中断的中断类型码固定为2，所以中断过程中，不需要取中断类型码，则不可屏蔽中断的中断过程为

  • ⼏乎所有由外设引发的外中断，都是可屏蔽中断。

死锁

死锁和活锁

• 死锁：指两个及以上的进程在执行过程中，由于竞争资源或彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。
• 活锁：指的是任务没有被阻塞，由于某些条件没有满足，导致一直重复尝试，失败，尝试，失败。

死锁条件

1. 互斥条件：一个资源每次只能被一个进程使用
2. 不可剥夺条件：进程已获得的资源在未使用完之前不能强行剥夺
3. 请求与保持条件：一个进程因请求资源而阻塞时，不释放已获得的资源
4. 循环等待条件：若干进程之间形成一种头尾相接的循环等待资源关系

解决死锁的方法

• 预防：采用某种策略，限制并发进程对资源的请求，从而使得死锁的必要条件在任何时间都不满足。
• 避免：系统在分配资源时，根据资源的使用情况提前做出预测，从而避免死锁的发生
• 检测：系统设有专门的机构检测死锁的发生，并确定与死锁有关的进程和资源。
• 解除：配合死锁检测，将进程从死锁状态下解脱出来。

死锁预防

• 破坏互斥条件。允许进程同时访问资源，但有的资源不能同时被访问。
• 破坏不可剥夺条件：允许进程抢占资源。这种预防方法实现起来困难，会降低系统性能。
• 破坏请求与保持条件：实行预先分配策略，在进程运行前就申请它所需要的全部资源，若不能满足则不分配任何资源。
  • 进程执行是动态的，很难提前预测它所需的全部资源。
  • 资源利用率低，即使有些资源最后才被用到，也会被进程长期占有。
• 破坏循环等待条件：给资源统一编号，让进程按序请求资源。
  • 相比之下资源利用率和系统吞吐量有所提高
  • 限制了进程对资源的请求，也难以给资源合理编号，增加了系统开销。

Mutex原理

Mutex 的本质就是一个内存标志，这个标志可以是一个flag（占用标志，底层基于硬件原子操作），也可以是一个指向持有者线程ID的指针，另外还有一个阻塞队列等若干信息。当 Mutex 被标记成占用、或持有者指针非空时，它就不能被被别的线程访问。只有等到空闲时，操作系统会从阻塞队列里取出第一线程调度执行（或标为就绪态等待调度）。

死锁避免

将系统的状态分为安全状态和不安全状态，分配资源前先测试系统状态，若分配资源后会产生死锁则拒绝分配，否则才为它分配资源。
安全状态：操作系统能够保证所有的进程在有限的时间内得到需要的全部资源。安全状态不会发生死锁，不安全状态可能发生死锁。
银行家算法：进程申请使用资源时，先试探分配给该进程资源，然后通过安全性算法判断分配后系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待，否则才真正分配资源给该进程。

死锁检测

不限制资源分配，也不采取死锁避免措施，但系统定时地运行一个 “死锁检测”的程序，判断系统内是否出现死锁，如果检测到了死锁再采取措施解除。

死锁解除

• 资源剥夺法：挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源，而处于资源匮乏的状态。
• 撤销进程法：撤销部分死锁进程，并剥夺它的资源。撤销的原则可以按进程优先级和撤销进程代价进行。
• 进程回退法：让部分进程回退到足以回避死锁的地步，进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息，设置还原点。

内存管理

分页存储

将程序的逻辑地址空间划分为固定大小的页，物理内存划分为同样大小的页框，大小取2的整数幂。程序加载时，可将任意一页放入内存中任意一个页框，因为页框不必连续，所以实现了离散分配。

需要用页表来记录页号到物理块号的映射关系，进程未执行时，页表的始址和长度放在 PCB 中，进程调度后放到页表寄存器 PTR 中。

地址映射：

地址结构由页号和页内地址（位移量）组成。CPU中的内存管理单元 (MMU) 按逻辑页号通过查进程的页表得到物理页框号，将物理页框号与页内地址相加形成物理地址。

优点：

• 没有外碎片，提高内存的利用率
• 实现离散分配，一个程序不必连续存放

缺点：

• 无论数据有多少，都只能按照页面大小分配，容易产生内部碎片
• 不能体现程序逻辑，页长与程序的逻辑大小不相关
• 不利于编程时的独立性，不易于存储保护和信息共享

快表

操作系统引入快表来加速虚拟地址到物理地址的转换。可以把快表理解为一种特殊的高速缓冲存储器，其中存放了页表的部分内容。作为页表的 Cache，它的作用与页表相似，但是提高了访问速率。因为采用页表做地址转换读写内存数据时，CPU 要访存两次，而通过快表可以只访问一次高速缓冲存储器，一次主存。

使用快表之后的地址转换流程是这样的：

1. 根据虚拟地址中的页号查快表，如果该页在快表中，直接从快表中读取相应的物理地址；
2. 如果该页不在快表中，就访问内存中的页表，再从页表中得到物理地址，同时将映射表项添加到快表中；
3. 当快表填满又要登记新页时，就按照一定的淘汰策略淘汰掉快表中的一个页。

分页和分段存储区别

共同点：

• 都是为了提高内存利用率，减少内存碎片。
• 都是离散分配内存的方式，但每个页和段中的内存是连续的。

区别：

• 页是信息的物理单位，分页是为了离散分配提高内存的利用率；段是信息的逻辑单位，分段是为了更好地满足用户的需要。

• 页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。

• 分页的地址空间是一维的，程序员只需用一个记忆符即可表示一个地址；而分段的作业地址空间是二维的，标识一个地址需要给出段名+段内地址。

• 段是信息的逻辑单位，便于存储保护和信息共享；页的保护和共享受到限制。

虚拟内存

什么是虚拟内存

基于局部性原理，可以将程序的一部分装入内存就启动执行，而其他部分留在外存。由于外存往往比内存大很多，所以运行的软件内存大小可以比计算机的实际内存更大。如果程序在运行中发生缺页（通过页表项标记位判断），则由处理器通知操作系统按照对应的页面置换算法将相应的页面调入到主存，同时操作系统也可以将暂时不用的页面置换到外存中。这样，计算机好像为用户提供了一个远大于实际内存的存储器，也叫虚拟存储器。

虚拟内存是一种时间换空间的策略，用 CPU 的计算时间、页的调入调出花费的时间，换来了一个虚拟的更大的空间来支持程序的运行。

为什么要用虚拟内存？因为早期的内存分配方法存在以下问题：

• 进程地址空间不隔离，会导致数据被随意修改。
• 内存使用效率低。
• 操作系统随机为进程分配内存空间，所以程序运行的地址是不确定的。

虚拟内存的优点：

1. 扩大了地址空间，虽然真实物理内存没那么多
2. 内存保护：防止不同进程对物理内存的争夺，可以对特定内存地址提供写保护
3. 可以实现内存共享，方便进程通信
4. 可以避免内存碎片，虽然物理内存可能不连续，但映射到虚拟内存上可以连续

虚拟内存的缺点：

1. 虚拟内存需要额外构建数据结构，占用空间
2. 虚拟地址到物理地址的转换和页面换入换出，增加了执行时间

页面置换算法

• OPT 最佳页面置换算法 ：淘汰以后最久不再访问的页面，这样可以保证获得最低的缺页率。但由于无法预知哪个页面未来最久不再被访问，因而该算法无法实现，一般作为衡量其他置换算法的方法。
• FIFO 先进先出页面置换算法：淘汰最先进入内存的页面。
• LRU 最近最久未使用页面置换算法：赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 T，当须淘汰一个页面时，选择现有页面中其 T 值最大的，即最近最久未使用的页面予以淘汰。
• LFU 最少使用页面置换算法：选择之前使用最少的页面作为淘汰页

用户态和内核态

⽤户态转化内核态

• 系统调⽤
  ⽤户态进程主动切换到内核态的⼀种⽅式，是操作系统提供给⽤户程序的⼀组特殊接⼝，从而让⽤户程序获得操作系统内核提供的服务，⽐如 fork() 实际上就是执⾏了⼀个创建新进程的系统调⽤。系统调⽤的核心机制是使⽤了操作系统为⽤户开放的⼀个中断来实现，例如 Linux 的 int 80h 中断。
• 异常
  由 CPU 执行指令的内部事件引起异常，如非法操作码、地址越界、算术溢出等。这时会触发当前进程切换到内核态的异常处理程序中。
• 外中断
  当外围设备完成⽤户请求的操作后，会向 CPU 发出相应的中断信号，这时 CPU 会暂停执⾏下⼀条要执⾏的指令，转⽽去执⾏相应的中断处理程序，如果先前执⾏的指令是⽤户态下的程序，就发⽣了由⽤户态到内核态的切换。如 I/O 完成中断、时钟中断、控制台中断等

内核级和用户级线程

• 内核级线程：依赖于内核，又称为内核支持的线程或轻量级进程。无论是在用户程序中还是系统进程中的线程，它们的创建、撤销和切换都由内核实现，可以在进程内并发，但创建、切换开销大
• 用户级线程：它仅存在于用户级中，不依赖于内核，操作系统内核无法感知用户级线程的存在，不能并发（一个堵塞所有堵塞）。应用进程利用线程库来完成其创建和管理，速度比较快
• 用户级线程和内核级映射关系：一对一，多对多，多对一

IO模型

网络IO涉及用户空间和内核空间，一般会经历两个阶段：

• 一阶段：等待网络数据被copy到内核缓冲区

  此阶段内核数据没准备好时（等待socket中数据到来），根据用户进程是否睡眠分为阻塞和非阻塞

• 二阶段：将数据从内核缓冲区copy到用户空间

  此阶段根据用户进程是否参与数据读写，分为同步和异步

  • 同步：数据读写都是请求方自己来完成
  • 异步：请求方并没有参与事件读写，由他人完成

根据以上两阶段的不同，分为以下五种网络IO模型：

五种I/O模型

1. 阻塞 I/O
   调⽤I/O函数会使进程阻塞，先等待数据准备好，再从内核拷⻉到⽤户空间。两个阶段均堵塞。

2. ⾮阻塞 I/O
   当I/O操作⽆法完成时不将进程睡眠，⽽是返回⼀个错误如 EWOULDBLOCK、EAGAIN。I/O操作函数将不断询问内核数据是否准备好（⼤量的占⽤CPU的时间），当数据准备好时，用户进程会阻塞直到数据从内核空间copy到用户空间完成。一阶段不阻塞，二阶段阻塞。

3. I/O 多路复⽤
   通过一种机制监视多个描述符，一旦某个描述符就绪，就通知程序进行相应的读写操作，会⽤到select、poll、Epoll 函数。I/O多路复用通常是非阻塞的，因为它允许你同时监控多个I/O操作而不必等待任何一个特定操作完成，但是第二阶段的I/O操作仍阻塞，属于同步。

4. 信号驱动 I/O
   Linux通过 sigaction 系统调用，建立起信号驱动IO的socket，并绑定一个信号处理函数；sigaction 不会阻塞，立即返回，进程继续运行。当数据准备好，内核就为进程产生一个 SIGIO 信号，随后在信号处理函数中接收数据。与非阻塞IO的区别在于它提供了消息通知机制，不需要用户进程不断地轮询检查，减少了系统调用次数，提高了效率。一阶段不阻塞，二阶段阻塞。

   以上四种模型在真正IO操作时都需要用户进程参与，均称为同步IO模型。

5. 异步 I/O
   如 libaio 库、POSIX 标准定义的异步IO的 aio 接口。用户进程调用 aio_read 之后会立即返回不阻塞，aio_read 会给内核传递文件描述符，缓冲区指针，缓冲区大小等；数据准备好时，内核直接将数据copy到用户空间，copy完后给用户进程发送一个信号，进行用户数据异步处理。因此用户进程不需要将数据从内核空间copy到用户空间。两阶段均不阻塞。

I/O复用的原理

进程预先告诉内核需要监视的IO条件，内核⼀旦发现进程指定的⼀个或多个IO条件就绪，就通过进程处理，从⽽不会在单个IO上阻塞了。Linux中提供了select、poll、Epoll三种接⼝函数来实现IO复⽤。

Select

监视文件描述符 fd 的三种事项：读事件、写事件、异常事件。

1. 可监视的最大文件描述符数量有限（1024）
2. 每次监听都要将文件描述符集合 fd_set 从用户态重新拷贝到内核态，返回结果时再拷贝出来
3. 调用完 Select 函数后需要循环获取发生变化的 fd，在大量 fd 并发、少量活跃时效率低

Poll

使⽤链表保存⽂件描述符，没有了监视⽂件数量的限制，但 Select 的其他三个缺点依然存在

Epoll

底层是一棵红黑树和一个就绪链表（双向链表），红黑树结点是一个与 fd 相关的结构体，包括了fd、事件和回调函数。当 fd 上有对应感兴趣事件发生时，内核自动调用回调函数将其添加到链表里，返回结果时（ET模式下清空链表）将就绪的 fd 集合返回用户空间，同时返回就绪事件的数量。使用红黑树查找删除添加都是 logn 的时间复杂度，有较稳定的时间复杂度，通过查找红黑树防止重复添加文件描述符。

相比与 Select 和 Poll，Epoll 更加高效：

1. 没 fd 数量限制：是一个很大的值，和内存大小有关
2. 减少拷贝(用户态<->内核态)：Select、Poll都需要将有关 fd 的数据结构拷贝进内核，返回结果时再拷贝出来。Epoll红黑树中已上树的 fd 不用再次拷贝，并且返回文件描述符时使用 mmap() 内存映射避免了内核态到用户态之间的拷贝
3. 回调(监测方式)：Select、Poll采用轮询的方式来检查 fd 是否处于就绪态，而Epoll采用回调机制。随着 fd 的增加，Epoll性能不会线性降低，除非活跃的socket很多。
4. 无需遍历(处理返回结果)：Select、Poll、Epoll虽然都会返回就绪的文件描述符数量。但是select和poll并不会明确指出是哪些文件描述符就绪，而Epoll会。因此系统调用返回后，Epoll无需遍历监听的整个文件描述符找到是谁处于就绪，直接处理即可。
5. ET触发：Epoll的边缘触发模式效率高，系统不会充斥大量不关心的就绪文件描述符
6. 虽然Epoll的性能最好，但是在连接数少并且连接都十分活跃的情况下，Select和Poll的性能可能比Epoll好，毕竟Epoll的通知机制需要很多函数回调。

LT模式和ET模式

水平触发

• 触发条件：只要缓冲区非空、不满时。
• 当 epoll_wait 检测到描述符事件时，应⽤程序可以不⽴即处理该事件，之后每次调⽤ epoll_wait 时还会继续通知此事件。但如果系统中有大量不需读写的就绪 fd ，而它们每次都返回，就会大大降低效率。

边缘触发

• 触发条件：缓冲区从不可读变为可读、不可写变为可写、数据量增减、 EPOLL_CTL 进行了 MOD 操作时。
• 当 epoll_wait 检测到描述符事件时，应⽤程序必须⽴即处理该事件。如果不处理，下次调⽤ epoll_wait 时不会再通知此事件，直到这个文件描述符上出现第二次该事件时才会通知。在很大程度上降低了同一个事件被 Epoll 触发的次数，因此效率比LT模式高

Select、Poll和Epoll区别

1. 用户态将 fd 传入内核的方式
   • select：创建3个文件描述符集并拷贝到内核中，分别监听读、写、异常动作。这里受到单个进程可以打开的fd数量限制，默认是1024
   • poll：将传入的 pollfd 结构体数组拷贝到内核中进行监听
   • Epoll：执行 epoll_create 会在内核的高速cache区中建立一颗红黑树以及就绪链表。接着用户执行的 epoll_ctl 函数添加文件描述符会在红黑树上增加相应的结点
2. 内核态检测 fd 就绪状态的方式
   • select：轮询方式遍历所有 fd，最后返回一个 fd 是否就绪的mask掩码，根据这个掩码给 fd_set 赋值。
   • poll：轮询遍历每个 fd 状态，如果就绪则加入等待队列中。
   • Epoll：采用回调机制。在执行 epoll_ctl 的 ADD 操作时，不仅将文件描述符放到红黑树上，而且也注册了回调函数，内核在检测到 fd 就绪时会调用回调函数，该回调函数将文件描述符放在就绪链表中。
3. 将就绪 fd 传递给用户态的方式
   • select / poll：将之前传入的fd数组拷贝传出用户态并返回就绪的文件描述符总数，需要遍历判断
   • Epoll：epoll_wait将就绪链表的数据放入传入的数组中并返回数量，无需判断直接依次处理即可。并且返回文件描述符时使用 mmap() 内存映射避免了内核态到用户态之间的拷贝
4. 重复监听的处理方式
   • select / poll：将新的监听文件描述符集合 / 结构体数组拷贝传入内核中
   • Epoll：无需重新构建红黑树，直接沿用已存在的即可

其他问题

硬链接和软链接

inode：索引节点，和文件唯一对应，记录文件的属性，同时记录此文件的内容所在的 block 号码

dentry：目录项，存储文件的文件名与inode编号，通过读取目录项来判断文件是否存在于这个目录中

block：用来存储文件的内容，可能占用多个 block

• 硬链接：普通文件。就是在目录下创建一个目录项，记录文件名与 inode 编号，这个 inode 和源文件相同。删除一个条目后，只要剩余引用数量不为 0，文件就还存在。但是硬链接有限制，它不能跨越文件系统，也不能链接目录
• 软链接：符号链接文件。保存着源文件所在的绝对路径，在读取时会定位到源文件上，可以理解为快捷方式。因为记录的是路径，所以可以链接目录。但当源文件被删除时，链接文件就打不开了

键盘敲入字母时

1. 用户输入键盘字符后，键盘控制器就会产生扫描码数据并缓冲在其寄存器中，然后键盘控制器通过总线发送中断请求
2. CPU 收到中断请求后，保存中断进程的上下文，然后调用键盘的中断处理程序（键盘驱动程序初始化时注册的），从键盘控制器的寄存器的缓冲区读取扫描码，如果是显示字符如 ABC，则翻译成对应的 ASCII 码，放到读缓冲区队列
3. 若要显示至屏幕，显示设备的驱动程序会定时从读缓冲区队列读取数据放到写缓冲区队列，最后把数据写入到显示设备的控制器的寄存器数据缓冲区中，显示在屏幕里

零拷贝

一种 I/O 操作优化技术，是指 IO 操作时 CPU 不需要将数据从一个存储区复制到另一个存储区，从而可以减少上下文切换以及CPU的拷贝时间。在实现方式上，也并非完全不拷贝数据，而是减少用户/内核态的切换以及CPU拷贝的次数

以读SSD+写网卡为例，两种实现方式：
1. mmap+write：4次用户/内核态切换，2次DMA拷贝和1次CPU拷贝
借助虚拟内存可以把内核空间和用户空间的虚拟地址映射到同一个物理地址，因此 mmap 将 page cache 与用户空间的缓冲区映射到一起，只需从磁盘拷贝数据到内核缓冲区，省掉了向用户缓冲拷贝的过程，使得读操作 IO 都在内核中完成

2. sendfile：2次用户/内核态切换，2次DMA拷贝和1次CPU拷贝
在两个文件描述符之间传输数据，全程由内核操作的，彻底避免了数据从内核缓冲区和用户缓冲区之间的拷贝操作

mmap原理

1. 基本概念
mmap 可以将一个文件映射到进程的地址空间，实现文件磁盘地址和进程虚拟地址空间中一段虚拟地址的对映关系。这样进程就可以采用指针的方式读写操作这一段内存：读操作时可能引发缺页异常，会把文件内容拷贝到主存，写操作后系统会自动回写脏页面到对应的文件磁盘上，不必再调用read,write等系统调用函数。

2. 优点

1. 减少显式调用read/write的系统调用，且mmap直接返回指向page cache的指针，避免OS到用户空间的一次拷贝
2. 共享内存进程间通信。不管是父子进程还是无亲缘关系的进程，都可以将自身用户空间映射到同一个文件或匿名映射到同一片区域，从而达到进程间通信和进程间共享的目的。

3. 瓶颈

1. 当SSD带宽高，DBMS 管理的数据量大于内存空间时，OS的页驱逐机制多线程扩展性比较差（因为 SSD I/O 带宽大、访问速度快，页驱逐机制成了瓶颈）
2. mmap的cache命中率不如read，因为OS会自动剔除一些内存页，这样可能导致频繁的缺页中断。在命中cache时，mmap没有用户态到内核态切换，LRU的内核页面无法+1，热点数据更新掉了
   • 使用 mlock 锁hashtable，但一个进程能锁住的内存页数量有限制
   • 使用 madvise 的 MADV_SEQUENTIAL 标记，积极顺序预取

4. 细节

1. mmap映射区域大小必须是 4K 大小的整倍数，否则实际映射区域向上取整，padding 部分填充为0且无法写入
2. 映射的是磁盘地址和文件无关，只要映射范围的数据合法即可，和文件扩张/关闭没有直接联系

指令乱序

编译器：优化会将源代码中的一些指令顺序进行重排序，或者使用寄存器进行优化

处理器：CPU可能将没有数据依赖的指令执行顺序重排；现代 CPU 都是流水线结构，因此在 CPU 上多条指令并行执行，如果一个除法的指令占据了很久的除法器，可能下一条加法指令会更早执行完，导致代码执行后的内存顺序和我们预想的不一样。

内存屏障：编译器和CPU可以在保证输出结果一样的情况下对指令重排序，使性能得到优化。

• 阻止屏障两侧的指令重排序：插入一个内存屏障，相当于告诉CPU和编译器先于这个命令的必须先执行，后于这个命令的必须后执行
• 强制把写缓冲区/高速缓存中的脏数据等写回主存，让缓存中相应的数据失效