Expanded the grading requirements section.
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.
October 2 and 3, 20:30–21:30, in COS 105
October 8, 18:00–22:00, in FC 010 (Fishbowl). Sign up at http://www.cs.princeton.edu/courses/archive/fall07/cos318/signup/signup.cgi.
October 9 and 10, 20:30–21:30, in COS 105
October 15, 23:59
The grading breakdown for the design review is as follows.
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.
1 point. Describe at a medium level how you will implement this part, with particular emphasis on how you are using your data structures.
1 point. Similar to the above.
1 point. Similar to the above.
The threads:
lock_init(&lock);
lock_acquire(&lock);
do_yield();
lock_release(&lock);
do_exit();while(TRUE) {
do_yield();
}do_yield();
lock_acquire(&lock);
lock_release(&lock);
do_exit();lock_acquire(&lock);
lock_release(&lock);
do_exit();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 http://www.win.tue.nl/~aeb/linux/kbd/A20.html.
Synonym for protection ring 0.
The process control block (PCB) contains all of the state the kernel needs to keep track of a process or kernel thread.
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 http://my.execpc.com/~geezer/os/pm.htm.
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.
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.
You should start with the code in arizona.princeton.edu:/u/cos318/2pre. 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.
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.
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.
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.
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.
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.
The boot loader provided to you for this project does more than the one you wrote last project. Specifically, it enables address line 20 and enters protected mode.
One of the first things you will need to do is to implement a queue data structure. gdb is a much nicer environment than bochs in which to debug, so we strongly recommend you that you test your data structure code in user-space first.
We’ve placed examples of how to call C from assembly and vice versa in hello1.c and hello2.S. Build the executable by typing make hello.
The dependencies of the parts of this project look like this:
Processes --> Timing a process context switch
Kernel threads --> Mutual exclusion
Timing a thread context switchWe have tried to specify the scheduler in such a way that at any point in the execution, there is exactly one correct choice for which task to schedule next. If you have even the slightest doubt about what this choice is in some situation, please contact us for clarification—some of our test code will assume that your scheduler is doing what we think it should.
Saving and restoring the general purpose registers (eax, ecx, edx, ebx, esp, ebp, esi, edi) is reasonably straightforward, but the flags register (eflags) is tricky. The only way to save eflags is the instruction pushf, which pushes the contents of eflags onto the stack—eflags is not a valid operand for mov. Similarly, the only way to restore eflags is popf, which pops the top of the stack into eflags. Worse, you must take care not to alter any register before it is saved or after it is restored, and many instructions set and clear flags. Instructions that don’t alter eflags include mov, pop, push, pushf, and ret, while arithmetic operations typically do. Consult the x86 manuals for more information.
To be determined.
As usual, the maximum credit available for the project is 10 points. The high-level breakdown is as follows:
3 points
2 points
2 points
1 point
2 points
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 full names and email addresses of each member of your team.
A statement regarding the correctness of your assignment. Please tell us if there are any parts that you have not implemented, or if some part that you have implemented does not follow the specification, and in what way. If a particular shortcoming results in what we believe to be a disproportionate number of failed tests, we may restore some credit. If you believe your code to be correct in all aspects, please say so.
An overview of your design.
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.