CSC573 (Linux Internals)
Project Proposal -- 10/20/1999
Nathan Sprague, Brandon Sanders
The scheduler is a central component of all modern multi-tasking operating systems. The algorithm used to implement the scheduler balances important goals such as interactivity and efficient CPU utilization while striving to ensure that no processes are starved (i.e., regardless of load, all processes get to use the processor at regular, predictable intervals). Consequently, we will examine Linux's scheduling algorithm as well as those of other OSes, implement an alternative scheduling method and perform quantitative comparisons between the newly implemented and pre-existing schedulers.
This project will be executed in three phases:
There seems to be a natural (if naïve) way of implementing the lottery scheduling algorithm using the pre-existing framework. When deciding which process to run next, rather than running the process with the highest dynamic priority, pick at random a number and determine which process's ticket that number corresponds to. This determination could take several forms. A straightforward method entails walking down the ready list subtracting the dynamic priority of each process encountered from the lottery value -- the process whose priority takes the lottery value below zero is then run.
This project is pedagogically important because it examines a core OS concept, namely that of scheduling processes effectively. It is reasonable because the framework that exists appears to be extensible without significant modification. As a contribution to Linux this project may also be valuable since scheduler performance is at the heart of OS performance.