AaMr2y  0 @0pp  `P@ P`0PHH $ @d HHHHff@  d Footnote TableFootnote**.\t.\t/ - :;,.!?cZ+ cxTOCHeading1Heading2 Tanenbaum   PEquationVariablesJ?@j@@@A 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++AGGII33557AMMA???? ? ? ??????????!?#?%?'?)?+?-?/?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.='@@@;#$@@@;/;2F66.Ga62.@AAAAA A AAAAAAAAA$ C'I8.Hl64.F65.=F,F-F$Ea& Hm,Hn$Ho)a.Hp)b.Hq)c.Hr)d.>>>$Hs)e.===I I67.I 9.I$ PF-Gi63.G}G}F-F$F)a.F)b.F)c.F)d.F)e.G)a.G)b.GxG}G}G}G}G}G}dq5+dE HHEHH|  X ܁܁brilliant idea: Implement segmentation, but let the  least significant m  bits of a virtual adress be used to select the 큩@hsegment, and let the other bits determine the offset. Should the designer retire or get a raise? Why? 6` Extra Credit / ܁`Z( 10 points )  Prove that Belady's anomaly cannot occur in a stack algorithm. ZI |( 15 points ) A particular database program repeatedly scans an array of 1,000 pages. Each scan starts with page 0 0Wmand continues to page 999. There is only enough main store to hold 100 pages. None of the page replacement spolicies we discussed does very well. Suggest a different policy that will do as well as the optimal page replace@"ment policy OPT for this program. C[ ` 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, ܁܁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 HHEHH7 靕l}?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ŝ007J ` Homework 4 M܁`2Due Date : June 8, 1999 Points : 100 LN`Short-Answer Questions  ܁]`\These can be answered in a sentence or two, and are intended to reinforce important points. i`M( 4 points ) What is the difference between segmentation and paging? ! w( 4 points ) Consider a logical address space of eight pages of 1024 words each, mapped onto a physical memory @Yof 32 frames. How many bits are there in the logical address? In the physical address? 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. != {( 12 points ) A virtual memory has a page size of 1024 words, eight virtual pages, and four physical page frames. @The page table is as follows: t`"virtual page  page frame u `03 v`11 w`2 not in main memory x`3 not in main memory y`42 z`5 not in main memory >`60 ?`7 not in main memory ^`BMake a list of all virtual addresses that will cause page faults. _`OWhat are the physical addresses for 0, 3728, 1023, 1024, 1025, 4096, and 7800? 0 `D( 25 points ) Consider the following page reference string: 8`1 2 3 4 1 5 6 2 1 !9 hHow many page faults would occur for the following replacement algorithms, assuming first 4, and then 7 @kframes? Remember all frames are initially empty, so your first unique pages will all cost one fault each. :`First In First Out (FIFO) ;`Optimal (OPT, MIN) <`Least Recently Used (LRU) =`hNot Recently Used, Not Used Recently (NRU, NUR); assume all references to pages 2, 4, and 6 are writes. B`Clock 1 `d( 20 points ) Consider a demand paged system with the following time-measured utilizations: 4`CPU utilization20% ,`Paging disk97.7% D`Other I/O devices5% I`_Which (if any) of the following will (probably) improve CPU utilization? Explain your answer. J`Install a faster CPU. K`Install a bigger paging disk. L`)Increase the degree of multiprogramming. M`)Decrease the degree of multiprogramming. N`#Install faster, other I/O devices.  `5( 20 points ) Consider the reference string 3`w  = 1234523432442444 #5  lAssuming the working set replacement strategy, determine the minimum window size such that the string genermates at most five page faults. Show which pages are in memory at each reference, as well as which pages are @.being brought into, and removed from, memory. AX z( 15 points ) You are the president of Cheapo Computronics, Inc., and your star hardware designer has suggested a HH;6HH66 靕ld>GM EGxR>EGxREPwEPw TableFootnote}?H A>1=?H @EW*a }H A><H @EW+a dA??dA >d@@ 靕l dA!>dR=?RUX[^adgjmpsvy| %).1H$ >:IH$ HH靕l H$ >:H$ GW>܁܁h4May 27, 1999ECS 150 Spring 1999Page 1 HUV >:GMHUV JJ靕l HUV >:HUV ❝IW?܁܁l>Last modified at 10:43 am on Tuesday, May 25, 1999 HH>:IHHNN 靕l HH>:HH❝MW@ ܁܁` dLeftd:Rightd ReferenceddHTMLd>HTMLd HeadingsdĿ@@ QMapping Table Title. Ŀ@@ QBody.  f@PRTitleBody. Ŀ@@ QFooter. f@T Q TableTitleT:Table : .  f@PRTitleBody. f@ Q BodySpaced. f@T RHeading1Body. mf@ Ql. DateProject. Ŀ@@ QHeader Double Line. f@ Q NumberedSpaced.\t. Ŀ@@ QHeader Double Line. f@ Q CellFooting. f@ Q CellHeading. f@ Q CellBody. Ŀ@@ QMapping Table Cell. f@N Q Numbered N:.< =0>. Ŀ@@/Mapping Table Cell. f@$Q.Line Single Line. Ŀ@@ /Mapping Table Cell. Ŀ@@ QMapping Table Cell. f@ QCellBody. f@ Q CellHeading. f@T QHeading2Body. f@T QHeading2Body. f@T Q HeadingRunInBody. f@ Q Indented. f@ Q TableFootnote. f@T Q TableTitleT:Table : . f@ R  Body. f@ R Body. f@T RHeading1Body. f@ R  Body. $f@N Q$. Lettered N:< >.. f@ Q Footnote. $f@N Q$. Lettered N:< >.. f@ R  Body. f@ R  lBody. f@N R   Numbered N:.< =0>. f@NE R   Numbered1 N:.Numbered. f@N R  Numbered N:.< =0>. f@ R ...Date. f@ R .Reading. f@NE R  Numbered1 N:.Numbered. f@ R  Bulleted\t. Ŀ@@ R $ H l      D h  ManHeading. Ŀ@@ R  $ H l      D h  ManBody. Ŀ@@ R ManHeading2. $$Ŀ@@   $ H l      D h  ManCode. f@ Q.Date HW Single Line. f@ Q.Date HW Single Line. -HHf@ R  Body. HHf@ R  c . .Body.  Q Q Q蜜 / Q QRQ蜜Emphasis R  Q R  ۸M Symbol Q/ QQ蜜EquationVariables R Q /  蜜 BoldItalic ۸Q Italic QBold M Symbol Q  ۸R  SubscriptZZThinMediumDoubleThick@ 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 FrameRoman M.Symbol.PSymbol FrameRomanM.Helvetica.BIHelvetica-BoldOblique FrameRoman M.Times.I Times-Italic FrameRomanbCourier. HelveticaLSymbolPTimesQTimes New Roman Monotype!Regular$Roman MediumBoldRegular ObliqueItalic\ #f*Lc+*Yվ}a% qgCi).?m@Ij(SGI<1;K^9OqtȪq報<^1[.fPfc3;!I\727(HέpFYv