Aar|}   p0  p  PpPP```PHH $ @d HHHH̀̀̀ff@  d Footnote TableFootnote**.\t.\t/ - :;,.!?/ d7dTOCHeading1Heading2   WEquationVariablesF;`<<=7=P=i=@;@=@?@A <$lastpagenum><$monthname> <$daynum>, <$year>"<$monthnum>/<$daynum>/<$shortyear>J<$hour>:<$minute00> <$ampm> on <$dayname>, <$monthname> <$daynum>, <$year>"<$monthnum>/<$daynum>/<$shortyear><$monthname> <$daynum>, <$year>"<$monthnum>/<$daynum>/<$shortyear> <$fullfilename> <$filename> <$paratext[Title]> <$paratext[Heading1]> <$curpagenum> <$marker1> <$marker2> (Continued)+ (Sheet <$tblsheetnum> of <$tblsheetcount>)Heading & Page <$paratext> on page<$pagenum>Pagepage<$pagenum>See Heading & Page%See <$paratext> on page<$pagenum>. Table All7Table<$paranumonly>, <$paratext>, on page<$pagenum>Table Number & Page'Table<$paranumonly> on page<$pagenum>Heading <$paratext>HTML Headings++A88::335577AHHA+;b;d;f;h;j;l;n;p;r;t;v;x;z;|;~;;;;;;;;;;;;;;;;;;;;;BB;;;;;;;;;;CC;;;;;;;;;;;;;;;;;;;;CDCF;;;;;;;;;;<<<<<< < <<<<<<<<CC< <"<$<&<(<*<,<.<0<2<4<6<8<:<<CC<@;W/@m }d ;ad WeHTML Mapping Table }Hd ;cHd We }Hd ;eHd We }Hd ;gHd We }Hd ;iHd We }H&;kH&% FrameMaker PE Source Item }H ;mH We HTML 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#H %New Web PEPage? }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 Q&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(( 3eP 1e Parent = OL Q2e 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((IeLI Ge Parent = UL QHe 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;^`HR% P:HeadingRuPEnIn }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<hjCH\% P:TableFootPEnote }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((deLI be Parent = OL Qce 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 }»d <DZF»d F$W:eHTML Options Table }D»d <DD»d F$W;e }D»d <DD»d F$W<e }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&A% 0001IMAGGIF p MACP0001GIEF }H6<DJLH6 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 }DD(<DTVDD((F*L% Copy Files  Imported by PE Reference }DDH(<DUWDDH( F*WMeN }DH(<DV"DH( 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 = DaR?~H F.WYe }~H = DRd~H F.WZe }?= Dce?F/[% StartOfSubPEDoc }?H=DdS?H F/W\e }H=DSgH F/W]e }?=Dfh?F0^% EndOfSubPEDoc }?H=DgT?H F0W_e }H=DTjH F0W`e }?=Dik?F1a% StartOfFirstPESubDoc }?H=DjU?H F1Wbe }H=DUmH F1Wce }?=Dln?F2d% EndOfFirstPESubDoc }?H=!DmV?H F2Wee }H=#DVpH F2Wfe }?=%Doq?F3g% StartOfLastPESubDoc }?H='DpW?H F3Whe }H=)DWsH F3Wie } ?=+Drt ?F4j% EndOfLastPESubDoc }? H=-DsX? H F4Wke } H=/DX H F4Wle }H DD_wH F5Gme C:Symbol }H DDvxH F5GneEM }H DDwYH F5GoeN },d =8|,d 6WpeCross-Reference Macros }?,d =:?,d 6Wqe },d =<,d 6Wre }<? =>y}<? 7Wse Macro Name }?<H =@|~?<H 7Wte Replace With }<H =B}<H 7Wue Comments }H?=D~H? 8Wve See Also }?HH=F?HH8w% See Also: PE <$paratext> }HH=HHH 8Wxe }Vd ADVd F+Wye }fH AD\]fH F,WzeHead }rH AD_`rH F-W{e }hd =Q hd :WeGeneral Macros }?hd =S?hd :We }hd =Uhd :We }hd =Whd :We }x? =Y"x? ;We Macro Name d= d= d l d= du  WBm }d = d  <W|eHeadings Table }Hd = Hd  <W}e }Hd = Hd  <W~e }H= H  =WeHeading Level }HH= HH =%Paragraph ForPEmat }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 e1 }HcH= HcH AW  eTitle }cH= cH  AW e }?H Ax ?H BWBe... }H AzH BWCe d@48H}?xH =[ #?xH ;We Replace With }xH =]"$xH ;W eHead }xH =_#%xH ;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ˆr007  ` Homework #1  `4Due Date : Tuesday, February 8, 2000 at 11:59PM >`Points : 100  ` ! t( 20 points ) The following table shows domains and ranges for a system of processes along with known prece@dence constraints: 0*`  process  p 1  p 2  p 3  p 4  p 5  p 6  p 7 1t`1 domain  v 5  v 1 ,  v 7  v 4  v 4 ,  v 8  v 2  v 3  v 4 2`C range  v 4 ,  v 7  v 5  v 6  v 2  v 1 ,  v 3  v 5  v 5 ,  v 8 3` preceded by  p 1  p 1  p 2  p 3  p 3  p 4 ,  p 6 4UU fAdd the minimum number of precedence constraints to make this system of processes determinate. Do not @remove any constraints. L ;( 26 points ) For a semaphore  s , define: 0L C init [ s ] is the initial value of  s ; i start_down [ s ] is the number of times  down ( s ) has been started; m end_down [ s ] is the number of times  down ( s ) has been completed; and e end_up [ s ] is the number of times  up ( s ) has been completed. !A useful semaphore invariant is:   end_down [ s ] = min( start_down [ s ],  init [ s ] +  end_up [ s ]); Show that X0  end_down [ empty ]  end_down [ full ]  n ofor the version of the producer-consumer solution using semaphores in the handout  Process Synchronization @and Communication , p. 11. 6=x z( 14 points ) Indicate how each of the following items could be incorporated in the monitor mechanism (a sentence Iw@Kor two for each is sufficient; you do not have to show an implementation). UB`type of request 8aA`× at which the requests were made 9`request parameters :`process information ;`priority relation <`local state of resource =`history information 73`y( 20 points ) Show that the  ordered request policy  of Havender prevents deadlocks (text, problem 3.4). 5 z( 20 points ) Given that the mutual exclusion, hold and wait, and no preemption conditions are in place, consider 0qthe following strategy: All processes are given unique priorities. When more than one process is waiting for a qresource and the resource becomes available, allocate the resource to the waiting process with the highest prior@oity. Either prove this prevents deadlock or give an example in which this strategy does not prevent deadlock. ?$` Extra Credit @ w( 10 points ) (Tanenbaum) Cinderella and the Prince are getting divorced. To divide their property, they have p nagreed on the following algorithm. Every morning, each one may send a letter to the other's lawyer requesting uone item of property. Since it takes a day for letters to be delivered, they have agreed that if both discover that qthey have requested the same item on the same day, the next day they will send a letter cancelling the request. mAmong their property is their dog, Woofer, Woofer's doghouse, their canary Tweeter, and Tweeter's cage. The sanimals love their houses, so it has been agreed that any division of property separating an animal from its house qis invalid, requiring the whole division to start over from scratch. Both Cinderella and the Prince desperately lwant Woofer. So they can go on (separate) vacations, each spouse has programmed a personal computer to hanodle the negotiation. When they come back from vacation, the computers are still negotiating. Why? Is deadlock @!possible? Starvation? Discuss. HHˆ;6HHˆ66 lH$ @5!:H$ 99l H$ @6!H$ 8Wl8January 25, 2000ECS 251 Winter 2000Page  1  HUV @7!8HHUV GGl}? A|@<? GWDe }?H A~;=?H GWEe- }H A<H GWFe }? AK?? HWGe }?H A>@?H HWHe-- }H A?;H HWIe }? ANJ? IWJe }?H =x1C?H FW-e¢ }H =zBOH FW.e d=~EEd=DdFF l d=Dd$uE~ytoje`[vCFILORU"X[^adgjmpsy| %).1OLA>; HUV @8!HUV :WlBLast modified at 10:55 pm on Tuesday, January 25, 2000 HHˆ@9!:HHˆII l HHˆ@:!HHˆHW` }?H AAK?H IWKe° }H AJ>H IWLe }? AQM? JWMe }?H ALN?H JWNe® }H AMAH JWOe }? ACP? KWPe }?H AOQ?H KWQe© }H APLH KWRe }~H ADbc~H F.WSe }HADefH F/WTe }HADhiH F0WUe }HADklH F1WVe }HBDnoH F2WWe }HBDqrH F3WXe } HBDtu H F4WYe }H DDxZH F5GZeN }H DDYCH F5G[e }H DDd\H F9G\e C:Subscript }H DD[]H F9G]eEM }H DD\^H F9G^eN }H DD]_H F9G_eN }H DD^vH F9G`e }H DDiaH FLGae C:Emphasis }H DD`bH FLGbeEM }H DDacH FLGceN }H DDbdH FLGdeN }H DDc[H FLGee }H DDnfH FMGfe C:Computer }H DDegH FMGgeEM }H DDfhH FMGheN }H DDgiH FMGieN }H DDh`H FMGje }H(DDskH( FNGke P:Romani }H(DDjlH((FNleLI $e Parent = OL A%e Depth = 0 }H(DDkmH( FNGmeN }H(DDlnH( FNGneN }H(DDmeH( FNGoe }H(DDxpH( FOGpeP:Roman }H(DDoqH((FOqeLI "e Parent = OL A#e Depth = 0 }H(DDprH( FOGreN }H(DDqsH( FOGseN }H(DDrjH( FOGte }H DD}uH FPGueP:Line }H DDtvH FPGveP }H DDuwH FPGweN }H DDvxH FPGxeN }H DDwoH FPGye }H DDzH FQGze P:Lettereda }H DDy{H FQG{eH* }H DDz|H FQG|eN }H DD{}H FQG}eN }H DD|tH FQG~e }H(DDH( FRGe P:Lettered }H(DD~H((FReLI  e Parent = OL A!e Depth = 0 }H(DDH( FRGeN }H(DDH( FRGeN }H(EDyH( FRGe }HEDHFSg% P:CodeComEment }HEDH FSGeP }HEDH FSGeN }HEDH FSGeN }HE D~H FSGe }H E  H TG eP:CodeC }H E H TG eP }H E H TG eN }H E H TG eN }H E H TGe }H EH UGe P:CodeASM }H E H UGeP }H EH UGeN }H EH UGeN }H EH UGe }H E H VGe P:BodyIndent }H E"H VGeP }H E$H VGeN }H E&H VGeN }H E( H VGe }H(E*BH( WGe P:Answer1 }H(E,H((WeLI e Parent = UL Ae Depth = 0 }H(E.H( WGeN }H(E0H( WGeN }H(E2H( WGe dE dEdy y| %).1OLA>;dEdE l}DFPD$ DFXg&% CSS Export E Encoding }HFRD!H FXG'e }HFTD XH FXG(e }DFVDW#DFYg)% Export EnEcoding }HFXD"$H FYG*e }HFZD#H FYG+e dLeftd!Rightd ReferenceddHTMLdDHTMLd HeadingsdHTML(@@ XMapping Table Title. @@ XBody. f@ X Answer1ItalicAnswer: . f@T XHeading2Body. @@ XFooter. f@T X TableTitleT:Table : . f@ X BodySpaced. f@ X Bulleted\t. f@ X...Date. mf@ Xl. DateProject. @@ XHeader Double Line. f@   $.6.Z.~..CodeC. f@T XHeading1Body. $f@ X Answer. f@ X NumberedSpaced. @@ XMapping Table Cell. @@ XHeader Double Line. f@ X CellFooting. f@ X CellHeading. f@ X CellBody. @@ XMapping Table Cell. f@ X.Reading. @@1Mapping Table Cell.  f@PXTitleBody. @@ 1Mapping Table Cell. @@ XMapping Table Cell. f@$X.Line Single Line.  f@PXTitleBody. f@ XCellBody. f@ X CellHeading. f@ X Footnote. f@T XHeading2Body. f@T X HeadingRunInBody. f@ X Indented. f@ X TableFootnote. @@XMapping Table Cell. L̀Lf@N X Numbered N:.< =1>. f@ X NumberedSpaced. f@NE X 6 Numbered1 N:.Numbered. L̀Lf@N X 6Numbered N:.< =1>. f@T X TableTitleT:Table : . f@NE X Numbered1 N:.Numbered. f@ X $l DhBody. f@ X $l DhBody. $f@L X$. Lettereda L:.. $f@L X$. LetteredL:.. $f@L X$. Lettereda L:.. $f@L X$. LetteredL:.. L̀Lf@N X Numbered N:.< =1>. 6$f@R X6. Romani R:.. 6$f@R X6. RomanR:.. f@ X BodyIndent. f@   $.6.Z.u..CodeASM. Hf@ XH.. CodeComment.  X XXEmphasis X 1 X ڝXXXEquationVariables 1  BoldItalic XItalic X ڝX X X X Subscript X1 X XBoldT Symbol   Computer  Subscript XXZZThinMediumDoubleThick@ Very Thin HHHHHFormat A HHHHHFormat BH333 Mapping TableH Mapping Tableh6â5HHHHH$XDHH+4?HHH68?HH :C?HHHTDB?HH*< ? @ 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 "W>#?#@#A#B#» %FC$D$E$ $&FF%G%H%6%'FI&J&K& &(FL'M'N'')FO(P(Q(((*FR)S)T)D()YFU*V*W*Vd ,FX+Y++Z+f +-F[,\,,],r ,.F^-_--`-~ -/Fa.b.R.c..0Fd/e/S/f//1Fg0h0T0i002Fj1k1U1l113Fm2n2V2o224Fp3q3W3r3 3Fs4t4X4u4h 9Fv5w5x5Y5Z5,d 7y6z6{6< 68|7}7~7H7888h L5F[9\9]9^9_9hd ;::::x :C ;";#;$; =  <<<<> ====? >>>K >@ ???W ?A @@@c@ AAA GBB B ;%C&C'C(Cd E)D,D-D DF.E/E0E EK1FBFCF HB;GH?H@H JHAIJIKI KILJMJNJ FJOKPKQKh M9F`LaLbLcLdLh NLFeMfMgMhMiMh(OMFjNkNlNmNnNh(PNFoOpOqOrOsOh QOFtPuPvPwPxPh RPFyQzQ{Q|Q}Qh(SQF~RRRRRhTRFSSSSSh UST T T T Th VT UUUUUh WUVVVVVh(#VWWWWWYFX X!X*XF"Y#Y$YComment @<@@d BlackT!WhiteddARedddGreendd 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.Courier.PCourier FrameRoman M.Helvetica.BHelvetica-Bold FrameRomanM.Helvetica.BIHelvetica-BoldOblique FrameRoman M.Times.I Times-Italic FrameRoman M.Times.BITimes-BoldItalic FrameRoman FrameRoman FrameRomanfCourier0 HelveticaSSymbolWTimes"Regular$Roman MediumBoldRegular ObliqueItalicz h% g}\f/^t8:x-1Ŭ+pquI\˪[MY|i!j\{xusEop\oܠg,MpD xe<OzH{?W׻khRë7dW=[o0I(e8~@yRD5}gqT: