处理机调度与死锁

操作系统Operating System主讲老师：单 红第一章 引论第二章 进程管理第三章 处理机调度与死锁第四章 存储管理第五章 设备管理第七章 操作系统接口操作系统操作系统第六章 文件管理v2 2、低级调度（进程调度，短程调度）、低级调度（进程调度，短程调度）v主要是由分派程序（主要是由分派程序（DispatcherDispatcher）分派处理机。）分派处理机。1.1.非抢占方式：非抢占方式：简单，实时性差简单，实时性差 (如如win31)win31)2.2.抢占方式抢占方式 （1 1）时间片原则）时间片原则 （2 2）优先权原则）优先权原则 （3 3）短作业优先原则。）短作业优先原则。v运行频率：低运行频率：低 中中 高高。v三种调度被引发的事件？三种调度被引发的事件？v事件的表现方式？事件的表现方式？v一、仅有进程调度的队列模型一、仅有进程调度的队列模型就绪队列就绪队列CPU阻塞队列阻塞队列交互用户交互用户时间片完时间片完进程调度进程调度进程完成进程完成等待事件等待事件事件出现事件出现v二、具有高二、具有高/低级模型低级模型 n 就绪队列就绪队列CPU阻塞队列阻塞队列时间片完时间片完进程调度进程调度进程进程完成完成等待事件等待事件1事件事件1出现出现后备队列后备队列阻塞队列阻塞队列等待事件等待事件2事件事件2出现出现作业调度作业调度NoImage就绪队列就绪队列CPU就绪、挂起队列就绪、挂起队列时间片完时间片完进程调度进程调度进程进程完成完成后备队列后备队列阻塞、挂起队列阻塞、挂起队列事件出现事件出现作业调度作业调度阻塞队列阻塞队列等待事件等待事件挂起挂起事件出现事件出现中级调度中级调度交互型作业交互型作业v一、面向用户的准则一、面向用户的准则 1 1周转时间短（常用于批处理系统）周转时间短（常用于批处理系统）概念：作业从提交概念：作业从提交 完成的时间完成的时间.分为：分为：（1 1）驻外等待调度时间）驻外等待调度时间 （2 2）驻内等待调度时间）驻内等待调度时间 （3 3）执行时间）执行时间 （4 4）阻塞时间）阻塞时间v一、面向用户的准则一、面向用户的准则 平均周转时间平均周转时间 平均带权平均带权 可见带权可见带权w w越小越好越小越好,Ts,Ts为实际服务时间。为实际服务时间。11niiTnT11nisiTTnWv一、面向用户的准则一、面向用户的准则 2 2响应时间快：（对交互性作业）响应时间快：（对交互性作业）概念：键盘提交请求到首次响应时间概念：键盘提交请求到首次响应时间 （1 1）输入传送时间）输入传送时间 （2 2）处理时间）处理时间 （3 3）响应传送时间）响应传送时间 3 3截止时间的保证（特别于实时系统）截止时间的保证（特别于实时系统）4 4优先权准则：（即需要抢占调度）优先权准则：（即需要抢占调度）v二、面向系统的准则二、面向系统的准则 1 1吞吐量高（特别于批处理）：单位时间完成作吞吐量高（特别于批处理）：单位时间完成作业数业数 2 2处理机利用率好：（因处理机利用率好：（因CPUCPU贵，特别于大中型贵，特别于大中型多用户系统）多用户系统）3 3各类资源的平衡利用。（？折算标准）各类资源的平衡利用。（？折算标准）v先来先服务和短作业（进程）优先调度算法先来先服务和短作业（进程）优先调度算法 1.FCFS 1.FCFS 特点：简单，有利于长作业特点：简单，有利于长作业 即即CPUCPU繁忙性作业繁忙性作业 2.2.短作业进程优先调度算法：短作业进程优先调度算法：SJ(P)F SJ(P)F 提高了平均周转时间和平均带权周转时间（从而提提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量）高了系统吞吐量）特点：对长作业不利，有可能得不到服务（饥饿）特点：对长作业不利，有可能得不到服务（饥饿）估计时间不易确定估计时间不易确定进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.99进程名进程名 A B C D E平均平均到达时间到达时间 0 1 2 3 4服务时间服务时间 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.1v1.1.优先权调度算法类型优先权调度算法类型 非抢占式优先权算法非抢占式优先权算法 抢占式优先权算法，实时性更好。抢占式优先权算法，实时性更好。v2.2.优先权类型：优先权类型：1 1静态优先权：静态优先权：进程优先权在整个运行期不变。进程优先权在整个运行期不变。确定优先权依据确定优先权依据 C（1 1）进程类型）进程类型 C（2 2）进程对资源的需求；）进程对资源的需求；C（3 3）根据用户需求。）根据用户需求。特点：简单，但低优先权作业可能长期不被调度。特点：简单，但低优先权作业可能长期不被调度。v2 2动态优先权：动态优先权：如：优先权随执行时间而下降，随等待时间而升高。如：优先权随执行时间而下降，随等待时间而升高。响应比响应比RpRp=（等待时间服务时间）（等待时间服务时间）/服务时间服务时间 作为优作为优先权先权 优点：长短兼顾优点：长短兼顾 缺点：需计算缺点：需计算RpRp v3.3.高响应比优先算法：高响应比优先算法：特点：特点：响应比响应比RpRp=（tw+tstw+ts）/tsts （1 1）短作业）短作业R RP P大。大。（2 2）tsts（要求服务时间）相同的进程间相当于（要求服务时间）相同的进程间相当于FCFSFCFS。（3 3）长作业等待一段时间仍能得到服务。）长作业等待一段时间仍能得到服务。v1.1.时间片轮转时间片轮转 时间片大小的确定时间片大小的确定 太大：退化为太大：退化为FCFSFCFS；太小：系统开销过大太小：系统开销过大 系统对响应时间的要求；系统对响应时间的要求；T=T=nqnq 就绪队列中进程的数目；就绪队列中进程的数目；系统的处理能力：（应保证一个时间片处理完常用命令）系统的处理能力：（应保证一个时间片处理完常用命令）v2.2.多级反馈队列调度多级反馈队列调度 特点：长、短作业兼顾，有较好的响应时间特点：长、短作业兼顾，有较好的响应时间 （1 1）短作业一次完成；）短作业一次完成；（2 2）中型作业周转时间不长；）中型作业周转时间不长；（3 3）大型作业不会长期不处理。）大型作业不会长期不处理。就绪队列就绪队列1 1至至CPUS1就绪队列就绪队列2 2S2至至CPU就绪队列就绪队列3 3S3至至CPU就绪队列就绪队列n nSn至至CPU时间片：时间片：S1S2S3图图35多级队列反馈调度算法多级队列反馈调度算法v实现实时调度的基本条件实现实时调度的基本条件 1 1提供必要的调度信息提供必要的调度信息 （1 1）就绪时间；）就绪时间；（2 2）开始）开始/完成截止时间；完成截止时间；（3 3）处理时间；）处理时间；（4 4）资源要求；）资源要求；（5 5）优先级；）优先级；2 2系统处理能力强系统处理能力强 NPCPCmiiimiii111Ci为处理时间，为处理时间，Pi为周期时间（基于周期性实时任务）为周期时间（基于周期性实时任务）v实现实时调度的基本条件实现实时调度的基本条件 3.3.采用抢占调度方式采用抢占调度方式 剥夺方式：一般都采用此剥夺方式：一般都采用此 非剥夺方式（实现简单）：一般应使实时任务较小，非剥夺方式（实现简单）：一般应使实时任务较小，以及时放弃以及时放弃CPUCPU。4.4.具有快速切换机制具有快速切换机制 具有快速响应外部中断能力。具有快速响应外部中断能力。快速任务分派快速任务分派v1 1非抢占式调度算法非抢占式调度算法 时间片轮转时间片轮转 秒级秒级 非抢占优先权（协同）非抢占优先权（协同）秒秒 毫秒级毫秒级 v2 2抢占式调度算法抢占式调度算法 时钟中断抢占优先权时钟中断抢占优先权 毫秒级毫秒级 基于抢占点抢占基于抢占点抢占 立即抢占立即抢占immediate preemption immediate preemption 毫秒毫秒 微秒级微秒级 只要不在临界区即抢占（中断引发）只要不在临界区即抢占（中断引发）进程1进程2进程n实时进程调度时间调度时间实时进程要求调度实时进程要求调度调度实时进程运行调度实时进程运行a 非抢占轮转调度非抢占轮转调度当前进程实时进程实时进程要求调度实时进程要求调度当前进程运行完成当前进程运行完成b 非抢占优先权调度非抢占优先权调度调度时间调度时间c 基于时钟中断抢占的优先权抢占调度基于时钟中断抢占的优先权抢占调度当前进程实时进程实时进程要求调度实时进程要求调度抢占时刻（其它中断）抢占时刻（其它中断）b 立即抢占优先权调度立即抢占优先权调度当前进程实时进程实时进程要求调度实时进程要求调度时钟中断到达时时钟中断到达时调度时间调度时间 调度时间调度时间 v1.1.最早截止时间优先最早截止时间优先EDFEDF（earliest deadline first)earliest deadline first)算法算法 根据任务的截止时间来确定任务的优先级根据任务的截止时间来确定任务的优先级 截止时间越早，优先级越高截止时间越早，优先级越高 可以是抢占式或非抢占式可以是抢占式或非抢占式 1342134212 34t开始截止时间开始截止时间任务到达任务到达任务执行任务执行图图37 EDF算法用于非抢占调度方式算法用于非抢占调度方式v松弛度：松弛度：若若A A进程需在进程需在200ms200ms时完成，其本身运行需要时完成，其本身运行需要100ms100ms，当，当前时刻是前时刻是10ms10ms，则，则A A的松弛度为：的松弛度为：200200100100101090 90 主要用于可抢占的调度方式中主要用于可抢占的调度方式中 例：例：A1A2A3A4A5A6A7A8B1B2B3020406080 100120 140160t图图38 A/B任务每次必须完成的时间任务每次必须完成的时间A1(10)A2(10)A3(10)A4(10)t01020304050607080t1=0B1(20)B1(5)B2(15)B2(10)t1t2t3t4t5t6t7t8v1.1.紧密耦合紧密耦合MPSMPS和松弛耦合和松弛耦合MPS MPS 紧密耦合紧密耦合 共享共享RAMRAM和和I/O I/O 高速总线和交叉开关连接高速总线和交叉开关连接 松弛耦合松弛耦合 独立独立RAMRAM和和I/O I/O 通道和通信线路连接通道和通信线路连接 v2.2.对称多处理器系统和非对称多处理器系统对称多处理器系统和非对称多处理器系统 处理器是否结构相同处理器是否结构相同v中进程分配方式中进程分配方式 静态分配静态分配 动态分配动态分配 可防止系统中多个处理器忙闲不均可防止系统中多个处理器忙闲不均 v2.2.非非SMPSMP中进程分配方式中进程分配方式 进程调度在主处理器上执行进程调度在主处理器上执行 有潜在的不可靠性有潜在的不可靠性 v1.1.自调度自调度 各个处理机自行在就绪队列中取任务。各个处理机自行在就绪队列中取任务。特点；简单，分布式调度，调度算法可采用特点；简单，分布式调度，调度算法可采用前述方法，多个前述方法，多个CPUCPU利用率都不错（不会闲）利用率都不错（不会闲）但：但：瓶颈问题，（单队列）瓶颈问题，（单队列）低效性；（需拷贝现场）低效性；（需拷贝现场）线程切换频繁（当线程合作时线程切换频繁（当线程合作时,各线程并各线程并行的条件不容易满足）行的条件不容易满足）v优点：优点：（1 1）对相互合作的进（线）程组调度，可以减小切换，）对相互合作的进（线）程组调度，可以减小切换，减小系统开销。减小系统开销。（2 2）每次分配一组）每次分配一组CPUCPU，减少了调度频率。，减少了调度频率。v分配时间分配时间 （1 1）面向程序）面向程序 （2 2）面向线程：使处理机利用率更高。）面向线程：使处理机利用率更高。NoImage应用程序应用程序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%v引入：多处理机系统，每个处理已不再属宝贵资源。引入：多处理机系统，每个处理已不再属宝贵资源。v特点：每个进（线）程专用处理机，使其切换小，特点：每个进（线）程专用处理机，使其切换小，提高效率。提高效率。v主要用于大型计算，实时系统主要用于大型计算，实时系统v引入：多处理机系统，每个处理已不再属宝贵资源。引入：多处理机系统，每个处理已不再属宝贵资源。v特点：每个进（线）程专用处理机，使其切换小，特点：每个进（线）程专用处理机，使其切换小，提高效率。提高效率。v主要用于大型计算，实时系统主要用于大型计算，实时系统v3 3竞争临时性资源竞争临时性资源 临时性资源是指由一个进程产生，被另一个进程使用临时性资源是指由一个进程产生，被另一个进程使用一段时间后便无用的资源。一段时间后便无用的资源。213DP2Req(R2)P2Req(R1)P1Req(R1)P1Req(R2)P2Rel(R2)P2Rel(R1)P1Rel(R1)P1Rel(R2)4v1 1互斥条件（资源的临界性）互斥条件（资源的临界性）v2 2请求和保持条件请求和保持条件 v3 3不剥夺条件不剥夺条件 v4 4环路等待环路等待v1 1预防；破坏预防；破坏4 4个条件之一：有效，使资源个条件之一：有效，使资源利用率低。利用率低。v2 2避免：防止进入不安全态。避免：防止进入不安全态。v3 3检测：检测到死锁再清除。检测：检测到死锁再清除。v4 4解除：与解除：与“检检”配套。配套。v3.6.1 3.6.1 死锁预防死锁预防 一、互斥条件是资源固有属性，不能避免。一、互斥条件是资源固有属性，不能避免。二、摒弃请求和保持条件二、摒弃请求和保持条件 全分配，全释放（全分配，全释放（ANDAND）缺点：（缺点：（1 1）延迟进程运行）延迟进程运行 （2 2）资源严重浪费）资源严重浪费 三、摒弃三、摒弃“不剥夺不剥夺”条件条件 增加系统开销，且进程前段工作可能失效。增加系统开销，且进程前段工作可能失效。v3.6.1 3.6.1 死锁预防死锁预防 四、摒弃四、摒弃“环路环路”条件条件 有序资源分配法：为资源编号，申请时需按编号进行。有序资源分配法：为资源编号，申请时需按编号进行。缺点：缺点：（1 1）新增资源不便，（原序号已排定）新增资源不便，（原序号已排定）（2 2）用户不自由）用户不自由 （3 3）资源与进程使用顺序不同造成浪费）资源与进程使用顺序不同造成浪费v在在“避免死锁避免死锁”方法中的判断条件方法中的判断条件 v1.1.安全状态安全状态 按某种顺序并发进程都能达到获得最大资源而顺序按某种顺序并发进程都能达到获得最大资源而顺序完成的序列为安全序列。完成的序列为安全序列。能找到安全序列的状态为安全状态。能找到安全序列的状态为安全状态。v2.2.安全状态例安全状态例进程进程最大需求最大需求已分配已分配可用可用P11053P242P392安全序列：安全序列：p2p2p1p1p3 p3 v3 3安全安全不安全的转换不安全的转换 上例中，若上例中，若P3P3再申请一台，则不安全再申请一台，则不安全 进程进程最大需求最大需求 已分配已分配可用可用P11052P242P393v 1 1数据结构数据结构 availablejavailablej=k:=k:系统现有系统现有RjRj类资源类资源k k个；个；maxi,jmaxi,j=k:=k:进程进程i i需要需要RjRj的最大数的最大数k k个；个；alloci,jalloci,j=k:=k:进程进程i i已得到已得到RjRj类资源类资源k k个；个；needi,jneedi,j=k:=k:进程进程i i需要需要RjRj类资源类资源k k个个 有：有：needi,jneedi,j=maxi,jmaxi,j alloci,jalloci,j requestirequesti进程进程i i请求资源数请求资源数 workiworki：进程：进程i i执行完后系统应有资源数（也即可用数）执行完后系统应有资源数（也即可用数）finishifinishi：布尔量，表进程：布尔量，表进程i i能否顺序完成。能否顺序完成。v2 2银行家算法银行家算法 reqi=needierrorreqi=availiblockavail=avail-reqi alloci=alloci+reqi needi=needi-reqifinishi=.F.needi=workwork=work+alloci finishi=.T.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 1T0时刻的资源分配表时刻的资源分配表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 p0 10 4 7 7 4 3 0 1 0 10 5 7 trueT0时刻的安全序列时刻的安全序列Work A B CNeed A B C Alloc A B CWork+alloc A B C 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 true p4 7 4 3 4 3 1 0 0 2 7 4 5 true p0 7 4 5 7 4 3 0 1 0 7 5 5 true p2 7 5 5 6 0 0 3 0 2 10 5 7 trueP1申请资源申请资源(1,0,2)时安全性检查时安全性检查(安全安全)Allocation A B C Need A B C Available A B C p0 0 3 0 7 2 3 2 1 0 p1 3 0 2 0 2 0 p2 3 0 2 6 0 0 p3 2 1 1 0 1 1 p4 0 0 2 4 3 1为为P0分配（分配（0，2，0）后的情况（不安全）后的情况（不安全）v检测检测 v1.1.资源分配图资源分配图 p1p2v2.2.死锁定理死锁定理 简化资源分配图简化资源分配图 若能完全简化则消去所有的边。若能完全简化则消去所有的边。定理：死锁状态的充分条件，资源分配图不可完全简化定理：死锁状态的充分条件，资源分配图不可完全简化 v3.3.检测死锁的算法：检测死锁的算法：Work=available L:=Li|alloci=0 reqi=0(孤立进程点孤立进程点)For all Li L do Begin For all reqi=work do Begin Work=work+alloci L=LiL endEnd Deadlock=(L=p1 pn)v检测到死锁后，回退到上一状态（要进行资源剥夺，检测到死锁后，回退到上一状态（要进行资源剥夺，且需保存以前状态的分配信息），重新分配，若不且需保存以前状态的分配信息），重新分配，若不行，继续回退行，继续回退，