75操作系统第三章处理机调度与死锁

第三章处理机调度与死锁主要内容：●处理机的两级调度●作业调度●进程调度●死锁●什么是死锁●预防死锁。●避免死锁。●检测死锁。第一部分处理机调度主要内容：两级调度：作业调度和进程调度的调度算法。作业调度：从磁盘的众多的作业中选择作业进入内存。进程调度：进入系统中若干进程如何争夺cpu的控制权。§1.cpu的调度层级作业调度：宏观调度（用户的观点）进程调度：微观调度（系统的观点）一，作业调度和进程调度的任务1.作业调度的任务(1)从磁盘的后备作业中按一定的算法选择作业进入内存;(2)建立相应的进程于就绪状态,使它们有资格获得cpu的控制权;(3)当作业执行完成后,作善后处理工作,如:撤销JCB,回收资源等。2.进程调度的任务（1）按一定的算法将CPU分配某一就绪状态的进程，规定占用CPU的时间，或测试优先级；（2）当CPU被进程占用时，建立相应的运行环境，如：保护现场等。二，两级调度的关系执行运行就绪等待后备提交完成作业录入：sploonig系统作业调度作业调度进程调度注意：作业的执行状态就是进程处于运行,就绪,等待等状态之中。§2作业调度一.作业的状态及其转换1.作业的4种状态①提交状态：一个作业被提交给机房后或用户通过终端设备向计算机中输入其作业时所处的状况。②后备状态：作业的全部信息都已输入，并存放在磁盘中等待运行。③运行状态：作业被调度程序选中而被送入主存中投入运行。④完成状态：作业完成其全部任务，释放其所占用的全部资源，准备退出系统。2.作业状态转换提交状态→后备状态→运行状态→完成状态二.作业调度的功能①记录进入系统的各作业的情况。建立作业控制块jcb(jobcontrolblock)。作业控制块记录了每个作业类型、状态、资源请求及分配情况。②按调度算法从后备作业中挑选出若干作业投入运行。③为选中的作业分配主存和外设资源。为选中的作业分配所需要的系统资源。④作业结束后作善后处理工作。收回该作业所占用的全部资源，撤消作业控制块以及与该作业有关的全部进程。三.作业控制块(JCB)每个作业进入系统时由系统为其建立一个作业控制块JCB（JobControlBlock)，它是存放作业控制和管理信息的数据结构，主要信息见右图。四.调度性能的衡量1.调度算法设计时考虑的因素①与整体目标一致●批量系统:尽量增加系统作业的平均吞吐量,提高系统的效率.●分时系统:保证用户能忍受时间.●实时系统:保证及时响应和处理.资源负载均匀,作业应能运行,特殊要求等。②考虑的调度原则●公平性:对用户要公平和满意,不能无故地拖延作业的运行.●平衡资源的使用:将I/O繁忙的作业和CPU繁忙的作业搭配起来,尽量使资源都处于忙碌.●较大的流量:单位时间内,尽可多的为多个作业服务.保证系统的吞吐能力.2.调度性能的衡量通常采用平均周转时间和平均带权周转时间衡量.(1)周转时间和平均周转时间作业的周转时间ti：一个作业在系统中停留的时间.ti=tci-tsitci:作业完成时间tsi:作业进入输入井时间n个作业的平均周转时间t:t越小调度性能越好;系统吞吐量大,资源利用率越高.(2)带权周转时间和平均带权周转时间带权周转时间wi:周转时间/运行时间作业在系统中相对等待时间注：平均周转时间：用来衡量不同的调度算法对同一作业流的调度性能。平均带权周转时间：用来衡量某种调度算法对不同作业流的调度性能。五.作业调度算法●先来先服务调度算法●短作业优先调度算法●响应比高者优先调度算法●优先数调度算法●均衡调度算法1.先来先服务调度算法（FCFS）按作业到达输入井的先后次序，且满足资源要求挑选作业进行的调度。例子在一个多道程序系统中，有作业A,B,C,D,E；用户使用的空间100KB。各作业进入输入井的时间和要求运行的时间如下表：根据达到输入井的先后次序和满足资源要求条件,4个作业的调度次序：A→B→D→C→E作业进入输入井的时间（小时）要求运行时间（分钟）主存量要求A10.14215kB10.33060kC10.52450kD10.62410kE10.71220k先来先服务算法（0.1小时＝6分钟）作业进入输入井时间(小时)执行时间（分钟）开始时间(小时)完成时间(小时)周转时间(小时)带权周转时间(小时)A10.110.142（0.7）10.110.80.71B10.310.330（0.5）10.811.312C10.511.324（0.4）11.712.11.64D10.610.624（0.4）11.311.71.12.75E10.711.312（0.2）12.112.31.68平均周转时间t=(0.7+1+1.6+1.1+1.6)/5=1.2(小时)平均带权周转时间w=(1+2+4+2.75+8)/5=3.55(小时)算法的优缺点：优点：实现简单；算法具有一定的公平性。缺点：当计算时间长的作业先达到而被选中时，可能使计算时间短的作业长期等待，则周转时间长，平均周转时间增大，降低了系统的吞吐能力。入内存时间（小时）2.短作业优先调度算法每次总是选择满足资源要求的作业优先调入内存，然后挑选要求运行时间最短的作业投入运行。上例：短作业优先调度的次序：A→B→D→E→C作业入主存时间(小时)执行时间（分钟）开始时间(小时)完成时间(小时)周转时间(小时)带权周转时间(小时)A10.110.142（0.7）10.110.80.71B10.310.330（0.5）10.811.312C10.511.724（0.4）11.912.31.84.5D10.610.624（0.4）11.311.71.12.75E10.711.712（0.2）11.711.91.26入输入井时间(小时)平均周转时间t=(0.7+1+1.8+1.1+1.2)/5=1.16(小时)平均带权周转时间w=(1+2+4.5+1.75+6)/5=3.25(小时)比先来先服务算法调度,t,w都下降了.短作业优先调度算法的优缺点：优点:提高了系统的吞吐能力.缺点：不断地接受计算时间短的作业,会使计算时间长的作业长期等待,长作业用户不满意.3.响应比高者优先调度算法每一次计算每个作业的响应比,从满足资源的作业中挑选响应比高者优先调度.注:该算法是先来先服务调度算法和短作业优先调度算法的折衷方案.响应比=————等待时间计算时间例子:单道程序系统中,三个作业A,B,C达到输入井的时间及要求的运行时间,如下表:作业进入输入井的时间要求运行时间（小时）不考虑资源要求A8:501.5B9:000.4C9:301从达到的时间9:30开始,计算A,B,C的响应比:A,B,C等待的时间分别:40分(9:30-8:50),30分(9:30-9:00),0分:第一遍A的响应比=40/90分=4/9B的响应比=30/24分=5/4C的响应比=0/60分=0应该调度B:周转时间t=(9:30-9:00=30分=0.5小时)+0.4=0.9(小时)带权周转时间w=0.9/0.4=2.25(小时)第二遍:B结束.开始时间:9:54小时(9:30+24分(0.4*6=24分))A的响应比=64/90分=32/45(9:54-8:50=64分)C的响应比=24/60分=2/5(9:54-9:30=24分)应该调度A:周转时间t=(9:54-8:50)+1.5=2.54(小时)带权周转时间w=2.54/1.5=1.69(小时)最后调度C:开始时间11:24小时(9:54+1.5小时)周转时间t=(11:24-9:30=1.54小时)+1=2.9(小时)带权周转时间w=2.9/1=2.9(小时)平均周转时间:T=(0.9+2.54+2.9)/3=2.11(小时)平均带权周转时间:w=(2.25+1.69+2.9)/3=2.26(小时)优缺点:优点:既照顾了作业到来的先后次序,又考虑了要求系统服务时间的长短.缺点:计算复杂,每调度一次,都要计算每个作业的响应比.4.优先数调度算法算法综合考虑的因素（作业等待时间、运行时间、缓急程度，系统资源使用等），给每个作业设置一个优先数，调度程序总是选择一个优先数最大（或者最小）的作业调入（系统）内存。优先数确定:用户规定系统规定优先数=(等待时间)-要求运行的时间-16×输出量。输出量以行计.算法优缺点:优点:保证优先照顾运行时间短的作业;但也不会使运行时间长的长作业等待太久,而得不到运行的机会.缺点:算法实现的困难,如何综合考虑各种因素之间的关系确定优先数。5.均衡调度算法依据作业对资源的要求分类,作业调度轮流地从不同类的作业中去挑选作业,尽可能地使得使用不同资源的作业同时执行.优点:减少作业等待同类资源的时间,加快作业的执行.缺点:算法实现复杂.2§3进程调度一,进程调度的功能和时机1.进程调度的功能①记录和保持系统中所有进程有关情况和状态特征。②决定分配策略。③实施处理机的分配和回收。2.进程调度时机调度时机有如下几种情况:正常终止系统服务请求：如：请求I/O等；异常终止：程序出错；时间片到可剥夺方式下，高优先级进程进入就绪队列3.进程调度方式⑴非剥夺方式让正在执行的进程继续执行，直到该进程完成或发生某事件而进入“完成”或“阻塞”状态时，才把处理机分配给“重要而紧迫”的进程。⑵剥夺方式当“重要而紧迫”的进程一到，便暂停正在执行的进程，立即把处理机分配给优先级更高的进程。三.调度用的进程状态变迁图例:有一个分时系统进程状态变迁图如下:运行等待高优先就绪低优先就绪超时间片其次选择500ms请求I/OI/O完成首先选择100ms12345要求分析:进程的可能状态，状态间的变迁的原因，调度策略和调度效果。问：(1)说明发生变迁3，2，4的原因是什么？(2)下列因果关系是否会发生？如果会发生，在什么情况下发生？a.2→1b.3→5c.4→2d.3→1(3)依据该系统的状态变迁图，叙述该系统的调度策略和调度效果。解：(1)发生变迁3的原因：一个运行的进程要请求系统服务。发生变迁2的原因：一个运行的进程用完了此轮的时间片，但任务还未完成。或者：系统采用剥夺式调度，一个更高优先级的进程进入就绪队列要求执行。发生变迁4的原因：I/o完成的消息到来，等待队列中的一个进程获得该I/o设备，则它由等待状态变为就绪状态。(2)a.2→1:是因果变迁关系。条件：当时间片到时，高优先就绪队列为空。b.3→5：是因果变迁关系。条件：高优先就绪队列为非空。c.4→2:不是因果变迁关系。d.3→1:是因果变迁关系。条件：高优先就绪队列为空,低优先就绪队列为非空。(3)调度策略:优先照顾I/O量大的进程,也适当的照顾了计算量大的进程.调度效果:平衡系统的负荷,将I/O繁忙的进程和计算繁忙的进程搭配使用不同的资源,使CPU和I/O设备并行性更合理一些.资源的利用率更高.四.进程调度算法先来先服务调度算法优先级调度算法时间片轮转调度算法分级的调度算法1.先来先服务调度算法按进程进入就绪队列的先后次序选择进程占用CPU.直至它运行完毕,或因等待某一事件让出CPU为止.优点:算法实现简单.缺点:不考虑进程的其它要求.2.优先级调度算法预先确定各进程的优先级,系统把CPU分给就绪队列中优先级别高的进程.关键是优先级的确定:静态优先级和动态优先级.(1)静态优先级的确定在进程创建时确定,确定后,在整个运行期间不能改变.确定情况:a.直接取作业的优先级.b.根据进程要求的资源和程序运行的估计时间综合确定.如:进程要求资源越多,运算的时间愈长,优先级就低.c.基于进程的类型确定系统进程的优先级高于用户进程的优先级.I/O繁忙的进程优先级高于CPU繁忙的进程优先级.保证CPU与I/O并行.在分时OS中,前台进程的优先级高于后台进程的优先级.优点:算法容易实现,系统开销小.缺点:死板.不能精确地调度进程,可能导致低优先级的进程长期等待.(2)动态优先级的确定进程优先级在运行时可以调整.确定:●进程优先级随占用CPU时间的延长而下降,随等待CPU时间的延长而上升.●当等待一外设的进程较多时,可提高使用该外设进程的优先级,使它尽快运行,以释放该外