Aa"r4y  0 `p P` PPHH $ @d HHHHff@  d Footnote TableFootnote**.\t.\t/ - :;,.!?cZ! cZTOCHeading1Heading2 Tanenbaum   YEquationVariablesD?@j@@@A A'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++AGGII335577AMMA8???? ? ? ??????????!?#?%?'?)?+?-?/?1?3?5?7?9?;?=???A?C?E?G?I?K?L?M?O?Q?S?U?W?Y?[?]?_?a?b?c?e?g?i?k?m?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@l@n@p@r@t@v@x@z@|@~@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@A)A+A-A/A1A3A5A7A9A;A=A?AAACAEAGAIAKAL$Ai81.='Aj62.@@@;#$@@@;/;2;56 10.Ak63.@AAAAA A AAAAAAAAA$Ar64.C'D)a.A1A1=D)b.A1A1D1D0D67.>>>$C6 11.D$68.=6 9.===IBc&9C66.C65.D%1D&$dq5+HǝHC c6 UU-C UU-UUUUd>d>; HmR>HmRHRHRFootnote Hr@>Hr@HzHz Single LineH靕> Footnote >  HD> HDHH Double LineH>  Double Line> > H֝>  Single Line> d5p77HZ֝>; TableFootnoted>d?靕l d?d1QRUX[^adgjmpsvy| %).1W, ܁܁Bm }蝝d ?蝝d WaHTML Mapping Table }H蝝d ?H蝝d Wa }H蝝d ?H蝝d Wa }H蝝d ?H蝝d Wa }H蝝d ? H蝝d Wa }H? H! FrameMaker PA Source Item }H ?H Wa HTML Item }H ?H Wa }H?H W aInclude Auto# } H? H W a Comments }H?H W a }HH? HH W aElement }H?#H W a New Topic? }H?H Wa } H? H Wa }H ?  $H Wa P:Date Line }HH ?"#%HH WaP }H ?$$&H WaN }H ?&%'H WaN } H ?(&( H Wa }EH ?*')EH Wa P:Reading }HEH ?,(*HEH WaP }EH ?.)+EH WaN }EH ?0*,EH WaN } EH ?2+- EH Wa }QH ?4,.QH WaP:Title }HQH ?6-/HQH WaH* }QH ?8.0QH WaN }QH ?:/1QH WaN } QH ?<02 QH Wa }]H ?>13]H WaP:Body }H]H ?@24H]H W aP }]H ?B35]H W!aN }]H ?D46]H W"aN } ]H ?F57 ]H W#a }iH(?H68iH( W$a P:Numbered1 }HiH(?J79HiH((%aLI &a Parent = OL Q'a Depth = 0 }iH(?N8:iH( W(aN }iH(?P9;iH( W)aY } iH(?R:< iH( W*a }띝H ?T;=띝H  W+a P:Heading1 }H띝H ?V<>H띝H  W,aH* }띝H ?X=?띝H  W-aN }띝H ?Z>@띝H  W.aN } 띝H ?\?A 띝H  W/a }H(?^@BH(  W0a P:Numbered }HH(?`ACHH(( 1aP 2a Parent = OL Q3a Depth = 0 }H(?dBDH(  W4aN }H(?fCEH(  W5aY } H(?hDF H(  W6a }H ?jEGH  W7a P:CellBody }HH ?lFHHH  W8aP }H ?nGIH  W9aN }H ?pHJH  W:aN } H ?rIK H  W;a }H ?tJLH  W<aP:CellHeading }HH ?vKMHH  W=aP }H ?xLNH  W>aN }H ?zMOH  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 @ H W a }H @H W aC:Bold }HH @HH WaSTRONG }H @H WaN }H @H WaN } H @ H Wa }H@H! X:Heading & PAPage }HH@HH Wa See Also }H@H WaN }H@ H WaN } H@" H Wa })H @$!)H WaX:Page }H)H @& "H)H Wa See Also })H @(!#)H WaN })H @*"$)H WaN } )H @,#% )H Wa }5H@.$&5H! X:See HeadPA ing & Page }H5H@0%'H5H Wa See Also }5H@2&(5H WaN }5H@4')5H WaN } 5H@6(* 5H W a }OH @8)+OH W!a X:Table All }HOH @:*,HOH W"a See Also }OH @<+-OH W#aN }OH @>,.OH W$aN } OH @@-/ OH W%a }[H@B.0[H &! X:Table NumPA ber & Page }H[H@D/1H[H  W'a See Also }[H@F02[H  W(aN }[H@H13[H  W)aN } [H@J24 [H  W*a }uH@L35uH !W+a X:Heading }HuH@N46HuH!,! USE XREF PAFMT }uH@P57uH !W-aN }uH@R68uH !W.aN } uH@T79 uH !W/a }蝝H@V8:蝝H "W0a P:Header }H蝝H@X9;H蝝H"1!THROW PAAWAY }蝝H@Z:<蝝H "W2aN }蝝H@\;=蝝H "W3aN } 蝝H@^<> 蝝H "W4a }H @`=?H #W5a }HH @b>@HH #W6a }H @d?AH #W7a }H @f@BH #W8a } H @hAC H #W9a }d @kBFd $W:aHTML Options Table }Dd @mDd $W;a }Dd @oDd $W<a }D @qCGD %W=a }DH @sFHDH %W>a }H @uGIH %W?a }םD @wHJםD &W@a Image Format }DםH @yIKDם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 dA$ dA% d 靕l dA& do  W ܁܁Bm }蝝d A( 蝝d  <W|aHeadings Table }H蝝d A* H蝝d  <W}a }H蝝d A, H蝝d  <W~a }HA. H =!Paragraph ForPAmat }HHA0 HH  =WaHeading Level }HA2 H  =Wa Comments }HA4 H >W aTitle }HHA6 HH  >Wa }HA8 H  >Wa }KH A: KH  ?Wa Heading1 }HKH A< HKH  ?Wa }KH A> KH  ?Wa }WH A@ WH  @Wa Heading2 }HWH AB HWH  @W a }WH AD WH  @W a }cH AF cH  AW a }HcH AH HcH  AW a }cH AJ cH  AW a UTāXC 9UTāXUTοUTA}?H @> #?H @;Wa Replace With }H @>"$H @;WaHead }H A>#%H @;Wa Comments }? A>$&? @BWa }?H A>%'?H @BW a }H A>&(H @BW!a }H A>')H @BW"a }d A >(.d @CW#aCharacter Macros HH;"HH❝+G ܁e HH;$3HH**靕l}?d A >?d @CW$a }?d A>?d @CW%a }? A>)/? @DW&a Macro Name }?H A>.0?H @DW'a Replace With }H A>/1H @DW(a Comments }? A>0<? @EW)a HUV ;.HUV ❝3G܁e HUV ;05+HUV 22靕l H$ ;1H$ 5G܁e H$ ;33H$ 44靕l HH;4HHɁ )7J ` Homework 2 M܁`4Due Date : April 29, 1999 Points : 100 LN`Short-Answer Questions  ܁]`\These can be answered in a sentence or two, and are intended to reinforce important points. i`H( 3 points ) What is a race condition? (Tanenbaum, problem 2.5) `8( 4 points ) What are the Bernstein conditions? `\( 4 points ) What conditions must a solution to the critical section problem meet?. !- r( 4 points ) Suppose someone devised a new synchronization primitive she claimed were as powerful as sema@)phores. How would she prove this claim? 2`Long-Answer Questions . ܁ sThese questions require some thought and longer answers than the short-answer questions. They are intended to have @`you use the concepts discussed in class, to be sure you understand them and can work with them. !$ ~( 15 points ) A  binary semaphore  is most commonly defined as a semaphore whose integer value can range only obetween 0 and 1. (This is slightly different than Tanenbaum's definition on p. 68, but is more common.) Imple@Yment counting semaphores using binary semaphores. (variation of Tanenbaum, problem 2.11) !# y( 20 points ) Instead of test-and-set, some computers provide an atomic instruction that sets the new value to 1 @+greater than its old value, as shown here: 0(`Vfunction  testandinc( var  lock:  integer ):  integer ; 1'!`begin 4`testandinc := lock; 5`lock := lock + 1; 6`!end (*  testandinc  *) 7 `dShow how to use this instruction to implement locks. (Hint: you must be wary of integer overflow.) 18Y w( 25 points ) On page 77 of the text, Tanenbaum claims that the program in Fig. 2-18 solves the Dining Philosotphers' problem. Either prove or disprove this claim. If the claim is false, fix the program (that is, implement a @@solution to the dining philosophers' problem using semaphores). B ( 25 points ) Synchronization within monitors uses condition variables and two special operations,  wait  and  signal . A more general form of synchronization would be to have a single primitive,  waituntil , that had an arbitrary  @CBoolean predicate as parameter. Thus, one could say, for example, '(`,waituntil  x < 0  or  y + z < n ( xThe  signal  primitive would be no longer needed. This looks more general than that of Hoare or Brinch Hansen, @but is not used. #/ Show that  waituntil  is as general as Hoare's scheme (that is, any monitor using Hoare's  wait  and  signal  prim@Hitives can be written using it.) Is it in fact more general? Justify. 3`iWhy is this form not used in practise? (Hint: think about the implementation.) (Tanenbaum, problem 2.13) i` Extra Credit I ܁ z( 5 points ) When a message is sent to a sleeping process in MINIX, the procedure ready is called to put that pro0pcess in the proper scheduling queue. This procedure starts out by disabling interrupts. Explain. (Tanenbaum, @problem 2.30) `( 5 points )  The MINIX procedure mini_rec contains a loop. Explain what it is for.  (Tanenbaum, problem 2.31) AA hw( 5 points ) Can the precedence graph  below be implemented using  parbegin  and  parend ? HH;6HH66 靕l-C A-d>GM EGxR>EGxREPwEPw TableFootnote}?H A>1=?H @EW*a }H A><H @EW+a dA??dA >d@@ 靕l dA!>dR=?RUX[^adgjmpsvy| %).1 םāC 9BםāםοםB āC ACāΡCUV-C BDUV-UVUV XC CEX@@DUVUV-C DFUVUV-UVUVUVUV UUC EOUUUU@UU@EH$ >:IH$ HH靕l H$ >:H$ GW>܁܁h6April 15, 1999ECS 150 Spring 1999Page 1 HUV >:GMHUV JJ靕l HUV >:HUV ❝IW?܁܁l@Last modified at 1:33 pm on Thursday, April 15, 1999 HH>:IHHNN 靕l HH>:HH❝MW@ ܁܁d ᗯC FPᗯ@@FA-C OQA-AA UVXC PRUVXD>D>GA-C QSA-AA UVXC RTUVXD>D>H UUUVщyC SUUUUVщyUUD>UUD>IUUUuC TWUUUuUUUuUUUuЁUZ띛C UXЁUZ띛ЁUZЁUWUZā띛C W[UZā띛UUUZUWā띛D Xbā띛݁UU띛D [cUU띛UUUUUVā띛D bUVā띛UVdLeftd:Rightd ReferenceddHTMLd>HTMLd HeadingsĿ@@ ZMapping Table Title. Ŀ@@ ZBody.  f@P[TitleBody. Ŀ@@ ZFooter. f@T Z TableTitleT:Table : .  f@P[TitleBody. f@ Z BodySpaced. f@T [Heading1Body. mf@ Zl. DateProject. Ŀ@@ ZHeader Double Line. f@ Z NumberedSpaced.\t. Ŀ@@ ZHeader Double Line. f@ Z CellFooting. f@ Z CellHeading. f@ Z CellBody. Ŀ@@ ZMapping Table Cell. Ŀ@@3Mapping Table Cell. f@$Z.Line Single Line. Ŀ@@ 3Mapping Table Cell. Ŀ@@ ZMapping Table Cell. f@ ZCellBody. f@ Z CellHeading. f@T ZHeading2Body. f@T ZHeading2Body. f@T Z HeadingRunInBody. f@ Z Indented. f@ Z TableFootnote. f@T Z TableTitleT:Table : . f@ [  Body. f@ [ Body. f@T [Heading1Body. f@ [  Body. $f@N Z$. Lettered N:< >.. f@ Z Footnote. $f@N Z$. Lettered N:< >.. f@ [   Indented. $$Ŀ@@  ' $ H l      D h  ManCode. f@N [   Numbered N:.< =0>. f@NE [   Numbered1 N:.Numbered. f@N [  Numbered N:.< =0>. f@ [ ...Date. f@ [ .Reading. f@NE [  Numbered1 N:.Numbered. f@ [  Bulleted\t. Ŀ@@ [ $ H l      D h  ManHeading. Ŀ@@ [  $ H l      D h  ManBody. Ŀ@@ [ ManHeading2. $$Ŀ@@   $ H l      D h  ManCode. f@ Z.Date HW Single Line. f@ Z.Date HW Single Line.  Z Z Z蜜 3 Z Z[Z蜜Emphasis [  Z [  Z3 ZZ蜜EquationVariables [ Z 3 蜜 BoldItalic ۸Z Italic ZBold nG[  Z         ۸[  SubscriptZZZZdThinMediumDoubleThick@ 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 FrameRomanM.Times New Roman.BTimesNewRomanPS-BoldMT FrameRoman M.Times.B Times-Bold FrameRoman M.Helvetica.BHelvetica-Bold FrameRomanM.Times New Roman.PTimesNewRomanPSMT FrameRoman M.Courier.PCourier FrameRomanM.Times New Roman.ITimesNewRomanPS-ItalicMT FrameRomanM.Helvetica.BIHelvetica-BoldOblique FrameRoman M.Times.I Times-Italic FrameRoman M.Courier.B Courier-Bold FrameRoman M.Courier.ICourier-Oblique FrameRomanhCourier2 HelveticaYTimesZTimes New Roman Monotype"Regular$Roman MediumBoldRegular ObliqueItalicl6TC46OR<9ѤWGp(}߈E,e˴=/+Hl{t ]? z,2F:$j{6SZ:+gBU@LµV1BIDח;CI\+tj 9Mwf .֒ G