计算机操作系统(3)第3章 处理机调度与死锁

第三章处理机调度与死锁重点掌握进程调度算法，各适用于何种情况理解常用的几种实时调度算法理解产生死锁的原因掌握银行家算法避免死锁难点多道程序设计中的各种调度算法响应比高者优先调度算法的计算过程银行家算法第三章处理机调度与死锁知识点处理机调度及调度算法多处理机环境下的进程（线程）调度方式产生死锁的原因和必要条件预防死锁的方法，死锁的检测与解除银行家算法第三章处理机调度与死锁处理机是计算机系统中的重要资源在多道程序环境下，进程数目通常多于处理机的数目系统必须按一定方法动态地把处理机分配给就绪队列中的一个进程处理机利用率和系统性能（吞吐量、响应时间）在很大程度上取决于处理机调度WHAT：按什么原则分配CPU—进程调度算法WHEN：何时分配CPU—进程调度的时机HOW：如何分配CPU—CPU调度过程（进程的上下文切换）第三章处理机调度与死锁作业是用户在一次解题或一个事务处理过程中要求计算机系统所做工作的集合，包括用户程序、所需的数据及命令等作业的状态：一个作业进入系统到运行结束，一般需要经历收容、运行、完成三个阶段，与之相对应的是作业的三种状态后备状态运行状态完成状态第三章处理机调度与死锁作业状态间转换运行状态后备状态完成状态就绪阻塞执行时间片完作业注册作业调度进程调度终止作业第三章处理机调度与死锁3.1处理机调度的层次3.2调度队列模型和调度准则3.3调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除3.1处理机调度的层次高级调度(HighScheduling)作业调度或长程调度（Long-TermScheduling）按一定的原则对外存上处于后备状态的作业进行选择，给选中的作业分配内存、输入/输出设备等必要的资源，并建立相应的进程，放入就绪队列，以使该作业的进程获得竞争处理机的权利。也称为接纳调度（AdmissionScheduling）时间尺度：通常是分钟、小时或天。3.1处理机调度的层次关键问题接纳多少个作业即允许多少个作业同时在内存中运行，取决于多道程序度（DegreeofMultiprogramming）作业太多服务质量下降作业太少资源利用率低接纳哪些作业取决于作业调度算法先来先服务短作业优先作业优先权调度响应比调度多道程序度：即允许多少个作业同时在内存中运行。周转时间：从作业被提交给系统开始，到作业完成为止的这段时间间隔。吞吐量：是指在单位时间内系统所完成的作业数。3.1处理机调度的层次低级调度进程调度或短程调度（Short-TermScheduling）按照某种策略和方法选取一个处于就绪状态的进程，将处理机分配给它。常见调度方式非抢占式；抢占式。时间尺度：通常是毫秒级的。由于低级调度算法的频繁使用，要求在实现时做到高效。3.1处理机调度的层次中级调度(Intermediate-LevelScheduling)中程调度(Medium-TermScheduling)引入目的提高内存利用率和系统吞吐量。使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待。交换过程按照给定的原则和策略，将处于外存对换区中的重又具备运行条件的就绪进程调入内存，或将处于内存就绪状态或内存阻塞状态的进程交换到外存对换区。3.1处理机调度的层次进程调度的任务控制、协调进程对CPU的竞争,即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程确定算法的原则具有公平性；资源利用率高（特别是CPU利用率）；在交互式系统中追求响应时间（越短越好）；在批处理系统中追求系统吞吐量。3.1处理机调度的层次进程调度方式非抢占方式(Non-preemptiveMode)抢占方式(PreemptiveMode)3.1处理机调度的层次非抢占方式(Non-preemptiveMode)进程正在处理机上执行时，新就绪的进程进入就绪队列，该进程仍继续执行，直到其完成或发生某种事件而进入完成或阻塞状态时，才转让处理机。引起进程调度的因素正在执行的进程执行完毕，或因发生某事件而不能再继续执行执行中的进程因提出I/O请求而暂停执行；在进程通信或同步过程中执行了某种原语操作，如wait、Block、Wakeup原语优点：算法简单，系统开销小缺点：紧急任务不能及时响应；短进程到达要等待长进程运行结束3.1处理机调度的层次抢占方式(PreemptiveMode)进程正在处理机上执行时，若有某个更为重要或紧迫的进程进入就绪队列，则立即暂停正在执行的进程，将处理机分配给这个更为重要或紧迫的进程抢占式调度原则优先权原则允许高优先权的新到进程抢占当前进程的处理机短作业(进程)优先原则允许执行时间短的新到进程抢占当前进程的处理机时间片原则时间片用完后停止执行，重新进行调度，适用于分时系统优点：适于时间要求严格的实时系统缺点：调度算法复杂，系统开销大3.1处理机调度的层次进程调度的运行频率最高，在分时系统中通常是10～100ms便进行一次进程调度，因此把它称为短程调度。为避免进程调度占用太多的CPU时间，进程调度算法不宜太复杂。作业调度往往是发生在一个(批)作业运行完毕，退出系统，而需要重新调入一个(批)作业进入内存时，故作业调度的周期较长，大约几分钟一次，因此把它称为长程调度。由于其运行频率较低，故允许作业调度算法花费较多的时间。中级调度的运行频率基本上介于上述两种调度之间，因此把它称为中程调度。3.2调度队列模型和调度准则调度队列模型仅有进程调度的调度队列模型具有高级和低级调度的调度队列模型同时具有三级调度的调度队列模型选择调度方式和调度算法的若干准则面向用户的准则面向系统的准则3.2.1调度队列模型仅有进程调度在分时系统中，通常仅设有进程调度系统把这些进程组织成一个就绪队列每个进程在执行时，可能有以下几种情况进程获得CPU正在执行；任务在给定时间片内已完成，释放处理机后为完成状态；任务在时间片内未完成，进入就绪队列末尾；在执行期间因某事件而阻塞。3.2.1调度队列模型仅有进程调度就绪队列阻塞队列进程调度CPU进程完成等待事件交互用户事件出现时间片完3.2.1调度队列模型具有高级和低级调度在批处理系统中，不仅需要进程调度，而且还要有作业调度就绪队列的形式在批处理系统中，常用高优先权队列。进程进入就绪队列时，按优先权高低插入相应位置，调度程序总是把处理机分配给就绪队首进程设置多个阻塞队列根据事件的不同设置多个队列提高效率3.2.1调度队列模型进程调度CPU进程完成时间片完就绪队列…12等待事件等待事件等待事件n12n事件出现事件出现…事件出现后备队列作业调度……阻队列塞2阻队列塞n阻队列塞1与上一模型的主要区别：就绪队列的形式；设置多个阻塞队列3.2.1调度队列模型同时具有三级调度在OS中引入中级调度后，进程的就绪状态分为内存就绪(表示进程在内存中就绪)和外存就绪(进程在外存中就绪)。同样，阻塞状态进一步分成内存阻塞和外存阻塞两种状态。在调出操作的作用下，可使进程状态由内存就绪转为外存就绪，由内存阻塞转为外存阻塞；在中级调度的作用下，又可使外存就绪转为内存就绪。3.2.1调度队列模型同时具有三级调度就绪队列进程调度就绪，挂起队列中级调度阻塞，挂起队列阻塞队列等待事件进程完成时间片完作业调度交互型作业后备队列批量作业挂起挂起事件出现事件出现CPU3.2.2选择调度方式和调度算法的准则面向用户的准则周转时间短周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔(称为作业周转时间)。它包括四部分时间：作业在外存后备队列上等待(作业)调度的时间；进程在就绪队列上等待进程调度的时间进程在CPU上执行的时间；进程等待I/O操作完成的时间。注意：此三项在一个作业的处理过程中可能会发生多次。3.2.2选择调度方式和调度算法的准则面向用户的准则周转时间短平均周转时间带权周转时间：进程（或作业）的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS。而平均带权周转时间则可表示为:niiTnT11niSiiTTnW113.2.2选择调度方式和调度算法的准则面向用户的准则响应时间快响应时间是指从用户通过键盘提交一个请求开始，直至系统中首次产生响应为止的时间交互式系统用周转时间衡量不是最佳截止时间保证截止时间是指某任务必须开始执行的最迟时间或必须完成的最迟时间截止时间是实时系统中的重要指标3.2.2选择调度方式和调度算法的准则面向用户的准则周转时间短响应时间快截止时间保证批处理系统分时系统实时系统等待时间短优先权3.2.2选择调度方式和调度算法的准则面向用户的准则等待时间短等待时间是在就绪队列中等待所花的时间调度算法并不影响进程运行和执行I/O的时间量；只影响进程在就绪队列中等待所花费的时间优先权准则在批处理、实时和分时系统中都可以选择优先权准则，以便让紧急任务先处理有时还选择抢占式调度方式3.2.2选择调度方式和调度算法的准则面向系统的准则系统吞吐量高吞吐量指单位时间内系统所完成的作业数作业调度的方式和算法对吞吐量的大小有较大影响处理机利用率高各类资源的平衡利用使内存、外存和I/O设备的利用率高基于这样的准则，你设计操作系统的调度策略应如何？3.3调度算法在OS中调度的实质是一种资源分配，因而调度算法是指：根据系统的资源分配策略所规定的资源分配算法。问题提出如何制定分配策略：对不同的系统和系统目标，通常采用不同的算法，如短作业优先，时间片轮转等有些算法适用于作业调度，有些适用于进程调度，有些两者皆可3.3调度算法先来先服务和短作业优先算法高优先权优先调度算法基于时间片的轮转调度算法3.3.1先来先服务和短作业优先算法先来先服务(FCFS)/先进先出(FIFO)调度算法按照作业/进程进入系统的先后次序进行调度，先进入系统者先调度；即启动等待时间最长的作业/进程是一种最简单的调度算法，即可用于作业调度，也可用于进程调度术语到达时间、服务时间、开始时间完成时间、等待时间周转时间：完成时间-到达时间带权周转时间：周转时间/服务时间3.3.1先来先服务和短作业优先算法进程名到达时间服务时间开始时间完成时间周转时间带权周转时间平均04A13B25C32D44E044476先来先服务（先进先出）：712101214111418141225.53.592.8AAAABBBCCCCCDDEEEE05101518t3.3.1先来先服务和短作业优先算法先来先服务（先进先出）优缺点比较有利于长作业（进程），而不利于短作业（进程）有利于CPU繁忙型作业（进程），而不利于I/O繁忙型作业（进程）用于批处理系统，不适于分时系统3.3.1先来先服务和短作业优先算法短作业(进程)优先调度算法SJ(P)F以要求运行时间长短进行调度，即启动要求运行时间最短的作业可以分别用于作业调度和进程调度短作业优先(SJF)的调度算法，是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行；而短进程优先(SPF)调度算法，则是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。3.3.1先来先服务和短作业优先算法进程名到达时间服务时间开始时间完成时间周转时间带权周转时间平均04A13B25C32D44E0441短作业/短进程优先（SJF/SPF）：4631.56982.6791392.251318163.282.1AAAABBBCCCCCDDEEEE05101518t进程到达时间要求服务时间开始执行时间完成时间周转时间带权周转时间P107P215P323P432P544等待时间：P1=14;P2=5;P3