rfc62.txt

来自「RFC 的详细文档！」· 文本 代码 · 共 1,123 行 · 第 1/4 页

Network Working Group                                       D. C. Walden
Request for Comments: 62                                        BBN Inc.
Supercedes NWG/RFC #61                                     3 August 1970


                A System for Interprocess Communication
                                 in a
                   Resource Sharing Computer Network

1.  Introduction

   If you are working to develop methods of communications within a
   computer network, you can engage in one of two activities.  You can
   work with others, actually constructing a computer network, being
   influenced, perhaps influencing your colleagues.  Or you can
   construct an intellectual position of how things should be done in an
   ideal network, one better than the one you are helping to construct,
   and then present this position for the designers of future networks
   to study.  The author has spent the past two years engaged in the
   first activity.  This paper results from recent engagement in the
   second activity.

   "A resource sharing computer network is defined to be a set of
   autonomous, independent computer systems, interconnected so as to
   permit each computer system to utilize all of the resources of the
   other computer systems much as it would normally call a subroutine."
   This definition of a network and the desirability of such a network
   is expounded upon by Roberts and Wessler in [9].

   The actual act of resource sharing can be performed in two ways:  in
   an ad hoc manner between all pairs of computer systems in the
   network; or according to a systematic network-wide standard.  This
   paper develops one possible network-wide system for resource sharing.

   I believe it is natural to think of resources as being associated
   with processes<1> and available only through communication with these
   processes.  Therefore, I view the fundamental problem of resource
   sharing to be the problem of interprocess communication.  I also
   share with Carr, Crocker, and Cerf [2] the view that interprocess
   communication over a network is a subcase of general interprocess
   communication in a multi-programmed environment.

   These views have led me to perform a two-part study.  First, a set of
   operations enabling interprocess communication within a single time-
   sharing system is constructed.  This set of operations eschews many
   of the interprocess communications techniques currently in use within
   time-sharing systems -- such as communication through shared memory
   -- and relies instead on techniques that can be easily generalized to



Walden                                                         [Page 1]

RFC 62                  IPC for Resource Sharing          3 August 1970


   permit communication between remote processes.  The second part of
   the study presents such a generalization.  The application of this
   generalized system to the ARPA Computer Network [9] is also
   discussed.

   The ideas enlarged upon in this paper came from many sources.
   Particularly influential were -- 1) an early sketch of a Host
   protocol for the ARPA Network by S. Crocker of UCLA and W. Crowther
   of Bolt Beranek and Newman Inc. (BBN); 2) Ackerman and Plummer's
   paper on the MIT PDP-1 time-sharing system [1]; and 3) discussions
   with W. Crowther and R. Kahn of BBN about Host protocol, flow
   control, and message routing for the ARPA Network.  Hopefully, there
   are also some original ideas in this note.  I alone am responsible
   for the collection of all of these ideas into the system described
   herein, and I am therefore responsible for any inconsistencies or
   bugs in the system.

   It must be emphasized that this paper does not represent an official
   BBN position on Host protocol for the ARPA Computer Network.


2.  A System for Interprocess Communication within a Time-Sharing System

   This section describes a set of operations enabling interprocess
   communication within a time-sharing system.  Following the notation
   of [10], I call this interprocess communication facility an IPC.  As
   an aid to the presentation of this IPC, a model for a time-sharing
   system is described; this model is then used to illustrate the use of
   the interprocess communication operations.

   The model time-sharing has two pieces: the monitor and the processes.
   The monitor performs such functions as switching control from one
   process to another process when a process has used "enough" time,
   fielding hardware interrupts, managing core and the swapping medium,
   controlling the passing of control from one process to another (i.e.,
   protection mechanisms), creating processes,caring for sleeping
   processes, and providing to the processes a set of machine extending
   operations (often called Supervisor or Monitor Calls).  The processes
   perform the normal user functions (user processes) as well as the
   functions usually thought of as being supervisor functions in a
   time-sharing system (systems processes) but not performed by the
   monitor in the current model.  A typical system process is the disc
   handler or the file system.  System processes is the disc handler or
   the file system.  System processes are probably allowed to execute in
   supervisor mode, and they actually execute I/O instructions and
   perform other privileged operations that user processes are not
   allowed to perform.  In all other ways, user and system processes are
   identical.  For reasons of efficiency, it may be useful to think of



Walden                                                         [Page 2]

RFC 62                  IPC for Resource Sharing          3 August 1970


   system processes as being locked in core.

   Although they will be of concern later in this study, protection
   considerations are not my concern here: instead I will assume that
   all of the processes are "good" processes which never made any
   mistakes.  If the reader needs a protection structure to keep in mind
   while he reads this note, the capability system developed in
   [1][3][7][8] should be satisfying.

   Of the operations a process can call on the monitor to perform, six
   are of particular interest for providing a capability for
   interprocess communication.

   RECEIVE. This operation allows a specified process to send a message
   to the process executing the RECEIVE. The operation has four
   parameters: the port (defined below) awaiting the message -- the
   RECEIVE port; the port a message will be accepted from -- the SEND
   port; a specification of the buffer available to receive the message;
   and a location to transfer to when the transmission is complete --
   the restart location.

   SEND.  This operation sends a message from the process executing the
   SEND to a specified process.  It has four parameters: a port to send
   the message to -- the RECEIVE port; the port the message is being
   sent from -- the SEND port; a specification of the buffer containing
   the message to be sent; and the restart location.

   RECEIVE ANY.  This operations allows any process to send a message to
   the process executing the RECEIVE ANY.  The operation has four
   parameters: the port awaiting the message -- the RECEIVE port; a
   specification of the buffer available to receive the message; a
   restart location; and a location where the port which sent the
   message may be noted.

   SEND FROM ANY.  This operation allows a process to send a message to
   a process able to receive a message from any process.  It has the
   same four parameters as SEND.  (The necessity for this operation will
   be explained much later).

   SLEEP.  This operation allows the currently running process to put
   itself to sleep pending the completion of an event.  The operation
   has one optional parameter, an event to be waited for.  An example
   event is the arrival of a hardware interrupt.  The monitor never
   unilaterally puts a process to sleep as a result of the process
   executing one of the above four operations; however, if a process is
   asleep when one of the above four operations is satisfied, the
   process is awakened.




Walden                                                         [Page 3]

RFC 62                  IPC for Resource Sharing          3 August 1970


   UNIQUE.  This operation obtains a unique number from the monitor.

   A port is a particular data path to a process (a RECEIVE port) or
   from a process (a SEND port), and all ports have an associated unique
   port number which is used to identify the port.  Ports are used in
   transmitting messages from one process to another in the following
   manner.  Consider two processes, A and B, that wish to communicate.
   Process A executes a RECEIVE to port N from port M.  Process B
   executes a SEND to port N from port M.  The monitor matches up the
   port numbers and transfers the message from process B to process A.
   As soon as the buffer has been fully transmitted out of process B,
   process B is restarted at the location specified in the SEND
   operation.  As soon as the message is fully received at process A,
   process A is restarted at the location specified in the RECEIVE
   operation.  Just how the processes come by the correct port numbers
   with which to communicate with other processes is not the concern of
   the monitor -- this problem is left to the processes.

   When a SEND is executed, nothing happens until a matching RECEIVE is
   executed.  Somewhere in the monitor there must be a table of port
   numbers associated with processes and restart locations.  The table
   entries are cleared after each SEND/RECEIVE match is made.  If a
   proper RECEIVE is not executed for some time, the SEND is timed out
   after a while and the SENDing process is notified.  If a RECEIVE is
   executed but the matching SEND does not happen for a long time, the
   RECEIVE is timed out and the RECEIVing process is notified.

   The mechanism of timing out "unused" table entries is of little
   fundamental importance, merely providing a convenient method of
   garbage collecting the table.  There is no problem if an entry is
   timed out prematurely, because the process can always re-execute the
   operation.  However, the timeout interval should be long enough so
   that continual re-execution of an operation will cause little
   overhead.

   A RECEIVE ANY never times out, but may be taken back using a
   supervisor call.  A message resultant from a SEND FROM ANY is always
   sent immediately and will be discarded if a proper receiver does not
   exist.  An error message is not returned and acknowledgment, if any,
   is up to the processes.  If the table where the SEND and RECEIVE are
   matched up ever overflows, a process originating a further SEND and
   RECEIVE is notified just as if the SEND or RECEIVE timed out.

   The restart location is an interrupt entrance associated with a
   pseudo interrupt local to the process executing the operation
   specifying the restart location.  If the process is running when then
   event causing the pseudo interrupt occurs (for example, a message
   arrives satisfying a pending RECEIVE), the effect is exactly as if



Walden                                                         [Page 4]

RFC 62                  IPC for Resource Sharing          3 August 1970


   the hardware interrupted the process and transferred control to the
   restart location.  Enough information is saved for the process to
   continue execution at the point it was interrupted after the
   interrupt is serviced.  If the process is asleep, it is readied and
   the pseudo interrupt is saved until the process runs again and the
   interrupt is then allowed.  Any RECEIVE or RECEIVE ANY message port
   may thus be used to provide process interrupts, event channels,
   process synchronization, message transfers, etc.  The user programs
   what he wants.

   It is left as an exercise to the reader to convince himself that the
   monitor he is saddled with can be made to provide the six operations
   described above -- most monitors can since these are only additional
   supervisor calls.

   An example.  Suppose that our model time-sharing system is
   initialized to have several processes always running.  Additionally,
   these permanent processes have some universally known and permanently
   assigned ports<2>.  Suppose that two of the permanently running
   processes are the logger-process and the teletype-scanner-process.
   When the teletype-scanner-process first starts running, it puts
   itself to sleep awaiting an interrupt from the hardware teletype
   scanner.  The logger-process initially puts itself to sleep awaiting
   a message from the teletype-scanner-process via well-known permanent
   SEND and RECEIVE ports.  The teleype-scanner-process keeps a table
   indexed by teletype number, containing in each entry a pair of port
   numbers to use to send characters from that teletype to a process and
   a pair of port numbers to use to receive characters for that teletype
   from a process.  If a character arrives (waking up the teletype-
   scanner- process) and the process does not have any entry for that
   teletype, it gets a pair of unique numbers from the monitor (via
   UNIQUE) and sends a message containing this pair of numbers to the
   logger-process using the ports for which the logger-process is known
   to have a RECEIVE pending.  The scanner-process also enters the pair
   of numbers in the teletype table, and sends the character and all
   future characters from this teletype to the port with the first
   number from the port with the second number.  The scanner-process
   must also pass a second pair of unique numbers to the logger-process
   for it to use for teletype output and do a RECEIVE using these port
   numbers.  When the logger-process receives the message from the
   scanner-process, it starts up a copy of what SDS 940 TSS [6] users
   call the executive<3>, and passes the port numbers to this copy of
   the executive, so that this executive-process can also do its inputs
   and outputs to the teletype using these ports.  If the logger-process
   wants to get a job number and password from the user, it can
   temporarily use the port numbers to communicate with the user before
   it passes them on to the executive.  The scanner-process could always
   use the same port numbers for a particular teletype as long as the