【操作系统】进程的调度、僵尸进程/孤儿进程/守护进程
更多面试题总结请看：【面试题】技术面试题汇总
进程的状态
基本状态
进程的基本状态：“就绪”、“执行”、“阻塞”。
- 就绪：进程已获得除处理机以外的所需资源，等待分配处理机资源
- 执行：进程正在占用处理机资源执行
- 阻塞：进程等待某种条件，在条件满足之前无法执行。如发起了 I/O 系统调用，会被阻塞，等待 I/O 中断发生
挂起
“挂起”是指将暂不执行的进程换出到外存，节省内存空间。
“挂起”和“阻塞”都是进程暂停执行的状态，但是这是两个维度的概念：
- 阻塞表示进程正在等待一个事件的发生，阻塞状态下收到收到信号会切换为就绪状态
- 挂起表示进程被换出到外存，挂起状态下被激活时会被载入到内存，切换为非挂起状态
综上所属，挂起状态的进程按照是否阻塞可以分为：
- 挂起就绪状态：进程在外存中，但是只要被载入内存就可以执行
- 挂起阻塞状态：进程在外存中并等待一个事件，即使被载入内存（激活）也无法运行
图 1：进程的五状态图，包含“挂起”
睡眠
Linux 将进程的阻塞状态进一步细分为：暂停、浅睡眠、深睡眠。其中，若不需要等待资源，则切换为“暂停”；若需要等待资源，切换为“睡眠”；如果睡眠状态能被信号唤醒，则是“浅睡眠”，否则是“深睡眠”。
图 2：Linux 的进程状态图
调度算法
调度算法的分类
- 按照 CPU 的分配方式：非抢占式、抢占式
- 按照系统的分时方式：在批处理系统，交互系统或实时系统下的调度
饥饿问题
某个进程无限等待，无法被调度。
批处理系统的调度算法
调度算法的目标：
- 吞吐量（每小时最大作业数）：系统每小时完成的作业数，要尽可能多
- 周转时间（每作业最小时间）：一个作业从提交到完成时的统计平均时间
- CPU 利用率（CPU 始终忙碌）：由于没有交互，CPU 不会出现等待输入的情况，因此 CPU 利用率要高
先来先服务（First Come First Serverd，FCFS）
- 按照请求 CPU 的顺序使用 CPU，非抢占式
- 优点是易于理解，便于实现，只需一个就绪队列
- 缺点是对短作业不公平；对 I/O 密集型进程不利，长时间等待设备；响应时间不确定
最短作业优先（Shortest Job First，SJF）
- 预知作业的运行时间，选择最短时间的优先运行
- 优点是提高平均周转时间
- 缺点是对长作业不公平；可能导致饥饿问题
最短剩余时间优先（Shortest Remaining Time Next，SRTN）
- 最短作业优先的抢占式版本，如果新作业比正在执行的作业剩余时间短，则它优先执行
- 缺点是对长作业不公平；可能导致饥饿问题。同“最短作业优先”
最高响应比优先算法（Highest Response Ratio Next，HRRN）
- 响应比的定义：作业等待时间/作业运行所需时间
- 哪个进程的响应比大，哪个进程优先
- 由响应比的定义可以知道，作业运行所需时间越小、作业等待时间越长，响应比越大
- 优点：同时考虑了等待时间和执行时间，既优先考虑短作业，也防止长作业无限等待的饥饿
交互系统（分时系统）的调度算法
调度算法的目标：
- 响应时间：要快速响应交互请求
- CPU 的运行分为若干个时间片，能够处理不同的运算请求，使每个用户都能共享主机资源
时间片轮转（Round Robin，RR）
- 将所有就绪进程排成一个队列，按照时间片轮流调度，用完实践篇的进程排到队列末尾，属于抢占式
- 优点：没有饥饿问题
- 问题：若时间片小，进程切换频繁，吞吐量低；若时间片长，则响应时间过长，实时性得不到保证
优先级调度算法（Priority）
- 优先级高的进程先运行，同优先级的进程轮转。当高优先级队列中没有进程后，再调度下一级队列
- 缺点是可能导致低优先级进程饿死
引入动态设定优先级的思想：在优先级高的进程运行一个时间片后，降低其优先级，防止其一直占用 CPU，饿死优先级低的进程。结合这个思想，可设计出“多级反馈队列”。
多级反馈队列（Multilevel Feedback Queue，MFQ）
- 优先级高的队列先执行；优先级越高，时间片越短；如果一个进程在当前队列规定的时间片内无法执行完毕，则移动到下一个队列的队尾
- 缺点：也有可能出现饥饿问题，比如不断有新的更高优先级的进程加入
彩票法
- 向进程提供各种系统资源的彩票。调度时随机抽取彩票，拥有该彩票的进程得到资源
- 可给重要的进程更多的彩票；协作进程可以交换彩票
公平分享法
- 为每用户分配一定比例的 CPU 时间，而不是按照进程
- 各用户之间按照比例挑选进程
实时系统的调度算法
调度算法的目标：满足任务的截止时间。也就是说，如果有一个任务需要执行，实时操作系统会马上执行该任务，不会有较长的延时。
最早截止时间优先算法
先把截止时间早的任务给完成，否则这个任务如果在截止时间后才完成，就没有意义了。
僵尸进程、孤儿进程、守护进程
- 僵尸进程：停止运行
- 孤儿进程：正在运行
- 守护进程：正在运行
僵尸进程
当一个进程由于某种原因终止时，内核并不是立即把它从系统中清除。进程会保持在一种“已终止”的状态中，直到被它的父进程回收。当父进程回收已终止的子进程时，内核会抛弃已终止的进程，此时该进程就不存在了。
僵尸进程是指终止但还未被回收的进程。如果子进程退出，而父进程并没有调用 wait() 或 waitpid() 来回收，那么就会产生僵尸进程。僵尸进程是一个已经死亡的进程，但是其进程描述符仍然保存在系统的进程表中。
危害：占用进程号，系统所能使用的进程号是有限的，可能导致不能产生新的进程；占用一定的内存。
如何避免产生僵尸进程：
- 父进程调用
wait或者waitpid等待子进程结束 - 子进程结束时，内核会发生
SIGCHLD信号给父进程。父进程可以注册一个信号处理函数，在该函数中调用waitpid，等待所有结束的子进程；也可以用signal(SIGCLD, SIG_IGN)忽略SIGCHLD信号，那么子进程结束后，内核会进行回收 - 杀死父进程，僵尸进程就会变成孤儿进程，由 Init 进程接管并处理
《CSAPP》8.5.5 节提供了一个示例程序，在父进程中通过
SIGCHLD信号处理程序回收所有子进程。
孤儿进程
如果某个进程的父进程先结束了，那么它的子进程会成为孤儿进程每个进程结束的时候，系统都会扫描是否存在子进程，如果有则用 Init 进程（pid = 1）接管，并由 Init 进程调用 wait 等待其结束，完成状态收集工作。孤儿进程不会对系统造成危害。
守护进程
守护进程（英语：daemon，英语发音：/ˈdiːmən/或英语发音：/ˈdeɪmən/）是一种在后台执行的电脑程序。此类程序会被以进程的形式初始化。