%!PS (but not EPSF; comments have been disabled) %DVIPSCommandLine: dvips 2strejilevich.dvi -o %DVIPSParameters: dpi=600, compressed, comments removed %DVIPSSource: TeX output 1998.05.06:1524 /TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N /X{S N}B /TR{translate}N /isls false N /vsize 11 72 mul N /hsize 8.5 72 mul N /landplus90{false}def /@rigin{isls{[0 landplus90{1 -1}{-1 1} ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR[matrix currentmatrix{dup dup round sub abs 0.00001 lt{round}if} forall round exch round exch]setmatrix}N /@landscape{/isls true N}B /@manualfeed{statusdict /manualfeed true put}B /@copies{/#copies X}B /FMat[1 0 0 -1 0 0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{ /nn 8 dict N nn begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N string /base X array /BitMaps X /BuildChar{CharBuilder}N /Encoding IE N end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{ /sf 1 N /fntrx FMat N df-tail}B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0] N df-tail}B /E{pop nn dup definefont setfont}B /ch-width{ch-data dup length 5 sub get}B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{ 128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data dup type /stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N /rc 0 N /gp 0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup /base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx 0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff .1 sub]/id ch-image N /rw ch-width 7 add 8 idiv string N /rc 0 N /gp 0 N /cp 0 N{rc 0 ne{rc 1 sub /rc X rw}{G}ifelse}imagemask restore}B /G{{id gp get /gp gp 1 add N dup 18 mod S 18 idiv pl S get exec}loop}B /adv{cp add /cp X}B /chg{rw cp id gp 4 index getinterval putinterval dup gp add /gp X adv}B /nd{/cp 0 N rw exit}B /lsh{rw cp 2 copy get dup 0 eq{pop 1}{ dup 255 eq{pop 254}{dup dup add 255 and S 1 and or}ifelse}ifelse put 1 adv}B /rsh{rw cp 2 copy get dup 0 eq{pop 128}{dup 255 eq{pop 127}{dup 2 idiv S 128 and or}ifelse}ifelse put 1 adv}B /clr{rw cp 2 index string putinterval adv}B /set{rw cp fillstr 0 4 index getinterval putinterval adv}B /fillstr 18 string 0 1 17{2 copy 255 put pop}for N /pl[{adv 1 chg} {adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{ adv rsh nd}{1 add adv}{/rc X nd}{1 add set}{1 add clr}{adv 2 chg}{adv 2 chg nd}{pop nd}]dup{bind pop}forall N /D{/cc X dup type /stringtype ne{] }if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N}B /I{ cc 1 add D}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin 0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore userdict /eop-hook known{eop-hook}if showpage}N /@start{userdict /start-hook known{start-hook}if pop /VResolution X /Resolution X 1000 div /DVImag X /IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for 65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0 0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V {}B /RV statusdict begin /product where{pop product dup length 7 ge{0 7 getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false} ifelse}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale rulex ruley false RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR rulex ruley scale 1 1 false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave newpath transform round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail {dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{S p tail}B /c{-4 M} B /d{-3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{3 M}B /k{ 4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p -1 w}B /q{ p 1 w}B /r{p 2 w}B /s{p 3 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{3 2 roll p a}B /bos{/SS save N}B /eos{SS restore}B end TeXDict begin 40258431 52099146 1000 600 600 (2strejilevich.dvi) @start /Fa 1 21 df<1A0E1A3F1AFF1903F10FFEF13FF8F1FFE00603138095381FFE00 F07FF8943801FFE005071380DD1FFEC7FCEF7FF0933801FFC0040790C8FCEE1FFCEE7FF0 923801FFC0030790C9FCED1FFCED7FF0913801FFC0020790CAFCEC3FFCECFFF0010313C0 010F90CBFCEB3FFCEBFFE000031380D80FFECCFCEA3FF8EAFFE01380A213E0EA3FF8EA0F FE3803FF80C613E0EB3FFCEB0FFF010313C0010013F0EC3FFCEC07FF020113C09138007F F0ED1FFCED07FF030113C09238007FF0EE1FFCEE07FF040113C09338007FF0EF1FFE9438 07FF80050113E09438007FF8F01FFE953803FF80060013E0F13FF8F10FFEF103FF19001A 3F1A0E1A00B3007FBA12FEBCFCA36C19FE485E76CB5D>20 D E /Fb 3 89 df32 D<12F07E127C7E123F7E6C7E6C7E6C7E7F12016C7E7F137E13 3E133F6D7E130F806D7EA26D7E80130180130080147E147F8081141F81140F81140781A2 140381140181A2140081A2157FA36F7EA382151FA282150FA3821507A382A21503A282A3 1501A282A31500A382A482A21780A7163F17C0AC161F17E0B3B3A217C0163FAC1780167F A71700A25EA45EA31501A35EA21503A35EA21507A25EA3150F5EA3151F5EA2153F5EA34B C7FCA315FEA25D1401A25D14035D1407A25D140F5D141F5D143F92C8FC5C147E14FE5C13 015C13035C495AA2495A5C131F49C9FC133E137E5B5B485A12035B485A485A48CAFC5A12 3E5A5A5A2BF87E8242>I88 D E /Fc 1 51 df<003FB712FEB9FCA300F0C9120FB3B3A4B9FCA4 303079B43E>50 D E /Fd 28 122 df46 D<141E143E14FE1307133FB5FCA313CFEA000FB3B3A6007FB6 1280A4213779B630>49 DIII<001C15C0D81F80130701F8137F90B61280A216005D5D15F05D15804AC7FC14F090 C9FCA8EB07FE90383FFFE090B512F89038FC07FC9038E003FFD98001138090C713C0120E C813E0157F16F0A216F8A21206EA3F80EA7FE012FF7FA44914F0A26C4813FF90C713E000 7C15C06C5B6C491380D9C0071300390FF01FFE6CB512F8000114E06C6C1380D90FF8C7FC 25387BB630>I58 D65 D67 D80 D<003FB91280A4D9F800EBF003D87FC09238007FC049161F007EC7150FA2007C1707A200 781703A400F818E0481701A4C892C7FCB3AE010FB7FCA43B387DB742>84 D97 D<903801FFC0010F13FC017F13FFD9FF8013802603FE0013C048485AEA 0FF8121F13F0123F6E13804848EB7F00151C92C7FC12FFA9127FA27F123FED01E06C7E15 036C6CEB07C06C6C14806C6C131FC69038C07E006DB45A010F13F00101138023257DA42A >99 DI<9038 03FF80011F13F0017F13FC3901FF83FE3A03FE007F804848133F484814C0001FEC1FE05B 003FEC0FF0A2485A16F8150712FFA290B6FCA301E0C8FCA4127FA36C7E1678121F6C6C14 F86D14F000071403D801FFEB0FE06C9038C07FC06DB51200010F13FC010113E025257DA4 2C>II<16 1FD907FEEBFFC090387FFFE348B6EAEFE02607FE07138F260FF801131F48486C138F003F 15CF4990387FC7C0EEC000007F81A6003F5DA26D13FF001F5D6C6C4890C7FC3907FE07FE 48B512F86D13E0261E07FEC8FC90CAFCA2123E123F7F6C7E90B512F8EDFF8016E06C15F8 6C816C815A001F81393FC0000F48C8138048157F5A163FA36C157F6C16006D5C6C6C495A D81FF0EB07FCD807FEEB3FF00001B612C06C6C91C7FC010713F02B377DA530>I<13FFB5 FCA412077EAFED7FC0913803FFF8020F13FE91381F03FFDA3C01138014784A7E4A14C05C A25CA291C7FCB3A3B5D8FC3F13FFA4303A7DB935>I<13FFB5FCA412077EAF92380FFFE0 A4923803FC0016F0ED0FE0ED1F804BC7FC157E5DEC03F8EC07E04A5A141FEC7FE04A7E81 81A2ECCFFEEC0FFF496C7F806E7F6E7F82157F6F7E6F7E82150F82B5D8F83F13F8A42D3A 7EB932>107 D<13FFB5FCA412077EB3B3ACB512FCA4163A7DB91B>I<01FED97FE0EB0FFC 00FF902601FFFC90383FFF80020701FF90B512E0DA1F81903983F03FF0DA3C0090388780 1F000749DACF007F00034914DE6D48D97FFC6D7E4A5CA24A5CA291C75BB3A3B5D8FC1FB5 0083B512F0A44C257DA451>I<01FEEB7FC000FF903803FFF8020F13FE91381F03FFDA3C 011380000713780003497E6D4814C05CA25CA291C7FCB3A3B5D8FC3F13FFA430257DA435 >I<903801FFC0010F13F8017F13FFD9FF807F3A03FE003FE048486D7E48486D7E48486D 7EA2003F81491303007F81A300FF1680A9007F1600A3003F5D6D1307001F5DA26C6C495A 6C6C495A6C6C495A6C6C6CB45A6C6CB5C7FC011F13FC010113C029257DA430>I<9038FE 03F000FFEB0FFEEC3FFF91387C7F809138F8FFC000075B6C6C5A5CA29138807F80ED3F00 150C92C7FC91C8FCB3A2B512FEA422257EA427>114 D<90383FF0383903FFFEF8000F13 FF381FC00F383F0003007E1301007C130012FC15787E7E6D130013FCEBFFE06C13FCECFF 806C14C06C14F06C14F81203C614FC131F9038007FFE140700F0130114007E157E7E157C 6C14FC6C14F8EB80019038F007F090B512C000F8140038E01FF81F257DA426>I<130FA5 5BA45BA25B5BA25A1207001FEBFFE0B6FCA3000390C7FCB21578A815F86CEB80F014816C EBC3E090383FFFC06D1380903803FE001D357EB425>I119 D121 D E /Fe 35 122 df37 D<143814FC13011303EB07F8EB0FF0EB1FC0EB3F80EB7F0013FE485A485A5B12075B120F 5B485AA2123F90C7FCA25A127EA312FE5AAC7E127EA3127F7EA27F121FA26C7E7F12077F 12037F6C7E6C7E137FEB3F80EB1FC0EB0FF0EB07F8EB03FC130113001438164272B92C> 40 D<127012FC7E7E6C7E6C7EEA0FE06C7E6C7E6C7E6C7E137F7F1480131F14C0130FEB 07E0A214F01303A214F81301A314FC1300AC130114F8A3130314F0A2130714E0A2EB0FC0 131F1480133F14005B13FE485A485A485A485AEA3FC0485A48C7FC5A5A1270164279B92C >I<007FB6FCB71280A46C150021067B9B2C>45 D<121FEA3F80EA7FC0EAFFE0A5EA7FC0 EA3F80EA1F000B0B708A2C>I<14FE497EA4497FA214EFA2130781A214C7A2010F7FA314 C390381F83F0A590383F01F8A490387E00FCA549137E90B512FEA34880A29038F8003FA3 4848EB1F80A4000715C049130FD87FFEEBFFFC6D5AB514FE6C15FC497E27347EB32C>65 D<007FB612F8B712FCA37ED803F0C7FCA716781600A515F04A7EA490B5FCA5EBF001A46E 5A92C7FCAD387FFFE0B5FC805C7E26337EB22C>70 D<387FFFFCB67E15E015F86C803907 E007FE1401EC007F6F7E151FA26F7EA64B5AA2153F4BC7FCEC01FE140790B55A5D15E081 819038E007FCEC01FE1400157F81A8160FEE1F80A5D87FFEEB1FBFB5ECFF00815E6C486D 5AC8EA01F029347EB22C>82 D<90381FF80790B5EA0F804814CF000714FF5A381FF01F38 3FC003497E48C7FC007E147F00FE143F5A151FA46CEC0F00007E91C7FC127F7FEA3FE0EA 1FFCEBFFC06C13FC0003EBFFC06C14F06C6C7F01077F9038007FFEEC07FF02001380153F ED1FC0A2ED0FE0A20078140712FCA56CEC0FC0A26CEC1F806D133F01E0EB7F009038FE01 FF90B55A5D00F914F0D8F83F13C0D8700790C7FC23357CB32C>I<3B7FFF803FFFC0B56C 4813E0A36C496C13C03B03F00001F800B3AF6D130300015DA26D130700005D6D130F017F 495A6D6C485AECE0FF6DB5C7FC6D5B010313F86D5B9038003F802B3480B22C>85 D87 D<3801FFF0000713FE001F6D7E15E048809038C01FF81407EC01FC381F80000006C77EC8 127EA3ECFFFE131F90B5FC1203120F48EB807E383FF800EA7FC090C7FC12FE5AA47E007F 14FEEB8003383FE01F6CB612FC6C15FE6C14BF0001EBFE1F3A003FF007FC27247CA32C> 97 DI<903803FFE0011F13F8017F13FE48B5FC48804848C6FCEA0FF0485A49137E 4848131890C9FC5A127EA25AA8127EA2127F6C140F6DEB1F806C7E6D133F6C6CEB7F0039 07FE03FF6CB55A6C5C6C6C5B011F13E0010390C7FC21247AA32C>IIII II< 1307EB1FC0A2497EA36D5AA20107C7FC90C8FCA7387FFFC080B5FC7EA2EA0007B3A8007F B512FCB612FEA36C14FC1F3479B32C>I107 D<387FFFE0B57EA37EEA0003B3B3A5007F B61280B712C0A36C158022337BB22C>I<3A7F83F007E09039CFFC1FF83AFFDFFE3FFCD8 7FFF13FF91B57E3A07FE1FFC3E01FCEBF83F496C487E01F013E001E013C0A301C01380B3 3B7FFC3FF87FF0027F13FFD8FFFE6D13F8D87FFC4913F0023F137F2D2481A32C>I<397F F01FE039FFF87FFC9038F9FFFE01FB7F6CB6FC00019038F03F80ECC01F02807FEC000F5B 5BA25BB3267FFFE0B5FCB500F11480A36C01E0140029247FA32C>II<397FF01FE0 39FFF8FFF801FB13FE90B6FC6C158000019038F07FC09138801FE091380007F049EB03F8 5BED01FC491300A216FE167EA816FE6D14FCA2ED01F86D13036DEB07F0150F9138801FE0 9138E07FC091B51280160001FB5B01F813F8EC3FC091C8FCAD387FFFE0B57EA36C5B2736 7FA32C>I<903903FC078090391FFF0FC0017F13CF48B512EF4814FF3807FE07380FF001 48487E49137F4848133F90C7FC48141F127E150F5AA87E007E141FA26C143F7F6C6C137F 6D13FF380FF0033807FC0F6CB6FC6C14EF6C6C138F6D130FEB07F890C7FCAD0203B5FC4A 1480A36E140029367DA32C>II<90387FF8700003B512F8120F5A5A387FC00F387E00034813015AA36CEB 00F0007F140013F0383FFFC06C13FE6CEBFF80000314E0C66C13F8010113FCEB0007EC00 FE0078147F00FC143F151F7EA26C143F6D133E6D13FE9038F007FC90B5FC15F815E000F8 148039701FFC0020247AA32C>I<131E133FA9007FB6FCB71280A36C1500D8003FC8FCB1 ED03C0ED07E0A5EC800F011FEB1FC0ECE07F6DB51280160001035B6D13F89038003FE023 2E7EAD2C>I<3A7FF003FF80486C487FA3007F7F0001EB000FB3A3151FA2153F6D137F39 00FE03FF90B7FC6D15807F6D13CF902603FE07130029247FA32C>I<3A7FFF01FFFCB514 FE148314016C15FC3A03E0000F80A26D131F00011500A26D5B0000143EA26D137E017C13 7CA2017E13FC013E5BA2EB3F01011F5BA21483010F5BA214C701075BA214EF01035BA214 FF6D90C7FCA26D5A147C27247EA32C>II<3A3FFF03FFF048018713F8A36C010313F03A00FC007E005D90387E01F8013F5BEB1F 83EC87E090380FCFC0903807EF80EB03FF6D90C7FC5C6D5A147C14FE130180903803EF80 903807CFC0EB0FC7EC83E090381F01F0013F7FEB7E00017C137C49137E0001803A7FFF01 FFFC1483B514FE6C15FC140127247EA32C>I<3A7FFF01FFFCB5008113FE148314816C01 0113FC3A03E0000F806C7E151F6D140012005D6D133E137C017E137E013E137CA2013F13 FC6D5BA2EB0F815DA2EB07C1ECC3E0A2EB03E3ECE7C0130114F75DEB00FFA292C7FC80A2 143EA2147E147CA214FC5CA2EA0C01003F5BEA7F83EB87E0EA7E0F495A387FFF806C90C8 FC6C5A6C5AEA07E027367EA32C>I E /Ff 2 62 df<14075C5C147F5C1307133F000FB5 FCB6FC13F913C1EAF0011200B3B3B3A7497F010F13E0B712FEA4274F75CE3B>49 D<003FBB12F0BC12FCA4CFFCB3BC12FCA4003F1AF04E1D7AAB5B>61 D E /Fg 2 120 720 600 dfs[<14FE137FA3EB01FC13001301A25CA21303A25CA21307 A25CA2130FA25CA2131FA25C163F013FECFFC0923803C0E09138000703ED1E0F491338ED 701F017E13E0EC01C001FE018013C00203EB07004948C8FC140E00015B5C495A5C3803FB C001FFC9FC8014F83807F1FE9038F03F809038E00FE06E7E000F130381EBC001A2001FED 01C017801380A2003F15031700010013F05E481506160E007E150C161C00FE01005BED78 7048EC3FE00038EC0F80>43 70 123 196 61 107 D[<013E1738D9FF80D901C013FC26 03C3C0903907E001FE380703E0380601F0000E150F001C16C0D8180316000038187E0030 031F143E00705ED86007171E5C163FD8E00F92C7121C00C049160CEA001F4A49141C047E 1418133F91C7FC04FE1438491730017E5CA20301157001FE1760495C19E019C0A2494948 1301198018031900606D0107140670130E017C010F5C017E010C1418013ED91CFC13386D D9387E13F0903B0FC0F01F01C0903B03FFC00FFF809028007F0001FEC7FC>63 45 125 171 84 119 D E /Fh 1 107 df106 D E /Fi 6 62 df<140EB3A2B812E0A3C7000EC8FCB3A22B2B 7DA333>43 D<13381378EA01F8121F12FE12E01200B3AB487EB512F8A215267BA521>49 D<13FF000313E0380E03F0381800F848137C48137E00787F12FC6CEB1F80A4127CC7FC15 005C143E147E147C5C495A495A5C495A010EC7FC5B5B903870018013E0EA018039030003 0012065A001FB5FC5A485BB5FCA219267DA521>I<13FF000313E0380F01F8381C007C00 30137E003C133E007E133FA4123CC7123E147E147C5C495AEB07E03801FF8091C7FC3800 01E06D7E147C80143F801580A21238127C12FEA21500485B0078133E00705B6C5B381F01 F03807FFC0C690C7FC19277DA521>I<1438A2147814F81301A2130313071306130C131C 131813301370136013C012011380EA03005A120E120C121C5A12305A12E0B612E0A2C7EA F800A7497E90383FFFE0A21B277EA621>I<007FB712C0B812E0A2CBFCABB812E0A26C16 C02B117D9633>61 D E /Fj 2 4 df0 D<1338A50060130C00F8 133E00FC137E00FE13FE383FBBF83807FFC000011300EA007C48B4FC000713C0383FBBF8 38FE38FE00FC137E00F8133E0060130C00001300A517197B9A22>3 D E /Fk 21 120 df<16E0000214010006EC03F0120E000C1401481400A2481570166048 1330147014F04815C0A2495AED018014C0ED03005DD8E003130E0107131E39F01FE07CB6 5AD87FFC5B6C485B391FE07FC0260F803FC7FC241B7E992A>33 D<4B7E1503150782150F 151FA2153FA2156F15CF82EC0187140315071406140E140C02187FA2EC30031460A214C0 13011480D903007F91B5FC5B90380C0001A25B13380130805B01E013005B12011203000F 4A7ED8FFF890381FFFE0A22B2A7DA932>65 D<4AB41308020FEBE01891397F80F038903A 01F8001870D903E0EB0CF0D90F80130749C71203013E15E05B491401485A484815C0485A 120F5B001F168090C8FC4892C7FCA2127EA4127C12FCA21606007C5DA35E007E5D123E5E 6C5D6C6C495A00074AC7FCD803E0130E6C6C13383900FE01F090383FFFC0D907FCC8FC2D 2A7DA830>67 D<013FB512FC16FF903A01FC001FC04AEB03E0EE01F801031400177C4A80 A2010781A25CA2130F18805CA2011F1600A24A5CA2133F173E91C8127E177C4915FC5F01 7E14015F01FE4A5AA2494A5A4C5A00014BC7FC167C495CED03E00003EC1FC0B600FEC8FC 15F031287DA736>I<013FB612F0A2903901FC00074A1301160001031560A25CA21307A2 5CED0180010F0103130093C7FC14C05D131F151EECFFFEA290383F801E150C1400A24913 1C1518137E92C8FC13FEA25BA21201A25BA21203B512F0A22C287DA72A>70 D<4AB4FC021F13E091387E01F8903901F0007ED907C0131F4948EB0F80011EC7EA07C013 7C49EC03E0485AEE01F0485A485A120F4915F8121F90C8FC5A17F0007E1503A4EE07E05A EE0FC0A2EE1F80A2007CED3F00007E153E167E003E5D4B5A6C4A5A6DEB07C0000F4A5A6C 6C013FC7FCD803F013FC3900FC03F090383FFFC0D907FCC8FC2D2A7DA832>79 D<013FB512F816FF903A01FC001FC04AEB07E0EE01F0010315F816005CA2130716015CA2 010FEC03F0A24AEB07E0EE0FC0011FEC1F80EE3E0091388001FC91B512E093C7FCD93F80 C8FC91C9FCA35B137EA313FE5BA312015BA21203B512C0A22D287DA72A>I<013FB512E0 16FC903901FC007F4AEB0F80EE07C0010315E016035C17F01307EE07E05CA2010FEC0FC0 17804AEB1F00163E011F14F8ED07F091B51280A290393F800FE0ED03F002007F15015BA2 137EA201FE1303A2495CA20001160817184914E017380003EDF070B5D8C00113E0923800 FFC0C9EA3F002D297DA732>82 D<000FB712E05A9039800FE007D81E009038C001C05A00 38011F1300123000705C00601501023F148012E0481400A2C74890C7FCA2147EA214FEA2 5CA21301A25CA21303A25CA21307A25CA2130FA25CA2131F001FB57EA22B287DA727>84 D86 DI<15F8141FA2EC01F0A21403A215E0A21407A215C0A2140FEB1F8F9038 7FCF80EBF0EF3803C03FEA0780390F001F00A2001E5B123E003C133E127C147E5A147CA2 14FC5AECF830A3903801F060A2EA7803010E13C0393C1CF980381FF07F3907C01E001D29 7CA723>100 DI<130E131F5BA2133E131C90C7FCA7EA03E0487EEA 0C78EA187C1230A212605B12C0A2EA01F0A3485AA2485AA2EBC180EA0F81A2381F0300A2 13066C5A131CEA07F06C5A11287DA617>105 D<1407EC0F80141FA21500140E91C7FCA7 EB03E0EB07F8EB0C3C1318EB303E136013C0A248485AA2C7FCA25CA4495AA4495AA4495A A4495AA21238D87C1FC7FC12FC133E485AEA70F8EA7FE0EA1F80193380A61B>I<133EEA 07FEA2EA007CA213FCA25BA21201A25BA21203EC07809038E01FC0EC38600007EB61E014 C3EBC187EBC307D80FC613C09038CC038001B8C7FC13E0487E13FEEB3F80EB0FC0486C7E 1303003E1460A2127EECC0C0127CECC18012FC903801E30038F800FE0070137C1B297CA7 23>I<3B07801FC007E03B0FE07FF01FF83B18F0E0F8783C3B30F1807CE03E903AFB007D 801ED860FEEB3F005B49133E00C14A133E5B1201A24848495BA35F4848485A1830EE01F0 A23C0F8003E003E060A218C0933801E180271F0007C013E3933800FF00000E6D48137C34 1B7D993B>109 D<3907801FC0390FE07FF03918F0E0F83930F1807CEBFB00D860FE133C 5B5B00C1147C5B1201A248485BA34A5AEA07C01660EC03E0A23A0F8007C0C0A2EDC18091 3803C300D81F0013C7EC01FE000EEB00F8231B7D9929>II<3903E001C03907 F003E0380C7807EA187C0030130314011260EBF80000C014C0A2EA01F0A2EC0180EA03E0 A2EC0300EA07C0A21406A25CA200035B6D5A3801F0E06CB45A013FC7FC1B1B7D9921> 118 DI E /Fl 30 119 df12 D46 D 49 DII<163FA25E5E5D5DA25D5D 5D5DA25D92B5FCEC01F7EC03E7140715C7EC0F87EC1F07143E147E147C14F8EB01F0EB03 E0130714C0EB0F80EB1F00133E5BA25B485A485A485A120F5B48C7FC123E5A12FCB91280 A5C8000F90C7FCAC027FB61280A531417DC038>I<0007150301E0143F01FFEB07FF91B6 FC5E5E5E5E5E16804BC7FC5D15E092C8FC01C0C9FCAAEC3FF001C1B5FC01C714C001DF14 F09039FFE03FFC9138000FFE01FC6D7E01F06D13804915C0497F6C4815E0C8FC6F13F0A3 17F8A4EA0F80EA3FE0487E12FF7FA317F05B5D6C4815E05B007EC74813C0123E003F4A13 80D81FC0491300D80FF0495AD807FEEBFFFC6CB612F0C65D013F1480010F01FCC7FC0101 13C02D427BC038>I68 D70 D73 D80 D82 DI98 DI101 DI104 D<137C48B4FC4813804813C0A24813E0A56C13C0A26C13806C1300EA007C 90C7FCAAEB7FC0EA7FFFA512037EB3AFB6FCA518467CC520>I108 D<90277F8007FEEC0FFCB590263FFFC090387FFF80 92B5D8F001B512E002816E4880913D87F01FFC0FE03FF8913D8FC00FFE1F801FFC0003D9 9F009026FF3E007F6C019E6D013C130F02BC5D02F86D496D7EA24A5D4A5DA34A5DB3A7B6 0081B60003B512FEA5572D7CAC5E>I<90397F8007FEB590383FFF8092B512E0028114F8 913987F03FFC91388F801F000390399F000FFE6C139E14BC02F86D7E5CA25CA35CB3A7B6 0083B512FEA5372D7CAC3E>II<90397FC00FF8B590B57E02C314E002CF14F89139DFC03FFC9139FF001FFE000301FC EB07FF6C496D13804A15C04A6D13E05C7013F0A2EF7FF8A4EF3FFCACEF7FF8A318F017FF A24C13E06E15C06E5B6E4913806E4913006E495A9139DFC07FFC02CFB512F002C314C002 C091C7FCED1FF092C9FCADB67EA536407DAC3E>II<90387F807FB53881FFE0028313F0028F13F8ED8FFC91 389F1FFE000313BE6C13BC14F8A214F0ED0FFC9138E007F8ED01E092C7FCA35CB3A5B612 E0A5272D7DAC2E>I<90391FFC038090B51287000314FF120F381FF003383FC00049133F 48C7121F127E00FE140FA215077EA27F01E090C7FC13FE387FFFF014FF6C14C015F06C14 FC6C800003806C15806C7E010F14C0EB003F020313E0140000F0143FA26C141F150FA27E A26C15C06C141FA26DEB3F8001E0EB7F009038F803FE90B55A00FC5CD8F03F13E026E007 FEC7FC232F7CAD2C>IIII E /Fm 13 113 df<007FB81280B912C0A26C17803204799641>0 D<121C127FEAFF80A5EA 7F00121C0909799917>I15 D20 D<127012FCB4FCEA7FC0EA1FF0EA07FCEA01FF3800 7FC0EB1FF0EB07FCEB01FF9038007FC0EC1FF0EC07FCEC01FF9138007FC0ED1FF0ED07FC ED01FF9238007FC0EE1FF0EE07FCEE01FF9338007FC0171F177F933801FF80933807FC00 EE1FF0EE7FC04B48C7FCED07FCED1FF0ED7FC04A48C8FCEC07FCEC1FF0EC7FC04948C9FC EB07FCEB1FF0EB7FC04848CAFCEA07FCEA1FF0EA7FC048CBFC12FC1270CCFCAD007FB812 80B912C0A26C1780324279B441>I49 D<91381FFFFE91B6FC1303010F14FED91FF0C7FCEB7F8001FEC8FCEA01F8485A485A485A 5B48C9FCA2123EA25AA2127812F8A25AA2B712FE16FFA216FE00F0C9FCA27EA21278127C A27EA27EA26C7E7F6C7E6C7E6C7EEA00FEEB7F80EB1FF06DB512FE010314FF1300021F13 FE283279AD37>I54 D<0060161800F0163C6C16 7CA200781678007C16F8A2003C16F0003E1501A26CED03E0A26C16C06D1407A200071680 6D140FA26C6CEC1F00A26CB612FEA36C5D01F8C7127CA2017C5CA2013C5C013E1301A201 1E5C011F1303A26D6C485AA201075CECC00FA2010391C7FC6E5AA2903801F03EA2010013 3CECF87CA2EC7878EC7CF8A2EC3FF0A26E5AA36E5AA36E5A6EC8FC2E3C80B92F>56 D<0203B512F8027FECFF8049B712F0010F8290273FC3F00313FED978039038003FFF2601 E00702071380D803C06F13C0D807801500000F177FD81F00EE3FE0484A141F123E5A0078 010F150F12C0C7FC4B15C0A3021FED1F80A24B1500183EA2023F5D6092C85A4D5A4D5A4A 4A5A027E020EC7FC173C17F84AEB03E0EE3F80DB1FFEC8FC0101EB7FF89138F8FFC0DAF9 FCC9FC02F8CAFC495AA3495AA3495AA3495AA291CBFC5BA2137EA35B13F013C03B3D7FB8 3A>80 D102 D<12FCEAFFC0EA07F0EA01FCEA007E7F 80131F80130FB3A7801307806D7E6D7EEB007EEC1FF0EC07F8EC1FF0EC7E00495A495A49 5A5C130F5CB3A7131F5C133F91C7FC137E485AEA07F0EAFFC000FCC8FC1D537ABD2A>I< F10180F103C01907A2F10F80A2F11F00A2193EA261A261A24E5AA24E5AA24E5AA24E5AA2 96C7FC60A2183EA260A260A24D5AA24D5AA24D5AA24D5AA24DC8FCA20130153E13F00001 5EEA07F8000F5E487E00794B5AEAE1FE00C04B5AC67E6D4A5AA26E495A133F6E49C9FC13 1F6E133E130F6E5B13076E1378010314F8A26E485A13016E485A13006E485A147FED8F80 143F039FCAFC15DFEC1FFEA26E5AA26E5AA26E5AA26E5A5D42547B8345>112 D E /Fn 25 120 df<027FB512C00103B612E0130F5B017F15C09026FF81FEC7FC3901FC 007E48487F485A497F484880485AA248C7FCA2127EA2153F00FE92C7FC5AA25D157E5A5D A24A5AA24A5A007C495A5D003C495A003E013FC8FC6C137C380F81F83803FFE0C66CC9FC 2B257DA32F>27 D<121C127FEAFF80A5EA7F00121C0909798817>58 D<121C127FEAFF80A213C0A3127F121C1200A412011380A2120313005A1206120E5A5A5A 12600A19798817>II<150C151E15 3EA2153C157CA2157815F8A215F01401A215E01403A215C01407A21580140FA215005CA2 141E143EA2143C147CA2147814F8A25C1301A25C1303A2495AA25C130FA291C7FC5BA213 1E133EA2133C137CA2137813F8A25B1201A25B1203A25B1207A25B120FA290C8FC5AA212 1E123EA2123C127CA2127812F8A25A12601F537BBD2A>I<124012F812FE6C7EEA3FE0EA 0FF8EA03FEC66C7EEB3FE0EB0FF8EB03FE903800FF80EC3FE0EC0FF8EC03FE913800FF80 ED3FE0ED0FF8ED03FE923800FF80EE3FE0EE0FF8EE03FE933800FF80EF3FC0A2EFFF8093 3803FE00EE0FF8EE3FE0EEFF80DB03FEC7FCED0FF8ED3FE0EDFF80DA03FEC8FCEC0FF8EC 3FE0ECFF80D903FEC9FCEB0FF8EB3FE0EBFF80D803FECAFCEA0FF8EA3FE0EAFF8048CBFC 12F81260323279AD41>I<9339FF8001C0030F13E0037F9038F80380913A01FF807E0791 3A07F8000F0FDA1FE0EB079FDA3F80903803BF0002FFC76CB4FCD901FC80495A4948157E 495A495A4948153E017F163C49C9FC5B1201484816385B1207485A1830121F4993C7FCA2 485AA3127F5BA312FF90CCFCA41703A25F1706A26C160E170C171C5F6C7E5F001F5E6D4A 5A6C6C4A5A16076C6C020EC8FC6C6C143C6C6C5C6CB4495A90393FE00FC0010FB5C9FC01 0313FC9038007FC03A3D7CBA3B>67 D<0103B7FC4916E018F8903B0007F80007FE4BEB00 FFF03F80020FED1FC0180F4B15E0F007F0021F1503A24B15F81801143F19FC5DA2147FA2 92C8FCA25C18035CA2130119F84A1507A2130319F04A150FA2010717E0181F4A16C0A201 0FEE3F80A24AED7F00187E011F16FE4D5A4A5D4D5A013F4B5A4D5A4A4A5A057FC7FC017F 15FEEE03FC91C7EA0FF049EC7FC0B8C8FC16FC16C03E397DB845>I<003FB56C48B51280 485DA226007F80C7381FF00091C8EA07C0604993C7FCA2491506A20001160E170C5BA200 03161C17185BA20007163817305BA2000F167017605BA2001F16E05F5BA2003F15015F5B A2007F150394C8FC90C8FCA25E4815065A160E160C161C161816385E127E5E4B5A6C4A5A 4BC9FC6C6C131E6C6C5B6C6C13F83903F807E06CB55A6C6C48CAFCEB0FF0393B7BB839> 85 D<1578EC01FEEC07C6EC0F861507EC1E03143E147C1507ECF806A2EB01F00103130E ECE00C1307A2ECC01C010F1318153890381F80301570156090383F00E015C01401017F13 80EB7E03EC07001406EBFE0E495A5C143000011370495AEBF9C0EBFB8001FFC7FC5B5B48 5AA25BA4485A120F121DEA39F0127100E1140C0080143C0000147015E090387801C0EC07 8090383C1E00EB1FF8EB07E0203C7FBA23>96 D<147E903803FF8090390FC1C38090391F 00EFC0017E137F49133F485A4848EB1F8012075B000F143F48481400A2485A5D007F147E 90C7FCA215FE485C5AA214015D48150CA21403EDF01C16181407007C1538007E010F1330 003E131F027B13706C01E113E03A0F83C0F9C03A03FF007F80D800FCEB1F0026267DA42C >I<133FEA1FFFA3C67E137EA313FE5BA312015BA312035BA31207EBE0FCEBE3FF9038E7 07C0390FFE03E09038F801F001F013F8EBE000485A15FC5BA2123F90C7FCA214015A127E A2140312FE4814F8A2140715F05AEC0FE0A215C0EC1F80143F00781400007C137E5C383C 01F86C485A380F07C06CB4C7FCEA01FC1E3B7CB924>II<14E0EB03F8A21307A314F0EB 01C090C7FCAB13F8EA03FEEA070F000E1380121C121812381230EA701F1260133F00E013 0012C05BEA007EA213FE5B1201A25B12035BA20007131813E01438000F133013C01470EB 806014E014C01381EB838038078700EA03FEEA00F815397EB71D>105 D<150FED3F80A2157FA31600151C92C7FCABEC0F80EC3FE0ECF0F0903801C0F849487E14 005B130E130C131CEB1801133801305BA2EB0003A25DA21407A25DA2140FA25DA2141FA2 5DA2143FA292C7FCA25CA2147EA214FEA25CA21301001E5B123F387F83F0A238FF87E049 5A00FE5BD87C1FC8FCEA707EEA3FF8EA0FC0214981B722>II109 DI<90390F 8003F090391FE00FFC903939F03C1F903A70F8700F80903AE0FDE007C09038C0FF800300 13E00001491303018015F05CEA038113015CA2D800031407A25CA20107140FA24A14E0A2 010F141F17C05CEE3F80131FEE7F004A137E16FE013F5C6E485A4B5A6E485A90397F700F 80DA383FC7FC90387E1FFCEC07E001FEC9FCA25BA21201A25BA21203A25B1207B512C0A3 2C3583A42A>112 D<02FC13C0903803FF0190380F838390383F01C790397E00EF804913 7F485A4848133F000715005B485A001F5C157E485AA2007F14FE90C75AA3481301485CA3 1403485CA314075D140F127C141F007E495A003E137F381F01EF380F839F3903FF1F80EA 00FC1300143F92C7FCA35C147EA314FE5C130190387FFFF0A322357DA425>I<3903E001 F83907F807FE390E3C1E07391C3E381F3A183F703F800038EBE07F0030EBC0FF00705B00 601500EC007E153CD8E07F90C7FCEAC07EA2120013FE5BA312015BA312035BA312075BA3 120F5BA3121F5B0007C9FC21267EA425>I<14FF010313C090380F80F090383E00380178 131C153C4913FC0001130113E0A33903F000F06D13007F3801FFE014FC14FF6C14806D13 C0011F13E013039038003FF014071403001E1301127FA24814E0A348EB03C012F800E0EB 07800070EB0F006C133E001E13F83807FFE0000190C7FC1E267CA427>II<13F8D803FE1438D8070F147C000E6D13 FC121C1218003814011230D8701F5C12601503EAE03F00C001005B5BD8007E1307A201FE 5C5B150F1201495CA2151F120349EC80C0A2153F1681EE0180A2ED7F0303FF130012014A 5B3A00F8079F0E90397C0E0F1C90393FFC07F8903907F001F02A267EA430>I<01F816F0 D803FE9138E001F8D8070F903801F003000ED9800314FC121C12180038020713010030ED E000D8701F167C1260030F143CD8E03F163800C001005B5BD8007E131F183001FE5C5B03 3F1470000117604991C7FCA218E000034A14C049137E17011880170318005F03FE130617 0E000101015C01F801BF5B3B00FC039F8070903A7E0F0FC0E0903A1FFC03FFC0902703F0 007FC7FC36267EA43B>119 D E /Fo 3 84 df69 D74 D83 D E /Fp 54 123 df<04FFEB03F003039038E00FFC923A0FC0F01F1E923A3F00783E0F923A7E01F8 7C3FDB7C03EBFC7F03FC14F8DA01F813F905F1137EDC01E1133C913B03F00003F000A314 074B130760A3140F4B130F60A3010FB812C0A3903C001F80001F8000A3023F143F92C790 C7FCA44A5C027E147EA402FE14FE4A5CA413014A13015FA313034A13035FA313074A495A A44948495AA44948495AA3001CD9038090C8FC007E90380FC03F013E143E00FE011F5B13 3C017C5C3AF8780F01E0D878F0EB07C0273FE003FFC9FC390F8000FC404C82BA33>11 DI39 D<150C151C153815F0EC01E0EC03C0EC0780EC0F00 141E5C147C5C5C495A1303495A5C130F49C7FCA2133EA25BA25BA2485AA212035B12075B A2120F5BA2121FA290C8FCA25AA2123EA2127EA2127CA412FC5AAD1278A57EA3121C121E A2120E7EA26C7E6C7EA212001E5274BD22>I<140C140E80EC0380A2EC01C015E0A21400 15F0A21578A4157C153CAB157CA715FCA215F8A21401A215F0A21403A215E0A21407A215 C0140F1580A2141F1500A2143EA25CA25CA2495AA2495A5C1307495A91C7FC5B133E133C 5B5B485A12035B48C8FC120E5A12785A12C01E527FBD22>I44 D<387FFFF8A2B5FCA214F0150579941E>I<120EEA3F80127F12FFA3130012 7E123C0909778819>I50 DI<157F913803FFC0020F13 E0EC3F8191387E00F002F81370903903F003F0903807E007EB0FC0EB1F80020013E04914 C0017E90C7FC13FE5B485AA21203485AA2380FE07E9038E3FF809038E783E0391FCE01F0 9038DC00F813F84848137C5B49137EA2485AA290C7FC15FE5A5AA214015D5AA214035DA3 48495A5D140F5D4A5A6C49C7FC127C147C6C485A6C485A6CB45A6C1380D801FCC8FC243A 76B72A>54 DI57 D65 D67 D<0103B612FEEFFFC018F0903B0007F8000FF84BEB03FCEF00FE020F157FF0 3F804B141F19C0021F150F19E05D1807143F19F05DA2147FA292C8FCA25C180F5CA21301 19E04A151FA2130319C04A153FA201071780187F4A1600A2010F16FEA24A4A5A60011F15 034D5A4A5D4D5A013F4B5A173F4A4AC7FC17FC017FEC03F84C5A91C7EA1FC04949B45A00 7F90B548C8FCB712F016803C397CB83F>I<0107B8FCA3903A000FF000034BEB007F183E 141F181E5DA2143FA25D181C147FA29238000380A24A130718004A91C7FC5E13015E4A13 3E167E49B512FEA25EECF8000107147C163C4A1338A2010F147818E04A13701701011F16 C016004A14031880013F150718004A5CA2017F151E173E91C8123C177C4915FC4C5A4914 070001ED7FF0B8FCA25F38397BB838>I<0107B712FEA3903A000FF000074B1300187C02 1F153CA25DA2143FA25D1838147FA292C8FCEE03804A130718004A91C7FCA201015CA24A 131E163E010314FE91B5FC5EA2903807F800167C4A1378A2130FA24A1370A2011F14F0A2 4A90C8FCA2133FA25CA2137FA291CAFCA25BA25B487EB6FCA337397BB836>I<0103B512 F8A390390007F8005DA2140FA25DA2141FA25DA2143FA25DA2147FA292C7FCA25CA25CA2 1301A25CA21303A25CA21307A25CA2130FA25CA2131FA25CA2133FA25CA2137FA291C8FC 497EB6FCA25C25397CB820>73 D<0207B512F0A391390007FC006F5AA215075EA3150F5E A3151F5EA3153F5EA3157F93C7FCA35D5DA314015DA314035DA31407A25DA2140FA2003F 5C5A141F485CA24A5A12FC00E049C8FC14FE00705B495A6C485A381E0FC06CB4C9FCEA01 F82C3B78B82C>I<0107B512FCA25E9026000FF8C7FC5D5D141FA25DA2143FA25DA2147F A292C8FCA25CA25CA21301A25CA21303A25CA21307A25CA2130F170C4A141CA2011F153C 17384A1478A2013F157017F04A14E01601017F140317C091C71207160F49EC1F80163F49 14FF000102071300B8FCA25E2E397BB834>76 D<902607FFF8923807FFF0614F13E0D900 0FEFF0004F5AA2021F167FF1EFC0141DDA1CFCEC01CF023C16DF9538039F800238ED071F A20278ED0E3F97C7FC0270151CA202F04B5AF0707E14E0037E14E0010117FE4D485A02C0 EC0380A20103ED0701610280140EA20107ED1C0305385B14006F137049160705E05B010E EC01C0A2011E913803800F61011CEC0700A2013C020E131F4C5C1338ED1FB80178163F04 F091C8FC01705CA201F04A5B187E00015DD807F816FEB500C09039007FFFFC151E150E4C 397AB84A>I<902603FFF891B512E0A281D90007923807F8006F6E5A61020F5E81DA0E7F 5DA2021E6D1307033F92C7FC141C82DA3C1F5C70130EEC380FA202786D131E0307141C14 7082DAF003143C70133814E0150101016E1378030014705C8201036E13F0604A1480163F 010715C1041F5B91C7FC17E149EC0FE360010E15F31607011E15FF95C8FC011C80A2013C 805F1338160013785F01F8157CEA03FC267FFFE0143CB51538A243397CB83E>II<0107B612F8 17FF1880903B000FF0003FE04BEB0FF0EF03F8141FEF01FC5DA2023F15FEA25DA2147FEF 03FC92C7FCA24A15F817074A15F0EF0FE01301EF1FC04AEC3F80EFFE0001034A5AEE0FF0 91B612C04CC7FCD907F8C9FCA25CA2130FA25CA2131FA25CA2133FA25CA2137FA291CAFC A25BA25B1201B512FCA337397BB838>I<0103B612F017FEEFFF80903B0007F8003FC04B EB0FF01707020FEC03F8EF01FC5DA2021F15FEA25DA2143FEF03FC5DA2027FEC07F818F0 92C7120F18E04AEC1FC0EF3F004A14FEEE01F80101EC0FE091B6128004FCC7FC9138FC00 3F0103EC0F80834A6D7E8301071403A25C83010F14075F5CA2011F140FA25CA2133F161F 4AECE007A2017F160F180E91C7FC49020F131C007F01FE153CB5913807F078040313F0CA EAFFE0EF3F80383B7CB83D>82 D<92383FC00E913901FFF01C020713FC91391FC07E3C91 393F001F7C027CEB0FF84A130749481303495A4948EB01F0A2495AA2011F15E091C7FCA3 4915C0A36E90C7FCA2806D7E14FCECFF806D13F015FE6D6D7E6D14E0010080023F7F1407 9138007FFC150F15031501A21500A2167C120EA3001E15FC5EA3003E4A5AA24B5AA2007F 4A5A4B5A6D49C7FC6D133ED8F9F013FC39F8FC03F839F07FFFE0D8E01F138026C003FCC8 FC2F3D7ABA2F>I<0007B812E0A25AD9F800EB001F01C049EB07C0485AD900011403121E 001C5C003C17801403123800785C00701607140700F01700485CA2140FC792C7FC5DA214 1FA25DA2143FA25DA2147FA292C9FCA25CA25CA21301A25CA21303A25CA21307A25CA213 0FA25CEB3FF0007FB512F8B6FCA2333971B83B>I87 D<14F8EB07FE90381F871C90383E03FE137CEBF801120148 486C5A485A120FEBC001001F5CA2EA3F801403007F5C1300A21407485C5AA2140F5D48EC C1C0A2141F15831680143F1587007C017F1300ECFF076C485B9038038F8E391F0F079E39 07FE03FC3901F000F0222677A42A>97 D<133FEA1FFFA3C67E137EA313FE5BA312015BA3 12035BA31207EBE0F8EBE7FE9038EF0F80390FFC07C013F89038F003E013E0D81FC013F0 A21380A2123F1300A214075A127EA2140F12FE4814E0A2141F15C05AEC3F80A215005C14 7E5C387801F8007C5B383C03E0383E07C0381E1F80D80FFEC7FCEA01F01C3B77B926>I< 147F903803FFC090380FC1E090381F0070017E13784913383901F801F83803F003120713 E0120FD81FC013F091C7FC485AA2127F90C8FCA35A5AA45AA3153015381578007C14F000 7EEB01E0003EEB03C0EC0F806CEB3E00380F81F83803FFE0C690C7FC1D2677A426>II<147F903803FFC090380FC1E090383F00F0017E13785B485A485A485A120F4913F800 1F14F0383F8001EC07E0EC1F80397F81FF00EBFFF891C7FC90C8FC5A5AA55AA21530007C 14381578007E14F0003EEB01E0EC03C06CEB0F806CEB3E00380781F83803FFE0C690C7FC 1D2677A426>IIIII107 DIII<147F903803FFC090380FC1F090381F00F8017E 137C5B4848137E4848133E0007143F5B120F485AA2485A157F127F90C7FCA215FF5A4814 FEA2140115FC5AEC03F8A2EC07F015E0140F007C14C0007EEB1F80003EEB3F00147E6C13 F8380F83F03803FFC0C648C7FC202677A42A>I<9039078007C090391FE03FF090393CF0 787C903938F8E03E9038787FC00170497EECFF00D9F0FE148013E05CEA01E113C15CA2D8 0003143FA25CA20107147FA24A1400A2010F5C5E5C4B5A131F5EEC80035E013F495A6E48 5A5E6E48C7FC017F133EEC70FC90387E3FF0EC0F8001FEC9FCA25BA21201A25BA21203A2 5B1207B512C0A3293580A42A>II<3903C0 03F0390FF01FFC391E783C0F381C7C703A3C3EE03F8038383FC0EB7F8000781500007013 00151CD8F07E90C7FCEAE0FE5BA2120012015BA312035BA312075BA3120F5BA3121F5BA3 123F90C9FC120E212679A423>I<14FE903807FF8090380F83C090383E00E04913F00178 137001F813F00001130313F0A215E00003EB01C06DC7FC7FEBFFC06C13F814FE6C7F6D13 807F010F13C01300143F141F140F123E127E00FE1480A348EB1F0012E06C133E00705B6C 5B381E03E06CB45AD801FEC7FC1C267AA422>II<13F8D803FEEB01C0D8078FEB03E0390E0F8007121E121C003814 0F131F007815C01270013F131F00F0130000E015805BD8007E133FA201FE14005B5D1201 49137EA215FE120349EBFC0EA20201131E161C15F813E0163CD9F003133814070001ECF0 7091381EF8F03A00F83C78E090393FF03FC090390FC00F00272679A42D>I<01F0130ED8 03FC133FD8071EEB7F80EA0E1F121C123C0038143F49131F0070140FA25BD8F07E140000 E08013FEC6485B150E12015B151E0003141C5BA2153C000714385B5DA35DA24A5A140300 035C6D48C7FC0001130E3800F83CEB7FF8EB0FC0212679A426>I<01F01507D803FC9039 03801F80D8071E903907C03FC0D80E1F130F121C123C0038021F131F49EC800F00701607 A249133FD8F07E168000E0ED000313FEC64849130718000001147E5B03FE5B0003160E49 5BA2171E00070101141C01E05B173C1738A217781770020314F05F0003010713016D486C 485A000190391E7C07802800FC3C3E0FC7FC90393FF81FFE90390FE003F0322679A437> I<903907E007C090391FF81FF89039787C383C9038F03E703A01E01EE0FE3803C01F0180 13C0D8070014FC481480000E1570023F1300001E91C7FC121CA2C75AA2147EA214FEA25C A21301A24A1370A2010314F016E0001C5B007E1401010714C000FEEC0380010F1307010E EB0F0039781CF81E9038387C3C393FF03FF03907C00FC027267CA427>I<13F0D803FCEB 01C0D8071EEB03E0D80E1F1307121C123C0038140F4914C01270A249131FD8F07E148012 E013FEC648133F160012015B5D0003147E5BA215FE00075C5BA214015DA314035D140700 03130FEBF01F3901F87FE038007FF7EB1FC7EB000F5DA2141F003F5C48133F92C7FC147E 147C007E13FC387001F8EB03E06C485A383C1F80D80FFEC8FCEA03F0233679A428>I<90 3903C0038090380FF007D91FF81300496C5A017F130E9038FFFE1E9038F83FFC3901F007 F849C65A495B1401C7485A4A5A4AC7FC141E5C5C5C495A495A495A49C8FC131E5B49131C 5B4848133C48481338491378000714F8390FF801F0391FFF07E0383E1FFFD83C0F5B0078 5CD8700790C7FC38F003FC38E000F021267BA422>I E /Fq 57 123 df<91393FE00FE0903A01FFF83FF8903A07E01EF83C903A1F800FF07E903A3F001FE0FE 017E133F4914C0485A1738484890381F8000ACB812C0A33B03F0001F8000B3A7486C497E B50083B5FCA32F357FB42D>11 DI<137813FCA212011203EA07F813E0EA0FC0EA1F 801300123C5A5A12400E0E71B326>19 D<003C13F0387E01F838FF03FCA2EB83FEA2EA7F 81383D80F600011306A40003130EEB000CA248131C00061318000E1338000C1330001C13 704813E0387001C00060138017177EB326>34 D<14C01301EB0380EB0F00130E5B133C5B 5BA2485A485AA212075B120F90C7FC5AA2121E123EA3123C127CA55AB0127CA5123C123E A3121E121FA27E7F12077F1203A26C7E6C7EA213787F131C7F130FEB0380EB01C0130012 4A79B71E>40 D<12C07E1270123C121C7E120F6C7E6C7EA26C7E6C7EA27F1378137C133C 133EA2131E131FA37F1480A5EB07C0B0EB0F80A514005BA3131E133EA2133C137C137813 F85BA2485A485AA2485A48C7FC120E5A123C12705A5A124A7CB71E>I<123C127EB4FCA2 1380A2127F123D1201A412031300A25A1206120E120C121C5A5A126009177A8715>44 DI<123C127E12FFA4127E123C08087A8715>I<13075B5B137FEA 07FFB5FC13BFEAF83F1200B3B3A2497E007FB51280A319327AB126>49 DI<123C127E12FFA4127E123C1200B0123C12 7E12FE12FFA3127F123F1203A412071206A3120E120C121C1238123012701260082F7A9F 15>59 D<15E0A34A7EA24A7EA34A7EA3EC0DFE140CA2EC187FA34A6C7EA202707FEC601F A202E07FECC00FA2D901807F1507A249486C7EA301066D7EA2010E80010FB5FCA2498001 18C77EA24981163FA2496E7EA3496E7EA20001821607487ED81FF04A7ED8FFFE49B512E0 A333367DB53A>65 DII< B77E16F016FE3A01FE0001FF00009138003FC0EE0FE0707E707E707E707E177E177FEF3F 80A2EF1FC0A3EF0FE0A418F0AA18E0A3171F18C0A21880173F18005F17FE5F4C5AEE07F0 4C5AEE3FC000014AB45AB748C7FC16F8168034337EB23B>II 73 D75 D77 DIII82 D<007FB712FEA390398007F001D87C00EC003E0078161E0070160EA20060160600E01607 A3481603A6C71500B3AB4A7E011FB512FCA330337DB237>84 DI87 D89 D91 D<0003130C48131C000E133848 137000181360003813E0003013C0EA700100601380A2EAE00300C01300A400DE137800FF 13FCEB83FEA2EA7F81A2383F00FC001E1378171774B326>II97 DII<153FEC0FFFA3EC007F81AEEB07F0EB3FFCEBFC0F3901F003 BF3907E001FF48487E48487F8148C7FCA25A127E12FEAA127E127FA27E6C6C5BA26C6C5B 6C6C4813803A03F007BFFC3900F81E3FEB3FFCD90FE0130026357DB32B>III<151F90391FC07F809039FFF8E3C03901F07FC73907E03F033A0FC01F 83809039800F8000001F80EB00074880A66C5CEB800F000F5CEBC01F6C6C48C7FCEBF07C 380EFFF8380C1FC0001CC9FCA3121EA2121F380FFFFEECFFC06C14F06C14FC4880381F00 01003EEB007F4880ED1F8048140FA56C141F007C15006C143E6C5C390FC001F83903F007 E0C6B51280D91FFCC7FC22337EA126>IIIIII<2703F01FE013FF00FF90267FF80313C0903BF1E07C0F 03E0903BF3803E1C01F02807F7003F387FD803FE1470496D486C7EA2495CA2495CB3486C 496C487EB53BC7FFFE3FFFF0A33C217EA041>I<3903F01FC000FFEB7FF09038F1E0FC90 38F3807C3907F7007EEA03FE497FA25BA25BB3486CEB7F80B538C7FFFCA326217EA02B> II<3903F03F8000FFEBFFE0 9038F3C0F89038F7007ED807FE7F6C48EB1F804914C049130F16E0ED07F0A3ED03F8A915 0716F0A216E0150F16C06D131F6DEB3F80160001FF13FC9038F381F89038F1FFE0D9F07F C7FC91C8FCAA487EB512C0A325307EA02B>I<903807F00390383FFC07EBFC0F3901F803 8F3807E001000F14DF48486CB4FC497F123F90C77E5AA25A5AA9127FA36C6C5B121F6D5B 000F5B3907E003BF3903F0073F3800F81EEB3FF8EB0FE090C7FCAAED7F8091380FFFFCA3 26307DA029>I<3803E07C38FFE1FF9038E38F809038E71FC0EA07EEEA03ECA29038FC0F 8049C7FCA35BB2487EB512E0A31A217FA01E>II<1330A51370A313F0A21201A212031207381FFFFEB5FCA23803F000AF 1403A814073801F806A23800FC0EEB7E1CEB1FF8EB07E0182F7FAD1E>III II<3A7FFF807FF8A33A07F8001FC00003EC0F800001EC070015066C6C5BA26D131C 017E1318A26D5BA2EC8070011F1360ECC0E0010F5BA2903807E180A214F3010390C7FC14 FBEB01FEA26D5AA31478A21430A25CA214E05CA2495A1278D8FC03C8FCA21306130EEA70 1CEA7838EA1FF0EA0FC025307F9F29>I<003FB512F0A2EB000F003C14E00038EB1FC000 30EB3F800070137F1500006013FE495A13035CC6485A495AA2495A495A49C7FC153013FE 485A12035B48481370485A001F14604913E0485A387F000348130F90B5FCA21C207E9F22 >I E /Fr 7 117 df65 D97 DI<903807FF80013F13F090B512FC3903FE01FE 4848487EEA0FF8EA1FF0EA3FE0A2007F6D5A496C5A153000FF91C7FCA9127F7FA2003FEC 07807F6C6C130F000FEC1F00D807FE133E3903FF80FCC6EBFFF8013F13E0010790C7FC21 217DA027>I<3901F81F8000FFEB7FF0ECFFF89038F9E3FC9038FBC7FE380FFF876C1307 A213FEEC03FCEC01F8EC0060491300B1B512F0A41F217EA024>114 D<9038FFE1C0000713FF5A383F803F387E000F14075A14037EA26C6CC7FC13FCEBFFE06C 13FC806CEBFF80000F14C06C14E0C6FC010F13F0EB007F140F00F0130714037EA26C14E0 6C13076CEB0FC09038C01F8090B5120000F913FC38E03FE01C217DA023>I<133CA5137C A313FCA21201A212031207001FB51280B6FCA3D807FCC7FCB0EC03C0A79038FE07801203 3901FF0F006C13FEEB3FFCEB0FF01A2F7EAE22>I E /Fs 84 124 df6 D11 DIII<1278 12FCA27E7EEA7F80121FEA0FC0EA07E0EA03F012001378133C131E13060F0F77B92A>18 D<133C137EA213FE1201EA03FC13F0EA07E0EA0FC0EA1F80EA1E005A5A5A12C00F0F6FB9 2A>I<121C127FEAFF80A8EA7F00AB123EAB121CABC7FCA8121C127FEAFF80A5EA7F0012 1C093C79BB17>33 D<001C131C007F137F39FF80FF80A26D13C0A3007F137F001C131C00 001300A40001130101801380A20003130301001300485B00061306000E130E485B485B48 5B006013601A197DB92A>I<121C127FEAFF80A213C0A3127F121C1200A412011380A212 0313005A1206120E5A5A5A12600A1979B917>39 D<146014E0EB01C0EB0380EB0700130E 131E5B5BA25B485AA2485AA212075B120F90C7FCA25A121EA2123EA35AA65AB2127CA67E A3121EA2121F7EA27F12077F1203A26C7EA26C7E1378A27F7F130E7FEB0380EB01C0EB00 E01460135278BD20>I<12C07E12707E7E7E120F6C7E6C7EA26C7E6C7EA21378A2137C13 3C133E131EA2131F7FA21480A3EB07C0A6EB03E0B2EB07C0A6EB0F80A31400A25B131EA2 133E133C137C1378A25BA2485A485AA2485A48C7FC120E5A5A5A5A5A13527CBD20>I<15 301578B3A6007FB812F8B912FCA26C17F8C80078C8FCB3A6153036367BAF41>43 D<121C127FEAFF80A213C0A3127F121C1200A412011380A2120313005A1206120E5A5A5A 12600A19798817>II<121C127FEAFF80A5EA7F00121C09097988 17>I<150C151E153EA2153C157CA2157815F8A215F01401A215E01403A215C01407A215 80140FA215005CA2141E143EA2143C147CA2147814F8A25C1301A25C1303A2495AA25C13 0FA291C7FC5BA2131E133EA2133C137CA2137813F8A25B1201A25B1203A25B1207A25B12 0FA290C8FC5AA2121E123EA2123C127CA2127812F8A25A12601F537BBD2A>IIIII<1538A2157815F8A2140114 031407A2140F141F141B14331473146314C313011483EB030313071306130C131C131813 301370136013C01201EA038013005A120E120C5A123812305A12E0B712F8A3C73803F800 AB4A7E0103B512F8A325397EB82A>I<0006140CD80780133C9038F003F890B5FC5D5D15 8092C7FC14FC38067FE090C9FCABEB07F8EB3FFE9038780F803907E007E090388003F049 6C7E12066E7EC87EA28181A21680A4123E127F487EA490C71300485C12E000605C127000 30495A00385C6C1303001E495A6C6C485A3907E03F800001B5C7FC38007FFCEB1FE0213A 7CB72A>II<12301238123E003FB612E0A316C05A16 8016000070C712060060140E5D151800E01438485C5D5DC712014A5A92C7FC5C140E140C 141C5CA25CA214F0495AA21303A25C1307A2130FA3495AA3133FA5137FA96DC8FC131E23 3B7BB82A>III<121C127FEAFF80 A5EA7F00121CC7FCB2121C127FEAFF80A5EA7F00121C092479A317>I<121C127FEAFF80 A5EA7F00121CC7FCB2121C127F5A1380A4127F121D1201A412031300A25A1206A2120E5A 121812385A1260093479A317>I<007FB812F8B912FCA3CCFCAEB912FCA36C17F836167B 9F41>61 D63 DI<1538A3157CA315FEA34A7EA34A6C7EA202077FEC063FA2020E7F EC0C1FA2021C7FEC180FA202387FEC3007A202707FEC6003A202C07F1501A2D901807F81 A249C77F167FA20106810107B6FCA24981010CC7121FA2496E7EA3496E7EA3496E7EA213 E0707E1201486C81D80FFC02071380B56C90B512FEA3373C7DBB3E>II<913A01FF800180020FEBE003027F13F8903A01FF807E07903A03FC000F0FD90FF0EB 039F4948EB01DFD93F80EB00FF49C8127F01FE153F12014848151F4848150FA248481507 A2485A1703123F5B007F1601A35B00FF93C7FCAD127F6DED0180A3123F7F001F16031800 6C7E5F6C7E17066C6C150E6C6C5D00001618017F15386D6C5CD91FE05C6D6CEB03C0D903 FCEB0F80902701FF803FC7FC9039007FFFFC020F13F002011380313D7BBA3C>III IIII<013FB512E0A390 39001FFC00EC07F8B3B3A3123FEA7F80EAFFC0A44A5A1380D87F005B0070131F6C5C6C49 5A6C49C7FC380781FC3801FFF038007F80233B7DB82B>IIIIIII82 DI<003FB812E0A3D9C003 EB001F273E0001FE130348EE01F00078160000701770A300601730A400E01738481718A4 C71600B3B0913807FF80011FB612E0A335397DB83C>IIII91 D<3901800180000313033907000700000E130E 485B0018131800381338003013300070137000601360A200E013E0485BA400CE13CE39FF 80FF806D13C0A3007F137FA2393F803F80390E000E001A1974B92A>II97 DIIII<14 7E903803FF8090380FC1E0EB1F8790383F0FF0137EA213FCA23901F803C091C7FCADB512 FCA3D801F8C7FCB3AB487E387FFFF8A31C3B7FBA19>IIIIIII<2703F00FF0EB1FE0 00FFD93FFCEB7FF8913AF03F01E07E903BF1C01F83803F3D0FF3800FC7001F802603F700 13CE01FE14DC49D907F8EB0FC0A2495CA3495CB3A3486C496CEB1FE0B500C1B50083B5FC A340257EA445>I<3903F00FF000FFEB3FFCECF03F9039F1C01F803A0FF3800FC03803F7 0013FE496D7EA25BA35BB3A3486C497EB500C1B51280A329257EA42E>II<3903F01FE000FFEB7FF89038F1E07E9039F3801F803A07F7000FC0D803FEEB07E049 EB03F04914F849130116FC150016FEA3167FAA16FEA3ED01FCA26DEB03F816F06D13076D EB0FE001F614C09039F7803F009038F1E07E9038F0FFF8EC1FC091C8FCAB487EB512C0A3 28357EA42E>II<3807E01F00FFEB7FC09038E1E3E09038E387F0380FE707EA03E613 EE9038EC03E09038FC0080491300A45BB3A2487EB512F0A31C257EA421>II<1318A51338A31378A3 13F8120112031207001FB5FCB6FCA2D801F8C7FCB215C0A93800FC011580EB7C03017E13 006D5AEB0FFEEB01F81A347FB220>IIIIII<003FB512FCA2EB8003D83E0013F8003CEB 07F00038EB0FE012300070EB1FC0EC3F800060137F150014FE495AA2C6485A495AA2495A 495A495AA290387F000613FEA2485A485A0007140E5B4848130C4848131CA24848133C48 C7127C48EB03FC90B5FCA21F247EA325>II E /Ft 17 119 df65 D<91B612F0A25F020101C0C7FC6E5B4A90C8FCA25DA314035D A314075DA3140F5DA3141F5DA3143F5DA3147F5DA314FF92C9FCA35B5CA3010316104A15 38A21878010716705C18F018E0010F15015C18C01703011F15074A1580170FA2013FED1F 004A5C5F017F15FE16034A130F01FFEC7FFCB8FCA25F35447AC33D>76 D83 D97 D99 DII<14FE137FA3EB01FC13001301A25CA213 03A25CA21307A25CA2130FA25CA2131FA25C157F90393F83FFC091388F81F091381E00F8 02387F4948137C5C4A137EA2495A91C7FCA25B484814FE5E5BA2000314015E5BA2000714 035E5B1507000F5DA249130F5E001F1678031F1370491480A2003F023F13F0EE00E090C7 FC160148023E13C01603007E1680EE070000FEEC1E0FED1F1E48EC0FF80038EC03E02D46 7AC432>104 D<143C147E14FE1301A3EB00FC14701400AE137C48B4FC3803C780380703 C0000F13E0120E121C13071238A21278EA700F14C0131F00F0138012E0EA003F1400A25B 137EA213FE5B12015BA212035B141E0007131C13E0A2000F133CEBC038A21478EB807014 F014E0EB81C0EA0783EBC7803803FE00EA00F8174378C11E>I<16F0ED03F8A21507A316 F0ED01C092C7FCAEEC01F0EC07FCEC1E1EEC380F0270138014E0130114C0EB0380010713 1F1400A2130E153F131E011C140090C7FC5DA2157EA215FEA25DA21401A25DA21403A25D A21407A25DA2140FA25DA2141FA25DA2143FA292C7FCA25C147EA214FE001C5B127F4848 5A495AA248485A495AD8F81FC8FCEA707EEA3FF8EA0FC0255683C11E>I108 DIII114 D<1470EB01F8A313035CA313075CA3130F5CA3131F5CA2 007FB512E0B6FC15C0D8003FC7FCA25B137EA313FE5BA312015BA312035BA312075BA312 0F5BA2EC0780001F140013805C140E003F131EEB001C143C14385C6C13F0495A6C485AEB 8780D807FEC7FCEA01F81B3F78BD20>116 D<017C143848B414FC3A03C78001FE380703 C0000F13E0120E001C14000107147E1238163E1278D8700F141E5C131F00F049131C12E0 EA003F91C7123C16385B137E167801FE14705BA216F0000115E05B150116C0A24848EB03 80A2ED0700A2150E12015D6D5B000014786D5B90387C01E090383F0780D90FFFC7FCEB03 F8272D78AB2D>118 D E /Fu 36 120 df45 D<157815FC14031407141F14FF130F0007B5FCB6FCA2147F13F0EAF800C7FCB3B3B3A600 7FB712FEA52F4E76CD43>49 DI<91380FFFC091B512 FC0107ECFF80011F15E090263FF8077F9026FF800113FC4848C76C7ED803F86E7E491680 D807FC8048B416C080486D15E0A4805CA36C17C06C5B6C90C75AD801FC1680C9FC4C1300 5FA24C5A4B5B4B5B4B13C04B5BDBFFFEC7FC91B512F816E016FCEEFF80DA000713E00301 13F89238007FFE707E7013807013C018E07013F0A218F8A27013FCA218FEA2EA03E0EA0F F8487E487E487EB57EA318FCA25E18F891C7FC6C17F0495C6C4816E001F04A13C06C484A 1380D80FF84A13006CB44A5A6CD9F0075BC690B612F06D5D011F1580010302FCC7FCD900 1F1380374F7ACD43>I<177C17FEA2160116031607160FA2161F163F167FA216FF5D5DA2 5D5DED1FBFED3F3F153E157C15FCEC01F815F0EC03E01407EC0FC01580EC1F005C147E14 7C5C1301495A495A5C495A131F49C7FC133E5B13FC485A5B485A1207485A485A90C8FC12 3E127E5ABA12C0A5C96C48C7FCAF020FB712C0A53A4F7CCE43>III<932601FFFCEC01C0047FD9FFC013030307B600F81307033F03FE131F92 B8EA803F0203DAE003EBC07F020F01FCC7383FF0FF023F01E0EC0FF94A01800203B5FC49 4848C9FC4901F8824949824949824949824949824990CA7E494883A2484983485B1B7F48 5B481A3FA24849181FA3485B1B0FA25AA298C7FC5CA2B5FCAE7EA280A2F307C07EA36C7F A21B0F6C6D1980A26C1A1F6C7F1C006C6D606C6D187EA26D6C606D6D4C5A6D6D16036D6D 4C5A6D6D4C5A6D01FC4C5A6D6DEE7F806D6C6C6C4BC7FC6E01E0EC07FE020F01FEEC1FF8 0203903AFFE001FFF0020091B612C0033F93C8FC030715FCDB007F14E0040101FCC9FC52 5479D261>67 D69 DI73 D77 DI<93380FFF C00303B6FC031F15E092B712FC0203D9FC0013FF020F01C0010F13C0023F90C7000313F0 DA7FFC02007F494848ED7FFE4901E0ED1FFF49496F7F49496F7F4990C96C7F4985494870 7F4948707FA24849717E48864A83481B804A83481BC0A2481BE04A83A2481BF0A3484971 13F8A5B51AFCAF6C1BF86E5FA46C1BF0A26E5F6C1BE0A36C6D4D13C0A26C6D4D1380A26C 1B006C6D4D5A6E5E6C626D6C4C5B6D6D4B5B6D6D4B5B6D6D4B5B6D6D4B5B6D6D4B90C7FC 6D6D4B5A6D01FF02035B023F01E0011F13F0020F01FC90B512C0020390B7C8FC020016FC 031F15E0030392C9FCDB001F13E0565479D265>II82 D<003FBC1280A59126C0003F9038C0007F49C71607D87FF8060113C0 01E08449197F49193F90C8171FA2007E1A0FA3007C1A07A500FC1BE0481A03A6C994C7FC B3B3AC91B912F0A553517BD05E>84 D97 D<913801FFF8021FEBFF8091B612F0010315FC010F9038C00FFE 903A1FFE0001FFD97FFC491380D9FFF05B4817C048495B5C5A485BA2486F138091C7FC48 6F1300705A4892C8FC5BA312FFAD127F7FA27EA2EF03E06C7F17076C6D15C07E6E140F6C EE1F806C6DEC3F006C6D147ED97FFE5C6D6CEB03F8010F9038E01FF0010390B55A010015 80023F49C7FC020113E033387CB63C>99 D<4DB47E0407B5FCA5EE001F1707B3A4913801 FFE0021F13FC91B6FC010315C7010F9038E03FE74990380007F7D97FFC0101B5FC49487F 4849143F484980485B83485B5A91C8FC5AA3485AA412FFAC127FA36C7EA37EA26C7F5F6C 6D5C7E6C6D5C6C6D49B5FC6D6C4914E0D93FFED90FEFEBFF80903A0FFFC07FCF6D90B512 8F0101ECFE0FD9003F13F8020301C049C7FC41547CD24B>I<913803FFC0023F13FC49B6 FC010715C04901817F903A3FFC007FF849486D7E49486D7E4849130F48496D7E48178048 497F18C0488191C7FC4817E0A248815B18F0A212FFA490B8FCA318E049CAFCA6127FA27F 7EA218E06CEE01F06E14037E6C6DEC07E0A26C6DEC0FC06C6D141F6C6DEC3F806D6CECFF 00D91FFEEB03FE903A0FFFC03FF8010390B55A010015C0021F49C7FC020113F034387CB6 3D>IIII<137F497E000313E0487FA2487FA76C5BA26C5BC613806DC7FC90C8FCADEB3FF0B5 FCA512017EB3B3A6B612E0A51B547BD325>I107 DIII<913801FFE0021F13FE91B612C00103 15F0010F9038807FFC903A1FFC000FFED97FF86D6C7E49486D7F48496D7F48496D7F4A14 7F48834890C86C7EA24883A248486F7EA3007F1880A400FF18C0AC007F1880A3003F1800 6D5DA26C5FA26C5F6E147F6C5F6C6D4A5A6C6D495B6C6D495B6D6C495BD93FFE011F90C7 FC903A0FFF807FFC6D90B55A010015C0023F91C8FC020113E03A387CB643>I<90397FE0 03FEB590380FFF80033F13E04B13F09238FE1FF89139E1F83FFC0003D9E3E013FEC6ECC0 7FECE78014EF150014EE02FEEB3FFC5CEE1FF8EE0FF04A90C7FCA55CB3AAB612FCA52F36 7CB537>114 D<903903FFF00F013FEBFE1F90B7FC120348EB003FD80FF81307D81FE013 0148487F4980127F90C87EA24881A27FA27F01F091C7FC13FCEBFFC06C13FF15F86C14FF 16C06C15F06C816C816C81C681013F1580010F15C01300020714E0EC003F030713F01501 0078EC007F00F8153F161F7E160FA27E17E07E6D141F17C07F6DEC3F8001F8EC7F0001FE EB01FE9039FFC00FFC6DB55AD8FC1F14E0D8F807148048C601F8C7FC2C387CB635>I<14 3EA6147EA414FEA21301A313031307A2130F131F133F13FF5A000F90B6FCB8FCA426003F FEC8FCB3A9EE07C0AB011FEC0F8080A26DEC1F0015806DEBC03E6DEBF0FC6DEBFFF86D6C 5B021F5B020313802A4D7ECB34>IIII E /Fv 16 124 df<140C141C1438147014E0EB01C01303EB0780EB0F00A2131E5BA2 5B13F85B12015B1203A2485AA3485AA348C7FCA35AA2123EA2127EA4127CA312FCB3A212 7CA3127EA4123EA2123FA27EA36C7EA36C7EA36C7EA212017F12007F13787FA27F7FA2EB 0780EB03C01301EB00E014701438141C140C166476CA26>40 D<12C07E12707E7E7E120F 6C7E6C7EA26C7E6C7EA21378137C133C133E131E131FA2EB0F80A3EB07C0A3EB03E0A314 F0A21301A214F8A41300A314FCB3A214F8A31301A414F0A21303A214E0A3EB07C0A3EB0F 80A3EB1F00A2131E133E133C137C13785BA2485A485AA2485A48C7FC120E5A5A5A5A5A16 647BCA26>I<121EEA7F8012FF13C0A213E0A3127FEA1E601200A413E013C0A312011380 120313005A1206120E5A5A5A12600B1D78891B>44 D<121EEA7F80A2EAFFC0A4EA7F80A2 EA1E000A0A78891B>46 D<143014F013011303131F13FFB5FC13E713071200B3B3B0497E 497E007FB6FCA3204278C131>49 DI< 49B4FC010F13E0013F13FC9038FE01FE3A01F0007F80D803C0EB3FC048C7EA1FE0120EED 0FF0EA0FE0486C14F8A215077F5BA26C48130FEA03C0C813F0A3ED1FE0A2ED3FC01680ED 7F0015FE4A5AEC03F0EC1FC0D90FFFC7FC15F090380001FCEC007FED3F80ED1FC0ED0FE0 16F0ED07F816FC150316FEA2150116FFA3121EEA7F80487EA416FE491303A2007EC713FC 00701407003015F80038140F6C15F06CEC1FE06C6CEB3FC0D803E0EB7F803A01FE01FE00 39007FFFF8010F13E0010190C7FC28447CC131>I54 D<14FF010713E0011F13F890387F00FE01FC133FD801F0EB1F804848EB0FC049EB07E000 07EC03F048481301A290C713F8481400A47FA26D130116F07F6C6CEB03E013FC6C6CEB07 C09039FF800F806C9038C01F006CEBF03EECF87839007FFEF090383FFFC07F01077F6D13 F8497F90381E7FFFD97C1F1380496C13C02601E00313E048486C13F000079038007FF848 48EB3FFC48C7120F003EEC07FE150148140016FF167F48153FA2161FA56C151E007C153E A2007E153C003E157C6C15F86DEB01F06C6CEB03E06C6CEB07C0D803F8EB1F80C6B4EBFF 0090383FFFFC010F13F00101138028447CC131>56 D<14FF010713E0011F13F890387F80 FC9038FC007E48487F4848EB1F804848EB0FC0000FEC07E0485AED03F0485A16F8007F14 0190C713FCA25AA216FE1500A516FFA46C5CA36C7E5D121F7F000F5C6C6C1306150E6C6C 5B6C6C5BD8007C5B90383F01E090390FFF80FE903801FE0090C8FC150116FCA4ED03F8A2 16F0D80F801307486C14E0486C130F16C0ED1F80A249EB3F0049137E001EC75A001C495A 000F495A3907E01FE06CB51280C649C7FCEB1FF028447CC131>I108 D<3901FC01FE00FF903807FFC09138 1E07F091383801F8000701707F0003EBE0002601FDC07F5C01FF147F91C7FCA25BA35BB3 A8486CECFF80B5D8F83F13FEA32F2C7DAB36>110 DI<3901FC03FC00FF90380FFF8091383C07E091387001F83A07FDE000FE000101 80137F01FFEC3F8091C7EA1FC04915E049140F17F0160717F8160317FCA3EE01FEABEE03 FCA3EE07F8A217F0160F6D15E0EE1FC06D143F17806EEB7E00D9FDC05B9039FCF003F891 383C0FE091381FFF80DA03FCC7FC91C9FCAE487EB512F8A32F3F7DAB36>I118 D123 D E /Fw 18 120 df<121FEA3F80EA7FC0EAFFE0A5EA7FC0 EA3F80EA1F000B0B6C8A33>46 D<167816F8ED01FCA21503A2ED07F8A2ED0FF0A2ED1FE0 A216C0153FA2ED7F80A2EDFF00A24A5AA25D1403A24A5AA24A5AA24A5AA25D143FA24A5A A24AC7FCA2495AA25C1303A2495AA2495AA25C131FA2495AA2495AA249C8FCA25B1201A2 485AA2485AA2485AA25B121FA2485AA2485AA248C9FCA25AA2127CA2264D7AC433>I<12 1FEA3F80EA7FC0EAFFE0A5EA7FC0EA3F80EA1F00C7FCB3A3121FEA3F80EA7FC0EAFFE0A5 EA7FC0EA3F80EA1F000B2B6CAA33>58 D97 DIIII104 D<14E0EB03F8A2497EA36D5AA2EB00E091 C8FCAA383FFFF8487FA47EEA0001B3AD007FB612C0B712E016F0A216E06C15C0243E78BD 33>I<1570EC01FCA2EC03FEA3EC01FCA2EC00701500AA90383FFFFC4913FE90B5FCA27F 7F90C7FCB3B3A9140115FCA21218007EEB03F81407B414F0140F9038803FE090B512C06C 14806C14006C5B6C13F8000113E01F557BBD33>I111 DI114 D<90381FFE0F90B5EA8F80000314FF 120F5A5AEBF007387F800190C7FC00FE147F5A153FA37E007FEC1F0001C090C7FCEA3FF8 EBFFC06C13FF6C14E0000314F8C680011F13FF01001480020713C0EC007FED1FE0007C14 0F00FEEC07F01503A27EA27F15076D14E06D130F6DEB3FC09038FE01FF90B61280160000 FD5C00FC14F8D8F83F13E0D8780790C7FC242E79AC33>III<3B7FFF8007FF F8B56C4813FC6E5AA24A7E6C496C13F8D80FC0C7EA0FC06D141F00071680A56D143F0003 1600A3EC0FC0EC1FE0A23A01F83FF07EA3EC7FF8147CA20000157C9039FCFCFCFCA3ECF8 7CA2017C5C017D137EECF03EA2017F133FA26D486C5AA3ECC00F90390F8007C02E2B7EAA 33>119 D E /Fx 18 118 df<1538A3157CA315FEA34A7EA34A6C7EA202077FEC063FA2 020E7FEC0C1FA2021C7FEC180FA202387FEC3007A202707FEC6003A202C07F1501A2D901 807F81A249C77F167FA20106810107B6FCA24981010CC7121FA2496E7EA3496E7EA3496E 7EA213E0707E1201486C81D80FFC02071380B56C90B512FEA3373C7DBB3E>65 D68 DI73 D<013FB512E0A39039001FFC00 EC07F8B3B3A3123FEA7F80EAFFC0A44A5A1380D87F005B0070131F6C5C6C495A6C49C7FC 380781FC3801FFF038007F80233B7DB82B>I79 D83 D97 D99 D101 D<147E903803FF8090380FC1E0EB1F8790383F0FF0137EA213FCA23901F8 03C091C7FCADB512FCA3D801F8C7FCB3AB487E387FFFF8A31C3B7FBA19>I 105 D108 D<3903F00FF000FFEB3FFCECF03F9039F1C01F803A0FF3800FC03803F70013FE496D7EA2 5BA35BB3A3486C497EB500C1B51280A329257EA42E>110 DI<3807E0 1F00FFEB7FC09038E1E3E09038E387F0380FE707EA03E613EE9038EC03E09038FC008049 1300A45BB3A2487EB512F0A31C257EA421>114 D<1318A51338A31378A313F812011203 1207001FB5FCB6FCA2D801F8C7FCB215C0A93800FC011580EB7C03017E13006D5AEB0FFE EB01F81A347FB220>116 DI E end TeXDict begin 21 0 bop 523 318 2865 4 v 1150 500 a Fx(E)35 b(l)17 b(e)26 b(c)h(t)d(r)f(o)30 b(n)k(i)16 b(c)78 b(J)25 b(o)30 b(u)j(r)23 b(n)34 b(a)c(l)68 b(o)23 b(f)70 b(S)28 b(A)46 b(D)g(I)22 b(O)1161 666 y Fw(http://www.dc.uba.ar/sadio/)q(ejs)q(/)1316 832 y Fv(v)m(ol.)32 b(1,)g(no.)h(1,)f(pp.)h(21{36)f(\(1998\))p 523 944 V 662 1260 a Fu(New)45 b(Results)h(on)f(F)-11 b(air)45 b(Multi-threaded)g(P)l(aging)1299 1459 y Ft(A)n(lejandr)-5 b(o)34 b(Str)-5 b(ejilevich)34 b(de)h(L)-5 b(oma)523 1741 y Fs(Departamen)n(to)21 b(de)g(Computaci\023)-42 b(on,)23 b(F)-7 b(acultad)21 b(de)h(Ciencias)f(Exactas)f(y)h (Naturales,)h(Uni-)523 1841 y(v)n(ersidad)17 b(de)i(Buenos)f(Aires,)j (P)n(ab)r(ell\023)-42 b(on)17 b(I,)i(Ciudad)g(Univ)n(ersitaria,)g (\(1428\))e(Capital)h(F)-7 b(ede-)523 1940 y(ral,)27 b(Argen)n(tina;)g(e-mail:)36 b(asdel@dc.uba.ar.)1786 2214 y Fr(Abstract)846 2345 y Fq(The)18 b(Multi-threaded)g(P)n(aging)h (problem)f(\(MTP\))h(w)n(as)g(in)n(tro)r(duced)e(as)i(a)g(gener-)731 2436 y(alization)25 b(of)f(P)n(aging)h(for)f(the)f(case)h(where)g (there)f(are)h(man)n(y)e(threads)h(of)h(requests.)731 2527 y(This)31 b(mo)r(dels)h(situations)g(in)f(whic)n(h)g(the)g (requests)g(come)g(from)g(more)g(than)g(one)731 2619 y(indep)r(enden)n(t)25 b(source.)40 b(A)n(t)26 b(eac)n(h)h(step)g(it)g (is)h(necessary)g(to)f(decide)g(whic)n(h)g(request)731 2710 y(to)c(serv)n(e)g(among)g(sev)n(eral)h(p)r(ossibilities,)i(and)d (also)h(\(as)g(in)f(normal)f(P)n(aging\))j(whic)n(h)731 2801 y(page)34 b(of)h(fast)f(memory)e(to)i(remo)n(v)n(e)f(on)h(a)g (page)h(fault.)59 b(In)33 b(the)h(fair)h(v)n(ersion)f(of)731 2893 y(the)26 b(problem)f(an)n(y)h(algorithm)g(m)n(ust)f(guaran)n(tee)i (that)f(the)g(next)f(request)h(of)i(eac)n(h)731 2984 y(thread)d(will)i(b)r(e)f(serv)n(ed)f(within)h(a)g(predetermined)e (\014nite)h(time.)846 3075 y(In)32 b(this)h(pap)r(er)f(w)n(e)h(reduce)g (the)f(existing)h(gaps)h(b)r(et)n(w)n(een)e(the)g(kno)n(wn)h(lo)n(w)n (er)731 3167 y(and)f(upp)r(er)f(b)r(ounds)h(for)h(the)f(comp)r(etitiv)n (eness)g(of)h(on-line)f(algorithms)h(for)g(the)731 3258 y(fair)26 b(v)n(ersion)f(of)h(MTP.)35 b(W)-6 b(e)25 b(treat)h(some)e (particular)i(situations,)h(with)e(\014nite)g(and)731 3349 y(in\014nite)20 b(input)g(sequences.)33 b(W)-6 b(e)21 b(pro)n(v)n(e)f(higher)h(lo)n(w)n(er)h(b)r(ounds)e(and)h(presen)n(t)f (a)h(new)731 3440 y(on-line)29 b(algorithm.)44 b(W)-6 b(e)28 b(close)j(the)d(gap)h(for)h(the)e(case)i(in)f(whic)n(h)g(the)f (cac)n(he)i(can)731 3532 y(hold)25 b(only)g(one)h(page;)g(surprisingly) -6 b(,)26 b(w)n(e)g(obtain)g(di\013eren)n(t)f(b)r(ounds)g(for)h(ev)n (en)f(and)731 3623 y(o)r(dd)h(n)n(um)n(b)r(er)f(of)j(sequences;)g(w)n (e)g(pro)n(v)n(e)e(that)h(an)n(y)f(lazy)h(algorithm)h(ac)n(hiev)n(es)f (the)731 3714 y(on-line)e(lo)n(w)n(er)i(b)r(ound)e(when)g(the)h(n)n(um) n(b)r(er)d(of)k(sequences)e(is)i(o)r(dd.)p 523 4481 V 523 4581 a(Researc)n(h)k(supp)r(orted)g(in)f(part)h(b)n(y)f(EC)i(pro)t (ject)g(D)n(YND)n(A)-6 b(T)g(A)28 b(under)i(program)h(KIT,)g(and)f(b)n (y)523 4680 y(UBA)n(CyT)f(pro)t(jects)h(\\Algoritmos)g(E\014cien)n(tes) g(para)f(Problemas)h(On-line)e(con)h(Aplicaciones")523 4780 y(and)g(\\Mo)r(delos)i(y)e(T)n(\023)-36 b(ecnicas)31 b(de)e(Optimizaci\023)-38 b(on)30 b(Com)n(binatoria".)46 b(A)29 b(preliminary)g(v)n(ersion)g(of)523 4880 y(this)d(pap)r(er)f (app)r(eared)h(in)g([11)q(,)g(12)q(].)p eop 22 1 bop 523 324 a Fs(A.)28 b(Strejilevic)n(h)g(de)f(Loma,)g Fp(F)-6 b(air)30 b(Multi-thr)l(e)l(ade)l(d)h(Paging)7 b Fs(,)29 b Fo(EJS)p Fs(,)f(1\(1\))f(21{36)f(\(1998\))10 b(22)523 614 y Fu(1)135 b(In)l(tro)t(duction)523 796 y Fs(The)23 b Fp(Paging)h Fs(problem)f(consists)f(of)h(managing)e(a)i (t)n(w)n(o-lev)n(el)e(memory)-7 b(,)23 b(one)g(of)f(them)i(with)523 896 y(limited)k(capacit)n(y)e(and)h(fast)g(access)f(\(the)i(cac)n(he\)) f(and)g(the)g(other)g(one)g(with)g(slo)n(w)g(access)523 995 y(but)d(p)r(oten)n(tially)g(unlimited)g(capacit)n(y)-7 b(.)35 b(A)23 b Fp(Paging)28 b(algorithm)d Fs(is)e(faced)h(with)g(a)f (sequence)523 1095 y(of)29 b(page)g(references.)42 b(A)n(t)29 b(eac)n(h)g(step)h(the)g(algorithm)e(m)n(ust)h(ensure)g(that)h(the)g (requested)523 1195 y(page)k(is)h(in)g(fast)g(memory)-7 b(,)36 b(p)r(erhaps)e(evicting)h(another)f(page)g(to)h(mak)n(e)f(ro)r (om)g(for)g(the)523 1294 y(incoming)29 b(one.)43 b(A)30 b Fp(p)l(age)j(fault)d Fs(o)r(ccurs)e(eac)n(h)h(time)h(a)g(page)e(m)n (ust)i(b)r(e)g(brough)n(t)f(in)n(to)g(fast)523 1394 y(memory)-7 b(.)63 b(The)36 b(goal)g(of)g(the)h(P)n(aging)d(algorithm)i(is)g(to)g (minimize)i(the)e(total)h(n)n(um)n(b)r(er)523 1494 y(of)c(page)f (faults)h(o)n(v)n(er)e(the)i(sequence)f(of)h(requests.)51 b(An)34 b Fp(on-line)h(algorithm)f Fs(for)e(P)n(aging)523 1593 y(m)n(ust)25 b(decide)g(whic)n(h)g(page)g(to)g(evict)g(without)g (kno)n(wledge)f(of)h(future)h(requests,)e(while)i(an)523 1693 y Fp(o\013-line)32 b(algorithm)g Fs(can)d(decide)g(based)h(on)f (the)h(whole)f(sequence.)43 b(On-line)29 b(algorithms)523 1792 y(for)g(P)n(aging)e(ha)n(v)n(e)h(b)r(een)h(studied)h(from)e(a)h Fp(c)l(omp)l(etitive)j(analysis)f Fs(p)r(oin)n(t)e(of)g(view)g(in)g ([10)o(],)523 1892 y(comparing)f(their)h(p)r(erformance)f(to)h(that)g (of)g(the)h(optimal)f(o\013-line)g(algorithm.)40 b(In)29 b(that)523 1992 y(w)n(ork)j(it)h(is)g(sho)n(wn)f(that,)j(if)f(the)f (cac)n(he)f(can)h(hold)g Fn(k)j Fs(pages,)d(no)g(deterministic)g (on-line)523 2091 y(algorithm)22 b(can)h(b)r(e)h(b)r(etter)g(than)g Fn(k)s Fs(-comp)r(etitiv)n(e,)g(that)f(is,)i(guaran)n(tee)c(less)i (than)h Fn(k)i Fs(times)523 2191 y(the)31 b(optimal)g(o\013-line)g(n)n (um)n(b)r(er)f(of)h(page)f(faults)h(on)g(ev)n(ery)f(input;)j(b)r (esides,)f(it)f(is)g(sho)n(wn)523 2291 y(that)i(kno)n(wn)g(on-line)f (algorithms)g(suc)n(h)g(as)h(Least-Recen)n(tly-Used)e(\(LR)n(U\))j(and) f(First-)523 2390 y(In-First-Out)27 b(\(FIF)n(O\))h(ac)n(hiev)n(e)e (that)i(b)r(ound.)648 2490 y(The)g Fp(Multi-thr)l(e)l(ade)l(d)j(Paging) e Fs(problem)f(\(MTP\))g(w)n(as)f(in)n(tro)r(duced)h(as)f(a)h (generaliza-)523 2589 y(tion)21 b(of)h(P)n(aging)d(for)i(the)g(case)g (in)g(whic)n(h)g(there)g(is)g(not)h(just)g(one)e(sequence)h(of)g (requests)g(but)523 2689 y(p)r(ossibly)i(man)n(y)g(threads)f([5,)h(6].) 35 b(This)24 b(mo)r(dels)f(situations)g(in)g(whic)n(h)h(the)f(requests) g(come)523 2789 y(from)29 b(more)g(than)h(one)g(indep)r(enden)n(t)g (source,)f(as)g(in)h(m)n(ulti-tasking)f(systems)g(where)h(all)523 2888 y(pro)r(cesses)22 b(indep)r(enden)n(tly)j(presen)n(t)e(their)h (requests)f(of)h(memory)f(pages)g(to)h(the)g(manager)523 2988 y(of)33 b(fast)g(memory)-7 b(.)51 b(A)n(t)34 b(eac)n(h)e(step)h (it)g(is)f(necessary)g(to)g(decide)h(whic)n(h)g(request)f(to)h(serv)n (e)523 3088 y(among)d(sev)n(eral)g(p)r(ossibilities,)j(and)e(also)g (\(as)g(in)g(normal)g(P)n(aging\))f(whic)n(h)h(page)g(of)g(fast)523 3187 y(memory)g(to)i(remo)n(v)n(e)d(on)i(a)g(page)f(fault.)52 b(The)32 b(total)g(n)n(um)n(b)r(er)g(of)g(page)g(faults)g(dep)r(ends) 523 3287 y(therefore)24 b(not)i(only)e(on)h(the)h(strategy)e(used)h(to) g(determine)g(ho)n(w)g(eac)n(h)f(request)h(is)g(serv)n(ed)523 3386 y(but)h(when)g(\(in)g(whic)n(h)g(order\))f(this)h(is)f(done.)36 b(Moreo)n(v)n(er,)24 b(in)i(some)f(cases)f(ev)n(en)i(the)g(set)f(of)523 3486 y(requests)d(that)h(will)g(ev)n(en)n(tually)f(b)r(e)i(serv)n(ed)d (dep)r(ends)j(on)e(the)i(particular)d(algorithm)h(that)523 3586 y(is)27 b(used.)36 b(As)27 b(it)g(can)g(b)r(e)g(seen,)g(in)g(MTP)f (there)h(is)f(no)h(notion)f(of)h(\\sequence)f(of)h(requests")523 3685 y(but)g(a)e(more)h(complex)f(pattern)h(that)g(is)g(not)g(captured) g(b)n(y)g(the)g(most)g(general)f(classes)f(of)523 3785 y(on-line)32 b(problems)g(prop)r(osed)f(in)i(the)g(literature)f(\(lik)n (e)g(Metrical)g(T)-7 b(ask)32 b(Systems)g([4])g(or)523 3885 y(Request-Answ)n(er)26 b(Games)i([2)o(,)g(9)o(]\).)648 3984 y(Tw)n(o)d(v)n(ersions)g(of)h(MTP)g(w)n(ere)g(presen)n(ted)g(in)g ([6].)37 b(In)26 b(the)h(\014rst)f(one,)h(the)f(goal)f(is)i(just)523 4084 y(to)22 b(minimize)h(the)g(n)n(um)n(b)r(er)e(of)i(page)e(faults)h (done)g(while)h(serving)e(a)h(set)g(of)g Fn(w)j Fs(sequences)c(of)523 4184 y(requests.)36 b(In)26 b(the)g(second)g(one,)g Fp(fairness)h Fs(restrictions)d(are)i(imp)r(osed,)g(so)f(an)n(y)h(algorithm)523 4283 y(m)n(ust)36 b(guaran)n(tee)f(that)h(the)g(next)h(request)e(of)h (eac)n(h)g(thread)f(will)i(b)r(e)f(serv)n(ed)f(within)i(a)523 4383 y(predetermined)20 b(\014nite)i(time.)35 b(F)-7 b(or)20 b(eac)n(h)g(one)g(of)h(these)g(t)n(w)n(o)e(problems,)j (\014nite)f(and)g(in\014nite)523 4482 y(sequences)37 b(of)h(requests)g(can)f(b)r(e)i(considered.)67 b(In)39 b([6)o(])g(it)f(w)n(as)f(pro)n(v)n(ed)g(that)h(the)h(only)523 4582 y(case)31 b(in)i(whic)n(h)f(there)g(exist)g(comp)r(etitiv)n(e)g (on-line)f(algorithms)g(for)h(the)g(fair)g(v)n(ersion)e(is)523 4682 y(when)h(fairness)e(restrictions)g(are)h(so)g(tigh)n(t)g(that)h (enforce)f(serving)f(one)h(request)g(of)g(eac)n(h)523 4781 y(thread)g(in)h(a)f(cyclic)g(w)n(a)n(y)-7 b(.)45 b(F)-7 b(or)29 b(that)i(case,)g(a)f(\()p Fn(k)23 b Fs(+)d Fn(w)r Fs(\)-comp)r(etitiv)n(e)31 b(on-line)g(algorithm)523 4881 y(w)n(as)j(prop)r(osed,)h(and)f(a)g(lo)n(w)n(er)f(b)r(ound)i(of)g Fn(k)i Fs(for)d(the)h(comp)r(etitiv)n(eness)g(of)f(an)n(y)g(on-line)p eop 23 2 bop 523 324 a Fs(A.)28 b(Strejilevic)n(h)g(de)f(Loma,)g Fp(F)-6 b(air)30 b(Multi-thr)l(e)l(ade)l(d)h(Paging)7 b Fs(,)29 b Fo(EJS)p Fs(,)f(1\(1\))f(21{36)f(\(1998\))10 b(23)523 614 y(algorithm)26 b(w)n(as)h(obtained.)648 714 y(In)36 b(this)h(pap)r(er)f(w)n(e)g(address)f(some)h(of)g(the)h (problems)f(that)g(w)n(ere)g(left)h(op)r(en)f(when)523 814 y(MTP)28 b(w)n(as)f(in)n(tro)r(duced.)39 b(More)27 b(precisely)-7 b(,)28 b(for)g(some)f(particular)g(situations)h(of)g (the)h(fair)523 913 y(v)n(ersion)20 b(of)i(MTP)g(w)n(e)g(reduce)f(the)i (existing)e(gaps)g(b)r(et)n(w)n(een)h(the)h(kno)n(wn)e(lo)n(w)n(er)f (and)i(upp)r(er)523 1013 y(b)r(ounds.)36 b(W)-7 b(e)25 b(treat)g(sev)n(eral)e(cases:)34 b(The)25 b(\014rst)g(one)f(is)h(the)g (case)f(in)h(whic)n(h)g(the)g(cac)n(he)f(can)523 1112 y(hold)k(only)f(one)g(page)g(\()p Fn(k)g Fs(=)22 b(1\))28 b(and)g(the)g(n)n(um)n(b)r(er)f(of)h(sequences)f(is)g(ev)n(en;)h(w)n(e) f(raise)g(from)523 1212 y(1)f(to)f Fn(w)18 b Fs(+)d(1)25 b(the)i(kno)n(wn)e(lo)n(w)n(er)f(b)r(ound,)j(and)f(therefore)f(the)h (on-line)f(algorithm)g(from)h([6)o(])523 1312 y(is)37 b(strongly)g(comp)r(etitiv)n(e)g(\(optimal\).)67 b(In)38 b(the)g(second)f(case)f(again)h(w)n(e)g(ha)n(v)n(e)f Fn(k)43 b Fs(=)c(1,)523 1411 y(but)30 b(no)n(w)e(w)n(e)h(consider)f(an) h(o)r(dd)h Fn(w)r Fs(;)h(in)e(this)h(case)e(the)i(new)f(lo)n(w)n(er)f (b)r(ound)h(is)g Fn(w)r Fs(,)i(and)e(w)n(e)523 1511 y(pro)n(v)n(e)d (that)j(an)n(y)e(algorithm)g(that)h(do)r(es)f(not)h(unnecessarily)f (evict)h(pages)f(ac)n(hiev)n(es)f(that)523 1611 y(b)r(ound.)37 b(The)28 b(third)f(case)g(is)g(when)h Fn(w)d Fm(\024)e Fn(k)s Fs(;)k(w)n(e)g(presen)n(t)g(a)g(\()p Fn(k)21 b Fs(+)d(1\)-comp)r(etitiv)n(e)27 b(on-line)523 1710 y(algorithm,)g (reducing)f(the)i(existing)g(gap)e(to)i(1.)648 1810 y(The)33 b(case)f Fn(k)i Fs(=)e(1)g(mo)r(dels)h(the)g(sc)n(heduling)g(problem)f (in)h(whic)n(h)g(a)g(mac)n(hine)f(serv)n(es)523 1910 y Fn(w)k Fs(sequences)c(of)g(tasks,)h(where)g(the)g(cost)f(of)h(eac)n (h)f(task)g(is)h(insigni\014can)n(t)f(or)g(zero,)h(and)523 2009 y(the)28 b(cost)g(of)g(switc)n(hing)g(tasks)f(is)h(unitary)-7 b(.)38 b(This)28 b(is)g(an)f(extreme)h(situation)g(of)g(the)g(more)523 2109 y(general)22 b(case)g Fn(k)k(<)c(w)r Fs(.)37 b(W)-7 b(e)23 b(treat)g(that)g(extreme)g(situation)g(and)g(the)g(opp)r(osite)g (case,)g(that)523 2208 y(is,)28 b(the)g(case)e Fn(w)g Fm(\024)d Fn(k)s Fs(.)648 2308 y(Fiat)37 b(and)h(Karlin)f([7)o(])h(ha)n (v)n(e)f(considered)g(a)g(v)n(ersion)f(of)i(P)n(aging)e(in)i(whic)n(h)f (the)h(in-)523 2408 y(put)e(corresp)r(onds)d(to)i(a)f(m)n(ulti-p)r(oin) n(ter)h(w)n(alk)f(on)g(an)h Fp(ac)l(c)l(ess)i(gr)l(aph)f Fs([3].)59 b(Within)36 b(that)523 2507 y(framew)n(ork,)23 b(there)g(are)g(m)n(ultiple)h(threads)f(of)g(requests,)h(but)g(they)g (are)f(seen)g(as)g(a)g(unique)523 2607 y(sequence)e(corresp)r(onding)e (to)j(an)f(in)n(terlea)n(v)n(ed)e(execution)j(of)f(the)h(di\013eren)n (t)f(threads.)34 b(The)523 2707 y(w)n(a)n(y)28 b(in)h(whic)n(h)g(the)h (threads)e(are)g(in)n(terlea)n(v)n(ed)g(in)h([7])g(is)g(decided)g(in)h (an)f(earlier)e(stage)h(of)523 2806 y(the)36 b(pro)r(cess.)59 b(On)36 b(the)g(con)n(trary)-7 b(,)35 b(in)h(MTP)f(the)h(algorithms)e (are)h(free)g(to)g(decide)h(\(up)523 2906 y(to)29 b(a)g(certain)g (limit,)h(in)g(the)f(case)g(of)g(fairness)f(restrictions\))h(ho)n(w)f (to)h(do)g(that.)43 b(In)29 b(other)523 3005 y(w)n(ords,)d(the)h (algorithms)e(for)i(MTP)f(act)h(not)g(only)f(as)g(fast)h(memory)f (managers)f(but)i(also)523 3105 y(as)k(sc)n(hedulers,)g(while)h(in)g (the)f(cited)h(w)n(ork)e(the)i(sc)n(heduling)f(is)g(implicitly)h(supp)r (osed)f(to)523 3205 y(b)r(e)d(done)f(somewhere)g(else.)648 3304 y(Recen)n(tly)-7 b(,)37 b(Alb)r(orzi)e(et)h(al.)f([1)o(])h(ha)n(v) n(e)e(prop)r(osed)g(a)h(m)n(ulti-threaded)g(v)n(ersion)f(of)h(the)523 3404 y(1-serv)n(er)g(problem.)68 b(They)38 b(consider)f(a)h(metric)g (space)f(in)h(whic)n(h)g(a)g(serv)n(er)e(mo)n(v)n(es)g(at)523 3504 y(constan)n(t)e(sp)r(eed)i(to)f(satisfy)g(requests)f(generated)g (b)n(y)h(man)n(y)g(clien)n(ts;)k(eac)n(h)34 b(request)g(is)523 3603 y(satis\014ed)h(when)g(the)h(serv)n(er)d(arriv)n(es)g(to)i(the)h (lo)r(cation)e(of)h(the)h(request,)g(and)f(then)h(the)523 3703 y(corresp)r(onding)20 b(clien)n(t)i(presen)n(ts)e(a)i(new)g (request)f(in)h(another)e(place)i(of)f(the)h(metric)g(space.)523 3802 y(Although)33 b(the)g(1-serv)n(er)d(problem)j(is)f(a)h (generalization)d(of)j(P)n(aging)e(with)i Fn(k)i Fs(=)c(1,)j(only)523 3902 y(\014nite)39 b(input)h(sequences)e(are)f(considered)h(in)h([1)o (],)j(and)d(fairness)e(restrictions)h(are)f(not)523 4002 y(stated.)648 4101 y(The)22 b(remainder)g(of)g(this)h(pap)r(er)f(is)h (organized)d(as)i(follo)n(ws:)34 b(In)22 b(Section)h(2)f(w)n(e)g (formally)523 4201 y(presen)n(t)33 b(the)g(fair)g(v)n(ersion)f(of)h (MTP)-7 b(,)33 b(with)h(\014nite)g(and)f(in\014nite)h(input)g (sequences,)h(and)523 4301 y(detail)g(the)h(kno)n(wn)e(results)g(ab)r (out)h(it.)60 b(In)35 b(Section)g(3)g(w)n(e)f(treat)h(the)g(case)g Fn(k)j Fs(=)d(1)g(and)523 4400 y(ev)n(en)29 b Fn(w)r Fs(.)44 b(In)30 b(Section)g(4)f(w)n(e)g(complete)h(the)g(case)f Fn(k)g Fs(=)d(1)j(b)n(y)h(considering)e(an)i(o)r(dd)f Fn(w)r Fs(.)44 b(In)523 4500 y(Section)31 b(5)f(w)n(e)h(analyze)f(the)h (case)f Fn(w)h Fm(\024)d Fn(k)s Fs(.)47 b(W)-7 b(e)31 b(conclude)f(in)h(Section)g(6)g(b)n(y)f(presen)n(ting)523 4599 y(some)d(remarks.)p eop 24 3 bop 523 324 a Fs(A.)28 b(Strejilevic)n(h)g(de)f(Loma,)g Fp(F)-6 b(air)30 b(Multi-thr)l(e)l(ade)l(d)h(Paging)7 b Fs(,)29 b Fo(EJS)p Fs(,)f(1\(1\))f(21{36)f(\(1998\))10 b(24)523 614 y Fu(2)135 b(Preliminaries)523 813 y Fl(2.1)112 b(Description)36 b(of)i(the)f(Problem)523 966 y Fs(Imagine)18 b(that)i Fn(w)i Fs(indep)r(enden)n(t)d(pro)r(cesses)f(sim)n (ultaneously)g(presen)n(t)h(their)g(requiremen)n(ts)523 1066 y(of)26 b(pages)f(of)g(secondary)g(memory)g(that)h(m)n(ust)g(b)r (e)g(brough)n(t)f(in)n(to)h(fast)f(memory)-7 b(.)36 b(A)n(t)26 b(eac)n(h)523 1165 y(momen)n(t,)j(the)f(sc)n(heduler)g(and)g(fast)g (memory)g(manager)e(can)i(see)g(only)g(one)g(request)f(p)r(er)523 1265 y(pro)r(cess,)d(precisely)h(the)g(\014rst)g(unserv)n(ed)f(request) g(of)h(the)g(sequence)g(of)g(requests)f(that)h(the)523 1365 y(pro)r(cess)i(presen)n(ts.)37 b(Serving)27 b(the)h(curren)n(t)f (request)g(of)h(a)f(particular)g(pro)r(cess)g(allo)n(ws)f(the)523 1464 y(system)f(to)h(see)f(the)h(next)f(request)g(of)h(that)g(pro)r (cess.)35 b(The)25 b(system)h(m)n(ust)f(decide)h(at)f(eac)n(h)523 1564 y(step)36 b(whic)n(h)g(request)g(should)g(b)r(e)h(serv)n(ed,)g (apart)e(from)h(deciding)g(whic)n(h)g(page)f(of)h(fast)523 1663 y(memory)27 b(to)g(evict)h(to)f(mak)n(e)g(ro)r(om)g(for)g(the)h (incoming)f(page)g(if)h(that)g(is)f(the)h(case.)648 1763 y(MTP)37 b(allo)n(ws)f(the)i(mo)r(deling)f(of)g(the)h(ab)r(o)n(v)n(e)e (problem)h(as)g(follo)n(ws.)65 b(In)38 b(the)g(\014nite)523 1863 y(v)n(ersion,)20 b(called)g(Finite-MTP)f(\(FMTP\),)i(algorithms)d (are)h(faced)h(to)g(a)f(certain)h(n)n(um)n(b)r(er)f(of)523 1962 y(\014nite)j(sequences)e(of)h(requests)f(that)i(ha)n(v)n(e)e(to)h (b)r(e)g(serv)n(ed)f Fp(c)l(ompletely)p Fs(,)k(that)d(is,)i(algorithms) 523 2062 y(ha)n(v)n(e)38 b(to)g(arriv)n(e)f(to)i(the)h(end)f(of)f(eac)n (h)h(one)f(of)h(the)g(sequences.)70 b(FMTP)39 b(is)g(giv)n(en)f(b)n(y) 523 2162 y(the)c(univ)n(erse)f(or)h(set)g(of)g(pages)f Fn(U)42 b Fs(and)34 b(t)n(w)n(o)g(p)r(ositiv)n(e)f(in)n(tegers)g Fn(k)k Fs(and)d Fn(w)r Fs(,)i(the)f(size)e(of)523 2261 y(the)g(cac)n(he)f(and)g(the)h(n)n(um)n(b)r(er)f(of)h(sequences)f(resp) r(ectiv)n(ely)-7 b(.)50 b Fn(C)38 b Fs(=)31 b Fm(P)2746 2273 y Fk(k)2787 2261 y Fs(\()p Fn(U)9 b Fs(\))32 b(is)h(the)g(set)f (of)523 2361 y Fp(c)l(on\014gur)l(ations)p Fs(,)g(where)f Fm(P)1382 2373 y Fk(k)1423 2361 y Fs(\()p Fn(U)9 b Fs(\))31 b(is)h(the)f(p)r(o)n(w)n(er-set)f(of)h Fn(U)40 b Fs(restricted)31 b(to)g(subsets)g(of)h(size)523 2460 y Fn(k)s Fs(.)40 b Fn(\033)29 b Fm(2)c Fs(\()p Fn(U)886 2430 y Fj(\003)924 2460 y Fs(\))956 2430 y Fk(w)1039 2460 y Fs(is)j(the)h Fp(input)i(tuple)p Fs(,)e Fn(\033)f Fs(=)d Fn(\033)1923 2472 y Fi(1)1961 2460 y Fn(;)14 b(\033)2045 2472 y Fi(2)2082 2460 y Fn(;)g(:)g(:)g(:)g(\033)2277 2472 y Fk(w)2331 2460 y Fs(,)29 b(where)f(eac)n(h)g Fn(\033)2859 2472 y Fk(i)2916 2460 y Fs(is)h(a)f(sequence)523 2560 y(of)f(requests.)36 b(W)-7 b(e)27 b(can)g(view)g Fn(\033)k Fs(as)26 b(a)h(set)g(of)g (sequences)f(of)h(requests;)g(eac)n(h)f(request)h(is)g(an)523 2660 y(elemen)n(t)g(of)g(the)h(univ)n(erse)e Fn(U)9 b Fs(.)36 b(The)28 b(tuple)f(of)g(the)h Fn(j)5 b Fs(-th)27 b(requests)f(is)h(called)g(the)h Fn(j)5 b Fs(-th)27 b Fp(r)l(ow)523 2759 y Fs(of)h(requests.)648 2859 y(W)-7 b(e)32 b(can)f(imagine)g(that)h(w)n(e)f(ha)n(v)n(e)f(a)i(p)r(oin)n(ter) f(to)g(the)h(curren)n(t)f(p)r(osition)g(in)h(eac)n(h)f(se-)523 2959 y(quence)f Fn(\033)847 2971 y Fk(i)875 2959 y Fs(.)43 b(In)30 b(a)f(certain)g(con\014guration)g Fn(c)p Fs(,)h(the)g(system)g (can)f(adv)-5 b(ance)29 b(the)h(p)r(oin)n(ter)f(of)523 3058 y(some)i(sequence)h Fn(\033)1131 3070 y Fk(i)1191 3058 y Fs(suc)n(h)f(that)h Fn(u)1614 3070 y Fk(i)1642 3058 y Fs(,)h(the)f(curren)n(tly)f(p)r(oin)n(ted)h(page)f(of)h Fn(\033)2853 3070 y Fk(i)2881 3058 y Fs(,)h(is)f(presen)n(t)f(in)523 3158 y Fn(c)p Fs(.)61 b(Giv)n(en)35 b(an)g(input)i(tuple)f Fn(\033)j Fs(and)c(an)g(initial)h(con\014guration,)g(a)f Fp(sche)l(dule)h Fs(for)f Fn(\033)k Fs(is)d(a)523 3257 y(sequence)27 b(of)h(pairs)f Fn(<)d(i)1284 3269 y Fk(j)1318 3257 y Fn(;)14 b(c)1391 3269 y Fk(j)1450 3257 y Fn(>)p Fs(,)28 b(where)f(1)c Fm(\024)g Fn(i)1988 3269 y Fk(j)2047 3257 y Fm(\024)g Fn(w)r Fs(,)29 b(suc)n(h)f(that)g(the)g(curren)n(tly)f (p)r(oin)n(ted)523 3357 y(request)k(of)h Fn(\033)962 3369 y Fk(i)985 3377 y Fh(j)1052 3357 y Fs(ma)n(y)f(b)r(e)h(serv)n(ed)f (in)h(con\014guration)e Fn(c)2256 3369 y Fk(j)2291 3357 y Fs(.)49 b(The)32 b Fp(c)l(ost)f Fs(of)h(suc)n(h)f(sc)n(hedule)g(is) 523 3457 y(the)e(summation)f(o)n(v)n(er)f(the)i(sequence)f(of)g(the)h (Hamming)f(distance)g(b)r(et)n(w)n(een)h(successiv)n(e)523 3556 y(con\014gurations.)40 b(A)n(t)29 b(an)n(y)g(stage)f(of)h(a)g(sc)n (hedule,)g(an)n(y)g(sequence)f Fn(\033)2663 3568 y Fk(i)2721 3556 y Fs(whose)g(last)h(request)523 3656 y(has)e(not)h(b)r(een)g(serv) n(ed)e(is)i(called)f Fp(active)p Fs(.)648 3756 y(An)19 b(algorithm)e(for)h(FMTP)g(receiv)n(es)f(a)h(tuple)h(of)g(sequences)f Fn(\033)k Fs(as)17 b(input)j(and)e(pro)r(duces)523 3855 y(as)i(output)h(a)e(sc)n(hedule)h(for)g Fn(\033)s Fs(.)35 b(An)21 b(on-line)f(algorithm)f(m)n(ust)h(pro)r(duce)g(the)h(sc)n (hedule)f(with)523 3955 y(the)k(restriction)f(that)i(eac)n(h)e (con\014guration)f(m)n(ust)i(b)r(e)g(determined)h(only)e(as)g(a)h (function)g(of)523 4054 y(the)19 b(curren)n(t)f(tuple)h(of)f(requests)g (and)h(all)f(the)h(requests)f(already)f(serv)n(ed)g(b)n(y)h(the)h (algorithm.)523 4154 y(On)25 b(the)h(con)n(trary)-7 b(,)24 b(an)i(o\013-line)f(algorithm)g(can)g(decide)g(based)h(on)f(the)h(en)n (tire)f(input.)37 b(An)523 4254 y(algorithm)32 b(for)h(FMTP)g(is)h Fn(c)p Fs(-comp)r(etitiv)n(e)f(if)g(and)h(only)f(if)h(there)f(exists)g (a)g(constan)n(t)f Fn(D)523 4353 y Fs(suc)n(h)22 b(that)h(for)f(an)n(y) g(input)i(tuple)f Fn(\033)s Fs(,)h(w)n(e)e(ha)n(v)n(e)g Fn(C)2038 4365 y Fk(A)2092 4353 y Fs(\()p Fn(\033)s Fs(\))i Fm(\024)f Fn(c)9 b Fm(\001)g Fn(C)2454 4365 y Fk(O)r(P)g(T)2609 4353 y Fs(\()p Fn(\033)s Fs(\))g(+)g Fn(D)r Fs(,)24 b(where)e Fn(C)3218 4365 y Fk(A)3272 4353 y Fs(\()p Fn(\033)s Fs(\))523 4453 y(is)30 b(the)g(cost)f(incurred)g(b)n(y)h(the)g(algorithm,)f(and)h Fn(C)2147 4465 y Fk(O)r(P)9 b(T)2303 4453 y Fs(\()p Fn(\033)s Fs(\))31 b(is)f(the)g(cost)f(incurred)g(b)n(y)h(an)523 4553 y(optimal)d(o\013-line)h(algorithm.)648 4652 y(The)20 b(de\014nition)h(of)f(FMTP)g(is)h(mo)r(di\014ed)f(to)h(get)f(the)h (in\014nite)g(v)n(ersion)e(of)h(the)h(problem,)523 4752 y(In\014nite-MTP)30 b(\(IMTP\).)g(In)g(IMTP)g(the)g(sequences)f(of)h (requests)f(are)g(in\014nite,)i(that)f(is,)523 4851 y(the)24 b(input)h(to)f(an)f(algorithm)g(is)g Fn(\033)k Fm(2)c Fs(\()p Fn(U)1793 4821 y Fk(!)1841 4851 y Fs(\))1873 4821 y Fk(w)1951 4851 y Fs(instead)h(of)g Fn(\033)i Fm(2)e Fs(\()p Fn(U)2575 4821 y Fj(\003)2613 4851 y Fs(\))2645 4821 y Fk(w)2699 4851 y Fs(,)h(where)e(\006)3043 4821 y Fk(!)3115 4851 y Fs(denotes)p eop 25 4 bop 523 324 a Fs(A.)28 b(Strejilevic)n(h)g(de)f(Loma,)g Fp(F)-6 b(air)30 b(Multi-thr)l(e)l(ade)l(d)h(Paging)7 b Fs(,)29 b Fo(EJS)p Fs(,)f(1\(1\))f(21{36)f(\(1998\))10 b(25)523 614 y(the)22 b(set)f(of)h(in\014nite)g(w)n(ords)e(o)n(v)n(er)f (an)i(alphab)r(et)h(\006.)35 b(In)21 b(this)h(case,)g(although)e(the)i (sequences)523 714 y(are)33 b(in\014nite,)k(the)e(system)f(is)g(observ) n(ed)f(after)h(a)g(\014nite)h(n)n(um)n(b)r(er)f Fn(`)g Fs(of)g(steps,)i(when)f(w)n(e)523 814 y(compare)21 b(the)i(cost)e (incurred)h(b)n(y)g(the)h(distinct)f(algorithms)f(with)i(the)g(cost)e (of)i(an)f(optimal)523 913 y(o\013-line)k(algorithm)f(that)i(adv)-5 b(ances)25 b(at)i(least)f(the)g(same)g(n)n(um)n(b)r(er)g(of)g(steps.)37 b(Notice)26 b(that)523 1013 y(the)i(v)-5 b(alue)27 b(of)h Fn(`)f Fs(is)h(not)f(kno)n(wn)g(b)n(y)h(on-line)f(algorithms.)648 1112 y(In)34 b(a)h(m)n(ulti-threaded)f(en)n(vironmen)n(t)f(it)i(is)g (desirable)f(to)g(include)h(fairness)f(restric-)523 1212 y(tions.)64 b(In)37 b(MTP)f(these)h(restrictions)e(are)h(mo)r(deled)g (b)n(y)h(considering,)g(as)f(part)g(of)h(the)523 1312 y(input)26 b(of)f(the)g(problem,)g(an)f(in)n(teger)g Fn(t)h Fs(suc)n(h)g(that)g(fair)f(algorithms)g(are)g(restricted)g(to)h (act)523 1411 y(as)31 b(follo)n(ws:)43 b(from)32 b(the)f(momen)n(t)h (an)n(y)f(request)f(is)i(seen)f(till)h(the)g(momen)n(t)f(that)h (request)523 1511 y(is)26 b(serv)n(ed,)g(at)g(most)g Fn(t)h Fs(other)f(requests)f(can)i(b)r(e)f(satis\014ed.)36 b(Consequen)n(tly)-7 b(,)26 b(the)h(notion)f(of)523 1611 y Fn(t)p Fp(-fair)k Fs(sc)n(hedule)f(is)g(de\014ned.)42 b(This)29 b(allo)n(ws)f(the)h(de\014nition)g(of)h(the)f(F)-7 b(air-MTP)28 b(problem,)523 1710 y(the)38 b(fair)f(v)n(ersion)f(of)h (MTP.)66 b(An)38 b(algorithm)e(for)h(F)-7 b(air-MTP)36 b(m)n(ust)h(pro)r(duce)g(a)g Fn(t)p Fs(-fair)523 1810 y(sc)n(hedule)e(for)g(the)g(input)h(tuple)g(of)f(sequences.)59 b(Again)35 b(there)g(are)f(\014nite)i(and)f(in\014nite)523 1910 y(v)n(ersions)26 b(of)h(the)h(problem,)g(namely)f(F)-7 b(air-FMTP)26 b(and)i(F)-7 b(air-IMTP.)523 2142 y Fl(2.2)112 b(Previous)37 b(Results)523 2295 y Fs(In)24 b([6])f(it)h(w)n(as)f(pro)n (v)n(ed)f(that)i(there)g(is)f(no)h(comp)r(etitiv)n(e)g(on-line)f (algorithm)g(for)g(F)-7 b(air-MTP)523 2395 y(with)33 b Fn(t)d Fm(\025)h Fn(w)i Fm(\025)e Fs(2.)50 b(This)32 b(means)g(that)g(comp)r(etitiv)n(e)h(on-line)e(algorithms)g(can)h (exist)g(in)523 2494 y(only)22 b(t)n(w)n(o)g(cases)g(of)h(F)-7 b(air-MTP:)21 b Fn(w)26 b Fs(=)c(1)h(and)f Fn(t)h Fs(=)g Fn(w)11 b Fm(\000)e Fs(1.)34 b(In)23 b(the)g(case)f(of)h(\014nite)g (sequences)523 2594 y(of)g(requests)f(\(that)i(is,)f(F)-7 b(air-FMTP\))23 b(there)f(is)h(no)g(comp)r(etitiv)n(e)g(on-line)f (algorithm)g(when)523 2694 y Fn(w)k Fm(\025)c Fs(3,)k(ev)n(en)f(with)h Fn(t)d Fs(=)f Fn(w)17 b Fm(\000)d Fs(1.)35 b(This)26 b(is)f(b)r(ecause)g(on-line)g(algorithms)f(can)h(b)r(e)h(forced)f(to) 523 2793 y(serv)n(e)h(a)h(\014rst)h(sequence)f(of)g(length)h(1;)f(in)h (practice)f(this)h(is)f(equiv)-5 b(alen)n(t)28 b(to)f(ha)n(v)n(e)g Fn(t)c Fs(=)f Fn(w)r Fs(.)648 2893 y(Among)34 b(the)h(cases)f(where)h (on-line)f(comp)r(etitiv)n(eness)g(is)h(p)r(ossible,)i(w)n(e)d(can)h (ignore)523 2993 y(the)e(situation)f(in)h(whic)n(h)f Fn(w)i Fs(=)d(1:)47 b(with)33 b Fn(w)h Fs(=)c(1)i(fairness)g (restrictions)f(ha)n(v)n(e)h(no)g(sense,)523 3092 y(and)j(w)n(e)f(are)g (faced)h(to)f(regular)f(P)n(aging.)57 b(On)34 b(the)h(other)g(hand,)h (the)f(case)f Fn(t)h Fs(=)g Fn(w)26 b Fm(\000)d Fs(1)523 3192 y(requires)j(further)h(analysis.)36 b(In)27 b(this)h(situation)f (the)h(algorithms)e(\(on-line)h(or)g(not\))g(m)n(ust)523 3291 y(apply)38 b(round-robin,)h(i.)f(e.,)j(serv)n(e)36 b(one)i(request)f(of)h(eac)n(h)f(sequence)h(in)g(a)g(\014xed)g(order) 523 3391 y(whic)n(h)g(is)f(rep)r(eated)h(o)n(v)n(er)e(and)h(o)n(v)n(er) f(again.)66 b(This)38 b(particular)e(case)h(of)h(F)-7 b(air-MTP)36 b(is)523 3491 y(closely)27 b(related)g(to)g(normal)g(P)n (aging,)e(since)j(after)f(an)h(algorithm)e(has)h(c)n(hosen)g(the)h (order)523 3590 y(in)h(whic)n(h)f(to)g(serv)n(e)f(the)i(requests,)e(w)n (e)h(can)g(think)h(that)g(there)f(is)g(only)g(one)g(sequence)g(to)523 3690 y(b)r(e)33 b(serv)n(ed,)f(as)f(it)i(is)f(the)g(case)g(in)g(normal) f(P)n(aging.)49 b(Nev)n(ertheless,)32 b(the)h(t)n(w)n(o)e(problems)523 3790 y(are)c(di\013eren)n(t,)g(as)g(w)n(e)h(can)f(see:)648 3956 y Fm(\017)41 b Fs(In)33 b(F)-7 b(air-MTP)33 b(w)n(e)g(can)g(sa)n (y)f(that)i(an)n(y)f(algorithm)f(has)i(serv)n(ed)e(the)i(same)f(set)g (of)731 4055 y(requests)28 b(only)h(after)g(eac)n(h)g Fn(w)j Fs(new)d(requests)g(\(after)g(eac)n(h)g(ro)n(w)f(of)h (requests\),)g(not)731 4155 y(at)e(ev)n(ery)f(step)i(as)f(in)h(normal)e (P)n(aging.)648 4321 y Fm(\017)41 b Fs(The)24 b(algorithms)f(\(of)i(an) n(y)f(t)n(yp)r(e\))h(can)f(c)n(ho)r(ose)f(b)r(et)n(w)n(een)i Fn(w)r Fs(!)g(distinct)h(orders)c(of)j(the)731 4421 y(sequences.)51 b(A)33 b(priori)f(this)h(is)g(an)f(adv)-5 b(an)n(tage)31 b(for)h(o\013-line)h(algorithms,)g(b)r(ecause)731 4520 y(they)39 b(can)g(decide)g(with)g(information)g(on)f(the)i(whole)f (input)g(tuple,)k(while)c(an)n(y)731 4620 y(c)n(hoice)23 b(made)h(b)n(y)g(an)g(on-line)g(algorithm)f(can)h(b)r(e)g(fo)r(oled)g (if)h(the)g(\014rst)f(t)n(w)n(o)f(requests)731 4719 y(of)i(all)g(the)g (sequences)g(are)f(to)h(the)h(same)f(page.)35 b(In)25 b(other)g(w)n(ords,)g(from)g(a)f(comp)r(et-)731 4819 y(itiv)n(e)k(analysis)f(p)r(oin)n(t)h(of)g(view,)h(o\013-line)f (algorithms)f(can)g(really)h(decide)g(in)g(whic)n(h)p eop 26 5 bop 523 324 a Fs(A.)28 b(Strejilevic)n(h)g(de)f(Loma,)g Fp(F)-6 b(air)30 b(Multi-thr)l(e)l(ade)l(d)h(Paging)7 b Fs(,)29 b Fo(EJS)p Fs(,)f(1\(1\))f(21{36)f(\(1998\))10 b(26)731 614 y(order)31 b(to)i(serv)n(e)e(the)i(sequences,)h(while)f (the)g(c)n(hoice)f(of)h(an)f(on-line)h(algorithm)e(is)731 714 y(an)c(illusion.)648 880 y Fm(\017)41 b Fs(The)25 b(on-line)g(algorithms)g(can)g(see)g(the)h(follo)n(wing)f Fn(w)j Fs(requests)d(to)g(serv)n(e,)g(not)h(only)731 980 y(one)i(of)h(them.)41 b(More)28 b(precisely)-7 b(,)29 b(on-line)f(algorithms)g(can)g(mak)n(e)g(use)h(of)g(a)g(lo)r(ok)-5 b(a-)731 1079 y(head)27 b(of)g(size)g Fn(w)r Fs(.)37 b(This)27 b(is)g(not)h(a)e(clear)h(adv)-5 b(an)n(tage)25 b(for)i(on-line)g(algorithms,)f(since)731 1179 y(this)g(kind)g(of)g(lo) r(ok)-5 b(ahead)25 b(can)h(b)r(e)h(easily)e(neutralized)h(b)n(y)g (replacing)f(eac)n(h)g(request)731 1279 y(with)j Fn(w)i Fs(requests)d(to)g(the)h(same)f(page.)648 1445 y(A)c(lo)n(w)n(er)e(b)r (ound)j(of)e Fn(k)k Fs(for)d(the)g(comp)r(etitiv)n(eness)g(of)f(an)n(y) h(on-line)f(algorithm)g(for)g(F)-7 b(air-)523 1544 y(MTP)24 b(can)f(b)r(e)i(obtained)e(b)n(y)h(considering)f(equal)g(sequences,)h (eac)n(h)f(one)h(lik)n(e)f(the)i(nemesis)523 1644 y(sequence)i(used)h (in)g(the)g(pro)r(of)f(of)g(the)h(lo)n(w)n(er)e(b)r(ound)i(for)f (normal)g(P)n(aging.)648 1743 y(An)37 b(on-line)g(algorithm)g(for)f(F) -7 b(air-MTP)37 b(called)g(Round-Robin{Flush-When-F)-7 b(ull)523 1843 y(\(RRFWF\))37 b(w)n(as)d(presen)n(ted)g(in)h([6].)59 b(The)36 b(algorithm)d(is)i(based)g(on)g(Flush-When-F)-7 b(ull)523 1943 y(\(FWF\),)35 b(a)e(v)n(ery)f(w)n(ell)h(kno)n(wn)g Fn(k)s Fs(-comp)r(etitiv)n(e)g(on-line)g(algorithm)f(for)h(P)n(aging)e ([8],)k(al-)523 2042 y(though)j(an)n(y)g(deterministic)g(marking)f (algorithm)g(for)h(P)n(aging)f(can)h(b)r(e)g(used)h(instead)523 2142 y(\(for)25 b(instance,)h(LR)n(U\).)g(FWF)g(main)n(tains)f(a)g(set) g(of)h(mark)n(ed)e(pages.)35 b(Initially)26 b(no)f(page)f(is)523 2242 y(mark)n(ed.)48 b(On)31 b(eac)n(h)g(request,)h(an)f(unmark)n(ed)f (page)h(is)h(evicted)f(to)h(mak)n(e)e(ro)r(om)h(for)g(the)523 2341 y(requested)i(page)g(if)h(necessary;)h(in)f(an)n(y)f(case)g(the)h (requested)f(page)g(is)h(mark)n(ed.)54 b(FWF)523 2441 y(w)n(orks)29 b(in)j Fp(phases)p Fs(,)h(the)f(\014rst)e(phase)h (starting)f(with)i(the)f(\014rst)g(request)f(of)h(the)h(sequence)523 2540 y(and)22 b(eac)n(h)f(new)h(phase)g(starting)f(with)i(the)f (request)g(that)g(w)n(ould)g(ha)n(v)n(e)f(caused)g(more)g(than)523 2640 y Fn(k)36 b Fs(pages)31 b(to)i(b)r(e)g(mark)n(ed)e(\(when)i(the)g (marks)e(are)h(deleted\).)53 b(It)33 b(is)f(easy)g(to)g(v)n(erify)g (that)523 2740 y(FWF)23 b(nev)n(er)f(faults)h(t)n(wice)f(on)g(the)h (same)f(page)g(during)g(an)n(y)g(giv)n(en)g(phase,)h(whic)n(h)f (implies)523 2839 y(that)27 b(its)h(cost)e(is)h(at)g(most)g Fn(k)j Fs(p)r(er)d(phase;)f(b)r(esides,)h(if)h(w)n(e)f(consider)f(all)g (the)i(requests)e(of)h(a)523 2939 y(phase)g(plus)h(the)g(\014rst)f (request)g(of)g(the)h(follo)n(wing)f(phase,)g Fn(k)21 b Fs(+)d(1)27 b(distinct)h(pages)e(app)r(ear.)648 3039 y(Algorithm)41 b(RRFWF)h(for)f(F)-7 b(air-MTP)40 b(is)h(describ)r(ed)g (in)h(Fig.)13 b(1.)78 b(The)42 b(algorithm)523 3138 y(w)n(orks)23 b(in)i(\\sup)r(er-phases";)e(eac)n(h)h(sup)r(er-phase)f(consists)h(of)g (applying)g(a)g(phase)g(of)h(FWF)523 3238 y(to)32 b(the)h(sequence)g (formed)f(b)n(y)g(taking)g(in)h(turn)g(one)f(request)g(of)g(eac)n(h)g (activ)n(e)g(sequence)523 3337 y Fn(\033)570 3349 y Fi(1)608 3337 y Fn(;)14 b(\033)692 3349 y Fi(2)729 3337 y Fn(;)g(:)g(:)g(:)g (\033)924 3349 y Fk(w)978 3337 y Fs(,)33 b(and)f(then)h(serving)e(the)h (next)h(request)e(and)h(all)g(the)g(other)g(p)r(ending)g(re-)523 3437 y(quests)d(in)g(the)g(same)g(ro)n(w;)f(these)h(additional)g (requests)f(are)g(serv)n(ed)g(b)n(y)g(RRFWF)i(in)g(an)523 3537 y(arbitrary)20 b(deterministic)i(w)n(a)n(y)-7 b(.)34 b(Clearly)21 b(RRFWF)i(is)f(fair)g(for)f(an)n(y)h(legal)f(v)-5 b(alue)22 b(of)g Fn(t)p Fs(.)35 b(It)22 b(is)523 3636 y(not)g(di\016cult)i(to)e(sho)n(w)f(that)i(it)g(is)f(\()p Fn(k)11 b Fs(+)d Fn(w)r Fs(\)-comp)r(etitiv)n(e)23 b(for)f(F)-7 b(air-IMTP)21 b(with)i Fn(t)g Fs(=)f Fn(w)10 b Fm(\000)e Fs(1.)523 3736 y(Algorithm)27 b(RRFWF)h(is)e(\()p Fn(k)21 b Fs(+)16 b Fn(w)r Fs(\)-comp)r(etitiv)n(e)28 b(also)e(for)g(F)-7 b(air-FMTP)26 b(with)i Fn(t)23 b Fs(=)f Fn(w)e Fm(\000)d Fs(1,)523 3836 y(but)28 b(of)g(course)e(when)i Fn(w)e Fm(\024)c Fs(2)28 b(only)-7 b(.)523 4110 y Fu(3)135 b(The)44 b(Case)i Fg(k)37 b Ff(=)c(1)45 b Fu(and)f(Ev)l(en)i Fg(w)523 4292 y Fs(In)23 b(this)g(section)g(w)n(e)f(will)h(analyze)f(the)h(case) f(of)h(F)-7 b(air-MTP)22 b(in)h(whic)n(h)g(the)g(cac)n(he)f(can)g(hold) 523 4392 y(only)32 b(one)h(page)e(and)i(the)g(n)n(um)n(b)r(er)f(of)h (sequences)f(is)g(ev)n(en.)52 b(W)-7 b(e)33 b(will)g(consider)f (in\014nite)523 4491 y(and)f(\014nite)g(input)h(sequences,)f(and)g(w)n (e)f(will)i(restrict)e(our)g(atten)n(tion)h(to)g(the)g(situations)523 4591 y(where)f(on-line)g(comp)r(etitiv)n(eness)g(is)g(p)r(ossible.)44 b(As)31 b(it)g(is)f(usually)g(done)g(in)g(comp)r(etitiv)n(e)523 4691 y(analysis,)i(w)n(e)g(will)h(compare)e(on-line)h(strategies)f (against)h(an)g Fp(adversary)i Fs(that)f(c)n(ho)r(oses)523 4790 y(the)28 b(input)g(and)g(serv)n(es)e(it)i(optimally)-7 b(.)p eop 27 6 bop 523 324 a Fs(A.)28 b(Strejilevic)n(h)g(de)f(Loma,)g Fp(F)-6 b(air)30 b(Multi-thr)l(e)l(ade)l(d)h(Paging)7 b Fs(,)29 b Fo(EJS)p Fs(,)f(1\(1\))f(21{36)f(\(1998\))10 b(27)523 684 y Fe(While)42 b(there)f(is)i(at)g(least)e(one)h(request)f (to)i(be)g(served)e(do)785 784 y(\045)i(a)g(new)f(super-phase)d(starts) 785 883 y(Apply)i(a)i(phase)f(of)h(FWF)f(to)h(the)f(sequence)e Fn(\033)2447 853 y Fj(\003)2529 883 y Fe(formed)i(by)g(taking)785 983 y(in)g(turn)g(one)h(request)d(of)j(each)f(active)f(sequence)f Fn(\033)2749 995 y Fi(1)2787 983 y Fn(;)14 b(\033)2871 995 y Fi(2)2909 983 y Fn(;)g(:)g(:)g(:)f(\033)3103 995 y Fk(w)785 1083 y Fe(Serve)41 b(the)h(next)g(request)f(of)i Fn(\033)1968 1052 y Fj(\003)2050 1083 y Fe(\(no)f(matter)f(how\))785 1182 y(Serve)g(all)h(the)h(pending)d(requests)h(of)h Fn(\033)2316 1152 y Fj(\003)2399 1182 y Fe(in)g(the)h(same)f(row)785 1282 y(of)g(the)h(last)f(served)f(request)f(\(no)j(matter)e(how\))523 1381 y(end)h(While.)1004 1647 y Fs(Figure)27 b(1:)36 b(Algorithm)28 b(Round-Robin{Flush-When-F)-7 b(ull)523 1894 y Fl(3.1)112 b(In\014nite)37 b(Sequences)523 2047 y Fs(Till)31 b(no)n(w)g(the)g(kno)n(wn)f(lo)n(w)n(er)g(b)r(ound)h(for)f (the)i(comp)r(etitiv)n(eness)e(of)h(on-line)g(algorithms)523 2147 y(for)f(F)-7 b(air-IMTP)30 b(with)h Fn(t)e Fs(=)f Fn(w)23 b Fm(\000)d Fs(1)31 b(w)n(as)f Fn(k)s Fs(;)i(this)f(b)r(ound)h (b)r(ecomes)e(trivial)g(when)h Fn(k)h Fs(=)c(1.)523 2247 y(W)-7 b(e)25 b(will)f(no)n(w)g(pro)n(v)n(e)e(a)i(higher)g(lo)n(w)n(er) e(b)r(ound)j(for)f(an)g(ev)n(en)f(n)n(um)n(b)r(er)h(of)h(sequences,)f (using)523 2346 y(that)k(the)g(adv)n(ersary)d(can)i(c)n(ho)r(ose)f(an)i (appropriate)d(order)i(for)g(the)h(threads.)523 2506 y Fd(Theorem)i(3.1.1)40 b Fp(No)c(on-line)g(algorithm)h(for)f(F)-6 b(air-IMTP)37 b(with)f Fn(t)d Fs(=)g Fn(w)26 b Fm(\000)c Fs(1)p Fp(,)37 b Fn(k)f Fs(=)d(1)523 2606 y Fp(and)h(even)f Fn(w)r Fp(,)i(is)e Fn(c)p Fp(-c)l(omp)l(etitive)h(if)g Fn(c)29 b(<)g(w)24 b Fs(+)c(1)p Fp(,)34 b(even)f(if)h(we)g(r)l(estrict) e(the)i(se)l(quenc)l(es)e(of)523 2706 y(r)l(e)l(quests)d(to)h(b)l(e)f (forme)l(d)i(by)f(at)g(most)g Fs(2)f Fp(distinct)h(p)l(ages.)523 2866 y Fd(Pro)s(of)66 b Fs(Let)25 b(A)g(b)r(e)h(an)n(y)e(on-line)g (algorithm)f(and)i(AD)n(V)h(an)e(o\013-line)h(adv)n(ersary)-7 b(.)33 b(W)-7 b(e)25 b(will)523 2965 y(sho)n(w)e(a)g(set)g(of)h (sequences)e Fn(\033)1425 2977 y Fi(1)1463 2965 y Fn(;)14 b(\033)1547 2977 y Fi(2)1585 2965 y Fn(;)g(:)g(:)g(:)f(\033)1779 2977 y Fk(w)1857 2965 y Fs(for)23 b(whic)n(h)g(A)h(cannot)f(b)r(eha)n (v)n(e)g(b)r(etter)g(than)h(the)523 3065 y(prop)r(osed)j(b)r(ound.)648 3164 y(Let)h Fn(U)34 b Fs(=)25 b Fm(f)p Fn(a)1064 3176 y Fi(1)1100 3164 y Fn(;)14 b(a)1181 3176 y Fi(2)1218 3164 y Fm(g)28 b Fs(b)r(e)i(a)e(set)h(of)f(2)h(distinct)g(pages,)f (where)g Fn(a)2607 3176 y Fi(1)2673 3164 y Fs(is)g(a)h(page)f(not)g(in) h(A's)523 3264 y(cac)n(he)i(at)h(the)h(b)r(eginning.)50 b(W)-7 b(e)32 b(will)g(describ)r(e)g(the)g(input)h(tuple)g(b)n(y)f(ro)n (ws)e(of)i(requests.)523 3364 y(The)23 b(\014rst)f(ro)n(w)g(is)g (formed)g(b)n(y)h(page)f Fn(a)1706 3376 y Fi(1)1765 3364 y Fs(for)h(the)g(o)r(dd)f(sequences)g Fn(\033)2603 3376 y Fi(1)2641 3364 y Fn(;)14 b(\033)2725 3376 y Fi(3)2763 3364 y Fn(;)g(:)g(:)g(:)f(\033)2957 3376 y Fk(w)r Fj(\000)p Fi(1)3096 3364 y Fs(,)24 b(and)f(b)n(y)523 3463 y(page)h Fn(a)758 3475 y Fi(2)819 3463 y Fs(for)g(the)h(ev)n(en)f(sequences)f Fn(\033)1689 3475 y Fi(2)1727 3463 y Fn(;)14 b(\033)1811 3475 y Fi(4)1849 3463 y Fn(;)g(:)g(:)g(:)f(\033)2043 3475 y Fk(w)2097 3463 y Fs(.)36 b(In)25 b(the)g(second)e(ro)n(w,)h(all) g(the)h(requests)523 3563 y(are)d(to)g(page)g Fn(a)986 3575 y Fi(1)1023 3563 y Fs(.)36 b(Eac)n(h)21 b(new)i(pair)f(of)h(ro)n (ws)e(is)i(lik)n(e)f(the)h(previous)f(one,)h(but)g(with)h(pages)d Fn(a)3350 3575 y Fi(1)523 3663 y Fs(and)h Fn(a)723 3675 y Fi(2)782 3663 y Fs(in)n(terc)n(hanged)e(\(see)h(Fig.)14 b(2\).)35 b(Let)22 b Fn(`)g Fs(=)h(2)p Fn(w)r(n)f Fs(b)r(e)g(the)g (total)g(n)n(um)n(b)r(er)f(of)h(requests)f(to)523 3762 y(b)r(e)e(serv)n(ed,)h(where)e Fn(n)h Fs(is)f(an)n(y)g(p)r(ositiv)n(e)h (in)n(teger.)33 b(Without)19 b(loss)f(of)h(generalit)n(y)e(assume)h (that)523 3862 y(A)29 b(serv)n(es)d(one)i(request)g(of)g(eac)n(h)f (sequence)h(in)g(the)h(order)e Fn(\033)2431 3874 y Fi(1)2468 3862 y Fn(;)14 b(\033)2552 3874 y Fi(2)2590 3862 y Fn(;)g(:)g(:)g(:)g (\033)2785 3874 y Fk(w)2867 3862 y Fs(\(otherwise,)28 b(w)n(e)523 3961 y(add)d(t)n(w)n(o)g(initial)g(ro)n(ws)f(with)i (requests)e(only)h(to)g(page)g Fn(a)2285 3973 y Fi(2)2322 3961 y Fs(,)h(and)f(rearrange)d(the)k(sequences)523 4061 y(if)h(necessary\).)35 b(Since)27 b Fn(k)f Fs(=)c(1,)27 b(only)f(one)g(page)g(can)g(b)r(e)h(held)f(in)h(fast)g(memory)e(at)i(a) f(time,)523 4161 y(and)i(therefore)e(A)i(necessarily)e(faults)i(on)g (eac)n(h)f(request)g(of)g(the)h(o)r(dd)g(ro)n(ws)e(and)i(on)f(eac)n(h) 523 4260 y(\014rst)g(request)g(of)h(the)g(ev)n(en)f(ones;)g(th)n(us,)h (its)f(total)h(cost)f(is)g Fn(C)2451 4272 y Fk(A)2529 4260 y Fm(\025)c Fs(\()p Fn(w)e Fs(+)d(1\))p Fn(n)p Fs(.)648 4360 y(The)26 b(adv)n(ersary)d(can)j(use)g(an)n(y)f(order)g(in)i(whic)n (h)f(the)g(ev)n(en)g(sequences)f(app)r(ear)h(b)r(efore)523 4460 y(the)39 b(o)r(dd)h(ones,)h(e.)e(g.,)i Fn(\033)1350 4472 y Fi(2)1388 4460 y Fn(;)14 b(\033)1472 4472 y Fi(4)1510 4460 y Fn(;)g(:)g(:)g(:)f(\033)1704 4472 y Fk(w)1759 4460 y Fn(;)h(\033)1843 4472 y Fi(1)1880 4460 y Fn(;)g(\033)1964 4472 y Fi(3)2002 4460 y Fn(;)g(:)g(:)g(:)f(\033)2196 4472 y Fk(w)r Fj(\000)p Fi(1)2335 4460 y Fs(.)72 b(In)39 b(this)g(w)n(a)n(y)f(it)h(groups)f(the)523 4559 y(rep)r(eated)29 b(requests,)f(and)h(faults)g(only)g(once)g(ev)n(ery)e(t)n(w)n(o)i(ro)n (ws.)39 b(Then)30 b(the)f(total)g(cost)f(of)523 4659 y(the)g(adv)n(ersary)d(is)i Fn(C)1185 4671 y Fk(AD)r(V)1372 4659 y Fm(\024)c Fn(n)p Fs(,)28 b(and)f(w)n(e)g(ha)n(v)n(e)g(for)g(the) h(comp)r(etitiv)n(e)f(ratio)1484 4806 y Fn(C)1543 4818 y Fk(A)p 1429 4843 223 4 v 1429 4919 a Fn(C)1488 4931 y Fk(AD)r(V)1685 4862 y Fm(\025)1782 4806 y Fs(\()p Fn(w)22 b Fs(+)c(1\))p Fn(n)p 1782 4843 320 4 v 1917 4919 a(n)2135 4862 y Fs(=)k Fn(w)f Fs(+)d(1)41 b Fn(:)p eop 28 7 bop 523 324 a Fs(A.)28 b(Strejilevic)n(h)g(de)f(Loma,)g Fp(F)-6 b(air)30 b(Multi-thr)l(e)l(ade)l(d)h(Paging)7 b Fs(,)29 b Fo(EJS)p Fs(,)f(1\(1\))f(21{36)f(\(1998\))10 b(28)1349 692 y Fn(\033)1396 704 y Fi(1)1556 692 y Fm(\001)k(\001)g (\001)88 b Fn(\033)1788 704 y Fk(odd)1983 692 y Fn(\033)2030 704 y Fk(ev)r(en)2257 692 y Fm(\001)14 b(\001)g(\001)115 b Fn(\033)2516 704 y Fk(w)p 1309 792 165 4 v 1307 892 4 100 v 1351 862 a Fn(a)1395 874 y Fi(1)p 1472 892 V 1307 991 V 1351 961 a Fn(a)1395 973 y Fi(1)p 1472 991 V 1307 1091 V 1351 1061 a Fn(a)1395 1073 y Fi(2)p 1472 1091 V 1307 1191 V 1351 1161 a Fn(a)1395 1173 y Fi(2)p 1472 1191 V 1307 1290 V 1351 1260 a Fn(a)1395 1272 y Fi(1)p 1472 1290 V 1307 1390 V 1351 1360 a Fn(a)1395 1372 y Fi(1)p 1472 1390 V 1307 1545 4 155 v 1380 1448 a Fs(.)1380 1482 y(.)1380 1515 y(.)p 1472 1545 V 1309 1548 165 4 v 1736 792 V 1734 892 4 100 v 1778 862 a Fn(a)1822 874 y Fi(1)p 1899 892 V 1734 991 V 1778 961 a Fn(a)1822 973 y Fi(1)p 1899 991 V 1734 1091 V 1778 1061 a Fn(a)1822 1073 y Fi(2)p 1899 1091 V 1734 1191 V 1778 1161 a Fn(a)1822 1173 y Fi(2)p 1899 1191 V 1734 1290 V 1778 1260 a Fn(a)1822 1272 y Fi(1)p 1899 1290 V 1734 1390 V 1778 1360 a Fn(a)1822 1372 y Fi(1)p 1899 1390 V 1734 1545 4 155 v 1807 1448 a Fs(.)1807 1482 y(.)1807 1515 y(.)p 1899 1545 V 1736 1548 165 4 v 1997 792 V 1995 892 4 100 v 2038 862 a Fn(a)2082 874 y Fi(2)p 2159 892 V 1995 991 V 2038 961 a Fn(a)2082 973 y Fi(1)p 2159 991 V 1995 1091 V 2038 1061 a Fn(a)2082 1073 y Fi(1)p 2159 1091 V 1995 1191 V 2038 1161 a Fn(a)2082 1173 y Fi(2)p 2159 1191 V 1995 1290 V 2038 1260 a Fn(a)2082 1272 y Fi(2)p 2159 1290 V 1995 1390 V 2038 1360 a Fn(a)2082 1372 y Fi(1)p 2159 1390 V 1995 1545 4 155 v 2067 1448 a Fs(.)2067 1482 y(.)2067 1515 y(.)p 2159 1545 V 1997 1548 165 4 v 2437 792 V 2435 892 4 100 v 2479 862 a Fn(a)2523 874 y Fi(2)p 2600 892 V 2435 991 V 2479 961 a Fn(a)2523 973 y Fi(1)p 2600 991 V 2435 1091 V 2479 1061 a Fn(a)2523 1073 y Fi(1)p 2600 1091 V 2435 1191 V 2479 1161 a Fn(a)2523 1173 y Fi(2)p 2600 1191 V 2435 1290 V 2479 1260 a Fn(a)2523 1272 y Fi(2)p 2600 1290 V 2435 1390 V 2479 1360 a Fn(a)2523 1372 y Fi(1)p 2600 1390 V 2435 1545 4 155 v 2508 1448 a Fs(.)2508 1482 y(.)2508 1515 y(.)p 2600 1545 V 2437 1548 165 4 v 947 1780 a(Figure)27 b(2:)37 b(Sequences)27 b(used)g(in)h(the)g(pro)r(of)f(of)h(Theorem)f(3.1.1)3325 2030 y Fc(2)648 2172 y Fs(As)40 b(w)n(e)f(can)h(see)g(the)g(ab)r(o)n(v) n(e)f(lo)n(w)n(er)f(b)r(ound)j(is)e(tigh)n(t,)44 b(since)39 b(algorithm)g(RRFWF)523 2271 y(describ)r(ed)27 b(in)h(Section)g(2)f(is) h(\()p Fn(k)21 b Fs(+)d Fn(w)r Fs(\)-comp)r(etitiv)n(e)28 b(for)g(F)-7 b(air-IMTP)26 b(with)i Fn(t)23 b Fs(=)g Fn(w)e Fm(\000)d Fs(1.)523 2435 y Fd(Corollary)32 b(3.1.2)40 b Fp(A)n(lgorithm)22 b(RRFWF)e(is)i(str)l(ongly)f(c)l(omp)l(etitive)h (for)h(F)-6 b(air-IMTP)22 b(with)523 2534 y Fn(t)h Fs(=)g Fn(w)e Fm(\000)d Fs(1)p Fp(,)30 b Fn(k)25 b Fs(=)e(1)29 b Fp(and)i(even)e Fn(w)r Fp(.)523 2763 y Fl(3.2)112 b(Finite)36 b(Sequences)523 2917 y Fs(W)-7 b(e)31 b(can)g(repro)r(duce)f(in)h(the)g (\014nite)g(mo)r(del)g(the)g(results)g(w)n(e)f(ha)n(v)n(e)g(obtained)g (for)h(in\014nite)523 3016 y(sequences.)k(The)25 b(follo)n(wing)f(lo)n (w)n(er)g(b)r(ound)h(for)g(F)-7 b(air-FMTP)24 b(with)h Fn(t)e Fs(=)g Fn(w)16 b Fm(\000)d Fs(1)24 b(and)h Fn(k)h Fs(=)d(1)523 3116 y(is)28 b(only)f(in)n(teresting)g(when)g(the)h(n)n (um)n(b)r(er)g(of)f(sequences)g(is)h Fn(w)d Fs(=)e(2.)523 3279 y Fd(Theorem)30 b(3.2.1)40 b Fp(No)34 b(on-line)h(algorithm)g(for) g(F)-6 b(air-FMTP)36 b(with)f Fn(t)c Fs(=)f Fn(w)24 b Fm(\000)e Fs(1)p Fp(,)35 b Fn(k)e Fs(=)e(1)523 3379 y Fp(and)j(even)f Fn(w)r Fp(,)i(is)e Fn(c)p Fp(-c)l(omp)l(etitive)h(if)g Fn(c)29 b(<)g(w)24 b Fs(+)c(1)p Fp(,)34 b(even)f(if)h(we)g(r)l(estrict) e(the)i(se)l(quenc)l(es)e(of)523 3479 y(r)l(e)l(quests)d(to)h(b)l(e)f (forme)l(d)i(by)f(at)g(most)g Fs(2)f Fp(distinct)h(p)l(ages.)523 3642 y Fd(Pro)s(of)83 b Fs(The)41 b(pro)r(of)g(is)h(the)g(same)e(of)i (Theorem)e(3.1.1,)k(except)e(that)f(w)n(e)g(use)h(\014nite)523 3742 y(sequences,)27 b(all)g(of)h(them)g(of)g(the)f(same)h(length.)1285 b Fc(2)648 3883 y Fs(Again)26 b(the)g(ab)r(o)n(v)n(e)f(lo)n(w)n(er)g(b) r(ound)i(is)f(tigh)n(t)h(for)e(the)i(cases)f(in)g(whic)n(h)g(comp)r (etitiv)n(e)h(on-)523 3983 y(line)34 b(algorithms)e(can)i(exist,)h (since)f(algorithm)e(RRFWF)j(is)f(\()p Fn(k)25 b Fs(+)d Fn(w)r Fs(\)-comp)r(etitiv)n(e)35 b(for)523 4083 y(F)-7 b(air-FMTP)27 b(with)h Fn(t)23 b Fs(=)f Fn(w)f Fm(\000)d Fs(1)28 b(and)f Fn(w)f Fm(\024)c Fs(2.)523 4246 y Fd(Corollary)32 b(3.2.2)40 b Fp(A)n(lgorithm)j(RRFWF)g(is)g(str)l(ongly)g(c)l(omp)l (etitive)i(for)f(F)-6 b(air-FMTP)523 4346 y(with)30 b Fn(t)23 b Fs(=)g Fn(w)e Fm(\000)d Fs(1)p Fp(,)30 b Fn(k)c Fs(=)c(1)30 b Fp(and)g Fn(w)c Fs(=)c(2)p Fp(.)523 4617 y Fu(4)135 b(The)44 b(Case)i Fg(k)37 b Ff(=)c(1)45 b Fu(and)f(Odd)h Fg(w)523 4799 y Fs(In)27 b(this)f(section)h(w)n(e)f (will)g(consider)g(an)g(o)r(dd)g(n)n(um)n(b)r(er)h(of)f(sequences)g (for)g(F)-7 b(air-MTP)25 b(with)523 4898 y Fn(t)j Fs(=)g Fn(w)c Fm(\000)c Fs(1)30 b(and)h Fn(k)g Fs(=)d(1.)46 b(This)31 b(completes)g(the)g(analysis)e(of)i(F)-7 b(air-MTP)29 b(when)i(the)h(size)p eop 29 8 bop 523 324 a Fs(A.)28 b(Strejilevic)n(h)g(de)f(Loma,)g Fp(F)-6 b(air)30 b(Multi-thr)l(e)l(ade)l(d)h(Paging)7 b Fs(,)29 b Fo(EJS)p Fs(,)f(1\(1\))f(21{36)f(\(1998\))10 b(29)523 614 y(of)30 b(the)g(cac)n(he)f(is)h(1.)44 b(As)30 b(w)n(e)f(will)h(see,)h(lo)n(w)n(er)d(and)i(upp)r(er)g(b)r(ounds)g (di\013er)g(from)g(the)g(ones)523 714 y(obtained)35 b(for)g(an)h(ev)n (en)f(n)n(um)n(b)r(er)g(of)g(sequences.)60 b(Nev)n(ertheless,)37 b(again)d(w)n(e)h(will)h(sho)n(w)523 814 y(an)k(optimal)g(on-line)g (algorithm.)74 b(Moreo)n(v)n(er,)40 b(w)n(e)g(will)h(pro)n(v)n(e)d (that)j(an)n(y)e(reasonable)523 913 y(algorithm)f(is)h(optimal.)70 b(The)39 b(only)g(case)f(of)h(F)-7 b(air-FMTP)38 b(with)h(an)g(o)r(dd)g (n)n(um)n(b)r(er)f(of)523 1013 y(sequences)33 b(in)g(whic)n(h)h(comp)r (etitiv)n(e)f(on-line)g(algorithms)f(can)h(exist)g(is)h(regular)d(P)n (aging)523 1112 y(\()p Fn(w)26 b Fs(=)d(1\);)k(so)f(w)n(e)g(will)h (omit)g(a)f(useless)g(discussion,)g(and)h(w)n(e)f(will)h(treat)f(only)h (the)g(in\014nite)523 1212 y(mo)r(del.)523 1445 y Fl(4.1)112 b(In\014nite)37 b(Sequences)523 1598 y Fs(W)-7 b(e)28 b(start)f(with)h(a)f(lo)n(w)n(er)f(b)r(ound)i(for)f(the)h(comp)r (etitiv)n(e)g(ratio)f(of)g(on-line)g(algorithms.)523 1780 y Fd(Theorem)j(4.1.1)40 b Fp(No)c(on-line)g(algorithm)h(for)f(F)-6 b(air-IMTP)37 b(with)f Fn(t)d Fs(=)g Fn(w)26 b Fm(\000)c Fs(1)p Fp(,)37 b Fn(k)f Fs(=)d(1)523 1880 y Fp(and)25 b(o)l(dd)h Fn(w)r Fp(,)h(is)e Fn(c)p Fp(-c)l(omp)l(etitive)h(if)f Fn(c)e(<)g(w)r Fp(,)k(even)e(if)h(we)f(r)l(estrict)f(the)h(se)l(quenc)l (es)g(of)g(r)l(e)l(quests)523 1980 y(to)30 b(b)l(e)g(forme)l(d)g(by)h (at)e(most)h Fs(2)f Fp(distinct)h(p)l(ages.)523 2162 y Fd(Pro)s(of)61 b Fs(If)20 b Fn(w)26 b Fs(=)d(1)c(then)h(there)g(is)g (nothing)f(to)h(pro)n(v)n(e.)32 b(F)-7 b(or)20 b Fn(w)25 b Fm(\025)e Fs(3)c(the)h(pro)r(of)g(is)f(as)g(follo)n(ws.)523 2262 y(The)24 b(\014rst)f Fn(w)13 b Fm(\000)d Fs(1)23 b(sequences)g(are)g(constructed)g(as)g(in)h(Theorem)f(3.1.1.)34 b(Sequence)23 b Fn(\033)3188 2274 y Fk(w)3266 2262 y Fs(is)h(a)523 2362 y(cop)n(y)j(of)h Fn(\033)859 2374 y Fi(1)897 2362 y Fs(.)39 b(Without)29 b(loss)e(of)h(generalit)n(y)f (assume)g(again)g(that)h(the)h(on-line)f(algorithm)523 2461 y(A)i(serv)n(es)d(the)j(sequences)e(in)h(the)h(order)e Fn(\033)1889 2473 y Fi(1)1926 2461 y Fn(;)14 b(\033)2010 2473 y Fi(2)2048 2461 y Fn(;)g(:)g(:)g(:)f(\033)2242 2473 y Fk(w)2297 2461 y Fs(.)41 b(In)30 b(this)f(situation)g(A)g (faults)h(on)523 2561 y(eac)n(h)24 b(request)h(of)g(the)g(o)r(dd)h(ro)n (ws)d(\(note)j(that)f(the)h(ev)n(en)e(ro)n(ws)g(are)g(redundan)n(t\).) 36 b(Then)25 b(its)523 2660 y(cost)30 b(for)f Fn(`)e Fs(=)g(2)p Fn(w)r(n)j Fs(requests)f(is)h Fn(C)1632 2672 y Fk(A)1714 2660 y Fm(\025)d Fn(w)r(n)p Fs(.)45 b(The)30 b(adv)n(ersary)e(can)h(group)g(the)i(rep)r(eated)523 2760 y(requests)j(as)g(in)h(Theorem)f(3.1.1)g(faulting)h(only)f(once)h (ev)n(ery)e(t)n(w)n(o)i(ro)n(ws,)g(with)g(a)g(total)523 2860 y(cost)27 b Fn(C)753 2872 y Fk(AD)r(V)940 2860 y Fm(\024)c Fn(n)p Fs(.)37 b(Therefore)26 b(w)n(e)h(ha)n(v)n(e)1659 3020 y Fn(C)1718 3032 y Fk(A)p 1604 3057 223 4 v 1604 3133 a Fn(C)1663 3145 y Fk(AD)r(V)1860 3076 y Fm(\025)1958 3020 y Fn(w)r(n)p 1958 3057 112 4 v 1989 3133 a(n)2102 3076 y Fs(=)c Fn(w)44 b(:)3325 3274 y Fc(2)648 3423 y Fs(In)35 b(normal)g(P)n(aging)f(with)i Fn(k)j Fs(=)d(1)g(there)f(is)h (no)f(particular)f(strategy)h(that)h(a)f(go)r(o)r(d)523 3523 y(algorithm)f(m)n(ust)h(follo)n(w:)50 b(if)36 b(the)f(requested)f (page)g(is)h(in)g(the)h(cac)n(he,)f(then)h(nothing)e(is)523 3623 y(done;)27 b(otherwise)e(the)i(page)f(m)n(ust)h(b)r(e)g(brough)n (t)e(in)n(to)i(fast)f(memory)-7 b(,)26 b(replacing)g(the)h(only)523 3722 y(page)34 b(that)h(is)g(there.)59 b(An)n(y)35 b(algorithm)e(that)j (do)r(es)e(not)h(unnecessarily)f(evict)h(pages)e(is)523 3822 y(optimal.)h(In)19 b(F)-7 b(air-IMTP)18 b(with)i Fn(t)j Fs(=)f Fn(w)t Fm(\000)r Fs(1)d(and)g Fn(k)26 b Fs(=)c(1)d(the)g(situation)g(is)g(the)h(same,)g(except)523 3922 y(that)25 b(the)h(algorithms)d(can)i(c)n(ho)r(ose)e(b)r(et)n(w)n (een)i Fn(w)r Fs(!)h(distinct)f(orders)f(of)g(the)i(sequences.)35 b(W)-7 b(e)523 4021 y(said)30 b(that)g(this)h(c)n(hoice)e(is)h(useless) f(for)h(an)g(on-line)g(algorithm,)f(so)h(it)g(mak)n(es)f(sense)h(that) 523 4121 y(an)n(y)e(on-line)h(algorithm)f(is)h(strongly)f(comp)r (etitiv)n(e.)41 b(W)-7 b(e)30 b(will)f(no)n(w)f(see)h(that)h(this)f(is) g(the)523 4220 y(case,)j(at)f(least)g(for)g(an)g(o)r(dd)h(n)n(um)n(b)r (er)f(of)g(sequences.)48 b(W)-7 b(e)32 b(are)e(able)h(to)h(pro)n(v)n(e) d(that)j(an)n(y)523 4320 y(lazy)24 b(algorithm)g(\(on-line)h(or)f (not\))h(for)f(F)-7 b(air-IMTP)24 b(with)h Fn(t)e Fs(=)g Fn(w)15 b Fm(\000)e Fs(1,)25 b Fn(k)h Fs(=)c(1)j(and)g(o)r(dd)g Fn(w)r Fs(,)523 4420 y(is)32 b Fn(w)r Fs(-comp)r(etitiv)n(e.)49 b(A)32 b(lazy)f(algorithm)g(is)h(one)f(whic)n(h)h(only)f(evicts)g(a)h (page)f(on)g(a)g(page)523 4519 y(fault,)d(and)g(in)f(that)h(case)f (evicts)g(exactly)g(one)h(page.)523 4702 y Fd(Theorem)i(4.1.2)40 b Fp(A)n(ny)29 b(lazy)i(algorithm)g(for)g(F)-6 b(air-IMTP)31 b(with)g Fn(t)23 b Fs(=)f Fn(w)f Fm(\000)d Fs(1)p Fp(,)30 b Fn(k)c Fs(=)d(1)29 b Fp(and)523 4802 y(o)l(dd)i Fn(w)r Fp(,)g(is)f Fn(w)r Fp(-c)l(omp)l(etitive.)p eop 30 9 bop 523 324 a Fs(A.)28 b(Strejilevic)n(h)g(de)f(Loma,)g Fp(F)-6 b(air)30 b(Multi-thr)l(e)l(ade)l(d)h(Paging)7 b Fs(,)29 b Fo(EJS)p Fs(,)f(1\(1\))f(21{36)f(\(1998\))10 b(30)523 614 y Fd(Pro)s(of)83 b Fs(Let)42 b(A)f(b)r(e)h(an)n(y)f(lazy)g (algorithm)f(\(on-line)h(or)g(not\))h(and)f(AD)n(V)h(an)g(o\013-line) 523 714 y(adv)n(ersary)-7 b(.)55 b(T)-7 b(o)34 b(measure)f(the)i(costs) e(of)i(b)r(oth)f(algorithms)f(w)n(e)h(will)h(split)g(the)g(ro)n(ws)d (of)523 814 y(requests)d(in)n(to)g(disjoin)n(t)h Fp(stages)p Fs(.)44 b(The)29 b(\014rst)h(stage)f(starts)g(with)h(the)g(\014rst)f (ro)n(w)g(and)g(ends)523 913 y(with)34 b(the)f(\014rst)g(ro)n(w)f(in)h (whic)n(h)g(the)g(adv)n(ersary)d(has)j(no)g(cost.)52 b(Eac)n(h)32 b(new)h(stage)f(starts)523 1013 y(with)37 b(the)g(ro)n(w)e(immediately)i(after)f(the)h(last)f(ro)n(w)f(of)h(the)h (previous)e(stage,)j(and)e(ends)523 1112 y(with)31 b(the)g(next)g(ro)n (w)e(in)i(whic)n(h)g(again)e(the)i(adv)n(ersary)d(has)i(no)g(cost.)46 b(W)-7 b(e)31 b(will)f(consider)523 1212 y(that)24 b(the)g Fn(i)p Fs(-th)g(stage)e(starts)h(and)h(ends)f(with)i(the)f Fn(p)2143 1224 y Fk(i)2170 1212 y Fs(-th)g(and)g(the)g Fn(q)2634 1224 y Fk(i)2661 1212 y Fs(-th)g(ro)n(ws)f(of)g(requests,)523 1312 y(resp)r(ectiv)n(ely)-7 b(.)43 b(W)-7 b(e)30 b(will)g(denote)g(b)n (y)f Fn(C)1764 1282 y Fk(i)1758 1335 y(A)1843 1312 y Fs(and)g Fn(C)2065 1324 y Fk(A)2120 1312 y Fs(\()p Fn(j)5 b Fs(\))30 b(the)g(costs)f(of)h(A)g(in)h(the)f Fn(i)p Fs(-th)f(stage)523 1411 y(and)f(in)h(the)g Fn(j)5 b Fs(-th)29 b(ro)n(w,)f(resp)r(ectiv)n(ely)-7 b(.)39 b(A)29 b(similar)f(notation)g (is)g(v)-5 b(alid)29 b(for)f(the)h(adv)n(ersary)-7 b(.)523 1511 y(Notice)28 b(that)g(\()p Fm(8)p Fn(j)5 b Fs(\))14 b Fn(C)1187 1523 y Fk(A)1240 1511 y Fs(\()p Fn(j)5 b Fs(\))24 b Fm(\024)f Fn(w)r Fs(.)648 1611 y(Supp)r(ose)35 b(that)h(after)e Fn(`)h Fs(requests)g(the)h(algorithms)d(completed)j Fn(m)f Fs(stages)f(and)h(are)523 1710 y(curren)n(tly)22 b(in)h(the)g(\()p Fn(m)9 b Fs(+)g(1\)-st)22 b(stage.)34 b(Before)22 b(w)n(e)h(measure)e(the)j(costs)e(of)h(the)g(algorithms,) 523 1810 y(it)33 b(is)g(con)n(v)n(enien)n(t)f(to)g(p)r(oin)n(t)h(out)g (some)f(facts)h(ab)r(out)g(the)g(stages)e(w)n(e)i(ha)n(v)n(e)e (de\014ned.)53 b(In)523 1910 y(the)25 b(completed)f(stages)f(\()p Fn(i)g Fm(\024)g Fn(m)p Fs(\),)i(the)f(last)g(ro)n(w)f(v)n(eri\014es)g Fn(C)2405 1922 y Fk(AD)r(V)2569 1910 y Fs(\()p Fn(q)2638 1922 y Fk(i)2666 1910 y Fs(\))h(=)e(0,)j(whic)n(h)f(implies)523 2009 y(that)33 b(all)f(the)h(requests)f(in)h(the)g(ro)n(w)e(are)g(to)i (the)g(same)f(page,)h(and)f(hence)h Fn(C)3012 2021 y Fk(A)3066 2009 y Fs(\()p Fn(q)3135 2021 y Fk(i)3163 2009 y Fs(\))f Fm(\024)f Fs(1;)523 2109 y(b)r(esides,)d(b)r(oth)h(A)g(and)f (the)g(adv)n(ersary)d(start)j(the)h(next)f(stage)f(with)i(the)f(same)g (con)n(ten)n(ts)523 2208 y(in)j(the)f(cac)n(he.)44 b(On)30 b(the)h(other)f(hand,)h(in)f(eac)n(h)g(ro)n(w)f Fn(r)k Fs(but)e(the)g(last)f(one)f(\()p Fn(p)2983 2220 y Fk(i)3039 2208 y Fm(\024)e Fn(r)j(<)d(q)3327 2220 y Fk(i)3355 2208 y Fs(\))523 2308 y(w)n(e)e(ha)n(v)n(e)f Fn(C)891 2320 y Fk(AD)r(V)1055 2308 y Fs(\()p Fn(r)r Fs(\))h Fm(\025)d Fs(1;)k(this)g(is)f(also)f(true)i(for)f(the)g(completed)h(ro)n(ws)e(of) h(the)h(\()p Fn(m)14 b Fs(+)g(1\)-st)523 2408 y(stage,)27 b(b)r(ecause)g(otherwise)g(w)n(e)g(w)n(ould)g(ha)n(v)n(e)f(an)i (additional)f(stage.)648 2507 y(W)-7 b(e)28 b(will)f(no)n(w)g(analyze)g (the)h(costs)f(in)h(the)g(di\013eren)n(t)f(stages:)648 2668 y Fm(\017)41 b Fs(In)31 b(the)g(\014rst)f(stage,)h(all)f(the)h(ro) n(ws)f(but)h(the)g(last)g(one)f(v)n(erify)g Fn(C)2768 2680 y Fk(AD)r(V)2932 2668 y Fs(\()p Fn(r)r Fs(\))f Fm(\025)f Fs(1,)k(and)731 2767 y(then)c(w)n(e)f(ha)n(v)n(e)1691 2867 y Fn(C)1756 2833 y Fi(1)1750 2887 y Fk(A)1827 2867 y Fm(\024)c Fn(w)r(C)2041 2833 y Fi(1)2035 2887 y Fk(AD)r(V)2218 2867 y Fs(+)18 b Fn(w)44 b(:)648 3044 y Fm(\017)d Fs(In)36 b(the)g(last)g(stage,)h(all)e(the)i(ro)n(ws)d(except)i(ev)n(en)n (tually)f(the)i(last)e(one)h(v)n(erify)f(the)731 3143 y(same)27 b(condition)g Fn(C)1362 3155 y Fk(AD)r(V)1526 3143 y Fs(\()p Fn(r)r Fs(\))d Fm(\025)f Fs(1,)k(and)h(then)g(w)n(e)f (ha)n(v)n(e)1570 3319 y Fn(C)1635 3283 y Fk(m)p Fi(+1)1629 3343 y Fk(A)1805 3319 y Fm(\024)c Fn(w)r(C)2019 3283 y Fk(m)p Fi(+1)2013 3343 y Fk(AD)r(V)2196 3319 y Fs(+)18 b Fn(w)j Fm(\000)d Fs(1)41 b Fn(:)648 3526 y Fm(\017)g Fs(Let)30 b Fn(s)g Fs(b)r(e)g(an)g(in)n(termediate)f(stage)g(\(2)e Fm(\024)f Fn(i)h Fm(\024)g Fn(m)p Fs(\))j(for)f(whic)n(h)h(A)g(do)r(es) g(not)g(pa)n(y)f(in)731 3626 y(the)j(last)f(ro)n(w)g(of)g(the)h(stage.) 49 b(Again)31 b(all)g(the)i(other)e(ro)n(ws)f(v)n(erify)h Fn(C)2930 3638 y Fk(AD)r(V)3094 3626 y Fs(\()p Fn(r)r Fs(\))g Fm(\025)f Fs(1,)731 3725 y(and)d(then)h(w)n(e)f(ha)n(v)n(e)1772 3825 y Fn(C)1837 3791 y Fk(i)1831 3845 y(A)1909 3825 y Fm(\024)22 b Fn(w)r(C)2122 3791 y Fk(i)2116 3845 y(AD)r(V)2323 3825 y Fn(:)648 4002 y Fm(\017)41 b Fs(W)-7 b(e)31 b(m)n(ust)g(no)n(w)g (consider)f(the)h(costs)f(in)i(eac)n(h)e(in)n(termediate)g(stage)g(\(2) f Fm(\024)f Fn(i)h Fm(\024)f Fn(m)p Fs(\))731 4101 y(for)37 b(whic)n(h)h(A)h(pa)n(ys)e(in)i(the)f(last)g(ro)n(w)f(of)h(the)h (stage.)68 b(The)38 b(only)g(p)r(ossibilit)n(y)f(is)731 4201 y(that)c Fn(C)975 4213 y Fk(A)1030 4201 y Fs(\()p Fn(q)1099 4213 y Fk(i)1127 4201 y Fs(\))g(=)f(1,)j(since)e(w)n(e)h(kno) n(w)e(that)i Fn(C)2194 4213 y Fk(A)2249 4201 y Fs(\()p Fn(q)2318 4213 y Fk(i)2346 4201 y Fs(\))f Fm(\024)f Fs(1.)54 b(First)34 b(notice)f(that)h(the)731 4301 y(algorithms)28 b(start)h(the)h(last)f(ro)n(w)g(of)g(the)h(stage)f(with)h(di\013eren)n (t)g(con)n(ten)n(ts)f(in)g(their)731 4400 y(cac)n(hes;)g(this)h(is)f(b) r(ecause)g(all)h(the)g(requests)e(in)i(that)g(ro)n(w)e(are)h(to)g(the)h (same)f(page,)731 4500 y(while)19 b Fn(C)998 4512 y Fk(A)1053 4500 y Fs(\()p Fn(q)1122 4512 y Fk(i)1150 4500 y Fs(\))k Fm(6)p Fs(=)g Fn(C)1352 4512 y Fk(AD)r(V)1516 4500 y Fs(\()p Fn(q)1585 4512 y Fk(i)1613 4500 y Fs(\))d(\(1)j Fm(6)p Fs(=)f(0\).)34 b(It)20 b(follo)n(ws)f(that)h(the)g(stage)e(has)h (at)h(least)f(t)n(w)n(o)731 4599 y(ro)n(ws)24 b(of)i(requests.)35 b(W)-7 b(e)27 b(claim)f(that)g(among)f(the)h(ro)n(ws)f(that)h(are)f (not)h(the)g(last)g(one)731 4699 y(of)31 b(the)i(stage,)f(there)g (exists)f(at)h(least)f(one)h(ro)n(w)f(whic)n(h)g(v)n(eri\014es)g Fn(C)2875 4711 y Fk(A)2930 4699 y Fs(\()p Fn(t)2992 4711 y Fk(i)3020 4699 y Fs(\))f Fm(\024)g Fn(w)24 b Fm(\000)d Fs(1)731 4799 y(or)34 b Fn(C)899 4811 y Fk(AD)r(V)1063 4799 y Fs(\()p Fn(t)1125 4811 y Fk(i)1152 4799 y Fs(\))i Fm(\025)f Fs(2.)58 b(Supp)r(ose)35 b(this)g(is)g(not)g(true,)h(i.)f (e.,)i(for)d(eac)n(h)g(ro)n(w)g(w)n(e)h(ha)n(v)n(e)731 4898 y Fn(C)790 4910 y Fk(A)844 4898 y Fs(\()p Fn(r)r Fs(\))26 b(=)f Fn(w)31 b Fs(and)e Fn(C)1375 4910 y Fk(AD)r(V)1539 4898 y Fs(\()p Fn(r)r Fs(\))d(=)f(1,)k(in)g(particular)e(for)h(the)h (\014rst)g(ro)n(w)e(of)i(the)g(stage.)p eop 31 10 bop 523 324 a Fs(A.)28 b(Strejilevic)n(h)g(de)f(Loma,)g Fp(F)-6 b(air)30 b(Multi-thr)l(e)l(ade)l(d)h(Paging)7 b Fs(,)29 b Fo(EJS)p Fs(,)f(1\(1\))f(21{36)f(\(1998\))10 b(31)731 614 y(Let)29 b Fn(a)925 626 y Fk(i)982 614 y Fs(b)r(e)h(the)f(page)g(in)g(the)h(cac)n(hes)e(of)h(b)r(oth)h(A)f(and)h (the)f(adv)n(ersary)e(when)i(they)731 714 y(start)21 b(serving)h(the)h(stage.)34 b(Since)22 b Fn(C)1855 726 y Fk(AD)r(V)2019 714 y Fs(\()p Fn(p)2093 726 y Fk(i)2121 714 y Fs(\))h(=)g(1,)g(from)f(the)h(adv)n(ersary's)d(p)r(oin)n(t)i(of) 731 814 y(view,)i(this)h(\014rst)f(ro)n(w)f(is)h(formed)g(b)n(y)g(zero) f(or)h(more)f(requests)g(to)h(page)g Fn(a)3019 826 y Fk(i)3046 814 y Fs(,)h(follo)n(w)n(ed)731 913 y(b)n(y)i(one)f(or)h (more)f(requests)h(to)g(another)f(page)g Fn(b)2262 925 y Fk(i)2317 913 y Fs(\()p Fn(b)2385 925 y Fk(i)2436 913 y Fm(6)p Fs(=)c Fn(a)2567 925 y Fk(i)2595 913 y Fs(\).)37 b(On)27 b(the)h(other)e(hand,)731 1013 y(since)d Fn(C)989 1025 y Fk(A)1043 1013 y Fs(\()p Fn(p)1117 1025 y Fk(i)1145 1013 y Fs(\))g(=)g Fn(w)r Fs(,)i(for)e(A)h(the)g(ro)n(w)f(lo)r(oks)f (lik)n(e)i(alternating)e(requests)h(to)g(pages)g Fn(a)3360 1025 y Fk(i)731 1112 y Fs(and)28 b Fn(b)929 1124 y Fk(i)956 1112 y Fs(,)h(starting)f(and)g(ending)g(with)h Fn(b)1975 1124 y Fk(i)2031 1112 y Fs(b)r(ecause)f(A)h(faults)g(on)f(eac)n(h)g (request)g(and)731 1212 y Fn(w)g Fs(is)d(o)r(dd.)37 b(Hence,)26 b(once)f(the)h(\014rst)f(ro)n(w)g(of)g(the)h(stage)f(is)g(completed,)h (w)n(e)g(are)e(as)h(in)731 1312 y(the)e(b)r(eginning)g(of)h(the)f (stage,)g(in)h(the)f(sense)g(that)h(b)r(oth)f(A)h(and)f(the)g(adv)n (ersary)e(has)731 1411 y(the)32 b(same)f(con)n(ten)n(ts)g(in)i(the)f (cac)n(he)f(\(no)n(w)h(it)g(is)g(page)f Fn(b)2518 1423 y Fk(i)2545 1411 y Fs(\).)50 b(W)-7 b(e)33 b(can)e(think)h(ab)r(out)731 1511 y(the)g(second)g(ro)n(w)f(of)i(the)f(stage)g(lik)n(e)g(w)n(e)g (did)g(ab)r(out)h(the)f(\014rst,)i(and)e(so)g(on,)h(un)n(til)731 1611 y(w)n(e)27 b(arriv)n(e)f(to)i(the)g(last)g(ro)n(w)e(of)i(the)g (stage.)37 b(This)28 b(last)g(ro)n(w)e(starts)h(with)i(the)f(same)731 1710 y(con)n(ten)n(ts)j(in)h(the)g(cac)n(he)f(of)h(b)r(oth)g (algorithms,)f(but)i(w)n(e)e(said)g(it)i(cannot)e(happ)r(en.)731 1810 y(This)26 b(is)g(a)g(con)n(tradiction,)f(and)h(therefore)g(our)f (claim)h(is)h(true.)36 b(If)27 b Fn(C)2901 1822 y Fk(A)2955 1810 y Fs(\()p Fn(t)3017 1822 y Fk(i)3045 1810 y Fs(\))c Fm(\024)g Fn(w)18 b Fm(\000)e Fs(1)731 1910 y(w)n(e)27 b(ha)n(v)n(e)1119 2092 y Fn(C)1178 2104 y Fk(A)1232 2092 y Fs(\()p Fn(t)1294 2104 y Fk(i)1322 2092 y Fs(\))19 b(+)f Fn(C)1515 2104 y Fk(A)1569 2092 y Fs(\()p Fn(q)1638 2104 y Fk(i)1666 2092 y Fs(\))24 b Fm(\024)e Fs(\()p Fn(w)g Fm(\000)c Fs(1\))g(+)g(1)23 b(=)f Fn(w)k Fm(\024)d Fn(w)r(C)2625 2104 y Fk(AD)r(V)2789 2092 y Fs(\()p Fn(t)2851 2104 y Fk(i)2879 2092 y Fs(\))g(=)1516 2275 y(=)f Fn(w)17 b Fs([)p Fn(C)1761 2287 y Fk(AD)r(V)1925 2275 y Fs(\()p Fn(t)1987 2287 y Fk(i)2015 2275 y Fs(\))h(+)h Fn(C)2208 2287 y Fk(AD)r(V)2371 2275 y Fs(\()p Fn(q)2440 2287 y Fk(i)2468 2275 y Fs(\)])56 b Fn(;)731 2424 y Fs(while)27 b(if)h Fn(C)1082 2436 y Fk(AD)r(V)1246 2424 y Fs(\()p Fn(t)1308 2436 y Fk(i)1336 2424 y Fs(\))c Fm(\025)e Fs(2)1202 2607 y Fn(C)1261 2619 y Fk(A)1315 2607 y Fs(\()p Fn(t)1377 2619 y Fk(i)1405 2607 y Fs(\))d(+)f Fn(C)1598 2619 y Fk(A)1652 2607 y Fs(\()p Fn(q)1721 2619 y Fk(i)1749 2607 y Fs(\))24 b Fm(\024)e Fn(w)f Fs(+)d(1)23 b Fm(\024)g Fs(2)p Fn(w)i Fm(\024)e Fn(w)r(C)2542 2619 y Fk(AD)r(V)2706 2607 y Fs(\()p Fn(t)2768 2619 y Fk(i)2796 2607 y Fs(\))g(=)1516 2790 y(=)f Fn(w)17 b Fs([)p Fn(C)1761 2802 y Fk(AD)r(V)1925 2790 y Fs(\()p Fn(t)1987 2802 y Fk(i)2015 2790 y Fs(\))h(+)h Fn(C)2208 2802 y Fk(AD)r(V)2371 2790 y Fs(\()p Fn(q)2440 2802 y Fk(i)2468 2790 y Fs(\)])56 b Fn(:)731 2939 y Fs(Since)31 b(the)h(ro)n(w)e(w)n(e)h(found)g(v)n(eri\014es)f(at)h(least)g(one)g(of) g(those)g(conditions,)h(and)f(the)731 3039 y(other)g(ro)n(ws)f(in)i (the)h(stage)e(\(except)h(the)g(last)g(one\))f(v)n(erify)h Fn(C)2703 3051 y Fk(AD)r(V)2867 3039 y Fs(\()p Fn(r)r Fs(\))f Fm(\025)f Fs(1,)j(again)731 3138 y(w)n(e)27 b(ha)n(v)n(e)1772 3238 y Fn(C)1837 3204 y Fk(i)1831 3258 y(A)1909 3238 y Fm(\024)22 b Fn(w)r(C)2122 3204 y Fk(i)2116 3258 y(AD)r(V)2323 3238 y Fn(:)523 3421 y Fs(The)h(total)f(costs)g Fn(C)1140 3433 y Fk(A)1217 3421 y Fs(and)h Fn(C)1433 3433 y Fk(AD)r(V)1620 3421 y Fs(are)f(the)h(sums)f(of)h(the)g(costs)f(in)h(eac)n(h)f(stage,)h (and)f(hence)756 3678 y Fn(C)815 3690 y Fk(A)893 3678 y Fs(=)980 3574 y Fk(m)p Fi(+1)992 3599 y Fb(X)998 3775 y Fk(i)p Fi(=1)1137 3678 y Fn(C)1202 3643 y Fk(i)1196 3698 y(A)1274 3678 y Fm(\024)1361 3536 y Fb( )1427 3574 y Fk(m)p Fi(+1)1439 3599 y Fb(X)1445 3775 y Fk(i)p Fi(=1)1584 3678 y Fn(w)r(C)1710 3643 y Fk(i)1704 3698 y(AD)r(V)1869 3536 y Fb(!)1953 3678 y Fs(+)c(2)p Fn(w)i Fm(\000)e Fs(1)23 b(=)g Fn(w)r(C)2513 3690 y Fk(AD)r(V)2696 3678 y Fs(+)18 b(\(2)p Fn(w)j Fm(\000)d Fs(1\))41 b Fn(;)523 3933 y Fs(that)28 b(is,)f(A)h(is)g Fn(w)r Fs(-comp)r(etitiv)n(e.)1808 b Fc(2)648 4082 y Fs(The)26 b(preceding)f(pro)r(of)h(cannot)g(b)r(e)h (applied)f(to)g(an)g(ev)n(en)g(n)n(um)n(b)r(er)g(of)g(sequences;)g(the) 523 4182 y(problem)j(arises)f(with)i(the)f(last)h(kind)f(of)g(stages)g (w)n(e)g(considered,)f(where)h(the)h(induction)523 4281 y(is)e(not)f(v)-5 b(alid)28 b(for)f(an)g(ev)n(en)g Fn(w)r Fs(.)648 4381 y(It)35 b(is)h(w)n(orth)n(while)f(to)g(men)n(tion)h(that) f(the)h(lo)n(w)n(er)e(b)r(ounds)i(sho)n(wn)f(in)h(this)g(and)f(the)523 4481 y(previous)c(section)h(can)f(b)r(e)i(generalized)d(to)i(arbitrary) e(v)-5 b(alues)32 b(of)g Fn(k)s Fs(,)h(so)f(as)f(to)h(obtain)g(a)523 4580 y(general)f(lo)n(w)n(er)g(b)r(ound)i(of)g(\(roughly\))f Fn(w)r(=k)s Fs(.)52 b(This)32 b(new)h(lo)n(w)n(er)e(b)r(ound)i(is)f (linear)g(in)h(the)523 4680 y(n)n(um)n(b)r(er)j(of)f(sequences,)i(and)f (when)g Fn(w)j(>)e(k)1987 4650 y Fi(2)2060 4680 y Fs(it)f(is)g(b)r (etter)g(than)g(the)g(already)e(kno)n(wn)523 4780 y(lo)n(w)n(er)26 b(b)r(ound)i(of)g Fn(k)s Fs(.)p eop 32 11 bop 523 324 a Fs(A.)28 b(Strejilevic)n(h)g(de)f(Loma,)g Fp(F)-6 b(air)30 b(Multi-thr)l(e)l(ade)l(d)h(Paging)7 b Fs(,)29 b Fo(EJS)p Fs(,)f(1\(1\))f(21{36)f(\(1998\))10 b(32)523 684 y Fe(While)42 b(there)f(is)i(at)g(least)e(one)h(request)f (to)i(be)g(served)e(do)785 784 y(\045)i(a)g(new)f(super-phase)d(starts) 785 883 y(Repeat)1090 983 y(Apply)i(a)i(phase)f(of)h(FWF)f(to)h(the)f (sequence)e Fn(\033)2752 953 y Fj(\003)2835 983 y Fe(formed)h(by)1090 1083 y(taking)g(in)i(turn)e(one)i(request)d(of)j(each)f(active)f (sequence)785 1182 y(Until)85 b(it)42 b(is)h(possible)d(to)j(serve)f (with)g(unitary)e(cost)1090 1282 y(the)i(next)g(request)f(of)h Fn(\033)2011 1252 y Fj(\003)2094 1282 y Fe(and)g(all)g(the)h(pending)d (requests)1090 1381 y(in)i(the)h(same)f(row)g(of)h(that)f(request)785 1481 y(Serve)f(the)h(next)g(request)f(of)i Fn(\033)1968 1451 y Fj(\003)2050 1481 y Fe(and)f(all)h(the)f(pending)f(requests)785 1581 y(in)h(the)h(same)f(row)g(of)h(that)f(request)e(\(with)i(unitary)f (cost\))523 1680 y(end)h(While.)1043 1946 y Fs(Figure)27 b(3:)36 b(Algorithm)27 b(Chec)n(k-Ro)n(w{Flush-When-F)-7 b(ull)523 2211 y Fu(5)135 b(The)44 b(Case)i Fg(w)36 b Fa(\024)d Fg(k)523 2393 y Fs(In)27 b(this)g(section)f(w)n(e)h(will)g (analyze)f(the)h(case)f(of)g(F)-7 b(air-MTP)26 b(in)h(whic)n(h)g Fn(w)e Fm(\024)e Fn(k)s Fs(.)36 b(This)27 b(case)523 2493 y(is)c(the)h(opp)r(osite)f(situation)g(to)h(the)f(extreme)g(case)g (of)g(the)h(t)n(w)n(o)f(previous)f(sections)h(\(where)523 2592 y(w)n(e)32 b(considered)f Fn(k)i Fs(=)e(1\).)50 b(W)-7 b(e)33 b(will)f(presen)n(t)f(a)h(new)g(on-line)g(algorithm)f (for)h(F)-7 b(air-MTP)523 2692 y(and)33 b(w)n(e)f(will)i(sho)n(w)e (that)h(for)f Fn(w)j Fm(\024)c Fn(k)36 b Fs(it)e(b)r(eha)n(v)n(es)d(b)r (etter)j(than)f(RRFWF,)h(the)f(kno)n(wn)523 2792 y(on-line)27 b(algorithm)g(for)g(F)-7 b(air-MTP.)523 3024 y Fl(5.1)112 b(In\014nite)37 b(Sequences)523 3177 y Fs(The)24 b(new)g(on-line)g (algorithm)f(for)g(F)-7 b(air-MTP)23 b(is)h(called)g(Chec)n(k-Ro)n (w{Flush-When-F)-7 b(ull)523 3277 y(\(CRFWF\),)34 b(and)e(it)h(is)g (describ)r(ed)f(in)h(Fig.)13 b(3.)52 b(Algorithm)32 b(CRFWF)h(can)f(b)r (e)h(regarded)523 3376 y(as)h(a)f(mo)r(di\014cation)i(of)f(RRFWF:)h (CRFWF)g(w)n(orks)e(in)h(sup)r(er-phases)f(and)h(serv)n(es)f(the)523 3476 y(requests)24 b(ro)n(w)f(b)n(y)i(ro)n(w)e(as)h(RRFWF)i(do)r(es;)f (the)g(di\013erence)g(is)g(that)g(in)g(eac)n(h)f(sup)r(er-phase)523 3576 y(RRFWF)36 b(applies)f(one)f(phase)h(of)g(FWF)g(and)g(serv)n(es)f (some)g(additional)g(requests)g(\(see)523 3675 y(Fig.)14 b(1\),)33 b(while)f(CRFWF)h(applies)f(one)f(or)g(more)h(phases)f(of)h (FWF)h(un)n(til)f(it)h(is)f(p)r(ossible)523 3775 y(to)25 b(serv)n(e)e(the)i(additional)f(requests)g(with)h(unitary)g(cost.)35 b(As)25 b(w)n(e)f(will)h(see)g(no)n(w,)g(CRFWF)523 3875 y(b)r(eats)j(RRFWF)g(in)g(F)-7 b(air-IMTP)26 b(with)i Fn(t)23 b Fs(=)g Fn(w)e Fm(\000)d Fs(1)27 b(and)h Fn(w)e Fm(\024)c Fn(k)s Fs(.)523 4057 y Fd(Theorem)30 b(5.1.1)40 b Fp(A)n(lgorithm)28 b(CRFWF)f(is)g Fs(\()p Fn(k)15 b Fs(+)d(1\))p Fp(-c)l(omp)l(etitive)28 b(for)f(F)-6 b(air-IMTP)29 b(with)523 4157 y Fn(t)23 b Fs(=)g Fn(w)e Fm(\000)d Fs(1)29 b Fp(and)h Fn(w)c Fm(\024)d Fn(k)s Fp(.)523 4340 y Fd(Pro)s(of)68 b Fs(Assume)26 b(that)g(after)g Fn(`)g Fs(requests)f(CRFWF)i(completed) f Fn(m)g Fs(sup)r(er-phases,)f(eac)n(h)523 4439 y(one)h(ha)n(ving)g Fn(p)983 4451 y Fk(i)1033 4439 y Fm(\025)d Fs(1)j(phases)g(\(1)d Fm(\024)g Fn(i)f Fm(\024)h Fn(m)p Fs(\),)k(and)g(is)f(curren)n(tly)g (in)h(the)g(\()p Fn(m)17 b Fs(+)f(1\)-st)26 b(sup)r(er-)523 4539 y(phase)e(with)h Fn(p)979 4551 y Fk(m)p Fi(+1)1149 4539 y Fm(\025)e Fs(0)h(phases)g(completed)g(in)h(this)g(last)f(sup)r (er-phase.)35 b(T)-7 b(o)24 b(terminate)h(a)523 4638 y(sup)r(er-phase)h(CRFWF)i(en)n(tirely)e(serv)n(es)f(its)i(last)g(ro)n (w;)f(th)n(us)h(the)g(adv)n(ersary)d(has)j(serv)n(ed)523 4738 y(all)g(the)g(requests)g(in)g(the)g(sup)r(er-phases)f(that)i (CRFWF)g(has)e(completed.)37 b(Consider)26 b(the)523 4838 y Fn(i)p Fs(-th)31 b(of)g(those)g(sup)r(er-phases)f(\(1)f Fm(\024)g Fn(i)g Fm(\024)g Fn(m)p Fs(\).)48 b(By)31 b(de\014nition)g (of)h(CRFWF,)g(the)g(cost)e(of)p eop 33 12 bop 523 324 a Fs(A.)28 b(Strejilevic)n(h)g(de)f(Loma,)g Fp(F)-6 b(air)30 b(Multi-thr)l(e)l(ade)l(d)h(Paging)7 b Fs(,)29 b Fo(EJS)p Fs(,)f(1\(1\))f(21{36)f(\(1998\))10 b(33)523 614 y(eac)n(h)27 b(phase)g(is)g(at)h(most)f Fn(k)s Fs(,)h(and)f(then)h(the)g(cost)f(for)h(the)g(sup)r(er-phase)e (is)1352 771 y Fn(C)1417 736 y Fk(i)1411 791 y(C)t(RF)9 b(W)g(F)1714 771 y Fm(\024)23 b Fn(p)1844 783 y Fk(i)1871 771 y Fn(k)f Fs(+)c(1)k Fm(\024)h Fs(\()p Fn(k)e Fs(+)d(1\))p Fn(p)2466 783 y Fk(i)2535 771 y Fn(:)523 927 y Fs(T)-7 b(o)34 b(analyze)f(the)i(adv)n(ersary's)d(cost)i(in)g(the)h(sup)r (er-phase,)g(w)n(e)f(asso)r(ciate)f(to)i(eac)n(h)e(o)r(dd)523 1027 y(phase)d(an)h Fp(xphase)g Fs(\(extended)h(phase\))e(as)g(follo)n (ws:)42 b(w)n(e)30 b(include)i(in)f(the)g(xphase)f(all)g(the)523 1126 y(requests)c(of)h(the)g(o)r(dd)g(phase)f(plus)h(the)g(next)g (request)f(serv)n(ed)g(b)n(y)g(CRFWF,)i(and)f(all)f(the)523 1226 y(requests)31 b(in)i(the)f(ro)n(ws)f(of)h(the)g(already)f (included)i(requests;)g(note)f(that)h(w)n(e)f(include)g(in)523 1326 y(the)22 b(xphase)f(all)h(or)f(none)h(of)f(the)i(requests)e(of)g (an)n(y)g(giv)n(en)g(ro)n(w.)34 b(Being)22 b Fn(w)j Fm(\024)e Fn(k)s Fs(,)g(eac)n(h)e(phase)523 1425 y(has)30 b(at)h(least)f Fn(w)j Fs(requests,)e(and)f(then)h(the)g(xphases)f(are)g(disjoin)n(t.) 46 b(F)-7 b(rom)30 b(the)h(b)r(eha)n(vior)523 1525 y(of)26 b(FWF)h(w)n(e)f(kno)n(w)f(that)h(in)g(eac)n(h)g(xphase)f(at)h(least)g Fn(k)18 b Fs(+)d(1)25 b(di\013eren)n(t)h(pages)f(app)r(ear;)h(this)523 1625 y(implies)f(that)g(the)g(adv)n(ersary)d(m)n(ust)i(fault)h(at)g (least)f(once)g(in)h(eac)n(h)f(xphase.)35 b(If)25 b(an)f(xphase)523 1724 y(is)35 b(not)g(asso)r(ciated)f(with)i(the)f(last)g(phase)g(of)g (the)g(sup)r(er-phase,)h(then)g(the)g(n)n(um)n(b)r(er)e(of)523 1824 y(distinct)28 b(pages)e(is)i(at)f(least)g Fn(k)21 b Fs(+)d(2)27 b(\(b)r(ecause)g(otherwise)g(the)h(sup)r(er-phase)e(w)n (ould)h(\014nish)523 1923 y(in)i(that)h(xphase\);)f(in)g(these)g (xphases)g(the)g(adv)n(ersary)d(m)n(ust)j(fault)h(at)f(least)f(t)n (wice.)41 b(If)30 b Fn(p)3360 1935 y Fk(i)523 2023 y Fs(is)j(ev)n(en,)i(there)e(is)h(no)f(xphase)g(asso)r(ciated)f(with)i (the)g(last)f(phase)g(of)h(the)f(sup)r(er-phase;)523 2123 y(then)28 b(the)g(cost)f(of)h(the)g(adv)n(ersary)d(in)i(the)h(sup) r(er-phase)f(is)1601 2296 y Fn(C)1666 2261 y Fk(i)1660 2316 y(AD)r(V)1847 2296 y Fm(\025)22 b Fs(2)1986 2240 y Fn(p)2028 2252 y Fk(i)p 1986 2277 70 4 v 2000 2353 a Fs(2)2088 2296 y(=)h Fn(p)2218 2308 y Fk(i)2287 2296 y Fn(:)523 2475 y Fs(If)32 b Fn(p)652 2487 y Fk(i)712 2475 y Fs(is)g(o)r(dd,)h(the)f(last)g(xphase)f(corresp)r(onds)f(to)i (the)g(last)g(phase)f(of)h(the)g(sup)r(er-phase,)523 2575 y(and)27 b(hence)h(the)g(cost)f(is)1458 2693 y Fn(C)1523 2659 y Fk(i)1517 2714 y(AD)r(V)1704 2693 y Fm(\025)22 b Fs(2)1843 2637 y Fn(p)1885 2649 y Fk(i)1931 2637 y Fm(\000)c Fs(1)p 1843 2674 213 4 v 1928 2750 a(2)2084 2693 y(+)g(1)k(=)h Fn(p)2361 2705 y Fk(i)2430 2693 y Fn(:)523 2850 y Fs(In)28 b(b)r(oth)g(cases)e(w)n(e)i(ha)n(v)n(e)e(for)h (the)h(costs)f(in)h(the)g(sup)r(er-phase)1243 3006 y Fn(C)1308 2972 y Fk(i)1302 3027 y(C)t(RF)9 b(W)g(F)1605 3006 y Fm(\024)23 b Fs(\()p Fn(k)e Fs(+)d(1\))p Fn(p)1988 3018 y Fk(i)2039 3006 y Fm(\024)k Fs(\()p Fn(k)g Fs(+)c(1\))p Fn(C)2445 2972 y Fk(i)2439 3027 y(AD)r(V)2644 3006 y Fn(:)523 3163 y Fs(In)28 b(the)g(\()p Fn(m)18 b Fs(+)g(1\)-st)28 b(sup)r(er-phase)e(the)i(cost)f(of)h(CRFWF)g(is)1157 3319 y Fn(C)1222 3284 y Fk(m)p Fi(+1)1216 3343 y Fk(C)t(RF)9 b(W)g(F)1519 3319 y Fm(\024)23 b Fn(p)1649 3331 y Fk(m)p Fi(+1)1795 3319 y Fn(k)f Fs(+)c Fn(k)26 b Fm(\024)c Fs(\()p Fn(k)g Fs(+)c(1\))p Fn(p)2395 3331 y Fk(m)p Fi(+1)2560 3319 y Fs(+)g Fn(k)44 b(:)523 3475 y Fs(W)-7 b(e)31 b(can)f(think)h(ab) r(out)g(the)g(adv)n(ersary's)c(cost)k(in)f(this)h(sup)r(er-phase)f(as)g (w)n(e)g(did)h(for)f(the)523 3575 y(other)g(sup)r(er-phases.)45 b(Nev)n(ertheless)30 b(w)n(e)g(m)n(ust)h(discard)f(the)h(last)f(phase)g (of)h(the)g(sup)r(er-)523 3675 y(phase,)22 b(b)r(ecause)f(w)n(e)g(do)g (not)g(kno)n(w)g(whether)g(the)h(adv)n(ersary)c(has)j(serv)n(ed)f (those)h(requests.)523 3774 y(Th)n(us)27 b(w)n(e)h(ha)n(v)n(e)1590 3874 y Fn(C)1655 3838 y Fk(m)p Fi(+1)1649 3898 y Fk(AD)r(V)1836 3874 y Fm(\025)23 b Fn(p)1966 3886 y Fk(m)p Fi(+1)2131 3874 y Fm(\000)18 b Fs(1)41 b Fn(;)523 4008 y Fs(whic)n(h)28 b(implies)523 4164 y Fn(C)588 4129 y Fk(m)p Fi(+1)582 4188 y Fk(C)t(RF)9 b(W)g(F)885 4164 y Fm(\024)23 b Fs(\()p Fn(k)5 b Fs(+)r(1\))p Fn(p)1236 4176 y Fk(m)p Fi(+1)1384 4164 y Fs(+)r Fn(k)25 b Fs(=)e(\()p Fn(k)5 b Fs(+)r(1\))14 b(\()o Fn(p)1915 4176 y Fk(m)p Fi(+1)2081 4164 y Fm(\000)k Fs(1\))q(+)r(2)p Fn(k)5 b Fs(+)r(1)21 b Fm(\024)i Fs(\()p Fn(k)5 b Fs(+)r(1\))p Fn(C)2900 4129 y Fk(m)p Fi(+1)2894 4188 y Fk(AD)r(V)3059 4164 y Fs(+)r(2)p Fn(k)g Fs(+)r(1)39 b Fn(:)523 4320 y Fs(Summing)25 b(o)n(v)n(er)e(all)h(the)h(sup)r (er-phases)f(w)n(e)g(obtain)g(that)h(the)g(total)g(costs)f Fn(C)2949 4332 y Fk(C)t(RF)9 b(W)g(F)3254 4320 y Fs(and)523 4420 y Fn(C)582 4432 y Fk(AD)r(V)774 4420 y Fs(v)n(erify)523 4651 y Fn(C)582 4663 y Fk(C)t(RF)g(W)g(F)885 4651 y Fs(=)973 4547 y Fk(m)p Fi(+1)984 4572 y Fb(X)990 4749 y Fk(i)p Fi(=1)1129 4651 y Fn(C)1194 4617 y Fk(i)1188 4671 y(C)t(RF)g(W)g(F)1492 4651 y Fm(\024)22 b Fs(\()p Fn(k)s Fs(+1\))1810 4547 y Fk(m)p Fi(+1)1821 4572 y Fb(X)1828 4749 y Fk(i)p Fi(=1)1967 4651 y Fn(C)2032 4617 y Fk(i)2026 4671 y(AD)r(V)2190 4651 y Fs(+2)p Fn(k)s Fs(+1)g(=)g(\()p Fn(k)s Fs(+1\))p Fn(C)2835 4663 y Fk(AD)r(V)2999 4651 y Fs(+\(2)p Fn(k)s Fs(+1\))41 b Fn(:)3325 4859 y Fc(2)p eop 34 13 bop 523 324 a Fs(A.)28 b(Strejilevic)n(h)g(de)f(Loma,)g Fp(F)-6 b(air)30 b(Multi-thr)l(e)l(ade)l(d)h(Paging)7 b Fs(,)29 b Fo(EJS)p Fs(,)f(1\(1\))f(21{36)f(\(1998\))10 b(34)523 677 y(T)-7 b(able)39 b(1:)59 b(Summary)38 b(of)h(previous)f (and)h(curren)n(t)f(results)g(ab)r(out)h(F)-7 b(air-IMTP)37 b(\(Im)j(=)523 776 y(Impro)n(v)n(ed;)26 b(Cl)i(=)f(Closed\).)p 549 892 2813 4 v 547 991 4 100 v 564 991 V 1697 991 V 1714 991 V 1821 961 a(Previous)p 2237 991 V 2254 991 V 403 w(Curren)n(t)p 3105 991 V 3122 991 V 3343 991 V 3360 991 V 1716 995 1408 4 v 547 1091 4 100 v 564 1091 V 1697 1091 V 1714 1091 V 1765 1061 a(l.b.)p 1929 1091 V 136 w(u.b.)p 2237 1091 V 2254 1091 V 196 w(l.b.)p 2558 1091 V 180 w(u.b.)p 2867 1091 V 135 w(Im?)p 3105 1091 V 3122 1091 V 117 w(Cl?)p 3343 1091 V 3360 1091 V 549 1094 2813 4 v 547 1194 4 100 v 564 1194 V 615 1164 a Fn(t)c Fm(\025)g Fn(w)p 1697 1194 V 1714 1194 V 966 w Fm(1)p 1929 1194 V 188 w(\000)p 2237 1194 V 2254 1194 V 249 w(1)p 2558 1194 V 233 w(\000)p 2867 1194 V 3105 1194 V 3122 1194 V 3199 1105 a(p)p 3343 1194 V 3360 1194 V 549 1197 2813 4 v 547 1297 4 100 v 564 1297 V 615 1267 a Fn(t)g Fs(=)g Fn(w)e Fm(\000)d Fs(1,)27 b Fn(k)f Fs(=)d(1)k(and)g(ev) n(en)g Fn(w)p 1697 1297 V 1714 1297 V 156 w Fs(1)p 1929 1297 V 138 w Fn(w)22 b Fs(+)c(1)p 2237 1297 V 2254 1297 V 117 w Fn(w)k Fs(+)c(1)p 2558 1297 V 101 w Fn(w)j Fs(+)d(1)p 2867 1297 V 2953 1208 a Fm(p)p 3105 1297 V 3122 1297 V 177 w(p)p 3343 1297 V 3360 1297 V 549 1300 2813 4 v 547 1400 4 100 v 564 1400 V 615 1370 a Fn(t)23 b Fs(=)g Fn(w)e Fm(\000)d Fs(1,)27 b Fn(k)f Fs(=)d(1)k(and)g(o)r(dd)h Fn(w)p 1697 1400 V 1714 1400 V 181 w Fs(1)p 1929 1400 V 138 w Fn(w)22 b Fs(+)c(1)p 2237 1400 V 2254 1400 V 189 w Fn(w)p 2558 1400 V 247 w(w)p 2867 1400 V 2953 1311 a Fm(p)p 3105 1400 V 3122 1400 V 177 w(p)p 3343 1400 V 3360 1400 V 549 1403 2813 4 v 547 1503 4 100 v 564 1503 V 615 1473 a Fn(t)23 b Fs(=)g Fn(w)e Fm(\000)d Fs(1)27 b(and)h Fn(w)d Fm(\024)e Fn(k)p 1697 1503 V 1714 1503 V 435 w(k)p 1929 1503 V 137 w(k)f Fs(+)c Fn(w)p 2237 1503 V 2254 1503 V 198 w(k)p 2558 1503 V 192 w(k)j Fs(+)d(1)p 2867 1503 V 2953 1414 a Fm(p)p 3105 1503 V 3122 1503 V 3343 1503 V 3360 1503 V 549 1506 2813 4 v 547 1606 4 100 v 564 1606 V 615 1576 a Fn(t)23 b Fs(=)g Fn(w)e Fm(\000)d Fs(1)27 b(and)h Fn(w)d(>)e(k)j(>)c Fs(1)p 1697 1606 V 1714 1606 V 280 w Fn(k)p 1929 1606 V 137 w(k)g Fs(+)c Fn(w)p 2237 1606 V 2254 1606 V 198 w(k)p 2558 1606 V 182 w(k)j Fs(+)d Fn(w)p 2867 1606 V 3105 1606 V 3122 1606 V 3343 1606 V 3360 1606 V 549 1609 2813 4 v 523 1941 a Fl(5.2)112 b(Finite)36 b(Sequences)523 2094 y Fs(T)-7 b(o)41 b(conclude)h(our)e(analysis)h(w)n(e)g(will)h(pro)n(v)n (e)d(that)j(algorithm)f(CRFWF)h(is)g(\()p Fn(k)30 b Fs(+)e(1\)-)523 2194 y(comp)r(etitiv)n(e)36 b(also)e(for)h(F)-7 b(air-FMTP)35 b(with)h Fn(w)j Fm(\024)d Fn(k)s Fs(.)61 b(Of)35 b(course)g(w)n(e)g (are)g(restricted)f(to)523 2294 y(the)28 b(situations)f(in)h(whic)n(h)g (comp)r(etitiv)n(e)f(on-line)g(algorithms)g(can)g(exist.)523 2476 y Fd(Theorem)j(5.2.1)40 b Fp(A)n(lgorithm)26 b(CRFWF)f(is)g Fs(\()p Fn(k)10 b Fs(+)d(1\))p Fp(-c)l(omp)l(etitive)26 b(for)f(F)-6 b(air-FMTP)27 b(with)523 2576 y Fn(t)c Fs(=)g Fn(w)e Fm(\000)d Fs(1)p Fp(,)30 b Fn(w)25 b Fm(\024)e Fn(k)32 b Fp(and)f Fn(w)25 b Fm(\024)e Fs(2)p Fp(.)523 2758 y Fd(Pro)s(of)71 b Fs(With)31 b(t)n(w)n(o)e(activ)n(e)g(sequences) f(CRFWF)j(b)r(eha)n(v)n(es)d(as)h(in)h(the)g(in\014nite)h(v)n(ersion,) 523 2858 y(and)i(hence)h(its)g(cost)f(is)g(at)g(most)h Fn(k)25 b Fs(+)d(1)33 b(times)g(the)h(optimal)g(cost)f(necessary)e(to)j (serv)n(e)523 2958 y(those)c(requests.)45 b(The)30 b(p)r(erformance)f (of)i(CRFWF)g(is)f(the)h(same)f(with)h(only)f(one)g(activ)n(e)523 3057 y(sequence.)36 b(In)28 b(an)n(y)f(case)g(the)h(algorithm)e (results)h(\()p Fn(k)22 b Fs(+)c(1\)-comp)r(etitiv)n(e.)477 b Fc(2)523 3382 y Fu(6)135 b(Concluding)45 b(Remarks)523 3564 y Fs(T)-7 b(able)26 b(1)g(summarizes)g(our)f(results)h(ab)r(out)g (F)-7 b(air-IMTP)g(,)26 b(as)f(w)n(ell)h(as)g(the)h(results)f(already) 523 3663 y(kno)n(wn;)i(w)n(e)f(assume)g Fn(w)g(>)c Fs(1)28 b(through)f(the)h(table.)38 b(In)28 b(the)h(\014nite)f(mo)r(del)h(the)f (results)f(are)523 3763 y(the)h(same,)f(except)h(that)g(no)f(comp)r (etitiv)n(e)h(on-line)f(algorithm)f(can)h(exist)h(if)g Fn(w)e Fm(\025)c Fs(3.)648 3862 y(When)i(the)h(size)f(of)g(the)g(cac)n (he)f(is)h(1,)h(ha)n(ving)e(an)h(ev)n(en)g(n)n(um)n(b)r(er)f(of)h (threads)g(is)g(sligh)n(tly)523 3962 y(more)18 b(di\016cult)i(for)e (on-line)h(algorithms)e(than)i(the)g(case)f(in)i(whic)n(h)e(the)i(n)n (um)n(b)r(er)e(of)h(threads)523 4062 y(is)30 b(o)r(dd.)43 b(The)29 b(di\016cult)n(y)h(probably)f(dep)r(ends)h(not)g(only)f(on)g (the)h(parit)n(y)f(of)h Fn(w)i Fs(itself,)f(but)523 4161 y(on)25 b(its)h(relationship)e(with)i(the)g(size)f(of)h(the)f(cac)n (he.)36 b(The)25 b(fact)h(that)g(b)r(oth)f Fn(w)k Fs(and)c Fn(k)j Fs(a\013ect)523 4261 y(the)i(b)r(eha)n(vior)f(of)h(on-line)f (algorithms)f(b)r(ecomes)i(clear)f(when)h(w)n(e)f(compare)g(the)h (results)523 4361 y(for)e(the)h(t)n(w)n(o)f(opp)r(osite)h(situations)f (w)n(e)h(ha)n(v)n(e)e(considered:)38 b(when)29 b Fn(k)f Fs(=)d(1)f Fn(<)h(w)32 b Fs(there)c(is)h(a)523 4460 y(tigh)n(t)e(b)r (ound)g(near)f(to)g Fn(w)r Fs(,)i(while)f(if)g Fn(w)f Fm(\024)c Fn(k)30 b Fs(on-line)c(comp)r(etitiv)n(eness)h(is)f(b)r(et)n (w)n(een)h Fn(k)j Fs(and)523 4560 y Fn(k)12 b Fs(+)d(1.)35 b(It)23 b(seems)g(that)g(when)h(the)f(cac)n(he)f(is)h(small)g(the)g (adv)n(ersary)d(can)j(tak)n(e)f(b)r(ene\014t)i(of)f(its)523 4659 y(decision)j(ab)r(out)h(the)h(order)d(in)i(whic)n(h)g(to)g(serv)n (e)e(the)j(sequences;)e(th)n(us)h(the)g(p)r(erformance)523 4759 y(of)35 b(on-line)f(algorithms)g(get)h(w)n(orse)e(when)i(the)g(n)n (um)n(b)r(er)g(of)g(sequences)f(increases.)58 b(On)523 4859 y(the)32 b(other)g(hand,)h(when)f(the)h(cac)n(he)e(is)h(big)f (enough)h(the)g(p)r(erm)n(utation)g(of)g(the)g(threads)p eop 35 14 bop 523 324 a Fs(A.)28 b(Strejilevic)n(h)g(de)f(Loma,)g Fp(F)-6 b(air)30 b(Multi-thr)l(e)l(ade)l(d)h(Paging)7 b Fs(,)29 b Fo(EJS)p Fs(,)f(1\(1\))f(21{36)f(\(1998\))10 b(35)523 614 y(migh)n(t)25 b(ha)n(v)n(e)f(a)h(lo)r(cal)f(e\013ect,)j (and)e(then)g(the)h(p)r(erformance)e(that)h(on-line)g(algorithms)f(can) 523 714 y(ac)n(hiev)n(e)i(is)i(similar)f(to)g(the)h(one)f(observ)n(ed)f (in)i(normal)f(P)n(aging.)648 814 y(Although)i(w)n(e)g(impro)n(v)n(ed)f (previous)h(results)g(and)g(w)n(e)g(closed)g(some)g(gaps,)g(there)g (are)523 913 y(still)34 b(di\013erences)g(b)r(et)n(w)n(een)g(curren)n (t)g(lo)n(w)n(er)e(and)i(upp)r(er)g(b)r(ounds;)k(a)c(nice)g(result)g(w) n(ould)523 1013 y(b)r(e)28 b(to)g(close)f(those)g(gaps.)36 b(W)-7 b(e)29 b(pro)n(v)n(ed)d(that)i(an)n(y)f(lazy)g(algorithm)g(ac)n (hiev)n(es)f(the)i(on-line)523 1112 y(lo)n(w)n(er)c(b)r(ound)h(if)h Fn(k)g Fs(=)c(1)j(and)g Fn(w)j Fs(is)d(o)r(dd;)i(w)n(e)d(kno)n(w)h (that)g(algorithm)f(RRFWF)i(is)g(optimal)523 1212 y(when)33 b(the)g(n)n(um)n(b)r(er)f(of)g(sequences)g(is)g(ev)n(en,)i(but)f(it)f (w)n(ould)g(b)r(e)h(in)n(teresting)f(to)g(analyze)523 1312 y(whether)c(that)f(general)g(result)g(is)g(v)-5 b(alid)28 b(in)g(this)g(case)f(to)r(o.)648 1411 y(Sev)n(eral)22 b(in)n(teresting)h(researc)n(h)f(directions)h(are)g(p)r(ossible.)36 b(One)23 b(of)h(them)h(is)f(mo)r(deling)523 1511 y(fairness)37 b(restrictions)h(in)g(a)g(di\013eren)n(t)h(w)n(a)n(y;)j(p)r(erhaps)c (alternativ)n(e)f(mo)r(dels)i(allo)n(w)e(the)523 1611 y(existence)d(of)h(more)e(\015exible)i(comp)r(etitiv)n(e)f(on-line)g (algorithms.)56 b(Distinct)35 b(de\014nitions)523 1710 y(of)41 b(comp)r(etitiv)n(eness)f(ma)n(y)g(also)f(b)r(e)i(considered)f (for)g(the)h(in\014nite)g(problem,)j(suc)n(h)c(as)523 1810 y(comparing)17 b(the)i(p)r(erformances)e(of)h(the)h(di\013eren)n (t)g(algorithms)e(in)h(the)h(limit,)i(that)e(is,)h(when)523 1910 y(the)29 b(n)n(um)n(b)r(er)f(of)h(serv)n(ed)e(requests)h(tends)h (to)f(in\014nit)n(y)-7 b(.)40 b(Another)29 b(in)n(teresting)f(p)r (ossibilit)n(y)523 2009 y(is)g(to)f(analyze)f(randomized)h(algorithms)f (for)h(these)h(problems.)648 2109 y(A)g(general)e(observ)-5 b(ation)26 b(is)i(that)g(m)n(ulti-threaded)g(en)n(vironmen)n(ts)e(seem) i(a)f(p)r(o)n(w)n(erful)523 2208 y(mo)r(deling)g(to)r(ol)h(and)f(a)g(c) n(hallenging)g(researc)n(h)e(\014eld.)523 2408 y Fd(Ac)m(kno)m (wledgmen)m(ts:)39 b Fs(I)29 b(w)n(ould)g(lik)n(e)g(to)g(thank)g (Esteban)f(F)-7 b(euerstein)30 b(for)e(his)i(encour-)523 2507 y(agemen)n(t)d(and)g(man)n(y)g(helpful)i(suggestions)d(ab)r(out)h (this)h(w)n(ork.)523 2782 y Fu(References)565 2964 y Fs([1])41 b(H.)28 b(Alb)r(orzi,)h(E.)f(T)-7 b(orng,)27 b(P)-7 b(.)28 b(Uthaisom)n(but,)h(and)f(S.)h(W)-7 b(agner.)38 b(The)28 b Fn(k)s Fs(-clien)n(t)g(prob-)694 3063 y(lem.)36 b(In)27 b Fp(Pr)l(o)l(c)l(e)l(e)l(dings)j(of)g(the)f(Eighth)h(A)n (nnual)f(A)n(CM-SIAM)g(Symp)l(osium)g(on)h(Dis-)694 3163 y(cr)l(ete)e(A)n(lgorithms)p Fs(,)f(pages)e(73{82,)f(New)i(Orleans,)f (Louisiana,)g(5{7)g(Jan)n(uary)f(1997.)565 3329 y([2])41 b(S.)25 b(Ben-Da)n(vid,)g(A.)g(Boro)r(din,)g(R.)g(Karp,)g(G.)g(T)-7 b(ardos,)24 b(and)h(A.)h(Widgerson.)31 b(On)25 b(the)694 3429 y(p)r(o)n(w)n(er)d(of)i(randomization)e(in)i(online)g(algorithms.) 29 b(T)-7 b(ec)n(hnical)23 b(Rep)r(ort)g(TR-90-023,)694 3528 y(ICSI,)k(June)h(1990.)565 3694 y([3])41 b(A.)33 b(Boro)r(din,)f(S.)h(Irani,)g(P)-7 b(.)32 b(Ragha)n(v)-5 b(an,)32 b(and)h(B.)f(Sc)n(hieb)r(er.)51 b(Comp)r(etitiv)n(e)32 b(paging)694 3794 y(with)c(lo)r(calit)n(y)e(of)i(reference.)35 b(In)28 b Fp(Pr)l(o)l(c.)j(of)f(23r)l(d)h(A)n(CM)f(Symp)l(osium)g(on)f (The)l(ory)i(of)694 3894 y(Computing)p Fs(,)d(pages)f(249{259,)d(1991.) 565 4060 y([4])41 b(A.)f(Boro)r(din,)i(N.)e(Linial,)i(and)e(M.)g(Saks.) 72 b(An)40 b(optimal)f(on-line)g(algorithm)g(for)694 4159 y(metrical)27 b(task)g(system.)36 b Fp(J.)30 b(A)n(CM)p Fs(,)e(39\(4\):745{763,)c(1992.)565 4325 y([5])41 b(E.)27 b(F)-7 b(euerstein.)36 b Fp(On-line)29 b(Paging)i(of)f(Structur)l(e)l (d)e(Data)h(and)h(Multi-thr)l(e)l(ade)l(d)h(Pag-)694 4425 y(ing)p Fs(.)37 b(PhD)28 b(thesis,)f(Univ)n(ersit\022)-42 b(a)27 b(degli)g(Studi)i(di)e(Roma)g(\\La)g(Sapienza",)g(1995.)565 4591 y([6])41 b(E.)29 b(F)-7 b(euerstein)29 b(and)h(A.)g(Strejilevic)n (h)f(de)h(Loma.)42 b(On)29 b(m)n(ulti-threaded)h(paging.)41 b(In)694 4691 y Fp(Pr)l(o)l(c.)34 b(Seventh)g(A)n(nnual)f (International)h(Symp)l(osium)g(on)g(A)n(lgorithms)h(and)f(Com-)694 4790 y(putation)29 b(\(ISAA)n(C'96\))p Fs(,)g(v)n(olume)d(1178)g(of)h Fp(L)l(e)l(ctur)l(e)i(Notes)g(in)h(Computer)g(Scienc)l(e)p Fs(,)694 4890 y(pages)c(417{426.)e(Springer-V)-7 b(erlag,)26 b(1996.)p eop 36 15 bop 523 324 a Fs(A.)28 b(Strejilevic)n(h)g(de)f(Loma,)g Fp(F)-6 b(air)30 b(Multi-thr)l(e)l(ade)l(d)h(Paging)7 b Fs(,)29 b Fo(EJS)p Fs(,)f(1\(1\))f(21{36)f(\(1998\))10 b(36)565 614 y([7])41 b(A.)28 b(Fiat)f(and)h(A.)g(Karlin.)35 b(Randomized)28 b(and)f(m)n(ultip)r(oin)n(ter)h(paging)e(with)i(lo)r (calit)n(y)694 714 y(of)i(reference.)45 b(In)30 b Fp(Pr)l(o)l(c.)k(of)f (27th)g(A)n(CM)g(Symp)l(osium)g(on)f(The)l(ory)i(of)g(Computing)p Fs(,)694 814 y(1995.)565 980 y([8])41 b(A.)31 b(Karlin,)f(M.)g (Manasse,)g(L.)h(Rudolph,)g(and)g(D.)g(Sleator.)44 b(Comp)r(etitiv)n(e) 30 b(sno)r(op)n(y)694 1079 y(cac)n(hing.)35 b Fp(A)n(lgorithmic)l(a)p Fs(,)30 b(3:79{119,)24 b(1988.)565 1245 y([9])41 b(R.)d(Karp.)65 b(On-line)37 b(algorithms)f(v)n(ersus)g(o\013-line)i(algorithms:)55 b(ho)n(w)37 b(m)n(uc)n(h)g(is)h(it)694 1345 y(w)n(orth)26 b(to)i(kno)n(w)f(the)h(future?)46 b(T)-7 b(ec)n(hnical)27 b(Rep)r(ort)h(TR-92-044,)c(ICSI,)k(July)f(1992.)523 1511 y([10])41 b(D.D.)g(Sleator)d(and)i(R.E.)g(T)-7 b(arjan.)72 b(Amortized)40 b(e\016ciency)f(of)h(list)g(up)r(date)h(and)694 1611 y(paging)26 b(rules.)36 b Fp(Communic)l(ations)31 b(of)g(A)n(CM)p Fs(,)d(28:202{208,)23 b(1985.)523 1777 y([11])41 b(A.)36 b(Strejilevic)n(h)g(de)g(Loma.)61 b(New)36 b(results)g(on)f(fair)h(m)n(ulti-threaded)f(paging.)61 b(In)694 1876 y Fp(Pr)l(o)l(c.)41 b(First)f(A)n(r)l(gentine)g(Workshop) i(on)f(The)l(or)l(etic)l(al)h(Informatics)f(\(W)-6 b(AIT'97\))p Fs(,)694 1976 y(pages)26 b(111{122.)e(SADIO,)29 b(1997.)523 2142 y([12])41 b(A.)27 b(Strejilevic)n(h)g(de)h(Loma.)35 b(New)27 b(results)g(on)g(fair)f(m)n(ulti-threaded)h(paging.)35 b(T)-7 b(ec)n(h-)694 2242 y(nical)33 b(Rep)r(ort)g(TR)g(97-005,)f(Univ) n(ersidad)g(de)h(Buenos)g(Aires,)h(Departamen)n(to)e(de)694 2341 y(Computaci\023)-42 b(on,)27 b(July)g(1997.)35 b(h)n (ttp://www.dc.uba.ar/p)r(eople/pro)n(yin)n(v/tr.h)n(tml.)p eop end userdict /end-hook known{end-hook}if .