COS 318 : Operating system
Fall 2004, Princeton University

Project 4: Interprocess Communication and Process Management

Important Dates:

Design review: Due 7 PM Monday, November 8, 2004
Due: 11:59 PM Monday, November 15, 2004


Quick Links

Inter-Process Communication
Process Management
Files for this assignment
Detailed Requirements and Hints
Extra Credit
Useful Resources
Design Review
Submitting your program


This project basically consists of two separate parts. The first part is Inter-Process Communication (IPC) mechanism, and the second is Process Management.

Inter-Process Communication

Inter-Process Communication (IPC) mechanism allows processes to communicate with each other. We will also add support for keyboard using IPC so that we can interact with the OS.

Since interrupts should be turned off as infrequently as possible, this project requires you to improve the implementation of mutexes and condition variables. Your goal should be to have interrupts disabled in as few places as possible and for as short a time as it is essential.

In this project, everything still runs in the kernel mode.

You are required to do the following for this part of the assignment:

Note: The code is based to work off of a floppy disk. You will be reading from the floppy disk and as before, do not read or modify the hard disk.

Process Management

This is the fun part, and it makes our OS look more like a real one. We will add some preliminary process management into the kernel including dynamic process loading which will enable you to actually run a program from a floppy other than the one you created for booting, i.e., you will have your own program disk! Also for those who always have energy and time, there are plenty of possibilities to earn extra credits in this part.

To load a program (process) dynamically from a floppy disk, we will have to first agree upon a really simple format of file system, though we will be dealing with a more sophisticated file system in the last assignment. This file system is flat, limited-sized. It's flat, because there is no directory structures. All files, if they can be called a file at all, reside in the same root directory. It's limited-sized, because only one sector will be used as the root directory. Therefore only limited number of entry could be there. A more detailed structure of this simple file system is given in the next section.

Now we can do something more interesting other than fire in the shell. We can tell the OS to "load" a program from a program disk. The kernel will then read the root directory sector of the disk and find the offset and length of the program, read it into a memory area which is not used, and then allocate a new PCB entry for it. You only need to allocate memory for the process, but need not to worry about the deallocation for your required features. To earn extra credits, you will have  to actually deallocate all the memory used by a process when it exits.

We will provide you with a utility program similar to createimage, which will create a program disk but not a boot disk given a bunch of process images.

You will need to implement the following functions in kernel.c :

Function name Function type Description
readdir System call Reads the process directory into a given buffer (just read a whole sector).
loadproc System call Loads the ith process(program) on the program disk, creates a new PCB entry and inserts it into the ready list.


Files for this assignment

You should use the code provided to you as a starting point for your project. We provide you with 28 files. Don't be daunted by the large number of files since you are already familar with many of them and also most files do not require to be touched at all. Only a few files need to be changed and their names are in bold face.

File name Description Need to modify? For what?
Makefile A makefile for you to compile with the right options No  
bootblock.s Code for the bootblock that handles arbitrary size image files and also switches the machines into protected-mode and creates a flat address space for you. The details will be explained in the precept. No  
createimage.c Your familar Linux tool to create a bootable operating system image on a floppy diskette No  
kernel.c kernel entry code Yes Proc Mgmt
kernel.h Include some useful prototypes. No  
scheduler.c scheduler code No  
scheduler.h Include some useful prototypes. No  
interrupt.c Interrupt handlers No  
interrupt.h header file for interrupt.c No  
keyboard.c Keyboard handling code Yes IPC
keyboard.h Header file for keyboard.c No  
mbox.c A template you will use to write mailbox code Yes IPC
mbox.h Header file for msg.c No  
common.h common definitions between the kernel and user processes No  
thread.h Include the prototypes of lock and synchronization primitives. No  
thread.c synchronization primitive implementations. Yes Interrupt disabling
th.h header file of th1.c and th2.c No  
th1.c Code of the first kernel thread No  
th2.c Code of two kernel threads to test synchronization primitives No  
process1.c The first user process No  
process2.c The second user process No  
process3.c One of the processes to test the mailboxes No  
process4.c The other process used to test the mailboxes. No  
shell.c A primitive shell that uses the keyboard input. Yes  Extra points: PS or KILL
util.h Contains the prototypes of util.c No  
util.c Contains useful routines like print_int() and gettimer() No  
syslib.h Contains the prototypes of syslib.c No  
syslib.c system calls. No  


Detailed Requirements and Hints

We strongly recommend you first implement the IPC part of this assignment, then proceed to implement the process management part. These parts are independent and can be implemented and tested separately.

You will be implementing a simple mailbox mechanism that supports variable sized messages. All messages will be delivered in FIFO order. So, the implementation of the mailbox mechanism essentially involves solving the bounded buffer problem discussed in classes. You can use the Mesa-style monitor to implement the bounded buffer.

Adding keyboard support requires writing an interrupt handler and a getchar() system call. You can treat the interrupt handler as the producer and the processes calling getchar() as the consumers. The interrupt handler simply turns an input character into a message and places it into the proper mailbox, as discussed in the class. The getchar() system call can call mbox_recv() from the mailbox to read the input character.

The interrupt handler needs to handle nested interrupts because you have multiple types of interrupts (timer and keyboard, for example). The code in interrupt.c takes care of the nested interrupts, but you should read the code carefully and understand what it is doing.

To minimize interrupt disabling in the implementation of mutexes and condition variables, you should use the the spinlock primitives provided to perform atomic operations. Only when you make a call to a scheduler function (like block and unblock) should you turn the interrupts off.

At this point, you should be able to run your OS. Everything should be running. The plane should fire a bullet when you type "fire" in your shell. Now you can start doing process management.

To make your life a little bit easier, I will give you the solution object files of those four source files that you will be modifying, namely, given/mbox.o, given/keyboard.o, given/thread.o, and given/kernel.o. You can use these given object files to test your program incrementally.

Extra Credit

It's already pretty cool with our very primitive loading mechanism, but memory is not reclaimed after process exits, thus as the system runs, garbages inside your memory will build up, and eventually exhaust your available memory. Clearly, we need a memory management mechanism as well for a better OS. You can earn up to 2 extra points implementing the following features:

Useful Resources 

Design Review

The best way to present your thoughts during the design review is to give us a brief summary of each of the functions in the templates that are missing and will be filled in by you. There is no need for actual C code here, just a few English sentences should suffice. It is a good idea to take a look at the provided code to better understand what you have to do.

For the thread.c file, instead of submitting psuedo-code, submit the final code. It is small enough to be done with now (and there wont be much of a difference between it and psuedo-code anyways). You have to email the design review to me (nitin@...) by 7 PM, Monday Nov. 8, 2004. Please submit text files only! No .doc, .pdf, .ps or any other fancypants format!

Submitting your program

Submit your final solution electronically using the following command:

/u/cos318/bin/318submit 4 README kernel.c keyboard.c mbox.c thread.c  <other files>

The submit command copies your files to the directory /u/cos318/submit/UserLogin/number and lists all the files that you have submitted for assignment number. UserLogin is your user account name. If you execute submit after the project deadline, your files are placed in directory number_late. You can run submit more than once, and you can submit partial lists of files. Each group needs to submit only one copy. This means that only one of you needs to submit.


CS318 Staff