Uniprocessor scheduling algorithms Scheduling Policies Static Scheduling Dynamic Scheduling With Priorities Without Priorities Static Priorities Dynamic Priorities Non- Non- preemptive Preemptive Preemptive Non-preemptive Preemptive preemptive SJF FPS mit Deadline mit Deadline SRT HRRN RR FCFS Real-Time Scheduling RMS DMS EDF LLF MUF FPS:Fixed-Priority FCFS:First Come First served RMS:Rate Monotonic RR: Round Robin DMS:Deadline Monot.Scheduling Real-Time Scheduling FC-EDF EDF:Earliest Deadline SJF:Shortest Job First LLF:Least Laxity First SRT:Shortest Remaining Time MUF:Maximum Urgency HRRN:Highest Response Ratio Nea FC-EDF:Feedback EDF
Uniprocessor scheduling algorithms
实时调度算法分类 USTC 按调度方案生成方式 -静态调度：off-line,Static Table-Driven Scheduling,可预测性好 ·Time-driven scheduling,任务时间表，固定每个任务的起始时间 -动态调度：on-line ·如：Priority-.driven scheduling,生成任务队列，顺序执行 ● 按调度策略：如何进行任务排序？ -基于时间的调度算法(Time-driven scheduling):离线静态 -基于优先级的调度算法(Priority-driven scheduling):动态在线 按调度机制：触发任务调度的方式 时间触发：Clock driven/ticK scheduling Allchn ·固定时间片可变时间片 -事件触发：优先级驱动/中断驱动 static scheduling dynamic scheduling -Hybrid: (or offline,or clock driven) (or online,or priority driven) 一可抢占不可抢占 uc/OS? static-pnority dynamic-prionty scheduling scheduling 18/41
实时调度算法分类 • 按调度方案生成方式 – 静态调度：off-line，Static Table-Driven Scheduling，可预测性好 • Time-driven scheduling，任务时间表，固定每个任务的起始时间 – 动态调度：on-line • 如：Priority-driven scheduling，生成任务队列，顺序执行 • 按调度策略：如何进行任务排序？ – 基于时间的调度算法（Time-driven scheduling）：离线静态 18/41 – 基于时间的调度算法（Time-driven scheduling）：离线静态 – 基于优先级的调度算法（Priority-driven scheduling）：动态在线 • 按调度机制：触发任务调度的方式 – 时间触发：Clock driven/tick scheduling • 固定时间片/可变时间片 – 事件触发：优先级驱动/中断驱动 – Hybrid： – 可抢占/不可抢占 • uc/OS？
Scheduling Objective USTC User-oriented Criteria.System-oriented Criteria Response time Throughput Turnaround time -CPU utilization -Deadline -Fairness Algorithm Decision Mode Priority Function Arbitration Rule FCFS non-preemptive P(r)=r Random S.JF non-preemptive P(t)=-t FIFO/Random SRT preemptive (at job arrival)】 P(a,t)=a-t FIFO/Random preemptive RR P()=k Cyclic (at quantum) MLF preemptive P(a),n-levels FIFO/Cyclic (at quantum) a:attained time:w:waiting time:r:real time,r=a w;t:total time required
Scheduling Objective • User-oriented Criteria – Response time – Turnaround time – Deadline • System-oriented Criteria – Throughput – CPU utilization – Fairness a：attained time；w：waiting time；r：real time, r = a + w；t：total time required
=1 Round-Robin D 1245611↓0丝日45指9t ·抢占式时间片轮转调度 ●●●●●●●●◆● -任务的当前时间片用完后，OS将CPU使用权给下一个Ready任务 或被中断的任务(Interrupted) - 基于CPU使用率的共享式调度(Share-driven scheduling) ·“共享”=按比例分享！ T 一适用：响应时间要求不高者 CS 。 时间片确定 -周转时间T:任务从提交OS直至完成的时间（f-a) ·称turn around time(就是实时任务模型中的“响应时间”) - 带权周转时间W:一个任务的周转时间T与OS实际给它的服务时 间Ts之比。 调度目标：n个任务的平均周转时间T或平均带权周转时间W短 ·即：硬件资源利用率高（吞吐率最大） r-w- 一时间片大或小好？
Round-Robin • 抢占式时间片轮转调度 – 任务的当前时间片用完后，OS将CPU使用权给下一个Ready任务 或被中断的任务（Interrupted） – 基于CPU使用率的共享式调度（Share-driven scheduling） • “共享”= 按比例分享！ – 适用：响应时间要求不高者 • 时间片确定 – 周转时间Ti ：任务从提交OS直至完成的时间（f - a） • 称turn around time（就是实时任务模型中的“响应时间”） – 带权周转时间Wi ：一个任务的周转时间Ti 与OS实际给它的服务时 间TSi之比。 – 调度目标：n个任务的平均周转时间T或平均带权周转时间W短 • 即：硬件资源利用率高（吞吐率最大） – 时间片大或小好？
例： =1 -C D D S=3 B B D D 012!4561↓↓0且丝日45络”出9t I图1S=1和S3时任务运行图 表1反映时间片的大小对平均周转周期和平均带权周期的影响。 任务情况 任 务名 A B D 平均 到达时间 0 时间片 服务时间 5 4 3 完成时间 16 14 1 17 8-1 周转时间 16 13 9 14 13 带权周转时间 32 325 3 28 3.0625 完成时间 I 15 9 17 S=3 周转时间 14 H 14 12.25 带权周转时间 2.8 3.5 2.3 2.8 2.85
例：