Skip to contentSkip to conversation

plugsched-2.0 patches ...

RFC Peter Williams 7 participants 11 messages Jan 20, 2005 – Jan 21, 2005

lore
Share & tools
lore
#0 lore raw

... are now available from:

<http://prdownloads.sourceforge.net/cpuse/plugsched-2.0-for-2.6.10.patch?download>

as a single patch to linux-2.6.10 and at:

<http://prdownloads.sourceforge.net/cpuse/plugsched-2.0-for-2.6.10.patchset.tar.gz?download>

as a (gzipped and tarred) patch set including "series" file which nominates the order of application of the patches.

This is an update of the earlier version of plugsched (previously released by Con Kolivas) and has a considerably modified scheduler interface that is intended to reduce the amount of code duplication required when adding a new scheduler. It also contains a sysfs interface based on work submitted by Chris Han.

This version of plugsched contains 4 schedulers:

1. "ingosched" which is the standard active/expired array O(1) scheduler created by Ingo Molnar,
2. "staircase" which is Con Kolivas's version 10.5 O(1) staircase scheduler,
3. "spa_no_frills" which is a single priority array O(1) scheduler without any interactive response enhancements, etc., and
4. "zaphod" which is a single priority array O(1) scheduler with interactive response bonuses, throughput bonuses and a choice of priority based or entitlement based interpretation of "nice".

Schedulers 3 and 4 also offer unprivileged real time tasks and hard/soft per task CPU rate caps.

The required scheduler can be selected at boot time by supplying a string of the form "cpusched=<name>" where <name> is one of the names listed above.

The default scheduler (that will be used in the absence of a "cpusched" boot argument) can be configured at build time and is set to "ingosched" by default.

The file /proc/scheduler contains a string describing the current scheduler.

The directory /sys/cpusched/<current scheduler name>/ contains any scheduler configuration control files that may apply to the current scheduler.

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
#2 lore raw
In reply to Peter Williams

Peter, thank you for maintaining Con's plugsched code in light of Linus' and Ingo's prior objections to this idea. On the one hand, I partially agree with Linus&Ingo's prior views that when there is only one scheduler that the rest of the world + dog will focus on making it better. On the other hand, having a clean framework that lets developers in a clean way plug in new schedulers is quite useful.

Linus & Ingo, it would be good to have an indepth discussion on this topic. I'd argue that the Linux kernel NEEDS a clean pluggable scheduling framework.

Let me make a case for this NEED by example. Ingo's scheduler belongs to the egalitarian regime of schedulers that do a poor job of isolating workloads from each other in multiprogrammed environments such as those found on Enterprise servers and in my case on PlanetLab (www.planet-lab.org) nodes. This has been rectified by HP-UX, Solaris, and AIX through the use of fair share schedulers that use O(1) schedulers within a share. Currently PlanetLab uses a CKRM modified version of Ingo's scheduler. Similarly, the linux-vserver project also modifies Ingo's scheduler to construct an entitlement based scheduling regime. These are not just variants of O(1) schedulers in the sense of Con's staircase O(1). Nor is it clear what the best type of scheduler is for these environments (i.e., HP-UX, Solaris and AIX don't have it fully solved yet either). The ability to dynamically swap out schedulers on a production system like PlanetLab would help in determining what type of scheduler is the most appropriate. This is because it is non-trivial, if not impossible, to recreate the multiprogrammed workloads that we see in a lab.

For these reasons, it would be useful for plugsched (or something like it) to make its way into the mainline kernel as a framework to plug in different schedulers. Alternatively, it would be useful to consider in what way Ingo's scheduler needs to support plugins such as the CKRM and Vserver types of changes.

Best regards,
Marc

#3 lore raw
Quoted 10 lines · Marc E. Fiuczynski

Peter, thank you for maintaining Con's plugsched code in light of Linus' and Ingo's prior objections to this idea. On the one hand, I partially agree with Linus&Ingo's prior views that when there is only one scheduler that the rest of the world + dog will focus on making it better. On the other hand, having a clean framework that lets developers in a clean way plug in new schedulers is quite useful.

Linus & Ingo, it would be good to have an indepth discussion on this topic. I'd argue that the Linux kernel NEEDS a clean pluggable scheduling framework.

Is this something that would benefit from several trips around the -mm series?

ISTR that we started with one disk elevator, and now we have 3 or 4 that are selectable on the fly after some banging around in -mm. (And yes, I realize that the only reason we can change the elevator on the fly is because it can switch from the current to the 'stupid FIFO none' elevator and thence to the new one, which wouldn't really work for the CPU scheduler....)

All the arguments that support having more than one elevator apply equally well to the CPU scheduler....

#4 lore raw
Quoted 15 lines · On Thu, Jan 20 2005, [email protected] wrote:
Quoted 10 lines · Marc E. Fiuczynski

Peter, thank you for maintaining Con's plugsched code in light of Linus' and Ingo's prior objections to this idea. On the one hand, I partially agree with Linus&Ingo's prior views that when there is only one scheduler that the rest of the world + dog will focus on making it better. On the other hand, having a clean framework that lets developers in a clean way plug in new schedulers is quite useful.

Linus & Ingo, it would be good to have an indepth discussion on this topic. I'd argue that the Linux kernel NEEDS a clean pluggable scheduling framework.

Is this something that would benefit from several trips around the -mm series?

Quoted 6 lines

ISTR that we started with one disk elevator, and now we have 3 or 4 that are selectable on the fly after some banging around in -mm. (And yes, I realize that the only reason we can change the elevator on the fly is because it can switch from the current to the 'stupid FIFO none' elevator and thence to the new one, which wouldn't really work for the CPU scheduler....)

I don't think you can compare the two. Yes they are both schedulers, but that's about where the 'similarity' stops. The CPU scheduler must be really fast, overhead must be kept to a minimum. For a disk scheduler, we can affort to burn cpu cycles to increase the io performance. The extra abstraction required to fully modularize the cpu scheduler would come at a non-zero cost as well, but I bet it would have a larger impact there. I doubt you could measure the difference in the disk scheduler.

There are vast differences between io storage devices, that is why we have different io schedulers. I made those modular so that the desktop user didn't have to incur the cost of having 4 schedulers when he only really needs one.

Quoted 2 lines

All the arguments that support having more than one elevator apply equally well to the CPU scheduler....

Not at all, imho. It's two completely different problems.

Signature · 1 line
Jens Axboe
#5 lore raw

Paraphrasing Jens Axboe:

Quoted 8 lines

I don't think you can compare [plugsched with the plugio framework]. Yes they are both schedulers, but that's about where the 'similarity' stops. The CPU scheduler must be really fast, overhead must be kept to a minimum. For a disk scheduler, we can affort to burn cpu cycles to increase the io performance. The extra abstraction required to fully modularize the cpu scheduler would come at a non-zero cost as well, but I bet it would have a larger impact there. I doubt you could measure the difference in the disk scheduler.

Modularization usually is done through a level of indirection (function pointers). I have a can of "indirection be gone" almost ready to spray over the plugsched framework that would reduce the overhead to zero at runtime. I'd be happy to finish that work if it makes it more palpable to integrate a plugsched framework into the kernel?

Marc

#6 lore raw
Quoted 12 lines · Marc E. Fiuczynski

Paraphrasing Jens Axboe:

Quoted 8 lines

I don't think you can compare [plugsched with the plugio framework]. Yes they are both schedulers, but that's about where the 'similarity' stops. The CPU scheduler must be really fast, overhead must be kept to a minimum. For a disk scheduler, we can affort to burn cpu cycles to increase the io performance. The extra abstraction required to fully modularize the cpu scheduler would come at a non-zero cost as well, but I bet it would have a larger impact there. I doubt you could measure the difference in the disk scheduler.

Quoted 5 lines

Modularization usually is done through a level of indirection (function pointers). I have a can of "indirection be gone" almost ready to spray over the plugsched framework that would reduce the overhead to zero at runtime. I'd be happy to finish that work if it makes it more palpable to integrate a plugsched framework into the kernel?

The indirection was a minor point. On modern cpus it was suggested by wli that this would not be a demonstrable hit in perormance. Having said that, I'm sure Peter would be happy for another developer. I know how tiring and lonely it can feel maintaining such a monster.

Cheers,
Con

#7 lore raw
Quoted 15 lines · Con Kolivas
Quoted 13 lines · Marc E. Fiuczynski

Paraphrasing Jens Axboe:

Quoted 8 lines

I don't think you can compare [plugsched with the plugio framework]. Yes they are both schedulers, but that's about where the 'similarity' stops. The CPU scheduler must be really fast, overhead must be kept to a minimum. For a disk scheduler, we can affort to burn cpu cycles to increase the io performance. The extra abstraction required to fully modularize the cpu scheduler would come at a non-zero cost as well, but I bet it would have a larger impact there. I doubt you could measure the difference in the disk scheduler.

Quoted 8 lines
Quoted 5 lines

Modularization usually is done through a level of indirection (function pointers). I have a can of "indirection be gone" almost ready to spray over the plugsched framework that would reduce the overhead to zero at runtime. I'd be happy to finish that work if it makes it more palpable to integrate a plugsched framework into the kernel?

The indirection was a minor point. On modern cpus it was suggested by wli that this would not be a demonstrable hit in perormance. Having said that, I'm sure Peter would be happy for another developer. I know how tiring and lonely it can feel maintaining such a monster.

Indeed, the more hands the lighter the load.

Another issue (than indirection) that I think needs to be addressed at some stage is freeing up the memory occupied by the code of the schedulers that were unlucky not to be picked. Something like what __init offers only more selective.

And the option of allowing more than one CPU per run queue is another direction that needs addressing. This could allow a better balance between the good scheduling fairness that is obtained by using a single run queue with the better scalability obtained by using separate run queues.

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
#8 lore raw
In reply to Marc E. Fiuczynski
Quoted 11 lines · Marc E. Fiuczynski

Peter, thank you for maintaining Con's plugsched code in light of Linus' and Ingo's prior objections to this idea. On the one hand, I partially agree with Linus&Ingo's prior views that when there is only one scheduler that the rest of the world + dog will focus on making it better. On the other hand, having a clean framework that lets developers in a clean way plug in new schedulers is quite useful.

Linus & Ingo, it would be good to have an indepth discussion on this topic. I'd argue that the Linux kernel NEEDS a clean pluggable scheduling framework.

Quoted 7 lines

Let me make a case for this NEED by example. Ingo's scheduler belongs to the egalitarian regime of schedulers that do a poor job of isolating workloads from each other in multiprogrammed environments such as those found on Enterprise servers and in my case on PlanetLab (www.planet-lab.org) nodes. This has been rectified by HP-UX, Solaris, and AIX through the use of fair share schedulers that use O(1) schedulers within a share. Currently PlanetLab uses a CKRM modified version of Ingo's scheduler.

I'm hoping that the CKRM folks will send me a patch to add their scheduler to plugsched :-)

Quoted 19 lines

Similarly, the
linux-vserver project also modifies Ingo's scheduler to construct an entitlement based scheduling regime. These are not just variants of O(1) schedulers in the sense of Con's staircase O(1). Nor is it clear what the best type of scheduler is for these environments (i.e., HP-UX, Solaris and AIX don't have it fully solved yet either). The ability to dynamically swap out schedulers on a production system like PlanetLab would help in determining what type of scheduler is the most appropriate. This is because it is non-trivial, if not impossible, to recreate the multiprogrammed workloads that we see in a lab.

For these reasons, it would be useful for plugsched (or something like it) to make its way into the mainline kernel as a framework to plug in different schedulers. Alternatively, it would be useful to consider in what way Ingo's scheduler needs to support plugins such as the CKRM and Vserver types of changes.

Best regards,
Marc

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
#9 lore raw

Hi Peter,

Quoted 2 lines

I'm hoping that the CKRM folks will send me a patch to add their scheduler to plugsched :-)

They are planning to release a patch against 2.6.10. But their patch wont stand alone against 2.6.10 and so it might be difficult for you to integrate their code into a scheduler for plugsched.

Also, the CKRM scheduler only modifies Ingo's O(1) scheduler. It certainly would be interesting to have CKRM variants of the other schedulers. This points to a whole new level of 'plugsched' in that general O(1) schedulers need to support fair share plugins.

Marc

#10 lore raw
Quoted 10 lines · Marc E. Fiuczynski

Hi Peter,

Quoted 2 lines

I'm hoping that the CKRM folks will send me a patch to add their scheduler to plugsched :-)

They are planning to release a patch against 2.6.10. But their patch wont stand alone against 2.6.10 and so it might be difficult for you to integrate their code into a scheduler for plugsched.

Thats true. The current CKRM CPU scheduler is not a standalone component...if it were made one, it would need a non-CKRM interface to define classes, set their shares etc.

However, we have not investigated the possibility of making our CPU scheduler a pluggable one that could be loaded into a kernel equipped with the plugsched patches AND the CKRM framework. This should be possible but not a high priority until there is more consensus for having CPU schedulers pluggable at all (we have more basic stuff to fix in our scheduler such as load balancing).

Of course, we're more than happpy to work with someone willing to chip in and make our scheduler pluggable.

-- Shailabh

Quoted 18 lines

Also, the CKRM scheduler only modifies Ingo's O(1) scheduler. It certainly would be interesting to have CKRM variants of the other schedulers. This points to a whole new level of 'plugsched' in that general O(1) schedulers need to support fair share plugins.

Marc

-------------------------------------------------------
This SF.Net email is sponsored by: IntelliVIEW -- Interactive Reporting Tool for open source databases. Create drag-&-drop reports. Save time by over 75%! Publish reports on the web. Export to DOC, XLS, RTF, etc. Download a FREE copy at http://www.intelliview.com/go/osdn_nl
_______________________________________________
ckrm-tech mailing list
https://lists.sourceforge.net/lists/listinfo/ckrm-tech