One of the first works on scheduling theory for computer systems appeared in 1967 by Conway, Maxwell, and Miller [CML67]. In this work, they reference much scheduling work that up to that point had been primarily used in job shops across the country. They discuss results which are applicable to both what later became known as classical scheduling theory, and real time systems.
Classical scheduling theory - such as what would normally be seen in a regular multitasking operating system such as Unix - typically uses metrics such as minimizing the sum of completion times, minimizing the weighted sum of completion times, minimizing schedule length, or minimizing the number of processors required. Most of these metrics evolved in job shops during and immediately after World War II, where the main concern was of maximizing the throughput of a given machine, such as both lathes and a milling machines.
In 1973, Coffman and Denning [CD73] showed that these metrics are not useful for Real Time Systems. For example, the sum of completion times is useless for time critical systems because there is no direct assessment of timing properties (deadlines or periods) in the metric. Thus this algorithm may be desirable for Unix, where the goal is to maximize the throughput or number of tasks that are executed in a given amount of time, but will not be desirable for a hard timing environment as would be the case of AMB control.
Real time researchers thus looked at the second results presented by Conway et al.. Namely, they cite a 1955 job-shop scheduling result by Jackson, where he states:
The maximum lateness and maximum job tardiness are minimized by sequencing the jobs in order of non-decreasing due dates
This algorithm, which is usually referred to as the ``Earliest Deadline First'' or simply EDF algorithm, has been shown to be optimal for uniprocessor systems, where optimality in real time scheduling algorithms is measured by the following:
An optimal scheduling algorithm is one that may fail to meet a deadline only if no other scheduling algorithm can meet it.
The Jackson result sparked much interest and consequently spawned two areas of real time scheduling research. Namely, it developed research in both dynamic and static scheduling, the latter of which is more applicable to AMB control. A scheduling algorithm is said to be ``dynamic'' when the algorithm has full knowledge of task properties1.5 of both previous and present tasks. However, it has no knowledge of future tasks, neither in the number of tasks nor in their start times.
A static scheduler, on the other hand, knows the task properties of
all past, present, and future tasks and therefore it is possible to
set up the key scheduling parameters a priori. As a simple
example, suppose that an AMB will use a simple PID for thrust control
and a plotting package for real time monitoring of plant states. We
know a priori that the suspension controller must execute
every microseconds without fail, and that the plotting package
will execute once every
microseconds, although we are not too
concerned if one time it executes after 14k or after 50k
microseconds. Consequently, we can assign, a priori some
schedule parameters such as the next execution time (now + 100
microseconds and now + 14k microseconds), and a relative priority (it
is more important that the suspension controller executes at its
specified time).
A ``fixed priority scheduler'' (FPS) is a type of static scheduling algorithm where tasks are assigned - a priori - a priority, or relative importance, as shown in Figure 1.2. Each task has an associated start time at which the task is expected to begin its execution, an execution time, and a completion time. Thus, at both the start time and completion times of each of these tasks, the scheduler must make a decision. That is, it must decide which task should be allowed to execute in the CPU at any point in time to meet all deadlines. Higher priority tasks are given precedence over lower priority tasks, and tasks having the same priority level are assigned into the CPU on a First In First Out (FIFO) scheme. Tasks may preempt lower priority tasks, only, and tasks in general are assumed to be completely independent of each other. Research in FPS algorithms is most heavy in optimal solutions to the priority assignment for each of these tasks, since depending on how priorities are assigned will determine if deadlines are met.
![]() |
In 1973, Liu and Layland [LL73] developed the ``Rate Monotonic Algorithm'' (RMA). This algorithm assigns priorities to each of the tasks in the following fashion:
The priority of the task is inversely proportional to its period.
In other words, under this assignment policy, tasks having
the smallest period (highest frequency) - as would be the case for a
suspension controller in an AMB - would have the higher priority over
a second task that executes with a larger period. Of most importance
is that this algorithm was shown by Liu and Layland to be optimal among FPS algorithms for real time systems, and that it can
be applied for tasks (
).
Unfortunately, the RMA algorithm was shown to be optimal by Liu and Layland only for independent tasks. However, since there is a large need for communication between controller tasks in an AMB (for example, controller effort from the suspension task are communicated to a second task which in turn transmits this information over the network), the RMA algorithm can be shown to be limiting for real time applications. Consequently, research ensued which tried to relax this independence assumption, necessary for RMA.
The direct application of a simple semaphore1.6, or synchronization variable, for sharing critical data between tasks may result in a high priority task being blocked by a lower priority task for an unbounded amount of time. More importantly, this may potentially lead to missed deadlines. This type of unbounded blocking is usually referred to as priority inversion, and is exemplified in Figure 1.3.
![]() |
Priority inversion usually occurs when there are three or more tasks present, and data is shared between both the highest and lowest priority tasks. Generally, the lowest priority task may get a hold of the semaphore and begin accessing data. Then, sometime later, the highest priority task will attempt to access the semaphore but will find that it is already locked by the lowest priority task, and therefore the highest priority task is blocked by the lowest priority task. At this time the lowest priority task resumes execution. However, some time later, the medium priority task begins executing and preempts the lowest priority task. Consequently, the highest priority task not only needs to wait for the medium priority task to finish, but also for the lowest priority task to release the semaphore. The problem becomes more acute when there are more than one medium priority tasks. Consequently, the highest priority task will have to wait for an undetermined amount of time until all intermediate priority tasks complete, and the lowest priority task releases its semaphore.
One solution to this problem is to carefully design each of the real time tasks to avoid this priority inversion problem. However, this becomes inordinately difficult as the number of tasks increases.
A powerful solution to the priority inversion problem was introduced by Sha et al. in 1990 [SRL90] under the name of ``priority inheritance protocols'' (PIPs). PIPs are a series of protocols in which the lower priority tasks that may be blocking a higher priority task will, while blocking the higher priority task, automatically inherit the priority of the highest priority task that the offending task blocks. Two protocols were presented: a basic priority inheritance protocol and a priority ceiling protocol. In both cases, priority inversion will be solved by effectively bounding the maximum amount of time that the highest priority tasks will be blocked by the lower priority tasks. The former will block the higher priority task by at most the duration of one critical section from each of the lower tasks which share semaphores with the higher priority tasks, while the latter will block the higher priority task by at most the duration of one shared segment from any of the lower priority tasks. Thus, by the application of either of these protocols, one can know, a priori the worst case execution time of any tasks.