[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 simple kernel with non-preemptive scheduling

With the bootup mechanism from the first project, we can start developing an operating system kernel. The goal of this project is to design and implement a simple multiprogramming kernel with a non-preemptive scheduler. Although the kernel will be very primitive, you will be dealing with several core mechanisms and applying techniques that are important for building advanced, multiprogrammed operating systems.

The kernel of this project and future projects supports both user processes and kernel 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 and (for the moment) run in kernel mode. In the future, we will be providing processes with separate address spaces. Our threads are kernel level threads that always share the same address space with the kernel; they will never run in user mode.

The kernel threads are linked together with the kernel, so they can access kernel data and functions directly. On the other hand, processes use the single entry-point mechanism described in the lecture. 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:

You should use the code available in the common/2 subdirectory of your Subversion directory as a starting point for your project (you will need to do svn up to fetch this code, and should copy it to your main directory with svn cp common/2 . as in the first assignment). We provide you with 21 files. Don't be scared by so many files since you are already familiar with some of them; you will need to change only 6 of them (listed in bold face).

2. Detailed requirements and hints

You need to understand the PCB (Process Control Block) and decide whether you would like to add additional items for your needs. The PCB provided has essential fields for a context switch. Since the processes and threads share the same address space in this project, the PCB can be very simple. Consider how data is saved during a context switch, and which stacks are used by threads and processes.

The bootblock given for this assignment not only loads your kernel but also sets up the memory system, by initializing the Global Descriptor Table and setting up the segment registers so that you can refer to addresses directly in a flat 1 MB address space. You should probably not modify the segment registers or GDT if you want the processes to keep working.

In the template file kernel.c, you need to implement the _start() function to initialize the processes and threads you wish to run. For example, you need to know at which location in memory the code for the process or thread starts and where the stack for that process or thread is. Once the required information has been recorded in the appropriate data structures you will need to start the first process or thread. Note that each process is placed at a fixed location in memory. You can figure this out by looking at the Makefile. It is possible that you will need to adjust the location of the processes in order to make room for your kernel.

Each kernel thread will need a stack. Each user process should get two stacks—one for user mode and one for kernel mode—and the system call mechanism should switch between them. You will need to allocate these stacks in your _start() function (or something called by your _start() function). Put them somewhere where they won't bump into anything else (you have up to 0xA0000 to work with). They do not need to be especially big (4K should be plenty).

Once a process is started it will run until it gives up execution by calling yield() or exit(). The scheduler than decides what process to run next. This process is executed as a return from its yield()call. Consider what should happen when a process exits or makes an invalid system call. You need to understand how a thread's state changes upon calling synchronization primitives.

The system call mechanism should be a single entry mechanism. The main difference from later versions of the kernel is that you are not making an entry by using the INT instruction to trap into the kernel; you will simply make a procedure call instead. This is because there are no user-mode processes in this project. In order to make this mechanism work, you need to understand the stack frame and the calling sequence.

The synchronization primitives lock_acquire() and lock_release() are for threads. They are not designed for processes to synchronize; processes cannot share data structures. On the other hand, they need to deal with the PCB data structures to block and unblock threads. An important step is to figure out how to queue blocked threads. Although it is nice to implement the synchronization primitives in the way that works with a preemptive scheduler, it is not required in this project.

Finally, once all this is up and running we would like you to measure the time taken for a context switch in your system. To do this you can use the provided function get_timer() to get the CPU clock ticks. This call contains a one-line assembly instruction that returns the number of clock cycles that have passed since the processor was booted. The value returned by this function is a 64-bit quantity (unsigned long long int). Note that this function will only run on Pentium or newer processors.

3. Extra credit

You can earn 2 extra points in this project.

To receive one point of extra credit, your implementation needs to keep track of the user and system time used by each process: When a process exits, this usage should be printed (much like 'time' on any UNIX system). You will be measuring the time in clock cycles using the get_timer() routine that you used to measure the time of a context switch.

For the remaining point of extra credit, change the scheduler so that is tries allocating relatively even CPU time to each process or thread. The scheduler can implement a strategy trying to achieve fairness, subject to processes giving up control.

4. Design review

For the design review, you need to have figured out all the details including the PCB data structure, the call sequence executed during a context switch or system call, how process state is saved and restored, etc. In other words, you should understand the role of each function, being ready to implement it.Before you come to meet the TA you should prepare for a brief 10 min presentation on a piece of paper or a text file. An oral-only presentation is not acceptable.

5. Submission

Commit your files as usual using svn commit.

6. Acknowledgments

Once again, we gratefully acknowledge the kindness of the staff of Princeton's COS 318 course for providing us with the material for (and most of the text of) this assignment.

2014-06-17 11:58