操作系统① —— 进程管理

1. 进程、线程、协程

进程：
- 是系统进行资源分配的基本单位
- 私有地址空间，私有栈、堆
- 上下⽂切换需要切换虚拟地址空间
线程：
- 是资源调度的基本单位
- 公有同⼀地址空间，公有堆、私有栈
- 上下⽂切换只需要切换少量寄存器
进程和线程的对比：
- 进程是系统进行资源分配的基本单位，线程是资源调度的基本单位
- 线程是进程的⼦任务，是进程内的执⾏单元。⼀个进程⾄少有⼀个线程，⼀个进程可以运⾏多个线程，这些线程共享同⼀块内存
协程：
- 是⽤户级的轻量线程
- 上下⽂切换由开发者决定，不由内核决定，类似于函数执⾏到⼀半，⼀会回来继续执⾏
为什么要有进程？
- 单道批处理系统只能串⾏，CPU利⽤率不⾼
- 多道批处理系统难以实现共享资源
- 进程实现了多个程序并发执行
为什么要有线程？
- 进程切换系统开销⼤，线程切换仅需保存和设置少量寄存器内容
- 适合⾼并发环境，线程成为并发执⾏的最⼩单元
- 节省空间：线程之间共享内存空间和资源，⽆序拷⻉
- 节省时间：进程切换需要切换虚拟内存，线程不需要
为什么要有协程？
- 线程是抢占式任务，由操作系统控制，不知道什么时候被抢⾛，需要加锁；
- 协程是异步机制，需要代码编写者主动让出控制权，不需要上下⽂切换
- 线程是同步机制，协程是异步机制

2. 什么是上下文切换？进程线程的上下文切换有什么区别？

上下文切换：从当前执⾏任务切换到另⼀个任务执⾏的过程；同时，为了确保下次能从正确的位置继续执⾏，在切换之前，会保存上⼀个任务的状态
进程线程上下文切换区别：
- 都是由操作系统内核完成（最显著的性能损耗：寄存器中的内容切换）
- 线程切换虚拟地址空间内存是相同的，进程切换的虚拟地址空间内存是不同的
- 进程：①切换⻚表以使⽤新的地址空间 ②切换内核栈和硬件上下⽂
- 线程：①切换内核栈和硬件上下⽂
为什么线程切换⽐进程切换快（为什么虚拟地址空间切换耗时）
- 把虚拟地址转换成物理地址需要查找⻚表，⻚表查找很慢，故⽤cache（TLB）缓存地址映射，可以加速
- 每个进程有⾃⼰的虚拟地址空间，每个进程有⾃⼰的⻚表，进程切换时候⻚表也要切换，⻚表切换TLB就失效了，cache命中率低，查找慢，程序运⾏慢

3. 进程状态切换

进程的3种基本状态：运⾏、就绪和阻塞。
- 就绪：当⼀个进程获得了除处理机以外的⼀切所需资源，⼀旦得到处理机即可运⾏，则称此进程处于就绪状态。就绪进程可以按多个优先级来划分队列。例如，当⼀个进程由于时间⽚⽤完⽽进⼊就绪状态时，排⼊低优先级队列；当进程由I/O操作完成⽽进⼊就绪状态时，排⼊⾼优先级队列。
- 运⾏：当⼀个进程在处理机上运⾏时，则称该进程处于运⾏状态。处于此状态的进程的数⽬⼩于等于处理器的数⽬，对于单处理机系统，处于运⾏状态的进程只有⼀个。在没有其他进程可以执⾏时（如所有进程都在阻塞状态），通常会⾃动执⾏系统的空闲进程。
- 阻塞：也称为等待或睡眠状态，⼀个进程正在等待某⼀事件发⽣（例如请求I/O⽽等待I/O完成等）⽽暂时停⽌运⾏，这时即使把处理机分配给进程也⽆法运⾏，故称该进程处于阻塞状态。
进程的五种状态
- 创建状态：进程在创建时需要申请⼀个空⽩PCB，向其中填写控制和管理进程的信息，完成资源分配。如果创建⼯作⽆法完成，⽐如资源⽆法满⾜，就⽆法被调度运⾏，把此时进程所处状态称为创建状态
- 就绪状态：进程已经准备好，已分配到所需资源，只要分配到CPU就能够⽴即运⾏
- 执⾏状态：进程处于就绪状态被调度后，进程进⼊执⾏状态
- 阻塞状态：正在执⾏的进程由于某些事件（I/O请求，申请缓存区失败）⽽暂时⽆法运⾏，进程受到阻塞。在满⾜请求时进⼊就绪状态等待系统调⽤
- 终⽌状态：进程结束，或出现错误，或被系统终⽌，进⼊终⽌状态。⽆法再执⾏

4. 进程切换场景

进程调度，时间⽚被耗尽，被系统挂起
系统资源不⾜，等到资源满⾜后再运⾏
通过睡眠函数 sleep() 主动挂起
有优先级更⾼的进程需要运⾏
发⽣硬件中断，当前进程被挂起

5. 进程间通信

进程的⽤⼾地址独⽴，不能互相访问，内核空间是共享的，进程之间通信必须通过内核
通信方式：
- 管道/匿名管道：
  - 管道（内核⾥⾯的⼀串缓存）
  - 单向、半双⼯
  - 只能在存在⽗⼦关系的进程
  - 缺点：效率低，容量有限
- 命名管道（FIFO）：
  - 半双⼯
  - 不相关的进程间也能相互通信
- 共享内存：
  - 就是映射⼀段能被其他进程所访问的内存，这段共享内存由⼀个进程创建，但多个进程都可以访问
  - 缺点：同时修改，存在冲突（线程安全）
  - 优点：速度快，因为是直接对内存进⾏存取（理论上效率最⾼）
- 信号量：
  - ⼀个整型计数器，实现进程间互斥和同步，P（-）V（+）操作，是原⼦操作
  - 信号量+共享内存通常组合使⽤
  - 缺点：不能传递复杂消息，只能同步
- 消息队列：
  - 消息链表
  - 容量有限、不适合⼤数据传输
- 信号
  - 通知某个事件已经发⽣
  - 唯⼀的异步通信机制
  - 常⽤信号（SIGCLD⼦进程退出、SIGKILL⽤⼾终⽌进程、SIGPIPE管道破裂信号）
- 套接字Socket：
  - 不同主机上的进程间通信
  - 缺点：速度慢
  - 优点：任何进程都能通信

6. 进程同步和进程互斥

7. 临界区的调度规则（如何解决临界区冲突）

⼀次仅允许⼀个进程进⼊（加锁）
其他试图进⼊的进程必须等待
已经进⼊临界区的进程要在有限时间内退出
如果不能进⼊临界区则应让出CPU，避免出现“忙等”现象
- 忙等：不断的测试循环代码中变量的值，占⽤处理机不释放

8. 进程内存布局

高地址向低地址：
- 栈区：编译器自动分配
- 内存映射区：动态链接库等⽂件映射、mmap申请⼤内存
- 堆区：程序员使⽤new、malloc申请，程序员不释放会由os释放
- BSS端：未初始化的全局变量
- 数据段：初始化的全局变量、静态数据
- 代码段：常量、⼆进制代码

9. 进程的调度算法

先来先服务：
- ⾮抢占式的调度算法，按照请求的顺序进⾏调度
- 有利于⻓作业，但不利于短作业
短作业优先：
- ⾮抢占式的调度算法，按估计运⾏时间最短的顺序进⾏调度
- ⻓作业有可能会饿死，处于⼀直等待短作业执⾏完毕的状态
最短剩余时间优先：
- 最短作业优先的抢占式版本，按剩余运⾏时间的顺序进⾏调度
- 当⼀个新的作业到达时，其整个运⾏时间与当前进程的剩余时间作⽐较。如果新的进程需要的时间更少，则挂起当前进程，运⾏新的进程。否则新的进程等待。
时间片轮转：
- 将所有就绪进程按 FCFS 的原则排成⼀个队列，每次调度时，把 CPU 时间分配给队⾸进程，该进程可以执⾏⼀个时间⽚。当时间⽚⽤完时，由计时器发出时钟中断，调度程序便停⽌该进程的执⾏，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队⾸的进程。
优先级调度：
- 为每个进程分配⼀个优先级，按优先级进⾏调度。为了防⽌低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。
高响应比优先：
- （等待时间 + 要求服务时间）/ 要求服务时间
多级队列：
- ⼀个进程需要执⾏ 100 个时间⽚，如果采⽤时间⽚轮转调度算法，那么需要交换 100 次。
- 多级队列是为这种需要连续执⾏多个时间⽚的进程考虑，它设置了多个队列，每个队列时间⽚⼤⼩都不同，例如1,2,4,8,…。进程在第⼀个队列没执⾏完，就会被移到下⼀个队列。这种⽅式下，之前的进程只需要交换 7 次。每个队列优先权也不同，最上⾯的优先权最⾼。因此只有上⼀个队列没有进程在排队，才能调度当前队列上的进程。
- 可以将这种调度算法看成是时间⽚轮转调度算法和优先级调度算法的结合。
CFS（完全公平调度）：
- 红⿊树，vruntime虚拟时间越⼩，越靠左，每次选最左边节点作为下⼀个任务O(1)
- vruntime += 实际运⾏时间* 1024 / 进程权重(权重根据nice值进⾏计算，任务分配的优先级)
- vruntime并不是⽆限⼩为0，每个CPU运⾏队列维护⼀个min_vruntime，新进程的vruntime以此为准
- CFS缺点：休眠进程在唤醒时候会获得vruntime的补偿；因此主动休眠进程并不要求快速相应，交互式进程要求（⿏标键盘啥的），主动休眠进程因为补偿⽽抢占了更重要的进程

10. 进程终止的方式（8种）

5种正常终止：
- 从mian返回
- 调用exit
- 调用_exit或_Exit
- 最后一个线程从其启动例程返回
- 最后一个线程调用pthread_exit
3种异常终止：
- 调用abort
- 接到一个信号并终止
- 最后一个线程对取消请求作出响应

11. 孤儿进程、僵尸进程、守护进程

⼀般情况下，⼦进程由⽗进程创建，但是⽗⼦进程的退出是⽆顺序的
孤⼉进程：⽗进程先退出，⼦进程还没有退出，托孤给init进程
僵⼫进程：⼦进程已经终⽌，⽗进程还没有调⽤wait、waitpid获取到其状态，⼦进程残留的状态信息变成僵⼫进程
- 如何避免僵尸进程：
  - 在fork后调用wait/waitpid函数取得子进程退出状态
  - 调用fork两次
    - 第一次调用产生一个子进程，第二次调用fork是在第一个子进程中调用，同时将父进程退出（第一个子进程退出），此时的第二个子进程的父进程id为init进程id
  - 在程序中显示忽略SIGCHLD信号
    - 子进程退出时会产生一个SIGCHLD信号，我们显示忽略此信号即可
  - 捕获SIGCHLD信号并在捕获程序中调用wait/waitpid函数
守护进程：运⾏在后台，不与任何终端关联的进程；通常情况系统启动时就在运⾏；通常是周期性的执⾏某些任务

12. 锁

两个基础的锁：
- 互斥锁：互斥锁是⼀种最常⻅的锁类型，⽤于实现互斥访问共享资源。在任何时刻，只有⼀个线程可以持有互斥锁，其他线程必须等待直到锁被释放。这确保了同⼀时间只有⼀个线程能够访问被保护的资源。
- ⾃旋锁：⾃旋锁是⼀种基于忙等待的锁，即线程在尝试获取锁时会不断轮询，直到锁被释放。
其他锁都是基于这两个锁：
- 读写锁：允许多个线程同时读共享资源，只允许⼀个线程进⾏写操作。分为读（共享）和写（排他）两种状态。
- 悲观锁：认为多线程同时修改共享资源的概率⽐较⾼，所以访问共享资源时候要上锁
- 乐观锁：先不管，修改了共享资源再说，如果出现同时修改的情况，再放弃本次操作

13. 死锁

多个进程在运⾏过程中因争夺资源⽽造成的⼀种僵局，占有⾃⾝资源并请求对⽅资源

产生死锁的原因：
- 资源分配不当，系统资源不⾜
- 程序推进的顺序不合适
产生死锁的必要条件：
- 互斥条件：⼀段时间内某资源仅为⼀个进程占⽤
- 请求和保持条件：对已获得的资源保持不放
- 不剥夺条件：获得之后不能被剥夺
- 环路等待条件：存在环形链
解决死锁的方法：
- 预防死锁
  - 破坏互斥条件没有实⽤价值
  - ⼀次性分配所有资源（破坏请求条件）
  - 有其中⼀个资源得不到，其他的也不给分配（破坏请保持条件）
  - 已经得到部分，但得不到其他，释放拥有的（破坏不可剥夺条件）
  - 给每类资源赋予⼀个编号，每⼀个进程按编号递增的顺序请求资源（破坏环路等待条件）
- 避免死锁
  - 在进⾏资源分配之前预先计算资源分配的安全性，如果会导致系统进⼊不安全的状态，则分配给进程
  - 解决：银⾏家算法
- 检测死锁
  - ⾸先为每个进程和每个资源指定⼀个唯⼀的号码
  - 然后建⽴资源分配图
  - 判断是否有环路
- 解除死锁
  - 剥夺资源/终⽌进程/撤销进程
  - 进程回退/回滚
- 鸵⻦策略
  - 原因：解决死锁的代价很⾼
  - ⽅法：影响不⼤，发⽣概率很低时候，假装根本没发⽣问题
  - Unix、Linux、Windos解决死锁的办法仅仅是忽略

14. 线程分类

⽤户级线程：有关线程管理的所有⼯作都由应⽤程序完成；不依赖操作系统，操作系统内核意识不到⽤⼾级线程的存在
内核级线程/轻量级线程：有关线程的所有⼯作都是由内核完成的；应⽤程序没有进程线程管理的代码，只有对接操作系统的API

15. 线程同步

线程同步是指两个或多个线程协同步调，按预期的顺序执行代码。
- 若两个或多个线程同时访问同一个共享资源时，需要让多个线程之间按照顺序访问。
- 若线程A的执行依赖线程B的结果，需要依赖线程同步来保证两个线程的执行的顺序。
互斥锁：互斥锁是最常⻅的线程同步机制。它允许只有⼀个线程同时访问被保护的临界区（共享资源）
条件变量：条件变量⽤于线程间通信，允许⼀个线程等待某个条件满⾜，⽽其他线程可以发出信号通知等待线程。通常与互斥锁⼀起使⽤。
读写锁：读写锁允许多个线程同时读取共享资源，但只允许⼀个线程写⼊资源。
信号量：⽤于控制多个线程对共享资源进⾏访问的⼯具。整数变量
⾃旋锁：上锁受阻的时候线程不阻塞，轮询查看是否获得了该锁

16. 线程间通信

若是两个进程间的两个线程通信，相当于进程间通信
若是一个进程中的两个线程通信，可直接通信；它们共享全局变量和内存，共享数据很容易也很方便，但会带来某些共享数据的互斥问题。
- 锁机制、信号量机制、条件变量等来解决

17. 线程资源回收与退出方法

线程可以简单地从启动历程中返回，返回值是线程的退出码
线程可以被同⼀进程中的其他线程所取消
线程调⽤pthread_exit

18. 生产者消费者模式（线程同步互斥问题）

基本思想：生产者负责生成数据并将其放入缓冲区，而消费者则从缓冲区中取出数据并进行处理。当缓冲区为空时，消费者需要等待生产者生成新的数据；当缓冲区已满时，生产者需要等待消费者取出数据。
生产者消费者模型是一种常见的多线程设计模式，它用于解决生产者和消费者之间的同步问题。由于生产者和消费者线程共享缓冲区，所以需要使用同步机制来确保线程安全。通常情况下，可以使用互斥锁来保护缓冲区，防止多个线程同时访问。此外，还可以使用条件变量来实现生产者和消费者之间的同步。
- 互斥锁：避免多个线程同时访问共享数据区而导致的竞态条件，使得所有线程独立。
- 条件变量：通过标记两种状态保证数据的安全性。
  - 当缓冲区已满时，生产者线程应该进入等待状态。此时，生产者线程可以使用条件变量来等待消费者从缓冲区中取出数据。
  - 当消费者从缓冲区中取出数据时，它会使用条件变量来通知生产者继续生产数据。
Blocking Queue常用于生产者消费者模型中，作为生产者和消费者之间的缓冲区，生产者向Blocking Queue中添加数据，消费者从Blocking Queue中取出数据：
- 当Blocking Queue已满时，生产者线程将会被阻塞；
- 当Blocking Queue为空时，消费者线程将会被阻塞。

19. CAS（Compare And Swap）

是一种无锁原子算法，映射到操作系统就是一条硬件汇编指令（保证原子性），其作用是让CPU将内存值更新为新值，但是有个条件，内存值必须与期望值相同，并且CAS操作无需用户态与内核态切换，直接在用户态对内存进行读写操作（意味着不会阻塞/线程上下文切换）。
简单说，CAS需要你额外给出一个期望值，也就是你认为这个变量现在应该是什么样子的，如果变量不是你想象的那样，说明它已经被别人修改过了，你只需要重新读取，设置新期望值，再次尝试修改就好了。
CAS如何保证原子性：
- 总线锁定
  - 总线锁定是指CPU使用了总线锁，所谓总线锁就是使用CPU提供的LOCK#信号，当CPU在总线上输出LOCK#信号时，其他CPU的总线请求将被阻塞。
  - 问题：总线锁定方式虽然保证了原子性，但是在锁定期间，会导致大量阻塞，增加系统的性能开销，所以现代CPU为了提升性能，通过锁定范围缩小的思想设计出了缓存行锁定
    - 缓存行是CPU高速缓存存储的最小单位
- 缓存锁定
  - 缓存锁定是指CPU对缓存行进行锁定，当缓存行中的共享变量回写到内存时，其他CPU会通过总线嗅探机制感知该共享变量是否发生变化，如果发生变化，让自己对应的共享变量缓存行失效，重新从内存读取最新的数据，缓存锁定是基于缓存一致性机制来实现的，因为缓存一致性机制会阻止两个以上CPU同时修改同一个共享变量
CAS的问题：
- 只能保证一个共享变量原子操作
  - CAS只能针对一个共享变量使用，如果多个共享变量就只能使用锁了
- 自旋时间太长
  - 当一个线程获取锁时失败，不进行阻塞挂起，而是间隔一段时间再次尝试获取，直到成功为止，这种循环获取的机制被称为自旋锁
  - 自旋锁好处：持有锁的线程在短时间内释放锁，那些等待竞争锁的线程就不需进入阻塞状态（无需线程上下文切换/无需用户态与内核态切换），它们只需要等一等（自旋），等到持有锁的线程释放锁之后即可获取，这样就避免了用户态和内核态的切换消耗。
  - 自旋锁坏处：线程在长时间内持有锁，等待竞争锁的线程一直自旋，即CPU一直空转，资源浪费在毫无意义的地方，所以一般会限制自旋次数。
- ABA问题
  - 假设有两个线程，线程1读取到内存值A，线程1时间片用完，切换到线程2，线程2也读取到了内存值A，并把它修改为B值，然后再把B值还原到A值，简单说，修改次序是A->B->A，接着线程1恢复运行，它发现内存值还是A，然后执行CAS操作
  - 要解决ABA问题也非常简单，只要追加版本号即可，每次改变时加1，即A -> B -> A，变成1A -> 2B -> 3A