1. Blocking Message Send (120 pts)

This problem concerns the implementation of a blocking version of send(), call it sendb(). sendb() has the same function definition as send(). If the receiver's 1-word message buffer is empty, sendb() behaves as send(). If the receiver's buffer is full, however, sendb() blocks, i.e., the kernel context switches out the calling process and puts it into a waiting state, call it SENDING. This is implemented by defining an additional state constant PR_SND (choose what value to assign it to) in process.h. The 1-word message that makes the calling process block — note that there can be only one such message outstanding in Xinu's process/thread model — is stored in the calling process's process table entry by defining two additional fields:

• umsg32     sndmsg;
• char         sndflag;

On the receiver side, before a receiving process returns from receive() it must check if there are any blocked sending processes, and if so, unblock one of the waiting processes. When implementing "unblock" there are at least three issues to consider: one, whom to unblock, two, how to unblock, and three, where to queue the list of blocked processes. If the semantics exported to the application programmer is a FIFO message buffer, then the sending process that blocked first is put into READY state. If a different semantics is exported by the kernel, then dequeueing must follow its corresponding policy. In how to unblock, care must be exercised to ensure that shared data structures are not corrupted by concurrent access. Last, but not least, there is a degree of freedom in deciding where to maintain the queue of blocked processes. Due to performance considerations, it is preferable that there is a per-receiving process queue of blocked processes in SENDING state so that dequeueing and enqueueing overhead are only dependent on the number of processes sending to the same process. Dynamic allocation of queue memory should be avoided for performance reasons.

A default solution is to overload queuetab[] in queue.h (look into related source code, including initialize.c, to see how processes in READY and WAITING states are stored in different segments of queuetab[]). How you choose to implement the specifics is up to you. Make sure to explain your design decisions and rationale in a separate write-up Lab3Answers.pdf.

Create 3 test cases whose output (e.g., senders may print sender-specific 1-word messages before calling sendb() and a receiver may print a received message) demonstrate the correct functioning of the blocking message send extension of kernel services. If you find a need, you may use the sleepms() system call in conjunction with busy looping (i.e., for-loops performing non-I/O instructions) to craft your test cases. It is important to benchmark a system when it is stressed, hence don't be shy with respect to the number of sending processes in your tests. That is, we want multiple processes to write messages to the same receiver process, and for these writer processes to be queued in blocking state SENDING, because the receiver process's reads are unable to keep up with the pace of message writes.

2. Asynchronous Message Receive (300 pts)

Problem 2 concerns implementation of asynchronous receive in Xinu using a callback function that an application (i.e., Xinu process) registers with the kernel. Thereafter whenever a 1-word message is sent to the receiver, the registered callback function is executed which handles the chore of processing the received message: copy from kernel buffer to user buffer by executing Xinu's receive() system call (which won't block since there is guaranteed to be a message) and print the 1-word message stored in the receiver process's local variable after which the callback function returns.

The kernel exports a system call, registercb(), that is used by an application to specify a user space 1-word buffer and a user space callback function that should be executed when a message is received. For brevity, we will adhere to the convention that a callback function must be of type int and contains no argument. The function definition is given by

• syscall registercb(int (* func) (void) )

   int myrecvhandler(void) {
      umsg32 recvbuf;
      recvbuf = receive();
      kprintf("msg received = %d\n",recvbuf);
   }

   if (registercb(&myrecvhandler) != OK) {
      kprintf("recv handler registration failed\n");
      return 1;
   }

The more critical concern is how to invoke the callback function. In the first approach, when a sender executes the send() or sendb() system calls, the system calls check if the receiver process has registered a callback function, and, if so, executes it before returning. The problem with this approach (not in Xinu where there is no kernel/user separation but in modern kernels such as Windows, UNIX/Linux) is that a user space function is executed in kernel mode (since the system call hasn't returned yet) which would be a critical security vulnerability as isolation/protection is violated. That is, myrecvhandler() which is user supplied code could contain bugs (innocuous) or malicious code that subverts the system.

In a second approach, which is a slight (but important) variant of the first approach, we could execute the callback function after the sender's send() or sendb() system calls return. This ensures that the callback function is executed in user mode so that system-wide damage is prevented. Although myrecvhandler() runs in user mode, it runs in the context of the sender process which also violates isolation/protection. That is, processes must be sandboxed so that they are protected from each other. For example, if myrecvhandler() has a bug or is an infinite loop (malicious), the sender process would crash or never escape from the infinite loop. Thus the second solution is not a valid solution in modern operating systems.

In the third approach, the receiver's callback function is executed when the receiver process is context switched in by the scheduler in the future. To do so, when a sender process executes send() or sendb() the kernel needs to make a note to execute the receiver process's registered callback function when it is scheduled next. Since the callback function needs to use the receiver process's user space run-time stack, before the kernel returns to user mode preparations must be made so that after returning to user mode a call to myrecvhandler() is made. Ignoring the fact the Xinu does not implement kernel/user mode separation, note that in Xinu after context switching in the receiver process ctxsw() returns to resched() and resched() returns to whichever kernel function (system call or interrupt handling routine) invoked it while still in kernel mode in the case of Windows, UNIX/Linux. For example, had the sleepms() system call called resched(), before sleepms() returns it must prepare the receiver process's run-time stack (tantamount to pushing the call frame of myrecvhandler() onto the stack) so that a call to the callback function is made after sleepms() returns.

Implement the first and third approaches which count for 150 points each. In both approaches, describe the design of your specific implementation in Lab3Answers.pdf. Create four test cases, two for each approach, to demonstrate the correct behavior of your kernel modification that implements asynchronous message receive.

Important: Please comment your code changes in Xinu such that (a) where changes are made is highlighted, and (b) what changes are made is conveyed.

Turnin Instructions

Please follow the same turnin procedure as before with lab3 in place of lab2.