Data Structures

First, I need to introduce how the CFS run queue looks. Recall that an instance is embedded into each per-CPU run queue of the main scheduler:

kernel/sched.c struct cfs_rq {

struct load_weight load; unsigned long nr_running;

u64 min_vruntime;

struct rb_root tasks_timeline; struct rb_node *rb_leftmost;

struct sched_entity *curr;

The individual elements have the following meaning:

□ nr_running counts the number of runnable processes on the queue, and load maintains the cumulative load values of them all. Recall that you have already encountered the load calculation in Section 2.5.3.

□ min_vruntime tracks the minimum virtual run time of all processes on the queue. This value forms the basis to implement the virtual clock associated with a run queue. The name is slightly confusing because min_vruntime can actually be bigger than the vruntime setting of the leftmost tree element as it needs to increase monotonically, but I will come back to this when I discuss how the value is set in detail.

□ tasks_timeline is the base element to manage all processes in a time-ordered red-black tree. rb_leftmost is always set to the leftmost element of the tree, that is, the element that deserves to be scheduled most. The element could, in principle, be obtained by walking through the redblack tree, but since usually only the leftmost element is of interest, this speeds up the average time spent searching the tree.

□ curr points to the schedulable entity of the currently executing process.

Was this article helpful?

0 0

Post a comment