操作系统,处理机调度与死锁教案

1、Operating SystemOperating SystemPage 12022-6-16Operating SystemOperating SystemPage 22022-6-16q重点重点v掌握掌握进程调度进程调度算法，各适用于何种情况算法，各适用于何种情况 v理解常用的几种理解常用的几种实时调度实时调度算法算法 v理解产生理解产生死锁死锁的原因的原因 v掌握掌握银行家算法银行家算法避免避免死锁死锁q难点难点v多道程序设计中的各种调度算法多道程序设计中的各种调度算法 v响应比高者优先调度算法的计算过程响应比高者优先调度算法的计算过程 v银行家算法银行家算法 Operating Sys

2、temOperating SystemPage 32022-6-16q知识点知识点v处理机调度及调度算法处理机调度及调度算法v多处理机环境下的进程（线程）调度方式多处理机环境下的进程（线程）调度方式v产生死锁的原因和必要条件产生死锁的原因和必要条件v预防死锁的方法，死锁的检测与解除预防死锁的方法，死锁的检测与解除 v银行家算法银行家算法Operating SystemOperating SystemPage 42022-6-16q处理机是计算机系统中的处理机是计算机系统中的重要资源重要资源q在多道程序环境下，进程数目通常在多道程序环境下，进程数目通常多于处多于处理机的数目理机的数目q系统必须按

3、一定方法系统必须按一定方法动态地动态地把处理机把处理机分配分配给给就绪队列中的一个进程就绪队列中的一个进程q处理机处理机利用率和系统性能利用率和系统性能（吞吐量、响应（吞吐量、响应时间）在很大程度上时间）在很大程度上取决于取决于处理机处理机调度调度分配处理机的任务是由处理机调度程序完分配处理机的任务是由处理机调度程序完成的。它是操作系统设计的中心问题之一。成的。它是操作系统设计的中心问题之一。WHAT：按什么原则分配：按什么原则分配CPU进程调度算法进程调度算法WHEN：何时分配：何时分配CPU 进程调度的时机进程调度的时机 HOW：如何分配：如何分配CPU CPU调度过程（进程调度过程（进程

4、的上下文切换）的上下文切换）Operating SystemOperating SystemPage 52022-6-16q 处理机调度的层次和调度算法的目标处理机调度的层次和调度算法的目标q 作业与作业调度作业与作业调度q 进程调度进程调度q 实时调度实时调度 q 死锁概述死锁概述q 预防死锁预防死锁q 避免死锁避免死锁q 死锁的检测与解除死锁的检测与解除Operating SystemOperating SystemPage 62022-6-16q作业作业是用户在一次解题或一个事务处理过是用户在一次解题或一个事务处理过程中程中要求计算机系统所做工作的集合要求计算机系统所做工作的集合，包，包

5、括用户程序、所需的数据及命令等括用户程序、所需的数据及命令等q作业的状态：作业的状态：一个作业进入系统到运行结一个作业进入系统到运行结束，一般需要经历收容、运行、完成三个束，一般需要经历收容、运行、完成三个阶段，与之相对应的是作业的三种状态阶段，与之相对应的是作业的三种状态v后备状态后备状态v运行状态运行状态v完成状态完成状态Operating SystemOperating SystemPage 72022-6-16运行状态运行状态后备状态后备状态完成状态完成状态就绪就绪阻塞阻塞执行执行I/O完成完成I/O请求请求时间片完时间片完作业作业注册注册作业作业调度调度进程进程调度调度终止终止作业作

6、业q作业作业状态间转换状态间转换Operating SystemOperating SystemPage 82022-6-163.1.1 处理机调度的层次处理机调度的层次1. 高级调度高级调度(High Scheduling) 2. 低级调度低级调度(Low Level Scheduling) 3. 中级调度中级调度(Intermediate-Level Scheduling) Operating SystemOperating SystemPage 92022-6-16q高级调度高级调度(High Scheduling)(High Scheduling) 作业调度作业调度或或长程调度（长程调

7、度（Long-Term Long-Term SchedulingScheduling）v主要任务是按一定的原则对外存上处于后备主要任务是按一定的原则对外存上处于后备状态的作业进行选择，给选中的作业状态的作业进行选择，给选中的作业分配分配内内存、输入存、输入/ /输出设备等输出设备等必要的资源必要的资源，并，并建立建立相相应的应的进程进程，放入放入就绪就绪队列队列，以使该作业的进，以使该作业的进程获得竞争处理机的权利程获得竞争处理机的权利v也称为也称为接纳调度（接纳调度（Admission SchedulingAdmission Scheduling）v高级调度的时间尺度通常是分钟、小时或天高级

8、调度的时间尺度通常是分钟、小时或天Operating SystemOperating SystemPage 102022-6-16在每次作业调度时，须决定：在每次作业调度时，须决定：v接纳多少个作业接纳多少个作业 即允许多少个作业同时在内存中运行，取决于即允许多少个作业同时在内存中运行，取决于多多 道程序度道程序度（Degree of Multiprogramming）作业太多作业太多 服务质量下降服务质量下降作业太少作业太少 资源利用率低资源利用率低v接纳哪些作业接纳哪些作业 取决于作业调度算法取决于作业调度算法先来先服务先来先服务短作业优先短作业优先作业优先权调度作业优先权调度响应比调度响

9、应比调度周转时间太长系统吞吐量太低 适当的折衷：即允许多少个作业同时在内存中运行。：即允许多少个作业同时在内存中运行。：从作业被提交给系统开始，到作业完成为：从作业被提交给系统开始，到作业完成为止的这段时间间隔。止的这段时间间隔。：是指在单位时间内系统所完成的作业数。：是指在单位时间内系统所完成的作业数。Operating SystemOperating SystemPage 112022-6-16q 低级调度低级调度 进程调度进程调度或或短程调度短程调度（Short-Term Scheduling）v主要任务是按照某种主要任务是按照某种策略和方法策略和方法选取选取一个处于一个处于就绪就绪状态

10、的进程，将处理机状态的进程，将处理机分配分配给它给它v常见的低级调度有常见的低级调度有非抢占式非抢占式和和抢占式抢占式两种两种v低级调度的时间尺度通常是低级调度的时间尺度通常是毫秒级毫秒级的。的。由于低级调度算法的由于低级调度算法的频繁使用频繁使用，要求，要求在实现时做到在实现时做到高效高效Operating SystemOperating SystemPage 122022-6-16q 进程调度的任务进程调度的任务 是是控制、协调进程控制、协调进程对对CPUCPU的竞争的竞争, ,即按一定的调度算法从就绪队列中选即按一定的调度算法从就绪队列中选中一个进程，把中一个进程，把CPUCPU的使用权

11、交给被选的使用权交给被选中的进程中的进程Operating SystemOperating SystemPage 132022-6-16q 非抢占方式非抢占方式(Non-preemptive Mode)(Non-preemptive Mode)q 抢占方式抢占方式(Preemptive Mode)(Preemptive Mode)Operating SystemOperating SystemPage 142022-6-16q 非抢占方式非抢占方式(Non-preemptive Mode)(Non-preemptive Mode) 当某一进程正在处理机上执行时，即使有某个更当某一进程正在处理机

12、上执行时，即使有某个更为重要或紧迫的进程进入就绪队列，该进程仍继为重要或紧迫的进程进入就绪队列，该进程仍继续执行，直到其完成或发生某种事件而进入完成续执行，直到其完成或发生某种事件而进入完成或阻塞状态时，才把处理机分配给更为重要或紧或阻塞状态时，才把处理机分配给更为重要或紧迫的进程迫的进程v引起进程调度的因素引起进程调度的因素正在执行的进程执行完毕，正在执行的进程执行完毕， 或因发生某事或因发生某事件而不能再继续执行件而不能再继续执行执行中的进程因提出执行中的进程因提出I/OI/O请求而暂停执行；请求而暂停执行；在进程通信或同步过程中执行了某种原语在进程通信或同步过程中执行了某种原语操作，如操

13、作，如waitwait、BlockBlock、WakeupWakeup原语原语优点优点：算法简单，：算法简单，系统开销小系统开销小缺点缺点：紧急任务不：紧急任务不能及时响应；短进能及时响应；短进程到达要等待长进程到达要等待长进程运行结束程运行结束Operating SystemOperating SystemPage 152022-6-16q 抢占方式抢占方式(Preemptive Mode)(Preemptive Mode) 当某一进程正在处理机上执行时，若有某个当某一进程正在处理机上执行时，若有某个更为重要或紧迫的进程进入就绪队列，则立即更为重要或紧迫的进程进入就绪队列，则立即暂停正在执行

14、的进程，将处理机分配给这个更暂停正在执行的进程，将处理机分配给这个更为重要或紧迫的进程为重要或紧迫的进程抢占式调度主要有以下原则抢占式调度主要有以下原则优先权原则优先权原则 允许高优先权的新到进程抢允许高优先权的新到进程抢占当前进程的处理机占当前进程的处理机短作业短作业( (进程进程) )优先原则优先原则允许执行时间短允许执行时间短的新到进程抢占当前进程的处理机的新到进程抢占当前进程的处理机 时间片原则时间片原则 时间片用完后停止执行，时间片用完后停止执行，重新进行调度，适用于分时系统重新进行调度，适用于分时系统 优点优点：适于时间要：适于时间要求严格的实时系统求严格的实时系统缺点缺点：调度算

15、法复：调度算法复杂，系统开销大杂，系统开销大Operating SystemOperating SystemPage 162022-6-16q 中级调度中级调度(Intermediate-Level (Intermediate-Level Scheduling)Scheduling)v又称为内存调度又称为内存调度v引入目的引入目的是为了提高是为了提高内存利用率内存利用率和和系统吞系统吞吐量。吐量。使那些暂时不能运行的进程不再占使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上用宝贵的内存资源，而将它们调至外存上去等待去等待v主要任务主要任务是按照给定的是按照给定的原则和策略原则

16、和策略，将处，将处于外存于外存对换区对换区中的重又具备运行条件的就中的重又具备运行条件的就绪进程绪进程调入内存调入内存，或将处于内存就绪状态，或将处于内存就绪状态或内存阻塞状态的进程或内存阻塞状态的进程交换到外存交换到外存对换区对换区Operating SystemOperating SystemPage 172022-6-163.1.2 处理机调度算法的目标处理机调度算法的目标q 处理机调度算法的共同目标处理机调度算法的共同目标v资源利用率资源利用率为提高系统的资源利用率，应使系统中的处理机和其它所为提高系统的资源利用率，应使系统中的处理机和其它所有资源尽可能地保持忙碌状态。有资源尽可能地保

17、持忙碌状态。CPUCPU的利用率的利用率=CPU=CPU有效工作时间有效工作时间/ /（CPUCPU有效工作时间有效工作时间+CPU+CPU空空闲等待时间）闲等待时间）v公平性。公平性。指应使诸进程都获得合理的指应使诸进程都获得合理的CPUCPU时间，不会发生进程时间，不会发生进程饥饿现象。对相同类型的进程应获得相同的服务，对于不同饥饿现象。对相同类型的进程应获得相同的服务，对于不同类型的进程，由于其紧急程度或重要性的不同，则应提供不类型的进程，由于其紧急程度或重要性的不同，则应提供不同的服务。同的服务。v平衡性。平衡性。尽可能保持系统资源使用的平衡性，使内存、外存尽可能保持系统资源使用的平衡

18、性，使内存、外存和和I/OI/O设备的利用率高设备的利用率高v策略强制执行。策略强制执行。对所制订的策略其中包括安全策略，只要需对所制订的策略其中包括安全策略，只要需要，必须予以准确地执行，即使会造成某些工作的延迟也要要，必须予以准确地执行，即使会造成某些工作的延迟也要执行。执行。Operating SystemOperating SystemPage 182022-6-16(1) 平均周转时间短。平均周转时间短。 (2) 系统吞吐量高。系统吞吐量高。 (3) 处理机利用率高。处理机利用率高。 3.1.2 处理机调度算法的目标处理机调度算法的目标q 批处理系统的目标批处理系统的目标Operat

19、ing SystemOperating SystemPage 192022-6-16周转时间周转时间是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。由四部分组成： 作业在外存后备队列上等待（作业）调度的时间 进程在就绪队列上等待进程调度的时间 进程在CPU上执行的时间 进程等待I/O操作完成的时间。后3项是在一个作业的整个处理过程中，可能发生多次。 3.1.2 处理机调度算法的目标处理机调度算法的目标q 周转时间周转时间Operating SystemOperating SystemPage 202022-6-16v周转时间短周转时间短平均周转时间平均周转时间niiTnT11niSi

20、iTTnW11带权周转时间：带权周转时间：进程（或作业）的进程（或作业）的周转时周转时间间T T与系统为它与系统为它提供服务的时间提供服务的时间T TS S之比，即之比，即W=T/TW=T/TS S 。而。而平均带权周转时间平均带权周转时间则可表示为则可表示为: : 3.1.2 处理机调度算法的目标处理机调度算法的目标Operating SystemOperating SystemPage 212022-6-16v系统吞吐量高系统吞吐量高吞吐量吞吐量指单位时间内系统所完成的作业数指单位时间内系统所完成的作业数作业调度的方式和算法对吞吐量的大小有较大影响作业调度的方式和算法对吞吐量的大小有较大影

21、响v处理机利用率高处理机利用率高 对于大、中型计算机，对于大、中型计算机，CPUCPU价格十分昂贵，致使处理机价格十分昂贵，致使处理机的利用率成为衡量系统性能的十分重要的指标。而调度的利用率成为衡量系统性能的十分重要的指标。而调度方式和算法对处理机的利用率起着十分重要的作用。如方式和算法对处理机的利用率起着十分重要的作用。如果单纯是为使处理机利用率高，应尽量多的选择计算量果单纯是为使处理机利用率高，应尽量多的选择计算量大的作业运行。这些要求之间存在一定的矛盾。大的作业运行。这些要求之间存在一定的矛盾。3.1.2 处理机调度算法的目标处理机调度算法的目标Operating SystemOpera

22、ting SystemPage 222022-6-163.1.2 处理机调度算法的目标处理机调度算法的目标q 分时系统的目标分时系统的目标v响应时间快响应时间快响应时间响应时间是指从用户通过键盘提交一个请求开始，是指从用户通过键盘提交一个请求开始，直至系统中直至系统中首次首次产生产生响应响应为止的时间为止的时间包括三部分时间：一是请求信息从键盘输入开始，包括三部分时间：一是请求信息从键盘输入开始，直到将其传送到处理机的时间；二是处理机对请求直到将其传送到处理机的时间；二是处理机对请求信息进行处理的时间；三是将所形成的响应信息回信息进行处理的时间；三是将所形成的响应信息回送到终端显示器的时间。送

23、到终端显示器的时间。v均衡性均衡性用户对响应时间的要求并非完全相同。对较复杂任用户对响应时间的要求并非完全相同。对较复杂任务的响应时间允许较长，而对简单任务的响应时间务的响应时间允许较长，而对简单任务的响应时间要短。要短。均衡性是指系统响应时间的快慢应与用户所均衡性是指系统响应时间的快慢应与用户所请求服务的复杂性相适应请求服务的复杂性相适应。Operating SystemOperating SystemPage 232022-6-16q实时系统的目标实时系统的目标v截止时间保证截止时间保证截止时间截止时间是指某任务必须开始执行的最迟时是指某任务必须开始执行的最迟时间或必须完成的最迟时间间或必

24、须完成的最迟时间截止时间是截止时间是实时系统实时系统中的重要指标中的重要指标 可预测性可预测性。在实时系统中，可预测性显得非常重要。3.1.2 处理机调度算法的目标处理机调度算法的目标Operating SystemOperating SystemPage 242022-6-16q各种系统主要目标各种系统主要目标v 周转时间短周转时间短v 响应时间快响应时间快v 截止时间保证截止时间保证批处理系统批处理系统分时系统分时系统实时系统实时系统等待时间短等待时间短优先权优先权Operating SystemOperating SystemPage 252022-6-16v等待时间短等待时间短等待时间

25、等待时间是在就绪队列中等待所花的时间是在就绪队列中等待所花的时间调度算法并不影响进程运行和执行调度算法并不影响进程运行和执行I/O的时的时间量；只影响进程在就绪队列中等待所花费间量；只影响进程在就绪队列中等待所花费的时间的时间v优先权准则优先权准则在在批处理批处理、实时实时和和分时系统分时系统中都可以选择优中都可以选择优先权准则，以便让紧急任务先处理先权准则，以便让紧急任务先处理有时还选择抢占式调度方式有时还选择抢占式调度方式Operating SystemOperating SystemPage 262022-6-16q处理机调度的层次和调度算法的目标处理机调度的层次和调度算法的目标 q作业

26、与作业调度作业与作业调度 q进程调度进程调度q 实时调度实时调度 q 死锁概述死锁概述q 预防死锁预防死锁q 避免死锁避免死锁q 死锁的检测与解除死锁的检测与解除Operating SystemOperating SystemPage 272022-6-16q在在OS中中调度的实质是一种资源分配调度的实质是一种资源分配，因而，因而调度算法是指：根据系统的资源分配策略调度算法是指：根据系统的资源分配策略所规定的资源分配算法所规定的资源分配算法q问题提出问题提出q如何制定分配策略：对不同的系统和系统如何制定分配策略：对不同的系统和系统目标，通常采用不同的算法，如短作业优目标，通常采用不同的算法，如

27、短作业优先，时间片轮转等先，时间片轮转等q有些算法适用于作业调度，有些适用于进有些算法适用于作业调度，有些适用于进程调度，有些两者皆可程调度，有些两者皆可Operating SystemOperating System3.2.1 批处理系统中的作业 1.作业和作业步作业和作业步 作业作业：作业是一个比程序更为广泛的概念，它不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位，从外存调入内存的。 作业步作业步：在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果。我们把其中的每一个加工

28、步骤称一个作业步，各作业步之间存在着相互联系，往往是上一个作业步的输出作为下一个作业步的输入。 2.作业控制块作业控制块JCB 在多道批处理系统中，为每个作业设置了一个作业控制块JCB，它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。在作业运行期间，系统就按照JCB中的信息，和作业说明书对作业进行控制。Operating SystemOperating System 3.作业运行的三个阶段和三种状态作业运行的三个阶段和三种状态 作业从进入系统到运行结束，通常需要经历收容、运行和完成三个阶段。相应的作业也就有“后备状态”、“运行状态”和“完成状态”。 收容阶段：收容

29、阶段：操作员把用户提交的作业，通过某种输入方式或SPOOLing系统，输入到硬盘上，再为该作业建立JCB，并把它放入作业后备队列中，相应的，此时作业的状态为“后备状态”。 运行阶段运行阶段：当作业被作业调度选中后，便为它分配必要的资源和建立进程，并将它放入就绪队列。一个作业从第一次进入就绪状态开始，直到它运行结束前，在此期间都处于“运行状态”。 完成阶段：完成阶段：当作业运行完成、或发生异常情况而提前结束时，作业便进入完成阶段，相应的作业状态为“完成状态”。此时系统中的“终止作业”程序，将会回收已分配给该作业的作业控制块和所有资源，并将作业运行结果信息形成输出文件后输出。3.2.1 批处理系统

30、中的作业Operating SystemOperating SystemPage 302022-6-163.2.1 批处理系统中的作业SPOOLing （即外部设备联机并行操作），它是关于慢速字符设备如何与计算机主机交换信息的一种技术，通常称为“假脱机技术”。spooling系统的三大组成部分：系统的三大组成部分：.输入井和输出井.输入缓冲和输出缓冲.输入进程SPi和输出进程Spo例如：例如：若有进程要求对它打印输出时，SPOOLing系统并不是将这台打印机直接分配给 SPOOLING进程，而是在共享设备（磁盘）上的输出SPOOLing存储区中为其分配一块存储空间，进程的输出数据以文件形式存放

31、于此。各进程的数据输出文件形成了一个输出队列，由输出SPOOLing系统控制这台打印机进程，依次将队列中的输出文件实际打印输出。在SPOOLing 系统中，实际上并没有为任何进程分配，而只是在输入井和输出井中，为进程分配一存储区和建立一张I/O请求表。这样，便把独占设备改造为共享设备。Operating SystemOperating System 作业调度的主要任务 也称为接纳调度，根据JCB中的信息，检查系统中的资源，能否满足作业对资源的需求，以及按照一定的调度算法，从外存的后备队列中，选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程，排在就绪队列上等待调度。因

32、此，也把作业调度（Admission Scheduling）。 在每次执行作业调度时，都须做出以下两个决定 接纳多少个作业 取决于多道程序度，即允许多少个作业同时在内存中运行。 接纳哪些作业 取决于所采用的调度算法。3.2.2 3.2.2 作业调度的主要任务作业调度的主要任务Operating SystemOperating SystemPage 322022-6-16q 先来先服务先来先服务(FCFS)/先进先出先进先出(FIFO)调度算法调度算法v按照作业按照作业/进程进入系统的进程进入系统的先后次序先后次序进行调度，进行调度，先进入系统者先调度；即启动等待时间最长先进入系统者先调度；即启

33、动等待时间最长的作业的作业/进程进程v是一种最简单的调度算法，即可用于是一种最简单的调度算法，即可用于作业调作业调度度，也可用于，也可用于进程调度进程调度q 几个术语几个术语v到达时间、服务时间、开始时间到达时间、服务时间、开始时间v完成时间、等待时间完成时间、等待时间v周转时间：完成时间周转时间：完成时间-到达时间到达时间v带权周转时间：周转时间带权周转时间：周转时间/服务时间服务时间3.2.3 3.2.3 先来先服务和短作业优先调度算法先来先服务和短作业优先调度算法 Operating SystemOperating SystemPage 332022-6-16进程名进程名到达时间到达时间

34、 服务时间服务时间 开始时间开始时间 完成时间完成时间 周转时间周转时间带权周带权周转时间转时间平均平均04A13B25C32D44E044476先来先服务（先进先出）：先来先服务（先进先出）：712101214111418141225.53.592.8A A A A B B B C C C C C D D E E E E05101518tOperating SystemOperating SystemPage 342022-6-16q 先来先服务先来先服务（先进先出）（先进先出）优缺点优缺点v 比较有利于比较有利于长作业（进程）长作业（进程），而不利于，而不利于短作短作业（进程）业（进程）v

35、 有利于有利于CPU繁忙型作业（进程）繁忙型作业（进程） ，而不利于，而不利于I/O繁忙型作业（进程）繁忙型作业（进程）v 用于批处理系统，不适于分时系统用于批处理系统，不适于分时系统Operating SystemOperating SystemPage 352022-6-16q短作业短作业( (进程进程) )优先调度算法优先调度算法SJ(P)FSJ(P)Fv短作业短作业( (进程进程) )优先调度算法优先调度算法SJ(P)FSJ(P)F，以要求，以要求运运行时间长短行时间长短进行调度，即启动要求运行时间最进行调度，即启动要求运行时间最短的作业短的作业v可以分别用于可以分别用于作业调度作业调

36、度和和进程调度进程调度v短作业优先短作业优先(SJF)(SJF)的调度算法，是从后备队列的调度算法，是从后备队列中选择一个或若干个中选择一个或若干个估计运行时间估计运行时间最短的作业，最短的作业，将它们调入内存运行；而短进程优先将它们调入内存运行；而短进程优先(SPF)(SPF)调调度算法，则是从就绪队列中选出一度算法，则是从就绪队列中选出一估计运行时估计运行时间间最短的进程，将处理机分配给它，使它立即最短的进程，将处理机分配给它，使它立即执行并一直执行到完成执行并一直执行到完成，或，或发生某事件发生某事件而被阻而被阻塞放弃处理机时，再重新调度塞放弃处理机时，再重新调度Operating Sy

37、stemOperating SystemPage 362022-6-16进程名进程名到达时间到达时间 服务时间服务时间 开始时间开始时间 完成时间完成时间 周转时间周转时间带权周带权周转时间转时间平均平均04A13B25C32D44E0441短作业短作业/短进程优先（短进程优先（SJF/SPF）：）：4633/26988/391399/413181616/540/52.1A A A AB B BC C C C CD DE E E E05101518tOperating SystemOperating SystemPage 372022-6-16qFCFS/SJF调度算法的性能调度算法的性能SJ

38、FSJF能有效地降低作业的平均等待时间，提高系统吞吐量能有效地降低作业的平均等待时间，提高系统吞吐量 作业作业调度调度 情况情况 算法算法进程名进程名ABCDE平均平均到达时间到达时间01234服务时间服务时间43524FCFS完成时间完成时间47121418周转时间周转时间461011149带权周转时间带权周转时间1225.53.52.8SJF完成时间完成时间4918613周转时间周转时间4816398带权周转时间带权周转时间12.673.11.52.252.1SJFSJF平均周转平均周转时间和平均带时间和平均带权周转时间明权周转时间明显改善显改善Operating SystemOperat

39、ing SystemPage 382022-6-16qSJ(P)F调度算法也存在不容忽视的缺点调度算法也存在不容忽视的缺点v对对长作业不利长作业不利。严重的是，若一长作业。严重的是，若一长作业(进程进程)进进入系统的后备队列入系统的后备队列(就绪队列就绪队列)，由于调度程序总，由于调度程序总是优先调度那些是优先调度那些(即使是后进来的即使是后进来的)短作业短作业(进程进程)，将导致长作业将导致长作业(进程进程)长期不被调度长期不被调度饥饿饥饿v完全未考虑作业完全未考虑作业(进程进程)的的紧迫程度紧迫程度，因而不能保，因而不能保证证紧迫性紧迫性作业作业(进程进程)会被会被及时处理及时处理v由于作

40、业由于作业(进程进程)的长短只是根据的长短只是根据用户用户所提供的所提供的估估计执行时间计执行时间而定的，而用户又可能会而定的，而用户又可能会有意或无意有意或无意地地缩短缩短其作业的估计其作业的估计运行时间运行时间，致使该算法不一，致使该算法不一定能真正做到短作业优先调度。定能真正做到短作业优先调度。Operating SystemOperating System2022-6-16391 1、在单道批处理系统中，有五个作业进入输入井的时间在单道批处理系统中，有五个作业进入输入井的时间及需要执行的时间如下表所示，及需要执行的时间如下表所示，并约定当这五个作业全部并约定当这五个作业全部进入输入井后

41、立即进行调度进入输入井后立即进行调度，忽略调度的时间开销。，忽略调度的时间开销。要求：写出分别采用先来先服务和最短执行时间优先调度要求：写出分别采用先来先服务和最短执行时间优先调度算法时的调度次序和作业平均周转时间。算法时的调度次序和作业平均周转时间。作业号进入输入井时间需执行时间（分钟）开始执行时间结束执行时间周转时间（分钟）110 0040 210 1030 310 2020 410 3025 510 4010 Operating SystemOperating System2022-6-1640作业号进入输入井时间需执行时间（分钟）开始执行时间结束执行时间周转时间（分钟）110 0040

42、 210 1030 310 2020 410 3025 510 4010 Operating SystemOperating System2022-6-1641作业号进入输入井时间需执行时间（分钟）开始执行时间结束执行时间周转时间（分钟）110 004010:40 11:2080 210 1030 11:2011:50 100 310 2020 11:5012:10 110 410 3025 12:1012:35 125 510 4010 12:3512:45 125 调度次序：1-2-3-4-5平均周转时间为（80+100+110+125+125)/5=108 分钟Operating Sys

43、temOperating System2022-6-1642作业号进入输入井时间需执行时间（分钟）开始执行时间结束执行时间周转时间（分钟）110 0040 210 1030 310 2020 410 3025 510 4010 Operating SystemOperating System2022-6-1643作业号进入输入井时间需执行时间（分钟）开始执行时间结束执行时间周转时间（分钟）110 0040 12:0512:45 165 210 1030 11:3512:05 115 310 2020 10:5011:10 50 410 3025 11:1011:35 65 510 401010

44、:40 10:50 10调度次序：5-3-4-2-1平均周转时间为（165+115+50+65+10)/5=81 分钟Operating SystemOperating System3.2.4 优先级调度算法和高响应比优先调度算法 1.优先级调度算法(priority-scheduling algorithm) 基于作业的紧迫程度，由外部赋予作业相应的优先级，调度算法是根据该优先级进行调度的。这样就可以保证紧迫性作业优先运行。 2.高响应比优先调度算法 高响应比优先调度算法则是既考虑了作业的等待时间，又考虑作业运行时间的调度算法，因此既照顾了短作业，又不致使长作业的等待时间过长，从而改善了处理

45、机调度的性能。 高响应比优先算法的实现 优先级的变化规律可描述为： 由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先级又相当于响应比RP。据此，又可表示为： Operating SystemOperating SystemPage 452022-6-16q优先权调度算法的类型优先权调度算法的类型v非抢占式非抢占式优先权调度算法优先权调度算法v抢占式抢占式优先权调度算法优先权调度算法3.2.4 3.2.4 优先级调度算法和高响应比优先调度算优先级调度算法和高响应比优先调度算法法Operating SystemOperating SystemPage 462022-6-16q优先权

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

47、rating SystemPage 472022-6-16q优先权调度算法的类型优先权调度算法的类型v抢占式抢占式优先权调度算法优先权调度算法把处理机分配给优先权最高的进程，但在执行把处理机分配给优先权最高的进程，但在执行期间，只要出现另一个优先权更高的进程，则期间，只要出现另一个优先权更高的进程，则进程调度程序就进程调度程序就立即停止立即停止当前进程的执行，并当前进程的执行，并将处理机分配给新到的优先权最高的进程将处理机分配给新到的优先权最高的进程注意注意：只要只要系统中系统中出现出现一个新的就绪进程，一个新的就绪进程，就就进行进行优先权优先权比较比较该调度算法，能更好地该调度算法，能更好地

48、满足紧迫作业满足紧迫作业的要求，的要求，故而常用于要求比较严格的实时系统中，以及故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中对性能要求较高的批处理和分时系统中Operating SystemOperating SystemPage 482022-6-16q优先权的类型（优先权的类型（P94P94）v静态优先权静态优先权静态优先权在创建进程时确定，且在进程的整个静态优先权在创建进程时确定，且在进程的整个运行期间运行期间保持不变保持不变。一般地，优先权是利用某一。一般地，优先权是利用某一范围内的一个整数来表示的，例如，范围内的一个整数来表示的，例如，0 0 7 7或或

49、0 0 255255， 又把该整数称为又把该整数称为优先数优先数v确定进程静态优先权的依据确定进程静态优先权的依据进程类型进程类型: :系统进程，用户进程系统进程，用户进程进程对资源的需求进程对资源的需求用户要求用户要求v静态优先权特点静态优先权特点系统开销小、不够精确、一般用在要求不高的系系统开销小、不够精确、一般用在要求不高的系统中统中问题：用户将优先权设的较高，对其他进程不利！问题：用户将优先权设的较高，对其他进程不利！ 短进程优先对长进程不利！短进程优先对长进程不利！Operating SystemOperating SystemPage 492022-6-16v动态优先权动态优先权随

50、随进程的推进进程的推进或随其或随其等待时间等待时间的增加而改变，以获的增加而改变，以获得更好的调度性能得更好的调度性能可规定，在可规定，在就绪队列中的进程就绪队列中的进程，随其，随其等待时间的增等待时间的增长长，其优先权，其优先权以速率以速率a提高提高具有具有相同相同优先权优先权初值初值的进程，则的进程，则最先进入最先进入就绪就绪队列，其将因其动态优先权变得最高而队列，其将因其动态优先权变得最高而优先获优先获得得处理机，此即处理机，此即FCFS算法算法具有各不相同的优先权初值的就绪进程，则具有各不相同的优先权初值的就绪进程，则优优先权初值低先权初值低的进程，在的进程，在等待了足够的时间等待了足

51、够的时间后，后，其其优先权便可能升为最高优先权便可能升为最高，从而可以获得处理，从而可以获得处理机机当采用抢占式优先权调度算法时，如果再当采用抢占式优先权调度算法时，如果再规定当前规定当前进程进程的优先权的优先权以速率以速率b下降下降，则可防止一个长作业，则可防止一个长作业长期地长期地垄断垄断处理机处理机Operating SystemOperating SystemPage 502022-6-16进程进程名名到达到达时间时间服务服务时间时间静态优静态优先权先权开始开始时间时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间平均平均静态优先权，静态优先权，非抢占式非抢占式（1为高优先权

52、）为高优先权）04A413B225C332D544E1044148418111010/311161414/516181515/29.42.93考虑一下考虑一下抢占式抢占式，情况如何？，情况如何？Operating SystemOperating SystemPage 512022-6-16q其中，其中，RQRQ为就绪队列指针，为就绪队列指针，EPEP为运行队列指针。为运行队列指针。Operating SystemOperating SystemPage 522022-6-16进程进程名名到达到达时间时间服务服务时间时间静态优静态优先权先权开始开始时间时间完成完成时间时间周转周转时间时间带权周带

53、权周转时间转时间平均平均04A413B225C332D544E1016164484114318131111/516181515/29.83.14静态优先权，静态优先权，抢占式抢占式（1为高优先权）为高优先权）A B B B E E E E C C C C C A A A D D05101518tB AA CDEA CDOperating SystemOperating System作业作业到达时间到达时间运行时间运行时间优先级优先级A082B141C264（高）高）Page 532022-6-16假定在单假定在单CPU条件下有下列要执行的作业：条件下有下列要执行的作业： （1）用一个执行时间图

54、描述在采用非抢占优先级算法时执行这些作业的情况；）用一个执行时间图描述在采用非抢占优先级算法时执行这些作业的情况；（2）对于上述算法，各个作业的周转时间是多少？平均周转时间是多少？）对于上述算法，各个作业的周转时间是多少？平均周转时间是多少？（3）对于上述算法，各个作业的带权周转时间是多少？）对于上述算法，各个作业的带权周转时间是多少？ 平均带权周转时间是多少平均带权周转时间是多少Operating SystemOperating SystemPage 542022-6-16ACB01281418T任务执行任务到达AB C（2） 平均周转时间 ：（8+12+17）/312.33（3） 平均带权

55、周转时间 ：（8/8+12/6+17/3）/32.22Operating SystemOperating SystemPage 552022-6-16q高响应比优先调度算法（高响应比优先调度算法（HRF）v是是FCFS和和SJF的结合，克服了两种算法的的结合，克服了两种算法的缺点缺点v调度策略调度策略：响应比：响应比最高的作业优先启动最高的作业优先启动v因因等待时间等待时间+服务时间服务时间=该作业的该作业的响应时间响应时间，故该优先权又相当于故该优先权又相当于响应比响应比RP。据此，又。据此，又可表示为可表示为时时间间务务时时间间权权务务时时间间等等待待+ 要+ 要求求服服优优先先= =要要

56、求求服服时间务时间响应时间权务时间务时间等等待待+ 要+ 要求求服服优优先先=要要求求服服要要求求服服Operating SystemOperating SystemPage 562022-6-16q 对对HRF的小结的小结v等待时间相同等待时间相同的作业，则的作业，则要求服务的时间愈要求服务的时间愈短短，其，其优先权愈高优先权愈高，v要求服务的时间相同要求服务的时间相同的作业，则的作业，则等待时间愈等待时间愈长长，其，其优先权愈高优先权愈高，v长作业，优先权长作业，优先权随等待时间的增加随等待时间的增加而提高，而提高，其等待时间足够长时，其优先权便可升到很其等待时间足够长时，其优先权便可升到

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

58、时间响应比响应比开始开始时间时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间平均平均04A13B25C32D44E044114181414/447629141212/579638.42.38高响应比优先，非高响应比优先，非抢占式抢占式21.41.51231.752.42.25时时间间务务时时间间权权务务时时间间等等待待+ 要+ 要求求服服优优先先= =要要求求服服=当前时间当前时间-到达时间到达时间服务时间服务时间+服务时间服务时间Operating SystemOperating SystemPage 582022-6-16假定在单假定在单CPU条件下有下列要执行的作业：条件下有

59、下列要执行的作业：（1）用一个执行时间图描述在）用一个执行时间图描述在采用响应比高者优先调度算法采用响应比高者优先调度算法 执行这些作业的情况；执行这些作业的情况；（2）计算各作业的）计算各作业的周转时间和平均周转时间。周转时间和平均周转时间。作业作业到达时间到达时间运行时间运行时间A08B14C26Operating SystemOperating Systemq假设有三个同时到达的作业J1、J2和J3，它们的执行时间分别是T1、T2和T3，且T1T2T3。单处理机系统采用短作业优先算法运行，则平均周转时间是（ ）。Page 592022-6-16Operating SystemOperat

60、ing SystemPage 602022-6-16q处理机调度的层次和调度算法的目标处理机调度的层次和调度算法的目标 q作业与作业调度作业与作业调度 q进程调度进程调度q 实时调度实时调度 q 死锁概述死锁概述q 预防死锁预防死锁q 避免死锁避免死锁q 死锁的检测与解除死锁的检测与解除Operating SystemOperating System3.3.1 进程调度的任务、机制和方式 1.进程调度任务进程调度任务 保存处理机的现场信息：在进行调度时首先需要保存当前进程的处理机的现场信息，如程序计数器、多个通用寄存器中的内容等。 按某种算法选取进程：调度程序按某种算法，从就绪队列中选取一个进