[FrontPage] [TitleIndex] [WordIndex

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.

  • 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.

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.

2014-06-17 11:58