The periodicity of scheduling

Thu Aug 4 17:02:43 UTC 2016

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