第三章 处理机的调度和死锁

3.1 处理机调度的基本概念 3.1高、中、低三级调度 1、高级调度（作业调度、长程调度、接纳调度） 将外存作业调入内存，创建PCB等，插入就绪队列。 一般用于批处理系统，分/实时系统一般直接入内存，无此环节。 调度特性 1.接纳作业数（内存驻留数） 太多―――> 周转时间T长 太少―――> 系统效率低 2.接纳策略：即采用何种调度算法：FCFS、短作业优先等

处理机调度的基本概念（2） 2、低级调度（进程调度，短程调度） 主要是由分派程序（Dispatcher）分派处理机。 1.非抢占方式： 简单，实时性差 (如win31) 2.抢占方式 （1）时间片原则 （2）优先权原则 （3）短作业优先原则。 3、中级调度（中程） 为提高系统吞吐量和内存利用率而引入的一内------外存对换功能（换出时，进程为挂起或就绪驻外状态） 运行频率：低>中>高。

问？ 三种调度被引发的事件？ 事件的表现方式？

3.1.2调度的队列模型 一、仅有进程调度的队列模型 时间片完 进程完成 交互用户 CPU 就绪队列 进程调度 事件出现 等待事件 阻塞队列

3.1.2调度的队列模型 二、具有高/低级模型 作业调度 时间片完 进程完成 CPU 后备队列 就绪队列 进程调度 等待事件1 事件1出现 阻塞队列 等待事件2 事件2出现 阻塞队列

三、具有三级调度 作业调度 时间片完 进程调度 进程完成 CPU 后备队列 就绪队列 中级调度 交互型作业 就绪、挂起队列 事件出现 阻塞、挂起队列 挂起 阻塞队列 等待事件

3.1.3选择调度方式和算法的若干准则 一、面向用户的准则 1．周转时间短（常用于批处理系统） 概念：作业从提交――> 完成的时间.分为： （1）驻外等待调度时间 （2）驻内等待调度时间 （3）执行时间 （4）阻塞时间

3.1.3选择调度方式和算法的若干准则 一、面向用户的准则 平均周转时间 平均带权 可见带权w越小越好,Ts为实际服务时间。

3.1.3选择调度方式和算法的若干准则 一、面向用户的准则 2．响应时间快：（对交互性作业） 概念：键盘提交请求到首次响应时间 （1）输入传送时间 （2）处理时间 （3）响应传送时间 3．截止时间的保证（特别于实时系统） 4．优先权准则：（即需要抢占调度）

3.1.3选择调度方式和算法的若干准则 二、面向系统的准则 1．吞吐量高（特别于批处理）：单位时间完成作业数 2．处理机利用率好：（因CPU贵，特别于大中型多用户系统） 3．各类资源的平衡利用。（？折算标准）

3.2调度算法——是一个资源分配问题 3.2.1先来先服务和短作业（进程）优先调度算法 1.FCFS 特点：简单，有利于长作业 即CPU繁忙性作业 2.短作业进程优先调度算法：SJ(P)F 提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量） 特点：对长作业不利，有可能得不到服务（饥饿） 估计时间不易确定

例 进程名 到达时间 服务时间 开始执行时间 完成时间 周转时间 带权周转时间 A 1 B 100 101 C 2 102 D 3 202 1 B 100 101 C 2 102 D 3 202 199 1.99

图3.4FCFS和SJF比较 进程名 A B C D E 平均 到达时间 0 1 2 3 4 服务时间 4 3 5 2 4 FCFS 0 1 2 3 4 服务时间 4 3 5 2 4 FCFS 完成时间 4 7 12 14 18 周转时间 4 6 10 11 14 9 带权周转时间 1 2 2 5.5 3.5 2.8 SJF 4 9 18 6 13 4 8 16 3 9 8 1 2.67 3.1 1.5 2.25 2.1

3.2.2高优先权优先调度算法 1.优先权调度算法类型 非抢占式优先权算法 抢占式优先权算法，实时性更好。 2.优先权类型： 1．静态优先权： 进程优先权在整个运行期不变。 确定优先权依据 （1）进程类型 （2）进程对资源的需求； （3）根据用户需求。 特点：简单，但低优先权作业可能长期不被调度。

3.2.2高优先权优先调度算法(2) 2．动态优先权： 如：优先权随执行时间而下降，随等待时间而升高。 响应比Rp=（等待时间＋服务时间）/服务时间 作为优先权 优点：长短兼顾 缺点：需计算Rp 3.高响应比优先算法： 特点： 响应比Rp=（tw+ts）/ts （1）短作业RP大。 （2）ts（要求服务时间）相同的进程间相当于FCFS。 （3）长作业等待一段时间仍能得到服务。

系统的处理能力：（应保证一个时间片处理完常用命令） 3.2.3基于时间片的轮转调度算法 1.时间片轮转 时间片大小的确定 太大：退化为FCFS； 太小：系统开销过大 系统对响应时间的要求；T=nq 就绪队列中进程的数目； 系统的处理能力：（应保证一个时间片处理完常用命令）

3.2.3基于时间片的轮转调度算法 2.多级反馈队列调度 特点：长、短作业兼顾，有较好的响应时间 （1）短作业一次完成； （2）中型作业周转时间不长； （3）大型作业不会长期不处理。

图3－5多级队列反馈调度算法 S1 至CPU 就绪队列1 S2 至CPU 就绪队列2 S3 至CPU 就绪队列3 Sn 至CPU 就绪队列n 时间片：S1<S2<S3

Ci为处理时间，Pi为周期时间（基于周期性实时任务） 3.3实时调度 3.3.1实现实时调度的基本条件 1．提供必要的调度信息 （1）就绪时间； （2）开始/完成截止时间； （3）处理时间； （4）资源要求； （5）优先级； 2．系统处理能力强 Ci为处理时间，Pi为周期时间（基于周期性实时任务）

3.3实时调度 3.3.1实现实时调度的基本条件 3.采用抢占调度方式 剥夺方式：一般都采用此 非剥夺方式（实现简单）：一般应使实时任务较小，以及时放弃CPU。 4.具有快速切换机制 具有快速响应外部中断能力。 快速任务分派

3.3.2实时调度算法的分类 1非抢占式调度算法 时间片轮转 秒级 非抢占优先权（协同） 秒~毫秒级 2抢占式调度算法 时钟中断抢占优先权 毫秒级 基于抢占点抢占 立即抢占immediate preemption 毫秒~微秒级 只要不在临界区即抢占（中断引发）

调度实时进程运行 实时进程要求调度 进程1 进程2 进程n 实时进程 调度时间 a 非抢占轮转调度 实时进程要求调度 当前进程运行完成 当前进程 实时进程 调度时间 b 非抢占优先权调度

实时进程要求调度 时钟中断到达时 当前进程 实时进程 调度时间 c 基于时钟中断抢占的优先权抢占调度 实时进程要求调度 抢占时刻（其它中断） 当前进程 实时进程 调度时间 b 立即抢占优先权调度

3.3.3常用的几种实时调度算法 1.最早截止时间优先EDF（earliest deadline first)算法 根据任务的截止时间来确定任务的优先级 截止时间越早，优先级越高 可以是抢占式或非抢占式

最早截止时间优先EDF例 1 3 4 2 开始截止时间 1 3 4 2 任务执行 t 任务到达 1 2 3 4 图3－7 EDF算法用于非抢占调度方式

2. 最低松弛度优先LLF算法 松弛度： 若A进程需在200ms时完成，其本身运行需要100ms，当前时刻是10ms，则A的松弛度为：200－100－10＝90 主要用于可抢占的调度方式中 例： A1 A2 A3 A4 A5 A6 A7 A8 t 20 40 60 80 100 120 140 160 B1 B2 B3 图3－8 A/B任务每次必须完成的时间

最低松弛度优先LLF算法(2) A1(10) A2(10) A3(10) A4(10) t1 t2 t3 t4 t5 t6 t7 t8 t 10 20 30 40 50 60 70 80 t1=0 B1(20) B1(5) B2(15) B2(10)

3.4多处理机系统中的调度 1.紧密耦合MPS和松弛耦合MPS 紧密耦合 松弛耦合 2.对称多处理器系统和非对称多处理器系统 共享RAM和I/O 高速总线和交叉开关连接 松弛耦合 独立RAM和I/O 通道和通信线路连接 2.对称多处理器系统和非对称多处理器系统 处理器是否结构相同

3.4.2进程分配方式 1.SMP中进程分配方式 静态分配 动态分配 2.非SMP中进程分配方式 进程调度在主处理器上执行 有潜在的不可靠性 可防止系统中多个处理器忙闲不均 2.非SMP中进程分配方式 进程调度在主处理器上执行 有潜在的不可靠性

3.4.3进程（线程）调度方式 1.自调度 各个处理机自行在就绪队列中取任务。 特点；简单，分布式调度，调度算法可采用前述方法，多个CPU利用率都不错（不会闲） 但： 瓶颈问题，（单队列） 低效性；（需拷贝现场） 线程切换频繁（当线程合作时,各线程并行的条件不容易满足）

2.成组调度 优点： （1）对相互合作的进（线）程组调度，可以减小切换，减小系统开销。 （2）每次分配一组CPU，减少了调度频率。 分配时间 （1）面向程序 （2）面向线程：使处理机利用率更高。

2.成组调度 应用程序A 应用程序B Cpu1 线程1 Cpu2 线程2 空闲 Cpu3 线程3 Cpu4 线程4 时间 1/2 应用程序A 4/5 1/5 浪费15% 浪费37.5%

3.专用处理机分配 引入：多处理机系统，每个处理已不再属宝贵资源。 特点：每个进（线）程专用处理机，使其切换小，提高效率。 主要用于大型计算，实时系统

3.5产生死锁的原因和必要条件 3.5.1产生死锁的原因。 一、竞争资源引起死锁。 1．可剥夺（CPU、内存，）和非剥夺性（打印机，磁带机）资源 2．竞争非剥夺性资源——可造成死锁 p1 R2 R1 p2

3.5产生死锁的原因和必要条件 3．竞争临时性资源 临时性资源是指由一个进程产生，被另一个进程使用一段时间后便无用的资源。

二、进程推进顺序不当引起死锁。 2 P2Rel(R1) P2Rel(R2) P2Req(R1) 1 D P2Req(R2) 3 4

3.5.2 产生死锁的必要条件 1．互斥条件（资源的临界性） 2．请求和保持条件 3．不剥夺条件 4．环路等待

3.5.3处理死锁的基本方法 1．预防；破坏4个条件之一：有效，使资源利用率低。 2．避免：防止进入不安全态。 3．检测：检测到死锁再清除。 4．解除：与“检”配套。

3.6 死锁预防和避免 3.6.1 死锁预防 一、互斥条件是资源固有属性，不能避免。 二、摒弃请求和保持条件 全分配，全释放（AND） 缺点：（1）延迟进程运行 （2）资源严重浪费 三、摒弃“不剥夺”条件 增加系统开销，且进程前段工作可能失效。

3.6 死锁预防和避免 3.6.1 死锁预防 四、摒弃“环路”条件 有序资源分配法：为资源编号，申请时需按编号进行。 缺点： （1）新增资源不便，（原序号已排定） （2）用户不自由 （3）资源与进程使用顺序不同造成浪费

3.6.2 系统的安全状态 在“避免死锁”方法中的判断条件 1. 安全状态 按某种顺序并发进程都能达到获得最大资源而顺序完成的序列为安全序列。 能找到安全序列的状态为安全状态。

3.6.2 系统的安全状态（2） 2.安全状态例 进程 最大需求 已分配 可用 P1 10 5 3 P2 4 2 P3 9

3.6.2 系统的安全状态（3） 3安全——不安全的转换 上例中，若P3再申请一台，则不安全 进程 最大需求 已分配 可用 P1 10 5 4 P3 9 3

3.6.3利用银行家算法避免死锁 1．数据结构 available[j]=k: 系统现有Rj类资源k个； max[i,j]=k: 进程i需要Rj的最大数k个； alloc[i,j]=k: 进程i已得到Rj类资源k个； need[i,j]=k: 进程i需要Rj类资源k个 有：need[i,j]= max[i,j]－alloc[i,j] requesti 进程i请求资源数 worki：进程i执行完后系统应有资源数（也即可用数） finish[i]：布尔量，表进程i能否顺序完成。

3.6.3利用银行家算法避免死锁 2．银行家算法 reqi<=needi error reqi<=availi block

3.6.3利用银行家算法避免死锁 avail=avail-reqi alloci=alloci+reqi needi=needi-reqi finish[i]=.F. needi<=work work=work+alloci finish[i]=.T.

4实例 Max A B C Allocation Need Available p0 7 5 3 0 1 0 7 4 3 3 3 2 (2 3 0) p1 3 2 2 2 0 0 (3 0 2) 1 2 2 (0 2 0) p2 9 0 2 3 0 2 6 0 0 p3 2 2 2 2 1 1 0 1 1 p4 4 3 3 0 0 2 4 3 1 T0时刻的资源分配表

4实例 Work A B C Need A B C Alloc Work+alloc Finish p1 3 3 2 1 2 2 2 0 0 5 3 2 true p3 5 3 2 0 1 1 2 1 1 7 4 3 p4 7 4 3 4 3 1 0 0 2 7 4 5 p2 7 4 5 6 0 0 3 0 2 10 4 7 p0 10 4 7 0 1 0 10 5 7 T0时刻的安全序列

4实例 Work A B C Need A B C Alloc Work+alloc Finish p1 2 3 0 0 2 0 3 0 2 5 3 2 true p3 5 3 2 0 1 1 2 1 1 7 4 3 p4 7 4 3 4 3 1 0 0 2 7 4 5 p0 7 4 5 0 1 0 7 5 5 p2 7 5 5 6 0 0 3 0 2 10 5 7 P1申请资源(1,0,2)时安全性检查(安全)

4实例 Allocation A B C Need Available p0 0 3 0 7 2 3 2 1 0 p1 3 0 2 0 2 0 p2 6 0 0 p3 2 1 1 0 1 1 p4 0 0 2 4 3 1 为P0分配（0，2，0）后的情况（不安全）

3.7死锁的检测和解除 3.7.1检测 1.资源分配图 p1 p2

3.7死锁的检测和解除 2.死锁定理 简化资源分配图 若能完全简化则消去所有的边。 定理：死锁状态的充分条件，资源分配图不可完全简化 3.检测死锁的算法：

3.7死锁的检测和解除 Work= available L:={Li| alloci=0 reqi=0} (孤立进程点) For all Li L do Begin For all reqi <=work do Work=work+alloci L=Li∪L end End Deadlock= ~(L={p1 … pn})

解除 检测到死锁后，回退到上一状态（要进行资源剥夺，且需保存以前状态的分配信息），重新分配，若不行，继续回退……，