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()

results matching ""

    No results matching ""