Process Selection
CFS attempts to balance a process’s virtual runtime with a simple rule:When CFS is deciding what process to run next, it picks the process with the smallest vruntime
CFS uses a red-black tree to manage the list of runnable processes and efficiently find the process with the smallest vruntime
. A red-black tree, called an rbtree
in Linux, is a type of self-balancing binary search tree
Picking a Task
Given an rbtree
, the process that CFS wants to run next, which is the process with the smallest vruntime
, is the leftmost node in the tree
static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq) { struct rb_node *left = cfs_rq->rb_leftmost;
if (!left) return NULL;
return rb_entry(left, struct sched_entity, run_node);
}
__pick_next_entity()
does not actually traverse the tree to find the leftmost node, because the value is cached by rb_leftmost
The return value from this function is the process that CFS next runs. If the function returns NULL
, there is no leftmost node, and thus no nodes in the tree. In that case, there are no runnable processes, and CFS schedules the idle task.
Adding a Task
This would occur when a process becomes runnable (wakes up) or is first created via fork()
Adding processes to the tree is performed by enqueue_entity()
Removing a Task
A node is removed from the rbtree
is done by calling dequeue_entity()