一种多核实时容错系统中获取准确的最晚截止时间的方法

专利类型：发明专利 

语 言：中文 

申 请 号：CN201310739053.0 

申 请 日：20131227 

发 明 人：沙行勉吴剀劼崔晓通 

申 请 人：重庆大学 

申请人地址：400044 重庆市沙坪坝区沙正街174号 

公 开 日：20160525 

公 开 号：CN103699455B 

代 理 人：郭云 

代理机构：重庆市前沿专利事务所(普通合伙) 50211 

摘　　要：本发明提出了一种多核实时容错系统中获取准确的最晚截止时间的方法，包括如下步骤：根据给定的任务调度，在保持原有数据依赖的基础上，为调度在同一核上的相邻任务增加调度顺序依赖；增加两个执行时间为0的虚拟任务节点，使得在任务调度中，其中一个虚拟节点先于所有任务执行，另外一个后于所有任务执行；假设在任务执行过程中最多出现X个软错误，在原有调度的基础上通过出错任务在同一核上立即重新执行来实现容错，并确定任务集合的关键任务，获取任务集合的准确的最晚截止时间。若任务集合中包含N个任务，并且在执行过程中最多出现X个软错误，本发明能够在O(n^2)时间内确定任务集合的准确的最晚截止时间，保证容错，高效快速。 

主 权 项：一种多核实时容错系统中获取准确的最晚截止时间的方法，其特征在于，包括如下步骤：S1，根据多核系统的任务调度，在保持原有数据依赖的基础上，为在同一核上执行的相邻任务增加调度顺序依赖，建立新的有向无环图；S2，在新的有向无环图的基础上，增加两个虚拟任务节点，所述虚拟任务的执行时间为0，在以该有向无环图为模型的任务调度中，其中一个虚拟任务节点最先执行，另外一个虚拟任务节点最后执行；S3，假设在任务执行过程中最多出现X个软错误，在原有调度的基础上通过出错任务在同一核上的立即重新执行来实现容错，保证任务集合的正确执行，并确定任务集合的关键任务，获取任务集合的准确的最晚截止时间，具体包括如下步骤：S31，初始化每个任务的最早截止时间为所有任务都不发生错误时该任务的完成时间；初始化每个任务的最晚截止时间为0；S32，以一个任务节点I作为输入，该任务可以是任何一个节点；如果该任务节点I的最晚截止时间大于0，说明该任务节点已经被计算过，直接返回其最晚截止时间及其关键任务；如果该任务节点的父节点集合包含源节点，则该任务的关键任务是它本身，通过让该任务发生所有错误来获得该任务的最晚截止时间；否则进入下一步骤；S33、递归的遍历求解该任务节点I的所有父节点的最晚截止时间以及对应的关键任务；S34、假设任务I共有m个父节点，且它们的最晚截止时间分别为F(I)₁,F(I)₂,…,F(I)_m，分别在F(I)₁,F(I)₂,…,F(I)_m的基础上计算任务I的完成时间，分别为I₁,I₂,…,I_m，同时计算其他任务都不发生错误而只有任务I发生所有X个软错误的完成时间I₀，将I₀与I₁,I₂,…,I_m进行比较，选取最大的作为任务I的最晚截止时间，同时确定该任务节点I的关键任务是其本身还是S33中所求得的关键任务；S4，衡量任务集合的准确的最晚截止时间是否满足当前多核实时容错系统中的工作时限需求，如果满足，则退出，如果不满足，则调整调度策略，返回步骤S1。 

关 键 词： 

法律状态：授权 

IPC专利分类号：G06F11/07(2006.01)I