第 7 讲 处理机调度 & 死锁问题 ¶
about 2673 words reading time 13 minutes
1. 处理机调度 ¶
在多道程序设计系统中，通常会有多个进程（或线程）竞争处理机资源，因此操作系统必须选择要运行哪一个进程（或线程
处理机调度的时机：
- 创建一个新进程之后。
- 当一个进程运行完毕，或由于某种错误而终止运行时。
- 当一个进程转入等待状态。
- I/O 中断发生时。
- 在每个时钟中断或者每 k 个时钟中断发生时。
上面的 2、3 两种情况下必须执行处理机调度程序。根据其他情况下是否执行调度程序，可以把调度的方式分为两类：抢先式、非抢先式。
非抢先式 (non_preemptive) 调度：调度程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或进程因等待某事件而阻塞时，才把处理机分配给另一个进程。实现简单，系统开销小，主要适用于批处理系统，不适用于分时系统和实时系统非抢先式 (non_preemptive) 调度。
抢先式 (preemptive) 调度：当进程正在处理机上运行时，调度程序可以根据规定的原则抢先分配给此进程的处理机，并将其移入就绪列队，选择其他进程运行。主要适用于分时系统和实时系统。
抢先原则有两种：优先级原则：高优先级进程可抢先低优先级进程。时间片原则：当运行进程的时间片用完后被抢先。
批处理系统中的调度 ¶
先来先服务 (FCFS，First Come First Served)，按进程的提交或变为就绪的先后顺序进行调度。实现简单、非抢先式。有利于长作业而不利于短作业。有利于 CPU 密集的作业而不利于 I/O 密集的作业。
最短作业优先 (SJF，Shortest Job First)，预计执行时间短的作业 ( 进程 ) 优先分派处理机。它的设计目标是减少进程的平均周转时间。对长作业不利。难于预计作业的执行时间。
最高响应比优先 (HRRN，Highest Response Ratio Next)，响应比公式： \(\text{ 响应比 }=1+\dfrac{\text{ 等待时间 }}{\text{ 要求服务时间 }}\) ，介于 FCFS 与 SJF 之间的折中算法，既考虑作业等待时间又考虑作业运行时间，既照顾短作业又不使长作业等待时间过长。
最短剩余时间 (SRT，shortest remaining time)，调度程序总是选择剩余时间最短的进程运行。如果新的进程比当前运行的进程需要更少的时间，当前进程将被抢先而运行新的进程。可使新的短作业获得良好的服务。
交互式系统中的调度 ¶
时间片轮转 (RR，round robin)，每个进程被分配一个时间段，称为时间片 (quantum)，即允许该进程运行的时间。如果在时间片结束时该进程还在运行，则将剥夺 CPU 并分配给另一个进程；如果该进程在时间片结束前阻塞或结束，则 CPU 立即进行切换。
调度程序需要维护一张可运行进程列表。同时，时间片长度不宜过短或者过长，通常将时间片长度设为 20ms～50ms 比较合理。
优先级调度 (Priority Scheduling)，每个进程被赋予一个优先级，允许优先级最高的可运行进程先运行。静态优先级：在进程创建时指定优先级，在进程运行时优先级不变。动态优先级：在进程创建时设置一个优先级，但在其生命周期内优先级可以动态变化，如等待时间长优先级可改升高。
多级反馈队列 (Multiple Feadback Queue)，为 CPU 密集型的进程设置较长的时间片比频繁地分给它们很短的时间片要高效，但是时间片过长又会影响到响应时间。解决方法：设立优先级类——高优先级的队列时间片短、低优先级的队列时间片长。
最短进程优先 (shortest process next)，最短作业优先的交互式版本。对于每个可运行的进程，可以根据过去的行为对其执行时间进行预测，并执行估计运行时间最短的那个进程。
保证调度 (guaranteed scheduling)，首先做出明确的性能保证，然后去实现它。例如，若有 n 个进程，则保证每个进程获得 1/n 的 CPU 处理时间。为实现保证，系统必须跟踪各个进程自创建以来已使用了多少 CPU 时间，然后计算各个进程应获得的 CPU 时间 ( 即自创建以来的时间除以 n)，并进而计算出实际获得的 CPU 时间与应获得的 CPU 时间之比，从中选择比例最低的进程。
彩票调度 (lottery scheduling)，向进程提供各种资源的彩票。一旦需要做出一项调度决策时，就随机抽出一张彩票，拥有彩票的进程将获得该资源。可以为更重要的进程额外的彩票，以增加它们获胜的机会。协作的进程可以交换彩票。
公平分享调度 (fair share scheduling)，到目前为止，所有调度算法都未考虑进程的拥有者。如果用户 1 启动 9 个进程，用户 2 启动 1 个进程，则用户 1 将得到 90% 的 CPU 时间。公平分享调度在调度前要考虑进程的拥有者这一因素。
实时系统中的调度 ¶
速率单调调度 (RMS，Rate Monotonic Scheduling)，RMS 为静态优先级调度算法：为每个进程分配一个与事件发生频率成正比的优先级。例如周期为 20ms 的进程优先级为 50，周期为 100ms 的进程优先级为 10。运行时调度程序总是调度优先级最高的就绪进程，必要时将抢先当前进程。
最早截止时限优先 (EDF，Earliest Deadline First)，一种动态优先级调度算法。当一个事件发生时，对应的进程被加到就绪队列，该队列按照截止时限排序。对于周期性事件，截止时限即为事件下一次发生的时间。调度程序总是选择截止时限最早的进程。
最小裕度优先 (LLF，least laxity first) 是一种动态优先级调度算法，它总是选择裕度最小的进程。裕度 (laxity) 指进程的富裕时间，也称为松弛度 (slack)。裕度 =( 截止时刻 - 当前时刻 )- 剩余运行时间。例如一个进程需要运行 100ms，它必须在 200ms 内完成，则在周期开始时刻执行其裕度为 100ms，在周期开始后 50ms 执行其裕度为 50ms。
2. 死锁问题 ¶
死锁 (Deadlock) 是指系统中多个进程无限制地等待永远不会发生的条件。
可抢占资源——指资源占有进程虽然需要使用该资源，但另一个进程却强行把资源从占有者进程处抢来。CPU、主存、硬盘，可为几个进程共同使用——可抢占。
不可抢占资源——指只有占用者进程不再需要使用该资源而主动释放资源外，其它进程不得在占有者进程使用资源过程中强行抢占。打印机、CD 刻录机，只可为某个进程独享——不可抢占。
永久资源：可重复使用的资源，例如所有的硬件资源和可再入的纯代码过程。
临时性资源：由一个进程产生，被另外一个进程使用短暂时间之后便无用的资源，如在进程同步和通信中出现的消息、信号和数据。
死锁问题产生的必要条件：
- 互斥：任一时刻只允许一个进程使用资源。
- 非抢占：进程已经占用的资源，不会被强制剥夺。
- 请求和保持：进程在请求其余资源时，不主动释放已经占用的资源。
- 环路等待：存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中的下一个进程所请求。
处理死锁问题的方法：
鸵鸟算法 (Ostrich algorithm)：忽略死锁问题，视而不见。原因：死锁问题的发生是小概率事件，且处理死锁问题的代价太高。UNIX、Linux 和 Windows 采用这方法。
死锁预防 (deadlock prevention)，破坏产生死锁的四个必要条件之一。例如：
- 破坏互斥条件：某些设备 ( 例如打印机 ) 可以假脱机操作，只有打印机守护程序使用打印机资源，但是所有的设备都可以进行假脱机操作。
- 破坏非抢占条件：通常不考虑。
- 破坏请求和保持条件：预先静态分配法：进程开始运行前一次分配所需全部资源，若系统不能满足，则进程阻塞，直到系统满足其要求——保证进程运行过程中不会再提出新的资源请求。改进措施：进程必须释放已分配的所有资源之后才能在需要时申请其他所需资源。
- 破坏环路等待条件：有序资源使用法：把资源分类按顺序排列，保证对资源的请求不形成环路。
死锁避免 (deadlock avoidance) 并不事先采取限制去破坏产生死锁的条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。优点：事先只需要较弱的限制条件，可获得较高的资源利用率和系统吞吐量。缺点：实现较难。
银行家问题。
死锁检测：主要检查系统中是否存在循环等待条件（允许前三个死锁必要条件存在