Re: [PATCH] c-user: Update overrun handling related functions and structure
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: > 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
[PATCH] c-user: Update overrun handling related functions and structure
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