Mastering Linux Kernel Development

CFS's runqueue

CFS sheds the need for a normal runqueue and uses a self-balancing, red-black tree instead to get to the next best process to run in the shortest possible time. The RB tree holds all the contending processes and facilitates easy and quick insertion, deletion, and searching of processes. The highest-priority process is placed to its leftmost node. The pick_next_task() function now just picks the leftmost node from the rb tree to schedule.