Re: behavior of hrtimers scheduled to expire in the past, SCHED_SPORADIC subtlety

Re: behavior of hrtimers scheduled to expire in the past, SCHED_SPORADIC subtlety

[Daniel Rosenthal]

On Tue, Oct 21, 2008 at 4:09 AM, Thomas Gleixner <tglx@linutronix.de> wrote:
> On Mon, 20 Oct 2008, Daniel Rosenthal wrote:
>> What is the intended behavior for an hrtimer that is scheduled to
>> expire in the past?  I assumed that it would simply be scheduled to
>> expire at the nearest available time in the future, but I wrote some
>> scheduler code and it looks like hrtimers don't go off at all if they
>> are not scheduled to go off at a time which is after rq->clock.  Is
>> this the intended behavior or is this a bug?
>
> That depends on the callback mode of the hrtimer. The standard ones
> are scheduled to the softirq when they are already expired, but those
> which are not allowed to run their callback in softirq context are
> _not_ enqueued and the caller has to check, whether the timer is
> active/enqueued after starting it.

Ok, thanks for the heads up.  Is this documented somewhere, or do I
need to submit a patch?


Darrio,
Just to warn you, be careful that your SCHED_SPORADIC implementation
deals with the above situation correctly.  There are situations in
which the actual scheduling of a replenishment can unintentionally be
deferred for an excessive period of time (i.e. a SCHED_SPORADIC task
running at its high priority gets preempted for a relatively long
time, or at least a time which is long compared to the task's period).
 In this case, you may accidentally end up scheduling a replenishment
timer with an expiration time in the past (because (activation_time +
period) < rq->clock ).  Be careful to avoid this in your code because
this is subtle and it took me a very long time to debug this (this was
compounded by the fact that I made an incorrect assumption about
hrtimers, discussed above).  It can be solved by executing such past
replenishments immediately, rather than submitting them to
hrtimer_start().

And regarding SCHED_SPORADIC, I am also working on SCHED_SPORADIC in
2.6.25. If I don't finish my RFC patch by the time you finish your
final 2.6.27 patch, please let me know because I believe it would be
beneficial for us to compare code before any final decisions are made
(mine still isn't working well enough to compare yet).

Daniel

Re: behavior of hrtimers scheduled to expire in the past, SCHED_SPORADIC subtlety

[Dario Faggioli]

[-- Attachment #1: Type: text/plain, Size: 2716 bytes --]

On Wed, 2008-10-22 at 21:05 -0400, Daniel Rosenthal wrote:
> Darrio,
> Just to warn you, be careful that your SCHED_SPORADIC implementation
> deals with the above situation correctly.  
I know this is an issue, but anyway thank you very much for adding me to
this Cc. :-)

> Be careful to avoid this in your code because
> this is subtle and it took me a very long time to debug this
I know that feeling quite well!! :-P

> And regarding SCHED_SPORADIC, I am also working on SCHED_SPORADIC in
> 2.6.25. If I don't finish my RFC patch by the time you finish your
> final 2.6.27 patch, please let me know because I believe it would be
> beneficial for us to compare code before any final decisions are made
> (mine still isn't working well enough to compare yet).
Ok, this is how things are right now. Anyway, any comparison, discussion
and collaboration are more than welcome. :-D

I've almost rewritten almost all the code in order to fulfill Peter's
suggestions and to deal with some situations I did not consider in the
first implementation.

First of all I've changed the interface from standard POSIX calls
(sched_setscheduler, etc.) to the new API (sched_setscheduler2, etc.) as
suggested in the LKML.
After that I discovered that dealing with poor precision in budget
accounting (tick resolution) causes very big issues, especially if
budget and period are very short, and I had to rethink the algorithm and
the code again to cope with this (and no, hrtick does not help, not so
much at least!). :-(

All this took very long time, much more than what I expected, but now
it's ready... I'm just testing it with some corner cases I have been
able to figure out and, more interestingly, I'm trying to establish a
meaningful comparison between the present throttling mechanism and the
SCHED_SPORADIC group scheduling.

In a short while (I hope) I'll send the patch again to you as well as to
the ML, so that we can discuss about it being more informed. :-)

Also, I'm going to present this work at the next RealTime Linux
Workshop, next week, in Mexico... Are you attending?

Thanks again and 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: dario.faggioli@sipproxy.wengo.fr or
             raistlin@ekiga.net
Jabber Account: dario.faggioli@jabber.org/WengoPhone
GnuPG Key ID: 4DC83AC4
GnuPG Key Fingerprint: 2A78 AD5D B9CF A082 0836 08AD 9385 DA04 4DC8 3AC4

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: behavior of hrtimers scheduled to expire in the past, SCHED_SPORADIC subtlety

[Daniel Rosenthal]

On Thu, Oct 23, 2008 at 4:10 AM, Dario Faggioli <raistlin@linux.it> wrote:
> First of all I've changed the interface from standard POSIX calls
> (sched_setscheduler, etc.) to the new API (sched_setscheduler2, etc.) as
> suggested in the LKML.

I was thinking about this, and I'm not convinced that this is actually
a good idea. It seems the only POSIX call that arguably needs a dual
is sched_getparam(). Every other function (sched_setscheduler() and
sched_setparam()) should be able to determine from the policy the
appropriate structure to copy from user space. For example, if the
policy is SCHED_SPORADIC, the function knows it needs to copy a new
sched_param structure from user space, including
sched_ss_low_priority, etc., and otherwise it just copies an old
sched_param_legacy structure containing the single field struct
sched_priority. Considerable padding can also be added (making the
final structure 512 bytes or so) to sched_param for future
compatability so this change (hopefully) never has to be made again.

Of course, this would probably require re-coding
do_sched_setscheduler(), and I know this would break the convention of
Linux system call implementations where the user arguments are copied
from user space before any arguments are actually examined, but I
think it is worth it to minimize incompatibility with POSIX, since
after all the whole point of POSIX is to make programs portable and
not implementation specific. I understand such portability is at
conflict with the interest of backwards binary compatibility, but any
POSIX non-conformance should be minimized. In this particular case I
don't see why this can't be done by only adding sched_getparam2() (and
slightly modifying sched_getparam()) and not changing anything else.


> After that I discovered that dealing with poor precision in budget
> accounting (tick resolution) causes very big issues, especially if
> budget and period are very short, and I had to rethink the algorithm and
> the code again to cope with this (and no, hrtick does not help, not so
> much at least!). :-(

Are you talking about a situation in which the platform cannot provide
high-resolution ticks, or do you mean something else?


> All this took very long time, much more than what I expected, but now
> it's ready... I'm just testing it with some corner cases I have been
> able to figure out and, more interestingly, I'm trying to establish a
> meaningful comparison between the present throttling mechanism and the
> SCHED_SPORADIC group scheduling.

This is definitely an interesting issue. In the future it might be
better to model the entire rt-throttling mechanism as a periodic
server, and model group scheduling in the same way. This has been
proposed before by multiple people in real-time systems, including Rob
Davis and Alan Burns.


> In a short while (I hope) I'll send the patch again to you as well as to
> the ML, so that we can discuss about it being more informed. :-)

Thanks. This is very much appreciated :-).


> Also, I'm going to present this work at the next RealTime Linux
> Workshop, next week, in Mexico... Are you attending?

Unfortunately not. Good luck on your presentation though :-).


Daniel


-----------------------------------------------
Daniel Rosenthal
Florida State University
http://ww2.cs.fsu.edu/~rosentha/

Sporadic Server stuff:
http://ww2.cs.fsu.edu/~rosentha/cop5641/
http://ww2.cs.fsu.edu/~rosentha/cop5641/modifications.php