Initial release.
Your task is to extend the support code we give you to a kernel with preemptively scheduled processes and kernel threads. This will consist mainly of writing the timer interrupt handler. You will also implement several synchronization primitives.
David Eisenstat is the TA in charge of this project.
October 16 and 17, 20:30–21:30, in COS 105. Slides (eventually): http://www.cs.princeton.edu/courses/archive/fall07/cos318/projects/precept3_1.pdf
October 22, 18:00–22:00, in FC 010 (Fishbowl). Sign up at http://www.cs.princeton.edu/courses/archive/fall07/cos318/signup/signup.cgi
October 23 and 24, 20:30–21:30, in COS 105. Slides (eventually): http://www.cs.princeton.edu/courses/archive/fall07/cos318/projects/precept3_2.pdf
November 5, 23:59
To be determined precisely. Expect as usual that we will ask you to provide and discuss pseudo-code or code describing how the various parts of the system will work.
Acronym for Interrupt Descriptor Table. This table tells the hardware how to handle interrupts.
Acronym for Interrupt ReQuest.
IRQ 0 is the timer interrupt. Tasks that don’t yield will be interrupted, allowing the kernel to regain control.
When IRQ 0 is enabled, the hardware will occasionally generate spurious IRQ 7s that will crash the kernel if not handled.
The support code is in arizona.princeton.edu:/u/cos318/3pre. Type make to prepare an image file floppy.img for use with bochs. In the fishbowl, make boot loads this image onto a USB stick. Change /dev/sdf to the right device elsewhere.
Some versions of gcc may not support the flag -fno-stack-protector. If you are using one of these versions, it is safe to remove this flag.
The x86 interrupt mechanism is quite complicated, so we will present only the details relevant to this project. Interrupts can be triggered in several different ways: hardware, software, exceptions. The timer interrupt, IRQ 0, is a hardware interrupt, as is IRQ 7. The system call mechanism, which uses the int instruction, is a software interrupt. Exceptions are generated for a variety of invalid actions: dividing by zero, for example, will cause an exception.
The support code installs handlers for IRQ 0, IRQ 7, the system call interrupt, and the various exceptions. Your job for this part is to complete the handler for IRQ 0, entry.S:irq0entry; the others are given to you as examples. The main file you will be working with is entry.S, but you may need to consult other files, especially interrupt.[ch] and scheduler.[ch]. In particular, the definition of the PCB structure has moved to scheduler.h.
The processor takes the following actions on an interrupt.
Disable interrupts.
Push the flags register and the instruction pointer onto the stack.
Jump to the interrupt handler.
Note that if a process is interrupted, the memory addresses above (on the stack; below in physical memory) the top of its stack will be overwritten. This is unfortunate, but we can’t avoid it until processes run at a lower privilege level. For this project, and this project only, the kernel may use user stacks. Once the interrupt handler has run, it returns control to the interrupted task with the iret instruction, which pops the instruction pointer and the flags register, and enables interrupts.
As with entry.S:syscallentry, it may be some time before entry.S:irq0entry actually performs the iret, since other tasks may execute in the middle. IRQ 0 is a hardware interrupt, so you should acknowledge it quickly using the macro entry.S:SENDEOI—otherwise the hardware won’t deliver any more timer interrupts. The other tasks entry.S:irq0entry must perform are
Increment the 64-bit counter numticks.
Increment entry.S:disablecount to reflect the fact that interrupts are off.
If nestedcount is zero, enter the kernel the way a system call would.
Yield.
If nestedcount was zero, leave the kernel the way a system call would.
Decrement entry.S:disablecount in anticipation of
iret.
nestedcount is a field in the PCB. For processes, it is 1 during a system call and 0 otherwise. For threads, it is always 1. You should study how interrupt.c changes this field during a system call.
This may not look very hard, but the tricky part is managing when interrupts are on, and when they are off. Your solution should satisfy the following two properties:
To avoid race conditions, interrupts should be off whenever your code is accessing kernel data structures, primarily the PCBs and task queues.
Interrupts should be on most of the time so that threads, processes, and system calls that take too long are preempted.
The main files you will edit here are sync.[ch], but you will probably need to consult queue.[ch] and scheduler.[ch]. You have to implement condition variables, semaphores, and barriers. We’ve given you an implementation of locks as a reference. These primitives must operate correctly in the face of preemption by turning interrupts on and off with the functions entercritical and leavecritical.
In the descriptions below, if an operation is performed on a uninitialized structure, the results are up to you. All unblocks should place the unblocked thread at the end of the ready queue.
conditioninit(cond) initializes the specified memory to hold a condition variable. As prerequisites to calling conditionwait(lock, cond), the calling thread holds lock. The calling thread atomically releases the lock and blocks until unblocked by one of the following calls. It reacquires the lock before returning. conditionsignal(cond) unblocks the thread that blocked least recently during a conditionwait(cond), if there is one. conditionbroadcast unblocks all threads that blocked during a conditionwait(cond). The order in which the threads are unblocked is not important.
semaphoreinit(sem, value) initializes the specified memory to hold a semaphore whose starting value is value. value is non-negative. semaphoredown(sem) performs a blocking wait until the semaphore value is positive and then decrements it. semaphoreup(sem) increments the semaphore value, unblocking the thread that blocked least recently with a semaphoredown(sem), if that thread exists.
barrierinit(bar, n) initializes a barrier for use by n threads. When a thread calls barrierwait(bar), it blocks until n threads have called barrierwait(bar). The order in which the threads are unblocked is not important.
The sleep()/dosleep() calls work by spinning on numticks. We did this partially to test your implementation of system call preemption and partially so that you could earn 1 point of extra credit by implementing a blocking sleep call. If you choose to do the extra credit, you should add a pair of calls enableblocking()/doenableblocking() that change the behavior of sleep from spinning to blocking for all tasks.
We bowed to popular demand and wrote printf. The interface is familiar, except instead of writing at the cursor, you must specify a line and a column as the first two arguments. Not all formats/options are supported; peruse the source if you have any questions about what is and isn’t supported. The demo code is littered with examples of its use.
To be determined.
As usual, the maximum credit available for the project is 10 points. The high-level breakdown is to be determined.
The README should include the following:
The full names and email addresses of each member of your team.
A statement regarding the correctness of your project. 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, modulo aspects that we discussed in the design review.
The README should NOT contain instructions on how to build your project. We expect that make will prepare the image for bochs, and that make boot will transfer this image to a USB stick.
Strive for clear code with some comments. We don’t have strict rules concerning style.