Scheduling with CFS: what happens at the end of a period?
Linux - KernelThis forum is for all discussion relating to the Linux kernel.
Notices
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQ-related cookies.
Get a virtual cloud desktop with the Linux distro that you want in less than five minutes with Shells! With over 10 pre-installed distros to choose from, the worry-free installation life is here! Whether you are a digital nomad or just looking for flexibility, Shells can put your Linux machine on the device that you want to use.
Exclusive for LQ members, get up to 45% off per month. Click here for more info.
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)
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?
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.
Last edited by sundialsvcs; 01-27-2012 at 08:37 AM.
LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.