Aaw^d    PPP  `PPP 0 HH $ @d HHHHff@  d Footnote TableFootnote**.\t.\t/ - :;,.!?8cZ';cZTOCHeading1Heading2   FEquationVariables@>#???@@,@I>>>> > >  <$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++AGGII33557 AKKA>%>'>)>+>->/>1>3>5>7>9>;>=>?>A>C>E>G>I>K>M>O>Q>S>U>W>Y>[>]>_>a>c>e>g>i>k>m>n>o>q>s>u>w>y>{>}>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>?????? ? ? ??????????!?#?%?'?)?+?-?/?1?3?5?7?9?;?=???A?C?E?G?I?K?M?O?Q?S?U?W?Y?[?]?_?a?c?e?g?i?k?m?o?q?s?u?w?y?{?}???????????????????????????????????????????????????????????????@@@@@@ @ @@@@K@M@O@Q@S@U@W@Y@[@]@_@a@c@e@g@i@k@m@n=> @@@;#@@@;/;2;5$>@!@#@%@'@)@+@.@0@2@4@6@8@:@<@>@?==>===========================$=$=$=$=$dq5+d= d> d>; HmR>HmRHRHRFootnote Hr@>Hr@HzHz Single LineH靕> Footnote >  HD> HDHH Double LineH>  Double Line> > H֝>  Single Line> d5p77HZ֝>; TableFootnoted>!d?靕l d>"d1QRUX[^adgjmpsvy| %).1W,܁܁@m }蝝d >$蝝d WaHTML Mapping Table }H蝝d >&H蝝d Wa }H蝝d >(H蝝d Wa }H蝝d >*H蝝d Wa }H蝝d >,H蝝d Wa }H>.H! FrameMaker PA Source Item }H >0H Wa HTML Item }H >2H Wa }H>4H W aInclude Auto# } H>6 H W a Comments }H>8H W a }HH>: HH W aElement }H><#H W a New Topic? }H>>H Wa } H>@ H Wa }H >B $H Wa P:Date Line }HH >D#%HH WaP }H >F$&H WaN }H >H%'H WaN } H >J&( H Wa }EH >L')EH Wa P:Reading }HEH >N(*HEH WaP }EH >P)+EH WaN }EH >R*,EH WaN } EH >T+- EH Wa }QH >V,.QH WaP:Title }HQH >X-/HQH WaH* }QH >Z.0QH WaN }QH >\/1QH WaN } QH >^02 QH Wa }]H >`13]H WaP:Body }H]H >b24H]H W aP }]H >d35]H W!aN }]H >f46]H W"aN } ]H >h57 ]H W#a }iH(>j68iH( W$a P:Numbered1 }HiH(>l79HiH((%aLI &a Parent = OL Q'a Depth = 0 }iH(>p8:iH( W(aN }iH(>r9;iH( W)aY } iH(>t:< iH( W*a }띝H >v;=띝H  W+a P:Heading1 }H띝H >x<>H띝H  W,aH* }띝H >z=?띝H  W-aN }띝H >|>@띝H  W.aN } 띝H >~?A 띝H  W/a }H(>@BH(  W0a P:Numbered }HH(>ACHH(( 1aP 2a Parent = OL Q3a Depth = 0 }H(>BDH(  W4aN }H(>CEH(  W5aY } H(>DF H(  W6a }H >EGH  W7a P:CellBody }HH >FHHH  W8aP }H >GIH  W9aN }H >HJH  W:aN } H >IK H  W;a }H >JLH  W<aP:CellHeading }HH >KMHH  W=aP }H >LNH  W>aN }H >MOH  W?aN } H >NP H  W@a }H >OQH  WAa P:Footnote }HH >PRHH  WBaP }H >QSH  WCaN }H >RTH  WDaN } H >SU H  WEa }ȝH(>TVȝH( WFa P:Bulleted }HȝH(>UWHȝH((GaLI Ha Parent = UL QIa Depth = 0 }ȝH(>VXȝH( WJaN }ȝH(>WYȝH( WKaN } ȝH(>XZ ȝH( WLa }H >Y[H WMa P:Heading2 }HH >Z\HH WNaH* }H >[]H WOaN }H >\^H WPaN } H >]_ H WQa }H>^`HR! P:HeadingRuPAnIn }HH>_aHH WSaP }H>`bH WTaN }H>acH WUaN } H>bd H WVa }7H >ce7H WWa P:Indented }H7H >dfH7H WXaP }7H >eg7H WYaN }7H >fh7H WZaN } 7H >gi 7H W[a }CH>hjCH\! P:TableFootPAnote }HCH>ikHCH W]aP }CH>jlCH W^aN }CH>kmCH W_aN } CH>ln CH W`a }]H(>mo]H( Waa P:TableTitle }H]H(>npH]H((baLI ca Parent = OL Qda Depth = 0 }]H(>oq]H( WeaN }]H(>pr]H( WfaN } ]H(>qs ]H( Wga }֝H >rt֝H Wha P:BodySpaced }H֝H >suH֝H WiaP }֝H >tv֝H WjaN }֝H >uw֝H WkaN } ֝H >vx ֝H Wla }띝H >wy띝H WmaP:Date }H띝H >xzH띝H WnaP }띝H >y{띝H WoaN }띝H >z|띝H WpaN } 띝H >{} 띝H Wqa }H(>|~H(r! P:NumberedPASpaced }HH(?}HH((saP ta Parent = OL Qua Depth = 0 }H(?~H( WvaN }H(?H( WwaY } H(? H( Wxa }H ? H WyaP:DateProject }HH ? HH WzaP }H ?H W{aN }H ?H W|aN } H ? H W}a }H ?H W~a C:BoldItalic }HH ? HH WaSTRONG }H ? H WaN }H ? H WaN } H ? H Wa }H? H! C:EquationPA Variables }HH?  HH WaEM }H?" H WaN }H?$H WaN } H?& H Wa }H ?(H Wa C:Italic }HH ?*HH W aEM }H ?,H W aN }H ?.H W aN } H ?0 H W a }H ?2H W aC:Bold }HH ?4HH WaSTRONG }H ?6H WaN }H ?8H WaN } H ?: H Wa }H?<H! X:Heading & PAPage }HH?>HH Wa See Also }H?@H WaN }H?BH WaN } H?D H Wa })H ?F!)H WaX:Page }H)H ?H "H)H Wa See Also })H ?J!#)H WaN })H ?L"$)H WaN } )H ?N#% )H Wa }5H?P$&5H! X:See HeadPA ing & Page }H5H?R%'H5H Wa See Also }5H?T&(5H WaN }5H?V')5H WaN } 5H?X(* 5H W a }OH ?Z)+OH W!a X:Table All }HOH ?\*,HOH W"a See Also }OH ?^+-OH W#aN }OH ?`,.OH W$aN } OH ?b-/ OH W%a }[H?d.0[H &! X:Table NumPA ber & Page }H[H?f/1H[H  W'a See Also }[H?h02[H  W(aN }[H?j13[H  W)aN } [H?l24 [H  W*a }uH?n35uH !W+a X:Heading }HuH?p46HuH!,! USE XREF PAFMT }uH?r57uH !W-aN }uH?t68uH !W.aN } uH?v79 uH !W/a }蝝H?x8:蝝H "W0a P:Header }H蝝H?z9;H蝝H"1!THROW PAAWAY }蝝H?|:<蝝H "W2aN }蝝H?~;=蝝H "W3aN } 蝝H?<> 蝝H "W4a }H ?=?H #W5a }HH ?>@HH #W6a }H ??AH #W7a }H ?@BH #W8a } H ?AC H #W9a }d ?BFd $W:aHTML Options Table }Dd ?Dd $W;a }Dd ?Dd $W<a }D ?CGD %W=a }DH ?FHDH %W>a }H ?GIH %W?a }םD ?HJםD &W@a Image Format }DםH ?IKDםH &WAaIMAGGIF }םH ?JLםH &WBa }D ?KMD 'WCaBanners }DH ?LNDH 'WDaN }H ?MOH 'WEa }ԝD?NPԝD(F! Banner ReferPA ence Frame }DԝH?OQDԝH (WGa }ԝH?PԝH (WHa }D(?>SD((@)I! Copy Files  Imported by PA Rerefernce }DH(?>RTDH( @)WJa }H(?>SUH( @)WKa }DD ?>TVDD @*WLa }DDH ?>UWDDH @*WMa }DH ?>VXDH @*WNa }Vd ?>W[Vd @+WOaSystem Macros }?Vd ?>?Vd @+WPa }?Vd ?>?Vd @+WQa }f? ?>X\f? @,WRa Macro Name }?fH ?>[]?fH @,WSa Replace With }fH ?>\^fH @,WTa Comments }r? ?>]_r? @-WUa StartOfDoc }?rH ?>^`?rH @-WVa }rH ?>_arH @-WWa }~? ?>`b~? @.WXa EndOfDoc }?~H ?>ac?~H @.WYa }~H ?>bd~H @.WZa }??>ce?@/[! StartOfSubPADoc }?H?>df?H @/W\a }H?>egH @/W]a }??>fh?@0^! EndOfSubPADoc }?H?>gi?H @0W_a }H?>hjH @0W`a }??>ik?@1a! StartOfFirstPASubDoc }?H?>jl?H @1Wba }H?>kmH @1Wca }??>ln?@2d! EndOfFirstPASubDoc }?H?>mo?H @2Wea }H?>npH @2Wfa }??>oq?@3g! StartOfLastPASubDoc }?H?>pr?H @3Wha }H?>qsH @3Wia } ??>rt ?@4j! EndOfLastPASubDoc }? H?>su? H @4Wka } H?>tv H @4Wla }&? ?>uw&? @5Wma }?&H ?>vx?&H @5Wna }&H ?>wy&H @5Woa }8d ?>x|8d @6WpaCross-Reference Macros }?8d ?>?8d @6Wqa }?8d ?>?8d @6Wra }H? @>y}H? @7Wsa Macro Name }?HH @>|~?HH @7Wta Replace With }HH @>}HH @7Wua Comments }T?@>~T? @8Wva See Also }?TH@ >?TH@8w! See Also: PA <$paratext> }TH@ >TH @8Wxa }n? @ >n? @9Wya }?nH @>?nH @9Wza }nH @>nH @9W{a }d @> d @:WaGeneral Macros }?d @>?d @:Wa }?d @>?d @:Wa }?d @>?d @:Wa }? @>"? @;Wa Macro Name d@F d@G d 靕l d@H do  W܁܁@m }蝝d @J 蝝d  <W|aHeadings Table }H蝝d @L H蝝d  <W}a }H蝝d @N H蝝d  <W~a }H@P H =!Paragraph ForPAmat }HH@R HH  =WaHeading Level }H@T H  =Wa Comments }H@V H >W aTitle }HH@X HH  >Wa }H@Z H  >Wa }KH @\ KH  ?Wa Heading1 }HKH @^ HKH  ?Wa }KH @` KH  ?Wa }WH @b WH  @Wa Heading2 }HWH @d HWH  @W a }WH @f WH  @W a }cH @h cH  AW a }HcH @j HcH  AW a }cH @l cH  AW a HH=HHi  T܁܁|pends on the semaphore  xcond . When restarted, it indicates it is done with the  x . wait  by sub0큩tracting  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 . !U lines 16-21First, the process indicates it will be executing an  x . signal  by adding  1  to  urgentcount . It then 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 ). A` HH=HH7 靕l}?H @> #?H @;Wa Replace With }H @ >"$H @;WaHead }H @">#%H @;Wa Comments }? @$>$&? @BWa }?H @&>%'?H @BW a }H @(>&(H @BW!a }H @*>')H @BW"a }d @->(.d @CW#aCharacter Macros HH;"HH❝+G܁e HH;$3HH**靕l}?d @/>?d @CW$a }?d @1>?d @CW%a }? @3>)/? @DW&a Macro Name }?H @5>.0?H @DW'a Replace With }H @7>/1H @DW(a Comments }? @9>0<? @EW)a HUV ;.HUV ❝3G܁e HUV ;05+HUV 22靕l H$ ;1H$ 5G܁e H$ ;33H$ 44靕l HH;4HHǝ007 `Monitors and Semaphores 0,` Introduction 1܁ 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. 3b` Algorithm 4 ܁t`K1 var mutex ,  urgent ,  xcond : semaphore; 5ā`D 2  urgentcount ,  xcondcount : integer; 7`?The body of each procedure in the monitor is set up like this: 8 `*3  down ( xmutex ); 9`! 4 (* procedure body*) :`9 5 if   urgentcount  > 0  then ;`- 6  up ( urgent ) <` 7 else =`- 8  up ( mutex ); ?`EEach  x . wait  within the procedure is replaced by: @ `:9  xcondcount  :=  xcondcount  + 1; A `: 10  if  urgentcount  > 0  then B`) 11 up ( urgent ) C` 12 else D`. 13  up ( mutex ); E`* 14 down ( xcond ); F`; 15 xcondcount  :=  xcondcount  - 1; H`GEach  x . signal  within the procedure is replaced by: I `=16  urgentcount  :=  urgentcount  + 1; J `? 17  if  xcondcount  > 0  then begin K`, 18 up ( xcondsem ); L`1 19  down ( urgent ); M` 20 end ; N`= 21 urgentcount  :=  urgentcount  - 1; P` Comments Q܁ |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 . !R vline 2The integer  urgentcount  indicates how many processes are suspended as a result of a  signal  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 ). !S mlines 3-8Since only one process at a time may be in the monitor, the process entering the monitor procedure 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 ) ). aT lines 9-15First, the process indicates it will be executing an  x . wait  by adding  1  to  xcondcount . It then esignals some other process that that process may proceed (using the same priority as above). It susHH;6HH 66 靕ld=GK EGxR>EGxREPwEPw TableFootnote}?H @;>1=?H @EW*a }H @=><H @EW+a d@A??d@B>d@@ 靕l d@C>dR=?RUX[^adgjmpsvy| %).1H$ =:IH$ HH靕l H$ =:H$ GW܁܁l@April 19, 1999ECS 150 Spring 1999Page 2 HUV >:GKHUV JJ靕l HUV >:HUV ❝IW܁܁l?Last modified at 10:56 pm on Monday, April 19, 1999 HH>:IHHLL 靕l HH>:HH❝KW2܁܁e dLeftd:Rightd ReferenceddHTMLd>HTMLd HeadingsdĿ@@ GMapping Table Title. Ŀ@@ GBody. Ŀ@@ GFooter. f@T G TableTitleT:Table : .  f@ GBody. Ŀ@@ GHeader Double Line. f@ G CellFooting. f@ G CellHeading. f@ G CellBody. Ŀ@@ GMapping Table Cell.  f@PGTitleBody. Ŀ@@Mapping Table Cell. Ŀ@@ Mapping Table Cell. Ŀ@@ GMapping Table Cell. f@T GHeading1Body. f@ G .$.H.l..... .D.h.Code. f@ GBody. f@ G BodySpaced. f@ G Bulleted\t. f@ G...Date. mf@ Gl. DateProject. Hf@ GH. LineComment. Ŀ@@ GHeader Double Line. f@T GHeading1Body. f@ G Numbered.\t. f@E G Numbered1.\tNumbered. f@ G NumberedSpaced.\t. f@ G.Reading.  f@PGTitleBody. f@$G.Line Single Line. f@ GCellBody. f@ G CellHeading. f@ G Footnote. f@T GHeading2Body. f@T G HeadingRunInBody. f@ G Indented. f@ G TableFootnote. f@T G TableTitleT:Table : . f@ G .$.H.l..... .D.h.Code. Hf@ GH. LineComment.  G G G蜜  G G G   G G G G     GG蜜EmphasisG蜜EquationVariables   蜜 BoldItalic ۸GItalic GBoldZZThinMediumDoubleThick@ Very Thin HHHHHFormat A HHHHHFormat BH Mapping TableH Mapping Tableh*|#HHHHHf$*DHH+5?HH&69?HH :B?HHH CE?HH*6 ? @ h( A B C D E h  F G H I J h  K L M N O 𝝡h  P Q R S T ȝh( UVWXYh Z[\]^h_`abc7h defghChijklm]h(nopqr֝h stuvw띝h xyz{|h(}~h h    𝝡h  h h h)h  !"#$5h%&'()Oh  *+,-.[h!/ 0 1 2 3 uh "4!5!6!7!8!蝝h!#9":";"<"="h ">#?#@#A#B# %C$D$E$ $&F%G%H%ם %'I&J&K& &(L'M'N'ԝ')O(P(Q(((*@R)S)T)D )@U*V*W*V ,@X+Y+Z+f +-@[,\,],r ,.@^-_-`-~ -/@a.b.c..0@d/e/f//1@g0h0i002@j1k1l113@m2n2o224@p3q3r3 35@s4t4u4& 4@v5w5x58 7@y6z6{6H 68@|7}7~7T79@888n 8@999 ;@:::: :B@ ;";#;$;蝝 =  <<<<> ====? >>>K >@ ???W ?A @@@c @ AAA ;@%B&B'B(B D@)C,C-C CE@.D/D0D D@1E>> d BlackT!WhiteddARedddŝGreendd BluedCyandMagentad YellowHeader/Footer $1Header/Footer $1Header/Footer $2Header/Footer $2IndexIndexCommentCommentSubjectSubjectAuthorAuthorGlossaryGlossaryEquationEquation Hypertext Hypertext  Cross-Ref Cross-Ref Conditional TextConditional TextPositionFMPrivatePositionFMPrivateRangeEndFMPrivateRangeEndFMPrivate HTML Macro HTML Macro M.Times.P Times-Roman FrameRoman M.Times.B Times-Bold FrameRoman M.Helvetica.BHelvetica-Bold FrameRoman M.Geneva.PGeneva FrameRoman M.Times.I Times-Italic FrameRoman M.Courier.B Courier-Bold FrameRoman M.Courier.ICourier-Oblique FrameRoman M.Courier.PCourier FrameRomanM.Helvetica.BIHelvetica-BoldOblique FrameRomanTCourierGeneva HelveticaFTimes#Regular#Roman MediumBoldRegular ObliqueItalic<Ӱ5n8k ǔnP`迗#'2^31Q]?`H},io)V@8ތ?Ɋ4%g M(6_Õyhݱ^1_/-"c~@~vt.֭O>(Y荥I@/*"Qz܊~zJ`H-4