Aa!sr|}   0  @ P @`@@HH $ @d HHHH̀̀̀ff@  d Footnote TableFootnote**.\t.\t/ - :;,.!?/ d00e;TOCHeading1Heading2   UEquationVariablesL/ ACfCCCDD#AAAAAA  <$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++A33557A<<>>@@A ABBBBB B B BBBBBBBBBB!B#B%B'B)B+B-B/B1B3B5B7B9B;B=B?BABCBEH#H%BIBKBMBOBQBSBUBWBYB[HGHIB_BaBcBeBgBiBkBmBoBqBsBuBwByB{B}BBBBHHBBBBBBBBBBBBBBBBBBBBBBBBBHHBBBBBBBBBBBBBBBIIBBBBBBBBBBBBBBBBBBCCCCC C C CCCCCCCCCC!C#C%C'C)C+C-C/C1C3C5C7C9C;C=C?CACCCECGCICKCMCOCQCSCUCWCYC[C]C_CaCcCeChCjClCnCpCrCtCvCxCzC|C~CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCIIICCCCCCCCCG:G<G>D%D'D)D+D-D/D1D3D5D7D9D;D=D?DA'DH$@D,CCCCC;#$CCC;/;2CD 1.DAnswer: D(2.D(3.DDDDD D DDDDDDD$DD(4.DE(Answer: EAnswer: E)E*E1Answer: E2 E3 E6E7FCE9 FDFEECEDEEEHEqFEsAAA$FFE~FFFFFFFFFFFFFFFFG@GBGDGFGHGJGLIIIIIJJJJJJ J JJJJJJJJJJ J"J$J&J(J*J,J.J0J2J4J6J8J:J<J>J@JBJD?PJFJHJJJLJNJPJRJTJVJXJZJ\J^J`JbJdJfJhJjJlJnJpJrJtJvJxJzJJJJJJKKK'K)KKKKKKdq5+dEI HHˆEJHHˆ[*?*`:S 3  receives REPLY(3, 31) from  S 3  A`35]H W!eN }]H B@46]H W"eN } ]H BB57 ]H W#a }iH(BD68iH( W$e P:Numbered1 }HiH(BF79HiH(('eLI %e Parent = OL Q&e Depth = 0 }iH(BJ8:iH( W(eN }iH(BL9;iH( W)eY } iH(BN:< iH( W*a }H BP;=H  W+e P:Heading1 }HH BR<>HH  W,eH* }H BT=?H  W-eN }H BV>@H  W.eN } H BX?A H  W/a }H(BZ@BH(  W0e P:Numbered }HH(B\ACHH(( 3eP 1e Parent = OL Q2e Depth = 0 }H(B`BDH(  W4eN }H(BbCEH(  W5eY } H(BdDF H(  W6a }H BfEGH  W7e P:CellBody }HH BhFHHH  W8eP }H BjGIH  W9eN }H BlHJH  W:eN } H BnIK H  W;a }H BpJLH  W<eP:CellHeading }HH BrKMHH  W=eP }H BtLNH  W>eN }H BvMOH  W?eN } H BxNP H  W@a }H BzOQH  WAe P:Footnote }HH B|PRHH  WBeP }H B~QSH  WCeN }H BRTH  WDeN } H BSU H  WEa }H(BTVH( WFe P:Bulleted }HH(BUWHH((IeLI Ge Parent = UL QHe Depth = 0 }H(BVXH( WJeN }H(BWYH( WKeN } H(BXZ H( WLa }H BY[H WMe P:Heading2 }HH BZ\HH WNeH* }H B[]H WOeN }H B\^H WPeN } H B]_ H WQa }HB^`HR% P:HeadingRuPEnIn }HHB_aHH WSeP }HB`bH WTeN }HBacH WUeN } HBbd H WVa }7H Bce7H WWe P:Indented }H7H BdfH7H WXeP }7H Beg7H WYeN }7H Bfh7H WZeN } 7H Bgi 7H W[a }CHBhjCH\% P:TableFootPEnote }HCHBikHCH W]eP }CHBjlCH W^eN }CHBkmCH W_eN } CHBln CH W`a }]H(Bmo]H( Wae P:TableTitle }H]H(BnpH]H((deLI be Parent = OL Qce Depth = 0 }]H(Boq]H( WeeN }]H(Bpr]H( WfeN } ]H(Bqs ]H( Wga }H BrtH Whe P:BodySpaced }HH BsuHH WieP }H BtvH WjeN }H BuwH WkeN } H Bvx H Wla }H BwyH WmeP:Date }HH BxzHH WneP }H By{H WoeN }H Bz|H WpeN } H B{} H Wqa }H(B|~H(r% P:NumberedPESpaced }HH(B}HH((ueP se Parent = OL Qte Depth = 0 }H(B~H( WveN }H(BH( WweY } H(B H( Wxa }H BH WyeP:DateProject }HH BHH WzeP }H BH W{eN }H BH W|eN } H B H W}a }H BH W~e C:BoldItalic }HH B HH WeSTRONG }H B H WeN }H B H WeN } H B H Wa }HB H% C:EquationPE Variables }HHB HH WeEM }HB H WeN }HBH WeN } HC H Wa }H CH We C:Italic }HH CHH W eEM }H CH W eN }H CH W eN } H C  H W a }H C H W eC:Bold }HH CHH WeSTRONG }H CH WeN }H CH WeN } H C H Wa }HCH% X:Heading & PEPage }HHCHH We See Also }HCH WeN }HCH WeN } HC H Wa })H C !)H WeX:Page }H)H C" "H)H We See Also })H C$!#)H WeN })H C&"$)H WeN } )H C(#% )H Wa }5HC*$&5H% X:See HeadPE ing & Page }H5HC,%'H5H We See Also }5HC.&(5H WeN }5HC0')5H WeN } 5HC2(* 5H W a }OH C4)+OH W!e X:Table All }HOH C6*,HOH W"e See Also }OH C8+-OH W#eN }OH C:,.OH W$eN } OH C<-/ OH W%a }[HC>.0[H &% X:Table NumPE ber & Page }H[HC@/1H[H  W'e See Also }[HCB02[H  W(eN }[HCD13[H  W)eN } [HCF24 [H  W*a }uHCH35uH !W+e X:Heading }HuHCJ46HuH!,% USE XREF PEFMT }uHCL57uH !W-eN }uHCN68uH !W.eN } uHCP79 uH !W/a }HCR8:H "W0e P:Header }HHCT9;HH"1%THROW PEAWAY }HCV:<H "W2eN }HCX;=H "W3eN } HCZ<> H "W4a }©H C\=?©H #W5e P:Answer }H©H C^>@H©H #W6eP }©H C`?A©H #W7eN }©H Cb@B©H #W8eN } ©H CdA ©H #W9a }»d Cg:]F»d C$W:aHTML Options Table }D»d Ci:D»d C$W;a }D»d Ck:D»d C$W<a }D Cm:CGD C%W=eControl }DH Co:FHDH C%W>eValue }H Cq:GIH C%W?e Comments }D6Cs:HJD6 C&W@e Image Format }DH6Cu:IKDH66C&A% 0001IMAGGIF p MACP0001GIEF }H6Cw:JLH6 C&WBa }D Cy:KMD C'WCeBanners }DH C{:LNDH C'WDeN }H C}:MOH C'WEa }DC:NPDC(F% Banner ReferPE ence Frame }DHC:OQDH C(WGe }HC:PRH C(WHa }D(C:QSD((C)I$% Copy Files  Imported by PE Rerefernce }DH(C:RTDH( C)WJe }H(C:SUH( C)WKa }DD(C:TVDD((C*L% Copy Files  Imported by PE Reference }DDH(C:UWDDH( C*WMeN }DH(C:V%DH( C*WNa }Vd C:$[Vd C+WOaSystem Macros }?Vd C:?Vd C+WPa }Vd C:Vd C+WQa }f? C:X\f? C,WRe Macro Name }?fH C:[?fH C,WSe Replace With }fH C:^fH C,WTe Comments }r? C:]_r? C-WUe StartOfDoc }?rH C:^?rH C-WVa }rH C:arH C-WWa }~? C:`b~? C.WXe EndOfDoc }?~H C:aU?~H C.WYa }~H C:Ud~H C.WZa }?C:ce?C/[% StartOfSubPEDoc }?HC:dV?H C/W\a }HC:VgH C/W]a }?C:fh?C0^% EndOfSubPEDoc }?HC:gW?H C0W_a }HC:WjH C0W`a }?C:ik?C1a% StartOfFirstPESubDoc }?HC:jX?H C1Wba }HC:XmH C1Wca }?C:ln?C2d% EndOfFirstPESubDoc }?HC:mY?H C2Wea }HC:YpH C2Wfa }?C:oq?C3g% StartOfLastPESubDoc }?HC:pZ?H C3Wha }HC:ZsH C3Wia } ?C:rt ?C4j% EndOfLastPESubDoc }? HC:s[? H C4Wka } HC:[ H C4Wla }H I:bwH C5Gme C:Symbol }H I:vxH C5GneEM }H I:w\H C5GoeN },d C|,d  6WpaCross-Reference Macros }?,d C?,d  6Wqa },d C,d  6Wra }<? Cy}<?  7Wse Macro Name }?<H C|~?<H  7Wte Replace With }<H C}<H  7Wue Comments }H?C~H?  8Wve See Also }?HHC?HH 8w% See Also: PE <$paratext> }HHCHH  8Wxa }Vd G9:Vd C+Wye }fH G;:\]fH C,WzeHead }rH G=:_`rH C-W{e }hd C hd  :WaGeneral Macros }?hd C?hd  :Wa }hd Chd  :Wa }hd Chd  :Wa }x? C"x?  ;We Macro Name dD  dD! d l dD" di  WBm }d D$ d  <W|aHeadings Table }Hd D& Hd  <W}a }Hd D( Hd  <W~a }HD* H  =WeHeading Level }HHD, HH =%Paragraph ForPEmat }HD. H  =We Comments }HD0 H >W e2 }HHD2 HH  >We Heading1 }HD4 H  >Wa }KH D6 KH  ?We3 }HKH D8 HKH  ?We Heading2 }KH D: KH  ?Wa }WHD< WH  @We1 }HWHD> HWH @W eTitle }WHD@ WH  @W a HHˆELHHˆ7 l}? FHD?  FWGe EGxRAEGxREPwEPw TableFootnote}?xH C #?xH  ;We Replace With }xH C"$xH  ;WeHead }xH C#%xH  ;We Comments }? C$&?  BWa }?H D%'?H  BW a }H D&(H  BW!a }H D')H  BW"a }d D(.d  CW#aCharacter Macros HHˆ;"HHˆ+Ge HHˆ;$3HHˆ**l}?d D ?d  CW$a }d D d  CW%a }? D )/?  DW&e Character }?H D.0?H  DW'e Replace With }H D/1H  DW(e Comments }? D08?  EW)e HUV ;.HUV 3Ge HUV ;05+HUV 22l H$ ;1H$ 5Ge H$ ;33H$ 44l HHˆ;4HHˆ€..7  `Answers to Homework #3  `6Due Date : February 27, 2001 Points : 70 @ }( 20 points ) Show that in Lamports algorithm the critical section is accessed according to the increasing order of L@(timestamps. (text, problem 6.7, p. 149) ! dRecall that two basic assumptions of Lamports algorithm (or any other distributed mutual exclusion algorithm, for that matter) is that messages sent from process  p  to process  q  arrive in the order they are sent, and @Qif a message is sent then it will arrive ( i.e. , no messages are lost). /* Proof by contradiction. Suppose process  p 1  issues a request to enter the critical section at time  t 1 ,  p 2  issues a 0Csimilar request at time  t 2  with  t 1  <  t 2 , and  p 2  enters first. This means that  p 2 s request is at the head of its queue. As the queues are ordered by timestamp, this means  p 1 s request has not arrived. If  p 2  enters, though, it also received a message from  p 1  with a timestamp higher than  t 2 . This implies that  p 1 s request has a timestamp Shigher than  t 2  (which is false as  t 1  <  t 2 ) or  p 2  never received  p 1 s request. The latter is possible only if either  p 1 s request was lost, or messages from  p 1  to  p 2  arrive out of order. Both these contradict the above basic assump@[tions. Hence  p 2  cannot enter the critical section first, proving the claim. UU̳ |( 20 points ) Show that in the Ricart-Agrawala algorithm, the critical section is accessed according to the increas̲@=ing order of timestamps. (text, problem 6.5, part 1, p. 149) 1*} Proof by contradiction. Suppose process  p 1  issues a request to enter the critical section at time  t 1 ,  p 2  0Aissues a similar request at time  t 2  with  t 1  <  t 2 , and  p 2  enters first. This means that  p 2  has received reply messages from all other processes including  p 1 . But  p 1  will send such a message only if it is neither requesting nor executing the critical section (which is false) or if  p 2 s requests timestamp is smaller than that of  p 1 s request (which is "also false). Hence  p 1  will not send a reply to  p 2 s request, and so  p 2  cannot enter the critical section first. This UU@+contradicts hypothesis, proving the claim. G {( 30 points ) On p. 145, the text discusses the greedy strategy for Raymonds tree-based algorithm, and notes that 0Sqit can cause starvation. Please give an example of the application of this algorithm to a situation in which the @Ggreedy strategy causes starvation, but the regular algorithm does not. 0kݫ`KThere are two answers to this question, depending on how one views site. 12wݪ qIf there are multiple processes at each site, the processes can genetate a stream of requests to enter the critiycal section. As the greedy nature of the algorithm requires the site to honor requests generated at that site first, the @atoken stays at the site and any other site with a request to enter the critical section starves. !3 sIf there is a single process at each site, starvation will not occur. Observe that, after the process finishes exe~cuing in the critical section, the token will be forwarded as indicated by the  holdier  variable. Given this observa@\tion, the proof showing no starvation in both the greedy and non-greedy cases are the same. -2` Extra Credit .ݤ v( 30 points ) Does Maekawas algorithm access the critical section according to the increasing order of timesݣ@atamps? Either show that it does or provide a counterexample. (text, problem 6.5, part 2, p. 149) 4*n`HThe claim is false. Consider the following situation, with three sites: 5**m`3R 1  = {  S 1 ,  S 2  } R 2  = {  S 2 ,  S 3  } R 3  = {  S 1 ,  S 3  } 6UU`6These satisfy the conditions for Maekawas algorithm. 7*`Let the clocks at sites 1, 2, and 3 be  C 1  = 10,  C 2  = 20, and  C 3  = 30, respectively. Then: 8(`MS 2  sends REQUEST(2, 20) to  S 2  and  S 3  9`;S 2  receives REQUEST(2,20) from  S 2  ;`0S 2  sends REPLY(2, 21) to  S 2 <`5S 2  receives REPLY(2, 21) from  S 2 =`HS 3  sends REQUEST(3, 30) to  S 1  and  S 3 @`;S 3  receives REQUEST(3,30) from  S 3  A>`5S 3  sends REPLY(3, 31) to  S 3  HHˆ;6HHˆ66 l}?H D19?H  EW*e¢ }H D8RH  EW+a dDBBdA<@H$ A;>H$ == l H$ A;H$ <WDlHAnswers to Homework #3 ECS 251 Winter 2001Page  1  HUV A;<@HUV ?? l HUV A;HUV >WEl>Last modified at 4:45 pm on Monday, March 19, 2001 HHˆA;>HHˆAA l HHˆA;HHˆ@WFe dD:d!CC l dD:d@uB|wrmhc^vCFILORU%"X[^adgjmpsy| %).1ROLIF }?H F E?H  FWHe... }H FDH  FWJe }? FKG?  GWKe }?H FFH?H  GWLe- }H FG H  GWMe }? FNJ?  HWNe }?H FIK?H  HWOe-- }H FJFH  HWPe }? FQM?  IWQe }?H FLN?H  IWRe° }H FMIH  IWSe }? FTP?  JWTe }?H FOQ?H  JWUe® }H FPLH  JWVe }? F9S?  KWWe }?H FRT?H  KWXe© }H FSOH  KWYe }~H G?:bc~H C.WZe }HGA:efH C/W[e }HGC:hiH C0W\e }HGE:klH C1W]e }HGG:noH C2W^e }HGI:qrH C3W_e } HGK:tu H C4W`e }H I:x]H C5GaeN }H I:\CH C5Gbe }H I:g_H C9Gce C:Subscript }H I:^`H C9GdeEM }H I:_aH C9GeeN }H I:`bH C9GfeN }H J:avH C9Gge }H J:ldH CLGhe C:Emphasis }H J:ceH CLGieEM }H J:dfH CLGjeN }H J :egH CLGkeN }H J :f^H CLGle }H J :qiH CMGme C:Computer }H J:hjH CMGneEM }H J:ikH CMGoeN }H J:jlH CMGpeN }H J:kcH CMGqe }H(J:vnH( CNGre P:Romani }H(J:moH((CNseLI -e Parent = OL A.e Depth = 0 }H(J:npH( CNGteN }H(J:oqH( CNGueN }H(J:phH( CNGve }H(J!:{sH( COGweP:Roman }H(J#:rtH((COxeLI +e Parent = OL A,e Depth = 0 }H(J%:suH( COGyeN }H(J':tvH( COGzeN }H(J):umH( COG{e }H J+:xH CPG|eP:Line }H J-:wyH CPG}eP }H J/:xzH CPG~eN }H J1:y{H CPGeN }H J3:zrH CPGe }H(J5:}H( CQGe P:Lettereda }H(J7:|~H((CQeLI )e Parent = OL A*e Depth = 0 }H(J9:}H( CQGeN }H(J;:~H( CQGeN }H(J=:wH( CQGe }H(J?: H( CRGe P:Lettered }H(JA:H((CReLI 'e Parent = OL A(e Depth = 0 }H(JC:H( CRGeN }H(JE:H( CRG eN }H(JG:|H( CRG e }HJI:HCSg % P:CodeComEment }HJK:H CSG eP }HJM: H CSGeN }HJO: H CSGeN }HJQ: H CSGe }H JS H TGeP:CodeC }H JU H TGeP }H JW H TGeN }H JY H TGeN }H J[H TGe }H J]H UGe P:CodeASM }H J_H UGeP }H JaH UGeN }H JcH UGeN }H Je H UGe }H JgH VGe P:BodyIndent }H JiH VGeP }H JkH VGeN }H JmH VGeN }H JoH VGe }H(JqBH( WG e P:Answer1 }H(JsH((W!eLI %e Parent = UL A&e Depth = 0 }H(JuH( WG"eN }H(JwH( WG#eN }H(JyH( WG$e dJ!! dJdyE!y| %).1ROLIF dJdB  l}DK:'#DCXg/% CSS Export E Encoding }HK:"$H CXG0e }HK:#XH CXG1e }DK:W&DCYg2% Export EnEcoding }HK:%'H CYG3e }HK:&"H CYG4e dLeftd;Rightd ReferenceddHTMLd :HTMLd HeadingsddHTML @@ VMapping Table Title. @@ VBody. @@V Mapping Table Cell. f@ V Answer1ItalicAnswer: . @@ VFooter. f@T V TableTitleT:Table : . $f@ V Answer. f@T VHeading2Body. f@NE V Numbered1 N:.Numbered. $f@ V DAnswer. f@ V Answer1ItalicAnswer: . f@ V Answer. f@ VAnswer. @@ VHeader Double Line. f@ V CellFooting. f@ V CellHeading. f@ V CellBody. @@ VMapping Table Cell. @@1Mapping Table Cell. @@ 1Mapping Table Cell. @@ VMapping Table Cell.  f@PVTitleBody. f@ VBody. f@ VBody. L̀Lf@N V 6Numbered N:.< =1>. f@ V BodySpaced. f@ V. BodySpaced Single Line. f@ V Bulleted\t. f@ V...Date. mf@ Vl. DateProject. @@ VHeader Double Line. f@  $.6.Z.~..CodeC. f@T VHeading1Body. $f@ V Answer. f@ V NumberedSpaced. f@ V.Reading.  f@PVTitleBody. f@$V.Line Single Line. f@ VCellBody. f@ V CellHeading. f@ V Footnote. f@T VHeading2Body. f@T V HeadingRunInBody. f@ V Indented. f@ V TableFootnote. f@T V TableTitleT:Table : . f@NE V Numbered1 N:.Numbered. $f@L V$. Lettereda L:.. $f@L V$. LetteredL:.. L̀Lf@N V Numbered N:.< =1>. 6$f@R V6. Romani R:.. 6$f@R V6. RomanR:.. f@ V BodyIndent. f@  $.6.Z.u..CodeASM. Hf@ VH.. CodeComment. V V VItalic V 1 V ڝVV VV V ڝV VVEmphasis V1 V  SubscriptVEquationVariables 1  BoldItalic VItalic VBoldR Symbol  ComputerZZThinMediumDoubleThick@ Very Thin HHHHHFormat AH Mapping Table HHHHHFormat BH$$$ Mapping Tableh6þ5HHHHH$XDHH+4?HHH68?HH :B?HHHTCF?HH*0<@HHH@h h h !"h #$%&'Eh ()*+,Qh -./01]h 23456ih( 789:;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 "W>#?#@#A#B#» %CC$D$E$ $&CF%G%H%6%'CI&J&K& &(CL'M'N'')CO(P(Q(((*CR)S)T)D()YCU*V*W*Vd ,CX+Y++Z+f +-C[,\,,],r ,.C^-_--`-~ -/Ca.b.U.c..0Cd/e/V/f//1Cg0h0W0i002Cj1k1X1l113Cm2n2Y2o224Cp3q3Z3r3 3Cs4t4[4u4h 9Cv5w5x5\5]5,d 7 y6z6{6< 68 |7}7~7H7 888h L5C^9_9`9a9b9hd ; ::::x :B  ;";#;$; =  <<<<> ====? >>>K >@ ???W? @@@ ; %B&B'B(Bd D )C,C-C CE .D/D0D DK 1E8E9E G  FDFEF HF FGGGHG IG IHJHKH JH LIMINI KI OJPJQJ EJ RKSKTKh M9CcLdLeLfLgLh NLChMiMjMkMlMh(OMCmNnNoNpNqNh(PNCrOsOtOuOvOh QOCwPxPyPzP{Ph(RPC|Q}Q~QQQh(SQCRRRRRhTRCSSS S Sh US T T TTTh VTUUUUUh WUVVVVVh(#VWWWWWYC"X#X$X*XC%Y&Y'YComment A AAd@ BlackT!WhiteddARedddGreendd BluedCyandMagentad YellowHeader/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.Helvetica.BHelvetica-Bold FrameRoman M.Courier.PCourier FrameRoman M.Times.I Times-Italic FrameRomanM.Helvetica.BIHelvetica-BoldOblique FrameRoman FrameRoman FrameRomanbCourier0 HelveticaQSymbolUTimes#Regular$Roman MediumBoldRegular ObliqueItalicѿRŽ*c9( gDqBsZC*P˷,N:{7.V5onf`BLfnP$SqT_.fYe &Xc0Bs)F҄H6' 5E|q|+ZGTsC%l _]s]Yr