一种欺负算法的改进与实现.pdf

《一种欺负算法的改进与实现.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第30卷第2期(上)赤峰学院学报(自然科学版)Vo1．30No．22014年2月JournalofChifengUniversity(NaturalScienceEdition)Feb．2014一种欺负算法的改进与实现邓定胜(四川民族学院计算机科学系，四川康定626001)摘要：改进并实现了欺负算法，利用二次连接检测的方法，构架了一个用于欺负算法的故障检测器并针对在新进程启动时，协调者可能重新选举的问题，提出了设置稳定时间的方法．关键词：欺负算法；二次连接检测；分布式系统；选举算法中图分类号：TP311．13文献标识码：A文章编号：1673—260X(2014)02—0017—021前言IP的

2、方法．当连接完成后，各参与进程间的关系如空中交通管理系统需要实时的采集处理和保图所示：存大量的数据，如地图信息、雷达信息、飞行情报2．2．2失效检测器等．这就要求空中交通管理系统具有强大的处理能这里所讲的失效检测器可以处理两种故障．力、并具有高可靠性；为了满足性能需求，空中交通2．2．2．1leader进程崩溃管理系统选择分布式系统来作为其解决方案．由于各参与节点间以TCP来连接，所以当参在多数分布式算法中，都需要一个进程来充当与进程崩溃或结束时，与此失效的进程相连接的所协调者，通常来说，选择哪一个进程来作为协调者有进程都会收到由失效进程节点发出的FIN，收到并不重要，重要的是需要由一个唯一的

3、进程来充当FIN的进程的rev函数会返回0，所以利用TCP的[11．欺负算法是由Garcia—Molina提出的，其基本思想这个特性，就可以检测出此类故障并处理．是：“当任何一个进程发现协调者不再响应时就发2．2．2．2leader进程所在的主机崩溃和leader断网起一次选举”，目前已有许多关于欺负算法讨论的当leader所在的主机崩溃或leader断网时，由文章[21，据此，本文改进并实现了欺负算法．于进程来不及向其它节点发送FIN，所以其它所有2实现的非leader进程都将不会检测到leader是否已经其实现的功能有：失效．虽然TCP的SO—KEEPALIVE套接口选项可2．1保证在le

4、ader进程崩溃、leader进程所在的节以在一定的时间之后发现leader已经崩溃，但此套点崩溃和leader网断时可以选举出新的leader．接口选项的超时间过长，且不可更改，所以这种方2．2改进欺负算法，使得只要leader不出现故障，法不可采用．就不重新选举新的leader．为了能在较短的时间内获知leader是否已经2．2．1各参与进程的连接方式失效，可以使用UDP(心跳)的方法，然而使用这种各个参与进程的通信方式为TCP，连接方式为方法有个缺点：可能会出现leader没有失效，而错两两相连，同时，为了简化为各参与进程创建TCP误的认为leader已经失效的情况．据此，本文采用连接的

5、过程及减少TCP链路的数量，应该使进程一种二次连接的方法来检测leader所在的主机崩间的连接有方向，因此在本文中使用小IP连接大溃和断网的故障．详细方法如下[31：2．2．2．2．1为了进行连接测试，每个进程都创建两个套接口A、B，每一个进程都在A套接口上监听．2．2．2．2．2连接检查时，用接口B向所有由系统中其它进程创建的套接口A发起非阻塞连接connect函数，若非阻塞函数connect函数返回值为0，就表示被连接节点没有发生故障；若非阻塞函数con—时间后，进程2又启动了，那么此时进程2将被选nect函数返回值为一1f而windows则返回SOCK—举为leader，以此类推，若进程

6、1、2、3、4、5在较短ET的时间内依次启动，而中间的时间差又足够挑选新_ERROR)，则取其错误代码err，如果e~=EIN—PROGRESS，则表示TCP的三路握手已经发起，连的leader的时候，将会发生4次leader的变化．为了接正在进行中，但不能马上完成，需要进行第二次防止这种情形的出现，本文采用如下方法：每一个连接检查；若是其它错误，就表示连接失败，被连接进程在启动时都设置一个稳定的时间，在这个稳定进程可能已经出现故障了，不需要进行第二次连接的时间内，此进程除用于新节点发现的广播外，任检查了；在上面的第一次连接完成后，若需要进行何事情都不做，若当前leader发现有新进程启动第二

7、次连接检查，就先等待数秒，再进行第二次连时，leader就给此新启动的进程发送一个通知消接检查，第二次连接检查使用select函数，其方法息，告诉新进程当前leader的编号；若新启动的进是：程在稳定的时间内没有收到此通知信息，它就认为第一步：将连接方的文件描述符加入到select系统中没有leader存在，于是便发起选举．函数的读集和写集中，并设置select的超时间为一3实验个很小的值．实验采