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

第三章处理机调度与死锁1第三章处理机调度与死锁第三章处理机调度与死锁2第三章处理机调度与死锁3.1处理机调度的基本概念3.2调度队列模型和调度准则3.3调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除第三章处理机调度与死锁33.1处理机调度的层次3.1.1高级调度概念：功能：根据某种算法，把外存上处于后备队列中的那些作业调入内存。调度对象：作业一般用于批处理系统，分/实时系统一般直接入内存，无此环节。作业：在一次应用业务处理过程中，从输入开始到输出结束，用户要求计算机所做的有关该业务处理的全部工作。作业是一个比程序更广的概念，它由程序、数据和作业说明书组成，系统通过作业说明书控制文件形式的程序和数据，使之执行和操作，在批处理中，作业是抢占内存的基本单位。一个作业可以由多个进程组成。第三章处理机调度与死锁43.1处理机调度的基本概念3.1.1高级、中级和低级调度1.高级调度（作业调度、长程调度）将外存作业调入内存，创建PCB等，插入就绪队列。一般用于批处理系统，分/实时系统一般直接入内存，无此环节。调度特性接纳作业数（内存驻留数）太多―――周转时间T长太少―――系统效率低接纳策略：即采用何种调度算法：FCFS、短作业优先等第三章处理机调度与死锁53.1处理机调度的基本概念3.1.2低级调度概念：功能：决定就绪队列中哪个进程获得处理机,然后由分派程序（Dispatcher）分派处理机。调度对象：进程低级调度的主要功能：保存处理机的现场信息、按某种算法选取进程、把处理机分配给进程进程调度的三个基本机制排队器分派器（分派程序）上下文切换机制第三章处理机调度与死锁63.1处理机调度的层次3.1.2低级调度进程调度方式1)非抢占方式：运行至进程完成，自愿释放处理机，或发生某事件而被阻塞时，才再把处理机分配给其他进程。进程调度原因：进程运行完毕、进程阻塞、执行了某种原语操作简单，系统开销小。实时性差2)抢占方式：允许调度程序根据某种原则去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。时间片原则优先权原则短作业优先原则。第三章处理机调度与死锁73.1处理机调度的层次3.1.3中级调度（中程）为提高系统吞吐量和内存利用率而引入的。应使那些暂时不能运行的进程不再占用宝贵的内存资源，面将它们调至外存上去等待。内存------外存对换功能（换出时，进程为挂起或就绪驻外存状态）运行频率：低级调度中级调度高级调度。第三章处理机调度与死锁83.1处理机调度的层次处理机的三级调度第三章处理机调度与死锁9处理器调度与进程状态转换高级调度中级调度低级调度运行态就绪态终止态新建态挂起就绪态中级调度挂起等待态等待态高级调度高级调度中级调度第三章处理机调度与死锁10第三章处理机调度与死锁3.1处理机调度的基本概念3.2调度队列模型和调度准则3.3调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除第三章处理机调度与死锁113.2调度队列模型和调度算法3.2.1调度队列模型1.仅有进程调度的队列模型（分时系统）交互用户就绪队列CPU阻塞队列时间片完进程调度进程完成等待事件事件出现第三章处理机调度与死锁123.2.1调度队列模型2.具有高级和低级模型（批处理系统）就绪队列CPU阻塞队列时间片完进程调度进程完成等待事件1事件1出现后备队列阻塞队列等待事件2事件2出现作业调度第三章处理机调度与死锁133.2.1调度的队列模型交互式用户后备作业队列中级调度处理器低级调度高级调度完成超时挂起就绪队列挂起等待队列等待队列就绪队列等待事件事件出现中级调度3.同时具有三级调度的调度队列模型第三章处理机调度与死锁143.2.2选择调度方式和算法的若干准则一、面向用户的准则1．周转时间短（常用于评价批处理系统）概念：所谓周转时间，是指从作业提交给系统开始，到作业完成为止的这段时间间隔（称为作业周转时间）.包括四部分时间：（1）作业在外存后备队列上等待调度时间（2）进程在内存就绪队列上等待调度时间（3）进程在CPU上执行时间（4）进程等待I/O操作完成的时间注：（后三项在一个作业的整个处理过程中发生多次）第三章处理机调度与死锁15一、面向用户的准则平均周转时间平均带权周转时间3.2.2选择调度方式和算法的若干准则][11niiTnT][11nisiTTnW作业的周转时间Ti与系统为它提供服务的时间TS之比可见带权周转时间W越小越好,Ts为实际服务时间。第三章处理机调度与死锁16一、面向用户的准则2．响应时间快：（常用于评价分时系统）概念：所谓响应时间，是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。包括三部分时间（1）输入传送时间（2）处理时间（3）响应传送时间3．截止时间的保证（常用于评价实时系统）概念：是指某任务必须开始执行的最迟时间或必须完成的最迟时间。4．优先权准则：（即需要抢占调度）指让某些紧急的作业能得到及时处理。3.2.2选择调度方式和算法的若干准则第三章处理机调度与死锁17二、面向系统的准则1．系统吞吐量高（特别用于批处理）：吞吐量是指在单位时间内系统所完成的作业数2．处理机利用率好（因CPU贵，特别于用大中型多用户系统）3．各类资源的平衡利用3.2.2选择调度方式和算法的若干准则第三章处理机调度与死锁18第三章处理机调度与死锁3.1处理机调度的基本概念3.2调度队列模型和调度准则3.3调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除第三章处理机调度与死锁193.3调度算法调度算法：根据系统的资源分配策略所规定的资源分配算法。对于不同的系统和系统目标，通常采用不周的调度算法。在OS中调度的实质是一种资源分配。第三章处理机调度与死锁203.3.1先来先服务和短作业(进程)优先调度算法1.先来先服务（FCFS）调度算法特点：可用于作业调度、也可用于进程调度利于长作业（进程）、不利于短作业（进程）利于CPU繁忙型作业，不利于I/O繁忙型的作业(进程)第三章处理机调度与死锁21例进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A01B1100C21D310001110110110011011021001001022021991.99第三章处理机调度与死锁22FCFS实例1.先来先服务调度算法平均周转时间：11111001001991004niiTTn平均带权周转时间111111001.99425.9975niiSiTTnT第三章处理机调度与死锁232.短作业(进程)优先调度算法短作业优先(SJF)调度算法：从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。短进程优先(SPF)调度算法：从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，处理机调度与死锁图3.4FCFS和SJF比较作业情况调度算法进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间周转时间带权周转时间SJF完成时间周转时间带权周转时间4417621210214115.518143.592.8441631.5982.671392.2518163.182.1第三章处理机调度与死锁25平均周转时间：iiiTnT11niSiiTTnW11带权周转时间：W=T/TS平均带权周转时间:第三章处理机调度与死锁26优点：有效的降低作业的平均等待时间，提高了系统的吞吐量。缺点：对长作业不利完全未考虑作业的紧迫程度作业的运行时间不能准确获得2.短作业(进程)优先调度算法第三章处理机调度与死锁273.3.2高优先权优先调度算法1.优先权调度算法的类型1)非抢占式优先权算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成。或因发生某事件使该进程放弃处理机时才再分配。第三章处理机调度与死锁28这种抢占式的优先权调度算法，能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。1.优先权调度算法的类型2)抢占式优先权调度算法在执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程的执行，重新将处理机分配给新到的优先权最高的进程。第三章处理机调度与死锁292.优先权的类型静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。1)静态优先权(1)进程类型。(2)进程对资源的需求。(3)用户要求。优点：简单易行、系统开销小。缺点：不够精确，很可能出现优先权低的作业（进程）长期不被调度的情况。第三章处理机调度与死锁30动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。2)动态优先权2.优先权的类型第三章处理机调度与死锁313.高响应比优先调度算法要求服务时间要求服务时间等待时间优先权优先权的变化规律可描述为：由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为：要求服务时间响应时间要求服务时间要求服务时间等待时间优先权第三章处理机调度与死锁32(1)等待时间相同，则要求服务的时间愈短，其优先权愈高——有利于短作业(2)当要求服务的时间相同时，则等待时间愈长，其优先权愈高——先来先服务(3)长作业只要等待时间足够长，其优先级便可升到很高，从而也可获得处理机(4)响应比的计算增加了系统开销3.高响应比优先调度算法要求服务时间要求服务时间等待时间优先权第三章处理机调度与死锁33例：单道批处理系统中，一组作业的提交时刻和运行时间如表所示。采用高响应比优先调度算法表1作业提交时刻和运行时间作业提交时刻运行时间18.01.028.50.539.00.249.10.1作业1到达时，没有其它作业到达，故作业1执行表2作业执行次序提交时刻运行时间等待时间开始时刻完成时刻周转时间带权周转时间18.01.008.09.01.01.039.00.20.69.69.80.84.0作业1执行完成时刻为9.0，作业2、3均已到达，此时作业2、3的响应比分别是：作业2=1+0.5/0.5=2；作业3=1+0/0.2=1；即选择2运行28.50.50.59.09.51.02.0作业2执行完成时刻为9.5，作业3、4均已到达，其响应比分别是：作业3=1+0.5/0.2=3.5作业4=1+0.4/0.1=5，即选择作业4运行。49.10.10.49.59.60.55.0最后只剩下作业3，执行第三章处理机调度与死锁343.3.3基于时间片的轮转调度算法1.时间片轮转法确定时间片大小的考虑因素：1、系统对响应时间的要求2、就绪队列中进程的数目3、系统的处理能力基本原理：所有就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片.当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的未尾……时间片大小的确定一般从几ms到几百ms.太大：退化为FCFS；太小：系统开销过大系统对响应时间的要求:T=nq用户数时间片第三章处理机调度与死锁35作业情况时间片进程名ABCDE平均到达时间01234服务时间43524RRq=1完成时间1210181117周转时间1291681311.6带权周转时间333.243.253.29RRq=4完成时间47121418周转时间461011149带权周转时间1225.53.52.8图3.6q=1和q=4时进程的周转