![]() |
COS 318 : Operating system Fall 2006, Princeton University Project 4: Interprocess Communication and Process Management |
Introductory Precept: Wed 11/08, 8:30-9:30pm
Design Review: Mon 11/13, 6:00-9:00pm
Second Precept: Wed 11/15, 8:30-9:30pm
Project Due: Tue 11/21, 11:59pm
Signup for Design Review
Overview
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 (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:
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.
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.
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. |
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 |
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.
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:
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.
To signup for the design review, please use
online signup here.
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