《分布式容错_DFT_系统原理及实现》由会员分享，可在线阅读，更多相关《分布式容错_DFT_系统原理及实现（6页珍藏版）》请在金锄头文库上搜索。
1、?年? 月重 庆大 学学 报第 ? 期 卜 分布式容错? ?系统原理及实现 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ! 陈以农 姚 荣 李庆商陈廷槐 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?计算机研究所? 【摘要】容错枝术是提高计算机系统可靠性的重要途径 。 要使 分布式系统进入极高 可靠性的应用领域 , 必须开发容错的分布式 系统 。 ? ? 是在分布 式 系统上实现容错计算的一种方法 , 它以系统的可靠性为设计目标 。 本文给出? ?原理及实现?原理的 模型试验 。 ? ? !? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
2、? ? ? ? ? ? ? ? ? ? !? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 一 、 引言 在计算机 的许多应用 ?例如 , 关键任务计算?中 , 要求计算机 在 内部发生 故障时 , 仍然 能够正确地 连续运行 。 这种超高可靠性计算机 的研究与设计 , 引出了所谓 “容错” 技术 。 本文引入 一种在分布式系统上实现容错计算的方法 , 并用实验验证了这一方 法的 可行 性 。 分布式系统是 由独 立的处理单元通过 互连而成 。 如图 ? 所示 。 系统的结构特征取决于互 连网络 。 这是一种用无 向 图来表
3、示的连接方案 , 其顶点对 应于处理单元 , 边对应于处理单元 间的通讯线路 。 分布式系统尽管定义多样 , 形式复杂 , 但都有三大共同特点 ? 模块性 、 并行性 和 自治 性 。 这三大特点使得分布式系统获得了一系列其它 系统无法比拟的优点 , 也正是这三大特点 使得分布容错计算 ? 成为可能 。 在? ? 容错管理中 , 使 每个关键任务在三个 处理单元上 同时执行 , 定期进行结果表决 。 本文于? 年?月 ?日收至 ,? ? ? 重 庆 大学学报 ? ? ? 年 表决中获得 的多数作为正确值 继 续运行?这种工作方式称为仿作? 。 当表 决 中发现错误 , 农 决程序作出故障记 录
4、 , 故障诊 断 程序找 出 引起错误的原 因 , 系统重组 程序 通过任务在 各 处理 单元间的一次重分配切换故障 。 二 、 ? ? 原理 ? ? 原理是在分布式系统 上实现 容错计算的一种方法 。 它以系统中关键任务的可靠计算 为目标 。 ? ? ? 故障模型 设分布式系统由独立 的处理单元。 ?, ? , ? ? 通过通讯线路 互连而成 。 ? ?从功能上把 系统的故障分为两类 ? ? ? 的单元故障是指 ?不 能正确执行其上的信息处理任务 。 ? ? 与 ? ? ?今? ? 的通讯故障是指 ? 与 ? 间不能正确完成信息交换 。 ? 。? 任务分配与时钟同步 进入系统的任务 , 按照
5、各种要求分配给各单元执行 。 系统中的关键任务分配在 三个单元 上仿作 。 设有任务? , ? ? , ? , 它们在单元 ? , ?, ? 。上 的一种分配如表 ?所 示 。 其中 , ? ?, ? ? 是三个单元上仿作的关键任务 。 表 ? 侧训 ? 仑 州下? “ 搏 ? ? ? ? 图 ? ? 。? 故障处理 故障处理是? ? 容错管理的核心 。 它包括故障隔离 、 屏蔽 、 检测 、 诊断 、 切换等过 程 。 ? ? 故障隔离 故障隔离是指防止 系统中的故障部件引起非故障部件不 正确的行为 。 ? 。 故障检测与屏蔽 ? ? 系统中 , 故障检测 与屏蔽是靠三中取二的表决来实现 的
6、 。 ? ? 故障诊断 当表决发现故障后 , 故障诊断过程将故障定位 。 ? ? 系统重组与故障切换 ?系统中 , 故障的切换是通过重组 , 即任务在各单元间的一次重分配来实现 。 在分布式系统中 , 各单元是独立 、 平等的 , 没有主从关系 , 这是实现故障隔离的先决条 件 。 系统中所有容错行为 , 必须通过多数表决后才能进行 。 在单故障的假设下 , 一组仿作单 ? ? 重庆大学学报 ? ? ?年 ? ? ? 软件 系统 ?一? 用软件实现所有容错管理 , 其组织如图 ? 所 示 。 在各软件模块中 , 模拟应 用软 件和容错管理软件作为系统的任务由任务调度统一管理 。 而任务调度 由
7、节拍脉冲引起 。 通 讯 管理 则作为中断服务程序由数据通讯中断所激活 。 ? ? ? 一? 软件系统 模拟应 用软件执行软件 ? 一管 容错管 理 通迅 司 ? 一在 落丽 一 正 时代同步故障诊断 ? 局部故障检测 ? 全局故障诊断 ? 图 ? ? 一 ? 软件配置 ? ? ? 时钟同步 仿作任务间的通讯 , 要求各仿作单元同步执行 , 以便其输出能按时送 去表 决 。 有很多时钟 同步算法能使时钟间的漂移不超过允许值 。 然而 , 在 高可靠 性的 容 错 系统 同步算法不仅要求有效 , 而且要求能容错 。 设 系统中有?个单元参加同步 , 对? 二 ? , ? , , ? , 单元?
8、?按 如下算法同步 ? ? ? ? ?, ? ? ? ? 单元 ? 送时钟 ? 到 ? ? ? ? ? ? ? ? ? ? ? ? ?读?的时钟?, ? ? ? ? 一? ? ? ? ? ? ? ? ? ? ? ! ,N一1O d,Od ; S, ep : C 三一贵 三 S 五 该算法的思想是 , 去掉故障时钟 (使S ,; d 的时钟 , 它的漂移超出了允许范围) 己的时钟调 整到所有非故障时钟的均值 。 显然 , 该时钟同步算法是容错的 。 将自 3.4 故障诊断 故障诊断分为局部诊断和 全局诊断 。 每个单元的局部诊断只检测 与自己相邻 的 两个单 第5期 陈以农等:分布式容错(D F
9、 T )系统原理及实现 3 9 元 , 其过程如下: 1) 单元u ; (i=o , l , 2 , 3 ) 发测 试数据d;给相邻单元 u:; 2) 单元u:检测相邻单元u j发来的测试数据d j , 若d j正确 , 则 t: 二, 0 , 后 则 t;j,1; 3) 将t*、发送到所有单元 。 全局诊断综合各单元局部诊断的结 果 , 找出故障部件 。 其过程如下 : 1) 接收各局部诊断结果构成故障症候 , 2 ) 根据 表2查出故障部件 。 表 2是 根据P 一 M 一 C 模型 (5)预先存入系统的 。 表 2 故障及拄候 万蕊丽二二不不二亘万舀下万 It , !t 。 t ,。 t
10、 。, It :。 t ,。 t 。 t 。 , 一 00000!000 单元 u。 0 1 0 0 0 1 X IX 单元 u, 0 0 1 0 】 1 I X X 01 单 元 u: 1 0 IX X ! 10 00 单兀 u。 一 火 1 ! 00 一 0 10 边(u n, u : ) 1 0 1 0 0 1 00 1 0 . 1 边(u l, u , ) 0 一 1 1 0 ! ; 0 0 00 边(u , u q ) 1 1 0 一 1 0 010 1 00 边(u3 , u 。 ) “ 0 “ O J ” 一 ” 多故障 其 它 *x 表示 可为。或1 。 3 . 5 实验结果
11、D FT一1硬件系统由四台28 0 单板机通过并行接口 P IO 连成环系统 。 软件系统由近2000条 28 0机 器指 令编成 。 DFT 一 l目前已全部调 试通过 并投入试验运行 , 实现 了关键任务的容错计算 。 容错能力 : 单元故障容错度为 1 通讯故障容错度为2 故障注入试验 : 任意制造一个故障D FT一 1 能容忍 (保证关键任务正确执行)并且诊 断出故障 (在无故障单元的数码管上显 示故障部件的编号) , 当仿作单元故障时 , 另一个非 仿作单元能 自动替换故障 , 实现系统重 组 。 四 、 结束语 DFT原 理适合于任意结构的分布式系统 。 系统的容错能力决定于系统的
12、连通 度 。 D厂 T系 统的可靠性可用马尔柯 夫过程中求得 。 设单元故障率为10 一, 通讯故障率为10b , 则可求得 重庆大学学报 1985年 系DF T一 1在1 0 小时连续工作中 , 失效的概率为2 .2x 工。 “. , 比单机系统可靠性提高了4 5 5倍 。 参考文献 (i) Siewiorek J . D. etal.: TheTheory an d p rae ti ee of Rel iable Sy ste扭 D esign , Di g it a l p ress . 1 98 2 . ( 2 )G o ldb er g J . e t a l . : SIFT : AP rova b l e F au lT o l e ran t C o m p u t er f or A i r - era f t Fli g h t C on t ro l . I n f or m a t i on p roeess i n g . 198 0 p p15 1一156 (3)金兰:分布式计算机系统总论 , 小型微型计算机系统1(198 4) , P l 一 6 。 ( 4 ) 陈廷槐 。 陈光熙 ; 数学系统的诊断与容错国防工业出版社 , 1981 。
