Time-utility function

A Time/Utility Function (TUF), née Time/Value Function, specifies the application-specific utility that an action (e.g., task, mechanical movement) yields depending on its completion time.[1][2] TUFs and their utility interpretations (semantics), scales, and values are derived from application domain-specific subject matter knowledge. A frequent interpretation of utility is an action's relative importance, which is orthogonal to its urgency. The traditional deadline represented as a TUF is a special case—a downward step of values from 1 to 0 at the deadline time—i.e., urgency without importance. A TUF is more general—it has a critical time, with application-specific shapes and values on each side, after which it does not increase.

The optimality criterion for scheduling multiple TUFs historically has been solely maximal utility accrual (UA)—e.g., a (perhaps expected) sum of the individual actions' completion utilities. This thus takes into account timeliness with respect to critical times. Additional criteria (e.g., energy, predictability), constraints (e.g., dependencies), system models, scheduling algorithms, and assurances have been added as the TUF/UA paradigm and its use cases have evolved. More expressively, TUF/UA can be used where timeliness, accrued utility, and other scheduling criteria may be traded off against one another for the schedule to yield situational application QoS, as opposed to only timeliness per se.

Various published examples of civilian TUF/UA applications are included in the References.

Time/Utility Functions

The TUF/UA paradigm was originally created to address certain timeliness- and application QoS-based scheduling needs of various military applications for which traditional real-time concepts and practices are not sufficiently expressive (e.g., for timeliness-critical systems not having deadlines) and resilient (e.g., for systems subject to routine overloads). An example class of such applications is ballistic missile defense (notionally[3][4][5]).

Subsequently, numerous variations on the original TUF model, the TUF/UA paradigm’s system model, and thus scheduling algorithms, have been studied in the academic literature—e.g.,[6][7][8][9][10]—and applied in civilian contexts.

Some examples of the latter include: cyber-physical systems,[11] AI,[12] multi-robot systems,[13] drone scheduling,[14] autonomous robots,[15] intelligent vehicle-to-cloud data transfers,[16] industrial process control,[17] transaction systems,[18] high performance computing,[19] cloud systems,[20] heterogeneous clusters,[21] service-oriented computing,[22] networking [23][24] and memory management.[25][26] A steel mill example is briefly described in the Introduction of Clark's Ph.D. thesis.[27] Information about any commercial or military instances of the paradigm may be publicly inaccessible (proprietary or classified, respectively).

TUFs and their utility interpretations (semantics), scales, and values are derived from domain-specific subject matter knowledge.[28][5] A frequent generic interpretation of utility is actions' relative importance.[lower-alpha 1] A framework for á priori assigning static utility values subject to strong constraints on system models has been devised,[8] but subsequent (like prior) TUF/UA research and development have preferred to exploit application-specificity rather than attempting to create more general frameworks. However, such frameworks and tools remain an important research topic.

By convention, a TUF is a (strictly) concave function, including linear ones.

TUF/UA papers in the research literature, with few exceptions, e.g.,[29][6][30][31][8][10] are for only either linear or piecewise linear[32] (including conventional deadline-based) TUFs because they are easier to specify and schedule. In many cases, the TUFs are only monotonically decreasing.

A constant TUF represents an action's utility that is not related to the action's completion time—for example, the action's relative importance. An arbitrary critical time may be chosen for the purpose of scheduling—such as the action's release time, or its TUF's terminal time. This allows both time-dependent and time-independent actions to be scheduled coherently.

A (non-constant) TUF has a global critical time, after which its utility does not increase. If a (non-constant) TUF never decreases, its global critical time is the first time when its maximum utility is reached. The global critical time may be followed by local critical times[2]—for example, consider a TUF having a sequence of downward steps in value, perhaps to approximate a smooth downward curve.[lower-alpha 2]

TUF utility values usually are either integers or rational numbers.

TUF utility may include negative values. (A TUF that has negative values in its range is not necessarily dropped from scheduling consideration or aborted during its operation—that decision depends on the scheduling algorithm.)

A conventional deadline time (d) represented as a TUF is a special case—a downward step TUF[lower-alpha 3] having a unit penalty (i.e., having utility values 1 before and 0 after its critical time).

More generally, a TUF allows downward (and upward) step functions to have any pre- and post-critical time utilities.

Tardiness[33] represented as a TUF is a special case whose non-zero utility is the linear function C - d, where C is the function's completion time—either current, expected, or currently believed.[lower-alpha 4] More generally, a TUF allows non-zero earliness and tardiness to be non-linear—e.g., increasing tardiness may result in non-linearly decreasing utility (greater "penalty" or "cost"), such as when detecting a threat.

Thus, TUFs provide a rich generalization of traditional action completion time constraints in real-time computing.

Alternatively, the TUF/UA paradigm can be employed to use timeliness as a means to a utility accrual (i.e., application QoS) end, instead of timeliness per se being an end in itself (see below).

A TUF (its shape and values) may be dynamically adapted by an application or its operational environment,[2] independently for any actions currently either waiting or operating.[lower-alpha 5] These adaptations may occur either at discrete events—e.g., at an application mode change such as for ballistic missile flight phases,[5] or continuously such as for air-to-air radar tracking where some actions’ operational durations and utilities are a function of when those actions begin operation.[34][lower-alpha 6]

Utility Accrual Scheduling

INCOMPLETE DRAFT OF WORK IN PROGRESS

This section begins by listing generic properties of TUF/UA scheduling, then summarizes a number of notable specific cases of UA research in the public literature.

Generic Properties of UA Scheduling

Multiple actions in a system may contend for access to sequentially shared resources—physical ones such as processors, networks, exogenous application devices (sensors, actuators, etc.)—and logical ones such as synchronizers, data.

The TUF/UA paradigm resolves each instance of this contention using an application-specific algorithmic technique which creates a schedule. The instance’s contending actions are dispatched for resource access in order from the front of the schedule. Thus, action sequencing is not greedy.[lower-alpha 7]

A schedule may be created offline (i.e., prior to system operation) or online (i.e., during system operation). An online schedule may be either static or dynamic (discussed below). An online schedule may be either pre-emptive or non-preemptive. Offline schedules are static and non-preemptive.

The algorithmic technique creates a schedule having one or more application-specific objectives.

The primary objective for scheduling actions having TUFs is maximal utility accrual (UA). The accrued utility is an application-specific polynomial sum of the schedule’s completed actions’ utilities. When actions have one or more stochastic parameters (e.g., operation duration), the accrued utility is also stochastic (i.e., an expected polynomial sum).

Notable Examples of UA Scheduling Research


Notes
  1. Scheduling based on importance is not the same as greedy dispatching based on importance.
  2. this is more general than Locke's introduction of the term critical time in Locke 86.
  3. There is a discontinuity in either the function or its first or second derivative.
  4. For example, Dempster-Shafer Theory may be used for certain system models having epistemic uncertainties.
  5. Operating is used as the general case to include non-computational (e.g., mechanical) actions as well as computational tasks that execute.
  6. This case is a subfield of modern scheduling theory called time-dependent scheduling, vs. classical (fixed execution times) scheduling[35][36], particularly job alteration for applications such as air-to-air radar tracking.
  7. Some UA schedulers may remove an overload in a greedy manner—cf. 7.5.1 in Locke 86.
gollark: Oh, because more dimension → more good.
gollark: What?
gollark: I plotted its good\*ness in *3D*.
gollark: It's good*, actually.
gollark: GTech™ random number generator (good*).

See also

References
  1. E. Douglas Jensen, C. Douglas Locke, and Hideyuki Tokuda. A Time-Value Driven Scheduling Model for Real-Time Operating Systems, Proc. Symposium on Real-Time Systems, IEEE, 1985.
  2. E. Douglas Jensen. A Timeliness Model for Asynchronous Decentralized Computer Systems, Proc. International Symposium on Autonomous Decentralized Systems, IEEE, 1993
  3. E. Douglas Jensen. Chapter 3 Radar Scheduling, Section 1 The Scheduling Problem in Gouda+ 77 (unclassified version).
  4. Mohamed G. Gouda, Yi-Wu Han, E. Douglas Jensen, Wesley D. Johnson, Richard Y. Kain (Editor). Distributed Data Processing Technology, Vol. IV, Applications of DDP Technology to BMD: Architectures and Algorithms, unclassified version, Defense Technical Information Center a047477, Honeywell Systems and Research Center, Minneapolis, MN, 1977.
  5. David P. Maynard, Samuel E. Shipman, Raymond K. Clark, J. Duane Northcutt, E. Douglas Jensen, Russell B. Kegley, Betsy A. Zimmerman, Peter J. Keleher. An Example Real-Time Battle Management Command and Control Application for Alpha, Section 8.2.1, Archons Project Technical Report, 1988, and public version 2008.
  6. Binoy Ravindran, E. Douglas Jensen, and Peng Li. On Recent Advances in Time/Utility Function Real-Time Scheduling and Resource Management, Proc. Eighth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing, 2005.
  7. Saud A. Aldami and Alan Burns. Dynamic Value-Density for Scheduling Real-Time Systems, Proc. 11th Euromicro Conference on Real-Time Systems, IEEE, 1999.
  8. Alan Burns, D. Prasad, A. Bondavalli, F. Di Giandomenico, K. Ramamritham, J. Stankovic, L. Strigini. The meaning and role of value in scheduling flexible real-time systems, Journal of Systems Architecture, Elsivier, 2000.
  9. Divya Prasad, Alan Burns, and Martin Atkins. The Valid Use of Utility in Adaptive Real-Time Systems. Real-Time Systems, Kluwer, 2003.
  10. Ken Chen and Paul Muhlethaler. A Family of Scheduling Algorithms for Real-Time Systems Using Time Value Functions. Real-Time Systems, vol. 10 no. 3, Kluwer, 1996.
  11. Terry Tidwell, Robert Glaubius, Christopher D. Gill and William D. Smart. Optimizing Expected Time Utility in Cyber-Physical Systems Schedulers, Proc. IEEE Real-Time Systems Symposium, 2010.
  12. Yagil Ronén, Daniel Mossé, and Martha E. Pollack. Value-Density Algorithms for the Deliberation-Scheduling Problem, ACM SIGART Bulletin, Volume 7 Issue 2, 1996.
  13. Michał Barcís, Agata Barcís, and Hermann Hellwagner. An Evaluation Model for Information Distribution in Multi-Robot Systems, Sensors, January 2020.
  14. Shireen Seakhoa-King, Paul Balaji, Nicolas Trama Alvarez, and William J. Knottenbelt. Revenue-Driven Scheduling in Drone Delivery Networks with Time-Sensitive Service Level Agreements, Proc. 12th EAI International Conference on Performance Evaluation Methodologies and Tools, ACM, 2019.
  15. Aldis Baums. Automatic Control and Computer Sciences, Vol. 46, No. 6, Allerton Press, 2012.
  16. Jean Ibarz, Michaël Lauer, Matthieu Roy, Jean-Charles Fabre, Olivier Flébus. Optimizing Vehicle-to-Cloud Data Transfers using Soft Real-Time Scheduling Concepts, Proc. 28th International Conference on Real-Time Networks and Systems, ACM, 2020.
  17. Rutger Habets. Improving the line performance of packaging line 41 at Heineken Zoeterwoude, Bachelor of Science project thesis, Industrial Engineering and Management, University of Twente, 2019.
  18. Jayant R. Haritsa, Jayant R., Michael J. Carey, and Miron Livney. Value-Based Scheduling in Real-Time Databases, VLDB Journal, 2 (2) 1993.
  19. Luis Diego Briceño, Bhavesh Khemka, Howard Jay Siegel, Anthony A. Maciejewski, Christopher Groër, Gregory Koenig, Gene Okonski, and Steve Poole. Time Utility Functions for Modeling and Evaluating Resource Allocations in a Heterogeneous Computing System, Proc. IEEE International Symposium on Parallel and Distributed Processing, 2011.
  20. Cihan Tunc, Nirmal Kumbhare, Ali Akoglu, Salim Hariri, Dylan Machovec, Howard Jay Siegel. Value of Service Based Task Scheduling for Cloud Computing Systems, Proc. International Conference on Cloud and Autonomic Computing, 2016.
  21. Vignesh T. Ravi1, Michela Becchi2, Gagan Agrawal1, and Srimat Chakradhar. ValuePack: Value-Based Scheduling Framework for CPU-GPU Clusters, Proc. IEEE International Conference on High Performance Computing, Networking, Storage and Analysis, 2012.
  22. Alvin AuYoung, Laura Grit, Janet Wiener, John Wilkes. Service contracts and aggregate utility functions, Proc. 15th IEEE International Symposium on High Performance Distributed Computing, 2006.
  23. Jinggang Wang and Binoy Ravindran. Time-Utility Function-Driven Switched Ethernet: Packet Scheduling Algorithm, Implementation, and Feasibility Analysis, IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 2, February 2004.
  24. Michael D. Theys, Howard Jay Siegel, and Edwin K. P. Chong. Heuristics for Scheduling Data Requests Using Collective Communications in a Distributed Communication Network, Journal of Parallel and Distributed Computing 61, 1337- 1366, 2001.
  25. Hyeonjoong Cho, Binoy Ravindran, Chewoo Na. Garbage Collector Scheduling in Dynamic, Multiprocessor Real-Time Systems, IEEE Transactions on Parallel and Distributed Systems 20(6), June 2009.
  26. Shahrooz Feizabadi and Godmar Back. Garbage collection-aware utility accrual scheduling, Real-Time Systems Journal, July 2007, Volume 36, Issue 1–2, 2007.
  27. Raymond K. Clark. Scheduling Dependent Real-Time Activities, Ph.D. Dissertation, CMU-CS-90-155, Computer Science Department, Carnegie Mellon Univ., 1990.
  28. Raymond K. Clark, E. Douglas Jensen, Arkady Kanevsky, John Maurer, Paul Wallace, Tom Wheeler, Yun Zhang, Douglas M. Wells, Tom Lawrence, and Pat Hurley. An Adaptive, Distributed Airborne Tracking System, IEEE Parallel and Distributed Real-Time Systems, volume 1586 of LNCS, Springer-Verlag, 1999.
  29. C. Douglas Locke. Best-Effort Decision Making for Real-Time Scheduling, Ph.D. Thesis CMU-CS-86-134, Computer Science Department, Carnegie-Mellon University, 1986.
  30. Peng Li. Utility Accrual Real-Time Scheduling: Models and Algorithms, Ph.D. dissertation, Virginia Polytechnic Institute and State University, 2004.
  31. Peng Li, Haisang Wu, Binoy Ravindran, and E. Douglas Jensen. A Utility Accrual Scheduling Algorithm for Real-Time Activities with Mutual Exclusion Resource Constraints, IEEE Transactions on Computers, vol. 55, no. 4, April 2006.
  32. Zhishan Guo and Sanjoy Buruah. A Neurodynamic Approach for Real-Time Scheduling via Maximizing Piecewise Linear Utility, IEEE Transactions on Neural Networks and Learning Systems, vol. 27 no. 2, February 2016.
  33. Jeremy P. Erickson. Managing Tardiness Bounds and Overload in Soft Real-Time Systems, Ph.D. dissertation, University of North Carolina, 2014.
  34. Umut Balli, Haisang Wu, Binoy Ravindran, Jonathan Stephen Anderson, E. Douglas Jensen. Utility Accrual Real-Time Scheduling under Variable Cost Functions, IEEE Transactions on Computers, Volume 56, Number 3, March 2007.
  35. Stanislaw Gawiejnowicz. A review of four decades of time-dependent scheduling: main results, new topics, and open problems, Journal of Scheduling 23, 3–47, Springer, 2020.
  36. Stanislaw Gawiejnowicz. Models and Algorithms of Time-Dependent Scheduling, 2nd ed., eBook ISBN 978-3-662-59362-2, Springer, 2020.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.