![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to streams.ms CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10dc / vol2 / streams|
Return to streams.ms CVS log | Up to [Research Unix] / researchv10dc / vol2 / streams |
1.1 ! root 1: .so ../ADM/mac ! 2: .XX streams 503 "A Stream Input-Output System" ! 3: .TL ! 4: A Stream Input-Output System\(dg ! 5: .AU ! 6: Dennis M. Ritchie ! 7: .AI ! 8: .MH ! 9: .AB ! 10: In a new version of the ! 11: .UX ! 12: operating system, ! 13: a flexible coroutine-based design replaces the traditional ! 14: rigid connection between processes and terminals or networks. ! 15: Processing modules may be inserted dynamically into the stream ! 16: that connects a user's program to a device. ! 17: Programs may also connect directly to programs, providing ! 18: inter-process communication. ! 19: .AE ! 20: .2C ! 21: .FS ! 22: \(dgThis paper is a reproduction of |reference(bltj streams). ! 23: .FE ! 24: .NH ! 25: Introduction ! 26: .PP ! 27: The part of the ! 28: .UX ! 29: operating system that deals with terminals ! 30: and other character devices ! 31: has always been complicated. ! 32: In recent versions of the system it has become even more so, for ! 33: two reasons. ! 34: .IP 1) ! 35: Network connections require protocols more ornate than are ! 36: easily accommodated in the existing structure. ! 37: A notion of ``line disciplines'' was only partially successful, ! 38: mostly because in the traditional system only one line discipline ! 39: can be active at a time. ! 40: .IP 2) ! 41: The fundamental data structure of the traditional character I/O system, ! 42: a queue of individual characters (the ``clist''), ! 43: is costly because it accepts and dispenses characters one at a time. ! 44: Attempts to avoid overhead by bypassing the mechanism entirely ! 45: or by introducing ! 46: .I "ad hoc ! 47: routines succeeded in speeding up the ! 48: code at the expense of regularity. ! 49: .LP ! 50: Patchwork solutions to specific problems were ! 51: destroying the modularity of this part of the system. ! 52: The time was ripe to redo the whole thing. ! 53: This paper describes the new organization. ! 54: .PP ! 55: The system described here runs on about 20 machines ! 56: in the Information Sciences Research Division of Bell Laboratories. ! 57: Although it is being investigated by other parts of Bell Labs, ! 58: it is not generally available.* ! 59: .FS ! 60: *AT&T's UNIX System V Release 3 introduced a reimplementation ! 61: (in a commercially available system) ! 62: of the streams mechanisms described here. ! 63: This version was incomplete; for example, it did not contain a new ! 64: terminal-handling scheme. ! 65: UNIX System V Release 4 is intended to complete the streams ! 66: implementation. ! 67: The System V version of streams is called STREAMS, and though ! 68: considerably more ornate, is based on the same ideas that are ! 69: described here. ! 70: .FE ! 71: .NH ! 72: Overview ! 73: .PP ! 74: This section summarizes the nomenclature, components, and mechanisms ! 75: of the new I/O system. ! 76: .NH 2 ! 77: Streams ! 78: .PP ! 79: A ! 80: .I "stream ! 81: is a full-duplex connection between a user's process and a device ! 82: or pseudo-device. ! 83: It consists of several linearly connected processing modules, ! 84: and is analogous to a Shell pipeline, except that ! 85: data flows in both directions. ! 86: The modules in a stream communicate almost exclusively ! 87: by passing messages to their neighbors. ! 88: Except for some conventional variables used for flow control, modules do not ! 89: require access to the storage of their neighbors. ! 90: Moreover, a module provides only one entry point to each neighbor, namely ! 91: a routine that accepts messages. ! 92: .PP ! 93: At the end of the stream closest to the process ! 94: is a set of routines that provide the interface to the rest of the system. ! 95: A user's ! 96: .I "write ! 97: and ! 98: I/O control requests are turned into messages sent to the stream, ! 99: and ! 100: .I "read ! 101: requests take data from the stream and pass it to the user. ! 102: At the other end of the stream is a ! 103: device driver module. ! 104: Here, data arriving from the stream is sent to the device; ! 105: characters and state transitions detected by the device are ! 106: composed into messages and sent into the stream towards the user program. ! 107: Intermediate modules process the messages in various ways. ! 108: .PP ! 109: The two end modules in a stream become connected automatically when ! 110: the device is opened; ! 111: intermediate modules are attached dynamically by request of the user's program. ! 112: Stream processing modules are ! 113: symmetrical; their read and write interfaces are identical. ! 114: .NH 2 ! 115: Queues ! 116: .PP ! 117: Each stream processing module consists of a pair of ! 118: .I "queues, ! 119: one for each direction. ! 120: A queue comprises not only a data queue proper, but also two routines ! 121: and some status information. ! 122: One routine is the ! 123: .I "put procedure, ! 124: which is called by its neighbor ! 125: to place messages on the data queue. ! 126: The other, the ! 127: .I "service procedure, ! 128: is scheduled to execute whenever there is work for it to do. ! 129: The status information includes a pointer to the next queue downstream, ! 130: various flags, and a pointer to additional state information required ! 131: by the instantiation of the queue. ! 132: Queues are allocated in such a way that the routines associated with ! 133: one half of a stream module may find the queue associated with the other half. ! 134: (This is used, for example, in generating echos for terminal input.) ! 135: .NH 2 ! 136: Message blocks ! 137: .PP ! 138: The objects passed between queues are blocks obtained from an allocator. ! 139: Each contains a ! 140: .I "read pointer, ! 141: a ! 142: .I "write pointer, ! 143: and a ! 144: .I "limit pointer, ! 145: which specify respectively the beginning of information being passed, its end, ! 146: and a bound on the extent to which the write pointer may be increased. ! 147: .PP ! 148: The header of a block specifies its type; the most common blocks contain ! 149: data. ! 150: There are also control blocks of various kinds, ! 151: all with the same form as data blocks and obtained from the same ! 152: allocator. ! 153: For example, there are control blocks to introduce delimiters ! 154: into the data stream, to pass user I/O control requests, and to announce ! 155: special conditions such as line break and carrier loss on terminal ! 156: devices. ! 157: .PP ! 158: Although data blocks arrive in discrete units ! 159: at the processing modules, ! 160: boundaries between them are semantically insignificant; ! 161: standard subroutines may try to coalesce adjacent ! 162: data blocks in the same queue. ! 163: Control blocks, however, are never coalesced. ! 164: .NH 2 ! 165: Scheduling ! 166: .PP ! 167: Although each queue module behaves in some ways like a separate process, ! 168: it is not a real process; the system saves no state information ! 169: for a queue module that is not running. ! 170: In particular queue processing routines do not block when they cannot proceed, ! 171: but must explicitly return control. ! 172: A queue may be ! 173: .I "enabled ! 174: by mechanisms described below. ! 175: When a queue becomes enabled, the system will, as soon as convenient, ! 176: call its service procedure entry, ! 177: which removes successive blocks ! 178: from the associated data queue, processes them, and places them on the ! 179: next queue by calling its put procedure. ! 180: When there are no more blocks to process, or when the next queue becomes ! 181: full, the service procedure returns to the system. ! 182: Any special state information must be saved explicitly. ! 183: .PP ! 184: Standard routines make enabling of queue modules largely automatic. ! 185: For example, the routine that puts a block on a queue ! 186: enables the queue service routine if the queue was empty. ! 187: .NH 2 ! 188: Flow Control ! 189: .PP ! 190: Associated with each queue is a pair of numbers used for flow control. ! 191: A high-water mark limits the amount of data that may be outstanding ! 192: in the queue; by convention, modules do not place data on a queue ! 193: above its limit. ! 194: A low-water mark is used for scheduling in this way: ! 195: when a queue has exceeded its high-water mark, a flag is set. ! 196: Then, when the routine that takes blocks from a data queue notices ! 197: that this flag is set and that the queue has dropped below the low-water ! 198: mark, the queue upstream of this one is enabled. ! 199: .NH ! 200: Simple Examples ! 201: .PP ! 202: Figure 1 depicts a stream device that has just ! 203: been opened. ! 204: The top-level routines, drawn as a pair of half-open rectangles ! 205: on the left, are invoked by users' ! 206: .I read ! 207: and ! 208: .I write ! 209: calls. ! 210: The ! 211: writer ! 212: routine sends messages to the device driver shown on the right. ! 213: Data arriving from the device is composed ! 214: into messages sent to the top-level ! 215: reader ! 216: routine, which returns the data to the user process ! 217: when it executes ! 218: .I read . ! 219: .1C ! 220: .KF ! 221: .PS ! 222: boxht = boxht/1.5 ! 223: arrow "user" "write" ! 224: move up boxht/2 ! 225: line right boxwid/2 then down boxht then left boxwid/2 ! 226: move by (boxwid/2, boxht/2) ! 227: arrow right ! 228: line up boxht/2 ! 229: line right boxwid/2 ! 230: move down boxht ! 231: line left boxwid/2 then up boxht/2 ! 232: move right boxwid/2 ! 233: arrow "device" "out" ! 234: move down boxht ! 235: arrow left "device" "in" ! 236: move down boxht/2 ! 237: line left boxwid/2 then up boxht ! 238: move down boxht/2 ! 239: arrow left ! 240: move up boxht/2 ! 241: line down boxht then left boxwid/2 ! 242: move up boxht/2 ! 243: arrow left "user" "read" ! 244: .PE ! 245: .sp .5 ! 246: .ce ! 247: Figure 1. Configuration after device open. ! 248: .sp ! 249: .KE ! 250: .2C ! 251: .PP ! 252: Figure 2 shows an ordinary terminal connected by an RS-232 line. ! 253: Here a processing module (the pair of rectangles in the middle) is interposed; ! 254: it performs the services necessary to make terminals usable, ! 255: for example echoing, character-erase and line-kill, tab expansion ! 256: as required, and translation between carriage-return and new-line. ! 257: It is possible to use one of several terminal handling modules. ! 258: The standard one provides services like those of the Seventh ! 259: Edition system; ! 260: |reference(v7manual) ! 261: another resembles the Berkeley ``new tty'' driver. ! 262: |reference(bsdmanual) ! 263: .1C ! 264: .KF ! 265: .PS ! 266: arrow "user" "write" ! 267: move up boxht/2 ! 268: line right boxwid/2 then down boxht then left boxwid/2 ! 269: move by (boxwid/2, boxht/2) ! 270: arrow right ! 271: box "tty out"; arrow ! 272: line up boxht/2 ! 273: line right boxwid/2 ! 274: move down boxht ! 275: line left boxwid/2 then up boxht/2 ! 276: move right boxwid/2 ! 277: arrow "device" "out" ! 278: move down boxht ! 279: arrow left "device" "in" ! 280: move down boxht/2 ! 281: line left boxwid/2 then up boxht ! 282: move down boxht/2 ! 283: arrow left ! 284: box "tty in"; arrow ! 285: move up boxht/2 ! 286: line down boxht then left boxwid/2 ! 287: move up boxht/2 ! 288: arrow left "user" "read" ! 289: .PE ! 290: .sp .5 ! 291: .ce ! 292: Figure 2. Configuration for normal terminal attachment. ! 293: .sp ! 294: .KE ! 295: .2C ! 296: .PP ! 297: The processing modules in a stream are thought of as a stack whose ! 298: top (shown here on the left) is next to the user program. ! 299: Thus, to install the terminal processing module after opening ! 300: a terminal device, the program that makes ! 301: such connections executes a ``push'' I/O control call ! 302: naming the relevant stream and the desired processing module. ! 303: Other primitives pop a module from the stack ! 304: and determine the name of the topmost module. ! 305: .PP ! 306: Most of the machines using the version of the operating system ! 307: described here are connected to a network based on the ! 308: Datakit\(tm packet switch. ! 309: |reference(datakit asynchronous) ! 310: Although there is a variety of host interfaces to the network, ! 311: most of ours are primitive, and require network protocols ! 312: to be conducted by the host machine, rather than by a front-end ! 313: processor. ! 314: Therefore, when terminals are connected to a host through the network, ! 315: a setup like that shown in Fig. 3 is used; the terminal processing ! 316: module is stacked on the network protocol module. ! 317: Again, there is a choice of protocol modules, ! 318: both a current standard and an older protocol that is being phased ! 319: out. ! 320: .1C ! 321: .KF ! 322: .PS ! 323: arrow "user" "write" ! 324: move up boxht/2 ! 325: line right boxwid/2 then down boxht then left boxwid/2 ! 326: move by (boxwid/2, boxht/2) ! 327: arrow right ! 328: box "tty out"; arrow ! 329: box "proto out"; arrow ! 330: line up boxht/2 ! 331: line right boxwid/2 ! 332: move down boxht ! 333: line left boxwid/2 then up boxht/2 ! 334: move right boxwid/2 ! 335: arrow "device" "out" ! 336: move down boxht ! 337: arrow left "device" "in" ! 338: move down boxht/2 ! 339: line left boxwid/2 then up boxht ! 340: move down boxht/2 ! 341: arrow left ! 342: box "proto in"; arrow ! 343: box "tty in"; arrow ! 344: move up boxht/2 ! 345: line down boxht then left boxwid/2 ! 346: move up boxht/2 ! 347: arrow left "user" "read" ! 348: .PE ! 349: .sp .5 ! 350: .ce ! 351: Figure 3. Configuration for network terminals. ! 352: .sp ! 353: .KE ! 354: .2C ! 355: .PP ! 356: A common fourth configuration (not illustrated) is used when ! 357: the network is used for file transfers or other purposes ! 358: when terminal processing is not needed. ! 359: It simply omits the ``tty'' module and uses only the protocol module. ! 360: Some of our machines, on the other hand, have front-end processors programmed ! 361: to conduct standard network protocol. ! 362: Here a connection for remote file transfer will resemble ! 363: that of Fig. 1, because the protocol is handled outside the operating ! 364: system; likewise network terminal connections via the front end will be ! 365: handled as shown in Fig. 2. ! 366: .NH ! 367: Messages ! 368: .PP ! 369: Most of the messages between modules contain data. ! 370: The allocator that dispenses message blocks ! 371: takes an argument specifying the smallest block its caller ! 372: is willing to accept. ! 373: The current allocator maintains an inventory of blocks ! 374: 4, 16, 64, and 1024 characters long. ! 375: Modules that allocate blocks choose a size by balancing ! 376: space loss in block linkage overhead against unused space in the block. ! 377: For example, the top-level ! 378: .I write ! 379: routine requests either 64- or 1024-character blocks, ! 380: because such calls ! 381: usually transmit many characters; ! 382: the network input routine allocates 16-byte blocks because ! 383: data arrives in packets of that size. ! 384: The smallest blocks are used only to carry arguments to the ! 385: control messages discussed below. ! 386: .PP ! 387: Besides data blocks, there are also several kinds of control messages. ! 388: The following messages are queued along with data messages, ! 389: in order to ensure that their effect occurs at the appropriate time. ! 390: .IP BREAK 10 ! 391: is generated by a terminal device on detection of a line ! 392: break signal. ! 393: The standard terminal input processor turns this message into an interrupt ! 394: request. ! 395: It may also be sent to ! 396: a terminal device driver to cause it to generate a break on the output line. ! 397: .IP HANGUP ! 398: is generated by a device when its remote connection drops. ! 399: When the message arrives at the top level it is turned into an interrupt ! 400: to the process, and it also marks the stream so that ! 401: further attempts to use it return errors. ! 402: .IP DELIM ! 403: is a delimiter in the data. ! 404: Most of the stream I/O system is prepared to provide true streams, ! 405: in which record boundaries are insignificant, but there are ! 406: various situations in which it is desirable to delimit the data. ! 407: For example, terminal input is read a line at a time; ! 408: .SM DELIM ! 409: is generated by the terminal input processor to demarcate lines. ! 410: .IP DELAY ! 411: tells terminal drivers to generate a real-time delay ! 412: on output; it allows time for slow terminals react to characters previously ! 413: sent. ! 414: .IP IOCTL ! 415: messages are generated by users' ! 416: .I ioctl ! 417: system calls. ! 418: The relevant parameters are gathered at the top level, ! 419: and if the request is not understood there, it and its parameters ! 420: are composed into a message and sent down the stream. ! 421: The first module that understands the particular ! 422: request acts on it and returns a positive acknowledgement. ! 423: Intermediate modules that do not recognize a particular ! 424: .SM IOCTL ! 425: request pass it on; ! 426: stream-end modules return a negative acknowledgement. ! 427: The top-level routine waits for the acknowledgement, and returns ! 428: any information it carries to the user. ! 429: .LP ! 430: Other control messages are asynchronous and jump over ! 431: queued data and non-priority control messages. ! 432: .IP IOCACK 10 ! 433: .IP IOCNAK ! 434: acknowledge ! 435: .SM IOCTL ! 436: messages. ! 437: The device end of a stream must respond with one of these ! 438: messages; ! 439: the top level will eventually time out if no response is received. ! 440: .IP SIGNAL ! 441: messages are generated by the terminal processing module ! 442: and cause the top level to generate process signals such ! 443: as ! 444: .I quit ! 445: and ! 446: .I interrupt. ! 447: .IP FLUSH ! 448: messages are used to throw away data from input and output queues ! 449: after a signal or on request of the user. ! 450: .IP STOP ! 451: .IP START ! 452: messages are used by the terminal processor to halt and restart ! 453: output by a device, for example to implement the traditional ! 454: control-S/control-Q (X-on/X-off) flow control mechanism. ! 455: .1C ! 456: .KF top ! 457: .P1 ! 458: struct queue { ! 459: int flag; /* flag bits */ ! 460: void (*putp)(); /* put procedure */ ! 461: void (*servp)(); /* service procedure */ ! 462: struct queue *next; /* next queue downstream */ ! 463: struct block *first; /* first data block on queue */ ! 464: struct block *last; /* last data block on queue */ ! 465: int hiwater; /* max characters on queue */ ! 466: int lowater; /* wakeup point as queue drains */ ! 467: int count; /* characters now on queue */ ! 468: void *ptr; /* pointer to private storage */ ! 469: }; ! 470: .P2 ! 471: .ce ! 472: Figure 4. The queue data structure ! 473: .KE ! 474: .2C ! 475: .NH ! 476: Queue Mechanisms and Interfaces ! 477: .PP ! 478: Associated with each direction of a full-duplex stream module ! 479: is a queue data structure (somewhat simplified ! 480: for exposition) shown in Figure 4. ! 481: The ! 482: .CW flag ! 483: word contains several bits used by low-level routines to control ! 484: scheduling: they show whether the downstream module wishes to read data, ! 485: or the upstream module wishes to write, or the queue is already ! 486: enabled. ! 487: One bit is examined by the upstream module; it tells whether this ! 488: queue is full. ! 489: .PP ! 490: The ! 491: .CW first ! 492: and ! 493: .CW last ! 494: members point to the head and tail of a singly-linked list of ! 495: data and control blocks that form the queue proper; ! 496: .CW hiwater ! 497: and ! 498: .CW lowater ! 499: are initialized when the queue is created, and when compared against ! 500: .CW count, ! 501: the current size of the queue, determine whether the queue is full ! 502: and whether it has emptied sufficiently to enable a blocked writer. ! 503: .PP ! 504: The ! 505: .CW ptr ! 506: member stores an untyped pointer that may be used by the queue ! 507: module to keep track of the location of storage private ! 508: to itself. ! 509: For example, ! 510: each instantiation of the terminal processing module ! 511: maintains ! 512: a structure containing various mode bits and special characters; ! 513: it stores a pointer to this structure here. ! 514: The type of ! 515: .CW ptr ! 516: is artificial. ! 517: It should be a union of pointers to each possible module ! 518: state structure. ! 519: .1C ! 520: .KF bottom ! 521: .P1 ! 522: service(q) ! 523: struct queue *q ! 524: .sp .5 ! 525: while (q is not empty and q->next is not full) { ! 526: get a block from q ! 527: process message block ! 528: call q->next->putp to dispose of ! 529: new or transformed block ! 530: } ! 531: .P2 ! 532: .ce ! 533: Figure 5. Typical service routine ! 534: .KE ! 535: .2C ! 536: .PP ! 537: Stream processing modules are written in one of two general ! 538: styles. ! 539: In the simpler kind, the queue module acts nearly as a classical ! 540: coroutine. ! 541: When it is instantiated, it sets its put procedure ! 542: .CW putp ! 543: to a system-supplied default routine, and supplies a service ! 544: procedure ! 545: .CW servp . ! 546: Its upstream module disposes of blocks by calling this ! 547: module's ! 548: .CW putp ! 549: routine, which places the block on this module's queue (by ! 550: manipulating the ! 551: .CW first ! 552: and ! 553: .CW last ! 554: pointers.) ! 555: The standard put procedure also ! 556: enables the current module; ! 557: a short time later the current module's ! 558: service procedure ! 559: .CW servp ! 560: is called by the scheduler. ! 561: Figure 5 shows the pseudo-code, ! 562: for a typical service routine. ! 563: This mechanism is appropriate in cases in which messages can be ! 564: processed independently of each other. ! 565: For example, it is used by the terminal output module. ! 566: All the scheduling details are taken care of by standard routines. ! 567: .PP ! 568: More complicated modules need finer control over scheduling. ! 569: A good example is terminal input. ! 570: Here the device module upstream produces characters, usually one at a time, ! 571: that must be gathered into a line to allow for character erase and kill ! 572: processing. ! 573: Therefore the stream input module provides a put procedure to be called ! 574: by the device driver or other module downstream from it; ! 575: Figure 6 shows an outline ! 576: of this routine and its accompanying service procedure. ! 577: The put procedure generates the echo characters ! 578: as promptly as possible; ! 579: when the terminal module is attached to a ! 580: device handler, they are created during the input interrupt ! 581: from the device, because the put procedure is called as a subroutine ! 582: of the handler. ! 583: On the other hand, line-gathering and erase and kill processing, ! 584: which can be lengthy, are done during the service procedure ! 585: at lower priority. ! 586: .1C ! 587: .KF top ! 588: .P1 ! 589: putproc(q, bp) ! 590: struct queue *q; struct block *bp ! 591: .sp .5 ! 592: put bp on q ! 593: echo characters in bp's data ! 594: if (bp's data contains new-line or carriage return) ! 595: enable q ! 596: .sp ! 597: service(q) ! 598: struct queue *q ! 599: .sp .5 ! 600: take data from q until new-line or carriage return, ! 601: processing erase and kill characters ! 602: call q->next->putp to hand line to upstream queue ! 603: call q->next->putp with DELIM message ! 604: .P2 ! 605: .ce ! 606: Figure 6. A typical put routine ! 607: .SP ! 608: .KE ! 609: .2C ! 610: .NH ! 611: Connection with the Rest of the System ! 612: .PP ! 613: Although all the drivers for terminal and network devices, and all ! 614: protocol handlers, were rewritten, ! 615: only minor changes were required elsewhere in the system. ! 616: Character devices and a character device switch, ! 617: as described by Thompson|reference(thompson implementation bstj), ! 618: are still present. ! 619: A pointer in the character device switch structure, if null, ! 620: causes the system to treat the device as always; ! 621: this is used for raw disk and tape, for example. ! 622: If not null, it ! 623: points to initialization information for the stream device; ! 624: when a stream device is opened, the queue structure shown in Fig. 1 ! 625: is created, using this information, ! 626: and a pointer to the structure naming the stream is saved (in ! 627: the ``inode table;''|reference(thompson implementation bstj). ! 628: .PP ! 629: Subsequently, when the user process makes ! 630: .I read , ! 631: .I write , ! 632: .I ioctl , ! 633: or ! 634: .I close ! 635: calls, presence of a non-null stream pointer directs the ! 636: system to use a set of stream routines to generate and receive ! 637: queue messages; these are the ``top-level routines'' referred ! 638: to previously. ! 639: .PP ! 640: Only a few changes in user-level code are necessary, ! 641: most because opening a terminal puts it in the ! 642: ``very raw'' mode shown in Fig. 1. ! 643: In order to install the terminal-processing handler, ! 644: it is necessary for programs such as ! 645: .I init ! 646: to execute the appropriate ! 647: .I ioctl ! 648: call. ! 649: .NH ! 650: Interprocess Communication ! 651: .PP ! 652: As previously described, the stream I/O system constitutes a flexible ! 653: communication path between user processes and devices. ! 654: With a small addition, it also provides a mechanism for interprocess ! 655: communication. ! 656: A special device, the ``pseudo-terminal'' or ! 657: .SM PT , ! 658: connects processes. ! 659: .SM PT ! 660: files come in even-odd pairs; ! 661: data written on the odd member of the pair ! 662: appears as input for the even member, and vice versa. ! 663: The idea is not new; ! 664: it appears in Tenex|reference(bobrow burchfiel tenex) ! 665: and its successors, for example. ! 666: It is analogous to pipes, ! 667: and especially to named pipes.|reference(system iii manual) ! 668: .SM PT ! 669: files differ from traditional ! 670: pipes in two ways: ! 671: they are full-duplex, ! 672: and control information passes through them as well as data. ! 673: They differ from the usual pseudo-terminal files ! 674: |reference(bsdmanual) ! 675: by not having any of the usual ! 676: terminal processing mechanisms inherently attached to them; ! 677: they are pure transmitters of control and data messages. ! 678: .SM PT ! 679: files are adequate for setting up ! 680: a reasonably general mechanism for explicit process communication, ! 681: but by themselves are not especially interesting.* ! 682: .FS ! 683: *More recent research systems (Ninth and Tenth editions) drop ! 684: .SM PT ! 685: files altogether. ! 686: They use pipes where the name of the connection ! 687: is not needed, and `mounted streams' where a name is needed. ! 688: See |reference(latest presotto ipc). ! 689: .FE ! 690: .1C ! 691: .KF bottom ! 692: .PS ! 693: box invis height 2*boxht "device" "process" ! 694: move up boxht/2 ! 695: arrow right linewid/2 ! 696: move up boxht/2 ! 697: line right boxwid/2 then down boxht then left boxwid/2 ! 698: move by (boxwid/2, boxht/2) ! 699: arrow right ! 700: box "mesg"; arrow ! 701: line up boxht/2 ! 702: line right boxwid/2 ! 703: move down boxht ! 704: line invis left boxwid/4 "pt" ! 705: line left boxwid/4 then up boxht/2 ! 706: move right boxwid/2 ! 707: spline -> right boxwid then down 4*boxht then left boxwid ! 708: move down boxht/2 ! 709: line left boxwid/2 then up boxht ! 710: line right boxwid/4 ! 711: line invis right boxwid/4 "pt" ! 712: move by (-boxwid/2, -boxht/2) ! 713: arrow left ! 714: box "tty in"; arrow ! 715: move up boxht/2 ! 716: line down boxht then left boxwid/2 ! 717: move up boxht/2 ! 718: arrow left linewid/2 ! 719: move up boxht/2 ! 720: left ! 721: box invis height boxht*2 "user" "process" ! 722: move up boxht/2 ! 723: move right boxwid ! 724: arrow right linewid/2 ! 725: move up boxht/2 ! 726: line right boxwid/2 then down boxht then left boxwid/2 ! 727: move by (boxwid/2, boxht/2) ! 728: arrow right ! 729: box "tty out" ! 730: arrow right ! 731: move down boxht/2 ! 732: line up boxht then right boxwid/2 ! 733: move down boxht/2 ! 734: spline -> right boxwid/2 then up 2*boxht then left boxwid/2 ! 735: move down boxht/2 ! 736: line left boxwid/2 then up boxht ! 737: move down boxht/2 ! 738: arrow left ! 739: box "mesg" ! 740: arrow left ! 741: move up boxht/2 ! 742: line down boxht then left boxwid/2 ! 743: move up boxht/2 ! 744: arrow left linewid/2 ! 745: .PE ! 746: .sp .5 ! 747: .ce ! 748: Figure 7. Configuration for device simulator. ! 749: .sp ! 750: .KE ! 751: .2C ! 752: .PP ! 753: A special ! 754: .I message ! 755: module provides more intriguing possibilities. ! 756: In one direction, ! 757: the message processor takes control and data messages, such as those discussed ! 758: above, and transforms them into data blocks starting with a header giving ! 759: the message type, and followed by the message content. ! 760: In the other direction, it parses similarly-structured data messages ! 761: and creates the corresponding control blocks. ! 762: Figure 7 shows a configuration in which ! 763: a user process communicates through the terminal module, a ! 764: .SM PT ! 765: file pair, and the message module with another user-level process ! 766: that simulates a device driver. ! 767: Because ! 768: .SM PT ! 769: files are transparent, and the message module ! 770: maps bijectively between device-process data and stream control messages, ! 771: the device simulator may be completely faithful up to details ! 772: of timing. ! 773: In particular, user's ! 774: .I ioctl ! 775: requests are sent to the device process and are handled by it, ! 776: even if they are not understood by the operating system. ! 777: .PP ! 778: The usefulness of this setup is not so much to simulate new ! 779: devices, but to provide ! 780: ways for one program to control the environment ! 781: of another. ! 782: Pike|reference(blit bstj) ! 783: shows how these mechanisms are used to create ! 784: multiple virtual terminals on one physical terminal. ! 785: In another application, inter-machine connections in which ! 786: a user on one computer logs into another make use of the message module. ! 787: Here the ! 788: .I ioctl ! 789: requests generated by programs on the remote machine ! 790: are translated by this module into data messages that can be sent over ! 791: the network. ! 792: The local callout program translates them back into terminal control commands. ! 793: ...... ! 794: .NH ! 795: Evaluation ! 796: .PP ! 797: My intent in rewriting the character I/O system ! 798: was to improve its structure by separating functions ! 799: that had been intertwined, and by allowing independent modules ! 800: to be connected dynamically across well-defined interfaces. ! 801: I also wanted to make the system faster and smaller. ! 802: The most difficult part of the project was the design of the interface. ! 803: It was guided by these decisions: ! 804: .IP 1) ! 805: It seemed to be necessary for efficiency ! 806: that the objects passed between modules be references to blocks of data. ! 807: The most important consequences of this principle, and those ! 808: that proved deciding, are that data need not be copied as it passes ! 809: across a module interface, and that many characters can be handled ! 810: during a single intermodule transmission. ! 811: Another effect, undesirable but accepted, is that each module ! 812: must be prepared to handle discrete chunks of data of unpredictable size. ! 813: For example, a protocol that expects records containing (say) ! 814: an 8-byte header must be prepared to paste together smaller data blocks ! 815: and split a block containing both a header and following data. ! 816: A related, although not necessarily consequent, decision was to make ! 817: the code assume that the data is addressable. ! 818: .IP 2) ! 819: I decided, with regret, that each processing module ! 820: could not act as an independent process with its own call record. ! 821: The numbers seemed against it: on large systems it is necessary ! 822: to allow for as many as 1000 queues, and I saw no good way ! 823: to run this many processes without consuming inordinate amounts ! 824: of storage. ! 825: As a result, ! 826: stream server procedures are not allowed to block awaiting data, ! 827: but instead must return after saving necessary status information ! 828: explicitly. ! 829: The contortions required in the code are seldom serious in practice, ! 830: but the beauty of the scheme would increase if servers ! 831: could be written as a simple read-write loop in the true coroutine style. ! 832: .IP 3) ! 833: The characteristic feature of the design\-the server and put ! 834: procedures\-was the most difficult to work out. ! 835: I began with a belief that the intermodule interface ! 836: should be identical in the read and write directions. ! 837: Next, I observed that a pure call model (put procedure only) ! 838: would not work; ! 839: queueing would be necessary at some point. ! 840: For example, if the ! 841: .I write ! 842: system entry called through the terminal processing module to the device ! 843: driver, the driver would need to queue characters internally lest output ! 844: be completely synchronous. ! 845: On the other hand, a pure queueing model (service procedure only; ! 846: upstream modules always place their data in an input queue) ! 847: also appeared impractical. ! 848: As discussed above, a module (for example terminal input) ! 849: must often be activated at times that depend on its input data. ! 850: .PP ! 851: After considerable churning of details, the model presented here emerged. ! 852: In general its performance by various measures lives up to hopes. ! 853: .PP ! 854: The improvement in modularity is hard to measure, ! 855: but seems real; ! 856: for example, the number of ! 857: included header ! 858: files in stream modules drops to about one half of those required ! 859: by similar routines in the base system ! 860: (4.1 BSD). ! 861: Certainly stream modules may be composed more freely ! 862: than were the ``line disciplines'' of older systems. ! 863: .PP ! 864: The program text size of the version of the operating ! 865: system described here is about 106 kilobytes on the VAX; ! 866: the base system was about 130KB. ! 867: The reduction was achieved by rewriting the various device drivers ! 868: and protocols and eliminating the Seventh Edition ! 869: multiplexed files ! 870: |reference(v7manual) ! 871: , most (though not all) ! 872: of whose functions are subsumed by other mechanisms. ! 873: On the other hand, the data space has increased. ! 874: On a VAX 11/750 configured for 32 users ! 875: about 32KB are used for storage of the structures for streams, ! 876: queues, and blocks. ! 877: The traditional character lists seem to require less; ! 878: similar systems from Berkeley and AT&T use between 14 and 19KB. ! 879: The tradeoff of program for data seems desirable. ! 880: .PP ! 881: Proper time comparisons ! 882: have not been made, ! 883: because of the difficulty of finding a comparable configuration. ! 884: On a VAX 11/750, ! 885: printing a large file on a directly-connected terminal ! 886: consumes 346 microseconds per character using the system described here; ! 887: this is about 10 per cent slower than the base system. ! 888: On the other hand, that system's per-character interrupt routine is ! 889: coded in assembly language, and the rest of its terminal handler ! 890: is replete with nonportable ! 891: interpolated assembly code; ! 892: the current system is written completely in C. ! 893: Printing the same file on a terminal connected through a primitive ! 894: network interface requires 136 microseconds per character, ! 895: half as much as the older network routines. ! 896: Pike ! 897: |reference(blit bstj) ! 898: observes that among the three implementations of Blit connection software, ! 899: the one based on the stream system is the only one that can download programs ! 900: at anything approaching line speed through a 19.2 Kbps connection. ! 901: In general I conclude that the new organization ! 902: never slows comparable tasks much, and that considerable speed improvements ! 903: are sometimes possible. ! 904: .PP ! 905: Although the new organization performs well, it has several peculiarities ! 906: and limitations. ! 907: Some of them seem inherent, some are fixable, ! 908: and some are the subject of current work. ! 909: .PP ! 910: I/O control calls turn into messages that require answers ! 911: before a result can be returned to the user. ! 912: Sometimes the message ultimately goes to another user-level process ! 913: that may reply tardily or never. ! 914: The stream is write-locked until the reply returns, in order ! 915: to eliminate the need to determine which process gets which reply. ! 916: A timeout breaks the lock, ! 917: so there is an unjustified error return if a reply ! 918: is late, and a long lockup period if one is lost. ! 919: The problem can be ameliorated by working harder on it, but ! 920: it typifies the difficulties that turn up when direct calls are replaced ! 921: by message-passing schemes. ! 922: .PP ! 923: Several oddities appear because time spent in server routines ! 924: cannot be assigned to any particular user or process. ! 925: It is impossible, for example, for devices to support privileged ! 926: .I ioctl ! 927: calls, because the device has no idea who generated the message. ! 928: Accounting and scheduling become less accurate; ! 929: a short census of several systems showed that between 4 and 8 per cent ! 930: of non-idle CPU time was being spent in server routines. ! 931: Finally, the anonymity of server processing most certainly makes ! 932: it more difficult to measure the performance of the new I/O system. ! 933: .PP ! 934: In its current form the stream I/O system is purely data-driven. ! 935: That is, data is presented by a user's ! 936: .I write ! 937: call, and passes through to the device; conversely, data appears unbidden ! 938: from a device and passes to the top level, where it is picked up by ! 939: .I read ! 940: calls. ! 941: Wherever possible flow control throttles down fast ! 942: generators of data, but nowhere except at the consumer end of a stream ! 943: is there knowledge of precisely how much data is desired. ! 944: Consider a command to execute possibly interactive program on another ! 945: machine connected by a stream. ! 946: The simplest such command sets up the connection ! 947: and invokes the remote program, and then copies characters from its ! 948: own standard input to the stream, and from the stream to its standard ! 949: output. ! 950: The scheme is adequate in practice, ! 951: but breaks when the user types more than the remote program expects. ! 952: For example, if the remote program reads no input at all, ! 953: any typed-ahead characters are sent to the remote system and lost. ! 954: This demonstrates a problem, ! 955: but I know of no solution inside the stream I/O mechanism itself; ! 956: other ideas will have to be applied. ! 957: .PP ! 958: Streams are linear connections; by themselves, they support no notion ! 959: of multiplexing, fan-in or fan-out. ! 960: Except at the ends of a stream, each invocation of a module has ! 961: a unique ``next'' and ``previous'' module. ! 962: Two locally-important applications ! 963: of streams testify to the importance of multiplexing: ! 964: Blit terminal connections ! 965: |reference(blit bstj) ! 966: , where the multiplexing is done well, though at some performance cost, ! 967: by a user program, ! 968: and remote execution of commands over a network, ! 969: where it is desired, but not now easy, ! 970: to separate the standard output from error output. ! 971: It seems likely that a general multiplexing mechanism ! 972: could help in both cases, but again, I do not yet know how to ! 973: design it.* ! 974: .FS ! 975: *Subsequent Research versions of the system still do not ! 976: have a general stream-multiplexing scheme built into the ! 977: kernel, while the System V streams implementations do. ! 978: We have not found any applications that suffer from the ! 979: lack of stream-multiplexing. ! 980: .FE ! 981: .PP ! 982: Although the current design provides elegant means for controlling ! 983: the semantics of communication channels already opened, it lacks ! 984: general ways of establishing channels between processes. ! 985: The ! 986: .SM PT ! 987: files described above are just fine for ! 988: Blit layers, ! 989: and work adequately for handling a few administrator-controlled ! 990: client-server relationships. ! 991: (Yes, we have multi-machine mazewar.) ! 992: Nevertheless, better naming mechanisms are called for.\(dg ! 993: .FS ! 994: \(dgSee |reference(latest presotto ipc) ! 995: for our current ideas. ! 996: .FE ! 997: .PP ! 998: In spite of these limitations, the stream I/O system works well. ! 999: Its aim was to improve design rather than to add features, ! 1000: in the belief that with proper design, the features come cheaply. ! 1001: This approach is arduous, but continues to succeed. ! 1002: .NH ! 1003: References ! 1004: .LP ! 1005: |reference_placement
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.