COS 318: Operating Systems
Fall 2004, Princeton University

Project 3: Preemptive Scheduling

Important Dates:

Design review: 7PM Monday, October 18, 2004
Due: 11:59 PM Tuesday, November 2, 2004

The previous project was a simple but useful non-preemptive, multi-threaded operating system kernel. The main goal of the present 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:

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.

Since our entire project will be using the USB disk, please do not read/modify the hard disk.

Detailed Requirements and Hints

This project continues using the protected-mode of the CPU and run your code in the kernel-mode flat address 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 (IDT) and set up the timer chip. You need to understand how it is done so that you can adjust the interrupt frequency. 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. 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. You need again to review the techniques discussed in class.

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, ie, 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 shouldnt 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.

Extra Credit:


Useful Resources

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 (very) brief writeup of how you are planning to setup things so that it all works in the presence of interrupts/preemptive scheduling.

Prepare the writeup for the design review and email it to me ( by 12 noon, monday 18th Oct. 2004. We wont be having the usual in person design review session (if any group wants to go over their design or has questions, drop by during office hours).

Submitting Programming Assignments

Submit your complete working set of files (even ones you didnt modify). That makes grading much simpler as your submission doesnt need to be merged with the base set of files before testing.
Submit your final solution electronically using the following command:

/u/cos318/bin/318submit 3 < All files needed to make your solution work >

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.