Figure 2: TUF from GD-CMU™s BM=C 2 system.
lation centers with an unpopulated expanse in between, the optimal completion time for the self-destruct task would be the halfway point. The timeliness criteria of such a task can be expressed in the form of the depicted TUF. Another commonly used TUFs is illustrated in Figure 1(c) where the task™s utility diminishes beyond the optimal completion time, yet is still of some value even though tardy. Figure 1(d) depicts two execution segments of a single task. The task arrives at ta, starts execution at ts, is preempted at tp, resumes execution at tr and completes its execution at tc.
TUFs are often found in an emerging class of real-time control systems collectively known as supervisory systems. Such systems are typically deployed in environments where there exist significant runtime uncertainty and frequent overload conditions, making it difficult to provide firm guarantees of deter-ministic temporal system behavior. Soft real-time algorithms are increasingly incorporated into these complex systems to provide resource scheduling decision support. For example, under such conditions the system may not meet all deadlines, but some degree of predictability can be expected, given a predefined set of criteria. Crafting TUFs is, therefore, a highly application-specific endeavor [4, 5].
Figure 2 illustrates one such TUF from an operational BM=C 2 supervisory system [7]. The system is designed to address a problem that can be generically described as dynamic interception of moving objects. Assume we wish to intercept a set of moving objects prior to their crossing a specific boundary. Further, assume our secondary objective is for the interceptions to occur as far away from the boundary as possible.
Remote sensors track the location of the moving objects and continuously communicate updated coordinates to interceptors. The distance between the interceptors and the objects is greatest at interceptor launch time. It initially suffices the interceptors to aperiodically receive object coordinates for the purposes of plotting a proximity intercept course. As the interceptors close range with the moving objects, more frequent and timely updates are required to make appropriate course corrections. The interceptors require the finest-grain update periodicity just prior to contact. The interceptors must complete course calculations based on received sensor data by t critical . Arrow 1 in Figure 2 reflects the inverse proportionality of range and update frequency. Furthermore, should an interceptor receive fresh sensor data in mid-calculations, it must drop currently incomplete calculations of now-stale data in favor of more accurate results to be derived from the newly communicated update. The rapidly decreasing utility of completing calculations based on old data is reflected by arrow 2. Lastly, arrow 3 indicates the urgency of the intercept as the objects close their distance with their intended destinations. Interception, for instance, of an object that has penetrated the boundary would be of higher utility than one that is considerably
farther out. Figure 2(b) illustrates the dynamically changing TUF during various phases of interceptor operations [7].
Unaware of timing constraints, general-purpose OS schedulers extend the time horizon of task execution during over-load: all tasks eventually complete [9]. Similarly, general-purpose memory managers expand the limits of main memory into secondary store during memory overload [9, 10]. Virtual memory, however, is often impractical for real-time systems. Resource-constrained embedded systems may be limited to main memory only, while others may not be able to bear the high cost and unpredictability of demand paging. As such, real-time systems often rely solely on main memory, static allocation, and dedicated fixed-sized partitions to increase predictability. This approach is well-suited for the deterministic environment of a hard real-time system. Conversely, the less predictable environment of a soft real-time system would be conducive to a more space-efficient and dynamic storage management scheme. Furthermore, general-purpose memory managers indiscriminately service memory requests unaware of other attributes of the requesting task.
UA tasks currently allocate memory statically at load-time to ensure sustained availability. Unaware of its memory footprint, the scheduler may admit a task into the system, soon to preempt it by another. The preempted task, however, retains its allocated memory while waiting in the ready queue. Not unlike the priority inversion problem, This can lead to low utility tasks holding disproportionately large amounts of memory, while preventing admission of newly arrived high utility tasks.
The scheduling problem addressed by MSA is N P
-hard along both independent dimensions of time and memory. Optimal sequencing of TUF-described independent tasks is shown to be N P
-hard in [2], and optimal value-based storage mapping reduces to the classic N P
-hard 0 = 1 knapsack problem [8]. As MSA is an on-line scheduler in a dynamic real-time environment, it cannot afford an exhaustive search to produce the optimal solution. A heuristic approach must therefore be employed to produce an approximate solution in polynomially bounded time. MSA utilizes a hybrid greedy, geometric, and partial-combinatoric approximation heuristic.
MSA is invoked at the scheduling points of: task arrival, task completion, memory allocation request (static and dynamic), and memory de-allocation. The scheduler is preemptive and operates in a uni-processor, single address-space environment. Preempted and blocked tasks stay in the system until completion or time-infeasibility, whichever comes first. The scheduler may also elect to fiterminatefl a task in which case, the task is discarded from the system and all its held resources reclaimed.
Furthermore, memory allocation requests are wrapped to be blocking calls managed by the scheduler. The allocation request may not be serviced immediately, but upon a state transition, the scheduler may grant the request if the requesting task is still time-feasible. The notion of a blocking memory allocation request is similar to FreeBSD™s kernel implementation of a blocking malloc that ensures eventual memory availability for specific device drivers.
Throughout this paper, we make the assumption that there are n independent tasks (interchangeably, jobs) in the system: J = f
j 1 ; j 2 ; : : : ; jng
, each characterized by the triplet