操作系统第三章1

1、Operating SystemOperating SystemPage 12022-4-23Operating SystemOperating SystemPage 22022-4-23q知识点知识点v处理机调度及调度算法处理机调度及调度算法v实时系统的进程（线程）调度算法实时系统的进程（线程）调度算法v产生死锁的原因和必要条件产生死锁的原因和必要条件v预防死锁的方法，死锁的检测与解除预防死锁的方法，死锁的检测与解除 v银行家算法银行家算法Operating SystemOperating SystemPage 32022-4-23q重点重点v掌握掌握进程调度进程调度算法，各适用于何种情况算

2、法，各适用于何种情况 v理解产生理解产生死锁死锁的原因的原因 v掌握掌握银行家算法银行家算法避免避免死锁死锁Operating SystemOperating SystemPage 42022-4-23q处理机是计算机系统中的处理机是计算机系统中的重要资源重要资源q在多道程序环境下，进程数目通常在多道程序环境下，进程数目通常多于处理机的多于处理机的数目数目q系统必须按一定方法系统必须按一定方法动态地动态地把处理机把处理机分配给分配给就绪就绪队列中的一个进程队列中的一个进程q处理机处理机利用率和系统性能利用率和系统性能（吞吐量、响应时间）（吞吐量、响应时间）在很大程度上在很大程度上取决于取决于处

3、理机处理机调度调度分配处理机的任务是由进程调度程序完成分配处理机的任务是由进程调度程序完成的。它是操作系统设计的中心问题之一。的。它是操作系统设计的中心问题之一。WHAT：什么是处理机调度，按什么原则分配：什么是处理机调度，按什么原则分配CPU进进程调度算法程调度算法WHEN：何时分配：何时分配CPU 进程调度的时机进程调度的时机 HOW：如何分配：如何分配CPU CPU调度过程（进程的上下调度过程（进程的上下文切换）文切换）Operating SystemOperating SystemPage 52022-4-23q 处理机调度的基本概念处理机调度的基本概念 q作业调度作业调度q进程调度进

4、程调度q 实时调度实时调度 q 多处理机系统中的调度多处理机系统中的调度q 产生死锁的原因和必要条件产生死锁的原因和必要条件 q 预防死锁的方法预防死锁的方法 q 死锁的检测与解除死锁的检测与解除Operating SystemOperating SystemPage 62022-4-23q高级、中级和低级调度高级、中级和低级调度q处理机调度算法的目标处理机调度算法的目标Operating SystemOperating SystemPage 72022-4-23q作业的概念作业的概念-批处理系统中使用批处理系统中使用v作业作业包括用户程序、所需的数据及作业说明书包括用户程序、所需的数据及作业

5、说明书v作业的状态：作业的状态：一个作业进入系统到运行结束，一个作业进入系统到运行结束，一般需要经历一般需要经历收容、运行、完成收容、运行、完成三个阶段，与三个阶段，与之相对应的是作业的三种状态之相对应的是作业的三种状态后备后备状态状态运行运行状态状态完成完成状态状态Operating SystemOperating SystemPage 82022-4-23运行状态运行状态后备状态后备状态完成状态完成状态就绪就绪阻塞阻塞执行执行I/O完成完成I/O请求请求时间片完时间片完作业作业注册注册作业作业调度调度进程进程调度调度终止终止作业作业q作业作业状态间转换状态间转换内存内存外存外存高级高级调度

6、调度低级低级调度调度交换区中级中级调度调度Operating SystemOperating SystemPage 92022-4-233.1 处理机调度的基本概念处理机调度的基本概念 3.1.1 调度调度 的层次的层次1. 高级调度高级调度(High Scheduling)：作业调度：作业调度 2. 低级调度低级调度(Low Level Scheduling) ：进程调度：进程调度3. 中级调度中级调度(Intermediate-Level Scheduling) 批处理系统中有高级调度和低级调度批处理系统中有高级调度和低级调度分时系统用户命令直接进入内存，只有低级调度分时系统用户命令直接进

7、入内存，只有低级调度Operating SystemOperating SystemPage 102022-4-23q高级调度高级调度(High Scheduling)(High Scheduling)v主要任务是按一定的原则对外存上处于后备状主要任务是按一定的原则对外存上处于后备状态的作业进行选择，给选中的作业态的作业进行选择，给选中的作业分配分配内存、内存、输入输入/ /输出设备等输出设备等必要的资源必要的资源，并，并建立建立相应的相应的进程进程，放入放入就绪就绪队列队列，以使该作业的进程获得，以使该作业的进程获得竞争处理机的权利竞争处理机的权利v也称为也称为接纳调度（接纳调度（Admis

8、sion SchedulingAdmission Scheduling）v高级调度的时间尺度通常是分钟、小时或天高级调度的时间尺度通常是分钟、小时或天Operating SystemOperating SystemPage 112022-4-23在每次作业调度时，须决定：在每次作业调度时，须决定：v接纳多少个作业接纳多少个作业 即允许多少个作业同时在内存中运行，取决于即允许多少个作业同时在内存中运行，取决于多多 道程序度道程序度（Degree of Multiprogramming）作业太多作业太多 服务质量下降服务质量下降作业太少作业太少 资源利用率低资源利用率低v接纳哪些作业接纳哪些作业

9、取决于作业调度算法取决于作业调度算法先来先服务先来先服务短作业优先短作业优先作业优先权调度作业优先权调度响应比调度响应比调度周转时间太长系统吞吐量太低 适当的折衷：即允许多少个作业同时在内存中运行。：即允许多少个作业同时在内存中运行。：从作业被提交给系统开始，到作业完成为：从作业被提交给系统开始，到作业完成为止的这段时间间隔。止的这段时间间隔。：是指在单位时间内系统所完成的作业数。：是指在单位时间内系统所完成的作业数。Operating SystemOperating SystemPage 122022-4-23q 低级调度低级调度v主要任务是按照某种主要任务是按照某种策略和方法策略和方法选取

10、选取一个处一个处于于就绪就绪状态的进程，将处理机状态的进程，将处理机分配分配给它给它v低级调度的时间尺度通常是低级调度的时间尺度通常是毫秒级毫秒级的。由于的。由于低级调度算法的低级调度算法的频繁使用频繁使用，要求在实现时做，要求在实现时做到到高效高效Operating SystemOperating SystemPage 132022-4-23q 中级调度中级调度(Intermediate-Level (Intermediate-Level Scheduling)Scheduling)v引入目的引入目的是为了提高是为了提高内存利用率内存利用率和和系统吞吐系统吞吐量。量。v主要任务主要任务是按照

11、给定的是按照给定的原则和策略原则和策略，将那些，将那些暂时不能运行的进程调至外存，将处于外存暂时不能运行的进程调至外存，将处于外存对换区对换区中的重又具备运行条件的就绪进程中的重又具备运行条件的就绪进程调调入内存入内存 Operating SystemOperating SystemPage 142022-4-23q 高级、中级和低级调度高级、中级和低级调度q 处理机调度算法的目标处理机调度算法的目标Operating SystemOperating System1.共同目标共同目标Page 152022-4-23q 具有具有公平性公平性q 资源资源利用率高利用率高（特别是（特别是CPUCPU

12、利用率），利用率），尽可能保持忙的状态尽可能保持忙的状态q 系统资源使用的平衡性系统资源使用的平衡性Operating SystemOperating SystemPage 162022-4-232. 批处理系统的目标v周转时间短（周转时间短（P90P90）平均周转时间平均周转时间niiTnT11niSiiTTnW11带权周转时间：带权周转时间：进程（或作业）的进程（或作业）的周转时周转时间间T T与运行时间与运行时间T TS S之比，即之比，即W=T/TW=T/TS S 。而。而平均平均带权周转时间带权周转时间则可表示为则可表示为: : Operating SystemOperating S

13、ystemv系统吞吐量高系统吞吐量高吞吐量吞吐量指单位时间内系统所完成的作业数指单位时间内系统所完成的作业数作业调度的方式和算法对吞吐量的大小有较作业调度的方式和算法对吞吐量的大小有较大影响大影响v处理机利用率高处理机利用率高v各类资源的平衡利用各类资源的平衡利用使内存、外存和使内存、外存和I/OI/O设备的利用率高设备的利用率高Page 172022-4-23Operating SystemOperating SystemPage 182022-4-233. 分时系统的目标分时系统的目标v响应时间快响应时间快响应时间响应时间是指从用户通过键盘提交一个请求是指从用户通过键盘提交一个请求开始，直

14、至系统中开始，直至系统中首次首次产生产生响应响应为止的时间为止的时间响应时间与服务的复杂性适应即可响应时间与服务的复杂性适应即可Operating SystemOperating System4.实时系统的目标实时系统的目标v截止时间保证截止时间保证截止时间截止时间是指某任务必须开始执行的最迟时是指某任务必须开始执行的最迟时间或必须完成的最迟时间间或必须完成的最迟时间截止时间是截止时间是实时系统实时系统中的重要指标中的重要指标v可预测可预测提前预测做出准备处理提前预测做出准备处理Page 192022-4-23Operating SystemOperating SystemPage 20202

15、2-4-23q 调度算法调度算法v 周转时间短周转时间短v 响应时间快响应时间快v 截止时间保证截止时间保证批处理系统批处理系统分时系统分时系统实时系统实时系统Operating SystemOperating SystemPage 212022-4-23q 处理机调度的基本概念处理机调度的基本概念 q作业调度作业调度q进程调度进程调度q 实时调度实时调度 q 多处理机系统中的调度多处理机系统中的调度q 产生死锁的原因和必要条件产生死锁的原因和必要条件 q 预防死锁的方法预防死锁的方法 q 死锁的检测与解除死锁的检测与解除Operating SystemOperating SystemPage

16、 222022-4-23q 先来先服务先来先服务q 短作业优先算法短作业优先算法q 高优先权优先调度算法高优先权优先调度算法Operating SystemOperating SystemPage 232022-4-23q 先来先服务先来先服务(FCFS)调度算法调度算法v按照作业按照作业/进程进入系统进程进入系统/就绪队列的就绪队列的先后次序先后次序进行调度，先进入系统者先调度；即启动等进行调度，先进入系统者先调度；即启动等待时间最长的作业待时间最长的作业/进程进程v是一种最简单的调度算法，即可用于是一种最简单的调度算法，即可用于作业调作业调度度，也可用于，也可用于进程调度进程调度q 几个术

17、语几个术语v到达时间、开始时间到达时间、开始时间v完成时间、等待时间完成时间、等待时间v周转时间：完成时间周转时间：完成时间-到达时间到达时间v带权周转时间：周转时间带权周转时间：周转时间/服务时间服务时间Operating SystemOperating SystemPage 242022-4-23作业名作业名到达时间到达时间 服务时间服务时间 开始时间开始时间 完成时间完成时间 周转时间周转时间带权周带权周转时间转时间平均平均04A13B25C32D44E044476先来先服务（先进先出）：先来先服务（先进先出）：712101214111418141225.53.592.8A A A A

18、B B B C C C C C D D E E E E05101518tOperating SystemOperating SystemPage 252022-4-23q 先来先服务先来先服务（先进先出）（先进先出）优缺点优缺点v 比较有利于比较有利于长作业长作业 ，而不利于，而不利于短作业短作业 v 有利于有利于CPU繁忙型作业（进程）繁忙型作业（进程） ，而不利于，而不利于I/O繁忙型作业（进程）繁忙型作业（进程）Operating SystemOperating SystemPage 262022-4-23q短作业优先调度算法短作业优先调度算法SJFSJFv短作业短作业 优先调度算法优先

19、调度算法SJ FSJ F，以要求，以要求运行时间运行时间长短长短进行调度，即启动估计运行时间最短的作进行调度，即启动估计运行时间最短的作业业v可以分别用于可以分别用于作业调度作业调度和和进程调度进程调度Operating SystemOperating SystemPage 272022-4-23作业名作业名到达时间到达时间 服务时间服务时间 开始时间开始时间 完成时间完成时间 周转时间周转时间带权周带权周转时间转时间平均平均04A13B25C32D44E0441短作业优先（短作业优先（SJF）：）：4633/26988/391399/413181616/582.1A A A AB B BC

20、C C C CD DE E E E05101518tOperating SystemOperating SystemPage 282022-4-23qFCFS/SJF调度算法的性能调度算法的性能SJFSJF能有效地降低作业的平均等待时间，提高系统吞吐量能有效地降低作业的平均等待时间，提高系统吞吐量 作业作业调度调度 情况情况 算法算法进程名进程名ABCDE平均平均到达时间到达时间01234服务时间服务时间43524FCFS完成时间完成时间47121418周转时间周转时间461011149带权周转时间带权周转时间1225.53.52.8SJF完成时间完成时间4918613周转时间周转时间4816

21、398带权周转时间带权周转时间12.673.11.52.252.1SJFSJF平均周转平均周转时间和平均带时间和平均带权周转时间明权周转时间明显改善显改善Operating SystemOperating SystemPage 292022-4-23qSJ F调度算法也存在不容忽视的缺点调度算法也存在不容忽视的缺点v对对长作业不利长作业不利。 由于调度程序总是优先调度那由于调度程序总是优先调度那些些( (即使是后进来的即使是后进来的) )短作业短作业 ，将导致长作业，将导致长作业 长长期不被调度期不被调度饥饿饥饿v完全未考虑作业完全未考虑作业 的的紧迫程度紧迫程度，因而不能保证，因而不能保证紧

22、紧迫性迫性作业作业 会被会被及时处理及时处理v由于作业由于作业 的长短只是根据的长短只是根据用户用户所提供的所提供的估计执估计执行时间行时间而定的，而用户又可能会而定的，而用户又可能会有意或无意有意或无意地地缩缩短短其作业的估计其作业的估计运行时间运行时间，致使该算法不一定能，致使该算法不一定能真正做到短作业优先调度。真正做到短作业优先调度。Operating SystemOperating SystemPage 302022-4-23q先来先服务先来先服务q短作业优先算法短作业优先算法q优先权优先调度算法优先权优先调度算法Operating SystemOperating SystemPag

23、e 312022-4-23q根据作业的紧迫程度赋予作业相应的优先级，优根据作业的紧迫程度赋予作业相应的优先级，优先级高的优先运行先级高的优先运行q优先权的类型优先权的类型v静态优先权：优先级不变静态优先权：优先级不变v动态优先权动态优先权Operating SystemOperating SystemPage 322022-4-23进程进程名名到达到达时间时间服务服务时间时间静态优静态优先权先权开始开始时间时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间平均平均静态优先权（静态优先权（1为高优先权）为高优先权）04A413B225C332D544E1044148418111010/

24、311161414/516181515/29.42.93Operating SystemOperating SystemPage 332022-4-23q高响应比优先调度算法（高响应比优先调度算法（HRF）v是是FCFS和和SJF的结合，既考虑运行时间又的结合，既考虑运行时间又考虑到达时间，克服了两种算法的缺点考虑到达时间，克服了两种算法的缺点v调度策略调度策略：响应比：响应比最高的作业优先启动最高的作业优先启动v因因等待时间等待时间+服务时间服务时间=该作业的该作业的响应时间响应时间，故该优先权又相当于故该优先权又相当于响应比响应比RP。据此，又。据此，又可表示为可表示为时时间间务务时时间间

25、权权务务时时间间等等待待+ + 要要求求服服优优先先= =要要求求服服时间务时间响应时间权务时间务时间等等待待+ + 要要求求服服优优先先= = =要要求求服服要要求求服服Operating SystemOperating SystemPage 342022-4-23q 对对HRF的小结的小结v等待时间相同等待时间相同的作业，则的作业，则要求服务的时间愈要求服务的时间愈短短，其，其优先权愈高优先权愈高，v要求服务的时间相同要求服务的时间相同的作业，则的作业，则等待时间愈等待时间愈长长，其，其优先权愈高优先权愈高，v长作业，优先权长作业，优先权随等待时间的增加随等待时间的增加而提高，而提高，其等

26、待时间足够长时，其优先权便可升到很其等待时间足够长时，其优先权便可升到很高，高， 从而也可获得处理机从而也可获得处理机v这种算法是一种折衷，既照顾了短作业，又这种算法是一种折衷，既照顾了短作业，又考虑了作业到达的先后次序，又不会使长作考虑了作业到达的先后次序，又不会使长作业长期得不到服务。业长期得不到服务。缺点：要进行响应比计算，增加了系统开销缺点：要进行响应比计算，增加了系统开销时间务时间响应时间权务时间务时间等等待待+ + 要要求求服服优优先先= = =要要求求服服要要求求服服对短作业有利对短作业有利是先来先服务是先来先服务对长作业有利对长作业有利Operating SystemOpera

27、ting Systemq例：单道程序系统中，下列作业若采用响应比高者优先的算法调度，请列出各个作业的运行次序。作业名作业名提交时间提交时间计算时间计算时间A8:5090分钟B9:0024分钟C9:3060分钟Page 352022-4-23Operating SystemOperating SystemPage 362022-4-23q处理机调度的基本概念处理机调度的基本概念 q作业调度作业调度q进程调度进程调度q实时调度实时调度 q多处理机系统中的调度多处理机系统中的调度q产生死锁的原因和必要条件产生死锁的原因和必要条件 q预防死锁的方法预防死锁的方法 q死锁的检测与解除死锁的检测与解除Op

28、erating SystemOperating SystemPage 372022-4-23q 进程调度的任务进程调度的任务 保存保存当前进程的处理机信息，按一定当前进程的处理机信息，按一定的调度算法从就绪队列中的调度算法从就绪队列中选中选中一个进程，一个进程，将其状态改为运行状态，将选中进行的处将其状态改为运行状态，将选中进行的处理机信息理机信息恢复恢复到处理机中，把到处理机中，把CPUCPU的使用权的使用权交给被选中的进程。交给被选中的进程。Operating SystemOperating SystemPage 382022-4-23q 非抢占方式非抢占方式(Non-preemptive

29、 Mode)(Non-preemptive Mode)q 抢占方式抢占方式(Preemptive Mode)(Preemptive Mode)Operating SystemOperating SystemPage 392022-4-23q 非抢占方式非抢占方式(Non-preemptive Mode)(Non-preemptive Mode) 不能暂停在不能暂停在CPUCPU上执行的进程，上执行的进程，需要等到其完成需要等到其完成或发生某种事件而进入阻塞状态时，才把处理机或发生某种事件而进入阻塞状态时，才把处理机分配给其他进程分配给其他进程v引起进程调度的因素引起进程调度的因素- -进程主动

30、让出进程主动让出cpucpu正在执行的进程执行完毕，正在执行的进程执行完毕， 或因发生某事或因发生某事件而不能再继续执行件而不能再继续执行执行中的进程因提出执行中的进程因提出I/OI/O请求而暂停执行；请求而暂停执行；在进程通信或同步过程中执行了某种原语在进程通信或同步过程中执行了某种原语操作，如操作，如waitwait、BlockBlock、WakeupWakeup原语原语优点优点：算法简单，：算法简单，系统开销小系统开销小缺点缺点：紧急任务不：紧急任务不能及时响应；短进能及时响应；短进程到达要等待长进程到达要等待长进程运行结束程运行结束Operating SystemOperating S

31、ystemPage 402022-4-23q 抢占方式抢占方式(Preemptive Mode)(Preemptive Mode) 可以立即暂停正在执行的进程可以立即暂停正在执行的进程，将处理机分，将处理机分配给这个更为重要或紧迫的进程。配给这个更为重要或紧迫的进程。抢占式调度主要有以下原则抢占式调度主要有以下原则优先权原则优先权原则 允许高优先权的新到进程抢允许高优先权的新到进程抢占当前进程的处理机占当前进程的处理机短作业短作业( (进程进程) )优先原则优先原则允许执行时间短允许执行时间短的新到进程抢占当前进程的处理机的新到进程抢占当前进程的处理机 时间片原则时间片原则 时间片用完后停止执

32、行，时间片用完后停止执行，重新进行调度，适用于分时系统重新进行调度，适用于分时系统 优点优点：适于时间要：适于时间要求严格的实时系统求严格的实时系统缺点缺点：调度算法复：调度算法复杂，系统开销大杂，系统开销大Operating SystemOperating Systemq时间片轮转算法时间片轮转算法q优先级调度算法优先级调度算法q多级反馈队列调度算法多级反馈队列调度算法Page 412022-4-23Operating SystemOperating SystemPage 422022-4-23q 简单的时间片轮转法简单的时间片轮转法(RRRound Robin)v系统将所有的就绪进程按先来

33、先服务的原则排系统将所有的就绪进程按先来先服务的原则排成一个队列，每个进程依次执行一个时间片成一个队列，每个进程依次执行一个时间片v时间片的大小从几时间片的大小从几ms到几百到几百ms优点：公平。保证就绪队列中所有进程在一给定的优点：公平。保证就绪队列中所有进程在一给定的时间内，均能获得一时间片的处理机执行时间时间内，均能获得一时间片的处理机执行时间缺点：紧迫任务响应慢。缺点：紧迫任务响应慢。UNIX中采用：时间片中采用：时间片+优先权优先权Operating SystemOperating SystemPage 432022-4-23v分时系统中常用时间片轮转法分时系统中常用时间片轮转法时间

34、片选择时间片选择问题问题固定时间片固定时间片可变时间片可变时间片时间片大小：太小频繁切换，太大变为先来先时间片大小：太小频繁切换，太大变为先来先服务服务与与时间片大小时间片大小有关的因素有关的因素系统响应时间系统响应时间就绪进程个数就绪进程个数CPUCPU能力能力 Operating SystemOperating SystemPage 442022-4-23基于时间片的轮转调度算法基于时间片的轮转调度算法 （1）系统对响应时间的要求）系统对响应时间的要求 数目N和时间片q成反比，即T=Nq，因此在进程数一定时，作为分时系统首先就是必须满足系统对响应时间的要求。时间片的长短将正比于系统所要求的

35、响应时间。（2）就绪队列中进程的数目）就绪队列中进程的数目 在分时系统中，就绪队列上所有的进程数，是随着在终端上机的用户数目而改变的，但系统应保证，当所有终端用户上机时，获得较好的响应时间。（3）系统的处理能力）系统的处理能力 系统的处理能力是必须保证用户键入的常用命令能在一个时间片内处理完毕，否则将无法保证得到满意的响应时间，而且会使平均周转时间及带权周转时间都很长。 Operating SystemOperating SystemPage 452022-4-23进程名进程名到达时间到达时间 服务时间服务时间 开始时间开始时间 完成时间完成时间 周转时间周转时间带权周带权周转时间转时间平均平

36、均A B C D E A B C D E A B C E A C E C05101518t04A03B05C02D04E012349121517181515/41212/31818/599/21717/414.24.02若到达时间若到达时间为为0 0、1 1、2 2、3 3、4 4，又如，又如何？何？Operating SystemOperating SystemPage 462022-4-23q优先权的类型优先权的类型v静态优先权静态优先权v动态优先权动态优先权Operating SystemOperating SystemPage 472022-4-23q优先权的类型优先权的类型v静态优先

37、权静态优先权创建进程时确定，且在进程的整个运行期间创建进程时确定，且在进程的整个运行期间保持保持不变不变。 v确定进程静态优先权的依据确定进程静态优先权的依据进程类型进程类型: :系统进程的优先权高于一般用户进程进程对资源的需求：进程对资源的需求：如进程的估计执行时间及内存需要量少的进程，应赋予较高的优先权。 用户要求：用户要求：由用户进程的紧迫程度和用户所付费用的多少来确定优先权。 Operating SystemOperating SystemPage 482022-4-23v动态优先权动态优先权随随进程的推进进程的推进或随其或随其等待时间等待时间的增加而改变，以的增加而改变，以获得更好的

38、调度性能获得更好的调度性能可规定，在可规定，在就绪队列中的进程就绪队列中的进程，随其，随其等待时间的等待时间的增长增长，其优先权，其优先权以速率以速率a提高提高当采用抢占式优先权调度算法时，如果再当采用抢占式优先权调度算法时，如果再规定当规定当前进程前进程的优先权的优先权以速率以速率b下降下降，则可防止一个长，则可防止一个长作业长期地作业长期地垄断垄断处理机处理机Operating SystemOperating SystemPage 492022-4-23q优先权调度算法的类型优先权调度算法的类型v非抢占式非抢占式优先权调度算法优先权调度算法v抢占式抢占式优先权调度算法优先权调度算法Oper

39、ating SystemOperating SystemPage 502022-4-23q优先权调度算法的类型优先权调度算法的类型v非抢占式非抢占式优先权调度算法优先权调度算法特点：系统一旦把处理机分配给就绪队特点：系统一旦把处理机分配给就绪队列中列中优先权最高优先权最高的进程后，该进程便的进程后，该进程便一一直执行直执行下去，直至完成，或因发生某事下去，直至完成，或因发生某事件使该进程放弃处理机时，系统才将处件使该进程放弃处理机时，系统才将处理机重新分配给另一优先权最高的进程理机重新分配给另一优先权最高的进程主要主要用于批处理系统用于批处理系统中，也可用于某些中，也可用于某些对实时性对实时性

40、要求不严的实时系统要求不严的实时系统中中Operating SystemOperating SystemPage 512022-4-23q优先权调度算法的类型优先权调度算法的类型v抢占式抢占式优先权调度算法优先权调度算法把处理机分配给优先权最高的进程，但在执行把处理机分配给优先权最高的进程，但在执行期间，只要出现另一个优先权更高的进程，则期间，只要出现另一个优先权更高的进程，则进程调度程序就进程调度程序就立即停止立即停止当前进程的执行，并当前进程的执行，并将处理机分配给新到的优先权最高的进程将处理机分配给新到的优先权最高的进程注意注意：只要只要系统中系统中出现出现一个新的就绪进程，一个新的就绪

41、进程，就就进行进行优先权优先权比较比较该调度算法，能更好地该调度算法，能更好地满足紧迫作业满足紧迫作业的要求，的要求，故而常用于要求比较严格的实时系统中故而常用于要求比较严格的实时系统中 Operating SystemOperating SystemPage 522022-4-23q其中，其中，RQRQ为就绪队列指针，为就绪队列指针，EPEP为运行队列指针。为运行队列指针。Operating SystemOperating SystemPage 532022-4-23q 仅有进程调度的调度队列模型仅有进程调度的调度队列模型q 具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型q

42、 同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型Operating SystemOperating SystemPage 542022-4-23q 仅有进程调度的调度队列模型仅有进程调度的调度队列模型v在分时系统中，通常仅设有进程调度在分时系统中，通常仅设有进程调度v系统把这些进程组织成一个系统把这些进程组织成一个就绪队列就绪队列v每个进程在执行时，可能有以下几种情况每个进程在执行时，可能有以下几种情况进程获得进程获得CPUCPU正在执行正在执行任务在给定时间片内任务在给定时间片内已完成已完成，释放处理机，释放处理机后为完成状态后为完成状态任务在时间片内任务在时间片内未完成未完成

43、，进入就绪队列末，进入就绪队列末尾尾在执行期间因某事件而阻塞进入阻塞队列在执行期间因某事件而阻塞进入阻塞队列Operating SystemOperating SystemPage 552022-4-23q仅有进程调度的调度队列模型仅有进程调度的调度队列模型就就 绪绪队队 列列阻阻 塞塞队队列列进程调度进程调度CPU进程完成进程完成等待事件等待事件交互用户交互用户事事件件出出现现时间片完时间片完Operating SystemOperating SystemPage 562022-4-23q 具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型v在批处理系统中，不仅需要在批处理系统

44、中，不仅需要进程调度进程调度，而，而且还要有且还要有作业调度作业调度v就绪队列的形式就绪队列的形式进程进入就绪队列时，按优先权高低插进程进入就绪队列时，按优先权高低插入相应位置，调度程序总是把处理机分入相应位置，调度程序总是把处理机分配给就绪队首进程配给就绪队首进程v根据事件的不同设置多个阻塞队列根据事件的不同设置多个阻塞队列Operating SystemOperating SystemPage 572022-4-23进程调度进程调度CPU进程完成进程完成时间片完时间片完就就 绪绪队队列列12等待事件等待事件等待事件等待事件等待事件等待事件n12n事件事件 出现出现事件事件 出现出现事件事件

45、 出现出现后后备备 队队列列作业作业调度调度与上一模型的主要区别：就绪队列的形式；与上一模型的主要区别：就绪队列的形式； 设置多个阻塞队列设置多个阻塞队列阻阻队队列列塞塞2 2阻阻队队列列塞塞n n阻阻队队列列塞塞1 1Operating SystemOperating SystemPage 582022-4-23q同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型就绪队列就绪队列进程调度进程调度就绪，挂起队列就绪，挂起队列中级调度中级调度阻塞，挂起队列阻塞，挂起队列阻塞队列阻塞队列等待事件等待事件进程完成进程完成时间片完时间片完作业调度作业调度交互型作业交互型作业后备队列后备队列批

46、量作业批量作业挂起挂起挂起挂起事事件件出出现现事件出现事件出现CPUOperating SystemOperating SystemPage 592022-4-23 多级队列调度多级队列调度前台前台的就绪队列是交互性作业的进程，采用时间片轮转。后台后台的就绪队列是批处理作业的进程，采用优先权或短作业优先算法。调度方式有两种：(1) 优先调度前台，若前台无可运行进程，才调度后台。(2) 分配占用CPU的时间比例，如：前台80%，后台20%。Operating SystemOperating SystemPage 602022-4-23q多级反馈队列调度算法多级反馈队列调度算法 v设置设置多个就绪

47、队列多个就绪队列，并为各个队列赋予，并为各个队列赋予不同不同的优先级的优先级第一个队列的优先级最高，第二个队列次之，第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低其余各队列的优先权逐个降低优先权愈高优先权愈高的队列中，为每个进程所规定的执的队列中，为每个进程所规定的执行行时间片就愈小时间片就愈小。例如，。例如，第二个第二个队列的时间片队列的时间片要要比第一个比第一个队列的时间片队列的时间片长一倍长一倍，第，第i i+1+1个队列的时间片要比第个队列的时间片要比第i i个队列的时间片长个队列的时间片长一倍一倍Operating SystemOperating SystemPa

48、ge 612022-4-23就绪队列就绪队列1 1就绪队列就绪队列2 2就绪队列就绪队列3 3就绪队列就绪队列n nS1S2S3至至CPU至至CPU至至CPU至至CPU( (时间片：时间片：S1 S2 S3) )v调度方式调度方式高高低低优先级优先级时间片时间片小小大大Sn按按FIFO原则原则排队等待调排队等待调度度尚未完成转入第二尚未完成转入第二队列的末尾，按队列的末尾，按FIFO原则等待调原则等待调度度采取按时间片轮采取按时间片轮转的方式运行转的方式运行因等待而放弃因等待而放弃CPU后，后，进入阻塞队列，一旦进入阻塞队列，一旦等待的事件发生，则等待的事件发生，则回到原来的就绪队列回到原来的

49、就绪队列Operating SystemOperating SystemPage 622022-4-23v注意注意仅当第仅当第1(i-1) 1(i-1) 队列均空时，才会调度第队列均空时，才会调度第i i队队列中的进程运行列中的进程运行第第i i队列队列中某进程正在运行时，又有中某进程正在运行时，又有新新进程进进程进入入优先权较高优先权较高的队列的队列( (第第1(i-1)1(i-1)中的任何一中的任何一个队列个队列) )，则此时，则此时新进程将抢占新进程将抢占正在运行进程正在运行进程的处理机，调度程序把正在运行的进程的处理机，调度程序把正在运行的进程放回放回到第到第i i队列队列的末尾的末尾

50、第第i i队列队列中某进程正在运行时，该进程因等待中某进程正在运行时，该进程因等待事件发生而进入阻塞队列，等待事件发生后，事件发生而进入阻塞队列，等待事件发生后，调度程序把进程调度程序把进程放回到第放回到第i i队列队列的末尾的末尾Operating SystemOperating SystemPage 632022-4-23q多级反馈队列调度算法的性能多级反馈队列调度算法的性能v终端型作业用户终端型作业用户终端型作业用户所提交的作业多属于终端型作业用户所提交的作业多属于交互型交互型作作业，通常业，通常较小较小，系统只要能使这些作业在第一，系统只要能使这些作业在第一队列所队列所规定的时间片内完

51、成规定的时间片内完成即可即可v短批处理作业用户短批处理作业用户若在第若在第1 1队列中执行队列中执行一个时间片一个时间片即可完成，便即可完成，便可获得与终端型作业一样的响应时间可获得与终端型作业一样的响应时间如在第一个队列中不能完成，只需在第如在第一个队列中不能完成，只需在第2 2、3 3队队列中各执行一个时间片列中各执行一个时间片v长批处理作业用户长批处理作业用户长作业将依次在第长作业将依次在第1 1，2 2，33，n n队列中执行，队列中执行，最终按轮转方式运行最终按轮转方式运行Operating SystemOperating SystemPage 642022-4-23主动放弃主动放弃

52、CPUCPUq当一个进程当一个进程运行完毕运行完毕或由于某种错误而终止运行或由于某种错误而终止运行q当一个进程在运行中处于当一个进程在运行中处于等待等待状态（等待状态（等待I/OI/O）q在进程通信中，执行中的进程执行了某种原语操在进程通信中，执行中的进程执行了某种原语操作（作（P P操作，阻塞原语，唤醒原语）操作，阻塞原语，唤醒原语）被迫放弃被迫放弃CPUCPUq分时系统中分时系统中时间片到时间片到q当有一个当有一个优先级更高优先级更高的进程到（可抢占式）的进程到（可抢占式） 例如：新创建一个进程，一个阻塞进程变成就绪例如：新创建一个进程，一个阻塞进程变成就绪Operating System

53、Operating SystemPage 652022-4-23q只要只要OS取得对取得对CPU的控制，进程切换就可能发的控制，进程切换就可能发生生:v超级用户调用超级用户调用来自程序的显式请求来自程序的显式请求 (如：打开文件如：打开文件)，该，该进程通常会被阻塞进程通常会被阻塞v陷阱陷阱最末一条指令导致出错，会引起进程移至最末一条指令导致出错，会引起进程移至退出状态退出状态v中断中断 外部因素影响当前指令的执行，控制被转外部因素影响当前指令的执行，控制被转移至移至IH（中断处理程序）（中断处理程序）Operating SystemOperating SystemPage 662022-4-

54、23作业作业1234提交时间提交时间(时时)8.08.59.09.5运行时间运行时间(小时小时)2.00.50.10.2例例1 1 设某系统的作业提交时间和运行时间如下设某系统的作业提交时间和运行时间如下表表, ,请分别计算采用请分别计算采用先来先服务先来先服务算法和算法和短作业短作业优先优先算法时的平均周转时间和平均带权周转时算法时的平均周转时间和平均带权周转时间。间。进程进程A B CDE提交时间提交时间 02468运行时间运行时间 36452Operating SystemOperating SystemPage 672022-4-23例例2 2 有有5 5个批处理的作业（个批处理的作业

55、（A A，B B，C C，D D，E E）几乎同）几乎同时到达一个计算中心，估计的运行时间分别为时到达一个计算中心，估计的运行时间分别为2 2，4 4，6 6，8 8，1010分钟，他们的优先级分别为分钟，他们的优先级分别为1 1，2 2，3 3，4 4，5 5（1 1为最底）。对下面的每一种调度算法，为最底）。对下面的每一种调度算法，分别计算作业的平均周转时间：分别计算作业的平均周转时间：1 1、最高优先级优先；、最高优先级优先；2 2、短作业优先；、短作业优先；Operating SystemOperating SystemPage 682022-4-23q现有现有5 5个作业，他们的到达

56、时间和运行时间如下表，请用个作业，他们的到达时间和运行时间如下表，请用FCFSFCFS、SJFSJF算法分别进行调度，计算平均周转时间和平均算法分别进行调度，计算平均周转时间和平均带权周转时间。带权周转时间。作业号作业号ABCDE到达时间到达时间02468运行时间运行时间364522. 在一个单道批处理系统中，有三个作业进入系统的时间和在一个单道批处理系统中，有三个作业进入系统的时间和运行的时间如下，计算采用响应比高者优先的调度算法时每运行的时间如下，计算采用响应比高者优先的调度算法时每个作业的周转时间。个作业的周转时间。作业作业123进入系统时间进入系统时间9:009:109:15运行时间运

57、行时间60分钟分钟45分钟分钟25分钟分钟Operating SystemOperating SystemPage 692022-4-23q 处理机调度的基本概念处理机调度的基本概念 q作业调度作业调度q进程调度进程调度q 实时调度实时调度 q 多处理机系统中的调度多处理机系统中的调度q 产生死锁的原因和必要条件产生死锁的原因和必要条件 q 预防死锁的方法预防死锁的方法 q 死锁的检测与解除死锁的检测与解除Operating SystemOperating Systemq实现实时调度需要提供的信息v任务变为就绪状态的时间v开始截止时间或完成截止时间v处理所需时间v资源要求v优先级：根据错过截止

58、时间的后果严重程度设置Page 702022-4-23Operating SystemOperating SystemPage 712022-4-2371q 按实时任务性质分按实时任务性质分硬实时调度算法与软实时调度算法硬实时调度算法与软实时调度算法 q 按调度方式分按调度方式分非抢占式与抢占式调度算法非抢占式与抢占式调度算法 Operating SystemOperating SystemPage 722022-4-2372q最早截止时间优先最早截止时间优先EDFEDF（Earliest Deadline FirstEarliest Deadline First）算法）算法q最低松弛度优先即

59、最低松弛度优先即LLFLLF（Least Laxity FirstLeast Laxity First）算法）算法Operating SystemOperating SystemPage 732022-4-23q最早截止时间优先算法（最早截止时间优先算法（EDF）v截止时间越早优先级越高截止时间越早优先级越高vEDF算法可用于抢占式调度，也可用于非抢占式算法可用于抢占式调度，也可用于非抢占式调度。调度。v非抢占式调度方式用于非周期实时任务非抢占式调度方式用于非周期实时任务v抢占式调度方式用于周期实时任务抢占式调度方式用于周期实时任务Operating SystemOperating Syste

60、mPage 742022-4-2374t1342134212 34EDFEDF算法用于非抢占调度方式算法用于非抢占调度方式_ _适用于非周期实时任务适用于非周期实时任务开始截止时间开始截止时间任务执行任务执行任务到达任务到达四个非周期性任务：Operating SystemOperating SystemPage 752022-4-2375例：该例中两个周期性任务，任务例：该例中两个周期性任务，任务A A的周期时间是的周期时间是20ms20ms，每个周期的处理时间为每个周期的处理时间为10ms10ms；任务；任务B B的周期时间为的周期时间为50ms50ms，每个周期的处理时间为每个周期的处理