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

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调度的队列模型二、具有高二、具有高/ /低级模型低级模型进程进程完成完成后备队列后备队列作业调度作业调度就绪队列就绪队列CPU阻塞队列阻塞队列时间片完

4、时间片完进程调度进程调度等待事件等待事件1事件事件1出现出现阻塞队列阻塞队列等待事件等待事件2事件事件2出现出现西华大学数学与计算机学院 蒋明礼2007年1月三、具有三级调度后备队列后备队列就绪队列就绪队列CPU就绪、挂起队列就绪、挂起队列时间片完时间片完进程调度进程调度进程进程完成完成阻塞、挂起队列阻塞、挂起队列事件出现事件出现作业调度作业调度阻塞队列阻塞队列等待事件等待事件挂起挂起事件出现事件出现中级调度中级调度交互型作业交互型作业西华大学数学与计算机学院 蒋明礼2007年1月3.1.3选择调度方式和算法的若干准则 一、面向用户的准则一、面向用户的准则1 1周转时间短（常用于批处理系统）周

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

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

7、用率好：（因处理机利用率好：（因CPUCPU贵，特别于大中贵，特别于大中型多用户系统）型多用户系统）3 3各类资源的平衡利用。（？折算标准）各类资源的平衡利用。（？折算标准）3.1.3选择调度方式和算法的若干准则 西华大学数学与计算机学院 蒋明礼2007年1月3.2调度算法是一个资源分配问题 3.2.13.2.1先来先服务和短作业（进程）优先调度算先来先服务和短作业（进程）优先调度算法法 1.FCFS1.FCFS特点：简单，有利于长作业特点：简单，有利于长作业 即即CPUCPU繁忙性作业繁忙性作业2.2.短作业进程优先调度算法：短作业进程优先调度算法：SJ(P)FSJ(P)F提高了平均周转时间

8、和平均带权周转时间（从而提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量）提高了系统吞吐量）特点：对长作业不利，有可能得不到服务（饥饿）特点：对长作业不利，有可能得不到服务（饥饿）估计时间不易确定估计时间不易确定西华大学数学与计算机学院 蒋明礼2007年1月 例进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.99西华大学数学与计算机学院 蒋明礼2007年1月图3.4FCFS和SJF比较进程名进程名 A B C D E平均平均到达时间到达时间 0 1 2 3 4服务时间服

9、务时间 4 3 5 2 4FCFS完成时间完成时间 4 7 12 14 18周转时间周转时间 4 6 10 11 149带权周转时间带权周转时间 1 2 2 5.5 3.52.8SJF完成时间完成时间 4 9 18 6 13周转时间周转时间 4 8 16 3 98带权周转时间带权周转时间 1 2.67 3.1 1.5 2.252.1西华大学数学与计算机学院 蒋明礼2007年1月3.2.2高优先权优先调度算法1.1.优先权调度算法类型优先权调度算法类型非抢占式优先权算法非抢占式优先权算法抢占式优先权算法，实时性更好。抢占式优先权算法，实时性更好。2.2.优先权类型：优先权类型：1 1静态优先权：

10、静态优先权：进程优先权在整个运行期不变。进程优先权在整个运行期不变。确定优先权依据确定优先权依据（1 1）进程类型）进程类型（2 2）进程对资源的需求；）进程对资源的需求；（3 3）根据用户需求。）根据用户需求。特点：简单，但低优先权作业可能长期不被调度。特点：简单，但低优先权作业可能长期不被调度。西华大学数学与计算机学院 蒋明礼2007年1月3.2.2高优先权优先调度算法(2)2 2动态优先权：动态优先权：如：优先权随执行时间而下降，随等待时间而升高。如：优先权随执行时间而下降，随等待时间而升高。响应比响应比RpRp= =（等待时间服务时间）（等待时间服务时间）/ /服务时间服务时间 作为优

11、先权作为优先权优点：长短兼顾优点：长短兼顾 缺点：需计算缺点：需计算RpRp3.3.高响应比优先算法：高响应比优先算法：特点：特点：响应比响应比RpRp= =（tw+tstw+ts）/ts/ts（1 1）短作业）短作业R RP P大。大。（2 2）tsts（要求服务时间）相同的进程间相当于（要求服务时间）相同的进程间相当于FCFSFCFS。（3 3）长作业等待一段时间仍能得到服务。）长作业等待一段时间仍能得到服务。西华大学数学与计算机学院 蒋明礼2007年1月3.2.3基于时间片的轮转调度算法1.1.时间片轮转时间片轮转时间片大小的确定时间片大小的确定太大：退化为太大：退化为FCFSFCFS；

12、太小：系统开销过大太小：系统开销过大系统对响应时间的要求；系统对响应时间的要求；T=nqT=nq就绪队列中进程的数目；就绪队列中进程的数目；系统的处理能力：（应保证一个时间片处理完常用系统的处理能力：（应保证一个时间片处理完常用命令）命令）西华大学数学与计算机学院 蒋明礼2007年1月3.2.3基于时间片的轮转调度算法2.2.多级反馈队列调度多级反馈队列调度特点：长、短作业兼顾，有较好的响应时间特点：长、短作业兼顾，有较好的响应时间（1 1）短作业一次完成；）短作业一次完成；（2 2）中型作业周转时间不长；）中型作业周转时间不长；（3 3）大型作业不会长期不处理。）大型作业不会长期不处理。西华

13、大学数学与计算机学院 蒋明礼2007年1月就绪队列就绪队列1 1至至CPUS1就绪队列就绪队列2 2S2至至CPU就绪队列就绪队列3 3S3至至CPU就绪队列就绪队列n nSn至至CPU时间片：时间片：S1S2S3图图35多级队列反馈调度算法多级队列反馈调度算法西华大学数学与计算机学院 蒋明礼2007年1月3 3.3.1.3.1实现实时调度的基本条件实现实时调度的基本条件1 1提供必要的调度信息提供必要的调度信息（1 1）就绪时间；）就绪时间；（2 2）开始）开始/ /完成截止时间；完成截止时间；（3 3）处理时间；）处理时间；（4 4）资源要求；）资源要求；（5 5）优先级；）优先级；2 2

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

15、任务分派3.3实时调度西华大学数学与计算机学院 蒋明礼2007年1月3.3.2实时调度算法的分类1 1、非抢占式调度算法、非抢占式调度算法时间片轮转时间片轮转 秒级秒级非抢占优先权（协同）非抢占优先权（协同） 秒毫秒级秒毫秒级2 2、抢占式调度算法、抢占式调度算法时钟中断抢占优先权时钟中断抢占优先权 毫秒级毫秒级基于抢占点抢占基于抢占点抢占立即抢占立即抢占immediate preemption immediate preemption 毫秒微秒级毫秒微秒级只要不在临界区即抢占（中断引发）只要不在临界区即抢占（中断引发）进程1进程2进程n实时进程调度时间调度时间实时进程要求调度实时进程要求调度

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

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

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

19、607080t1=0B1(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.对称多处理器系统和非对称多处理器系对称多处理器系统和非对称多处理器系统统处理器是否结构相同处理器是否结构相同西华大学数学与计算机学院 蒋明礼2007年1月3.4.2进程分

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

21、）但：但：瓶颈问题，（单队列）瓶颈问题，（单队列）低效性；（需拷贝现场）低效性；（需拷贝现场）线程切换频繁（当线程合作时线程切换频繁（当线程合作时, ,各线程并行的条各线程并行的条件不容易满足）件不容易满足） 西华大学数学与计算机学院 蒋明礼2007年1月2.成组调度 优点：优点：（1 1）对相互合作的进（线）程组调度，可以减）对相互合作的进（线）程组调度，可以减小切换，减小系统开销。小切换，减小系统开销。（2 2）每次分配一组）每次分配一组CPUCPU，减少了调度频率。，减少了调度频率。分配时间分配时间（1 1）面向程序）面向程序（2 2）面向线程：使处理机利用率更高。）面向线程：使处理机利

22、用率更高。 西华大学数学与计算机学院 蒋明礼2007年1月2.成组调度应用程序应用程序A应用程序应用程序BCpu1线程线程1线程线程1Cpu2线程线程2空闲空闲Cpu3线程线程3空闲空闲Cpu4线程线程4空闲空闲时间时间1/21/2浪费浪费37.5%应用程序应用程序A应用程序应用程序BCpu1线程线程1线程线程1Cpu2线程线程2空闲空闲Cpu3线程线程3空闲空闲Cpu4线程线程4空闲空闲时间时间4/51/5浪费浪费15%西华大学数学与计算机学院 蒋明礼2007年1月3.专用处理机分配 引入：多处理机系统，每个处理已不再属宝贵引入：多处理机系统，每个处理已不再属宝贵资源。资源。特点：每个进（线

23、）程专用处理机，使其切换特点：每个进（线）程专用处理机，使其切换小，提高效率。小，提高效率。主要用于大型计算，实时系统主要用于大型计算，实时系统西华大学数学与计算机学院 蒋明礼2007年1月3.5产生死锁的原因和必要条件3 3.5.5.1.1产生死锁的原因。产生死锁的原因。一、竞争资源引起死锁。一、竞争资源引起死锁。1 1可剥夺（可剥夺（CPUCPU、内存，）和非剥夺性（打印机，、内存，）和非剥夺性（打印机，磁带机）资源磁带机）资源2 2竞争非剥夺性资源竞争非剥夺性资源可造成死锁可造成死锁 p1p2R1R2西华大学数学与计算机学院 蒋明礼2007年1月3.5产生死锁的原因和必要条件3 3竞争临

24、时性资源竞争临时性资源临时性资源是指由一个进程产生，被另一个进程临时性资源是指由一个进程产生，被另一个进程使用一段时间后便无用的资源。使用一段时间后便无用的资源。西华大学数学与计算机学院 蒋明礼2007年1月二、进程推进顺序不当引起死锁。213DP2Req(R2)P2Req(R1)P1Req(R1) P1Req(R2)P2Rel(R2)P2Rel(R1)P1Rel(R1) P1Rel(R2)4西华大学数学与计算机学院 蒋明礼2007年1月3.5.2 产生死锁的必要条件1 1互斥条件（资源的临界性）互斥条件（资源的临界性）2 2请求和保持条件请求和保持条件3 3不剥夺条件不剥夺条件4 4环路等待

25、环路等待西华大学数学与计算机学院 蒋明礼2007年1月3.5.3处理死锁的基本方法 1 1预防；破坏预防；破坏4 4个条件之一：有效，个条件之一：有效，使资源利用率低。使资源利用率低。2 2避免：防止进入不安全态。避免：防止进入不安全态。3 3检测：检测到死锁再清除。检测：检测到死锁再清除。4 4解除：与解除：与“检检”配套。配套。西华大学数学与计算机学院 蒋明礼2007年1月3.6 死锁预防和避免 3.6.1 3.6.1 死锁预防死锁预防 一、互斥条件是资源固有属性，不能避免。一、互斥条件是资源固有属性，不能避免。二、摒弃请求和保持条件二、摒弃请求和保持条件全分配，全释放（全分配，全释放（A

26、NDAND）缺点：（缺点：（1 1）延迟进程运行）延迟进程运行（2 2）资源严重浪费）资源严重浪费三、摒弃三、摒弃“不剥夺不剥夺”条件条件增加系统开销，且进程前段工作可能失效。增加系统开销，且进程前段工作可能失效。西华大学数学与计算机学院 蒋明礼2007年1月3.6 死锁预防和避免 3.6.1 3.6.1 死锁预防死锁预防 四、摒弃四、摒弃“环路环路”条件条件有序资源分配法：为资源编号，申请时需按编号进有序资源分配法：为资源编号，申请时需按编号进行。行。缺点：缺点：（1 1）新增资源不便，（原序号已排定）新增资源不便，（原序号已排定）（2 2）用户不自由）用户不自由（3 3）资源与进程使用顺序

27、不同造成浪费）资源与进程使用顺序不同造成浪费西华大学数学与计算机学院 蒋明礼2007年1月3.6.2 系统的安全状态在在“避免死锁避免死锁”方法中的判断条件方法中的判断条件 1. 1. 安全状态安全状态按某种顺序并发进程都能达到获得最大资源而顺按某种顺序并发进程都能达到获得最大资源而顺序完成的序列为安全序列。序完成的序列为安全序列。能找到安全序列的状态为安全状态。能找到安全序列的状态为安全状态。西华大学数学与计算机学院 蒋明礼2007年1月3.6.2 系统的安全状态（2）2.2.安全状态例安全状态例进程进程最大需最大需求求已分配已分配可用可用P11053P242P392安全序列：安全序列：p2

28、p2p1p1p3 p3 西华大学数学与计算机学院 蒋明礼2007年1月3.6.2 系统的安全状态（3）3 3安全安全不安全的转换不安全的转换 上例中，若上例中，若P3P3再申请一台，则不安全再申请一台，则不安全 进程进程最大需最大需求求已分配已分配 可用可用P11052P242P393西华大学数学与计算机学院 蒋明礼2007年1月3.6.3利用银行家算法避免死锁 1 1数据结构数据结构availablejavailablej=k: =k: 系统现有系统现有RjRj类资源类资源k k个；个；maxi,jmaxi,j=k: =k: 进程进程i i需要需要RjRj的最大数的最大数k k个；个；all

29、oci,jalloci,j=k: =k: 进程进程i i已得到已得到RjRj类资源类资源k k个；个； needi,jneedi,j=k:=k:进程进程i i需要需要RjRj类资源类资源k k个个有：有：needi,j= maxi,jneedi,j= maxi,j alloci,jalloci,j requestirequesti 进程进程i i请求资源数请求资源数workiworki：进程：进程i i执行完后系统应有资源数（也即可用数）执行完后系统应有资源数（也即可用数）finishifinishi ：布尔量，表进程：布尔量，表进程i i能否顺序完成。能否顺序完成。 西华大学数学与计算机学院

30、 蒋明礼2007年1月3.6.3利用银行家算法避免死锁 2 2银行家算法银行家算法 reqi=needierrorreqi=availiblock西华大学数学与计算机学院 蒋明礼2007年1月3.6.3利用银行家算法避免死锁 avail=avail-reqialloci=alloci+reqineedi=needi-reqifinishi=.F.needi=workwork=work+allocifinishi=.T.西华大学数学与计算机学院 蒋明礼2007年1月4实例 Max A B C Allocation A B C Need A B C Available A B C p0 7 5 3

31、 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 1T0时刻的资源分配表时刻的资源分配表西华大学数学与计算机学院 蒋明礼2007年1月4实例Work A B CNeed A B C Alloc A B CWork+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 10 4 7 true p