Time/Utility Function History, Related Work, and References

In 1976, Jensen devised time/utility functions (then called simply "utility functions") for scheduling the acquisition radar portion of the United States' only operational anti-ballistic missile system, known as SAFEGUARD. The U.S. Army Safeguard Command's AN/FPQ-16 Perimeter Acquisition Radar Characterization System was located at Grand Forks Air Force Base in Cavalier (“Concrete”), North Dakota. (In 1977 the site was recommissioned as the USAF Space Command's Cavalier Air Force Station.) [srmsc.org][globalsecurity.org] See Figure 1.

Figure 1: AN/FPQ-16 Perimeter Acquisition Radar Characterization System

Jensen's team performed simulations which indicated that time/utility function scheduling improved the phased array radar's performance enough that someone in the Federal government decided the Soviet Union might consider it a violation of the 1972 antiballistic missile treaty (SALT II). Furthermore, the entire SAFEGUARD system was overtaken by political events and technological progress, and decommissioned in 1976. Consequently, our time/utility function scheduler for the radar was never deployed, and its performance results are still classified. This work is mentioned in a highly sanitized summary document [Gouda77].

Research on time/utility functions and utility accrual algorithms resumed in 1983, as part of Jensen's Archons Project [reference] in the Computer Science Department at Carnegie Mellon University.

The first public paper about time/utility functions (then called "time/value functions") was published in the 1985 Real-Time Systems Symposium by Jensen, Locke, and Tokuda [Jensen 85.

Then two of Jensen's Ph.D. students wrote the first theses on this topic: Doug Locke [Locke 86], and Ray Clark [Clark 90]. The algorithm in Doug Locke's thesis allowed almost all non-convex time/utility functions (excluding those having no downward inflection point at what we called the "critical time"; and it provided for stochastic load properties.  Clark's thesis had more formalism than Locke's, and his algorithm's major strength was that it allowed for dependencies among the actions; it also out-performed Locke's in most cases. However, it was limited to downward step (i.e., deadline) functions, and a' priori known timeliness properties.

Locke's algorithm was implemented in our Alpha real-time operating system kernel [Northcutt 87, Clark et al. 93].

To transition the Alpha keystone technologies -- distributed threads and time/utility function utility accrual scheduling -- into industry, Jensen took a half-time leave of absence from CMU and became employee 11 at a start-up named Kendall Square Research (KSR), in Cambridge, MA. KSR intended that an Alpha-based distributed real-time OS be the OS for its KSR-1 multicomputer. The DoD funding for continued research on Alpha moved with Jensen to KSR.

The KSR hardware was unexpectedly slow to materialize, so the Alpha project sought an alternative COTS multiprocessor product on which to develop the second generation of the Alpha OS. There were few choices, and Jensen selected a MASSCOMP product, in part because MASSCOMP was located in the Boston area. About that time, KSR decided to move away from real-time toward scientific applications, so Jensen accepted a position as Chief Scientist at MASSCOMP, a leading real-time computing systems vendor. Jensen moved the Alpha project and its DoD funding to MASSCOMP as well. Immediately thereafter, MASSCOMP merged with the Concurrent Computer Corporation, another leading real-time computing system vendor.

"It's not that I'm so smart, it's just that I stay with problems longer."
-- Albert Einstein

[To Be Continued...

Notes: CCUR’s second generation of Alpha included Clark’s DASA algorithm. SRI did a B3 multilevel secure version of Alpha. TUF’s used to trade off covert timing channel bandwidth (B3 required <100 bps) vs. real-time performance. IBM’s OS/2 for PowerPC included TUF’s (not released). DEC’s Win32-compliant distributed RTOS included TUF’s (not released). Locke's algorithm was subsequently implemented in the Open Software Foundation's MK7.3a real-time OS (which was a merger of the Mach 3 and Alpha OS's) [mk73a]. List TUF work by other authors.

]
 

Back to:

 

Add to Favorites

Print Page

Real-Time:

Motivation and Intro

Real-Time Overview

Time Constraints

Deadlines

Time/Utility Functions

Time Constraints Scopes and Priorities

Sequencing

Sequencing Criteria

Timeliness Optimality

Predictability

Hard and Soft Real-Time

Sequencing Algorithms

Worked Examples

Coastal Air Defense

AWACS Tracker