Abstract
Real-time systems that must adapt their behavior to changes in internal and external circumstances require flexibility in their scheduling. One approach that has been advocated for achieving this flexibility is called “value-based” scheduling, wherein services are distinguished based upon their current utility values. The main result of this paper is that the assumptions used in the assignment of these values must be matched with the way the values are used in scheduling. The key notion for ensuring this is the “scale type” of the value, in the sense defined by measurement theory. There are simple tests for “meaningful” uses of values based on their scale types, and we apply these tests to investigate the meaningfulness requirements of some commonly-used scheduling approaches.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
AEEC. 1991. ARINC 651: Design Guidance for Integrated Mondular Avionics. Airlines Electronic Engineering Committee, draft edition.
Biyabani, S., Stankovic, J., and Ramamritham, K. 1988. The integration of criticalness and deadlines in scheduling real-time tasks. In Proceedings of the 9th IEEE Real-Time Systems Symposium, pp. 152–169.
Bums, A., and Prasad, D. 1998. Value-based scheduling of flexible real-time systems for intelligent autonomous vehicle control. In M. Salichs and A. Halme (eds.), Proceedings of the 3rd IFAC Symposium on Intelligent Autonomous Vehicles. Madrid, Spain, pp. 127–132.
Burns, A., Prasad, D., Bondavalli, A., Giandomenico, F. D., Ramamritham, K., Stankovic, J., and Strigini, L. 2000. The meaning and role of value in scheduling flexible real-time systems. Journal of Systems Architecture, 46: 305–325.
Burns, A., and Wellings, A. 2001. Real-Time Systems and Programming Languages: Ada 95, Real-Time Java and Real-Time POSIX, 3rd edition, Addison Wesley Longmain.
Buttazzo, G., and Stankovic, J. 1993. RED: A robust earliest deadline scheduling algorithm. In Proceedings of the 3rd International Workshop on Responsive Computer Systems. Austin.
Davis, R. 1995. On exploiting spare capacity in hard real-time systems. Ph.D. thesis, University of York, Department of Computer Science, Ph.D. Thesis.
Davis, R., Punnekkat, S., Audsley, N., and Burns, A. 1995. Flexible scheduling for adaptable real-time systems. In IEEE Real-Time Technology and Applications Symposium, pp. 230–239.
Huang, J., Stankovic, J., Towsley, D., and Ramamritham, K. 1989. Experimental evaluation of real-time transaction processing. In Proceedings of the 10th IEEE Real-Time Systems Symposium, pp. 144–153.
Jensen, E., Locke, C. and Tokuda, H. 1986. A time driven scheduling model for real-time operating systems. In Proceedings IEEE Real-Time Systems Symposium, pp. 112–122.
Krantz, D., Luce, R., Suppes, P., and Tversky, A. 1971. Foundations of Measurement: Additive and Polynomial Representations, Vol. 1. New York, Academic Press.
Locke C. 1986. Best effort decision making for real-time scheduling. Ph.D. Thesis, Computer Science Department, CMU. Ph.D. Thesis, CMU-CS-86–13.
Prasad, D. 1998. Dependable systems integration using measurement theory and decision analysis. Ph.D. Thesis, Department of Computer Science, University of York, UK.
Prasad, D., and Burns, A. 2000. A value-based scheduling approach for real-time autonomous vehicle control. Robotica 18.
Roberts, F. 1979. Measurement Theory, with Applications to Decision-making, Utility and the Social Sciences. Reading, MA: Addison Wesley.
Saaty, T. 1992. Multiple Criteria Decision Making: The Analytic Hierarchy Process. Pitssburgh, PA: RWS Publications.
Tokuda, H., Wendorf, J., and Wang, H. 1987. Implementation of a time-driven scheduler for real-time operating systems. Proceedings of IEEE Rea-Time Systems Symposium, pp. 271–280.
Wendorf, J. 1988. Implementation and evaluation of a time-driven scheduling processor. Proceedings of IEEE Real-Time Systems Symposium, pp. 172–180.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Prasad, D., Burns, A. & Atkins, M. The Valid Use of Utility in Adaptive Real-Time Systems. Real-Time Systems 25, 277–296 (2003). https://doi.org/10.1023/A:1025184411567
Issue Date:
DOI: https://doi.org/10.1023/A:1025184411567