Important Dates

Introductory Precept: Wed 10/18, 8:30-9:30pm
Design Review: Mon 10/23
Second Precept: Wed 10/25, 8:30-9:30pm
Midterm: Thu 10/26, in class.
Project Due: Tue 11/07 11:59pm
Wei is in charge of this project.
To sign up for the design review, please use online signup here.

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:

• Develop an interrupt handler that invokes the scheduler. This interrupt will be triggered once every 10ms by a timer.
• Though this kernel is preemptive the yield() call should still work 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.

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.

• 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: A template you will be using to write the scheduler code, if you do the extra credits.
• 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).
• thread.c: A template of the synchronization primitive implementations.
• 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().

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

Extra Credit:

Useful Resources

• Chapter 5: Interrupt and Exception Handling, PentiumPro Family Developer's Manual, Volume 3: Operating System Writer's Manual
• Using the GNU Assembler (especially the section specific to 80386): Describes the format and more
• M-x info under Emacs. Then : gcc -> C extensions -> Extended Asm

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 setup things so that it all works in the presence of interrupts/preemptive scheduling.

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.