CFS mechanism...

April 27, 2012

      Hi,
i have one basic doubt in the CFS algorithm.
Following is my doubts. I am using 2.6.23 as the kernel version

In CFS , when a Sleeping task wants to get inside the Running Queue (
cfs_rq ) , Then it calcluates the its own "vruntime" depend on
"cfs_rq->min_vruntime" and "sysctl_sched_latency". In function
"place_entity" , "vruntime" is assigned the value.
   in brief ===>
            se.vruntime = cfs_rq->min_vruntime - sysctl_sched_latency  (
equation 1 )

  So the process which wants to get inserted in CFS QUEUE ,
         will have a KEY ==> "se->vruntime - cfs_rq->min_vruntime" (
equation 2 )
  If we take merge equation 1 and equation 2 .. then KEY is equal to
"-sysctl_sched_latency".

  So when the Process will be added to RB TREE , then this new Task will
always be the leftmost entry,  as its KEY is in negative value.

I thought if we add the value of "sysctl_sched_latency" in equation "1" ,
then it would have been right as the New task will be waiting minimum
"sysctl_sched_latency" nano seconds before getting schedule ( if run queue
is heavily loaded ).

Can somebody help me in understanding  why we are Subtracting
"sysctl_sched_latency" instead of Adding

Help will be greatly appreciated.

below i have added the code for "place_entity" and "entity_key"
regards
Anirban Roy

static void
place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
u64 vruntime;

vruntime = cfs_rq->min_vruntime;

if (sched_feat(USE_TREE_AVG)) {
struct sched_entity *last = __pick_last_entity(cfs_rq);
if (last) {
vruntime += last->vruntime;
vruntime >>= 1;
}
} else if (sched_feat(APPROX_AVG) && cfs_rq->nr_running)
vruntime += __sched_vslice(cfs_rq->nr_running)/2;

if (initial && sched_feat(START_DEBIT))
vruntime += __sched_vslice(cfs_rq->nr_running + 1);

if (!initial) {
if (sched_feat(NEW_FAIR_SLEEPERS))
vruntime -= sysctl_sched_latency;

vruntime = max_t(s64, vruntime, se->vruntime);
}

se->vruntime = vruntime;

}

static inline s64
entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
return se->vruntime - cfs_rq->min_vruntime;
}