Version History

Version 2

Expanded the grading requirements section.

Version 1

Initial release.


For the rest of the semester, you will be building a simple operating system kernel. The kernel will be written mostly in C and will run in 32-bit protected mode. Your main task for this project is to extend the sources we give you to support non-preemptively scheduled kernel threads and “user” processes, and mutual exclusion besides. You must also measure the cost of context switches between threads and processes. Students in previous semesters have found this project to be significantly harder than the previous one, so start early!

David Eisenstat is the TA in charge of this project.

Dates, Times, and Places

Precept I

October 2 and 3, 20:30–21:30, in COS 105

Design Review

October 8, 18:00–22:00, in FC 010 (Fishbowl). Sign up at

Precept II

October 9 and 10, 20:30–21:30, in COS 105

Project Due

October 15, 23:59

Design Review

The grading breakdown for the design review is as follows.

Data structures diagram

1 point. Draw the contents of the data structures for PCBs, locks, and any other structures you need.


1 point. Given that the threads below are listed in order in tasks.c, explain how the execution unfolds and why.

Kernel threads and scheduling design

1 point. Describe at a medium level how you will implement this part, with particular emphasis on how you are using your data structures.

Processes and system calls design

1 point. Similar to the above.

Mutual exclusion design

1 point. Similar to the above.

The threads:

Thread 1
Thread 2
while(TRUE) {
Thread 3
Thread 4


address line 20

When PCs boot up, addresses 0x100000 to 0x1fffff are aliases for 0x00000 to 0xfffff to accommodate badly written real mode programs. Programs that use more than one megabyte of memory must disable this behavior. See

kernel mode

Synonym for protection ring 0.

process control block

The process control block (PCB) contains all of the state the kernel needs to keep track of a process or kernel thread.

protected mode

In (16-bit) real mode, an address ds:si refers to byte 16*ds + si. In 32-bit protected mode, the segment registers contain offsets into the global descriptor table, whose entries control the translation of memory accesses into physical addresses. The boot block provided to you sets up the global descriptor table and segment registers so that no translation is applied; you can ignore the segment registers for this project. See

protection ring

Intel processors since the 286 have four privilege levels, ring 0 through ring 3. Ring 0 is the most privileged; ring 3 is the least. Typically the kernel runs in ring 0, and user processes run in ring 3. For this project, all processes run in ring 0.

system call

In modern operating systems, processes are enjoined from accessing memory that they do not own. System calls are how processes communicate with the kernel. Typically, the process writes the system call number and its arguments in its own memory, and then it transfers control to the kernel with a special kind of far call. The kernel then performs the desired action and returns control to the process.


Following Linux, we use “task” to mean process or kernel thread.

Getting Started

You should start with the code in Compiling this project is tricky, so we have provided you with a Makefile. If you type make, it will compile all sources and prepare an image floppy.img for use with bochs. We’ve also supplied a bochsrc that instructs bochs to use this image as a floppy. On the fishbowl machines, to load the image onto a USB stick, type make boot. On other machines, edit Makefile to use the appropriate device.

We will use the notation file:symbol to refer to symbol symbol in file file.

Kernel Threads and Scheduling

The kernel proper consists of a collection of kernel threads. These threads run in the most privileged protection ring, and their code is part of the kernel loaded by the boot block. Kernel threads share a flat address space, but they do not share register values or stacks.

After the boot block has loaded the kernel, it calls the function kernel.c:start(). This function performs the setup necessary to run the tasks listed in tasks.c, including initializing process control blocks (PCBs) and allocating a kernel stack for each task. Since there is no fork() call, the number of tasks does not increase, and you are allowed and encouraged to allocate space for the PCBs statically. Stacks are STACKSIZE bytes and are allocated contiguously at increasing addresses starting with STACKMIN. Use the macro common.h:ASSERT() to enforce the invariant that all stacks lie in the interval STACKMIN inclusive to STACKMAX exclusive.

Since you are writing a non-preemptive scheduler, kernel threads run without interruption until they yield or exit by calling scheduler.c:doyield() or scheduler.c:doexit(). These functions in turn call entry.S:schedulerentry(), which saves the contents of the general purpose and flags registers in the PCB of the task that was just running, calls scheduler.c:scheduler() to choose the next task, restores the next task’s registers, and returns to it. (This may seem strange, but we’ll devote part of the precepts to it.) scheduler.c:schedulerentry() must not alter the stack in any way. scheduler.c:scheduler() chooses the next task to run in a strict round-robin fashion, and in the first round, the tasks are run in the order in which they are specified in tasks.c.

scheduler.c:scheduler() increments the global variable scheduler.c:schedulercount every time it runs. Don’t change this.

Processes and System Calls

In future projects, processes will have their own protected address spaces and run in a less privileged protection ring than the kernel. For now, however, there are only slight differences between threads and processes. Unlike threads, processes are allocated two stacks: one user stack, for the process proper, and one kernel stack, for system calls made by the process. Moreover, process code is not linked with the kernel, although for this project it is part of the image loaded by the boot block.

There are two system calls: syslib.c:yield() and syslib.c:exit(). These correspond to scheduler.c:doyield() and scheduler.c:doexit() respectively. Processes cannot invoke the latter directly, since they don’t know the address of these functions, and (in later projects), they don’t have the requisite privileges to modify kernel data structures. This project uses a simple dispatch mechanism to overcome the former difficulty. kernel.h defines an address ENTRYPOINT, at which kernel.c:start() writes the address of the function entry.S:kernelentry(). To make a system call, syslib.c:SYSCALL calls the function at this address, passing the number of the desired call as an argument. entry.S:kernelentry() saves the registers in a different part of the PCB than is used by entry.S:schedulerentry(), restores the kernel stack and calls kernel.c:kernelentryhelper(), which calls the appropriate function in scheduler.c. On return, entry.S:kernelentry() restores the registers and returns to the user process. In later projects, this mechanism will become more complicated.

Mutual Exclusion

lock.c contains three functions for use by kernel threads: lockinit(), lockacquire(), and lockrelease(). lockinit() initializes a lock structure; initially no thread holds the lock. In the event an uninitialized lock structure is passed to the other functions, the results are up to you.

Threads call lockacquire() to acquire the lock. If no thread currently holds the lock, it marks the lock as being held and returns. Otherwise it uses scheduler.c:block() to indicate to the scheduler that it is waiting for the lock and should not be run, and then it yields. When lockrelease() is called by the thread holding the lock, it passes the lock to the process that has been waiting longest and unblocks it. If no processes are waiting, it marks the lock as being not held. When a thread is unblocked, all tasks that are currently neither blocked nor running should be scheduled first. The results of a thread attempting to acquire a lock it already holds or to release a lock it doesn’t hold are up to you.

We have put a non-conforming implementation of mutual exclusion in lock.c so that you can write and test the kernel threads part in isolation. When you are ready to test your own implementation, change the constant lock.c:SPIN to FALSE.

Timing a Context Switch

The function util.c:gettimer() returns the number of instructions that have been executed since boot. Using util.c:printint() and util.c:printstr(), use the first line of the display to show us the number of cycles required by a context switch between threads and between processes. We’ve left space in th3.c and process3.c for your code.

Extra Credit

For 1 point extra credit: using util.c:gettimer(), implement a scheduler that allocates CPU time fairly, together with some tests that prove to us that it’s working. Please read the submission instructions below—you will turn in this scheduler separately. The grading criteria will be similar to that of the main assignment.



To be determined.

Grading Criteria

As usual, the maximum credit available for the project is 10 points. The high-level breakdown is as follows:

Kernel threads and scheduling

3 points

Processes and system calls

2 points

Mutual exclusion

2 points

Timing a context switch

1 point

README and style

2 points

Doesn’t run in bochs or doesn’t run in the fishbowl

1 point penalty, at most. Specifically, we will run the test scripts both in bochs and in the fishbowl. Your score for the first four categories will be the maximum of (the lower score) and (the higher score minus one).

For the first four categories, we will prepare test scripts to determine the number of points awarded, and we will make these scripts available to you at some point after the turn-in. We will provide a couple of tests in advance so that you can ensure your code is compatible with our test harness.

The README should consist of the following:

The README should NOT contain instructions on how to build your assignment. We expect that make will prepare the image for bochs, and that make boot will transfer this image to a USB stick.

As for style, strive for clear code with some comments, but know that we won’t be Miss Manners.