Overview

Your task in this project is to extend your non-preemptive user-level threads package with preemption.

In the previous project, you built a non-preemptive thread package and assumed that applications will cooperate with each other and voluntarily yield the CPU frequently. In general, your applications will not be well-behaved, cooperating processes that routinely yield the processor on their own. You need to guard against processes that want to monopolize the CPU by forcibly preempting them and switching to another process.

We have provided you with some code that emulates clock interrupts. The interrupts arrive on the stack of the currently executing thread, just like they do on native hardware. You get to write a clock handler that is supposed to do the right thing in response to the interrupt.

The Details

There are a few distinct components to this project.

1. You will need to make your threads package preemptive. interrupts.h provides the interfaces you will need for this purpose. Soon after you initialize the clock module (using minithread_clock_init) and enable interrupts (set_interrupt_level), you will start getting clock interrupts. You may initially want to set the clock period to a few seconds and print something from the clock interrupt handler to ensure that it is working (but disable such printf statements afterward because you cannot afford to spend time inside an interrupt handler printing things to the screen). You will need to reduce your quanta to ~100 ms once you have a working interrupt handler. Note that interrupts can arrive at any time, at any location in the code. They stop the currently running thread and force it to jump to an interrupt handler. Your code can take control at this point and can force the interrupted thread to yield. Note that there may be places in your code where you really do not want to take clock interrupts, e.g. when manipulating shared data structures. It is ok to briefly disable interrupts at critical moments, as long as this happens in your system code and interrupts are re-enabled shortly thereafter. However, you should never execute any application code with interrupts disabled.

2. Update your semaphore implementation to use TAS so that it is thread safe. Your semaphore implementation should not rely on disabling interrupts to maintain safety, except within the function minithread_unlock_and_stop(tas_lock_t* lock), which is located in minithread.c. If you have written semaphores using TAS in project 1, the minithread_unlock_and_stop() function is the missing piece of the puzzle required for a full preemptive semaphore implementation.

3. Add an alarm facility by which threads can request an arbitrary procedure to be called N milliseconds in the future. You will have to keep track of how many clock ticks have passed by in your clock interrupt handler in order to be able to decide when the alarms ought to expire. It's ok if the user specifies a clocktick value that is above the precision of your time quantum. Do the best you can with such requests instead of ignoring them.

4. Use this alarm facility to implement an interface, minithread_sleep_with_timeout(int timeout), by which threads can give up the CPU, go to sleep (i.e. relinquish the processor entirely) and wake up after a given number of milliseconds have elapsed.

5. Implement multilevel queues and use them to change your FCFS scheduler into a multilevel feedback scheduler with four levels. The quanta size should double at each level. You should use strict priority scheduling between levels. Levels with shorter quanta should receive higher priority than levels with longer quanta. To prevent starvation of lower priority threads your scheduler should not always search for threads starting at level 0. Instead the starting point should be varied in the proportions 50%, 25%, 15% and 10% for levels 0 to 3 respectively. The idle thread should not run unless there are no other tasks to execute.

6. Review the slides from the Project 2 lecture to get implementation hints and other details that were not written on this page.

Tips and tricks

1. A semaphore that is unable to acquire its TAS lock should not yield, but spin.

2. A preemptive semaphore implementation should no longer use minithread_stop(), but minithread_unlock_and_stop() instead.

3. All access to shared data structures should be synchronized. Search your code for places where such accesses are made and reason about where to disable interrupts.

4. Your multilevel feedback scheduler should operate as follows. The scheduler should maintain a multilevel queue with four levels. It should finish a sweep of all queues roughly every 160 ticks. For the first 80 ticks when the scheduler is called to schedule a thread, it should start searching from the top level. For the next 40 ticks it should start searching from the second level, for the next 24 ticks, from the third level and finally for the last 16 ticks, from the fourth and final level.

Scheduling should be round-robin within a level. The searches proceed by going down levels if a particular level is empty and wrap around to the top level if all levels have been searched. A dequeue operation should return a thread if there is even a single thread in the multilevel queue regardless of which level the search began from. A newly created thread enters the system at the very top level queue.

A thread extracted from level i (where the top level is numbered 0 and the levels are numbered from 0 to 3 in order) should be scheduled for 2^i quanta. Threads that yield or block should not have their priority downgraded as they are managing their run time appropriately (it is assumed that giving them a longer time slice would not change their behavior as they have no knowledge of scheduling). If a thread outruns its quanta, it should go into the next level (at the end of the quantum.) If its already at the last level, it should stay there.

5. If the nmake process generates too much text that searching for errors is cumbersome, you may try:

nmake /a | findstr "error warning"

This works like grep and will prune out non-essential lines, leaving behind only compiler errors or warnings. Make sure you omit the letter 's' from the words "error" and "warning" within the double quotes.

6. Avoid recursive functions in the kernel.

Stack space in the kernel is a very scarce resource and should be used sparingly. Each function call requires stack space to store non callee-saved registers that are in use, the return address, and base pointer. This space is not returned until the function returns. If a function calls itself, then it cannot return and release the stack space it occupies until that call returns. If this happens many times, you run the risk of overflowing the stack, (hopefully) resulting in a segmentation fault and a crash. For this reason, you should avoid use of recursion in your kernel.

How to Get Started

Make a backup copy of your code from the previous project, download the code from CMS, and merge. Do not directly overwrite the downloaded files with your own files; this can result in you missing some crucial function signatures.

You should overwrite files you did not change from Project 1 with files from Project 2. Files that were changed in Project 1 should be carefully merged (this is much easier with version control).

Pay careful attention to the merge process to make sure you don't introduce bugs.

Grading

The usual criteria apply: correctness, robustness, and elegance. Additionally, a clean compile will be worth 10%.

Common mistakes

1. Unnecessarily disabling interrupts.

2. Allowing user threads to run with interrupts disabled. (This frequently happens when returning from an interrupt handler without a context switch).

3. Incorrectly synchronized code (especially the portion of OS code that runs just after a context switch).

4. Semaphore implementations that depend on disabling interrupts for correctness (exception: minithread_unlock_and_stop() can disable interrupts).

5. Incorrect thread cleanup/idle thread that takes up non-idle time (these are old requirements but will still be enforced).

How to Test Your Code

It's crucial that systems code be correct and robust. You must write your own test programs and test your code with reasonable and unreasonable test cases, and ensure that it behaves correctly.

Do not forget to check for memory leaks. Your threads package should not run out of memory when large numbers of threads are created and destroyed.

Make sure to test that preemption works with CPU-bound threads, and that your multilevel feedback scheduler is appropriately lowering thread priorities.

Submissions

Use CMS to submit your project. You should include a README file with your name, your partner's name, and anything you think we should know. This includes documenting any broken functionality (although you will have trouble later on if you do not complete this project now, so you should not be submitting a broken project).