%!PS-Adobe-2.0 %%Creator: dvips by Radical Eye Software %%Title: machnix.dvi %%Pages: 12 1 %%BoundingBox: 0 0 612 792 %%EndComments %%BeginDocument: tex.pro /TeXDict 200 dict def TeXDict begin /bdf{bind def}def /bop-aux{}bdf /@rigin{ /@page-height exch def /@page-width exch def 72 Resolution div dup neg scale translate}bdf /@letter{Resolution dup -10 mul 8.5 11 @rigin}bdf /@landscape{[ 0 1 -1 0 0 0]concat Resolution dup 8.5 11 @rigin}bdf /@a4{Resolution dup -10.6929133858 mul 21 2.54 div 29.7 2.54 div @rigin}bdf /@legal{Resolution dup -13 mul 8.5 14 @rigin}bdf /@11x17{statusdict /11x17tray known{statusdict begin 11x17tray end}if Resolution dup -16 mul 11 17 @rigin}bdf /@manualfeed{ statusdict /manualfeed true put}bdf /@copies{/#copies exch def}bdf /@draft{ /bop-aux{gsave initmatrix 72 dup scale @page-width 2 div @page-height 2 div translate @page-height @page-width atan rotate /Helvetica-Bold findfont 2 scalefont setfont(DRAFT)dup stringwidth pop 2 div neg -1 moveto .95 setgray show grestore}bdf}bdf /@FontMatrix[1 0 0 -1 0 0]def /@FontBBox[0 0 0 0]def /dmystr(ZZf@@@)def /newname{dmystr cvn}bdf /df{/fontname exch def dmystr 2 fontname cvx(@@@@)cvs putinterval newname 7 dict def newname load begin /FontType 3 def /FontMatrix @FontMatrix def /FontBBox @FontBBox def /BitMaps 256 array def /BuildChar{CharBuilder}def /Encoding IdentityEncoding def end fontname{/foo setfont}2 array copy cvx def fontname load 0 dmystr 6 string copy cvn cvx put}bdf /dfe{newname dup load definefont setfont}bdf /ch-image{ ch-data 0 get}bdf /ch-width{ch-data 1 get}bdf /ch-height{ch-data 2 get}bdf /ch-xoff{ch-data 3 get}bdf /ch-yoff{ch-data 4 get}bdf /ch-dx{ch-data 5 get} bdf /CharBuilder{save 3 1 roll exch /BitMaps get exch get /ch-data exch def ch-data null ne{ch-dx 0 ch-xoff ch-yoff neg ch-xoff ch-width add ch-height ch-yoff sub setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-height ch-yoff sub .1 add]{ch-image}imagemask}if restore}bdf /dc{/ch-code exch def /ch-data exch def newname load /BitMaps get ch-code ch-data put}bdf /bop{gsave /SaveImage save def /bop-aux load exec 0 0 moveto}bdf /eop{clear SaveImage restore showpage grestore}bdf /@start{/Resolution exch def /IdentityEncoding 256 array def 0 1 255{IdentityEncoding exch 1 string dup 0 3 index put cvn put}for}bdf /p{show}bdf /RuleMatrix[1 0 0 -1 -.1 -.1]def /BlackDots 8 string def /v{gsave currentpoint translate false RuleMatrix{ BlackDots}imagemask grestore}bdf /a{moveto}bdf /delta 0 def /tail{dup /delta exch def 0 rmoveto}bdf /b{exch show tail}bdf /c{show delta 4 sub tail}bdf /d{ show delta 3 sub tail}bdf /e{show delta 2 sub tail}bdf /f{show delta 1 sub tail}bdf /g{show delta 0 rmoveto}bdf /h{show delta 1 add tail}bdf /i{show delta 2 add tail}bdf /j{show delta 3 add tail}bdf /k{show delta 4 add tail} bdf /l{show -4 0 rmoveto}bdf /m{show -3 0 rmoveto}bdf /n{show -2 0 rmoveto} bdf /o{show -1 0 rmoveto}bdf /q{show 1 0 rmoveto}bdf /r{show 2 0 rmoveto}bdf /s{show 3 0 rmoveto}bdf /t{show 4 0 rmoveto}bdf /w{0 rmoveto}bdf /x{0 exch rmoveto}bdf /y{3 2 roll show moveto}bdf /bos{/section save def}bdf /eos{clear section restore}bdf end %%EndDocument %%BeginDocument: special.pro TeXDict begin /SDict 200 dict def SDict begin /@SpecialDefaults{/hs 612 def /vs 792 def /ho 0 def /vo 0 def /hsc 1 def /vsc 1 def /ang 0 def /CLIP false def /BBcalc false def}bdf /@scaleunit 1 def /@hscale{@scaleunit div /hsc exch def}bdf /@vscale{@scaleunit div /vsc exch def}bdf /@hsize{/hs exch def /CLIP true def}bdf /@vsize{/vs exch def /CLIP true def}bdf /@hoffset{/ho exch def} bdf /@voffset{/vo exch def}bdf /@angle{/ang exch def}bdf /@rwi{10 div /rwi exch def}bdf /@llx{/llx exch def}bdf /@lly{/lly exch def}bdf /@urx{/urx exch def}bdf /@ury{/ury exch def /BBcalc true def}bdf end /@MacSetUp{userdict /md known{userdict /md get type /dicttype eq{md begin /letter{}def /note{}def /legal{}def /od{txpose 1 0 mtx defaultmatrix dtransform exch atan/pa exch def newpath clippath mark{transform{itransform moveto}}{transform{itransform lineto}}{6 -2 roll transform 6 -2 roll transform 6 -2 roll transform{ itransform 6 2 roll itransform 6 2 roll itransform 6 2 roll curveto}}{{ closepath}}pathforall newpath counttomark array astore /gc xdf pop ct 39 0 put 10 fz 0 fs 2 F/|______Courier fnt invertflag{PaintBlack}if}def /txpose{pxs pys scale ppr aload pop por{noflips{pop exch neg exch translate pop 1 -1 scale}if xflip yflip and{pop exch neg exch translate 180 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg translate}if xflip yflip not and{pop exch neg exch translate pop 180 rotate ppr 3 get ppr 1 get neg sub neg 0 translate}if yflip xflip not and{ppr 1 get neg ppr 0 get neg translate} if}{noflips{translate pop pop 270 rotate 1 -1 scale}if xflip yflip and{ translate pop pop 90 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg translate}if xflip yflip not and{translate pop pop 90 rotate ppr 3 get ppr 1 get neg sub neg 0 translate}if yflip xflip not and{ translate pop pop 270 rotate ppr 2 get ppr 0 get neg sub neg 0 exch translate} if}ifelse scaleby96{ppr aload pop 4 -1 roll add 2 div 3 1 roll add 2 div 2 copy translate .96 dup scale neg exch neg exch translate}if}def /cp{pop pop showpage pm restore}def end}if}if}def /psf$TeXscale{65536 div}def /startTexFig {/psf$SavedState save def userdict maxlength dict begin Resolution 72 div dup neg scale currentpoint translate /psf$ury exch psf$TeXscale def /psf$urx exch psf$TeXscale def /psf$lly exch psf$TeXscale def /psf$llx exch psf$TeXscale def /psf$y exch psf$TeXscale def /psf$x exch psf$TeXscale def currentpoint /psf$cy exch def /psf$cx exch def /psf$sx psf$x psf$urx psf$llx sub div def /psf$sy psf$y psf$ury psf$lly sub div def psf$sx psf$sy scale psf$cx psf$sx div psf$llx sub psf$cy psf$sy div psf$ury sub translate /showpage{}def /erasepage{ }def /copypage{}def @MacSetUp}def /doclip{psf$llx psf$lly psf$urx psf$ury currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll exch lineto exch lineto exch lineto closepath clip newpath moveto}def /endTexFig{end psf$SavedState restore}def /@beginspecial{SDict begin /SpecialSave save def Resolution 72 div dup neg scale currentpoint translate @SpecialDefaults}bdf /@setspecial{CLIP{newpath 0 0 moveto hs 0 rlineto 0 vs rlineto hs neg 0 rlineto closepath clip}{initclip}ifelse ho vo translate hsc vsc scale ang rotate BBcalc{rwi urx llx sub div dup scale llx neg lly neg translate}if /showpage{}def newpath}bdf /@endspecial{clear SpecialSave restore end}bdf /@defspecial{SDict begin}bdf /@fedspecial{end}bdf /li{lineto}bdf /rl{rlineto} bdf /rc{rcurveto}bdf /np{/SaveX currentpoint /SaveY exch def def newpath}bdf /st{stroke SaveX SaveY moveto}bdf /fil{fill SaveX SaveY moveto}bdf /ellipse{ /endangle exch def /startangle exch def /yrad exch def /xrad exch def /savematrix matrix currentmatrix def translate xrad yrad scale 0 0 1 startangle endangle arc savematrix setmatrix}bdf end %%EndDocument TeXDict begin 300 @start /fa df[<01801801C01C03803803803803803803803807007007 00700700700700700E00E00E00E00E00E00E00E11E01C21E01C21E03C21E05C43F08C439F07838 0000380000700000700000700000700000E00000E00000E00000C00000>24 30 1 10 27]22 dc [<70F8F8F870>5 5 4 0 13]58 dc[<000100030003000600060006000C000C000C0018001800 1800300030003000600060006000C000C000C00180018001800300030003000600060006000C00 0C000C00180018001800300030003000600060006000C000C000C000>16 45 3 11 23]61 dc dfe /fb df[<00E001E0038007000E001C001C0038003800700070007000E000E000E000E000E0 00E000E000E000E000700070007000380038001C001C000E000700038001E000E0>11 33 6 4 22]40 dc[10 33 5 4 22] 41 dc[17 3 2 4 22]95 dc[<1FE0003FF0007FF800783C00300E0000 0E00000E0003FE001FFE003E0E00700E00E00E00E00E00E00E00783E007FFFE03FE7E00F83E0> 19 18 2 0 22]97 dc[<7E0000FE00007E00000E00000E00000E00000E00000E3E000EFF000FFF 800F83C00F00E00E00E00E00700E00700E00700E00700E00700E00700E00E00F01E00F83C00FFF 800EFF00063C00>20 25 0 0 22]98 dc[<03F80FFC1FFE3C1E780C7000E000E000E000E000E0 00F000700778073E0E1FFC0FF803F0>16 18 3 0 22]99 dc[<003F00007F00003F0000070000 070000070000070003C7000FF7001FFF003C1F00780F00700700E00700E00700E00700E00700E0 0700E00700700F00700F003C1F001FFFE00FE7F007C7E0>20 25 1 0 22]100 dc[<03E00FF81F FC3C1E780E7007E007FFFFFFFFFFFFE000E000700778073C0F1FFE0FFC03F0>16 18 3 0 22] 101 dc[<001F00007F8000FF8001E78001C30001C00001C0007FFF00FFFF00FFFF0001C00001C0 0001C00001C00001C00001C00001C00001C00001C00001C00001C00001C0003FFE007FFF003FFE 00>17 25 1 0 22]102 dc[<03E3C007F7E00FFFE01C1CC0380E00380E00380E00380E00380E00 1C1C000FF8001FF0001BE0003800001800001FFC001FFF003FFF807803C0E000E0E000E0E000E0 E000E07001C07C07C03FFF800FFE0003F800>19 28 1 10 22]103 dc[<7E0000FE00007E0000 0E00000E00000E00000E00000E3C000EFE000FFF000F87800F03800E03800E03800E03800E0380 0E03800E03800E03800E03800E03800E03807FC7F0FFE7F87FC7F0>21 25 0 0 22]104 dc[<01 8003C003C0018000000000000000007FC07FC07FC001C001C001C001C001C001C001C001C001C0 01C001C001C07FFFFFFF7FFF>16 26 3 0 22]105 dc[17 25 2 0 22]108 dc[21 18 0 0 22]109 dc[<7E3C00FEFE007FFF000F87800F03800E03800E0380 0E03800E03800E03800E03800E03800E03800E03800E03807FC7F0FFE7F87FC7F0>21 18 0 0 22]110 dc[<03E0000FF8001FFC003C1E00780F00700700E00380E00380E00380E00380E00380 F00780700700780F003C1E001FFC000FF80003E000>17 18 2 0 22]111 dc[<7E3E00FEFF007F FF800F83C00F00E00E00E00E00700E00700E00700E00700E00700E00700E00E00F01E00F83C00F FF800EFF000E3C000E00000E00000E00000E00000E00000E00007FC000FFE0007FC000>20 27 0 9 22]112 dc[19 18 1 0 22]114 dc[<0FEC3FFC7FFC F03CE01CE01C70007F801FF007F8003C600EE00EF00EF81EFFFCFFF8C7E0>15 18 3 0 22]115 dc[<0300000700000700000700000700007FFF00FFFF00FFFF0007000007000007000007000007 000007000007000007010007038007038007038007870003FE0001FC0000F800>17 23 1 0 22] 116 dc[<7E1F80FE3F807E1F800E03800E03800E03800E03800E03800E03800E03800E03800E03 800E03800E03800E0F800FFFF007FBF803E3F0>21 18 0 0 22]117 dc[<7F1FC0FF1FE07F1FC0 1C07001E0F000E0E000E0E000E0E00071C00071C00071C00071C0003B80003B80003B80001F000 01F00000E000>19 18 1 0 22]118 dc[<7F1FC0FF9FE07F1FC01C07000E07000E0E000E0E0007 0E00071C00071C00039C00039C0003980001B80001B80000F00000F00000F00000E00000E00000 E00001C00079C0007BC0007F80003F00003C0000>19 27 1 9 22]121 dc dfe /fc df[<0070 00F001E003C007800F001E001C00380038007000700070007000E000E000E000E000E000E000E0 00E0007000700070007000380038001C001E000F00078003C001F000F00070>12 36 7 4 24] 40 dc[<6000F00078003C001E000F000780038001C001C000E000E000E000E000700070007000 70007000700070007000E000E000E000E001C001C0038007800F001E003C007800F0006000>12 36 4 4 24]41 dc[<1C3E7E7F3F1F070E1E7CF860>8 12 8 6 24]44 dc[<7FFF00FFFF80FFFF 807FFF00>17 4 3 -12 24]45 dc[<183C7E7E3C180000000000000000183C7E7E3E1E0E1C3C78 F060>7 26 8 6 24]59 dc[<000300000780001F80003F00007E0001FC0003F00007E0001FC000 3F00007E0000FC0000FC00007E00003F00001FC00007E00003F00001FC00007E00003F00001F80 000780000300>17 24 3 -2 24]60 dc[<7FFFC0FFFFE0FFFFE0FFFFE000000000000000000000 0000FFFFE0FFFFE0FFFFE07FFFC0>19 12 2 -8 24]61 dc[<600000F00000FC00007E00003F00 001FC00007E00003F00001FC00007E00003F00001F80001F80003F00007E0001FC0003F00007E0 001FC0003F00007E0000FC0000F00000600000>17 24 3 -2 24]62 dc[<00700000F80000F800 00D80000D80001DC0001DC0001DC00018C00038E00038E00038E00038E00030600070700070700 0707000707000FFF800FFF800FFF800E03800E03801C01C01C01C07F07F0FF8FF87F07F0>21 28 1 0 24]65 dc[21 28 1 0 24]69 dc[19 28 2 0 24]70 dc[<7FE000FFE0007FE0000E00000E00000E00000E00000E00000E00000E00000E00000E00000E 00000E00000E00000E00000E00000E00000E00000E00000E00700E00700E00700E00700E00707F FFF0FFFFF07FFFF0>20 28 1 0 24]76 dc[<03F3801FFF803FFF807C0F80700780E00380E003 80E00380E000007000007800003F00001FF00007FE0000FF00000F800003C00001C00000E00000 E06000E0E000E0E001E0F001C0F80780FFFF80FFFE00E7F800>19 28 2 0 24]83 dc[<7FFF00 FFFF80FFFF807FFF00>17 4 3 4 24]95 dc[<1FE0003FF8007FFC00781E00300E000007000007 0000FF0007FF001FFF007F0700780700E00700E00700E00700F00F00781F003FFFF01FFBF007E1 F0>20 20 3 0 24]97 dc[<7E0000FE00007E00000E00000E00000E00000E00000E00000E3E00 0EFF800FFFC00FC1E00F80E00F00700E00700E00380E00380E00380E00380E00380E00380F0070 0F00700F80E00FC1E00FFFC00EFF80063E00>21 28 0 0 24]98 dc[<01FE0007FF001FFF803E 0780380300700000700000E00000E00000E00000E00000E00000E000007000007001C03801C03E 03C01FFF8007FF0001FC00>18 20 3 0 24]99 dc[<001F80003F80001F800003800003800003 8000038000038003E3800FFB801FFF803C1F80380F80700780700380E00380E00380E00380E003 80E00380E00380700780700780380F803C1F801FFFF00FFBF803E3F0>21 28 2 0 24]100 dc[< 01F00007FC001FFE003E0F00380780700380700380E001C0E001C0FFFFC0FFFFC0FFFFC0E00000 7000007001C03801C03E03C01FFF8007FF0001FC00>18 20 3 0 24]101 dc[<001F80007FC000 FFE000E1E001C0C001C00001C00001C0007FFFC0FFFFC0FFFFC001C00001C00001C00001C00001 C00001C00001C00001C00001C00001C00001C00001C00001C00001C0007FFF007FFF007FFF00> 19 28 1 0 24]102 dc[<01E1F007FFF80FFFF81E1E301C0E0038070038070038070038070038 07001C0E001E1E001FFC001FF80039E0003800001C00001FFE001FFFC03FFFE07801F0700070E0 0038E00038E00038E000387800F07E03F01FFFC00FFF8001FC00>21 31 1 11 24]103 dc[<7E 0000FE00007E00000E00000E00000E00000E00000E00000E3E000EFF800FFFC00FC1C00F80E00F 00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E07FC3FCFF E7FE7FC3FC>23 28 0 0 24]104 dc[<03800007C00007C00007C0000380000000000000000000 000000007FC000FFC0007FC00001C00001C00001C00001C00001C00001C00001C00001C00001C0 0001C00001C00001C00001C00001C000FFFF00FFFF80FFFF00>17 29 4 0 24]105 dc[<003800 7C007C007C003800000000000000000FFC1FFC0FFC001C001C001C001C001C001C001C001C001C 001C001C001C001C001C001C001C001C001C001C001C001C001C6038F078FFF07FE03F80>14 39 2 10 24]106 dc[<7FE000FFE0007FE00000E00000E00000E00000E00000E00000E00000E00000 E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000 E00000E0007FFFC0FFFFE07FFFC0>19 28 2 0 24]108 dc[<7CE0E000FFFBF8007FFFF8001F1F 1C001E1E1C001E1E1C001C1C1C001C1C1C001C1C1C001C1C1C001C1C1C001C1C1C001C1C1C001C 1C1C001C1C1C001C1C1C001C1C1C007F1F1F00FFBFBF807F1F1F00>25 20 -1 0 24]109 dc[< 7E3E00FEFF807FFFC00FC1C00F80E00F00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E0 0E00E00E00E00E00E00E00E07FC3FCFFE7FE7FC3FC>23 20 0 0 24]110 dc[<01F0000FFE001F FF003E0F803803807001C07001C0E000E0E000E0E000E0E000E0E000E0F001E07001C07803C03C 07803E0F801FFF000FFE0001F000>19 20 2 0 24]111 dc[<7E3E00FEFF807FFFC00FC1E00F80 E00F00700E00700E00380E00380E00380E00380E00380E00380F00700F00700F80E00FC1E00FFF C00EFF800E3E000E00000E00000E00000E00000E00000E00000E00007FC000FFE0007FC000>21 30 0 10 24]112 dc[<01E38007FB801FFF803E1F80380F80700780700780E00380E00380E003 80E00380E00380E00380700780700780380F803C1F801FFF800FFB8003E3800003800003800003 80000380000380000380000380003FF8003FF8003FF8>21 30 2 10 24]113 dc[<7F87E0FF9F F07FBFF803F87803F03003E00003C00003C0000380000380000380000380000380000380000380 000380000380007FFE00FFFF007FFE00>21 20 1 0 24]114 dc[<07F7003FFF007FFF00780F00 E00700E00700E007007C00007FE0001FFC0003FE00001F00600780E00380E00380F00380F80F00 FFFF00FFFC00E7F000>17 20 3 0 24]115 dc[<0180000380000380000380000380007FFFC0FF FFC0FFFFC00380000380000380000380000380000380000380000380000380000380400380E003 80E00380E001C1C001FFC000FF80003E00>19 25 1 0 24]116 dc[<7E07E0FE0FE07E07E00E00 E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E01E00F03 E007FFFC03FFFE01FCFC>23 20 0 0 24]117 dc[<7F8FF0FF8FF87F8FF01E03C00E03800E0380 0E0380070700070700070700038E00038E00038E00038E0001DC0001DC0001DC0000F80000F800 007000>21 20 1 0 24]118 dc[21 20 1 0 24]119 dc[<7F8FF07F9FF07F8FF0070700078E00039E0001DC0001F80000F80000700000F0 0000F80001DC00039E00038E000707000F07807F8FF0FF8FF87F8FF0>21 20 1 0 24]120 dc[< 7F8FF0FF8FF87F8FF00E01C00E03800E0380070380070700070700038700038600038E0001CE00 01CE0000CC0000CC0000DC0000780000780000780000700000700000700000F00000E00079E000 7BC0007F80003F00001E0000>21 30 1 10 24]121 dc[<0007E0001FE0007FE000780000E000 00E00000E00000E00000E00000E00000E00000E00000E00000E00000E00001E0007FC000FF8000 FF80007FC00001E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E000 00E000007800007FE0001FE00007E0>19 36 2 4 24]123 dc[<60F0F0F0F0F0F0F0F0F0F0F0F0 F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F060>4 36 10 4 24]124 dc[<7C0000FF00 00FFC00003C00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E0 0000F000007FC0003FE0003FE0007FC000F00000E00000E00000E00000E00000E00000E00000E0 0000E00000E00000E00000E00003C000FFC000FF00007C0000>19 36 2 4 24]125 dc dfe /fd df[<387CFEFEFE7C38>7 7 4 0 16]46 dc[<00180000780001F800FFF800FFF80001F80001F8 0001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F8 0001F80001F80001F80001F80001F80001F80001F80001F80001F80001F8007FFFE07FFFE0>19 32 4 0 28]49 dc[<03FC000FFF003C1FC07007E07C07F0FE03F0FE03F8FE03F8FE01F87C01F8 3803F80003F80003F00003F00007E00007C0000F80001F00003E0000380000700000E01801C018 0380180700180E00380FFFF01FFFF03FFFF07FFFF0FFFFF0FFFFF0>21 32 3 0 28]50 dc[<00 FE0007FFC00F07E01E03F03F03F03F81F83F81F83F81F81F03F81F03F00003F00003E00007C000 1F8001FE0001FF000007C00001F00001F80000FC0000FC3C00FE7E00FEFF00FEFF00FEFF00FEFF 00FC7E01FC7801F81E07F00FFFC001FE00>23 32 2 0 28]51 dc[<0000700000000070000000 00F800000000F800000000F800000001FC00000001FC00000003FE00000003FE00000003FE0000 0006FF000000067F0000000E7F8000000C3F8000000C3F800000183FC00000181FC00000381FE0 0000300FE00000300FE00000600FF000006007F00000E007F80000FFFFF80000FFFFF800018001 FC00018001FC00038001FE00030000FE00030000FE000600007F000600007F00FFE00FFFF8FFE0 0FFFF8>37 34 2 0 42]65 dc[34 34 2 0 40]66 dc[< 0003FE0080001FFF818000FF01E38001F8003F8003E0001F8007C0000F800F800007801F800007 803F000003803F000003807F000001807E000001807E00000180FE00000000FE00000000FE0000 0000FE00000000FE00000000FE00000000FE00000000FE000000007E000000007E000001807F00 0001803F000001803F000003801F800003000F8000030007C000060003F0000C0001F800380000 FF00F000001FFFC0000003FE0000>33 34 3 0 40]67 dc[30 34 2 0 35]70 dc[19 34 1 0 21]73 dc[<0007FC0000003FFF800000FC07E00003F001F80007E000FC000FC0 007E001F80003F001F80003F003F00001F803F00001F807F00001FC07E00000FC07E00000FC0FE 00000FE0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE00000FE0 FE00000FE07E00000FC07F00001FC07F00001FC03F00001F803F80003F801F80003F000FC0007E 0007E000FC0003F001F80000FC07E000003FFF80000007FC0000>35 34 3 0 42]79 dc[32 34 2 0 38]80 dc[39 34 2 0 42]82 dc[<01FC0407FF8C1F03FC3C007C7C003C78001C78001CF8000CF8 000CFC000CFC0000FF0000FFE0007FFF007FFFC03FFFF01FFFF80FFFFC03FFFE003FFE0003FF00 007F00003F00003FC0001FC0001FC0001FE0001EE0001EF0003CFC003CFF00F8C7FFE080FF80> 24 34 3 0 31]83 dc[<07FC001FFF803F07C03F03E03F01E03F01F01E01F00001F00001F0003F F003FDF01FC1F03F01F07E01F0FC01F0FC01F0FC01F0FC01F07E02F07E0CF81FF87F07E03F>24 22 2 0 27]97 dc[26 35 2 0 31] 98 dc[<00FF8007FFE00F83F01F03F03E03F07E03F07C01E07C0000FC0000FC0000FC0000FC00 00FC0000FC00007C00007E00007E00003E00301F00600FC0E007FF8000FE00>20 22 2 0 25] 99 dc[<0001FE000001FE0000003E0000003E0000003E0000003E0000003E0000003E0000003E 0000003E0000003E0000003E0000003E0001FC3E0007FFBE000F81FE001F007E003E003E007E00 3E007C003E00FC003E00FC003E00FC003E00FC003E00FC003E00FC003E00FC003E00FC003E007C 003E007C003E003E007E001E00FE000F83BE0007FF3FC001FC3FC0>26 35 2 0 31]100 dc[<00 FE0007FF800F87C01E01E03E01F07C00F07C00F8FC00F8FC00F8FFFFF8FFFFF8FC0000FC0000FC 00007C00007C00007E00003E00181F00300FC07003FFC000FF00>21 22 2 0 26]101 dc[<003F 8000FFC001E3E003C7E007C7E00F87E00F83C00F80000F80000F80000F80000F80000F8000FFFC 00FFFC000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80 000F80000F80000F80000F80000F80000F80007FF8007FF800>19 35 1 0 17]102 dc[26 35 2 0 31]104 dc[<1C003F007F007F00 7F003F001C000000000000000000000000000000FF00FF001F001F001F001F001F001F001F001F 001F001F001F001F001F001F001F001F001F001F00FFE0FFE0>11 36 2 0 16]105 dc[11 35 2 0 16]108 dc[< FF07F007F000FF1FFC1FFC001F303E303E001F403E403E001F801F801F001F801F801F001F001F 001F001F001F001F001F001F001F001F001F001F001F001F001F001F001F001F001F001F001F00 1F001F001F001F001F001F001F001F001F001F001F001F001F001F001F001F001F001F001F001F 001F00FFE0FFE0FFE0FFE0FFE0FFE0>43 22 2 0 48]109 dc[26 22 2 0 31]110 dc[<00FE0007FFC00F83E01E00F03E00F87C007C7C007C7C007CFC007EFC007EFC 007EFC007EFC007EFC007EFC007E7C007C7C007C3E00F81F01F00F83E007FFC000FE00>23 22 2 0 28]111 dc[19 22 2 0 23]114 dc[<0FF3003FFF00781F00600700E00300E00300F00300FC00007FE0007FF8003FFE00 0FFF0001FF00000F80C00780C00380E00380E00380F00700FC0E00EFFC00C7F000>17 22 2 0 22]115 dc[<0180000180000180000180000380000380000780000780000F80003F8000FFFF00 FFFF000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F8180 0F81800F81800F81800F81800F830007C30003FE0000F800>17 32 1 0 22]116 dc[37 22 1 0 40]119 dc dfe /fe df[26 2 4 -10 35]0 dc[<01800180018001800180C183F18F 399C0FF003C003C00FF0399CF18FC18301800180018001800180>16 20 3 -1 23]3 dc[<03C0 0FF01FF83FFC7FFE7FFEFFFFFFFFFFFFFFFFFFFFFFFF7FFE7FFE3FFC1FF80FF003C0>16 18 3 -2 23]15 dc dfe /ff df[<007E1F8001C170400703C060060380E00E0380400E0380000E0380 000E0380000E0380000E038000FFFFFFE00E0380E00E0380E00E0380E00E0380E00E0380E00E03 80E00E0380E00E0380E00E0380E00E0380E00E0380E00E0380E00E0380E00E0380E07F8FE3FC> 30 26 0 0 32]14 dc[<60C0F1E0F9F068D0081008100810102010202040C180>12 11 1 -15 19]34 dc[<60F0F07010101020204080>4 11 3 7 11]44 dc[10 2 0 -7 13]45 dc[<60F0F060>4 4 3 0 11]46 dc[<0004000C00180018001800300030003000600060006000 C000C000C00180018001800300030003000600060006000C000C000C0018001800180030003000 3000600060006000C000C000>14 37 2 9 19]47 dc[<078018603030303060186018E01CE01C E01CE01CE01CE01CE01CE01CE01CE01CE01CE01C601860187038303018600780>14 24 2 0 19] 48 dc[<0F80106020304038803CC01CE01C401C003C003800380070006000C001800100020004 040804100430083FF87FF8FFF8>14 24 2 0 19]50 dc[<0F8010E02070607870382038007800 700070006000C00F8000E000700038003C003CE03CE03CC03C4038407030E00F80>14 24 2 0 19]51 dc[<30183FF03FE03FC02000200020002000200027C03860203000380018001C001C401C E01CE01C80184038403030E00F80>14 24 2 0 19]53 dc[<40007FFE7FFC7FFC400880108010 802000400040008001800180010003000300030003000700070007000700070007000200>15 25 2 0 19]55 dc[<07801860303070306018E018E018E01CE01CE01C601C603C303C185C0F9C001C 00180018003870307060604021801F00>14 24 2 0 19]57 dc[<000C0000000C0000000C0000 001E0000001E0000003F000000270000002700000043800000438000004380000081C0000081C0 000081C0000100E0000100E00001FFE00002007000020070000600780004003800040038000800 1C0008001C001C001E00FF00FFC0>26 26 1 0 29]65 dc[<003F0201C0C603002E0E001E1C00 0E1C0006380006780002700002700002F00000F00000F00000F00000F00000F000007000027000 027800023800041C00041C00080E000803003001C0C0003F00>23 26 2 0 28]67 dc[24 26 2 0 29]68 dc[20 26 2 0 25]70 dc[24 26 2 0 29]72 dc[11 26 1 0 14]73 dc[<1FFC00E000E000E000E000E000E000E000E000E000E000E000 E000E000E000E000E000E000E000E040E0E0E0E0E041C061801E00>14 26 3 0 20]74 dc[30 26 2 0 35]77 dc[24 26 2 0 29]78 dc[<007F000001C1C000070070000E0038001C001C003C001E0038000E0078000F00 70000700F0000780F0000780F0000780F0000780F0000780F0000780F0000780F000078078000F 0078000F0038000E003C001E001C001C000E0038000700700001C1C000007F0000>25 26 2 0 30]79 dc[21 26 2 0 26]80 dc[25 26 2 0 28]82 dc[<0FC21836200E6006C006C002C002C002E00070007E003FE01F F807FC003E000E00070003800380038003C002C006E004D81887E0>16 26 2 0 21]83 dc[<7F FFFF00701C0700401C0100401C0100C01C0180801C0080801C0080801C0080001C0000001C0000 001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C00 00001C0000001C0000001C0000001C0000001C000003FFE000>25 26 1 0 28]84 dc[<183020 4040804080810081008100B160F9F078F03060>12 11 5 -15 19]92 dc[<3F8070C070E02070 0070007007F01C7030707070E070E071E071E0F171FB1E3C>16 16 2 0 19]97 dc[18 26 1 0 21]98 dc[<07F80C1C381C30087000E000E000E000E000E000E0007000300438080C1807E0> 14 16 1 0 17]99 dc[<007E00000E00000E00000E00000E00000E00000E00000E00000E00000E 0003CE000C3E00380E00300E00700E00E00E00E00E00E00E00E00E00E00E00E00E00600E00700E 00381E001C2E0007CFC0>18 26 1 0 21]100 dc[<07C01C3030187018600CE00CFFFCE000E000 E000E0006000300438080C1807E0>14 16 1 0 17]101 dc[<01F0031807380E100E000E000E00 0E000E000E00FFC00E000E000E000E000E000E000E000E000E000E000E000E000E000E007FE0> 13 26 0 0 12]102 dc[<0FCE187330307038703870387038303018602FC02000600070003FF0 3FFC1FFE600FC003C003C003C0036006381C07E0>16 24 1 8 19]103 dc[18 26 1 0 21] 104 dc[<18003C003C001800000000000000000000000000FC001C001C001C001C001C001C001C 001C001C001C001C001C001C001C00FF80>9 26 0 0 10]105 dc[<018003C003C00180000000 0000000000000000000FC001C001C001C001C001C001C001C001C001C001C001C001C001C001C0 01C001C001C001C041C0E180E3007E00>10 33 -2 7 12]106 dc[9 26 0 0 10]108 dc[ 29 16 1 0 32]109 dc[18 16 1 0 21]110 dc[<07E01C38300C700E 6006E007E007E007E007E007E0076006700E381C1C3807E0>16 16 1 0 19]111 dc[18 23 1 7 21]112 dc[12 16 1 0 15]114 dc[<1F2060E04020C020C020F0007F003FC01FE000F080708030C030C020F0408F80>12 16 1 0 15]115 dc[<0400040004000C000C001C003C00FFC01C001C001C001C001C001C001C001C001C 201C201C201C201C200E400380>11 23 1 0 15]116 dc[18 16 1 0 21]117 dc[17 16 1 0 20]118 dc[25 16 1 0 28]119 dc[17 23 1 7 20]121 dc[<7FF86070407040E041C041C00380 070007000E081C081C08381070107030FFF0>13 16 1 0 17]122 dc dfe /fg df[<1C3C3C3C 3C040408081020204080>6 14 3 9 14]44 dc[<7FF0FFE07FE0>12 3 3 -8 16]45 dc[<70F8 F8F0E0>5 5 5 0 14]46 dc[<00000040000000C0000001800000018000000300000003000000 06000000060000000C0000001800000018000000300000003000000060000000C0000000C00000 01800000018000000300000003000000060000000C0000000C0000001800000018000000300000 003000000060000000C0000000C0000001800000018000000300000003000000060000000C0000 000C0000001800000018000000300000003000000060000000C0000000C000000080000000>26 45 1 11 23]47 dc[<000200020006000E003C00DC031C001C0038003800380038007000700070 007000E000E000E000E001C001C001C001C003800380038003800780FFF8>15 30 5 0 23]49 dc[<001F000061800080E00100E00200700220700420700410700820F00820F00820F00840E008 81E00703C0000380000700000C0000180000600000800003000004000008004010004010008020 01807E030047FF0041FE0080FC00807800>20 31 4 1 23]50 dc[<00C06000FFC001FF8001FE 00010000010000020000020000020000020000040000047800058C000606000C07000807000007 80000780000780000780000F00700F00F00F00F00E00E01E00801C0080380080300040600061C0 001F0000>19 31 5 1 23]53 dc[<08E0100BF01017F0201FF0603E19C0380E80200080600100 400300800300000600000E00000C00001C00001C0000380000380000700000700000F00000F000 01E00001E00001E00003C00003C00003C00007C000078000078000030000>20 31 7 1 23]55 dc[<001F000061800080C00100600300600600600600600600600E00C00F00800F818007C30007 E40003F80001F80003FC00047E00183F00300F00200700600700C00300C00300C0030080060080 0600C00C00C008004030003060001F8000>19 31 5 1 23]56 dc[<001F0000718000C0C00180 C00380E00700E00F00E00F01E01E01E01E01E01E01E01E01C01C03C01C03C01C03C01C07C01C0F 800C0F8006378003C700000F00000E00000E00001C00601C00F03800F07000E0600080C0004380 003E0000>19 31 5 1 23]57 dc[<070F1F1F0E0000000000000000000070F8F8F0E0>8 20 5 0 14]58 dc[<00000200000006000000060000000E0000001E0000001E0000003F0000002F000000 4F0000004F0000008F0000010F0000010F0000020F0000020F0000040F00000C0F0000080F0000 100F0000100F0000200F80003FFF800040078000C0078000800780010007800100078002000780 02000780060007801E000F80FF807FF8>29 32 2 0 34]65 dc[<01FFFFC0001E00F0001E0078 001E0038001E003C003C003C003C003C003C003C003C003C0078007800780078007800F0007801 E000F0078000FFFE0000F00F8000F003C001E001C001E001E001E001E001E001E003C001E003C0 01E003C001E003C001C0078003C00780078007800F0007801E000F007800FFFFE000>30 31 3 0 32]66 dc[<0000FE0200078186001C004C0038003C0060003C00C0001C01C00018038000180700 00180F0000181E0000101E0000103C0000003C00000078000000780000007800000078000000F0 000000F0000000F0000000F0000000F00000807000008070000080700001003800010038000200 180004000C001800060020000381C00000FE0000>31 33 6 1 33]67 dc[<01FFFF80001E00E0 001E0070001E0038001E001C003C001C003C000E003C000E003C000E0078000E0078000E007800 0E0078000E00F0001E00F0001E00F0001E00F0001E01E0003C01E0003C01E0003C01E0007803C0 007003C0007003C000E003C001C0078001C00780038007800E0007801C000F007000FFFFC000> 31 31 3 0 34]68 dc[<01FFFFFE001E001C001E000C001E0004001E0004003C0004003C000400 3C0004003C00040078080800780800007808000078180000F0300000FFF00000F0300000F03000 01E0200001E0200001E0200001E0001003C0002003C0002003C0004003C0004007800080078001 8007800100078007000F001F00FFFFFE00>31 31 3 0 31]69 dc[<01FFF3FFE0001F003E0000 1E003C00001E003C00001E003C00003C007800003C007800003C007800003C007800007800F000 007800F000007800F000007800F00000F001E00000FFFFE00000F001E00000F001E00001E003C0 0001E003C00001E003C00001E003C00003C007800003C007800003C007800003C007800007800F 000007800F000007800F000007800F00000F801F0000FFF1FFE000>35 31 3 0 34]72 dc[<01 FFF0001F00001E00001E00001E00003C00003C00003C00003C0000780000780000780000780000 F00000F00000F00000F00001E00001E00001E00001E00003C00003C00003C00003C00007800007 80000780000780000F8000FFF800>20 31 3 0 18]73 dc[<001FFF0000F80000F00000F00000 F00001E00001E00001E00001E00003C00003C00003C00003C0000780000780000780000780000F 00000F00000F00000F00001E00001E00301E00781E00F83C00F83C00F0780080700040E00021C0 001F0000>24 32 3 1 24]74 dc[<01FFF800001F0000001E0000001E0000001E0000003C0000 003C0000003C0000003C00000078000000780000007800000078000000F0000000F0000000F000 0000F0000001E0000001E0000001E0000001E0008003C0010003C0010003C0030003C002000780 06000780060007800C0007801C000F007800FFFFF800>25 31 3 0 29]76 dc[<01FE00007FC0 001E0000FC00001E0000F80000170001780000170001780000270002F00000270004F000002700 04F00000270008F00000470009E00000470011E00000470021E00000470021E00000870043C000 00838043C00000838083C00000838083C000010381078000010382078000010382078000010384 0780000203840F00000203880F00000203900F00000203900F00000401E01E00000401E01E0000 0401C01E00000C01801E00001C01803E0000FF8103FFC000>42 31 3 0 41]77 dc[<01FF007F E0001F000F00001F0004000017800400001780040000278008000023C008000023C008000023C0 08000041E010000041E010000041F010000040F010000080F02000008078200000807820000080 78200001003C400001003C400001003C400001001E400002001E800002001E800002000F800002 000F800004000F0000040007000004000700000C000700001C00020000FF80020000>35 31 3 0 34]78 dc[<0001FC0000070700001C01C0003000E000E0006001C0007003800070078000380700 00380E0000381E0000381C0000383C0000383C00003878000078780000787800007878000078F0 0000F0F00000F0F00000E0F00001E0F00001C0F00003C0700003807000070078000F0038001E00 38003C001C0070000E00E0000783800001FC0000>29 33 6 1 35]79 dc[<01FFFF80001E00E0 001E0070001E0038001E003C003C003C003C003C003C003C003C003C0078007800780078007800 F0007800E000F003C000F00F0000FFFC0000F0000001E0000001E0000001E0000001E0000003C0 000003C0000003C0000003C00000078000000780000007800000078000000F800000FFF00000> 30 31 3 0 31]80 dc[<01FFFF00001E03C0001E00E0001E0070001E0078003C0078003C007800 3C0078003C0078007800F0007800F0007801E0007801C000F0070000F01E0000FFF00000F03800 01E01C0001E01E0001E00E0001E00F0003C01E0003C01E0003C01E0003C01E0007803C0007803C 0807803C0807803C100F801C10FFF00C20000007C0>29 32 3 1 33]82 dc[<0007E040001C18 C0003005800060038000C0038001C00180018001000380010003800100038001000380000003C0 000003C0000003F8000001FF800001FFE000007FF000001FF0000001F800000078000000780000 0038000000380020003800200038002000300060007000600060006000E0007000C000E8038000 C606000081F80000>26 33 3 1 26]83 dc[<0FFFFFF01E0780E0180780201007802020078020 200F0020600F0020400F0020400F0020801E0040001E0000001E0000001E0000003C0000003C00 00003C0000003C00000078000000780000007800000078000000F0000000F0000000F0000000F0 000001E0000001E0000001E0000001E0000003E00000FFFF0000>28 31 8 0 33]84 dc[<7FFC 1FF807C003C00780010007800100078001000F0002000F0002000F0002000F0002001E0004001E 0004001E0004001E0004003C0008003C0008003C0008003C000800780010007800100078001000 78001000F0002000F0002000F0002000F0004000F0004000700080007001000030020000380400 000C18000007E00000>29 32 9 1 34]85 dc[30 32 9 1 34] 86 dc[41 32 9 1 45]87 dc[<00FFF07FE0000F801F00000F001C00000F80100000078030000007 8020000007C040000003C080000003C100000003E200000001E400000001EC00000001F8000000 00F000000000F800000000F800000000F8000000017C000000023C000000063C000000043E0000 00081E000000101E000000201F000000400F000000800F000001800F8000010007800007000780 001F000FC000FFC07FF800>35 31 2 0 34]88 dc[<00F1800389C00707800E03801C03803C03 80380700780700780700780700F00E00F00E00F00E00F00E20F01C40F01C40703C40705C40308C 800F0700>19 20 4 0 23]97 dc[<07803F8007000700070007000E000E000E000E001C001C00 1CF01D0C3A0E3C0E380F380F700F700F700F700FE01EE01EE01EE01CE03CE038607060E031C01F 00>16 32 5 0 21]98 dc[<007E0001C1000300800E07801E07801C07003C0200780000780000 780000F00000F00000F00000F00000F0000070010070020030040018380007C000>17 20 4 0 21]99 dc[<0000780003F80000700000700000700000700000E00000E00000E00000E00001C000 01C000F1C00389C00707800E03801C03803C0380380700780700780700780700F00E00F00E00F0 0E00F00E20F01C40F01C40703C40705C40308C800F0700>21 32 4 0 23]100 dc[<007C01C207 010E011C013C013802780C7BF07C00F000F000F000F0007000700170023804183807C0>16 20 4 0 21]101 dc[<00007800019C00033C00033C000718000700000700000E00000E00000E00000E 00000E0001FFE0001C00001C00001C00001C000038000038000038000038000038000070000070 0000700000700000700000700000E00000E00000E00000E00000C00001C00001C0000180003180 007B0000F300006600003C0000>22 41 -2 9 14]102 dc[<003C6000E27001C1E00380E00700 E00F00E00E01C01E01C01E01C01E01C03C03803C03803C03803C03803C07003C07001C0F001C17 000C2E0003CE00000E00000E00001C00001C00301C00783800F0700060E0003F8000>20 29 2 9 21]103 dc[<01E0000FE00001C00001C00001C00001C000038000038000038000038000070000 070000071E000763000E81800F01C00E01C00E01C01C03801C03801C03801C0380380700380700 380700380E10700E20700C20701C20700C40E00CC0600700>20 32 3 0 23]104 dc[<00C001E0 01E001C000000000000000000000000000000E003300230043804300470087000E000E000E001C 001C001C003840388030807080310033001C00>11 31 4 0 14]105 dc[<01E0000FE00001C000 01C00001C00001C0000380000380000380000380000700000700000703C00704200E08E00E11E0 0E21E00E40C01C80001D00001E00001FC00038E000387000387000383840707080707080707080 703100E03100601E00>19 32 3 0 21]107 dc[<03C01FC0038003800380038007000700070007 000E000E000E000E001C001C001C001C0038003800380038007000700070007100E200E200E200 E20064003800>10 32 4 0 12]108 dc[<1C0F80F0002630C318004740640C004780680E004700 700E004700700E008E00E01C000E00E01C000E00E01C000E00E01C001C01C038001C01C038001C 01C038001C01C0708038038071003803806100380380E100380380620070070066003003003800 >33 20 4 0 37]109 dc[<1C0F802630C04740604780604700704700708E00E00E00E00E00E00E 00E01C01C01C01C01C01C01C03843803883803083807083803107003303001C0>22 20 4 0 26] 110 dc[<007C0001C3000301800E01C01E01C01C01E03C01E07801E07801E07801E0F003C0F003 C0F003C0F00780F00700700F00700E0030180018700007C000>19 20 4 0 23]111 dc[<01C1E0 02621804741C04781C04701E04701E08E01E00E01E00E01E00E01E01C03C01C03C01C03C01C038 0380780380700380E003C1C0072380071E000700000700000E00000E00000E00000E00001C0000 1C0000FFC000>23 29 0 9 23]112 dc[<1C1E002661004783804787804707804703008E00000E 00000E00000E00001C00001C00001C00001C0000380000380000380000380000700000300000> 17 20 4 0 19]114 dc[<00FC030206010C030C070C060C000F800FF007F803FC003E000E700E F00CF00CE008401020601F80>16 20 3 0 19]115 dc[<018001C0038003800380038007000700 FFF007000E000E000E000E001C001C001C001C003800380038003820704070407080708031001E 00>12 28 4 0 15]116 dc[<0E00C03300E02301C04381C04301C04701C08703800E03800E0380 0E03801C07001C07001C07001C07101C0E20180E20180E201C1E200C264007C380>20 20 4 0 24]117 dc[<0E03803307802307C04383C04301C04700C08700800E00800E00800E00801C0100 1C01001C01001C02001C02001C04001C04001C08000E300003C000>18 20 4 0 21]118 dc[<0E 00C1C03300E3C02301C3E04381C1E04301C0E04701C060870380400E0380400E0380400E038040 1C0700801C0700801C0700801C0701001C0701001C0602001C0F02000C0F04000E13080003E1F0 00>27 20 4 0 30]119 dc[<0383800CC4401068E01071E02071E02070C040E00000E00000E000 00E00001C00001C00001C00001C040638080F38080F38100E5810084C600787800>19 20 3 0 21]120 dc[<0E00C03300E02301C04381C04301C04701C08703800E03800E03800E03801C0700 1C07001C07001C07001C0E00180E00180E001C1E000C3C0007DC00001C00001C00003800F03800 F07000E06000C0C0004380003E0000>19 29 4 9 22]121 dc dfe /fh df[<001F83E000F06E 3001C078780380F8780300F0300700700007007000070070000700700007007000070070000700 7000FFFFFF80070070000700700007007000070070000700700007007000070070000700700007 007000070070000700700007007000070070000700700007007000070070000700700007007000 7FE3FF00>29 32 0 0 27]11 dc[<003F0000E0C001C0C00381E00701E00701E0070000070000 070000070000070000070000FFFFE00700E00700E00700E00700E00700E00700E00700E00700E0 0700E00700E00700E00700E00700E00700E00700E00700E00700E00700E07FC3FE>23 32 0 0 25]12 dc[<003FE000E0E001C1E00381E00700E00700E00700E00700E00700E00700E00700E007 00E0FFFFE00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E007 00E00700E00700E00700E00700E00700E00700E07FE7FE>23 32 0 0 25]13 dc[<001F81F800 00F04F040001C07C06000380F80F000300F00F000700F00F000700700000070070000007007000 00070070000007007000000700700000FFFFFFFF00070070070007007007000700700700070070 070007007007000700700700070070070007007007000700700700070070070007007007000700 7007000700700700070070070007007007000700700700070070070007007007007FE3FE3FF0> 36 32 0 0 38]14 dc[<7038F87CFC7EFC7E743A040204020402080408041008100820104020> 15 14 2 -18 23]34 dc[<0F0000301880003030600060703001C0602C06C06013F980E0100300 E0100300E0100600E0100C00E0100C00E01018006010300060203000702060003040C0001880C0 000F018000000300E0000303100006060800060604000C0C0400180C0400181C0200301C020060 1C0200601C0200C01C0201801C0201801C0203000C0406000C04060006040C0006081800031008 0000E0>31 37 3 3 38]37 dc[<00780000008400000184000003020000070200000702000007 02000007020000070400000704000007080000070800000310000003A00FFC03C003E0038001C0 01C0008001C0010003E0010004E0020008F00200187004003078080070380800701C1000F01E10 00F00E2000F0074000F003C0087003C0087801C010380670301C18386007E00F80>30 34 2 1 35]38 dc[<70F8FCFC74040404080810102040>6 14 4 -18 13]39 dc[<002000400080010002 0006000C000C00180018003000300030007000600060006000E000E000E000E000E000E000E000 E000E000E000E000E0006000600060007000300030003000180018000C000C0006000200010000 8000400020>11 46 3 12 18]40 dc[<800040002000100008000C000600060003000300018001 80018001C000C000C000C000E000E000E000E000E000E000E000E000E000E000E000E000C000C0 00C001C001800180018003000300060006000C0008001000200040008000>11 46 3 12 18]41 dc[<70F8FCFC74040404080810102040>6 14 4 9 13]44 dc[10 2 1 -9 15]45 dc[<70F8F8F870>5 5 4 0 13]46 dc[<000100030003000600060006000C000C000C00180018 001800300030003000600060006000C000C000C00180018001800300030003000600060006000C 000C000C00180018001800300030003000600060006000C000C000C000>16 45 3 11 23]47 dc [<03F0000E1C001C0E00180600380700700380700380700380700380F003C0F003C0F003C0F003 C0F003C0F003C0F003C0F003C0F003C0F003C0F003C0F003C0F003C07003807003807003807807 803807001806001C0E000E1C0003F000>18 31 2 1 23]48 dc[<018003800F80F38003800380 038003800380038003800380038003800380038003800380038003800380038003800380038003 800380038007C0FFFE>15 30 4 0 23]49 dc[<03F0000C1C00100E00200700400780800780F0 07C0F803C0F803C0F803C02007C00007C0000780000780000F00000E00001C0000380000700000 600000C0000180000300000600400C00401800401000803FFF807FFF80FFFF80>18 30 2 0 23] 50 dc[<03F0000C1C00100E00200F00780F80780780780780380F80000F80000F00000F00000E 00001C0000380003F000003C00000E00000F000007800007800007C02007C0F807C0F807C0F807 C0F00780400780400F00200E001C3C0003F000>18 31 2 1 23]51 dc[<000600000600000E00 000E00001E00002E00002E00004E00008E00008E00010E00020E00020E00040E00080E00080E00 100E00200E00200E00400E00C00E00FFFFF0000E00000E00000E00000E00000E00000E00000E00 00FFE0>20 30 1 0 23]52 dc[<1803001FFE001FFC001FF8001FE00010000010000010000010 000010000010000011F000161C00180E001007001007800003800003800003C00003C00003C070 03C0F003C0F003C0E00380400380400700200600100E000C380003E000>18 31 2 1 23]53 dc[ <007C000182000701000E03800C07801C0780380300380000780000700000700000F1F000F21C 00F40600F80700F80380F80380F003C0F003C0F003C0F003C0F003C07003C07003C07003803803 803807001807000C0E00061C0001F000>18 31 2 1 23]54 dc[<4000007FFFC07FFF807FFF80 40010080020080020080040000080000080000100000200000200000400000400000C00000C000 01C000018000038000038000038000038000078000078000078000078000078000078000078000 030000>18 31 3 1 23]55 dc[<03F0000C0C0010060030030020018060018060018060018070 01807803003E03003F06001FC8000FF00003F80007FC000C7E00103F00300F806003804001C0C0 01C0C000C0C000C0C000C0C000806001802001001002000C0C0003F000>18 31 2 1 23]56 dc[ <03F0000E18001C0C00380600380700700700700380F00380F00380F003C0F003C0F003C0F003 C0F003C07007C07007C03807C0180BC00E13C003E3C00003800003800003800007003007007806 00780E00700C002018001070000FC000>18 31 2 1 23]57 dc[<70F8F8F87000000000000000 00000070F8F8F870>5 20 4 0 13]58 dc[<70F8F8F8700000000000000000000070F0F8F87808 0808101010202040>5 29 4 9 13]59 dc[<7FFFFFE0FFFFFFF000000000000000000000000000 00000000000000000000000000000000000000FFFFFFF07FFFFFE0>28 12 3 -5 35]61 dc[<00 0100000003800000038000000380000007C0000007C0000007C0000009E0000009E0000009E000 0010F0000010F0000010F00000207800002078000020780000403C0000403C0000403C0000801E 0000801E0000FFFE0001000F0001000F0001000F00020007800200078002000780040003C00E00 03C01F0007E0FFC03FFE>31 32 1 0 34]65 dc[26 31 2 0 32]66 dc[< 000FC040007030C001C009C0038005C0070003C00E0001C01E0000C01C0000C03C0000C07C0000 407C00004078000040F8000000F8000000F8000000F8000000F8000000F8000000F8000000F800 0000F8000000780000007C0000407C0000403C0000401C0000401E0000800E0000800700010003 80020001C0040000703800000FC000>26 33 3 1 33]67 dc[29 31 2 0 35]68 dc[27 31 2 0 31]69 dc[25 31 2 0 30]70 dc[<000FE0200078186000E004E0038002E0070001E00F0000E01E0000601E0000603C0000603C 0000207C00002078000020F8000000F8000000F8000000F8000000F8000000F8000000F8000000 F8007FFCF80003E0780001E07C0001E03C0001E03C0001E01E0001E01E0001E00F0001E0070001 E0038002E000E0046000781820000FE000>30 33 3 1 36]71 dc[29 31 2 0 34]72 dc[14 31 1 0 16]73 dc[ <0FFFC0007C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C 00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00203C00F83C00F83C 00F83C00F0380040780040700030E0000F8000>18 32 2 1 23]74 dc[30 31 2 0 35]75 dc[23 31 2 0 28]76 dc[37 31 2 0 42]77 dc[29 31 2 0 34]78 dc[<001F800000F0F00001C0380007801E00 0F000F000E0007001E0007803C0003C03C0003C07C0003E0780001E0780001E0F80001F0F80001 F0F80001F0F80001F0F80001F0F80001F0F80001F0F80001F0F80001F0780001E07C0003E07C00 03E03C0003C03C0003C01E0007800E0007000F000F0007801E0001C0380000F0F000001F8000> 28 33 3 1 35]79 dc[25 31 2 0 31]80 dc[<001F800000F0F00001C038 0007801E000F000F000E0007001E0007803C0003C03C0003C07C0003E07C0003E0780001E0F800 01F0F80001F0F80001F0F80001F0F80001F0F80001F0F80001F0F80001F0F80001F0780001E078 0001E07C0003E03C0003C03C0F03C01E1087800E2047000F204F0007A03E0001E0380000F0F010 001FB01000003010000038300000387000003FF000001FE000001FE000000FC000000780>28 41 3 9 35]81 dc[30 32 2 1 33]82 dc[<07E0800C198010078030 0380600180600180E00180E00080E00080E00080F00000F000007800007F00003FF0001FFC000F FE0003FF00001F800007800003C00003C00001C08001C08001C08001C08001C0C00180C00380E0 0300F00600CE0C0081F800>18 33 3 1 25]83 dc[<7FFFFFE0780F01E0600F0060400F002040 0F0020C00F0030800F0010800F0010800F0010800F0010000F0000000F0000000F0000000F0000 000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F00 00000F0000000F0000000F0000000F0000000F0000001F800007FFFE00>28 31 2 0 33]84 dc[ 29 32 2 1 34]85 dc[31 32 1 1 34]86 dc[44 32 1 1 47]87 dc[<7FF83FF80FE00FC007C0070003C0020001E0040001F00C0000F0 080000781000007C1000003C2000003E4000001E4000000F8000000F8000000780000003C00000 07E0000005E0000009F0000018F8000010780000207C0000603C0000401E0000801F0001800F00 01000780020007C0070003C01F8007E0FFE01FFE>31 31 1 0 34]88 dc[ 32 31 1 0 34]89 dc[<7FFFF87C00F87000F06001E04001E0C003C0C003C0800780800F80800F 00001E00001E00003C00003C0000780000F80000F00001E00001E00003C00403C0040780040F80 040F000C1E000C1E00083C00183C0018780038F801F8FFFFF8>22 31 3 0 28]90 dc[7 45 4 11 13]91 dc[<080410082010201040204020804080408040B85CFC7EFC7E7C 3E381C>15 14 5 -18 23]92 dc[7 45 1 11 13]93 dc[<1FE00030300078 1800781C00300E00000E00000E00000E0000FE00078E001E0E00380E00780E00F00E10F00E10F0 0E10F01E10781E103867200F83C0>20 20 2 0 23]97 dc[<0E0000FE00000E00000E00000E00 000E00000E00000E00000E00000E00000E00000E00000E3E000EC3800F01C00F00E00E00E00E00 700E00700E00780E00780E00780E00780E00780E00780E00700E00700E00E00F00E00D01C00CC3 00083E00>21 32 1 0 25]98 dc[<03F80E0C1C1E381E380C70007000F000F000F000F000F000 F00070007000380138011C020E0C03F0>16 20 2 0 20]99 dc[<000380003F80000380000380 00038000038000038000038000038000038000038000038003E380061B801C0780380380380380 700380700380F00380F00380F00380F00380F00380F003807003807003803803803807801C0780 0E1B8003E3F8>21 32 2 0 25]100 dc[<03F0000E1C001C0E00380700380700700700700380F0 0380F00380FFFF80F00000F00000F000007000007000003800801800800C010007060001F800> 17 20 1 0 20]101 dc[<007C00C6018F038F07060700070007000700070007000700FFF00700 070007000700070007000700070007000700070007000700070007000700070007007FF0>16 32 0 0 14]102 dc[<0000E003E3300E3C301C1C30380E00780F00780F00780F00780F00780F0038 0E001C1C001E380033E0002000002000003000003000003FFE001FFF800FFFC03001E0600070C0 0030C00030C00030C000306000603000C01C038003FC00>20 31 1 10 23]103 dc[<0E0000FE 00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E3E000E43000E 81800F01C00F01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E 01C00E01C00E01C00E01C0FFE7FC>22 32 1 0 25]104 dc[<1C001E003E001E001C0000000000 00000000000000000E007E000E000E000E000E000E000E000E000E000E000E000E000E000E000E 000E000E000E00FFC0>10 31 0 0 12]105 dc[<00E001F001F001F000E0000000000000000000 000000007007F000F0007000700070007000700070007000700070007000700070007000700070 0070007000700070007000706070F060F0C061803F00>12 40 -2 9 14]106 dc[<0E0000FE00 000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E0FF00E03C00E03 000E02000E04000E08000E10000E30000E70000EF8000F38000E1C000E1E000E0E000E07000E07 800E03800E03C00E03E0FFCFF8>21 32 1 0 24]107 dc[<0E00FE000E000E000E000E000E000E 000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E00 0E000E000E000E00FFE0>11 32 0 0 12]108 dc[<0E1F01F000FE618618000E81C81C000F00F0 0E000F00F00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00 E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E00FF E7FE7FE0>35 20 1 0 38]109 dc[<0E3E00FE43000E81800F01C00F01C00E01C00E01C00E01C0 0E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0FFE7FC>22 20 1 0 25]110 dc[<01F800070E001C03803801C03801C07000E07000E0F000F0F000F0F000F0F0 00F0F000F0F000F07000E07000E03801C03801C01C0380070E0001F800>20 20 1 0 23]111 dc [<0E3E00FEC3800F01C00F00E00E00E00E00F00E00700E00780E00780E00780E00780E00780E00 780E00700E00F00E00E00F01E00F01C00EC3000E3E000E00000E00000E00000E00000E00000E00 000E00000E0000FFE000>21 29 1 9 25]112 dc[<03E0800619801C05803C0780380380780380 700380F00380F00380F00380F00380F00380F003807003807803803803803807801C0B800E1380 03E380000380000380000380000380000380000380000380000380003FF8>21 29 2 9 24]113 dc[<0E78FE8C0F1E0F1E0F0C0E000E000E000E000E000E000E000E000E000E000E000E000E000E 00FFE0>15 20 1 0 18]114 dc[<1F9030704030C010C010C010E00078007F803FE00FF0007080 3880188018C018C018E030D0608F80>13 20 2 0 18]115 dc[<020002000200060006000E000E 003E00FFF80E000E000E000E000E000E000E000E000E000E000E000E080E080E080E080E080610 031001E0>13 28 1 0 18]116 dc[<0E01C0FE1FC00E01C00E01C00E01C00E01C00E01C00E01C0 0E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E03C00603C0030DC001F1FC>22 20 1 0 25]117 dc[21 20 1 0 24]118 dc [30 20 1 0 33]119 dc[<7FC3FC0F01E00701C007018003810001C20000E40000EC0000 7800003800003C00007C00004E000087000107000303800201C00601E01E01E0FF07FE>23 20 0 0 24]120 dc[21 29 1 9 24]121 dc[<3FFF380E200E201C40384078 407000E001E001C00380078007010E011E011C0338027006700EFFFE>16 20 1 0 20]122 dc[< FFFFFC>22 1 0 -12 23]123 dc[44 1 0 -12 45]124 dc dfe /fi df[<03 CC063C0C3C181C3838303870387038E070E070E070E070E0E2C0E2C0E261E462643C38>15 18 5 0 21]97 dc[<01F007080C08181C3838300070007000E000E000E000E000E000E008E010602030 C01F00>14 18 5 0 19]99 dc[<01E007100C1018083810701070607F80E000E000E000E000E0 00E0086010602030C01F00>13 18 5 0 19]101 dc[<0003C0000670000C70001C60001C00001C 0000380000380000380000380000380003FF8000700000700000700000700000700000E00000E0 0000E00000E00000E00001C00001C00001C00001C00001C0000380000380000380000300000300 00070000C60000E60000CC0000780000>20 37 -1 8 13]102 dc[<0180038001000000000000 0000000000000000001C002600470047008E008E000E001C001C001C0038003800710071007100 720072003C00>9 28 4 0 13]105 dc[<1F800380038007000700070007000E000E000E000E00 1C001C001C001C0038003800380038007000700070007000E400E400E400E40068003800>9 29 4 0 11]108 dc[<3C3C002646004687004707008E07008E07000E07000E07001C0E001C0E001C 0E001C1C00381C40381C40383840383880701900300E00>18 18 4 0 23]110 dc[<01E007180C 0C180C380C300E700E700EE01CE01CE01CE018E038E030E06060C031801E00>15 18 5 0 21] 111 dc[<3C3C26C2468747078E068E000E000E001C001C001C001C003800380038003800700030 00>16 18 4 0 18]114 dc[<00C001C001C001C00380038003800380FFE00700070007000E000E 000E000E001C001C001C001C00384038403840388019000E00>11 26 3 0 14]116 dc[<1E0300 270700470700470700870E00870E000E0E000E0E001C1C001C1C001C1C001C1C00383880383880 1838801839001C5900078E00>17 18 4 0 22]117 dc[<1E06270E470E4706870287020E020E02 1C041C041C041C0818083808181018200C400780>15 18 4 0 19]118 dc dfe /fj df[<007E 0001C1800301800703C00E03C00E01800E00000E00000E00000E00000E0000FFFFC00E01C00E01 C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01 C00E01C07F87F8>21 29 0 0 23]12 dc[<60F0F8680808081010204080>5 12 4 -17 12]39 dc[<004000800100020006000C000C0018001800300030007000600060006000E000E000E000E0 00E000E000E000E000E000E000E000E000600060006000700030003000180018000C000C000600 0200010000800040>10 42 3 11 16]40 dc[<800040002000100018000C000C00060006000300 0300038001800180018001C001C001C001C001C001C001C001C001C001C001C001C00180018001 80038003000300060006000C000C0018001000200040008000>10 42 2 11 16]41 dc[<60F0F0 701010101020204080>4 12 4 8 12]44 dc[11 2 0 -8 14]45 dc[<60F0F060>4 4 4 0 12]46 dc[<03C00C301818300C300C700E60066006E007E007E007E007E007E007E007E0 07E007E007E007E007E00760066006700E300C300C18180C3007E0>16 29 2 1 21]48 dc[<07 C01830201C400C400EF00FF80FF807F8077007000F000E000E001C001C00380070006000C00180 030006010C01180110023FFE7FFEFFFE>16 28 2 0 21]50 dc[<07E01830201C201C781E780E 781E381E001C001C00180030006007E00030001C001C000E000F000F700FF80FF80FF80FF00E40 1C201C183007E0>16 29 2 1 21]51 dc[<300C3FF83FF03FC020002000200020002000200023 E024302818301C200E000E000F000F000F600FF00FF00FF00F800E401E401C2038187007C0>16 29 2 1 21]53 dc[<000600000006000000060000000F0000000F0000000F0000001780000017 8000001780000023C0000023C0000023C0000041E0000041E0000041E0000080F0000080F00001 80F8000100780001FFF80003007C0002003C0002003C0006003E0004001E0004001E000C001F00 1E001F00FF80FFF0>28 29 1 0 31]65 dc[24 28 2 0 29]66 dc[<001F80 8000E0618001801980070007800E0003801C0003801C0001803800018078000080780000807000 0080F0000000F0000000F0000000F0000000F0000000F0000000F0000000F00000007000008078 00008078000080380000801C0001001C0001000E000200070004000180080000E03000001FC000 >25 30 2 1 30]67 dc[24 28 2 0 28]69 dc[22 28 2 0 27]70 dc[12 28 1 0 15]73 dc[21 28 2 0 26]76 dc[33 28 2 0 38]77 dc[<003F800000E0E0000380380007001C000E000E001C0007003C000780380003807800 03C0780003C0700001C0F00001E0F00001E0F00001E0F00001E0F00001E0F00001E0F00001E0F0 0001E0700001C0780003C0780003C0380003803C0007801C0007000E000E0007001C0003803800 00E0E000003F8000>27 30 2 1 32]79 dc[<003F800000E0E0000380380007001C000E000E00 1C0007003C00078038000380780003C0780003C0700001C0F00001E0F00001E0F00001E0F00001 E0F00001E0F00001E0F00001E0F00001E0700001C0780003C0780003C0380003803C0E07801C11 07000E208E0007205C0003A0780000F0E020003FE0200000602000003060000038E000003FC000 003FC000001F8000000F00>27 37 2 8 32]81 dc[28 29 2 1 31]82 dc[<07E0801C198030 0580700380600180E00180E00080E00080E00080F00000F800007C00007FC0003FF8001FFE0007 FF0000FF80000F800007C00003C00001C08001C08001C08001C0C00180C00180E00300D00200CC 0C0083F800>18 30 2 1 23]83 dc[<7FFFFFC0700F01C0600F00C0400F0040400F0040C00F00 20800F0020800F0020800F0020000F0000000F0000000F0000000F0000000F0000000F0000000F 0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F000000 0F0000001F800003FFFC00>27 28 1 0 30]84 dc[26 29 2 1 31]85 dc[<1FC00030700078 3800781C00301C00001C00001C0001FC000F1C00381C00701C00601C00E01C40E01C40E01C4060 3C40304E801F8700>18 18 2 0 21]97 dc[19 29 1 0 23]98 dc[< 07E00C301878307870306000E000E000E000E000E000E00060007004300418080C3007C0>14 18 2 0 18]99 dc[<003F000007000007000007000007000007000007000007000007000007000007 0003E7000C1700180F00300700700700600700E00700E00700E00700E00700E00700E007006007 00700700300700180F000C370007C7E0>19 29 2 0 23]100 dc[<03E00C301818300C700E6006 E006FFFEE000E000E000E00060007002300218040C1803E0>15 18 1 0 18]101 dc[<00F8018C 071E061E0E0C0E000E000E000E000E000E00FFE00E000E000E000E000E000E000E000E000E000E 000E000E000E000E000E000E007FE0>15 29 0 0 13]102 dc[<00038003C4C00C38C01C388018 1800381C00381C00381C00381C001818001C38000C300013C0001000003000001800001FF8001F FF001FFF803003806001C0C000C0C000C0C000C06001803003001C0E0007F800>18 28 1 9 21] 103 dc[20 29 1 0 23]104 dc[<18003C003C00180000000000000000 00000000000000FC001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C00 1C00FF80>9 29 1 0 12]105 dc[19 29 1 0 22]107 dc[9 29 1 0 12]108 dc[ 33 18 1 0 36]109 dc[20 18 1 0 23]110 dc[<03F0 000E1C00180600300300700380600180E001C0E001C0E001C0E001C0E001C0E001C06001807003 803003001806000E1C0003F000>18 18 1 0 21]111 dc[19 26 1 8 23]112 dc[<03C1000C 3300180B00300F00700700700700E00700E00700E00700E00700E00700E0070060070070070030 0F00180F000C370007C700000700000700000700000700000700000700000700003FE0>19 26 2 8 22]113 dc[13 18 1 0 16]114 dc[<1F9030704030C010C010E010F8007F803FE00FF000F88038 8018C018C018E010D0608FC0>13 18 1 0 16]115 dc[<04000400040004000C000C001C003C00 FFE01C001C001C001C001C001C001C001C001C001C101C101C101C101C100C100E2003C0>12 26 1 0 16]116 dc[20 18 1 0 23]117 dc[19 18 1 0 22]118 dc[27 18 1 0 30]119 dc[<7F8FF00F03800F030007020003 840001C80001D80000F00000700000780000F800009C00010E00020E000607000403801E07C0FF 0FF8>21 18 0 0 22]120 dc[19 26 1 8 22]121 dc dfe /fk df[<000380000003800000 07C0000007C0000007C000000FE000000FE000001FF000001BF000001BF0000031F8000031F800 0061FC000060FC0000E0FE0000C07E0000C07E0001803F0001FFFF0003FFFF8003001F8003001F 8006000FC006000FC00E000FE00C0007E0FFC07FFEFFC07FFE>31 28 2 0 36]65 dc[<0FF800 1C1E003E0F803E07803E07C01C07C00007C0007FC007E7C01F07C03C07C07C07C0F807C0F807C0 F807C0780BC03E13F80FE1F8>21 18 1 0 23]97 dc[23 29 1 0 27] 98 dc[<03FC000E0E001C1F003C1F00781F00780E00F80000F80000F80000F80000F80000F800 007800007801803C01801C03000E0E0003F800>17 18 2 0 21]99 dc[17 18 1 0 20]114 dc[<1FD830786018E018E018F000FF807FE07FF01FF807FC 007CC01CC01CE01CE018F830CFC0>14 18 2 0 19]115 dc[<0300030003000300070007000F00 0F003FFCFFFC1F001F001F001F001F001F001F001F001F001F0C1F0C1F0C1F0C0F08079803F0> 14 26 1 0 19]116 dc dfe /fl df[<70F8FCFC7404040404080810102040>6 15 4 10 14] 44 dc[<01F000071C000C06001803003803803803807001C07001C07001C07001C0F001E0F001 E0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F001E07001 C07001C07001C07803C03803803803801C07000C0600071C0001F000>19 34 2 1 24]48 dc[< 008003800F80F38003800380038003800380038003800380038003800380038003800380038003 800380038003800380038003800380038003800380038007C0FFFE>15 33 4 0 24]49 dc[<03 F0000C1C001007002007804003C04003C08003E0F003E0F801E0F801E0F801E02003E00003E000 03C00003C0000780000700000E00001C0000180000300000600000C00001800001000002002004 00200800201800603000403FFFC07FFFC0FFFFC0>19 33 2 0 24]50 dc[<03F8000C1E001007 002007804007C07807C07803C07807C03807C0000780000780000700000F00000E0000380003F0 00001C00000F000007800007800003C00003C00003E02003E07003E0F803E0F803E0F003C04003 C0400780200780100F000C1C0003F000>19 34 2 1 24]51 dc[<1000801E07001FFF001FFE00 1FF80013E00010000010000010000010000010000010000010F800130E00140700180380100380 0001C00001C00001E00001E00001E00001E07001E0F001E0F001E0E001C08001C04003C0400380 2007001006000C1C0003F000>19 34 2 1 24]53 dc[<0001800000018000000180000003C000 0003C0000003C0000005E0000005E000000DF0000008F0000008F0000010F80000107800001078 0000203C0000203C0000203C0000401E0000401E0000401E0000800F0000800F0000FFFF000100 078001000780030007C0020003C0020003C0040003E0040001E0040001E00C0000F00C0000F03E 0001F8FF800FFF>32 35 2 0 37]65 dc[<0007E0100038183000E0063001C00170038000F007 0000F00E0000701E0000701C0000303C0000303C0000307C0000107800001078000010F8000000 F8000000F8000000F8000000F8000000F8000000F8000000F800000078000000780000107C0000 103C0000103C0000101C0000201E0000200E000040070000400380008001C0010000E002000038 1C000007E000>28 36 3 1 35]67 dc[27 34 2 0 32]70 dc[40 34 2 0 45]77 dc[27 34 2 0 33]80 dc[<03F0200C0C601802603001E07000E060 0060E00060E00060E00020E00020E00020F00000F000007800007F00003FF0001FFE000FFF0003 FF80003FC00007E00001E00000F00000F0000070800070800070800070800070C00060C00060E0 00C0F000C0C80180C6070081FC00>20 36 3 1 27]83 dc[32 35 2 1 37]85 dc[<0FE0001838003C0C003C0E0018070000070000 070000070000FF0007C7001E07003C0700780700700700F00708F00708F00708F00F087817083C 23900FC1E0>21 21 2 0 24]97 dc[<0E0000FE00001E00000E00000E00000E00000E00000E00 000E00000E00000E00000E00000E00000E00000E1F000E61C00E80600F00300E00380E003C0E00 1C0E001E0E001E0E001E0E001E0E001E0E001E0E001E0E001C0E003C0E00380F00700C80600C41 C0083F00>23 35 1 0 27]98 dc[<01FE000703000C07801C0780380300780000700000F00000 F00000F00000F00000F00000F00000F000007000007800403800401C00800C010007060001F800 >18 21 2 0 22]99 dc[<01FC000707000C03801C01C03801C07801E07000E0F000E0FFFFE0F0 0000F00000F00000F00000F000007000007800203800201C00400E008007030000FC00>19 21 1 0 22]101 dc[<003C00C6018F038F030F070007000700070007000700070007000700FFF80700 0700070007000700070007000700070007000700070007000700070007000700070007807FF8> 16 35 0 0 15]102 dc[<00007001F198071E180E0E181C07001C07003C07803C07803C07803C 07801C07001C07000E0E000F1C0019F0001000001000001800001800001FFE000FFFC00FFFE038 00F0600030400018C00018C00018C000186000306000303800E00E038003FE00>21 33 1 11 24 ]103 dc[<0E0000FE00001E00000E00000E00000E00000E00000E00000E00000E00000E00000E 00000E00000E00000E1F800E60C00E80E00F00700F00700E00700E00700E00700E00700E00700E 00700E00700E00700E00700E00700E00700E00700E00700E00700E0070FFE7FF>24 35 1 0 27] 104 dc[<1C001E003E001E001C00000000000000000000000000000000000E00FE001E000E000E 000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E00FFC0>10 34 1 0 14]105 dc[<0E00FE001E000E000E000E000E000E000E000E000E000E000E000E000E000E000E 000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E00FFE0>11 35 1 0 14]108 dc[<0E1FC07F00FE60E183801E807201C00F003C00E00F003C00E00E003800E0 0E003800E00E003800E00E003800E00E003800E00E003800E00E003800E00E003800E00E003800 E00E003800E00E003800E00E003800E00E003800E00E003800E00E003800E0FFE3FF8FFE>39 21 1 0 42]109 dc[<0E1F80FE60C01E80E00F00700F00700E00700E00700E00700E00700E00700E 00700E00700E00700E00700E00700E00700E00700E00700E00700E0070FFE7FF>24 21 1 0 27] 110 dc[<01FC000707000C01801800C03800E0700070700070F00078F00078F00078F00078F000 78F00078F000787000707800F03800E01C01C00E038007070001FC00>21 21 1 0 24]111 dc[< 0E1F00FE61C00E80600F00700E00380E003C0E001C0E001E0E001E0E001E0E001E0E001E0E001E 0E001E0E003C0E003C0E00380F00700E80E00E41C00E3F000E00000E00000E00000E00000E0000 0E00000E00000E00000E0000FFE000>23 31 1 10 27]112 dc[<0E3CFE461E8F0F0F0F060F00 0E000E000E000E000E000E000E000E000E000E000E000E000E000F00FFF0>16 21 1 0 19]114 dc[<0F8830786018C018C008C008E008F0007F803FE00FF001F8003C801C800C800CC00CC008E0 18D0308FC0>14 21 2 0 19]115 dc[<02000200020002000600060006000E001E003E00FFF80E 000E000E000E000E000E000E000E000E000E000E000E040E040E040E040E040E040708030801F0 >14 31 1 0 19]116 dc[<0E0070FE07F01E00F00E00700E00700E00700E00700E00700E00700E 00700E00700E00700E00700E00700E00700E00700E00F00E00F006017003827800FC7F>24 21 1 0 27]117 dc[23 21 1 0 26] 118 dc[23 31 1 10 26]121 dc dfe /fm df[<3078FC FC7830>6 6 10 0 26]46 dc[<003E0001FF8003FFC007C1E00F00E01E0F703C3FF0387FF07070 F870E07870E078E1C038E1C038E1C038E1C038E1C038E1C038E1C038E1C03870E07070E0707070 E0387FE03C3FC01E0F000F003807C0F803FFF001FFE0003F00>21 30 2 0 26]64 dc[<00FF80 03FFC00FFFE01F01E03C00C0780000700000700000E00000E00000E00000E00000E00000700000 7000007800703C00701F01F00FFFE003FFC000FE00>20 21 3 0 26]99 dc[<001FC0001FC000 1FC00001C00001C00001C00001C00001C00001C001F1C007FDC00FFFC01E0FC03C07C07803C070 01C0E001C0E001C0E001C0E001C0E001C0E001C0E001C07003C07003C03807C03E0FC01FFFFC07 FDFC01F1FC>22 30 2 0 26]100 dc[<01F80007FF000FFF801E07C03C01C07800E07000E0E000 70E00070FFFFF0FFFFF0FFFFF0E000007000007000007800703C00701F01F00FFFE003FFC000FE 00>20 21 3 0 26]101 dc[<7CE0E000FFFBF8007FFFF8001F1F1C001E1E1C001E1E1C001C1C1C 001C1C1C001C1C1C001C1C1C001C1C1C001C1C1C001C1C1C001C1C1C001C1C1C001C1C1C001C1C 1C001C1C1C007F1F1F00FF9F9F807F1F1F00>25 21 0 0 26]109 dc[22 32 1 11 26]112 dc[<7F83F0FF8FF87FBFFC03FC3C03F01803E00003 C00003C0000380000380000380000380000380000380000380000380000380000380007FFF00FF FF007FFF00>22 21 2 0 26]114 dc[<07FB801FFF807FFF80780780E00380E00380E003807800 007FC0003FFC0007FE00003F800007806001C0E001C0E001C0F003C0FC0780FFFF00EFFE00E3F8 00>18 21 4 0 26]115 dc[23 21 1 0 26]117 dc dfe /fn df[<70F8F8F0E0>5 5 6 0 15]46 dc[<00FFFFF000000F003C0000 0F000E00000F000700001E000380001E000380001E0001C0001E0001C0003C0001C0003C0001E0 003C0001E0003C0001E000780001E000780001E000780001E000780001E000F00003C000F00003 C000F00003C000F00003C001E000078001E000078001E000070001E0000F0003C0000E0003C000 1C0003C0003C0003C00038000780007000078000E000078001C00007800700000F801C0000FFFF F00000>35 34 3 0 37]68 dc[<00FFFFE0000F0038000F001E000F000E001E0007001E000700 1E0007001E0007003C000F003C000F003C000F003C001E0078001E0078003C00780078007800E0 00F003C000FFFE0000F0000000F0000001E0000001E0000001E0000001E0000003C0000003C000 0003C0000003C00000078000000780000007800000078000000F800000FFF80000>32 34 3 0 33]80 dc[<00FFFFC0000F0070000F003C000F001C001E000E001E000E001E000F001E000F003C 001E003C001E003C001E003C003C0078003800780070007801E00078078000FFFC0000F00E0000 F0070000F0038001E003C001E003C001E003C001E003C003C0078003C0078003C0078003C00780 07800F0007800F0107800F01078007020F800702FFF8038C000000F0>32 35 3 1 36]82 dc[< 00F8C00185C00705C00E03800E03801C03803C0380380700780700780700780700F00E00F00E00 F00E00F00E10F01C20701C20703C20305C40308C400F0780>20 21 5 0 25]97 dc[<007E0001 C1000301800703800E07801C07803C0000380000780000780000780000F00000F00000F00000F0 0000F00100700100700200300C001830000FC000>17 21 5 0 22]99 dc[<00003C0003F80000 380000380000380000700000700000700000700000E00000E00000E00000E00001C000F9C00185 C00705C00E03800E03801C03803C0380380700780700780700780700F00E00F00E00F00E00F00E 10F01C20701C20703C20305C40308C400F0780>22 35 5 0 25]100 dc[<00F803840E021C023C 0238027804F018FFE0F000F000E000E000E000E000E002E0026004701830600F80>15 21 6 0 22]101 dc[<00F0000FE00000E00000E00000E00001C00001C00001C00001C000038000038000 038000038000070000071F0007218007C0C00F00E00F00E00E00E00E00E01C01C01C01C01C01C0 1C01C0380380380380380380380704700708700E08700E10700610E006206003C0>22 35 3 0 25]104 dc[<00C001E001C001C0000000000000000000000000000000001C0023004300430087 00870087000E000E001C001C001C00380038003840708070807080710032001C00>11 33 5 0 15]105 dc[<1C1F002620804741C08783C08703C08701808700000E00000E00000E00000E0000 1C00001C00001C00001C0000380000380000380000380000700000300000>18 21 5 0 21]114 dc[<00FC000183000200800401800C03800C03000C00000F00000FF00007FC0003FE00003E0000 0F00000700700700F00600F00600E004004008002030001FC000>17 21 3 0 20]115 dc[<1E03 802307C04387C04383C08381C08700C08700C00700800E00800E00800E00801C01001C01001C01 001C02001C02001C04001C08001C08000C300003C000>18 21 5 0 22]118 dc dfe /fo df[< FFFF80FFFF80FFFF80FFFF80FFFF80FFFF80>17 6 1 -11 23]45 dc[<000E00001E00007E0007 FE00FFFE00FFFE00F8FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000 FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000 FE0000FE0000FE0000FE0000FE0000FE0000FE007FFFFE7FFFFE7FFFFE>23 39 5 0 34]49 dc[ <00FF800003FFF0000FFFFC001F03FE003800FF007C007F80FE003FC0FF003FC0FF003FE0FF00 1FE0FF001FE07E001FE03C003FE000003FE000003FC000003FC000007F8000007F000000FE0000 00FC000001F8000003F0000003E00000078000000F0000001E0000003C00E0007000E000E000E0 01C001C0038001C0070001C00FFFFFC01FFFFFC03FFFFFC07FFFFFC0FFFFFF80FFFFFF80FFFFFF 80>27 39 3 0 34]50 dc[<007F800003FFF00007FFFC000F81FE001F00FF003F80FF003F807F 803F807F803F807F801F807F800F007F800000FF000000FF000000FE000001FC000001F8000007 F00000FFC00000FFF0000001FC0000007E0000007F0000007F8000003FC000003FC000003FE000 003FE03C003FE07E003FE0FF003FE0FF003FE0FF003FC0FF007FC07E007F807C007F003F01FE00 1FFFFC0007FFF00000FF8000>27 39 3 0 34]51 dc[<00000E0000001E0000003E0000007E00 0000FE000000FE000001FE000003FE0000077E00000E7E00000E7E00001C7E0000387E0000707E 0000E07E0000E07E0001C07E0003807E0007007E000E007E000E007E001C007E0038007E007000 7E00E0007E00FFFFFFF8FFFFFFF8FFFFFFF80000FE000000FE000000FE000000FE000000FE0000 00FE000000FE000000FE00007FFFF8007FFFF8007FFFF8>29 39 2 0 34]52 dc[<0C0003000F 803F000FFFFE000FFFFC000FFFF8000FFFF0000FFFE0000FFFC0000FFE00000E0000000E000000 0E0000000E0000000E0000000E0000000E7FC0000FFFF8000F80FC000E003E000C003F0000001F 8000001FC000001FC000001FE000001FE018001FE07C001FE0FE001FE0FE001FE0FE001FE0FE00 1FC0FC001FC078003F8078003F803C007F001F01FE000FFFF80003FFF00000FF8000>27 39 3 0 34]53 dc[<0007F000003FFC0000FFFE0001FC0F0003F01F8007E03F800FC03F801FC03F801F80 3F803F801F003F8000007F0000007F0000007F000000FF000000FF0FC000FF3FF800FF707C00FF C03E00FFC03F00FF801F80FF801FC0FF001FC0FF001FE0FF001FE0FF001FE07F001FE07F001FE0 7F001FE07F001FE03F001FE03F001FC01F801FC01F803F800FC03F0007E07E0003FFFC0000FFF0 00003FC000>27 39 3 0 34]54 dc[<380000003E0000003FFFFFF03FFFFFF03FFFFFF07FFFFF E07FFFFFC07FFFFF807FFFFF0070000E0070000E0070001C00E0003800E0007000E000E0000000 E0000001C000000380000007800000078000000F0000000F0000001F0000001F0000003F000000 3E0000003E0000007E0000007E0000007E0000007E000000FE000000FE000000FE000000FE0000 00FE000000FE000000FE000000FE0000007C000000380000>28 41 4 0 34]55 dc[<00000380 0000000007C00000000007C0000000000FE0000000000FE0000000000FE0000000001FF0000000 001FF0000000003FF8000000003FF8000000003FF80000000073FC0000000073FC00000000F3FE 00000000E1FE00000000E1FE00000001C0FF00000001C0FF00000003C0FF80000003807F800000 07807FC0000007003FC0000007003FC000000E003FE000000E001FE000001E001FF000001C000F F000001FFFFFF000003FFFFFF800003FFFFFF80000780007FC0000700003FC0000700003FC0000 E00001FE0000E00001FE0001E00001FF0001C00000FF0001C00000FF00FFFE001FFFFEFFFE001F FFFEFFFE001FFFFE>47 41 2 0 52]65 dc[41 41 3 0 49] 66 dc[<00003FF001800003FFFE0380000FFFFF8780003FF007DF8000FF8001FF8001FE00007F 8003FC00003F8007F000001F800FF000000F801FE0000007801FE0000007803FC0000007803FC0 000003807FC0000003807F80000003807F8000000000FF8000000000FF8000000000FF80000000 00FF8000000000FF8000000000FF8000000000FF8000000000FF8000000000FF80000000007F80 000000007F80000000007FC0000003803FC0000003803FC0000003801FE0000003801FE0000007 000FF00000070007F000000E0003FC00001E0001FE00003C0000FF8000F800003FF007E000000F FFFFC0000003FFFF000000003FF80000>41 41 4 0 50]67 dc[39 41 3 0 45]69 dc[22 41 2 0 26]73 dc[34 41 3 0 41]76 dc[58 41 3 0 65]77 dc[39 41 3 0 47]80 dc[48 41 3 0 52]82 dc[< 7FFFFFFFFFC07FFFFFFFFFC07FFFFFFFFFC07F803FC03FC07E003FC007C078003FC003C078003F C003C070003FC001C0F0003FC001E0F0003FC001E0E0003FC000E0E0003FC000E0E0003FC000E0 E0003FC000E0E0003FC000E000003FC0000000003FC0000000003FC0000000003FC0000000003F C0000000003FC0000000003FC0000000003FC0000000003FC0000000003FC0000000003FC00000 00003FC0000000003FC0000000003FC0000000003FC0000000003FC0000000003FC0000000003F C0000000003FC0000000003FC0000000003FC0000000003FC00000007FFFFFE000007FFFFFE000 007FFFFFE000>43 40 2 0 48]84 dc[68 41 1 0 71]87 dc[<01FF800007FFF0000F81F8001FC07E001FC07E001FC03F000F803F8007003F8000 003F8000003F8000003F80000FFF8000FFFF8007FC3F800FE03F803F803F803F003F807F003F80 FE003F80FE003F80FE003F80FE003F807E007F807F00DF803F839FFC0FFF0FFC01FC03FC>30 27 2 0 33]97 dc[<001FF80000FFFE0003F01F0007E03F800FC03F801F803F803F801F007F800E00 7F0000007F000000FF000000FF000000FF000000FF000000FF000000FF000000FF0000007F0000 007F0000007F8000003F8001C01F8001C00FC0038007E0070003F01E0000FFFC00001FE000>26 27 2 0 31]99 dc[<00003FF80000003FF80000003FF800000003F800000003F800000003F800 000003F800000003F800000003F800000003F800000003F800000003F800000003F800000003F8 00000003F800001FE3F80000FFFBF80003F03FF80007E00FF8000FC007F8001F8003F8003F8003 F8007F0003F8007F0003F8007F0003F800FF0003F800FF0003F800FF0003F800FF0003F800FF00 03F800FF0003F800FF0003F8007F0003F8007F0003F8007F0003F8003F8003F8001F8003F8000F 8007F80007C00FF80003F03BFF8000FFF3FF80003FC3FF80>33 42 2 0 38]100 dc[<003FE000 01FFF80003F07E0007C01F000F801F801F800F803F800FC07F000FC07F0007C07F0007E0FF0007 E0FF0007E0FFFFFFE0FFFFFFE0FF000000FF000000FF0000007F0000007F0000007F0000003F80 00E01F8000E00FC001C007E0038003F81F0000FFFE00001FF000>27 27 2 0 32]101 dc[<0007 F0003FFC00FE3E01F87F03F87F03F07F07F07F07F03E07F00007F00007F00007F00007F00007F0 0007F000FFFFC0FFFFC0FFFFC007F00007F00007F00007F00007F00007F00007F00007F00007F0 0007F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F0007FFF 807FFF807FFF80>24 42 2 0 21]102 dc[<00FF81F003FFE7F80FC1FE7C1F80FC7C1F007C383F 007E107F007F007F007F007F007F007F007F007F007F007F007F003F007E001F007C001F80FC00 0FC1F8001FFFE00018FF800038000000380000003C0000003E0000003FFFF8001FFFFF001FFFFF 800FFFFFC007FFFFE01FFFFFF03E0007F07C0001F8F80000F8F80000F8F80000F8F80000F87C00 01F03C0001E01F0007C00FC01F8003FFFE00007FF000>30 40 2 13 34]103 dc[33 42 3 0 38]104 dc[<07000FC01FE03FE03FE03FE01FE00FC00700 0000000000000000000000000000FFE0FFE0FFE00FE00FE00FE00FE00FE00FE00FE00FE00FE00F E00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE0FFFEFFFEFFFE>15 43 3 0 20]105 dc [31 42 2 0 36]107 dc[15 42 3 0 20]108 dc[53 27 3 0 58]109 dc[33 27 3 0 38]110 dc[<003FE0 0001FFFC0003F07E000FC01F801F800FC03F800FE03F0007E07F0007F07F0007F07F0007F0FF00 07F8FF0007F8FF0007F8FF0007F8FF0007F8FF0007F8FF0007F8FF0007F87F0007F07F0007F03F 800FE03F800FE01F800FC00FC01F8007F07F0001FFFC00003FE000>29 27 2 0 34]111 dc[ 33 39 2 12 38]112 dc[24 27 2 0 28]114 dc[<03FE300FFFF01E03F03800F07000 70F00070F00070F80070FC0000FFE0007FFE007FFF803FFFE01FFFF007FFF800FFF80003FC0000 FC60007CE0003CF0003CF00038F80038FC0070FF01E0F7FFC0C1FF00>22 27 2 0 27]115 dc[< 00700000700000700000700000F00000F00000F00001F00003F00003F00007F0001FFFF0FFFFF0 FFFFF007F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F000 07F00007F03807F03807F03807F03807F03807F03803F03803F87001F86000FFC0001F80>21 38 1 0 27]116 dc[33 27 3 0 38]117 dc[47 27 1 0 50]119 dc[33 27 1 0 36]120 dc[33 39 1 12 36]121 dc dfe end TeXDict begin @letter %%EndProlog %%Page: 1 1 bop 631 42 a fo(P)n(age)23 b(Replacemen)n(t)d(and)468 98 y(Reference)g(Bit)i (Em)n(ulation)g(in)g(Mac)n(h)779 215 y fn(R)n(ichar)n(d)17 b(P.)g(Dr)m(aves) 796 316 y fm(rpd@cs.cm)o(u.e)o(du)678 374 y fl(Sc)n(ho)r(ol)f(of)h(Computer)e (Science)684 432 y(Carnegie)h(Mellon)f(Univ)n(ersit)n(y)522 488 y(5000)j(F)-5 b(orb)r(es)16 b(Av)n(en)o(ue)g(Pittsburgh,)g(P)l(A)g(15213)884 630 y fk(Abstr\ act)251 702 y fj(A)e(page-replacemen)o(t)g(algorithm)e(guides)i(the)h(op)q (erating)f(system)g(when)h(it)e(needs)j(to)e(create)189 751 y(more)d(free)i (pages)g(b)o(y)f(reclaiming)e(pages)j(that)f(are)h(\014lled)f(with)g(data.)17 b(The)c(Mac)o(h)f(k)o(ernel)h(appro)o(x-)189 801 y(imates)f(the)j(famili)o (ar)c(Least)j(Recently)f(Used)i(\(LR)o(U\))f(algorithm)d(with)i(an)h(algorith\ m)d(kno)n(wn)j(as)189 851 y(FIF)o(O)f(with)f(Second)i(Chance.)k(This)13 b(str\ ategy)g(uses)h(page-referenced)h(information)10 b(to)i(a)o(v)o(oid)g(re-)189 901 y(claiming)e(recently-referenced)15 b(pages.)j(On)13 b(hardw)o(are)g(lac) o(king)f(suc)o(h)h(supp)r(ort,)g(the)g(k)o(ernel)g(m)n(ust)189 951 y(detect)i (references)i(in)c(soft)o(w)o(are.)251 1000 y(This)j(pap)q(er)i(describ)r(es) f(the)h(Mac)o(h)e(k)o(ernel's)h(page-replacemen)o(t)g(algorithm)d(and)i(consi\ ders)189 1050 y(three)h(soft)o(w)o(are)f(techniques)g(for)g(detecting)h(refer\ ences.)27 b(It)17 b(sho)o(ws)f(that)g(Mac)o(h)g(3.0's)f fi(r)n(efer)m(enc)n (e)189 1100 y(fault)i fj(tec)o(hnique)h(outp)q(erforms)f(Mac)o(h)g(2.5's)f fi (r)n(e)n(activation)i(fault)f fj(technique,)h(and)f(also)g(outp)q(er-)189 1150 y(forms)c(reference)j(detection)g(via)d(a)h(soft)o(w)o(are)g(TLB)h(miss)e(han\ dler.)19 b(Based)d(on)e(the)g(p)r(erformance)189 1200 y(of)g(the)i(Mach)f(3.0) f(implemen)l(tation,)h(w)o(e)h(conclude)g(that)f(hardw)o(are)h(page-reference\ d)i(informa-)189 1249 y(tion)13 b(is)h(not)g(a)f(prerequisite)i(for)f(a)g(sat\ isfactory)g(page-replacemen)n(t)g(algorithm.)75 1392 y fo(1)69 b(In)n(tro)s (duction)75 1494 y fh(The)17 b(Mac)n(h)h(k)n(ernel)g(uses)f(a)g(simple)h(glob\ al)g(page-replacement)f(algorithm,)g(called)h(FIF)o(O)f(with)g(Sec-)75 1550 y (ond)d(Chance,)h(that)e(requires)i(page-referenced)g(information)f(to)f(appro) o(ximate)h(LRU)g(b)q(eha)o(vior.)20 b(The)75 1606 y(Mac)n(h)j(2.5)e(implemen) q(tation)h(p)q(erformed)g(unsatisfactorily)h(on)g(arc)n(hitectures)g(without) g(hardw)n(are)75 1663 y(page-referenced)14 b(supp)r(ort.)19 b(The)13 b(Mac)o (h)g(3.0)g(k)n(ernel)i(uses)e(mac)o(hine-indep)t(endent)g(reference)h(bits)g (and)75 1719 y fg(r)n(efer)m(enc)m(e)k(faults)f fh(to)f(em)n(ulate)i(page-ref\ erenced)f(supp)r(ort.)24 b(This)17 b(implemen)q(tation)f(pro)o(vides)h(an)g (ad-)75 1776 y(equate)k(LR)o(U)g(appro)n(ximation)g(with)g(lo)o(w)g(o)n(v)o (erhead,)h(leading)g(to)e(the)g(conclusion)j(that)d(hardw)n(are)75 1832 y(pag\ e-referenced)d(information)f(is)h(not)e(a)h(requirement)f(for)h(a)f(satisfact\ ory)g(page-replacement)h(algo-)75 1889 y(rithm.)146 1945 y(P)n(age)e(replacem\ ent)g(is)h(a)f(v)o(ery)h(old)g(problem)g([Belady)g(66,)e(Denning)j(68])d(that) h(has)g(received)h(little)75 2002 y(atten)n(tion)d(in)h(recen)o(t)f(y)n(ears.) 19 b(This)12 b(is)g(for)f(go)q(o)q(d)h(reason.)18 b(The)12 b(c)o(hoice)h(of)e (page-replacemen)q(t)g(algorithm)75 2058 y(largely)16 b(do)q(esn't)f(matter,) e(b)r(ecause)i(memory)g(is)g(c)o(heap)g(and)h(most)e(mac)n(hines)j(ha)n(v)o (e)e(enough)h(memory)75 2115 y(that)e(paging)h(is)h(not)e(a)h(concern.)20 b (If)15 b(a)g(mac)n(hine)i(clearly)f(do)q(esn't)e(ha)o(v)o(e)h(enough)g(memory) g(to)f(supp)r(ort)75 2171 y(its)20 b(w)o(ork-load,)h(then)g(no)f(page-replace\ ment)g(algorithm)g(can)h(rescue)g(p)q(erformance.)35 b(Ho)o(w)n(ev)o(er,)21 b (a)75 2228 y(page-replacement)15 b(algorithm)g(should)h(still)h(meet)e(sev)o (eral)g(criteria:)75 2266 y 720 2 v 144 2309 a ff(This)h(researc)o(h)f(w)o (as)g(supp)r(orted)g(in)h(part)f(b)o(y)g(a)g(fellowship)h(from)e(the)h(F)m (annie)h(and)g(John)f(Hertz)f(F)m(oundation)j(and)75 2354 y(in)g(part)g(by)f (the)h(Defense)g(Adv)o(anced)g(Research)f(Pro)s(jects)g(Agency)n(,)h(Informat\ ion)h(Science)g(and)f(T)m(ec)o(hnology)h(O\016ce,)75 2400 y(under)c(the)g(tit\ le)g(\\Research)g(on)f(P)o(arallel)j(Computing",)f(ARP)m(A)e(Order)g(No.)18 b (7330,)13 b(issued)i(b)o(y)f(D)o(ARP)m(A/CMO)f(under)75 2446 y(Con)o(tract)g (MDS972-90-C-0035.)964 2825 y fh(1)p eop %%Page: 2 2 bop 143 42 a fe(\017)23 b fg(L)m(ow)16 b(Overhe)n(ad)f fh(|)g(Because)g(in)g (man)o(y)g(en)o(vironmen)o(ts)f(v)o(ery)h(little)h(page-replacement)e(o)q(ccu\ rs,)189 98 y(the)h(algorithm)g(should)h(not)f(imp)r(ose)g(a)g(noticeable)i (o)n(v)o(erhead)e(when)h(it)g(is)f(not)g(needed.)143 192 y fe(\017)23 b fg (No)18 b(T)l(uning)f fh(|)h(An)f(algorithm)h(that)f(requires)h(a)f(h)o(uman)h (other)f(than)g(the)g(original)i(designer)189 248 y(to)i(set)g(parameters)g (will)j(p)q(erform)e(p)q(o)q(orly)g(in)h(the)f(real)g(w)n(orld.)41 b(Mac)n (hine-dep)s(endent)22 b(and)189 305 y(user-dep)r(endent)15 b(tuning)h(is)f (undesirable.)143 399 y fe(\017)23 b fg(LR)n(U)d(Appr)n(oximation)g fh(|)g (When)g(it)g(is)g(needed,)h(the)f(page-replacement)f(algorithm)h(should)189 455 y(a)n(v)o(oid)h(pathological)g(b)q(eha)o(vior.)35 b(In)21 b(a)f(slightly) g(memory-p)r(o)q(or)f(environmen)o(t,)i(an)f(LRU)g(ap-)189 511 y(pro)n(ximati\ on)c(that)e(k)o(eeps)i(the)f(system's)f(w)o(orking)h(set)g(resident)g(will)i (mak)n(e)f(a)e(di\013erence.)75 605 y(F)l(or)i(example,)h(as)g(describ)r(ed)g (later)g(in)g(Section)h(2.3,)d(tuning)j(Mac)n(h's)f(page-replacement)f(algori\ thm)75 662 y(to)d(pro)q(duce)i(a)f(b)q(etter)g(LR)o(U)g(appro)o(ximation)g (impro)o(v)o(ed)g(the)g(p)r(erformance)f(of)h(a)f(simple)j(compilation)75 718 y(test)f(b)o(y)g(a)g(factor)f(of)h(four.)146 775 y(This)c(pap)r(er)g(describ) r(es)h(the)f(Mac)n(h)g(k)o(ernel's)h(page-replacement)f(algorithm.)18 b(In)12 b(Section)g(2)f(w)n(e)h(giv)o(e)75 831 y(an)j(o)o(v)o(erview)h(of)f(the)h(alg\ orithm's)f(op)q(eration)g(and)h(p)r(oin)o(t)f(out)g(some)h(problems)g(with)g (the)f(em)o(ulation)75 888 y(of)i(hardw)o(are)g(page-referenced)h(information\ .)27 b(W)l(e)17 b(examine)h(TLB-based)h(em)o(ulation)f(in)g(Section)g(3)75 944 y(and)h(then)h(presen)o(t)f(Mac)o(h)g(3.0's)f(mac)o(hine-indep)t(endent)h(em) n(ulation)i(in)f(Section)g(4.)32 b(In)19 b(Section)i(5,)75 1000 y(w)o(e)f(dis\ cuss)h(the)f(in\015uence)i(of)e(Mac)n(h's)g(external)g(memory)f(managemen)o (t)h(in)o(terface)g(on)g(the)g(page-)75 1057 y(replacement)f(algorithm.)32 b (W)l(e)19 b(consider)i(related)e(w)o(ork)g(in)h(Section)g(6.)31 b(Finally)n (,)20 b(in)g(Section)g(7)f(w)o(e)75 1113 y(summarize)d(the)f(pap)q(er.)75 1257 y fo(2)69 b(P)n(age)23 b(Replacemen)n(t)d(in)i(Mac)n(h)75 1358 y fh(The)h(Mac) n(h)g(k)o(ernel)g(uses)g(a)g(FIF)n(O)g(with)g(Second)h(Chance)f(page-replacem\ ent)f(algorithm.)42 b(This)75 1414 y(algorithm)19 b(appro)n(ximates)g(the)g (p)r(erformance)g(of)f(LRU)h(page-replacement)g(with)g(the)g(e\016ciency)h (of)75 1471 y(FIF)n(O)13 b(page-replacement.)19 b(The)13 b(mac)n(hine-indep)t (endent)f(pageout)g(daemon,)h(which)f(implemen)q(ts)g(the)75 1527 y(algorithm\ ,)18 b(uses)g(Mac)n(h's)g(pmap)g(in)o(terface)g(to)f(manipulate)i(mac)n(hine-\ dep)t(endent)e(page-referenced)75 1584 y(information.)i(On)13 b(arc)o(hitectu\ res)g(without)f(suc)o(h)h(information,)g(the)f(pmap)h(mo)q(dule)g(and)g(the)f (pageout)75 1640 y(daemon)j(m)o(ust)g(in)o(teract)g(to)f(em)o(ulate)i(page-re\ ferenced)g(supp)r(ort.)146 1697 y(Mac)n(h's)f(page-replacement)g(algorithm)g (has)g(t)o(w)n(o)g(ma)r(jor)g(adv)m(an)o(tages:)143 1791 y fe(\017)23 b fg (Simplicity)16 b fh(|)g(The)h(algorithm)g(attempts)e(to)h(reclaim)h(a)g(reaso\ nable)g(page,)f(not)g(the)g(optimal)189 1847 y(page.)j(A)d(small)g(amoun)n (t)f(of)g(co)q(de)h(and)f(run)o(time)g(e\013ort)g(pro)q(duces)h(goo)q(d)g(p)q (erformance.)143 1941 y fe(\017)23 b fg(Sc)m(alability)15 b fh(|)g(The)h(p)q (erformance)f(of)g(the)g(algorithm)g(is)h(relatively)g(insensitive)g(to)e(the) i(actual)189 1997 y(amoun)n(t)10 b(of)g(ph)o(ysical)i(memory)-5 b(,)11 b(b)r (ecause)g(the)f(pageout)g(daemon)g(nev)o(er)h(scans)f(ph)o(ysical)i(memory) 189 2054 y(directly)m(.)20 b(Instead,)15 b(it)h(op)q(erates)f(on)g(queues)h (of)f(ph)o(ysical)h(pages.)75 2148 y(Unfortunately)l(,)e(the)g(Mac)o(h)g(2.5) f(implementation)h(of)f(the)h(algorithm)g(pro)o(v)o(ed)g(to)f(b)r(e)h(di\016c\ ult)h(to)f(tune)75 2204 y(prop)q(erly)j(on)f(arc)n(hitectures)h(without)f(pag\ e-referenced)h(supp)r(ort,)e(and)h(consequently)g(it)h(p)q(erformed)75 2260 y (unsatisfactorily)f(on)f(those)g(arc)n(hitectures.)75 2382 y fd(2.1)56 b(FIF) n(O)19 b(with)g(Second)f(Chance)75 2468 y fh(The)12 b(Mac)n(h)g(implemen)q (tation)f(of)g(FIF)o(O)h(with)g(Second)g(Chance)g(uses)g(three)g(queues)g(of) g(ph)o(ysical)h(pages,)75 2524 y(kno)o(wn)j(as)h(the)f(free)h(queue,)h(the)e (activ)o(e)h(queue,)h(and)f(the)f(inactive)h(queue.)25 b(The)17 b(pageout)f (daemon,)75 2581 y(a)h(system)g(thread)h(running)g(inside)i(the)d(k)o(ernel's) h(address)g(space,)g(mo)n(v)o(es)f(pages)h(from)e(the)i(inactive)75 2637 y (queue)e(to)f(the)g(free)g(queue)h(and)g(from)e(the)h(activ)o(e)h(queue)g(to) e(the)i(inactiv)o(e)g(queue.)964 2825 y(2)p eop %%Page: 3 3 bop 146 42 a fh(T)l(o)15 b(manage)h(ph)o(ysical)h(memory)l(,)e(the)h(k)o(ern\ el)h(manipulates)g(small)g(page)f(structures.)21 b(Eac)o(h)16 b(page)75 98 y (structure)e(represen)o(ts)g(one)g(page)h(of)e(physical)i(memory)l(.)k(The)14 b(structure)g(records)g(v)n(arious)g(attributes)75 154 y(of)h(the)g(ph)o(ysic\ al)i(page,)d(including)k(its)e(address,)e(and)i(con)o(tains)f(link)i(\014elds) f(for)f(the)g(paging)h(queues.)146 211 y(P)n(ages)g(on)g(the)g(free)g(queue)g (con)o(tain)g(no)g(useful)h(data.)22 b(All)17 b(pages)f(on)f(the)h(free)g(que\ ue)h(are)f(equiv-)75 267 y(alent.)25 b(The)17 b(k)o(ernel)h(allo)r(cates)f (pages)g(from)f(the)h(free)h(queue)g(to)e(satisfy)h(page)g(faults)g(or)g(to)f (p)r(erform)75 324 y(internal)h(data)g(structure)g(allo)r(cation.)26 b(Zero-\ \014lling,)19 b(if)e(necessary)m(,)g(happ)r(ens)g(after)g(a)g(page)g(is)g(tak) o(en)75 380 y(from)f(the)g(free)h(queue.)25 b(If)17 b(there)f(are)g(insu\016c\ ien)q(t)h(free)f(pages,)g(an)h(allo)r(cating)g(thread)f(w)o(aits)g(for)g(the) 75 437 y(pageout)f(daemon)g(to)f(create)h(more)g(free)g(pages.)146 493 y(P)n (ages)i(on)g(the)g(activ)o(e)g(queue)g(are)g(mapp)q(ed)h(b)o(y)f(some)f(pro)q (cess)i(and)f(are)f(assumed)h(to)g(b)q(elong)h(to)75 550 y(the)h(system's)e (w)o(orking)i(set.)29 b(The)19 b(activ)o(e)g(queue)g(is)g(FIF)o(O;)f(new)h (pages)f(start)g(at)g(the)g(bac)o(k)h(of)f(the)75 606 y(queue)e(and)f(the)h (pageout)e(daemon)i(tak)n(es)f(pages)g(from)f(the)i(fron)n(t)f(of)g(the)g(act\ iv)o(e)g(queue.)146 663 y(The)k(inactive)g(queue,)h(which)f(is)g(also)g(FIF)o (O,)g(acts)f(as)h(a)g(bu\013er)g(b)q(et)o(w)n(een)h(the)f(free)g(queue)h(and) 75 719 y(the)c(activ)o(e)g(queue.)24 b(Inactiv)o(e)17 b(pages)e(are)h(assumed) g(to)g(b)q(e)h(less)f(v)n(aluable)h(than)f(activ)o(e)g(pages.)23 b(P)n(ages) 75 775 y(which)f(are)f(referenced)i(while)g(on)e(the)h(inactive)g(queue)g(ret\ urn)g(to)f(the)h(activ)o(e)g(queue)g(instead)g(of)75 832 y(mo)n(ving)14 b(to) e(the)h(free)g(queue.)20 b(The)14 b(inactiv)o(e)g(queue)f(implemen)q(ts)g(the) g(page-replacement)f(algorithm's)75 888 y(LRU)j(appro)n(ximation)h(b)o(y)f (prev)o(en)o(ting)h(frequen)o(tly-referenced)h(pages)e(from)f(b)r(eing)i(recl\ aimed.)146 945 y(The)g(pageout)g(daemon's)f(primary)i(resp)q(onsibilit)q(y)f (is)h(creating)f(free)h(pages.)22 b(It)17 b(w)n(ak)o(es)f(up)g(when)75 1001 y (the)21 b(free)f(queue)i(falls)f(b)r(elo)o(w)f fc(vm_page_free_min)e fh(pages\ ,)k(and)f(runs)f(until)h(the)g(free)f(queue)i(con-)75 1058 y(tains)15 b(at)f (least)h fc(vm_page_free_target)d fh(pages.)20 b(The)15 b(k)o(ernel)g(uses)h (these)f(thresholds)g(to)f(reduce)i(the)75 1114 y(o)n(v)o(erhead)k(of)e(rep)r (eatedly)h(inv)o(oking)g(the)g(pageout)f(daemon.)31 b(Once)20 b(a)o(w)n(ak)o (e,)f(the)g(pageout)g(daemon)75 1171 y(scans)d(the)f(inactive)h(queue.)22 b (Clean)16 b(pages)g(are)f(immediately)i(mo)o(v)n(ed)f(to)f(the)h(free)g(queue\ ,)g(and)g(dirt)o(y)75 1227 y(pages)21 b(are)g(\014rst)g(cleaned)i(b)o(y)f(wri\ ting)g(them)f(to)g(bac)o(king)h(store.)38 b(After)21 b(the)g(free)h(queue)g (reac)o(hes)75 1284 y fc(vm_page_free_target)14 b fh(\(or)i(if)h(the)g(inacti\ ve)g(queue)h(is)f(empt)o(y\),)g(the)f(pageout)h(daemon)g(re\014lls)h(the)75 1340 y(inactive)d(queue)h(from)f(the)g(activ)o(e)g(queue,)h(un)o(til)g(it)g (reac)n(hes)g fc(vm_page_inactive_target)p fh(.)146 1396 y(Figure)f(1)g(sho)o (ws)f(the)i(mo)n(v)o(emen)o(t)f(of)g(pages)g(among)f(the)h(activ)o(e,)g(inact\ ive,)g(and)h(free)f(queues.)390 1455 y 19471401 9406792 9209446 30588518 28680847 39995310 startTexFig %%BeginDocument: queues.ps 50 dict begin /arrowHeight 8 def /arrowWidth 4 def /none null def /numGraphicParameters 17 def /stringLimit 65535 def /Begin { save numGraphicParameters dict begin } def /End { end restore } def /SetB { dup type /nulltype eq { pop false /brushRightArrow idef false /brushLeftArrow idef true /brushNone idef } { /brushDashOffset idef /brushDashArray idef 0 ne /brushRightArrow idef 0 ne /brushLeftArrow idef /brushWidth idef false /brushNone idef } ifelse } def /SetCFg { /fgblue idef /fggreen idef /fgred idef } def /SetCBg { /bgblue idef /bggreen idef /bgred idef } def /SetF { /printSize idef /printFont idef } def /SetP { dup type /nulltype eq { pop true /patternNone idef } { /patternGrayLevel idef patternGrayLevel -1 eq { /patternString idef } if false /patternNone idef } ifelse } def /BSpl { 0 begin storexyn newpath n 1 gt { 0 0 0 0 0 0 1 1 true subspline n 2 gt { 0 0 0 0 1 1 2 2 false subspline 1 1 n 3 sub { /i exch def i 1 sub dup i dup i 1 add dup i 2 add dup false subspline } for n 3 sub dup n 2 sub dup n 1 sub dup 2 copy false subspline } if n 2 sub dup n 1 sub dup 2 copy 2 copy false subspline patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if brushNone not { istroke } if 0 0 1 1 leftarrow n 2 sub dup n 1 sub dup rightarrow } if end } dup 0 4 dict put def /Circ { newpath 0 360 arc patternNone not { ifill } if brushNone not { istroke } if } def /CBSpl { 0 begin dup 2 gt { storexyn newpath n 1 sub dup 0 0 1 1 2 2 true subspline 1 1 n 3 sub { /i exch def i 1 sub dup i dup i 1 add dup i 2 add dup false subspline } for n 3 sub dup n 2 sub dup n 1 sub dup 0 0 false subspline n 2 sub dup n 1 sub dup 0 0 1 1 false subspline patternNone not { ifill } if brushNone not { istroke } if } { Poly } ifelse end } dup 0 4 dict put def /Elli { 0 begin newpath 4 2 roll translate scale 0 0 1 0 360 arc patternNone not { ifill } if brushNone not { istroke } if end } dup 0 1 dict put def /Line { 0 begin 2 storexyn newpath x 0 get y 0 get moveto x 1 get y 1 get lineto brushNone not { istroke } if 0 0 1 1 leftarrow 0 0 1 1 rightarrow end } dup 0 4 dict put def /MLine { 0 begin storexyn newpath n 1 gt { x 0 get y 0 get moveto 1 1 n 1 sub { /i exch def x i get y i get lineto } for patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if brushNone not { istroke } if 0 0 1 1 leftarrow n 2 sub dup n 1 sub dup rightarrow } if end } dup 0 4 dict put def /Poly { 3 1 roll newpath moveto -1 add { lineto } repeat closepath patternNone not { ifill } if brushNone not { istroke } if } def /Rect { 0 begin /t exch def /r exch def /b exch def /l exch def newpath l b moveto l t lineto r t lineto r b lineto closepath patternNone not { ifill } if brushNone not { istroke } if end } dup 0 4 dict put def /Text { ishow } def /idef { dup where { pop pop pop } { exch def } ifelse } def /ifill { 0 begin gsave patternGrayLevel -1 ne { fgred bgred fgred sub patternGrayLevel mul add fggreen bggreen fggreen sub patternGrayLevel mul add fgblue bgblue fgblue sub patternGrayLevel mul add setrgbcolor eofill } { eoclip originalCTM setmatrix pathbbox /t exch def /r exch def /b exch def /l exch def /w r l sub ceiling cvi def /h t b sub ceiling cvi def /imageByteWidth w 8 div ceiling cvi def /imageHeight h def bgred bggreen bgblue setrgbcolor eofill fgred fggreen fgblue setrgbcolor w 0 gt h 0 gt and { l b translate w h scale w h true [w 0 0 h neg 0 h] { patternproc } imagemask } if } ifelse grestore end } dup 0 8 dict put def /istroke { gsave brushDashOffset -1 eq { [] 0 setdash 1 setgray } { brushDashArray brushDashOffset setdash fgred fggreen fgblue setrgbcolor } ifelse brushWidth setlinewidth originalCTM setmatrix stroke grestore } def /ishow { 0 begin gsave fgred fggreen fgblue setrgbcolor /fontDict printFont findfont printSize scalefont dup setfont def /descender fontDict begin 0 [FontBBox] 1 get FontMatrix end transform exch pop def /vertoffset 0 descender sub printSize sub printFont /Courier ne printFont /Courier-Bold ne and { 1 add } if def { 0 vertoffset moveto show /vertoffset vertoffset printSize sub def } forall grestore end } dup 0 3 dict put def /patternproc { 0 begin /patternByteLength patternString length def /patternHeight patternByteLength 8 mul sqrt cvi def /patternWidth patternHeight def /patternByteWidth patternWidth 8 idiv def /imageByteMaxLength imageByteWidth imageHeight mul stringLimit patternByteWidth sub min def /imageMaxHeight imageByteMaxLength imageByteWidth idiv patternHeight idiv patternHeight mul patternHeight max def /imageHeight imageHeight imageMaxHeight sub store /imageString imageByteWidth imageMaxHeight mul patternByteWidth add string def 0 1 imageMaxHeight 1 sub { /y exch def /patternRow y patternByteWidth mul patternByteLength mod def /patternRowString patternString patternRow patternByteWidth getinterval def /imageRow y imageByteWidth mul def 0 patternByteWidth imageByteWidth 1 sub { /x exch def imageString imageRow x add patternRowString putinterval } for } for imageString end } dup 0 12 dict put def /min { dup 3 2 roll dup 4 3 roll lt { exch } if pop } def /max { dup 3 2 roll dup 4 3 roll gt { exch } if pop } def /arrowhead { 0 begin transform originalCTM itransform /taily exch def /tailx exch def transform originalCTM itransform /tipy exch def /tipx exch def /dy tipy taily sub def /dx tipx tailx sub def /angle dx 0 ne dy 0 ne or { dy dx atan } { 90 } ifelse def gsave originalCTM setmatrix tipx tipy translate angle rotate newpath 0 0 moveto arrowHeight neg arrowWidth 2 div lineto arrowHeight neg arrowWidth 2 div neg lineto closepath patternNone not { originalCTM setmatrix /padtip arrowHeight 2 exp 0.25 arrowWidth 2 exp mul add sqrt brushWidth mul arrowWidth div def /padtail brushWidth 2 div def tipx tipy translate angle rotate padtip 0 translate arrowHeight padtip add padtail add arrowHeight div dup scale arrowheadpath ifill } if brushNone not { originalCTM setmatrix tipx tipy translate angle rotate arrowheadpath istroke } if grestore end } dup 0 9 dict put def /arrowheadpath { newpath 0 0 moveto arrowHeight neg arrowWidth 2 div lineto arrowHeight neg arrowWidth 2 div neg lineto closepath } def /leftarrow { 0 begin y exch get /taily exch def x exch get /tailx exch def y exch get /tipy exch def x exch get /tipx exch def brushLeftArrow { tipx tipy tailx taily arrowhead } if end } dup 0 4 dict put def /rightarrow { 0 begin y exch get /tipy exch def x exch get /tipx exch def y exch get /taily exch def x exch get /tailx exch def brushRightArrow { tipx tipy tailx taily arrowhead } if end } dup 0 4 dict put def /midpoint { 0 begin /y1 exch def /x1 exch def /y0 exch def /x0 exch def x0 x1 add 2 div y0 y1 add 2 div end } dup 0 4 dict put def /thirdpoint { 0 begin /y1 exch def /x1 exch def /y0 exch def /x0 exch def x0 2 mul x1 add 3 div y0 2 mul y1 add 3 div end } dup 0 4 dict put def /subspline { 0 begin /movetoNeeded exch def y exch get /y3 exch def x exch get /x3 exch def y exch get /y2 exch def x exch get /x2 exch def y exch get /y1 exch def x exch get /x1 exch def y exch get /y0 exch def x exch get /x0 exch def x1 y1 x2 y2 thirdpoint /p1y exch def /p1x exch def x2 y2 x1 y1 thirdpoint /p2y exch def /p2x exch def x1 y1 x0 y0 thirdpoint p1x p1y midpoint /p0y exch def /p0x exch def x2 y2 x3 y3 thirdpoint p2x p2y midpoint /p3y exch def /p3x exch def movetoNeeded { p0x p0y moveto } if p1x p1y p2x p2y p3x p3y curveto end } dup 0 17 dict put def /storexyn { /n exch def /y n array def /x n array def n 1 sub -1 0 { /i exch def y i 3 2 roll put x i 3 2 roll put } for } def Begin [ 0.923077 0 0 0.923077 0 0 ] concat /originalCTM matrix currentmatrix def Begin %I Pict [ 1 0 0 1 22 4 ] concat Begin %I Text 0 0 0 SetCFg /Times-Roman 12 SetF [ 1 0 0 1 259 630 ] concat [ (Free Queue) ] Text End Begin %I Elli 1 0 0 [] 0 SetB 0 0 0 SetCFg 1 1 1 SetCBg none SetP %I p n [ 1 0 0 1 98.5 126.5 ] concat 188 499 52 26 Elli End End %I eop Begin %I Pict [ 1 0 0 1 -20 31 ] concat Begin %I Text 0 0 0 SetCFg /Times-Roman 12 SetF [ 1 0 0 1 190 518 ] concat [ (Active Queue) ] Text End Begin %I Elli 1 0 0 [] 0 SetB 0 0 0 SetCFg 1 1 1 SetCBg none SetP %I p n [ 1 0 0 1 39.5 14 ] concat 188 499 52 26 Elli End End %I eop Begin %I Pict [ 1 0 0 1 61 31 ] concat Begin %I Text 0 0 0 SetCFg /Times-Roman 12 SetF [ 1 0 0 1 319 518 ] concat [ (Inactive Queue) ] Text End Begin %I Elli 1 0 0 [] 0 SetB 0 0 0 SetCFg 1 1 1 SetCBg none SetP %I p n [ 1 0 0 1 168.5 13.5 ] concat 188 499 52 26 Elli End End %I eop Begin %I BSpl 1 0 1 [] 0 SetB 0 0 0 SetCFg 1 1 1 SetCBg 0 SetP [ 0.442735 0 0 0.5 183.654 428 ] concat 177 379 142 355 107 327 74 285 4 BSpl End Begin %I BSpl 1 0 1 [] 0 SetB 0 0 0 SetCFg 1 1 1 SetCBg 0 SetP [ 0.5 0 0 0.5 179.75 427.5 ] concat 454 284 429 317 394 352 355 382 4 BSpl End Begin %I BSpl 1 0 1 [] 0 SetB 0 0 0 SetCFg 1 1 1 SetCBg 0 SetP [ 0.5 0 0 0.5 179.5 428 ] concat 155 250 198 271 267 275 331 271 379 253 5 BSpl End Begin %I BSpl 1 0 1 [] 0 SetB 0 0 0 SetCFg 1 1 1 SetCBg 0 SetP [ 0.5 0 0 0.5 179 428 ] concat 383 208 324 189 224 187 150 206 4 BSpl End Begin %I Text 0 0 0 SetCFg /Courier 10 SetF [ 1 0 0 1 181.5 617.5 ] concat [ (Allocation) ] Text End Begin %I Text 0 0 0 SetCFg /Courier 10 SetF [ 1 0 0 1 379.5 614.5 ] concat [ (Pageout Scan) ] Text End Begin %I Text 0 0 0 SetCFg /Courier 10 SetF [ 1 0 0 1 277 579 ] concat [ (Pageout Scan) ] Text End Begin %I Text 0 0 0 SetCFg /Courier 10 SetF [ 1 0 0 1 283 516.5 ] concat [ (References) ] Text End End %I eop showpage end %%EndDocument endTexFig 681 2149 a(Figure)h(1:)j(The)d(P)n(aging)g(Queues)75 2320 y fd (2.2)56 b(Reference)16 b(Bits)75 2406 y fh(The)f(FIF)n(O)g(with)g(Second)h (Chance)f(algorithm)f(relies)i(on)f(b)q(eing)h(able)f(to)f(detect)h(reference\ s)g(to)f(pages)75 2463 y(on)j(the)f(inactive)h(queue.)25 b(The)17 b(Mac)o(h)g (k)n(ernel)h(mak)o(es)e(use)h(of)g(page-referenced)g(information,)g(if)g(it)g (is)75 2519 y(pro)o(vided)f(b)o(y)g(the)g(hardw)n(are,)f(through)h(t)n(w)o (o)f(pmap)h(functions.)22 b(If)16 b(the)f(hardw)o(are)g(do)r(es)g(not)h(direc\ tly)75 2576 y(supply)22 b(page-referenced)f(information)g(then)g(the)g(k)n (ernel)h(m)o(ust)e(someho)o(w)g(em)o(ulate)h(it.)36 b(As)21 b(done)75 2632 y (in)d(Mac)n(h)f(2.5,)g(this)g(leads)h(to)e(t)n(w)o(o)h(v)n(ery)g(di\013erent) g(mo)q(des)g(of)f(op)r(eration)h(for)f(the)h(page-replacement)75 2689 y(algor\ ithm.)964 2825 y(3)p eop %%Page: 4 4 bop 146 42 a fh(The)20 b(Mac)o(h)g(k)o(ernel)i(accesses)e(MMU)g(hardw)o(are) g(through)g(a)g(mac)o(hine-indep)t(endent)g(interface,)75 98 y(the)g(pmap)g (interface)g([Rashid)h(et)f(al.)35 b(87,)19 b(T)l(ev)n(anian)h(87].)34 b(A)20 b(pmap)h(is)f(the)g(mac)o(hine-dep)s(endent)75 154 y(represen)o(tation)15 b (of)f(an)h(address)f(space.)20 b(The)15 b(pmap)g(interface)f(con)o(tains,)h (for)f(example,)h(functions)h(to)75 211 y(create)c(and)h(destro)o(y)f(pmaps)h (and)g(en)o(ter)f(virtual-to-physical)h(mappings)h(in)o(to)e(a)h(pmap.)19 b (The)13 b(k)n(ernel's)75 267 y(pmap)i(mo)q(dule)i(implements)e(the)g(pmap)h (in)o(terface.)146 324 y(Some)22 b(hardw)n(are)g(arc)o(hitectures)g(pro)o(vid\ e)h(page-referenced)g(information.)41 b(On)23 b(arc)n(hitectures)75 380 y(wit\ h)15 b(page)g(tables,)g(this)h(commonly)f(tak)n(es)h(the)f(form)f(of)h(a)f (reference)i(bit)g(in)g(eac)o(h)f(page-table)h(en)o(try)-5 b(.)75 437 y(The) 14 b(op)q(erating)f(system)h(can)f(clear)h(the)g(bit)g(in)g(a)f(page-table)h (entry)f(and)g(virtual)h(memory)f(references)75 493 y(through)f(a)g(page-tabl\ e)h(en)o(try)f(set)g(the)h(bit.)19 b(Ho)o(w)n(ev)o(er,)13 b(other)f(forms)f (of)h(page-referenced)i(information)75 550 y(are)k(p)q(ossible.)30 b(F)l(or) 18 b(example,)h(the)f(inv)n(erted)g(page)g(table)h(found)f(in)h(the)f(IBM)h (R)l(T)f([IBM)g(88])f(has)h(a)75 606 y(single)f(reference)e(bit)h(p)r(er)f (ph)o(ysical)h(page.)146 663 y(The)22 b(pmap)f(mo)q(dule)i(m)o(ust)f(pro)n (vide)h(t)n(w)o(o)f(functions)g(on)g(a)f(physical)h(page)g(address,)h(to)e (clear)75 719 y(and)c(query)g(reference)g(information,)g(as)g(sho)n(wn)g(in)h (Figure)f(2.)24 b(Because)18 b(the)e(interface)h(op)q(erates)f(on)75 775 y (ph)o(ysical)g(pages)e(instead)i(of)e(virtual)h(pages,)f(the)h(implemen)q(tat\ ion)f(on)g(arc)o(hitectures)h(with)g(reference)75 832 y(bits)e(in)g(page-tabl\ e)f(en)o(tries)h(m)n(ust)f(examine)h(or)f(mo)q(dify)h(the)f(reference)h(bit)g (in)g(ev)o(ery)f(page-table)g(entry)75 888 y(mapping)19 b(the)f(sp)r(eci\014e\ d)i(ph)o(ysical)f(page.)29 b(On)19 b(arc)n(hitectures)g(without)f(hardw)o(are) g(page-referenced)75 945 y(information,)13 b fc(pmap_clear_reference)e fh(sho\ uld)j(remo)n(v)o(e)f(all)h(mappings)g(for)e(the)h(physical)h(page)f(and)75 1001 y fc(pmap_is_referenced)g fh(should)j(alw)o(a)n(ys)f(return)g(F)-5 b(ALS\ E.)202 1122 y fb(void)21 b(pmap_clear_referenc)o(e\(ph)o(ysica)o(l)e(address\ \))375 1172 y fj(Clear)c(mac)n(hine-dep)q(endent)g(page-referenced)j(informat\ ion)12 b(asso)q(ciated)k(with)e(the)375 1222 y(sp)r(eci\014ed)g(ph)o(ysical)g (page.)202 1296 y fb(boolean_t)20 b(pmap_is_referenced)o(\(phys)o(ical)e(addr\ ess\))375 1346 y fj(Query)13 b(mac)n(hine-dep)r(endent)f(page-referenced)j (information)10 b(asso)q(ciated)j(with)f(the)375 1396 y(sp)r(eci\014ed)j(ph)o (ysical)f(page,)h(returning)g(TR)n(UE)g(if)f(the)i(ph)n(ysical)f(page)f(has)h (b)q(een)h(ac-)375 1446 y(cessed)g(since)f(the)f(page-referenced)i(informatio\ n)11 b(w)o(as)j(last)g(cleared.)608 1581 y fh(Figure)h(2:)20 b(P)o(age-Refere\ nced)c(F)l(unctions)146 1681 y(Using)g(these)g(pmap)h(functions,)f(the)g(Mac) o(h)g(2.5)f(pageout)h(daemon)g(functions)h(as)e(sho)o(wn)h(in)h(Fig-)75 1737 y (ure)k(3.)35 b(The)21 b(page-replacement)f(algorithm)h(b)q(eha)o(v)o(es)g(qui\ te)g(di\013eren)o(tly)g(on)g(mac)n(hines)h(with)f(and)75 1794 y(without)15 b (hardw)o(are)g(page-referenced)h(supp)r(ort:)143 1874 y fe(\017)23 b fh(On)15 b(mac)n(hines)h(without)e(suc)o(h)h(supp)r(ort,)f(pages)g(on)g(the)h(inactive) f(queue)h(are)g(not)f(mapp)q(ed)h(into)189 1931 y(an)n(y)e(address)f(space.) 19 b(F)l(aults)13 b(on)f(pages)g(in)h(the)g(inactiv)o(e)g(queue,)g(kno)o(wn)f (as)g fg(r)n(e)n(activation)i(faults)p fh(,)189 1987 y(are)k(satis\014ed)g (without)g(p)r(erforming)g(I/O,)g(b)o(y)g(mo)o(ving)h(the)f(page)g(bac)o(k)g (to)g(the)g(activ)o(e)g(queue)189 2044 y(and)d(remapping)h(it.)143 2132 y fe (\017)23 b fh(On)d(mac)n(hines)h(with)f(suc)o(h)g(supp)r(ort,)f(pages)g(on)h (the)g(inactiv)o(e)g(queue)h(are)e(left)h(mapp)q(ed)g(into)189 2189 y(address) 15 b(spaces.)22 b(Instead)16 b(of)g(using)g(reactiv)n(ation)g(faults)g(to)f (mo)n(v)o(e)h(pages)f(bac)o(k)h(to)f(the)h(activ)o(e)189 2245 y(queue,)f(the) g(pageout)g(daemon)g(notices)h(b)q(efore)f(freeing)h(a)f(page)g(that)f(it)h (has)g(b)r(een)g(referenced,)189 2302 y(and)h(activ)n(ates)g(the)h(page)f(ins\ tead.)24 b(This)18 b(t)n(yp)q(e)f(of)f(reactiv)n(ation)g(ma)o(y)g(b)r(e)g(vie\ wed)h(as)f(the)g(lazy)189 2358 y(ev)m(aluation)g(of)f(reactiv)n(ation)g(fault\ s.)75 2501 y fd(2.3)56 b(A)19 b(Problem)75 2587 y fh(Mac)n(h's)11 b(\014rst)f (platform)g(w)n(as)h(the)f(V)-5 b(AX-11/784,)10 b(a)g(four-pro)q(cessor)g(v)o (ersion)h(of)f(the)h(V)-5 b(AX-11/780.)17 b(The)75 2644 y(V)-5 b(AX)19 b(arc) n(hitecture)g([DEC)f(79])f(do)q(es)i(not)f(pro)n(vide)i(hardw)n(are)e(referen\ ce)h(bits.)30 b(As)19 b(originally)h(con-)75 2700 y(ceived)14 b([T)l(ev)m(ani\ an)g(87,)g(pages)f(43{45],)f(the)i(inactive)f(queue)i(con)o(tained)f(pages)g (not)f(mapp)q(ed)i(in)o(to)e(an)o(y)964 2825 y(4)p eop %%Page: 5 5 bop 225 81 a fc(vm_pageout_scan\(\))22 b({)416 138 y(while)h(\(vm_page_free_\ count)e(<)j(vm_page_free_target\))d({)607 194 y(page)i(=)h(dequeue\(vm_page_i\ nactive_)o(queue\);)607 251 y(if)f(\(pmap_is_referenced\(page->phy)o(s_addr\)) o(\))e({)798 307 y(enqueue\(vm_page_active_q)o(ueue,)g(page\);)607 364 y(})j (else)f({)798 420 y(clean)g(the)g(page)h(if)f(it)h(is)f(dirty;)798 477 y(enqu\ eue\(vm_page_free_que)o(ue,)e(page\);)607 533 y(})416 589 y(})416 702 y(while) i(\(vm_page_inactive_count)e(<)j(vm_page_inactive_target)o(\))d({)607 759 y (page)i(=)h(dequeue\(vm_page_active_qu)o(eue\);)607 815 y(pmap_clear_referenc\ e\(page)o(->phys_)o(addr\);)607 872 y(enqueue\(vm_page_inactive_)o(queue\);) 416 928 y(})225 985 y(})560 1132 y fh(Figure)16 b(3:)j(The)d(Mac)n(h)g(2.5)e (P)o(ageout)g(Daemon)75 1266 y(address)f(space,)f(and)h(at)f(b)q(o)q(ot-time) h(the)f(implemen)q(tation)g(con\014gured)h fc(vm_page_inactive_target)75 1322 y fh(to)k(a)h(small)g(v)n(alue,)h(nev)o(er)f(larger)f(than)h(80)f(pages.)28 b (Once)19 b(con\014gured,)g(the)f(implementation)g(nev)o(er)75 1379 y(c)o(hang\ ed)e fc(vm_page_inactive_targe)o(t)p fh(.)146 1435 y(After)h(some)h(exp)r(eri\ ence)i(with)e(the)h(page-replacement)f(algorithm,)g(it)h(b)q(ecame)g(clear)f (that)g(the)75 1492 y(original)f(con\014guration)e(of)g(the)h fc(vm_page_inac\ tive_target)c fh(w)o(as)j(not)g(appropriate)g(for)g(mac)o(hines)75 1548 y(wit\ h)e(hardw)o(are)f(page-referenced)i(supp)r(ort.)k(In)c(fact,)e(it)h(w)o(as)f (desirable)j(to)d(mak)n(e)h(the)g(inactive)g(queue)75 1605 y(larger)21 b(than) h(the)f(activ)o(e)h(queue.)40 b(A)21 b(large)h(inactive)f(queue)i(impro)o(v)n (es)f(the)g(qualit)o(y)g(of)f(the)g(LRU)75 1661 y(appro)o(ximation)14 b(b)o (y)g(giving)i(pages)e(more)f(time)i(in)g(which)f(to)g(b)q(e)h(referenced.)20 b (When)15 b(the)f(paging)h(rate)75 1717 y(is)d(high)h(and)f(the)g(pageout)f (daemon)h(runs)g(frequen)o(tly)l(,)g(a)g(small)g(inactive)g(queue)h(is)f(ine\ \013ective)g(b)q(ecause)75 1774 y(relativ)o(ely)18 b(few)f(pages)g(are)g(reac\ tiv)n(ated.)25 b(With)17 b(a)g(small)h(inactive)f(queue)h(and)f(a)g(high)h (paging)f(rate,)75 1830 y(the)d(page-replacement)g(algorithm)g(degenerates)g (to)f(almost)g(pure)i(FIF)n(O)f(replacement.)19 b(Ho)o(w)o(ev)o(er,)13 b(a)75 1887 y(reasonable)i(LRU)g(appro)o(ximation)g(is)h(most)e(imp)r(ortan)n(t)g (when)i(the)f(paging)g(rate)g(is)g(high,)h(b)q(ecause)g(it)75 1943 y(is)f(onl\ y)f(b)o(y)g(\014nding)h(the)g(system's)e(w)n(orking)h(set)g(and)g(k)o(eeping) h(it)g(resident)e(that)h(the)g(paging)g(rate)f(will)75 2000 y(come)i(do)o(wn.) 146 2056 y(T)l(o)h(examine)i(this)f(e\013ect,)g(w)n(e)g(used)h(a)e(small)i (compilation)g(test)e(suite)i(on)e(an)h(DECstation)f(3100)75 2113 y(\(DS3100\ \))f(con\014gured)j(to)f(use)g(8)g(megab)o(ytes)f(of)h(memory)l(.)26 b(The)17 b(DS3100)f(has)h(a)g(16.67Mhz)f(MIPS-)75 2169 y(arc)n(hitecture)k(R2000)e(CPU\ .)g(The)h(MIPS)g(arc)n(hitecture)h(do)q(es)f(not)f(pro)n(vide)i(page-referenc\ ed)g(infor-)75 2226 y(mation.)g(The)15 b(compilation)i(test)d(compiles)j(nine) f(small)g(C)f(programs.)146 2282 y(W)-5 b(e)19 b(ran)f(the)g(compilation)i (test)d(nine)j(consecutive)e(times)h(while)g(v)n(arying)f(the)g(inactive)h (target.)75 2338 y(Figure)i(4)g(summarizes)g(the)g(results.)37 b(With)21 b (a)f(small)i(inactive)f(target)e(of)h(20)h(pages)f(out)h(of)f(1100)75 2395 y (a)n(v)n(ailable)k(pages,)f(the)f(Mac)n(h)g(2.5)f(algorithm)h(p)r(erformed)f (p)r(o)q(orly)l(,)i(leading)h(to)d(excessive)h(paging.)75 2451 y(With)17 b (an)g(inactive)g(target)e(of)i(700)f(pages,)g(the)h(test)g(completed)h(appro) n(ximately)g(four)e(times)h(faster.)75 2508 y(Ev)o(en)g(after)g(the)g(inactiv\ e)g(target)f(w)o(as)h(lo)o(w)n(ered)h(to)f(the)g(original)h(small)g(v)n(alue,) g(the)f(test)g(completed)75 2564 y(more)12 b(quickly)h(b)r(ecause)g(the)g(sma\ ller)g(inactive)g(queue)h(b)q(ecame)f(more)g(e\013ectiv)o(e)g(once)g(the)g (paging)g(rate)75 2621 y(had)18 b(dropp)q(ed.)28 b(F)l(or)17 b(comparison,)h (the)f(test)g(to)q(ok)g(19.2s)f(to)h(complete)i(when)f(run)g(single-user)h (on)e(a)75 2677 y(DS3100)d(with)i(16)e(megab)o(ytes)h(of)f(memory)l(,)964 2825 y(5)p eop %%Page: 6 6 bop 390 0 a 18945146 14208860 0 0 18945146 14208860 startTexFig %%BeginDocument: plot.ps /MT {moveto} bind def /LT {lineto} bind def /sethsbcolor {setgray pop pop} bind def /x2sqrt3 2 sqrt 3 mul def /DoLText { gsave 3 1 roll translate rotate newpath 0 0 moveto show grestore } def /DoRText { gsave 3 1 roll translate rotate dup stringwidth pop neg 0 translate newpath 0 0 moveto show grestore } def /DoCText { gsave 3 1 roll translate rotate dup stringwidth pop 2 div neg 0 translate newpath 0 0 moveto show grestore } def /SymbolStart { gsave [] 0 setdash 3 1 roll translate dup dup scale 1 exch div setlinewidth newpath } def /SBox { SymbolStart -3 -3 moveto 3 -3 lineto 3 3 lineto -3 3 lineto closepath stroke grestore } def /SBullet { SymbolStart 0 0 3 0 360 arc fill grestore } def /SCircle { SymbolStart 0 0 3 0 360 arc stroke grestore } def /SCross { SymbolStart -3 -3 moveto 3 3 lineto stroke -3 3 moveto 3 -3 lineto stroke grestore } def /SCustom { pop pop pop } def /SDel { SymbolStart x2sqrt3 2 moveto x2sqrt3 neg 2 lineto 0 -4 lineto closepath stroke grestore } def /SPlus { SymbolStart -3 0 moveto 3 0 lineto stroke 0 -3 moveto 0 3 lineto stroke grestore } def /SDiamond { SymbolStart 45 rotate -3 -3 moveto 3 -3 lineto 3 3 lineto -3 3 lineto closepath stroke grestore } def /SEllipse { SymbolStart 2 1 scale 0 0 3 0 360 arc closepath stroke grestore } def /SNone { pop pop pop } def /SNumber { SymbolStart grestore } def /SSolidBox { SymbolStart -3 -3 moveto 3 -3 lineto 3 3 lineto -3 3 lineto closepath fill grestore } def /StarSide 6 36 cos div dup 36 sin mul sub 36 sin mul 36 cos div def /SStar { SymbolStart 0 3 translate -108 rotate 0 0 moveto 5 { StarSide 0 translate 0 0 lineto -72 rotate StarSide 0 translate 0 0 lineto 144 rotate } repeat closepath stroke grestore } def /STriangle { SymbolStart x2sqrt3 -2 moveto x2sqrt3 neg -2 lineto 0 4 lineto closepath stroke grestore } def /bar { gsave translate rotate exch 2 div exch % ci w/2 h newpath 2 copy pop 0 moveto 2 copy lineto 2 copy exch neg exch lineto 2 copy pop neg 0 lineto closepath stroke % ci w/2 h 3 -1 roll dup 0 ne { % w/2 h ci 3 copy pop moveto % w/2 h ci 3 copy add lineto 3 copy add exch neg exch lineto 3 copy pop exch neg exch lineto stroke 3 copy pop moveto % w/2 h ci 3 copy sub lineto 3 copy sub exch neg exch lineto 3 copy pop exch neg exch lineto stroke currentlinewidth 2 mul setlinewidth pop 2 copy moveto exch neg exch lineto stroke } {pop pop pop } ifelse grestore } def /linesfill { gsave clip initmatrix MFactor MFactor scale 0.5 setlinewidth rotate 1 dict begin /ksp 1000 MFactor div def ksp neg 5 ksp { % v newpath dup ksp exch moveto ksp neg exch lineto stroke } for end grestore newpath } def /lines2fill { gsave clip initmatrix MFactor MFactor scale 0.5 setlinewidth rotate 1 dict begin /ksp 1000 MFactor div def ksp neg 8 ksp { % v newpath dup ksp exch moveto dup ksp neg exch lineto stroke 2 add dup ksp exch moveto ksp neg exch lineto stroke } for end grestore newpath } def /lineswfill { gsave clip initmatrix MFactor MFactor scale 0.5 setlinewidth rotate 1 dict begin /ksp 1000 MFactor div def ksp neg 10 ksp { % v newpath dup ksp exch moveto ksp neg exch lineto stroke } for end grestore newpath } def /crosshatch { dup gsave linesfill grestore 90 add linesfill } def /fillbar { 2 dict begin /pg1 exch def /pg2 exch def 6 copy % save bar parameters gsave translate rotate exch 2 div exch % ci w/2 h 3 -1 roll % w/2 h ci newpath 3 copy pop pop neg 0 moveto 3 copy sub exch neg exch lineto 3 copy sub lineto 3 copy pop pop 0 lineto closepath pg1 3 copy sub exch neg exch moveto 3 copy add exch neg exch lineto 3 copy add lineto 3 copy sub lineto closepath pg2 grestore pop pop pop bar end } def save % Start Page save 0.0 0.0 translate 1.000000 1.000000 scale /MFactor 1.000000 def 1.000000 setlinewidth [] 0 setdash 1.000000 setlinewidth [] 0 setdash 0.0 19.7 155.0 0 56.7 25.6 {0.0 0.0 0.9 sethsbcolor fill} {0.0 0.0 0.8 sethsbcolor fill} fillbar 0.0 19.7 144.8 0 81.4 25.6 {0.0 0.0 0.9 sethsbcolor fill} {0.0 0.0 0.8 sethsbcolor fill} fillbar 0.0 19.7 139.1 0 106.1 25.6 {0.0 0.0 0.9 sethsbcolor fill} {0.0 0.0 0.8 sethsbcolor fill} fillbar 1.000000 setlinewidth [] 0 setdash 56.8 180.6 1.0000 SNone 81.5 170.4 1.0000 SNone 106.2 164.7 1.0000 SNone 1.000000 setlinewidth [] 0 setdash 1.000000 setlinewidth [] 0 setdash 0.0 19.7 61.7 0 130.8 25.6 {0.0 0.0 0.9 sethsbcolor fill} {0.0 0.0 0.4 sethsbcolor fill} fillbar 0.0 19.7 35.9 0 155.5 25.6 {0.0 0.0 0.9 sethsbcolor fill} {0.0 0.0 0.4 sethsbcolor fill} fillbar 0.0 19.7 50.2 0 180.2 25.6 {0.0 0.0 0.9 sethsbcolor fill} {0.0 0.0 0.4 sethsbcolor fill} fillbar 1.000000 setlinewidth [] 0 setdash 130.9 87.3 1.0000 SNone 155.6 61.5 1.0000 SNone 180.3 75.8 1.0000 SNone 1.000000 setlinewidth [] 0 setdash 1.000000 setlinewidth [] 0 setdash 0.0 19.7 45.2 0 204.9 25.6 {0.0 0.0 0.9 sethsbcolor fill} {0.0 0.0 0.8 sethsbcolor fill} fillbar 0.0 19.7 73.8 0 229.6 25.6 {0.0 0.0 0.9 sethsbcolor fill} {0.0 0.0 0.8 sethsbcolor fill} fillbar 0.0 19.7 78.7 0 254.3 25.6 {0.0 0.0 0.9 sethsbcolor fill} {0.0 0.0 0.8 sethsbcolor fill} fillbar 1.000000 setlinewidth [] 0 setdash 205.0 70.8 1.0000 SNone 229.7 99.4 1.0000 SNone 254.4 104.3 1.0000 SNone newpath 32.1 25.6 MT 279.1 25.6 LT stroke /Times-Roman findfont 10 scalefont setfont (First) 47.7 12.0 0 DoLText (Last) 245.9 12.0 0 DoLText 32.1 25.6 MT 32.1 210.4 LT stroke 32.1 48.7 MT 35.7 48.7 LT stroke 32.1 71.8 MT 35.7 71.8 LT stroke 32.1 94.9 MT 35.7 94.9 LT stroke 32.1 118.0 MT 35.7 118.0 LT stroke 32.1 141.1 MT 35.7 141.1 LT stroke 32.1 164.2 MT 35.7 164.2 LT stroke 32.1 187.3 MT 35.7 187.3 LT stroke 32.1 210.4 MT 35.7 210.4 LT stroke (Seconds) 10.0 177.2 90 DoLText (20) 18.6 43.7 0 DoLText (40) 18.6 66.8 0 DoLText (60) 18.6 89.9 0 DoLText (80) 18.6 113.0 0 DoLText (100) 13.6 136.1 0 DoLText (120) 13.6 159.2 0 DoLText (140) 13.6 182.3 0 DoLText (160) 13.6 205.4 0 DoLText (0) 23.6 20.6 0 DoLText (Small Inactive Target) 38.3 188.8 0 DoLText (Large Inactive) 126.7 108.0 0 DoLText (Target) 142.6 95.0 0 DoLText (Small Inactive) 200.8 131.1 0 DoLText (Target Again) 203.3 118.1 0 DoLText /Times-Roman findfont 12 scalefont setfont (Successive Compilation Tests) 72.2 0.0 0 DoLText restore restore %%EndDocument endTexFig 429 998 a fh(Figure)16 b(4:)j(A)c(Small)i(Inactiv)o(e)f(T)l(arget) e(Leads)i(T)l(o)e(Thrashing)146 1131 y(Unfortunately)l(,)h(a)f(large)h(inacti\ ve)g(queue)h(is)f(not)g(a)g(panacea.)k(On)d(mac)o(hines)g(without)f(hardw)n (are)75 1188 y(reference)h(bits,)f(pages)h(on)f(the)g(inactive)h(queue)g(are) f(unmapp)r(ed.)20 b(A)c(large)f(inactive)g(queue)h(on)g(these)75 1244 y(mac)o (hines)e(reduces)h(the)e(amoun)o(t)g(of)g(ph)o(ysical)i(memory)e(directly)i (a)n(v)m(ailable)h(to)d(applications,)i(leading)75 1301 y(to)f fg(r)n(e)n(act\ ivation)i(fault)g(thr)n(ashing)p fh(.)j(This)c(can)g(o)q(ccur)h(when)f(an)g (application's)g(w)o(orking)g(set)f(resides)i(in)75 1357 y(ph)o(ysical)h(memo\ ry)f(but)g(exceeds)h(the)f(capacit)o(y)h(of)e(the)h(activ)o(e)h(queue.)23 b (On)17 b(the)f(DS3100,)f(for)g(exam-)75 1414 y(ple,)i(a)e(reactiv)n(ation)g (fault)h(tak)n(es)g(115)p fa(\026)p fh(s.)21 b(Hence,)c(inappropriate)f(tunin\ g)h(of)e(the)h(page-replacement)75 1470 y(algorithm)f(can)h(greatly)e(decreas\ e)i(an)f(application's)i(p)q(erformance.)146 1527 y(F)-5 b(urthermore,)18 b (an)f(extremely)h(large)f(inactive)g(queue)i(increases)f(the)f(o)o(v)n(erhead) h(of)f(the)g(pageout)75 1583 y(daemon.)h(F)l(or)10 b(eac)o(h)h(unreferenced)h (page)e(that)g(it)h(\014nds)g(on)f(the)h(inactive)f(queue,)i(it)f(m)o(ust)f (pass)g(up)h(some)75 1639 y(n)o(um)o(b)q(er)18 b(of)f(referenced)i(pages.)27 b (If)18 b(the)g(inactiv)o(e)g(queue)h(con)o(tains)f(most)e(of)i(ph)o(ysical)h (memory)e(and)75 1696 y(almost)g(all)i(pages)e(on)h(it)g(are)f(referenced,)i (then)f(the)g(page-replacement)g(algorithm's)f(p)q(erformance)75 1752 y(degen\ erates.)h(T)m(o)10 b(\014nd)h(an)g(unreferenced)h(page,)f(the)f(pageout)g(dae\ mon)h(will)h(searc)o(h)f(the)f(large)h(inactive)75 1809 y(queue,)k(mo)o(ving) g(referenced)h(pages)f(from)f(the)h(inactiv)o(e)g(queue)h(to)e(the)h(activ)o (e)g(queue)h(and)f(then)g(bac)o(k)75 1865 y(to)g(the)g(inactive)g(queue)h(to) f(replenish)i(it.)146 1922 y(The)12 b(solution)h(to)e(this)h(dilemma)i(in)e (Mac)o(h)g(2.5)f(w)o(as)g(to)h(mak)n(e)g(it)g(p)r(ossible)h(for)e(mac)o(hine-\ dep)s(endent)75 1978 y(co)q(de)18 b(to)e(o)n(v)o(erride)i(the)f(b)q(o)q(ot-ti\ me)g(con\014guration)g(of)g fc(vm_page_inactive_target)c fh(and)k(the)g(other) 75 2035 y(parameters)e(of)h(the)h(page-replacement)f(algorithm.)23 b(The)17 b (default)g(size)g(of)f(the)g(inactive)h(queue)g(w)n(as)75 2091 y(increased)g (to)e(t)n(w)o(o-thirds)h(of)f(a)o(v)m(ailable)j(memory)-5 b(,)16 b(and)g(arc) n(hitectures)h(without)e(hardw)o(are)g(reference)75 2148 y(supp)r(ort)f(o)o (v)o(errode)i(this)g(to)e(use)i(appro)n(ximately)g(2%)f(of)g(a)n(v)m(ailable) i(memory)l(.)75 2291 y fo(3)69 b(TLB-Based)23 b(Reference)e(Bit)g(Em)n(ulatio\ n)75 2392 y fh(Some)f(arc)o(hitectures,)h(like)g(the)f(MIPS)g(arc)o(hitecture) h([Kane)f(88])f(used)i(in)g(the)f(DECstation)f(3100,)75 2449 y(pro)o(vide)g (a)g(TLB)g(whic)o(h)g(requires)h(soft)n(w)n(are)f(re\014ll.)32 b(Because)19 b (the)g(op)q(erating)g(system)f(supplies)j(the)75 2505 y(TLB)i(re\014ll)g(hand\ ler,)i(these)d(arc)o(hitectures)h(presen)o(t)f(considerable)i(\015exibilit)r (y)e(for)f(the)i(op)q(erating)75 2562 y(system)17 b(to)h(tailor)g(TLB)g(re\ \014ll)h(to)e(its)i(needs.)28 b(F)l(or)17 b(example,)i(TLB)g(re\014ll)g(ma)n (y)f(b)r(e)g(used)g(to)f(pro)o(vide)75 2618 y(page-referenced)f(information.) k(W)l(e)15 b(implemen)q(ted)g(this)g(successfully)i(in)f(Mac)n(h,)f(but)g(at) g(the)g(cost)f(of)75 2674 y(increased)i(TLB)g(miss)f(latency)m(.)964 2825 y (6)p eop %%Page: 7 7 bop 146 42 a fh(W)-5 b(e)12 b(exp)q(erimented)f(with)g(ha)o(ving)h(the)f(MIP\ S)g(TLB)g(miss)h(handler)g(em)o(ulate)f(reference)h(bits.)19 b(When)75 98 y (em)o(ulating)d(reference)g(bits,)f(the)g(MIPS)h(pmap)f(mo)q(dule)h(maintains) f(an)g(arra)n(y)g(of)g(reference)h(bits,)f(one)75 154 y(p)r(er)21 b(ph)o(ysic\ al)i(page.)38 b(F)l(or)21 b(e\016ciency)m(,)i(eac)o(h)e(reference)i(bit)e(is) h(stored)f(in)i(a)e(separate)f(b)o(yte)i(and)f(a)75 211 y(non-zero)i(b)o(yte) f(indicates)i(the)e(corresp)r(onding)h(ph)o(ysical)h(page)e(has)g fg(not)h fh (b)q(een)g(referenced.)43 b(The)75 267 y(pmap)19 b(op)q(erations)g fc(pmap_cl\ ear_reference)d fh(and)j fc(pmap_is_referenced)e fh(index)j(into)e(the)h(arra) n(y)75 324 y(and)c(manipulate)g(the)g(appropriate)g(b)o(yte.)k(The)c(TLB)g (miss)g(handler)g(clears)g(the)g(b)o(yte)f(for)g(a)h(ph)o(ysical)75 380 y(pag\ e)j(when)g(loading)h(a)e(mapping)i(for)e(that)g(page)h(into)f(the)h(TLB.)g (This)g(mo)q(di\014cation)h(to)f(the)g(miss)75 437 y(handler)e(increases)g (the)g(latency)f(of)g(servicing)i(a)e(miss)g(from)g(9)f(cycles)j(to)d(16)h (cycles.)146 493 y(With)i(this)i(tec)n(hnique,)h(the)e(MIPS)f(arc)o(hitecture) h(app)r(ears)f(to)g(supp)r(ort)g(page-referenced)i(infor-)75 550 y(mation)14 b (just)f(like)h(arc)n(hitectures)h(with)f(true)g(supp)r(ort)f(in)h(hardw)o(are\ .)19 b(The)14 b(pmap)g(in)o(terface)g(hides)h(the)75 606 y(di\013erence)j(fro\ m)d(the)i(mac)n(hine-indep)5 b(endent)16 b(page-replacement)g(algorithm.)23 b (Consequently)l(,)17 b(with)75 663 y(reference)e(bit)g(em)o(ulation)g(enabled) h(the)e(MIPS)h(arc)o(hitecture)g(can)f(con\014gure)h(a)f(large)h(inactive)f (queue)75 719 y(and)h(enjo)o(y)g(the)h(b)q(ene\014ts)g(of)f(an)g(impro)o(v)n (ed)h(LRU)f(appro)n(ximation.)146 775 y(Ho)n(w)o(ev)o(er,)c(the)g(latency)h (of)e(TLB)i(re\014ll)g(is)g(critical)g(to)f(o)n(v)o(erall)h(system)e(p)r(erfo\ rmance.)18 b(F)l(or)10 b(example,)75 832 y(w)o(e)19 b(coun)o(ted)g(the)g(n)o (um)o(b)q(er)g(of)g(TLB)g(misses)g(generated)g(b)o(y)g(the)g(compilation)i (test)d(of)g(Section)i(2.3,)75 888 y(run)15 b(single-user)h(on)e(a)h(DS3100)e (with)i(16)f(megab)n(ytes)h(of)f(memory)g(and)g(an)h(instrumen)o(ted)g(k)o (ernel.)20 b(In)75 945 y(this)d(en)o(vironmen)o(t,)f(the)g(compilation)h(test) f(has)g(enough)g(a)o(v)m(ailable)i(memory)e(to)f(run)h(to)g(completion)75 1001 y(without)e(page)f(replacemen)q(t.)19 b(On)14 b(a)n(v)o(erage,)f(the)h(compil\ ation)h(test)f(in)o(v)o(ok)n(ed)h(the)f(TLB)g(miss)g(handler)75 1058 y(560,00\ 0)e(times.)20 b(Giv)o(en)15 b(the)g(16.67Mhz)e(clo)r(c)o(k)h(rate)g(of)g(the) h(DS3100)e(and)i(the)f(increase)i(in)f(latency)g(of)75 1114 y(the)g(miss)h (handler,)g(w)n(e)g(can)f(calculate)619 1216 y(560000)9 b fe(\003)h fh(\(16)f fe(\000)h fh(9\))p fa(=)p fh(16)p fa(:)p fh(67Mhz)h(=)i(0)p fa(:)p fh(23s)75 1318 y(the)k(p)r(erformance)f(degradation)i(exp)q(ected)g(for)e(reference)i (bit)g(em)o(ulation.)26 b(T)l(o)17 b(con\014rm)g(this)h(e\013ect,)75 1375 y (w)o(e)h(also)f(timed)i(the)f(compilation)h(test.)31 b(With)19 b(reference)g (bit)h(em)o(ulation,)g(the)f(test)f(completed)i(in)75 1431 y(19.4s.)f(Without) c(reference)h(bit)f(em)o(ulation,)h(the)f(test)g(completed)h(in)g(19.2s.)146 1488 y(Ov)o(erall,)h(reference)g(bit)g(em)o(ulation)g(via)g(TLB)g(misses)g (w)n(as)f(an)h(impro)o(v)n(ement)f(b)q(ecause)h(it)g(let)g(us)75 1544 y(incre\ ase)h(the)g(size)g(of)f(the)h(inactive)f(queue)i(and)f(reduce)g(paging.)27 b (Ho)n(w)o(ev)o(er,)18 b(this)g(solution)g(did)g(not)75 1601 y(apply)h(to)e (other)g(arc)n(hitectures)i(lac)o(king)g(hardw)n(are)f(page-referenced)g(info\ rmation,)g(like)g(the)g(V)-5 b(AX,)75 1657 y(and)15 b(it)h(cost)f(ab)q(out)g (1%)f(in)i(o)o(v)o(erall)g(p)q(erformance)f(when)h(no)f(paging)g(w)o(as)g(o)q (ccurring.)75 1800 y fo(4)69 b(Mac)n(hine-Indep)q(enden)n(t)23 b(Reference)d (Bit)i(Em)n(ulation)75 1902 y fh(The)12 b(Mac)n(h)g(3.0)e(implemen)q(tation)h (of)g(the)g(FIF)o(O)h(with)g(Second)g(Chance)g(page-replacement)f(algorithm) 75 1958 y(uses)h(a)g(mac)n(hine-indep)5 b(endent)11 b(reference)i(bit)f(and)g (reference)h(faults)f(to)f(em)o(ulate)h(hardw)o(are)f(reference)75 2015 y(bit\ s.)20 b(With)14 b(this)h(mo)q(di\014cation,)g(the)f(algorithm)h(op)q(erates)f (similarly)i(whether)e(or)g(not)f(the)i(hardw)n(are)75 2071 y(arc)n(hitecture) g(supplies)g(page-referenced)g(information.)k(Reactiv)o(ation)13 b(fault)h (thrashing)f(is)h(no)g(longer)75 2128 y(a)h(concern.)146 2184 y(The)g(referen\ ce)g(fault)g(mec)o(hanism)h(extends)f(the)g(mac)o(hine-indep)t(endent)g(page) f(structure)h(with)g(a)75 2241 y(reference)k(bit.)31 b(As)18 b(b)r(efore,)h (when)g(the)g(pageout)f(daemon)g(mo)o(v)n(es)h(a)f(page)h(from)f(the)g(activ) o(e)h(queue)75 2297 y(to)h(the)g(inactive)g(queue,)i(it)f(uses)f fc(pmap_clea\ r_reference)e fh(to)h(clear)i(mac)o(hine-dep)s(endent)f(page-)75 2353 y(refer\ enced)d(information,)g(or)f(remo)n(v)o(e)g(all)i(mappings)f(for)e(the)i(page) f(if)h(the)g(pmap)f(mo)q(dule)i(do)q(es)e(not)75 2410 y(supp)r(ort)f(referenc\ e)i(information.)22 b(A)o(t)15 b(this)i(time,)f(the)g(page's)f(mac)o(hine-ind\ ep)t(endent)h(reference)g(bit)75 2466 y(is)i(also)f(cleared.)27 b(When)18 b (a)f(fault)h(on)f(an)g(inactive)g(page)h(o)q(ccurs,)f(the)h(fault)f(handler)i (do)q(es)e fg(not)h fh(acti-)75 2523 y(v)m(ate)g(the)h(page.)28 b(Instead,)19 b(it)g(sets)f(the)g(mac)n(hine-indep)5 b(endent)17 b(reference)i(bit,)h(creat\ es)d(a)h(mapping)75 2579 y(for)e(the)h(page,)g(and)g(leav)n(es)g(the)g(page)g (on)g(the)g(inactive)g(queue.)26 b(These)17 b(faults)g(are)g(kno)n(wn)g(as)g fg(r)n(efer-)75 2636 y(enc)m(e)h(faults)p fh(.)24 b(Before)17 b(the)g(pageout) f(daemon)h(mo)n(v)o(es)g(a)f(page)h(from)f(the)h(inactiv)o(e)g(queue)h(to)e (the)h(free)75 2692 y(queue,)k(it)f(uses)g(the)f(mac)o(hine-indep)t(endent)g (reference)h(bit)g(and)g fc(pmap_is_referenced)d fh(to)i(c)o(hec)o(k)964 2825 y(7)p eop %%Page: 8 8 bop 75 42 a fh(b)r(oth)14 b(mac)n(hine-indep)5 b(endent)14 b(and)h(mac)n(hin\ e-dep)t(enden)o(t)g(sources)f(of)h(page-referenced)g(information.)75 98 y(Fig\ ure)g(5)g(outlines)i(the)e(mo)q(di\014ed)i(algorithm.)225 238 y fc(vm_pageout\ _scan\(\))22 b({)416 294 y(while)h(\(vm_page_free_count)e(<)j(vm_page_free_ta\ rget\))d({)607 351 y(page)i(=)h(dequeue\(vm_page_inactive_)o(queue\);)607 407 y(if)f(\(page->referenced)f(||)702 464 y(pmap_is_referenced\(page->phy)o(s_ad\ dr\))o(\))f({)798 520 y(enqueue\(vm_page_active_q)o(ueue,)g(page\);)607 577 y (})j(else)f({)798 633 y(clean)g(the)g(page)h(if)f(it)h(is)f(dirty;)798 690 y (enqueue\(vm_page_free_que)o(ue,)e(page\);)607 746 y(})416 803 y(})416 915 y (while)i(\(vm_page_inactive_count)e(<)j(vm_page_inactive_target)o(\))d({)607 972 y(page)i(=)h(dequeue\(vm_page_active_qu)o(eue\);)607 1028 y(pmap_clear_re\ ference\(page)o(->phys_)o(addr\);)607 1085 y(page->referenced)d(=)j(FALSE;) 607 1141 y(enqueue\(vm_page_inactive_)o(queue\);)416 1198 y(})225 1254 y(}) 560 1402 y fh(Figure)16 b(5:)j(The)d(Mac)n(h)g(3.0)e(P)o(ageout)g(Daemon)146 1508 y(This)i(mo)q(di\014cation)i(uni\014es)f(the)g(op)q(eration)f(of)g(the)g (page-replacement)g(algorithm)g(on)g(arc)o(hitec-)75 1565 y(tures)g(with)g (and)g(without)g(page-referenced)h(supp)r(ort.)k(In)c(b)q(oth)f(cases,)f(refe\ rences)i(to)e(pages)h(on)g(the)75 1621 y(inactive)e(queue)h(leav)n(e)g(the)f (page)g(on)h(the)f(queue)h(until)g(the)f(pageout)g(daemon)g(notices)h(that)f (the)g(page)75 1678 y(has)d(b)r(een)h(referenced.)20 b(In)12 b(b)r(oth)f(case\ s,)h(pages)f(on)h(the)g(inactiv)o(e)g(queue)h(ma)n(y)f(b)q(e)g(mapp)q(ed)g (into)f(address)75 1734 y(spaces.)20 b(Therefore,)13 b(the)h(reference)h(faul\ t)f(mec)o(hanism)g(eliminates)i(the)e(need)h(to)e(tune)h(the)g(algorithm)75 1791 y(for)g(di\013erent)g(arc)n(hitectures.)21 b(Mac)n(hine-indep)t(endent) 14 b(co)r(de)g(can)h(con\014gure)g(the)g(size)g(of)f(the)h(inactive)75 1847 y (queue.)146 1903 y(Because)h(pages)g(on)g(the)h(inactive)f(queue)h(can)f(b)r (e)g(mapp)q(ed)h(into)e(address)h(spaces,)h(arc)n(hitectures)75 1960 y(withou\ t)j(page-referenced)h(supp)r(ort)e(no)h(longer)g(su\013er)g(from)f(reactiv)n (ation)h(fault)g(thrashing)g(when)75 2016 y(the)15 b(inactive)g(queue)h(is)f (large.)20 b(If)15 b(the)g(system's)f(w)o(orking)h(set)g(exceeds)h(the)f(size) g(of)g(the)g(activ)o(e)g(queue)75 2073 y(but)g(\014ts)f(in)h(memory)l(,)f(the\ n)h(the)f(system)g(reac)o(hes)g(a)g(quiescen)q(t)g(state)f(in)j(whic)o(h)f (most)f(of)f(the)i(inactive)75 2129 y(pages)g(are)g(mark)n(ed)h(as)e(referenc\ ed)j(and)e(are)g(mapp)q(ed.)146 2186 y(Allo)o(wing)21 b(inactive)f(pages)g (to)g(b)q(e)g(mapp)r(ed)g(in)h(e\013ect)f(allows)g(the)g(size)h(of)f(the)g (inactive)g(queue)75 2242 y(to)h(c)o(hange)i(dynamically)n(.)40 b(When)23 b (the)f(system)g(is)h(paging)f(hea)o(vily)m(,)i(few)e(pages)g(on)g(the)g(inact\ ive)75 2299 y(queue)g(are)e(referenced.)38 b(When)21 b(the)g(paging)g(rate)f (drops)h(b)q(ecause)h(the)f(system's)e(w)o(orking)i(set)f(is)75 2355 y(reside\ nt,)g(then)f(most)g(pages)g(in)h(the)g(inactiv)o(e)g(queue)g(b)r(ecome)f(refe\ renced)h(and)g(the)f(e\013ective)g(size)75 2412 y(of)g(the)h(inactive)g(queue) h(decreases.)34 b(The)20 b(adv)m(an)o(tage)f(of)g(this)h(metho)q(d)g(o)o(v)n (er)g(explicitly)j(adjusting)75 2468 y fc(vm_page_inactive_target)15 b fh(for) j(di\013erence)h(p)r(erformance)f(regimes)h(is)f(that)g(the)g(c)o(hanges)h (in)g(the)75 2524 y(comp)q(osition)d(of)f(the)g(inactive)g(queue)h(happ)r(en) g(automatically)l(.)964 2825 y(8)p eop %%Page: 9 9 bop 75 42 a fo(5)69 b(P)n(age)23 b(Replacemen)n(t)d(and)k(External)e(Memory) h(Managemen)n(t)75 143 y fh(The)18 b(pageout)g(daemon)g(faces)g(t)o(w)n(o)g (related)h(problems,)g(a)o(v)n(oiding)h(deadlo)r(c)o(ks)e(and)g(\015o)o(w)g (con)o(trol,)g(in)75 199 y(addition)k(to)f(its)h(primary)f(problem)h(of)f(c)o (ho)q(osing)g(pages)g(to)g(remo)n(v)o(e)h(from)e(main)i(memory)l(.)38 b(The) 75 256 y(original)22 b(page-replacement)e(implemen)q(tation)g(pro)q(ceeded)i (the)f(implemen)q(tation)f(of)h(the)g(external)75 312 y(memory)13 b(manager)g (\(XMM\))f(interface)h([Rashid)i(et)e(al.)20 b(87,)13 b(Y)l(oung)g(89],)g(and) h(this)g(greatly)f(simpli\014ed)75 369 y(the)18 b(pageout)f(daemon.)26 b(The) 18 b(Mac)n(h)g(3.0)f(pageout)g(daemon)g(uses)h(sev)o(eral)g(strategies)f(to)g (cop)q(e)h(with)75 425 y(slo)o(w)d(or)g(unco)q(op)r(erativ)n(e)h(external)f (memory)g(managers.)146 482 y(When)k(the)h(original)g(pageout)f(daemon)h(clea\ ned)h(dirt)o(y)e(pages,)h(it)g(copied)g(them)g(in)o(to)f(the)h(I/O)75 538 y (system's)e(bu\013er)g(cac)o(he.)31 b(The)19 b(size)g(of)f(the)h(cac)o(he)g (automatically)g(limited)i(the)d(rate)g(at)g(which)h(the)75 595 y(daemon)f (could)g(clean)h(pages,)e(b)r(ecause)h(once)g(it)g(\014lled)h(with)f(data)f (w)o(aiting)h(to)f(b)q(e)h(written)g(to)f(disk,)75 651 y(the)e(daemon)g(w)o (ould)h(start)e(w)o(aiting)h(for)g(disk)h(writes)f(to)g(complete)h(and)f(free) g(bu\013ers.)146 708 y(In)23 b(con)o(trast,)g(the)g(Mac)n(h)g(3.0)f(pageout)g (daemon)h(sends)g(dirt)o(y)g(pages)f(to)h(memory)f(managers)75 764 y(in)g fc (memory_object_data_writ)o(e)c fh(messages.)36 b(Because)21 b(the)g(XMM)f(int\ erface)g(is)i(async)n(hronous,)75 820 y(the)17 b(pageout)f(daemon)h(do)r(es)g (not)f(kno)o(w)g(when)i(a)e(memory)h(manager)f(has)h(completed)h(pro)q(cessin\ g)f(a)75 877 y fc(memory_object_data_write)p fh(.)24 b(If)18 b(the)g(pageout) f(daemon)h(encounters)f(a)h(long)g(sequence)h(of)e(dirt)o(y)75 933 y(pages)11 b(on)g(the)h(inactive)f(queue)h(and)g(mak)n(es)g(no)f(attempt)f(at)h(\015o)o (w)g(con)o(trol,)g(it)h(can)f(generate)g(arbitrarily)75 990 y(long)g(queues)g (of)g fc(memory_object_data_writ)o(e)d fh(messages)i(w)o(aiting)h(in)g(the)g (IPC)g(system)f([Dra)n(v)o(es)g(90].)75 1046 y(The)15 b(normal)f(queue-limiti\ ng)k(\015o)n(w)d(con)n(trol)g(mec)o(hanisms)g(of)f(the)g(IPC)h(system)f(are)g (not)g(appropriate)75 1103 y(\(and)k(are)h(not)f(applied\))i(b)r(ecause)f(the) g(pageout)f(daemon)g(can't)g(w)o(ait)h(for)f(a)g(p)q(oten)o(tially)i(buggy)e (or)75 1159 y(malicious)f(memory)d(manager)h(to)f(tak)o(e)h(some)g(action.) 146 1216 y(The)k(Mac)n(h)g(k)o(ernel)h(do)q(es)f(rely)g(on)g(a)g(distinguishe\ d)i(memory)d(manager,)h(the)g(default)h(memory)75 1272 y(manager)15 b([Golub) g(&)h(Dra)n(v)n(es)g(91],)e(to)g(op)r(erate)h(correctly)l(.)20 b(The)c(defaul\ t)g(memory)f(manager)f(services)75 1329 y(memory)i(ob)s(jects)g(created)h(whe\ n)g(a)f(pro)q(cess)h(allo)r(cates)g(temp)q(orary)e(memory)l(,)i(not)f(managed) g(b)o(y)h(an)75 1385 y(explicitly)g(sp)q(eci\014ed)f(memory)d(manager.)19 b (The)14 b(default)g(memory)g(manager)f(also)h(acts)f(as)h(the)g(\\pager)75 1441 y(of)20 b(last)g(resort,")g(which)g(cleans)h(the)g(dirt)o(y)f(pages)g (that)f(unprivileged)k(memory)d(managers)g(fail)h(to)75 1498 y(pro)q(cess.) 146 1554 y(The)13 b(pageout)g(daemon)h(and)g(the)f(default)h(memory)f(manager) g(on)h(o)q(ccasion)g(m)n(ust)g(allo)r(cate)f(mem-)75 1611 y(ory)l(,)26 b(cons\ uming)g(free)e(pages,)i(while)g(they)f(op)q(erate)f(to)g(create)h(more)f(free) g(pages.)48 b(F)l(or)24 b(exam-)75 1667 y(ple,)d(the)e(pageout)g(daemon)g(all\ o)r(cates)g(message)g(bu\013ers)g(for)g fc(memory_object_data_write)d fh(mes-) 75 1724 y(sages.)22 b(T)l(o)16 b(prev)o(en)o(t)g(a)g(deadlo)r(c)o(k)g(when)h (there)f(are)g(no)g(free)g(pages,)g(the)g(k)o(ernel)h(main)o(tains)f(a)g(rese\ rv)o(e)75 1780 y(of)22 b(free)g(pages)g(and)h(only)g(the)f(pageout)g(daemon)g (and)h(default)f(memory)g(manager)g(can)g(allo)r(cate)75 1837 y(free)f(pages) g(from)g(the)g(reserv)o(e.)38 b(If)22 b(the)f(pageout)g(daemon)g(fails)h(at)f (\015o)o(w)g(con)o(trol)g(and)g(generates)75 1893 y fc(memory_object_data_wri\ te)15 b fh(messages)j(more)f(quickly)i(than)f(they)g(are)g(pro)q(cessed,)i (then)e(it)h(can)75 1950 y(consume)d(the)f(free)g(page)g(reserv)o(e)g(and)h (deadlo)r(c)o(k.)146 1999 y(The)i(Mac)n(h)g(3.0)f(k)o(ernel)i(uses)g(three)f (thresholds)g(to)g(prev)o(en)o(t)f(the)i(free)f(page)g(queue)g(from)g(b)q(ein\ g)75 2049 y(exhausted:)202 2124 y fb(vm_page_free_reserv)o(ed)375 2174 y fj (Belo)o(w)c(this)g(lev)n(el,)g(only)f(privileged)g(threads)i(can)f(allocate)h (free)f(pages.)202 2248 y fb(vm_pageout_reserved)o(_inte)o(rnal)375 2298 y fj (Belo)o(w)f(this)h(lev)o(el,)f(the)h(pageout)f(daemon)f(no)h(longer)h(exp)q (ects)h(memory)c(managers)375 2348 y(other)19 b(than)g(the)g(default)f(memory) f(manager)g(to)h(function.)32 b(The)19 b(pageout)g(dae-)375 2398 y(mon)8 b (cleans)j(pages)f(asso)r(ciated)g(with)g(other)g(memory)e(managers)h(b)n(y)h (double-paging)375 2448 y(them,)i(or)h(sending)h(them)e(\014rst)i(to)f(their) h(real)f(memory)d(manager)i(and)h(then)h(imme-)375 2497 y(diately)f(resending) i(them)e(to)h(the)g(default)g(memory)d(manager.)202 2572 y fb(vm_pageout_rese\ rved)o(_real)o(ly)375 2622 y fj(Belo)o(w)19 b(this)g(lev)n(el,)h(the)f(pageou\ t)g(daemon)f(stops)h(op)q(erating)g(and)f(w)o(aits)h(for)f(the)375 2672 y(def\ ault)c(memory)d(manager)h(to)i(catch)g(up.)964 2825 y fh(9)p eop %%Page: 10 10 bop 75 42 a fh(Arti\014cially)23 b(constructed)d(paging)h(test)f(programs)g (can)g(drive)g(the)h(size)h(of)e(free)g(queue)i(b)q(elow)e(the)75 98 y fc(vm_\ pageout_reserved_really)7 b fh(threshold,)k(but)f(the)h fc(vm_pageout_reserve\ d_int)o(ernal)c fh(thresh-)75 154 y(old)16 b(is)f(rarely)h(exceeded)g(in)g (practice.)146 211 y(The)d(Mac)n(h)h(3.0)e(pageout)g(daemon)i(uses)f(t)n(w)o (o)g(strategies)f(for)h(\015o)o(w)g(con)o(trol,)g(to)f(con)o(trol)h(separatel\ y)75 267 y(the)g(rate)g(at)f(which)h(dirt)o(y)g(pages)g(are)g(sen)o(t)g(to)f (the)h(default)h(memory)f(manager)f(and)h(to)g(other)g(memory)75 324 y(manage\ rs.)19 b(Because)c(of)g(the)f(constrain)o(ts)h(placed)h(on)e(the)h(default)h (memory)e(manager,)f(that)i(it)g(m)n(ust)75 380 y(b)r(e)d(correct)g(and)g(it) g(m)o(ust)g(free)g(pages)g(after)g(cleaning)i(them,)e(the)g(pageout)g(daemon) g(can)h(use)f(a)g(reliable)75 437 y(strategy)18 b(with)i(it.)33 b(The)19 b (strategy)g(emplo)o(y)o(ed)h(with)f(other)g(memory)g(managers)g(is)h(only)g (heuristic,)75 493 y(but)i(the)g fc(vm_pageout_reserved_inter)o(nal)d fh(thre\ shold)j(describ)s(ed)g(earlier)h(prev)o(en)o(ts)e(this)i(from)75 550 y(compro\ mising)16 b(system)f(correctness.)146 606 y(T)l(o)20 b(a)o(v)n(oid)i(\015o)q (o)q(ding)g(the)f(default)g(memory)f(manager,)i(the)f(k)n(ernel)h(k)o(eeps)f (a)g(\\laundry)g(count")75 663 y(of)d(ho)o(w)g(man)o(y)g(pages)g(the)h(defaul\ t)g(memory)f(manager)g(has)g(not)g(y)o(et)g(cleaned.)31 b(P)o(ages)18 b(sen)o (t)g(to)g(the)75 719 y(default)e(memory)f(manager)f(are)h(mark)n(ed)h(with)g (a)f(\\laundry)h(bit,")f(and)h(when)f(pages)g(so)g(mark)o(ed)g(are)75 775 y (returned)g(to)e(the)i(free)f(queue,)h(the)g(laundry)g(coun)o(t)f(is)h(decrem\ en)o(ted.)20 b(The)15 b(pageout)e(daemon)i(pauses)75 832 y(to)h(let)g(the)g (default)h(memory)f(manager)f(catc)o(h)h(up)h(when)f(the)h(laundry)g(coun)o (t)f(exceeds)h(a)f(threshold,)75 888 y fc(vm_pageout_burst_max)p fh(.)146 945 y(T)l(o)10 b(a)n(v)o(oid)i(\015o)q(o)q(ding)f(other)g(memory)f(managers,)g (the)h(pageout)f(daemon)h(also)g(pauses)g(after)f(sending)75 1001 y(out)j fc (vm_pageout_burst_max)e fh(dirt)o(y)j(pages.)19 b(Because)c(the)f(k)n(ernel)h (do)r(es)e(not)h(ha)o(v)n(e)g(an)g(equiv)n(alent)f(of)75 1058 y(the)k(laundry) g(coun)o(t)f(for)g(these)h(memory)e(managers,)h(the)g(pageout)g(daemon)h(m)n (ust)g(assume)f(that)g(its)75 1114 y(pause)11 b(ga)n(v)o(e)g(the)g(memory)g (managers)f(time)h(to)f(pro)r(cess)h(the)g fc(memory_object_data_write)c fh (requests.)146 1171 y(The)j(t)n(w)o(o)g(\015o)o(w)g(con)o(trol)g(strategies)f (w)o(ork)h(b)q(est)g(when)h(the)f(pageout)g(daemon's)g(pauses)g(are)g(prop)q (erly)75 1227 y(tuned.)19 b(Instead)12 b(of)f(requiring)i(mac)o(hine-dep)s (endent)e(tuning,)i(the)f(pageout)f(daemon)g(tunes)h(the)g(pause)75 1284 y (interv)m(al)19 b(dynamically)n(.)31 b(If)19 b(the)g(pageout)g(daemon)f(w)o (ak)n(es)h(from)g(a)f(pause)h(and)g(the)g(laundry)h(coun)o(t)75 1340 y(is)d (still)h(high,)g(the)f(pageout)f(daemon)h(increases)g(the)g(pause)g(interv)m (al.)25 b(If)17 b(the)g(laundry)g(coun)o(t)g(is)g(lo)o(w)75 1396 y(after)d (eac)o(h)i(of)e(sev)o(eral)i(consecutive)f(pauses,)g(the)g(pageout)g(daemon)g (decreases)h(the)f(pause)h(in)o(terv)m(al.)75 1540 y fo(6)69 b(Related)21 b (W)-6 b(ork)75 1641 y fh(Other)23 b(op)q(erating)f(systems)g(for)g(the)h(V)-5 b(AX)23 b(arc)n(hitecture,)i(notably)e(VMS)f(and)h(BSD)f(Unix,)j(p)r(er-)75 1698 y(form)14 b(page-replacement)g(without)g(the)g(b)r(ene\014t)h(of)e(hardw) o(are)h(page-referenced)h(information.)20 b(Some)75 1754 y(researc)o(hers)15 b (ha)o(v)o(e)g(tak)o(en)g(a)h(di\013eren)o(t)f(approac)o(h)h(to)f(page)g(repla\ cement)g(in)i(Mac)n(h)f(and)f(ha)o(v)o(e)h(exp)q(eri-)75 1810 y(men)o(ted)f (with)h(application-lev)q(el)g(con)o(trol)f(o)o(v)n(er)h(page-replacement)f (decisions.)146 1867 y(The)21 b(V)-5 b(AX/VMS)22 b(op)q(erating)g(system[Gold\ en)n(b)r(erg)f(&)h(Kenah)g(91,)f(T)l(urner)h(&)g(Levy)g(81])f(uses)75 1923 y (p)r(er-pro)q(cess)e(w)n(orking)g(sets)g(with)g(global)g(free)g(and)g(mo)q (di\014ed)h(lists)f(to)g(con)n(trol)g(page)g(replacement.)75 1980 y(Normal)g (FIF)o(O)g(page)h(replacement)f(o)q(ccurs)g(within)i(a)e(w)n(orking)h(set,)g (eac)o(h)f(of)g(which)g(b)r(eha)o(v)n(es)h(like)75 2036 y(Mac)n(h's)i(activ)o (e)h(queue.)42 b(The)23 b(global)g(free)f(and)g(mo)q(di\014ed)i(lists)f(cac)o (he)g(pages)f(not)g(mapp)q(ed)h(into)75 2093 y(pro)q(cesses.)37 b(P)o(age)20 b (faults)h(which)g(are)f(satis\014ed)i(from)e(the)h(free)g(and)g(mo)q(di\014ed) h(lists)g(without)f(I/O)75 2149 y(are)d(kno)n(wn)g(as)g fg(soft)h(p)n(age)g (faults)p fh(.)28 b(Lik)o(e)19 b(Mac)n(h's)f(reactiv)m(ation)g(faults,)h(they) f(ameliorate)g(the)g(FIF)o(O)75 2206 y(replacement)d(within)h(w)n(orking)g (sets)e(to)h(pro)q(duce)h(an)e(LRU)h(appro)o(ximation.)20 b(They)15 b(also)g (su\013er)g(from)75 2262 y(the)g(same)g(p)q(erformance)g(tuning)h(dilemma.)21 b(F)l(or)14 b(example,)i([Lazo)n(wsk)n(a)e(79])g(found)i(that)e(the)h(default) 75 2319 y(size)h(for)f(the)g(free)g(and)h(modi\014ed)h(lists)f(w)o(as)f(too)g (small)h(for)f(memory-p)q(o)q(or)f(environmen)o(ts.)146 2375 y(The)f(BSD)g (Unix)i(op)q(erating)e(system)g(uses)h(a)e(clo)r(c)o(k)h(algorithm)h([Babaogl\ u)f(&)g(Jo)o(y)g(81].)19 b(The)13 b(clo)r(c)o(k)75 2431 y(hand)18 b(cycles)h (around)f(main)g(memory)l(,)g(clearing)h(soft)n(w)n(are)f(reference)g(bits)h (and)f(unmapping)h(pages.)75 2488 y(F)l(aults)14 b(on)g(unmapp)r(ed)h(pages,) f(like)g(Mac)n(h's)g(reference)h(faults,)f(set)g(the)g(soft)n(w)o(are)g(refer\ ence)h(bit.)20 b(The)75 2544 y(clo)r(c)o(k)c(algorithm)f(reclaims)i(unreferen\ ced)g(pages)f(found)g(b)o(y)g(the)g(hand.)22 b(Unlike)16 b(Mac)o(h's)f(algori\ thm,)75 2601 y(the)j(BSD)g(algorithm)g(su\013ers)g(from)f(scalabilit)q(y)h (problems,)g(b)r(ecause)g(the)g(clo)r(c)o(k)g(hand)g(m)o(ust)g(sw)n(eep)75 2657 y(across)d(the)g(mac)o(hine's)h(en)o(tire)g(ph)o(ysical)h(memory)l(.)j (It)c(is)g(also)f(di\016cult)i(to)e(tune)h(prop)q(erly)g(the)g(sp)q(eed)952 2825 y(10)p eop %%Page: 11 11 bop 75 42 a fh(of)15 b(the)g(clo)r(c)o(k)g(hand.)146 98 y(Some)20 b(researc) o(hers)g([McNamee)g(&)h(Armstrong)e(90])h(ha)n(v)o(e)h(tak)n(en)f(the)h(appro\ ac)n(h)g(of)f(pro)o(viding)75 154 y(con)o(trol)14 b(o)n(v)o(er)f(page-replace\ men)q(t)g(to)g(the)h(application.)21 b(This)14 b(is)h(a)e(promising)i(approac) n(h)f(for)f(applica-)75 211 y(tions)h(like)h(Lisp,)g(ML,)f(and)g(databases,)f (but)i(it)f(lea)o(v)o(es)g(op)r(en)g(the)h(question)f(of)g(a)g(default)h(mec) o(hanism.)75 267 y(Mac)n(h's)j(FIF)n(O)g(with)g(Second)g(Chance)g(algorithm)f (can)h(easily)g(accommo)q(date)f(simple)i(application-)75 324 y(level)f(hints) f(ab)r(out)g(the)h(relativ)o(e)g(w)o(orth)f(of)g(pages.)28 b(P)n(ages)18 b (deemed)g(less)h(v)m(aluable)h(can)d(b)r(e)h(forcibly)75 380 y(mo)n(v)o(ed)c (from)f(the)g(activ)o(e)h(queue)g(to)f(the)g(inactive)h(queue)g(to)f(mak)n (e)h(them)f(more)g(likely)h(candidates)h(for)75 437 y(replacement.)75 580 y fo (7)69 b(Conclusions)75 681 y fh(The)17 b(Mac)n(h)g(k)n(ernel)h(uses)f(a)f(FIF) n(O)h(with)g(Second)g(Chance)g(page-replacement)f(algorithm.)24 b(W)l(e)16 b (ha)o(v)o(e)75 738 y(exp)r(erimen)o(ted)21 b(with)f(sev)o(eral)g(approac)o (hes)g(to)f(pro)o(viding)i(the)f(page-referenced)h(information)g(that)75 794 y (the)g(algorithm)g(needs)h(to)f(appro)n(ximate)g(LRU)g(b)r(eha)o(vior.)37 b (An)22 b(approac)n(h)g(based)f(on)g(a)g(mac)o(hine-)75 851 y(indep)s(endent)f (reference)h(bit)g(and)f(reference)i(faults)e(outp)q(erforms)g(Mac)n(h)h(2.5'\ s)e(reactiv)m(ation)i(fault)75 907 y(tec)o(hnique)c(and)f(reference)g(bits)g (based)g(on)g(soft)n(w)n(are)g(TLB)g(re\014ll.)23 b(The)16 b(FIF)n(O)g(with)g (Second)h(Chance)75 964 y(algorithm)e(can)h(accommodate)f(the)g(requirements) g(of)g(external)h(memory)e(managemen)o(t.)75 1107 y fo(Ac)n(kno)n(wledgemen)n (ts)75 1208 y fh(Av)n(adis)d(T)l(ev)m(anian)g(and)g(Mic)o(hael)g(Y)m(oung)f (\014rst)g(implemen)q(ted)g(page-replacemen)q(t)g(in)h(the)g(Mac)n(h)g(k)n (ernel.)75 1265 y(Alessandro)g(F)l(orin)f(implemen)q(ted)g(the)h(TLB-based)g (reference)g(bit)f(em)o(ulation)h(describ)s(ed)f(in)i(Section)f(3.)75 1321 y (Mic)o(hael)j(Y)l(oung)f(implemented)g(preliminary)i(v)o(ersions)e(of)f(the)h (mec)o(hanisms)h(describ)r(ed)f(in)h(Section)g(5.)75 1464 y fo(References)75 1566 y fh([Babaoglu)h(&)h(Jo)n(y)f(81])22 b(Babaoglu,)e(O.)f(and)g(Jo)o(y)l (,)g(W.)31 b(Con)n(v)o(erting)19 b(a)g(Sw)o(ap-Based)g(System)g(to)f(do)273 1622 y(P)o(aging)g(in)h(an)f(Arc)o(hitecture)h(Lac)o(king)f(P)o(age-Reference\ d)i(Bits.)28 b(In)19 b fg(Pr)n(o)n(c)m(e)n(e)m(dings)g(of)g(the)273 1679 y (8th)h(A)n(CM)e(Symp)n(osium)h(on)g(Op)n(er)n(ating)f(Systems)g(Principles)p fh(,)f(pages)h(78{86,)g(Decem)n(b)r(er)273 1735 y(1981.)75 1829 y([Belady)e (66])22 b(Belady)m(,)14 b(L.)h(A.)j(A)d(Study)g(of)f(Replacemen)q(t)g(Algorit\ hms)h(for)f(a)g(Virtual-Storage)g(Com-)273 1886 y(puter.)20 b fg(IBM)15 b(Sys\ tems)h(Journal)p fh(,)f(5\(2\):78{101)o(,)d(1966.)75 1979 y([DEC)i(79])22 b (Digital)16 b(Equipment)f(Corp)q(oration.)k fg(V)-5 b(AX-11)17 b(A)n(r)n(chit\ e)n(ctur)n(e)f(Handb)n(o)n(ok)p fh(,)f(1979.)75 2073 y([Denning)h(68])22 b (Denning,)16 b(P)l(.)g(J.)22 b(The)16 b(W)-5 b(orking)16 b(Set)g(Mo)q(del)h (for)e(Program)f(Beha)o(vior.)22 b fg(Communic)n(a-)273 2130 y(tions)16 b(of) g(the)h(A)n(CM)p fh(,)d(11\(5\):323{333,)d(Ma)n(y)16 b(1968.)75 2223 y([Dra)n (v)n(es)g(90])21 b(Dra)n(v)o(es,)c(R.)g(P)l(.)25 b(A)16 b(Revised)j(IPC)e(In) o(terface.)24 b(In)18 b fg(Pr)m(o)n(c)n(e)m(e)n(dings)f(of)h(the)g(USENIX)e (Mach)273 2280 y(Workshop)p fh(,)g(pages)f(101{121,)e(Octob)q(er)i(1990.)75 2374 y([Golden)o(b)r(erg)f(&)i(Kenah)g(91])22 b(Golden)o(b)r(erg,)c(R.)g(E.)g (and)h(Kenah,)g(L.)f(J.)30 b fg(V)-5 b(AX/VMS)18 b(Internals)f(and)273 2430 y (Data)g(Structur)o(es:)j(V)l(ersion)c(5.2)p fh(.)k(Digital)c(Press,)f(1991.) 75 2524 y([Golub)g(&)h(Dra)n(v)o(es)f(91])22 b(Golub,)13 b(D.)f(B.)g(and)g (Dra)n(v)o(es,)h(R.)f(P)m(.)j(Mo)n(ving)e(the)g(Default)f(Memory)g(Manager) 273 2580 y(out)g(of)h(the)g(Mac)n(h)g(Kernel.)18 b(In)13 b fg(Pr)n(o)n(c)n (e)m(e)n(dings)g(of)h(the)h(Se)m(c)m(ond)g(USENIX)d(Mach)i(Symp)n(osium)p fh (,)273 2637 y(No)o(v)n(em)o(b)r(er)h(1991.)j(This)e(issue.)952 2825 y(11)p eop %%Page: 12 12 bop 75 42 a fh([IBM)15 b(88])22 b(In)o(ternational)12 b(Business)i(Mac)n(hin\ es,)f(Austin,)g(T)l(exas.)h fg(IBM)f(R)m(T)f(PC)h(Har)n(dwar)n(e)g(T)l(e)n (chnic)m(al)273 98 y(R)n(efer)m(enc)m(e)k(V)l(olume)g(1)p fh(,)e(third)g(edit\ ion,)h(1988.)75 192 y([Kane)f(88])22 b(Kane,)15 b(G.)20 b fg(MIPS)15 b(RISC)g (A)n(r)n(chite)n(ctur)n(e)p fh(.)20 b(Pren)o(tice-Hall,)d(Englew)o(o)q(o)q (d)e(Cli\013s,)h(NJ,)f(1988.)75 286 y([Lazo)n(wsk)n(a)g(79])21 b(Lazo)o(wsk)m (a,)k(E.)e(D.)43 b(The)23 b(Benchmarking,)i(T)l(uning)f(and)g(Analytic)g(Mo)q (deling)g(of)273 342 y(V)-5 b(AX/VMS.)33 b(In)21 b fg(Pap)n(ers)f(Pr)m(esente) m(d)h(at)f(the)h(1979)g(Confer)m(enc)m(e)g(on)f(Simulation,)h(Me)n(a-)273 399 y(sur)n(ement)16 b(and)g(Mo)n(deling)f(of)i(Computer)g(Systems)p fh(,)c(pages) i(57{64,)f(August)h(1979.)75 492 y([McNamee)g(&)g(Armstrong)f(90])22 b(McName\ e,)13 b(D.)g(and)g(Armstrong,)f(K.)k(Extending)e(the)g(Mac)n(h)f(Exter-)273 549 y(nal)18 b(P)o(ager)f(Interface)g(to)g(Accommo)q(date)h(User-Lev)o(el)h (P)o(age)e(Replacemen)q(t)g(P)o(olicies.)29 b(In)273 605 y fg(Pr)n(o)n(c)m (e)n(e)m(dings)16 b(of)g(the)h(USENIX)d(Mach)j(Workshop)p fh(,)e(pages)g(17{2\ 9,)f(Octob)q(er)h(1990.)75 699 y([Rashid)h(et)f(al.)g(87])22 b(Rashid,)d(R.,) e(T)l(ev)n(anian,)h(Jr.,)f(A.,)h(Y)l(oung,)f(M.,)g(Golub,)h(D.,)f(Baron,)g (R.,)h(Blac)o(k,)273 756 y(D.,)f(Bolosky)l(,)h(W.,)e(and)i(Chew,)f(J.)27 b (Mac)n(hine-Indep)t(endent)17 b(Virtual)h(Memory)f(Manage-)273 812 y(men)o (t)c(for)f(P)o(aged)g(Unipro)r(cessor)h(and)g(Multipro)r(cessor)g(Arc)o(hitec\ tures.)k(In)c fg(Pr)n(o)n(c)m(e)n(e)m(dings)h(of)273 868 y(the)20 b(Se)m(c)m (ond)g(International)e(Confer)m(enc)m(e)h(on)g(A)o(r)n(chite)n(ctur)n(al)g (Supp)n(ort)h(for)g(Pr)m(o)n(gr)n(amming)273 925 y(L)m(anguages)c(and)g(Op)n (er)n(ating)g(Systems)p fh(,)e(pages)h(31{39,)e(Octob)r(er)i(1987.)75 1019 y ([T)l(ev)m(anian)h(87])22 b(T)l(ev)n(anian,)13 b(Jr.,)f(A.)k fg(A)o(r)n(chite) m(ctur)o(e-Indep)m(endent)d(Virtual)h(Memory)g(Management)g(for)273 1075 y (Par)n(al)r(lel)j(and)h(Distribute)n(d)g(Envir)m(onments:)23 b(The)18 b(Mach) g(Appr)n(o)n(ach)p fh(.)25 b(PhD)17 b(dissertation,)273 1132 y(Carnegie)f(Mel\ lon)g(Univ)o(ersit)o(y)m(,)e(Decem)o(b)r(er)h(1987.)75 1225 y([T)l(urner)g (&)h(Levy)f(81])22 b(T)l(urner,)15 b(R.)g(and)h(Levy)l(,)f(H.)20 b(Segmen)o (ted)15 b(FIF)o(O)g(P)o(age)f(Replacemen)q(t.)19 b(In)d fg(Pr)n(o-)273 1282 y (c)n(e)m(e)n(dings)f(of)i(the)g(Confer)m(enc)m(e)f(on)g(Me)n(asur)n(ement)g (and)g(Mo)n(deling)g(of)g(Computer)h(Systems)p fh(,)273 1338 y(pages)e(48{51,) e(Septemb)q(er)i(1981.)75 1432 y([Y)l(oung)g(89])22 b(Y)l(oung,)h(M.)e(W.)39 b fg(Exp)m(orting)23 b(a)f(User)g(Interfac)m(e)g(to)g(Memory)h(Management)e(fr) n(om)i(a)273 1489 y(Communic)n(ation-Oriente)m(d)18 b(Op)n(er)n(ating)f(Syste\ m)p fh(.)25 b(PhD)17 b(dissertation,)h(Carnegie)f(Mellon)273 1545 y(Universit) o(y)l(,)e(No)n(v)o(em)o(b)q(er)g(1989.)952 2825 y(12)p eop %%Trailer end %%EOF