COS 318

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

Overview

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:

Implement a mailbox mechanism as the IPC mechanism. You will have to implement 6 functions, of which 5 are system calls.

Function name	Function type	Description
mbox_init	Internal routine	Initializes the data structures of all mailboxes in the kernel.
mbox_open	System call	Opens a mailbox for either mbox_send or mbox_recv.
mbox_close	System call	Closes a mailbox. When no process uses the mailbox, its data structure will be reclaimed
mbox_send	System call	Sends a message to the mailbox.
mbox_recv	System call	Receives a message from a mailbox.
mbox_stat	System call	Returns the number of messages in the mailbox.

The syntax of these primitives can be found in the header file mbox.h. Messages have variable size, being produced and consumed by an arbitrary number of processes. Messages are delivered according to FIFO policy. When no buffer space is available, the writer blocks until more space is made available. When no messages are available, the reader blocks waiting for messages to be written.

Implement 3 functions to support keyboard input (in keyboard.c)

Function name	Function type	Description
keyboard_init	Internal routine	Initializes the data structures for managing keyboard input.
getchar	System call	Gets the next keyboard character
putchar	Internal routine	Called by the keyboard interrupt handler to put a character in the keyboard buffer.

An interrupt handler is called every time a key is pressed acting as a producer (putchar). Consumer processes can read these keys by using getchar. When the buffer is full, the producer cannot block therefore it has to discard keys.

Improve the implementation of locks and condition variables to minimize interrupt disabling. This will involve modifying codes in the file thread.c only, and you can always code and debug this part separately from the above two parts, since this is only a matter of performance. You can use atomic operations to avoid disabling interrupts. Note these primitives are used within the kernel, they are not system calls.

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 i^th 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.

To test your IPC code, type "make ipc", given/thread.o and given/kernel.o will be used with your version of mbox.o and keyboard.o.
To test your interrupt disabling code, type "make int".
To test your process management code, type "make pm".
If you modify more than these four files, you will have to make all, or create your own make target. This will be the case when you are doing extra credit features.
To add user programs, edit the Makefile, and put your user program names after the definition "USER_PROGRAMS = ", then you can type "make progdisk" to make a program disk. Of course, you will have to compile and link your user program separately, or you will have to add some targets to the make yourself.
To run a demo, which uses the solution image, type "make demo".

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:

Memory reclamation(1/2pt): After process exits or gets killed (if you implement kill), you should free all the memory the process uses, and the PCB entry as well, so that the next newly started process can reuse this memory. You can use any cheap management algorithm, such as First Fit. Also, you can have fixed-size PCB table in your kernel, so that the user can create no more than this number of processes. Note: You must implement your own memory manager and a malloc-like function. You can't use the standard malloc() function in C library, because we are not linking against any standard libraries.
Better memory management(1/2pt): Implement a better memory allocation algorithm using Best Fit. Also, you allocate each PCB entry dynamically, so that the only limit of number of processes is the available memory. Note: You must implement your own memory manager, a malloc-like function and a free-like function. You can't use the standard malloc() or free() function in C library, because we are not linking against any standard libraries.
PS(1/2pt): Implement a UNIX-like ps command, so that the user can type "ps" in the shell and view all the processes along with their pids, statuses, and/or any other information you can come up with.
KILL(1/2pt): Implement a UNIX-like kill command, so that the user can type "kill" in the shell and kill a process specified by its pid. Note: It's okay to not be able to kill a thread, because our threads are linked statically with the kernel. You should take care of locks and condition variables that a process being killed owns. If a process is killed while executing a system call, killing the process has to be delayed until the system call ends; this ensures no locks are held by that process.

Useful Resources

Chapter 5: Interrupt and Exception Handling,
IA32 Intel Architecture Software Developer's Manual, Volume 3: System Programming Guide
A Guide to Programming on Intel IA32 PC Architecture
Using as, the GNU Assembler
An Introduction to Programming with Threads, Andrew D. Birrell
M-x info under Emacs. Then : gcc -> C extensions -> Extended asm

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

Project 4: Interprocess Communication and Process Management

Quick Links

Overview