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. should choose a message from one of the requested ports that (a) has a message queued up and (b) for which the associated guard evaluates to true. If such a port does not exist, mrecv() should block until these conditions are met for some port. As discussed below, these conditions should be re-evaluated for each port listed in the receive whenever a new message arrives at any of these ports. As also mentioned below, a guard takes the message as an argument. Therefore, it is possible that the guard will evaluate to false for the message at the head of the queue and true for some message behind it. Messages should not be delivered out of order - so you need to look only at the message at the head of the queue.
In this version of the receive call, 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.
When should a guard be evaluated? Clearly, it should be evaluated when a message arrives at a port on which a receiver is blocked. Ideally, it should also be evaluated whenever the guard condition changes for a port from false to true, However, this would require the guard to be evaluated after each assignment statement which is inefficient and impossible to do in the OS without compiler ssupport. Therefore, it is OK if you evaluate guards when (a) each time the mreceive statement is executed, and (b) a new message arrrives for one of the ports on which the receive is listening.
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.
Thus, some of the design decisions have been made for you, while others have been left for you to discover.
Your implementation should not use polling. In Xinu, message passing is built on top of semaphores - it uses semaphores to block and unblock a a process that does a synchronous operation. This approach would not work in the distributed case ( which is your next assignment) as the semaphores cannot be accessed by senders and receievers on different machines. In your assignment, you should implement message passing directly on top of the queue routines, that is, you should use these routines directly to block and unblock a process that does a synchronous message passing operation. (You should not use suspend or resume, either. Why?) In addition, you should implement (and test) a semaphore supporting the four Xinu operations that uses your IPC mechanisms. Thus, while in Xinu IPC is layered on top of semaphores, in your project, semaphores will be layered on top of IPC. The implementation of the four Xinu semaphore operations should be done outside the kernel in library routines. Thus, it should not call the queue routines or access any kernel data structure such as the context block. In addition, you should not use suspend or resume to block/unblock processes. By doing so, you ensure that the semaphores can be used by processes on different machines to synchronize with each other when you make your IPC distributed. As in the case of Xinu semaphores, multiple processes should be able to invoke both the wait and signal operations on a semaphore. Do not implement a binary semaphore and, as in Xinu, allow a semaphore to have an initial count. The space or time costs should not be proportional to the value of this initial count. This implementation requires some thought. (Hint: Try to do the bounded buffer problem on your own using the IPC mechanisms. The problem requires support of three operations: one that creates a finite list of buffers, one that puts a buffer in this list, and one that retrieves a buffer. Try to do the problem on your own first. If you cannot come up with the solution on your own, then see the partial solution in class to it. It does not give a solution to the first operation - but this solution follows from the other two. Once you implement this operation, you know the structure of the solution to the semaphore problem. If you choose to not follow this path, and come up with the semaphore solution independent of it, make sure it meets all of the requirements above. )
Have a look at the solution presented in class to the bounded buffer problem that uses message passing. Also your demo of semaphores should implicitly demo all of the message passsing primitives)
It is Ok to use the demo problem of the previous assignment (with synchronization/message passsing added) for this assignment. In fact, you are encouraged to build on the demo problems in subsequent assignments rather than invent new applications.
Following are some questions that you should think about and (answer as part of your submission) 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 a sender 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.