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

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

级任务的执行序列.用 preemptionSequence(T i )表示任务 T i 从被抢占到恢复执行这一段时间内高优先级任务的
执行序列,则 preemptionSequence(T i )=(T x ,T y ,T z )表示任务 T i 被任务 T x 抢占到任务 T i 恢复执行之间的任务集的执
行序列为 T x →T y →T z .因此,我们在计算每一个执行任务的 CRPD 前,需要确定该任务的抢占序列,并把序列中每
一次可能抢占的 CRPD 计算出来,并对所有抢占序列 CRPD 计算的结果进行求和,得到该任务被抢占的 CRPD.
对于 RMS 和 EDF 调度策略,系统任务在一个超周期内的抢占只能发生高优先级任务到来的时刻,我们称这
些点为任务执行断点,任务抢占点是一类特殊的执行断点.所以分析任务的可调度性时,首先要计算出在一个超
周期内所有任务的执行断点.假设有一个任务集 Taskset={K 1 ,K 2 ,K 3 },其中,K 1 的周期为 2ms,K 2 的周期为 3ms,K 3
的周期为 6ms,那么该任务集的超周期为其 3 个任务的最小公倍数,即为 6ms,分别为(0ms,2ms,3ms,4ms,6ms,8ms,
9ms,10ms)时刻.对于分区调度情形,分区调度时间片切换点也被认为是一种任务执行断点(如图 4 所示).

K i K i 释放

K 3 K 3 K 3

K 2 K 2 K 2 K 2 K 2

K 1 K 1 K 1 K 1 K 1 K 1 K 1
0ms 1ms 2ms 3ms 4ms 5ms 6ms 7ms 8ms 9ms 10ms
Fig.4 Dispatch of tasks in the task group within a superperiod
图 4 任务集中任务在一个超周期内的释放情况
算法 1 给出了任务集所有执行断点的计算过程.在算法 1 中有 Do-while 循环和 for 循环(设分区个数为 m,
任务集中任务数量为 n),前者循环的次数为 m,后者循环次数为 n,循环之间无嵌套关系,且 m 与 n 之间满足关系:
m≤n,故算法 1 的时间复杂度为 O(n).
算法 1. 计算任务集执行断点序列的过程.
Input:AADL 调度模型实例化文件;
Output:调度模型的执行断点序列 ExecutionPointSet;
1. 解析 AADL 调度模型文件,提取任务集合 SM;
2. 断点序列初始化:ExecutionPointSet=null;
3. 计算 SM 中任务的超周期 Superperiod;
4. if (采用分区调度) then
5. 获取分区配置信息 //包括分区调度顺序、时间片大小;
6. temp=1 //temp 标志当前的执行分区;
7. Do:
8. 将该分区切换点加入 ExecutionPointSet 集合;
9. temp=temp+1;
10. while (temp≤分区个数)
11. end if
12. for (SM 中的所有任务 T)
13. {令 k=0; //k 代表一个超周期内任务的最大执行次数
14. P 为任务 T i 的周期;
i T
15. while (k* P <Superperiod) //当 k 倍任务周期小于超周期
i T
16. {if (k 倍周期不属于 ExecutionPointSet)