The periodicity of scheduling

Kuan Hsun Chen kuan-hsun.chen at
Mon Aug 8 13:20:26 UTC 2016

Hello Sebastian,

Sorry, I spent some time to make sure the behaviour in Litmus RT. (I assume
the Linux EDF scheduler you mentioned it provides by Litmus RT)

For EDF case, you can find the implementation in curr_job_completion() in
sched_gsn_edf.c, and job_completion() in sched_pfp.c for RMS case.
By tracing back to the common function prepare_for_next_period() in jobs.c,
we can notice that they also prepare a counter, i.e., job_no variable, to
record how many jobs should be ideally released (without overrun).

With sys_wait_for_job_release() in litmus.c, the task is only going to
sleep only when its # of released job is larger than job_no by triggering
complete_job()  (like the case in RTEMS in rtems_rate_monotonic_period()
deciding if the period is going to block).
That means, the postponed jobs should be released continuously until there
is no more postponed jobs, which also reaches my conclusion.


2016-08-01 15:58 GMT+02:00 Sebastian Huber <sebastian.huber at embedded->:

> Hello Kuan-Hsun,
> it would be interesting to know the behaviour of the Linux EDF scheduler
> in this case.
> On 01/08/16 15:49, Kuan Hsun Chen 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.
>> 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:
>>  1. 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.
>>  2. 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.
>> 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.
>> Please let me know if this feature is sound and essential. I can patch it.
>> 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 <mailto:kuan-hsun.chen at
>> >
>> _______________________________________________
>> users mailing list
>> users at
> --
> Sebastian Huber, embedded brains GmbH
> Address : Dornierstr. 4, D-82178 Puchheim, Germany
> Phone   : +49 89 189 47 41-16
> Fax     : +49 89 189 47 41-09
> E-Mail  : sebastian.huber at
> PGP     : Public key available on request.
> Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.

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

Phone:  *+49 231 755 6124 <%2B49%20231%20755%206124>*
Mail:   kuan-hsun.chen at <kuan-hsun.chen at>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the users mailing list