关键字 |
| 互斥锁,响应性质,关键部分,令牌,错 |
介绍 |
| 高度可靠和可用的服务的要求不断提高,在许多领域在过去的十年。设计容错服务存在的几种方法。本章的重点是软件复制。复制允许一定数量的副本崩溃而不影响服务的可用性。系统涉及多个流程往往最容易编程使用的关键区域。当一个进程读取或更新某些共享的数据结构,它首先进入临界区实现互斥并确保没有其他过程将同时使用共享数据结构。互斥(通常缩写为互斥)算法用于并发编程,以避免同时使用一个共同的资源,如一个全局变量,通过计算机代码块叫做关键部分(CS)。一个关键部分是一段代码,一个进程或线程不断访问公共资源。程序、进程或线程可以有关键的部分没有任何机制或算法实现互斥。 |
| 原子广播/全序播放由不同的流程是确保消息广播给所有目的地过程在同一顺序启动。原子广播使排序机制和容忍失败。在异步系统崩溃失败两个最广泛使用的机制,容忍失败在原子广播算法1)不可靠的故障检测器2)组成员关系函数。 |
| 一个不可靠的探测器不提供一致的信息失败状态的过程。一组会员服务提供了一致的成员信息的所有成员组。例如告诉一个P, R已经崩溃的过程,和处理Q, R是活的,在同一时间。错误的失败的开销怀疑是高当使用组成员。团体会员服务,一个错误的怀疑会导致两个昂贵的会员操作:1)切除过程紧随其后,2)添加另一个进程。 |
| 故障检测器,删除和添加过程是必要的。原子广播算法基于故障检测器可用于实现会员服务。 |
本文的贡献 |
| 本文是对正在进行的研究的贡献不同容错互斥算法。到目前为止的研究是在系统层面上,许多系统都是相互联系的一个网格网络。现有的系统需要大量的电脑和一个巨大的骨干网络连接建立实验装置。和实验设置可能遭受的任何不必要的失败可能的失败节点或通信网络在的情况下,我们必须更加关注通信网络的节点故障。 |
| 在这篇文章中,我们集中在流程级别系统中失败,这是一个现实生活中通信系统的原型。摘要现有功能的多核处理器模拟网格计算环境的行为通过考虑一个小处理器组使用。 |
| 本文是一个扩展和修改的理查德·Ekwall原子广播算法[1],这是基于不可靠的故障检测器。这里的重点是过程的原子广播也将使用不可靠的故障检测器和令人满意的响应特性(RP)。[3]的服务质量也是维护过程中故障检测的过程。 |
| 崩溃的故障被认为是[4]类型。我们正在准备一个容错系统,肯定会在指定期限内作出回应,否则检查失败或故障在分布式系统将停止,不反应或获取资源的过程将被宣布为错误的,进一步从群体这一过程将被删除。本文的主要重点是错的宽容度以及原子广播的令牌必须回应其他进程在指定的时间间隔。 |
提出的模型 |
| 设计方案的目的是模拟分布式系统的容错能力在一个指定时间间隔。 |
| 这种方法的主要问题是有一个 |
| 容错系统:系统应该非常肯定和确认系统错误或没有错误的。它应该确认的状态处理器错误或没有错误的。如果处理器不是坠毁并且能够正确执行其任务处理器并不是错误的,否则错误的。 |
| 基于令牌:参加沟通过程的系统应该能够进入临界段执行只有在有效的令牌。的处理器有一个有效的令牌应该进入临界区和其他处理器应该尽量获得令牌如果它想进入CS。 |
| 响应性能:整个系统应该对用户查询和检查流程的可加工性在指定期限内。单个处理器应该执行指定时间跨度内的CS即处理器越来越时间限制在单个过程应该响应。如果不回应任何处理器为1圣时间应该尽量回复2nd时间等等,直到它到达指定的期限。 |
术语 |
| 我们使用以下术语来描述分布式系统的容错。 |
| 客户端是单个进程负责执行进程间通信。客户端将沟通当地调度程序或作业管理器进行操作。客户端是单独的实体负责执行指定的任务。客户端或处理器应该试着访问分布式任务执行。在这里我们假定客户端或崩溃的处理器只能失败。不接受其他手段失败的。 |
| 调度器或作业管理器准备就绪队列,这表明,客户会对网络中的共享资源的访问。调度器负责提供每个进程一个公平的机会来执行这项任务通过访问分布式资源。 |
| 工人与单个调度程序或作业管理器。每个作业管理器都有自己的员工来执行这个任务。 |
| 每个调度程序都有自己的一组工人但可能与任意数量的客户。分布式调度程序或作业管理器负责调度用户的查询,它可以通过分发其整个工作的工人。客户机和工人的沟通过程通过调度程序如下图1所示。 |
算法 |
| 实现容错原子广播算法我们需要遵循以下步骤 |
| 1。把工作分成许多任务(实验室) |
| 2。任务持有令牌访问资源 |
| 3所示。开始监控执行时间的计时器 |
| 4所示。如果任务超时时间内回应 |
| 申报流程为好 |
| 其他的 |
| 申报流程是错误的 |
| &删除流程/任务就绪队列 |
实现细节 |
| 实现实验装置在一个分布式计算过程的计算机模拟的行为我们需要以下配置的机器,这将促进我们看到多处理器环境的行为。 |
| 多核心处理器可以执行不同段的一个工作在一个处理器。段可以创建和执行的过程被称为细分。个人部分有能力分配整个工作分成小段可以进行独立。如果有任何国米依赖那么地方调度程序将处理任务依赖的问题和任何死锁或饥饿的问题。 |
| 每个任务应该访问主内存和他们应该执行部分的工作很快。促进这个过程我们需要至少2 gb的RAM。初级记忆越多我们越快可以执行的任务。执行时间或单独的任务的运行时间可以增强通过增加主内存的容量。 |
| 我们需要一个可配置的调度程序将资源分配给每个任务。调度器将持有的责任个人的资源每个分布式任务分配工作。为每个任务分配资源的目的我们可以有一个专门的调度器高性能计算(HPC)调度程序或者我们也可以使用现有的调度器中MATLAB。实现和测试当前工况的容错机制,我们使用现有的调度程序出现在MATLAB中,负载共享设施(LSF)调度器。LSF调度器是先发制人的调度器。它根据优先级分配和管理资源。我们模拟整个工作环境在MATLAB环境中通过适当的配置创建几乎不需要多处理器环境和研究整个系统的行为。 |
仿真与结果 |
| 模拟实验的设置中,我们首先需要创建和配置一个matalabpool将使我们能够模拟多处理环境中,我们可以有一个分布式共享资源,每个处理器可以访问。所以,我们首先创建一个本地调度器和定义集群的最大大小的分布式任务执行。我们还需要设置的路径分配工作。可以按照下面给出的配置选项。 |
| 这里设置集群大小后,共享资源的路径,默认的路径调度器MATLAB中我们需要验证配置设置,检查整个系统作为一个统一的可加工性。配置应该通过的所有步骤的正确的工作状态。为i5机器我们可以在最好的一个集群的大小8。 |
| 最初的整个核心机分为几个分区。这里每个分区是一个客户端,有独立执行分布式任务的能力。客户端将尝试访问共享资源来执行其CS在指定的时间跨度。每个客户端是一个独立的任务执行CS。在每次运行时,处理器将整个任务划分为若干子群体。对于魔法阵的情况下,我们整个8 x 8矩阵划分为4子部分的4 * 4矩阵。这样每个任务可以比出发,原8 x 8矩阵运算。这种分歧有助于做出更好和更快的利用现有的资源以有效的方式。 |
| 的观察,很明显,上面的执行时间计算的单个处理器或客户端系统作为一个整体小于整个任务。将整个任务的执行时间和实际计算可以比较性能测量。分布式任务调度的效果和性能增强部门的整个任务分成若干子组,我们发现系统可以运行和执行速度比子组作为一个整体。 |
| 我们有使用MATLAB模拟所有结果(7.10.0.499 (R2010a))在英特尔®CPU核心(TM) i5 M460 @2.53GHz机器。 |
| 根据这项工作,我们已经创建了二十工作,给她们指派到本地调度器。一旦任务被提交给当地的调度器,调度器将决定哪些工作将被执行。的工作需要从池中选择20个工作。选择的工作将执行其执行。客户端创建一个工作所花的时间与不同数量的任务显示在图2 (a)。这里的情节显示时间的总量为任务创建一个处理器。从情节的时间我们可以看到创建一个工作与越来越多的任务是减少对越来越多的任务。所以就业时间会大大减少,越来越多的任务指定的工作。 |
| 仿真结果2 (b)显示了任务或工人在当地调度程序创建时间。根据这个图表的时间创建一个分布式分区增加工人数量减少。这表明除以整个核心分成多个子组创建任务的时间逐渐减少,同时处理的任务的能力增加。通过增加集群大小机器的处理器可以运行速度比在正常状态。通过上面的图我们可以确认分布式任务可以执行的速度比正常的任务。 |
| 在整个工作变成一个数量的任务分工,我们允许他们执行CS(图2 (c))。当地的调度器将首先随机分配的令牌任务。有令牌的任务会得到一个公平的机会来执行CS。令牌的处理器或任务应该在超时之前访问共享资源。对于这个特殊的情况我已经分配了CS 20毫秒时间执行。如果任务没有响应第一尝试尽管有令牌,然后它不应止步于此,通过声明处理器有异味,而它会直到超时事件。如果任务仍无法访问共享资源,有令牌,那么这一过程应该被宣布为是错误的。这里我们假设坠毁处理器只会不回应,尽管拥有一个有效的令牌。一旦处理器完成其执行应该释放令牌其他想进入CS的处理器。 |
| 在任务完成后执行它应该被摧毁的记忆,使其他处理器分布式共享资源的访问。图2 (d)显示了控制站点的时间摧毁就业形式当地的调度器。 |
| 从图3中,我们可以看到任务失败率最初增加与小数量的任务工作。随着任务的数量增加故障率逐渐下降。因为在最初的阶段,它可能错误地怀疑一个过程是错误的,但是按照我们建议的模型处理器处理器不应该声明是错误的,除非在指定时间段内都不回应。我们消除错误涉嫌过失的处理器通过允许任务执行其CS通过收购令牌,不断通过发送请求令牌请求队列中的所有其他网站。错了错怀疑是减少,只有实际的故障识别模型有更好的性能,正常的容错机制。 |
结论和未来的范围 |
| 在本文中,我们已经开发出一种流程级别的容错机制,该机制是基于不可靠的故障检测器和原子广播机制应该能够探测到指定的时间期限内未能作出改进的容错机制。它结合了故障检测器和一个基于令牌机制,满足响应性质。机制可以容忍处理器级别故障与系统级故障的现有系统,因为该系统依赖不可靠的故障检测器,也依赖于反应性质。 |
| 仍然有许多开放的问题寻找容错互斥算法的效率和准确性。 |
| 这是一些有趣的开放等问题: |
| •实现死锁预防而资源分配而不是使用的死锁避免不那么有效的分布式系统增加了开销。 |
| •目前我们有一个单一的控制站点资源配置的,但是我们可以有一个分布式控制资源配置的站点进行生动的容错机制。 |
| •介绍情报系统的故障检测,检测故障所花费的时间可以最小化和优化。 |
|
数据乍一看 |
|
|
|
引用 |
- Ekwall, R。,Schiper, A., ”容错的口令原子广播算法”,IEEE可靠和安全的计算,8卷,没有。2011年10月5日,9月。
- 令牌传递总线访问方法,ANSI / IEEE 802.4标准,1985年。
- 陈,W。,Toueg, S., and Aguilera, M. K., “失败的服务质量检测器”,IEEE反式。电脑,卷。51岁的没有。2页561 - 580,2002年5月。
- Defago X。,Schiper, A., and Urban, P., “全序广播和多播算法:分类和调查”,ACM计算调查,36卷,没有。2,第421 - 372页,2004年12月。
- Ekwall, R。”,原子广播:基于容错令牌算法和性能评估“博士论文,洛桑联邦理工2007年5月。
- Ekwall, r和schip计划。”,比较原子在高延迟网络广播算法”,技术报告lsr -报告2006 - 003年洛桑Fe´de´罗音,瑞士,2006年7月。
- 弗里德曼、r和Renesse, r . V。”,包装信息作为一种工具推动总订购协议的性能”,Proc。第六IEEE计算机协会。高性能分布式计算,第242 - 233页,1997年8月。
- schip计划,a .和Toueg年代。”,从集员到组成员:关注点分离”,IEEE反式。可靠和安全计算,3卷,没有。1页2 - Jan.-Mar。2006年。
- 城市,P。,Shnayderman, I., and Schiper, A., “比较失败的探测器和组成员关系:两个原子广播算法的性能研究”,Proc。Intl相依可靠的系统和网络(DSN),第654 - 645页,2003年6月。
- Chang J.M. Maxemchuck, N。”,可靠的广播Proto-cols”,ACM反式。计算机系统,卷2,没有。3,第273 - 251页,1984年8月。
- Maxemchuk N.F.和前,d.h”,网络多播系统的股票市场”,ACM反式。计算机系统,19卷,不。3,第412 - 384页,2001年8月。
- 阿米尔,Y。,Moser, L., Melliar-Smith P., Aggarwal, D., and Ciarfella, P., “图腾的单码道命令和会员协议”,ACM反式。计算机系统,13卷,不。4,页311 - 342,Nov.1995。
- Whetten B。,Montgomery, T., and Kaplan, S. M., “高性能完全有序的多播协议”,Proc。Dagstuhl分布式系统研讨会,页。33-57,1994。
- 克里斯蒂安·F。Mishra年代。,and Alvarez, G., “高性能异步原子广播”,分布式系统中。J。,vol. 4, no. 2, pp. 109-128, June 1997.
- 克里斯蒂安·F。”,达成协议处理器组Member-ship同步分布式系统”,分布式计算,4卷,没有。4,第187 - 175页,1991年4月。
- Larrea, M。,Arevalo, S., and Fernandez, A., “高效的算法来实现可靠故障探测器部分同步系统”,Proc, Intl计算机协会。分布式计算、pp.34-48 1999。
- Hadzilacos,诉和Toueg、S。“错- - - - - -宽容的广播和相关问题”,技术报告94 - 1425年计算机科学部门,康奈尔大学,1994年5月。
- 钱德拉,t·d·Toueg,年代。”,可靠的分布式系统的不可靠的故障检测器”,j . ACM 43卷,没有。2、225 - 267年,1996页。
- Chockler, g . V。Keidar,我。,and Vitenberg, R., “组通信规格:一个全面的研究”,ACM计算调查,4卷,没有。33,页1 - 12月2001。
- Shye,。,Moseley, T., Reddi, V. J., Blomstedt, J.,”使用流程级冗余为瞬态容错利用多核”。
|
菜单
