主/副版本模型中预分配容错实时调度算法
发布时间：2022-01-21 23:07
实时系统中任务的超时完成可能导致灾难性后果,因此要求系统具备容错处理能力,以保证系统出错后的实时性及可靠性.主/副版本模型是提高实时系统容错能力的有效技术.传统的容错实时调度算法通过为副版本预留处理器时间来实现软件容错,为副版本预留的处理器时间在系统运行过程中需动态调整,增加了系统的容错调度开销.提出一种基于res-backwards-RM预分配子算法的容错实时调度算法BCE*,通过限制预分配过程中高优先级任务的抢占条件,在不影响系统可调度性的同时可以有效避免副版本预留时间的动态调整,降低系统的容错调度开销.仿真实验验证了BCE*算法的可行性及有效性,且在系统出错概率及主版本负载较低的环境下,BCE*算法对系统容错调度开销的优化效果更显著.
【文章来源】：计算机研究与发展. 2015,52(03)北大核心EICSCD
【文章页数】：9 页
【部分图文】：
图１ｂａｃｋｗａｒｄｓ－ＲＭ确定的Γ１的通知时间时序Ｆｉｇ．１ＴｈｅｎｏｔｉｆｉｃａｔｉｏｎｔｉｍｅｓｏｆΓ１ｃａｌｃｕｌａｔｅｄｂｙｂａｃｋｗａｒｄｓ－ＲＭ．
Ｆｉｇ．２Ｔｈｅｒｕｎ－ｔｉｍｅｓｃｈｅｄｕｌｉｎｇｏｆΓ１ｗｉｔｈｔｈｅｐｒｅ－ａｌｌｏｃａｔｉｏｎｏｆｂａｃｋｗａｒｄｓ－ＲＭ．图２基于ｂａｃｋｗａｒｄｓ－ＲＭ预分配的Γ１的运行时调度２．２预留时间的调整开销定义２．ＢＣＥ调度过程中，在时刻ｔ存在副版本预留时间的动态调整，当且仅当以下２个条件同时成立：１）存在Ｎｉｊ＞ｔ且Ｐｉｊ在时刻ｔ正确完成；２）存在Ｐｍｎ（ｐｒｉｏｍ＜ｐｒｉｏｉ）在时刻ｔ尚未完成，且Ａｍｎ与Ａｉｊ的预留时间冲突．由定义１，２可知，预留时间的动态调整仅可能发生在存在预留时间冲突的副版本上．Ｐｉｊ完成时，需从所有Ａｍｎ（ｐｒｉｏｍ＜ｐｒｉｏｉ）中查找到与Ａｉｊ冲突的副版本，此过程的时间开销为Ｏ（ｎ）．最坏情况下，在［０，Ｔ］内副版本预留时间的动态调整开销为Ｏ（ｎ×Ｎ），其中Ｎ为［０，Ｔ］内的作业总数．在［０，Ｔ］内可能发生的最大调整次数为反向调度过程中副版本的总抢占次数，表示为Ｍｍａｘ．实际调整次数受主版本的完成情况影响，当所有主版本均成功完成时，调整次数取最大值．随机生成１０００组任务集，每组任务集包含的任务个数ｎ在［２，２０］内取值，每个任务的周期Ｔｉ在［５，３００］内随机取值，副版本执行时间ａｉ在［１，Ｔｉ］内随机取值后乘以ＵＡ∑ｎｉ＝１ａｉＴｉ，以控制任务集的副版本处理器利用率ＵＡ为（０，１］内的指定数值，所有随机数均服从均匀分布．对任务集
－ＲＭ调度，由于每组任务集的计划周期不同，统计每组任务集在其计划周期内的抢占率ＭＰｍａｘ＝ＭｍａｘＴ，分别计算ＵＡ∈（０，０．１］，（０．１，０．２］，…，（０．９，１］时的平均ＭＰｍａｘ，结果如图３所示．从图３可看出，随着副版本处理器利用率增大，ＭＰｍａｘ呈上升趋势，特别是在高ＵＡ情况下，ＭＰｍａｘ加剧上升．预留时间调整次数过多将造成系统运行Ｆｉｇ．３ＴｈｅｉｎｆｌｕｅｎｃｅｏｆＭＰｍａｘｏｎＵＡ．图３ＵＡ对ＭＰｍａｘ的影响时的调度开销过大，进而影响任务的调度．根据定义２的条件２），为了减少预留时间的动态调整操作，对ｂａｃｋｗａｒｄｓ－ＲＭ算法进行改进，在副版本的反向调度过程中，设置新的任务抢占执行规则，提出ｒｅｓ－ｂａｃｋｗａｒｄｓ－ＲＭ预分配算法，并基于ｒｅｓ－ｂａｃｋｗａｒｄｓ－ＲＭ子算法提出容错实时调度算法ＢＣＥ＊．３ｒｅｓ－ｂａｃｋｗａｒｄｓ－ＲＭ算法预分配算法ｒｅｓ－ｂａｃｋｗａｒｄｓ－ＲＭ根据任务周期为Γ中任务τｉ分配优先级ｐｒｉｏ＊ｉ∈｛１，２，…，ｎ｝，任务周期越短，其优先级越高．ｒｅｓ－ｂａｃｋｗａｒｄｓ－ＲＭ从时刻Ｔ到０，对Γ中副版本进行反向调度，副版本Ａｉｊ的反向就绪时间ＢＲｉｊ＝Ｄｉｊ，反向截止时限ＢＤｉｊ＝Ｒｉｊ．反向调度过程中，若已就绪的副版本之间满足定义１中的冲突条件，则仅当高优先级任务的推迟执行将导致其超时完成时，高优先级任务才可抢占低优先级任务执行，否则优先执行低优先级任务．ｒ
【参考文献】：
期刊论文
[1]硬实时系统中基于软件容错模型的容错调度算法[J]. 丁万夫,郭锐锋,秦承刚,郭凤钊. 计算机研究与发展. 2011(04)
[2]容错多处理机中一种高效的实时调度算法(英文)[J]. 王健,孙建伶,王新宇,杨小虎,王申康,陈俊波. 软件学报. 2009(10)
[3]软件容错模型中的容错实时调度算法[J]. 刘东,张春元,李瑞,黄影,李毅. 计算机研究与发展. 2007(09)
本文编号：3601127
【文章来源】：计算机研究与发展. 2015,52(03)北大核心EICSCD
【文章页数】：9 页
【部分图文】：
图１ｂａｃｋｗａｒｄｓ－ＲＭ确定的Γ１的通知时间时序Ｆｉｇ．１ＴｈｅｎｏｔｉｆｉｃａｔｉｏｎｔｉｍｅｓｏｆΓ１ｃａｌｃｕｌａｔｅｄｂｙｂａｃｋｗａｒｄｓ－ＲＭ．
Ｆｉｇ．２Ｔｈｅｒｕｎ－ｔｉｍｅｓｃｈｅｄｕｌｉｎｇｏｆΓ１ｗｉｔｈｔｈｅｐｒｅ－ａｌｌｏｃａｔｉｏｎｏｆｂａｃｋｗａｒｄｓ－ＲＭ．图２基于ｂａｃｋｗａｒｄｓ－ＲＭ预分配的Γ１的运行时调度２．２预留时间的调整开销定义２．ＢＣＥ调度过程中，在时刻ｔ存在副版本预留时间的动态调整，当且仅当以下２个条件同时成立：１）存在Ｎｉｊ＞ｔ且Ｐｉｊ在时刻ｔ正确完成；２）存在Ｐｍｎ（ｐｒｉｏｍ＜ｐｒｉｏｉ）在时刻ｔ尚未完成，且Ａｍｎ与Ａｉｊ的预留时间冲突．由定义１，２可知，预留时间的动态调整仅可能发生在存在预留时间冲突的副版本上．Ｐｉｊ完成时，需从所有Ａｍｎ（ｐｒｉｏｍ＜ｐｒｉｏｉ）中查找到与Ａｉｊ冲突的副版本，此过程的时间开销为Ｏ（ｎ）．最坏情况下，在［０，Ｔ］内副版本预留时间的动态调整开销为Ｏ（ｎ×Ｎ），其中Ｎ为［０，Ｔ］内的作业总数．在［０，Ｔ］内可能发生的最大调整次数为反向调度过程中副版本的总抢占次数，表示为Ｍｍａｘ．实际调整次数受主版本的完成情况影响，当所有主版本均成功完成时，调整次数取最大值．随机生成１０００组任务集，每组任务集包含的任务个数ｎ在［２，２０］内取值，每个任务的周期Ｔｉ在［５，３００］内随机取值，副版本执行时间ａｉ在［１，Ｔｉ］内随机取值后乘以ＵＡ∑ｎｉ＝１ａｉＴｉ，以控制任务集的副版本处理器利用率ＵＡ为（０，１］内的指定数值，所有随机数均服从均匀分布．对任务集
－ＲＭ调度，由于每组任务集的计划周期不同，统计每组任务集在其计划周期内的抢占率ＭＰｍａｘ＝ＭｍａｘＴ，分别计算ＵＡ∈（０，０．１］，（０．１，０．２］，…，（０．９，１］时的平均ＭＰｍａｘ，结果如图３所示．从图３可看出，随着副版本处理器利用率增大，ＭＰｍａｘ呈上升趋势，特别是在高ＵＡ情况下，ＭＰｍａｘ加剧上升．预留时间调整次数过多将造成系统运行Ｆｉｇ．３ＴｈｅｉｎｆｌｕｅｎｃｅｏｆＭＰｍａｘｏｎＵＡ．图３ＵＡ对ＭＰｍａｘ的影响时的调度开销过大，进而影响任务的调度．根据定义２的条件２），为了减少预留时间的动态调整操作，对ｂａｃｋｗａｒｄｓ－ＲＭ算法进行改进，在副版本的反向调度过程中，设置新的任务抢占执行规则，提出ｒｅｓ－ｂａｃｋｗａｒｄｓ－ＲＭ预分配算法，并基于ｒｅｓ－ｂａｃｋｗａｒｄｓ－ＲＭ子算法提出容错实时调度算法ＢＣＥ＊．３ｒｅｓ－ｂａｃｋｗａｒｄｓ－ＲＭ算法预分配算法ｒｅｓ－ｂａｃｋｗａｒｄｓ－ＲＭ根据任务周期为Γ中任务τｉ分配优先级ｐｒｉｏ＊ｉ∈｛１，２，…，ｎ｝，任务周期越短，其优先级越高．ｒｅｓ－ｂａｃｋｗａｒｄｓ－ＲＭ从时刻Ｔ到０，对Γ中副版本进行反向调度，副版本Ａｉｊ的反向就绪时间ＢＲｉｊ＝Ｄｉｊ，反向截止时限ＢＤｉｊ＝Ｒｉｊ．反向调度过程中，若已就绪的副版本之间满足定义１中的冲突条件，则仅当高优先级任务的推迟执行将导致其超时完成时，高优先级任务才可抢占低优先级任务执行，否则优先执行低优先级任务．ｒ
【参考文献】：
期刊论文
[1]硬实时系统中基于软件容错模型的容错调度算法[J]. 丁万夫,郭锐锋,秦承刚,郭凤钊. 计算机研究与发展. 2011(04)
[2]容错多处理机中一种高效的实时调度算法(英文)[J]. 王健,孙建伶,王新宇,杨小虎,王申康,陈俊波. 软件学报. 2009(10)
[3]软件容错模型中的容错实时调度算法[J]. 刘东,张春元,李瑞,黄影,李毅. 计算机研究与发展. 2007(09)
本文编号：3601127
本文链接：https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/3601127.html
