操作低掣聪_处理机调度与死锁

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

1、第第 1 章章 处理机调度与死锁处理机调度与死锁3.1 处理机调度的层次对于批量作业而言，通常要经历的处理机调度包括： 作业调度(高级调度或长程调度)，进程调度(低级调度或短程调度)； 对于终端型作业，通常只需通过进程调度即可获得处理机； 完善的 OS 中，为提高内存的利用率，设置了中级调度(中程调度) 。3.1.1 高级调度(High Level Scheduling)其主要功能是：根据某种调度算法把外存上处于后备队列中的作业调入内存，调度对象是作业。1. 作业和作业步作业-程序、数据、作业说明书；外存-内存； 作业步-作业加工步骤；编译-连结-运行 作业流-若干作业依次放在外存上，等待处理

2、；2. 作业控制块 JCB(相当于进程中 PCB):包含管理和调度作业的全部信息，主要有：作业标识,用户名称，用户账户， 作业类型，作业状态，调度信息，资源需求，进入系统时间，开始处理时间， 作业完成时间，退出时间，资源使用状况。 作业进入系统，运行时，完成时，都要用到 JCB。3. 作业调度作业调度：根据 JCB，审查系统是否满足资源需求，并按照算法从外存的 后备队列中选取某些作业调入内存，为其建立进程，分配资源，最后将进程插 入就绪队列。 在每次执行作业调度时，都须做出以下两个决定。 1) 接纳多少个作业 (多道程序度)：即内存中允许多少个程序同时运行， 太多影响服务质量，太少资源利用率系

3、统吞吐量低。应根据系统的规模和速度 折中。 2) 接纳哪些作业：取决于调度算法。最简单的“先来先服务” ，较常用的 “短作业优先”和“基于优先级”的调度，比较好的“响应比高者优先” 。3.1.2 低级调度(Low Level Scheduling)1.功能-保存 CPU 现场信息；按算法选进程；分配 CPU；2.基本机制-1)排队器：就绪队列排队；2)分派器 ：取出进程,分配处理机； 3)上下文切换：两对切换分别是：当前进程分派程序，分派程序新选进程；思考：如何优化上下文切换机制？思考：如何优化上下文切换机制？ 采用硬件（两组寄存器） ，存储上下文，这样上下文切换只需改变指针。3.调度方式-非

4、抢占方式和抢占方式：1) 非抢占方式(Non-preemptive Mode)-占有 CPU,一直运行 采用这种方式，可能引起进程调度的几个因素： 进程执行完毕或因某事件不能继续； 提出 I/O 请求而暂停； 在进程通信或同步过程中执行了 P (wait)、Block、Wakeup 等某种原语 操作。 优点：实现简单、系统开销小，适于批处理系统。 缺点：难以满足实时任务立即执行的要求。 2) 抢占方式(Preemptive Mode) 抢占的原则有：优先权原则、 短作业(进程)优先原则、时间片原则。 优点：对大多数进程公平、适于实时系统。 缺点：系统开销大3.1.3 中级调度(Intermed

5、iate-Level Scheduling)又称中程调度(Medium-Term Scheduling)。 引入目的：提高内存利用率和系统吞吐量。 实质是存储器管理中的对换功能(外存-内存):暂时不能运行的进程调至外 存上去等待(静止就绪或静止阻塞)，具备条件且内存空闲时，由中级调度决定 把哪些进程重新调入内存。三种层次调度的比较-低级调度 高级调度 中级调度 运行频率 10-100ms 几分钟 中等3.2 调度队列模型和调度准则 3.2.2 选择调度方式和调度算法的若干准则1. 面向用户的准则(1) 周转时间短作业从开始到结束：通常作为评价批处理系统调度算 法的依据。可把平均周转时间描述为：

6、 iiiTnT11作业的周转时间 T 与系统为它提供服务的时间 TS 之比，即 W=T/TS，称为带权周转时间，而平均带权周转时间则可表示为: (2) 响应时间快从输入到首次响应：选择分时系统调度算法的依据。 (3) 截止时间的保证开始或完成的最迟时间：评价实时系统调度算法的 指标。 (4) 优先权准则：作为批处理、分时、实时系统选择算法的依据。3.3 调度算法3.3.1 先来先服务和短作业(进程)优先调度算法1.先来先服务调度算法 (FCFS)可用于作业和进程调度利于长作业(CPU繁忙型)，不利于短作业(I/O 繁忙型)2. 短作业(进程)优先调度算法 SJ(P)F-可用于作业和进程调度 n

7、iSii TT nW11SJ(P)F 是从后备(就绪)队列中选择一个或若干个估计运行时间最短的作业， 将它们调入内存运行(将处理机分配给它)。 优点：适合于短作业,如上表中的 D。 缺点： (1) 该算法对长作业不利：如上表中的 C。更严重的是，由于总是优先调 度那些(即使是后进来的)短作业(进程)，将可能导致长作业(进程)长期不被调 度。 (2) 该算法不能保证紧迫性作业(进程)会被及时处理。 (3) 由于作业(进程)的长短是估计执行时间，致使该算法不一定能真正做 到短作业优先调度。 3.3.2 高优先权优先调度算法 -处理机分给优先权最高的进程1. 优先权调度算法的类型1）非抢占式优先权算

8、法 进程一旦占有处理机，便一直执行下去，直至完成；自动放弃处理机时， 方可再重新分配处理机。主要用于批处理系统和对实时性要求不严的实时系统。2) 抢占式优先权调度算法 在其执行期间，只要出现优先权更高的进程，就立即停止当前进程的执行， 重新将处理机分配给新进程。满足紧迫作业的要求，常用于要求比较严格的实 时系统，及对性能要求较高的批处理和分时系统中。2. 优先权的类型1) 静态优先权 在创建进程时确定的，且在进程的整个运行期间保持不变。优先权用某一 范围的整数表示，优先权跟数值的大小关系用法各异。 确定进程优先权的依据有三个方面： 进程类型：系统进程高于一般进程； 进程对资源的需求：资源要求少

9、的赋予高优先级； 用户要求：用户进程紧迫程度和所付费用多少来决定。 2) 动态优先权 创建进程时赋予的优先权，可以随进程的推进或等待时间的增加而改变， 以便获得更好的调度性能。 例如：就绪队列中进程的优先权，随其等待时间以速率 a 提高，若其优先 权初值相同，即 FCFS 算法；若优先权初值不相同，则优先权初值低的进程，在 等待了足够的时间后，其优先权便可能升为最高。 采用抢占式优先权调度算法时，规定当前进程的优先权以速率 b 下降，则 可防止一个长作业长期地垄断处理机。3. 高响应比优先调度算法 优先权的变化规律可描述为：由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又要

10、求服务时间要求服务时间等待时间优先权相当于响应比 RP。据此，又可表示为：(1) 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高， 因而该算法有利于短作业。 (2) 当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时 间愈长，其优先权愈高，因而它实现的是先来先服务。 (3) 对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待 时间足够长时，其优先级便可升到很高， 从而也可获得处理机。 缺点：响应比的计算，会增加系统开销。3.3.3 基于时间片的轮转调度算法 1. 时间片轮转法1) 原理：时间片完-计时器中断-排队末尾-服务新进程 2) 时间片大小的确定：大小范围

11、从几 ms 到几百 ms。 过短：利于短作业，开销大，过长：退化为 FCFS，无法满足交互式用户。 合适的大小：取时间片略大于一次交互所需要的时间。 图 3-5 是时间片分别为 q=1，q=4 时五个进程运行情况 图 3-6 是时间片分别为 q=1，q=4 时各进程平均周转时间和平均带权周转时间。图 3-5要求服务时间响应时间 要求服务时间要求服务时间等待时间优先权ABCDEABCDEABCEACE(a) q1(b) q41234567891011 1213 14 151617 t图 3-62. 多级反馈队列调度算法不需要事先知道各进程执行时间(1)就绪队列设置：设置多个优先级和执行时间片不同

12、的就绪队列。优先权愈高时间片就愈小， 优先级变化规律：S1S2Sn。时间片变化规律：Ti=2*Ti-1。如图 3-7 多级 反馈队列调度算法 所示(2) 进程调度过程：新进程进入：放入第一队列末尾，按 FCFS 原则等待调度。轮到进程执行时： 能在时间片内完成-撤离；时间片内未完成-转入下一队列末尾，同样地按 FCFS 原则等待调度执 行，直到第 n 队列中。 (3) 队列调度： 仅当第 1(i-1) 队列均空时，才会调度第 i 队列中的进程运行； 如果正在处理第 i 队列，有新进程进入高优先权队列(1(i-1)，则新进程将抢 占处理机，把正在运行的进程放回到第 i 队列的末尾。3. 多级反馈

13、队列调度算法的性能-可满足各类用户需要 (1) 终端型作业用户：交互型作业，作业通常较小，系统只要能使这些作业(进 程)在第一队列所规定的时间片内完成，便可使终端型作业用户都感到满意。 (2) 短批处理作业：短作业在第一队列中执行一个时间片即可完成，稍长作业 只需在第二，三队列执行一个时间片即可完成。所需的队列数较少，所以周转 时间较短。 (3) 长批处理作业：它将依次在第 1,2,n 个队列中运行，用户不必担心其作 业长期得不到处理。就绪队列1就绪队列2就绪队列3就绪队列nS1S2S3至CPU至CPU至CPU至CPU(时间片：S1 S2 S3)3.4 实时调度 3.4.2 实时调度算法的分类

14、 实时调度算法可以按不同方式进行分类：实时任务性质-硬实时算法、软实时算法；调度方式-非抢占式、抢占式(本小节内容)；调度时间静态调度、动态调度。1. 非抢占式调度算法-小型、要求不严格的系统中(1) 非抢占式轮转调度算法(10s)：工业群控系统、循环轮转队列 (2) 非抢占式优先调度算法(100ms):优先级高者排在队首等待优先调度2. 抢占式调度算法要求较严格(10ms 以下)根据抢占时间分为： (1) 基于时钟中断的抢占式优先权调度算法:时钟中断到来再占有 (2) 立即抢占(Immediate Preemption)的优先权调度算法:当前进程不在临 界区，即可立即抢占。 （下图很重要）3

15、.4.3 常用的几种实时调度算法1. 最早截止时间优先 EDF(Earliest Deadline First)算法（了解）按任务开始时间或结束时间确定优先级，就绪队列。包括非抢占式和抢占式。 1) 非抢占式调度方式用于非周期实时任务(a) 非抢占轮转调度当前进程实时进程实时进程请求调度实时进程枪占当前 进程，并立即执行(d) 立即抢占的优先权调度调度时间进程 1进程 2实时进程要求调度进程 n实时进程调度实时进程运行(b) 非抢占优先权调度当前进程实时进程实时进程请求调度当前进程运行完成调度时间当前进程实时进程请求调度时钟中断到来时调度时间(c) 基于时钟中断抢占的优先权抢占调度调度时间实时

16、进程2）抢占式调度方式用于周期实施任务 二三行是采用通常的抢占式优先调度，四行用抢占式最早截至时间调度2. 最低松弛度优先即 LLF(Least Laxity First)算法 （重点）根据任务紧急(或松弛)的程度，来确定实时任务的优先级，并按优先级形 成就绪队列，主要用于可抢占调度方式中。 任务的紧急程度愈高，该任务的优 先级就愈高，以使之优先执行。 例如，一个任务在 200ms 时必须完成，而它本身所需的运行时间就有 100ms，因此，调度程序必须在 100ms 之前调度执行，该任务的紧急程度(松弛 程度)为 100ms。又如，另一任务在 400 ms 时必须完成，它本身需要运行 150ms，调度程序必须在 150ms 之前调度执行，则其松弛程度为 250 ms。 设有两个周期性实时任务 A 和 B，分别每 20ms,50ms 执行