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

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

系统根据分区配置表给每一个分区分配处理器时间片,分区内调度是根据各个分区得到时间片之后按照
分区内指定的调度策略去调度分区内的线程.在图 2 所示的分区调度模型中,每一个系统分区状态机有两个状
态:Ready 状态和 Pended 状态.Pended 表示该分区处于阻塞状态,并未得到处理器时间片信息.当 wakeupPartition
激活该分区时,记录分区已执行的时间 Partition_duration=0,并进入 Ready 状态.Ready 状态表示该分区分配到
处理器时间片并激活分区内线程,选择该分区内优先级最高的线程执行.当分区实际执行时间与分区获得时间
片大小(Partition_capacity)相等时,表明该分区的计算时间耗完,该分区中所有任务都进入阻塞状态.
2.3 抢占序列的计算
由于系统架构中不同的构件执行周期不尽相同,为了能准确、一致性地计算各构件执行的抢占代价,需要
把任务集的运行基准定义在一个超周期内.任务集的超周期是任务集中各个构件任务执行周期的最小公倍数.
为了更准确地描述任务集在一个超周期内的任务抢占发生时的时间开销,就需要对任务在一个超周期内发生
的所有抢占,即抢占序列进行计算.为了更加准确地完成抢占序列的计算,可以将抢占方式分为显式抢占与隐式
抢占两种情形.显式抢占是指抢占发生时,没有内存资源访问冲突导致 Cache 块切换的任务调度.此时,任务在特
定调度策略下所产生的抢占不需要考虑每个任务抢占点的 CRPD 代价.而隐式抢占是指抢占发生,由于系统
Cache 资源有限,任务执行过程中内存资源访问冲突导致 Cache 块切换的任务调度.此时,任务在特定调度策略
下发生抢占时,就需要考虑每个任务抢占点的 CRPD 代价.例如:系统中有 3 个线程构件,对应的执行任务集合为
{T 1 ,T 2 ,T 3 },各任务的调度行为属性见表 3.
Table 3 Task properties used in scheduling simulation
表 3 任务调度模型属性
Task Priority ϕ(释放相位) ET Period DeadLine
T 3 3 30 10ms 50ms 50ms
T 2 2 10 10ms 50ms 50ms
T 1 1 0 17ms 50ms 50ms
图 3(a)列出了该任务集在两个超周期内的调度序列(调度算法为固定优先级调度算法).在调度过程中,任务
T 1 在 10ms,60ms 处被任务 T 2 显示抢占.显然,任务的调度没有考虑 CRPD 代价对调度的影响.
然而,当考虑了 CRPD 代价并且任务调度过程中每个抢占点的 CRPD 代价较大时,基于显式抢占点计算出
的整个任务集的 WCET 则有可能过低.如图 3(b)所示的调度过程中,假设任务 T 2 在 10ms 处对任务 T 1 所产生的
抢占代价 CRPD 为 6ms,那么任务 T 1 基于 CRPD 的 WCET 为 23ms,因此会额外增加 T 3 对 T 1 的抢占.当 T 1 再次
被 T 3 抢占时,如果 30ms,80ms 的抢占点中,任务的抢占代价大于 10ms 处与 60ms 处 T 2 对 T 1 的抢占代价 6ms,那
么再以图 3(a)中的调度方式计算调度延迟的话,显然会低估任务 T 1 的调度延迟.因此,在计算任务集 WCET 的时
候,需要考虑到这些隐式抢占点的 CRPD.

任务 任务
T 3 T 3 T 3 抢占
T 3 抢占
T 3
T 3
T 2 抢占 T 2 抢占
T 2 抢占 T 2 抢占
T 2 T 2
T 1 T 1 T 1
T 1
T 1
T 1
0ms 10ms 20ms 30ms 40ms 50ms 60ms 70ms 80ms 90ms
0ms 10ms 20ms 30ms 40ms 50ms 60ms 70ms 80ms 90ms
Execution CRPD T i T i 释放 抢占 Execution CRPD T i T i 释放 抢占
(a) 显式抢占调度序列 (b) 隐式抢占调度序列
Fig.3 Comparation of task scheduling sequence in different context
图 3 不同调度情形的任务集调度序列比较
在给定调度策略下,一个抢占序列是指任务集中的一个任务从被抢占开始到该任务再次执行之间高优先