%!PS
%%Version: 3.3
%%DocumentFonts: (atend)
%%Pages: (atend)
%%EndComments
%
% Version 3.3 prologue for troff files.
%

/#copies 1 store
/aspectratio 1 def
/formsperpage 1 def
/landscape false def
/linewidth .3 def
/magnification 1 def
/margin 0 def
/orientation 0 def
/resolution 720 def
/rotation 1 def
/xoffset 0 def
/yoffset 0 def

/roundpage true def
/useclippath true def
/pagebbox [0 0 612 792] def

/R  /Times-Roman def
/I  /Times-Italic def
/B  /Times-Bold def
/BI /Times-BoldItalic def
/H  /Helvetica def
/HI /Helvetica-Oblique def
/HB /Helvetica-Bold def
/HX /Helvetica-BoldOblique def
/CW /Courier def
/CO /Courier def
/CI /Courier-Oblique def
/CB /Courier-Bold def
/CX /Courier-BoldOblique def
/PA /Palatino-Roman def
/PI /Palatino-Italic def
/PB /Palatino-Bold def
/PX /Palatino-BoldItalic def
/Hr /Helvetica-Narrow def
/Hi /Helvetica-Narrow-Oblique def
/Hb /Helvetica-Narrow-Bold def
/Hx /Helvetica-Narrow-BoldOblique def
/KR /Bookman-Light def
/KI /Bookman-LightItalic def
/KB /Bookman-Demi def
/KX /Bookman-DemiItalic def
/AR /AvantGarde-Book def
/AI /AvantGarde-BookOblique def
/AB /AvantGarde-Demi def
/AX /AvantGarde-DemiOblique def
/NR /NewCenturySchlbk-Roman def
/NI /NewCenturySchlbk-Italic def
/NB /NewCenturySchlbk-Bold def
/NX /NewCenturySchlbk-BoldItalic def
/ZD /ZapfDingbats def
/ZI /ZapfChancery-MediumItalic def
/S  /S def
/S1 /S1 def
/GR /Symbol def

/inch {72 mul} bind def
/min {2 copy gt {exch} if pop} bind def

/setup {
	counttomark 2 idiv {def} repeat pop

	landscape {/orientation 90 orientation add def} if
	/scaling 72 resolution div def
	linewidth setlinewidth
	1 setlinecap

	pagedimensions
	xcenter ycenter translate
	orientation rotation mul rotate
	width 2 div neg height 2 div translate
	xoffset inch yoffset inch neg translate
	margin 2 div dup neg translate
	magnification dup aspectratio mul scale
	scaling scaling scale

	/Symbol /S Sdefs cf
	/Times-Roman /S1 S1defs cf
	0 0 moveto
} def

/pagedimensions {
	useclippath userdict /gotpagebbox known not and {
		/pagebbox [clippath pathbbox newpath] def
		roundpage currentdict /roundpagebbox known and {roundpagebbox} if
	} if
	pagebbox aload pop
	4 -1 roll exch 4 1 roll 4 copy
	landscape {4 2 roll} if
	sub /width exch def
	sub /height exch def
	add 2 div /xcenter exch def
	add 2 div /ycenter exch def
	userdict /gotpagebbox true put
} def

/pagesetup {
	/page exch def
	currentdict /pagedict known currentdict page known and {
		page load pagedict exch get cvx exec
	} if
} def

/decodingdefs [
	{counttomark 2 idiv {y moveto show} repeat}
	{neg /y exch def counttomark 2 idiv {y moveto show} repeat}
	{neg moveto {2 index stringwidth pop sub exch div 0 32 4 -1 roll widthshow} repeat}
	{neg moveto {spacewidth sub 0.0 32 4 -1 roll widthshow} repeat}
	{counttomark 2 idiv {y moveto show} repeat}
	{neg setfunnytext}
] def

/setdecoding {/t decodingdefs 3 -1 roll get bind def} bind def

/w {neg moveto show} bind def
/m {neg dup /y exch def moveto} bind def
/done {/lastpage where {pop lastpage} if} def

/f {
	dup /font exch def findfont exch
	dup /ptsize exch def scaling div dup /size exch def scalefont setfont
	linewidth ptsize mul scaling 10 mul div setlinewidth
	/spacewidth ( ) stringwidth pop def
} bind def

/changefont {
	/fontheight exch def
	/fontslant exch def
	currentfont [
		1 0
		fontheight ptsize div fontslant sin mul fontslant cos div
		fontheight ptsize div
		0 0
	] makefont setfont
} bind def

/sf {f} bind def

/cf {
	dup length 2 idiv
	/entries exch def
	/chtab exch def
	/newfont exch def

	findfont dup length 1 add dict
	/newdict exch def
	{1 index /FID ne {newdict 3 1 roll put} {pop pop} ifelse} forall

	newdict /Metrics entries dict put
	newdict /Metrics get
	begin
		chtab aload pop
		1 1 entries {pop def} for
		newfont newdict definefont pop
	end
} bind def

%
% A few arrays used to adjust reference points and character widths in some
% of the printer resident fonts. If square roots are too high try changing
% the lines describing /radical and /radicalex to,
%
%	/radical	[0 -75 550 0]
%	/radicalex	[-50 -75 500 0]
%
% Move braceleftbt a bit - default PostScript character is off a bit.
%

/Sdefs [
	/bracketlefttp		[201 500]
	/bracketleftbt		[201 500]
	/bracketrighttp		[-81 380]
	/bracketrightbt		[-83 380]
	/braceleftbt		[203 490]
	/bracketrightex		[220 -125 500 0]
	/radical		[0 0 550 0]
	/radicalex		[-50 0 500 0]
	/parenleftex		[-20 -170 0 0]
	/integral		[100 -50 500 0]
	/infinity		[10 -75 730 0]
] def

/S1defs [
	/underscore		[0 80 500 0]
	/endash			[7 90 650 0]
] def
%
% Tries to round clipping path dimensions, as stored in array pagebbox, so they
% match one of the known sizes in the papersizes array. Lower left coordinates
% are always set to 0.
%

/roundpagebbox {
    7 dict begin
	/papersizes [8.5 inch 11 inch 14 inch 17 inch] def

	/mappapersize {
		/val exch def
		/slop .5 inch def
		/diff slop def
		/j 0 def
		0 1 papersizes length 1 sub {
			/i exch def
			papersizes i get val sub abs
			dup diff le {/diff exch def /j i def} {pop} ifelse
		} for
		diff slop lt {papersizes j get} {val} ifelse
	} def

	pagebbox 0 0 put
	pagebbox 1 0 put
	pagebbox dup 2 get mappapersize 2 exch put
	pagebbox dup 3 get mappapersize 3 exch put
    end
} bind def

%%EndProlog
%%BeginSetup
mark
/linewidth 0.5 def
/landscape false def
/resolution 720 def
setup
2 setdecoding
%%EndSetup
%%Page: 1 1
/saveobj save def
mark
1 pagesetup
12 B f
(Multiprocessor Streams for Plan 9)4 1768 1 1996 1230 t
10 I f
(David Leo Presotto)2 783 1 2488 1470 t
10 R f
(AT&T Bell Laboratories)2 993 1 2383 1650 t
(Murray Hill, New Jersey 07974)4 1267 1 2246 1770 t
(research!presotto)2537 1890 w
(presotto@research.att.com)2346 2010 w
10 I f
(ABSTRACT)2643 2390 w
10 R f
( Streams for the Plan 9 kernel, a multi-)8 1615(This paper describes an implementation of)5 1735 2 1330 2686 t
( Rather)1 316( of UNIX.)2 407(threaded, multiprocessor kernel with a system call interface reminiscent)8 2877 3 1080 2806 t
( Plan 9, we changed the abstraction to fit more natu-)10 2098(than port Dennis Ritchie's Streams to)5 1502 2 1080 2926 t
( mechanism that has similar performance)5 1674( result is a)3 429( The)1 212(rally into the new environment.)4 1285 4 1080 3046 t
(and is internally easier to program.)5 1392 1 1080 3166 t
10 B f
(1. Introduction)1 670 1 720 3526 t
10 R f
( computing environment being built and used by the Computing Science Research)11 3421(Plan 9 is a new)4 649 2 970 3682 t
( terminals, CPU servers and file servers connected by)8 2145( 9 consists of)3 531( Plan)1 230(Center at AT&T Bell Laboratories.)4 1414 4 720 3802 t
( components run specialized operating systems based on a common multi-threaded)10 3322( These)1 288(various networks.)1 710 3 720 3922 t
( kernel runs on both uniprocessors and shared memory multiprocessors.)9 2868(kernel. The)1 479 2 720 4042 t
( we decided to base all our net-)7 1286( Therefore)1 448( of different networks.)3 910(Plan 9 communicates via a number)5 1426 4 970 4198 t
( allowed us to solve at once a number of problems such as flow con-)14 2790( This)1 232( single structure.)2 671(work code on a)3 627 4 720 4318 t
( Ritchie's)1 394( our past experience with it, we chose Dennis)8 1866( Given)1 301(trol, memory allocation, and user interface.)5 1759 4 720 4438 t
( coroutine-based design, introduced in)4 1552( This)1 234( System [Rit84] to provide the structure for Plan 9.)9 2086(Stream I/O)1 448 4 720 4558 t
( Plan 9's)2 352( Although)1 428(the Eighth Edition, provides a clean, flexible mechanism for handling asynchronous I/O.)11 3540 3 720 4678 t
( applica-)1 348(kernel is unrelated to that of the Eighth Edition [McI85], the concept of Streams remained directly)15 3972 2 720 4798 t
( have, however, made two major alterations.)6 1771(ble. We)1 335 2 720 4918 t
( the Plan 9 ker-)4 626( In)1 137( runs on multiprocessor systems so we wanted to exploit their concurrency.)11 3051(Plan 9)1 256 4 970 5074 t
( therefore converted Ritchie's coroutine-based design)5 2161( We)1 193(nel, the basic unit of concurrency is the process.)8 1966 3 720 5194 t
( we shall see later, this change has both advantages and disadvantages.)11 2819( As)1 161(to a process-based one.)3 925 3 720 5314 t
( also had to reduce the number of threads.)8 1679(Associated with the change to a process-based structure, we)8 2391 2 970 5470 t
( into a process, we would)5 1040(If we had made the most obvious change to convert each of Ritchie's coroutines)13 3280 2 720 5590 t
( they would)2 492( matter how cheap we make our kernel processes)8 2027( No)1 181(have incurred very high CPU penalties.)5 1620 4 720 5710 t
( we chose a structure that performs in one process what Streams)11 2635( Instead,)1 370( as cheap as coroutines.)4 967(never be)1 348 4 720 5830 t
(does in many coroutines.)3 999 1 720 5950 t
( interfaces,)1 446( The)1 214( program.)1 397(The result is a structure very similar to Streams but, we believe, easier to)13 3013 4 970 6106 t
( the freedom to allow processing modules to)7 1815( However,)1 446(flow control, and memory allocation are the same.)7 2059 3 720 6226 t
( easier to program.)3 769(block and to use any resources available to a user process has made many pieces much)15 3551 2 720 6346 t
(A process is a familiar programming construct.)6 1883 1 720 6466 t
( rest of this paper we will refer to Ritchie's Streams simply as Streams and to Plan 9 Streams as)19 3840(In the)1 230 2 970 6622 t
(Plan 9.)1 278 1 720 6742 t
cleartomark
showpage
saveobj restore
%%EndPage: 1 1
%%Page: 2 2
/saveobj save def
mark
2 pagesetup
10 R f
(- 2 -)2 166 1 2797 480 t
10 B f
( Structures)1 474(2. Data)1 330 2 720 840 t
10 R f
( description here is)3 775( Our)1 211( data structures as Streams.)4 1108(Plan 9, aside from minor changes, uses the same)8 1976 4 970 996 t
( refer the reader to Dennis's excellent BLTJ)7 1851( We)1 202( the differences.)2 667(very brief and is intended to highlight)6 1600 4 720 1116 t
(paper [Rit84] for a more comprehensive treatment.)6 2031 1 720 1236 t
(The appendix contains the C definitions of our data structures.)9 2491 1 970 1392 t
10 B f
(2.1. Stream)1 510 1 720 1632 t
10 R f
(A)970 1788 w
10 CW f
(Stream)1078 1788 w
10 R f
( User)1 250( a user process.)3 645(is a full duplex channel connecting a device or pseudo-device to)10 2671 3 1474 1788 t
( device)1 292( processes acting on behalf of a)6 1300( Kernel)1 329(processes insert and remove data at one end of the stream.)10 2399 4 720 1908 t
(insert data at the other.)4 912 1 720 2028 t
(A stream is made up of a linear list of)9 1650 1 970 2184 t
10 I f
(processing modules)1 807 1 2661 2184 t
10 R f
( module has both an upstream)5 1281(. Each)1 291 2 3468 2184 t
( and a downstream \(toward the device\))6 1599(\(toward the user\))2 699 2 720 2304 t
10 I f
(put procedure)1 571 1 3051 2304 t
10 R f
( is inserted into a stream by)6 1147(. Data)1 271 2 3622 2304 t
( module calls the succeeding one)5 1342( Each)1 254(calling the put procedure of the module at either end of the stream.)12 2724 3 720 2424 t
(to send data up or down the stream.)7 1420 1 720 2544 t
10 B f
(2.2. Queue)1 478 1 720 2784 t
10 R f
( is described by a pair of)6 1011(An instance of a processing module)5 1448 2 970 2940 t
10 CW f
(Queues)3459 2940 w
10 R f
( Each)1 254(, one for each direction.)4 967 2 3819 2940 t
(queue contains:)1 624 1 720 3060 t
( pointer to the put procedure)5 1134(- a)1 294 2 720 3216 t
( pointer to the next queue)5 1018(- a)1 294 2 720 3372 t
( linked list of queued data blocks)6 1321(- a)1 294 2 720 3528 t
( number of bytes queued)4 987(- the)1 372 2 720 3684 t
( number of blocks queued)4 1037(- the)1 372 2 720 3840 t
( spin lock to control access to the data structure)9 1894(- a)1 294 2 720 3996 t
(Unlike a Stream queue ours has no)6 1416 1 970 4152 t
10 I f
(service procedure)1 721 1 2415 4152 t
10 R f
( since on a multiprocessor setting prior-)6 1611(. Also,)1 293 2 3136 4152 t
( to)1 112(ity levels is not a valid synchronization mechanism, we require a spin lock from the operating system)16 4208 2 720 4272 t
(control access to the queue.)4 1100 1 720 4392 t
10 B f
(2.3. Block)1 445 1 720 4632 t
10 R f
( by a data structure called a)6 1115(The objects passed through the stream are described)7 2102 2 970 4788 t
10 CW f
(Block)4216 4788 w
10 R f
( blocks)1 290(. Our)1 234 2 4516 4788 t
( to Streams and contain a)5 1072(are identical)1 504 2 720 4908 t
10 I f
(base pointer)1 510 1 2334 4908 t
10 R f
(, a)1 107 1 2844 4908 t
10 I f
(limit pointer)1 511 1 2989 4908 t
10 R f
(, a)1 107 1 3500 4908 t
10 I f
(read pointer)1 510 1 3645 4908 t
10 R f
(, and a)2 289 1 4155 4908 t
10 I f
(write pointer)1 533 1 4482 4908 t
10 R f
(.)5015 4908 w
( base and limit are never changed and are)8 1738( The)1 216(Each pointer refers to memory mapped into kernel space.)8 2366 3 720 5028 t
( read and write pointers point to the start and end of)11 2154( The)1 213( describe the data allocated to the block.)7 1658(used to)1 295 4 720 5148 t
(usable data within the block.)4 1146 1 720 5268 t
(There are two block types,)4 1081 1 970 5424 t
10 I f
(data)2081 5424 w
10 R f
(and)2289 5424 w
10 I f
(control.)2463 5424 w
10 R f
(Data blocks are used to pass information from process)8 2208 1 2832 5424 t
( both have the same format.)5 1124( They)1 258( action of the modules.)4 925( blocks are used to control the)6 1222( Control)1 360(to process.)1 431 6 720 5544 t
( module until some condition is met for passing them along or)11 2519(Data blocks are often queued in a processing)7 1801 2 720 5664 t
( one accepts and)3 656( blocks are never queued but are passed from module to module until)12 2774( Control)1 357(freeing them.)1 533 4 720 5784 t
(frees them.)1 443 1 720 5904 t
( their control blocks come in multiple flavors,)7 1881( However,)1 447(Streams also have data and control blocks.)6 1742 3 970 6060 t
( priority blocks are moved to the)6 1310( Higher)1 328( and some higher.)3 713(all queuable; some with the same priority as data)8 1969 4 720 6180 t
( a result, the routines used to manipulate these control blocks tend to be complex.)14 3252( At)1 150(front of the queue.)3 737 3 720 6300 t
(When a module's)2 718 1 970 6456 t
10 I f
(put)1720 6456 w
10 R f
( one desires to pass many blocks)6 1352( If)1 124( passed a pointer to a block.)6 1160(is called it is)3 524 4 1880 6456 t
( is)1 94( This)1 230( procedure.)1 450(atomically, the blocks may be chained together and a pointer to the first is passed to the)16 3546 4 720 6576 t
(similar to the way)3 722 1 720 6696 t
10 I f
(mbufs)1468 6696 w
10 R f
( need no such concept since no two)7 1418( Streams)1 373(are passed in the BSD kernel [Lef89].)6 1516 3 1733 6696 t
( System V STREAMS [Bac86] have a much)7 1877( UNIX)1 313( in a Streams procedure.)4 1023(threads run simultaneously)2 1107 4 720 6816 t
( System V construct)3 811( The)1 206( pass a multi-block message along with a single put.)9 2091(more complicated construct to)3 1212 4 720 6936 t
(is used both for atomicity \(they originally had no other block delimiters\) and for performance.)14 3758 1 720 7056 t
cleartomark
showpage
saveobj restore
%%EndPage: 2 2
%%Page: 3 3
/saveobj save def
mark
3 pagesetup
10 R f
(- 3 -)2 166 1 2797 480 t
10 B f
(3. Algorithms)1 608 1 720 840 t
( Allocation)1 464(3.1. Memory)1 565 2 720 1080 t
10 R f
( list is kept for each of several fixed block sizes.)10 1971( A)1 127( time.)1 233(Stream memory is allocated at system start)6 1739 4 970 1236 t
( access of)2 387( Synchronizing)1 633( size receives the smallest block that can hold the request.)10 2304(A process that requests a)4 996 4 720 1356 t
(the free lists is performed using a spin lock per free list.)11 2224 1 720 1476 t
( code runs in the context of processes, whenever an allocation cannot be immediately)13 3430(Since all stream)2 640 2 970 1632 t
( result is that momentary surges in)6 1419( The)1 213(processed the caller blocks until a block of the right size is freed.)12 2688 3 720 1752 t
(used blocks do not panic the kernel as they sometimes did in the Eight Edition.)14 3157 1 720 1872 t
( the specific block sizes and the number allocated of each size depends on the)14 3238(The number of lists,)3 832 2 970 2028 t
( allocated blocks reflect)3 959( The)1 208( blocks, the servers more large ones.)6 1470( tend to use more small)5 950(kernel. Terminals)1 733 5 720 2148 t
(this.)720 2268 w
10 B f
( Interface)1 412(3.2. User)1 399 2 720 2508 t
10 R f
( at least two files,)4 714(A stream is represented at user level as a directory containing)10 2475 2 970 2664 t
10 CW f
(ctl)4187 2664 w
10 R f
(and)4395 2664 w
10 CW f
(data)4567 2664 w
10 R f
(. The)1 233 1 4807 2664 t
( the)1 161( last process to close destroys)5 1254( The)1 220(first process to open either file creates the stream automatically.)9 2685 4 720 2784 t
( to the)2 270(stream. Writing)1 662 2 720 2904 t
10 CW f
(data)1687 2904 w
10 R f
( into)1 192( process then copies the data)5 1189( The)1 215(file causes a switch to kernel mode.)6 1482 4 1962 2904 t
( block.)1 280(kernel data blocks and calls the put procedure of the first downstream processing module for each)15 4040 2 720 3024 t
( flagged with a delimiter in the event that the downstream module cares about)13 3213(The last block of a write is)6 1107 2 720 3144 t
( the third, and so)4 693( most cases the first put procedure calls the second, the second calls)12 2787( In)1 140(write boundaries.)1 700 4 720 3264 t
( write lock at)3 545( A)1 129( context switch.)2 644( data may often be sent without taking a)8 1646( Thus,)1 281(on until the data is output.)5 1075 6 720 3384 t
( insert data into the top of the same)8 1444(the top of the stream assures that no two processes can simultaneously)11 2876 2 720 3504 t
(stream, which insures that all writes are atomic.)7 1905 1 720 3624 t
(Our system has no)3 750 1 970 3780 t
10 CW f
(ioctl)1748 3780 w
10 R f
( syntax and semantics of)4 994( The)1 208(system call.)1 475 3 2076 3780 t
10 CW f
(ioctl)3781 3780 w
10 R f
(in UNIX are so uncon-)4 930 1 4110 3780 t
( to the)2 262( Writing)1 367(trolled that we left it out.)5 1024 3 720 3900 t
10 CW f
(ctl)2403 3900 w
10 R f
(file takes the place of)4 873 1 2613 3900 t
10 CW f
(ioctl)3516 3900 w
10 R f
( to the control file is)5 833(. Writing)1 391 2 3816 3900 t
( processing module)2 793( A)1 130( control.)1 341(the same as writing to a data file except that the blocks created are of type)15 3056 4 720 4020 t
( There-)1 319( commands in the control blocks are simple ASCII strings.)9 2388( The)1 210(parses each control block put to it.)6 1403 4 720 4140 t
( when one system is controlling streams in a name space imple-)11 2566(fore, there is no problem with byte ordering)7 1754 2 720 4260 t
( time to parse the control blocks is not important since the control opera-)13 2931( The)1 207( another processor.)2 760(mented on)1 422 4 720 4380 t
(tion is a rare one, usually used only when starting operation on a stream.)13 2893 1 720 4500 t
( con-)1 207( These)1 293( the stream.)2 473(The stream system intercepts the control blocks that control configuration of)10 3097 4 970 4656 t
(trol blocks are:)2 599 1 720 4776 t
(push)720 4932 w
10 I f
(name)934 4932 w
10 R f
(to add an instance of the processing module)7 1750 1 1320 4932 t
10 I f
(name)3095 4932 w
10 R f
(to the top of the stream.)5 949 1 3336 4932 t
( remove the top module of the stream.)7 1520(pop to)1 678 2 720 5088 t
( send a control message containing the string ``hangup'' up the stream from the device)14 3642(hangup to)1 678 2 720 5244 t
(end.)1320 5364 w
(Other control blocks are read by each module they pass through.)10 2575 1 720 5520 t
(Reading from the)2 707 1 970 5676 t
10 CW f
(data)1706 5676 w
10 R f
( read terminates either)3 904( The)1 210( data queued at the top of the stream.)8 1512(file returns)1 439 4 1975 5676 t
( is a per stream read lock)6 997( There)1 282( reached or when the end of a delimited block is read.)11 2139(when the read count is)4 902 4 720 5796 t
( were)1 221( ensures that the bytes read)5 1088( This)1 230(that ensures that only one process can read from the stream at a time.)13 2781 4 720 5916 t
( the)1 147( Reading)1 383(contiguous bytes from the stream.)4 1357 3 720 6036 t
10 CW f
(ctl)2632 6036 w
10 R f
(file is described in the section on multiplexing.)7 1877 1 2837 6036 t
10 B f
( Input)1 265(3.3. Device)1 482 2 720 6276 t
10 R f
( at a device, the driver's interrupt routine wakes up a kernel process to carry the)15 3330(When input exists)2 740 2 970 6432 t
( level segments allocated to it and is)7 1502( kernel process is an ordinary process with no user)9 2096( A)1 131(data upstream.)1 591 4 720 6552 t
( devices like Ethernet [Met80] may have many pro-)8 2126( Message-based)1 667(scheduled just like any other process.)5 1527 3 720 6672 t
(cesses ready to carry the next message upstream so that many messages can be processed simultaneously.)15 4219 1 720 6792 t
( message)1 366( the)1 149( Eventually,)1 510(The kernel process carries the message upstream through protocol modules.)9 3045 4 970 6948 t
( and wakes any user process)5 1182( kernel process leaves it there)5 1237( The)1 217(is delivered to the most upstream queue.)6 1684 4 720 7068 t
( the only difference between input and output is that the user process)12 2745( Thus,)1 275(blocked in a read on that stream.)6 1300 3 720 7188 t
( can be a benefit in our)6 1064( This)1 253( from kernel blocks to user space.)6 1494(must perform the copy of the data)6 1509 4 720 7308 t
cleartomark
showpage
saveobj restore
%%EndPage: 3 3
%%Page: 4 4
/saveobj save def
mark
4 pagesetup
10 R f
(- 4 -)2 166 1 2797 480 t
( process were to copy the data)6 1244( the kernel)2 433( If)1 122(multiprocessors in which each processor has a separate cache.)8 2521 4 720 840 t
( it on the wrong processor and hence into the wrong cache.)11 2460(into the user process it would most likely do)8 1860 2 720 960 t
( shared memory)2 657(This would force the user process to fault it into its own cache, increasing the load on the)17 3663 2 720 1080 t
(bus.)720 1200 w
10 B f
(3.4. Multiplexing)1 751 1 720 1440 t
10 R f
( is added)2 367( This)1 234( device.)1 316(Most protocols need to multiplex several conversations onto a single physical)10 3153 4 970 1596 t
( is very similar to the way)6 1038( This)1 228( multiplexed conversation.)2 1063(to our scheme using pseudo-devices, one for each)7 1991 4 720 1716 t
( pseudo-devices are coupled with a multiplexing processing)7 2486( group of)2 392( A)1 135(Eighth Edition handles TCP/IP.)3 1307 4 720 1836 t
( pseudo-devices add)2 821( device end modules on the)5 1125( The)1 212(module that is pushed onto a physical device stream.)8 2162 4 720 1956 t
( module downstream of the multi-)5 1373(the necessary header onto downstream messages and then put them to the)11 2947 2 720 2076 t
( multiplexing module looks at each message moving up its stream and puts it to the correct)16 3823(plexor. The)1 497 2 720 2196 t
(pseudo-device stream after stripping whatever header it used to do the demultiplexing.)11 3455 1 720 2316 t
( directory contains a)3 815( The)1 206( directory.)1 411(The user interface to a multiplexed protocol is a)8 1913 4 970 2472 t
10 CW f
(clone)4341 2472 w
10 R f
(file and a)2 373 1 4667 2472 t
( stream directories are numbered)4 1331( The)1 211(stream directory for each conversation.)4 1583 3 720 2592 t
10 I f
(1)3876 2592 w
10 R f
(to)3957 2592 w
10 I f
(n)4066 2592 w
10 R f
( Open-)1 304(\(see Figure 1\).)2 589 2 4147 2592 t
( a macro for finding a free stream directory and opening its)11 2402(ing the clone file is)4 778 2 720 2712 t
10 CW f
(ctl)3929 2712 w
10 R f
( the con-)2 357(file. Reading)1 545 2 4138 2712 t
( allows the user process to find the cor-)8 1585( This)1 230( chosen.)1 329(trol file returns the ASCII number of the conversation)8 2176 4 720 2832 t
(responding)720 2952 w
10 CW f
(data)1189 2952 w
10 R f
(file.)1454 2952 w
( ctl)1 -465(ctl data)1 -241 2 2743 4302 t
cleartomark
saveobj restore
%%BeginGlobal
%
% Version 3.3 drawing procedures for dpost. Automatically pulled in, but only
% when needed.
%

/inpath false def
/savematrix matrix def

/Dl {
	inpath
		{pop pop neg lineto}
		{newpath neg moveto neg lineto stroke}
	ifelse
} bind def

/De {
	/y1 exch 2 div def
	/x1 exch 2 div def
	/savematrix savematrix currentmatrix def
	neg exch x1 add exch translate
	x1 y1 scale
	0 0 1 0 360
	inpath
		{1 0 moveto arc savematrix setmatrix}
		{newpath arc savematrix setmatrix stroke}
	ifelse
} bind def

/Da {
	/dy2 exch def
	/dx2 exch def
	/dy1 exch def
	/dx1 exch def
	dy1 add neg exch dx1 add exch
	dx1 dx1 mul dy1 dy1 mul add sqrt
	dy1 dx1 neg atan
	dy2 neg dx2 atan
	inpath
		{arc}
		{newpath arc stroke}
	ifelse
} bind def

/DA {
	/dy2 exch def
	/dx2 exch def
	/dy1 exch def
	/dx1 exch def
	dy1 add neg exch dx1 add exch
	dx1 dx1 mul dy1 dy1 mul add sqrt
	dy1 dx1 neg atan
	dy2 neg dx2 atan
	inpath
		{arcn}
		{newpath arcn stroke}
	ifelse
} bind def

/Ds {
	/y2 exch def
	/x2 exch def
	/y1 exch def
	/x1 exch def
	/y0 exch def
	/x0 exch def
	x0 5 x1 mul add 6 div
	y0 5 y1 mul add -6 div
	x2 5 x1 mul add 6 div
	y2 5 y1 mul add -6 div
	x1 x2 add 2 div
	y1 y2 add -2 div
	inpath
		{curveto}
		{newpath x0 x1 add 2 div y0 y1 add -2 div moveto curveto stroke}
	ifelse
} bind def
%%EndGlobal
/saveobj save def
mark
10 R f
4347 4153 4175 3865 Dl
3888 4153 4060 3865 Dl
(. . .)2 125 1 3509 3784 t
(clone)1447 3813 w
(dk)2599 3266 w
4117 3634 2735 3346 Dl
3023 3634 2678 3346 Dl
2217 3634 2620 3346 Dl
1584 3634 2563 3346 Dl
( 1)1 -835(n 2)1 -1016 2 4093 3813 t
3253 4153 3081 3865 Dl
2794 4153 2966 3865 Dl
2447 4153 2275 3865 Dl
1987 4153 2159 3865 Dl
( data)1 -600(data ctl)1 -328 2 4265 4302 t
10 B f
(Figure 1)1 358 1 2881 4480 t
(3.5. Pipes)1 428 1 720 4780 t
10 R f
( The)1 218( Eighth Edition, are just two streams joined at the device end.)11 2599(Pipes, as in)2 477 3 970 4936 t
10 CW f
(pipe)4302 4936 w
10 R f
(system call)1 460 1 4580 4936 t
( control files are inaccessible.)4 1183( The)1 205(returns file descriptors for the data files of the two streams.)10 2359 3 720 5056 t
10 B f
( Processes)1 429(3.6. Helper)1 494 2 720 5296 t
10 R f
( pipelining, the user pro-)4 1021( to achieve true)3 636( However,)1 448(Transport protocols need to retransmit lost data.)6 1965 4 970 5452 t
( process has to retransmit the data)6 1377( Another)1 381(cess will want to queue data at the protocol module and return.)11 2562 3 720 5572 t
( this purpose, process-)3 902( For)1 192( be called in the context of a process.)8 1501(when needed since all put procedures must)6 1725 4 720 5692 t
( processes are awakened)3 976( The)1 205( kernel processes to perform such actions when needed.)8 2219(ing modules can create)3 920 4 720 5812 t
(on need by the processing module's put procedure or whenever a timer expires.)12 3173 1 720 5932 t
10 B f
( Control)1 358(3.7. Flow)1 411 2 720 6172 t
10 R f
( system that queues data one needs a mechanism to keep a queue with a slow reader from)17 3805(In any)1 265 2 970 6328 t
( queue keeps a count)4 839( Each)1 251( control mechanism similar to Streams.)5 1576( use a flow)3 444( We)1 191(absorbing all of memory.)3 1019 6 720 6448 t
( the high water)3 599( either exceeds a predetermined limit,)5 1502( Whenever)1 459(of bytes and a count of blocks queued there.)8 1760 4 720 6568 t
( caller of a processing module checks the high water flag for the next queue)14 3062( Each)1 252( queue.)1 291(flag is set for that)4 715 4 720 6688 t
( caller goes to)3 578( the next queue is past its high water mark, the would-be)11 2324( If)1 122(before calling its put procedure.)4 1296 4 720 6808 t
( structure in)2 481(sleep, leaving a pointer to itself in its queue \(the rendezvous)10 2429 2 720 6928 t
10 CW f
(Queue)3657 6928 w
10 R f
( a process empties)3 735(\). When)1 348 2 3957 6928 t
(a queue past half its high water mark it wakes up any process waiting at the previous queue.)17 3671 1 720 7048 t
( flow control a little)4 870(Modules implementing transport protocols with window schemes implement)7 3200 2 970 7204 t
cleartomark
showpage
saveobj restore
%%EndPage: 4 4
%%Page: 5 5
/saveobj save def
mark
5 pagesetup
10 R f
(- 5 -)2 166 1 2797 480 t
( when the upstream queue is)5 1134( However,)1 440( than go to sleep, they always pass data upstream.)9 1983(differently. Rather)1 763 4 720 840 t
( the remote)2 461( Hence,)1 335( the remote system.)3 795(full, the transport module stops sending acknowledgements back to)8 2729 4 720 960 t
( open the window again, a helper process sleeps in the queue instead)12 2796( To)1 166( stop sending.)2 563(side will eventually)2 795 4 720 1080 t
( the next queue empties, the helper is awakened and it does whatever is needed)14 3165( When)1 289( device process.)2 636(of the)1 230 4 720 1200 t
(to open the remote system's transmit window.)6 1846 1 720 1320 t
10 B f
(4. Performance)1 678 1 720 1560 t
10 R f
( Our)1 220( cannot be evaluated without comparing it against earlier ones.)9 2636(A different flavor of Streams)4 1214 3 970 1716 t
( the)1 151( However,)1 444( a general idea of where the advantages and disadvantages of Plan 9 Streams lie.)14 3262(results give)1 463 4 720 1836 t
( Streams code)2 580( compilers, operating systems, and)4 1418( The)1 214(systems compared are in many ways incomparable.)6 2108 4 720 1956 t
(all have a considerable effect on the results.)7 1745 1 720 2076 t
( are SGI Power Series machines with 1,)7 1607( Three)1 285( 9 numbers we use 4 different configurations.)7 1834(For Plan)1 344 4 970 2232 t
( System V)2 433( compare these against another 4 processor SGI Power Series running)10 2873( We)1 197(2, and 4 processors.)3 817 4 720 2352 t
( M2000 has the)3 658( The)1 218( M2000 system also running SVR3.)5 1499(Release 3 and against a single processor MIPS)7 1945 4 720 2472 t
( it has a considerably faster memory)6 1471( However,)1 444(same CPU running at the same speed as the SGI machines.)10 2405 3 720 2592 t
( of tight loops, this has a major impact on processing speed.)11 2390(system. Outside)1 664 2 720 2712 t
( is a system developed in our center and)8 1645( This)1 234( Plan 9 system is the Gnot terminal [Pik90].)8 1801(The other)1 390 4 970 2868 t
( compare it against a DEC)5 1106( We)1 199( a 25 MHz Motorola 68020.)5 1176( uses)1 209( It)1 123(now manufactured for us by AT&T.)5 1507 6 720 2988 t
( Gnot CPU is about 4/3 the speed)7 1378( The)1 211( machines on average are about the same speed.)8 1956( The)1 210(MicroVAX 3.)1 565 5 720 3108 t
(of the microVAX with a memory system that is about 2/3 the speed of the microVAX.)15 3457 1 720 3228 t
( throughput is tested using the following pro-)7 1906( The)1 219( measure both throughput and latency.)5 1601(All tests)1 344 4 970 3384 t
(gram:)720 3504 w
9 CW f
(int i;)1 324 1 1440 3674 t
(char buf[64*1024];)1 972 1 1440 3784 t
(int p[2];)1 486 1 1440 3894 t
(makeconnection\(p\);)1440 4114 w
(switch\(fork\(\)\){)1440 4224 w
(case 0:)1 378 1 1440 4334 t
(close\(p[1]\);)1872 4444 w
(while\(read\(p[0], buf, sizeof buf\) > 0\))5 2052 1 1872 4554 t
(;)2304 4664 w
(break;)1872 4774 w
(default:)1440 4884 w
(close\(p[0]\);)1872 4994 w
(for\(i = 0; i<ITER; i++\){)4 1296 1 1872 5104 t
(if\(write\(p[1], buf, sizeof buf\) != sizeof buf\){)6 2538 1 2304 5214 t
(perror\("write"\);)2736 5324 w
(exit\(1\);)2736 5434 w
(})2304 5544 w
(})1872 5654 w
(break;)1872 5764 w
(})1440 5874 w
10 R f
( tested)1 262( latency is)2 411( The)1 208(The block size is chosen to be large to minimize the difference in system call speeds.)15 3439 4 720 6054 t
(using:)720 6174 w
cleartomark
showpage
saveobj restore
%%EndPage: 5 5
%%Page: 6 6
/saveobj save def
mark
6 pagesetup
10 R f
(- 6 -)2 166 1 2797 480 t
9 CW f
(int p[2];)1 486 1 1440 830 t
(int i;)1 324 1 1440 940 t
(char c;)1 378 1 1440 1050 t
(makeconnection\(p\);)1440 1270 w
(switch\(fork\(\)\){)1440 1380 w
(case 0:)1 378 1 1440 1490 t
(close\(p[1]\);)1872 1600 w
(while\(read\(p[0], &c, 1\) == 1\))4 1566 1 1872 1710 t
(write\(p[0], &c, 1\);)2 1026 1 2304 1820 t
(break;)1872 1930 w
(default:)1440 2040 w
(close\(p[0]\);)1872 2150 w
(for\(i = 0; i<ITER; i++\){)4 1296 1 1872 2260 t
(if\(write\(p[1], &c, 1\) != 1\){)4 1512 1 2304 2370 t
(perror\("write"\);)2736 2480 w
(exit\(1\);)2736 2590 w
(})2304 2700 w
(if\(read\(p[1], &c, 1\) != 1\){)4 1458 1 2304 2810 t
(perror\("read"\);)2736 2920 w
(exit\(1\);)2736 3030 w
(})2304 3140 w
(})1872 3250 w
(break;)1872 3360 w
(})1440 3470 w
10 R f
(In both cases, we perform each operation for a large number of iterations to get an average time.)17 3842 1 720 3650 t
( pipes, SVR3 stream pipes, a)5 1222(The first test \(Table 1\) compares Plan 9 pipes against SVR3 normal)11 2848 2 970 3806 t
( only two processes)3 806( Since)1 279( under SVR3, and Tenth Edition Streams.)6 1708(BSD sockets implementation running)3 1527 4 720 3926 t
( performed by processing modules, we are)6 1783(are involved in all configurations and no processing is being)9 2537 2 720 4046 t
(comparing the speed of the basic plumbing in the systems.)9 2337 1 720 4166 t
10 S f
(_ _____________________________________)1 1894 1 1933 4306 t
10 R f
(Table 1 - Pipes)3 602 1 2604 4426 t
10 S f
(_ _____________________________________)1 1894 1 1933 4446 t
10 R f
( latency)1 455(system throughput)1 1111 2 2236 4566 t
(MBytes/sec ms)1 824 1 2892 4686 t
10 S f
(_ _____________________________________)1 1894 1 1933 4706 t
10 R f
(SGI/1 CPU)1 459 1 2008 4826 t
( .29)1 580( 6.0)1 904(Plan 9)1 253 3 2008 4946 t
10 S f
(_ _____________________________________)1 1894 1 1933 4966 t
10 R f
(SGI/2 CPUs)1 498 1 2008 5086 t
( .21)1 580( 8.4)1 904(Plan 9)1 253 3 2008 5206 t
10 S f
(_ _____________________________________)1 1894 1 1933 5226 t
10 R f
(SGI/4 CPUs)1 498 1 2008 5346 t
( .28)1 580( 8.4)1 904(Plan 9)1 253 3 2008 5466 t
10 S f
(_ _____________________________________)1 1894 1 1933 5486 t
10 R f
(SGI/4 CPUs)1 498 1 2008 5606 t
(sVr3)2008 5726 w
( .51)1 580( 4.5)1 793(old pipes)1 364 3 2008 5846 t
10 S f
(_ _____________________________________)1 1894 1 1933 5866 t
10 R f
(M2000)2008 5986 w
( .51)1 580( 8.0)1 672(sVr3 stream)1 485 3 2008 6106 t
10 S f
(_ _____________________________________)1 1894 1 1933 6126 t
10 R f
(M2000)2008 6246 w
( .36)1 580( 8.0)1 644(sVr3 sockets)1 513 3 2008 6366 t
10 S f
(_ _____________________________________)1 1894 1 1933 6376 t
(_ _____________________________________)1 1894 1 1933 6396 t
10 R f
(68020 Gnot)1 475 1 2008 6506 t
( 1.67)1 530( 1.79)1 954(Plan 9)1 253 3 2008 6626 t
10 S f
(_ _____________________________________)1 1894 1 1933 6646 t
10 R f
(uVAX 3)1 341 1 2008 6766 t
( 1.69)1 530( 1.04)1 473(10th Edition spipe)2 734 3 2008 6886 t
10 S f
( \347)1 -1894(_ _____________________________________)1 1894 2 1933 6906 t
(\347)1933 6806 w
(\347)1933 6706 w
(\347)1933 6606 w
(\347)1933 6506 w
(\347)1933 6406 w
(\347)1933 6306 w
(\347)1933 6206 w
(\347)1933 6106 w
(\347)1933 6006 w
(\347)1933 5906 w
(\347)1933 5806 w
(\347)1933 5706 w
(\347)1933 5606 w
(\347)1933 5506 w
(\347)1933 5406 w
(\347)1933 5306 w
(\347)1933 5206 w
(\347)1933 5106 w
(\347)1933 5006 w
(\347)1933 4906 w
(\347)1933 4806 w
(\347)1933 4706 w
(\347)1933 4606 w
(\347)1933 4506 w
(\347)1933 4406 w
(\347)2792 6906 w
(\347)2792 6846 w
(\347)2792 6746 w
(\347)2792 6646 w
(\347)2792 6546 w
(\347)2792 6446 w
(\347)2792 6346 w
(\347)2792 6246 w
(\347)2792 6146 w
(\347)2792 6046 w
(\347)2792 5946 w
(\347)2792 5846 w
(\347)2792 5746 w
(\347)2792 5646 w
(\347)2792 5546 w
(\347)2792 5446 w
(\347)2792 5346 w
(\347)2792 5246 w
(\347)2792 5146 w
(\347)2792 5046 w
(\347)2792 4946 w
(\347)2792 4846 w
(\347)2792 4746 w
(\347)2792 4646 w
(\347)2792 4546 w
(\347)3414 6906 w
(\347)3414 6846 w
(\347)3414 6746 w
(\347)3414 6646 w
(\347)3414 6546 w
(\347)3414 6446 w
(\347)3414 6346 w
(\347)3414 6246 w
(\347)3414 6146 w
(\347)3414 6046 w
(\347)3414 5946 w
(\347)3414 5846 w
(\347)3414 5746 w
(\347)3414 5646 w
(\347)3414 5546 w
(\347)3414 5446 w
(\347)3414 5346 w
(\347)3414 5246 w
(\347)3414 5146 w
(\347)3414 5046 w
(\347)3414 4946 w
(\347)3414 4846 w
(\347)3414 4746 w
(\347)3414 4646 w
(\347)3414 4546 w
(\347)3827 6906 w
(\347)3827 6806 w
(\347)3827 6706 w
(\347)3827 6606 w
(\347)3827 6506 w
(\347)3827 6406 w
(\347)3827 6306 w
(\347)3827 6206 w
(\347)3827 6106 w
(\347)3827 6006 w
(\347)3827 5906 w
(\347)3827 5806 w
(\347)3827 5706 w
(\347)3827 5606 w
(\347)3827 5506 w
(\347)3827 5406 w
(\347)3827 5306 w
(\347)3827 5206 w
(\347)3827 5106 w
(\347)3827 5006 w
(\347)3827 4906 w
(\347)3827 4806 w
(\347)3827 4706 w
(\347)3827 4606 w
(\347)3827 4506 w
(\347)3827 4406 w
10 R f
( was the expected)3 745( This)1 241( 1 we can see that for the large machines, Plan 9 has lower latency.)14 2853(From Table)1 481 4 720 7146 t
( many fewer instructions than traditional Streams which must)8 2483(result since the straight call structure requires)6 1837 2 720 7266 t
cleartomark
showpage
saveobj restore
%%EndPage: 6 6
%%Page: 7 7
/saveobj save def
mark
7 pagesetup
10 R f
(- 7 -)2 166 1 2797 480 t
( going)1 266( dip of .08 ms when)5 854( The)1 217(schedule each service procedure in addition to calling its put procedure.)10 2983 4 720 840 t
( the first has)3 518( second process is starting up before)6 1507( The)1 215(from 1 processor to 2 is the result of concurrency.)9 2080 4 720 960 t
(returned from queuing its block.)4 1290 1 720 1080 t
( believe)1 318( We)1 193( 4.)1 105(The unexpected result is the rise from .21 ms to .28 when going from 2 processors to)16 3454 4 970 1236 t
( this paper is pre-)4 713( hope to verify this assumption before)6 1551( We)1 194(that this is contention over the process queue.)7 1862 4 720 1356 t
(sented.)720 1476 w
( reflects the slower mem-)4 1018(The low single processor SGI throughput for Plan 9 compared to the M2000)12 3052 2 970 1632 t
( concurrency and our)3 886( we use multiple processors, we take advantage of the)9 2280( When)1 303(ory on the SGI box.)4 851 4 720 1752 t
(throughput passes all the others.)4 1285 1 720 1872 t
( still)1 188( We)1 200( on the Gnot compared to the Tenth Edition on the MicroVAX is less impressive.)14 3418(Plan 9)1 264 4 970 2028 t
( given the ratio of machine speeds, we should be much)10 2238( However,)1 445( throughput.)1 494(have a definite advantage in)4 1143 4 720 2148 t
( the kernel showed that the disappointing latency time was due entirely to the)13 3218( Profiling)1 416(better in latency.)2 686 3 720 2268 t
( switch context we do a lot of)7 1200( we)1 145( Whenever)1 463( MMU on the Gnot only retains one process state.)9 2028(MMU. The)1 484 5 720 2388 t
( reason the throughput doesn't suffer from this problem is that the pipelin-)12 3017( The)1 209( the MMU.)2 455(faulting to refill)2 639 4 720 2508 t
(ing causes a lot of data to be moved per context switch.)11 2213 1 720 2628 t
( driver processors to performing puts at interrupt level, we)9 2464(To compare the performance of kernel)5 1606 2 970 2784 t
( and wide area network spanning all of)7 1563( is both a local)4 595( It)1 114(used our most prevalent network, Datakit [Che80].)6 2048 4 720 2904 t
( due to con-)3 483( However,)1 443( MicroVAX, SGI, and M2000 each have 8 megabit/sec links to Datakit.)11 2890(AT&T. The)1 504 4 720 3024 t
( Gnots have a slower 2 megabit link)7 1538( The)1 219( the Datakit the highest throughput is 2.6 megabits.)8 2156(straints in)1 407 4 720 3144 t
( all cases the remote sys-)5 1010( In)1 136( the Datakit.)2 497( 2 presents performance of various systems through)7 2074([Pre88]. Table)1 603 5 720 3264 t
( the)1 156( again, Plan 9 throughput matches or exceeds the throughput of)10 2627( Once)1 270(tem is a Plan 9 SGI processor.)6 1267 4 720 3384 t
( is the price paid for using kernel processes to send device)11 2364( This)1 232( latency is worse.)3 705( However,)1 444(other systems.)1 575 5 720 3504 t
( especially evident in the Gnot)5 1218( degradation is)2 590( The)1 206(data upstream rather than doing it in the interrupt routine.)9 2306 4 720 3624 t
(since it is the worst at process switching.)7 1632 1 720 3744 t
10 S f
(_ ________________________________)1 1643 1 2058 3884 t
10 R f
(Table 2 - URP/Datakit)3 902 1 2453 4004 t
10 S f
(_ ________________________________)1 1643 1 2058 4024 t
10 R f
( latency)1 446(system throughput)1 986 2 2244 4144 t
(KBytes/sec ms)1 807 1 2783 4264 t
10 S f
(_ ________________________________)1 1643 1 2058 4284 t
10 R f
(SGI/2 CPUs)1 498 1 2133 4404 t
( 1.4)1 509( 235)1 699(Plan 9)1 253 3 2133 4524 t
10 S f
(_ ________________________________)1 1643 1 2058 4544 t
10 R f
(SGI/4 CPUs)1 498 1 2133 4664 t
( 1.4)1 509( 235)1 699(Plan 9)1 253 3 2133 4784 t
10 S f
(_ ________________________________)1 1643 1 2058 4804 t
10 R f
(M2000)2133 4924 w
( 1.2)1 509(sVr3 235)1 952 2 2133 5044 t
10 S f
(_ ________________________________)1 1643 1 2058 5054 t
(_ ________________________________)1 1643 1 2058 5074 t
10 R f
(68020 Gnot)1 475 1 2133 5184 t
( 5.8)1 509( 100)1 699(Plan 9)1 253 3 2133 5304 t
10 S f
(_ ________________________________)1 1643 1 2058 5324 t
10 R f
(uVAX 3)1 341 1 2133 5444 t
( 3.2)1 509( 85)1 454(10th Edition)1 498 3 2133 5564 t
10 S f
( \347)1 -1643(_ ________________________________)1 1643 2 2058 5584 t
(\347)2058 5484 w
(\347)2058 5384 w
(\347)2058 5284 w
(\347)2058 5184 w
(\347)2058 5084 w
(\347)2058 4984 w
(\347)2058 4884 w
(\347)2058 4784 w
(\347)2058 4684 w
(\347)2058 4584 w
(\347)2058 4484 w
(\347)2058 4384 w
(\347)2058 4284 w
(\347)2058 4184 w
(\347)2058 4084 w
(\347)2058 3984 w
(\347)2683 5584 w
(\347)2683 5524 w
(\347)2683 5424 w
(\347)2683 5324 w
(\347)2683 5224 w
(\347)2683 5124 w
(\347)2683 5024 w
(\347)2683 4924 w
(\347)2683 4824 w
(\347)2683 4724 w
(\347)2683 4624 w
(\347)2683 4524 w
(\347)2683 4424 w
(\347)2683 4324 w
(\347)2683 4224 w
(\347)2683 4124 w
(\347)3288 5584 w
(\347)3288 5524 w
(\347)3288 5424 w
(\347)3288 5324 w
(\347)3288 5224 w
(\347)3288 5124 w
(\347)3288 5024 w
(\347)3288 4924 w
(\347)3288 4824 w
(\347)3288 4724 w
(\347)3288 4624 w
(\347)3288 4524 w
(\347)3288 4424 w
(\347)3288 4324 w
(\347)3288 4224 w
(\347)3288 4124 w
(\347)3701 5584 w
(\347)3701 5484 w
(\347)3701 5384 w
(\347)3701 5284 w
(\347)3701 5184 w
(\347)3701 5084 w
(\347)3701 4984 w
(\347)3701 4884 w
(\347)3701 4784 w
(\347)3701 4684 w
(\347)3701 4584 w
(\347)3701 4484 w
(\347)3701 4384 w
(\347)3701 4284 w
(\347)3701 4184 w
(\347)3701 4084 w
(\347)3701 3984 w
10 R f
( don't compare these against other sys-)6 1618( We)1 197(Finally, we present some Ethernet performance results.)6 2255 3 970 5860 t
( low weight)2 496( was designed as a)4 789( It)1 124(tems since the protocol we use, Nonet, currently runs only on Plan 9.)12 2911 4 720 5980 t
( published)1 418( should be noted that the throughput figures are higher than any we've seen)13 3047( It)1 114(transport protocol.)1 741 4 720 6100 t
( is as much a function the protocol as it is of Plan 9.)13 2071( This)1 228(to date for an Ethernet.)4 917 3 720 6220 t
cleartomark
showpage
saveobj restore
%%EndPage: 7 7
%%Page: 8 8
/saveobj save def
mark
8 pagesetup
10 R f
(- 8 -)2 166 1 2797 480 t
10 S f
(_ ________________________________)1 1641 1 2059 860 t
10 R f
(Table 3 - Nonet/Ethernet)3 995 1 2407 980 t
10 S f
(_ ________________________________)1 1641 1 2059 1000 t
10 R f
( latency)1 446(system throughput)1 985 2 2244 1120 t
(KBytes/sec ms)1 807 1 2782 1240 t
10 S f
(_ ________________________________)1 1641 1 2059 1260 t
10 R f
(SGI/2 CPUs)1 498 1 2134 1380 t
( 1.4)1 509( 950)1 697(Plan 9)1 253 3 2134 1500 t
10 S f
(_ ________________________________)1 1641 1 2059 1520 t
10 R f
(SGI/4 CPUs)1 498 1 2134 1640 t
( 1.4)1 509( 950)1 697(Plan 9)1 253 3 2134 1760 t
10 S f
( \347)1 -1641(_ ________________________________)1 1641 2 2059 1780 t
(\347)2059 1760 w
(\347)2059 1660 w
(\347)2059 1560 w
(\347)2059 1460 w
(\347)2059 1360 w
(\347)2059 1260 w
(\347)2059 1160 w
(\347)2059 1060 w
(\347)2059 960 w
(\347)2682 1780 w
(\347)2682 1700 w
(\347)2682 1600 w
(\347)2682 1500 w
(\347)2682 1400 w
(\347)2682 1300 w
(\347)2682 1200 w
(\347)2682 1100 w
(\347)3287 1780 w
(\347)3287 1700 w
(\347)3287 1600 w
(\347)3287 1500 w
(\347)3287 1400 w
(\347)3287 1300 w
(\347)3287 1200 w
(\347)3287 1100 w
(\347)3700 1780 w
(\347)3700 1760 w
(\347)3700 1660 w
(\347)3700 1560 w
(\347)3700 1460 w
(\347)3700 1360 w
(\347)3700 1260 w
(\347)3700 1160 w
(\347)3700 1060 w
(\347)3700 960 w
10 B f
(Related Work)1 602 1 720 2140 t
10 R f
(We must mention Larry Peterson's)4 1442 1 970 2296 t
10 I f
(x)2448 2296 w
10 R f
( The)1 216(-Kernel work [Pet89].)2 900 2 2492 2296 t
10 I f
(x)3644 2296 w
10 R f
( similar to Plan 9)4 732(-Kernel is very)2 620 2 3688 2296 t
( process structure, mul-)3 943( The)1 207( study the decomposition of network protocols.)6 1897( is used primarily to)4 812(Streams. It)1 461 5 720 2416 t
(tiplexing, and data structures are virtually identical to Plan 9 Steams.)10 2753 1 720 2536 t
(The greatest differences between our systems are:)6 1988 1 970 2692 t
(1\) The)1 405 1 720 2848 t
10 I f
(x)1160 2848 w
10 R f
( kernel)1 285( Our)1 215( are just a PC and a stack.)7 1096( They)1 265(-Kernel uses very light weight kernel processes.)6 1975 5 1204 2848 t
(processes carry all the baggage of user processes.)7 1971 1 970 2968 t
( and wait for the user process to read it,)9 1664( than queue data at the user process)7 1473(2\) Rather)1 516 3 720 3124 t
10 I f
(x)4408 3124 w
10 R f
(-Kernel kernel)1 588 1 4452 3124 t
( in the user's address space which moves the data directly into user)12 2822(processes call a put procedure)4 1248 2 970 3244 t
(memory.)970 3364 w
( message in the)3 646(3\) The)1 405 2 720 3520 t
10 I f
(x)1807 3520 w
10 R f
( tree is)2 290( pointer to the top of the)6 1032( A)1 133(-Kernel is in the form of a tree of blocks.)9 1734 4 1851 3520 t
( use a linear structure.)4 878( We)1 188(passed through the processing modules.)4 1590 3 970 3640 t
(Published performance of the)3 1193 1 970 3796 t
10 I f
(x)2193 3796 w
10 R f
( hope to bor-)3 531( We)1 194( with lower latency times.)4 1059(-Kernel is similar to ours)4 1019 4 2237 3796 t
(row some of the ideas of the)6 1131 1 720 3916 t
10 I f
(x)1876 3916 w
10 R f
(-Kernel to improve our own performance.)5 1673 1 1920 3916 t
10 B f
(Conclusions)720 4156 w
10 R f
( to Plan 9 Streams is making)6 1205( main advantage)2 672( The)1 214(We have presented another variation of streams.)6 1979 4 970 4312 t
( based model is)3 646( have a very subjective belief that the process)8 1892( We)1 198(use of concurrency in multiprocessors.)4 1584 4 720 4432 t
(easier to program than the coroutine based one.)7 1890 1 720 4552 t
( the contexts)2 533( However,)1 454( results show that the Plan 9 model has high throughput.)10 2387(The performance)1 696 4 970 4708 t
( research and tuning is required to reduce)7 1669( Further)1 347( by the kernel processes increase latency.)6 1660(switches caused)1 644 4 720 4828 t
(these costs.)1 455 1 720 4948 t
10 B f
(5. References)1 589 1 720 5188 t
10 R f
( Bach,)1 255(Bac86. M.)1 444 2 720 5416 t
10 I f
(The Design of the UNIX Operating System,)6 1729 1 1444 5416 t
10 R f
(Prentice-Hall \(1986\).)1 848 1 3198 5416 t
( G. Fraser, ``Datakit Network Architecture,'' in)6 1909( L. Chesson and A.)4 770(Che80. G.)1 433 3 720 5572 t
10 I f
(IEEE Compcon '80)2 786 1 3859 5572 t
10 R f
(\(January,)4672 5572 w
(1980\).)970 5692 w
( Leffler, M. K. McKusick, M. Karels, and J. Quarterman,)9 2304(Lef89. S.)1 394 2 720 5848 t
10 I f
(4.3BSD UNIX Operating System,)3 1335 1 3445 5848 t
10 R f
(Addi-)4807 5848 w
(son Wesley \(1989\).)2 779 1 970 5968 t
( D. McIlroy,)2 515(McI85. M.)1 455 2 720 6124 t
10 I f
(Unix Programmer's Manual, Eighth Edition,)4 1837 1 1723 6124 t
10 R f
( Murray Hill, NJ,)3 718(Bell Laboratories,)1 729 2 3593 6124 t
(USA \(February, 1985\).)2 926 1 970 6244 t
( Local Network:)2 674( Metcalfe, D. Boggs, C. Crane, E. Taft, J. Shoch, and J. Hupp, ``The Ethernet)14 3218(Met80. R.)1 428 3 720 6400 t
( Palo Alto Research Centers \(February, 1980\).)6 1852( XEROX)1 394(Three Reports,'' CSL-80-2,)2 1109 3 970 6520 t
( the X-Kernel: Evaluating New Design Techniques,'' in)7 2276( Peterson, ``RPC in)3 793(Pet89. L.)1 389 3 720 6676 t
10 I f
(Proceedings Twelfth)1 831 1 4209 6676 t
(Symposium on Operating Systems Principles)4 1793 1 970 6796 t
10 R f
(, Litchfield Park, AZ \(December, 1989\).)5 1610 1 2763 6796 t
( Pike, D. Presotto, K. Thompson, and H. Trickey, ``Plan 9 from Bell Labs,'' in)14 3147(Pik90. R.)1 401 2 720 6952 t
10 I f
(UKUUG Proceed-)1 746 1 4294 6952 t
(ings of the Summer 1990 Conference)5 1479 1 970 7072 t
10 R f
(, London, England \(July, 1990\).)4 1277 1 2449 7072 t
( Presotto, ``Plan 9 from Bell Labs - The Network,'' in)10 2258(Pre88. D.)1 405 2 720 7228 t
10 I f
( of the Spring 1988)4 811(EUUG Proceedings)1 811 2 3418 7228 t
cleartomark
showpage
saveobj restore
%%EndPage: 8 8
%%Page: 9 9
/saveobj save def
mark
9 pagesetup
10 R f
(- 9 -)2 166 1 2797 480 t
10 I f
(Conference)970 840 w
10 R f
(, London, England \(April, 1988\).)4 1321 1 1430 840 t
( M. Ritchie, ``A Stream Input-Output System,'')6 1913(Rit84. D.)1 395 2 720 996 t
10 I f
(AT&T Bell Laboratories Technical Journal)4 1744 1 3054 996 t
10 B f
(63)4824 996 w
10 R f
(\(8\))4924 996 w
(\(October, 1984\).)1 662 1 970 1116 t
(UNIX is a registered trademark of AT&T Bell Laboratories)8 2383 1 720 1392 t
(Datakit is a registered trademark of AT&T)6 1707 1 720 1548 t
10 B f
(Appendix)720 1788 w
9 CW f
(/*)1008 1958 w
( available to a queue)4 1134(* operations)1 702 2 1062 2068 t
(*/)1062 2178 w
( Qinfo;)1 540(typedef struct Qinfo)2 1080 2 1008 2288 t
(struct Qinfo)1 648 1 1008 2398 t
({)1008 2508 w
( input routine */)3 918( /*)1 270(void \(*iput\)\(Queue*, Block*\);)2 1566 3 1440 2618 t
( output routine */)3 972( /*)1 270(void \(*oput\)\(Queue*, Block*\);)2 1566 3 1440 2728 t
(void \(*open\)\(Queue*, Stream*\);)2 1620 1 1440 2838 t
(void \(*close\)\(Queue*\);)1 1188 1 1440 2948 t
(char *name;)1 594 1 1440 3058 t
(};)1008 3168 w
(/*)1008 3388 w
( reference kernel memory via descriptors kept in host memory)9 3240(* We)1 270 2 1062 3498 t
(*/)1062 3608 w
( Block;)1 540(typedef struct Block)2 1080 2 1008 3718 t
(struct Block)1 648 1 1008 3828 t
({)1008 3938 w
(Block *next;)1 756 1 1440 4048 t
( first not consumed byte */)5 1458( /*)1 648(uchar *rptr;)1 756 3 1440 4158 t
( first empty byte */)4 1080( /*)1 648(uchar *wptr;)1 756 3 1440 4268 t
( 1 past the end of the buffer */)8 1728( /*)1 702(uchar *lim;)1 702 3 1440 4378 t
( start of the buffer */)5 1242( /*)1 648(uchar *base;)1 756 3 1440 4488 t
(uchar flags;)1 756 1 1440 4598 t
(uchar type;)1 702 1 1440 4708 t
(};)1008 4818 w
(/* flag bits */)3 810 1 1008 5038 t
( this block is the end of a higher level message */)11 2754( /*)1 324(#define S_DELIM 0x80)2 1080 3 1008 5148 t
(#define S_CLASS 0x07)2 1080 1 1008 5258 t
(/* type values */)3 918 1 1008 5478 t
(#define M_DATA 0)2 864 1 1008 5588 t
(#define M_CTL 1)2 810 1 1008 5698 t
(/*)1008 5918 w
( list of blocks)3 810(* a)1 216 2 1062 6028 t
(*/)1062 6138 w
( Blist;)1 540(typedef struct Blist)2 1080 2 1008 6248 t
(struct Blist {)2 756 1 1008 6358 t
(Lock;)1440 6468 w
( first data block */)4 1080( /*)1 594(Block *first;)1 810 3 1440 6578 t
( last data block */)4 1026( /*)1 648(Block *last;)1 756 3 1440 6688 t
( length of list in bytes */)6 1458( /*)1 756(long len;)1 648 3 1440 6798 t
(};)1008 6908 w
cleartomark
showpage
saveobj restore
%%EndPage: 9 9
%%Page: 10 10
/saveobj save def
mark
10 pagesetup
10 R f
(- 10 -)2 216 1 2772 480 t
9 CW f
(/*)1008 830 w
( queue of blocks)3 864(* a)1 216 2 1062 940 t
(*/)1062 1050 w
( Queue;)1 540(typedef struct Queue)2 1080 2 1008 1160 t
(struct Queue {)2 756 1 1008 1270 t
(Blist;)1440 1380 w
( number of blocks in queue */)6 1566( /*)1 810(int nb;)1 594 3 1440 1490 t
(int flag;)1 702 1 1440 1600 t
( line discipline definition */)4 1620( /*)1 648(Qinfo *info;)1 756 3 1440 1710 t
( opposite direction, same line discipline */)6 2376( /*)1 594(Queue *other;)1 810 3 1440 1820 t
( next queue in the stream */)6 1512( /*)1 648(Queue *next;)1 756 3 1440 1930 t
( Block*\);)1 486(void \(*put\)\(Queue*,)1 1188 2 1440 2040 t
( flow control rendezvous point */)5 1782( /*)1 864(Rendez r;)1 540 3 1440 2150 t
( private info for the queue */)6 1620( /*)1 702(void *ptr;)1 702 3 1440 2260 t
(};)1008 2370 w
( flag bit meaning the stream has been hung up */)10 2592( /*)1 378(#define QHUNGUP 0x1)2 1026 3 1008 2480 t
( 0x2)1 270(#define QINUSE)1 756 2 1008 2590 t
( queue has gone past the high water mark */)9 2322( /*)1 378( 0x4)1 270(#define QHIWAT)1 756 4 1008 2700 t
(/*)1008 2920 w
( stream head)2 648(* a)1 216 2 1062 3030 t
(*/)1062 3140 w
(struct Stream {)2 810 1 1008 3250 t
( structure lock */)3 972(Lock; /*)1 1404 2 1440 3360 t
( use count */)3 702( /*)1 648(int inuse;)1 756 3 1440 3470 t
( number of reads after hangup */)6 1728( /*)1 648(int hread;)1 756 3 1440 3580 t
( correlation with Chan */)4 1350( /*)1 702(int type;)1 702 3 1440 3690 t
( ... */)2 378( /*)1 756(int dev;)1 648 3 1440 3800 t
( ... */)2 378( /*)1 810(int id;)1 594 3 1440 3910 t
( read lock */)3 702( /*)1 594(QLock rdlock;)1 810 3 1440 4020 t
( write lock */)3 756( /*)1 594(QLock wrlock;)1 810 3 1440 4130 t
( write queue at process end */)6 1620( /*)1 594(Queue *procq;)1 810 3 1440 4240 t
( read queue at device end */)6 1512( /*)1 648(Queue *devq;)1 756 3 1440 4350 t
(};)1008 4460 w
( < \(q\) ? \(q->other\) : q\))6 1296( \(\(q\)->other)1 1188(#define RD\(q\))1 702 3 1008 4570 t
( > \(q\) ? \(q->other\) : q\))6 1296( \(\(q\)->other)1 1188(#define WR\(q\))1 702 3 1008 4680 t
( b\))1 162( \(*\(q\)->next->put\)\(\(q\)->next,)1 1728(#define PUTNEXT\(q,b\))1 1080 3 1008 4790 t
( - \(b\)->rptr\))2 702( \(\(b\)->wptr)1 1026(#define BLEN\(b\))1 810 3 1008 4900 t
( & QHIWAT\))2 540( \(\(q\)->flag)1 972(#define QFULL\(q\))1 864 3 1008 5010 t
( if\(QFULL\(q\)\) flowctl\(q\); })3 1458( {)1 378(#define FLOWCTL\(q\))1 972 3 1008 5120 t
cleartomark
showpage
saveobj restore
%%EndPage: 10 10
%%Trailer
done
%%Pages: 10
%%DocumentFonts: Courier Times-Bold Times-Italic Times-Roman Symbol