diff options
Diffstat (limited to 'c-user/rate-monotonic/background.rst')
| -rw-r--r-- | c-user/rate-monotonic/background.rst | 390 |
1 files changed, 390 insertions, 0 deletions
diff --git a/c-user/rate-monotonic/background.rst b/c-user/rate-monotonic/background.rst new file mode 100644 index 0000000..9ca7dff --- /dev/null +++ b/c-user/rate-monotonic/background.rst @@ -0,0 +1,390 @@ +.. SPDX-License-Identifier: CC-BY-SA-4.0 + +.. Copyright (C) 1988, 2008 On-Line Applications Research Corporation (OAR) +.. Copyright (C) 2017 Kuan-Hsun Chen. + +Background +========== + +The rate monotonic manager provides facilities to manage the execution of +periodic tasks. This manager was designed to support application designers who +utilize the Rate Monotonic Scheduling Algorithm (RMS) to ensure that their +periodic tasks will meet their deadlines, even under transient overload +conditions. Although designed for hard real-time systems, the services +provided by the rate monotonic manager may be used by any application which +requires periodic tasks. + +Rate Monotonic Manager Required Support +--------------------------------------- + +A clock tick is required to support the functionality provided by this manager. + +Period Statistics +----------------- + +This manager maintains a set of statistics on each period object. These +statistics are reset implictly at period creation time and may be reset or +obtained at any time by the application. The following is a list of the +information kept: + +``owner`` + is the id of the thread that owns this period. + +``count`` + is the total number of periods executed. + +``missed_count`` + is the number of periods that were missed. + +``min_cpu_time`` + is the minimum amount of CPU execution time consumed on any execution of the + periodic loop. + +``max_cpu_time`` + is the maximum amount of CPU execution time consumed on any execution of the + periodic loop. + +``total_cpu_time`` + is the total amount of CPU execution time consumed by executions of the + periodic loop. + +``min_wall_time`` + is the minimum amount of wall time that passed on any execution of the + periodic loop. + +``max_wall_time`` + is the maximum amount of wall time that passed on any execution of the + periodic loop. + +``total_wall_time`` + is the total amount of wall time that passed during executions of the + periodic loop. + +Each period is divided into two consecutive phases. The period starts with the +active phase of the task and is followed by the inactive phase of the task. In +the inactive phase the task is blocked and waits for the start of the next +period. The inactive phase is skipped in case of a period miss. The wall time +includes the time during the active phase of the task on which the task is not +executing on a processor. The task is either blocked (for example it waits for +a resource) or a higher priority tasks executes, thus preventing it from +executing. In case the wall time exceeds the period time, then this is a +period miss. The gap between the wall time and the period time is the margin +between a period miss or success. + +The period statistics information is inexpensive to maintain and can provide +very useful insights into the execution characteristics of a periodic task +loop. But it is just information. The period statistics reported must be +analyzed by the user in terms of what the applications is. For example, in an +application where priorities are assigned by the Rate Monotonic Algorithm, it +would be very undesirable for high priority (i.e. frequency) tasks to miss +their period. Similarly, in nearly any application, if a task were supposed to +execute its periodic loop every 10 milliseconds and it averaged 11 +milliseconds, then application requirements are not being met. + +The information reported can be used to determine the "hot spots" in the +application. Given a period's id, the user can determine the length of that +period. From that information and the CPU usage, the user can calculate the +percentage of CPU time consumed by that periodic task. For example, a task +executing for 20 milliseconds every 200 milliseconds is consuming 10 percent of +the processor's execution time. This is usually enough to make it a good +candidate for optimization. + +However, execution time alone is not enough to gauge the value of optimizing a +particular task. It is more important to optimize a task executing 2 +millisecond every 10 milliseconds (20 percent of the CPU) than one executing 10 +milliseconds every 100 (10 percent of the CPU). As a general rule of thumb, +the higher frequency at which a task executes, the more important it is to +optimize that task. + +.. index:: periodic task, definition + +Periodicity Definitions +---------------------------------- + +A periodic task is one which must be executed at a regular interval. The +interval between successive iterations of the task is referred to as its +period. Periodic tasks can be characterized by the length of their period and +execution time. The period and execution time of a task can be used to +determine the processor utilization for that task. Processor utilization is +the percentage of processor time used and can be calculated on a per-task or +system-wide basis. Typically, the task's worst-case execution time will be +less than its period. For example, a periodic task's requirements may state +that it should execute for 10 milliseconds every 100 milliseconds. Although +the execution time may be the average, worst, or best case, the worst-case +execution time is more appropriate for use when analyzing system behavior under +transient overload conditions... index:: aperiodic task, definition + +In contrast, an aperiodic task executes at irregular intervals and has only a +soft deadline. In other words, the deadlines for aperiodic tasks are not +rigid, but adequate response times are desirable. For example, an aperiodic +task may process user input from a terminal. + +.. index:: sporadic task, definition + +Finally, a sporadic task is an aperiodic task with a hard deadline and minimum +interarrival time. The minimum interarrival time is the minimum period of time +which exists between successive iterations of the task. For example, a +sporadic task could be used to process the pressing of a fire button on a +joystick. The mechanical action of the fire button ensures a minimum time +period between successive activations, but the missile must be launched by a +hard deadline. + +.. index:: Rate Monotonic Scheduling Algorithm, definition +.. index:: RMS Algorithm, definition + +Rate Monotonic Scheduling Algorithm +----------------------------------- + +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:`Sha: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: + +.. sidebar:: *RMS* + + RMS is an optimal fixed-priority algorithm for scheduling independent, + preemptible, periodic tasks on a single processor. + +RMS is optimal in the sense that if a set of tasks can be scheduled by any +fixed-priority algorithm, then RMS will be able to schedule that task set. +RMS bases it schedulability analysis on the processor utilization level below +which all deadlines can be met. + +RMS calls for the static assignment of task priorities based upon their period. +The shorter a task's period, the higher its priority. For example, a task with +a 1 millisecond period has higher priority than a task with a 100 millisecond +period. If two tasks have the same period, then RMS does not distinguish +between the tasks. However, RTEMS specifies that when given tasks of equal +priority, the task which has been ready longest will execute first. RMS's +priority assignment scheme does not provide one with exact numeric values for +task priorities. For example, consider the following task set and priority +assignments: + ++--------------------+---------------------+---------------------+ +| Task | Period | Priority | +| | (in milliseconds) | | ++====================+=====================+=====================+ +| 1 | 100 | Low | ++--------------------+---------------------+---------------------+ +| 2 | 50 | Medium | ++--------------------+---------------------+---------------------+ +| 3 | 50 | Medium | ++--------------------+---------------------+---------------------+ +| 4 | 25 | High | ++--------------------+---------------------+---------------------+ + +RMS only calls for task 1 to have the lowest priority, task 4 to have the +highest priority, and tasks 2 and 3 to have an equal priority between that of +tasks 1 and 4. The actual RTEMS priorities assigned to the tasks must only +adhere to those guidelines. + +Many applications have tasks with both hard and soft deadlines. The tasks with +hard deadlines are typically referred to as the critical task set, with the +soft deadline tasks being the non-critical task set. The critical task set can +be scheduled using RMS, with the non-critical tasks not executing under +transient overload, by simply assigning priorities such that the lowest +priority critical task (i.e. longest period) has a higher priority than the +highest priority non-critical task. Although RMS may be used to assign +priorities to the non-critical tasks, it is not necessary. In this instance, +schedulability is only guaranteed for the critical task set. + +.. index:: RMS schedulability analysis + +Schedulability Analysis +----------------------- + +RMS allows application designers to ensure that tasks can meet all deadlines under fixed-priority assignment, +even under transient overload, without knowing exactly when any given task will +execute by applying proven schedulability analysis rules. + +Assumptions +^^^^^^^^^^^ + +The schedulability analysis rules for RMS were developed based on the following +assumptions: + +- The requests for all tasks for which hard deadlines exist are periodic, with + a constant interval between requests. + +- Each task must complete before the next request for it occurs. + +- The tasks are independent in that a task does not depend on the initiation or + completion of requests for other tasks. + +- The execution time for each task without preemption or interruption is + constant and does not vary. + +- Any non-periodic tasks in the system are special. These tasks displace + periodic tasks while executing and do not have hard, critical deadlines. + +Once the basic schedulability analysis is understood, some of the above +assumptions can be relaxed and the side-effects accounted for. + +.. index:: RMS Processor Utilization Rule + +Processor Utilization Rule +^^^^^^^^^^^^^^^^^^^^^^^^^^ + +The Processor Utilization Rule requires that processor utilization be +calculated based upon the period and execution time of each task. +The fraction of processor time spent executing task index is ``Time(i) +/ Period(i)``. The processor utilization can be calculated as follows +where n is the number of tasks in the set being analyzed: + +.. math:: + + Utilization = \sum_{i=1}^{n} Time_i/Period_i + +To ensure schedulability even under transient overload, the processor +utilization must adhere to the following rule: + +.. math:: + + maximumUtilization = n * (2^{\frac{1}{n}} - 1) + +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 +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +This example illustrates the application of the Processor Utilization Rule to +an application with three critical periodic tasks. The following table details +the RMS priority, period, execution time, and processor utilization for each +task: + ++------------+----------+--------+-----------+-------------+ +| Task | RMS | Period | Execution | Processor | +| | Priority | | Time | Utilization | ++============+==========+========+===========+=============+ +| 1 | High | 100 | 15 | 0.15 | ++------------+----------+--------+-----------+-------------+ +| 2 | Medium | 200 | 50 | 0.25 | ++------------+----------+--------+-----------+-------------+ +| 3 | Low | 300 | 100 | 0.33 | ++------------+----------+--------+-----------+-------------+ + +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. + +.. index:: RMS First Deadline Rule + +First Deadline Rule +^^^^^^^^^^^^^^^^^^^ + +If a given set of tasks do exceed the processor utilization upper limit imposed +by the Processor Utilization Rule, they can still be guaranteed to meet all +their deadlines by application of the First Deadline Rule. This rule can be +stated as follows: + +For a given set of independent periodic tasks, if each task meets its first +deadline when all tasks are started at the same time, then the deadlines will +always be met for any combination of start times. + +A key point with this rule is that ALL periodic tasks are assumed to start at +the exact same instant in time. Although this assumption may seem to be +invalid, RTEMS makes it quite easy to ensure. By having a non-preemptible user +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 +^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +The First Deadline Rule can ensure schedulability even when the Processor +Utilization Rule fails. The example below is a modification of the Processor +Utilization Rule example where task execution time has been increased from 15 +to 25 units. The following table details the RMS priority, period, execution +time, and processor utilization for each task: + ++------------+----------+--------+-----------+-------------+ +| Task | RMS | Period | Execution | Processor | +| | Priority | | Time | Utilization | ++============+==========+========+===========+=============+ +| 1 | High | 100 | 25 | 0.25 | ++------------+----------+--------+-----------+-------------+ +| 2 | Medium | 200 | 50 | 0.25 | ++------------+----------+--------+-----------+-------------+ +| 3 | Low | 300 | 100 | 0.33 | ++------------+----------+--------+-----------+-------------+ + +The total processor utilization for the modified task set is 0.83 which is +above the upper bound of 3 * (2**(1/3) - 1), or 0.779, imposed by the Processor +Utilization Rule. Therefore, this task set is not guaranteed to be schedulable +using RMS. However, the First Deadline Rule can guarantee the schedulability +of this task set. This rule calls for one to examine each occurrence of +deadline until either all tasks have met their deadline or one task failed to +meet its first deadline. The following table details the time of each deadline +occurrence, the maximum number of times each task may have run, the total +execution time, and whether all the deadlines have been met: + ++----------+------+------+------+----------------------+---------------+ +| Deadline | Task | Task | Task | Total | All Deadlines | +| Time | 1 | 2 | 3 | Execution Time | Met? | ++==========+======+======+======+======================+===============+ +| 100 | 1 | 1 | 1 | 25 + 50 + 100 = 175 | NO | ++----------+------+------+------+----------------------+---------------+ +| 200 | 2 | 1 | 1 | 50 + 50 + 100 = 200 | YES | ++----------+------+------+------+----------------------+---------------+ + +The key to this analysis is to recognize when each task will execute. For +example at time 100, task 1 must have met its first deadline, but tasks 2 and 3 +may also have begun execution. In this example, at time 100 tasks 1 and 2 have +completed execution and thus have met their first deadline. Tasks 1 and 2 have +used (25 + 50) = 75 time units, leaving (100 - 75) = 25 time units for task 3 +to begin. Because task 3 takes 100 ticks to execute, it will not have +completed execution at time 100. Thus at time 100, all of the tasks except +task 3 have met their first deadline. + +At time 200, task 1 must have met its second deadline and task 2 its first +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. + +Relaxation of Assumptions +^^^^^^^^^^^^^^^^^^^^^^^^^ + +The assumptions used to develop the RMS schedulability rules are uncommon in +most real-time systems. For example, it was assumed that tasks have constant +unvarying execution time. It is possible to relax this assumption, simply by +using the worst-case execution time of each task. + +Another assumption is that the tasks are independent. This means that the +tasks do not wait for one another or contend for resources. This assumption +can be relaxed by accounting for the amount of time a task spends waiting to +acquire resources. Similarly, each task's execution time must account for any +I/O performed and any RTEMS directive calls. + +In addition, the assumptions did not account for the time spent executing +interrupt service routines. This can be accounted for by including all the +processor utilization by interrupt service routines in the utilization +calculation. Similarly, one should also account for the impact of delays in +accessing local memory caused by direct memory access and other processors +accessing local dual-ported memory. + +The assumption that nonperiodic tasks are used only for initialization or +failure-recovery can be relaxed by placing all periodic tasks in the critical +task set. This task set can be scheduled and analyzed using RMS. All +nonperiodic tasks are placed in the non-critical task set. Although the +critical task set can be guaranteed to execute even under transient overload, +the non-critical task set is not guaranteed to execute. + +In conclusion, the application designer must be fully cognizant of the system +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. |