COS 318 - Project 4

Project 4: Inter-Process Communication and Process Management

Sections	Links	Code
Overview Important Dates Design Review Test cases IPC The Keyboard Syscall spawn() Syscall kill() Syscall wait() Glossary Extra Credit Hints Program Submission Grading Criteria	Sign up for design review	Project 4 Code Template

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:

Implement a spawn system call
Implement inter-process communication using message boxes
Implement a handler for the keyboard interrupt
Implement a kill system call
Implement a wait system call

This document will be elaborated as the project progresses. Check back to see if clarifying details or additional hints are added.

Nick Johnson will be the TA in charge of this project.

Important Dates

Precept 1: Nov 11, Wed, 7-8, COS 105.
Design Review 1: Two sessions: Tue 17 Nov 5-7:30pm; Wed 18 Nov 5-7:30pm. Sign up
Project Due: Nov 23, Mon, 23:59

Design Review

Design Review is graded as follows:
Data structure
1 point. Explain briefly the fields in the mbox_t structure and how they relate to the bounded-buffer problem from the textbook. What differences do you see between that example and the one you are going to build.
Keyboard Interrrupt
1 point. What does keyboard_init do? Explain the possible problems that can occur in keyboard getchar and putchar because of interrupts IRQ0 and IRQ1. What is a solution? How will you use inter-process communications to make your keyboard interrupts work?
Process Management
2 points. How can you efficiently implement the wait system call? Under what situations would each of spawn, kill and wait fail?
Inter-Process Communication
1 point. As we mentioned before, since messages are variable sized, a single mbox_recv call can allow several mbox_send operations to execute rather than one. Argue on how to achieve that. Explain how two processes can both access the same message box, even though their address spaces are (conceptually) disjoint. Describe how message boxes can be used as a design pattern within the kernel to decouple hardware drivers from users of that hardware.

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. Additional testcases may be released throughout the duration of this project.

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, as described by Tannenbaum.

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

mbox_open(name) 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. Different processes can access the same mbox if they know the name. This syscall should return a integer which uniquely specifies a message box. You may assume that there will never be more than MAX_MBOXEN message boxes open at any time. You may assume that the name of a message box is not more than MBOX_NAME_LENGTH characters long. You may assume that the bounded buffer will hold no more than MBOX_MBOX_LENGTH messages.
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 mbox has not been initialized, then behavior is undefined.
mbox_send(mbox,buf,size) will add the message buf to the mbox. Size is the length of the message, in bytes. If the mbox is full, then the process will block until it can enqueue the message. You may assume that the message is no longer MAX_MESSAGE_LENGTH bytes. If mbox has not been initialized, then behavior is undefined.
mbox_recv(mbox,buf,size) will receive the next message from the mbox. It will copy the contents of the message into buf. It will not copy more that size bytes, as to avoid buffer overflows. If mbox has not been initialized, then behavior is undefined.

The Keyboard

You will write a handler for irq1. This handler will receive bytes from the keyboard, and buffer them using a message box. As a special case, if the keyboard buffer is full, the keyboard interrupt handler will instead discard the character.

You will 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

These strings are commands for the testcase test_given.

Syscall spawn()

The spawn system call will 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 files in this filesystem are defined by whatever testcase you choose.

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

Syscall kill()

The kill system call will change the state of another process so that it will die (soon). Special care must be taken; for instance, there may be difficulties if this process is not in the ready queue. Think about it, 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). Sometimes the process is waiting on a resource, and it is not easy to kill this process. At the very latest, a killed process should die before it is scheduled to run again.

The kill system call should immediately kill a process, even if it is sleeping, blocked, or wait()ing on another process to die.

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.

Syscall wait()

The wait system call will block the calling process until another process has terminated. Just like blocking sleep from project 3, this must be an efficient, blocking implementation of wait.

Glossary

IPC: MOS 2.3.
Pipe

Extra Credit:

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.
The calls mbox_send() and mbox_recv() can be implemented without a critical section. In fact, you should implement these without a critical section.

Submission

Submit via dropbox. When you submit, you will submit the at least the following files:

common.h
interrupt.h
interrupt.c
kernel.h
kernel.c
keyboard.h
keyboard.c
mbox.h
mbox.c
scheduler.h
scheduler.c
sync.h
sync.c
syslib.h
syslib.c

If you have modified any files other than those listed above, or if you have created new files, you may submit those as well. Under no circumstances may you submit an archive of your code; you must submit each file listed above.

Grading Criteria

None yet! Check back for more details.