%!PS-Adobe-2.0
%%Title: final.mss
%%DocumentFonts: (atend)
%%Creator: Indira Subramanian and Scribe 7(1700)
%%CreationDate: 7 October 1991 20:09
%%Pages: (atend)
%%EndComments
% PostScript Prelude for Scribe.
/BS {/SV save def 0.0 792.0 translate .01 -.01 scale} bind def
/ES {showpage SV restore} bind def
/SC {setrgbcolor} bind def
/FMTX matrix def
/RDF {WFT SLT 0.0 eq 
  {SSZ 0.0 0.0 SSZ neg 0.0 0.0 FMTX astore}
  {SSZ 0.0 SLT neg sin SLT cos div SSZ mul SSZ neg 0.0 0.0 FMTX astore}
  ifelse makefont setfont} bind def
/SLT 0.0 def
/SI { /SLT exch cvr def RDF} bind def
/WFT /Courier findfont def
/SF { /WFT exch findfont def RDF} bind def
/SSZ 1000.0 def
/SS { /SSZ exch 100.0 mul def RDF} bind def
/AF { /WFT exch findfont def /SSZ exch 100.0 mul def RDF} bind def
/MT /moveto load def
/XM {currentpoint exch pop moveto} bind def
/UL {gsave newpath moveto dup 2.0 div 0.0 exch rmoveto
   setlinewidth 0.0 rlineto stroke grestore} bind def
/LH {gsave newpath moveto setlinewidth
   0.0 rlineto
   gsave stroke grestore} bind def
/LV {gsave newpath moveto setlinewidth
   0.0 exch rlineto
   gsave stroke grestore} bind def
/BX {gsave newpath moveto setlinewidth
   exch
   dup 0.0 rlineto
   exch 0.0 exch neg rlineto
   neg 0.0 rlineto
   closepath
   gsave stroke grestore} bind def
/BX1 {grestore} bind def
/BX2 {setlinewidth 1 setgray stroke grestore} bind def
/PB {/PV save def newpath translate
    100.0 -100.0 scale pop /showpage {} def} bind def
/PE {PV restore} bind def
/GB {/PV save def newpath translate rotate
    div dup scale 100.0 -100.0 scale /showpage {} def} bind def
/GE {PV restore} bind def
/FB {dict dup /FontMapDict exch def begin} bind def
/FM {cvn exch cvn exch def} bind def
/FE {end /original-findfont /findfont load def  /findfont
   {dup FontMapDict exch known{FontMapDict exch get} if
   original-findfont} def} bind def
/BC {gsave moveto dup 0 exch rlineto exch 0 rlineto neg 0 exch rlineto closepath clip} bind def
/EC /grestore load def
/SH /show load def
/MX {exch show 0.0 rmoveto} bind def
/W {0 32 4 -1 roll widthshow} bind def
/WX {0 32 5 -1 roll widthshow 0.0 rmoveto} bind def
/RC {100.0 -100.0 scale
612.0 0.0 translate
-90.0 rotate
.01 -.01 scale} bind def
/URC {100.0 -100.0 scale
90.0 rotate
-612.0 0.0 translate
.01 -.01 scale} bind def
/RCC {100.0 -100.0 scale
0.0 -792.0 translate 90.0 rotate
.01 -.01 scale} bind def
/URCC {100.0 -100.0 scale
-90.0 rotate 0.0 792.0 translate
.01 -.01 scale} bind def
%%EndProlog
%%Page: 0 1
BS
0 SI
15 /Times-Bold AF
13682 8205 MT
(Managing Discardable Pages with an External Pager)SH
12 /Times-Italic AF
25716 13400 MT
(Indira Subramanian)SH
17882 14668 MT
(Department of Electrical and Computer Engineering)SH
23865 15936 MT
(Carnegie Mellon University)SH
22882 17204 MT
(Pittsburgh, Pennsylvania 15213)SH
23664 19740 MT
(Internet: indira@cs.cmu.edu)SH
13 /Times-Bold AF
28181 23099 MT
(Abstract)SH
10 /Times-Roman AF
9000 25472 MT
(We have)
447 W( designed and implemented an)448 W
/Times-Italic SF
27628 XM
(external pager)448 W
/Times-Roman SF
34634 XM
(that: \0501\051 receives information regarding)448 W
9000 26577 MT
(discardability of pages from the client such)
77 W( as a garbage collector for functional programming languages,)76 W
9000 27682 MT
(\0502\051 saves and restores only)
179 W( non-discardable pages and \0503\051 influences page-replacement by pre-flushing)180 W
9000 28787 MT
(discardable pages.  In a general purpose operating system dirty pages are typically saved to)
68 W( disk and then)67 W
9000 29892 MT
(restored from disk even when the application may not)
11 W( care about the contents of those pages.  For example,)12 W
9000 30997 MT
(copying garbage)
49 W( collection used in functional programming languages generates many pages that are dirty)48 W
9000 32102 MT
(but discardable.  Using the external pager)
42 W( to manage the discardable pages we observed that elapsed times)43 W
9000 33207 MT
(for some applications decreased by as much as a factor of 6.)SH
12 /Times-Bold AF
9000 36891 MT
(1. Introduction)SH
10 /Times-Roman AF
10000 38608 MT
(Saving and restoring discardable dirty pages causes unnecessary disk traffic,)
94 W( thus preventing computer)93 W
9000 39713 MT
(systems from achieving the best possible performance.  An application)
143 W( may modify one or more pages)144 W
9000 40818 MT
(during the course of its execution.)
70 W( At)
388 W( subsequent points of execution, the application may not care about)69 W
9000 41923 MT
(the contents of some of these modified \050dirty\051 pages. We refer to these)
25 W( modified pages as)26 W
/Times-Italic SF
45313 XM
(discardable dirty)26 W
/Times-Roman SF
9000 43028 MT
(pages. The)
438 W( ratio between the average access time of magnetic)
94 W( disk and the average access time of main)93 W
9000 44133 MT
(memory is often between)
139 W( 2,500 and 70,000)
140 W( [Gibson)
SH( 90].  Hence, saving and restoring discardable dirty)140 W
9000 45238 MT
(pages would undermine the throughput of a computer system.)SH
10000 47445 MT
(One of the applications that can take advantage of discardable page management is copying)
150 W( garbage)149 W
9000 48550 MT
(collection. In)
394 W( systems that use copying garbage collection, such as the one described in)
72 W( [Appel)
SH( 89], heap)72 W
9000 49655 MT
(space is partioned into a)54 W
/Times-Italic SF
19185 XM
(new)SH
/Times-Roman SF
(,)SH
/Times-Italic SF
21349 XM
(old)SH
/Times-Roman SF
22930 XM
(and)SH
/Times-Italic SF
24677 XM
(reserved)SH
/Times-Roman SF
28423 XM
(regions. Allocations are made out of the new space. When)53 W
9000 50760 MT
(the new space is exhausted, a)25 W
/Times-Italic SF
21119 XM
(minor)SH
/Times-Roman SF
23783 XM
(collection phase is initiated.)
25 W( During)
301 W( the minor collection,)26 W
/Times-Italic SF
47317 XM
(live)SH
/Times-Roman SF
49037 XM
(data are)26 W
9000 51865 MT
(copied from the new)
67 W( space to the reserved space, which immediately follows the old data. The old region)66 W
9000 52970 MT
(continues to grow into the reserved region. Once)
82 W( the old region reaches a certain size, a)83 W
/Times-Italic SF
45534 XM
(major)SH
/Times-Roman SF
48256 XM
(collection)SH
9000 54075 MT
(phase is initiated.  During the major phase, the live data)
33 W( from the old region is copied to another region \050in)32 W
9000 55180 MT
(the heap\051, which becomes)
111 W( the old region from then on. At the end of each minor and major collections,)112 W
9000 56285 MT
(several pages become discardable.  Examples of systems that use copying garbage collection are:  SML/NJ)25 W
9000 57390 MT
(garbage collector)
34 W( [Appel)
SH( and MacQueen 87], and the CMU Common)
34 W( LISP garbage collector)
35 W( [MacLachlan)SH
9000 58495 MT
(91].)SH
10000 60702 MT
(Another application domain that can benefit from support for discardable pages is image)
172 W( processing)171 W
9000 61807 MT
(\050e.g., image restoration,)
188 W( image compression, and texture synthesis\051.  Texture synthesis is an important)189 W
9000 62912 MT
(component of computer graphics as well as)
182 W( image compression.  One of the techniques that has been)181 W
9000 64017 MT
(developed for texture synthesis is a two stage procedure)
42 W( [Balram)
SH( 91] involving matrix computations.  This)43 W
9000 65122 MT
(technique generates several intermediate matrices that become discardable.  For)
23 W( example, consider the case)22 W
10800 50 9000 67580 UL
8 SS 
9800 69228 MT
(This research was sponsored)
87 W( in part by The Defense Advanced Research Projects Agency, Information Science and Technology)86 W
9000 70152 MT
(Office, under the title ``Research on Parallel Computing'', ARPA Order No. 7330, issued by DARPA/CMO)
223 W( under Contract)224 W
9000 71076 MT
(MDS972-90-C-0035. The)
240 W( views and conclusions contained in this document are those of the authors and should not be)
20 W( interpreted as)19 W
9000 72000 MT
(representing the official policies, either expressed or implied, of DARPA, or the U.S. government.)SH
ES
%%Page: 1 2
BS
0 SI
10 /Times-Roman AF
9000 7886 MT
(where a typical image represented as a 512x512 double precision)
28 W( matrix is to be synthesised. At the end of)29 W
9000 8991 MT
(the first stage, there will be 26 512x512 matrices of double precision)
4 W( data, of which 20 matrices are input to)3 W
9000 10096 MT
(the second)
302 W( stage and 6 matrices become discardable.  Hence, in the first stage, the total memory)303 W
9000 11201 MT
(requirement is 52 megabytes of which 12 megabytes)
57 W( are discardable. In the second stage, there will be 21)56 W
9000 12306 MT
(matrices, of which 20 are from the first stage and)
29 W( 1 matrix is the output matrix of the second stage.  As the)30 W
9000 13411 MT
(iterations in the second stage proceed, each of the)
194 W( 20 input matrices become discardable. Support for)193 W
9000 14516 MT
(managing discardable pages is)
132 W( important since images can be even larger.  The ability to discard pages)133 W
9000 15621 MT
(would also be useful in applications such as smoothing of noisy)
244 W( images, where a similar two stage)243 W
9000 16726 MT
(procedure is used.)SH
10000 18933 MT
(In Mach, the)
3 W( vm_allocate and vm_deallocate calls can be used to map or unmap pages in a task's address)4 W
9000 20038 MT
(space [Rashid)
SH( et. al. 88].  The vm_deallocate call could be used to unmap the pages that an)
125 W( application)124 W
9000 21143 MT
(would like to discard. However, the physical pages get freed only if)
287 W( an entire object allocated by)288 W
9000 22248 MT
(vm_allocate is being deallocated \050by the vm_deallocate\051. If only a part of an object is deallocated,)
1 W( the pages)SH
9000 23353 MT
(are unmapped from the client's address space, but they remain)
25 W( as part of the object.  Hence, vm_deallocate)26 W
9000 24458 MT
(does not discard the pages unless a client deallocates an entire object.  In fact,)
220 W( the copying garbage)219 W
9000 25563 MT
(collector in CMU Common)
63 W( Lisp uses the vm_allocate call to allocate the new region; at the end of minor)64 W
9000 26668 MT
(collection, this new region is)
83 W( deallocated by vm_deallocate call.  Even modifying the kernel to solve this)82 W
9000 27773 MT
(problem introduces)
66 W( additional difficulties because repeated vm_deallocates and vm_allocates can result in)67 W
9000 28878 MT
(the fragmentation of a memory object, degrading memory management performance.)SH
10000 31085 MT
(To the best of our knowledge, general purpose operating systems do not)
51 W( provide support for identifying)50 W
9000 32190 MT
(discardable dirty pages as such and for avoiding the unnecessary saving and restoring of those pages.)SH
12 /Times-Bold AF
9000 35874 MT
(2. Solution)SH
10 /Times-Roman AF
10000 37591 MT
(Our solution is to exploit the knowledge about discardable pages in an)
82 W( application's address space and)83 W
9000 38696 MT
(avoid unnecessary saving and restoring of those)
46 W( pages.  Many applications, such as garbage collectors and)45 W
9000 39801 MT
(image processing systems know)
113 W( what pages are discardable at any point in time. These applications can)114 W
9000 40906 MT
(communicate this information to the operating system.)SH
10000 43113 MT
(We have implemented under)
2 W( the Mach Operating System)
1 W( [Tevanian)
SH( 87a], a pager that facilitates efficient)1 W
9000 44218 MT
(management of discardable pages.  Mach allows the user to create)27 W
/Times-Italic SF
36012 XM
(memory objects)27 W
/Times-Roman SF
42593 XM
([Tevanian 87b] that)
27 W( can)28 W
9000 45323 MT
(be managed by a user-level process, called the)130 W
/Times-Italic SF
28839 XM
(external pager)129 W
/Times-Roman SF
35078 XM
([Young et. al. 87].  Through the external)129 W
9000 46428 MT
(pager, a client may create an object and request that the kernel map the object into its address)
2 W( space.  Figure)3 W
9000 47533 MT
(2-1 summarizes the interaction between the kernel, the pager and a client.)SH
11 /Times-Bold AF
9000 51150 MT
(2.1. The Page Attribute Bitmap)SH
10 /Times-Roman AF
10000 52846 MT
(The information regarding the discardability)
79 W( of pages in the memory object created by)78 W
/Times-Italic SF
45817 XM
(ObjectCreate)SH
/Times-Roman SF
51533 XM
(is)SH
9000 53951 MT
(maintained in a bitmap shared between the client and the pager.)
113 W( This state information is written by the)114 W
9000 55056 MT
(client and read by the pager; it contains one bit per page, indicating that the page is in one of two states:)SH
/Symbol SF
10790 56509 MT
(\267)SH
/Times-Roman SF
11500 XM
(non-discardable - when paged out by the kernel,)
50 W( the pager must save the contents of this page)49 W
11500 57614 MT
(to backing storage; when paging)
66 W( in, the pager must retrieve the contents of the page from the)67 W
11500 58719 MT
(backing storage)SH
/Symbol SF
10790 60477 MT
(\267)SH
/Times-Roman SF
11500 XM
(discardable - when)
59 W( paged out by the kernel, the pager may discard this page; when paging in,)58 W
11500 61582 MT
(the contents of the page are irrelevant to the client)SH
10000 63789 MT
(The page attribute bitmap, also called)
18 W( the)19 W
/Times-Italic SF
26903 XM
(attribute object)19 W
/Times-Roman SF
(, is itself a memory object created by the pager.)19 W
9000 64894 MT
(The memory object whose pages will be managed by the)
124 W( pager, is called the)123 W
/Times-Italic SF
41475 XM
(primary object)123 W
/Times-Roman SF
(. A)
496 W( call to)123 W
/Times-Italic SF
9000 65999 MT
(ObjectCreate)SH
/Times-Roman SF
14661 XM
(returns two)
23 W( ports, one for the primary object and the other for the attribute object.  The client)24 W
9000 67104 MT
(then maps the primary object into its address space by calling)55 W
/Times-Italic SF
34462 XM
(vm_map)SH
/Times-Roman SF
(, which results in the kernel calling)54 W
/Times-Italic SF
9000 68209 MT
(memory_object_init)SH
/Times-Roman SF
(. In)28 W
/Times-Italic SF
18639 XM
(memory_object_init)SH
/Times-Roman SF
(, the pager maps the attribute object into pager's address space.)29 W
9000 69314 MT
(Upon returning from)210 W
/Times-Italic SF
18212 XM
(vm_map)SH
/Times-Roman SF
(, the client calls)210 W
/Times-Italic SF
28967 XM
(vm_map)SH
/Times-Roman SF
32815 XM
(again to map the attribute object into client's)210 W
9000 70419 MT
(address space. In this manner, the attribute object is shared between the)
61 W( client and the pager. The primary)62 W
9000 71524 MT
(object and the attribute object are managed by two different threads running within the)
159 W( pager to avoid)158 W
ES
%%Page: 2 3
BS
0 SI
10 SS 
1 1 0 250 68300 GB 
%%BeginDocument: fig1.ps
%!PS-Adobe-2.0 EPSF-1.2
%%DocumentFonts: Courier-Bold Times-Roman
%%%Pages: 1
%%BoundingBox: 129 347 478 611
%%EndComments

50 dict begin

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

/Begin {
save
numGraphicParameters dict begin
} def

/End {
end
restore
} def

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

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

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

/SetF {
/printSize idef
/printFont idef
} def

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

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

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

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

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

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

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

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

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

/Text {
ishow
} def

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

%%EndProlog

%I Idraw 7 Grid 8 

%%%Page: 1 1

Begin
%I b u
%I cfg u
%I cbg u
%I f u
%I p u
%I t
[ 0.923077 0 0 0.923077 0 0 ] concat
/originalCTM matrix currentmatrix def

Begin %I Elli
%I b 65535
2 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
1 SetP
%I t
[ 1 0 0 1 65.75 140.75 ] concat
%I
242 487 65 31 Elli
End

Begin %I Elli
%I b 65535
2 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
1 SetP
%I t
[ 1 0 0 1 60.75 133.75 ] concat
%I
137 378 54 31 Elli
End

Begin %I Elli
%I b 65535
2 0 0 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
1 SetP
%I t
[ 1.048 0 0 1.05797 58.774 111.62 ] concat
%I
373 382 62 34 Elli
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-courier-bold-r-*-120-*
/Courier-Bold 12 SetF
%I t
[ 1 0 0 1 171.75 519.75 ] concat
%I
[
(Client)
()
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-courier-bold-r-*-120-*
/Courier-Bold 12 SetF
%I t
[ 1 0 0 1 181.75 505.75 ] concat
%I
[
(Task)
()
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-courier-bold-r-*-120-*
/Courier-Bold 12 SetF
%I t
[ 1 0 0 1 280.75 632.75 ] concat
%I
[
(Kernel)
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-courier-bold-r-*-120-*
/Courier-Bold 12 SetF
%I t
[ 1 0 0 1 402.75 526.75 ] concat
%I
[
(External Pager)
()
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-courier-bold-r-*-120-*
/Courier-Bold 12 SetF
%I t
[ 1 0 0 1 434.75 512.75 ] concat
%I
[
(Task)
] Text
End

Begin %I Rect
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
1 SetP
%I t
[ 1 0 0 1 68.75 134.75 ] concat
%I
200 245 306 295 Rect
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-times-medium-r-*-120-*
/Times-Roman 12 SetF
%I t
[ 1 0 0 1 306 399 ] concat
%I
[
(Bitmap)
] Text
End

Begin %I Line
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 1 0 0 1 97 131 ] concat
%I
143 363 216 301 Line
End

Begin %I Line
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 1 0 0 1 97 131 ] concat
%I
157 381 286 381 Line
End

Begin %I Line
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 1 0 0 1 97 131 ] concat
%I
103 411 164 474 Line
End

Begin %I Line
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 1 0 0 1 97 131 ] concat
%I
298 366 232 300 Line
End

Begin %I Line
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 1 0 0 1 97 131 ] concat
%I
336 419 272 483 Line
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-times-medium-r-*-120-*
/Times-Roman 12 SetF
%I t
[ 1 0 0 1 382 408 ] concat
%I
[
(\(Shared Memory\))
()
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-times-medium-r-*-120-*
/Times-Roman 12 SetF
%I t
[ 1 0 0 1 269 550 ] concat
%I
[
(ObjectCreate)
(ObjectDestroy)
(FlushDiscardable)
()
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-times-medium-r-*-120-*
/Times-Roman 12 SetF
%I t
[ 1 0 0 1 184 600 ] concat
%I
[
(vm_map)
()
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-times-medium-r-*-120-*
/Times-Roman 12 SetF
%I t
[ 1 0 0 1 156 585 ] concat
%I
[
(vm_deallocate)
()
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-times-medium-r-*-120-*
/Times-Roman 12 SetF
%I t
[ 1 0 0 1 232 468 ] concat
%I
[
(write)
()
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-times-medium-r-*-120-*
/Times-Roman 12 SetF
%I t
[ 1 0 0 1 374 466 ] concat
%I
[
(read)
()
] Text
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-times-medium-r-*-120-*
/Times-Roman 12 SetF
%I t
[ 1 0 0 1 288 413 ] concat
%I
[
(Page Attribute)
] Text
End

Begin %I Line
%I b 65535
1 0 1 [] 0 SetB
%I cfg Black
0 0 0 SetCFg
%I cbg White
1 1 1 SetCBg
%I p
0 SetP
%I t
[ 1 0 0 1 97 131 ] concat
%I
256 473 314 416 Line
End

Begin %I Text
%I cfg Black
0 0 0 SetCFg
%I f *-times-medium-r-*-120-*
/Times-Roman 12 SetF
%I t
[ 1 0 0 1 402 600 ] concat
%I
[
(\(see Appendix I\))
] Text
End

End %I eop

showpage

%%Trailer

end

%%EndDocument
 GE /Times-Bold SF
9000 35375 MT
(Client to Kernel)SH
6888 50 9000 35575 UL
/Times-Italic SF
9000 36952 MT
(vm_map)SH
/Times-Roman SF
17000 XM
(maps a memory object into client's address space)SH
/Times-Italic SF
9000 38529 MT
(vm_deallocate)SH
/Times-Roman SF
17000 XM
(unmaps a specified range of pages from clients address space)SH
/Times-Bold SF
9000 41409 MT
(Client to Pager)SH
6443 50 9000 41609 UL
/Times-Italic SF
9000 42986 MT
(ObjectCreate)SH
/Times-Roman SF
17000 XM
(creates a memory object)SH
/Times-Italic SF
9000 44563 MT
(ObjectDestroy)SH
/Times-Roman SF
17000 XM
(terminates a memory object)SH
/Times-Italic SF
9000 46140 MT
(FlushDiscardable)SH
/Times-Roman SF
17000 XM
(flushes all discardable pages in a memory object)SH
/Times-Bold SF
19199 47931 MT
(Figure 2-1:)SH
/Times-Roman SF
24448 XM
(Interactions: Messages and Shared Memory)SH
9000 49722 MT
(deadlock.)SH
11 /Times-Bold AF
9000 53339 MT
(2.2. Improving Paging Performance: Pre-flushing Strategy)SH
10 /Times-Roman AF
10000 55035 MT
(The pager achieves significant performance gains in two)
113 W( ways.  First, by using the information in the)114 W
9000 56140 MT
(shared bitmap, it can avoid saving and restoring discardable pages. Second, it can pre-flush)
136 W( discardable)135 W
9000 57245 MT
(pages, allowing non-discardable pages to remain)
157 W( in memory for longer periods.  This further improves)158 W
9000 58350 MT
(performance because it is much less expensive to flush several discardable pages than to)
173 W( write a non-)172 W
9000 59455 MT
(discardable page to)
61 W( backing store, and to read that page back in later.  By default, the Mach kernel uses a)62 W
9000 60560 MT
(global page replacement policy based on a modified First-In-First-Out strategy, which does not take into)100 W
9000 61665 MT
(consideration whether a dirty)
265 W( page is discardable or not.  We use two approaches for pre-flushing:)266 W
/Times-Italic SF
9000 62770 MT
(user-initiated)SH
/Times-Roman SF
14639 XM
(and)SH
/Times-Italic SF
16333 XM
(pager-initiated)SH
/Times-Roman SF
(.)SH
10000 64977 MT
(In the user-initiated pre-flushing technique)
7 W( the client task, sets up the page attribute bitmap and explicitly)6 W
9000 66082 MT
(requests the pager to flush discardable pages by calling FlushDiscardable. The pager)
409 W( then calls)410 W
/Times-Italic SF
9000 67187 MT
(memory_object_lock_request)SH
/Times-Roman SF
21025 XM
(to flush all the pages that are marked discardable.)SH
10000 69394 MT
(In the pager-initiated pre-flushing technique, the pager calls)206 W
/Times-Italic SF
35837 XM
(memory_object_lock_request)SH
/Times-Roman SF
48068 XM
(to flush a)205 W
9000 70499 MT
(predefined number)
11 W( of discardable pages when it receives a)12 W
/Times-Italic SF
32794 XM
(memory_object_data_write)SH
/Times-Roman SF
44055 XM
(call from the kernel.)12 W
9000 71604 MT
(This is an appropriate time to flush discardable pages)
658 W( because if the kernel is making)657 W
ES
%%Page: 3 4
BS
0 SI
10 /Times-Italic AF
9000 7886 MT
(memory_object_data_write)SH
/Times-Roman SF
20435 XM
(calls, physical memory must be tight.  In the current implementation, each)186 W
9000 8991 MT
(time, the pager makes flush requests to flush 64 pages.  We chose 64)
184 W( because pre-flushing too many)183 W
9000 10096 MT
(discardable pages could add to the execution time; pre-flushing too few pages would mean that)
58 W( the kernel)59 W
9000 11201 MT
(could pageout non-discardable pages.  At this time, we have not)
81 W( experimented with values other than 64.)80 W
9000 12306 MT
(The pager refrains)
214 W( from making flush requests if there are acknowledgements pending from previous)215 W
/Times-Italic SF
9000 13411 MT
(memory_object_lock_request)SH
/Times-Roman SF
21025 XM
(calls.)SH
10000 15618 MT
(When the pre-flushing)
40 W( technique is being used, the client and the pager need to synchronize their access)39 W
9000 16723 MT
(to the page attribute bitmap.  A single lock is used for this purpose.  The)
99 W( pager acquires the lock before)100 W
9000 17828 MT
(making one or more flush requests to the kernel and releases)
76 W( the lock after it receives acknowledgements)75 W
9000 18933 MT
(from the kernel for)
25 W( all of the requests. The client acquires the lock when it needs to change the state of one)26 W
9000 20038 MT
(or more pages)
200 W( from discardable to non-discardable and then releases it.  Note that when pre-flushing)199 W
9000 21143 MT
(technique is not being used, access to the page attribute bitmap need not be synchronized.)SH
12 /Times-Bold AF
9000 24827 MT
(3. Evaluation)SH
10 /Times-Roman AF
10000 26544 MT
(Performance measurements of discardable)
239 W( page management by an external pager is important for)240 W
9000 27649 MT
(answering three questions:  First, are there significant performance gains to be realised even)
104 W( if only in a)103 W
9000 28754 MT
(small number of important applications? Second, how many applications can benefit from support for)191 W
9000 29859 MT
(discardable page management? Third, should the support)
226 W( for discardable page management be in the)225 W
9000 30964 MT
(kernel, or in an external pager?  The first and second questions will be answered)
5 W( as we build our experience)6 W
9000 32069 MT
(with performance of applications such as the)
26 W( ones discussed in section 1.  Even if the performance benefits)25 W
9000 33174 MT
(from an in-kernel implementation are greater than from an external pager, we need)
22 W( to be convinced that \050a\051)23 W
9000 34279 MT
(an in-kernel implementation is simple \050b\051 there are enough applications)
403 W( to warrant an in-kernel)402 W
9000 35384 MT
(implementation. In)
352 W( this section, we will present some data on the performance measurements we)
51 W( made in)52 W
9000 36489 MT
(the context of a copying garbage collector.)SH
11 /Times-Bold AF
9000 40106 MT
(3.1. Experimental Setup)SH
10 /Times-Roman AF
10000 41802 MT
(The measurements that are reported here were made on a)
104 W( Digital Equipment Corporation's Decstation)103 W
9000 42907 MT
(5000/200 with 24 megabytes of physical memory, running Mach)
2 W( version 2.5. This is a typical configuration)3 W
9000 44012 MT
(in our environment.  For the purpose)
4 W( of running the tests, the machine was booted in single user mode.  The)3 W
9000 45117 MT
(only other programs running were a nameserver and)
122 W( the external pager. The nameserver is used only at)123 W
9000 46222 MT
(client startup, to look up the external pager service port.  Hence for all practical purposes, only the)
78 W( client)77 W
9000 47327 MT
(and the external pager were running in the system.)SH
10000 49534 MT
(We ran four configurations: \050a\051 without pager, \050b\051 with pager, not using pre-flushing, \050c\051 with pager,)138 W
9000 50639 MT
(using pager-initiated pre-flushing,)
363 W( and \050d\051 with pager, using user-initiated pre-flushing.  They are)362 W
9000 51744 MT
(summarized in table 3-1.  In each test case, each of the four configurations were run 6 times. The average)55 W
9000 52849 MT
(measurements are being reported in the performance tables.  The entries in the performance tables are)166 W
9000 53954 MT
(described in table 3-2.)SH
/Times-Italic SF
16703 56144 MT
(NoPager)SH
/Times-Roman SF
21278 XM
(run without the external pager)SH
28592 50 16304 56762 LH BX1
/Times-Italic SF
16703 57847 MT
(PagerNF)SH
/Times-Roman SF
21278 XM
(run with the pager, without pre-flushing)SH
28592 50 16304 58465 LH BX1
/Times-Italic SF
16703 59550 MT
(PagerPF)SH
/Times-Roman SF
21278 XM
(run with the pager, using pager-initiated pre-flushing only)SH
28592 50 16304 60168 LH BX1
/Times-Italic SF
16703 61253 MT
(PagerUF)SH
/Times-Roman SF
21278 XM
(run with the pager, using user-initiated pre-flushing only)SH
28592 6812 50 16304 61871 BX BX1
-6812 50 20879 61871 LV BX1
/Times-Bold SF
25169 63481 MT
(Table 3-1:)SH
/Times-Roman SF
30030 XM
(Configurations)SH
11 /Times-Bold AF
9000 67098 MT
(3.2. Performance Measurements)SH
10 /Times-Roman AF
10000 68794 MT
(Two test cases written in Standard)
239 W( ML)
240 W( [Milner)
SH( et.al. 90] were studied: \050a\051 compiling parts of the)240 W
9000 69899 MT
(SML/NJ compiler and \050b\051 a sort program.  Modifications were made to the ML garbage collector to use our)10 W
9000 71004 MT
(external pager to create and manage the heap memory.)SH
ES
%%Page: 4 5
BS
0 SI
10 /Times-Italic AF
14302 8285 MT
(Time)SH
/Times-Roman SF
22099 XM
(shown in minutes:seconds)SH
33394 50 13903 8903 LH BX1
/Times-Italic SF
14302 9988 MT
(Pageins:Read)SH
/Times-Roman SF
22099 XM
(number of pages read from disk)SH
33394 50 13903 10606 LH BX1
/Times-Italic SF
14302 11691 MT
(Pageins:NoRead)SH
/Times-Roman SF
22099 XM
(number of discarded pages returned to client as zero-filled)SH
33394 50 13903 12309 LH BX1
/Times-Italic SF
14302 13394 MT
(Pageouts:Write)SH
/Times-Roman SF
22099 XM
(number of non-discardable pages written to disk)SH
33394 50 13903 14012 LH BX1
/Times-Italic SF
14302 15097 MT
(Pageous:Discard)SH
/Times-Roman SF
22099 XM
(number of discardable pages written to pager)SH
33394 50 13903 15715 LH BX1
/Times-Italic SF
14302 16800 MT
(Pageouts:Flush)SH
/Times-Roman SF
22099 XM
(number of discardable pages requested of kernel to be flushed)SH
33394 10218 50 13903 17418 BX BX1
-10218 50 21700 17418 LV BX1
/Times-Bold SF
23962 19028 MT
(Table 3-2:)SH
/Times-Roman SF
28823 XM
(Performance Metrics)SH
10000 21235 MT
(Besides exploiting)
227 W( support for discardable page management, the ML garbage collector does some)228 W
9000 22340 MT
(memory management)
65 W( of its own.  It takes a set of parameters called)64 W
/Times-Italic SF
37105 XM
(gc)SH
/Times-Roman SF
38363 XM
(parameters, that help maintain the)64 W
9000 23445 MT
(working set pertaining)
74 W( to the heap within the available physical memory)
75 W( [Cooper)
SH( and Nettles 91]. The gc)75 W
9000 24550 MT
(parameters have effect on how frequently minor and major collections happen. On a 24)
16 W( megabyte machine,)15 W
9000 25655 MT
(different combinations of gc parameters could result in variations in the elapsed time)
4 W( of a given application.)5 W
9000 26760 MT
(Details regarding the impacts of gc parameters are beyond the scope of this)
127 W( paper.  Cooper and Nettles)126 W
9000 27865 MT
(report significant performance improvements running ML applications)
127 W( with various gc parameters when)128 W
9000 28970 MT
(using our pager [Cooper and Nettles 91].)SH
10000 31177 MT
(Performance measurements for the compiler are shown in table 3-3.  We observe that:)SH
11000 32516 MT
(1.)SH
12000 XM
(The elapsed time when not using the pager is)
116 W( significantly larger than the user and system)115 W
12000 33621 MT
(times \050i.e., the CPU utilization is low\051. As we introduce the pager and then)
82 W( the pre-flushing)83 W
12000 34726 MT
(techniques, the CPU utilization increases, due to reduced disk accesses.)SH
11000 36484 MT
(2.)SH
12000 XM
(When using the pager without pre-flushing, the number of reads and)
140 W( writes is higher than)139 W
12000 37589 MT
(with user or pager initiated pre-flushing. This is because in both)
193 W( the pre-flush cases, the)194 W
12000 38694 MT
(kernel is able to retain more non-discardable pages.)SH
21828 41375 MT
(Time)SH
30124 XM
(Pageins)SH
43074 XM
(Pageouts)SH
35184 50 16287 41993 LH BX1
10128 43078 MT
(Configuration)SH
17542 XM
(User)SH
21411 XM
(System)SH
25699 XM
(Elapsed)SH
30652 XM
(Read)SH
34439 XM
(NoRead)SH
39337 XM
(Write)SH
43319 XM
(Discard)SH
48160 XM
(Flush)SH
41742 50 9729 43696 LH BX1
10128 44781 MT
(NoPager)SH
17597 XM
(2:49)SH
21995 XM
(0:16)SH
26143 XM
(16:00)SH
30430 XM
(22792)SH
35217 XM
(N/A)SH
39226 XM
(21693)SH
44013 XM
(N/A)SH
48411 XM
(N/A)SH
41742 50 9729 45399 LH BX1
10128 46484 MT
(PagerNF)SH
17597 XM
(2:51)SH
21995 XM
(0:17)SH
26393 XM
(8:01)SH
30680 XM
(6594)SH
34828 XM
(15516)SH
39476 XM
(6525)SH
43624 XM
(18813)SH
48411 XM
(N/A)SH
41742 50 9729 47102 LH BX1
10128 48187 MT
(PagerPF)SH
17597 XM
(2:45)SH
21995 XM
(0:18)SH
26393 XM
(3:56)SH
30930 XM
(710)SH
34828 XM
(24755)SH
39726 XM
(710)SH
44124 XM
(425)SH
48022 XM
(27899)SH
41742 50 9729 48805 LH BX1
10128 49890 MT
(PagerUF)SH
17597 XM
(2:49)SH
21995 XM
(0:22)SH
26393 XM
(5:18)SH
30680 XM
(2861)SH
34828 XM
(33051)SH
39476 XM
(2861)SH
43874 XM
(1720)SH
48022 XM
(36233)SH
41742 10709 50 9729 50508 BX BX1
/Times-Bold SF
17322 52118 MT
(Table 3-3:)SH
/Times-Roman SF
22183 XM
(Measurements: Compiling Parts of SML/NJ Compiler)SH
10000 54325 MT
(The elapsed time for pager-initiated flushing is smaller than for user-initiated flushing.  This)
62 W( is because)61 W
9000 55430 MT
(the pager-initiated flush happens only when memory gets)
91 W( tight, and a small number of discardable pages)92 W
9000 56535 MT
(are pre-flushed at that time.)
26 W( The user-initiated flush, on the other hand, happens whenever the user chooses)25 W
9000 57640 MT
(to activate it, and)
163 W( the user may have marked many pages discardable. This implies that pager-initiated)164 W
9000 58745 MT
(pre-flush is more likely to track closely the memory demands in the)
1 W( system than the user-initiated pre-flush.)SH
9000 59850 MT
(However, our experience has)
SH( shown that this is not always the case.  We do not in general, have an accurate)1 W
9000 60955 MT
(knowledge of the optimal number of pages to pre-flush from outside the kernel.)
217 W( This)
682 W( is one of the)216 W
9000 62060 MT
(disadvantages of doing discardable)
17 W( page management through an external pager. In the case of an in-kernel)18 W
9000 63165 MT
(implementation, the kernel flushes a discardable page only when it is in need of more memory.)
27 W( Unlike)
303 W( the)26 W
9000 64270 MT
(external pager implementation, there can never be too few or too many flushes.)SH
10000 66477 MT
(Another test case was a sort program.  It does)
64 W( quicksort using ML futures)
65 W( [Cooper)
SH( and Morrisett 90], a)65 W
9000 67582 MT
(variant of MultiLisp futures which is a construct for)
277 W( creating tasks and synchronizing among them)276 W
9250 68687 MT
([Halstead 85].  The results are summarized in table)
224 W( 3-4.  Once again we find that using the pager,)225 W
9000 69792 MT
(particularly with pre-flushing techniques, reduces the elapsed time significantly.)
168 W( Note)
584 W( that the elapsed)167 W
9000 70897 MT
(times for pager-initiated flush and user-initiated flush are almost the same in this case.)SH
ES
%%Page: 5 6
BS
0 SI
10 /Times-Roman AF
21828 8776 MT
(Time)SH
30124 XM
(Pageins)SH
43074 XM
(Pageouts)SH
35184 50 16287 9394 LH BX1
10128 10479 MT
(Configuration)SH
17542 XM
(User)SH
21411 XM
(System)SH
25699 XM
(Elapsed)SH
30652 XM
(Read)SH
34439 XM
(NoRead)SH
39337 XM
(Write)SH
43319 XM
(Discard)SH
48160 XM
(Flush)SH
41742 50 9729 11097 LH BX1
10128 12182 MT
(NoPager)SH
17597 XM
(1:36)SH
21995 XM
(0:16)SH
26143 XM
(24:04)SH
30430 XM
(27669)SH
35217 XM
(N/A)SH
39226 XM
(27524)SH
44013 XM
(N/A)SH
48411 XM
(N/A)SH
41742 50 9729 12800 LH BX1
10128 13885 MT
(PagerNF)SH
17597 XM
(1:36)SH
21995 XM
(0:19)SH
26393 XM
(8:42)SH
30430 XM
(10969)SH
34828 XM
(13439)SH
39226 XM
(12632)SH
43624 XM
(16038)SH
48411 XM
(N/A)SH
41742 50 9729 14503 LH BX1
10128 15588 MT
(PagerPF)SH
17597 XM
(1:37)SH
21995 XM
(0:16)SH
26393 XM
(4:00)SH
30680 XM
(3981)SH
34828 XM
(18463)SH
39476 XM
(5124)SH
44124 XM
(327)SH
48022 XM
(21454)SH
41742 50 9729 16206 LH BX1
10128 17291 MT
(PagerUF)SH
17597 XM
(1:36)SH
21995 XM
(0:18)SH
26393 XM
(3:58)SH
30680 XM
(3707)SH
34828 XM
(24491)SH
39476 XM
(5149)SH
44124 XM
(620)SH
48022 XM
(28327)SH
41742 10709 50 9729 17909 BX BX1
/Times-Bold SF
19406 19519 MT
(Table 3-4:)SH
/Times-Roman SF
24267 XM
(Measurements: Sorting using futures in ML)SH
12 /Times-Bold AF
9000 23203 MT
(4. Related Work)SH
10 /Times-Roman AF
10000 24920 MT
(Another example of an external pager is the PREMO pager)
94 W( [McNamee)
SH( and)
94 W( Armstrong 90]. This work)95 W
9000 26025 MT
(extends the)
137 W( external pager interface to implement user-level paging policies.  The kernel is modified to)136 W
9000 27130 MT
(supply the PREMO pager information on the state)
9 W( \050such as modified, referenced etc.\051 of physical pages and)10 W
9000 28235 MT
(accept from the pager the order in which the pages should be replaced.)SH
12 /Times-Bold AF
9000 31919 MT
(5. Future Work)SH
10 /Times-Roman AF
10000 33636 MT
(Managing discardable pages with an external pager has been shown to)
156 W( yield good results, especially)155 W
9000 34741 MT
(when using pre-flushing techniques. However, it)
90 W( is evident that having the information about discardable)91 W
9000 35846 MT
(pages within the kernel would have certain advantages:)SH
/Symbol SF
10790 37299 MT
(\267)SH
/Times-Roman SF
11500 XM
(Performing too many)
241 W( pre-flushes is likely to impede system performance; in the case of)240 W
11500 38404 MT
(in-kernel implementation, knowledge of physical memory availability)
34 W( would enable the kernel)35 W
11500 39509 MT
(to flush a discardable page only when necessary, thereby avoiding unnecessary zero-fills)SH
/Symbol SF
10790 41267 MT
(\267)SH
/Times-Roman SF
11500 XM
(It is possible to reduce the the number of zero-fills without compromising security.)
223 W( For)694 W
11500 42372 MT
(example, in Mach, we could let the kernel keep track)
69 W( of which task had last used a discarded)70 W
11500 43477 MT
(page in the inactive queue.  When)
163 W( a task pagefaults on a discarded page, the kernel could)162 W
11500 44582 MT
(return the discarded page in the inactive queue, which)
17 W( had previously belonged to the task thus)18 W
11500 45687 MT
(avoiding the)
111 W( need to zero-fill the page.  It is our belief that systems such as SML/NJ which)110 W
11500 46792 MT
(page heavily against their own pages and generate many)
99 W( discardable pages will benefit from)100 W
11500 47897 MT
(this approach.)SH
9000 49236 MT
(To evaluate this)
111 W( approach, we have begun an in-kernel implementation of discardable page management)110 W
9000 50341 MT
(under Mach version 3.0.)SH
12 /Times-Bold AF
9000 54025 MT
(6. Conclusion)SH
10 /Times-Roman AF
10000 55742 MT
(Given the wide disparity in the speed of primary memory and)
28 W( backing storage, it is important to manage)29 W
9000 56847 MT
(primary memory efficiently.  Physical)
111 W( memory is getting cheaper, but at the same time, we are seeing a)110 W
9000 57952 MT
(growing number)
8 W( of applications that are memory intensive.  In this paper we have demonstrated the need to)9 W
9000 59057 MT
(manage discardable pages for a certain number of applications. We are in the process of identifying other)67 W
9000 60162 MT
(applications that can benefit from support for discardable page)
6 W( management. Results from this effort and an)7 W
9000 61267 MT
(in-kernel implementation will be reported in a future paper [Subramanian 91].)SH
12 /Times-Bold AF
9000 64951 MT
(7. Acknowledgements)SH
10 /Times-Roman AF
10000 66668 MT
(I would like to thank Scott)
26 W( Nettles for getting the SML/NJ working with the pager. I would like to thank)25 W
9000 67773 MT
(Eric Cooper and Rick Rashid for suggesting the problem of discardable pages and)
30 W( for continued support in)31 W
9000 68878 MT
(pursuing further work in this area.)
43 W( I)
335 W( am grateful to Jeannette Wing and Bob Baron for allowing me to use)42 W
9000 69983 MT
(their workstations on which all the performance measurements were made.)SH
ES
%%Page: 6 7
BS
0 SI
12 /Times-Bold AF
9000 8004 MT
(Appendix I)
SH( Kernel)
600 W( - External Pager Interface)SH
10 /Times-Roman AF
10000 10081 MT
(Our external pager is functional under Mach versions 2.5 as well)
9 W( as 3.0. At the time of writing, our pager)10 W
9000 11186 MT
(uses only the Mach 2.5 Kernel - External Pager Interface.)SH
/Times-Bold SF
9000 12961 MT
(kernel to pager:)SH
/Times-Italic SF
9000 14538 MT
(memory_object_init)SH
/Times-Roman SF
17000 15643 MT
(initialise a memory object that is being mapped to a task's address space)SH
/Times-Italic SF
9000 17220 MT
(memory_object_terminate)SH
/Times-Roman SF
17000 18325 MT
(indicates that the specified memory object is no longer mapped)SH
/Times-Italic SF
9000 19902 MT
(memory_object_data_request)SH
/Times-Roman SF
17000 21007 MT
(request data from this memory object)SH
/Times-Italic SF
9000 22584 MT
(memory_object_copy)SH
/Times-Roman SF
17000 23689 MT
(indicates that a copy has been made of the specified range of the given)
1 W( original memory)SH
17000 24794 MT
(object)SH
/Times-Italic SF
9000 26371 MT
(memory_object_data_unlock)SH
/Times-Roman SF
17000 27476 MT
(request that the specified portion of the)
57 W( memory object be allowed the specified forms)56 W
17000 28581 MT
(of access)SH
/Times-Italic SF
9000 30158 MT
(memory_object_data_write)SH
/Times-Roman SF
17000 31263 MT
(write back modifications made to this portion of the memory object while in memory)SH
/Times-Italic SF
9000 32840 MT
(memory_object_lock_completed)SH
/Times-Roman SF
17000 33945 MT
(indicate that a previous memory_object_lock_request has been completed)SH
/Times-Bold SF
9000 35720 MT
(pager to kernel:)SH
/Times-Italic SF
9000 37297 MT
(memory_object_set_attributes)SH
/Times-Roman SF
17000 38402 MT
(make decisions regarding the use of the specified memory object)SH
/Times-Italic SF
9000 39979 MT
(memory_object_get_attributes)SH
/Times-Roman SF
17000 41084 MT
(retrieve attributes currently associated with an object)SH
/Times-Italic SF
9000 42661 MT
(memory_object_data_provided)SH
/Times-Roman SF
17000 43766 MT
(provide data contents of a given memory object)SH
/Times-Italic SF
9000 45343 MT
(memory_object_data_unavailable)SH
/Times-Roman SF
17000 46448 MT
(indicate that zero-fill page should be provided)SH
/Times-Italic SF
9000 48025 MT
(memory_object_lock_request)SH
/Times-Roman SF
17000 49130 MT
(indicate that the protection on a)
46 W( given range of pages be changed; may require that the)45 W
17000 50235 MT
(data be written back to the manager)SH
/Times-Italic SF
9000 51812 MT
(memory_object_data_error)SH
/Times-Roman SF
17000 52917 MT
(indicate that a range of specified memory object cannot be provided at this time)SH
/Times-Italic SF
9000 54494 MT
(memory_object_destroy)SH
/Times-Roman SF
17000 55599 MT
(indicate that the pager will no longer supply data for this object)SH
ES
%%Page: 7 8
BS
0 SI
13 /Times-Bold AF
27568 8071 MT
(References)SH
10 /Times-Roman AF
9000 10444 MT
([Appel 89])SH
16500 XM
(Andrew W. Appel.)SH
16500 11549 MT
(Simple Generational Garbage Collection and Fast Allocation.)SH
/Times-Italic SF
16500 12654 MT
(Software-Practice and Experience)SH
/Times-Roman SF
30525 XM
(, February, 1989.)SH
9000 14445 MT
([Appel and MacQueen 87])SH
16500 15550 MT
(Andrew W. Appel and David B. MacQueen.)SH
16500 16655 MT
(A Standard ML Compiler.)SH
/Times-Italic SF
16500 17760 MT
(Functional Programming Languages and Computer Architecture.)SH
/Times-Roman SF
16500 18865 MT
(Springer-Verlag, 1987, pages 301--324.)SH
16500 19970 MT
(Volume 274 of Lecture Notes in Computer Science.)SH
9000 21761 MT
([Balram 91])SH
16500 XM
(Nikhil Balram and Jose M. F. Moura.)SH
16500 22866 MT
(Recursive Enhancement of Noncausal Images.)SH
16500 23971 MT
(In)SH
/Times-Italic SF
17583 XM
(Proceedings IEEE ICASSP'91)SH
/Times-Roman SF
(, pages 2997-3000.  May, 1991.)SH
9000 25762 MT
([Cooper and Morrisett 90])SH
16500 26867 MT
(Eric C. Cooper and J. Gregory Morrisett.)SH
/Times-Italic SF
16500 27972 MT
(Adding Threads to Standard ML)SH
/Times-Roman SF
(.)SH
16500 29077 MT
(Technical Report, School of Computer Science, Carnegie Mellon University, December,)SH
18000 30182 MT
(1990.)SH
9000 31973 MT
([Cooper and Nettles 91])SH
16500 33078 MT
(Eric Cooper, Scott Nettles.)SH
16500 34183 MT
(Experience With Mach External Pager for ML Garbage Collection.)SH
/Times-Italic SF
16500 35288 MT
(In Preparation)SH
/Times-Roman SF
22722 XM
(, 1991.)SH
9000 37079 MT
([Gibson 90])SH
16500 XM
(Garth A. Gibson.)SH
/Times-Italic SF
16500 38184 MT
(Redundant Disk Arrays: Reliable, Parallel Secondary Storage)SH
/Times-Roman SF
(.)SH
16500 39289 MT
(PhD thesis, Computer Science Division, University of California, Berkeley, December,)SH
18000 40394 MT
(1990.)SH
9000 42185 MT
([Halstead 85])SH
16500 XM
(Robert H. Halstead Jr.)SH
16500 43290 MT
(Multilisp: A Language for Concurrent Symbolic Computation.)SH
/Times-Italic SF
16500 44395 MT
(ACM Transactions on Programming Languages and Systems)SH
/Times-Roman SF
41250 XM
(, October, 1985.)SH
9000 46186 MT
([MacLachlan 91])SH
16500 XM
(Robert A. MacLachlan.)SH
/Times-Italic SF
16500 47291 MT
(CMU Common Lisp User's Manual)SH
/Times-Roman SF
16500 48396 MT
(School of Computer Science, Carnegie Mellon University, 1991.)SH
9000 50187 MT
([McNamee and Armstrong 90])SH
16500 51292 MT
(Dylan McNamee and Katherine Armstrong.)SH
16500 52397 MT
(Extending the Mach External Pager Interface to Accommodate User-Level Page)SH
18000 53502 MT
(Replacement Policies.)SH
16500 54607 MT
(In)SH
/Times-Italic SF
17583 XM
(USENIX Mach Workshop)SH
/Times-Roman SF
(. USENIX)
250 W( Association, October, 1990.)SH
9000 56398 MT
([Milner et.al. 90])SH
16500 XM
(Robin Milner, Mads Tofte, and Robert Harper.)SH
/Times-Italic SF
16500 57503 MT
(The Definition of Standard ML.)SH
/Times-Roman SF
16500 58608 MT
(MIT Press, 1990.)SH
9000 60399 MT
([Rashid et. al. 88])SH
16500 XM
(Rashid, Richard F. et. al.)SH
16500 61504 MT
(Machine Independent Virtual Memory Management for Paged Uniprocessor and)SH
18000 62609 MT
(Multiprocessor Architectures.)SH
/Times-Italic SF
16500 63714 MT
(IEEE Transactions on Computers)SH
/Times-Roman SF
30278 XM
(, August, 1988.)SH
9000 65505 MT
([Subramanian 91])SH
16500 XM
(Indira Subramanian.)SH
16500 66610 MT
(Managing Discardable Pages.)SH
/Times-Italic SF
16500 67715 MT
(In Preparation)SH
/Times-Roman SF
22722 XM
(, 1991.)SH
ES
%%Page: 8 9
BS
0 SI
10 /Times-Roman AF
9000 7886 MT
([Tevanian 87a])SH
16500 XM
(Avadis Tevanian Jr. and Richard F. Rashid.)SH
/Times-Italic SF
16500 8991 MT
(MACH: A Basis for Future UNIX Development)SH
/Times-Roman SF
(.)SH
16500 10096 MT
(Technical Report, Computer Science Department, Carnegie Mellon University, June,)SH
18000 11201 MT
(1987.)SH
9000 12992 MT
([Tevanian 87b])SH
16500 XM
(Avadis Tevanian Jr.)SH
/Times-Italic SF
16500 14097 MT
(Architecture-Independent Virtual Memory Management for Parallel and Distributed)SH
18000 15202 MT
(Environments: The Mach Approach)SH
/Times-Roman SF
(.)SH
16500 16307 MT
(PhD thesis, Computer Science Department, Carnegie Mellon University, December,)SH
18000 17412 MT
(1987.)SH
9000 19203 MT
([Young et. al. 87])SH
16500 XM
(Michael Young et. al.)SH
/Times-Italic SF
16500 20308 MT
(The Duality of Memory and Communication in the Implementation of a Multiprocessor)SH
18000 21413 MT
(Oprating System)SH
/Times-Roman SF
(.)SH
16500 22518 MT
(Technical Report, Department of Computer Science, Carnegie Mellon University,)SH
18000 23623 MT
(August, 1987.)SH
ES
%%Page: i 10
BS
0 SI
12 /Times-Bold AF
26033 8004 MT
(Table of Contents)SH
11 SS 
10650 9172 MT
(1. Introduction)SH
51650 XM
(0)SH
10650 10340 MT
(2. Solution)SH
51650 XM
(1)SH
10 SS 
12500 11420 MT
(2.1. The Page Attribute Bitmap)SH
51700 XM
(1)SH
12500 12500 MT
(2.2. Improving Paging Performance: Pre-flushing Strategy)SH
51700 XM
(2)SH
11 SS 
10650 13668 MT
(3. Evaluation)SH
51650 XM
(3)SH
10 SS 
12500 14748 MT
(3.1. Experimental Setup)SH
51700 XM
(3)SH
12500 15828 MT
(3.2. Performance Measurements)SH
51700 XM
(3)SH
11 SS 
10650 16996 MT
(4. Related Work)SH
51650 XM
(5)SH
10650 18164 MT
(5. Future Work)SH
51650 XM
(5)SH
10650 19332 MT
(6. Conclusion)SH
51650 XM
(5)SH
10650 20500 MT
(7. Acknowledgements)SH
51650 XM
(5)SH
10650 21668 MT
(Appendix I)
SH( Kernel)
550 W( - External Pager Interface)SH
51650 XM
(6)SH
ES
%%Page: ii 11
BS
0 SI
12 /Times-Bold AF
26866 8004 MT
(List of Figures)SH
11 SS 
10650 9172 MT
(Figure 2-1:)
SH( Interactions:)
550 W( Messages and Shared Memory)SH
51650 XM
(2)SH
ES
%%Page: iii 12
BS
0 SI
12 /Times-Bold AF
27099 8004 MT
(List of Tables)SH
11 SS 
10650 9172 MT
(Table 3-1:)
SH( Configurations)550 W
51650 XM
(3)SH
10650 10340 MT
(Table 3-2:)
SH( Performance)
550 W( Metrics)SH
51650 XM
(4)SH
10650 11508 MT
(Table 3-3:)
SH( Measurements:)
550 W( Compiling Parts of SML/NJ Compiler)SH
51650 XM
(4)SH
10650 12676 MT
(Table 3-4:)
SH( Measurements:)
550 W( Sorting using futures in ML)SH
51650 XM
(5)SH
ES
%%Trailer
%%Pages: 12
%%DocumentFonts: Times-Roman Times-Bold Times-Italic Symbol