# 11.2. 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.

## 11.2.1. Rate Monotonic Manager Required Support¶

A clock tick is required to support the functionality provided by this manager.

## 11.2.2. 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.

## 11.2.3. 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.

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.

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.

## 11.2.4. 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 [LL73], [LSD89], [SG90], [Bur91]).

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:

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.

Period (in milliseconds)

Priority

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.

## 11.2.5. 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.

### 11.2.5.1. 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 should not 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.

### 11.2.5.2. 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:

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

$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 [LL73].

### 11.2.5.3. 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:

RMS Priority

Period

Execution Time

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

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 [LSD89].

### 11.2.5.5. 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:

RMS Priority

Period

Execution Time

Processor Utilization

1

High

100

25

0.25

2

Medium

200

50

0.25

3

Low

300

100

0.33

Total Execution Time

100

1

1

1

25 + 50 + 100 = 175

NO

200

2

1

1

50 + 50 + 100 = 200

YES