PortOS Project 2

Preemption, Alarms and Multi-level Feedback Queues


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

First, 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 (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 printfs because you cannot afford to spend time inside an interrupt handler printing things to the screen. You also need to reduce your quanta to ~100 ms.). Note that interrupts can arrive at any time, at any location in the code. They stop the currently running process and force it to jump to an interrupt handler. Your code can take control at this point and can force the interrupted process to yield. Note that there may be places in your code where you really do not want to take clock interrupts, e.g. when some system invariant is momentarily violated. It is ok to briefly disable interrupts at critical moments, as long as this happens in your system code and interrupts are reenabled shortly thereafter. However, you should never execute any application code with interrupts disabled. Also you should be aware that minithread_switch enables interrupts just after switching to the new thread.

Second, add an alarm facility by which processes can request an arbitrary procedure to be called N microseconds 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 below the precision of your time quantum. Do the best you can with such requests instead of ignoring them.

Third, 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 microseconds have elapsed.

Finally, implement multilevel queue's and use them to change your FCFS scheduler into a multilevel feedback scheduler with four levels. The quanta 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.

Tips and tricks

Many real systems attempt to use existing code, for instance, old device drivers, even though it may not be well integrated with the new system. Your OS is no exception. We would like you to be able to use the existing Windows libraries, but these libraries are not thread-safe. For example, if multiple minithreads concurrently attempt to allocate memory or print to the screen, you may get a crash in library code. To avoid this, we turn off preemption whenever your threads execute library code. More specifically, if a clock interrupt arrives while you are in a library, we ignore it and wait for the next one. This is a cheap and easy technique to let you continue to use legacy code without having to rewrite all of it. The downside is that programs that spend virtually all of their time in a library (e.g. performing tons of output to the screen in a loop) will not receive clock interrupts. You have two options: rewrite the C library to be minithread-safe, or restructure your program to spend less time in library code. 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 from which level the search began. A newly created process 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. If a thread outruns its quanta, yields or stops, then when it goes back into the multi-level queue, it should go into the next level (at the end of it.) If its already at the last level, it should stay there.

How to Get Started

Make a backup copy of your code from the previous project, download the code from here portos2.zip, and merge.


The usual criteria apply: correctness, robustness, and elegance. Unnecessarily disabling interrupts will be penalized. Incorrect thread cleanup, and an idle thread that takes up non-idle time will also be penalized.

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.


Consult the submission guidelines to find out how to submit your work.

For the Adventurous

Note: These suggestions for an extra challenge will be examined but not graded. They will have no impact on the class grades. They are here to provide some direction to those who finish their assignments early and are looking for a way to impress friends and family.

Use network.[ch] to implement unreliable datagrams.

Final Word

Here are the frequently asked questions about this project.

If you need help with any part of the assignment, we are here to help. If you start early, getting alarms to execute correctly should be a lot of fun. Note that alarms rarely go off when they are supposed to under Outlook on Win2K, so getting your alarms right will result in a more reliable alarm subsystem than those found in a successful commercial OS.

Emin Gün Sirer, May 2002