I've been through quite a few explanations about the Completely Fair Scheduler and they all seem to lack an important detail. The way everything is explained essentially comes down to a summary of the run "queue" (actually a red-black tree that keeps an efficient sort), along with details about how each process has its vruntime value updated. I'll skip the summary of the major details, and stick to what is important to my question.

Each time a process is scheduled, its vruntime is updated to reflect how much time it got on CPU. The fact that this value is monotonically increasing (though "strictly increasing" would be more accurate) is called out in most of these descriptions. Each time the OS decides to schedule a new process, it looks at the process with the lowest vruntime and sends it off for execution.

There's a major detail missing in these descriptions. Let's say I have a browser process running, and running, and running..... Over the course of a few days the vruntime for that process is going to get huge, reflecting many hours of CPU time. On the same machine (for the sake of argument, it's single-CPU hardware) is a new CPU-bound process. The scheduler looks at these two processes, sees that the cpu hog has zero vruntime and schedules it.

Every description of CFS I've seen says that this process will run until another process has less vruntime, but that cannot be true. If this were the case, the browser process would starve until the cpu hog caught up with it many hours or days later.

There must be a fudge factor in there, or there must be something more than just the direct comparison of vruntimes going on, but this important detail is skipped in all of these descriptions. What am I missing?

(And, has anyone noticed that a LARGE multi-cpu machine could potentially overflow the vruntime of a process group? It'd have to get something like 544 years of CPU time, but a 64-processor machine working for 10 years..... never mind. =] )


1 Answer 1


So there are two or three points that are missed in the typical CFS description. It IS TRUE that the scheduler will pick up and run the process with the lowest vruntime. However, the vruntime doesn't actually represent how much time the process has spent on a CPU, nor does it represent the time spent in the current run queue. It's a heuristically-calculated value that subtly builds in the required meaning through some deviously clever math.

Each CPU has its own process queue (actually, an RB tree, but it behaves like a queue). Each process queue keeps track of it's "leftmost" process, that's the process with the smallest vruntime. Don't think of any of the vruntimes in the queue as keeping track of total runtime. Instead, think about the DIFFERENCE between a process' vruntime and the smallest runtime in the queue. That difference has an important meaning. It's the difference in run time between the process in question and the leftmost process. In other words, it's how much more CPU time the process has gotten than the leftmost process has gotten.

So, when a brand-new process enters a CPU's queue, it has no vruntime. It simply inherits the same value as the leftmost process. Since their vruntimes are now the same, their difference is zero which makes sense because the new process as no more expected CPU time than the leftmost process. Chances are, the new process will be scheduled at the next context switch.

A process leaves the run queue for any number of reasons; waiting on IO or sleeping are pretty common triggers for leaving the run queue. Anything that causes the process to not need the CPU for a while will cause it to leave the queue. When this happens, the current min vruntime (the vruntime of the leftmost process) will be subtracted from the sleeping process' vruntime. The result is that its vruntime will now reflect how much more CPU time it had than the next-scheduled process. When it tries to join the run queue again, the min vruntime for that queue will be added to the process' vruntime and it will go into the queue somewhere in the middle, in roughly the same location in enjoyed when it left the previous queue.

So that's the explanation. vruntime is manipulated in a clever way to ensure that it can be interpreted as the relative difference in CPU fairness history, whether the process is currently in a run queue, or in between schedulable states.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .