论文部分内容阅读
摘要:本文对传统的几中互斥算法进行了讨论,分析了其特点,还提出了令牌环算法的一个改进。该算法解决互斥算法中出现的部分问题,并经过了实验验证。
关键词:互斥算法;令牌;选举算法
中图分类号:TP3文献标识码:A文章编号:1007-9599 (2010) 10-0000-02
Discussion and Improvement on Distributed Exclusion Algorithms
Zhao Xiling,He Yong
(Xinyang Agricultural College,Xinyang464000,China)
Abstract:This paper has analyses conventional mutual exclusion algorithms,and their characters were also analyzed.Furthermore,an improved algorithm for Token-ring algorithm was presented,which resolved some problems that could happen in mutual exclusion algorithms,and it is proved by experiments.
Keywords:Mutual exclusion;Token;Election
一、引言
在分布式系统中,经常出现多个进程请求访问同一个临界资源的问题,为了协调访问,分布式操作系统必须处理相关进程之间的同步与互斥,互斥是分布式系统设计的关键问题[1]。为了实现高效率的进程通信,应当有良好的互斥算法。
二、典型的互斥算法
(一)集中式算法
在分布式系统中达到互斥的最直接的方法是仿照单处理器系统中的方法,选举一个进程作为协调者,无论何时一个进程要进入临界区,它都要向协调者发送一个请求消息,说明它想要进入哪个临界区并请求允许。协调者对所有的请求进行排队并根据一定的规则如时间戳(Time Stamp)授予许可。若某一时刻临界区中已有一个进程,协调者便不能同意新的请求,最好的办法是发出拒绝应答。当占有临界区的进程从临界区退出时,向协调者发送释放互斥消息,允许其他进程进入临界区。
该算法保证了互斥的实现,这种方案也容易实现,每次访问一次临界区只需3条消息(请求、允许和释放),但缺点为协调者是一个瓶颈。
(二)分布式算法
该算法假设所有事件都是全序的,当进程欲进入临界区时,应向其它进程广播请求,任一进程收到此请求时,可分三种情况:
1.若接受者不在临界区也不想进入临界区,它就向发送者发送一个OK消息。
2.若接受者已经在临界区中,它不进行应答,而是将该请求放入队列中。
3.若接受者想进入临界区但尚未进入时,它将对收到的消息的时间戳与包含在它发送给其余进程的消息中的时间戳进行比较,取时间戳最早的进入。如果收到的消息的时间戳比较早,那么接收者向发送者发回一个OK消息。如果它自己的消息的时间戳比较早,那么接受者将收到的请求放入队列中,并且不发送任何消息。
这种算法的最大优点是不存在单个故障点。实现的分布式互斥也不会发生死锁或饿死现象。算法存在的问题:
1.要求访问共享资源的进程,须知道所有进程的名字。
2.如果系统中有一个进程失败,则必然会使发出请求消息的进程无法收到全部响应,因此系统还应具备这样的功能。即一旦某个进程失效,系统能将该进程的名字通知其它进程。
(三)令牌环算法
所有的进程组成一个逻辑环,环中每个进程只有唯一的前驱者和唯一的后记者。环中的每个进程都要知道谁在它的下一个位置。令牌代表了一个控制点,它在环上传递,一个进程当且仅当拥有令牌时可以访问临界区。当请求进程没有令牌时,算法需要N个消息;当请求进程持有令牌时,算法不需要产生任何消息[2]。
算法的正确性是显而易见的,但也存在一些问题,令牌一旦丢失,它必须重新生成。当进程崩溃时,该算法也会出现麻烦。
(四)以上三种算法的比较
互斥算法的性能由以下参数衡量:
1.每次请求的消息数。
2.同步延迟,以一个进程离开临界区到下一个进程进入该临界区之间的间隔来衡量。
3.反应时间,以一个进程发出请求到该进程离开该临界区之间的间隔来衡量。
上述三个参数中,1和2用于衡量一个给定的互斥算法的能,3更多的取决于系统中符合和每个进程在临界区执行时间的长短。对三种算法的比较见表一。
可见,集中式算法最简单,也最有效。令牌环算法的消息数目是可变的,如果每个进程总想进入临界区,那么令牌的每次传递将导致一次进入临界区。这样平均每进一次临界区就需要一个消息。在另一种极端的情况下,有时令牌在环中绕行了几个小时也没有进入临界区。这种情况下,每进入一次临界区消息的数目趋向于无穷大。
三、令牌算法的改进
对于令牌环算法会出现令牌丢失的情况,会导致算法的失败[3],提出了选举算法思想。
选举是分布式系统中一种常用的计算类型,它从进程集中选出一个进程执行特别的任务。选举的基本思想是:每一候选人收到比自己标识大的后选人的消息前,都可以发出选举消息,非候选人不能发出选举消息,只能向其相邻的可能的后选人发送唤醒消息。候选人发送的选举消息沿着其传播图前进,不能前进时再沿原路返回。若一节点所发出的所有消息都已返回,则此结点就是领导人。只有当一结点的标识在全系统中最大时,其发出的所有选举消息才能返回[4]。
由于无法预见令牌的丢失,所以无法通过预防来避免,只能在检测到令牌丢失后进行补救。可以将每个进程都固定编号,并设置一个记时器,当进程广播出去后进入倒计时。如令牌丢失,记时器将超时,此时则产生一个选举令牌,按逻辑环方式沿进程编号循环传递,所有进程都保留最后一次见到控制令牌时间(即上一次发送控制令牌时间,记作T1),选举令牌中记录了它自己产生的时间(记作T2)。当选举令牌达到某一进程时,进程首先判断自己是否是这个令牌的所有者,如该进程不是选取令牌的所有者,它通过比较T1和T2的大小来决定是否发生了令牌的丢失。如该进程在选举令牌产生后还发送过控制令牌(T2T1),则认为令牌可能丢失。它将T1,T2比较的结果在选举令牌中记录下来,然后将令牌沿逻辑环继续向前传。如该进程是选举令牌的所有者,则回收选举令牌,并根据选举令牌中的标记判断是否应产生一个新的控制令牌。产生的新控制令牌首先满足自己的请求,然后进入正常工作循环。这种方法可以较好的解决令牌丢失问题。实验证明,经过一段有限的选举时间之后,系统总能保证有且仅有一个令牌在逻辑环。
四、结束语
本文分析了分布式系统中的多种互斥算法,还提出了令牌算法的一种改进,解决了在真实网络中出现的部分问题,并经过单机环境下的多进程真网络环境模拟验证。
参考文献:
[1]孟静.操作系统教程--原理和实例分析[M].北京:高等教育出版社,2001
[2]Andrew S.Tanenbaum,Maarten van Steen分布式系统[M].北京:清华大学出版社,2002
[3]鞠九滨.分布计算系统[M].北京:高等教育出版社,1997
[4]ANDREWST.Distributed Operating Systems[M].北京:电子工业出版社,1997
作者简介:赵喜玲(1972-),女,讲师,硕士研究生,研究方向:图像处理和模式识别,操作系统。
关键词:互斥算法;令牌;选举算法
中图分类号:TP3文献标识码:A文章编号:1007-9599 (2010) 10-0000-02
Discussion and Improvement on Distributed Exclusion Algorithms
Zhao Xiling,He Yong
(Xinyang Agricultural College,Xinyang464000,China)
Abstract:This paper has analyses conventional mutual exclusion algorithms,and their characters were also analyzed.Furthermore,an improved algorithm for Token-ring algorithm was presented,which resolved some problems that could happen in mutual exclusion algorithms,and it is proved by experiments.
Keywords:Mutual exclusion;Token;Election
一、引言
在分布式系统中,经常出现多个进程请求访问同一个临界资源的问题,为了协调访问,分布式操作系统必须处理相关进程之间的同步与互斥,互斥是分布式系统设计的关键问题[1]。为了实现高效率的进程通信,应当有良好的互斥算法。
二、典型的互斥算法
(一)集中式算法
在分布式系统中达到互斥的最直接的方法是仿照单处理器系统中的方法,选举一个进程作为协调者,无论何时一个进程要进入临界区,它都要向协调者发送一个请求消息,说明它想要进入哪个临界区并请求允许。协调者对所有的请求进行排队并根据一定的规则如时间戳(Time Stamp)授予许可。若某一时刻临界区中已有一个进程,协调者便不能同意新的请求,最好的办法是发出拒绝应答。当占有临界区的进程从临界区退出时,向协调者发送释放互斥消息,允许其他进程进入临界区。
该算法保证了互斥的实现,这种方案也容易实现,每次访问一次临界区只需3条消息(请求、允许和释放),但缺点为协调者是一个瓶颈。
(二)分布式算法
该算法假设所有事件都是全序的,当进程欲进入临界区时,应向其它进程广播请求,任一进程收到此请求时,可分三种情况:
1.若接受者不在临界区也不想进入临界区,它就向发送者发送一个OK消息。
2.若接受者已经在临界区中,它不进行应答,而是将该请求放入队列中。
3.若接受者想进入临界区但尚未进入时,它将对收到的消息的时间戳与包含在它发送给其余进程的消息中的时间戳进行比较,取时间戳最早的进入。如果收到的消息的时间戳比较早,那么接收者向发送者发回一个OK消息。如果它自己的消息的时间戳比较早,那么接受者将收到的请求放入队列中,并且不发送任何消息。
这种算法的最大优点是不存在单个故障点。实现的分布式互斥也不会发生死锁或饿死现象。算法存在的问题:
1.要求访问共享资源的进程,须知道所有进程的名字。
2.如果系统中有一个进程失败,则必然会使发出请求消息的进程无法收到全部响应,因此系统还应具备这样的功能。即一旦某个进程失效,系统能将该进程的名字通知其它进程。
(三)令牌环算法
所有的进程组成一个逻辑环,环中每个进程只有唯一的前驱者和唯一的后记者。环中的每个进程都要知道谁在它的下一个位置。令牌代表了一个控制点,它在环上传递,一个进程当且仅当拥有令牌时可以访问临界区。当请求进程没有令牌时,算法需要N个消息;当请求进程持有令牌时,算法不需要产生任何消息[2]。
算法的正确性是显而易见的,但也存在一些问题,令牌一旦丢失,它必须重新生成。当进程崩溃时,该算法也会出现麻烦。
(四)以上三种算法的比较
互斥算法的性能由以下参数衡量:
1.每次请求的消息数。
2.同步延迟,以一个进程离开临界区到下一个进程进入该临界区之间的间隔来衡量。
3.反应时间,以一个进程发出请求到该进程离开该临界区之间的间隔来衡量。
上述三个参数中,1和2用于衡量一个给定的互斥算法的能,3更多的取决于系统中符合和每个进程在临界区执行时间的长短。对三种算法的比较见表一。
可见,集中式算法最简单,也最有效。令牌环算法的消息数目是可变的,如果每个进程总想进入临界区,那么令牌的每次传递将导致一次进入临界区。这样平均每进一次临界区就需要一个消息。在另一种极端的情况下,有时令牌在环中绕行了几个小时也没有进入临界区。这种情况下,每进入一次临界区消息的数目趋向于无穷大。
三、令牌算法的改进
对于令牌环算法会出现令牌丢失的情况,会导致算法的失败[3],提出了选举算法思想。
选举是分布式系统中一种常用的计算类型,它从进程集中选出一个进程执行特别的任务。选举的基本思想是:每一候选人收到比自己标识大的后选人的消息前,都可以发出选举消息,非候选人不能发出选举消息,只能向其相邻的可能的后选人发送唤醒消息。候选人发送的选举消息沿着其传播图前进,不能前进时再沿原路返回。若一节点所发出的所有消息都已返回,则此结点就是领导人。只有当一结点的标识在全系统中最大时,其发出的所有选举消息才能返回[4]。
由于无法预见令牌的丢失,所以无法通过预防来避免,只能在检测到令牌丢失后进行补救。可以将每个进程都固定编号,并设置一个记时器,当进程广播出去后进入倒计时。如令牌丢失,记时器将超时,此时则产生一个选举令牌,按逻辑环方式沿进程编号循环传递,所有进程都保留最后一次见到控制令牌时间(即上一次发送控制令牌时间,记作T1),选举令牌中记录了它自己产生的时间(记作T2)。当选举令牌达到某一进程时,进程首先判断自己是否是这个令牌的所有者,如该进程不是选取令牌的所有者,它通过比较T1和T2的大小来决定是否发生了令牌的丢失。如该进程在选举令牌产生后还发送过控制令牌(T2
四、结束语
本文分析了分布式系统中的多种互斥算法,还提出了令牌算法的一种改进,解决了在真实网络中出现的部分问题,并经过单机环境下的多进程真网络环境模拟验证。
参考文献:
[1]孟静.操作系统教程--原理和实例分析[M].北京:高等教育出版社,2001
[2]Andrew S.Tanenbaum,Maarten van Steen分布式系统[M].北京:清华大学出版社,2002
[3]鞠九滨.分布计算系统[M].北京:高等教育出版社,1997
[4]ANDREWST.Distributed Operating Systems[M].北京:电子工业出版社,1997
作者简介:赵喜玲(1972-),女,讲师,硕士研究生,研究方向:图像处理和模式识别,操作系统。