Aa{rv  `PP 0  P`p@Pp  pHH $ @d HHHH̀̀̀ff@  d Footnote TableFootnote**.\t.\t/ - :;,.!?* cN $ d;TOCHeading1Heading2   PEquationVariablesF);`<<=7=P=i=AAAA <$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>EHTML Headings++AGGII335577AKKA;b;d;f;h;j;l;n;p;r;t;v;x;z;|;~;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;<<<<<< < <<<<<<<<<<< <"<$<&<(<*<,<.<0<2<4<6<8<:<<<>HH  W,eH* }H ;=?H  W-eN }H ;>@H  W.eN } H ;?A H  W/e }H(;@BH(  W0e P:Numbered }HH(;ACHH(( 1eP 2e Parent = OL Q3e 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((GeLI He Parent = UL QIe 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((beLI ce Parent = OL Qde Depth = 0 }]H( H "W4e }©H <=?©H #W5e }H©H <>@H©H #W6e }©H <?A©H #W7e }©H <@B©H #W8e } ©H <AC ©H #W9e }»d <BF»d $W:eHTML Options Table }D»d <D»d $W;e }D»d <D»d $W<e }D <CGD %W=e }DH <FHDH %W>e }H <GIH %W?e }D <HJD &W@e Image Format }DH <IKDH &WAeIMAGGIF }H <JLH &WBe }D <KMD 'WCeBanners }DH <LNDH 'WDeN }H <MOH 'WEe }D<NPD(F% Banner ReferPE ence Frame }DH<OQDH (WGe }H<PH (WHe }D(<DSD((F)I% Copy Files  Imported by PE Rerefernce }DH(<DRTDH( F)WJe }H(<DSUH( F)WKe }DD <DTVDD F*WLe }DDH <DUWDDH F*WMe }DH <DVXDH F*WNe }Vd <DW[Vd F+WOeSystem Macros }?Vd <D?Vd F+WPe }?Vd <D?Vd 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 =D_arH F-WWe }~? =D`b~? F.WXe EndOfDoc }?~H = Dac?~H F.WYe }~H = Dbd~H F.WZe }?= Dce?F/[% StartOfSubPEDoc }?H=Ddf?H F/W\e }H=DegH F/W]e }?=Dfh?F0^% EndOfSubPEDoc }?H=Dgi?H F0W_e }H=DhjH F0W`e }?=Dik?F1a% StartOfFirstPESubDoc }?H=Djl?H F1Wbe }H=DkmH F1Wce }?=Dln?F2d% EndOfFirstPESubDoc }?H=!Dmo?H F2Wee }H=#DnpH F2Wfe }?=%Doq?F3g% StartOfLastPESubDoc }?H='Dpr?H F3Whe }H=)DqsH F3Wie } ?=+Drt ?F4j% EndOfLastPESubDoc }? H=-Dsu? H F4Wke } H=/Dtv H F4Wle }&? =1Duw&? F5Wme }?&H =3Dvx?&H F5Wne }&H =5Dwy&H F5Woe }8d =8Dx|8d F6WpeCross-Reference Macros }?8d =:D?8d F6Wqe }?8d =<D?8d F6Wre }H? =>Dy}H? F7Wse Macro Name }?HH =@D|~?HH F7Wte Replace With }HH =BD}HH F7Wue Comments }T?=DD~T? F8Wve See Also }?TH=FD?THF8w% See Also: PE <$paratext> }TH=HDTH F8Wxe }n? =JDn? F9Wye }?nH =LD?nH F9Wze }nH =NDnH F9W{e }d =QD d F:WeGeneral Macros }?d =SD?d F:We }?d =UD?d F:We }?d =WD?d F:We }? =YD"? F;We Macro Name d= d= d l d= do  WBm }d = d  <W|eHeadings Table }Hd = Hd  <W}e }Hd = Hd  <W~e }H= H =%Paragraph ForPEmat }HH= HH  =WeHeading Level }H= H  =We Comments }H= H >W eTitle }HH= HH  >We }H= H  >We }KH = KH  ?We Heading1 }HKH = HKH  ?We }KH = KH  ?We }WH = WH  @We Heading2 }HWH = HWH  @W e }WH = WH  @W e }cH = cH  AW e }HcH = HcH  AW e }cH = cH  AW e }?H =[D #?H F;We Replace With }H =]D"$H F;W eHead }H =_D#%H F;W!e Comments }? =aD$&? FCW"e }?H =cD%'?H FCW#e }H =eD&(H FCW$e }H =gD')H FCW%e }d =jD(.d FDW&eCharacter Macros HHˆ;"HHˆ+Ge HHˆ;$3HHˆ**l}?d =lD?d FDW'e }?d =nD?d FDW(e }? =pD)/? FEW)e Macro Name }?H =rD.0?H FEW*e Replace With }H =tD/1H FEW+e Comments }? =vD0B? FFW,e HUV ;.HUV 3Ge HUV ;05+HUV 22l H$ ;1H$ 5Ge H$ ;33H$ 44l HHˆ;4HHˆfE7  ` Homework #4  `2Due Date:  Thursday, March 9, 2000 at 11:59PM >`)Points:  60 regular, 20 extra credit O`Short-Answer Questions a`\These can be answered in a sentence or two, and are intended to reinforce important points. 7ms`t( 5 points ) How does the Working Set replacement strategy relate job scheduling to memory management?  D x( 5 points ) Consider a logical address space of 16 pages of 4096 words each, mapped onto a physical memory of D=@X1024 frames. How many bits are there in the logical address? In the physical address? 0`Long-Answer Questions 3D< tThese questions require some thought and longer answers than the short-answer questions. They are intended to have D;@`you use the concepts discussed in class, to be sure you understand them and can work with them. ɑ z( 10 points ) Assume that we have a paged memory system with a cache to hold the most active page table entries. 0ՑqIt takes 20ns to search the cache. If the page table is normally held in memory, and memory access time is 1s, uwhat is the effective access time if the hit ratio is 85%? What hit ratio will be necessary to reduce the effective @"memory access time to 1.1s?  J`D( 20 points ) Consider the following page reference string: K`&1 2 3 4 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 L* kHow many page faults would occur for the following replacement algorithms, assuming 1, 2, 3, 4, and then 5 !*@kframes? Remember all frames are initially empty, so your first unique pages will all cost one fault each. M`First In First Out (FIFO) O`Least Recently Used (LRU) Ew` y( 20 points ) This problem is meant to show that page size has a complex effect on performance. Assume that the Qw_@&total amount of real memory is fixed. 4]*`bGive an example of a reference string showing that doubling the page size can reduce page faults. 6i)`aGive an example of a reference string showing that halving the page size can reduce page faults. ?~` Extra Credit ( r( 10 points ) Tanenbaum, and many other authors, refer to the LOOK and SCAN algorithms as elevator algo0'{rithms. What is the major conceptual difference between disk scheduling and elevator scheduling? ( Hint : are @*we trying to minimize elevator movement?) < k( 10 points ) Why does the MINIX memory management scheme make it necessary to have a program like R@+chmem ? (text, chapter 4, problem 19) HHˆ;6HHˆ66 ldAGK }?H =xD1C?H FFW-e }H =zDBH FFW.e d=~EEd=DdFF l d=DdRCERUX[^adgjmpsvy| %).1H$ A:IH$ HHl H$ A:H$ GWFh9February 28, 2000ECS 150 Winter 2000Page  1  HUV A:GKHUV JJl HUV A:HUV IWGh@Last modified at 9:36 am on Wednesday, March 1, 2000 HHˆA:IHHˆLL l HHˆA:HHˆKWH` dLeftd:Rightd ReferenceddHTMLdDHTMLd Headings @@ QMapping Table Title. @@ QBody.  f@PQTitleBody. $f@L Q$. Lettereda L:.. @@ QFooter. f@T Q TableTitleT:Table : . $f@L Q$. LetteredL:.. f@ QBody. f@ Q NumberedSpaced. f@T QHeading1Body. L̀Lf@N Q Numbered N:.< =1>. f@ QBody. f@ Q BodySpaced. f@ Q Bulleted\t. f@ QBody. @@ QHeader Double Line. f@ Q CellFooting. f@ Q CellHeading. f@ Q CellBody. @@ QMapping Table Cell. f@ Q...Date. @@/Mapping Table Cell. mf@ Ql. DateProject. @@ /Mapping Table Cell. @@ QMapping Table Cell. @@ QHeader Double Line.  f@T QHeading2Body. f@  $.6.Z.~..CodeC. f@T QHeading1Body. $f@ Q Answer. f@ Q Answer1ItalicAnswer: . f@ Q NumberedSpaced. f@ Q.Reading.  f@PQTitleBody.  f@$Q.Line Single Line. f@ QCellBody. f@ Q CellHeading. f@ Q Footnote. f@T QHeading2Body. f@T Q HeadingRunInBody. f@ Q Indented. f@ Q TableFootnote. f@T Q TableTitleT:Table : . f@NE Q Numbered1 N:.Numbered. $f@L Q$. Lettereda L:.. $f@L Q$. LetteredL:.. L̀Lf@N Q Numbered N:.< =1>. 6$f@R Q6. Romani R:.. 6$f@R Q6. RomanR:.. f@ Q BodyIndent. f@  $.6.Z.u..CodeASM. Hf@ QH.. CodeComment.  Q QQ Q / Q ڝQ QQEmphasisQEquationVariables ڝQ  Q/ Q /  BoldItalic QItalic Q QBoldM Symbol  ComputerZZThinMediumDoubleThick@ Very Thin HHHHHFormat A HHHHHFormat BH Mapping TableH Mapping Tableh*|#HHHHHf$*DHH+5?HH&69?HH :C?HHH DF?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(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#B#» %C$D$E$ $&F%G%H% %'I&J&K& &(L'M'N'')O(P(Q(((*FR)S)T)D )FU*V*W*V ,FX+Y+Z+f +-F[,\,],r ,.F^-_-`-~ -/Fa.b.c..0Fd/e/f//1Fg0h0i002Fj1k1l113Fm2n2o224Fp3q3r3 35Fs4t4u4& 4Fv5w5x58 7Fy6z6{6H 68F|7}7~7T79F888n 8F999 ;F:::: :CF ;";#;$; =  <<<<> ====? >>>K >@ ???W ?A @@@c @ AAA ;F%C&C'C(C EF)D,D-D DFF.E/E0E EF1FBFCFComment AAd 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.Helvetica.BHelvetica-Bold FrameRoman M.Courier.PCourier FrameRomanM.Helvetica.BIHelvetica-BoldOblique FrameRoman M.Times.I Times-Italic FrameRoman FrameRoman FrameRomanbCourier. HelveticaLSymbolPTimes!Regular$Roman MediumBoldRegular ObliqueItalic=c~(\(Xx&3s^_c7y&rjzuzDõP?C!\b{%