Program 4: Scheduler

CS 3210 Design of Operating Systems
Spring 2000 * Hutto
Georgia Tech College of Computing

DUE: 1:35 pm (class time) Thursday 30 March 2000

Basic Assignment

For your fourth programming assignment, you will add the scheduling class SCHED_IDLE to the standard Linux scheduler and modify the system call sched_setparam to allow root to assign the SCHED_IDLE scheduling policy to a designated process.

SCHED_IDLE has been much discussed and often proposed in the Linux community. SCHED_IDLE processes (called "idlers') have roughly the same behavior as the standard idle process: they are run only when no other process is runnable. Therefore, the standard scheduler will "pass over" all SCHED_IDLE processes if there are runnable processes belonging to any other scheduling class. It should be possible to have several idlers and you can specify relative priorities for these processes in the same way that you can specify relative priorities for "real-time" processes. The priority of an idler will only be used to distinguish between two or more runnable SCHED_IDLE processes. If there are no idlers, then the standard idle process should be executed (as usual). SCHED_IDLE should be timesliced (like SCHED_OTHER and SCHED_RR). You don't want an idler to hold the CPU indefinitely until it blocks!

Devise a test scenario to demonstrate that your scheduler enhancement works. You should include two scenarios. For the first scenario, start and idler and show that it runs occasionally and properly relinquishes the CPU when other non-idler processes become runnable. This should be easy. The CPU is idle quite often under normal circumstances. You can make a blocked process runnable by typing a character on the console. The second scenario is a bit more difficult. Setup the system with an idler but make sure there is a non-idler that is ALWAYS runnable. Your idler should never run. You can do this by running a "CPU-bound" process (one that performs only computation, no i/o) with a real-time priority. Don't run it using SCHED_FIFO! Why?

Extra Credit

It shouldn't be too difficult to get a SCHED_IDLE scheduling class working under simple workloads. There's only one problem with SCHED_IDLE as we have described it. It suffers from potential DEADLOCK! As recently as 3 weeks ago, Linus Torvalds rejected the inclusion of a SCHED_IDLE patch into the kernel with the following comment:

So why do you think your implementation of this doesn't have the deadlock that every other implementation has?

The deadlock is due to priority inversion, where an "idle-priority" task gets a resource (say the directory semaphore), goes to sleep, and never wakes up again because there is some slightly more important process running all the time.

In short, this has been tried before, and it has ALWAYS been a serious security hole full of denial-of-service kind of attacks.

Not applied.

There are solutions to the "priority inversion" problem. You can read about them in Silberschatz, Galvin and Gagne. Basically you need to detect situations in which a high priority process is blocked waiting for a resource held by a lower priority process. A low priority process is keeping a high priority process that is otherwise runnable from running. The standard solution allows the lower priority process to temporarily "inherit" the priority of the higher priority task so it can complete its work and release the needed resource. The pthreads package under Solaris has a special "priority inheritance mutex" that behaves in this way.

As extra credit, propose and implement a solution to the priority inversion problem created by the SCHED_IDLE scheduling class. You will receive bonus points if your patch is accepted by Linus and included in the standard distribution :-)

Resources

SCHED_IDLE has been extensively discussed in the Linux kernel community and several patches have been proposed. You are free to make use of any resources you can find to help you with this problem. (Hey, its open source.) Just make sure you understand anything you use in your solution!

Turnin

Schedule a demo time with Jason as usual. In addition, you need to submit source and a README file clearly describing your modifications.

Good luck!