lamport时间戳及互斥算法分析

1、lamport时间戳及互斥算法分析 摘要 本文在比较了分布式系统中三种基于时间戳的资源分配算法(L。Lamport时间戳算法、GRicart算法和Isuzuki的循环令牌算法)之后，就保持较小报文数和提高吞吐率与响应时间方面，提出了对GRicart算法的改进。 关键词： 时间戳；报文（信件）；互斥；算法 一 前言 （一）分布式系统资源分配 在分布式系统中，资源分布于各节点计算机上，它们有两种管理方式：集中分布式管理和全分布式管理。集中式分布管理方式实现比较容易，但系统有可靠性差、通信开销大以及形成瓶颈的缺点；全分布式管理方式避免了上述缺点，但实现起来复杂，实际的分布式系统常采用混合管理方式。这

2、里主要讨论全分布式管理方式的有关算法。 资源的完全分布式管理方式，是每个资源由不同节点上的资源管理者共同管理（管理按算法给出的原则共同协商资源的分配），所以算法应满足： 1、资源分配的互斥性。即每个临界资源每次最多只能被一个进程占有，避免出现死锁似及饿死现象； 2、各资源管理者应处于平等地位，没有集中控制现象。 （二）比较几种时间戳算法 从1976年Thomas首先提出使用时间戳对分布式系统中的活动进行排序，LLamport提出使用多重逻辑时钟对系统中的全部活动进行排序以来，人们不断研究提出基于时间戳来进行资源分配的一些算法，主要有： 1、LLamport的时间戳算法； 2、GRicart算法

3、（最佳互斥算法）； 3、Isuzuki等人提出的循环令牌算法。 这三个算法都保证了互斥，并且资源管理者都处于平等地位。从完成一次获得资源所需报文数来看： LLamport时间戳算法需3(n-l)个，n为进程数，GRicart算法需2(n-l)个报文，再做某些修改，其报文数还可以减少，令牌算法则需报文数最少，只需n个。 在分布式系统中，一类临界资源（例打印机等外部设备）的数目有多个，所以衡量一个算法的好坏，除了报文数以外，还要考虑申请者发出申请后多长时间才能获得资源，即响应时间，以及单位时间内有多少个进程（节点）能获得资源即吞吐率，要综合考虑几方面因素： LLamport算法尽管所需报文数多，但

4、具有较快的响应时间和较大的吞吐率； G. Ricart算法因为申请者只有收到所有其它进程的回信才能得到资源而造成吞吐率小，但还具有较快的响应时间； 令牌算法因为持有令牌的节点才能获得资源，以及使用完资源传送令牌附上状态表等而造成较长的响应时间和小的吞吐率。另外，令牌算法不具有坚定性，当令牌丢失或者持有令牌的节点失效时，必须有一个算法来决定谁成为令牌持有者。 均衡几方面因素，GRicart算法报文数不多，响应时间也比较快，只是吞吐率不大，是一种折衷算法。本文针对G. Ricart算法中存在吞吐率小的问题，同时也涉及到响应时间的提高，而提出一种改进算法。 二 算法改进 （一）算法说明 1、若进程（

5、节点）未失效，报文一定能无误地接收到，若失效，则不发信，也不收信。 2、报文传递满足“先发先到”的原则。（二）报文格式报文类型保留进程号时间戳保留 其中：保留部分用作说明申请资源（互斥资源）的类型。 （三）具体规则 1、申请资源的进程s向其它各进程发申请资源的报文，附有时间戳； 2、其它各进程r，收到申诸报文后，若： (1)不占资源，也不申请资源者，立即回收（报文类型reply0）； (2)也申请资源，则比较进程了s与自己的时间戳，若T<T。 则回信(replyl)否则回信(reply2)； (3)占有资源的进程，则在使用完资源，才对申请报文的进程补发回信(reply3)同时释放资源。若

6、其没有收到申请报文，使用完资源也不释放资源。 3、申请资源的进程收到其它所有进程的回信后可以得到：1）释放资源的进程的报文(reply3)数目n free；2）时间戳小于自己时间戳的报文(reply2)的数目n less。若nfree>nless，说明系统中的释放出的资源数目多于时间戳比自己小的进程数目，显然可获得资源，否则不能。 因为，不占资源也不申请资源的进程和申请资源且时间戳大的进程，对于申请资源且时间戳小的进程而言，效果是一样的（都不提供资源且不会先得资源），所以可将它们看成一样进行处理即replyO=replyl。 （四）程序描述 为了清楚起见，该算法用程序(pascal)描述

7、： 各进程间传递的报文数据结构及变量说明） type message=record class: (application, replyl, reply2, reply3); 报文分为申请信，各种回答信 process: 1.nI发信进程的编号） timestamp: integer; end;varT: integer逻辑时间，初值为1status: (bothnot, requesting, got); 各进程的状态：既不申请资源，也不占用资源；申请资源；占有资源三种情况）sendingtime: integer;发申请信时刻replycount:0n-l；回信计数）n_free:0m；释

8、放资源的报文数n_less:0n-l；（时间戳小的进程回信）defer: boolean；推迟发回信标志，初值为false）buffer: message;接收进程的缓冲区，保留申请报文）finished: boolean；进程使用完资源的标志）procedure Apply； 申请资源时调用此过程，执行后即获得资源var M: message; i: integer; begin status: =requesting; ' replycount: -n-l with M do begin class : =application; timestamp: =T; process :

9、= me ; end; sendingtime: =T; T: =T+1; for i:=1 to n do if i<>me tben send (M, i); waitfor (status: =got);end;procedure Receive (var R: message); 接收端口专门负责Var R：messagebeginendI(varI：message)；R. process : =me;with M docase class of application: begin case of status of bothnot: R. class: =replyl；

10、 requesting: if (timestamp>sendingtime) or (timestamp=sendingtime and process>me) then R. class: =replyl else R. class: =reply2; got: if finished then R. class: =reply3 else begin defer:=true; movin (process, buffer); end ； . end; statuscase T: =l+max (T, timestamp) if not defer then send (R,

11、process);end ； replyl : replycount : =replycount-l J reply2: begin replycount: =replycount-l; reply3: begin replycount : =replycount-l;end； M. classcaseif status = requesting then if (replycount=0 and n free>n less) then status: -got;end；procedure Usefinished; 迸程每次使用完资源时调用此过程var R: message;begin

12、finished; -true;if buffer<>NULL then status : =bothnot; while buffer<>NULL do begin moveout (process, buffer);with R do begin class : =reply3; process : =me end;send (R, process);status : = bothnot ; endend； （五）问题作进一步讨论 本算法为考虑问题简单起见，没有考虑进程（节点）失效的情况，这里进一步讨论： 若申请资源的进程没有收到全部回信时，则向未回信的节点重发申请信（时间戳保持原样）或追加一封询问信，若在一定时间内仍然没有收到回信，则认为其已“失效”，不再考虑这里失效有两种情况： 1、真正失效进程（节点）； 2、资源占用者没有使用完资源（前面已提过资源占用者只有在收到申请信且使用完资源后才回信），此时该资源占用的进程显然是不会提供（该类）资源，也不再发申请信的进程，所以可将其当成“失效”进程（节点）来看待。 三 结束语 本算法是在G-Ricart算法的基础上加以改进的算法，仍满足互斥性和平等性条件；申