处理机调度与死锁-严军勇.ppt

《处理机调度与死锁-严军勇.ppt》由会员分享，可在线阅读，更多相关《处理机调度与死锁-严军勇.ppt（71页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang处理机调度与死锁处理机调度与死锁第三章第三章Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang回顾：回顾：回顾：回顾：具有挂起状态的进程状态图具有挂起状态的进程状态图具有挂起状态的进程状态图具有挂起状态的进程状态图执行执行活动活动就绪就绪静止静止就绪就绪活动活动阻塞阻塞静止静止阻塞阻塞激活

2、激活挂起挂起接纳接纳新建新建终止终止分派分派/调度调度时间片用完时间片用完激活激活挂起挂起事件发生事件发生完成完成事件发生事件发生事件等待事件等待Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia WangAbstract1、调度类型、调度类型2、调度准则、调度准则3、调度算法、调度算法4、实时调度、实时调度5、死锁与饥饿、死锁与饥饿Processes scheduling and Deadlock Processes scheduling and Deadlock Apri

3、l 2012,Caixia WangLearning objectives of this partLearning objectives of this partBy the end of this lecture you should be able to:v解释什么是响应时间解释什么是响应时间,周转时间周转时间,截至时间，吞吐量截至时间，吞吐量v理解进程调度的目标、类型、原则理解进程调度的目标、类型、原则v理解决策方式理解决策方式:非抢占非抢占&抢占抢占v分析掌握主要调度算法：分析掌握主要调度算法：FCFS,时间片轮转，短作业时间片轮转，短作业优先，高优先权优先优先，高优先权优先，高响应

4、比优先，反馈高响应比优先，反馈v理解理解实时系统及类型实时系统及类型v 实时操作系统的特征实时操作系统的特征v理解掌握：实时调度，截止调度理解掌握：实时调度，截止调度v理解理解死锁条件、预防死锁死锁条件、预防死锁、避免死锁、避免死锁、检测死锁、检测死锁、解除死锁解除死锁,银行家算法银行家算法(安全状态安全状态 vs.不安全状态不安全状态)Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang调度目标调度目标vResponse time（响应时间）（响应时间）vThrou

5、ghput（系统吞吐量）（系统吞吐量）vProcessor efficiency（处理机效率）（处理机效率）vFairness(公平性，防止进程饥饿公平性，防止进程饥饿)Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang3.1 调度类型调度类型v按调度的层次划分：按调度的层次划分：Long-term scheduling（长程调度）长程调度）Medium-term scheduling（中程调度）中程调度）Short-term scheduling（短程调度）短程调

6、度）Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang长程调度 又又称称为为高高级级调调度度、作作业业调调度度，它它为为被被调调度度作作业业或或用用户户程程序序创创建建进进程程、分分配配必必要要的的系系统统资资源源，并并将将新新创创建建的的进进程程插入插入就绪队列就绪队列，等待短程调度，等待短程调度v作作业业：比比程程序序更更广广泛泛，包包含含通通常常的的程程序序和和数数据据，还还配配有有一一份份作作业业说说明明书书，系系统统根根据据作作业业说说明明书书对对程程序序

7、的的运运行行进进行行控控制制。在在批批处处理理系系统统中中，是是以以作作业业为为基基本本单单位位从从外外存存调入内存的。调入内存的。v作作业业步步：在在作作业业运运行行期期间间，每每个个作作业业都都必必须须经经过过若若干干个个相相对对独独立立又又相相互互关关联联的的顺顺序序加加工工步步骤骤才才能能得得到到结结果果，把把其中的每一个加工步骤成为一个作业步。其中的每一个加工步骤成为一个作业步。v作业步一般分成：编译、连接装配、运行。作业步一般分成：编译、连接装配、运行。Processes scheduling and Deadlock Processes scheduling and Deadlo

8、ck April 2012,Caixia Wangv作作业业控控制制块块（JCB）：作作业业在在系系统统中中的的标标志志，其其中中保保存存了了系统对作业进行管理和调度所需的全部信息。系统对作业进行管理和调度所需的全部信息。v每每当当作作业业进进入入系系统统时时，系系统统便便为为每每个个作作业业建建立立一一个个PCB，根根据据作作业业类类型型将将它它插插入入相相应应的的后后备备队队列列中中。作作业业调调度度程程序序依依据据一一定定的的调调度度算算法法来来调调度度它它们们，被被调调度度到到的的作作业业将会装入内存。将会装入内存。v在在作作业业运运行行期期间间，系系统统就就按按照照JCB中中的的信信

9、息息对对作作业业进进行行控制。控制。v当当一一个个作作业业执执行行结结束束进进入入完完成成状状态态时时，系系统统负负责责回回收收分分配给它的资源，撤销它的作业控制块配给它的资源，撤销它的作业控制块。高级调度（长程调度）Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wangv 作业调度功能：根据作业控制块中的信息，审查系统能否满作业调度功能：根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后足用户作业的资源需求，以及按照一定的算法，

10、从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执必要的资源。然后再将新创建的进程插入就绪队列，准备执行。行。v 作业进入系统后，先驻留在磁盘上（批处理队列中）。长程作业进入系统后，先驻留在磁盘上（批处理队列中）。长程调度从该队列中选择作业，为之创建进程。在每次执行作业调度从该队列中选择作业，为之创建进程。在每次执行作业调度时，都须做出以下两个决定：调度时，都须做出以下两个决定：1)接纳多少个作业：太多或太少都不可接纳多少个作业：太多或太少都不可 2)接纳哪些作业接纳哪些作业：调

11、度算法：调度算法高级调度（长程调度）Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang短程调度v又称为进程调度、低级调度又称为进程调度、低级调度，调度内存中的就绪进程执行。调度内存中的就绪进程执行。v功能功能:决定就绪队列决定就绪队列WhichWhich进程将获得处理机进程将获得处理机 1 1、保存处理机的现场信息，、保存处理机的现场信息，2 2、按某种算法选取进程，、按某种算法选取进程，3 3、把处理机分配给进程。、把处理机分配给进程。v进程调度中的三个基本机制进

12、程调度中的三个基本机制 1 1、排队器、排队器 2 2、分派器、分派器 3 3、上下文切换机制、上下文切换机制v进程调度方式进程调度方式非抢占方式：非抢占方式：简单，实时性差简单，实时性差 抢占方式抢占方式:时间片原则、优先权原则、短作业优先原则。时间片原则、优先权原则、短作业优先原则。Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang中程调度 又又称称为为中中级级调调度度，它它调调度度换换出出到到磁磁盘盘的的进进程程进进入入内内存，准备执行存，准备执行v中程调度中

13、程调度配合配合对换技术对换技术使用。使用。v其目的是其目的是为了提高内存的利用率和系统吞吐量为了提高内存的利用率和系统吞吐量。v在在多多道道程程序序度度允允许许的的情情况况下下，从从外外存存选选择择一一个个挂挂起起状态的进程调度到内存（换入）状态的进程调度到内存（换入）Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang短程短程调度调度中程中程调度调度新建新建就绪就绪执行执行长程长程调度调度阻塞阻塞/挂起挂起阻塞阻塞图图3-1 3-1 调度与进程状态转换调度与进程状态

14、转换就绪就绪/挂起挂起总结总结外存外存内存内存占用占用cpuProcesses scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang3.2.1 3.2.1 3.2.1 3.2.1 调度的队列模型调度的队列模型调度的队列模型调度的队列模型v一、仅有进程调度的队列模型一、仅有进程调度的队列模型就绪队列就绪队列CPU阻塞队列阻塞队列交互用户交互用户时间片完时间片完进程调度进程调度进程完成进程完成等待事件等待事件事事件件出出现现Processes scheduling and Deadlock

15、Processes scheduling and Deadlock April 2012,Caixia Wang3.2.1 3.2.1 3.2.1 3.2.1 调度的队列模型调度的队列模型调度的队列模型调度的队列模型v二、具有高二、具有高/低级模型低级模型就绪队列就绪队列CPU阻塞队列阻塞队列时间片完时间片完进程调度进程调度进程进程完成完成等待事件等待事件1事件事件1出现出现后备队列后备队列阻塞队列阻塞队列等待事件等待事件2事件事件2出现出现作业调度作业调度Processes scheduling and Deadlock Processes scheduling and Deadlock A

16、pril 2012,Caixia Wang3.3.3.3.具有三级调度的调度队列模型具有三级调度的调度队列模型具有三级调度的调度队列模型具有三级调度的调度队列模型就绪队列就绪队列CPU就绪、挂起队列就绪、挂起队列时间片完时间片完进程调度进程调度进程进程完成完成后备队列后备队列阻塞、挂起队列阻塞、挂起队列事件出现事件出现作业调度作业调度阻塞队列阻塞队列等待事件等待事件挂起挂起事件出现事件出现中级调度中级调度交互型作业交互型作业3.2.1 3.2.1 3.2.1 3.2.1 调度队列模型调度队列模型调度队列模型调度队列模型Processes scheduling and Deadlock Proc

17、esses scheduling and Deadlock April 2012,Caixia Wang3.2.2 3.2.2 3.2.2 3.2.2 选择调度方式和算法的若干准则选择调度方式和算法的若干准则选择调度方式和算法的若干准则选择调度方式和算法的若干准则 v一、面向用户的准则一、面向用户的准则1 1周转时间短（常用于批处理系统）周转时间短（常用于批处理系统）概念：作业从提交概念：作业从提交 完成的时间完成的时间.分为：分为：（1 1）驻外等待调度时间）驻外等待调度时间（2 2）驻内等待调度时间）驻内等待调度时间（3 3）执行时间）执行时间（4 4）阻塞时间）阻塞时间Processes

18、 scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wangv一、面向用户的准则一、面向用户的准则平均周转时间平均周转时间 平均带权周转时间平均带权周转时间 可见带权可见带权w w越小越好越小越好,Ts,Ts为实际服务时间。为实际服务时间。3.2.2 3.2.2 3.2.2 3.2.2 选择调度方式和算法的若干准则选择调度方式和算法的若干准则选择调度方式和算法的若干准则选择调度方式和算法的若干准则 Processes scheduling and Deadlock Processes sche

19、duling and Deadlock April 2012,Caixia Wangv一、面向用户的准则一、面向用户的准则2 2响应时间快：（对交互性作业）响应时间快：（对交互性作业）概念：键盘提交请求到首次响应时间概念：键盘提交请求到首次响应时间（1 1）输入传送时间）输入传送时间（2 2）处理时间）处理时间（3 3）响应传送时间）响应传送时间3 3截止时间的保证：即某任务开始执行的最迟时截止时间的保证：即某任务开始执行的最迟时间或必须完成的最迟时间。（特别于实时系统）间或必须完成的最迟时间。（特别于实时系统）4 4优先权准则：（即需要抢占调度）优先权准则：（即需要抢占调度）3.2.2 3.

20、2.2 3.2.2 3.2.2 选择调度方式和算法的若干准则选择调度方式和算法的若干准则选择调度方式和算法的若干准则选择调度方式和算法的若干准则 Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wangv二、面向系统的准则二、面向系统的准则1 1吞吐量高（特别于批处理）：单位时间完成作吞吐量高（特别于批处理）：单位时间完成作业数业数2 2处理机利用率好：（因处理机利用率好：（因CPUCPU贵，特别于大中型多贵，特别于大中型多用户系统）用户系统）3 3各类资源的平衡利用。（

21、？折算标准）各类资源的平衡利用。（？折算标准）3.2.2 3.2.2 3.2.2 3.2.2 选择调度方式和算法的若干准则选择调度方式和算法的若干准则选择调度方式和算法的若干准则选择调度方式和算法的若干准则 Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wangv先来先服务和短作业（进程）优先调度算法先来先服务和短作业（进程）优先调度算法 特点：简单，有利于长作业特点：简单，有利于长作业,即即CPUCPU繁忙性作业繁忙性作业;不不利于短作业。利于短作业。2.2.短作业进

22、程优先调度算法：短作业进程优先调度算法：SJ(P)FSJ(P)F提高了平均周转时间和平均带权周转时间（从而提提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量）高了系统吞吐量）特点：特点：对长作业不利，有可能得不到服务（饥饿）对长作业不利，有可能得不到服务（饥饿）未考虑作业的紧迫程度，不能保证紧急作业被及时未考虑作业的紧迫程度，不能保证紧急作业被及时处理。处理。估计执行时间不易确定估计执行时间不易确定3.3 3.3 3.3 3.3 调度算法调度算法调度算法调度算法是一个资源分配问题是一个资源分配问题是一个资源分配问题是一个资源分配问题 Processes scheduling and

23、Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang 例：例：例：例：FCFSFCFSFCFSFCFS算法实例算法实例算法实例算法实例进程名进程名到达时间到达时间 服务时间服务时间 开始执行开始执行时间时间完成时间完成时间 周转时间周转时间=完成时间完成时间-到达时到达时间间带权周转带权周转时间时间=周转时间周转时间/服务时服务时间间A01B1100C21D3100011111011001101102100100102202199Processes scheduling and Deadlock Processes

24、scheduling and Deadlock April 2012,Caixia Wang图图图图3.4 FCFS3.4 FCFS3.4 FCFS3.4 FCFS和和和和SJFSJFSJFSJF比较比较比较比较 进程名进程名 A B C D E平均平均到达时间到达时间 0 1 2 3 4服务时间服务时间 4 3 5 2 4FCFS完成时间完成时间 周转时间周转时间 带权周转时间带权周转时间SJF完成时间完成时间 周转时间周转时间带权周转时间带权周转时间调度算法调度算法作业情况作业情况47121418461011149122491861348163981Processes scheduling

25、 and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang3.2.2 3.2.2 3.2.2 3.2.2 高优先权优先调度算法高优先权优先调度算法高优先权优先调度算法高优先权优先调度算法v1.1.优先权调度算法类型优先权调度算法类型非抢占式优先权算法非抢占式优先权算法抢占式优先权算法，实时性更好。抢占式优先权算法，实时性更好。v2.2.优先权类型：优先权类型：1 1静态优先权：静态优先权：进程优先权在整个运行期不变。进程优先权在整个运行期不变。确定优先权依据确定优先权依据（1 1）进程类型）进程类型（2 2）进程

26、对资源的需求；）进程对资源的需求；（3 3）根据用户需求。）根据用户需求。特点：简单，但低优先权作业可能长期不被调度。特点：简单，但低优先权作业可能长期不被调度。Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang3.2.2 3.2.2 3.2.2 3.2.2 高优先权优先调度算法高优先权优先调度算法高优先权优先调度算法高优先权优先调度算法(2)(2)(2)(2)v2 2动态优先权：动态优先权：如：优先权描述为如：优先权描述为可见：优先权随执行时间而下降，随等待时间可

27、见：优先权随执行时间而下降，随等待时间而升高。而升高。响应比响应比服务时间服务时间（等待时间服务时间）（等待时间服务时间）Rp=服务时间服务时间（等待时间服务时间）（等待时间服务时间）优先权优先权=服务时间服务时间响应时间响应时间=Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang优点：长短兼顾。优点：长短兼顾。主要体现在以下几个方面：主要体现在以下几个方面：（1 1）如果作业的等待时间相同时，则要求服务的时间愈短，）如果作业的等待时间相同时，则要求服务的时间愈短，

28、其优先权愈高，因而该算法有利于短作业。其优先权愈高，因而该算法有利于短作业。（2 2）当要求服务的时间相同时，作业的优先权决定于其等）当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。是先来先服务。（3 3）对于长作业，作业的优先级可以随等待时间的增加而）对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。从而也可获得处理机。缺点：需计算缺点：需计算RpRp，增加系统开销。，增

29、加系统开销。服务时间服务时间（等待时间服务时间）（等待时间服务时间）Rp=服务时间服务时间响应时间响应时间=Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang3.3.3 3.3.3 3.3.3 3.3.3 基于时间片的轮转调度算法基于时间片的轮转调度算法基于时间片的轮转调度算法基于时间片的轮转调度算法v1.1.时间片轮转时间片轮转时间片大小的确定时间片大小的确定太大（每个进程都能在一个时间片内完成）：退化为太大（每个进程都能在一个时间片内完成）：退化为FCFSFCF

30、S；太小：有利于短作业，频繁地发生中断、进程上下文的太小：有利于短作业，频繁地发生中断、进程上下文的切换，系统开销过大切换，系统开销过大系统对响应时间的要求；系统对响应时间的要求；T=nqT=nq就绪队列中进程的数目；就绪队列中进程的数目；系统的处理能力：（应保证一个时间片处理完常系统的处理能力：（应保证一个时间片处理完常用命令）用命令）例题：见书例题：见书p95,p96p95,p96Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang时间片轮转例题（时间片轮转例题（

31、时间片轮转例题（时间片轮转例题（VISIOVISIO截图）截图）截图）截图）Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang 进程名进程名 A B C D E平均平均到达时间到达时间 0 1 2 3 4服务时间服务时间 4 3 4 2 4RRq=1完成时间完成时间 周转时间周转时间 带权周转时间带权周转时间RRq=4完成时间完成时间 周转时间周转时间带权周转时间带权周转时间时间片时间片作业情况作业情况15121691715111461334711131746910

32、13125Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang3.2.3 3.2.3 3.2.3 3.2.3 基于时间片的轮转调度算法基于时间片的轮转调度算法基于时间片的轮转调度算法基于时间片的轮转调度算法v2.2.多级反馈队列调度多级反馈队列调度调度实施过程：调度实施过程：（1 1）设置多个就绪队列，并为各个队列赋予不同的优先级。）设置多个就绪队列，并为各个队列赋予不同的优先级。在优先级愈高的队列中，为进程执行的时间片愈小。在优先级愈高的队列中，为进程执行的时间片愈

33、小。就绪队列就绪队列1 1至至CPUS1就绪队列就绪队列2 2S2至至CPU就绪队列就绪队列3 3S3至至CPU就绪队列就绪队列n nSn至至CPU时间片：时间片：S1S2S3Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang图图37 多级队列反馈调度算法多级队列反馈调度算法（2）当一个新进程进入内存后，首先将它放入第一队列）当一个新进程进入内存后，首先将它放入第一队列的末尾，按的末尾，按FCFS原则排队等待调度。当轮到该进程执行原则排队等待调度。当轮到该进程执行时

34、，如它能在该时间片内完成，便可准备撤离系统，否则时，如它能在该时间片内完成，便可准备撤离系统，否则进入紧邻的后续队列。进入紧邻的后续队列。（3）仅当第一队列空闲时，调度程序才调度第二队列中）仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第的进程运行；仅当第1-（i-1）队列均为空时）队列均为空时,才会调度第才会调度第i队列中的进程运行。如果处理机正在第队列中的进程运行。如果处理机正在第i队列中为某进程队列中为某进程服务时，又有新进程进入优先级较高的队列，则此时新进服务时，又有新进程进入优先级较高的队列，则此时新进程将抢占正在运行进程的处理机。程将抢占正在运行进程的处理机。特点：长

35、、短作业兼顾，有较好的响应时间特点：长、短作业兼顾，有较好的响应时间（1）短作业一次完成；）短作业一次完成；（2）中型作业周转时间不长；）中型作业周转时间不长；（3）大型作业不会长期不处理。）大型作业不会长期不处理。Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang回顾回顾回顾回顾v1、周转时间、带权周转时间、周转时间、带权周转时间v2、FCFS：对短作业不公平：对短作业不公平v3、短作业：长作业饥饿、短作业：长作业饥饿v4、高优先权：低优先权的可能长期不调度。、高

36、优先权：低优先权的可能长期不调度。v5、高响应比：须计算相应比，增加开销。、高响应比：须计算相应比，增加开销。v6、时间片轮转：时间片长短不易确定。太长等同于、时间片轮转：时间片长短不易确定。太长等同于FCFS，太短频繁中断，增加开销。太短频繁中断，增加开销。v7、多级反馈：最好的调度算法。按不同的优先级设在不同、多级反馈：最好的调度算法。按不同的优先级设在不同的就绪队列。同一队列按的就绪队列。同一队列按FCFS调度。不同队列按优先级高调度。不同队列按优先级高低进行调度。优先级高的时间片设置短些。低进行调度。优先级高的时间片设置短些。Processes scheduling and Deadl

37、ock Processes scheduling and Deadlock April 2012,Caixia Wangv实现实时调度的基本条件实现实时调度的基本条件1 1提供必要的调度信息提供必要的调度信息（1 1）就绪时间；）就绪时间；（2 2）开始）开始/完成截止时间；完成截止时间；（3 3）处理时间；）处理时间；（4 4）资源要求；）资源要求；（5 5）优先级；）优先级；2 2系统处理能力强系统处理能力强3.4 3.4 3.4 3.4 实时调度实时调度实时调度实时调度Ci为处理时间，为处理时间，Pi为周期时间（基于周期性实时任务）为周期时间（基于周期性实时任务）Processes sc

38、heduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang例例:如果一个单处理器实时系统中有如果一个单处理器实时系统中有3 3个周期性任务，个周期性任务，它们的周期分别为它们的周期分别为80ms80ms、40ms40ms和和240ms240ms，需要，需要CPUCPU处理处理的时间分别为的时间分别为20ms20ms、10ms10ms和和40ms40ms，问该实时系统，问该实时系统能否调度这能否调度这3 3个周期性任务？个周期性任务？所以，该系统可调度这所以，该系统可调度这3 3个周期性实时任务。个

39、周期性实时任务。但是，如果这但是，如果这3 3个周期性实时任务需要处理器处理个周期性实时任务需要处理器处理的时间分别变为的时间分别变为30ms30ms、20ms20ms和和60ms60ms时，则：时，则：系统不能调度这系统不能调度这3 3个周期性实时任务。个周期性实时任务。Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang如果将该单处理器系统变为具有两个处理器的系统，如果将该单处理器系统变为具有两个处理器的系统，则：则：则双处理器系统可以调度这则双处理器系统可以调度

40、这3 3个周期性实时任务。个周期性实时任务。Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wangv实现实时调度的基本条件实现实时调度的基本条件3.3.采用抢占调度方式采用抢占调度方式剥夺方式：一般都采用此剥夺方式：一般都采用此非剥夺方式（实现简单）：一般应使实时任务较小，非剥夺方式（实现简单）：一般应使实时任务较小，以及时放弃以及时放弃CPUCPU。4.4.具有快速切换机制具有快速切换机制具有快速响应外部中断能力。具有快速响应外部中断能力。快速任务分派能力快速任务分派

41、能力3.4 3.4 3.4 3.4 实时调度实时调度实时调度实时调度Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang3.4.2 3.4.2 3.4.2 3.4.2 实时调度算法的分类实时调度算法的分类实时调度算法的分类实时调度算法的分类v1.1.非抢占式调度算法非抢占式调度算法时间片轮转时间片轮转 秒级秒级非抢占优先权（协同）非抢占优先权（协同）秒秒-毫秒级毫秒级v2.2.抢占式调度算法抢占式调度算法时钟中断抢占优先权时钟中断抢占优先权 毫秒级毫秒级基于抢占点抢占

42、基于抢占点抢占立即抢占立即抢占immediate preemption immediate preemption 毫秒毫秒-微秒级微秒级只要不在临界区即抢占（中断引发）只要不在临界区即抢占（中断引发）进程1进程2进程n实时进程调度时间调度时间实时进程要求调度实时进程要求调度调度实时进程运行调度实时进程运行a 非抢占轮转调度非抢占轮转调度当前进程实时进程实时进程要求调度实时进程要求调度当前进程运行完成当前进程运行完成b 非抢占优先权调度非抢占优先权调度调度时间调度时间c 基于时钟中断抢占的优先权抢占调度基于时钟中断抢占的优先权抢占调度当前进程实时进程实时进程要求调度实时进程要求调度抢占时刻（其它

43、中断）抢占时刻（其它中断）d 立即抢占优先权调度立即抢占优先权调度当前进程实时进程实时进程要求调度实时进程要求调度时钟中断到达时时钟中断到达时调度时间调度时间调度时间调度时间Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang3.4.3 3.4.3 3.4.3 3.4.3 常用的几种实时调度算法常用的几种实时调度算法常用的几种实时调度算法常用的几种实时调度算法v1.1.最早截止时间优先最早截止时间优先EDFEDF（earliest deadline first)ear

44、liest deadline first)算算法法根据任务的截止时间来确定任务的优先级根据任务的截止时间来确定任务的优先级截止时间越早，优先级越高截止时间越早，优先级越高可以是抢占式或非抢占式可以是抢占式或非抢占式Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang1.1.1.1.最早截止时间优先最早截止时间优先最早截止时间优先最早截止时间优先EDFEDFEDFEDF例例例例1342134212 34t开始截止时间开始截止时间任务到达任务到达任务执行任务执行图图39

45、EDF算法用于算法用于非抢占非抢占调度方式调度方式1)非抢占非抢占调度方式用于非周期实时任务调度方式用于非周期实时任务Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang2)抢占抢占调度方式用于周期实时任务调度方式用于周期实时任务A的周期时间是的周期时间是20ms，每个周期的处理时间是，每个周期的处理时间是10ms;B的周期时间是的周期时间是50ms，每个周期的处理时间是，每个周期的处理时间是25ms;A的到达时间为的到达时间为0，20，40，最后期限为最后期限为20

46、，40，60，B的到达时间为的到达时间为0，50，100，最后期限为最后期限为50，100，150，具体执行情况将教材具体执行情况将教材p101图图3-10。Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia WangProcesses scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang2.2.2.2.最低松弛度优先最低松弛度优先最低松弛度优先最低松弛度优先LLFLL

47、FLLFLLF算法算法算法算法v松弛度：截止时间松弛度：截止时间-运行时间运行时间-当前时间当前时间若若A A进程需在进程需在200ms200ms时完成，其本身运行需要时完成，其本身运行需要100ms100ms，当，当前时刻是前时刻是10ms10ms，则，则A A的松弛度为：的松弛度为：20020010010010109090主要用于可抢占的调度方式中主要用于可抢占的调度方式中例：例：A1A2A3A4A5A6A7A8B1B2B3020406080 100120 140160t图图311 A/B任务每次必须完成的时间任务每次必须完成的时间Processes scheduling and Dead

48、lock Processes scheduling and Deadlock April 2012,Caixia Wang最低松弛度优先最低松弛度优先最低松弛度优先最低松弛度优先LLFLLFLLFLLF算法算法算法算法(2)(2)(2)(2)A1(10)A2(10)A3(10)A4(10)t01020304050607080t1=0B1(20)B1(5)B2(15)B2(10)t1t2t3t4t5t6t7t8图图312 利用利用LLF算法进行调度的情况算法进行调度的情况注意：当一个任务结束注意：当一个任务结束或者有任务的松弛度为或者有任务的松弛度为0时时才进行比较才进行比较Processes

49、scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang3.5 3.5 3.5 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件产生死锁的原因和必要条件产生死锁的原因和必要条件v产生死锁的原因产生死锁的原因 A A、竞争资源、竞争资源 B B、进程间推进顺序非法、进程间推进顺序非法v一、竞争资源引起死锁。一、竞争资源引起死锁。1 1可剥夺（可剥夺（CPUCPU、内存，）和非剥夺性（打印机，磁、内存，）和非剥夺性（打印机，磁带机）资源带机）资源2 2竞争非剥夺性资源竞争非剥夺性资源可造

50、成死锁可造成死锁 p1p2R1R2Processes scheduling and Deadlock Processes scheduling and Deadlock April 2012,Caixia Wang3.5 3.5 3.5 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件产生死锁的原因和必要条件产生死锁的原因和必要条件v3 3竞争临时性资源竞争临时性资源临时性资源是指由一个进程产生，被另一个进程使用临时性资源是指由一个进程产生，被另一个进程使用一段时间后便无用的资源。一段时间后便无用的资源。如如S1,S2,S3S1,S2,S3为临时性资源。为临时性资源。p1p3S3S1S