电子科技大学《计算机操作系统》第2章-并发与进程-调度共73页

计算机操作系统电子科技大学计算机科学与工程学院李玉军主要内容调度scheduling死锁deadlock同步synchronization进程process2.5进程调度•如果有多个进程（线程）竞争CPU，那么就需要选择下一个要运行的进程（线程）。•在操作系统中完成这部分工作的程序称为调度程序（scheduler），该程序使用的算法称为调度算法（schedulingalgorithm）。•进程的调度算法对系统的整体性能和用户体验影响很大。2.5.1调度的目标、原则和方式•调度的生活实例2.5.1调度的目标、原则和方式目标•防止进程长期不能获得调度而饥饿•尽量提高处理机的利用率•提高系统吞吐量•尽量减少进程的响应时间原则•满足用户需求•满足系统需求2.5.1调度的目标、原则和方式•基本概念2.5.1调度的目标、原则和方式•响应时间从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。•响应时间的构成输入传送时间处理时间响应传送时间2.5.1调度的目标、原则和方式•周转时间从作业被提交给系统开始，到作业完成为止的这段时间间隔，也称为作业周转时间。•周转时间的构成驻外存等待调度时间驻内存等待调度时间执行时间阻塞时间需累计2.5.1调度的目标、原则和方式•平均周转时间：多个作业周转时间的平均值•带权周转时间：作业的周转时间与系统为它提供的服务时间之比•平均带权周转时间：多个作业带权周转时间的平均值niiTnT11niiWnT11siiiTTW2.5.1调度的目标、原则和方式•截至时间某任务必须开始执行的最迟时间，或必须完成的最迟时间。•系统吞吐量在单位时间内，系统所完成的作业数。2.5.1调度的目标、原则和方式面向用户的原则响应时间周转时间截止时间面向系统的原则吞吐量利用率公平性优先级2.5.1调度的目标、原则和方式•面向用户的原则–响应时间快尽可能使绝大多数用户的请求能在响应时间内完成，常用于评价分时系统的性能。–平均周转时间短常用于评价批处理系统的性能，涉及长程调度、中程调度和短程调度。–满足截至时间常用于评价实时系统的性能。2.5.1调度的目标、原则和方式•面向系统的原则–系统吞吐量大常用于评价批处理系统的性能。–处理器利用率高大、中型多用户系统较看重处理器的利用率单用户微机或某些实时系统不看重处理器的利用率–各类资源的平衡使用使系统中的各种资源都尽量处于忙碌状态。–公平性对所有进程公平，不偏袒任何进程。2.5.1调度的目标、原则和方式•面向系统的原则（续）–优先权：优先权高的进程应优先调度接纳调度处理机完成等待事件事件发生阻塞队列就绪队列0就绪队列1┇就绪队列n被剥夺2.5.1调度的目标、原则和方式•面向系统的原则（续）–优先权（续）几乎所有操作系统的调度算法都可考虑优先权原则。仅考虑优先权会导致进程饥饿，即某些低优先权进程长时间得不到调度。可以考虑动态优先权，将进程排队的等待时间等因素纳入优先权的计算。2.5.1调度的目标、原则和方式•调度类型非剥夺方式剥夺方式长程调度中程调度短程调度I/O调度2.5.1调度的目标、原则和方式•非剥夺（抢占）方式–执行进程只有在执行完毕，或因申请I/O阻塞自己时，才中断其执行，释放处理机。–不利于“即时性”要求较高的分时和实时系统，主要用于批处理系统。•剥夺（抢占）方式–在新进程到来时，或某个具有较高优先权的被阻塞进程插入就绪队列时，或在基于时间片调度的系统中，时间片用完而中断当前进程的执行，调度新的进程执行。–会产生较多的中断，主要用于实时性要求较高的实时系统及性能要求较高的批处理系统和分时系统。2.5.2调度的类型•长程调度（高级调度、作业调度）用于决定把外存上处于后备队列中的作业调入内存，并为它们创建进程、分配必要的资源，然后，再将新创建的进程排在就绪队列（就绪/挂起）上，等待短程（中程）调度。交互用户处理机完成就绪队列就绪/挂起队列┇后备队列长程调度2.5.2调度的类型•长程调度需要考虑两个问题–选择多少个作业进入内存，为之创建进程？取决于多道程序的度，即允许同时在内存中运行的进程数。–选择哪些作业取决于长程调度算法2.5.2调度的类型•短程调度（进程调度、低级调度）–决定就绪队列中的哪个进程应获得处理器–运行频率最高–现代操作系统几乎都具有短程调度功能•中程调度（中级调度）–对换功能的一部份，用以提高内存的利用率和系统的吞吐量。–内存紧张时，选择一个进程换出到外存（换出）。–内存充裕时，从外存选择一个挂起状态的进程调度到内存（换入）。–只有支持进程挂起的操作系统才具有中程调度功能。2.5.2调度的类型•同时具有三级调度的调度队列模型中程调度长程调度短程调度处理机完成就绪队列就绪/挂起队列阻塞/挂起队列阻塞队列时间片用完事件等待事件发生2.5.3进程调度算法•调度算法–根据系统的资源分配策略所规定的资源分配算法–对于不同的系统目标，通常采用不同的调度算法•常见的调度算法先来先服务短作业优先时间片轮转基于优先级剩余时间最短优先响应比高者优先反馈……2.5.3.1先来先服务（FCFS）•算法：First-Come-First-Served选择最先进入就绪队列的进程投入执行，即进程按照请求CPU的顺序使用CPU。•评价–属于非抢占调度方式–对长进程（作业）有利，不利于短进程（作业）–有利于CPU繁忙型的进程，而不利于I/O繁忙型的进程–不能直接用于分时系统–通常与其它调度算法混合使用–平均周转时间长2.5.3.1先来先服务（FCFS）•示例计算P1、P2、P3和P4的周转时间、平均周转时间、带权周转时间和平均带权周转时间。进程名产生时间服务时间优先级时间片P10221P2161P3214P43532.5.3.1先来先服务（FCFS）246810121416t进程名产生时间服务时间优先级时间片P10221P2161P3214P4353P1P2P3P4P1P2P3P42.5.3.2短进程（作业）优先（SPF/SJF）•算法:ShortestJob/ProcessFirst,SJF/SPF短进程或短作业优先调度，前提为执行时间预知。•评价–非抢占调度方式–该算法对长作业不利，可能导致长进程饥饿。–有利于短进程，减小了平均周转时间。–缺少剥夺机制，不适用于分时系统或事务处理环境。–由于作业（进程）的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会估计不准运行时间，致使该算法不一定能真正做到短作业优先调度。2.5.3.2短进程（作业）优先（SPF/SJF）246810121416t进程名产生时间服务时间优先级时间片P10221P2161P3214P4353P1P3P4P2P1P2P3P42.5.3.3时间片轮转调度算法（RR）•算法：RoundRobin每个进程被分配一个时间片，如果在时间片结束时该进程还在运行，则剥夺其CPU并分配给另一个进程，被剥夺CPU的进程则插入到就绪队列末尾，等待下次调度；如果该进程在时间片内阻塞或结束，则立即切换CPU。•典型应用系统示例——分时联机系统基于时间片轮转调度主机终端1终端2终端n…终端1服务进程终端2服务进程终端n服务进程…2.5.3.3时间片轮转调度算法（RR）•评价–属于抢占调度方式–对短的、计算型进程有利–对I/O型作业（进程）不利–常用于分时系统或事务处理系统–时间片的设置与系统性能、响应时间密切相关时间片设得太短会导致过多进程切换，降低CPU效率；反之，设得太长又可能引起对短的交互请求的响应时间变长。在分时系统中，时间片大小的确定应综合考虑最大用户数目、响应时间、系统效率等多种因素。246810121416t进程名产生时间服务时间优先级时间片P10221P2161P3214P4353P1P2P3P4P1P2P3P42.5.3.3时间片轮转调度算法（RR）246810121416t进程名产生时间服务时间优先级时间片P10221P2161P3214P4353P1P2P3P4P1P2P3P42.5.3.3时间片轮转调度算法（RR）2.5.3.4基于优先级的调度算法•算法每个进程被赋予一个优先级（权），允许优先级（权）最高的可运行进程先运行。•优先级的类型静态优先级动态优先级2.5.3.4基于优先级的调度算法•静态优先级(static)优先数在进程创建时分配，生存期内不变。•确定依据–进程类型（重要性、紧迫性）–进程对资源的需求–均衡系统资源使用–用户需求•评价–简单，开销小–适合批处理进程2.5.3.4基于优先级的调度算法•静态优先级的问题若一直存在高优先级的就绪进程，则低优先级的进程可能会饿死(无穷阻塞）。•解决方法进程的优先级随着时间或执行历史而变化——老化策略(aging)。•动态优先级在创建进程时所赋予的优先级可随进程的推进或随其等待时间的增加而改变，以便获得更好的调度性能。•调整时机–时钟中断–进程切换–进程终止2.5.3.4基于优先级的调度算法•基于优先级调度算法的分类2.5.3.4基于优先级的调度算法进程主动释放处理器处理器可被剥夺非抢占式优先级算法抢占式优先级调度算法246810121416t进程名产生时间服务时间优先级时间片P10221P2161P3214P4353P1P2P3P4P1P2P3P42.5.3.4基于优先级的调度算法1.非抢占式调度方式2.优先级数越小，优先级越高246810121416t进程名产生时间服务时间优先级时间片P10221P2161P3214P4353P1P2P3P4P1P2P3P42.5.3.4基于优先级的调度算法1.抢占式调度方式2.优先级数越小，优先级越高2.5.3.5剩余时间最短者优先算法•算法:ShortestRemainingTime,SRT–在SJF的基础上增加了剥夺机制–调度程序总是选择预期剩余时间最短的进程当一个新进程加入就绪队列时，它可能比当前运行的进程具有更短的剩余时间。只要新进程就绪，调度程序就可能抢占当前正在运行的进程。•优点–既不像FCFS那样偏爱长进程，也不像RR算法那样会产生额外的中断，从而减少了开销。–周转时间方面，SRT比SJF性能要好，短作业可以立即被选择执行。2.5.3.5剩余时间最短者优先算法•问题–需要估计预计的服务时间–存在进程饥饿现象–必须记录进程的已服务时间246810121416t进程名产生时间服务时间优先级时间片P10221P2161P3214P4353P1P2P3P4P1P2P3P42.5.3.5剩余时间最短者优先算法2.5.3.6响应比高者优先•算法:HighestResponseRatioNext当前进程执行完毕或需要阻塞时，选择响应比最高的进程投入执行。•评价–实质上是一种动态优先权调度算法–是FCFS和SJF的结合，既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务。–利用该算法时，每次调度之前，都须先做响应比的计算，会增加系统开销，且难以准确计算。要求服务时间响应时间要求服务时间要求服务时间等待时间pR246810121416t进程名产生时间服务时间优先级时间片P10221P2161P3214P4353P1P2P3P4P1P2P3P42.5.3.6响应比高者优先2.5.3.7反馈调度法•短进程优先、剩余时间最短者优先以及响应比高者优先调度算法采用了“奖励短进程”的思想。虽然性能较好，但均基于进程的预期执行时间——未来。•反馈调度法则采用了“惩罚长进程”的思想。根据进程执行历史，调度基于抢占原则（按时间片）并采用动态优先级机制，可以获得较好的性能。2.5.3.7反馈调度法•算法：MultilevelQueues，采用多级队列区别对待的方法“惩罚长进程”–多个独立的、优先级不同的就绪队列–各队列区别对待，即优先调度优先级高的队列–进程执行过程中可降级，即在整个生命周期内可能位于不同队列。•该算法有多个变种主要区别在于抢占机制不同2.5.3.7反馈调度法2.5.3.7反馈调度法•基于时间片轮转的反馈调度算法1.设置多个就绪队列，每个队列赋予不