第3章处理机调度与死锁

第三章处理机调度与死锁3.1处理机调度的基本概念3.3调度算法3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除3.1/3.2处理机调度的基本概念系统调度的实质是资源分配系统调度的三个层次：高级调度中级调度低级调度概念、要解决的问题高级调度也称为作业调度或长程调度。把外存上的作业调入内存。执行高级调度时，需考虑的问题：每次接纳多少个作业？取决于多道程序度（Degree)。太多太少？接纳哪些作业？取决于何种调度算法。低级调度也称进程调度。处理机--就绪进程---执行进程调度有两种基本方式：非抢占式一旦CPU分给某进程后，它一直执行，直到完成或发生某事件被阻塞，才分给其它进程。抢占式允许根据某原则，停止正在执行的进程，重新分配有时间片原则、优先权原则、短作业优先原则。进程（CPU）调度要解决的问题WHAT：按什么原则分配CPU—进程调度算法WHEN：何时分配CPU—进程调度的时机HOW：如何分配CPU—CPU调度过程（进程的上下文切换）•中级调度介于高级调度与低级调度之间，其主要目的是为了提高内存的利用率和系统吞吐量。涉及进程在内外存间的交换，把暂不执行的进程部分或全部换出到外存，将当前进程所需部分换入到内存，为当前进程的执行提供所需内存空间。注意：指令和数据必须在内存里才能被处理机直接访问。三种调度的比较：进程调度运行频率最高，一般10~100ms进行一次，故其算法不能太复杂，以免占用太多CPU时间。作业调度是一批（个）作业运行完，退出系统，需重新调入一批（个）作业进入内存，故周期较长，允许算法较复杂。中级调度介于上述二者之间。就绪队列CPU阻塞队列时间片完等待事件进程完成进程调度事件出现交互用户调度队列模型一：只有进程调度分时系统中就绪队列CPU阻塞队列时间片完等待事件2进程调度事件1出现作业调度调度队列模型二：高级调度、进程调度并存阻塞队列阻塞队列等待事件n等待事件1事件2出现事件n出现后备队列进程完成批量作业批处理系统中调度队列模型三：高、中、低调度并存就绪队列CPU就绪挂起队列时间片完进程调度作业调度阻塞队列阻塞挂起队列等待事件进程完成事件出现中级调度后备队列批量作业交互型作业事件出现挂起确定调度算法的几个原则对用户周转时间短，主要用于批处理能及时响应，常评价分时系统截止时间的保证，针对实时系统优先权，在各种系统中都要考虑到对系统公平原则，对微机不适用资源利用率，尤其是CPU，一般40%~90%系统吞吐量大，单位时间内完成的作业多3.3各种调度算法先来先服务法（FCFS）对作业：按照后备作业队列中先后次序调度作业对进程：按照进程就绪的先后次序来调度进程优点:实现简单缺点:没考虑优先级，有利于长作业，对短作业不好进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间ABCD0123110011000110110211011022021100100199111001.99短作业优先算法：（一般不采用）基于FCFS算法对短作业不利而提出的，使占很大比例的短作业优先于长作业执行。缺点：对长作业非常不利；未考虑作业紧迫程度；不公平，因为作业长短是由用户提供的，有可能把长作业故意说小。基于优先权的调度（HPF—HighestPriorityFirst）优先选择就绪队列中优先级最高的进程投入运行确定优先权的方法静态优先数法：在进程创建时指定优先数，在进程运行时优先数不变。实现简单，开销小，适于要求不太高的系统，因为优先权低者可能长期不能被调度。动态优先数法：在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变两种占用CPU的方式可剥夺式（可抢占式Preemptive）：当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用不可剥夺式（不可抢占式Non-preemptive）：某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去高响应比优先调度算法系统对该作业的响应时间=等待时间+服务时间优先权相当于响应比RP要求服务时间响应时间要求服务时间要求服务时间等待时间优先权(1)如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业(2)当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务(3)对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。要求服务时间响应时间要求服务时间要求服务时间等待时间优先权时间片轮转程序调度算法(RR—RoundRobin)把CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程，进程轮流占有CPU，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列末尾。同时系统选择另一个进程运行多级反馈队列调度算法设置多个就绪队列，并为各个队列赋予不同的优先级。优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。多级反馈队列调度算法多级反馈队列调度算法当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。多级反馈队列调度算法多级反馈队列调度算法仅当第1~(i-1)队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1~(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机。多级反馈队列调度算法多级反馈队列调度算法先来先服务、短作业优先完成，事先不必知道所需服务时间动态优先权、可抢占调度时间片内执行多级反馈队列调度算法的性能终端型作业用户短批处理作业用户长批处理作业用户进程（CPU）调度要解决的问题WHAT：按什么原则分配CPUWHEN：何时分配CPUHOW：如何分配CPU—进程调度算法—进程调度的时机—CPU调度过程（进程的上下文切换）进程调度的时机当一个进程运行完毕，或由于某种错误而终止运行当一个进程在执行中处于阻塞状态（等待I/O）分时系统中时间片到当有一个优先级更高的进程就绪（可抢占式）例如：新创建一个进程在进程通信中，执行中的进程执行了某种原语操作（P操作，阻塞原语，唤醒原语）进程切换进程切换一个进程让出处理器，由另一个进程占用处理器的过程进程的切换使系统中的各进程均有机会占用CPU进程的切换是由进程状态的变化引起的，而进程状态的变化又与出现中断事件有关当有中断事件发生时，当前运行的进程被中断，中断响应后由操作系统处理出现的中断事件。中断处理后，某些进程的状态会发生变化，也可能又创建了一些新的进程。因此，要进行队列的调整。然后，进程调度根据预定的调度算法从就绪队列选一个进程占用CPU。这个占用CPU运行的进程可能仍是被中断的进程，也可能是另一个进程CPU调度过程*保存现场：顺序保存，最后一步保存PSW*选择要运行的程序*恢复现场：最后一步恢复选中进程的PSW例题设有４个进程P1、P2、P3、P4，它们到达就绪队列的时刻、运行时间及优先级如下：进程到达就绪队列时刻运行时间优先级P1091P2143P3282P43104问：若采用可剥夺的优先级调度算法，请给出各进程的调度次序以及每个进程的周转时间注：优先级1为最低优先级答案：P1P2P4P2P3P1P131个基本时间单位P214P321P410例1：在一个批处理系统中，有两个作业进程。有一作业序列，其到达时间及估计运行时间列表见下表：作业到达时间（时）估计运行时间（分钟）110：0035210：1030310：1545410：2020510：3030系统采用最高响应比优先的作业调度算法（响应比=等待时间/估计运行时间）。作业进程的调度采用短作业优先的抢占式调度算法。1）列出各作业的执行时间片段；2）计算这批作业的平均周转时间。[分析]本题的作业和进程的推进过程如下：10：00作业1到达,被作业调度程序调度进入系统,被进程调度程序调度开始运行10：10作业1运行10分钟，剩余25分钟由于作业较长，被进程调度程序调度处于就绪状态作业2到达，由作业调度程序调度进入系统,由于作业较短，被进程调度程序调度开始运行10：15作业1等待5分钟，剩余25分钟作业2运行5分钟，剩余25分钟作业3到达，等待作业调度进程调度10：20作业1等待10分钟，剩余25分钟作业2运行10分钟，剩余20分钟作业3等待5分钟作业4到达，等待作业调度进程调度10：30作业1等待20分钟，剩余25分钟作业2运行20分钟，剩余10分钟作业3等待15分钟作业4等待10分钟作业5到达，等待作业调度进程调度10：40作业1等待30分钟，剩余25分钟作业2运行30分钟，运行结束作业3等待25分钟，响应比为25/45作业4等待20分钟，响应比为20/20因响应比较高，被作业调度程序调度进入系统,由于作业较短，被进程调度程序调度开始运行作业5等待10分钟，响应比为10/3011：00作业1等待50分钟，剩余25分钟由于作业较短，被进程调度程序调度开始运行作业3等待45分钟，响应比为45/45因响应比相同，按序被作业调度程序调度进入系统由于作业较长，被进程调度程序调度处于就绪状态作业4运行20分钟，运行结束作业5等待30分钟，响应比为30/3011：25作业1运行35分钟，运行结束作业3等待(在内存)25分钟，因作业较长，被作业调度程序调度处于就绪状态作业5等待55分钟，被作业调度程序调度进入系统由于作业较短，被进程调度程序调度开始运行11：55作业3等待(在内存)55分钟，被进程调度程序调度开始运行作业5运行30分钟，运行结束12：40作业3运行45分钟，运行结束[解答]1）各作业的执行时间序列如下：作业1：10：00~10：10，11：00~11：25（结束）作业2：10：10~10：40（结束）作业3：11：55~12：40（结束）作业4：10：40~11：00（结束）作业5：11：25~11：55（结束）2）各作业执行时的周转时间为：作业185分钟作业230分钟作业3145分钟作业440分钟作业585分钟作业的平均周转时间为77分钟例2:有一个具有两道作业的批处理系统,作业调度采用短作业优先的调度算法,进程调度采用以优先数为基础的抢占式调度算法(优先数数值越小优先级越高),1)列出所有作业进入内存时间及结束时间2)计算平均周转时间作业到达时间估计运行时间优先数A10：0040分5B10：2030分3C10：3050分4D10：5020分610:00A作业到达,被作业调度程序调度进入系统,被进程调度程序调度开始运行10:20A作业运行20分钟,剩余20分钟由于优先级低,被进程调度程序调度处于就绪状态B作业到达,被作业调度程序调度进入系统,由于优先级高,被进程调度程序调度开始运行10:30A作业等待10分钟,剩余20分钟继续等待B作业运行10分钟,剩余20分钟继续运行C作业到达,等待被作业调度程序调度10:50A作业等待30分钟,剩余20分钟由于优先级高,被进程调度程序调度开始运行B作业运行30分钟,结束运行C作业等待20分钟,由于估计运行时间较长,仍未被调入系统中运行D作业到达,由于估计运行时间较短,被作业调度程序调入系统,由于优先级低,被进程调度程序调度处于就绪状态11:10A作业运行40分钟,结束运行C作业等待30分钟,被作业调度程序调入系统,由于优先级高,被进程调度程序调度开始运行D作业等待10分钟,由于优先级低,被进程调度程序调度处于就绪状态12:00C作业运行50分钟,结束运行D作业等待60分钟,被进程调度程序调度开始运行12:20D作业运行20分钟,结束运行作业进入内存时间结束时间A10：0011：10B10：2010：50C11：1012：00D10：5012：20各作业执行时的周转周期为:作业A70分钟作业B30分钟作业C90分钟作业D90分钟作业的平均周转时间为70分钟难