History of the Time/Utility Function, Utility Accrual Paradigm
In 1975, E. Douglas Jensen devised the time/utility function (then called “time/value functions”), utility accrual, paradigm. It was initially intended for scheduling phased array radars. The exemplar case study was the AN/FPQ-16 Perimeter Acquisition Radar portion of the Safeguard anti-ballistic missile system, located in Cavalier (“Concrete”), North Dakota. [srmsc.org][globalsecurity.org] See Figure 1. That radar’s cost/performance was very poor, due in large part to its scheduling algorithm.
Figure 1: AN/FPQ-16 Perimeter Acquisition Radar System
Jensen’s team at Honeywell’s Systems and Research Center performed simulations which indicated that the time/utility function, utility accrual, scheduling paradigm could significantly improve the phased array radar’s cost-effectiveness (those performance results are still classified). This paradigm is briefly mentioned in an unclassified document for the Ballistic Missile Defense Advanced Technology Center [Jensen 77, Kain 77].
The entire Safeguard system was overtaken by political events and technological progress (e.g., the emergence of MIRV technology), and decommissioned in 1976. Consequently, his time/utility function scheduler was not deployed for that radar. (It has been implemented recently in far more difficult to schedule AESA radars, and other classified military systems such as combat platform management and battle management.)
Research on time/utility functions and utility accrual algorithms resumed in 1983, as part of Jensen’s Archons Project [Jensen 83] after he joined the faculty of the Computer Science Department at Carnegie Mellon University.
The seminal public paper about time/utility functions (then called “time/value functions”) was published in the 1985 Real-Time Systems Symposium by Jensen and two of his Ph.D. students, Douglas Locke, and Hide Tokuda [Jensen 85], and is his most-cited professional publication.
Then two of Jensen’s Ph.D. students wrote the first theses on this topic: Douglas Locke [Locke 86], and Raymond Clark [Clark 90].
The algorithm in 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 tasks; it also out-performed Locke’s in most cases. However, it was limited to certain downward step (i.e., deadline) functions, and á priori known timeliness properties.
Locke’s algorithm was implemented in our Alpha real-time operating system kernel [Northcutt 87, Clark et al. 93]. Clark’s algorithm was subsequently implemented as one of the optional scheduling policies in the Open Software Foundation‘s * OSF/1 ** operating system MK7.3a kernel (discussed below).
Jensen desired to transition the Alpha keystone technologies—distributed threads [ ] and time/utility function, utility accrual, scheduling—into industry. In 1987, he took a half-time leave of absence from CMU CS, and became employee 11 at a startup named Kendall Square Research (KSR), in Cambridge, MA. KSR intended that Alpha’s keystone technologies be integrated into their version of the Open Software Foundation’s OSF/1 operating system for its KSR-1 supercomputer. Some DoD funding for continued research on a second generation Alpha kernel moved with Jensen to KSR.
(As discussed below, that integration did not happen at KSR, but it did subsequently happen at the Open Software Foundation Research Institute (OSF/RI) [ ] and at IBM. The OSF/1 OS available to OSF members used a version of the CMU Mach *** 2.5 kernel. The OSF/RI, funded in part by DARPA, developed the enhanced MK7.3a [Reynolds 98] kernel based on a combination of their modified Mach 3 kernel plus the Alpha kernel’s distributed thread abstraction and a framework for user-pluggable scheduling policies [ ], including Clark’s TUF/UA algorithm.)
The KSR hardware was unexpectedly slow to materialize, so Jensen had to seek an alternative COTS real-time multiprocessor product on which to develop the second generation of the Alpha kernel. There were few choices, and Jensen selected a product from MASSCOMP, a leading real-time computing systems vendor, in part because MASSCOMP was fortunately located in the Boston area.
In 1988 KSR decided to move away from real-time and scientific applications toward commercial data processing.
MASSCOMP was acquiring the Concurrent Computer Corporation (but retaining the Concurrent name), becoming the largest U.S. real-time computer company. They recruited Jensen to be their Chief Scientist. He resigned from his CMU CS faculty position, and moved the Alpha project to Concurrent (nèe MASSCOMP). He sought and received new DoD funding there, and recruited a team, partially from his former CMU research project members and partially of new people, to do the research and development of a second version of the Alpha kernel for an anticipated distributed real-time OS product. Before that OS could finish being developed on the Alpha version 2 kernel, the MASSCOMP/Concurrent merger became a total managerial and financial failure. In 1990 all-new executive management closed the former MASSCOMP facility (retaining the New Jersey facility the pre-merger Concurrent occupied).
Jensen and his Alpha team members then moved to two other Boston area organizations which collaborated with each other and with a third enterprise to continue work on the commercial transition of the Alpha kernel technologies (as described below).
From Concurrent, Jensen then became the Technical Director of Digital Equipment Corporation’s (DEC) embedded and real-time business unit. One of his projects was collaboration with the OSF/RI (DEC was a member of the OSF) on integrating the Alpha kernel keystone technologies into their own revision of the CMU CS Mach 3 kernel for the OSF/1 OS (which DEC intended to use). Another project was for DEC’s Alpha staff to collaborate with IBM (a member of the OSF) on a similar integration of a Mach 3 and Alpha integration as part of their Workplace OS project. These projects are discussed next.
Some of Jensen’s former Alpha colleagues from CMU and Concurrent went to the OSF/RI. Among his projects at DEC was collaborating with the OSF/RI on transitioning the Alpha kernel distributed threads abstraction and TUF/UA scheduling paradigm to their OSF/1 operating system kernel derived from Mach 3. That resulted in a new kernel being an integration of Alpha’s native distributed threads and pluggable scheduling algorithms, including Clark’s TUF/UA algorithm, into a version of the Mach 3 kernel. The final OSF/RI version of the new kernel was named MK7.3a [Reynolds 98]. That integration was funded in part by DARPA.
[To be continued … DEC collaborates with IBM to incorporate the Alpha kernel keystone technologies into an MK7.3a-like kernel for OS/2 and . An NSA Orange Book B3 level multilevel security version of Alpha was produced by SRI with collaboration by DEC and OSF, and productized by . More… MITRE and VA Tech]
* The Wikipedia page about the Open Software Foundation has a number of important errors and omissions.
** The Wikipedia page containing information about OSF/1 has a number of important errors and omissions.
*** The Wikipedia page about the Mach microkernel has important errors and omissions.
Next: References