LinuxQuestions.org
Latest LQ Deal: Linux Power User Bundle
Go Back   LinuxQuestions.org > Forums > Linux Forums > Linux - Software > Linux - Kernel
User Name
Password
Linux - Kernel This forum is for all discussion relating to the Linux kernel.

Notices


Reply
  Search this Thread
Old 01-22-2012, 10:03 PM   #1
bharathravi1
LQ Newbie
 
Registered: Aug 2007
Posts: 2

Rep: Reputation: 0
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!
 
Old 01-23-2012, 11:04 PM   #2
sundialsvcs
LQ Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 9,078
Blog Entries: 4

Rep: Reputation: 3165Reputation: 3165Reputation: 3165Reputation: 3165Reputation: 3165Reputation: 3165Reputation: 3165Reputation: 3165Reputation: 3165Reputation: 3165Reputation: 3165
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.
 
Old 01-23-2012, 11:29 PM   #3
bharathravi1
LQ Newbie
 
Registered: Aug 2007
Posts: 2

Original Poster
Rep: Reputation: 0
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!
 
Old 01-27-2012, 08:33 AM   #4
sundialsvcs
LQ Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 9,078
Blog Entries: 4

Rep: Reputation: 3165Reputation: 3165Reputation: 3165Reputation: 3165Reputation: 3165Reputation: 3165Reputation: 3165Reputation: 3165Reputation: 3165Reputation: 3165Reputation: 3165
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.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
How to incorporate Contention free period and contention period together in 802.11e? stud17 Linux - Newbie 0 01-20-2012 05:27 PM
LXer: Linux: CFS Scheduler v19, Group Scheduling LXer Syndicated Linux News 0 07-07-2007 06:16 PM
CFS problem kenji Linux - Security 0 03-24-2007 02:30 PM
TrueCrypt vs. CFS kurrupt Linux - Security 4 10-10-2006 05:43 AM
Need help with CFS rjkfsm Linux - Security 1 08-05-2005 11:17 AM

LinuxQuestions.org > Forums > Linux Forums > Linux - Software > Linux - Kernel

All times are GMT -5. The time now is 05:46 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration