The periodicity of scheduling

Thu Aug 4 16:41:25 UTC 2016

Hello all,

I just make a pull request including the enhancement and a heuristic
example.
I believe this patch is good for further use in more general real-time task
models.
To demonstrate the differences, a heuristic example called deadlinemiss is
prepared in testsuites/samples/ to show the benefit of the enhancement.
This enhancement only affect those timeout cases without changing any
behaviour in normal cases.

However as Joel said, so far there is no standard requirements for how to
deal with missed periods.
Maybe RMS manger can have more flexibility to decide the way it reacts.
I can show some academic papers as the reference if it is necessary.

Cheers,
Kuan-Hsun

2016-08-02 10:45 GMT+02:00 Kuan Hsun Chen <kuan-hsun.chen at tu-dortmund.de>:

> 2016-08-01 19:11 GMT+02:00 Joel Sherrill <joel at rtems.org>:
>
>> On Aug 1, 2016 1:04 PM, "Gedare Bloom" <gedare at rtems.org> wrote:
>> >
>> > On Mon, Aug 1, 2016 at 9:49 AM, Kuan Hsun Chen
>> > <kuan-hsun.chen at tu-dortmund.de> wrote:
>> > > Hello All,
>> > >
>> > > I have used rate_monotonic function series to do some cycle-accuracy
>> > > emulation quite a long time. I believe that some missing features of
>> > > scheduling are essentially required. As I'm not aware of any
>> discussion
>> > > about this before, please correct me if I misunderstand.
>> > >
>> > > If I understand correctly, the current implementation of
>> > > rtems_rate_monotonic_period() is explicitly assumed the implicit
>> deadline or
>> > > constraint deadline model that the task deadline is always less than
>> or
>> > > equal to the period deadline. If rtems_rate_monotonic_period() is
>> called, it
>> > > is the moment that either the task is finished on time or earlier
>> than its
>> > > period (or inactivate as the first call). If a task misses its
>> period, the
>> > > watchdog will mark the period as RATE_MONOTONIC_EXPIRED and update the
>> > > deadline of watchdog.
>> > >
>> > Yes I think you understand correctly. Except, I don't think the
>> > deadline of the watchdog is updated by the watchdog.
>>
>> +1
>>
> Aha yes, the deadline of watchdog is updated by
> _Rate_monotonic_Release_job() instead of itself.
>
>> > > However, the behavior is not correct currently. From my point of
>> view, the
>> > > periodic task should always release its workload on time, even it
>> misses its
>> > > deadline. If there are already two expired periods, the task should
>> have two
>> > > more remaining instances workload to execute.
>> > > Especially if the task has arbitrary deadline or even the task is a
>> soft
>> > > real time task, this feature should behave correctly.
>> > > (Soft Real Time task: If a task misses its deadline, it is still
>> valuable to
>> > > gather its result no matter when. If the utilization of uniprocessor
>> is not
>> > > 100%, the tardiness is proved to be bounded.)
>> > >
>> > > Here I aim at a case that the task misses its deadline with the
>> current
>> > > implementation.
>> > > If a task period is time out (marked as RATE_MONOTONIC_EXPIRED), by
>> > > referring to _Rate_monotonic_Block_while_expired(), the next call of
>> > > rtems_rate_monotonic_period() will only release one following
>> instance and
>> > > manipulate the task period with the calling moment + the next length
>> of
>> > > period. However, this way of scheduling is in fact changing the
>> behaviour of
>> > > a periodic task:
>> > >
>> > > There may be more than one instances which are postponed due to the
>> > > preemption of higher priority tasks. Trivially release only one
>> instance is
>> > > not correct in the sense of scheduling.
>> >
>> > I understand that counting the number of missed deadlines could be
>> > correct for certain applications. The way to handle missed deadlines
>> > should be a parameter of the RM manager though, since handling missed
>> > deadlines is application specific property of how "soft" the deadlines
>> > are.
>>
>> There are no standard requirements for how to deal with missed periods.
>> The current implementation does precisely what is required for RMS per the
>> original paper and nothing more.
>>
>> We can discuss what to do on missed periods but having academic papers to
>> back that up would be ideal.
>>
> I can find some collections which are more related to this requirement.
> (Also my emulation I did for.)
>
>> > > The period of expired task is shifted and unpredictable. This should
>> be
>> > > calculated correctly and rapidly by taking the time point of first
>> period
>> > > released. The deadline of watchdog in this case should be assigned
>> with an
>> > > absolute tick.
>> > >
>> > Yes. I would deal with this by having the watchdog timeout reprogram
>> > itself with the next period immediately when it expires in
>> > _Rate_monotonic_Timeout, along with incrementing the RM_Control
>> > counter for currently missed deadlines/pending jobs. This way another
>> > expiration indicates another deadline miss, or so the task finishes
>> > its current job it can immediately start the next job with the correct
>> > deadline already programmed in the watchdog.
>>
> This is a great way. I deal with this by RM manager side.
> I should do this inside the watchdog for more precise control.
>
>> >
>> > > I have enhanced this feature in the system by adding three additional
>> > > counters in Rate_monotonic_Control structure and one more function to
>> do the
>> > > correct assignment of deadline and job release. I also prepare a
>> heuristic
>> > > example to demonstrate the results. I'm going to fix the case for
>> arbitrary
>> > > deadline later on.
>> > >
>> > By arbitrary deadline you mean explicit deadlines? I don't think this
>> > is a common requirement, but it would be a welcome addition if the
>> > complexity is not that great and the common case (implicit deadline)
>> > is negligibly affected.
>>
> The arbitrary deadline model is that the task relative deadline could be
> larger than its period as shown in [1-2] for example.
> In this model, a task may have multiple ready jobs. A common assumption is
> that those jobs are scheduled on a First-Come-First Serve basis.
> Therefore, the period is no longer "timeout". The deadline can only be
> expired by the task it belongs to.
>
> I'm not sure how the others use RTEMS, but I make the application itself
> detect deadline misses with absolute tick instead of watching the status of
> period.
> In some common cases, the task deadline is no more than its period
> so-called constraint deadline model.
> Deadline monotonic is optimal in this model, which is similar to RMS.
>
> I think implicit deadline case can always keep as it is, if we do it
> carefully.
> As Gedare said, it might be a good way to prepare a option there in RM
> manager.
> I believe having an enhanced scheduler is great to the community of RTEMS
> anyway.
> So I will do this right now and evaluate the overhead from my side.
>
> [1] Andersson etal., Scheduling Arbitrary-Deadline Sporadic Task Systems
> on Multiprocessors, RTSS'08
> [2] Huang etal., Response time bounds for sporadic arbitrary-deadline
> tasks under global fixed-priority scheduling on multiprocessors. RTNS'15
>
>> >
>> > > Please let me know if this feature is sound and essential. I can
>> patch it.
>> > >
>> > The feature seems useful for some applications, but may be not all of
>> > them will want to have this behavior for a missed deadline.
>> >
>>
> > > Best Regards,
>> > > Kuan-Hsun
>> > >
>> > > --
>> > > M.Sc. Kuan-Hsun Chen
>> > >
>> > > TU Dortmund
>> > > Department of Computer Science 12
>> > > Design Automation of Embedded Systems
>> > > Otto-Hahn-Strasse 16, Room 102
>> > >
>> > > 44227 Dortmund
>> > > Germany
>> > >
>> > > Phone:  +49 231 755 6124
>> > > Mail:   kuan-hsun.chen at tu-dortmund.de
>> > >
>> > > _______________________________________________
>> > > users mailing list
>> > > users at rtems.org
>> > > http://lists.rtems.org/mailman/listinfo/users
>> > _______________________________________________
>> > users mailing list
>> > users at rtems.org
>> > http://lists.rtems.org/mailman/listinfo/users
>>
>
>
>
> --
> M.Sc. Kuan-Hsun Chen
>
> TU Dortmund
> Department of Computer Science 12
> Design Automation of Embedded Systems
> Otto-Hahn-Strasse 16, Room 102
>
> 44227 Dortmund
> Germany
>
> Phone:  *+49 231 755 6124 <%2B49%20231%20755%206124>*
> Mail:   kuan-hsun.chen at tu-dortmund.de <kuan-hsun.chen at tu-dortmund.de>
>

-- 
M.Sc. Kuan-Hsun Chen

TU Dortmund
Department of Computer Science 12
Design Automation of Embedded Systems
Otto-Hahn-Strasse 16, Room 102

44227 Dortmund
Germany

Phone:  *+49 231 755 6124 <%2B49%20231%20755%206124>*
Mail:   kuan-hsun.chen at tu-dortmund.de <kuan-hsun.chen at tu-dortmund.de>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/users/attachments/20160804/18168a4f/attachment-0002.html>