Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

1. A pre-emptive kernel with interrupts

The previous project was a simple but useful non-preemptive, multi-threaded operating system kernel. The main goal of this project is to transform the non-preemptive kernel into a preemptive kernel. You will also change the system call mechanism from a simple function call to an interrupt mechanism as used in contemporary operating systems. Also, you will be required to add condition variables and semaphores to augment the synchronization primitives designed during the last project.

The kernel of this project and future projects supports both processes and kernel threads. See the description for project 2 on how the processes in our project differ from the traditional notion of processes.

In this project, everything still runs in the kernel mode. Also note that the delay() function has been removed, and replaced with ms_delay(), which waits the specified number of milliseconds.

You are required to do the following:

Interrupt and system call handling

Develop an interrupt handler that invokes the scheduler. This interrupt will be triggered once every 10ms by a timer.
Set things up so that—even though this kernel is preemptive—the yield() call still works correctly.
Use a software interrupt to perform system calls. All of this code is actually given to you as a template. The system calls (available to processes) that are already implemented are yield(), getpid(), and exit(). You are required to ensure that these system calls perform correctly even in the presence of the timer interrupt.

Synchronization

The synchronization primitives for mutual exclusion: lock_acquire() and lock_release() should continue to work in the presence of preemptive scheduling. Note that these two calls are used only for threads.
You need to add condition variable calls to the synchronization primitives.
You also need to add semaphore calls to the synchronization primitives.
You also need to implement a reusable barrier using condition variables. A barrier has the property that it collects processes until some number n (specified when the barrier is initialized) are waiting for it; then it release them all at once.

2. Files

You should use the code provided to you as a starting point for your project. We provide you with 26 files. Don't be daunted by the large number of files since you are already familiar 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.

These files should magically appear in common/3 under your group or user directory when you do svn up. You should do svn cp common/3 ./3 to get a copy you can commit—as always you do not have write access to common, so Subversion will not let you commit changes there.

Makefile: A makefile for you to compile with the right options.
barrier_test.c: Threads you can use to test your barrier implementation.
bootblock.s: Code for the bootblock that handles arbitrary size image files, switches the machine into protected-mode, and creates a flat address space.
createimage.c: Your familiar Linux tool to create a bootable operating system image on a floppy diskette.
entry.S: Template for you to write assembly code for the timer interrupt. You should also browse the code in this file to gain a deeper understanding on what goes on in the OS. You need to complete the timer interrupt handler (irq0_entry and fake_irq7_entry).
interrupt.c and interrupt.h: The interrupt and exception handlers. (Not necessary to change the file, but need to read the file to understand how it works.)
kernel.c: Make sure it all works with timer interrupts on. (Not necessary to change it.)
kernel.h: Includes some useful prototypes.
scheduler.c: The scheduler. You probably don't need to modify this, but you can if you want to tinker with the scheduling algorithm.
scheduler.h: Includes some useful prototypes, and defines a number of macros.
common.h: Common definitions between the kernel and user processes.
thread.h: Includes the prototypes of lock and synchronization primitives. You need to add data structures for condition variables and semaphores (and barriers if you do the extra credits). Note: this file includes the lock_* functions that were in lock.h in the previous assignment.
thread.c: A template of the synchronization primitive implementations. Includes lock_* functions previously in lock.c.
th.h: header file of th1.c and th2.c.
th1.c: Code of the first kernel thread.
th2.c: Code of two kernel threads to test synchronization primitives.
process1.c: A template of the first user process that prints to the second line on the screen.
process2.c: A template of the second user process that prints to the 3rd line of the screen.
philosophers.c: Threads you can use to test your semaphore implementation.
util.h: Contains the prototypes of util.c
util.c: Contains useful routines like print_int() and get_timer().
syslib.h: Contains the prototypes of syslib.c
syslib.c: A template to implement the stub routines for the system calls.
time.c,.h: Contains routines that detect the CPU speed. The CPU speed is available through the call cpuspeed().

3. Detailed Requirements and Hints

This project continues using the protected-mode of the CPU and a flat, kernel-mode space. To implement preemptive scheduling, you need to use the timer interrupt mechanism. We have prepared for you most of the code that is required to set up the interrupt descriptor tables (IDTs) and set up the timer chip. We have provided you with an interrupt handler template. It is your job to decide what goes into the interrupt handler.

You need to figure out where you can perform preemptive scheduling. You need to review the techniques discussed in class. Note that in this project, you can disable interrupts, but you should avoid disabling interrupts for a long period of time (or indefinitely!). In order for processes to make system calls, you will note that the code in syslib.c does not make a function call, rather it invokes a software interrupt. This mechanism is only used by processes. The kernel threads should still work in the same way as before, calling the functions in the kernel directly.

To implement condition variables, you will need to add three new calls in the kernel (the code will end up in thread.c). Also, both condition variable calls and mutual exclusion calls should work correctly in the presence of preemptive scheduling.

For semaphores you need to implement the up and down calls.

The barrier functionality should be implemented using condition variables and should be re-useable, i.e., the same barrier_t variable can be used multiple times without a process needing to reset it between uses (note: the variable of course will be reset for re-use at some point but that should be internal to the implementation of the barrier functionality. A programmer making use of barriers shouldn't have to call a barrier_reset or some such call between uses. See barrier_test.c to see how the barrier variables are used).

Once again, everything should work in the presence of interrupts.

4. Design review

The requirements of this design review are to finish creating the data structures in thread.h and give a brief summary of each of the functions in the templates (thread.c, entry.S) that are missing and will be filled in by you. There is no need for actual C code here, just a few sentences or psuedo-code is sufficient. Also a brief writeup (less than 2 printed/handwritten pages) of how you are planning to set up things so that it all works in the presence of interrupts/preemptive scheduling.