Proposal

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:

• The first phase includes a rather quick survey of the scheduling algorithms used by other OSes (a sort of sanity check - is the lottery algorithm proposed below reasonable) as well as a more intense investigation of the scheduler used in Linux.
• The second phase consists of modifying the existing scheduling algorithm to perform like an alternative found in the literature. We anticipate implementation of a lottery scheduling algorithm, where each process is given a certain number of lottery tickets and gets to run whenever one of its lottery tickets is randomly selected. Those processes with many lottery tickets correspond to the processes with high priority and will, on average, be run more often than the processes that possess only a small number of tickets.
• The final phase of the project consists of a quantitative comparison of the newly implemented scheduler against the current scheduler. There seems to be a natural (if naive) 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.