| |||||||||||||
Per-entity load trackingPer-entity load trackingPosted Jan 11, 2013 3:31 UTC (Fri) by thoffman (subscriber, #3063)Parent article: Per-entity load tracking
"Perfect scheduling requires a crystal ball; when the kernel knows exactly what demands every process will make on the system and when, it can schedule those processes optimally".
Actually, I'm pretty sure that's NP-hard, at least for some definitions of optimal. So it might very well be counterproductive to spend the time obtaining an optimal scheduling.
(Log in to post comments)
Per-entity load tracking Posted Jan 11, 2013 9:06 UTC (Fri) by ekj (guest, #1524) [Link]
NP-hard doesn't automatically mean "too hard", just like "solvable in polynomial time" doesn't automatically mean "practical".
I know you didn't claim that, it's just that I've seen one-to-many arguments that consist of "NP-hard, therefore not doable"
If a problem scales as 1.1**n and n is expected to be 100 at most, then it's easily doable (barring huge constant factors), a n**7 algorithm is actually more computationally intensive up to a n of about 350.
I don't know how large the problem-space tends to be for scheduling-problems though.
Per-entity load tracking Posted Jan 24, 2013 1:33 UTC (Thu) by igorrs (guest, #88981) [Link]
Either you misunderstood the quoted text or you quoted the wrong part.
If you were after PERFECT scheduling, finding the solution would require actual prediction of the future (with a crystal ball, for example ;-)). Time complexity was not at stake in that specific sentence.
|
|||||||||||||