Hi
I am currently pondering about ways to implement time partitioning in an L4 context, i.e. the idea is to distribute processing time to subsystems (consisting of groups of tasks/threads) according to predefined rules. Ideally, the underlying subsystems should be unaware of this process. Also, ideally, the concept should be recursive (i.e. a subsystem task should be able to donate (some of) its processing time to other sub-subsytems).
At first glance, the concept of external preempters, as specified (though AFAIK never implemented) in L4 looks like it could be a useable basis for this, however:
- I'm still having difficulties to fully understand preempters in L4. Their specification in the reference manual is somewhat sketchy.
- I have a few ideas of my own, but implementing them would require extensions to some L4 functions. My past experience with the L4 reference manual has been that everything in there is there for a good reason, but the reasoning is not always explained (which is probably the way a "reference manual" should be).
I would very much appreciate if someone could point me to a document that explains the reasoning behind preempters, as defined in L4.
Failing that, are there any publications on external schedulers in the context of microkernels that might be helpful to read, any discussion forums you might suggest?
.. or am I really on uncharted ground here?
Any response would be greatly appreciated
Rob
---------------------------------------------------------------- Robert Kaiser email: rkaiser@sysgo.de SYSGO AG Am Pfaffenstein 14 phone: (49) 6136 9948-762 D-55270 Klein-Winternheim / Germany fax: (49) 6136 9948-10
rkaiser@sysgo.de wrote:
Hi Robert,
. or am I really on uncharted ground here?
No not completely, if you can live with hierarchical proportional share scheduling, see
Checkout Ford et al. "CPU inheritance scheduling", OSDI 96 http://www.cs.utah.edu/flux/papers/index.html
and for a look at L4 in particular
http://www.cse.unsw.edu.au/~disy/papers/index.html#ug-theses
Simon Winwood Flexible scheduling mechanisms in L4, BE Thesis, SCS&E, UNSW, November 2000.
Have a look at Dresden as well for a more real-time slant on scheduling in L4. I believe they use multi-level round robin and a variation on priority inheritance (helping). I can't convey the exact details of priority assignment etc, so your better off having a look yourself.
I believe Jochen envisaged something "better" than proportional share, but still keeping the flexibility, decomposability, and preserving performance. However, this never got beyond being a vision except for the existence of preempters (time slice + total quanta ideas) in V4, which is unfinished work.
- Kevin
Hi Kevin,
Am Freitag, 24. Januar 2003 00:52 schrieb Kevin Elphinstone:
Checkout Ford et al. "CPU inheritance scheduling", OSDI 96 http://www.cs.utah.edu/flux/papers/index.html
and for a look at L4 in particular
http://www.cse.unsw.edu.au/~disy/papers/index.html#ug-theses
Simon Winwood Flexible scheduling mechanisms in L4, BE Thesis, SCS&E, UNSW, November 2000.
Thanks a lot for these links. At first glance, the Ford paper seems to describe pretty much what I had in mind (but I have to study it further).
Have a look at Dresden as well for a more real-time slant on scheduling in L4. I believe they use multi-level round robin and a variation on priority inheritance (helping).
Interesting! Our P4 kernel implements this too :-).
I can't convey the exact details of priority assignment etc, so your better off having a look yourself.
I haven't found any publications along these lines yet. Is anyone from Dresden listening ?
I believe Jochen envisaged something "better" than proportional share, but still keeping the flexibility, decomposability, and preserving performance. However, this never got beyond being a vision except for the existence of preempters (time slice + total quanta ideas) in V4, which is unfinished work.
Well, maybe it's time to push this work a little further ? I would be interested.
Rob
---------------------------------------------------------------- Robert Kaiser email: rkaiser@sysgo.de SYSGO AG Am Pfaffenstein 14 phone: (49) 6136 9948-762 D-55270 Klein-Winternheim / Germany fax: (49) 6136 9948-10
l4-hackers@os.inf.tu-dresden.de