rfc150.txt

RFC 的详细文档！

Richard Bl. Kalin                            Network Working Group
MIT Lincoln Laboratory                       Request for Comments #150
5 May 1971                                   NIC 6754


THE USE OF IPC FACILITIES

***A WORKING PAPER***

This material has not been reviewed for public release and is intended
only for use within the ARPA network. It should not be quoted or cited
in any publication not related to the ARPA network.

INTRODUCTION

      It is our hypothesis that the goals of interprocess communication
are more complex than commonly realized, and that until this complexity
is more fully understood, there will be no satisfactory implementations.
The objective of an IPC design must be more than that of providing a
facility for moving bits between otherwise independent user programs, a
variety of other constraints must also be satisfied.

      These constraints are dictated by the eventual usage of the
facility. Any design that will sustain this usage pattern can be a
satisfactory one. If it does so efficiently, it will be said to be well
designed. Furthermore, it is unimaginable that a large design effort,
undertaken without a complete understanding of the usage it must serve,
will ever be well designed or even satisfactorily designed.

      This paper undertakes the exposition of the types of usage to
which an IPC facility would be subjected, in hopes that such a
discussion will clarify the goals being pursued and will provide a
benchmark for gauging various implementation strategies. The difficulty
of this task should not be underestimated. The only experience available
for us to draw upon is from very primitive and overly constrained IPC
implementations. Extrapolation from this limited usage environment to
more general notions has as yet no basis in real experience. Such
speculation is therefore subject to enormous oversight and misguided
perspective.

      In compiling this paper, it was necessary to imagine what services
a process might want from an IPC facility. The areas recognized include:
 1) the exchange of bit encoded information via channels.
 2) the establishment, deletion, and reassignment of these channels.
 3) the ability to debug errors and suspected errors.
 4) the potential to improve running efficiency.
 5) the capacity to avoid storage allocation deadlocks.
 6) the aided recovery from transmission errors.



                                                                [Page 1]

RFC #150                 Use of IPC Facilities                5 May 1971


This list is known to be incomplete. Some areas, such as understood to
be intelligently discussed. In other cases, omissions should be blamed
on simple oversight.

      Because of these obvious problems, one should not consider any
document of this kind as either authoritative or final. For this reason,
this paper is being kept as a computer based textfile, and so will
remain subject to editting and rerelease whenever new insights become
understood. We hope that it can remain an accurate and up to date
statement of the goals to which any group of IPC implementers can aspire
and, as such, can be a guidebook to the problems that must be faced.

      For several reasons no attempt shall be made here to design
suitable solutions to the problems raised. To be useful, such solutions
must be machine dependent. A so called 'general solution' would actually
be too clumsy and inefficient to be of any value. Secondly, we take the
point of view of the user, who need not be aware of the manner in which
his demands are carried out, so long as they can be accomplished.
Finally, we are trying to stay aloof from the eccentricities of present
day machine organization.

In our attempt to be implementation independent, we are admittedly
treading a fuzzy line. Our characterization of usage patterns presumes
both a system/process software organization and a computing milieu
capable of supporting it. Although this does not appear to significantly
affect the generality of the document, some care must be exercised in
the selection of host machines.

               *****

      In the rest of this paper, we attempt to characterize the types of
usage that should be anticipated by an IPC facility. The organization is
into titled sections, each section discussing some aspect of the
expected usage.

ABILITY TO USE VARIOUS SOURCES OF WAKEUP INFORMATION

      Most processes exhibit preferences toward certain quantities of
input data. This preference is reflected in the amount of computing time
that can be expended for a given amount of input. For example, a
character translation routine might prefer eight bit quantities of
input. With seven or less bits no processing is possible, but once a
complete character is available an entire translation cycle can
commence. This preference is independent of the function of the routine.
Otherwise equivalent routines could be written that would accept one bit
at a time. In other examples, a command interpreter might require a
complete line of input, a linking loader a complete file.




                                                                [Page 2]

RFC #150                 Use of IPC Facilities                5 May 1971


      Every executive system must face the problem of deciding at what
times enough input is available for a given routine for it to run
efficiently. This decision can not be taken lightly. Issuing a wakeup to
a dormant process carries with it considerable overhead -- room in core
storage must be made available, the program must be swapped into memory,
tables must be updated, active registers exchanged, and the entire
procedure done in reverse once the process has finished. To issue a
wakeup when there is insufficient input for the program is inefficient
and wasteful. The amount of computing that can be done does not justify
the overhead that must be expended.

      The problem of determining a priori the best time to issue a
wakeup has no general solution. It depends critically upon the
relationship between waiting costs and running costs. Attempts to make
reasonable predictions must contend with the tradeoff between accuracy
and overhead. The more system code that must be run, the more overhead
incurred and the less the final prediction means.

      Although there is no general solution, help is available to the
scheduler in specific cases. A commonly found instance is that of using
the receiving process to specify the number of bits that it is
expecting. Thus, a process may inform the supervisor/scheduler that it
requires fifty bits of input from some source before it is able to
continue. The process can then go into the shade and it will be awakened
when the required input is available.

      In cases where input lengths are predetermined, this technique is
quite satisfactory. Elsewhere, problems arise. In the case of unknown
input sizes, too short a prediction will give rise to the inefficiencies
of premature scheduling, and too long a prediction may produce input
deadlocks.

      Under these circumstances it is common to have the process tell
the scheduler a simple criterion that can be applied to determine if
there is sufficient input -- the appearance of a carriage return in the
teletype input stream, for example. The criterion is tested either by
system routines or by a low overhead user supplied routine (which in
turn must have a criterion of its own for being awakened).  Once the
criterion is met, the main routine is awakened and processing continues.

      Sometimes the system and user criteria work in conjunction with
one another. A user may specify an maximum character count,
corresponding to available buffer size, and the system may look for line
terminators. Wakeups to the user process may appear from either source.
At other times the system may preempt the user's criterion. For example,
if a process while trying to put a single character into a full buffer
is forced into shade, it will typically not be awakened again until
buffer has been almost emptied. Even though the user program only wished



                                                                [Page 3]

RFC #150                 Use of IPC Facilities                5 May 1971


room for a single character, the system imposed a much stronger
criterion, namely room for N characters, on the assumption other calls
to output characters will follow. Thus the program is forced into
outputting in bursts and, rather than going into the shade and being
awakened N times, each time when there is only room to output one
character, the program is awakened once and sends N characters. Program
efficiency is appropriately improved.

      A third source of criteria for deciding when to awaken the user
process is the device or routine that is producing the input data. This
source is frequently utilized in hardware design. Many computer
peripherals have the ability to send an end of record indication. For
variable length uninterpreted records this is an absolute necessity. For
fixed length records it is a convenient double check. In the world of
interprocess communication an analogous feature should be available. If
the routine that is generating the data knows how much the receiving
routine will require, then this information should be made available for
scheduling purposes. Implementing this requires a standardized way of
denoting logical boundaries on the stream of data flowing, through a
communication channel. The markers must be recognizable by the
scheduler/supervisor in the receiving host computer so that wakeups can
be issued as desired. To simplify the task of input interpretation,
marker pacement should also be visible to the receiving process.

      The data between boundaries we shall call a logical message, since
it is a natural unit of information exchange and since the markers
travel with the data through the channel. The additional information the
markers provide about data flow yield many useful consequences.
Consider, for example, two processes that always exchange 100 bit long
logical messages. If the receiving process is able to determine the
length of each logical message that arrives, there is available a simple
facility for error detection. If a 99 bit message arrives, it is obvious
that a bit has been dropped somewhere.

      It should be noted that it is not always possible for the
receiving process to compute the positions of boundary markers in the
input stream. there is no reason that the information implicit is marker
position must also be found as part of the coded input data. Even in
cases in which there is coding redundancy, it may be more difficult to
extract boundary information from the rest of the input than it is to
use the markers explicitly.

ABILITY TO SEND PARTS OF LOGICAL MESSAGES

      Any IPC facility, in which user storage is at all constrained, can
not require a process to send an entire logical message at one time. The
concept is only introduced to facilitate the issuing of wakeups to a
receiving process. What are convenient input quanta for the receiving



                                                                [Page 4]

RFC #150                 Use of IPC Facilities                5 May 1971


process may not be convenient output quanta for the sending one.
consider the case of a process running on a small machine and sending
messages to a process on a large task-multiplexed machine. For
efficiency, the receiving process requires large quantities of input
data at a time. Buffer space in the address space of the sending process
can not hold much data. The only answer is to allow the sending process
to dump its logical message in parts and with the last part to indicate
that it is the end of a message.

ABILITY TO RECEIVE A LOGICAL MESSAGE IN PARTS

      In the reverse of the above situation, a receiving process may not
have sufficient buffer space available to accept an entire message at
once. It should be possible under these circumstances to elect to accept
the message in parts. This is also necessary in the case of messages
that are too long to be buffered by the system. Unless part of the
message is accepted by the receiving process, the transmission can never
be completed. This device also serves for the removal of very long
messages that appear by error in the input stream.

ABILITY TO FIND OUT IF A MESSAGE CAN BE SENT

      If left unchecked, a routine can easily generate messages faster
than they can be consumed. Since any given amount of buffer capacity can
be quickly exhausted, there must be a way for the system to limit the
rate at which a process produces messages. This implies that at times a
process trying to send a message may be prevented from doing so because
of buffer inavailability. If the process is forced into the shade, the
pause should not come without warning. There should be a way for the
process to learn in advance if the message can be sent. A program may
have better things to do than wait for a buffer to become available.

ABILITY TO GET A GUARANTEE OF OUTPUT BUFFER SPACE

      A process should be able to get guarantee from the system that a
message of a certain size can be sent. This allows the process to know
before a computation is made that the results can be successfully
output. This allocation should remain either until it is depleted or
until it is changed by another allocation request.

      This particular user option is sure to raise the wrath of legions
of system programmers. From their point of view, the empty buffer space
that is being preallocated is necessarily being wasted. For although it
contains no messages, it is not available for other uses. The user, on
the other hand, does not correlate 'empty' with 'wasteful' nor 'full'
with 'efficient'. A process needs empty output buffers as much as it
needs full input ones. Both are resources necessary to sustain
processing.



                                                                [Page 5]

RFC #150                 Use of IPC Facilities                5 May 1971


ABILITY TO FIND OUT ABOUT OUTSTANDING MESSAGES

      A process that is sending messages over a channel should be able
to find out how many of those messages have not yet been accepted by the
user process at the far end and whether or not this number can decrease.
Ideally, it should also be able to determine the number of bits left in
any partially accepted message, but the overhead necessary to implement
this on conventional systems may be too great to be tolerated.

      The count returned can be useful both dynamically and for post
mortems. Used in debugging a remote process, it allows inputs on
normally concurrent channels to be presented one at a time and in any
given order. In this way one could, for example, verify that the same
results are produced regardless of the order in which the inputs arrive.

      If there is a failure of a receiving process, this mechanism
allows a sending process to determine the last input accepted before the
process died. Even between operational processes it provides a user
managed way for the transmitting process to slow down and let the