哈尔滨商业大学学报(自然科学版)JournalofHarbinUniversityofCommerceNaturalSciencesEdition第19卷第1期2003年2月Vol.19No.1Feb.2003关于分布式系统进程互斥算法的研究邢雁(哈尔滨商业大学计算机与信息工程学院,黑龙江哈尔滨150076)摘要:就互斥问题,即定义基本的操作来解决共享资源的多个并发进程的冲突问题,提出了一种更适合真网络环境的算法。关键词:互诉;分布式;集中式;令牌环;消息中图分类号:TP301.6文献标识码:A文章编号:1672-0946(2003)01-0043-04StudyondistributedmutualexclusionalgorithmsXINGYan(SchoolofComputerandInformationEngineering,HarbinUniversityofCommerceHarbin150076,China)Abstract:Themutualexclusionproblem-todefinethefundamentaloperationstodealwithsev2eralconcurrentprocesses,whicharesharingresourceshasbecomethemajorproblemconcerningdistributedsystem.Expoundingsomebasictheoryandcharacteristicsofdistributedmutualexclu2sionalgorithms.Onthebasisofthreeconcisealgorithms,putforwardaalgorithmthatfittherealnetworkenvironmentbetter.Keywords:mutualexclusion;distributed;centralized;tokenring四项假设3:(1)每个分布式系统具有N个节点,每个节点有唯一的编号,可以从1到N。每个节点中仅有一个进程提出访问共享资源的请求。(2)按序传送信息。即发送进程按序发送消息,接收进程也按相同顺序接收消息。(3)每个消息能在有限的时间内被正确地传送到目标进程。(4)在处理机间能实现直接通信,即每个进程能把消息直接发送到指定的进程,不需要中转处理机。以下讨论的一些互斥算法,都是基于以上四项假设的。在单机条件下,诸进程运行于同一个处理机和内存环境中,进程通信十分简单1。进程之间可以借助于“共享存储器”进行直接通信,使用信号量(semaphore),PV操作,锁机制等实现进程的同步与互斥。而在分布式环境下,相互合作的进程可能在不同的处理机上运行,进程间的通信涉及处理机的通信问题。在松散耦合系统中,进程间通信还可能要通过较长的通信信道,甚至网络。因此,在分布式环境下,为了实现高效率的进程通信,应当有良好的互斥算法。互斥问题最初是在集中式计算机系统中为独占控制之间的同步而考虑的2。Dekker提出了分布式系统互斥问题的第一个软件解决方案,经过不收稿日期:2002-10-091作者简介:邢雁(1981-),女,哈尔滨商业大学计算机与信息工程学院,研究方向:计算机应用1障,如果崩溃,整个系统将瘫痪。此外,大系统中单协调者会成为执行的瓶颈4。112分布式算法拥有单点故障的情况往往是不可接受的,所以研究者对此进行分布式互斥算法。假设所有事件都是全序的,当进程欲进入临界区时,应向其他进程广播请求(应使用可靠的通信),任一进程收到此请求时若:(1)不在临界区中,也不想进入临界区,向发送者发送OK;(2)已在临界区中,不回答,负责将发送者排入请求队列;(3)要进入临界区,尚未进入,则要比较时间戳,取小的进入,即发来的时间戳小,发OK,否则同(2)。如所有回答均为OK,请求进程可进入临界区,待从临界区退出,向请求队列中所有进程发OK,释放它们。该算法需要2(N-1)个消息交换:N-1个消息用于进程Pi通知所有其他进程对临界区的请求,另外N-1个消息用于传达同意信息(agree2ment)。一个进程只有收到所有其他进程的许可后才能访问临界区5。为了提高算法的效率,作为改进,一个请求进程可以在收到预先定义的进程子集(这样的子集称要进程在接收到令牌后发回确认消息,当相邻进程试图传递给它令牌却没有成功时,它就会检测到死进程。这时就将死进程从进程组中移出,它的下个进程就会从令牌持有者手中接收到令牌。114以上三种算法的比较互斥算法的性能由以下参数衡量:(1)每次请求的消息数;(2)同步延迟,以一个进程离开临界区到下一个进程进入该临界区之间的间隔来衡量;(3)反应时间,以一个进程发出请求到该进程离开该临界区之间的间隔来衡量。以上三个参数中,(1)和(2)用于衡量一个给定的互斥算法的性能,而第(3)个参数更多地取系统中符合和每个进程在临界区执行时间的长短。下表对这三种算法做一简单比较:表1三种算法的比较Table1Comparisonofthreealgorithms每次进出需要的...