Many old ideas from uniprocessor systems apply to multiprocessor systems and networks!
UNIX pipes MULTICS shared segments DEMOS message passingThere are many other examples, but we will focus on these for the moment. Whatever the primitives may be, there are problems that are common to all interprocess communication mechanisms.
To establish an interprocess communications channel, it must be created, the rights to use the channel (or knowledge about it) must be distributed to the processes that wish to communicate, and then the channel must be used. These three aspects of channel establishment are conceptually independant.
Here is an example from Classic UNIX, where the commonly used interprocess communication channel is the pipe.
UNIX pipes are not, strictly speaking, FIFO queues of characters. Most older UNIX implementations buffer 512 bytes on behalf of the sending process before delivering anything to the receiver, and the sender is not re-awakened until the receiver has finished consuming all 512 bytes. This default behavior could be modified by the sender -- if the sender issues a fsync(p) system command on pipe p, the receiver gets whatever was written in p prior to the flush operation. This is the same operation that a user can apply to a disk file to force all cached data to disk.
Note that it is quite easy to change the way pipes are created without changing the way they are distributed or used. For example, when AT&T brought out System V UNIX, named pipes were introduced. These may be placed in a directory, just like a file, thus changing the way they are distributed and created.
Under MULTICS, processes may communicate through shared memory. Files, under multics are named segments, and when a file is opened, that segment is inserted in the address space of the process. If two processes open the same file, they share the segment and may use it to communicate.
The answer lies in the way DEMOS processes are created. DEMOS process creation is done by sending a message to the process manager's "create process" link. The message contains the size of the desired memory region for the created process, and it contains a link to be used by the process manager to send a reply message. The process manager's reply to this request contains a newly created link to the process manager that uniquely identifies the new process. Messages to this link can be used to load or inspect the memory image of the new process, to load or inspect the link table of the new process, and to start or stop the process.
Once a process is created, the process that created it must use these services to give it code to run and any links it may need to get started. Generally, it will give the new process a "standard environment" of links, so that, for example, slot zero might be the link to the process manager, slot one might be the link to the file system, slot 2 might be the link for an open output file (standard output), and so on.
The file system has one widely known link used to request that files be opened, and it exports a new link for each file it opens, where the messages sent over those new links are used to read or write the open files. Thus, link table entries may refer to many kinds of objects and it is up to the application program to remember what kind of thing each link represents.
(the latter is not a new problem -- we are completely comfortable with similar constraints on main memory, where it is up to the application program to make appropriate interpretations of each byte).
Interprocess communication channels may be symmetrically named by both sender and receiver in the same way, as with UNIX pipes and MULTICS segments. In this case, the channel exists somewhat independantly of its users.
Alternately, channels may be bound to one or the other processes involved, as with DEMOS links. We send messages to a link which identifies a receiving process. Ownership of a link may be transferrable, as in DEMOS, or it may not be transferrable.
Where is an interprocess communication channel located, physically? This question is of secondary importance with conventional systems, but when a system is distributed, it becomes a significant issue!
____________ ___________ | ___________ | | | | | P1 ----|--|--Channel--|--|---- P2 | | | | ____________| | | |___________ | |With an asymmetric channel, it is obvious that the storage associated with the channel should be located with the process to which the channel is bound.
With a symmetrical channel, it is not obvious where the storage should be located! For a file, as in MULTICS, the problem is not so bad -- the storage is physically shared between all users, and when there are no users of the file, the storage is all on disk under the management of the file system.
For a UNIX pipe, on the other hand, nothing is obvious. The pipe may have many readers and many writers, and on a distributed system, the reasonable location for the buffer associated with the pipe may vary continuously as readers and writers are created and destroyed during the life of the pipe.
The example of multiple readers and writers on a UNIX pipe is not entirely artificial. Under UNIX, pipes may be used to implement both shared memory and semaphores. Writing a byte to a pipe (and using fsync to make sure that the receiver gets the byte) can be used as a Signal operation, and reading a byte from a pipe can be used as a Wait operation, thus implementing semaphores. If this is done, all processes using the pipe must be able to both read and write.
To implement shared memory using a pipe, consider the pipe to be a single shared variable containing up to 512 bytes of data. Reading the contents of the variable is done with a READ command, which is destructive -- therefore, every user always follows each read with a write restoring the value of the variable. Write is also troublesome -- the variable must be empited of its old value prior to the recording of a new value, so again, changing the variable is always done by first reading out the old value and then writing in the new one.
This implementation of shared variables and semaphores using UNIX pipes is stupid, but it is part of the proof of a folk theorem that any system supporting an adequate interprocess communication mechanism can be used to implement any other interprocess comunication mechanism.
The communication services offered by a system tend to dictate the style of distrubuted applications. For example, UNIX pipes encourage structuring applications as pipelines:
A|B|C (in UNIX shell notation)In contrast, the message passing facilities of DEMOS encourage client-server relationships.
P1 <---> Server <---> P2It is fair to ask what models of interprocess communication are really useful? The answer lies not in theory, but in what real programmers have successfully found uses for. The semantic structures of programming languages also give strong hints, since communication structures that are widely used within one program are also likely to be useful between programs in a distributed system.
Clearly, both pipelines and client-server relationships have proven themselves to be useful. Pipelines are fairly simple, conceptually, but client-server relationships require deeper study.
All of the following have significant similarities:
Dijkstra's notion of a secretary process Hoare's monitors Ada tasks and the rendezvous concept Remote procedure calls Client-server modelsDijkstra developed the notion of a secretary in the context of his THE operating system (Techniche Hochschule Eidenhoven, or some such). Processes requesting a service would communicate with the secretary process (using semaphores). When the secretary was done, it would issue a signal saying it had done the requested service.
Hoare formalized this with his idea of a monitor (more about this later). The Ada rendezvous (literally, a get-together between tasks) allows the construction of monitor-like processes.
Remote procedure calls are one way of implementing monitors and Ada rendezvous entries on a distributed system.
All of the above are examples of client-server interactions:
________ request ________ | Client |----------->| | |________|<-----------| | reply | | | server | ________ request | | | Client |----------->| | |________|<-----------|________| replyClients are processes. The server may be a process providing multiple services, a process providing a single service, or in the case of object oriented systems, not a process.
In all cases, the server may serve many clients, all of whom make requests that contain enough information to send a reply when the service is complete.
If the server is not a process, it must execute on the same machine as the client, and each entry to the server is essentially a procedure call. Any synchronization between entries to the server must be provided by conventional interprocess synchronization, for example, using semaphores.
If the server is a process, it waits for a request for service, then takes the requested action, then sends a reply indicating that the service is done.
If clients immediately await a reply after sending a request, and if the server does no computation when it is not acting on behalf of a client, then the server is imitating a procedure call model as it might be implemented on a uniprocessor, except that no two clients may enter the server at the same time -- the limitation of the server to a single process ensures that there is mutual exclusion between different service requests.
If the server provides multiple services, as is common when the overhead of large nubmers of small processes is high, this just adds a degree of unneeded mutual exclusion.
The DEMOS system was completely structured around client-server interactions. For example, the file system was a server. To open a file, a process would send a message to the file server's open link (the link to the file server's port from which it expects to get open messages) containing the name of the file to be opened. The file server would reply with a message containing a link designating an open file.
When the file server opens a file, it allocates one of its ports to that file and creates a link allowing users of that file to send messages to that port. Messages to this port are interpreted by the file server as requests to read, write, seek or close that particular file.
Read, write, seek and close messages are sent to the file server by clients that have open files, and in each case, the server is expected to send a reply after it completes the requested service.
Client server interactions almost always follow the following scheme:
1) Client allocates a reply port and creates a reply link using that port. 2) Client sends message to server containing a) Identity of service requested b) Data needed to perform that service c) The reply link 3) Client awaits a message on the reply port. 4) Server receives the message and does the work requested; 5) Server sends reply message containing the results of requested operation. 5) Server sends reply message containing the results of requested operation, and then deletes the reply link. 6) Client receives the reply. the reply port.This sequence is so common that the designers of DEMOS extended the set of system services to include call, a service that combines the creation of a reply port and link with the sending of a request and waiting for the reply.
The designers of DEMOS also added an attribute to links, delete. Links with this attribute are automatically deleted from the holder's link table when they are used, and reply links are always of this type. Thus once a process receives a message on a reply port, it may assume that it will never receive another message there.
Finally, the designers of DEMOS added a send-delete service that automatically deletes the link it uses as a side effect of sending a message. This is generally used by servers to send replies.
Note that a typical server, for example, the DEMOS file server, must always be willing to accept an incoming message on any of a number of ports! In the case of the file server, incoming messages are expected on the open port and on the ports for each open file. This is why the DEMOS service for receiving a message allows a set of ports to be specified.