APERIODIC TASK SCHEDULING - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 68

3.4.2 THE SPRING ALGORITHM

Here we describe the scheduling algorithm adopted in the Spring kernel [SR87, SR91],
a hard real-time kernel designed at the University of Massachusetts at Amherst by
Stankovic and Ramamritham to support critical control applications in dynamic en-
vironments. The objective of the algorithm is to find a feasible schedule when tasks
have different types of constraints, such as precedence relations, resource constraints,
arbitrary arrivals, non-preemptive properties, and importance levels. The Spring algo-
rithm is used in a distributed computer architecture and can also be extended to include
fault-tolerance requirements.

Clearly, this problem is NP -hard and finding a feasible schedule would be too expen-
sive in terms of computation time, especially for dynamic systems. In order to make
the algorithm computationally tractable even in the worst case, the search is driven by
a heuristic function H, which actively directs the scheduling to a plausible path. On
each level of the search, function H is applied to each of the tasks that remain to be
scheduled. The task with the smallest value determined by the heuristic function H is
selected to extend the current schedule.

The heuristic function is a very flexible mechanism to easily define and modify the
scheduling policy of the kernel. For example, if H = a i (arrival time) the algorithm
behaves as First Come First Served, if H = C i (computation time) it works as Shortest
Job First, whereas if H = d i (deadline) the algorithm is equivalent to Earliest Deadline
First.

To consider resource constraints in the scheduling algorithm, each task J i has to de-
clare a binary array of resources R i =[ R 1 ( i ) ,...,R r ( i )], where R k ( i )=0if J i
does not use resource R k , and R k ( i )=1if J i uses R k in exclusive mode. Given a
partial schedule, the algorithm determines, for each resource R k , the earliest time the
resource is available. This time is denoted as EAT k (Earliest Available Time). Thus,
the earliest start time that a task J i can begin the execution without blocking on shared
resources is

T est ( i )=max[ a i , max
k

( EAT k )] ,

where a i is the arrival time of J i . Once T est is calculated for all the tasks, a possible
search strategy is to select the task with the smallest value of T est . Composed heuristic
functions can also be used to integrate relevant information on the tasks, such as

H d + W · C

=

H d + W · T est ,

=