The Multi Level Feedback Queue

First described by Corbato et al. We want to minimize response time while also minimizing turnaround time (all without a priori knowledge of a program.

Some basic rules

This is a pretty solid setup. It allows us to basically approximate SJF. But there are some problems. First, there's the problem of starvation. If there are a bunch a jobs, some processes will get pushed to lower and lower priorities - eventually leading to a point where they don't get any CPU time. Another problem is that this scheduler is insecure. It's easy to game. We can execute a process for 99% of the allotment time and then call an I/O operation to stay in the highest priority queue.

To solve starvation, we'll boost all processes to the top priority every now and then. This helps use prevent stavation (and also optimizes for processes that get less intensive as they continue to execute)

To prevent people from taking advantage of the scheduler, we can account for the CPU time at each level of the queue. In other words, we don't reset allotment time after something like an I/O, we add to the allotment time that was used earlier.

Ousterholt's Law

There are so many "random numbers" that we're using. How do we know that best number of queues? How do we figure out all these random choice intervals. This is a common problem in cs and can only really be solved by testing & praying.

Solaris and FreeBSD

Solaris and FreeBSD use tables, formulas, and other metrics to calculate these "random numbers." Some other schedulers implement MLFQ in different ways. Some schedulers prioritize OS process timing over anything else. Some schedulers even allow for user input (check out the nice command in Linux)