Linux Kernel Architecture

Chapter 2: Process Management and Scheduling

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_timelineis the base element to manage all processes in a time-ordered red-black tree.

rb_leftmostis 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 red-

black tree, but since usually only the leftmost element is of interest, this speeds up the average

time spent searching the tree.

❑ currpoints to the schedulable entity of the currently executing process.

2.6.2 CFS Operations

Let us now turn our attention to how the scheduling methods provided by the CF scheduler are imple-

mented.

The VirtualClock

I discussed in the Introduction that the completely fair scheduling algorithm depends on a virtual clock

that measures the amount of time a waiting process would have been allowed to spend on the CPU on

a completely fair system. However, no virtual clockcan be found anywhere in the data structures! This

is because all required information can be inferred from the existing real-time clocks combined with the

load weight associated with every process. All calculations related to the virtual clock are performed in

update_curr, which is called from various places in the system including the periodic scheduler. The

code flow diagram in Figure 2-17 provides an overview of what the function does.

Update physical and virtual run time of the process

Update min_vruntime of the CFS queue

Set rq->exec_start

_ _update_curr

update_curr

Figure 2-17: Code flow diagram forupdate_curr.

First of all, the function determines the currently executing process of the run queue and also obtains the

real clock value of the main scheduler run queue, which is updated at each scheduler tick (rq_ofis an

auxiliary function to determine the instance ofstruct rqthat is associated with a CFS run queue):

static void update_curr(struct cfs_rq *cfs_rq)

{

struct sched_entity *curr = cfs_rq->curr;

u64 now = rq_of(cfs_rq)->clock;

unsigned long delta_exec;

if (unlikely(!curr))

return;

...