Linux 2.6 started with a O(1) complexity scheduler. The code related is found in kernel/sched.h, and include/linux/sched.h .
The latest scheduler being used in CFS scheduler (Completely Fair Scheduler) it uses a red black tree to sort jobs and the leftmost is used for next replacement.
The associated files are sched_fair.c, sched.c, sched_debug.c, sched_rt.c .
Another scheduler which was going to be merged into the main line was Rotating Staircase DeadLine scheduler but wasn't included.
There is a lot of stuff on net to read. Best is the kernel source itself.
zz from linuxforums
