Hi everybody,
I'm spending some time implementing the POSIX real-time SCHED_SPORADIC
scheduling policy on top of the mainline Linux kernel, and here it is
the code in its very first version.
Please, notice that it's still in preliminary status, group interface is
only a stub, and it may suffer of some issues, especially on SMP
systems.
So, why am I "releasing" it? Because, before going on, I'm interested in
hearing what do you think of it, if it is useful or not, if you think it
could be designed and written somehow different, and so on.
Also, since group and SMP scheduling are not even mentioned in the POSIX
specification, I think some discussion about them is needed if you want
(me) to go ahead on this path.
Well, all this given, let me try to briefly summarize what
SCHED_SPORADIC scheduling is, what it does mean for tasks and groups and
why I think it could be useful.
* The Sporadic Server in real-time theory
I don't think this mail is the very right place where to go into
details describing real-time systems theory, so I'll keep it very
short.
Let me just say that the so called Sporadic Server (SS), which POSIX
SCHED_SPORADIC somehow mimics, is one of the preferred mechanisms to
serve aperiodic or sporadic tasks in a periodic task-based fixed
priority real-time system.
It has been proposed by Sprunt et al. in '89 [1] to achieve two main
goals:
- reduce to the minimum the interference with the fixed priority
periodic task scheduling analysis;
- get fast (and, obviously, guaranteed!) aperiodic/sporadic response
time, at least comparable with its competitor algorithms.
Its main competitors were/are the Polling Server (PS) and the Deferable
Server (DS) [2](*).
Again, I'm not going into details of any of them but, indeed, the DS is
not that far from what Linux now has for real-time task group
throttling.
As you can see below the rules the SS follows seems quite tricky, but
the benefit it introduces could make it worthwhile to give it a
chance! :-P
* The POSIX SCHED_SPORADIC policy
The best source of information about the POSIX real-time (optional)
scheduling policy called SCHED_SPORADIC is, I think, the Open Group
specification document itself [3]. Also, the QNX documentation [4],
since QNX supports SCHED_SPORADIC, is in my opinion very well written.
Anyway, here they are some extracts from the POSIX specs, just in the
case you want to look at the code but you have no time or will to go
through the links. :-)
"The policy is based primarily on the replenishment period
(sched_ss_repl_period) and the execution capacity
(sched_ss_init_budget)."
"The policy is identical to SCHED_FIFO with conditions that cause
priority to be switched between sched_priority and
sched_ss_low_priority."
"The priority of a thread is: if the execution capacity is greater than
zero and the number of pending replenishment is less than
sched_ss_max_repl, it is sched_priority; otherwise, priority shall be
sched_ss_low_priority."
"The modification of the available execution capacity and is done as
follows:
1. When a thread becomes running, its execution time shall be limited
to at most its execution capacity.
2. Each time the thread is inserted at the tail of the list associated
with sched_priority -because it became runnable or because of a
replenishment operation- the time is posted as the activation_time.
3. When the running thread with sched_priority becomes preempted, the
execution time consumed is subtracted from the execution capacity.
4. When the running thread with sched_priority becomes blocked, the
execution time consumed is subtracted from the execution capacity,
and a replenishment operation is scheduled.
5. When the running thread with sched_priority reaches its execution
time limit, it becomes the tail of the list for
sched_ss_low_priority. The execution time consumed is subtracted
and a replenishment operation is scheduled.
6. Each time a replenishment is scheduled, the replenish_amount is set
equal to the execution time consumed since the activation_time. The
replenishment is scheduled at activation_time plus
sched_ss_repl_period (immediately if this is in the past).
The number of replenishment simultaneously pending shall not be
greater than sched_ss_max_repl.
7. A replenishment consists of adding replenish_amount to the
execution capacity. If the thread was sched_ss_low_priority, then
it becomes sched_priority."
As you can see, the scheduling policy behave exactly the same as
SCHED_FIFO with respect to non RT tasks, but may affect which RT task
is going to be the running one, by continuously changing the priority
of SCHED_SPORADIC ones.
* POSIX SCHED_SPORADIC group scheduling
For groups, POSIX does not say anything about them (we know group
scheduling is out of the POSIX specs), but I think everyone can see
that a policy like this applied to task groups could realize something
similar to what you have and you call throttling.
In the code below I applied the rules of SCHED_SPORADIC also to task
groups (if configured!) with the following semantic:
a. a task group becomes blocked iff it contains no tasks or other
task groups to be scheduled in its runqueue;
b. a task group unblocks/wake up when a task and/or a task group is
queued to its runqueue;
A said before, you are presently throttling real-time task groups by
something very similar to the Deferrable Server.
The main concern against DS is schedulability. In fact, when you have a
fixed priority _periodic-task_ based real-time system, you have a
particular subset of task sets that are schedulable, and tests exists
to find out if a given task set is going to be schedulable (no deadline
miss!) or not.
Now, the problem is that, when you add a DS(-like mechanism) the subset
of task sets that are guaranteed to be schedulable, i.e., that are
going to pass the scheduling test, could be reduced.
If you prefer, we can reprhase this like that: the scheduling test
should be modified to reject more task sets than before, otherwise
schedulability without deadline misses is no longer guaranteed.
Conversely, while using SS, which is more or less what the code tries
to do, thanks to the complicated but effective replenishment rules, the
schedulable region does not decreases that much.
More precisely, each Sporadic Servers behaves, for scheduling test
purposes, just like it is another real-time periodic task, which is
definitely not true for different approaches!
Math could appear quite tricky, especially for non real-time
theorists (which I definitely am not!! :-D)... But let me know if you
want me to try to cut&paste them here...
* Why SCHED_SPORADIC in Linux
Well, I started implementing the POSIX SCHED_SPORADIC policy in the
Linux kernel first of all for fun, as well as to get in touch with
kernel programming, which is something that I always wanted to, and
also because this is part of my work as a PhD Student in real-time
systems... :-)
This given, I decided to let all of you aware about that because of the
following reasons:
- it seems to me that there is some interest in this scheduling policy,
at least from the academic and research community, e.g., our Lab
(ReTiS Lab, Scuola Superiore Sant'Anna, Pisa [5]) or the Florida
State University (FSU [6](**)).
Other implementation are also been attempted but, AFAIK, code is not
available or, if it is hanging around the Web, it is based on old
versions of Linux (or RTLinux!).
- it is a feature of the POSIX specifications that Linux is not
supporting yet!
Ok, it is optional, but I think it could be useful, especially
considering that there are very few other OSs supporting it, i.e.,
only QNX and RTEMS (and, but I'm not sure, OpenSolaris).
- the extension of the policy to group scheduling, which is in place in
the code, could be a valid alternative for throttling real-time task
groups, providing different guarantees. As said, throttling using SS
instead of DS (which is, I repeat, very similar to what you are doing
now), could result in comparable performances but with better
scheduling capabilities for the user, and this, I think, could be
appreciated by the real-time systems designers.
* Schedulability Test
A final note on the schedulability admission test.
I have not yet implemented it, since coding the exact formulas for a
fully-general hierarchical real-time system could be very complex and,
more important, time consuming when executing such a code path on-line.
So, I think that leaving this duty to the user could be a good choice,
at least for now.
This idea is also reinforced by thinking about the fact that the user,
being the designer of the application, know better than us what kind of
guarantee, so what kind of test, he needs, e.g, he knows if he is using
hierarchical scheduling or not, and so if he needs a full hierarchical
test or a much simpler one.
Moreover, I think the present implementation of group scheduling, where
groups have not "their own" priority but derive it by the tasks (and
the task groups) they contain, does not fully adhere to what we, in
real-time theory, call hierarchical scheduling (not in always at
least).
For this reason, I'm quite convinced that whatever (well known)
scheduling test we are implementing on top of such a design, it is not
going to work as we would have expected.
Obviously the present implementation has the benefit of being
transparent and behaving just like POSIX (FIFO, RR and, now,
SPORADIC!), excepted for throttling, so I'm not complaining about
that... Just noticing some differences.
Summarizing, if you we to use real-time scheduling test (better, if
we want to use one of the well known scheduling tests) I think we
have first of all to modify the group scheduling infrastructure (giving
a priority to each group could be sufficient), and then code a fully
hierarchical test... And I'm not doing any of those things, not for now
at least, in my RFC-patch. :-)
Ok, let's stop gossiping now... The code follows... It is worthless to
say that comments are not welcome... They are necessary and absolutely
needed!! :-D
Best Regards,
Dario
---
(*) There exists many other algorithms, e.g., Priority Exchange, Slack
Stealer, etc., but they are out of our scope for now.
(**) I found out that code only yesterday! :-(
Anyway, my patch has nothing to do with it, and the approach is
quite a lot different, one of the biggest difference being the FSU
code is not supporting group scheduling.
---
[1] B. Sprunt, L. Sha, and J. Lehoczky. Aperiodic Task Scheduling for
Hard Real-Time Systems. Journal of Real-Time Systems, 1:27–60, 1989
[2] J.P. Lehoczky, L. Sha, and J.K. Strosnider. Enhanced aperiodic
responsiveness in hard real-time environments. In Proceedings of
IEEE Real-Time Systems Symposium, pages 261–270, 1987
[3] The Open Group Base Specifications Issue 6
IEEE Std 1003.1, 2004 Edition
http://www.opengroup.org/onlinepubs/009695399/functions/xsh_chap02_08.html#tag_02_08_04_04
[4] The QNX Neutrino Microkernel
http://www.qnx.com/developers/docs/6.3.2/neutrino/sys_arch/kernel.html#Sporadic_scheduling
[5] ReTiS Lab, Scuola Superiore Sant'Anna, Pisa
http://retis.sssup.it/
[6] Florida State University
COP 5641 - Kernel and Device Driver Programming
http://ww2.cs.fsu.edu/~rosentha/cop5641/modifications.php
--
<<This happens because I choose it to happen!>>
(Raistlin Majere, DragonLance Chronicles -Dragons of Spring Drawning-)
----------------------------------------------------------------------
Dario Faggioli
GNU/Linux Registered User: #340657
Web: http://www.linux.it/~raistlin
Blog: http://blog.linux.it/raistlin
SIP Account: [email protected] or
[email protected]
Jabber Account: [email protected]/WengoPhone
GnuPG Key ID: 4DC83AC4
GnuPG Key Fingerprint: 2A78 AD5D B9CF A082 0836 08AD 9385 DA04 4DC8 3AC4
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Dario Faggioli wrote:
> I'm spending some time implementing the POSIX real-time SCHED_SPORADIC
> scheduling policy on top of the mainline Linux kernel, and here it is
> the code in its very first version.
I'm not commenting on the code or usefulness of ht features. I just
want to point out a problem.
The authors of that POSIX extension unfortunately decided to extend the
sched_param structure. If you look at the definition of that structure
Linux uses you'll see that there is no place for this. I.e., any
implementation of that feature following the POSIX spec to the letter
will introduce major headache in the form of binary incompatibility.
In case the features is useful enough (I actually always thought it
isn't an have actually proposed to remove it again from POSIX) then I
would rather prefer to not claim support for this feature in the POSIX
way. One could still implement it as described. But change the
interface to not require the sched_param change.
- --
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
iEYEARECAAYFAkigSHsACgkQ2ijCOnn/RHS23QCfWNJRqnrhgSXGpnNag/nVeKcC
uwIAn3fUIwku+i+xegBDhfh5yaIW/VCo
=LCa/
-----END PGP SIGNATURE-----
On Mon, 2008-08-11 at 07:11 -0700, Ulrich Drepper wrote:
> I'm not commenting on the code or usefulness of ht features. I just
> want to point out a problem.
Ok...
> The authors of that POSIX extension unfortunately decided to extend the
> sched_param structure. If you look at the definition of that structure
> Linux uses you'll see that there is no place for this. I.e., any
> implementation of that feature following the POSIX spec to the letter
> will introduce major headache in the form of binary incompatibility.
Yeah, I'm aware of that, as you can see in the comments inside the patch
(has the mail with the patch arrived? It seems no to me :-().
> In case the features is useful enough (I actually always thought it
> isn't an have actually proposed to remove it again from POSIX)
Uao... Thanks for your support! :-P
> then I
> would rather prefer to not claim support for this feature in the POSIX
> way. One could still implement it as described. But change the
> interface to not require the sched_param change.
It could be done like this, I agree, for sure.
I would be sorry if we implemented this but we still miss POSIX
support... But I can't imagine any other solution that is not going
cause ABI issues too.
Anyway, thanks a lot for replying.
Dario
--
<<This happens because I choose it to happen!>>
(Raistlin Majere, DragonLance Chronicles -Dragons of Spring Drawning-)
----------------------------------------------------------------------
Dario Faggioli
GNU/Linux Registered User: #340657
Web: http://www.linux.it/~raistlin
Blog: http://blog.linux.it/raistlin
SIP Account: [email protected] or
[email protected]
Jabber Account: [email protected]/WengoPhone
GnuPG Key ID: 4DC83AC4
GnuPG Key Fingerprint: 2A78 AD5D B9CF A082 0836 08AD 9385 DA04 4DC8 3AC4
On Mon, 2008-08-11 at 07:11 -0700, Ulrich Drepper wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Dario Faggioli wrote:
> > I'm spending some time implementing the POSIX real-time SCHED_SPORADIC
> > scheduling policy on top of the mainline Linux kernel, and here it is
> > the code in its very first version.
>
> I'm not commenting on the code or usefulness of ht features. I just
> want to point out a problem.
>
> The authors of that POSIX extension unfortunately decided to extend the
> sched_param structure. If you look at the definition of that structure
> Linux uses you'll see that there is no place for this. I.e., any
> implementation of that feature following the POSIX spec to the letter
> will introduce major headache in the form of binary incompatibility.
>
> In case the features is useful enough (I actually always thought it
> isn't an have actually proposed to remove it again from POSIX) then I
> would rather prefer to not claim support for this feature in the POSIX
> way. One could still implement it as described. But change the
> interface to not require the sched_param change.
Whichever way you turn SCHED_SPORADIC or SCHED_EDF etc.. you'll need
some place to pass along extra data. The single int in sched_param is
not enough for these policies.
My suggestion would be to create struct sched_param2 with plenty of
padding to support future expansion and add
sys_sched_setscheduler2()/sys_sched_getscheduler2() to deal with this
new structure.
I think at least 3 struct timespec fields and a flags field might be
needed for the most exotic deadline parameters:
- budget
- deadline
- period
My own take is that SCHED_SPORADIC is a nice excersice in scheduler
development - but I'm not sure its actually in demand from application
developers (those of you who actually write RT progs, please holler if
you care - I'm interested to hear your stories).
SCHED_EDF is in great demand - and is being worked on - albeit not as
much as I'd like to, due to me being too busy with other stuff atm :-/
On Mon, 2008-08-11 at 16:25 +0200, Peter Zijlstra wrote:
> My suggestion would be to create struct sched_param2 with plenty of
> padding to support future expansion and add
> sys_sched_setscheduler2()/sys_sched_getscheduler2() to deal with this
> new structure.
And we will miss POSIX compliance. :-(
Anyway, I agree the ABI issue this could raise are serious enough and, I
repeat, I can't see any other solution too.
So, whatever someone is interested in the code or not, I think I'll
rewrite the interface part of the patch coping with something like the
solution you are proposing... Thank you.
> I think at least 3 struct timespec fields and a flags field might be
> needed for the most exotic deadline parameters:
>
> - budget
> - deadline
> - period
>
Let's hope they're enough... You know, real-time people are... Well...
Quite unpredictable!! :-P
> My own take is that SCHED_SPORADIC is a nice excersice in scheduler
> development
Can't disagree on that, especially because this is exactly one of the
first reasons why I started writing it! :-D
> but I'm not sure its actually in demand from application
> developers
Indeed, I also think that the task scheduling policy could be tricky and
quite difficult to be used for applications, especially in general
purpose environments, where the use of RT priorities is uncommon and,
often, an exceptional event.
If, conversely, you have an embedded system with very few tasks and you
run them with RT prios, I think this could be profitably used.
Anyway, even if we came to the agreement that SCHED_SPORADIC task
scheduling is not that useful, or, if you want, it is a complete mess,
what do you think about group scheduling and throttling?
I think, as I write, that it could be nice to have the possibility to
"throttle" task groups according to something similar to a Sporadic
Server.
I re-red my first mail and I can understand it could be quite difficult
to figure out what the main differences are just reading my (poorly
written!) English sentences... So I think I'll try to come out with an
example (as soon as I can).
Also, if you know any existing application that is making use of the
throttling/group scheduling infrastructure, please, point them out to
me, and I'll give them a try with SCHED_SPORADIC group scheduling, and
try to compare their behavior with the present one.
> (those of you who actually write RT progs, please holler if
> you care - I'm interested to hear your stories).
Well, we will for sure (at least try to) use it for implementing a soft
and hard real-time library from a research project.
Maybe we will modify it a little bit more, but it will be the basis.
Furthermore, I remember that, when we met in Prague, T. Backer from FSU
seemed quite interested in SCHED_SPORADIC... Maybe we can ask him to
help us too... What do you think?
> SCHED_EDF is in great demand - and is being worked on - albeit not as
> much as I'd like to, due to me being too busy with other stuff atm :-/
Hey, we sent you our code, even if it is very, very preliminary state...
And you have not make us know what you do think about it! :-O
Anyway, we also are continuing working on it, even if being busy with a
lot of other things too, and we would be glad collaborate, it there is
room for. :-D
But this is another thread, and I don't want to mix things! :-)
Thanks for replying,
Dario
--
<<This happens because I choose it to happen!>>
(Raistlin Majere, DragonLance Chronicles -Dragons of Spring Drawning-)
----------------------------------------------------------------------
Dario Faggioli
GNU/Linux Registered User: #340657
Web: http://www.linux.it/~raistlin
Blog: http://blog.linux.it/raistlin
SIP Account: [email protected] or
[email protected]
Jabber Account: [email protected]/WengoPhone
GnuPG Key ID: 4DC83AC4
GnuPG Key Fingerprint: 2A78 AD5D B9CF A082 0836 08AD 9385 DA04 4DC8 3AC4
On Mon, 2008-08-11 at 18:23 +0200, Dario Faggioli wrote:
> On Mon, 2008-08-11 at 16:25 +0200, Peter Zijlstra wrote:
> > My suggestion would be to create struct sched_param2 with plenty of
> > padding to support future expansion and add
> > sys_sched_setscheduler2()/sys_sched_getscheduler2() to deal with this
> > new structure.
> And we will miss POSIX compliance. :-(
> Anyway, I agree the ABI issue this could raise are serious enough and, I
> repeat, I can't see any other solution too.
Well, a new version of glibc could use those to implement the posix
interface. Because as I understand it, glibc can break ABI on certain
version bumps.
On Mon, 2008-08-11 at 18:30 +0200, Peter Zijlstra wrote:
> On Mon, 2008-08-11 at 18:23 +0200, Dario Faggioli wrote:
> > On Mon, 2008-08-11 at 16:25 +0200, Peter Zijlstra wrote:
> > > My suggestion would be to create struct sched_param2 with plenty of
> > > padding to support future expansion and add
> > > sys_sched_setscheduler2()/sys_sched_getscheduler2() to deal with this
> > > new structure.
> > And we will miss POSIX compliance. :-(
> > Anyway, I agree the ABI issue this could raise are serious enough and, I
> > repeat, I can't see any other solution too.
>
> Well, a new version of glibc could use those to implement the posix
> interface.
I see. Actually, you're more than right! I have not thought at it in
those terms...
> Because as I understand it, glibc can break ABI on certain
> version bumps.
Seems better to me too... I confirm I'll do the interface change as soon
as possible.
Thanks again,
Dario
--
<<This happens because I choose it to happen!>>
(Raistlin Majere, DragonLance Chronicles -Dragons of Spring Drawning-)
----------------------------------------------------------------------
Dario Faggioli
GNU/Linux Registered User: #340657
Web: http://www.linux.it/~raistlin
Blog: http://blog.linux.it/raistlin
SIP Account: [email protected] or
[email protected]
Jabber Account: [email protected]/WengoPhone
GnuPG Key ID: 4DC83AC4
GnuPG Key Fingerprint: 2A78 AD5D B9CF A082 0836 08AD 9385 DA04 4DC8 3AC4
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Peter Zijlstra wrote:
> Well, a new version of glibc could use those to implement the posix
> interface. Because as I understand it, glibc can break ABI on certain
> version bumps.
In theory. But this hasn't happened so far and I don't expect it to
happen any time soon. New interfaces are not a real problem for me, though.
- --
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
iEYEARECAAYFAkigdB8ACgkQ2ijCOnn/RHSQSQCfaDp3XAM9vJXHBIqSM7PQq1n2
AwkAoMmMyglHDYe4aw2Yqa6jQgG/48er
=D9Eb
-----END PGP SIGNATURE-----
On Mon, 2008-08-11 at 10:17 -0700, Ulrich Drepper wrote:
> > Well, a new version of glibc could use those to implement the posix
> > interface. Because as I understand it, glibc can break ABI on certain
> > version bumps.
>
> In theory. But this hasn't happened so far and I don't expect it to
> happen any time soon. New interfaces are not a real problem for me, though.
>
Ok, we'll see.
I still think that SCHED_SPORADIC task (but specially group!) scheduling
could be useful, even with a non fully-POSIX interface.
This mail only to say that I'm actively working on it, i.e., I'm
rewriting it with the new sched_param2/sched_setscheduler2 interface and
fixing some very glaring bugs that was present in my first code. :-P
Unfortunately, I'll be off the PC till September 4th... If you are still
interested in, we will talk about it at that time, when I'll post the
new version of the RFC.
I also hope, by then, to be able to show you some test cases and
overhead estimation.
Thanks all of you for minding me, and sorry if I wasted some of your
time. :-)
Best Regards,
Dario
--
<<This happens because I choose it to happen!>>
(Raistlin Majere, DragonLance Chronicles -Dragons of Spring Drawning-)
----------------------------------------------------------------------
Dario Faggioli
GNU/Linux Registered User: #340657
Web: http://www.linux.it/~raistlin
Blog: http://blog.linux.it/raistlin
SIP Account: [email protected] or
[email protected]
Jabber Account: [email protected]/WengoPhone
GnuPG Key ID: 4DC83AC4
GnuPG Key Fingerprint: 2A78 AD5D B9CF A082 0836 08AD 9385 DA04 4DC8 3AC4