5.4.3 DPS算法分析


以上分析说明当n取值较大时,DPS的算法性能不尽如人意。但是从实际运用上看,移动便携式设备实时调度任务也是有限的,根据统计,在工作状态下,1024个时钟周期内,系统产生的硬实时任务从0~7个不等,这就意味着当下系统压力最严重的调度计算量为27=128,基本上是可以接受的。算法在实际运行过程中,如果把支配规则定得更严更细会产生比较好的效果,可以提前减去大量不必要的中间结果,使算法快速收敛。
在DPS算法基础上,下面进一步讨论硬实时调度算法思路:先将整个硬实时任务集Γτ(ξ1,ξ2,…,ξn)按截止期先后进行排序得到可调度任务集合
。接下来对
运用DPS算法得到一个最优节能调度序列:
。根据调度结果更新Γτ,如果Γτ为空则算法结束,否则重复以上步骤。本书记这个算法为HRDS算法。
算法5.2 HRDS算法(https://www.daowen.com)

定理5.5 可调度任务集合
,经过HRDS算法后的输出S是一个最优节能调度,即
。
证明:从算法运算过程可知S=S1∪S2∪…∪Sm,
ξ2,…,ξr)。对于任意元组ξi必定出现某子集Sj。假设存在ξi∈Sj,S′=S1∪S2∪…∪Sj∪…∪Sm使得:

说明
,显然与前面讨论的DPS性质相矛盾,从反面说明了HRDS算法的节能最优性,证毕。