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

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

其中,
1) WCRT i 为任务 T i 的最坏响应时间;
2) P j 为任务 T j 的周期.
固定优先级抢占式系统中任务的响应时间 WCRT i 可用公式(13)计算得到:
⎡ WCRT ⎤
WCRT = i WCET i new + ∀∈ i ⎥ × ⎢ ∑ WCET j new (13)
⎢ jhp () i P j ⎦ ⎥ ⎣
为了判断任务集的可调度性,需要判断在一个超周期内,任务集中任务在每一个周期的响应时间是否超过
截止期.所以在 AADL 线程构件模型中添加剩余执行时间属性,当下一个任务执行断点来临并且下一个任务执
行断点处释放的是当前正在调度的任务,根据任务当前的剩余执行时间,判断该任务在下一次执行断点来临时
是否能够执行完成.如果当前正在执行任务的剩余执行时间小于下一个执行断点与当前时间点的差,则表示任
务能够完成执行;否则,表示该任务在下一个任务释放来临前未执行完毕,任务集不可调度.
AADL 架构任务集的可调度性判定可以通过计算每一个任务基于抢占序列的最坏响应时间,并分别比较
每一个构件任务的最坏响应时间与构件截止期的大小来进行判断.即,系统 AADL 架构是可调度的当且仅当架
构中任何一个构件任务的最坏响应时间都小于其截止期.任务 WCET 的计算如算法 3 所示.算法 3 中调用了算
法 2,并对每个任务的 WCET 求解,任务集中任务的数量 n,执行断点序列中断点数量为 k,则 n 与 k 之间满足关系:
n≤k.所以算法 3 的时间复杂度为 O(k).
算法 3. 每个任务 WCET 的计算.
Input:AADL 的 XML 实例化文件;
Output:各个任务的 CRPD 约束下的 WCET 以及任务集可调度性.
1. 解析 AADL 调度模型文件,提取任务调度属性; //提取中所需相关属性
2. 初始化线程任务:CRPD=0;
3. 根据公式(6)计算线程使用的缓存块数;
4. 根据公式(4)计算缓存利用率;
5. 求解抢占缓存块集合 ECBs; //假设缓存利用率 CU 离散分布随机过程为均匀分布;
i T
6. 计算|UCBs|=ρ⋅|ECBs|;
7. 调用算法 1 求解执行断点集 ExecutionPointSet;
8. 调用算法 2 计算任务集在一个超周期内的抢占序列 preemptionSequence;
9. if (任务集可调度)
{for (对任务集中的所有任务)
j
10. {根据公式(7)计算一次抢占序列下任务的缓存相关抢占代价 CRPD ;
, ik
11. 根据公式(8)计算任务在一个周期内的 CRPD i,k ;
12. 根据公式(9)计算任务在一个超周期内的 CRPD i ;
13. 根据公式(10)更新任务的 WCET;}
14. 输出任务集的可调度序列及其 WCET;} //在算法 2 的第 11 行~第 18 行中得到调度的结果
15. end if

3 工具实现与案例分析

基于前面建模与分析理论,采用 Eclipse 插件开发技术,开发了 AADL 模型的可调度性分析工具原型系统,
系统架构如图 6 所示.该工具支持 ARINC653 分区操作系统平台上的多分区、多任务信息系统的 AADL 架构
模型建模、存储资源建模和模型可调度性分析.