3.1 处理机调度的层次和调度算法的目标

处理机调度的层次 ★

高级调度/作业调度/长程调度

调度对象是作业。

用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，排在就绪队列上。

批处理操作系统中的高级调度。分时系统和实时系统一般不需要高级调度。

低级调度/进程调度/短程调度

调度对象是进程。

决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。

短程调度程序是操作系统最为核心的部分，短程调度策略的优劣直接影响到整个系统的性能

中级调度/内存调度

主要目的是为了提高内存利用率和系统吞吐量。

将处于外存交换区中的就绪状态或等待状态的进程调入内存，或把处于内存就绪状态或内存等待状态的进程交换到外存交换区中。

实际上就是存储器管理中的对换功能。

处理机调度的层次

在三种调度中，进程调度的运行频率最高，作业调度的周期较长，中级调度的运行频率在上述两者之间。

调度队列模型

仅有进程调度的调度队列模型：

具有高级和低级调度的调度队列模型：

同时具有三级调度的调度队列模型：

处理机调度算法的目标

共同目标

• 资源利用率

CPU的利用率 = CPU有效工作时间 / (CPU有效工作时间 + CPU空闲等待时间)

• 公平性
• 平衡性
• 策略强制执行

批处理系统的目标

• 平均周转时间短

周转时间：从作业被提交给系统开始，到作业完成为止。

平均周转时间：

带权周转时间：作业的周转时间T与系统为它提供服务的时间T_S之比，即W=T/T_S。

平均带权周转时间：

• 系统吞吐量高

吞吐量：单位时间内完成的作业数，与作业的平均长度具有密切关系。

• 处理机利用率高

分时系统的目标

• 响应时间快

响应时间：从用户通过键盘提交一个请求开始至系统首次产生响应为止。

• 均衡性

实时系统的目标

• 截止时间的保证

截止时间：某任务开始执行的最迟时间，或必须完成的最迟时间。

• 可预测性

3.2 作业与作业调度

批处理系统中的作业

作业：通常的程序+数据+作业说明书。

作业步：每一个步骤。

作业控制块 JCB：作业标识+用户名称+用户账号+作业类型+作业状态+调度信息+资源需求+资源使用情况+……。管理和调度作业。

作业运行的三个阶段（三种状态）：

• 收容阶段（后备状态）
• 运行阶段（运行状态）
• 完成阶段（完成状态）

作业调度算法

执行作业调度时，需要解决：

• 一次接纳多少作业，即允许多少个作业同时在内存中运行。
• 接纳哪些作业，即哪些作业调入内存，取决于所采用的算法。比如先来先服务调度算法；或者是短作业优先调度算法；还有基于作业优先权的调度算法，响应比高者优先调度算法等。

① 先来先服务调度算法（FCFS）

可用于作业调度和进程调度。

按照作业（进程）进入后备队列（就绪队列）的先后次序来挑选作业（进程），先进入先被挑选。

算法容易实现，效率不高，只顾及作业（进程）等候时间，没考虑作业（进程）要求服务时间的长短。

有利于长作业（进程），不利于短作业（进程）。有利于CPU繁忙型作业，不利于I/O繁忙型作业。

② 短作业优先调度算法 (SJF) / 短进程优先调度算法 (SPF)

短作业优先（SJF）：从后备队列中选择估计运行时间最短的作业，调入内存运行。

短进程优先（SPF）：从就绪队列中选出估计运行时间最短的进程，将处理机分配给它，使它立即执行。 直到运行完成进程才会让出处理机--非抢占式。

优点：

• 降低作业的平均等待时间，提高系统吞吐量。

缺点：

• 对长作业不利，有可能长期不被调度；
• 完全没考虑作业的紧迫程度（某些特殊的）；
• 用户做出的估计时间带有很大的主观性。

③ 高优先权优先调度算法(FPF) / 高响应比优先级调度算法 (HRRN) ★

高优先权优先调度算法(FPF)

作为作业调度算法时，系统将从后备队列中选择若干个优先权最高的作业装入内存。

作为进程调度算法时，该算法把处理机分配给就绪队列中优先权最高的进程。

• 非抢占式优先权算法
• 抢占式优先权调度算法

高响应比优先级调度算法 (HRRN)

• 优先权的变化规律可描述为：
• 由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为：

每当要进行调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。

既照顾了短作业，又考虑了作业到达的先后顺序，还不会使长作业长期得不到服务。

该调度算法改进了FCFS和SJF算法的缺点。

3.3 进程调度

进程调度的任务、机制和方式

进程调度的任务

• 保存处理机的现场信息
• 按某种算法选取进程
• 把处理器分配给进程

进程调度机制

排队器：将就绪进程插入到相应的就绪队列中。

分派器：依据进程调度程序所选定的进程，将其从就绪队列中取出。

上下文切换器：保存当前进程的上下文；新选进出的CPU现场信息恢复。

进程调度的方式 ★

非抢占方式

一旦把处理机分配给某个进程后，让该进程一直执行，直到该进程完成或者发生某事件而阻塞。

引起进程调度的因素：

• 正在执行的进程执行完毕
• 执行中的进程因为提出I/O请求而暂停执行
• 进程通信或同步过程中执行了原语操作

优点：实现简单、系统开销小，适用于大多数的批处理系统环境。

缺点：难以满足紧急任务的要求，不适宜要求比较严格的实时系统。

抢占方式

允许调度程序根据某种原则，暂停正在执行的进程，将处理机重新分配给其他进程。

抢占原则：

• 优先权原则：允许优先权高的新到进程抢占当前进程的处理机
• 短进程优先原则
• 时间片原则

轮转调度算法

原理：将CPU的处理时间分成固定大小的时间片，系统将所有就绪进程按先来先服务的原则排成队列。每次调度时，把CPU 分配给队首进程，令其执行一个时间片，时间片用完后，若进程未结束，则重新排入就绪队列尾部。

• 可以保证就绪队列中所有进程在一给定时间内，均能获得一时间片的处理机执行时间。
• 系统能在给定的时间内响应所有的用户。
• 在轮转法中，时间片长度的选取非常重要，时间片长度的选择会直接影响系统开销和响应时间。

根据FCFS，使用轮转法处理，让每一个就绪队列上的进程每次运行一个时间片（若就绪队列上有n个进程，每个进程每次大约获得1/n的处理机时间）。

时间片的确定：略大于一次典型交互所需时间。

优先级调度算法

优先级调度算法的类型

• 非抢占式优先级调度算法
• 抢占式优先级调度算法

优先权的类型

静态优先权

静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。

确定进程优先权的依据有如下三个方面：

• 进程类型
• 进程对资源的需求
• 用户要求

动态优先权

动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。

进程优先权改变原因：

• 进程等待时间
• 进程占用CPU时间

多级反馈队列调度算法 ▽

1. 设置多个就绪队列，并为各个队列赋予不同的优先级，优先级越高的队列中，为每个进程所规定的执行时间片就越小
2. 新进程进入内存后，放入第一队列末尾，按FCFS原则等待调度，如果在一个时间片结束时没完成，将该进程转入第二队列末尾重新等待调度执行……
3. 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行
4. 如果处理机正在为某队列的进程服务，又有新进程插入到较高优先级的队列中，则新进程将抢占正在运行进程的处理机

多级反馈队列调度算法性能：

• 较好的性能，能够照顾到用户的利益
• 短作业、长作业都能得到比较满意的处理

3.4 实时调度 ▽

实现实时调度的基本条件

1 提供必要的调度信息

• 就绪时间
• 开始截止时间和完成截止时间
• 处理时间
• 资源要求
• 优先级

2 系统处理能力强

假定系统中有m个周期性的硬实时任务，它们的处理时间可表示为Ci，周期时间表示为Pi，则在单处理机情况下，必须满足下面的限制条件：，系统才是可调度的。

3 采用抢占调度方式

在含有硬实时任务的系统中，广泛采用抢占调度方式；一些小的实时系统，可采用非抢占调度机制。

4 具有快速切换机制

对外部中断的快速响应能力

快速的任务分派能力

实时调度算法的分类（非抢占式和抢占式）

非抢占式轮转调度算法：可用于要求不太严格的实时控制系统中。

非抢占的优先级调度算法：可用于有一定要求的实时控制系统中。

基于时钟中断的抢占式优先权调度算法：可用于大多数的实时系统中。

立即抢占的优先权调度算法：能获得非常快的响应。

最早截止时间优先EDF算法

最早截止时间优先EDF（earliest deadline first）调度算法：根据任务的截止时间确定优先级，截止时间愈早的优先级愈高，具有最早截止时间的任务排队列首，优先分配处理机。

• 根据开始截止时间来确定任务的优先级
• 截止时间早的排在就绪队列前面
• 总是选择就绪队列中的第一个任务
• 可用于抢占式调度和非抢占式调度

最低松弛度优先LLF算法

最低松弛度优先LLF（least laxity first）调度算法：根据任务的紧急（松弛）程度，紧急程度愈高的优先级愈高，优先执行处理。

• 根据任务紧急（或松弛）的程度来确定优先级
• 紧急程度愈高（松弛程度愈低）优先级愈高，愈先执行
• 主要用于抢占式调度

松弛度 = 必须完成时间 - 其本身的运行时间 - 当前时间

一任务在400 ms时必须完成，它本身需要运行 150 ms，则其松弛程度为 250 ms。

优先级倒置 ▲

如何解决优先级倒置现象：

• 进程进入临界区后所占用的处理机不允许被抢占。
• 动态优先级继承。

3.5 死锁概述 ★

所谓死锁是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，他们都将无法再向前推进。

资源分类

分类标准一：

• 可重用性资源：IO设备、打印机等
• 可消耗性资源（临时资源）：进程间通信的消息等

分类标准二：

• 可抢占性资源（可剥夺资源）：CPU、内存
• 不可抢占性资源（非可剥夺资源）：磁带机、打印机

产生死锁的原因

• 竞争不可抢占性资源引起进程死锁
• 竞争可消耗资源引起进程死锁
• 进程推进顺序不当引起死锁
• PV操作使用不当产生死锁

死锁的定义

如果一组进程中的‘每一个进程’都在等待仅由该组进程中的‘其它进程’才能引发的‘事件’，那么该组进程是死锁的（Deadlock）。

死锁的必要条件

（缺一不可）

互斥条件：进程分配到的资源互斥性使用，资源只能被一个进程占用，其他请求该资源的进程只能等到被用完释放。

请求和保持条件：进程已占有某资源，又提出新资源请求，而该资源被占，则进程请求被阻塞，已得资源保持。

不可抢占条件：进程已得资源不可被抢占。

循环等待条件：存在一个进程的资源循环链

死锁的处理方法

预防死锁：通过设置某些限制条件来破坏产生死锁的四个必要条件中的一个或几个，来预防发生死锁

避免死锁：在动态分配资源的过程中，用某种方法防止系统进入不安全状态，从而避免发生死锁

检测死锁：通过设置检测机制，及时检测出死锁的发生，确定有关的进程和资源

解除死锁：与检测死锁配套使用，常用的方法是撤销或挂起一些进程，收回资源，分配给处于阻塞状态的进程，使之转为就绪状态，可以继续运行

3.6 预防死锁 ★

预防死锁的方法：破坏死锁四个必要条件。

互斥条件是非共享设备所必须的——主要破坏其他三个条件。

破坏“请求和保持”条件

第一种协议：资源静态分配法

• 一个进程必须在执行前就申请它所要的全部资源，并且直到它所要的资源都得到满足后才开始执行

第二种协议：资源静态分配法

• 允许进程只获得运行初期所需的资源，便开始运行。这些资源使用完毕并全部释放，再申请新的所需资源。

破坏“不可抢占”条件

采用剥夺控制

• 当进程在申请资源未获准许时,先主动释放已占有的资源,然后才去等待，以后再一起向系统提出申请
• 一般只适用于可剥夺性资源，如CPU、存储区

破坏“循环等待”条件

资源顺序分配法

• 对系统的全部资源编号，并规定进程申请资源时只能按升序进行

3.7 避免死锁 ★

系统安全状态

安全状态是指系统能按某种顺序为每个进程分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。

安全序列：进程安全执行完的顺序。

如果系统无法找到这样一个安全序列，则称系统处于不安全状态。

• 并非所有的不安全状态都导致死锁，但当系统进入不安全状态后，便可能进而进入死锁状态。
• 只要系统处于安全状态，便可避免进入死锁状态。
• 避免死锁的本质在于：当进行资源分配时，如何避免进入不安全状态。

利用银行家算法避免死锁 ★★★

银行家算法

银行家拥有一笔周转资金，客户要求分期贷款，如果客户能够得到各期贷款，就一定能够归还贷款，否则就一定不能归还贷款，银行家应谨慎的贷款，防止出现坏帐。

利用银行家算法来避免死锁

操作系统（银行家）

操作系统管理的资源(周转资金)

进程（要求贷款的客户）

银行家算法中的数据结构

可利用资源向量Available。 m个元素的数组，Available[j]=K表示系统中现有Rj类资源K个。

最大需求矩阵Max。 n×m的矩阵，Max[i,j]=K表示进程i需要Rj类资源的最大数目为K。

分配矩阵Allocation。 n×m的矩阵，Allocation[i,j]=K表示进程i当前已分得Rj类资源的数目为K。

需求矩阵Need。 n×m的矩阵，Need[i,j]=K表示进程i还需要Rj类资源K个，方能完成其任务。

银行家算法

1. 如果Requesti[j]≤Need[i,j]，便转向步骤2；否则认为出错。
2. 如果Requesti[j]≤Available[j]，便转向步骤3；否则， 表示尚无足够资源，Pi须等待。
3. 系统试探着把资源分配给进程Pi，并执行： Available[j]=Available[j]-Requesti[j]; Allocation[i,j]=Allocation[i,j]+Requesti[j]; Need[i,j]=Need[i,j]-Requesti[j];
4. 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

安全性算法

1. 设置工作向量Work和布尔型向量Finish ，并初始化: Work=Available; Finish[i]=false;
2. 寻找能满足下述条件的进程： ①Finish[i]=false; ② Need[i,j]≤Work[j]; 若找到，执行3，否则，执行4。
3. 执行： Work[j]=Work[i]+Allocation[i,j]; Finish[i]=true; go to step 2;
4. 如果所有进程的Finish[i]=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。

银行家算法的优缺点

优点：资源利用率比静态资源分配法高，又避免死锁。

缺点：对资源分配过于保守；计算太多，并且需知道对资源的最大需求量，不太实际。

3.8 死锁的检测与解除 ▽

解决死锁问题的一条途径是死锁检测和解除，这种方法对资源的分配不加任何限制，也不采取死锁避免措施，但系统定时地运行一个“死锁检测”程序，判断系统内是否已出现死锁，如果检测到系统已发性了死锁，再采取措施解除它。

死锁的检测

资源分配图

(1)如果资源分配图中无环路，则此时系统没有发生死锁。

(2)如果资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生了死锁，此时，环路是系统发生死锁的充要条件，环路中的进程便为死锁进程。

(3)如果资源分配图中有环路，且涉及的资源类中有多个资源，则环路的存在只是产生死锁的必要条件而不是充分条件。

死锁定理

如果能在资源分配图中消去此进程的所有请求边和分配边，成为孤立结点。经一系列简化，使所有进程成为孤立结点，则该图是可完全简化的；否则则称该图是不可完全简化的。

系统为死锁状态的充分条件是：当且仅当该状态的资源分配图是不可完全简化的。该充分条件称为死锁定理。

死锁的解除

抢占资源

从其它进程抢占足够数量的资源给死锁进程，解除死锁状态。

撤销进程

最简单撤消进程的方法是使全部死锁的进程夭折掉；但以前工作全部作废,损失可能很大。

另一方法是按照某种顺序逐个地撤消进程，直至有足够的资源可用，死锁状态消除为止。