Aar큀  0  P p` p0 `@``HH $ @d HHHH̀̀̀ff@  d Footnote TableFootnote**.\t.\t/ - :;,.!?72 cN, dTOCHeading1Heading2   BEquationVariablesL ;`<<=7=P=i=;B;D;F;HA&UBaBu  <$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<<>>@@A6;b;d;f;h;j;l;n;p;r;t;v;x;z;|;~;;;;;;;;;;;;;;;;;;;;;IDI;;;;;;;;;IDI;;;;;;;;;;;;;;;;;;;JE3J;;;;;;;;;<<<<<< < <<<<<<<<JZEJ\<"<$<&<(<*<,<.<0<2<4<6<8<:<<JEJA?A@AAABACADAEAFBBBAJAKALAMANAOAPAQARASATAUEAVAWAXAYAZA[A\A]A^AjWAkEAlBEB B B B B B B B B B B B B C C C C C C C C C C  C  C  C  C  C C C C CEAAAAAAAAA#AEACECCCCCCCCC C!C"C#C$C%C&C'C(C)C*C+C,C-C.C/C0C1EAAAAAAAAAAKA#AEAAEA A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A AEAAABBBBB#BEBBEBBBB B B B B B BB B B B  B! B" B# B$B% B& B' B( B) B* B+EB,B-B.B/B0PB=#B>EB?B@EBA BB BC BD BE BF BG BH BI BJ BK BL BM BN BO BPEBQBRBSBTBUB]#B^EB_B`EBcBeBgBiBkBmBoBqBsBtBwByB{B}BBBBBBBB#BEBBEB B B B B B B B B B B B B B B B B B B B B BEBBBB)B#BEBBEBB B B B B B B B B B B B B B B B B B B B B B B B B B BB BB BEBBBBBFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF GCGGGGGGHfHh Hjdq5+d? 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'({(rmhc^vCFILORUX[^adgjmpsy| %).1ROLI:!W/@m }d ;ad WaHTML Mapping Table }Hd ;cHd Wa }Hd ;eHd Wa }Hd ;gHd Wa }Hd ;iHd Wa }H&;kH&g% FrameMaker E Source Item }H ;mH We HTML Item }H ;oH Wa }H&;qH& W eInclude Auto# } H&;s H& W e Comments }H;uH W a }HH;w HH W eElement }H;y#Hg %New Web EPage? }H;{H Wa } H;} H Wa }H ; $H We P:Date Line }HH ;#%HH WeP }H ;$&H WeN }H ;%'H WeN } H ;&( H Wa }EH ;')EH We P:Reading }HEH ;(*HEH WeP }EH ;)+EH WeN }EH ;*,EH WeN } EH ;+- EH Wa }QH ;,.QH WeP:Title }HQH ;-/HQH WeH* }QH ;.0QH WeN }QH ;/1QH WeN } QH ;02 QH Wa }]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#a }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*a }H ;;=H  W+e P:Heading1 }HH ;<>HH  W,eH* }H ;=?H  W-eN }H ;>@H  W.eN } H ;?A H  W/a }H(;@BH(  W0e P:Numbered }HH(;ACHH(( 2eP 1e Parent = OL A3e Depth = 0 }H(;BDH(  W4eN }H(;CEH(  W5eY } H(;DF H(  W6a }H ;EGH  W7e P:CellBody }HH ;FHHH  W8eP }H ;GIH  W9eN }H ;HJH  W:eN } H ;IK H  W;a }H ;JLH  W<eP:CellHeading }HH ;KMHH  W=eP }H ;LNH  W>eN }H ;MOH  W?eN } H ;NP H  W@a }H ;OQH  WAe P:Footnote }HH ;PRHH  WBeP }H ;QSH  WCeN }H ;RTH  WDeN } H ;SU H  WEa }H(;TVH( WFe P:Bulleted }HH(;UWHH((HeLI Ge Parent = UL AIe Depth = 0 }H(;VXH( WJeN }H(;WYH( WKeN } H(;XZ H( WLa }H ;Y[H WMe P:Heading2 }HH ;Z\HH WNeH* }H ;[]H WOeN }H ;\^H WPeN } H ;]_ H WQa }H;^`HgR% P:HeadingRuEnIn }HH;_aHH WSeP }H<`bH WTeN }H<acH WUeN } H<bd H WVa }7H <ce7H WWe P:Indented }H7H < dfH7H WXeP }7H < eg7H WYeN }7H < fh7H WZeN } 7H <gi 7H W[a }CH<hjCHg\% P:TableFootEnote }HCH<ikHCH W]eP }CH<jlCH W^eN }CH<kmCH W_eN } CH<ln CH W`a }]H(<mo]H( Wae P:TableTitle }H]H(<npH]H((ceLI be Parent = OL Ade Depth = 0 }]H( H "W4a }©H <=?©H #W5e P:BodyIndent }H©H <>@H©H #W6eP }©H <?A©H #W7eN }©H <@B©H #W8eN } ©H <A ©H #W9a }d <D]Fd F$W:aHTML Options Table }Dd <DDd F$W;a }d <Dd F$W<a }D <DCGD F%W=eControl }DH <DFHDH F%W>eValue }H <DGIH F%W?e Comments }D6<DHJD6 F&W@e Image Format }DH6<DIKDH66F&A2% 0001IMAGGIF p MACP0001GIEF }H6<DJLH6 F&WBa }D <DKMD F'WCeBanners }DH <DLNDH F'WDeN }H <DMOH F'WEa } D<DNP DF(F% Banner ReferPE ence Frame }D H<DOQD H F(WGe } H<DPR H F(WHa }&D(<DQS&D((F)I$% Copy Files  Imported by PE Rerefernce }D&H(<DRTD&H( F)WJe }&H(<DSU&H( F)WKa }ND(<DTVND((F*L$% Copy Files  Imported by PE Reference }DNH(<DUWDNH( F*WMeN }NH(<DVNH( F*WNa }d <D[d F+WOaSystem Macros }?d <D?d F+WPa }d <Dd F+WQa }? <DX\? F,WRe Macro Name }?H <D[?H F,WSe Replace With }H <D^H F,WTe Comments }? =D]_? F-WUe StartOfDoc }?H =D^?H F-WVa }H =DaH F-WWa }? =D`b? F.WXe EndOfDoc }?H = DaU?H F.WYa }H = DUdH F.WZa }?= Dce?F/[% StartOfSubPEDoc }?H=DdV?H F/W\a }H=DVgH F/W]a }?=Dfh?F0^% EndOfSubPEDoc }?H=DgW?H F0W_a }H=DWjH F0W`a }?=Dik?F1a% StartOfFirstPESubDoc }?H=DjX?H F1Wba }H=DXmH F1Wca }2?=Dln2?F2d% EndOfFirstPESubDoc }?2H=!DmY?2H F2Wea }2H=#DYp2H F2Wfa }L?=%DoqL?F3g% StartOfLastPESubDoc }?LH='DpZ?LH F3Wha }LH=)DZsLH F3Wia }f?=+Drtf?F4j% EndOfLastPESubDoc }?fH=-Ds[?fH F4Wka }fH=/D[yfH F4Wla }H FDbwH F5Wme C:Emphasis }HH FDvxHH F5WneEM }H FDw\H F5WoeN }†d =8Du|†d F6WpaCross-Reference Macros }?†d =:D?†d F6Wqa }†d =<D†d F6Wra }–? =>Dy}–? F7Wse Macro Name }?–H =@D|~?–H F7Wte Replace With }–H =BD}–H F7Wue Comments }¢?=DD~¢? F8Wve See Also }?¢H=FD?¢HF8w% See Also: PE <$paratext> }¢H=HD¢H F8Wxa }d CDd F+Wye }H CD\]H F,WzeHead }H CD_`H F-W{e }d =QD d F:WaGeneral Macros }?d =SD?d F:Wa }d =UDd F:Wa }d =WDd F:Wa }? =YD"? F;We Macro Name d= d= d l d= d  WBm }d = d  <W|aHeadings Table }Hd = Hd  <W}a }Hd = Hd  <W~a }H= H  =WeHeading Level }HH= HH =g%Paragraph ForEmat }H= H  =We Comments }H= H >W e2 }HH= HH  >We Heading1 }H= H  >Wa }KH = KH  ?We3 }HKH = HKH  ?We Heading2 }KH = KH  ?Wa }WH = WH  @We4 }HWH = HWH  @W e Lettereda }WH = WH  @W a }cH = cH  AW e5 }HcH = HcH  AW e LineComment }cH = cH  AW a HHˆ?HHˆ W2` HHˆ?HHˆ7H l}? Cc H8?  LW3e }?H =[D #?H F;We Replace With }H =]D"$H F;W eHead }H =_D#%H F;W!e Comments }? =aD$&? FCW"a }?H =cD%'?H FCW#a }H =eD&(H FCW$a }H =gD')H FCW%a }d =jD(.d FDW&aCharacter Macros HHˆ;"HHˆ+Ge HHˆ;$3HHˆ**l}?d =lD?d FDW'a }d =nDd FDW(a }? =pD)/? FEW)e Character }?H =rD.0?H FEW*e Replace With }H =tD/1H FEW+e Comments } ? =vD0B ? FFW,e HUV ;.HUV 3Ge HUV ;05+HUV 22l H$ ;1H$ 5Ge H$ ;33H$ 44l HHˆ;4HHˆ‚f337 `/Interprocess Synchronization and Communication `kGoal: To understand how these are implemented we need to look at what they are and why they are necessary. 5u`Bernstein conditions 6`Ecant read, write or write, write from/to same location concurrently 8` Parallel Programming Constructs 9`Yfork  splits a process,  join  resynchronizes them,  quit  stops one :g`4parbegin, parend  bracket concurrent statements <t*`Critical Section Problem =`mutual exclusion wj` progress 0` bounded wait ?4`Software Solutions @`Petersons solution 1`Lamports bakery algorithm B]`Hardware Solutions C` Test and Set E` Semaphores F`rnon-negative integer variables that can be accessed only using the  wait  and  signal  operations H`#Testing synchronization primitives I`bounded buffer problem 4ݿ`readers-writers problem 7`dining philosophers problem K+*`Abstract datatypes L`classes ;CwS` instances TO` Monitors U`Vmutual exclusion and coordination through  wait ,  signal  operations >h`condition variables A`priority waiting W]`Event counters and sequencers X`/allow synchronization without mutual exclusion D|`'sequencers  vs . eventcounters G`;read ,  advance ,  await ,  ticket ZF` Problems [`lack of hardware support JD`Bshared memory vs. message-based synchronization schemes ]Ր`!Interprocess communication (IPC) ^`send ,  receive Mݥ`$blocking  vs . non-blocking N` capacity O`'explicit  vs . implicit naming P`acknowledgements Q`process terminations R`lost or corrupted messages c6*k`Remote Procedure Calls (RPC) d`[like a regular subroutine to programmer, but the IPC details are all within the subroutine f`ADA g`)accept ,  select  mechanisms Sg`fair internal policy ` A` HHˆ;6HHˆ 66 l}?H Ce !9?H  LWVe... }H Cg 8H  LWYe }? Ci KG?  MW\e d;;<@H$ ;<;>H$ == l H$ ;=;H$ <Wl8January 12, 2000ECS 150 Winter 2000Page 1  HUV ;>;<@HUV ?? l HUV ;?;HUV >WlALast modified at  12:08 am on Friday, January 14, 2000  HHˆ;@;>HHˆAA l HHˆ;A;HHˆ@W` }? H =xD1C? H FFW-e¢ } H =zDB H FFW.a d=~EEd=Dd FF l d=Dd$"rCE"rmhc^vCFILORUX[^adgjmpsy| %).1ROLI:!}?H Ck :H?H  MW_e- }H Cm G!H  MW`e }? Co NJ?  NWae }?H Cq IK?H  NWbe-- }H Cs J:H  NWee }? Cu QM?  OWhe }?H Cw LN?H  OWie° }H Cy MIH  OWje }? C{ TP?  PWke }?H C} OQ?H  PWle® }H C PLH  PWme }? C S?  QWne }?H C RT?H  QWoe© }H C SOH  QWpe }H CDbcH F.Wqe }HCDefH F/Wre }HCDhiH F0Wse }HCDklH F1Wte }2HCDno2H F2Wue }LHCDqrLH F3Wve }fHCDtufH F4Wwe }H FDx]H F5WxeN } H FD\C H F5Wye }H FDg_H F9Wze C:Computer }HH FD^`HH F9W{eEM }H FD_aH F9W|eN }H FD`bH F9W}eN } H FDav H F9W~e }vHFDldvHFR% P:LineComPEment }HvHFDceHvH FRWeH* }vHFDdfvH FRW3eN }vHFDegvH FRW4eN } vHFDf^ vH FRW5e }jH FDqijH FSW6eP:Line }HjH FDhjHjH FSW7eP }jH FDikjH FSW8eN }jH FDjljH FSW9eN } jH FDkc jH FSW:e }^H FDvn^H FTW;e P:Lettereda }H^H FDmoH^H FTW<eH* }^H FDnp^H FTW=eN }^H FDoq^H FTW>eN } ^H FDph ^H FTW?e }6H(FDs6H( FUW@e P:Lettered }H6H(FDrtH6H((FUZ$eLI  e Parent = OL Qee Depth = 0 }6H(FDsu6H( FUWBeN }6H(FDtv6H( FUWCeN } 6H(FDum 6H( FUWDe }H FxH VGEeP:CodeN }H FwyH VGFeP }H FxzH VGGeN }H Fy{H VGHeN }H FzH VGIe }HF}HWgJ% P:CodeComEment }HF|~H WGKeP }HF}H WGLeN }HF~H WGMeN }HFwH WGNe }H F H XGOeP:CodeC }H FH XGPeP }H FH XGQeN }H FH XGReN }H F|H XGSe }H FBH YGTe P:CodeASM }H FH YGUeP }H F H YGVeN }H F H YGWeN }H F H YGXe dG  dG ddR9 ROLI:!dG dE  l}DGDDFZ[% CSS Export PE Encoding }DHGDDH FZW\e ISO-8859-1 }HGDXH FZW]e }vDGDWvDF[^% Export EnPEcoding }DvHGDDvH F[W_e ISO-8859-1 }vHGDvH F[W`e }HHe H  \Gae1 }HHg H \Gb eTitle }HHi H  \Gce P/d@HH HHˆ@FHHˆ%$$H `Bakery Algorithm ,` Introduction  This algorithm solves the critical section problem for  n  processes in software. The basic idea is that of a bakery; cus0Iutomers take numbers, and whoever has the lowest number gets service next. Here, of course, service means entry to @the critical section. n` Algorithm `j1 var choosing :  shared array  [0.. n -1]  of   boolean ; `o2  number :  shared   array  [0.. n -1]  of   integer ; `   `3  repeat  `34  choosing [ i ] := true;  `u5  number [ i ] := max( number [0], number [1],, number -1]) + 1;  `46  choosing [ i ] := false;  `R 7 for   j  := 0  to   n -1  do begin `W8  while   choosing [ j ]  do  (* nothing *); `G9  while   number [ j ] <> 0  and `{ 10  ( number [ j ],  j ) < ( number [ i ], i )  do `11 (* nothing *); `12  end ; `"13 (* critical section *) `/14  number [ i ] := 0; `# 15(* remainder section *) `! 16 until  false; Y` Comments *k "lines 1-2:Here,  choosing [ i ]  is true if  P i  is choosing a number. The number that  P i  will use to enter the y@critical section is in  number [ i ] ; it is 0 if  P i  is not trying to enter its critical section. UUU: qlines 4-6:These three lines first indicate that the process is choosing a number (line 4), then try to assign a *U9~unique number to the process  P i  (line 5); however, that does not always happen. Afterwards,  P i  UU*@indicates it is done (line 6). ** lines 7-12:Now we select which process goes into the critical section.  P i  waits until it has the lowest number UUgof all the processes waiting to enter the critical section. If two processes have the same number, the 0one with the smaller name the value of the subscript goes in; the notation ( a , b ) < ( c , d ) means &true if  a  <  c  or if both  a  =  c  and  b  <  d  (lines 9-10). Note that if a process is not trying to enter the *xcritical section, its number is 0. Also, if a process is choosing a number when  P i  tries to look at it, +@AP i  waits until it has done so before looking (line 8). S}` line 14:Now  P i  is no longer interested in entering its critical section, so it sets  number [ i ]  to 0. HHˆ@FHHˆ KGG ld@KK HHˆ@IHHˆ(''K `Bogus Bakery Algorithm ,` Introduction  }Why does Lamport's Bakery algorithm used a variable called  choosing  (see the algorithm, lines 1, 4, 6, and 8)? It 0Iwis very instructive to see what happens if you leave it out. This gives an example of mutual exclusion being violated if you don't put  choosing  in. But first, the algorithm (with the lines involving  choosing  commented out) so you @#can see what the modification was: z` Algorithm  `|1 var (* choosing :  shared array  [0.. n -1]  of   boolean ;*) !`o2  number :  shared   array  [0.. n -1]  of   integer ; "`   #`3  repeat $`?4 (* choosing [ i ] := true;*) %`u5  number [ i ] := max( number [0], number [1],, number -1]) + 1; &`@6 (* choosing [ i ] := false;*) '`\ 7   for   j  := 0  to   n -1  do begin (`U8 (* while   choosing [ j ]  do  ;*) )`G9  while   number [ j ] <> 0  and *`{ 10  ( number [ j ],  j ) < ( number [ i ], i )  do +`11 (* nothing *); ,`12  end ; -`"13 (* critical section *) .`/14  number [ i ] := 0; /`# 15(* remainder section *) 0`! 16 until  false; 1e`'Proof of Violation of Mutual Exclusion 2dw Suppose we have two processes just beginning; call them p 0  and p 1 . Both reach line 5 at the same time. Now, we'll 0assume both read  number [0]  and  number [1]  before either addition takes place. Let p 1  complete the line, assigning 1 to  number [1] , but p 0  block before the assignment. Then p 1  gets through the  while  loop at lines 9-11 and enters the critical section. While in the critical section, it blocks; p 0  unblocks, and assigns 1 to  number [0]  at UUline 5. It proceeds to the while loop at lines 9-11. When it goes through that loop for  j  = 1, the condition on line 9 is dtrue. Further, the condition on line 10 is false, so p 0  enters the critical section. Now p 0  and p 1  are both in the critical UU?@§ion, viuolating mutual exclusion. 13? The reason for  choosing  is to prevent the  while  loop in lines 9-11 from being  entered  when process  j  is setting 'its  number [ j ] . Note that if the loop is entered and  then  process  j  reaches line 5, one of two situations arises. Either "number [ j ]  has the value 0 when the first test is executed, in which case process  i  moves on to the next process, or +number [ j ]  has a non-zero value, in which case at some point  number [ j ]  will be greater than  number [ i ]  b(since process  i  finished executing statement 5 before process  j  began). Either way, process  i  will enter the critical section before process  j , and when process  j  reaches the  while  loop, it will loop at least until process  i  leaves the @critical section. HHˆ@IHHˆHNJJ ld@NN HHˆ@LHHˆjp,,N4 `Test and Set Solution 5,` Introduction 6 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: 7`B function  TaS( var  Lock: boolean): boolean; 8` begin 9`TaS := Lock; :`Lock := true; ;` end ; <` Algorithm =``1 var waiting :  shared array  [0.. n -1]  of  boolean; >`92  Lock :  shared   boolean; ?`. 3  j : 0.. n -1; @`"4  key : boolean; A` B*`85  repeat (* process P i  *) CUU`26  waiting [ i ] := true; D`!7  key  := true; E`]8  while   waiting [ i ]  and   key   do F`;9  key  :=  TaS ( Lock ); G`410  waiting [ i ] := false; H`,11 (* critical section goes here *) I`E12  j  :=  i  + 1  mod   n ; J`{13  while  ( j  <>  i )  and   not   waiting [ j ]  do K`F14  j  :=  j  + 1  mod   n ; L`<15  if   j  =  i   then M`$16  Lock  := false N`17  else O`518  waiting [ j ] := false; P`19 until  false; Q8` Comments R`Zlines 1-2:These are global to all processes, and are all initialized to  false . S*`Tlines 3-4:These are local to each process  P i  and are uninitialized. TU3 lines 5-10:This is the entry section. Basically,  waiting [ i ]  is  true  as long as  P i  is trying to get into its 0*critical section; if any other process is in that section, then  Lock  will also be true, and  P i  will loop uin 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 . U*%' lines 12-18:This is the exit section. When  P i  leaves the critical section, it must choose which other waiting proUU3ygcess may enter next. It starts with the process with the next higher index (line 12). It checks each ?xiprocess 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 Y"entry,  P i  simply shanges  waiting [ j ]  to  false  to allow  P j  to enter the critical section (lines 17-HUU@18). HHˆ@LHHˆKQMM ld@QQ HHˆ@OHHˆ}..QV `#Classical Synchronization Problems W,` Introduction X uThis handout states three classical synchronization problems that are often used to compare language constructs that I@pher is a plate and to the left of each plate is a fork (so there are five forks, one to the right and one to the left of each |philosopher's plate; see the figure). When a philosopher wishes to eat, he picks up the forks to the right and to the left vof his plate. When done, he puts both forks back on the table. The problem is to ensure that no philosopher will be @=allowed to starve because he cannot ever pick up both forks. ae vThere are two issues here: first, deadlock (where each philosopher picks up one fork so none can get the second) must xnever occur; and second, no set of philosophers should be able to act to prevent another philosopher from ever eating. HHˆ@OHHˆNTPP ldATT HHˆARHHˆŒUUTe@A solution must prevent both. f Ž h gm8`(Figure. The Dining Philosopher's Table Qhm7` HHˆARHHˆQYSS lVA'RVVS A(U =QuickDraw PICT #%v  T XT7S/XT@/\XT.vJXTm.JXTddX"m"[.##########"!*"2;##########"!r"2`##########"d"S##########"i"{W########## =EndInset dA.YY HHˆA/WHHˆ‚//Yi `Producer/Consumer Problem j,` Introduction k`[This algorithm uses semaphores to solve the producer/consumer (or bounded buffer) problem. lV` Algorithm mh`d1 var  buffer :  array  [0.. n -1]  of   item ; nt`L2 full ,  empty ,  mutex :  semaphore ; o`73 nextp ,  nextc :  item ; p`4 begin q`5 full  := 0; r`$6 empty  :=  n ; s`7 mutex  := 1; t`8 parbegin u`09 repeat (* producer process *) v`010(* produce an item in  nextp  *) w`(11 down ( empty ); x`(12 down ( mutex ); y`/13(* deposit  nextp  in buffer *) z`&14 up ( mutex ); {`%15 up ( full ); |`'16 until   false ; }`117 repeat (* consumer process *) ~`'18 down ( full ); `(19 down ( mutex ); `020(* extract an item in  nextc  *) `&21 up ( mutex ); `&22 up ( empty ); `123(* consume the item in  nextc  *) `'24 until   false ; `25 parend ; `26 end . ` Comments  lines 1-3Here,  buffer  is the shared buffer, and contains  n  spaces;  full  is a semaphore the value of which 0˪mis the number of filled slots in the buffer,  empty  is a semaphore the value of which is the number kof emoty slots in the buffer, and  mutex  is a semaphore used to enforce mutual exclusion (so only uone process can access the buffer at a time).  nextp  and  nextc  are the items produced by the pro@2ducer and consumed by the consumer, respectively.   |line 5-7This just initializes all the semaphores. It is the only time anything other than a  down   or an  up  @operation may be done to them.   lline 10Since the buffer is not accessed while the item is produced, we don't need to put semaphores around %@ this part.  4 qlines 11-13Depositing an item into the buffer, however, does require that the producer process obtain exclusive 0@haccess to the buffer. First, the producer checks that there is an empty slot in the buffer for the new |item and, if not, waits until there is ( down ( empty ) ). When there is, it waits until it can obtain zexclusive access to the buffer ( down ( mutex ) ). Once both these conditions are met, it can safely @deposit the item.  s tlines 14-15As the producer is done with the buffer, it signals that any other process needing to access the buffer P@may do so ( up ( mutex ) ). It then indicates it has put another item into the buffer ( up ( full ) ). HHˆA1WHHˆT\XX ldA2\\ HHˆA3ZHHˆ  \   mlines 18-20Extracting an item from the buffer, however, does require that the consumer process obtain exclu0gsive access to the buffer. First, the consumer checks that there is a slot in the buffer with an item deposited and, if not, waits until there is ( down ( full ) ). When there is, it waits until it can obtain zexclusive access to the buffer ( down ( mutex ) ). Once both these conditions are met, it can safely @extract the item. E mlines 21-22As the consumer is done with the buffer, it signals that any other process needing to access the 0Qxbuffer may do so ( up ( mutex ) ). It then indicates it has extracted another item into the buffer @&( up ( empty ) ). l eline 23Since the buffer is not accessed while the item is consumed, we don't need to put semaphores x@around this part. Q` HHˆA5ZHHˆY_[[ ldAa__ HHˆAb]HHˆ//_  `First Readers Writers Problem ,` Introduction `LThis algorithm uses semaphores to solve the first readers-writers problem. V` Algorithm h`71 var wrt ,  mutex : semaphore; t`,2 readcount :  integer ; `3 begin `4 readcount  := 0; `5 wrt  := 1; `6 mutex  := 1; `7 parbegin `,8 repeat (* reader process *) `9(* do something *) `'10 down ( mutex ); `611 readcount  :=  readcount  + 1;  `512 if   readcount  = 1  then !`&13 down ( wrt ); "`%14 up ( mutex ); #`15(* read the file *) $$`, 16 down ( mutex ); %`617 readcount  :=  readcount  - 1; &`518 if   readcount  = 0  then '`$19 up ( wrt ); (`%20 up ( mutex ); )`!21 (* do something else *) *`22 until  false; +`-23 repeat (* writer process *) ,`24(* do something *) -`%25 down ( wrt ); .`26(* write to the file *) /`#27 up ( wrt ); 0`28(* do something else *) 1`29 until  false; 2`30 parend ; 3`31 end . 4` Comments 5 zlines 1-2Here,  readcount  contains the number of processes reading the file, and  mutex  is a semaphore 0cused to provide mutual exclusion when  readcount  is incremented or decremented. The semalphore  wrt  is common to both readers and writers and ensures that when one writer is accessing the @-file, no other readers or writers may do so. 6. lines 4-60:wThis just initializes all the semaphores. It is the only time anything other than a  down  or an  up  noperation may be done to them. As no readers are yet reading the file,  readcount  is initialized to @0 . 7a`^line 9Since the file is not accessed here, we don't need to put semaphores around this part. 8 ulines 10-15Since the value of the shared variable  readcount  is going to be changed, the process must wait P|wuntil no-one else is accessing it ( down ( mutex ) ). Since this process will read from the file, HHˆAd]HHˆ\b^^ ldAebb HHˆAf`HHˆ  b 8mreadcount  is incremented by 1; if this is the only reader that will access the file, it waits until any 2~writers have finished ( down ( wrt ) ). It then indicates other processes may access  readcount  @L( down ( mutex ) ) and proceeds to read from the file. 9 xlines 16-20Now the reader is done reading the file (for now.) It must update the value of  readcount  to indi0zcate this, so it waits until no-one else is accessing that variable ( down ( mutex ) ) and then decrexments  readcount . If no other readers are waiting to read ( readcount  = 0 ), it signals that any reader or writer who wishes to access the file may do so ( up ( wrt ) ). Finally, it indicates it is done @?with  readcount  ( up ( mutex ) ). :l`_line 24Since the file is not accessed here, we don't need to put semaphores around this part. ; lines 25-26The writer process waits ( down ( wrt ) ) until no other process is accessing the file; it then proceeds @to write to the file. < nline 27When the writer is done writing to the file, it signals that anyone who wishes to access the file may P@*do so ( up ( wrt ) ). HHˆAh`HHˆ_eaa ldAee HHˆAcHHˆ‚//e = `Producer Consumer Problem >,` Introduction ?`[This algorithm uses a monitor to solve the producer/consumer (or bounded-buffer) problem. @V` Algorithm Ah`#1 buffer : monitor ; Bt`X2 var  slots :  array  [0.. n -1]  of  item; C`<3 count ,  in ,  out : integer; D`74 notempty ,  notfull : condition; E`P5 procedure   entry   deposit ( data : item); F` 6 begin G`97 if   count  =  n   then H`'8 notfull . wait ; I$`: 9 slots [ in ] :=  data ; J`A10 in  :=  in  + 1  mod   n ; K`-11 count  :=  count  + 1; L`*12 notempty . signal ; M`13 end ; N`_14 procedure   entry   extract ( var   data : item); O`15 begin P`016 if   count  = 0  then Q`)17 notempty . wait ; R$`< 18 data  :=  slots [ out ]; S`C19 out  :=  out  + 1  mod   n ; T`-20 count  :=  count  1; U`)21 notfull . signal ; V`22 end ; W`23 begin X`B24 count  := 0;  in  := 0;  out  := 0; Y`25 end . Z` Comments [ lines 2-4Here,  slots  is the actual buffer,  count  the number of items in the buffer, and  in  and  out  the 0lindices of the next element of  slots  where a deposit is to be made or from which an extraction is cto be made. There are two conditions we care about: if the buffer is not full (represented by the mcondition variable  notfull ), and if the buffer is not empty (represented by the condition variable @notempty ). \ sline 5The keyword  entry  means that this procedure may be called from outside the monitor. It is called Uby placing the name of the monitor first, then a period, then the function name; so, @'buffer . deposit () . ] plines 7-8This code checks to see if there is room in the buffer for a new item. If not, the process blocks on 0%gthe condition  notfull ; when some other process does extract an element from the buffer, then ithere will be room and that process will signal on the condition  notfull , allowing the blocked bone to proceed. Note that while blocked on this condition, other processes may access procedures @within the monitor. ^X plines 9-11This code actually deposits the item into the buffer. Note that the monitor guarantees mutual exclud@sion. _s jline 12Just as a producer will block on a full buffer, a consumer will block on an empty one. This indiPccates to any such consumer process that the buffer is no longer empty, and unblocks exactly one of HHˆAcHHˆbhdd ldAhh HHˆAfHHˆh _@Gthem. If there are no blocked consumers, this is effectively a no-op. ` Sline 14As with the previous procedure, this is called from outside the monitor by @'buffer . extract () . a slines 16-17 This code checks to see if there is any unconsumed item in the buffer. If not, the process blocks on 0fthe condition  notempty ; when some other process does deposit an element in the buffer, then athere will be something for the consumer to extract and that producer process will signal on the jcondition  notempty , allowing the blocked one to proceed. Note that while blocked on this condi@@tion, other processes may access procedures within the monitor. bo klines 18-20This code actually extracts the item from the buffer. Note that the monitor guarantees mutual {@ exclusion. c jline 21Just as a consumer will block on an empty buffer, a producer will block on a full one. This indi0bcates to any such producer process that the buffer is no longer full, and unblocks exactly one of @Gthem. If there are no blocked producers, this is effectively a no-op. Qd`-lines 23-25This is the initialization part. HHˆAfHHˆekgg ldAkk HHˆAiHHˆ|//kf `First Readers Writers Problem g,` Introduction h`LThis algorithm uses a monitor to solve the first readers-writers problem. iV` Algorithm jh`(1 readerwriter :  monitor kt`*2 var readcount : integer; l`!3 writing : boolean; m`94 oktoread ,  oktowrite : condition; n`-5 procedure entry  beginread ; o`6 begin p`47 readcount  :=  readcount  + 1; q`-8 if   writing   then r`(9 oktoread . wait ; s`10 end ; t`;11 procedure   entry   endread ; u`12 begin v`513 readcount  :=  readcount  - 1; w`414 if   readcount  = 0  then x`,15 oktowrite . signal ; y`16 end ; z`>17 procedure   entry   beginwrite ; {`18 begin |`S19 if   readcount  > 0  or   writing   then }`*20 oktowrite . wait ; ~` 21 writing  := true; ` 22 end ; `<23 procedure   entry   endwrite ; `(24 var  i : integer; `25 begin `!26 writing  := false; `427 if   readcount  > 0  then `A28 for   i  := 1  to   readcount `,29 oktoread . signal ; `30 else `+31 oktowrite . signal ;  `32 end ;  `33 begin  `;34 readcount  := 0;  writing  := false;  `35 end .  ` Comments + |lines 1-4Here,  readcount  contains the number of processes reading the file, and  writing  is true when a 07swriter is writing to the file.  Oktoread  and  oktowrite  correspond to the logical conditions of @Ebeing able to access the file for reading and writing, respectively. R ulines 7-9In this routine, the reader announces that it is ready to read (by adding 1 to  readcount ). If a 0^lwriter is accessing the file, it blocks on the condition variable  oktoread ; when done, the writer @Dwill signal on that condition variable, and the reader can proceed. Qy vlines 13-15In this routine, the reader announces that it is done (by subtracting 1 from  readcount ). If no HHˆAiHHˆhnjj ldAnn HHˆAlHHˆ  nemore readers are reading, it indicates a writer may go ahead by signalling on the condition variable @oktowrite .  {lines 19-21In this routine, the writer first sees if any readers or writers are accessing the file; if so, it waits until mthey are done. Then it indicates that it is writing to the file by setting the boolean  writing  to @ true . H lines 26-31Here, the writer first announces it is done by setting  writing  to  false . Since readers have pri0Thority, it then checks to see if any readers are waiting; if so, it signals all of them (as many readers @Ncan access the file simultaneously). If not, it signals any writers waiting. o`(line 34This initializes the variables. A` HHˆAlHHˆkqmm ldBqq HHˆBoHHˆ//q `Monitors and Semaphores ,` Introduction  sThis handout describes how to express monitors in terms of semaphores. If an operating system provided semaphores I@Tas primitives, this is what a compiler would produce when presented with a monitor. b` Algorithm t`U1 var mutex ,  urgent ,  xcond :  semaphore ; `D2 urgentcount ,  xcondcount :  integer ; `?The body of each procedure in the monitor is set up like this: `%3 down ( xmutex ); `4(* procedure body*) `45 if   urgentcount  > 0  then `#6 up ( urgent )  ` 7 else !`#8 up ( mutex ); "`EEach  x . wait  within the procedure is replaced by: #`59 xcondcount  :=  xcondcount  + 1; $$`: 10  if  urgentcount  > 0  then %`) 11 up ( urgent ) &` 12 else '`$13 up ( mutex ); (`%14 down ( xcond ); )`615 xcondcount  :=  xcondcount  - 1; *`GEach  x . signal  within the procedure is replaced by: +`816 urgentcount  :=  urgentcount  + 1; ,$`? 17  if  xcondcount  > 0  then begin -`, 18 up ( xcondsem ); .`'19 down ( urgent ); /`20 end ; 0`821 urgentcount  :=  urgentcount  - 1; 1` Comments 2 |line 1The semaphore  mutex  is initialized to  1  and ensures that only one process at a time is executing kwithin the monitor. The semaphore  urgent  is used to enforce the requirement that processes that fsignal  (and as a result are suspended) are to be restarted before any new process enters the monuitor. The semaphore  xcond  will be used to block processes doing  wait s on the condition variable ix . Note that if there is more than one such condition variable, a corresponding semaphore for each @qcondition variable must be generated. Both  urgent  and  xcond  are initialized to  0 . 3 vline 2The integer  urgentcount  indicates how many processes are suspended as a result of a  signal  0 moperation (and are therefore waiting on the semaphore  urgent ); the counter  xcondcount  is kassociated with the condition variable  x , and indicates how many processes are suspended on that @Hcondition ( i.e. , suspended on the semaphore  xcond ). 41 mlines 3-8Since only one process at a time may be in the monitor, the process entering the monitor procedure 0=zmust wait until no other process is using it ( down ( mutex ) ). On exit, the process signals others ethat they may attempt entry, using the following order: if any other process has issues a signal and been suspended ( i.e. ,  urgentcount  _  0 ), the exiting process indicates that one of those is to be xcontinued ( up ( urgent ) ). Otherwise, one of the processes trying to enter the monitor may do so @&( up ( mutex ) ). Q5| lines 9-15First, the process indicates it will be executing an  x . wait  by adding  1  to  xcondcount . It then HHˆB oHHˆntpp ldB tt HHˆB rHHˆl  t5esignals some other process that that process may proceed (using the same priority as above). It sus0|pends on the semaphore  xcond . When restarted, it indicates it is done with the  x . wait  by subtracting  1  from  xcondcount , and proceeds. Note that the  down ( xcond )  will always suspend the process since, unlike semaphores, if no process is suspended on  x . wait , then  x . signal  is @fignored. So when this is executed, the value of the semaphore  xcond  is always  0 . 6E lines 16-21First, the process indicates it will be executing an  x . signal  by adding  1  to  urgentcount . It pQthen checks if any process is waiting on condition variable  x  ( xcondcount  >  0 ), and if so signals any such process ( up ( xcondsem ) ) before suspending itself ( down ( urgent ) ). When restarted, @ithe process indicates it is no longer suspended (by subtracting  1  from  urgentcount ). HHˆB rHHˆqwss  ldB4ww HHˆB5uHHˆ!!w8 `Monitors and Priority Waits 9,` Introduction : tThis is an example of a monitor using priority waits. It implements a simple alarm clock; that is, a process calls !Ialarmclock . wakeme ( n ) , and suspends for  n  seconds. Note that we are assuming the hardware invokes the pro@8cedure  tick  to update the clock every second. ;n` Algorithm <`'1 alarmclock : monitor ; =`)2 var  now :integer; >`"3 wakeup : condition; ?`T 4 procedure   entry   wakeme ( n : integer); @`5 begin A`;6 alarmsetting  :=  now  +  n ; B`H 7 while   now  <  alarmsetting   do C`>8 wakeup . wait ( alarmsetting ); D`'9 wakeup . signal ; E` 10 end ; F`811 procedure   entry   tick ; G`12 begin H`)13 now  :=  now  + 1; I`(14 wakeup . signal ; J`15 end . KA` Comments LS ~lines 2-3Here,  now  is the current time (in seconds) and is updated once a second by the procedure  tick . _@NWhen a process suspends, it will do a wait on the condition  wakeup . Mn`Fline 6This computes the time at which the process is to be awakened. N`\lines 7-8The process now checks that it is to be awakened later, and then suspends itself. O pline 9Once a process has been woken up, it  signal s the process that is to resume next. That process 0pchecks to see if it is time to wake up; if not, it suspends again (hence the  while  loop above, rather @^than an  if  statement). If it is to wake up, it  signal s the next process P gline 14This is done once a second (hence the addition of 1 to now). The processes to be woken up are pkqueued in order of remaining time to wait with the next one to wake up first. So, when  tick  sigknals, the next one to wake up determines if it is in fact time to wake up. If not, it suspends itself; if @so, it proceeds. HHˆB7uHHˆtzvv  ldB8zz HHˆB9xHHˆg~zQ `send/receive Chart R,` Introduction S pThese charts summarize the actions of the send and receive primitives using both blocking and non-blocking mode I@"and explicit and implicit naming. Tb`Charts ^t@hOThis chart summarizes how naming and blocking affects the send primitive. h쪢@hRThis chart summarizes how naming and blocking affects the receive primitive. Ai` HHˆB;xHHˆw}yy  ldBX}} HHˆBY{HHˆO++}j `Producer Consumer Problem k,` Introduction l qThis algorithm uses blocking send and receive primitives to solve the producer/consumer (or bounded-buffer) probI@Mlem. In this solution, the buffer size depends on the capacity of the link. mb` Algorithm nt`/1 var  nextp, nextc : item; o`+2 procedure   producer ; p`3 begin q`14 while   true   do begin r`+5(* produce item in  nextp  *) s`C6 send ( Consumerprocess ,  nextp ); t`7 end ; u` 8 end; v`&9 procedure  consumer ; w`10 begin x`211 while   true   do begin y`G12 receive ( Producerprocess ,  nextc ); z`,13(* consume item in  nextc  *) {`14 end ; |`15 end; }` 16 begin ~`17 parbegin `518 Consumerprocess :  consumer ; `519 Producerprocess :  producer ; `20 parend ` 21 end . }` Comments  xline 1Here,  nextp  is the item the consumer produces, and  nextc   the item that the consumer con@sumes.  jlines 2-8This procedure simply generates items and sends them to the consumer process (named  Consumqerprocess ). Suppose the capacity of the link is n items. If  n  items are waiting to be consumed, "yand the producer tries to  send  the  n +1-st item, the producer will block (suspend) until the consumer lhas removed one item from the link (i.e., done a  receive  on the producer process). Note the name cof the consumer process is given explicitly, so this is an example of explicit naming or direct icommunication. Also, since the  send  is blocking, it ias an example of synchronous communica@tion.  klines 9-15This code simply receives items from the producer process (named  Producerprocess ) and 0 bconsumes them. If when the receive statement is executed there are no items in the link, the conpsumer will block (suspend) until the producer has put an item from the link (i.e., done a  send  to the `consumer process). Note the name of the producer process is given explicitly; again this is an nexample of explicit naming or direct communication. Also, since the  receive  is blocking, it is @+an example of synchronous communication. QL`slines 17-20This starts two concurrent processes, the  Consumerprocess  and the  Producerprocess . HHˆB[{HHˆz|| l}HHBbxHHyBWU&`send }Bdx~yBWV` blocking }VBfxVyBWW` non-blocking }HHBhxHHyGX explicit P@naming }BjxyGY -send message to receiver; wait until message P@ accepted }VBlxVyGWZ`send message to receiver }HHBnxHHyH[ implicit P@naming }BpxyH\ ,broadcast message; wait until all processes P@accept message }VBrxVyHW]`broadcast message }HCHBvxHCHyIW_&`receive }CBxx CyIW`` blocking }VCBzx VCyIWa` non-blocking }HWHB|x HWHyJb explicit P@naming }WB~x WyJWc`#wait for message from named sender }VWBx VWyJd -if there is a message from the named sender, P@get it; otherwise, proceed }HwHBx HwHyKe implicit P@naming }wBx wyKWf`!wait for message from any sender }VwBxVwyKg /if there is a message from any sender, get it; P@otherwise, proceed dB HHˆBHHˆ‚//  `Producer Consumer Problem  ,` Introduction  `TThis algorithm uses ADA to solve the producer/consumer (or bounded-buffer) problem.  V` Algorithm  h`0This process (task, to ADA) manages the buffer. t`21 task   boundedbuffer   is `T2 entry   deposit ( data :  in   item ); `U3 entry   extract ( data :  out   item ); `4 end ; `A5 task   body   boundedbuffer   is `U6 buffer :  array [0.. n -1]  of   item ; `L7 count :  integer   range  0.. n  := 0; `Z8 in ,  out :  integer   range  0.. n -1 := 0; `9 begin `10 loop `11 select `712 when   count  <  n  => ``13 accept   deposit ( data :  in   item )  do `;14 buffer [ in ] :=  data ; `15 end ; `F16 in  := ( in  + 1)  mod   n ; `017 count  :=  count  + 1; `:18 or   when   count  > 0 =>  `a19 accept   extract ( data :  out   item )  do !`<20 data  :=  buffer [ out ]; "`21 end ; #`H22 out  := ( out  + 1)  mod   n ; $`023 count  :=  count  - 1; %`24 end select ; &`25 end loop ; '`26 end . (`3The producer deposits an item into the buffer with )`A27 boundedbuffer . deposit ( nextp ); *`7and the consumer extracts an item from the buffer with +`A28 boundedbuffer . extract ( nextc ); ,` Comments - ylines 1-4This indicates that the procedures  deposit  and  extract  may be called outside the task, and @Xthat  extract  will return something in its parameter list (the  out ). . lines 6-8As usual,  buffer  is the buffer, and  count  the number of items currently in the buffer;  in  and "@Wout  are the indices indicating where deposits go or where extractions come from. /1 lines 13-17If there is room in the buffer ( when   count  <  n ) this process will accept a request to deposit an =@Witem in it ( accept   deposit   ); it then updates its variables. 0L lines 18-23If there is an item in the buffer ( when   count  > 0 ) this process will accept a request to extract an 0Xyitem from the buffer ( accept   extract   ); the item is returned via the parameter list. This pro@#cedure then updates its variables. 1s tline 24If both of the above two  when  conditions are true, and both a producer and consumer has invoked a Pfprocedure named by an  accept  statement (called an open accept statement), the system will HHˆBHHˆ} ldB HHˆBHHˆ1dselect one to be executed in some fair manner (such as first-come-first-serve). If only one of the pkconditions is true, and the procedure named in an  accept  statement in the body of the when stateqment is open, that one will be executed. If both of the  when  conditions are false, an error condition @.occurs (this usually terminates the process.) HHˆBHHˆ ldLeftd;Rightd ReferenceddHTMLdDHTMLd Headingsd d Fd Id Ld Od Rd WdZd ]d `d cd fd idldodrdudxd{ddd HTML@@ CMapping Table Title. @@ CBody. f@   .$.H.l..... .D.h.CodeN. Hf@ CH.. CodeComment. @@ CFooter. f@T C TableTitleT:Table : . Hf@ CH.. CodeComment. f@ CCellBody. f@ CCellBody. @@ CMapping Table Cell. @@C Mapping Table Cell. ~f@   ~.....2.V.z...CodeC. f@ C .$.H.l..... .D.h.CodeN. f@ C .$.H.l..... .D.h.CodeN. f@ CCellBody. f@ CBody. @@ CHeader Double Line. f@ C CellFooting. f@ C CellHeading. f@ C CellBody. @@ CMapping Table Cell. f@ C&CellBody. @@Mapping Table Cell. @@ Mapping Table Cell. @@ CMapping Table Cell. f@ CBody.  f@PCTitleBody. f@ C BodySpaced. f@ C Bulleted\t. f@ C...Date. mf@ Cl. DateProject. @@ CHeader Double Line. f@T CHeading1Body. f@NE C Numbered1 N:.Numbered. f@ C NumberedSpaced.\t. f@ C.Reading. f@$C.Line Single Line. f@ C CellHeading. f@ C Footnote. f@T CHeading2Body. f@T C HeadingRunInBody. f@ C Indented. f@ C TableFootnote. f@T C TableTitleT:Table : . L̀Lf@N C Numbered N:.< =1>. $f@L C$. Lettereda L:.. $f@L C$. LetteredL:..  f@T CHeading1Body. f@NE C Numbered1 N:.Numbered. $f@L C$. Lettereda L:.. $f@L C$. LetteredL:.. f@ CBody. L̀Lf@N C Numbered N:.< =1>. f@   .$.6.H.Z.l.~....... .D.h...Body. f@ CBody.  f@PCTitleBody.  f@PCTitleBody. %f@ C BodyIndent. f@  $.6.Z.u..CodeASM. C C C C  C ڝCCEmphasis  C CEquationVariables ڝC   BoldItalic CItalic CBold C C  ComputerC C    C    Computer    Computer C        Computer   Computer CZZdZThinMediumDoubleThick@ Very Thin HHHHHFormat A HHHHHFormat AH Mapping Table HHHHHFormat BH Mapping Table h6,5HHHHH$ZDHH+4?HHH68?HH :C?HHHTDL?HH*H<\HHHSBHHSIKH\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 "Y>#?#@#A#B#d %FC$D$E$ $&FF%G%H%6%'FI&J&K& &(FL'M'N' ')FO(P(Q(&((*FR)S)T)N()[FU*V*W*d ,FX+Y++Z+ +-F[,\,,], ,.F^-_--`- -/Fa.b.U.c..0Fd/e/V/f//1Fg0h0W0i002Fj1k1X1l1213Fm2n2Y2o2L24Fp3q3Z3r3f3Fs4t4[4u4h 9Fv5w5x5\5]5†d 7Fy6z6{6– 68F|7}7~7¢7F888h R5F^9_9`9a9b9d ;F:::: :CF ;";#;$; =  <<<<> ====? >>>K >@ ???W ?A @@@c @\ AAAHGy~BBB ;F%C&C'C(Cd EF)D,D-D DFF.E/E0E EQF1FBFCFHBHyGGGHGyHHHHC JyII IHW IKy J J JHw Jy KKK M !L8L9L NL :MGMHM OM INJNKN PN LOMONO QO OPPPQP FP RQSQTQvhS9FcRdReRfRgRjh TRFhSiSjSkSlS^h USFmTnToTpTqT6h(VTFrUsUtUuUvUh WUwVxVyVzV{VhXV|W}W~WWWh YWXXXXXh #XYYY Y Y[FZZZv*ZF[[[A \\\Comment ;C ;G 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.Courier.PCourier FrameRoman M.Times.B Times-Bold FrameRoman M.Times.I Times-Italic FrameRoman M.Helvetica.BHelvetica-Bold FrameRoman M.Geneva.PGeneva FrameRomanM.Helvetica.BIHelvetica-BoldOblique FrameRoman M.Courier.B Courier-Bold FrameRoman FrameRoman M.Courier.ICourier-Oblique FrameRoman M.Courier.BICourier-BoldOblique FrameRomanQCourierGeneva HelveticaBTimes#Regular#Roman MediumBoldRegular ObliqueItalic !'pV]B9L.*y7:n=ѓ/d[{^0 h_ܨCog^Д͡rB'Vvv4%='SV58$µ(G0j2@L#b°# =D0'EO? uJ6}.XB(k ~<|^XBͻ[_Ы>QCs;qdOxQ\a7y8n1Qu9J7MSЍ?->z&nY[W된boꃹ]-Jd w CIkLLٰ;6P!Ϊh~RӲ[Z](>].+gp<K̦xwPblv/QT$<גd