第3章处理机调度与死锁

1.调度的基本概念2.调度队列模型和调度准则3.调度算法4.实时调度5.死锁第三章 处理机调度与死锁Date 11.处理机调度的基本概念处理机是计算机系统中的重要资源处理机调度算法对整个计算机系统的综合性能指标有重要影响可把处理机调度分成三个层次：l 高级调度l 中级调度l 低级调度Date 2n 高级调度也称为 作业调度， 长程调度，接纳调度 或宏观调度 ， 用于决定把外存上处于后备队列中的哪些作业调入主存，并为它们创建进程、分配必要的资源，然后将新创建的进程排入就绪队列，准备执行。n 一般在批处理系统中有作业调度。在分时和实时系统中无作业调度。Date 3n 低级调度也称 微观调度、进程调度或 短程调度 ， 它决定主存中的就绪队列上的哪个进程（单处理器系统）将获得处理器，然后把处理器分配给该进程，使其执行。n 从处理机资源分配的角度来看，处理机需要经常选择就绪进程或线程进入运行状态。由于低级调度算法的频繁使用，要求在实现时做到高效。Date 4n 中级调度u系统将那些暂时不能运行的进程从主存调到外存（仍然保持进程状态）上的特定区域，这些在外存存放的进程所处的状态称为就绪驻外状态或挂起状态。当这些进程的运行条件具备，且主存又有空闲时，在中级调度的控制下，再将处于外存上的那些重新具备运行条件的就绪驻外进程调入主存，并将其状态修改为就绪状态，放入就绪队列，等待进程调度。 n 目的u是为了进一步提高主存的利用率和系统的吞吐量。管理进程在内外存间的交换，从存储器资源管理的角度来看，把进程的部分或全部换出到外存上，可为当前运行进程的执行提供所需内存空间 。Date 5n 三种调度中，进程调度运行频率最高，在分时系统中通常是 10100ms便进行一次进程调度，因而进程调度算法不能太复杂。n 作业调度往往是发生在一个（批）作业运行完毕，退出系统，而需要重新调入一个（批）作业进入时，帮作业调度的周期较长，大约几分钟一次。n 中级调度的运行频率，介于上述两种调度之间Date 6调度队列模型1. 仅有进程调度的调度队列模型在 分时系统 中，通常仅设置了进程调度，用户键入的命令和数据，都直接送入内存，对于命令，是由 OS为之建立一个进程。常把就绪进程组织成 FIFO队列形式。每个进程在执行时，都可能出现以下三种情况：n 任务在给定时间片内已经完成（完成状态）n 任务在本次分得的时间片内尚未完成（就绪状态）n 在执行期，进程因为某事件而被阻塞后，被 OS放入阻塞队列（阻塞状态）Date 7调度队列模型1. 仅有进程调度的调度队列模型图 3 - 1 仅具有进程调度的调度队列模型 Date 8调度队列模型2. 具有高级和低级调度的调度队列模型在 批处理系统 中，不仅进程调度，而且还需要有作业调度。与仅有进程调度的调度队列模型的区别：n 就绪队列的形式：在批处理系统中，最常用的是 最高优先权 调度算法，相应的最常用的就绪队列形式是 优先权队列 。（仅有进程调度的模型就绪队列采用 FIFO队列 形式）n 设置多个阻塞队列。Date 9调度队列模型2. 具有高级和低级调度的调度队列模型图 3-2 具有高、低两级调度的调度队列模型 外存 内存Date 10调度队列模型3. 同时具有三级调度的调度队列模型OS引入中级调度，可把进程的就绪状态分为内存就绪和外存就绪，阻塞状态分成内存阻塞和外存阻塞。n 调出操作：使进程状态由内存就绪转变为外存就绪，由内存阻塞转变为外存阻塞。n 中级调度：使外存就绪转变为内存就绪。Date 11调度队列模型3. 同时具有三级调度的调度队列模型外存外存内存Date 123调度基本准则 n 面向用户的准则 u周转时间短 ：评价批处理系统性能的准则F 周转时间 ：指作业被提交给系统开始，到作业完成为止的时间间隔F 分为作业周转时间和进程周转时间F 作业周转时间包括：作业在外存上的等待时间；进程在就绪队列中等待时间；进程在 cpu上执行时间；等待 I/O时间F 作为系统管理者希望作业平均周转时间最短，有利于大多数用户可把 平均周转时间 描述为：作业的周转时间 T与系统为它提供服务的时间 TS之比，即W=T/TS，称为 带权周转时间 ，而平均带权周转时间则可表示为 :Date 133调度基本准则n 面向用户的原则 u响应时间快 ：评价分时系统性能的准则F 响应时间 ：指从用户通过键盘提交一个请求开始，到系统首次产生响应为止的时间间隔F 包括：键盘请求送入处理机时间；处理机处理请求时间；形成响应送回终端时间u截止时间有保证 ：评价实时系统性能的准则F 截至时间 ：某任务必须开始执行的最迟时间，或必须完成的最迟时间。u优先权原则 ：在批处理，分时，实时系统中都使用F 让紧急作业及时得到处理，有时甚至是立即抢占Date 143调度基本准则n 面向系统的原则 u系统吞吐量高 ：评价批处理系统性能的重要指标F 吞吐量 ：指在单位时间内系统完成的作业数。u处理器利用率好 ：适用于大中型多用户系统，不适于单用户或实时系统F 一般 cpu利用率在 40%-90%之间u各类资源的平衡利用 ：适用于大中型多用户系统，不适于单用户或实时系统Date 15调度算法n 先来先服务调度算法 （ FCFS） n 短作业（进程）优先调度算法 （ SJF）n 优先级调度算法（高响应比优先调度算法 HRRN）n 基于时间片的轮转调度算法 (RR)（多级反馈队列调度算法 FB ）Date 16先来先服务调度 (FCFS)算法 n 既可用于作业调度，也可用于进程调度n 原理u作业调度：每次调度是从后备队列中，选择一个或多个 最先进入 该队列的作业，将它们调入内存，为它们分配资源，创建进程，然后放入就绪队列。u进程调度：从就绪队列中，选择一个 最先进入该队列的进程，把处理器分配给该进程，使之得到执行。该进程一旦占有了处理器，它就一直运行下去，直到该进程完成或因发生事件而阻塞，才退出处理器。 Date 17先来先服务调度 (FCFS)算法 n 既可用于作业调度，也可用于进程调度u优点 :实现简单u缺点 :没考虑进程的优先级u特点 :利于长作业（进程）和 CPU繁忙型的作业（进程），而不利于短作业（进程）和 I/O繁忙型作业（进程）。uCPU繁忙型的作业：需要大量的 CPU时间进行计算，而很少请求 I/O。（科学计算）uI/O繁忙型作业：在 CPU进行处理时，需频繁地请求 I/O。（事务处理）Date 18先来先服务调度算法n 完成时间 =开始时间 +服务时间n 周转时间 =完成时间 -到达时间n 带权周转时间 =周转时间 /服务时间Date 19短作业（进程）优先调度算法n 原理u短作业优先（ SJF）：从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。u短进程优先（ SPF）：从就绪队列中选择一个估计运行时间最短的进程，将处理器分配给该进程，使之占有处理器并执行，直到该进程完成或因发生事件而阻塞，然后退出处理器，再重新调度。 Date 20短作业（进程）优先调度算法n 优点：照顾到了系统中占大部分的短进程，有效地降低了作业的平均等待时间，提高了系统的吞吐量。n 缺点：但对长作业不利，没有考虑紧迫度，根据估计时间不准确。 Date 21短作业（进程）优先调度算法Date 22优先级调度算法 n 原理u从后备队列中选择一个优先级最高的作业，调入内存运行。u从就绪队列中选择一个优先级最高的进程，让其获得处理器并执行。 Date 23两种占用 CPU的方式：u非抢占式优先权调度算法F系统一旦把处理器分配给就绪队列中优先权最高的进程后，该进程就占有处理器一直运行下去，直到该进程完成或因发生事件而阻塞，才退出处理器。u抢占式优先权调度算法F当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的 CPU， 提供给具有更高优先级的进程使用， 能更好地满足紧迫作业的要求。Date 24优先权的类型静态优先权：在进程创建时指定优先权，在进程运行时优先权不变。 (短进程优先调度算法 )优点：简单易行，系统开销小缺点：不精确，可能出现优先权低的长期没有被调度的情况。Date 25优先权的类型动态优先权：在进程创建时创立一个优先数，但在其生命周期内优先权可以动态变化。如等待时间长优先权可改变 ,比如： 规定在就绪队列中的进程，随其等待时间的增长，其优先权以速率 a提高。Date 26高响应比优先调度算法n 高响应比优先算法（ HRRN： Highest Response Ratio Next）（优先权）响应比 R = 作业周转时间（作业响应时间 ） 要求服务时间=（要求服务时间 +作业等待时间） /要求服务时间= 1 +（作业等待时间 /要求服务时间）从上式可见：#若等待时间相同， 则要求服务时间愈短 ,其优先权愈高 SPF#若服务时间相同， 优先权决定于等待时间 -FCFS #长作业若等待时间足够长，优先级会升高，也能获得 CPUDate27高响应比优先调度算法n 原理u它是从就绪队列中选择一个响应比最高的进程，让其获得处