最新-第三章处理机调度与死锁-课件

处理机调度与死锁

第三章12/22/20221操作系统

处理机调度与死锁

第三章12/17/20221操作系统3.1处理机调度的基本概念3.1.1高、中、低三级调度1、高级调度（作业调度、长程调度、接纳调度）将外存作业调入内存，创建PCB等，插入就绪队列。一般用于批处理系统，分/实时系统一般直接入内存，无此环节。调度特性1.接纳作业数（内存驻留数）太多―――> 周转时间(T)长太少―――> 资源利用率和系统吞吐量低2.接纳哪些作业（接纳策略）：即采用何种调度算法：FCFS、短作业优先等12/22/20222操作系统3.1处理机调度的基本概念3.1.1高、中、低三级调度处理机调度的基本概念（2）2、低级调度（进程调度，短程调度）主要是由分派程序（Dispatcher）分派处理机。1.非抢占方式： 简单，实时性差(如win31)2.抢占方式（1）时间片原则（2）优先权原则（3）短作业优先原则。

12/22/20223操作系统处理机调度的基本概念（2）2、低级调度（进程调度，短程调度）3、中级调度（中程）为提高系统吞吐量和内存利用率而引入的一内------外存对换功能（换出时，进程为挂起或就绪驻外状态）

运行频率：低>中>高。12/22/20224操作系统3、中级调度（中程）12/17/20224操作系统3.1.2调度的队列模型一、仅有进程调度的队列模型就绪队列CPU阻塞队列交互用户时间片完进程调度进程完成等待事件事件出现12/22/20225操作系统3.1.2调度的队列模型一、仅有进程调度的队列模型就绪队列C3.1.2调度的队列模型二、具有高/低级模型就绪队列CPU阻塞队列时间片完进程调度进程完成等待事件1事件1出现后备队列阻塞队列等待事件2事件2出现作业调度12/22/20226操作系统3.1.2调度的队列模型二、具有高/低级模型就绪队列CPU阻三、具有三级调度就绪队列CPU就绪，挂起队列时间片完进程调度进程完成后备队列阻塞，挂起队列事件出现作业调度阻塞队列等待事件挂起事件出现中级调度交互型作业12/22/20227操作系统三、具有三级调度就绪队列CPU就绪，挂起队列时间片完进程调度3.1.3选择调度方式和算法的若干准则

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

平均带权周转时间

T/Ts为带权周转时间，T为周转时间，Ts为实际服务时间；可见带权w越小越好。3.1.3选择调度方式和算法的若干准则

12/22/20229操作系统3.1.3选择调度方式和算法的若干准则12/17/20222．响应时间快：（常用于评价分时系统）概念：键盘提交请求到首次响应时间（1）输入传送时间（2）处理时间（3）响应传送时间3．截止时间的保证（常用于评价实时系统）4．优先权准则：（即需要抢占调度）3.1.3选择调度方式和算法的若干准则12/22/202210操作系统2．响应时间快：（常用于评价分时系统）3.1.3选择调度方式二、面向系统的准则1．吞吐量高（特别用于批处理）：单位时间完成作业数2．处理机利用率好：（因CPU贵，特别用于大中型多用户系统）3．各类资源的平衡利用。（折算标准）3.1.3选择调度方式和算法的若干准则

12/22/202211操作系统二、面向系统的准则3.1.3选择调度方式和算法的若干准则13.2调度算法——是一个资源分配问题3.2.1先来先服务和短作业（进程）优先调度算法1. FCFS优点：简单，有利于长作业即CPU繁忙型作业缺点：没考虑进程的优先级进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.9912/22/202212操作系统3.2调度算法——是一个资源分配问题3.2.1先来先服务和2.短作业(进程)优先调度算法SJ(P)F

：提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量）特点：对长作业不利，有可能得不到服务，不能保证紧迫性作业被及时处理，估计时间不易确定。12/22/202213操作系统2.短作业(进程)优先调度算法SJ(P)F：12/17/2图3.4 FCFS和SJF比较进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间47121418周转时间461011149带权周转时间1225.53.52.8SJF完成时间4918613周转时间4816398带权周转时间12.673.11.52.252.112/22/202214操作系统图3.4 FCFS和SJF比较进程名AB3.2.2高优先权优先调度算法1.优先权调度算法类型(作业、进程)针对进程调度又有如下两种算法：非抢占式优先权算法抢占式优先权算法，实时性更好。12/22/202215操作系统3.2.2高优先权优先调度算法1.优先权调度算法类型(作业、2.优先权类型：①．静态优先权：进程优先权在整个运行期不变。确定优先权依据（1）进程类型（2）进程对资源的需求；（3）根据用户需求。特点：简单，但低优先权作业可能长期不被调度。②．动态优先权：如：优先权随执行时间而下降，随等待时间而升高。12/22/202216操作系统2.优先权类型：12/17/202216操作系统3.2.2高优先权优先调度算法(2)3.高响应比优先算法：响应比Rp=（等待时间＋服务时间）/服务时间

作为优先权优点：长短兼顾缺点：需计算Rp特点：响应比Rp=（tw+ts）/ts（优先权相当于相应比）（1）短作业（ts小，tw相同）RP大。（2）ts（要求服务时间）相同的进程间相当于FCFS。（3）长作业等待一段时间仍能得到服务。12/22/202217操作系统3.2.2高优先权优先调度算法(2)12/17/2022173.2.3基于时间片的轮转调度算法(进程)1.时间片轮转时间片大小的确定太大：退化为FCFS；太小：系统开销过大系统对响应时间的要求；就绪队列中进程的数目；系统的处理能力（CPU能力）：（应保证一个时间片处理完常用命令）12/22/202218操作系统3.2.3基于时间片的轮转调度算法(进程)1.时间片轮转123.2.3基于时间片的轮转调度算法2.多级反馈队列调度特点：长、短作业兼顾，有较好的响应时间（1）短作业一次完成；（2）中型作业周转时间不长；（3）大型作业不会长期不处理。12/22/202219操作系统3.2.3基于时间片的轮转调度算法2.多级反馈队列调度12/就绪队列1至CPUS1就绪队列2S2至CPU就绪队列3S3至CPU就绪队列nSn至CPU时间片：S1<S2<S3<…<Sn图3－5多级反馈队列调度算法12/22/202220操作系统就绪队列1至CPUS1就绪队列2S2至CPU就绪队列3S3至多级反馈队列调度算法示例图12/22/202221操作系统多级反馈队列调度算法示例图12/17/202221操作系统多级反馈队列调度算法小结：首先系统中设置多个就绪队列每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大各个队列按照FCFS调度算法，最后一个队列是按照时间片轮转调度一个新进程就绪后进入第一级队列进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到第一级队列。当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾。当第一级队列为空时，就去调度第二级队列，以此类推当时间片到后，进程放弃CPU，回到下一级队列。12/22/202222操作系统多级反馈队列调度算法小结：首先系统中设置多个就绪队列12/13.3.1实现实时调度的基本条件1．提供必要的调度信息（1）就绪时间；（2）开始/完成截止时间；（3）处理时间；（4）资源要求；（5）优先级；2．系统处理能力强3.3实时调度Ci为处理时间，Pi为周期时间（基于周期性实时任务）12/22/202223操作系统3.3.1实现实时调度的基本条件3.3实时调度Ci为处理时间3.采用抢占调度方式剥夺方式：一般都采用此非剥夺方式（实现简单）：一般应使实时任务较小，以及时放弃CPU。4.具有快速切换机制具有快速响应外部中断能力。快速的任务分派能力3.3实时调度12/22/202224操作系统3.采用抢占调度方式3.3实时调度12/17/202224操3.3.2实时调度算法的分类1.非抢占式调度算法时间片轮转 秒级非抢占式优先权（协同） 秒-毫秒级2.抢占式调度算法时钟中断抢占优先权 毫秒级基于抢占点抢占立即抢占immediatepreemption毫秒-微秒级只要不在临界区即抢占（中断引发）12/22/202225操作系统3.3.2实时调度算法的分类1.非抢占式调度算法12/17/进程1进程2进程n实时进程调度时间实时进程要求调度调度实时进程运行a非抢占轮转调度b非抢占优先权调度当前进程实时进程实时进程要求调度当前进程运行完成调度时间12/22/202226操作系统进程1进程2进程n实时进程调度时间实时进程要求调度调度实时进c基于时钟中断抢占的优先权抢占调度当前进程实时进程实时进程要求调度抢占时刻（其它中断）b立即抢占优先权调度当前进程实时进程实时进程要求调度时钟中断到达时调度时间调度时间12/22/202227操作系统c基于时钟中断抢占的优先权抢占调度当前进程实时进程实时进程3.3.3常用的几种实时调度算法1.最早截止时间优先EDF（earliestdeadlinefirst)算法根据任务的开始截止时间来确定任务的优先级截止时间越早，优先级越高可以是抢占式或非抢占式12/22/202228操作系统3.3.3常用的几种实时调度算法1.最早截止时间优先EDF（最早截止时间优先EDF例134213421234t开始截止时间任务到达任务执行图3－7EDF算法用于非抢占调度方式12/22/202229操作系统最早截止时间优先EDF例134213421234t开始截止时2.最低松弛度优先LLF算法松弛度：若A进程需在200ms时完成，其本身运行需要100ms，当前时刻是10ms，则A的松弛度为：200－100－10＝90ms（松弛度=必须完成时间-其本身运行时间-当前时间）主要用于可抢占的调度方式中12/22/202230操作系统2.最低松弛度优先LLF算法松弛度：12/17/20223最低松弛度优先LLF算法(2)A1(10)A2(10)A3(10)A4(10)t01020304050607080t1=0B1(20)B1(5)B2(15)B2(10)t1t2t3t4t5t6t7t8A1A2A3A4A5A6A7A8B1B2B3020406080100120140160tA/B任务每次必须完成的时间如下：调度情况如下：12/22/202231操作系统最低松弛度优先LLF算法(2)A1(10)A2(10)A3(3.5产生死锁的原因和必要条件3.5.1产生死锁的原因。一、竞争资源引起死锁。1．可剥夺（CPU、内存，）和非剥夺性（打印机，磁带机）资源2．竞争非剥夺性资源——可造成死锁p2R1R2p112/22/202232操作系统3.5产生死锁的原因和必要条件3.5.1产生死锁的原因。p23.5产生死锁的原因和必要条件3．竞争临时性资源临时性资源是指由一个进程产生，被另一个进程使用一段时间后便无用的资源。P2S3S2P1S1P3正常运行情况：P1:Release(S1);Resquest(S3)P2:Release(S2);Resquest(S1)P3:Release(S3);Resquest(S2)产生死锁：P1:Request(S3);Realse(S1)P2:Request(S1);Realse(S2)P3:Request(S2);Realse(S3)12/22/202233操作系统3.5产生死锁的原因和必要条件3．竞争临时性资源P2S3S2二、进程推进顺序不当引起死锁。213DP2Req(R2)P2Req(R1)P1Req(R1)P1Req(R2)P2Rel(R2)P2Rel(R1)P1Rel(R1)P1Rel(R2)412/22/202234操作系统二、进程推进顺序不当引起死锁。213DP2Req(R2)P23.5.2产生死锁的必要条件1．互斥条件（资源的临界性）2．请求和保持条件3．不剥夺条件4．环路等待12/22/202235操作系统3.5.2产生死锁的必要条件1．互斥条件（资源的临界性）13.5.3处理死锁的基本方法

1．预防；破坏4个条件之一：有效，使资源利用率低。2．避免：防止进入不安全态。3．检测：检测到死锁再清除。4．解除：与“检”配套。12/22/202236操作系统3.5.3处理死锁的基本方法1．预防；破坏4个条件之一：有3.6死锁预防和避免3.6.1死锁预防一、互斥条件是资源固有属性，不能避免。二、摒弃请求和保持条件全分配，全释放（AND）缺点：（1）延迟进程运行 （2）资源严重浪费三、摒弃“不剥夺”条件 增加系统开销，且进程前段工作可能失效。12/22/202237操作系统3.6死锁预防和避免3.6.1死锁预防12/17/23.6死锁预防和避免3.6.1死锁预防 四、摒弃“环路”条件有序资源分配法：为资源编号，申请时需按编号进行。缺点：（1）新增资源不便，（原序号已排定）（2）用户不自由（3）资源与进程使用顺序不同造成浪费12/22/202238操作系统3.6死锁预防和避免3.6.1死锁预防12/17/23.6.2系统的安全状态在“避免死锁”方法中的判断条件1.安全状态按某种顺序并发进程都能达到获得最大资源而顺序完成的序列为安全序列。能找到安全序列的状态为安全状态。12/22/202239操作系统3.6.2系统的安全状态在“避免死锁”方法中的判断条件13.6.2系统的安全状态（2）2.安全状态例进程最大需求已分配可用P11053P242P392安全序列：p2p1p312/22/202240操作系统3.6.2系统的安全状态（2）2.安全状态例进程最大需求已3.6.2系统的安全状态（3）3安全——不安全的转换上例中，若P3再申请一台，则不安全进程最大需求已分配可用P11052P242P39312/22/202241操作系统3.6.2系统的安全状态（3）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能否顺序完成。

12/22/202242操作系统3.6.3利用银行家算法避免死锁12/17/202242操3.6.3利用银行家算法避免死锁2．银行家算法

reqi<=needierrorreqi<=availiblock12/22/202243操作系统3.6.3利用银行家算法避免死锁2．银行家算法reqi<3.6.3利用银行家算法避免死锁avail=avail-reqialloci=alloci+reqineedi=needi-reqifinish[i]=.F.needi<=workwork=work+allocifinish[i]=.T.12/22/202244操作系统3.6.3利用银行家算法避免死锁avail=avail-r4实例MaxABCAllocationABCNeedABCAvailableABCp0753010743332p1322200122p2902302600p3222211011p4433002431T0时刻的资源分配表(302)(020)(230)12/22/202245操作系统4实例MaxAllocationNeed4实例WorkABCNeedABCAllocABCWork+allocABCFinishp1332122200532truep3532011211743truep4743431002745truep27456003021047truep010477430101057trueT0时刻的安全序列12/22/202246操作系统4实例WorkNeedAllocWork+allocFi4实例WorkABCNeedABCAllocABCWork+allocABCFinishp1230020302532truep3532011211743truep4743431002745truep0745743010755truep27556003021057trueP1申请资源(1,0,2)时安全性检查(安全)12/22/202247操作系统4实例WorkNeedAllocWork+allocFi4实例AllocationABCNeedABCAvailableABCp0030723210p1302020p2302600p3211011p4002431为P0分配（0，2，0）后的情况（不安全）12/22/202248操作系统4实例AllocationNeedAvaila3.7死锁的检测和解除3.7.1检测1.资源分配图p1p2r1r212/22/202249操作系统3.7死锁的检测和解除3.7.1检测p1p2r1r212/3.7死锁的检测和解除2.死锁定理简化资源分配图若能完全简化则消去所有的边。定理：死锁状态的充分条件，资源分配图不可完全简化3.检测死锁的算法：12/22/202250操作系统3.7死锁的检测和解除2.死锁定理12/17/202250Work=availableL:={Li|alloci=0reqi=0}(孤立进程点)ForallLiLdoBegin Forallreqi<=workdo Begin Work=work+alloci L=Li∪L end EndDeadlock=~(L={p1…pn})3.7死锁的检测和解除12/22/202251操作系统Work=available3.7死锁的检测和解除12/解除检测到死锁后，回退到上一状态（要进行资源剥夺，且需保存以前状态的分配信息），重新分配，若不行，继续回退……，12/22/202252操作系统解除检测到死锁后，回退到上一状态（要进行资源剥夺，且需保存以

处理机调度与死锁

第三章12/22/202253操作系统

处理机调度与死锁

第三章12/17/20221操作系统3.1处理机调度的基本概念3.1.1高、中、低三级调度1、高级调度（作业调度、长程调度、接纳调度）将外存作业调入内存，创建PCB等，插入就绪队列。一般用于批处理系统，分/实时系统一般直接入内存，无此环节。调度特性1.接纳作业数（内存驻留数）太多―――> 周转时间(T)长太少―――> 资源利用率和系统吞吐量低2.接纳哪些作业（接纳策略）：即采用何种调度算法：FCFS、短作业优先等12/22/202254操作系统3.1处理机调度的基本概念3.1.1高、中、低三级调度处理机调度的基本概念（2）2、低级调度（进程调度，短程调度）主要是由分派程序（Dispatcher）分派处理机。1.非抢占方式： 简单，实时性差(如win31)2.抢占方式（1）时间片原则（2）优先权原则（3）短作业优先原则。

12/22/202255操作系统处理机调度的基本概念（2）2、低级调度（进程调度，短程调度）3、中级调度（中程）为提高系统吞吐量和内存利用率而引入的一内------外存对换功能（换出时，进程为挂起或就绪驻外状态）

运行频率：低>中>高。12/22/202256操作系统3、中级调度（中程）12/17/20224操作系统3.1.2调度的队列模型一、仅有进程调度的队列模型就绪队列CPU阻塞队列交互用户时间片完进程调度进程完成等待事件事件出现12/22/202257操作系统3.1.2调度的队列模型一、仅有进程调度的队列模型就绪队列C3.1.2调度的队列模型二、具有高/低级模型就绪队列CPU阻塞队列时间片完进程调度进程完成等待事件1事件1出现后备队列阻塞队列等待事件2事件2出现作业调度12/22/202258操作系统3.1.2调度的队列模型二、具有高/低级模型就绪队列CPU阻三、具有三级调度就绪队列CPU就绪，挂起队列时间片完进程调度进程完成后备队列阻塞，挂起队列事件出现作业调度阻塞队列等待事件挂起事件出现中级调度交互型作业12/22/202259操作系统三、具有三级调度就绪队列CPU就绪，挂起队列时间片完进程调度3.1.3选择调度方式和算法的若干准则

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

平均带权周转时间

T/Ts为带权周转时间，T为周转时间，Ts为实际服务时间；可见带权w越小越好。3.1.3选择调度方式和算法的若干准则

12/22/202261操作系统3.1.3选择调度方式和算法的若干准则12/17/20222．响应时间快：（常用于评价分时系统）概念：键盘提交请求到首次响应时间（1）输入传送时间（2）处理时间（3）响应传送时间3．截止时间的保证（常用于评价实时系统）4．优先权准则：（即需要抢占调度）3.1.3选择调度方式和算法的若干准则12/22/202262操作系统2．响应时间快：（常用于评价分时系统）3.1.3选择调度方式二、面向系统的准则1．吞吐量高（特别用于批处理）：单位时间完成作业数2．处理机利用率好：（因CPU贵，特别用于大中型多用户系统）3．各类资源的平衡利用。（折算标准）3.1.3选择调度方式和算法的若干准则

12/22/202263操作系统二、面向系统的准则3.1.3选择调度方式和算法的若干准则13.2调度算法——是一个资源分配问题3.2.1先来先服务和短作业（进程）优先调度算法1. FCFS优点：简单，有利于长作业即CPU繁忙型作业缺点：没考虑进程的优先级进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.9912/22/202264操作系统3.2调度算法——是一个资源分配问题3.2.1先来先服务和2.短作业(进程)优先调度算法SJ(P)F

：提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量）特点：对长作业不利，有可能得不到服务，不能保证紧迫性作业被及时处理，估计时间不易确定。12/22/202265操作系统2.短作业(进程)优先调度算法SJ(P)F：12/17/2图3.4 FCFS和SJF比较进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间47121418周转时间461011149带权周转时间1225.53.52.8SJF完成时间4918613周转时间4816398带权周转时间12.673.11.52.252.112/22/202266操作系统图3.4 FCFS和SJF比较进程名AB3.2.2高优先权优先调度算法1.优先权调度算法类型(作业、进程)针对进程调度又有如下两种算法：非抢占式优先权算法抢占式优先权算法，实时性更好。12/22/202267操作系统3.2.2高优先权优先调度算法1.优先权调度算法类型(作业、2.优先权类型：①．静态优先权：进程优先权在整个运行期不变。确定优先权依据（1）进程类型（2）进程对资源的需求；（3）根据用户需求。特点：简单，但低优先权作业可能长期不被调度。②．动态优先权：如：优先权随执行时间而下降，随等待时间而升高。12/22/202268操作系统2.优先权类型：12/17/202216操作系统3.2.2高优先权优先调度算法(2)3.高响应比优先算法：响应比Rp=（等待时间＋服务时间）/服务时间

作为优先权优点：长短兼顾缺点：需计算Rp特点：响应比Rp=（tw+ts）/ts（优先权相当于相应比）（1）短作业（ts小，tw相同）RP大。（2）ts（要求服务时间）相同的进程间相当于FCFS。（3）长作业等待一段时间仍能得到服务。12/22/202269操作系统3.2.2高优先权优先调度算法(2)12/17/2022173.2.3基于时间片的轮转调度算法(进程)1.时间片轮转时间片大小的确定太大：退化为FCFS；太小：系统开销过大系统对响应时间的要求；就绪队列中进程的数目；系统的处理能力（CPU能力）：（应保证一个时间片处理完常用命令）12/22/202270操作系统3.2.3基于时间片的轮转调度算法(进程)1.时间片轮转123.2.3基于时间片的轮转调度算法2.多级反馈队列调度特点：长、短作业兼顾，有较好的响应时间（1）短作业一次完成；（2）中型作业周转时间不长；（3）大型作业不会长期不处理。12/22/202271操作系统3.2.3基于时间片的轮转调度算法2.多级反馈队列调度12/就绪队列1至CPUS1就绪队列2S2至CPU就绪队列3S3至CPU就绪队列nSn至CPU时间片：S1<S2<S3<…<Sn图3－5多级反馈队列调度算法12/22/202272操作系统就绪队列1至CPUS1就绪队列2S2至CPU就绪队列3S3至多级反馈队列调度算法示例图12/22/202273操作系统多级反馈队列调度算法示例图12/17/202221操作系统多级反馈队列调度算法小结：首先系统中设置多个就绪队列每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大各个队列按照FCFS调度算法，最后一个队列是按照时间片轮转调度一个新进程就绪后进入第一级队列进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到第一级队列。当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾。当第一级队列为空时，就去调度第二级队列，以此类推当时间片到后，进程放弃CPU，回到下一级队列。12/22/202274操作系统多级反馈队列调度算法小结：首先系统中设置多个就绪队列12/13.3.1实现实时调度的基本条件1．提供必要的调度信息（1）就绪时间；（2）开始/完成截止时间；（3）处理时间；（4）资源要求；（5）优先级；2．系统处理能力强3.3实时调度Ci为处理时间，Pi为周期时间（基于周期性实时任务）12/22/202275操作系统3.3.1实现实时调度的基本条件3.3实时调度Ci为处理时间3.采用抢占调度方式剥夺方式：一般都采用此非剥夺方式（实现简单）：一般应使实时任务较小，以及时放弃CPU。4.具有快速切换机制具有快速响应外部中断能力。快速的任务分派能力3.3实时调度12/22/202276操作系统3.采用抢占调度方式3.3实时调度12/17/202224操3.3.2实时调度算法的分类1.非抢占式调度算法时间片轮转 秒级非抢占式优先权（协同） 秒-毫秒级2.抢占式调度算法时钟中断抢占优先权 毫秒级基于抢占点抢占立即抢占immediatepreemption毫秒-微秒级只要不在临界区即抢占（中断引发）12/22/202277操作系统3.3.2实时调度算法的分类1.非抢占式调度算法12/17/进程1进程2进程n实时进程调度时间实时进程要求调度调度实时进程运行a非抢占轮转调度b非抢占优先权调度当前进程实时进程实时进程要求调度当前进程运行完成调度时间12/22/202278操作系统进程1进程2进程n实时进程调度时间实时进程要求调度调度实时进c基于时钟中断抢占的优先权抢占调度当前进程实时进程实时进程要求调度抢占时刻（其它中断）b立即抢占优先权调度当前进程实时进程实时进程要求调度时钟中断到达时调度时间调度时间12/22/202279操作系统c基于时钟中断抢占的优先权抢占调度当前进程实时进程实时进程3.3.3常用的几种实时调度算法1.最早截止时间优先EDF（earliestdeadlinefirst)算法根据任务的开始截止时间来确定任务的优先级截止时间越早，优先级越高可以是抢占式或非抢占式12/22/202280操作系统3.3.3常用的几种实时调度算法1.最早截止时间优先EDF（最早截止时间优先EDF例134213421234t开始截止时间任务到达任务执行图3－7EDF算法用于非抢占调度方式12/22/202281操作系统最早截止时间优先EDF例134213421234t开始截止时2.最低松弛度优先LLF算法松弛度：若A进程需在200ms时完成，其本身运行需要100ms，当前时刻是10ms，则A的松弛度为：200－100－10＝90ms（松弛度=必须完成时间-其本身运行时间-当前时间）主要用于可抢占的调度方式中12/22/202282操作系统2.最低松弛度优先LLF算法松弛度：12/17/20223最低松弛度优先LLF算法(2)A1(10)A2(10)A3(10)A4(10)t01020304050607080t1=0B1(20)B1(5)B2(15)B2(10)t1t2t3t4t5t6t7t8A1A2A3A4A5A6A7A8B1B2B3020406080100120140160tA/B任务每次必须完成的时间如下：调度情况如下：12/22/202283操作系统最低松弛度优先LLF算法(2)A1(10)A2(10)A3(3.5产生死锁的原因和必要条件3.5.1产生死锁的原因。一、竞争资源引起死锁。1．可剥夺（CPU、内存，）和非剥夺性（打印机，磁带机）资源2．竞争非剥夺性资源——可造成死锁p2R1R2p112/22/202284操作系统3.5产生死锁的原因和必要条件3.5.1产生死锁的原因。p23.5产生死锁的原因和必要条件3．竞争临时性资源临时性资源是指由一个进程产生，被另一个进程使用一段时间后便无用的资源。P2S3S2P1S1P3正常运行情况：P1:Release(S1);Resquest(S3)P2:Release(S2);Resquest(S1)P3:Release(S3);Resquest(S2)产生死锁：P1:Request(S3);Realse(S1)P2:Request(S1);Realse(S2)P3:Request(S2);Realse(S3)12/22/202285操作系统3.5产生死锁的原因和必要条件3．竞争临时性资源P2S3S2二、进程推进顺序不当引起死锁。213DP2Req(R2)P2Req(R1)P1Req(R1)P1Req(R2)P2Rel(R2)P2Rel(R1)P1Rel(R1)P1Rel(R2)412/22/202286操作系统二、进程推进顺序不当引起死锁。213DP2Req(R2)P23.5.2产生死锁的必要条件1．互斥条件（资源的临界性）2．请求和保持条件3．不剥夺条件4．环路等待12/22/202287操作系统3.5.2产生死锁的必要条件1．互斥条件（资源的临界性）13.5.3处理死锁的基本方法

1．预防；破坏4个条件之一：有效，使资源利用率低。2．避免：防止进入不安全态。3．检测：检测到死锁再清除。4．解除：与“检”配套。12/22/202288操作系统3.5.3处理死锁的基本方法1．预防；破坏4个条件之一：有3.6死锁预防和避免3.6.1死锁预防一、互斥条件是资源固有属性，不能避免。二、摒弃请求和保持条件全分配，全释放（AND）缺点：（1）延迟进程运行 （2）资源严重浪费三、摒弃“不剥夺”条件 增加系统开销，且进程前段工作可能失效。12/22/202289操作系统3.6死锁预防和避免3.6.1死锁预防12/17/23.6死锁预防和避免3.6.1死锁预防 四、摒弃“环路”条件有序资源分配法：为资源编号，申请时需按编号进行。缺点：（1）新增资源不便，（原序号已排定）（2）用户不自由（3）资源与进程使用顺序不同造成浪费12/22/202290操作系统3.6死锁预防和避免3.6.1死锁预防12/17/23.6.2系统的安全状态在“避免死锁”方法中的判断条件1.安全状态按某种顺序并发进程都能达到获得最大资源而顺序完成的序列为安全序列。能找到安全序列的状态为安全状态。12/22/202291操作系统3.6.2系统的安全状态在“避免死锁”方法中的判断条件13.6.2系统的安全状态（2）2.安全状态例进程最大需求已分配可用P11053P242P392安全序列：p2p1p312/22/202292操作系统3.6.2系统的安全状态（2）2.安全状态例进程最大需求已3.6.2系统的安全状态（3）3安全——不安全的转换上例中，若P3再申请一台，则不安全进程最大需求已分配可用P11052P242P39312/22/202293操作系统3.6.2系统的安全状态（3）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能否顺序完成。

12/22/202294操作系统3.6.3利用银行家算法避免死锁12/17/202242操3.6.3利用银行家算法避免死锁2．银行家算法

reqi<=needierrorreqi<=availiblock12/22/202295操作系统3.6.3利用银行家算法避免死锁2．银行家算法reqi<3.6.3利用银行家算法避免死锁avail=avail-reqialloci=alloci+reqineedi=needi-reqifinish[i]=.F.needi<=workwork=work+allocifinish[i]=.T.12/22/202296操作系统3.6.3利用银行家算法避免死锁avail=avail-r4实例MaxABCAllocationABCNeedABCAvailableABCp0753010743332p1322200122p2902302600