H. Rebecca Callison
Abstract
Process-oriented models for real-time systems focus on the timing constraints of processes, a focus that can adversely affect resulting designs. Data dependencies between processes create scheduling interactions that limit the times at which processes may execute. Processes are then designed to fit available windows in the overall system schedule. “Fitting in” frequently involves fragmenting processes to fit scheduling windows and/or designing program and data structures for speed rather than for program comprehension. The result is often a system with very sensitive timing that is hard to understand and maintain. As an alternative to process-oriented design, we present time-sensitive objects: a data-oriented model for real-time systems. The time-sensitive object (TSO) model structures systems as time-constrained data, rather than time constrained processing. Object values are extended to object histories in which a sequence of time constrained values describe the evolution of the object over time. Systems comprise a set of objects and their dependencies. The TSO model describes the effects of object operations and the propagation of change among related objects. Periodic objects, a class of objects within the TSO model, are described in detail in this article and compared with traditional periodic processes. Advantages of time-sensitive objects are identified, including greater scheduling independence when processes have data dependencies, more opportunity for concurrency, and greater inherent capability for detection of and tolerance to timing errors.
- ~ABBOTT, R. AND GARCIA-MOLINA, H. 1988. Scheduling real-tram transactions' A performance ~evaluation In Proceedings of the 14th International Conference on Very Large Data Bases. ~Morgan Kaufmann, San Mateo, Calif., 1-12. Google Scholar
- ~BIHARI, T., GOP~NATH, P., AND SCHWAN, K. 1989. Object-oriented design of real-time software. ~In Procee&ngs of the Real-Time Systems Symposium IEEE Computer Society Press, Los ~Alamltos, Cahf., 194-201.Google Scholar
- ~CALLISON, H.R. 1991. Time-sensitive objects: A data-oriented approach to real-time systems ~design. TR 91-08-11, Dept. of CSE, Univ. of Washington, Seattle, Wash. Aug.Google Scholar
- ~CALLISON, H. R 1994a. A periodic model for real-time systems. In Proceedings of the Intern,- ~tlonal Conference on So{tware Engzneemng. IEEE Computer Socmty Press, Los Alamitos, ~Calif, 291 300. Google Scholar
- ~CALLISON, H. R. 1994b. Time-sensitive objects: A data-oriented view of real-time systems. ~Ph.D. dissertation, Univ. of Washington, Seattle, Wash. Google Scholar
- ~CHODROW, S. E., JAHANIAN, F. AND DONNER, M. 1991. Run-time monitoring of real-time ~systems. In Proceedings of the Real-Trine Systems Symposmm. IEEE Computer Society Press, ~Los Alamitos, Calif, 74-83Google Scholar
- ~HARITSA, J. R., CAREY, M. J., AND LIVNY, M. 1990. Dynamic real-time optimistic concurrency ~control. In Proceedings of the Real-Tzme Systems Sympostum. IEEE Computer Society Press, ~Los Alamltos, Calif, 94-103Google Scholar
- ~HAmTSA, J. R., LIVNY, M, AND CAREY, M J. 1991. Earliest deadline scheduhng for real-time ~database systems. In Proceedzngs of the iYeal-T~me Systems $ympostum. IEEE Computer ~Society Press, Los Alamltos, Calif., 232-242.Google Scholar
- ~HERHHY, M. 1990. A methodology for implementing highly concurrent data structures. SIG- ~PLAN Not. 25, 3 (Mar), 197-206. Google Scholar
- ~HERLIHY, M. P. AND WING, J.M. 1990. Lineamzability: A correctness condition for concurrent ~objects. ACM Trans. Program. Lang. Syst. 12, 3 (July), 463 492. Google Scholar
- ~HERRTWICH, R.G. 1990. Time capsules: An abstraction for access to continuous-media data. ~In Proceedings of the Real-T~me Systems Symposium. IEEE Computer Society Press, Los ~Alamitos, Calif, 11-20.Google Scholar
- ~HUaNU, J., STANKOVIC, J. A., RAMAMRITHAM, K., AND TOWSLEY, D. 1991. On using priority ~inheritance m real-time databases. In Proceedings of the Real-Time Systems Sympostum ~IEEE Computer Society Press, Los Alamitos, Calif, 210-221Google Scholar
- ~ISHIKAWA, Y., TOKUDA, H., AND MERCER, C.W. 1990. Object-oriented real-time language de- ~sign: Constructs for timing constraints. SIGPLAN Not. 25, 10 (Oct.), 289-298. Google Scholar
- ~KENN~, K. B. AND LIN, K.-J. 1990. Structuring large real-time systems with performance ~polymorphism. In Proceedings of the Real-Time Systems Symposium. IEEE Computer Society ~Press, Los Alamitos, Calif., 238-246.Google Scholar
- ~KOPETZ, H., DAMM, A., KOZA, C., MULAZZANI, M., SCHWABL, W., SENFT, C., AND ZAINLINGER, R. ~1989. Distributed fault-tolerant real-time systems: The Mars approach. IEEE Micro 9, 1 ~(Feb.), 25 40. Google Scholar
- ~KORTI-{, I-I. F., SOPARKAR, S., AND SILBERSCHATZ, A. 1990. Triggered real-time databases with ~consistency constraints. In Proceedings of the 16th International Conference on Very Large ~Data Bases. Morgan Kaufmann, San Mateo, Calif, 71 82. Google Scholar
- ~Kuo, T. AND MOK, A. 1992. Application semantics and concurrency control of real-time data- ~intensive applications. In Proceedzngs of the ReaLTime Systems Symposium. IEEE Computer ~Society Press, Los Alamitos, Calif., 35 45.Google Scholar
- ~KuO, T. AND MOK, A. 1993. SSP: A semantics-based protocol for real-time data access. In ~Proceedings of the Real-Time Systems Symposium. IEEE Computer Society Press, Los Alaml- ~tos, Calif., 76-86.Google Scholar
- ~LEE, I. AND GEHLOT, V. 1985. Language constructs for distributed real-time programming. In ~Proceedings of the Real-Time Systems Symposium. IEEE Computer Society Press, Los Alami- ~tos, Calif., 57-66.Google Scholar
- ~LIN, K.-J. AND LIN, M.-J. 1988. Enhancing availability in distributed real-time databases. ~SIGMOD Rec. 17, i (Mar.), 34-43. Google Scholar
- ~LIN, K.-J. AND NATA~AJAN, S. 1988. Expressing and maintaining timing constraints in Flex. In ~Proceedings of the Real-Tzme Systems Symposium. IEEE Computer Society Press, Los AIami- ~tos, Calif., 96-105Google Scholar
- ~LIN, Y. AND SON, S.H. 1990. Concurrency control in real-time databases by dynamic adjust- ~ment of serialization order. In Proceedzngs of the Real-Time Systems Symposium. IEEE ~Computer Society Press, Los Alamitos, Calif., 104-112.Google Scholar
- ~LIu, J. W. S., LIN, K.-J., SHIn, W.-K., Yu, A. C.-S., CHUN% J.-Y., AND ZHAO, W. 1991. Algo- ~rithms for scheduling imprecise computations. IEEE Comput. 24, 5 (May), 58-68. Google Scholar
- ~LIu, L. Y. AND SHYAMASUNDAR, R.K. 1990. Exception handling in RT-CDL. Comput. Lang. 15, ~3, 1'77-92. Google Scholar
- RAJU, S. C. V., RAJKUMAR, R., AND JAHANIAN, F. 1992. Monitoring timing constraints in ~distributed real-time systems. In Proceedings of the Real-Time Systems Symposn~m. IEEE ~Computer Society Press, Los Alamitos, Calif., 57-67.Google Scholar
- ~SHA, L., RAJKUMAR, R., AND LEHOCZKY, J. P. 1988. Concurrency control for distributed real-time ~databases. SIGMOD Rec. 17, i (Mar), 82-98. Google Scholar
- ~SONG, X. 1992. Data temporal consistency in hard real-time systems. Ph.D. dissertation, Univ. ~of Illinois, Urbana-Champaign, Ill. Google Scholar
- ~SONG, X. AND LIU, J. W.S. 1990. Performance of multiversion concurrency control algorithms ~in maintaining temporal consistency. In Proceedings of COMPSAC. IEEE Computer Society ~Press, Los Alamitos, Calif., 132-139.Google Scholar
Index Terms
- A time-sensitive object model for real-time systems
Recommendations
Supporting predictability in real-time database systems
RTAS '96: Proceedings of the 2nd IEEE Real-Time Technology and Applications Symposium (RTAS '96)Real-time database systems (RTDBSs) have timing constraints in their specifications, such as read times, deadlines and other temporal constraints. In addition, RTDBSs must adapt to changes in the operating environment and guarantee the completion of ...
Dynamic Scheduling of Hard Real-Time Tasks and Real-Time Threads
The authors investigate the dynamic scheduling of tasks with well-defined timing constraints. They present a dynamic uniprocessor scheduling algorithm with an O(n log n) worst-case complexity. The preemptive scheduling performed by the algorithm is ...
Comments