%!PS-Adobe-2.0 %%Creator: dvips by Radical Eye Software %%Title: paper.dvi %%Pages: 14 1 %%BoundingBox: 0 0 612 792 %%EndComments %%BeginDocument: tex.pro /TeXDict 200 dict def TeXDict begin /bdf{bind def}def /bop-aux{}bdf /@rigin{ /@page-height exch def /@page-width exch def 72 Resolution div dup neg scale translate}bdf /@letter{Resolution dup -10 mul 8.5 11 @rigin}bdf /@landscape{[ 0 1 -1 0 0 0]concat Resolution dup 8.5 11 @rigin}bdf /@a4{Resolution dup -10.6929133858 mul 21 2.54 div 29.7 2.54 div @rigin}bdf /@legal{Resolution dup -13 mul 8.5 14 @rigin}bdf /@11x17{statusdict /11x17tray known{statusdict begin 11x17tray end}if Resolution dup -16 mul 11 17 @rigin}bdf /@manualfeed{ statusdict /manualfeed true put}bdf /@copies{/#copies exch def}bdf /@draft{ /bop-aux{gsave initmatrix 72 dup scale @page-width 2 div @page-height 2 div translate @page-height @page-width atan rotate /Helvetica-Bold findfont 2 scalefont setfont(DRAFT)dup stringwidth pop 2 div neg -1 moveto .95 setgray show grestore}bdf}bdf /@FontMatrix[1 0 0 -1 0 0]def /@FontBBox[0 0 0 0]def /dmystr(ZZf@@@)def /newname{dmystr cvn}bdf /df{/fontname exch def dmystr 2 fontname cvx(@@@@)cvs putinterval newname 7 dict def newname load begin /FontType 3 def /FontMatrix @FontMatrix def /FontBBox @FontBBox def /BitMaps 256 array def /BuildChar{CharBuilder}def /Encoding IdentityEncoding def end fontname{/foo setfont}2 array copy cvx def fontname load 0 dmystr 6 string copy cvn cvx put}bdf /dfe{newname dup load definefont setfont}bdf /ch-image{ ch-data 0 get}bdf /ch-width{ch-data 1 get}bdf /ch-height{ch-data 2 get}bdf /ch-xoff{ch-data 3 get}bdf /ch-yoff{ch-data 4 get}bdf /ch-dx{ch-data 5 get} bdf /CharBuilder{save 3 1 roll exch /BitMaps get exch get /ch-data exch def ch-data null ne{ch-dx 0 ch-xoff ch-yoff neg ch-xoff ch-width add ch-height ch-yoff sub setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-height ch-yoff sub .1 add]{ch-image}imagemask}if restore}bdf /dc{/ch-code exch def /ch-data exch def newname load /BitMaps get ch-code ch-data put}bdf /bop{gsave /SaveImage save def /bop-aux load exec 0 0 moveto}bdf /eop{clear SaveImage restore showpage grestore}bdf /@start{/Resolution exch def /IdentityEncoding 256 array def 0 1 255{IdentityEncoding exch 1 string dup 0 3 index put cvn put}for}bdf /p{show}bdf /RuleMatrix[1 0 0 -1 -.1 -.1]def /BlackDots 8 string def /v{gsave currentpoint translate false RuleMatrix{ BlackDots}imagemask grestore}bdf /a{moveto}bdf /delta 0 def /tail{dup /delta exch def 0 rmoveto}bdf /b{exch show tail}bdf /c{show delta 4 sub tail}bdf /d{ show delta 3 sub tail}bdf /e{show delta 2 sub tail}bdf /f{show delta 1 sub tail}bdf /g{show delta 0 rmoveto}bdf /h{show delta 1 add tail}bdf /i{show delta 2 add tail}bdf /j{show delta 3 add tail}bdf /k{show delta 4 add tail} bdf /l{show -4 0 rmoveto}bdf /m{show -3 0 rmoveto}bdf /n{show -2 0 rmoveto} bdf /o{show -1 0 rmoveto}bdf /q{show 1 0 rmoveto}bdf /r{show 2 0 rmoveto}bdf /s{show 3 0 rmoveto}bdf /t{show 4 0 rmoveto}bdf /w{0 rmoveto}bdf /x{0 exch rmoveto}bdf /y{3 2 roll show moveto}bdf /bos{/section save def}bdf /eos{clear section restore}bdf end %%EndDocument %%BeginDocument: texps.pro TeXDict begin /rf{655360 div mul Resolution mul 7227 div /PixPerEm exch def findfont dup length 1 add dict /newfont exch def{1 index /FID ne{newfont 3 1 roll put}{pop pop}ifelse}forall 256 dict begin newfont /Encoding get 255 -1 0{ 2 copy get 4 -1 roll 1000 mul PixPerEm div def pop}for pop newfont /Metrics currentdict put end /fontname exch def dmystr 2 fontname cvx(@@@@)cvs putinterval newname dup newfont definefont[PixPerEm 0 0 PixPerEm neg 0 0] makefont def fontname{/foo setfont}2 array copy cvx def fontname load 0 dmystr 6 string copy cvn cvx put}bdf /ObliqueSlant{dup sin exch cos div neg}bdf /SlantFont{/foo exch def[1 0 foo 1 0 0]TransFont}bdf /ExtendFont{/foo exch def 258 2 roll 0 1 255{pop foo div 256 1 roll}for 258 -2 roll[foo 0 0 1 0 0] TransFont}bdf /TransFont{exch findfont exch makefont dup length dict /newfont exch def{1 index /FID ne{newfont 3 1 roll put}{pop pop}ifelse}forall dup newfont definefont pop}bdf end %%EndDocument %%BeginDocument: special.pro TeXDict begin /SDict 200 dict def SDict begin /@SpecialDefaults{/hs 612 def /vs 792 def /ho 0 def /vo 0 def /hsc 1 def /vsc 1 def /ang 0 def /CLIP false def /BBcalc false def}bdf /@scaleunit 1 def /@hscale{@scaleunit div /hsc exch def}bdf /@vscale{@scaleunit div /vsc exch def}bdf /@hsize{/hs exch def /CLIP true def}bdf /@vsize{/vs exch def /CLIP true def}bdf /@hoffset{/ho exch def} bdf /@voffset{/vo exch def}bdf /@angle{/ang exch def}bdf /@rwi{10 div /rwi exch def}bdf /@llx{/llx exch def}bdf /@lly{/lly exch def}bdf /@urx{/urx exch def}bdf /@ury{/ury exch def /BBcalc true def}bdf end /@MacSetUp{userdict /md known{userdict /md get type /dicttype eq{md begin /letter{}def /note{}def /legal{}def /od{txpose 1 0 mtx defaultmatrix dtransform exch atan/pa exch def newpath clippath mark{transform{itransform moveto}}{transform{itransform lineto}}{6 -2 roll transform 6 -2 roll transform 6 -2 roll transform{ itransform 6 2 roll itransform 6 2 roll itransform 6 2 roll curveto}}{{ closepath}}pathforall newpath counttomark array astore /gc xdf pop ct 39 0 put 10 fz 0 fs 2 F/|______Courier fnt invertflag{PaintBlack}if}def /txpose{pxs pys scale ppr aload pop por{noflips{pop exch neg exch translate pop 1 -1 scale}if xflip yflip and{pop exch neg exch translate 180 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg translate}if xflip yflip not and{pop exch neg exch translate pop 180 rotate ppr 3 get ppr 1 get neg sub neg 0 translate}if yflip xflip not and{ppr 1 get neg ppr 0 get neg translate} if}{noflips{translate pop pop 270 rotate 1 -1 scale}if xflip yflip and{ translate pop pop 90 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg translate}if xflip yflip not and{translate pop pop 90 rotate ppr 3 get ppr 1 get neg sub neg 0 translate}if yflip xflip not and{ translate pop pop 270 rotate ppr 2 get ppr 0 get neg sub neg 0 exch translate} if}ifelse scaleby96{ppr aload pop 4 -1 roll add 2 div 3 1 roll add 2 div 2 copy translate .96 dup scale neg exch neg exch translate}if}def /cp{pop pop showpage pm restore}def end}if}if}def /psf$TeXscale{65536 div}def /startTexFig {/psf$SavedState save def userdict maxlength dict begin Resolution 72 div dup neg scale currentpoint translate /psf$ury exch psf$TeXscale def /psf$urx exch psf$TeXscale def /psf$lly exch psf$TeXscale def /psf$llx exch psf$TeXscale def /psf$y exch psf$TeXscale def /psf$x exch psf$TeXscale def currentpoint /psf$cy exch def /psf$cx exch def /psf$sx psf$x psf$urx psf$llx sub div def /psf$sy psf$y psf$ury psf$lly sub div def psf$sx psf$sy scale psf$cx psf$sx div psf$llx sub psf$cy psf$sy div psf$ury sub translate /showpage{}def /erasepage{ }def /copypage{}def @MacSetUp}def /doclip{psf$llx psf$lly psf$urx psf$ury currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll exch lineto exch lineto exch lineto closepath clip newpath moveto}def /endTexFig{end psf$SavedState restore}def /@beginspecial{SDict begin /SpecialSave save def Resolution 72 div dup neg scale currentpoint translate @SpecialDefaults}bdf /@setspecial{CLIP{newpath 0 0 moveto hs 0 rlineto 0 vs rlineto hs neg 0 rlineto closepath clip}{initclip}ifelse ho vo translate hsc vsc scale ang rotate BBcalc{rwi urx llx sub div dup scale llx neg lly neg translate}if /showpage{}def newpath}bdf /@endspecial{clear SpecialSave restore end}bdf /@defspecial{SDict begin}bdf /@fedspecial{end}bdf /li{lineto}bdf /rl{rlineto} bdf /rc{rcurveto}bdf /np{/SaveX currentpoint /SaveY exch def def newpath}bdf /st{stroke SaveX SaveY moveto}bdf /fil{fill SaveX SaveY moveto}bdf /ellipse{ /endangle exch def /startangle exch def /yrad exch def /xrad exch def /savematrix matrix currentmatrix def translate xrad yrad scale 0 0 1 startangle endangle arc savematrix setmatrix}bdf end %%EndDocument TeXDict begin @defspecial /@scaleunit 100 def @fedspecial end TeXDict begin 300 @start /fa df[< 03C00FF01FF83FFC7FFE7FFEFFFFFFFFFFFFFFFF7FFE7FFE3FFC1FF80FF003C0>16 16 2 -2 21 ]15 dc dfe /fb 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 25 25 25 25 25 25 25 25 25 25 25 25 25 0 0 0 25 25 25 25 0 25 25 25 25 25 25 25 0 0 25 0 25 25 25 25 25 25 25 25 0 25 25 0 25 25 25 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 25 0 0 0 0 25 25 0 25 0 0 0 0 0 0 0 0 0 25 0 0 25 25 0 25 0 0 0 0 /Courier 1000 655360 rf /fc 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 14 23 21 21 42 35 14 14 14 21 24 10 14 10 12 21 21 21 21 21 21 21 21 21 21 14 14 24 24 24 21 39 30 28 30 30 28 25 32 32 16 21 32 28 39 30 32 25 32 30 23 28 30 30 42 30 30 28 14 12 14 24 21 14 21 23 18 23 18 14 21 23 12 14 23 12 35 23 21 23 23 18 16 14 23 21 30 21 21 18 16 9 16 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14 21 21 7 21 21 21 21 12 21 21 14 14 23 23 0 21 21 21 10 0 22 15 14 21 21 21 42 42 0 21 0 14 14 14 14 14 14 14 14 0 14 14 0 14 14 14 42 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 42 0 12 0 0 0 0 28 32 42 14 0 0 0 0 0 30 0 0 0 12 0 0 12 21 30 23 0 0 0 0 /Times-Bold 1000 655360 rf /fd df[<0C000C008C40EDC07F 800C007F80EDC08C400C000C00>10 11 3 -1 16]3 dc dfe /fe 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 11 14 17 17 28 26 11 11 11 17 19 8 11 8 9 17 17 17 17 17 17 17 17 17 17 9 9 19 19 19 15 31 24 22 22 24 20 18 24 24 11 13 24 20 30 24 24 18 24 22 18 20 24 24 31 24 24 20 11 9 11 16 17 11 15 17 15 17 15 11 17 17 9 9 17 9 26 17 17 17 17 11 13 9 17 17 24 17 17 15 16 7 16 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 17 17 6 17 17 17 17 6 15 17 11 11 18 18 0 17 17 17 8 0 15 12 11 15 15 17 33 33 0 15 0 11 11 11 11 11 11 11 11 0 11 11 0 11 11 11 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 30 0 9 0 0 0 0 20 24 30 10 0 0 0 0 0 22 0 0 0 9 0 0 9 17 24 17 0 0 0 0 /Times-Roman 1000 524288 rf /ff 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 14 17 21 21 35 32 14 14 14 21 28 10 14 10 12 21 21 21 21 21 21 21 21 21 21 14 14 28 28 28 21 38 25 25 28 30 25 25 30 30 14 18 28 23 35 28 30 25 30 25 21 23 30 25 35 25 23 23 16 12 16 18 21 14 21 21 18 21 18 12 21 21 12 12 18 12 30 21 21 21 21 16 16 12 21 18 28 18 18 16 17 11 17 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16 21 21 7 21 21 21 21 9 23 21 14 14 21 21 0 21 21 21 10 0 22 15 14 23 23 21 37 42 0 21 0 14 14 14 14 14 14 14 14 0 14 14 0 14 14 14 37 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 37 0 11 0 0 0 0 23 30 39 13 0 0 0 0 0 28 0 0 0 12 0 0 12 21 28 21 0 0 0 0 /Times-Italic 1000 655360 rf /fg 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 14 17 21 21 35 32 14 14 14 21 23 10 14 10 12 21 21 21 21 21 21 21 21 21 21 12 12 23 23 23 18 38 30 28 28 30 25 23 30 30 14 16 30 25 37 30 30 23 30 28 23 25 30 30 39 30 30 25 14 12 14 19 21 14 18 21 18 21 18 14 21 21 12 12 21 12 32 21 21 21 21 14 16 12 21 21 30 21 21 18 20 8 20 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14 21 21 7 21 21 21 21 7 18 21 14 14 23 23 0 21 21 21 10 0 19 15 14 18 18 21 42 42 0 18 0 14 14 14 14 14 14 14 14 0 14 14 0 14 14 14 42 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 37 0 11 0 0 0 0 25 30 37 13 0 0 0 0 0 28 0 0 0 12 0 0 12 21 30 21 0 0 0 0 /Times-Roman 1000 655360 rf /fh 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12 17 28 25 25 50 41 17 17 17 25 28 12 17 12 14 25 25 25 25 25 25 25 25 25 25 17 17 28 28 28 25 46 36 33 36 36 33 30 39 39 19 25 39 33 47 36 39 30 39 36 28 33 36 36 50 36 36 33 17 14 17 29 25 17 25 28 22 28 22 17 25 28 14 17 28 14 41 28 25 28 28 22 19 17 28 25 36 25 25 22 20 11 20 26 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 25 25 8 25 25 25 25 14 25 25 17 17 28 28 0 25 25 25 12 0 27 17 17 25 25 25 50 50 0 25 0 17 17 17 17 17 17 17 17 0 17 17 0 17 17 17 50 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 50 0 15 0 0 0 0 33 39 50 16 0 0 0 0 0 36 0 0 0 14 0 0 14 25 36 28 0 0 0 0 /Times-Bold 1000 786432 rf /fi 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 12 15 19 19 31 29 12 12 12 19 21 9 12 9 10 19 19 19 19 19 19 19 19 19 19 10 10 21 21 21 17 34 27 25 25 27 23 21 27 27 12 15 27 23 33 27 27 21 27 25 21 23 27 27 35 27 27 23 12 10 12 18 19 12 17 19 17 19 17 12 19 19 10 10 19 10 29 19 19 19 19 12 15 10 19 19 27 19 19 17 18 7 18 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12 19 19 6 19 19 19 19 7 17 19 12 12 21 21 0 19 19 19 9 0 17 13 12 17 17 19 37 37 0 17 0 12 12 12 12 12 12 12 12 0 12 12 0 12 12 12 37 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 33 0 10 0 0 0 0 23 27 33 12 0 0 0 0 0 25 0 0 0 10 0 0 10 19 27 19 0 0 0 0 /Times-Roman 1000 589824 rf /fj 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 12 21 19 19 37 31 12 12 12 19 21 9 12 9 10 19 19 19 19 19 19 19 19 19 19 12 12 21 21 21 19 35 27 25 27 27 25 23 29 29 15 19 29 25 35 27 29 23 29 27 21 25 27 27 37 27 27 25 12 10 12 22 19 12 19 21 17 21 17 12 19 21 10 12 21 10 31 21 19 21 21 17 15 12 21 19 27 19 19 17 15 8 15 19 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12 19 19 6 19 19 19 19 10 19 19 12 12 21 21 0 19 19 19 9 0 20 13 12 19 19 19 37 37 0 19 0 12 12 12 12 12 12 12 12 0 12 12 0 12 12 12 37 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 37 0 11 0 0 0 0 25 29 37 12 0 0 0 0 0 27 0 0 0 10 0 0 10 19 27 21 0 0 0 0 /Times-Bold 1000 589824 rf /fk 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12 17 20 25 25 41 39 17 17 17 25 28 12 17 12 14 25 25 25 25 25 25 25 25 25 25 14 14 28 28 28 22 46 36 33 33 36 30 28 36 36 17 19 36 30 44 36 36 28 36 33 28 30 36 36 47 36 36 30 17 14 17 23 25 17 22 25 22 25 22 17 25 25 14 14 25 14 39 25 25 25 25 17 19 14 25 25 36 25 25 22 24 10 24 27 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 25 25 8 25 25 25 25 9 22 25 17 17 28 28 0 25 25 25 12 0 23 17 17 22 22 25 50 50 0 22 0 17 17 17 17 17 17 17 17 0 17 17 0 17 17 17 50 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 44 0 14 0 0 0 0 30 36 44 15 0 0 0 0 0 33 0 0 0 14 0 0 14 25 36 25 0 0 0 0 /Times-Roman 1000 786432 rf /fl df[<020002000200C218F2783AE00F800F803AE0F278C2180200020002 00>13 14 2 -1 18]3 dc dfe /fm 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12 17 21 25 25 41 39 17 17 17 25 34 12 17 12 14 25 25 25 25 25 25 25 25 25 25 17 17 34 34 34 25 46 30 30 33 36 30 30 36 36 17 22 33 28 41 33 36 30 36 30 25 28 36 30 41 30 28 28 19 14 19 21 25 17 25 25 22 25 22 14 25 25 14 14 22 14 36 25 25 25 25 19 19 14 25 22 33 22 22 19 20 14 20 27 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 19 25 25 8 25 25 25 25 11 28 25 17 17 25 25 0 25 25 25 12 0 26 17 17 28 28 25 44 50 0 25 0 17 17 17 17 17 17 17 17 0 17 17 0 17 17 17 44 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 44 0 14 0 0 0 0 28 36 47 15 0 0 0 0 0 33 0 0 0 14 0 0 14 25 33 25 0 0 0 0 /Times-Italic 1000 786432 rf /fn 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 20 33 30 30 60 50 20 20 20 30 34 15 20 15 17 30 30 30 30 30 30 30 30 30 30 20 20 34 34 34 30 56 43 40 43 43 40 37 47 47 23 30 47 40 56 43 47 37 47 43 33 40 43 43 60 43 43 40 20 17 20 35 30 20 30 33 27 33 27 20 30 33 17 20 33 17 50 33 30 33 33 27 23 20 33 30 43 30 30 27 24 13 24 31 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 30 30 10 30 30 30 30 17 30 30 20 20 33 33 0 30 30 30 15 0 32 21 20 30 30 30 60 60 0 30 0 20 20 20 20 20 20 20 20 0 20 20 0 20 20 20 60 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 60 0 18 0 0 0 0 40 47 60 20 0 0 0 0 0 43 0 0 0 17 0 0 17 30 43 33 0 0 0 0 /Times-Bold 1000 943718 rf end TeXDict begin @letter %%EndProlog %%Page: 1 1 bop 396 199 a fn(Generalized)11 b(Emulation)j(Services)f(for)i(Mach)g(3.0) 423 274 y(Overview)m(,)d(Experiences)h(and)i(Curr)o(ent)f(Status)340 436 y fm (Daniel)e(P)-6 b(.)13 b(Julin)124 b(Jonathan)12 b(J.)h(Chew)125 b(J.)13 b(Mar\ k)g(Stevenson)696 494 y(Carnegie)f(Mellon)h(University)512 610 y(Paulo)f(Gued\ es)112 b(Paul)13 b(Neves)1129 592 y fl(\003)1254 610 y fm(Paul)g(Roy)705 668 y (Open)f(Softwar)n(e)h(Foundation)789 807 y fk(November)f(6,)g(1991)905 1040 y fj(Abstract)235 1133 y fi(This)6 b(paper)g(reports)g(on)g(an)g(ongoing)f(proj\ ect)i(to)f(develop)f(a)i(general)e(understanding)g(of)i(the)f(problems)g(enco\ untered)179 1179 y(when)h(building)i(emulators)f(for)h(various)f(operating)g (systems)f(at)i(the)f(user)o(-level)h(on)f(top)g(of)h(a)g(Mach)e(3.0)i(micro-\ kernel,)179 1224 y(and)14 b(to)i(propose)d(a)i(common)f(framework)i(to)f(cons\ truct)g(emulations)f(for)i(a)f(wide)g(range)f(of)i(target)f(systems)e(and)179 1270 y(environments.)34 b(It)17 b(presents)e(an)h(overview)g(and)f(discussion) f(of)j(the)f(major)h(techniques)d(and)i(experiments)f(that)179 1316 y(charact\ erize)10 b(the)h(design)e(of)j(the)f(proposed)e(system.)19 b(Some)10 b(of)i (the)f(relevant)f(aspects)g(include)g(the)h(combination)f(of)179 1361 y(sever\ al)d(independent)e(servers)i(to)i(create)e(a)h(complete)f(system,)g(generic)g (service)g(interfaces)h(relying)g(on)f(the)h(emulation)179 1407 y(library)j (as)e(an)g(interface)h(translator)o(,)g(the)g(use)f(of)i(object-oriented)e (technology)f(to)i(de\256ne)f(standard)g(interfaces)g(and)g(to)179 1453 y(sim\ plify)g(the)e(implementation)h(of)h(common)e(facilities,)i(moving)f(portions) f(of)i(the)f(system)f(state)g(and)h(processing)e(from)179 1498 y(the)j(server\ s)g(into)h(a)f(smart)h(emulation)f(library)o(,)h(and)f(a)g(few)h(general-purp\ ose)d(facilities)k(that)f(simplify)g(the)g(generation)179 1544 y(of)e(a)f(com\ plete)g(system.)12 b(A)c(number)f(of)h(practical)g(observations)d(and)i(exper\ iences)e(are)j(also)f(presented,)g(in)h(the)f(context)179 1590 y(of)i(the)g (development)f(of)h(a)g(prototype)g(for)g(the)g(emulation)g(of)h(UNIX)f(4.3)g (BSD.)75 1754 y fh(1.)50 b(Intr)o(oduction)75 1888 y fg(De\256ning)13 b(and)h (standardizing)f(a)h(powerful)f(micro-kernel)g(base)i(is)e(only)g(the)h(\256r\ st)f(step)h(in)f(realizing)h(the)f(potential)f(of)75 1938 y(the)i(architectur\ e)h(proposed)f(with)f(the)i(overall)e(Mach)j(approach.)28 b(The)15 b(next)f (step,)i(and)f(perhaps)f(the)h(one)f(richest)h(in)75 1988 y(design)d(possibil\ ities,)g(is)h(to)f(learn)h(how)g(to)f(construct)g(a)i(wide)f(range)g(of)g(use\ ful)f(higher)n(-level)h(systems)h(on)e(top)g(of)h(this)75 2038 y(simple)i(ker\ nel.)29 b(A)15 b(particular)f(class)i(of)f(such)g(systems)g(is)g(the)g(so-cal\ led)g ff(emulation)e(systems)p fg(,)k(that)e(implement)f(the)75 2088 y(applic\ ation)e(programming)h(interface)g(of)g(an)h(existing)e(complete)i(operating)e (system)i(or)f ff(tar)n(get)g(system)h fg(with)f(various)75 2138 y(combinatio\ ns)g(of)h(user)o(-level)g(components)g(\(servers)h(and/or)e(libraries\))g(ope\ rating)h(on)f(top)h(of)g(a)h(Mach)f(kernel.)27 b(The)75 2187 y(emulation)11 b (system)i(provides)e(an)h ff(operating)e(system)j(envir)o(onment)e fg(for)h (a)g(number)g(of)g ff(emulated)f(pr)n(ocesses)p fg(,)k(such)d(that)75 2237 y (programs)f(executing)f(in)g(these)h(processes)h(can)g(operate)f(as)g(if)g (they)f(were)i(running)d(under)h(a)i(native)e(implementation)f(of)75 2287 y (the)f(tar)o(get)g(system.)15 b(The)9 b(main)f(bene\256ts)g(expected)h(from)f (this)f(overall)h(emulation)f(approach,)i(met)g(at)f(various)f(degrees)i(by) 75 2335 y 720 2 v 73 x fe(This)f(research)g(was)g(sponsored)e(in)i(part)g(by) g(The)g(Defense)f(Advanced)f(Research)h(Projects)i(Agency)n(,)d(Information)h (Science)h(and)g(T)n(echnology)d(Of)o(\256ce,)75 2447 y(under)h(the)h(title)h (\252Research)e(on)h(Parallel)h(Computing\272,)e(ARP)m(A)i(Order)f(No.)12 b (7330,)6 b(issued)h(by)f(DARP)m(A/CMO)i(under)e(Contract)h(MDS972-90-C-0035) 75 2487 y(and)g(in)h(part)f(by)g(the)h(Open)f(Software)g(Foundation)g(\(OSF\)\ .)i(The)e(views)h(and)f(conclusions)e(contained)h(in)i(this)g(document)e(are) h(those)g(of)h(the)f(authors)g(and)75 2526 y(should)g(not)h(be)f(interpreted) g(as)h(representing)f(the)h(of)o(\256cial)h(policies,)e(either)h(expressed)f (or)h(implied,)g(of)g(DARP)m(A,)h(OSF)m(,)h(or)e(the)f(U.S.)j(government.)117 2589 y fd(\003)135 2600 y fe(Paul)e(Neves)f(is)i(currently)e(with)h(the)g(Swi\ ss)h(Bank)f(Corporation)e(/)j(O'Connor)e(Assoc.)k(L.P)l(.,)g(Chicago)c(IL)75 2675 y(This)h(paper)f(will)i(appear)e(in)h(the)g(Proceedings)f(of)h(the)g(Sec\ ond)f(USENIX)i(Mach)e(Symposium,)g(Monterey)n(,)g(November)f(1991.)p eop %%Page: 2 2 bop 75 42 a fg(dif)n(ferent)10 b(system)g(architectures,)g(include)f(increas\ ed)h(modularity)l(,)g(portability)-6 b(,)10 b(\257exibility)-5 b(,)10 b(secur\ ity)f(and)h(extensibility)-5 b(,)75 91 y(as)11 b(well)f(as)h(simpler)f(develo\ pment,)g(debugging)f(and)h(maintenance.)137 183 y(W)o(ith)f(the)h(increasing) h(maturity)e(of)h(the)g(Mach)h(3.0)g(micro-kernel,)f(an)h(ever-growing)d(numb\ er)j(of)f(pure)g(and)h(applied)75 232 y(research)g(groups)e(are)h(now)f(under\ taking)f(to)h(design,)h(build)e(and)h(study)g(such)h(emulation)f(systems)h (for)f(a)h(range)g(of)f(tar)o(gets)75 282 y(that)d(span)h(from)g(relatively)e (simple)i(systems)g(like)g(MS-DOS)f(to)h(considerably)f(lar)o(ger)h(systems)g (such)g(as)g(VMS[8,)g(1,)g(11,)g(9].)75 332 y(All)i(these)i(systems)f(have)h (a)f(few)h(common)f(characteristics:)15 b(a)10 b(Mach)h(kernel,)f(one)g(or)g (more)g(servers,)i(and)e(an)g ff(emulation)75 382 y(library)k fg(associated)h (with)e(each)j(emulated)f(process,)h(that)e(intercepts)g(the)g(system)h(calls) g(issued)f(by)g(that)g(process)h(and)75 432 y(redirects)i(them)g(to)f(the)g (appropriate)g(emulation)g(services.)36 b(But)16 b(beyond)g(these)h(broad)f (similarities,)h(a)h(number)e(of)75 482 y(dif)n(ferent)9 b(approaches)i(are)f (taken.)k(Some)c(systems)g(use)g(a)g(single)e(monolithic)f(server)j(that)f (more-or)n(-less)h(reproduces)f(the)75 531 y(internal)h(structure)h(of)h(the) f(native)g(implementation)g(of)g(the)g(OS)h(being)f(emulated.)19 b(Others)12 b (attempt)f(to)g(decompose)h(the)75 581 y(functionality)5 b(of)i(the)g(single) g(native)g(kernel)h(into)e(several)i(independent)f(servers.)15 b(Still)6 b (others)h(follow)f(a)i(mixed)f(approach,)75 631 y(with)g(one)h(main)h(central) f(server)g(and)h(a)f(number)g(of)g(auxiliary)f(servers)i(implementing)e(speci\ \256c)i(portions)d(of)i(functionality)75 681 y(that)13 b(are)h(more)g(easily) g(or)f(usefully)g(separated.)26 b(Furthermore,)15 b(some)f(designs)f(attempt) g(to)g(keep)i(all)e(emulation)g(code)75 731 y(strictly)7 b(out)h(of)g(the)h (kernel,)g(while)f(others)g(de\256ne)h(various)f(controlled)f(mechanisms)j (to)e(assist)h(emulation)f(by)g(integrating)75 780 y(some)j(specialized)g(mod\ ules)f(into)f(the)h(protected)g(kernel)g(space.)137 872 y(In)15 b(general,)j (most)d(efforts)f(to)h(develop)g(emulation)g(systems)h(so)f(far)h(are)g(being) f(pursued)g(in)g(a)h(mostly)e(\252ad-hoc\272)75 922 y(fashion.)22 b(The)14 b (precise)f(or)o(ganization)f(of)g(the)h(interactions)e(between)j(the)e(compon\ ents)h(of)f(each)i(emulation)e(system)h(is)75 971 y(often)h(lar)o(gely)f(dete\ rmined)h(by)g(extrapolating)e(from)i(the)g(architecture)g(of)g(the)g(native)g (implementation)e(of)i(the)g(tar)o(get)75 1021 y(operating)d(system.)19 b(Mor\ eover)n(,)13 b(each)f(individual)e(component)h(is)g(typically)f(designed)i (speci\256cally)f(for)g(the)h(particular)75 1071 y(system)j(in)f(which)h(it)e (is)i(to)f(be)h(used,)h(and)f(implemented)g(either)f(entirely)g(from)g(scratc\ h)i(or)e(by)g(adapting)g(code)h(from)75 1121 y(the)c(native)f(OS)h(implementa\ tion.)16 b(However)o(,)11 b(it)f(appears)i(that)e(a)i(number)e(of)h(basic)g (design)g(and)g(or)o(ganizational)e(issues,)75 1171 y(and)j(even)g(the)f(spec\ i\256cation)h(of)f(some)h(high-level)e(functions,)h(are)h(in)f(fact)h(quite)f (similar)g(between)h(various)f(emulation)75 1220 y(systems)i(for)e(dif)o(fere\ nt)h(tar)o(gets.)21 b(In)12 b(response,)h(this)e(paper)i(reports)e(on)h(an)h (ongoing)d(ef)o(fort)i(to)f(take)i(a)f(broader)g(view)g(of)75 1270 y(the)d (problem)g(of)g(OS)h(emulation)e(in)h(general,)h(and)g(to)f(propose)f(a)i(com\ mon)g(framework)g(to)f(minimize)g(the)g(duplication)e(of)75 1320 y(effort)i (for)h(the)g(development)g(of)g(multiple)f(emulation)h(systems)h(for)f(the)g (widest)g(possible)g(range)h(of)f(tar)o(get)g(systems)h(and)75 1370 y(environ\ ments.)j(This)c(range)h(may)f(include)g(several)g(dif)o(ferent)g(\252traditio\ nal\272)e(operating)h(systems)i(\(UNIX,)f(VMS,)h(DOS,)75 1420 y(etc.\),)j(var\ ious)e(specialized)h(systems)g(or)f(con\256gurations)f(related)i(to)f(a)h(sin\ gle)f(main)g(tar)o(get,)i(or)e(even)h(completely)f(new)75 1469 y(programming) d(environments.)75 1634 y fh(2.)50 b(Appr)o(oach)12 b(and)g(Overview)75 1768 y fg(The)d(primary)f(focus)h(of)f(this)f(work)h(is)h(the)f(de\256nition)f(and)h (re\256nement)h(of)g(a)g(general-purpose)f(architecture)g(for)g(operating)75 1818 y(system)13 b(emulation.)22 b(This)13 b(design)f(is)g(not)g(directly)g (tied)g(to)g(the)h(emulation)f(of)g(any)h(particular)f(operating)g(system,)i (nor)75 1868 y(does)e(it)f(attempt)g(to)h(imitate)f(the)g(structure)h(of)f (any)h(particular)f(existing)f(operating)h(system)h(implementation.)19 b(Inst\ ead,)75 1918 y(this)13 b(work)g(attempts)h(to)f(take)h(an)g(original)e(look)h (at)h(the)f(problems)h(and)g(opportunities)d(presented)j(by)f(a)i(micro-kerne\ l)75 1968 y(architecture)i(for)g(emulation,)h(and)f(to)g(develop)f(a)i(global) e(understanding)f(of)i(the)g(pertinent)f(design)g(trade-of)o(fs.)36 b(It)75 2017 y(concentrates)18 b(on)f(identifying)e(common)j(issues)g(and)f(proposing) f(general)i(solutions)d(or)i(practical)h(mechanisms)h(to)75 2067 y(address)10 b(them.)k(The)c(main)f(challenge)g(is)g(to)f(de\256ne)i(such)f(a)h(general)f (architecture)g(so)g(that)f(the)h(resulting)e(systems)j(remain)75 2117 y(prac\ tical)g(and)f(competitive)g(when)h(compared)g(with)f(traditional)e(monolithic) h(kernel-based)h(architectures,)i(particularly)75 2167 y(in)f(the)g(areas)h (of)f(simplicity)f(of)h(implementation,)f(robustness)h(and,)g(of)g(course,)i (performance.)137 2258 y(T)n(o)f(provide)f(a)i(concrete)g(environment)e(in)h (which)g(to)g(evaluate)g(the)h(design,)f(we)h(are)g(implementing)e(a)i(protot\ ype)d(of)75 2308 y(a)j(complete)g(emulation)e(system)i(for)f(UNIX)g(4.3)h(BSD\ ,)g(often)e(referred)i(to)f(as)h(the)g(\252Mach)g(3.0)f(multi-server)g(emulat\ ion)75 2358 y(system\272.)38 b(However)o(,)20 b(this)c(particular)h(prototype) f(is)i(not)e(intended)h(to)g(be)h(the)f(major)h(or)f(single)g(\256nal)h(produ\ ct)e(of)75 2408 y(this)e(work.)29 b(Rather)n(,)17 b(it)d(is)h(used)g(as)h(a)f (vehicle)g(with)f(which)h(to)f(test)h(general)g(ideas)h(about)e(the)h(system) g(or)o(ganization)75 2457 y(and)f(to)f(experiment)h(with)f(particular)g(imple\ mentations)g(of)g(these)i(ideas.)26 b(The)15 b(overall)e(development)g(of)h (the)g(design)75 2507 y(proceeds)g(through)d(successive)j(re\256nements)g(of) f(the)g(prototype,)f(such)h(that)f(each)i(consecutive)g(version)e(constitutes) g(a)75 2557 y(new)f(working)e(emulation)h(environment)g(with)g(better)g(chara\ cteristics)h(than)g(the)f(one)h(preceding)g(it,)f(while)g(allowing)f(all)75 2607 y(design)g(decisions)h(to)f(be)h(reconsidered)g(at)g(each)h(stage)g(in)e (light)f(of)h(the)h(experiences)h(accumulated)g(during)d(this)h(process.)75 2657 y(The)j(\252\256nal\272)h(prototype)d(after)i(the)f(design)h(and)g(evalu\ ation)e(are)j(complete)f(might)f(then)g(be)h(used)g(as)h(a)f(basis)g(for)f (further)965 2804 y(2)p eop %%Page: 3 3 bop 75 42 a fg(engineering)8 b(work)g(to)g(construct)f(a)i(production-qualit\ y)c(system)k(for)f(BSD)g(emulation,)h(or)f(for)g(other)g(UNIX)g(emulations.) 137 133 y(The)k(overall)e(architecture)h(is)g(shown)f(on)h(\256gure)f(1.)17 b (The)12 b(major)f(elements)g(in)g(this)f(architecture)h(are)g(the)g(kernel,)g (the)75 183 y(emulated)g(processes,)g(and)g(a)g(collection)e(of)h(servers.)75 1659 y @beginspecial 55 @vscale 55 @hscale 90 @angle 435 @hoffset @setspecial %%BeginDocument: main-architecture.ps /__NXdef{1 index where{pop pop pop}{def}ifelse}bind def /__NXbdef{1 index where{pop pop pop}{bind def}ifelse}bind def /UserObjects 10 array __NXdef /defineuserobject{ exch dup 1 add dup UserObjects length gt{ array dup 0 UserObjects putinterval /UserObjects exch def }{pop}ifelse UserObjects exch 3 -1 roll put }__NXbdef /undefineuserobject{UserObjects exch null put}__NXbdef /execuserobject{UserObjects exch get exec}__NXbdef /__NXRectPath{4 2 roll moveto 1 index 0 rlineto 0 exch rlineto neg 0 rlineto closepath}__NXbdef /__NXProcessRectArgs{ 1 index type /arraytype eq{ exch 0 4 2 index length 1 sub{ dup 3 add 1 exch{1 index exch get exch}for 5 1 roll 5 index exec }for pop pop }{exec}ifelse }__NXbdef /rectfill{gsave newpath {__NXRectPath fill} __NXProcessRectArgs grestore}__NXbdef /rectclip{newpath {__NXRectPath} __NXProcessRectArgs clip newpath}__NXbdef /rectstroke{ gsave newpath dup type /arraytype eq{dup length 6 eq}{false}ifelse{ {gsave __NXRectPath null concat stroke grestore} dup length array cvx copy dup 2 4 -1 roll put __NXProcessRectArgs }{{__NXRectPath stroke} __NXProcessRectArgs}ifelse grestore }__NXbdef /xyshow{ 0 1 3 index length 1 sub{ currentpoint 4 index 3 index 1 getinterval show 3 index 3 index 2 mul 1 add get add exch 3 index 3 index 2 mul get add exch moveto pop }for pop pop }__NXbdef /xshow{ 0 1 3 index length 1 sub{ currentpoint 4 index 3 index 1 getinterval show exch 3 index 3 index get add exch moveto pop }for pop pop }__NXbdef /yshow{ 0 1 3 index length 1 sub{ currentpoint 4 index 3 index 1 getinterval show 3 index 3 index get add moveto pop }for pop pop }__NXbdef /arct{arcto pop pop pop pop}__NXbdef /setbbox{pop pop pop pop}__NXbdef /ucache{}__NXbdef /ucachestatus{mark 0 0 0 0 0}__NXbdef /setucacheparams{cleartomark}__NXbdef /uappend{systemdict begin cvx exec end}__NXbdef /ueofill{gsave newpath uappend eofill grestore}__NXbdef /ufill{gsave newpath uappend fill grestore}__NXbdef /ustroke{ gsave newpath dup length 6 eq {exch uappend concat}{uappend}ifelse stroke grestore }__NXbdef /__NXustrokepathMatrix dup where {pop pop}{matrix def}ifelse /ustrokepath{ newpath dup length 6 eq{ exch uappend __NXustrokepathMatrix currentmatrix exch concat strokepath setmatrix }{uappend strokepath}ifelse } __NXbdef /upath{ [exch {/ucache cvx}if pathbbox /setbbox cvx {/moveto cvx}{/lineto cvx}{/curveto cvx}{/closepath cvx}pathforall]cvx } __NXbdef /setstrokeadjust{pop}__NXbdef /currentstrokeadjust{false}__NXbdef /selectfont{exch findfont exch dup type /arraytype eq {makefont}{scalefont}ifelse setfont}__NXbdef /_NXCombineArrays{ counttomark dup 2 add index dup length 3 -1 roll { 2 index length sub dup 4 1 roll 1 index exch 4 -1 roll putinterval exch }repeat pop pop pop }__NXbdef /setcmykcolor{ 1.0 exch sub dup dup 6 -1 roll sub dup 0 lt{pop 0}if 5 1 roll 4 -1 roll sub dup 0 lt{pop 0}if 3 1 roll exch sub dup 0 lt{pop 0}if setrgbcolor }__NXbdef /currentcmykcolor{currentrgbcolor 3{1.0 exch sub 3 1 roll}repeat 0}__NXbdef /flushgraphics{}def /setwindowtype{pop pop}def /currentwindowtype{pop 0}def /setalpha{pop}def /currentalpha{1.0}def /hidecursor{}def /obscurecursor{}def /revealcursor{}def /setcursor{4 {pop}repeat}bind def /showcursor{}def /NextStepEncoding where not{ /NextStepEncoding StandardEncoding 256 array copy def 0 [129/Agrave/Aacute/Acircumflex/Atilde/Adieresis/Aring/Ccedilla/Egrave /Eacute/Ecircumflex/Edieresis/Igrave/Iacute/Icircumflex/Idieresis /Eth/Ntilde/Ograve/Oacute/Ocircumflex/Otilde/Odieresis/Ugrave/Uacute /Ucircumflex/Udieresis/Yacute/Thorn/mu/multiply/divide/copyright 176/registered 181/brokenbar 190/logicalnot 192/onesuperior 201/twosuperior 204/threesuperior 209/plusminus/onequarter/onehalf/threequarters/agrave /aacute/acircumflex/atilde/adieresis/aring/ccedilla/egrave/eacute /ecircumflex/edieresis/igrave 226/iacute 228/icircumflex/idieresis/eth /ntilde 236/ograve/oacute/ocircumflex/otilde/odieresis 242/ugrave/uacute /ucircumflex 246/udieresis/yacute 252/thorn/ydieresis] {dup type /nametype eq {NextStepEncoding 2 index 2 index put pop 1 add}{exch pop}ifelse }forall pop /NextStepEncoding NextStepEncoding readonly def /_NXfstr 128 string dup 0 (_NX) putinterval def /findfont{ % Because we can never let NextStepEncoding get into % SharedFontDirectory, we cannot reencode a font to NextStepEncoding % if we are in shared mode. So if currentshared is true, % we call the normal findfont and return that /currentshared where {pop currentshared} {false} ifelse {//findfont exec} {dup _NXfstr 3 125 getinterval cvs length 3 add _NXfstr 0 3 -1 roll getinterval cvn exch FontDirectory 2 index known {pop FontDirectory exch get} {//findfont exec dup /Encoding get StandardEncoding eq { dup length dict exch {1 index /FID ne {2 index 3 1 roll put}{pop pop}ifelse}forall dup /Encoding NextStepEncoding put definefont }{exch pop} ifelse }ifelse }ifelse }bind def }{pop}ifelse /_NXProcArray 5 array __NXdef /_NXChannels 0 __NXdef /_NXTotalBytes 0 __NXdef /_NXDoImageOp{ 1 index{dup}{1}ifelse /_NXChannels exch store _NXChannels 2 add 2 roll _NXProcArray 0 _NXChannels getinterval astore pop 5 index 4 index mul 2 index{1 sub 8 idiv 1 add mul}{mul 1 sub 8 idiv 1 add}ifelse 4 index mul /_NXTotalBytes exch store pop exch pop gsave matrix invertmatrix concat 0.5 setgray 0 0 4 2 roll rectfill grestore { 0 1 _NXChannels 1 sub{ _NXProcArray exch get exec length _NXTotalBytes exch sub /_NXTotalBytes exch store}for _NXTotalBytes 0 le{exit}if }loop /_NXProcArray 5 array def }__NXbdef /colorimage{_NXDoImageOp}__NXbdef /alphaimage{1 add _NXDoImageOp}def /landscape false def /t300 [0.000 0.006 0.011 0.017 0.022 0.028 0.033 0.039 0.045 0.050 0.056 0.061 0.067 0.073 0.078 0.084 0.089 0.095 0.101 0.117 0.133 0.148 0.164 0.179 0.195 0.210 0.225 0.240 0.255 0.270 0.285 0.299 0.314 0.329 0.344 0.359 0.374 0.389 0.404 0.419 0.435 0.451 0.466 0.482 0.498 0.513 0.529 0.544 0.560 0.576 0.591 0.610 0.632 0.654 0.677 0.699 0.721 0.744 0.766 0.788 0.821 0.866 0.911 0.955 1.000 ] def /t400 [0.000 0.003 0.006 0.009 0.012 0.014 0.017 0.020 0.023 0.026 0.029 0.032 0.035 0.038 0.041 0.043 0.046 0.049 0.056 0.063 0.071 0.079 0.087 0.095 0.104 0.117 0.130 0.143 0.157 0.173 0.189 0.205 0.225 0.245 0.259 0.272 0.285 0.298 0.314 0.329 0.345 0.361 0.376 0.392 0.407 0.423 0.439 0.454 0.470 0.486 0.502 0.528 0.554 0.580 0.605 0.628 0.650 0.672 0.695 0.727 0.762 0.796 0.857 0.922 1.000 ] def /tlinear [0.000 0.016 0.031 0.047 0.062 0.078 0.094 0.109 0.125 0.141 0.156 0.172 0.188 0.203 0.219 0.234 0.250 0.266 0.281 0.297 0.312 0.328 0.344 0.359 0.375 0.391 0.406 0.422 0.438 0.453 0.469 0.484 0.500 0.516 0.531 0.547 0.562 0.578 0.594 0.609 0.625 0.641 0.656 0.672 0.688 0.703 0.719 0.734 0.750 0.766 0.781 0.797 0.812 0.828 0.844 0.859 0.875 0.891 0.906 0.922 0.938 0.953 0.969 0.984 1.000 ] def /dmatrix matrix def /desiredpat 0 def /dpi 72 0 dmatrix defaultmatrix dtransform dup mul exch dup mul add sqrt round def /freq dpi 18.75 div 8 div round dup 0 eq { pop 1 } if 8 mul dpi exch div def /sangle 1 0 dmatrix defaultmatrix dtransform exch atan def /graymode true def /pats 16 array def /mymatrix matrix def /savedgray 0 def /F /fill load def /rc /rectclip load def /GS /gsave load def /GR /grestore load def /SL /setlinewidth load def /SC /setlinecap load def /CS { closepath S } bind def /A /strokepath load def /TR /translate load def /M /moveto load def /C /closepath load def /smat { mymatrix currentmatrix pop } bind def /rmat { mymatrix setmatrix } bind def /sp { P exch get exec } bind def systemdict /setshared known { 300 dpi eq { /tran t300 def } { /tran t400 def } ifelse } { /tran tlinear def } ifelse systemdict /xshow known not { /xhow { /pts exch def /str exch def 0 1 str length 1 sub { currentpoint 3 -1 roll str 1 index 1 getinterval show 3 1 roll moveto pts exch get 0 rmoveto } for } bind def } { /xhow { checkink xshow } bind def } ifelse systemdict /xyshow known not { /xyhow { /pts exch def /str exch def 0 1 str length 1 sub { currentpoint 3 -1 roll str 1 index 1 getinterval show 3 1 roll moveto 2 mul pts 1 index get pts 3 -1 roll 1 add get rmoveto } for } bind def } { /xyhow { checkink xyshow } bind def } ifelse /PrintInColor systemdict /colorimage known def PrintInColor { /HUE 0 def /SAT 0 def /BRIGHT 0 def /Colors [[0 0 ] [0 0 ] [0.00 1.0] [0.37 1.0] [0.60 1.0] [0.50 1.0] [0.83 1.0] [0.16 1.0] ] def /K { Colors exch get dup 0 get /HUE exch store 1 get /BRIGHT exch store HUE 0 eq BRIGHT 0 eq and {1.0 SAT sub setgray } {HUE SAT BRIGHT sethsbcolor } ifelse } def /mysetgray { /SAT exch 1.0 exch sub store HUE 0 eq BRIGHT 0 eq and {1.0 SAT sub setgray } {HUE SAT BRIGHT sethsbcolor } ifelse } bind def } { /mysetgray /setgray load def /K /pop load def } ifelse /setpattern { /bwidth exch def /bpside exch def /bstring exch def /onbits 0 def /offbits 0 def freq sangle landscape {90 add} if {/y exch def /x exch def /xindex x 1 add 2 div bpside mul cvi def /yindex y 1 add 2 div bpside mul cvi def bstring yindex bwidth mul xindex 8 idiv add get 1 7 xindex 8 mod sub bitshift and 0 ne {/onbits onbits 1 add def 1} {/offbits offbits 1 add def 0} ifelse } setscreen tran offbits 64 mul offbits onbits add div cvi get mysetgray } bind def /myfonts [] def /procarray 30 array def 3.86 setmiterlimit currentscreen cvlit /orgproc exch def /organgle exch def /orgfreq exch def /currentpat -1 def /checkpat { graymode currentpat desiredpat ne or { pats desiredpat get exec /graymode false store /currentpat desiredpat store } if } bind def /Z { checkpat fill } bind def /checkink { graymode not { orgfreq organgle orgproc cvx setscreen /graymode true store savedgray mysetgray } if } bind def /F { checkink fill } bind def /dorectfill { checkink rectfill } bind def /dorectstroke { checkink rectstroke } bind def /S { checkink stroke } bind def /G { /savedgray exch def savedgray mysetgray } def /makecontextpattern { exch pop [null 8 1 /setpattern cvx] 4 array copy dup 0 5 -1 roll put cvx pats 3 1 roll put } def /P [ 0 1 15 { [ /desiredpat 3 -1 roll /store cvx ] cvx } for ] def /patoffsetx 0 def /patoffsety 0 def /currentpat null def /DiacriticEncoding [ /.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 /quotesingle /parenleft /parenright /asterisk /plus /comma /hyphen /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 /grave /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 /Adieresis /Aring /Ccedilla /Eacute /Ntilde /Odieresis /Udieresis /aacute /agrave /acircumflex /adieresis /atilde /aring /ccedilla /eacute /egrave /ecircumflex /edieresis /iacute /igrave /icircumflex /idieresis /ntilde /oacute /ograve /ocircumflex /odieresis /otilde /uacute /ugrave /ucircumflex /udieresis /dagger /.notdef /cent /sterling /section /bullet /paragraph /germandbls /registered /copyright /trademark /acute /dieresis /.notdef /AE /Oslash /.notdef /.notdef /.notdef /.notdef /yen /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /ordfeminine /ordmasculine /.notdef /ae /oslash /questiondown /exclamdown /logicalnot /.notdef /florin /.notdef /.notdef /guillemotleft /guillemotright /ellipsis /.notdef /Agrave /Atilde /Otilde /OE /oe /endash /emdash /quotedblleft /quotedblright /quoteleft /quoteright /.notdef /.notdef /ydieresis /Ydieresis /fraction /currency /guilsinglleft /guilsinglright /fi /fl /daggerdbl /periodcentered /quotesinglbase /quotedblbase /perthousand /Acircumflex /Ecircumflex /Aacute /Edieresis /Egrave /Iacute /Icircumflex /Idieresis /Igrave /Oacute /Ocircumflex /.notdef /Ograve /Uacute /Ucircumflex /Ugrave /dotlessi /circumflex /tilde /macron /breve /dotaccent /ring /cedilla /hungarumlaut /ogonek /caron ] def /DiacriticEncode { /basefontdict exch def /newfontdict basefontdict maxlength 2 add dict def basefontdict {exch dup /FID ne {dup /Encoding eq {exch pop DiacriticEncoding } {exch} ifelse newfontdict 3 1 roll put } {pop pop} ifelse } forall newfontdict } def /line { pop pop pop pop } def /rrectpath { smat 4 2 roll TR /h exch def /w exch def /r exch def mark r 0 M w 0 w h r arcto w h 0 h r arcto 0 h 0 0 r arcto 0 0 w 0 r arcto C cleartomark rmat } def /RF { rrectpath F } bind def /RP { checkpat rrectpath fill } bind def /RS { rrectpath S } bind def /RQ { checkpat rrectpath A fill } bind def /NF { dorectfill } bind def /NR { checkpat 4 2 roll rectfill } bind def /W { savedgray 5 1 roll 1.0 G dorectfill G } bind def /invertbox { pop pop pop pop } def /highbox { pop pop pop pop } def /PP { newpath 3 1 roll M 1 sub { lineto } repeat } bind def /SP { 3 1 roll M 3 div cvi { curveto } repeat } bind def /rectpath { M dup 0 exch rlineto exch 0 rlineto neg 0 exch rlineto C } def /N { dorectstroke } bind def /NQ { checkpat 4 2 roll rectstroke } bind def /drawip { pop pop pop } bind def /eraseip { pop pop pop } bind def /highip { pop pop pop pop } def /insideedgebox { pop pop pop pop pop } def /replbox { pop pop pop pop pop pop } def /pop4 { pop pop pop pop } def /graybox { pop4 } def /darkgraybox { pop4 } def /arcpath { newpath TR /h exch def /w exch def /dth exch def /th exch def 90 th dth add sub 90 th sub dth 0 lt { exch } if 1 h w div neg scale 0 0 w 2 div 5 -2 roll arc } def /AS { smat arcpath rmat S } bind def /AP { checkpat smat arcpath rmat A fill } bind def /AF { smat arcpath 0 0 lineto rmat F } bind def /AQ { checkpat smat arcpath 0 0 lineto rmat fill } bind def /mymakefont { /size exch def /name exch def /i exch def /myfontdict name cvn findfont def myfontdict /Encoding get dup StandardEncoding eq exch /NextStepEncoding where { pop NextStepEncoding eq or }{ pop } ifelse { myfontdict DiacriticEncode /gfontdict exch def /gfontdict (F ) dup 1 i ( ) cvs putinterval cvn gfontdict definefont def } { /gfontdict myfontdict def } ifelse /myfonts [ myfonts aload pop null ] def myfonts i gfontdict [size 0 0 size neg 0 0 ] makefont put } def /FF { myfonts exch get setfont } bind def /CR { initclip newpath 4 2 roll M dup 0 exch rlineto exch 0 rlineto 0 exch neg rlineto C clip newpath } bind def /cliptowindow { initclip } def /beginprintcode { GS newpath 1 setlinewidth 0 SL 0 setlinejoin [] 0 setdash 0 setgray 10 setmiterlimit /FMdicttop countdictstack 1 add def /FMoptop count 7 sub def 200 dict begin TR dup neg scale 0.0 0.0 M } def /endprintcode { count -1 FMoptop {pop pop} for countdictstack -1 FMdicttop {pop end} for GR } def /beginPSInsetprintcode { /pinsetsave save def newpath 1 setlinewidth 0 setlinecap 0 setlinejoin [] 0 setdash 0 setgray 10 setmiterlimit /showpage {} def /FMdicttop countdictstack 1 add def /FMoptop count def 200 dict begin /showimage {} def } def /endPSInsetprintcode { count -1 FMoptop {pop pop} for countdictstack -1 FMdicttop {pop end} for pinsetsave restore } def /cacheimage { /flip exch def /theta exch def /bps exch def /h exch def /w exch def /destHeight exch def /destWidth exch def /destY exch def /destX exch def /rowbytes w bps mul 7 add 8 idiv def /buffer rowbytes string def GS destX destY TR theta rotate flip {destWidth neg destHeight scale} {destWidth destHeight scale} ifelse w h bps [w 0 0 h 0 h ] { currentfile buffer readhexstring pop } bind image GR } def <0f1e3c78f0e1c387> (I17a658) 8 makecontextpattern <0f87c3e1f0783c1e> (I17a674) 9 makecontextpattern (I17a690) 10 makecontextpattern (I17a6ac) 11 makecontextpattern <8142241818244281> (I17a6c8) 12 makecontextpattern <03060c183060c081> (I17a6e4) 13 makecontextpattern <8040201008040201> (I17a700) 14 makecontextpattern gsave -1 -9 translate /__NXbasematrix matrix currentmatrix def grestore /__NXsheetsavetoken save def -90 rotate -792 0 translate 0 0 translate gsave /__NXbasematrix matrix currentmatrix def grestore gsave 0 0 792 612 rectclip [1 0 0 -1 0 612] concat 0 0 translate gsave 0 0 792 612 rectclip /landscape true def 0 0 792 612 CR 1 G 72 36 648 10 NF 0 G 0 (Times-Roman) 10 mymakefont 0 FF 72 42.67 M ( ) [0 ] xhow 1 G 72 569.333374 648 10 NF 0 G 72 576 M ( ) [0 ] xhow 0.5 SL 3.86 setmiterlimit 2 SC 14 sp 774 594 9 9 NQ 3 SL 0 SC 233.501938 516.348389 522 63 N 242.501938 372.348358 144 108 N 422.501953 372.348358 144 108 N 602.501953 372.348358 144 108 N 261.510376 59.36467 162 243 N 2 SL 0.5 G 269.501953 66.348358 144 99 N 270.582367 183.348358 144 92.232285 N 3 SL 0 G 566.501953 57.348358 162 245.016312 N 2 SL 0.5 G 575.501953 66.348358 144 99 N 575.501953 183.348358 144 92.232285 N 0 G 0 360 9 9 289.55426 275.544647 AS 0 360 9 9 334.266296 275.616638 AS 0 360 9 9 311.946259 275.616638 AS 0 360 9 9 392.29834 275.616638 AS 0 360 9 9 593.106567 275.616638 AS 0 360 9 9 615.426575 275.616638 AS 0 360 9 9 695.778687 275.616638 AS 0 360 9 9 271.770203 400.536774 AS 0 360 9 9 718.098694 400.536774 AS 0 360 9 9 294.01825 400.608765 AS 0 360 9 9 691.386658 400.536774 AS 0 360 9 9 450.330383 400.608765 AS 0 360 9 9 472.650421 400.608765 AS 0 360 9 9 494.970459 400.536774 AS 276.74 389.86 271.73 396.1 268.83 388.64 272.79 389.25 4 PP F 289.59 280.04 272.8 389.26 2 PP 0.5 SL S 443.21 388.53 445.81 396.09 437.96 394.57 440.58 391.55 4 PP F 311.91 280.04 440.6 391.56 2 PP S 469.88 388.57 472.6 396.09 464.72 394.69 467.3 391.63 4 PP F 334.23 280.04 467.32 391.64 2 PP S 681.89 389.82 686.86 396.09 678.94 397.26 680.42 393.54 4 PP F 392.26 280.04 680.45 393.56 2 PP S 720.72 388.53 718.11 396.1 712.86 390.06 716.79 389.3 4 PP F 695.81 280.04 716.81 389.31 2 PP S 306.42 397.26 298.51 396.09 303.47 389.82 304.95 393.54 4 PP F 593.14 280.04 304.96 393.56 2 PP S 484.94 394.69 477.06 396.09 479.78 388.57 482.36 391.63 4 PP F 615.46 280.04 482.38 391.64 2 PP S 1 (Times-Bold) 24 mymakefont 1 FF 280.66 51.93 M (Process A) [14.66 10.65 11.99 10.65 10.65 9.33 9.33 6 0 ] xhow 587.63 51.93 M (Process B) [14.66 10.65 11.99 10.65 10.65 9.33 9.33 6 0 ] xhow 422.19 565.29 M (Mach Kernel) [22.64 11.99 10.65 13.34 6 18.66 10.65 10.65 13.34 10.65 0 ] xhow 2 (Times-Roman) 18 mymakefont 2 FF 277.59 444.11 M (TTY server) [10.99 10.99 12.99 4.5 7 7.99 5.99 9 7.99 0 ] xhow 458.67 445.21 M (File server) [10 5 5 7.99 4.5 7 7.99 5.99 9 7.99 0 ] xhow 614.59 445.77 M (Process manager) [10 5.99 9 7.99 7.99 7 7 4.5 14 7.99 9 7.99 9 7.99 0 ] xhow 306.44 100.38 M (User code) [12.99 7 7.99 5.99 4.5 7.99 9 9 0 ] xhow 614.46 100.38 M (User code) [12.99 7 7.99 5.99 4.5 7.99 9 9 0 ] xhow 311.89 222.57 M (Emul. lib) [10.99 14 9 5 4.5 4.5 5 5 0 ] xhow 615.45 222.57 M (Emul. lib) [10.99 14 9 5 4.5 4.5 5 5 0 ] xhow 155.67 579.13 231.56 579.13 2 PP 1 SL S 155.67 498.78 240.49 498.78 2 PP S 155.67 275.58 262.81 275.58 2 PP S 262.81 172.91 155.67 172.91 2 PP S 262.81 56.84 155.67 56.84 2 PP S 162.06 68.97 169.06 56.84 176.06 68.97 169.06 68.97 4 PP 0.5 G F 176.06 160.78 169.06 172.91 162.06 160.78 169.06 160.78 4 PP F 169.06 68.97 169.06 160.78 2 PP 3 SL S 162.06 189.5 169.06 177.37 176.06 189.5 169.06 189.5 4 PP F 176.06 263.46 169.06 275.58 162.06 263.46 169.06 263.46 4 PP F 169.06 189.5 169.06 263.46 2 PP S 162.06 287.7 169.06 275.58 176.06 287.7 169.06 287.7 4 PP F 176.06 486.66 169.06 498.78 162.06 486.66 169.06 486.66 4 PP F 169.06 287.7 169.06 486.66 2 PP S 162.06 510.91 169.06 498.78 176.06 510.91 169.06 510.91 4 PP F 176.06 567.01 169.06 579.13 162.06 567.01 169.06 567.01 4 PP F 169.06 510.91 169.06 567.01 2 PP S 0 G 1 FF 40.18 118.89 M (Application) [17.32 13.34 13.34 6.67 6.67 10.65 11.99 7.99 6.67 11.99 0 ] xhow 52.17 230.49 M (Emulation) [16 19.98 13.34 6.67 11.99 7.99 6.67 11.99 0 ] xhow 85.54 390 M (Service) [13.34 10.65 10.65 11.99 6.67 10.65 0 ] xhow 93.98 541.78 M (Kernel) [18.66 10.65 10.65 13.34 10.65 0 ] xhow 334.16 161.71 343.16 146.12 352.16 161.71 343.16 161.71 4 PP 0.666 G F 352.16 188.57 343.16 204.16 334.16 188.57 343.16 188.57 4 PP F 343.16 161.71 343.16 188.57 2 PP 5 SL S 642.17 161.71 651.17 146.12 660.17 161.71 651.17 161.71 4 PP F 660.17 188.57 651.17 204.16 642.17 188.57 651.17 188.57 4 PP F 651.17 161.71 651.17 188.57 2 PP S 302.91 474.19 311.91 458.6 320.91 474.19 311.91 474.19 4 PP F 320.91 523.37 311.91 538.96 302.91 523.37 311.91 523.37 4 PP F 311.91 474.19 311.91 523.37 2 PP S 485.93 474.19 494.93 458.6 503.93 474.19 494.93 474.19 4 PP F 503.93 523.37 494.93 538.96 485.93 523.37 494.93 523.37 4 PP F 494.93 474.19 494.93 523.37 2 PP S 664.49 474.19 673.49 458.6 682.49 474.19 673.49 474.19 4 PP F 682.49 523.37 673.49 538.96 664.49 523.37 673.49 523.37 4 PP F 673.49 474.19 673.49 523.37 2 PP S grestore grestore showpage __NXsheetsavetoken restore %%EndDocument @endspecial 654 1729 a(Figure)g(1:)15 b(Overall)9 b(System)i(Architecture) 137 1828 y(The)f(kernel)g(is)f(the)h(\252pure\272)g(Mach)g(kernel,)g(exportin\ g)e(only)g(the)h(basic)h(Mach)h(primitives.)i(It)c(is)g(completely)g(general,) 75 1878 y(and)j(contains)f(no)h(code)g(speci\256c)h(to)f(any)g(emulation)f (system.)20 b(This)12 b(decision)g(is)f(intended)g(to)h(maximize)h(security)e (and)75 1928 y(fault)e(isolation.)137 2019 y(Each)14 b(emulated)g(process)f (is)g(implemented)g(in)g(a)g(separate)h(Mach)g(task)f(that)g(contains)f(the)h (unmodi\256ed)f(user)i(code)75 2069 y(from)i(various)f(application)g(programs) h(and)g(an)h(emulation)e(library)g(that)h(intercepts)f(and)h(implements)g(sys\ tem)h(calls)75 2119 y(issued)10 b(by)h(instructions)d(embedded)j(in)f(the)g (user)h(code.)17 b(Although)8 b(both)i(of)g(these)h(regions)e(of)i(code)g(res\ ide)f(in)g(the)h(same)75 2169 y(address)f(space,)i(we)e(often)f(refer)h(to)f (the)h(circumstances)h(when)e(a)h(thread)g(is)f(executing)g(user)h(code)h(as) f(\252executing)f(in)h ff(user)75 2218 y(space)p fg(\272,)h(and)g(when)f(a)g (thread)g(is)g(executing)f(code)i(in)e(the)h(emulation)f(library)g(as)i(\252e\ xecuting)f(in)f ff(emulation)f(space)p fg(\272.)16 b(The)75 2268 y(emulation) 9 b(library)g(is)i(relatively)e(lar)o(ge;)h(it)f(manages)j(a)f(considerable)f (portion)e(of)i(the)g(process)h(state)g(and)f(the)g(emulation)75 2318 y(funct\ ions)f(locally)l(.)137 2409 y(The)k(rest)g(of)f(the)g(functionality)d(of)j (the)g(emulation)g(system,)h(that)f(is)g(not)f(handled)h(in)g(the)g(emulation) g(library)f(itself,)75 2459 y(is)j(distributed)f(among)h(a)h(\252federation\ \272)g(of)f(servers)h(each)h(operating)e(in)f(a)j(separate)f(Mach)g(task.)28 b (These)16 b(servers)f(are)75 2509 y(independent)c(of)h(each)h(other)f(and)g (can)h(be)f(replaced)h(or)f(re-con\256gured)f(at)i(will,)e(to)h(provide)f(for) g(maximum)i(\257exibility)-5 b(.)75 2559 y(Examples)9 b(of)f(servers)i(in)d (the)i(BSD)f(prototype)f(include)g(\256le)i(servers,)h(a)f(process)g(manager) o(,)h(a)f(TTY)g(server)o(,)g(a)g(pipe/socket)75 2609 y(server)o(,)i(etc.)137 2700 y(The)g(primary)f(mode)g(of)g(communication)f(between)i(components)f(in) f(the)h(system)g(is)g(the)g(Mach)h(IPC)f(facility)l(.)15 b(Every)965 2804 y (3)p eop %%Page: 4 4 bop 75 42 a fg(individual)11 b(UNIX)i(abstraction)f(\(\256les,)j(sockets,)g (pipes,)f(etc.\))24 b(in)13 b(every)h(server)g(is)f(represented)g(by)g(a)h (separate)g(Mach)75 91 y(port.)21 b(However)o(,)13 b(Mach)h(shared)f(memory)g (may)g(also)f(be)h(used)g(in)f(client-server)g(interactions)g(when)g(appropri\ ate:)19 b(for)75 141 y(example,)11 b(\256le)g(data)f(is)g(typically)f(mapped) i(directly)e(into)g(the)h(address)h(space)h(of)e(each)h(client)f(for)f(fast)i (I/O)e(access.)137 232 y(Finally)l(,)k(to)f(maximize)g(the)g(potential)f(for) g(building)f(dif)n(ferent)i(con\256gurations)f(or)h(collections)f(of)g(server\ s,)j(as)f(well)75 282 y(as)j(to)e(minimize)i(communication)e(overheads,)j(the) e(emulation)g(libraries)f(communicate)i(directly)e(with)g(each)j(server)75 332 y(whenever)10 b(needed)h(without)c(any)j(central)g(coordinating)e(agent)i(or) f(server)n(.)15 b(As)10 b(a)h(consequence,)g(the)f(state)g(of)f(the)h(system) 75 382 y(is)d(ef)o(fectively)g(distributed)e(among)i(the)g(various)f(servers) i(and)f(emulation)f(libraries)g(operating)g(in)h(each)h(emulated)f(process.) 137 473 y(The)14 b(following)d(sections)i(elaborate)g(on)g(the)g(main)g(techn\ ical)g(aspects)h(of)f(this)f(or)o(ganization)g(and)h(the)g(basic)h(ideas)75 523 y(and)9 b(experiments)g(that)f(we)i(are)g(evaluating,)e(along)h(with)f (a)h(number)g(of)g(our)f(concerns)i(and)f(experiences)h(with)e(the)h(design) 75 573 y(and)h(the)g(current)g(prototype.)75 738 y fh(3.)50 b(Major)12 b(Desi\ gn)h(Considerations)e(and)h(Experiences)75 880 y(3.1.)51 b(Generic)12 b(Servi\ ce)g(Layer)75 999 y fg(A)7 b(\256rst)h(key)f(idea)h(underlying)d(the)i(design) g(is)g(the)h(de\256nition)d(of)i(two)g(separate)i(functional)c(layers)j(in)f (the)g(emulation)g(system)75 1049 y(architecture,)15 b(corresponding)d(to)g (generic)i(and)f(tar)o(get-speci\256c)h(functions.)23 b(Such)14 b(a)g(separat\ ion)f(is)g(suggested)g(by)g(the)75 1099 y(observation)7 b(that)h(the)g(emulat\ ion)g(library)f(is)h(the)h ff(only)f fg(system)h(component)f(that)f(interacts) i(directly)e(with)g(the)i(application)75 1149 y(programs)e(operating)e(in)i (the)f(emulated)h(environment;)g(it)f(provides)g(the)h(necessary)h(indirectio\ n)d(allowing)g(the)i(decoupling)75 1198 y(of)h(the)g(interface)g(provided)f (by)h(the)g(collection)f(of)h(servers)h(and)f(the)g(application)f(programming) g(interface.)15 b(Accordingly)l(,)75 1248 y(the)e(\256rst)g(layer)o(,)i(or)e ff(service)i(layer)p fg(,)g(contains)e(a)h(collection)e(of)h(components)h(or) f(servers)h(that)f(provide)f(basic)i(services,)75 1298 y(de\256ned)e(in)e(suc\ h)i(a)g(way)f(as)h(to)f(be)h(as)g(generic)f(as)h(possible,)f(so)h(that)e(they) h(can)h(be)g(useful)f(for)g(the)g(emulation)f(of)h(several)75 1348 y(dif)n (ferent)h(high-level)e(operating)h(systems)h(and/or)f(for)g(various)g(con\256\ gurations.)18 b(The)12 b(second)g(layer)g(or)f ff(specialization)75 1398 y (layer)j fg(implements)f(the)h(aspects)g(of)f(interface)h(or)f(functionality) e(that)i(are)h(speci\256c)h(to)d(a)j(particular)d(emulation)h(tar)o(get,)75 1448 y(and)c(operates)h(as)f(a)h(translator)e(between)h(the)g(emulated)h(appl\ ication)d(programming)i(interface)g(and)g(the)g(generic)g(services)75 1497 y (exported)h(by)h(the)g(service)g(layer)n(.)17 b(This)11 b(specialization)f (layer)h(is)g(concentrated)g(as)h(much)f(as)h(possible)e(in)g(the)h(emulation) 75 1547 y(library)l(.)137 1638 y(This)i(approach)g(leads)h(to)e(the)h(de\256n\ ition)e(of)i(a)h(new)f(\252system)h(programming)e(interface\272)i(between)f (the)g(emulation)75 1688 y(library)7 b(and)h(the)g(service)h(layer)f(that)f (is)h(not)g(directly)f(visible)g(to)g(application)g(programs.)14 b(Its)8 b (design)f(can)i(thus)f(concentrate)75 1738 y(on)i(issues)i(of)e(security)m (,)h(performance)h(and)f(most)f(of)h(all)f(\257exibility)-5 b(,)12 b(thereby) e(increasing)h(the)f(potential)f(for)i(making)f(the)75 1788 y(service)h(layer) g(more)g(generic.)18 b(Issues)11 b(of)f(simplicity)f(and)i(ease)h(of)f(use)g (of)g(this)e(interface)i(by)g(programmers,)h(while)e(still)75 1838 y(importan\ t,)k(are)h(nonetheless)e(secondary)i(when)f(compared)g(to)g(this)f(main)h(con\ sideration.)25 b(Similarly)l(,)15 b(the)f(modes)g(of)75 1888 y(interactions)8 b(between)h(the)g(components)f(inside)g(the)h(service)h(layer)f(can)g(be)g (de\256ned)g(freely)g(to)f(maximize)i(the)f(\257exibility)-5 b(,)75 1937 y (con\256gurability)9 b(and)i(reusability)f(of)h(this)g(layer)n(,)h(with)e(lit\ tle)g(concern)i(for)f(the)g(requirements)g(of)g(application)f(programs)75 1987 y(in)g(each)h(speci\256c)g(tar)o(get)f(system.)137 2078 y(In)d(practice,)i (the)e(service)i(layer)e(can,)i(of)e(course,)i(only)d(be)i(partially)e(generi\ c.)14 b(Current)7 b(observations)f(from)h(the)h(design)75 2128 y(of)k(our)f (prototype)f(indicate)i(that)f(high-level)g(services)i(such)f(as)h(\256le)f (management,)i(network)d(access)j(and)e(local)g(\252pipe-)75 2178 y(style\272) h(interprocess)g(communication,)h(can)g(be)f(expected)h(to)f(be)g(directly)g (useful)f(for)h(a)h(variety)f(of)g(operating)f(system)75 2228 y(environments.) 18 b(In)11 b(addition,)f(many)i(ancillary)e(services)i(that)f(are)h(not)f(dir\ ectly)f(exported)h(at)g(the)g(application)f(program)75 2278 y(level,)h(such)g (as)g(authentication,)e(location)h(of)g(servers)h(\(coarse-grain)g(naming\),) f(con\256guration)f(management,)j(etc.,)g(can)75 2328 y(also)i(be)g(reused)h (in)e(many)h(dif)o(ferent)f(system)i(con\256gurations.)25 b(On)14 b(the)f(oth\ er)h(hand,)h(process)f(management)i(remains)75 2377 y(lar)o(gely)11 b(tied)f (to)g(the)h(semantics)h(of)e(each)j(particular)d(tar)o(get)h(operating)e(syst\ em,)j(mainly)f(because)h(of)f(the)g(complexity)e(of)75 2427 y(the)i(de\256nit\ ions)f(of)h(groups)f(of)h(emulated)h(processes)g(and)g(the)f(associated)h(rul\ es)f(for)g(access)i(mediation.)18 b(However)o(,)12 b(we)75 2477 y(have)c(star\ ted)g(and)g(continue)f(to)g(develop)g(a)i(set)f(of)f(low-level)g(core)i(compo\ nents)e(that)g(can)i(be)f(assembled)h(and)f(customized)75 2527 y(to)k(constru\ ct)g(dif)n(ferent)g(variations)g(of)g(process)h(managers.)23 b(Finally)l(,)14 b(terminal)e(management)h(\(\252TTY\272\))h(has)f(not)f(been)75 2577 y(consid\ ered)f(for)g(generalization)f(so)h(far;)g(the)g(main)h(dif)n(\256culties)f (in)f(this)h(area)h(stem)g(from)e(the)h(semantic)h(richness)f(of)g(the)75 2626 y(line)f(management)h(strategies,)g(together)e(with)g(the)h(multiple)f(user)o (-controllable)g(options)g(\()p ff(ioctl\(\))p fg(\).)965 2804 y(4)p eop %%Page: 5 5 bop 75 42 a fh(3.2.)51 b(Standard)10 b(Object-Oriented)g(System)j(Interfaces) 75 161 y fg(T)m(o)j(capitalize)g(on)f(the)h(idea)g(of)f(using)g(generic)h(ser\ vices,)i(most)e(high-level)e(functions)h(are)h(de\256ned)g(in)f(terms)h(of)g (an)75 211 y(object-oriented)8 b(framework.)16 b(Each)11 b(operating)e(system) h(service)h(is)e(represented)i(by)e(one)h(or)g(more)g(abstract)h ff(OS)e(obje\ cts)75 260 y fg(or)e ff(items)p fg(,)i(exporting)d(a)i(well-de\256ned)g(set)g (of)f(operations.)14 b(Examples)8 b(from)g(the)f(UNIX)h(domain)f(are)i(\256le\ s,)g(pipes,)f(sockets,)75 310 y(tty')l(s,)k(etc.,)g(but)e(in)h(practice,)g (each)h(of)f(those)g(UNIX)f(abstractions)h(may)m(,)h(of)e(course,)i(be)f(repr\ esented)h(by)e(a)h(more)h(neutral)75 360 y(item,)e(corresponding)e(to)h(a)h (generic)g(service)g(that)f(can)h(be)g(specialized)g(by)f(the)h(emulation)e (library)h(for)g(a)h(given)f(emulated)75 410 y(environment.)16 b(Each)c(serve\ r)g(normally)e(implements)g(a)i(lar)o(ge)f(number)g(of)f(similar)n(,)i(but)e (independent)g(items.)17 b(Note)11 b(that)75 460 y(the)j(various)f(servers)h (and)g(items)f(may)i(themselves)f(be)g(implemented)g(using)e(object-oriented) h(techniques;)h(the)g(word)75 509 y ff(item)c fg(is)g(used)g(to)g(avoid)g(con\ fusion)f(with)g(the)h(actual)h(objects)f(used)g(at)g(the)g(implementation)f (level.)137 601 y(The)k(operations)d(exported)h(by)h(each)h(item)e(are)i(cate\ gorized)f(into)e(several)j(independent)e(functional)f(groups)h(which)75 651 y (are)k(standard)e(throughout)f(the)h(system.)27 b(Each)15 b(such)f(group)f (of)g(functions)g(is)g(represented)i(by)e(a)i(speci\256c)f(\252standard\272) 75 700 y(interface.)i(These)11 b(interfaces)g(are)g(important)e(both)g(to)h (allow)f(a)i(degree)g(of)f(tar)o(get-system)g(independence)h(at)f(the)g(servi\ ce)75 750 y(level,)j(and)g(to)f(allow)g(for)g(the)h(easy)g(combination)e(and) i(integration)e(of)h(many)h(independent)f(servers)h(or)f(services.)23 b(The) 75 800 y(major)11 b(categories)h(of)f(functions)f(currently)h(de\256ned)g(for) g(our)g(BSD)h(prototype,)e(that)h(appear)h(to)f(be)g(well-suited)f(in)h(both) 75 850 y(of)f(these)h(respects,)g(are:)75 970 y fc(access)h(mediation:)19 b fg (access)c(to)d(all)g(entities)g(\()p ff(items)p fg(\))g(in)g(the)h(system)g (is)g(mediated)g(through)e(a)i(standard)g(facility)e(using)179 1020 y(general\ -purpose)c(access)j(control)d(lists)g(and)h(a)g(uniform)f(representation)g (for)g(user)h(credentials.)15 b(The)8 b(requirements)179 1070 y(of)16 b(parti\ cular)g(tar)o(get)g(OS'es)h(can)h(typically)d(be)h(handled)h(with)e(special)i (initialization)c(and)k(interpretation)d(of)179 1119 y(the)h(standard)g(abstr\ actions.)30 b(There)17 b(is)e(a)h(\252secure\272)h(variation)e(of)g(this)f (system,)k(tar)o(geted)d(at)h(the)f(B3)g(level)g(of)179 1169 y(security[11)o (].)75 1250 y fc(naming:)k fg(all)d(entities)f(in)g(the)h(system)g(can)g(be)g (named)h(and)f(accessed)i(through)c(a)j(uniform)d(name)j(space,)i(that)c(also) 179 1300 y(handles)8 b(garbage-collection)g(and)g(access)j(mediation)d(for)g (item)g(creation.)15 b(There)9 b(is)f(a)h(common)g(name)h(resolution)179 1350 y(protocol)g(to)i(navigate)g(the)g(global)f(name)i(space,)i(locate)d(servers) h(and)f(locate)g(individual)e(items)i(inside)g(a)h(server)179 1399 y(\(e.g.,) k(\256les)f(in)e(a)i(\256le)f(server)o(,)h(pipes)f(in)g(a)g(pipe)g(server)n (,)i(etc.\).)30 b(This)15 b(name)i(space)f(is)f(lar)o(gely)f(independent)g (of)179 1449 y(syntactic)9 b(issues)g(for)g(path)f(names,)j(such)e(as)h(the)f (interpretation)e(of)i(symbolic)f(links,)h(UNIX)g(\252..\272,)i(etc.)16 b(It) 8 b(supports)179 1499 y(user)o(-centered)j(naming)f(through)e(the)i(use)h(of) f ff(pr)n(e\256x)h(tables)p fg([12)o(].)75 1580 y fc(I/O:)21 b fg(the)12 b (I/O)g(interface)h(provides)f(a)h(neutral)f(model)h(for)f(the)h(identi\256cat\ ion)e(and)i(transfer)f(of)h(data.)22 b(It)13 b(supports)e(both)179 1630 y(byt\ e-level)d(and)h(record-level)f(data)h(access,)j(as)d(well)g(as)g(sequential)f (and)h(random)g(access)i(operation.)j(Most)8 b(issues)179 1679 y(of)g(synchro\ nization)f(are)j(left)e(to)g(the)h(clients)f(\(emulation)g(libraries\))f(for) i(maximum)g(\257exibility:)i(when)e(necessary)o(,)179 1729 y(asynchronous)14 b (operations)f(are)j(simply)e(implemented)g(with)g(multiple)f(client)h(threads\ .)28 b(In)15 b(addition,)f(various)179 1779 y(caching)c(and)h(buf)n(fer)g(man\ agement)g(policies)f(can)h(be)f(implemented)g(within)f(the)h(same)i(I/O)d(fra\ mework.)75 1860 y fc(network)i(control:)20 b fg(the)12 b(network)f(control)g (operations)g(deal)i(with)e(the)h(creation)g(and)h(management)g(of)f(transpor\ t)f(end-)179 1910 y(points,)f(to)h(the)g(exclusion)f(of)h(actual)h(I/O)e(on)h (those)g(endpoints.)17 b(This)11 b(interface)g(is)g(lar)o(gely)g(inspired)f (by)h(XTI[6],)179 1959 y(with)d(some)i(changes)g(to)e(facilitate)h(sharing)f (of)h(endpoints)e(between)j(multiple)e(clients,)h(and)g(for)g(integration)e (in)h(the)179 2009 y(uniform)h(name)i(space.)75 2090 y fc(asynchronous)f(noti\ \256cations:)20 b fg(this)12 b(subsystem)i(can)g(be)g(used)g(by)f(servers)h (to)g(deliver)f(all)g(kinds)f(of)i(noti\256cations)e(to)179 2140 y(clients,)e (such)g(as)h(UNIX)f(signals,)h(VMS)f(events,)h(etc.)75 2260 y(Each)h(of)e(the\ se)h(basic)h(interfaces)f(does)g(not)f(directly)f(de\256ne)j(the)e(complete)h (functionality)d(exported)i(by)h(any)g(individual)75 2310 y(item;)17 b(rather) n(,)g(they)e(correspond)f(to)h(lower)o(-level)f(services)i(that)f(must)g(be)g (combined)g(to)g(de\256ne)g(the)g(complete)h(item.)75 2360 y(For)10 b(example\ ,)i(network)e(endpoints)f(typically)g(export)h(operations)g(from)g(both)g(the) g(I/O)g(and)h(network)e(control)h(interface)75 2409 y(categories.)137 2501 y (Many)g(primitives)e(of)h(various)g(tar)o(get)h(operating)e(environments)h (can)h(simply)f(be)h(implemented)g(with)e(an)i(equivalent)75 2551 y(primitive) k(from)h(a)h(standard)g(system)g(interface,)h(or)f(with)e(a)i(combination)f (of)g(such)h(primitives.)29 b(However)o(,)17 b(it)e(does)75 2600 y(not)e(seem) i(either)e(possible)g(or)h(practical)f(to)g(de\256ne)i(all)e(standard)g(inter\ faces)h(to)g(incorporate)e(every)i(feature)g(of)g(every)75 2650 y(conceivable) e(tar)o(get)f(system.)20 b(Therefore,)13 b(there)e(must)h(be)g(exceptions)f (that)g(must)g(be)h(handled)f(with)g(more)h(specialized)75 2700 y(system)c (primitives.)13 b(The)8 b(object-oriented)d(framework)j(provides)e(a)i(sound) f(basis)g(for)g(the)g(de\256nition)f(of)h(such)h(specialized)965 2804 y(5)p eop %%Page: 6 6 bop 75 42 a fg(functions,)12 b(either)g(through)f(the)i(addition)d(of)j(new) f(specialized)h(interfaces)g(alongside)f(the)h(standard)f(ones)h(for)f(variou\ s)75 91 y(specialized)d(items,)g(or)f(through)f(the)h(\252derivation\272)g (of)g(specialized)g(interfaces)h(from)f(the)h(standard)f(ones)g(by)g(adding)g (more)75 141 y(complex)j(or)f(modi\256ed)h(operations.)k(Since)c(the)g(de\256\ nitions)e(of)h(all)h(the)f(items)h(are)g(cleanly)g(separated)h(from)e(each)i (other)n(,)75 191 y(such)e(extensions)g(can)h(be)g(made)g(with)e(minimal)h (impact)g(on)g(the)g(system)h(as)g(whole.)137 282 y(It)i(is)h(clear)g(that)g (a)g(trade-of)n(f)g(exists)g(between)g(de\256ning)f(standard)g(interfaces)h (that)f(represent)h(the)g(union)e(of)i(many)75 332 y(dif)n(ferent)g(tar)o(get) g(systems,)h(and)f(resorting)f(to)g(specialization)g(of)h(interfaces)g(to)f (handle)h(some)g(less-common)g(or)g(less-)75 382 y(generalizable)c(features.) 16 b(In)10 b(general,)g(a)h(complete)f(system)g(contains)f(a)i(mix)e(of)h(gen\ eric)g(and)g(specialized)h(interfaces,)f(as)75 432 y(well)e(as)h(a)g(mix)g (of)f(generic)h(and)f(specialized)h(servers.)15 b(One)9 b(signi\256cant)f(exa\ mple)h(of)f(this)g(trade-of)o(f)g(is)g(the)h(de\256nition)d(of)j(a)75 482 y (collection)f(of)h(attributes)e(for)i(various)g(items,)g(that)g(can)h(be)f (used)g(to)g(implement)g(the)g(UNIX)g fb(stat\(\))f fg(operation:)13 b(the)c (set)75 531 y(of)h(all)h(possible)e(attributes)h(and)g(combinations)g(is)g (simply)g(too)g(lar)o(ge.)16 b(Accordingly)l(,)11 b(we)g(have)h(de\256ned)e (a)i(\252reasonable\272)75 581 y(set)j(of)g(standard)g(attributes,)h(and)f (rely)g(on)g(additional)e(specialized)j(operations)e(to)h(manipulate)g(all)f (other)h(attributes.)75 631 y(Some)f(other)e(examples)i(of)f(OS)g(features)h (that)e(seem)j(best)e(handled)f(through)g(specialization)g(are)i(the)f(combin\ ation)e(of)75 681 y(multiple)e(I/O)h(channels)g(into)f(one)i(\(message)h(queu\ es)e(in)g(UNIX)g(System)h(V)-5 b(,)10 b(reading)g(out-of-band)f(data)h(inline) f(on)h(BSD)75 731 y(sockets\),)j(complex)f(protections)e(that)h(do)g(not)g (\256t)h(the)f(simple)h(access)i(control)c(list)h(scheme)i(\(AFS,)g(UNIX)e (\252sticky)h(bit\272)75 780 y(on)e(directories\),)g(special)g(blocking)f(opt\ ions)g(for)g fb(open\(\))h fg(on)g(UNIX)g(TTY')n(s,)h(etc.)137 872 y(Regardle\ ss)e(of)g(the)g(resolution)e(of)h(the)h(trade-of)n(f)g(between)h(generalizati\ on)e(and)h(specialization,)f(it)g(remains)i(the)f(case)75 922 y(that)f(the)g (generic)g(interfaces)h(are)g(typically)e(more)i(complex)f(than)g(the)g(corre\ sponding)f(ones)i(in)e(any)i(particular)e(tar)o(get)i(OS,)75 971 y(since)j (they)e(must)h(often)g(support)f(a)h(richer)g(set)h(of)f(features,)h(and)f (tend)g(to)f(have)i(many)f(service)h(options.)k(As)c(mentioned)75 1021 y(earl\ ier)n(,)h(this)e(complexity)f(is)i(not)f(visible)f(to)h(application)f(program\ s)i(and)g(is)f(thus)g(not)g(a)h(primary)f(problem,)h(but)f(it)g(does)75 1071 y (signi\256cantly)d(complicate)i(the)g(task)f(of)h(providing)d(correct)j(and)g (complete)f(server)i(implementations)d(of)i(each)g(interface.)75 1121 y(W)m (e)g(have)g(found)f(that)g(a)i(good)e(\252standard)h(library\272)f(of)g(reusa\ ble)h(components)g(or)f(building)f(blocks)h(is)h(crucial)g(to)f(solving)75 1171 y(this)g(problem.)137 1262 y(In)h(addition,)g(in)f(order)i(to)e(maximize) j(\257exibility)-5 b(,)11 b(complex)f(operations)g(are)h(sometimes)g(decompos\ ed)g(into)e(several)75 1312 y(simpler)f(primitives)f(in)h(the)h(generic)g(int\ erfaces.)15 b(For)8 b(example,)i(most)f(UNIX)f(\256le)h(system)g(operations)f (are)h(implemented)75 1362 y(with)e(a)h(combination)e(of)i(one)g(or)f(more)h (steps)g(to)f(navigate)h(through)e(the)h(system)h(name)h(space)g(to)e(locate) h(a)h(particular)d(entity)75 1411 y(in)i(the)g(\256le)h(system,)g(followed)e (by)i(one)f(or)g(more)h(additional)e(steps)h(directed)g(at)h(the)f(item)h(ret\ urned)e(in)h(the)h(previous)e(phase.)75 1461 y(Similarly)l(,)j(several)h(step\ s)f(are)h(typically)e(needed)h(to)g(completely)g(set-up)f(a)i(socket)f(\(crea\ tion,)g(establishment)g(of)f(service)75 1511 y(options,)g(installation)f(in)i (the)g(user)o(-visible)f(name)i(space\).)17 b(This)10 b(approach)g(gives)g (rise)h(to)e(two)h(new)g(considerations:)137 1602 y(First,)15 b(whenever)g (the)f(state)g(of)g(the)g(system)h(or)f(item)g(is)g(visible)f(between)i(indiv\ idual)c(steps)k(of)f(such)g(a)h(sequence)75 1652 y(of)d(operations,)g(there)g (is)g(a)g(question)f(as)i(to)e(the)h(management)h(and)f(protection)f(of)g(tha\ t)h(state.)20 b(The)13 b(design)f(of)f(the)h(item)75 1702 y(interfaces)d(is)f (such)g(that,)g(in)g(most)g(cases,)j(this)c(does)h(not)g(cause)h(signi\256can\ t)e(dif)o(\256culties.)14 b(The)9 b(relevant)f(state)g(information)75 1752 y (is)k(either)g(naturally)f(made)i(visible)e(and)h(accessible)i(to)d(all)h(\(e\ .g.,)i(item)e(references)i(or)e(locks\))g(or)f(it)h(is)g(abstracted)g(away)75 1802 y(through)5 b(the)i(use)h(of)f(options)e(and)j(information)d(maintained) i(by)g(the)g(client)f(and)h(provided)f(explicitly)f(with)h(each)j(primitive) 75 1851 y(\(e.g.,)i(I/O)f(modes)h(and)f(current)g(of)o(fset\).)15 b(In)10 b (one)g(case,)i(however)o(,)e(we)h(have)g(had)f(to)g(introduce)f(a)i(special)f (mechanism:)16 b(it)75 1901 y(is)9 b(possible)f(to)h(create)i(a)e(\252reserve\ d)i(entry\272)e(in)g(a)g(directory)g(to)f(lock)h(a)h(name)g(until)e(a)h(compl\ ete)h(entry)f(can)h(be)f(established.)75 1951 y(This)i(entry)g(prevents)h(ano\ ther)f(entry)g(from)g(being)g(created)i(with)d(the)h(same)i(name,)h(but)c(it) h(cannot)g(be)h(looked-up)e(in)h(the)75 2001 y(traditional)e(fashion.)18 b (In)11 b(general,)h(we)g(have)g(considered)f(introducing)e(a)j(general-purpos\ e)f(locking)f(facility)g(to)h(protect)75 2051 y(groups)e(of)h(operations,)g (but)f(have)i(not)f(found)f(such)h(a)h(facility)e(to)h(be)g(required)g(so)g (far)n(.)137 2142 y(Second,)16 b(and)e(probably)f(more)h(importantly)-5 b(,) 16 b(the)e(use)g(of)g(sequences)h(of)f(operations)f(to)h(perform)g(common)g (tasks)75 2192 y(raises)e(legitimate)e(performance)i(concerns.)18 b(This)12 b (question)d(introduces)i(another)f(design)h(trade-of)o(f,)g(to)g(de\256ne)g (a)h(set)f(of)75 2242 y(special)i(\252composite)h(operations\272)e(to)g(optim\ ize)h(selected)h(functions)d(without)g(unduly)h(compromising)g(the)h(\257exib\ ility)75 2291 y(and)d(reusability)f(of)h(the)g(various)f(servers.)16 b(The)11 b(number)f(of)g(these)g(operations)f(must)h(be)h(kept)f(small,)g(because)i (they)e(may)75 2341 y(in)k(principle)f(have)i(to)f(be)g(implemented)h(by)f (every)g(server)h(participating)e(in)h(every)g(emulation)g(system.)28 b(The) 15 b(prime)75 2391 y(example)g(of)f(this)g(question)f(is)h(again)h(provided)e (by)h(the)g(UNIX)g ff(stat\(\))f fg(operation:)22 b(the)14 b(design)g(de\256n\ es)h(a)g(composite)75 2441 y(operation)10 b(that)g(combines)h(a)h(simple)e (name)i(resolving)e(step)h(to)f(locate)h(a)g(\256le)h(and)e(a)i(simple)f(oper\ ation)e(to)i(retrieve)f(a)i(set)75 2491 y(of)f(common)g(attributes.)17 b(This) 11 b(composite)g(operation)f(only)g(covers)i(the)f(most)g(common)g(usage)h (pattern)f(in)f(the)h(system;)75 2540 y(if)h(the)g(resolving)f(process)i(has) g(to)e(be)i(more)g(complex)f(\(e.g.)22 b(follow)11 b(mount)g(points)g(or)h (symbolic)g(links\),)g(or)g(if)g(special)75 2590 y(attributes)d(must)h(be)h (retrieved,)f(the)g(clients)g(must)g(fall)g(back)g(on)g(the)g(more)h(primitiv\ e)e(operations.)137 2682 y(T)n(o)i(try)f(to)g(provide)g(another)h(approach)g (to)g(this)f(problem,)h(we)h(are)f(also)g(planning)f(to)g(investigate)g(exten\ sions)h(in)f(the)965 2804 y(6)p eop %%Page: 7 7 bop 75 42 a fg(RPC)9 b(system)h(to)f(allow)g(\252batching\272)h(or)f(groupin\ g)f(of)h(several)i(primitive)d(operations)g(in)h(a)i(single)e(high-level)f (invocation)75 91 y(without)g(requiring)h(changes)i(to)f(the)g(simple)g(inter\ faces.)75 248 y fh(3.3.)51 b(Modular)11 b(Services)75 368 y fg(In)k(order)f (to)g(maximize)i(the)f(overall)f(\257exibility)-5 b(,)17 b(and)e(to)f(take)h (advantage)g(of)g(the)g(potential)e(of)o(fered)i(by)g(the)f(idea)h(of)75 418 y (reusable)g(services,)j(the)d(design)f(aims)i(to)e(de\256ne)h(as)h(many)f(ind\ ependent)f(servers)i(as)g(possible.)28 b(Those)16 b(servers)f(can)75 467 y (then)c(be)g(used)g(as)h(a)g(collection)e(of)h(standardized)g(building)d(bloc\ ks)j(that)f(can)i(be)g(assembled)g(in)e(various)h(ways)g(to)g(create)75 517 y (dif)n(ferent)16 b(systems.)31 b(In)15 b(addition)f(to)h(its)f(great)i(\257ex\ ibility)-5 b(,)17 b(such)f(an)f(architecture)h(also)f(increases)i(the)e(secur\ ity)g(and)75 567 y(robustness)g(of)g(the)g(system)h(by)f(isolating)f(faulty)g (or)h(potentially)e(malicious)i(components)g(into)f(separate,)19 b(protected) 75 617 y(address)12 b(spaces.)20 b(Moreover)n(,)12 b(it)f(sometimes)h(simpli\ \256es)f(the)g(implementation)f(of)h(some)h(servers,)h(by)e(allowing)e(the)j (use)75 667 y(of)i(multiple)f(instances)i(of)f(one)h(server)g(instead)f(of)h (a)g(single)e(more)i(complicated)g(server)g(\(for)f(example,)j(one)d(simple) 75 716 y(\256le)e(server)g(for)f(each)i(disk)e(partition\).)16 b(However)o (,)c(such)g(a)g(desire)g(for)f(maximum)h(modularity)e(must)h(be)h(balanced)g (by)g(a)75 766 y(number)e(of)g(practical)g(considerations:)137 878 y fa(\017) 21 b fg(Interactions)9 b(between)h(servers)h(are)g(more)f(expensive)g(than)g (interactions)f(between)h(modules)g(inside)f(a)i(particular)179 928 y(server) n(.)j(The)7 b(separation)f(of)f(services)i(and)g(the)f(corresponding)t(interf\ aces)h(must)f(be)g(carefully)g(de\256ned)h(to)e(minimize)179 977 y(those)10 b (interactions.)16 b(W)m(e)11 b(have)g(tried)f(to)g(limit)f(each)j(basic)g(use\ r)o(-level)e(operation)g(to)g(require)g(the)h(intervention)d(of)179 1027 y (only)g(one)h(server)n(.)15 b(There)10 b(are)g(two)f(main)g(examples)h(where) g(this)e(principle)g(creates)i(dif)o(\256culties)e(in)h(our)f(prototype:)179 1077 y(the)i(interaction)e(between)j(the)f(process)g(manager)h(and)f(the)g (TTY)h(server)f(to)g(handle)g(job)f(control,)g(and)h(the)g(general)179 1127 y (problem)d(of)h(UNIX)f fb(fork\(\))p fg(,)h(where)h(the)e(parent)h(emulated)g (process,)h(which)f(is)f(normally)g(in)g(contact)h(with)f(many)179 1177 y(ser\ vers,)k(must)e(arrange)i(for)e(the)h(child)f(process)i(to)e(inherit)f(access) k(to)d(all)h(those)g(servers,)h(along)e(with)g(a)h(consistent)179 1226 y(clie\ nt)k(state.)28 b(W)m(e)15 b(have)g(no)g(solution)d(to)i(the)h(job)e(control)h (problem.)27 b(W)m(e)15 b(handle)g(the)f fb(fork\(\))g fg(problem)g(by)179 1276 y(de\256ning)9 b(the)i(system)g(interfaces)g(such)g(that)e(a)j(single)d (association)h(between)h(a)g(client)f(and)h(a)g(server)g(\(i.e.)16 b(a)11 b (Mach)179 1326 y(port\))f(can)i(be)g(transparently)e(shared)i(between)g(all)f (the)g(processes)i(in)e(a)h(UNIX)f(process)h(tree,)g(without)e(requiring)179 1376 y(the)i(explicit)f(intervention)e(of)j(each)i(server)n(.)21 b(Note)12 b (that)f(with)g(this)h(scheme,)i(from)e(the)g(perspective)g(of)g(a)h(server)o (,)179 1426 y(all)d(the)g(client)f(processes)j(that)d(share)i(the)g(same)g (authentication)e(credentials)h(are)h(normally)e(indistinguishable.)179 1489 y (In)f(general,)i(the)e(separation)g(between)h(servers,)h(and)f(between)g(serv\ ers)g(and)g(clients,)g(increases)h(the)e(importance)g(of)179 1539 y(distribut\ ed)g(shared)k(state)f(in)f(the)h(system.)18 b(Much)11 b(of)f(this)h(dif)n(\ \256culty)f(is)h(solved)f(by)h(appropriate)f(selection)h(of)f(the)179 1589 y (location)g(of)h(each)h(item)f(of)g(information)f(throughout)e(the)j(system)h (\(see)g(\252Smart)g(Emulation)f(Libraries\272)g(below\).)179 1638 y(In)e(add\ ition,)f(we)h(are)h(investigating)d(the)i(possibility)d(of)j(using)f(a)i(gene\ ral-purpose)e(facility)g(\(blackboard)h(service\))179 1688 y(that)f(allows)h (more-or)o(-less)h(arbitrary)e(data)i(elements)g(to)f(be)g(shared)h(ef)o(\256\ ciently)f(between)h(any)f(number)g(of)g(servers)179 1738 y(and)h(clients,)g (according)g(to)g(a)h(schema)h(that)d(can)i(be)g(adapted)f(to)g(the)g(needs)h (of)f(various)g(speci\256c)h(emulations.)137 1815 y fa(\017)21 b fg(The)c(aut\ hentication)d(logic)h(in)h(the)g(system)g(can)h(become)g(complicated,)h(since) f(each)g(server)g(is)f(normally)f(re-)179 1864 y(sponsible)10 b(for)h(verifyi\ ng)e(the)i(identity)e(of)i(its)f(clients)h(independently)l(.)18 b(This)11 b (policy)f(also)h(introduces)f(additional)179 1914 y(dif)n(\256culties)i(if)h (dif)n(ferent)g(authentication)e(schemes)j(are)g(to)e(be)h(used)g(with)f(dif) n(ferent)h(servers)g(and)g(if)f(the)h(system)179 1964 y(must)f(handle)g(mutua\ l)f(suspicion)g(between)i(clients)e(and)h(arbitrary)f(servers.)22 b(The)12 b (standard)g(access)i(control)d(and)179 2014 y(naming)g(interfaces)i(of)o(fer) f(basic)g(support)f(for)g(these)i(requirements)e(by)h(providing)d(a)k(good)e (separation)h(between)179 2064 y(the)j(functions)g(related)h(to)f(normal)g (client)g(access)j(and)e(the)f(authentication)g(function)f(itself:)24 b(clien\ ts)15 b(may)i(be)179 2113 y(arbitrarily)12 b(requested)i(to)g(re-authenticate) f(themselves)i(whenever)g(they)e(start)h(referring)f(to)h(any)g(speci\256c)h (new)179 2163 y(item,)10 b(and)h(the)f(particular)f(authentication)g(mechanis\ m)i(to)f(be)g(used)h(may)g(be)f(dif)o(ferent)g(in)g(each)h(case.)137 2240 y fa (\017)21 b fg(Although)15 b(each)j(server)f(typically)f(performs)h(a)g(dif)n (ferent)g(high-level)f(function,)h(there)g(are)h(many)f(low-level)179 2290 y (functions)f(that)h(must)h(be)g(performed)f(similarly)g(by)g(all)g(servers,)k (such)d(as)g(access)i(mediation,)f(name)g(space)179 2339 y(management,)13 b (buf)o(fer)e(management,)j(etc.)19 b(Modules)11 b(implementing)f(most)h(of)h (these)f(functions)f(are)j(stored)e(in)g(a)179 2389 y(common)c(library)f(used) i(by)f(all)f(servers,)j(but)e(the)g(overall)f(run-time)h(memory)g(usage)h(of) f(the)g(system)h(is)f(considerably)179 2439 y(greater)j(than)e(that)h(of)g (an)h(equivalent)e(monolithic)g(system.)15 b(This)9 b(problem)g(could)g(be)h (partially)e(solved)g(by)h(the)h(use)179 2489 y(of)i(a)i(shared)f(library)e (to)h(eliminate)h(duplication)d(of)j(code)g(segments,)i(but)c(it)h(remains)i (the)e(case)j(that)d(much)h(data)179 2539 y(space)e(is)f(essentially)g(wasted\ .)137 2650 y(In)k(general,)h(the)e(design)g(of)g(the)h(system)g(interfaces)g (is)f(such)h(that)f(clients)g(\(emulation)f(libraries\))h(are)h(unaware)g(of) 75 2700 y(which)e(server)g(is)g(handling)e(which)i(item,)h(so)f(that)f(server\ s)i(can)f(be)h(combined)e(or)h(separated)h(freely)f(without)e(requiring)965 2804 y(7)p eop %%Page: 8 8 bop 75 42 a fg(changes)14 b(in)f(the)h(clients.)24 b(The)14 b(few)g(elements) g(of)f(state)h(that)f(are)h(logically)e(associated)i(with)f(each)h(client-ser\ ver)f(pair)75 91 y(\(mostly)c(authentication)e(information\))h(appear)i(to)f (the)h(clients)f(as)h(if)f(they)g(were)h(attached)g(to)f(each)i(individual)c (item,)j(and)75 141 y(are)i(transparently)e(replicated)h(and)g(inherited)f (among)h(multiple)f(items)h(managed)h(by)f(the)g(same)h(server)g(as)g(appropr\ iate.)75 191 y(However)n(,)k(there)e(is)g(also)f(a)i(need)f(for)g(a)g(global) f(knowledge)g(of)h(the)g(system,)h(to)f(handle)f(operations)g(such)h(as)h(ord\ erly)75 241 y(shutdown,)i(startup,)g(administration)d(and)i(maintenance,)j (etc.,)g(as)d(well)g(as)h(to)f(keep)g(track)g(of)g(information)e(needed)75 291 y(by)g(all)h(components,)g(such)g(as)h(the)e(current)h(time)f(zone,)j(node)d (identity)-5 b(,)17 b(etc.)29 b(W)m(e)15 b(are)g(currently)f(building)e(a)j ff (system)75 340 y(con\256guration)10 b(server)15 b fg(to)d(keep)h(track)f(of)g (all)h(the)f(servers)h(in)f(the)g(system)h(and)g(to)f(perform)g(those)g(dutie\ s.)22 b(Finally)l(,)13 b(the)75 390 y(question)7 b(of)g(implementing)f(global) h(system)h(usage)h(accounting)e(and)g(of)h(enforcing)f(global)f(resource)j (limits)d(has)i(received)75 440 y(little)k(attention)f(so)j(far;)g(the)g(main) f(dif)o(\256culties)f(in)h(this)g(area)h(are)g(the)g(need)g(for)e(servers)j (to)d(identify)g(individual)f(client)75 490 y(processes)g(\(and)f(not)g(just) f(groups)g(of)h(processes)i(with)d(the)h(same)h(identity\),)e(and)h(of)g(ef)o (\256ciently)g(collecting)f(them)h(among)75 540 y(a)h(collection)e(of)h(indep\ endent)f(servers.)137 631 y(In)h(practice,)h(our)f(BSD)g(prototype)f(contains) g(or)h(will)f(contain)h(the)g(following)e(servers:)75 756 y fc(Servers)k(that) e(provide)g(services)h(directly)f(visible)f(to)h(application)f(programs)h(\(t\ hr)o(ough)g(emulation)f(libraries\):)229 847 y fa(\017)20 b fg(one)12 b(or)g (more)h(\256le)f(servers,)i(handling)d(dif)n(ferent)h(\256le)h(systems)f(\(UF\ S,)h(NFS,)g(AFS,)g(etc.\))21 b(and/or)12 b(physical)270 897 y(devices.)229 963 y fa(\017)20 b fg(a)10 b(terminal)g(server)g(managing)f(all)h(serial)f(lines) h(and)g(implementing)e(the)i(equivalent)e(of)i(all)f(UNIX)h(tty')l(s)g(and) 270 1013 y(pty')m(s.)229 1079 y fa(\017)20 b fg(a)11 b(local)f(IPC)g(server)h (or)f(\252pipenet)g(server)r(\272,)h(responsible)e(for)h(all)g(intra-node)f (emulation-level)g(\(non-Mach\))270 1129 y(IPC:)h(pipes,)g(UNIX-domain)f(sock\ ets,)i(and)g(possibly)e(System)h(V)h(queues)f(and)g(VMS)h(mailboxes.)229 1196 y fa(\017)20 b fg(a)11 b(process)g(management)g(server)g(or)f(\252task)h(mast\ er)r(\272,)h(to)d(keep)i(track)g(of)f(all)g(emulated)g(process)h(and)g(proces\ s)270 1245 y(groups,)f(and)g(handle)g(signal)g(dispatching.)229 1312 y fa(\ \017)20 b fg(one)11 b(or)g(more)h(network)e(servers)i(implementing)e(socket-l\ ike)h(entities)f(for)h(a)h(variety)e(of)h(network)g(protocol)270 1362 y(famil\ ies.)k(This)10 b(server)h(is)f(currently)f(derived)h(from)g(the)h(x-kernel)e (from)h(the)g(University)f(of)h(Arizona[7)o(].)229 1428 y fa(\017)20 b fg(a) 11 b(device)g(server)f(handling)f(raw)i(access)h(to)e(the)g(hardware)h(device\ s,)g(grouped)e(in)h(a)h(\252/dev\272)g(directory)l(.)75 1519 y fc(Servers)h (that)e(support)h(the)f(operation)g(of)g(the)h(other)g(servers:)229 1611 y fa (\017)20 b fg(one)13 b(or)f(more)i ff(r)n(oot)e(name)h(servers)i fg(tying)c (all)i(the)f(other)h(servers)g(into)f(a)h(single)f(hierarchical)h(name)h(spac\ e)270 1660 y(through)9 b(a)h(collection)g(of)f ff(mount)h(points)p fg(.)229 1727 y fa(\017)20 b fg(a)14 b(simple)g(authentication)e(server)i(providing)d (trusted)i(translations)g(between)h(client)f ff(tokens)h fg(and)f(explicit) 270 1777 y ff(cr)o(edentials)p fg(.)229 1843 y fa(\017)20 b fg(a)d(blackboard) e(server)i(managing)f(distributed)d(state)k(stored)e(in)h(pages)g(of)g(shared) h(memory)f(mapped)h(in)270 1893 y(various)10 b(servers)h(and)f(client)g(emula\ tion)f(libraries.)229 1959 y fa(\017)20 b fg(a)8 b(con\256guration/admin/star\ tup)s(server)g(that)f(starts)g(all)f(the)i(other)e(servers)i(and)f(provides)g (centralized)g(access)270 2009 y(to)j(global)f(information.)229 2076 y fa(\ \017)20 b fg(various)13 b(ancillary)h(servers)g(not)f(directly)g(related)h (to)g(the)g(emulation)f(system,)i(for)f(diagnostics,)g(network)270 2125 y(sha\ red)d(memory)m(,)g(network)f(IPC,)g(etc.)75 2285 y fh(3.4.)51 b(Client-side) 11 b(Pr)o(ocessing)i(and)f(Smart)g(Emulation)g(Libraries)75 2405 y fg(Indepen\ dent)j(of)h(providing)d(a)j(convenient)f(mechanism)i(for)f(introducing)d(a)j (separation)g(between)g(a)h(generic)f(and)g(a)75 2454 y(tar)o(get-speci\256c) 11 b(layer)f(in)f(the)h(system,)h(the)f(emulation)f(library)g(also)h(provides) f(an)i(opportunity)c(to)i(optimize)h(or)g(simplify)75 2504 y(many)f(client-se\ rver)g(interactions)f(by)h(displacing)e(some)j(of)f(the)g(processing)f(requir\ ed)h(to)f(implement)h(various)f(functions)75 2554 y(from)i(the)g(system)g(ser\ vers)h(into)d(the)i(clients)f(of)h(these)g(services)h(themselves,)g(and)f(to) f(concentrate)i(system)f(state)g(in)g(these)75 2604 y(clients.)15 b(This)10 b (approach)g(is)h(illustrated)d(by)i(three)g(main)h(strategies:)965 2804 y(8)p eop %%Page: 9 9 bop 137 42 a fa(\017)21 b fg(The)9 b(design)f(of)h(many)g(service)h(interfac\ es)f(is)f(such)h(that)f(the)h(client)f(itself)g(is)h(primarily)e(responsible) h(for)g(managing)179 91 y(important)f(pieces)j(of)f(information)e(\(UNIX)i (\256le)g(descriptor)f(table,)h(signal)g(mask)h(and)f(handlers,)g(current)g (working)179 141 y(directory)l(,)i(etc.\))k(and)c(performing)e(complex)h(func\ tions)f(\(pathname)i(resolution,)d fb(exec\(\))i fg(logic,)g(etc.\).)137 223 y fa(\017)21 b fg(Whenever)13 b(a)g(server)g(grants)g(access)h(for)f(a)g(given) f(item)g(to)g(a)i(given)e(client,)h(a)g(special)g(code)g(fragment)g(or)f ff (pr)n(oxy)179 272 y(object)p fg([10)o(])k(is)h(installed)e(by)i(the)f(run-tim\ e)g(system)h(in)f(the)h(address)g(space)h(of)f(that)f(client)g(to)g(act)i(as) f(a)g(local)179 322 y(representative)8 b(for)g(the)g(associated)h(item.)15 b (This)8 b(proxy)l(,)h(which)f(is)h(de\256ned)f(and)h(supplied)e(by)h(the)g (server)o(,)h(provides)179 372 y(a)14 b(convenient)e(level)i(of)f(indirection) e(between)j(clients)f(and)h(servers.)25 b(Simple)13 b(proxies)g(just)g(forwar\ d)g(all)g(client)179 422 y(requests)c(directly)e(to)i(the)f(server)i(via)e (Mach)i(IPC,)f(but)f(more)h(complex)g(ones)g(can)g(implement)g(optimizations) e(such)179 472 y(as)14 b(caching)f(item)h(information,)e(or)h(managing)h(a)g (window)e(of)h(shared)h(memory)g(containing)d(\256le)j(data)g(or)f(other)179 521 y(I/O)e(or)g(control)f(information.)16 b(Proxies)11 b(are)i(currently)d (statically)g(linked)h(with)f(each)i(emulation)f(library)l(,)h(but)f(we)179 571 y(expect)f(that)g(they)g(will)f(eventually)g(be)i(dynamically)e(loaded.) 137 653 y fa(\017)21 b fg(The)9 b(emulation)e(library)h(can)h(itself)e(operat\ e)i(as)g(an)g(active)g(element,)g(to)f(simplify)f(and)i(relieve)f(some)h(of)f (the)h(burden)179 702 y(on)14 b(servers.)27 b(For)14 b(example,)j(the)d(UNIX) g(emulation)f(library)g(currently)g(contains)h(an)g(active)h(thread)f(to)f (handle)179 752 y(incoming)d(asynchronous)h(noti\256cations)f(and)i(transform) f(them)g(into)f(the)i(appropriate)e(UNIX)i(signals.)18 b(W)m(e)12 b(also)179 802 y(plan)e(to)f(use)i(active)g(emulation)e(library)g(threads)h(to)g(impleme\ nt)g(most)g(forms)g(of)g(asynchronous)g(I/O.)137 923 y(It)g(is)h(clear)g(that) f(there)h(are)g(limitations)d(to)i(the)h(use)g(of)f(client-side)g(processing.) 16 b(There)11 b(are)h(many)e(system)h(functions)75 973 y(that)16 b(require)g (synchronization)f(and)i(sharing)f(of)h(information)e(or)h(resources)i(betwee\ n)f(several)g(clients.)34 b(Although)75 1023 y(there)15 b(are)h(mechanisms)h (to)d(handle)h(a)h(number)f(of)g(these)g(problems)g(with)f(minimal)g(server)i (overhead,)h(the)e(need)h(for)75 1073 y(external)d(agents)h(or)f(servers)h (cannot)g(be)f(completely)h(eliminated.)24 b(More)13 b(importantly)-5 b(,)15 b (the)f(decision)f(to)f(place)j(more)75 1123 y(responsibility)d(for)i(various) h(system)g(functions)e(in)i(an)g(emulation)f(library)g(that)g(is)h(not)f(prot\ ected)g(from)h(incorrect)f(or)75 1172 y(malicious)d(user)g(programs)h(has)f (obvious)f(implications)g(in)g(the)h(areas)i(of)e(robustness)g(and)g(security) m(.)18 b(Clearly)m(,)12 b(the)f(more)75 1222 y(code)g(and)f(information)e(tha\ t)i(is)g(stored)f(in)h(the)g(emulation)f(library)l(,)i(the)f(greater)h(the)f (risk)f(is)h(of)g(accidental)h(or)e(intentional)75 1272 y(modi\256cation,)15 b (which)f(can)h(lead)f(to)g(very)g(complex)g(failure)g(modes.)28 b(One)14 b (interesting)f(example)i(of)f(this)g(problem)f(is)75 1322 y(presented)j(by)f (the)g fb(copyin)g fg(and)g fb(copyout)g fg(routines,)h(that)f(are)h(used)g (in)f(traditional)e(UNIX)i(systems)h(to)f(transfer)75 1372 y(system)f(call)g (ar)o(guments)f(between)h(user)g(space)h(and)f(the)f(protected)g(system)h(spa\ ce.)26 b(In)14 b(our)f(emulated)h(system,)h(these)75 1421 y(routines)9 b(may) j(verify)d(the)i(validity)d(of)i(the)h(user)f(buf)o(fers)h(when)f(they)h(are) g(invoked)e(and)i(even)g(copy)f(the)h(associated)g(data)75 1471 y(to)f(separa\ te)h(emulation-space)g(buf)n(fers,)h(but)d(there)i(is)f(no)g(way)g(to)g(effec\ tively)f(protect)h(this)g(data)g(from)h(modi\256cations)e(at)75 1521 y(any)h (time)h(while)e(it)h(is)g(being)f(used)i(inside)e(the)h(emulation)g(library)l (.)137 1612 y(In)j(accordance)i(with)d(the)h(goal)f(of)h(supporting)e(very)i (secure)h(system)g(implementations,)f(our)f(design)h(policy)f(is)h(to)75 1662 y(avoid)f(any)g(optimization)f(that)h(can)h(allow)e(a)i(malicious)f(emulated) h(client)f(to)g(gain)g(unauthorized)f(access)k(to)d(protected)75 1712 y(resou\ rces,)17 b(or)d(to)g(affect)h(the)f(integrity)f(of)h(another)h(emulated)g(cli\ ent)f(in)g(ways)h(that)f(would)f(not)h(be)h(possible)f(simply)75 1762 y(throu\ gh)d(the)i(use)g(of)g(the)g(\252published\272)f(application)g(programming)g (interface)h(being)f(emulated.)24 b(On)13 b(the)g(other)f(hand,)75 1812 y(we) j(believe)g(that)g(reasonable)g(compromises)g(are)h(acceptable)g(in)f(trading\ -of)m(f)g(performance)g(against)g(the)g(robustness)75 1861 y(of)f(individual) d(clients.)25 b(An)14 b(incorrect)g(user)g(program)f(may)i(be)f(allowed)f(to) h(corrupt)f(the)g(data)h(structures)g(of)f(its)h(own)75 1911 y(emulation)c (library)l(.)18 b(As)12 b(a)g(result,)f(it)f(may)i(even)g(modify)e(the)h(exte\ rnal)g(behavior)f(of)h(the)g(whole)g(emulated)h(process,)g(but)75 1961 y(only) 7 b(in)h(ways)h(that)f(could)g(also)g(be)h(achieved)g(with)f(a)h(dif)n(ferent) f(\(correct\))h(user)g(program.)14 b(The)9 b(key)g(element)g(that)e(permits) 75 2011 y(the)i(implementation)f(of)h(such)g(a)h(policy)e(resides)i(in)e(the) h(use)h(of)f(port)f(capabilities)g(for)h(all)g(individual)e(items)i(manipulat\ ed)75 2061 y(by)j(the)h(client:)19 b(these)13 b(can)h(be)f(destroyed)f(or)g (even)i(swapped,)g(but)e(never)h(actually)f(for)o(ged.)23 b(However)n(,)14 b (this)e(approach)75 2111 y(requires)e(very)g(careful)h(design,)f(and)g(we)h (know)f(of)g(no)g(formal)g(method)f(to)h(guarantee)h(its)f(correct)g(applicat\ ion.)137 2202 y(W)m(e)g(have)h(also)f(considered)f(a)i(scheme)g(in)e(which)h (a)g(substantial)e(portion)g(of)i(the)f(emulation)g(library)g(is)h(kept)f(sep\ arate)75 2252 y(from)e(the)f(emulated)h(process)h(itself)e(in)g(a)h(dif)o(fer\ ent)g(protected)f(Mach)i(task,)f(so)g(that)f(each)i(emulated)g(process)f(is)g (represented)75 2301 y(by)g(two)g(Mach)h(tasks.)14 b(However)n(,)9 b(the)e (communication)g(bandwidth)e(between)j(an)g(emulated)f(process)h(and)g(such)f (a)h(separate)75 2351 y(library)j(is)h(per)g(necessity)h(lower)f(than)f(that) h(of)g(the)g(fully-shared)f(case,)j(since)f(at)f(least)g(some)h(data)g(must)f (cross)h(address)75 2401 y(space)g(boundaries,)f(and)g(since)g(control)e(must) i(be)g(transferred)g(between)g(threads.)20 b(In)11 b(addition,)g(the)h(cost)f (of)h(creating)g(a)75 2451 y(new)f(emulated)g(process)g(is)g(typically)e(sign\ i\256cantly)g(higher)n(,)i(since)g(two)f(Mach)i(tasks)e(must)h(be)g(created)h (instead)e(of)h(one.)75 2501 y(Consequently)l(,)e(the)g(decision)f(to)g(use)i (a)f(protected)g(or)f(unprotected)g(emulation)g(library)g(must)g(be)i(made)f (by)g(balancing)f(the)75 2551 y(added)j(performance)g(of)f(one)h(against)f (the)g(added)h(robustness)f(of)g(the)g(other)m(.)16 b(W)m(e)11 b(feel)g(that) e(in)h(a)h(system)g(such)g(as)g(UNIX,)75 2600 y(where)g fb(fork\(\))e fg(oper\ ations)g(are)i(frequent,)f(the)g(unprotected)f(approach)h(is)g(probably)e(pre\ ferable.)16 b(On)10 b(the)g(other)f(hand,)75 2650 y(in)h(a)g(system)h(such)f (as)h(VMS,)f(where)h(process)g(creation)f(is)g(rare,)h(the)f(trade-of)n(f)g (may)h(lean)f(the)g(other)g(way)m(.)16 b(Note)10 b(that)f(this)75 2700 y(part\ icular)j(trade-of)n(f)h(does)f(not)g(detract)h(from)f(the)g(potential)f(for)h (reuse)h(of)g(server)g(components)f(and)h(generic)f(services)965 2804 y(9)p eop %%Page: 10 10 bop 75 42 a fg(for)11 b(the)g(emulation)f(of)h(dif)o(ferent)g(tar)o(get)g (systems,)h(since)g(emulation)f(libraries)f(are)i(necessarily)g(speci\256c)g (to)f(each)h(tar)o(get)75 91 y(operating)d(system.)137 183 y(T)n(wo)h(other)h (schemes)h(have)g(also)e(been)i(proposed)e(with)g(respect)h(to)f(the)h(locati\ on)f(and)h(protection)e(of)h(the)h(emulation)75 232 y(library:)17 b(placing) 11 b(it)g(in)h(kernel)g(space)h(within)e(each)i(emulated)f(task,)h(and)f(disp\ lacing)f(all)h(of)f(its)h(function)e(into)h(a)i(single)75 282 y(centralized)f (server)h(independent)e(of)h(the)g(emulated)g(processes)h(themselves.)21 b (Both)11 b(of)h(these)h(schemes)g(are)g(obviously)75 332 y(feasible,)c(but)e (they)g(contradict)g(our)h(basic)g(design)f(decisions)h(to)f(avoid)g(includin\ g)f(specialized)j(emulation)e(code)h(in)f(kernel)75 382 y(space)14 b(and)g (to)e(avoid)h(using)f(a)i(centralized)f(coordinating)e(agent,)j(respectively) m(.)24 b(Consequently)l(,)14 b(they)f(have)g(not)g(been)75 432 y(considered)d (further)g(within)e(the)i(scope)h(of)f(this)f(particular)h(investigation)137 523 y(Independent)e(of)g(these)h(high-level)e(considerations,)h(the)h(increas\ ed)g(complexity)f(of)g(smart)h(emulation)e(libraries)h(also)75 573 y(creates) i(very)e(signi\256cant)g(dif)n(\256culties)g(at)h(the)f(technical)g(level:)14 b(increased)9 b(size,)h(expensive)e(management)i(of)e(client)g(state)75 623 y (and)i(complexity)f(due)i(to)e(multi-threading.)137 714 y(The)15 b(size)f(of) f(a)i(smart)f(emulation)f(library)f(tends)i(to)f(be)h(considerably)f(lar)o (ger)h(than)f(that)g(of)g(a)i(simple)e(library)g(that)75 764 y(blindly)e(forw\ ards)h(all)h(system)h(calls)f(to)f(one)h(or)g(several)h(servers.)24 b(This)13 b(results)g(in)f(an)i(increased)f(load)g(on)g(the)g(virtual)75 814 y(memory)d (system,)h(both)d(in)h(the)h(form)f(of)g(normal)h(paging)e(activity)h(and)g (in)g(the)h(form)f(of)g(copy)h(faults)f(when)g(creating)h(new)75 863 y(emulat\ ed)h(processes)g(\(UNIX)f fb(fork\(\))p fg(\).)137 955 y(Smart)17 b(emulation) f(libraries)h(also)f(tend)h(to)f(contain)g(signi\256cant)g(amounts)h(of)g(sta\ te)g(that)f(must)h(be)g(inherited)e(or)75 1005 y(re-created)g(during)e(proces\ s)h(creation.)27 b(Simple)13 b(memory)i(can)g(be)f(naturally)f(inherited)g (through)f(the)i(services)h(of)e(the)75 1054 y(Mach)e(kernel,)f(but)g(other)g (elements)h(of)f(state)g(cannot,)g(such)h(as)g(active)f(threads)h(and)f(port) f(capabilities.)15 b(This)10 b(introduces)75 1104 y(potentially)e(signi\256ca\ nt)i(overheads.)16 b(In)10 b(particular)n(,)h(it)e(is)i(clear)g(that)f(a)h (trade-of)n(f)g(exists)f(with)f(respect)j(to)d(inheritance)h(of)75 1154 y(inf\ ormation)f(simply)i(cached)h(in)f(the)g(emulation)g(library)l(,)h(versus)f (simply)g(re-creating)g(this)f(cached)j(information)c(when)75 1204 y(and)h (if)g(needed.)16 b(This)10 b(trade-of)o(f)g(has)h(not)e(yet)h(been)h(satisfac\ torily)e(explored.)137 1295 y(Finally)l(,)g(smart)f(emulation)e(libraries)h (naturally)f(need)i(to)f(be)h(multi-threaded,)f(both)f(to)h(support)f(multipl\ e)g(user)i(threads)75 1345 y(issuing)i(system)j(calls,)f(and)g(to)f(support)f (active)i(threads)g(internal)e(to)h(the)h(emulation)f(library)l(.)19 b(W)m (e)12 b(have)h(found)d(that)h(the)75 1395 y(existing)j(implementations)g(of)h (the)g(Mach)h(cthreads)g(library)e(are)i(poorly)e(adapted)h(to)g(operate)h (inside)e(an)i(emulation)75 1445 y(library)l(.)k(W)l(e)13 b(have)f(had)f(to)g (introduce)g(modi\256cations)g(to)g(handle)g(interactions)g(with)f(threads)i (in)f(the)h(emulated)g(process)75 1494 y(itself,)g(for)f(correct)i(transfer)e (of)h(thread)g(state)g(at)g fb(fork\(\))f fg(time)h(\(clean-up)g(stacks)h(and) f(cthread)g(data)g(structures\),)g(and)75 1544 y(to)g(implement)h(an)g(interr\ upt)e(handling)g(facility)h(for)g(signal)g(delivery)m(.)23 b(Even)13 b(with)f (these)h(extensions,)h(multi-threaded)75 1594 y(emulation)c(libraries)g(are)i (still)d(dif)n(\256cult)i(to)f(write.)16 b(Furthermore,)11 b(it)f(does)h(not) f(appear)i(that)e(newer)i(implementations)d(of)75 1644 y(user)o(-level)g(thre\ ads)h(libraries)f(will)f(reduce)i(the)f(magnitude)g(of)g(this)g(problem.)14 b (In)c(particular)m(,)g(the)g(current)f(trend)g(towards)75 1694 y(mixing)e(cor\ outines)g(and)g(kernel-level)h(threads)f(clearly)h(complicates)h(matters,)g (since)f(the)g(emulation)f(system)h(must)g(often)75 1743 y(still)h(deal)h(wit\ h)f(\252raw\272)j(kernel)e(threads)g(for)g(Mach)h(exceptions)f(and)g(for)g (interrupts.)75 1900 y fh(3.5.)51 b(Object-oriented)10 b(Service)i(Library)75 2019 y fg(In)c(order)f(to)h(avoid)f(unnecessary)i(duplication)d(of)i(code,)h (the)f(system)h(design)e(includes)h(a)g(common)h(library)d(implementing)75 2069 y(many)13 b(functions)f(that)g(must)h(be)h(provided)d(in)i(several)h(dif) n(ferent)f(servers,)i(or)d(in)h(several)g(specialized)h(versions)f(of)f(the) 75 2119 y(same)17 b(service.)32 b(Such)16 b(a)g(library)l(,)i(through)c(its)h (modularity)-5 b(,)18 b(greatly)d(contributes)f(to)h(the)g(extensibility)e (and)j(ease)h(of)75 2168 y(modi\256cation)d(of)h(the)h(system)f(and)h(also)f (reduces)i(the)e(overall)g(complexity)f(of)h(the)g(entire)g(system)h(implemen\ tation.)75 2218 y(Our)11 b(prototype)e(contains)h(a)i(growing)e(collection)f (of)i(reusable)h(code)f(fragments)g(or)g(objects;)g(the)g(main)g(areas)h(curr\ ently)75 2268 y(covered)f(are:)137 2376 y fa(\017)21 b fg(access)12 b(mediati\ on)e(for)f(arbitrary)h(items)g(\(access)i(control)d(lists,)h(user)g(credentia\ ls,)h(authentication,)e(etc.\).)137 2451 y fa(\017)21 b fg(simple)11 b(buildi\ ng)e(blocks)i(to)g(construct)g(a)h(name)h(space)f(collecting)f(all)g(the)g (items)h(managed)g(by)f(one)h(server)o(,)g(and)179 2501 y(to)d(handle)h(item) h(creation)f(and)g(deallocation)f(when)i(appropriate.)137 2575 y fa(\017)21 b fg(mapped-\256le)10 b(access,)j(including)8 b(pagers)j(and)f(appropriate)g (proxy)f(objects.)137 2650 y fa(\017)21 b fg(sequential)12 b(streams)j(of)e (data)g(following)e(the)i(standard)g(I/O)f(interface)i(\(connections,)g(buf)n (fering,)g(data)f(transfer)179 2700 y(across)e(address)g(spaces,)h(etc.\).) 954 2804 y(10)p eop %%Page: 11 11 bop 137 42 a fa(\017)21 b fg(simple)9 b(pathname)g(resolution)f(from)h(the)g (client)f(side,)i(including)d(a)j(user)o(-controlled)e(pre\256x)h(table)g(and) g(caching)g(of)179 91 y(mount)g(points)g(and)h(symbolic)g(links.)137 172 y fa (\017)21 b fg(a)15 b(layer)g(of)g(code)g(to)g(export)f(the)g(standard)h(I/O)f (and)h(naming)g(interfaces)g(from)g(a)g(server)h(based)f(internally)e(on)179 222 y ff(vnodes)p fg([5].)75 342 y(Considerable)c(ef)o(fort)g(has)h(been)h (put)d(in)i(the)f(design)g(and)h(implementation)f(of)g(this)g(common)h(librar\ y)l(,)g(and)g(we)g(have)h(been)75 392 y(served)e(very)g(well)f(by)g(this)g (approach)h(in)f(practice.)15 b(Some)9 b(servers)h(\(root)d(name)j(server)o (,)f(pipenet)f(server\))h(are)h(constructed)75 442 y(almost)g(exclusively)f (from)h(modules)f(in)h(this)f(library)l(.)15 b(The)c(only)e(non-common)g(code) h(in)g(these)g(servers)h(is)e(a)i(small)f ff(main)75 492 y fg(procedure)g(for) f(startup)g(and)g(a)i(few)f(lines)f(of)g(code)h(to)g(specialize)g(the)g(opera\ tion)e(of)i(various)f(modules)g(in)g(the)h(library)e(and)75 541 y(supply)k (some)i(operating)d(parameters.)25 b(This)13 b(specialization)f(is)h(normally) f(realized)h(through)f(derivation)f(in)h(the)h(class)75 591 y(hierarchy)d(de\ \256ned)h(by)f(the)g(library)l(.)15 b(Other)10 b(servers)h(\(UFS,)g(NFS,)g (TTY)l(,)f(network\))g(contain)f(a)i(lar)o(ge)g(body)e(of)h(\252internal\272) 75 641 y(specialized)i(code,)g(often)e(inherited)g(from)h(other)f(sources.)18 b(They)11 b(have)h(been)f(integrated)g(in)f(the)h(system)g(in)g(a)g(matter)g (of)75 691 y(hours)f(simply)f(by)h(linking)e(them)i(with)g(an)g(\252upper)o (-layer)r(\272)g(of)g(code)h(from)f(the)g(common)h(library)l(.)137 782 y(Seve\ ral)19 b(of)f(these)h(modules)g(were)g(\256rst)f(developed)g(in)g(earlier)g (versions)g(of)g(our)g(prototype)f(using)g(a)i(straight)75 832 y(\252C\272)c (coding)f(style,)i(but)e(it)g(became)j(quickly)c(evident)i(that)f(this)g(styl\ e)g(was)i(poorly)d(adapted)i(to)f(writing)f(the)i(kind)e(of)75 882 y(polymorp\ hic,)f(reusable)i(code)f(desired)g(for)f(such)h(a)h(library)l(.)23 b(The)14 b (library)d(has)j(since)f(been)g(converted)g(to)f(use)i(object-)75 932 y(orien\ ted)9 b(technology)f(\(\256rst)h(using)g(MachObjects[4],)h(then)f(C++\),)i (augmented)f(by)f(a)i(powerful)d(remote)i(procedure)g(call)75 981 y(package) 16 b(closely)f(integrated)f(with)g(the)h(object-oriented)f(language)h(itself) f(\(see)i(below\).)29 b(W)m(e)16 b(have)f(found)g(that)f(this)75 1031 y(switc\ h)d(in)g(implementation)g(style)g(has)h(considerably)f(simpli\256ed)g(the)g (task)h(of)f(writing)f(new)i(modules)f(and)h(integrating)75 1081 y(them)e(wit\ h)f(the)h(rest)f(of)h(the)g(system.)15 b(Several)c(observations)e(can)h(be)g (made)h(with)e(respect)i(to)e(the)h(use)g(of)g(object-oriented)75 1131 y(tech\ nology)f(in)h(this)f(context[3)o(])137 1222 y(First,)h(multiple-inheritance)e (signi\256cantly)h(simpli\256es)h(the)g(design)g(of)g(the)g(library)l(.)15 b (W)m(e)c(use)g(it)e(in)h(several)h(instances)75 1272 y(for)h(the)h(combinatio\ n)e(of)i(independent)f(interfaces)h(for)f(the)h(de\256nition)e(of)i(items,)g (as)h(suggested)f(above.)23 b(W)m(e)13 b(also)g(use)75 1322 y(it)f(routinely) e(for)i(the)g(combination)g(of)g(independent)f(pieces)j(of)e(functionality)d (for)j(the)h(implementation)e(of)h(items,)i(for)75 1372 y(example)9 b(to)e (add)h(a)g(protection)f(module)g(or)h(a)g(buf)o(fer)g(management)h(module)e (to)h(an)g(item)g(representing)f(a)h(\256le)g(or)g(socket.)14 b(In)75 1421 y (addition,)8 b(in)g(the)h(C++)g(implementation)f(of)g(the)h(library)l(,)g(we) h(use)f(multiple)e(inheritance)i(to)f(allow)g(classes)i(implementing)75 1471 y (various)f(functions)f(in)g(the)h(system)h(to)f(inherit)f(both)g(from)h(base) h(classes)h(in)d(a)i(normal)f(\252implementation\272)g(hierarchy)m(,)h(and)75 1521 y(from)h(classes)h(in)e(an)h(abstract)g(hierarchy)g(representing)f(the)g (standard)h(system)g(interfaces)g(\(used)g(for)f(de\256ning)g(the)h(same)75 1571 y(interfaces)g(on)f(the)g(client-)f(and)h(server-side\).)137 1662 y(Seco\ nd,)15 b(we)f(need)g(some)g(form)g(of)f(runtime)g(type)g(checking)g(in)g(the) g(language.)25 b(Although)12 b(static)h(type)g(checking)75 1712 y(clearly)i (of)n(fers)g(important)f(bene\256ts)g(in)g(terms)h(of)g(program)f(reliability) e(and)j(maintenance,)i(it)c(cannot)i(be)g(used)f(in)g(all)75 1762 y(situation\ s,)c(speci\256cally)h(for)f(the)h(implementation)e(of)i(method)g(invocations) e(across)j(a)f(client-server)g(boundary)l(.)17 b(When)75 1812 y(\256rst)11 b (resolving)f(a)i(name)h(to)d(obtain)h(a)h(reference)h(to)d(an)i(item)f(in)g (our)g(standard)g(naming)g(subsystem,)i(as)f(with)e(the)h(UNIX)75 1861 y fb (open\(\))c fg(primitive,)g(only)g(the)g(name)i(of)e(that)g(item)h(is)f(known\ .)14 b(The)8 b(actual)g(type)g(and)f(the)h(exact)g(collection)f(of)g(operatio\ ns)75 1911 y(exported)j(by)g(that)g(item)g(can)i(only)d(be)i(determined)f(at) h(run-time.)k(This)c(information)d(must)j(then)f(be)h(explicitly)d(obtained) 75 1961 y(by)j(the)h(client)e(upon)h(acquiring)g(or)g(using)f(a)i(proxy)f(for) g(that)g(item.)19 b(The)12 b(total)f(number)g(of)g(de\256ned)h(interfaces)g (makes)h(it)75 2011 y(very)e(impractical)f(to)g(de\256ne)i(a)f(single)f(expor\ ted)g(type)g(that)g(exports)g(the)h(union)e(of)i(all)f(possible)g(operations.) 16 b(Further)m(,)c(if)75 2061 y(we)d(allow)f(for)g(maximum)h(\257exibility)e (and)h(the)h(de\256nition)e(and)i(integration)d(of)j(new)f(servers)i(and)f (interfaces)g(over)f(the)h(life)75 2111 y(the)f(system,)h(even)f(the)g(comple\ te)h(set)f(of)f(possible)g(operations)g(may)i(not)e(be)h(known)f(in)h(advance\ .)15 b(W)o(ith)7 b(the)h(MachObjects)75 2160 y(system,)i(this)d(problem)h(is) g(moot)g(since)h(all)f(method)g(invocations)f(are)j(checked)f(at)g(run-time.) k(In)c(the)f(C++)h(system,)h(we)f(use)75 2210 y(static)h(type)f(checking)h (wherever)g(possible,)g(coupled)f(with)g(a)h(package)h(similar)f(to)f(the)g (NIH)h(class)h(library[2)n(])f(to)f(provide)75 2260 y(the)h(required)g(extend\ ed)g(functionality)e(for)h(run-time)h(type)g(checking.)137 2351 y(Lastly)m (,)17 b(it)c(is)i(very)f(useful)h(to)f(be)h(able)g(to)f(manipulate)g(classes) i(and)f(methods)f(as)h(\256rst-class)g(abstractions)f(in)g(the)75 2401 y(lang\ uage.)27 b(The)15 b(proxy)e(mechanism,)j(which)e(is)g(based)h(on)f(the)g(run-\ time)f(speci\256cation)h(of)g(a)g(class)h(to)f(instantiate)f(in)75 2451 y(a)h (client,)g(obviously)e(creates)j(a)f(need)g(to)f(refer)i(to)e(classes)i(expli\ citly)c(and)j(directly)l(.)26 b(In)13 b(addition,)g(the)h(RPC)f(package)75 2501 y(integrated)j(with)g(the)g(object-oriented)g(programming)g(environment) g(manipulates)g(method)h(references)h(directly)e(at)75 2551 y(run-time)g(to)g (transparently)g(forward)h(some)h(invocations)d(without)g(the)i(need)g(to)g (generate)g(explicit)f(stubs,)j(thereby)75 2600 y(greatly)10 b(enhancing)g (the)g(\257exibility)e(of)i(this)g(system)h(and)f(speeding-up)g(the)g(design) g(and)g(prototyping)e(process.)16 b(Method)75 2650 y(references)h(are)f(also) f(manipulated)f(by)h(the)g(access)i(mediation)d(subsystem,)j(which)d(uses)i (a)f(simple)g(table)g(lookup)f(to)75 2700 y(determine)d(if)f(a)h(given)g(meth\ od)f(invocation)f(is)i(to)f(be)h(allowed)f(for)h(a)g(given)f(caller)h(and)g (object)f(combination.)16 b(As)11 b(is)f(the)954 2804 y(11)p eop %%Page: 12 12 bop 75 42 a fg(case)12 b(for)e(run-time)g(type)g(checking,)h(these)g(feature\ s)g(are)g(handled)f(trivially)f(in)g(MachObjects,)j(and)f(with)e(the)h(help)h (of)f(an)75 91 y(extension)f(package)j(in)e(C++.)75 251 y fh(3.6.)51 b(Hiding) 11 b(Complexity)g(in)h(the)g(T)l(ools)75 371 y fg(In)c(addition)e(to)i(the)f (common)i(library)e(mentioned)g(above,)i(the)f(design)g(also)g(attempts)g(to) f(reduce)i(the)f(complexity)f(directly)75 420 y(visible)i(to)h(implementors)g (by)g(aggressively)h(hiding)d(functionality)g(in)i(a)h(collection)e(of)i(powe\ rful)e(run-time)h(and)g(library)75 470 y(tools.)27 b(These)16 b(tools)d(can)j (be)e(used)h(lar)o(gely)f(as)i(opaque)e(\252black)h(boxes\272;)i(they)d(creat\ e)i(another)e(degree)h(of)g(\256ne-grain)75 520 y(layering)c(in)h(the)g(overa\ ll)f(system)i(design.)20 b(The)12 b(design)g(of)g(many)g(such)g(complicated)h (tools)d(could)i(easily)g(constitute)f(a)75 570 y(research)i(project)e(in)g (itself,)g(considerably)g(beyond)g(the)g(scope)h(of)g(our)f(current)g(goals.) 19 b(Accordingly)l(,)12 b(our)f(focus)h(is)f(not)75 620 y(on)i(developing)e (ideal)i(general-purpose)f(solutions)f(in)i(this)f(area,)j(but)d(on)g(solving) g(the)g(speci\256c)i(problems)f(and)g(issues)75 669 y(raised)e(in)f(our)g(des\ ign,)g(and)h(only)e(as)i(we)g(encounter)g(them.)16 b(Our)10 b(success)i(with) d(this)h(approach)h(so)f(far)h(encourages)g(us)g(to)75 719 y(continue)e(in)h (this)f(direction.)137 811 y(A)k(\256rst)g(example)g(of)g(this)f(approach)h (is)g(the)g(use)g(of)g(the)f(extended)h(cthreads)g(library)f(described)h(abov\ e,)h(that)f(takes)75 860 y(care)g(of)e(many)h(of)f(the)g(dif)o(\256culties)g (inherent)f(in)h(the)g(implementation)g(of)g(emulation)f(libraries.)18 b(The) 13 b(main)e(complexity)75 910 y(introduced)d(at)i(this)f(level)g(is)h(a)g(fac\ ility)e(used)i(to)f(interrupt)f(pending)h(operations)f(in)h(the)h(emulation)f (library)l(.)15 b(This)9 b(facility)75 960 y(must)j(be)h(invoked)e(whenever)i (the)g(reception)f(of)g(a)h(UNIX)f(signal)g(must)g(cause)i(the)e(execution)g (of)g(a)i(system)e(call)h(to)f(be)75 1010 y(prematurely)e(aborted.)15 b(It)9 b (includes)h(a)h(relatively)e(general)h(exception)g(handling)f(mechanism,)j (and)e(it)f(interacts)h(with)f(the)75 1060 y(RPC)h(system)i(to)e(propagate)g (such)h(interruptions)d(to)j(various)f(servers)h(as)h(appropriate.)k(Another) 10 b(example)h(is)g(the)f(set)h(of)75 1110 y(extensions)f(to)f(the)h(object-o\ riented)f(run-time)g(system)i(described)g(in)e(the)h(previous)g(section.)137 1201 y(More)j(importantly)-5 b(,)13 b(the)f(last)h(and)f(probably)f(most)h (far)o(-reaching)h(example)g(is)f(a)h(sophisticated)e(remote)i(procedure)75 1251 y(call)d(package)h(integrated)f(with)f(the)h(object-oriented)e(language) i(used)h(for)e(the)h(implementation)f(of)h(the)g(prototype.)j(This)75 1300 y (RPC)i(package)h(is)f(the)g(key)g(to)g(many)g(of)g(the)g(features)h(mentioned) e(in)h(the)g(rest)g(of)g(this)f(overview)m(.)30 b(It)14 b(transparently)75 1350 y(converts)e(local)h(method)f(invocations)f(into)g(RPC')m(s)i(as)g(appro\ priate,)f(and)h(makes)g(it)f(very)g(easy)i(to)e(de\256ne)h(new)f(RPC')m(s.)75 1400 y(It)j(handles)g(interruptions)d(of)j(arbitrary)f(RPC')m(s)i(through)d (a)j(special)g(message)h(protocol)c(that)i(is)g(implemented)g(in)f(all)75 1450 y(servers.)j(It)11 b(automatically)e(takes)j(care)f(of)g(transferring)e(item) i(references)h(across)g(address)f(spaces)i(and)d(of)h(instantiating)75 1500 y (the)g(correct)h(proxy)f(objects.)18 b(Finally)l(,)13 b(it)d(completely)h(hid\ es)h(all)f(details)g(of)g(the)g(management)i(of)e(ports)g(and)g(Mach)h(IPC)75 1550 y(semantics)g(from)g(its)f(users,)h(including)e(taking)g(care)j(of)f(aut\ omatic)f(garbage-collection)g(of)g(item)g(references)j(using)c(the)75 1599 y (\252no-more-senders\272)h(facility)e(of)h(the)g(Mach)h(IPC)f(system.)137 1691 y(Not)j(surprisingly)-5 b(,)14 b(this)e(RPC)h(package)h(turns)f(out)f(to)h (be)g(very)g(complex,)i(and)e(to)g(be)g(a)h(signi\256cant)e(factor)i(for)e (the)75 1740 y(performance)k(of)e(the)h(prototype.)27 b(However)n(,)17 b(we)e (feel)g(that)f(most)h(of)f(this)g(complexity)g(is)h(essentially)f(unavoidable\ ,)75 1790 y(and)f(would)e(simply)g(have)i(to)f(be)h(distributed)d(through)h (other)h(parts)g(of)g(the)h(system)f(if)g(it)g(was)h(not)f(concentrated)g(in) g(the)75 1840 y(RPC)i(module.)26 b(Therefore,)16 b(we)e(plan)g(to)f(continue) g(to)h(extend)f(the)h(RPC)g(package)h(in)e(directions)g(that)g(we)i(think)d (will)75 1890 y(improve)c(the)g(performance)i(and)e(\257exibility)e(of)j(the) f(overall)g(system.)15 b(Some)9 b(proposed)f(experiments)g(include)g(automati\ c)75 1940 y(initialization)h(of)j(complex)h(proxies,)f(the)g(use)h(of)f(polym\ orphic)f(abstract)h(data)h(types)f(as)h(ar)o(guments)f(for)g(certain)h(calls,) 75 1990 y(and)d(batching)g(of)g(operations)f(to)h(reduce)h(the)f(total)f(numb\ er)h(of)g(messages)i(used)f(in)e(the)h(system.)75 2154 y fh(4.)50 b(Status)11 b(and)h(Evaluation)75 2288 y fg(The)d(main)f(observation)f(to)h(be)g(made)i (at)e(this)f(stage)i(is)f(that)f(the)h(overall)g(architecture)g(appears)h(to) f(be)g(sound)g(and)g(effective.)75 2338 y(The)j(current)f(system)h(prototype) d(for)i(BSD)g(does)h(work)e(with)h(completely)f(modular)h(services)h(and)g (has)f(already)h(reached)75 2388 y(a)g(relatively)e(high)g(level)h(of)g(funct\ ionality)e(and)i(practical)g(utility)-5 b(.)15 b(The)c(\257exible)f(technolog\ y)f(for)g(interface)i(de\256nition)d(is)75 2438 y(adequate)j(and)g(we)g(expec\ t)g(that)f(it)f(will)h(continue)f(to)h(be)h(successful)g(as)g(we)g(re\256ne)h (that)d(prototype.)15 b(The)c(framework)g(for)75 2488 y(integrating)d(servers) k(into)d(the)h(system,)h(centered)g(on)f(the)h(naming)f(and)g(access)j(mediat\ ion)c(components,)i(has)g(proven)f(to)75 2537 y(be)i(extremely)g(useful.)19 b (Finally)-5 b(,)13 b(the)e(use)h(of)g(modular)f(servers)h(has)g(been)g(and)g (continues)f(to)g(be)h(invaluable)e(in)h(helping)75 2587 y(with)i(the)g(incre\ mental)h(construction)e(and)i(debugging)e(of)i(the)f(system:)22 b(we)14 b(rou\ tinely)e(restart)h(or)h(replace)h(individual)75 2637 y(servers)e(while)e(the) g(whole)h(system)g(is)g(operating,)f(and)h(debug)g(them)g(\252on-the-spot\272) e(using)h(the)h(Mach)h(task)e(and)h(thread)75 2687 y(control)d(facilities.) 954 2804 y(12)p eop %%Page: 13 13 bop 137 42 a fg(The)9 b(BSD)e(prototype)f(currently)h(implements)h(all)f(the) g(essential)h(functionality)d(for)j fb(fork\(\))f fg(and)h fb(exec\(\))p fg (,)g(general)75 91 y(\256le)j(access)i(services,)f(signal)e(and)g(process)i (management)f(\(including)e(interrupted)g(system)i(calls\),)g(TTY)h(managemen\ t,)75 141 y(pipes,)g(and)g(UNIX-domain)f(and)h(IP/UDP)g(sockets.)20 b(In)12 b (practice,)h(the)f(system)g(can)h(be)f(started)f(or)h(\252booted\272)g(on)f (top)g(of)75 191 y(the)e ff(POE)i fg(low-level)d(emulator)n(,)i(run)f(an)h (emulated)g(login)e(process,)j(start)e(a)h(shell)f(and)h(run)f(various)f(edit\ ors)h(and)h(common)75 241 y(UNIX)i(commands,)h(up)f(to)f(and)h(including)d (compilation)i(of)g(programs.)20 b(Still)10 b(missing)h(are)i(TCP)f(sockets,) h(raw)f(device)75 291 y(access,)e(and)e(a)g(number)f(of)g(more)h(specialized) g(or)f(less)h(frequently)e(used)h(features)h(in)f(the)g(above)h(subsystems,)g (for)f(example)75 340 y(asynchronous)j(I/O,)h(set-uid)f fb(exec\(\))p fg(,)i (sharing)e(of)h(\256le)g(descriptors)f(between)i(processes,)h(resource)e(cont\ rol,)g(etc.)18 b(W)m(e)75 390 y(continue)8 b(to)h(add)g(new)h(features)f(in)g (these)h(areas)g(and)g(to)e(integrate)h(new)g(facilities.)14 b(The)c(major)g (implementation)d(activity)75 440 y(at)j(the)g(present)h(time)f(is)g(a)h(conv\ ersion)e(to)h(use)h(C++)g(as)g(the)f(standard)g(implementation)f(language.) 137 531 y(W)m(e)15 b(have)f(not)f(made)i(any)f(signi\256cant)f(efforts)g(to)g (improve)h(the)f(robustness)h(and)g(performance)g(of)g(the)g(prototype)75 581 y(until)8 b(its)h(level)h(of)f(functionality)e(was)k(suf)o(\256cient)e(to)g (make)i(such)f(efforts)f(meaningful.)14 b(W)m(e)c(feel)g(that)f(this)g(point) f(has)j(now)75 631 y(been)g(reached,)g(and)f(detailed)g(evaluation)f(and)h (tuning)f(should)g(begin)g(in)h(earnest)g(as)h(soon)f(as)h(the)f(conversion)f (to)h(C++)g(is)75 681 y(complete.)16 b(A)10 b(\256rst)g(short-term)f(objectiv\ e)h(is)g(to)f(make)j(the)e(prototype)e(self-hosting.)137 772 y(The)j(degree)h (to)e(which)g(various)g(elements)h(of)f(this)g(system)h(are)g(reusable)g(is)f (still)f(a)i(matter)g(of)f(discussion,)g(but)g(early)75 822 y(observations)h (are)h(encouraging.)18 b(W)m(e)12 b(feel)g(that)f(the)h(design)f(of)g(many)h (servers)g(and)g(high-level)e(components,)i(coupled)75 872 y(with)k(the)h(gen\ eric)h(service)g(interfaces,)i(has)d(very)g(good)g(potential)e(for)i(\257exib\ ility)e(and)i(reusability)f(under)h(various)75 922 y(operating)7 b(conditions\ .)13 b(In)8 b(addition,)f(the)i(smaller)o(-level)f(reusability)f(of)h(the)g (pieces)h(of)f(the)h(common)f(service)h(library)f(has)75 971 y(already)i(been) g(lar)o(gely)f(demonstrated;)g(we)h(believe)f(that)g(the)g(current)g(prototyp\ e)f(could)h(not)g(have)g(been)h(built)e(without)g(it.)75 1021 y(A)h(desirable) g(further)f(step)h(in)g(this)f(direction)g(should)g(be)h(the)g(construction)e (of)i(a)h(similar)e(library)g(for)g(the)h(implementation)75 1071 y(of)h(emula\ tion)f(libraries.)137 1162 y(On)h(the)f(negative)g(side,)h(the)f(size)h(and)g (complexity)e(of)h(the)h(current)f(prototype)e(are)k(clearly)e(causes)i(for)e (concern.)15 b(The)75 1212 y(memory)f(usage)f(of)g(the)g(multiple)e(servers)j (is)f(lar)o(ge,)h(and)f(the)g(load)g(that)f(they)h(impose)g(on)g(the)g(machin\ e)g(is)g(important.)75 1262 y(Re-compilation)h(of)i(the)g(prototype)e(is)i (slow)m(,)i(due)e(to)f(the)h(volume)g(of)g(code)g(involved.)31 b(Several)17 b (of)f(our)f(low-level)75 1312 y(mechanisms)d(and)f(sub-systems)f(are)i(very)e (lar)o(ge)h(and)g(seem)g(overly)f(complicated,)h(for)f(example)i(the)e(facili\ ty)f(to)h(handle)75 1362 y(interrupted)d(system)i(calls)g(and)f(all)g(the)h (logic)e(around)h(UNIX)h fb(fork\(\))p fg(.)14 b(Hopefully)l(,)9 b(the)f(magn\ itude)g(of)h(these)f(problems)75 1411 y(will)g(decrease)j(as)f(the)g(design)e (and)i(its)f(implementation)f(become)i(more)g(mature,)g(but)f(it)f(is)h(not)g (clear)h(if)f(they)g(will)f(ever)i(be)75 1461 y(completely)g(resolved.)137 1553 y(Finally)l(,)h(we)g(cannot)f(yet)g(draw)g(conclusions)g(on)g(the)g(expe\ riment)g(with)f(the)i(use)f(of)g(\252smart\272)i(emulation)d(libraries)h(in) 75 1602 y(general)g(or)f(the)g(degree)h(to)f(which)g(this)f(general)i(approac\ h)g(can)g(and)f(should)f(be)i(applied.)k(There)d(are)f(practical)f(examples) 75 1652 y(of)14 b(other)g(systems)h(where)g(this)f(approach)h(has)g(been)g (useful[1)o(],)h(but)d(none)i(that)f(goes)g(as)h(far)g(as)g(the)g(present)f (design.)75 1702 y(The)d(dif)n(\256culties)f(in)g(terms)g(of)g(complexity)m (,)g(robustness)g(and)g(increased)h ff(fork\(\))f fg(overhead)h(cannot)f(be)h (ignored.)j(W)m(e)c(will)75 1752 y(reserve)f(\256nal)f(judgment)f(on)g(this)g (experiment)h(until)e(more)j(experience)g(has)f(been)h(gained)e(with)g(implem\ enting)g(and)h(using)75 1802 y(systems)j(that)e(rely)h(on)g(this)g(aspect)h (of)f(the)g(architecture.)75 1966 y fh(5.)50 b(Conclusion)75 2100 y fg(W)m (e)13 b(are)g(conducting)e(experiments)h(and)g(proposing)f(a)i(number)f(of)g (techniques)g(with)f(the)h(goals)g(of)g(helping)f(the)h(devel-)75 2150 y(opme\ nt)f(of)g(emulation)f(systems,)j(and)e(of)g(minimizing)f(the)h(duplication)f (of)h(ef)o(fort)f(for)h(the)g(implementation)f(of)h(several)75 2200 y(indepen\ dent)j(emulations.)31 b(There)16 b(is)f(no)g(question)g(that)f(achieving)h (these)h(goals)f(is)h(highly)d(desirable;)18 b(the)d(present)75 2250 y(effort\ ,)g(although)f(still)g(incomplete,)i(shows)f(that)g(there)g(are)h(many)f(oppo\ rtunities)e(to)h(make)j(signi\256cant)d(progress)h(in)75 2300 y(this)c(direct\ ion.)19 b(Furthermore,)12 b(several)g(of)g(the)g(proposed)f(general-purpose)g (components)h(or)f(mechanisms)j(constitute)75 2349 y(signi\256cant)h(practica\ l)g(steps)h(toward)f(improving)e(the)j(current)f(state)h(of)f(the)g(technolog\ y)l(,)i(and)f(the)f(results)g(from)h(our)75 2399 y(BSD)11 b(prototype)f(encou\ rage)i(us)f(to)g(continue)f(this)h(ef)o(fort.)18 b(W)m(e)11 b(expect)h(that)f (the)g(experiences)i(from)e(this)f(investigation,)75 2449 y(combined)i(with)e (the)i(lessons)f(from)h(other)f(efforts)g(in)g(the)g(same)i(area,)h(will)c (eventually)h(lead)h(to)f(the)h(development)f(of)h(a)75 2499 y(complete)g(pra\ ctical)g(framework)f(for)h(the)f(implementation)f(of)i(many)g(emulators,)g (and)g(maybe)g(to)f(the)g(emer)q(gence)h(of)g(a)75 2549 y(new)f(software)f (industry)e(for)i(the)g(production)e(of)i(replaceable,)i(modular)e(components) g(for)g(Mach-based)h(systems.)954 2804 y(13)p eop %%Page: 14 14 bop 75 42 a fh(Acknowledgments)75 176 y fg(Many)9 b(people)f(at)h(CMU)g(and) g(at)g(the)f(Research)i(Institute)d(of)i(OSF)g(have)g(participated)f(in)g(var\ ious)h(stages)g(of)f(the)h(design)f(of)75 225 y(the)h(system)g(and)g(the)f (implementation)g(of)h(successive)h(versions)e(of)h(the)f(BSD)h(prototype.)k (Beside)c(the)g(authors,)f(they)h(are:)75 275 y(Robert)f(Baron,)i(Alessandro) f(Forin,)g(Jef)o(frey)g(Heller)n(,)h(Michael)g(Jones,)g(Keith)e(Loepere,)j (Douglas)e(Orr)n(,)h(Richard)e(Rashid,)75 325 y(Franklin)14 b(Reynolds)f(and) i(Richard)f(Sanzi.)29 b(In)14 b(addition,)h(the)f(whole)h(T)o(rusted-Mach)f (team)i(at)f(T)n(rusted)g(Information)75 375 y(Systems)c(has)f(often)g(contri\ buted)f(many)h(valuable)g(insights.)75 540 y fh(Refer)o(ences)96 649 y fg([1]) 20 b(David)12 b(Golub,)g(Randall)f(Dean,)j(Alessandro)f(Forin,)f(and)g(Richar\ d)g(Rashid.)20 b(Unix)11 b(as)i(an)g(application)e(program.)165 699 y(In)f ff (Pr)o(oceedings)g(of)g(the)g(1990)f(Summer)i(Usenix)p fg(.)g(Usenix,)f(June)h (1990.)96 782 y([2])20 b(Keith)c(E.)h(Gorlen,)h(Sanford)e(M.)h(Orlow)m(,)h (and)f(Perry)f(S.)h(Plexico.)32 b ff(Data)16 b(Abstraction)f(and)h(Object-Ori\ ented)165 831 y(Pr)o(ogramming)9 b(in)g(C++)p fg(.)15 b(John)10 b(W)o(iley)f (and)i(Sons,)f(1990.)96 914 y([3])20 b(Paulo)11 b(Guedes)h(and)g(Daniel)f(P)l (.)h(Julin.)18 b(Object-oriented)10 b(interfaces)i(in)f(the)g(Mach)h(3.0)g (multi-server)f(system.)19 b(T)m(o)165 964 y(appear)c(in)f(the)g(proceedings) g(of)g(the)g(Second)h(International)d(W)m(orkshop)h(on)h(Object-Orientation)e (in)i(Operating)165 1014 y(Systems,)d(Palo)f(Alto,)g(1991.)96 1097 y([4])20 b (Daniel)7 b(P)l(.)h(Julin)f(and)g(Richard)h(F)l(.)h(Rashid.)k(MachObjects.)i (Internal)7 b(document,)i(Mach)f(Project,)g(Carnegie)g(Mellon)165 1147 y(Univ\ ersity)-5 b(,)11 b(1989.)96 1230 y([5])20 b(S.)10 b(R.)g(Kleiman.)15 b(Vnodes\ :)g(An)9 b(architecture)h(for)f(multiple)g(\256le)h(system)g(types)g(in)f(Sun) g(UNIX.)15 b(In)10 b ff(Pr)o(oceedings)g(of)165 1280 y(the)g(1986)f(summer)i (Usenix)p fg(,)g(pages)g(238\261247.)e(Usenix,)i(1986.)96 1363 y([6])20 b(Ope\ n)10 b(Software)g(Foundation.)k ff(OSF/1)c(Network)g(Pr)o(ogrammer)q(')-5 b (s)10 b(Guide)p fg(,)g(1990.)96 1446 y([7])20 b(Larry)12 b(L.)h(Peterson,)g (Norman)f(C.)g(Hutchinson,)g(Sean)h(W)l(.)f(O`Malley)m(,)h(and)f(Herman)h(C.) f(Rao.)20 b(The)13 b ff(x)p fg(-Kernel:)18 b(A)165 1496 y(platform)9 b(for)h (accessing)h(internet)f(resources.)16 b ff(IEEE)11 b(Computer)p fg(,)f(23\(5\ \):23\26133,)e(May)i(1990.)96 1579 y([8])20 b(Richard)11 b(Rashid,)h(Robert)f (Baron,)i(Alessandro)f(Forin,)f(David)h(Golub,)f(Michael)h(Jones,)h(Daniel)f (Julin,)g(Douglas)165 1628 y(Orr)n(,)e(and)f(Richard)g(Sanzi.)15 b(Mach:)f (A)c(foundation)d(for)h(open)h(systems.)16 b(In)9 b ff(Pr)o(oceedings)g(of)f (the)h(Second)g(W)l(orkshop)165 1678 y(on)h(W)l(orkstation)e(Operating)h(Syst\ ems)p fg(,)j(pages)e(109\261113.)f(IEEE)j(Computer)d(Society)m(,)i(September) g(1989.)96 1761 y([9])20 b(Richard)12 b(Rashid,)g(Gerald)h(Malan,)g(David)f (Golub,)g(and)g(Robert)f(Baron.)20 b(DOS)13 b(as)g(a)g(Mach)f(3.0)h(applicati\ on.)19 b(T)m(o)165 1811 y(appear)11 b(in)f(the)g(proceedings)g(of)g(the)g(Sec\ ond)g(USENIX)h(Mach)g(Symposium,)f(November)g(1991.)75 1894 y([10])20 b(Marc) 13 b(Shapiro.)19 b(Structure)12 b(and)g(encapsulation)g(in)f(distributed)f (computing)h(systems:)19 b(the)12 b(Proxy)f(principle.)19 b(In)165 1944 y ff (The)11 b(6th)e(International)e(Confer)n(ence)12 b(on)e(Distributed)e(Computi\ ng)g(Systems)p fg(,)j(Boston)e(\(USA\),)i(May)f(1986.)75 2027 y([11])20 b(T)o (rusted)10 b(Information)e(Systems,)j(Inc.)16 b(T)o(rusted)10 b(Mach)g(system) h(architecture.)k(Internal)10 b(Report,)g(April)f(1990.)75 2110 y([12])20 b (B.)8 b(W)m(elch)g(and)h(J.)f(Ousterhout.)13 b(Pre\256x)c(tables:)k(A)8 b(sim\ ple)g(mechanism)h(for)f(locating)f(\256les)h(in)g(a)h(distributed)c(system.) 165 2160 y(In)k ff(Pr)o(oceedings)h(of)f(the)h(6th)e(International)f(Confer)n (ence)k(on)e(Distributed)f(Computing)f(Systems)p fg(,)k(pages)f(184\261189.) 165 2210 y(IEEE,)i(May)e(1986.)954 2804 y(14)p eop %%Trailer end %%EOF