The goal of this project is to design and implement a simple multiprogramming kernel with a preemptive scheduler. Although the kernel will be very primitive, you will be dealing with several main mechanisms and apply techniques that are important for building multiprogrammed operating systems.

The kernel of this project and future projects supports both processes and threads. Note that the processes in this project are different from those in traditional operating systems (like Unix). Our processes have their own protection domains, but they share a flat address space. In the future, we will be providing processes with separate address spaces. The main difference between processes and threads in this project is that a process resides in a separate object file so that it cannot address data in another process, whereas threads are linked together with the kernel in a single object file.

From now on, the kernel will use the protected mode of the x86 processors instead of the real mode. In this project, everything runs in kernel mode. You are required to do the following:

• Develop an interrupt handler that invokes scheduler. This interrupt will be triggered once every 10ms.
• 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 should use the code available in the class webpage as a starting point for your project. We provide you with 19 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 two files need to be changed and their names are in bold face.

• Makefile: A makefile for you to compile with the right options.
• 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.
• kernel.c: A template you will be using to write the kernel entry code.
• kernel.h: Include some useful prototypes.
• scheduler.c: A template you will be using to write the scheduler code.
• scheduler.h: Include some useful prototypes.
• common.h: Common definitions between the kernel and user processes.
• thread.h: Include the prototypes of lock and synchronization primitives.
• 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.
• 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.

Since our entire project will be using the floppy drive, 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 the code that is required to set up the interrupt descriptor tables (IDTs) and set up the timer chip. Your job is 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 long a 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 two 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.

Extra Credit

You will get an extra point if you implement priority scheduling and demonstrate it with processes provided by us.

Useful Resources

• Chapter 5: Interrupt and Exception Handling, PentiumPro Family Developer's Manual, Volume 3: Operating System Writer's Manual
• Guide to programming with Pentium and Pentium-Pro.
• Using the GNU Assembler (especially the section specific to 80386): Describes the format and more
• Assembly language tutorial: A quick tutorial
• Brennan's Guide to Inline Assembly
• An Introduction to Programming with Threads, Andrew D. Birrell
• M-x info under Emacs. Then : gcc -> C extensions -> Extended Asm

Submitting Programming Assignments

Submit your final solution electronically using the following command:

/u/cs318/bin/318submit 4 README otherfiles ...

The submit command copies your files to the directory /u/cs318/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.

CS318 Staff