CS4411
Practicum in Operating Systems

Project 2: Preemptive Multitasking

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

../../images/alarm.gif

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

Note

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 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 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 milliseconds have elapsed.

Finally, 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.

Tips and tricks

../../images/clock4.gif

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. Threads that yield or block should not be aged 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 it.) If its already at the last level, it should stay there.

How to Get Started

../../images/clock5.gif

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

The new code's README should have both a link to this page, and a list of all files changed. You should overwrite files you did not change from Project 1 with files from Project 2. Files that were changed in both versions should be 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.

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.

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

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

We will maintain a list of 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.

Powered by Firmant