作系统作业调度.ppt

按任务执行时是否呈现周期性来划分： 周期性实时任务：每隔一段固定的时间发生 非周期性实时任务：在不可预测的时间发生。 截止时间(deadline)： 开始截止时间（最晚开始时间） 完成截止时间（最晚完成时间） 根据对截止时间的要求来划分： 硬实时任务：存在必须满足的时间限制。 软实时任务:可以容忍偶尔超过时间限制。 实时任务的类型： 2）实现实时调度的基本条件 提供必要的信息(就绪时间、截止时间、处理时间、资源要求、资源优先级) 系统处理能力要足够强: 单处理机情况下：设有m个周期性事件，事件i的周期为Pi，其中每个事件需要Ci秒的CPU时间来处理，可调度的的实时系统必须满足： C1/P1 + C2/P2 + … + Cm/Pm ≤ 1 采用抢占式调度机制 具有快速切换机制 3）实时调度算法的分类 1)非抢占式调度算法 : 非抢占式轮转调度算法(实时要求不太严格，s) 非抢占式优先调度算法(要求比较严格,数百ms) 2)抢占式调度算法: 基于时钟中断的抢占优先调度算法(要求比较严格,数10ms) 立即抢占优先权调度算法(紧迫任务,几ms甚至百微秒) 图 3-8 实时进程调度 4）常用的几种实时调度算法 I.最早截止时间优先即EDF(Earliest Deadline First)算法 1）非抢占式调度用于非周期实时任务：最早开始截止时间优先 图 3-9 EDF算法用于非抢占调度方式 2）抢占式调度用于周期实时任务：最早完成截止时间优先 II. 最低松弛度优先即LLF(Least Laxity First)算法 该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级，即选择松弛度最少的进程执行该算法。主要用于可抢占调度方式中。 松弛度：即各个进程的富裕时间（裕度） 松弛度=必须完成时间-其本身的运行时间-当前时间 图3-12 利用LLF算法进行调度的情况 图3-11 A和B任务每次必须完成的时间 假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每 20 ms执行一次，执行时间为 10 ms；任务B只要求每50 ms执行一次，执行时间为 25 ms。 练习1 对下面的5个非周期性实时任务，按最早开始截止时间优先调度算法如何进行CPU调度？(非抢占式/抢占式) 进程 到达时间 执行时间 开始截止时间 A 10 20 110 B 20 20 20 C 40 20 50 D 50 20 90 E 60 20 70 0 10 20 30 40 50 60 70 80 90 100 110 A B C D E B C E D A 到达时间 开始截止时间 练习2 若有3个周期性任务，各任务的周期和执行时间如下表所示，考虑应如何按最低松弛度优先算法对它们进行CPU调度？ 进程 周期 执行时间 A 20 10 B 50 10 C 50 15 0 10 20 30 40 50 60 70 80 90 100 110 A1 B1 C1 A2 A3 B2 C2 A4 A5 A6 B3 C3 A1 A2 A3 A4 A5 时间 各进程到达时间 必须完成时间 B1C1 B2C2 假设一个系统中有5个进程，它们的到达时间和服务时间如下表所示，忽略I/O以及其它开销时间。 分别按先来先服务FCFS、非抢占及抢占的短进程优先SPF和最高响应比优先HRRN、时间片轮转RR法 进行CPU调度，分别计算出各进程的周转时间、带权周转时间、平均周转时间和带权的平均周转时间。 进程 到达时间 服务时间 A 0 3 B 2 6 C 4 4 D 6 5 E 8 2 有一个内存中只能装入两道作业的批处理系统，作业调度数是指采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法。作业序列如下表所示，表中所列的优先进程调度的优先数，且优先数越小优先级越高。列出所有作业进入内存的时刻以及结束的时刻，计算作业的平均周转时间。 作业 到达时间 估计运行时间 优先数 A 10:00 40 5 B 10:20 30 3 C 10:30 50 4 D 10:50 20 6 * * 调度时间也是依次减少 * 图中示意的位置为到达时间点和截止时间点 * 有处理能力 * EDF没有考虑本身的运行时间 LLF考虑了 * T1 T2时刻，A2还未到达，因此B1执行