第三章处理剂调度与死锁pptx

1、第三章处理机调度与死锁第三章处理机调度与死锁 3.1 处理机调度的层次处理机调度的层次和调度算法的目标和调度算法的目标3.2 作业与作业调度作业与作业调度3.3 进程调度进程调度3.4 实时调度实时调度 3.5 死锁概述死锁概述3.6 预防死锁的方法预防死锁的方法3.7 避免死锁避免死锁3.8 死锁的检测与解除死锁的检测与解除 调调度度短程调度：短程调度：即进程调度，运行频率最高，在分时系即进程调度，运行频率最高，在分时系 统中通常是统中通常是10100 ms便进行一次进程调度便进行一次进程调度。用。用于选择就绪队列中哪个进程获得于选择就绪队列中哪个进程获得CPU,多道、实时、多道、实时、分时

2、均有；分时均有；中程调度：中程调度：将进程在内存与外存间调入调出。运将进程在内存与外存间调入调出。运行行 频率基本上介于短程、长程调度频率基本上介于短程、长程调度之间，实际就之间，实际就 是存储器置换功能是存储器置换功能 ；长程调度：长程调度：周期较长大约几分钟一周期较长大约几分钟一次，决定处于次，决定处于后备队列中的那个几个作业调入内存，主要用于后备队列中的那个几个作业调入内存，主要用于多道批处理系统，分时、实时中不设置；多道批处理系统，分时、实时中不设置；3.1处理机调度的层次和调度算法的处理机调度的层次和调度算法的目标目标3.1.1 3.1.1 处理机的调度层次处理机的调度层次3.1.2

3、3.1.2处理机调度算法的目标处理机调度算法的目标1 1面向用户的准则面向用户的准则 (1) (1) 周转时间短。周转时间短。 周转时间：从作业被提交给系统开始，到作业完成周转时间：从作业被提交给系统开始，到作业完成的时间间隔。的时间间隔。周周转转时时间间1.作业在外存后备队列上等待作业在外存后备队列上等待(作业作业)调度的时间调度的时间2.进程在就绪队列上等待进程调度的时间进程在就绪队列上等待进程调度的时间3.进程在进程在CPU上执行的时间上执行的时间4.进程等待进程等待I/O操作完成的时间操作完成的时间niiTnT11niiTTnW1s1带权周转时间：带权周转时间：作业的周转时间作业的周转

4、时间系统提供服务的时间系统提供服务的时间平均带权周转时间：平均带权周转时间： 作业周转时间越短越好。作业周转时间越短越好。平均周转时间越短越好。平均周转时间越短越好。用户：用户： 系统：系统：平均周转时间：平均周转时间：(2) 响应时间快。响应时间快。 是分时系统中进程调度算法选择重要准则之一。是分时系统中进程调度算法选择重要准则之一。 响应时间：响应时间：从用户通过键盘提交一个请求开始，直至从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。系统首次产生响应为止的时间。响响应应时时间间1.1.从键盘输入的请求信息传送到处理机的时间从键盘输入的请求信息传送到处理机的时间2.2.处理

5、机对请求信息进行处理的时间处理机对请求信息进行处理的时间3.3.将所形成的响应信息回送到终端显示器的时间将所形成的响应信息回送到终端显示器的时间(3) (3) 截止时间的保证。截止时间的保证。 是选择实时调度算法的重要准则。是选择实时调度算法的重要准则。(4) (4) 优先权准则。优先权准则。 优先权优先权+ +抢占式调度抢占式调度2 2面向系统的准则面向系统的准则 (1) 系统吞吐量高。系统吞吐量高。 吞吐量：单位时间内系统所完成的作业数。吞吐量：单位时间内系统所完成的作业数。 是选择批处理作业调度的重要准则。是选择批处理作业调度的重要准则。 (2) 处理机利用率好。处理机利用率好。 (3)

6、 各类资源的平衡利用。各类资源的平衡利用。 在大、中型系统中，不仅要使处理机的利用率高，在大、中型系统中，不仅要使处理机的利用率高，而且还应能有效地利用其它各类资源，如内存、外而且还应能有效地利用其它各类资源，如内存、外存和存和I/O设备等。设备等。3. 2 3. 2 作业与作业调度作业与作业调度3.2.13.2.1批处理系统中的作业批处理系统中的作业1 1作业和作业步作业和作业步(1) 作业作业(Job)：程序和数据：程序和数据+ +作业说明书。作业说明书。 作作业业用户角度：用户提交给计算机进行加工的一个用户角度：用户提交给计算机进行加工的一个 任务，是用户向计算机提交工作的基本单位任务，

7、是用户向计算机提交工作的基本单位系统角度：由用户程序、数据、作业说明书组系统角度：由用户程序、数据、作业说明书组成，系统通过作业说明书控制程序和数据。成，系统通过作业说明书控制程序和数据。终端型作业终端型作业：前台作业、联机作业，针对：前台作业、联机作业，针对分时实时系统，需要用户与计算机交互，分时实时系统，需要用户与计算机交互，优先级高于批处理作业。优先级高于批处理作业。批量型作业批量型作业：后台作业、脱机作业，针对：后台作业、脱机作业，针对批处理系统，批量型作业放在文件中如批处理系统，批量型作业放在文件中如MS-DOS中为中为.bat文件。文件。作作业业说说明明书书1.作业基本情况描述：用

8、户名、作业名、作业基本情况描述：用户名、作业名、 使用语言使用语言2.作业控制描述：控制方式，出错处理作业控制描述：控制方式，出错处理3.作业资源要求描述：内存空间，处理机作业资源要求描述：内存空间，处理机 优先级优先级作业说明书由作业说明书由作业控制语言作业控制语言编写，随同作业编写，随同作业一起提交给系统一起提交给系统 (2) (2) 作业步作业步(Job Step)(Job Step)： 每个作业分成若干个相对独立，又相互关联的顺每个作业分成若干个相对独立，又相互关联的顺序加工步骤，每一个加工步骤称为一个作业步。序加工步骤，每一个加工步骤称为一个作业步。 作业可分成三个作业步：作业可分成

9、三个作业步：“编译编译”: :源程序编译后产生若干个目标程序段；源程序编译后产生若干个目标程序段；“连结装配连结装配”: :将多个目标程序段装配成目标程序；将多个目标程序段装配成目标程序；“运行运行”: :将可执行目标程序读入内存运行；将可执行目标程序读入内存运行；(3) 作业流作业流：若干个作业进入系统后，被依次存放：若干个作业进入系统后，被依次存放在外存上，这便形成了输入的作业流；在操作系统在外存上，这便形成了输入的作业流；在操作系统的控制下，逐个作业进行处理，于是便形成了处理的控制下，逐个作业进行处理，于是便形成了处理作业流。作业流。 2 2作业控制块作业控制块JCBJCB(Job Co

10、ntrol Block)(Job Control Block) 1 1个作业设置个作业设置1 1个个JCBJCB，其中保存了系统对作业进，其中保存了系统对作业进行管理和调度所需的全部信息，是作业在系统中存行管理和调度所需的全部信息，是作业在系统中存在的标志。在的标志。 JCB中所包含的内容因系统而异，通常包含：作中所包含的内容因系统而异，通常包含：作业标识、用户名称、用户帐户、作业类型业标识、用户名称、用户帐户、作业类型(CPU 繁忙繁忙型、型、I/O 繁忙型、批量型、终端型繁忙型、批量型、终端型)、作业状态、调、作业状态、调度信息度信息(优先级、作业已运行时间优先级、作业已运行时间)、资源需

11、求、资源需求(预计预计运行时间、要求内存大小、要求运行时间、要求内存大小、要求I/O设备的类型和数设备的类型和数量等量等)、进入系统时间、开始处理时间、作业完成时、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况等。间、作业退出时间、资源使用情况等。 3 32.2 2.2 作业调度的主要任务作业调度的主要任务 按照一定的算法从按照一定的算法从外存外存的后备队列中选取某些作的后备队列中选取某些作业调入业调入内存内存，并为之创建进程、分配必要的资源。，并为之创建进程、分配必要的资源。 系统在选择作业调度算法时，既应考虑用户的要系统在选择作业调度算法时，既应考虑用户的要求，又能确

12、保系统具有较高的效率。求，又能确保系统具有较高的效率。 每次执行作业调度时，都须做出以下两个决定：每次执行作业调度时，都须做出以下两个决定： 1 1. .决定决定接纳多少个作业接纳多少个作业取决于多道程序度。不能太多也不能太少。取决于多道程序度。不能太多也不能太少。 多道程序度的确定应根据多道程序度的确定应根据系统的规模系统的规模和和运行速运行速度度等。等。 2 2. .决定决定接纳哪些作业接纳哪些作业 应将哪些作业从外存调入内存，取决于所采用的应将哪些作业从外存调入内存，取决于所采用的调度算法。调度算法。 常用作业调度算法：常用作业调度算法： FCFSFCFS调度算法；调度算法； SCFSC

13、F调度算法；调度算法； 基于作业优先级基于作业优先级的调度算法；的调度算法； “响应比高者优先响应比高者优先” 调度算法。调度算法。 分时系统、实时系统中不需要作业调度。分时系统、实时系统中不需要作业调度。 3.2.33.2.3先来先服务和短先来先服务和短作业优先作业优先调度算调度算法法1 1先来先服务调度算法先来先服务调度算法先来先服务先来先服务(FCFS): :最简单的调度算法，既可用最简单的调度算法，既可用于作业调度，也可用于进程调度。于作业调度，也可用于进程调度。 例：四个作业（进程）按先后顺序到达，已知要例：四个作业（进程）按先后顺序到达，已知要求服务的时间，求各自的周转时间及带权周

14、转时间。求服务的时间，求各自的周转时间及带权周转时间。进程名进程名 到达时间到达时间服务时间服务时间开始执行时间开始执行时间完成时间完成时间周转时间周转时间带权周带权周转时间转时间ABCD0123110011000111110110011011021001001022021991.99服务时间服务时间周转时间周转时间=完成时间完成时间-到达时间到达时间带权周转时间带权周转时间=周转时间周转时间/服务时间服务时间结果分析：结果分析： 短作业短作业C C的带权周转时间高达的带权周转时间高达100100，是不能容忍，是不能容忍的；长作业的；长作业D D的带权周转时间仅为的带权周转时间仅为1.991.

15、99。结论：结论：FCFS算法比较有利于长作业算法比较有利于长作业(进程进程)，而不，而不利于短作业利于短作业(进程进程)。 长作业：即长作业：即CPUCPU繁忙型繁忙型的作业，需要大量的的作业，需要大量的CPUCPU时间进行计算很少请求时间进行计算很少请求I/O(I/O(通常的科学计算通常的科学计算) )。 短作业：即短作业：即I/OI/O繁忙型繁忙型作业，作业，CPUCPU进行处理时需进行处理时需频繁地请求频繁地请求I/O(I/O(大多数事务处理大多数事务处理) )。 2 2短作业短作业( (进程进程) )优先调度算法优先调度算法 SJ(P)FSJ(P)F算法：既用于作业调度也用于进程调度

16、。算法：既用于作业调度也用于进程调度。例：有五个进程例：有五个进程A A、B B、C C、D D、E E，它们到达的时间分，它们到达的时间分别是别是0 0、1 1、2 2、3 3和和4 4，所要求的服务时间分别是，所要求的服务时间分别是4 4、3 3、5 5、2 2和和4 4，计算每个进程的周转时间和带权周转时间。，计算每个进程的周转时间和带权周转时间。 并将并将SJ(P)FSJ(P)F算法与算法与FCFSFCFS算法做对比。算法做对比。图图3-4FCFS和和SJF调度算法的性能比较调度算法的性能比较 结果分析：结果分析： 1)1)采用采用SJ(P)FSJ(P)F算法，短作业算法，短作业D D

17、周转时间由原来的周转时间由原来的( (用用FCFSFCFS算法时算法时)11)11降为降为3 3；而平均带权周转时间从；而平均带权周转时间从5.55.5降到降到1.51.5。 2)2)系统平均周转时间由系统平均周转时间由9 9变为变为8 8，平均带权周转时，平均带权周转时间由间由2.82.8变为变为2.12.1。结论：采用结论：采用SJFSJF调度算法，系统不论是平均周转时间调度算法，系统不论是平均周转时间还是平均带权周转时间，都有较明显的改善，还是平均带权周转时间，都有较明显的改善，SJFSJF能能有效地降低作业的平均等待时间提高系统吞吐量。有效地降低作业的平均等待时间提高系统吞吐量。 SJ

18、(P)FSJ(P)F调度算法的缺点：调度算法的缺点：(1)(1)对长作业不利：如作业对长作业不利：如作业C C。队列中长作业长。队列中长作业长时间不被调度。时间不被调度。(2)(2)未考虑作业的紧迫程度，不能保证紧迫性作未考虑作业的紧迫程度，不能保证紧迫性作业业( (进程进程) )会被及时处理。会被及时处理。(3) (3) 作业作业( (进程进程) )的长短是根据用户所提供的估的长短是根据用户所提供的估计执行时间而定的，不准确，致使该算法不一定能计执行时间而定的，不准确，致使该算法不一定能真正做到短作业优先调度。真正做到短作业优先调度。 3.2.4 3.2.4 优先级调度算法和高响应比优先优先

19、级调度算法和高响应比优先调度算法调度算法1 1优先权调度算法优先权调度算法(HPF)的类型的类型 为了照顾紧迫型作业。为了照顾紧迫型作业。 既是作业调度算法，也是进程调度算法。既是作业调度算法，也是进程调度算法。 该算法又可进一步分成如下两种：该算法又可进一步分成如下两种： 1) 1) 非抢占式优先权算法非抢占式优先权算法一旦分配处理机不允许剥夺。每次调度都找优先一旦分配处理机不允许剥夺。每次调度都找优先权最高的进程（作业）。权最高的进程（作业）。 主要用于批处理系统中和某些对实时性要求不严主要用于批处理系统中和某些对实时性要求不严的实时系统中。的实时系统中。 2) 2) 抢占式优先权调度算法

20、抢占式优先权调度算法优先级高的进程抢占优先级低的进程的处理机。优先级高的进程抢占优先级低的进程的处理机。因此，在采用这种调度算法时，每当系统中出现一因此，在采用这种调度算法时，每当系统中出现一个新的就绪进程时，就将其优先权与正在执行的进个新的就绪进程时，就将其优先权与正在执行的进程的优先权进行比较。程的优先权进行比较。 这种抢占式的优先权调度算法能更好地满足紧这种抢占式的优先权调度算法能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系迫作业的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。统中，以及对性能要求较高的批处理和分时系统中。 2 2高响应比高

21、响应比优先调度优先调度算法（动态优先权）算法（动态优先权）要求服务时间要求服务时间等待时间优先权由于等待时间与服务时间之和就是系统对该作业的由于等待时间与服务时间之和就是系统对该作业的响应时间，故该优先权又相当于响应比响应时间，故该优先权又相当于响应比RP。据此，又可。据此，又可表示为：表示为： 要求服务时间响应时间要求服务时间要求服务时间等待时间PR要求服务时间响应时间要求服务时间要求服务时间等待时间PR1+等待时间等待时间要求服务时间要求服务时间由上式可以看出：由上式可以看出：(1)(1)若等待时间相同，则要求服务的时间愈短，其优若等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算

22、法有利于短作业。先权愈高，因而该算法有利于短作业。(2)(2)当要求服务的时间相同时，等待时间愈长，其优当要求服务的时间相同时，等待时间愈长，其优先权愈高，因而实现是先来先服务。先权愈高，因而实现是先来先服务。 (3)(3)对于长作业，作业的优先级可以随等待时间的增对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。很高，从而也可获得处理机。 要求服务时间响应时间要求服务时间要求服务时间等待时间PR1+等待时间等待时间要求服务时间要求服务时间优点：既照顾了短作业，又考虑了作业到达的先

23、后优点：既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务。次序，不会使长作业长期得不到服务。缺点：每要进行调度之前都须先做响应比的计算，增加缺点：每要进行调度之前都须先做响应比的计算，增加系统开销。系统开销。 3.3进程调进程调 度度3.3.1 进程调度的任务、机制和方式进程调度的任务、机制和方式 1.进程调度的任务进程调度的任务 1)保存处理机的现场信息保存处理机的现场信息 2)按算法选取进程按算法选取进程 3)把处理机分配给进程把处理机分配给进程 2.进程调度机制进程调度机制 1)排队器：将就绪进程按一定策略排成一个或多个排队器：将就绪进程按一定策略排成一个或多个队列

24、；队列； 2)分派器：按调度算法选择进程，分配处理机；分派器：按调度算法选择进程，分配处理机； 3)上下文切换器：两次上下文切换上下文切换器：两次上下文切换 a.移出当前进程上下文，切入分配程序上下文；移出当前进程上下文，切入分配程序上下文； b.移出分配程序上下文，切入新调度进程上下文；移出分配程序上下文，切入新调度进程上下文；3.进程调度方式进程调度方式 1)非抢占方式非抢占方式 此时引起调度的原因：此时引起调度的原因： a)正在执行的进程运行完毕；正在执行的进程运行完毕； b) 正在执行的进程提出正在执行的进程提出I/O操作而暂停；操作而暂停； c)正在执行的进程通信或同步过程执行原正在

25、执行的进程通信或同步过程执行原语操作，如阻塞原语；语操作，如阻塞原语； 2)抢占方式抢占方式 若能抢占，必须遵循的原则：若能抢占，必须遵循的原则： a)优先权原则优先权原则 b)短进程优先原则短进程优先原则 c)时间片原则时间片原则3.3.2 轮转调度算法（轮转调度算法（RR）1.轮转法的基本原理轮转法的基本原理进程进程n.进程进程3进程进程2进程进程1分配分配CPU按按FCFS排队排队时间片用完时间片用完2.进程切换时机进程切换时机 1)若时间片尚未用完正在运行的进程结束，则若时间片尚未用完正在运行的进程结束，则调度进程并启动一个新的时间片；调度进程并启动一个新的时间片； 2)时间片用完时调

26、度另外进程；时间片用完时调度另外进程； 3.3.时间片时间片大小的确定大小的确定时间片的大小对系统性能有很大的影响。时间片的大小对系统性能有很大的影响。 时间片太小：有利于短作业；但会频繁地发生中断、时间片太小：有利于短作业；但会频繁地发生中断、进程上下文的切换，从而增加系统的开销。进程上下文的切换，从而增加系统的开销。 时间片太长：每个进程都能在一个时间片内完成退化时间片太长：每个进程都能在一个时间片内完成退化为为FCFSFCFS算法，无法满足交互式用户的需求。算法，无法满足交互式用户的需求。例：例：A,B,C,D,EA,B,C,D,E五个进程分别在五个进程分别在0,1,2,3,40,1,2

27、,3,4时刻到达系时刻到达系统，要求服务时间分别是统，要求服务时间分别是4 4，3,4,2,43,4,2,4，时间片为，时间片为q q。3.3.3 3.3.3 优先级调度算法优先级调度算法 1. 1.优先级调度算法的类型优先级调度算法的类型 1 1）非抢占式优先级调度算法）非抢占式优先级调度算法 2 2）抢占式优先级调度算法）抢占式优先级调度算法2.2.优先权的类型优先权的类型静态优先权静态优先权 动态优先权动态优先权1) 1) 静态优先权静态优先权静态优先权是在创建进程时确定的静态优先权是在创建进程时确定的，且在进，且在进程的整个运行期间保持不变。程的整个运行期间保持不变。 优先权用某一范围

28、内的一个整数来表示优先权用某一范围内的一个整数来表示: :如，如，07或或0255中的某一整数，称为优先数。中的某一整数，称为优先数。 有的系统用有的系统用“0”表示最高优先权，当数值愈表示最高优先权，当数值愈大时，其优先权愈低；而有的系统恰恰相反。大时，其优先权愈低；而有的系统恰恰相反。 确定进程优先权的依据：确定进程优先权的依据： (1)(1)进程类型进程类型。 系统进程、一般用户进程。系统进程、一般用户进程。 (2)(2)进程对资源的需求进程对资源的需求。 ( (3)3)用户要求用户要求。 用户进程的紧迫程度。用户进程的紧迫程度。 优点优点：简单易行，系统开销小。：简单易行，系统开销小。

29、 缺点缺点：不够精确，可能出现优先权低的作业：不够精确，可能出现优先权低的作业(进程进程)长期没有被调度的情况。长期没有被调度的情况。 适用范围：要求不高的系统适用范围：要求不高的系统。2) 2) 动态优先权动态优先权创建进程时所赋予的优先权可以随进程的推创建进程时所赋予的优先权可以随进程的推进或随其等待时间的增加而改变的。进或随其等待时间的增加而改变的。 3.3.5 3.3.5 多级反馈队列调度算法多级反馈队列调度算法3.3.4 3.3.4 多队列调度算法多队列调度算法 原理：将就绪队列从一个拆分成多个，不同的就绪原理：将就绪队列从一个拆分成多个，不同的就绪队列设置不同的优先级。队列设置不同

30、的优先级。 (1)(1)设置多个就绪队列，每个队列优先级不同、时间片也设置多个就绪队列，每个队列优先级不同、时间片也不同。不同。 第一个队列的优先级最高，其余各队列的优先权逐个第一个队列的优先级最高，其余各队列的优先权逐个降低。降低。 优先权愈高的队列时间片就愈小。优先权愈高的队列时间片就愈小。 第第i+1i+1个队列的时间片比第个队列的时间片比第i i个时间片长一倍。个时间片长一倍。就绪队列 1就绪队列 2就绪队列 3就绪队列 nS1S2S3至CPU至CPU至CPU至CPU(时间片： S1 S2 S3)(2)(2)新进程进入内存后，先放入第一队列的末尾按新进程进入内存后，先放入第一队列的末尾

31、按FCFSFCFS调度。当该进程执行时，如能在时间片内完成，便可撤调度。当该进程执行时，如能在时间片内完成，便可撤离系统；如未完成，便将该进程转入第二队列的末尾，离系统；如未完成，便将该进程转入第二队列的末尾，再按再按FCFSFCFS调度执行；以此类推。调度执行；以此类推。 (3)(3)仅当第一队列空闲时，调度程序才调度第二队列中仅当第一队列空闲时，调度程序才调度第二队列中的进程；以此类推。如处理机正在第的进程；以此类推。如处理机正在第i i队列中为某进程队列中为某进程服务，又有新进程进入优先权较高的队列，新进程将抢服务，又有新进程进入优先权较高的队列，新进程将抢占处理机并把正在运行的进程放回

32、到第占处理机并把正在运行的进程放回到第i i队列的末尾。队列的末尾。 3 3多级反馈队列调度算法的性能多级反馈队列调度算法的性能(1)(1)终端型作业用户。终端型作业用户。 作业通常较小，系统只要能使这些作业作业通常较小，系统只要能使这些作业( (进程进程) )在第在第一队列所规定的时间片内完成，便可使终端型作业用户一队列所规定的时间片内完成，便可使终端型作业用户都感到满意。都感到满意。 (2)(2)短批处理作业用户。短批处理作业用户。 与终端型作业类似，周转时间较短。与终端型作业类似，周转时间较短。(3)(3)长批处理作业用户。长批处理作业用户。 作业依次在第作业依次在第1 1，2 2，n

33、n个队列中按轮转方式运行个队列中按轮转方式运行不必担心长期得不到处理。不必担心长期得不到处理。 例：例：A,B,C,D,E五个进程，到达时间分别为五个进程，到达时间分别为0,1,2,3,4,要要求服务时间分别是求服务时间分别是4,3,4,2,4。共有三个就绪队列：。共有三个就绪队列：队列队列q=2；队列队列q=4；队列队列q=8。试求每个时间片。试求每个时间片运行哪个进程，其周转时间、带权周转时间各是多少？运行哪个进程，其周转时间、带权周转时间各是多少？3.3.6 基于公平原则的调度算法基于公平原则的调度算法 1.保证调度算法保证调度算法 2.公平分享调度算法公平分享调度算法3.4实实 时时

34、调调 度度 3.4.13.4.1实现实时调度的基本条件实现实时调度的基本条件1 1系统提供有关任务的必要信息系统提供有关任务的必要信息 (1) 就绪时间。这是该任务成为就绪状态的起始时间。就绪时间。这是该任务成为就绪状态的起始时间。周期任务：是事先预知的一串时间序列。周期任务：是事先预知的一串时间序列。 (2)(2)开始截止时间和完成截止时间。开始截止时间和完成截止时间。 (3)(3)处理时间。处理时间。 指一个任务从开始执行直至完成所需的时间。指一个任务从开始执行直至完成所需的时间。 (4)(4)资源要求。资源要求。 (5)(5)优先级。优先级。 “绝对绝对”优先级；优先级； “相对相对”优

35、先级。优先级。 2 2系统处理能力强系统处理能力强 若处理机的处理能力不够强，则有可能因处理机忙不若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理，从而导致发过来而使某些实时任务不能得到及时处理，从而导致发生难以预料的后果。假定系统中有生难以预料的后果。假定系统中有m个周期性的硬实时个周期性的硬实时任务，它们的处理时间可表示为任务，它们的处理时间可表示为Ci，周期时间表示为，周期时间表示为Pi，则在单处理机情况下，必须满足下面的限制条件则在单处理机情况下，必须满足下面的限制条件： 11miiiPC 限制条件简化：假定系统内有限制条件简化：假定系统内有m m个周

36、期相同的硬实时个周期相同的硬实时任务，处理时间也相同均为任务，处理时间也相同均为c,c,则周期时间则周期时间p p应应=m x c,=m x c,系统才是可调度的。系统才是可调度的。 假如系统中有假如系统中有6 6个硬实时任务，周期时间都是个硬实时任务，周期时间都是 50 ms50 ms，而每次的处理时间为而每次的处理时间为 10 ms10 ms，则不难算出系统是不可调，则不难算出系统是不可调度的。度的。解决的方法是解决的方法是提高系统的处理能力提高系统的处理能力，其途径有二：，其途径有二：1.1.仍是单处理机系统，但增强其处理能力减少对每一个仍是单处理机系统，但增强其处理能力减少对每一个任务

37、的处理时间；任务的处理时间；2. 2. 采用多处理机系统。采用多处理机系统。 若系统中处理机数为若系统中处理机数为N，则应将上述限制条件改为：，则应将上述限制条件改为： NPCmiii13.4.2实时调度算法的分类实时调度算法的分类分分类类非抢占式非抢占式抢占式抢占式轮转调度算法轮转调度算法优先调度算法优先调度算法立即抢占式优先权调度算法立即抢占式优先权调度算法基于时钟中断的抢占基于时钟中断的抢占式优先权调度算法式优先权调度算法 1 1非抢占式调度算法非抢占式调度算法 1) 1) 非抢占式非抢占式轮转调度轮转调度算法算法 常用于工业生产的群控系统中，由一台计算机控制若常用于工业生产的群控系统中

38、，由一台计算机控制若干个相同的干个相同的(或类似的或类似的)对象，为每一个被控对象建立一个对象，为每一个被控对象建立一个实时任务，并将它们排成一个轮转队列。实时任务，并将它们排成一个轮转队列。 每次都选择队列第一个任务运行，该任务完成后，便每次都选择队列第一个任务运行，该任务完成后，便把它挂在轮转队列的末尾。与把它挂在轮转队列的末尾。与RRRR算法类似。算法类似。 这种调度算法可获得这种调度算法可获得数秒至数十秒数秒至数十秒的响应时间，可用的响应时间，可用于要求不太严格的实时控制系统中。于要求不太严格的实时控制系统中。 (a ) 非抢占式轮转调度当前进程实时进程实时进程请求调度实时进程抢占当前

39、进程并立即执行(d ) 立即抢占的优先权调度调度时间进程 1进程 2实时进程要求调度进程 n实时进程调度实时进程运行(b ) 非抢占式优先权调度当前进程实时进程实时进程请求调度当前进程运行完成调度时间当前进程实时进程请求调度时钟中断到来时调度时间(c ) 基于时钟中断抢占的优先权抢占调度调度时间实时进程进程进程1均代表当前正在执行的进程，其后为就绪队列。均代表当前正在执行的进程，其后为就绪队列。 2) 2) 非抢占式非抢占式优先调度优先调度算法算法如果在实时系统中存在着要求较为严格如果在实时系统中存在着要求较为严格(响应时间为响应时间为数百毫秒数百毫秒)的任务，则可采用非抢占式优先调度算法为这

40、的任务，则可采用非抢占式优先调度算法为这些任务赋予较高的优先级。些任务赋予较高的优先级。当这些实时任务到达时，把当这些实时任务到达时，把它们安排在就绪队列的队首它们安排在就绪队列的队首，等待当前任务自我终止或，等待当前任务自我终止或运行完成后才能被调度执行。这种调度算法有可能获得运行完成后才能被调度执行。这种调度算法有可能获得仅仅为数秒至数百毫秒为数秒至数百毫秒级的响应时间，因而可用于有一定级的响应时间，因而可用于有一定要求的实时控制系统中。要求的实时控制系统中。 (a) 非抢占式轮转调度当前进程实时进程实时进程请求调度实时进程抢占当前进程并立即执行(d) 立即抢占的优先权调度调度时间进程 1

41、进程 2实时进程要求调度进程 n实时进程调度实时进程运行(b) 非抢占式优先权调度当前进程实时进程实时进程请求调度当前进程运行完成调度时间当前进程实时进程请求调度时钟中断到来时调度时间(c) 基于时钟中断抢占的优先权抢占调度调度时间实时进程进程进程1进程进程2进程进程3.进程进程n实时进程实时进程实时进程实时进程要求调度要求调度进程进程1实时进程实时进程进程进程2.进程进程3进程进程n实时进程实时进程要求调度要求调度调度时间调度时间就绪队列就绪队列正在运行的进程正在运行的进程 2 2抢占式调度算法抢占式调度算法用于要求较严格的用于要求较严格的( (响应时间为数十毫秒以下响应时间为数十毫秒以下)

42、 )的实时的实时系统中。根据抢占发生时间不同可分以下两种调度算法。系统中。根据抢占发生时间不同可分以下两种调度算法。1) 1) 基于时钟中断的抢占式基于时钟中断的抢占式优先权优先权调度算法调度算法若实时任务优先级高于当前任务，并不立即抢占当前若实时任务优先级高于当前任务，并不立即抢占当前任务的处理机而是等到时钟中断到来时。这种调度算法能任务的处理机而是等到时钟中断到来时。这种调度算法能获得较好的响应效果。可用于大多数的实时系统中。获得较好的响应效果。可用于大多数的实时系统中。 (a) 非抢占式轮转调度当前进程实时进程实时进程请求调度实时进程抢占当前进程并立即执行(d ) 立即抢占的优先权调度调

43、度时间进程 1进程 2实时进程要求调度进程 n实时进程调度实时进程运行(b ) 非抢占式优先权调度当前进程实时进程实时进程请求调度 当前进程运行完成调度时间当前进程实时进程请求调度时钟中断到来时调度时间(c) 基于时钟中断抢占的优先权抢占调度调度时间实时进程 2) 2) 立即抢占的立即抢占的优先权优先权调度算法调度算法若实时任务优先级高于当前任务若实时任务优先级高于当前任务，只要当前任务未，只要当前任务未处于临界区，便立即剥夺当前任务的执行。这种算法能处于临界区，便立即剥夺当前任务的执行。这种算法能获得非常快的响应，可把调度延迟降低到几毫秒至获得非常快的响应，可把调度延迟降低到几毫秒至1001

44、00微秒，甚至更低。微秒，甚至更低。(a ) 非抢占式轮转调度当前进程实时进程实时进程请求调度实时进程抢占当前进程并立即执行(d ) 立即抢占的优先权调度调度时间进程 1进程 2实时进程要求调度进程 n实时进程调度实时进程运行(b ) 非抢占式优先权调度当前进程实时进程实时进程请求调度当前进程运行完成调度时间当前进程实时进程请求调度时钟中断到来时调度时间(c ) 基于时钟中断抢占的优先权抢占调度调度时间实时进程当前进程当前进程实时进程实时进程实时进程请求调度实时进程请求调度实时进程立即抢占当实时进程立即抢占当前进程并立即执行前进程并立即执行调度时间调度时间3.4.33.4.3最早截止时间优先最

45、早截止时间优先(EDF)(EDF)算法算法 截止截止时间愈早，其优先级愈高时间愈早，其优先级愈高。 在实时任务在实时任务就绪队列中各任务按截止时间的早晚排序就绪队列中各任务按截止时间的早晚排序；当然，截止时间最早的任务排在最前面。调度总是选择当然，截止时间最早的任务排在最前面。调度总是选择就绪队列中的第一个任务。就绪队列中的第一个任务。 既可用于抢占式调度，也可用于非抢占式调度。既可用于抢占式调度，也可用于非抢占式调度。 1 1. .EDFEDF用于用于非周期非周期实时任务实时任务非抢占式非抢占式调度方式调度方式例：四个非周期任务例：四个非周期任务1,2,3,41,2,3,4先后到达，开始截止

46、时间先后到达，开始截止时间排序为排序为1,3,4,21,3,4,2。则任务执行顺序如下：。则任务执行顺序如下： 1342开始截止时间任务执行任务到达12 341342t排序2.EDF2.EDF用于用于周期周期实时任务实时任务抢占抢占式调度方式式调度方式例例: :有两个周期性任务，任务有两个周期性任务，任务A的周期时间为的周期时间为20 ms，每个周期的处理时间为每个周期的处理时间为10 ms；任务；任务B的周期时间为的周期时间为50 ms，每个周期的处理时间为，每个周期的处理时间为25 ms。图中的第一行示出。图中的第一行示出了两个任务的到达时间、最后期限和执行时间图。其中了两个任务的到达时间

47、、最后期限和执行时间图。其中任务任务A的到达时间为的到达时间为0、20、40、；任务；任务A的最后期限的最后期限为为20、40、60、；任务；任务B的到达时间为的到达时间为0、50、100、；任务；任务B的最后期限为的最后期限为50、100、150、(注：注：单位皆为单位皆为ms)。 到达时间到达时间020406080050进程名进程名A1A2A3A4A5B1B2截止时间截止时间2040608010050100执行时间执行时间10101010102525若采用一般优先级调度算法：若采用一般优先级调度算法：A1 B1 A2B1A3 B2 A4B2A5B1A2A3B2A5A1B1B1 A2 B1

48、A3 B2 A4 B2 A5 B2A1A2B2A3A4A5B1最后期限B2最后期限A1最后期限A2最后期限A3最后期限A4最后期限A5最后期限到达时间、执行时间和最后期限A1固定优先级调度固定优先级调度A2 B1A3A4A5，B2A5，B2A4A1(错过)A2 B1 A3(错过)A1A2 B1(错过)A3A4A5，B201020304050 60708090100 时间t/ms使用完成最后期限最早和最后期限调度(A有较高优先级)(B有较高优先级)不能满足实时任务调度不能满足实时任务调度A1 B1A2B1A3 B2 A4B2A5B1A2A3B2A5A1B1B1A2B1A3 B2 A4B2A5 B

49、2A1A2B2A3A4A5B1最后期限B2最后期限A1最后期限A2最后期限A3最后期限A4最后期限A5最后期限到达时间、执行时间和最后期限A1固定优先级调度固定优先级调度A2B1A3A4A5，B2A5，B2A4A1(错过)A2B1A3(错过)A1A2B1(错过)A3A4A5，B201020304050 60708090100 时间 t/ms使用完成最后期限最早和最后期限调度(A有较高优先级)(B有较高优先级)采用采用EDFEDF算法：算法：可以满足实时可以满足实时任务调度任务调度A1 B1 A2 B1 A3B2A4B2A5B1A2A3B2A5A1B1B1 A2 B1 A3 B2 A4 B2 A

50、5B2A1A2B2A3A4A5B1最后期限B2最后期限A1最后期限A2最后期限A3最后期限A4最后期限A5最后期限到达时间、执行时间和最后期限A1固定优先级调度固定优先级调度A2 B1 A3A4A5，B2A5，B2A4A1(错过)A2 B1 A3(错过)A1A2 B1(错过)A3A4A5，B2010 20 30 40 50 60 70 80 90 100时间t/ms使用完成最后期限最早和最后期限调度(A有较高优先级)(B有较高优先级)0-10 A110-20 B120-30 A230-40 B140-45 B145-55 A355-60 B260-70 A470-80 B280-90 B290

51、-100 A53.4.43.4.4最低最低松弛度优先松弛度优先(LLF)(LLF)算法算法 原理：根据任务紧急原理：根据任务紧急(或松弛或松弛)的程度，来确定任务的的程度，来确定任务的优先级。越紧急优先级愈高。优先级。越紧急优先级愈高。 例如，任务例如，任务A A在在200 ms时必须完成，本身所需运行时时必须完成，本身所需运行时间为间为100 ms，则该任务的紧急程度，则该任务的紧急程度(松弛程度松弛程度)为为100 ms。任务任务B B在在400 ms时必须完成，本身需运行时必须完成，本身需运行 150 ms，则其，则其松弛程度为松弛程度为 250 ms。 算法实现算法实现: :实时任务的

52、就绪队列按松弛度排序，松实时任务的就绪队列按松弛度排序，松弛度最小的队首，调度程序总是选择队首任务执行。弛度最小的队首，调度程序总是选择队首任务执行。 松弛度松弛度= =完成截止时间完成截止时间- -仍需运行时间仍需运行时间- -当前时间当前时间 例：周期性实时任务例：周期性实时任务A,B如下表如下表到达时间到达时间020406080050进程名进程名A1A2A3A4A5B1B2截止时间截止时间2040608010050100执行时间执行时间10101010102525A1A2A3A4A5A6A7A820406080100120140160B1B2B3t0t1A1(10)10203040506

53、080t0t10B1(20)t2t370A2(10)A3(10)A4(10)t4t5t6t7t8B1(5)B2(15)B2(10)3.4.5 优先级倒置优先级倒置1.优先级倒置的形成优先级倒置的形成 优先级倒置：优先级高的进程被优先级低的进程延迟优先级倒置：优先级高的进程被优先级低的进程延迟或阻塞。或阻塞。 形成：大多因资源的访问形成：大多因资源的访问2.解决方法解决方法 1)进入临界区后处理机不予许被抢占进入临界区后处理机不予许被抢占 2)动态优先级继承：发生倒置时，让低优先级的进程继动态优先级继承：发生倒置时，让低优先级的进程继承高优先级进程的优先级承高优先级进程的优先级3.5 死锁概述死

54、锁概述3.5.1 资源问题资源问题可剥夺性资源可剥夺性资源:获得的资源可以被其获得的资源可以被其他进程或系统剥夺。例他进程或系统剥夺。例 如，如，CPU、主存。主存。不可剥夺性资源：分配给进程后，不可剥夺性资源：分配给进程后，不能强行收回，只能在进程用完后不能强行收回，只能在进程用完后自行释放，如磁带机、打印机等。自行释放，如磁带机、打印机等。 资资源源按是否能被抢占按是否能被抢占按是否可以重按是否可以重复使用复使用临时性资源临时性资源/消耗性资源消耗性资源:由一个由一个进程产生，被另一进程使用一短暂进程产生，被另一进程使用一短暂时间后便无用的资源。时间后便无用的资源。永久性资源：资源属于可重

55、复使用，永久性资源：资源属于可重复使用， 如打印机。如打印机。3.5.2 计算机系统中的死锁计算机系统中的死锁 1. 1.竞争竞争资源资源。 当系统中供多个进程共享的资源数目不足以满足诸当系统中供多个进程共享的资源数目不足以满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁进程的需要时，会引起诸进程对资源的竞争而产生死锁。 1)竞争竞争不可抢占性资源引起死锁不可抢占性资源引起死锁 例如例如，系统中只有一台打印机，系统中只有一台打印机R1和一台磁带机和一台磁带机R2，可供，可供进程进程P1和和P2共享。两个进程都在等待对方释放出自己所需的共享。两个进程都在等待对方释放出自己所需的资源。但它们

56、又都因不能继续获得自己所需的资源而不能继资源。但它们又都因不能继续获得自己所需的资源而不能继续推进，从而也不能释放出自己已占有的资源，以致进入死续推进，从而也不能释放出自己已占有的资源，以致进入死锁状态。锁状态。R1R2P1P2 P1已占用打印机已占用打印机R1，P2已占用了磁带机已占用了磁带机R2。P2继续要求打印机继续要求打印机R1，P2将阻塞；将阻塞；P1要求磁带要求磁带机机R2，P1也阻塞。于是，也阻塞。于是，在在P1与与P2之间便形成了之间便形成了僵局，即闭合环路。僵局，即闭合环路。打印机打印机磁带机磁带机2)竞争可消耗资源引起死锁竞争可消耗资源引起死锁如如图图所所示，示，S S1

57、1、S S2 2和和S S3 3是临时性资源。是临时性资源。P P1 1产生消息产生消息S S1 1，要求接收消息，要求接收消息S S3 3；P P2 2产生消息产生消息S S2 2，要接收消息，要接收消息S S1 1； P P3 3产生消息产生消息S S3 3，要求接收消息，要求接收消息S S2 2；若按下述的运行顺序：若按下述的运行顺序：P1P1： Request(S3)Request(S3)； Release(S1)Release(S1)； P2P2： Request(S1)Request(S1)； Release(S2)Release(S2)； P3P3： Request(S2)Req

58、uest(S2)； Release(S3)Release(S3)； 则发生死锁。则发生死锁。 S2P1S3P3S1P22进程推进顺序不当引起死锁进程推进顺序不当引起死锁由于由于进程在运行中具有异步性特征，因此进程在运行中具有异步性特征，因此P1和和P2两两个进程按多种顺序向前推进。个进程按多种顺序向前推进。 1) 进程推进顺序合法进程推进顺序合法P1： Request(R1)； Request(R2)； Releast(R1)； Release(R2)；P2： Request(R2)； Request(R1)； Release(R2)； Release(R1)；顺序顺序1：顺序顺序2：P2：

59、Request(R2)； Request(R1)； Release(R2)； Release(R1)； P1： Request(R1)； Request(R2)； Releast(R1)； Release(R2)；顺序顺序3：P1： Request(R1)； Request(R2)； P2： Request(R2)； P1： Releast(R1)； Release(R2)；P2： Request(R1)； Release(R2)； Release(R1)；图图3-15进程推进顺序对死锁的影响进程推进顺序对死锁的影响 P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1

60、Req(R1)P1Req(R2) P1Rel(R1) P1Rel(R2)DP1Req (R1)P1Req (R2)P1Rel (R1)P1Rel (R2)P2Rel (R1)P2Rel (R2)P2Req (R1)P2Req (R2)死锁点死锁点2) 进程推进顺序非法进程推进顺序非法 若并发进程若并发进程P1和和P2按曲线所示的顺序推进，它们按曲线所示的顺序推进，它们将进入不安全区将进入不安全区D内。此时内。此时P1保持了资源保持了资源R1，P2保持保持了资源了资源R2，系统处于不安全状态。，系统处于不安全状态。 此时两进程再向前推进，便可能发生死锁。此时两进程再向前推进，便可能发生死锁。 在