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 <c00...@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).
> +@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},
> }
> +@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},
> +}
> +@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},
> +}
> +@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},
> +}
> +@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},
> }
> +@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},
> }
> +@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},
> }
> +@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},
> +}
> +@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
>
>
_______________________________________________
devel mailing list
devel@rtems.org
http://lists.rtems.org/mailman/listinfo/devel
