%! for use by dvi2ps Version 2.00 /TeXDict 200 dict def TeXDict begin /Resolution 300 def /Inch {Resolution mul} def /Mtrx 6 array def /@draft { /DraftOption 1 def } def /every-page { DraftOption 1 eq {print-draft} if } def /print-draft { gsave -45 rotate -100 0 moveto /Helvetica-Bold findfont [ 120.0 0 0 -120.0 0 0 ] makefont setfont (DRAFT) show grestore gsave 300 -100 moveto /Helvetica-Bold findfont [ 60.0 0 0 -60.0 0 0 ] makefont setfont Date-and-Time show ( :: ) show Dvi-File-Name show grestore } def userdict /letter known not {/letter {} def} if /@letter { letter initmatrix 72 Resolution div dup neg scale 310 -3005 translate Mtrx currentmatrix pop } def /@note { note initmatrix 72 Resolution div dup neg scale 310 -3005 translate Mtrx currentmatrix pop } def /LandscapeOption 0 def /@landscape { /LandscapeOption 1 def letter initmatrix 72 Resolution div dup neg scale Mtrx currentmatrix 0 0.0 put Mtrx 1 -1.0 put Mtrx 2 1.0 put Mtrx 3 0.0 put Mtrx setmatrix 300 310 translate Mtrx currentmatrix pop } def /@legal { legal initmatrix 72 Resolution div dup neg scale 295 -3880 translate Mtrx currentmatrix pop } def /@manualfeed { statusdict /manualfeed true put } def /@copies { /#copies exch def } def /@newfont { /newname exch def pop newname 7 dict def newname load begin /FontType 3 def /FontMatrix [1 0 0 -1 0 0] def /FontBBox [0 0 1 1] def /BitMaps 128 array def /BuildChar {CharBuilder} def /Encoding 128 array def 0 1 127 {Encoding exch /.undef put} for end newname newname load definefont pop } def /ch-image {ch-data 0 get} def /ch-width {ch-data 1 get} def /ch-height {ch-data 2 get} def /ch-xoff {ch-data 3 get} def /ch-yoff {ch-data 4 get} def /ch-tfmw {ch-data 5 get} def /CharBuilder { /ch-code exch def /font-dict exch def /ch-data font-dict /BitMaps get ch-code get def ch-data null eq not { ch-tfmw 0 ch-xoff neg ch-yoff neg ch-width ch-xoff sub ch-height ch-yoff sub setcachedevice ch-width ch-height true [1 0 0 1 ch-xoff ch-yoff] {ch-image} imagemask } if } def /@sf { setfont() pop } def /@dc { /ch-code exch def dup 0 get length 2 lt { pop [ <00> 1 1 0 0 8.00 ] } if /ch-data exch def currentfont /BitMaps get ch-code ch-data put currentfont /Encoding get ch-code dup ( ) cvs cvn put } def /@bop0 { } def /@bop1 { pop erasepage initgraphics Mtrx setmatrix /SaveImage save def() pop } def /@eop { every-page showpage SaveImage restore() pop } def /@start { @letter } def /@end { end } def /p { moveto } def /r { 0 rmoveto } def /s { show } def /c { c-string exch 0 exch put c-string show } def /c-string ( ) def /ru { /dy exch neg def /dx exch def /x currentpoint /y exch def def newpath x y moveto dx 0 rlineto 0 dy rlineto dx neg 0 rlineto closepath fill x y moveto } def /@SpecialDefaults { /hs 8.5 Inch def /vs 11 Inch def /ho 0 def /vo 0 def /hsc 1 def /vsc 1 def /CLIP false def } def /@hsize {/hs exch def /CLIP true def} def /@vsize {/vs exch def /CLIP true def} def /@hoffset {/ho exch def} def /@voffset {/vo exch def} def /@hscale {/hsc exch def} def /@vscale {/vsc exch def} def /@setclipper { hsc vsc scale CLIP { newpath 0 0 moveto hs 0 rlineto 0 vs rlineto hs neg 0 rlineto closepath clip } if } def /@beginspecial { gsave /SpecialSave save def currentpoint transform initgraphics itransform translate LandscapeOption 1 eq {90 rotate} if @SpecialDefaults @MacSetUp } def /@setspecial { MacDrwgs {md begin /pxt ho def /pyt vo neg def end} {ho vo translate @setclipper} ifelse } def /@endspecial { SpecialSave restore grestore } def /MacDrwgs false def /@MacSetUp { userdict /md known { userdict /md get type /dicttype eq { /MacDrwgs true def md begin /psu /psu load { /letter {} def /note {} def /legal {} def statusdict /waittimeout 300 put /page {pop} def /pyt vo neg def /pxt ho def } concatprocs def /od /od load { @setclipper } concatprocs def end } if } if } def /concatprocs { /p2 exch cvlit def /p1 exch cvlit def /p p1 length p2 length add array def p 0 p1 putinterval p p1 length p2 putinterval p cvx } def end TeXDict begin @start %%Creator: dvi-ps %%EndProlog /bp-per-inch 72 def /bp2pxl 1.0 Resolution div bp-per-inch mul def /Rotate-Angle 0.0 def /Default-Matrix { [bp2pxl 0.0 0.0 bp2pxl 72.0 -72.0 ] } def /Default-Matrix { [0.0 bp2pxl bp2pxl neg 0.0 720.0 0.0 ] } def /Default-Matrix { [ bp2pxl 0.0 0.0 bp2pxl neg 1 bp-per-inch mul % t_x 11 1 sub bp-per-inch mul % t_y ] } def /Dvi-File-Name (scheduling.dvi) def /DraftOption 0 def /#copies 1 def /Date-and-Time (Tue Feb 6 17:09:48 1990) def % circle10.1500 is @F67 % line10.1500 is @F65 % ========================================================================= % ========================= ps fonts go here ============================== % ========================================================================= % From 'old-font-name' generate a makefont-operator modified font % which is called new-font-name. % new-font-name [ matrix ] old-font-name @newfont-ps - /@newfont-ps { % Save the arguments /old-font-name exch def /font-mat exch def /new-font-name exch def % In the following we have three fonts: % (a) the old font, which forms the basis % (b) the new font 2, which is the result of the 'makefont' operator % (c) the new font, which is a copied directory of (b) /old-font-dict old-font-name findfont def /font-dict-2 old-font-dict font-mat makefont def % Create a new dictionary. Make a copy of the old font /font-dict-new font-dict-2 length dict def font-dict-new begin font-dict-2 % copy everything out of font-dict-2 { % except FontBBox and FID exch dup dup /FID ne exch /FontBBox ne and { exch font-dict-new 3 1 roll put } { pop pop } ifelse } forall end /newFontBBox old-font-dict /FontBBox get % bug fix, see exercise aload length array astore def font-dict-new /FontBBox newFontBBox put font-dict-new /FontName new-font-name put % newfont /Metrics newwidths put new-font-name font-dict-new definefont pop % vmstatus exch sub == pop % print a few statistics (mem remaining) } def % Load a PS PS font % fontdict @sfps - -- make that the current font /@sfps { findfont setfont } def %! % Print the font dictionaries in the current context /@PrintFontDicts { } def %! % $Revision: 1.4 $ % Program 18 of the Postscript Cookbook, Page 211 % Modified for the needs of including it into the postscript % stuff of TeX. /reencodedict 12 dict def % get us a temporary directory % Reencode procedure % font-name newfont-name encoding-change-vector ReEncodeSmall /@ReEncodeSmall { reencodedict begin /newcodesandnames exch def /newfontname exch def /basefontname exch def /basefontdict basefontname findfont def % get font dictionary you % start out with /newfont basefontdict maxlength dict def % Create a new dictionary, % same length basefontdict { exch dup /FID ne % (Looping\n) print flush { % dup % duplicate Key for printing % (Key being copied: ) print % ( ) cvs print % (\n) print flush dup /Encoding eq { exch dup length array copy % make a COPY of the % encoding vector elements newfont 3 1 roll put }{ exch newfont 3 1 roll put % the rest is easy to copy } ifelse }{ pop pop % do not copy FID } ifelse } forall newfont /FontName newfontname put % put in the new name % Now we start to modify the encoding vector newcodesandnames aload pop newcodesandnames length 2 idiv { newfont /Encoding get 3 1 roll put} repeat newfontname newfont definefont % Declare the new font pop % ignore result end @PrintFontDicts } def % START PS FONT, TeX internal font number: 53 % psname: @Times-Bold.53 % SetUpPsFont: Start /@CodeVectorTextDelta [ 8#0 /Aacute 8#1 /Acircumflex 8#2 /Adieresis 8#3 /Agrave 8#4 /Aring 8#5 /Atilde 8#6 /Ccedilla 8#7 /Eacute 8#10 /Ecircumflex 8#11 /Edieresis 8#12 /Egrave 8#13 /Iacute 8#14 /Icircumflex 8#15 /Idieresis 8#16 /Igrave 8#17 /Ntilde 8#20 /Oacute 8#21 /Ocircumflex 8#22 /Odieresis 8#23 /Ograve 8#24 /Otilde 8#25 /Scaron 8#26 /Uacute 8#27 /Ucircumflex 8#30 /Udieresis 8#31 /Ugrave 8#32 /Ydieresis 8#33 /Zcaron 8#34 /aacute 8#35 /acircumflex 8#36 /adieresis 8#37 /agrave 8#200 /aring 8#201 /atilde 8#202 /ccedilla 8#203 /eacute 8#204 /ecircumflex 8#205 /edieresis 8#206 /egrave 8#207 /iacute 8#210 /icircumflex 8#211 /idieresis 8#212 /igrave 8#213 /ntilde 8#214 /oacute 8#215 /ocircumflex 8#216 /odieresis 8#217 /ograve 8#220 /otilde 8#221 /scaron 8#222 /uacute 8#223 /ucircumflex 8#224 /udieresis 8#225 /ugrave 8#226 /ydieresis 8#227 /zcaron ] def /Times-Bold /@Times-Bold.53.1 @CodeVectorTextDelta @ReEncodeSmall % NO outline font business % Font magnification: 2.1600 /@Times-Bold.53.2 [ 59.776 0.000 0.000 -59.776 0.000 0.000 ] /@Times-Bold.53.1 @newfont-ps % SetUpPsFont: End /@P53 { /@Times-Bold.53.2 } def % END PS FONT, TeX internal font number: 53 % START PS FONT, TeX internal font number: 38 % psname: @Times-Bold.38 % SetUpPsFont: Start /Times-Bold /@Times-Bold.38.1 @CodeVectorTextDelta @ReEncodeSmall % NO outline font business % Font magnification: 1.6430 /@Times-Bold.38.2 [ 45.468 0.000 0.000 -45.468 0.000 0.000 ] /@Times-Bold.38.1 @newfont-ps % SetUpPsFont: End /@P38 { /@Times-Bold.38.2 } def % END PS FONT, TeX internal font number: 38 % START PS FONT, TeX internal font number: 37 % psname: @Times-Italic.37 % SetUpPsFont: Start /Times-Italic /@Times-Italic.37.1 @CodeVectorTextDelta @ReEncodeSmall % NO outline font business % Font magnification: 1.6430 /@Times-Italic.37.2 [ 45.468 0.000 0.000 -45.468 0.000 0.000 ] /@Times-Italic.37.1 @newfont-ps % SetUpPsFont: End /@P37 { /@Times-Italic.37.2 } def % END PS FONT, TeX internal font number: 37 % cmsy10.1643 is @F36 % cmmi10.1643 is @F35 % START PS FONT, TeX internal font number: 34 % psname: @Times-Italic-Math.34 % SetUpPsFont: Start /Times-Italic /@Times-Italic-Math.34.1 @CodeVectorTextDelta @ReEncodeSmall % NO outline font business % Font magnification: 1.6430 /@Times-Italic-Math.34.2 [ 45.468 0.000 0.000 -45.468 0.000 0.000 ] /@Times-Italic-Math.34.1 @newfont-ps % SetUpPsFont: End /@P34 { /@Times-Italic-Math.34.2 } def % END PS FONT, TeX internal font number: 34 % START PS FONT, TeX internal font number: 33 % psname: @Times-Roman.33 % SetUpPsFont: Start /Times-Roman /@Times-Roman.33.1 @CodeVectorTextDelta @ReEncodeSmall % NO outline font business % Font magnification: 1.6430 /@Times-Roman.33.2 [ 45.468 0.000 0.000 -45.468 0.000 0.000 ] /@Times-Roman.33.1 @newfont-ps % SetUpPsFont: End /@P33 { /@Times-Roman.33.2 } def % END PS FONT, TeX internal font number: 33 % START PS FONT, TeX internal font number: 30 % psname: @Times-Bold.30 % SetUpPsFont: Start /Times-Bold /@Times-Bold.30.1 @CodeVectorTextDelta @ReEncodeSmall % NO outline font business % Font magnification: 1.5000 /@Times-Bold.30.2 [ 41.511 0.000 0.000 -41.511 0.000 0.000 ] /@Times-Bold.30.1 @newfont-ps % SetUpPsFont: End /@P30 { /@Times-Bold.30.2 } def % END PS FONT, TeX internal font number: 30 % START PS FONT, TeX internal font number: 25 % psname: @Times-Roman.25 % SetUpPsFont: Start /Times-Roman /@Times-Roman.25.1 @CodeVectorTextDelta @ReEncodeSmall % NO outline font business % Font magnification: 1.5000 /@Times-Roman.25.2 [ 41.511 0.000 0.000 -41.511 0.000 0.000 ] /@Times-Roman.25.1 @newfont-ps % SetUpPsFont: End /@P25 { /@Times-Roman.25.2 } def % END PS FONT, TeX internal font number: 25 % cmmi9.1500 is @F20 % START PS FONT, TeX internal font number: 18 % psname: @Times-Roman.18 % SetUpPsFont: Start /Times-Roman /@Times-Roman.18.1 @CodeVectorTextDelta @ReEncodeSmall % NO outline font business % Font magnification: 1.3500 /@Times-Roman.18.2 [ 37.360 0.000 0.000 -37.360 0.000 0.000 ] /@Times-Roman.18.1 @newfont-ps % SetUpPsFont: End /@P18 { /@Times-Roman.18.2 } def % END PS FONT, TeX internal font number: 18 % START PS FONT, TeX internal font number: 13 % psname: @Times-Roman.13 % SetUpPsFont: Start /Times-Roman /@Times-Roman.13.1 @CodeVectorTextDelta @ReEncodeSmall % NO outline font business % Font magnification: 1.2000 /@Times-Roman.13.2 [ 33.209 0.000 0.000 -33.209 0.000 0.000 ] /@Times-Roman.13.1 @newfont-ps % SetUpPsFont: End /@P13 { /@Times-Roman.13.2 } def % END PS FONT, TeX internal font number: 13 % START PS FONT, TeX internal font number: 4 % psname: @Times-Roman.4 % SetUpPsFont: Start /Times-Roman /@Times-Roman.4.1 @CodeVectorTextDelta @ReEncodeSmall % NO outline font business % Font magnification: 0.9000 /@Times-Roman.4.2 [ 24.907 0.000 0.000 -24.907 0.000 0.000 ] /@Times-Roman.4.1 @newfont-ps % SetUpPsFont: End /@P4 { /@Times-Roman.4.2 } def % END PS FONT, TeX internal font number: 4 0 @bop0 0 @bop1 @P53 @sfps 280 458 p (Scheduling) s 20 r (Support) s 20 r (for) s 20 r (Concurr) s 0 r (ency) s 18 r (and) s 20 r (Parallelism) s 573 514 p (in) s 20 r (the) s 20 r (Mach) s 20 r (Operating) s 20 r (System) s @P38 @sfps 824 612 p (David) s 15 r (L.) s 15 r (Black) s @P33 @sfps 707 669 p (School) s 15 r (of) s 15 r (Computer) s 15 r (Science) s 715 725 p (Carnegie) s 15 r (Mellon) s 15 r (University) s 776 782 p (Pittsbur) s 0 r (gh,) s 14 r 80 c -3 r 65 c 14 r (15213) s 829 838 p (\(412\)) s 16 r (268-3041) s 736 894 p (David.Black@cs.cmu.edu) s @P30 @sfps 896 1065 p (Abstract) s @P25 @sfps 176 1160 p (Changes) s 14 r (in) s 15 r (the) s 15 r (use) s 14 r (of) s 15 r (multiprocessors) s 14 r (are) s 15 r (placing) s 15 r (new) s 14 r (demands) s 15 r (on) s 14 r (operating) s 15 r (system) s 15 r (schedulers.) s 114 1210 p (This) s 14 r (article) s 14 r (describes) s 14 r (some) s 14 r (of) s 15 r (the) s 14 r (new) s 14 r (challenges) s 14 r (posed) s 15 r (by) s 14 r (parallel) s 14 r (and) s 14 r (concurrent) s 14 r (applications,) s 15 r (and) s 114 1260 p (introduces) s 15 r (techniques) s 15 r (developed) s 16 r (by) s 15 r (the) s 15 r (Mach) s 16 r (project) s 15 r (to) s 15 r (meet) s 16 r (these) s 15 r (challenges.) s 23 r (An) s 15 r (overview) s 15 r (of) s 16 r (the) s 114 1309 p (techniques) s 13 r (of) s 14 r (timesharing) s 14 r (scheduling) s 14 r (and) s 14 r 97 c 14 r (description) s 13 r (of) s 14 r (the) s 14 r (Mach) s 14 r (scheduler) s 14 r (are) s 14 r (also) s 14 r (included.) s 176 1359 p (This) s 12 r (article) s 11 r (describes) s 12 r (work) s 12 r (to) s 11 r (incorporate) s 12 r (processor) s 12 r (allocation) s 11 r (and) s 12 r (control) s 12 r (into) s 11 r (the) s 12 r (Mach) s 12 r (operating) s 114 1409 p (system.) s 18 r (The) s 14 r (design) s 14 r (approach) s 14 r (divides) s 13 r (the) s 14 r (implementation) s 14 r (into) s 14 r (three) s 14 r (components:) s 160 1478 p (1.) s 22 r (Basic) s 14 r (mechanisms) s 14 r (implemented) s 14 r (in) s 14 r (the) s 14 r (kernel.) s 160 1544 p (2.) s 22 r (Long) s 14 r (term) s 14 r (policy) s 14 r (implemented) s 14 r (in) s 14 r 97 c 14 r (server) s -2 r 46 c 160 1610 p (3.) s 22 r (Optional) s 14 r (user) s 14 r (implementation) s 14 r (of) s 14 r (short) s 14 r (term) s 14 r (policy) s -2 r 46 c 114 1679 p (Isolating) s 17 r (long-term) s 17 r (policy) s 17 r (in) s 17 r 97 c 17 r (server) s 17 r (yields) s 17 r (the) s 17 r (advantages) s 17 r (of) s 17 r (policy-mechanism) s 18 r (separation,) s 17 r (while) s 114 1729 p (avoiding) s 22 r (the) s 22 r (drawbacks) s 23 r (encountered) s 22 r (in) s 23 r (previous) s 22 r (applications) s 22 r (of) s 23 r (this) s 22 r (principle) s 22 r (to) s 23 r (multiprocessor) s 114 1779 p (scheduling.) s 27 r (The) s 17 r (design) s 17 r (and) s 17 r (implementation) s 17 r (of) s 17 r 97 c 17 r (processor) s 17 r (allocation) s 17 r (server) s 17 r (for) s 17 r 97 c 17 r (gang) s 17 r (scheduling) s 114 1828 p (policy) s 13 r (is) s 14 r (also) s 14 r (described.) s 176 1878 p (This) s 13 r (article) s 13 r (also) s 13 r (describes) s 14 r (work) s 13 r (to) s 13 r (support) s 13 r (the) s 13 r (ef) s 0 r (fective) s 13 r (multiprogrammed) s 13 r (use) s 13 r (of) s 13 r (multiprocessors.) s 114 1928 p (The) s 15 r (approach) s 15 r (taken) s 14 r (to) s 15 r (this) s 15 r (problem) s 15 r (implements) s 15 r (the) s 15 r (scheduler) s 15 r (in) s 15 r (the) s 15 r (kernel,) s 15 r (but) s 15 r (encourages) s 15 r (users) s 15 r (to) s 114 1978 p (provide) s 13 r (hints.) s 18 r (This) s 13 r (allows) s 13 r (the) s 14 r (scheduler) s 13 r (to) s 13 r (take) s 13 r (advantage) s 13 r (of) s 14 r (user) s 13 r (knowledge) s 13 r (without) s 13 r (requiring) s 13 r (users) s 114 2028 p (to) s 13 r (implement) s 14 r (sophisticated) s 14 r (scheduling) s 14 r (modules.) s @P38 @sfps 62 2229 p (Keywords:) s @P33 @sfps 27 r (Multiprocessor) s -1 r 44 c 18 r (Scheduling,) s 19 r (Mach,) s 19 r (Operating) s 18 r (System) s 19 r (Multiprogramming,) s 19 r (Synchroniza-) s 0 2286 p (tion,) s 15 r (Parallelism,) s 15 r (Concurrency) s -2 r 44 c 14 r (Gang) s 16 r (Scheduling,) s 15 r (Handof) s 0 r 102 c 14 r (Scheduling) s 62 2463 p (This) s 15 r (research) s 16 r (was) s 15 r (sponsored) s 15 r (by) s 15 r (the) s 15 r (Defense) s 15 r (Advanced) s 15 r (Research) s 16 r (Projects) s 15 r (Agency) s 15 r (\(DOD\),) s 15 r (monitored) s 0 2519 p (by) s 15 r (the) s 15 r (Space) s 15 r (and) s 16 r (Naval) s 15 r 87 c -3 r (arfare) s 14 r (Systems) s 15 r (Command) s 16 r (under) s 15 r (Contract) s 15 r (N00039-87-C-0251.) s 62 2617 p (The) s 19 r (views) s 19 r (and) s 19 r (conclusions) s 19 r (contained) s 19 r (in) s 19 r (this) s 19 r (document) s 19 r (are) s 19 r (those) s 19 r (of) s 19 r (the) s 19 r (authors) s 19 r (and) s 19 r (should) s 19 r (not) s 19 r (be) s 0 2673 p (interpreted) s 19 r (as) s 20 r (representing) s 19 r (the) s 19 r (of) s 0 r 174 c 0 r (cial) s 19 r (policies,) s 20 r (either) s 20 r (expressed) s 19 r (or) s 19 r (implied,) s 21 r (of) s 19 r (the) s 20 r (Defense) s 19 r (Advanced) s 0 2730 p (Research) s 15 r (Projects) s 15 r (Agency) s 15 r (or) s 16 r (the) s 15 r (US) s 15 r (Government.) s @eop 1 @bop0 1 @bop1 @P38 @sfps 0 42 p (1.) s 45 r (Intr) s 0 r (oduction) s @P33 @sfps 0 186 p (Signi) s 174 c (cant) s 17 r (changes) s 18 r (occurring) s 17 r (in) s 17 r (the) s 18 r (use) s 17 r (of) s 17 r (multiprocessors) s 17 r (require) s 18 r (new) s 17 r (support) s 17 r (from) s 18 r (operating) s 17 r (system) s 0 243 p (schedulers.) s 20 r (The) s 15 r (original) s 16 r (use) s 15 r (of) s 15 r (multiprocessors) s 15 r (for) s 15 r (increased) s 15 r (throughput) s 16 r (\(more) s 15 r (applications) s 15 r (run) s 15 r (at) s 15 r (once,) s 0 299 p (but) s 16 r (no) s 16 r (individual) s 16 r (application) s 16 r (runs) s 16 r (faster\)) s 16 r (is) s 16 r (giving) s 16 r (way) s 16 r (to) s 15 r (the) s 16 r (use) s 16 r (of) s 16 r (parallel) s 16 r (programming) s 16 r (for) s 16 r (reducing) s 0 356 p (the) s 18 r (run) s 19 r (time) s 18 r (of) s 18 r (individual) s 19 r (applications.) s 29 r (Programming) s 19 r (models) s 18 r (and) s 18 r (languages) s 19 r (for) s 18 r (parallel) s 18 r (programming) s 0 412 p (often) s 18 r (anticipate) s 19 r (dedicated) s 18 r (use) s 18 r (of) s 19 r (processors) s 18 r (or) s 18 r (an) s 19 r (entire) s 18 r (multiprocessor) s -1 r 44 c 19 r (but) s 18 r (few) s 18 r (machines) s 19 r (are) s 18 r (used) s 18 r (in) s 0 469 p (this) s 20 r (fashion.) s 37 r (Most) s 20 r (modern) s 21 r (general) s 20 r (purpose) s 21 r (multiprocessors) s 20 r (run) s 21 r 97 c 20 r (timesharing) s 20 r (operating) s 21 r (system) s 20 r (such) s 0 525 p (as) s 20 r (Unix) s @P13 @sfps 148 509 p 49 c @P33 @sfps 167 525 p 46 c 34 r (The) s 20 r (shared) s 19 r (usage) s 20 r (model) s 20 r (of) s 19 r (these) s 20 r (systems) s 19 r (con) s 0 r 175 c 0 r (icts) s 20 r (with) s 20 r (the) s 19 r (dedicated) s 20 r (use) s 20 r (model) s 19 r (of) s 20 r (many) s 0 581 p (programs.) s 22 r (Resolving) s 16 r (this) s 16 r (clash) s 15 r (by) s 16 r (restricting) s 16 r (usage) s 16 r (of) s 16 r 97 c 15 r (multiprocessor) s 16 r (to) s 16 r 97 c 16 r (single) s 16 r (application) s 15 r (at) s 16 r 97 c 16 r (time) s 0 638 p (is) s 15 r (often) s 15 r (not) s 15 r (an) s 16 r (attractive) s 15 r (solution.) s 62 736 p (Another) s 11 r (impact) s 11 r (on) s 12 r (schedulers) s 11 r (comes) s 11 r (from) s 11 r (the) s 11 r (increasing) s 11 r (use) s 11 r (of) s 11 r (concurrency) s -2 r 46 c 18 r 87 c -3 r 101 c 11 r (de) s 0 r 174 c 0 r (ne) s 11 r (the) s @P37 @sfps 11 r (application) s 0 792 p (parallelism) s @P33 @sfps 19 r (for) s 18 r (an) s 19 r (application) s 18 r (on) s 19 r 97 c 18 r (multiprocessor) s 19 r (as) s 18 r (the) s 19 r (actual) s 18 r (degree) s 19 r (of) s 18 r (parallel) s 19 r (execution) s 18 r (achieved.) s 0 849 p (The) s 19 r (corresponding) s 19 r (de) s 0 r 174 c 0 r (nition) s 19 r (of) s @P37 @sfps 19 r (application) s 19 r (concurr) s 0 r (ency) s @P33 @sfps 18 r (is) s 19 r (the) s 19 r (maximum) s 19 r (degree) s 19 r (of) s 19 r (parallel) s 19 r (execution) s 0 905 p (that) s 14 r (could) s 15 r (be) s 14 r (achieved) s 15 r (if) s 14 r (an) s 15 r (unlimited) s 14 r (number) s 15 r (of) s 14 r (processors) s 15 r (were) s 14 r (available.) s 20 r (For) s 14 r (example,) s 15 r (an) s 14 r (application) s 0 962 p (consisting) s 20 r (of) s 20 r (ten) s 21 r (independent) s 20 r (processes) s 20 r (running) s 20 r (on) s 20 r 97 c 21 r (six) s 20 r (processor) s 20 r (multiprocessor) s 20 r (has) s 21 r (an) s 20 r (application) s 0 1018 p (parallelism) s 14 r (of) s 13 r (six) s 14 r (based) s 14 r (on) s 14 r (the) s 13 r (six) s 14 r (processors,) s 14 r (and) s 14 r (an) s 14 r (application) s 13 r (concurrency) s 14 r (of) s 14 r (ten) s 14 r (because) s 13 r (it) s 14 r (could) s 14 r (use) s 0 1075 p (up) s 18 r (to) s 18 r (ten) s 17 r (processors.) s 29 r (Application) s 17 r (concurrency) s 18 r (beyond) s 18 r (the) s 18 r (hardware) s 17 r (parallelism) s 18 r (can) s 18 r (improve) s 18 r (hardware) s 0 1131 p (utilization) s 14 r (by) s 13 r (allowing) s 14 r (other) s 14 r (portions) s 13 r (of) s 14 r (the) s 14 r (application) s 13 r (to) s 14 r (proceed) s 14 r (if) s 13 r (one) s 14 r (portion) s 14 r (blocks) s 13 r (for) s 14 r (some) s 14 r (reason,) s 0 1188 p (such) s 12 r (as) s 12 r 97 c 12 r (disk) s 12 r (or) s 12 r (network) s 12 r (operation.) s 19 r (The) s 12 r (use) s 12 r (of) s 12 r (concurrency) s 12 r (can) s 12 r (also) s 12 r (simplify) s 12 r (programming) s 12 r (of) s 12 r (concurrent) s 0 1244 p (applications) s 12 r (by) s 12 r (allowing) s 12 r (the) s 12 r (state) s 12 r (of) s 12 r (ongoing) s 12 r (interactions) s 12 r (to) s 12 r (be) s 12 r (captured) s 12 r (in) s 12 r (the) s 12 r (local) s 12 r (variables) s 12 r (of) s 12 r (executing) s 0 1300 p (entities) s 15 r (instead) s 15 r (of) s 15 r 97 c 16 r (state) s 15 r (table.) s 62 1398 p (Application) s 14 r (parallelism) s 15 r (and) s 14 r (concurrency) s 14 r (complicate) s 14 r (two) s 15 r (areas) s 14 r (of) s 14 r (scheduling:) s 20 r (making) s 14 r (ef) s 0 r (fective) s 13 r (use) s 15 r (of) s 0 1455 p (the) s 18 r (processing) s 19 r (resources) s 18 r (available) s 19 r (to) s 18 r (individual) s 19 r (applications,) s 19 r (and) s 18 r (dividing) s 19 r (processing) s 18 r (resources) s 18 r (among) s 0 1511 p (competing) s 16 r (applications.) s 24 r (The) s 17 r (problem) s 16 r (of) s 17 r (scheduling) s 16 r (within) s 17 r (applications) s 16 r (usually) s 16 r (does) s 17 r (not) s 16 r (arise) s 17 r (for) s 16 r (serial) s 0 1568 p (applications) s 18 r (because) s 18 r (the) s 18 r (schedulable) s 18 r (entities) s 17 r (that) s 18 r (compose) s 18 r (an) s 18 r (application) s 18 r (can) s 18 r (often) s 18 r (be) s 18 r (scheduled) s 18 r (inde-) s 0 1624 p (pendently) s 18 r (with) s 18 r (little) s 17 r (impact) s 18 r (on) s 18 r (overall) s 18 r (performance.) s 28 r (In) s 18 r (contrast,) s 18 r (the) s 18 r (medium) s 18 r (to) s 18 r 174 c 0 r (ne) s 17 r (grain) s 18 r (interactions) s 0 1681 p (exhibited) s 20 r (by) s 19 r (programs) s 20 r (employing) s 19 r (parallelism) s 20 r (and) s 19 r (concurrency) s 20 r (may) s 19 r (necessitate) s 20 r (scheduling) s 19 r (portions) s 20 r (of) s 0 1737 p (these) s 20 r (programs) s 21 r (together) s 20 r (to) s 20 r (achieve) s 21 r (acceptable) s 20 r (performance.) s 36 r (Parallel) s 20 r (applications) s 20 r (that) s 21 r (require) s 20 r 97 c 20 r 174 c 0 r (xed) s 0 1794 p (number) s 15 r (of) s 15 r (processors) s 15 r (complicate) s 15 r (scheduling) s 15 r (across) s 15 r (applications) s 15 r (by) s 15 r (making) s 15 r (it) s 15 r (more) s 15 r (dif) s 0 r 174 c 0 r (cult) s 15 r (to) s 15 r (divide) s 15 r (up) s 0 1850 p (machine) s 13 r (time.) s 20 r (These) s 13 r (applications) s 14 r (may) s 13 r (also) s 13 r (introduce) s 13 r (situations) s 14 r (in) s 13 r (which) s 13 r (fair) s 14 r (sharing) s 13 r (of) s 13 r (the) s 14 r (machine) s 13 r (may) s 0 1906 p (not) s 15 r (be) s 16 r (an) s 15 r (appropriate) s 16 r (policy) s -2 r 46 c 20 r (For) s 16 r (example,) s 15 r (an) s 16 r (application) s 15 r (may) s 15 r (be) s 16 r (con) s 0 r 174 c 0 r (gured) s 15 r (to) s 16 r (require) s 15 r 97 c 16 r 174 c 0 r (xed) s 15 r (numbers) s 0 1963 p (of) s 15 r (processors) s 15 r (for) s 15 r (ef) s 0 r 174 c 0 r (cient) s 15 r (execution,) s 15 r (and) s 15 r (be) s 15 r (unable) s 15 r (to) s 16 r (cope) s 15 r (ef) s 0 r 174 c 0 r (ciently) s 14 r (with) s 15 r (less) s 15 r (than) s 15 r (that) s 16 r (number) s -2 r 46 c 62 2061 p (This) s 12 r (article) s 12 r (discusses) s 11 r (new) s 12 r (approaches) s 12 r (to) s 11 r (these) s 12 r (areas) s 12 r (developed) s 12 r (as) s 11 r (part) s 12 r (of) s 12 r (the) s 11 r (Mach) s 12 r (operating) s 12 r (system[) s 0 r 49 c 0 r 93 c 0 2117 p (at) s 17 r (Carnegie) s 18 r (Mellon) s 17 r (University) s -2 r 46 c 26 r (Mach) s 17 r (is) s 17 r 97 c 17 r (new) s 18 r (operating) s 17 r (system) s 17 r (for) s 18 r (uniprocessors) s 17 r (and) s 17 r (multiprocessors) s 0 2174 p (that) s 22 r (provides) s 21 r 175 c 0 r (exible) s 22 r (memory) s 21 r (management) s 22 r (and) s 21 r (sharing,) s 23 r (multiple) s @P37 @sfps 22 r (thr) s -1 r (eads) s @P33 @sfps 21 r (\(locus) s 21 r (of) s 22 r (control,) s 23 r (program) s 0 2230 p (counter) s -1 r 44 c 16 r (registers\)) s 16 r (within) s 17 r 97 c 16 r (single) s 17 r (address) s 16 r (space) s 17 r (or) s @P37 @sfps 16 r (task) s @P33 @sfps 16 r (for) s 17 r (concurrency) s 16 r (and) s 17 r (parallelism,) s 16 r (and) s 17 r 97 c 16 r (network) s 0 2287 p (transparent) s 18 r (communication) s 19 r (subsystem) s 18 r (\(IPC\).) s 18 r (The) s 19 r (Mach) s 18 r (kernel) s 18 r (incorporates) s 19 r (compatibility) s 18 r (code) s 18 r (derived) s 0 2343 p (from) s 18 r (4.3BSD) s 18 r (Unix[) s 0 r 50 c 0 r 93 c 19 r (that) s 18 r (provides) s 18 r (complete) s 18 r (binary) s 18 r (compatibility) s -2 r 46 c 29 r (Mach) s 18 r (runs) s 18 r (on) s 18 r 97 c 18 r (variety) s 19 r (of) s 18 r (unipro-) s 0 2400 p (cessor) s 16 r (and) s 17 r (multiprocessor) s 16 r (architectures) s 16 r (including) s 17 r (the) s 16 r 86 c -5 r (AX) s @P13 @sfps 1099 2383 p 50 c @P33 @sfps 1118 2400 p 44 c 16 r (Sun) s 17 r (3,) s 16 r (IBM) s 16 r (RP3) s @P13 @sfps 1464 2383 p 51 c @P33 @sfps 1483 2400 p 44 c 16 r (and) s 16 r (Encore) s 17 r (Multimax) s @P13 @sfps 1917 2383 p 52 c @P33 @sfps 1935 2400 p 46 c 0 2432 p 779 2 ru @P4 @sfps 53 2489 p 49 c @P18 @sfps 67 2505 p (Unix) s 13 r (is) s 12 r 97 c 13 r (trademark) s 12 r (of) s 13 r 65 c -4 r (T&T) s 12 r (Bell) s 12 r (Laboratories.) s @P4 @sfps 53 2565 p 50 c @P18 @sfps 67 2581 p 86 c -4 r (AX) s 12 r (is) s 12 r 97 c 13 r (trademark) s 12 r (of) s 13 r (Digital) s 12 r (Equipment) s 13 r (Corporation) s @P4 @sfps 53 2641 p 51 c @P18 @sfps 67 2657 p (An) s 13 r (experimental) s 12 r (NUMA) s 13 r (multiprocessor) s @P4 @sfps 53 2717 p 52 c @P18 @sfps 67 2733 p (Multimax) s 13 r (is) s 12 r 97 c 13 r (trademark) s 12 r (of) s 13 r (Encore) s 12 r (Computer) s 12 r (Corporation) s @P33 @sfps 962 2843 p 49 c @eop 2 @bop0 2 @bop1 @P33 @sfps 0 42 p (This) s 17 r (article) s 16 r (concentrates) s 17 r (on) s 16 r (the) s 17 r (shared) s 17 r (use) s 16 r (of) s 17 r (general) s 17 r (purpose) s 16 r (uniprocessors) s 17 r (and) s 16 r (shared) s 17 r (memory) s 17 r (multi-) s 0 98 p (processors.) s 25 r (Support) s 17 r (is) s 16 r (emphasized) s 17 r (for) s 17 r (the) s 16 r (common) s 17 r (Uniform) s 17 r (Memory) s 16 r (Access) s 17 r (\(UMA\)) s 17 r (architectures) s 17 r (that) s 0 154 p (have) s 18 r (all) s 17 r (memory) s 18 r (equidistant) s 17 r (from) s 18 r (all) s 18 r (processors) s 17 r (in) s 18 r (terms) s 18 r (of) s 17 r (access) s 18 r (time.) s 27 r (This) s 18 r (work) s 18 r (is) s 17 r (also) s 18 r (applicable) s 0 211 p (to) s 18 r (Non-Uniform) s 17 r (Memory) s 18 r (Access) s 18 r (\(NUMA\)) s 17 r (machines) s 18 r (that) s 18 r (have) s 18 r (access) s 17 r (times) s 18 r (to) s 18 r (memory) s 17 r (depend) s 18 r (on) s 18 r (the) s 0 267 p (location) s 13 r (of) s 12 r (the) s 13 r (processor) s 13 r (with) s 13 r (respect) s 12 r (to) s 13 r (the) s 13 r (accessed) s 12 r (memory) s -2 r 44 c 13 r (but) s 12 r (it) s 13 r (does) s 13 r (not) s 12 r (provide) s 13 r 97 c 13 r (complete) s 13 r (solution) s 0 324 p (to) s 15 r (the) s 15 r (load) s 15 r (balancing) s 16 r (problems) s 15 r (for) s 15 r (this) s 15 r (class) s 15 r (of) s 15 r (machines.) s 62 422 p (This) s 17 r (article) s 16 r (begins) s 16 r (with) s 16 r 97 c 16 r (review) s 17 r (of) s 16 r (timesharing) s 16 r (schedulers) s 16 r (and) s 17 r 97 c 16 r (description) s 16 r (of) s 16 r (the) s 17 r (Mach) s 16 r (scheduler) s 0 478 p (as) s 15 r 97 c 15 r (basis) s 14 r (for) s 15 r (improvements.) s 20 r (This) s 15 r (is) s 15 r (followed) s 14 r (by) s 15 r 97 c 15 r (short) s 15 r (survey) s 14 r (of) s 15 r (parallel) s 15 r (and) s 15 r (concurrent) s 14 r (programming) s 0 535 p (models.) s 28 r (Section) s 18 r 53 c 18 r (discusses) s 18 r (the) s 18 r (techniques) s 17 r (of) s 18 r (Handof) s 0 r 102 c 17 r (and) s 18 r (Discouragement) s 18 r (Scheduling) s 18 r (for) s 17 r (support) s 18 r (of) s 0 591 p (concurrency) s -2 r 46 c 18 r (Section) s 13 r 54 c 13 r (discusses) s 13 r (the) s 12 r (design) s 13 r (and) s 13 r (implementation) s 13 r (of) s 12 r (the) s 13 r (Mach) s 13 r (processor) s 13 r (allocation) s 12 r (system,) s 0 648 p (and) s 18 r 97 c 18 r (server) s 18 r (that) s 18 r (implements) s 18 r 97 c 19 r (simple) s 18 r (but) s 18 r (useful) s 18 r (allocation) s 18 r (policy) s -2 r 46 c 28 r (Section) s 18 r 55 c 18 r (covers) s 18 r (related) s 18 r (processor) s 0 704 p (allocation) s 15 r (work.) s 20 r (Section) s 16 r 56 c 15 r (concludes) s 15 r (with) s 15 r 97 c 15 r (summary) s 15 r (of) s 15 r (results.) s @P38 @sfps 0 869 p (2.) s 45 r 84 c 0 r (imesharing) s 15 r (Scheduling) s @P33 @sfps 0 1014 p 65 c 10 r (major) s 11 r (goal) s 10 r (of) s 10 r (timesharing) s 10 r (schedulers) s 11 r (is) s 10 r (fair) s 10 r (sharing) s 11 r (of) s 10 r (processor) s 10 r (resources) s 10 r (so) s 11 r (that) s 10 r (applications) s 10 r (competing) s 0 1070 p (for) s 13 r (processor) s 12 r (time) s 13 r (will) s 12 r (receive) s 13 r (approximately) s 13 r (equal) s 12 r (portions.) s 20 r (The) s 12 r (notion) s 13 r (of) s 12 r (`approximately) s 13 r (equal') s 13 r (applies) s 0 1127 p (over) s 16 r (periods) s 16 r (of) s 15 r 97 c 16 r (few) s 16 r (seconds) s 16 r (to) s 16 r (ensure) s 15 r (interactive) s 16 r (response) s 16 r (in) s 16 r (the) s 16 r (presence) s 15 r (of) s 16 r (compute-bound) s 16 r (jobs.) s 22 r (In) s 0 1183 p (practice,) s 21 r (this) s 20 r (sharing) s 19 r (requires) s 20 r (some) s 20 r (form) s 19 r (of) s 20 r (processor) s 20 r (usage) s 20 r (tracking) s 19 r (and) s 20 r (the) s 20 r (use) s 20 r (of) s 19 r (this) s 20 r (information) s 0 1240 p (in) s 17 r (scheduling) s 17 r (decisions.) s 25 r (The) s 17 r (simplest) s 17 r (form) s 17 r (of) s 17 r (this) s 16 r (is) s 17 r 97 c 17 r (decreasing) s 17 r (priority) s 17 r (scheduler) s 17 r (where) s 17 r (the) s 16 r (priority) s 0 1296 p (of) s 18 r 97 c 18 r (process) s 19 r (decreases) s 18 r (continuously) s 18 r (as) s 18 r (it) s 19 r (uses) s 18 r (processor) s 18 r (time,) s 19 r (and) s 18 r (the) s 19 r (scheduler) s 18 r (favors) s 18 r (higher) s 18 r (priority) s 0 1353 p (processes.) s 32 r (Multics[) s 0 r 51 c 0 r 93 c 19 r (used) s 19 r (such) s 19 r 97 c 19 r (scheduler) s 19 r (and) s 19 r (discovered) s 19 r (its) s 19 r (major) s 19 r (disadvantage,) s 20 r (that) s 19 r (on) s 19 r 97 c 20 r (heavily) s 0 1409 p (loaded) s 14 r (system) s 15 r (with) s 14 r (signi) s 0 r 174 c 0 r (cant) s 14 r (numbers) s 14 r (of) s 15 r (short-lived) s 14 r (jobs) s 14 r (the) s 14 r (priority) s 15 r (of) s 14 r 97 c 14 r (lengthy) s 14 r (job) s 15 r (can) s 14 r (decrease) s 14 r (to) s 15 r 97 c 0 1466 p (point) s 15 r (where) s 15 r (little) s 15 r (or) s 15 r (no) s 15 r (further) s 15 r (processor) s 15 r (time) s 14 r (is) s 15 r (available) s 15 r (to) s 15 r (it.) s 20 r (The) s 15 r (automatic) s 15 r (depression) s 15 r (of) s 15 r (priority) s 15 r (for) s 0 1522 p (lengthy) s 15 r (jobs) s 15 r (in) s 15 r (some) s 16 r (versions) s 15 r (of) s 15 r (Unix) s 15 r (also) s 15 r (exhibits) s 15 r (this) s 16 r (drawback.) s 62 1620 p 84 c -2 r 111 c 19 r (avoid) s 20 r (the) s 21 r (problem) s 20 r (of) s 20 r (permanently) s 20 r (depressed) s 20 r (priorities) s 20 r (it) s 20 r (is) s 21 r (necessary) s 20 r (to) s 20 r (elevate) s 20 r (them) s 20 r (in) s 20 r (some) s 0 1676 p (manner) s -2 r 46 c 20 r (There) s 16 r (are) s 15 r (two) s 15 r (major) s 16 r (choices) s 15 r (for) s 15 r (elevation) s 16 r (methodologies:) s 20 r (event-based) s 16 r (elevation,) s 15 r (and) s 15 r (processor) s 0 1733 p (usage) s 22 r (aging.) s 39 r (Event-based) s 22 r (elevation) s 21 r (is) s 22 r (used) s 21 r (to) s 22 r (deliberately) s 22 r (favor) s 21 r (interactive) s 22 r (response) s 21 r (over) s 22 r (compute-) s 0 1789 p (bound) s 14 r (jobs) s 15 r (because) s 14 r (process) s 15 r (priority) s 14 r (is) s 15 r (elevated) s 14 r (by) s 14 r (the) s 15 r (occurrence) s 14 r (of) s 15 r (events) s 14 r (such) s 15 r (as) s 14 r (I/O) s 14 r (completion.) s 20 r (The) s 0 1846 p (elevations) s 20 r (associated) s 20 r (with) s 20 r (the) s 20 r (events) s 20 r (of) s 20 r (interest) s 20 r (must) s 20 r (be) s 20 r (determined) s 20 r (in) s 20 r (some) s 20 r (manner) s -1 r 44 c 20 r (such) s 20 r (as) s 20 r (tuning) s 0 1902 p (under) s 17 r (expected) s 18 r (workloads) s 17 r (to) s 18 r (produce) s 17 r (desired) s 18 r (behavior) s -2 r 46 c 26 r (This) s 18 r (methodology) s 17 r (assumes) s 18 r (that) s 17 r (jobs) s 17 r (are) s 18 r (either) s 0 1959 p (distinctly) s 20 r (compute-bound) s 20 r (or) s 19 r (distinctly) s 20 r (interactive) s 20 r (and) s 20 r (that) s 19 r (interactive) s 20 r (jobs) s 20 r (are) s 20 r (more) s 19 r (important.) s 34 r (Users) s 0 2015 p (whose) s 10 r (interactive) s 10 r (work) s 10 r (consumes) s 10 r (lar) s 0 r (ge) s 10 r (amounts) s 10 r (of) s 10 r (processor) s 10 r (time) s 10 r (may) s 10 r (not) s 10 r (do) s 10 r (well) s 11 r (under) s 10 r (this) s 10 r (methodology) s -2 r 44 c 0 2072 p (and) s 17 r (it) s 16 r (may) s 17 r (be) s 17 r (necessary) s 16 r (to) s 17 r (retune) s 17 r (the) s 16 r (priority) s 17 r (elevations) s 17 r (in) s 16 r (response) s 17 r (to) s 17 r (workload) s 16 r (or) s 17 r (hardware) s 17 r (changes.) s 0 2128 p (The) s 15 r 86 c -5 r (AX/VMS) s @P13 @sfps 290 2112 p 53 c @P33 @sfps 323 2128 p (scheduler) s 16 r (employs) s 15 r (this) s 15 r (elevation) s 15 r (methodology[) s 0 r 52 c 0 r (].) s 62 2226 p (The) s 22 r (second) s 22 r (priority) s 22 r (elevation) s 22 r (methodology) s 22 r (is) s 22 r (processor) s 23 r (usage) s 22 r (aging.) s 40 r 65 c 22 r (scheduler) s 22 r (that) s 23 r (uses) s 22 r (this) s 0 2283 p (methodology) s 17 r (elevates) s 17 r (priorities) s 18 r (by) s 17 r (gradually) s 17 r (for) s 0 r (getting) s 17 r (about) s 17 r (past) s 17 r (processor) s 17 r (usage,) s 18 r (usually) s 17 r (in) s 17 r (an) s 18 r (expo-) s 0 2339 p (nential) s 15 r (fashion.) s 20 r (An) s 15 r (example) s 15 r (is) s 14 r (that) s 15 r (usage) s 15 r (from) s 15 r (one) s 15 r (minute) s 14 r (ago) s 15 r (is) s 15 r (half) s 15 r (as) s 15 r (costly) s 14 r (as) s 15 r (usage) s 15 r (within) s 15 r (the) s 15 r (past) s 0 2395 p (minute,) s 20 r (usage) s 19 r (from) s 19 r (the) s 19 r (minute) s 19 r (before) s 19 r (is) s 19 r (half) s 19 r (again) s 19 r (as) s 19 r (costly) s -2 r 44 c 19 r (and) s 19 r (so) s 19 r (on.) s 32 r (As) s 19 r 97 c 19 r (result,) s 20 r (the) s 19 r (scheduler) s 1 r 39 c -1 r 115 c 0 2452 p (measure) s 13 r (of) s 13 r (processor) s 13 r (usage) s 13 r (is) s 13 r (an) s 13 r (exponentially) s 13 r (weighted) s 13 r (average) s 13 r (over) s 13 r (the) s 12 r (lifetime) s 13 r (of) s 13 r 97 c 13 r (process.) s 20 r 65 c 13 r (simple) s 0 2508 p (exponential) s 17 r (average) s 16 r (is) s 17 r (not) s 16 r (desirable) s 17 r (because) s 16 r (it) s 17 r (has) s 17 r (the) s 16 r (unexpected) s 17 r (side) s 16 r (ef) s 0 r (fect) s 16 r (of) s 17 r (raising) s 16 r (priorities) s 17 r (when) s 0 2565 p (the) s 15 r (load) s 15 r (on) s 15 r (the) s 15 r (system) s 15 r (rises.) s 20 r (This) s 15 r (happens) s 15 r (because) s 15 r (under) s 15 r (higher) s 15 r (loads) s 14 r (each) s 15 r (process) s 15 r (gets) s 15 r 97 c 15 r (smaller) s 15 r (share) s 0 2621 p (of) s 19 r (the) s 18 r (processor) s -1 r 44 c 19 r (so) s 18 r (its) s 19 r (usage) s 19 r (average) s 18 r (drops,) s 20 r (causing) s 18 r (its) s 19 r (priority) s 19 r (to) s 18 r (rise.) s 31 r (These) s 18 r (elevated) s 19 r (priorities) s 19 r (can) s 0 2653 p 779 2 ru @P4 @sfps 53 2711 p 53 c @P18 @sfps 67 2727 p 86 c -4 r (AX/VMS) s 12 r (is) s 12 r 97 c 13 r (trademark) s 12 r (of) s 13 r (Digital) s 12 r (Equipment) s 13 r (Corporation.) s @P33 @sfps 962 2843 p 50 c @eop 3 @bop0 3 @bop1 @P33 @sfps 0 42 p (degrade) s 19 r (system) s 18 r (response) s 19 r (under) s 18 r (heavy) s 19 r (loads) s 19 r (because) s 18 r (no) s 19 r (process) s 18 r (accumulates) s 19 r (enough) s 19 r (usage) s 18 r (to) s 19 r (drop) s 18 r (its) s 0 98 p (priority) s -2 r 46 c 21 r (The) s 16 r (4.3BSD) s 16 r (version) s 16 r (of) s 16 r (Unix) s 16 r (solves) s 15 r (this) s 16 r (problem) s 16 r (by) s 16 r (making) s 16 r (the) s 16 r (aging) s 15 r (rate) s 16 r (depend) s 16 r (on) s 16 r (the) s 16 r (load) s 0 154 p (factor) s -1 r 44 c 20 r (so) s 19 r (that) s 20 r (aging) s 20 r (is) s 19 r (slower) s 20 r (in) s 19 r (the) s 20 r (presence) s 19 r (of) s 20 r (higher) s 19 r (load,) s 21 r (keeping) s 20 r (priorities) s 19 r (in) s 20 r (approximately) s 19 r (the) s 0 211 p (same) s 16 r (range) s 16 r 91 c 0 r 50 c 0 r (].) s 23 r (An) s 16 r (alternative) s 16 r (technique) s 16 r (is) s 16 r (to) s 16 r (use) s 17 r (an) s 16 r (overload) s 16 r (factor) s 16 r (to) s 16 r (alter) s 16 r (the) s 16 r (rate) s 16 r (at) s 16 r (which) s 16 r (usage) s 16 r (is) s 0 267 p (accumulated.) s 20 r (Under) s 14 r (this) s 14 r (technique) s 14 r (the) s 14 r (usage) s 13 r (accumulated) s 14 r (by) s 14 r (the) s 14 r (scheduler) s 14 r (is) s 14 r (the) s 14 r (actual) s 14 r (usage) s 14 r (multiplied) s 0 324 p (by) s 15 r 97 c 15 r (factor) s 15 r (that) s 16 r (re) s 0 r 175 c 0 r (ects) s 15 r (the) s 15 r (increased) s 15 r (load) s 15 r (on) s 15 r (the) s 16 r (system.) s 62 422 p (For) s 18 r 97 c 17 r (multiprocessor) s 18 r (scheduler) s -1 r 44 c 17 r (the) s 18 r (concept) s 17 r (of) s 18 r (fair) s 18 r (sharing) s 17 r (is) s 18 r (strongly) s 17 r (intertwined) s 18 r (with) s 17 r (that) s 18 r (of) s 18 r (load) s 0 478 p (balancing.) s 29 r (The) s 18 r (goal) s 18 r (of) s 18 r (load) s 18 r (balancing) s 18 r (is) s 18 r (to) s 18 r (spread) s 18 r (the) s 18 r (system') s -1 r 115 c 17 r (computational) s 18 r (load) s 18 r (evenly) s 18 r (among) s 18 r (the) s 0 535 p (available) s 14 r (processors) s 13 r (over) s 14 r (time.) s 20 r (For) s 14 r (example,) s 14 r (if) s 13 r (three) s 14 r (similar) s 14 r (jobs) s 14 r (are) s 13 r (running) s 14 r (on) s 14 r 97 c 14 r (two) s 13 r (processor) s 14 r (system,) s 0 591 p (each) s 11 r (should) s 11 r (get) s 12 r (two-thirds) s 11 r (of) s 11 r 97 c 11 r (processor) s 11 r (on) s 12 r (average.) s 18 r (This) s 12 r (often) s 11 r (requires) s 11 r (the) s 11 r (scheduler) s 11 r (to) s 12 r (shuf) s 0 r 175 c 0 r 101 c 10 r (processes) s 0 648 p (among) s 15 r (processors) s 15 r (to) s 15 r (keep) s 16 r (the) s 15 r (load) s 15 r (balanced.) s 20 r (There) s 15 r (is) s 15 r (an) s 16 r (important) s 15 r (tradeof) s 0 r 102 c 14 r (between) s 15 r (load) s 15 r (balancing) s 15 r (and) s 0 704 p (overhead) s 14 r (in) s 15 r (that) s 14 r (optimal) s 14 r (load) s 14 r (balancing) s 15 r (causes) s 14 r (high) s 14 r (scheduler) s 14 r (overhead) s 15 r (due) s 14 r (to) s 14 r (frequent) s 15 r (context) s 14 r (switches) s 0 760 p (for) s 19 r (load) s 19 r (balancing.) s 32 r 65 c 19 r (uniprocessor) s 19 r (timesharing) s 19 r (scheduler) s 19 r (encounters) s 19 r (similar) s 19 r (issues) s 19 r (in) s 19 r (minimizing) s 19 r (the) s 0 817 p (number) s 15 r (of) s 15 r (context) s 15 r (switches) s 16 r (used) s 15 r (to) s 15 r (implement) s 15 r (fair) s 15 r (sharing.) s @P38 @sfps 0 986 p (3.) s 45 r (The) s 16 r (Mach) s 15 r (Scheduler) s @P33 @sfps 0 1131 p (This) s 18 r (section) s 18 r (describes) s 18 r (the) s 17 r (Mach) s 18 r (timesharing) s 18 r (scheduler) s 18 r (to) s 18 r (establish) s 18 r 97 c 18 r (basis) s 17 r (for) s 18 r (the) s 18 r (improvements) s 18 r (to) s 18 r (be) s 0 1187 p (discussed.) s 40 r (Although) s 21 r (Mach) s 22 r (splits) s 22 r (the) s 22 r (usual) s 21 r (process) s 22 r (notion) s 22 r (into) s 21 r (the) s 22 r (task) s 22 r (and) s 21 r (thread) s 22 r (abstractions,) s 23 r (the) s 0 1244 p (Mach) s 19 r (scheduler) s 18 r (only) s 19 r (schedules) s 19 r (threads.) s 31 r (The) s 19 r (knowledge) s 18 r (that) s 19 r (two) s 19 r (threads) s 19 r (are) s 18 r (in) s 19 r (the) s 19 r (same) s 19 r (task) s 18 r (can) s 19 r (be) s 0 1300 p (used) s 16 r (to) s 16 r (optimize) s 16 r (the) s 16 r (context) s 16 r (switch) s 16 r (between) s 16 r (them.) s 23 r (This) s 16 r (information) s 16 r (is) s 16 r (not) s 16 r (used) s 16 r (to) s 16 r (select) s 16 r (the) s 16 r (threads) s 16 r (to) s 0 1357 p (run) s 15 r (because) s 15 r (there) s 16 r (may) s 15 r (be) s 15 r (little) s 15 r (improvement) s 15 r (in) s 15 r (performance) s 16 r (depending) s 15 r (on) s 15 r (the) s 15 r (hardware) s 15 r (and) s 15 r (application) s 0 1413 p (involved,) s 13 r (and) s 12 r (because) s 13 r (favoring) s 12 r (some) s 13 r (threads) s 12 r (on) s 13 r (this) s 12 r (basis) s 13 r (can) s 12 r (be) s 12 r (detrimental) s 13 r (to) s 12 r (load) s 13 r (and) s 12 r (usage) s 13 r (balancing.) s 0 1470 p (Some) s 18 r (scheduler) s 19 r (functions) s 18 r (are) s 18 r (driven) s 19 r (by) s 18 r (periodic) s 19 r (clock) s 18 r (or) s 18 r (timer) s 19 r (interrupts) s 18 r (that) s 18 r (occur) s 19 r (on) s 18 r (all) s 18 r (processors) s 0 1526 p (every) s 15 r (10) s 15 r (to) s 15 r (100) s 16 r (milliseconds.) s @P38 @sfps 0 1690 p (3.1.) s 45 r (Data) s 16 r (Structur) s 0 r (es) s @P33 @sfps 0 1819 p (The) s 18 r (primary) s 18 r (data) s 18 r (structure) s 18 r (used) s 17 r (by) s 18 r (the) s 18 r (Mach) s 18 r (scheduler) s 18 r (is) s 18 r (the) s @P37 @sfps 18 r (run) s 18 r (queue) s @P33 @sfps 0 r 44 c 18 r 97 c 18 r (priority) s 18 r (queue) s 18 r (of) s 18 r (runnable) s 0 1875 p (threads) s 15 r (implemented) s 16 r (by) s 15 r (an) s 16 r (array) s 15 r (of) s 16 r (doubly-linked) s 15 r (queues.) s 21 r (Thirty-two) s 16 r (queues) s 15 r (are) s 16 r (used) s 15 r (in) s 16 r (Mach,) s 15 r (so) s 16 r (four) s 0 1932 p (priorities) s 21 r (from) s 20 r (the) s 21 r (Unix) s 20 r (range) s 21 r (of) s 20 r 48 c 0 r 177 c 0 r (127) s 21 r (map) s 20 r (to) s 21 r (each) s 20 r (queue) s @P13 @sfps 1162 1915 p 54 c @P33 @sfps 1181 1932 p 46 c 36 r (Lower) s 21 r (priorities) s 20 r (correspond) s 21 r (to) s 20 r (higher) s 0 1988 p (numbers) s 16 r (and) s 15 r (vice-versa.) s 21 r 65 c 16 r (hint) s 15 r (is) s 16 r (maintained) s 16 r (that) s 15 r (indicates) s 16 r (the) s 15 r (probable) s 16 r (location) s 15 r (of) s 16 r (the) s 15 r (highest) s 16 r (priority) s 0 2045 p (thread.) s 28 r (The) s 18 r (highest) s 18 r (priority) s 17 r (thread) s 18 r (cannot) s 18 r (be) s 18 r (at) s 17 r 97 c 18 r (higher) s 18 r (priority) s 18 r (than) s 18 r (the) s 17 r (hint,) s 19 r (but) s 18 r (may) s 17 r (be) s 18 r (at) s 18 r 97 c 18 r (lower) s 0 2101 p (priority) s -2 r 46 c 19 r (This) s 14 r (allows) s 14 r (the) s 14 r (search) s 14 r (for) s 14 r (the) s 14 r (highest) s 15 r (priority) s 14 r (thread) s 14 r (to) s 14 r (start) s 14 r (from) s 14 r (the) s 14 r (hint) s 14 r (instead) s 14 r (of) s 14 r (the) s 14 r (highest) s 0 2158 p (priority) s 14 r (queue,) s 15 r (and) s 14 r (can) s 15 r (avoid) s 14 r (searching) s 15 r 97 c 14 r (dozen) s 15 r (or) s 14 r (more) s 15 r (queues) s 14 r (because) s 15 r (the) s 14 r (highest) s 14 r (priority) s 15 r (possible) s 14 r (for) s 0 2214 p (most) s 13 r (user) s 13 r (threads) s 13 r (is) s 14 r (50) s 13 r (to) s 13 r (match) s 13 r (Unix.) s 20 r (Each) s 13 r (run) s 13 r (queue) s 13 r (also) s 13 r (contains) s 13 r 97 c 14 r (mutual) s 13 r (exclusion) s 13 r (lock) s 13 r (and) s 13 r 97 c 13 r (count) s 0 2270 p (of) s 14 r (threads) s 13 r (currently) s 14 r (enqueued.) s 20 r (The) s 14 r (count) s 13 r (is) s 14 r (used) s 14 r (to) s 13 r (optimize) s 14 r (testing) s 14 r (for) s 13 r (emptiness) s 14 r (by) s 14 r (replacing) s 13 r 97 c 14 r (scan) s 14 r (of) s 0 2327 p (the) s 15 r (individual) s 15 r (queues) s 14 r (with) s 15 r 97 c 15 r (comparison) s 15 r (of) s 15 r (the) s 14 r (counter) s 15 r (to) s 15 r (zero.) s 20 r (This) s 15 r (eliminates) s 15 r (the) s 14 r (need) s 15 r (to) s 15 r (hold) s 15 r (the) s 15 r (run) s 0 2383 p (queue) s 16 r (lock) s 15 r (when) s 16 r (the) s 16 r (run) s 16 r (queue) s 15 r (is) s 16 r (empty) s -2 r 44 c 15 r (reducing) s 16 r (potential) s 16 r (contention) s 15 r (for) s 16 r (this) s 16 r (important) s 15 r (lock.) s 22 r (The) s 16 r (use) s 0 2440 p (of) s 15 r 97 c 14 r (single) s 15 r (lock) s 14 r (assumes) s 15 r (that) s 14 r (clock) s 15 r (interrupts) s 14 r (on) s 15 r (the) s 14 r (processors) s 15 r (of) s 14 r 97 c 15 r (multiprocessor) s 14 r (are) s 15 r (not) s 15 r (synchronized) s 0 2496 p (because) s 16 r (signi) s 0 r 174 c 0 r (cant) s 16 r (contention) s 17 r (can) s 16 r (be) s 16 r (expected) s 16 r (in) s 16 r (the) s 16 r (synchronized) s 17 r (case,) s 16 r (and) s 16 r (the) s 16 r (use) s 17 r (of) s 16 r 97 c 16 r (shared) s 16 r (global) s 0 2553 p (run) s 13 r (queue) s 13 r (may) s 13 r (not) s 13 r (be) s 12 r (appropriate.) s 20 r (Figure) s 13 r 49 c 13 r (shows) s 12 r (an) s 13 r (example) s 13 r (of) s 13 r 97 c 13 r (run) s 13 r (queue) s 13 r (with) s 13 r 51 c 13 r (threads.) s 19 r (The) s 13 r (queues) s 0 2602 p 779 2 ru @P4 @sfps 53 2659 p 54 c @P18 @sfps 67 2675 p (More) s 13 r (recent) s 12 r (Mach) s 13 r (kernels) s 12 r (use) s 13 r 97 c 12 r (priority) s 12 r (range) s 13 r (of) s 12 r 48 c 0 r 177 c 0 r (31) s 13 r (so) s 12 r (that) s 13 r (queues) s 12 r (and) s 13 r (priorities) s 12 r (correspond.) s @P33 @sfps 962 2843 p 51 c @eop 4 @bop0 [ 1500 ] /@F67 @newfont @F67 @sf [ 32 27 0 25 49.812] 11 @dc [<000007E000003FE00001F8000007C000000E0000003C00000070000000E0000001C000000380000007000000060000000E00 00001C00000018000000380000003000000070000000600000006000000060000000E0000000C0000000C0000000C0000000 C0000000C0000000> 32 27 0 0 49.812] 10 @dc [<0000006000000060000000600000006000000060000000E0000000C0000000C0000000C0000001C000000180000003800000 03000000070000000E0000000C0000001C0000003800000070000000E0000001C00000078000000E0000007C000003F00000 FF800000FC000000> 32 27 25 25 49.812] 8 @dc [ 32 27 25 0 49.812] 9 @dc [ 1500 ] /@F65 @newfont @F65 @sf [<000000000600060006000F000F000F001F801F801F803FC03FC07FE07FE0FFF0FFF0> 16 17 6 0 41.510] 63 @dc [<000180000780001F8000FF8007FF803FFF803FFF8007FF8000FF80001F80000780000180> 24 12 0 6 41.510] 27 @dc [ 48 16 1 1 41.510] 16 @dc [ 24 12 -25 6 41.510] 45 @dc [ 48 44 1 1 41.510] 0 @dc [<0000000000300000000000700000000000E00000000001C0000000000380000000000700000000000E00000000001C000000 0000380000000000700000000000E00000000001C0000000000380000000000700000000000E00000000001C000000000038 0000000000700000000000E00000000001C0000000000380000000000700000000000E00000000001C000000000038000000 0000700000000000E00000000001C0000000000380000000000700000000000E00000000001C000000000038000000000070 0000000000E00000000001C0000000000380000000000700000000000E00000000001C000000000038000000000070000000 0000E00000000000C00000000000> 48 44 1 1 41.510] 64 @dc [<000100000600000E00003C0000F80007F8003FF000FFF0007FE0003FE0001FE0000FC00007C00003C000018000008000> 24 16 -26 0 41.510] 82 @dc 4 @bop1 516 852 p 360 2 ru 515 851 p 2 780 ru 516 762 p 360 2 ru 516 672 p 360 2 ru 516 582 p 720 2 ru 516 492 p 720 2 ru 516 342 p 720 2 ru 516 252 p 720 2 ru 516 162 p 720 2 ru 516 72 p 720 2 ru 875 851 p 2 360 ru 875 342 p 2 270 ru 1235 581 p 2 510 ru @P33 @sfps 276 821 p (Hint) s 324 r 50 c 276 731 p (Count) s 294 r 51 c 276 641 p (Lock) s 281 r (free) s 216 551 p (Queue) s 15 r (31) s 276 432 p 46 c 7 r 46 c 8 r 46 c 216 312 p (Queue) s 15 r 50 c 216 222 p (Queue) s 15 r 49 c 216 132 p (Queue) s 15 r 48 c @F67 @sf 1415 507 p 11 c 1415 542 p 2 10 ru 1415 567 p 10 c 1715 507 p 8 c 1715 542 p 2 10 ru 1715 567 p 9 c -323 r 250 2 ru 1441 507 p 250 2 ru @P33 @sfps 1491 551 p (Thread) s @F67 @sf 1415 268 p 11 c 1415 302 p 2 10 ru 1415 327 p 10 c 1715 268 p 8 c 1715 302 p 2 10 ru 1715 327 p 9 c -323 r 250 2 ru 1441 268 p 250 2 ru @P33 @sfps 1491 312 p (Thread) s @F67 @sf 1415 88 p 11 c 1415 122 p 2 10 ru 1415 148 p 10 c 1715 88 p 8 c 1715 122 p 2 10 ru 1715 148 p 9 c -323 r 250 2 ru 1441 88 p 250 2 ru @P33 @sfps 1491 132 p (Thread) s 1565 266 p 2 120 ru @F65 @sf 1 r 63 c 1056 297 p 360 2 ru 1056 297 p 27 c 1056 537 p 360 2 ru 1056 536 p 27 c 696 297 p 16 c 737 283 p 16 c 779 269 p 16 c 820 255 p 16 c 862 241 p 16 c 903 227 p 16 c 945 213 p 16 c 986 200 p 16 c 1028 186 p 16 c 1069 172 p 16 c 1111 158 p 16 c 1152 144 p 16 c 1194 130 p 16 c 1200 128 p 16 c 1236 117 p 180 2 ru 1374 117 p 45 c 696 536 p 0 c 737 495 p 0 c 744 488 p 0 c 786 447 p 570 2 ru 1356 488 p 64 c 1380 512 p 64 c -40 r 82 c @P33 @sfps 640 949 p (Figure) s 15 r (1:) s 21 r (Mach) s 15 r (run) s 15 r (queue) s 15 r (structure) s 0 1082 p (containing) s 15 r (the) s 15 r (threads) s 15 r (are) s 15 r (doubly-linked,) s 16 r (but) s 15 r (only) s 15 r (the) s 15 r (forward) s 15 r (links) s 15 r (are) s 15 r (shown) s 15 r (for) s 15 r (clarity) s -2 r 46 c 20 r (The) s 15 r (hint) s 15 r (is) s 15 r (2,) s 0 1139 p (indicating) s 15 r (that) s 15 r (queues) s 15 r 48 c 16 r (and) s 15 r 49 c 15 r (are) s 15 r (empty) s 15 r (and) s 15 r (can) s 16 r (be) s 15 r (skipped) s 15 r (in) s 15 r 97 c 15 r (search) s 15 r (for) s 15 r (the) s 16 r (highest) s 15 r (priority) s 15 r (thread.) s 62 1246 p (Each) s 16 r (processor) s 16 r (consults) s 16 r (the) s 15 r (appropriate) s 16 r (run) s 16 r (queues) s 15 r (when) s 16 r 97 c 16 r (new) s 16 r (thread) s 15 r (is) s 16 r (needed) s 16 r (for) s 16 r (execution.) s 22 r (The) s 0 1303 p (kernel) s 12 r (maintains) s 13 r 97 c @P37 @sfps 12 r (local) s 13 r (run) s 12 r (queue) s @P33 @sfps 13 r (for) s 12 r (each) s 13 r (processor) s 12 r (and) s 13 r 97 c 12 r (shared) s @P37 @sfps 13 r (global) s 12 r (run) s 13 r (queue) s @P33 @sfps 0 r 46 c 19 r (The) s 12 r (local) s 13 r (run) s 12 r (queue) s 0 1359 p (is) s 13 r (used) s 14 r (by) s 13 r (threads) s 13 r (that) s 14 r (have) s 13 r (been) s 13 r (temporarily) s 14 r (bound) s 13 r (to) s 13 r 97 c 14 r (speci) s 0 r 174 c 0 r 99 c 13 r (processor) s 13 r (for) s 14 r (one) s 13 r (of) s 14 r (two) s 13 r (reasons.) s 19 r (Some) s 0 1416 p (of) s 14 r (the) s 14 r (Unix) s 14 r (compatibility) s 15 r (code) s 14 r (in) s 14 r (current) s 14 r (Mach) s 14 r (kernels) s 14 r (has) s 15 r (not) s 14 r (been) s 14 r (converted) s 14 r (for) s 14 r (parallel) s 14 r (execution) s @P13 @sfps 1874 1399 p 55 c @P33 @sfps 1906 1416 p (so) s 0 1472 p (threads) s 15 r (executing) s 16 r (in) s 15 r (the) s 15 r (unparallelized) s 16 r (portion) s 15 r (of) s 15 r (this) s 16 r (code) s 15 r (are) s 15 r (temporarily) s 16 r (bound) s 15 r (to) s 15 r 97 c 16 r (single) s 15 r (designated) s @P37 @sfps 0 1529 p (master) s 19 r (pr) s 0 r (ocessor) s @P33 @sfps 0 r 46 c 31 r (Interrupts) s 20 r (that) s 19 r (invoke) s 19 r (Unix) s 20 r (compatibility) s 19 r (code) s 19 r (are) s 19 r (also) s 20 r (restricted) s 19 r (to) s 19 r (this) s 20 r (processor) s -2 r 46 c 0 1585 p (The) s 19 r (remaining) s 18 r (use) s 19 r (of) s 19 r (the) s 18 r (local) s 19 r (run) s 18 r (queues) s 19 r (is) s 19 r (made) s 18 r (by) s 19 r (the) s 19 r (processor) s 18 r (allocation) s 19 r (operation) s 19 r (described) s 18 r (in) s 0 1642 p (Section) s 14 r (6.) s 20 r (Mach) s 14 r (is) s 14 r (self) s 13 r (scheduling) s 14 r (in) s 14 r (that) s 14 r (processors) s 14 r (consult) s 14 r (the) s 14 r (run) s 14 r (queues) s 14 r (individually) s 14 r (when) s 14 r (they) s 14 r (need) s 0 1698 p 97 c 14 r (new) s 14 r (thread) s 14 r (to) s 13 r (run) s 14 r (instead) s 14 r (of) s 14 r (having) s 14 r 97 c 14 r (centralized) s 14 r (dispatcher) s 13 r (assign) s 14 r (threads) s 14 r (to) s 14 r (processors.) s 20 r (The) s 14 r (local) s 13 r (run) s 0 1754 p (queue) s 16 r (is) s 15 r (examined) s 16 r 174 c 0 r (rst) s 16 r (to) s 15 r (give) s 16 r (absolute) s 16 r (preference) s 15 r (to) s 16 r (bound) s 16 r (threads) s 16 r (over) s 15 r (unbound) s 16 r (threads.) s 22 r (This) s 15 r (avoids) s 0 1811 p (bottlenecks) s 16 r (by) s 15 r (maximizing) s 16 r (throughput) s 15 r (of) s 16 r (the) s 16 r (unparallelized) s 15 r (Unix) s 16 r (compatibility) s 15 r (code) s @P13 @sfps 1580 1794 p 56 c @P33 @sfps 1598 1811 p 44 c 16 r (and) s 16 r (improves) s 15 r (the) s 0 1867 p (performance) s 12 r (of) s 12 r (processor) s 13 r (allocation) s 12 r (by) s 12 r (causing) s 12 r (it) s 13 r (to) s 12 r (preempt) s 12 r (other) s 12 r (operations.) s 20 r (If) s 12 r (the) s 12 r (local) s 12 r (queue) s 12 r (is) s 13 r (empty) s -2 r 44 c 0 1924 p (then) s 16 r (the) s 17 r (global) s 16 r (run) s 16 r (queue) s 16 r (is) s 17 r (examined.) s 23 r (In) s 17 r (both) s 16 r (cases) s 16 r (the) s 17 r (highest) s 16 r (priority) s 16 r (thread) s 16 r (found) s 17 r (is) s 16 r (dequeued) s 16 r (and) s 0 1980 p (run) s 15 r (by) s 15 r (the) s 15 r (processor) s -1 r 46 c 19 r (If) s 15 r (both) s 15 r (run) s 16 r (queues) s 15 r (are) s 15 r (empty) s -2 r 44 c 14 r (the) s 15 r (processor) s 15 r (becomes) s 16 r (idle.) s 62 2078 p (Special) s 15 r (mechanisms) s 15 r (are) s 15 r (used) s 15 r (for) s 15 r (idle) s 15 r (processors.) s 20 r (Most) s 15 r (uniprocessor) s 15 r (systems) s 15 r (borrow) s 15 r (the) s 15 r (kernel) s 15 r (stack) s 0 2135 p (of) s 15 r (the) s 16 r (thread) s 15 r (or) s 15 r (process) s 16 r (that) s 15 r (ran) s 15 r (most) s 16 r (recently) s 15 r (to) s 15 r (execute) s 16 r (the) s 15 r (idle) s 15 r (loop.) s 21 r (On) s 16 r 97 c 15 r (multiprocessor) s 15 r (this) s 16 r (can) s 15 r (be) s 0 2191 p (disastrous) s 16 r (if) s 16 r (the) s 16 r (thread) s 16 r (resumes) s 16 r (execution) s 16 r (on) s 17 r (another) s 16 r (processor) s 16 r (because) s 16 r (the) s 16 r (two) s 16 r (processors) s 16 r (will) s 16 r (corrupt) s 0 2248 p (the) s 18 r (thread') s -2 r 115 c 17 r (kernel) s 18 r (stack.) s 29 r (Mach) s 18 r (avoids) s 18 r (this) s 18 r (stack) s 18 r (corruption) s 18 r (by) s 18 r (using) s 18 r 97 c 18 r (dedicated) s @P37 @sfps 18 r (idle) s 18 r (thr) s -1 r (ead) s @P33 @sfps 17 r (for) s 18 r (each) s 0 2304 p (processor) s -2 r 46 c 29 r (Idle) s 19 r (processors) s 18 r (are) s 19 r (dispatched) s 18 r (by) s 18 r 97 c 19 r (mechanism) s 18 r (that) s 19 r (bypasses) s 18 r (the) s 18 r (run) s 19 r (queues.) s 30 r (Threads) s 18 r (that) s 0 2360 p (become) s 21 r (runnable) s 21 r (are) s 21 r (matched) s 21 r (with) s 21 r (idle) s 21 r (processors.) s 38 r (The) s 21 r (idle) s 21 r (thread) s 21 r (on) s 21 r (each) s 21 r (processor) s 21 r (picks) s 21 r (up) s 21 r (the) s 0 2417 p (corresponding) s 16 r (new) s 16 r (thread) s 15 r (and) s 16 r (context) s 16 r (switches) s 16 r (directly) s 16 r (to) s 15 r (it,) s 16 r (gaining) s 16 r (performance) s 16 r (by) s 16 r (bypassing) s 15 r (the) s 16 r (run) s 0 2473 p (queues.) s 24 r (This) s 16 r (mechanism) s 17 r (is) s 16 r (one) s 17 r (example) s 16 r (of) s 16 r 97 c 17 r (general) s 16 r (technique) s 17 r (called) s 16 r (Handof) s 0 r 102 c 16 r (Scheduling) s 16 r (that) s 16 r (context) s 0 2530 p (switches) s 15 r (directly) s 15 r (to) s 15 r 97 c 16 r (new) s 15 r (thread) s 15 r (without) s 15 r (searching) s 15 r (for) s 15 r (it) s 16 r (on) s 15 r 97 c 15 r (run) s 15 r (queue.) s 0 2577 p 779 2 ru @P4 @sfps 53 2634 p 55 c @P18 @sfps 67 2650 p (Most) s 13 r (of) s 12 r (this) s 13 r (code) s 12 r (has) s 13 r (been) s 12 r (parallelized,) s 12 r (see) s 13 r 91 c 0 r 53 c 0 r 93 c 12 r (for) s 13 r (details.) s @P4 @sfps 53 2710 p 56 c @P18 @sfps 67 2726 p (See) s 13 r 91 c 0 r 54 c 0 r 93 c 12 r (for) s 13 r (an) s 12 r (extensive) s 13 r (study) s 12 r (of) s 12 r (this) s 13 r (area) s @P33 @sfps 962 2843 p 52 c @eop 5 @bop0 [ 1643 ] /@F35 @newfont @F35 @sf [ 24 45 -3 11 22.727] 61 @dc [ 1500 ] /@F20 @newfont @F20 @sf [<60F0F060> 8 4 -3 0 10.666] 58 @dc [ 16 37 -2 9 19.198] 61 @dc 5 @bop1 @P38 @sfps 0 42 p (3.2.) s 45 r (Priority) s 16 r (Calculations) s @P33 @sfps 0 170 p (Thread) s 16 r (priorities) s 15 r (consist) s 16 r (of) s 15 r 97 c 16 r (base) s 15 r (priority) s 16 r (plus) s 16 r (an) s 15 r (of) s 0 r (fset) s 15 r (derived) s 15 r (from) s 16 r (recent) s 16 r (processor) s 15 r (usage.) s 22 r (The) s 15 r (base) s 0 226 p (priority) s 18 r (is) s 19 r (set) s 18 r (low) s 19 r (enough) s 18 r (to) s 19 r (allow) s 18 r (internal) s 18 r (kernel) s 19 r (threads) s 18 r (to) s 19 r (run) s 18 r (at) s 19 r (higher) s 18 r (priorities) s 18 r (than) s 19 r (user) s 18 r (threads) s 0 283 p (because) s 17 r (the) s 17 r (internal) s 17 r (threads) s 17 r (perform) s 17 r (critical) s 17 r (kernel) s 17 r (functions) s 17 r (such) s 17 r (as) s 17 r (pageout.) s 26 r (The) s 17 r (of) s 0 r (fset) s 17 r (derived) s 17 r (from) s 0 339 p (usage) s 10 r (is) s 11 r (weighted) s 10 r (by) s 11 r (the) s 10 r (load) s 11 r (factor) s 10 r (to) s 11 r (preserve) s 10 r (system) s 11 r (responsiveness) s 10 r (under) s 11 r (load.) s 18 r (If) s 11 r (an) s 10 r (adequate) s 11 r (hardware) s 0 396 p (source) s 18 r (of) s 18 r (timestamps) s 19 r (exists,) s 19 r (such) s 18 r (as) s 18 r 97 c 18 r (32-bit) s 18 r (microsecond) s 19 r (counter) s -1 r 44 c 18 r (the) s 18 r (scheduler) s 18 r (can) s 19 r (be) s 18 r (con) s 0 r 174 c 0 r (gured) s 18 r (to) s 0 452 p (base) s 14 r (usage) s 14 r (calculations) s 14 r (on) s 14 r (timestamps) s 14 r (from) s 14 r (this) s 14 r (counter) s -1 r 46 c 19 r (This) s 14 r (eliminates) s 14 r (the) s 14 r (inaccuracies) s 14 r (and) s 14 r (distortions) s 0 509 p (caused) s 15 r (by) s 15 r (statistical) s 15 r (usage) s 16 r (calculations) s 15 r (\(see) s 15 r 91 c 0 r 54 c 0 r 93 c 15 r (for) s 15 r (details\).) s 62 607 p (Mach) s 14 r (uses) s 14 r (the) s 14 r (overload) s 14 r (factor) s 13 r (technique) s 14 r (for) s 14 r (processor) s 14 r (usage) s 14 r (aging.) s 19 r (The) s 14 r (aging) s 14 r (overhead) s 14 r (is) s 14 r (distributed) s 0 663 p (by) s 19 r (making) s 20 r (each) s 19 r (thread) s 20 r (responsible) s 19 r (for) s 19 r (aging) s 20 r (of) s 19 r (its) s 20 r (processor) s 19 r (usage.) s 33 r (Clock) s 19 r (interrupts) s 20 r (and) s 19 r (events) s 19 r (that) s 0 720 p (unblock) s 16 r 97 c 16 r (thread) s 15 r (cause) s 16 r (it) s 16 r (to) s 16 r (check) s 16 r (its) s 16 r (local) s 15 r (copy) s 16 r (of) s 16 r 97 c 16 r (counter) s 16 r (against) s 16 r 97 c 15 r (global) s 16 r (value) s 16 r (that) s 16 r (is) s 16 r (incremented) s 0 776 p (once) s 21 r 97 c 21 r (second.) s 37 r (If) s 21 r (these) s 21 r (values) s 21 r (dif) s 0 r (fer) s -2 r 44 c 21 r (the) s 21 r (thread) s 21 r (ages) s 21 r (its) s 21 r (usage) s 20 r (by) s 21 r 97 c 21 r (factor) s 21 r (of) s 21 r 53 c @F35 @sf 0 r 61 c @P33 @sfps 0 r 56 c 21 r (for) s 21 r (each) s 20 r (unit) s 21 r (of) s 0 833 p (dif) s 0 r (ference.) s 20 r (This) s 16 r (results) s 15 r (in) s 16 r (each) s 15 r (thread') s -1 r 115 c 14 r (accumulated) s 16 r (usage) s 15 r (being) s 16 r (multiplied) s 15 r (by) s 16 r 53 c @F35 @sf 0 r 61 c @P33 @sfps 0 r 56 c 15 r (once) s 16 r 97 c 15 r (second.) s 21 r 53 c @F35 @sf 0 r 61 c @P33 @sfps 0 r 56 c 0 889 p (was) s 16 r (chosen) s 17 r (to) s 16 r (produce) s 17 r (behavior) s 16 r (similar) s 16 r (to) s 17 r (other) s 16 r (timesharing) s 17 r (systems) s @P13 @sfps 1299 872 p 57 c @P33 @sfps 1318 889 p 44 c 16 r (and) s 17 r (because) s 16 r (multiplication) s 17 r (by) s 16 r (it) s 0 945 p (can) s 16 r (be) s 16 r (ef) s 0 r 174 c 0 r (ciently) s 15 r (without) s 16 r (using) s 16 r (multiplication) s 16 r (or) s 16 r (division.) s 23 r (Mach) s 16 r (uses) s 16 r (an) s 16 r (overload) s 16 r (factor) s 16 r (of) s 16 r (the) s 16 r (number) s 0 1002 p (of) s 15 r (runnable) s 15 r (threads) s 15 r (divided) s 15 r (by) s 15 r (the) s 16 r (number) s 15 r (of) s 15 r (processors) s 15 r (with) s 15 r 97 c 15 r (minimum) s 15 r (of) s 15 r (1.) s 20 r (This) s 15 r (factor) s 15 r (is) s 16 r (calculated) s 0 1058 p (as) s 15 r (an) s 15 r (exponential) s 15 r (average) s 16 r (to) s 15 r (smooth) s 15 r (the) s 15 r (impact) s 15 r (of) s 15 r (abrupt) s 16 r (load) s 15 r (changes.) s 62 1156 p (This) s 15 r (scheduling) s 15 r (algorithm) s 14 r (requires) s 15 r (that) s 15 r (all) s 14 r (threads) s 15 r (check) s 15 r (their) s 14 r (copy) s 15 r (of) s 15 r (the) s 14 r (counter) s 15 r (on) s 15 r 97 c 14 r (regular) s 15 r (basis.) s 0 1213 p (The) s 12 r (clock) s 13 r (interrupt) s 12 r (handler) s 13 r (performs) s 12 r (this) s 12 r (check) s 13 r (for) s 12 r (running) s 12 r (threads,) s 13 r (and) s 13 r (threads) s 12 r (that) s 12 r (are) s 13 r (not) s 12 r (running) s 13 r (defer) s 0 1269 p (this) s 16 r (check) s 16 r (until) s 16 r (they) s 16 r (become) s 16 r (runnable.) s 23 r (Runnable) s 16 r (threads) s 15 r (with) s 16 r (low) s 16 r (priorities) s 16 r (may) s 16 r (spend) s 16 r (long) s 16 r (periods) s 16 r (of) s 0 1326 p (time) s 11 r (on) s 11 r 97 c 10 r (run) s 11 r (queue) s 11 r (while) s 11 r (higher) s 10 r (priority) s 11 r (threads) s 11 r (monopolize) s 11 r (the) s 10 r (processor) s -1 r 46 c 18 r (Such) s 10 r (threads) s 11 r (would) s 11 r (run) s 11 r (if) s 10 r (they) s 0 1382 p (could) s 12 r (check) s 12 r (their) s 12 r (copy) s 13 r (of) s 12 r (the) s 12 r (counter) s 12 r (and) s 12 r (age) s 12 r (their) s 12 r (usage,) s 13 r (but) s 12 r (their) s 12 r (low) s 13 r (priority) s 12 r (positions) s 12 r (on) s 12 r (the) s 12 r (run) s 12 r (queue) s 0 1439 p (prevent) s 16 r (them) s 16 r (from) s 16 r (running) s 15 r (to) s 16 r (perform) s 16 r (this) s 16 r (check.) s 22 r 84 c -2 r 111 c 15 r (avoid) s 16 r (the) s 16 r (resulting) s 16 r (starvation) s 16 r (situation) s 15 r (an) s 16 r (internal) s 0 1495 p (kernel) s 18 r (thread) s 17 r (scans) s 18 r (the) s 17 r (run) s 18 r (queues) s 17 r (once) s 18 r (every) s 17 r (two) s 18 r (seconds) s 17 r (to) s 18 r (perform) s 17 r (the) s 18 r (aging) s 18 r (and) s 17 r (resulting) s 18 r (priority) s 0 1551 p (elevation) s 20 r (for) s 19 r (any) s 20 r (threads) s 20 r (in) s 19 r (this) s 20 r (situation.) s 34 r (The) s 20 r (two) s 19 r (second) s 20 r (period) s 20 r (was) s 19 r (chosen) s 20 r (to) s 20 r (produce) s 20 r (acceptable) s 0 1608 p (behavior) s 15 r (based) s 15 r (on) s 15 r (experience) s 16 r (with) s 15 r (versions) s 15 r (of) s 15 r (the) s 15 r (system) s 15 r (that) s 16 r (exhibited) s 15 r (this) s 15 r (starvation) s 15 r (behavior) s -2 r 46 c @P38 @sfps 0 1769 p (3.3.) s 45 r (Managing) s 16 r (Context) s 15 r (Switches) s @P33 @sfps 0 1898 p (The) s 11 r (scheduler) s 11 r (utilizes) s 10 r (time) s 11 r (quanta) s 11 r (to) s 11 r (minimize) s 11 r (the) s 10 r (number) s 11 r (of) s 11 r (context) s 11 r (switches) s 11 r (it) s 10 r (causes.) s 19 r (When) s 11 r 97 c 11 r (processor) s 0 1954 p (begins) s 16 r (to) s 17 r (run) s 16 r 97 c 16 r (thread,) s 17 r (that) s 16 r (thread) s 16 r (is) s 16 r (assigned) s 17 r 97 c 16 r (time) s 16 r (quantum.) s 24 r (Periodic) s 16 r (clock) s 16 r (interrupts) s 17 r (decrement) s 16 r (this) s 0 2010 p (quantum,) s 14 r (and) s 14 r 97 c 14 r (rescheduling) s 14 r (check) s 14 r (occurs) s 14 r (when) s 13 r (the) s 14 r (quantum) s 14 r (expires) s 14 r (if) s 14 r (the) s 14 r (thread) s 14 r (does) s 14 r (not) s 14 r (stop) s 13 r (or) s 14 r (block) s 0 2067 p (before) s 14 r (then.) s 20 r (This) s 14 r (rescheduling) s 15 r (check) s 14 r (causes) s 14 r 97 c 14 r (context) s 14 r (switch) s 15 r (if) s 14 r (there) s 14 r (is) s 14 r (another) s 15 r (thread) s 14 r (to) s 14 r (run) s 14 r (of) s 15 r (equal) s 14 r (or) s 0 2123 p (higher) s 15 r (priority) s -2 r 44 c 14 r (otherwise) s 15 r (the) s 14 r (original) s 15 r (thread) s 15 r (continues) s 15 r (running) s 15 r (with) s 14 r 97 c 15 r (new) s 15 r (quantum.) s 20 r (The) s 15 r (context) s 15 r (switch) s 0 2180 p (mechanism) s 21 r (uses) s 21 r (an) s 21 r (AST) s 21 r (\(Asynchronous) s 22 r (System) s 21 r 84 c -1 r (rap\)) s 20 r (to) s 21 r (avoid) s 21 r (context) s 22 r (switches) s 21 r (in) s 21 r (interrupt) s 21 r (service) s 0 2236 p (routines.) s 29 r (An) s 18 r (AST) s 18 r (is) s 18 r 97 c 18 r (general) s 18 r (mechanism) s 18 r (that) s 18 r (allows) s 18 r (an) s 18 r (interrupt) s 18 r (service) s 18 r (routine) s 18 r (to) s 18 r (force) s 18 r (the) s 18 r (current) s 0 2293 p (thread) s 12 r (to) s 12 r (trap) s 12 r (into) s 13 r (the) s 12 r (kernel) s 12 r (from) s 12 r (user) s 12 r (mode.) s 19 r (AST') s -1 r 115 c 11 r (may) s 12 r (be) s 12 r (directly) s 13 r (supported) s 12 r (in) s 12 r (hardware,) s 13 r (implemented) s 0 2349 p (entirely) s 14 r (in) s 13 r (software,) s 14 r (or) s 14 r 97 c 13 r (combination) s 14 r (of) s 13 r (the) s 14 r (two.) s 19 r (Priority) s 14 r (reductions) s 14 r (due) s 13 r (to) s 14 r (processor) s 13 r (usage) s 14 r (accumulated) s 0 2406 p (during) s 13 r 97 c 13 r (thread') s -1 r 115 c 12 r 174 c 0 r (rst) s 13 r (quantum) s 13 r (do) s 13 r (not) s 13 r (cause) s 13 r (context) s 13 r (switches.) s 20 r (This) s 13 r (feature) s 13 r (reduces) s 13 r (the) s 13 r (number) s 14 r (of) s 13 r (context) s 0 2462 p (switches) s 15 r (for) s 15 r (load) s 15 r (and) s 16 r (usage) s 15 r (balancing) s 15 r (by) s 15 r (extending) s 15 r (the) s 15 r (time) s 16 r (period) s 15 r (between) s 15 r (context) s 15 r (switches.) s 62 2560 p (Context) s 13 r (switches) s 12 r (are) s 13 r (also) s 12 r (used) s 13 r (to) s 12 r (implement) s 13 r (preemption) s 12 r (of) s 13 r (lower) s 12 r (priority) s 13 r (threads) s 12 r (when) s 13 r (higher) s 13 r (priority) s 0 2616 p (threads) s 15 r (become) s 16 r (runnable.) s 21 r (Preemption) s 15 r (occurs) s 16 r (immediately) s 15 r (on) s 16 r 97 c 15 r (uniprocessor) s 15 r (where) s 16 r (an) s 15 r (AST) s 16 r (is) s 15 r (requested) s 0 2653 p 779 2 ru @P4 @sfps 53 2710 p 57 c @P18 @sfps 67 2726 p (The) s 13 r (number) s 12 r (used) s 13 r (by) s 12 r (4.3BSD) s 13 r (Unix) s 12 r (depends) s 12 r (on) s 13 r (load.) s 16 r (For) s 13 r (the) s 12 r (range) s 13 r (from) s 12 r 48 c @F20 @sf 0 r 58 c @P18 @sfps 0 r 53 c 13 r (to) s 12 r 49 c @F20 @sf 0 r 58 c @P18 @sfps 0 r (0,) s 13 r (it) s 12 r (varies) s 13 r (from) s 12 r 49 c @F20 @sf 0 r 61 c @P18 @sfps 0 r 50 c 12 r (to) s 13 r 50 c @F20 @sf 0 r 61 c @P18 @sfps 0 r (3[) s 0 r 50 c 0 r (].) s @P33 @sfps 962 2843 p 53 c @eop 6 @bop0 [ 1643 ] /@F36 @newfont @F36 @sf [ 32 36 -4 7 35.353] 21 @dc 6 @bop1 571 43 p 790 2 ru 570 100 p 2 56 ru @P33 @sfps 630 83 p (Relationship) s 918 100 p 2 56 ru 8 r 2 56 ru 1085 83 p (Model) s 1360 100 p 2 56 ru 571 101 p 790 2 ru 571 111 p 790 2 ru 570 168 p 2 56 ru @P34 @sfps 596 151 p (MR) s @P33 @sfps 13 r 61 c @P34 @sfps 12 r (VP) s @P33 @sfps 13 r 61 c @P34 @sfps 12 r (PP) s 918 168 p 2 56 ru 8 r 2 56 ru @P33 @sfps 952 151 p (Pure) s 15 r (Parallelism) s 1360 168 p 2 56 ru 571 169 p 790 2 ru 570 226 p 2 56 ru @P34 @sfps 596 209 p (MR) s @F36 @sf 13 r 21 c @P34 @sfps 12 r (VP) s @P33 @sfps 13 r 61 c @P34 @sfps 12 r (PP) s 918 226 p 2 56 ru 8 r 2 56 ru @P33 @sfps 952 209 p (User) s 15 r (Concurrency) s 1360 226 p 2 56 ru 571 227 p 790 2 ru 570 284 p 2 56 ru @P34 @sfps 596 267 p (MR) s @P33 @sfps 13 r 61 c @P34 @sfps 12 r (VP) s @F36 @sf 13 r 21 c @P34 @sfps 12 r (PP) s 918 284 p 2 56 ru 8 r 2 56 ru @P33 @sfps 952 267 p (System) s 15 r (Concurrency) s 1360 284 p 2 56 ru 571 286 p 790 2 ru 570 342 p 2 56 ru @P34 @sfps 596 325 p (MR) s @F36 @sf 13 r 21 c @P34 @sfps 12 r (VP) s @F36 @sf 13 r 21 c @P34 @sfps 12 r (PP) s 918 342 p 2 56 ru 8 r 2 56 ru @P33 @sfps 952 325 p (Dual) s 15 r (Concurrency) s 1360 342 p 2 56 ru 571 344 p 790 2 ru 293 420 p 84 c -2 r (able) s 14 r (1:) s 20 r (Programming) s 16 r (Models) s 15 r (for) s 15 r (Parallel) s 15 r (and) s 15 r (Concurrent) s 15 r (Programming) s 0 550 p (as) s 20 r (part) s 20 r (of) s 20 r (making) s 20 r (the) s 20 r (higher) s 20 r (priority) s 21 r (thread) s 20 r (runnable,) s 21 r (but) s 20 r (it) s 20 r (may) s 20 r (take) s 20 r (up) s 20 r (to) s 20 r 97 c 20 r (clock) s 20 r (interrupt) s 21 r (period) s 0 607 p (on) s 18 r 97 c 18 r (multiprocessor) s 18 r (if) s 19 r (another) s 18 r (processor) s 18 r (must) s 18 r (notice) s 18 r (the) s 18 r (presence) s 18 r (of) s 19 r 97 c 18 r (higher) s 18 r (priority) s 18 r (thread) s 18 r (on) s 18 r 97 c 18 r (run) s 0 663 p (queue.) s 19 r (Mach) s 12 r (does) s 12 r (not) s 12 r (use) s 12 r (interprocessor) s 12 r (interrupts) s 12 r (for) s 12 r (preemption) s 12 r (because) s 11 r (they) s 12 r (haven') s 0 r 116 c 12 r (been) s 11 r (necessary) s 12 r (to) s 0 720 p (achieve) s 10 r (acceptable) s 10 r (timesharing) s 10 r (behavior) s -1 r 46 c 17 r 65 c 11 r (consequence) s 10 r (of) s 10 r (this) s 10 r (is) s 10 r (that) s 10 r (the) s 11 r (scheduler) s 10 r (does) s 10 r (not) s 10 r (maintain) s 10 r (data) s 0 776 p (structures) s 15 r (that) s 15 r (would) s 16 r (permit) s 15 r (the) s 15 r (ef) s 0 r 174 c 0 r (cient) s 15 r (identi) s 0 r 174 c 0 r (cation) s 15 r (of) s 15 r (the) s 15 r (lowest) s 15 r (priority) s 16 r (processor) s 15 r (when) s 15 r (preemption) s 0 833 p (is) s 17 r (needed.) s 26 r (The) s 17 r (use) s 17 r (of) s 17 r (interprocessor) s 18 r (interrupts) s 17 r (for) s 17 r (preemption) s 17 r (is) s 17 r (expected) s 17 r (to) s 17 r (be) s 17 r (added) s 17 r (in) s 17 r (the) s 17 r (future) s 18 r (as) s 0 889 p (Mach) s 15 r (evolves) s 15 r (to) s 15 r (include) s 16 r (support) s 15 r (for) s 15 r (some) s 15 r (real-time) s 15 r (applications.) s @P38 @sfps 0 1057 p (4.) s 45 r (Pr) s 0 r (ogramming) s 15 r (Models) s @P33 @sfps 0 1202 p (Programming) s 14 r (models) s 15 r (for) s 14 r (applications) s 14 r (can) s 15 r (introduce) s 14 r (concurrency) s 14 r (beyond) s 15 r (the) s 14 r (hardware) s 14 r (parallelism) s 15 r (at) s 14 r (two) s 0 1258 p (levels.) s 25 r (An) s 16 r (operating) s 17 r (system) s 16 r (can) s 17 r (introduce) s 17 r (concurrency) s 16 r (by) s 17 r (providing) s 17 r (independently) s 16 r (schedulable) s 17 r (entities) s 0 1315 p (such) s 12 r (as) s 12 r (Unix) s 12 r (processes) s 12 r (or) s 13 r (Mach) s 12 r (threads) s 12 r (that) s 12 r (it) s 12 r (multiplexes) s 12 r (onto) s 12 r (the) s 12 r (hardware) s 13 r (processors.) s 19 r (This) s 12 r (article) s 12 r (uses) s 0 1371 p (the) s 12 r (term) s @P37 @sfps 12 r (virtual) s 12 r (pr) s -1 r (ocessor) s @P33 @sfps 11 r (or) s 12 r (VP) s 12 r (for) s 12 r (these) s 12 r (entities.) s 19 r 65 c 12 r (user) s 12 r (level) s 12 r (library) s 12 r (or) s 12 r (language) s 12 r (runtime) s 12 r (may) s 12 r (choose) s 12 r (to) s 0 1428 p (introduce) s 15 r (further) s 16 r (concurrency) s 15 r (by) s 16 r (multiplexing) s 15 r (language) s 16 r (level) s 15 r (entities) s 15 r (onto) s 16 r (these) s 15 r (VPs.) s 21 r (This) s 16 r (article) s 15 r (refers) s 0 1484 p (to) s 14 r (these) s 14 r (entities) s 14 r (as) s @P37 @sfps 14 r (multir) s 0 r (outines) s @P33 @sfps 0 r 59 c 13 r (they) s 14 r (may) s 14 r (be) s 14 r (thought) s 14 r (of) s 14 r (as) s 15 r (multiprocessor) s 14 r (generalizations) s 14 r (of) s 14 r (coroutines.) s 0 1541 p (Special) s 16 r (cases) s 17 r (of) s 16 r (multiroutines) s 16 r (include) s 17 r (coroutines) s 16 r (\(only) s 16 r 49 c 17 r (VP\),) s 16 r (and) s 16 r (the) s 17 r (common) s 16 r (programming) s 16 r (notion) s 17 r (of) s 0 1597 p (multiple) s 12 r (threads) s 13 r (\(1) s 12 r (VP) s 13 r (per) s 12 r (multiroutine\)) s 13 r (as) s 12 r (found) s 12 r (the) s 13 r (Mach) s 12 r (Cthreads) s 13 r (library[) s 0 r 55 c 0 r (].) s 19 r (Multiroutines) s 12 r (and) s 13 r 86 c -2 r (irtual) s 0 1654 p (Processors) s 12 r (can) s 11 r (be) s 12 r (identi) s 0 r 174 c 0 r (ed) s 12 r (in) s 11 r (almost) s 12 r (any) s 12 r (parallel) s 12 r (programming) s 11 r (language) s 12 r (implementation) s 12 r (or) s 11 r (environment.) s 0 1710 p (One) s 17 r (example) s 17 r (is) s 17 r (that) s 17 r (an) s 17 r (Ada) s @P13 @sfps 532 1694 p (10) s @P33 @sfps 585 1710 p (runtime) s 17 r (on) s 17 r (Unix) s 17 r (would) s 17 r (use) s 17 r (Unix) s 17 r (processes) s 17 r (as) s 17 r (its) s 18 r (virtual) s 17 r (processors) s 17 r (and) s 0 1767 p (Ada) s 15 r (tasks) s 16 r (as) s 15 r (its) s 15 r (multiroutines.) s 21 r (Another) s 16 r (example) s 15 r (is) s 15 r (that) s 16 r (the) s 15 r (Mach) s 16 r (Cthreads) s 15 r (library) s 15 r (uses) s 16 r (Mach) s 15 r (threads) s 15 r (as) s 0 1823 p (its) s 15 r (virtual) s 15 r (processors) s 15 r (and) s 16 r (Cthreads) s 15 r (as) s 15 r (its) s 15 r (multiroutines.) s 62 1931 p (Programming) s 14 r (models) s 13 r (for) s 13 r (parallel) s 13 r (and) s 14 r (concurrent) s 13 r (programming) s 13 r (can) s 14 r (be) s 13 r (classi) s 0 r 174 c 0 r (ed) s 13 r (based) s 14 r (on) s 13 r (the) s 13 r (relation-) s 0 1987 p (ships) s 17 r (among) s 18 r (the) s 17 r (numbers) s 18 r (of) s 17 r (multiroutines) s 17 r 40 c @P34 @sfps 0 r (MR) s @P33 @sfps 0 r (\),) s 18 r (virtual) s 18 r (processors) s 17 r 40 c @P34 @sfps 0 r (VP) s @P33 @sfps 0 r (\),) s 18 r (and) s 18 r (physical) s 17 r (processors) s 17 r 40 c @P34 @sfps 0 r (PP) s @P33 @sfps 0 r 41 c 0 2044 p (supported) s 14 r (by) s 14 r (the) s 14 r (model) s 14 r (\(T) s -2 r (able) s 13 r (1\).) s 20 r (For) s @P37 @sfps 14 r (pur) s -1 r 101 c 13 r (parallelism) s @P33 @sfps 14 r (models,) s 15 r (the) s 14 r (programmer) s 1 r 39 c -1 r 115 c 13 r (notion) s 14 r (of) s 14 r (concurrency) s 0 2100 p (is) s 17 r (identical) s 17 r (to) s 17 r (the) s 18 r (hardware) s 17 r (parallelism.) s 26 r (Compiler) s 17 r (generated) s 17 r (code) s 17 r (for) s 17 r (parallel) s 18 r (execution) s 17 r (of) s 17 r (loop) s 17 r (bodies) s 0 2157 p (is) s 16 r 97 c 15 r (common) s 16 r (example.) s @P37 @sfps 21 r (User) s 16 r (concurr) s -1 r (ency) s @P33 @sfps 14 r (models) s 16 r (introduce) s 15 r (additional) s 16 r (concurrency) s 16 r (at) s 15 r (the) s 16 r (user) s 15 r (level.) s 22 r (An) s 0 2213 p (example) s 13 r (is) s 13 r (programs) s 13 r (based) s 12 r (on) s 13 r 97 c 13 r (queue) s 13 r (of) s 13 r (user) s 0 r (-de) s 0 r 174 c 0 r (ned) s 12 r (tasks) s 13 r (that) s 12 r (are) s 13 r (dequeued) s 13 r (and) s 13 r (executed) s 13 r (in) s 13 r (parallel) s 13 r (by) s 0 2269 p (virtual) s 16 r (processors.) s 25 r 65 c @P37 @sfps 16 r (cor) s -1 r (outine) s @P33 @sfps 16 r (model) s 16 r (is) s 17 r 97 c 16 r (user) s 17 r (concurrency) s 16 r (model) s 17 r (with) s 16 r (exactly) s 16 r (one) s 17 r (physical) s 16 r (processor) s 0 2326 p (and) s 17 r (hence) s 16 r (also) s 17 r (one) s 17 r (virtual) s 16 r (processor) s -1 r 46 c 23 r (The) s @P37 @sfps 17 r (system) s 17 r (concurr) s -1 r (ency) s @P33 @sfps 16 r (models) s 16 r (introduce) s 17 r (additional) s 17 r (concurrency) s 0 2382 p (only) s 14 r (at) s 14 r (the) s 14 r (system) s 15 r (level.) s 19 r (This) s 15 r (class) s 14 r (of) s 14 r (model) s 14 r (is) s 14 r (used) s 14 r (by) s 15 r (most) s 14 r (multithreading) s 14 r (packages) s 14 r (and) s 14 r (many) s 14 r (parallel) s 0 2439 p (language) s 16 r (runtime) s 16 r (systems.) s 22 r (Finally) s -2 r 44 c 15 r (the) s 16 r (relatively) s 15 r (new) s 16 r (class) s 16 r (of) s @P37 @sfps 16 r (dual) s 16 r (concurr) s -1 r (ency) s @P33 @sfps 15 r (models) s 15 r (introduces) s 16 r (con-) s 0 2495 p (currency) s 14 r (at) s 14 r (both) s 14 r (the) s 14 r (system) s 14 r (and) s 14 r (user) s 14 r (levels.) s 19 r (The) s 14 r (programming) s 14 r (model) s 14 r (for) s 14 r (an) s 14 r (application) s 14 r (depends) s 14 r (both) s 14 r (on) s 0 2552 p (the) s 15 r (programming) s 15 r (language) s 15 r (or) s 16 r (library) s 15 r (and) s 15 r (how) s 15 r (it) s 15 r (is) s 15 r (used.) s 21 r (For) s 15 r (example,) s 15 r (pure) s 15 r (parallelism) s 15 r (applications) s 15 r (can) s 0 2608 p (be) s 14 r (written) s 14 r (using) s 14 r 97 c 14 r (library) s 14 r (or) s 14 r (language) s 14 r (with) s 14 r 97 c 14 r (system) s 14 r (concurrency) s 14 r (model) s 14 r (by) s 14 r (only) s 14 r (creating) s 14 r (as) s 14 r (many) s 14 r (virtual) s 0 2653 p 779 2 ru @P4 @sfps 40 2710 p (10) s @P18 @sfps 67 2726 p (Ada) s 13 r (is) s 12 r 97 c 13 r (trademark) s 12 r (of) s 13 r (the) s 12 r (US) s 12 r (Government.) s @P33 @sfps 962 2843 p 54 c @eop 7 @bop0 7 @bop1 @P33 @sfps 0 42 p (processors) s 15 r (as) s 15 r (physical) s 15 r (processors.) s 62 139 p (Programming) s 16 r (models) s 17 r (that) s 16 r (do) s 16 r (not) s 16 r (employ) s 16 r (system) s 17 r (concurrency) s 16 r (are) s 16 r (required) s 16 r (by) s 16 r 174 c 0 r (ne) s 17 r (grain) s 16 r (applications) s 0 196 p (that) s 21 r (execute) s 21 r (tens) s 22 r (to) s 21 r (hundreds) s 21 r (of) s 21 r (instructions) s 21 r (between) s 22 r (interactions) s 21 r (with) s 21 r (other) s 21 r (multiroutines.) s 39 r (Because) s 0 252 p (virtual) s 16 r (and) s 16 r (physical) s 16 r (processors) s 16 r (correspond) s 16 r (in) s 16 r (these) s 16 r (models,) s 16 r (every) s 16 r (virtual) s 16 r (processor) s 15 r (is) s 16 r (always) s 16 r (executing.) s 0 309 p (This) s 21 r (assumption) s 20 r (is) s 21 r (incorporated) s 20 r (into) s 21 r (the) s 21 r (design) s 20 r (of) s 21 r (synchronization) s 20 r (primitives) s 21 r (for) s 20 r (these) s 21 r (models,) s 22 r (such) s 0 365 p (as) s 20 r (spin) s 19 r (locks,) s 21 r (and) s 20 r (performance) s 19 r (suf) s 0 r (fers) s 19 r (if) s 20 r (this) s 19 r (assumption) s 20 r (is) s 19 r (violated.) s 34 r (Hence) s 19 r (programs) s 20 r (that) s 20 r (use) s 19 r (these) s 0 422 p (models) s 18 r (require) s 19 r (dedicated) s 18 r (physical) s 19 r (processors.) s 30 r (The) s 18 r (only) s 19 r (exception) s 18 r (to) s 19 r (this) s 18 r (is) s 19 r (coroutine) s 18 r (models) s 18 r (because) s 0 478 p (they) s 19 r (use) s 18 r (only) s 19 r (one) s 18 r (physical) s 19 r (processor) s -2 r 46 c 30 r (The) s 19 r (major) s 18 r (disadvantage) s 19 r (of) s 18 r (these) s 19 r (classes) s 19 r (of) s 18 r (models) s 19 r (is) s 18 r (that) s 19 r (they) s 0 535 p (handle) s 18 r (blocking) s 17 r (system) s 18 r (operations) s 17 r (and) s 18 r (page) s 17 r (faults) s 18 r (inef) s 0 r 174 c 0 r (ciently) s 17 r (because) s 17 r (blocking) s 18 r 97 c 17 r (virtual) s 18 r (processor) s 17 r (in) s 0 591 p (the) s 19 r (operating) s 19 r (system) s 19 r (also) s 19 r (blocks) s 19 r 97 c 20 r (physical) s 19 r (processor) s -2 r 46 c 31 r (This) s 19 r (results) s 19 r (in) s 19 r (wasted) s 20 r (time) s 19 r (when) s 19 r (the) s 19 r (physical) s 0 648 p (processor) s 15 r (is) s 15 r (dedicated) s 15 r (to) s 16 r (the) s 15 r (application.) s 62 746 p (The) s 15 r (remaining) s 14 r (classes) s 15 r (of) s 14 r (models) s 15 r (support) s 14 r (blocking) s 15 r (operations) s 14 r (ef) s 0 r 174 c 0 r (ciently) s 14 r (but) s 15 r (are) s 14 r (inappropriate) s 15 r (for) s 14 r 174 c 0 r (ne) s 0 802 p (grain) s 18 r (applications) s 17 r (due) s 18 r (to) s 17 r (potentially) s 18 r (lar) s 0 r (ge) s 16 r (synchronization) s 18 r (overheads.) s 27 r (Blocking) s 18 r (operations) s 17 r (are) s 18 r (ef) s 0 r 174 c 0 r (cient) s 0 858 p (because) s 16 r (system) s 16 r (concurrency) s 16 r (can) s 16 r (make) s 16 r (an) s 16 r (additional) s 17 r (virtual) s 16 r (processor) s 16 r (available) s 16 r (to) s 16 r (utilize) s 16 r (the) s 16 r (time) s 16 r (relin-) s 0 915 p (quished) s 13 r (by) s 14 r 97 c 13 r (blocked) s 14 r (virtual) s 13 r (processor) s -1 r 46 c 19 r (The) s 13 r (blocking) s 14 r (nature) s 13 r (of) s 14 r (synchronization) s 13 r (in) s 14 r (languages) s 13 r (such) s 14 r (as) s 13 r (Ada) s 0 971 p (and) s 14 r (programming) s 14 r (paradigms) s 14 r (like) s 13 r (message) s 14 r (passing) s 14 r (forces) s 14 r (the) s 14 r (use) s 14 r (of) s 13 r (models) s 14 r (from) s 14 r (these) s 14 r (classes.) s 20 r (The) s 14 r (need) s 0 1028 p (for) s 13 r (dedicated) s 13 r (processors) s 13 r (in) s 13 r (these) s 13 r (models) s 14 r (is) s 13 r (application-dependent) s 13 r (rather) s 13 r (than) s 13 r (being) s 13 r (inherent) s 13 r (in) s 13 r (the) s 13 r (model.) s 0 1084 p (Applications) s 15 r (for) s 16 r (which) s 15 r (parallel) s 15 r (execution) s 15 r (is) s 16 r (important) s 15 r (may) s 15 r (need) s 15 r (dedicated) s 16 r (processors,) s 15 r (while) s 15 r (others) s 15 r (may) s 0 1141 p (not.) s 31 r (Communication) s 18 r (or) s 19 r (synchronization) s 18 r (with) s 19 r (virtual) s 19 r (processors) s 18 r (that) s 19 r (are) s 18 r (not) s 19 r (running) s 19 r (can) s 18 r (be) s 19 r (expensive) s 0 1197 p (because) s 12 r (the) s 11 r (operating) s 12 r (system) s 11 r (may) s 12 r (not) s 12 r (understand) s 11 r (which) s 12 r (virtual) s 11 r (processors) s 12 r (are) s 11 r (involved.) s 19 r (Operating) s 12 r (system) s 0 1254 p (support) s 16 r (for) s 15 r (such) s 16 r (synchronization) s 15 r (and) s 16 r (communication) s 15 r (can) s 16 r (improve) s 15 r (performance.) s 22 r (Even) s 15 r (with) s 16 r (this) s 15 r (support,) s 0 1310 p (synchronization) s 13 r (can) s 13 r (still) s 13 r (consume) s 13 r (tens) s 13 r (to) s 14 r (hundreds) s 13 r (of) s 13 r (instructions,) s 13 r (making) s 13 r (these) s 13 r (models) s 13 r (inappropriate) s 14 r (for) s 0 1367 p 174 c (ne) s 15 r (grain) s 15 r (parallel) s 15 r (applications.) s @P38 @sfps 0 1536 p (5.) s 45 r (Scheduling) s 16 r (Support) s 15 r (for) s 15 r (Concurr) s 0 r (ency) s @P33 @sfps 0 1681 p (The) s 19 r (performance) s 19 r (of) s 19 r (applications) s 19 r (that) s 19 r (use) s 19 r (more) s 19 r (virtual) s 19 r (processors) s 20 r (than) s 19 r (physical) s 19 r (processors) s 19 r (can) s 19 r (bene) s 0 r 174 c 0 r 116 c 0 1737 p (from) s 18 r (user) s 18 r (input) s 18 r (to) s 18 r (scheduling) s 18 r (decisions.) s 28 r (Users) s 18 r (may) s 18 r (have) s 18 r (application-speci) s 0 r 174 c 0 r 99 c 18 r (information) s 18 r (about) s 18 r (which) s 0 1793 p (virtual) s 15 r (processors) s 14 r (should) s 15 r (or) s 14 r (should) s 15 r (not) s 14 r (be) s 15 r (running.) s 20 r (The) s 14 r (Mach) s 15 r (scheduler) s 14 r (is) s 15 r (implemented) s 15 r (in) s 14 r (the) s 15 r (operating) s 0 1850 p (system) s 16 r (kernel,) s 15 r (but) s 16 r (allows) s 15 r (users) s 16 r (to) s 16 r (provide) s 15 r (hints) s 16 r (that) s 15 r (in) s 0 r 175 c 0 r (uence) s 16 r (its) s 15 r (decisions.) s 22 r (These) s 15 r (hints) s 16 r (consist) s 15 r (of) s 16 r (local) s 0 1906 p (information) s 18 r (involving) s 17 r (the) s 18 r (thread) s 18 r (that) s 17 r (provides) s 18 r (the) s 18 r (hint) s 17 r (and) s 18 r (possibly) s 18 r (one) s 17 r (other) s 18 r (thread) s 18 r (so) s 18 r (that) s 17 r (users) s 18 r (can) s 0 1963 p (avoid) s 12 r (maintaining) s 13 r (information) s 12 r (on) s 13 r (the) s 12 r (overall) s 13 r (state) s 12 r (of) s 13 r (their) s 12 r (applications.) s 19 r (The) s 13 r (hints) s 12 r (are) s 13 r (based) s 12 r (on) s 13 r (two) s 12 r (pieces) s 0 2019 p (of) s 16 r (scheduling) s 15 r (information) s 16 r (that) s 16 r (may) s 16 r (be) s 15 r (available) s 16 r (when) s 16 r 97 c 15 r (thread) s 16 r (attempts) s 16 r (to) s 15 r (communicate) s 16 r (or) s 16 r (synchronize) s 0 2076 p (with) s 15 r (another) s 15 r (thread) s 15 r (that) s 14 r (is) s 15 r (not) s 15 r (running:) s 20 r (the) s 15 r 174 c 0 r (rst) s 15 r (thread) s 15 r (may) s 15 r (be) s 15 r (unable) s 15 r (to) s 14 r (make) s 15 r (further) s 15 r (progress) s 15 r (until) s 15 r (the) s 0 2132 p (communication) s 15 r (or) s 15 r (synchronization) s 15 r (is) s 15 r (complete,) s 15 r (and) s 15 r (it) s 16 r (may) s 15 r (know) s 15 r (the) s 15 r (identity) s 15 r (of) s 15 r (the) s 15 r (thread) s 15 r (it) s 15 r (is) s 15 r (trying) s 15 r (to) s 0 2189 p (communicate) s 15 r (or) s 15 r (synchronize) s 15 r (with.) s 20 r (For) s 15 r (example,) s 16 r (in) s 15 r 97 c 15 r (synchronization) s 15 r (based) s 15 r (on) s 15 r 97 c 15 r (message) s 15 r (exchange,) s 15 r (the) s 0 2245 p (initiating) s 14 r (thread) s 13 r (must) s 14 r (block) s 14 r (and) s 14 r (the) s 13 r (identity) s 14 r (of) s 14 r (the) s 14 r (thread) s 13 r (that) s 14 r (must) s 14 r (complete) s 14 r (the) s 13 r (synchronization) s 14 r (is) s 14 r (often) s 0 2302 p (known.) s 62 2399 p (The) s 16 r (Mach) s 16 r (scheduler) s 16 r (has) s 16 r (been) s 16 r (enhanced) s 16 r (to) s 17 r (accept) s 16 r (and) s 16 r (use) s 16 r (hints) s 16 r (that) s 16 r (provide) s 16 r (this) s 16 r (information.) s 23 r (There) s 0 2456 p (are) s 15 r (two) s 15 r (classes) s 15 r (of) s 16 r (hints:) s 57 2554 p (1.) s @P38 @sfps 23 r (Discouragement:) s @P33 @sfps 20 r (Hint) s 15 r (that) s 15 r (the) s 15 r (current) s 15 r (thread) s 16 r (should) s 15 r (not) s 15 r (run.) s 20 r (There) s 15 r (are) s 15 r (three) s 15 r (levels:) s 140 2648 p (\(a\)) s 23 r (Mild:) s 20 r (Give) s 16 r (up) s 15 r (the) s 15 r (processor) s 15 r (to) s 15 r (any) s 15 r (other) s 15 r (thread) s 16 r (if) s 15 r (possible.) s 138 2721 p (\(b\)) s 23 r (Strong:) s 20 r (Give) s 15 r (up) s 15 r (the) s 15 r (processor) s 15 r (if) s 16 r (possible) s 15 r (and) s 15 r (temporarily) s 15 r (depress) s 15 r (priority) s -2 r 46 c 962 2843 p 55 c @eop 8 @bop0 @F36 @sf [ 32 32 -3 1 35.353] 6 @dc 8 @bop1 @P33 @sfps 140 42 p (\(c\)) s 23 r (Absolute:) s 20 r (Block) s 16 r (for) s 15 r 97 c 15 r (speci) s 0 r 174 c 0 r (ed) s 15 r (time) s 15 r (period.) s 57 129 p (2.) s @P38 @sfps 23 r (Handoff:) s @P33 @sfps 20 r (Hint) s 15 r (that) s 15 r 97 c 15 r (speci) s 0 r 174 c 0 r 99 c 15 r (thread) s 16 r (should) s 15 r (run) s 15 r (instead) s 15 r (of) s 15 r (the) s 15 r (current) s 15 r (one.) s 0 227 p 65 c 15 r (new) s 15 r (primitive,) s @P38 @sfps 15 r (thr) s 0 r (ead) s 2 r 14 2 ru 14 r (switch) s @P33 @sfps 0 r 44 c 15 r (allows) s 15 r (hints) s 15 r (from) s 16 r (both) s 15 r (classes) s 15 r (to) s 15 r (be) s 15 r (provided) s 15 r (simultaneously) s -2 r 46 c 62 325 p (Discouragement) s 18 r (hints) s 18 r (are) s 18 r (useful) s 18 r (for) s 18 r (optimizing) s 18 r (shared) s 18 r (memory) s 18 r (synchronization) s 18 r (in) s 18 r (applications) s 18 r (that) s 0 381 p (employ) s 22 r (system) s 22 r (concurrency) s -1 r 46 c 40 r (The) s 22 r (identity) s 22 r (of) s 23 r (the) s 22 r (lock) s 22 r (holder) s 22 r (is) s 23 r (not) s 22 r (recorded) s 22 r (by) s 22 r (the) s 23 r (common) s 22 r (`test-) s 0 438 p (and-set') s 20 r (instructions) s 20 r (used) s 21 r (to) s 20 r (implement) s 20 r (shared) s 20 r (memory) s 20 r (locks,) s 22 r (making) s 20 r 97 c 20 r (Handof) s 0 r 102 c 19 r (hint) s 21 r (impossible.) s 35 r 65 c 0 494 p (Discouragement) s 14 r (hint) s 14 r (yields) s 15 r (the) s 14 r (processor) s 14 r (in) s 14 r (the) s 15 r (hope) s 14 r (that) s 14 r (the) s 14 r (holder) s 14 r (of) s 15 r (the) s 14 r (lock) s 14 r (will) s 14 r (run.) s 20 r (This) s 14 r (can) s 15 r (cause) s 0 551 p (problems) s 14 r (if) s 14 r (more) s 14 r (than) s 14 r (one) s 14 r (thread) s 14 r (is) s 14 r (yielding) s 14 r (because) s 14 r (they) s 14 r (may) s 14 r (yield) s 14 r (to) s 14 r (each) s 13 r (other) s 14 r (with) s 14 r (the) s 14 r (result) s 14 r (that) s 14 r (no) s 0 607 p (useful) s 16 r (computation) s 15 r (occurs.) s 22 r (This) s 16 r (can) s 16 r (be) s 15 r (caused) s 16 r (by) s 16 r (the) s 16 r (timesharing) s 15 r (scheduler) s 16 r (giving) s 16 r (the) s 15 r (yielding) s 16 r (threads) s 0 664 p (higher) s 16 r (usage-based) s 16 r (priorities) s 16 r (than) s 17 r (the) s 16 r (thread\(s\)) s 16 r (they) s 16 r (are) s 16 r (waiting) s 16 r (for) s -1 r 46 c 22 r (Absolute) s 16 r (Discouragement) s 17 r (prevents) s 0 720 p (this) s 18 r (by) s 19 r (blocking) s 18 r (the) s 19 r (threads,) s 19 r (but) s 19 r (the) s 18 r (available) s 19 r (time) s 18 r (resolution) s 19 r (based) s 18 r (on) s 19 r (clock) s 18 r (interrupts) s 19 r (is) s 18 r (usually) s 19 r (too) s 0 777 p (coarse) s 18 r (for) s 19 r (medium) s 18 r (to) s 18 r 174 c 0 r (ne) s 18 r (grain) s 19 r (synchronization.) s 29 r (Strong) s 18 r (Discouragement) s 19 r (is) s 18 r 97 c 18 r (compromise) s 19 r (that) s 18 r (avoids) s 0 833 p (the) s 18 r (weaknesses) s 19 r (of) s 18 r (the) s 19 r (other) s 18 r (alternatives.) s 30 r 65 c 18 r (Strong) s 19 r (Discouragement) s 18 r (hint) s 19 r (causes) s 18 r (the) s 18 r (scheduler) s 19 r (to) s 18 r (favor) s 0 889 p (threads) s 13 r (doing) s 13 r (useful) s 12 r (work) s 13 r (over) s 13 r (those) s 13 r (that) s 13 r (are) s 12 r (unable) s 13 r (to) s 13 r (proceed) s 13 r (without) s 13 r (the) s 12 r (overhead) s 13 r (of) s 13 r (actually) s 13 r (blocking) s 0 946 p (the) s 17 r (latter) s 17 r (threads.) s 25 r 65 c 16 r (thread) s 17 r (that) s 17 r (issues) s 17 r 97 c 16 r (Strong) s 17 r (Discouragement) s 17 r (hint) s 17 r (may) s 17 r (explicitly) s 16 r (cancel) s 17 r (it) s 17 r (when) s 17 r (the) s 0 1002 p (desired) s 15 r (event) s 15 r (occurs,) s 15 r (otherwise) s 16 r (it) s 15 r (expires) s 15 r (based) s 15 r (on) s 15 r 97 c 15 r (timeout) s 16 r (supplied) s 15 r (with) s 15 r (the) s 15 r (hint.) s 62 1100 p (Handof) s 0 r 102 c 16 r (Scheduling) s 17 r (`hands) s 16 r (of) s 0 r 102 c 2 r 39 c 17 r (the) s 16 r (processor) s 17 r (directly) s 16 r (to) s 17 r (the) s 17 r (speci) s 0 r 174 c 0 r (ed) s 16 r (thread,) s 17 r (bypassing) s 17 r (the) s 16 r (internal) s 0 1157 p (scheduler) s 17 r (mechanisms.) s 27 r (Handof) s 0 r 102 c 17 r (scheduling) s 17 r (may) s 18 r (designate) s 17 r 97 c 18 r (thread) s 17 r (within) s 17 r (the) s 18 r (same) s 17 r (task) s 18 r (or) s 17 r 97 c 17 r (dif) s 0 r (ferent) s 0 1213 p (task) s 18 r (on) s 18 r (the) s 18 r (same) s 18 r (host) s 18 r (to) s 17 r (run) s 18 r (next.) s 29 r 65 c 18 r (shared) s 18 r (memory) s 17 r (lock) s 18 r (based) s 18 r (on) s 18 r 97 c 18 r (`compare-and-swap') s 18 r (instruction) s 0 1270 p (can) s 17 r (identify) s 17 r (the) s 17 r (tar) s 0 r (get) s 16 r (thread,) s 17 r (or) s 17 r (it) s 17 r (may) s 17 r (be) s 17 r (available) s 17 r (from) s 17 r (the) s 17 r (structure) s 16 r (of) s 17 r (an) s 17 r (application.) s 26 r (For) s 17 r (example) s 0 1326 p 97 c 18 r (buf) s 0 r (fer) s 17 r (may) s 18 r (be) s 17 r (empty) s 18 r (and) s 18 r (only) s 18 r (one) s 17 r (thread) s 18 r 174 c 0 r (lls) s 18 r (it.) s 28 r (One) s 18 r (promising) s 18 r (use) s 17 r (of) s 18 r (this) s 18 r (technique) s 18 r (is) s 18 r (to) s 17 r (address) s 0 1383 p (the) s 18 r (problem) s 18 r (of) s 18 r (`priority) s 19 r (inversion') s 18 r (where) s 18 r 97 c 18 r (low) s 18 r (priority) s 18 r (thread) s 18 r (holds) s 18 r 97 c 19 r (lock) s 18 r (needed) s 18 r (by) s 18 r 97 c 18 r (high) s 18 r (priority) s 0 1439 p (thread.) s 25 r (The) s 17 r (high) s 17 r (priority) s 17 r (thread) s 17 r (can) s 17 r (detect) s 17 r (this) s 16 r (situation) s 17 r (and) s 17 r (hand) s 17 r (of) s 0 r 102 c 16 r (the) s 17 r (processor) s 17 r (to) s 17 r (the) s 16 r (low) s 17 r (priority) s 0 1496 p (thread) s 17 r (for) s 18 r (the) s 17 r (purposes) s 17 r (of) s 17 r (dropping) s 18 r (the) s 17 r (lock.) s 26 r (When) s 18 r (used) s 17 r (from) s 17 r (outside) s 17 r (the) s 18 r (kernel,) s 17 r (Handof) s 0 r 102 c 17 r (Scheduling) s 0 1552 p (causes) s 20 r (the) s 21 r (speci) s 0 r 174 c 0 r (ed) s 20 r (thread) s 20 r (to) s 20 r (be) s 21 r (removed) s 20 r (from) s 20 r (its) s 21 r (run) s 20 r (queue) s 20 r (and) s 21 r (run,) s 21 r (avoiding) s 20 r 97 c 21 r (run) s 20 r (queue) s 20 r (search.) s 0 1608 p (Handof) s 0 r 102 c 19 r (Scheduling) s 20 r (is) s 20 r (also) s 20 r (used) s 21 r (extensively) s 20 r (by) s 20 r (Mach') s -2 r 115 c 19 r (message) s 20 r (passing) s 20 r (subsystem) s 21 r (inside) s 20 r (the) s 20 r (kernel) s 0 1665 p (to) s 18 r (immediately) s 18 r (run) s 19 r (the) s 18 r (recipient) s 18 r (of) s 18 r 97 c 18 r (message.) s 30 r (Uses) s 18 r (inside) s 18 r (the) s 18 r (kernel) s 19 r (gain) s 18 r (additional) s 18 r (performance) s 18 r (by) s 0 1721 p (avoiding) s 15 r (the) s 15 r (run) s 15 r (queue) s 16 r (entirely) s -2 r 46 c @P38 @sfps 0 1882 p (5.1.) s 45 r (Performance) s @P33 @sfps 0 2011 p (This) s 18 r (section) s 19 r (presents) s 18 r (results) s 18 r (from) s 18 r (two) s 19 r (experiments) s 18 r (that) s 18 r (demonstrate) s 18 r (the) s 19 r (performance) s 18 r (bene) s 0 r 174 c 0 r (ts) s 18 r (of) s 19 r (using) s 0 2067 p (scheduling) s 17 r (hints.) s 26 r (These) s 17 r (experiments) s 17 r (were) s 17 r (performed) s 17 r (on) s 16 r 97 c 17 r (Encore) s 17 r (Multimax) s 17 r (with) s 17 r (NS32332) s 17 r (processors,) s 0 2124 p (which) s 21 r (have) s 20 r 97 c 21 r (speed) s 20 r (of) s 21 r (approximately) s 21 r 50 c 20 r (MIPS.) s 21 r (The) s 20 r 174 c 0 r (rst) s 21 r (experiment) s 21 r (investigates) s 20 r (the) s 21 r (use) s 20 r (of) s 21 r (hints) s 21 r (for) s 0 2180 p (synchronizing) s 16 r (with) s 17 r 97 c 16 r (thread) s 17 r (that) s 16 r (is) s 17 r (not) s 16 r (running.) s 24 r (It) s 16 r (uses) s 17 r 97 c 16 r (multithreaded) s 17 r (test) s 16 r (program) s 16 r (than) s 17 r (synchronizes) s 0 2237 p (with) s 22 r (randomly) s 22 r (selected) s 22 r (threads.) s 42 r 65 c 22 r (shared) s 22 r (variable) s 22 r (contains) s 22 r 97 c 22 r (thread) s 23 r (number) s -2 r 46 c 40 r (That) s 22 r (thread) s 23 r (replaces) s 0 2293 p (it) s 20 r (with) s 21 r (some) s 20 r (other) s 20 r (randomly) s 21 r (chosen) s 20 r (thread) s 20 r (number) s 0 r 44 c 20 r (which) s 21 r (replaces) s 20 r (it) s 20 r (with) s 21 r (another) s 20 r (randomly) s 20 r (chosen) s 0 2350 p (thread) s 17 r (number) s -1 r 44 c 16 r (and) s 17 r (so) s 17 r (on.) s 25 r (This) s 16 r (program) s 17 r (is) s 17 r (restricted) s 17 r (to) s 16 r (run) s 17 r (on) s 17 r 97 c 17 r (single) s 16 r (processor) s 0 r 44 c 16 r (so) s 16 r (that) s 17 r (it) s 17 r (repeatedly) s 0 2406 p (synchronizes) s 14 r (with) s 14 r 97 c 15 r (thread) s 14 r (that) s 14 r (isn') s 0 r 116 c 13 r (executing.) s 20 r (The) s 14 r (threads) s 15 r (that) s 14 r (are) s 14 r (not) s 14 r (the) s 15 r (tar) s 0 r (get) s 13 r (of) s 14 r (the) s 14 r (synchronization) s 0 2463 p (can) s 15 r (use) s 15 r 97 c 15 r (scheduling) s 16 r (hint) s 15 r (to) s 15 r (encourage) s 15 r (the) s 15 r (operating) s 15 r (system) s 16 r (to) s 15 r (run) s 15 r (the) s 15 r (tar) s 0 r (get.) s 62 2560 p 84 c -2 r (able) s 18 r 50 c 19 r (shows) s 19 r (the) s 19 r (elapsed) s 19 r (time) s 19 r (per) s 19 r (synchronization) s 19 r (in) s 19 r (microseconds) s 19 r (for) s 19 r (dif) s 0 r (ferent) s 19 r (scheduling) s 19 r (hints) s 0 2617 p (and) s 15 r (dif) s 0 r (ferent) s 15 r (numbers) s 16 r (of) s 15 r (threads) s 15 r (as) s 16 r (mean) s @F36 @sf 15 r 6 c @P33 @sfps 16 r (standard) s 15 r (deviation.) s 21 r (The) s 16 r (Mild) s 15 r (Discouragement) s 16 r (hint) s 15 r (exhibits) s 0 2673 p (two) s 14 r (dif) s 0 r (ferent) s 14 r (behaviors.) s 20 r (If) s 14 r (all) s 14 r (of) s 15 r (the) s 14 r (threads) s 14 r (are) s 15 r (at) s 14 r (the) s 14 r (same) s 15 r (usage-based) s 14 r (priority) s -2 r 44 c 13 r (then) s 15 r (the) s 14 r (`Mild-ok') s 14 r (line) s 0 2730 p (applies) s 17 r (and) s 17 r (the) s 18 r (synchronization) s 17 r (is) s 17 r (accomplished) s 17 r (in) s 18 r 97 c 17 r (millisecond) s 17 r (or) s 17 r (less.) s 27 r (If) s 17 r (some) s 17 r (of) s 17 r (the) s 18 r (threads) s 17 r (are) s 17 r (at) s 962 2843 p 56 c @eop 9 @bop0 @F35 @sf [ 32 29 -1 9 27.388] 22 @dc 9 @bop1 287 43 p 1358 2 ru 286 100 p 2 56 ru @P33 @sfps 312 83 p (Threads) s 505 100 p 2 56 ru 8 r 2 56 ru 614 83 p 51 c 735 100 p 2 56 ru 847 83 p 52 c 979 100 p 2 56 ru 1079 83 p 53 c 1201 100 p 2 56 ru 1301 83 p 54 c 1422 100 p 2 56 ru 1523 83 p 55 c 1644 100 p 2 56 ru 287 101 p 1358 2 ru 287 111 p 1358 2 ru 286 168 p 2 56 ru 312 151 p (Mild-ok) s 505 168 p 2 56 ru 8 r 2 56 ru 551 151 p (570) s @F36 @sf 0 r 6 c @P33 @sfps 0 r (67) s 735 168 p 2 56 ru 772 151 p (723) s @F36 @sf 0 r 6 c @P33 @sfps 0 r (125) s 979 168 p 2 56 ru 1016 151 p (837) s @F36 @sf 0 r 6 c @P33 @sfps 0 r (26) s 1201 168 p 2 56 ru 1227 151 p (920) s @F36 @sf 0 r 6 c @P33 @sfps 0 r (103) s 1422 168 p 2 56 ru 1449 151 p 49 c -1 r (132) s @F36 @sf 0 r 6 c @P33 @sfps 0 r (48) s 1644 168 p 2 56 ru 287 169 p 1358 2 ru 286 226 p 2 56 ru 312 209 p (Mild-bad) s 505 226 p 2 56 ru 8 r 2 56 ru 539 209 p (1052) s @F36 @sf 0 r 6 c @P33 @sfps 0 r (36) s 735 226 p 2 56 ru 761 209 p (1794) s @F36 @sf 0 r 6 c @P33 @sfps 0 r (512) s 979 226 p 2 56 ru 1018 209 p (No) s 15 r (data) s 1201 226 p 2 56 ru 1231 209 p 62 c 16 r (189ms) s 1422 226 p 2 56 ru 1453 209 p 62 c 15 r (195ms) s 1644 226 p 2 56 ru 287 227 p 1358 2 ru 286 284 p 2 56 ru 312 267 p (Strong) s 505 284 p 2 56 ru 8 r 2 56 ru 551 267 p (708) s @F36 @sf 0 r 6 c @P33 @sfps 0 r (46) s 735 284 p 2 56 ru 772 267 p (1029) s @F36 @sf 0 r 6 c @P33 @sfps 0 r (36) s 979 284 p 2 56 ru 1005 267 p (1276) s @F36 @sf 0 r 6 c @P33 @sfps 0 r (45) s 1201 284 p 2 56 ru 1227 267 p (1587) s @F36 @sf 0 r 6 c @P33 @sfps 0 r (24) s 1422 284 p 2 56 ru 1448 267 p (1867) s @F36 @sf 0 r 6 c @P33 @sfps 0 r (37) s 1644 284 p 2 56 ru 287 286 p 1358 2 ru 286 342 p 2 56 ru 312 325 p (Handof) s 0 r 102 c 505 342 p 2 56 ru 8 r 2 56 ru 551 325 p (402) s @F36 @sf 0 r 6 c @P33 @sfps 0 r (12) s 735 342 p 2 56 ru 795 325 p (406) s @F36 @sf 0 r 6 c @P33 @sfps 0 r 57 c 979 342 p 2 56 ru 1029 325 p (41) s -1 r 49 c @F36 @sf 0 r 6 c @P33 @sfps 0 r 52 c 1201 342 p 2 56 ru 1249 325 p (417) s @F36 @sf 0 r 6 c @P33 @sfps 0 r 52 c 1422 342 p 2 56 ru 1471 325 p (429) s @F36 @sf 0 r 6 c @P33 @sfps 0 r 51 c 1644 342 p 2 56 ru 287 344 p 1358 2 ru 551 420 p 84 c -2 r (able) s 14 r (2:) s 20 r (Synchronization) s 15 r (Experiment) s 15 r (Results) s 0 554 p (dif) s 0 r (ferent) s 15 r (priorities,) s 17 r (the) s 16 r (`Mild-bad') s 17 r (line) s 16 r (applies,) s 16 r (and) s 17 r (the) s 16 r (synchronization) s 16 r (can) s 16 r (take) s 17 r (much) s 16 r (longer) s -1 r 46 c 22 r (Multiple) s 0 611 p (runs) s 19 r (of) s 20 r (the) s 19 r (program) s 20 r (with) s 19 r (this) s 20 r (hint) s 19 r (exhibit) s 20 r (both) s 19 r (behaviors) s 20 r (unpredictably) s -2 r 46 c 32 r (The) s 19 r (only) s 20 r (exception) s 19 r (is) s 20 r (the) s 19 r 53 c 0 667 p (threads) s 18 r (case) s 18 r (in) s 17 r (which) s 18 r (no) s 18 r (`Mild-bad') s 18 r (behavior) s 18 r (was) s 17 r (observed.) s 29 r 46 c 28 r (This) s 18 r (is) s 17 r (probably) s 18 r (due) s 18 r (to) s 18 r (the) s 18 r (number) s 17 r (of) s 0 724 p (threads) s 16 r (being) s 16 r 97 c 16 r (divisor) s 16 r (of) s 16 r (the) s 16 r (10Hz) s 17 r (clock) s 16 r (frequency) s 16 r (that) s 16 r (drives) s 16 r (the) s 16 r (scheduler) s -1 r 44 c 15 r (so) s 16 r (that) s 17 r (stable) s 16 r (behavior) s 16 r (is) s 0 780 p (more) s 15 r (likely) s -2 r 46 c 19 r (The) s 14 r (times) s 15 r (for) s 15 r (the) s 14 r 54 c 15 r (and) s 15 r 55 c 14 r (thread) s 15 r (cases) s 15 r (of) s 14 r (`Mild-bad') s 15 r (ranged) s 15 r (from) s 14 r (the) s 15 r (approximately) s 14 r (200ms) s 0 837 p (shown) s 17 r (in) s 17 r (the) s 17 r (table) s 16 r (to) s 17 r (over) s 17 r 97 c 17 r (second.) s 25 r (Standard) s 17 r (deviations) s 17 r (are) s 17 r (not) s 17 r (meaningful) s 17 r (for) s 17 r (this) s 16 r (data) s 17 r (because) s 17 r (it) s 17 r (is) s 0 893 p (skewed) s 15 r (and) s 15 r (contains) s 16 r 97 c 15 r (small) s 15 r (number) s 15 r (of) s 16 r (data) s 15 r (points.) s 20 r (Absolute) s 16 r (Discouragement) s 15 r (was) s 15 r (not) s 15 r (tested) s 16 r (because) s 15 r (it) s 0 950 p (would) s 16 r (result) s 17 r (in) s 16 r (times) s 17 r (on) s 16 r (the) s 17 r (order) s 16 r (of) s 16 r (100ms) s 17 r (per) s 16 r (synchronization) s 17 r (given) s 16 r (the) s 17 r (clock) s 16 r (interrupt) s 16 r (frequency) s 17 r (of) s 0 1006 p (10Hz.) s 62 1105 p (These) s 16 r (results) s 15 r (demonstrate) s 15 r (the) s 15 r (bene) s 0 r 174 c 0 r (ts) s 16 r (of) s 15 r (scheduling) s 15 r (hints.) s 21 r (Running) s 15 r (this) s 16 r (program) s 15 r (with) s 15 r (no) s 15 r (scheduling) s 0 1161 p (hints) s 17 r (yields) s 17 r (times) s 17 r (of) s 17 r (half) s 17 r 97 c 16 r (second) s 17 r (to) s 17 r 97 c 17 r (second) s 17 r (per) s 17 r (synchronization,) s 17 r (demonstrating) s 17 r (the) s 17 r (potential) s 17 r (perfor-) s 0 1218 p (mance) s 13 r (penalties) s 12 r (for) s 13 r (ignoring) s 12 r (this) s 13 r (problem.) s 19 r (If) s 13 r (the) s 13 r (threads) s 12 r (are) s 13 r (at) s 12 r (the) s 13 r (same) s 13 r (priority) s 12 r (then) s 13 r (context) s 13 r (switching) s 12 r (is) s 0 1274 p (ef) s 0 r (fective,) s 14 r (but) s 15 r (poor) s 15 r (results) s 15 r (occur) s 15 r (if) s 15 r (this) s 16 r (is) s 15 r (not) s 15 r (the) s 15 r (case) s 15 r (due) s 15 r (to) s 15 r (priority) s 15 r (inversions.) s 20 r (Strong) s 15 r (Discouragement) s 0 1330 p (has) s 16 r (predictable) s 16 r (performance,) s 17 r (but) s 16 r (is) s 16 r (slower) s 16 r (than) s 16 r (the) s 17 r (best) s 16 r (cases) s 16 r (of) s 16 r (Mild) s 16 r (Discouragement) s 17 r (due) s 16 r (to) s 16 r (the) s 16 r (costs) s 0 1387 p (of) s 21 r (the) s 20 r (timeouts) s 21 r (associated) s 20 r (with) s 21 r (the) s 21 r (priority) s 20 r (depressions.) s 37 r (These) s 20 r (costs) s 21 r (also) s 21 r (account) s 20 r (for) s 21 r (the) s 20 r (increasing) s 0 1443 p (dif) s 0 r (ference) s 16 r (between) s 17 r (the) s 16 r (`Strong') s 17 r (and) s 17 r (`Mild-ok') s 16 r (as) s 17 r (the) s 17 r (number) s 17 r (of) s 16 r (threads) s 17 r (increases.) s 25 r (Handof) s 0 r 102 c 16 r (Scheduling) s 0 1500 p (produces) s 13 r (the) s 14 r (best) s 13 r (performance) s 13 r (and) s 13 r (is) s 14 r (signi) s 0 r 174 c 0 r (cantly) s 13 r (faster) s 13 r (than) s 13 r (sending) s 14 r 97 c 13 r (message) s 13 r (because) s 14 r (no) s 13 r (time) s 13 r (is) s 13 r (spent) s 0 1556 p (formatting) s 20 r (and) s 19 r (transporting) s 20 r (the) s 20 r (message,) s 21 r (or) s 20 r (blocking) s 19 r (to) s 20 r (wait) s 20 r (for) s 20 r (it.) s 34 r (These) s 19 r (results) s 20 r (suggest) s 20 r (that) s 20 r (ef) s 0 r (fec-) s 0 1613 p (tive) s 14 r (support) s 14 r (of) s 14 r (system) s 13 r (concurrent) s 14 r (applications) s 14 r (requires) s 14 r (Strong) s 14 r (Discouragement) s 14 r (support,) s 14 r (and) s 14 r (that) s 13 r (Handof) s 0 r 102 c 0 1669 p (Scheduling) s 17 r (is) s 17 r (an) s 17 r (ef) s 0 r (fective) s 16 r (optimization) s 17 r (if) s 17 r (the) s 17 r (information) s 17 r (it) s 16 r (requires) s 17 r (is) s 17 r (available.) s 26 r (These) s 17 r (are) s 17 r (worst) s 17 r (case) s 0 1726 p (results,) s 15 r (but) s 15 r (do) s 15 r (indicate) s 16 r (the) s 15 r (relative) s 15 r (performance) s 15 r (of) s 15 r (the) s 15 r (hints.) s 62 1824 p (The) s 15 r (second) s 14 r (experiment) s 15 r (concerns) s 14 r (the) s 14 r (performance) s 15 r (bene) s 0 r 174 c 0 r (ts) s 14 r (of) s 15 r (using) s 14 r (Handof) s 0 r 102 c 14 r (Scheduling) s 14 r (in) s 15 r (the) s 14 r (kernel.) s 0 1880 p (It) s 11 r (uses) s 12 r 97 c 11 r (message) s 12 r (passing) s 11 r (exerciser) s 12 r (to) s 11 r (measure) s 12 r (the) s 11 r (performance) s 11 r (impact) s 12 r (of) s 11 r (Handof) s 0 r 102 c 11 r (Scheduling) s 11 r (in) s 12 r (the) s 11 r (Mach) s 0 1936 p (IPC) s 14 r (system.) s 20 r (The) s 13 r (experiment) s 14 r (involves) s 14 r (exchanging) s 14 r (messages) s 14 r (between) s 14 r (two) s 13 r (threads) s 14 r (in) s 14 r 97 c 14 r (task) s 14 r (on) s 14 r (both) s 14 r (single) s 0 1993 p (and) s 16 r (multiple) s 17 r (processor) s 16 r (con) s 0 r 174 c 0 r (gurations.) s 25 r (The) s 16 r (key) s 17 r (dif) s 0 r (ference) s 15 r (between) s 17 r (the) s 16 r (uniprocessor) s 17 r (and) s 16 r (multiprocessor) s 0 2049 p (experiments) s 17 r (is) s 18 r (the) s 17 r (availability) s 18 r (of) s 17 r (an) s 18 r (idle) s 17 r (processor) s 18 r (to) s 17 r (run) s 18 r (the) s 17 r (recipient) s 18 r (thread.) s 27 r (Hence) s 17 r (the) s 18 r (uniprocessor) s 0 2106 p (results) s 17 r (are) s 17 r (also) s 17 r (applicable) s 17 r (to) s 17 r (multiprocessors) s 16 r (when) s 17 r (no) s 17 r (idle) s 17 r (processors) s 17 r (are) s 17 r (available.) s 26 r 84 c -3 r (able) s 16 r 51 c 17 r (shows) s 17 r (the) s 0 2162 p (results) s 19 r (in) s @F35 @sf 18 r 22 c @P33 @sfps 0 r (sec) s 19 r (of) s 18 r (elapsed) s 19 r (time) s 18 r (per) s 19 r (exchange) s 18 r (as) s 19 r (mean) s @F36 @sf 18 r 6 c @P33 @sfps 19 r (standard) s 18 r (deviation.) s 31 r (The) s 18 r (time) s 19 r (dif) s 0 r (ferences) s 18 r (are) s 0 2219 p (statistically) s 14 r (signi) s 0 r 174 c 0 r (cant) s 13 r (only) s 14 r (for) s 14 r (the) s 13 r (RPC) s 14 r (case) s 14 r (without) s 13 r (idle) s 14 r (processors.) s 20 r (The) s 13 r (RPC) s 14 r (case) s 14 r (with) s 13 r (idle) s 14 r (processors) s 0 2275 p (bene) s 174 c (ts) s 11 r (from) s 12 r 97 c 11 r (handof) s 0 r 102 c 11 r (in) s 11 r (the) s 12 r (dispatching) s 11 r (code) s 11 r (discussed) s 12 r (in) s 11 r (Section) s 12 r (3.1.) s 18 r (This) s 12 r (handof) s 0 r 102 c 10 r (was) s 12 r (not) s 11 r (disabled) s 12 r (for) s 0 2332 p (these) s 13 r (experiments) s 14 r (because) s 13 r (it) s 13 r (is) s 14 r (not) s 13 r (speci) s 0 r 174 c 0 r 99 c 13 r (to) s 14 r (the) s 13 r (IPC) s 13 r (system,) s 14 r (and) s 13 r (because) s 14 r (disabling) s 13 r (it) s 13 r (requires) s 14 r (scheduler) s 0 2388 p (modi) s 174 c (cations) s 17 r (that) s 17 r (impact) s 17 r (the) s 17 r (critical) s 17 r (context) s 17 r (switch) s 17 r (path.) s 26 r (The) s 17 r (performance) s 17 r (gain) s 17 r (from) s 17 r (this) s 17 r (handof) s 0 r 102 c 16 r (can) s 0 2445 p (be) s 19 r (estimated) s 20 r (from) s 19 r (the) s 20 r (performance) s 19 r (gain) s 20 r (in) s 19 r (the) s 19 r (`no) s 20 r (idle) s 19 r (processors') s 20 r (case) s 19 r (of) s 20 r (about) s 19 r (65) s @F35 @sf 0 r 22 c @P33 @sfps 0 r (sec.) s 33 r (Individual) s 0 2501 p (messages) s 14 r (do) s 14 r (not) s 13 r (gain) s 14 r (performance) s 14 r (from) s 14 r (Handof) s 0 r 102 c 13 r (Scheduling) s 13 r (for) s 14 r (two) s 14 r (reasons:) s 19 r (in) s 14 r (its) s 14 r (absence) s 14 r 97 c 13 r (sender) s 14 r (can) s 0 2557 p (queue) s 13 r (multiple) s 14 r (messages) s 13 r (before) s 13 r (context) s 14 r (switching) s 13 r (to) s 13 r (the) s 14 r (receiver) s -1 r 44 c 13 r (and) s 13 r (on) s 13 r 97 c 14 r (multiprocessor) s 13 r (the) s 13 r (sender) s 14 r (and) s 0 2614 p (receiver) s 15 r (can) s 15 r (run) s 15 r (in) s 16 r (parallel) s 15 r (with) s 15 r (complete) s 15 r (overlap.) s 62 2722 p (Based) s 13 r (on) s 12 r (these) s 13 r (results,) s 13 r (Mach) s 12 r (is) s 13 r (con) s 0 r 174 c 0 r (gured) s 12 r (to) s 13 r (use) s 12 r (Handof) s 0 r 102 c 12 r (Scheduling) s 12 r (for) s 13 r (RPC) s 12 r (when) s 13 r (no) s 12 r (idle) s 12 r (processor) s 962 2843 p 57 c @eop 10 @bop0 10 @bop1 400 43 p 1132 2 ru 399 100 p 2 56 ru @P33 @sfps 425 83 p (Messages) s 729 100 p 2 56 ru 8 r 2 56 ru 905 83 p (RPC) s 1156 100 p 2 56 ru 1288 83 p (1-way) s 1531 100 p 2 56 ru 400 101 p 1132 2 ru 399 158 p 2 56 ru 425 141 p (Idle) s 15 r (processor?) s 729 158 p 2 56 ru 8 r 2 56 ru 820 141 p (No) s 957 158 p 2 56 ru 1024 141 p 89 c -3 r (es) s 1156 158 p 2 56 ru 1228 141 p (No) s 1355 158 p 2 56 ru 1411 141 p 89 c -4 r (es) s 1531 158 p 2 56 ru 400 159 p 1132 2 ru 400 169 p 1132 2 ru 399 226 p 2 56 ru 425 209 p (No) s 15 r (Handof) s 0 r 102 c 729 226 p 2 56 ru 8 r 2 56 ru 763 209 p (1914) s @F36 @sf 0 r 6 c @P33 @sfps 0 r 49 c -1 r 49 c 957 226 p 2 56 ru 983 209 p (1630) s @F36 @sf 0 r 6 c @P33 @sfps 0 r 54 c 1156 226 p 2 56 ru 1193 209 p (857) s @F36 @sf 0 r 6 c @P33 @sfps 0 r 53 c 1355 226 p 2 56 ru 1381 209 p (432) s @F36 @sf 0 r 6 c @P33 @sfps 0 r 51 c 1531 226 p 2 56 ru 400 227 p 1132 2 ru 399 284 p 2 56 ru 425 267 p (Handof) s 0 r 102 c 729 284 p 2 56 ru 8 r 2 56 ru 774 267 p (1848) s @F36 @sf 0 r 6 c @P33 @sfps 0 r 56 c 957 284 p 2 56 ru 983 267 p (1628) s @F36 @sf 0 r 6 c @P33 @sfps 0 r 55 c 1156 284 p 2 56 ru 1182 267 p (861) s @F36 @sf 0 r 6 c @P33 @sfps 0 r (10) s 1355 284 p 2 56 ru 1381 267 p (429) s @F36 @sf 0 r 6 c @P33 @sfps 0 r 52 c 1531 284 p 2 56 ru 400 286 p 1132 2 ru 574 362 p 84 c -2 r (able) s 14 r (3:) s 20 r (Message) s 15 r (Passing) s 15 r (Handof) s 0 r 102 c 15 r (Results) s 0 496 p (is) s 16 r (available.) s 22 r (Current) s 16 r (Mach) s 15 r (kernels) s 16 r (can) s 16 r (only) s 16 r (handof) s 0 r 102 c 15 r (once) s 15 r (per) s 16 r (RPC) s 16 r (because) s 16 r (the) s 16 r (send) s 15 r (half) s 16 r (of) s 16 r (the) s 16 r (RPC) s 15 r (is) s 0 553 p (implemented) s 18 r (separately) s 18 r (from) s 17 r (the) s 18 r (receive.) s 28 r (This) s 18 r (results) s 18 r (in) s 18 r (the) s 18 r (sender) s 18 r (handing) s 17 r (of) s 0 r 102 c 17 r (to) s 18 r (the) s 18 r (receiver) s 18 r (before) s 0 609 p (the) s 14 r (sender) s 15 r (is) s 14 r (queued) s 14 r (for) s 15 r (the) s 14 r (reply) s -2 r 46 c 19 r (When) s 15 r (the) s 14 r (reply) s 14 r (comes) s 15 r (back,no) s 14 r (thread) s 14 r (is) s 15 r (queued) s 14 r (and) s 15 r (no) s 14 r (handof) s 0 r 102 c 13 r (takes) s 0 666 p (place.) s 28 r (The) s 18 r (Mach) s 18 r (IPC) s 17 r (system) s 18 r (is) s 18 r (being) s 18 r (redesigned) s 17 r (to) s 18 r (incorporate) s 18 r 97 c 18 r (bidirectional) s 17 r (message) s 18 r (primitive) s 18 r (that) s 0 722 p (can) s 15 r (handof) s 0 r 102 c 13 r (in) s 15 r (both) s 14 r (directions.) s 20 r (Similar) s 15 r (functionality) s 14 r (exists) s 15 r (in) s 15 r (other) s 14 r (systems,) s 15 r (such) s 14 r (as) s 15 r (the) s 14 r 84 c -2 r (opaz) s 14 r (operating) s 0 779 p (system) s 15 r (developed) s 15 r (at) s 15 r (DEC) s 16 r (SRC) s 15 r (for) s 15 r (the) s 15 r (Fire) s 0 r 175 c 0 r (y[) s 0 r 56 c 0 r (].) s 62 877 p (An) s 17 r (alternative) s 16 r (approach) s 17 r (to) s 16 r (this) s 17 r (area) s 16 r (is) s 17 r (to) s 16 r (combine) s 17 r (the) s 16 r (scheduling) s 17 r (hints) s 16 r (into) s 16 r (higher) s 17 r (level) s 16 r (kernel) s 17 r (syn-) s 0 933 p (chronization) s 15 r (primitives,) s 16 r (such) s 15 r (as) s 15 r (semaphores) s 16 r (or) s 15 r (condition) s 15 r (variables.) s 21 r (The) s 15 r (advantages) s 16 r (of) s 15 r (this) s 15 r (approach) s 16 r (are) s 0 989 p (that) s 14 r 97 c 14 r (cleaner) s 14 r (interface) s 14 r (can) s 14 r (be) s 14 r (provided) s 14 r (by) s 14 r (hiding) s 14 r (more) s 14 r (scheduler) s 14 r (details,) s 14 r (and) s 14 r (higher) s 14 r (level) s 14 r (primitives) s 14 r (can) s 0 1046 p (simplify) s 17 r (the) s 16 r (implementation) s 17 r (of) s 17 r 97 c 16 r (library) s 17 r (or) s 17 r (language) s 16 r (runtime) s 17 r (that) s 17 r (uses) s 16 r (them.) s 25 r (The) s 17 r (corresponding) s 16 r (disad-) s 0 1102 p (vantages) s 19 r (are) s 18 r (that) s 19 r (languages) s 18 r (and) s 19 r (libraries) s 18 r (must) s 19 r (use) s 18 r (these) s 19 r (primitives) s 18 r (to) s 19 r (in) s 0 r 175 c 0 r (uence) s 18 r (the) s 19 r (scheduler) s -1 r 44 c 18 r (and) s 19 r (the) s 0 1159 p (primitives) s 13 r (may) s 13 r (be) s 14 r (specialized) s 13 r (towards) s 13 r (some) s 13 r (languages) s 13 r (or) s 13 r (classes) s 14 r (of) s 13 r (applications.) s 19 r (This) s 14 r (can) s 13 r (impact) s 13 r (perfor-) s 0 1215 p (mance) s 15 r (if) s 14 r (the) s 15 r (primitives) s 14 r (are) s 15 r (not) s 14 r 97 c 15 r (good) s 14 r (match) s 15 r (to) s 14 r (the) s 15 r (programming) s 14 r (language) s 15 r (or) s 14 r (model.) s 20 r (The) s 15 r 84 c -3 r (opaz) s 14 r (system) s 0 1272 p (uses) s 17 r (this) s 16 r (approach,) s 18 r (but) s 16 r (specialization) s 17 r (is) s 17 r (not) s 16 r (an) s 17 r (issue) s 17 r (in) s 17 r (that) s 16 r (environment) s 17 r (because) s 17 r (most) s 17 r (programming) s 16 r (is) s 0 1328 p (done) s 15 r (in) s 15 r (Modula-2+[) s 0 r 56 c 0 r (].) s @P38 @sfps 0 1497 p (6.) s 45 r (Pr) s 0 r (ocessor) s 15 r (Allocation) s @P37 @sfps 0 1642 p (Gang) s 13 r (scheduling) s @P33 @sfps 13 r (is) s 13 r (the) s 13 r (common) s 13 r (name) s 13 r (for) s 13 r 97 c 13 r (scheduling) s 13 r (discipline) s 13 r (that) s 13 r (guarantees) s 13 r (to) s 13 r (schedule) s 13 r (components) s 0 1699 p (of) s 21 r (an) s 21 r (application) s 20 r (simultaneously) s -2 r 44 c 22 r (and) s 20 r (is) s 21 r (the) s 21 r (primary) s 21 r (use) s 20 r (for) s 21 r (processor) s 21 r (allocation) s 21 r (in) s 20 r 97 c 21 r (multiprocessor) s 0 1755 p (operating) s 16 r (system.) s 24 r (Gang) s 17 r (scheduling) s 16 r (is) s 17 r (required) s 16 r (by) s 17 r 174 c 0 r (ne) s 16 r (grain) s 16 r (parallel) s 17 r (applications) s 16 r (whose) s 17 r (performance) s 16 r (is) s 0 1812 p (severely) s 15 r (impacted) s 15 r (when) s 15 r (any) s 15 r (part) s 15 r (of) s 15 r (the) s 15 r (application) s 14 r (is) s 15 r (not) s 15 r (running,) s 15 r (but) s 15 r (is) s 15 r (also) s 15 r (applicable) s 15 r (to) s 15 r (other) s 15 r (classes) s 0 1868 p (of) s 18 r (parallel) s 18 r (programs.) s 29 r (The) s 18 r (need) s 18 r (for) s 18 r (gang) s 18 r (scheduling) s 18 r (has) s 18 r (been) s 18 r (widely) s 18 r (recognized,) s 18 r (and) s 18 r (implementations) s 0 1924 p (exist) s 18 r (on) s 17 r 97 c 18 r (variety) s 17 r (of) s 18 r (multiprocessors.) s 28 r (This) s 17 r (section) s 18 r (describes) s 17 r (the) s 18 r (design) s 18 r (and) s 17 r (implementation) s 18 r (of) s 17 r (Mach') s -1 r 115 c 0 1981 p (processor) s 15 r (allocation) s 15 r (facility) s -2 r 46 c @P38 @sfps 0 2145 p (6.1.) s 45 r (Design) s @P33 @sfps 0 2274 p (Flexibility) s 15 r (is) s 14 r (the) s 15 r (driving) s 15 r (factor) s 14 r (in) s 15 r (the) s 15 r (design) s 14 r (of) s 15 r (Mach') s -2 r 115 c 14 r (processor) s 15 r (allocation) s 14 r (facility) s 15 r (since) s 15 r (Mach) s 14 r (supports) s 0 2330 p 97 c 18 r (multitude) s 19 r (of) s 18 r (applications,) s 19 r (languages,) s 19 r (and) s 19 r (programming) s 18 r (models) s 18 r (on) s 19 r 97 c 18 r (variety) s 18 r (of) s 19 r (multiprocessor) s 18 r (archi-) s 0 2386 p (tectures.) s 23 r (This) s 16 r 175 c 0 r (exibility) s 16 r (has) s 17 r (several) s 16 r (aspects.) s 23 r (It) s 16 r (should) s 16 r (be) s 16 r (possible) s 16 r (to) s 17 r (allocate) s 16 r (processors) s 16 r (to) s 16 r (applications) s 0 2443 p (written) s 15 r (in) s 15 r (dif) s 0 r (ferent) s 15 r (languages) s 15 r (with) s 15 r (dif) s 0 r (ferent) s 14 r (programming) s 16 r (models.) s 20 r (Binding) s 15 r (threads) s 15 r (to) s 16 r (individual) s 15 r (proces-) s 0 2499 p (sors) s 19 r (is) s 19 r (not) s 19 r (suf) s 0 r 174 c 0 r (cient) s 18 r (because) s 18 r (applications) s 19 r (that) s 19 r (use) s 19 r (system) s 19 r (concurrency) s 19 r (need) s 18 r (to) s 19 r (bind) s 19 r 97 c 19 r (pool) s 19 r (of) s 19 r (threads) s 0 2556 p (to) s 16 r 97 c 17 r (pool) s 16 r (of) s 17 r (processors.) s 24 r (This) s 16 r (improves) s 17 r (their) s 16 r (performance) s 16 r (by) s 17 r (allowing) s 16 r (any) s 17 r (thread) s 16 r (to) s 17 r (run) s 16 r (on) s 16 r 97 c 17 r (processor) s 0 2612 p (vacated) s 17 r (by) s 16 r 97 c 17 r (blocked) s 16 r (thread.) s 25 r (The) s 16 r (allocation) s 17 r (facility) s 16 r (should) s 17 r (be) s 16 r (adaptable) s 17 r (to) s 17 r (the) s 16 r (dif) s 0 r (ferent) s 16 r (multiprocessor) s 0 2669 p (architectures) s 13 r (that) s 13 r (can) s 13 r (run) s 13 r (Mach,) s 14 r (in) s 13 r (particular) s -1 r 44 c 12 r (it) s 13 r (should) s 13 r (be) s 13 r (able) s 13 r (to) s 13 r (support) s 13 r (UMA) s 13 r (and) s 13 r (NUMA) s 13 r (architectures) s 0 2725 p (without) s 12 r (major) s 13 r (changes) s 12 r (to) s 13 r (the) s 12 r (kernel) s 13 r (interface.) s 19 r (The) s 13 r (facility) s 12 r (should) s 13 r (also) s 12 r (accommodate) s 13 r (the) s 12 r (dif) s 0 r (ferent) s 12 r (policies) s 951 2843 p (10) s @eop 11 @bop0 @F67 @sf [ 80 76 0 74 149.436] 35 @dc [<00000000000000001FF80000000000000007FFF8000000000000007FE00000000000000007F800000000000000003F800000 000000000000F8000000000000000007C000000000000000001F00000000000000000078000000000000000001E000000000 00000000038000000000000000000F0000000000000000003C00000000000000000070000000000000000001E00000000000 00000003800000000000000000070000000000000000000E0000000000000000003C00000000000000000070000000000000 000000E0000000000000000001C0000000000000000003800000000000000000070000000000000000000E00000000000000 00001C000000000000000000380000000000000000007000000000000000000060000000000000000000E000000000000000 0001C000000000000000000380000000000000000003000000000000000000070000000000000000000E0000000000000000 000C0000000000000000001C0000000000000000003800000000000000000030000000000000000000700000000000000000 0060000000000000000000E0000000000000000000C0000000000000000001C0000000000000000001800000000000000000 0380000000000000000003000000000000000000070000000000000000000600000000000000000006000000000000000000 0E0000000000000000000C0000000000000000000C0000000000000000001C00000000000000000018000000000000000000 1800000000000000000038000000000000000000300000000000000000003000000000000000000030000000000000000000 7000000000000000000060000000000000000000600000000000000000006000000000000000000060000000000000000000 60000000000000000000E0000000000000000000C0000000000000000000C0000000000000000000C0000000000000000000 C0000000000000000000C0000000000000000000C0000000000000000000C0000000000000000000C0000000000000000000 C0000000000000000000> 80 76 0 0 149.436] 34 @dc [<0000000000000000003000000000000000000030000000000000000000300000000000000000003000000000000000000030 0000000000000000003000000000000000000030000000000000000000300000000000000000003000000000000000000070 0000000000000000006000000000000000000060000000000000000000600000000000000000006000000000000000000060 000000000000000000E0000000000000000000C0000000000000000000C0000000000000000000C0000000000000000001C0 0000000000000000018000000000000000000180000000000000000003800000000000000000030000000000000000000300 00000000000000000700000000000000000006000000000000000000060000000000000000000E0000000000000000000C00 00000000000000001C0000000000000000001800000000000000000038000000000000000000300000000000000000007000 000000000000000060000000000000000000E0000000000000000000C0000000000000000001C00000000000000000038000 0000000000000003000000000000000000070000000000000000000E0000000000000000000C0000000000000000001C0000 00000000000000380000000000000000007000000000000000000060000000000000000000E0000000000000000001C00000 00000000000003800000000000000000070000000000000000000E0000000000000000001C00000000000000000038000000 00000000000070000000000000000000E0000000000000000003C00000000000000000070000000000000000000E00000000 00000000001C00000000000000000078000000000000000000E0000000000000000003C000000000000000000F0000000000 000000001C00000000000000000078000000000000000001E000000000000000000F8000000000000000003E000000000000 000001F000000000000000001FC00000000000000001FE00000000000000007FE000000000000000FFFE0000000000000000 FF800000000000000000> 80 76 74 74 149.436] 32 @dc [ 80 76 74 0 149.436] 33 @dc [ 88 85 0 83 166.040] 39 @dc [<0000000000000000001FF800000000000000000FFFF80000000000000000FFE000000000000000000FF00000000000000000 007F00000000000000000001F00000000000000000000F800000000000000000003E00000000000000000000F00000000000 0000000003C00000000000000000000F000000000000000000003C00000000000000000000F000000000000000000001C000 000000000000000007800000000000000000000E000000000000000000003C00000000000000000000700000000000000000 0000E000000000000000000001C000000000000000000007800000000000000000000E000000000000000000001C00000000 00000000000038000000000000000000007000000000000000000000E000000000000000000001C000000000000000000003 8000000000000000000007000000000000000000000E000000000000000000001C0000000000000000000018000000000000 0000000038000000000000000000007000000000000000000000E000000000000000000000C000000000000000000001C000 00000000000000000380000000000000000000030000000000000000000007000000000000000000000E0000000000000000 00000C000000000000000000001C000000000000000000003800000000000000000000300000000000000000000070000000 000000000000006000000000000000000000E000000000000000000000C000000000000000000001C0000000000000000000 0180000000000000000000018000000000000000000003800000000000000000000300000000000000000000070000000000 0000000000060000000000000000000006000000000000000000000E000000000000000000000C000000000000000000000C 000000000000000000001C000000000000000000001800000000000000000000180000000000000000000018000000000000 0000000038000000000000000000003000000000000000000000300000000000000000000030000000000000000000007000 0000000000000000006000000000000000000000600000000000000000000060000000000000000000006000000000000000 00000060000000000000000000006000000000000000000000E000000000000000000000C000000000000000000000C00000 0000000000000000C000000000000000000000C000000000000000000000C000000000000000000000C00000000000000000 0000C000000000000000000000C000000000000000000000C000000000000000000000> 88 85 0 0 166.040] 38 @dc [<0000000000000000000018000000000000000000001800000000000000000000180000000000000000000018000000000000 0000000018000000000000000000001800000000000000000000180000000000000000000018000000000000000000001800 0000000000000000003800000000000000000000300000000000000000000030000000000000000000003000000000000000 0000003000000000000000000000300000000000000000000030000000000000000000007000000000000000000000600000 000000000000000060000000000000000000006000000000000000000000E000000000000000000000C00000000000000000 0000C000000000000000000000C000000000000000000001C000000000000000000001800000000000000000000180000000 0000000000000380000000000000000000030000000000000000000003000000000000000000000700000000000000000000 06000000000000000000000E000000000000000000000C000000000000000000000C000000000000000000001C0000000000 0000000000180000000000000000000038000000000000000000003000000000000000000000700000000000000000000060 00000000000000000000E000000000000000000001C000000000000000000001800000000000000000000380000000000000 000000070000000000000000000006000000000000000000000E000000000000000000001C00000000000000000000180000 000000000000000038000000000000000000007000000000000000000000E000000000000000000000C00000000000000000 0001C0000000000000000000038000000000000000000007000000000000000000000E000000000000000000001C00000000 00000000000038000000000000000000007000000000000000000000E000000000000000000001C000000000000000000003 800000000000000000000F000000000000000000001C00000000000000000000380000000000000000000070000000000000 00000001E000000000000000000003800000000000000000000F000000000000000000001C00000000000000000000780000 0000000000000001E000000000000000000007800000000000000000001E0000000000000000000078000000000000000000 03E00000000000000000000F800000000000000000007C00000000000000000007F00000000000000000007F800000000000 0000003FF80000000000000000FFFF800000000000000000FFC0000000000000000000> 88 85 83 83 166.040] 36 @dc [ 88 85 83 0 166.040] 37 @dc @F65 @sf [ 16 15 6 -25 41.510] 54 @dc 11 @bop1 514 41 p 903 2 ru 514 461 p 2 420 ru @P33 @sfps 731 261 p (Operating) s 15 r (System) s 15 r (Kernel) s 1416 461 p 2 420 ru 514 462 p 903 2 ru @F67 @sf 515 627 p 35 c 515 702 p 2 1 ru 515 777 p 34 c 935 627 p 32 c 935 702 p 2 1 ru 935 777 p 33 c -493 r 271 2 ru 591 627 p 271 2 ru @P33 @sfps 606 710 p (Application) s @F67 @sf 1115 552 p 39 c 1115 768 p 2 134 ru 1115 852 p 38 c 1415 552 p 36 c 1415 768 p 2 134 ru 1415 852 p 37 c -381 r 134 2 ru 1199 552 p 134 2 ru @P33 @sfps 1206 710 p (Server) s 725 551 p 2 90 ru @F65 @sf 726 503 p 54 c 725 626 p 2 75 ru 1 r 63 c 1026 702 p 90 2 ru 1074 701 p 45 c 936 702 p 90 2 ru 936 701 p 27 c 1265 506 p 2 45 ru 1266 503 p 54 c 1265 551 p 2 45 ru 1 r 63 c @P33 @sfps 564 949 p (Figure) s 15 r (2:) s 21 r (Processor) s 15 r (Allocation) s 15 r (Components) s 0 1084 p (that) s 12 r (are) s 13 r (sure) s 12 r (to) s 12 r (exist) s 12 r (at) s 13 r (various) s 12 r (installations) s 12 r (concerning) s 12 r (who) s 13 r (can) s 12 r (allocate) s 12 r (how) s 12 r (many) s 13 r (processors,) s 12 r (when,) s 13 r (and) s 0 1140 p (for) s 16 r (how) s 15 r (long.) s 22 r (Changes) s 16 r (to) s 16 r (these) s 16 r (policies) s 15 r (should) s 16 r (not) s 16 r (require) s 16 r (rebuilding) s 15 r (the) s 16 r (kernel.) s 22 r (Finally) s -2 r 44 c 15 r (it) s 16 r (is) s 15 r (desirable) s 0 1197 p (to) s 16 r (of) s 0 r (fer) s 15 r (applications) s 16 r (complete) s 17 r (control) s 16 r (over) s 16 r (which) s 16 r (threads) s 16 r (execute) s 16 r (on) s 16 r (which) s 16 r (processors,) s 17 r (but) s 16 r (applications) s 0 1253 p (that) s 15 r (do) s 15 r (not) s 15 r (want) s 16 r (this) s 15 r (degree) s 15 r (of) s 15 r (control) s 15 r (should) s 15 r (not) s 16 r (be) s 15 r (forced) s 15 r (to) s 15 r (implement) s 15 r (it.) s 62 1351 p (Mach') s -1 r 115 c 19 r (processor) s 21 r (allocation) s 20 r (facility) s 21 r (meets) s 20 r (these) s 21 r (goals) s 20 r (by) s 21 r (dividing) s 20 r (the) s 21 r (responsibility) s 20 r (for) s 21 r (processor) s 0 1408 p (allocation) s 15 r (among) s 15 r (the) s 15 r (three) s 16 r (components) s 15 r (shown) s 15 r (in) s 15 r (Figure) s 15 r (2:) s 57 1506 p (1.) s 23 r (Kernel) s 15 r 208 c 15 r (Allocation) s 15 r (mechanisms) s 15 r (only) s -2 r 46 c 57 1581 p (2.) s 23 r (Server) s 15 r 208 c 15 r (Implements) s 15 r (allocation) s 15 r (policy) s -2 r 46 c 57 1656 p (3.) s 23 r (Application) s 15 r 208 c 15 r (Requests) s 15 r (processors) s 15 r (from) s 15 r (server) s 15 r (and) s 16 r (uses) s 15 r (them.) s 20 r (Can) s 15 r (control) s 15 r (their) s 15 r (use) s 16 r (if) s 15 r (desired.) s 0 1754 p (The) s 17 r (server) s 18 r (must) s 17 r (be) s 17 r (privileged) s 18 r (to) s 17 r (gain) s 17 r (direct) s 18 r (control) s 17 r (over) s 17 r (processors.) s 27 r (It) s 17 r (is) s 18 r (also) s 17 r (the) s 17 r (primary) s 18 r (component) s 0 1810 p (af) s 0 r (fected) s 11 r (by) s 13 r (changes) s 12 r (in) s 12 r (usage) s 13 r (policies) s 12 r (or) s 12 r (hardware) s 12 r (con) s 0 r 174 c 0 r (guration,) s 13 r (and) s 12 r (is) s 13 r (much) s 12 r (easier) s 12 r (to) s 13 r (replace) s 12 r (or) s 12 r (recon) s 0 r 174 c 0 r (g-) s 0 1867 p (ure) s 13 r (than) s 12 r (the) s 13 r (kernel.) s 19 r (This) s 13 r (design) s 12 r (assumes) s 13 r (that) s 13 r (processors) s 12 r (will) s 13 r (be) s 12 r (dedicated) s 13 r (to) s 13 r (applications) s 12 r (for) s 13 r (time) s 13 r (periods) s 0 1923 p (of) s 16 r (seconds) s 15 r (or) s 16 r (more) s 16 r (rather) s 15 r (than) s 16 r (milliseconds) s 16 r (to) s 15 r (amortize) s 16 r (the) s 16 r (overhead) s 15 r (of) s 16 r (crossing) s 16 r (the) s 15 r (boundaries) s 16 r (among) s 0 1980 p (the) s 19 r (components) s 19 r (in) s 18 r (Figure) s 19 r 50 c 19 r (to) s 19 r (perform) s 19 r (allocation.) s 31 r (The) s 19 r (application) s 18 r (to) s 19 r (server) s 19 r (interface) s 19 r (is) s 19 r (not) s 18 r (speci) s 0 r 174 c 0 r (ed) s 0 2036 p (because) s 19 r (it) s 19 r (can) s 19 r (be) s 19 r (expected) s 20 r (to) s 19 r (change) s 19 r (with) s 19 r (both) s 19 r (policy) s 19 r (and) s 19 r (hardware) s 19 r (architecture.) s 32 r (Some) s 20 r (servers) s 19 r (may) s 0 2092 p (require) s 18 r (applications) s 18 r (to) s 18 r (provide) s 18 r (authentication) s 18 r (information) s 18 r (to) s 19 r (establish) s 18 r (their) s 18 r (right) s 18 r (to) s 18 r (use) s 18 r (certain) s 18 r (proces-) s 0 2149 p (sors,) s 17 r (while) s 16 r (other) s 17 r (servers) s 16 r (may) s 17 r (require) s 16 r (information) s 17 r (describing) s 16 r (the) s 17 r (location) s 16 r (of) s 17 r (the) s 16 r (requested) s 17 r (processors) s 16 r (in) s 0 2205 p 97 c 17 r (NUMA) s 17 r (architecture.) s 27 r (The) s 17 r (kernel) s 17 r (interface) s 18 r (does) s 17 r (not) s 17 r (change) s 17 r (from) s 17 r (machine) s 18 r (to) s 17 r (machine,) s 18 r (but) s 17 r (some) s 17 r (calls) s 0 2262 p (return) s 15 r (machine-dependent) s 15 r (information.) s 62 2370 p (The) s 21 r (allocation) s 21 r (facility) s 21 r (adds) s 21 r (two) s 22 r (new) s 21 r (objects) s 21 r (to) s 21 r (the) s 21 r (Mach) s 21 r (kernel) s 21 r (interface,) s 22 r (the) s @P37 @sfps 21 r (pr) s 0 r (ocessor) s @P33 @sfps 20 r (and) s 21 r (the) s @P37 @sfps 0 2426 p (pr) s -1 r (ocessor) s 19 r (set) s @P33 @sfps 0 r 46 c 32 r (Processor) s 20 r (objects) s 19 r (correspond) s 19 r (to) s 20 r (physical) s 19 r (processors,) s 20 r (and) s 20 r (are) s 19 r (used) s 19 r (to) s 20 r (manipulate) s 19 r (them.) s 0 2483 p (Processor) s 12 r (set) s 12 r (objects) s 13 r (are) s 12 r (independent) s 12 r (entities) s 12 r (to) s 13 r (which) s 12 r (threads) s 12 r (and) s 12 r (processors) s 13 r (can) s 12 r (be) s 12 r (assigned.) s 19 r (Processors) s 0 2539 p (only) s 13 r (execute) s 14 r (threads) s 13 r (assigned) s 14 r (to) s 13 r (the) s 14 r (same) s 13 r (processor) s 14 r (set) s 13 r (and) s 14 r (vice-versa,) s 14 r (and) s 13 r (every) s 14 r (processor) s 13 r (and) s 14 r (thread) s 13 r (is) s 0 2595 p (always) s 16 r (assigned) s 16 r (to) s 16 r 97 c 17 r (processor) s 16 r (set.) s 23 r (If) s 16 r 97 c 16 r (processor) s 16 r (set) s 16 r (has) s 17 r (no) s 16 r (assigned) s 16 r (processors,) s 16 r (then) s 16 r (threads) s 16 r (assigned) s 0 2652 p (to) s 14 r (it) s 14 r (are) s 15 r (suspended.) s 20 r (Assignments) s 14 r (are) s 14 r (initialized) s 14 r (by) s 15 r (an) s 14 r (inheritance) s 14 r (mechanism.) s 20 r (Each) s 14 r (task) s 14 r (is) s 15 r (also) s 14 r (assigned) s 0 2708 p (to) s 15 r 97 c 15 r (processor) s 16 r (set,) s 15 r (but) s 15 r (this) s 15 r (assignment) s 16 r (is) s 15 r (used) s 15 r (only) s 15 r (to) s 15 r (initialize) s 16 r (the) s 15 r (assignment) s 15 r (of) s 15 r (threads) s 16 r (created) s 15 r (in) s 15 r (that) s 952 2843 p 49 c -1 r 49 c @eop 12 @bop0 @F36 @sf [<00000200000000030000000003000000000180000000018000000000C00000000060007FFFFFF000FFFFFFF8000000000C00 000000070000000003C000000000F0000000007C00000001F000000003800000000E00FFFFFFFC007FFFFFF0000000006000 000000C000000000C0000000018000000003000000000300000000020000> 40 26 -3 2 45.454] 41 @dc 12 @bop1 @P33 @sfps 0 42 p (task.) s 20 r (In) s 15 r (turn) s 14 r (each) s 15 r (task') s -2 r 115 c 14 r (initial) s 14 r (assignment) s 15 r (is) s 14 r (inherited) s 15 r (from) s 15 r (its) s 14 r (parent) s 15 r (upon) s 14 r (creation,) s 15 r (and) s 15 r (the) s 14 r 174 c 0 r (rst) s 15 r (task) s 14 r (in) s 0 98 p (the) s 15 r (system) s 15 r (is) s 15 r (initially) s 15 r (assigned) s 15 r (to) s 16 r (the) s @P37 @sfps 15 r (default) s 15 r (pr) s -1 r (ocessor) s 14 r (set) s @P33 @sfps 0 r 46 c 20 r (Thus) s 15 r (in) s 16 r (the) s 15 r (absence) s 15 r (of) s 15 r (explicit) s 15 r (assignments,) s 0 154 p (every) s 13 r (thread) s 13 r (and) s 13 r (task) s 13 r (in) s 13 r (the) s 13 r (system) s 13 r (will) s 13 r (inherit) s 13 r (the) s 13 r 174 c 0 r (rst) s 13 r (task') s -1 r 115 c 12 r (assignment) s 13 r (to) s 13 r (the) s 13 r (default) s 13 r (processor) s 13 r (set.) s 20 r (All) s 0 211 p (processors) s 17 r (are) s 17 r (initially) s 16 r (assigned) s 17 r (to) s 17 r (the) s 17 r (default) s 17 r (processor) s 16 r (set,) s 18 r (and) s 16 r (at) s 17 r (least) s 17 r (one) s 17 r (processor) s 17 r (must) s 16 r (always) s 17 r (be) s 0 267 p (assigned) s 13 r (to) s 14 r (it) s 13 r (so) s 14 r (that) s 13 r (internal) s 14 r (kernel) s 13 r (threads) s 13 r (and) s 14 r (important) s 13 r (daemons) s 14 r (can) s 13 r (be) s 14 r (run.) s 19 r (Processors) s 14 r (and) s 13 r (processor) s 0 324 p (sets) s 21 r (are) s 20 r (represented) s 21 r (by) s 20 r (Mach) s 21 r (ports.) s 37 r (Since) s 20 r (access) s 21 r (to) s 20 r 97 c 21 r (port) s 20 r (requires) s 21 r (possession) s 21 r (of) s 20 r 97 c 21 r (kernel-managed) s 0 380 p (capability) s 16 r (for) s 17 r (the) s 16 r (port,) s 17 r (or) s @P37 @sfps 16 r (port) s 16 r (right) s @P33 @sfps 0 r 44 c 17 r (entities) s 16 r (other) s 16 r (than) s 17 r (the) s 16 r (appropriate) s 16 r (server) s 17 r (and/or) s 16 r (application) s 16 r (cannot) s 0 437 p (interfere) s 16 r (with) s 15 r (allocations) s 16 r (because) s 15 r (they) s 16 r (do) s 15 r (not) s 16 r (have) s 15 r (the) s 16 r (required) s 15 r (port) s 16 r (right\(s\).) s 21 r (Processor) s 16 r (sets) s 15 r (also) s 16 r (have) s 15 r 97 c 0 493 p (name) s 16 r (port) s 16 r (for) s 17 r (identi) s 0 r 174 c 0 r (cation) s 16 r (and) s 16 r (status) s 16 r (queries,) s 16 r (but) s 17 r (this) s 16 r (port) s 16 r (cannot) s 16 r (be) s 16 r (used) s 16 r (to) s 17 r (manipulate) s 16 r (the) s 16 r (processor) s 0 550 p (set.) s 62 648 p (The) s 11 r (allocation) s 11 r (and) s 11 r (use) s 11 r (of) s 11 r (dedicated) s 11 r (processors) s 11 r (involves) s 11 r (the) s 11 r (application,) s 12 r (server) s 11 r (and) s 11 r (kernel.) s 19 r (The) s 11 r (division) s 0 704 p (of) s 12 r (responsibilities) s 13 r (is) s 12 r (that) s 12 r (the) s 13 r (server) s 12 r (controls) s 12 r (the) s 13 r (assignment) s 12 r (of) s 12 r (processors) s 13 r (to) s 12 r (processor) s 12 r (sets,) s 13 r (the) s 13 r (application) s 0 760 p (controls) s 11 r (the) s 12 r (assignment) s 11 r (of) s 12 r (tasks) s 11 r (and) s 11 r (threads) s 12 r (to) s 11 r (processor) s 12 r (sets,) s 12 r (and) s 11 r (the) s 12 r (kernel) s 11 r (does) s 11 r (whatever) s 12 r (the) s 11 r (application) s 0 817 p (and) s 12 r (server) s 13 r (ask) s 12 r (it) s 13 r (to) s 12 r (do.) s 20 r (The) s 12 r (following) s 12 r (example) s 13 r (describes) s 12 r (how) s 13 r (an) s 12 r (application) s 13 r (might) s 12 r (allocate) s 13 r (six) s 12 r (processors) s 0 873 p (for) s 15 r (its) s 15 r (use:) s 57 971 p (1.) s @P38 @sfps 23 r (Application) s @F36 @sf 15 r 41 c @P38 @sfps 15 r (Kernel) s @P33 @sfps 15 r (Create) s 15 r (processor) s 15 r (set.) s 57 1046 p (2.) s @P38 @sfps 23 r (Application) s @F36 @sf 15 r 41 c @P38 @sfps 15 r (Server) s @P33 @sfps 15 r (Request) s 15 r (six) s 15 r (processors) s 15 r (for) s 16 r (processor) s 15 r (set.) s 57 1122 p (3.) s @P38 @sfps 23 r (Application) s @F36 @sf 15 r 41 c @P38 @sfps 15 r (Kernel) s @P33 @sfps 15 r (Assign) s 15 r (threads) s 15 r (to) s 15 r (processor) s 16 r (set.) s 57 1197 p (4.) s @P38 @sfps 23 r (Server) s @F36 @sf 15 r 41 c @P38 @sfps 15 r (Kernel) s @P33 @sfps 15 r (Assign) s 15 r (processors) s 15 r (to) s 15 r (processor) s 16 r (set.) s 57 1272 p (5.) s @P38 @sfps 23 r (Application) s @P33 @sfps 15 r (Use) s 15 r (processors.) s 57 1347 p (6.) s @P38 @sfps 23 r (Application) s @F36 @sf 15 r 41 c @P38 @sfps 15 r (Server) s @P33 @sfps 15 r (Finished) s 15 r (with) s 15 r (processors) s 15 r (\(OPTIONAL\).) s 57 1422 p (7.) s @P38 @sfps 23 r (Server) s @F36 @sf 15 r 41 c @P38 @sfps 15 r (Kernel) s @P33 @sfps 15 r (Reassign) s 15 r (processors.) s 0 1520 p (This) s 14 r (example) s 14 r (illustrates) s 14 r (three) s 14 r (important) s 14 r (features) s 14 r (of) s 14 r (the) s 14 r (allocation) s 14 r (facility) s -2 r 46 c 19 r (The) s 14 r 174 c 0 r (rst) s 14 r (is) s 14 r (that) s 14 r (the) s 15 r (application) s 0 1577 p (creates) s 15 r (the) s 15 r (processor) s 15 r (set) s 15 r (and) s 15 r (uses) s 15 r (it) s 15 r (as) s 15 r (the) s 16 r (basis) s 15 r (of) s 15 r (its) s 15 r (communication) s 15 r (with) s 15 r (the) s 15 r (server) s -1 r 44 c 14 r (freeing) s 15 r (the) s 15 r (server) s 0 1633 p (from) s 12 r (dependence) s 12 r (on) s 11 r (the) s 12 r (internal) s 12 r (structure) s 12 r (of) s 12 r (the) s 11 r (application.) s 19 r (The) s 12 r (second) s 12 r (feature) s 12 r (is) s 12 r (that) s 11 r (only) s 12 r (one) s 12 r (processor) s 0 1689 p (set) s 18 r (is) s 18 r (used.) s 29 r (The) s 18 r (scheduling) s 18 r (algorithms) s 18 r (described) s 19 r (earlier) s 18 r (function) s 18 r (within) s 18 r (each) s 18 r (processor) s 18 r (set,) s 19 r (and) s 18 r (if) s 18 r (the) s 0 1746 p (task) s 14 r (in) s 14 r (this) s 15 r (example) s 14 r (contains) s 14 r (six) s 14 r (or) s 15 r (fewer) s 14 r (threads) s 14 r (there) s 14 r (will) s 14 r (be) s 15 r (no) s 14 r (context) s 14 r (switches) s 14 r (to) s 15 r (shuf) s 0 r 175 c 0 r 101 c 13 r (the) s 14 r (threads) s 0 1802 p (among) s 21 r (the) s 22 r (allocated) s 21 r (processors.) s 39 r (The) s 21 r (third) s 21 r (feature) s 22 r (is) s 21 r (that) s 21 r (the) s 22 r (server) s 21 r (does) s 21 r (not) s 22 r (need) s 21 r (the) s 21 r (application') s -1 r 115 c 0 1859 p (cooperation) s 19 r (to) s 20 r (remove) s 19 r (processors) s 19 r (from) s 20 r (it.) s 33 r (The) s 19 r (server) s 19 r (retains) s 20 r (complete) s 19 r (control) s 19 r (over) s 20 r (the) s 19 r (processors) s 19 r (at) s 0 1915 p (all) s 17 r (times) s 16 r (because) s 17 r (it) s 16 r (retains) s 17 r (the) s 16 r (access) s 17 r (rights) s 17 r (to) s 16 r (the) s 17 r (processor) s 16 r (objects.) s 25 r (Removing) s 16 r (processors) s 17 r (without) s 16 r (the) s 0 1972 p (application') s -2 r 115 c 20 r (cooperation) s 20 r (should) s 20 r (not) s 20 r (be) s 20 r (necessary) s 20 r (for) s 20 r (well-behaved) s 20 r (applications,) s 21 r (but) s 20 r (can) s 20 r (be) s 20 r (useful) s 20 r (to) s 0 2028 p (remove) s 15 r (processors) s 15 r (from) s 15 r 97 c 16 r (runaway) s 15 r (application) s 15 r (that) s 15 r (has) s 15 r (exceeded) s 15 r (its) s 16 r (allocated) s 15 r (time.) s 62 2126 p (This) s 14 r (design) s 13 r (meets) s 13 r (its) s 14 r 175 c 0 r (exibility) s 13 r (goals.) s 20 r (Dif) s 0 r (ferent) s 12 r (programming) s 13 r (models) s 14 r (and) s 13 r (languages) s 14 r (are) s 13 r (supported) s 13 r (by) s 0 2183 p (the) s 17 r (ability) s 16 r (to) s 17 r (assign) s 17 r (processors) s 16 r (to) s 17 r (individual) s 17 r (processor) s 17 r (sets,) s 17 r (or) s 16 r (to) s 17 r (one) s 17 r (or) s 16 r (more) s 17 r (common) s 17 r (sets) s 16 r (that) s 17 r (match) s 0 2239 p (the) s 15 r (application') s -1 r 115 c 14 r (requirements.) s 21 r (An) s 16 r (assignment) s 15 r (of) s 15 r (one) s 16 r (processor) s 15 r (to) s 16 r (each) s 15 r (of) s 15 r 97 c 16 r (collection) s 15 r (of) s 15 r (processor) s 16 r (sets) s 0 2296 p (provides) s 19 r (the) s 18 r (application) s 19 r (with) s 18 r (complete) s 19 r (control) s 19 r (over) s 18 r (which) s 19 r (threads) s 19 r (run) s 18 r (on) s 19 r (which) s 18 r (processors.) s 31 r (Isolating) s 0 2352 p (scheduling) s 13 r (policy) s 12 r (in) s 13 r 97 c 13 r (server) s 13 r (makes) s 12 r (it) s 13 r (easy) s 13 r (to) s 12 r (change) s 13 r (for) s 13 r (dif) s 0 r (ferent) s 12 r (hardware) s 12 r (architectures) s 13 r (and) s 13 r (site-speci) s 0 r 174 c 0 r 99 c 0 2408 p (usage) s 19 r (policies.) s 33 r (NUMA) s 19 r (machines) s 20 r (can) s 19 r (use) s 20 r (this) s 19 r (processor) s 19 r (allocation) s 20 r (facility) s 19 r (to) s 19 r (match) s 20 r (processor) s 19 r (sets) s 19 r (to) s 0 2465 p (clusters) s 16 r (of) s 16 r (processors) s 16 r (with) s 16 r (identical) s 16 r (memory) s 16 r (access) s 16 r (characteristics.) s 23 r (This) s 16 r (disables) s 16 r (the) s 16 r (kernel) s 16 r (scheduler) s 2 r 39 c -1 r 115 c 0 2521 p (load) s 17 r (balancing) s 18 r (between) s 17 r (clusters) s 18 r (which) s 17 r (is) s 17 r 97 c 18 r (minimum) s 17 r (requirement) s 18 r (for) s 17 r (scheduling) s 17 r (on) s 18 r (NUMA) s 17 r (machines.) s 0 2578 p (The) s 19 r (allocation) s 20 r (facility) s 19 r (does) s 20 r (not) s 19 r (provide) s 19 r 97 c 20 r (replacement) s 19 r (for) s 20 r (the) s 19 r (disabled) s 19 r (load) s 20 r (balancing,) s 20 r (but) s 20 r (the) s 19 r (kernel) s 0 2634 p (interface) s 16 r (has) s 17 r (been) s 16 r (designed) s 16 r (to) s 16 r (make) s 17 r (suf) s 0 r 174 c 0 r (cient) s 15 r (information) s 16 r (available) s 17 r (for) s 16 r 97 c 16 r (user) s 0 r (-mode) s 16 r (implementation) s 16 r (of) s 0 2691 p 97 c 15 r (NUMA) s 15 r (load) s 15 r (balancer) s -1 r 46 c 951 2843 p (12) s @eop 13 @bop0 13 @bop1 622 43 p 688 2 ru 621 100 p 2 56 ru @P33 @sfps 753 83 p (Operation) s 1065 100 p 2 56 ru 1140 83 p 84 c 0 r (ime) s 1309 100 p 2 56 ru 622 101 p 688 2 ru 622 111 p 688 2 ru 621 168 p 2 56 ru 647 151 p (Create) s 15 r (Processor) s 15 r (Set) s 1065 168 p 2 56 ru 1102 151 p (2250) s @F36 @sf 0 r 6 c @P33 @sfps 0 r (50) s 1309 168 p 2 56 ru 622 169 p 688 2 ru 621 226 p 2 56 ru 647 209 p (Assign) s 15 r (Processor) s 1065 226 p 2 56 ru 1090 209 p (4772) s @F36 @sf 0 r 6 c @P33 @sfps 0 r (128) s 1309 226 p 2 56 ru 622 227 p 688 2 ru 621 284 p 2 56 ru 647 267 p (Assign) s 15 r (thread) s 15 r (\(self\)) s 1065 284 p 2 56 ru 1102 267 p (1558) s @F36 @sf 0 r 6 c @P33 @sfps 0 r (25) s 1309 284 p 2 56 ru 622 286 p 688 2 ru 621 342 p 2 56 ru 647 325 p (Assign) s 15 r (thread) s 15 r (\(other\)) s 1065 342 p 2 56 ru 1090 325 p (2624) s @F36 @sf 0 r 6 c @P33 @sfps 0 r (185) s 1309 342 p 2 56 ru 622 344 p 688 2 ru 479 420 p 84 c -2 r (able) s 14 r (4:) s 20 r (Performance) s 15 r (of) s 15 r (some) s 16 r (Allocation) s 15 r (Operations) s @P38 @sfps 0 554 p (6.2.) s 45 r (Implementation) s @P33 @sfps 0 683 p (The) s 14 r (kernel) s 13 r (implementation) s 14 r (of) s 13 r (processor) s 14 r (sets) s 13 r (is) s 14 r (an) s 13 r (extension) s 14 r (of) s 13 r (the) s 14 r (Mach) s 14 r (timesharing) s 13 r (scheduler) s 14 r (described) s 0 739 p (in) s 14 r (Section) s 14 r (3.) s 20 r (The) s 14 r (data) s 13 r (structure) s 14 r (for) s 14 r (each) s 14 r (processor) s 14 r (set) s 14 r (contains) s 14 r 97 c 14 r (run) s 14 r (queue) s 14 r (that) s 14 r (is) s 14 r (used) s 14 r (as) s 14 r (the) s 13 r (global) s 14 r (run) s 0 796 p (queue) s 16 r (for) s 15 r (processors) s 16 r (assigned) s 15 r (to) s 16 r (it.) s 22 r (The) s 15 r (list) s 16 r (of) s 15 r (idle) s 16 r (processors) s 16 r (is) s 15 r (also) s 16 r (maintained) s 15 r (on) s 16 r 97 c 16 r (per) s 15 r (processor) s 16 r (set) s 0 852 p (basis) s 15 r (because) s 14 r 97 c 15 r (processor) s 14 r (can) s 15 r (only) s 14 r (be) s 15 r (dispatched) s 14 r (to) s 15 r (threads) s 14 r (that) s 15 r (are) s 14 r (assigned) s 15 r (to) s 14 r (its) s 15 r (current) s 14 r (processor) s 15 r (set.) s 0 909 p (The) s 17 r (processor) s 17 r (set) s 16 r (data) s 17 r (structure) s 17 r (is) s 17 r (also) s 17 r (the) s 16 r (head) s 17 r (of) s 17 r (individual) s 17 r (linked) s 17 r (lists) s 16 r (that) s 17 r (are) s 17 r (threaded) s 17 r (through) s 17 r (the) s 0 965 p (data) s 13 r (structures) s 13 r (of) s 13 r (assigned) s 12 r (tasks,) s 14 r (threads) s 13 r (and) s 12 r (processors) s 13 r (so) s 13 r (that) s 13 r (these) s 13 r (entities) s 13 r (can) s 13 r (be) s 12 r (found) s 13 r (and) s 13 r (reassigned) s 0 1022 p (when) s 20 r (the) s 20 r (processor) s 20 r (set) s 21 r (is) s 20 r (terminated.) s 35 r (In) s 20 r (addition,) s 21 r (the) s 20 r (data) s 21 r (structure) s 20 r (contains) s 20 r (some) s 20 r (state) s 20 r (information) s 0 1078 p (required) s 14 r (to) s 13 r (run) s 14 r (the) s 14 r (timesharing) s 14 r (scheduling) s 13 r (algorithm,) s 14 r (the) s 14 r (identities) s 14 r (of) s 13 r (the) s 14 r (ports) s 14 r (that) s 13 r (represent) s 14 r (the) s 14 r (set,) s 14 r (and) s 0 1135 p 97 c 14 r (mutual) s 14 r (exclusion) s 15 r (lock) s 14 r (to) s 14 r (control) s 14 r (access) s 14 r (to) s 15 r (the) s 14 r (data) s 14 r (structure.) s 20 r (The) s 14 r (implementation) s 14 r (of) s 14 r (thread) s 15 r (assignment) s 0 1191 p (suspends) s 14 r (the) s 13 r (thread) s 14 r (during) s 14 r (assignment) s 13 r (so) s 14 r (that) s 14 r (it) s 13 r (can) s 14 r (remain) s 14 r (suspended) s 13 r (if) s 14 r (assigned) s 14 r (to) s 13 r 97 c 14 r (processor) s 14 r (set) s 13 r (with) s 0 1247 p (no) s 14 r (processors.) s 20 r (Interprocessor) s 15 r (interrupts) s 14 r (are) s 15 r (used) s 14 r (for) s 15 r (thread) s 14 r (and) s 14 r (processor) s 15 r (assignment) s 14 r (as) s 15 r (needed.) s 20 r 84 c -2 r (able) s 13 r 52 c 0 1304 p (shows) s 13 r (the) s 13 r (times) s 13 r (required) s 13 r (by) s 13 r (some) s 13 r (basic) s 13 r (operations) s 13 r (in) s 13 r (the) s 13 r (processor) s 12 r (allocation) s 13 r (system) s 13 r (as) s 13 r (mean) s @F36 @sf 13 r 6 c @P33 @sfps 13 r (standard) s 0 1360 p (deviation) s 12 r (in) s 13 r (microseconds.) s 19 r (The) s 12 r (self) s 12 r (and) s 13 r (other) s 12 r (cases) s 12 r (of) s 12 r (thread) s 13 r (assignment) s 12 r (correspond) s 12 r (to) s 12 r 97 c 13 r (thread) s 12 r (assigning) s 0 1417 p (itself) s 15 r (and) s 15 r 97 c 15 r (thread) s 16 r (assigning) s 15 r (another) s 15 r (thread.) s 62 1525 p (Special) s 16 r (techniques) s 15 r (are) s 16 r (used) s 16 r (to) s 15 r (manage) s 16 r (the) s 15 r (processor) s 16 r (to) s 16 r (processor) s 15 r (set) s 16 r (assignments.) s 21 r (Code) s 16 r (in) s 15 r 97 c 16 r (critical) s 0 1581 p (path) s 15 r (of) s 14 r (the) s 15 r (scheduler) s 15 r (reads) s 15 r (the) s 14 r (assignment) s 15 r (as) s 15 r (part) s 14 r (of) s 15 r 174 c 0 r (nding) s 15 r 97 c 15 r (thread) s 14 r (to) s 15 r (run) s 15 r (on) s 14 r 97 c 15 r (processor) s -1 r 46 c 19 r 84 c -2 r 111 c 13 r (optimize) s 0 1637 p (this) s 14 r (common) s 13 r (case) s 14 r (against) s 13 r (infrequent) s 14 r (changes) s 14 r (in) s 13 r (assignment,) s 14 r (each) s 14 r (processor) s 13 r (is) s 14 r (restricted) s 14 r (to) s 13 r (changing) s 14 r (only) s 0 1694 p (its) s 17 r (own) s 18 r (assignment.) s 26 r (This) s 18 r (avoids) s 17 r (the) s 17 r (need) s 18 r (for) s 17 r 97 c 17 r (mutual) s 18 r (exclusion) s 17 r (lock) s 17 r (because) s 18 r 97 c 17 r (processor) s 17 r (looking) s 18 r (for) s 0 1750 p 97 c 18 r (new) s 18 r (thread) s 18 r (cannot) s 18 r (be) s 18 r (simultaneously) s 18 r (changing) s 17 r (its) s 18 r (assignment.) s 29 r (The) s 18 r (cost) s 18 r (to) s 18 r (the) s 18 r (assignment) s 17 r (operation) s 0 1807 p (is) s 19 r (that) s 18 r (it) s 19 r (must) s 18 r (temporarily) s 19 r (bind) s 19 r 97 c 18 r (thread) s 19 r (to) s 18 r (the) s 19 r (processor) s 19 r (while) s 18 r (changing) s 19 r (the) s 18 r (assignment.) s 31 r (An) s 18 r (internal) s 0 1863 p (kernel) s 14 r (thread,) s 15 r (the) s @P37 @sfps 15 r (action) s 14 r (thr) s -1 r (ead) s @P33 @sfps 0 r 44 c 14 r (is) s 14 r (used) s 15 r (for) s 14 r (this) s 15 r (purpose.) s 20 r (Current) s 14 r (kernels) s 15 r (only) s 14 r (use) s 15 r (one) s 14 r (action) s 15 r (thread,) s 14 r (but) s 0 1920 p (are) s 15 r (designed) s 15 r (to) s 16 r (accomodate) s 15 r (more) s 15 r (than) s 15 r (one.) s 21 r (The) s 15 r (processor) s 15 r (assignment) s 16 r (interface) s 15 r (allows) s 15 r 97 c 15 r (server) s 16 r (to) s 15 r (avoid) s 0 1976 p (synchronizing) s 18 r (with) s 18 r (completion) s 19 r (of) s 18 r (each) s 18 r (assignment) s 18 r (so) s 19 r (that) s 18 r 97 c 18 r (server) s 18 r (thread) s 19 r (can) s 18 r (exercise) s 18 r (the) s 18 r (parallelism) s 0 2033 p (available) s 15 r (from) s 15 r (multiple) s 15 r (action) s 16 r (threads.) s @P38 @sfps 0 2197 p (6.3.) s 45 r 65 c 16 r (Gang) s 15 r (Scheduling) s 15 r (Server) s @P33 @sfps 0 2325 p 84 c -2 r 111 c 19 r (demonstrate) s 20 r (the) s 20 r (utility) s 20 r (of) s 19 r (this) s 20 r (work,) s 21 r 97 c 20 r (simple) s 20 r (processor) s 20 r (allocation) s 20 r (server) s 20 r (for) s 20 r (gang) s 20 r (scheduling) s 20 r (has) s 0 2382 p (been) s 17 r (implemented.) s 27 r (This) s 17 r (server) s 18 r (is) s 17 r 97 c 17 r (batch) s 18 r (scheduler) s 17 r (for) s 17 r (processors) s 18 r (that) s 17 r (schedules) s 17 r (requests) s 18 r (on) s 17 r 97 c 17 r (greedy) s 0 2438 p 174 c (rst-come,) s 14 r 174 c 0 r (rst-served) s 14 r (basis) s 14 r (subject) s 13 r (to) s 14 r (the) s 14 r (number) s 13 r (of) s 14 r (available) s 14 r (processors.) s 20 r (The) s 13 r (server) s 14 r (is) s 14 r (con) s 0 r 174 c 0 r (gured) s 14 r (for) s 13 r 97 c 0 2495 p (maximum) s 14 r (allocation) s 13 r (of) s 14 r (75%) s 14 r (of) s 13 r (the) s 14 r (machine) s 14 r (for) s 14 r (at) s 13 r (most) s 14 r (15) s 14 r (minutes) s 13 r (at) s 14 r 97 c 14 r (time.) s 19 r (The) s 14 r (server) s 14 r (implementation) s 0 2551 p (uses) s 17 r (two) s 17 r (threads:) s 24 r (one) s 17 r (to) s 17 r (manage) s 17 r (processors,) s 18 r (the) s 17 r (other) s 17 r (to) s 17 r (communicate) s 17 r (with) s 17 r (applications.) s 26 r (The) s 17 r (primary) s 0 2608 p (interaction) s 16 r (between) s 17 r (these) s 16 r (threads) s 17 r (is) s 16 r (by) s 17 r (operations) s 16 r (on) s 17 r (shared) s 16 r (data) s 17 r (structures) s 16 r (describing) s 17 r (the) s 16 r (requests,) s 17 r (but) s 0 2664 p (the) s 13 r (interaction) s 13 r (thread) s 12 r (sends) s 13 r 97 c 13 r (message) s 13 r (to) s 13 r (the) s 12 r (processor) s 13 r (thread) s 13 r (when) s 13 r (an) s 13 r (immediate) s 12 r (change) s 13 r (is) s 13 r (needed) s 13 r (to) s 12 r (the) s 0 2720 p (assignment) s 16 r (of) s 16 r (processors.) s 22 r (One) s 16 r (such) s 16 r (situation) s 16 r (is) s 16 r (the) s 16 r (receipt) s 16 r (of) s 16 r (an) s 16 r (allocation) s 16 r (request) s 16 r (that) s 16 r (can) s 16 r (be) s 16 r (satis) s 0 r 174 c 0 r (ed) s 951 2843 p (13) s @eop 14 @bop0 14 @bop1 @P33 @sfps 0 42 p (immediately) s -2 r 46 c 26 r (Library) s 18 r (routines) s 17 r (are) s 18 r (available) s 18 r (to) s 17 r (hide) s 18 r (the) s 17 r (server) s 18 r (interfaces,) s 18 r (so) s 17 r (an) s 18 r (application) s 17 r (can) s 18 r (make) s 18 r 97 c 0 98 p (single) s 18 r (call) s 19 r (indicating) s 18 r (how) s 18 r (many) s 19 r (processors) s 18 r (it) s 18 r (wants) s 19 r (for) s 18 r (how) s 19 r (many) s 18 r (seconds.) s 30 r (This) s 18 r (routine) s 18 r (contacts) s 19 r (the) s 0 154 p (server) s -1 r 44 c 14 r (arranges) s 14 r (the) s 14 r (allocation,) s 15 r (and) s 14 r (returns) s 15 r (when) s 14 r (the) s 14 r (server) s 15 r (has) s 14 r (begun) s 14 r (to) s 15 r (assign) s 14 r (the) s 14 r (requested) s 15 r (processors.) s 0 211 p (The) s 13 r (total) s 13 r (time) s 13 r (taken) s 13 r (by) s 13 r (this) s 13 r (routine) s 12 r (is) s 13 r (about) s 13 r (35ms) s 13 r (to) s 13 r (allocate) s 13 r (one) s 13 r (processor) s 13 r (plus) s 13 r (the) s 13 r (processor) s 13 r (assignment) s 0 267 p (time) s 14 r (of) s 14 r (about) s 13 r (5ms) s 14 r (per) s 14 r (additional) s 14 r (processor) s 14 r (from) s 14 r 84 c -3 r (able) s 13 r (4.) s 20 r (This) s 14 r (overhead) s 14 r (is) s 13 r (acceptable) s 14 r (given) s 14 r (the) s 14 r (expected) s 0 324 p (allocation) s 18 r (durations) s 18 r (of) s 17 r (tens) s 18 r (of) s 18 r (seconds) s 18 r (to) s 17 r (tens) s 18 r (of) s 18 r (minutes.) s 28 r (This) s 18 r (server) s 17 r (and) s 18 r (library) s 18 r (interface) s 18 r (have) s 17 r (been) s 0 380 p (successfully) s 11 r (used) s 11 r (by) s 10 r (researchers) s 11 r (and) s 11 r (students) s 11 r (in) s 10 r (an) s 11 r (under) s 0 r (graduate) s 10 r (parallel) s 11 r (programming) s 11 r (course) s 10 r (at) s 11 r (Carnegie) s 0 437 p (Mellon) s 12 r (to) s 12 r (facilitate) s 12 r (performance) s 11 r (measurements) s 12 r (of) s 12 r (parallel) s 12 r (programs.) s 19 r (The) s 12 r (server) s 12 r (removed) s 12 r (almost) s 12 r (all) s 11 r (of) s 12 r (the) s 0 493 p (administrative) s 12 r (dif) s 0 r 174 c 0 r (culties) s 12 r (usually) s 12 r (involved) s 12 r (in) s 12 r (obtaining) s 13 r (dedicated) s 12 r (machine) s 12 r (time.) s 19 r (In) s 13 r (addition,) s 12 r (development) s 0 550 p (of) s 11 r (the) s 12 r (server) s 11 r (repeatedly) s 11 r (demonstrated) s 12 r (the) s 11 r (utility) s 11 r (of) s 11 r (implementing) s 12 r (policy) s 11 r (in) s 11 r 97 c 12 r (separate) s 11 r (server) s 11 r (because) s 12 r (server) s 0 606 p (crashes) s 15 r (did) s 15 r (not) s 15 r (crash) s 16 r (the) s 15 r (operating) s 15 r (system.) s 62 704 p (Many) s 17 r (extensions) s 17 r (and) s 17 r (changes) s 17 r (to) s 16 r (the) s 17 r (policy) s 17 r (implemented) s 17 r (in) s 17 r (the) s @P38 @sfps 17 r (cpu) s 2 r 14 2 ru 14 r (server) s @P33 @sfps 17 r (are) s 17 r (possible.) s 25 r (Since) s 17 r (it) s 17 r (is) s 0 760 p 97 c 16 r (batch) s 16 r (scheduler) s 16 r (for) s 17 r (processors,) s 16 r (techniques) s 16 r (originally) s 16 r (developed) s 16 r (for) s 17 r (batch) s 16 r (scheduling) s 16 r (of) s 16 r (memory) s -2 r 44 c 15 r (such) s 0 817 p (as) s 15 r (assigning) s 16 r (higher) s 15 r (priority) s 16 r (to) s 15 r (shorter) s 15 r (requests,) s 16 r (are) s 15 r (applicable.) s 21 r (In) s 15 r (addition,) s 16 r (the) s 15 r (server) s 16 r (could) s 15 r (be) s 15 r (extended) s 0 873 p (to) s 17 r (allow) s 16 r (some) s 17 r (users) s 17 r (higher) s 16 r (or) s 17 r (absolute) s 16 r (priority) s 17 r (in) s 17 r (allocating) s 16 r (processors,) s 17 r (or) s 17 r (to) s 17 r (allow) s 16 r (more) s 17 r (processors) s 17 r (to) s 0 930 p (be) s 14 r (allocated) s 15 r (during) s 14 r (light) s 14 r (usage) s 15 r (periods.) s 19 r (Finally) s -1 r 44 c 13 r (the) s 14 r (server) s 15 r (can) s 14 r (be) s 14 r (replaced) s 15 r (in) s 14 r (its) s 14 r (entirety) s 14 r (by) s 15 r 97 c 14 r (server) s 14 r (that) s 0 986 p (implements) s 14 r 97 c 15 r (dif) s 0 r (ferent) s 13 r (scheduling) s 14 r (policy) s -2 r 46 c 19 r (One) s 15 r (promising) s 14 r (new) s 14 r (policy) s 14 r (is) s 15 r (to) s 14 r (vary) s 14 r (the) s 14 r (number) s 15 r (of) s 14 r (processors) s 0 1043 p (available) s 13 r (to) s 14 r (applications) s 13 r (based) s 14 r (on) s 13 r (the) s 14 r (overall) s 13 r (demand) s 13 r (for) s 14 r (processors.) s 20 r 65 c 13 r (server) s 13 r (with) s 14 r (this) s 13 r (policy) s 14 r (can) s 13 r (notify) s 0 1099 p (applications) s 15 r (to) s 16 r (recon) s 0 r 174 c 0 r (gure) s 15 r (when) s 16 r (it) s 15 r (changes) s 16 r (the) s 15 r (number) s 15 r (of) s 16 r (processors) s 15 r (available.) s 21 r (Researchers) s 16 r (at) s 15 r (Stanford) s 0 1156 p (are) s 18 r (pursuing) s 17 r (this) s 18 r (approach) s 17 r (and) s 18 r (have) s 17 r (implemented) s 18 r 97 c 17 r (server) s 18 r (for) s 17 r (this) s 18 r (scheduling) s 17 r (policy) s 18 r (under) s 17 r (Mach) s 18 r (with) s 0 1212 p (good) s 15 r (initial) s 15 r (results[) s 0 r 57 c 0 r (].) s @P38 @sfps 0 1381 p (7.) s 45 r (Related) s 16 r 87 c -2 r (ork) s @P33 @sfps 0 1526 p (Previous) s 18 r (work) s 17 r (on) s @P37 @sfps 18 r (policy) s 18 r (mechanism) s 17 r (separation) s @P33 @sfps 18 r (has) s 18 r (proposed) s 18 r (separating) s 17 r (the) s 18 r (scheduler) s 18 r (into) s 17 r (two) s 18 r (pieces:) s 0 1583 p (mechanisms) s 20 r (implemented) s 20 r (in) s 21 r (the) s 20 r (operating) s 20 r (system,) s 22 r (and) s 20 r (policy) s 20 r (decisions) s 20 r (made) s 20 r (by) s 21 r 97 c 20 r (user) s 20 r (mode) s @P37 @sfps 20 r (policy) s 0 1639 p (module) s @P33 @sfps 46 c 40 r (This) s 22 r (work) s 21 r (only) s 22 r (considered) s 22 r (the) s 21 r (problem) s 22 r (of) s 22 r (scheduling) s 22 r (within) s 21 r (applications,) s 24 r (but) s 21 r (encountered) s 0 1695 p (two) s 20 r (problems.) s 35 r (The) s 20 r 174 c 0 r (rst) s 21 r (is) s 20 r (the) s 20 r (overhead) s 20 r (of) s 20 r (crossing) s 20 r (the) s 20 r (boundary) s 21 r (between) s 20 r (the) s 20 r (operating) s 20 r (system) s 20 r (and) s 0 1752 p (an) s 18 r (application) s 18 r (to) s 18 r (access) s 18 r 97 c 18 r (policy) s 17 r (module.) s 29 r (This) s 18 r (required) s 18 r (the) s 18 r (operating) s 18 r (system) s 17 r (to) s 18 r (implement) s 18 r (short) s 18 r (term) s 0 1808 p (policy) s -2 r 44 c 20 r (and) s 20 r (made) s 20 r (it) s 20 r (more) s 20 r (ef) s 0 r 174 c 0 r (cient) s 19 r (to) s 20 r (delay) s 20 r (long) s 20 r (term) s 20 r (policy) s 20 r (decisions) s 20 r (to) s 20 r (the) s 20 r (detriment) s 20 r (of) s 20 r (the) s 20 r (policy) s 0 1865 p (modules.) s 20 r (The) s 15 r (second) s 15 r (is) s 15 r (that) s 15 r (experience) s 15 r (with) s 14 r (the) s 15 r (resulting) s 15 r (systems) s 15 r (reveals) s 15 r (that) s 15 r (most) s 15 r (applications) s 15 r (did) s 15 r (not) s 0 1921 p (use) s 13 r (the) s 13 r (available) s 13 r 175 c 0 r (exibility) s -2 r 46 c 19 r (One) s 13 r (reason) s 13 r (for) s 13 r (this) s 14 r (is) s 13 r (the) s 13 r (inherent) s 13 r (complexity) s 13 r (of) s 13 r (the) s 13 r (policy) s 14 r (modules,) s 13 r (as) s 13 r (most) s 0 1978 p (non-trivial) s 15 r (instances) s 16 r (require) s 15 r (an) s 16 r (intricate) s 15 r (scheduler) s 16 r (implementation[) s 0 r (10) s 0 r 44 c 0 r 49 c -1 r 49 c 0 r (].) s 20 r (Our) s 16 r (use) s 15 r (of) s 16 r (policy) s 15 r (mechanism) s 0 2034 p (separation) s 14 r (avoids) s 14 r (these) s 14 r (problems) s 14 r (because) s 14 r (processor) s 13 r (allocation) s 14 r (decisions) s 14 r (are) s 14 r (made) s 14 r (infrequently) s 14 r (enough) s 14 r (to) s 0 2091 p (ef) s 0 r (fectively) s 13 r (amortize) s 14 r (the) s 14 r (boundary) s 14 r (crossing) s 13 r (costs,) s 15 r (and) s 13 r (because) s 14 r (the) s 14 r (complex) s 14 r (policy) s 14 r (implementation) s 14 r (resides) s 0 2147 p (in) s 15 r 97 c 16 r (server) s 15 r (that) s 16 r (is) s 15 r (implemented) s 16 r (once) s 15 r (for) s 15 r 97 c 16 r (system) s 15 r (rather) s 16 r (than) s 15 r 97 c 16 r (module) s 15 r (that) s 15 r (must) s 16 r (be) s 15 r (customized) s 16 r (to) s 15 r (each) s 0 2204 p (application.) s 62 2302 p (Another) s 18 r (body) s 17 r (of) s 18 r (related) s 17 r (work) s 18 r (concerns) s 17 r (the) s 18 r (area) s 17 r (of) s 18 r (coscheduling.) s @P37 @sfps 27 r (Coscheduling) s @P33 @sfps 17 r (is) s 18 r 97 c 17 r (multiprocessor) s 0 2358 p (scheduling) s 18 r (policy) s 18 r (that) s 18 r (attempts) s 18 r (to) s 17 r (schedule) s 18 r (components) s 18 r (of) s 18 r (an) s 18 r (application) s 18 r (at) s 18 r (the) s 18 r (same) s 18 r (time,) s 18 r (but) s 18 r (makes) s 0 2414 p (no) s 21 r (guarantees) s 21 r (about) s 21 r (its) s 21 r (success) s 21 r (in) s 21 r (doing) s 21 r (so.) s 38 r (This) s 21 r (policy) s 21 r (was) s 21 r (originally) s 21 r (proposed) s 21 r (for) s 21 r (medium) s 21 r (grain) s 0 2471 p (parallel) s 19 r (message) s 18 r (passing) s 19 r (\(hundreds) s 18 r (to) s 19 r (thousands) s 19 r (of) s 18 r (instructions) s 19 r (between) s 18 r (interactions\)) s 19 r (applications) s 19 r (that) s 0 2527 p (bene) s 174 c 116 c 17 r (from) s 16 r (this) s 17 r (coscheduling) s 17 r (but) s 16 r (can) s 17 r (achieve) s 17 r (reasonable) s 16 r (performance) s 17 r (in) s 17 r (its) s 16 r (absence.) s 25 r (The) s 17 r (major) s 16 r (work) s 0 2584 p (on) s 15 r (coscheduling) s 14 r (was) s 15 r (done) s 15 r (for) s 15 r (the) s 14 r (Medusa) s 15 r (operating) s 15 r (system) s 14 r (on) s 15 r (Cm*[) s 0 r 49 c -1 r 49 c 0 r (],) s 14 r (but) s 15 r (it) s 15 r (is) s 14 r (not) s 15 r (directly) s 15 r (applicable) s 0 2640 p (to) s 13 r (current) s 13 r (multiprocessors) s 13 r (because) s 13 r (the) s 13 r (techniques) s 13 r (depend) s 13 r (on) s 13 r (synchronized) s 13 r (clocks) s 13 r (and) s 13 r 97 c 13 r (memory) s 14 r (structure) s 0 2697 p (that) s 15 r (precluded) s 15 r (short) s 15 r (term) s 16 r (load) s 15 r (balancing.) s 20 r (In) s 15 r (contrast,) s 15 r (the) s 16 r (uniform) s 15 r (\(UMA\)) s 15 r (shared) s 15 r (memory) s 15 r (machines) s 15 r (that) s 951 2843 p (14) s @eop 15 @bop0 15 @bop1 @P33 @sfps 0 42 p (are) s 15 r (our) s 15 r (primary) s 15 r (interest) s 16 r (do) s 15 r (need) s 15 r (short) s 15 r (term) s 15 r (load) s 15 r (balancing) s 16 r (and) s 15 r (do) s 15 r (not) s 15 r (have) s 15 r (synchronized) s 15 r (clocks.) s 62 139 p (The) s 15 r (Alliant) s 15 r (Concentrix) s @P13 @sfps 491 123 p 49 c 0 r 49 c @P33 @sfps 540 139 p (scheduler) s 15 r (described) s 15 r (by) s 15 r (Jacobs[) s 0 r (12) s 0 r 93 c 15 r (is) s 15 r (an) s 15 r (example) s 15 r (of) s 15 r (an) s 15 r (alternative) s 15 r (approach) s 0 196 p (to) s 18 r (processor) s 18 r (allocation) s 19 r (and) s 18 r (control.) s 29 r (This) s 19 r (scheduler) s 18 r (supports) s 18 r 97 c 18 r 174 c 0 r (xed) s 19 r (number) s 18 r (of) s 18 r (scheduling) s 18 r (classes) s 19 r (and) s 0 252 p (uses) s 19 r 97 c @P37 @sfps 19 r (scheduling) s 19 r (vector) s @P33 @sfps 19 r (for) s 20 r (each) s 19 r (processor) s 19 r (to) s 19 r (indicate) s 19 r (which) s 19 r (classes) s 19 r (should) s 19 r (be) s 20 r (searched) s 19 r (for) s 19 r (work) s 19 r (in) s 0 309 p (what) s 14 r (order) s -2 r 46 c 19 r (Each) s 14 r (processor) s 13 r (cycles) s 14 r (through) s 14 r 97 c 13 r (set) s 14 r (of) s 14 r (scheduling) s 13 r (vectors) s 14 r (based) s 14 r (on) s 13 r (time) s 14 r (durations) s 14 r (associated) s 0 365 p (with) s 17 r (each) s 18 r (vector) s -1 r 44 c 17 r (typically) s 17 r (fractions) s 17 r (of) s 18 r 97 c 17 r (second.) s 27 r (Processes) s 17 r (are) s 17 r (assigned) s 18 r (to) s 17 r (scheduling) s 17 r (classes) s 18 r (by) s 17 r (their) s 0 422 p (characteristics) s 16 r (or) s 16 r 97 c 16 r (system) s 16 r (call) s 15 r (available) s 16 r (to) s 16 r (privileged) s 16 r (users) s 16 r (and) s 16 r (applications.) s 22 r (This) s 16 r (scheduler) s 16 r (is) s 16 r (oriented) s 0 478 p (towards) s 17 r (dividing) s 17 r (processors) s 16 r (among) s 17 r (statically) s 17 r (de) s 0 r 174 c 0 r (ned) s 17 r (classes) s 17 r (of) s 16 r (applications) s 17 r (over) s 17 r (short) s 17 r (periods) s 17 r (of) s 17 r (time.) s 0 535 p (This) s 16 r (contrasts) s 16 r (with) s 16 r (the) s 16 r (Mach) s 16 r (orientation) s 16 r (of) s 16 r (dedicating) s 17 r (processors) s 16 r (to) s 16 r (applications) s 16 r (over) s 16 r (longer) s 16 r (periods) s 16 r (of) s 0 591 p (time.) s 27 r (Mach') s -1 r 115 c 16 r (processor) s 18 r (sets) s 17 r (can) s 18 r (be) s 17 r (created) s 17 r (dynamically) s 18 r (as) s 17 r (opposed) s 18 r (to) s 17 r (the) s 18 r 174 c 0 r (xed) s 17 r (number) s 18 r (of) s 17 r (scheduling) s 0 648 p (classes.) s 19 r (Scheduling) s 11 r (servers) s 11 r (could) s 11 r (be) s 12 r (implemented) s 11 r (by) s 11 r (reserving) s 11 r (some) s 11 r (scheduling) s 11 r (classes) s 12 r (for) s 11 r (their) s 11 r (exclusive) s 0 704 p (use,) s 18 r (but) s 17 r (the) s 17 r (static) s 18 r (class) s 17 r (and) s 17 r (vector) s 17 r (de) s 0 r 174 c 0 r (nitions) s 18 r (appear) s 17 r (to) s 17 r (restrict) s 17 r (the) s 18 r 175 c 0 r (exibility) s 17 r (available) s 17 r (in) s 17 r (forming) s 18 r (sets) s 0 760 p (of) s 17 r (processors.) s 25 r (The) s 17 r (Concentrix) s 17 r (scheduler) s 17 r (also) s 16 r (enforces) s 17 r 97 c 17 r (more) s 17 r (restrictive) s 17 r (version) s 17 r (of) s 16 r (gang) s 17 r (scheduling) s 17 r (in) s 0 817 p (which) s 13 r 97 c 13 r (blocking) s 14 r (operation) s 13 r (by) s 13 r (any) s 13 r (thread) s 14 r (blocks) s 13 r (the) s 13 r (entire) s 13 r (gang.) s 20 r (This) s 13 r (restricts) s 13 r (its) s 14 r (use) s 13 r (to) s 13 r (applications) s 13 r (that) s 0 873 p (do) s 15 r (not) s 14 r (use) s 15 r (system) s 15 r (concurrency) s 14 r (and) s 15 r (makes) s 15 r (parallel) s 15 r (handling) s 14 r (of) s 15 r (blocking) s 15 r (operations) s 14 r (such) s 15 r (as) s 15 r (I/O) s 14 r (and) s 15 r (page) s 0 930 p (faults) s 15 r (all) s 15 r (but) s 15 r (impossible.) s @P38 @sfps 0 1095 p (8.) s 45 r (Conclusion) s @P33 @sfps 0 1240 p (This) s 22 r (article) s 22 r (has) s 22 r (described) s 22 r (problem) s 22 r (areas) s 22 r (posed) s 22 r (by) s 22 r (the) s 22 r (multiprogrammed) s 22 r (use) s 22 r (of) s 22 r (multiprocessors) s 22 r (and) s 0 1296 p (techniques) s 18 r (used) s 17 r (by) s 18 r (the) s 17 r (Mach) s 18 r (operating) s 18 r (system) s 17 r (to) s 18 r (deal) s 18 r (with) s 17 r (them.) s 28 r (In) s 17 r (the) s 18 r (areas) s 18 r (of) s 17 r (synchronization) s 18 r (and) s 0 1353 p (concurrency) s 19 r (management,) s 20 r (it) s 20 r (described) s 19 r (the) s 19 r (use) s 19 r (of) s 19 r (Discouragement) s 19 r (and) s 20 r (Handof) s 0 r 102 c 18 r (Scheduling) s 19 r (techniques) s 0 1409 p (to) s 20 r (make) s 20 r (ef) s 0 r 174 c 0 r (cient) s 19 r (use) s 19 r (of) s 20 r (processor) s 20 r (time.) s 34 r (Handof) s 0 r 102 c 19 r (Scheduling) s 20 r (is) s 19 r 97 c 20 r (particularly) s 20 r (powerful) s 20 r (technique,) s 21 r (so) s 0 1466 p (hardware) s 14 r (support) s 14 r (such) s 15 r (as) s 14 r (the) s 14 r (atomic) s 14 r (`compare) s 15 r (and) s 14 r (swap') s 14 r (operation) s 14 r (required) s 14 r (to) s 15 r (use) s 14 r (it) s 14 r (for) s 14 r (shared) s 15 r (memory) s 0 1522 p (locks) s 14 r (should) s 14 r (be) s 14 r (considered.) s 20 r (This) s 14 r (paper) s 14 r (also) s 13 r (described) s 14 r 97 c 14 r (general) s 14 r (approach) s 14 r (and) s 14 r (architecture) s 14 r (for) s 14 r (supporting) s 0 1579 p (processor) s 12 r (allocation) s 11 r (and) s 12 r 97 c 11 r (sample) s 12 r (implementation,) s 12 r (the) s @P38 @sfps 12 r (cpu) s 3 r 14 2 ru 13 r (server) s @P33 @sfps 0 r 46 c 19 r (This) s 12 r (work) s 12 r (does) s 11 r (not) s 12 r (solve) s 11 r (the) s 12 r (problems) s 0 1635 p (of) s 15 r (multiprocessor) s 15 r (scheduling,) s 15 r (but) s 15 r (rather) s 15 r (opens) s 15 r (up) s 16 r (new) s 15 r (research) s 15 r (areas) s 15 r (by) s 15 r (replacing) s 15 r (human) s 15 r (administrative) s 0 1691 p (processor) s 20 r (allocation) s 19 r (techniques) s 20 r (with) s 19 r (automatic) s 20 r (techniques) s 19 r (that) s 20 r (can) s 20 r (be) s 19 r (changed) s 20 r (without) s 19 r (modifying) s 20 r (the) s 0 1748 p (operating) s 15 r (system) s 15 r (kernel.) s @P38 @sfps 0 1913 p (Acknowledgements) s @P33 @sfps 0 2058 p (The) s 17 r (initial) s 17 r (design) s 18 r (of) s 17 r (the) s 17 r (run) s 17 r (queue) s 18 r (structure) s 17 r (is) s 17 r (due) s 17 r (to) s 17 r 65 c -2 r (vadis) s 16 r 84 c -2 r (evanian,) s 17 r (Jr) s -2 r 46 c 26 r (and) s 17 r (is) s 17 r (similar) s 18 r (to) s 17 r (structures) s 0 2114 p (used) s 17 r (in) s 17 r (various) s 18 r (versions) s 17 r (of) s 17 r (Unix.) s 26 r (The) s 18 r (initial) s 17 r (implementation) s 17 r (of) s 17 r (handof) s 0 r 102 c 17 r (scheduling) s 17 r (for) s 17 r (kernel) s 17 r (use) s 18 r (was) s 0 2171 p (done) s 19 r (by) s 18 r (Richard) s 19 r (Rashid.) s 30 r (The) s 18 r (author) s 19 r (would) s 18 r (like) s 19 r (to) s 18 r (thank) s 19 r (all) s 18 r (of) s 19 r (the) s 18 r (members) s 19 r (of) s 18 r (the) s 19 r (Mach) s 18 r (project) s 19 r (for) s 0 2227 p (making) s 15 r (this) s 15 r (research) s 16 r (possible.) s 20 r (Code) s 15 r (to) s 16 r (implement) s 15 r (the) s 15 r (features) s 15 r (described) s 16 r (in) s 15 r (this) s 15 r (article) s 15 r (is) s 15 r (expected) s 16 r (to) s 15 r (be) s 0 2284 p (included) s 15 r (in) s 15 r 97 c 16 r (forthcoming) s 15 r (release) s 15 r (of) s 15 r (Mach.) s 21 r (The) s 15 r (author) s 15 r (would) s 16 r (also) s 15 r (like) s 15 r (to) s 15 r (thank) s 15 r (the) s 16 r (referees) s 15 r (and) s 15 r (editors) s 0 2340 p (for) s 15 r (suggestions) s 15 r (that) s 15 r (greatly) s 16 r (improved) s 15 r (the) s 15 r (structure) s 15 r (and) s 15 r (presentation) s 15 r (of) s 16 r (this) s 15 r (article.) s @P38 @sfps 0 2505 p (Refer) s 0 r (ences) s @P33 @sfps 23 2623 p ([1]) s 22 r (R.) s 16 r 70 c -3 r 46 c 14 r (Rashid,) s 15 r 170 c 0 r (Threads) s 15 r (of) s 16 r 97 c 15 r (New) s 15 r (System,) s 0 r 186 c @P37 @sfps 15 r (Unix) s 15 r (Review) s @P33 @sfps 0 r 44 c 15 r (vol.) s 15 r (4,) s 16 r (pp.) s 15 r (37) s 0 r 177 c 0 r (49,) s 15 r (August) s 15 r (1986.) s 0 2655 p 779 2 ru @P4 @sfps 41 2712 p 49 c 0 r 49 c @P18 @sfps 67 2728 p (Concentrix) s 13 r (is) s 12 r 97 c 13 r (trademark) s 12 r (of) s 13 r (Alliant) s 12 r (Computer) s 12 r (Systems.) s @P33 @sfps 951 2843 p (15) s @eop 16 @bop0 16 @bop1 @P33 @sfps 23 42 p ([2]) s 22 r (S.) s 15 r (J.) s 14 r (Lef) s 0 r 175 c 0 r (er) s -1 r 44 c 13 r (M.) s 15 r (K.) s 14 r (McKusick,) s 15 r (M.) s 15 r (J.) s 14 r (Karels,) s 15 r (and) s 14 r (J.) s 15 r (S.) s 14 r (Quarterman,) s @P37 @sfps 15 r (The) s 14 r (Design) s 15 r (and) s 14 r (Implementation) s 98 98 p (of) s 16 r (the) s 15 r (4.3BSD) s 15 r (Unix) s 15 r (Operating) s 15 r (System) s @P33 @sfps 0 r 46 c 20 r (Reading,) s 16 r (MA:) s 15 r (Addison-W) s -3 r (esley) s -3 r 44 c 14 r (1989.) s 23 173 p ([3]) s 22 r (E.) s 16 r (I.) s 15 r (Or) s 0 r (ganick,) s @P37 @sfps 15 r (The) s 15 r (Multics) s 15 r (System:) s 21 r (An) s 15 r (Examination) s 15 r (of) s 16 r (Its) s 15 r (Structur) s -1 r 101 c @P33 @sfps 0 r 46 c 20 r (Cambridge,) s 15 r (MA:) s 15 r (MIT) s 16 r (Press,) s 98 230 p (1972.) s 23 305 p ([4]) s 22 r (L.) s 16 r (J.) s 15 r (Kenah) s 16 r (and) s 15 r (S.) s 15 r 70 c -2 r 46 c 14 r (Bate,) s @P37 @sfps 15 r 86 c -2 r (AX/VMS) s 14 r (Internals) s 16 r (and) s 15 r (Data) s 16 r (Structur) s -1 r (es) s @P33 @sfps 0 r 46 c 20 r (Maynard,) s 15 r (MA:) s 15 r (Digital) s 16 r (Press,) s 98 361 p (1984.) s 23 436 p ([5]) s 22 r (A.) s 15 r (Langerman,) s 14 r (J.) s 14 r (Boykin,) s 15 r (S.) s 14 r (LoV) s -4 r (erso,) s 14 r (and) s 14 r (S.) s 14 r (Mangalat,) s 15 r 170 c 0 r 65 c 14 r (Highly-Parallelized) s 14 r (Mach-based) s 14 r (Vnode) s 98 493 p (Filesystem,) s 0 r 186 c 16 r (in) s @P37 @sfps 15 r (Pr) s -1 r (oceedings) s 14 r (of) s 15 r (the) s 16 r 87 c -2 r (inter) s 14 r (1990) s 15 r (USENIX) s 15 r (Confer) s 0 r (ence) s @P33 @sfps 0 r 44 c 14 r (January) s 15 r (1990.) s 23 568 p ([6]) s 22 r (J.) s 18 r 87 c -3 r 46 c 17 r 87 c -3 r (endorf,) s @P37 @sfps 18 r (Operating) s 18 r (System/Application) s 18 r (Concurr) s -1 r (ency) s 17 r (in) s 18 r 84 c -2 r (ightly-Coupled) s 17 r (Multiple-Pr) s 0 r (ocessor) s 98 624 p (Systems) s @P33 @sfps 0 r 46 c 20 r (PhD) s 13 r (thesis,) s 13 r (Carnegie) s 14 r (Mellon) s 13 r (University) s -2 r 44 c 12 r (Department) s 13 r (of) s 13 r (Computer) s 13 r (Science,) s 14 r (Pittsbur) s 0 r (gh,) s 13 r 80 c -4 r (A,) s 98 681 p (1987.) s 21 r 65 c -3 r (vailable) s 14 r (as) s 16 r 84 c -3 r (echnical) s 15 r (Report) s 15 r (CMU-CS-88-1) s -1 r (17.) s 23 756 p ([7]) s 22 r (E.) s 22 r (C.) s 22 r (Cooper) s 22 r (and) s 22 r (R.) s 22 r 80 c -4 r 46 c 21 r (Draves,) s 23 r 170 c 0 r 67 c 22 r (Threads,) s 0 r 186 c 24 r 84 c -2 r (ech.) s 21 r (Rep.) s 22 r (CMU-CS-88-154,) s 23 r (Computer) s 22 r (Science) s 98 812 p (Department,) s 16 r (Carnegie) s 15 r (Mellon) s 15 r (University) s -2 r 44 c 14 r (June) s 15 r (1988.) s 23 887 p ([8]) s 22 r (C.) s 13 r 80 c -4 r 46 c 11 r (Thacker) s -1 r 44 c 12 r (L.) s 13 r (C.) s 12 r (Stewart,) s 13 r (and) s 12 r (J.) s 13 r (Edwin) s 12 r (H.) s 12 r (Satterwaithe,) s 13 r 170 c 0 r (Fire) s 0 r 175 c 0 r 121 c -2 r 44 c 12 r 65 c 13 r (Multiprocessor) s 12 r (Workstation,) s 0 r 186 c @P37 @sfps 98 944 p (IEEE) s 16 r 84 c -2 r (rans.) s 14 r (Computers) s @P33 @sfps 0 r 44 c 15 r (vol.) s 16 r (8,) s 15 r (pp.) s 15 r (909) s 0 r 177 c 0 r (920,) s 15 r (August) s 15 r (1988.) s 23 1019 p ([9]) s 22 r (A.) s 21 r 84 c 0 r (ucker) s 20 r (and) s 21 r (A.) s 21 r (Gupta,) s 22 r 170 c 0 r (Process) s 21 r (Control) s 21 r (and) s 21 r (Scheduling) s 21 r (Issues) s 21 r (for) s 21 r (Multiprogrammed) s 21 r (Shared) s 98 1076 p (Memory) s 19 r (Multiprocessors,) s 0 r 186 c 19 r (in) s @P37 @sfps 18 r (Pr) s 0 r (oceedings) s 17 r (of) s 19 r (the) s 18 r 84 c -2 r (welfth) s 17 r (ACM) s 18 r (Symposium) s 19 r (on) s 18 r (Operating) s 19 r (Systems) s 98 1132 p (Principles) s @P33 @sfps 0 r 44 c 16 r (December) s 15 r (1989.) s 0 1207 p ([10]) s 23 r 87 c -3 r 46 c 12 r (A.) s 14 r 87 c -1 r (ulf,) s 13 r (R.) s 14 r (Levin,) s 14 r (and) s 14 r (S.) s 14 r 80 c -4 r 46 c 13 r (Harbison,) s @P37 @sfps 14 r (Hydra/C.mmp:) s 19 r (An) s 14 r (Experimental) s 14 r (Computer) s 14 r (System) s @P33 @sfps 0 r 46 c 19 r (New) s 98 1264 p 89 c -3 r (ork,) s 14 r (NY) s -3 r 58 c 14 r (McGraw-Hill,) s 15 r (1981.) s 2 1339 p ([1) s -1 r (1]) s 22 r (E.) s 11 r 70 c -3 r 46 c 10 r (Gehringer) s -1 r 44 c 11 r (D.) s 11 r 80 c -4 r 46 c 10 r (Siewiorek,) s 12 r (and) s 11 r (Z.) s 11 r (Segall,) s @P37 @sfps 12 r (Parallel) s 11 r (Pr) s -1 r (ocessing:) s 17 r (The) s 11 r (Cm*) s 11 r (Experience) s @P33 @sfps 0 r 46 c 19 r (Maynard,) s 98 1395 p (MA:) s 16 r (Digital) s 15 r (Press,) s 15 r (1987.) s 0 1470 p ([12]) s 23 r (H.) s 20 r (Jacobs,) s 22 r 170 c 0 r 65 c 21 r (User) s 0 r (-tunable) s 19 r (Multiple) s 21 r (Processor) s 20 r (Scheduler) s -1 r 44 c 0 r 186 c 21 r (in) s @P37 @sfps 21 r (1986) s 20 r (USENIX) s 21 r 87 c -2 r (inter) s 20 r (Confer) s -1 r (ence) s 98 1527 p (Pr) s 0 r (oceedings) s @P33 @sfps 0 r 44 c 14 r (January) s 15 r (1986.) s 951 2843 p (16) s @eop @end (\nEND-JOB 0 scheduling.dvi\n) print flush