Movatterモバイル変換

Richard Bl. Kalin                            Network Working GroupMIT Lincoln Laboratory                       Request for Comments #1505 May 1971                                 NIC 6754THE USE OF IPC FACILITIES***A WORKING PAPER***This material has not been reviewed for public release and is intendedonly for use within the ARPA network. It should not be quoted or citedin any publication not related to the ARPA network.INTRODUCTION      It is our hypothesis that the goals of interprocess communicationare more complex than commonly realized, and that until this complexityis more fully understood, there will be no satisfactory implementations.The objective of an IPC design must be more than that of providing afacility for moving bits between otherwise independent user programs, avariety of other constraints must also be satisfied.      These constraints are dictated by the eventual usage of thefacility. Any design that will sustain this usage pattern can be asatisfactory one. If it does so efficiently, it will be said to be welldesigned. 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 towhich an IPC facility would be subjected, in hopes that such adiscussion will clarify the goals being pursued and will provide abenchmark for gauging various implementation strategies. The difficultyof this task should not be underestimated. The only experience availablefor us to draw upon is from very primitive and overly constrained IPCimplementations. Extrapolation from this limited usage environment tomore general notions has as yet no basis in real experience. Suchspeculation is therefore subject to enormous oversight and misguidedperspective.      In compiling this paper, it was necessary to imagine what servicesa 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 1971This list is known to be incomplete. Some areas, such as understood tobe intelligently discussed. In other cases, omissions should be blamedon simple oversight.      Because of these obvious problems, one should not consider anydocument of this kind as either authoritative or final. For this reason,this paper is being kept as a computer based textfile, and so willremain subject to editting and rerelease whenever new insights becomeunderstood. We hope that it can remain an accurate and up to datestatement of the goals to which any group of IPC implementers can aspireand, as such, can be a guidebook to the problems that must be faced.      For several reasons no attempt shall be made here to designsuitable solutions to the problems raised. To be useful, such solutionsmust be machine dependent. A so called 'general solution' would actuallybe too clumsy and inefficient to be of any value. Secondly, we take thepoint of view of the user, who need not be aware of the manner in whichhis demands are carried out, so long as they can be accomplished.Finally, we are trying to stay aloof from the eccentricities of presentday machine organization.In our attempt to be implementation independent, we are admittedlytreading a fuzzy line. Our characterization of usage patterns presumesboth a system/process software organization and a computing milieucapable of supporting it. Although this does not appear to significantlyaffect the generality of the document, some care must be exercised inthe selection of host machines.               *****      In the rest of this paper, we attempt to characterize the types ofusage that should be anticipated by an IPC facility. The organization isinto titled sections, each section discussing some aspect of theexpected usage.ABILITY TO USE VARIOUS SOURCES OF WAKEUP INFORMATION      Most processes exhibit preferences toward certain quantities ofinput data. This preference is reflected in the amount of computing timethat can be expended for a given amount of input. For example, acharacter translation routine might prefer eight bit quantities ofinput. With seven or less bits no processing is possible, but once acomplete character is available an entire translation cycle cancommence. This preference is independent of the function of the routine.Otherwise equivalent routines could be written that would accept one bitat a time. In other examples, a command interpreter might require acomplete 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 whattimes enough input is available for a given routine for it to runefficiently. This decision can not be taken lightly. Issuing a wakeup toa dormant process carries with it considerable overhead -- room in corestorage must be made available, the program must be swapped into memory,tables must be updated, active registers exchanged, and the entireprocedure done in reverse once the process has finished. To issue awakeup when there is insufficient input for the program is inefficientand wasteful. The amount of computing that can be done does not justifythe overhead that must be expended.      The problem of determining a priori the best time to issue awakeup has no general solution. It depends critically upon therelationship between waiting costs and running costs. Attempts to makereasonable predictions must contend with the tradeoff between accuracyand overhead. The more system code that must be run, the more overheadincurred and the less the final prediction means.      Although there is no general solution, help is available to thescheduler in specific cases. A commonly found instance is that of usingthe receiving process to specify the number of bits that it isexpecting. Thus, a process may inform the supervisor/scheduler that itrequires fifty bits of input from some source before it is able tocontinue. The process can then go into the shade and it will be awakenedwhen the required input is available.      In cases where input lengths are predetermined, this technique isquite satisfactory. Elsewhere, problems arise. In the case of unknowninput sizes, too short a prediction will give rise to the inefficienciesof premature scheduling, and too long a prediction may produce inputdeadlocks.      Under these circumstances it is common to have the process tellthe scheduler a simple criterion that can be applied to determine ifthere is sufficient input -- the appearance of a carriage return in theteletype input stream, for example. The criterion is tested either bysystem routines or by a low overhead user supplied routine (which inturn must have a criterion of its own for being awakened).  Once thecriterion is met, the main routine is awakened and processing continues.      Sometimes the system and user criteria work in conjunction withone another. A user may specify an maximum character count,corresponding to available buffer size, and the system may look for lineterminators. 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 bufferis forced into shade, it will typically not be awakened again untilbuffer has been almost emptied. Even though the user program only wished                                                                [Page 3]

RFC #150                 Use of IPC Facilities                5 May 1971room for a single character, the system imposed a much strongercriterion, namely room for N characters, on the assumption other callsto output characters will follow. Thus the program is forced intooutputting in bursts and, rather than going into the shade and beingawakened N times, each time when there is only room to output onecharacter, the program is awakened once and sends N characters. Programefficiency is appropriately improved.      A third source of criteria for deciding when to awaken the userprocess is the device or routine that is producing the input data. Thissource is frequently utilized in hardware design. Many computerperipherals have the ability to send an end of record indication. Forvariable length uninterpreted records this is an absolute necessity. Forfixed length records it is a convenient double check. In the world ofinterprocess communication an analogous feature should be available. Ifthe routine that is generating the data knows how much the receivingroutine will require, then this information should be made available forscheduling purposes. Implementing this requires a standardized way ofdenoting logical boundaries on the stream of data flowing, through acommunication channel. The markers must be recognizable by thescheduler/supervisor in the receiving host computer so that wakeups canbe 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, sinceit is a natural unit of information exchange and since the markerstravel with the data through the channel. The additional information themarkers provide about data flow yield many useful consequences.Consider, for example, two processes that always exchange 100 bit longlogical messages. If the receiving process is able to determine thelength of each logical message that arrives, there is available a simplefacility for error detection. If a 99 bit message arrives, it is obviousthat a bit has been dropped somewhere.      It should be noted that it is not always possible for thereceiving process to compute the positions of boundary markers in theinput stream. there is no reason that the information implicit is markerposition must also be found as part of the coded input data. Even incases in which there is coding redundancy, it may be more difficult toextract boundary information from the rest of the input than it is touse the markers explicitly.ABILITY TO SEND PARTS OF LOGICAL MESSAGES      Any IPC facility, in which user storage is at all constrained, cannot require a process to send an entire logical message at one time. Theconcept is only introduced to facilitate the issuing of wakeups to areceiving process. What are convenient input quanta for the receiving                                                                [Page 4]

RFC #150                 Use of IPC Facilities                5 May 1971process may not be convenient output quanta for the sending one.consider the case of a process running on a small machine and sendingmessages to a process on a large task-multiplexed machine. Forefficiency, the receiving process requires large quantities of inputdata at a time. Buffer space in the address space of the sending processcan not hold much data. The only answer is to allow the sending processto dump its logical message in parts and with the last part to indicatethat 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 nothave sufficient buffer space available to accept an entire message atonce. It should be possible under these circumstances to elect to acceptthe message in parts. This is also necessary in the case of messagesthat are too long to be buffered by the system. Unless part of themessage is accepted by the receiving process, the transmission can neverbe completed. This device also serves for the removal of very longmessages 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 fasterthan they can be consumed. Since any given amount of buffer capacity canbe quickly exhausted, there must be a way for the system to limit therate at which a process produces messages. This implies that at times aprocess trying to send a message may be prevented from doing so becauseof buffer inavailability. If the process is forced into the shade, thepause should not come without warning. There should be a way for theprocess to learn in advance if the message can be sent. A program mayhave 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 amessage of a certain size can be sent. This allows the process to knowbefore a computation is made that the results can be successfullyoutput. This allocation should remain either until it is depleted oruntil it is changed by another allocation request.      This particular user option is sure to raise the wrath of legionsof system programmers. From their point of view, the empty buffer spacethat is being preallocated is necessarily being wasted. For although itcontains no messages, it is not available for other uses. The user, onthe other hand, does not correlate 'empty' with 'wasteful' nor 'full'with 'efficient'. A process needs empty output buffers as much as itneeds full input ones. Both are resources necessary to sustainprocessing.                                                                [Page 5]

RFC #150                 Use of IPC Facilities                5 May 1971ABILITY TO FIND OUT ABOUT OUTSTANDING MESSAGES      A process that is sending messages over a channel should be ableto find out how many of those messages have not yet been accepted by theuser 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 inany partially accepted message, but the overhead necessary to implementthis on conventional systems may be too great to be tolerated.      The count returned can be useful both dynamically and for postmortems. Used in debugging a remote process, it allows inputs onnormally concurrent channels to be presented one at a time and in anygiven order. In this way one could, for example, verify that the sameresults are produced regardless of the order in which the inputs arrive.      If there is a failure of a receiving process, this mechanismallows a sending process to determine the last input accepted before theprocess died. Even between operational processes it provides a usermanaged way for the transmitting process to slow down and let thereceiver catch up with it. By pinpointing bottlenecks, it can be used todetect design mismatches.      Unless the channel has no outstanding messages or it is dead,there is the possibility that concurrently with the request thereceiving process will accept another message. This being the case, thecount returned can not be assumed to be exact but must be considered asonly an upper bound.ABILITY TO GET WAKEUPS WHEN MESSAGES ARE ACCEPTED      In conjunction with the above it should be possible for a userprocess to be alerted when the number of messages that have been sentover a particular channel and not accepted at the far end falls below aspecified threshold. Thus a process, upon discovering that twentymessages are still outstanding, can elect to enter the shade until thisnumber has fallen to less than five. By doing so the process can run in'burst mode'. Rather than being swapped in and out of core fifteen timesand each time being allowed to send one message, it is loaded once andsends fifteen messages. There is no penalty for doing this since thebottleneck on throughput is at the receiving process. If swapping costsfor the local process are significant, there may be considerableeconomic advantage to this mode of operation.      If the remote process dies or issues a channel 'close', the countof undelivered messages becomes frozen. If the receiving process isexpecting this type of wakeup, it should get one at this time eventhough the count has not reached the desired threshold. The process isthus alerted to do a postmortem on the channel.                                                                [Page 6]

RFC #150                 Use of IPC Facilities                5 May 1971ABILITY TO LEARN ABOUT MESSAGES QUEUED FOR INPUT      A process should be able to learn of the status of the Nth logicalmessage queued on a given input channel. It should a least be able todetermine if it is available, whether or not it is complete, how long itis and what it contains.      This facility allows a program to make general preparations beforeaccepting a message. It offers some escape from being put into theawkward position of having accepted input and not being able to disposeof it. If for example, it is known that processing the message willresult in two more messages being sent, then it is advantageous to getguarantees that the output can be generated before the input isaccepted.      Under circumstances in which one end of a channel is moved fromone process to another, for example, moving a teletype connectionbetween a user program and a debugging program, this ability to scanahead in the input stream allows a process to check whether or notpending input is really meant for it. If it is, the input will then beaccepted normally, otherwise, the end of the channel must be first movedto another receiving process.      Accepting input should be viewed as a grave responsibility, not tobe undertaken unless there is reasonable assurance that the input can beprocessed. One of the first rules of asynchronous system design is todetect errors as soon as possible. If propagated, the tangled resultsmay be hopeless to unravel.ABILITY TO LEARN HOW MANY MESSAGES ARE WAITING      A process should be able to determine how many messages areleft to be processed on a given input channel. Two uses are readilythought of. Given pending inputs on several channels a process should beable to exercise preference. One decision might be to take input firstfrom the channel with the most messages queued. This might have theeffect of increasing throughput since by freeing message buffers theremote transmitting process might be allowed to run. Another possibilitymight be that the receiving process has some control over the sendingprocess and, upon observing the backlog on inputs, it could tell thatprocess to slow down.      Assuming that the remote process is still able to send messages,the number of inputs reported is only a lower bound. New inputs may beadded concurrently. If the foreign process has died or has otherwiseclosed the connection then the bound can be made exact. The localprocess should be able to learn when it is exact.                                                                [Page 7]

RFC #150                 Use of IPC Facilities                5 May 1971GUARANTEE THAT INPUT WILL STAY AVAILABLE      This requirement states that if a process has been told that it isable to receive N messages on a given channel, that those messages arereally available and buffered within the host machine. If promised to auser process, messages should not mysteriously become unavailable. Anexample of how this might happen is illustrated inRFC60.  There, duringa panic for buffer space, messages are destroyed and reported as beingin error. They are later recovered from backup copies contained in theforeign host.ABILITY TO RECEIVE A WAKEUP WHEN INPUTS ARRIVE      A process should be able to enable a wakeup when the number ofmessages queued on an input channel exceeds a specified value or hasreached its maximum value. This allows a program to process input in aburst mode fashion and to economize on swapping costs. It also permitsinputs to be combined in a simple manner. If, for example, two inputsare needed before anything can be done, then the appropriate interruptcan be easily generated.      The same interrupt should be generated if the maximum number ofinputs have been received. Two cases are distinguished. Either theforeign process has closed the channel and is therefore not sending moremessages, or the system will not allocate more buffers until some inputis accepted. In this way the process can be informed that there is nopoint in waiting for the condition it anticipates.ABILITY TO SPECIFY SPECIAL WAKEUPS      A process, when trying to run efficiently, should be able tospecify arbitrarily complicated wakeup conditions. This allows a usermanaged way of minimizing the number of premature wakeups. Thisgenerality is perhaps most easily provided for by allowing the mainprocess to designate a small low overhead interrupt driven routine thatwill check for the desired conditions and issue a wakeup to the mainprocess whenever they are met.ABILITY TO MEASURE CHANNEL CAPACITY      There has been much discussion about the measure of a data streamand in the heat of committee, much confusion has been generated. It isour feeling that, within the present domain of discussion, there is nosingle measure of the capacity of a message channel. Two completelyorthogonal concepts must be measured -- 1) the number of messagesbuffered and 2) the number of bits of encoded data represented. Thesystem overhead associated with each is very much implementationdependent and hence no general equation can express the measure of one                                                                [Page 8]

RFC #150                 Use of IPC Facilities                5 May 1971in terms of the other. By making an arbitrary assumption (eg. a messageboundary equals 100 bits of buffer), a system runs the risk of excludingnew nodes that are unable to meet the old criterion.ABILITY TO FIND OUT MAXIMUM CHANNEL CAPACITY      There should be provided a system call that enables a user processto learn of the maximum current capacity of any given channel. Thisshould be reported as a pair of numbers, namely the maximum bit countand the maximum message count.ABILITY TO CONSTRAIN CHANNEL CAPACITY      A process using a channel should be able to set new bounds on thecapacity of a given channel. If possible the system should try to meetthis bound. It should be noted that the actual bounds imposed must meetthe constraints of at least four different sources -- local and remoteuser process, local and remote system -- by setting a arbitrarily highbound, no guarantee is made that it can be met. Similarly, a low boundcan not always be met until buffered messages are consumed.      Thus a receiving process, by setting the current message bound tozero, effectively disables the transmission of new messages. Thus,without the cooperation of the transmitting process, message generationcan be temporarily disabled, while outstanding message buffers areflushed. Later the message allocation can be raised to its originallimit and transmission can be resumed.ABILITY TO CLOSE A CHANNEL AT ANY TIME      A process should be able to close down a channel at any time. Ifthe process has died, the system should be able to close all openchannels for it. For channels over which the process was receiving data,pending input should be thrown away and indications returned to thetransmitting system marking the channel as dead and identifying the lastdata item accepted. This identification will be in terms of the numberof logical messages discarded and the number of bits left in the oldestmessage.      If a process closes a channel over which it had been sending,buffered output should be sent normally, and with it should be sent anindication that this is all of the input that will ever appear.                                                                [Page 9]

RFC #150                 Use of IPC Facilities                5 May 1971ABILITY TO GIVE AWAY CHANNEL PRIVILEGES      The right to perform any of the operations discussed here isnormally reserved by the process that established the channel. At timesthat process may wish to transfer some of its delegated power to anotherprocess, especially in an environment where one process may spawnanother and resources must be passed to the newly created process.      Schemes for such reassignment can become arbitrarily complicated.One could, for example, assign each of the various aspects of usageindividually and then separately assign the various rights ofreassignment. Fortunately it is not always necessary that it become soelaborate, it is expected that in most cases the following simplestrategy can suffice. The ability to close a channel is retainedexclusively by the process that established the channel. If the channelis still open when the process dies, it is automatically closed by thesystem. All other uses of the channel remain outside system control. Thechannel is known by name and all processes to which the name has beengiven may make use of the channel. It is left to user level coordinationto insure that only one process is actually making use of it at any onetime.ABILITY TO INITIATE CHANNEL CREATION      For most cases channel establishment can be handled quite simply.A process announces to its local system that it listening on aspecified channel. It is connected to the first remote process that'dials' the right number. Identification of the caller takes placeonly after the channel has been established. In the event of a wrongnumber, the channel can be closed and the listening resumed. Callerstrying to reach preestablished channels will get a 'busy signal'.      To 'dial' a remote process a process must specify a channel onwhich it is listening and a remote number. The system will thenattempt to establish the connection. The channel will become 'busy'during this time.      For processes that prefer to avoid the complications ofidentifying remote callers, an additional feature can be added. Byspecifying both the local and remote channel identifiers a process cantransfer to the system the responsibility for screening callers forthe proper identification. The connection will only be accepted fromthe caller specified.                                                                [Page 10]

RFC #150                 Use of IPC Facilities                5 May 1971ABILITY TO REPORT TRANSMISSION ERRORS      If after prescanning an input message a process should decidethat it contains some sort of transmission error, it should be able toreject the message. The system should then invoke any internal errorrecovery mechanism that it may have implemented.POSTSCRIPT      The author welcomes any comments, questions, or corrections tothis document. Even the most informal note or telephone call will beappreciated. Especially of interest are opinions about the usefulnessof the discussion and wether or not there should be more papersdirected at other of the basic questions of computer networking. Ifthe consensus tends to the affirmative, then others are encouraged tocontribute working papers on the problems of flow control, errorhandling, process ownership, accounting, resource control, and thelike.RBK/TX2         [ This RFC was put into machine readable form for entry ]         [ into the online RFC archives by Michael Baudisch 9/97 ]                                                                [Page 11]