maintained by RTOS e》 卡面年人 Task Control Block relative deadline D; task identifier task address t a d task type absolute deadline criticalness response time R; (d=a:+R) priority ∩Deadline d state computation time period Computation time Period relative deadline absolute deadline BLOCKED T signal wait utilization factor context pointer dispatching precedence pointer activation termination READY RUNNING resource pointer preemption pointer to the next TCB ACTIVE
maintained by RTOS UnRegistered
Task scheduling Priority queues TCB rejection Thread ID Starting Address Task Parameters Sporadic Acceptance Task Type Jobs Test Thread Context Phase Scheduling Period Periodic Information Jobs Processor Relative Deadline Synchronization Number of Instances Information Aperiodic Event List Time Usage Jobs Information Timer Information Other Information activation dispatching termination Execution scheduling preemption
Task scheduling Priority queues TCB UnRegistered
实时任务调度 ·逐一调度并发任务执行，满足约束条件 一功能：排序、分配（单处理器、多处理器） - 可行调度(feasible schedule):所有任务的延迟f-d≤O -最优调度(optimal schedule):对所有任务集都可行 ·处理器利用率，任务集大小 ·最大延迟(lateness),最坏响应时间，总完成时间(makespan) ·任务集的最大jitter ·算法选择需考虑任务（集）属性 C 任务数：固定任务集可变 一有无时限 S d 一到达时刻： 同时到达/异步到达，周期性 一优先次序： 独立任务集 可抢占性 S=1 B 一调度器开销 D D D ·执行调度的时机 01234 561&90且边日45指1出9t 18/41
18/41 实时任务调度 • 逐一调度并发任务执行，满足约束条件 – 功能：排序、分配（单处理器、多处理器） – 可行调度（feasible schedule）：所有任务的延迟f – d ≤ 0 – 最优调度（optimal schedule）：对所有任务集都可行 • 处理器利用率，任务集大小 • 最大延迟（lateness），最坏响应时间，总完成时间（makespan） • 任务集的最大jitter • 算法选择需考虑任务（集）属性 – 任务数：固定任务集/可变 – 有无时限 – 到达时刻：同时到达/异步到达，周期性 – 优先次序：独立任务集 – 可抢占性 – 调度器开销 • 执行调度的时机 UnRegistered
STC Uniprocessor scheduling algorithms Scheduling Policies Static Scheduling Dynamic Scheduling With Priorities Without Priorities Static Priorities Dynsmic Priorities Non- Non- preemptive Preemptive Preciptive Non-preemptive Preemptive preemptive SJF FPS mit Deadline mii Deadline SRT RRN RR FCFS Real-Time Scheduling RMS DMS EDF MUF FPS:Fixed-Priority FCFS:First Come First served RMS:Rate Monotonic RR: Round Robin DMS:Deadline Monot.Scheduling EDF:Earliest Deadline Real-Time Scheduling FC-EDF SIF:Shortest Job First LLF:Least Laxity First SRT:Shortest Remaining Time MUF:Maximum Urgency HRRN:Highest Response Ratio Next FC-EDF:Feedback EDF
Uniprocessor scheduling algorithms UnRegistered
实时调度算法分类 ·按调度方案实现方式 -静态调度：off-line,Static Table-Driven Scheduling ·Time-driven scheduling,生成任务时间表，固定每个任务的起始时间。可预测性好 -动态调度：on-line ·如：Priority-driven scheduling,生成任务队列，顺序执行 按调度策略：如何进行任务排序？ -基于时间的调度算法(Time-driven scheduling-TD):离线静态 基于优先级的调度算法(Priority-driven scheduling-PD) -基于CPU使用率的共享式凋度算法(Share-driven scheduling-SD) ·“共享”：指按比例分享！如：Round-Robin 。3 按调度机制：触发任务调度方式 All scheduling algorithms -时间触发：Clock driven,tick scheduling ·固定时间片可变时间片 static scheduling dynamic scheduling -事件触发：优先级驱动/中断驱动 (or offline,or clock driven) (or online,or prionity dniven) -Hybrid:事件+时钟，可抢占/不可抢占 ·如uc/OS static-pnority dynamic-priority scheduling 2049uling
20/41 实时调度算法分类 • 按调度方案实现方式 – 静态调度：off-line，Static Table-Driven Scheduling • Time-driven scheduling，生成任务时间表，固定每个任务的起始时间。可预测性好 – 动态调度：on-line • 如：Priority-driven scheduling，生成任务队列，顺序执行 • 按调度策略：如何进行任务排序？ – 基于时间的调度算法（Time-driven scheduling-TD）：离线静态 – 基于优先级的调度算法（Priority-driven scheduling-PD） – 基于CPU使用率的共享式调度算法（Share-driven scheduling-SD） • “共享”：指按比例分享！如：Round-Robin • 按调度机制：触发任务调度方式 – 时间触发：Clock driven，tick scheduling • 固定时间片/可变时间片 – 事件触发：优先级驱动/中断驱动 – Hybrid：事件+时钟，可抢占/不可抢占 • 如uc/OS UnRegistered