您好、欢迎来到现金彩票网!
当前位置:2019欢乐棋牌 > 执行开销 >

基于依赖跟踪和消息计数的回卷恢复容错技术研究一旦出现故障便使

发布时间:2019-06-28 08:46 来源:未知 编辑:admin

  基于依赖跟踪和消息计数的回卷恢复容错技术研究一旦出现故障便使用保存的检查点信息将故障进程重生 然后重演日志消息 将进程状态前滚。设 表示做检查点的时间开销 三表示做消息日志的时间开销 表示进程重启的时间开销 表示进程前滚的时间开销。因此公式 可以细化为 系统的正常执行效率会因回卷恢复机制的引入而有所

  基于依赖跟踪和消息计数的回卷恢复容错技术研究一旦出现故障便使用保存的检查点信息将故障进程重生 然后重演日志消息 将进程状态前滚。设 表示做检查点的时间开销 三表示做消息日志的时间开销 表示进程重启的时间开销 表示进程前滚的时间开销。因此公式 可以细化为 系统的正常执行效率会因回卷恢复机制的引入而有所降低这也是容错所要必须付出的代价。开销率表征的就是引入回卷恢复机制后的系统效率的降低程度【 。正常情况下 用户都会选择开销率小的回卷恢复协议。由公式 可知开销主要包括检查点开销、消息日志开销、回卷开销、前滚开销四个方面。当然如果系统只采用了检查点协议 那就不会存在消息日志开销。检查点开销的主要来源有如下几个方面 检查点的存储开销 检查点协议中需要将进程的状态信息保存在存储介质中以生成检查点文件。存储开销与检查点的数据量大小及存储介质的访问速度有关。 进程间的阻塞开销 基于阻塞的检查点协议在做检查点时需要阻塞进程的正常执行并使其停止发送消息。如果采用非阻塞的检查点协议就会降低或消除这种开销。 控制消息开销 在协同检查点协议的检查点设置过程中 各个进程之间需要通过发送和接收相关的控制消息来确保生成一致的全局检查点。 附带消息开销 在某些检查点协议中 有时需要将检查点的相关信息附带在应用消息上以实现回卷进程数的最小化或者强迫实现检查点的一致性等。附带信息可能与进程数量成比例 也可能是固定大小的。消息日志开销主要来源有以下几个方面 日志的存储开销 消息日志协议需要将相关的应用消息记录到存储介质中以生成消息日志。日志存储开销与消息的频率、消息的数据量大小以及存储介质的访问速度有关。 依赖跟踪开销 在某些消息日志协议中 需要计算、传递和保存消息定子 以记录进程间的依赖关系。依赖跟踪开销可细分为计算开销和存储开销两部分。计算开销包括计算需要传递的依赖关系以及维护依赖关系等 传输开销表示传输应用消息上附带的依赖关系信息所带来的开销。重启开销是指故障发生后 重启进程并使用检查点数据来设置进程状态所花费的开销。前滚开销是指进程从重启后的检查点状态到恢复至故障发生时状态所花费的开销。工程硕士学位论文 降低回卷恢复开销的途径在许多实际应用中 程序计算结果的响应时间是一个关键的性能指标 因此降低回卷恢复开销、提高故障恢复速度具有重大意义。降低系统回卷开销可以从单进程级和系统级两个层次进行研究 单进程级主要考虑单个进程场景下降低回卷恢复开销的途径 系统级主要考虑分布式并行场景下降低进程间协同开销的途径。 降低单进程级的回卷恢复开销在单进程级 直接减少检查点和消息日志存储的开销 是从实现角度来说的一条行之有效的方法。降低每一个检查点的开销 可以减少系统的无故障执行时间 进而降低故障发生的概率 提高系统的有效性。在单进程级降低回卷恢复开销主要有如下途径 优化检查点时间间隔【 】检查点时间间隔是一个能够直接影响系统运行效率的重要参数。一方面 如果检查点时间间隔设置得小 那么在系统出现故障时损失的计算量就少 但是它会增加系统的无故障执行开销 拉长系统的执行时间 从而增加了故障产生的概率 另一方面 如果检查点时间间隔设置得大 那么系统无故障执行时间就少 有利于系统执行的尽旱完成 但是一旦出现故障其计算量的损失会比较大。因此可以根据应用程序的特征、系统失效概率以及系统的节点数量等因素进行分析 以确定最佳的检查点时间间隔 提高系统的利用率。 检查点压缩方法【 】目前存在许多的数据压缩算法 在检查点设置时 使用压缩方法可以直接减小检查点中保存的数据量 从而降低检查点开销。但有时压缩方法不一定有效 因为压缩方法的使用会引入相应时间开销 如果用于压缩的时间大于因数据量减少而节约的时间 那么使用压缩方法就毫无意义。因此在使用压缩方法前必须根据应用的特征 权衡压缩后减少的数据量与压缩花费的时间之间效益。 增量式检查点方法【 】由于保存检查点的数据是造成检查点开销的主要来源 因此减少检查点的数据量是降低回卷恢复开销的有效方法。增量式检查点方法不重复保存上一次检查点中己保存且没修改的数据 只对修改了的数据进行保存。它利用页式内存管理方式来识别并排除“只读”的内存页。在程序运行时 系统需要记录下被程序修改过的内存页 做检查点时 系统不需要保存全部的程序空间 只需保存被修改过的内存页。在许多应用场景下 增量式检查点技术都能够有效的减少检查点的数据量 降低检查点的时间开销。 程序员参与的排除方法【 】基于依赖跟踪和消息计数的回卷恢复容错技术研究增量式的检查点方法对程序员不透明任何的改动都会导致整个单元的重新保存 因此有效性不太高。对于一些与故障无关的数据 比如代码段、常量数据段以某些使用后不用再调用的临时变量等 此类情况可以通过程序员在分析程序结构的基础上 使用人工方法来排除这一部分数据。另外对于某些特殊的实时容错应用 程序员可以根据程序语义来确定哪些数据需要保存 哪些数据不用保存 从而减少检查点的数据量 加快检查点设置和进程重启的速度。 检查点缓存方法【 在检查点缓存方法中应用程序在做检查点的同时依旧能够继续执行。在设置检查点时 它不会直接将程序状态数据保存到稳定存储介质 而是先将状态数据复制到缓冲区 然后让程序继续执行 同时将缓冲区中的状态数据保存至稳定存储介质。 写时复制方法【 在检查点缓存方法中存在缓冲开销大以及对缓冲区要求大的缺点。采用写时复制方法可以避免这些缺点。做检查点时 为了减少缓冲区中的数据量 只需将程序修改的内存页面复制到缓冲区中 而不需要将所有程序状态数据复制到缓冲区中。而后在程序正常执行的同时 将程序状态中的其它内容和缓冲区中的数据保存到稳定存储介质中。 重启前滚并发执行方法【 】重启前滚并发执行方法是通过跟踪内存页面访问顺序来降低进程重启开销的策略。它是基于存储访问带宽以及检查点的数据量来设置时间窗口 在检查点设置完成之后 通过内存页面访问的信号机制来跟踪并记录应用程序对内存页面的访问顺序。在故障后的重启恢复过程中 按照记录的内存页面访问顺序读取检查点 这样就克服了进程状态重启完成后才能前滚的限制 实现了重启与前滚的并发执行。 两级检查点方法【 】针对不同的故障类型 两级检查点方法中采用了两类不同的检查点。第一类是本地检查点 它由节点自己保存 处理节点上发生的偶然性故障 第二类是稳定检查点 它保存在整个系统的稳定存储介质中 用于节点在发生永久性故障时 转移到其它节点上进行恢复。根据偶然性故障发生概率高 而永久性故障发生概率低这一特征 因此系统设置本地检查点频率远大于设置稳定检查点的频率。由此可见 两级检查点方法能够灵活处理两类故障 同时能够有效降低系统的整体开销。 降低系统级的回卷恢复开销在系统级中 降低回卷恢复开销的一个主要方面是如何减少进程之间协同所引发的开销 即进程之间构建一致性全局进程状所带来的开销。这类开销包括传工程硕士学位论文递协议控制消息的开销、消息日志开销、无用检查点开销等。对于不同的回卷恢复技术 其降低开销的策略有所差别。对于非协同检查点协议 主要是减少无用检查点的产生 避免回卷传播引发恶性循环 对于协同检查点协议 可以采用非阻塞的协同技术 同时要减少设置检查点过程中传递的协同消息数量 对于通信引导检查点协议 要减少附带消息的数据量和强制检查点数量 对于基于消息日志的回卷恢复协议 主要是减少需要记录的消息的数据量、减少应用消息上附带的控制消息和依赖关系的数据量、以及减少进程间的阻塞时间。在具体的应用场景下 为了实现回卷性能优化 通常会将多种回卷恢复算法相结合使用。例如将通信引导检查点技术加入到非协同检查点协议中来避免不一致的检查点产生。 回卷恢复技术的应用作为回卷恢复的核心技术 检查点技术是实现容错计算 提高应用系统可靠性的常用策略。除了应用于容错计算之外 它还在分布式计算的其它领域中得到了广泛的应用。这些应用包括如下几个方面 软件调试【 在分布式应用程序中 出现错误后再次运行时经常会遇到难以确定故障原因的情况 这是由于分布式程序中通信延迟等不确定性因素所导致的。利用检查点技术在适当的时候对进程状态做检查点 一旦出现错误 则从检查点状态重新执行 以精确恢复到故障前的状态 提高错误重现的概率 解决程序中存在的漏洞。 进程迁移 。利用检查点技术 某台计算机可以将自己进程的执行状态保存为检查点文件 然后传输给另一台计算机。接收到检查点文件的计算机恢复相应的进程状态 从而实现进程的迁移。进程迁移技术广泛应用于实现分布式系统中的负载均衡 以此提高整个系统的利用率。 作业交换【” 处理机在执行当前应用程序时 如果有紧急作业需要立马处理 那么它会把当前程序的执行状态和执行环境数据保存在检查点文件中 然后中止其执行转而处理紧急作业。待紧急作业处理完成之后 处理机会重新读取检查点文件 恢复原来应用程序的执行状态和执行环境 使原来的应用程序继续执行。 避免边界条件引发的故障【 】分布式系统中存在许多不确定性的因素导致进程的执行具有不可预知性。有一些故障只有在满足某些特定的边界条件时才会发生 遇到这样的故障可以将所有进程回卷到前面的一个全局检查点状态 再重新执行。由于边界条件发生的概基于依赖跟踪和消息计数的回卷恢复容错技术研究率小 重新执行时程序会避开原来的执行路径 从而避免故障的重现。除此之外 回卷恢复技术还应用在了许多其它方面 例如应用于移动代理技术、快速恢复的实时系统、时间扭曲模拟系统等。 本章小结本章首先介绍了回卷恢复技术的基本概念 接着分别对基于检查点的回卷恢复协议和基于消息日志的回卷恢复协议进行了具体介绍 并对六种回卷恢复协议的各自特征进行了对比。然后具体分析了回卷恢复开销的主要来源以及从不同层面降低回卷恢复开销的途径。最后介绍了回卷恢复技术在其它领域的应用。第 章基于依赖跟踪的轻量级消息日志协议 引言消息日志技术作为对检查点技术的一种补充 它在回卷恢复容错技术中应用广泛。因为消息日志技术的引入可以增加进程做检查点的自主度 降低检查点的开销 同时在故障恢复时它能够前移恢复线 减少需要回卷的进程数 减少丢失的计算量。当然消息日志技术在带来诸多优点的同时 也带来了大量额外开销。在悲观消息日志中 进程需要以同步的方式在发送端或接收端将消息保存到稳定存储介质 这样使得进程的正常执行过程中增加了大量的开销 特别当系统的通信频繁时 这些开销可能是难以忍受的。为了降低悲观消息日志协议的开销 乐观消息日志协议和因果消息日志协议中引入了依赖跟踪方法。进程之间的消息传递导致了进程之间的相互依赖关系 接收方的消息提交状态依赖于发送方的相应发送状态 如果在消息的传递过程 发送方在发送消息时将自己的依赖关系传递给接收方 成为接收方依赖关系的组成部分 然后接收方在发送自己的消息时也同样将自己的依赖关系传递出去 从而使得每一个进程都知道自己的当前状态直接或间接的依赖对象 这个过程就是依赖跟踪。依赖关系从本质上说是由于消息提交事件所引发的 对依赖关系进行跟踪 也就是对消息进行跟踪 因此依赖跟踪和消息跟踪表示的是相同的含义。通过依赖跟踪方法 保证进程之间消息传递的一致性不必通过严格同步保存消息的方式来实现。依赖跟踪方法同样也会带来相应的开销 这此开销包括计算开销、传递开销和存储开销三部分。计算开销就是计算和表达依赖关系所带来的开销 传递开销就将依赖关系在进程间传递所带来的开销 存储开销是接收方在保存依赖关系时需要花费的时间开销和空间开销。现有的依赖跟踪方法普遍存在开销大的问题 其根源在于引入了同步约束 附加传输和存储的数据量大【 。本章利用运行时的消息传递特性 采用附带策略 提出一种基于依赖跟踪的轻量级消息日志协议 简称协议 系统模型分布式计算由个分布于计算结点上的进程并行执行 记为 进程之间相互传递消息彼此协同完成计算任务。程序满足 分段确定性假设【 。消息传输信道是可靠地 但存在有限却不可预计的传输时延。基于依赖跟踪和消息计数的回卷恢复容错技术研究另外 系统中产生的故障均为失效 故障 一旦故障发生进程执行立马中断 进程状态丢失。在基于日志的回卷恢复模型中 每个进程状态的变迁都是由消息所驱动的 假设进程 在整个计算过程中从其它进程 也包括自己 接收并提交的消息序列分别为朋 。进程的初始状态为三 提交消息聊 后变迁为状态 。进程尸 在从状态三 变迁到状态 的过程中可能给其它进程发送消息。设进程最近所做的检查点为状态三 然后依次提交消息朋 假定进程在提交 。的过程中发生故障。那么故障后的恢复过程为 使用检查点恢复到状态三是 然后依次重演消息 以此实现故障恢复。在回卷恢复中为了保证进程 实现严格一致的恢复 日志中既要记录进程提交消息的顺序 还要记录消息本身【 引。在故障后的恢复中 除了做检查点和消息日志外 还要标识重复性消息。假设进程尸 在提交消息 的过程中给进程尸 发送了消息 那么进程 在其故障恢复过程中还会给进程尸 重新发送消息聊一 出现消息重复现象。回卷恢复中 必须标识重复消息聊 并将其丢弃 保证进程 不重复提交同一消息。 协议的基本思想 依赖跟踪方法在基于消息日志的回卷恢复协议中 每个进程在正常运行时独立地做检查点 同时做消息日志 将进程间传递的消息保存到故障影响不到的稳定存储介质上。一旦发生故障 故障进程回卷到其检查点状态 然后通过重演消息日志来前滚进程状态。在这个回卷恢复容错模型中 除了进程检查点、消息日志、进程重生、消息重演这四个基本组件外 消息跟踪也是其中的核心内容 。。基于消息日志的回卷恢复协议中 可以将依赖跟踪方法划分为直接依赖跟踪 和间接依赖跟踪 两种类型【 】。在直接依赖跟踪中 发送方在发送消息时将自己的状态间隔标识附带在消息上发送给接收方 接收方只记录产生该接收消息的状态间隔标识 在回卷恢复时 所有的直接依赖信息可以组合成全局的依赖信息。在间接消息依赖跟踪中 不仅要跟踪直接相关的依赖信息 还需要跟踪间接相关的依赖信息。如果说直接依赖跟踪是记录自己的“父辈”信息 那间接依赖跟踪可以看作是记录自己的“祖辈”信息 可以是全部也可以是部分 因此可以把直接依赖跟踪看成是间接依赖跟踪的一个特例。典型的间接依赖跟踪有基于向量的依赖跟踪方法 在该方法中每一个进程 都会维护一个依赖关系向量 其中肛】是进程 自己的当前进程状态索工程硕士学位论文引 表示进程依赖于进程尸 的最大进程状态索引垆 。基于向量的间接依赖跟踪在消息传递时要附带依赖关系向量 所以它会带来较高的无故障执行开销 但是具有输出提交和回卷恢复速度快的优点。因果依赖跟踪也是一类间接依赖跟踪方法 它有两种不同的表现形式。第一种是利用先行图 】来维护因果依赖跟踪关系 先行图中保存了影响进程每一个状态的全部历史非确定性事件。先行图中的每一个节点表示一个先于 某一进程状态的非确定性事件 每一条边表示事件之间的先后依赖关系。在系统无故障执行过程中 发送进程需要将自己的先行图附带在消息上发送给接收方 接收方会将缓存这些先行图 通过增量先行图的方式能够有效的降低存储和传递先行图的开销。使用先行图来维护依赖关系最大的缺点就是实现比较复杂。第二种方法是使用消息的确定因子【 】来维护因果依赖跟踪关系 消息的确定因子通常表达为四元组 其中标识消息的发送进程号 标识消息在发送端的发送序号 标识消息的接收进程号 标识消息在接收端的接收序号 该方法的一个经典实现是 算法【 。该算法中设置了一个参数 最大容忍同时失效进程数 表示 个进程的并行系统中能够容忍同时出错的故障进程的最大数量 因此该算法中将每一个消息的确定因子和消息本身都放在厂 个不同节点上进行暂存 以保证故障后能正确恢复。该算法中消息的确定因子和消息本身都不需要在稳定存储介质中保存 但是每一个消息的确定因子和消息本身都需要在暂存中保存 这也是相当耗费存储的。改进的依赖跟踪方法消息传递使得进程之间相互关联、彼此依赖 在故障恢复中存在全局状态一致性问题。依赖跟踪方法与协同检查点方法、消息日志方法一样 也是解决进程之间状态不一致的方法。前面我们已经介绍和分析了依赖跟踪的基本方法以及它们各自的特征 开销大是它们普遍存在问题 基于向量的依赖跟踪方法传输开销大 基于先行图的方法计算复杂 基于确定因子的 方法存储开销大。为了降低依赖跟踪的开销 我们从开销的来源入手进行分析。 依赖关系的计算开销如果要计算依赖关系 必须先要表示依赖关系 表示依赖关系就是对依赖进行建模 比如前面说到的向量、先行图、确定因子都是对依赖关系的模型化表示。计算开销的大小依赖于模型的复杂程度。相比较而言 先行图的计算比较复杂 向量和确定因子的方法相对简单。 依赖关系的传输开销消息传递产生依赖关系 因此在消息上附带依赖关系 在因果依赖跟踪中 每个消息不仅会附带自己的“父辈”直接依赖 还会附带“祖辈 依赖 那么来基于依赖跟踪和消息计数的回卷恢复容错技术研究自同一个“家族”的不同消息上可能附带了许多相同“祖辈”依赖 如果这此消息都被同一个进程接收 那么这些重复的依赖就是无意义的。为了降低这一部分无意义的依赖传输 增量式的依赖跟踪是一种有效的方法 增量先行图方法己取得了良好的效果。 依赖关系的存储开销没有消息日志的依赖跟踪是空洞的 那是无本之末 没有依赖跟踪的消息日志是笨拙的 那就如果悲观消息日志。依赖跟踪必须结合适当的消息日志才能有效的保证进程之间状态的一致性。因此考虑依赖关系本身开销的同时 还要考虑与之配合的消息日志所带来的开销。通过上述的分析 我们选择基于确定因子的依赖跟踪方法来进行研究 我们的研究主要基于以下几个点来降低开销 很多应用场景中 运行时消息可能具有聚集性 某些进程之间通信频率高 而与其它进程通信频率低 会造成大量的“祖辈 依赖关系的重复。如果整个系统的通信频率都很高的话 “祖辈”依赖关系重复更为严重 因此我们采用附带策略来降低重复依赖关系的传递 实现增量式的依赖跟踪。 进程正常执行期间的容错工作都为故障后的恢复做准备的 降低无故障执行期间的开销和故障恢复时的开销都是我们的研究内容。但这两种开销之间在一定程度上具有此消彼长的对立关系 考虑到故障发生是低概率这一特征 我们可以将正常执行期间的部分开销转移到故障后的恢复过程 这对提交整个系统的执行效率是有意义的。在此我们通过降低与依赖跟踪相结合的日志开销 来提高系统无故障执行时期的效率。 基于依赖跟踪的轻量级消息日志协议 协议描述在依赖跟踪中 为了唯一地标识系统在整个计算过程中进程间传递的每一消息 每一个消息有消息标识符 其中记录发送进程的标识号 记录接收进程的标识号 记录针对接收进程而言的消息发送序号 记录接收进程的消息提交序号 记录已存储了该消息标识符的进程集合。例如 表示该消息为进程 给进程 发送的第 个消息 也是进程尸 提交的第 个消息 该消息标识符已经分别在进程 中被存储。为了给每一消息能附加上消息标识符每一进程维护数组变量 分别记录给其它进程也包括自己 己发送的消息个数 和从其它进程 也包括自己 已经接收的消息个数。例如进程尸 表示进工程硕士学位论文程已经给进程 发送了 个消息 表示进程已经接收了 个来自进程尸 的消息。每一进程也维护变量 记录它已经提交的消息的个数。另外 每一进程也维护一个消息标识符容器 。当进程给进程毋发送一个消息 进程构造该消息的 将其 赋值为赋值为 然后将 附带在消息 上一起发给进程 。当进程尸 提交一个消息 先将变量增 再摘取出该消息的 将其 赋值为 设置为空然后将该 加入到 中。进程尸 在给另一进程 发送一个消息 还执行如下操作。首先扫描中的每一项 检查其元组 中是否包含元素 如果没有 则在其元组 中添加元素 再将该项附加到 上附加的项集记作 。进程尸 然后将附加了 的消息 发送给接收进程尸 。然后检查 中每一项的元组 中包含的元素个数 如果达到阈值 多故障上限值则将该项从 中删除。每一进程还维护一个消息标识符容器 其中的消息标识符项与中的项所含的元组稍有区别 没有 元组 记作。 。当进程 从进程接收到一个消息 将附带在其上的分别合并到自己的 容器中不存在的项直接添如到两 容器 容器中存在的项更新 容器中对应项的 值。合并后 再检查 中每一项的元组 中包含的元素个数 如果达 到阈值厂 多故障上限值 则将该项从 中删除。故障恢复时 假设进程尸 发生故障 在一个正常结点上使用 最近的检查点恢复至状态三墨 然后向系统广播故障恢复请求 请求中包含参数 其它正常进程收到请求后 中找出等于 并且 大于 将它们作为响应发送给进程置同时也把自己的 】也发给 。进程 根据收到的响应 基于 得到。 序列 使用日 志依次重演消息 以此实现故障恢复。其中的值并不是预知的 只有在接收到系统中的所有其它进程的响应之后才可确定。在进程 前滚中 如果要给进程尸 发送消息 应先检查其 是否大于进程尸 响应中的 如果不是则说明该消息为重复消息 应丢弃 不需要发送给进程尸

  基于依赖跟踪和消息计数的回卷恢复容错技术研究,容错技术,计数器,科学计数法,重映射扇区计数,crc接口错误计数,血小板计数,重映射扇区计数警告,白细胞计数,红细胞计数

http://nicolashsiung.com/zhixingkaixiao/139.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有