[PATCH] c-user: Update overrun handling related functions and structure

Kuan Hsun Chen c0066c at gmail.com
Thu Jan 26 13:53:19 UTC 2017


Some references for arbitrary deadline model are not included in C-user,
since there is no explicit concept about arbitrary and soft real-time yet.

2017-01-26 14:48 GMT+01:00 Kuan-Hsun Chen <c0066c at gmail.com>:

> State the limited count of postponed_jobs.
> Update _rtems_rate_monotonic_get_status() and related structure.
> Move "Further Reading" in c-user to references.
> Add mentioned papers in ticket #2795 to references.
>
> Update #2795.
> ---
>  c-user/rate_monotonic_manager.rst | 62 ++++++++++++++----------------
> -----
>  common/refs.bib                   | 68 ++++++++++++++++++++++++++++++
> ++++++++-
>  2 files changed, 92 insertions(+), 38 deletions(-)
>
> diff --git a/c-user/rate_monotonic_manager.rst
> b/c-user/rate_monotonic_manager.rst
> index de1de75..213dbca 100644
> --- a/c-user/rate_monotonic_manager.rst
> +++ b/c-user/rate_monotonic_manager.rst
> @@ -2,6 +2,7 @@
>
>  .. COMMENT: COPYRIGHT (c) 1988-2008.
>  .. COMMENT: On-Line Applications Research Corporation (OAR).
> +.. COMMENT: COPYRIGHT (c) 2017 Kuan-Hsun Chen.
>  .. COMMENT: All rights reserved.
>
>  Rate Monotonic Manager
> @@ -169,10 +170,12 @@ Rate Monotonic Scheduling Algorithm
>  .. index:: Rate Monotonic Scheduling Algorithm, definition
>  .. index:: RMS Algorithm, definition
>
> -The Rate Monotonic Scheduling Algorithm (RMS) is important to real-time
> systems
> -designers because it allows one to sufficiently guarantee that a set of
> tasks is
> -schedulable.  A set of tasks is said to be schedulable if all of the
> tasks can
> -meet their deadlines.  RMS provides a set of rules which can be used to
> perform
> +The Rate Monotonic Scheduling Algorithm (RMS) is important to real-time
> systems
> +designers because it allows one to sufficiently guarantee that a set of
> tasks
> +is schedulable (see :cite:`Liu:1973:Scheduling`,
> :cite:`Lehoczky:1989:RM`, :cite:`Lui:1990:Ada`, :cite:`Burns:1991:Review`).
> +
> +A set of tasks is said to be schedulable if all of the tasks can meet
> their
> +deadlines.  RMS provides a set of rules which can be used to perform
>  a guaranteed schedulability analysis for a task set.  This analysis
> determines
>  whether a task set is schedulable under worst-case conditions and
> emphasizes
>  the predictability of the system's behavior.  It has been proven that:
> @@ -283,6 +286,7 @@ As the number of tasks increases, the above formula
> approaches ln(2) for a
>  worst-case utilization factor of approximately 0.693.  Many tasks sets
> can be
>  scheduled with a greater utilization factor.  In fact, the average
> processor
>  utilization threshold for a randomly generated task set is approximately
> 0.88.
> +See more detail in :cite:`Liu:1973:Scheduling`.
>
>  Processor Utilization Rule Example
>  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> @@ -306,7 +310,7 @@ task:
>  The total processor utilization for this task set is 0.73 which is below
> the
>  upper bound of 3 * (2**(1/3) - 1), or 0.779, imposed by the Processor
>  Utilization Rule.  Therefore, this task set is guaranteed to be
> schedulable
> -using RMS.
> +using RMS.
>
>  First Deadline Rule
>  ^^^^^^^^^^^^^^^^^^^
> @@ -328,6 +332,7 @@ initialization task, all application tasks, regardless
> of priority, can be
>  created and started before the initialization deletes itself.  This
> technique
>  ensures that all tasks begin to compete for execution time at the same
> instant
>  - when the user initialization task deletes itself.
> +See more detail in :cite:`Lehoczky:1989:RM`.
>
>  First Deadline Rule Example
>  ^^^^^^^^^^^^^^^^^^^^^^^^^^^
> @@ -382,7 +387,7 @@ deadline.  As a result, of the first 200 time units,
> task 1 uses (2 * 25) = 50
>  and task 2 uses 50, leaving (200 - 100) time units for task 3.  Task 3
> requires
>  100 time units to execute, thus it will have completed execution at time
> 200.
>  Thus, all of the tasks have met their first deadlines at time 200, and
> the task
> -set is schedulable using the First Deadline Rule.
> +set is schedulable using the First Deadline Rule.
>
>  Relaxation of Assumptions
>  ^^^^^^^^^^^^^^^^^^^^^^^^^
> @@ -417,26 +422,6 @@ and its run-time behavior when performing
> schedulability analysis for a system
>  using RMS.  Every hardware and software factor which impacts the
> execution time
>  of each task must be accounted for in the schedulability analysis.
>
> -Further Reading
> -^^^^^^^^^^^^^^^
> -
> -For more information on Rate Monotonic Scheduling and its schedulability
> -analysis, the reader is referred to the following:
> -
> -- C. L. Liu and J. W. Layland. "Scheduling Algorithms for
> Multiprogramming in a
> -  Hard Real Time Environment." *Journal of the Association of Computing
> -  Machinery*. January 1973. pp. 46-61.
> -
> -- John Lehoczky, Lui Sha, and Ye Ding. "The Rate Monotonic Scheduling
> -  Algorithm: Exact Characterization and Average Case Behavior."  *IEEE
> -  Real-Time Systems Symposium*. 1989. pp. 166-171.
> -
> -- Lui Sha and John Goodenough. "Real-Time Scheduling theory and Ada."
> *IEEE
> -  Computer*. April 1990. pp. 53-62.
> -
> -- Alan Burns. "Scheduling hard real-time systems: a review."  *Software
> -  Engineering Journal*. May 1991. pp. 116-128.
> -
>  Operations
>  ==========
>
> @@ -471,7 +456,8 @@ monotonic period results in one of the following
> scenarios:
>    ``rtems_rate_monotonic_period`` directive, the postponed job will be
> released
>    until there is no more postponed jobs. The calling task returns
> immediately
>    with a timeout error status. In the watchdog routine, the period will
> still
> -  be updated periodically and track the number of the postponed periods.
> +  be updated periodically and track the count of the postponed jobs
> :cite:`Chen:2016:Overrun`.
> +  Please note, the count of the postponed jobs is only saturated until
> 0xffffffff.
>
>  Obtaining the Status of a Period
>  --------------------------------
> @@ -561,8 +547,8 @@ Subsequent invocations of the
> ``rtems_rate_monotonic_period`` directive will
>  result in the task blocking for the remainder of the 100 tick period.
> If, for
>  any reason, the body of the loop takes more than 100 ticks to execute, the
>  ``rtems_rate_monotonic_period`` directive will return the
> ``RTEMS_TIMEOUT``
> -status and the postponed job will be released.  If the above task misses
> -its deadline, it will delete the rate monotonic period and itself.
> +status. If the above task misses its deadline, it will delete the rate
> +monotonic period and itself.
>
>  Task with Multiple Periods
>  --------------------------
> @@ -630,8 +616,8 @@ will not block.
>
>  If, for any reason, the task misses any deadline, the
>  ``rtems_rate_monotonic_period`` directive will return the
> ``RTEMS_TIMEOUT``
> -directive status and the postponed job will be released. If the above
> task misses
> -its deadline, it will delete the rate monotonic periods and itself.
> +directive status. If the above task misses its deadline, it will delete
> the
> +rate monotonic periods and itself.
>
>  Directives
>  ==========
> @@ -841,9 +827,9 @@ DESCRIPTION:
>      remainder of the period before reinitiating the period with the
> specified
>      period.  If id was not running (either expired or never initiated),
> the
>      period is immediately initiated and the directive returns immediately.
> -       If id has expired its period, the postponed job will be released
> immediately
> -       and the following calls of this directive will release postponed
> -       jobs until there is no more deadline miss.
> +    If id has expired its period, the postponed job will be released
> immediately
> +    and the following calls of this directive will release postponed
> +    jobs until there is no more deadline miss.
>
>      If invoked with a period of ``RTEMS_PERIOD_STATUS`` ticks, the current
>      state of id will be returned.  The directive status indicates the
> current
> @@ -897,6 +883,7 @@ DIRECTIVE STATUS CODES:
>              rtems_rate_monotonic_period_states    state;
>              rtems_rate_monotonic_period_time_t    since_last_period;
>              rtems_thread_cpu_usage_t
> executed_since_last_period;
> +            uint32_t                              postponed_jobs_count;
>          }  rtems_rate_monotonic_period_status;
>
>      .. COMMENT: RATE_MONOTONIC_INACTIVE does not have RTEMS in front of
> it.
> @@ -907,11 +894,12 @@ DIRECTIVE STATUS CODES:
>      time values will be set to 0.  Otherwise, both time values will
> contain
>      time information since the last invocation of the
>      ``rtems_rate_monotonic_period`` directive.  More specifically, the
> -    ticks_since_last_period value contains the elapsed time which has
> occurred
> +    since_last_period value contains the elapsed time which has occurred
>      since the last invocation of the ``rtems_rate_monotonic_period``
> directive
> -    and the ``ticks_executed_since_last_period`` contains how much
> processor
> +    and the ``executed_since_last_period`` contains how much processor
>      time the owning task has consumed since the invocation of the
> -    ``rtems_rate_monotonic_period`` directive.
> +    ``rtems_rate_monotonic_period`` directive. In addition, the
> +    postponed_jobs_count value contains the count of jobs which are not
> released yet.
>
>  NOTES:
>      This directive will not cause the running task to be preempted.
> diff --git a/common/refs.bib b/common/refs.bib
> index 76fd116..62a4233 100644
> --- a/common/refs.bib
> +++ b/common/refs.bib
> @@ -1,5 +1,13 @@
>  % Use <AUTHOR>:<YEAR>:<TOPIC> for the reference labels.
>  % Sort lexicographically by (YEAR, AUTHOR, TOPIC).
> + at article{Liu:1973:Scheduling,
> +  author      = {Liu, C. L. and Layland, James W.},
> +  title       = {{Scheduling Algorithms for Multiprogramming in a
> Hard-Real-Time Environment}},
> +  journal     = {Journal of the ACM},
> +  volume      = {20},
> +  year        = {1973},
> +  pages       = {46-61},
> +}
>  @inproceedings{Varghese:1987:TimerWheel,
>    author      = {Varghese, G. and Lauck, T.},
>    title       = {{Hashed and Hierarchical Timing Wheels: Data Structures
> for the Efficient Implementation of a Timer Facility}},
> @@ -7,12 +15,42 @@
>    year        = {1987},
>    url         = {http://www.cs.columbia.edu/~n
> ahum/w6998/papers/sosp87-timing-wheels.pdf},
>  }
> + at inproceedings{Lehoczky:1989:RM,
> +  author      = {Lehoczky, J. and Sha, L. and Ding, Y.},
> +  booktitle   = {Real-Time Systems Symposium},
> +  title       = {{The rate monotonic scheduling algorithm: exact
> characterization and average case behavior}},
> +  year        = {1989},
> +  pages       = {166-171},
> +}
> + at inproceedings{Lehoczky:1990:Arbitrary,
> +  author      = {Lehoczky, J. P.},
> +  booktitle   = {11th Real-Time Systems Symposium},
> +  title       = {{Fixed priority scheduling of periodic task sets with
> arbitrary deadlines}},
> +  year        = {1990},
> +  pages       = {201-209},
> +}
> + at article{Lui:1990:Ada,
> +  author      = {Sha, Lui and Goodenough, J. B.},
> +  journal     = {Computer},
> +  title       = {{Real-time scheduling theory and Ada}},
> +  year        = {1990},
> +  volume      = {23},
> +  pages       = {53-62},
> +}
> + at ARTICLE{Burns:1991:Review,
> +  author      = {Burns, A.},
> +  journal     = {Software Engineering Journal},
> +  title       = {{Scheduling hard real-time systems: a review}},
> +  year        = {1991},
> +  volume      = {6},
> +  pages       = {116-128},
> +}
>  @techreport{Varghese:1995:BSDCallout,
>    author      = {Varghese, G. and Costello, A.},
>    title       = {{Redesigning the BSD callout and timer facilities}},
>    institution = {Washington University in St. Louis},
>    note        = {WUCS-95-23},
> -  year        = {1987},
> +  year        = {1995},
>    month       = {November},
>    url         = {http://web.mit.edu/afs.new/si
> pb/user/daveg/ATHENA/Info/wucs-95-23.ps},
>  }
> @@ -52,6 +90,12 @@
>    publisher   = {Lockheed Martin Corporation},
>    url         = {http://www.stroustrup.com/JSF-AV-rules.pdf},
>  }
> + at book{Buttazzo:2005:SRS,
> +  author      = {Buttazzo, Giorgio and Lipari, Giuseppe and Abeni, Luca
> and Caccamo, Marco},
> +  title       = {{Soft Real-Time Systems: Predictability vs. Efficiency
> (Series in Computer Science)}},
> +  year        = {2005},
> +  publisher   = {Plenum Publishing Co.},
> +}
>  @inproceedings{Gleixner:2006:Hrtimers,
>    author      = {Gleixner, Thomas and Niehaus, Douglas},
>    title       = {{Hrtimers and Beyond: Transforming the Linux Time
> Subsystems}},
> @@ -168,8 +212,30 @@
>    pages       = {179-195},
>    year        = {2015},
>  }
> + at inproceedings{Huang:2015:RTB,
> +  author      = {Huang, Wen-Hung and Chen, Jian-Jia},
> +  title       = {Response Time Bounds for Sporadic Arbitrary-deadline
> Tasks Under Global Fixed-priority Scheduling on Multiprocessors},
> +  booktitle   = {ACM Proceedings of the 23rd International Conference on
> Real Time and Networks Systems},
> +  year        = {2015},
> +  pages       = {215-224},
> +}
>  @book{CERT:2016:CCS,
>    title       = {{SEI CERT C Coding Standard}},
>    year        = {2016},
>    publisher   = {Carnegie Mellon University},
>  }
> + at INPROCEEDINGS{vonderBr:2016:DynRT,
> +  author      = {von der Br\"uggen, Georg and Chen, Kuan-Hsun and Huang,
> Wen-Hung and Chen, Jian-Jia},
> +  booktitle   = {IEEE Real-Time Systems Symposium (RTSS)},
> +  title       = {{Systems with Dynamic Real-Time Guarantees in Uncertain
> and Faulty Execution Environments}},
> +  year        = {2016},
> +  pages       = {303-314},
> +}
> + at inproceedings{Chen:2016:Overrun,
> +  author      = {Chen, Kuan-Hsun and von der Br\"uggen, Georg and Chen,
> Jian-Jia},
> +  title       = {{Overrun Handling for Mixed-Criticality Support in
> RTEMS}},
> +  booktitle   = {Mixed Criticality Systems - WMC 2016},
> +  pages       = {13-14},
> +  year        = {2016},
> +}
> +
> --
> 1.9.1
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/devel/attachments/20170126/5ec81b6b/attachment-0002.html>


More information about the devel mailing list