admin管理员组文章数量:1572325
第二章 Scheduler
调度:在有限的一组处理单元上决定具有某些已知特征(周期性、持续时间/执行时间/计算时间)的一组任务的顺序和/或执行时间。这些单元具有给定的能力(容量、处理速度),并且在每个任务的完成时间和处理单元的使用上受到一组约束。
Work-conserving scheduling:在每一时刻,优先级与每个活动作业相关联,并且可以执行的最高优先级作业被选择在可用处理器上执行。当活动作业存在时,处理器永远不会处于空闲状态(除非迁移约束阻止任务在空闲处理器上执行,分区调度/自挂起?)
在过去:每个任务有专用的处理器,只需要保证任务在deadline之前执行完成即刻,不是实时系统RTOS
而现在 :一个处理器上有多个任务,需要调度保证每个任务满足deadline
如果所有任务都可以根据一组指定的约束完成,则称该调度(schedule)是**可行(feasible)**的。
如果存在至少一个算法可以产生一个可行的调度,则这一组任务被称为**可调度(schedulable)**的,
一些非实时调度算法(可以用做实时调度算法的一部分):
- FIFO,先进先出
- LIFO,后进先出
- SETF,最短执行时间优先
- LETF,最长执行时间优先
一些定义:
Arrival time/release time :一个任务到达,可以被执行的时间点.
Computation time c i c_i ci :处理器在没有被打断的情况下,执行一个任务所必需的时间
Deadline d i d_i di:一个任务需要被完成的时间点
Start time: 任务开始被执行的时间点
Finishing time f i f_i fi: 任务执行完成的时间点
L a t e n e s s ( L i ) : L i = f i − d i Lateness (L_i): L_i=f_i- d_i Lateness(Li):Li=fi−di, 代表一个任务被完成时相对于deadline的时间长度,如果是在deadline前完成,他的延迟是负数。
T a r d i n e s s o r e x c e e d i n g t i m e ( E i ) : E i = m a x ( 0 , L i ) Tardiness\ or \ exceeding\ time (E_i): E_i=max(0,Li) Tardiness or exceeding time(Ei):Ei=max(0,Li), 一个任务在结束时间之后仍然活跃的时间长度
L a x i t y o r S l a c k t i m e ( X i ) : X i = ( d i ) f i − a i − C i Laxity\ or\ Slack time (X_i): X_i=(d_i)\ f_i-a_i-C_i Laxity or Slacktime(Xi):Xi=(di) fi−ai−Ci 是任务在激活时可以延迟(或被其他任务抢占)以在截止日期内完成的最长时间。
Response time 完成一个任务所需要的时间.$ R_i=F_i-r_i.$ 也可以是被高优先级任务抢占的时间和计算时间 R i = I i + C i R_i=I_i+C_i Ri=Ii+Ci相加
Average response time平均响应时间: 1 n ∑ i = 1 n ( R i ) \frac{1}{n}\sum^n_{i=1}(R_i) n1∑i=1n(Ri) ,其实就是n个任务的响应时间求个平均值。
全部完成时间 total completion time : max f i − min r i \max{f_i}-\min{r_i} maxfi−minri ,最后被完成的任务的结束时间减去最早到的任务的开始时间。
Maximum Lateness 最大延迟时间 : L m a x = max i f i − d i L_{max}=\max_i{f_i-d_i} Lmax=maxifi−di 所有任务中延迟时间最大的任务的延迟时间。
Maximum Number of Late tasks : N l a t e = ∑ i n m i s s ( f i ) m i s s ( f i ) = 0 i f f i ≤ d i e l s e 1 N_{late}=\sum^n_imiss(f_i)\\miss(f_i)=0 \ if\ f_i \ \le d_i\ else\ 1 Nlate=∑inmiss(fi)miss(fi)=0 if fi ≤di else 1说白了就是这个调度会让多少任务的结束时间超过截止期限。
图之间的优先关系可以通过非循环有向图(对于WCET最坏执行时间,控制流图,CFG)来描述,其中任务由节点表示,优先关系由箭头表示。CFG在任务集上诱导一个偏序。
这个图可以有不同的解释,激活当前任务的所有后续任务(并发任务执行)。激活任务的一个后续任务(非确定性选择)。
实时系统可以分为硬实时和软实时系统,都是尽力在ddl之前完成任务,但是根据没按时完成的后果,严重的是硬实时,没有严重后果的是软实时。
调度算法可以按几种标准分成如下三类
1.Time-Triggered (TT) scheduling 时间触发调度
- 也称为:时钟驱动调度
- 所有任务调用时间都是离线计算的,并存储在表中
- 运行时分派是一种简单的表查找。示例:静态循环调度Static cyclic scheduling
Event-Triggered scheduling 事件触发调度,这也是这门课关注的部分
- 进程的时间表由外部中断的发生决定
- 固定优先级调度
- 动态优先级调度
2.Fixed/Static priority scheduling 固定/静态优先级调度
Dynamic priority scheduling 动态优先级调度
3.Preemptive scheduling 可抢占式调度
non-preemptive scheduling 不可抢占式调度
接下来介绍非抢占式调度
对于每个事件,都有一个将要执行的相应流程。事件由(a)外部中断和(b)进程本身发出。在队列中收集事件;根据排队规则,选择一个事件来运行。
进程不能被中断。
如果事件队列为空(例如空闲任务),后台进程可以运行(并被抢占!)。定时事件仅在经过一段时间间隔后才进入队列。
上图这个进程是是CPU的运行简单版本,当事务队列是空的时候,CPU进入低电休眠;否则从事务队列抓取事务,并且执行事务对应的进程。
非抢占式调度的属性
进程之间的通信是简单的(共享资源不会产生问题),但是中断可能引发问题。
如果环境或进程生成太多事务,会造成缓存溢出,当很长的进程阻止了其他的进程运行也会造成缓存溢出(事务队列放不下了)。解决方法也很简单,把长进程划分的更小,局部上下文保存(?)。
Co-operative Multitasking 协作多任务
每个进程允许上下文切换当 cswitch() 函数被调用. 单独的调度程序来选择下一个运行的进程。
优点
- 知道哪里发生了上下文切换
- 共享资源更少出错
缺点
- 编程错误可以阻止其他线程,线程永远不会放弃CPU。(很简单的一点大概就是没写cswitch?)
- 如果在允许上下文切换之前花费太长时间,则实时行为将面临风险。(就是从线程执行的时候开始到cswitch很久?)
Preemptive Scheduling – Stack Policy 可抢占式任务,栈策略
和非抢占式的情况很像,但是进程可以被其他进程抢占,这解决了长任务的部分问题。
如果抢占顺序受到限制,我们可以使用通常的基于堆栈的函数调用上下文机制(进程=函数)。
进程必须按照其实例的后进先出顺序LIFO完成。
- 限制灵活性
- 如果多个进程等待外部事件的时间未知,则不实用
共享资源(进程之间的通信!)必须加以保护,例如:禁用中断、使用信号量。
箭头所指向的地方就发生了抢占,T2抢占T1, T3抢占T2。
Preemptive Multitasking
由操作系统决定何时进行上下文切换,以及下一个进程是谁。使用timer去调用操作系统和切换上下文。使用硬件或者软件中断,或者直接调用操作系统去切换上下文。
控制流图 像下图
Static cyclic scheduling
- 所有任务调用时间都是离线计算的,并存储在表中
- 运行时分派是一种简单的表查找
Round-Robin scheduling
- 每个作业准备好执行时都会加入一个先进先出(队列)
- 队列头部的作业最多执行一个时间片。无论作业是否完成,它都将被抢占并放置在队列的末尾
- 用于调度分时应用程序
- 常用于台式计算机系统
- 也称为处理器共享算法
- 常用于服务器集群的负载平衡
Weighted Round-Robin scheduling
- 不同的作业可能有不同的权重,而不是给每个作业相同的时间片。作业的权重是指分配给作业的处理器时间的分数
- 具体地说,一个作业的权重为每轮 w t w_t wt时间片,一轮的长度等于所有就绪作业的权重之和
- 已被用于高速交换网络中的实时流量调度。
Static/Fixed priority scheduling
- 每个任务都有一个固定的优先级
- 运行时间分配是基于优先级的
- 可以是抢占式,也可以是非抢占式
Dynamic priority scheduling
- 任务优先级在运行时动态分配
- 总是使用复杂的算法来确定每个任务/作业的优先级
例如,最早截止日期优先(EDF)
Cyclic Executive Scheduling 循环执行调度
- 执行时间线是一个无限长的超周期序列。
- 同一调度在每个超时段执行一次。
- 计划是脱机设计的,并存储在表中。
- 运行时任务分派是简单的表查找。
属性:
- 可预测
- 低运行时开销
缺陷:
如果任务周期相对较短,任务表可能会变得非常大。维护噩梦?Maintenance nightmare
未广泛使用除了某些安全关键系统。
简单的周期性时间触发调度
每隔一个周期P,从时间t(0)开始,timer都会到期,然后从头开始执行进程表。
时间触发的循环执行调度
P被划分成了很多个帧f,每个帧的开头都有一个任务被释放。
通用时间触发调度器
这个图 就是 0时刻执行T1,3时刻执行T2,7时刻执行T1。。。12时刻执行T2
Event Triggered Scheduling
-
Aperiodic Task Sets 非周期任务集
-
Periodic Task Sets 定期任务集
-
**Mixed Aperiodic and Periodic Task Sets **混合非周期和周期任务集
具有实时约束的非周期任务调度
相同到达时间,非抢占类型 | 随机到达时间,可抢占 | |
---|---|---|
独立任务集 | EDD(Jackson) | EDF(Horn) |
非独立任务集 | LDF(Lawler) | EDF*(Chetto) |
EDD Earliest Deadline Due最早期限到期
给定一组n个任务。在最小化最大延迟方面( min ( m a x i m u m l a t e n e s s ) \min({maximum\ lateness)} min(maximum lateness)),谁的截止期在前面就先调度谁,这么做是最优的。
证明:
图画的不太好,不妨假设 f 2 ′ − f 1 = 2 ≤ d 2 − d 1 = 1 f_2'-f_1 =2\ \le d_2-d_1=1 f2′−f1=2 ≤d2−d1=1
第一个调度序列中$f_1-d_1\ \le \ f_2-\ d_2 $ L m a x 1 = f 2 − d 2 L^1_{max}=f_2-d_2 Lmax1=f2−d2
第二个调度序列中 f 2 ′ − d 2 ≤ f 1 ′ − d 1 f_2'-d_2 \le f1'-d_1 f2′−d2≤f1′−d1 L m a x 2 = f 1 ′ − d 1 L_{max}^2=f_1'-d_1 Lmax2=f1′−d1
所以 L m a x 1 − L m a x 2 = f 2 − f 1 ′ − ( d 2 − d 1 ) ≤ 0 L^1_{max}-L^2_{max}=f_2-f_1'-(d_2-d_1)\le0 Lmax1−Lmax2=f2−f1′−(d2−d1)≤0
所以确实是先调度截止期在前头的。
例子:
d 1 − > d 5 − > d 3 − > d 4 − > d 2 d_1->d_5->d_3->d_4->d_2 d1−>d5−>d3−>d4−>d2
**EDF Earliest Deadline First **
执行已经arrive了的任务中,截止期最前的就行。
证明:对于每个时间间隔[t,t+1),验证实际运行的任务是否是具有最早绝对截止日期的任务。如果不是这样,则在该时间间隔内执行具有最早绝对截止日期的任务。此操作不能增加最大延迟。
引入一些变量和术语
σ ( t ) \sigma(t) σ(t)表示这个任务在片段[t,t+1)中执行
E ( t ) E(t) E(t)表明这个准备了的任务,在时间t是有最早截止时间的。
t E ( t ) tE(t) tE(t)是在当前调度中,任务 E ( t ) E(t) E(t)什么时候开始执行的时间片。
这是相同的两个任务集,上面不知道用了什么算法,下面是EDF,看黑色的方块,上下两图中t=4的时候,到达的任务有 T 1 , T 2 , T 3 , T 4 T_1,T_2,T_3,T_4 T1,T2,T3,T4,他们的截止时间分别是 d 2 ≤ d 3 ≤ d 1 ≤ d 4 d2\le d3\le d1\le d4 d2≤d3≤d1≤d4,所以在t=4的时候应该执行 T 2 T_2 T2 ,这个例子不太好,看下面的例子。
EDF:当每个任务进入系统时,会为其分配一个优先级,其优先级由其绝对截止日期决定,截止日期较早的任务被分配更高的优先级
好处是CPU利用率达到百分百
坏处是高运行时开销,过载期间的时间隔离不良。
所以这个算法没有被广泛运用。
比如下面是一个缺点,上面的调度中,T2的ddl比较前,但是T2来的太晚了,所以就算马上让给T2,T2也会超时,但还好T1执行完了,如果再提前一点,让T2在t=4时刻到,两个任务都执行不完。
事务触发调度
周期性任务的抢夺调度算法
deadline和周期一样 | deadline比周期小 | |
---|---|---|
静态优先级 | RM(rate-monotonic)速率单调 | DM(deadline-monotonic)时限单调 |
动态优先级 | EDF | EDF* |
混合周期性任务和非周期性任务的任务集
周期性任务:时间驱动,执行具有硬时间约束的关键控制活动,旨在保证正常的激活率。
非周期任务:事件驱动,可能有硬、软、非实时要求,具体取决于具体应用。
零星任务:只有对环境做出适当的假设,才能离线保证具有关键时间约束的事件驱动非周期任务;也就是说,假设每个关键事件的最大到达率。以最短到达间隔时间为特征的非周期性任务称为零星任务。
后台调度
- 周期性任务的RM和EDF调度的简单解决方案:
- 在后台处理非周期性任务,即如果没有定期请求。
- 定期任务不受影响。
- 非周期性任务的响应可能太长,不可能为其分配更高的优先级。
说白了就是有两个不同优先级的队列,周期性任务用RM算法排队,非周期任务用FCFS排队,周期任务优先级更高,非周期任务只有周期任务空闲时才能用上cpu。
例子:
每个周期性任务的竖线,都是他此刻要进行调度的时候,RM算法的特点是,周期越短的任务优先级越高,所以T1优先级大于T2,在12时刻的时候,T2没执行完,被T1抢占了,再继续执行。然后最下面的非周期任务就插周期任务的空运行。
RM - Polling Server rm-轮询服务器
想法:人为的创建一个周期性任务,这个任务专门用来处理非周期性任务,所以也被称为server。
和所有的周期性任务一样,server也有他的周期和计算时间,所以运行其上的周期性任务也会受限于他的周期
他的优先级(也就是周期的倒数)可以选取为能匹配非周期任务的需求。
如果没有提交的非周期性请求,PS将挂起自己,直到下一个周期开始,并且最初分配给非周期性服务的时间不会为非周期性执行保留。
缺点:如果一个非周期性请求刚好在服务器挂起之后到达,它必须等到下一个轮询周期开始。
周期性任务的可调度性分析
一组定期任务和一个服务器任务可以在其截止日期内执行,如果
这是充分非必要条件。
可调度性算法
Utilization Bound Test
$U=10/30+10/40+12/52=81% \ge 3(2^{1/3}-1)=78% $ 但是还是可以调度,所以说明这个利用率上界是充分条件。
精确分析:计算WCRT的方程
h p ( i ) 是 比 T a s k i 更 高 优 先 级 的 T a s k 集 合 , [ ] 是 向 上 取 整 , 整 个 式 子 采 用 迭 代 方 式 求 直 到 收 敛 hp(i)是比Task_i更高优先级的Task集合,[]是向上取整,整个式子采用迭代方式求直到收敛 hp(i)是比Taski更高优先级的Task集合,[]是向上取整,整个式子采用迭代方式求直到收敛
Task | T 周期 | D 截止 | C 计算时间 | 优先级 |
---|---|---|---|---|
1 | 30 | 30 | 10 | H |
2 | 40 | 40 | 10 | M |
3 | 52 | 52 | 12 | L |
R 1 = C 1 + 0 = 10 ≤ D 1 = 30 , 所 以 可 以 调 度 R_1=C_1+0=10\le D_1=30 ,所以可以调度 R1=C1+0=10≤D1=30,所以可以调度。 R 2 = C 2 + [ R 2 T 1 ] C 1 \displaystyle R_2=C_2+[\frac{R2}{T1}]C_1 R2=C2+[T1R2]C1,从 R 2 = C 2 R_2=C_2 R2=C2的最好情况开始迭代,直到收敛。第一次是 R 2 = 10 + [ 10 30 ] × 10 = 10 + 1 × 10 = 20 ; 接 着 迭 代 R 2 = 10 + [ 20 30 ] × 10 = 10 + 1 × 10 = 20 。 发 现 收 敛 了 , 所 以 R 2 就 是 20 ≤ D 2 = 40 \displaystyle R_2=10+[\frac{10}{30}]\times10=10+1\times10=20;接着迭代R_2=10+[\frac{20}{30}]\times10=10+1\times10=20。发现收敛了,所以R_2就是20\le D_2=40 R2=10+[3010]×10=10+1×10=20;接着迭代R2=10+[3020]×10=10+1×10=20。发现收敛了,所以R2就是20≤D2=40,可以调度。R3算数过程如下图:
版权声明:本文标题:实时系统-调度算法和可调度分析 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1727724606a1127073.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论