[RTEMS Project] #2795: Overrun Handling for general real-time models

[RTEMS trac]

#2795: Overrun Handling for general real-time models
-------------------------+---------------------
 Reporter:  khchen       |      Owner:
     Type:  enhancement  |     Status:  new
 Priority:  high         |  Milestone:  4.11.1
Component:  cpukit       |    Version:  4.11
 Severity:  critical     |   Keywords:  overrun
-------------------------+---------------------
 In the current implementation, if a task period is time out, the next call
 of rtems_rate_monotonic_period() will only release one following job and
 manipulate the task period with the calling moment + the next length of
 period. With the assumption that implicit/constraint deadline and hard
 real-time model, the above mechanism is okay.

 However, it may not be applicable for general task models, e.g., soft
 real-time task, arbitrary deadline, mixed-criticality system [1-4]. It is
 usually assumed that multiple task jobs of a task are executed in a first-
 come-first-serve manner. Thus, it is sufficient to release the second task
 job at the moment the first task job finishes according to a strictly
 periodic release pattern. The current design in fact shifts the release
 pattern of periodic/sporadic tasks. Since there maybe more than one
 postponed jobs due to the preemption, these postponed jobs that should be
 released are never released to the system.

 Although there is no standard requirement in reality for deadline misses,
 with this enhancement, the postponed jobs will be released with the
 correct number without periodic release shifting. This way of handling is
 already widely considered in academia from 90s [2] until now [3] or even
 on multicores as well [4].

 I refine the following four files and handle this requirement
 individually. The overhead seems to me negligible.
 cpukit/rtems/include/rtems/rtems/ratemon.h
 cpukit/rtems/include/rtems/rtems/ratemonimpl.h
 cpukit/rtems/src/ratemontimeout.c
 cpukit/rtems/src/ratemonperiod.c
 I have tested the enhancement on Qemu and Raspberry Pi Model B+ with
 corresponding BSPs.

 I believe this patch as a basis is required for further use for more
 general real-time task models.
 This enhancement only affect those timeout cases without changing any
 behaviour in normal cases.
 This enhancement is accepted in workshop mixed-criticality (WMC 2016)
 along with RTSS'16 this year [5].

 To demonstrate the differences, a heuristic example is prepared in
 testsuites/sptests/sprmsched01 to show the benefit of the enhancement:
 Given two tasks with implicit deadline that task deadline is equal to its
 period.
 Task 1 period is 10000 ticks, whereas task 2 is 2000 ticks.
 Task 1 has the execution time 6000 ticks, and task 2 has 1000 ticks.
 Assume Task 1 has a higher priority than task 2. Task 1 only executes 2
 times.
 In the expected result, we can observe that the postponed jobs are
 continuously released till there is no postponed job left, and the task
 period will still keep as it is.
 (Job 3-7 in task 2 are postponed jobs)

 [1] Buttazzo et al., Soft Real-Time Systems: Predictability vs.
 Efficiency, Springer 2005, ​http://www.springer.com/gp/book/9780387237015
 [2] Lehoczky et al., Fixed priority scheduling of periodic task sets with
 arbitrary deadlines, RTSS 1990,
 ​http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=128748
 [3] Georg von der Brüggen et al., Systems with Dynamic Real-Time
 Guarantees in Uncertain and Faulty Execution Environments, RTSS'16,
 accepted.
 [4] Huang et al., Response time bounds for sporadic arbitrary-deadline
 tasks under global fixed-priority scheduling on multiprocessors, RTNS
 2015, ​http://dl.acm.org/citation.cfm?doid=2597457.2597459
 [5] Chen et al., Overrun Handling for Mixed-Criticality Support in RTEMS,
 WMC 2016, accepted.

--
Ticket URL: <http://devel.rtems.org/ticket/2795>
RTEMS Project <http://www.rtems.org/>
RTEMS Project