Aa! re  0  `  p00pp0!Author Matt BishopTitleNotes for January 9, 2001Subject ConcurrencyKeywordsconcurrency parallel systemsHH $ @d HHHH̀̀̀ff@  d Footnote TableFootnote**.\t.\t/ - :;,.!?4e eTOCHeading1Heading2   REquationVariablesP= ;`<<=7=P=i=@E@FA;@;@=@?@AC+C?   <$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::33557"AHHA;b;d;f;h;j;l;n;p;r;t;v;x;z;|;~;;;;;;;;;;;;;;;;;;;;;LFL;;;;;;;;;LGL;;;;;;;;;;;;;;;;;;;LGEL;;;;;;;;;<<<<<< < <<<<<<<<M;GM=<"<$<&<(<*<,<.<0<2<4<6<8<:<<MoGMqCE?7E@7EO-f.EvExEzE|E~EEEEEEEEEEEEEEEEEFFFHHHHHHHHHHHHHHHHHHHHHHHHHHHHOHHHHNHHHHHHHIIIIII I IIIIINIIII I"I$I&I(I*I,I.I0I2I4I6I8I:I<I>I@IBIDIFIHIJILINIPIRNSIVIXIZNUIeNINJOJ%JJJJJJKTKVGKXdq5+dA 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ˆAHHˆ O`Invariant expressions P`CSP I`RPC A`ADA HHˆAHHˆ7H 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ˆ117  `Outline for January 9, 2001 `Greetings and felicitations! `!First part of project due Friday >`Web page up and running! Q`What is concurrency? 3]`.Concurrent (parallel) vs. sequential (serial) 6`Logical vs.actual concurrency ;`gProcess creation: statically declare all subprocesses (created at execution) or dynamically spawn them ?`4Can view OS as a collection of concurrent processes `Simple parallel constructs `fork, join, quit `cobegin/coend `Process models ê`P(p1, p2); S(p1,p2) 1`Proper and improper nesting =*`  (precedence) relation:  p i      p j  means  p i  must complete before  p j  starts UU`Domain, range of processes 0`$Equivalence of systems of processes 2` Determinate system of processes 4`,Mutually noninterfering system of processes 5`DTheorem: If a system is mutually noninterfering, it is determinate. 7* Theorem: Let  f p  be an interpretation of process  p . Let be a system of processes, with  p     . If for all such 3U;9p ,  domain ( p ) and  range ( p ) , but  f p  unspecified, is determinate for all  f p , then all processes in are UU@mutually noninterfering 18M* tMaximally parallel system: determinate system for which the removal of any pair from the relation    makes @5the two processes in the pair interfering processes. h*`Critical section problem t*`Mutual exclusion ` Progress ` Bounded wait *`Classical problems *`Producer/consumer `DReaders/writers (first: readers priority; second: writers priority)  `Dining philosophers !*`Basic language constructs "*` Semaphores w` Send/receive *`,Evaluating higher-level language constructs *~` Modularity ` Constraints `Expressive power ` Ease of use ` Portability `#Relationship with proram structure `<>SBSA;=?=?BSBSA;>@>@BSSA;?A?ASSA;@J@JS}?H =x1C?H FW-e¢ }H =zB2H FW.e d=~EEd=DdFF l d=Dd& zrE zupkfa\WRMHC>vCFILORUX[^adgjmpsy| %).12/,)&# HUV @8!HUV :Wl@Last modified at 11:31 pm on Sunday, January 7, 2001 HHˆ@9!:HHˆII l HHˆ@:!HHˆHW` BA;AKAKBBA ;JLJLBA!;KMKMA";LNLNBA#;MOMOBBA$;NPNPBBA%;OQOQBBA&;PRPRBBA';QSQSBBA(;RTRTBJ+PA) ;SUSU IJ+P0/'A*;TVTV/'B/NGI "lA+ ;UWUWBIGI "l0K/A,;VXVXK/K/KKJzbA- ;WYWYIJzb0T// A.;XZXZT// T/O "lA/ ;Y[Y[ "l0 eA0;Z\Z\ e e L+PA1 ;[][]9L+P0e'A2;\^\^e'e<C1A3 ;]_]_BC1102SA4;^`^`2SGG "lA5 ;_a_aBG "l0KA6;`b`bKKKG "lA7 ;acacBG "l0KA8;bdbdKKKenl A9 ;cece[enl 0Kl<A:;dfdfKl<lKTe 6A;;egegTe 6Te]SCx䠉RA< ;fhfhKSCx䠉R0VA=;gigiV]V TFA>;hjhjTFprecedence graph UEA?;ikikUEU*U* S1 TEA@;jljlTE``S2 UTEAA;kmkmUTEU`U`S5 TEAB;lnlnTE``S7 EAC;momoES3 1EAD;npnp1E11S4 1EAE;oqoq1E11S6 UEAF;prprUEUUS8AG;qsqsAH;rtrtR "lAI ;susuRR "l0#/%AJ;tvtv#/%#/#TW:AK ;uwuwW:0\'AL;vxvx\'#\ "lAM ;wywy "l0#\%AN;xzxz#\%#\##\$-AO;y{y{#\$-#\G:~|AP ;z|z|:~|50 AAQ;{}{} A "lAR ;|~|~ "l0#@AS;}}#@## ʉ"lAT ;~~ ʉ"l0AU;$~|AV ;$~|0' AAW;' AG' "lAX ; "l0#AY;###AZ;A[; EA\; E * *S !A];  !!!E $99A^;  $99$E$Ep1 f9A_;  f9rrp2 H9A`;  H9HHp7 $o9Aa;  $o9${${p5 9Ab;   9 p4 9Ac;  9p3 $9Ad;$9$$p6 $9Ae;$9$$p8 mÀAf;EmÀprocess flow graphT92-Ag;ET92-<wAh ;EwSAi ;ESBSAj ;EBSSAk ;ESBAl ;EBAm ;EBAn ;EBBAo ;EBBAp ;EB TEAq;ETE  precedence graph VӏAr;EVӏV'V' S1 TӌAs;ETӌ]]S2 VTӌAt; E VTӌV]V]S5 TӌAu;!E!Tӌ]]S7 ӌAv; "E "ӌS3 2ӌAw;!#E!#2ӌ22S4 2ӌAx;"$E"$2ӌ22S6 VӌAy;#%E#%VӌVVS8Az ;$&E$&A{ ;%'E%' !ӆA|;&(E&(!ӆ!'!'S ӇTA};')E') ӇT E % A~;(*E(*% %B%Bp1 f A;)+E)+f oop2 I A;*,E*,I IIp7 %o A;+-E+-%o %x%xp5 A;,.E,. p4  A;-/E-/ p3 % A;.0E.0% %%p6 % A;/1E/1% %%p8 [JA;02E02[J process flow graphl A;13E13l Qc33A ;24E24Qc33cQQ-ͪA ;35E35Q-ͪQ-WIͯ"A ;46E46Iͯ"IͯIQͩ4)A ;57E57ͩ4)CͩRb4(A ;68E68b4(bDe$A ;79E79e$e8`A ;8:E8:8`CI(A ;9;E9;I(III&A ;:E<>"ͯ."ͯ"][",A ;=?E=?[",![&A ;>@E>@&%!KA ;?AE?A!K !*A ;@BE@B!*!""IA ;ACEAC"I"""[2A ;BDEBD"[2"["X~wA ;CEECX_aw"NOJ1H3srFXwA;DwDdAHH HHˆAFHHˆ†H;;H: `Improper Nesting Example <,` Introduction @ wOne of the limits on the use of parbegin/parend, and any related constructs, is that the program involved must be propI@lerly nested. Not all programs are. For example, consider the program represented by the following graphs. Ab`The Program as Graphs B w h  CH`%Using  fork/join  Primitives D[`GThe program equivalent to these precedence and process flow graphs is: EZ` t6 := 2; F` t8 := 3; G`'S1; fork p2; fork p5; fork p7; quit; H`!p2:S2; fork p3: fork p4; quit; I`p5:S5; join t6, p6; quit; J`p7:S7; join t8, p8; quit; K`p3:S3; join t8, p8; quit; L`p4:S4; join t6, p6; quit; M`p6:S6; join t8, p8; quit; N`p8:S8; quit O`4where S i  is the program for p i . PAH`+Using  parbegin/parend  Primitives QRO wTo see if this is possible, we must determine if the above program is properly nested. If not, we clearly cannot repre^N@rsent it using  parbegin  and  parend , which require a block structure, and hence proper nesting. aR ]Let  S ( a , b ) represent the serial execution of processes  a  and  b , and  P ( a , b ) the parallel execution of processes  a  and  b . Then a process flow graph is properly nested if it can be described by  P ,  S , and functional composition. For example, @ the program HHˆAFHHˆ KGG ldAKK HHˆAIHHˆKS` parbegin T`p1:a := b + 1; U`p2:c := d + 1; V`parend W`p3:e := a + c; X`would be written as Y`S ( P (p1,p2),p3) Z`We now prove: [`0Claim . The example is not properly nested. \`:Proof : For something to be properly nested, it must be of the form  S (p i ,p j ) or  P (p i ,p j ) at the most interior level. ]`Clearly the example's most interior level is not  P (p i ,p j ) as there are no constructs of that form in the graph. a^ In the graph, all serially connected processes pi and pj have at least 1 more process p k  starting or finishing at the node Fbetween p i  and p j ; but if  S (p i ,p j ) is in the innermost level, there can be no such p k  (else a more interior  P  or  S  is @Xneeded, contradiction). Hence, it's not  S (p i ,p j ) either. HHˆAIHHˆHNJJ ldANN HHˆALHHˆ--N_ `Maximally Parallel Systems `,` Introduction a }A  maximally parallel system  is a determinate system for which the removal of any pair from the precedence relation I@B  makes the two processes in the pair interfering processes. bb`Example c*t`The system  S  = (,   ) is composed of the set of processes = {  p 1 , .,  p 9  } and the precedence relation d`b  = { ( p 1 , p 2 ), ( p 1 , p 3 ), ( p 1 , p 4 ), ( p 2 , p 5 ), ( p 3 , p 5 ), ( p 4 , p 6 ), ( p 4 , p 7 ), ( p 4 , p 8 ), ( p 5 , p 8 ), ( p 6 , p 8 ), ( p 7 , p 9 ), ( p 8 , p 9 ) }. eUU`5The processes have the following domains and ranges: fz`'24 until   false ; ?`25 parend ; @`26 end . A` Comments B 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. C |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. D lline 10Since the buffer is not accessed while the item is produced, we don't need to put semaphores around %@ this part. E4 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 ( P ( empty ) ). When there is, it waits until it can obtain exclu~sive access to the buffer ( P ( mutex ) ). Once both these conditions are met, it can safely deposit the @item. Fs 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 ( V ( mutex ) ). It then indicates it has put another item into the buffer ( V ( full ) ). HHˆBRHHˆQWSS ldBWW HHˆBUHHˆ  WG 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 ( P ( full ) ). When there is, it waits until it can obtain wexclusive access to the buffer ( P ( mutex ) ). Once both these conditions are met, it can safely @extract the item. HE mlines 21-22As the consumer is done with the buffer, it signals that any other process needing to access the 0Qwbuffer may do so ( V ( mutex ) ). It then indicates it has extracted another item into the buffer @%( V ( empty ) ). Il eline 23Since the buffer is not accessed while the item is consumed, we don't need to put semaphores x@around this part. QJ` HHˆBUHHˆTZVV ldBZZ HHˆBXHHˆ//Z K `First Readers Writers Problem L,` Introduction M`LThis algorithm uses semaphores to solve the first readers-writers problem. NV` Algorithm O h`71 var wrt ,  mutex : semaphore; Pt`,2 readcount :  integer ; Q`3 begin R`4 readcount  := 0; S`5 wrt  := 1; T`6 mutex  := 1; U`7 parbegin V`,8 repeat (* reader process *) W`9(* do something *) X`$10 P ( mutex ); Y`611 readcount  :=  readcount  + 1; Z`512 if   readcount  = 1  then [`#13 P ( wrt ); \`$14 V ( mutex ); ]`15(* read the file *) ^"`) 16 P ( mutex ); _ `617 readcount  :=  readcount  - 1; ``518 if   readcount  = 0  then a`#19 V ( wrt ); b`$20 V ( mutex ); c`!21 (* do something else *) d`22 until  false; e`-23 repeat (* writer process *) f`24(* do something *) g`"25 P ( wrt ); h`26(* write to the file *) i`"27 V ( wrt ); j`28(* do something else *) k`29 until  false; l`30 parend ; m`31 end . n` Comments o 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. p. lines 4-6This 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 . qU`^line 9Since the file is not accessed here, we don't need to put semaphores around this part. r ulines 10-15Since the value of the shared variable  readcount  is going to be changed, the process must wait p~until no-one else is accessing it ( P ( mutex ) ). Since this process will read from the file,  readB#ncount  is incremented by 1; if this is the only reader that will access the file, it waits until any writHHˆBXHHˆW]YY ldB]] HHˆB[HHˆ  ] rwers have finished ( P ( wrt ) ). It then indicates other processes may access  readcount  @I( P ( mutex ) ) and proceeds to read from the file. s xlines 16-20Now the reader is done reading the file (for now.) It must update the value of  readcount  to indi|cate this, so it waits until no-one else is accessing that variable ( P ( mutex ) ) and then decrements #mreadcount . 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 ( V ( wrt ) ). Finally, it indicates it is done @>with  readcount  ( V ( mutex ) ). t``_line 24Since the file is not accessed here, we don't need to put semaphores around this part. u lines 25-26The writer process waits ( P ( wrt ) ) until no other process is accessing the file; it then proceeds to {@write to the file. v nline 27When the writer is done writing to the file, it signals that anyone who wishes to access the file may P@)do so ( V ( wrt ) ). HHˆB[HHˆZr\\ l}HHC,p_HHqBW|%`send }C.p^`qBW}` blocking }VC0p_aVqBW~` non-blocking }HHC2p`bHHqG explicit P@naming }C4pacqG -send message to receiver; wait until message P@ accepted }VC6pbdVqGW`send message to receiver }HHC8pceHHqH implicit P@naming }C:pdfqH ,broadcast message; wait until all processes P@accept message }VC<pegVqHW`broadcast message }HCHC@pfhHCHqIW%`receive }CCBpgiCqIW` blocking }VCCDphjVCqIW` non-blocking }HWHCFpikHWHqJ  explicit P@naming }WCHpjlWqJW `#wait for message from named sender }VWCJpkmVWqJ  -if there is a message from the named sender, P@get it; otherwise, proceed }HwHCLplnHwHqK  implicit P@naming }wCNpmowqKW `!wait for message from any sender }VwCPpnVwqK /if there is a message from any sender, get it; P@otherwise, proceed dCUrr HHˆCVpHHˆO ^or x `send/receive Chart y,` Introduction z pThese charts summarize the actions of the send and receive primitives using both blocking and non-blocking mode I@"and explicit and implicit naming. {b`Charts t@hOThis chart summarizes how naming and blocking affects the send primitive. Q쪢@hRThis chart summarizes how naming and blocking affects the receive primitive. HHˆCXpHHˆ]uqq ldD'uu HHˆD(sHHˆ^,,u  `Producer Consumer Problem ,` Introduction  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. b` Algorithm  t`/1 var  nextp, nextc : item; !`+2 procedure   producer ; "`3 begin #`14 while   true   do begin $`+5(* produce item in  nextp  *) %`C6 send ( Consumerprocess ,  nextp ); &`7 end ; '` 8 end; (`&9 procedure  consumer ; )`10 begin *`211 while   true   do begin +`G12 receive ( Producerprocess ,  nextc ); ,`,13(* consume item in  nextc  *) -`14 end ; .`15 end; /!` 16 begin 0 `17 parbegin 1`518 Consumerprocess :  consumer ; 2`519 Producerprocess :  producer ; 3`20 parend 4!` 21 end . 5}` Comments 6 xline 1Here,  nextp  is the item the consumer produces, and  nextc   the item that the consumer con@sumes. 7 jlines 2-8This procedure simply generates items and sends them to the consumer process (named  Consum#qerprocess ). 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. 8 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. 9L`slines 17-20This starts two concurrent processes, the  Consumerprocess  and the  Producerprocess . A:` HHˆD*sHHˆrxtt ldD+xx HHˆD,vHHˆ‚//x ; `Producer Consumer Problem <,` Introduction =`[This algorithm uses a monitor to solve the producer/consumer (or bounded-buffer) problem. >V` Algorithm ? h`#1 buffer : monitor ; @t`X2 var  slots :  array  [0.. n -1]  of  item; A`<3 count ,  in ,  out : integer; B`74 notempty ,  notfull : condition; C`P5 procedure   entry   deposit ( data : item); D!` 6 begin E `97 if   count  =  n   then F`'8 notfull . wait ; G"`: 9 slots [ in ] :=  data ; H `A10 in  :=  in  + 1  mod   n ; I`-11 count  :=  count  + 1; J`*12 notempty . signal ; K`13 end ; L`_14 procedure   entry   extract ( var   data : item); M`15 begin N`016 if   count  = 0  then O`)17 notempty . wait ; P"`< 18 data  :=  slots [ out ]; Q `C19 out  :=  out  + 1  mod   n ; R`-20 count  :=  count  1; S`)21 notfull . signal ; T`22 end ; U`23 begin V`B24 count  := 0;  in  := 0;  out  := 0; W`25 end . X` Comments Y 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 ). Z 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ˆD.vHHˆu{ww ldD/{{ HHˆD0yHHˆ{]@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 () . _ 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. `o klines 18-20This code actually extracts the item from the buffer. Note that the monitor guarantees mutual {@ exclusion. a 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. b`-lines 23-25This is the initialization part. Ac` HHˆD2yHHˆx~zz ldD3~~ HHˆD4|HHˆ|//~d `First Readers Writers Problem e,` Introduction f`LThis algorithm uses a monitor to solve the first readers-writers problem. gV` Algorithm h h`(1 readerwriter :  monitor it`*2 var readcount : integer; j`!3 writing : boolean; k`94 oktoread ,  oktowrite : condition; l`-5 procedure entry  beginread ; m`6 begin n`47 readcount  :=  readcount  + 1; o`-8 if   writing   then p`(9 oktoread . wait ; q`10 end ; r`;11 procedure   entry   endread ; s`12 begin t`513 readcount  :=  readcount  - 1; u`414 if   readcount  = 0  then v`,15 oktowrite . signal ; w`16 end ; x`>17 procedure   entry   beginwrite ; y`18 begin z`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ˆD6|HHˆ{}} ldD7 HHˆD8HHˆ  emore 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ˆD:HHˆ~ ldD; HHˆD<HHˆ// `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 P ( xmutex ); `4(* procedure body*) `45 if   urgentcount  > 0  then `"6 V ( urgent ) ` 7 else `"8 V ( mutex );  `EEach  x . wait  within the procedure is replaced by: ! `59 xcondcount  :=  xcondcount  + 1; ""`: 10  if  urgentcount  > 0  then #`( 11 V ( urgent ) $!` 12 else % `#13 V ( mutex ); &`"14 P ( 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 V ( xcond ); , `$19 P ( urgent ); -`20 end ; .`821 urgentcount  :=  urgentcount  - 1; /` Comments 0 |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 . 1 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 ). 21 mlines 3-8Since only one process at a time may be in the monitor, the process entering the monitor procedure 0=|must wait until no other process is using it ( P ( mutex ) ). On exit, the process signals others that ethey 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 continqued ( V ( urgent ) ). Otherwise, one of the processes trying to enter the monitor may do so @%( V ( mutex ) ). Q3| lines 9-15First, the process indicates it will be executing an  x . wait  by adding  1  to  xcondcount . It then HHˆD>HHˆ ldD? HHˆD@HHˆ{  3esignals 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  P ( 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 . 4E lines 16-21First, the process indicates it will be executing an  x . signal  by adding  1  to  urgentcount . It 0Qthen checks if any process is waiting on condition variable  x  ( xcondcount  >  0 ), and if so signals any such process ( V ( xcondsem ) ) before suspending itself ( P ( urgent ) ). When restarted, the @eprocess indicates it is no longer suspended (by subtracting  1  from  urgentcount ). Q5x` HHˆDBHHˆ  ldDC  HHˆDDHHˆ!! 6 `Monitors and Priority Waits 7,` Introduction 8 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. 9n` Algorithm : `'1 alarmclock : monitor ; ;`)2 var  now :integer; <`"3 wakeup : condition; =!`T 4 procedure   entry   wakeme ( n : integer); > `5 begin ?`;6 alarmsetting  :=  now  +  n ; @!`H 7 while   now  <  alarmsetting   do A `>8 wakeup . wait ( alarmsetting ); B`'9 wakeup . signal ; C!` 10 end ; D `811 procedure   entry   tick ; E`12 begin F`)13 now  :=  now  + 1; G`(14 wakeup . signal ; H`15 end . IA` Comments JS ~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 . Kn`Fline 6This computes the time at which the process is to be awakened. L`\lines 7-8The process now checks that it is to be awakened later, and then suspends itself. M 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 N 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ˆDFHHˆ ldDh  HHˆDi HHˆ‡22 Q `First Readers Writers Problem R,` Introduction S`KThis uses crowd monitors to solve the first readers/writers problem.  TV` Algorithm U h`81 readerwriter :  crowd   monitor Vt`?2 var Readers :  crowd   read ; W`H3 Writers :  crowd   read ,  write ; X`,4 readcount :  integer ; Y`*5 writing :  boolean ; Z`B6 oktoread ,  oktowrite :  condition ; [`87 guard procedure entry   beginread ; \`8 begin ]`49 readcount  :=  readcount  + 1; ^`.10 if   writing   then _`)11 oktoread . wait ; ``(12 enter   Readers ; a`13 end ; b`714 guard procedure entry   endread ; c`15 begin d`(16 leave   Readers ; e`517 readcount  :=  readcount  - 1; f`418 if   readcount  = 0  then g`,19 oktowrite . signal ; h`20 end ; i`:21 guard procedure entry   beginwrite ; j`22 begin k`S23 if   readcount  > 0  or   writing   then l`*24 oktowrite . wait ; m` 25 writing  := true; n`(26 enter   Writers ; o`27 end ; p`828 guard procedure entry   endwrite ; q`229 var  i :  integer ; r`30 begin s`(31 leave   Writers ; t`!32 writing  := false; u`433 if   readcount  > 0  then v`<34 for   i  := 1  to  readcount w`,35 oktoread . signal ; x`36 else y`,37 oktowrite . signal ; z`38 end ; {`.39 procedure entry   read ; |`*40  read from shared data  }`41 end ; ~`/42 procedure entry   write ; `)43  write to shared data  `44 end ; `45 begin A`;46 readcount  := 0;  writing  := false; HHˆDk HHˆ  ldD HHˆDHHˆ  `47 end . ` Comments  jlines 2-3These lines define which procedures can be called by members of the crowd; here, members of the Readers  crowd can call  read , and members of the  Writers  crowd can call either  read  or  write . Only "zprocesses in those crowds can call  read  or  write ; should any other process do so, it will cause a run-@ time error. d qline 7The keyword  guard  means this procedure is mutually exclusive (so only one process at a time may 0pfbe in the guarded procedures). Note this relaxes the definition of Hoares monitor, in that multiple @4proceses may now access the monitor simultaneously. `vline 12This puts the calling process into the  Readers  crowd; it may now call the procedure  read .  line 16This removes the calling process from the  Readers  crowd, so it may not call  read  until after it calls @+beginread  and executes line 12 again.  ` line 26This puts the calling process into the  Writers  crowd; it may now call the procedures  read  and  write .   line 31This removes the calling process from the  Readers  crowd, so it may not call  read  or  write  until after Ъ@Xit calls  beginread  or  beginwrite  and executes lines 12 or 26 again.  ߪ`\line 39Now any number of processes may access the  read  procedure simultaneously.   mline 42Although it may appear that any number of processes may access the  write  procedure simultapmneously, note that all callers must first have invoked  beginwrite  and only one such process will @Hbe active at a time. So at most one process will call  write . HHˆDHHˆ  ldD HHˆDHHˆU**  `Producer Consumer Problem ,` Introduction `HThis uses invariant expressions to solve the producer consumer problem. V` Algorithm  h`11 buffer :  invariant module ; t`'2 const   n  = 1024; `b3 var  slots :  array  [0.. n -1]  of   item ; `34 in ,  out : 0.. n -1; `$5 invariant   deposit `\6 StartCount ( deposit ) -  FinishCount ( extract ) < n; `37 CurrentCount ( deposit ) = 0; `$8 invariant   extract `[9 StartCount ( extract ) -  FinishCount ( deposit ) < 0 `410 CurrentCount ( extract ) = 0; `Q11 procedure entry   deposit ( data :  item ); `12 begin `613 slots [ in ] :=  data ; `A14 in  :=  in  + 1  mod   n ; `15 end ;  `_16 procedure entry   extract ( var   data :  item ); !`17 begin "`718 data  :=  slots [ out ]; #`C19 out  :=  out  + 1  mod   n ; $`20 end ; %`21 begin &`,22 in  := 0;  out  := 0; '`23 end . (` Comments ) lines 3-4Here,  slots  is the actual buffer and  in  and  out  the indices of the next element of slots where a deposit @9is to be made or from which an extraction is to be made. *`Fline 5The next constraints apply to the procedure  deposit . + |line 6This invariant checks that there is at least one slot in the buffer that is empty. If false, then  deposit  Ѫ@Xmust have been started at least  n  times more than  extract  finished. ,ઍ`bline 7This ensures at most one process can be in  deposit  at a time (mutual exclusion). -`Fline 8The next constraints apply to the procedure  extract . . |line 6This invariant checks that there is at least one slot in the buffer that is full. If so, then  deposit  fin @1ished more times than  extract  started. /`bline 7This ensures at most one process can be in  extract  at a time (mutual exclusion). 0`zline 11As with the previous procedure, this is called from outside the monitor by  buffer . extract (). 1 nlines 12-15 This code actually extracts the item from the buffer. Note that the invariant guarantees mutual C@ exclusion. Q2R`-lines 23-25This is the initialization part. HHˆDHHˆ ldD HHˆDHHˆ3 `First Readers Writers Problem 4,` Introduction 5`LThis uses invariant expressions to solve the first readers writers problem. 6V` Algorithm 7 h`;1 readerwriter :  invariant   module 8t`!2 invariant   read 9`13 CurrentCount ( write ) = 0; :`"4 invariant   write ;`Z5 CurrentCount ( write ) +  CurrentCount ( read ) = 0; <`-6 procedure entry   read ; =`(7  read from shared data  >`8 end ; ?`.9 procedure entry   write ; @`(10  write to shared data  A`11 end ; B`12 begin C`13 end . D` Comments E# zlines 2-3This states the condition that must hold whenever the procedure  read  is executed; it requires that no 0/oprocesses be executing  write . Note this means readers will have priority over writers when a reader eis presently reading; it says nothing about what happens if a reader and a writer call the module at @the same time. FV xlines 4-5This states the condition that must hold whenever the procedure  write  is executed; it requires that b@Dno processes be executing either  read  or  write . Gq`Alines 6-11Here, the routines simply do the reading and writing. AH`hlines 12-13The initialization part of the module; as there are no variables in it, this part is empty. HHˆDHHˆ ldD HHˆDHHˆJ `Producer Consumer Process K,` Introduction L`GThis uses Hoares CSP language to solve the producer consumer problem. MV` Algorithm Nh`BThis process manages the buffer; call it  boundedbuffer . Ot`,1 buffer : (0..9)  item ; P`32 in ,  out :  integer ; Q`3 in  := 0; R`4 out  := 0; S`5*[ in  <  out  +  n ;  producer  ?  buffer ( in   mod   n ) T`16 n   in  :=  in  + 1 U`V7     out  <  in ;  consumer  ?  more () V`b8 n   consumer  !  buffer ( out   mod   n ); W`)9  out  :=  out  + 1 X`10 ] Y` Comments Z  lines 1-2:Here,  buffer  is the buffer,  in  the number of items put into the buffer, and  out  the number of items @Uextracted. The producer process outputs an item  nextp  to this process by: [&`1bounded - buffer  !  nextp ; \`Nand the consumer process outputs an item  nextc  to this process by: ]`ibounded - buffer  !  more ();  bounded - buffer  ?  nextc ; ^`S( more () is there because CSP does not allow output commands in guards.) _`Blines 3-4:These just initialize  in  and  out . ` lines 5-6:If there is room for another item in the buffer ( in  <  out  +  n ), wait for the producer to produce some0}thing and deposit it in an empty buffer slot ( producer  ?  buffer ( in   mod   n )) and indicate that slot is @-now used ( in  :=  in  + 1). a lines 7-9:If the buffer is full ( out  <  in ), wait until the consumer asks for something ( consumer  ?  more ()), then poutput the next element of the buffer ( consumer  !  buffer ( out   mod   n )), and indicate it has been @0extracted ( out  :=  out  + 1). HHˆDHHˆ ldEC HHˆEDHHˆ‚//b `Producer Consumer Problem c,` Introduction d`TThis algorithm uses ADA to solve the producer/consumer (or bounded-buffer) problem. eV` Algorithm fh`0This process (task, to ADA) manages the buffer. g t`21 task   boundedbuffer   is h`T2 entry   deposit ( data :  in   item ); i`U3 entry   extract ( data :  out   item ); j`4 end ; k`A5 task   body   boundedbuffer   is l`U6 buffer :  array [0.. n -1]  of   item ; m`L7 count :  integer   range  0.. n  := 0; n`Z8 in ,  out :  integer   range  0.. n -1 := 0; o`9 begin p`10 loop q`11 select r`712 when   count  <  n  => s``13 accept   deposit ( data :  in   item )  do t`;14 buffer [ in ] :=  data ; u`15 end ; v`F16 in  := ( in  + 1)  mod   n ; w`017 count  :=  count  + 1; x`:18 or   when   count  > 0 => y`a19 accept   extract ( data :  out   item )  do z`<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.  L 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.  s 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ˆEFHHˆ ldEG HHˆEHHHˆZ dselect one to be executed in some fair manner (such as first-come-first-serve). If only one of the 0kconditions 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.)  `  ` A ` HHˆEJHHˆ" ldEK""! HHˆEL HHˆ"W9 ` HHˆEN HHˆ!! 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 Fd Id Ld Od Rd UdXd [d pd sd vd yd|ddddd ddddd d!d dHTMLG@@ SMapping Table Title. @@ SBody. f@ S Answer1ItalicAnswer: . f@ SBody. @@ SFooter. f@T S TableTitleT:Table : . f@ S BodySpaced. f@ S Bulleted\t. f@ S...Date. mf@ Sl. DateProject. @@ SHeader Double Line. f@  $.6.Z.~..CodeC. f@T SHeading1Body. $f@ S Answer. f@ S NumberedSpaced. f@ SBody. @@ SHeader Double Line. f@ S CellFooting. f@ S CellHeading. f@ S CellBody. @@ SMapping Table Cell. f@ S.Reading. @@0Mapping Table Cell.  f@PSTitleBody. @@ 0Mapping Table Cell. @@ SMapping Table Cell. f@$S.Line Single Line.  f@PSTitleBody. f@ SCellBody. f@ S CellHeading. f@ S Footnote. f@T SHeading2Body. f@T S HeadingRunInBody. f@ S Indented. f@ S TableFootnote.  f@PSTitleBody. f@NE S Numbered N:.< =1> Lettereda. f@NE S Numbered N:.< =1> Lettereda. $f@LE S$. Lettereda L:.Lettered. f@NE S Numbered1 N:. Lettereda. f@NE S Numbered1 N:. Lettereda. f@T S TableTitleT:Table : . f@T SHeading1Body. $f@LE S$. Lettereda L:.Lettered. $f@L S$. LetteredL:.. f@ S .$.H.l..... .D.h...Body. ~f@   ~.....2.V.z...CodeC. ~f@  ~.....2.V.z...CodeC. f@ SBody. f@ S-.Body. f@ S H.l..... .D.h...Body. f@T SHeading2Body. f@ S~Body. f@   .$.H.l..... .D.h.CodeN. Hf@ SH.. CodeComment. f@ S .$.H.l..... .D.h.CodeN. $f@L S$. LetteredL:.. Hf@ SH.. CodeComment. 6$f@R S6. Romani R:.. 6$f@R S6. RomanR:.. f@ S BodyIndent. f@  $.6.Z.u..CodeASM. Hf@ SH.. CodeComment. f@ SCellBody. f@ SCellBody. f@ S%CellBody. Hf@ SH. LineComment. f@   .$.H.l..... .D.h.CodeN. Hf@ SH. LineComment. @@ SMapping Table Cell. @@S*Mapping Table Cell. * S SSEmphasis S 0 S ڝSSSEquationVariables 0  BoldItalic SItalic S ڝS S S ]  Wingding S0 S SBoldO  Symbol   Computer O  Symbol )   S    S S Subscript S Superscript S  Computer Computer  Computer   S Subscript S    Computer S Superscript ]  WingdingS ZZd Z ZdZdThinMediumDoubleThick@ Very Thin HHHHHFormat A HHHHHFormat BH Mapping TableH Mapping Table HHHHHFormat A h65HHHHH$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 AAAHGq^B_B`B ;%C&C'C(Cd E)D,D-D DF.E/E0E EQ1FBFCFHBHqaGbGcGHGqdHeHfHHC JqgIhIiIHW IKqjJkJlJHw JqmKnKoK 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.Courier.B Courier-Bold FrameRoman M.Times.I Times-Italic FrameRoman M.Times.BITimes-BoldItalic FrameRomanM.Helvetica.BIHelvetica-BoldOblique FrameRoman M.Wingdings.P Wingdings FrameRoman FrameRoman FrameRoman M.Symbol.PSymbolMT FrameRoman M.Geneva.PGeneva FrameRoman M.Courier.ICourier-Oblique FrameRoman M.Courier.BICourier-BoldOblique FrameRomangCourier(Geneva/ HelveticaNSymbolRTimes\ Wingdings#Regular$Roman MediumBoldRegular ObliqueItalic ~hkb<*VOI&6Yp]A.HgWT)ӮڅwJ:vcr@ -udO=6 hmsIhMhVY*4I'f5iqm ?g$DD4C.ӮEj˅SoB  6< YE+<:+筊h3QH!IT R|Q[nPh:; j>>K-`kW-zr [JKCr "ēO"k闓NeDu%ZILwrx s_y eU:0o$:jLU k< o<w%ʐPO6es> X#nQ:ND۸XOVi2픍e#WލlkQV$2>!("s*_zZK|