source: rtems/doc/user/rtmon.t @ 337d369

4.104.114.84.95
Last change on this file since 337d369 was 78287f41, checked in by Joel Sherrill <joel.sherrill@…>, on 03/27/02 at 17:35:15

2002-03-27 Eric Norum <eric.norum@…>

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