操作系统漫游（三）处理机调度和死锁
在多道程序环境下，系统需要按照某种算法，动态地将处理机分配给处于就绪状态的一个进程。分配处理机的任务，就由处理机调度程序来完成。
调度的层次
高级调度
或者称长程调度或作业调度，在多道批处理系统中配置。分时、实时系统不需配置。
- 外存（后备队列） -> 内存（就绪队列）
低级调度
或者称短程调度或进程调度，在多道批处理、分时、实时系统中，都必须配置这级调度。
- 内存（就绪队列） -> 处理机
中级调度
或者称内存调度。目的是提高内存利用率和系统吞吐量。
- 内存（暂时不能允许的进程） -> 外存（swap分区）
作业调度算法
作业调度算法主要解决的是如何从外存后被队列中调入哪些进程到内存就绪队列中。
- 周转时间 = 完成时间 - 到达时间
- 带权周转时间 = 周转时间/服务时间
先来先服务（first-come first-served，FCFS）
- 从后备队列中选择几个最先进入该队列的作业，调入内存。
短作业优先（short job first, SJF）
- 作业越短，优先级越高。
优先级调度算法（priority-scheduling algorithm, PSA）
- 基于紧迫性。
高响应比优先调度算法（Hihest Response Ratio Next, HRRN）
- 即考虑作业的等待时间，又兼顾作业运行时间。这样，照顾了短作业又不至于让长作业等待时间过长。
其实现是为每个作业引入一个动态优先级，优先级随着等待时间延长而增加。
优先权 = （等待时间+要求服务时间） / 要求服务时间
进程调度算法
- 轮转调度算法（round robin, RR）：按照时间片
- 优先级调度算法：按照紧迫性
- 多队列调度算法
- 多级反馈队列的调度算法
- 基于公平原则的调度算法
实时调度算法
抢占式和非抢占式
最低松弛度优先（Least Laxity First）算法
松弛度 = 完成截止时间 - 运行时间 - 当前时刻
死锁
死锁指的是，两个或多个进程都持有一些资源，但又想申请对方拥有的资源，双方都希望对方释放出自己所需的资源，导致僵持的一种状态。
《计算机操作系统》（第四版）对死锁的定义是：
如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件，那么该组进程是死锁的（Deadlock）。
死锁的起因通常是进程推进顺序非法，导致多个进程对资源的争夺。（包括对不可抢占式资源和可消耗资源的争夺）
死锁的必要条件
- 互斥条件
- 请求和保持条件 （进程已经获得某个资源，又要申请另一资源）
- 不可抢占条件 （进程获得的资源在未使用完之前不能被其他进程抢占）
- 循环等待条件
死锁的检测
采用资源分配图简化算法。
资源分配图中，找出一个既不阻塞又非独立的进程结点Pi，在顺利的情况下，Pi可获得所需资源而继续运行，直至运行完毕，将所有请求边删去，成为孤立结点。Pi释放资源后，P(i+1)获得资源继续运行。以此类推，如果到最后所有的结点都成为孤立结点，那么该图是可完全化简的。不会导致死锁。
同样可以证明：
S为死锁的充分条件是，当且仅当S状态的资源分配图是不可完全化简的。（死锁定理）
处理死锁的方法
- 预防死锁
- 避免死锁
- 检测死锁
- 解除死锁
预防死锁的两种协议
- 协议一：进程一开始就一次性申请整个运行过程所需的全部资源。（会导致资源浪费）
- 协议二：申请 -> 释放 -> 申请 -> 释放
除了两种协议之外，还可以破坏“不可抢占”这个必要条件，例如，提出新的资源请求而不能得到满足时，必须释放已经保持的所有资源。
避免死锁
当系统处于安全状态时，就可以避免死锁。所谓安全状态，就是系统能按照某种进程推进顺序为每个进程分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。
可以用银行家算法来避免死锁。
当每一个进程在进入系统时，必须先申明运行过程中可能需要的每种资源类型的最大单元数目。当进程请求一组资源时，系统必须首先确定是否有足够的资源分配给它。若有，计算分配后是否会让系统处于不安全状态，如果不会，才将资源分配给它。