第三章处理机调度与死锁.

东北农业大学王艳操作系统原理Page2用户用户用户作业1作业2作业3作业4外存后备队列作业调度程序内存CPU进程调度Page3第三章处理机调度与死锁3.1处理机调度的层次和调度算法的目标3.1.1处理机调度的层次1高级调度长程调度、作业调度，调度对象为作业。2低级调度进程调度、短程调度，调度对象为进程。3中级调度内存调度，为提高内存利用率和系统吞吐量。Page4第三章处理机调度与死锁CPU就绪队列阻塞队列后备作业队列高级调度低级调度时间片用完进程完成等待事件事件解除Page5第三章处理机调度与死锁3.1处理机调度的层次和调度算法的目标3.1.2处理机算法的目标1处理机算法的共同目标（1）资源利用率（2）公平性（3）平衡性（4）策略强制执行性Page6第三章处理机调度与死锁3.1处理机调度的层次和调度算法的目标3.1.2处理机算法的目标2批处理系统的目标（1）平均周转时间短作业提交开始到作业完成为止的时间间隔系统：作业的平均周转时间尽可能少用户：自己作业周转时间尽量少指标：平均周转时间指标：带权周转时间Page7第三章处理机调度与死锁①作业平均周转时间（T）②带权平均周转时间（W）T＝（）×=niTi1n1n为作业数目，第i个作业的周转时间Ti＝Ei–SiEi：作业完成时间Si：作业提交时间W＝（）×n1=niriTi1ri为某作业i的实际执行时间3.1处理机调度的层次和调度算法的目标3.1.2处理机算法的目标Page8第三章处理机调度与死锁3.1处理机调度的层次和调度算法的目标3.1.2处理机算法的目标2批处理系统的目标（2）系统吞吐量（3）处理机利用率高3分时系统的目标（1）响应时间快（2）均衡性4实时系统的目标（1）截止时间的保证（2）可预测性Page9第三章处理机调度与死锁3.2作业与作业调度3.2.1批处理系统中的作业1作业和作业步（1）作业（Job）：程序+数据+作业说明符（2）作业步：作业执行过程中的加工步骤2作业控制块（JCB）(1)作业存在的标识(2)保存系统对作业进行管理和调度的所有信息Page10第三章处理机调度与死锁3.2作业与作业调度3.2.1批处理系统中的作业3作业运行的三个阶段和三种状态后备状态→运行状态→完成状态（1）三个阶段收容阶段→运行阶段→完成阶段（2）三种状态Page11第三章处理机调度与死锁3.2作业与作业调度3.2.2作业调度的主要任务1决定接纳多少个作业多道程序度2接纳哪些作业调度算法Page12第三章处理机调度与死锁3.2作业与作业调度3.2.3先来先服务和短作业优先算法1先来先服务算法（1）FCFS：FirstComeFirstServe（2）适用于作业、进程调度（3）选择最先进入的作业/进程（4）例子：Page13第三章处理机调度与死锁作业到达t服务t开始t结束tTWA01B1100C21D31000111011011021022021110011001001991.99平均周转时间：t=100带权平均周转时间w=25.9975优点：实现简单（优待大作业）缺点：对短作业不利3.2作业与作业调度3.2.3先来先服务和短作业优先算法Page14第三章处理机调度与死锁2短作业优先算法（1）SJ（P）F：ShortestJob（Process）First（2）适用于作业、进程调度（3）选择短的作业/进程（4）例子：3.2作业与作业调度3.2.3先来先服务和短作业优先算法Page15第三章处理机调度与死锁进程ABCDE平均到达t01234服务t43524先来先服务算法开始t完成tTW短作业优先算法开始t完成tTW作业情况算法0447712121414184162102115.5143.592.804691318469134182.67163.231.592.2582.143.2作业与作业调度3.2.3先来先服务和短作业优先算法Page16第三章处理机调度与死锁1优先级调度算法（PSA）3.2作业与作业调度3.2.4优先级调度算法和高响应比优先调度算法先来先服务算法→等待时间为优先级短作业优先算法→作业长短为优先级优先级调度算法→作业的紧迫程度Page17第三章处理机调度与死锁2高响应比优先权调度算法（HRRN）（1）HRRN是介于FCFS和SJP（F）之间的一种折中算法（2）优先权3.2作业与作业调度3.2.4优先级调度算法和高响应比优先调度算法优先权=（等待时间+要求服务时间）/要求服务时间动态优先权：随等待时间延长而增加响应比R=（等待时间+要求服务时间）/要求服务时间=响应时间/要求服务时间Page18第三章处理机调度与死锁2高响应比优先权调度算法（HRRN）（3）优点＊等待时间相同，则处理时间短，优先级R高。＊作业处理时间相同，则等待时间决定优先级R。＊对于长作业，等待足够时间，R增加，可获得处理机。——SJF——FCFS（4）缺点＊增加系统开销3.2作业与作业调度3.2.4优先级调度算法和高响应比优先调度算法Page19第三章处理机调度与死锁2高响应比优先权调度算法（HRRN）（5）例子到达t服务t开始t完成tTWA04B13C25D32E44平均04Rb=1，Rc=0.4Rd=0.5，Re=047Rc=1，Rd=2，Re=0.7579Rc=1.4，Re=1.2591414184162122.463143.58.42.383.2作业与作业调度3.2.4优先级调度算法和高响应比优先调度算法Page20（1）FCFS（2）SJ（P）F（3）HRNPage21名称ABCDE平均到达01234CPU36452FCFS开始完成TWSJF开始完成TWHRN开始完成TW0339913131818203181115161.332.753810.63.220314203791479311951153.171.252.22.58.62.02033911151520911318131771.333.253.43.59.62.496Page22第三章处理机调度与死锁3.3进程调度1进程调度的任务(1)保存处理机现场信息(2)按某种算法选取进程(3)把处理机分配给进程2进程调度机制(1)排队器(2)分派器(3)上下文切换机制3.3.1进程调度的任务、机制和方式Page23第三章处理机调度与死锁3.3进程调度3调度方式(1)非抢占式＊引发进程调度的事件——执行完毕、进程阻塞、执行原语＊特点——实现简单、开销小、不能立即执行（2）抢占式＊基本原则—优先权原则、短作业（进程）优先、时间片原则＊特点—开销大、公平、响应及时Page24第三章处理机调度与死锁3.3进程调度3.3.2轮转调度算法（RR）1轮转法的基本原理按FCFS将就绪进程排成一个就绪队列，进程按时间片轮流使用CPU。3时间片大小的确定太长——不能及时响应太短——频繁切换，降低CPU效率2进程切换时机（1）时间片未完，进程已完成（2）时间片完，进程未完成Page25第三章处理机调度与死锁ABCDEABCDEABCEACE(a)q＝1(b)q＝41234567891011121314151617tPage26第三章处理机调度与死锁进程名ABCDE平均到达时间01234作业情况时间片服务时间43424完成时间151216917周转时间15111461311.8RRq=1带权周转时间3.753.673.533.333.46完成时间47111317周转时间46910138.4RRq=4带权周转时间122.2553.332.5Page27第三章处理机调度与死锁3.3进程调度3.3.3优先级调度算法1优先级调度算法类型（1）非抢占式优先权调度算法＊批处理系统、实时性要求不高的实时系统（2）抢占式优先权算法＊严格的实时系统，高性能的分时、批处理系统Page28第三章处理机调度与死锁3.3进程调度3.3.3优先级调度算法2优先级的类型（1）静态优先级进程创建时确定，在进程整个运行期间保持不变。①进程类型②进程对资源的需求③用户要求简单易行，系统开销小，但不够精确，优先级低的进程长期不被调用Page29第三章处理机调度与死锁3.3进程调度3.3.3优先级调度算法2优先级的类型（2）动态优先级进程创建之初确定，随进程推进或等待时间的增加而改变①随等待时间的增长，优先级相应提高②抢占式调度方式中，规定当前进程的优先级随运行时间的推移而下降Page30第三章处理机调度与死锁3.3进程调度3.3.4多队列调度算法就绪队列→多个不同队列→不同优先级不同队列→不同调度算法Page31第三章处理机调度与死锁3.3进程调度3.3.5多级反馈队列调度算法1调度机制（1）建立多个就绪队列，优先级递减就绪队列1就绪队列2就绪队列3就绪队列nS1S2S3至CPU至CPU至CPU至CPU(时间片：S1＜S2＜S3)Page32第三章处理机调度与死锁3.3进程调度3.3.5多级反馈队列调度算法1调度机制（2）每个队列都采用FCFS算法，第n个队列采用RR方式调度（3）按队列优先级调度。首先调度最高优先级队列中的进程运行，仅当第一队列空闲时才调度第二队列中的进程运行。Page33第三章处理机调度与死锁3.3进程调度3.3.5多级反馈队列调度算法2调度算法性能若规定第一个队列的时间片略大于多数人机交互所需处理时间时，便能较好满足各种类型用户的需要。＊终端型用户＊短批处理作业用户＊长批处理作业用户Page34第三章处理机调度与死锁3.5产生死锁的原因和必要条件1典型死锁的例子P1：申请R1申请R2…P2：申请R2申请R1…P1拥有R1申请R2，P2拥有R2申请R1Page35第三章处理机调度与死锁3.5产生死锁的原因和必要条件3.5.1资源问题1可重用性资源和消耗性资源(1)可重用性资源：供用户使用多次的资源①一个可重用性资源单元只能分配给一个进程使用②请求资源→使用资源→释放资源③系统中每一类可重用性资源中的单元数目是相对固定的，进程在运行期间既不能创建也不能删除④计算机系统中大多数资源都属于可重用性资源Page36第三章处理机调度与死锁3.5产生死锁的原因和必要条件3.5.1资源问题1可重用性资源和消耗性资源(2)可消耗性资源：临时资源③可以请求若干个可消耗性资源单元②进程运行过程中，可以不断的创造可消耗性资源的单元①每一类可消耗性资源中的单元数目是可以不断变化的④生产者创建，消费者进程消耗Page37第三章处理机调度与死锁3.5产生死锁的原因和必要条件3.5.1资源问题2可抢占性资源和不可抢占性资源(1)可抢占性资源磁带机、打印机等（2）不可抢占性资源CPU、主存等，此类资源不会引起死锁Page38第三章处理机调度与死锁3.5产生死锁的原因和必要条件3.5.２计算机系统中的死锁１竞争非剥夺性资源R1：磁带机R2：打印机R1R2P1P2Page39第三章处理机调度与死锁3.5产生死锁的原因和必要条件3.5.２计算机系统中的死锁２竞争可消耗性资源P1：…Release(S1)；Reqaest(S3)；…P2：…Release(S2)；Request(S1)；…P3：…Release(S3)；Request(S2)；…P1：…Request(S3)；Release(S1)；…P2：…Request(S1)；Release(S2)；…P3：…Request(S2)；Release(S3)；…S2P1S3P3S1P2Page40第三章处理机调度与死锁3.5产生死锁的原因和必要条件3.5.２计算机系统中的死锁３进程间推进顺序非法（１）合法P1：Request(R1)；Request(R2)；P1：Releast(R1)；Release(R2)；P2：Request(R2)；Request(R1)；P2：Release(R2)；Release(R1)；Page41第三章处理机调度与死锁3.5产生死锁的原因和必要条件3.5.２计算机系统中的死锁（2）进程间推进顺序非法P2Rel(R1)P2Rel(R2)P2Req(R1)