After an embedded application has been decomposed into ISRs and tasks, the tasks must be scheduled to run in order to perform required system functionality. Schedulability analysis determines if all tasks can be scheduled to run and meet their deadlines based on the deployed scheduling algorithm while still achieving optimal processor utilization.
Note that schedulability analysis looks only at how systems meet temporal requirements, not functional requirements.
The commonly practiced analytical method for real-time systems is Rate Monotonic Analysis (RMA). Liu and Layland initially developed the mathematical model for RMA in 1973. (This book calls their RMA model the basic RMA because it has since been extended by later researchers.) The model is developed over a scheduling mechanism called Rate Monotonic Scheduling (RMS), which is the preemptive scheduling algorithm with rate monotonic priority assignment as the task priority assignment policy. Rate monotonic priority assignment is the method of assigning a task its priority as a monotonic function of the execution rate of that task. In other words, the shorter the period between each execution, the higher the priority assigned to a task.
A set of assumptions is associated with the basic RMA. These assumptions are that:
all of the tasks are periodic,
the tasks are independent of each other and that no interactions occur among tasks,
a task's deadline is the beginning of its next period,
each task has a constant execution time that does not vary over time,
all of the tasks have the same level of criticality, and
aperiodic tasks are limited to initialization and failure recovery work and that these aperiodic tasks do not have hard deadlines.
Equation 14.1 is used to perform the basic RMA schedulability test on a system.
C_{i }= worst-case execution time associated with periodic task I
T_{i} = period associated with task i
n = number of tasks
U( n) is the utilization factor. The right side of the equation is the theoretical processor utilization bound. If the processor utilization for a given set of tasks is less than the theoretical utilization bound, this set of tasks is schedulable. The value of U decreases as n increases and eventually converges to 69% when n becomes infinite.
Let's look at a sample problem and see how the formula is implemented. Table 14.3 summarizes the properties of three tasks that are scheduled using the RMS.
Periodic Task |
Execution Time |
Period (milliseconds) |
---|---|---|
Task 1 |
20 |
100 |
Task 2 |
30 |
150 |
Task 3 |
50 |
300 |
Using Equation 14.1, the processor utilization for this sample problem is calculated as follows
Total utilization for the sample problem is at 57%, which is below the theoretical bound of 77%. This system of three tasks is schedulable, i.e., every task can meet its deadline.
The basic RMA is limiting. The second assumption associated with basic RMA is impractical because tasks in real-time systems have inter-dependencies, and task synchronization methods are part of many real-time designs. Task synchronization, however, lies outside the scope of basic RMA.
Deploying inter-task synchronization methods implies some tasks in the system will experience blocking, which is the suspension of task execution because of resource contention. Therefore, the basic RMA is extended to account for task synchronization. Equation 14.2 provides the equation for the extended RMA schedulability test.
where:
C_{i }= worst case execution time associated with periodic task I
T_{i} = period associated with task i
B_{i} = the longest duration of blocking that can be experienced by I
n = number of tasks
This equation is best demonstrated with an example. This example uses the same three tasks provided in Table 14.3 and inserts two shared resources, as shown in Figure 14.7. In this case, the two resources represent a shared memory (resource #1) and an I/O bus (resource #2).
Task #1 makes use of resource #2 for 15ms at a rate of once every 100ms. Task #2 is a little more complex. It is the only task that uses both resources. Resource #1 is used for 5ms, and resource #2 is used for 10ms. Task #2 must run at a rate of once every 150ms.
Task #3 has the lowest frequency of the tasks and runs once every 300ms. Task #3 also uses resource #2 for 18ms.
Now looking at schedulability, Equation 14.2 yields three separate equations that must be verified against a utility bound. Let's take a closer look at the first equation
Either task #2 or task #3 can block task #1 by using resource #2. The blocking factor B_{1} is the greater of the times task #2 or task #3 holds the resource, which is 18ms, from task #3. Applying the numbers to Equation 14.2, the result is below the utility bound of 100% for task #1. Hence, task #1 is schedulable.
Looking at the second equation, task #2 can be blocked by task #3. The blocking factor B_{2} is 18ms, which is the time task #3 has control of resource #2, as shown
Task #2 is also schedulable as the result is below the utility bound for two tasks. Now looking at the last equation, note that B_{n} is always equal to 0. The blocking factor for the lowest level task is always 0, as no other tasks can block it (they all preempt it if they need to), as shown
Again, the result is below the utility bound for the three tasks, and, therefore, all tasks are schedulable.
Other extensions are made to basic RMA for dealing with the rest of the assumptions associated with basic RMA, such as accounting for aperiodic tasks in real-time systems. Consult the listed references for additional readings on RMA and related materials.