Scheduling with CFS: what happens at the end of a period?
 

Hi all,

I'm trying to figure out the CFS scheduler.
I understand it splits up the current "period" (20ms by default) into virtual time slices for each entity.

However, what happens when the current period ends? Is the virtual runtime reset to zero for all runnable tasks? (This sounds quite inefficient, which is why I ask)

Clarifications would be greatly appreciated!

Thanks!

The "current period" (more properly called the "epoch") per se does not "end." Rather, it is an interval of time over which the upcoming scheduling-events are distributed.

Ah I see, thanks for clarifying.
A related followup: I understand every entity starts of with zero virtual runtime,
which gets incremented appropriately each time it runs.

The scheduler picks the task with lowest vruntime on every scheduler tick.
If this is the basic algorithm, where does epoch length feature in this? (The algorithm
could in theory run infinitely without worrying about an epoch at all).

Is the epoch length used to alter the scheduler tick frequency somehow?

Thanks a lot!

No, think of "epoch" simply as a convenient mathematical device. Think of it sort-of like a ruler, of some certain length, such that if you set it down on top of the time-line, and no matter exactly where you set it, the events that fall underneath it ought to look more-or-less "evenly distributed." If they do not, then some adjustment or another needs to be made to the machine.

The flow of events, of course, is continuous in nature, not periodic, hence the notion of an epoch "beginning" or "ending" or "being consecutive" (all of which would imply, "periodic") is not meant to be strongly held. Rather, it is an interval of time, of known and agreed-upon (and malleable) duration but not a strict starting-point, over which the distribution of events ought to be seen to fall in a certain way.

Think "applied statistics," because that's really what this is. The stream is constantly flowing past your feet, and you're dipping a bucket into it (you know the size of the bucket, but it doesn't matter when or where you dipped it...). You are in effect taking a random sample, and making adjustments based upon what's in that sample right now.

The decision that the scheduler must make during a timer-interrupt is designed to be simple: i.e. "it's no decision at all." This is what makes it fast. The notion of an epoch, then, is what makes it reactive while nevertheless being fast. On a foggy night, the length of the epoch is how far (and/or behind) the car the headlights will reach.