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

陆寅 等:面向 AADL 模型的存储资源约束可调度性分析 1667

往往会导致系统行为失效,但是不一定导致最坏的执行时间,因此时序异常不在本文不考虑范围.在抢占式系统
中,当任务之间抢占发生时,被抢占任务已经加载到缓存中的内容由于缓存冲突而被替换出缓存,当被抢占任务
再次执行时,需要将替换出去的内容再次加载到缓存 [17] ,重复加载的时间就是任务调度因为缓存相关抢占造成
的任务延迟代价.造成抢占延迟的根本原因是由于任务之间存储资源映射发生冲突.
在抢占式调度环境中,任务的执行效率以及系统实时性所受的影响往往来自于任务之间的抢占,任务的抢
占不仅会造成上下文切换代价(context switch overhead,简称 CSH),并且也会造成缓存相关抢占延迟.研究成果
表明:任务调度过程中,上下文切换代价大约在 5μs~10μs 之间,而缓存相关导致的任务抢占带来的计算延迟可
以到达 1μs~10000μs,每一次计算任务抢占的延迟大小取决于系统结构及其 Cache 容量 [18,19] .因此,系统的实时
性分析需要更多地考虑系统架构中存储资源结构及其缓存容量可能导致相关抢占引起的延迟.
由于系统模型中特定的软硬件环境下,CPU 从缓存中加载一个缓存块的时间 CacheMissTime 可以认为是常
数,也可以用它来表示从主存中加载一个块大小的数据内容到缓存中的时间上限,所以计算缓存相关抢占代价
时,只需要知道被抢占任务在恢复执行时需要重复加载缓存块的个数,就可以采用公式(1)计算出系统资源抢占
延迟 CRPD [13] :
CRPD=g×CacheMissTime (1)
其中,(1) g 为被抢占任务恢复执行时需要加载的缓存块个数;(2) CacheMissTime 表示从主存中加载一个缓存块
大小内容到缓存中所需要时间的上界,在特定硬件体系结构中可以将其看成一个常数.
在系统架构层级分析模型中,各构件的可调度性的关键是计算构件的 CRPD.由于架构模型中没有系统代
码实现的信息,也就没有系统执行时真实的运行剖面信息可用来计算 CRPD,所以如何确定被抢占构件恢复执
行时需要加载缓存块的个数,是系统架构可调度分析的难点.如果使用被抢占任务所有缓存块个数参与计算
CRPD,显然会高估 CRPD 的值,因为被替换出去的缓存块可能在被抢占任务恢复执行后不会再使用到.本文基
于有用缓存块(useful cache block,简称 UCB)和抢占缓存块(evicting cache block,简称 ECB)的大小来估算 CRPD
的值.有用缓存块是指在程序执行的过程中不被替换出缓存的任务数据块,而抢占缓存块是指在抢占任务的执
行过程中需要替换进入缓存的任务数据块.基于 UCB,ECB 的思想,人们提出了两种 CRPD 计算方法为 UCB-
Union 和 ECB-Union [13] .UCB-Union 方法是用来计算任务 T k 对 T i 抢占代价的开销,计算方法如式(2)所示 [14] :
⎛ ⎞
CRPD UCB -Union = CacheMissTime × ⎜ UCBs ∩ i ⎟ ∪ ECBs (2)
ik
(, ) ⎜ ⎟ k
⎝ ∀∈ (, ) k ⎠
kbet i
其中,(1) CRPD UCB -Union 为 UCB-Union 方法计算出的抢占任务 T k 抢占任务 T i 所产生的缓存相关抢占延迟;
(, )ik
(2) UCBs i 为任务 T i 的有用缓存块集合;(3) ECBs k 为任务 T k 的抢占缓存块集合;(4) bet(i,k)表示被调度的任务集
中优先级大于等于被抢占任务 T i 且优先级低于任务 T k 的任务集合.
ECB-Union 方法用来计算任务 T k 对 T i 抢占代价的开销,计算方法如公式(3)所示:
⎧ ⎪ ⎛ ⎞ ⎫
⎪
CRPD ECB -Union = CacheMissTime × max (, )i k ⎨ UCBs ∩ ⎜ ECBs k ⎟ ∪ ⎬ (3)
kbet
(, )ik ∀∈ i ⎜ ⎟
∈ ⎝
⎪ ⎩ thp ()k ∪ k T ⎠ ⎪ ⎭
其中,(1) CRPD ECB -Union 为 ECB-Union 方法所计算出的任务 T i 抢占任务 T k 的 CRPD;(2) UCBs i ,ECBs k 的含义与公
(, )ik
式(2)中一致;3) hp(k)表示在调度任务集中任务优先级大于任务 T k 的任务集合.
UCB-Union 和 ECB-Union 方法都会高估缓存抢占代价,其原因是它们在 CRPD 计算时,把没有参与抢占的
高优先级任务也加入了被抢占任务的 CRPD 计算中.为此,本文针对可能的缓存抢占代价高估问题提出基于抢
占序列的 CRPD 计算方法,重点解决抢占发生时,如何准确计算被抢占任务的 CRPD,准确地判定系统架构中各
构件的可调度性.
2.2 线程的时间自动机模型
为了刻画系统架构中各构件的运行行为,模拟构件运行的调度行为,AADL 把系统中最小执行单元线程构
件的调度执行行为抽象为一个时间自动机模型.AADL 线程状态机中任务状态分为 Ready,Running,Awaiting