计算机操作系统课件(第四版)第三章

第三章处理机调度与死锁第一节处理机调度的层次第二节调度队列模型和调度准则第三节调度算法第四节实时调度第五节产生死锁的原因和必要条件第六节预防死锁的方法第七节死锁的检测和解除3.1处理机调度的层次高级调度低级调度中级调度3.1.1、高级调度高级调度（作业调度/长程调度）决定把外存上处于后备队列中的哪些作业调入内存。调度对象：作业•1、作业和作业步作业：程序+数据+作业说明书作业步：作业运行期间的每个加工步骤例如：编译连结装配运行2、作业控制块（JCB）JCB：保存了系统对作业进行管理和调度所需的全部信息。作业在系统中存在的标志。JCB包含的内容有：作业标识、用户名称、用户账号、作业类型、作业状态、调度信息、资源需求、时间信息、资源使用情况等。JCB的创建和回收3、高级调度（作业/长程/接纳调度）概念：决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，准备执行。多用于批处理系统每次调度时要考虑：(1)接纳多少作业：取决于多道程序度(2)接纳哪些作业：取决于调度算法作业调度运行频率低，几分钟一次系统规模运行速度低级调度（进程/短程调度）决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作是最基本的调度，在三种类型的OS中都必须配置3.1.2、低级调度1、低级调度的功能保存处理机的现场信息按照某种算法选取进程把处理机分配给进程2、进程调度中的三个基本机制排队器分派器（分派程序）上下文切换机制3、进程调度方式非抢占方式抢占方式1）非抢占方式：一旦进程获得处理机，则一直执行，直到该进程完成或被阻塞此方式下，可能引起进程调度的因素：（1）正在执行的进程执行完毕，或因发生某事件不能再继续执行（2）执行中的进程因提出I/O请求而暂停执行（3）在进程通信或同步过程中执行了某原语，P操作等优点：简单、系统开销小，适合大多数批处理系统缺点：无法满足紧急任务的需要，不适合实时系统2）抢占方式：允许调度程序根据某原则，暂停正在执行的进程，将处理机重新分配抢占原则：优先权原则就绪的高优先权进程有权抢占低优先权进程的CPU短作业优先原则就绪的短作业(进程)有权抢占长作业(进程)的CPU时间片原则一个时间片用完后，系统重新进行进程调度中级调度（中程调度）目的：提高内存利用率和系统吞吐量按一定的算法将外存上已具备运行条件的挂起进程换入内存，挂到就绪队列上，准备执行；而将内存中处于阻塞状态的某些进程换出至外存。3.1.3、中级调度调度队列模型选择调度方式和调度算法的若干准则3.2、调度队列模型3.2.1、调度队列模型仅具有进程调度的调度队列模型就绪队列阻塞队列CPU时间片完交互用户进程调度进程完成等待事件事件发生……具有高、低两级调度的调度队列模型就绪队列阻塞队列CPU时间片完作业调度进程调度进程完成等待事件1阻塞队列阻塞队列等待事件2等待事件n事件1发生事件2发生事件n发生后备队列具有高、低、中三级调度的调度队列模型就绪队列绪就、挂起队列CPU时间片完作业调度进程调度进程完成事件出现阻塞队列挂起等待事件中级调度事件发生后备队列塞阻、挂起队列挂起3.2.2、选择调度方式和算法的选择准则1、面向用户的准则（1）周转时间短——评价批处理系统周转时间：是指从作业被提交系统开始，到作业完成为止的这段时间间隔。包括四部分时间：1）等待作业调度时间2）等待进程调度时间3）执行时间4）进程等待I/O操作完成时间平均周转时间：niTinT11带权周转时间：TsTW周转时间服务时间niTsTinW11平均带权周转时间：（2）响应时间快——评价分时系统响应时间：从用户通过键盘提交一个请求开始直至系统首次产生响应为止。包括三部分时间：1）从键盘输入的请求信息传送到处理机的时间2）处理时间3）响应信息回送终端的时间（3）截止时间保证——评价实时系统截止时间：任务必须开始执行的最迟时间，或必须完成的最迟时间。（4）优先权准则——三种系统中皆适用2、面向系统的准则系统吞吐量高——评价批处理系统处理机利用率好——针对大中型系统各类资源的平衡利用——对大中型系统3.3调度算法先来先服务和短作业（进程）优先调度算法高优先权先调度算法基于时间片的轮转调度算法3.2.1、先来先服务和短作业（进程）优先调度算法1、先来先服务（FCFS）调度算法可用于作业调度和进程调度用于作业调度：每次从后备作业队列中选择最先进入的作业，将它们调入内存，为它们分配资源、创建进程，然后挂到就绪进程队列上。用于进程调度：每次从就绪进程队列中选择最先进入的进程，为之分配处理机，使之投入运行。直到运行完成进程才会让出处理机--非抢占式。有利于长作业，而不利于短作业。进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.99性能评价：周转时间=完成时间–到达时间带权周转时间=周转时间/服务（运行）时间2、短作业/进程优先（SJF/SPF）短作业优先（SJF）从后备队列中选择估计运行时间最短的作业，调入内存运行。短进程优先（SPF）从就绪队列中选出估计运行时间最短的进程，将处理机分配给它，使它立即执行。直到运行完成进程才会让出处理机--非抢占式。缺点：对长作业不利，有可能长期不被调度；完全没考虑作业的紧迫程度（某些特殊的）；用户做出的估计时间带有很大的主观性。2.259133.5141844E3.116182101252C2.678926731B1.5365.5111423D2.11带权周转时间84周转时间4完成时间FJS2.81带权周转时间94周转时间4完成时间FCFS4服务时间0到达时间平均A进程名作调业度情算况法周转时间=完成时间–到达时间带权周转时间=周转时间/服务时间3.3.2、高优先权先调度算法既能用于作业调度，也可用于进程调度。作业调度：从后备队列中选择若干个优先权最高的作业装入内存。进程调度：把处理机分配给就绪队列中优先权最高的进程两种占用CPU的方式：非抢占式优先权算法抢占式优先权算法1、优先权调度算法的类型非抢占式优先权算法系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程就一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。主要用于批处理系统抢占式优先权算法新的就绪进程i，优先权Pi。正在执行的进程j，优先权Pj。若Pi=Pj，原进程j继续执行。若PiPj，做进程切换。新进程i执行。优点：能更好的满足紧迫作业的要求。主要用于比较严格的实时系统。2、优先权的类型1）静态优先权在进程创建时确定的，在进程整个运行期间保持不变优先权利用某一范围的整数来表示，该整数称为优先数。如：0—7，0—255确定优先权的依据：（1）进程类型（2）进程对资源的需求（3）用户要求注：规定优先数越小，其优先权越高4/348334C15/81517482B119118D带权周转时间周转时间155完成时间2优先权非抢占式优先权算法5服务时间0到达时间A进程名作调业度情算况法平均6.251.3例：非抢占式优先权算法t(等待)优先权t(运行)优先权2)动态优先权在进程创建时创立的优先权，可随进程的推进或等待时间的增加而改变。如等待时间长，优先权升高。等待时间+要求服务时间优先权=------------------------------------要求服务时间等待时间+要求服务时间响应时间响应比(Rp)=------------------------------------=-------------------要求服务时间要求服务时间3、高响应比优先调度算法(HRRN)为每个进程引入动态优先权，随着等待时间增加优先权提高。优点：等待时间相同，短作业优先权高(即SPF)要求服务时间相同，等待时间长，优先权高(即FCFS)对于长作业，在等待足够时间后，可获得处理机3.571528E2.2591344C1.177962B2.8142056D2.141带权周转时间83周转时间3完成时间3服务时间0到达时间平均A进程名作调业度情算况法RC＝1+(9-4)/4=2.25RD＝1+(9-6)/5=1.6RE＝1+(9-8)/2=1.5RD＝1+(13-6)/5=2.4RE＝1+(13-8)/2=3.5执行顺序：A－B－C－E－DHRRN（R大，优先权高）3.3.3、基于时间片的轮转调度算法1、时间片轮转法1）基本原理系统将所有的就绪进程按FIFO原则排成一个队列，将CPU分配给队首进程，执行一个时间片。在时间片内进程未完，则插入就绪队列未尾，CPU交给下一个进程。2）时间片大小的确定时间片略大于一次典型的交互所需要的时间。3.3313173.33131744E2.259113.5141642C2673.67111231B5101336923D带权周转时间2.58.4周转时间144完成时间RRq=4带权周转时间3.4611.8周转时间3.751515完成时间RRq=14服务时间0到达时间平均A进程名作调业度情算况法周转时间=完成时间–到达时间带权周转时间=周转时间/服务时间2、多级反馈队列调度算法原理：设置多个就绪队列，并为各个队列赋予不同的优先级和不同长度的时间片；新创建的进程挂到第一优先级的队列后，然后按FCFS原则排队等待调度。当轮到其执行时，如它能在时间片内完成，便撤离系统；如果不能完成，便被挂入第二级队列后，……，最后一级队列采用时间片轮转法；仅当第一级队列空闲时，调度程序才调度第二级队列中的进程运行，依次类推……；新进程可抢占低级进程的处理机。……多级反馈队列调度算法示意图CPU时间片完进程调度进程完成就绪队列一就绪队列二就绪队列三就绪队列n时间片完时间片完就级1绪队列空就级2绪队列就级3绪队列运行等待12354时间片小－－－－大优先级高－－－－低多级反馈队列调度算法的性能多级反馈队列调度算法能较好地满足各种类型用户（进程）的需要：终端（交互）型作业用户短批处理作业用户长批处理作业用户3.3.4、基于公平原则的调度算法1、保证调度算法如果系统中有n个相同类型的进程同时运行，保证每个进程都获得相同的处理机时间1/n。2、公平分享调度算法使所有用户能获得相同的处理机时间。3.4实时调度实现实时调度的基本概念和条件实时调度算法的分类常见的几种实时调度算法选学1.实时调度是为了完成实时处理任务而分配处理机的调度方法。2.硬实时任务要求计算机系统必须在用户给定的时限内完成3.软实时任务允许计算机系统在用户给定的时限左右处理完毕。提供更详细的调度信息：就绪时间、开始截止时间或完成截止时间、处理时间、资源要求、优先级等；含有硬实时任务的实时系统中，广泛采用基于优先级的抢占式调度策略实时调度算法分类：非抢占式轮转调度算法：只适用于一般实时信息处理系统非抢占式优先级调度算法：优先级最高的实时任务排在就绪队列队首，当前任务终止或完成后才被调度。基于时钟中断抢占式优先级调度算法：新到的实时任务的优先级高于当前任务时，并不立即抢占CPU，而是等到时钟中断到来，才进行切换。用于大多数的实时系统中。立即抢占的优先级调度算法：这种算法适用于实时要求比较严格的实时控制系统。常用的几种实时调度算法1、最早截止时间优先算法（EDF）该算法根据任务的开始截止时间来确定任务的优先级。截止时间越早，优先级越高。该算法要求实时任务的就绪队列按任务截止时间的早晚排序。调度程序总选择队首的任务执行。该算法可用于抢占式和非抢占式调度。t任务到达任务执行开始截止时间134211224433非抢占式调度方式2、最低松弛度优先算法（LLF）该算法根据任务的松弛度来确定任务的优先级。松弛度越低，优先级越高。松弛度＝任务必须完成的时间－运行时间－当前时间