[PATCH] c-user: Update overrun handling related functions and structure
Kuan-Hsun Chen
c0066c at gmail.com
Thu Jan 26 13:48:33 UTC 2017
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/~nahum/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/sipb/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
More information about the devel
mailing list