Linux Kernel Architecture

Chapter 2: Process Management and Scheduling

2.6.3 Queue Manipulation

Two functions are available to move elements to and from the run queue:enqueue_task_fairand

dequeue_task_fair. Let us concentrate on placing new tasks on the run queue first.

Besides pointers to the generic run queue and the task structure in question, the function accepts one

more parameter:wakeup. This allows for specifying if the task that is enqueued has only recently been

woken up and changed into the running state (wakeupis 1 in this case), or if it was runnable before

(wakeupis 0 then). The code flow diagram forenqueue_task_fairis shown in Figure 2-20.

enqueue_task_fair

return

enqueue_entity

update_curr

place_entity

enqueue_sleeper

se != cfs_rq->curr _ _enqueue_entity

Task has been woken up?

Already on runqueue?

Figure 2-20: Code flow diagram forenqueue_task_fair.

If the task is already on the run queue as signaled by theon_rqelement ofstruct sched_entity,noth-

ing needs to be done. Otherwise, the work is delegated toenqueue_entity, where the kernel takes the

opportunity to update the statistics withupdater_curr.

If the task has recently been running, its virtual run time is still valid, and (unless it is currently executing)

it can be directly included into the red-black tree with__enqueue_entity. This function requires some

mechanics to handle the red-black tree, but it can rely on standard methods of the kernel (see Appendix C

for more information) and is thus not very interesting. The essential point is that the process is placed at

the proper position, but this has already been ensured before by setting thevruntimefield of the process,

and by the constantmin_vruntimeupdates performed by the kernel for the queue.

If the process has been sleeping before, the virtual run time of the process is first adjusted in

place_entity^30 :

kernel/sched_fair.c

static void

place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)

(^30) Note that the real kernel sources will execute portions of the code depending on outcomes ofsched_featurequeries. The CF
scheduler supports some ‘‘configurable’’ features, but they can only be turned on and off in debugging mode — otherwise, the set
of features is fixed. I will therefore ignore the feature selection mechanism and consider only those that are always compiled in and
active.