操作系统原理.ppt

操作系统原理操作系统原理3.4 3.4 实时调度实时调度u能满足紧迫性时间约束紧迫性时间约束的调度称为实时调度。与实时调度相关的几个概念与实时调度相关的几个概念u 就绪时间： 进入就绪队列的时间u 开始截止时间：最迟开始处理的时间。u 完成截止时间：最迟完成时间。u 处理时间：u 资源需求：u 优先级：绝对/相对。一、实现实时调度的基本条件一、实现实时调度的基本条件v提供必要的调度信息提供必要的调度信息（就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级）v系统处理能力强系统处理能力强 (限制条件：决定系统是否可调度) 单机单机: （m-实时任务数目，实时任务数目，ci每次处理时间，每次处理时间，pi周期时间）周期时间） 多机多机: （N处理机数目，处理机数目，ci每次处理时间，每次处理时间，pi周期时间）周期时间）v采用抢占式的调度机制采用抢占式的调度机制v具有快速切换机制具有快速切换机制11 miiipcNpcmiii 1二、二、 实时调度算法的分类实时调度算法的分类u 按实时任务性质（即对时间约束的强弱程度）按实时任务性质（即对时间约束的强弱程度）v硬实时调度算法：必须满足任务截止期要求，错过可能导致严重后果。v软实时调度算法：期望满足任务截止期要求，错过一般可容忍。u 按调度方式按调度方式v非抢占式调度算法非抢占式轮转调度算法： 用于工业生产的群控系统中。非抢占式优先权调度算法：用于有一定时间要求的实时控制系统之中。v抢占式调度算法 按抢占发生的时间 基于时钟中断抢占的优先权调度算法立即抢占的优先权调度算法进程n实时进程进程1进程2实时进程请求调度调度实时进程运行调度时间（a）非抢占轮转调度）非抢占轮转调度实时进程调度实时进程调度实时进程要求调度当前进程运行完成调度时间当前进程实时进程（b）非抢占优先权调度）非抢占优先权调度实时进程调度实时进程调度实时进程要求调度 时钟中断到来时调度调度时间当前进程实时进程（c）基于时钟中断抢占的优先权抢占调度）基于时钟中断抢占的优先权抢占调度实时进程调度实时进程调度实时进程要求调度实时进程抢占当前进程，并立即执行调度时间当前进程实时进程（d）立即抢占的优先权调度）立即抢占的优先权调度实时进程调度实时进程调度三、常用的几种实时调度算法三、常用的几种实时调度算法u 最早截止时间优先算法（EDF算法）v该算法是根据任务的开始截止时间来确定任务的优先级。开始截止时间越早，其优先级越高。就绪队列中任务按其截止时间排列，队首任务先分配处理机。v如：2 43143212431开始截止时间任务执行任务到达最低松弛度优先算法（最低松弛度优先算法（LLFLLF算法）算法）u该算法是根据任务紧急（或松弛）的程序，来确定任务的优先级。任务的紧急度越高，其优先级越高，并使之优先执行。该算法主要采用抢占调度方式。u例：在一个实时系统中，有两个周期性实时任务A和B，任务A要求每20ms执行一次，执行时间为10ms；任务B只要求每50ms执行，执行时间为25ms。其最低松弛度优先算法调度如下：A8A7A6A5A4A3A2A1160140120100806040200B3B2B1A和和B任务每次必须完成的时间任务每次必须完成的时间某时刻的松弛度计算：某时刻的松弛度计算： 松弛度松弛度=必须完成时间必须完成时间-其本身的运行时间其本身的运行时间-当前时间当前时间 优先调度松弛度小的任务优先调度松弛度小的任务利用最低松弛度优先算法调度情况利用最低松弛度优先算法调度情况08070605040302010B2(15)B1(20)A1(10)A2(10)B1(5)A3(10)A4(10)B2(10)t1 t2 t3 t4 t5 t6 t7 t8