<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>