Page 100 - 《软件学报》2021年第6期

1674 Journal of Software 软件学报 Vol.32, No.6, June 2021

得到任务 T i 实例在一个执行周期内的抢占序列.遍历该序列,就能得到每个抢占任务的抢占缓存块集合 ECBs ,
n T
所有集合 ECBs 的并就是 T i 实例执行过程中被抢占导致的可能访问缓存块总数,它与被抢占任务 T i 的有用缓
n T
存块集合UCBs 的交集就是被替换出缓存块的集合.这样就可以得到任务 T i 在第 k 个子周期(k=1,2,...,m)被任务
i T
j
n 抢占后,基于第 j 个抢占序列任务的缓存相关抢占代价 CRPD ,利用公式(7)计算得到:
, ik
⎛ ⎞
CRPD j , ik = CacheMissTime UCBs ∩ × ⎜ ⎜ ∪ ECBs n T ⎟ ⎟ (7)
⎝ i T n T ∈ preemtingSequence () i T ⎠
其中,preemtingSequence(T i )为任务 T i 从被抢占到恢复执行这一时间段内高优先级任务的执行序列.
公式(7)用来计算在一次抢占序列下的被抢占任务的抢占代价,但是我们需要计算在一个任务周期内发生
多次抢占的被抢占任务的抢占代价.因为在被抢占任务的一个任务周期内可能出现多个抢占序列,那么被抢占
任务的一个周期内的 CRPD 为所有抢占序列所计算出的 CRPD 值之和.因此,在一个周期内,一个抢占任务 T i 的
CRPD i,k 可以用公式(8)计算:
N
=
CRPD , ik ∑ CRPD j , ik (8)
j= 1
进而,利用公式(9)可以计算任务 T i 在一个超周期内的最大延迟时间 CRPD i :
CRPD i =max{CRPD i,1 ,CRPD i,2 ,…,CRPD i,k } (9)
2.5 最坏执行时间计算及任务集可调度性判定

更新任务 T i 的最坏执行时间为WCET i new ,根据公式(10)可以计算出任务缓存相关抢占延迟约束下的最坏执
行时间:
WCET new = WCET old + CRPD (10)
i i i
其中,
1) WCET i old 为在 AADL 架构模型中 T i 的执行时间;
2) CRPD i 为任务 T i 在一个超周期内的缓存相关抢占最大延迟.
AADL 架构模型中,任务的执行时间具体大小是架构模型中线程构件的 Execution_Time 属性确定一个任务
执行范围值,表示线程的最好执行时间和最坏执行时间.公式(10)中计算出来的最坏执行时间是基于超周期内
任务集调度中产生的抢占序列所计算出的每个任务的 CRPD,但是在不同的调度序列会产生不同的抢占点,修
改了任务的 WCET 后,再次执行任务集则会产生不同的调度序列,因此在基于抢占代价分析系统可调度性的时
候,要不断地更新 WCET 的值,直到其不再发生变化的时候,说明该任务的 WCET 计算完成.
要对系统的实时性进行分析,则要引入最坏响应时间(worst case response time,简称 WCRT),最坏响应时间
是实时调度理论研究的重点问题.可调度性的基本思想就是判断任务的最坏响应时间是否满足截止期约束:如
果一个任务的最坏响应时间满足截止期约束,那么该任务就是可调度的.
系统的调度策略直接影响到任务执行的最坏响应时间,这是由于不同的调度策略下任务最坏响应时间的
计算方法不同.例如,分区内调度系统采用固定优先级调度策略时,缓存抢占延迟的情况下任务 T i 的最坏响应时
间由任务 T i 的执行时间WCET new 和高优先级任务对 T i 的干扰 I 确定,其干扰 I 的计算方法如公式(11)所示:
i
I = n WCET× ∑ new (11)
∀ j T ∈ hp () j
i T
其中,
1) hp(T i )为调度任务集中任务的优先级高于任务 T i 的任务集合;
2) WCET j new 为任务 T j 的最坏执行时间;
3) n 为高优先级任务在任务 T i 的响应时间内所释放的次数的上界,n 大小的计算如公式(12)所示:
⎡ WCRT ⎤
n = ⎢ i ⎥ (12)
⎢ P j ⎥ ⎣ ⎦