source: rtems/doc/user/rtmon.t @ 99c3730c

4.104.114.84.9
Last change on this file since 99c3730c was af61bca7, checked in by Joel Sherrill <joel.sherrill@…>, on Mar 2, 2007 at 9:30:22 PM

2007-03-02 Joel Sherrill <joel@…>

PR 1221/doc

  • user/rtmon.t: Add missing exponent operator in RMS CPU Utiliziation formula.
  • Property mode set to 100644
File size: 39.2 KB
Line 
1@c
2@c  COPYRIGHT (c) 1988-2002.
3@c  On-Line Applications Research Corporation (OAR).
4@c  All rights reserved.
5@c
6@c  $Id$
7@c
8
9@c
10@c  Open Issues
11@c    - nicen up the tables
12@c    - use math mode to print formulas
13@c
14
15@chapter Rate Monotonic Manager
16
17@cindex rate mononitonic tasks
18@cindex periodic tasks
19
20@section Introduction
21
22The rate monotonic manager provides facilities to
23implement tasks which execute in a periodic fashion.  The
24directives provided by the rate monotonic manager are:
25
26@itemize @bullet
27@item @code{@value{DIRPREFIX}rate_monotonic_create} - Create a rate monotonic period
28@item @code{@value{DIRPREFIX}rate_monotonic_ident} - Get ID of a period
29@item @code{@value{DIRPREFIX}rate_monotonic_cancel} - Cancel a period
30@item @code{@value{DIRPREFIX}rate_monotonic_delete} - Delete a rate monotonic period
31@item @code{@value{DIRPREFIX}rate_monotonic_period} - Conclude current/Start next period
32@item @code{@value{DIRPREFIX}rate_monotonic_get_status} - Obtain status information on period
33@end itemize
34
35@section Background
36
37The rate monotonic manager provides facilities to
38manage the execution of periodic tasks.  This manager was
39designed to support application designers who utilize the Rate
40Monotonic Scheduling Algorithm (RMS) to ensure that their
41periodic tasks will meet their deadlines, even under transient
42overload conditions.  Although designed for hard real-time
43systems, the services provided by the rate monotonic manager may
44be used by any application which requires periodic tasks.
45
46@subsection Rate Monotonic Manager Required Support
47
48A clock tick is required to support the functionality provided by this manager.
49
50@subsection Rate Monotonic Manager Definitions
51
52@cindex periodic task, definition
53
54A periodic task is one which must be executed at a
55regular interval.  The interval between successive iterations of
56the task is referred to as its period.  Periodic tasks can be
57characterized by the length of their period and execution time.
58The period and execution time of a task can be used to determine
59the processor utilization for that task.  Processor utilization
60is the percentage of processor time used and can be calculated
61on a per-task or system-wide basis.  Typically, the task's
62worst-case execution time will be less than its period.  For
63example, a periodic task's requirements may state that it should
64execute for 10 milliseconds every 100 milliseconds.  Although
65the execution time may be the average, worst, or best case, the
66worst-case execution time is more appropriate for use when
67analyzing system behavior under transient overload conditions.
68
69@cindex aperiodic task, definition
70
71In contrast, an aperiodic task executes at irregular
72intervals and has only a soft deadline.  In other words, the
73deadlines for aperiodic tasks are not rigid, but adequate
74response times are desirable.  For example, an aperiodic task
75may process user input from a terminal.
76
77@cindex sporadic task, definition
78
79Finally, a sporadic task is an aperiodic task with a
80hard deadline and minimum interarrival time.  The minimum
81interarrival time is the minimum period of time which exists
82between successive iterations of the task.  For example, a
83sporadic task could be used to process the pressing of a fire
84button on a joystick.  The mechanical action of the fire button
85ensures a minimum time period between successive activations,
86but the missile must be launched by a hard deadline.
87
88@subsection Rate Monotonic Scheduling Algorithm
89
90@cindex Rate Monotonic Scheduling Algorithm, definition
91@cindex RMS Algorithm, definition
92
93The Rate Monotonic Scheduling Algorithm (RMS) is
94important to real-time systems designers because it allows one
95to guarantee that a set of tasks is schedulable.  A set of tasks
96is said to be schedulable if all of the tasks can meet their
97deadlines.  RMS provides a set of rules which can be used to
98perform a guaranteed schedulability analysis for a task set.
99This analysis determines whether a task set is schedulable under
100worst-case conditions and emphasizes the predictability of the
101system's behavior.  It has been proven that:
102
103@itemize @code{ }
104@b{RMS is an optimal static priority algorithm for
105scheduling independent, preemptible, periodic tasks
106on a single processor.}
107@end itemize
108
109RMS is optimal in the sense that if a set of tasks
110can be scheduled by any static priority algorithm, then RMS will
111be able to schedule that task set.  RMS bases it schedulability
112analysis on the processor utilization level below which all
113deadlines can be met.
114
115RMS calls for the static assignment of task
116priorities based upon their period.  The shorter a task's
117period, the higher its priority.  For example, a task with a 1
118millisecond period has higher priority than a task with a 100
119millisecond period.  If two tasks have the same period, then RMS
120does not distinguish between the tasks.  However, RTEMS
121specifies that when given tasks of equal priority, the task
122which has been ready longest will execute first.  RMS's priority
123assignment scheme does not provide one with exact numeric values
124for task priorities.  For example, consider the following task
125set and priority assignments:
126
127@ifset use-ascii
128@example
129@group
130+--------------------+---------------------+---------------------+
131|        Task        |       Period        |      Priority       |
132|                    |  (in milliseconds)  |                     |
133+--------------------+---------------------+---------------------+
134|         1          |         100         |         Low         |
135+--------------------+---------------------+---------------------+
136|         2          |          50         |       Medium        |
137+--------------------+---------------------+---------------------+
138|         3          |          50         |       Medium        |
139+--------------------+---------------------+---------------------+
140|         4          |          25         |        High         |
141+--------------------+---------------------+---------------------+
142@end group
143@end example
144@end ifset
145
146@ifset use-tex
147@sp 1
148@tex
149\centerline{\vbox{\offinterlineskip\halign{
150\vrule\strut#&
151\hbox to 0.75in{\enskip\hfil#\hfil}&
152\vrule#&
153\hbox to 1.25in{\enskip\hfil#\hfil}&
154\vrule#&
155\hbox to 1.25in{\enskip\hfil#\hfil}&
156\vrule#\cr\noalign{\hrule}
157&\bf Task&& \bf Period && \bf Priority &\cr
158& && \bf (in milliseconds) && &\cr\noalign{\hrule}
159& 1 && 100 && Low &\cr\noalign{\hrule}
160& 2 && 50 && Medium &\cr\noalign{\hrule}
161& 3 && 50 && Medium &\cr\noalign{\hrule}
162& 4 && 25 && High &\cr\noalign{\hrule}
163}}\hfil}
164@end tex
165@end ifset
166
167@ifset use-html
168@html
169<CENTER>
170  <TABLE COLS=3 WIDTH="80%" BORDER=2>
171<TR><TD ALIGN=center><STRONG>Task</STRONG></TD>
172    <TD ALIGN=center><STRONG>Period (in milliseconds)</STRONG></TD>
173    <TD ALIGN=center><STRONG>Priority</STRONG></TD></TR>
174<TR><TD ALIGN=center>1</TD>
175    <TD ALIGN=center>100 </TD>
176    <TD ALIGN=center>Low</TD></TR>
177<TR><TD ALIGN=center>2</TD>
178    <TD ALIGN=center>50 </TD>
179    <TD ALIGN=center>Medium</TD></TR>
180<TR><TD ALIGN=center>3</TD>
181    <TD ALIGN=center>50 </TD>
182    <TD ALIGN=center>Medium</TD></TR>
183<TR><TD ALIGN=center>4</TD>
184    <TD ALIGN=center>25 </TD>
185    <TD ALIGN=center>High</TD></TR>
186  </TABLE>
187</CENTER>
188@end html
189@end ifset
190
191RMS only calls for task 1 to have the lowest
192priority, task 4 to have the highest priority, and tasks 2 and 3
193to have an equal priority between that of tasks 1 and 4.  The
194actual RTEMS priorities assigned to the tasks must only adhere
195to those guidelines.
196
197Many applications have tasks with both hard and soft
198deadlines.  The tasks with hard deadlines are typically referred
199to as the critical task set, with the soft deadline tasks being
200the non-critical task set.  The critical task set can be
201scheduled using RMS, with the non-critical tasks not executing
202under transient overload, by simply assigning priorities such
203that the lowest priority critical task (i.e. longest period) has
204a higher priority than the highest priority non-critical task.
205Although RMS may be used to assign priorities to the
206non-critical tasks, it is not necessary.  In this instance,
207schedulability is only guaranteed for the critical task set.
208
209@subsection Schedulability Analysis
210
211@cindex RMS schedulability analysis
212
213RMS allows application designers to ensure that tasks
214can meet all deadlines, even under transient overload, without
215knowing exactly when any given task will execute by applying
216proven schedulability analysis rules.
217
218@subsubsection Assumptions
219
220The schedulability analysis rules for RMS were
221developed based on the following assumptions:
222
223
224@itemize @bullet
225@item The requests for all tasks for which hard deadlines
226exist are periodic, with a constant interval between requests.
227
228@item Each task must complete before the next request for it
229occurs.
230
231@item The tasks are independent in that a task does not depend
232on the initiation or completion of requests for other tasks.
233
234@item The execution time for each task without preemption or
235interruption is constant and does not vary.
236
237@item Any non-periodic tasks in the system are special.  These
238tasks displace periodic tasks while executing and do not have
239hard, critical deadlines.
240@end itemize
241
242Once the basic schedulability analysis is understood,
243some of the above assumptions can be relaxed and the
244side-effects accounted for.
245
246@subsubsection Processor Utilization Rule
247
248@cindex RMS Processor Utilization Rule
249
250The Processor Utilization Rule requires that
251processor utilization be calculated based upon the period and
252execution time of each task.  The fraction of processor time
253spent executing task index is Time(index) / Period(index).  The
254processor utilization can be calculated as follows:
255
256@example
257@group
258Utilization = 0
259
260for index = 1 to maximum_tasks
261  Utilization = Utilization + (Time(index)/Period(index))
262@end group
263@end example
264
265To ensure schedulability even under transient
266overload, the processor utilization must adhere to the following
267rule:
268
269@example
270Utilization = maximum_tasks * (2**(1/maximum_tasks) - 1)
271@end example
272
273As the number of tasks increases, the above formula
274approaches ln(2) for a worst-case utilization factor of
275approximately 0.693.  Many tasks sets can be scheduled with a
276greater utilization factor.  In fact, the average processor
277utilization threshold for a randomly generated task set is
278approximately 0.88.
279
280@subsubsection Processor Utilization Rule Example
281
282This example illustrates the application of the
283Processor Utilization Rule to an application with three critical
284periodic tasks.  The following table details the RMS priority,
285period, execution time, and processor utilization for each task:
286
287@ifset use-ascii
288@example
289@group
290    +------------+----------+--------+-----------+-------------+
291    |    Task    |   RMS    | Period | Execution |  Processor  |
292    |            | Priority |        |   Time    | Utilization |
293    +------------+----------+--------+-----------+-------------+
294    |     1      |   High   |  100   |    15     |    0.15     |
295    +------------+----------+--------+-----------+-------------+
296    |     2      |  Medium  |  200   |    50     |    0.25     |
297    +------------+----------+--------+-----------+-------------+
298    |     3      |   Low    |  300   |   100     |    0.33     |
299    +------------+----------+--------+-----------+-------------+
300@end group
301@end example
302@end ifset
303
304@ifset use-tex
305@sp 1
306@tex
307\centerline{\vbox{\offinterlineskip\halign{
308\vrule\strut#&
309\hbox to 0.75in{\enskip\hfil#\hfil}&
310\vrule#&
311\hbox to 0.75in{\enskip\hfil#\hfil}&
312\vrule#&
313\hbox to 0.75in{\enskip\hfil#\hfil}&
314\vrule#&
315\hbox to 1.00in{\enskip\hfil#\hfil}&
316\vrule#&
317\hbox to 1.00in{\enskip\hfil#\hfil}&
318\vrule#\cr\noalign{\hrule}
319&\bf Task&& \bf RMS && \bf Period && \bf Execution &&\bf Processor&\cr
320& && \bf Priority && &&\bf Time &&\bf Utilization &\cr\noalign{\hrule}
321& 1 && High && 100 && 15 && 0.15 &\cr\noalign{\hrule}
322& 2 && Medium && 200 && 50 && 0.25 &\cr\noalign{\hrule}
323& 3 && Low && 300 && 100 && 0.33 &\cr\noalign{\hrule}
324}}\hfil}
325@end tex
326@end ifset
327 
328@ifset use-html
329@html
330<CENTER>
331  <TABLE COLS=5 WIDTH="80%" BORDER=2>
332<TR><TD ALIGN=center><STRONG>Task</STRONG></TD>
333    <TD ALIGN=center><STRONG>RMS Priority</STRONG></TD>
334    <TD ALIGN=center><STRONG>Period</STRONG></TD>
335    <TD ALIGN=center><STRONG>Execution Time</STRONG></TD>
336    <TD ALIGN=center><STRONG>Processor Utilization</STRONG></TD></TR>
337<TR><TD ALIGN=center>1</TD>
338    <TD ALIGN=center>High</TD>
339    <TD ALIGN=center>100</TD>
340    <TD ALIGN=center>15</TD>
341    <TD ALIGN=center>0.15</TD></TR>
342<TR><TD ALIGN=center>2</TD>
343    <TD ALIGN=center>Medium</TD>
344    <TD ALIGN=center>200</TD>
345    <TD ALIGN=center>50</TD>
346    <TD ALIGN=center>0.25</TD></TR>
347<TR><TD ALIGN=center>3</TD>
348    <TD ALIGN=center>Low</TD>
349    <TD ALIGN=center>300</TD>
350    <TD ALIGN=center>100</TD>
351    <TD ALIGN=center>0.33</TD></TR>
352  </TABLE>
353</CENTER>
354@end html
355@end ifset
356
357The total processor utilization for this task set is
3580.73 which is below the upper bound of 3 * (2**(1/3) - 1), or
3590.779, imposed by the Processor Utilization Rule.  Therefore,
360this task set is guaranteed to be schedulable using RMS.
361
362@subsubsection First Deadline Rule
363
364@cindex RMS First Deadline Rule
365
366If a given set of tasks do exceed the processor
367utilization upper limit imposed by the Processor Utilization
368Rule, they can still be guaranteed to meet all their deadlines
369by application of the First Deadline Rule.  This rule can be
370stated as follows:
371
372For a given set of independent periodic tasks, if
373each task meets its first deadline when all tasks are started at
374the same time, then the deadlines will always be met for any
375combination of start times.
376
377A key point with this rule is that ALL periodic tasks
378are assumed to start at the exact same instant in time.
379Although this assumption may seem to be invalid,  RTEMS makes it
380quite easy to ensure.  By having a non-preemptible user
381initialization task, all application tasks, regardless of
382priority, can be created and started before the initialization
383deletes itself.  This technique ensures that all tasks begin to
384compete for execution time at the same instant -- when the user
385initialization task deletes itself.
386
387@subsubsection First Deadline Rule Example
388
389The First Deadline Rule can ensure schedulability
390even when the Processor Utilization Rule fails.  The example
391below is a modification of the Processor Utilization Rule
392example where task execution time has been increased from 15 to
39325 units.  The following table details the RMS priority, period,
394execution time, and processor utilization for each task:
395
396@ifset use-ascii
397@example
398@group
399    +------------+----------+--------+-----------+-------------+
400    |    Task    |   RMS    | Period | Execution |  Processor  |
401    |            | Priority |        |   Time    | Utilization |
402    +------------+----------+--------+-----------+-------------+
403    |     1      |   High   |  100   |    25     |    0.25     |
404    +------------+----------+--------+-----------+-------------+
405    |     2      |  Medium  |  200   |    50     |    0.25     |
406    +------------+----------+--------+-----------+-------------+
407    |     3      |   Low    |  300   |   100     |    0.33     |
408    +------------+----------+--------+-----------+-------------+
409@end group
410@end example
411@end ifset
412
413@ifset use-tex
414@sp 1
415@tex
416\centerline{\vbox{\offinterlineskip\halign{
417\vrule\strut#&
418\hbox to 0.75in{\enskip\hfil#\hfil}&
419\vrule#&
420\hbox to 0.75in{\enskip\hfil#\hfil}&
421\vrule#&
422\hbox to 0.75in{\enskip\hfil#\hfil}&
423\vrule#&
424\hbox to 1.00in{\enskip\hfil#\hfil}&
425\vrule#&
426\hbox to 1.00in{\enskip\hfil#\hfil}&
427\vrule#\cr\noalign{\hrule}
428&\bf Task&& \bf RMS && \bf Period && \bf Execution &&\bf Processor&\cr
429& && \bf Priority && &&\bf Time &&\bf Utilization &\cr\noalign{\hrule}
430& 1 && High && 100 && 25 && 0.25 &\cr\noalign{\hrule}
431& 2 && Medium && 200 && 50 && 0.25 &\cr\noalign{\hrule}
432& 3 && Low && 300 && 100 && 0.33 &\cr\noalign{\hrule}
433}}\hfil}
434@end tex
435@end ifset
436 
437@ifset use-html
438@html
439<CENTER>
440  <TABLE COLS=5 WIDTH="80%" BORDER=2>
441<TR><TD ALIGN=center><STRONG>Task</STRONG></TD>
442    <TD ALIGN=center><STRONG>RMS Priority</STRONG></TD>
443    <TD ALIGN=center><STRONG>Period</STRONG></TD>
444    <TD ALIGN=center><STRONG>Execution Time</STRONG></TD>
445    <TD ALIGN=center><STRONG>Processor Utilization</STRONG></TD></TR>
446<TR><TD ALIGN=center>1</TD>
447    <TD ALIGN=center>High</TD>
448    <TD ALIGN=center>100</TD>
449    <TD ALIGN=center>25</TD>
450    <TD ALIGN=center>0.25</TD></TR>
451<TR><TD ALIGN=center>2</TD>
452    <TD ALIGN=center>Medium</TD>
453    <TD ALIGN=center>200</TD>
454    <TD ALIGN=center>50</TD>
455    <TD ALIGN=center>0.25</TD></TR>
456<TR><TD ALIGN=center>3</TD>
457    <TD ALIGN=center>Low</TD>
458    <TD ALIGN=center>300</TD>
459    <TD ALIGN=center>100</TD>
460    <TD ALIGN=center>0.33</TD></TR>
461  </TABLE>
462</CENTER>
463@end html
464@end ifset
465
466The total processor utilization for the modified task
467set is 0.83 which is above the upper bound of 3 * (2**(1/3) - 1),
468or 0.779, imposed by the Processor Utilization Rule.  Therefore,
469this task set is not guaranteed to be schedulable using RMS.
470However, the First Deadline Rule can guarantee the
471schedulability of this task set.  This rule calls for one to
472examine each occurrence of deadline until either all tasks have
473met their deadline or one task failed to meet its first
474deadline.  The following table details the time of each deadline
475occurrence, the maximum number of times each task may have run,
476the total execution time, and whether all the deadlines have
477been met.
478
479@ifset use-ascii
480@example
481@group
482+----------+------+------+------+----------------------+---------------+
483| Deadline | Task | Task | Task |        Total         | All Deadlines |
484|   Time   |  1   |  2   |  3   |    Execution Time    |     Met?      |
485+----------+------+------+------+----------------------+---------------+
486|   100    |  1   |  1   |  1   |  25 + 50 + 100 = 175 |      NO       |
487+----------+------+------+------+----------------------+---------------+
488|   200    |  2   |  1   |  1   |  50 + 50 + 100 = 200 |     YES       |
489+----------+------+------+------+----------------------+---------------+
490@end group
491@end example
492@end ifset
493
494@ifset use-tex
495@sp 1
496@tex
497\centerline{\vbox{\offinterlineskip\halign{
498\vrule\strut#&
499\hbox to 0.75in{\enskip\hfil#\hfil}&
500\vrule#&
501\hbox to 0.75in{\enskip\hfil#\hfil}&
502\vrule#&
503\hbox to 0.75in{\enskip\hfil#\hfil}&
504\vrule#&
505\hbox to 0.75in{\enskip\hfil#\hfil}&
506\vrule#&
507\hbox to 2.00in{\enskip\hfil#\hfil}&
508\vrule#&
509\hbox to 1.00in{\enskip\hfil#\hfil}&
510\vrule#\cr\noalign{\hrule}
511&\bf Deadline&& \bf Task &&\bf Task&&\bf Task&&\bf Total          &&\bf All Deadlines &\cr
512&\bf Time    && \bf 1    &&\bf 2   &&\bf 3   &&\bf Execution Time &&\bf Net?&\cr\noalign{\hrule}
513& 100&& 1 && 1 && 1 && 25 + 50 + 100 = 175 && NO &\cr\noalign{\hrule}
514& 200&& 2 && 1 && 1 && 50 + 50 + 100 = 200 && YES &\cr\noalign{\hrule}
515}}\hfil}
516@end tex
517@end ifset
518 
519@ifset use-html
520@html
521<CENTER>
522  <TABLE COLS=6 WIDTH="80%" BORDER=2>
523<TR><TD ALIGN=center><STRONG>Deadline Time</STRONG></TD>
524    <TD ALIGN=center><STRONG>Task 1</STRONG></TD>
525    <TD ALIGN=center><STRONG>Task 2</STRONG></TD>
526    <TD ALIGN=center><STRONG>Task 3</STRONG></TD>
527    <TD ALIGN=center><STRONG>Total Execution Time</STRONG></TD>
528    <TD ALIGN=center><STRONG>All Deadlines Met?</STRONG></TD></TR>
529<TR><TD ALIGN=center>100</TD>
530    <TD ALIGN=center>1</TD>
531    <TD ALIGN=center>1</TD>
532    <TD ALIGN=center>1</TD>
533    <TD ALIGN=center>25 + 50 + 100 = 175</TD>
534    <TD ALIGN=center>NO</TD></TR>
535<TR><TD ALIGN=center>200</TD>
536    <TD ALIGN=center>2</TD>
537    <TD ALIGN=center>1</TD>
538    <TD ALIGN=center>1</TD>
539    <TD ALIGN=center>50 + 50 + 100 = 175</TD>
540    <TD ALIGN=center>YES</TD></TR>
541  </TABLE>
542</CENTER>
543@end html
544@end ifset
545
546The key to this analysis is to recognize when each
547task will execute.  For example at time 100, task 1 must have
548met its first deadline, but tasks 2 and 3 may also have begun
549execution.  In this example, at time 100 tasks 1 and 2 have
550completed execution and thus have met their first deadline.
551Tasks 1 and 2 have used (25 + 50) = 75 time units, leaving (100
552- 75) = 25 time units for task 3 to begin.  Because task 3 takes
553100 ticks to execute, it will not have completed execution at
554time 100.  Thus at time 100, all of the tasks except task 3 have
555met their first deadline.
556
557At time 200, task 1 must have met its second deadline
558and task 2 its first deadline.  As a result, of the first 200
559time units, task 1 uses (2 * 25) = 50 and task 2 uses 50,
560leaving (200 - 100) time units for task 3.  Task 3 requires 100
561time units to execute, thus it will have completed execution at
562time 200.  Thus, all of the tasks have met their first deadlines
563at time 200, and the task set is schedulable using the First
564Deadline Rule.
565
566@subsubsection Relaxation of Assumptions
567
568The assumptions used to develop the RMS
569schedulability rules are uncommon in most real-time systems.
570For example, it was assumed that tasks have constant unvarying
571execution time.  It is possible to relax this assumption, simply
572by using the worst-case execution time of each task.
573
574Another assumption is that the tasks are independent.
575This means that the tasks do not wait for one another or
576contend for resources.  This assumption can be relaxed by
577accounting for the amount of time a task spends waiting to
578acquire resources.  Similarly, each task's execution time must
579account for any I/O performed and any RTEMS directive calls.
580
581In addition, the assumptions did not account for the
582time spent executing interrupt service routines.  This can be
583accounted for by including all the processor utilization by
584interrupt service routines in the utilization calculation.
585Similarly, one should also account for the impact of delays in
586accessing local memory caused by direct memory access and other
587processors accessing local dual-ported memory.
588
589The assumption that nonperiodic tasks are used only
590for initialization or failure-recovery can be relaxed by placing
591all periodic tasks in the critical task set.  This task set can
592be scheduled and analyzed using RMS.  All nonperiodic tasks are
593placed in the non-critical task set.  Although the critical task
594set can be guaranteed to execute even under transient overload,
595the non-critical task set is not guaranteed to execute.
596
597In conclusion, the application designer must be fully
598cognizant of the system and its run-time behavior when
599performing schedulability analysis for a system using RMS.
600Every hardware and software factor which impacts the execution
601time of each task must be accounted for in the schedulability
602analysis.
603
604@subsubsection Further Reading
605
606For more information on Rate Monotonic Scheduling and
607its schedulability analysis, the reader is referred to the
608following:
609
610@itemize @code{ }
611@item @cite{C. L. Liu and J. W. Layland. "Scheduling Algorithms for
612Multiprogramming in a Hard Real Time Environment." @b{Journal of
613the Association of Computing Machinery}. January 1973. pp. 46-61.}
614
615@item @cite{John Lehoczky, Lui Sha, and Ye Ding. "The Rate Monotonic
616Scheduling Algorithm: Exact Characterization and Average Case
617Behavior."  @b{IEEE Real-Time Systems Symposium}. 1989. pp. 166-171.}
618
619@item @cite{Lui Sha and John Goodenough. "Real-Time Scheduling
620Theory and Ada."  @b{IEEE Computer}. April 1990. pp. 53-62.}
621
622@item @cite{Alan Burns. "Scheduling hard real-time systems: a
623review."  @b{Software Engineering Journal}. May 1991. pp. 116-128.}
624@end itemize
625
626@section Operations
627
628@subsection Creating a Rate Monotonic Period
629
630The @code{@value{DIRPREFIX}rate_monotonic_create} directive creates a rate
631monotonic period which is to be used by the calling task to
632delineate a period.  RTEMS allocates a Period Control Block
633(PCB) from the PCB free list.  This data structure is used by
634RTEMS to manage the newly created rate monotonic period.  RTEMS
635returns a unique period ID to the application which is used by
636other rate monotonic manager directives to access this rate
637monotonic period.
638
639@subsection Manipulating a Period
640
641The @code{@value{DIRPREFIX}rate_monotonic_period} directive is used to
642establish and maintain periodic execution utilizing a previously
643created rate monotonic period.   Once initiated by the
644@code{@value{DIRPREFIX}rate_monotonic_period} directive, the period is
645said to run until it either expires or is reinitiated.  The state of the rate
646monotonic period results in one of the following scenarios:
647
648@itemize @bullet
649@item If the rate monotonic period is running, the calling
650task will be blocked for the remainder of the outstanding period
651and, upon completion of that period, the period will be
652reinitiated with the specified period.
653
654@item If the rate monotonic period is not currently running
655and has not expired, it is initiated with a length of period
656ticks and the calling task returns immediately.
657
658@item If the rate monotonic period has expired before the task
659invokes the @code{@value{DIRPREFIX}rate_monotonic_period} directive,
660the period will be initiated with a length of period ticks and the calling task
661returns immediately with a timeout error status.
662
663@end itemize
664
665@subsection Obtaining the Status of a Period
666
667If the @code{@value{DIRPREFIX}rate_monotonic_period} directive is invoked
668with a period of @code{@value{RPREFIX}PERIOD_STATUS} ticks, the current
669state of the specified rate monotonic period will be returned.  The following
670table details the relationship between the period's status and
671the directive status code returned by the
672@code{@value{DIRPREFIX}rate_monotonic_period}
673directive:
674
675@itemize @bullet
676@item @code{@value{RPREFIX}SUCCESSFUL} - period is running
677
678@item @code{@value{RPREFIX}TIMEOUT} - period has expired
679
680@item @code{@value{RPREFIX}NOT_DEFINED} - period has never been initiated
681@end itemize
682
683Obtaining the status of a rate monotonic period does
684not alter the state or length of that period.
685
686@subsection Canceling a Period
687
688The @code{@value{DIRPREFIX}rate_monotonic_cancel} directive is used to stop
689the period maintained by the specified rate monotonic period.
690The period is stopped and the rate monotonic period can be
691reinitiated using the @code{@value{DIRPREFIX}rate_monotonic_period} directive.
692
693@subsection Deleting a Rate Monotonic Period
694
695The @code{@value{DIRPREFIX}rate_monotonic_delete} directive is used to delete
696a rate monotonic period.  If the period is running and has not
697expired, the period is automatically canceled.  The rate
698monotonic period's control block is returned to the PCB free
699list when it is deleted.  A rate monotonic period can be deleted
700by a task other than the task which created the period.
701
702@subsection Examples
703
704The following sections illustrate common uses of rate
705monotonic periods to construct periodic tasks.
706
707@subsection Simple Periodic Task
708
709This example consists of a single periodic task
710which, after initialization, executes every 100 clock ticks.
711
712@page
713@example
714rtems_task Periodic_task(rtems_task_argument arg)
715@{
716  rtems_name        name;
717  rtems_id          period;
718  rtems_status_code status;
719
720  name = rtems_build_name( 'P', 'E', 'R', 'D' );
721
722  status = rtems_rate_monotonic_create( name, &period );
723  if ( status != RTEMS_STATUS_SUCCESSFUL ) @{
724    printf( "rtems_monotonic_create failed with status of %d.\n", rc );
725    exit( 1 );
726  @}
727
728
729  while ( 1 ) @{
730    if ( rtems_rate_monotonic_period( period, 100 ) == RTEMS_TIMEOUT )
731      break;
732
733    /* Perform some periodic actions */
734  @}
735
736  /* missed period so delete period and SELF */
737
738  status = rtems_rate_monotonic_delete( period );
739  if ( status != RTEMS_STATUS_SUCCESSFUL ) @{
740    printf( "rtems_rate_monotonic_delete failed with status of %d.\n", status );
741    exit( 1 );
742  @}
743
744  status = rtems_task_delete( SELF );    /* should not return */
745  printf( "rtems_task_delete returned with status of %d.\n", status );
746  exit( 1 );
747@}
748@end example
749
750
751The above task creates a rate monotonic period as
752part of its initialization.  The first time the loop is
753executed, the @code{@value{DIRPREFIX}rate_monotonic_period}
754directive will initiate the period for 100 ticks and return
755immediately.  Subsequent invocations of the
756@code{@value{DIRPREFIX}rate_monotonic_period} directive will result
757in the task blocking for the remainder of the 100 tick period.
758If, for any reason, the body of the loop takes more than 100
759ticks to execute, the @code{@value{DIRPREFIX}rate_monotonic_period}
760directive will return the @code{@value{RPREFIX}TIMEOUT} status. 
761If the above task misses its deadline, it will delete the rate
762monotonic period and itself.
763
764@subsection Task with Multiple Periods
765
766This example consists of a single periodic task
767which, after initialization, performs two sets of actions every
768100 clock ticks.  The first set of actions is performed in the
769first forty clock ticks of every 100 clock ticks, while the
770second set of actions is performed between the fortieth and
771seventieth clock ticks.  The last thirty clock ticks are not
772used by this task.
773
774@page
775@example
776rtems_task Periodic_task(rtems_task_argument arg)
777@{
778  rtems_name        name_1, name_2;
779  rtems_id          period_1, period_2;
780  rtems_status_code status;
781
782  name_1 = rtems_build_name( 'P', 'E', 'R', '1' );
783  name_2 = rtems_build_name( 'P', 'E', 'R', '2' );
784
785  (void ) rtems_rate_monotonic_create( name_1, &period_1 );
786  (void ) rtems_rate_monotonic_create( name_2, &period_2 );
787
788  while ( 1 ) @{
789    if ( rtems_rate_monotonic_period( period_1, 100 ) == TIMEOUT )
790      break;
791
792    if ( rtems_rate_monotonic_period( period_2, 40 ) == TIMEOUT )
793      break;
794
795    /*
796     *  Perform first set of actions between clock
797     *  ticks 0 and 39 of every 100 ticks.
798     */
799
800    if ( rtems_rate_monotonic_period( period_2, 30 ) == TIMEOUT )
801      break;
802
803    /*
804     *  Perform second set of actions between clock 40 and 69
805     *  of every 100 ticks.  THEN ...
806     *
807     *  Check to make sure we didn't miss the period_2 period.
808     */
809
810    if ( rtems_rate_monotonic_period( period_2, STATUS ) == TIMEOUT )
811      break;
812
813    (void) rtems_rate_monotonic_cancel( period_2 );
814  @}
815
816  /* missed period so delete period and SELF */
817
818  (void ) rtems_rate_monotonic_delete( period_1 );
819  (void ) rtems_rate_monotonic_delete( period_2 );
820  (void ) task_delete( SELF );
821@}
822@end example
823
824The above task creates two rate monotonic periods as
825part of its initialization.  The first time the loop is
826executed, the @code{@value{DIRPREFIX}rate_monotonic_period}
827directive will initiate the period_1 period for 100 ticks
828and return immediately.  Subsequent invocations of the
829@code{@value{DIRPREFIX}rate_monotonic_period} directive
830for period_1 will result in the task blocking for the remainder
831of the 100 tick period.  The period_2 period is used to control
832the execution time of the two sets of actions within each 100
833tick period established by period_1.  The
834@code{@value{DIRPREFIX}rate_monotonic_cancel( period_2 )}
835call is performed to ensure that the period_2 period
836does not expire while the task is blocked on the period_1
837period.  If this cancel operation were not performed, every time
838the @code{@value{DIRPREFIX}rate_monotonic_period( period_2, 40 )}
839call is executed, except for the initial one, a directive status
840of @code{@value{RPREFIX}TIMEOUT} is returned.  It is important to
841note that every time this call is made, the period_2 period will be
842initiated immediately and the task will not block.
843
844If, for any reason, the task misses any deadline, the
845@code{@value{DIRPREFIX}rate_monotonic_period} directive will
846return the @code{@value{RPREFIX}TIMEOUT}
847directive status.  If the above task misses its deadline, it
848will delete the rate monotonic periods and itself.
849
850@section Directives
851
852This section details the rate monotonic manager's
853directives.  A subsection is dedicated to each of this manager's
854directives and describes the calling sequence, related
855constants, usage, and status codes.
856
857@c
858@c
859@c
860@page
861@subsection RATE_MONOTONIC_CREATE - Create a rate monotonic period
862
863@cindex create a period
864
865@subheading CALLING SEQUENCE:
866
867@ifset is-C
868@findex rtems_rate_monotonic_create
869@example
870rtems_status_code rtems_rate_monotonic_create(
871  rtems_name  name,
872  rtems_id   *id
873);
874@end example
875@end ifset
876
877@ifset is-Ada
878@example
879procedure Rate_Monotonic_Create (
880   Name   : in     RTEMS.Name;
881   ID     :    out RTEMS.ID;
882   Result :    out RTEMS.Status_Codes
883);
884@end example
885@end ifset
886
887@subheading DIRECTIVE STATUS CODES:
888@code{@value{RPREFIX}SUCCESSFUL} - rate monotonic period created successfully@*
889@code{@value{RPREFIX}INVALID_NAME} - invalid task name@*
890@code{@value{RPREFIX}TOO_MANY} - too many periods created
891
892@subheading DESCRIPTION:
893
894This directive creates a rate monotonic period.  The
895assigned rate monotonic id is returned in id.  This id is used
896to access the period with other rate monotonic manager
897directives.  For control and maintenance of the rate monotonic
898period, RTEMS allocates a PCB from the local PCB free pool and
899initializes it.
900
901@subheading NOTES:
902
903This directive will not cause the calling task to be
904preempted.
905
906@c
907@c
908@c
909@page
910@subsection RATE_MONOTONIC_IDENT - Get ID of a period
911
912@cindex get ID of a period
913@cindex obtain ID of a period
914
915@subheading CALLING SEQUENCE:
916
917@ifset is-C
918@findex rtems_rate_monotonic_ident
919@example
920rtems_status_code rtems_rate_monotonic_ident(
921  rtems_name  name,
922  rtems_id   *id
923);
924@end example
925@end ifset
926
927@ifset is-Ada
928@example
929procedure Rate_Monotonic_Ident (
930   Name   : in     RTEMS.Name;
931   ID     :    out RTEMS.ID;
932   Result :    out RTEMS.Status_Codes
933);
934@end example
935@end ifset
936
937@subheading DIRECTIVE STATUS CODES:
938@code{@value{RPREFIX}SUCCESSFUL} - period identified successfully@*
939@code{@value{RPREFIX}INVALID_NAME} - period name not found
940
941@subheading DESCRIPTION:
942
943This directive obtains the period id associated with
944the period name to be acquired.  If the period name is not
945unique, then the period id will match one of the periods with
946that name.  However, this period id is not guaranteed to
947correspond to the desired period.  The period id is used to
948access this period in other rate monotonic manager directives.
949
950@subheading NOTES:
951
952This directive will not cause the running task to be
953preempted.
954
955@c
956@c
957@c
958@page
959@subsection RATE_MONOTONIC_CANCEL - Cancel a period
960
961@cindex cancel a period
962
963@subheading CALLING SEQUENCE:
964
965@ifset is-C
966@findex rtems_rate_monotonic_cancel
967@example
968rtems_status_code rtems_rate_monotonic_cancel(
969  rtems_id id
970);
971@end example
972@end ifset
973
974@ifset is-Ada
975@example
976procedure Rate_Monotonic_Cancel (
977   ID     : in     RTEMS.ID;
978   Result :    out RTEMS.Status_Codes
979);
980@end example
981@end ifset
982
983@subheading DIRECTIVE STATUS CODES:
984@code{@value{RPREFIX}SUCCESSFUL} - period canceled successfully@*
985@code{@value{RPREFIX}INVALID_ID} - invalid rate monotonic period id@*
986@code{@value{RPREFIX}NOT_OWNER_OF_RESOURCE} - rate monotonic period not created by calling task
987
988@subheading DESCRIPTION:
989
990This directive cancels the rate monotonic period id.
991This period will be reinitiated by the next invocation of
992@code{@value{DIRPREFIX}rate_monotonic_period} with id.
993
994@subheading NOTES:
995
996This directive will not cause the running task to be
997preempted.
998
999The rate monotonic period specified by id must have
1000been created by the calling task.
1001
1002@c
1003@c
1004@c
1005@page
1006@subsection RATE_MONOTONIC_DELETE - Delete a rate monotonic period
1007
1008@cindex delete a period
1009
1010@subheading CALLING SEQUENCE:
1011
1012@ifset is-C
1013@findex rtems_rate_monotonic_delete
1014@example
1015rtems_status_code rtems_rate_monotonic_delete(
1016  rtems_id id
1017);
1018@end example
1019@end ifset
1020
1021@ifset is-Ada
1022@example
1023procedure Rate_Monotonic_Delete (
1024   ID     : in     RTEMS.ID;
1025   Result :    out RTEMS.Status_Codes
1026);
1027@end example
1028@end ifset
1029
1030@subheading DIRECTIVE STATUS CODES:
1031@code{@value{RPREFIX}SUCCESSFUL} - period deleted successfully@*
1032@code{@value{RPREFIX}INVALID_ID} - invalid rate monotonic period id
1033
1034@subheading DESCRIPTION:
1035
1036This directive deletes the rate monotonic period
1037specified by id.  If the period is running, it is automatically
1038canceled.  The PCB for the deleted period is reclaimed by RTEMS.
1039
1040@subheading NOTES:
1041
1042This directive will not cause the running task to be
1043preempted.
1044
1045A rate monotonic period can be deleted by a task
1046other than the task which created the period.
1047
1048@c
1049@c
1050@c
1051@page
1052@subsection RATE_MONOTONIC_PERIOD - Conclude current/Start next period
1053
1054@cindex conclude current period
1055@cindex start current period
1056@cindex period initiation
1057
1058@subheading CALLING SEQUENCE:
1059
1060@ifset is-C
1061@findex rtems_rate_monotonic_period
1062@example
1063rtems_status_code rtems_rate_monotonic_period(
1064  rtems_id       id,
1065  rtems_interval length
1066);
1067@end example
1068@end ifset
1069
1070@ifset is-Ada
1071@example
1072procedure Rate_Monotonic_Period (
1073   ID      : in     RTEMS.ID;
1074   Length  : in     RTEMS.Interval;
1075   Result  :    out RTEMS.Status_Codes
1076);
1077@end example
1078@end ifset
1079
1080@subheading DIRECTIVE STATUS CODES:
1081@code{@value{RPREFIX}SUCCESSFUL} - period initiated successfully@*
1082@code{@value{RPREFIX}INVALID_ID} - invalid rate monotonic period id@*
1083@code{@value{RPREFIX}NOT_OWNER_OF_RESOURCE} - period not created by calling task@*
1084@code{@value{RPREFIX}NOT_DEFINED} - period has never been initiated (only
1085possible when period is set to PERIOD_STATUS)@*
1086@code{@value{RPREFIX}TIMEOUT} - period has expired
1087
1088@subheading DESCRIPTION:
1089
1090This directive initiates the rate monotonic period id
1091with a length of period ticks.  If id is running, then the
1092calling task will block for the remainder of the period before
1093reinitiating the period with the specified period.  If id was
1094not running (either expired or never initiated), the period is
1095immediately initiated and the directive returns immediately.
1096
1097If invoked with a period of @code{@value{RPREFIX}PERIOD_STATUS} ticks, the
1098current state of id will be returned.  The directive status
1099indicates the current state of the period.  This does not alter
1100the state or period of the period.
1101
1102@subheading NOTES:
1103
1104This directive will not cause the running task to be preempted.
1105
1106@c
1107@c
1108@c
1109@page
1110@subsection RATE_MONOTONIC_GET_STATUS - Obtain status information on period
1111
1112@cindex get status of period
1113@cindex obtain status of period
1114
1115@subheading CALLING SEQUENCE:
1116
1117@ifset is-C
1118@findex rtems_rate_monotonic_get_status
1119@example
1120rtems_status_code rtems_rate_monotonic_get_status(
1121  rtems_id                            id,
1122  rtems_rate_monotonic_period_status *status
1123);
1124@end example
1125@end ifset
1126
1127@ifset is-Ada
1128@example
1129procedure Rate_Monotonic_Get_Status (
1130   ID      : in     RTEMS.ID;
1131   Status  :    out RTEMS.Rate_Monotonic_Period_Status;
1132   Result  :    out RTEMS.Status_Codes
1133);
1134@end example
1135@end ifset
1136
1137@subheading DIRECTIVE STATUS CODES:
1138@code{@value{RPREFIX}SUCCESSFUL} - period initiated successfully@*
1139@code{@value{RPREFIX}INVALID_ID} - invalid rate monotonic period id@*
1140@code{@value{RPREFIX}INVALID_ADDRESS} - invalid address of status@*
1141
1142@subheading DESCRIPTION:
1143
1144This directive returns status information associated with
1145the rate monotonic period id in the following data @value{STRUCTURE}:
1146
1147@ifset is-C
1148@findex rtems_rate_monotonic_period_status
1149@example
1150typedef struct @{
1151  rtems_rate_monotonic_period_states  state;
1152  rtems_unsigned32                    ticks_since_last_period;
1153  rtems_unsigned32                    ticks_executed_since_last_period;
1154@}  rtems_rate_monotonic_period_status;
1155@end example
1156@end ifset
1157
1158@ifset is-Ada
1159@example
1160type Rate_Monotonic_Period_Status is
1161   begin
1162      State                    : RTEMS.Rate_Monotonic_Period_States;
1163      Ticks_Since_Last_Period  : RTEMS.Unsigned32;
1164      Ticks_Executed_Since_Last_Period : RTEMS.Unsigned32;
1165   end record;
1166@end example
1167@end ifset
1168
1169@c RATE_MONOTONIC_INACTIVE does not have RTEMS_ in front of it.
1170
1171If the period's state is @code{RATE_MONOTONIC_INACTIVE}, both
1172ticks_since_last_period and ticks_executed_since_last_period
1173will be set to 0.  Otherwise, ticks_since_last_period will
1174contain the number of clock ticks which have occurred since
1175the last invocation of the
1176@code{@value{DIRPREFIX}rate_monotonic_period} directive.
1177Also in this case, the ticks_executed_since_last_period will indicate
1178how much processor time the owning task has consumed since the invocation
1179of the @code{@value{DIRPREFIX}rate_monotonic_period} directive.
1180
1181@subheading NOTES:
1182
1183This directive will not cause the running task to be preempted.
Note: See TracBrowser for help on using the repository browser.