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 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.

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 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 numbers were passed on to only one copy of the executive at a time.

It is important to distinguish between the act of passing a port from one process to another and the act of passing a port number from one process to another. In the previous example, where characters from a particular teletype are sent either to the logger-process or an executive-process by the teletype-scanner-process, the SEND port always remains in the teletype-scanner-process while the RECEIVE port moves from the logger-process to the executive process. On the other hand, the SEND port number is passed between the logger-process and the executive-process to enable the RECEIVE process to do a RECEIVE from the correct SEND port. It is crucial that, once a process transfers a port to some other process, the first process no longer use the port. We could add a mechanism that enforces this. The protected object system of [9] is one such mechanism. Using this mechanism, a process executing a SEND would need a capability for the SEND port and only one capability for this SEND port would exist in the system at any given time. A process executing a RECEIVE would be required to have a capability for the RECEIVE port, and only one capability for this RECEIVE port would exist at a given time. Without such a protection mechanism, a port implicitly moves from one process to another by the processes merely using the port at disjoint times even if the port's number is never explicitly passed.

Of course, if the protected object system is available to us, there is really no need for two port numbers to be specified before a transmission can take place. The fact that a process knows an existing RECEIVE port number could be considered prima facie evidence of the process' right to send to that port. The difference between RECEIVE and RECEIVE ANY ports then depends solely on the number of copies of a particular port number that have been passed out. A system based on this approach would clearly be preferable to the one described here if it was possible to assume that all autonomous time-sharing systems in a network would adopt this protection mechanism. If this assumption cannot be made, it seems more practical to require both port numbers.

Note that in the interprocess communication system (IPC) being described here, when two processes wish to communicate they set up the connection themselves, and they are free to do it in a mutually convenient manner. For instance, they can exchange port numbers or one process can pick all the port numbers and instruct the other process which to use. However, in a particular implementation of a time-sharing system, the builders of the system might choose to restrict the processes' execution of SENDs and RECEIVEs and might forbid arbitrary passing around of ports and port numbers, requiring instead that the monitor be called (or some other special program) to perform these functions.

Flow control is provided in this IPC by the simple method of never starting data transmission resultant from a SEND from one process until a RECEIVE is executed by the receiver. Of course, interprocess messages may also be sent back and forth suggesting that a process stop sending or that space be allocated.

Generally, well-known permanently-assigned ports are used via RECEIVE ANY and SEND FROM ANY. The permanent ports will most often be used for starting processes and, consequently, little data will be sent via them. If a process if running (perhaps asleep), and has a RECEIVE ANY pending, then any process knowing the receive port number can talk to that process without going through loggers. This is obviously essential within a local time-sharing system and seems very useful in a more general network if the ideal of resource sharing is to be reached. For instance, in a resource sharing network, the programs in the subroutine libraries at all sites might have RECEIVE ANYs always pending over permanently assigned ports with well-known port numbers. Thus, to use a particular network resource such as a matrix manipulation hardware, a process running anywhere in the network can send a message to the matrix inversion subroutine containing the matrix to be inverted and the port numbers to be used for returning the results.

An additional example demonstrates the use of the FORTRAN compiler. We have already explained how a user sits down at his teletype and gets connected to an executive. We go on from there. The user is typing in and out of the executive which is doing SENDs and RECEIVEs. Eventually the user types RUN FORTRAN, and executive asks the monitor to start up a copy of the FORTRAN compiler and passes to FORTRAN as start up parameters the port numbers the executive was using to talk to the teletype. (This, at least conceptually, FORTRAN is passed a port at which to RECEIVE characters from the teletype and a port from which to SEND characters to the teletype.) FORTRAN is, of course, expecting these parameters and does SENDs and RECEIVEs via the indicated ports to discover from the user what input and output files the user wants to use. FORTRAN types INPUT FILE? to the user, who responds F001. FORTRAN then sends a message to the file-system-process, which is asleep waiting for something to do. The message is sent via well-known ports and it asks the file system to open F001 for input. The message also contains a pair of port numbers that the file-system process can use to send its reply. The file-system looks up F001, opens it for input, make some entries in its open file tables, and sends back to FORTRAN a message containing the port numbers that FORTRAN can use to read the file. The same procedure is followed for the output file. When the compilation is complete, FORTRAN returns the teletype port numbers (and the ports) back to the executive that has been asleep waiting for a message from FORTRAN, and then FORTRAN halts itself. The file-system-process goes back to sleep when it has nothing else to do<4>.

Again, the file-system process can keep a small collection of port numbers which it uses over and over if it can get file system users to return the port numbers when they have finished with them. Of course, when this collection of port numbers has eventually dribbled away, the file system can get some new unique numbers from the monitor.