%!PS (but not EPSF because of memory limits)
%%Creator: dvips by Radical Eye Software
%%Title: rtmach.dvi
%%Pages: 9 1
%%BoundingBox: 0 0 612 792
%%EndComments
%%BeginDocument: tex.pro
/TeXDict 200 dict def TeXDict begin /bdf{bind def}def /bop-aux{}bdf /@rigin{
/@page-height exch def /@page-width exch def 72 Resolution div dup neg scale
translate}bdf /@letter{Resolution dup -10 mul 8.5 11 @rigin}bdf /@landscape{[
0 1 -1 0 0 0]concat Resolution dup 8.5 11 @rigin}bdf /@a4{Resolution dup
-10.6929133858 mul 21 2.54 div 29.7 2.54 div @rigin}bdf /@legal{Resolution dup
-13 mul 8.5 14 @rigin}bdf /@11x17{statusdict /11x17tray known{statusdict begin
11x17tray end}if Resolution dup -16 mul 11 17 @rigin}bdf /@manualfeed{
statusdict /manualfeed true put}bdf /@copies{/#copies exch def}bdf /@draft{
/bop-aux{gsave initmatrix 72 dup scale @page-width 2 div @page-height 2 div
translate @page-height @page-width atan rotate /Helvetica-Bold findfont 2
scalefont setfont(DRAFT)dup stringwidth pop 2 div neg -1 moveto .95 setgray
show grestore}bdf}bdf /@FontMatrix[1 0 0 -1 0 0]def /@FontBBox[0 0 0 0]def
/dmystr(ZZf@@@)def /newname{dmystr cvn}bdf /df{/fontname exch def dmystr 2
fontname cvx(@@@@)cvs putinterval newname 7 dict def newname load begin
/FontType 3 def /FontMatrix @FontMatrix def /FontBBox @FontBBox def /BitMaps
256 array def /BuildChar{CharBuilder}def /Encoding IdentityEncoding def end
fontname{/foo setfont}2 array copy cvx def fontname load 0 dmystr 6 string
copy cvn cvx put}bdf /dfe{newname dup load definefont setfont}bdf /ch-image{
ch-data 0 get}bdf /ch-width{ch-data 1 get}bdf /ch-height{ch-data 2 get}bdf
/ch-xoff{ch-data 3 get}bdf /ch-yoff{ch-data 4 get}bdf /ch-dx{ch-data 5 get}
bdf /CharBuilder{save 3 1 roll exch /BitMaps get exch get /ch-data exch def
ch-data null ne{ch-dx 0 ch-xoff ch-yoff neg ch-xoff ch-width add ch-height
ch-yoff sub setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub
ch-height ch-yoff sub .1 add]{ch-image}imagemask}if restore}bdf /dc{/ch-code
exch def /ch-data exch def newname load /BitMaps get ch-code ch-data put}bdf
/bop{gsave /SaveImage save def /bop-aux load exec 0 0 moveto}bdf /eop{clear
SaveImage restore showpage grestore}bdf /@start{/Resolution exch def
/IdentityEncoding 256 array def 0 1 255{IdentityEncoding exch 1 string dup 0 3
index put cvn put}for}bdf /p{show}bdf /RuleMatrix[1 0 0 -1 -.1 -.1]def
/BlackDots 8 string def /v{gsave currentpoint translate false RuleMatrix{
BlackDots}imagemask grestore}bdf /a{moveto}bdf /delta 0 def /tail{dup /delta
exch def 0 rmoveto}bdf /b{exch show tail}bdf /c{show delta 4 sub tail}bdf /d{
show delta 3 sub tail}bdf /e{show delta 2 sub tail}bdf /f{show delta 1 sub
tail}bdf /g{show delta 0 rmoveto}bdf /h{show delta 1 add tail}bdf /i{show
delta 2 add tail}bdf /j{show delta 3 add tail}bdf /k{show delta 4 add tail}
bdf /l{show -4 0 rmoveto}bdf /m{show -3 0 rmoveto}bdf /n{show -2 0 rmoveto}
bdf /o{show -1 0 rmoveto}bdf /q{show 1 0 rmoveto}bdf /r{show 2 0 rmoveto}bdf
/s{show 3 0 rmoveto}bdf /t{show 4 0 rmoveto}bdf /w{0 rmoveto}bdf /x{0 exch
rmoveto}bdf /y{3 2 roll show moveto}bdf /bos{/section save def}bdf /eos{clear
section restore}bdf end
%%EndDocument
%%BeginDocument: texps.pro
TeXDict begin /rf{655360 div mul Resolution mul 7227 div /PixPerEm exch def
findfont dup length 1 add dict /newfont exch def{1 index /FID ne{newfont 3 1
roll put}{pop pop}ifelse}forall 256 dict begin newfont /Encoding get 255 -1 0{
2 copy get 4 -1 roll 1000 mul PixPerEm div def pop}for pop newfont /Metrics
currentdict put end /fontname exch def dmystr 2 fontname cvx(@@@@)cvs
putinterval newname dup newfont definefont[PixPerEm 0 0 PixPerEm neg 0 0]
makefont def fontname{/foo setfont}2 array copy cvx def fontname load 0 dmystr
6 string copy cvn cvx put}bdf /ObliqueSlant{dup sin exch cos div neg}bdf
/SlantFont{/foo exch def[1 0 foo 1 0 0]TransFont}bdf /ExtendFont{/foo exch def
258 2 roll 0 1 255{pop foo div 256 1 roll}for 258 -2 roll[foo 0 0 1 0 0]
TransFont}bdf /TransFont{exch findfont exch makefont dup length dict /newfont
exch def{1 index /FID ne{newfont 3 1 roll put}{pop pop}ifelse}forall dup
newfont definefont pop}bdf end
%%EndDocument
%%BeginDocument: special.pro
TeXDict begin /SDict 200 dict def SDict begin /@SpecialDefaults{/hs 612 def
/vs 792 def /ho 0 def /vo 0 def /hsc 1 def /vsc 1 def /ang 0 def /CLIP false
def /BBcalc false def}bdf /@scaleunit 1 def /@hscale{@scaleunit div /hsc exch
def}bdf /@vscale{@scaleunit div /vsc exch def}bdf /@hsize{/hs exch def /CLIP
true def}bdf /@vsize{/vs exch def /CLIP true def}bdf /@hoffset{/ho exch def}
bdf /@voffset{/vo exch def}bdf /@angle{/ang exch def}bdf /@rwi{10 div /rwi
exch def}bdf /@llx{/llx exch def}bdf /@lly{/lly exch def}bdf /@urx{/urx exch
def}bdf /@ury{/ury exch def /BBcalc true def}bdf end /@MacSetUp{userdict /md
known{userdict /md get type /dicttype eq{md begin /letter{}def /note{}def
/legal{}def /od{txpose 1 0 mtx defaultmatrix dtransform exch atan/pa exch def
newpath clippath mark{transform{itransform moveto}}{transform{itransform
lineto}}{6 -2 roll transform 6 -2 roll transform 6 -2 roll transform{
itransform 6 2 roll itransform 6 2 roll itransform 6 2 roll curveto}}{{
closepath}}pathforall newpath counttomark array astore /gc xdf pop ct 39 0 put
10 fz 0 fs 2 F/|______Courier fnt invertflag{PaintBlack}if}def /txpose{pxs pys
scale ppr aload pop por{noflips{pop exch neg exch translate pop 1 -1 scale}if
xflip yflip and{pop exch neg exch translate 180 rotate 1 -1 scale ppr 3 get
ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg translate}if xflip yflip
not and{pop exch neg exch translate pop 180 rotate ppr 3 get ppr 1 get neg sub
neg 0 translate}if yflip xflip not and{ppr 1 get neg ppr 0 get neg translate}
if}{noflips{translate pop pop 270 rotate 1 -1 scale}if xflip yflip and{
translate pop pop 90 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2
get ppr 0 get neg sub neg translate}if xflip yflip not and{translate pop pop
90 rotate ppr 3 get ppr 1 get neg sub neg 0 translate}if yflip xflip not and{
translate pop pop 270 rotate ppr 2 get ppr 0 get neg sub neg 0 exch translate}
if}ifelse scaleby96{ppr aload pop 4 -1 roll add 2 div 3 1 roll add 2 div 2
copy translate .96 dup scale neg exch neg exch translate}if}def /cp{pop pop
showpage pm restore}def end}if}if}def /psf$TeXscale{65536 div}def /startTexFig
{/psf$SavedState save def userdict maxlength dict begin Resolution 72 div dup
neg scale currentpoint translate /psf$ury exch psf$TeXscale def /psf$urx exch
psf$TeXscale def /psf$lly exch psf$TeXscale def /psf$llx exch psf$TeXscale def
/psf$y exch psf$TeXscale def /psf$x exch psf$TeXscale def currentpoint /psf$cy
exch def /psf$cx exch def /psf$sx psf$x psf$urx psf$llx sub div def /psf$sy
psf$y psf$ury psf$lly sub div def psf$sx psf$sy scale psf$cx psf$sx div
psf$llx sub psf$cy psf$sy div psf$ury sub translate /showpage{}def /erasepage{
}def /copypage{}def @MacSetUp}def /doclip{psf$llx psf$lly psf$urx psf$ury
currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll exch lineto
exch lineto exch lineto closepath clip newpath moveto}def /endTexFig{end
psf$SavedState restore}def /@beginspecial{SDict begin /SpecialSave save def
Resolution 72 div dup neg scale currentpoint translate @SpecialDefaults}bdf
/@setspecial{CLIP{newpath 0 0 moveto hs 0 rlineto 0 vs rlineto hs neg 0
rlineto closepath clip}{initclip}ifelse ho vo translate hsc vsc scale ang
rotate BBcalc{rwi urx llx sub div dup scale llx neg lly neg translate}if
/showpage{}def newpath}bdf /@endspecial{clear SpecialSave restore end}bdf
/@defspecial{SDict begin}bdf /@fedspecial{end}bdf /li{lineto}bdf /rl{rlineto}
bdf /rc{rcurveto}bdf /np{/SaveX currentpoint /SaveY exch def def newpath}bdf
/st{stroke SaveX SaveY moveto}bdf /fil{fill SaveX SaveY moveto}bdf /ellipse{
/endangle exch def /startangle exch def /yrad exch def /xrad exch def
/savematrix matrix currentmatrix def translate xrad yrad scale 0 0 1
startangle endangle arc savematrix setmatrix}bdf end
%%EndDocument
TeXDict begin bos 300 @start /fa 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 8 11 18 17 17 33 28 11 11 11 17 19 8 11 8 9 17 17 17 17 17
17 17 17 17 17 11 11 19 19 19 17 31 24 22 24 24 22 20 26 26 13 17 26 22 31 24
26 20 26 24 18 22 24 24 33 24 24 22 11 9 11 19 17 11 17 18 15 18 15 11 17 18 9
11 18 9 28 18 17 18 18 15 13 11 18 17 24 17 17 15 13 7 13 17 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 17 17 6 17 17 17 17 9 17
17 11 11 18 18 0 17 17 17 8 0 18 12 11 17 17 17 33 33 0 17 0 11 11 11 11 11 11
11 11 0 11 11 0 11 11 11 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 33 0 10 0 0 0 0 22
26 33 11 0 0 0 0 0 24 0 0 0 9 0 0 9 17 24 18 0 0 0 0 /Times-Bold 1000 524288
rf /fb 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 7 8
10 10 17 16 7 7 7 10 12 5 7 5 6 10 10 10 10 10 10 10 10 10 10 6 6 12 12 12 9
19 15 14 14 15 13 12 15 15 7 8 15 13 18 15 15 12 15 14 12 13 15 15 20 15 15 13
7 6 7 10 10 7 9 10 9 10 9 7 10 10 6 6 10 6 16 10 10 10 10 7 8 6 10 10 15 10 10
9 10 4 10 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 7 10 10 3 10 10 10 10 4 9 10 7 7 12 12 0 10 10 10 5 0 9 7 7 9 9 10 21 21 0 9
0 7 7 7 7 7 7 7 7 0 7 7 0 7 7 7 21 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 18 0 6 0 0
0 0 13 15 18 6 0 0 0 0 0 14 0 0 0 6 0 0 6 10 15 10 0 0 0 0 /Times-Roman 1000
327680 rf /fc df[<60F0F0701010101020204080>4 12 4 8 12]59 dc dfe /fd df[<FFFF
FF80FFFFFF80>25 2 3 -9 32]0 dc[<000001800000078000001E00000078000001E000000780
00001E00000078000001E00000078000001E00000078000000E0000000780000001E0000000780
000001E0000000780000001E0000000780000001E0000000780000001E00000007800000018000
0000000000000000000000000000000000000000000000000000007FFFFF00FFFFFF80>25 34 3
8 32]20 dc[<400004C0000C6000186000186000183000303000303000301800601800601FFFE0
0FFFC00C00C00C00C006018006018003030003030003030001860001860001860000CC0000CC00
00CC00007800007800007800003000003000>22 30 0 1 23]56 dc dfe /fe 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 9 10 10 17 16 7 7 7 10
14 5 7 5 6 10 10 10 10 10 10 10 10 10 10 7 7 14 14 14 10 19 13 13 14 15 13 13
15 15 7 9 14 12 17 14 15 13 15 13 10 12 15 13 17 13 12 12 8 6 8 9 10 7 10 10 9
10 9 10 10 10 6 6 9 6 15 10 10 10 10 8 8 6 10 9 14 9 9 8 8 6 8 11 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 10 10 3 10 10 10 10
4 12 10 7 7 10 10 0 10 10 10 5 0 11 7 7 12 12 10 18 21 0 10 0 7 7 7 7 7 7 7 7
0 7 7 0 7 7 7 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 18 0 6 0 0 0 0 12 15 20 6 0 0
0 0 0 14 0 0 0 6 0 0 6 10 14 10 0 0 0 0 /Times-Italic-Math
/Times-Italic 1.0 ExtendFont 1000 327680 rf /ff df[<FFFFFFFFFFFFC0FFFFFFFFFFFF
E07F00000001FFE07F000000001FE03F8000000003F01FC000000000F00FC000000000380FE000
0000001807F0000000000C03F8000000000403F8000000000401FC000000000200FE0000000000
007F0000000000007F0000000000003F8000000000001FC000000000000FC000000000000FE000
0000000007F0000000000003F8000000000003F8000000000001FC000000000000FE0000000000
007E0000000000007F0000000000003F8000000000001FC000000000001FC000000000000FC000
000000000780000000000003800000000000070000000000000E0000000000001C000000000000
380000000000007000000000000070000000000000E0000000000001C000000000000380000000
0000070000000000000E0000000000000E0000000000001C000000000200380000000004007000
0000000400E0000000000C01E0000000001801C00000000038038000000000F8070000000001F0
0E000000000FF01C00000001FFF03FFFFFFFFFFFE03FFFFFFFFFFFE07FFFFFFFFFFFE0FFFFFFFF
FFFFC0>55 58 2 58 60]88 dc dfe /fg 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 14 23 21 21 42 35 14 14 14 21 24 10 14 10 12 21 21 21
21 21 21 21 21 21 21 14 14 24 24 24 21 39 30 28 30 30 28 25 32 32 16 21 32 28
39 30 32 25 32 30 23 28 30 30 42 30 30 28 14 12 14 24 21 14 21 23 18 23 18 14
21 23 12 14 23 12 35 23 21 23 23 18 16 14 23 21 30 21 21 18 16 9 16 22 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14 21 21 7 21 21
21 21 12 21 21 14 14 23 23 0 21 21 21 10 0 22 15 14 21 21 21 42 42 0 21 0 14
14 14 14 14 14 14 14 0 14 14 0 14 14 14 42 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 42
0 12 0 0 0 0 28 32 42 14 0 0 0 0 0 30 0 0 0 12 0 0 12 21 30 23 0 0 0 0
/Times-Bold 1000 655360 rf /fh 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 12 17 28 25 25 50 41 17 17 17 25 28 12 17 12 14 25 25 25 25 25
25 25 25 25 25 17 17 28 28 28 25 46 36 33 36 36 33 30 39 39 19 25 39 33 47 36
39 30 39 36 28 33 36 36 50 36 36 33 17 14 17 29 25 17 25 28 22 28 22 17 25 28
14 17 28 14 41 28 25 28 28 22 19 17 28 25 36 25 25 22 20 11 20 26 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 25 25 8 25 25 25 25
14 25 25 17 17 28 28 0 25 25 25 12 0 27 17 17 25 25 25 50 50 0 25 0 17 17 17
17 17 17 17 17 0 17 17 0 17 17 17 50 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 50 0 15 0
0 0 0 33 39 50 16 0 0 0 0 0 36 0 0 0 14 0 0 14 25 36 28 0 0 0 0 /Times-Bold
1000 786432 rf /fi 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 7 10 12 15 15 24 23 10 10 10 15 16 7 10 7 8 15 15 15 15 15 15 15 15 15 15
8 8 16 16 16 13 27 21 19 19 21 18 16 21 21 10 11 21 18 26 21 21 16 21 19 16 18
21 21 27 21 21 18 10 8 10 14 15 10 13 15 13 15 13 10 15 15 8 8 15 8 23 15 15
15 15 10 11 8 15 15 21 15 15 13 14 6 14 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 15 15 5 15 15 15 15 5 13 15 10 10 16 16 0
15 15 15 7 0 13 10 10 13 13 15 29 29 0 13 0 10 10 10 10 10 10 10 10 0 10 10 0
10 10 10 29 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 26 0 8 0 0 0 0 18 21 26 9 0 0 0 0
0 19 0 0 0 8 0 0 8 15 21 15 0 0 0 0 /Times-Roman 1000 458752 rf /fj 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 12 15 15 24 23 10
10 10 15 20 7 10 7 8 15 15 15 15 15 15 15 15 15 15 10 10 20 20 20 15 27 18 18
19 21 18 18 21 21 10 13 19 16 24 19 21 18 21 18 15 16 21 18 24 18 16 16 11 8
11 12 15 10 15 15 13 15 13 14 15 15 8 8 13 8 21 15 15 15 15 11 11 8 15 13 19
13 13 11 12 8 12 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 11 15 15 5 15 15 15 15 6 16 15 10 10 15 15 0 15 15 15 7 0 15 10 10
16 16 15 26 29 0 15 0 10 10 10 10 10 10 10 10 0 10 10 0 10 10 10 26 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 26 0 8 0 0 0 0 16 21 27 9 0 0 0 0 0 19 0 0 0 8 0 0 8 15
19 15 0 0 0 0 /Times-Italic-Math /Times-Italic 1.0 ExtendFont 1000 458752 rf
/fk 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14 17 21
21 35 32 14 14 14 21 28 10 14 10 12 21 21 21 21 21 21 21 21 21 21 14 14 28 28
28 21 38 25 25 28 30 25 25 30 30 14 18 28 23 35 28 30 25 30 25 21 23 30 25 35
25 23 23 16 12 16 18 21 14 21 21 18 21 18 20 21 21 12 12 18 12 30 21 21 21 21
16 16 12 21 18 28 18 18 16 17 11 17 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 16 21 21 7 21 21 21 21 9 23 21 14 14 21 21 0 21 21
21 10 0 22 15 14 23 23 21 37 42 0 21 0 14 14 14 14 14 14 14 14 0 14 14 0 14 14
14 37 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 37 0 11 0 0 0 0 23 30 39 13 0 0 0 0 0 28
0 0 0 12 0 0 12 21 28 21 0 0 0 0 /Times-Italic-Math
/Times-Italic 1.0 ExtendFont 1000 655360 rf /fl 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 11 14 17 17 28 26 11 11 11 17 19 8 11 8 9
17 17 17 17 17 17 17 17 17 17 9 9 19 19 19 15 31 24 22 22 24 20 18 24 24 11 13
24 20 30 24 24 18 24 22 18 20 24 24 31 24 24 20 11 9 11 16 17 11 15 17 15 17
15 11 17 17 9 9 17 9 26 17 17 17 17 11 13 9 17 17 24 17 17 15 16 7 16 18 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 17 17 6 17 17
17 17 6 15 17 11 11 18 18 0 17 17 17 8 0 15 12 11 15 15 17 33 33 0 15 0 11 11
11 11 11 11 11 11 0 11 11 0 11 11 11 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 30 0 9
0 0 0 0 20 24 30 10 0 0 0 0 0 22 0 0 0 9 0 0 9 17 24 17 0 0 0 0 /Times-Roman
1000 524288 rf /fm 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 6 8 10 12 12 21 19 8 8 8 12 14 6 8 6 7 12 12 12 12 12 12 12 12 12 12 7 7
14 14 14 11 23 18 17 17 18 15 14 18 18 8 10 18 15 22 18 18 14 18 17 14 15 18
18 24 18 18 15 8 7 8 12 12 8 11 12 11 12 11 8 12 12 7 7 12 7 19 12 12 12 12 8
10 7 12 12 18 12 12 11 12 5 12 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 8 12 12 4 12 12 12 12 4 11 12 8 8 14 14 0 12 12 12 6 0
11 9 8 11 11 12 25 25 0 11 0 8 8 8 8 8 8 8 8 0 8 8 0 8 8 8 25 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 22 0 7 0 0 0 0 15 18 22 8 0 0 0 0 0 17 0 0 0 7 0 0 7 12 18 12
0 0 0 0 /Times-Roman 1000 393216 rf /fn 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 10 14 17 21 21 35 32 14 14 14 21 28 10 14 10 12 21
21 21 21 21 21 21 21 21 21 14 14 28 28 28 21 38 25 25 28 30 25 25 30 30 14 18
28 23 35 28 30 25 30 25 21 23 30 25 35 25 23 23 16 12 16 18 21 14 21 21 18 21
18 12 21 21 12 12 18 12 30 21 21 21 21 16 16 12 21 18 28 18 18 16 17 11 17 22
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16 21 21 7
21 21 21 21 9 23 21 14 14 21 21 0 21 21 21 10 0 22 15 14 23 23 21 37 42 0 21 0
14 14 14 14 14 14 14 14 0 14 14 0 14 14 14 37 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
37 0 11 0 0 0 0 23 30 39 13 0 0 0 0 0 28 0 0 0 12 0 0 12 21 28 21 0 0 0 0
/Times-Italic 1000 655360 rf /fo 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 10 14 17 21 21 35 32 14 14 14 21 23 10 14 10 12 21 21 21 21
21 21 21 21 21 21 12 12 23 23 23 18 38 30 28 28 30 25 23 30 30 14 16 30 25 37
30 30 23 30 28 23 25 30 30 39 30 30 25 14 12 14 19 21 14 18 21 18 21 18 14 21
21 12 12 21 12 32 21 21 21 21 14 16 12 21 21 30 21 21 18 20 8 20 22 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14 21 21 7 21 21 21
21 7 18 21 14 14 23 23 0 21 21 21 10 0 19 15 14 18 18 21 42 42 0 18 0 14 14 14
14 14 14 14 14 0 14 14 0 14 14 14 42 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 37 0 11 0
0 0 0 25 30 37 13 0 0 0 0 0 28 0 0 0 12 0 0 12 21 30 21 0 0 0 0 /Times-Roman
1000 655360 rf /fp 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 12 17 21 25 25 41 39 17 17 17 25 34 12 17 12 14 25 25 25 25 25 25 25 25 25
25 17 17 34 34 34 25 46 30 30 33 36 30 30 36 36 17 22 33 28 41 33 36 30 36 30
25 28 36 30 41 30 28 28 19 14 19 21 25 17 25 25 22 25 22 14 25 25 14 14 22 14
36 25 25 25 25 19 19 14 25 22 33 22 22 19 20 14 20 27 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 19 25 25 8 25 25 25 25 11 28 25 17
17 25 25 0 25 25 25 12 0 26 17 17 28 28 25 44 50 0 25 0 17 17 17 17 17 17 17
17 0 17 17 0 17 17 17 44 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 44 0 14 0 0 0 0 28 36
47 15 0 0 0 0 0 33 0 0 0 14 0 0 14 25 33 25 0 0 0 0 /Times-Italic 1000 786432
rf /fq 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12 17
20 25 25 41 39 17 17 17 25 28 12 17 12 14 25 25 25 25 25 25 25 25 25 25 14 14
28 28 28 22 46 36 33 33 36 30 28 36 36 17 19 36 30 44 36 36 28 36 33 28 30 36
36 47 36 36 30 17 14 17 23 25 17 22 25 22 25 22 17 25 25 14 14 25 14 39 25 25
25 25 17 19 14 25 25 36 25 25 22 24 10 24 27 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 25 25 8 25 25 25 25 9 22 25 17 17 28 28 0
25 25 25 12 0 23 17 17 22 22 25 50 50 0 22 0 17 17 17 17 17 17 17 17 0 17 17 0
17 17 17 50 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 44 0 14 0 0 0 0 30 36 44 15 0 0 0
0 0 33 0 0 0 14 0 0 14 25 36 25 0 0 0 0 /Times-Roman 1000 786432 rf /fr 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 20 33 30 30 60 50
20 20 20 30 34 15 20 15 17 30 30 30 30 30 30 30 30 30 30 20 20 34 34 34 30 56
43 40 43 43 40 37 47 47 23 30 47 40 56 43 47 37 47 43 33 40 43 43 60 43 43 40
20 17 20 35 30 20 30 33 27 33 27 20 30 33 17 20 33 17 50 33 30 33 33 27 23 20
33 30 43 30 30 27 24 13 24 31 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 20 30 30 10 30 30 30 30 17 30 30 20 20 33 33 0 30 30 30 15
0 32 21 20 30 30 30 60 60 0 30 0 20 20 20 20 20 20 20 20 0 20 20 0 20 20 20 60
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 60 0 18 0 0 0 0 40 47 60 20 0 0 0 0 0 43 0 0 0
17 0 0 17 30 43 33 0 0 0 0 /Times-Bold 1000 943718 rf end
 TeXDict begin @letter
%%EndProlog
%%Page: 1 1
 bop 415 193 a fr(Evaluation)14 b(of)h(Real-T)o(ime)e(Synchr)o(onization)920
268 y(in)730 343 y(Real-T)o(ime)g(Mach)554 463 y fq(Hideyuki)f(T)m(okuda)g
(and)g(T)m(atsuo)h(Nakajima)663 521 y fp(School)f(of)h(Computer)f(Science)665
579 y(Carnegie)h(Mellon)g(University)625 637 y(Pittsbur)o(gh,)g(Pennsylvania)
g(15213)778 696 y fq(hxt@cs.cmu.edu)-118 858 y fr(Abstract)-118 952 y fo(Real\
-T)o(ime)g(Mach)h(provides)f(real-time)g(thread)g(and)g(real-time)h(syn-)-118
1002 y(chronization)c(facilities.)19 b(A)12 b(real-time)g(thread)f(can)i(be)f
(created)g(for)g(a)-118 1052 y(periodic)d(or)g(aperiodic)h(activity)e(with)h
(a)h(timing)e(constraint.)14 b(Threads)-118 1101 y(can)f(be)g(synchronized)f
(among)g(them)h(using)e(a)i(real-time)g(version)f(of)-118 1151 y(the)g(monito\
r)g(based)h(synchronization)e(mechanism)j(with)e(a)h(suitable)-118 1201 y(loc\
king)f(protocol.)25 b(In)13 b(Real-T)o(ime)h(Mach,)i(we)e(have)g(implemented)
-118 1251 y(several)d(locking)f(policies,)g(such)h(as)h fn(kernelized)f(monit\
or)p fo(,)f fn(basic)h(pri-)-118 1301 y(ority)17 b(priority)g(inheritance)g
(pr)n(otocol)p fo(,)i fn(priority)e(ceiling)g(pr)n(otocol)p fo(,)-118 1350 y
(and)e fn(r)n(estartable)f(critical)g(section)p fo(,)i(for)e(real-time)h(appl\
ications.)28 b(It)-118 1400 y(can)11 b(also)f(avoid)g(a)h(unbounded)d fn(prio\
rity)i(inversion)g fo(problem.)-77 1451 y(In)d(this)e(paper)o(,)i(we)g(descri\
be)g(the)g(real-time)f(synchronization)f(facili-)-118 1500 y(ties)h(in)g(Real\
-T)o(ime)h(Mach)g(and)f(its)g(implementation)f(and)h(performance)-118 1550 y
(evaluation.)22 b(Our)12 b(evaluation)g(results)h(demonstrated)f(that)g(a)i
(proper)-118 1600 y(choice)g(of)g(locking)f(policy)g(can)h(avoid)g(unbounded)
e(priority)g(inver-)-118 1650 y(sions)k(and)h(improve)f(the)g(processor)h(sch\
edulability)e(for)h(real-time)-118 1700 y(applications.)-118 1843 y fr(1)60 b
(Intr)o(oduction)-118 1937 y fo(A)18 b(new)f(challenge)h(in)f(advanced)i(real\
-time)e(systems)h(is)g(not)e(only)-118 1986 y(creating)6 b(a)h(fast)g(and)g
(responsive)f(kernel,)i(but)d(providing)g(a)i(predictable)-118 2036 y(and)g
(analyzable)h(real-time)f(computing)e(environment.)14 b(An)6 b(advanced)-118
2086 y(real-time)11 b(kernel)g(should)f(allow)h(a)g(system)h(designer)f(to)f
(analyze)i(the)-118 2136 y(runtime)i(behavior)g(at)h(the)f(design)h(stage)g
(and)g(predict)f(whether)g(the)-118 2186 y(given)5 b(real-time)i(tasks)f(havi\
ng)f(various)h(types)g(of)g(system)g(interactions)-118 2235 y(can)11 b(meet)g
(their)e(timing)g(requirements.)-77 2286 y(The)18 b(objective)e(of)g(Real-T)o
(ime)h(Mach)g(is)g(to)f(create)i(a)f(real-time)-118 2336 y(version)9 b(of)h
(Mach)g(operating)f(system)h(which)g(can)g(provide)f(such)h(pre-)-118 2374 y
417 2 v -73 2401 a fm(1)-25 2413 y fl(This)i(research)f(was)h(supported)e(in)
i(part)f(by)h(the)f(U.S.)j(Naval)d(Ocean)g(Systems)-58 2453 y(Center)f(under)
f(contract)h(number)f(N66001-87-C-0155,)f(by)i(the)h(Of)o(\256ce)g(of)f(Naval)
-58 2492 y(Research)g(under)g(contract)g(number)g(N00014-84-K-0734,)e(by)j
(the)g(Defense)f(Ad-)-58 2532 y(vanced)f(Research)h(Projects)h(Agency)n(,)f
(ARP)m(A)i(Order)f(No.)20 b(7330)10 b(under)g(contract)-58 2571 y(number)d
(MDA72-90-C-0035,)f(by)i(the)g(Federal)g(Systems)h(Division)f(of)g(IBM)h(Cor-)
-58 2610 y(poration)g(under)g(University)g(Agreement)g(Y)l(A-278067,)g(and)h
(by)f(the)h(SONY)h(Cor-)-58 2650 y(poration.)16 b(The)9 b(views)h(and)f(concl\
usions)e(contained)h(in)i(this)g(document)e(are)h(those)-58 2689 y(of)e(the)h
(authors)e(and)h(should)g(not)g(be)g(interpreted)g(as)h(representing)e(of)o
(\256cial)i(policies,)-58 2729 y(either)h(expressed)e(or)j(implied,)f(of)g
(NOSC,)i(ONR,)f(DARP)m(A,)g(IBM,)g(SONY)l(,)g(or)f(the)-58 2768 y(U.S.)g(Gove\
rnment.)966 858 y fo(dictable)16 b(real-time)g(computing)g(environment.)33 b
(However)n(,)19 b(in)d(the)966 908 y(Mach)h(kernel,)j(it)c(is)h(often)g(dif)n
(\256cult)g(to)f(analyze)i(the)f(runtime)g(be-)966 958 y(haviour)c(of)h(the)g
(time)h(critical)e(activities)h(due)g(to)g(lack)h(of)f(real-time)966 1008 y
(scheduling)d(and)i(synchronization)d(facilities.)21 b(For)13 b(instance,)g
(Mach)966 1057 y(provides)g(synchronization)g(facility)g(among)h(threads)h
(using)e(a)i(con-)966 1107 y(ventional)f(monitor)m(-based)i(mechanism[5)q(].)
31 b(Threads)16 b(can)g(enter)f(a)966 1157 y(critical)9 b(section)h(in)g(FIFO)
g(order)n(,)h(however)n(,)g(this)e(may)i(cause)h(a)e fn(a)h(pri-)966 1207 y
(ority)f(inversion)g(pr)n(oblem)g fo(among)h(threads.)16 b(If)10 b(many)h(low\
er)f(priority)966 1257 y(threads)j(are)h(already)f(waiting)f(on)g(a)i(mutex)f
(variable,)h(a)g(higher)e(pri-)966 1307 y(ority)g(thread)i(which)f(may)i(have)
f(a)h(tighter)d(deadline)i(must)g(wait)f(for)966 1356 y(their)d(completion.)
15 b(Thus,)d(the)e(higher)g(priority)f(thread)h(may)i(miss)f(its)966 1406 y
(deadline.)1007 1456 y(Furthermore,)h(a)g(real-time)g(system)g(designer)f(nee\
d)h(to)f(determine)966 1506 y(the)d(worst)f(case)j(blocking)d(delay)h(for)g
(a)h(higher)e(priority)f(thread)i(for)g(the)966 1556 y(shared)14 b(resource.)
26 b(It)13 b(is)g(often)g(impossible)g(to)g(compute)h(the)f(bound)966 1606 y
(if)f(a)g(thread)h(in)f(the)g(protected)g(region)f(can)i(be)g(preemptable.)22
b(Let)13 b(us)966 1656 y(consider)g(the)g(following)f(case.)26 b(Suppose)14 b
(that)f(the)g(lowest)g(priority)966 1705 y(thread)e fk(T)1104 1711 y fj(L)
1133 1705 y fo(is)g(in)g(the)f(critical)h(region)f(\256rst,)i(then)e(the)h
(highest)f(priority)966 1755 y(thread)i fk(T)1105 1761 y fj(H)1140 1755 y fo
(becomes)i(runnable)d(and)h(attempts)g(to)g(obtain)f(the)h(mutex)966 1805 y
(variable.)23 b(However)n(,)14 b(since)f fk(T)1428 1811 y fj(L)1460 1805 y fo
(is)g(in)f(the)h(critical)f(region,)h fk(T)1891 1811 y fj(H)1927 1805 y fo
(must)966 1855 y(wait)f(for)g(its)h(completion.)22 b(After)12 b fk(T)1507 1861
y fj(L)1538 1855 y fo(resumed,)j(a)e(medium)g(priority)966 1905 y(thread)g fk
(T)1106 1911 y fj(M)p fi(1)1161 1905 y fo(becomes)h(runnable.)25 b(Then)14 b
fk(T)1622 1911 y fj(M)p fi(1)1676 1905 y fo(starts)f(running)f(with-)966 1954
y(out)h(using)g(the)h(critical)f(resource)i(and)f(wakes)h(up)e(another)h(medi\
um)966 2004 y(priority)9 b(thread)j fk(T)1241 2010 y fj(M)p fi(2)1294 2004 y
fo(and)g(so)f(on.)20 b(Under)12 b(this)f(type)g(of)h(interactions,)966 2054 y
(the)i(worst)h(case)h(blocking)d(time)i(of)g fk(T)1547 2060 y fj(H)1585 2054 y
fo(cannot)f(be)i(determined)e(by)966 2104 y(without)6 b(knowing)i(all)g(behav\
ior)g(of)h(related)g(medium)g(priority)d(thread)966 2154 y fk(T)989 2160 y fj
(M)1015 2154 y fo(')n(s.)1007 2204 y(In)17 b(order)f(to)g(bound)g(the)g(worst)
g(case)i(blocking)d(time,)k(a)e(simple)966 2254 y(solution)12 b(called)j fn
(priority)e(inheritance)g fo(scheme)j(was)f(developed)g(in)966 2303 y(our)c
(group)h([12)o(,)h(10)o(,)g(14].)21 b(An)12 b(priority)e(inheritance)i(scheme)
i(is)e(that)966 2353 y(once)c fk(T)1075 2359 y fj(H)1107 2353 y fo(blocks)g
(on)g(the)g(mutex)g(variable,)h fk(T)1621 2359 y fj(L)1648 2353 y fo(inherits)
e(the)h(priority)e(of)966 2403 y fk(T)989 2409 y fj(H)1012 2403 y fo(.)18 b
(Then,)12 b fk(T)1170 2409 y fj(M)p fi(1)1222 2403 y fo(cannot)f(preempt)g
(the)g(activity)f(of)h fk(T)1758 2409 y fj(L)1787 2403 y fo(in)g(the)g(critic\
al)966 2453 y(region.)j(In)8 b(this)h(way)m(,)h(the)f(worst)f(case)j(blocking)
c(time)i(of)g fk(T)1842 2459 y fj(H)1874 2453 y fo(can)h(be)f(a)966 2503 y
(function)d(of)i(the)h(duration)d(of)j(the)f(critical)f(region,)i(and)f(not)g
(a)h(function)966 2552 y(of)h(the)g(execution)f(times)i(of)f(the)g(medium)g
(priority)e(tasks.)1007 2603 y(Real-T)o(ime)18 b(Mach)g([15)o(])f(provides)g
(a)h(set)f(of)g(locking)f(protocols)966 2652 y(for)d(the)i(mutex)f(variable)g
(for)g(sharing)f(resources)j(among)e(real-time)966 2702 y(threads.)19 b(W)l
(e)12 b(have)g(implemented)g(\256ve)g(locking)e(protocols,)h(namely)966 2752 y
fn(kernelized)17 b(monitor)p fo(,)f fn(basic)g(priority)p fo(,)i fn(basic)e
(priority)f(inheritance)935 2877 y fo( )p eop
%%Page: 2 2
 bop -118 77 a fn(pr)n(otocol)p fo(,)10 b fn(priority)g(ceiling)g(pr)n(otocol)
p fo(,)g(and)h fn(r)o(estartable)f(critical)f(sec-)-118 127 y(tion)g fo(to)h
(be)g(used)h(for)e(various)h(real-time)g(applications.)-77 184 y(In)16 b(this)
g(paper)n(,)i(we)f(describe)g(the)f(implementation)f(and)h(perfor-)-118 234 y
(mance)8 b(evaluation)d(of)i(real-time)f(synchronization)f(facilities)g(in)h
(Real-)-118 284 y(T)o(ime)i(Mach.)15 b(In)8 b(Section)f(2,)i(we)f(\256rst)g
(introduce)f(the)h(real-time)f(thread)-118 334 y(model)k(and)g(synchronizatio\
n)e(facilities)h(in)g(Real-T)o(ime)h(Mach.)18 b(Sec-)-118 384 y(tion)6 b(3)i
(discusses)h(the)e(extended)h(system)g(interface)g(for)g(real-time)g(syn-)
-118 433 y(chronization)g(and)i(the)g(implementation)f(of)g(synchronization)f
(mech-)-118 483 y(anisms)17 b(and)f(policy)g(modules.)34 b(In)16 b(Section)g
(4,)i(we)f(also)g(describe)-118 533 y(the)10 b(performance)i(evaluation)d(of)
i(thread)f(preemption)g(and)g(the)h(lock-)-118 583 y(ing)h(protocols.)22 b
(Related)12 b(work)h(is)f(discussed)h(in)g(Section)f(5)h(and)g(we)-118 633 y
(describe)e(the)f(conclusion)f(and)h(future)g(work)f(in)h(Section)g(6.)-118
815 y fr(2)60 b(Real-T)o(ime)18 b(Thr)o(ead)i(and)h(Synchr)o(oniza-)-28 889 y
(tion)14 b(Model)-118 997 y fo(In)e(this)f(section,)h(we)h(brie\257y)e(descri\
be)h(a)h(real-time)f(thread)g(and)g(syn-)-118 1047 y(chronization)k(model)h
(we)g(adopted)g(in)f(Real-T)o(ime)i(Mach)f(and)g(the)-118 1096 y(notion)10 b
(of)i(schedulable)g(bound)f(for)h(synchronizing)e(real-time)i(tasks)-118 1146
y(in)e(a)g(single)g(processor)g(environment.)-118 1307 y fh(2.1)50 b(Real-T)o
(ime)13 b(Thr)o(ead)f(Model)-118 1399 y fo(A)c(thread)g(can)g(be)g(de\256ned)
h(for)e(a)i(real-time)e(or)h(non-real-time)f(activity)l(.)-118 1449 y(Each)17
b(thread)f(is)g(speci\256ed)h(by)f(at)h(least)f(a)h(procedure)f(name)h(and)g
(a)-118 1499 y(stack)h(descriptor)f(which)g(speci\256es)i(the)f(size)h(and)e
(address)i(of)e(the)-118 1549 y(local)f(stack)g(region.)32 b(For)16 b(a)h(rea\
l-time)f(thread,)i(additional)c fn(timing)-118 1599 y(attributes)d fo(must)i
(be)h(de\256ned)f(by)g(a)h(timing)e(attribute)f(descriptor)m(.)24 b(A)-118
1648 y(real-time)11 b(thread)h(can)g(be)g(also)g(de\256ned)f(as)i(a)f fn(har)
n(d)f fo(real-time)h(or)f fn(soft)-118 1698 y fo(real-time)g(thread.)19 b(By)
11 b(a)h(hard)f(real-time)g(thread,)h(we)g(mean)h(that)d(the)-118 1748 y(thre\
ad)15 b(must)f(complete)h(its)f(activities)g(by)h(its)f fn(har)n(d)g fo(deadl\
ine)h(time,)-118 1798 y(otherwise)e(it)h(will)e(cause)j(undesirable)f(damage)
h(or)f(a)g(fatal)g(error)g(to)-118 1848 y(the)e(system.)21 b(The)12 b(soft)g
(real-time)g(thread,)g(on)g(the)g(other)f(hand,)i(does)-118 1897 y(not)e(have)
i(such)g(a)g(hard)f(deadline,)h(and)g(it)f(still)e(makes)k(sense)f(for)f(the)
-118 1947 y(system)g(to)f(complete)i(the)e(thread)h(even)g(if)g(it)f(passed)h
(its)f(critical)h(\(i.e.)-118 1997 y fn(soft)d fo(deadline\))h(time.)-77 2055
y(A)g(real-time)f(thread)g(can)h(be)g(also)f(de\256ned)h(as)g(a)g fn(periodic)
f fo(or)g fn(aperi-)-118 2104 y(odic)f fo(thread)g(based)i(on)e(the)g(nature)
g(of)h(its)e(activity)l(.)15 b(A)9 b(periodic)e(thread)-118 2154 y fk(P)-93
2160 y fj(i)-75 2154 y fo(is)h(de\256ned)g(by)g(the)f(worst)g(case)j(executio\
n)d(time)h fk(C)658 2160 y fj(i)668 2154 y fo(,)h(period)e fk(T)824 2160 y fj
(i)834 2154 y fo(,)i(start)-118 2204 y(time)j fk(S)-11 2210 y fj(i)-1 2204 y
fo(,)h(phase)f(of)o(fset)g fk(O)264 2210 y fj(i)274 2204 y fo(,)h(and)f(task')
m(s)h(semantic)f(importance)g(value)-118 2254 y fk(V)-93 2260 y fj(i)-83 2254
y fo(.)22 b(In)12 b(a)h(periodic)f(thread,)h(a)g(new)f(instantiation)e(of)i
(the)g(thread)h(will)-118 2304 y(be)e(scheduled)g(at)g fk(S)171 2310 y fj(i)
191 2304 y fo(and)g(then)f(repeat)i(the)e(activity)f(in)i(every)g fk(T)823
2310 y fj(i)833 2304 y fo(.)17 b(The)-118 2354 y(phase)c(of)o(fset)f(is)g(use\
d)g(to)g(adjust)f(a)i(ready)g(time)f(within)e(each)k(period.)-118 2403 y(If)g
(a)i(periodic)d(thread)i(is)f(a)i(soft)e(real-time)g(thread,)i(it)e(may)i(nee\
d)f(to)-118 2453 y(express)h(the)g(abort)f(time)h(which)f(tells)g(the)h(sched\
uler)g(to)f(abort)g(the)-118 2503 y(thread.)26 b(An)14 b(aperiodic)f(thread)h
fk(AP)423 2509 y fj(j)448 2503 y fo(is)g(de\256ned)g(by)g(the)f(worst)h(case)
-118 2553 y(execution)c(time)h fk(C)167 2559 y fj(j)177 2553 y fo(,)h(the)e
(worst)h(case)h(interarrival)e(time)g fk(A)751 2559 y fj(j)762 2553 y fo(,)h
(deadline)-118 2603 y fk(D)-88 2609 y fj(j)-78 2603 y fo(,)f(and)g(task')n
(s)g(semantic)g(importance)g(value)f fk(V)595 2609 y fj(i)606 2603 y fo(.)15 b
(In)10 b(the)f(case)i(of)f(soft)-118 2652 y(real-time)e(threads,)i fk(A)205
2658 y fj(j)224 2652 y fo(indicates)e(the)g(average)i(case)g(interarrival)d
(time)-118 2702 y(and)i fk(D)-19 2708 y fj(j)0 2702 y fo(represents)h(the)f
(average)h(response)f(time.)15 b(Abort)8 b(time)h(can)h(be)-118 2752 y(also)g
(de\256ned)h(for)f(the)g(soft)f(real-time)h(thread.)966 77 y fh(2.2)50 b(Real\
-T)n(ime)13 b(Synchr)o(onization)e(Model)966 156 y fo(In)g(a)g(real-time)h
(synchronization)d(model,)j(we)g(have)f(created)i(various)966 206 y(synchroni\
zation)f(policies)h(based)h(on)g(two)f(basic)h(factors:)22 b(one)14 b(is)f
(a)966 256 y(queueing)7 b(order)g(among)h(waiting)f(threads)h(and)f(the)h(oth\
er)f(is)h(preempt-)966 305 y(ability)g(of)i(the)g(running)f(thread)h(in)f(the)
i(critical)e(section.)1007 356 y(T)o(raditional)18 b(synchronization)g(primit\
ives)g(use)i(FIFO)f(ordering)966 406 y(among)14 b(waiting)f(threads)i(to)f
(enter)g(a)h(critical)f(section,)i(since)f(FIFO)966 456 y(ordering)8 b(can)j
(avoid)e(the)h(starvation,)f(In)g(real-time)h(computing)f(envi-)966 505 y(ron\
ment,)f(however)n(,)i(FIFO)e(ordering)f(often)h(creates)i(a)f(priority)d(inve\
r-)966 555 y(sion)j(problem.)16 b(A)11 b(higher)e(thread)i(must)f(wait)g(for)
g(the)h(completion)e(of)966 605 y(all)h(low)g(priority)e(threads)j(in)f(the)g
(waiting)g(queue.)16 b(If)10 b(all)h(of)f(real-time)966 655 y(threads)i(can)i
(meet)f(their)f(deadlines,)h(then)g(there)f(will)g(be)h(no)f(starva-)966 705 y
(tion)f(among)h(these)h(threads.)22 b(Thus,)14 b(in)e(real-time)g(synchroniza\
tion,)966 754 y(the)f(system)h(should)e(provide)g(a)i(deadline)f(based)i(\(or)
d(priority)g(based\))966 804 y(ordering)f(to)g(avoid)h(unbound)f(priority)f
(inversion)g(problems.)1007 855 y(Preemptability)14 b(of)h(the)g(running)e
(thread)i(in)g(the)g(critical)f(section)966 905 y(also)c(affects)h(the)g(sync\
hronization)e(policies)h(and)h(the)g(schedulability)966 954 y(of)h(the)h(task)
g(sets.)23 b(In)13 b(Real-T)n(ime)h(Mach,)g(the)f(following)d(three)j(pre-)
966 1004 y(emption)h(levels)i(of)f(the)h(running)d(task)j(in)f(the)g(critical)
g(section)h(has)966 1054 y(been)10 b(supported.)966 1148 y fg(Non)g(Preemptab\
le:)21 b fo(No)13 b(preemption)h(is)g(allowed)f(while)h(a)g(thread)1049 1198 y
(is)c(executing)f(in)h(the)g(critical)g(section.)966 1284 y fg(Preemptable:)
20 b fo(A)8 b(higher)g(priority)d(thread)j(can)g(preempt)h(the)e(current)1049
1333 y(running)i(thread.)18 b(If)12 b(the)f(higher)f(priority)f(thread)i(need)
h(to)f(enter)1049 1383 y(the)e(critical)g(section,)h(it)f(will)g(be)h(blocked)
f(\(i.e.,)i(it)e(must)g(wait)g(for)1049 1433 y(the)h(completion)f(of)h(the)g
(critical)g(section\).)966 1519 y fg(Restartable:)20 b fo(A)11 b(higher)f(pri\
ority)f(thread)h(can)i(preempt)f(the)f(current)1049 1569 y(running)f(thread.)
17 b(It)10 b(then)h(aborts)f(the)h(running)e(thread)i(and)g(puts)1049 1618 y
(the)g(thread)h(back)g(to)f(the)h(waiting)e(queue.)20 b(The)12 b(higher)f(pri\
ority)1049 1668 y(thread)h(executes)i(the)f(critical)g(section)f(without)f
(further)h(delay)m(.)1049 1718 y(The)d(preempted)h(lower)f(priority)d(thread)
j(will)f(restart)h(later)g(from)1049 1768 y(the)h(beginning)e(of)i(the)g(crit\
ical)g(section.)1007 1862 y(By)h(selecting)h(a)g(queueing)f(ordering)g(and)g
(the)h(above)g(preemption)966 1912 y(choices,)f(the)e(following)f(synchroniza\
tion)g(policies)h(can)i(be)f(de\256ned:)966 1997 y fg(Kernelized)i(Monitor)e
(pr)o(otocol)g(\(KM\):)21 b fo(KM)15 b(protocol)g(takes)h(the)1049 2047 y(non)
9 b(preemptable)i(mode.)966 2132 y fg(Basic)f(Priority)g(pr)o(otocol)g(\(BP\)\
:)20 b fo(BP)10 b(protocol)e(takes)i(the)f(preempt-)1049 2182 y(able)e(mode)h
(and)g(the)f(queueing)g(ordering)f(is)i(based)g(on)f(the)g(thread)1049 2232 y
(priority)-6 b(.)966 2318 y fg(Basic)10 b(Priority)g(Inheritance)h(protocol)e
(\(BPI\):)21 b fo(BPI)k(protocol)f(is)1049 2367 y(created)13 b(as)g(BP)f(prot\
ocol)f(plus)g(the)i(priority)c(inheritance)j(func-)1049 2417 y(tion.)24 b(By)
14 b(this)f(function,)g(a)i(lower)e(priority)f(thread)h(executing)1049 2467 y
(the)g(critical)g(section)h(inherits)e(the)i(priority)d(of)i(higher)g(priorit\
y)1049 2517 y(thread,)d(when)g(the)h(lock)e(is)h(con\257icted.)966 2603 y fg
(Priority)g(Ceiling)f(protocol)g(\(PCP\):)21 b fo(PCP)d(protocol)e(is)h(an)h
(exten-)1049 2652 y(sion)d(of)h(BPI)h(protocol.)32 b(In)16 b(PCP)-5 b(,)17 b
(the)f(it)g(ceiling)f(priority)f(of)1049 2702 y(the)f(lock)h(is)g(de\256ned)g
(by)g(the)f(priority)f(of)i(the)f(highest)g(priority)1049 2752 y(thread)f(tha\
t)g(may)h(lock)f(the)h(lock)f(variable.)22 b(The)13 b(execution)f(of)935 2877
y( )p eop
%%Page: 3 3
 bop -35 77 a fo(the)7 b(thread)g(is)h(blocked)f(when)g(the)g(priority)e(ceil\
ing)i(of)g(the)g(lock)g(is)-35 127 y(not)g(higher)g(than)g(all)h(locks)f(whic\
h)h(are)h(owned)e(by)h(other)f(threads.)-35 177 y(The)19 b(protocol)d(prevent\
s)i(deadlock,)i(and)e(chained)g(blocking.)-35 226 y(The)9 b(underlying)e(idea)
h(of)g(PCP)h(is)f(to)g(ensure)h(that)f(when)g(a)h(thread)-35 276 y fk(T)h fo
(preempts)h(the)f(critical)g(section)g(of)g(another)g(thread)g fk(S)g fo(and)
g(ex-)-35 326 y(ecutes)17 b(its)e(own)h(critical)f(section)h fk(CS)p fo(,)h
(the)f(priority)e(at)i(which)-35 376 y fk(CS)e fo(will)g(be)h(executed)h(is)e
(guaranteed)h(to)g(be)g(higher)f(than)g(the)-35 426 y(inherited)9 b(prioritie\
s)f(of)i(all)g(the)g(preempted)h(critical)e(sections.)-118 510 y fg(Restartab\
le)h(Critical)g(Section)g(protocol)g(\(RCS\):)20 b fo(RCS)13 b(policy)g(is)
-35 559 y(based)j(on)f(the)g(restartable)h(mode.)31 b(In)15 b(RCS,)g(a)h(high\
er)f(prior-)-35 609 y(ity)g(thread)h(is)g(able)h(to)e(abort)h(the)g(current)g
(running)f(thread)h(in)-35 659 y(the)d(critical)h(section)f(and)h(puts)f(it)g
(back)h(to)f(the)h(waiting)e(queue)-35 709 y(with)h(recovering)h(the)g(state)
g(of)g(shared)g(variable.)27 b(During)12 b(the)-35 759 y(recovery)m(,)j(the)e
(higher)f(priority)f(thread')m(s)j(priority)d(is)i(inherited)-35 808 y(like)h
(in)f(priority)f(inheritance)i(protocol.)26 b(After)14 b(this)g(recovery)-35
858 y(action,)c(the)f(higher)g(priority)f(thread)h(can)i(enter)f(the)f(critic\
al)g(sec-)-35 908 y(tion)14 b(without)f(any)i(waiting)f(in)g(the)h(queue.)30 b
(A)15 b(user)g(program)-35 958 y(must)8 b(be)i(responsible)d(to)i(recover)g
(the)f(state)h(of)g(shared)g(variable.)-77 1042 y(Each)j(synchronization)c
(protocol)g(has)j(a)f(dif)o(ferent)g(characteristics)-118 1091 y(for)g(schedu\
lability)g(and)h(a)g(dif)o(ferent)g(cost)g(to)f(enter)h(to)g(and)g(exit)f(fro\
m)-118 1141 y(critical)15 b(sections.)31 b(In)15 b(the)g(following)e(section,)
k(we)f(will)e(show)h(the)-118 1191 y(dif)n(ference)i(between)e(synchronizatio\
n)f(protocols.)28 b(The)16 b(result)e(al-)-118 1241 y(lows)8 b(application)f
(programmer)i(to)g(select)g(suitable)f(synchronization)-118 1291 y(protocols)
h(for)h(their)f(applications.)-118 1410 y fh(2.3)50 b(Real-T)o(ime)13 b(Synch\
r)n(onization)e(Analysis)-118 1489 y fo(Analyzing)h(the)h(schedulable)g(bound)
f(for)g(real-time)h(tasks)g(is)g(a)g(very)-118 1538 y(dif)n(\256cult)i(proble\
m.)30 b(W)m(e)15 b(have)h(developed)f(a)h(simple)f(yet)g(very)g(ap-)-118 1588
y(plicable)9 b(scheme)j(for)d(analyzing)g(real-time)h(periodic)f(threads)h
(which)-118 1638 y(are)h(synchronizing)e(in)g(a)i(single)f(processor)g(enviro\
nment)750 1623 y fi(1)765 1638 y fo(.)-77 1688 y(T)n(o)h(compute)g(a)h(schedu\
lable)f(bound,)f(we)i(must)f(avoid)f(a)i(potential)-118 1738 y(unbounded)6 b
(priority)g(inversion)g(problem)h(among)h(real-time)g(threads.)-118 1788 y
(Once)15 b(we)g(could)f(bound)f(the)h(worst)g(case)i(blocking)d(time,)j(then)
e(we)-118 1837 y(can)i(compute)g(a)h(bound)d(as)j(an)f(extension)f(of)g(the)h
fn(rate)g(monotonic)-118 1887 y fo(scheduling)9 b(analysis)h([8].)-77 1937 y
(There)j(are)f(basically)g(two)f(approaches)h(to)g(bound)e(the)i(worst)f(case)
-118 1987 y(blocking)d(time)h(among)h(real-time)f(tasks.)15 b(One)10 b(is)f
(using)g(a)h fn(kernelized)-118 2037 y(monitor)i fo(protocol)g(and)i(the)g
(other)f(is)g(using)g(a)h fn(priority)f(inheritance)-118 2087 y fo(scheme)f
(as)f(we)f(described)h(in)f(the)g(previous)f(section.)-77 2137 y(In)i(the)f
(kernelized)g(monitor)g(protocol,)f(while)h(a)h(task)f(is)h(executing)-118
2187 y(in)g(a)i(critical)f(section,)g(the)g(system)h(will)e(not)g(allow)h(any)
g(preemption)-118 2236 y(of)d(that)f(task.)15 b(Suppose)9 b(that)g(if)f fk
(n)h fo(tasks)g(are)h(scheduled)g(in)e(the)h(earliest)-118 2286 y(deadline)f
(\256rst)g(order)n(,)h(the)f(worst)g(case)i(schedulable)f(bound)e(is)h(de\256\
ned)-118 2336 y(as)j(follow)l(.)314 2400 y fj(n)291 2412 y ff(X)302 2502 y fj
(j)p fi(=1)356 2431 y fj(C)375 2435 y fe(j)383 2431 y fi(+)p fj(CS)356 2442 y
78 2 v 383 2466 a(T)399 2470 y fe(j)450 2452 y fd(\024)h fo(1)-118 2587 y(whe\
re)21 b fk(C)32 2593 y fj(i)42 2587 y fo(,)j fk(T)99 2593 y fj(i)109 2587 y fo
(,)g fk(CS)c fo(represents)h(the)f(total)g(computation)f(time)i(of)-118 2636 y
fk(Thread)2 2642 y fj(i)12 2636 y fo(,)16 b(the)e(period)g(of)g fk(Thread)393
2642 y fj(i)404 2636 y fo(,)i(and)e(the)h(worst)f(case)i(execution)-118 2673 y
417 2 v -73 2701 a fm(1)-58 2713 y fl(For)7 b(a)h(multiprocessor)e(case,)h
(a)g(simple)g(priority)g(inheritance)f(case)h(may)g(not)g(work)-118 2752 y
(and)g(further)h(extensions)e(are)i(necessary)n(.)i(Please)f(refer[10)n(].)
966 77 y fo(time)h(of)g(the)h(critical)e(section)i(respectively)m(.)16 b(In)
10 b(general,)h(if)f(the)g(dura-)966 127 y(tion)5 b(of)i(CS)g(is)g(too)f(big,)
h(the)g(system)h(cannot)f(satisfy)f(the)h(schedulability)966 177 y(test)j(and)
h(end)g(up)f(with)g(reducing)g(the)h(number)f(of)h(tasks)g(and)g(running)966
226 y(with)e(a)i(very)f(low)f(total)h(processor)g(utilization.)1007 278 y(On)
15 b(the)g(other)f(hand,)i(if)e(we)i(relax)f(the)g(kernelized)f(monitor)g(and)
966 328 y(allow)h(a)j(preemption)d(during)g(the)i(critical)e(section,)k(we)e
(may)g(face)966 378 y(the)f(unbounded)f(priority)f(inversion)h(problem.)33 b
(Under)16 b(a)h(priority)966 428 y(inheritance)g(scheme,)22 b(once)c(the)g
(higher)f(priority)f(task)i(blocks)f(on)966 478 y(the)d(critical)g(section,)h
(the)g(low)e(priority)f(task)j(will)e(inherit)g(the)h(high)966 527 y(priority)
8 b(from)i(the)g(higher)g(priority)e(task.)16 b(One)11 b(of)f(extended)g(prio\
rity)966 577 y(inheritance)f(protocols)g(is)h(called)h(a)g fn(priority)e(ceil\
ing)g(pr)o(otocol)p fo([10)n(].)1007 629 y(Using)17 b(these)h(inheritance)f
(protocols)g(under)g(a)h(rate)g(monotonic)966 679 y(policy)l(,)h(we)f(can)f
(also)g(check)h(schedulable)f(bound)f(for)h fk(n)g fo(periodic)966 729 y(thre\
ads)10 b(as)h(follows.)1148 848 y fd(8)p fk(i)p fc(;)6 b fo(1)11 b fd(\024)h
fk(i)f fd(\024)h fk(n)p fc(;)1447 831 y fj(B)1465 835 y fe(i)1447 839 y 26 2 v
1448 862 a fj(T)1464 866 y fe(i)1487 848 y fo(+)1545 796 y fj(i)1519 809 y ff
(X)1530 898 y fj(j)p fi(=1)1584 827 y fj(C)1603 831 y fe(j)1584 839 y 28 2 v
1586 862 a fj(T)1602 866 y fe(j)1628 848 y fd(\024)g fk(i)p fo(\(2)1723 822 y
fb(1)1723 827 y 11 2 v 1725 843 a fe(i)1750 848 y fd(\000)d fo(1\))966 980 y
(where)j fk(C)1107 986 y fj(i)1117 980 y fo(,)i fk(T)1164 986 y fj(i)1174 980
y fo(,)f fk(B)1222 986 y fj(i)1245 980 y fo(represents)g(the)f(total)f(comput\
ation)g(time,)i(the)f(pe-)966 1030 y(riod,)d(and)i(the)f(worst)f(case)j(block\
ing)d(time)h(of)g fk(Thread)1774 1036 y fj(i)1794 1030 y fo(respectively)m
(.)1007 1082 y(Restartable)f(critical)g(section)g(protocol)f(makes)j(the)e
(blocking)f(time)966 1132 y(to)13 b(be)g(smallest)h(among)g(the)f(proposed)g
(protocols,)g(if)g(abort)g(and)h(re-)966 1181 y(covery)e(overhead)h(is)f(negl\
igible.)19 b(The)13 b(schedulability)e(formula)g(for)966 1231 y(restartable)d
(critical)g(section)g(is)g(similar)g(to)g(the)g(formula)g(for)g(the)g(prior-)
966 1281 y(ity)j(ceiling)g(protocol.)18 b(The)13 b(dif)n(ference)g(is)f(that)
f fk(B)1710 1287 y fj(i)1733 1281 y fo(should)g(represent)966 1331 y(the)f
(abort)f(and)h(recovery)h(time)f(when)g(using)f(restartable)i(critical)e(sec-)
966 1381 y(tion.)966 1532 y fr(3)59 b(Implementation)966 1629 y fo(The)10 b
(current)g(version)f(of)h(Real-T)o(ime)g(Mach)h(is)f(being)f(developed)h(us-)
966 1678 y(ing)h(a)h(network)f(of)h(SUN,)g(SONY)g(workstations,)f(laptop)g
(and)h(single)966 1728 y(board)i(tar)o(get)h(machines.)29 b(The)16 b(pure)e
(kernel)h(provided)e(us)i(a)g(better)966 1778 y(execution)10 b(environment)g
(where)h(we)g(could)f(reduce)i(unexpected)f(de-)966 1828 y(lays)i(in)h(the)f
(kernel.)26 b(The)15 b(preemptability)d(of)h(the)h(kernel)g(was)g(also)966
1878 y(improved)8 b(signi\256cantly)f(since)j(UNIX)f(primitives)f(and)h(some)
h(device)966 1927 y(drivers)g(are)i(no)f(longer)g(in)f(the)h(kernel.)18 b(In)
11 b(this)g(section,)g(we)h(will)e(de-)966 1977 y(scribe)g(the)f(extended)h
(system)g(interface)g(for)g(real-time)f(synchroniza-)966 2027 y(tion)15 b(and)
i(the)g(implementation)e(of)i(synchronization)e(mechanisms)966 2077 y(and)10 b
(policy)f(modules.)966 2207 y fh(3.1)50 b(System)12 b(Interface)g(for)g(Synch\
r)o(onization)966 2289 y fo(The)g(synchronization)f(mechanism)i(is)f(based)h
(on)e(mutual)h(exclusion)966 2338 y(with)g(a)i(lock)f(variable)1317 2323 y fi
(2)1334 2338 y fo(.)25 b(A)14 b(thread)f(can)h(allocate,)h(deallocate,)g(and)
966 2388 y(initialize)7 b(a)i(lock)f(variable)h(with)e(a)i(suitable)f fn(lock)
h(attribute)p fo(.)k(The)c(lock)966 2438 y(attribute)k(speci\256es)j(a)f(sync\
hronization)f(policy)f(which)i(determines)966 2488 y(its)9 b(queueing)h(and)g
(priority)e(ordering.)1007 2540 y(A)15 b(simple)g(pair)f(of)g fn(rt)s 13 2 v
12 w(mutex)s 13 2 v 12 w(lock)h fo(and)g fn(rt)r 13 2 v 13 w(mutex)r 13 2 v 13
w(unlock)f fo(primi-)966 2590 y(tives)9 b(is)h(used)h(to)e(specify)h(mutual)g
(exclusion.)k(The)d fn(rt)r 13 2 v 13 w(mutex)r 13 2 v 13 w(trylock)966 2634 y
417 2 v 1011 2661 a fm(2)1025 2673 y fl(W)m(e)19 b(have)f(also)f(created)h
(event-based)e(primitives:)32 b fa(rt)r 10 2 v 10 w(event)r 10 2 v 10 w(send)
p fl(\()19 b(event,)966 2713 y(event)q 10 2 v 10 w(attr)12 b(\),)h fa(rt)r 10
2 v 10 w(event)q 10 2 v 10 w(r)o(eceive)p fl(\()e(event,)h(event)q 10 2 v 10 w
(attr)o(,)i(timeout)d(\).)23 b(However)o(,)12 b(we)g(do)966 2752 y(not)7 b
(describe)g(these)h(primitives)g(in)g(this)g(paper)n(.)935 2877 y fo( )p eop
eos end TeXDict begin bos 300 @start /fa df[<60F0F060>4 4 3 -7 11]1 dc[<030003
0003000300E31C73381FE0078007801FE07338E31C0300030003000300>14 16 2 -1 19]3 dc[
<007001C0038007000700070007000700070007000700070007000700070007000E001C00F000
1C000E000700070007000700070007000700070007000700070007000700038001C00070>12 37
3 9 19]102 dc[<F0001C000E0007000700070007000700070007000700070007000700070007
00038001C0007001C0038007000700070007000700070007000700070007000700070007000E00
1C00F000>12 37 3 9 19]103 dc dfe /fb 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 9 12 21 19 19 37 31 12 12 12 19 21 9 12 9 10 19 19 19 19
19 19 19 19 19 19 12 12 21 21 21 19 35 27 25 27 27 25 23 29 29 15 19 29 25 35
27 29 23 29 27 21 25 27 27 37 27 27 25 12 10 12 22 19 12 19 21 17 21 17 12 19
21 10 12 21 10 31 21 19 21 21 17 15 12 21 19 27 19 19 17 15 8 15 19 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12 19 19 6 19 19 19
19 10 19 19 12 12 21 21 0 19 19 19 9 0 20 13 12 19 19 19 37 37 0 19 0 12 12 12
12 12 12 12 12 0 12 12 0 12 12 12 37 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 37 0 11 0
0 0 0 25 29 37 12 0 0 0 0 0 27 0 0 0 10 0 0 10 19 27 21 0 0 0 0 /Times-Bold
1000 589824 rf /fc 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 9 12 15 19 19 31 29 12 12 12 19 21 9 12 9 10 19 19 19 19 19 19 19 19 19 19
10 10 21 21 21 17 34 27 25 25 27 23 21 27 27 12 15 27 23 33 27 27 21 27 25 21
23 27 27 35 27 27 23 12 10 12 18 19 12 17 19 17 19 17 12 19 19 10 10 19 10 29
19 19 19 19 12 15 10 19 19 27 19 19 17 18 7 18 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12 19 19 6 19 19 19 19 7 17 19 12 12
21 21 0 19 19 19 9 0 17 13 12 17 17 19 37 37 0 17 0 12 12 12 12 12 12 12 12 0
12 12 0 12 12 12 37 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 33 0 10 0 0 0 0 23 27 33
12 0 0 0 0 0 25 0 0 0 10 0 0 10 19 27 19 0 0 0 0 /Times-Roman 1000 589824 rf
/fd df[<0180300380700380700380700700E00700E00700E00700E00E01C00E01C00E01C00E01
C01C03881C03881C03881E07883E19903BE0E0380000380000700000700000700000700000E000
00E00000C00000>21 27 1 9 25]22 dc dfe /fe 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 14 23 21 21 42 35 14 14 14 21 24 10 14 10 12 21
21 21 21 21 21 21 21 21 21 14 14 24 24 24 21 39 30 28 30 30 28 25 32 32 16 21
32 28 39 30 32 25 32 30 23 28 30 30 42 30 30 28 14 12 14 24 21 14 21 23 18 23
18 14 21 23 12 14 23 12 35 23 21 23 23 18 16 14 23 21 30 21 21 18 16 9 16 22 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14 21 21 7
21 21 21 21 12 21 21 14 14 23 23 0 21 21 21 10 0 22 15 14 21 21 21 42 42 0 21
0 14 14 14 14 14 14 14 14 0 14 14 0 14 14 14 42 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 42 0 12 0 0 0 0 28 32 42 14 0 0 0 0 0 30 0 0 0 12 0 0 12 21 30 23 0 0 0 0
/Times-Bold 1000 655360 rf /ff 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 12 17 28 25 25 50 41 17 17 17 25 28 12 17 12 14 25 25 25 25 25
25 25 25 25 25 17 17 28 28 28 25 46 36 33 36 36 33 30 39 39 19 25 39 33 47 36
39 30 39 36 28 33 36 36 50 36 36 33 17 14 17 29 25 17 25 28 22 28 22 17 25 28
14 17 28 14 41 28 25 28 28 22 19 17 28 25 36 25 25 22 20 11 20 26 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 25 25 8 25 25 25 25
14 25 25 17 17 28 28 0 25 25 25 12 0 27 17 17 25 25 25 50 50 0 25 0 17 17 17
17 17 17 17 17 0 17 17 0 17 17 17 50 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 50 0 15 0
0 0 0 33 39 50 16 0 0 0 0 0 36 0 0 0 14 0 0 14 25 36 28 0 0 0 0 /Times-Bold
1000 786432 rf /fg 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 10 12 15 15 24 23 10 10 10 15 20 7 10 7 8 15 15 15 15 15 15 15 15 15 15
10 10 20 20 20 15 27 18 18 19 21 18 18 21 21 10 13 19 16 24 19 21 18 21 18 15
16 21 18 24 18 16 16 11 8 11 12 15 10 15 15 13 15 13 14 15 15 8 8 13 8 21 15
15 15 15 11 11 8 15 13 19 13 13 11 12 8 12 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 15 15 5 15 15 15 15 6 16 15 10 10 15 15
0 15 15 15 7 0 15 10 10 16 16 15 26 29 0 15 0 10 10 10 10 10 10 10 10 0 10 10
0 10 10 10 26 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 26 0 8 0 0 0 0 16 21 27 9 0 0 0
0 0 19 0 0 0 8 0 0 8 15 19 15 0 0 0 0 /Times-Italic-Math
/Times-Italic 1.0 ExtendFont 1000 458752 rf /fh 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14 17 21 21 35 32 14 14 14 21 28 10 14 10
12 21 21 21 21 21 21 21 21 21 21 14 14 28 28 28 21 38 25 25 28 30 25 25 30 30
14 18 28 23 35 28 30 25 30 25 21 23 30 25 35 25 23 23 16 12 16 18 21 14 21 21
18 21 18 20 21 21 12 12 18 12 30 21 21 21 21 16 16 12 21 18 28 18 18 16 17 11
17 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16
21 21 7 21 21 21 21 9 23 21 14 14 21 21 0 21 21 21 10 0 22 15 14 23 23 21 37
42 0 21 0 14 14 14 14 14 14 14 14 0 14 14 0 14 14 14 37 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 37 0 11 0 0 0 0 23 30 39 13 0 0 0 0 0 28 0 0 0 12 0 0 12 21 28 21 0
0 0 0 /Times-Italic-Math /Times-Italic 1.0 ExtendFont 1000 655360 rf /fi 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 14 17 21 21 35 32
14 14 14 21 28 10 14 10 12 21 21 21 21 21 21 21 21 21 21 14 14 28 28 28 21 38
25 25 28 30 25 25 30 30 14 18 28 23 35 28 30 25 30 25 21 23 30 25 35 25 23 23
16 12 16 18 21 14 21 21 18 21 18 12 21 21 12 12 18 12 30 21 21 21 21 16 16 12
21 18 28 18 18 16 17 11 17 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 16 21 21 7 21 21 21 21 9 23 21 14 14 21 21 0 21 21 21 10 0
22 15 14 23 23 21 37 42 0 21 0 14 14 14 14 14 14 14 14 0 14 14 0 14 14 14 37 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 37 0 11 0 0 0 0 23 30 39 13 0 0 0 0 0 28 0 0 0
12 0 0 12 21 28 21 0 0 0 0 /Times-Italic 1000 655360 rf /fj 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 14 17 21 21 35 32 14 14 14 21
23 10 14 10 12 21 21 21 21 21 21 21 21 21 21 12 12 23 23 23 18 38 30 28 28 30
25 23 30 30 14 16 30 25 37 30 30 23 30 28 23 25 30 30 39 30 30 25 14 12 14 19
21 14 18 21 18 21 18 14 21 21 12 12 21 12 32 21 21 21 21 14 16 12 21 21 30 21
21 18 20 8 20 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 14 21 21 7 21 21 21 21 7 18 21 14 14 23 23 0 21 21 21 10 0 19 15 14 18
18 21 42 42 0 18 0 14 14 14 14 14 14 14 14 0 14 14 0 14 14 14 42 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 37 0 11 0 0 0 0 25 30 37 13 0 0 0 0 0 28 0 0 0 12 0 0 12 21
30 21 0 0 0 0 /Times-Roman 1000 655360 rf /fk 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 20 33 30 30 60 50 20 20 20 30 34 15 20 15
17 30 30 30 30 30 30 30 30 30 30 20 20 34 34 34 30 56 43 40 43 43 40 37 47 47
23 30 47 40 56 43 47 37 47 43 33 40 43 43 60 43 43 40 20 17 20 35 30 20 30 33
27 33 27 20 30 33 17 20 33 17 50 33 30 33 33 27 23 20 33 30 43 30 30 27 24 13
24 31 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20
30 30 10 30 30 30 30 17 30 30 20 20 33 33 0 30 30 30 15 0 32 21 20 30 30 30 60
60 0 30 0 20 20 20 20 20 20 20 20 0 20 20 0 20 20 20 60 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 60 0 18 0 0 0 0 40 47 60 20 0 0 0 0 0 43 0 0 0 17 0 0 17 30 43 33 0
0 0 0 /Times-Bold 1000 943718 rf end
 TeXDict begin @letter
%%Page: 4 4
 bop -118 77 a fj(primitive)9 b(is)h(used)h(for)g(acquiring)e(the)i(lock)f
(conditionally)-6 b(.)17 b(A)11 b(modi-)-118 127 y(\256ed)d(version)f(of)g
(the)g(condition)f(variable)h(is)g(also)h(supported)e(for)h(speci-)-118 177 y
(fying)g(a)i(conditional)d(critical)h(region.)14 b(A)8 b(pair)g(of)g fi(rt)r
13 2 v 13 w(condition)p 13 2 v 13 w(signal)-118 226 y fj(and)k fi(rt)r 13 2 v
13 w(condition)p 13 2 v 13 w(wait)f fj(primitives)f(is)i(used)h(to)f(synchron\
ize)g(over)g(a)-118 276 y(condition)c(variable.)-77 327 y(The)15 b(interface)
f(of)f(the)h(synchronization)e(functions)g(and)i(lock)f(at-)-118 376 y(tribut\
e)c(are)i(summarized)g(as)g(follows.)-59 520 y(kval)r 13 2 v 12 w(t)f(=)h fe
(rt)s 13 2 v 12 w(mutex)r 13 2 v 13 w(allocate)p fj(\(lock,)e(lock)r 13 2 v 12
w(attr\))-59 570 y(kval)r 13 2 v 12 w(t)h(=)h fe(rt)s 13 2 v 12 w(mutex)r 13 2
v 13 w(deallocate)p fj(\(lock\))-59 620 y(kval)r 13 2 v 12 w(t)f(=)h fe(rt)s
13 2 v 12 w(mutex)r 13 2 v 13 w(lock)p fj(\(lock,)f(timeout,)f(context\))-59
669 y(kval)r 13 2 v 12 w(t)h(=)h fe(rt)s 13 2 v 12 w(mutex)r 13 2 v 13 w(unlo\
ck)p fj(\(lock\))-59 719 y(kval)r 13 2 v 12 w(t)f(=)h fe(rt)s 13 2 v 12 w(mut\
ex)r 13 2 v 13 w(trylock)p fj(\(lock\))-59 769 y(kval)r 13 2 v 12 w(t)f(=)h fe
(rt)s 13 2 v 12 w(condition)r 13 2 v 12 w(allocate)p fj(\(cond,)f(cond)r 13 2
v 12 w(attr\))-59 819 y(kval)r 13 2 v 12 w(t)g(=)h fe(rt)s 13 2 v 12 w(condit\
ion)r 13 2 v 12 w(deallocate)p fj(\(cond\))-59 869 y(kval)r 13 2 v 12 w(t)f
(=)h fe(rt)s 13 2 v 12 w(condition)r 13 2 v 12 w(wait)p fj(\(cond,)f(lock,)g
(cond)r 13 2 v 13 w(attr)m(,)h(timeout\))-59 919 y(kval)r 13 2 v 12 w(t)f(=)h
fe(rt)s 13 2 v 12 w(condition)r 13 2 v 12 w(signal)p fj(\(cond,)e(cond)s 13 2
v 12 w(attr\))-59 1059 y fc(typedef)f(struct)i fb(lock)q 12 2 v 12 w(attr)f fa
(f)0 1104 y fc(type)r 12 2 v 11 w(t)148 b(rt)s 12 2 v 11 w(type;)125 b(/)p fa
(\003)10 b fc(lock)f(type)g fa(\003)p fc(/)0 1150 y(priority)s 12 2 v 12 w
(t)100 b(rt)s 12 2 v 11 w(priority;)79 b(/)p fa(\003)10 b fc(ceiling)f(priori\
ty)i fa(\003)p fc(/)236 1196 y fa(\001)6 b(\001)g(\001)-59 1241 y(g)j fc(lock)
r 12 2 v 11 w(attr)s 12 2 v 12 w(t;)-59 1333 y(typedef)f(struct)i fb(cond)q 12
2 v 11 w(attr)f fa(f)0 1378 y fc(type)r 12 2 v 11 w(t)148 b(rt)s 12 2 v 11 w
(type;)125 b(/)p fa(\003)10 b fc(condition)f(variable)g(type)f fa(\003)p fc
(/)0 1424 y(priority)s 12 2 v 12 w(t)100 b(rt)s 12 2 v 11 w(priority;)79 b
(/)p fa(\003)10 b fc(for)g(priority)h(inheritance)d fa(\003)p fc(/)236 1470 y
fa(\001)e(\001)g(\001)-59 1515 y(g)j fc(cond)q 12 2 v 12 w(attr)s 12 2 v 11 w
(t;)-118 1654 y fi(rt)r 13 2 v 13 w(type)15 b fj(indicates)f(a)h(lock)g(polic\
y)e(given)i(by)f(a)h(user)n(.)29 b fi(rt)r 13 2 v 13 w(priority)13 b fj(is)
-118 1704 y(used)h(for)f(the)h(ceiling)e(protocol)h(and)g(speci\256es)i(the)f
(ceiling)f(priority)-118 1754 y(of)f(the)f(lock.)21 b(If)11 b(NULL)i(value)f
(is)g(set)g(as)h(a)f(lock)g(attribute,)f(a)i(default)-118 1804 y(policy)f(\(i\
.e.,)i(BP)-5 b(,)13 b(basic)g(priority)e(policy\))g(is)i(chosen.)23 b(In)12 b
fi(cond)r 13 2 v 13 w(attr)p fj(,)-118 1854 y fi(rt)r 13 2 v 13 w(type)g fj
(indicates)f(the)h(type)f(of)h(condition)d(variable,)k(and)f fi(rt)r 13 2 v 12
w(priority)-118 1903 y fj(is)e(used)g(for)g(priority)e(inheritance.)-118 2025
y ff(3.2)50 b(Synchr)n(onization)11 b(Module)-118 2103 y fj(The)i(synchroniza\
tion)d(facility)h(is)g(implemented)h(based)h(on)e(the)h(pol-)-118 2153 y(icy/\
mechanism)d(separation)g(concept)f(for)h(improving)e(the)h(adaptabil-)-118
2203 y(ity)k(of)g(the)h(system.)23 b(Each)14 b(synchronization)d(policy)g(mod\
ule)i(is)f(im-)-118 2253 y(plemented)e(as)h(an)g(object)f(\(or)g(an)h(abstrac\
t)f(data)h(type\).)k(The)c(commu-)-118 2303 y(nication)d(between)h(the)g(poli\
cy)e(object)i(and)g(its)f(mechanism)i(was)f(done)-118 2353 y(through)f(functi\
on)h(calls,)i(not)e(message)j(passing.)-77 2403 y(The)d(synchronization)d(mod\
ule)h(is)g(divided)g(into)f(the)i(common)g(lock)-118 2453 y(object)i(and)g
(lock)g(policy)f(objects.)15 b(Figure)10 b(1)g(shows)g(the)g(relationship)
-118 2502 y(between)k(the)f(common)h(lock)f(object)g(and)h(various)e(lock)h
(policy)g(ob-)-118 2552 y(jects.)19 b(Only)10 b(one)i(common)g(lock)e(object)
h(is)h(created,)h(while)d(the)i(lock)-118 2602 y(policy)h(object)i(is)f(creat\
ed)i(for)e(each)i(lock)e(object)g(and)h(controls)e(the)-118 2652 y(priority)8
b(of)i(the)g(thread)g(which)g(is)g(holding)e(the)i(lock)g(object.)-77 2702 y
(The)f(common)f(lock)f(object)g(of)o(fers)h(the)g(mechanism)g(to)g(manage)g
(the)-118 2752 y(blocking)g(and)j(unblocking)d(of)i(threads)g(for)f(exclusive)
h(access)j(It)c(also)966 35 y @beginspecial -30 @hoffset -330 @voffset
0.600000 @hscale 0.600000 @vscale @setspecial
%%BeginDocument: sync.ps

50 dict begin

/arrowHeight 8 def
/arrowWidth 4 def
/none null def
/numGraphicParameters 17 def
/stringLimit 65535 def

/Begin {
save
numGraphicParameters dict begin
} def

/End {
end
restore
} def

/SetB {
dup type /nulltype eq {
pop
false /brushRightArrow idef
false /brushLeftArrow idef
true /brushNone idef
} {
/brushDashOffset idef
/brushDashArray idef
0 ne /brushRightArrow idef
0 ne /brushLeftArrow idef
/brushWidth idef
false /brushNone idef
} ifelse
} def

/SetCFg {
/fgblue idef
/fggreen idef
/fgred idef
} def

/SetCBg {
/bgblue idef
/bggreen idef
/bgred idef
} def

/SetF {
/printSize idef
/printFont idef
} def

/SetP {
dup type /nulltype eq {
pop true /patternNone idef
} {
/patternGrayLevel idef
patternGrayLevel -1 eq {
/patternString idef
} if
false /patternNone idef
} ifelse
} def

/BSpl {
0 begin
storexyn
newpath
n 1 gt {
0 0 0 0 0 0 1 1 true subspline
n 2 gt {
0 0 0 0 1 1 2 2 false subspline
1 1 n 3 sub {
/i exch def
i 1 sub dup i dup i 1 add dup i 2 add dup false subspline
} for
n 3 sub dup n 2 sub dup n 1 sub dup 2 copy false subspline
} if
n 2 sub dup n 1 sub dup 2 copy 2 copy false subspline
patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if
brushNone not { istroke } if
0 0 1 1 leftarrow
n 2 sub dup n 1 sub dup rightarrow
} if
end
} dup 0 4 dict put def

/Circ {
newpath
0 360 arc
patternNone not { ifill } if
brushNone not { istroke } if
} def

/CBSpl {
0 begin
dup 2 gt {
storexyn
newpath
n 1 sub dup 0 0 1 1 2 2 true subspline
1 1 n 3 sub {
/i exch def
i 1 sub dup i dup i 1 add dup i 2 add dup false subspline
} for
n 3 sub dup n 2 sub dup n 1 sub dup 0 0 false subspline
n 2 sub dup n 1 sub dup 0 0 1 1 false subspline
patternNone not { ifill } if
brushNone not { istroke } if
} {
Poly
} ifelse
end
} dup 0 4 dict put def

/Elli {
0 begin
newpath
4 2 roll
translate
scale
0 0 1 0 360 arc
patternNone not { ifill } if
brushNone not { istroke } if
end
} dup 0 1 dict put def

/Line {
0 begin
2 storexyn
newpath
x 0 get y 0 get moveto
x 1 get y 1 get lineto
brushNone not { istroke } if
0 0 1 1 leftarrow
0 0 1 1 rightarrow
end
} dup 0 4 dict put def

/MLine {
0 begin
storexyn
newpath
n 1 gt {
x 0 get y 0 get moveto
1 1 n 1 sub {
/i exch def
x i get y i get lineto
} for
patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if
brushNone not { istroke } if
0 0 1 1 leftarrow
n 2 sub dup n 1 sub dup rightarrow
} if
end
} dup 0 4 dict put def

/Poly {
3 1 roll
newpath
moveto
-1 add
{ lineto } repeat
closepath
patternNone not { ifill } if
brushNone not { istroke } if
} def

/Rect {
0 begin
/t exch def
/r exch def
/b exch def
/l exch def
newpath
l b moveto
l t lineto
r t lineto
r b lineto
closepath
patternNone not { ifill } if
brushNone not { istroke } if
end
} dup 0 4 dict put def

/Text {
ishow
} def

/idef {
dup where { pop pop pop } { exch def } ifelse
} def

/ifill {
0 begin
gsave
patternGrayLevel -1 ne {
fgred bgred fgred sub patternGrayLevel mul add
fggreen bggreen fggreen sub patternGrayLevel mul add
fgblue bgblue fgblue sub patternGrayLevel mul add setrgbcolor
eofill
} {
eoclip
originalCTM setmatrix
pathbbox /t exch def /r exch def /b exch def /l exch def
/w r l sub ceiling cvi def
/h t b sub ceiling cvi def
/imageByteWidth w 8 div ceiling cvi def
/imageHeight h def
bgred bggreen bgblue setrgbcolor
eofill
fgred fggreen fgblue setrgbcolor
w 0 gt h 0 gt and {
l b translate w h scale
w h true [w 0 0 h neg 0 h] { patternproc } imagemask
} if
} ifelse
grestore
end
} dup 0 8 dict put def

/istroke {
gsave
brushDashOffset -1 eq {
[] 0 setdash
1 setgray
} {
brushDashArray brushDashOffset setdash
fgred fggreen fgblue setrgbcolor
} ifelse
brushWidth setlinewidth
originalCTM setmatrix
stroke
grestore
} def

/ishow {
0 begin
gsave
fgred fggreen fgblue setrgbcolor
/fontDict printFont findfont printSize scalefont dup setfont def
/descender fontDict begin 0 [FontBBox] 1 get FontMatrix end
transform exch pop def
/vertoffset 0 descender sub printSize sub printFont /Courier ne
printFont /Courier-Bold ne and { 1 add } if def {
0 vertoffset moveto show
/vertoffset vertoffset printSize sub def
} forall
grestore
end
} dup 0 3 dict put def

/patternproc {
0 begin
/patternByteLength patternString length def
/patternHeight patternByteLength 8 mul sqrt cvi def
/patternWidth patternHeight def
/patternByteWidth patternWidth 8 idiv def
/imageByteMaxLength imageByteWidth imageHeight mul
stringLimit patternByteWidth sub min def
/imageMaxHeight imageByteMaxLength imageByteWidth idiv patternHeight idiv
patternHeight mul patternHeight max def
/imageHeight imageHeight imageMaxHeight sub store
/imageString imageByteWidth imageMaxHeight mul patternByteWidth add string def
0 1 imageMaxHeight 1 sub {
/y exch def
/patternRow y patternByteWidth mul patternByteLength mod def
/patternRowString patternString patternRow patternByteWidth getinterval def
/imageRow y imageByteWidth mul def
0 patternByteWidth imageByteWidth 1 sub {
/x exch def
imageString imageRow x add patternRowString putinterval
} for
} for
imageString
end
} dup 0 12 dict put def

/min {
dup 3 2 roll dup 4 3 roll lt { exch } if pop
} def

/max {
dup 3 2 roll dup 4 3 roll gt { exch } if pop
} def

/arrowhead {
0 begin
transform originalCTM itransform
/taily exch def
/tailx exch def
transform originalCTM itransform
/tipy exch def
/tipx exch def
/dy tipy taily sub def
/dx tipx tailx sub def
/angle dx 0 ne dy 0 ne or { dy dx atan } { 90 } ifelse def
gsave
originalCTM setmatrix
tipx tipy translate
angle rotate
newpath
0 0 moveto
arrowHeight neg arrowWidth 2 div lineto
arrowHeight neg arrowWidth 2 div neg lineto
closepath
patternNone not {
originalCTM setmatrix
/padtip arrowHeight 2 exp 0.25 arrowWidth 2 exp mul add sqrt brushWidth mul
arrowWidth div def
/padtail brushWidth 2 div def
tipx tipy translate
angle rotate
padtip 0 translate
arrowHeight padtip add padtail add arrowHeight div dup scale
arrowheadpath
ifill
} if
brushNone not {
originalCTM setmatrix
tipx tipy translate
angle rotate
arrowheadpath
istroke
} if
grestore
end
} dup 0 9 dict put def

/arrowheadpath {
newpath
0 0 moveto
arrowHeight neg arrowWidth 2 div lineto
arrowHeight neg arrowWidth 2 div neg lineto
closepath
} def

/leftarrow {
0 begin
y exch get /taily exch def
x exch get /tailx exch def
y exch get /tipy exch def
x exch get /tipx exch def
brushLeftArrow { tipx tipy tailx taily arrowhead } if
end
} dup 0 4 dict put def

/rightarrow {
0 begin
y exch get /tipy exch def
x exch get /tipx exch def
y exch get /taily exch def
x exch get /tailx exch def
brushRightArrow { tipx tipy tailx taily arrowhead } if
end
} dup 0 4 dict put def

/midpoint {
0 begin
/y1 exch def
/x1 exch def
/y0 exch def
/x0 exch def
x0 x1 add 2 div
y0 y1 add 2 div
end
} dup 0 4 dict put def

/thirdpoint {
0 begin
/y1 exch def
/x1 exch def
/y0 exch def
/x0 exch def
x0 2 mul x1 add 3 div
y0 2 mul y1 add 3 div
end
} dup 0 4 dict put def

/subspline {
0 begin
/movetoNeeded exch def
y exch get /y3 exch def
x exch get /x3 exch def
y exch get /y2 exch def
x exch get /x2 exch def
y exch get /y1 exch def
x exch get /x1 exch def
y exch get /y0 exch def
x exch get /x0 exch def
x1 y1 x2 y2 thirdpoint
/p1y exch def
/p1x exch def
x2 y2 x1 y1 thirdpoint
/p2y exch def
/p2x exch def
x1 y1 x0 y0 thirdpoint
p1x p1y midpoint
/p0y exch def
/p0x exch def
x2 y2 x3 y3 thirdpoint
p2x p2y midpoint
/p3y exch def
/p3x exch def
movetoNeeded { p0x p0y moveto } if
p1x p1y p2x p2y p3x p3y curveto
end
} dup 0 17 dict put def

/storexyn {
/n exch def
/y n array def
/x n array def
n 1 sub -1 0 {
/i exch def
y i 3 2 roll put
x i 3 2 roll put
} for
} def




Begin
[ 0.8 0 0 0.8 0 0 ] concat
/originalCTM matrix currentmatrix def

Begin %I Rect
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 127 210 ] concat
22 418 441 467 Rect
End

Begin %I Rect
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 127 210 ] concat
381 238 431 318 Rect
End

Begin %I Rect
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 127 210 ] concat
311 238 361 318 Rect
End

Begin %I Rect
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 58 210 ] concat
311 238 361 318 Rect
End

Begin %I Rect
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 -11 210 ] concat
311 238 361 318 Rect
End

Begin %I Rect
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 127 210 ] concat
32 238 162 378 Rect
End

Begin %I Elli
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 77 210 ] concat
172 149 30 30 Elli
End

Begin %I Elli
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 67 210 ] concat
281 149 30 30 Elli
End

Begin %I Elli
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 87 210 ] concat
361 149 30 30 Elli
End

Begin %I Text
0 0 0 SetCFg
/Helvetica-Oblique 14 SetF
[ 1 0 0 1 269 658 ] concat
[
(Mutex  Syscall  Interface)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Helvetica-Oblique 14 SetF
[ 1 0 0 1 179 518 ] concat
[
(Common Lock)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Helvetica-Oblique 14 SetF
[ 1 0 0 1 507 362 ] concat
[
(Lock  Objects)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Helvetica-Oblique 14 SetF
[ 1 0 0 1 380 488 ] concat
[
(BPI)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Helvetica-Oblique 14 SetF
[ 1 0 0 1 448 488 ] concat
[
(KM)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Helvetica-Oblique 14 SetF
[ 1 0 0 1 518 488 ] concat
[
(PCP)
] Text
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 127 210 ] concat
102 418 102 378 Line
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 127 210 ] concat
92 238 122 179 Line
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 127 210 ] concat
92 238 212 179 Line
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 127 210 ] concat
92 238 311 179 Line
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 127 210 ] concat
122 179 262 238 Line
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 127 210 ] concat
232 179 331 238 Line
End

Begin %I Line
1 0 1 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 127 210 ] concat
311 179 272 238 Line
End

Begin %I Text
0 0 0 SetCFg
/Helvetica-Oblique 14 SetF
[ 1 0 0 1 202 490 ] concat
[
(Object)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Helvetica-Oblique 14 SetF
[ 1 0 0 1 316 489 ] concat
[
(BP)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Helvetica-Oblique 14 SetF
[ 1 0 0 1 362 573 ] concat
[
(Lock Policy Objects)
] Text
End

End %I eop

showpage


end
%%EndDocument
 @endspecial 1233 856 a(Figure)h(1:)k(Lock)d(Policy)e(Module)966 991 y(manipu\
lates)h(the)h(queues)g(of)f(threads)h(waiting)e(for)h(the)h(releasing)f(the)
966 1040 y(lock)g(according)g(to)g(the)h(current)f(processor)h(scheduling)f
(policy)l(.)16 b(The)966 1090 y(lock)11 b(object)g(up)h(calls)f(its)g(associa\
ted)i(lock)e(policy)g(object.)19 b(Some)12 b(of)966 1140 y(lock)f(policy)g
(objects)h(also)g(controls)f(the)h(thread')m(s)h(ef)o(fective)f(priority)966
1190 y(for)d(controlling)f(a)j(priority)d(inheritance)i(scheme.)966 1305 y fe
(3.2.1)41 b(Interface)12 b(for)e(Policy)g(Contr)o(ol)966 1384 y fj(The)17 b
(policy)f(operations)f(for)i(the)f(lock)h(object)f(are)h(triggered)f(by)g(a)
966 1434 y(system)c(call)h(from)f(a)h(user)n(.)21 b(The)14 b(thread)e(execute\
s)h(these)g(operations)966 1484 y(without)f(blocking.)25 b(If)14 b(the)h(thre\
ad)f(must)g(be)g(blocked)g(inside)g(these)966 1533 y(operations,)9 b(it)h(ret\
urns)g(to)g(the)g(common)g(lock)g(object.)16 b(The)11 b(common)966 1583 y(loc\
k)g(object)g(determines)h(whether)f(to)g(block)g(the)g(thread)g(or)h(not,)f
(and)966 1633 y(re-execute)g(the)f(policy)f(operations.)1007 1684 y(The)j(loc\
k)f(object)g(and)h(policy)e(object)h(provide)f(the)i(following)d(op-)966 1733
y(erations.)1025 1820 y(kval)r 13 2 v 12 w(t)h(=)h fe(rt)s 13 2 v 12 w(mutex)
r 13 2 v 13 w(policy)q 13 2 v 13 w(acquir)o(ed)p fj(\(lock\))1025 1870 y(kval)
r 13 2 v 12 w(t)f(=)h fe(rt)s 13 2 v 12 w(mutex)r 13 2 v 13 w(policy)q 13 2 v
13 w(notacquir)o(ed)p fj(\(lock\))1025 1919 y(kval)r 13 2 v 12 w(t)f(=)h fe
(rt)s 13 2 v 12 w(mutex)r 13 2 v 13 w(policy)q 13 2 v 13 w(con\257ict)p fj
(\(lock\))1025 1969 y(kval)r 13 2 v 12 w(t)f(=)h fe(rt)s 13 2 v 12 w(mutex)r
13 2 v 13 w(policy)q 13 2 v 13 w(unlock)p fj(\(lock,)f(lock)r 13 2 v 12 w(att\
r\))1025 2019 y(kval)r 13 2 v 12 w(t)g(=)h fe(rt)s 13 2 v 12 w(mutex)r 13 2 v
13 w(policy)q 13 2 v 13 w(abort)p fj(\(lock,)f(mode,)h(who\))1025 2069 y(kval)
r 13 2 v 12 w(t)f(=)h fe(rt)s 13 2 v 12 w(mutex)r 13 2 v 13 w(policy)q 13 2 v
13 w(contr)o(ol)p fj(\(lock,)f(cmd,)h(arg,)f(argsize\))1007 2204 y fi(rt)r 13
2 v 13 w(mutex)r 13 2 v 13 w(lock)s 13 2 v 12 w(acquir)n(ed)i fj(is)g(called)
h(when)f(the)g(mechanism)i(layer)966 2254 y(needs)8 b(to)f(acquire)h(the)g
(lock.)14 b(This)7 b(operation)g(keeps)h(track)g(the)f(current)966 2304 y(thr\
ead')m(s)g(priority)e(for)h(the)h(lock)f(object.)14 b fi(rt)r 13 2 v 13 w(mut\
ex)r 13 2 v 13 w(lock)r 13 2 v 13 w(not)q 13 2 v 13 w(acquir)n(ed)966 2354 y
fj(is)f(used)g(when)g(the)g(mechanism)h(module)f(cannot)g(acquire)g(the)g(loc\
k.)966 2403 y(In)d(the)h(case)i(of)d(basic)i(priority)d(inheritance)h(protoco\
l,)g(the)h(operation)966 2453 y(inherits)d(the)h(higher)g(thread')m(s)h(prior\
ity)-6 b(.)15 b fi(rt)s 13 2 v 12 w(mutex)s 13 2 v 12 w(lock)s 13 2 v 12 w
(unlock)10 b fj(is)f(in-)966 2503 y(voked)g(from)h fi(rt)r 13 2 v 12 w(mutex)
s 13 2 v 12 w(unlock)p fj(.)15 b(It)10 b(resets)g(the)g(lock)f(structure.)15 b
(In)9 b(the)966 2553 y(case)k(of)e(priority)e(inheritance,)j(the)f(operation)
g(recovers)h(the)f(priority)966 2603 y(of)j(the)h(thread)g(which)g(executes)h
fi(unlock)p fj(.)29 b fi(rt)r 13 2 v 13 w(mutex)r 13 2 v 13 w(con\257ict)14 b
fj(is)h(in-)966 2652 y(voked)10 b(when)h fi(lock)g fj(is)g(called.)18 b(It)10
b(checks)i(whether)f(we)h(need)f(to)g(abort)966 2702 y(the)i(current)g(critic\
al)g(section.)25 b fi(rt)r 13 2 v 12 w(mutex)s 13 2 v 12 w(lock)s 13 2 v 12 w
(abort)13 b fj(is)g(used)h(when)966 2752 y(the)e(lock)h(is)f(aborted.)22 b
(The)14 b(operation)d(is)i(called)g(in)f(two)g(ways:)20 b(one)935 2877 y( )p
eop
%%Page: 5 5
 bop -118 77 a fj(is)9 b(when)h fi(lock)g fj(or)f fi(unlock)h fj(operation)f
(fails)g(and)h(the)f(other)g(is)h(when)f(the)-118 127 y(thread)g(in)f(the)h
(locked)f(region)h(need)g(to)f(be)i(aborted.)k(The)c(operation)d(is)-118 177 y
(also)i(called)g(when)f(timeout)g(occurred.)15 b fi(rt)r 13 2 v 13 w(mutex)r
13 2 v 13 w(contr)n(ol)8 b fj(is)g(invoked)-118 226 y(to)g(control)g(policy)f
(module)i(such)g(as)g(set)g(and)g(get)g(default)f(lock)h(policy)l(.)-118 342 y
fe(3.2.2)41 b(Policy)10 b(Module)-118 421 y fj(A)k(lock)g(policy)g(module)g
(is)g(implemented)g(as)h(an)g(object)f(similar)g(to)-118 471 y(the)g(scheduli\
ng)f(policy)g(object)g([15].)26 b(The)15 b(following)d(lock)h(policy)-118 521
y(objects)d(are)h(supported.)-118 616 y fe(Kernelized)h(Monitor)e(\(KM\):)21 b
fj(No)13 b(preemption)g(is)h(allowed)f(while)-35 666 y(a)j(thread)g(is)f(in)g
(the)h(kernelized)g(critical)f(section.)31 b(The)17 b(dura-)-35 716 y(tion)9 b
(of)h(the)h(priority)d(inversion)h(is)i(bounded)e(by)h(the)h(size)g(of)f(the)
-35 766 y(critical)k(region.)26 b fi(rt)r 13 2 v 13 w(mutex)r 13 2 v 13 w(pol\
icy)r 13 2 v 12 w(aquir)n(ed)14 b fj(noti\256es)g(the)g(pro-)-35 815 y(cessor)
g(scheduler)g(for)g(entering)f(the)g(kernelized)h(monitor)e(and)-35 865 y fi
(rt)r 13 2 v 13 w(mutex)r 13 2 v 13 w(policy)r 13 2 v 12 w(unlock)18 b fj(tel\
ls)f(the)h(thread)f(to)g(exit)h(from)f(the)-35 915 y(kernelized)10 b(critical)
g(section.)-118 1002 y fe(Basic)g(Priority)g(\(BP\):)34 b fj(All)12 b(operati\
ons)h(of)g(this)f(policy)g(object)h(are)-35 1052 y(null)g(functions.)26 b(The)
15 b(waiting)e(threads)h(are)h(enqueued)g(in)e(the)-35 1101 y(lock)d(object)g
(based)h(on)e(the)h(thread')n(s)g(priority)-5 b(.)-118 1188 y fe(Basic)10 b
(Priority)g(Inheritance)h(\(BPI\):)21 b fj(The)d(lower)f(priority)d(thread)
-35 1238 y(executing)9 b(the)f(critical)h(section)g(inherits)f(the)h(priority)
d(of)j(higher)-35 1288 y(priority)j(thread,)k(when)f(the)g(lock)f(is)h(con\
\257icted.)28 b(Priority)13 b(in-)-35 1338 y(heritance)g(is)f(processed)h(in)
f fi(rt)r 13 2 v 13 w(mutex)r 13 2 v 13 w(policy)r 13 2 v 12 w(noacquir)m(ed)
h fj(and)-35 1387 y fi(rt)r 13 2 v 13 w(mutex)r 13 2 v 13 w(policy)r 13 2 v 12
w(unlock)j fj(recovers)g(the)g(inherited)e(priority)g(to)-35 1437 y(the)c(thr\
ead')m(s)h(original)d(priority)-5 b(.)-118 1524 y fe(Priority)10 b(Ceiling)f
(Protocol)h(\(PCP\):)21 b fj(The)15 b(execution)f(of)h(thread)f(is)-35 1574 y
(blocked)c(when)g(the)h(priority)d(ceiling)i(of)g(the)g(lock)g(is)g(not)g(hig\
her)-35 1624 y(than)f(all)h(locks)g(which)f(are)i(owned)e(by)h(other)f(thread\
s.)15 b(The)c(pro-)-35 1673 y(tocol)c(prevents)g(deadlock,)i(and)f(chained)g
(blocking.)13 b(The)8 b(policy)-35 1723 y(module)j(has)i(a)f(global)f(queue)h
(to)g(hold)f(the)g(currently)g(acquired)-35 1773 y(locks.)21 b fi(rt)r 13 2 v
13 w(mutex)r 13 2 v 13 w(policy)r 13 2 v 12 w(acquir)n(ed)13 b fj(checks)g
(the)f(ceiling)g(prior-)-35 1823 y(ity)7 b(of)h(locks)f(in)h(the)g(global)f
(lock)g(queues)i(with)e(the)h(thread)g(which)-35 1873 y(will)f(enter)h(the)g
(critical)f(section)h(to)g(determine)g(the)g(ceiling)f(block)-35 1923 y(of)j
(the)g(thread.)-118 2009 y fe(Restartable)g(Critical)g(Section)g(\(RCS\):)21 b
fj(The)j(critical)e(section)h(is)-35 2059 y(aborted)14 b(by)f(the)h(higher)f
(priority)f(threads)i(and)g(restarted)g(after)-35 2109 y(the)7 b(higher)f(pri\
ority)f(thread)h(is)h(completed.)14 b fi(rt)s 13 2 v 12 w(mutex)s 13 2 v 12 w
(con\257ict)6 b fj(is)-35 2159 y(called)i(in)g fi(rt)r 13 2 v 12 w(mutex)s 13
2 v 12 w(lock)h fj(and)f(aborts)g(the)g(execution)f(of)h(the)g(crit-)-35 2209
y(ical)j(section)g(of)g(the)g(current)g(running)e(thread)i(if)g(lower)g(prior\
ity)-35 2258 y(thread)f(is)g(executing)g(the)g(critical)g(section.)-77 2354 y
(The)h(lock)f(policy)f(object)h(is)g(easy)h(to)f(de\256ne.)16 b(Among)10 b
(all)g(policies,)-118 2403 y(the)i(priority)f(ceiling)g(protocol)g(is)i(the)f
(lar)o(gest)h(policy)f(module.)22 b(The)-118 2453 y(priority)13 b(inheritance)
i(scheme)h(is)g(used)f(in)g(both)f(the)h(basic)h(priority)-118 2503 y(inherit\
ance)8 b(protocol)e(and)j(priority)d(ceiling)h(protocol.)13 b(The)c(code)g
(can)-118 2553 y(be)i(shared)g(in)f(both)g(object.)17 b(The)11 b(advantage)g
(of)g(the)f(approach)h(is)g(not)-118 2603 y(only)g(the)h(reduction)f(of)h(cod\
e)g(size,)i(but)d(also)h(it)g(makes)h(clear)g(de\256ni-)-118 2652 y(tion)c
(of)i(each)h(algorithm.)j(For)10 b(instance,)i(priority)c(ceiling)i(algorithm)
-118 2702 y(is)i(separated)h(into)e(priority)g(inheritance)g(management)j(and)
f(priority)-118 2752 y(ceiling)c(management)j(part.)966 35 y @beginspecial -30
@hoffset -330 @voffset 0.600000 @hscale 0.600000 @vscale @setspecial
%%BeginDocument: preempt.ps

50 dict begin

/arrowHeight 8 def
/arrowWidth 4 def
/none null def
/numGraphicParameters 17 def
/stringLimit 65535 def

/Begin {
save
numGraphicParameters dict begin
} def

/End {
end
restore
} def

/SetB {
dup type /nulltype eq {
pop
false /brushRightArrow idef
false /brushLeftArrow idef
true /brushNone idef
} {
/brushDashOffset idef
/brushDashArray idef
0 ne /brushRightArrow idef
0 ne /brushLeftArrow idef
/brushWidth idef
false /brushNone idef
} ifelse
} def

/SetCFg {
/fgblue idef
/fggreen idef
/fgred idef
} def

/SetCBg {
/bgblue idef
/bggreen idef
/bgred idef
} def

/SetF {
/printSize idef
/printFont idef
} def

/SetP {
dup type /nulltype eq {
pop true /patternNone idef
} {
/patternGrayLevel idef
patternGrayLevel -1 eq {
/patternString idef
} if
false /patternNone idef
} ifelse
} def

/BSpl {
0 begin
storexyn
newpath
n 1 gt {
0 0 0 0 0 0 1 1 true subspline
n 2 gt {
0 0 0 0 1 1 2 2 false subspline
1 1 n 3 sub {
/i exch def
i 1 sub dup i dup i 1 add dup i 2 add dup false subspline
} for
n 3 sub dup n 2 sub dup n 1 sub dup 2 copy false subspline
} if
n 2 sub dup n 1 sub dup 2 copy 2 copy false subspline
patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if
brushNone not { istroke } if
0 0 1 1 leftarrow
n 2 sub dup n 1 sub dup rightarrow
} if
end
} dup 0 4 dict put def

/Circ {
newpath
0 360 arc
patternNone not { ifill } if
brushNone not { istroke } if
} def

/CBSpl {
0 begin
dup 2 gt {
storexyn
newpath
n 1 sub dup 0 0 1 1 2 2 true subspline
1 1 n 3 sub {
/i exch def
i 1 sub dup i dup i 1 add dup i 2 add dup false subspline
} for
n 3 sub dup n 2 sub dup n 1 sub dup 0 0 false subspline
n 2 sub dup n 1 sub dup 0 0 1 1 false subspline
patternNone not { ifill } if
brushNone not { istroke } if
} {
Poly
} ifelse
end
} dup 0 4 dict put def

/Elli {
0 begin
newpath
4 2 roll
translate
scale
0 0 1 0 360 arc
patternNone not { ifill } if
brushNone not { istroke } if
end
} dup 0 1 dict put def

/Line {
0 begin
2 storexyn
newpath
x 0 get y 0 get moveto
x 1 get y 1 get lineto
brushNone not { istroke } if
0 0 1 1 leftarrow
0 0 1 1 rightarrow
end
} dup 0 4 dict put def

/MLine {
0 begin
storexyn
newpath
n 1 gt {
x 0 get y 0 get moveto
1 1 n 1 sub {
/i exch def
x i get y i get lineto
} for
patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if
brushNone not { istroke } if
0 0 1 1 leftarrow
n 2 sub dup n 1 sub dup rightarrow
} if
end
} dup 0 4 dict put def

/Poly {
3 1 roll
newpath
moveto
-1 add
{ lineto } repeat
closepath
patternNone not { ifill } if
brushNone not { istroke } if
} def

/Rect {
0 begin
/t exch def
/r exch def
/b exch def
/l exch def
newpath
l b moveto
l t lineto
r t lineto
r b lineto
closepath
patternNone not { ifill } if
brushNone not { istroke } if
end
} dup 0 4 dict put def

/Text {
ishow
} def

/idef {
dup where { pop pop pop } { exch def } ifelse
} def

/ifill {
0 begin
gsave
patternGrayLevel -1 ne {
fgred bgred fgred sub patternGrayLevel mul add
fggreen bggreen fggreen sub patternGrayLevel mul add
fgblue bgblue fgblue sub patternGrayLevel mul add setrgbcolor
eofill
} {
eoclip
originalCTM setmatrix
pathbbox /t exch def /r exch def /b exch def /l exch def
/w r l sub ceiling cvi def
/h t b sub ceiling cvi def
/imageByteWidth w 8 div ceiling cvi def
/imageHeight h def
bgred bggreen bgblue setrgbcolor
eofill
fgred fggreen fgblue setrgbcolor
w 0 gt h 0 gt and {
l b translate w h scale
w h true [w 0 0 h neg 0 h] { patternproc } imagemask
} if
} ifelse
grestore
end
} dup 0 8 dict put def

/istroke {
gsave
brushDashOffset -1 eq {
[] 0 setdash
1 setgray
} {
brushDashArray brushDashOffset setdash
fgred fggreen fgblue setrgbcolor
} ifelse
brushWidth setlinewidth
originalCTM setmatrix
stroke
grestore
} def

/ishow {
0 begin
gsave
fgred fggreen fgblue setrgbcolor
/fontDict printFont findfont printSize scalefont dup setfont def
/descender fontDict begin 0 [FontBBox] 1 get FontMatrix end
transform exch pop def
/vertoffset 0 descender sub printSize sub printFont /Courier ne
printFont /Courier-Bold ne and { 1 add } if def {
0 vertoffset moveto show
/vertoffset vertoffset printSize sub def
} forall
grestore
end
} dup 0 3 dict put def

/patternproc {
0 begin
/patternByteLength patternString length def
/patternHeight patternByteLength 8 mul sqrt cvi def
/patternWidth patternHeight def
/patternByteWidth patternWidth 8 idiv def
/imageByteMaxLength imageByteWidth imageHeight mul
stringLimit patternByteWidth sub min def
/imageMaxHeight imageByteMaxLength imageByteWidth idiv patternHeight idiv
patternHeight mul patternHeight max def
/imageHeight imageHeight imageMaxHeight sub store
/imageString imageByteWidth imageMaxHeight mul patternByteWidth add string def
0 1 imageMaxHeight 1 sub {
/y exch def
/patternRow y patternByteWidth mul patternByteLength mod def
/patternRowString patternString patternRow patternByteWidth getinterval def
/imageRow y imageByteWidth mul def
0 patternByteWidth imageByteWidth 1 sub {
/x exch def
imageString imageRow x add patternRowString putinterval
} for
} for
imageString
end
} dup 0 12 dict put def

/min {
dup 3 2 roll dup 4 3 roll lt { exch } if pop
} def

/max {
dup 3 2 roll dup 4 3 roll gt { exch } if pop
} def

/arrowhead {
0 begin
transform originalCTM itransform
/taily exch def
/tailx exch def
transform originalCTM itransform
/tipy exch def
/tipx exch def
/dy tipy taily sub def
/dx tipx tailx sub def
/angle dx 0 ne dy 0 ne or { dy dx atan } { 90 } ifelse def
gsave
originalCTM setmatrix
tipx tipy translate
angle rotate
newpath
0 0 moveto
arrowHeight neg arrowWidth 2 div lineto
arrowHeight neg arrowWidth 2 div neg lineto
closepath
patternNone not {
originalCTM setmatrix
/padtip arrowHeight 2 exp 0.25 arrowWidth 2 exp mul add sqrt brushWidth mul
arrowWidth div def
/padtail brushWidth 2 div def
tipx tipy translate
angle rotate
padtip 0 translate
arrowHeight padtip add padtail add arrowHeight div dup scale
arrowheadpath
ifill
} if
brushNone not {
originalCTM setmatrix
tipx tipy translate
angle rotate
arrowheadpath
istroke
} if
grestore
end
} dup 0 9 dict put def

/arrowheadpath {
newpath
0 0 moveto
arrowHeight neg arrowWidth 2 div lineto
arrowHeight neg arrowWidth 2 div neg lineto
closepath
} def

/leftarrow {
0 begin
y exch get /taily exch def
x exch get /tailx exch def
y exch get /tipy exch def
x exch get /tipx exch def
brushLeftArrow { tipx tipy tailx taily arrowhead } if
end
} dup 0 4 dict put def

/rightarrow {
0 begin
y exch get /tipy exch def
x exch get /tipx exch def
y exch get /taily exch def
x exch get /tailx exch def
brushRightArrow { tipx tipy tailx taily arrowhead } if
end
} dup 0 4 dict put def

/midpoint {
0 begin
/y1 exch def
/x1 exch def
/y0 exch def
/x0 exch def
x0 x1 add 2 div
y0 y1 add 2 div
end
} dup 0 4 dict put def

/thirdpoint {
0 begin
/y1 exch def
/x1 exch def
/y0 exch def
/x0 exch def
x0 2 mul x1 add 3 div
y0 2 mul y1 add 3 div
end
} dup 0 4 dict put def

/subspline {
0 begin
/movetoNeeded exch def
y exch get /y3 exch def
x exch get /x3 exch def
y exch get /y2 exch def
x exch get /x2 exch def
y exch get /y1 exch def
x exch get /x1 exch def
y exch get /y0 exch def
x exch get /x0 exch def
x1 y1 x2 y2 thirdpoint
/p1y exch def
/p1x exch def
x2 y2 x1 y1 thirdpoint
/p2y exch def
/p2x exch def
x1 y1 x0 y0 thirdpoint
p1x p1y midpoint
/p0y exch def
/p0x exch def
x2 y2 x3 y3 thirdpoint
p2x p2y midpoint
/p3y exch def
/p3x exch def
movetoNeeded { p0x p0y moveto } if
p1x p1y p2x p2y p3x p3y curveto
end
} dup 0 17 dict put def

/storexyn {
/n exch def
/y n array def
/x n array def
n 1 sub -1 0 {
/i exch def
y i 3 2 roll put
x i 3 2 roll put
} for
} def




Begin
[ 0.8 0 0 0.8 0 0 ] concat
/originalCTM matrix currentmatrix def

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0 SetP
[ 1 0 0 1 148 197 ] concat
11 263 461 263 Line
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
< 11 22 44 88 11 22 44 88 > -1 SetP
[ 1 0 0 1 138 197 ] concat
11 321 61 331 Rect
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 138 197 ] concat
61 261 111 271 Rect
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 138 197 ] concat
111 261 161 271 Rect
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 138 197 ] concat
161 261 211 271 Rect
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
< 11 22 44 88 11 22 44 88 > -1 SetP
[ 1 0 0 1 138 197 ] concat
211 321 260 331 Rect
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
0.75 SetP
[ 1 0 0 1 138 197 ] concat
260 192 310 202 Rect
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 138 197 ] concat
310 192 360 202 Rect
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 138 197 ] concat
360 192 410 202 Rect
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 138 197 ] concat
410 192 460 202 Rect
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 148 197 ] concat
51 321 51 261 Line
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 148 197 ] concat
201 321 201 271 Line
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 148 197 ] concat
251 321 251 202 Line
End

Begin %I Line
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 148 197 ] concat
450 371 450 202 Line
End

Begin %I Text
0 0 0 SetCFg
/Times-Roman 12 SetF
[ 1 0 0 1 89 600 ] concat
[
(Thread A)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Times-Roman 12 SetF
[ 1 0 0 1 90 529 ] concat
[
(Thread B)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Times-Roman 12 SetF
[ 1 0 0 1 135 474 ] concat
[
(handler)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Times-Roman 12 SetF
[ 1 0 0 1 92 397 ] concat
[
(Scheduler)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Helvetica-Oblique 14 SetF
[ 1 0 0 1 149 548 ] concat
[
(C)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Helvetica-Oblique 14 SetF
[ 1 0 0 1 199 448 ] concat
[
(C)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Helvetica-Oblique 14 SetF
[ 1 0 0 1 249 488 ] concat
[
(C)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Helvetica-Oblique 14 SetF
[ 1 0 0 1 299 448 ] concat
[
(C)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Helvetica-Oblique 14 SetF
[ 1 0 0 1 349 548 ] concat
[
(C)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Helvetica-Oblique 14 SetF
[ 1 0 0 1 399 379 ] concat
[
(C)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Helvetica-Oblique 14 SetF
[ 1 0 0 1 448 418 ] concat
[
(C)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Helvetica-Oblique 14 SetF
[ 1 0 0 1 498 379 ] concat
[
(C)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Courier 8 SetF
[ 1 0 0 1 159 538 ] concat
[
(non_int)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Courier 8 SetF
[ 1 0 0 1 209 438 ] concat
[
(int_hdr)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Courier 8 SetF
[ 1 0 0 1 259 478 ] concat
[
(wakeup)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Courier 8 SetF
[ 1 0 0 1 309 438 ] concat
[
(int_left)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Courier 8 SetF
[ 1 0 0 1 359 538 ] concat
[
(sys_left)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Courier 8 SetF
[ 1 0 0 1 408 369 ] concat
[
(sched_call)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Courier 8 SetF
[ 1 0 0 1 458 408 ] concat
[
(block)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Courier 8 SetF
[ 1 0 0 1 508 369 ] concat
[
(choose)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Helvetica-Oblique 14 SetF
[ 1 0 0 1 548 418 ] concat
[
(C)
] Text
End

Begin %I Rect
1 0 0 [] 0 SetB
0 0 0 SetCFg
1 1 1 SetCBg
none SetP %I p n
[ 1 0 0 1 297 236 ] concat
302 322 357 332 Rect
End

Begin %I Text
0 0 0 SetCFg
/Times-Roman 12 SetF
[ 1 0 0 1 81 474 ] concat
[
(Interrupt)
] Text
End

Begin %I Text
0 0 0 SetCFg
/Courier 8 SetF
[ 1 0 0 1 557 410 ] concat
[
(dispatch)
] Text
End

End %I eop

showpage


end
%%EndDocument
 @endspecial 1128 856 a(Figure)e(2:)k(Preemption)c(during)f(a)i(System)f(Call)
966 994 y fk(4)59 b(Evaluation)14 b(and)i(Cost)f(Analysis)966 1091 y fj(In)i
(this)g(section,)j(we)e(\256rst)g(discuss)f(the)h(cost)g(for)f(managing)h(rea\
l-)966 1141 y(time)e(thread)h(and)f(the)h(synchronization)e(cost)h(under)g
(various)g(syn-)966 1191 y(chronization)7 b(policies.)14 b(W)m(e)9 b(then)f
(analyze)i(the)e(relation)g(between)h(the)966 1240 y(schedulability)d(and)j
(the)f(cost)g(of)h(various)e(real-time)i(synchronization)966 1290 y(protocols\
.)1007 1342 y(The)j(basic)g(cost)f(of)g(the)g(real-time)g(thread)g(management)
h(and)f(syn-)966 1392 y(chronization)i(primitives)g(were)i(measured)g(using)f
(a)h(Sony)e(NEWS-)966 1442 y(1720)d(workstation)g(\(25)h(MHz)g(MC68030\))f
(and)i(a)f(FORCE)h(CPU-30)966 1492 y(board)18 b(\(20)g(MHz)h(MC68030\).)38 b
(W)m(e)19 b(simply)f(evaluated)h(a)g(single)966 1542 y(processor)12 b(environ\
ment)g(with)g(a)h(Sony)f(machine.)23 b(W)m(e)13 b(used)g(an)g(ac-)966 1592 y
(curate)c(clock)g(on)g(the)g(FORCE)g(board)g(for)f(timing)g(measurement)j(on)
d(a)966 1641 y(NEWS-1720)h(through)f(VME-bus)h(backplane.)16 b(This)9 b(clock)
h(enabled)966 1691 y(us)g(to)g(measure)h(the)f(overheads)h(with)e(resolution)
g(of)h(4)g fd(\026)p fh(s)p fj(.)966 1823 y ff(4.1)50 b(Pr)o(eemption)12 b
(Cost)h(Analysis)966 1905 y fj(Before)18 b(we)g(start)g(analyzing)f(the)h(pre\
emptability)e(of)h(the)h(system,)966 1955 y(let)c(us)g(\256rst)h(determine)f
(the)h(basic)g(cost)f(factors.)29 b(Figure)14 b(2)g(de\256nes)966 2005 y(the)
g(basic)h(cost)f(factors)h(when)f(a)i(higher)d(priority)f(thread)j(preempts)
966 2055 y(a)e(lower)f(priority)e(thread)j(which)f(is)g(executing)g(a)h(syste\
m)g(call.)23 b fh(C)1966 2061 y fg(opr)966 2104 y fj(speci\256es)17 b(the)g
(execution)f(cost)h(of)f(the)g(primitive)f fi(opr)p fj(.)34 b fh(C)1872 2110 y
fg(non)q 13 2 v 13 w(int)1980 2104 y fj(is)966 2154 y(the)12 b(worst)g(case)i
(execution)e(time)g(of)g(a)h(non-interrupt)d(region)h(where)966 2204 y(all)h
(interrupts)f(are)j(masked.)23 b(A)13 b(critical)f(interrupt)f(may)j(be)f(del\
ayed)966 2254 y(until)d(the)i(non-critical)f(region)h(is)g(completed.)21 b fh
(C)1712 2260 y fg(int)r 13 2 v 13 w(hdr)1812 2254 y fj(is)12 b(the)h(worst)
966 2304 y(case)e(execution)f(time)g(of)g(the)g(interrupt)e(handlers.)15 b
(Interrupt)8 b(handler)966 2354 y(can)17 b(be)h(interrupted)d(by)i(a)h(higher)
e(priority)f(interrupt.)33 b fh(C)1872 2360 y fg(wakeup)1980 2354 y fj(is)966
2403 y(the)11 b(time)h(to)f(wakeup)g(a)h(blocked)g(thread.)19 b fh(C)1633 2409
y fg(int)q 13 2 v 13 w(lef)s(t)1738 2403 y fj(is)11 b(the)h(remaining)966 2453
y(time)e(after)i(the)e(wakeup)i(until)d(the)h(interrupt)g(is)g(completed.)18 b
fh(C)1910 2459 y fg(sys)r 13 2 v 13 w(lef)s(t)966 2503 y fj(is)c(the)h(remain\
ing)g(execution)f(time)h(of)g(the)g(system)g(call.)30 b fh(C)1897 2509 y fg
(sched)1980 2503 y fj(is)966 2553 y(the)15 b(total)g(scheduling)f(delay)i(tim\
e)f(and)h(sum)g(of)f fh(C)1751 2559 y fg(sched)q 13 2 v 13 w(call)1877 2553 y
fj(,)j fh(C)1933 2559 y fg(block)1997 2553 y fj(,)966 2603 y fh(C)994 2609 y
fg(choose)1076 2603 y fj(,)d(and)f fh(C)1203 2609 y fg(dispatch)1304 2603 y fj
(.)26 b fh(C)1368 2609 y fg(sched)q 13 2 v 13 w(call)1509 2603 y fj(is)13 b
(the)h(delay)g(time)g(to)f(switch)h(to)966 2652 y(the)9 b(scheduler)m(.)15 b
fh(C)1235 2658 y fg(block)1309 2652 y fj(is)9 b(the)g(blocking)f(time)h(for)f
(giving)f(up)i(the)g(CPU)966 2702 y(and)14 b fh(C)1068 2708 y fg(choose)1166
2702 y fj(is)g(the)h(selection)f(time)h(for)f(a)h(next)f(thread,)i fh(C)1865
2708 y fg(dispatch)1980 2702 y fj(is)966 2752 y(the)9 b(context)g(switching)f
(time.)15 b(The)c(results)e(of)g(the)h(measurement)h(are)935 2877 y( )p eop
eos end TeXDict begin bos 300 @start /fa 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 9 12 16 19 19 31 29 12 12 12 19 25 9 12 9 10 19 19
19 19 19 19 19 19 19 19 12 12 25 25 25 19 34 23 23 25 27 23 23 27 27 12 17 25
21 31 25 27 23 27 23 19 21 27 23 31 23 21 21 15 10 15 16 19 12 19 19 17 19 17
10 19 19 10 10 17 10 27 19 19 19 19 15 15 10 19 17 25 17 17 15 15 10 15 20 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 19 19 6 19
19 19 19 8 21 19 12 12 19 19 0 19 19 19 9 0 20 13 12 21 21 19 33 37 0 19 0 12
12 12 12 12 12 12 12 0 12 12 0 12 12 12 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 33
0 10 0 0 0 0 21 27 35 12 0 0 0 0 0 25 0 0 0 10 0 0 10 19 25 19 0 0 0 0
/Times-Italic 1000 589824 rf /fb df[<0C0C0C0C0C0C1818181818181818303030323032
307278B46F1C60006000C000C000C0008000>15 19 2 6 20]22 dc dfe /fc 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 10 12 15 15 24 23 10 10 10
15 20 7 10 7 8 15 15 15 15 15 15 15 15 15 15 10 10 20 20 20 15 27 18 18 19 21
18 18 21 21 10 13 19 16 24 19 21 18 21 18 15 16 21 18 24 18 16 16 11 8 11 12
15 10 15 15 13 15 13 8 15 15 8 8 13 8 21 15 15 15 15 11 11 8 15 13 19 13 13 11
12 8 12 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11 15 15 5 15 15 15 15 6 16 15 10 10 15 15 0 15 15 15 7 0 15 10 10 16 16 15 26
29 0 15 0 10 10 10 10 10 10 10 10 0 10 10 0 10 10 10 26 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 26 0 8 0 0 0 0 16 21 27 9 0 0 0 0 0 19 0 0 0 8 0 0 8 15 19 15 0 0 0
0 /Times-Italic 1000 458752 rf /fd 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 8 10 12 12 21 19 8 8 8 12 17 6 8 6 7 12 12 12 12 12 12
12 12 12 12 8 8 17 17 17 12 23 15 15 17 18 15 15 18 18 8 11 17 14 21 17 18 15
18 15 12 14 18 15 21 15 14 14 10 7 10 11 12 8 12 12 11 12 11 12 12 12 7 7 11 7
18 12 12 12 12 10 10 7 12 11 17 11 11 10 10 7 10 13 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 12 12 4 12 12 12 12 5 14 12 8 8
12 12 0 12 12 12 6 0 13 9 8 14 14 12 22 25 0 12 0 8 8 8 8 8 8 8 8 0 8 8 0 8 8
8 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 22 0 7 0 0 0 0 14 18 24 8 0 0 0 0 0 17 0
0 0 7 0 0 7 12 17 12 0 0 0 0 /Times-Italic-Math /Times-Italic 1.0 ExtendFont
1000 393216 rf /fe 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 12 16 19 19 31 29 12 12 12 19 25 9 12 9 10 19 19 19 19 19 19 19 19 19 19
12 12 25 25 25 19 34 23 23 25 27 23 23 27 27 12 17 25 21 31 25 27 23 27 23 19
21 27 23 31 23 21 21 15 10 15 16 19 12 19 19 17 19 17 18 19 19 10 10 17 10 27
19 19 19 19 15 15 10 19 17 25 17 17 15 15 10 15 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 19 19 6 19 19 19 19 8 21 19 12 12
19 19 0 19 19 19 9 0 20 13 12 21 21 19 33 37 0 19 0 12 12 12 12 12 12 12 12 0
12 12 0 12 12 12 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 33 0 10 0 0 0 0 21 27 35
12 0 0 0 0 0 25 0 0 0 10 0 0 10 19 25 19 0 0 0 0 /Times-Italic-Math
/Times-Italic 1.0 ExtendFont 1000 589824 rf /ff df[<0603000703800E07000E07000E
07000E07001C0E001C0E001C0E001C0E00381C40381C40381C40383C407C4C8077870070000070
0000E00000E00000E00000E00000C00000>18 23 2 7 23]22 dc[<0004000C00180018001800
300030003000600060006000C000C000C00180018001800300030003000600060006000C000C00
0C00180018001800300030003000600060006000C000C000>14 37 2 9 19]61 dc dfe /fg df
[<8000C0C001C0600300300600180C000C180006300003600001C00001C0000360000630000C18
00180C00300600600300C001C08000C0>18 18 6 0 30]2 dc dfe /fh 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 12 15 19 19 31 29 12 12 12 19 21
9 12 9 10 19 19 19 19 19 19 19 19 19 19 10 10 21 21 21 17 34 27 25 25 27 23 21
27 27 12 15 27 23 33 27 27 21 27 25 21 23 27 27 35 27 27 23 12 10 12 18 19 12
17 19 17 19 17 12 19 19 10 10 19 10 29 19 19 19 19 12 15 10 19 19 27 19 19 17
18 7 18 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 19 19 6 19 19 19 19 7 17 19 12 12 21 21 0 19 19 19 9 0 17 13 12 17 17 19 37
37 0 17 0 12 12 12 12 12 12 12 12 0 12 12 0 12 12 12 37 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 33 0 10 0 0 0 0 23 27 33 12 0 0 0 0 0 25 0 0 0 10 0 0 10 19 27 19 0
0 0 0 /Times-Roman 1000 589824 rf /fi df[<0180300380700380700380700700E00700E0
0700E00700E00E01C00E01C00E01C00E01C01C03881C03881C03881E07883E19903BE0E0380000
380000700000700000700000700000E00000E00000C00000>21 27 1 9 25]22 dc[<E0000000
780000001E0000000780000001E0000000780000001E0000000780000001E0000000780000001E
00000007800000078000001E00000078000001E00000078000001E00000078000001E000000780
00001E00000078000000E0000000>25 24 3 2 32]62 dc dfe /fj df[<FFFFFF80FFFFFF80>
25 2 3 -9 32]0 dc[<400020C000606000C03001801803000C0600060C0003180001B00000E0
0000E00001B000031800060C000C06001803003001806000C0C00060400020>19 20 6 0 32]2
dc dfe /fk 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7
9 10 10 17 16 7 7 7 10 14 5 7 5 6 10 10 10 10 10 10 10 10 10 10 7 7 14 14 14
10 19 13 13 14 15 13 13 15 15 7 9 14 12 17 14 15 13 15 13 10 12 15 13 17 13 12
12 8 6 8 9 10 7 10 10 9 10 9 10 10 10 6 6 9 6 15 10 10 10 10 8 8 6 10 9 14 9 9
8 8 6 8 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 10 10 3 10 10 10 10 4 12 10 7 7 10 10 0 10 10 10 5 0 11 7 7 12 12 10 18 21 0
10 0 7 7 7 7 7 7 7 7 0 7 7 0 7 7 7 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 18 0 6 0
0 0 0 12 15 20 6 0 0 0 0 0 14 0 0 0 6 0 0 6 10 14 10 0 0 0 0
/Times-Italic-Math /Times-Italic 1.0 ExtendFont 1000 327680 rf /fl 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12 17 28 25 25 50 41 17 17
17 25 28 12 17 12 14 25 25 25 25 25 25 25 25 25 25 17 17 28 28 28 25 46 36 33
36 36 33 30 39 39 19 25 39 33 47 36 39 30 39 36 28 33 36 36 50 36 36 33 17 14
17 29 25 17 25 28 22 28 22 17 25 28 14 17 28 14 41 28 25 28 28 22 19 17 28 25
36 25 25 22 20 11 20 26 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 17 25 25 8 25 25 25 25 14 25 25 17 17 28 28 0 25 25 25 12 0 27
17 17 25 25 25 50 50 0 25 0 17 17 17 17 17 17 17 17 0 17 17 0 17 17 17 50 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 50 0 15 0 0 0 0 33 39 50 16 0 0 0 0 0 36 0 0 0 14
0 0 14 25 36 28 0 0 0 0 /Times-Bold 1000 786432 rf /fm 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 10 12 15 15 24 23 10 10 10 15 16 7
10 7 8 15 15 15 15 15 15 15 15 15 15 8 8 16 16 16 13 27 21 19 19 21 18 16 21
21 10 11 21 18 26 21 21 16 21 19 16 18 21 21 27 21 21 18 10 8 10 14 15 10 13
15 13 15 13 10 15 15 8 8 15 8 23 15 15 15 15 10 11 8 15 15 21 15 15 13 14 6 14
16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 15
15 5 15 15 15 15 5 13 15 10 10 16 16 0 15 15 15 7 0 13 10 10 13 13 15 29 29 0
13 0 10 10 10 10 10 10 10 10 0 10 10 0 10 10 10 29 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 26 0 8 0 0 0 0 18 21 26 9 0 0 0 0 0 19 0 0 0 8 0 0 8 15 21 15 0 0 0 0
/Times-Roman 1000 458752 rf /fn 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 12 15 15 24 23 10 10 10 15 20 7 10 7 8 15 15 15 15 15
15 15 15 15 15 10 10 20 20 20 15 27 18 18 19 21 18 18 21 21 10 13 19 16 24 19
21 18 21 18 15 16 21 18 24 18 16 16 11 8 11 12 15 10 15 15 13 15 13 14 15 15 8
8 13 8 21 15 15 15 15 11 11 8 15 13 19 13 13 11 12 8 12 16 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 15 15 5 15 15 15 15 6 16 15
10 10 15 15 0 15 15 15 7 0 15 10 10 16 16 15 26 29 0 15 0 10 10 10 10 10 10 10
10 0 10 10 0 10 10 10 26 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 26 0 8 0 0 0 0 16 21
27 9 0 0 0 0 0 19 0 0 0 8 0 0 8 15 19 15 0 0 0 0 /Times-Italic-Math
/Times-Italic 1.0 ExtendFont 1000 458752 rf /fo 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14 17 21 21 35 32 14 14 14 21 28 10 14 10
12 21 21 21 21 21 21 21 21 21 21 14 14 28 28 28 21 38 25 25 28 30 25 25 30 30
14 18 28 23 35 28 30 25 30 25 21 23 30 25 35 25 23 23 16 12 16 18 21 14 21 21
18 21 18 20 21 21 12 12 18 12 30 21 21 21 21 16 16 12 21 18 28 18 18 16 17 11
17 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16
21 21 7 21 21 21 21 9 23 21 14 14 21 21 0 21 21 21 10 0 22 15 14 23 23 21 37
42 0 21 0 14 14 14 14 14 14 14 14 0 14 14 0 14 14 14 37 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 37 0 11 0 0 0 0 23 30 39 13 0 0 0 0 0 28 0 0 0 12 0 0 12 21 28 21 0
0 0 0 /Times-Italic-Math /Times-Italic 1.0 ExtendFont 1000 655360 rf /fp 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 11 14 17 17 28 26
11 11 11 17 19 8 11 8 9 17 17 17 17 17 17 17 17 17 17 9 9 19 19 19 15 31 24 22
22 24 20 18 24 24 11 13 24 20 30 24 24 18 24 22 18 20 24 24 31 24 24 20 11 9
11 16 17 11 15 17 15 17 15 11 17 17 9 9 17 9 26 17 17 17 17 11 13 9 17 17 24
17 17 15 16 7 16 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 11 17 17 6 17 17 17 17 6 15 17 11 11 18 18 0 17 17 17 8 0 15 12 11
15 15 17 33 33 0 15 0 11 11 11 11 11 11 11 11 0 11 11 0 11 11 11 33 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 30 0 9 0 0 0 0 20 24 30 10 0 0 0 0 0 22 0 0 0 9 0 0 9 17
24 17 0 0 0 0 /Times-Roman 1000 524288 rf /fq 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 8 10 12 12 21 19 8 8 8 12 14 6 8 6 7 12 12
12 12 12 12 12 12 12 12 7 7 14 14 14 11 23 18 17 17 18 15 14 18 18 8 10 18 15
22 18 18 14 18 17 14 15 18 18 24 18 18 15 8 7 8 12 12 8 11 12 11 12 11 8 12 12
7 7 12 7 19 12 12 12 12 8 10 7 12 12 18 12 12 11 12 5 12 13 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 12 12 4 12 12 12 12 4 11
12 8 8 14 14 0 12 12 12 6 0 11 9 8 11 11 12 25 25 0 11 0 8 8 8 8 8 8 8 8 0 8 8
0 8 8 8 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 22 0 7 0 0 0 0 15 18 22 8 0 0 0 0 0
17 0 0 0 7 0 0 7 12 18 12 0 0 0 0 /Times-Roman 1000 393216 rf /fr 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 14 17 21 21 35 32 14 14
14 21 28 10 14 10 12 21 21 21 21 21 21 21 21 21 21 14 14 28 28 28 21 38 25 25
28 30 25 25 30 30 14 18 28 23 35 28 30 25 30 25 21 23 30 25 35 25 23 23 16 12
16 18 21 14 21 21 18 21 18 12 21 21 12 12 18 12 30 21 21 21 21 16 16 12 21 18
28 18 18 16 17 11 17 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 16 21 21 7 21 21 21 21 9 23 21 14 14 21 21 0 21 21 21 10 0 22 15
14 23 23 21 37 42 0 21 0 14 14 14 14 14 14 14 14 0 14 14 0 14 14 14 37 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 37 0 11 0 0 0 0 23 30 39 13 0 0 0 0 0 28 0 0 0 12 0 0
12 21 28 21 0 0 0 0 /Times-Italic 1000 655360 rf /fs 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 14 17 21 21 35 32 14 14 14 21 23 10
14 10 12 21 21 21 21 21 21 21 21 21 21 12 12 23 23 23 18 38 30 28 28 30 25 23
30 30 14 16 30 25 37 30 30 23 30 28 23 25 30 30 39 30 30 25 14 12 14 19 21 14
18 21 18 21 18 14 21 21 12 12 21 12 32 21 21 21 21 14 16 12 21 21 30 21 21 18
20 8 20 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
14 21 21 7 21 21 21 21 7 18 21 14 14 23 23 0 21 21 21 10 0 19 15 14 18 18 21
42 42 0 18 0 14 14 14 14 14 14 14 14 0 14 14 0 14 14 14 42 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 37 0 11 0 0 0 0 25 30 37 13 0 0 0 0 0 28 0 0 0 12 0 0 12 21 30 21
0 0 0 0 /Times-Roman 1000 655360 rf /ft 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 15 20 33 30 30 60 50 20 20 20 30 34 15 20 15 17 30
30 30 30 30 30 30 30 30 30 20 20 34 34 34 30 56 43 40 43 43 40 37 47 47 23 30
47 40 56 43 47 37 47 43 33 40 43 43 60 43 43 40 20 17 20 35 30 20 30 33 27 33
27 20 30 33 17 20 33 17 50 33 30 33 33 27 23 20 33 30 43 30 30 27 24 13 24 31
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 30 30
10 30 30 30 30 17 30 30 20 20 33 33 0 30 30 30 15 0 32 21 20 30 30 30 60 60 0
30 0 20 20 20 20 20 20 20 20 0 20 20 0 20 20 20 60 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 60 0 18 0 0 0 0 40 47 60 20 0 0 0 0 0 43 0 0 0 17 0 0 17 30 43 33 0 0 0 0
/Times-Bold 1000 943718 rf end
 TeXDict begin @letter
%%Page: 6 6
 bop 158 79 a 491 2 v 157 124 a 2 46 v 183 111 a fh(Basic)8 b(Operation)449
124 y 2 46 v 8 w 2 46 v 483 111 a(Cost)h(\()p ff(\026)p fh(s\))647 124 y 2 46
v 158 126 a 491 2 v 10 x 491 2 v 157 183 a 2 47 v 252 169 a fe(C)277 173 y fd
(wakeup)449 183 y 2 47 v 8 w 2 47 v 516 169 a fh(72)563 153 y fq(\2621)647 183
y 2 47 v 158 184 a 491 2 v 157 230 a 2 46 v 236 216 a fe(C)261 220 y fd(sched)
s 12 2 v 12 w(call)449 230 y 2 46 v 8 w 2 46 v 534 216 a fh(72)647 230 y 2 46
v 158 232 a 491 2 v 157 277 a 2 46 v 216 264 a fe(C)241 268 y fd(int)s 12 2 v
11 w(lef)r(t)p fq(\()p fd(clock)p fq(\))449 277 y 2 46 v 8 w 2 46 v 534 264 a
fh(36)647 277 y 2 46 v 158 279 a 491 2 v 157 329 a 2 50 v 232 313 a fe(C)257
296 y fq(\2621)257 323 y fd(block)310 328 y fk(reincar)449 329 y 2 50 v 8 w 2
50 v 507 313 a fh(672)572 297 y fq(\2621)647 329 y 2 50 v 158 330 a 491 2 v
157 377 a 2 47 v 263 363 a fe(C)288 367 y fd(block)449 377 y 2 47 v 8 w 2 47 v
516 363 a fh(84)563 347 y fq(\2621)647 377 y 2 47 v 158 379 a 491 2 v 157 425
a 2 47 v 256 412 a fe(C)281 416 y fd(choose)449 425 y 2 47 v 8 w 2 47 v 516
412 a fh(40)563 396 y fq(\2621)647 425 y 2 47 v 158 427 a 491 2 v 157 473 a 2
46 v 248 459 a fe(C)273 463 y fd(dispatch)449 473 y 2 46 v 8 w 2 46 v 534 459
a fh(48)647 473 y 2 46 v 158 474 a 491 2 v 10 x 491 2 v 157 530 a 2 46 v 243
516 a fe(C)268 520 y fd(null)s 12 2 v 12 w(trap)449 530 y 2 46 v 8 w 2 46 v
534 516 a fh(48)647 530 y 2 46 v 158 532 a 491 2 v 157 578 a 2 47 v 251 565 a
fe(C)276 569 y fd(clockint)449 578 y 2 47 v 8 w 2 47 v 507 565 a fh(108)572
549 y fq(\2622)647 578 y 2 47 v 158 580 a 491 2 v -118 646 a fm(\2621)20 b fn
(C)-49 650 y fk(block)-2 646 y fm(,)14 b fn(C)38 650 y fk(wakeup)116 646 y fm
(and)d fn(C)189 650 y fk(choose)249 646 y fm(,)j(are)d(measured)g(under)f(a)i
(\256xed)f(priority)f(scheduling)g(policy)-35 679 y(\(default\))5 b(and)h(are)
h(policy)f(speci\256c)h(numbers.)-118 729 y(\2622)20 b(This)7 b(includes)f
(the)h(cost)g(calling)f(scheduling)f(policy)h(routines,)g(but)h(no)f(thread)g
(wakeup)f(cost.)-118 778 y(\2623)20 b fn(C)-49 782 y fk(block)-5 789 y(reinca\
r)69 778 y fm(is)7 b(the)g(blocking)e(cost)i(at)g(the)g(reincarnation)e(of)h
(a)h(period)f(thread.)159 895 y fs(T)m(able)11 b(1:)j(The)d(Basic)g(Overhead)
-118 1021 y(summarized)g(in)f(T)m(able)h(1.)-77 1071 y(Now)m(,)e(let)f(us)g
(consider)g(the)f(preemption)h(cost)g(in)f(Real-T)o(ime)h(Mach.)-118 1121 y
(The)j(total)e(worst)h(case)h(preemption)f(cost)g(can)h(be)g(de\256ned)f(as)
-59 1214 y fo(C)-31 1220 y fn(preempt)77 1214 y fs(=)i fo(C)140 1220 y fn(non)
q 13 2 v 13 w(int)241 1214 y fs(+)d fo(C)301 1220 y fn(int)r 13 2 v 13 w(hdr)
398 1214 y fs(+)h fo(C)459 1220 y fn(wakeup)248 1264 y fs(+)p fo(C)299 1270 y
fn(int)r 13 2 v 13 w(lef)s(t)402 1264 y fs(+)g fo(C)463 1270 y fn(sys)r 13 2 v
13 w(lef)s(t)570 1264 y fs(+)g fo(C)631 1270 y fn(sched)-59 1313 y fo(C)-31
1319 y fn(sched)48 1313 y fs(=)i fo(C)111 1319 y fn(sched)r 13 2 v 12 w(call)
247 1313 y fs(+)e fo(C)308 1319 y fn(block)382 1313 y fs(+)f fo(C)442 1319 y
fn(choose)534 1313 y fs(+)h fo(C)595 1319 y fn(dispatch)-77 1456 y fs(Under)
29 b(the)g(\256xed)g(priority)d(scheduling,)33 b fo(C)653 1462 y fn(preempt)
779 1456 y fs(becomes)-118 1506 y fo(C)-90 1512 y fn(non)q 13 2 v 12 w(int)13
1506 y fs(+)12 b fo(C)76 1512 y fn(int)r 13 2 v 12 w(hdr)175 1506 y fs(+)h fo
(C)239 1512 y fn(int)r 13 2 v 12 w(lef)s(t)344 1506 y fs(+)f fo(C)407 1512 y
fn(sys)s 13 2 v 12 w(lef)s(t)517 1506 y fs(+)h(316)h fi(\026)p fs(s.)29 b(In)
15 b(our)f(tar)o(get)-118 1556 y(machine,)j(a)e(clock)f(interrupt)f(handler)h
(alone)g(requires)h(at)f(least)h(ad-)-118 1606 y(ditional)e fo(C)52 1612 y fn
(clockint)164 1606 y fs(=)18 b fo(C)233 1612 y fn(int)r 13 2 v 12 w(hdr)332
1606 y fs(+)13 b fo(C)396 1612 y fn(int)r 13 2 v 12 w(lef)s(t)507 1606 y fs
(=)19 b(108)p fi(\026)p fs(s.)28 b(In)15 b(a)g(real-time)-118 1655 y(applicat\
ion,)f(the)f(cost)h(of)g fo(C)314 1661 y fn(int)r 13 2 v 12 w(hdr)413 1655 y
fs(+)d fo(C)475 1661 y fn(int)r 13 2 v 13 w(lef)s(t)583 1655 y fs(can)j(be)g
(precomputed)-118 1705 y(based)8 b(on)g(the)f(system)h(con\256guration,)g(how\
ever)n(,)h(the)e(cost)h(for)f fo(C)833 1711 y fn(non)q 13 2 v 12 w(int)-118
1755 y fs(and)j fo(C)-20 1761 y fn(sys)s 13 2 v 13 w(lef)s(t)89 1755 y fs(are)
h(operating)f(system)h(speci\256c.)16 b(In)10 b(many)h(monolithic)-118 1805 y
(kernel-based)i(systems,)i fo(C)291 1811 y fn(non)q 13 2 v 13 w(int)396 1805 y
fs(and)e fo(C)497 1811 y fn(sys)s 13 2 v 12 w(lef)s(t)609 1805 y fs(becomes)h
(relatively)-118 1855 y(high.)27 b(However)n(,)16 b(in)e(a)h(micro)g(kernel-b\
ased)f(system,)j(an)d(ordinary)-118 1904 y(system)j(call)g(becomes)h(preempti\
ve)f(since)g(its)g(function)e(is)i(imple-)-118 1954 y(mented)d(in)g(a)h(user)
o(-level)f(thread.)27 b(For)13 b(real-time)i(programs)f(which)-118 2004 y(hav\
e)i(shorter)e(deadlines)h(than)g fo(C)393 2010 y fn(preempt)490 2004 y fs(,)i
(we)f(need)f(to)g(reduce)h(each)-118 2054 y(cost)d(factor)g(further)g(down.)
23 b(T)m(o)14 b(reduce)g fo(C)534 2060 y fn(non)p 13 2 v 13 w(int)638 2054 y
fs(and)f fo(C)739 2060 y fn(sys)s 13 2 v 12 w(lef)s(t)837 2054 y fs(,)i(fur-)
-118 2104 y(ther)10 b(kernelization)f(of)h(the)g(current)g(micro)g(kernel)g
(is)g(required.)-118 2224 y fl(4.2)50 b(Synchr)n(onization)11 b(Cost)i(Analys\
is)-118 2303 y fs(In)j(this)f(section,)j(we)f(will)e(analyze)i(the)f(synchron\
ization)e(cost)j(for)-118 2353 y(each)11 b(locking)e(protocol)g(we)i(have)f
(implemented.)-77 2403 y(In)15 b(general,)i(KM)e(tends)g(to)f(be)h(useful)g
(for)f(a)i(very)f(short)f(critical)-118 2453 y(section.)23 b(For)12 b(medium)
i(size)f(critical)f(sections,)i(we)g(can)f(use)h(one)f(of)-118 2503 y(priorit\
y)d(inheritance)i(protocols.)20 b(For)12 b(very)g(lar)o(ge)g(critical)g(secti\
ons,)-118 2552 y(on)g(the)g(other)g(hand,)h(it)f(may)h(be)g(better)f(to)g(use)
g(a)h(restartable)g(critical)-118 2602 y(section)7 b(scheme)i(if)e(the)g(high\
er)f(priority)f(thread)j(cannot)f(af)o(ford)g(to)g(wait)-118 2652 y(for)j(the)
g(lower)g(priority)e(thread)i(to)f(complete)i(its)f(critical)f(section.)-77
2702 y(T)n(able)14 b(2)g(summarizes)h(the)f(execution)f(costs)h(of)f(primitiv\
es,)h fr(lock)-118 2752 y(and)j(acquir)n(ed)p fs(,)k fr(lock)d(and)f(not)h
(acquir)m(ed)p fs(,)j(and)d fr(unlock)g fs(under)f(the)966 77 y(\256ve)11 b
(locking)e(protocols;)h(Basic)h(Priority)e(\(BP\),)i(kernelized)f(monitor)966
127 y(\(KM\),)f(basic)g(priority)e(inheritance)i(\(BPI\),)g(priority)d(ceilin\
g)j(protocol)966 177 y(\(PCP\),)i(and)f(restartable)h(critical)g(section)f
(\(RCS\).)h(The)g fr(lock)h(and)e(ac-)966 226 y(quir)m(ed)i fs(cost)e(include\
s)h(the)g(cost)g(of)f(trap)h(handling,)f fr(rt)r 13 2 v 12 w(mutex)s 13 2 v 12
w(lock)i fs(in)966 276 y(the)e(common)h(lock)f(object,)h(and)f fr(rt)r 13 2 v
13 w(mutex)r 13 2 v 13 w(policy)r 13 2 v 12 w(aquir)n(ed)h fs(function)966 326
y(in)k(a)h(policy)f(object.)32 b(The)16 b fr(lock)g(and)g(not)f(acquir)m(ed)i
fs(cost)f(includes)966 376 y(only)f(the)i(cost)g(for)f(executing)g fr(rt)r 13
2 v 13 w(mutex)r 13 2 v 13 w(policy)r 13 2 v 12 w(notacquir)m(ed)h fs(in)f
(a)966 426 y(policy)11 b(module.)21 b(The)13 b fr(unlock)f fs(cost)g(includes)
g(the)g(cost)g(of)g(trap)g(han-)966 475 y(dling,)7 b fr(rt)r 13 2 v 13 w(mute\
x)s 13 2 v 12 w(unlock)h fs(function)f(in)h(the)g(common)h(lock)f(object,)h
(and)966 525 y fr(rt)r 13 2 v 12 w(mutex)s 13 2 v 12 w(policy)r 13 2 v 13 w
(unlock)h fs(function)f(in)g(a)i(policy)e(object.)1007 575 y(Let)16 b(us)g
(now)g(calculate)g(the)g(cost)f(of)h(locking)e(policies,)j(and)f(de-)966 625 y
(termine)11 b(which)h(protocol)e(is)i(better)f(under)h(what)g(conditions.)18 b
(Here,)966 675 y fo(C)994 655 y fn(p)994 687 y(nullcs)p fm(\(1\))1110 675 y fs
(indicates)11 b(the)g(time)g(for)g(a)h(single)f(thread)g(to)f(execute)j(a)e
(pair)966 725 y(of)e(lock)h(and)g(unlock)f(operations)g(under)h(a)h(given)e
(locking)g(protocol)f fo(p)966 774 y fs(and)i(is)g(de\256ne)h(as)g fo(C)1259
754 y fn(p)1259 787 y(nullcs)p fm(\(1\))1375 774 y fs(=)h fo(C)1438 754 y fn
(p)1438 786 y(syscall)1528 774 y fs(+)e fo(C)1589 754 y fn(p)1589 786 y(acqui\
red)1703 774 y fs(+)g fo(C)1764 754 y fn(p)1764 786 y(unlock)1843 774 y fs
(.)1007 824 y(The)h(measured)h(results)d(for)h(KM,)h(BPI,)f(and)g(PCP)h(are)g
(as)g(follows.)1084 896 y fo(C)1112 881 y fn(km)1112 908 y(nullcs)p fm(\(1\))
1228 896 y fs(=)h fo(C)1291 881 y fn(km)1291 908 y(syscall)1381 896 y fs(+)e
fo(C)1442 881 y fn(km)1442 908 y(acquired)1556 896 y fs(+)g fo(C)1617 881 y fn
(km)1617 908 y(unlock)1708 896 y fs(=)i(288)p fi(\026)p fs(s)1084 954 y fo
(C)1112 934 y fn(bpi)1112 966 y(nullcs)p fm(\(1\))1228 954 y fs(=)g fo(C)1291
934 y fn(bpi)1291 966 y(syscall)1381 954 y fs(+)e fo(C)1442 934 y fn(bpi)1442
966 y(acquired)1556 954 y fs(+)g fo(C)1617 934 y fn(bpi)1617 966 y(unlock)
1708 954 y fs(=)i(388)p fi(\026)p fo(s)1084 1007 y(C)1112 987 y fn(pcp)1112
1019 y(nullcs)p fm(\(1\))1228 1007 y fs(=)g fo(C)1291 987 y fn(pcp)1291 1019 y
(syscall)1381 1007 y fs(+)e fo(C)1442 987 y fn(pcp)1442 1019 y(acquired)1556
1007 y fs(+)g fo(C)1617 987 y fn(pcp)1617 1019 y(unlock)1708 1007 y fs(=)i
(488)p fi(\026)p fo(s)1007 1079 y fs(From)f(the)g(above)g(results,)g(it)g(was)
g(clear)h(that)e(the)h(implementation)966 1129 y(cost)16 b(increased)i(propor\
tional)c(to)i(the)g(complexity)g(of)g(the)g(locking)966 1179 y(protocol.)1007
1228 y(Let)g(us)f(then)g(determine)g(the)g(worst)f(case)j(blocking)c(time)i
(of)g(the)966 1278 y(highest)f(priority)g(thread)i(where)g fo(n)f fs(threads)
h(are)h(sharing)e(the)h(same)966 1328 y(critical)c(lock)h(resource.)26 b(The)
14 b(worst)f(case)i(for)e(the)g(highest)f(priority)966 1378 y(thread)d(may)i
(occur)f(when)g(a)h(lower)e(priority)f(thread)i(is)g(already)g(in)f(the)966
1428 y(critical)j(section.)22 b(Then,)14 b(under)e(BPI)h(or)f(PCP)h(policies,)
f(the)h(highest)966 1478 y(priority)d(thread)j(becomes)i(runnable)d(and)i(pre\
empts)f(the)g(lower)g(pri-)966 1527 y(ority)8 b(thread)i(and)g(attempts)g(to)
g(enter)g(the)g(critical)g(section.)15 b(Since)10 b(the)966 1577 y(resource)h
(is)g(already)g(in)f(use,)i(the)f(highest)f(priority)e(thread')m(s)j(lock)g
(re-)966 1627 y(quest)6 b(will)g(blocks)h(itself)f(and)h(resume)h(the)f(lower)
g(priority)t(thread)g(with)966 1677 y(the)h(highest)f(priority)f(\(due)i(to)g
(priority)d(inversion\).)13 b(Additional)6 b(over-)966 1727 y(head)11 b(may)g
(occur)g(when)g(all)f(other)g(threads)h(become)h(runnable)e(while)966 1776 y
(the)g(lower)g(priority)e(thread)i(is)g(executing)g(in)f(the)h(critical)g(sec\
tion)1938 1761 y fm(1)1954 1776 y fs(.)1007 1826 y(Under)19 b(this)e(assumpti\
on,)j(we)f(can)h(determine)e(the)h(worst)e(case)966 1876 y(blocking)7 b(time)
i fo(C)1231 1856 y fn(p)1231 1888 y(wait)p fm(\()p fn(n)p fm(\))1326 1876 y fs
(for)f(the)h(highest)f(priority)f(thread)i(under)g(lock-)966 1926 y(ing)g(pro\
tocol)g fo(p)h fs(as)h(follows.)1013 1998 y fo(C)1041 1983 y fn(km)1041 2010 y
(wait)p fm(\()p fn(n)p fm(\))1138 1998 y fs(=)h fo(C)1201 2004 y fn(csbody)
1293 1998 y fs(+)d(\()p fo(n)g fj(\000)h fs(1\))f fj(\002)g fo(C)1524 2004 y
fn(activate)1627 1998 y fs(+)h fo(C)1688 1983 y fn(km)1688 2010 y(unlock)1013
2055 y fo(C)1041 2035 y fn(bpi)1041 2067 y(wait)p fm(\()p fn(n)p fm(\))1138
2055 y fs(=)i fo(C)1201 2061 y fn(csbody)1293 2055 y fs(+)d(\()p fo(C)1367
2061 y fn(wakeup)1467 2055 y fs(+)h fo(C)1528 2061 y fn(switch)1613 2055 y fs
(+)f fo(C)1673 2061 y fn(lock)r 13 2 v 13 w(not)q 13 2 v 13 w(acquire)1202
2112 y fs(+)p fo(C)1253 2118 y fn(choose)1345 2112 y fs(+)h fo(C)1406 2118 y
fn(dispatch)1506 2112 y fs(\))f(+)h(\()p fo(n)e fj(\000)i fs(2\))f fj(\002)g
fo(C)1760 2118 y fn(activate)1863 2112 y fs(+)h fo(C)1924 2092 y fn(bpi)1924
2124 y(unlock)1013 2162 y fo(C)1041 2142 y fn(pcp)1041 2175 y(wait)p fm(\()p
fn(n)p fm(\))1138 2162 y fs(=)i fo(C)1201 2168 y fn(csbody)1293 2162 y fs(+)d
(\()p fo(C)1367 2168 y fn(wakeup)1467 2162 y fs(+)h fo(C)1528 2168 y fn(switc\
h)1613 2162 y fs(+)f fo(C)1673 2168 y fn(lock)r 13 2 v 13 w(not)q 13 2 v 13 w
(acquire)1202 2214 y fs(+)p fo(C)1253 2220 y fn(choose)1345 2214 y fs(+)h fo
(C)1406 2220 y fn(dispatch)1506 2214 y fs(\))f(+)h(\()p fo(n)e fj(\000)i fs
(2\))f fj(\002)g fo(C)1760 2220 y fn(activate)1863 2214 y fs(+)h fo(C)1924
2194 y fn(pcp)1924 2227 y(unlock)966 2337 y fs(where)k fo(C)1109 2343 y fn
(csbody)1205 2337 y fs(indicates)f(the)g(cost)h(for)f(executing)g(the)g(body)
g(of)g(the)966 2386 y(critical)d(section)g(alone,)h fo(C)1359 2392 y fn(switc\
h)1446 2386 y fs(represents)g(the)g(total)e(thread)i(switch-)966 2436 y(ing)i
(cost,)j(and)e fo(C)1228 2442 y fn(activate)1336 2436 y fs(is)g(the)g(cost)g
(for)g(making)g(a)g(blocked)g(thread)966 2486 y(runnable.)1007 2536 y(From)i
(T)n(able)g(1)g(and)g(2,)i(we)e(can)h(determine)f(the)g(cost)g(of)g(thread)
966 2586 y(switching)10 b fo(C)1167 2592 y fn(switch)1256 2586 y fs(\(172)h fi
(\026)p fs(s)h(=)h fo(C)1461 2592 y fn(block)1536 2586 y fs(+)e fo(C)1598 2592
y fn(choose)1690 2586 y fs(+)g fo(C)1752 2592 y fn(dispatch)1852 2586 y fs
(\),)i fo(C)1917 2592 y fn(wakeup)966 2635 y fs(is)c(72)g fi(\026)p fs(s,)i fo
(C)1144 2641 y fn(activate)1247 2635 y fs(is)f(108)f fi(\026)p fs(s,)h(and)g
fo(C)1516 2641 y fn(unlock)1605 2635 y fs(for)f(each)i(protocol.)i(Then,)966
2685 y(for)c fo(n)j fi(>)p fs(=)g(2,)e(we)h(can)g(derive)966 2712 y 417 2 v
1011 2740 a fq(1)1025 2752 y fp(Assuming)c(that)i(the)e(system)h(does)f(not)h
(disable)f(all)i(interrupts)e(in)i(KM.)935 2877 y fs( )p eop
%%Page: 7 7
 bop 154 79 a 1581 2 v 45 x 2 46 v 365 w 2 46 v 620 111 a fh(BP)9 b(\()p ff
(\026)p fh(s\))837 124 y 2 46 v 881 111 a(KM)g(\()p ff(\026)p fh(s\))1055 124
y 2 46 v 1111 111 a(BPI)h(\()p ff(\026)p fh(\))1281 124 y 2 46 v 1326 111 a
(PCP)f(\()p ff(\026)p fh(s\))1508 124 y 2 46 v 1551 111 a(RCS)g(\()p ff(\026)
p fh(s\))1735 124 y 2 46 v 154 126 a 1581 2 v 46 x 2 46 v 217 158 a(Lock\(Acq\
uired\))519 172 y 2 46 v 651 158 a(120)837 172 y 2 46 v 919 158 a(132)1055 172
y 2 46 v 1141 158 a(196)1281 172 y 2 46 v 1368 158 a(232)1508 172 y 2 46 v
1594 158 a(256)1735 172 y 2 46 v 154 173 a 1581 2 v 47 x 2 47 v 179 206 a(Loc\
k)f(\(Not)i(Acquired\))519 220 y 2 47 v 591 206 a(208)e(+)h fe(C)711 210 y fd
(block)837 220 y 2 47 v 897 206 a fh(N.A.)969 190 y fq(\2621)1055 220 y 2 47 v
1081 206 a fh(340)f(+)h fe(C)1201 210 y fd(block)1281 220 y 2 47 v 1307 206 a
fh(508)g(+)g fe(C)1428 210 y fd(block)1508 220 y 2 47 v 1534 206 a fh(628)f
(+)i fe(C)1655 210 y fd(block)1735 220 y 2 47 v 154 222 a 1581 2 v 46 x 2 47 v
282 255 a fh(Unlock)519 268 y 2 47 v 545 255 a(144)e(+)h fe(C)665 259 y fd
(activate)756 255 y fg(\002)g fh(n)837 268 y 2 47 v 863 255 a(156)p ff(=)p fh
(180)1004 239 y fq(\2623)1055 268 y 2 47 v 1141 255 a fh(192)1281 268 y 2 47 v
1368 255 a(256)1508 268 y 2 47 v 1594 255 a(196)1735 268 y 2 47 v 154 270 a
1581 2 v -35 336 a fm(\2621)d(No)h(one)f(can)h(preempt.)-35 369 y(\2622)f fc
(m)h fm(is)h(a)f(number)e(of)i(chains)f(of)h(chained)e(locks.)-35 402 y(\2623)
h(The)h(cost)g(of)f(right)g(parts)h(includes)f(the)h(cost)g(to)g(wakeup)f(the)
g(thread)g(waiting)h(a)g(lock.)-35 435 y(\2624)f fc(n)h fm(is)h(a)f(number)e
(of)h(nest)h(of)g(nested)f(locks.)-35 468 y(\2625)g fn(C)20 472 y fk(activate)
96 468 y fm(is)h(the)g(cost)g(for)f(making)g(a)h(blocked)e(thread)h(runnable.)
i(The)f(measured)f(cost)h(is)g(108)f fb(\026)p fm(s.)607 585 y fs(T)n(able)k
(2:)15 b(The)c(Cost)e(of)h(Locking)g(Primitives)0 718 y fo(C)28 703 y fn(km)
28 730 y(wait)p fm(\()p fn(n)p fm(\))125 718 y fs(=)i fo(C)188 724 y fn(csbod\
y)280 718 y fs(+)e(180)e(+)i(\()p fo(n)e fj(\000)i fs(1\))f fj(\002)g fs(108)
p fi(\026)p fs(s)0 775 y fo(C)28 755 y fn(bpi)28 787 y(wait)p fm(\()p fn(n)p
fm(\))125 775 y fs(=)j fo(C)188 781 y fn(csbody)280 775 y fs(+)e(948)e(+)i
(\()p fo(n)e fj(\000)i fs(2\))f fj(\002)g fs(108)p fi(\026)p fs(s)0 827 y fo
(C)28 807 y fn(pcp)28 840 y(wait)p fm(\()p fn(n)p fm(\))125 827 y fs(=)j fo
(C)188 833 y fn(csbody)280 827 y fs(+)e(1180)e(+)h(\()p fo(n)g fj(\000)h fs
(2\))f fj(\002)g fs(108)p fi(\026)p fs(s)-77 913 y(From)16 b(these)g(numbers,)
i(we)e(can)h(conclude)f(that)f(as)h(long)f(as)h(the)-118 963 y(system)k(does)
g(not)f(have)h(any)g(real-time)g(thread)g(whose)f(deadline)-118 1013 y(is)d
(shorter)h(than)f fo(C)175 1019 y fn(csbody)270 1013 y fs(+)e(288)p fi(\026)p
fs(s)i(and)h(the)f(deadline)h(of)f(the)h(real-)-118 1063 y(time)h(thread)f
(which)h(shares)g(the)g(critical)f(section)h(is)f(greater)i(than)-118 1112 y
(2)8 b fj(\002)h fo(C)-20 1118 y fn(csbody)70 1112 y fs(+)g(108)f fj(\002)g fo
(n)g fs(+)h(72)p fi(\026)p fs(s,)h(then)g(we)g(should)f(be)h(able)g(to)f(use)
h(the)-118 1162 y(KM)g(policy)f(among)i fo(n)f fs(real-time)g(thread)g(\()p fo
(n)h fi(>)p fs(=)h(2\).)-77 1213 y(In)18 b(general,)j(the)d(BPI)f(and)h(PCP)g
(protocols)f(are)i(suitable)e(for)h(a)-118 1263 y(lar)o(ge)12 b(critical)f
(section)g(.)20 b(For)11 b(instance,)i(among)f(two)f(synchronizing)-118 1313 y
(threads,)i(the)f(deadline)g(of)g(the)g(threads)h(should)e(be)h(longer)g(than)
g(2)e fj(\002)-118 1362 y fo(C)-90 1368 y fn(csbody)1 1362 y fs(+)f(1336\(=)i
(948)d(+)h(388\))p fi(\026)p fs(s)h(for)f(BPI.)i(Otherwise,)f(it)f(may)i(need)
-118 1412 y(to)k(use)h(KM,)g(if)f(there)g(is)h(no)f(real-time)g(thread)g(whos\
e)h(deadline)f(is)-118 1462 y(shorter)g(than)h(2)c fj(\002)g fo(C)206 1468 y
fn(csbody)301 1462 y fs(+)h(288\(=)19 b(216)12 b(+)g(72\))p fi(\026)p fs(s.)
32 b(Similarly)15 b(for)-118 1512 y(two)c(threads)g(under)g(PCP)-5 b(,)12 b
(the)f(deadline)g(should)f(be)i(lar)o(ger)f(than)g(2)f fj(\002)-118 1562 y fo
(C)-90 1568 y fn(csbody)2 1562 y fs(+)f(1668)p fi(\026)p fs(s.)-77 1612 y(For)
j(a)h(restartable)f(critical)f(section,)i(we)f(could)g(get)f(the)h(restarting)
-118 1662 y(cost,)f fo(C)-2 1647 y fn(rcs)-2 1672 y(restart)87 1662 y fs(as)g
(follows.)-35 1757 y fo(C)-7 1742 y fn(rcs)-7 1767 y(restart)83 1757 y fs(=)f
fo(C)144 1763 y fn(abort)219 1757 y fs(\(=)h(816)f fi(\026)p fs(s\))g(+)h fo
(C)467 1763 y fn(recover)-118 1852 y fs(where)j fo(C)25 1858 y fn(abort)103
1852 y fs(is)f(a)h(cost)f(for)g(aborting)e(a)j(lower)f(priority)e(thread)i
(and)-118 1902 y fo(C)-90 1908 y fn(recover)17 1902 y fs(is)j(a)h(cost)f(for)
g(recovering)g(the)g(state)g(of)g(shared)h(resource.)-118 1951 y fo(C)-90 1957
y fn(recover)20 1951 y fs(is)i(application)f(speci\256c)j(and)e(there)h(are)g
(many)g(dif)n(ferent)-118 2001 y(schemes)14 b(exit.)21 b(From)13 b(this)e(res\
tarting)g(cost,)j(we)f(can)g(also)f(conclude)-118 2051 y(that)e(the)h(restart\
able)g(critical)g(section)g(is)f(a)i(suitable)e(policy)g(if)h fo(C)845 2057 y
fn(restart)-118 2101 y fs(is)f(less)h(than)e fo(C)102 2081 y fn(bpi)102 2113 y
(wait)p fm(\()p fn(n)p fm(\))199 2101 y fs(or)h fo(C)272 2081 y fn(pcp)272
2113 y(wait)p fm(\()p fn(n)p fm(\))357 2101 y fs(.)-118 2224 y fl(4.3)50 b
(Schedulability)10 b(T)l(est:)17 b(Case)c(I)-118 2304 y fs(In)i(the)h(followi\
ng)d(section,)k(we)f(will)f(compare)i(the)e(schedulability)-118 2354 y(of)f
(various)g(periodic)g(threads)g(under)g(dif)o(ferent)g(locking)f(protocols:)
-118 2403 y(KM,)g(BP)-5 b(,)12 b(BPI,)h(PCP)-5 b(,)13 b(and)f(RCS)g(using)f
(few)i(benchmark)g(programs.)-118 2453 y(In)f(this)f(Benchmark-1)i(program,)g
(there)f(are)i(four)d(periodic)h(threads:)-118 2503 y fo(Th)-74 2509 y fn(A)
-54 2503 y fs(,)h fo(Th)13 2509 y fn(B)32 2503 y fs(,)h fo(Th)100 2509 y fn
(C)133 2503 y fs(and)f fo(Th)250 2509 y fn(D)273 2503 y fs(.)21 b fo(Th)348
2509 y fn(A)380 2503 y fs(has)13 b(the)f(highest)f(priority)-5 b(,)13 b fo
(Th)832 2509 y fn(B)864 2503 y fs(and)-118 2553 y fo(Th)-74 2559 y fn(C)-45
2553 y fs(are)8 b(medium,)h(and)f fo(Th)280 2559 y fn(D)310 2553 y fs(is)g
(the)f(lowest)g(priority)-5 b(.)15 b fo(Th)711 2559 y fn(D)741 2553 y fs(is)8
b(executed)-118 2603 y(\256rst,)13 b fo(Th)14 2609 y fn(B)47 2603 y fs(and)f
fo(Th)163 2609 y fn(C)197 2603 y fs(are)i(executed)f(next.)22 b(Lastly)m(,)13
b fo(Th)693 2609 y fn(A)726 2603 y fs(is)f(executed.)-118 2652 y fo(Th)-74
2658 y fn(A)-40 2652 y fs(and)j fo(Th)79 2658 y fn(D)116 2652 y fs(share)g
(the)f(same)i(object.)27 b(At)14 b(the)h(beginning)d(of)i(the)-118 2702 y(exe\
cution,)d(each)h(thread)f(locks)g(the)g(shared)g(object)g(and)g(releases)h
(the)-118 2752 y(object)c(at)h(the)g(end.)15 b(The)10 b(timing)d(attributes)h
(of)g(each)i(thread)f(are)h(given)1135 720 y 703 2 v 33 x 2 34 v 1174 743 a fm
(Thread)1295 753 y 2 34 v 8 w 2 34 v 1329 743 a fn(T)1345 747 y fk(i)1360 743
y fm(\(ms\))1438 753 y 2 34 v 1463 743 a fn(C)1482 747 y fk(i)1498 743 y fm
(\(ms\))1575 753 y 2 34 v 1601 743 a fn(S)1616 747 y fk(i)1630 743 y fm(\(ms\
\))1708 753 y 2 34 v 1734 743 a fn(U)1755 747 y fk(i)1770 743 y fm(\(%\))1837
753 y 2 34 v 1135 755 a 703 2 v 10 x 703 2 v 1134 798 a 2 34 v 1160 788 a(Thr\
ead)c(A)1295 798 y 2 34 v 8 w 2 34 v 1349 788 a(100)1438 798 y 2 34 v 1493 788
a(10)1575 798 y 2 34 v 1628 788 a(20)1708 798 y 2 34 v 1759 788 a(10)1837 798
y 2 34 v 1135 800 a 703 2 v 1134 837 a 2 38 v 1161 824 a(Thread)g(B)1295 837 y
2 38 v 8 w 2 38 v 1349 824 a(300)1438 837 y 2 38 v 1479 824 a(EXE)1575 837 y 2
38 v 1628 824 a(10)1708 837 y 2 38 v 1754 813 a fk(EXE)1754 818 y 39 2 v 1755
837 a fq(300)46 b 2 38 v 1135 839 a 703 2 v 33 x 2 34 v 1161 862 a fm(Thread)
6 b(C)1295 872 y 2 34 v 8 w 2 34 v 1349 862 a(400)1438 872 y 2 34 v 1493 862 a
(60)1575 872 y 2 34 v 1628 862 a(10)1708 872 y 2 34 v 1759 862 a(15)1837 872 y
2 34 v 1135 874 a 703 2 v 1134 907 a 2 34 v 1160 897 a(Thread)g(D)1295 907 y 2
34 v 8 w 2 34 v 1342 897 a(1000)1438 907 y 2 34 v 1493 897 a(30)1575 907 y 2
34 v 1635 897 a(0)1708 907 y 2 34 v 1766 897 a(3)1837 907 y 2 34 v 1135 908 a
703 2 v 1124 1024 a fs(T)n(able)k(3:)15 b(Thread)c(Attributes)d(of)i(Benchmar\
k-1)1174 1122 y 626 2 v 1173 1156 a 2 34 v 1199 1146 a fm(Lock)c(Policy)1364
1156 y 2 34 v 9 w 2 34 v 1398 1146 a(Max)h(Exec)f(T)o(ime)h(\(ms\))1669 1156 y
2 34 v 1695 1146 a fn(U)1716 1150 y fk(i)1731 1146 y fm(\(%\))1799 1156 y 2 34
v 1174 1157 a 626 2 v 10 x 626 2 v 1173 1201 a 2 34 v 1252 1191 a(BP)1364 1201
y 2 34 v 9 w 2 34 v 1507 1191 a(14)1669 1201 y 2 34 v 1709 1191 a(32.6)1799
1201 y 2 34 v 1174 1202 a 626 2 v 1173 1235 a 2 34 v 1247 1225 a(BPI)1364 1235
y 2 34 v 9 w 2 34 v 1500 1225 a(181)1669 1235 y 2 34 v 1709 1225 a(88.3)1799
1235 y 2 34 v 1174 1237 a 626 2 v 1173 1270 a 2 34 v 1246 1260 a(KM)1364 1270
y 2 34 v 9 w 2 34 v 1500 1260 a(183)1669 1270 y 2 34 v 1720 1260 a(89)1799
1270 y 2 34 v 1174 1272 a 626 2 v 1173 1305 a 2 34 v 1244 1295 a(PCP)1364 1305
y 2 34 v 9 w 2 34 v 1500 1295 a(181)1669 1305 y 2 34 v 1709 1295 a(88.3)1799
1305 y 2 34 v 1174 1307 a 626 2 v 1173 1340 a 2 34 v 1242 1330 a(RCS)1364 1340
y 2 34 v 9 w 2 34 v 1500 1330 a(202)1669 1340 y 2 34 v 1709 1330 a(95.3)1799
1340 y 2 34 v 1174 1342 a 626 2 v 1052 1457 a fs(T)m(able)k(4:)j(Breakdown)c
(Utilization)e(under)i(Benchmark-1)966 1587 y(in)d(T)m(able)h(3.)15 b fo(C)
1179 1593 y fn(i)1196 1587 y fs(represents)9 b(the)e(worst)g(case)j(execution)
d(time)h(of)f(thread)966 1637 y fo(Th)1010 1643 y fn(i)1020 1637 y fs(.)20 b
fo(B)1075 1643 y fn(i)1097 1637 y fs(indicates)12 b(the)g(worst)f(case)i(bloc\
king)e(time)g(of)h fo(Th)1841 1643 y fn(i)1863 1637 y fs(and)g fo(T)1958 1643
y fn(i)1980 1637 y fs(is)966 1687 y(the)g(period)g(of)g fo(Th)1239 1693 y fn
(i)1249 1687 y fs(.)22 b fo(U)1311 1693 y fn(i)1334 1687 y fs(is)12 b(the)h
(processor)f(utilization)e(of)j fo(Th)1882 1693 y fn(i)1904 1687 y fs(and)g fo
(S)1998 1693 y fn(i)966 1737 y fs(indicates)d(the)g(start)g(time)g(of)g(aperi\
odic)g(thread)g fo(Th)1719 1743 y fn(i)1729 1737 y fs(.)1007 1789 y(For)f(eac\
h)i(locking)d(protocol,)h(we)h(compared)g(the)g(breakdown)f(pro-)966 1839 y
(cessor)19 b(utilization)e(while)h(we)h(vary)g(the)f(execution)g(time)h(of)g
fo(Th)1987 1845 y fn(C)966 1888 y fs(\(i.e.,)g fh(EXE)e fs(in)f(T)n(able)h
(3\).)34 b(T)n(able)17 b(4)g(shows)f(the)h(execution)f(results)966 1938 y(of)
8 b(Benchmark-1.)15 b(The)9 b(result)f(indicates)g(that)g(the)g(priority)e
(inversion)966 1988 y(degrades)12 b(the)f(schedulability)e(signi\256cantly)h
(and)i(priority)d(queueing)966 2038 y(alone)g(does)g(not)f(solve)g(the)h(prio\
rity)d(inversion)i(problem.)14 b(Thus,)c(KM,)966 2088 y(BPI,)d(PCP)-5 b(,)8 b
(or)e(RCS)h(is)g(a)h(very)e(effective)h(policy)f(in)h(real-time)g(synchro-)
966 2138 y(nization.)13 b(Also,)d(this)e(benchmark)i(result)f(indicates)g(tha\
t)f(RCS)h(policy)966 2187 y(could)i(achieve)h(the)f(highest)g(schedulability)
f(among)h(these)h(policies,)966 2237 y(if)h fo(C)1033 2222 y fn(rcs)1033 2247
y(restart)1126 2237 y fs(is)h(signi\256cantly)e(small.)27 b(Since)14 b(it)f
(can)i(abort)e(the)h(critical)966 2287 y(section)f(of)g(the)g(lower)g(priorit\
y)d(thread,)15 b(the)e(higher)f(priority)f(thread)966 2337 y(need)e(not)f(to)
g(wait)g(for)h(the)f(termination)g(of)g(the)h(lower)f(priority)f(thread.)966
2468 y fl(4.4)50 b(Schedulability)10 b(T)-5 b(est:)18 b(Case)13 b(II)966 2550
y fs(The)e(previous)e(benchmark)i(shows)f(that)g(KM,)h(BPI,)f(and)h(PCP)f(pol\
icy)966 2600 y(may)e(achieve)h(relatively)e(high)g(schedulability)f(for)i(the)
g(given)g(taskset.)1007 2652 y(Benchmark-2)j(presents)h(that)e(this)g(is)h
(not)g(always)g(true)g(under)g(dif-)966 2702 y(ferent)i(taskset.)24 b(In)13 b
(this)f(program,)i(we)g(consider)e(two)h(threads,)h fo(Th)1988 2708 y fn(A)
966 2752 y fs(and)d fo(Th)1081 2758 y fn(B)1101 2752 y fs(.)18 b fo(Th)1173
2758 y fn(A)1204 2752 y fs(is)12 b(the)f(highest)f(priority)f(thread,)j(and)g
(it)e(is)h(started)g(10)935 2877 y( )p eop
%%Page: 8 8
 bop 52 79 a 703 2 v 51 112 a 2 34 v 91 102 a fm(Thread)211 112 y 2 34 v 8 w 2
34 v 245 102 a fn(T)261 106 y fk(i)276 102 y fm(\(ms\))354 112 y 2 34 v 380
102 a fn(C)399 106 y fk(i)414 102 y fm(\(ms\))491 112 y 2 34 v 517 102 a fn
(S)532 106 y fk(i)547 102 y fm(\(ms\))624 112 y 2 34 v 650 102 a fn(U)671 106
y fk(i)686 102 y fm(\(%\))754 112 y 2 34 v 52 114 a 703 2 v 9 x 703 2 v 51 157
a 2 34 v 77 147 a(Thread)5 b(A)211 157 y 2 34 v 8 w 2 34 v 266 147 a(100)354
157 y 2 34 v 409 147 a(20)491 157 y 2 34 v 544 147 a(10)624 157 y 2 34 v 675
147 a(20)754 157 y 2 34 v 52 158 a 703 2 v 51 196 a 2 38 v 77 183 a(Thread)h
(B)211 196 y 2 38 v 8 w 2 38 v 266 183 a(200)354 196 y 2 38 v 395 183 a(EXE)
491 196 y 2 38 v 551 183 a(0)624 196 y 2 38 v 671 172 a fk(EXE)671 177 y 39 2
v 19 x fq(200)47 b 2 38 v 52 198 a 703 2 v 41 313 a fs(T)m(able)11 b(5:)j(Thr\
ead)d(Attributes)d(of)i(Benchmark-2)90 409 y 626 2 v 89 442 a 2 34 v 115 432 a
fm(Lock)c(Policy)281 442 y 2 34 v 8 w 2 34 v 315 432 a(Max)g(Exec)g(T)o(ime)h
(\(ms\))585 442 y 2 34 v 611 432 a fn(U)632 436 y fk(i)647 432 y fm(\(%\))715
442 y 2 34 v 90 444 a 626 2 v 9 x 626 2 v 89 487 a 2 34 v 163 477 a(BPI)281
487 y 2 34 v 8 w 2 34 v 416 477 a(155)585 487 y 2 34 v 626 477 a(97.5)715 487
y 2 34 v 90 488 a 626 2 v 89 522 a 2 34 v 162 512 a(KM)281 522 y 2 34 v 8 w 2
34 v 423 512 a(88)585 522 y 2 34 v 636 512 a(64)715 522 y 2 34 v 90 523 a 626
2 v 89 556 a 2 34 v 160 546 a(PCP)281 556 y 2 34 v 8 w 2 34 v 423 546 a(87)
585 556 y 2 34 v 626 546 a(63.5)715 556 y 2 34 v 90 558 a 626 2 v 34 674 a fs
(T)n(able)j(6:)15 b(BPI,)10 b(KM,)h(PCP)f(under)g(Benchmark-2)-118 806 y(ms)k
(after)f fo(Th)77 812 y fn(B)110 806 y fs(starts.)23 b(The)14 b(timing)e(attr\
ibutes)g(of)g fo(Th)690 812 y fn(A)723 806 y fs(and)i fo(Th)841 812 y fn(B)
873 806 y fs(are)-118 856 y(given)e(in)g(T)m(able)h(5.)22 b fo(Th)233 862 y fn
(B)265 856 y fs(contains)12 b(a)i(critical)d(section,)j(and)e(we)h(vary)-118
906 y(the)d(length)f(of)h(the)g(critical)g(section)g(during)f(the)h(test.)-77
956 y(W)m(e)15 b(compared)g(BPI)e(with)g(KM)h(and)g(PCP)g(under)g(Benchmark-2\
.)-118 1006 y(T)m(able)i(6)f(summarize)h(the)f(breakdown)g(utilization)e(of)h
(each)j(policy)l(.)-118 1056 y(Although)10 b(PCP)h(has)h(nice)g(properties)f
(such)h(as)g(deadlock)g(free)g(prop-)-118 1106 y(erty)m(,)e(the)f(result)g
(indicates)g(that)g(PCP)g(could)g(not)g(achieve)h(at)g(the)f(same)-118 1156 y
(level)j(as)h(BPI)g(scheme.)23 b(If)12 b(the)h(taskset)f(is)h(deadlock)f(free)
h(in)f(nature,)-118 1206 y(then)e(BPI)g(policy)f(is)h(the)g(best)g(scheme.)
-77 1256 y(W)m(e)i(also)f(compared)g(BPI)g(and)g(RCS)g(policy)f(under)g(Bench\
mark-3)-118 1306 y(program.)22 b(In)12 b(general,)i(RCS)e(becomes)i(useful)f
(if)f(a)h(higher)f(priority)-118 1356 y(thread)e(cannot)g(afford)g(to)f(wait)
i(for)f(a)g(lower)h(priority)d(thread)i(to)g(com-)-118 1406 y(plete)h(the)g
(critical)g(section.)18 b(However)o(,)12 b(restarting)e(a)i(critical)f(sectio\
n)-118 1456 y(requires)f(not)g(only)g(the)h(cost)g(of)f(aborting)f(of)i(the)f
(critical)h(section)f(but)-118 1505 y(also)i(the)g(restarting)g(cost.)21 b
(The)13 b(schedulability)e(may)h(be)h(decreased,)-118 1555 y(if)d(these)g(cos\
ts)h(dominates)f(the)g(total)f(overhead.)-77 1606 y(Unlike)f(Benchmark-1,)i
(Benchmark-3)f(indicates)g(the)f(case)j(where)-118 1656 y(RCS)f(has)g(signi\
\256cantly)f(lower)h(break)h(down)e(utilization)f(than)i(BPI.)-77 1706 y(V)l
(arious)e(benchmark)h(programs)f(we)h(presented)g(in)f(this)g(section)g(in-)
-118 1756 y(dicates)h(that)g(there)g(is)g(no)f(best)h(policy)f(for)h(all)f
(real-time)h(applications.)-118 1806 y(A)16 b(system)g(designer)g(needs)g(to)
f(select)i(a)f(suitable)f(policy)g(for)g(their)-118 1856 y(applications.)-118
2001 y ft(5)60 b(Related)13 b(W)m(ork)-118 2095 y fs(The)c(micro)e(kernel-bas\
ed)i(approach)f(is)g(gaining)e(popularity)g(and)i(sev-)-118 2145 y(eral)g(mic\
ro)g(kernel-based)g(operating)f(systems)h(have)g(been)h(developed)-118 2195 y
(for)h(an)g(advanced)h(distributed)d(computing)h(environment)g([4,)i(9,)f(11]\
.)-77 2245 y(Advantages)17 b(of)f(using)g(a)h(micro)f(kernel)h(instead)f(of)g
(a)h(standard)-118 2295 y(monolithic)8 b(kernel)i(is)f(its)g(high)g(preemptab\
ility)l(,)h(small)g(size,)h(and)f(ex-)-118 2345 y(tensibility)-6 b(.)22 b(How\
ever)n(,)13 b(only)f(a)g(few)h(micro)f(kernels)h(were)g(designed)52 2482 y 703
2 v 51 2515 a 2 34 v 91 2505 a fm(Thread)211 2515 y 2 34 v 8 w 2 34 v 245 2505
a fn(T)261 2509 y fk(i)276 2505 y fm(\(ms\))354 2515 y 2 34 v 380 2505 a fn
(C)399 2509 y fk(i)414 2505 y fm(\(ms\))491 2515 y 2 34 v 517 2505 a fn(S)532
2509 y fk(i)547 2505 y fm(\(ms\))624 2515 y 2 34 v 650 2505 a fn(U)671 2509 y
fk(i)686 2505 y fm(\(%\))754 2515 y 2 34 v 52 2517 a 703 2 v 10 x 703 2 v 51
2560 a 2 34 v 77 2550 a(Thread)5 b(A)211 2560 y 2 34 v 8 w 2 34 v 266 2550 a
(100)354 2560 y 2 34 v 409 2550 a(20)491 2560 y 2 34 v 544 2550 a(50)624 2560
y 2 34 v 675 2550 a(20)754 2560 y 2 34 v 52 2562 a 703 2 v 51 2599 a 2 38 v 77
2586 a(Thread)h(B)211 2599 y 2 38 v 8 w 2 38 v 266 2586 a(150)354 2599 y 2 38
v 395 2586 a(EXE)491 2599 y 2 38 v 544 2586 a(60)624 2599 y 2 38 v 671 2575 a
fk(EXE)671 2580 y 39 2 v 19 x fq(150)47 b 2 38 v 52 2601 a 703 2 v 51 2634 a 2
34 v 77 2624 a fm(Thread)6 b(C)211 2634 y 2 34 v 8 w 2 34 v 266 2624 a(200)
354 2634 y 2 34 v 409 2624 a(60)491 2634 y 2 34 v 551 2624 a(0)624 2634 y 2 34
v 675 2624 a(30)754 2634 y 2 34 v 52 2636 a 703 2 v 42 2751 a fs(T)m(able)11 b
(7:)j(Thread)d(Attributes)e(in)g(Benchmark-3)1174 79 y 626 2 v 1173 112 a 2 34
v 1199 102 a fm(Lock)d(Policy)1364 112 y 2 34 v 9 w 2 34 v 1398 102 a(Max)h
(Exec)f(T)o(ime)h(\(ms\))1669 112 y 2 34 v 1695 102 a fn(U)1716 106 y fk(i)
1731 102 y fm(\(%\))1799 112 y 2 34 v 1174 114 a 626 2 v 9 x 626 2 v 1173 157
a 2 34 v 1247 147 a(BPI)1364 157 y 2 34 v 9 w 2 34 v 1507 147 a(60)1669 157 y
2 34 v 1720 147 a(90)1799 157 y 2 34 v 1174 158 a 626 2 v 1173 192 a 2 34 v
1242 182 a(RCS)1364 192 y 2 34 v 9 w 2 34 v 1507 182 a(15)1669 192 y 2 34 v
1720 182 a(60)1799 192 y 2 34 v 1174 193 a 626 2 v 1134 309 a fs(T)m(able)k
(8:)j(BPI)c(vs.)15 b(RCS)10 b(under)g(Benchmark-3)966 440 y(for)h(supporting)
f(predictable)i(distributed)e(real-time)i(computing)f(en-)966 490 y(vironment\
.)1007 543 y(For)17 b(instance,)h(Chorus')m(s)f(micro)f(kernel[11)o(])h(was)g
(designed)f(for)966 593 y(real-time)g(applications.)32 b(However)o(,)18 b(the\
ir)e(emphasis)h(was)g(placed)966 642 y(at)d(rather)g(low-level)f(kernel)h(fun\
ctions)e(such)j(as)f(providing)e(a)j(user)o(-)966 692 y(de\256ned)g(interrupt)
f(handler)h(and)g(preemptive)h(kernel.)30 b(The)16 b(kernel)966 742 y(uses)f
(the)f(wired-in)f(\256xed)h(priority)e(preemptive)j(scheduling)e(policy)966
792 y(and)j(there)g(is)g(no)f(additional)g(features)h(reported)g(to)f(avoid)g
(priority)966 842 y(inversion)9 b(problems.)1007 894 y(The)16 b(V)f(kernel')m
(s)g(emphasis)h(was)f(also)g(intended)f(for)g(supporting)966 944 y(high)f(spe\
ed)i(real-time)f(applications[4)o(].)27 b(V')n(s)15 b(optimized)e(message)966
994 y(passing)6 b(mechanism)j(and)e(VMTP)g(protocol)f(can)i(provide)e(basic)h
(func-)966 1044 y(tions)j(for)h(building)e(distributed)g(real-time)i(applicat\
ions.)17 b(However)n(,)966 1094 y(the)9 b(wired-in)g(scheduling)g(policy)g
(and)h(locking)f(protocol)f(may)j(cause)966 1143 y(us)f(a)h(potential)d(inver\
sion)h(problem.)1007 1196 y(Amoeba')n(s)14 b(advantage)g(is)g(its)f(high)g
(performance)h(RPC)g(and)f(was)966 1246 y(used)c(for)g(remote)h(video)f(image)
h(transmission)f(using)f(Ethernet.)15 b(Like)966 1296 y(Real-T)n(ime)i(Mach,)
h(Amoeba)f(can)f(support)f(a)h(set)h(of)e(single)g(board)966 1346 y(computers)
j(without)e(having)h(local)h(disks,)i(however)n(,)g(it)e(does)g(not)966 1396 y
(provide)8 b(any)h(safe)h(mechanisms)g(for)f(creating)g(a)h(periodic)e(thread)
h(and)966 1445 y(avoiding)f(priority)g(inversion)h(problems.)1007 1498 y(The)
18 b(POSIX-Thread)g(proposal[7)n(])g(is)f(very)g(similar)g(to)g(Mach')n(s)966
1548 y(C-Thread)e(package[5)q(].)31 b(However)n(,)18 b(it)d(also)g(does)h(not)
f(distinguish)966 1598 y(between)6 b(real-time)h(threads)f(and)g(non-real-tim\
e)g(threads.)13 b(Like)7 b(Real-)966 1648 y(T)o(ime)17 b(Mach,)i(it)d(can)h
(dynamically)f(select)i(the)e(thread)h(scheduling)966 1697 y(policy)l(.)e(A)9
b(POSIX)g(thread)f(also)h(contains)g(the)f(thread)h(attributes)f(such)966 1747
y(as)13 b fr(inherit)e(priority)p fs(,)i fr(scheduling)f(priority)p fs(,)g fr
(scheduling)g(policy)p fs(,)h(and)966 1797 y fr(minimum)8 b(stack)h(size)p fs
(.)15 b(Thus,)10 b(adding)f(our)g(timing)e(attributes)h(into)g(the)966 1847 y
(proposed)h(POSIX)h(interface)h(would)e(be)i(very)f(simple.)1007 1900 y(Uniqu\
eness)16 b(of)h(Real-T)n(ime)g(Mach)g(is)g(based)g(on)f(our)g(real-time)966
1949 y(thread)7 b(and)h(synchrozation)f(model.)14 b(The)8 b(proposed)f(real-t\
ime)h(thread)966 1999 y(model)j(is)g(dif)n(ferent)g(from)g(many)h(other)e(thr\
ead)h(models.)18 b(Our)11 b(model)966 2049 y(distinguishes)f(between)i(real-t\
ime)g(and)g(non)g(real-time)g(threads)g(and)966 2099 y(we)c(provide)f(explici\
t)g(timing)g(constraints)g(for)g(each)j(real-time)e(thread.)966 2149 y(A)14 b
(suitable)f(synchrozation)f(policy)h(such)h(as)h(KM,)f(BPI,)g(PCP)-5 b(,)14 b
(RCS)966 2199 y(can)h(be)g(selected)g(to)f(avoid)g(unbounded)f(priority)f(inv\
ersion)h(and)i(to)966 2248 y(improve)9 b(the)h(schedulability)f(of)h(the)g
(given)f(taskset.)966 2405 y ft(6)59 b(Conclusion)15 b(and)g(Futur)o(e)f(W)m
(ork)966 2503 y fs(W)m(e)c(demonstrated)h(that)e(using)h(new)h(real-time)f
(thread)g(and)h(synchro-)966 2553 y(nization)16 b(facility)g(in)h(Real-T)o
(ime)h(Mach,)j(a)d(user)f(could)g(eliminate)966 2603 y(unbounded)c(priority)g
(inversion)h(problems)g(among)i(synchronizing)966 2652 y(threads.)g(W)l(e)11 b
(also)g(described)g(the)f(schedulability)e(analysis)j(for)f(real-)966 2702 y
(time)j(programs)h(in)f(a)h(single)f(CPU)g(environment.)24 b(The)15 b(system)
f(in-)966 2752 y(terface)h(for)e(creating)h(periodic)f(and)i(aperiodic)e(thre\
ads,)j(creating)d(a)935 2877 y( )p eop
%%Page: 9 9
 bop -118 77 a fs(mutex)12 b(variable,)h(and)g(locking)e(and)h(unlocking)f
(mutex)h(was)h(natural)-118 127 y(and)d(easy)h(to)f(specify)g(a)h(user)g(poli\
cy)e(for)h(a)g(speci\256c)i(application.)-77 177 y(W)m(e)g(also)f(analyzed)h
(the)f(performance)i(of)d(proposed)h(locking)f(pro-)-118 226 y(tocols,)g(KM,)
h(BP)-5 b(,)11 b(BPI,)g(PCP)-5 b(,)11 b(and)f(RCS,)h(and)f(determined)h(the)f
(worst)-118 276 y(case)i(blocking)c(cost)i(for)g(real-time)g(threads.)15 b
(From)10 b(the)g(analysis,)h(we)-118 326 y(could)i(determine)g(which)h(policy)
e(should)g(be)i(effective)f(under)g(what)-118 376 y(conditions.)-77 426 y(How\
ever)o(,)19 b(these)f(primitives)e(alone)h(cannot)h(eliminate)f(priority)-118
475 y(inversion)10 b(problems)i(in)f(the)g(systems.)20 b(Our)12 b(plan)f(is)g
(to)h(remodel)f(the)-118 525 y(Mach)d(IPC)e(feature)i(so)f(that)f(it)g(can)i
(support)e(a)h(priority-based)e(message)-118 575 y(handling)i(and)i(dif)o(fer\
ent)f(types)h(of)g(transport)e(protocols)h(for)g(real-time)-118 625 y(message)
j(transmission.)j(The)c(basic)f(issues)h(has)f(been)h(discussed)f(and)-118 675
y(evaluated)k(in)f(our)h(experimental)g(tested)f([13,)h(14].)23 b(For)13 b
(instance,)h(a)-118 725 y(priority)5 b(inversion)i(may)h(occur)g(when)g(a)g
(client)f(requests)h(for)f(a)i(service)-118 774 y(to)e(a)h(non-preemptive)e
(server)n(.)14 b(A)8 b(higher)n(-priority)d(client)h(may)i(face)h(an)-118 824
y(unbounded)i(priority)g(inversion)h(problem)g(at)h(the)g(server)n(.)24 b(T)m
(o)13 b(avoid)-118 874 y(this)h(problem,)h(one)g(solution)e(is)i(to)f(add)h
(a)g fr(port)f(attribute)f fs(for)h(each)-118 924 y(port)d(and)i(allow)f(us)h
(to)f(set)g(a)h(dif)o(ferent)f(priority)f(inheritance)h(policy)l(,)-118 974 y
(like)17 b(the)g(lock)h(attribute)e(we)i(implemented.)38 b(Real-time)17 b(net\
work)-118 1023 y(support)11 b(is)h(also)h(important)e(and)h(we)h(are)h(planni\
ng)c(to)i(create)i(a)f(new)-118 1073 y(netserver)e(facility)f(where)i(protoco\
l)d(processing)i(will)f(be)h(performed)-118 1123 y(by)f(multiple)f(worker)g
(threads)i(based)g(on)f(a)g(message)i(priority)-5 b(.)-118 1263 y ft(Refer)o
(ences)-93 1351 y fh([1])22 b(M.J.)8 b(Accetta,)f(W)m(.)g(Baron,)h(R.V)-5 b
(.)8 b(Bolosky)l(,)g(D.B.)g(Golub,)g(R.F)m(.)15 b(Rashid,)-28 1397 y(A.)7 b
(T)m(evanian,)f(and)f(M.W)n(.)i(Y)l(oung,)h(\252Mach:)k(A)6 b(new)g(kernel)g
(foundation)-28 1442 y(for)12 b(unix)g(development\272,)19 b fa(In)13 b(Pr)m
(oceedings)d(of)i(the)g(Summer)e(Usenix)-28 1488 y(Confer)m(ence,)p fh(,)f
(July)m(,)g(1986.)-93 1566 y([2])-21 1558 y(\310)-28 1566 y(Ozalp)h(Babaoglu,)
17 b(\252Fault-T)m(olerant)10 b(Computing)h(Based)e(on)h(Mach\272,)-28 1612 y
(In)f fa(Pr)n(oceedings)e(of)i(USENIX)g(Mach)g(W)l(orkshop)p fh(,)f(October)m
(,)i(1990.)-93 1690 y([3])22 b(R.)10 b(Chen)f(and)g(T)m(.P)l(.)i(Ng,)k(\252Bu\
ilding)10 b(a)f(Fault-T)n(olerant)h(System)f(Based)-28 1735 y(on)d(Mach\272,)
j(In)e fa(Pr)n(oceedings)t(of)g(USENIX)g(Mach)f(W)m(orkshop)p fh(,)f(October)
n(,)-28 1781 y(1990.)-93 1859 y([4])22 b(D.R.)11 b(Cheriton,)f(G.R.)h(Whitehe\
ad)e(and)h(E.D.)g(Sznyter)n(,)16 b(\252Binary)10 b(em-)-28 1905 y(ulation)i
(of)h(UNIX)g(using)f(V)g(Kernel\272,)23 b fa(In)13 b(pr)n(oceedings)d(of)j
(Summer)-28 1951 y(Usenix)8 b(Confer)m(ence,)g fh(June,)h(1990.)-93 2029 y
([5])22 b(E.)15 b(C.)g(Cooper)m(,)i(and)c(R.)i(P)l(.)g(Draves,)28 b(\252C)14 b
(threads\272,)28 b(T)m(echnical)14 b(re-)-28 2074 y(port,)f(Computer)e(Scienc\
e)f(Department,)i(Carnegie)f(Mellon)h(Univer-)-28 2120 y(sity)m(,)e(CMU-CS-88\
-154,)f(March,)g(1987.)-93 2198 y([6])22 b(D.)17 b(Golub,)h(R.)f(Dean,)g(A.)g
(Forin,)i(and)c(R.)i(Rashid,)33 b(\252Unix)16 b(as)g(an)-28 2244 y(applicatio\
n)e(program\272,)29 b fa(In)16 b(the)e(pr)n(oceedings)f(of)i(Summer)e(Usenix)
-28 2289 y(Confer)m(ence)p fh(,)8 b(June,)g(1990.)-93 2368 y([7])22 b(IEEE,)j
(\252Realtime)13 b(Extension)f(for)i(Portable)g(Operating)f(Systems\272,)-28
2413 y(P1003.4/Draft6,)c(February)l(,)h(1989.)-93 2491 y([8])22 b(C.)10 b(L.)
g(Liu)g(and)f(J.)g(W)m(.)h(Layland,)k(\252Scheduling)8 b(algorithms)h(for)i
(multi-)-28 2537 y(programming)f(in)i(a)f(hard)f(real)h(time)h(environment\
\272,)18 b fa(Journal)9 b(of)i(the)-28 2583 y(ACM,)e fh(V)l(ol.20,)g(No.1,)g
(1973.)-93 2661 y([9])22 b(S.J.)9 b(Mullender)o(,)h(G.V)-5 b(.)10 b(Rossum,)e
(A.S.)i(T)n(anenbaum,)d(R.)j(Renesse)d(and)-28 2706 y(H.)i(Staveren,)j(\252Am\
oeba:)f(A)e(Distributed)g(Operating)f(System)g(for)h(the)-28 2752 y(1990s\272\
,)i fa(IEEE)f(Computer)d fh(V)l(ol.23,)i(No.5,)g(May)m(,)h(1990)973 77 y([10])
21 b(R.)13 b(Rajkumar)n(,)26 b(\252T)m(ask)12 b(Synchronization)g(in)h(Real-T)
o(ime)g(Systems\272,)1056 123 y(Ph.D.)c(Dissertation,)g(Carnegie)f(Mellon)i
(University)m(,)g(August,)e(1989.)973 202 y([11])21 b(M.)e(Rozier)n(,)i(V)-5 b
(.)19 b(Abrossimov)m(,)i(F)m(.)e(Armand,)i(I.)e(Boule,)i(M.)e(Gien,)1056 247 y
(M.)6 b(Guillemount,)g(F)m(.)g(Herrmann,)g(C.)g(Kaiser)n(,)h(S.)f(Langlois,)f
(P)l(.)h(L)r(\302)-14 b(eonard,)1056 293 y(and)5 b(W)m(.)i(Neuhauser)l(,)j
(\252Chorus)5 b(distributed)h(operating)g(system\272,)i fa(Com-)1056 339 y
(puting)15 b(Systems)g(Journal)p fh(,)i(The)e(Usenix)h(Association,)h(Decembe\
r)m(,)1056 384 y(1988)973 463 y([12])k(L.)11 b(Sha,)g(R.)h(Rajkumar)n(,)g(and)
e(J.)h(P)l(.)g(Lehoczky)-5 b(,)20 b(\252Priority)12 b(inheritance)1056 509 y
(protocols:)f(An)6 b(approach)f(to)h(real-time)h(synchronization\272,)g(T)m
(echnical)1056 554 y(Report)i(CMU-CS-87-181,)h(Carnegie)f(Mellon)h(University)
m(,)g(Novem-)1056 600 y(ber)f(1987)973 679 y([13])21 b(H.)12 b(T)m(okuda)e
(and)h(C.)i(W)m(.)f(Mercer)n(,)22 b(\252AR)m(TS:)12 b(A)g(distributed)g(real-\
time)1056 725 y(kernel\272,)23 b fa(ACM)13 b(Operating)f(Systems)f(Review)p fh
(,)i(V)l(ol.23,)h(No.3,)g(July)m(,)1056 770 y(1989.)973 849 y([14])21 b(H.)8 b
(T)m(okuda,)g(C.)g(W)m(.)h(Mercer)n(,)g(Y)-5 b(.)9 b(Ishikawa,)f(and)f(T)m
(.)i(E.)f(Marchok,)j(\252Pri-)1056 895 y(ority)d(inversions)f(in)h(real-time)
h(communication\272,)h(In)e fa(Pr)n(oceedings)e(of)1056 940 y(10th)i(IEEE)i
(Real-T)m(ime)g(Systems)d(Symposium)p fh(,)h(December)m(,)i(1989.)973 1019 y
([15])21 b(H.)6 b(T)m(okuda,)f(T)m(.)i(Nakajima,)f(and)f(P)-5 b(.)7 b(Rao,)h
(\252Real-T)n(ime)e(Mach:)11 b(T)m(owards)1056 1065 y(a)h(Predictable)g(Real-\
T)n(ime)h(System\272,)22 b(In)12 b fa(Pr)n(oceedings)e(of)j(USENIX)1056 1111 y
(Mach)8 b(W)m(orkshop)p fh(,)f(October)n(,)i(1990.)935 2877 y fs( )p eop eos
%%Trailer
 end
%%EOF