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