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
