计算机操作系统之处理机调度与死锁

1、2007年1月 西华大学数学与计算机学院 蒋明礼2007年1月 3.1 处理机调度的基本概念 3.13.1高、中、低三级调度高、中、低三级调度 1 1、高级调度（作业调度、长程调度、接纳调度）、高级调度（作业调度、长程调度、接纳调度） 将外存作业调入内存，创建将外存作业调入内存，创建PCBPCB等，插入就绪队列。等，插入就绪队列。 一般用于批处理系统，分一般用于批处理系统，分/ /实时系统一般直接入内存，无此实时系统一般直接入内存，无此 环节。环节。 调度特性调度特性 1.1.接纳作业数（内存驻留数）接纳作业数（内存驻留数） 太多太多周转时间周转时间T T长长 太少太少系统效率低系统效率低 2

2、.2.接纳策略：即采用何种调度算法：接纳策略：即采用何种调度算法：FCFSFCFS、短作业优先等、短作业优先等 西华大学数学与计算机学院 蒋明礼2007年1月 处理机调度的基本概念（2） 2 2、低级调度（进程调度，短程调度）、低级调度（进程调度，短程调度） 主要是由分派程序（主要是由分派程序（DispatcherDispatcher）分派处理机。）分派处理机。 1.1.非抢占方式：非抢占方式： 简单，实时性差简单，实时性差 ( (如如win31)win31) 2. 2.抢占方式抢占方式 （1 1）时间片原则）时间片原则 （2 2）优先权原则）优先权原则 （3 3）短作业优先原则。）短作业优先

3、原则。 运行频率：低运行频率：低 中中 高高。 西华大学数学与计算机学院 蒋明礼2007年1月 问？ 三种调度被引发的事件？三种调度被引发的事件？ 事件的表现方式？事件的表现方式？ 西华大学数学与计算机学院 蒋明礼2007年1月 3.1.2调度的队列模型 一、仅有进程调度的队列模型一、仅有进程调度的队列模型 就绪队列就绪队列CPU 阻塞队列阻塞队列 交互用户交互用户 时间片完时间片完 进程调度进程调度 进程完成进程完成 等待事件等待事件 事件出现事件出现 西华大学数学与计算机学院 蒋明礼2007年1月 3.1.2调度的队列模型 二、具有高二、具有高/ /低级模型低级模型 进程进程 完成完成后备

4、队列后备队列 作业调度作业调度 就绪队列就绪队列CPU 阻塞队列阻塞队列 时间片完时间片完 进程调度进程调度 等待事件等待事件1 事件事件1出现出现 阻塞队列阻塞队列 等待事件等待事件2 事件事件2出现出现 西华大学数学与计算机学院 蒋明礼2007年1月 三、具有三级调度 后备队列后备队列就绪队列就绪队列CPU 就绪、挂起队列就绪、挂起队列 时间片完时间片完 进程调度进程调度进程进程 完成完成 阻塞、挂起队列阻塞、挂起队列 事件出现事件出现 作业调度作业调度 阻塞队列阻塞队列 等待事件等待事件 挂起挂起 事件出现事件出现 中级调度中级调度 交互型作业交互型作业 西华大学数学与计算机学院 蒋明礼

5、2007年1月 3.1.3选择调度方式和算法的若干准则 一、面向用户的准则一、面向用户的准则 1 1周转时间短（常用于批处理系统）周转时间短（常用于批处理系统） 概念：作业从提交概念：作业从提交 完成的时间完成的时间. . 分为：分为： （1 1）驻外等待调度时间）驻外等待调度时间 （2 2）驻内等待调度时间）驻内等待调度时间 （3 3）执行时间）执行时间 （4 4）阻塞时间）阻塞时间 西华大学数学与计算机学院 蒋明礼2007年1月 一、面向用户的准则一、面向用户的准则 平均周转时间平均周转时间 平均带权平均带权 可见带权可见带权w w越小越好越小越好,Ts,Ts为实际服务时间。为实际服务时间

6、。 3.1.3选择调度方式和算法的若干准则 1 1 n i i T n T 1 1 n i s i T T n W 西华大学数学与计算机学院 蒋明礼2007年1月 一、面向用户的准则一、面向用户的准则 2 2响应时间快：（对交互性作业）响应时间快：（对交互性作业） 概念：键盘提交请求到首次响应时间概念：键盘提交请求到首次响应时间 （1 1）输入传送时间）输入传送时间 （2 2）处理时间）处理时间 （3 3）响应传送时间）响应传送时间 3 3截止时间的保证（特别于实时系统）截止时间的保证（特别于实时系统） 4 4优先权准则：（即需要抢占调度）优先权准则：（即需要抢占调度） 3.1.3选择调度方式

7、和算法的若干准则 西华大学数学与计算机学院 蒋明礼2007年1月 二、面向系统的准则二、面向系统的准则 1 1吞吐量高（特别于批处理）：单位时间完成吞吐量高（特别于批处理）：单位时间完成 作业数作业数 2 2处理机利用率好：（因处理机利用率好：（因CPUCPU贵，特别于大中贵，特别于大中 型多用户系统）型多用户系统） 3 3各类资源的平衡利用。（？折算标准）各类资源的平衡利用。（？折算标准） 3.1.3选择调度方式和算法的若干准则 西华大学数学与计算机学院 蒋明礼2007年1月 3.2调度算法是一个资源分配问题 3.2.13.2.1先来先服务和短作业（进程）优先调先来先服务和短作业（进程）优先

8、调 度算法度算法 1.FCFS1.FCFS 特点：简单，有利于长作业特点：简单，有利于长作业 即即CPUCPU繁忙性作业繁忙性作业 2.2.短作业进程优先调度算法：短作业进程优先调度算法：SJ(P)FSJ(P)F 提高了平均周转时间和平均带权周转时间提高了平均周转时间和平均带权周转时间 （从而提高了系统吞吐量）（从而提高了系统吞吐量） 特点：对长作业不利，有可能得不到服务特点：对长作业不利，有可能得不到服务 （饥饿）（饥饿） 估计时间不易确定估计时间不易确定 西华大学数学与计算机学院 蒋明礼2007年1月 例 进程 名 到达 时间 服务 时间 开始 执行 时间 完成 时间 周转 时间 带权 周

9、转 时间 A010111 B110011011001 C21101102100100 D31001022021991.99 西华大学数学与计算机学院 蒋明礼2007年1月 图3.4FCFS和SJF比较 进程名进程名 A B C D E平均平均 到达时间到达时间 0 1 2 3 4 服务时间服务时间 4 3 5 2 4 FCFS完成时间完成时间 4 7 12 14 18 周转时间周转时间 4 6 10 11 149 带权周转时间带权周转时间 1 2 2 5.5 3.52.8 SJF完成时间完成时间 4 9 18 6 13 周转时间周转时间 4 8 16 3 98 带权周转时间带权周转时间 1 2

10、.67 3.1 1.5 2.252.1 西华大学数学与计算机学院 蒋明礼2007年1月 3.2.2高优先权优先调度算法 1.1.优先权调度算法类型优先权调度算法类型 非抢占式优先权算法非抢占式优先权算法 抢占式优先权算法，实时性更好。抢占式优先权算法，实时性更好。 2.2.优先权类型：优先权类型： 1 1静态优先权：静态优先权： 进程优先权在整个运行期不变。进程优先权在整个运行期不变。 确定优先权依据确定优先权依据 （1 1）进程类型）进程类型 （2 2）进程对资源的需求；）进程对资源的需求； （3 3）根据用户需求。）根据用户需求。 特点：简单，但低优先权作业可能长期不被调特点：简单，但低优

11、先权作业可能长期不被调 度。度。 西华大学数学与计算机学院 蒋明礼2007年1月 3.2.2高优先权优先调度算法(2) 2 2动态优先权：动态优先权： 如：优先权随执行时间而下降，随等待时间而升高。如：优先权随执行时间而下降，随等待时间而升高。 响应比响应比RpRp= =（等待时间服务时间）（等待时间服务时间）/ /服务时间服务时间 作为优先权作为优先权 优点：长短兼顾优点：长短兼顾 缺点：需计算缺点：需计算RpRp 3.3.高响应比优先算法：高响应比优先算法： 特点：特点： 响应比响应比RpRp= =（tw+tstw+ts）/ /tsts （1 1）短作业）短作业R RP P大。大。 （2

12、2）tsts（要求服务时间）相同的进程间相当于（要求服务时间）相同的进程间相当于FCFSFCFS。 （3 3）长作业等待一段时间仍能得到服务。）长作业等待一段时间仍能得到服务。 西华大学数学与计算机学院 蒋明礼2007年1月 3.2.3基于时间片的轮转调度算法 1.1.时间片轮转时间片轮转 时间片大小的确定时间片大小的确定 太大：退化为太大：退化为FCFSFCFS； 太小：系统开销过大太小：系统开销过大 系统对响应时间的要求；系统对响应时间的要求；T=T=nqnq 就绪队列中进程的数目；就绪队列中进程的数目； 系统的处理能力：（应保证一个时间片处理完常用系统的处理能力：（应保证一个时间片处理完

13、常用 命令）命令） 西华大学数学与计算机学院 蒋明礼2007年1月 3.2.3基于时间片的轮转调度算法 2.2.多级反馈队列调度多级反馈队列调度 特点：长、短作业兼顾，有较好的响应时间特点：长、短作业兼顾，有较好的响应时间 （1 1）短作业一次完成；）短作业一次完成； （2 2）中型作业周转时间不长；）中型作业周转时间不长； （3 3）大型作业不会长期不处理。）大型作业不会长期不处理。 西华大学数学与计算机学院 蒋明礼2007年1月 就绪队列就绪队列1 1 至至CPU S1 就绪队列就绪队列2 2 S2 至至CPU 就绪队列就绪队列3 3 S3 至至CPU 就绪队列就绪队列n n Sn 至至C

14、PU 时间片：时间片：S1S2S3 图图35多级队列反馈调度算法多级队列反馈调度算法 西华大学数学与计算机学院 蒋明礼2007年1月 3 3.3.1.3.1实现实时调度的基本条件实现实时调度的基本条件 1 1提供必要的调度信息提供必要的调度信息 （1 1）就绪时间；）就绪时间； （2 2）开始）开始/ /完成截止时间；完成截止时间； （3 3）处理时间；）处理时间； （4 4）资源要求；）资源要求； （5 5）优先级；）优先级； 2 2系统处理能力强系统处理能力强 3.3实时调度 N P C P C m i i i m i i i 11 1 Ci为处理时间，为处理时间，Pi为周期时间（基于周期

15、性实时任务）为周期时间（基于周期性实时任务） 西华大学数学与计算机学院 蒋明礼2007年1月 3 3.3.1.3.1实现实时调度的基本条件实现实时调度的基本条件 3.3.采用抢占调度方式采用抢占调度方式 剥夺方式：一般都采用此剥夺方式：一般都采用此 非剥夺方式（实现简单）：一般应使实时任务非剥夺方式（实现简单）：一般应使实时任务 较小，以及时放弃较小，以及时放弃CPUCPU。 4.4.具有快速切换机制具有快速切换机制 具有快速响应外部中断能力。具有快速响应外部中断能力。 快速任务分派快速任务分派 3.3实时调度 西华大学数学与计算机学院 蒋明礼2007年1月 3.3.2实时调度算法的分类 1

16、1、非抢占式调度算法、非抢占式调度算法 时间片轮转时间片轮转 秒级秒级 非抢占优先权（协同）非抢占优先权（协同） 秒毫秒级秒毫秒级 2 2、抢占式调度算法、抢占式调度算法 时钟中断抢占优先权时钟中断抢占优先权 毫秒级毫秒级 基于抢占点抢占基于抢占点抢占 立即抢占立即抢占immediate preemption immediate preemption 毫秒微秒级毫秒微秒级 只要不在临界区即抢占（中断引发）只要不在临界区即抢占（中断引发） 2007年1月 进程1进程2进程n实时进程 调度时间调度时间 实时进程要求调度实时进程要求调度 调度实时进程运行调度实时进程运行 a 非抢占轮转调度非抢占轮转

17、调度 当前进程实时进程 实时进程要求调度实时进程要求调度当前进程运行完成当前进程运行完成 b 非抢占优先权调度非抢占优先权调度 调度时间调度时间 2007年1月 c 基于时钟中断抢占的优先权抢占调度基于时钟中断抢占的优先权抢占调度 当前进程实时进程 实时进程要求调度实时进程要求调度抢占时刻（其它中断）抢占时刻（其它中断） b 立即抢占优先权调度立即抢占优先权调度 当前进程实时进程 实时进程要求调度实时进程要求调度时钟中断到达时时钟中断到达时 调度时间调度时间 调度时间调度时间 西华大学数学与计算机学院 蒋明礼2007年1月 3.3.3常用的几种实时调度算法 1.1.最早截止时间优先最早截止时间

18、优先EDFEDF（earliest deadline earliest deadline first)first)算法算法 根据任务的截止时间来确定任务的优先级根据任务的截止时间来确定任务的优先级 截止时间越早，优先级越高截止时间越早，优先级越高 可以是抢占式或非抢占式可以是抢占式或非抢占式 西华大学数学与计算机学院 蒋明礼2007年1月 最早截止时间优先EDF例 1342 134 2 12 34 t 开始截止时间开始截止时间 任务到达任务到达 任务执行任务执行 图图37 EDF算法用于非抢占调度方式算法用于非抢占调度方式 西华大学数学与计算机学院 蒋明礼2007年1月 2. 最低松弛度优先L

19、LF算法 松弛度：松弛度： 若若A A进程进程需在需在200ms200ms时完成，其本身运行需要时完成，其本身运行需要100ms100ms， 当前时刻是当前时刻是10ms10ms，则，则A A的松弛度为：的松弛度为：2002001001001010 9090 主要用于可抢占的调度方式中主要用于可抢占的调度方式中 例：例： A1A2A3A4A5A6A7A8 B1B2B3 020 406080 100120 140160 t 图图38 A/B任务每次必须完成的时间任务每次必须完成的时间 西华大学数学与计算机学院 蒋明礼2007年1月 最低松弛度优先LLF算法(2) A1(10) A2(10)A3(

20、10)A4(10) t 01020304050607080 t1=0 B1(20)B1(5)B2(15)B2(10) t1t2t3t4t5t6t7t8 西华大学数学与计算机学院 蒋明礼2007年1月 3.4多处理机系统中的调度 1.1.紧密耦合紧密耦合MPSMPS和松弛耦合和松弛耦合MPSMPS 紧密耦合紧密耦合 共享共享RAMRAM和和I/OI/O 高速总线和交叉开关连接高速总线和交叉开关连接 松弛耦合松弛耦合 独立独立RAMRAM和和I/OI/O 通道和通信线路连接通道和通信线路连接 2.2.对称多处理器系统和非对称多处理对称多处理器系统和非对称多处理 器系统器系统 处理器是否结构相同处理

21、器是否结构相同 西华大学数学与计算机学院 蒋明礼2007年1月 3.4.2进程分配方式 1.1.SMPSMP中进程分配方式中进程分配方式 静态分配静态分配 动态分配动态分配 可防止系统中多个处理器忙闲不均可防止系统中多个处理器忙闲不均 2.2.非非SMPSMP中进程分配方式中进程分配方式 进程调度在主处理器上执行进程调度在主处理器上执行 有潜在的不可靠性有潜在的不可靠性 西华大学数学与计算机学院 蒋明礼2007年1月 3.4.3进程（线程）调度方式 1.1.自调度自调度 各个处理机自行在就绪队列中取任务。各个处理机自行在就绪队列中取任务。 特点；简单，分布式调度，调度算法可采用前述方特点；简单

22、，分布式调度，调度算法可采用前述方 法，多个法，多个CPUCPU利用率都不错（不会闲）利用率都不错（不会闲） 但：但： 瓶颈问题，（单队列）瓶颈问题，（单队列） 低效性；（需拷贝现场）低效性；（需拷贝现场） 1.1.线程切换频繁（当线程合作时线程切换频繁（当线程合作时, ,各线程并行各线程并行 的条件不容易满足）的条件不容易满足） 西华大学数学与计算机学院 蒋明礼2007年1月 2.成组调度 优点：优点： （1 1）对相互合作的进（线）程组调度，可）对相互合作的进（线）程组调度，可 以减小切换，减小系统开销。以减小切换，减小系统开销。 （2 2）每次分配一组）每次分配一组CPUCPU，减少了调

23、度频率。，减少了调度频率。 分配时间分配时间 （1 1）面向程序）面向程序 （2 2）面向线程：使处理机利用率更高。）面向线程：使处理机利用率更高。 西华大学数学与计算机学院 蒋明礼2007年1月 2.成组调度 应用程序应用程序A应用程序应用程序 B Cpu1线程线程1线程线程1 Cpu2线程线程2空闲空闲 Cpu3线程线程3空闲空闲 Cpu4线程线程4空闲空闲 时间时间1/21/2 浪费浪费37.5% 应用程序应用程序 A 应用程序应用程序 B Cpu1线程线程1线程线程1 Cpu2线程线程2空闲空闲 Cpu3线程线程3空闲空闲 Cpu4线程线程4空闲空闲 时间时间4/51/5 浪费浪费15

24、% 西华大学数学与计算机学院 蒋明礼2007年1月 3.专用处理机分配 引入：多处理机系统，每个处理已不再属宝贵引入：多处理机系统，每个处理已不再属宝贵 资源。资源。 特点：每个进（线）程专用处理机，使其切换特点：每个进（线）程专用处理机，使其切换 小，提高效率。小，提高效率。 主要用于大型计算，实时系统主要用于大型计算，实时系统 西华大学数学与计算机学院 蒋明礼2007年1月 3.5产生死锁的原因和必要条件 3.5.13.5.1产生死锁的原因。产生死锁的原因。 一、竞争资源引起死锁。一、竞争资源引起死锁。 1 1可剥夺（可剥夺（CPUCPU、内存，）和非剥夺性（打印机，、内存，）和非剥夺性（

25、打印机， 磁带机）资源磁带机）资源 2 2竞争非剥夺性资源竞争非剥夺性资源可造成死锁可造成死锁 p1 p2 R1 R2 西华大学数学与计算机学院 蒋明礼2007年1月 3.5产生死锁的原因和必要条件 3 3竞争临时性资源竞争临时性资源 临时性资源是指由一个进程产生，被另一个进程临时性资源是指由一个进程产生，被另一个进程 使用一段时间后便无用的资源。使用一段时间后便无用的资源。 西华大学数学与计算机学院 蒋明礼2007年1月 二、进程推进顺序不当引起死锁。 2 1 3 D P2Req(R2) P2Req(R1) P1Req(R1) P1Req(R2) P2Rel(R2) P2Rel(R1) P1

26、Rel(R1) P1Rel(R2) 4 西华大学数学与计算机学院 蒋明礼2007年1月 3.5.2 产生死锁的必要条件 1 1互斥条件（资源的临界性）互斥条件（资源的临界性） 2 2请求和保持条件请求和保持条件 3 3不剥夺条件不剥夺条件 4 4环路等待环路等待 西华大学数学与计算机学院 蒋明礼2007年1月 3.5.3处理死锁的基本方法 1 1预防；破坏预防；破坏4 4个条件之一：有效，个条件之一：有效， 使资源利用率低。使资源利用率低。 2 2避免：防止进入不安全态。避免：防止进入不安全态。 3 3检测：检测到死锁再清除。检测：检测到死锁再清除。 4 4解除：与解除：与“检检”配套。配套。

27、 西华大学数学与计算机学院 蒋明礼2007年1月 3.6 死锁预防和避免 3.6.1 3.6.1 死锁预防死锁预防 一、互斥条件是资源固有属性，不能避免。一、互斥条件是资源固有属性，不能避免。 二、摒弃请求和保持条件二、摒弃请求和保持条件 全分配，全释放（全分配，全释放（ANDAND） 缺点：（缺点：（1 1）延迟进程运行）延迟进程运行 （2 2）资源严重浪费）资源严重浪费 三、摒弃三、摒弃“不剥夺不剥夺”条件条件 增加系统开销，且进程前段工作可能失效。增加系统开销，且进程前段工作可能失效。 西华大学数学与计算机学院 蒋明礼2007年1月 3.6 死锁预防和避免 3.6.1 3.6.1 死锁预

28、防死锁预防 四、摒弃四、摒弃“环路环路”条件条件 有序资源分配法：为资源编号，申请时需按编号进有序资源分配法：为资源编号，申请时需按编号进 行。行。 缺点：缺点： （1 1）新增资源不便，（原序号已排定）新增资源不便，（原序号已排定） （2 2）用户不自由）用户不自由 （3 3）资源与进程使用顺序不同造成浪费）资源与进程使用顺序不同造成浪费 西华大学数学与计算机学院 蒋明礼2007年1月 3.6.2 系统的安全状态 在在“避免死锁避免死锁”方法中的判断条件方法中的判断条件 1. 1. 安全状态安全状态 按某种顺序并发进程都能达到获得最大资源而顺按某种顺序并发进程都能达到获得最大资源而顺 序完成

29、的序列为安全序列。序完成的序列为安全序列。 能找到安全序列的状态为安全状态。能找到安全序列的状态为安全状态。 西华大学数学与计算机学院 蒋明礼2007年1月 3.6.2 系统的安全状态（2） 2.2.安全状态例安全状态例 进程进程最大需最大需 求求 已分配已分配可用可用 P11053 P242 P392 安全序列：安全序列：p2p2p1p1p3 p3 西华大学数学与计算机学院 蒋明礼2007年1月 3.6.2 系统的安全状态（3） 3 3安全安全不安全的转换不安全的转换 上例中，若上例中，若P3P3再申请一台，则不安全再申请一台，则不安全 进程进程最大需最大需 求求 已分配已分配 可用可用 P

30、11052 P242 P393 西华大学数学与计算机学院 蒋明礼2007年1月 3.6.3利用银行家算法避免死锁 1 1数据结构数据结构 availablej=k: availablej=k: 系统现有系统现有RjRj类资源类资源k k个；个； maxi,j=k: maxi,j=k: 进程进程i i需要需要RjRj的最大数的最大数k k个；个； alloci,j=k: alloci,j=k: 进程进程i i已得到已得到RjRj类资源类资源k k个；个； needi,j=k:needi,j=k:进程进程i i需要需要RjRj类资源类资源k k个个 有：有：needi,j= maxi,jneedi

31、,j= maxi,jalloci,jalloci,j requestirequesti 进程进程i i请求资源数请求资源数 workiworki：进程：进程i i执行完后系统应有资源数（也即可用数）执行完后系统应有资源数（也即可用数） finishifinishi：布尔量，表进程：布尔量，表进程i i能否顺序完成。能否顺序完成。 西华大学数学与计算机学院 蒋明礼2007年1月 3.6.3利用银行家算法避免死锁 2 2银行家算法银行家算法 reqi=needi error reqi=availi block 西华大学数学与计算机学院 蒋明礼2007年1月 3.6.3利用银行家算法避免死锁 ava

32、il=avail-reqi alloci=alloci+reqi needi=needi-reqi finishi=.F. needi=work work=work+alloci finishi=.T. 西华大学数学与计算机学院 蒋明礼2007年1月 4实例 Max A B C Allocation A B C Need A B C Available A B C 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时刻的资源分配表时刻的资源分配表 西华大学数学与计算机学院 蒋明礼2007年1月 4实例 Work A B C Need A B C Alloc A B C Work+alloc A B C 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 true p4 7 4 3 4 3 1 0 0 2 7 4 5 true p2 7 4 5 6 0 0 3 0 2