基于检查点间隔优化的容错实时系统可调度性

引用本文

何忠政, 门朝光, 李香. 基于检查点间隔优化的容错实时系统可调度性. 2014, 44(2): 433-439[HE Zhong-zheng, MEN Chao-guang, LI Xiang. Schedulability of fault-tolerant real-time system based on checkpoint interval optimization. 吉林大学学报(工学版), 2014, 44(2): 433-439] 复制到剪切板

Permissions

基于检查点间隔优化的容错实时系统可调度性

何忠政, 门朝光, 李香

哈尔滨工程大学计算机科学与技术学院, 哈尔滨 150001

何忠政(1986),男,博士研究生.研究方向:可信计算,移动计算.E-mail:hezhongzheng@hrbeu.edu.cn

基金:国家自然科学基金项目(60873138,61100004);

摘要

针对实时系统容错模型只能容忍任务执行时一次故障发生的缺陷,基于卷回恢复容错模型,提出了任务局部最优检查点间隔求解算法,使实时系统任务能够容忍任务执行过程中多次故障的发生;进而基于局部最优检查点间隔提出任务集检查点间隔全局优化(CIGO)策略。基于不同的检查点间隔优化机制,结合实时系统任务最坏响应时间的计算公式进行系统可调度性分析。仿真实验表明,与局部最优检查点间隔相比,基于全局优化检查点间隔的实时系统容错能力有显著提升。

关键词: 计算机系统结构; 实时系统; 检查点设置与卷回恢复; 可调度性分析; 检查点间隔优化

中图分类号:TP316 文献标志码:A 文章编号:1671-5497(2014)2-433-7

Schedulability of fault-tolerant real-time system based on checkpoint interval optimization

HE Zhong-zheng, MEN Chao-guang, LI Xiang

College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China)

Fund:

Abstract

To overcome the defect of the real-time system fault-tolerant model that could only tolerate one fault occurred during the task execution process, a task Local Optimum Checkpoint Interval (LOCI) iterative algorithm was proposed. The algorithm is based on the checkpoint and rollback recovery fault tolerant model to make the task of the real-time system could tolerate multiple faults occurred during the task execution process. Then the Checkpoint Interval Global Optimization (CIGO) algorithm of the task set was proposed. The schedulability of the real-time system was analyzed based on the different checkpoint interval optimization mechanisms according to the calculation formula of the task worst case response time. The simulation results show that the strategy based on the GIGI can significantly improve the system fault resilience compared to that based on the LOCI.

Keyword: computer system architecture; real-time system; checkpoint and rollback recovery; schedulability analysis; checkpoint interval optimization

Show Figures

引言

实时系统的任务必须按时、可靠地执行完成,否则将导致灾难性后果^{[ 1]}。实时系统中电路晶体管尺寸及工作电压的减小降低了电路噪声容限,而且集成度的提高也使芯片更易受瞬时故障影响。由瞬时故障所导致的计算机可靠性已成为一个严峻的问题^{[ 2, 3, 4]}。外界环境也可能导致晶体管PN结内部逻辑状态发生改变^{[ 5]}。因此瞬时故障容错技术对保证系统的可靠性至关重要。

为了确保系统实时性和可靠性,需对任务进行可调度性分析^{[ 6]}。基于卷回恢复容错模型进行任务调度,能够在瞬时故障多次发生情况下,将任务恢复至过去某一正确状态,避免任务重新执行所带来的时间浪费。局部最优检查点间隔能够在提供容错能力的同时,最小化任务额外执行时间。检查点间隔全局优化能够调整故障恢复开销,以充分利用其他任务的空闲时间。文献[7]中卷回恢复容错模型的检查点间隔是单次故障情况下的最优检查点间隔,该检查点间隔并不是整个任务集的最优检查点间隔。文献[8]中可调度性分析模型的故障发生次数是确定的,而任务故障次数是由任务响应时间和故障发生间隔决定的。基于上述问题本文首先基于文献[8]的卷回恢复容错模型,对文献[7]的任务最坏响应时间计算公式进行改进。然后基于文献[8]的容错模型,提出了多次瞬时故障发生时的局部最优检查点间隔求解算法。接着通过最坏响应时间计算公式的分析,提出了检查点间隔全局优化(CIGO)策略。最后通过仿真实验比较了不同检查点间隔优化机制下系统的容错能力。

1 容错调度模型

实时系统的任务集可表示为 Γ={ τ₁, τ₂,…, τ _n}, τ _i表示实时系统执行的周期性任务。在卷回恢复容错模型下,任务 τ _i的配置属性可由七元组 _i, D _i, C _i, n _i, O _i, α _i, μ _i >表示,其中 T _i、 D _i、 C _i分别表示 τ _i的周期、截止时间、最坏执行时间,且 C _i _i≤ T _i; n _i表示 τ _i的检查点数量,任务开始执行时设置第一个检查点,任务结束时不设置检查点; O _i表示检查点设置时间开销; α _i为故障检测时间开销; μ _i为卷回恢复时间开销。

在任务 τ _i到达后,系统采用固定优先级调度算法(如速率单调算法(Rate-Monotonic,RM)^{[ 9]})为其分配一个固定且唯一的优先级 p _i∈{1,2,…, n}。由 p _i可确定任务集 Γ的两个子集:优先级高于 p _i的任务集合 hp( i)( hp( i) ={ τ _j∈ Γ|p _j >p _i})和优先级不低于 p _i的任务集合 hpe( i)( hpe( i) =hp( i)∪{ τ _i})。任务集 Γ中任务的优先级 p _i数值越大,则其优先级越高。本文的研究基于以下条件:

(1)仅进行单处理器系统中瞬时故障的容错处理,且瞬时故障在故障检测阶段能够被成功检测;

(2)任务之间相互独立,无故障传播,且无资源共享导致的任务阻塞;

(3)检查点间隔是相等的;

(4)两个连续发生的故障之间存在最小时间间隔,记为 T_E。若故障发生间隔小于 T_E,则系统不可调度;系统能够容忍的 T_E越小,则其容错能力越强。

文献[7]推导出了卷回恢复容错模型下实时系统任务 τ _i的最坏响应时间 R _i的计算公式。任务最坏响应时间为任务自身的最坏执行时间、优先级比该任务高的任务的抢占执行时间和故障后的卷回恢复时间三者之和^{[ 7]}。卷回恢复时间为任务最坏响应时间内可能发生的故障次数和最大故障恢复开销的乘积。该方法将故障检测开销和检查点设置开销合二为一,表示为 O _i,且忽略故障恢复开销;而故障的检测、恢复及检查点设置是实现容错必需的过程,且对于不同的任务这三者的开销各不相同,即使相同任务在不同的时间和负载条件下运行时,三者的开销也是不同的。其任务被检查点分成的段数 m _i是在任务只发生一次故障的情况下求得的,而在实际情况下任务发生多次故障是极有可能的。文献[7]中 R _i( T_E)的计算公式为

图1为基于卷回恢复技术的容错模型^{[ 8]},该模型为 n _i =6且发生故障次数 k=2时的执行情况。故障在任务 P₁的第2个和第6个检查点间隔的故障检测阶段被检测出来。基于该模型,对公式(1)进行扩展,在任务可能发生多次故障的情况下,考虑检查点设置开销、故障检测开销、故障恢复开销,得到任务 τ _i的最坏响应时间计算公式如式(2)所示:

	Figure Option View Download New Window
	图1 基于卷回恢复技术的容错模型Fig.1 Fault tolerant model based on checkpoint and rollback recovery

2 局部最优检查点间隔迭代求解
检查点的设置给任务执行带来了一定的额外开销,这主要包括无故障时的检查点设置开销和故障后的卷回恢复开销;故障检测也为正常运行的任务带来了额外开销。检查点卷回恢复的开销由检查点间隔决定,因此检查点间隔对于容错实时系统任务的可调度性有重要影响。不同配置的任务其故障发生次数是不相同的;相同的任务在不同的故障间隔 T_E下,故障发生次数也不相同,局部最优检查点数量也不同,因此其最坏响应时间 R _i也不同。 R _i可表示为局部最优检查点数量 n_local _i和故障发生次数 k的函数。文献[8]提出了任务独自执行情况下发生 k次故障时的响应时间计算公式(式(3)),并求解了该公式下任务局部最优检查点间隔的计算公式(式(4))。

任务执行过程中所发生的故障次数是由任务的最坏响应时间及系统的故障发生间隔 T_E决定的。在 T_E小于最坏响应时间时,任务可能会发生多次瞬时故障;但只要故障发生间隔 T_E满足大于ma ( C _i /n _i +O _i +α _i)和ma ( C _j /n _j +μ _j +α _j),检查点设置与卷回恢复技术就能确保任务执行完成。基于文献[8] k次故障情况下的局部最优检查点间隔求解公式,本文提出任务局部最优检查点间隔迭代求解算法Chekpt LN( T_E)如下:

算法从任务的最坏执行时间 C _i开始,按照公式(3)(4)迭代求解任务故障发生次数 k和局部最优检查点数量 n_local _i,最后算法收敛于唯一的故障发生次数 k,由 k得局部最优检查点数量 n_local _i。
算法收敛性证明:随着迭代次数的增加,故障发生次数 k增加,检查点数量 n_local _i增加,故障恢复间隔 C _i /n_local _i减小。相邻 k值间 R _i( n_local _i, k)的增量计算公式为: Δ=R _i( n_local _i_, _k+₁, k+1) -R _i( n_local _i_, _k, k)。将 n_local _i_, _k+₁ = 和 n_local _i_, _k = 带入 Δ,得 Δ=2 *( - ) * +μ _i +α _i。该 Δ函数是关于 k的递减函数。因此随着 k值的增加,两次 k值间的增量 Δ减小, R _i( n_local _i, k)能够趋于稳定值。即算法最终收敛于某一值,收敛处的 k值即为故障发生次数。因此用局部最优检查点间隔算法能够求出最终且唯一的故障发生次数和局部最优检查点数量。
在考虑故障检测、故障恢复和检查点设置开销且任务只发生一次故障的情况下,基于文献[7]方法的任务最优检查点间隔计算公式为

表1为在任务只发生一次故障情况下求得不同 T_E下的任务最坏响应时间,其检查点数量根据检查点间隔计算公式(5)求得;表2为在局部最优检查点间隔情况下求得的任务最坏响应时间。比较两表发现,基于一次故障情况下的检查点间隔时,任务在 T_E =61时是不可调度的;而在局部最优检查点间隔 <10,14,24 >时,任务在 T_E =26时是不可调度的。因此基于局部最优检查点间隔的任务可调度性优于基于一次故障情况下检查点间隔的任务可调度性。
表1
Table 1
表1(Table 1)
表1 基于一次故障情况下检查点间隔的任务最坏响应时间 Table 1 the task worst case response time based on the checkpoint interval under the single fault
任务 τ _i 属性优先级 p _i 任务集调度最坏响应时间
T _i D _i C _i n _i O _i α _i μ _i k R _i(61) R _i(62)
τ₁ 500 400 55 4 2 1 1 1 3 98.5 98.5
τ₂ 1000 800 80 5 2 1 1 1 2 234 234
τ₃ 1750 1750 160 5 4 3 3 1 1 1755 1717
表1 基于一次故障情况下检查点间隔的任务最坏响应时间 Table 1 the task worst case response time based on the checkpoint interval under the single fault
表2
Table 2
表2(Table 2)
表2 基于局部最优检查点间隔的任务最坏响应时间 Table 2 The task worst case response time based on the local optimum checkpoint interval
任务 τ _i 属性优先级 p _i 任务集调度最坏响应时间
T _i D _i C _i n_local _i O _i α _i μ _i k R _i( T_E)
R _i(27) τ₁ 500 400 55 10 2 1 1 5 3 122.5
τ₂ 1000 800 80 14 2 1 1 7 2 291.86
τ₃ 1750 1750 160 23 4 3 3 23 1 1747.17
R _i(26) τ₁ 500 400 55 10 2 1 1 5 3 122.5
τ₂ 1000 800 80 14 2 1 1 7 2 299.57
τ₃ 1750 1750 160 24 4 3 3 25 1 1786
表2 基于局部最优检查点间隔的任务最坏响应时间 Table 2 The task worst case response time based on the local optimum checkpoint interval

3 检查点间隔全局优化策略
局部最优检查点间隔是仅仅考虑任务独自执行时的最优检查点间隔。当存在优先级关系的多个任务并发执行时,高优先级的任务会周期性抢占低优先级任务的执行,因此每个任务的最坏响应时间较单独执行时的响应时间会有所变化,任务的故障发生次数也会有所变化。如图2所示:
图2
Fig.2
Figure Option
View Download New Window

图2 故障数量增加的情况Fig.2 The number of failure increasing
由于任务 P _j的周期性抢占,使任务 P _i的故障发生次数增加 4))。如图3所示:
图3
Fig.3
Figure Option
View Download New Window

图3 故障数量减少的情况Fig.3 The number of failure decreasing
由于任务 P _j的周期性抢占,使任务 P _i的故障发生次数减少。因此单任务局部最优检查点间隔并不是任务集的全局最优检查点间隔。检查点间隔全局优化(Checkpoint interval global optimization,CIGO)算法通过增加引起最大故障恢复开销任务的检查点数量来减小公式(2)的故障恢复开销,减少非最大故障恢复开销任务的检查点数量来减小公式(2)的高优先级任务抢占执行时间或任务自身执行时间,使不能满足截止时间要求的任务可以抢占其他任务空闲时间。因此通过检查点间隔全局优化能进一步提升系统可调度性。
在卷回恢复容错实时调度下,全局优化检查点间隔配置 n_global =_global1, n_global2,…, n_global _n >下系统可容忍的最小 T_E表示为 n_global的函数 T _e( n_global)。当 T_E小于 T _e( n_global)时,系统不可调度,此时不可调度任务的集合为: D( n_global) ={ τ _i∈ Γ|R _i( n_global, T _e( n_global) -1) >D _i}。根据可调度性的改善条件选择搜索路径,定义检查点数量增加和减少集合,可有效降低算法的搜索空间。
对于不可调度任务 τ _i,定义最大故障恢复开销任务集合max D( i) ={ τ _j∈ Γ|τ _j∈ hpe( i)∧( C _j /n_global _j +μ _j +α _j) =ma ( C _l /n_global _l +μ _l +α _l)},检查点数量增加的任务集合IncChekptSet( n_global, i)为:
IncChekptSet( n_global, i) =
{ τ _j∈ Γ|τ _j∈max D( i)∧
R _j( n_global, T _e( n_global) -1) _j}。
对于不可调度任务 τ _i,非最大故障恢复开销任务集合 Nmax D( i) ={ τ _j∈ Γ|τ _j∈ hpe( i)∧( C _j /n_global _j +μ _j +α _j) <ma ( C _l /n_global _l +μ _l +α _l)},检查点数量减小任务集合DecChekptSet( n_global, i)为
DecChekptSet( n_global, i) ={ τ _j∈ Γ|τ _j∈
Nmax D( i)∧ R _j( n_global,T _e(n_global)-1) _j∧
( C _j /n_global _j+μ _j+α _j)< (C_l/n _global_l+μ_l+α_l)}。
检查点间隔全局优化( CIGO)算法的伪代码如下所示。
(1) ← n _local
(2) T _E← T _e( ); ← T _E
(3) while TRUE
(4) n _local← ChekptLN( T _E)
(5) n _global← n _local
(6) if(∀ τ _i∈ Γ: R _i( n _global, T _E) _i)
(7) ← n _local
(8) ← T _E
(9) T _E← T _E←1
(10) if( T _E≤ ma ( C _j /n _global +O _j +α _j)) exit while
(11) if( T _E≤ ma ( C _k /n _global +μ _k +α _k)) exit while
(12) else
(13)∀ τ _i∈ D( n _global)
(14) if(( IncChekptSet( n _global, i) =⌀) &&( DecChekptSet( n _global, i) =⌀)) exit while
(15) if( IncChekptSelt( n _global, i)≠⌀)
(16) n _global← ma ( n _globalj ++)
(17) if( |IncChenkptSet( n _global, i) |=1) T _E← min( T _e( n _global), T _E)
(18) if( DecChekptSet( n _global, i)≠⌀)
(19) n _global← mi ( n _global --)
(20) if( |DecChekptSet( n _global, i) |=1) T _e← min( T _E( n _global), T _E)
(21) end if
(22) end while
(23) n _global←
(24) T _E←
CIGO算法确定系统中不可调度的任务后,根据上述讨论对任务的全局检查点间隔进行配置,得到全局优化检查点间隔 n_global。对已经采用 FP( Γ)分配优先级的任务集 Γ,CIGO算法从其局部最优检查点间隔 n_local及初始 T_E开始迭代搜索全局优化检查点间隔 n_global,其搜索过程分为两部分:
(1)验证部分:计算当前 T_E下各任务的局部最优检查点间隔 n_local并作为初始值赋给 n_global,然后求解各任务在当前 n_global时的最坏响应时间,并判断是否大于其截止时间来决定任务的可调度性。若系统可调度,则将当前 n_global与 T _E保存到与中,并尝试 n_global是否支持更小的 T _E(见CIGO算法的代码中的第(4)~(9))。
(2)搜索部分:若当前 n_global与 T_E下存在不可调度任务,则搜索新的全局优化检查点间隔。此时 D( n_global)≠∅,对于 D( n_global)中任意 τ _i,依次增加IncChekptSet( n_global, i)中各任务的检查点数量,并验证新 n_global的有效性,将满足条件的最大检查点数量赋给新的全局优化检查点间隔,最后取新 n_global下的 T _e( n_global)与当前 T_E中的较小者作为新的 T_E(见第16、17行);然后依次减小DecChekptSet( n_global, i)中各任务的检查点数量,并验证新 n_global的有效性,将满足条件的最小检查点数量赋给新的全局优化检查点间隔,最后取新 n_global下的 T _e( n_global)与当前 T_E中的较小者作为新的 T_E(见第19-20行)。当条件 T_E≤ma ( C _j /n _j +O _j +α _j)、 T_E≤ma ( C _k /n _k +μ _k +α _k)或((IncChekptSet( n_global, i) =∅) &&(DecChekptSet( n_global, i) =∅))满足时,无法找到更优的 n_global,算法终止(见第10、11、14行)。此时, 保存的值即为最优 n_global, 保存的值即为系统支持的最小 T_E,它表示系统的最大容错能力(见第23、24行)。
表3给出了实时周期性任务集 Γ={ τ₁, τ₂, τ₃}在全局优化检查点间隔情况下容错调度结果。由表2知,在局部最优检查点间隔 <10,14,23 >下,当 T_E =27时,各任务最坏响应时间均小于其截止时间,系统是可调度的。当 T_E =26时,此时局部最优检查点间隔为 <10,14,24 >,任务 τ₃最坏响应时间 R₃(26)超过了其截止时间 D₃,导致系统不可调度。由表3知在全局优化检查点间隔 <6,9,31 >下,当 T _E =23时,系统是可调度的。当 T_E =22时,在全局优化检查点间隔 <6,9,31 >下,任务 τ₃最坏响应时间 R₃(22)超过了其截止时间 D₃,系统是不可调度的。在局部最优检查点间隔下,系统容错能力 T _E为27;在全局优化检查点间隔下,系统容错能力 T_E为23,容错能力提升(27-23)/27×100%=14.81%。因此在局部最优检查点间隔下并不能获得最优的系统可调度性,检查点间隔全局优化能够进一步提升系统可调度性。
表3
Table 3
表3(Table 3)
表3 基于全局优化检查点间隔的任务最坏响应时间 Table 3 The task’s worst case response time based on the global optimization checkpoint interval
任务 τ _i 任务属性优先级 p _i 任务集调度最坏响应时间
T _i D _i C _i n_globa _li O _i α _i μ _i k R _i( T_E)
T_E =26 τ₁ 500 400 55 6 2 1 1 5 3 128.83
τ₂ 1000 800 80 8 2 1 1 7 2 333
τ₃ 1750 1750 160 27 4 3 3 25 1 1448
T_E =23 τ₁ 500 400 55 6 2 1 1 6 3 151.17
τ₂ 1000 800 80 9 2 1 1 8 2 358.67
τ₃ 1750 1750 160 31 4 3 3 32 1 1720.5
T_E =22 τ₁ 500 400 55 6 2 1 1 6 3 151.17
τ₂ 1000 800 80 9 2 1 1 9 2 369.83
τ₃ 1750 1750 160 31 4 3 3 35 1 1798.67
表3 基于全局优化检查点间隔的任务最坏响应时间 Table 3 The task’s worst case response time based on the global optimization checkpoint interval

4 仿真实验
为验证全局优化检查点间隔的高效性,本文用仿真试验模拟了810个任务集,每个任务集包含4个实时周期性任务(可扩展至包含任意数量任务的任务集)。试验计算机的配置为:Intel(R) E4500 CPU,2G内存,500G硬盘。参照文献[10]中的仿真方法,各任务的相关属性是随机产生的,但任务集 Γ中任务 τ _i的配置需满足以下约束条件:
(1)任务 τ _i的周期 T _i和截止时间 D _i服从区间[100,3000]上的均匀分布,且 D _i≤ T _i。
(2)任务 τ _i的处理器利用率 U _i =C _i /T _i服从均值为 U/4的指数分布,其中 U= U _i,表示任务集 Γ的处理器总利用率。为了保证 Γ的可调度性,0 .1≤ U≤0 .9, U每隔0 .01取一次值,为每个 U值分配10个任务集。

采用固定优先级调度算法RM对实时系统任务集 Γ进行卷回恢复容错实时调度。计算任务集 Γ分别在局部最优检查点间隔和全局优化检查点间隔下所能达到的最小故障发生间隔 LT_E和 GT_E。通过 ΔGLT_E =100% *(( GT_E -LT_E) /LT_E)来衡量检查点间隔全局优化算法相对于局部最优检查点间隔策略,系统容错能力的提升程度。
检查点间隔全局优化算法的系统容错能力提升情况如图4所示:
图4
Fig.4
Figure Option
View Download New Window

图4 系统容错能力提升情况Fig.4 Gain in system fault resilience
图4中横坐标表示任务集的处理器利用率 U,纵坐标表示系统容错能力的提升幅度 ΔGLT_E,图中黑点表示一个任务集的 ΔGLT_E值。由黑点的分布可知,当0 0 .6时, ΔGLT_E较小,其值在(0~20%)的范围内缓慢增长;当0 .6≤ U≤0 .9时, ΔGLT_E在高、低值区域内变化,变化范围较大,最高可达79.8%。呈现上述分布规律的原因是:当 U较低时,任务可以利用自身的空闲时间进行容错处理,此时 T_E可接近其下限,检查点间隔全局优化对 T_E的提升空间很小。当 U较高时,任务自身的空闲时间不足以完成瞬时故障容错, T_E较大,检查点间隔全局优化允许增加或减少任务的检查点数量以减小任务自身执行开销、抢占任务执行开销和故障恢复开销来满足自身截止时间要求,从而大幅降低 T_E。 ΔGLT_E值在有些任务配置下可能为零,此时全局检查点间隔优化并不能提升系统的容错能力,这主要是由于检查点数量的改变已经不能减小任务的抢占执行时间和最大故障恢复开销,或者不存在满足检查点间隔全局优化条件的任务。

5 结束语
由于计算机设备自身及恶劣环境的影响,实时系统面临严峻的瞬时故障影响,导致系统中任务不能按时完成,甚至发生灾难性后果。因此针对实时系统瞬时故障卷回恢复容错模型只能容忍任务执行过程中一次故障发生的情况,本文对实时系统的容错调度进行研究,提出了任务局部最优检查点间隔迭代求解算法,使任务能够容忍执行过程中多次瞬时故障的发生;进而提出了任务集检查点间隔全局优化算法,并通过任务的最坏响应时间来分析系统的可调度性。由仿真实验中 ΔGLT_E的变化情况可知,检查点间隔全局优化算法能够在局部最优检查点间隔策略的基础上进一步提升系统的容错能力。

The authors have declared that no competing interests exist.

参考文献

View Option

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1] Sha L, Abdelzaher T F, Arzén K E, et al. Real time scheduling theory: a historical perspective[J]. Real-Time Systems, 2004, 28(2-3): 101-155. [本文引用:1] [JCR: 0.55]

[2] Shivakumar P, Kistler M, Keckler S W, et al. Modeling the effect of technology trends on the soft error rate of combinational logic[C]∥Proc of the Int’1 Conference on Dependable Systems and Networks, 2002: 389-399. [本文引用:1]

[3] 傅忠传, 陈红松, 崔刚, 等. 处理器容错技术研究与展望[J]. 计算机研究与发展, 2007, 44(1): 154-160.
Fu Zhong-chuan, Chen Hong-song, Cui Gang, et al. Processor fault-tolerance technology research and prospect[J]. Journal of Computer Research and development, 2007: 44(1): 154-160. [本文引用:1]

[4] Clark J A, Pradhan D K. Fault injection: a method for validating computer system dependability[J]. IEEE Computer, 1995, 28(6): 47-56. [本文引用:1] [JCR: 2.039]

[5] Ziegler J F. IBM experiments in soft fails in computer electronics(1978-1994)[J]. IBM Journal Research Development, 1996, 40(1): 3-18. [本文引用:1] [JCR: 0.688]

[6] Zhang F, Burns A. Schedulability analysis for real-time systems with EDF scheduling[J]. IEEE Transactions on Computers, 2009, 58(9): 1250-1258. [本文引用:1] [JCR: 1.379]

[7] Punnekkat S, Burns A, Davis R. Analysis of checkpointing for real-time systems[J]. Real-time Systems, 2001, 20(1): 83-102. [本文引用:1] [JCR: 0.55]

[8] Paul Pop, Viacheslav Izosimov, Petru Eles, et al. Design optimization of time-and cost-constrained fault-tolerant embedded systems with checkpointing and replication[J]. IEEE Trans on Very Large Scale Integration Systems, 2009, 17(3): 389-402. [本文引用:1]

[9] Liu L C, Layland J W. Scheduling algorithms for multiprogramming in a hard real-time environment[J]. Journal of the ACM, 1973, 20(1): 46-61. [本文引用:1] [JCR: 2.37]

[10] 刘娴, 郭锐锋, 丁万夫. 基于优先级混合策略的回卷恢复容错实时系统的可调度[J]. 吉林大学学报: 工学版, 2012, 42(5): 1243-1250.
Liu Xian, Guo Rui-feng, Ding Wan-fu. Schedulability of rollback recovery fault-tolerant real-time system based on priority mixed strategy[J]. Journal of Jilin University(Engineering and Technology Edition), 2012, 42(5): 1243-1250 [本文引用:1] [CJCR: 0.701]

1

2004

0.55

0.0

. 2004, 28(2-3):101-155 DOI:10.1023/B:TIME.0000045315.61234.1e

Real time scheduling theory: a historical perspective

1.Department of Computer Science University of Illinois at Urbana Champaign USA 2.Department of Computer Science University of Virginia USA 3.Department of Automatic Control Lund Institute of Technology Sweden 4.Department of Computer Science Florida State University USA 5.Department of Computer Science University of York UK 6.Department of Computer Science University of Pavia Italy 7.Department of Statistics Carnegie Mellon University USA 8.Department of Computer Science University of Texas at Austin USA 

In this 25th year anniversary paper for the IEEE Real Time Systems Symposium, we review the key results in real-time scheduling theory and the historical events that led to the establishment of the current real-time computing infrastructure. We conclude this paper by looking at the challenges ahead of us.

... 引言实时系统的任务必须按时、可靠地执行完成,否则将导致灾难性后果^[1] ...

1

2002

0.0

0.0

... 由瞬时故障所导致的计算机可靠性已成为一个严峻的问题^[2,3,4] ...

1

2007

0.0

0.0

. 2007, 44(1):154-160

Processor fault-tolerance technology research and prospect

随着生产工艺的进步和硅形体尺寸的缩小,计算机系统面临着前所未有的瞬态故障影响,可信计算已经成为桌面级和嵌入式系统设计和应用的热点,其中以处理器的可信设计为核心.首先,从容错技术角度对处理器提出了一种新颖的、比较全面的分类方法;在此基础上,以处理器容错技术发展趋势为线索,对目前流行的处理器结构、微结构的容错机制和容错技术以及不同层次上有代表性的最新研究成果做了介绍和分析;最后,对处理器容错技术研究新趋势及其发展方向提出了意见和建议.

... 由瞬时故障所导致的计算机可靠性已成为一个严峻的问题^[2,3,4] ...

1

1995

2.039

0.0

... 由瞬时故障所导致的计算机可靠性已成为一个严峻的问题^[2,3,4] ...

1

1996

0.688

0.0

... 外界环境也可能导致晶体管PN结内部逻辑状态发生改变^[5] ...

1

2009

1.379

0.0

... 为了确保系统实时性和可靠性,需对任务进行可调度性分析^[6] ...

1

2001

0.55

0.0

. 2001, 20(1):83-102 DOI:10.1023/A:1026589200419

Analysis of checkpointing for real-time systems

1.M?lardalen University 2.University of York 

Predictable performance in the event of failuresis of paramount importance in most safety critical real-timesystems. Various hardware as well as software fault-toleranttechniques are employed towards this goal among which checkpointingis a relatively cost-effective scheme. Since checkpointing schemesdepend on time redundancy, they could affect the correctnessof the system by causing deadlines to be missed. This paper providesexact schedulability tests for fault tolerant task sets undera specified failure hypothesis and employing checkpointing toassist in fault recovery. The effects of checkpointing strategieson task response time are analysed and some insights for optimalcheckpointing are provided. The emphasis here is on utilizingthis analysis as an off-line design support tool.

... 任务最坏响应时间为任务自身的最坏执行时间、优先级比该任务高的任务的抢占执行时间和故障后的卷回恢复时间三者之和^[7] ...

1

2009

0.0

0.0

... 图1为基于卷回恢复技术的容错模型^[8],该模型为n_i=6且发生故障次数k=2时的执行情况 ...

1

1973

2.37

0.0

... _i到达后,系统采用固定优先级调度算法(如速率单调算法(Rate-Monotonic,RM)^[9])为其分配一个固定且唯一的优先级p_i#cod#x02208 ...

1

2012

0.0

0.701

. 2012, 42(5):1243-1250

Schedulability of rollback recovery fault-tolerant real-time system based on priority mixed strategy

1. Graduate University of Chinese Academy of Sciences, Beijing 100039, China; 2. Shenyang Institute of Computing Technology, Chinese Academy of Sciences, Shenyang 110168, China

A real-time system must guarantee the stringent requirements of real-time response and reliability. Taking account of the effects of errors, an investigation of the schedulability of fault-tolerant real-time systems was conducted based on the rollback recovery fault-tolerant model. A priority mixed strategy of fault-tolerance was proposed, and the computing formula of worst-case response time of a task under the new strategy is deduced. The new strategy allows the faulty task to execute at higher or lower priority levels. According to the schedulability analysis, an efficient priority assignment search algorithm (FTPCS_MS) was proposed. The algorithm reduces the search space of optimal fault-tolerant priority mixed assignment from O(nn) to O(n²). The simulation shows that the mixed strategy can improve system fault resilience efficiently.

实时系统具有严格的实时性及高度的可靠性要求。考虑到系统可能出错的情况,对回卷恢复容错模型下实时系统的可调度性进行了研究,提出了容错优先级混合策略,并推导出该策略下任务最坏响应时间的计算公式。结合系统的可调度性分析,提出了混合策略的优先级配置搜索算法(FTPCS_MS算法),该算法将最优容错优先级混合配置的搜索空间由O(nⁿ)降低为O(n²)。仿真实验表明,容错优先级混合策略能够在继承策略的基础上进一步提升系统的容错能力。

	Figure Option View Download New Window
	图2 故障数量增加的情况Fig.2 The number of failure increasing

	Figure Option View Download New Window
	图3 故障数量减少的情况Fig.3 The number of failure decreasing

	Figure Option View Download New Window
	图4 系统容错能力提升情况Fig.4 Gain in system fault resilience

[1]	Sha L, Abdelzaher T F, Arzén K E, et al. Real time scheduling theory: a historical perspective[J]. Real-Time Systems, 2004, 28(2-3): 101-155. [本文引用:1] [JCR: 0.55]
[2]	Shivakumar P, Kistler M, Keckler S W, et al. Modeling the effect of technology trends on the soft error rate of combinational logic[C]∥Proc of the Int’1 Conference on Dependable Systems and Networks, 2002: 389-399. [本文引用:1]
[3]	傅忠传, 陈红松, 崔刚, 等. 处理器容错技术研究与展望[J]. 计算机研究与发展, 2007, 44(1): 154-160. Fu Zhong-chuan, Chen Hong-song, Cui Gang, et al. Processor fault-tolerance technology research and prospect[J]. Journal of Computer Research and development, 2007: 44(1): 154-160. [本文引用:1]
[4]	Clark J A, Pradhan D K. Fault injection: a method for validating computer system dependability[J]. IEEE Computer, 1995, 28(6): 47-56. [本文引用:1] [JCR: 2.039]
[5]	Ziegler J F. IBM experiments in soft fails in computer electronics(1978-1994)[J]. IBM Journal Research Development, 1996, 40(1): 3-18. [本文引用:1] [JCR: 0.688]
[6]	Zhang F, Burns A. Schedulability analysis for real-time systems with EDF scheduling[J]. IEEE Transactions on Computers, 2009, 58(9): 1250-1258. [本文引用:1] [JCR: 1.379]
[7]	Punnekkat S, Burns A, Davis R. Analysis of checkpointing for real-time systems[J]. Real-time Systems, 2001, 20(1): 83-102. [本文引用:1] [JCR: 0.55]
[8]	Paul Pop, Viacheslav Izosimov, Petru Eles, et al. Design optimization of time-and cost-constrained fault-tolerant embedded systems with checkpointing and replication[J]. IEEE Trans on Very Large Scale Integration Systems, 2009, 17(3): 389-402. [本文引用:1]
[9]	Liu L C, Layland J W. Scheduling algorithms for multiprogramming in a hard real-time environment[J]. Journal of the ACM, 1973, 20(1): 46-61. [本文引用:1] [JCR: 2.37]
[10]	刘娴, 郭锐锋, 丁万夫. 基于优先级混合策略的回卷恢复容错实时系统的可调度[J]. 吉林大学学报: 工学版, 2012, 42(5): 1243-1250. Liu Xian, Guo Rui-feng, Ding Wan-fu. Schedulability of rollback recovery fault-tolerant real-time system based on priority mixed strategy[J]. Journal of Jilin University(Engineering and Technology Edition), 2012, 42(5): 1243-1250 [本文引用:1] [CJCR: 0.701]