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:

• Initialize processes and threads including their stack(s) and related kernel data structures.

• Implement a simple, non-preemptive scheduler such that every time a thread calls yield() or exit(), the scheduler picks the next thread and schedules it. As discussed in class, threads need to explicitly call yield() or exit(), in order to invoke the scheduler, otherwise a thread can run forever.

• Implement a very simple system call mechanism. Since everything in this project runs in only the kernel mode, the system call mechanism can be a simple jump table. But the basic single-entry system call framework should be in place. You are required to implement two system calls: yield() and exit(). As previously mentioned, processes can make system calls, while threads can call scheduler functions directly.

• Implement two synchronization primitives for mutual exclusion:  lock_acquire() and lock_release(). Their semantics should be identical to that described in Birrell's paper (see BirrellThreads). To implement lock_acquire() and lock_release(), the scheduler needs to support block()  and unblock() for threads and processes. Blocking and unblocking is performed within the kernel - these are not system calls.

• Measure the running time of a process/thread context switch.

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

• Makefile: A make file 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 the USB disk.

• kernel.h: Interface for the kernel.

• kernel.c: A template for you to write the implementation of the kernel.

• common.h: Commonly used definitions.

• lock.h: Interface for the synchronization primitives.

• lock.c: Template for you to write the implementation of the synchronization primitives.

• th.h: Declaration of threads in th1.c and th2.c.
• th1.c: Code of the first kernel thread.
• th2.c: Code of two kernel threads to test the synchronization primitives.
• process1.c: A user process.
• process2.c: Another user process.
• scheduler.h: Interface of the scheduler, part of the kernel

• scheduler.c: Template for you to write scheduler functions

• entry.S: Template for assembly code that used by the kernel and scheduler

• util.h: Declaration of useful routines like print_int() and get_timer().

• util.c: Implementation of the functions declared in util.h.
• syslib.h: Interface for the kernel functions available to processes.
• syslib.c: Implementation of the functions declared in syslib.h.
• bochsrc: The usual bochs initialization file.

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.