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

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

17. 将 k 倍任务周期对应的时间作为一个执行断点;
18. k=k+1;}
19. end while;}
20. end for
21. 输出执行断点集 ExecutionPointSet;
由于在 RMS 和 EDF 调度策略下,高优先级任务对低优先级任务的抢占一定会发生在高优先级任务到来的
时刻,那么判断一个执行断点是否是抢占点,可以根据当前任务在执行断点到来时其剩余执行时间是否为零,并
且是否有高优先级的任务到达来判断.所以在任务执行断点序列计算完成后,还要计算每个任务的剩余执行时
间来判断执行断点是否为抢占点.如图 5 中任务 T 1 和 T 2 的执行序列为例,从第 Kms~K+5ms 处的执行断点序列
为{Kms,K+1ms,K+2ms,K+4ms},假设当前执行断点为 K+1ms,那么上一个执行断点则为 Kms.Kms 处释放任务
T 1 ,且 T 1 所需要的执行时间为 1.5ms,那么在当前执行断点处,任务 T 1 并未执行完成,并且在当前执行断点 K+1ms
时刻,任务 T 2 到达,T 1 剩余执行时间为 0.5ms,任务 T 1 被抢占,当前执行断点即为一个抢占断点.因此,把一个任务
执行过程中的所有抢占断点计算出来后,即可得到该任务调度过程中的抢占序列.

T 2的优先级高于T 1的优先级
当前
处于的 T i
执行断点 T i 释放
T 2 T 2 T 2 T 2
上一个
执行断点

T 1 T 1 T 1 T 1 T 1

0ms ... Kms K+1ms K+2ms K+3ms K+4ms K+5ms
T 1:周期2ms;最坏执行时间1.5ms;截止期2ms.
T 2:周期3ms;最坏执行时间0.5ms;截止期3ms.
Fig.5 Calculation of preemption points
图 5 任务抢占点的判定
算法 2 给出了通过判断抢占点生成抢占序列的过程.算法 2 包含一层 Do-while 循环,循环变量为执行断点
序列,该序列大小与每个任务周期大小相关,而任务周期由设计人员提供,故算法 3 的时间复杂度无法根据任务
数量 n 进行估算.假设执行断点序列中的元素为 k 个,则算法时间复杂度为 O(k).
算法 2. 求解一个任务的抢占序列.
Input:任务集 SM 及其执行断点序列 ExecutionPointSet、分区配置信息表;
Output:任务集中任务在一个超周期内的抢占序列 preemptionSequence.
1. 任务集初始化:所有任务实例化标志 State=0; //State=0 表示任务实例未就绪或执行完成被销毁
2. 所有任务剩余执行时间 LaveExecutionTime=0;
3. 时钟变量 clock=0;
4. 完成预计时间:time=0;
5. 执行断点初始化:CurPt←ExecutionPointSet[0]; //设置当前执行点为执行断点序列中首元素
6. Unfinished=null; //设定上个执行断点处未完成的任务记录初始值为空
7. 抢占序列初始化:preemptionSequence=null;
8. 初始化分区标志:r=1; //分区初始值为第 1 个分区
9. 初始化任务预估;
10. Do:
11. if (执行断点处是否有任务要释放)