duality.ps.ps

国外开发的著名分布式操作系统mach的有关代码文章

%!PS-Adobe-2.0
%%Title: sosp11.mss
%%DocumentFonts: (atend)
%%Creator: Mary Thompson and Scribe 7(1700)
%%CreationDate: 24 November 1993 15:23
%%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
    /letter {} def
    /lettersmall {} def
    /note {} 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
13 /Times-Bold AF
18196 13831 MT
(The Duality of Memory and Communication)SH
23233 15404 MT
(in the Implementation of a)SH
21212 16977 MT
(Multiprocessor Operating System)SH
10 /Times-Roman AF
17504 22434 MT
(Michael Young, Avadis Tevanian, Richard Rashid, David Golub,)SH
13810 23539 MT
(Jeffrey Eppinger, Jonathan Chew, William Bolosky, David Black and Robert Baron)SH
24434 24644 MT
(Computer Science Department)SH
24948 25749 MT
(Carnegie-Mellon University)SH
26280 26854 MT
(Pittsburgh, PA 15213)SH
17115 30338 MT
(Appeared in Proceedings of the 11th Operating Systems Principles,)SH
27239 31443 MT
(November, 1987)SH
13 /Times-Bold AF
28181 44993 MT
(Abstract)SH
10 /Times-Roman AF
7200 47366 MT
(Mach is)
238 W( a multiprocessor operating system being implemented at Carnegie-Mellon University.  An important)237 W
7200 48471 MT
(component of the Mach design is the use of memory objects which can)
50 W( be managed either by the kernel or by user)51 W
7200 49576 MT
(programs through a message interface.  This feature allows applications such)
32 W( as transaction management systems to)31 W
7200 50681 MT
(participate in decisions regarding secondary storage management and page replacement.)SH
7200 52888 MT
(This paper explores the goals, design and implementation of Mach and its external memory management)
100 W( facility.)101 W
7200 53993 MT
(The relationship between memory and communication in Mach is examined as)
132 W( it relates to overall performance,)131 W
7200 55098 MT
(applicability of Mach to new multiprocessor architectures, and the structure of application programs.)SH
8200 61886 MT
(This research was sponsored by the Defense Advanced Research Projects Agency \050DOD\051, ARPA Order)
177 W( No.)178 W
7200 62991 MT
(4864, monitored by the Space and Naval Warfare Systems Command under)
181 W( contract N00039-85-C-1034.  The)180 W
7200 64096 MT
(views expressed are those of the authors alone.)SH
/Times-Bold SF
8200 66303 MT
(Permission to copy without fee all or part of this material is granted provided that the copies)
29 W( are not made)30 W
7200 67408 MT
(or distributed for direct commercial advantage, the ACM copyright notice and the title of)
7 W( the publication and)6 W
7200 68513 MT
(its date)
15 W( appear, and notice is given that copying is by permission of the Association of Computing Machinery.)16 W
7200 69618 MT
(To copy otherwise, or to republish, requires a fee and/or specific permission.)SH
ES
%%Page: 1 2
BS
0 SI
10 /Times-Roman AF
30350 4286 MT
(1)SH
12 /Times-Bold AF
7200 8004 MT
(1. Introduction)SH
10 /Times-Roman AF
8200 9381 MT
(In late 1984, we began implementation of an operating system called Mach.  Our goals for Mach were:)SH
/Symbol SF
8990 10834 MT
(\267)SH
/Times-Roman SF
9700 XM
(an object oriented interface with a small number of basic system objects,)SH
/Symbol SF
8990 12592 MT
(\267)SH
/Times-Roman SF
9700 XM
(support for both distributed computing and multiprocessing,)SH
/Symbol SF
8990 14350 MT
(\267)SH
/Times-Roman SF
9700 XM
(portability to a wide range of multiprocessor and uniprocessor architectures,)SH
/Symbol SF
8990 16108 MT
(\267)SH
/Times-Roman SF
9700 XM
(compatibility with Berkeley UNIX, and)SH
/Symbol SF
8990 17866 MT
(\267)SH
/Times-Roman SF
9700 XM
(performance comparable to commercial UNIX offerings.)SH
8200 20345 MT
(Most of these early goals have been met.  The underlying Mach kernel)
53 W( is based on five interrelated abstractions;)52 W
7200 21722 MT
(operations on Mach objects are)
63 W( invoked through message passing.  Mach runs on the majority of workstations and)64 W
7200 23099 MT
(mainframes within the Department of Computer Science, and supports projects in distributed computing and)
8 W( parallel)7 W
7200 24476 MT
(processing such as)
409 W( the Camelot distributed transaction processing system)
410 W( [21],)
SH( the Agora parallel speech)410 W
7200 25853 MT
(understanding system)
41 W( [3])
SH( and a parallel implementation of OPS5)
41 W( [7].)
SH( Mach)
332 W( has already been ported to more than a)41 W
8 SS 
49691 26885 MT
(1)SH
10 SS 
7200 27230 MT
(dozen computer systems including ten members of the VAX family of)
23 W( uniprocessors and multiprocessors)24 W
50091 XM
(, the IBM)24 W
7200 28607 MT
(RT PC, the SUN 3, the 16-processor Encore MultiMax , and the 26-processor Sequent Balance)
116 W( 21000.  Mach is)115 W
7200 29984 MT
(binary compatible with Berkeley UNIX 4.3bsd and has been)
50 W( shown to outperform 4.3bsd in several benchmarks of)51 W
7200 31361 MT
(overall system performance [1].)SH
8200 33840 MT
(A key and unusual)
147 W( element in the design of Mach is the notion that communication \050in the form of message)146 W
7200 35217 MT
(passing\051 and virtual memory can play complementary roles, not only in the organization of distributed and)
59 W( parallel)60 W
7200 36594 MT
(applications, but in the implementation of the operating)
296 W( system kernel itself.  Mach uses memory-mapping)295 W
7200 37971 MT
(techniques to make the passing of large messages on a tightly coupled multiprocessor or uniprocessor)
SH( more efficient.)1 W
7200 39348 MT
(In addition, Mach implements)
223 W( virtual memory by mapping process addresses onto memory objects which are)222 W
7200 40725 MT
(represented as communication channels and accessed via messages.  The advantages gained by Mach)
128 W( in treating)129 W
7200 42102 MT
(memory and communication as duals in this way include:)SH
/Symbol SF
8990 43555 MT
(\267)SH
/Times-Roman SF
9700 XM
(increased flexibility in memory management available to user programs,)SH
/Symbol SF
8990 45313 MT
(\267)SH
/Times-Roman SF
9700 XM
(a better match between Mach facilities and both tightly and loosely coupled multiprocessors, and)SH
/Symbol SF
8990 47071 MT
(\267)SH
/Times-Roman SF
9700 XM
(improved performance.)SH
8200 49550 MT
(In this paper we describe the relationship)
197 W( between memory and communication in Mach.  In particular, we)196 W
7200 50927 MT
(examine the design and implementation of)
55 W( key Mach memory management operations, how Mach memory objects)56 W
7200 52304 MT
(can be managed)
246 W( outside the Mach kernel by application programs and the overall performance of the Mach)245 W
7200 53681 MT
(operating system.)SH
12 /Times-Bold AF
7200 57365 MT
(2. Early Work in Virtual Memory/Message Integration)SH
10 /Times-Roman AF
8200 58742 MT
(The design of Mach owes a great deal to a previous system developed at CMU called)
117 W( Accent)
118 W( [15].)
SH( A)
486 W( central)118 W
7200 60119 MT
(feature of Accent was the integration of virtual memory and communication.  Large amounts)
172 W( of data could be)171 W
7200 61496 MT
(transmitted between processes in Accent with extremely high performance)
175 W( through its use of memory-mapping)176 W
7200 62873 MT
(techniques. This)
366 W( allowed client and server processes)
58 W( to exchange potentially huge data objects, such as large files,)57 W
7200 64250 MT
(without concern for the traditional data copying costs of message passing.)SH
10800 50 7200 68504 UL
6 SS 
8000 69843 MT
(1)SH
8 SS 
8300 70152 MT
(The VAX 11/750, 11/780, 11/785, 8200, 8300, 8600, 8650, 8800, MicroVAX)
5 W( I and MicroVAX II are supported, including support for QBUS,)6 W
7200 71076 MT
(UNIBUS, MASSBUS and BIBUS devices. Several experimental VAXen are also in use including a VAX 11/784 \050four)
57 W( processor 780\051, 11/787)56 W
7200 72000 MT
(\050two processor 785\051 and 8204 \050four processor 8200\051.)SH
ES
%%Page: 2 3
BS
0 SI
10 /Times-Roman AF
30350 4286 MT
(2)SH
8200 7886 MT
(In effect, Accent carried into the domain)
201 W( of message-passing systems the notion that I/O can be performed)202 W
7200 9263 MT
(through virtual memory management.  It supported a)8 W
/Times-Italic SF
28678 XM
(single level)
8 W( store)7 W
/Times-Roman SF
35727 XM
(in which primary memory acted as a cache of)7 W
7200 10640 MT
(secondary storage.  Filesystem data and runtime allocated storage were both implemented as)
SH( disk-based data objects.)1 W
7200 12017 MT
(Copies of large messages were managed using shadow paging techniques.  Other systems of the time, such)
82 W( as the)81 W
7200 13394 MT
(IBM System 38)
84 W( [6])
SH( and)
84 W( Apollo Aegis)
85 W( [13],)
SH( also used the single level store approach, but limited its application to)85 W
7200 14771 MT
(the management of files.)SH
8200 17250 MT
(For the operating system designer, a single level store can be very)
59 W( attractive.  It can simplify the construction of)58 W
7200 18627 MT
(application programs by allowing programmers to map a file into the address space of)
227 W( a process. This often)228 W
7200 20004 MT
(encourages the replacement of state-laden libraries of I/O routines \050)184 W
/Times-Italic SF
(e.g.)SH
/Times-Roman SF
(, the UNIX standard)
184 W( I/O package\051 with)183 W
7200 21381 MT
(conceptually simpler programming language)
114 W( constructs such as arrays and records.  A single level store can also)115 W
7200 22758 MT
(make programs more efficient.  File data can be read directly into the pages)
37 W( of physical memory used to implement)36 W
7200 24135 MT
(the virtual address space of)
187 W( a program rather than into intermediate buffers managed by the operating system.)188 W
7200 25512 MT
(Because physical memory is used to cache secondary storage, repeated references)
130 W( to the same data can often be)129 W
7200 26889 MT
(made without corresponding disk transfers.)SH
8200 29368 MT
(Accent was successful in demonstrating the utility of combining memory mapping)
55 W( with message passing.  At its)56 W
7200 30745 MT
(peak, Accent ran on over 150 workstations at CMU and served as the base for)
230 W( a number of experiments in)229 W
7200 32122 MT
(distributed transaction)
209 W( processing)
210 W( [20],)
SH( distributed sensor networks)
210 W( [8],)
SH( distributed filesystems)
210 W( [12],)
SH( and process)210 W
7200 33499 MT
(migration [24].)SH
8200 35978 MT
(Accent was unsuccessful, however, in surviving the introduction)
118 W( of new hardware architectures and was never)117 W
7200 37355 MT
(able to efficiently support the large body of UNIX software used within the academic community)
31 W( [16].)
SH( In)
314 W( addition,)32 W
7200 38732 MT
(from the point of view of a system designer, the Accent style of)
134 W( message/memory integration lacked symmetry.)133 W
7200 40109 MT
(Accent allowed communication to be managed using memory-mapping techniques, but the)
210 W( notion of a virtual)211 W
7200 41486 MT
(memory object was highly specialized and the management of such)
53 W( an object was largely reserved to the operating)52 W
7200 42863 MT
(system itself.  Late in the life of Accent this issue was partially addressed)
154 W( by the implementation of)155 W
/Times-Italic SF
49889 XM
(imaginary)SH
7200 44240 MT
(segments)SH
/Times-Roman SF
11116 XM
([24] which could be provided by user-state processes, but such objects did not have the flexibility)
172 W( or)171 W
7200 45617 MT
(performance of kernel data objects.)SH
12 /Times-Bold AF
7200 49301 MT
(3. The Mach Design)SH
10 /Times-Roman AF
8200 50678 MT
(The Mach design grew out of an attempt to adapt Accent from its role as a network)
168 W( operating system for a)169 W
7200 52055 MT
(uniprocessor to a new)
206 W( environment that supported multiprocessors and uniprocessors connected on high speed)205 W
7200 53432 MT
(networks. Its)
250 W( history led to a design that provided both the message passing prevalent in Accent and new support)
SH( for)1 W
7200 54809 MT
(parallel processing and shared memory.)SH
8200 57288 MT
(There are four basic abstractions that Mach inherited)
23 W( \050although substantially changed\051 from Accent:)22 W
/Times-Italic SF
49006 XM
(task)SH
/Times-Roman SF
(,)SH
/Times-Italic SF
51139 XM
(thread)SH
/Times-Roman SF
(,)SH
/Times-Italic SF
7200 58665 MT
(port)SH
/Times-Roman SF
9233 XM
(and)SH
/Times-Italic SF
11043 XM
(message)SH
/Times-Roman SF
(. Their)
482 W( primary purpose is to provide)
116 W( control over program execution, internal program virtual)117 W
7200 60042 MT
(memory management)
134 W( and interprocess communication.  In addition, Mach provides a fifth abstraction called the)133 W
/Times-Italic SF
7200 61419 MT
(memory object)SH
/Times-Roman SF
13365 XM