1. The Linux scheduler went through a major overhaul between the 2.4 and 2.6 kernel. The current scheduler can make scheduling decisions in O(i) time. Explain why is this so? 2. In Linux, the data and...

1. The 2.4 kernel introduced to us a simple scheduler that operated in O(N) time (as it iterated over every task during a scheduling event). The 2.4 scheduler divided time into epochs, and within each epoch, every task was allowed to execute up to its time slice. If a task did not use all of its time slice, then half of the remaining time slice was added to the new time slice to allow it to execute longer in the next epoch. The scheduler would simply iterate over the tasks, applying a goodness function, a metric to determine which task to execute next.
Although this approach was relatively simple, there were lots of disadvantages added to it. This scheduler despite being simple lacked the...