Aard}   @P   @` P@pHH $ @d HHHHff@  d Footnote TableFootnote**.\t.\t/ - :;,.!? cZ1cZTOCHeading1Heading2   PEquationVariables@f=?H?s???@====== <$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::335577AHHA================>>>>> > > >>>>>>>>>>!>#>%>'>)>*>+>->/>1>3>5>7>9>;>=>?>@>A>C>E>G>I>K>M>O>Q>S>U>W>Y>[>]>_>a>c>e>g>i>j>k>m>o>q>s>u>w>y>{>}>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>????? ? ? ??????????!?#?%?'?)?+?-?/?1?3?5?7?9?;?=???A?C?E?G?J?L?N?P?R?T?V?X?Z?\?^?`?b?d?f?h?j?l?n?p?r?u?w?y?{?}????????????????????????????????????????@@ @ @ @@@@@@@@@@!@#@%@'@)@* ==???;#???;/;2=????????????????@,-@0/@1@24@34@44@54@64@8/@92@:2@;2@<2@=2@>2@?2@@2@A2@B2@C2@D2@E2@F2@G2@H2@I2@J2@K2@L2@N/@O5@P5@Q5@R5dq5+d=d=; HmR=HmRHRHRFootnote Hr@=Hr@HzHz Single LineH靕= Footnote =  HD= HDHH Double LineH=  Double Line= = H֝=  Single Line= d5p77HZ֝=; TableFootnoted=d?靕l d=d1QRUX[^adgjmpsvy| %).1W,܁܁Bm }蝝d =蝝d WaHTML Mapping Table }H蝝d =H蝝d Wa }H蝝d =H蝝d Wa }H蝝d =H蝝d Wa }H蝝d =H蝝d Wa }H=H! FrameMaker PA Source Item }H =H Wa HTML Item }H =H Wa }H=H W aInclude Auto# } H= H W a Comments }H=H W a }HH= HH W aElement }H=#H W a New Topic? }H=H Wa } H= H Wa }H = $H Wa P:Date Line }HH >#%HH WaP }H >$&H WaN }H >%'H WaN } H >&( H Wa }EH >')EH Wa P:Reading }HEH > (*HEH WaP }EH > )+EH WaN }EH >*,EH WaN } EH >+- EH Wa }QH >,.QH WaP:Title }HQH >-/HQH WaH* }QH >.0QH WaN }QH >/1QH WaN } QH >02 QH Wa }]H >13]H WaP:Body }H]H >24H]H W aP }]H > 35]H W!aN }]H >"46]H W"aN } ]H >$57 ]H W#a }iH(>&68iH( W$a P:Numbered1 }HiH(>(79HiH((%aLI &a Parent = OL Q'a Depth = 0 }iH(>,8:iH( W(aN }iH(>.9;iH( W)aY } iH(>0:< iH( W*a }띝H >2;=띝H  W+a P:Heading1 }H띝H >4<>H띝H  W,aH* }띝H >6=?띝H  W-aN }띝H >8>@띝H  W.aN } 띝H >:?A 띝H  W/a }H(><@BH(  W0a P:Numbered }HH(>>ACHH(( 1aP 2a Parent = OL Q3a Depth = 0 }H(>BBDH(  W4aN }H(>DCEH(  W5aY } H(>FDF H(  W6a }H >HEGH  W7a P:CellBody }HH >JFHHH  W8aP }H >LGIH  W9aN }H >NHJH  W:aN } H >PIK H  W;a }H >RJLH  W<aP:CellHeading }HH >TKMHH  W=aP }H >VLNH  W>aN }H >XMOH  W?aN } H >ZNP H  W@a }H >\OQH  WAa P:Footnote }HH >^PRHH  WBaP }H >`QSH  WCaN }H >bRTH  WDaN } H >dSU H  WEa }ȝH(>fTVȝH( WFa P:Bulleted }HȝH(>hUWHȝH((GaLI Ha Parent = UL QIa Depth = 0 }ȝH(>lVXȝH( WJaN }ȝH(>nWYȝH( WKaN } ȝH(>pXZ ȝH( WLa }H >rY[H WMa P:Heading2 }HH >tZ\HH WNaH* }H >v[]H WOaN }H >x\^H WPaN } H >z]_ H WQa }H>|^`HR! P:HeadingRuPAnIn }HH>~_aHH WSaP }H>`bH WTaN }H>acH WUaN } H>bd H WVa }7H >ce7H WWa P:Indented }H7H >dfH7H WXaP }7H >eg7H WYaN }7H >fh7H WZaN } 7H >gi 7H W[a }CH>hjCH\! P:TableFootPAnote }HCH>ikHCH W]aP }CH>jlCH W^aN }CH>kmCH W_aN } CH>ln CH W`a }]H(>mo]H( Waa P:TableTitle }H]H(>npH]H((baLI ca Parent = OL Qda Depth = 0 }]H(>oq]H( WeaN }]H(>pr]H( WfaN } ]H(>qs ]H( Wga }֝H >rt֝H Wha P:BodySpaced }H֝H >suH֝H WiaP }֝H >tv֝H WjaN }֝H >uw֝H WkaN } ֝H >vx ֝H Wla }띝H >wy띝H WmaP:Date }H띝H >xzH띝H WnaP }띝H >y{띝H WoaN }띝H >z|띝H WpaN } 띝H >{} 띝H Wqa }H(>|~H(r! P:NumberedPASpaced }HH(>}HH((saP ta Parent = OL Qua Depth = 0 }H(>~H( WvaN }H(>H( WwaY } H(> H( Wxa }H >H WyaP:DateProject }HH >HH WzaP }H >H W{aN }H >H W|aN } H > H W}a }H >H W~a C:BoldItalic }HH > HH WaSTRONG }H > H WaN }H > H WaN } H > H Wa }H> H! C:EquationPA Variables }HH> HH WaEM }H> H WaN }H>H WaN } H> H Wa }H >H Wa C:Italic }HH >HH W aEM }H >H W aN }H >H W aN } H > H W a }H >H W aC:Bold }HH >HH WaSTRONG }H >H WaN }H >H WaN } H > H Wa }H>H! X:Heading & PAPage }HH>HH Wa See Also }H>H WaN }H>H WaN } H? H Wa })H ?!)H WaX:Page }H)H ? "H)H Wa See Also })H ?!#)H WaN })H ?"$)H WaN } )H ? #% )H Wa }5H? $&5H! X:See HeadPA ing & Page }H5H?%'H5H Wa See Also }5H?&(5H WaN }5H?')5H WaN } 5H?(* 5H W a }OH ?)+OH W!a X:Table All }HOH ?*,HOH W"a See Also }OH ?+-OH W#aN }OH ?,.OH W$aN } OH ?-/ OH W%a }[H? .0[H &! X:Table NumPA ber & Page }H[H?"/1H[H  W'a See Also }[H?$02[H  W(aN }[H?&13[H  W)aN } [H?(24 [H  W*a }uH?*35uH !W+a X:Heading }HuH?,46HuH!,! USE XREF PAFMT }uH?.57uH !W-aN }uH?068uH !W.aN } uH?279 uH !W/a }蝝H?48:蝝H "W0a P:Header }H蝝H?69;H蝝H"1!THROW PAAWAY }蝝H?8:<蝝H "W2aN }蝝H?:;=蝝H "W3aN } 蝝H?<<> 蝝H "W4a }H ?>=?H #W5a }HH ?@>@HH #W6a }H ?B?AH #W7a }H ?D@BH #W8a } H ?FAC H #W9a }d ?IBFd $W:aHTML Options Table }Dd ?KDd $W;a }Dd ?MDd $W<a }D ?OCGD %W=a }DH ?QFHDH %W>a }H ?SGIH %W?a }םD ?UHJםD &W@a Image Format }DםH ?WIKDםH &WAaIMAGGIF }םH ?YJLםH &WBa }D ?[KMD 'WCaBanners }DH ?]LNDH 'WDaN }H ?_MOH 'WEa }ԝD?aNPԝD(F! Banner ReferPA ence Frame }DԝH?cOQDԝH (WGa }ԝH?ePԝH (WHa }D(?g>SD((@)I! Copy Files  Imported by PA Rerefernce }DH(?i>RTDH( @)WJa }H(?k>SUH( @)WKa }DD ?m>TVDD @*WLa }DDH ?o>UWDDH @*WMa }DH ?q>VXDH @*WNa }Vd ?t>W[Vd @+WOaSystem Macros }?Vd ?v>?Vd @+WPa }?Vd ?x>?Vd @+WQa }f? ?z>X\f? @,WRa Macro Name }?fH ?|>[]?fH @,WSa Replace With }fH ?~>\^fH @,WTa Comments }r? ?>]_r? @-WUa StartOfDoc }?rH ?>^`?rH @-WVa }rH ?>_arH @-WWa }~? ?>`b~? @.WXa EndOfDoc }?~H ?>ac?~H @.WYa }~H ?>bd~H @.WZa }??>ce?@/[! StartOfSubPADoc }?H?>df?H @/W\a }H?>egH @/W]a }??>fh?@0^! EndOfSubPADoc }?H?>gi?H @0W_a }H?>hjH @0W`a }??>ik?@1a! StartOfFirstPASubDoc }?H?>jl?H @1Wba }H?>kmH @1Wca }??>ln?@2d! EndOfFirstPASubDoc }?H?>mo?H @2Wea }H?>npH @2Wfa }??>oq?@3g! StartOfLastPASubDoc }?H?>pr?H @3Wha }H?>qsH @3Wia } ??>rt ?@4j! EndOfLastPASubDoc }? H?>su? H @4Wka } H?>tv H @4Wla }&? ?>uw&? @5Wma }?&H ?>vx?&H @5Wna }&H ?>wy&H @5Woa }8d ?>x|8d @6WpaCross-Reference Macros }?8d ?>?8d @6Wqa }?8d ?>?8d @6Wra }H? ?>y}H? @7Wsa Macro Name }?HH ?>|~?HH @7Wta Replace With }HH ?>}HH @7Wua Comments }T??>~T? @8Wva See Also }?TH?>?TH@8w! See Also: PA <$paratext> }TH?>TH @8Wxa }n? ?>n? @9Wya }?nH ?>?nH @9Wza }nH ?>nH @9W{a }d ?> d @:WaGeneral Macros }?d ?>?d @:Wa }?d ?>?d @:Wa }?d ?>?d @:Wa }? ?>"? @;Wa Macro Name d@ d@ d 靕l d@ do  W܁܁Bm }蝝d @ 蝝d  <W|aHeadings Table }H蝝d @ H蝝d  <W}a }H蝝d @  H蝝d  <W~a }H@  H =!Paragraph ForPAmat }HH@ HH  =WaHeading Level }H@ H  =Wa Comments }H@ H >W aTitle }HH@ HH  >Wa }H@ H  >Wa }KH @ KH  ?Wa Heading1 }HKH @ HKH  ?Wa }KH @ KH  ?Wa }WH @ WH  @Wa Heading2 }HWH @  HWH  @W a }WH @" WH  @W a }cH @$ cH  AW a }HcH @& HcH  AW a }cH @( cH  AW a d=8H}?H ?> #?H @;Wa Replace With }H ?>"$H @;WaHead }H ?>#%H @;Wa Comments }? ?>$&? @BWa }?H ?>%'?H @BW a }H ?>&(H @BW!a }H ?>')H @BW"a }d ?>(.d @CW#aCharacter Macros HH;"HH❝+G܁e HH;$3HH**靕l}?d ?>?d @CW$a }?d ?>?d @CW%a }? ?>)/? @DW&a Macro Name }?H ?>.0?H @DW'a Replace With }H ?>/1H @DW(a Comments }? ?>0<? @EW)a HUV ;.HUV ❝3G܁e HUV ;05+HUV 22靕l H$ ;1H$ 5G܁e H$ ;33H$ 44靕l HH;4HHap,,7- `Test and Set Solution 1,` Introduction 2܁ This algorithm solves the critical section problem for  n  processes using a Test and Set instruction (called TaS here). I@9This instruction does the following function atomically: 3`B function  TaS( var  Lock: boolean): boolean; 4` begin 5`TaS := Lock; 6`Lock := true; 7` end ; 9` Algorithm :܁``1 var waiting :  shared array  [0.. n -1]  of  boolean; ;`92  Lock :  shared   boolean; <`. 3  j : 0.. n -1; =`"4  key : boolean; >` ?*`85  repeat (* process P i  *) @UU`26  waiting [ i ] := true; A`!7  key  := true; B`]8  while   waiting [ i ]  and   key   do C`;9  key  :=  TaS ( Lock ); D`410  waiting [ i ] := false; E`,11 (* critical section goes here *) F`E12  j  :=  i  + 1  mod   n ; G`{13  while  ( j  <>  i )  and   not   waiting [ j ]  do H`F14  j  :=  j  + 1  mod   n ; I`<15  if   j  =  i   then J`$16  Lock  := false K`17  else L`518  waiting [ j ] := false; M`19 until  false; Oع8` Comments P܁`Zlines 1-2:These are global to all processes, and are all initialized to  false . Q*`Olines 3-4:These are local to each process P i  and are uninitialized. 1RU3 lines 5-10:This is the entry section. Basically,  waiting [ i ]  is  true  as long as P i  is trying to get into its }critical section; if any other process is in that section, then  Lock  will also be true, and P i  will loop pin lines 8-9. Once P i  can go on, it is no longer waiting for permission to enter, and sets  wait UU ing [ i ]  to  false  (line 10); it then proceeds into the critical section. Note that  Lock  is set to (@Strue  by the  TaS  instruction in line 9 that returns  false . S* ~lines 12-18:This is the exit section. When P i  leaves the critical section, it must choose which other waiting proUU*ygcess may enter next. It starts with the process with the next higher index (line 12). It checks each 6xiprocess to see if that process is waiting for access (lines 13-14); if no-one is, it simply releases the *~lock (by setting  Lock  to  false ; lines 15-16). However, if some other process P j  is waiting for Pentry, P i  simply shanges  waiting [ j ]  to  false  to allow P j  to enter the critical section (lines 17-HUU@18). HH;6HH66 靕lH$ =!:H$ 99靕l H$ =!H$ 8W܁܁h@April 20, 1999ECS 150 Spring 1999Page 1 HUV =!8HHUV GG靕l EGxR=EGxREPwEPw TableFootnote}?H ?>1=?H @EW*a }H ?><H @EW+a d???d?>d@@ 靕l d?>dR=?RUX[^adgjmpsvy| %).1 HUV =!HUV ❝:W܁܁l?Last modified at 10:31 pm on Monday, April 19, 1999 HH=!:HHII 靕l HH=!HH❝HW܁܁e dLeftd!Rightd ReferenceddHTMLd>HTMLd HeadingsĿ@@ QMapping Table Title. Ŀ@@ QBody. f@ QBody. f@ Q BodySpaced. Ŀ@@ QFooter. f@T Q TableTitleT:Table : . f@ Q Bulleted\t. f@ Q...Date. mf@ Ql. DateProject. Ŀ@@ QHeader Double Line. f@T QHeading1Body. f@ Q Numbered.\t. f@E Q Numbered1.\tNumbered. f@ Q NumberedSpaced.\t. f@ Q.Reading. f@ QBody. Ŀ@@ QHeader Double Line. f@ Q CellFooting. f@ Q CellHeading. f@ Q CellBody. Ŀ@@ QMapping Table Cell.  f@PQTitleBody. Ŀ@@/Mapping Table Cell. f@$Q.Line Single Line. Ŀ@@ /Mapping Table Cell. Ŀ@@ QMapping Table Cell. f@ QCellBody. f@ Q CellHeading. f@ Q Footnote. f@T QHeading2Body. f@T Q HeadingRunInBody. f@ Q Indented. f@ Q TableFootnote. f@T Q TableTitleT:Table : .   f@PQTitleBody.  f@T QHeading1Body. f@ Q .$.H.l..... .D.h.Code. f@   .$.H.l..... .D.h.Code. Hf@ QH. LineComment. f@ Q .$.H.l..... .D.h.Code. Hf@ QH. LineComment.  Q QQ蜜Emphasis Q蜜 / Q QQ蜜EquationVariables / 蜜 BoldItalic ۸QItalic Q Q/ Q QBold       Q Q QZZThinMediumDoubleThick@ Very Thin HHHHHFormat A HHHHHFormat BH Mapping TableH Mapping Tableh*|#HHHHHf$*DHH+5?HH&69?HH :B?HHH CE?HH*6 ? @ 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(nopqr֝h stuvw띝h 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#B# %C$D$E$ $&F%G%H%ם %'I&J&K& &(L'M'N'ԝ')O(P(Q(((*@R)S)T)D )@U*V*W*V ,@X+Y+Z+f +-@[,\,],r ,.@^-_-`-~ -/@a.b.c..0@d/e/f//1@g0h0i002@j1k1l113@m2n2o224@p3q3r3 35@s4t4u4& 4@v5w5x58 7@y6z6{6H 68@|7}7~7T79@888n 8@999 ;@:::: :B@ ;";#;$;蝝 =  <<<<> ====? >>>K >@ ???W ?A @@@c @ AAA ;@%B&B'B(B D@)C,C-C CE@.D/D0D D@1ETey`L)23N\"L-WwH㓟P/@@UW