Comp 242 Spring 2004
Interprocess Communication (Due Tue Feb 10)
In this project, you will add IPC to your Xinu-like kernel. Your IPC will be more realistic and sophisticated than Xinu IPC - it will include both synchronous and asynchronous sends, synchronous receive, multiple input ports per process, selectivity in receipt, and guarded receives. The calls to be implemented are given below. In all of these calls, assume that the port is an input port.
ssend(port_id, mesg, size)
int port_id; /* which port to send to */
char *mesg; /* pointer to the message */
int size; /* number of bytes in the message */
asend (port_id, mesg, size)
int port_id; /* which port to send to */
char *mesg; /* pointer to the message */
int size; /* number of bytes in the message */
Both sends will queue up messages at the port port_id in FIFO order if there is no receiving process waiting for a message at this port.
ssend will block the sending process until its message is received. You can assume that the size and number of outstanding messages are bounded.
For receive, there are two choices. The first is:
mrecv(ports_req, mesg, size, port_id, guard)
int ports_req; /* bit map of ports to receive from */
char *mesg; /* buffer to contain message */
int *size; /* number of bytes in the message buffer */
int *port_id; /* port returned message is from */
int guard(); /* procedure to guard the port */
A receiving process can request messages from multiple ports. mrecv() should choose a message from one of the requested ports, if one is present and the associated guard for it evaluates to true; otherwise, it should block. If the guard evaluates to false for the message at the head of the message queue, the message should not be removed from the message queue - instead mrecv should block until the guard becomes true for the message. Moreover, messages should not be delivered out of order. When a message is selected, it is copied into the the variable mesg. Upon return, the size of the received message is returned in the variable size, and the port on which it arrived is noted in the parameter port_id.
An alternative would be for mrecv to return a buffer instead of passing it in for the OS to copy:
char *mrecv(ports_req, size, port_id, guard)
int ports_req; /* ports to receive from */
int *size; /* size of returned message */
int *port_id; /* which port message is from */
int guard(); /* procedure to guard the port */
You have to make the choice between these two semantics for receive.
In either case, the guard procedure takes a pointer to the following structure, which tells it the port no, message content, and message size of the received message:
struct msgdesc {
int port_id; /* port message arrived on */
int msgsize; /* size of message */
char *msg; /* message */
};
The guard computes a boolean return value based on this parameter and
values of global variables.
You can look at the discussion of CSP and Ada in the Andrews and Schneider
paper (papers in the reading list are in the Colab, Room 155).
Multiple receive corresponds to the alternative command in CSP
and the select statement in Ada.
You must also implement the following support routine:
int req_port(port_id)
int port_id; /* to be translated into a bit mask */
This routine returns a bit vector corresponding to the port requested in port_id. req_port() is used in an mrecv() invocation, such as:
mrecv(req_port(1)|req_port(5), buf, size, port, guard);You can assume that there are 32 ports for all processes.
Finally, you should also implement the following routines to allocate and free a port:
int alloc_port(port_id)
int port_id;
int free_port(port_id)
int port_id;
If the argument is not a valid port (e.g. -1), then alloc_port should reserve some unallocated port and returns its id, otherwise it should allocate the specified port and return its id.
If a message is sent to an unallocated port, rather than giving an error message, queue it at the port expecting the port to be later allocated. While these are not ideal semantics, they will help you easily deal with some race conditions in future assignments.
Your implementation should not use polling. In Xinu, message passing is built on top of semaphores. In your assignment, you should implement message passing directly on top of the queue routines. The approach of using semaphores would not work in the distributed case, which is your next assignment. In fact, you should implement (and test) a Xinu semaphore using your IPC mechanisms (this requires some thought).
Thus, some of the design decisions have been made for you, while others have been left for you to discover. Following are some questions that you should think about and answer as you work through your design and implementation decisions:
Where are messages stored until they are received?
What are the tradeoffs between the two receive calls? What portions of your address space could you safely use for passing messages (stack, heap, etc)? Who should be allocating the buffer in the second receive (OS or sender)? If your implementation requires certain rules to be followed by senders and receivers, that is OK, as long as you document these rules and justify them (based on efficiency, generality or other considerations).
What happens when you kill() a process that is blocked waiting to ssend() or mrecv a message?
What happens when you free a port that has pending messages?
How is buffer deallocation handled (you should not assume that memory is infinite)? That is, who (sender/receiver/OS) is responsible for deallocating heap data structures used for passing messages?
Should guards be allowed to affect the global state of the system (i.e. should they have side effects)?
How is the semaphore implemented?
As before, you should write test programs to demonstrate the IPC primitives you implement and the semaphore you build on top of it. The semaphore itself will demonstrate many of the IPC primitives. Write test programs to demonstrate the rest.