A Model for a Time-Sharing System

This section describes a model time-sharing system which I think is particularly suitable for performing interprocess communication. The basic structure of this model time-sharing system is not original [5][9].

The model time-sharing system has two pieces: the monitor and the processes. The monitor performs several functions, including switching control from process to process as appropriate (e.g., when a process has used "enough" time or when an interrupt occurs), 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, etc.

The processes perform most of the functions normally thought of as being supervisor functions in a time-sharing system (system processes) as well as the normal user functions (user processes). A typical system process is the disc handler or the file system. For efficiency reasons it may be useful to think of system processes as being locked in core.

A process can call on the monitor to perform several functions: start another, equal, autonomous process (i.e., load a program or find a copy of a program somewhere that can be shared, start it, and pass it some initial parameters); halt the running process; put the current process to sleep pending a specified event; send a message to a specified process; become available to receive a message from a specified process; become available to receive a message from any process; send a message to a process able to receive from any process; and request a unique number. There undoubtedly should also be other monitor functions. It is left as an exercise to the reader to convince himself that the monitor he is saddled with can be made to provide these functions -- most can.

I will not concern myself with protection considerations here, but instead will assume all of the processes are "good" processes which never make any mistakes. If the reader needs a protection structure to keep in mind while he reads this note, the capability system described in [5][6][7][8] should be satisfying.

We now look a little closer at the eight operations listed above that a process can ask the monitor to perform.

START. This operation starts another process. It has two parameters -- some kind of identification for the program that is to be loaded and a parameter list for that program. Once the program is loaded, it is started at its given entry point and passed its parameter list in some well known manner. The process will continue to exist until it halts itself.

HALT. This operation puts the currently running process to sleep pending the completion of some event. The operation has one parameter, the event to be waited for. Sample events are arrival of a hardware interrupt, arrival of a message from another process, etc. The process is restarted at the instruction after the SLEEP command. The monitor never unilaterally puts a process to sleep except when the process overflows its quantum.

RECEIVE. This operation allows another process to send a message to this process. The operation has four parameters: the port (defined below) awaiting the message, the port a message will be accepted from, a specification of the buffer available to receive the message, and a location of transfer to when the transmission is complete. [In other words, an interrupt location. Any message port may be used to allow interrupts, event channels, etc. The user programs what he wants.]

SEND. This operation sends a message to some other process. [I suppose a process could also send a message to itself.] It has four parameters: a port to send the message to, the port the message is being sent from, the message, and a location to transfer to when the transmission is complete.

RECEIVE ANY. This operation allows any process to send a message to this process. The operation has four parameters: the port awaiting the message, the buffer available to receive the message, a location to transfer to when the message is received, 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 discussed below.

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

A port is a particular data path to or from a process. All ports have an associated unique number which is used to identify the port. Ports are used in transmitting messages from one process to another in the following fashion. Consider two processes, A and B, wishing to communicate. Process A executes a RECEIVE at 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.

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. [Or perhaps there is only one permanently known port which belongs to a directory-process which keeps a table of permanent-process/well-known-port associations.] 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 teletype-scanner-process keeps a table indexed by teletype number containing in each entry a port to send characters from that teletype to, and a port at which to receive characters for that teletype. 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 that the logger-process is known to have a RECEIVE pending for. [Actually, the scanner process could always use the same pair of port numbers for a particular teletype as long as they were passed on to only one copy of the executive at a time.] The scanner-process also enters the pair of numbers in the teletype table, and sends the characters and all future characters from this teletype to the port with the first number from the port with the second number. The scanner-process probably also passes a second pair of unique numbers to the logger-process for it to use for teletype output and does a RECEIVE using these numbers. The logger-process when it receives the message from the scanner-process, starts up a copy of what SDS 940 TSS [12] users call the executive (that program which prints file directories, tells who is on other teletypes, runs subsystems, etc.) and passes this copy of the executive, the port numbers so this executive-process can also do its in's and out's 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.

Port numbers are often passed among processes. More rarely, a port is transferred to another process. It is crucial that once a process transfers a port to some other process that the first process no longer use the port. We could add a mechanism that enforces this. The protected object system of [8] is one such mechanism. [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 is 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 all of the autonomous time-sharing system 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 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. Also note that if a process is running (perhaps asleep), and has RECEIVE ANY pending, then any process knowing the receive port number can talk to that process without going through loggers or any of that. 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.

When a SEND is executed, nothing happens until a matching RECEIVE is executed. 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.

A RECEIVE ANY never times out, but may be taken back. A SEND FROM ANY message 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 or RECEIVE is notified just as if the SEND or RECEIVE timed out.

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 going and consequently little data will be sent via them.

Still another example, this time a demonstration of 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 the executive asks the monitor to start up a copy of the FORTRAN compiler and passes to FORTRAN as start up parameters the two ports the executive was using to talk to the teletype. FORTRAN is of course expecting these parameters and does SENDs and RECEIVEs to these ports to discover 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 ports that the file-system-process can use to send its reply. The file-system looks up F001, opens it for input, makes some entries in its open file tables, and sends a message back to FORTRAN which contains the ports which 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 back to the executive which 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.

[The reader should have noticed by now that I do not like to think of a new process (consisting of a new conceptual copy of a program) being started up each time another user wishes to use the program. Rather, I like to think of the program as a single process which knows it is being used simultaneously by many other processes and consciously multiplexes among the users or delays service to users until it can get around to them.]

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

Note that 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. Of course, 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 port numbers, requiring instead that the monitor be called (or some other special program) to perform these functions.

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