《操作系统》第3章处理机调度与死锁.

第三章处理机调度与死锁重点掌握进程调度算法，各适用于何种情况理解常用的几种实时调度算法理解产生死锁的原因掌握银行家算法避免死锁难点多道程序设计中的各种调度算法响应比高者优先调度算法的计算过程银行家算法第三章处理机调度与死锁知识点处理机调度及调度算法多处理机环境下的进程（线程）调度方式产生死锁的原因和必要条件预防死锁的方法，死锁的检测与解除银行家算法第三章处理机调度与死锁处理机是计算机系统中的重要资源在多道程序环境下，进程数目通常多于处理机的数目系统必须按一定方法动态地把处理机分配给就绪队列中的一个进程处理机利用率和系统性能（吞吐量、响应时间）在很大程度上取决于处理机调度WHAT：按什么原则分配CPU—进程调度算法WHEN：何时分配CPU—进程调度的时机HOW：如何分配CPU—CPU调度过程（进程的上下文切换）第三章处理机调度与死锁3.1处理机调度的层次和调度算法的目标3.2作业与作业调度3.3进程调度3.4实时调度3.5死锁描述3.6预防死锁3.7避免死锁3.8死锁的检测与解除3.1.1处理机调度的层次高级调度(HighScheduling)作业调度或长程调度（Long-TermScheduling）按一定的原则对外存上处于后备状态的作业进行选择，给选中的作业分配内存、输入/输出设备等必要的资源，并建立相应的进程，放入就绪队列，以使该作业的进程获得竞争处理机的权利。也称为接纳调度（AdmissionScheduling）时间尺度：通常是分钟、小时或天。3.1.1处理机调度的层次低级调度进程调度或短程调度（Short-TermScheduling）按照某种策略和方法选取一个处于就绪状态的进程，将处理机分配给它。常见调度方式非抢占式；抢占式。时间尺度：通常是毫秒级的。由于低级调度算法的频繁使用，要求在实现时做到高效。3.1.1处理机调度的层次中级调度(Intermediate-LevelScheduling)中程调度(Medium-TermScheduling)引入目的提高内存利用率和系统吞吐量。使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待。交换过程按照给定的原则和策略，将处于外存对换区中的重又具备运行条件的就绪进程调入内存，或将处于内存就绪状态或内存阻塞状态的进程交换到外存对换区。3.1.1处理机调度的层次进程调度的运行频率最高，在分时系统中通常是10～100ms便进行一次进程调度，因此把它称为短程调度。为避免进程调度占用太多的CPU时间，进程调度算法不宜太复杂。作业调度往往是发生在一个(批)作业运行完毕，退出系统，而需要重新调入一个(批)作业进入内存时，故作业调度的周期较长，大约几分钟一次，因此把它称为长程调度。由于其运行频率较低，故允许作业调度算法花费较多的时间。中级调度的运行频率基本上介于上述两种调度之间，因此把它称为中程调度。3.1.2处理机调度算法的目标处理调度算法的共同目标资源的利用率公平性平衡性策略强制执行CPU的的的的=CPU的的的的的的CPU的的的的的的+CPU的的的的的的3.1.2处理机调度算法的目标基本术语到达时间作业进入后备作业队列或新创建进程进入就绪队列的时刻；服务时间作业（进程）占用处理机的时间开始时间作业被创建进入就绪队列或进程首次占有处理机的时刻完成时间用户获得作业执行结果的时刻。3.1.2处理机调度算法的目标批处理系统的目标平均周转时间短周转时间，指从作业被提交给系统开始，到作业完成为止的这段时间间隔(称为作业周转时间)。它包括四部分时间：作业在外存后备队列上等待(作业)调度的时间；进程在就绪队列上等待进程调度的时间进程在CPU上执行的时间；进程等待I/O操作完成的时间。注意：此三项在一个作业的处理过程中可能会发生多次。周转时间=完成时间-到达时间3.1.2处理机调度算法的目标批处理系统的目标平均周转时间短平均周转时间带权周转时间：进程（或作业）的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS。平均带权周转时间niiTnT11niSiiTTnW11带权周转时间=周转时间/服务时间3.1.2处理机调度算法的目标批处理系统的目标系统吞吐量高吞吐量指单位时间内系统所完成的作业数作业调度的方式和算法对吞吐量的大小有较大影响处理机利用率高各类资源的平衡利用使内存、外存和I/O设备的利用率高3.1.2处理机调度算法的目标分时系统的目标响应时间快响应时间，从用户通过键盘提交一个请求开始，直至系统中首次产生响应为止的时间交互式系统用周转时间衡量不是最佳均衡性系统响应时间的快慢与用户所请求服务的复杂性相适应。3.1.2处理机调度算法的目标实时系统的目标截止时间保证截止时间，某任务必须开始执行的最迟时间或必须完成的最迟时间截止时间是实时系统中的重要指标可预测性数据的到达或将要处理任务的要求是可预测的。3.1.2处理机调度算法的目标问题的本质周转时间短响应时间快截止时间保证批处理系统分时系统实时系统等待时间短优先级3.1.2处理机调度算法的目标目标实现等待时间短等待时间，在就绪队列中等待所花的时间调度算法并不影响进程运行和执行I/O的时间量；只影响进程在就绪队列中等待所花费的时间优先级准则在批处理、实时和分时系统中都可以选择优先级准则，以便让紧急任务先处理有时还选择抢占式调度方式3.2作业与作业调度3.2.1批处理系统中的作业3.2.2作业调度的主要任务3.2.3先来先服务和短作业优先调度算法3.2.4优先级调度算法和高响应比调度算法3.2.1批处理系统中的作业作业和作业步作业(Job)。用户在一次解题或一个事务处理过程中要求计算机系统所做工作的集合，包括用户程序、所需的数据及命令等。作业步(JobStep)。通常，在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果。例，一个典型的作业可分成三个作业步：①“编译”作业步；②“链接装配”作业步；③“运行”作业步。3.2.1批处理系统中的作业作业控制块（JobcontrolBlock,JCB）作业在系统中存在的标志；包括作业标识、用户名称、用户账号、作业类型（CPU繁忙型、I/O繁忙型、批量型、终端型）、作业状态、调度信息（优先级、作业运行时间）、资源需求（预计运行时间、要求内存大小）、资源使用情况。3.2.1批处理系统中的作业作业运行的三个阶段和三种状态一个作业进入系统到运行结束，一般需要经历收容、运行、完成三个阶段，与之相对应的是作业的三种状态后备状态运行状态完成状态3.2.1批处理系统中的作业作业状态间转换运行状态后备状态完成状态就绪阻塞执行时间片完作业注册作业调度进程调度终止作业3.2.2作业调度的主要任务作业调度的主要功能根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。接纳多少个作业即允许多少个作业同时在内存中运行，取决于多道程序度（DegreeofMultiprogramming）作业太多服务质量下降作业太少资源利用率低3.2.2作业调度的主要任务接纳哪些作业取决于作业调度算法先来先服务短作业优先作业优先级调度响应比调度多道程序度：即允许多少个作业同时在内存中运行。周转时间：从作业被提交给系统开始，到作业完成为止的这段时间间隔。吞吐量：是指在单位时间内系统所完成的作业数。3.2.3先来先服务和短作业优先算法先来先服务(FCFS)/先进先出(FIFO)调度算法按照作业/进程进入系统的先后次序进行调度，先进入系统者先调度；即启动等待时间最长的作业/进程最简单的调度算法，既可用于作业调度，也可用于进程调度3.2.3先来先服务和短作业优先算法进程名到达时间服务时间开始时间完成时间周转时间带权周转时间平均04A13B25C32D44E044476先来先服务（先进先出）：712101214111418141225.53.592.8AAAABBBCCCCCDDEEEE05101518t3.2.3先来先服务和短作业优先算法先来先服务（先进先出）优缺点比较有利于长作业（进程），而不利于短作业（进程）有利于CPU繁忙型作业（进程），而不利于I/O繁忙型作业（进程）用于批处理系统，不适于分时系统3.2.3先来先服务和短作业优先算法先来先服务（先进先出）等待时间：J1=0;J2=0;J3=100；J4=100平均等待时间：(0+0+100+100)/4=50平均周转时间：(1+100+101+200)/4=100.5平均带权周转时间：(1+1+101+2)/4=26.25作业到达时间服务时间开始时间完成时间周转时间带权周转时间J101J21100J311J4210001110110110210220211100110110120023.2.3先来先服务和短作业优先算法先来先服务（先进先出）等待时间：J1=0;J2=1;J3=0；J4=100平均等待时间：(0+1+0+100)/4=25.25平均周转时间：(1+1+101+200）/4=75.75平均带权周转时间：（1+1+1.01+2）/4=1.2525作业到达时间服务时间开始时间完成时间周转时间带权周转时间J101J311J21100J421000112210210220211111011.0120023.2.3先来先服务和短作业优先算法短作业(进程)优先调度算法SJ(P)F按运行时间长短进行调度，即先启动要求运行时间最短的作业（进程）短作业优先(SJF)的调度算法：从后备队列中选择一个或若干个估计运行时间最短的作业，调入内存运行；短进程优先(SPF)调度算法：从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。3.2.3先来先服务和短作业优先算法作业名到达时间服务时间开始时间完成时间周转时间带权周转时间平均04A13B25C32D44E0441短作业/短进程优先（SJF/SPF）：4631.56982.6791392.251318163.282.1AAAABBBCCCCCDDEEEE05101518t3.2.3先来先服务和短作业优先算法SJ(P)F调度算法的缺点对长作业不利。严重的是，由于调度程序总是优先调度短作业(进程)，将导致长作业(进程)长期不被调度——饥饿不能保证紧迫性作业(进程)会被及时处理；不一定能真正做到短作业优先调度。由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间。优先级调度算法对于先来先服务算法，作业的等待时间就是作业的优先级，等待时间越长，优先级越高。对于短作业优先算法，作业的长短就是作业的优先级，作业所需时间越短，其优先级越高。在优先级算法，根据作业的紧迫程度，由外部给予作业不同的优先级，然后根据优先级调度3.2.4优先级和高响应比优先调度算法高响应比优先调度算法（HRRN）FCFS和SJF的结合，克服了两种算法的缺点调度策略：响应比最高的作业优先启动因等待时间+服务时间=该作业的响应时间，故该优先级又相当于响应比RP。据此，又可表示为3.2.4优先级和高优先比优先调度算法优先级=等待时间+要求服务时间要求服务时间Rp=等待时间+要求服务时间要求服务时间响应时间要求服务时间=3.2.4优先级和高优先比优先调度算法对HRRN的小结等待时间相同的作业，则要求服务的时间愈短，其优先级愈高，要求服务的时间相同的作业，则等待时间愈长，其优先级愈高，长作业，优先级随等待时间的增加而提高，其等待时间足够长时，其优先级便可升到很