COS 318 : Operating system
Fall 2003, Princeton University

Project 2: Non-Preemptive Scheduling

Important Dates:

          Design review: 7 PM Monday, October 4, 2004 
          Due: 11:59 PM Monday, October 11, 2004


With the bootup mechanism built in the first project, we can start developing a 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 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. 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, subsequently 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 /u/cos318/2_pre/ as a starting point for your project. We provide you with 20 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).

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

To signup for the design review, please use online signup form here.

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.

In the template file kernel.c, you need to implement _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.


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 as discussed in the class. The main difference 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 is 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 a provided function get_timer() to get the CPU clock ticks. This call contains basically an one-line assembly instruction that returns the number of clock cycles that have passed since the processor was booted. Note that the value returned is a 64-bit quantity (unsigned long long int). Also, notice that this function will only run on Pentium or newer processors.

Extra Credit

You can earn 1 extra point in this project.

To receive an 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. (1/2 point).

For the remaining 1/2 point 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. (1/2 point)

Useful Resources

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. Only oral presentation is not acceptable.

Submitting Programming Assignments

Submit your final solution electronically using the following command:

/u/cos318/bin/318submit 2 README entry.S kernel.c kernel.h threads.c threads.h scheduler.c scheduler.h  <other files>

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.


CS318 Staff