Assignment 5: Kernel Programming: A Scheduler with User Fairness

This assignment is to be completed by your group.

The Linux scheduler repeatedly switches between all the running tasks on the system, attempting to give a fair amount of CPU time to each task, favoring interactive tasks. In this project, you will modify the existing scheduling discipline to maintain fairness across users, not tasks. This ensures that no single user can "hog" a system by running lots of CPU-intensive processes.

In the modified scheduler, we instead want the user to act as the resource principal. Each user has her own set of tasks and credits for execution are tracked for each user, not just for each task. (If you prefer, you can also create a new scheduling discipline that has a priority above that of the default scheduler.)

For simplicity, we approximate user allocations by tying credits to the login process for each user. (A user could therefore cheat and log in several times, but we'll ignore that here. If you are adventurous, you might try to address this problem.) Thus, you may need to extend the PCB for processes so that it can track the credit usage for all child processes after each scheduler invocation. The remainder of the default scheduler remains the same.

Each user login process will be allocated a fixed number of credits (say 100). These credits must be shared evenly between the processes associated with that user. A credit is essentially the equivalent of a time slice with its value equal to 100ms/DEF_TIMESLICE. Once a task has exhausted its credits, its credits are replenished and the task is moved to the expired queue. All user login processes will have an equal number of credits.

Most of the code of interest for this assignment is in kernel/sched.c and include/linux/sched.h. These are not the only files you will need to look at, but they're a good start.

You may want to consider turning off SMP operations (CONFIG_SMP), to minimize the spin-locking and other surprises.

It is highly recommended that you study the scheduler chapter in Love.

Testing your scheduler

You will need to test your scheduler to make sure that it works. To do this write a program that goes into an infinite while(1) loop. This program would normally take up 100% of the cpu.

Now create three different users have them each run one or more copies of the loop program. Use the program top to monitor the CPU usage, both before and after you make your scheduler modifications.

Create another test program that alternates I/O with CPU bursts. For example, you could compute the hash for all files in a directory, by reading one file at a time and computing its MD5 or SHA-1 hash. Compare the CPU usage accumulated between the pure CPU and the CPU+I/O program, both in the original 2.6 kernel and your modified version.

Last updated by Henning Schulzrinne