Aa!r[}  0 `@ @ P0@PppHH $ @d HHHH̀̀̀ff@  d Footnote TableFootnote**.\t.\t/ - :;,.!?4eeTOCHeading1Heading2   bEquationVariablesbZ ;`<<=7=P=i=@E@F@;@=@?@A  <$lastpagenum><$monthname> <$daynum>, <$year>"<$monthnum>/<$daynum>/<$shortyear>J<$hour>:<$minute00> <$ampm> on <$dayname>, <$monthname> <$daynum>, <$year>"<$monthnum>/<$daynum>/<$shortyear><$monthname> <$daynum>, <$year>"<$monthnum>/<$daynum>/<$shortyear> <$fullfilename> <$filename> <$paratext[Title]> <$paratext[Heading1]> <$curpagenum> <$marker1> <$marker2> (Continued)+ (Sheet <$tblsheetnum> of <$tblsheetcount>)Heading & Page <$paratext> on page<$pagenum>Pagepage<$pagenum>See Heading & Page%See <$paratext> on page<$pagenum>. Table All7Table<$paranumonly>, <$paratext>, on page<$pagenum>Table Number & Page'Table<$paranumonly> on page<$pagenum>Heading <$paratext>HTML Headings++A88::33557QAHHA;b;d;f;h;j;l;n;p;r;t;v;x;z;|;~;;;;;;;;;;;;;;;;;;;;;LFL;;;;;;;;;LGL;;;;;;;;;;;;;;;;;;;LGEL;;;;;;;;;<<<<<< < <<<<<<<<M;GM=<"<$<&<(<*<,<.<0<2<4<6<8<:<<MoGMq$3.[?$4.[@$5.[A%a.[B-b.[C-c.[D2[E:[F:[G:^@^:?P^:_ :_:_ :_):_0:_1O_2O_3:_4:_5:\:_7O_8O_:a :a':X.XX.X8X8X.X11.X$2.X$3.X$6.a,:a9:X$7.X2X:[]7[^.[_[`.[a8[b8[c8[d8[e8[f8[g.[h11.[i$2.[j$3.[k$4.[l%a.[m-b.[n-c.[o.[p:_:a>:aI:aN:aW:a\:acO]:agOal:aq:]:]1:]:]:]i:]j:]Z:][:]:]:]:^:as:^:^:^+O^,:^.O^3:^8:^L:a~:^O^O^:^:^:a:a:a:Y9Aa:a:a:a:a:a:aOaOa:a:b:[7[.[[.[8[8[8[8[8[.[11.b:[$2.[%a.[-b.[$3.[%a.[-b.b:[$4.[%a.[-b.[2[:b:bObObC:bH:bS:`:eEvExEzE|E~EEEEEEEEEEEEEEEEEFFFHHHHHHHHHHHHHHHHHHHHHHHHHHHHOHHHHNHHHHHHHIIIIII I IIIIINIIII I"I$I&I(I*I,I.I0I2I4I6I8I:I<I>I@IBIDIFIHIJILINIPIRNSIVIXIZNUIeNINJOJ%JJJJJJKTKVGKXQdq5+dXb d;]d;L HmR;MHmRHRHRFootnote Hr@;NHr@HzHz Single LineH;O Footnote ;P  HD;Q HDHH Double LineH;R Double Line;S ;T H;U  Single Line;V HZ;W  TableFootnoted5p77 EGxR;XEGxREPwEPw TableFootnoted;^dEl d;_d'00zupkfa\WRMHC>vCFILORUX[^adgjmpsy| %).12/,)&#W/Bm }d ;ad WeHTML Mapping Table }Hd ;cHd We }Hd ;eHd We }Hd ;gHd We }Hd ;iHd We }H&;kH&g% FrameMaker E Source Item }H ;mH We XML Item }H ;oH We }H&;qH& W eInclude Auto# } H&;s H& W e Comments }H;uH W e }HH;w HH W eElement }H;y#Hg %New Web EPage? }H;{H We } H;} H We }H ; $H We P:Date Line }HH ;#%HH WeP }H ;$&H WeN }H ;%'H WeN } H ;&( H We }EH ;')EH We P:Reading }HEH ;(*HEH WeP }EH ;)+EH WeN }EH ;*,EH WeN } EH ;+- EH We }QH ;,.QH WeP:Title }HQH ;-/HQH WeH* }QH ;.0QH WeN }QH ;/1QH WeN } QH ;02 QH We }]H ;13]H WeP:Body }H]H ;24H]H W eP }]H ;35]H W!eN }]H ;46]H W"eN } ]H ;57 ]H W#e }iH(;68iH( W$e P:Numbered1 }HiH(;79HiH((&eLI %e Parent = OL A'e Depth = 0 }iH(;8:iH( W(eN }iH(;9;iH( W)eY } iH(;:< iH( W*e }H ;;=H  W+e P:Heading1 }HH ;<>HH  W,eH* }H ;=?H  W-eN }H ;>@H  W.eN } H ;?A H  W/e }H(;@BH(  W0e P:Numbered }HH(;ACHH(( 2eP 1e Parent = OL A3e Depth = 0 }H(;BDH(  W4eN }H(;CEH(  W5eY } H(;DF H(  W6e }H ;EGH  W7e P:CellBody }HH ;FHHH  W8eP }H ;GIH  W9eN }H ;HJH  W:eN } H ;IK H  W;e }H ;JLH  W<eP:CellHeading }HH ;KMHH  W=eP }H ;LNH  W>eN }H ;MOH  W?eN } H ;NP H  W@e }H ;OQH  WAe P:Footnote }HH ;PRHH  WBeP }H ;QSH  WCeN }H ;RTH  WDeN } H ;SU H  WEe }H(;TVH( WFe P:Bulleted }HH(;UWHH((HeLI Ge Parent = UL AIe Depth = 0 }H(;VXH( WJeN }H(;WYH( WKeN } H(;XZ H( WLe }H ;Y[H WMe P:Heading2 }HH ;Z\HH WNeH* }H ;[]H WOeN }H ;\^H WPeN } H ;]_ H WQe }H;^`HgR% P:HeadingRuEnIn }HH;_aHH WSeP }H<`bH WTeN }H<acH WUeN } H<bd H WVe }7H <ce7H WWe P:Indented }H7H < dfH7H WXeP }7H < eg7H WYeN }7H < fh7H WZeN } 7H <gi 7H W[e }CH<hjCHg\% P:TableFootEnote }HCH<ikHCH W]eP }CH<jlCH W^eN }CH<kmCH W_eN } CH<ln CH W`e }]H(<mo]H( Wae P:TableTitle }H]H(<npH]H((ceLI be Parent = OL Ade Depth = 0 }]H( H "W4e }©H <=?©H #W5e P:Answer }H©H <>@H©H #W6eP }©H <?A©H #W7eN }©H <@B©H #W8eN } ©H <A ©H #W9e }Td <D=FTd F$W:eHTML Options Table }DTd <DDTd F$W;e }Td <DTd F$W<e }dD <DCGdD F%W=eControl }DdH <DFHDdH F%W>eValue }dH <DGIdH F%W?e Comments }pD6<DHJpD6 F&W@e Image Format }DpH6<DIKDpH66F&A2% 0001IMAGGIF  MACP0001GIPdEF }pH6<DJLpH6 F&WBe }D <DKMD F'WCeBanners }DH <DLNDH F'WDeN }H <DMOH F'WEe }D<DNPDF(F% Banner ReferPE ence Frame }DH<DOQDH F(WGe }H<DPRH F(WHe }D(<DQSD((F)I$% Copy Files  Imported by PE Rerefernce }DH(<DRTDH( F)WJe }H(<DSUH( F)WKe }D(<DTVD((F*L$% Copy Files  Imported by PE Reference }DH(<DUWDH( F*WMeN }H(<DVH( F*WNe }Vd <D[Vd F+WOeSystem Macros }?Vd <D?Vd F+WPe }Vd <DVd F+WQe }f? <DX\f? F,WRe Macro Name }?fH <D[?fH F,WSe Replace With }fH <D^fH F,WTe Comments }r? =D]_r? F-WUe StartOfDoc }?rH =D^?rH F-WVe }rH =DarH F-WWe }~? =D`b~? F.WXe EndOfDoc }?~H = Da5?~H F.WYe }~H = D5d~H F.WZe }Š?= DceŠ?F/[% StartOfSubPEDoc }?ŠH=Dd6?ŠH F/W\e }ŠH=D6gŠH F/W]e }¤?=Dfh¤?F0^% EndOfSubPEDoc }?¤H=Dg7?¤H F0W_e }¤H=D7j¤H F0W`e }¾?=Dik¾?F1a% StartOfFirstPESubDoc }?¾H=Dj8?¾H F1Wbe }¾H=D8m¾H F1Wce }?=Dln?F2d% EndOfFirstPESubDoc }?H=!Dm9?H F2Wee }H=#D9pH F2Wfe }?=%Doq?F3g% StartOfLastPESubDoc }?H='Dp:?H F3Whe }H=)D:H F3Wie }?=+t?4j% EndOfLastPESubDoc }?H=-s;?H 4Wke }H=/;yH 4Wle }BH HDBwBH F5Wme C:Wingding }HBH HDvxHBH F5WneEM }BH HDw<BH F5WoeN }y}L? 7Wse Macro Name }?LH =@|~?LH 7Wte Replace With }LH =B}LH 7Wue Comments }X?=D~X? 8Wve See Also }?XH=F?XH8w% See Also: PE <$paratext> }XH=HXH 8Wxe }Vd EDVd F+Wye }fH ED\]fH F,WzeHead }rH ED_`rH F-W{e }xd =Q xd :WeGeneral Macros }?xd =S?xd :We }xd =Uxd :We }xd =Wxd :We }? =Y"? ;We Macro Name d= d= d l d= d  WBm }d = d  <W|eHeadings Table }Hd = Hd  <W}e }Hd = Hd  <W~e }H= H  =WeHeading Level }HH= HH =g%Paragraph ForEmat }H= H  =We Comments }H= H >W e2 }HH= HH  >We Heading1 }H= H  >We }KH = KH  ?We3 }HKH = HKH  ?We Heading2 }KH = KH  ?We }WH = WH  @We4 }HWH = HWH  @W e Lettereda }WH = WH  @W e }cH = cH  AW e5 }HcH = HcH  AW e LineComment }cH = cH  AW e HHˆXcHHˆ  `0Maekawas Distributed Mutual Exclusion Protocol ,` Introduction * /Maekawas algorithm uses sets  S i  of fewer than  n  processes. Also, a process  p i  locks all the nodes in  S i  by having only UUK@hone reply message out at a time. Each process has a queue of unsatisfied requests ordered by timestamp. dQ` Notation *v`4n  processes  p 1 , ,  p n UM`t j  timestamp  ` Protocol !**`To enter the critical section,  p i  sends REQUEST( t i ,  i ) to all sites in  S i . "L`SWhen  p j  receives a REQUEST( t i ,  i ) message:  if it has not sent a REPLYmessage to any site since the last RELEASE message  p j  received,  p j  sends D-@=REPLY( t j , , j ) to  p i . `*Otherwise, there is a process  p k  such that  p j  has already sent a REPLY( t j , , j ) message to  p k . Then: 0`:if ( t i ,  i ) < ( t k ,  k ),  p j  sends an INQUIRE( j ) message to  p k  and places the REQUEST on its queue. 1`WOtherwise,  p j  sends a FAILED( j ) message to  p i . #A When  p k  receives an INQUIRE( j ) message, it sends a YEILD( k ) message if either of the following conditions are UU#@met: 2*0^`Lp k  has received a FAILED message from a site in  S k  3=ݰ`p k  has sent a YIELD( m ) message to a site  p m      S k  and has not received a REPLY in reply. 4N`*Otherwise  p k  does nothing. 5\T EWhen  p j  receives a YIELD( k ) message,  p j  places REQUEST( t k ,  k ) in the queue and sends a REPLY( t j ,  j ) to the UU@*site whose request is first in the queue. *vq /When  p j  receives a RELEASE( t i ,  i ) message, it sends a REPLY( t j , , j ) message to the next site in the queue and 0deletes the entry from the queue. If the queue is empty,  p j  updates its state to reflect that no REPLY message has @Qbeen sent to any site since the last RELEASE message  p j  received. $w3`{p i  enters the critical section when it has received REPLY messages from all processes in  S i .  C'`When  p i  leaves the critical section, it sends RELEASE( t i ,  i ) to all sites in  S i . HHˆXeHHˆ7t ld@48H}?H =[ #?H ;We Replace With }H =]"$H ;W eHead }H =_#%H ;W!e Comments }? =a$&? CW"e }?H =c%'?H CW#e }H =e&(H CW$e }H =g')H CW%e }d =j(.d DW&eCharacter Macros HHˆ;"HHˆ+Ge HHˆ;$3HHˆ**l}?d =l?d DW'e }d =nd DW(e }? =p)/? EW)e Character }?H =r.0?H EW*e Replace With }H =t/1H EW+e Comments }? =v0B? FW,e HUV ;.HUV 3Ge HUV ;05+HUV 22l H$ ;1H$ 5Ge H$ ;33H$ 44l HHˆ;4HHˆ/7  `Outline for February 8, 2001 `Greetings and felicitations! Ru` Maekawass S`/Request sets satisfy the following conditions: T*OD?` for all 1   i ,  j   n  with  i   j ,  R i      R j    W]`Xfor all 1   i   n ,  p i      R i  X`Ffor all 1   i   n , |  R i  | =  K Y`Fp j  is contained in  K  number of  R i . ZUU`]Idea: every pair of processes has has a mediator (in both request sets) to mediate conflicts 1[ hOnly one outstanding REPLY per process, so each process gives permission to enter to only one other pro@cess \`8Assumes messages delivered in order which they are sent l`=To avoid deadlock, can INQUIRE whether someone cannot get it m`BA FAILED message just means someone else is going in out of order ]`MPerformance: between 3 N   and   5 N  messages ^L`Sanders generalized protocol _*`kInform set  I i  is set of processes to be informed when  p i  enters or leaves CS `i`TStatus set  ST i  contains pids for which  p i  maintains status information; note:  p i      I j      p j      ST i a`If  p i      I i  for all  i , then necessary and sufficient conditions to guarantee mutual exclusion are: b`&I i      R i c`I i      I j     or ( p i     Rj and  p j      R i ) dUU,}`#Suzuki-Kasamis broadcast protocol e8H` token-based fDG`"uses sequence numbers, not clocks g`-token has sequence numbers, associated queue h`?how to handle stale requests? tokens sequence number too high iiD`Raymonds tree-based protocol j` token-based Qk`5think of token as at root of tree, root moves around HHˆ;6HHˆ 66 lH$ @5!:H$ 99l H$ @6!H$ 8WlO Raymonds Tree-Based ProtocolECS 251 Winter 2001Page  8  HUV @7!8HHUV GGldZb== HHˆZc;HHˆw?=n `Sanders Generalized Protocol o,` Introduction p`=This protocol is a generalization of the previous protocols. qV` Notation rh`n  processes s*w`p i  process t`*R i  request set for  p i u`)I i  inform set for  p i v`*ST i  status set for  p i wUU`:CSSTAT  sites knowledge of state of critical section xUE` Protocol y*`uTo request entry,  p i  sends REQUEST( t i ,  i ) to all sites in  R i . z" `VWhen a site  p i  gets a REQUEST( t j ,  j ) message: {UU`Eit places the request onto its queue, which is ordered by timestamps |*D* if  CSSTAT  says the critical section is free,  p i  sends a GRANT message to the first process  p f   in the queue and |@3deletes its entry from the queue. If  p f      ST i , then  CSSTAT  is set to indicate that  p f  is in the critical section. }*;` When  p i  has received GRANT messages from all processes in  R i ,  p i  enters the critical section. ~`When  p i  leaves the critical section,  p i  sends a RELEASE message to every site in  I i . `3When  p i  receives a RELEASE message: UU`CSSTAT  is set to free *` If  p i  queue is not empty,  p i  sends a GRANT to the first process  p f   in the queue and deletes its entry from the nwE@queue. If  p f      ST i , then  CSSTAT  is set to indicate that  p f  is in the critical section. A` Repeat step b until either  CSSTAT  indicates a process has entered the critical section, or  p f s queue is empty. HHˆZe;HHˆt@<< ld[@@ HHˆ[>HHˆU*##@`Example *`:There are three processes,  p 1 ,  p 2 , and  p 3 .  p 1  and  p 3  seek mutually exclusive access to a shared resource. Let: `.I 1  = {  p 1 ,  p 3  },  I 2  = {  p 2  },  I 3  = {  p 3  }, so  ST 1  = {  p 1  },  ST 2  = {  p 2  },  ST 3  = {  p 1 ,  p 3  }; and `ZR 1  = {  p 1 ,  p 2 ,  p 3  },  R 2  = {  p 1 ,  p 2 ,  p 3  },  R 3  = {  p 2 ,  p 3  } `fThese satisfy the criteria that, for all  i ,  p i      I i ,  I i      R i , and for all pairs ( i ,  j ), either  I i      I j     or ( p i     Rj and  p j      R i ). JUU Initially: 0\+p1 state: C1 = 0, Q1 empty, CSSTAT1 empty +p2 state: C2 = 0, Q2 empty, CSSTAT2 empty @+p3 state: C3 = 0, Q3 empty, CSSTAT3 empty ``p1 sends Q(0,1) to p1, p2 and p3; p1s state now C1 = 1, Q1 empty, CSSTAT1 empty, GRANTS1 empty M`]p1 receives Q(0,1) from p1; p1s state now C1 = 1, Q1 = Q(0,1), CSSTAT1 empty, GRANTS1 empty N`Tp1 sends G(1,1) to p1; p1s state now C1 = 2, Q1 empty, CSSTAT1 = p1, GRANTS1 empty R`Xp1 receives G(1,1) to p1; p1s state now C1 = 2, Q1 empty, CSSTAT1 = p1, GRANTS1 G(1,1) E`\p3 sends Q(0,3) to p2 and p3; p3s state now C3 = 1, Q3 empty, CSSTAT3 empty, GRANTS3 empty O`]p3 receives Q(0,3) from p3; p3s state now C3 = 1, Q3 = Q(0,3), CSSTAT3 empty, GRANTS3 empty P`Tp3 sends G(1,3) to p3; p3s state now C3 = 2, Q3 empty, CSSTAT3 = p3, GRANTS3 empty S`Zp3 receives G(1,3) from p3; p3s state now C3 = 2, Q3 empty, CSSTAT3 = p3, GRANTS3 G(1,3) I`]p2 receives Q(0,1) from p1; p2s state now C2 = 2, Q2 = Q(0,1), CSSTAT2 empty, GRANTS2 empty K`Up2 sends G(2,2) to p1; p2s state now C2 = 3, Q2 empty, CSSTAT2 empty, GRANTS2 empty L`]p2 receives Q(0,3) from p3; p2s state now C2 = 3, Q2 = Q(0,3), CSSTAT2 empty, GRANTS2 empty V`Up2 sends G(3,2) to p3; p2s state now C2 = 4, Q2 empty, CSSTAT2 empty, GRANTS2 empty Q`]p3 receives Q(0,1) from p1; p3s state now C3 = 2, Q3 = Q(0,1), CSSTAT3 = p3, GRANTS3 G(1,3) T`bp1 receives G(2,2) from p2; p1s state now C1 = 2, Q1 empty, CSSTAT1 = p1, GRANTS1 G(1,1), G(2,2) W`ep3 receives G(3,2) from p2; p3s state now C3 = 3, Q3 = Q(0,1), CSSTAT3 = p3, GRANTS3 G(1,3), G(3,2) X`p3 enters its critical section Z`p3 exits its critical section [`Tp3 sends R(3,3) to p3; p3s state now C3 = 4, Q3 empty, CSSTAT3 = p3, GRANTS3 empty \`^p3 receives R(3, 3) from p3; p3s state now C3 = 4, Q3 = Q(0,1), CSSTAT3 empty, GRANTS3 empty ]`Up3 sends G(4, 3) to p1; p3s state now C3 = 5, Q3 empty, CSSTAT3 = p1, GRANTS3 empty Y`jp1 receives G(4,3) from p3; p1s state now C1 = 4, Q1 empty, CSSTAT1 = p1, GRANTS1 G(1,1), G(2,2), G(4,3) _`p1 enters its critical section ``p1 exits its critical section a`Yp1 sends R(4, 1) to p1, p3; p1s state now C1 = 5, Q1 empty, CSSTAT1 = p1, GRANTS1 empty b`Zp1 receives R(4,1) from p1; p1s state now C1 = 5, Q1 empty, CSSTAT1 empty, GRANTS1 empty Ac`Zp3 receives R(4,1) from p1; p3s state now C3 = 5, Q3 empty, CSSTAT3 empty, GRANTS3 empty HHˆ[>HHˆ=K?? ld[KK }?H =x1C?H FW-e¢ }H =zB2H FW.e d=~EEd=DdFF l d=Dd& zrE zupkfa\WRMHC>vCFILORUX[^adgjmpsy| %).12/,)&# HUV @8!HUV :WlBLast modified at 7:03 pm on Tuesday, February 27, 2001 HHˆ@9!:HHˆII l HHˆ@:!HHˆHW` HHˆ[AHHˆRE''K* `!Suzuki-Kasami Broadcast Protocol +,` Introduction , vThis is a token-based protocol. Unlike non-token-based ones, it uses the tokens being possessed by a site to provide I@]ordering of requests. Clocks and virtual time do not play a role; but order of arrival does. -b` Notation .t`n  processes /*`p i  process 0`xR i [ j ] largest sequence number  p i  has received in a REQUEST message from  p j 1`aL [ i ] sequence number of request that  p i  has most recently executed 2UU`2Q  queue (sequence) of sites requesting token 3*`T  = (Q, L) token 4` Protocol 5** To request entry, if  p i  does not have the token, it increments its sequence number  R i [ i ] and then sends @eREQUEST( i ,  s ),  s  =  R i [ i ], to all other sites. 6 " -When  p i  receives REQUEST( i ,  s ) from  p j ,  p i  sets  R i [ j ] = max( R i [ j ],  s ). If  p i  has the token and  R i [ j ] =  L [ j ] + 1, it ]@&sends the token to  p j . 7({`kIf  p i  is requesting entry and it has or receives the token, it enters the critical section. 8`@When  p i  finishes executing the critical section: 9`Cit sets  L [ i ] =  R i [ i ]; :R3 `0for every  j  not in  Q  and for which  R i [ j ] =  L [ j ] + 1,  p i  appends  j  to  Q ; and ;`if  Q  is not empty,  p i  deletes the first element  f  of  Q  and sends the token to  p f . <{3`Example =*ݭ`5There are three processes,  p 1 ,  p 2 , and  p 3 .  p 1  and  p 3  seek mutually exclusive access to a shared resource. UU QInitially:the token is at p2 and the tokens state is L = [0, 0, 0] and Q empty; @vp1s state is C1 = 0, R1 = [0, 0, 0]; p3s state is C1 = 0, R2 = [0, 0, 0]; and p3s state is C3 = 0, R3 = [0, 0, 0]  `Fp1 sends R(1, 1) to p2 and p3; p1s state is C1 = 1, R1 = [ 1, 0, 0 ]  `Fp3 sends R(3, 1) to p1 and p2; p3s state is C3 = 1, R3 = [ 0, 0, 1 ]  `Sp2 receives R(1, 1) from p1; p2s state is C2 = 1, R2 = [ 1, 0, 0 ], holding token >`p2 sends the token to p1  `Dp1 receives R(3, 1) from p3; p1s state is C1 = 1, R1 = [ 1, 0, 1 ] `Dp3 receives R(1, 1) from p1; p3s state is C3 = 1, R3 = [ 1, 0, 1 ] `p1 receives the token from p2 `p1 enters the critical section `dp1 exits the critical section  and sets the tokens state to L = [ 1, 0, 0 ] and Q = ( 3 )  `}p1sends the token to p3; p1s state is C1 = 2, R1 = [ 1, 0, 1 ], holding token, tokens state is L = [ 1, 0, 0 ] and Q empty `Up3 receives the token from p1; p3s state is C3 = 1, R3 = [ 1, 0, 1 ], holding token `p3 enters the critical section `]p3 exits the critical section  and sets the tokens state to L = [ 1, 0, 1 ] and Q empty C` HHˆ[AHHˆ@NJJ ld[NN HHˆ[LHHˆ!Ns `Raymonds Tree-Based Protocol t,` Introduction u tThis is a token-based protocol. The nodes are arranged in a binary tree, and one acquires the token by going up the I@ytree. The token is always kept at the root, so the tree needs to rearrange itself as the token floats from site to site. vb` Notation wt`n  processes x*`p i  process y`TQ i  request queue (sequence) of sites associated with process  p i z`BH i  holder variable associated with process  p i {UU`T  token |` Protocol }** To request entry, if  p i  does not have the token, it sends a REQUEST( i ) message to the node named in  H i  unless Q i  is not empty (because then it has already sent a REQUEST( i ) but has not yet received the token). It adds the @request to  Q i .  ^`MWhen  p i  receives REQUEST( j ) from  p j :  if  p i  does not have the token, it places the REQUEST( j ) on  Q i  and sends a REQUEST( i ) message along (proUU&@Pvided that it is not waiting for a response to an earlier REQUEST( i ). *2`mif  p i  has the token, it sends the token to  p j  and sets  H i  to j. A`BIf  p i  is requesting entry and receives the token:  Iif  i  is not the first entry in  Q i , it deletes the first entry  j  from  Q i  and forwards the token to  p j . It then sets  H i  to ][@nj . If  Q i  is not empty,  p i  sends REQUEST( i ) to  p j . `if  i  is the first entry in  Q i ,  p i  deletes  i  from  Q i  and enters the critical section. x`@When  p i  finishes executing the critical section: `-if  Q i  is not empty, it deletes the first entry  j  from  Q i , sends the token to  p j , and sets  H i  to  j Q;`sif after step a  Q i  is not empty,  p i  sends REQUEST( i ) to  p j . HHˆ[LHHˆKQMM ld[QQ HHˆ[OHHˆF$00Q `Example  * DThere are six processes,  p 1  through  p 6 .  p 1  and  p 5  seek mutually exclusive access to a shared resource, and later  p 3  will UU@ request it. 1 Initially: p4 has the token; .p1s state is C1 = 0, HOLDER2 = p3, Q1 empty .p2s state is C2 = 0, HOLDER2 = p3, Q2 empty .p3s state is C3 = 0, HOLDER3 = p4, Q3 empty =p4s state is C4 = 0, HOLDER4 = p4, Q4 empty, holding token .p5s state is C5 = 0, HOLDER5 = p4, Q5 empty @.p6s state is C6 = 0, HOLDER6 = p5, Q6 empty )`Dp1 sends Q(1) to p3; p1s state is C1 = 1, HOLDER2 = p3, Q1 = Q(1). `Dp5 sends Q(5) to p4; p5s state is C5 = 1, HOLDER5 = p4, Q5 = Q(5). `Hp3 receives Q(1) from p1; p3s state is C3 = 0, HOLDER3 = p4, Q3 empty. %`Dp3 sends Q(3) to p4; p3s state is C3 = 1, HOLDER3 = p4, Q3 = Q(1). &`Wp4 receives Q(5) from p5; p4s state is C4 = 0, HOLDER4 = p4, Q4 empty, holding token. ?`Dp4 sends token to p5; p4s state is C4 = 1, HOLDER4 = p5, Q4 empty. @`Hp4 receives Q(3) from p3; p4s state is C4 = 1, HOLDER4 = p5, Q4 empty. A`Dp4 sends Q(4) to p5; p4s state is C4 = 2, HOLDER4 = p5, Q4 = Q(3). B`Jp5 receives token from p4; p5s state is C5 = 1, HOLDER5 = p4, Q5 = Q(5). C`Bp5 resets state to C5 = 1, HOLDER5 = p4, Q5 empty, holding token. D`p5 enters the critical section F`p5 leaves the critical section G`Wp5 receives Q(4) from p4; p5s state is C5 = 1, HOLDER5 = p4, Q5 empty, holding token. U`Dp5 sends token to p4; p5s state is C5 = 2, HOLDER5 = p4, Q5 empty. H`Ip3 sends Q(3) to p4; p3s state is C3 = 2, HOLDER3 = p4, Q3 = Q(1) Q(3). ^`Ip4 receives Q(3) from p3; p4s state is C4 = 2, HOLDER4 = p5, Q4 = Q(3). d`ep4s state is C4 = 3, HOLDER4 = p5, Q4 = Q(3)Q(5) [it sends nothing as it is waiting for a response] e`^p4 receives token from p5; p4s state is C4 = 3, HOLDER4 = p5, Q4 = Q(3) Q(5), holding token. f`Ep4 sends token to p3; p4s state is C4 = 3, HOLDER4 = p3, Q4 = Q(5). h`Dp4 sends Q(4) to p3; p4s state is C4 = 3, HOLDER4 = p3, Q4 = Q(5). ~`^p3 receives token from p4; p3s state is C3 = 2, HOLDER3 = p4, Q3 = Q(1) Q(3), holding token. i`Ep3 sends token to p1; p3s state is C3 = 3, HOLDER3 = p1, Q3 = Q(3). j`Dp3 sends Q(3) to p1; p3s state is C3 = 4, HOLDER3 = p1, Q3 = Q(3). l`Yp1 receives token from p3; p1s state is C1 = 1, HOLDER1 = p3, Q1 = Q(1), holding token. m`Bp1 resets state to C1 = 1, HOLDER1 = p3, Q1 empty, holding token. n`p1 enters the critical section o`p1 leaves the critical section p`Wp1 receives Q(3) from p3; p1s state is C1 = 1, HOLDER1 = p3, Q1 empty, holding token. q`Dp1 sends token to p3; p1s state is C1 = 2, HOLDER1 = p3, Q1 empty. r`Yp3 receives token from p1; p3s state is C3 = 4, HOLDER3 = p1, Q3 = Q(3), holding token. `Np3 receives Q(4) from p4; p3s state is C3 = 4, HOLDER3 = p1, Q3 = Q(3) Q(4).  `4p3 resets state to C3 = 4, HOLDER3 = p1, Q3 = Q(4).  `p3 enters the critical section  `p3 leaves the critical section k`Sp3 sends token to p4; p3s state is C3 = 5, HOLDER3 = p4, Q3 empty, holding token. `Xp4 receives token from p3; p4s state is p4s state is C4 = 3, HOLDER4 = p3, Q4 = Q(5). `Dp4 sends token to p5; p4s state is C4 = 4, HOLDER4 = p5, Q4 empty. A`Ip5 receives token from p4; p5s state is C5 = 2, HOLDER5 = p4, Q5 empty. HHˆ[OHHˆNPP l dXtt HHˆXrHHˆ"$$t(`Example )`RThere are 13 processes. Initially, all logical clocks are set to 0. The sets are: 6*`S 1  = { 1, 2, 3, 4 } S 4  = { 4, 6, 10, 11 } S 7  = { 2, 7, 10, 13 } S 10  = { 3, 5, 10, 12 } 7` S 2  = { 2, 5, 8, 11 } S 5  = { 1, 5, 6, 7 } S 8  = { 1, 8, 9, 10 } S 11  = { 1, 11, 12, 13 } 8` S 3  = { 3, 6, 8, 13 } S 6  = { 2, 6, 9, 12 } S 9  = { 3, 7, 9, 11 } S 12  = { 4, 7, 8, 12 } 9`( S 13  = { 4, 5, 9, 13 } :UU`*p11 sends REQUEST(0, 11) to p1, p12, p13. ;h`;p12 receives REQUEST(0, 11) and sends REPLY(1, 12) to p11. <`;p13 receives REQUEST(0, 11) and sends REPLY(1, 13) to p11. =`(p7 sends REQUEST(0, 7) to p2, p10, p13. >`7p2 receives REQUEST(0, 7) and sends REPLY(1, 2) to p7. ?`9p10 receives REQUEST(0, 7) and sends REPLY(1, 10) to p7. @`'p8 sends REQUEST(0, 8) to p1, p9, p10. C`7p1 receives REQUEST(0, 8) and sends REPLY(1, 1) to p8. D`7p9 receives REQUEST(0, 8) and sends REPLY(1, 9) to p8. !B rp10 receives REQUEST(0, 8). It already sent a REPLY to p7. p7s request is timestamped (0, 7) < (0, 8). p10 sends @FAILED(10) to p8. !A rp1 receives REQUEST(0, 11). It already sent a REPLY to p8. p8s request is timestamped (0, 8) < (0, 11). p1 sends @FAILED(1) to p11. !E sp13 receives REQUEST(0, 7). It already sent a REPLY to p11. p11s request is timestamped (0, 11), and (0, 7) < (0, @#11). p13 sends INQUIRE(13) to p11. F`cp11 receives INQUIRE(13). It has received a FAILED(1) message from p1. p11 sends YIELD(11) to p13. G`_p13 receives YIELD(11). It now sends REPLY(2, 7) to p7 and places REQUEST(0, 11) in its queue. H*`ap7 has received replies from all processes in  S 7 . It enters the critical section. IUU62`Kp7 leaves the critical section and sends RELEASE(1000, 7) to p2, p10, p13. JB1`p10 receives RELEASE(1000, 7). L`p10 sends REPLY(1001, 8). N*`ap8 has received replies from all processes in  S 8 . It enters the critical section. OUUh`Jp8 leaves the critical section and sends RELEASE(1003, 8) to p1, p9, p10. Pt`p1 receives RELEASE(1003, 8). Q`p1 sends REPLY(1004, 1). U*`cp11 has received replies from all processes in  S 11 . It enters the critical section. VUU`Mp11 leaves the critical section and sends RELEASE(1005, 11) to p1, p12, p13. M` K` Ag` HHˆXrHHˆ =ss l|.} ? Eu($ ? LWe }? H Ew#%? H LWe... } H Ey$ H LWe }? E{+'? MWe }?H E}&(?H MWe- }H E'#H MWe }? E.*? NWe }?H E)+?H NWe-- }H E*&H NWe }? E1-? OWe }?H E,.?H OWe° }H E-)H OWe }? E40? PWe }?H E/1?H PWe® }H E0,H PWe }? EC3? QWe }?H E24?H QWe© }H E3/H QW e }~H EDbc~H F.W!e }ŠHEDefŠH F/W"e }¤HEDhi¤H F0W#e }¾HEDkl¾H F1W$e }HEDnoH F2W%e }HFDqrH F3W&e }HFtuH 4W'e }BH HDx=BH F5W(eN } BH HD@H6H F9W+eEM }6H HD?A6H F9W,eN }6H HD@B6H F9W-eN } 6H HDAv 6H F9W.e }*H HDLD*H FRW/eC:Superscript }H*H HDCEH*H FRW0eEM }*H HDDF*H FRW1eN }*H HDEG*H FRW2eN } *H HDF> *H FRW3e }H HDQIH FSW4e C:Subscript }HH HDHJHH FSW5eEM }H HDIKH FSW6eN }H HDJLH FSW7eN } H HDKC H FSW8e }H HDVNH FTW9e C:Emphasis }HH HDMOHH FTW:eEM }H HDNPH FTW;eN }H HDOQH FTW<eN } H HDPH H FTW=e }H HD[SH FUW>e C:Computer }HH HDRTHH FUW?eEM }H HDSUH FUW@eN }H HDTVH FUWAeN } H HDUM H FUWBe }H(HD`XH( FVWCe P:Romani }HH(HDWYHH((FV$eLI De Parent = OL Qe Depth = 0 }H(HDXZH( FVWEeN }H(HDY[H( FVWFeN } H(HDZR H( FVWGe }H(HDe]H( FWWHeP:Roman }HH(HD\^HH((FW$eLI Ie Parent = OL Qe Depth = 0 }H(HD]_H( FWWJeN }H(HD^`H( FWWKeN } H(HD_W H( FWWLe }HHDjbHFXM% P:LineComPEment }HHHDacHH FXWNeH* }HHDbdH FXWOeN }HHDceH FXWPeN } HHDd\ H FXWQe }H IDogH FYWReP:Line }HH IDfhHH FYWSeP }H IDgiH FYWTeN }H IDhjH FYWUeN } H I Dia H FYWVe }H I DtlH FZWWe P:Lettereda }HH I DkmHH FZWXeH* }H IDlnH FZWYeN }H IDmoH FZWZeN } H IDnf H FZW[e }\H(IDyq\H( F[W\e P:Lettered }H\H(IDprH\H((F[$eLI ]e Parent = OL Qe Depth = 0 }\H(IDqs\H( F[W^eN }\H(IDrt\H( F[W_eN } \H(IDsk \H( F[W`e }PH ID~vPH F\WaeP:CodeN }HPH I!DuwHPH F\WbeP }PH I#DvxPH F\WceN }PH I%DwyPH F\WdeN } PH I'Dxp PH F\Wee }6HI)D{6HF]f% P:CodeComPEment }H6HI+Dz|H6H F]WgeP }6HI-D{}6H F]WheN }6HI/D|~6H F]WieN } 6HI1D}u 6H F]Wje }H I3H ^GkeP:CodeC }H I5H ^GleP }H I7H ^GmeN }H I9H ^GneN }H I;H ^Goe }H I= H _Gpe P:CodeASM }H I?H _GqeP }H IAH _GreN }H ICH _GseN }H IEH _Gte }H IG H `Gue P:BodyIndent }H II H `GveP }H IK H `GweN }H IM H `GxeN }H IO H `Gye }H(IQBH( aGze P:Answer1 }H(ISH((aeLI {e Parent = UL Ae Depth = 0 }H(IUH( aG|eN }H(IWH( aG}eN }H(IY H( aG~e dIf" dIgds%sy| %).12/,)&#dIidE l}6DJD6DFb% CSS Export PE Encoding }D6HJDD6H FbWe ISO-8859-1 }6HJDX6H FbW e }DJDWDFc % Export EnPEcoding }DHJDDH FcW e ISO-8859-1 }HJDH FcW e }HKS H  dG e1 }HKU H dG* eTitle }HKW H  dGe dLeftd!Rightd ReferenceddHTMLd"DHTMLd" Headingsd d rd ;d >d Ad Ld OdHTMLB@@ cMapping Table Title. @@ cBody. f@ c Answer1ItalicAnswer: . f@ cBody. @@ cFooter. f@T c TableTitleT:Table : . f@ c BodySpaced. f@N c Numbered N:.< =1>. f@ c...Date. mf@ cl. DateProject. @@ cHeader Double Line. f@  $.6.Z.~..CodeC. f@T cHeading1Body. $f@ c Answer. f@ c NumberedSpaced. f@ cBody. @@ cHeader Double Line. f@ c CellFooting. f@ c CellHeading. f@ c CellBody. @@ cMapping Table Cell. f@ c.Reading. @@7Mapping Table Cell.  f@PcTitleBody. @@ 7Mapping Table Cell. @@ cMapping Table Cell. f@$c.Line Single Line.  f@PcTitleBody. f@ cCellBody. f@ c CellHeading. f@ c Footnote. f@T cHeading2Body. f@T c HeadingRunInBody. f@ c Indented. f@ c TableFootnote. L̀Lf@N c Numbered N:.< =1>. $f@L c$. Lettereda L:.. 6$f@R c6. Romani R:.. $f@LE c$. Lettereda L:.Lettered. f@NE c Numbered1 N:. Lettereda. f@NE c Numbered1 N:. Lettereda. f@T c TableTitleT:Table : . 6$f@R c6. RomanR:.. $f@LE c$. Lettereda L:.Lettered. $f@L c$. LetteredL:.. f@T cHeading1Body. f@ c NumberedSpaced. f@ clDBody. f@NE c Numbered1 N:.Numbered. f@T cHeading1Body. f@ clDBody. 6$f@X c6. Romani X:.. f@ c Bulleted\t. f@N c Numbered N:.< =1>.  f@PcTitleBody. f@ c Bulleted\t. $f@L c$. LetteredL:.. f@ c$Body. 6$f@R c6. Romani R:.. 6$f@R c6. RomanR:.. f@ c BodyIndent. f@  $.6.Z.u..CodeASM. Hf@ cH.. CodeComment. f@ c$Body. f@ c H .uUU .... ..D.Body. 6$f@X c6. RomanX:.. f@   .$.H.l..... .D.h.CodeN. Hf@ cH. LineComment. @@ cMapping Table Cell. @@c*Mapping Table Cell. f@ clDBody. f@ c$Body.  c ccEmphasis c 7 c ڝcccEquationVariables 7  BoldItalic cItalic _ Symbol ڝc c c c c7 c cBold_  Symbol   Computer c c c c c Subscript c Superscript l  WingdingcZZThinMediumDoubleThick@ Very Thin HHHHHFormat A HHHHHFormat BH Mapping TableH Mapping Tableh65HHHHH$bDHH+4?HHH68?HH :C?HHHTDL?HH*H ? @ h( A B C D E h  F G H I J h  K L M N O h  P Q R S T h( UVWXYh Z[\]^h_`abc7h defghChijklm]h(nopqrh stuvwh xyz{|h(}~h h    h  h h h)h  !"#$5h%&'()Oh  *+,-.[h!/ 0 1 2 3 uh "4!5!6!7!8!h!#9":";"<"="©h "a>#?#@#A#B#Td %FC$D$E$d $&FF%G%H%p6%'FI&J&K& &(FL'M'N'')FO(P(Q(((*FR)S)T)()cFU*V*W*Vd ,FX+Y++Z+f +-F[,\,,],r ,.F^-_--`-~ -/Fa.b.5.c.Š.0Fd/e/6/f/¤/1Fg0h070i0¾02Fj1k181l113Fm2n292o224Fp3q3:3r33s4t4;4u4Bh 9Fv5w5x5<5=59?9@9A9B9xd ;:::: :C ;";#;$; =  <<<<> ====? >>>K >@ ???W ?A @@@c @d AAA ;%C&C'C(Cd E)D,D-D DF.E/E0E EQ1FBFCF M#L$L%L NL&M'M(M OM)N*N+N PN,O-O.O QO/P0P1P FP2Q3Q4Q*h S9FCRDRERFRGRh TRFHSISJSKSLSh USFMTNTOTPTQTh VTFRUSUTUUUVUh(WUFWVXVYVZV[Vh(XVF\W]W^W_W`WhYWFaXbXcXdXeXh ZXFfYgYhYiYjYh [YFkZlZmZnZoZ\h(\ZFp[q[r[s[t[Ph ][Fu\v\w\x\y\6h^\Fz]{]|]}]~]h _]^^^^^h `^_____h a_ ` ` ` ` `h(#`aaaaa6cFbbb*bFcccA dddComment @D @<@@ d@ BlackT!WhiteddARedddGreendd BluedCyandMagentad Yellowd PICT Color 1Header/Footer $1Header/Footer $1Header/Footer $2Header/Footer $2IndexIndexCommentCommentSubjectSubjectAuthorAuthorGlossaryGlossaryEquationEquation Hypertext Hypertext  Cross-Ref Cross-Ref Conditional TextConditional TextPositionFMPrivatePositionFMPrivateRangeEndFMPrivateRangeEndFMPrivate HTML Macro HTML Macro M.Times.P Times-Roman FrameRoman M.Times.B Times-Bold FrameRoman M.Courier.PCourier FrameRoman M.Helvetica.BHelvetica-Bold FrameRoman M.Times.BITimes-BoldItalic FrameRomanM.Helvetica.BIHelvetica-BoldOblique FrameRoman M.Times.I Times-Italic FrameRoman M.Symbol.PSymbol FrameRoman FrameRoman FrameRoman M.Wingdings.P Wingdings FrameRomanrCourier6 Helvetica^SymbolbTimesk Wingdings%Regular$Roman MediumBoldRegular ObliqueItalicZpMτoi3Eݦս*_OlO"yB/(9ejHd z\TT䃈,ݞU~%J_OڈG3׽6-Py]d r0b65}i!K=}1|g}}6XT믉V$B_lVg1Ca3c5S N]gsx7K;g*:ڛ8]je$s _8|JMhLƘ!zRǚp0