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

To unpack and set up minithreads in Visual Studio under Windows NT, do the following:

• Make a backup copy of your Project 1 code.
• Download the code from the course management website.
• The rest of the instructions are the same as those for Project 1. You can change which main routine you are linking against by modifying the Makefile, which should make life a little easier.

If you have problems or questions, please send mail to cs414-staff@cs.cornell.edu or come to office hours for one of the TAs.

Grading

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 ports are created and destroyed.

Submissions

For the Adventurous

Use network.[ch] to implement unreliable datagrams.

Final Word