Overview

In this project, you will add the following functionality to the previous assignment's kernel. We recommend you tackle these problems in this order:

1. Implement a spawn system call
2. Implement inter-process communication using message boxes
3. Implement a handler for the keyboard interrupt
4. Implement a kill system call
5. Implement a wait system call

Test Cases

The source code is distributed with two test cases:

• test_given implements a simple shell
• robinhoodandlittlejohn features three processes which interact using spawn, kill and wait, and which communicate using IPC

To select a test case, use the tasks script just like in project 3.

Spawning Processes

The spawn() system call should create a new running process.

First, it must look up a process by name. Since we have not yet implemented file systems, you are provided a dummy filesystem defined in ramdisk.h. The test cases each define their own files.

You may assume a finite number of running processes (NUM_PCBS).

Return the pid on success, -1 if unable to find the process, -2 if there are too many processes.

Inter-Process Communications

Processes will be able to communicate via first-in, first-out message box queues. These queues should be an efficient implementation of the bounded-buffer problem.

Message boxes support four operations, each with a corresponding system call:

• do_mbox_open(name) will create an IPC queue named name. If a queue already exists under that name, then instead return the existing queue and increment its usage count. This allows multiple processes to access the same message box if they use the same name. This syscall should return an integer which uniquely specifies the message box. You may assume:
       that there will never be more than MAX_MBOXEN message boxes open at any time
       that the name of a message box is not more than MBOX_NAME_LENGTH characters long
       that the bounded buffer will hold no more than MAX_MBOX_LENGTH messages.
• do_mbox_close(mbox) will decrease the usage count of the specified message box. If no one is using that message box, it will deallocate this message box. If the message box has not been initialized, then behavior is undefined.
• do_mbox_send(mbox,buf,size) will add the message buf to the specified message box. size is the length of the message, in bytes. If the message box is full, then the process will block until it can enqueue the message. You may assume that the message is no longer than MAX_MESSAGE_LENGTH bytes. If the message box has not been initialized, then behavior is undefined.
• do_mbox_recv(mbox,buf,size) will receive the next message from the message box. It will copy the contents of the message into buf. It will not copy more than size bytes, as to avoid buffer overflows. If the message box has not been initialized, then behavior is undefined.
• do_mbox_is_full(mbox) returns 1 if the message box is full and calling do_mbox_send would cause the calling process to block. Return 0 otherwise.

Neither do_mbox_send() nor do_mbox_recv() should call enter_critical() or leave_critical() directly.

Handling the Keyboard

You will write a handler for irq1. This handler will receive bytes from the keyboard, and buffer them using a message box. If the keyboard buffer is full, the handler must instead discard the character.

You must also implement the get_char system call. This system call will try to read a character from the keyboard buffer, or block until one is available.

To aid in your debugging, the initial code distribution contains a dummy implementation of get_char. This implementation repeatedly types out the strings:

• help
• plane
• count

Killing Processes

The kill() system call should change the state of a process such that it will die (soon). Special care must be taken in certain circumstances; for instance, there may be difficulties if this process is not in the ready queue. Think about this problem, and discuss your solution at design review.

When a process is killed, no effort should be made to release any resources that it holds (such as locks).

The kill system call should immediately kill a process, even if it is sleeping or blocked (even on a wait() call). If a process is killed while sleeping, other sleeping processes should still wake on schedule. If a process is killed while blocked on a lock, semaphore, condition variable or barrier, the other processes which interact with that synchronization primitive should be unaffected. If a process is killed while it is in the ready queue, lottery scheduling should still give proportional scheduling to the surviving processes.

If a process has opened message boxes, their usage counts should be decremented when a process is killed.

Waiting on Processes

The wait() system call should block the caller until a given process has terminated. Your implementation must be efficient.

Hints

• During system intialization, calls to leave_critical() will (re-)enable interrupts prematurely. To conquer this, you may want to define -_helper() variants of several system calls to avoid this problem (compare to lock_acquire_helper()).
• It might be helpful to define a new queue method that, given a node_t* will remove that element from whatever list it is a member of.
• You should reclaim stacks.

Design Review

• How will your spawn, wait, and kill work?
• How will you satisfy the requirement that "if a process is killed while blocked on a lock, semaphore, condition variable or barrier, the other processes which interact with that synchronization primitive [will] be unaffected?"

Grading

Every function in the starter code that has something to the effect of “fill this in” should work correctly. Functionality that will be tested:

• mbox functions
• Keyboard input handling
• spawn correctly schedules a new process
• wait correctly blocks a task and wakes up on a kill or exit
• kill correctly removes tasks without affecting others
• Message boxes, PCBs, and stacks are reclaimed and reused

Submission

Extra Credit

• Modify your implementation of kill(pid) so that any locks held by the killed task are released. Test your implementation and note that you implemented this extra credit in your README.