Skip to contentSkip to conversation

POSIX SCHED_SPORADIC implementation for tasks and groups

RFC PATCH In review Dario Faggioli 3 participants 9 messages Aug 11, 2008 – Aug 17, 2008

lore
Share & tools
lore
#0 lore raw

cover POSIX SCHED_SPORADIC implementation for tasks and groups

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

Signature · 12 lines
<<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
#1 lore raw

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quoted 3 lines · Dario Faggioli

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-----

#2 lore raw
Quoted 2 lines · Ulrich Drepper

I'm not commenting on the code or usefulness of ht features. I just want to point out a problem.

Ok...

Quoted 5 lines

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 :-().

Quoted 2 lines

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

Quoted 4 lines

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

Signature · 12 lines
<<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
#3 lore raw
In reply to Ulrich Drepper
Quoted 17 lines · Ulrich Drepper

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quoted 3 lines · Dario Faggioli

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.

Quoted 5 lines

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 :-/

#4 lore raw
Quoted 4 lines · Peter Zijlstra

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.

Quoted 7 lines

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

Quoted 2 lines

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

Quoted 2 lines

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.

Quoted 2 lines

(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?

Quoted 2 lines

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

Signature · 12 lines
<<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
#5 lore raw
Quoted 8 lines · Dario Faggioli
Quoted 4 lines · Peter Zijlstra

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.

#6 lore raw
Quoted 6 lines · Peter Zijlstra
Quoted 5 lines · Dario Faggioli
Quoted 4 lines · Peter Zijlstra

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.

Quoted 6 lines
Quoted 3 lines

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...

Quoted 2 lines

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

Signature · 12 lines
<<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
#7 lore raw
In reply to Peter Zijlstra

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quoted 3 lines · Peter Zijlstra

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-----

#8 lore raw
Quoted 7 lines · Ulrich Drepper
Quoted 3 lines

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

Signature · 12 lines
<<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