The periodicity of scheduling

Thu Aug 4 17:18:18 UTC 2016

Hello Gedare,

Okay, I see.
I will check the convention and follow the aforementioned rules.

Best,
Kuan-Hsun

2016-08-04 19:02 GMT+02:00 Gedare Bloom <gedare at rtems.org>:

> On Thu, Aug 4, 2016 at 12:41 PM, Kuan Hsun Chen
> <kuan-hsun.chen at tu-dortmund.de> wrote:
> > Hello all,
> >
> > I just make a pull request including the enhancement and a heuristic
> > example.
> We don't use pull requests on github. Please submit patches to
> devel at rtems.org for review, or if you think this is a bugfix or major
> improvement please open a ticket on our Trac and attach the patch to
> the ticket.
>
> Be sure you have followed the guidelines in
> https://devel.rtems.org/wiki/Developer/Coding/Conventions
>
> > 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.
> >
> New test cases that are for the uniprocessor RTEMS usually go into the
> sptests directory. This might qualify as a new sprmsched01 or some
> such. Make sure you include the .doc and .scn files to provide
> adequate documentation of the example/test.
>
> > 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.
> >
> References are helpful.
>
> > 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
> >> Mail:   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
> > Mail:   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*
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/c808c32b/attachment-0002.html>