kernel 2.6 scheduling time complexity o(1)

The highest priority level, with at-least ONE task in it, is selected. This takes a fixed time ( say t1 )

The first task ( head of the doubly-linked list ) in this priority level is allowed to run. This takes a fixed time ( say t2 )

Total time taken for selecting a new process is t = t1 + t2 ( Fixed )

The time taken for selecting a new process will be fixed( constant time irrespective of number of tasks )

Deterministic algorithm !!



Kernel 2.4 had Global runqueue. All CPUs had to wait for other CPUs to finish execution.

An O(n) scheduler.
In 2.4, the scheduler used to go through the entire “ global runqueue” to determine the next task to be run.

This was an O(n) algorithm where 'n' is the number of processes. The time taken was proportional to the number of active processes in the system.

This lead to large performance hits during heavy workloads.