进程调度
进程调度是指计算机通过决策决定哪个就绪进程可以获得CPU使用权。前提是多道程序设计。
进程调度有两个步骤：
- 保留旧进程的运行信息，请出旧进程；
- 选择新进程，准备运行环境并分配CPU；
操作系统提供了三个机制来负责进程调度：
- 就绪队列的排队机制：
为了提高进程调度的效率，操作系统事先将就绪进程按照一定的方式排成队列，以便调度程序可以最快找到就绪进程。
- 选择运行进程的委派机制：
调度程序以一定的策略选择就绪进程，将CPU资源分配给它。
- 新老进程的上下文切换机制：
保存当前进程的上下文信息，装入被委派执行进程的运行上下文。
如果进程调度触发时，老进程还没有执行完毕的场景怎么办？为此有两种进程调度的方式：
- 非抢占式的调度：
处理器一旦分配给某个进程，就让该进程一直使用下去，调度程序不以任何原因抢占正在被使用的处理器。直到进程完成工作或因为IO阻塞才会让出处理器。
- 抢占式的调度：
允许调度程序以一定的策略暂停当前运行的进程，保存好旧进程的上下文信息，分配处理器给新进程。
| 抢占式调度 | 非抢占式调度 | |
|---|---|---|
| 系统开销 | 频繁切换，开销大 | 切换次数少，开销小 |
| 公平性 | 相对公平 | 不公平 |
| 应用 | 通用系统 | 专用系统 |
进程调度算法
- 先来先服务算法：
这个算法比较简单，在就绪队列中按照先来先服务的原则，优先取出队列最前面的就绪进程来调度，之后依次执行。
- 短进程优先调度算法：
调度程序优先选择就绪队列中估计运行时间最短的进程。短进程优先调度算法不利于长作业进程的执行。
- 高优先权优先调度算法：
进程附带优先权，调度程序优先选择权重高的进程。这个算法使得紧迫的任务可以优先处理。
系统中分为前台进程和后台进程，一般来说前台进程的优先级都比后台进程大，因为前台进程需要和用户交互，要保证用户使用时不会卡顿。
- 时间片轮转调度算法：
按照先来先服务的原则排列就绪队列，然后每次从队列头部取出待执行的进程，分配一个时间片执行，每个进程分配的时间片都是一样的。这是相对公平的调度算法，但是不能保证及时响应用户操作。
死锁
死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞现象。若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。
死锁的产生
第一个死锁产生的原因是资源竞争。当共享资源数量不满足各个进程需求时，各个进程之间就会因为共享资源的竞争而导致死锁。每个进程都在等待请求的资源被释放，但自身占用的资源又不会主动释放。如果此时增加多余的系统资源，死锁就会解开。
第二个原因是进程调度顺序不当。如下图，进程1和进程2都要申请打印机和传真机资源。如果调度的顺序是A->B->C->D，那么就会发生死锁。如果适当的改变调度顺序，改为A->D->B->C，那么就可以正常调度。
死锁产生的必要条件有四个，必须同时满足：
- 互斥条件：进程对资源的使用是排他性的使用。某个资源只能由一个进程使用，其他进程需要使用只能等待。
- 请求保持条件：进程至少保持一个资源，同时又提出新的资源请求。此时新资源被占用，请求被阻塞，但被阻塞的进程不释放自己保持的资源。
- 不可剥夺条件：进程获得的资源在未完成使用前不能被剥夺，获得的资源只能由进程自身释放。
- 环路等待条件：发生死锁时，必然存在“进程-资源”的环形等待链。
死锁的处理
预防死锁的方法
死锁产生的必要条件有四个，我们只需要破坏其中一个或多个即可预防死锁产生。互斥条件我们不能破坏，其余三个我们都有方法破坏：
- 摒弃请求保持条件：系统规定进程运行之前，一次性申请所有需要的资源。这样在进程运行期间不会再提出资源请求。
- 摒弃不可剥夺条件：当一个进程请求新的资源得不到满足时，必须释放占有的资源。
- 破坏环路等待条件：可用资源按照线性排列，申请必须按照需要递增申请，线性申请就不再形成环路。
银行家算法
以银行借贷系统分配策略为基础的算法，是一个可操作的著名的避免死锁的算法。客户申请的贷款是有限的，每次申请需声明最大资金量。银行在能够满足贷款时，都应该给用户贷款；客户在使用贷款后，能够及时归还贷款。
银行家算法需要有三个数据结构：已分配资源表、所需资源表、可分配资源表。如下图，表格中A、B、C、D四列表示可申请的四个共享资源，P1、P2、P3、P4是四个进程，第一张表内部的数字表示当前进程拥有的资源数量，第二张表内部的数字表示当前进程还需要资源的数量，第三张表内部数字表示当前系统还剩的资源数量。
当我们把所需资源表减去已分配资源表，就可以得到一张还需要分配的资源表:
此时我们把还需分配资源表中每个进程依次和可分配资源表比较，如果有一个进程当前满足运行条件，则直接把资源分配给它。等进程运行完毕归还资源后，重新再比较。
