第7讲 处理机调度&死锁问题⚓

1. 处理机调度⚓

在多道程序设计系统中，通常会有多个进程（或线程）竞争处理机资源，因此操作系统必须选择要运行哪一个进程（或线程），为其分配处理机，完成选择工作的操作系统代码称为调度程序(scheduler)。

处理机调度的时机：

1. 创建一个新进程之后。
2. 当一个进程运行完毕，或由于某种错误而终止运行时。
3. 当一个进程转入等待状态。
4. I/O 中断发生时。
5. 在每个时钟中断或者每 k 个时钟中断发生时。

上面的2、3两种情况下必须执行处理机调度程序。根据其他情况下是否执行调度程序，可以把调度的方式分为两类：抢先式、非抢先式。

1. 非抢先式(non-preemptive)调度：调度程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或进程因等待某事件而阻塞时，才把处理机分配给另一个进程。实现简单，系统开销小，主要适用于批处理系统，不适用于分时系统和实时系统非抢先式(non_preemptive)调度。
2. 抢先式(preemptive)调度：当进程正在处理机上运行时，调度程序可以根据规定的原则抢先分配给此进程的处理机，并将其移入就绪列队，选择其他进程运行。主要适用于分时系统和实时系统。抢先原则有2种：(1) 优先级原则：高优先级进程可抢先低优先级进程。(2) 时间片原则：当运行进程的时间片用完后被抢先。

调度的层次：

1. 长程调度：即作业调度，也称为宏观调度、高级调度。从用户工作流程的角度，一次提交的若干个流程，其中每个程序按照流程进行调度执行。时间尺度通常是分钟、小时。
2. 中程调度：即内外存交换，也称为中级调度。从存储器资源的角度看，将进程的部分或全部换出到外存上，将当前所需部分换入到内存。
3. 短程调度：即进程调度(线程调度)，也称为微观调度、低级调度。从 CPU 资源分配的角度看，CPU 要经常选择就绪进程或线程进入运行状态。时间尺度通常是毫秒级。因为执行频繁，要求在实现时达到高效率。

进程的行为：

1. CPU 繁忙：如代码中的运算语句、分支语句、循环语句等。
2. I/O 繁忙：如打开文件、读写文件、显示、网络通信等。

调度算法的目标：

1. 批处理系统：吞吐量（每小时最大作业数），周转时间，CPU 利用率。
2. 交互式系统：响应时间。
3. 实时系统：保证截止时间，避免丢失数据、发生灾难。

调度算法的评价指标：

1. 周转时间：作业从提交到完成所用的时间。包括就绪队列中等待时间、CPU 执行时间和 I/O 时间。由此定义平均周转时间。
2. 等待时间：作业在就绪队列中等待 CPU 分配的时间。
3. 响应时间：交互式系统中，从用户提交请求到系统首次响应的时间。

1.1 批处理系统中的调度⚓

先来先服务(FCFS, First Come First Served)

按进程的提交或变为就绪的先后顺序进行调度。

实现简单、非抢先式。有利于长作业而不利于短作业。有利于 CPU 密集的作业而不利于 I/O 密集的作业。

最短作业优先(SJF, Shortest Job First)

预计执行时间短的作业(进程)优先分配处理机。每当有新作业到达或有作业执行结束，就选择当前队列中预计执行时间最短的作业运行。

目标是减少进程的平均周转时间。对长作业不利。难于预计作业的执行时间。

最高响应比优先(HRRN, Highest Response Ratio Next)

响应比公式：“响应比=1+等待时间/要求服务时间”。

介于 FCFS 与 SJF 之间的折中算法，既考虑作业等待时间又考虑作业运行时间，既照顾短作业又不使长作业等待时间过长。

最短剩余时间(SRT, Shortest Remaining Time)

调度程序总是选择剩余时间最短的进程运行。如果新的进程比当前运行的进程需要更少的时间，当前进程将被抢先而运行新的进程。是最短作业优先算法 SJF 的抢占式版本。

可使新的短作业获得良好的服务。

1.2 交互式系统中的调度⚓

时间片轮转(RR, round robin)

每个进程被分配一个时间段，称为时间片(quantum)，即允许该进程运行的时间。如果在时间片结束时该进程还在运行，则将剥夺CPU并分配给另一个进程；如果该进程在时间片结束前阻塞或结束，则 CPU 立即进行切换。

调度程序需要维护一张可运行进程列表。同时，时间片长度不宜过短或者过长，通常将时间片长度设为 20ms～50ms 比较合理。

特点：简单、公平；隐含所有进程同等重要的假设。

优先级调度(Priority Scheduling)

每个进程被赋予一个优先级，允许优先级最高的可运行进程先运行。

静态优先级：在进程创建时指定优先级，在进程运行时优先级不变。动态优先级：在进程创建时设置一个优先级，但在其生命周期内优先级可以动态变化，如等待时间长优先级可改升高。

对于动态优先级：I/O 密集型的进程需要 CPU 时，应立即分配给它 CPU，以便启动下一个 I/O 请求，这样就可以在另一个进程计算的同时执行 I/O 操作。使 I/O 密集型进程获得较好服务的简单算法：将其优先级设为 1/f，f 为该进程在上一时间片中计算时间所占的比重。

特点：可以方便地将一组进程按优先级分成若干类，在各类间采用优先级调度，各类内部采用时间片轮转调度。

多级反馈队列(Multiple Feadback Queue)

为 CPU 密集型的进程设置较长的时间片比频繁地分给它们很短的时间片要高效，但是时间片过长又会影响到响应时间。

解决方法：设立优先级类——高优先级的队列时间片短、低优先级的队列时间片长。

最短进程优先(shortest process next)

最短作业优先的交互式版本。对于每个可运行的进程，可以根据过去的行为对其执行时间进行预测，并执行估计运行时间最短的那个进程。

假设某终端上的一条命令估计运行时间为 T0，当前实际测量值为 T1，则新的估计时间为“aT0+(1-a)T1”。这种通过当前测量值和先前估计值进行加权平均而得到下一个估计值的技术称为老化(aging)。

保证调度(guaranteed scheduling)

首先做出明确的性能保证，然后去实现它。例如，若有 n 个进程，则保证每个进程获得 1/n 的 CPU 处理时间。为实现保证，系统必须跟踪各个进程自创建以来已使用了多少 CPU 时间，然后计算各个进程应获得的 CPU 时间(即自创建以来的时间除以 n)，并进而计算出实际获得的 CPU 时间与应获得的 CPU 时间之比，从中选择比例最低的进程。

彩票调度(lottery scheduling)

向进程提供各种资源的彩票。一旦需要做出一项调度决策时，就随机抽出一张彩票，拥有彩票的进程将获得该资源。可以为更重要的进程额外的彩票，以增加它们获胜的机会。协作的进程可以交换彩票。

公平分享调度(fair share scheduling)

到目前为止，所有调度算法都未考虑进程的拥有者。如果用户1启动9个进程，用户2启动1个进程，则用户1将得到90%的 CPU 时间。公平分享调度在调度前要考虑进程的拥有者这一因素。

1.3 实时系统中的调度⚓

实时系统是时间起主导作用的系统。外设给计算机一个请求，计算机必须在一个确定的时间范围内恰当地做出反应。在实时系统中，迟到的响应即使正确，也和没有响应一样糟糕。实时系统可以分为硬实时（必须满足绝对的截止时间）和软实时系统（偶尔超过时间限制可以容忍）。

实时系统中的事件可以按响应方式分为周期性事件（以规则的时间间隔发生）和非周期性事件（发生时间不可预知）。

如果有 m 个周期性事件，事件 i 以周期 \(P_i\) 发生，并且需要 \(C_i\) 秒的 CPU 时间处理，那么在单处理机系统中可以处理负载的条件为 \(\displaystyle\sum_{i=1}^m \dfrac{C_i}{P_i}\) ，满足该条件的实时系统称为是可调度的。

速率单调调度(RMS, Rate Monotonic Scheduling)

一种静态优先级调度算法。为每个进程分配一个与事件发生频率成正比的优先级。例如周期为20ms的进程优先级为50，周期为100ms的进程优先级为10。运行时调度程序总是调度优先级最高的就绪进程，必要时将抢先当前进程。

最早截止时限优先(EDF, Earliest Deadline First)

一种动态优先级调度算法。当一个事件发生时，对应的进程被加到就绪队列，该队列按照截止时限排序。对于周期性事件，截止时限即为事件下一次发生的时间。调度程序总是选择截止时限最早的进程。

最小裕度优先(LLF, least laxity first)

一种动态优先级调度算法，总是选择裕度最小的进程。

裕度(laxity)指进程的富裕时间，也称为松弛度(slack)。裕度=(截止时刻-当前时刻)-剩余运行时间。

例如一个进程需要运行100ms，它必须在200ms内完成，则在周期开始时刻执行其裕度为100ms，在周期开始后50ms执行其裕度为50ms。

2. 死锁问题⚓

死锁(Deadlock)是指系统中多个进程无限制地等待永远不会发生的条件。

产生死锁的原因：

1. 竞争资源：当系统中供多个进程所共享的资源，不足以同时满足它们的需要时，引起它们对资源的竞争而产生死锁。
2. 进程推进的顺序不当：进程在运行过程中，请求和释放资源的顺序不当，导致进程的死锁。

资源的分类：

1. 可抢占资源：指资源占有进程虽然需要使用该资源，但另一个进程却强行把资源从占有者进程处抢来。CPU、主存、硬盘可为几个进程共同使用。
2. 不可抢占资源：指只有占用者进程不再需要使用该资源而主动释放资源外，其它进程不得在占有者进程使用资源过程中强行抢占。打印机、CD 刻录机，只可为某个进程独享。
3. 永久资源：可重复使用的资源，例如所有的硬件资源和可再入的纯代码过程。
4. 临时性资源：由一个进程产生，被另外一个进程使用短暂时间之后便无用的资源，如在进程同步和通信中出现的消息、信号和数据。

死锁问题产生的必要条件：

1. 互斥：任一时刻只允许一个进程使用资源。
2. 非抢占：进程已经占用的资源，不会被强制剥夺。
3. 请求和保持：进程在请求其余资源时，不主动释放已经占用的资源。
4. 环路等待：存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中的下一个进程所请求。

处理死锁问题的方法：

(1) 鸵鸟算法(Ostrich algorithm)，忽略死锁问题，视而不见。原因：死锁问题的发生是小概率事件，且处理死锁问题的代价太高。UNIX、Linux 和 Windows 采用此方法。

(2) 死锁预防(deadlock prevention)，破坏产生死锁的四个必要条件之一。例如：

1. 破坏互斥条件：某些设备(例如打印机)可以假脱机操作，只有打印机守护程序使用打印机资源，但是所有的设备都可以进行假脱机操作。
2. 破坏非抢占条件：通常不考虑。
3. 破坏请求和保持条件：预先静态分配法：进程开始运行前一次分配所需全部资源，若系统不能满足，则进程阻塞，直到系统满足其要求——保证进程运行过程中不会再提出新的资源请求。改进措施：进程必须释放已分配的所有资源之后才能在需要时申请其他所需资源。
4. 破坏环路等待条件：有序资源使用法：把资源分类按顺序排列，保证对资源的请求不形成环路。

(3) 死锁避免(deadlock avoidance)，并不事先采取限制去破坏产生死锁的条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。优点：事先只需要较弱的限制条件，可获得较高的资源利用率和系统吞吐量。缺点：实现较难。

(4) 死锁检测，主要检查系统中是否存在循环等待条件（允许前三个死锁必要条件存在），一旦发现这种环路便认定死锁存在，并识别出该环路所涉及的有关进程，以供系统采取适当的措施来解除死锁。最常用的是一种基于资源分配图(RAG)和死锁定理的检测死锁算法。

死锁解除。发现进程死锁时，从死锁中解脱出来的最常用的方法有两种：

1. 剥夺资源法：从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态。
2. 撤消进程法：撤消全部死锁进程，或是按照某种顺序逐个地撤消进程，直至有足够的资源可用，死锁状态消除为止。

银行家算法问题⚓

关键变量：可用资源 Available，已分配资源 Allocation，最大需求 Maximum，需求 Need，进程的资源分配请求 Request。其中 Need = Maximum - Allocation。

在系统运行过程中，对进程提出的每一个（系统能够满足的）资源申请进行动态检查（安全性检查），并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。

安全状态：存在某种资源调度顺序（安全序列），保证所有进程正常运行完成。不安全状态：不存在可满足所有进程正常运行的资源调度顺序。虽然并非所有不安全状态都是死锁状态，但当系统进入不安全状态后，便有可能进入死锁状态；反之只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质是如何使系统不进入不安全状态。

优点：

1. 银行家算法允许死锁必要条件中的互斥条件、请求和保持和非剥夺条件存在，比起预防死锁的几种方法来说，限制条件放松，资源利用程度提高。
2. 由于系统可以满足、也可以拒绝进程提出的资源请求，当一个进程的资源要求将导致不安全状态时，系统就拒绝其要求，直到该资源要求不会导致不安全状态时，才满足此进程的资源要求(这主要由于其它进程释放出了资源)，这样系统总是处于安全状态。

缺点：

1. 要求被分配的每类资源的数量是固定不变的，难以做到，因为资源本身需要维护，可能损坏。
2. 要求用户数也保持固定不变，在多道程序系统中难以做到，用户数是经常变化的(尤其在分时环境中)。

Comments