---------- X-Sun-Data-Type: text X-Sun-Data-Description: text X-Sun-Data-Name: text X-Sun-Charset: us-ascii X-Sun-Content-Lines: 37 Hi, My thanks to "Robert G. Ferrell" Original Question: Hi Sun-Gurus, I am looking for Kernel Conversion Tool called ECLIPSE. Does anybody know where I can find this s/w ? Working on Ultra-1/Solaris 2.5.1. Thanks. Will summarize. Regards, Pravin prchavan@pcsbom.patni.com ================================================================= Robert G. Ferrell wrote: Try Eran Gabber, one of the developers: eran@bell-labs.com ================================================================= Well, I got the reqd. info. from Eran Gabber. I am attaching the postscript file Eran sent to me , if any one else is interested. Thanks & Regards, Pravin prchavan@pcsbom.patni.com ---------- X-Sun-Data-Type: postscript-file X-Sun-Data-Name: postscript-file X-Sun-Charset: us-ascii X-Sun-Content-Lines: 8307 %!PS-Adobe-2.0 %%Creator: dvipsk 5.66a Copyright 1986-97 Radical Eye Software (www.radicaleye.com) %%Title: main.dvi %%Pages: 12 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%DocumentFonts: Times-Bold Times-Roman Times-Italic Courier %%EndComments %DVIPSCommandLine: dvips -f main %DVIPSParameters: dpi=600 %DVIPSSource: TeX output 1998.04.25:1309 %%BeginProcSet: tex.pro %! /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]{ch-image}imagemask restore}B /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 false[(Display)(NeXT) (LaserWriter 16/600)]{dup length product length le{dup length product exch 0 exch getinterval eq{pop true exit}if}{pop}ifelse}forall}{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 %%EndProcSet %%BeginProcSet: 8r.enc % @@psencodingfile@{ % author = "S. Rahtz, P. MacKay, Alan Jeffrey, B. Horn, K. Berry", % version = "0.6", % date = "22 June 1996", % filename = "8r.enc", % email = "kb@@mail.tug.org", % address = "135 Center Hill Rd. // Plymouth, MA 02360", % codetable = "ISO/ASCII", % checksum = "119 662 4424", % docstring = "Encoding for TrueType or Type 1 fonts to be used with TeX." % @} % % Idea is to have all the characters normally included in Type 1 fonts % available for typesetting. This is effectively the characters in Adobe % Standard Encoding + ISO Latin 1 + extra characters from Lucida. % % Character code assignments were made as follows: % % (1) the Windows ANSI characters are almost all in their Windows ANSI % positions, because some Windows users cannot easily reencode the % fonts, and it makes no difference on other systems. The only Windows % ANSI characters not available are those that make no sense for % typesetting -- rubout (127 decimal), nobreakspace (160), softhyphen % (173). quotesingle and grave are moved just because it's such an % irritation not having them in TeX positions. % % (2) Remaining characters are assigned arbitrarily to the lower part % of the range, avoiding 0, 10 and 13 in case we meet dumb software. % % (3) Y&Y Lucida Bright includes some extra text characters; in the % hopes that other PostScript fonts, perhaps created for public % consumption, will include them, they are included starting at 0x12. % % (4) Remaining positions left undefined are for use in (hopefully) % upward-compatible revisions, if someday more characters are generally % available. % % (5) hyphen appears twice for compatibility with both ASCII and Windows. % /TeXBase1Encoding [ % 0x00 (encoded characters from Adobe Standard not in Windows 3.1) /.notdef /dotaccent /fi /fl /fraction /hungarumlaut /Lslash /lslash /ogonek /ring /.notdef /breve /minus /.notdef % These are the only two remaining unencoded characters, so may as % well include them. /Zcaron /zcaron % 0x10 /caron /dotlessi % (unusual TeX characters available in, e.g., Lucida Bright) /dotlessj /ff /ffi /ffl /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef % very contentious; it's so painful not having quoteleft and quoteright % at 96 and 145 that we move the things normally found there down to here. /grave /quotesingle % 0x20 (ASCII begins) /space /exclam /quotedbl /numbersign /dollar /percent /ampersand /quoteright /parenleft /parenright /asterisk /plus /comma /hyphen /period /slash % 0x30 /zero /one /two /three /four /five /six /seven /eight /nine /colon /semicolon /less /equal /greater /question % 0x40 /at /A /B /C /D /E /F /G /H /I /J /K /L /M /N /O % 0x50 /P /Q /R /S /T /U /V /W /X /Y /Z /bracketleft /backslash /bracketright /asciicircum /underscore % 0x60 /quoteleft /a /b /c /d /e /f /g /h /i /j /k /l /m /n /o % 0x70 /p /q /r /s /t /u /v /w /x /y /z /braceleft /bar /braceright /asciitilde /.notdef % rubout; ASCII ends % 0x80 /.notdef /.notdef /quotesinglbase /florin /quotedblbase /ellipsis /dagger /daggerdbl /circumflex /perthousand /Scaron /guilsinglleft /OE /.notdef /.notdef /.notdef % 0x90 /.notdef /.notdef /.notdef /quotedblleft /quotedblright /bullet /endash /emdash /tilde /trademark /scaron /guilsinglright /oe /.notdef /.notdef /Ydieresis % 0xA0 /.notdef % nobreakspace /exclamdown /cent /sterling /currency /yen /brokenbar /section /dieresis /copyright /ordfeminine /guillemotleft /logicalnot /hyphen % Y&Y (also at 45); Windows' softhyphen /registered /macron % 0xD0 /degree /plusminus /twosuperior /threesuperior /acute /mu /paragraph /periodcentered /cedilla /onesuperior /ordmasculine /guillemotright /onequarter /onehalf /threequarters /questiondown % 0xC0 /Agrave /Aacute /Acircumflex /Atilde /Adieresis /Aring /AE /Ccedilla /Egrave /Eacute /Ecircumflex /Edieresis /Igrave /Iacute /Icircumflex /Idieresis % 0xD0 /Eth /Ntilde /Ograve /Oacute /Ocircumflex /Otilde /Odieresis /multiply /Oslash /Ugrave /Uacute /Ucircumflex /Udieresis /Yacute /Thorn /germandbls % 0xE0 /agrave /aacute /acircumflex /atilde /adieresis /aring /ae /ccedilla /egrave /eacute /ecircumflex /edieresis /igrave /iacute /icircumflex /idieresis % 0xF0 /eth /ntilde /ograve /oacute /ocircumflex /otilde /odieresis /divide /oslash /ugrave /uacute /ucircumflex /udieresis /yacute /thorn /ydieresis ] def %%EndProcSet %%BeginProcSet: texps.pro %! TeXDict begin /rf{findfont dup length 1 add dict begin{1 index /FID ne 2 index /UniqueID ne and{def}{pop pop}ifelse}forall[1 index 0 6 -1 roll exec 0 exch 5 -1 roll VResolution Resolution div mul neg 0 0]/Metrics exch def dict begin Encoding{exch dup type /integertype ne{pop pop 1 sub dup 0 le{pop}{[}ifelse}{FontMatrix 0 get div Metrics 0 get div def} ifelse}forall Metrics /Metrics currentdict end def[2 index currentdict end definefont 3 -1 roll makefont /setfont cvx]cvx def}def /ObliqueSlant {dup sin S cos div neg}B /SlantFont{4 index mul add}def /ExtendFont{3 -1 roll mul exch}def /ReEncodeFont{/Encoding exch def}def end %%EndProcSet %%BeginProcSet: special.pro %! TeXDict begin /SDict 200 dict N SDict begin /@SpecialDefaults{/hs 612 N /vs 792 N /ho 0 N /vo 0 N /hsc 1 N /vsc 1 N /ang 0 N /CLIP 0 N /rwiSeen false N /rhiSeen false N /letter{}N /note{}N /a4{}N /legal{}N}B /@scaleunit 100 N /@hscale{@scaleunit div /hsc X}B /@vscale{@scaleunit div /vsc X}B /@hsize{/hs X /CLIP 1 N}B /@vsize{/vs X /CLIP 1 N}B /@clip{ /CLIP 2 N}B /@hoffset{/ho X}B /@voffset{/vo X}B /@angle{/ang X}B /@rwi{ 10 div /rwi X /rwiSeen true N}B /@rhi{10 div /rhi X /rhiSeen true N}B /@llx{/llx X}B /@lly{/lly X}B /@urx{/urx X}B /@ury{/ury X}B /magscale true def end /@MacSetUp{userdict /md known{userdict /md get type /dicttype eq{userdict begin md length 10 add md maxlength ge{/md md dup length 20 add dict copy def}if end md begin /letter{}N /note{}N /legal{} N /od{txpose 1 0 mtx defaultmatrix dtransform S atan/pa X newpath clippath mark{transform{itransform moveto}}{transform{itransform lineto} }{6 -2 roll transform 6 -2 roll transform 6 -2 roll transform{ itransform 6 2 roll itransform 6 2 roll itransform 6 2 roll curveto}}{{ closepath}}pathforall newpath counttomark array astore /gc xdf pop ct 39 0 put 10 fz 0 fs 2 F/|______Courier fnt invertflag{PaintBlack}if}N /txpose{pxs pys scale ppr aload pop por{noflips{pop S neg S TR pop 1 -1 scale}if xflip yflip and{pop S neg S TR 180 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip not and{pop S neg S TR pop 180 rotate ppr 3 get ppr 1 get neg sub neg 0 TR}if yflip xflip not and{ppr 1 get neg ppr 0 get neg TR}if}{noflips{TR pop pop 270 rotate 1 -1 scale}if xflip yflip and{TR pop pop 90 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip not and{TR pop pop 90 rotate ppr 3 get ppr 1 get neg sub neg 0 TR}if yflip xflip not and{TR pop pop 270 rotate ppr 2 get ppr 0 get neg sub neg 0 S TR}if}ifelse scaleby96{ppr aload pop 4 -1 roll add 2 div 3 1 roll add 2 div 2 copy TR .96 dup scale neg S neg S TR}if}N /cp {pop pop showpage pm restore}N end}if}if}N /normalscale{Resolution 72 div VResolution 72 div neg scale magscale{DVImag dup scale}if 0 setgray} N /psfts{S 65781.76 div N}N /startTexFig{/psf$SavedState save N userdict maxlength dict begin /magscale true def normalscale currentpoint TR /psf$ury psfts /psf$urx psfts /psf$lly psfts /psf$llx psfts /psf$y psfts /psf$x psfts currentpoint /psf$cy X /psf$cx X /psf$sx psf$x psf$urx psf$llx sub div N /psf$sy psf$y psf$ury psf$lly sub div N psf$sx psf$sy scale psf$cx psf$sx div psf$llx sub psf$cy psf$sy div psf$ury sub TR /showpage{}N /erasepage{}N /copypage{}N /p 3 def @MacSetUp}N /doclip{ psf$llx psf$lly psf$urx psf$ury currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll S lineto S lineto S lineto closepath clip newpath moveto}N /endTexFig{end psf$SavedState restore}N /@beginspecial{SDict begin /SpecialSave save N gsave normalscale currentpoint TR @SpecialDefaults count /ocount X /dcount countdictstack N}N /@setspecial {CLIP 1 eq{newpath 0 0 moveto hs 0 rlineto 0 vs rlineto hs neg 0 rlineto closepath clip}if ho vo TR hsc vsc scale ang rotate rwiSeen{rwi urx llx sub div rhiSeen{rhi ury lly sub div}{dup}ifelse scale llx neg lly neg TR }{rhiSeen{rhi ury lly sub div dup scale llx neg lly neg TR}if}ifelse CLIP 2 eq{newpath llx lly moveto urx lly lineto urx ury lineto llx ury lineto closepath clip}if /showpage{}N /erasepage{}N /copypage{}N newpath }N /@endspecial{count ocount sub{pop}repeat countdictstack dcount sub{ end}repeat grestore SpecialSave restore end}N /@defspecial{SDict begin} N /@fedspecial{end}B /li{lineto}B /rl{rlineto}B /rc{rcurveto}B /np{ /SaveX currentpoint /SaveY X N 1 setlinecap newpath}N /st{stroke SaveX SaveY moveto}N /fil{fill SaveX SaveY moveto}N /ellipse{/endangle X /startangle X /yrad X /xrad X /savematrix matrix currentmatrix N TR xrad yrad scale 0 0 1 startangle endangle arc savematrix setmatrix}N end %%EndProcSet TeXDict begin 40258431 52099146 1000 600 600 (main.dvi) @start /Fa 130[40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 1[40 40 40 40 40 40 40 40 40 1[40 1[40 1[40 40 40 3[40 40 40 40 1[40 3[40 40 1[40 40 40 1[40 40 40 4[40 40 40 40 40 7[40 40 40 40 40 40 40 40 40 40 40 1[40 38[{TeXBase1Encoding ReEncodeFont}63 66.4176 /Courier rf /Fb 145[37 1[21 2[21 3[33 101[{ .167 SlantFont TeXBase1Encoding ReEncodeFont}4 74.7198 /Times-Roman rf %DVIPSBitmapFont: Fc cmsy9 9 1 /Fc 1 71 df<0000000FFFFFFFE00000007FFFFFFFF8000003FFFFFFFFFC00000FFFFFFF FFF800001F03F8000FF800007803F00003E00000F003F00003800001E003F00000000003 E007F00000000007C007E0000000000FC007E0000000000F8007E0000000001F000FE000 0000001C000FC00000000000000FC00000000000000FC00000000000001FC00000000000 001F800000000000001F800000000000001F800000000000003F000000000000003F0000 00000000003F000000000000007E000000000000007E000000000000007FFFFFE0000000 00FFFFFFC000000000FFFFFF8000000000FFFFFE0000000001F800000000000001F80000 0000000003F000000000000003F000000000000003E000000000000007E0000000000000 07C00000000000000FC00000000000000F800000000000001F800000000000001F000000 000000003F000000000000003E000000000000007E000000000000007C00000000000E00 FC00000000003F00F800000000007F01F80000000000FF81F00000000000FFC3E0000000 00007FF3C000000000007FFF8000000000003FFE0000000000001FFC00000000000007E0 0000000000003E367FB237>70 D E %EndDVIPSBitmapFont /Fd 134[33 33 50 33 37 21 29 29 1[37 37 37 54 21 33 1[21 37 37 21 33 37 33 37 37 8[46 62 1[54 42 37 46 1[46 54 50 62 2[33 25 1[54 46 46 54 50 1[46 7[37 37 37 37 37 2[37 37 1[21 1[25 19 2[25 25 25 39[{TeXBase1Encoding ReEncodeFont}54 74.7198 /Times-Italic rf %DVIPSBitmapFont: Fe cmsl8 8 4 /Fe 4 111 df<0003F000001FFC00007C1F0000F80F8003F007C007E003C007C003E00F 8003E01F8003E01F0001E03F0001E03F0003E07E0003E07E0003E07FFFFFE07FFFFFE0FE 000000FC000000FC000000FC000000FC000000FC0000007C0000007C0001807E0001803E 0003803E0007001F000E000F801C0007C0F80001FFE000007F00001B207C9E1F>101 D<000700001FC0003FC0003FC0003FC0003FC0003F80000E000000000000000000000000 00000000000000000000000000003E0007FE0007FE0000FE00007C00007C00007C00007C 00007C0000FC0000F80000F80000F80000F80000F80001F80001F00001F00001F00001F0 0001F00003F00003E00003E00003E00003E00007E00007E000FFFE00FFFE00122E7EAD14 >105 D<0007C001FFC001FF80001F80000F80000F80000F80001F80001F00001F00001F 00001F00001F00003F00003E00003E00003E00003E00003E00007E00007C00007C00007C 00007C00007C0000FC0000F80000F80000F80000F80000F80001F80001F00001F00001F0 0001F00001F00003F00003E00003E00003E00003E00007E00007E000FFFE00FFFE00122E 7EAD14>108 D<003E07F00007FE1FFC0007FE783E0000FEE01F00007DC01F00007F800F 80007F000F80007E000F80007C001F8000FC001F0000FC001F0000F8001F0000F8001F00 00F8001F0000F8003F0001F8003F0001F0003E0001F0003E0001F0003E0001F0003E0001 F0007E0003F0007E0003E0007C0003E0007C0003E0007C0003E0007C0007E000FC0007E0 00FC00FFFE1FFFC0FFFE1FFFC0221E7E9D27>110 D E %EndDVIPSBitmapFont /Ff 131[50 4[50 50 50 50 50 50 1[50 50 50 50 50 50 1[50 50 1[50 50 50 50 50 50 13[50 50 1[50 50 7[50 50 1[50 50 4[50 8[50 4[50 50 5[50 50 40[{TeXBase1Encoding ReEncodeFont}35 83.022 /Courier rf /Fg 138[45 1[45 45 1[45 45 1[45 45 2[45 45 2[45 45 45 99[{TeXBase1Encoding ReEncodeFont}12 74.7198 /Courier rf /Fh 71[25 15[25 17[37 1[33 33 24[33 37 37 54 37 37 21 29 25 37 37 37 37 58 21 37 1[21 37 37 25 33 37 33 37 33 3[25 1[25 2[54 71 54 54 46 42 50 54 42 54 54 66 46 54 29 25 54 54 42 46 54 50 50 54 6[21 37 37 37 37 37 37 37 37 37 37 21 19 25 19 2[25 25 1[58 62 25[25 7[42 42 2[{TeXBase1Encoding ReEncodeFont}78 74.7198 /Times-Roman rf %DVIPSBitmapFont: Fi cmex10 10 1 /Fi 1 81 df80 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fj cmmi7 7 2 /Fj 2 107 df<000E00001F00003F00003F00003E00001C000000000000000000000000 0000000000000000000003E00007F0000C7800187C00307C00307C00607C0060F800C0F8 00C0F80001F00001F00001F00003E00003E00007C00007C00007C1800F81800F81801F03 001F03001F06000F0C000F1C0007F00003E00011287DA617>105 D<0000070000000F8000001F8000001F8000001F0000000E000000000000000000000000 00000000000000000000000000000000000003E0000007F800000C3C0000183C0000303E 0000603E0000C03E0000C03E0001807C0001807C0000007C0000007C000000F8000000F8 000000F8000000F8000001F0000001F0000001F0000001F0000003E0000003E0000003E0 000003E0000007C0000007C0000007C0000007C000000F8000000F8000380F80007C1F00 00FC1F0000FC3E0000F87C000070F800007FE000001F800000193380A61B>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fk lasy10 10 2 /Fk 2 52 df<3FFFFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF0000000000F F0000000000FF0000000000FF0000000000FF0000000000FF0000000000FF0000000000F F0000000000FF0000000000FF0000000000FF0000000000FF0000000000FF0000000000F F0000000000FF0000000000FF0000000000FF0000000000FF0000000000FF0000000000F F0000000000FF0000000000FF0000000000FF0000000000FF0000000000FF0000000000F F0000000000FF0000000000FF0000000000FF0000000000FF0000000000FF0000000000F F0000000000FF0000000000FF0000000000FF0000000000FF0000000000FF0000000000F F0000000000FF0000000000FF0000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF FFFFFFFFFFFF303079B43E>50 D<000000180000000000003C0000000000007E00000000 0000FF000000000001FF800000000003FFC00000000007E7E0000000000FC3F000000000 1F81F8000000003F00FC000000007E007E00000000FC003F00000001F8001F80000003F0 000FC0000007E00007E000000FC00003F000001F800001F800003F000000FC00007E0000 007E0000FC0000003F0001F80000001F8003F00000000FC007E000000007E00FC0000000 03F01F8000000001F83F0000000000FC7E00000000007EFC00000000003FF80000000000 1FFC00000000003F7E00000000007E3F0000000000FC1F8000000001F80FC000000003F0 07E000000007E003F00000000FC001F80000001F8000FC0000003F00007E0000007E0000 3F000000FC00001F800001F800000FC00003F0000007E00007E0000003F0000FC0000001 F8001F80000000FC003F000000007E007E000000003F00FC000000001F81F8000000000F C3F00000000007E7E00000000003FFC00000000001FF800000000000FF0000000000007E 0000000000003C0000000000001800000038397BB843>I E %EndDVIPSBitmapFont /Fl 134[42 42 60 1[46 28 32 2[46 42 46 69 23 2[23 46 1[28 37 46 37 46 42 11[60 2[60 12[55 60 60 8[28 6[42 42 42 7[28 28 37[46 2[{TeXBase1Encoding ReEncodeFont}31 83.022 /Times-Bold rf %DVIPSBitmapFont: Fm cmr10 10 58 /Fm 58 122 df<00000006000000000000000F000000000000000F000000000000001F80 0000000000001F800000000000003FC00000000000003FC00000000000007FE000000000 00007FE0000000000000DFF0000000000000DFF00000000000018FF80000000000018FF8 00000000000307FC00000000000307FC00000000000603FE00000000000603FE00000000 000E01FF00000000000C01FF00000000001C00FF80000000001800FF800000000038007F C00000000030007FC00000000070003FE00000000060003FE000000000E0001FF0000000 00C0001FF000000001C0000FF80000000180000FF800000003800007FC00000003000007 FC00000007000003FE00000006000003FE0000000E000001FF0000000C000001FF000000 1C000000FF80000018000000FF800000380000007FC00000300000007FC0000070000000 3FE00000600000003FE00000E00000001FF00000C00000001FF00000C00000000FF00001 800000000FF800018000000007F800030000000007FC00030000000003FC000600000000 03FE00060000000001FE000C0000000001FF000C0000000000FF00180000000000FF801F FFFFFFFFFFFF803FFFFFFFFFFFFFC03FFFFFFFFFFFFFC07FFFFFFFFFFFFFE07FFFFFFFFF FFFFE0FFFFFFFFFFFFFFF0FFFFFFFFFFFFFFF03C3C7CBB45>1 D<00000FF800FC000000 7FFF07FF000001F807DF83C00007E001FF0FC0001F8007FE1FE0003F000FFC1FE0007E00 0FFC1FE0007E000FF81FE000FC000FF81FE000FC000FF0078001F80007F0000001F80003 F0000001F80003F0000001F80003F0000001F80003F0000001F80003F0000001F80003F0 000001F80003F0000001F80003F0000001F80003F0000001F80003F0000001F80003F000 0001F80003F00000FFFFFFFFFFF800FFFFFFFFFFF800FFFFFFFFFFF80001F80003F00000 01F80003F0000001F80003F0000001F80003F0000001F80003F0000001F80003F0000001 F80003F0000001F80003F0000001F80003F0000001F80003F0000001F80003F0000001F8 0003F0000001F80003F0000001F80003F0000001F80003F0000001F80003F0000001F800 03F0000001F80003F0000001F80003F0000001F80003F0000001F80003F0000001F80003 F0000001F80003F0000001F80003F0000001F80003F0000001F80003F0000001F80003F0 000001F80003F0000001F80003F0000003FC0007F800007FFFE0FFFFF0007FFFE0FFFFF0 007FFFE0FFFFF000333B7FBA30>11 D<00000FFC000000007FFF70000001F803F0000007 E007F000001F800FF000003F000FF000007E000FF000007E000FF00000FC000FF00000FC 0007F00001F80003F00001F80003F00001F80003F00001F80003F00001F80003F00001F8 0003F00001F80003F00001F80003F00001F80003F00001F80003F00001F80003F00001F8 0003F00001F80003F000FFFFFFFFF000FFFFFFFFF000FFFFFFFFF00001F80003F00001F8 0003F00001F80003F00001F80003F00001F80003F00001F80003F00001F80003F00001F8 0003F00001F80003F00001F80003F00001F80003F00001F80003F00001F80003F00001F8 0003F00001F80003F00001F80003F00001F80003F00001F80003F00001F80003F00001F8 0003F00001F80003F00001F80003F00001F80003F00001F80003F00001F80003F00001F8 0003F00001F80003F00001F80003F00001F80003F00003FC0007F8007FFFE0FFFFC07FFF E0FFFFC07FFFE0FFFFC02A3B7FBA2E>13 D<007C00000000600001FF00000000F00007C3 80000001F0000F81C0000003F0000F00E0000007E0001E007800000FC0003E003C00001F C0003C003F00007F80007C001BE003FF00007C0018FFFFBF00007800181FFC3E0000F800 1C00007C0000F8000C0000FC0000F8000C0000F80000F8000C0001F00000F8000C0003F0 0000F8000C0003E00000F8000C0007C00000F8000C000FC00000F8000C000F800000F800 0C001F000000F8001C003F000000780018003E0000007C0018007C0000007C001800FC00 00003C003800F80000003E003001F00000001E007003F00000000F00E003E00000000F81 C007C000000007C3800FC000000001FF000F80000000007C001F000000000000003F0007 C0000000003E001FF0000000007C003C3800000000FC00F81C00000000F800F00E000000 01F001E00600000003F003E00700000003E003C00300000007C007C0038000000FC007C0 018000000F8007C0018000001F00078001C000003F000F8000C000003E000F8000C00000 7C000F8000C00000FC000F8000C00000F8000F8000C00001F0000F8000C00003F0000F80 00C00003E0000F8000C00007C0000F8000C0000FC0000F8000C0000F8000078001C0001F 000007C00180003F000007C00180003E000007C00380007C000003C0030000FC000003E0 070000F8000001E0060001F0000000F00E0003F0000000F81C0003E00000003C380003C0 0000001FF000018000000007C0003A437BBD45>37 D<0000600000E00001C00003800007 00000E00001E00003C0000780000780000F00001E00001E00003C00003C00007C0000780 000F80000F00000F00001F00001E00001E00003E00003E00003E00007C00007C00007C00 007C00007C00007C0000F80000F80000F80000F80000F80000F80000F80000F80000F800 00F80000F80000F80000F80000F80000F80000F80000F80000F800007C00007C00007C00 007C00007C00007C00003E00003E00003E00001E00001E00001F00000F00000F00000F80 0007800007C00003C00003C00001E00001E00000F000007800007800003C00001E00000E 000007000003800001C00000E0000060135278BD20>40 DI<0000003000000000000078 000000000000780000000000007800000000000078000000000000780000000000007800 000000000078000000000000780000000000007800000000000078000000000000780000 000000007800000000000078000000000000780000000000007800000000000078000000 000000780000000000007800000000000078000000000000780000000000007800000000 00007800000000000078000000000000780000007FFFFFFFFFFFF8FFFFFFFFFFFFFCFFFF FFFFFFFFFC7FFFFFFFFFFFF8000000780000000000007800000000000078000000000000 780000000000007800000000000078000000000000780000000000007800000000000078 000000000000780000000000007800000000000078000000000000780000000000007800 000000000078000000000000780000000000007800000000000078000000000000780000 000000007800000000000078000000000000780000000000007800000000000078000000 0000003000000036367BAF41>43 D 45 D<1C007F00FF80FF80FF80FF80FF807F001C000909798817>I<0000000C0000001E00 00003E0000003E0000003C0000007C0000007C00000078000000F8000000F8000000F000 0001F0000001F0000001E0000003E0000003E0000003C0000007C0000007C00000078000 000F8000000F8000000F0000001F0000001F0000001E0000003E0000003E0000003C0000 007C0000007C00000078000000F8000000F8000000F0000001F0000001F0000001E00000 03E0000003E0000007C0000007C00000078000000F8000000F8000000F0000001F000000 1F0000001E0000003E0000003E0000003C0000007C0000007C00000078000000F8000000 F8000000F0000001F0000001F0000001E0000003E0000003E0000003C0000007C0000007 C00000078000000F8000000F8000000F0000001F0000001F0000001E0000003E0000003E 0000003C0000007C0000007C00000078000000F8000000F8000000F0000000600000001F 537BBD2A>I<0003F80000001FFF0000007E0FC00000F803E00001E000F00003C0007800 07C0007C000F80003E000F80003E001F00001F001F00001F003F00001F803F00001F803F 00001F807E00000FC07E00000FC07E00000FC07E00000FC07E00000FC07E00000FC0FE00 000FE0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE0000 0FE0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE00000F E0FE00000FE0FE00000FE0FE00000FE0FE00000FE07E00000FC07E00000FC07E00000FC0 7E00000FC07F00001FC03F00001F803F00001F803F00001F801F00001F001F80003F000F 80003E000F80003E0007C0007C0003E000F80001F001F00000F803E000007E0FC000001F FF00000003F80000233A7DB72A>I<0001C0000003C0000007C000001FC00000FFC000FF FFC000FFFFC000FF1FC000001FC000001FC000001FC000001FC000001FC000001FC00000 1FC000001FC000001FC000001FC000001FC000001FC000001FC000001FC000001FC00000 1FC000001FC000001FC000001FC000001FC000001FC000001FC000001FC000001FC00000 1FC000001FC000001FC000001FC000001FC000001FC000001FC000001FC000001FC00000 1FC000001FC000001FC000001FC000001FC000001FC000001FC000001FC000001FC00000 1FC000001FC000003FE0007FFFFFF07FFFFFF07FFFFFF01C3879B72A>I<000FF0000000 7FFE000001FFFF800003E03FE0000F000FF0000E0007F8001C0003FC00380001FE003000 01FE00700000FF00600000FF00FC0000FF00FF00007F80FF80007F80FF80007F80FF8000 7F80FF80007F80FF80007F807F00007F801C00007F800000007F80000000FF00000000FF 00000000FF00000001FE00000001FC00000003FC00000003F800000007F000000007E000 00000FE00000001FC00000003F800000003F000000007C00000000F800000001F0000000 03E000000007C00000000F800000000F000000001E000180003C000180007800018000F0 00038001E000030003C000030007800003000E000007000FFFFFFF001FFFFFFF003FFFFF FF007FFFFFFE00FFFFFFFE00FFFFFFFE00FFFFFFFE0021387CB72A>I<0007F80000003F FF0000007FFFC00001F80FF00003C007F800078003FC000E0001FC000F0001FE001FE000 FE001FF000FF001FF000FF001FF000FF001FF000FF001FF000FF000FE000FF0007C000FF 00000000FE00000001FE00000001FE00000001FC00000003F800000003F800000007F000 000007E00000000F800000007E0000001FFC0000001FFF800000000FE000000007F00000 0001FC00000001FE00000000FF000000007F800000007F800000007FC00000007FC00000 003FC00000003FE00000003FE01E00003FE07F80003FE0FFC0003FE0FFC0003FE0FFC000 3FE0FFC0003FE0FFC0003FC0FF80007FC07F80007F807E00007F80700000FF00380001FE 001E0001FE000F8003F80007F00FF00001FFFFC000007FFF0000000FF80000233A7DB72A >I<000000380000000038000000007800000000F800000000F800000001F800000003F8 00000007F800000007F80000000FF80000001FF80000001BF800000033F800000073F800 000063F8000000C3F8000001C3F800000183F800000303F800000703F800000603F80000 0C03F800001C03F800001803F800003003F800007003F800006003F80000C003F80001C0 03F800038003F800030003F800070003F8000E0003F8000C0003F800180003F800380003 F800300003F800600003F800E00003F800FFFFFFFFF8FFFFFFFFF8FFFFFFFFF8000003F8 00000003F800000003F800000003F800000003F800000003F800000003F800000003F800 000003F800000003F800000003F800000007FC000003FFFFF80003FFFFF80003FFFFF825 397EB82A>I<0600000C000780003C0007F003F80007FFFFF80007FFFFF00007FFFFE000 07FFFF800007FFFF000007FFFC0000067FE0000006000000000600000000060000000006 000000000600000000060000000006000000000600000000060000000006000000000600 0000000607F80000063FFE000006780F800007E007E000078003F000070001F800060001 F800060000FC00000000FE00000000FE00000000FF000000007F000000007F000000007F 800000007F800000007F800000007F803E00007F807F00007F80FF80007F80FF80007F80 FF80007F80FF80007F80FF00007F00FE0000FF00E00000FF00600000FE00700000FE0030 0001FC00380001F8001C0003F8001E0007F0000F800FE00007E03F800001FFFF0000007F FC0000001FE00000213A7CB72A>I<00003FC0000001FFF0000007FFFC00000FE03E0000 3F800700007E001F0000FC003F8001F8007F8003F0007F8003F0007F8007E0007F800FE0 003F000FC0001E001FC00000001FC00000003F800000003F800000003F800000007F8000 00007F000000007F01FC00007F07FF8000FF1E07E000FF3801F000FF7000F800FF6000FC 00FFE0007E00FFC0003F00FFC0003F00FF80003F80FF80003FC0FF80001FC0FF80001FC0 FF00001FE0FF00001FE0FF00001FE0FF00001FE0FF00001FE07F00001FE07F00001FE07F 00001FE07F00001FE07F00001FE03F80001FE03F80001FC03F80001FC01F80001FC01F80 003F801FC0003F800FC0003F0007E0007F0007E000FE0003F000FC0001F801F80000FE07 F000003FFFC000001FFF00000003FC0000233A7DB72A>I<0003F80000001FFF0000007F FFC00000FC07F00001E001F80003C000FC000780007C000700003E000F00001E000E0000 1F001E00000F001E00000F001E00000F001F00000F001F00000F001F80000F001F80001F 001FE0001E000FF0003E000FFC003C000FFE00780007FF80F00007FFC1E00003FFF3C000 01FFFF000000FFFE0000003FFF0000001FFFC000001FFFE000007FFFF80000F0FFFC0003 E07FFE0007801FFF000F000FFF801F0003FF803E0001FFC03C00007FC07C00003FC07800 000FE0F8000007E0F0000007E0F0000003E0F0000003E0F0000001E0F0000001E0F00000 01E0F8000001C078000001C078000003C07C000003803E000007001F00000F000F80001E 0007E0007C0003F803F00000FFFFE000003FFF80000007FC0000233A7DB72A>56 D<0003F80000001FFF0000007FFFC00000FC07E00003F803F00007F001F8000FE000FC00 0FC0007E001FC0007E003F80003F003F80003F007F80003F807F00003F807F00003F80FF 00001FC0FF00001FC0FF00001FC0FF00001FC0FF00001FC0FF00001FC0FF00001FE0FF00 001FE0FF00001FE0FF00001FE0FF00001FE07F00003FE07F00003FE07F80003FE03F8000 3FE01F80007FE01F80007FE00FC000FFE007E000DFE003E001DFE001F0039FE000FC0F1F E0003FFC1FC00007F01FC00000001FC00000003FC00000003F800000003F800000003F80 0000003F000000007F000F00007E001F80007E003FC000FC003FC000FC003FC001F8003F C003F0003F8007E0001F000FC0001C001F80000F807F000007FFFC000001FFF00000003F C00000233A7DB72A>I<7FFFFFFFFFFFF8FFFFFFFFFFFFFCFFFFFFFFFFFFFC7FFFFFFFFF FFF800000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000007FFFFFFFFFFFF8FF FFFFFFFFFFFCFFFFFFFFFFFFFC7FFFFFFFFFFFF836167B9F41>61 D<000001FF80018000000FFFE0038000007FFFF803800001FF807E07800003FC000F0F80 000FF000039F80001FE00001DF80003F800000FF80007F0000007F8000FE0000003F8001 FE0000003F8003FC0000001F8007F80000000F8007F80000000F800FF000000007800FF0 00000007801FE000000007801FE000000003803FE000000003803FC000000003807FC000 000001807FC000000001807FC000000001807F800000000180FF800000000000FF800000 000000FF800000000000FF800000000000FF800000000000FF800000000000FF80000000 0000FF800000000000FF800000000000FF800000000000FF800000000000FF8000000000 00FF8000000000007F8000000000007FC000000001807FC000000001807FC00000000180 3FC000000001803FE000000001801FE000000003801FE000000003000FF000000003000F F0000000070007F8000000070007F8000000060003FC0000000E0001FE0000001C0000FE 0000001800007F0000003800003F8000007000001FE00000E000000FF00003C0000003FC 000F80000001FF803F000000007FFFFC000000000FFFF00000000001FF800000313D7BBA 3C>67 D69 D<000000FF8000C000000FFFF001C000003FFFFC01C0 0000FF803F03C00003FC000787C0000FF00003CFC0001FE00000EFC0003FC000007FC000 7F8000003FC000FF0000001FC001FE0000001FC003FC0000000FC007F800000007C007F8 00000007C00FF000000003C00FF000000003C01FE000000003C01FE000000001C03FE000 000001C03FC000000001C07FC000000000C07FC000000000C07FC000000000C07FC00000 0000C0FF800000000000FF800000000000FF800000000000FF800000000000FF80000000 0000FF800000000000FF800000000000FF800000000000FF800000000000FF8000000000 00FF800000000000FF800000FFFFFFFF800000FFFFFF7FC00000FFFFFF7FC00000007FE0 7FC00000003FC07FC00000003FC03FC00000003FC03FE00000003FC01FE00000003FC01F E00000003FC00FF00000003FC00FF00000003FC007F80000003FC007F80000003FC003FC 0000003FC001FE0000003FC000FF0000007FC0007F8000007FC0003FC00000FFC0001FE0 0000EFC0000FF80003C7C00003FE000783C00000FFC03F01C000003FFFFC00C000000FFF F00000000000FF800000383D7CBA41>71 D 73 D76 DII<000003FF0000000000 1FFFE000000000FE01FC00000001F8007E00000007E0001F8000000FC0000FC000003F80 0007F000007F000003F80000FE000001FC0001FC000000FE0001F80000007E0003F80000 007F0007F00000003F8007F00000003F800FE00000001FC00FE00000001FC01FE0000000 1FE01FC00000000FE03FC00000000FF03FC00000000FF03FC00000000FF07FC00000000F F87F8000000007F87F8000000007F87F8000000007F8FF8000000007FCFF8000000007FC FF8000000007FCFF8000000007FCFF8000000007FCFF8000000007FCFF8000000007FCFF 8000000007FCFF8000000007FCFF8000000007FCFF8000000007FCFF8000000007FC7F80 00000007F87FC00000000FF87FC00000000FF87FC00000000FF83FC00000000FF03FC000 00000FF01FE00000001FE01FE00000001FE01FE00000001FE00FF00000003FC007F00000 003F8007F80000007F8003F80000007F0001FC000000FE0001FC000000FE0000FE000001 FC00007F000003F800003F800007F000001FC0000FE0000007E0001F80000003F8007F00 000000FE01FC000000001FFFE00000000003FF000000363D7BBA41>II82 D<000FF800C0003FFE01C000FFFF81C003F807E3C007E000F7C00FC0007FC01F80003FC0 3F00001FC03E00000FC07E000007C07E000007C07C000003C0FC000003C0FC000001C0FC 000001C0FC000001C0FE000000C0FE000000C0FE000000C0FF000000C0FF800000007FC0 0000007FE00000007FF80000003FFF8000001FFFF800001FFFFF80000FFFFFE00007FFFF F80003FFFFFE0000FFFFFF00003FFFFF800007FFFFC000007FFFC0000007FFE00000007F E00000003FF00000001FF00000000FF000000007F800000007F8C0000003F8C0000003F8 C0000001F8C0000001F8C0000001F8E0000001F8E0000001F8E0000001F0F0000001F0F0 000003F0F8000003E0FC000007E0FE000007C0FF00000FC0FF80001F80FBF0003F00F0FE 00FE00E03FFFF800E00FFFE000C001FF0000253D7CBA2E>I<3FFFFFFFFFFFE03FFFFFFF FFFFE03FFFFFFFFFFFE03FC003FF001FE03E0001FE0003E07C0001FE0001F0780001FE00 00F0700001FE000070700001FE000070700001FE000070600001FE000030600001FE0000 30600001FE000030600001FE000030E00001FE000038C00001FE000018C00001FE000018 C00001FE000018C00001FE000018000001FE000000000001FE000000000001FE00000000 0001FE000000000001FE000000000001FE000000000001FE000000000001FE0000000000 01FE000000000001FE000000000001FE000000000001FE000000000001FE000000000001 FE000000000001FE000000000001FE000000000001FE000000000001FE000000000001FE 000000000001FE000000000001FE000000000001FE000000000001FE000000000001FE00 0000000001FE000000000001FE000000000001FE000000000001FE000000000001FE0000 00000001FE000000000001FE000000000001FE000000000001FE000000000001FE000000 000007FF800000001FFFFFFFE000001FFFFFFFE000001FFFFFFFE00035397DB83C>II87 D91 D93 D<001FE0000000FFFC000003E03F000007000F80000F8007E0001FC003F0001FE003F000 1FE001F8001FE001F8001FE000FC000FC000FC00078000FC00000000FC00000000FC0000 0000FC00000000FC0000007FFC000007FFFC00003FE0FC0000FE00FC0003F800FC000FF0 00FC001FC000FC003FC000FC007F8000FC007F0000FC007F0000FC0CFE0000FC0CFE0000 FC0CFE0000FC0CFE0001FC0CFE0001FC0CFF0003FC0C7F00077C0C7F80063E183FC01E3E 180FE0781FF003FFF00FE0007F8007C026277DA52A>97 D<03F0000000FFF0000000FFF0 000000FFF00000000FF000000003F000000003F000000003F000000003F000000003F000 000003F000000003F000000003F000000003F000000003F000000003F000000003F00000 0003F000000003F000000003F000000003F000000003F01FE00003F07FF80003F1E03E00 03F3801F8003F7000FC003FE0007E003FC0003F003F80001F803F00001F803F00000FC03 F00000FC03F00000FE03F00000FE03F000007E03F000007F03F000007F03F000007F03F0 00007F03F000007F03F000007F03F000007F03F000007F03F000007F03F000007F03F000 007E03F00000FE03F00000FE03F00000FC03F00001FC03F80001F803F80003F003FC0003 F003EE0007E003C6000FC003C7801F000381E07E000300FFF80000001FC000283B7EB92E >I<0003FC00001FFF80007E03E001F8007003F000F807E001FC0FC003FC0FC003FC1F80 03FC3F8003FC3F0001F87F0000F07F0000007F0000007E000000FE000000FE000000FE00 0000FE000000FE000000FE000000FE000000FE000000FE000000FE0000007E0000007F00 00007F0000003F0000063F8000061F80000E1FC0000C0FC0001C07E0003803F0007001F8 00E0007C07C0001FFF000007F8001F277DA525>I<0000000FC0000003FFC0000003FFC0 000003FFC00000003FC00000000FC00000000FC00000000FC00000000FC00000000FC000 00000FC00000000FC00000000FC00000000FC00000000FC00000000FC00000000FC00000 000FC00000000FC00000000FC00000000FC00003F80FC0001FFF0FC0007E078FC000F801 EFC003F0007FC007E0003FC00FC0001FC00FC0001FC01F80000FC03F80000FC03F00000F C07F00000FC07F00000FC07E00000FC0FE00000FC0FE00000FC0FE00000FC0FE00000FC0 FE00000FC0FE00000FC0FE00000FC0FE00000FC0FE00000FC0FE00000FC07E00000FC07F 00000FC07F00000FC03F00000FC03F00000FC01F80001FC01F80001FC00FC0003FC007E0 007FC003F000EFF001F801CFFF007C078FFF001FFE0FFF0007F80FC0283B7DB92E>I<00 07F800001FFF00007C0FC001F803E003F001F007E001F80FC000F81F80007C1F80007C3F 00007E3F00003E7F00003E7F00003F7E00003FFE00003FFE00003FFE00003FFFFFFFFFFF FFFFFFFE000000FE000000FE000000FE000000FE0000007E0000007E0000007F0000007F 0000003F0000033F8000031F8000070FC0000607C0000E07E0001C01F0003800F8007000 7E03E0001FFF800003FC0020277EA525>I<00007E000003FF80000FC1E0001F87E0003F 0FF0007E0FF0007E0FF000FC0FF000FC0FF001F803C001F8000001F8000001F8000001F8 000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8 0000FFFFFC00FFFFFC00FFFFFC0001F8000001F8000001F8000001F8000001F8000001F8 000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8 000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8 000001F8000001F8000001F8000001F8000001F8000003FC00007FFFF8007FFFF8007FFF F8001C3B7FBA19>I<00000003F0000FF00FF8003FFC3C3C00F81F707C01F00FE07C03E0 07C07C07C003E0100FC003F0000FC003F0001F8001F8001F8001F8001F8001F8001F8001 F8001F8001F8001F8001F8001F8001F8001F8001F8000FC003F0000FC003F00007C003E0 0003E007C00003F00F800003F81F0000073FFC0000060FF000000E000000000E00000000 0E000000000E000000000F000000000F000000000FC000000007FFFFC00007FFFFF80003 FFFFFE0001FFFFFF8003FFFFFFC00F80007FE01F00000FF03E000003F07C000001F07C00 0001F8F8000000F8F8000000F8F8000000F8F8000000F8F8000000F8FC000001F87C0000 01F03E000003E03F000007E00F80000F8007E0003F0001FC01FC00007FFFF0000007FF00 0026387EA52A>I<03F000000000FFF000000000FFF000000000FFF0000000000FF00000 000003F00000000003F00000000003F00000000003F00000000003F00000000003F00000 000003F00000000003F00000000003F00000000003F00000000003F00000000003F00000 000003F00000000003F00000000003F00000000003F00000000003F00FF0000003F03FFC 000003F0F03F000003F1C01F800003F3800FC00003F7000FC00003FE000FC00003FC0007 E00003FC0007E00003F80007E00003F80007E00003F80007E00003F00007E00003F00007 E00003F00007E00003F00007E00003F00007E00003F00007E00003F00007E00003F00007 E00003F00007E00003F00007E00003F00007E00003F00007E00003F00007E00003F00007 E00003F00007E00003F00007E00003F00007E00003F00007E00003F00007E00003F00007 E00003F00007E00007F8000FF000FFFFC1FFFF80FFFFC1FFFF80FFFFC1FFFF80293A7EB9 2E>I<0380000FE0001FF0001FF0001FF0001FF0001FF0000FE000038000000000000000 00000000000000000000000000000000000000000000000003F000FFF000FFF000FFF000 07F00003F00003F00003F00003F00003F00003F00003F00003F00003F00003F00003F000 03F00003F00003F00003F00003F00003F00003F00003F00003F00003F00003F00003F000 03F00003F00003F00003F00003F00007F800FFFFC0FFFFC0FFFFC012387EB717>I<03F0 000000FFF0000000FFF0000000FFF00000000FF000000003F000000003F000000003F000 000003F000000003F000000003F000000003F000000003F000000003F000000003F00000 0003F000000003F000000003F000000003F000000003F000000003F000000003F0000000 03F001FFFC03F001FFFC03F001FFFC03F0007FC003F0007F0003F0007C0003F000700003 F000E00003F001C00003F003800003F007000003F01E000003F038000003F078000003F0 FC000003F1FC000003F3FE000003F73F000003FE3F800003F81F800003F00FC00003F00F E00003F007E00003F003F00003F001F80003F001FC0003F000FC0003F0007E0003F0007F 0003F0003F0003F0003F8003F0001FC007F8003FF0FFFFC0FFFFFFFFC0FFFFFFFFC0FFFF 283A7EB92C>107 D<03F000FFF000FFF000FFF0000FF00003F00003F00003F00003F000 03F00003F00003F00003F00003F00003F00003F00003F00003F00003F00003F00003F000 03F00003F00003F00003F00003F00003F00003F00003F00003F00003F00003F00003F000 03F00003F00003F00003F00003F00003F00003F00003F00003F00003F00003F00003F000 03F00003F00003F00003F00003F00003F00003F00003F00003F00007F800FFFFC0FFFFC0 FFFFC0123A7EB917>I<03F00FF0001FE000FFF03FFC007FF800FFF0F03F01E07E00FFF1 C01F83803F000FF3800FC7001F8003F7000FCE001F8003FE000FDC001F8003FC0007F800 0FC003FC0007F8000FC003F80007F0000FC003F80007F0000FC003F80007F0000FC003F0 0007E0000FC003F00007E0000FC003F00007E0000FC003F00007E0000FC003F00007E000 0FC003F00007E0000FC003F00007E0000FC003F00007E0000FC003F00007E0000FC003F0 0007E0000FC003F00007E0000FC003F00007E0000FC003F00007E0000FC003F00007E000 0FC003F00007E0000FC003F00007E0000FC003F00007E0000FC003F00007E0000FC003F0 0007E0000FC003F00007E0000FC003F00007E0000FC007F8000FF0001FE0FFFFC1FFFF83 FFFFFFFFC1FFFF83FFFFFFFFC1FFFF83FFFF40257EA445>I<03F00FF00000FFF03FFC00 00FFF0F03F0000FFF1C01F80000FF3800FC00003F7000FC00003FE000FC00003FC0007E0 0003FC0007E00003F80007E00003F80007E00003F80007E00003F00007E00003F00007E0 0003F00007E00003F00007E00003F00007E00003F00007E00003F00007E00003F00007E0 0003F00007E00003F00007E00003F00007E00003F00007E00003F00007E00003F00007E0 0003F00007E00003F00007E00003F00007E00003F00007E00003F00007E00003F00007E0 0003F00007E00007F8000FF000FFFFC1FFFF80FFFFC1FFFF80FFFFC1FFFF8029257EA42E >I<0003FE0000000FFF8000003E03E00000F800F80001F0007C0003E0003E0007C0001F 000F80000F801F80000FC01F000007C03F000007E03F000007E07E000003F07E000003F0 7E000003F07E000003F0FE000003F8FE000003F8FE000003F8FE000003F8FE000003F8FE 000003F8FE000003F8FE000003F8FE000003F87E000003F07E000003F07F000007F03F00 0007E03F000007E01F80000FC00F80000F800FC0001F8007E0003F0003F0007E0000F800 F800007E03F000001FFFC0000003FE000025277EA52A>I<03F01FE000FFF07FF800FFF1 E07E00FFF3801F8007F7000FC003FE0007E003FC0003F003F80003F803F00001F803F000 01FC03F00000FC03F00000FE03F00000FE03F00000FE03F000007F03F000007F03F00000 7F03F000007F03F000007F03F000007F03F000007F03F000007F03F000007F03F000007F 03F00000FE03F00000FE03F00000FE03F00001FC03F00001FC03F80003F803F80003F003 FC0007F003FE000FE003F6000FC003F7803F0003F1E07E0003F0FFF80003F01FC00003F0 00000003F000000003F000000003F000000003F000000003F000000003F000000003F000 000003F000000003F000000003F000000007F8000000FFFFC00000FFFFC00000FFFFC000 0028357EA42E>I<07E01F00FFE07FC0FFE1E3E0FFE387F00FE707F003E607F003EE07F0 03EC03E003FC008003F8000003F8000003F8000003F8000003F0000003F0000003F00000 03F0000003F0000003F0000003F0000003F0000003F0000003F0000003F0000003F00000 03F0000003F0000003F0000003F0000003F0000003F0000003F0000003F0000007F80000 FFFFF000FFFFF000FFFFF0001C257EA421>114 D<00FF030003FFE7000F80FF001E003F 003C001F0078000F0070000700F0000700F0000700F0000300F8000300F8000300FC0003 00FF0000007FE000007FFF00003FFFE0001FFFF8000FFFFC0003FFFE0000FFFF000007FF 8000007F8000001F80C0000FC0C00007C0C00007C0E00003C0E00003C0E00003C0F00003 C0F0000380F8000780FC000780FC000F00FF001E00F3C07C00E1FFF000C03F80001A277D A521>I<0018000000180000001800000018000000180000003800000038000000380000 00780000007800000078000000F8000001F8000003F8000007F800001FFFFF00FFFFFF00 FFFFFF0001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F80000 01F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F80000 01F8000001F800C001F800C001F800C001F800C001F800C001F800C001F800C001F800C0 01F800C000FC01C000FC0180007C0380007E0300003F0700000FFE000001F8001A347FB2 20>I<03F00007E000FFF001FFE000FFF001FFE000FFF001FFE0000FF0001FE00003F000 07E00003F00007E00003F00007E00003F00007E00003F00007E00003F00007E00003F000 07E00003F00007E00003F00007E00003F00007E00003F00007E00003F00007E00003F000 07E00003F00007E00003F00007E00003F00007E00003F00007E00003F00007E00003F000 07E00003F00007E00003F00007E00003F00007E00003F0000FE00003F0000FE00003F000 0FE00003F0001FE00001F0001FE00001F8003FE00000F80077F80000FC00E7FF80003F03 C7FF80001FFF87FF800003FC07E00029267EA42E>III121 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fn cmr7 7 3 /Fn 3 52 df<00380000780001F8001FF800FEF800E0F80000F80000F80000F80000F800 00F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F800 00F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F800 00F80001FC00FFFFF8FFFFF815267BA521>49 D<00FF000003FFE0000E03F0001800F800 30007C0060007E0078003F00FC003F00FE001F80FE001F80FE001F80FE001F807C001F80 00001F8000001F0000003F0000003E0000007E0000007C000000F8000001F0000003E000 0003C00000078000000E0000001C0000003800000070018000E001800180018003000300 060003000C0003001FFFFF003FFFFF007FFFFE00FFFFFE00FFFFFE0019267DA521>I<00 FF000003FFE0000F01F8001C007C0030007E003C003E007E003F007E003F007E003F007E 003F003C003F0000003E0000007E0000007C000000F8000001F0000007E00001FF800001 FF00000001E0000000F00000007C0000003E0000003F0000001F0000001F8000001F8038 001F807C001F80FE001F80FE001F80FE001F00FC003F0078003E0070007C003800F8001F 01F00007FFC00000FF000019277DA521>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fo cmmi10 10 22 /Fo 22 120 df<00003FC000000000FFF800000007E07C0000000F801F0000003F001F80 0C007E000F800C00FC0007C01C01F80007E01803F00007E01807E00003E0380FE00003F0 300FC00003F0301FC00003F0703F800003F0603F800003F0E07F800003F0C07F000003F1 C07F000003F1807F000003F380FF000003F300FE000003F700FE000003FE00FE000003FC 00FE000003FC00FC000003F800FC000003F000FC000003F000FC000003F000FC000003F0 007E000007F0007E00000FF0003E00001DF8183F000079F8181F0000E1F8380F8007C0F8 3007E03F007CF001FFF8003FC0003FC0000F802E267DA435>11 D<000003000000003FF8 0000007FFF800001E3FFC0000180FFC00003803FC00003001F8000030007000003000000 000380000000038000000003C000000003C000000003E000000003F000000001F0000000 01F800000001FC00000000FC00000000FE000000007F000000007F800000003F80000000 3FC0000001FFE0000007FFE000000F8FF000003E0FF000007C07F80000F807F80001F003 F80003E003FC0007E003FC000FC001FC000F8001FC001F8001FC003F0001FC003F0000FC 007F0000FC007E0000FC007E0000FC00FE0000FC00FE0000F800FC0001F800FC0001F800 FC0001F800FC0001F000FC0001F000F80003F000F80003E000FC0007E000FC0007C0007C 0007C0007C000F80003E000F00003E001F00001F003E00000F807C000007C0F0000001FF E00000003F000000223D7DBB25>14 D<003FFFFFFE00FFFFFFFF01FFFFFFFF03FFFFFFFF 07FFFFFFFE0F801C00001E001C00003C001C000038003800007000380000E000380000C0 00780000000078000000007000000000F000000000F000000000F000000000F000000001 E000000001E000000001E000000003E000000003E000000003E000000007C000000007C0 00000007C00000000FC00000000FC00000000F800000001F800000001F800000001F8000 00003F800000003F800000003F000000001E00000028257EA324>28 D<1C007F00FF80FF80FF80FF80FF807F001C000909798817>58 D<1C007F00FF80FF80FF C0FFC0FFC07FC01CC000C000C000C000C001C00180018003800300070006000E001C0038 00700060000A19798817>I<0000000C0000001E0000003E0000003E0000003C0000007C 0000007C00000078000000F8000000F8000000F0000001F0000001F0000001E0000003E0 000003E0000003C0000007C0000007C00000078000000F8000000F8000000F0000001F00 00001F0000001E0000003E0000003E0000003C0000007C0000007C00000078000000F800 0000F8000000F0000001F0000001F0000001E0000003E0000003E0000007C0000007C000 00078000000F8000000F8000000F0000001F0000001F0000001E0000003E0000003E0000 003C0000007C0000007C00000078000000F8000000F8000000F0000001F0000001F00000 01E0000003E0000003E0000003C0000007C0000007C00000078000000F8000000F800000 0F0000001F0000001F0000001E0000003E0000003E0000003C0000007C0000007C000000 78000000F8000000F8000000F0000000600000001F537BBD2A>61 D<60000000000000FC000000000000FF0000000000007FC000000000001FF00000000000 07FC000000000001FF0000000000007FC000000000001FF0000000000007FC0000000000 01FF0000000000007FC000000000001FF0000000000007FC000000000001FF0000000000 007FC000000000001FF0000000000007FC000000000001FF0000000000007FC000000000 001FF0000000000007FC000000000001FF0000000000007F8000000000001FC000000000 001FC000000000007F800000000001FF000000000007FC00000000001FF000000000007F C00000000001FF000000000007FC00000000001FF000000000007FC00000000001FF0000 00000007FC00000000001FF000000000007FC00000000001FF000000000007FC00000000 001FF000000000007FC00000000001FF000000000007FC00000000003FF000000000007F C00000000000FF000000000000FC00000000000070000000000000323279AD41>I<0003 FFFFFFFF00000007FFFFFFFFE0000007FFFFFFFFF800000007F80007FE00000007F00000 FF00000007F000003F8000000FF000001FC000000FF000000FC000000FE000000FE00000 0FE0000007F000001FE0000003F000001FE0000003F000001FC0000003F800001FC00000 01F800003FC0000001F800003FC0000001FC00003F80000001FC00003F80000001FC0000 7F80000001FC00007F80000001FC00007F00000001FC00007F00000001FC0000FF000000 01FC0000FF00000003FC0000FE00000003FC0000FE00000003FC0001FE00000003FC0001 FE00000003F80001FC00000007F80001FC00000007F80003FC00000007F80003FC000000 07F00003F80000000FF00003F80000000FF00007F80000000FE00007F80000001FE00007 F00000001FC00007F00000001FC0000FF00000003F80000FF00000003F80000FE0000000 7F00000FE00000007E00001FE0000000FE00001FE0000001FC00001FC0000001F800001F C0000003F000003FC0000007E000003FC000000FC000003F8000001F8000003F8000007F 0000007F800000FE0000007F800003FC0000007F00000FF0000000FF00007FC00000FFFF FFFFFF000000FFFFFFFFFC000000FFFFFFFFC00000003E397DB845>68 D<0003FFFFFFFFFFE00007FFFFFFFFFFE00007FFFFFFFFFFE0000007F800003FE0000007 F000000FE0000007F0000003C000000FF0000003C000000FF0000001C000000FE0000001 C000000FE0000001C000001FE0000001C000001FE0000001C000001FC0000001C000001F C00000018000003FC00000018000003FC00000018000003F800000018000003F80006001 8000007F8000E0018000007F8000E0000000007F0000C0000000007F0000C000000000FF 0001C000000000FF0001C000000000FE00038000000000FE00078000000001FE001F8000 000001FFFFFF8000000001FFFFFF0000000001FFFFFF0000000003FC001F0000000003FC 000F0000000003F8000E0000000003F8000E0000000007F8000E0000000007F8000E0000 000007F0000C0000000007F0000C000000000FF0001C000000000FF0001C000000000FE0 0000000000000FE00000000000001FE00000000000001FE00000000000001FC000000000 00001FC00000000000003FC00000000000003FC00000000000003F800000000000003F80 0000000000007F800000000000007F800000000000007F00000000000000FF8000000000 00FFFFFFC000000000FFFFFFC000000000FFFFFFC0000000003B397DB835>70 D<0003FFFFF80007FFFC0007FFFFF80007FFFC0007FFFFF80007FFFC000007F8000000FF 80000007F0000000FC00000007F0000000F00000000FF0000001E00000000FF000000380 0000000FE0000007000000000FE000000E000000001FE0000038000000001FE000007000 0000001FC00000E0000000001FC0000380000000003FC0000700000000003FC0000E0000 0000003F80003C00000000003F80007000000000007F8000E000000000007F8001C00000 0000007F00070000000000007F000E000000000000FF001C000000000000FF007E000000 000000FE00FE000000000000FE01FF000000000001FE03FF000000000001FE0E7F800000 000001FC1C7F800000000001FC383F800000000003FCE03FC00000000003FDC03FC00000 000003FB801FE00000000003FF001FE00000000007FC000FF00000000007F8000FF00000 000007F00007F00000000007F00007F8000000000FF00007F8000000000FF00003FC0000 00000FE00003FC000000000FE00001FC000000001FE00001FE000000001FE00001FE0000 00001FC00000FF000000001FC00000FF000000003FC000007F800000003FC000007F8000 00003F8000003F800000003F8000003FC00000007F8000003FC00000007F8000001FE000 00007F0000003FE0000000FF8000003FF00000FFFFFF0007FFFFC000FFFFFF0007FFFFC0 00FFFFFF0007FFFF800046397DB847>75 D<00000001FF00000000001FFFF000000000FE 01FC00000003F0007E00000007C0001F8000001F80000FC000003E000007E00000FC0000 03F00001F8000003F00003F0000001F80007E0000001F8000FC0000000FC001F80000000 FC003F00000000FE007F000000007E00FE000000007E00FC000000007F01FC000000007F 03F8000000007F03F8000000007F07F0000000007F07F0000000007F0FF0000000007F0F E0000000007F1FE000000000FF1FE000000000FF3FC000000000FF3FC000000000FF3FC0 00000000FF7F8000000001FE7F8000000001FE7F8000000001FE7F8000000001FEFF8000 000003FCFF0000000003FCFF0000000003FCFF0000000007F8FF0000000007F8FF000000 000FF0FF000000000FF0FF000000000FE0FF000000001FE0FF000000001FC0FF00000000 3F807F000000007F807F000000007F007F00000000FE007F00000001FC003F80000001F8 003F80000003F8001F80000007F0001FC000000FE0000FC000001F800007E000003F0000 07F000007E000003F00001F8000001FC0003F00000007E000FC00000003F807F00000000 07FFF80000000000FF80000000383D7CBA3F>79 D<0003FFFFFFFF00000007FFFFFFFFE0 000007FFFFFFFFF800000007F80007FC00000007F00000FE00000007F000007F0000000F F000003F8000000FF000001FC000000FE000001FC000000FE000001FC000001FE000001F E000001FE000001FE000001FC000001FE000001FC000001FE000003FC000001FE000003F C000003FC000003F8000003FC000003F8000003FC000007F8000007F8000007F8000007F 8000007F0000007F0000007F000000FE000000FF000001FC000000FF000001F8000000FE 000007F0000000FE00000FE0000001FE00003FC0000001FE0001FF00000001FFFFFFFC00 000001FFFFFFE000000003FC00000000000003FC00000000000003F800000000000003F8 00000000000007F800000000000007F800000000000007F000000000000007F000000000 00000FF00000000000000FF00000000000000FE00000000000000FE00000000000001FE0 0000000000001FE00000000000001FC00000000000001FC00000000000003FC000000000 00003FC00000000000003F800000000000003F800000000000007F800000000000007F80 0000000000007F00000000000000FF800000000000FFFFFF0000000000FFFFFF00000000 00FFFFFF00000000003B397DB835>I<0003FFFFFFF800000007FFFFFFFF80000007FFFF FFFFE000000007F8001FF800000007F00003FC00000007F00000FE0000000FF000007F00 00000FF000007F0000000FE000003F8000000FE000003F8000001FE000003FC000001FE0 00003FC000001FC000003FC000001FC000003FC000003FC000003FC000003FC000007F80 00003F8000007F8000003F8000007F8000007F800000FF0000007F800000FE0000007F00 0001FC0000007F000003F8000000FF000007F0000000FF00000FE0000000FE00001F8000 0000FE00007F00000001FE0007F800000001FFFFFFE000000001FFFFFF0000000001FC00 0FC000000003FC0003F000000003FC0001F800000003F80000FC00000003F80000FE0000 0007F80000FE00000007F800007E00000007F000007E00000007F000007F0000000FF000 00FF0000000FF00000FE0000000FE00000FE0000000FE00000FE0000001FE00001FE0000 001FE00001FE0000001FC00001FE0000001FC00001FE0000003FC00001FE0000003FC000 03FE0000003F800003FC0060003F800003FC0060007F800003FC00E0007F800003FC00C0 007F000003FC01C000FF800001FC0180FFFFFF0001FC0380FFFFFF0000FE0700FFFFFF00 007E0E0000000000001FFC00000000000007F0003B3B7DB83F>82 D<03FFFFFFFFFFFE03FFFFFFFFFFFE07FFFFFFFFFFFE07F8003FC001FE07C0003F80007E 0F80003F80003C0F00007F80001C1E00007F80001C1C00007F00001C1C00007F00001C38 0000FF00001C380000FF00001C300000FE00001C700000FE000018600001FE000018E000 01FE000018C00001FC000018C00001FC000018C00003FC000018000003FC000000000003 F8000000000003F8000000000007F8000000000007F8000000000007F0000000000007F0 00000000000FF000000000000FF000000000000FE000000000000FE000000000001FE000 000000001FE000000000001FC000000000001FC000000000003FC000000000003FC00000 0000003F8000000000003F8000000000007F8000000000007F8000000000007F00000000 00007F000000000000FF000000000000FF000000000000FE000000000000FE0000000000 01FE000000000001FE000000000001FC000000000001FC000000000003FC000000000003 FC000000000003F800000000000FFC000000003FFFFFFF0000007FFFFFFF0000007FFFFF FF00000037397EB831>84 D<000000003F0000001FFF0000001FFF0000001FFF00000000 7F000000007E000000007E00000000FE00000000FE00000000FC00000000FC00000001FC 00000001FC00000001F800000001F800000003F800000003F800000003F000000003F000 000007F000000007F000007E07E00003FF87E0000FC1CFE0001F00EFE0007E007FC000FC 003FC001F8003FC003F0001FC007F0001F8007E0001F800FE0003F801FC0003F801FC000 3F003F80003F003F80007F007F80007F007F00007E007F00007E007F0000FE00FF0000FE 00FE0000FC00FE0000FC00FE0001FC00FE0001FC00FC0001F80CFC0001F80CFC0003F80C FC0003F81CFC0003F018FC0007F0187C0007F0387E000FF0303E001FF0303E007BF0701F 00E1F0E00F83C0F9C003FF007F8000FC001F00283B7DB92B>100 D<0000E00003F80003F80007F80007F80007F80007F00001C00000000000000000000000 0000000000000000000000000000000000000000000000F80003FE00070F000E0F801C0F 80180F80380F80300F80701F80601F80603F80E03F00C03F00C07F00007E00007E0000FE 0000FC0001FC0001FC0001F80003F80003F00003F00007F01807E01807E0380FE0300FC0 300FC0700F80600F80E00F80C00F81C00F838007870003FE0000F80015397EB71D>105 D<03E0007F0000FE000007F801FFE003FFC0000E3C0781F00F03E0001C3E1E00F83C01F0 00383F3800FC7001F800303F7000FCE001F800303FE0007DC000F800703FC0007F8000F8 00603F80007F0000F800603F80007F0000F800E03F0000FE0001F800C07F0000FE0001F8 00C07E0000FC0001F800C07E0000FC0001F800007E0001FC0003F80000FE0001FC0003F0 0000FC0001F80003F00000FC0001F80003F00000FC0003F80007F00001FC0003F80007E0 0001F80003F00007E00001F80003F0000FE00001F80007F0000FC00003F80007F0000FC0 0003F00007E0001FC06003F00007E0001F806003F0000FE0003F80E007F0000FE0003F00 C007E0000FC0003F00C007E0000FC0003F01C007E0001FC0003E01800FE0001FC0003E03 800FC0001F80003E03000FC0001F80003E07000FC0003F80003E0E001FC0003F80001E1C 001F80003F00000FF8000700000E000003E00043267EA449>109 D<03E0007F000007F801FFE0000E3C0781F0001C3E1E00F800383F3800FC00303F7000FC 00303FE0007C00703FC0007C00603F80007C00603F80007C00E03F0000FC00C07F0000FC 00C07E0000FC00C07E0000FC00007E0001FC0000FE0001F80000FC0001F80000FC0001F8 0000FC0003F80001FC0003F00001F80003F00001F80007F00001F80007E00003F80007E0 0003F0000FE03003F0000FC03003F0001FC07007F0001F806007E0001F806007E0001F80 E007E0001F00C00FE0001F01C00FC0001F01800FC0001F03800FC0001F07001FC0000F0E 001F800007FC0007000001F0002C267EA432>I<0000FF000003FFC0000F80F0003E0038 0078001C0078003C00F000FC01F001FC01E001FC01E001FC01E001FC03F000F003F80000 03FC000001FFE00001FFFC0001FFFF0000FFFF80007FFFC0001FFFE00003FFE000003FF0 000007F0000003F01E0001F07F0001F07F0001F0FF0001E0FF0001E0FF0001E0FE0003C0 F80003C0E000078070000F0038003E001E00F80007FFE00001FF00001E267CA427>115 D<0001C0000003E0000007E0000007E0000007E0000007E000000FE000000FC000000FC0 00000FC000001FC000001F8000001F8000001F8000003F8000003F00007FFFFF807FFFFF 80FFFFFF80007E0000007E0000007E000000FE000000FC000000FC000000FC000001FC00 0001F8000001F8000001F8000003F8000003F0000003F0000003F0000007F0000007E000 0007E0000007E000000FE000000FC006000FC006000FC00E001FC00C001F801C001F8018 001F8038001F8070001F8060001F80E0000F81C0000787800003FE000000F8000019357E B31E>I<00F80003C003FE0007E0070F000FE00E0F800FF01C0F800FF0180F800FF0380F 8007F0300F8003F0701F8001F0601F8001F0601F8000F0E03F8000E0C03F0000E0C07F00 00E0007E0000E0007E0000C000FE0000C000FC0000C000FC0001C001FC00018001F80001 8001F800038001F800030003F800030003F000070003F000060003F0000E0003F0000C00 03F0001C0003F000180003F000380003F000700001F000E00001F801C00000FC03800000 7E0F0000001FFE00000007F0000024267EA428>118 D<00F800000000F003FE0000E001 F8070F0001F003F80E0F8003F003FC1C0F8003F003FC180F8003F003FC380F8007F001FC 300F8007E000FC701F8007E0007C601F8007E0007C601F800FE0003CE03F800FE00038C0 3F000FC00038C07F000FC00038007E001FC00038007E001FC0003000FE001F80003000FC 001F80003000FC003F80007001FC003F80006001F8003F00006001F8003F00006001F800 3F0000E003F8007F0000C003F0007E0000C003F0007E0001C003F0007E00018003F0007E 00038003F0007E00030003F0007E00070003F000FE00060003F000FE000E0001F001FE00 1C0001F801BF00380000FC039F807000007E0F0FC0E000001FFC03FFC0000003F0007F00 0036267EA43B>I E %EndDVIPSBitmapFont /Fp 133[32 37 37 55 37 42 23 32 32 42 42 42 42 60 23 37 23 23 42 42 23 37 42 37 42 42 11[60 46 42 51 1[51 2[69 46 8[55 20[21 28 21 2[28 28 28 35[42 3[{ TeXBase1Encoding ReEncodeFont}41 83.022 /Times-Italic rf /Fq 134[50 50 72 50 55 33 39 44 1[55 50 55 83 28 55 1[28 55 50 33 44 55 44 55 50 9[100 1[72 66 55 72 78 61 78 1[94 66 2[39 3[66 72 72 66 72 9[50 50 50 50 50 50 50 1[28 25 33 45[{TeXBase1Encoding ReEncodeFont}49 99.6264 /Times-Bold rf /Fr 107[37 37 24[37 42 42 60 42 42 23 32 28 42 42 42 42 65 23 42 23 23 42 42 28 37 42 37 42 37 3[28 1[28 2[60 78 1[60 51 46 55 60 46 60 60 74 51 60 1[28 60 60 46 51 60 55 55 60 76 2[47 1[23 23 42 42 42 42 42 42 42 42 42 42 23 21 28 21 47 1[28 28 28 1[69 1[42 1[28 29[46 46 2[{TeXBase1Encoding ReEncodeFont}79 83.022 /Times-Roman rf %DVIPSBitmapFont: Fs cmsy10 10 13 /Fs 13 107 df<7FFFFFFFFFFF80FFFFFFFFFFFFC0FFFFFFFFFFFFC07FFFFFFFFFFF8032 04799641>0 D<6000000006F80000000FFC0000001F7E0000003F3F0000007E1F800000 FC0FC00001F807E00003F003F00007E001F8000FC000FC001F80007E003F00003F007E00 001F80FC00000FC1F8000007E3F0000003F7E0000001FFC0000000FF800000007F000000 007F00000000FF80000001FFC0000003F7E0000007E3F000000FC1F800001F80FC00003F 007E00007E003F0000FC001F8001F8000FC003F00007E007E00003F00FC00001F81F8000 00FC3F0000007E7E0000003FFC0000001FF80000000F6000000006282874A841>2 D<0000003000000000000078000000000000780000000000007800000000000078000000 000000780000000000007800000000000078000000000000780000000000007800000000 000078000000000000780000000000007800000000000078000000000000780000000000 007800000000000078000000000000780000000000007800000000000078000000000000 78000000000000780000000000007800000000000078000000000000780000007FFFFFFF FFFFF8FFFFFFFFFFFFFCFFFFFFFFFFFFFC7FFFFFFFFFFFF8000000780000000000007800 000000000078000000000000780000000000007800000000000078000000000000780000 000000007800000000000078000000000000780000000000007800000000000078000000 000000780000000000007800000000000078000000000000780000000000007800000000 0000780000000000007800000000000078000000000000780000007FFFFFFFFFFFF8FFFF FFFFFFFFFCFFFFFFFFFFFFFC7FFFFFFFFFFFF836367BB641>6 D<000FE000007FFC0000 FFFE0003FFFF8007FFFFC00FFFFFE01FFFFFF03FFFFFF83FFFFFF87FFFFFFC7FFFFFFC7F FFFFFCFFFFFFFEFFFFFFFEFFFFFFFEFFFFFFFEFFFFFFFEFFFFFFFEFFFFFFFEFFFFFFFE7F FFFFFC7FFFFFFC7FFFFFFC3FFFFFF83FFFFFF81FFFFFF00FFFFFE007FFFFC003FFFF8000 FFFE00007FFC00000FE0001F207BA42A>15 D<00000000000180000000000007C0000000 00001FC000000000007F800000000001FF000000000007FC00000000001FF00000000000 7FC00000000001FF000000000007FC00000000001FF000000000007FC00000000001FF00 0000000007FC00000000001FF000000000007FC00000000001FF000000000007FC000000 00001FF000000000007FC00000000001FF000000000007FC00000000003FF00000000000 7FC00000000000FF000000000000FE0000000000007F8000000000003FE000000000000F F8000000000003FE000000000000FF8000000000003FE000000000000FF8000000000003 FE000000000000FF8000000000003FE000000000000FF8000000000003FE000000000000 FF8000000000003FE000000000000FF8000000000003FE000000000000FF800000000000 3FE000000000000FF8000000000003FE000000000000FF8000000000003FC00000000000 0FC000000000000380000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000007F FFFFFFFFFF80FFFFFFFFFFFFC0FFFFFFFFFFFFC07FFFFFFFFFFF80324479B441>20 D<60000000000000F8000000000000FE0000000000007F8000000000003FE00000000000 0FF8000000000003FE000000000000FF8000000000003FE000000000000FF80000000000 03FE000000000000FF8000000000003FE000000000000FF8000000000003FE0000000000 00FF8000000000003FE000000000000FF8000000000003FE000000000000FF8000000000 003FE000000000000FF8000000000003FE000000000000FF8000000000003FC000000000 001FC000000000007F800000000001FF000000000007FC00000000001FF000000000007F C00000000001FF000000000007FC00000000001FF000000000007FC00000000001FF0000 00000007FC00000000001FF000000000007FC00000000001FF000000000007FC00000000 001FF000000000007FC00000000001FF000000000007FC00000000001FF000000000007F C00000000000FF000000000000FC00000000000070000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000007FFFFFFFFFFF80FFFFFFFFFFFFC0FFFFFFFFFF FFC07FFFFFFFFFFF80324479B441>I<003F800000000800FFF00000001C03FFFC000000 1C07FFFE0000001C0FFFFF8000001C1FFFFFC000001C3FC07FF000003C3F000FF8000038 7C0003FE000078780001FF0000F87000007FC003F0F000003FF80FF0E000000FFFFFE0E0 000007FFFFC0E0000001FFFF80E0000000FFFF00E00000003FFC004000000007F0000000 000000000000000000000000003F800000000800FFF00000001C03FFFC0000001C07FFFE 0000001C0FFFFF8000001C1FFFFFC000001C3FC07FF000003C3F000FF80000387C0003FE 000078780001FF0000F87000007FC003F0F000003FF80FF0E000000FFFFFE0E0000007FF FFC0E0000001FFFF80E0000000FFFF00E00000003FFC004000000007F00036267BA741> 25 D<000078000000000000000078000000000000000078000000000000000078000000 0000000000F80000000000000000F00000000000000000F00000000000000001F0000000 0000000001E00000000000000003E00000000000000007C00000000000000007C0000000 000000000F80000000000000001F00000000000000003F00000000000000007E00000000 00000000FC0000000000000001F80000000000000003F0000000000000000FE000000000 0000003FFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF3FFFFFFFFFFF FFFFFE0FE00000000000000003F00000000000000001F80000000000000000FC00000000 000000007E00000000000000003F00000000000000001F00000000000000000F80000000 0000000007C00000000000000007C00000000000000003E00000000000000001E0000000 0000000001F00000000000000000F00000000000000000F00000000000000000F8000000 000000000078000000000000000078000000000000000078000000000000000078000000 000000482C7BAA53>32 D<00000007FFFFFFFE000000003FFFFFFFFF80000001FFFFFFFF FFC0000007FFFFFFFFFFC000000F807E0000FFC000003C00FE00003F0000007800FE0000 1E000000F000FC000018000001F000FC000000000003E000FC000000000007E001FC0000 00000007E001FC00000000000FC001F800000000000F8001F800000000000F0001F80000 000000180003F80000000000000003F00000000000000003F00000000000000003F00000 000000000007E00000000000000007E00000000000000007E0000000000000000FE00000 00000000000FC0000000000000000FC0000000000000000FC0000000000000001F800000 00000000001F80000000000000001FFFFFFC00000000003FFFFFF800000000003FFFFFF0 00000000007FFFFFC000000000007E00000000000000007E0000000000000000FC000000 0000000000FC0000000000000000F80000000000000001F80000000000000001F8000000 0000000003F00000000000000003F00000000000000003E00000000000000007E0000000 0000000007C0000000000000000FC0000000000000000F80000000000000001F80000000 000000001F00000000000000003F00000000000006003E0000000000003E007E00000000 00007E007C000000000000FF00FC000000000000FF80F8000000000000FFC1F000000000 0000FFF1E00000000000007FFFC00000000000003FFF000000000000001FFE0000000000 000007F000000000000000423C7EB83C>70 D<0000000001FC00000000000FFE00000000 007FFF0000000001FFFF0000000003FFFF800000000F03FF800000001E01FF800000003C 00FF800000007C00FF80000000F8007F80000001F0007F80000003F0007F00000003E000 7E00000007E0007C0000000FC000700000000FC000C00000001F8000000000001F800000 0000003F0000000000003F0000000000007F0000000000007E000000000000FE00000000 0000FE000000000000FC000000000001FC000000000001FC000000000001F80000000000 03F8000000000003F8000000000003F8000000000007F0000000000007F0000000000007 F0000000000007F000000000000FE000000000000FE000000000000FE000000000000FE0 00000000001FC000000000001FC000000000001FC000000000001F8000000000003F8000 000000003F0000000000003F0000000000007E0000000000007E000000002000FC000000 01E000FC00000003E001F80000000FC001F7F800001FC003FFFF80001F8003FFFFF0001F 0007FFFFFF003E000FFFFFFFF03C000F07FFFFFFF8001E007FFFFFE0003C000FFFFFC000 700000FFFE0000C000000FF00000333D7EBA39>76 D<000001F800000FF800003F800000 FC000001F8000003F0000007E0000007E000000FE000000FC000000FC000000FC000000F C000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000F C000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000F C000000FC000000FC000000FC000001FC000001F8000003F8000007F000000FE000003F8 00007FE00000FF0000007FE0000003F8000000FE0000007F0000003F8000001F8000001F C000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000F C000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000F C000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FE0000007 E0000007E0000003F0000001F8000000FC0000003F8000000FF8000001F81D537ABD2A> 102 DI<60F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0 F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0 F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F060045377BD17> 106 D E %EndDVIPSBitmapFont /Ft 134[44 2[44 50 28 39 39 2[50 50 1[28 2[28 50 50 1[44 1[44 50 50 12[55 5[66 83 55 1[44 1[72 5[61 61 7[50 1[50 50 1[50 3[50 1[25 1[25 44[{TeXBase1Encoding ReEncodeFont}31 99.6264 /Times-Italic rf /Fu 87[33 45[44 4[50 28 39 33 2[50 50 78 28 2[28 50 2[44 50 44 50 44 13[55 3[72 4[39 2[72 1[61 2[66 72 20[25 44[{TeXBase1Encoding ReEncodeFont}25 99.6264 /Times-Roman rf /Fv 134[60 60 1[60 66 40 47 53 1[66 60 66 100 33 66 1[33 66 60 40 53 66 53 1[60 9[120 2[80 66 86 93 73 93 1[113 80 2[47 1[93 73 80 86 86 1[86 6[40 1[60 60 60 60 60 60 60 60 3[40 45[{TeXBase1Encoding ReEncodeFont} 47 119.552 /Times-Bold rf end %%EndProlog %%BeginSetup %%Feature: *Resolution 600dpi TeXDict begin %%EndSetup %%Page: 1 1 1 0 bop 1143 255 a Fv(The)30 b(Eclipse)g(Operating)h(System:)560 405 y(Pr)n(o)o(viding)g(Quality)f(of)f(Ser)o(vice)i(via)f(Reser)o(v)o (ation)f(Domains)642 646 y Fu(John)24 b(Bruno,)h(Eran)g(Gabber)l(,)g (Banu)1961 623 y(\250)1941 646 y(Ozden)g(and)g(Abraham)g(Silberschatz) 1150 762 y Ft(Bell)g(Labor)o(atories,)d(Lucent)j(T)-9 b(ec)o(hnolo)o(gies)1558 878 y(600)24 b(Mountain)g(A)-5 b(ve)o(.)1476 994 y(Murr)o(ay)24 b(Hill,)g(NJ)i(07974)1091 1111 y Fs(f)p Fr(jbruno,)17 b(eran,)j(ozden,)f(a)n(vi)p Fs(g)p Fr(@research.bell-labs.com)0 1436 y Fq(Abstract)0 1599 y Fr(In)25 b(this)h(paper)m(,)f(we)h(introduce)e(a)i(ne)n(w)f (operating)e(system)j(ab-)0 1698 y(straction)36 b(called)f Fp(r)m(eservation)h(domains)p Fr(,)j(and)c(describe)h(its)0 1798 y(implementation)d(in)j(Eclipse,)j(an)d(e)o(xperimental)d (operating)0 1898 y(system)i(that)g(pro)o(vides)e(a)j(testbed)e(for)h (Quality)f(of)h(Service)0 1997 y(\(QoS\))20 b(support)e(for)i (applications.)125 2101 y(Reserv)n(ation)d(domains)g(enable)h(e)o (xplicit)g(control)f(o)o(v)o(er)g(the)0 2200 y(pro)o(visioning)i(of)j (system)g(resources)g(among)e(applications)h(in)0 2300 y(order)37 b(to)i(achie)n(v)o(e)e(desired)h(le)n(v)o(els)g(of)g (predictable)f(perfor)n(-)0 2399 y(mance.)d(In)23 b(general,)f(each)h (reserv)n(ation)f(domain)g(is)i(assigned)0 2499 y(a)c(certain)f (fraction)f(of)i(each)f(resource)f(\(e.g.,)h(25\045)g(CPU,)i(50\045)0 2599 y(disk)26 b(I/O,)g(etc.\).)42 b(Eclipse)26 b(implements)f(reserv)n (ation-domain)0 2698 y(scheduling)h(of)h(multiple)g(resources.)46 b(It)28 b(currently)e(supports)0 2798 y(CPU)h(and)f(disk)g(and)g (physical)f(memory)g(\(w)o(orking)f(set)j(size\))0 2898 y(scheduling.)125 3001 y(Eclipse)44 b(implements)g(a)i(ne)n(w)e (scheduling)f(algorithm,)0 3100 y(Mo)o(v)o(e-to-Rear)17 b(List)j(Scheduling)d(\(MTR-LS\),)i(that)g(pro)o(vides)0 3200 y(a)29 b Fp(cumulative)f(service)i(guar)o(antee)p Fr(,)f(in)g(addition)f(to)h(f)o(airness)0 3300 y(and)21 b(delay)f(bounds.)27 b(Cumulati)n(v)o(e)20 b(service)g(guarantee)g(is)i (nec-)0 3399 y(essary)d(for)g(ensuring)f(predictable)f(aggre)o(gate)g (throughput)f(for)0 3499 y(applications)g(that)h(require)f(multiple)h (resources.)23 b(Preliminary)0 3599 y(e)o(xperiments)i(indicate)i(that) g(MTR-LS)g(pro)o(vides)e(good)g(QoS)0 3698 y(in)33 b(o)o(v)o(erloaded)d (systems.)63 b(In)32 b(particular)m(,)i(MTR-LS)f(f)o(a)n(v)n(ors)0 3798 y Fp(less-gr)m(eedy)20 b Fr(processes.)125 3901 y(The)39 b(Eclipse)h(operating)e(system)i(is)h(based)e(the)h(Plan9)0 4001 y(from)18 b(Bell)j(Labs,)e(and)g(can)g(run)g(an)o(y)g(Plan9)g (application)f(with-)0 4100 y(out)33 b(modi\002cation.)65 b(Eclipse)33 b(emphasizes)h(the)f(use)h(of)g(per)n(-)0 4200 y(process)22 b(name)g(space,)h(and)g(it)g(can)g(schedule)e(an)o(y) h(I/O)h(de)n(vice)0 4300 y(or)29 b(user)h(le)n(v)o(el)f(\002le)h (system)g(without)f(an)o(y)f(change)h(to)g(de)n(vice)0 4399 y(dri)n(v)o(er)19 b(or)h(\002le)g(system)h(code.)0 4580 y Fv(1)119 b(Intr)n(oduction)0 4742 y Fr(Ne)n(w)20 b(multimedia)e(applications,)h(which)g(require)f(support)g(for)0 4842 y(real-time)k(processing,)g(are)h(pacing)f(the)h(demand)f(for)g (operat-)0 4941 y(ing)28 b(system)h(support)e(for)h(Quality)h(of)f (Service)g(\(QoS\))g(guar)n(-)0 5041 y(antees.)48 b(The)28 b(desire)g(to)g(support)f(multiple)g(real-time)g(appli-)0 5141 y(cations)f(on)g(a)g(single)g(platform)f(requires)g(that)h(the)g (operating)0 5240 y(system)34 b(ha)n(v)o(e)f(the)h(ability)g(to)g(pro)o (vision)d(system)k(resources)0 5340 y(among)15 b(applications)g(in)h(a) h(manner)d(that)j(achie)n(v)o(es)e(the)h(desired)2010 1436 y(le)n(v)o(els)24 b(of)f(predictable)g(performance.)33 b(Moreo)o(v)o(er)m(,)21 b(computer)2010 1536 y(netw)o(orks)c(are)h (starting)f(to)h(pro)o(vide)e(QoS)i(guarantees)e(with)i(re-)2010 1635 y(spect)23 b(to)g(pack)o(et)g(delay)f(and)h(connection)d (bandwidth.)32 b(These)2010 1735 y(QoS)g(guarantees)f(are)h(of)g (little)h(use)f(if)h(the)o(y)e(cannot)g(be)h(e)o(x-)2010 1835 y(tended)24 b(to)i(applications)e(e)o(x)o(ecuting)f(at)j(the)g (endpoints.)38 b(Cur)n(-)2010 1934 y(rent)e(general-purpose)e (multiprogrammed)e(operating)j(sys-)2010 2034 y(tems)d(do)f(not)h(pro)o (vide)d(QoS)j(guarantees)f(since)g(the)h(perfor)n(-)2010 2133 y(mance)23 b(of)h(a)g(single)g(application)f(is,)i(in)g(part,)f (determined)e(by)2010 2233 y(the)g(o)o(v)o(erall)e(load)h(on)h(system.) 29 b(As)23 b(a)f(result,)g(man)o(y)e(users)i(pre-)2010 2333 y(fer)h(to)h(use)g(stand-alone)e(systems)i(with)f(limited)h (dependenc)o(y)2010 2432 y(on)30 b(shared)f(serv)o(ers)h(in)g(order)f (to)i(achie)n(v)o(e)e(some)h(semblance)2010 2532 y(of)f(QoS)h(by)g (indirectly)e(controlling)g(the)i(system)g(w)o(orkload.)2010 2632 y(Real-time)j(operating)d(systems)j(are)g(capable)e(of)i(deli)n(v) o(ering)2010 2731 y(performance)c(guarantees)h(such)h(as)h(delay)f (bounds,)h(b)n(ut)g(re-)2010 2831 y(quire)22 b(that)g(applications)f (be)i(modi\002ed)e(to)i(tak)o(e)f(adv)n(antage)f(of)2010 2930 y(the)f(real-time)g(features.)2135 3035 y(Our)f(goal)f(is)j(to)e (pro)o(vide)f(QoS)h(guarantees)f(in)h(the)h(conte)o(xt)2010 3134 y(of)34 b(a)g(general-purpose)c(multiprogrammed)g(operating)i (sys-)2010 3234 y(tem,)23 b(without)e(modi\002cation)f(to)j(the)f (applications,)f(by)h(gi)n(ving)2010 3334 y(the)d(user)h(the)f(option)f (to)i(pro)o(vision)d(system)j(resources)e(among)2010 3433 y(applications)h(in)h(order)e(to)j(achie)n(v)o(e)d(the)i(desired)f (performance)2010 3533 y(le)n(v)o(els.)2135 3637 y(This)33 b(paper)e(introduces)h(a)h(ne)n(w)g(operating)e(system)i(ab-)2010 3737 y(straction)24 b(called)h Fp(r)m(eservation)g(domains)p Fr(,)g(which)f(is)i(intended)2010 3836 y(to)c(pro)o(vide)f(predictable) f(QoS)j(by)f(controlling)e(resource)h(pro-)2010 3936 y(visioning.)28 b(The)21 b(basic)h(idea)f(behind)f(reserv)n(ation)g (domains)h(is)2010 4036 y(to)k(isolate)g(the)h(performance)c(of)i (reserv)n(ation)g(domains)g(from)2010 4135 y(each)31 b(other)-5 b(.)57 b(In)31 b(particular)m(,)i(time-sensiti)n(v)o(e)d (processes)h(can)2010 4235 y(coe)o(xist)20 b(with)g(batch)g(processes)g (on)f(the)i(same)f(system.)2135 4339 y(W)-7 b(e)41 b(discuss)f(the)g (importance)e(of)i Fp(cumulative)f(service)2010 4439 y Fr(guarantee,)f(which)e(complements)f(other)g(QoS)i(parameters)2010 4538 y(such)27 b(as)h Fp(delay)e Fr(and)h Fp(fairness)p Fr(.)46 b(Informally)-5 b(,)26 b(guaranteed)f(cu-)2010 4638 y(mulati)n(v)o(e)30 b(service)h(means)f(that)i(the)f(scheduling)e (delays)i(en-)2010 4738 y(countered)15 b(by)h(a)h(process)g(on)f(v)n (arious)g(resources)f(do)i(not)f(accu-)2010 4837 y(mulate)23 b(o)o(v)o(er)f(the)h(lifetime)g(of)g(the)h(process.)34 b(In)23 b(other)f(w)o(ords,)2010 4937 y(a)f(process)g(that)g(is)h (competing)d(for)h(resources)g(will)i(e)o(x)o(ecute)d(at)2010 5036 y(a)f(predictable)e(rate,)i(which)g(is)g(determined)e(by)i(the)f (fraction)g(of)2010 5136 y(the)i(resources)g(that)g(is)h(reserv)o(ed)e (for)h(that)g(process,)g(re)o(gardless)2010 5236 y(of)h(the)g (intensity)g(of)g(the)g(competition)e(for)i(the)g(resource.)2135 5340 y(W)-7 b(e)25 b(continue)e(with)h(the)h(description)e(of)h(a)h(ne) n(w)f(schedul-)1914 5790 y(1)p eop %%Page: 2 2 2 1 bop 0 23 a Fr(ing)20 b(polic)o(y)e(called)i(Mo)o(v)o(e-T)-7 b(o-Rear)17 b(List)k(Scheduling)d(\(MTR-)0 123 y(LS\),)e(that)g(pro)o (vides)e(cumulati)n(v)o(e)g(service)i(guarantees,)f(as)i(well)0 222 y(as)k(f)o(airness)f(and)g(delay)f(bounds.)125 324 y(Ne)o(xt)47 b(we)i(describe)e(the)h(Eclipse)g(operating)e(system,)0 424 y(which)18 b(is)i(a)f(testbed)g(for)f(operating)f(system)i(support) e(for)i(QoS.)0 523 y(Eclipse)31 b(implements)e(reserv)n(ation)g (domains)h(and)g(MTR-LS)0 623 y(scheduling.)g(Eclipse)22 b(can)g(schedule)g(multiple)f(resources)h(in-)0 723 y(dependently)-5 b(.)39 b(The)25 b(current)f(implementation)g(can)i(schedule)0 822 y(CPU,)d(disk)f(I/O)h(and)e(physical)h(memory)e(\(w)o(orking)h (set\).)31 b(Ex-)0 922 y(perimental)36 b(results)i(indicate)f(that)h (MTR-LS)f(outperforms)0 1021 y(the)g(standard)e(Plan9)h(priority)f (scheduler)h(and)g(a)h(weighted)0 1121 y(round-robin)17 b(scheduler)-5 b(.)28 b(W)-7 b(e)22 b(also)f(include)g(an)g(e)o(xcerpt) f(from)0 1221 y(the)37 b(Eclipse)g(implementation)e(of)h(MTR-LS,)h (which)f(illus-)0 1320 y(trates)21 b(the)f(simplicity)g(of)g(the)g (implementation.)125 1422 y(The)39 b(remainder)g(of)h(this)h(paper)e (is)i(or)o(ganized)c(as)k(fol-)0 1522 y(lo)n(ws.)k(In)26 b(Section)g(2)h(we)g(discuss)g(related)f(w)o(ork.)44 b(Section)26 b(3)0 1621 y(introduces)31 b(the)i(concept)f(of)g(a)i (reserv)n(ation)d(domain.)61 b(Sec-)0 1721 y(tion)18 b(4)h(presents)f(the)h(QoS)g(parameters)e(of)i(interest.)24 b(Section)18 b(5)0 1821 y(presents)24 b(the)h(MTR-LS)f(scheduling)f (polic)o(y)g(and)h(its)h(proper)n(-)0 1920 y(ties.)46 b(The)27 b(implementation)e(of)h(the)h(Eclipse)g(operating)e(sys-)0 2020 y(tem)32 b(is)h(described)e(in)h(Section)g(6.)60 b(Section)32 b(7)g(presents)g(the)0 2119 y(results)22 b(of)f(our)g(preliminary)e(e)o(xperiments)h(with)h(Eclipse.)29 b(Fi-)0 2219 y(nally)-5 b(,)29 b(Section)f(8)g(describes)g(our)f (future)g(w)o(ork)g(and)h(conclu-)0 2319 y(sions.)45 b(The)26 b(Appendix)f(contains)h(a)h(code)f(e)o(xcerpt)f(from)h(the)0 2418 y(Eclipse)20 b(implementation)e(of)i(MTR-LS.)0 2590 y Fv(2)119 b(Related)31 b(W)-9 b(ork)0 2750 y Fr(Stride)34 b(scheduling)e([16)o(])i(and)f(lottery)g(scheduling)g([17)n(])h(at-)0 2849 y(tempt)46 b(to)h(pro)o(vide)d(each)i(process)g(with)g(a)h(share)f (of)h(the)0 2949 y(serv)o(er)27 b(in)g(proportion)e(to)j(its)g (corresponding)c(weight)j(\(num-)0 3049 y(ber)32 b(of)f(\223tick)o (ets\224\).)60 b(Start-time)32 b(f)o(air)g(queuing)e([4)o(])i(and)g (ear)n(-)0 3148 y(liest)j(eligible)f(virtual)g(deadline)f(\002rst)i ([13)o(])f(guarantee)f(f)o(air)n(-)0 3248 y(ness)19 b(bound.)j(Class)e (based)d(queuing)g(\(CBQ\))h([15)o(])g(uses)h(band-)0 3347 y(width)32 b(reserv)n(ations)f(to)i(schedule)e(pack)o(ets)h(on)g (shared)g(data)0 3447 y(links.)79 b(Processor)38 b(capacity)f(reserv)o (es)h([7)o(])g(pro)o(vides)f(each)0 3547 y(process)e(with)h(its)h (reserv)o(ed)d(share)i(and)f(delay)g(guarantees.)0 3646 y(The)25 b(SMAR)-5 b(T)25 b(scheduler)f([8)o(])h(pro)o(vides)e (predictable)g(perfor)n(-)0 3746 y(mance)29 b(for)h(real-time)f (applications,)i(which)f(may)f(e)o(x)o(ecuted)0 3846 y(concurrently)c(with)k(non)e(real-time)h(applications.)48 b(SMAR)-5 b(T)0 3945 y(allo)n(ws)21 b(processes)g(to)h(specify)e(their) h(scheduling)f(constraints,)0 4045 y(and)c(pro)o(vides)g(dynamic)f (feedback)g(to)i(applications)f(when)h(the)0 4144 y(constrains)36 b(cannot)g(be)g(met.)75 b(The)36 b(Rialto)h(operating)e(sys-)0 4244 y(tem)16 b([5)o(])g(pro)o(vides)e(resource)g(reserv)n(ations)g (similar)i(to)g(Eclipse.)0 4344 y(Ho)n(we)n(v)o(er)m(,)23 b(both)g(SMAR)-5 b(T)24 b(and)f(Rialto)i(schedule)e(only)g(CPU.)0 4443 y(The)c(Nemesis)h(operating)e(system)i([6)o(])g(pro)o(vides)e (accurate)h(ac-)0 4543 y(counting)h(of)h(resource)f(consumption)f(by)i (running)e(the)i(appli-)0 4643 y(cation)k(and)f(most)h(of)g(the)g(k)o (ernel)f(code)h(in)g(the)g(same)g(address)0 4742 y(space.)44 b(Nemesis)27 b(is)h(similar)f(to)g(Eclipse)f(by)g(pro)o(viding)e(pre-)0 4842 y(dictable)17 b(performance)f(via)i(allocation)f(of)h(CPU)h(and)e (disk)h(I/O)0 4941 y(to)k(domains.)28 b(Ho)n(we)n(v)o(er)m(,)20 b(Nemesis)i(emplo)o(ys)e(a)i(radically)f(dif-)0 5041 y(ferent)16 b(OS)h(structure,)f(which)g(necessitates)i(re)n(writing)d (of)i(most)0 5141 y(applications)27 b(and)h(de)n(vice)g(dri)n(v)o(ers.) 49 b(The)28 b(abo)o(v)o(e)f(algorithms)0 5240 y(and)20 b(systems)h(were)f(not)g(designed)f(with)i(our)f(cumulati)n(v)o(e)e (ser)n(-)0 5340 y(vice)34 b(measure)f(in)h(mind,)j(so)d(it)h(is)g(not)f (surprising)e(that)j(the)2010 933 y @beginspecial 101 @llx 306 @lly 544 @urx 519 @ury 2250 @rwi @setspecial %%BeginDocument: rd.ps %!PS-Adobe-2.0 EPSF-1.2 %%Creator: idraw %%DocumentFonts: Times-Roman %%Pages: 1 %%BoundingBox: 101 306 544 519 %%EndComments /arrowHeight 10 def /arrowWidth 5 def /IdrawDict 51 dict def IdrawDict begin /reencodeISO { dup dup findfont dup length dict begin { 1 index /FID ne { def }{ pop pop } ifelse } forall /Encoding ISOLatin1Encoding def currentdict end definefont } def /ISOLatin1Encoding [ /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /space/exclam/quotedbl/numbersign/dollar/percent/ampersand/quoteright /parenleft/parenright/asterisk/plus/comma/minus/period/slash /zero/one/two/three/four/five/six/seven/eight/nine/colon/semicolon /less/equal/greater/question/at/A/B/C/D/E/F/G/H/I/J/K/L/M/N /O/P/Q/R/S/T/U/V/W/X/Y/Z/bracketleft/backslash/bracketright /asciicircum/underscore/quoteleft/a/b/c/d/e/f/g/h/i/j/k/l/m /n/o/p/q/r/s/t/u/v/w/x/y/z/braceleft/bar/braceright/asciitilde /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/dotlessi/grave/acute/circumflex/tilde/macron/breve /dotaccent/dieresis/.notdef/ring/cedilla/.notdef/hungarumlaut /ogonek/caron/space/exclamdown/cent/sterling/currency/yen/brokenbar /section/dieresis/copyright/ordfeminine/guillemotleft/logicalnot /hyphen/registered/macron/degree/plusminus/twosuperior/threesuperior /acute/mu/paragraph/periodcentered/cedilla/onesuperior/ordmasculine /guillemotright/onequarter/onehalf/threequarters/questiondown /Agrave/Aacute/Acircumflex/Atilde/Adieresis/Aring/AE/Ccedilla /Egrave/Eacute/Ecircumflex/Edieresis/Igrave/Iacute/Icircumflex /Idieresis/Eth/Ntilde/Ograve/Oacute/Ocircumflex/Otilde/Odieresis /multiply/Oslash/Ugrave/Uacute/Ucircumflex/Udieresis/Yacute /Thorn/germandbls/agrave/aacute/acircumflex/atilde/adieresis /aring/ae/ccedilla/egrave/eacute/ecircumflex/edieresis/igrave /iacute/icircumflex/idieresis/eth/ntilde/ograve/oacute/ocircumflex /otilde/odieresis/divide/oslash/ugrave/uacute/ucircumflex/udieresis /yacute/thorn/ydieresis ] def /Times-Roman reencodeISO def /none null def /numGraphicParameters 17 def /stringLimit 65535 def /Begin { save numGraphicParameters dict begin } def /End { end restore } def /SetB { dup type /nulltype eq { pop false /brushRightArrow idef false /brushLeftArrow idef true /brushNone idef } { /brushDashOffset idef /brushDashArray idef 0 ne /brushRightArrow idef 0 ne /brushLeftArrow idef /brushWidth idef false /brushNone idef } ifelse } def /SetCFg { /fgblue idef /fggreen idef /fgred idef } def /SetCBg { /bgblue idef /bggreen idef /bgred idef } def /SetF { /printSize idef /printFont idef } def /SetP { dup type /nulltype eq { pop true /patternNone idef } { dup -1 eq { /patternGrayLevel idef /patternString idef } { /patternGrayLevel idef } ifelse false /patternNone idef } ifelse } def /BSpl { 0 begin storexyn newpath n 1 gt { 0 0 0 0 0 0 1 1 true subspline n 2 gt { 0 0 0 0 1 1 2 2 false subspline 1 1 n 3 sub { /i exch def i 1 sub dup i dup i 1 add dup i 2 add dup false subspline } for n 3 sub dup n 2 sub dup n 1 sub dup 2 copy false subspline } if n 2 sub dup n 1 sub dup 2 copy 2 copy false subspline patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if brushNone not { istroke } if 0 0 1 1 leftarrow n 2 sub dup n 1 sub dup rightarrow } if end } dup 0 4 dict put def /Circ { newpath 0 360 arc patternNone not { ifill } if brushNone not { istroke } if } def /CBSpl { 0 begin dup 2 gt { storexyn newpath n 1 sub dup 0 0 1 1 2 2 true subspline 1 1 n 3 sub { /i exch def i 1 sub dup i dup i 1 add dup i 2 add dup false subspline } for n 3 sub dup n 2 sub dup n 1 sub dup 0 0 false subspline n 2 sub dup n 1 sub dup 0 0 1 1 false subspline patternNone not { ifill } if brushNone not { istroke } if } { Poly } ifelse end } dup 0 4 dict put def /Elli { 0 begin newpath 4 2 roll translate scale 0 0 1 0 360 arc patternNone not { ifill } if brushNone not { istroke } if end } dup 0 1 dict put def /Line { 0 begin 2 storexyn newpath x 0 get y 0 get moveto x 1 get y 1 get lineto brushNone not { istroke } if 0 0 1 1 leftarrow 0 0 1 1 rightarrow end } dup 0 4 dict put def /MLine { 0 begin storexyn newpath n 1 gt { x 0 get y 0 get moveto 1 1 n 1 sub { /i exch def x i get y i get lineto } for patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if brushNone not { istroke } if 0 0 1 1 leftarrow n 2 sub dup n 1 sub dup rightarrow } if end } dup 0 4 dict put def /Poly { 3 1 roll newpath moveto -1 add { lineto } repeat closepath patternNone not { ifill } if brushNone not { istroke } if } def /Rect { 0 begin /t exch def /r exch def /b exch def /l exch def newpath l b moveto l t lineto r t lineto r b lineto closepath patternNone not { ifill } if brushNone not { istroke } if end } dup 0 4 dict put def /Text { ishow } def /idef { dup where { pop pop pop } { exch def } ifelse } def /ifill { 0 begin gsave patternGrayLevel -1 ne { fgred bgred fgred sub patternGrayLevel mul add fggreen bggreen fggreen sub patternGrayLevel mul add fgblue bgblue fgblue sub patternGrayLevel mul add setrgbcolor eofill } { eoclip originalCTM setmatrix pathbbox /t exch def /r exch def /b exch def /l exch def /w r l sub ceiling cvi def /h t b sub ceiling cvi def /imageByteWidth w 8 div ceiling cvi def /imageHeight h def bgred bggreen bgblue setrgbcolor eofill fgred fggreen fgblue setrgbcolor w 0 gt h 0 gt and { l b translate w h scale w h true [w 0 0 h neg 0 h] { patternproc } imagemask } if } ifelse grestore end } dup 0 8 dict put def /istroke { gsave brushDashOffset -1 eq { [] 0 setdash 1 setgray } { brushDashArray brushDashOffset setdash fgred fggreen fgblue setrgbcolor } ifelse brushWidth setlinewidth originalCTM setmatrix stroke grestore } def /ishow { 0 begin gsave fgred fggreen fgblue setrgbcolor /fontDict printFont printSize scalefont dup setfont def /descender fontDict begin 0 [FontBBox] 1 get FontMatrix end transform exch pop def /vertoffset 1 printSize sub descender sub def { 0 vertoffset moveto show /vertoffset vertoffset printSize sub def } forall grestore end } dup 0 3 dict put def /patternproc { 0 begin /patternByteLength patternString length def /patternHeight patternByteLength 8 mul sqrt cvi def /patternWidth patternHeight def /patternByteWidth patternWidth 8 idiv def /imageByteMaxLength imageByteWidth imageHeight mul stringLimit patternByteWidth sub min def /imageMaxHeight imageByteMaxLength imageByteWidth idiv patternHeight idiv patternHeight mul patternHeight max def /imageHeight imageHeight imageMaxHeight sub store /imageString imageByteWidth imageMaxHeight mul patternByteWidth add string def 0 1 imageMaxHeight 1 sub { /y exch def /patternRow y patternByteWidth mul patternByteLength mod def /patternRowString patternString patternRow patternByteWidth getinterval def /imageRow y imageByteWidth mul def 0 patternByteWidth imageByteWidth 1 sub { /x exch def imageString imageRow x add patternRowString putinterval } for } for imageString end } dup 0 12 dict put def /min { dup 3 2 roll dup 4 3 roll lt { exch } if pop } def /max { dup 3 2 roll dup 4 3 roll gt { exch } if pop } def /midpoint { 0 begin /y1 exch def /x1 exch def /y0 exch def /x0 exch def x0 x1 add 2 div y0 y1 add 2 div end } dup 0 4 dict put def /thirdpoint { 0 begin /y1 exch def /x1 exch def /y0 exch def /x0 exch def x0 2 mul x1 add 3 div y0 2 mul y1 add 3 div end } dup 0 4 dict put def /subspline { 0 begin /movetoNeeded exch def y exch get /y3 exch def x exch get /x3 exch def y exch get /y2 exch def x exch get /x2 exch def y exch get /y1 exch def x exch get /x1 exch def y exch get /y0 exch def x exch get /x0 exch def x1 y1 x2 y2 thirdpoint /p1y exch def /p1x exch def x2 y2 x1 y1 thirdpoint /p2y exch def /p2x exch def x1 y1 x0 y0 thirdpoint p1x p1y midpoint /p0y exch def /p0x exch def x2 y2 x3 y3 thirdpoint p2x p2y midpoint /p3y exch def /p3x exch def movetoNeeded { p0x p0y moveto } if p1x p1y p2x p2y p3x p3y curveto end } dup 0 17 dict put def /storexyn { /n exch def /y n array def /x n array def n 1 sub -1 0 { /i exch def y i 3 2 roll put x i 3 2 roll put } for } def /SSten { fgred fggreen fgblue setrgbcolor dup true exch 1 0 0 -1 0 6 -1 roll matrix astore } def /FSten { dup 3 -1 roll dup 4 1 roll exch newpath 0 0 moveto dup 0 exch lineto exch dup 3 1 roll exch lineto 0 lineto closepath bgred bggreen bgblue setrgbcolor eofill SSten } def /Rast { exch dup 3 1 roll 1 0 0 -1 0 6 -1 roll matrix astore } def %%EndProlog %%BeginIdrawPrologue /arrowhead { 0 begin transform originalCTM itransform /taily exch def /tailx exch def transform originalCTM itransform /tipy exch def /tipx exch def /dy tipy taily sub def /dx tipx tailx sub def /angle dx 0 ne dy 0 ne or { dy dx atan } { 90 } ifelse def gsave originalCTM setmatrix tipx tipy translate angle rotate newpath arrowHeight neg arrowWidth 2 div moveto 0 0 lineto arrowHeight neg arrowWidth 2 div neg lineto patternNone not { originalCTM setmatrix /padtip arrowHeight 2 exp 0.25 arrowWidth 2 exp mul add sqrt brushWidth mul arrowWidth div def /padtail brushWidth 2 div def tipx tipy translate angle rotate padtip 0 translate arrowHeight padtip add padtail add arrowHeight div dup scale arrowheadpath ifill } if brushNone not { originalCTM setmatrix tipx tipy translate angle rotate arrowheadpath istroke } if grestore end } dup 0 9 dict put def /arrowheadpath { newpath arrowHeight neg arrowWidth 2 div moveto 0 0 lineto arrowHeight neg arrowWidth 2 div neg lineto } def /leftarrow { 0 begin y exch get /taily exch def x exch get /tailx exch def y exch get /tipy exch def x exch get /tipx exch def brushLeftArrow { tipx tipy tailx taily arrowhead } if end } dup 0 4 dict put def /rightarrow { 0 begin y exch get /tipy exch def x exch get /tipx exch def y exch get /taily exch def x exch get /tailx exch def brushRightArrow { tipx tipy tailx taily arrowhead } if end } dup 0 4 dict put def %%EndIdrawPrologue %I Idraw 10 Grid 8.83569e-40 4.96317e-40 %%Page: 1 1 Begin %I b u %I cfg u %I cbg u %I f u %I p u %I t [ 0.799705 0 0 0.799705 0 0 ] concat /originalCTM matrix currentmatrix def Begin %I Elli %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 -0 -0 1 88 206 ] concat %I 96 386 24 24 Elli End Begin %I Elli %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 -0 -0 1 88 206 ] concat %I 176 386 24 24 Elli End Begin %I Elli %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 -0 -0 1 88 206 ] concat %I 216 330 24 24 Elli End Begin %I CBSpl %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 -0 -0 1 88 206 ] concat %I 6 48 418 152 442 288 402 264 250 72 234 40 306 6 CBSpl End Begin %I CBSpl %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 -0 -0 1 56 78 ] concat %I 5 336 426 432 426 448 346 344 306 280 402 5 CBSpl End Begin %I CBSpl %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 -0 -0 1 184 334 ] concat %I 5 240 218 288 290 392 314 496 266 376 98 5 CBSpl End Begin %I Rect %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 -0 -0 1 27 204 ] concat %I 125 292 157 324 Rect End Begin %I Elli %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 64 86 ] concat %I 392 378 24 24 Elli End Begin %I Rect %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 11 76 ] concat %I 373 372 405 404 Rect End Begin %I Elli %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 192 294 ] concat %I 392 306 24 24 Elli End Begin %I Rect %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 131 332 ] concat %I 381 252 413 284 Rect End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f -*-times-medium-r-normal-*-14-*-*-*-*-*-*-* Times-Roman 14 SetF %I t [ 1 0 0 1 216 485 ] concat %I [ (RD1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f -*-times-medium-r-normal-*-14-*-*-*-*-*-*-* Times-Roman 14 SetF %I t [ 1 0 0 1 424 429 ] concat %I [ (RD3) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f -*-times-medium-r-normal-*-14-*-*-*-*-*-*-* Times-Roman 14 SetF %I t [ 1 0 0 1 520 525 ] concat %I [ (RD2) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f -*-times-medium-r-normal-*-14-*-*-*-*-*-*-* Times-Roman 14 SetF %I t [ 1 0 0 1 176 597 ] concat %I [ (P1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f -*-times-medium-r-normal-*-14-*-*-*-*-*-*-* Times-Roman 14 SetF %I t [ 1 0 0 1 256 597 ] concat %I [ (P3) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f -*-times-medium-r-normal-*-14-*-*-*-*-*-*-* Times-Roman 14 SetF %I t [ 1 0 0 1 448 469 ] concat %I [ (P2) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f -*-times-medium-r-normal-*-14-*-*-*-*-*-*-* Times-Roman 14 SetF %I t [ 1 0 0 1 576 605 ] concat %I [ (P4) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f -*-times-medium-r-normal-*-14-*-*-*-*-*-*-* Times-Roman 14 SetF %I t [ 1 0 0 1 160 518 ] concat %I [ (R1) ] Text End Begin %I Rect %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 -0 -0 1 18 155 ] concat %I 190 357 222 389 Rect End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f -*-times-medium-r-normal-*-14-*-*-*-*-*-*-* Times-Roman 14 SetF %I t [ 1 0 0 1 216 533 ] concat %I [ (R2) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f -*-times-medium-r-normal-*-14-*-*-*-*-*-*-* Times-Roman 14 SetF %I t [ 1 0 0 1 296 541 ] concat %I [ (P6) ] Text End Begin %I Rect %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 -0 -0 1 18 155 ] concat %I 446 389 478 421 Rect End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f -*-times-medium-r-normal-*-14-*-*-*-*-*-*-* Times-Roman 14 SetF %I t [ 1 0 0 1 472 565 ] concat %I [ (R2) ] Text End Begin %I Rect %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 -0 -0 1 18 155 ] concat %I 518 381 550 413 Rect End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f -*-times-medium-r-normal-*-14-*-*-*-*-*-*-* Times-Roman 14 SetF %I t [ 1 0 0 1 544 557 ] concat %I [ (R3) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f -*-times-medium-r-normal-*-14-*-*-*-*-*-*-* Times-Roman 14 SetF %I t [ 1 0 0 1 520 605 ] concat %I [ (R1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f -*-times-medium-r-normal-*-14-*-*-*-*-*-*-* Times-Roman 14 SetF %I t [ 1 0 0 1 392 469 ] concat %I [ (R1) ] Text End End %I eop showpage %%Trailer end %%EndDocument @endspecial 2242 1019 a(Figure)20 b(1:)25 b(A)c(Reserv)n (ation-Domains)c(System)2010 1291 y(properties)25 b(the)o(y)h(do)g (enjo)o(y)g(are)h(not)f(suf)n(\002cient)g(to)h(guarantee)2010 1391 y(cumulati)n(v)o(e)18 b(service)i(ef)n(fecti)n(v)o(ely)-5 b(.)2010 1568 y Fv(3)119 b(Reser)o(v)o(ation)30 b(Domains)2010 1729 y Fr(In)24 b(order)g(to)g(incorporate)f(QoS)h(into)h(operating)d (systems,)k(we)2010 1828 y(introduce)16 b(the)j(notion)e(of)h(a)g Fp(r)m(eservation)g(domain)p Fr(.)23 b(A)c(reserv)n(a-)2010 1928 y(tion)g(domain)f(is)i(a)g(collection)e(of)h(processes)g(and)f (correspond-)2010 2028 y(ing)25 b(resource)f(reserv)n(ations.)38 b(A)26 b(computer)d(system)j(may)e(run)2010 2127 y(se)n(v)o(eral)32 b(reserv)n(ation)f(domains)h(and)h(pro)o(vide)d(se)n(v)o(eral)j(types) 2010 2227 y(of)28 b(resources)f(\(e.g.,)i(CPU,)f(disk,)i(netw)o(ork,)e (physical)f(mem-)2010 2326 y(ory\),)j(which)e(are)h(reserv)o(ed)e(and)i (scheduled)e(independently)-5 b(.)2010 2426 y(The)20 b(processes)g(that)g(belong)e(to)j(a)f(particular)f(reserv)n(ation)f (do-)2010 2526 y(main)d(are)h(guaranteed)d(to)j(recei)n(v)o(e)f(at)h (least)h(their)e(reserv)o(ed)f(por)n(-)2010 2625 y(tions)25 b(of)f(the)h(domain')-5 b(s)24 b(associated)g(resources.)37 b(Figure)24 b(1)h(il-)2010 2725 y(lustrates)g(a)h(system)f(that)g(runs) f(three)h(reserv)n(ations)f(domains:)2010 2825 y Fo(R)q(D)2143 2837 y Fn(1)2180 2825 y Fr(,)d Fo(R)q(D)2355 2837 y Fn(2)2412 2825 y Fr(and)g Fo(R)q(D)2687 2837 y Fn(3)2723 2825 y Fo(:)g Fr(Each)g(domain)e(contains)h(an)g(e)o(xplicit)2010 2924 y(resource)26 b(reserv)n(ation)f(for)i(the)g(resources)f Fo(R)q Fm(1)p Fr(,)j Fo(R)q Fm(2)d Fr(and)h Fo(R)q Fm(3)p Fr(.)2010 3024 y(One)21 b(or)g(more)g(processes)g(may)g(run)g(within)g (a)g(single)h(reserv)n(a-)2010 3123 y(tion)e(domain.)2135 3196 y(Reserv)n(ation)33 b(domains)h(are)g(designed)g(to)g(combine)g (the)2010 3296 y(adv)n(antages)29 b(of)h(real-time,)i(time-sharing,)f (and)f(stand-alone)2010 3395 y(systems.)74 b(Bene\002ts)36 b(of)g(reserv)n(ation)f(domains,)k(which)d(are)2010 3495 y(impossible)23 b(to)h(achie)n(v)o(e)f(with)h(priority)e(based)i (scheduling)e(or)2010 3595 y(real-time)d(scheduling)g(algorithms,)g (are:)2135 3709 y Fs(\017)41 b Fr(Pro)o(vides)18 b(QoS)h(guarantees)f (e)n(v)o(en)h(when)g(the)g(system)h(is)2218 3809 y(o)o(v)o(erloaded.)36 b(In)25 b(f)o(act,)h(a)g(reserv)n(ation)e(domain)f(is)j(sim-)2218 3909 y(ilar)e(to)h(a)g(smaller)m(,)g(dedicated)f(machine.)37 b(Application)2218 4008 y(programs)29 b(need)i(not)g(be)h(re)n(written) f(to)g(use)h(real-time)2218 4108 y(services)c(in)h(order)f(to)h(deli)n (v)o(er)f(predictable)f(QoS)i(in)g(a)2218 4208 y(shared)19 b(en)m(vironment.)2135 4325 y Fs(\017)41 b Fr(Allo)n(ws)16 b(di)n(vision)f(of)h(resources)f(according)f(to)i(a)g(polic)o(y)-5 b(.)2218 4425 y(F)o(or)27 b(e)o(xample,)h(tw)o(o)f(reserv)n(ation)f (domains)h(may)g(each)2218 4525 y(reserv)o(e)d(half)h(the)h(CPU,)g (although)d(one)i(of)g(them)g(con-)2218 4624 y(tains)j(more)g (processes)g(than)g(the)g(other)m(,)h(and)f(all)h(pro-)2218 4724 y(cesses)21 b(are)f(CPU)h(bound.)2135 4842 y Fs(\017)41 b Fr(Supports)20 b(interesting)g(w)o(ays)i(of)f(controlling)e(the)i (com-)2218 4941 y(puting)e(en)m(vironment.)25 b(F)o(or)c(e)o(xample,)e (the)i(windo)n(wing)2218 5041 y(system)30 b(may)g(be)g(able)g(to)h (change)e(resource)g(reserv)n(a-)2218 5141 y(tions)h(of)h(domains)f (associated)h(with)g(the)g(windo)n(w)e(in)2218 5240 y(focus)17 b(\(important\))e(and)i(of)h(closed)f(windo)n(ws)g(\(less)i(im-)2218 5340 y(portant\).)39 b(Another)24 b(possibility)h(is)h(a)g(resource)e (super)n(-)p eop %%Page: 3 3 3 2 bop 208 23 a Fr(visor)m(,)36 b(that)e(adapts)f(resource)g(reserv)n (ations)f(dynami-)208 123 y(cally)24 b(according)f(to)i(the)f (\223complaints\224)g(of)g(processes.)208 222 y(A)c(process)g(that)h (misses)g(its)h(deadlines)d(will)i(complain,)208 322 y(which)30 b(will)h(prompt)e(the)i(supervisor)e(to)h(increase)h(its)208 422 y(reserv)n(ations.)55 b(A)31 b(process)f(that)h(meets)g(its)g (deadlines)208 521 y(will)18 b(k)o(eep)f(silent,)i(and)e(will)i(get)e (a)i(smaller)e(reserv)n(ation.)125 685 y(A)29 b(v)n(ariety)g(of)g (applications)f(can)h(bene\002t)g(from)f(reserv)n(a-)0 784 y(tion)f(domains.)45 b(F)o(or)27 b(e)o(xample,)h(soft-real-time)e (applications)0 884 y(can)34 b(use)g(bounded)e(response)h(times,)38 b(hosting)33 b(applications)0 983 y(can)21 b(bene\002t)g(from)f(pro)o (visioning)e(the)j(system)h(resources,)e(and)0 1083 y(long)26 b(running)e(OLAP)j(\(on-line)e(analytical)h(processing\))f(ap-)0 1183 y(plications)36 b(can)g(use)g(protection)e(between)i(reserv)n (ation)e(do-)0 1282 y(mains)26 b(to)g(complete)e(their)i(tasks)g(in)g (a)g(timely)f(manner)g(with-)0 1382 y(out)30 b(impacting)e(current)h(w) o(orkload.)53 b(Reserv)n(ation)29 b(domains)0 1482 y(can)h(also)g (bene\002t)f(PC)i(users,)i(who)c(w)o(ould)g(lik)o(e)i(to)f(run)f(se)n (v-)0 1581 y(eral)19 b(applications)e(concurrently)-5 b(,)16 b(when)i(the)g(applications)g(are)0 1681 y(written)h(with)h(the) g(assumption)f(that)g(the)o(y)g(run)g(on)h(a)g(dedicated)0 1780 y(machine.)0 1973 y Fv(4)119 b(QoS)30 b(Guarantees)0 2140 y Fr(The)35 b(reader)e(who)i(is)h(f)o(amiliar)e(with)h(QoS)g (parameters)f(and)0 2240 y(with)24 b([2)o(])g(may)f(skip)g(this)h (section.)35 b(In)23 b(this)h(section)g(we)g(intro-)0 2339 y(duce)e(three)g(Quality)g(of)g(Service)g(\(QoS\))f(parameters:)29 b(cumu-)0 2439 y(lati)n(v)o(e)17 b(service,)g(delay)f(bound)f(and)i(f)o (airness.)24 b(Cumulati)n(v)o(e)15 b(ser)n(-)0 2539 y(vice)h(is)g(a)h (ne)n(w)e(QoS)h(parameter)m(,)f(while)g(delay)h(bound)d(and)j(f)o(air)n (-)0 2638 y(ness)30 b(are)f(well)g(kno)n(wn,)h(and)f(man)o(y)e (scheduling)h(algorithms)0 2738 y(do)d(pro)o(vide)f(them.)40 b(W)-7 b(e)27 b(start)f(with)f(an)h(e)o(xample)e(that)i(sho)n(ws)0 2837 y(the)d(need)f(for)g(the)h(cumulati)n(v)o(e)e(service)h (guarantee.)31 b(The)22 b(def-)0 2937 y(inition)g(of)f(f)o(airness)h (and)g(delay)g(bounds)e(will)j(be)f(gi)n(v)o(en)f(at)i(the)0 3037 y(end)d(of)g(this)g(section.)0 3142 y Fl(Example)31 b(1:)45 b Fr(W)-7 b(e)32 b(assume)e(that)g(the)h(system)g(runs)e(one)h (I/O)0 3242 y(bound)25 b(process)h(together)f(with)i Fo(n)g Fr(in\002nite)f(loops.)44 b(The)26 b(sys-)0 3342 y(tem)f(emplo)o(ys)e(a)i(weighted)e(round-robin)e(scheduler)m(,)i (similar)0 3441 y(to)f(the)g(one)f(described)g(in)h(Section)f(6.2.)29 b(The)22 b(I/O)g(bound)e(pro-)0 3541 y(cess)h(issues)h(I/O)e(requests)g (sequentially)-5 b(.)24 b(It)d(requires)e(1)i(msec.)0 3640 y(of)i(CPU)g(in)g(order)f(to)h(issue)h(the)e(ne)o(xt)h(I/O)g (request.)32 b(Each)22 b(I/O)0 3740 y(request)e(requires)h(23)f(msec.) 28 b(to)22 b(complete.)k(There)21 b(is)h(no)e(con-)0 3840 y(tention)h(on)g(the)h(I/O)f(de)n(vice.)29 b(W)-7 b(e)22 b(reserv)o(e)f(0.5)g(of)g(the)h(CPU)g(to)0 3939 y(the)h(I/O)g(bound)f(process.)33 b(W)-7 b(e)24 b(e)o(xpect)e(that)i (each)e(iteration)h(of)0 4039 y(the)k(I/O)h(bound)e(process)h(will)h (last)g Fm(2)23 b(+)h(23)j Fr(msec.,)i(where)d(2)0 4139 y(msec.)35 b(is)25 b(the)e(e)o(xpected)f(e)o(x)o(ecution)g(time)h(of)h (the)f(CPU)i(phase)0 4238 y(of)d(each)f(iteration)h(\(1)f(msec.)31 b(on)21 b(an)h(idle)g(machine)f(is)i(equi)n(v)n(a-)0 4338 y(lent)16 b(to)h(2)f(msec.)24 b(elapsed)16 b(time)g(when)g(the)g (process)g(is)h(reserv)o(ed)0 4437 y(0.5)g(of)g(the)h(CPU\).)f(Thus)h (the)f(e)o(xpected)f(e)o(x)o(ecution)f(rate)j(of)f(this)0 4537 y(program)h(is)j Fm(1000)p Fo(=)p Fm(25)f(=)i(40)e Fr(iterations)g(per)g(second.)125 4643 y(Ho)n(we)n(v)o(er)m(,)e(whene)n (v)o(er)h(the)h(I/O)h(bound)e(process)h(arri)n(v)o(es)g(at)0 4742 y(the)d(CPU,)i(it)f(is)g(appended)d(to)j(the)f(end)g(of)g(the)h (ready)e(processes)0 4842 y(queue,)i(so)h(it)h(has)f(to)g(w)o(ait)h (for)e(at)i(least)g Fo(n)f Fr(time)g(slices)h(before)e(it)0 4941 y(can)h(run.)24 b(Thus)18 b(the)h(actual)g(e)o(x)o(ecution)e(time) i(of)g(each)f(iteration)0 5041 y(is)30 b Fm(1)25 b(+)g Fo(n\016)k Fm(+)c(23)p Fr(,)31 b(where)e Fo(\016)k Fr(is)d(the)g(time)g (slice)g(length.)52 b(F)o(or)0 5141 y(e)o(xample,)26 b(for)g Fo(n)34 b Fm(=)g(10)26 b Fr(and)g Fo(\016)37 b Fm(=)d(10)26 b Fr(msec.)43 b(the)27 b(e)o(x)o(ecution)0 5240 y(rate)16 b(of)f(the)h(I/O)f(bound)f(process)h(is)i Fm(1000)p Fo(=)p Fm(\(1)q(+)q(100)q(+)q(23\))i Fs(\031)k Fm(8)p Fr(,)0 5340 y(which)d(is)h(one)e(\002fth)i(of)e(the)i(e)o (xpected)d(rate!)2135 23 y(Note)34 b(that)g(the)g(round-robin)c (scheduler)j(pro)o(vides)g(f)o(air)n(-)2010 123 y(ness)19 b(and)f(delay)f(bounds,)g(since)i(all)g(processes)f(are)g(scheduled) 2010 222 y(within)28 b Fo(n)d Fm(+)f(1)29 b Fr(time)f(slices.)51 b(Ho)n(we)n(v)o(er)m(,)29 b(the)f(e)o(x)o(ecution)f(rate)2010 322 y(of)k(the)g(I/O)g(bound)f(process)g(can)h(be)g(arbitrarily)f(lo)n (w)-5 b(,)33 b(since)2010 422 y(round-robin)16 b(does)j(not)h(pro)o (vide)d(a)j(cumulati)n(v)o(e)e(service)h(guar)n(-)2010 521 y(antee.)1580 b Fk(2)2135 628 y Fr(W)-7 b(e)20 b(will)g(need)f(the) h(follo)n(wing)e(de\002nitions)g(for)h(the)h(rest)g(of)2010 728 y(the)30 b(section:)44 b(A)30 b(system)g(is)h(considered)d(to)i(be) f(a)i(collection)2010 827 y(of)e(resources)f(\(serv)o(ers\).)50 b(Each)28 b(resource)g(is)i(modeled)e(by)g(a)2010 927 y(\223service)20 b(rate\224)g(and)f(a)h(\223preemption)e(interv)n (al\224)h Fm(\001)p Fo(t)p Fr(.)26 b Fm(\001)p Fo(t)21 b Fr(is)g(the)2010 1027 y(minimum)i(time)i(that)g(the)g(resource)e (must)i(run)f(before)f(a)i(pre-)2010 1126 y(emption)f(can)i(occur)-5 b(.)40 b(A)27 b(resource)d(with)i(a)g(zero)f(preemption)2010 1226 y(interv)n(al)19 b(can)h(preempt)f(a)i(process)e(at)i(an)o(y)f (time.)2135 1333 y(A)33 b(process)g(is)i(considered)c(to)j(e)o(x)o (ecute)e(an)h(ordered)f(set)2010 1432 y(of)24 b(of)f Fp(phases,)i Fr(where)e(a)h(phase)g(is)h(a)f(resource-duration)c(pair)m (,)2010 1532 y Fm(\()p Fo(s;)14 b(t)p Fm(\))p Fr(,)32 b(where)d Fo(s)h Fr(is)g(one)f(of)g(the)h(system)f(resources)g(and)g Fo(t)h Fr(is)2010 1632 y(the)21 b(amount)e(of)i(time)g(it)g(w)o(ould)f (tak)o(e)h(resource)e Fo(s)j Fr(to)f(complete)2010 1731 y(the)i(phase)g(running)e(alone)i(on)g(the)g(resource.)33 b(The)23 b(phases)g(of)2010 1831 y(a)f(process)g(are)g(not)g(kno)n(wn)e (in)i(adv)n(ance.)29 b(The)22 b(identity)f(of)h(the)2010 1931 y(ne)o(xt)29 b(phase)h(is)h(kno)n(wn)d(only)i(after)f(e)o(x)o (ecuting)f(the)i(pre)n(vious)2010 2030 y(phase.)2135 2137 y(Ev)o(en)18 b(though)f(we)j(are)g(interested)e(in)i(the)f (performance)e(of)2010 2237 y(our)g(system)i(o)o(v)o(er)e(all)h (resources,)g(it)h(turns)e(out)h(that,)h(due)e(to)i(the)2010 2336 y(de\002nition)e(of)h(the)h(cumulati)n(v)o(e)d(service)j (guarantee,)d(it)j(is)h(suf)n(\002-)2010 2436 y(cient)c(to)g(study)f (the)h(performance)d(at)k(a)f(single)g(resource.)22 b(From)2010 2536 y(the)h(point)g(of)g(vie)n(w)g(of)g(resource)f Fo(s)p Fr(,)i(a)f(process)g(is)h(denoted)e(by)2010 2635 y(an)g(ordered)d(set)k (of)e(phases)g(that)h(alternate)f(between)g(resource)2010 2735 y Fo(s)30 b Fr(and)f Fp(else)o(wher)m(e)p Fr(.)52 b(The)29 b(\223else)n(where\224)f(resource)g(represents)2010 2835 y(the)20 b(phases)g(of)g(processes)g(at)h(resources)e(other)g (than)h Fo(s)p Fr(.)2135 2942 y(The)j(moti)n(v)n(ation)f(for)h(reserv)n (ation)e(domains)i(is)h(to)g(isolate)2010 3041 y(the)e(each)g(reserv)n (ation)e(domain)h(from)f(the)i(others.)30 b(W)-7 b(e)23 b(w)o(ould)2010 3141 y(lik)o(e)d(to)h(guarantee)d(a)j(lo)n(wer)f(bound) e(on)i(the)g(performance)d(of)j(a)2010 3240 y(reserv)n(ation)d(domain,) g(which)g(is)j(independent)15 b(of)j(other)g(reser)n(-)2010 3340 y(v)n(ation)k(domains.)33 b(Let)23 b Fo(\013)2763 3352 y Fj(i)2815 3340 y Fr(be)g(the)g(fraction)f(of)h(a)g(resource)f (al-)2010 3440 y(located)h(to)i(a)f(reserv)n(ation)f(domain)f Fo(D)3159 3452 y Fj(i)3187 3440 y Fo(:)i Fr(Ideally)-5 b(,)24 b(each)g(reser)n(-)2010 3539 y(v)n(ation)g(domain)g Fo(D)2585 3551 y Fj(i)2638 3539 y Fr(should)g(recei)n(v)o(e)g(at)i (least)g Fo(\013)3464 3551 y Fj(i)3517 3539 y Fr(fraction)e(of)2010 3639 y(the)32 b(resource)e(whene)n(v)o(er)g Fo(D)2878 3651 y Fj(i)2938 3639 y Fr(has)i(a)g(process)g(requiring)e(the)2010 3739 y(resource)24 b(\(a.k.a.,)i(whene)n(v)o(er)d Fo(D)2985 3751 y Fj(i)3038 3739 y Fr(is)k Fp(b)n(usy)p Fr(\).)40 b(W)-7 b(e)27 b(refer)e(to)h(the)2010 3838 y(minimum)d(service)h(time)h (recei)n(v)o(ed)e(in)h(the)h Fp(idealized)f Fr(service)2010 3938 y(model)19 b(as)j Fp(virtual)e(service)h(time)o(.)k Fr(W)-7 b(e)22 b(denote)d(the)i(virtual)e(ser)n(-)2010 4037 y(vice)i(time)g(recei)n(v)o(ed)e(by)i(reserv)n(ation)e(domain)h Fo(D)3471 4049 y Fj(i)3519 4037 y Fr(in)h(an)o(y)g(real)2010 4137 y(time)k(interv)n(al)f Fm([)p Fo(\034)5 b(;)14 b(t)p Fm(])25 b Fr(by)g Fo(v)2788 4149 y Fj(i)2816 4137 y Fm(\()p Fo(\034)5 b(;)14 b(t)p Fm(\))p Fr(.)40 b(Similarly)-5 b(,)25 b(we)g(denote)f(the)2010 4237 y Fp(r)m(eal)i(service)h(time)f Fr(\(running)d(on)j(the)f(resource\))g(recei)n(v)o(ed)f(by)2010 4336 y(reserv)n(ation)c(domain)h Fo(D)2740 4348 y Fj(i)2790 4336 y Fr(in)h(an)o(y)g(real)g(time)g(interv)n(al)f Fm([)p Fo(\034)5 b(;)14 b(t)p Fm(])23 b Fr(by)2010 4436 y Fo(s)2049 4448 y Fj(i)2077 4436 y Fm(\()p Fo(\034)5 b(;)14 b(t)p Fm(\))p Fr(.)26 b(Note)20 b(that)g Fo(\013)2676 4448 y Fj(i)2704 4436 y Fo(v)2744 4448 y Fj(i)2772 4436 y Fm(\()p Fo(\034)5 b(;)14 b(t)p Fm(\))23 b(=)g Fo(s)3094 4448 y Fj(i)3121 4436 y Fm(\()p Fo(\034)5 b(;)14 b(t)p Fm(\))p Fo(:)2135 4543 y Fr(Realizable)19 b(scheduling)f(policies)h (require)f(that)i(we)f(run)g(at)2010 4643 y(most)j(one)g(process)g(at)h (a)g(time)g(on)f(the)g(resource.)30 b(This)23 b(means)2010 4742 y(that)h(if)h(there)f(is)h(more)f(than)g(one)g(process)g(w)o (aiting)g(to)g(run)g(on)2010 4842 y(the)h(resource,)f(then)g(one)h(or)f (both)g(of)h(the)f(processes)h(will)g(e)o(x-)2010 4941 y(perience)d(\(queuing\))f(delay)-5 b(.)34 b(W)-7 b(e)24 b(de\002ne)f Fo(w)3311 4953 y Fj(i)3340 4941 y Fm(\()p Fo(\034)5 b(;)14 b(t)p Fm(\))24 b Fr(be)f(the)h(cu-)2010 5041 y(mulati)n(v)o(e)i Fp(r)m(eal)i(waiting)g(time)g Fr(\(block)o(ed)e(by)h(other)g(domains')2010 5141 y(processes)d (running)e(on)h(the)h(resource\))f(obtained)f(by)i(domain)2010 5240 y Fo(D)2079 5252 y Fj(i)2126 5240 y Fr(in)19 b(the)g(interv)n(al)g Fm([)p Fo(\034)5 b(;)14 b(t)p Fm(])p Fr(.)25 b(By)19 b(de\002nition,)f Fo(w)3337 5252 y Fj(i)3365 5240 y Fm(\()p Fo(\034)5 b(;)14 b(t)p Fm(\))h(+)f Fo(s)3670 5252 y Fj(i)3697 5240 y Fm(\()p Fo(\034)5 b(;)14 b(t)p Fm(\))2010 5340 y Fr(is)22 b(the)f(total)g Fp(r)m(eal)g(time)g Fr(spent)g(by)f(domain)g Fo(D)3336 5352 y Fj(i)3385 5340 y Fr(at)h(the)g(resource)p eop %%Page: 4 4 4 3 bop 0 23 a Fr(in)20 b(the)h(interv)n(al)e Fm([)p Fo(\034)5 b(;)14 b(t)p Fm(])21 b Fr(either)e(by)h(running)e(or)i(w)o (aiting.)125 127 y(In)g(the)h(idealized)f(model,)g(recei)n(ving)f Fo(v)1277 139 y Fj(i)1305 127 y Fm(\()p Fo(\034)5 b(;)14 b(t)p Fm(\))22 b Fr(virtual)e(ser)n(-)0 227 y(vice)d(time)g(tak)o(es)g (at)g(most)g Fo(v)804 239 y Fj(i)832 227 y Fm(\()p Fo(\034)5 b(;)14 b(t)p Fm(\))k Fr(real)f(time.)24 b(W)m(ith)17 b(realizable)0 326 y(scheduling)e(policies,)i(in)g(order)e(to)i(pro)o (vide)e(a)i(performance)d(as)0 426 y(good)h(as)i(the)g(one)f(in)g(the)h (idealized)f(model,)g(the)g(total)h(real)f(time)0 526 y Fo(w)59 538 y Fj(i)87 526 y Fm(\()p Fo(\034)5 b(;)14 b(t)p Fm(\))h(+)f Fo(s)392 538 y Fj(i)419 526 y Fm(\()p Fo(\034)5 b(;)14 b(t)p Fm(\))21 b Fr(spent)d(by)h(domain)f Fo(D)1247 538 y Fj(i)1294 526 y Fr(at)h(the)h(resource)d(in)0 625 y(the)26 b(interv)n(al)f Fm([)p Fo(\034)5 b(;)14 b(t)p Fm(])27 b Fr(to)f(recei)n(v)o(e)f Fo(v)981 637 y Fj(i)1008 625 y Fm(\()p Fo(\034)5 b(;)14 b(t)p Fm(\))27 b Fr(virtual)f(service)f(time)0 725 y(should)e(be)h(less)i(than)d(or)h (equal)g(to)g Fo(v)1094 737 y Fj(i)1122 725 y Fm(\()p Fo(\034)5 b(;)14 b(t)p Fm(\))p Fr(.)38 b(W)-7 b(e)25 b(e)o(xpress)f(the)0 825 y(real)16 b(system')-5 b(s)17 b(ability)e(to)i(match)e(the)h(performance)d(of)j(the)g(ide-)0 924 y(alized)i(system)h(in)g(terms)f(of)g(a)h(cumulati)n(v)o(e)e (service)h(guarantee)0 1024 y([2)o(].)125 1128 y Fl(De\002nition)27 b(1:)38 b Fr(W)-7 b(e)28 b(say)f(that)g(a)g(scheduling)e(polic)o(y)h (pro-)0 1228 y(vides)33 b(a)h Fp(cumulative)e(service)i(guar)o(antee)e Fr(if)h(there)g(e)o(xists)h(a)0 1327 y(constant)d Fo(K)39 b Fr(such)31 b(that)i(for)e(all)i(domains)e Fo(D)1389 1339 y Fj(j)1456 1327 y Fr(and)h Fo(\034)55 b Fs(\024)44 b Fo(t)p Fr(,)0 1427 y(we)21 b(ha)n(v)o(e)e Fo(v)332 1439 y Fj(j)367 1427 y Fm(\()p Fo(\034)5 b(;)14 b(t)p Fm(\))24 b Fs(\025)f Fo(w)710 1439 y Fj(j)745 1427 y Fm(\()p Fo(\034)5 b(;)14 b(t)p Fm(\))19 b(+)f Fo(s)1058 1439 y Fj(j)1093 1427 y Fm(\()p Fo(\034)5 b(;)14 b(t)p Fm(\))19 b Fs(\000)f Fo(K)6 b Fr(.)312 b Fk(2)125 1531 y Fr(Although)24 b(the)i(de\002nition)e(of)i(cumulati)n(v)o(e)e (service)h(guar)n(-)0 1631 y(antee)43 b(is)i(in)e(terms)h(of)f(a)h (single)f(resource,)48 b(it)d(implies)e(a)0 1730 y(\223global\224)33 b(cumulati)n(v)o(e)g(service)h(guarantee)f(\(using)h(cumula-)0 1830 y(ti)n(v)o(e)29 b(virtual)f(service)h(time)g(and)g(cumulati)n(v)o (e)e(real)i(time)g(o)o(v)o(er)0 1930 y(all)20 b(resources\))f(in)g(the) h(multi-resource)d(case)j(where)f(there)h(is)g(a)0 2029 y(constant)c(number)f(of)h(resources)f([2].)24 b(Guaranteeing)14 b(cumula-)0 2129 y(ti)n(v)o(e)20 b(service)g(is)h(vital)f(for)g (applications)f(that)h(require)f(multiple)0 2229 y(resources)26 b(and)g(arri)n(v)n(al)g(of)g(a)i(phase)e(on)g(a)h(resource)f(depends)0 2328 y(on)19 b(the)h(departure)e(of)i(pre)n(vious)e(phases.)24 b(Cumulati)n(v)o(e)19 b(service)0 2428 y(guarantee)g(is)j(necessary)f (to)g(ensure)f(a)h(predictable)f(aggre)o(gate)0 2527 y(throughput)d(o)o(v)o(er)i(all)i(the)f(resources)f(for)h(such)g (applications.)125 2632 y(W)-7 b(e)19 b(will)g(de\002ne)f(the)g(delay)g (guarantee)e(for)i(the)g(case)h(when)0 2731 y(at)37 b(an)o(y)e(gi)n(v)o (en)f(time)j(there)e(is)i(only)e(one)h(process)f(within)h(a)0 2831 y(reserv)n(ation)29 b(domain.)56 b(F)o(or)31 b(the)f(more)h (general)e(case,)34 b(when)0 2931 y(there)23 b(can)g(be)g(multiple)g (concurrent)e(processes)i(within)g(a)g(do-)0 3030 y(main,)29 b(the)f(delay)f(a)h(phase)g(e)o(xperiences)e(also)i(depends)e(ho)n(w)0 3130 y(the)h(reserv)n(ation)e(domain)g(schedules)h(its)i(phases.)44 b(This)27 b(case)0 3229 y(requires)c(elaborate)f(treatment,)i(and)f (will)i(not)e(be)h(co)o(v)o(ered)d(in)0 3329 y(this)g(paper)-5 b(.)125 3433 y Fl(De\002nition)34 b(2:)52 b Fr(A)34 b(scheduling)e (polic)o(y)h(pro)o(vides)f Fp(delay)0 3533 y(bound)25 b Fr(if,)j(for)e(a)g(phase)g(of)h(an)o(y)e(domain)g Fo(D)1325 3545 y Fj(j)1360 3533 y Fo(;)i Fr(the)g(real)f(w)o(ait-)0 3633 y(ing)19 b(time)g(plus)g(service)g(time)g(to)g(complete)f(the)h (phase)g(tak)o(es)g(at)0 3732 y(most)j(a)g(constant)g(amount)e(more)h (than)h Fo(d=\013)1311 3744 y Fj(j)1346 3732 y Fr(,)h(where)e Fo(d)i Fr(is)g(the)0 3832 y(duration)18 b(of)i(the)h(phase.)1056 b Fk(2)125 3936 y Fr(The)31 b(f)o(airness)g(parameter)f(measures)h(the) g(ability)g(of)h(the)0 4036 y(system)e(to)g(ensure)f(that)h(domains)f (that)h(are)g(simultaneously)0 4135 y(contending)e(for)h(the)i(same)f (resource)f(will)i(\223share\224)f(that)g(re-)0 4235 y(source)e(in)i Fp(pr)l(oportion)d Fr(to)j(their)e(reserv)n(ations,)i (independent)0 4335 y(of)18 b(their)h(pre)n(vious)e(usage)h(of)g(the)h (resource)e([3)o(].)25 b(That)18 b(is,)i(a)f(f)o(air)0 4434 y(scheduling)27 b(polic)o(y)g(does)i(not)f(penalize)g(a)h(domain)e (that)i(uti-)0 4534 y(lized)21 b(an)h(idle)f(resource)f(be)o(yond)f (its)k(reserv)n(ation)d(when)g(other)0 4633 y(domains)f(become)g(b)n (usy)h(on)g(that)g(resource.)125 4738 y(The)j(de\002nition)g(of)h(f)o (airness)g(is)g(based)g(on)f(another)g(ideal-)0 4837 y(ized)18 b(service)g(model)f(called)h Fp(pr)l(ocessor)g(sharing)f Fr([11)o(].)25 b(Under)0 4937 y(processor)h(sharing,)i(each)f(domain)f (recei)n(v)o(es)g(a)i(service)f(pro-)0 5037 y(portional)d(to)i(its)h (fraction)d(on)i(a)g(resource.)40 b(Since)26 b(ideal)g(pro-)0 5136 y(cessor)g(sharing)f(cannot)f(be)i(implemented)e(in)i(practice,)h (f)o(air)n(-)0 5236 y(ness)21 b(is)g(de\002ned)e(as:)125 5340 y Fl(De\002nition)h(3:)25 b Fr(A)c(scheduling)e(polic)o(y)g(is)i Fp(fair)g Fr(if)f(there)g(e)o(x-)2010 23 y(ists)33 b(a)g(constant)e Fo(F)44 b Fr(such)32 b(that)g(for)g(an)o(y)f(time)h(interv)n(al)f Fm([)p Fo(\034)5 b(;)14 b(t)p Fm(])2010 123 y Fr(during)24 b(which)i(a)g(pair)f(of)h(domains,)g Fo(D)3196 135 y Fj(i)3250 123 y Fr(and)f Fo(D)3465 135 y Fj(j)3500 123 y Fr(,)i(both)e(con-)2010 222 y(tinuously)k(require)g(the)h(resource,)h (we)g(ha)n(v)o(e)e Fs(j)p Fo(s)3457 234 y Fj(i)3485 222 y Fm(\()p Fo(\034)5 b(;)14 b(t)p Fm(\))p Fo(=\013)3752 234 y Fj(i)3805 222 y Fs(\000)2010 322 y Fo(s)2049 334 y Fj(j)2084 322 y Fm(\()p Fo(\034)5 b(;)14 b(t)p Fm(\))p Fo(=\013)2351 334 y Fj(j)2386 322 y Fs(j)23 b(\024)g Fo(F)12 b Fr(.)1181 b Fk(2)2135 426 y Fr(Reserv)n(ation)15 b(domains)h(specify)g(their)h(QoS)g(requirements)2010 525 y(by)29 b(pro)o(viding)e(a)j(service)g(fraction)e Fo(\013)3149 537 y Fj(i)3207 525 y Fr(for)i(each)f(system)h(re-)2010 625 y(source.)46 b(Admission)27 b(control)f(ensures)h(that)h(the)f(sum) g(of)h(the)2010 724 y(service)j(fractions)g(of)g(all)h(domains)f(do)g (not)g(e)o(xceed)f(certain)2010 824 y(prescribed)15 b(limits.)25 b(Admission)16 b(control)f(is)j(necessary)e(for)g(de-)2010 924 y(lay)k(and)g(cumulati)n(v)o(e)f(service)h(guarantees.)k(It)d(is)g (not)f(required)2010 1023 y(for)g(f)o(airness.)2010 1206 y Fv(5)119 b(Mo)o(v)o(e-to-Rear)29 b(List)g(Scheduling)2010 1369 y Fr(This)i(section)g(presents)g(the)g(Mo)o(v)o(e-T)-7 b(o-Rear)29 b(List)j(Schedul-)2010 1468 y(ing)22 b(\(MTR-LS\))f(polic)o (y)-5 b(,)21 b(which)h(pro)o(vides)e(a)j(cumulati)n(v)o(e)d(ser)n(-) 2010 1568 y(vice)30 b(guarantee,)g(is)h(f)o(air)m(,)g(and)e(has)h (bounded)e(delay)-5 b(.)52 b(MTR-)2010 1668 y(LS)20 b(polic)o(y)f(is)i (a)f(generalization)d(of)j(the)g(one)f(presented)g(in)g([2].)2010 1767 y(The)j(main)g(dif)n(ference)e(is)j(that)g(we)g(allo)n(w)f(here)g (the)g(aggre)o(gate)2010 1867 y(quantum)h(allocated)h(for)g(a)h(domain) e(to)i(be)g(partitioned.)36 b(This)2010 1967 y(impro)o(v)o(es)16 b(QoS)i(guarantees)e(and)h(a)n(v)o(erage)g(delay)g(and)g(w)o(aiting) 2010 2066 y(time.)25 b(In)20 b(the)h(follo)n(wing)d(subsections)i(we)h (present)e(the)h(MTR-)2010 2166 y(LS)h(polic)o(y)-5 b(,)18 b(its)j(comple)o(xity)-5 b(,)18 b(and)h(its)j(properties.)2010 2305 y Fq(5.1)99 b(Algorithm)25 b(and)g(Data)g(Structur)n(es)2010 2439 y Fr(Central)i(to)h(the)f(MTR-LS)g(polic)o(y)f(is)j(an)e(ordered)e (list,)30 b Fs(L)p Fr(,)g(of)2010 2538 y(pairs)19 b Fp(\(i,left\))h Fr(where)e Fo(i)i Fr(is)g(the)g(inde)o(x)e(of)h(a)h(reserv)n(ation)e (domain)2010 2638 y(\(i.e.,)31 b Fo(D)2261 2650 y Fj(i)2288 2638 y Fr(\))f(and)f Fp(left)h Fr(is)g(size)g(of)f(the)h Fp(quantum,)f Fr(which)g(is)i(the)2010 2738 y(maximal)21 b(amount)f(of)i(service)f(time)h(reserv)n(ation)e(domain)h Fo(D)3843 2750 y Fj(i)2010 2837 y Fr(can)16 b(recei)n(v)o(e)f(without)g (being)g(interrupted.)22 b(There)15 b(can)h(be)g(mul-)2010 2937 y(tiple)27 b(occurrences)d(of)i(domain)f Fo(D)3049 2949 y Fj(i)3103 2937 y Fr(on)h Fs(L)p Fr(,)j(that)d(is,)j(pairs)d(ap-) 2010 3037 y(pearing)k(at)h(dif)n(ferent)f(positions)h(in)g(list)h Fs(L)g Fr(which)f(ha)n(v)o(e)g(the)2010 3136 y(same)d(\002rst)h (coordinate)d Fo(i:)i Fr(The)g(pairs)f Fp(\(i,left\))h Fr(will)h(be)f(called)2010 3236 y Fp(tok)o(ens)20 b Fr(in)g(the)h (follo)n(wing)d(discussion.)2135 3339 y(W)