Working of CFS

["Sukanto Ghosh" <sukanto.cse.iitb@xxxxxxxxx>]

Hi all,

I am trying to understand the working of the CFS.

I have read:
1. http://www.linuxinsight.com/files/sched-design-CFS.txt  (by Ingo Molnar)
2. IBM Linux Developerworks article  "Multiprocessing with the
Complete Fair Scheduler"

But I couldn't properly understand how CFS works.

Specifically my doubts are as under:

1. What is 'fair_clock' ?
(Ingo says it is 'CPU time a runnable task would have fairly gotten,
had it been runnable during that *time* ')

How is this calculated ?

(my understanding:  suppose there are 2 runnable tasks for 4ms and in
the next 4ms there are 4 runnable tasks, then fair_clock would be
incremented by 3ms in this 8ms period ?

If this is correct then, what is *that time* ? is it the 8ms period ? )


2. When is this fair_clock updated ( when a task is 'scheduled in' /
'scheduled out' ) ?


3. Doesn't every runnable task has its own wait_runtime (that's why
p->wait_runtime) ? If so, why is there a wait_runtime in "struct
cfs_rq" ? What does it mean ?


4. When is the p-> wait_runtime updated ?
You queue a process (p->wait_runtime = 0), note its time ta and then
it gets cpu at time tb (p->wait_runtime += (tb-ta)), it runs till time
tc (p->wait_runtime -= (tc-tb))
This is how you do it for a particular process, but what about the
rest of the processes (other than the one scheduled out and the one
scheduled in) ? Shouldn't their p->wait_runtime be updated as well ?
Updating the value for all the tasks in the runqueue would be too much
an overhead, but without updating how do you get their proper position
in the runqueue ?


4. When is a running task preempted ? Or, how is the length of the
timeslices calculated ?


5. The entries (tasks) in the rbtree are sorted on the basis of key =
'rq->fair_clock - p->wait_runtime'.  Suppose a running task is
preempted after running for t ns, then its key would change (as
p->wait_runtime is decremented by t). So, will this task be deleted
and re-inserted into the rbtree as per its new key value ?



Are there any other documents which explain CFS in greater detail ?

-- 
Thanks and Regards,
Sukanto Ghosh

--
To unsubscribe from this list: send an email with
"unsubscribe kernelnewbies" to ecartis@xxxxxxxxxxxx
Please read the FAQ at http://kernelnewbies.org/FAQ