Linux Scheduler

See link:

1. http://www.ibm.com/developerworks/linux/library/l-scheduler/
2. http://en.wikipedia.org/wiki/Completely_Fair_Scheduler
3. http://www.ibm.com/developerworks/linux/library/l-completely-fair-scheduler/

3 Linux Scheduling Policies:

•  SCHED_OTHER/SCHED_NORMAL Time-based policy with time slices
• SCHED_FIFO Priority-based policy
• SCHED_RR Priority-based policy with time slices

Linux scheduler queues:

•      runqueue
•      wait_queue or
•      red-black tree

Linux task states :

• TASK_RUNNING(runqueue)
• TASK_INTERRUPTIBLE(wait_queue)
• TASK_UNINTERRUPTIBLE(wait_queue)
• TASK_STOPPED
• TASK_ZOMBIE

Linux Scheduling Algorithm Evolution :

• O(N)
• O(1)
• Completely Fair Scheduler (CFS)