硬实时系统中基于任务同步及节能的动态调度算法

提出基于任务同步及节能的动态实时调度算法HDSA(hybrid dynamic scheduling algorithm),以有效地解决任务同步及节能的难题。HDSA结合RM及EDF算法,在满足任务实时可调度性及任务同步的限制条件下,采用DVFS节省能耗。HDSA包含静态算法及动态算法两部分。静态算法在静态条件下,求出任务的静态速度。动态调度算法在实际运行中,固定临界区的运行速度,并充分回收、利用任务运行时的空闲执行时间,调节处理器的速度,以有效降低能耗并满足实时可调度性。同时避免高优先权任务被阻塞时,临界区继承高优先权任务的速度时所造成的处理器电压开关的频繁切换,因而能有效地降低实时任务调度的成本。实验测试表明,HDSA在调度性能上明显优于目前所知的有效算法。

多处理器环境中基于节能及容错的实时动态调度算法

当前处理器由于较高的能量消耗,导致处理器热量散发的提高及系统可靠性的降低,同时任务实际运行中的错误也降低了系统的可靠性.因此同时满足节能性及容错性已经成为目前计算机领域较为关心的问题.提出的调度算法针对实时多处理器计算环境,以执行时间最短的任务优先调度为基础,结合其他有效技术(共享空闲时间回收及检查点技术),使得实时任务在其截止期内完成的同时,能够动态地降低整个系统的能量消耗及动态容错.针对独立任务集及具有依赖关系的任务集,提出两种算法:STFBA1及STFBA2(shortest taskfirst based algorithm)..通过实验与目前所知的有效算法相比,算法具有更好的性能(调度长度及能量消耗)及较低的通信时间复杂度.

基于软件容错的动态实时调度算法

在硬实时系统中 ,由于任务超时完成将会导致灾难性后果 ,因而硬实时系统具有严格的时间及可靠性限制条件 目前实时容错调度算法大部分针对硬件的容错 ,很少考虑软件运行的故障 提出了一种类似EDF基于软件容错的动态实时调度算法EBPA (expectation basedprobingalgorithm ) ,该算法在任务执行过程中通过基于期望值的若干试探性检测步骤 ,提高了任务可执行性的预测 ,尽可能避免了任务早期的错误对后续任务的影响 ,因此提高了任务的完成率并同时有效地减少了浪费的CPU时间片 通过实验测试 ,同目前所知的同类算法相比 。

同构计算环境中一种快速有效的静态任务调度算法

快速有效的调度任务是多处理器计算环境中的一个关键问题.目前任务调度算法中刻画任务依赖关系最流行的模型是DAG.在以前的文献中,提出了一种新的更实际、更普遍的TTIG模型及其相应的MATE算法(基于同构计算环境).延伸了TTIG模型,并提出基于同构系统的新的算法及两种启发式方法(GBHA1和GBHA2).GBHA以组的形式尽量消除图中回路,因而能获得任务图的全局信息,具有更好的调度性能.在模拟实验中,将此算法与MATE和其他同构环境中基于DAG的有效调度算法,在不同测试条件下进行了比较,结果显示GBHA在性能上明显优于MATE,与基于DAG模型的调度算法比较而言,在性能方面各有千秋,但在算法时间复杂度方面具有显著的优势.

基于任务同步及节能的单机系统实时动态调度算法

提出了一种基于任务同步及节能的单机系统实时混合动态调度算法(HDSA),以有效解决能耗及实时任务同步时的优先权反转所导致的缺乏实时可调度性的问题。HDSA 包含静态算法及动态算法两部分。静态算法可在静态条件下,固定临界区的运行速度,并求出非临界区部分的静态速度。动态调度算法在实际运行中,在满足周期性任务实时可调度性及任务同步的条件下,充分利用及回收任务运行时剩余的执行时间,调节处理器的速度,以有效降低能耗。同时也能避免高优先权任务被阻塞时,低优先权任务的临界区继承高优先权任务的速度所造成的处理器电压开关的频繁切换,故能有效地降低实时任务调度的成本。实验测试表明 HDSA 在调度性能上明显优于相关的有效算法。

实时数据库中具有时态限制的事务调度算法

在实时数据库中,事务对时态数据对象的访问在很多领域的应用日益广泛.目前实时数据库中的事务调度算法大多仅考虑数据的逻辑一致性,而忽略了满足时态的一致性.本文提出了临时数据截止期的概念,以定理的形式证明了低成本的预测算法的可行性,尽可能早地终止或推迟无法满足时态一致性要求的事务的执行,节省了计算资源以供其它事务执行.在此基础上提出了新的实时数据库中具有时态限制的事务调度算法TDDBPA(TemporaryDataDeadline-BasedPredictiveAlgo-rithm).通过与目前所知的有效算法比较,本算法在性能指标上(事务失败率、浪费的CPU时间)明显优于这些算法.

实时多处理器系统中基于能量节约的动态调度算法

当前处理器由于较高的能量消耗,导致处理器热量散发的提高及系统可靠性的降低,已经成为目前计算机领域较为关心的问题.然而目前一些有效降低能量消耗的技术大多针对单处理器系统,较少考虑多处理器系统.本文提出的调度算法针对多处理器系统,以最短任务优先调度为基础,结合其它有效技术,如共享空闲时间回收等,使得实时任务在其截止期内完成的同时能够有效地减低整个系统的能量消耗.针对独立任务集及具有依赖关系的任务集,本文提出两种算法:STFBA1及STFBA2(Shortest Task First-Based Algorithm).与目前所知的有效算法相比,我们的算法具有更好的性能(调度长度及能量消耗).

基于软件容错的动态实时调度算法

在硬实时系统中,由于任务超时完成将会导致灾难性后果,因而硬实时系统具有严格的时间及可靠性限制条件.目前实时容错调度算法大多针对硬件的容错,很少考虑软件运行的故障.提出了一种类似EDF的软件容错的动态实时调度算法PKSA(ProbingkstepAlgorithm),本算法在任务执行过程中,通过若干试探性检测步骤,提高了任务可执行性的预测,尽可能地避免了任务早期的失败对后续任务的影响,因此提高了任务的完成率,并同时有效地减少了浪费的CPU时间片.通过实验测试,同目前所知的同类算法相比,具有更佳的调度性能调度成本比.

同构环境中基于通信竞争的任务调度算法

基于DAG的静态任务调度算法已有深入的研究及应用.目前的调度算法大多假定处理器之间可以并行接收数据,而没有考虑实际应用中通信链路的竞争及延迟,进而导致调度算法在具体应用中效率较低.侧重研究同构计算环境下具有依赖关系任务的边调度问题,结合传统任务调度问题中的有效策略,提出基于优化插入的调度算法(OISA).OISA根据实际问题的具体特征,采用改进的路由算法选择负载较少的数据链路,并通过形式化的证明以优化通信数据在链路的开始传输时间,以达到降低调度长度的目的.通过试验测试表明,OISA在性能上明显优于目前已有的相关算法.

同构计算环境中一种新的静态任务调度算法

延伸了 TTIG模型并提出新的算法 .在模拟实验中 ,将此算法与 MATE和其它同构环境中基于 DAG的调度算法 ,在不同测试条件下进行了比较 ,结果显示该算法性能明显优于 MATE,与基于 DAG模型的调度算法比较而言 ,在性能方面各有千秋 ,但在算法时间复杂度方面具有显著的优势 .

基于挖掘具有时态限制数据语义的实时事务调度算法

在实时数据库中,事务对时态数据对象的访问在很多领域的应用日益广泛。目前实时数据库中的事务调度算法大多仅考虑数据的逻辑一致性,而忽略了满足时态的一致性。论文提出了新的实时数据库中具有时态限制的事务调度算法PSBA(PredictionandSimilarity-BasedAlgorithm)。首先提出了临时数据截止期的概念,以定理的形式证明了低成本地预测算法的可行性,尽可能早地终止或推迟无法满足时态一致性要求的事务的执行,节省了计算资源以供其它事务执行。继而通过挖掘数据语义,利用数据相似性,结合预测算法,进一步提高了调度性能。与目前所知的有效算法比较,该算法在性能指标上(事务失败率、浪费的CPU时间)明显优于这些算法。

基于任务同步及节能的实时调度算法

实时任务在实际应用中通常需要以独占方式访问共享资源,但是由于资源的独占性导致高优先权任务运行时往往被低优先权任务阻塞,从而产生优先权反转,难以满足任务的实时性;同时当前处理器由于较高的能量消耗,导致处理器热量散发提高及系统可靠性降低,已经成为目前计算机领域较为关心的问题。提出一种基于任务同步及节能的实时调度算法CSSFA,有效地解决了上述难题。CSSFA在满足任务实时可调度性及任务同步的条件下,固定临界区的运行速度,使更多的空闲时间用于非临界区部分,有效地降低了整体系统的能耗;同时也能避免高优先权任务被阻塞、临界区继承高优先权任务的速度时所造成的处理器电压开关的频繁切换,因而能有效地降低实时任务调度的成本。试验测试表明,CSSFA在调度性能上明显优于目前所知的有效算法。