how does linux scheduler manage process scheduling?

Question

I was reading somewhere on the internet, but I dont remember where ... that the Linux scheduler tries to workout "active" queue and process to run in nearly O(1).

My question is, since there are two queues , Active and Expired. and each of the two queues have 140 priority levels. So for each of the 140 priorities there will be separate queue of processes.

If I had to implement with this data, I would make use of "for loops" . Having said that, for loop will be expensive, because there can be N process in any of the 140 queues. So the complexity should be O(N) which shouldn't ever be acceptable for the scheduler.

So how does linux scheduler do that ?

Answer 1

In versions of Linux kernel 2.6 prior to 2.6.23, the scheduler used is an O(1) scheduler by Ingo Molnár.

The scheduler used thereafter is the Completely Fair Scheduler, also by Ingo Molnár, which runs in O(log N) time.

Check out wikipedia article

The following two tutorials completely explains O(1) scheduling Tutorial 1 and Tutorial 2