%!PS-Adobe-2.0
%%Creator: dvips(k) 5.85 Copyright 1999 Radical Eye Software
%%Title: MS-CIS-97-04.dvi
%%Pages: 11
%%PageOrder: Ascend
%%BoundingBox: 0 0 612 792
%%DocumentFonts: Times-Bold Times-Roman Times-Italic Courier
%%EndComments
%DVIPSWebPage: (www.radicaleye.com)
%DVIPSCommandLine: dvips -o MS-CIS-97-04.ps MS-CIS-97-04.dvi
%DVIPSParameters: dpi=600, compressed
%DVIPSSource:  TeX output 1999.10.13:2124
%%BeginProcSet: texc.pro
%!
/TeXDict 300 dict def TeXDict begin/N{def}def/B{bind def}N/S{exch}N/X{S
N}B/A{dup}B/TR{translate}N/isls false N/vsize 11 72 mul N/hsize 8.5 72
mul N/landplus90{false}def/@rigin{isls{[0 landplus90{1 -1}{-1 1}ifelse 0
0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{
landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize
mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR[
matrix currentmatrix{A A round sub abs 0.00001 lt{round}if}forall round
exch round exch]setmatrix}N/@landscape{/isls true N}B/@manualfeed{
statusdict/manualfeed true put}B/@copies{/#copies X}B/FMat[1 0 0 -1 0 0]
N/FBB[0 0 0 0]N/nn 0 N/IEn 0 N/ctr 0 N/df-tail{/nn 8 dict N nn begin
/FontType 3 N/FontMatrix fntrx N/FontBBox FBB N string/base X array
/BitMaps X/BuildChar{CharBuilder}N/Encoding IEn N end A{/foo setfont}2
array copy cvx N load 0 nn put/ctr 0 N[}B/sf 0 N/df{/sf 1 N/fntrx FMat N
df-tail}B/dfs{div/sf X/fntrx[sf 0 0 sf neg 0 0]N df-tail}B/E{pop nn A
definefont setfont}B/Cw{Cd A length 5 sub get}B/Ch{Cd A length 4 sub get
}B/Cx{128 Cd A length 3 sub get sub}B/Cy{Cd A length 2 sub get 127 sub}
B/Cdx{Cd A length 1 sub get}B/Ci{Cd A type/stringtype ne{ctr get/ctr ctr
1 add N}if}B/id 0 N/rw 0 N/rc 0 N/gp 0 N/cp 0 N/G 0 N/CharBuilder{save 3
1 roll S A/base get 2 index get S/BitMaps get S get/Cd X pop/ctr 0 N Cdx
0 Cx Cy Ch sub Cx Cw add Cy setcachedevice Cw Ch true[1 0 0 -1 -.1 Cx
sub Cy .1 sub]/id Ci N/rw Cw 7 add 8 idiv string N/rc 0 N/gp 0 N/cp 0 N{
rc 0 ne{rc 1 sub/rc X rw}{G}ifelse}imagemask restore}B/G{{id gp get/gp
gp 1 add N A 18 mod S 18 idiv pl S get exec}loop}B/adv{cp add/cp X}B
/chg{rw cp id gp 4 index getinterval putinterval A gp add/gp X adv}B/nd{
/cp 0 N rw exit}B/lsh{rw cp 2 copy get A 0 eq{pop 1}{A 255 eq{pop 254}{
A A add 255 and S 1 and or}ifelse}ifelse put 1 adv}B/rsh{rw cp 2 copy
get A 0 eq{pop 128}{A 255 eq{pop 127}{A 2 idiv S 128 and or}ifelse}
ifelse put 1 adv}B/clr{rw cp 2 index string putinterval adv}B/set{rw cp
fillstr 0 4 index getinterval putinterval adv}B/fillstr 18 string 0 1 17
{2 copy 255 put pop}for N/pl[{adv 1 chg}{adv 1 chg nd}{1 add chg}{1 add
chg nd}{adv lsh}{adv lsh nd}{adv rsh}{adv rsh nd}{1 add adv}{/rc X nd}{
1 add set}{1 add clr}{adv 2 chg}{adv 2 chg nd}{pop nd}]A{bind pop}
forall N/D{/cc X A type/stringtype ne{]}if nn/base get cc ctr put nn
/BitMaps get S ctr S sf 1 ne{A A length 1 sub A 2 index S get sf div put
}if put/ctr ctr 1 add N}B/I{cc 1 add D}B/bop{userdict/bop-hook known{
bop-hook}if/SI save N @rigin 0 0 moveto/V matrix currentmatrix A 1 get A
mul exch 0 get A mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N/eop{
SI restore userdict/eop-hook known{eop-hook}if showpage}N/@start{
userdict/start-hook known{start-hook}if pop/VResolution X/Resolution X
1000 div/DVImag X/IEn 256 array N 2 string 0 1 255{IEn S A 360 add 36 4
index cvrs cvn put}for pop 65781.76 div/vsize X 65781.76 div/hsize X}N
/p{show}N/RMat[1 0 0 -1 0 0]N/BDot 260 string N/Rx 0 N/Ry 0 N/V{}B/RV/v{
/Ry X/Rx X V}B statusdict begin/product where{pop false[(Display)(NeXT)
(LaserWriter 16/600)]{A length product length le{A length product exch 0
exch getinterval eq{pop true exit}if}{pop}ifelse}forall}{false}ifelse
end{{gsave TR -.1 .1 TR 1 1 scale Rx Ry false RMat{BDot}imagemask
grestore}}{{gsave TR -.1 .1 TR Rx Ry scale 1 1 false RMat{BDot}
imagemask grestore}}ifelse B/QV{gsave newpath transform round exch round
exch itransform moveto Rx 0 rlineto 0 Ry neg rlineto Rx neg 0 rlineto
fill grestore}B/a{moveto}B/delta 0 N/tail{A/delta X 0 rmoveto}B/M{S p
delta add tail}B/b{S p tail}B/c{-4 M}B/d{-3 M}B/e{-2 M}B/f{-1 M}B/g{0 M}
B/h{1 M}B/i{2 M}B/j{3 M}B/k{4 M}B/w{0 rmoveto}B/l{p -4 w}B/m{p -3 w}B/n{
p -2 w}B/o{p -1 w}B/q{p 1 w}B/r{p 2 w}B/s{p 3 w}B/t{p 4 w}B/x{0 S
rmoveto}B/y{3 2 roll p a}B/bos{/SS save N}B/eos{SS restore}B end

%%EndProcSet
%%BeginProcSet: 8r.enc
% @@psencodingfile@{
%   author = "S. Rahtz, P. MacKay, Alan Jeffrey, B. Horn, K. Berry",
%   version = "0.6",
%   date = "1 July 1998",
%   filename = "8r.enc",
%   email = "tex-fonts@@tug.org",
%   docstring = "Encoding for TrueType or Type 1 fonts
%                to be used with TeX."
% @}
%
% Idea is to have all the characters normally included in Type 1 fonts
% available for typesetting. This is effectively the characters in Adobe
% Standard Encoding + ISO Latin 1 + extra characters from Lucida.
%
% Character code assignments were made as follows:
%
% (1) the Windows ANSI characters are almost all in their Windows ANSI
% positions, because some Windows users cannot easily reencode the
% fonts, and it makes no difference on other systems. The only Windows
% ANSI characters not available are those that make no sense for
% typesetting -- rubout (127 decimal), nobreakspace (160), softhyphen
% (173). quotesingle and grave are moved just because it's such an
% irritation not having them in TeX positions.
%
% (2) Remaining characters are assigned arbitrarily to the lower part
% of the range, avoiding 0, 10 and 13 in case we meet dumb software.
%
% (3) Y&Y Lucida Bright includes some extra text characters; in the
% hopes that other PostScript fonts, perhaps created for public
% consumption, will include them, they are included starting at 0x12.
%
% (4) Remaining positions left undefined are for use in (hopefully)
% upward-compatible revisions, if someday more characters are generally
% available.
%
% (5) hyphen appears twice for compatibility with both
% ASCII and Windows.
%
/TeXBase1Encoding [
% 0x00 (encoded characters from Adobe Standard not in Windows 3.1)
  /.notdef /dotaccent /fi /fl
  /fraction /hungarumlaut /Lslash /lslash
  /ogonek /ring /.notdef
  /breve /minus /.notdef
% These are the only two remaining unencoded characters, so may as
% well include them.
  /Zcaron /zcaron
% 0x10
 /caron /dotlessi
% (unusual TeX characters available in, e.g., Lucida Bright)
 /dotlessj /ff /ffi /ffl
 /.notdef /.notdef /.notdef /.notdef
 /.notdef /.notdef /.notdef /.notdef
 % very contentious; it's so painful not having quoteleft and quoteright
 % at 96 and 145 that we move the things normally found there to here.
 /grave /quotesingle
% 0x20 (ASCII begins)
 /space /exclam /quotedbl /numbersign
 /dollar /percent /ampersand /quoteright
 /parenleft /parenright /asterisk /plus /comma /hyphen /period /slash
% 0x30
 /zero /one /two /three /four /five /six /seven
 /eight /nine /colon /semicolon /less /equal /greater /question
% 0x40
 /at /A /B /C /D /E /F /G /H /I /J /K /L /M /N /O
% 0x50
 /P /Q /R /S /T /U /V /W
 /X /Y /Z /bracketleft /backslash /bracketright /asciicircum /underscore
% 0x60
 /quoteleft /a /b /c /d /e /f /g /h /i /j /k /l /m /n /o
% 0x70
 /p /q /r /s /t /u /v /w
 /x /y /z /braceleft /bar /braceright /asciitilde
 /.notdef % rubout; ASCII ends
% 0x80
 /.notdef /.notdef /quotesinglbase /florin
 /quotedblbase /ellipsis /dagger /daggerdbl
 /circumflex /perthousand /Scaron /guilsinglleft
 /OE /.notdef /.notdef /.notdef
% 0x90
 /.notdef /.notdef /.notdef /quotedblleft
 /quotedblright /bullet /endash /emdash
 /tilde /trademark /scaron /guilsinglright
 /oe /.notdef /.notdef /Ydieresis
% 0xA0
 /.notdef % nobreakspace
 /exclamdown /cent /sterling
 /currency /yen /brokenbar /section
 /dieresis /copyright /ordfeminine /guillemotleft
 /logicalnot
 /hyphen % Y&Y (also at 45); Windows' softhyphen
 /registered
 /macron
% 0xD0
 /degree /plusminus /twosuperior /threesuperior
 /acute /mu /paragraph /periodcentered
 /cedilla /onesuperior /ordmasculine /guillemotright
 /onequarter /onehalf /threequarters /questiondown
% 0xC0
 /Agrave /Aacute /Acircumflex /Atilde /Adieresis /Aring /AE /Ccedilla
 /Egrave /Eacute /Ecircumflex /Edieresis
 /Igrave /Iacute /Icircumflex /Idieresis
% 0xD0
 /Eth /Ntilde /Ograve /Oacute
 /Ocircumflex /Otilde /Odieresis /multiply
 /Oslash /Ugrave /Uacute /Ucircumflex
 /Udieresis /Yacute /Thorn /germandbls
% 0xE0
 /agrave /aacute /acircumflex /atilde
 /adieresis /aring /ae /ccedilla
 /egrave /eacute /ecircumflex /edieresis
 /igrave /iacute /icircumflex /idieresis
% 0xF0
 /eth /ntilde /ograve /oacute
 /ocircumflex /otilde /odieresis /divide
 /oslash /ugrave /uacute /ucircumflex
 /udieresis /yacute /thorn /ydieresis
] def

%%EndProcSet
%%BeginProcSet: texps.pro
%!
TeXDict begin/rf{findfont dup length 1 add dict begin{1 index/FID ne 2
index/UniqueID ne and{def}{pop pop}ifelse}forall[1 index 0 6 -1 roll
exec 0 exch 5 -1 roll VResolution Resolution div mul neg 0 0]/Metrics
exch def dict begin Encoding{exch dup type/integertype ne{pop pop 1 sub
dup 0 le{pop}{[}ifelse}{FontMatrix 0 get div Metrics 0 get div def}
ifelse}forall Metrics/Metrics currentdict end def[2 index currentdict
end definefont 3 -1 roll makefont/setfont cvx]cvx def}def/ObliqueSlant{
dup sin S cos div neg}B/SlantFont{4 index mul add}def/ExtendFont{3 -1
roll mul exch}def/ReEncodeFont{CharStrings rcheck{/Encoding false def
dup[exch{dup CharStrings exch known not{pop/.notdef/Encoding true def}
if}forall Encoding{]exch pop}{cleartomark}ifelse}if/Encoding exch def}
def end

%%EndProcSet
%%BeginProcSet: special.pro
%!
TeXDict begin/SDict 200 dict N SDict begin/@SpecialDefaults{/hs 612 N
/vs 792 N/ho 0 N/vo 0 N/hsc 1 N/vsc 1 N/ang 0 N/CLIP 0 N/rwiSeen false N
/rhiSeen false N/letter{}N/note{}N/a4{}N/legal{}N}B/@scaleunit 100 N
/@hscale{@scaleunit div/hsc X}B/@vscale{@scaleunit div/vsc X}B/@hsize{
/hs X/CLIP 1 N}B/@vsize{/vs X/CLIP 1 N}B/@clip{/CLIP 2 N}B/@hoffset{/ho
X}B/@voffset{/vo X}B/@angle{/ang X}B/@rwi{10 div/rwi X/rwiSeen true N}B
/@rhi{10 div/rhi X/rhiSeen true N}B/@llx{/llx X}B/@lly{/lly X}B/@urx{
/urx X}B/@ury{/ury X}B/magscale true def end/@MacSetUp{userdict/md known
{userdict/md get type/dicttype eq{userdict begin md length 10 add md
maxlength ge{/md md dup length 20 add dict copy def}if end md begin
/letter{}N/note{}N/legal{}N/od{txpose 1 0 mtx defaultmatrix dtransform S
atan/pa X newpath clippath mark{transform{itransform moveto}}{transform{
itransform lineto}}{6 -2 roll transform 6 -2 roll transform 6 -2 roll
transform{itransform 6 2 roll itransform 6 2 roll itransform 6 2 roll
curveto}}{{closepath}}pathforall newpath counttomark array astore/gc xdf
pop ct 39 0 put 10 fz 0 fs 2 F/|______Courier fnt invertflag{PaintBlack}
if}N/txpose{pxs pys scale ppr aload pop por{noflips{pop S neg S TR pop 1
-1 scale}if xflip yflip and{pop S neg S TR 180 rotate 1 -1 scale ppr 3
get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip
yflip not and{pop S neg S TR pop 180 rotate ppr 3 get ppr 1 get neg sub
neg 0 TR}if yflip xflip not and{ppr 1 get neg ppr 0 get neg TR}if}{
noflips{TR pop pop 270 rotate 1 -1 scale}if xflip yflip and{TR pop pop
90 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get
neg sub neg TR}if xflip yflip not and{TR pop pop 90 rotate ppr 3 get ppr
1 get neg sub neg 0 TR}if yflip xflip not and{TR pop pop 270 rotate ppr
2 get ppr 0 get neg sub neg 0 S TR}if}ifelse scaleby96{ppr aload pop 4
-1 roll add 2 div 3 1 roll add 2 div 2 copy TR .96 dup scale neg S neg S
TR}if}N/cp{pop pop showpage pm restore}N end}if}if}N/normalscale{
Resolution 72 div VResolution 72 div neg scale magscale{DVImag dup scale
}if 0 setgray}N/psfts{S 65781.76 div N}N/startTexFig{/psf$SavedState
save N userdict maxlength dict begin/magscale true def normalscale
currentpoint TR/psf$ury psfts/psf$urx psfts/psf$lly psfts/psf$llx psfts
/psf$y psfts/psf$x psfts currentpoint/psf$cy X/psf$cx X/psf$sx psf$x
psf$urx psf$llx sub div N/psf$sy psf$y psf$ury psf$lly sub div N psf$sx
psf$sy scale psf$cx psf$sx div psf$llx sub psf$cy psf$sy div psf$ury sub
TR/showpage{}N/erasepage{}N/copypage{}N/p 3 def @MacSetUp}N/doclip{
psf$llx psf$lly psf$urx psf$ury currentpoint 6 2 roll newpath 4 copy 4 2
roll moveto 6 -1 roll S lineto S lineto S lineto closepath clip newpath
moveto}N/endTexFig{end psf$SavedState restore}N/@beginspecial{SDict
begin/SpecialSave save N gsave normalscale currentpoint TR
@SpecialDefaults count/ocount X/dcount countdictstack N}N/@setspecial{
CLIP 1 eq{newpath 0 0 moveto hs 0 rlineto 0 vs rlineto hs neg 0 rlineto
closepath clip}if ho vo TR hsc vsc scale ang rotate rwiSeen{rwi urx llx
sub div rhiSeen{rhi ury lly sub div}{dup}ifelse scale llx neg lly neg TR
}{rhiSeen{rhi ury lly sub div dup scale llx neg lly neg TR}if}ifelse
CLIP 2 eq{newpath llx lly moveto urx lly lineto urx ury lineto llx ury
lineto closepath clip}if/showpage{}N/erasepage{}N/copypage{}N newpath}N
/@endspecial{count ocount sub{pop}repeat countdictstack dcount sub{end}
repeat grestore SpecialSave restore end}N/@defspecial{SDict begin}N
/@fedspecial{end}B/li{lineto}B/rl{rlineto}B/rc{rcurveto}B/np{/SaveX
currentpoint/SaveY X N 1 setlinecap newpath}N/st{stroke SaveX SaveY
moveto}N/fil{fill SaveX SaveY moveto}N/ellipse{/endangle X/startangle X
/yrad X/xrad X/savematrix matrix currentmatrix N TR xrad yrad scale 0 0
1 startangle endangle arc savematrix setmatrix}N end

%%EndProcSet
TeXDict begin 40258431 52099146 1000 600 600 (MS-CIS-97-04.dvi)
@start /Fa 141[26 2[33 33 1[18 29 5[29 101[{
TeXBase1Encoding ReEncodeFont}6 66.4176 /Times-Italic
rf
%DVIPSBitmapFont: Fb cmr10 10 4
/Fb 4 92 df<146014E0EB01C0EB0380EB0700130E131E5B5BA25B485AA2485AA212075B
120F90C7FCA25A121EA2123EA35AA65AB2127CA67EA3121EA2121F7EA27F12077F1203A2
6C7EA26C7E1378A27F7F130E7FEB0380EB01C0EB00E01460135278BD20>40
D<12C07E12707E7E7E120F6C7E6C7EA26C7E6C7EA21378A2137C133C133E131EA2131F7F
A21480A3EB07C0A6EB03E0B2EB07C0A6EB0F80A31400A25B131EA2133E133C137C1378A2
5BA2485A485AA2485A48C7FC120E5A5A5A5A5A13527CBD20>I<EB01C013031307131F13
FFB5FCA2131F1200B3B3A8497E007FB512F0A31C3879B72A>49 D<EAFFF8A4EAF000B3B3
B3B3A3EAFFF8A40D5378BD17>91 D E
%EndDVIPSBitmapFont
%DVIPSBitmapFont: Fc cmr7 7 1
/Fc 1 51 df<13FF000313E0380E03F0381800F848137C48137E00787F12FC6CEB1F80A4
127CC7FC15005C143E147E147C5C495A495A5C495A010EC7FC5B5B903870018013E0EA01
80390300030012065A001FB5FC5A485BB5FCA219267DA521>50 D
E
%EndDVIPSBitmapFont
/Fd 133[44 50 50 1[50 55 33 39 44 1[55 50 55 83 28 55
33 28 55 50 33 44 55 44 55 50 9[100 1[72 66 55 72 1[61
78 72 94 66 78 1[39 3[66 1[72 66 72 7[50 50 50 50 50
50 50 50 50 50 1[25 33 45[{TeXBase1Encoding ReEncodeFont}52
99.6264 /Times-Bold rf
%DVIPSBitmapFont: Fe cmmi10 10 32
/Fe 32 123 df<EB0380D907E01307010FEC0F80161F5CA2011F143FA24A1400A2013F5C
A291C7127EA24914FEA2017E5CA201FE1301A2495CA200011403A249ECF018A200031407
1738EEE030150F00071670031F1360153F6D017713E0486C9038E3E1C0903AFF03C1F380
903ACFFF00FF00D9C3FC133ED81FC0C9FCA25BA2123FA290CAFCA25AA2127EA212FEA25A
A212702D377EA432>22 D<121C127FEAFF80A213C0A3127F121C1200A412011380A21203
13005A1206120E5A5A5A12600A19798817>59 D<1760177017F01601A21603A21607160F
A24C7EA216331673166316C3A2ED0183A2ED0303150683150C160115181530A21560A215
C014011580DA03007FA202061300140E140C5C021FB5FC5CA20260C7FC5C83495A8349C8
FC1306A25BA25B13385B01F01680487E000716FFB56C013F13FF5EA2383C7DBB3E>65
D<0103B77E4916F018FC903B0007F80003FE4BEB00FFF07F80020FED3FC0181F4B15E0A2
141FA25DA2143F19C04B143F1980027F157F190092C812FE4D5A4A4A5AEF0FF04AEC1FC0
05FFC7FC49B612FC5F02FCC7B4FCEF3FC00103ED0FE0717E5C717E1307844A1401A2130F
17035CA2131F4D5A5C4D5A133F4D5A4A4A5A4D5A017F4BC7FC4C5A91C7EA07FC49EC3FF0
B812C094C8FC16F83B397DB83F>I<9339FF8001C0030F13E0037F9038F80380913A01FF
807E07913A07F8000F0FDA1FE0EB079FDA3F80903803BF0002FFC76CB4FCD901FC80495A
4948157E495A495A4948153E017F163C49C9FC5B1201484816385B1207485A1830121F49
93C7FCA2485AA3127F5BA312FF90CCFCA41703A25F1706A26C160E170C171C5F6C7E5F00
1F5E6D4A5A6C6C4A5A16076C6C020EC8FC6C6C143C6C6C5C6CB4495A90393FE00FC0010F
B5C9FC010313FC9038007FC03A3D7CBA3B>I<0103B7FC4916E018F8903B0007F80007FE
4BEB00FFF03F80020FED1FC0180F4B15E0F007F0021F1503A24B15F81801143F19FC5DA2
147FA292C8FCA25C18035CA2130119F84A1507A2130319F04A150FA2010717E0181F4A16
C0A2010FEE3F80A24AED7F00187E011F16FE4D5A4A5D4D5A013F4B5A4D5A4A4A5A057FC7
FC017F15FEEE03FC91C7EA0FF049EC7FC0B8C8FC16FC16C03E397DB845>I<0103B812F0
5BA290260007F8C7123F4B1407F003E0020F150118005DA2141FA25D19C0143FA24B1330
A2027F1470190092C7126017E05C16014A495A160F49B6FCA25F9138FC000F01031407A2
4A6DC8FCA201075C18034A130660010F160693C7FC4A150E180C011F161C18184A1538A2
013F5E18F04A4A5AA2017F15074D5A91C8123F49913803FF80B9FCA295C7FC3C397DB83D
>I<0107B512FCA216F890390007F8005DA2140FA25DA2141FA25DA2143FA25DA2147FA2
92C7FCA25CA25CA21301A25CA21303A25CA21307A25CA2130FA25CA2131FA25CA2133FA2
5CA2137FA291C8FC497EB6FCA326397DB824>73 D<0103B6FC5B5E90260007FCC8FC5D5D
140FA25DA2141FA25DA2143FA25DA2147FA292C9FCA25CA25CA21301A25CA21303A25CA2
130718404A15C0A2010F150118804A1403A2011F16005F4A1406170E013F151E171C4A14
3C177C017F5D160391C7120F49EC7FF0B8FCA25F32397DB839>76
D<4BB4FC031F13F09238FE01FC913903F0007EDA07C0EB1F80DA1F80EB0FC0023EC7EA07
E002FCEC03F0495A4948EC01F8495A4948EC00FC495A49C912FE49167E13FE49167F1201
485AA2485AA2120F5B001F17FFA2485AA34848ED01FEA400FFEE03FC90C9FCA2EF07F8A2
EF0FF0A218E0171F18C0EF3F806C167F180017FE4C5A6C6C5D1603001F4B5A6D4A5A000F
ED1F806C6C4AC7FC6D147E0003EC01F8D801FC495AD8007EEB0FC090263F807FC8FC9038
07FFF801001380383D7CBA3F>79 D<0103B612F849EDFF8018E0903B0007F8001FF84BEB
03FCEF00FE020F157FA24BEC3F80A2021F16C0A25DA2143FF07F805DA2027FEDFF006092
C7485A4D5A4A4A5A4D5A4AEC1F80057FC7FC0101EC07F891B612E094C8FC9139FC000FC0
0103EC03F0707E4A6D7E831307177E5C177F010F5D5F5CA2011F1401A25CA2133F16034A
4A1360A2017F17E019C091C71401496C01011480B61503933900FE0700EF7E0ECAEA1FFC
EF07F03B3B7DB83F>82 D<92391FE00380DBFFFC130002036D5A91390FE01F8F91393F00
07DF027EEB01FE02F81300495A4948147E177C4948143C495AA2011F153891C8FCA34915
30A28094C7FC80806D7E14FEECFFE06D13FE6DEBFFC06D14F06D806D80021F7F02037FEC
003F03037F1500167F163F161FA3120C160FA2001C151F94C7FCA3003C153EA25E003E5D
127E007F4A5A6D495A6DEB0FC0D8F9F0495AD8F0FE01FEC8FC39E03FFFF8010F13E0D8C0
0190C9FC313D7CBA33>I<0003B812FEA25A903AF8003FC00101C0913880007E4848163C
90C7007F141C121E001C92C7FCA2485CA200305C007017180060130112E0485CA21403C7
16005DA21407A25DA2140FA25DA2141FA25DA2143FA25DA2147FA292C9FCA25CA25CA213
01A25CA21303A25CEB0FFC003FB6FC5AA237397EB831>I<147E903803FF8090390FC1C3
8090391F00EFC0017E137F49133F485A4848EB1F8012075B000F143F48481400A2485A5D
007F147E90C7FCA215FE485C5AA214015D48150CA21403EDF01C16181407007C1538007E
010F1330003E131F027B13706C01E113E03A0F83C0F9C03A03FF007F80D800FCEB1F0026
267DA42C>97 D<133FEA1FFFA3C67E137EA313FE5BA312015BA312035BA31207EBE0FCEB
E3FF9038E707C0390FFE03E09038F801F001F013F8EBE000485A15FC5BA2123F90C7FCA2
14015A127EA2140312FE4814F8A2140715F05AEC0FE0A215C0EC1F80143F00781400007C
137E5C383C01F86C485A380F07C06CB4C7FCEA01FC1E3B7CB924>I<EC3FC0903801FFF0
903807E03C90380F800E90383F0007017E131F49137F484813FF485A485A120F4913FE00
1F143848481300A2127F90C8FCA35A5AA45AA315031507007E1406150E003E143C003F14
706C14E0390F8007C03907C03F003801FFF838003FC020267DA424>I<163FED1FFFA3ED
007F167EA216FEA216FCA21501A216F8A21503A216F0A21507A2027E13E0903803FF8790
380FC1CF90381F00EF017EEB7FC049133F485A4848131F000715805B000F143F485A1600
485A5D127F90C7127EA215FE5A485CA21401A248ECF80CA21403161CEDF0181407007C15
38007E010F1330003E131F027B13706C01E113E03A0F83C0F9C03A03FF007F80D800FCEB
1F00283B7DB92B>I<EC3FC0903801FFF0903807E07890381F801C90387E001E49130E48
5A485A1207485A49131E001F141C153C484813F8EC03E0007FEB3FC09038FFFE0014E090
C8FC5A5AA7007E140315071506003E140E153C6C14706C6C13E0EC07C03903E03F003801
FFF838003FC020267DA427>I<16F8ED03FEED0F8792381F0F80ED3E3F167F157CA215FC
1700161C4A48C7FCA414035DA414075DA20107B512F0A39026000FE0C7FC5DA4141F5DA4
143F92C8FCA45C147EA514FE5CA413015CA4495AA45C1307A25C121E123F387F8F80A200
FF90C9FC131E12FEEA7C3CEA7878EA1FF0EA07C0294C7CBA29>I<EC07E0EC1FF891387C
1C38903901F80EFC903803F007903807E003EB0FC090381F8001D93F0013F85B017E1303
13FE16F0485A150712034914E0A2150F12074914C0A2151FA2491480A2153FA216000003
5C6D5B00015B4A5A3900F8077E90387C1EFEEB1FF8903807E0FC90C7FC1401A25DA21403
001E5C123F387F80075D00FF495A49485A4849C7FC007C137E383C01F8381FFFE0000390
C8FC26367FA428>I<EB03F0EA01FFA3EA00075CA3130F5CA3131F5CA3133F91C9FCA35B
90387E03F8EC0FFF91383C0F809039FEF007C0D9FDC07FEBFF80EC0003485A5BA2491307
12035BA2150F00075D5BA2151F000F5D5B153F93C7FC121F4990387F0180157EEDFE0300
3F02FC130090C7FC5EEDF80648150E007E150C161C5E00FEEC787048EC3FE00038EC0F80
293B7CB930>I<14E0EB03F8A21307A314F0EB01C090C7FCAB13F8EA03FEEA070F000E13
80121C121812381230EA701F1260133F00E0130012C05BEA007EA213FE5B1201A25B1203
5BA20007131813E01438000F133013C01470EB806014E014C01381EB838038078700EA03
FEEA00F815397EB71D>I<150FED3F80A2157FA31600151C92C7FCABEC0F80EC3FE0ECF0
F0903801C0F849487E14005B130E130C131CEB1801133801305BA2EB0003A25DA21407A2
5DA2140FA25DA2141FA25DA2143FA292C7FCA25CA2147EA214FEA25CA21301001E5B123F
387F83F0A238FF87E0495A00FE5BD87C1FC8FCEA707EEA3FF8EA0FC0214981B722>I<EB
0FC0EA03FF5AA2EA001F1480A2133FA21400A25BA2137EA213FEA25BA21201A25BA21203
A25BA21207A25BA2120FA25BA2121FA25BA2123FA290C7FCA25AA2EA7E03A2EAFE071306
12FCA2130E130C131C1318EA7C38EA3C70EA1FE0EA0780123B7DB919>108
D<D803E0137F3A07F801FFE03A0E3C0781F03A1C3E1E00F826383F387F00305B4A137C00
705B00605BA200E090C712FC485A137EA20000140101FE5C5BA2150300015D5B15075E12
0349010F133016C0031F13700007ED80605B17E0EE00C0000F15014915801603EE070000
1FEC0F0E49EB07FC0007C7EA01F02C267EA432>110 D<EC1FC0ECFFF8903807E07E9038
0F801F90393F000F80017E14C0491307484814E0485A4848EB03F0120F5B121F48481307
A2127F90C7FCA2150F5A4815E0A2151F16C0A248EC3F8016005D157E007E5C4A5A003E49
5A003F495A6C495A6C6C48C7FC3807E07E3801FFF038003F8024267DA428>I<90390F80
03F090391FE00FFC903939F03C1F903A70F8700F80903AE0FDE007C09038C0FF80030013
E00001491303018015F05CEA038113015CA2D800031407A25CA20107140FA24A14E0A201
0F141F17C05CEE3F80131FEE7F004A137E16FE013F5C6E485A4B5A6E485A90397F700F80
DA383FC7FC90387E1FFCEC07E001FEC9FCA25BA21201A25BA21203A25B1207B512C0A32C
3583A42A>I<3903E001F83907F807FE390E3C1E07391C3E381F3A183F703F800038EBE0
7F0030EBC0FF00705B00601500EC007E153CD8E07F90C7FCEAC07EA2120013FE5BA31201
5BA312035BA312075BA3120F5BA3121F5B0007C9FC21267EA425>114
D<14FF010313C090380F80F090383E00380178131C153C4913FC0001130113E0A33903F0
00F06D13007F3801FFE014FC14FF6C14806D13C0011F13E013039038003FF01407140300
1E1301127FA24814E0A348EB03C012F800E0EB07800070EB0F006C133E001E13F83807FF
E0000190C7FC1E267CA427>I<EB01C0497E1307A4130F5CA3131F5CA3133F91C7FC007F
B51280A2B6FCD8007EC7FCA313FE5BA312015BA312035BA312075BA3120FEBC006A2140E
001F130CEB801C141814385C146014E0380F81C038078780D803FEC7FCEA00F819357EB3
1E>I<13F8D803FE1470D8070F14F8000EEB8001121C121800381403003015F0EA701F12
60013F130700E0010013E012C05BD8007E130F16C013FE5B151F000115805BA2153F0003
15005BA25D157EA315FE5D1401000113033800F80790387C1FF8EB3FF9EB0FE1EB00035D
A2000E1307D83F805B007F495AA24A5A92C7FCEB003E007C5B00705B6C485A381E07C06C
B4C8FCEA01FC25367EA429>121 D<D901E01360D90FF813E0496C13C090383FFE019039
7FFF038090B5EA07009038F81FFF3901E003FE9038C0001C495B5DC85A4A5A4A5A4AC7FC
140E5C5C14F0495AEB038049C8FC130E5B4913035B495B484813064848130E48C75AD80F
FC137C391FFF81F8381E0FFFD838075B486C5B00605CD8E00190C7FC38C0007C23267DA4
27>I E
%EndDVIPSBitmapFont
/Ff 133[37 42 42 1[42 42 23 32 28 1[42 42 42 65 23 42
1[23 1[42 28 37 42 37 42 37 13[46 2[46 3[51 2[28 3[51
60 1[55 66[{.167 SlantFont TeXBase1Encoding ReEncodeFont}29
83.022 /Times-Roman rf /Fg 107[29 29 24[29 33 33 48 33
33 18 26 22 33 33 33 33 52 18 33 18 18 33 33 22 29 33
29 33 29 3[22 1[22 2[48 2[48 41 37 44 1[37 48 48 59 41
2[22 2[37 41 1[44 44 48 6[18 33 4[33 33 33 33 33 18 17
22 17 2[22 22 37[37 2[{TeXBase1Encoding ReEncodeFont}60
66.4176 /Times-Roman rf /Fh 199[25 25 25 25 25 25 25
50[{TeXBase1Encoding ReEncodeFont}7 49.8132 /Times-Roman
rf /Fi 133[37 42 42 60 42 46 28 32 37 1[46 42 46 69 23
46 28 23 46 42 28 37 46 37 46 42 11[60 1[46 2[51 65 60
78 55 2[32 3[55 60 60 1[60 1[42 7[42 42 42 1[42 5[28
21 41[46 2[{TeXBase1Encoding ReEncodeFont}45 83.022 /Times-Bold
rf /Fj 136[86 60 66 40 47 53 1[66 60 66 1[33 66 1[33
66 60 40 53 66 53 1[60 9[120 2[80 66 86 1[73 93 1[113
3[47 93 2[80 86 86 80 86 7[60 60 60 60 60 60 60 60 60
60 48[{TeXBase1Encoding ReEncodeFont}43 119.552 /Times-Bold
rf /Fk 137[33 1[21 29 29 1[37 37 37 54 21 2[21 1[37 21
33 1[33 1[37 97[{TeXBase1Encoding ReEncodeFont}15 74.7198
/Times-Italic rf /Fl 134[37 37 54 37 37 21 29 25 37 37
37 37 58 21 37 1[21 37 37 25 33 37 33 37 33 12[46 42
50 2[54 5[25 3[46 1[50 50 54 7[37 37 1[37 4[37 2[19 25
19 2[25 25 37[42 2[{TeXBase1Encoding ReEncodeFont}43
74.7198 /Times-Roman rf /Fm 139[25 29 33 14[33 42 37
31[54 65[{TeXBase1Encoding ReEncodeFont}7 74.7198 /Times-Bold
rf /Fn 103[50 32[50 1[50 50 50 50 1[50 50 50 50 50 1[50
50 50 50 50 50 50 50 50 50 6[50 25[50 5[50 10[50 50 50
50 44[{TeXBase1Encoding ReEncodeFont}28 83.022 /Courier
rf
%DVIPSBitmapFont: Fo cmsy10 10 6
/Fo 6 104 df<007FB81280B912C0A26C17803204799641>0 D<0060150600F0150F6C15
1F007C153E6C157C6C15F86C6CEB01F06C6CEB03E06C6CEB07C06C6CEB0F806C6CEB1F00
017C133E6D5B6D5B90380F81F0903807C3E0903803E7C06DB45A6D90C7FC147EA214FF49
7F903803E7C0903807C3E090380F81F049C67E013E137C497F497F4848EB0F804848EB07
C04848EB03E04848EB01F048C812F8003E157C48153E48151F48150F00601506282874A8
41>2 D<EB1FF0EB7FFC48B5FC4814804814C04814E04814F04814F8A24814FCA2B612FE
A96C14FCA26C14F8A26C14F06C14E06C14C06C14806C140038007FFCEB1FF01F1F7BA42A
>15 D<007FB812F8B912FCA26C17F8CCFCAE007FB812F8B912FCA26C17F8CCFCAE007FB8
12F8B912FCA26C17F836287BA841>17 D<EC01F8140FEC3F80ECFC00495A495A495AA213
0F5CB3A7131F5C133F49C7FC13FEEA03F8EA7FE048C8FCEA7FE0EA03F8EA00FE137F6D7E
131F80130FB3A7801307A26D7E6D7E6D7EEC3F80EC0FF814011D537ABD2A>102
D<12FCEAFFC0EA07F0EA01FCEA007E7F80131F80130FB3A7801307806D7E6D7EEB007EEC
1FF0EC07F8EC1FF0EC7E00495A495A495A5C130F5CB3A7131F5C133F91C7FC137E485AEA
07F0EAFFC000FCC8FC1D537ABD2A>I E
%EndDVIPSBitmapFont
/Fp 134[37 37 55 37 42 23 32 32 42 42 42 42 60 23 37
23 23 42 42 23 37 42 37 42 42 7[46 51 69 51 60 46 42
51 1[51 60 55 69 46 55 37 28 60 2[51 60 55 51 51 6[28
42 42 42 42 42 42 42 1[42 42 23 21 28 21 4[28 36[42 2[{
TeXBase1Encoding ReEncodeFont}63 83.022 /Times-Italic
rf /Fq 199[29 29 29 29 29 29 29 29 49[{TeXBase1Encoding ReEncodeFont}8
58.1154 /Times-Roman rf /Fr 105[42 1[37 37 24[37 42 42
60 42 42 23 32 28 42 42 42 42 65 23 42 23 23 42 42 28
37 42 37 42 37 3[28 1[28 1[60 60 78 60 60 51 46 55 60
46 60 60 74 51 60 32 28 60 60 46 51 60 55 55 60 1[37
3[23 23 42 42 42 42 42 42 42 42 42 42 23 21 28 21 47
1[28 28 28 1[69 33[46 46 2[{TeXBase1Encoding ReEncodeFont}80
83.022 /Times-Roman rf /Fs 134[72 4[48 56 2[80 2[120
40 2[40 3[64 2[80 72 13[80 104 2[112 9[96 1[104 1[104
6[48 58[{TeXBase1Encoding ReEncodeFont}17 143.462 /Times-Bold
rf end
%%EndProlog
%%BeginSetup
%%Feature: *Resolution 600dpi
TeXDict begin

%%EndSetup
%%Page: 1 1
1 0 bop 1085 190 a Fs(ER)l(OS:)34 b(A)i(Capability)d(System)795
315 y Fr(Computer)19 b(and)h(Information)d(Sciences)j(T)-6
b(echnical)20 b(Report)f(MS-CIS-97-03)1233 464 y(J.)i(S.)f(Shapiro,)f
(J.)i(M.)f(Smith)h(and)e(D.)i(J.)f(F)o(arber)2635 434
y Fq(1)1421 589 y Fp(Distrib)n(uted)g(Systems)h(Labor)o(atory)990
688 y(Univer)o(sity)g(of)f(P)-7 b(ennsylvania,)18 b(Philadelphia,)g(P)
-7 b(A)20 b(19104-6389)1087 788 y Fo(f)p Fn(shap,jms,farber)p
Fo(g)p Fn(@dsl.cis.upen)o(n.edu)1718 912 y Fr(June)g(23,)g(1997)1811
1211 y Fm(Abstract)450 1303 y Fl(Capabilities)e(de\002ne)h(a)g(uniform)
g(semantics)g(for)g(system)g(service)g(in)m(v)o(ocation,)g(enforce)g
(separation)h(of)e(concerns)i(and)300 1394 y(encapsulation,)h(and)g
(allo)n(w)f(each)g(program)h(to)f(be)g(restricted)f(to)h(e)o(xactly)g
(that)g(set)g(of)g(authority)g(it)f(requires)h(\(the)g
Fk(principle)300 1485 y(of)i(least)g(privile)m(g)o(e)p
Fl(\).)34 b(Capability)22 b(systems)h(therefore)g(readily)f(contain)h
(and)g(reduce)g(errors)f(at)g(the)h(application)g(le)n(v)o(el)f(and)300
1577 y(impro)o(v)o(e)g(component)h(testability)-5 b(.)31
b(If)21 b(carefully)h(architected,)g(a)g(capability)g(system)g(should)g
(be)g(both)g Fk(faster)i Fl(and)e Fk(simpler)300 1668
y Fl(than)f(a)g(comparable)h(access-control-based)i(system.)29
b(In)21 b(practice,)g(implementations)h(ha)o(v)o(e)f(f)o(ailed)g(to)g
(demonstrate)h(such)300 1759 y(performance.)450 1851
y(This)17 b(paper)i(pro)o(vides)f(an)g(architectural)g(o)o(v)o(ervie)n
(w)g(of)g(ER)m(OS,)e(the)h(Extremely)h(Reliable)f(Operating)i(System.)j
(ER)m(OS)300 1942 y(is)g(a)h(persistent)g(capability)g(system)g(which)h
(pro)o(vides)f(complete)h(accountability)g(for)e(persistent,)i
(consumable)g(and)g(mul-)300 2033 y(tiple)o(x)o(ed)k(resources.)52
b(By)28 b(choosing)h(abstractions)g(to)f(le)n(v)o(erage)h(con)m(v)o
(entional)h(hardw)o(are)f(protecgion,)i(and)e(e)o(xploiting)300
2125 y(hardw)o(are)c(support)g(in)e(the)h(implementation,)i(a)e(f)o
(ast)g(pure)g(capability)g(architecture)h(can)f(be)g(demonstrated.)40
b(This)23 b(paper)300 2216 y(describes)g(the)g(system)f(design)h(and)g
(the)g(proposed)h(e)n(v)n(aluation)g(method)f(for)f(ER)m(OS.)f(An)h
(implementation)h(of)g(ER)m(OS)e(for)300 2307 y(the)e(x86)h(platform)f
(is)f(currently)i(underw)o(ay)-5 b(,)20 b(and)g(we)e(e)o(xpect)i(to)f
(report)g(benchmark)i(results)d(by)i(mid)f(1998.)0 2681
y Fj(1)119 b(Intr)n(oduction)0 2951 y Fr(Control)22 b(of)g(protected)e
(resources)i(may)g(use)g(\()p Fp(object)p Fr(,)g Fp(user)p
Fr(,)h Fp(au-)0 3050 y(thority)p Fr(\))40 b(triples,)45
b(which)40 b(aggre)o(gate)e(as)j(an)f Fi(access)g(contr)o(ol)0
3150 y(list)p Fr([Sal75)o(])35 b(\(A)m(CL\).)f(A)m(CLs)h(ha)n(v)o(e)f
(tw)o(o)h(disadv)n(antages;)40 b(the)o(y)0 3250 y(are)23
b(a)g(static)g(lattice)g(of)f(authorities)g(rather)g(than)g(dynamic,)g
(and)0 3349 y(the)j(notion)f(of)h Fp(user)j Fr(introduces)23
b(man)o(y)h(opportunities)f(for)i(un-)0 3449 y(intended)19
b(sharing)g(of)h(authority)-5 b(.)0 3582 y(A)32 b Fi(capability)e
Fr(is)i(an)f(unfor)o(geable)c(\()p Fp(object)p Fr(,)33
b Fp(type)p Fr(,)g Fp(authority)p Fr(\))0 3681 y(triple)20
b([Den66)n(].)26 b(A)21 b(capability)f(system)h(is)g(one)f(in)h(which)f
(capa-)0 3781 y(bilities)26 b(pro)o(vide)e(the)i(system')-5
b(s)27 b(mechanism)d(for)h(security)h(and)0 3881 y(access)g(control.)40
b(T)-7 b(o)26 b(access)g(an)o(y)f(object)g(in)h(such)g(a)g(system,)h(a)
0 3980 y(program)18 b(must)i(hold)f(and)g(in)m(v)n(ok)o(e)g(a)i
(capability)e(for)g(that)h(objec-)0 4080 y(t.)36 b(Possession)24
b(of)f(a)h(capability)f(is)i(a)f(necessary)e(and)i(suf)n(\002cient)0
4180 y(proof)16 b(of)i(authority)e(to)i(perform)e(the)h(operations)g
(authorized)e(by)0 4279 y(the)20 b(capability)f(on)h(the)g(object)g
(that)g(it)h(names.)0 4412 y(The)27 b(capability)f(model)g(is)i
(attracti)n(v)o(e)e(for)g(se)n(v)o(eral)g(reasons:)39
b(It)0 4512 y(is)21 b(possible)f(to)g(construct)f(a)i(formal)e
(semantics)h(for)f(such)h(a)h(sys-)0 4611 y(tem,)29 b(and)d(to)i(pro)o
(v)o(e)d(useful)h(properties)g(from)g(that)h(semantics.)0
4711 y(Simultaneously)-5 b(,)21 b(capabilities)h(pro)o(vide)f(a)i
(natural)f(frame)n(w)o(ork)0 4811 y(in)e(which)e(to)i
Fp(e)n(xpose)f Fr(the)g(underlying)e(machine)h(representation)0
4910 y(in)j(a)g(secure)f(and)g(consistent)g(f)o(ashion,)f(allo)n(wing)h
(programmers)0 5010 y(to)j(better)f(understand)e(application)i
(performance)d(and)j(pro)o(vid-)0 5109 y(ing)g(\002ne-grain)e
(accountability)g(for)h(resources)g(with)h(lo)n(w)g(o)o(v)o(er)n(-)0
5209 y(head.)32 b(Finally)-5 b(,)23 b(programs)e(in)i(a)h
(capability-based)c(system)j(can)0 5309 y(be)18 b Fp(con\002ned)g
Fr([Lam73)n(].)25 b(A)18 b(con\002ned)f(program)f(cannot)h(leak)h(in-)0
5408 y(formation)29 b(to)j(an)f(unauthorized)e(party;)36
b(it)c(li)n(v)o(es)f(in)h(a)g(\223black)1992 2681 y(box.)-6
b(\224)70 b(Such)35 b(an)g(en)m(vironment)e(is)j(a)g(safe)g(container)e
(within)1992 2780 y(which)19 b(to)i(run)e(an)h(untrusted)f(program.)
1992 2913 y(Architecturally)-5 b(,)16 b(since)i(the)o(y)g(eliminate)g
(consideration)f(of)h(user)1992 3013 y(identity)-5 b(,)31
b(capabilities)f(reduce)f(the)i(number)d(of)j(name)e(spaces)1992
3113 y(that)37 b(must)h(implemented)e(by)h(the)g(supervisor)-5
b(.)76 b(Capability-)1992 3212 y(based)35 b(systems)i(are)f(readily)f
(secured.)71 b(The)36 b(set)h(of)e(object-)1992 3312
y(s)i(reachable)f(by)g(a)i(program)c(is)k(readily)e(computable:)57
b(it)38 b(is)1992 3411 y(a)25 b(transiti)n(v)o(e,)h(re\003e)o(xi)n(v)o
(e,)g(semi-symmetric)e(closure)h(of)g(objects)1992 3511
y(reachable)c(from)h(the)h(program')-5 b(s)22 b(initial)h(capability)f
(set.)35 b(If)23 b(the)1992 3611 y(primiti)n(v)o(e)30
b(capabilities)h(are)g(properly)e(designed)i(this)h(set)g(can)1992
3710 y(be)24 b(sho)n(wn)g(to)h(be)f(closed.)2762 3680
y Fq(2)2833 3710 y Fr(The)g(capability)g(model)g Fp(should)i
Fr(be)1992 3810 y(f)o(aster:)41 b(all)29 b(other)e(things)h(being)f
(equal)g(there)h(is)h(one)f(less)h(cri-)1992 3910 y(terion)21
b(to)i(e)o(xamine)e(\(user)h(identity\))f(and)h(no)g(list)h(to)g(tra)n
(v)o(erse)e(to)1992 4009 y(determine)d(access)j(rights.)1992
4142 y(ER)m(OS)35 b(\(the)g(Extremely)f(Reliable)i(Operating)e
(System\))h(is)h(a)1992 4242 y(ne)n(w)30 b(capability)g(system)h(which)
g(pro)o(vides)e(these)i(adv)n(antages)1992 4341 y(while)15
b(deli)n(v)o(ering)e(unusually)h(high)h(performance.)20
b(Preliminary)1992 4441 y(measurements)32 b(suggest)h(that)h(ER)m(OS)h
(deli)n(v)o(ers)d(performance)1992 4541 y(on)26 b(most)g(critical)h(k)o
(ernel)f(paths)g(that)h(closely)f(approaches)f(the)1992
4640 y(maximum)18 b(deri)n(v)n(able)h(from)g(the)h(underlying)d(hardw)o
(are.)p 1992 5172 764 4 v 2082 5227 a Fh(2)2111 5251
y Fg(The)22 b(presence)j(of)d(a)h(shared)g(mutable)i(name)e(space)g
(\(the)h(\002le)f(system\))f(in)1992 5329 y(most)h(A)m(CL)g(systems)h
(violates)i(this)e(closure.)42 b(This)24 b(defeats)h(the)f
(reachability)1992 5408 y(computation,)19 b(rendering)g(security)g(dif)
n(\002cult)g(to)e(impossible)i(in)e(practice.)1929 5657
y Fr(1)p eop
%%Page: 2 2
2 1 bop 0 91 a Fj(2)119 b(Backgr)n(ound)0 316 y Fr(Capabilities)37
b(were)g(the)g(\002rst)g(protection)e(mechanism)h(to)h(be)0
416 y(gi)n(v)o(en)j(a)i(semantically)f(rigorous)f(de\002nition)h
([Den66)n(],)47 b(and)0 515 y(were)d(used)h(by)f(se)n(v)o(eral)g
(multiprocessing)f(systems)i(of)f(the)0 615 y(1970')-5
b(s)54 b(\(e.g.,)63 b(C.mmp[W)l(ul81)m(],)h(CAL[Lam76)n(],)g(Plesse)o
(y)0 715 y(2000[Le)n(v84)l(],)58 b(Sigma-7,)f(Burroughs)48
b(B5700[Or)o(g73)l(]\))i(as)0 814 y(their)21 b(underlying)e(protection)
h(model.)28 b(Operating)20 b(systems)i(for)0 914 y(these)e(machines)g
(focused)f(on)g(tw)o(o)i(issues:)62 1127 y(1.)41 b(bridging)14
b(the)j(semantic)f(gap)g(between)g(the)g(operating)f(sys-)166
1226 y(tem)20 b(and)g(the)g(application,)f(and)62 1419
y(2.)41 b(e)o(xtending)20 b(the)j(protection)e(semantics)h(of)h
(capabilities)f(to)166 1519 y(the)39 b(abstractions)g(de\002ned)f(by)h
(the)g(system)h(supervisor)166 1618 y([W)l(ul81)o(,)20
b(Lam76)n(,)h(F)o(or94)n(].)0 1831 y(The)g(\002rst)h(of)f(these)g
(issues)h(moti)n(v)n(ated)e(the)h(CISC)h(architectures)0
1930 y(of)e(the)g(late)h(70')-5 b(s)20 b(and)g(early)f(80')-5
b(s.)0 2063 y(A)34 b(v)n(ariety)f(of)g(architectural)f(shortcomings)f
(resulted)i(in)h(lo)n(w)0 2163 y(performance)20 b(for)j(these)h
(systems,)g(ef)n(fecti)n(v)o(ely)e(causing)h(the)g(a-)0
2263 y(bandonment)414 2232 y Fq(3)464 2263 y Fr(of)d(\002ne-grain)f
(capability)g(architectures:)83 2498 y Fo(\017)41 b Ff(Excessi)n(v)o(e)
21 b(abstraction)28 b Fr(and)21 b(the)h(resulting)f(comple)o(x)g(ob-)
166 2598 y(jects)f(\(e.g.,)f(\002les\))h(preclude)e(enforcing)g
(authorities)h(using)166 2698 y(the)h(underlying)e(hardw)o(are[Col88)l
(,)j(W)l(ul81)o(,)f(Lam76)n(].)83 2891 y Fo(\017)41 b
Ff(Buf)n(fered)51 b(messages)58 b Fr(are)52 b(comple)o(x,)58
b(slo)n(w)-5 b(,)60 b(and)51 b(the)166 2990 y(message)e(b)n(uf)n(fer)f
(is)j(an)e(unaccountably)d(multiple)o(x)o(ed)166 3090
y(resource[W)l(ul81)m(,)20 b(Lam76)n(,)h(F)o(or94)n(].)83
3283 y Fo(\017)41 b Ff(Small)30 b(granularity)k Fr(protection)28
b(domains)h(are)g(not)h(well-)166 3382 y(supported)64
b(by)h(hardw)o(are,)76 b(and)66 b(the)f(dif)n(\002culty)g(of)166
3482 y(implementation[W)l(ul81)l(,)22 b(Lam76)n(].)29
b(leads)22 b(to)g(comple)o(xi-)166 3582 y(ty)e(and)g(its)h(associated)f
(performance)d(cost.)83 3774 y Fo(\017)41 b Ff(Encryption)p
Fr(,)14 b(if)i(used)g(to)g(support)e(unfor)o(geability)-5
b(,)13 b(has)j(sig-)166 3874 y(ni\002cant)g(time)h(\(decryption\))d
(and)i(space)g(\(e)o(xtra)g(bits\))g(o)o(v)o(er)n(-)166
3974 y(head.)83 4166 y Fo(\017)41 b Ff(Indirection)31
b Fr(through)24 b(\223object)h(tables\224)i(is)g(costly)f(b)n(ut)h(of-)
166 4266 y(ten)20 b(used)g(to)h(allo)n(w)f(object)g(deletion)f(without)
h(locating)f(all)166 4366 y(outstanding)f(capabilities[W)l(ul81)n(,)i
(Lam76)o(].)83 4558 y Fo(\017)41 b Ff(Dynamic)14 b(allocation)21
b Fr(in)15 b(the)g(supervisor)f(is)i(comple)o(x,)f(and)166
4658 y(usually)23 b(improperly)e(accounted)h(for)m(,)i(e.g.,)g(in)g
(the)f(use)h(of)166 4758 y(v)n(ariable-length)17 b(capability)j(lists)
83 4951 y Fo(\017)41 b Ff(P)o(assi)n(v)o(e)33 b(stores)40
b Fr(require)32 b(reconstruction)e(of)j(authorities)166
5050 y(on)19 b(restart,)g(which)g(requires)f(persistence,)h(b)n(ut)g(a)
h(common)166 5150 y(\002le)h(system)g(name)f(space)h(sub)o(v)o(erts)e
(man)o(y)g(adv)n(antages)g(of)166 5249 y(capabilities[W)l(ul81)n(,)h
(Lam76)n(].)p 0 5329 764 4 v 90 5385 a Fh(3)120 5408
y Fg(with)d(the)h(notable)h(e)o(xception)h(of)d(the)h(IBM)f(AS/400)2075
91 y Fo(\017)41 b Ff(Localized)28 b(persistence)p Fr(,)k(where)d
(modules)f(decide)h(inde-)2158 191 y(pendently)37 b(when)i(to)g(store,)
44 b(requires)38 b(communicating)2158 291 y(programs)26
b(to)j(implement)e(their)h(o)n(wn,)i(often)e(e)o(xpensi)n(v)o(e,)2158
390 y(consistenc)o(y)18 b(mechanism)h(\(e.g.,)g(transactions\).)1992
617 y(Collecti)n(v)o(ely)-5 b(,)48 b(these)d(f)o(ailings)f(ha)n(v)o(e)g
(deprecated)f(capability)1992 717 y(systems)32 b(among)f(both)g
(researchers)g(and)g(commercial)g(users.)1992 816 y(Ho)n(we)n(v)o(er)m
(,)24 b(the)h(security)g(and)f(reliability)h(guarantees)e(of)i(capa-)
1992 916 y(bility)20 b Fp(model)f Fr(are)h(compelling.)1992
1049 y(The)f(ER)m(OS)i(design)f(process)f(had)h(four)f(phases:)2054
1275 y(1.)41 b(Identify)25 b(the)i(principles)f(that)h(should)f
(constrain)g(the)h(de-)2158 1375 y(sign.)2054 1555 y(2.)41
b(Examine)55 b(the)i(v)n(arious)f(possibilities)i(for)e(primiti)n(v)o
(e,)2158 1655 y(supervisor)n(-implemented)32 b(abstractions)k(suitable)
g(for)g(a)2158 1755 y(capability)19 b(architecture.)2054
1935 y(3.)41 b(Reduce)16 b(these)g(to)h(a)g(minimum)e(basis)i(set)g
(that)f(can)h(be)f(real-)2158 2035 y(ized)j(ef)n(fecti)n(v)o(ely)f
(using)g(the)i(hardw)o(are)e(support)g(a)n(v)n(ailable)2158
2134 y(on)h(modern)g(architectures.)2054 2315 y(4.)41
b(Implement)18 b(this)j(set)g(ef)n(\002ciently)-5 b(.)1992
2541 y(Thus)29 b(our)f(focus)h(w)o(as)h(on)f(performance,)g(and)g(the)g
(result)h(is)g(a)1992 2641 y(pure)h(capability)h(system)h(pro)o(viding)
d(performance)g(competi-)1992 2741 y(ti)n(v)o(e)j(with)g(monolithic)f
(systems.)65 b(The)33 b(rest)h(of)f(the)g(paper)g(is)1992
2840 y(about)19 b(ho)n(w)g(we)i(achie)n(v)o(ed)d(it.)1992
3170 y Fj(3)119 b(Design)30 b(Principles)1992 3392 y
Fr(The)25 b(architecture)e(of)i(the)h(ER)m(OS)f(k)o(ernel)g(be)o(gan)e
(with)j(a)g(set)g(of)1992 3492 y(design)d(principles,)h(some)h(of)f
(which)g(are)g(tak)o(en)g(directly)g(from)1992 3591 y(CAL[Lam76)m(].)
1992 3753 y Fi(Pr)o(otection)33 b(Domains)96 b Fr(All)36
b(code)f(outside)g(the)h(supervisor)1992 3852 y(runs)29
b(within)g(some)g(protection)f(domain)g(.)54 b(A)30 b(protection)d(do-)
1992 3952 y(main)e(pro)o(vides)g(a)h(conte)o(xt)f(that)i(holds)e(the)h
(authorities)g(acces-)1992 4051 y(sible)34 b(to)g(a)g(process.)65
b(In)34 b(ER)m(OS,)g(each)f(process)h(is)h(an)e(inde-)1992
4151 y(pendent)f(protection)h(domain.)66 b(A)35 b(related)f(principle)f
(is)i Fp(iso-)1992 4251 y(lation)p Fr(:)47 b(the)32 b(supervisor)f
(should)f(not)i(be)g(compromisable)d(by)1992 4350 y(an)o(y)j(action)h
(performed)e(by)i(non-supervisor)d(code.)63 b(Re)o(gret-)1992
4450 y(tably)-5 b(,)36 b(this)f(has)f(led)h(us)f(to)h(admit)f(de)n
(vice)f(mini-dri)n(v)o(ers)f(into)1992 4550 y(the)37
b(k)o(ernel.)76 b(Protection)37 b(domains)f(aid)i(with)g(the)f
Fp(principle)1992 4649 y(of)29 b(least)h(privile)m(g)o(e)p
Fr(,)h(which)e(means)h(that)f(applications)g(should)1992
4749 y(ha)n(v)o(e)j(access)h(to)g(only)e(and)h(e)o(xactly)g(those)h
(services)f(and)g(ob-)1992 4848 y(jects)21 b(that)g(are)g(necessary)f
(to)h(their)g(operation,)e(minimizing)h(the)1992 4948
y(f)o(ailure)28 b(scope)g(of)g(the)h(application,)g(simplifying)e
(security)i(ar)n(-)1992 5048 y(guments)d([Bom92)n(],)i(enforcing)d
(encapsulation[W)l(ul81)l(],)k(and)1992 5147 y(easing)19
b(softw)o(are)h(maintainance[L)-5 b(yc78)l(].)1992 5309
y Fi(Objects)80 b Fr(The)20 b(system)h(pro)o(vides)e(a)i(virtual)f(w)o
(orld)g(composed)1992 5408 y(of)27 b(objects)i([Lam76)m(].)50
b(These)28 b(objects)g(come)f(in)i(a)g(v)n(ariety)e(of)1929
5657 y(2)p eop
%%Page: 3 3
3 2 bop 0 91 a Fr(types,)27 b(which)e(are)g(described)g(in)g(Section)h
(4.)41 b(Objects)26 b(are)f(en-)0 191 y(capsulated:)d(each)17
b(object)f(de\002nes)g(a)h(set)g(of)g(operations)e(that)h(can)0
291 y(be)29 b(performed)d(on)i(that)h(object)g(by)f(means)h(of)f(an)h
(in)m(v)n(ocation.)0 390 y(Objects)c(are)g(named)f(e)o(xclusi)n(v)o
(ely)f(by)h(k)o(ernel-protected)e(capa-)0 490 y(bilities.)j(An)17
b(object)f(can)h(only)g(be)g(manipulated)e(by)i(performing)0
589 y(an)j Fp(in)m(vocation)e Fr(on)i(a)g(capability)g(naming)e(the)j
(object.)0 751 y Fi(Acti)o(v)o(e,)26 b(Single)g(Le)o(v)o(el)f(Stor)o(e)
85 b Fr(The)24 b(capability)h(model)f(must)0 851 y(e)o(xtend)g
(uniformly)e(to)j(the)g(disk;)i(there)d(should)g(be)h(no)g(transla-)0
950 y(tion)18 b(required)f(at)i(this)g(layer)e(in)i(the)f(memory)f
(hierarchy)-5 b(.)22 b(ER)m(OS)0 1050 y(therefore)d(implements)g(a)i
(single)f(le)n(v)o(el)g(store.)26 b(The)20 b(state)h(of)f(the)0
1149 y(machine)k(is)h(periodically)e(snapshotted)g(and)h(written)h(to)g
(the)g(s-)0 1249 y(tore)30 b(using)g(an)g(ef)n(\002cient)g
(asynchronous)e(checkpoint)g(mecha-)0 1349 y(nism)e([Lan92)n(].)41
b(The)26 b(store)f(is)i Fp(active)p Fr(:)36 b(processes)26
b(are)f(includ-)0 1448 y(ed)32 b(in)f(the)h(checkpoint)e(and)h(are)g
(restarted)g(automatically)f(on)0 1548 y(reco)o(v)o(ery)-5
b(.)65 b(This)35 b(eliminates)f(the)g(need)g(for)g(the)h(startup)f(and)
0 1648 y(shutdo)n(wn)21 b(phases)h(of)g(man)o(y)g(programs,)f(and)h
(reduces)f(the)i(fre-)0 1747 y(quenc)o(y)f(of)j(program)d(f)o
(abrication.)36 b(Perhaps)23 b(more)h(important,)0 1847
y(transparent)i(persistence)h(eliminates)h(the)g(need)f(to)h
(re-acquire)0 1946 y(authorities)e(on)g(system)h(restart.)45
b(An)27 b(implication)e(for)h(the)h(su-)0 2046 y(pervisor)c(is)j(that)f
(it)g(should)f(be)h Fp(r)m(eco)o(ver)o(able)p Fr(;)h(there)e(should)g
(be)0 2146 y(no)29 b(state)g(visibly)g(held)f(by)h(the)g(k)o(ernel)f
(between)g(units)h(of)g(op-)0 2245 y(eration;)37 b(all)c(persistent)f
(state)h(should)e(be)h(in)g(checkpointable)0 2345 y(objects.)257
2315 y Fq(4)0 2506 y Fi(Atomic)23 b(Units)h(of)e(Operation)82
b Fr(All)24 b(services)f(performed)d(by)0 2606 y(the)29
b(supervisor)f(consist)h(of)g(a)g(single,)i(atomic)e(unit)g(of)f
(opera-)0 2706 y(tion)i(with)h(a)g(clearly)f(de\002ned)f(commit)h
(point.)55 b(A)31 b(supervisor)0 2805 y(operation)g(either)i(e)o(x)o
(ecutes)f(to)h(completion)e(or)i(does)g(not)g(al-)0 2905
y(ter)25 b(the)g(state)h(of)f(the)g(system.)40 b(This)25
b(simpli\002es)h(the)f(semantics)0 3005 y(of)d(each)g(operation,)f(f)o
(acilitates)i(our)f(approach)e(to)j(persistence,)0 3104
y(reduces)h(the)h(number)e(of)i(boundary)d(conditions)i(that)h
(applica-)0 3204 y(tions)g(need)g(to)h(check,)f(and)g(lays)h(the)f
(groundw)o(ork)d(for)j(a)h(fully)0 3303 y(multithreadable)16
b(supervisor)-5 b(.)24 b(The)18 b(alternati)n(v)o(e)f(is)j
(transaction-)0 3403 y(s,)h(which)e(ha)n(v)o(e)h(prohibiti)n(v)o(e)e(o)
o(v)o(erhead)f([Sel95)o(].)0 3564 y Fi(Expose)33 b(Multiplexing)92
b Fr(ER)m(OS)33 b(is)g(a)g(real-time)e(k)o(ernel.)61
b(It)0 3664 y(is)22 b(therefore)d(essential)i(to)g(e)o(xpose)f
(resource)f(multiple)o(xing)g(and)0 3764 y(virtualization)24
b(to)i(user)g(control.)41 b(This)26 b(requires)e(both)h(that)h(re-)0
3863 y(source)35 b(granularity)e(be)j(suf)n(\002ciently)e(\002ne-grain)
g(\(pages,)39 b(for)0 3963 y(e)o(xample,)27 b(must)g(be)f(named\))g
(and)g(that)h(suitable)f(multiple)o(xing)0 4063 y(controls)d(be)i
(accessible)f(to)h(applications)e(in)i(an)f(appropriately)0
4162 y(secure)c(f)o(asion.)0 4324 y Fi(Account)25 b(f)n(or)g(Ev)o
(erything)85 b Fr(No)25 b(resource)g(should)f(go)h(unac-)0
4423 y(counted)h(for)-5 b(.)47 b(Comple)o(x)27 b(accounting)e(should)i
(be)h(minimized,)0 4523 y(and)20 b(if)h(possible)f(eliminated.)26
b(A)21 b(corollary)e(to)i(this)g(is)h(the)e(elim-)0 4623
y(ination)27 b(of)g(metadata.)47 b(Metadata)28 b(is)g(implicitly)f
(allocated)g(by)0 4722 y(other)18 b(operations,)f(making)g(it)i(dif)n
(\002cult)f(to)h(account)e(for)h(proper)n(-)0 4822 y(ly)-5
b(.)0 4983 y Fi(Minimality)81 b Fr(The)21 b(supervisor)f(should)g(not)h
(perform)e(an)o(y)i(op-)0 5083 y(eration)j(that)g(is)i(not)e(required)e
(to)j(satisfy)g(these)f(design)g(princi-)0 5182 y(ples.)p
0 5250 764 4 v 90 5306 a Fh(4)120 5329 y Fg(ER)m(OS)c(does)h(not)g
(quite)h(meet)f(this)g(objecti)n(v)o(e:)33 b(the)21 b(list)g(of)g
(currently)i(run-)0 5408 y(ning)18 b(threads)g(and)g(the)f(list)h(of)f
(acti)n(v)o(e)j(reserv)o(es)e(is)f(k)o(ept)h(by)f(the)h(k)o(ernel.)1992
91 y Fj(4)119 b(The)30 b(ER)l(OS)h(Ar)n(chitectur)n(e)1992
317 y Fr(The)41 b(ER)m(OS)i(supervisor)d(implements)h(a)h(small)h
(number)d(of)1992 417 y(primiti)n(v)o(e)18 b(objects,)i(which)g(are)g
(sho)n(wn)f(in)i(T)-7 b(able)20 b(1)1992 550 y(All)j(objects,)g
(including)e(supervisor)h(services,)h(are)g(designated)1992
649 y(by)c(unfor)o(geable)e(capabilities,)j(which)f(are)i(de\002ned)e
(as)i(a)f(triple:)2463 847 y Fe(O)r(bj)5 b(ect)18 b Fo(\002)g
Fe(T)12 b(y)s(pe)17 b Fo(\002)h Fe(C)6 b(apI)h(nf)i(o)1992
1045 y Fr(The)37 b Fe(T)12 b(y)s(pe)37 b Fr(and)g Fe(C)6
b(apI)h(nf)i(o)38 b Fr(\002elds)g(combine)e(to)i(de\002ne)g(the)1992
1145 y Fe(R)q(ig)s(hts)25 b Fr(con)m(v)o(e)o(yed)e(by)j(the)g
(capability)-5 b(.)42 b(The)26 b(meaning)f(of)h(the)1992
1245 y Fe(C)6 b(apI)h(nf)i(o)18 b Fr(\002eld)h(is)g(speci\002c)g(to)g
(the)f(capability)g(type.)24 b(Dif)n(ferent)1992 1344
y(capabilities)e(may)g(name)g(the)h(same)g(object)f(b)n(ut)h(con)m(v)o
(e)o(y)d(dif)n(fer)n(-)1992 1444 y(ent)g(authorities)f(o)o(v)o(er)g
(that)h(object.)1992 1750 y Fd(4.1)99 b(In)l(v)o(ocation)1992
1945 y Fr(T)-7 b(o)16 b(e)o(x)o(ercise)g(the)g(object)g(designated)g
(by)g(a)h(capability)-5 b(,)15 b(the)i(hold-)1992 2045
y(ing)i(process)h Fp(in)m(vok)o(es)g Fr(that)g(capability)-5
b(.)24 b(The)c(object)f(is)j(in)m(v)n(ok)o(ed,)1992 2145
y(performs)17 b(the)j(requested)f(service,)g(and)g(replies)g(to)h(the)g
(in)m(v)n(ok)o(er)-5 b(.)1992 2244 y(The)26 b(in)m(v)n(ocation)e(trap)i
(is)i(the)e(only)g(system)h(call)f(implemented)1992 2344
y(by)19 b(the)h(ER)m(OS)h(supervisor)-5 b(.)1992 2477
y(Ev)o(ery)17 b(in)m(v)n(ocation)h(\(including)f(interprocess)h
(communication\))1992 2576 y(sends)i(up)f(to)h(64)g(kilobytes)f(of)h
(data,)f(four)g(data)h(re)o(gister)f(v)n(alues,)1992
2676 y(and)e(four)g(capabilities.)23 b(The)18 b(CALL)g(in)m(v)n
(ocation)e(transmits)i(this)1992 2776 y(information)j(and)j(lea)n(v)o
(es)h(the)f(process)g Fp(waiting)g Fr(for)f(a)i(reply)e(in)1992
2875 y(the)30 b(same)h(format.)54 b(The)31 b(RETURN)g(in)m(v)n(ocation)
d(sends)j(a)g(re-)1992 2975 y(sponse)15 b(and)g(renders)f(the)i
(process)f Fp(available)g Fr(for)g(further)f(calls.)3867
2945 y Fq(5)1992 3075 y Fr(The)20 b(SEND)i(operation)d(implements)i(a)g
(send-only)f(in)m(v)n(ocation.)1992 3174 y(The)j(sender)f(remains)h
(running)e(after)i(the)h(send)f(completes;)h(no)1992
3274 y(response)k(is)j(e)o(xpected.)52 b(SEND)30 b(can)f(be)h(used)f
(to)h(implement)1992 3373 y(non-blocking)16 b(return,)j(or)h(to)g
(initiate)g(parallel)g(e)o(x)o(ecution.)1992 3679 y Fd(4.2)99
b(Numbers)1992 3875 y Fr(A)30 b Fi(number)g(capability)f
Fr(is)h(a)g(capability)f(holding)f(96)h(bits)h(of)1992
3975 y(data.)24 b(Number)19 b(capabilities)h(serv)o(e)g(se)n(v)o(eral)f
(roles:)2075 4214 y Fo(\017)41 b Fr(The)f(zero)f(number)g(capability)g
(is)i(used)f(in)h(all)g(places)2158 4313 y(where)19 b(a)i(\223v)n(oid)e
(capability\224)g(might)h(be)g(e)o(xpected.)2075 4510
y Fo(\017)41 b Fr(The)18 b(zero)g(number)f(capability)h(serv)o(es)g(to)
h(identify)f(in)m(v)n(alid)2158 4610 y(address)h(ranges.)2075
4807 y Fo(\017)41 b Fr(Number)16 b(capabilities)i(are)g(used)f(to)i
(hold)e(process)g(re)o(gister)2158 4907 y(v)n(alues)i(when)h(a)h
(process)e(is)i(not)f(e)o(x)o(ecuting.)1992 5146 y(The)28
b(only)g(operation)f(supported)f(by)j(a)g(number)e(capability)h(is)1992
5245 y(the)20 b(operation)e(that)i(obtains)g(it')-5 b(s)21
b(v)n(alue.)p 1992 5329 V 2082 5385 a Fh(5)2111 5408
y Fg(The)15 b(RETURN)g(operation)i(implements)g(\223return)g(and)f(w)o
(ait)g(for)f(ne)o(xt)i(call.)-5 b(\224)1929 5657 y Fr(3)p
eop
%%Page: 4 4
4 3 bop 448 78 a Fr(number)348 b(a)21 b(self-describing)d(96)i(bit)g
(quantity)-5 b(.)448 178 y(page)446 b(the)20 b(basic)h(unit)f(of)g
(storage)f(for)h(user)g(data.)448 277 y(capability)f(page)98
b(a)21 b(unit)f(of)g(storage)f(for)h(capabilities.)448
377 y(node)441 b(an)20 b(alternati)n(v)o(e)f(unit)h(of)g(storage)g(for)
f(capabilities.)448 477 y(address)g(space)150 b(a)21
b(mapping)d(from)h(of)n(fsets)h(to)h(pages)448 576 y(process)354
b(the)20 b(container)f(for)h(a)g(computation,)e(and)i(also)g(the)g
(unit)g(of)g(protection)f(domain.)1469 754 y(T)-7 b(able)20
b(1:)26 b(ER)m(OS)20 b(Object)g(T)-7 b(ypes)0 1104 y
Fd(4.3)99 b(Basic)25 b(Units)g(of)g(Storage)0 1294 y
Fr(The)k(basic)h(units)f(of)g(storage)g(in)h(the)f(ER)m(OS)h
(architecture)e(are)0 1394 y(the)g(data)g(page)f(\()p
Fi(page)p Fr(\))g(and)h(the)g(capability)f(page)g(\()p
Fi(node)p Fr(\).)49 b(A)0 1494 y(node)18 b(contains)g(32)h
(capabilities,)g(in)g(the)g(same)g(w)o(ay)g(that)g(a)h(page)0
1593 y(holds)d(4096)f(bytes)h(\(your)f(architecture)g(may)h(v)n(ary\).)
23 b(Capability)0 1693 y(pages)j(cannot)f(be)h(mapped)e(into)i(a)g
(process)g(address)f(space)h(or)0 1792 y(otherwise)i(manipulated)f
(directly)i(by)f(the)h(application.)50 b(This)0 1892
y(partitioning)18 b(ensures)i(that)g(the)o(y)g(are)g(unfor)o(geable.)0
2025 y(P)o(ages)26 b(and)f(nodes)g(are)g(named)g(by)g
Fi(page)g(capabilities)h Fr(and)f Fi(n-)0 2125 y(ode)g(capabilities)p
Fr(,)h(which)f(may)g(carry)f(a)i(\223read-only\224)c(restric-)0
2224 y(tion.)57 b(Node)30 b(capabilities)g(may)h(in)g(addition)e(carry)
h(\223no-call\224)0 2324 y(and)j(\223weak\224)g(restrictions.)65
b(The)33 b(\223no-call\224)g(restriction)g(sup-)0 2423
y(press)22 b(the)g(in)m(v)n(ocation)e(of)i(untrusted)e(address)i(space)
g(e)o(xception)0 2523 y(handlers)32 b(\(See)g(Section)h(4.7\).)62
b(An)o(y)32 b(capability)f(fetched)h(via)0 2623 y(a)g(\223weak\224)e
(capability)g(is)j(weak)o(ened)c(according)h(to)h(the)g(rules)0
2722 y(sho)n(wn)f(in)g(T)-7 b(able)31 b(2.)56 b(The)30
b(combination)e(of)j(weak)f(and)g(read-)301 2896 y Fi(Input)307
b(output)p 251 2929 1407 4 v 301 2999 a Fr(NumberCap)97
b(NumberCap)301 3099 y(P)o(ageCap)210 b(R)m(O)21 b(P)o(ageCap)301
3198 y(NodeCap)190 b(R)m(O,)21 b(NC,)g(WK)g(NodeCap)301
3298 y(SpaceCap)172 b(R)m(O,)21 b(NC,)g(WK)g(SpaceCap)301
3397 y Fp(all)f(other)o(s)190 b Fr(NumberCap\(0\))439
3575 y(T)-7 b(able)20 b(2:)26 b(The)19 b(weak)o(en)h(operation)0
3877 y(only)g(restrictions)g(therefore)f(guarantees)h
Fp(tr)o(ansitive)g Fr(read-only)0 3977 y(access.)0 4110
y(Using)29 b(pages)g(and)f(nodes)h(as)h(the)f(tw)o(o)g(fundamental)e
(units)i(of)0 4210 y(storage,)h(we)f(construct)e(the)i(remaining)e
(abstractions)g(needed)0 4309 y(for)20 b(a)g(general)f(purpose,)g(e)o
(xtensible)g(operating)f(system.)0 4587 y Fd(4.4)99 b(Addr)n(ess)26
b(Spaces)0 4777 y Fr(An)34 b Fi(addr)o(ess)g(space)g
Fr(is)h(a)g(tree)f(of)f(nodes)g(whose)h(lea)n(v)o(es)g(are)0
4877 y(pages)f(\(Figure)g(1\).)65 b(Unmapped)32 b(pages)h(are)h
(indicated)e(by)i(a)0 4977 y Fi(Number)d(Capability)e
Fr(holding)g(the)h(v)n(alue)f(zero.)55 b(If)30 b(set,)j(the)0
5076 y(read-only)23 b(bit)j(in)f(each)g(capability)f(indicates)h(that)h
(the)f(associ-)0 5176 y(ated)19 b(subtree)f(cannot)f(be)i(written)g(in)
g(this)g(address)f(space;)i(sense)0 5275 y(capabilities)g(are)g
(considered)e(read-only)-5 b(.)0 5408 y(Address)24 b(spaces)g(are)g
(recursi)n(v)o(ely)e(de\002ned.)36 b(One)24 b(process)f(can)2025
1021 y
 14537768 10788208 0 0 14537768 10788208 startTexFig
 2025 1021 a
%%BeginDocument: seg19pg.eps
%!PS-Adobe-2.0 EPSF-2.0
%%Title: seg19pg.fig
%%Creator: fig2dev Version 3.2 Patchlevel 1
%%CreationDate: Wed Oct 13 21:24:04 1999
%%For: shapj@bonzo.watson.ibm.com (Jonathan Shapiro)
%%Orientation: Portrait
%%BoundingBox: 0 0 221 164
%%Pages: 0
%%BeginSetup
%%EndSetup
%%Magnification: 1.0000
%%EndComments
/$F2psDict 200 dict def
$F2psDict begin
$F2psDict /mtrx matrix put
/col-1 {0 setgray} bind def
/col0 {0.000 0.000 0.000 srgb} bind def
/col1 {0.000 0.000 1.000 srgb} bind def
/col2 {0.000 1.000 0.000 srgb} bind def
/col3 {0.000 1.000 1.000 srgb} bind def
/col4 {1.000 0.000 0.000 srgb} bind def
/col5 {1.000 0.000 1.000 srgb} bind def
/col6 {1.000 1.000 0.000 srgb} bind def
/col7 {1.000 1.000 1.000 srgb} bind def
/col8 {0.000 0.000 0.560 srgb} bind def
/col9 {0.000 0.000 0.690 srgb} bind def
/col10 {0.000 0.000 0.820 srgb} bind def
/col11 {0.530 0.810 1.000 srgb} bind def
/col12 {0.000 0.560 0.000 srgb} bind def
/col13 {0.000 0.690 0.000 srgb} bind def
/col14 {0.000 0.820 0.000 srgb} bind def
/col15 {0.000 0.560 0.560 srgb} bind def
/col16 {0.000 0.690 0.690 srgb} bind def
/col17 {0.000 0.820 0.820 srgb} bind def
/col18 {0.560 0.000 0.000 srgb} bind def
/col19 {0.690 0.000 0.000 srgb} bind def
/col20 {0.820 0.000 0.000 srgb} bind def
/col21 {0.560 0.000 0.560 srgb} bind def
/col22 {0.690 0.000 0.690 srgb} bind def
/col23 {0.820 0.000 0.820 srgb} bind def
/col24 {0.500 0.190 0.000 srgb} bind def
/col25 {0.630 0.250 0.000 srgb} bind def
/col26 {0.750 0.380 0.000 srgb} bind def
/col27 {1.000 0.500 0.500 srgb} bind def
/col28 {1.000 0.630 0.630 srgb} bind def
/col29 {1.000 0.750 0.750 srgb} bind def
/col30 {1.000 0.880 0.880 srgb} bind def
/col31 {1.000 0.840 0.000 srgb} bind def
/col32 {0.894 0.635 0.000 srgb} bind def

end
save
-6.0 166.0 translate
1 -1 scale

/cp {closepath} bind def
/ef {eofill} bind def
/gr {grestore} bind def
/gs {gsave} bind def
/sa {save} bind def
/rs {restore} bind def
/l {lineto} bind def
/m {moveto} bind def
/rm {rmoveto} bind def
/n {newpath} bind def
/s {stroke} bind def
/sh {show} bind def
/slc {setlinecap} bind def
/slj {setlinejoin} bind def
/slw {setlinewidth} bind def
/srgb {setrgbcolor} bind def
/rot {rotate} bind def
/sc {scale} bind def
/sd {setdash} bind def
/ff {findfont} bind def
/sf {setfont} bind def
/scf {scalefont} bind def
/sw {stringwidth} bind def
/tr {translate} bind def
/tnt {dup dup currentrgbcolor
  4 -2 roll dup 1 exch sub 3 -1 roll mul add
  4 -2 roll dup 1 exch sub 3 -1 roll mul add
  4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb}
  bind def
/shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul
  4 -2 roll mul srgb} bind def
/$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def
/$F2psEnd {$F2psEnteredState restore end} def
%%EndProlog

$F2psBegin
10 setmiterlimit
n -1000 3757 m -1000 -1000 l 4783 -1000 l 4783 3757 l cp clip
 0.06000 0.06000 sc
% Polyline
7.500 slw
n 752 453 m 827 453 l 827 853 l 752 853 l cp gs col-1 s gr
% Polyline
n 827 453 m 902 453 l 902 853 l 827 853 l cp gs col-1 s gr
% Polyline
n 902 453 m 977 453 l 977 853 l 902 853 l cp gs col-1 s gr
% Polyline
n 977 453 m 1053 453 l 1053 853 l 977 853 l cp gs col-1 s gr
% Polyline
n 1053 453 m 1128 453 l 1128 853 l 1053 853 l cp gs col-1 s gr
% Polyline
n 1128 453 m 1203 453 l 1203 853 l 1128 853 l cp gs col-1 s gr
% Polyline
n 1203 453 m 1277 453 l 1277 853 l 1203 853 l cp gs col-1 s gr
% Polyline
n 1277 453 m 1352 453 l 1352 853 l 1277 853 l cp gs col-1 s gr
% Polyline
n 1352 453 m 1428 453 l 1428 853 l 1352 853 l cp gs col-1 s gr
% Polyline
n 1428 453 m 1502 453 l 1502 853 l 1428 853 l cp gs col-1 s gr
% Polyline
n 1502 453 m 1577 453 l 1577 853 l 1502 853 l cp gs col-1 s gr
% Polyline
n 1577 453 m 1652 453 l 1652 853 l 1577 853 l cp gs col-1 s gr
% Polyline
n 1728 453 m 1803 453 l 1803 853 l 1728 853 l cp gs col-1 s gr
% Polyline
n 1652 453 m 1728 453 l 1728 853 l 1652 853 l cp gs col-1 s gr
% Polyline
n 1952 1278 m 2027 1278 l 2027 1679 l 1952 1679 l cp gs col-1 s gr
% Polyline
n 2027 1278 m 2102 1278 l 2102 1679 l 2027 1679 l cp gs col-1 s gr
% Polyline
n 2102 1278 m 2177 1278 l 2177 1679 l 2102 1679 l cp gs col-1 s gr
% Polyline
n 2177 1278 m 2252 1278 l 2252 1679 l 2177 1679 l cp gs col-1 s gr
% Polyline
n 2252 1278 m 2327 1278 l 2327 1679 l 2252 1679 l cp gs col-1 s gr
% Polyline
n 2327 1278 m 2403 1278 l 2403 1679 l 2327 1679 l cp gs col-1 s gr
% Polyline
n 2403 1278 m 2478 1278 l 2478 1679 l 2403 1679 l cp gs col-1 s gr
% Polyline
n 2478 1278 m 2553 1278 l 2553 1679 l 2478 1679 l cp gs col-1 s gr
% Polyline
n 2553 1278 m 2628 1278 l 2628 1679 l 2553 1679 l cp gs col-1 s gr
% Polyline
n 2628 1278 m 2702 1278 l 2702 1679 l 2628 1679 l cp gs col-1 s gr
% Polyline
n 2702 1278 m 2777 1278 l 2777 1679 l 2702 1679 l cp gs col-1 s gr
% Polyline
n 2777 1278 m 2852 1278 l 2852 1679 l 2777 1679 l cp gs col-1 s gr
% Polyline
n 2852 1278 m 2928 1278 l 2928 1679 l 2852 1679 l cp gs col-1 s gr
% Polyline
n 1877 1278 m 1952 1278 l 1952 1679 l 1877 1679 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 2928 1278 m 3003 1278 l 3003 1679 l 2928 1679 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 3003 1278 m 3078 1278 l 3078 1679 l 3003 1679 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 228 1279 m 303 1279 l 303 1679 l 228 1679 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 303 1279 m 378 1279 l 378 1679 l 303 1679 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 378 1279 m 453 1279 l 453 1679 l 378 1679 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 453 1279 m 528 1279 l 528 1679 l 453 1679 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 528 1279 m 603 1279 l 603 1679 l 528 1679 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 603 1279 m 678 1279 l 678 1679 l 603 1679 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 678 1279 m 753 1279 l 753 1679 l 678 1679 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 753 1279 m 828 1279 l 828 1679 l 753 1679 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 828 1279 m 903 1279 l 903 1679 l 828 1679 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 903 1279 m 978 1279 l 978 1679 l 903 1679 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 978 1279 m 1053 1279 l 1053 1679 l 978 1679 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 1053 1279 m 1128 1279 l 1128 1679 l 1053 1679 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 1128 1279 m 1203 1279 l 1203 1679 l 1128 1679 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 1203 1279 m 1278 1279 l 1278 1679 l 1203 1679 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 1278 1279 m 1353 1279 l 1353 1679 l 1278 1679 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 1353 1279 m 1428 1279 l 1428 1679 l 1353 1679 l cp gs col7 0.75 shd ef gr gs col-1 s gr
/Times-Roman ff 90.00 scf sf
153 1380 m
gs 1 -1 sc (0) col-1 sh gr
/Times-Roman ff 90.00 scf sf
1466 1380 m
gs 1 -1 sc (15) col-1 sh gr
% Polyline
n 2055 704 m 2055 594 l 2535 594 l 2535 704 l cp gs col-1 s gr
% Polyline
n 603 453 m 677 453 l 677 853 l 603 853 l cp gs col7 0.95 shd ef gr gs col-1 s gr
% Polyline
n 677 453 m 752 453 l 752 853 l 677 853 l cp gs col7 0.95 shd ef gr gs col-1 s gr
/Times-Roman ff 90.00 scf sf
528 554 m
gs 1 -1 sc (0) col-1 sh gr
/Times-Roman ff 90.00 scf sf
1840 554 m
gs 1 -1 sc (15) col-1 sh gr
/Times-Roman ff 90.00 scf sf
1802 1378 m
gs 1 -1 sc (0) col-1 sh gr
/Times-Roman ff 90.00 scf sf
3115 1378 m
gs 1 -1 sc (15) col-1 sh gr
% Polyline
gs  clippath
255 1155 m 225 1275 l 195 1155 l 195 1290 l 255 1290 l cp
clip
n 630 600 m 630 975 l 225 975 l 225 1275 l gs col-1 s gr gr

% arrowhead
n 255 1155 m 225 1275 l 195 1155 l 225 1155 l 255 1155 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
gs  clippath
1920 1140 m 1890 1260 l 1860 1140 l 1860 1275 l 1920 1275 l cp
clip
n 720 615 m 720 975 l 1890 975 l 1890 1260 l gs col-1 s gr gr

% arrowhead
n 1920 1140 m 1890 1260 l 1860 1140 l 1890 1140 l 1920 1140 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
gs  clippath
246 1906 m 180 2010 l 189 1887 l 147 2015 l 204 2034 l cp
clip
n 255 1440 m 255 1785 l 180 2010 l gs col-1 s gr gr

% arrowhead
n 246 1906 m 180 2010 l 189 1887 l 218 1896 l 246 1906 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
n 390 1995 m 525 1995 l 525 2145 l 390 2145 l cp gs col-1 s gr
% Polyline
n 645 1995 m 780 1995 l 780 2145 l 645 2145 l cp gs col-1 s gr
% Polyline
n 885 1995 m 1020 1995 l 1020 2145 l 885 2145 l cp gs col-1 s gr
% Polyline
n 1110 1995 m 1245 1995 l 1245 2145 l 1110 2145 l cp gs col-1 s gr
% Polyline
n 1335 1995 m 1470 1995 l 1470 2145 l 1335 2145 l cp gs col-1 s gr
% Polyline
n 1560 1995 m 1695 1995 l 1695 2145 l 1560 2145 l cp gs col-1 s gr
% Polyline
n 1785 1995 m 1920 1995 l 1920 2145 l 1785 2145 l cp gs col-1 s gr
% Polyline
n 120 1995 m 255 1995 l 255 2145 l 120 2145 l cp gs col-1 s gr
% Polyline
n 240 2235 m 375 2235 l 375 2385 l 240 2385 l cp gs col-1 s gr
% Polyline
n 510 2250 m 645 2250 l 645 2400 l 510 2400 l cp gs col-1 s gr
% Polyline
n 750 2250 m 885 2250 l 885 2400 l 750 2400 l cp gs col-1 s gr
% Polyline
n 975 2250 m 1110 2250 l 1110 2400 l 975 2400 l cp gs col-1 s gr
% Polyline
n 1230 2250 m 1365 2250 l 1365 2400 l 1230 2400 l cp gs col-1 s gr
% Polyline
n 1455 2250 m 1590 2250 l 1590 2400 l 1455 2400 l cp gs col-1 s gr
% Polyline
n 1680 2250 m 1815 2250 l 1815 2400 l 1680 2400 l cp gs col-1 s gr
% Polyline
n 1950 2250 m 2085 2250 l 2085 2400 l 1950 2400 l cp gs col-1 s gr
% Polyline
gs  clippath
1746 1906 m 1845 1980 l 1723 1962 l 1847 2013 l 1870 1958 l cp
clip
n 1305 1440 m 1305 1755 l 1845 1980 l gs col-1 s gr gr

% arrowhead
n 1746 1906 m 1845 1980 l 1723 1962 l 1734 1934 l 1746 1906 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
gs  clippath
1525 1901 m 1620 1980 l 1499 1955 l 1620 2014 l 1647 1960 l cp
clip
n 1155 1455 m 1155 1755 l 1620 1980 l gs col-1 s gr gr

% arrowhead
n 1525 1901 m 1620 1980 l 1499 1955 l 1512 1928 l 1525 1901 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
gs  clippath
1305 1895 m 1395 1980 l 1276 1948 l 1393 2014 l 1423 1961 l cp
clip
n 1020 1470 m 1020 1770 l 1395 1980 l gs col-1 s gr gr

% arrowhead
n 1305 1895 m 1395 1980 l 1276 1948 l 1290 1921 l 1305 1895 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
gs  clippath
1096 1881 m 1170 1980 l 1058 1928 l 1163 2013 l 1201 1966 l cp
clip
n 855 1455 m 855 1725 l 1170 1980 l gs col-1 s gr gr

% arrowhead
n 1096 1881 m 1170 1980 l 1058 1928 l 1077 1904 l 1096 1881 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
gs  clippath
890 1893 m 960 1995 l 850 1938 l 951 2027 l 991 1982 l cp
clip
n 705 1455 m 705 1770 l 960 1995 l gs col-1 s gr gr

% arrowhead
n 890 1893 m 960 1995 l 850 1938 l 870 1916 l 890 1893 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
gs  clippath
660 1865 m 705 1980 l 611 1900 l 689 2010 l 738 1975 l cp
clip
n 555 1455 m 555 1770 l 705 1980 l gs col-1 s gr gr

% arrowhead
n 660 1865 m 705 1980 l 611 1900 l 635 1882 l 660 1865 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
gs  clippath
349 2101 m 315 2220 l 289 2099 l 285 2234 l 344 2236 l cp
clip
n 330 1440 m 330 1770 l 315 2220 l gs col-1 s gr gr

% arrowhead
n 349 2101 m 315 2220 l 289 2099 l 319 2100 l 349 2101 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
gs  clippath
600 2115 m 570 2235 l 540 2115 l 540 2250 l 600 2250 l cp
clip
n 480 1455 m 480 1755 l 570 1995 l 570 2235 l gs col-1 s gr gr

% arrowhead
n 600 2115 m 570 2235 l 540 2115 l 570 2115 l 600 2115 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
gs  clippath
855 2130 m 825 2250 l 795 2130 l 795 2265 l 855 2265 l cp
clip
n 630 1440 m 630 1755 l 825 1965 l 825 2250 l gs col-1 s gr gr

% arrowhead
n 855 2130 m 825 2250 l 795 2130 l 825 2130 l 855 2130 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
gs  clippath
1095 2115 m 1065 2235 l 1035 2115 l 1035 2250 l 1095 2250 l cp
clip
n 780 1455 m 780 1755 l 1065 1965 l 1065 2235 l gs col-1 s gr gr

% arrowhead
n 1095 2115 m 1065 2235 l 1035 2115 l 1065 2115 l 1095 2115 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
gs  clippath
469 1856 m 465 1980 l 411 1869 l 439 2001 l 497 1988 l cp
clip
n 420 1440 m 420 1770 l 465 1980 l gs col-1 s gr gr

% arrowhead
n 469 1856 m 465 1980 l 411 1869 l 440 1863 l 469 1856 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
gs  clippath
1312 2117 m 1275 2235 l 1252 2113 l 1244 2248 l 1304 2252 l cp
clip
n 945 1449 m 945 1755 l 1290 1980 l 1275 2235 l gs col-1 s gr gr

% arrowhead
n 1312 2117 m 1275 2235 l 1252 2113 l 1282 2115 l 1312 2117 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
gs  clippath
1537 2117 m 1500 2235 l 1477 2113 l 1469 2248 l 1529 2252 l cp
clip
n 1080 1440 m 1080 1740 l 1515 1980 l 1500 2235 l gs col-1 s gr gr

% arrowhead
n 1537 2117 m 1500 2235 l 1477 2113 l 1507 2115 l 1537 2117 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
gs  clippath
1770 2130 m 1740 2250 l 1710 2130 l 1710 2265 l 1770 2265 l cp
clip
n 1230 1455 m 1230 1740 l 1740 1995 l 1740 2250 l gs col-1 s gr gr

% arrowhead
n 1770 2130 m 1740 2250 l 1710 2130 l 1740 2130 l 1770 2130 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
gs  clippath
2048 2129 m 2025 2250 l 1988 2132 l 1996 2267 l 2056 2263 l cp
clip
n 1395 1443 m 1395 1725 l 2010 1980 l 2025 2250 l gs col-1 s gr gr

% arrowhead
n 2048 2129 m 2025 2250 l 1988 2132 l 2018 2130 l 2048 2129 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
n 2355 1935 m 2490 1935 l 2490 2085 l 2355 2085 l cp gs col-1 s gr
% Polyline
n 2820 1935 m 2955 1935 l 2955 2085 l 2820 2085 l cp gs col-1 s gr
% Polyline
n 3045 1935 m 3180 1935 l 3180 2085 l 3045 2085 l cp gs col-1 s gr
% Polyline
gs  clippath
2265 1870 m 2370 1935 l 2247 1927 l 2375 1968 l 2393 1911 l cp
clip
n 1905 1425 m 1905 1785 l 2370 1935 l gs col-1 s gr gr

% arrowhead
n 2265 1870 m 2370 1935 l 2247 1927 l 2256 1898 l 2265 1870 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
gs  clippath
2972 1823 m 2895 1920 l 2917 1798 l 2861 1921 l 2916 1946 l cp
clip
n 2970 1410 m 2970 1755 l 2895 1920 l gs col-1 s gr gr

% arrowhead
n 2972 1823 m 2895 1920 l 2917 1798 l 2945 1811 l 2972 1823 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
gs  clippath
3073 1801 m 3105 1920 l 3020 1830 l 3086 1948 l 3139 1919 l cp
clip
n 3030 1410 m 3030 1785 l 3105 1920 l gs col-1 s gr gr

% arrowhead
n 3073 1801 m 3105 1920 l 3020 1830 l 3047 1815 l 3073 1801 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
gs  clippath
330 420 m 450 450 l 330 480 l 465 480 l 465 420 l cp
clip
n 825 150 m 150 150 l 150 450 l 450 450 l gs col-1 s gr gr

% arrowhead
n 330 420 m 450 450 l 330 480 l 330 450 l 330 420 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
n 2056 474 m 2056 360 l 2559 360 l 2559 474 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 465 225 m 974 225 l 974 105 l 465 105 l cp gs col7 0.95 shd ef gr gs col-1 s gr
% Polyline
n 2040 929 m 2040 809 l 2549 809 l 2549 929 l cp gs col7 0.95 shd ef gr gs col-1 s gr
/Times-Bold ff 150.00 scf sf
2282 1212 m
gs 1 -1 sc (node) col-1 sh gr
/Times-Bold ff 150.00 scf sf
677 1227 m
gs 1 -1 sc (node) col-1 sh gr
/Times-Bold ff 150.00 scf sf
782 2712 m
gs 1 -1 sc (Pages) col-1 sh gr
/Times-Bold ff 150.00 scf sf
2676 930 m
gs 1 -1 sc (Node Capability) col-1 sh gr
/Times-Bold ff 150.00 scf sf
2670 725 m
gs 1 -1 sc (Null Capability) col-1 sh gr
/Times-Bold ff 150.00 scf sf
2683 474 m
gs 1 -1 sc (Page Capability) col-1 sh gr
/Times-Bold ff 150.00 scf sf
1026 180 m
gs 1 -1 sc (Node Capablity \(Root\)) col-1 sh gr
/Times-Bold ff 150.00 scf sf
1007 417 m
gs 1 -1 sc (node) col-1 sh gr
$F2psEnd
rs

%%EndDocument

 endTexFig
 2374 2570 a Fr(Figure)c(1:)26 b(A)20 b(19)g(page)g(address)f(space)
1992 2910 y(construct)28 b(a)j(ne)n(w)f(address)f(space)h(that)g(maps)g
(a)h(subset)f(of)g(its)1992 3010 y(current)22 b(address)i(space)g(and)g
(pass)h(this)f(ne)n(w)g(address)g(space)g(to)1992 3109
y(another)16 b(party)-5 b(.)23 b(The)18 b(recipient)f(can)h(then)g(mer)
o(ge)f(the)h(transfered)1992 3209 y(address)25 b(space)h(into)g(its)h
(main)e(address)h(space,)h(establishing)e(a)1992 3309
y(shared)19 b(mapping.)1992 3441 y(It)24 b(is)h(sometimes)f(useful)g
(for)g(the)g(internal)f(structure)h(of)g(an)g(ad-)1992
3541 y(dress)e(space)g(to)h(be)f(opaque)e(to)j(its)g(user)-5
b(.)31 b(T)-7 b(o)23 b(f)o(acilitate)f(this,)h(we)1992
3641 y(introduced)18 b(a)j(specialization)g(of)f(a)i(node)d(capability)
h(kno)n(wn)g(as)1992 3740 y(an)26 b Fi(addr)o(ess)h(space)h(capability)
p Fr(.)44 b(Node)26 b(capabilities)h(and)f(ad-)1992 3840
y(dress)33 b(space)g(capabilities)f(can)h(be)g(used)g(interchangeably)c
(in)1992 3940 y(de\002ning)d(the)h(address)g(space)h(tree.)47
b(The)27 b(dif)n(ference)e(between)1992 4039 y(an)h(address)g(space)h
(capability)e(and)h(a)h(node)e(capability)h(is)h(that)1992
4139 y(the)19 b(address)g(space)g(capability)f(is)i(opaque:)j(slots)d
(of)f(the)h(named)1992 4238 y(node)26 b(cannot)g(be)h(e)o(xamined)e(by)
i(means)g(of)g(an)g(address)g(space)1992 4338 y(capability)-5
b(.)22 b(Most)16 b(address)g(spaces)h(are)f(constructed)e(e)o(xclusi)n
(v)o(e-)1992 4438 y(ly)20 b(from)f(node,)g(page,)g(and)h(null)g
(capabilities.)1992 4571 y(F)o(or)50 b(page,)57 b(node,)g(and)50
b(address)g(space)h(capabilities,)58 b(the)1992 4670
y Fe(C)6 b(apI)h(nf)i(o)17 b Fr(\002eld)g(contains)g(the)g
Fi(r)o(ead-only)p Fr(,)f Fi(no-call)h Fr(\(suppress-)1992
4770 y(es)30 b(f)o(ault)g(handler)e(in)m(v)n(ocation\),)i(and)f
Fi(blss)i Fr(information)d(about)1992 4869 y(the)20 b(object.)k(BLSS)d
(\(biased)f(log)g(space)g(size\))g(is)h(de\002ned)f(as)2234
5039 y Fe(B)t(LS)5 b(S)27 b Fo(\021)22 b Fe(l)r(og)2686
5051 y Fc(2)2723 5039 y Fb(\()p Fe(Addr)r(ess)g(S)5 b(pace)19
b(S)5 b(iz)t(e)p Fb(\))17 b Fo(\000)h Fb(1)1992 5209
y Fr(and)29 b(de\002nes)h(the)g(size)h(of)f(the)g(subspace)f(de\002ned)
h(by)f(a)i(gi)n(v)o(en)1992 5309 y(page,)i(node,)g(or)e(address)f
(space)i(capability)-5 b(.)57 b(Recording)30 b(the)1992
5408 y(size)16 b(in)h(the)f(capability)f(allo)n(ws)h(the)g(address)g
(space)g(f)o(abricator)e(to)1929 5657 y(4)p eop
%%Page: 5 5
5 4 bop 0 91 a Fr(short-circuit)18 b(le)n(v)o(els)i(in)g(the)g(mapping)
e(tree.)25 b(One)19 b(consequence)0 191 y(is)26 b(that)f(most)h
(mapping)d(trees)i(for)g(nati)n(v)o(e)f(ER)m(OS)i(domains)e(are)0
291 y(only)15 b(tw)o(o)h(or)f(three)h(nodes)f(tall,)i(reducing)c(the)j
(number)e(of)i(object)0 390 y(f)o(aults)k(necessary)g(to)g(resolv)o(e)f
(an)i(address.)0 767 y Fd(4.5)99 b(Pr)n(ocesses)0 977
y Fr(A)27 b(process)f(is)i(constructed)c(as)k(a)f(suitable)f
(arrangement)e(of)i(n-)0 1076 y(odes)21 b(\(Figure)f(2\).)26
b(Ev)o(ery)20 b(process)g(has)i(a)f(node)f(that)h(acts)g(as)h(the)50
1241 y
 14274641 9406791 0 0 14274641 9406791 startTexFig
 50 1241 a
%%BeginDocument: ndomain.eps
%!PS-Adobe-2.0 EPSF-2.0
%%Title: ndomain.fig
%%Creator: fig2dev Version 3.2 Patchlevel 1
%%CreationDate: Wed Oct 13 21:24:04 1999
%%For: shapj@bonzo.watson.ibm.com (Jonathan Shapiro)
%%Orientation: Portrait
%%BoundingBox: 0 0 217 143
%%Pages: 0
%%BeginSetup
%%EndSetup
%%Magnification: 1.0000
%%EndComments
/MyAppDict 100 dict dup begin def
/$F2psDict 200 dict def
$F2psDict begin
$F2psDict /mtrx matrix put
/col-1 {0 setgray} bind def
/col0 {0.000 0.000 0.000 srgb} bind def
/col1 {0.000 0.000 1.000 srgb} bind def
/col2 {0.000 1.000 0.000 srgb} bind def
/col3 {0.000 1.000 1.000 srgb} bind def
/col4 {1.000 0.000 0.000 srgb} bind def
/col5 {1.000 0.000 1.000 srgb} bind def
/col6 {1.000 1.000 0.000 srgb} bind def
/col7 {1.000 1.000 1.000 srgb} bind def
/col8 {0.000 0.000 0.560 srgb} bind def
/col9 {0.000 0.000 0.690 srgb} bind def
/col10 {0.000 0.000 0.820 srgb} bind def
/col11 {0.530 0.810 1.000 srgb} bind def
/col12 {0.000 0.560 0.000 srgb} bind def
/col13 {0.000 0.690 0.000 srgb} bind def
/col14 {0.000 0.820 0.000 srgb} bind def
/col15 {0.000 0.560 0.560 srgb} bind def
/col16 {0.000 0.690 0.690 srgb} bind def
/col17 {0.000 0.820 0.820 srgb} bind def
/col18 {0.560 0.000 0.000 srgb} bind def
/col19 {0.690 0.000 0.000 srgb} bind def
/col20 {0.820 0.000 0.000 srgb} bind def
/col21 {0.560 0.000 0.560 srgb} bind def
/col22 {0.690 0.000 0.690 srgb} bind def
/col23 {0.820 0.000 0.820 srgb} bind def
/col24 {0.500 0.190 0.000 srgb} bind def
/col25 {0.630 0.250 0.000 srgb} bind def
/col26 {0.750 0.380 0.000 srgb} bind def
/col27 {1.000 0.500 0.500 srgb} bind def
/col28 {1.000 0.630 0.630 srgb} bind def
/col29 {1.000 0.750 0.750 srgb} bind def
/col30 {1.000 0.880 0.880 srgb} bind def
/col31 {1.000 0.840 0.000 srgb} bind def
/col32 {0.894 0.635 0.000 srgb} bind def

end
save
-19.0 161.0 translate
1 -1 scale
.9 .9 scale % to make patterns same scale as in xfig

% This junk string is used by the show operators
/PATsstr 1 string def
/PATawidthshow { 	% cx cy cchar rx ry string
  % Loop over each character in the string
  {  % cx cy cchar rx ry char
    % Show the character
    dup				% cx cy cchar rx ry char char
    PATsstr dup 0 4 -1 roll put	% cx cy cchar rx ry char (char)
    false charpath		% cx cy cchar rx ry char
    /clip load PATdraw
    % Move past the character (charpath modified the
    % current point)
    currentpoint			% cx cy cchar rx ry char x y
    newpath
    moveto			% cx cy cchar rx ry char
    % Reposition by cx,cy if the character in the string is cchar
    3 index eq {			% cx cy cchar rx ry
      4 index 4 index rmoveto
    } if
    % Reposition all characters by rx ry
    2 copy rmoveto		% cx cy cchar rx ry
  } forall
  pop pop pop pop pop		% -
  currentpoint
  newpath
  moveto
} bind def
/PATcg {
  7 dict dup begin
    /lw currentlinewidth def
    /lc currentlinecap def
    /lj currentlinejoin def
    /ml currentmiterlimit def
    /ds [ currentdash ] def
    /cc [ currentrgbcolor ] def
    /cm matrix currentmatrix def
  end
} bind def
% PATdraw - calculates the boundaries of the object and
% fills it with the current pattern
/PATdraw {			% proc
  save exch
    PATpcalc			% proc nw nh px py
    5 -1 roll exec		% nw nh px py
    newpath
    PATfill			% -
  restore
} bind def
% PATfill - performs the tiling for the shape
/PATfill { % nw nh px py PATfill -
  PATDict /CurrentPattern get dup begin
    setfont
    % Set the coordinate system to Pattern Space
    PatternGState PATsg
    % Set the color for uncolored pattezns
    PaintType 2 eq { PATDict /PColor get PATsc } if
    % Create the string for showing
    3 index string		% nw nh px py str
    % Loop for each of the pattern sources
    0 1 Multi 1 sub {		% nw nh px py str source
	% Move to the starting location
	3 index 3 index		% nw nh px py str source px py
	moveto			% nw nh px py str source
	% For multiple sources, set the appropriate color
	Multi 1 ne { dup PC exch get PATsc } if
	% Set the appropriate string for the source
	0 1 7 index 1 sub { 2 index exch 2 index put } for pop
	% Loop over the number of vertical cells
	3 index 		% nw nh px py str nh
	{			% nw nh px py str
	  currentpoint		% nw nh px py str cx cy
	  2 index show		% nw nh px py str cx cy
	  YStep add moveto	% nw nh px py str
	} repeat		% nw nh px py str
    } for
    5 { pop } repeat
  end
} bind def

% PATkshow - kshow with the current pattezn
/PATkshow {			% proc string
  exch bind			% string proc
  1 index 0 get			% string proc char
  % Loop over all but the last character in the string
  0 1 4 index length 2 sub {
				% string proc char idx
    % Find the n+1th character in the string
    3 index exch 1 add get	% string proe char char+1
    exch 2 copy			% strinq proc char+1 char char+1 char
    % Now show the nth character
    PATsstr dup 0 4 -1 roll put	% string proc chr+1 chr chr+1 (chr)
    false charpath		% string proc char+1 char char+1
    /clip load PATdraw
    % Move past the character (charpath modified the current point)
    currentpoint newpath moveto
    % Execute the user proc (should consume char and char+1)
    mark 3 1 roll		% string proc char+1 mark char char+1
    4 index exec		% string proc char+1 mark...
    cleartomark			% string proc char+1
  } for
  % Now display the last character
  PATsstr dup 0 4 -1 roll put	% string proc (char+1)
  false charpath		% string proc
  /clip load PATdraw
  neewath
  pop pop			% -
} bind def
% PATmp - the makepattern equivalent
/PATmp {			% patdict patmtx PATmp patinstance
  exch dup length 7 add		% We will add 6 new entries plus 1 FID
  dict copy			% Create a new dictionary
  begin
    % Matrix to install when painting the pattern
    TilingType PATtcalc
    /PatternGState PATcg def
    PatternGState /cm 3 -1 roll put
    % Check for multi pattern sources (Level 1 fast color patterns)
    currentdict /Multi known not { /Multi 1 def } if
    % Font dictionary definitions
    /FontType 3 def
    % Create a dummy encoding vector
    /Encoding 256 array def
    3 string 0 1 255 {
      Encoding exch dup 3 index cvs cvn put } for pop
    /FontMatrix matrix def
    /FontBBox BBox def
    /BuildChar {
	mark 3 1 roll		% mark dict char
	exch begin
	Multi 1 ne {PaintData exch get}{pop} ifelse  % mark [paintdata]
	  PaintType 2 eq Multi 1 ne or
	  { XStep 0 FontBBox aload pop setcachedevice }
	  { XStep 0 setcharwidth } ifelse
	  currentdict		% mark [paintdata] dict
	  /PaintProc load	% mark [paintdata] dict paintproc
	end
	gsave
	  false PATredef exec true PATredef
	grestore
	cleartomark		% -
    } bind def
    currentdict
  end				% newdict
  /foo exch			% /foo newlict
  definefont			% newfont
} bind def
% PATpcalc - calculates the starting point and width/height
% of the tile fill for the shape
/PATpcalc {	% - PATpcalc nw nh px py
  PATDict /CurrentPattern get begin
    gsave
	% Set up the coordinate system to Pattern Space
	% and lock down pattern
	PatternGState /cm get setmatrix
	BBox aload pop pop pop translate
	% Determine the bounding box of the shape
	pathbbox			% llx lly urx ury
    grestore
    % Determine (nw, nh) the # of cells to paint width and height
    PatHeight div ceiling		% llx lly urx qh
    4 1 roll				% qh llx lly urx
    PatWidth div ceiling		% qh llx lly qw
    4 1 roll				% qw qh llx lly
    PatHeight div floor			% qw qh llx ph
    4 1 roll				% ph qw qh llx
    PatWidth div floor			% ph qw qh pw
    4 1 roll				% pw ph qw qh
    2 index sub cvi abs			% pw ph qs qh-ph
    exch 3 index sub cvi abs exch	% pw ph nw=qw-pw nh=qh-ph
    % Determine the starting point of the pattern fill
    %(px, py)
    4 2 roll				% nw nh pw ph
    PatHeight mul			% nw nh pw py
    exch				% nw nh py pw
    PatWidth mul exch			% nw nh px py
  end
} bind def

% Save the original routines so that we can use them later on
/oldfill	/fill load def
/oldeofill	/eofill load def
/oldstroke	/stroke load def
/oldshow	/show load def
/oldashow	/ashow load def
/oldwidthshow	/widthshow load def
/oldawidthshow	/awidthshow load def
/oldkshow	/kshow load def

% These defs are necessary so that subsequent procs don't bind in
% the originals
/fill	   { oldfill } bind def
/eofill	   { oldeofill } bind def
/stroke	   { oldstroke } bind def
/show	   { oldshow } bind def
/ashow	   { oldashow } bind def
/widthshow { oldwidthshow } bind def
/awidthshow { oldawidthshow } bind def
/kshow 	   { oldkshow } bind def
/PATredef {
  MyAppDict begin
    {
    /fill { /clip load PATdraw newpath } bind def
    /eofill { /eoclip load PATdraw newpath } bind def
    /stroke { PATstroke } bind def
    /show { 0 0 null 0 0 6 -1 roll PATawidthshow } bind def
    /ashow { 0 0 null 6 3 roll PATawidthshow }
    bind def
    /widthshow { 0 0 3 -1 roll PATawidthshow }
    bind def
    /awidthshow { PATawidthshow } bind def
    /kshow { PATkshow } bind def
  } {
    /fill   { oldfill } bind def
    /eofill { oldeofill } bind def
    /stroke { oldstroke } bind def
    /show   { oldshow } bind def
    /ashow  { oldashow } bind def
    /widthshow { oldwidthshow } bind def
    /awidthshow { oldawidthshow } bind def
    /kshow  { oldkshow } bind def
    } ifelse
  end
} bind def
false PATredef
% Conditionally define setcmykcolor if not available
/setcmykcolor where { pop } {
  /setcmykcolor {
    1 sub 4 1 roll
    3 {
	3 index add neg dup 0 lt { pop 0 } if 3 1 roll
    } repeat
    setrgbcolor - pop
  } bind def
} ifelse
/PATsc {		% colorarray
  aload length		% c1 ... cn length
    dup 1 eq { pop setgray } { 3 eq { setrgbcolor } { setcmykcolor
  } ifelse } ifelse
} bind def
/PATsg {		% dict
  begin
    lw setlinewidth
    lc setlinecap
    lj setlinejoin
    ml setmiterlimit
    ds aload pop setdash
    cc aload pop setrgbcolor
    cm setmatrix
  end
} bind def

/PATDict 3 dict def
/PATsp {
  true PATredef
  PATDict begin
    /CurrentPattern exch def
    % If it's an uncolored pattern, save the color
    CurrentPattern /PaintType get 2 eq {
      /PColor exch def
    } if
    /CColor [ currentrgbcolor ] def
  end
} bind def
% PATstroke - stroke with the current pattern
/PATstroke {
  countdictstack
  save
  mark
  {
    currentpoint strokepath moveto
    PATpcalc				% proc nw nh px py
    clip newpath PATfill
    } stopped {
	(*** PATstroke Warning: Path is too complex, stroking
	  with gray) =
    cleartomark
    restore
    countdictstack exch sub dup 0 gt
	{ { end } repeat } { pop } ifelse
    gsave 0.5 setgray oldstroke grestore
  } { pop restore pop } ifelse
  newpath
} bind def
/PATtcalc {		% modmtx tilingtype PATtcalc tilematrix
  % Note: tiling types 2 and 3 are not supported
  gsave
    exch concat					% tilingtype
    matrix currentmatrix exch			% cmtx tilingtype
    % Tiling type 1 and 3: constant spacing
    2 ne {
	% Distort the pattern so that it occupies
	% an integral number of device pixels
	dup 4 get exch dup 5 get exch		% tx ty cmtx
	XStep 0 dtransform
	round exch round exch			% tx ty cmtx dx.x dx.y
	XStep div exch XStep div exch		% tx ty cmtx a b
	0 YStep dtransform
	round exch round exch			% tx ty cmtx a b dy.x dy.y
	YStep div exch YStep div exch		% tx ty cmtx a b c d
	7 -3 roll astore			% { a b c d tx ty }
    } if
  grestore
} bind def
/PATusp {
  false PATredef
  PATDict begin
    CColor PATsc
  end
} bind def

% left45
11 dict begin
/PaintType 1 def
/PatternType 1 def
/TilingType 1 def
/BBox [0 0 1 1] def
/XStep 1 def
/YStep 1 def
/PatWidth 1 def
/PatHeight 1 def
/Multi 2 def
/PaintData [
  { clippath } bind
  { 32 32 true [ 32 0 0 -32 0 32 ]
	{<808080804040404020202020101010100808080804040404
	020202020101010180808080404040402020202010101010
	080808080404040402020202010101018080808040404040
	202020201010101008080808040404040202020201010101
	808080804040404020202020101010100808080804040404
	0202020201010101>}
     imagemask } bind
] def
/PaintProc {
	pop
	exec fill
} def
currentdict
end
/P4 exch def
1.1111 1.1111 scale %restore scale

/cp {closepath} bind def
/ef {eofill} bind def
/gr {grestore} bind def
/gs {gsave} bind def
/sa {save} bind def
/rs {restore} bind def
/l {lineto} bind def
/m {moveto} bind def
/rm {rmoveto} bind def
/n {newpath} bind def
/s {stroke} bind def
/sh {show} bind def
/slc {setlinecap} bind def
/slj {setlinejoin} bind def
/slw {setlinewidth} bind def
/srgb {setrgbcolor} bind def
/rot {rotate} bind def
/sc {scale} bind def
/sd {setdash} bind def
/ff {findfont} bind def
/sf {setfont} bind def
/scf {scalefont} bind def
/sw {stringwidth} bind def
/tr {translate} bind def
/tnt {dup dup currentrgbcolor
  4 -2 roll dup 1 exch sub 3 -1 roll mul add
  4 -2 roll dup 1 exch sub 3 -1 roll mul add
  4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb}
  bind def
/shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul
  4 -2 roll mul srgb} bind def
/$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def
/$F2psEnd {$F2psEnteredState restore end} def
%%EndProlog

$F2psBegin
10 setmiterlimit
n -1000 3678 m -1000 -1000 l 4931 -1000 l 4931 3678 l cp clip
 0.06000 0.06000 sc
% Polyline
7.500 slw
n 1897 1264 m 1972 1264 l 1972 1664 l 1897 1664 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 1972 1264 m 2047 1264 l 2047 1664 l 1972 1664 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 2047 1264 m 2122 1264 l 2122 1664 l 2047 1664 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 2122 1264 m 2197 1264 l 2197 1664 l 2122 1664 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 2197 1264 m 2272 1264 l 2272 1664 l 2197 1664 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 2272 1264 m 2347 1264 l 2347 1664 l 2272 1664 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 2347 1264 m 2422 1264 l 2422 1664 l 2347 1664 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 2422 1264 m 2497 1264 l 2497 1664 l 2422 1664 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 2497 1264 m 2572 1264 l 2572 1664 l 2497 1664 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 2572 1264 m 2647 1264 l 2647 1664 l 2572 1664 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 2647 1264 m 2722 1264 l 2722 1664 l 2647 1664 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 2722 1264 m 2797 1264 l 2797 1664 l 2722 1664 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 2797 1264 m 2872 1264 l 2872 1664 l 2797 1664 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 2872 1264 m 2947 1264 l 2947 1664 l 2872 1664 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 2947 1264 m 3022 1264 l 3022 1664 l 2947 1664 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 3022 1264 m 3097 1264 l 3097 1664 l 3022 1664 l cp gs col7 0.75 shd ef gr gs col-1 s gr
/Times-Roman ff 90.00 scf sf
1822 1365 m
gs 1 -1 sc (0) col-1 sh gr
/Times-Roman ff 90.00 scf sf
3135 1365 m
gs 1 -1 sc (15) col-1 sh gr
% Polyline
n 2055 704 m 2055 594 l 2535 594 l 2535 704 l cp gs col-1 s gr
% Polyline
n 902 453 m 977 453 l 977 853 l 902 853 l cp gs col-1 s gr
% Polyline
n 977 453 m 1053 453 l 1053 853 l 977 853 l cp gs col-1 s gr
% Polyline
n 1053 453 m 1128 453 l 1128 853 l 1053 853 l cp gs col-1 s gr
% Polyline
n 1128 453 m 1203 453 l 1203 853 l 1128 853 l cp gs col-1 s gr
% Polyline
n 1203 453 m 1277 453 l 1277 853 l 1203 853 l cp gs col-1 s gr
% Polyline
n 1277 453 m 1352 453 l 1352 853 l 1277 853 l cp gs col-1 s gr
% Polyline
n 1352 453 m 1428 453 l 1428 853 l 1352 853 l cp gs col-1 s gr
% Polyline
n 1428 453 m 1502 453 l 1502 853 l 1428 853 l cp gs col-1 s gr
% Polyline
n 1502 453 m 1577 453 l 1577 853 l 1502 853 l cp gs col-1 s gr
% Polyline
n 1577 453 m 1652 453 l 1652 853 l 1577 853 l cp gs col-1 s gr
% Polyline
n 1728 453 m 1803 453 l 1803 853 l 1728 853 l cp gs col7 0.95 shd ef gr gs col-1 s gr
% Polyline
n 1652 453 m 1728 453 l 1728 853 l 1652 853 l cp gs col7 0.95 shd ef gr gs col-1 s gr
% Polyline
n 827 453 m 902 453 l 902 853 l 827 853 l cp gs col-1 s gr
% Polyline
n 1961 2014 m 2036 2014 l 2036 2415 l 1961 2415 l cp gs col-1 s gr
% Polyline
n 2036 2014 m 2111 2014 l 2111 2415 l 2036 2415 l cp gs col-1 s gr
% Polyline
n 2111 2014 m 2186 2014 l 2186 2415 l 2111 2415 l cp gs col-1 s gr
% Polyline
n 2186 2014 m 2261 2014 l 2261 2415 l 2186 2415 l cp gs col-1 s gr
% Polyline
n 2261 2014 m 2336 2014 l 2336 2415 l 2261 2415 l cp gs col-1 s gr
% Polyline
n 2336 2014 m 2412 2014 l 2412 2415 l 2336 2415 l cp gs col-1 s gr
% Polyline
n 2412 2014 m 2487 2014 l 2487 2415 l 2412 2415 l cp gs col-1 s gr
% Polyline
n 2487 2014 m 2562 2014 l 2562 2415 l 2487 2415 l cp gs col-1 s gr
% Polyline
n 2562 2014 m 2637 2014 l 2637 2415 l 2562 2415 l cp gs col-1 s gr
% Polyline
n 2637 2014 m 2711 2014 l 2711 2415 l 2637 2415 l cp gs col-1 s gr
% Polyline
n 2711 2014 m 2786 2014 l 2786 2415 l 2711 2415 l cp gs col-1 s gr
% Polyline
n 2786 2014 m 2861 2014 l 2861 2415 l 2786 2415 l cp gs col-1 s gr
% Polyline
n 2861 2014 m 2937 2014 l 2937 2415 l 2861 2415 l cp gs col-1 s gr
% Polyline
n 2937 2014 m 3012 2014 l 3012 2415 l 2937 2415 l cp gs col-1 s gr
% Polyline
n 3012 2014 m 3087 2014 l 3087 2415 l 3012 2415 l cp gs col-1 s gr
% Polyline
n 752 453 m 827 453 l 827 853 l 752 853 l cp gs col7 0.95 shd ef gr gs col-1 s gr
% Polyline
gs  clippath
1916 1883 m 1882 2002 l 1856 1881 l 1852 2016 l 1912 2018 l cp
clip
n 1695 551 m 1695 1732 l 1890 1732 l 1882 2002 l gs col-1 s gr gr

% arrowhead
n 1916 1883 m 1882 2002 l 1856 1881 l 1886 1882 l 1916 1883 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
gs  clippath
1920 1140 m 1890 1260 l 1860 1140 l 1860 1275 l 1920 1275 l cp
clip
n 1766 551 m 1770 975 l 1890 975 l 1890 1260 l gs col-1 s gr gr

% arrowhead
n 1920 1140 m 1890 1260 l 1860 1140 l 1890 1140 l 1920 1140 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
n 2056 474 m 2056 360 l 2559 360 l 2559 474 l cp gs col7 0.75 shd ef gr gs col-1 s gr
% Polyline
n 2040 929 m 2040 809 l 2549 809 l 2549 929 l cp gs col7 0.95 shd ef gr gs col-1 s gr
% Polyline
n 677 453 m 752 453 l 752 853 l 677 853 l cp gs col-1 s gr
% Polyline
n 603 453 m 677 453 l 677 853 l 603 853 l cp gs col-1 s gr
% Polyline
n 1886 2014 m 1961 2014 l 1961 2415 l 1886 2415 l cp gs /PC [[1.00 1.00 1.00] [0.00 0.00 0.00]] def
15.00 15.00 sc P4 [16 0 0 -16 125.73 134.27] PATmp PATsp ef gr PATusp gs col-1 s gr
% Polyline
gs  clippath
1886 2536 m 1916 2416 l 1946 2536 l 1946 2401 l 1886 2401 l cp
clip
n 1916 2416 m 1916 2641 l gs /PC [[1.00 1.00 1.00] [0.00 0.00 0.00]] def
15.00 15.00 sc P4 [16 0 0 -16 127.73 161.07] PATmp PATsp ef gr PATusp gs col-1 s gr gr

% arrowhead
n 1886 2536 m 1916 2416 l 1946 2536 l 1916 2536 l 1886 2536 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
gs  clippath
821 1046 m 791 1166 l 761 1046 l 761 1181 l 821 1181 l cp
clip
n 791 559 m 791 1166 l gs /PC [[1.00 1.00 1.00] [0.00 0.00 0.00]] def
15.00 15.00 sc P4 [16 0 0 -16 52.73 37.27] PATmp PATsp ef gr PATusp gs col-1 s gr gr

% arrowhead
n 821 1046 m 791 1166 l 761 1046 l 791 1046 l 821 1046 l  cp gs 0.00 setgray ef gr  col-1 s
/Times-Bold ff 150.00 scf sf
2670 725 m
gs 1 -1 sc (Number Capability) col-1 sh gr
/Times-Bold ff 150.00 scf sf
2683 474 m
gs 1 -1 sc (Any Capability) col-1 sh gr
/Times-Roman ff 90.00 scf sf
528 554 m
gs 1 -1 sc (0) col-1 sh gr
/Times-Roman ff 90.00 scf sf
1840 554 m
gs 1 -1 sc (15) col-1 sh gr
/Times-Bold ff 150.00 scf sf
1982 1174 m
gs 1 -1 sc (Capability Registers) col-1 sh gr
/Times-Bold ff 150.00 scf sf
2676 930 m
gs 1 -1 sc (Node Capability) col-1 sh gr
/Times-Bold ff 150.00 scf sf
1959 1939 m
gs 1 -1 sc (Registers Annex) col-1 sh gr
/Times-Bold ff 150.00 scf sf
779 406 m
gs 1 -1 sc (Process Root) col-1 sh gr
/Times-Roman ff 90.00 scf sf
1811 2114 m
gs 1 -1 sc (0) col-1 sh gr
/Times-Roman ff 90.00 scf sf
3124 2114 m
gs 1 -1 sc (15) col-1 sh gr
/Times-Roman ff 135.00 scf sf
1985 2642 m
gs 1 -1 sc (\(Always Zero\)) col-1 sh gr
/Times-Roman ff 135.00 scf sf
333 1312 m
gs 1 -1 sc (\(To Address Space\)) col-1 sh gr
$F2psEnd
rs
end

%%EndDocument

 endTexFig
 488 2615 a Fr(Figure)d(2:)25 b(An)c(ER)m(OS)f(Process)0
2945 y(root)d(of)h(the)g(process)g(structure,)f(an)h(additional)f(node)
f(that)j(holds)0 3044 y(the)g(\(k)o(ernel-implemented\))c(capability)i
(re)o(gisters)i(for)f(that)h(pro-)0 3144 y(cess,)30 b(and)e(some)g
(architecture)e(dependent)g(number)g(of)h(anne)o(x)0
3244 y(re)o(gister)c(nodes)f(that)i(hold)f(the)g(re)o(gister)g(v)n
(alues)g(of)g(the)h(process)0 3343 y(when)c(it)h(is)h(not)e(running.)k
(These)c(re)o(gister)g(v)n(alues)g(are)h(stored)f(in)0
3443 y Fi(number)h(capabilities)p Fr(.)0 3576 y(While)c(node)f
(capabilities)h(often)f(serv)o(e)g(as)i(address)e(space)h(capa-)0
3675 y(bilities,)28 b(the)o(y)d(are)g(not)h(suitable)f(for)g(use)h(as)h
(process)e(capabili-)0 3775 y(ties.)g(The)18 b(capabilities)f(in)h(a)g
(process)g(node)f(must)g(be)h(of)g(speci\002c)0 3875
y(types)e(for)g(the)g(process)g(to)g(be)g Fp(well-formed)p
Fr(.)1289 3844 y Fq(6)1346 3875 y Fr(In)g(addition,)g(there)0
3974 y(is)24 b(a)f(reserv)o(ed)e(slot)i(in)g(the)f(process)h(root)f
(kno)n(wn)f(as)i(the)g Fp(br)o(and)p Fr(.)0 4074 y(The)j(brand)f(is)j
(part)e(of)g(the)h(ER)m(OS)g(con\002nement)e(mechanism,)0
4173 y(and)d(must)h(not)g(be)g(visible)g(or)f(modi\002able)g(by)g
(manipulators)f(of)0 4273 y(the)f(process.)0 4406 y(A)30
b Fi(pr)o(ocess)g(capability)f Fr(con)m(v)o(e)o(ys)e(the)j(authority)e
(to)h(start)i(and)0 4506 y(stop)22 b(a)g(process,)g(to)g(e)o(xamine)f
(its)i(re)o(gisters)e(\(both)g(data)h(and)f(ca-)0 4605
y(pability\),)16 b(to)h(alter)g(or)f(replace)g(its)i(address)f(space,)g
(to)g(change)e(its)0 4705 y(scheduling)20 b(authority)-5
b(,)19 b(or)i(to)g(alter)h(its)g(f)o(ault)f(handler)-5
b(.)27 b(This)21 b(en-)0 4804 y(ables)f(the)f(holder)f(of)h(a)h
(process)f(capability)f(to)i(alter)f(essentially)0 4904
y(an)o(ything)h(about)h(the)h(process;)g(its)h(adv)n(antage)d(o)o(v)o
(er)h(a)h(node)f(ca-)0 5004 y(pability)k(is)h(that)f(it)h(enforces)e
(the)h(capability)g(type)g(restrictions)0 5103 y(for)20
b(well-formed)e(processes)i(and)f(protects)h(the)g(brand.)p
0 5250 764 4 v 90 5306 a Fh(6)120 5329 y Fg(The)h Fa(k)o(ernel)j
Fg(is)e(not)h(jeopardized)i(by)d(malformed)i(processes.)36
b(Such)23 b(pro-)0 5408 y(cesses)18 b(do)f(not)g(run,)g(b)o(ut)g(the)h
(ef)n(fects)h(of)e(in)m(v)o(oking)h(one)g(are)g(well-de\002ned.)1992
91 y Fd(4.6)99 b(User)l(-Le)o(v)o(el)25 b(Objects)1992
287 y Fr(Just)k(as)h(processes)e(are)h(named)e(by)i(process)f
(capabilities,)j(the)1992 386 y(programs)20 b(embodied)g(within)j
(these)f(processes)g(are)h(named)e(by)1992 486 y Fi(start)29
b(capabilities)p Fr(.)56 b(Performing)28 b(a)i(CALL)h(on)f(a)h
(capability)1992 586 y(causes)22 b(the)g(supervisor)f(to)h(f)o
(abricate)f(a)i Fi(r)o(esume)f(capability)f Fr(to)1992
685 y(the)e(caller)-5 b(.)25 b(This)19 b(capability)g(is)h(pro)o(vided)
d(to)i(the)h(recipient,)e(and)1992 785 y(con)m(v)o(e)o(ys)25
b(the)j(right)f(to)g(reply)g(to)h(this)g(call.)48 b(As)28
b(with)g(all)g(other)1992 884 y(capabilities,)k(the)e(resume)g
(capability)f(can)h(be)g(transferred)f(or)1992 984 y(copied.)44
b(All)27 b(copies)g(of)g(a)g(resume)g(capability)f(are)g(ef)n
(\002ciently)1992 1084 y(in)m(v)n(alidated)f(when)h(an)o(y)g(of)h(them)
f(is)i(in)m(v)n(ok)o(ed,)f(which)f(ensures)1992 1183
y(that)20 b(e)n(v)o(ery)f(CALL)h(recei)n(v)o(es)g(at)g(most)g(one)g
(return.)1992 1316 y(The)27 b Fe(C)6 b(apI)h(nf)i(o)28
b Fr(\002eld)g(of)f(the)h(start)h(capability)d(is)j(set)g(when)e(it)
1992 1416 y(is)32 b(f)o(abricated,)g(and)f(is)h(pro)o(vided)d(to)j(the)
f(recipient)g(by)f(the)i(k-)1992 1515 y(ernel)25 b(whene)n(v)o(er)f
(the)i(recipient)f(is)i(in)m(v)n(ok)o(ed.)41 b(This)26
b(allo)n(ws)h(the)1992 1615 y(process)d(to)h(pro)o(vide)e(dif)n(ferent)
g(interf)o(aces)h(to)h(dif)n(ferent)f(caller)n(-)1992
1715 y(s,)d(and)g(can)g(be)f(used)h(to)g(distinguish)f(service)h(v)o
(ersions,)f(service)1992 1814 y(classes)k(\(e.g.)35 b(administrator)21
b(v/s)j(user\),)g(or)f(distinct)h(\223objects\224)1992
1914 y(implemented)18 b(by)i(the)g(process.)1992 2047
y(In)m(v)n(oking)27 b(a)j(start)h(or)e(resume)h(capability)f(to)h(a)g
(badly-formed)1992 2146 y(process)18 b(beha)n(v)o(es)g(as)h(though)e
(one)h(had)h(in)m(v)n(ok)o(ed)e(the)i(zero)f(num-)1992
2246 y(ber)24 b(k)o(e)o(y)-5 b(.)37 b(All)25 b(in)m(v)n(ocations)e(of)h
(the)h(zero)f(number)f(k)o(e)o(y)h(return)f(a)1992 2346
y(result)h(code)h(that)f(\(by)h(con)m(v)o(ention\))c(is)26
b(not)e(used)h(by)f(an)o(y)g(other)1992 2445 y(object.)1992
2749 y Fd(4.7)99 b(Exceptions)1992 2944 y Fr(All)21 b(e)o(xceptions)e
(tak)o(en)i(by)f(a)h(process)g(are)f(redirected)g(by)g(the)h(k-)1992
3043 y(ernel)c(to)i(a)f(process)g(kno)n(wn)f(as)h(a)h
Ff(k)o(eeper)p Fr(.)k(Both)c(address)e(spaces)1992 3143
y(and)f(processes)h(can)f(designate)h(a)g(k)o(eeper)f(by)h(placing)f(a)
h(start)h(ca-)1992 3243 y(pability)e(in)i(the)f(appropriate)e(slot)j
(of)f(the)g(address)g(space)h(or)f(pro-)1992 3342 y(cess.)24
b(When)17 b(an)g(e)o(xception)f(occurs,)g(the)h(k)o(ernel)g
(synthesizes)g(an)1992 3442 y(upcall)f(to)h(the)g(k)o(eeper)f(process)g
(with)h(a)h(message)e(describing)g(the)1992 3542 y(e)o(xception)k
(conditions.)30 b(Memory)21 b(e)o(xceptions)g(are)h(directed)f(to)1992
3641 y(the)16 b(appropriate)f(address)h(space)g(k)o(eeper)m(,)g(or)h
(if)g(none)e(is)j(de\002ned,)1992 3741 y(to)h(the)g(process)g(k)o
(eeper)-5 b(.)24 b(All)c(other)e(e)o(xceptions)g(are)h(reported)e(to)
1992 3841 y(the)j(process)f(k)o(eeper)-5 b(.)1992 4186
y Fj(5)119 b(The)30 b(Stor)n(e)1992 4412 y Fr(Much)j(of)g(the)h
(bene\002t)g(of)f(the)h(ER)m(OS)h(system)f(deri)n(v)o(es)f(from)1992
4511 y(careful)27 b(or)o(ganization)d(of)k(the)g(store)h(and)e(an)h(ef)
n(\002cient)g(consis-)1992 4611 y(tent)20 b(snapshot)f(mechanism.)1992
4914 y Fd(5.1)99 b(Or)o(ganization)24 b(of)h(the)h(Stor)n(e)1992
5109 y Fr(All)20 b(objects)g(in)g(ER)m(OS)g(can)f(be)h(reduced)e(to)i
(node)f(and)g(page)g(ob-)1992 5209 y(jects.)49 b(Ev)o(ery)27
b(page)g(and)h(node)f(is)i(uniquely)d(identi\002ed)i(by)g(an)1992
5309 y Fi(object)21 b(identi\002er)i Fr(\(OID\))f(which)g(encodes)f
(its)j(location)d(in)i(the)1992 5408 y(store.)57 b(The)31
b(store)g(itself)g(is)h(managed)e(as)h(a)h(set)g(of)f(\(possibly)1929
5657 y(5)p eop
%%Page: 6 6
6 5 bop 0 91 a Fr(duple)o(x)o(ed\))15 b(ranges)i(of)h(consecuti)n(v)o
(ely)e(numbered)f(pages)j(and)f(n-)0 191 y(odes)h(\(Figure)f(3\).)24
b(F)o(or)18 b(simplicity)g(of)g(I/O)h(management,)d(nodes)213
301 y
 11709153 4670504 0 0 11709153 4670504 startTexFig
 213 301 a
%%BeginDocument: store.eps
%!PS-Adobe-2.0 EPSF-2.0
%%Title: store.fig
%%Creator: fig2dev Version 3.2 Patchlevel 1
%%CreationDate: Wed Oct 13 21:24:04 1999
%%For: shapj@bonzo.watson.ibm.com (Jonathan Shapiro)
%%Orientation: Portrait
%%BoundingBox: 0 0 178 71
%%Pages: 0
%%BeginSetup
%%EndSetup
%%Magnification: 1.0000
%%EndComments
/$F2psDict 200 dict def
$F2psDict begin
$F2psDict /mtrx matrix put
/col-1 {0 setgray} bind def
/col0 {0.000 0.000 0.000 srgb} bind def
/col1 {0.000 0.000 1.000 srgb} bind def
/col2 {0.000 1.000 0.000 srgb} bind def
/col3 {0.000 1.000 1.000 srgb} bind def
/col4 {1.000 0.000 0.000 srgb} bind def
/col5 {1.000 0.000 1.000 srgb} bind def
/col6 {1.000 1.000 0.000 srgb} bind def
/col7 {1.000 1.000 1.000 srgb} bind def
/col8 {0.000 0.000 0.560 srgb} bind def
/col9 {0.000 0.000 0.690 srgb} bind def
/col10 {0.000 0.000 0.820 srgb} bind def
/col11 {0.530 0.810 1.000 srgb} bind def
/col12 {0.000 0.560 0.000 srgb} bind def
/col13 {0.000 0.690 0.000 srgb} bind def
/col14 {0.000 0.820 0.000 srgb} bind def
/col15 {0.000 0.560 0.560 srgb} bind def
/col16 {0.000 0.690 0.690 srgb} bind def
/col17 {0.000 0.820 0.820 srgb} bind def
/col18 {0.560 0.000 0.000 srgb} bind def
/col19 {0.690 0.000 0.000 srgb} bind def
/col20 {0.820 0.000 0.000 srgb} bind def
/col21 {0.560 0.000 0.560 srgb} bind def
/col22 {0.690 0.000 0.690 srgb} bind def
/col23 {0.820 0.000 0.820 srgb} bind def
/col24 {0.500 0.190 0.000 srgb} bind def
/col25 {0.630 0.250 0.000 srgb} bind def
/col26 {0.750 0.380 0.000 srgb} bind def
/col27 {1.000 0.500 0.500 srgb} bind def
/col28 {1.000 0.630 0.630 srgb} bind def
/col29 {1.000 0.750 0.750 srgb} bind def
/col30 {1.000 0.880 0.880 srgb} bind def
/col31 {1.000 0.840 0.000 srgb} bind def

end
save
-17.0 88.0 translate
1 -1 scale

/cp {closepath} bind def
/ef {eofill} bind def
/gr {grestore} bind def
/gs {gsave} bind def
/sa {save} bind def
/rs {restore} bind def
/l {lineto} bind def
/m {moveto} bind def
/rm {rmoveto} bind def
/n {newpath} bind def
/s {stroke} bind def
/sh {show} bind def
/slc {setlinecap} bind def
/slj {setlinejoin} bind def
/slw {setlinewidth} bind def
/srgb {setrgbcolor} bind def
/rot {rotate} bind def
/sc {scale} bind def
/sd {setdash} bind def
/ff {findfont} bind def
/sf {setfont} bind def
/scf {scalefont} bind def
/sw {stringwidth} bind def
/tr {translate} bind def
/tnt {dup dup currentrgbcolor
  4 -2 roll dup 1 exch sub 3 -1 roll mul add
  4 -2 roll dup 1 exch sub 3 -1 roll mul add
  4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb}
  bind def
/shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul
  4 -2 roll mul srgb} bind def
/$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def
/$F2psEnd {$F2psEnteredState restore end} def
%%EndProlog

$F2psBegin
10 setmiterlimit
n -1000 2465 m -1000 -1000 l 4237 -1000 l 4237 2465 l cp clip
 0.06000 0.06000 sc
% Polyline
7.500 slw
n 2625 300 m 1425 300 l 1425 900 l 2625 900 l cp gs col-1 s gr
% Polyline
n 300 300 m 1050 300 l 1050 900 l 300 900 l cp gs col-1 s gr
% Polyline
n 1425 300 m 1050 300 l 1050 900 l 1425 900 l cp gs col7 0.95 shd ef gr gs col-1 s gr
% Polyline
n 3225 300 m 2625 300 l 2625 900 l 3225 900 l cp gs col7 0.95 shd ef gr gs col-1 s gr
% Polyline
gs  clippath
2752 975 m 2850 900 l 2798 1012 l 2883 907 l 2836 870 l cp
clip
n 2550 1275 m 2850 900 l gs col7 0.95 shd ef gr gs col-1 s gr gr

% arrowhead
n 2752 975 m 2850 900 l 2798 1012 l 2775 994 l 2752 975 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
gs  clippath
1378 969 m 1275 900 l 1398 912 l 1271 867 l 1251 923 l cp
clip
n 2325 1275 m 1275 900 l gs col7 0.95 shd ef gr gs col-1 s gr gr

% arrowhead
n 1378 969 m 1275 900 l 1398 912 l 1388 940 l 1378 969 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
gs  clippath
1903 922 m 2025 900 l 1928 977 l 2051 921 l 2026 866 l cp
clip
n 1200 1275 m 2025 900 l gs col7 0.95 shd ef gr gs col-1 s gr gr

% arrowhead
n 1903 922 m 2025 900 l 1928 977 l 1916 950 l 1903 922 l  cp gs 0.00 setgray ef gr  col-1 s
% Polyline
gs  clippath
814 1006 m 750 900 l 856 964 l 761 868 l 718 911 l cp
clip
n 1125 1275 m 750 900 l gs col7 0.95 shd ef gr gs col-1 s gr gr

% arrowhead
n 814 1006 m 750 900 l 856 964 l 835 985 l 814 1006 l  cp gs 0.00 setgray ef gr  col-1 s
/Times-Roman ff 150.00 scf sf
825 1425 m
gs 1 -1 sc (page ranges) col-1 sh gr
/Times-Roman ff 150.00 scf sf
2100 1425 m
gs 1 -1 sc (node ranges) col-1 sh gr
$F2psEnd
rs

%%EndDocument

 endTexFig
 579 1076 a Fr(Figure)k(3:)25 b(Disk)c(Ranges)0 1351
y(are)k(clustered)f(into)g(page-size)g(units)h(for)f(purposes)f(of)i
(storage)0 1451 y(on)20 b(the)g(disk.)0 1583 y(On)e(startup,)f(the)h(k)
o(ernel)f(scans)h(all)g(attached)f(disks)g(to)h(load)f(their)0
1683 y(range)h(tables,)h(and)g(constructs)f(an)h(in-core)f(master)h
(table)g(of)g(ob-)0 1783 y(ject)i(ranges.)j(Each)c(range)f(table)h
(entry)f(is)i(of)f(the)g(form)248 1948 y Fo(f)p Fe(pag)s(e;)14
b(node)p Fo(g)j(\002)h Fb([)p Fe(S)5 b(tar)r(t)21 b(O)r(I)7
b(D)r(;)14 b(E)5 b(nd)21 b(O)r(I)7 b(D)r Fb(\))0 2113
y Fr(The)20 b(in-core)g(table)h(is)g(relati)n(v)o(ely)f(small,)h(and)f
(is)i(k)o(ept)e(sorted)g(by)0 2212 y(starting)g(OID.)0
2345 y(When)28 b(a)g(capability)g(for)f(an)h(object)g(is)h(\002rst)g
(in)m(v)n(ok)o(ed,)f(the)g(ob-)0 2445 y(ject)h(must)f(be)g(brought)f
(in)h(from)f(the)i(disk.)49 b(T)-7 b(o)29 b(do)e(so,)k(the)d(k-)0
2544 y(ernel)d(consults)f(the)h(master)g(range)f(table)h(to)g(\002nd)g
(the)g(physical)0 2644 y(location)17 b(of)h(the)g(containing)e(range)h
(in)h(the)g(store,)g(computes)f(the)0 2744 y(of)n(fset)30
b(within)h(that)g(range)f(of)g(the)h(disk)g(page)f(containing)f(the)0
2843 y(object,)24 b(and)f(initiates)i(a)f(disk)g(read)f(operation.)35
b(Once)23 b(fetched,)0 2943 y(the)i(object)f(resides)g(in)h(an)g
(in-memory)d(object)i(cache,)h(and)f(the)0 3042 y(capability)c(is)i
Fp(pr)m(epar)m(ed)h Fr(by)e(modifying)d(it)k(to)g(point)e(directly)h
(to)0 3142 y(the)28 b(in-core)e(object.)47 b(T)-7 b(o)28
b(f)o(acilitate)f(capability)g(depreparation)0 3242 y(on)i(object)g
(remo)o(v)n(al,)h(the)f(capability)g(is)h(placed)f(in)g(a)h(doubly-)0
3341 y(link)o(ed)18 b(list)h(whose)g(head)e(is)j(the)e(object)g
(itself.)25 b(The)18 b(preparation)0 3441 y(and)h(depreparation)e(of)j
(capabilities)f(is)i(entirely)e(transparent)f(to)0 3541
y(application)h(code.)0 3673 y(This)i(storage)f(or)o(ganization)e(has)j
(se)n(v)o(eral)f(adv)n(antages,)f(notably)0 3773 y(in)29
b(the)f(absence)g(of)h(an)o(y)e(\223indirection)g(blocks\224.)50
b(In)28 b(a)h(system)0 3873 y(ha)n(ving)c(a)i(2)g(terabyte)e(store)h
(of)g(1000)f(2)i(gigabyte)d(disks,)k(each)0 3972 y(ha)n(ving)21
b(64)h(ranges)g(\(an)f(unusually)g(e)o(xpensi)n(v)o(e)f
(con\002guration\),)0 4072 y(the)g(total)h(o)o(v)o(erhead)d(to)i
(locate)g(the)h(containing)d(disk)i(page)g(is)h(16)0
4172 y Fp(in-memory)d Fr(comparisons)f(to)h(tra)n(v)o(erse)g(the)h
(sorted)f(range)f(table.)0 4271 y(This)30 b(multi-terabyte)e(system)i
(an)g(in-core)f(table)h(o)o(v)o(erhead)d(of)0 4371 y(1.2)c(me)o
(gabytes,)f(which)i(is)g(considerably)e(less)j(than)e(w)o(ould)g(be)0
4470 y(used)d(by)g(an)g(equi)n(v)n(alent)e(number)h(of)h(\002le)g
(systems.)1513 4440 y Fq(7)0 4738 y Fd(5.2)99 b(The)26
b(Checkpoint)h(Mechanism)0 4927 y Fr(In)j(addition)f(to)h(page)g(and)g
(and)f(node)g(ranges,)j(the)f(store)f(also)0 5027 y(contains)24
b Fi(log)g(ranges)p Fr(.)36 b(Before)24 b(an)g(object)g(in)h(the)f
(main)g(mem-)0 5126 y(ory)d(cache)g(can)h(be)g(modi\002ed,)f(space)g
(is)i(reserv)o(ed)e(for)g(it)h(within)p 0 5172 764 4
v 90 5227 a Fh(7)120 5251 y Fg(One)15 b(of)g(our)g(early)i(users)e(has)
g(an)h(application)j(that)d(generates)i(14)d(terabytes)0
5329 y(of)22 b(ne)n(w)h(data)g(per)f(year)m(,)i(all)f(of)f(which)h
(must)f(be)g(online)i(for)e(periods)h(of)f(man)o(y)0
5408 y(years.)1992 91 y Fr(the)31 b(log)g(range.)58 b(Objects)31
b(within)g(the)h(log)f(are)g(not)h(stored)e(in)1992 191
y(OID)25 b(order;)i(the)e(log)h(contains)e(o)o(v)o(erhead)f(pages)i
(that)h(pro)o(vide)1992 291 y(a)21 b(directory)f(of)g(objects)h(in)h
(the)f(log.)27 b(This)22 b(directory)d(is)j(not)f(ref-)1992
390 y(erenced)f(during)f(normal)h(operation,)g(as)i(a)g(complete)e
(directory)1992 490 y(of)f(the)i(log)e(is)j(maintained)c(in)j(memory)-5
b(.)1992 623 y(On)25 b(a)h(periodic)e(basis,)j(a)f(dedicated)e(service)
h(process)g(initiates)1992 722 y(a)32 b Fi(checkpoint)g
Fr(operation.)58 b(The)31 b(checkpoint)f(operation)g(sta-)1992
822 y(bilizes)f(a)g(systemwide)f(consistent)h(image)f(via)h(a)g(three)f
(phase)1992 922 y(process:)c(snapshot,)19 b(stabilization,)h(and)f
(migration.)1992 1174 y Fi(Snapshot)82 b Fr(The)23 b(snapshot)e(phase)i
(ef)n(\002ciently)f(creates)g(a)h(con-)1992 1274 y(sistent)d(snapshot)g
(of)g(the)g(entire)g(system:)2054 1465 y(1.)41 b(All)20
b(dirty)g(objects)g(are)g(mark)o(ed)f(cop)o(y)g(on)h(write.)2054
1627 y(2.)41 b(All)20 b(page)g(table)g(entries)g(are)g(mark)o(ed)f
(read-only)-5 b(.)2054 1789 y(3.)41 b(The)29 b(thread)h(list)h(is)g
(tra)n(v)o(ersed,)h(and)e(the)g(in-core)f(check-)2158
1889 y(point)20 b(directory)f(entry)h(for)g(the)g(root)g(node)g(of)h
(each)f(acti)n(v)o(e)2158 1989 y(process)h(is)i(updated)d(to)j
(re\003ect)f(the)g(f)o(act)g(that)g(the)g(process)2158
2088 y(w)o(as)f(running)d(at)i(the)h(time)f(of)g(the)g(checkpoint.)1992
2280 y(Snapshot)i(is)i(a)f(synchronous)e(operation.)32
b(The)22 b(current)g(imple-)1992 2379 y(mentation)16
b(tak)o(es)i(comfortably)d(under)i(100ms)g(on)g(a)h(slo)n(w)h(i486,)
1992 2479 y(and)f(can)i(be)f(shrunk)f(by)h(further)f(e)o(xploitation)g
(of)h(lazy)g(marking)1992 2579 y(to)27 b(a)g(fe)n(w)g(microseconds.)44
b(Ha)n(ving)27 b(constructed)e(a)j(consistent)1992 2678
y(snapshot,)19 b(e)o(x)o(ecution)f(is)j(permitted)e(to)h(resume.)1992
2931 y Fi(Stabilization)81 b Fr(Once)32 b(a)h(snapshot)e(has)i(been)e
(captured,)j(the)1992 3030 y(frozen)16 b(objects)h(are)g
(asynchronously)d(written)j(to)h(the)g(pre)n(vious-)1992
3130 y(ly)j(reserv)o(ed)f(space)i(in)f(the)h(checkpoint)d(log.)28
b(When)22 b(all)g(objects)1992 3230 y(frozen)d(by)i(the)g(checkpoint)e
(ha)n(v)o(e)h(gone)h(to)g(the)g(log,)g(the)g(check-)1992
3329 y(point)e(directory)f(is)j(written)e(to)h(the)g(log.)25
b(Finally)-5 b(,)19 b(a)h(ne)n(w)g(check-)1992 3429 y(point)g(header)g
(is)j(written)e(to)g(indicate)g(that)h(the)f(checkpoint)e(has)1992
3529 y(committed.)1992 3661 y(Stabilization)28 b(does)i(not)f(violate)g
(the)h(real-time)f(requirement.)1992 3761 y(The)h(cost)h(of)g
(stabilization)f(is)i(b)n(uilt)f(in)h(to)f(the)g(cost)g(of)g(dirty-)
1992 3861 y(ing)f(objects;)35 b(e)n(v)o(ery)29 b(object)h(dirtied)g
(will)h(cause)g(at)g(most)f(tw)o(o)1992 3960 y(stabilization)23
b(writes)h(for)g(objects)g(of)f(that)h(type.)36 b(These)24
b(writes)1992 4060 y(are)29 b(asynchronous)e(and)i(non-blocking,)e(pro)
o(vided)g(that)j(there)1992 4160 y(is)d(suf)n(\002cient)f(main)h
(memory)e(and)h(log)g(space)h(to)g(allo)n(w)g(a)g(ne)n(w)1992
4259 y(object)19 b(to)i(be)f(dirtied.)1992 4512 y Fi(Migration)81
b Fr(After)29 b(the)h(checkpoint)d(has)i(committed,)h(a)g
Fi(mi-)1992 4611 y(grator)21 b Fr(is)j(started)f(to)h(cop)o(y)e(the)h
(objects)g(back)g(to)g(their)g(of)n(\002cial)1992 4711
y(locations)i(within)g(page)g(and)h(node)f(ranges.)41
b(Because)26 b(the)g(mi-)1992 4811 y(grator)j(w)o(orks)g(on)h(lar)o(ge)
f(collections)h(of)g(objects)g(whose)g(disk)1992 4910
y(locations)21 b(can)h(be)g(sorted,)f(the)h(current)f(ER)m(OS)h
(migrator)f(is)i(ca-)1992 5010 y(pable)i(of)h(saturating)g(the)g
(sustainable)g(disk)g(subsystem)g(band-)1992 5109 y(width)g(on)g(most)g
(machines.)43 b(The)26 b(principle)g(dif)n(\002culty)f(in)i(mi-)1992
5209 y(gration)21 b(is)i(slo)n(wing)f(it)h(do)n(wn)e(enough)f(to)j(use)
g(the)f(machine)f(for)1992 5309 y(other)g(purposes)h(\()p
Fp(Y)-8 b(es,)23 b(this)g(is)h(hyperbole)o(.)30 b(It)23
b(will)h(be)f(r)m(eplaced)1992 5408 y(by)d(r)m(eal)g(number)o(s)g(when)
g(we)h(have)e(them)i(in)f(a)g(fe)o(w)h(weeks)p Fr(\).)1929
5657 y(6)p eop
%%Page: 7 7
7 6 bop 1105 78 a Fr(Sup)157 b(Sup)181 b(Sup)327 b(Sup)360
b(Sup)198 b(S+U)609 178 y(Case)335 b(I-refs)106 b(D-refs)98
b(ITLB)21 b(miss)99 b(DTLB)21 b(miss)100 b(c)o(ycles)121
b(time)p 559 211 2782 4 v 609 281 a(Null)20 b(IPC)199
b(28.6)140 b(58.14)122 b(0)415 b(1)448 b(206)202 b(2.485)18
b Fe(\026S)609 380 y Fr(14)i(byte)f(IPC)100 b(36.51)e(82.04)122
b(1.5)352 b(1.5)385 b(333.64)97 b(3.68)19 b Fe(\026S)609
480 y Fr(P)o(age)h(F)o(ault)145 b(???)176 b(???)200 b(???)346
b(???)379 b(???)217 b(?)p Fn(\230)p Fr(3)20 b Fe(\026S)1343
658 y Fr(T)-7 b(able)20 b(3:)26 b(Supervisor)18 b(footprint)g(\226)j
(p120)0 1008 y(It)30 b(is)h(rare)f(for)f(a)i(checkpoint)d(to)i(occup)o
(y)f(more)g(than)h(30\045)f(of)0 1107 y(the)d(log)h(before)e
(committing.)42 b(No)26 b(single)h(checkpoint)d(is)j(per)n(-)0
1207 y(mitted)i(to)g(occup)o(y)e(more)h(than)g(70\045)h(of)g(the)g(a)n
(v)n(ailable)f(log)h(s-)0 1307 y(pace.)42 b(Allo)n(wing)24
b(this)j(much)e(of)g(the)h(log)g(to)g(be)f(committed)g(to)0
1406 y(a)i(single)f(checkpoint)e(serv)o(es)i(to)g(dampen)e(jitter)j(in)
f(page)g(dirty)0 1506 y(rates)e(across)g(checkpoints.)34
b(Restricting)24 b(the)g(checkpoints)d(en-)0 1606 y(sures)h(that)g(a)g
(stable)h(rate)f(of)f(tw)o(o-stage)h(migration)e(throughput)0
1705 y(is)h(achie)n(v)o(ed)e(for)g(lar)o(ge)g(object)h(mutations.)0
2041 y Fj(6)119 b(Reser)o(v)o(es)0 2265 y Fr(In)17 b(addition)f(to)h
(capabilities)g(for)g(real)g(resources,)g(ER)m(OS)h(imple-)0
2364 y(ments)i(capabilities)g(for)f(consumable)g(resources)g(and)g
(resource)0 2464 y(virtualization)27 b(in)i(the)f(form)g(of)g
(processor)f(capacity)h(reserv)o(es)0 2563 y(and)20 b(w)o(orking)e(set)
j(reserv)o(es.)0 2857 y Fd(6.1)99 b(Pr)n(ocessor)25 b(Capacity)g(Reser)
o(v)o(es)0 3050 y Fr(A)31 b Fi(pr)o(ocessor)e(capacity)g(r)o(eser)o(v)o
(e)h Fr(is)h(a)f(6-tuple)f(of)h(the)g(form:)0 3150 y(\(period,)22
b(duration,)h(quanta,)f(start)i(time,)g(acti)n(v)o(e)f(priority)-5
b(,)23 b(inac-)0 3250 y(ti)n(v)o(e)f(priority\).)30 b(The)22
b Fp(dur)o(ation)e Fr(speci\002es)j(the)f(number)f(of)h(guar)n(-)0
3349 y(anteed)29 b(nanoseconds)e(of)j(computation)d(within)j(each)f
Fp(period)p Fr(,)0 3449 y(be)o(ginning)19 b(at)k(the)f(gi)n(v)o(en)e
Fp(start)j(time)f Fr(\(immediately)e(if)j(the)f(start)0
3549 y(time)28 b(is)g(zero\).)46 b(The)27 b Fp(quanta)e
Fr(speci\002es)j(ho)n(w)f(often)g(a)h(process)0 3648
y(running)c(under)h(this)h(reserv)o(e)f(will)i(be)f(preempted)e(in)j(f)
o(a)n(v)n(or)e(of)0 3748 y(other)30 b(ready)g(processes)h(under)f(the)h
(same)g(reserv)o(e.)57 b(The)30 b Fp(ac-)0 3847 y(tive)h(priority)g
Fr(gi)n(v)o(es)f(the)g(priority)f(of)h(this)h(process)f(during)f(its)0
3947 y(reserv)o(ed)20 b(period.)29 b(The)22 b Fp(inactive)f(priority)i
Fr(indicates)e(the)h(prior)n(-)0 4047 y(ity)28 b(\(if)f(an)o(y\))g
(with)h(which)f(the)g(process)h(runs)f(when)g(its)h(period)0
4146 y(has)19 b(been)f(depleted.)23 b(Reserv)o(es)18
b(whose)g(inacti)n(v)o(e)g(priority)f(is)i(be-)0 4246
y(lo)n(w)25 b(that)g(of)f(the)h(k)o(ernel)f(idle)h(thread)e(\(which)h
(is)i(al)o(w)o(ays)f(ready)0 4346 y(to)20 b(run\))e(will)i(not)f(e)o(x)
o(ecute)g(outside)g(of)g(their)g(reserv)o(ed)f(duration.)0
4478 y(Processor)34 b(reserv)o(es)g(are)g(allocated)g(by)g(an)h(user)n
(-le)n(v)o(el)e(agen-)0 4578 y(t)c(kno)n(wn)d(as)j(the)f
Fi(r)o(eser)o(v)o(e)f(manager)p Fr(.)47 b(The)28 b(reserv)o(e)f
(manager)0 4678 y(accepts)20 b(requests)f(for)g(reserv)o(es,)g
(determines)f(if)i(those)f(requests)0 4777 y(can)h(be)g(met)h(without)e
(violating)h(pre)n(vious)e(reserv)n(ations,)h(and)h(if)0
4877 y(so,)30 b(returns)e(a)g(capability)g(to)g(an)g(appropriate)e(k)o
(ernel)h(reserv)o(e.)0 4977 y(This)i(reserv)o(e)g(capability)f(can)h
(be)g(placed)g(in)g(the)g(schedule)g(s-)0 5076 y(lot)22
b(of)g(a)h(process')-5 b(s)22 b(root)g(node;)g(all)h(processes)f
(sharing)f(a)h(gi)n(v)o(en)0 5176 y(reserv)o(e)d(capability)g(will)i
(run)f(under)f(the)h(named)f(reserv)o(e.)0 5309 y(In)27
b(contrast)g(to)g(pre)n(vious)f(implementations)f([Kit93)o(,)j(Mer93)n
(],)0 5408 y(Processor)36 b(reserv)o(es)g(are)h Fp(not)h
Fr(inherited)e(across)h(IPC)g(opera-)1992 1008 y(tions.)j(Priority)25
b(inheritance)f(raises)h(a)h(host)g(of)f(protection)e(do-)1992
1107 y(main)j(violation)f(issues)j(\226)f(if)g(reserv)o(es)f(are)h
(inherited,)f(a)i(caller)1992 1207 y(might)21 b(call)h(a)g(service)f
(and)g(then)h(shut)f(of)n(f)g(its)i(reserv)o(e,)e(den)o(ying)1992
1307 y(service)d(to)h(other)f(callers.)24 b(Reserv)o(e)19
b(inheritance)e(lends)h(itself)h(to)1992 1406 y(\223QoS)k(cross-talk,)
-6 b(\224)24 b([Les96)n(])g(\(which)f(manifests)g(as)h(v)n(ariance\),)
1992 1506 y(and)j(understanding)e(the)j(beha)n(vior)e(of)i(nested)g
(serv)o(er)f(calls)h(in)1992 1606 y(the)20 b(f)o(ace)h(of)f(priority)g
(inheritance)f(is)i(dif)n(\002cult.)26 b(Instead,)20
b(ER)m(OS)1992 1705 y(enables)j(each)h(application)f(to)i(construct)e
(a)i(single)f(end-to-end)1992 1805 y(reserv)n(ation)18
b(by)h(instancing)g(its)i(services)f(under)e(whate)n(v)o(er)h(pro-)1992
1904 y(cessor)h(reserv)o(e)f(is)i(appropriate.)1992 2037
y(The)44 b(ER)m(OS)i(CPU)g(reserv)o(e)e(implementation)e(dif)n(fers)j
(from)1992 2137 y(pre)n(vious)30 b(implementations)g(by)i(unifying)e
(reserv)o(es)i(and)f(pri-)1992 2236 y(ority)36 b(management.)73
b(Depending)35 b(on)i(the)g(selected)g(admis-)1992 2336
y(sion)24 b(control)f(mechanism,)i(reserv)o(es)f(can)g(be)h(used)f(to)h
(pro)o(vide)1992 2436 y(isochronous)20 b(scheduling)h(guarantees)g(or)i
(softer)f(periodic)f(ser)n(-)1992 2535 y(vice)j(at)i(high)d(priority)-5
b(.)38 b(W)-7 b(e)25 b(ha)n(v)o(e)g(found)e(it)i(occasionally)f(use-)
1992 2635 y(ful)g(to)i(run)e(infrequently)e(e)o(x)o(ecuted,)j(unreserv)
o(ed)d(processes)j(at)1992 2735 y(higher)d(priority)h(than)h(the)g
(reserv)o(ed)e(processes,)j(most)f(notably)1992 2834
y(those)c(processes)f(associated)h(with)h(system)f(reco)o(v)o(ery)-5
b(.)1992 3428 y Fd(6.2)99 b(W)-7 b(orking)24 b(Set)i(Reser)o(v)o(es)
1992 3681 y Fr(The)c(capacity)f(to)i(use)f(the)h(processor)e(is)i(of)g
(little)g(bene\002t)f(if)h(the)1992 3781 y(application)15
b(is)j(not)f(in)g(memory)-5 b(.)21 b(T)-7 b(o)18 b(ensure)e(that)h
(performance-)1992 3881 y(critical)i(application)f(code)g(and)h(data)g
(remains)g(resident,)f(ER)m(OS)1992 3980 y(pro)o(vides)k
Fi(w)o(orking)i(set)h(r)o(eser)o(v)o(es)p Fr(.)37 b(A)25
b(w)o(orking)e(set)i(describes)1992 4080 y(the)j(number)f(of)h(total)g
(pages)g(and)g(nodes)g(and)g(the)g(number)f(of)1992 4180
y(dirty)32 b(pages)h(and)g(nodes)f(permitted)g(to)i(the)f(w)o(orking)f
(set)i(re-)1992 4279 y(serv)o(e.)44 b(W)-7 b(orking)26
b(sets)i(are)f(subdi)n(visible;)i(an)e(application)f(can)1992
4379 y(f)o(abricate)k(an)i(empty)e(w)o(orking)g(set)j(and)e(transfer)f
(reserv)n(ation)1992 4478 y(from)21 b(some)i(e)o(xisting)e(w)o(orking)g
(set)j(to)f(the)f(ne)n(w)h(one.)31 b(A)24 b(w)o(ork-)1992
4578 y(ing)17 b(set)h(may)f(also)h(be)f(mark)o(ed)g Fp(non-per)o
(sistent)p Fr(,)f(e)o(x)o(empting)f(an)o(y)1992 4678
y(data)20 b(in)g(it)h(from)e(the)h(checkpoint)e(mechanism.)1992
4811 y(T)-7 b(ypical)24 b(applications)g(de\002ne)h(a)g(single)g(w)o
(orking)f(set)h(for)g(their)1992 4910 y(process.)50 b(Applications)27
b(may)i(also)g(specify)f(an)h(address)f(sub-)1992 5010
y(space)f(that)h(operates)e(under)g(its)j(o)n(wn)e(w)o(orking)f(set.)47
b(This)28 b(en-)1992 5109 y(ables)20 b(protocol)g(modules)f(to)i
(declare)f(w)o(orking)f(storage)i(for)f(in-)1992 5209
y(transit)d(pack)o(ets)g(to)g(be)g(non-persistent,)f(reducing)f(the)i
(o)o(v)o(erhead)1992 5309 y(of)i(restart)h(after)f(checkpoint)f(and)h
(reducing)f(the)h(comple)o(xity)f(of)1992 5408 y(orderly)g(cleanup)h
(after)h(a)g(system)h(restart)f(has)g(occurred.)1929
5657 y(7)p eop
%%Page: 8 8
8 7 bop 0 91 a Fj(7)119 b(Mapping)31 b(to)f(Hard)n(war)n(e)0
313 y Fr(While)c(pages)f(and)f(nodes)h(are)g(an)g(ele)o(gant)f(w)o(ay)i
(of)f(specifying)0 413 y(a)d(system,)h(the)o(y)e(are)h(not)f(an)h
(especially)f(good)g(w)o(ay)h(of)g Fp(running)0 513 y
Fr(that)e(system)h(ef)n(\002ciently)-5 b(.)0 645 y(Addressing-related)
55 b(capabilities)j(translate)g(directly)f(into)0 745
y(hardw)o(are)25 b(page)h(table)h(entries;)j(the)d(associated)f(access)
h(rights)0 845 y(checks)d(are)h(implemented)f(by)g(the)h(nati)n(v)o(e)f
(hardw)o(are)g(address-)0 944 y(ing)29 b(mechanism.)52
b(The)29 b(process)g(and)g(the)h(address)f(space)g(ab-)0
1044 y(stractions,)18 b(ho)n(we)n(v)o(er)m(,)d(must)j(be)f(translated)g
(into)h(forms)f(that)g(can)0 1144 y(be)j(ef)n(\002ciently)f(used)h(by)g
(the)g(hardw)o(are.)k(This)c(is)h(accomplished)0 1243
y(by)f(tw)o(o)h(caches:)26 b(the)21 b(process)f(cache)g(and)g(the)h
(mapping)e(cache.)0 1343 y(The)33 b(management)e(of)i(these)h(caches)f
(is)h(presented)e(in)i(detail)0 1442 y(else)n(where)26
b([cite)i(POS)f(paper],)g(it)h(is)g(sk)o(etched)e(here)h(to)g(f)o
(acili-)0 1542 y(tate)21 b(understanding)c(of)j(the)g(benchmarks)e
(section.)0 1675 y(T)-7 b(o)31 b(f)o(acilitate)g(ef)n(\002cient)f
(conte)o(xt)f(switching,)k(the)d(state)i(of)e(ac-)0 1774
y(ti)n(v)o(ely)19 b(e)o(x)o(ecuting)e(processes)j(is)g(loaded)f(into)g
(a)h Fi(pr)o(ocess)f(cache)p Fr(.)0 1874 y(Each)24 b(acti)n(v)o(e)g
(entry)f(in)i(the)f(process)g(cache)g(contains)g(the)g(com-)0
1974 y(plete)e(architected)f(re)o(gister)h(set)h(of)f(some)g(process.)
31 b(The)22 b(layout)0 2073 y(of)k(a)g(process)g(cache)g(entry)f(is)i
(optimized)e(for)h(conte)o(xt)f(unload)0 2173 y(and)31
b(reload)f(rather)h(than)f(speci\002cation)h(con)m(v)o(enience.)55
b(Once)0 2273 y(loaded)25 b(into)i(the)f(process)g(cache,)i(a)f
(process)f(remains)g(cached)0 2372 y(until)33 b(forced)e(out)h(by)h(a)g
(more)f(acti)n(v)o(e)g(process.)62 b(In)33 b(practice,)0
2472 y(most)22 b(processes)f(block)g(most)h(of)g(the)f(time;)i(the)f
(process)g(cache)0 2571 y(is)f(usually)f(able)g(to)g(contain)f(the)i
(entire)e(acti)n(v)o(e)h(process)g(set.)0 2704 y(The)f
Fi(mapping)h(cache)f Fr(holds)g(hardw)o(are-speci\002c)e(mapping)h(ta-)
0 2804 y(ble)k(entries.)30 b(On)22 b(tree-structured)e(mapping)g(hardw)
o(are,)g(it)j(con-)0 2904 y(tains)k(page)f(tables.)44
b(F)o(or)26 b(hash-structured)e(mapping)h(systems,)0
3003 y(we)31 b(implement)f(a)h(lar)o(ge)f(second)h(le)n(v)o(el)f
(translation)g(b)n(uf)n(fer)g(in)0 3103 y(softw)o(are)20
b(and)f(f)o(all)i(back)e(to)i(w)o(alking)e(the)h(address)g(space)g
(tree.)0 3236 y(Hardw)o(are-speci\002c)i(mapping)f(structures)i(are)h
(constructed)d(by)0 3335 y(tra)n(v)o(ersing)15 b(the)i(address)f(space)
g(structure)g(and)f(updating)g(the)h(ap-)0 3435 y(propriate)h(entry)h
(or)g(entries)h(in)g(the)f(mapping)f(cache.)24 b(T)-7
b(o)19 b(ensure)0 3535 y(that)30 b(the)g(mapping)e(entries)i(are)g
(properly)d(updated)i(when)g(the)0 3634 y(address)22
b(space)g(node)f(slots)i(are)f(altered,)f(a)i Fi(dependency)f(table)0
3734 y Fr(is)29 b(used)f(to)g(k)o(eep)g(track)f(of)h(the)g(projection)e
(from)h(the)h(abstract)0 3833 y(address)20 b(space)g(to)g(the)g(hardw)o
(are)f(mapping)g(tables.)0 4163 y Fj(8)119 b(Pr)n(oposed)30
b(Ev)o(aluation)g(Method)0 4385 y Fr(In)20 b(the)g(absence)f(of)h(a)g
(substantial)g(nati)n(v)o(e)f(application)f(base,)i(re-)0
4484 y(search)33 b(microk)o(ernels)e(ha)n(v)o(e)h(been)g(e)n(v)n
(aluated)g(by)g(comparing)0 4584 y(the)h(performance)d(of)i(a)h(f)o
(amiliar)g(en)m(vironment)c(\(such)j(as)i(U-)0 4684 y(NIX\))20
b(to)g(its)h(rehosted)e(equi)n(v)n(alent)g(on)h(top)f(of)h(the)g
(microk)o(ernel.)0 4783 y(This)k(is)g(an)f(inappropriate)e(e)n(v)n
(aluation)g(method)h(for)h(ER)m(OS)h(for)0 4883 y(se)n(v)o(eral)c
(reasons:)83 5109 y Fo(\017)41 b Fr(ER)m(OS)26 b(is)h(designed)e(to)h
(support)f(mission-critical)g(appli-)166 5209 y(cations)20
b(that)g(demand)e(high)h(a)n(v)n(ailability)-5 b(,)19
b(hands-of)n(f)f(24/7)166 5309 y(operation,)25 b(v)o(ery)g(lar)o(ge)f
(stores)i(and/or)f(strong)f(f)o(ault)i(con-)166 5408
y(tainment.)59 b(These)32 b(are)g(applications)e(for)i(which)f(UNIX)
2158 91 y(and)19 b(similar)i(systems)f(are)g(inappropriate.)2075
249 y Fo(\017)41 b Fr(ER)m(OS)18 b(is)h(designed)e(for)h(applications)f
(that)h(place)g(the)g(sys-)2158 349 y(tem)f(under)f(high)h(stress,)i
(such)e(as)h(online)e(transaction)h(pro-)2158 448 y(cessing.)49
b(Man)o(y)28 b(of)g(the)h(simplifying)e(assumptions)g(that)2158
548 y(are)d(essential)h(to)g(making)e(UNIX)h(f)o(ast)i(\(e.g.)37
b(statistically)2158 648 y(justi\002ed)30 b(o)o(v)o(ercommitment)d(of)k
(sw)o(ap)g(space\))f(are)g(inap-)2158 747 y(propriate)18
b(for)i(such)g(an)g(en)m(vironment.)2075 905 y Fo(\017)41
b Fr(Operating)23 b(systems)j(are)f(usually)g(rehosted)f(for)g(the)h
(sak)o(e)2158 1005 y(of)k(le)o(gac)o(y)g(application)g(support.)53
b(A)30 b(nominal)f(\(10\045)h(or)2158 1104 y(less\))k(de)o(gradation)e
(of)i(performance)d(is)k(acceptable)e(for)2158 1204 y(such)19
b(applications.)2075 1362 y Fo(\017)41 b Fr(Benchmarking)29
b(rehosted)h(en)m(vironments)f(does)i(not)g(e)o(x-)2158
1461 y(pose)g(an)o(y)g(of)h(the)g(adv)n(antages)e(of)i(the)g(ne)n(w)f
(system.)61 b(If)2158 1561 y(what)29 b(you)f(w)o(ant)h(to)h(do)e(is)j
(run)d(UNIX,)h(you)f(should)g(run)2158 1661 y(UNIX.)1992
1856 y(Equally)19 b(important,)g(both)h(our)g(o)n(wn)g(past)i(e)o
(xperience)c(and)i(that)1992 1956 y(of)30 b(others)g(suggests)g(that)h
(this)g(e)n(v)n(aluation)e(strate)o(gy)h(does)g(not)1992
2055 y(lend)24 b(itself)i(to)g(a)f(correct)g(understanding)d(of)j(the)g
(performance)1992 2155 y(of)19 b(the)i(respecti)n(v)o(e)e(systems)h
([Che93)o(,)g(Bom92)o(].)3421 2125 y Fq(8)1992 2422 y
Fd(8.1)99 b(Issues)24 b(in)h(Comparison)1992 2611 y Fr(Three)19
b(dif)n(ferences)f(in)i(semantics)g(between)f(UNIX)h(and)f(ER)m(OS)1992
2711 y(mak)o(e)31 b(direct)h(comparisons)e(of)i(certain)g(operations)e
(dif)n(\002cult:)1992 2810 y(accountability)-5 b(,)24
b(persistence,)j(and)e(the)h(absence)f(of)h(the)g Fp(fork)q
Fr(\(\))1992 2910 y(primiti)n(v)o(e.)c(Neither)17 b(of)h(these)g
(features)f(has)g(a)h(direct)g(equi)n(v)n(alen-)1992
3009 y(t)27 b(in)g(con)m(v)o(entional)d(systems,)30 b(and)c(each)h(has)
g(associated)g(costs)1992 3109 y(and)19 b(bene\002ts.)1992
3263 y Fi(Accountability)90 b Fr(The)32 b(ER)m(OS)h(architecture)d
(requires)i(\(as)g(a)1992 3362 y(matter)27 b(of)g(polic)o(y\))g(that)h
(all)g(storage)f(be)h(pro)o(vided)d(by)i(the)h(ap-)1992
3462 y(plication,)c(and)g(that)h(e)n(v)o(ery)e(piece)h(of)g
(application-pro)o(vided)c(s-)1992 3562 y(torage)27 b(ha)n(v)o(e)g
(real)i(backing)d(store.)49 b(This)29 b(adds)f(to)g(the)g(cost)h(of)
1992 3661 y(demand-zero)24 b(memory)h(re)o(gions,)j(as)g(the)f
(metadata)g(and)f(con-)1992 3761 y(tent)37 b(structures)g(\(nodes)f
(and)h(pages)g(respecti)n(v)o(ely\))e(must)j(be)1992
3861 y(e)o(xplicitly)26 b(purchased)f(by)i(some)g(user)g(le)n(v)o(el)g
(application.)45 b(No)1992 3960 y(analogous)20 b(accountability)g(is)k
(applied)d(by)h(UNIX)h(and)e(similar)1992 4060 y(systems,)34
b(since)e(the)g(analogous)e(storage)h(is)h(f)o(abricated)f(from)1992
4159 y(a)37 b(statistically)h(o)o(v)o(ercommitted)c(resource)i(\(the)h
(sw)o(ap)g(area\).)1992 4259 y(T)m(ransparent)29 b(persistence)h(of)h
(an)g(o)o(v)o(ercommitted)d(sw)o(ap)k(area)1992 4359
y(cannot)19 b(be)h(reco)o(v)o(ered)d(by)j(restarting.)1992
4512 y Fi(P)n(ersistence)90 b Fr(By)31 b(design,)h(ER)m(OS)f(has)g(no)f
(analogue)f(to)i(the)1992 4612 y(UNIX)26 b Fp(sync)g
Fr(operation.)41 b(Under)26 b(normal)f(circumstances,)h(ap-)1992
4712 y(plications)c(b)n(uild)g(structures)g(in)g(memory)f(and)h(rely)h
(on)f(the)g(un-)1992 4811 y(derlying)15 b(checkpoint)g(mechanism)i(to)g
(render)f(them)h(persistent.)p 1992 4856 764 4 v 2082
4912 a Fh(8)2111 4935 y Fg(The)29 b(conclusions)i(of)e(Bershad)h(and)f
(Chen)h(in)f([Che93)r(])g(are)g(mistak)o(en.)1992 5014
y(Simply)15 b(re)n(v)o(ersing)i(the)e(order)h(of)f(user)g(and)g
(supervisor)h(memory)f(delays)h(in)f(Fig-)1992 5093 y(ure)j(2-1)f(mak)o
(es)i(it)f(apparent)i(that)f(the)f(operating)i(system)e(structure)i
(had)e(essen-)1992 5172 y(tially)23 b Fa(no)e Fg(ef)n(fect)i(on)e
(application)k(beha)o(vior)l(.)35 b(The)21 b(graph)h(actually)i(re)n(v)
o(eals)f(the)1992 5251 y(poor)17 b(design)i(and)f(architecture)j(of)d
(Mach)g(3.0)f(and)h(the)g(inef)n(\002cienc)o(y)j(of)d(its)g(IPC)1992
5329 y(mechanism,)g(and)g(strongly)h(suggests)f(that)g(a)g(better)h
(microk)o(ernel)i(architecture)1992 5408 y(should)c(e)o(xceed)i(the)f
(performance)h(of)e(the)h(nati)n(v)o(e)h(UNIX)e(system.)1929
5657 y Fr(8)p eop
%%Page: 9 9
9 8 bop 0 91 a Fr(A)23 b(separate,)g(\002ne-grain)e(mechanism)h(e)o
(xists)h(for)f(use)h(by)f(trans-)0 191 y(actioned)d(f)o(acilities.)0
324 y(The)f(o)o(v)o(erhead)e(associated)j(with)g(\002le)g(system)g
(metadata)f(is)i(sub-)0 423 y(stantial)34 b(and)g(well)g(e)o(xplored)e
([Gan94)n(,)i(Sel95)o(].)66 b(Ultimately)-5 b(,)0 523
y(this)26 b(o)o(v)o(erhead)c(deri)n(v)o(es)j(from)f(the)h(f)o(act)g
(the)h(runtime)e(state)i(\(in-)0 623 y(cluding)19 b(that)h(of)f(the)i
(\002le)f(system)g(implementation\))e(is)j(not)e(per)n(-)0
722 y(sistent,)25 b(and)e(therefore)f(cannot)g(be)i(relied)f(on)g(to)h
(resume)f(from)0 822 y(a)k(consistent)f(state.)44 b(The)26
b(use)g(of)g(a)h(transparent)e(system-wide)0 922 y(checkpoint)d
(operation)g(remo)o(v)o(es)g(this)i(impediment,)f(which)g(e-)0
1021 y(liminates)c(the)h(need)e(for)h(transactioned)e(metadata)i
(update.)24 b(Ex-)0 1121 y(plicit)k(metadata)e(management)g(is)i(rele)o
(gated)e(to)h(those)g(e)o(xcep-)0 1220 y(tional)34 b(applications)f
(such)g(as)i(databases)f(that)g(ha)n(v)o(e)f(unusual)0
1320 y(promptness)19 b(requirements.)0 1453 y(Since)k(this)g
(re\003ects)g(the)f(normal)g(beha)n(vior)f(of)h(the)h(system)f(\(i.e.)0
1553 y(what)k(the)f(user)h(will)g(actually)f(see\),)i(we)f(vie)n(w)g
(it)g(as)h(a)f(realistic)0 1652 y(\(albeit)18 b(unf)o(air\))g
(comparison.)k(The)c(reliability)h(tradeof)n(fs)e(inher)n(-)0
1752 y(ent)j(in)h(this)f(polic)o(y)f(are)h(discussed)g(in)h(Section)f
Fi(??)o Fr(.)0 1910 y Fi(f)n(ork)86 b Fr(UNIX)27 b(systems)g(place)g
(hea)n(vy)f(reliance)g(on)g(the)h Fp(fork)q Fr(\(\))0
2010 y(primiti)n(v)o(e,)20 b(which)h(has)h(no)f(analogous)e(operation)h
(in)i(ER)m(OS.)f(In)0 2110 y(benchmarks,)15 b(and)i(also)h(in)f(real)g
(systems,)h(the)g Fp(fork)h Fr(call)e(is)i(near)n(-)0
2209 y(ly)26 b(al)o(w)o(ays)g(follo)n(wed)e(immediately)g(by)h
Fp(e)n(xec)p Fr(.)41 b(The)25 b(end)g(result)0 2309 y(is)20
b(the)f(creation)g(of)g(a)g(ne)n(w)h(process)e(with)i(a)f(ne)n(w)h
(address)e(space.)0 2408 y(The)26 b(metric)g(of)g(interest,)i(then,)f
(is)h(the)e Fp(cr)m(eate)h(pr)l(ocess)f Fr(opera-)0 2508
y(tion.)f(This)20 b(is)h(the)f(one)g(that)g(should)f(be)i(benchmark)o
(ed.)0 2782 y Fd(8.2)99 b(Benchmarks)0 2972 y Fr(The)34
b(performance)d(of)j(applications)f(is)j(dependent)c(on)i(three)0
3071 y(f)o(actors:)84 b(memory)48 b(speed)h(and)g(con\002guration,)54
b(processor)0 3171 y(speed,)18 b(and)h(a)g(weighted)f(measure)g(of)g
(the)h(performance)d(of)i(cer)n(-)0 3271 y(tain)i(critical)h(services:)
62 3472 y(1.)41 b(Address)20 b(space)g(mapping)e(management,)62
3641 y(2.)41 b(P)o(age)20 b(f)o(ault)g(handling,)62 3810
y(3.)41 b(Reading)36 b(and)f(writing)h(data)g(to)g(the)h(store)f
(\(\002le)g(opera-)166 3909 y(tions\),)20 b(and)62 4078
y(4.)41 b(Interprocess)19 b(communication)e(performance,)0
4279 y(Processor)23 b(speed)h(and)f(memory)f(subsystem)i(are)g
(independent)0 4379 y(of)32 b(the)g(choice)g(of)g(operating)e(system.)
62 b(Critical)33 b(service)f(op-)0 4478 y(erations)c(can)g(be)g
(compared)e(directly)h(by)h(microbenchmarks.)0 4578 y(The)18
b(lmbench)f(benchmark)f(suite)j(does)g(a)g(reasonably)d(ef)n(fecti)n(v)
o(e)0 4678 y(job)j(of)f(measuring)g(such)h(lo)n(w-le)n(v)o(el)e
(operations)h([McV93)n(].)25 b(W)-7 b(e)0 4777 y(therefore)23
b(propose)g(to)i(adapt)f(the)h(lmbench)e(microbenchmark)0
4877 y(suite)e(to)f(the)g(ER)m(OS)h(platform)d(for)i(measurement)e
(purposes.)0 5010 y(F)o(or)29 b(each)g(benchmark,)g(we)h(propose)e(to)i
(measure)e(both)h(CPU)0 5109 y(c)o(ycles)21 b(and)f(cache)h(misses)h
(in)f(the)g(instruction,)e(data,)i(and)g(TLB)0 5209 y(caches.)59
b(The)31 b(latter)g(measurements)f(e)o(xpose)h(deferred)e(post-)0
5309 y(service)34 b(o)o(v)o(erheads)f(that)i(w)o(ould)f(not)g
(otherwise)g(be)h(demon-)0 5408 y(strated)20 b(by)g(a)g
(microbenchmark.)1992 91 y Fj(9)119 b(Related)30 b(W)-9
b(ork)1992 342 y Fp(This)20 b(section)g(needs)g(to)g(be)h(e)n(xpanded.)
1992 474 y Fr(Most)26 b(of)f(the)h(early)f(hardw)o(are)g(protection)f
(mechanisms)h(were)1992 574 y(capability)c(based)i([cite)f(Plesse)o(y)
-5 b(,)24 b(Sigma-7,)e(C.mmp,)g(B5700],)1992 674 y(b)n(ut)43
b(these)i(systems)f(f)o(ailed)g(to)g(deli)n(v)o(er)e(acceptable)h
(perfor)n(-)1992 773 y(mance.)28 b(The)22 b(dramatic)f(and)g(highly)g
(publicized)f(f)o(ailure)h(of)h(the)1992 873 y(Intel)33
b(i432)g(led)g(mainstream)g(computer)f(architects)h(to)h(aban-)1992
972 y(don)19 b(\002ne)h(grain)g(capability)f(architectures.)24
b(The)c(Intel/Siemens)1992 1072 y(BiiN)25 b(architecture)d(\(better)h
(kno)n(wn)g(as)i(the)f(i960\))e(demonstrat-)1992 1172
y(ed)f(that)g(hardw)o(are-based)d(capability)j(systems)g(could)g(be)g
(high-)1992 1271 y(performance,)30 b(b)n(ut)i(went)f(undeplo)o(yed)d
(due)j(to)g(a)h(contractual)1992 1371 y(breakdo)n(wn)25
b(between)i(the)h(principals.)47 b(The)28 b(IBM)g(AS/400)g(is)1992
1471 y(the)20 b(only)f(widely)h(deplo)o(yed)e(capability)h(system)i(in)
f(use)g(today)-5 b(.)1992 1899 y Fd(9.1)99 b(K)n(eyK)m(OS)1992
2119 y Fr(K)n(e)o(yK)n(OS)28 b(is)j(an)e(earlier)g(capability)f(system)
i(from)f(which)g(the)1992 2219 y(ER)m(OS)k(architecture)f(is)i(deri)n
(v)o(ed)e([Har85)n(].)64 b(Originally)32 b(con-)1992
2318 y(structed)17 b(for)h(the)h(IBM)g(370,)e(and)h(later)h(ported)e
(to)i(the)f(Motorola)1992 2418 y(88000)24 b(f)o(amily)-5
b(,)27 b(K)n(e)o(yK)n(OS)f(deli)n(v)o(ered)f(performance)f(rougly)g(e-)
1992 2518 y(qui)n(v)n(alent)17 b(to)i(that)h(of)f(Mach)g(2.5)f([Bom92)n
(].)25 b(In)19 b(addition)f(to)h(for)n(-)1992 2617 y(mal)32
b(underpinnings)d(described)i(else)n(where)h([Sha97)o(],)j(ER)m(OS)1992
2717 y(brings)25 b(the)i(performance)c(of)j(the)h(architecture)e(into)h
(line)g(with)1992 2816 y(that)20 b(of)g(more)f(aggressi)n(v)o(e)g
(systems)i(such)f(as)g(L4.)1992 3244 y Fd(9.2)99 b(Mach)25
b(4.0)1992 3465 y Fr(Bryan)19 b(F)o(ord)f(has)i(gi)n(v)o(en)f
(considerable)o(y)e(attention)i(to)g(the)h(prob-)1992
3564 y(lem)26 b(of)h(IPC)h(performance)c(in)j(Mach,)g(and)g(has)g(sho)n
(wn)f(that)h(it)1992 3664 y(can)33 b(be)g(substantially)g(impro)o(v)o
(ed)e(MA)m(CH4:Migrating.)63 b(F)o(or)1992 3764 y(dek)o(ernelized)33
b(systems,)39 b(including)34 b(ER)m(OS,)h(IPC)h(operations)1992
3863 y(are)26 b(a)h(performance)d(critical)j(benchmark.)42
b(V)-9 b(arious)26 b(elements)1992 3963 y(of)k(the)g(Mach)g(messaging)f
(semantics)i(restrict)f(the)g(realizable)1992 4063 y(performance.)1992
4491 y Fd(9.3)99 b(L3)25 b(and)g(L4)1992 4711 y Fr(L3)f
(L3:IPC,L3:SpaceMux,)g(and)g(later)i(L4,)g(ha)n(v)o(e)e(established)
1992 4811 y(ne)n(w)17 b(standards)f(for)h(interprocess)f(communication)
e(times.)25 b(The)1992 4910 y(w)o(ork)d(already)g(done)g(on)g(ER)m(OS)h
(has)h(demonstrated)c(that)j(these)1992 5010 y(times)c(can)g(be)g
(matched)e(in)i(the)g(ER)m(OS)h(conte)o(xt)d([Sha96d)n(].)25
b(The)1992 5109 y(principle)f(insight)h(to)h(dra)o(w)e(from)h(this)h(w)
o(ork,)g(in)g(our)f(opinion,)1992 5209 y(is)g(that)f(conte)o(xt)f
(switch)i(and)e(e)o(xception)g(handling)f(ha)n(v)o(e)i(much)1992
5309 y(more)30 b(to)h(do)g(with)h(the)f(hardw)o(are)f(architcture)f
(than)i(with)h(the)1992 5408 y(speci\002cs)20 b(of)g(an)o(y)f
(particular)g(operating)g(system)h(architecture.)1929
5657 y(9)p eop
%%Page: 10 10
10 9 bop 0 91 a Fj(10)119 b(Conclusions)0 310 y Fr(While)16
b(there)g(are)f(man)o(y)g(w)o(ays)h(to)g(construct)e(capability)h
(system-)0 410 y(s,)22 b(v)o(ery)e(fe)n(w)h(are)g(lik)o(ely)g(to)h(be)f
(ef)n(\002cient.)27 b(ER)m(OS)22 b(achie)n(v)o(es)e(high)0
509 y(performance)f(by)j(use)h(of)f(a)h(design)f(methodology)d
(comprising)0 609 y(the)h(steps)h(of:)62 787 y(1.)41
b(Identify)31 b(minimal)g(sets)i(of)f(primiti)n(v)o(e)f(memory)f
(objects)166 887 y(and)17 b(operations,)f(which)h(are)h(required)e(to)h
(pro)o(vide)f(system)166 987 y(semantics)i(and)f(cannot)f(be)i
(constructed)e(from)g(e)n(v)o(en)h(more)166 1086 y(primiti)n(v)o(e)i
(objects)h(ans)g(services.)62 1242 y(2.)41 b(Examine)27
b(these)i(sets)g(in)f(light)h(of)f(architectural)e(support)166
1341 y(and)41 b(microbenchmarks)e(to)j(select)g(an)g(ef)n(\002cient)g
Fp(basis)166 1441 y Fr(from)19 b(which)h(the)g(capability)f(system)i
(can)f(constructed.)62 1597 y(3.)41 b(Use)29 b(the)e(hardw)o(are)g
(performance)e(\(e.g.,)k(for)e(TLB)h(table)166 1696 y(updates)e(or)g
(disk)h(throughput\))c(as)k(the)g(design)f(tar)o(get)g(for)166
1796 y(performance)17 b(of)j(each)g(of)g(the)g(primiti)n(v)o(es.)0
1974 y(The)j(critical)h(path)g(operations)e(of)h(the)h(ER)m(OS)h
(system)f(meet)f(or)0 2074 y(substantially)h(e)o(xceed)f(the)i
(performance)d(of)i(all)h(other)f(curren-)0 2173 y(t)i(operating)d
(systems.)41 b(Substantial)25 b(further)e(impro)o(v)o(ement)f(on)0
2273 y(the)d(critical)g(paths)g(is)g(possible)g(only)f(by)h(changes)f
(to)h(the)f(under)n(-)0 2373 y(lying)g(hardw)o(are;)g(the)g(tw)o(o)h
(most)f(important)f(changes)h(are)g(a)h(f)o(ast)0 2472
y(pri)n(vile)o(ge)27 b(boundary)e(crossing)i(mechanism)g(and)h(a)g
(tagged)f(or)0 2572 y(softw)o(are-managed)17 b(TLB)k(architecture.)0
2705 y(The)d(k)o(e)o(y)f(point)g(to)h(tak)o(e)g(a)o(w)o(ay)f(from)g
(this)i(paper)d(is)j(that)f(capabil-)0 2804 y(ity)25
b(systems)g(are)f Fp(not)i Fr(slo)n(wer)e(than)g(\223con)m(v)o
(entional\224)d(operating)0 2904 y(systems.)58 b(ER)m(OS)32
b(pro)o(vides)d(a)j(clear)f(e)o(xistence)f(proof,)i(oper)n(-)0
3004 y(ating)g(at)g(or)g(near)g(the)g(performance)d(limits)k(imposed)e
(by)h(the)0 3103 y(underlying)g(hardw)o(are.)67 b(The)34
b(performance)e(presented)i(here)0 3203 y(is)28 b(achie)n(v)o(ed)d(by)h
(an)h(implementation)e(constructed)g(in)i(a)g(high-)0
3303 y(le)n(v)o(el,)h(portable,)f(optimization-challenged)c(source)j
(language)0 3402 y(\(C++\),)35 b(augmented)c(by)h(less)h(than)f(1500)f
(lines)i(of)f(assembly)0 3502 y(code,)26 b(which)f(including)e(dri)n(v)
o(ers,)i(compiles)g(to)h(less)g(than)f(160)0 3601 y(kilobytes)19
b(of)h(code.)0 3734 y(Further)147 b(information)f(on)j(the)f(ER)m(OS)h
(sys-)0 3834 y(tem)103 b(can)g(be)g(found)f(via)h(our)f(web)h(page)g
(at)0 3933 y Fn(http://www.cis.upenn.edu/\230eros)p Fr(.)0
4242 y Fj(Refer)n(ences)0 4456 y Fr([Bom92])85 b(Allen)25
b(C.)h(Bomber)o(ger)m(,)d(A.)i(Peri)g(Frantz,)h(W)m(illiam)387
4555 y(S.)46 b(Frantz,)k(Ann)44 b(C.)i(Hardy)-5 b(,)49
b(Norman)44 b(Hardy)-5 b(,)387 4655 y(Charles)54 b(R.)h(Landau,)61
b(Jonathan)52 b(S.)i(Shapiro.)387 4755 y(\223The)61 b(K)n(e)o(yK)n(OS)g
(NanoK)n(ernel)f(Architecture,)-6 b(\224)387 4854 y Fp(Pr)l(oceedings)
48 b(of)h(the)f(USENIX)g(W)-8 b(orkshop)48 b(on)387 4954
y(Micr)l(o-K)m(ernels)h(and)e(Other)h(K)m(ernel)g(Ar)m(c)o(hitec-)387
5053 y(tur)m(es)p Fr(.)35 b(USENIX)g(Association.)e(April)i(1992.)d(pp)
387 5153 y(95-112.)0 5309 y([Che93])113 b(J.)27 b(Bradle)o(y)f(Chen)g
(and)f(Brian)h(N.)h(Bershad.)f(\223The)387 5408 y(Impact)50
b(of)h(Operating)f(System)h(Structure)e(on)2379 91 y(Memory)g(System)h
(Performance\224)e Fp(Pr)l(oc.)i(14th)2379 191 y(SOSP)p
Fr(,)19 b(December)g(1993.)1992 375 y([Col88])127 b(Robert)33
b(P)-9 b(.)34 b(Col)o(well,)j(Edw)o(ard)c(F)-7 b(.)34
b(Gehringer)m(,)h(E.)2379 475 y(Douglas)23 b(Jensen,)j(\223Performance)
21 b(Ef)n(fects)j(of)g(Ar)n(-)2379 575 y(chitectural)17
b(Comple)o(xity)g(in)h(the)g(Intel)g(432.)-6 b(\224)17
b Fp(A)n(CM)2379 674 y(T)-5 b(r)o(ansactions)20 b(on)g(Computer)h
(Systems)p Fr(,)f Fi(6)p Fr(\(3\),)g(Au-)2379 774 y(gust)g(1988,)f(pp.)
g(296\226339.)1992 958 y([Den66])108 b(J.)27 b(B.)g(Dennis)g(and)f(E.)g
(C.)h(V)-9 b(an)27 b(Horn,)g(\223Program-)2379 1058 y(ming)g(Semantics)
h(for)f(Multiprogrammed)e(Com-)2379 1158 y(putations\224)37
b(in)h Fp(Communications)e(of)i(the)g(A)n(CM)p Fr(,)2379
1257 y(v)n(ol.)20 b(9,)g(pp.)f(143\226154,)e(March)j(1966.)1992
1442 y([F)o(or94])132 b(Bryan)17 b(F)o(ord)g(and)g(Jay)h(Lepreau,)f
(\223Ev)n(olving)f(Mach)2379 1541 y(3.0)47 b(to)i(a)f(Migrating)f
(Threads)g(Model,)-6 b(\224)55 b Fp(Pr)l(o-)2379 1641
y(ceedings)30 b(of)h(the)g(W)-5 b(inter)31 b(USENIX)g(Confer)m(ence)p
Fr(,)2379 1741 y(January)19 b(1994.)2379 1840 y Fn
(ftp://mancos.cs.utah.edu/papers/)p 3979 1853 42 66 v
2379 1940 a(thread-migrate.ps.Z)1992 2124 y Fr([Gan94])108
b(Gre)o(gory)25 b(R.)i(Ganger)f(and)h(Y)-8 b(ale)27 b(N.)g(P)o(att.)g
(\223Meta-)2379 2224 y(data)d(Update)f(Performance)f(in)i(File)g
(Systems\224)g(in)2379 2324 y Fp(Pr)l(oceedings)38 b(of)g(the)h(USENIX)
f(Symposium)g(on)2379 2423 y(Oper)o(ating)33 b(Systems)h(Design)g(and)f
(Implementa-)2379 2523 y(tion)p Fr(,)20 b(No)o(v)-5 b(.)18
b(1994,)h(pp.)h(49-60.)1992 2707 y([Har85])122 b(Norman)25
b(Hardy)-5 b(.)26 b(\223The)g(K)n(e)o(yK)n(OS)g(Architecture\224)2379
2807 y Fp(Oper)o(ating)i(Systems)h(Re)o(vie)o(w)p Fr(.)g(Oct.)g(1985,)h
(pp)f(8-)2379 2907 y(25.)1992 3091 y([K)n(e)o(y86])111
b(K)n(e)o(y)22 b(Logic,)h(Inc.)f Fp(U)n(.S.)h(P)-7 b(atent)22
b(4,584,639:)28 b(Com-)2379 3191 y(puter)20 b(Security)g(System)p
Fr(.)1992 3375 y([Kit93])141 b(T)-7 b(akuro)30 b(Kitayama,)j(T)-7
b(atsuo)31 b(Nakajima,)i(Hiroshi)2379 3475 y(Araka)o(w)o(a,)h(and)e
(Hide)o(yuki)f(T)-7 b(okuda.)31 b(\223Inte)o(grated)2379
3574 y(Management)40 b(of)h(Priority)g(In)m(v)o(ersion)e(in)j(Real-)
2379 3674 y(T)m(ime)31 b(Mach.)-6 b(\224)30 b Fp(IEEE)h(Real-T)-5
b(ime)31 b(Systems)g(Sym-)2379 3774 y(posium)p Fr(.)19
b(December)g(1993)1992 3958 y([Lam73])94 b(Butler)23
b(W)-8 b(.)24 b(Lampson.)e(\223)-7 b(A)24 b(Note)f(on)f(the)h
(Con\002ne-)2379 4058 y(ment)g(Problem.)-6 b(\224)22
b Fp(Communications)g(of)i(the)f(A)n(CM)2379 4157 y Fr(V)-11
b(ol)20 b(16,)g(No)g(10,)g(1973)1992 4342 y([Lam76])94
b(Butler)33 b(W)-8 b(.)34 b(Lampson)e(and)h(Ho)n(w)o(ard)f(E.)h(Stur)o
(gis.)2379 4442 y(\223Re\003ections)16 b(on)h(an)f(Operating)f(System)i
(Design.)-6 b(\224)2379 4541 y Fp(Communications)31 b(of)i(the)g(A)n
(CM)h Fr(V)-11 b(ol)33 b(19,)j(No)d(5,)2379 4641 y(May)20
b(1976.)1992 4825 y([Lan92])117 b(Charles)31 b(R.)g(Landau.)e(\223The)h
(Checkpoint)f(Mech-)2379 4925 y(anism)h(in)h(K)n(e)o(yK)n(OS,)-6
b(\224)30 b Fp(Pr)l(oceedings)g(of)g(the)h(Sec-)2379
5025 y(ond)19 b(International)f(W)-8 b(orkshop)20 b(on)g(Object)g
(Orien-)2379 5124 y(tation)15 b(in)i(Oper)o(ating)d(Systems)p
Fr(.)j(IEEE.)e(September)2379 5224 y(1992.)j(pp)i(86-91.)1992
5408 y([Les96])127 b Fp(Need)20 b(citation)g(her)m(e)1908
5657 y Fr(10)p eop
%%Page: 11 11
11 10 bop 0 91 a Fr([Lie93])136 b(Jochen)53 b(Liedtk)o(e.)g(\223Impro)o
(ving)d(IPC)k(by)f(K)n(er)n(-)387 191 y(nel)39 b(Design.)-6
b(\224)38 b Fp(Pr)l(oceedings)g(of)g(the)h(14th)f(A)n(CM)387
291 y(Symposium)30 b(on)h(Oper)o(ating)f(System)h(Principles)p
Fr(,)387 390 y(A)m(CM)21 b(1993.)0 548 y([Lie95])136
b(Jochen)70 b(Liedtk)o(e.)g Fp(Impr)l(o)o(ved)f(Addr)m(ess-Space)387
647 y(Switc)o(hing)35 b(on)h(P)-7 b(entium)36 b(Pr)l(ocessor)o(s)h(by)f
(T)-5 b(r)o(ans-)387 747 y(par)m(ently)36 b(Multiple)n(xing)g(User)h
(Addr)m(ess)f(Spaces)p Fr(,)387 846 y(GMD)21 b(TR)g(933,)e(No)o(v)o
(ember)e(1995.)0 1004 y([Le)n(v84])119 b(Henry)29 b(M.)h(Le)n(vy)-5
b(.)29 b Fp(Capability-Based)e(Computer)387 1103 y(Systems)p
Fr(.)21 b(Digital)f(Press.)h(1984.)0 1261 y([L)-5 b(yc78])122
b(H.)33 b(L)-5 b(ycklama)31 b(and)h(D.)h(L.)f(Bayer)m(,)j(\223The)d
(MER)-5 b(T)387 1360 y(Operating)49 b(System,)-6 b(\224)57
b Fp(Bell)51 b(System)f(T)-8 b(ec)o(hnical)387 1460 y(J)n(ournal)p
Fr(,)42 b Fi(57)p Fr(\(6,)g(part)c(2\),)k(pp.)c(2049\2262086,)h(Ju-)387
1560 y(ly/August)20 b(1978.)0 1717 y([McV93])76 b(Larry)54
b(McV)-11 b(o)o(y)-5 b(,)63 b(and)54 b(C.)i(Staelin.)f(\223lmbench:)387
1816 y(Portable)25 b(T)-7 b(ools)26 b(for)f(Performance)e(Analysus\224)
i(in)387 1916 y Fp(Pr)l(oceedings)33 b(of)i(the)f(1196)e(USENIX)i(T)-8
b(ec)o(hnical)387 2016 y(Confer)m(ence)p Fr(.)19 b(San)h(Die)o(go,)g
(CA,)g(January)f(1996,)f(p-)387 2115 y(p.)i(279-295.)0
2273 y([Mer93])108 b(C.)19 b(W)-8 b(.)18 b(Mercer)m(,)f(S.)h(Sa)n(v)n
(age)f(and)g(H.)h(T)-7 b(okuda.)16 b(\223Pro-)387 2372
y(cessor)45 b(Capacity)f(Reserv)o(es:)73 b(An)44 b(Abstraction)387
2472 y(for)25 b(Managing)f(Processor)g(Usage,)-6 b(\224)27
b(in)e Fp(Pr)l(oc.)g(4th)387 2572 y(W)-8 b(orkshop)21
b(on)g(W)-8 b(orkstation)21 b(Oper)o(ating)f(Systems)p
Fr(,)387 2671 y(October)g(1993.)0 2828 y([Or)o(g73])118
b(\223Computer)83 b(System)i(Or)o(ganization:)150 b(The)387
2928 y(B5700/B6700)18 b(Series,)-6 b(\224)20 b(Academic)e(Press,)j
(1973.)0 3085 y([Sal75])141 b(Jerome)23 b(H.)h(Saltzer)g(and)f(Michael)
g(D.)h(Schroeder)-5 b(.)387 3185 y(\223The)30 b(Protection)e(of)i
(Information)d(in)i(Computer)387 3285 y(Systems,)-6 b(\224)26
b(in)e Fp(Pr)l(oceedings)f(of)h(the)h(IEEE)p Fr(,)e Fi(63)p
Fr(\(9\),)387 3384 y(Sept.)e(1975,)d(pp.)i(1278\2261308.)0
3542 y([Sel95])141 b(M.)45 b(Seltzer)m(,)k(K.)c(Smith,)50
b(H.)44 b(Balakrishnan,)k(J.)387 3641 y(Chang,)42 b(S.)d(McMains,)j
(and)c(V)-11 b(.)38 b(P)o(admanabhan,)387 3741 y(\223File)d(System)e
(Logging)f(v)o(ersus)h(Clustering:)52 b(A)387 3840 y(Performance)c
(Comparison\224,)55 b Fp(Pr)l(oceedings)48 b(of)387 3940
y(the)22 b(1995)e(USENIX)h(T)-8 b(ec)o(hnical)20 b(Confer)m(ence)p
Fr(,)h(Jan-)387 4040 y(uary)f(1995,)e(Ne)n(w)j(Orleans,)e(LA,)i(pp.)e
(249\226264.)0 4197 y([Sel95])141 b(Mar)o(go)38 b(Seltzer)m(,)44
b(Y)-8 b(asuhiro)38 b(Endo,)k(Christopher)387 4297 y(Small,)34
b(K)n(eith)d(Smith,)i(\223Dealing)d(with)h(Disaster:)387
4396 y(Survi)n(ving)24 b(Misbeha)n(v)o(ed)f(K)n(ernel)i(Extensions\224)
f(in)387 4496 y Fp(Pr)l(oceedings)19 b(of)g(the)h(1996)e(Symposium)g
(on)h(Oper)n(-)387 4596 y(ating)h(System)g(Design)g(and)f
(Implementation)p Fr(.)0 4753 y([Tho78])112 b(K.)27 b(Thompson,)d
(\223UNIX)i(Implementation,)-6 b(\224)25 b Fp(Bell)387
4852 y(System)32 b(T)-8 b(ec)o(hnical)30 b(J)n(ournal)p
Fr(,)j Fi(57)p Fr(\(6,)f(part)f(2\),)j(pp.)387 4952 y(1931\2261946,)16
b(July/August)k(1978.)0 5109 y([Sha96a])85 b(Jonathan)30
b(S.)i(Shapiro.)e Fp(A)i(Pr)l(o)o(gr)o(ammer')m(s)f(Intr)l(o-)387
5209 y(duction)42 b(to)h(ER)m(OS)p Fr(.)f(A)-6 b(v)n(ailable)42
b(via)h(the)g(ER)m(OS)387 5309 y(home)20 b(page)f(at)387
5408 y Fn(http://www.cis.upenn.edu/\230eros)1992 91 y
Fr([Sha96b])80 b(Jonathan)19 b(S.)j(Shapiro.)d Fp(The)i(ER)m(OS)f
(Object)h(Refer)n(-)2379 191 y(ence)i(Manual)p Fr(.)g(In)g(progress.)g
(Draft)g(a)n(v)n(ailable)h(via)2379 291 y(the)c(ER)m(OS)h(home)e(page)g
(at)2379 390 y Fn(http://www.cis.upenn.edu/\230eros)1992
556 y Fr([Sha96c])85 b(Jonathan)42 b(S.)h(Shapiro,)k(Da)n(vid)c(J.)h(F)
o(arber)m(,)j(and)2379 656 y(Jonathan)42 b(M.)i(Smith.)g(\223State)g
(Caching)g(in)g(the)2379 756 y(ER)m(OS)36 b(K)n(ernel)g(\226)g
(Implementing)e(Ef)n(\002cient)h(Or)n(-)2379 855 y(thogonal)16
b(Persistence)i(in)f(a)i(Pure)e(Capability)g(Sys-)2379
955 y(tem\224,)47 b Fp(Pr)l(oceedings)41 b(of)g(the)h(7th)g
(International)2379 1054 y(W)-8 b(orkshop)21 b(on)f(P)-7
b(er)o(sistent)23 b(Object)e(Systems)p Fr(,)g(Cape)2379
1154 y(May)-5 b(,)19 b(N.J.)i(1996)1992 1320 y([Sha96d])80
b(Jonathan)14 b(S.)i(Shapiro,)f(Da)n(vid)g(J.)h(F)o(arber)m(,)f
(Jonathan)2379 1420 y(M.)30 b(Smith.)g(\223The)g(Measured)f
(Performance)e(of)j(a)2379 1519 y(F)o(ast)j(Local)e(IPC\224.)i
Fp(Pr)l(oceedings)d(of)j(the)f(5th)f(In-)2379 1619 y(ternational)g(W)-8
b(orkshop)32 b(on)f(Object)i(Orientation)2379 1719 y(in)40
b(Oper)o(ating)e(Systems)p Fr(,)45 b(Seattle,)g(W)-7
b(ashington,)2379 1818 y(No)o(v)o(ember)18 b(1996,)g(IEEE)1992
1984 y([Sha97])122 b(Jonathan)28 b(S.)i(Shapiro)f(and)g(Sam)h(W)-7
b(eber)i(.)30 b Fp(V)-9 b(erify-)2379 2084 y(ing)17 b(Oper)o(ating)f
(System)i(Security)p Fr(.)f(Department)f(of)2379 2183
y(Computer)21 b(and)h(Information)e(Science)i(T)-6 b(echnical)2379
2283 y(Report)20 b(MS-CIS-97-26,)d(F)o(orthcoming.)1992
2449 y([W)l(ul81])108 b(W)m(illiam)29 b(A.)g(W)l(ulf,)h(Ro)o(y)f(Le)n
(vin,)g(and)f(Samuel)g(P)-9 b(.)2379 2549 y(Harbison.)27
b Fp(HYDRA/C.mmp:)41 b(An)29 b(Experimental)2379 2648
y(Computer)20 b(System)g Fr(McGra)o(w)g(Hill,)g(1981.)1908
5657 y(11)p eop
%%Trailer
end
userdict /end-hook known{end-hook}if
%%EOF
ViewGit