进程调度与死锁

《操作系统原理》

第二章 进程调度与死锁主讲教师：李阅历2版权所有，转载请注明出处2内容提要进程调度模型与方法死锁内容提要3版权所有，转载请注明出处3进程调度的基本概念CPU资源管理——多道程序设计面临的挑战批处理系统：如何安排内存中多个作业的运行顺序？交互式系统：如何更好应对不同的交互式请求？实时系统：如何保证实时服务的高质量？进程调度——有效的管理CPU资源When：何时进行进程调度？How：遵循何种规则完成调度？抢占、非抢占式；What：调度过程中需要完成哪些工作？进程调度的发展方向：PC机和服务器进程调度4进程行为BurstsofCPUusagealternatewithperiodsofI/OwaitaCPU-boundprocessanI/Oboundprocess何时调度当创建一个新进程时；当一个进程退出时；当一个进程阻塞时；当发生一个I/O中断时；总之，在OS按照时钟中断来执行调度程序；版权所有，转载请注明出处5调度算法分类批处理非抢占交互式抢占实时可以非抢占7版权所有，转载请注明出处7进程调度的考量标准

响应时间(responsetime)进程自进入就绪队列开始至进程占用CPU之间的时间间隔周转时间(turnaroundtime)进程自进入就绪队列开始至进程结束之间的时间间隔

CPU吞吐量（throughout)单位时间内运行结束的进程个数举例进程调度8SchedulingAlgorithmGoalsP78

作业周转时间如果作业i提交给系统的时刻是ts，完成时刻是tf，该作业的周转时间ti为：ti=tf-ts

实际上，它是作业在系统里的等待时间与运行时间之和。平均作业周转时间为了提高系统的性能，要让若干个用户的平均作业周转时间和平均带权周转时间最小。平均作业周转时间T=(Σti)/n作业带权周转时间和平均

作业带权周转时间如果作业i的周转时间为ti，所需运行时间为tk，则称wi=ti/tk为该作业的带权周转时间。ti是等待时间与运行时间之和，故带权周转时间总大于1。平均作业带权周转时间W=(Σwi)/n1.先来先服务调度算法,first-comefirst-server,FCFS(非抢占）批处理系统中的调度

1.先来先服务调度算法先来先服务算法-特点按照作业进入系统的先后次序来挑选作业，先进入系统的作业优先被挑选。算法容易实现，效率不高，只顾及作业等候时间，没考虑作业要求服务时间的长短，不利于短作业而优待了长作业。

短作业(进程)优先调度算法(ShortestJobFirst,SJF)-非抢占，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法，是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法，则是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。2.短作业(进程)优先调度算法FCFS和SJF调度算法的性能(1)该算法对长作业不利，如作业C的周转时间由10增至16，其带权周转时间由2增至3.1。更严重的是，如果有一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度。(2)该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。(3)由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。SJ(P)F的缺点17版权所有，转载请注明出处17进程调度的三个层次进程调度高级调度：也称作业调度，决定哪些程序可以进入系统中级调度：也称内存调度，决定内存中程序的位置和状态低级调度：也称进程调度，决定CPU资源在就绪进程间的分配思考：内存中可以保留的进程个数？18版权所有，转载请注明出处18交互式系统中的调度

1.时间片轮转调度进程调度RoundRobinSchedulinglistofrunnableprocesseslistofrunnableprocessesafterBusesupitsquantum19版权所有，转载请注明出处191.时间片轮转调度

核心思想：每个进程运行固定的时间片，然后调入下一个进程，抢占；如何确定时间片的大小？实现机理：维护就绪进程队列，采用FIFO方式一次读取，特殊控制：时间片内发生阻塞或结束，则立即放弃时间片优缺点分析优点：绝对公平缺点：公平即合理吗？时间片如何设计才能保证效率？结论：P82进程调度20版权所有，转载请注明出处202.优先级调度

核心思想：为每个进程赋予不同级别的优先级，越高越优先实现机理：维护一个优先级队列，自顶向下依次读取特殊控制：静态优先级与动态优先级（时钟滴答、I/O密集型进程获得更高的优先级）概念优缺点分析优点：响应时间快，易于调整。最通用的方法。缺点：死规则，如何保证周转时间和吞吐量？饥饿现象进程调度2.优先级调度Aschedulingalgorithmwithfourpriorityclasses2优先级调度例子UNIX：preemptive+dynamicpriority（可抢占CPU动态优先数）。计算公式：p_pri=min{127,USER+p_cpu/16+p_nice}定义USER=100；p_cpu:运行进程每20ms加1（优先级降低），其它进程每1200ms减10（优先级提高）；p_nice:可以通过系统调用nice(…)修改的量：规定用户进程0~20之间（低），系统进程-20~+20之间（高）。3.多级队列为减少进程之间的切换时间，高优先级的分配较少的时间片，而低优先级的分配较大的时间片；例如：XDS940系统上：终端、I/O、短时间片、长时间片通过降低计算密集型（后台）进程的优先级，来照顾交互用户和短作业进程；4.最短进程优先最短响应时间进程优先如何找到运行最短的进程“老化”算法：通过测量当前值和先前的估计值进行加权平均来得到下一个估计值的技术；25版权所有，转载请注明出处255.彩票调度算法

核心思想：保证响应速度最快、依据进程对CPU资源的需求量调度实现机理：维护定量的彩票，不同进程获取数量不同，随机选择特殊控制：彩票交换：进程间可以动态自主调节调度顺序优缺点分析优点：响应速度最快、CPU利用率最高缺点：OS实现机制复杂、吞吐量和周转时间无法保证进程调度26版权所有，转载请注明出处26

实时调度针对于专用领域和专用应用目的必须具备前提条件才能进行实时调度特点：系统规模小、中断时间短、进程切换快、OS管理深度高如：多媒体OS中；实时系统包括监控系统、自动驾驶系统、安全控制系统等，这些系统中，迟到的响应即使正确，也和没有响应一样糟糕。进程调度周期性和非周期性事件实时系统响应的事件可划分为周期性事件和非周期性事件。例如，m个周期性事件，事件i的周期为Pi，每个事件需要Ci秒的CPU时间来处理，则只有满足以下条件：

C1/P1+C2/P2+…+Cm/Pm≤1

时，才可能处理所有的负载。满足该条件的实时系统称作任务可调度的（schedulable）。软实时系统一个软实时系统处理三个事件流，其周期分别为100ms，200ms和500ms，如果事件处理时间分别为50ms，30ms和100ms，则这个系统是可调度的，因为0.5+0.15+0.2≤1如果加入周期为1秒的第4个事件，则只要其处理时间不超过150ms，该系统仍将时可调度的。（忽略进程的切换时间）29版权所有，转载请注明出处29反思：如何实现进程调度？

调度机制,schedulingmechanism不同调度算法适用于不同环境和不同目的调度算法一旦固定，则其最优、最坏情况均无法避免如能根据具体情况动态调整，则效果更佳调度策略,schedulingpolicy为用户提供改变调整调度机制的渠道实现方法——提供系统调用，能够改变调度机制结论,softwareengineer尽量使调度策略（由用户进程决定）和调度机制（由OS或内核决定）分离；进程调度30版权所有，转载请注明出处30小结（2）

进程调度的基本概念调度原则各种评价指标的计算方法经典的进程调度机制不同调度算法的应用环境、针对目标各不相同从简单到复杂，体现了OS历史发展潮流调度策略的思考OS设计的关键——调度策略调度策略的实现方法——对调度机制的管理进程调度31内容提要进程死锁资源轨迹图银行家算法内容提要32进程死锁原理死锁举例进程A：获得CD-ROM使用权，申请打印机进程B：获得打印机使用权，申请CD-ROM死锁：此时进程A、B均被阻塞，无法运行进程死锁进程A进程B打印机CD-ROM33如何理解死锁概念基础资源、可剥夺资源与不可剥夺资源（打印机、磁盘）可剥夺资源会造成死锁吗？（举例）对比理解死锁与互斥有哪些异同？-使用信号量避免死锁，P93,无死锁和有死锁的编码；操作系统为什么要解决死锁问题？在所有的操作系统中都会发生死锁问题吗？进程死锁34死锁的定义进程死锁若一个进程集合中的每一个进程都在等待只能由本集合中其他进程引发的事件。则这种情况为死锁。假设每个进程只有一个线程，并且被阻塞的进程不能被中断所唤醒，即自动释放自己所占用的资源；35死锁发生的条件进程死锁Coffman1971互斥条件：每一个资源或者空闲，或者被分配给一个进程保持和等待条件：已占有某些资源的进程需申请新的资源后方可继续运行非剥夺条件：被进程占用的资源不可剥夺，只能被进程本身显式释放循环等待条件：系统必然存在一条由两个或两个以上进程组成的循环链，该循环链中每个进程都在等待临近的进程释放资源-P93；36死锁的形式化描述基于有向图描述死锁条件–死锁建模Holt，1972进程死锁资源分配图HowdeadlockoccursABC死锁的产生1Howdeadlockcanbeavoided(o)(p)(q)死锁的产生239死锁处理策略不理会死锁原因：为什么耗费大量的时间在小概率事件上呢？死锁检测与恢复目标：检测死锁发生，通过撤销进程恢复系统运行死锁预防目标：对进程加以适当限制以防止死锁情况发生,仔细控制对资源的分配；死锁避免目标：不对进程加以限制，由操作系统完成死锁预防，进程死锁40鸵鸟算法OstrichAlgorithm核心思想：忽略死锁问题原因：死锁问题的发生是小概率事件OS中的每一种表都代表了一种有限的资源，都可能发生死锁举例：对系统运行的最大程序数目的限制（PCB的表项）；UNIXandWindowstakesthisapproachItisatradeoffbetweenconveniencecorrectness进程死锁41死锁检测与恢复核心思想：将系统从死锁中解脱方法动机：与其耗费大量时间来避免死锁的发生，不如采取有效的手段解决死锁死锁检测的解决方法每个类型的资源只有一个每个类型的资源有多个何时检测？每当有资源申请时就去检测；每隔K分钟，检测CPU的使用率，如果降低到一定的阀值以下，就进行死锁检测；进程死锁42死锁检测算法简介每个类型的资源只有一个，基于图和集合的算法检测是否有闭环建立资源分配图结构，记录了所有的进程、资源和有向边从任一结点开始进行深度优先遍历，如找到闭环则结束如某条遍历路径已经到达终点，则回退至上一结点，继续重复此过程–P97进程死锁DetectionwithOneResourceofEachType(1)NotetheresourceownershipandrequestsAcyclecanbefoundwithinthegraph,denotingdeadlock44死锁检测算法简介每个类型的资源有多个，基于矩阵和向量比较方法检测是否存在死锁建立现有资源标量、可用资源标量、当前分配矩阵、请求矩阵等数据结构对当前分配矩阵，寻找可满足资源需求的进程，对其标记，并释放其所占用的资源；如果有进程没有被标记，说明该进程是死锁进程进程死锁DetectionwithOneResourceofEachType(2)Datastructuresneededbydeadlockdetectionalgorithm，注意C矩阵、R矩阵和E、A向量之间的关系，公式，P98DetectionwithOneResourceofEachType(3)Anexampleforthedeadlockdetectionalgorithm47死锁检测与恢复死锁恢复的解决方法-重新分配资源进行资源抢占：将某个进程的资源强制性分配给其他进程，取决于资源是否可以强行剥夺！利用回退恢复：设定检查点，发现存在死锁情况后则回退杀死进程恢复：直接杀掉占用资源的进程，使得其他进程得以运行；最关键的问题是选择杀死哪一个进程，以及如何处理进程的原工作所带来的后果；进程死锁48死锁预防核心思想：对进程加以限制防止死锁发生设计思路：针对四个死锁条件，逐一避免具体解决方法——但都有些不实用互斥条件：使用Spooling技术来管理设备，保持和等待条件：资源可用性决定资源分配，在开始就请求分配所有资源；不可剥夺条件：由系统直接剥夺此类资源循环链条件：资源编号，按预定规则申请，P104；进程死锁DeadlockPrevention

AttackingtheMutualExclusionConditionSomedevices(suchasprinter)canbespooledonlytheprinterdaemonusesprinterresourcethusdeadlockforprintereliminatedNotalldevicescanbespooledPrinciple:avoidassigningresourcewhennotabsolutelynecessaryasfewprocessesaspossibleactuallyclaimtheresourceAttackingtheHoldandWaitConditionRequireprocessestorequestresourcesbeforestartingaprocessneverhastowaitforwhatitneedsProblemsmaynotknowrequiredresourcesatstartofrunalsotiesupresourcesotherprocessescouldbeusingVariation:processmustgiveupallresourcesthenrequestallimmediatelyneededAttackingtheNoPreemptionConditionThisisnotaviableoptionConsideraprocessgiventheprinterhalfwaythroughitsjobnowforciblytakeawayprinter!!??

Normallyorderedresources，Aresourcegraph；b图只有在A申请j和B同时申请i时才死锁；可以规定各个进程，都必须按升序来申请各个所需资源，或者仅要求进程只能申请比当前所占有的资源号高的资源，从而避免死锁，p104；(a)(b)AttackingtheCycleWaitingConditionSummaryofapproaches

todeadlockpreventionOtherIssues

Two-PhaseLockingPhaseOneprocesstriestolockallrecordsitneeds,oneatatimeifneededrecordfoundlocked,startover(norealworkdoneinphaseone)Ifphaseonesucceeds,itstartssecondphase,performingupdatesreleasinglocksNotesimilaritytorequestingallresourcesatonceAlgorithmworkswhereprogrammercanarrangeprogramcanbestopped,restartedNonresourceDeadlocksPossiblefortwoprocessestodeadlockeachiswaitingfortheothertodosometaskCanhappenwithsemaphoreseachprocessrequiredtodoadown()ontwosemaphores(mutexandanother)ifdoneinwrongorder,deadlockresultsForexample,Producer-ConsumerProblemStarvationAlgorithmtoallocatearesourcemaybetogivetoshortestjobfirstForexample，SJF：WorksgreatformultipleshortjobsinasystemMaycauselongjobtobepostponedindefinitely,eventhoughnotblockedSolution:First-come,first-servepolicy57死锁避免核心思想：不对进程进行限制，预防死锁设计思路：操作系统分析资源分配情况防止死锁核心思想安全状态：存在某种资源调度顺序，保证所有进程正常运行完成，则称该状态为安全状态不安全状态：不存在可满足所有进程正常运行的资源调度顺序，则称该状态为不安全状态具体实现方法资源轨迹图：针对两个进程的死锁避免银行家算法：单种资源和多种资源的算法进程死锁58使用资源轨迹图方法避免死锁针对两个进程、两种资源的死锁避免方法条件：两个进程A和B，两种资源“打印机”和“绘图仪”根据指令运行过程来判断是否发生死锁进程A：P点启动，I1~I3使用打印机，I2~I4使用绘图仪；进程B：Q点启动，I5~I7使用绘图仪，I6~I8使用打印机；进程死锁59使用资源轨迹图方法避免死锁进程死锁A、B不能同时进入不安全区域，如在t点OS只能挂起B，执行A到I4，P10060单种资源银行家算法核心思想记录每个进程的已有资源（已贷金额）和所需最大资源数（贷款额度）对每一个资源请求（再次申请贷款金额）进行检查，判断是否会造成不安全（信用危机）如果不安全则不分配，从而避免死锁（破产）方法分析对任何资源