处理机的调度与死锁

《处理机的调度与死锁》由会员分享，可在线阅读，更多相关《处理机的调度与死锁（77页珍藏版）》请在金锄头文库上搜索。

1、第三章 处理机调度与死锁3.1 处理机调度的层次和调度算法的目标 3.2 作业与作业调度 3.3 进程调度 3.4 实时调度（自学内容） 3.5 死锁概述 3.6 预防死锁 3.7 避免死锁 3.8 死锁的检测与解除处理机调度的基本概念：在多道程环境下，进程数目往往多于处理机数目，致使它们争用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由进程调度程序完成的。它是操作系统设计的中心问题之一。3.1 处理机调度的层次和调度算法的目标3.1.1 处理机调度的层次l处理机是计算机系统中的重要资源l处理机调度算法对整个计算机系统的综 合性能指标

2、有重要影响 l可把处理机调度分成三个层次： 高级调度 中级调度 低级调度 高级调度也称为作业调度或宏观调度高级调度的时间尺度通常是分钟、小时或天 中级调度涉及进程在内外存间的交换，从存储 器资源管理的角度来看，把进程的部分或全部 换出到外存上，可为当前运行进程的执行提供 所需内存空间，将当前进程所需部分换入到内 存。指令和数据必须在内存里才能被处理机直 接访问 低级调度也称微观调度，从处理机资源分配的 角度来看，处理机需要经常选择就绪进程或线 程进入运行状态，低级调度的时间尺度通常是 毫秒级的。由于低级调度算法的频繁使用，要 求在实现时做到高效3.1.2 处理机调度算法的目标1. 处理机算法调

3、度的共同目标1）资源利用率：CPU利用率=有效工作时间/总时间2）公平性：公平性是相对的3）平衡性：保持系统资源使用的平衡性4）策略强制执行2 . 批处理系统的目标1）平均周转时间短：2）系统吞吐量高3）处理机利用率高3. 分时系统的目标 1）响应时间快 2）均衡性4 . 实时系统的目标 1）截止时间的保证 2）可预测性3.2 作业与作业调度3.2.1 批处理系统中的作业 1 作业和作业步 2 作业控制块（JCB）在JCB中所包含的内容因系统而异，通常应包含的内容 有：作业标识、用户名称、用户帐户、作业类型(CPU 繁忙型、I/O 繁忙型、批量型、终端型)、作业状态、调 度信息(优先级、作业已

4、运行时间)、资源需求(预计运行 时间、要求内存大小、要求I/O设备的类型和数量等)、 进入系统时间、开始处理时间、作业完成时间、作业退 出时间、资源使用情况等。3. 作业运行的三个阶段和三种状态1）收容阶段：建立JCB2）运行阶段：建立PCB3）完成阶段：回收PCB与JCB3.2.2 作业调度的主要任务作业调度每次要接纳多少个作业进入内存，取决于多道程序 度(Degree of Multiprogramming)，即允许多少个作业同时在内存 中运行。当内存中同时运行的作业数目太多时，可能会影响到系 统的服务质量，比如，使周转时间太长。但如果在内存中同时运 行作业的数量太少时，又会导致系统的资源

5、利用率和系统吞吐量 太低，因此，多道程序度的确定应根据系统的规模和运行速度等 情况做适当的折衷。（接纳多少个作业）应将哪些作业从外存调入内存，这将取决于所采用的调度算 法。最简单的是先来先服务调度算法，这是指将最早进入外存的 作业最先调入内存；较常用的一种算法是短作业优先调度算法， 是将外存上最短的作业最先调入内存；另一种较常用的是基于作 业优先级的调度算法，该算法是将外存上优先级最高的作业优先 调入内存；比较好的一种算法是“响应比高者优先”的调度算法。 （接纳哪些作业）3.2.3 作业调度算法1 先来先服务（FCFS）先来先服务(FCFS)调度算法是一种最简单的调 度算法，该算法既可用于作业

6、调度，也可用于 进程调度。当在作业调度中采用该算法时，每 次调度都是从后备作业队列中选择一个或多个 最先进入该队列的作业，将它们调入内存，为 它们分配资源、创建进程，然后放入就绪队列 。在进程调度中采用FCFS算法时，则每次调度 是从就绪队列中选择一个最先进入该队列的进 程，为之分配处理机，使之投入运行。该进程 一直运行到完成或发生某事件而阻塞后才放弃 处理机。作业调度性能分析在此，我们通过一个例子来说明采用FCFS调 度算法时的调度性能。下图示出有五个进程A 、B、C、D、E，它们到达的时间分别是0、1 、2、3和4，所要求的服务时间分别是4、3、 5、2和4，其完成时间分别是4、7、12、

7、14和 18。从每个进程的完成时间中减去其到达时 间，即得到其周转时间，进而可以算出每个 进程的带权周转时间。2. 短作业优先调度算法 结论： FCFS算法比较有利于长作业(进程)，而 不利于短作业(进程)。 短作业(进程)优先调度算法SJ(P)F，是指对短作 业或短进程优先调度的算法。它们可以分别用 于作业调度和进程调度。短作业优先(SJF)的调 度算法是从后备队列中选择一个或若干个估计 运行时间最短的作业，将它们调入内存运行。 而短进程优先(SPF)调度算法则是从就绪队列中 选出一个估计运行时间最短的进程，将处理机 分配给它，使它立即执行并一直执行到完成， 或发生某事件而被阻塞放弃处理机时

8、再重新调 度。 SJ(P)F调度算法也存在不容忽视的缺点：(1) 该算法对长作业不利，如作业C的周转时间由10增至16，其带 权周转时间由2增至3.1。更严重的是，如果有一长作业(进程)进入 系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即 使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度 。(2) 该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作 业(进程)会被及时处理。(3) 由于作业(进程)的长短只是根据用户所提供的估计执行时间 而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间 ，致使该算法不一定能真正做到短作业优先调度。 3. 2.4 优先级调度

9、算法和高响应比优先调度算法1优先权调度算法为了照顾紧迫型作业，使之在进入系统后便获得优先 处理，引入了最高优先权优先(FPF)调度算法。1）非抢占式优先2）抢占式优先对于最高优先权优先调度算法，其关键在于：它是使 用静态优先权，还是用动态优先权，以及如何确定进程 的优先权。2. 高响应比优先调度算法在批处理系统中，短作业优先算法是一种比较 好的算法，其主要的不足之处是长作业的运行得不 到保证。如果我们能为每个作业引入前面所述的动 态优先权，并使作业的优先级随着等待时间的增加 而以速率a提高，则长作业在等待一定的时间后，必 然有机会分配到处理机。该优先权的变化规律可描 述为：3.3 进程调度3.

10、3.1 进程调度的任务、机制和方式1. 进程调度的任务1）保存处理机的现场信息。2）按某种算法选取进程。3）把处理器分配给进程。2. 进程调度机制1）排队器2）分派器3）上下文切换器3. 进程调度方式1）非抢占方式：突发事件、I/O请求、 进程通信2）抢占方式： 优先权原则 短进程优先原则 时间片原则3.3.2 轮转调度算法1. 轮转法的基本原理在早期的时间片轮转法中，系统将所有的就绪进程按 先来先服务的原则排成一个队列，每次调度时，把 CPU分配给队首进程，并令其执行一个时间片。时间 片的大小从几ms到几百ms。当执行的时间片用完时， 由一个计时器发出时钟中断请求，调度程序便据此信 号来停止

11、该进程的执行，并将它送往就绪队列的末尾 ；然后，再把处理机分配给就绪队列中新的队首进程 ，同时也让它执行一个时间片。这样就可以保证就绪 队列中的所有进程在一给定的时间内均能获得一时间 片的处理机执行时间。换言之，系统能在给定的时间 内响应所有用户的请求。2.进程切换时机3. 时间片大小的确定 在时间片轮转算法中，时间片的大小对系统性 能有很大的影响，如选择很小的时间片将有利 于短作业，因为它能较快地完成，但会频繁地 发生中断、进程上下文的切换，从而增加系统 的开销；反之，如选择太长的时间片，使得每 个进程都能在一个时间片内完成，时间片轮转 算法便退化为FCFS算法，无法满足交互式用户 的需求。

12、一个较为可取的大小是，时间片略大 于一次典型的交互所需要的时间。这样可使大 多数进程在一个时间片内完成。图为q=1和q=4时各进程的平均周转时间和带 权平均周转时间3.3.3 优优先级调级调 度算法该算法总是把处理机分配给就绪队列中具 有最高优先权的进程。常用以下两种方法来确 定进程的优先权(优先级根据优先数来决定) 静态优先数法：静态优先权是在创建进程时确 定的，在整个运行期间不再改变。依据有：进 程类型、进程对资源的要求、用户要求的优先 权。 动态优先数法：在进程创建时创立一个优先数 ，但在其生命周期内优先数可以动态变化。如 等待时间长优先数可改变3.3.4 多级反馈队列算法 1 多就绪队

13、列设置多个就绪队列，并为各个队列赋予不同 的优先级。第一个队列的优先级最高，第二 个队列次之，其余各队列的优先权逐个降低 。该算法赋予各个队列中进程执行时间片的 大小也各不相同，在优先权愈高的队列中， 为每个进程所规定的执行时间片就愈小。例 如，第二个队列的时间片要比第一个队列的 时间片长一倍，第i+1个队列的时间片 要比第i个队列的时间片长一倍。图是多级反 馈队列算法的示意。多级反馈队列调度算法 2 各队列FCFS算法当一个新进程进入内存后，首先将它放入第一队列 的末尾，按FCFS原则排队等待调度。当轮到该进程 执行时，如它能在该时间片内完成，便可准备撤离 系统；如果它在一个时间片结束时尚未

14、完成，调度 程序便将该进程转入第二队列的末尾，再同样地按 FCFS原则等待调度执行；如果它在第二队列中运行 一个时间片后仍未完成，再依次将它放入第三队列 ，如此下去，当一个长作业(进程)从第一队列 依次降到第n队列后，在第n队列中便采取按时间片 轮转的方式运行。 3 队列优先级调度仅当第一队列空闲时，调度程序才调度 第二队列中的进程运行；仅当第1(i-1) 队列均空时，才会调度第i队列中的进程 运行。如果处理机正在第i队列中为某进 程服务时，又有新进程进入优先权较高 的队列(第1(i-1)中的任何一个队列)， 则此时新进程将抢占正在运行进程的处 理机，即由调度程序把正在运行的进程 放回到第i队

15、列的末尾，把处理机分配给 新到的高优先权进程。3.4 实 时 调 度 3.4.1 实现实时调度的基本条件 提供必要的信息(就绪时间、截止时间、处理时间、资源优先级) 系统处理能力强 采用抢占式调度机制 具有快速切换机制3.4.2 实时调度算法的分类1)非抢占式调度算法 : 非抢占式轮转调度算法 非抢占式优先调度算法2)抢占式调度算法: 基于时钟中断的抢占优先调度算法 立即抢占优先权调度算法。 实时进程调度 3.4.3 最早截止时间优先EDF(Earliest Deadline First)算法 EDF算法用于非抢占调度方式 3.4.4最低松弛度优先(LLF)算法 该算法是根据任务紧急(或松弛)

16、的程度，来确定任务 的优先级。该算法主要用于可抢占调度方式中。假如在一个实时系统中，有两个周期性实时任务A和 B，任务A要求每 20 ms执行一次，执行时间为 10 ms；任 务B只要求每50 ms执行一次，执行时间为 25 ms。 A和B任务每次必须完成的时间在刚开始时(t1=0)，A1必须在20ms时完成，而它本身运 行又需 10 ms，可算出A1的松弛度为10ms；B1必须在50ms 时完成， 而它本身运行就需25 ms，可算出B1的松弛度为25 ms，故调度程序应先调度A1执行。在t2=10 ms时，A2的松弛度可按下式算出： A2的松弛度=必须完成时间-其本身的运行时间-当前时间 =40 ms-10 ms-10 ms=20 ms 类似地，可算出B1的松弛度为15ms，调度程序应选择 B2运行。t3=30 ms时，A2的松弛度已减为0，B1的松弛度为 15 ms，于是调度程序应抢占B1的处理机而调度A2运行 .利用ELLF算法进行调度的情况3.5 死锁概述 3.5.1 资源