Deadlock prevention in concurrent real-time systems
Tóm tắt
To meet consistency requirements found in concurrent applications, a process must be guaranteed that it will be able to use all resources in a set ofpassive resources (such as shared data structures). To provide predictable execution time required in real-time systems, a process also needs guaranteed access to at least one of a set ofactive resources (such as processors) associated with each passive resource. As such, a concurrent real-time-process has AND-OR resource requirements. If locking is used to provide exclusive access to resources, deadlock is possible since processes can request additional resources while holding other resources. Deadlock detection and recovery techniques and deadlock avoidance techniques typically involve preempting resources or terminating processes, and are therefore inappropriate for real-time systems that require the execution time of processes to be predictable. This paper describes a general resource request condition that we proveprevents deadlock in AND-OR systems. It also describes how we use this AND-OR deadlock prevention technique in a concurrent real-time system.
Tài liệu tham khảo
Belik, F. 1990. An efficient deadlock avoidance technique.IEEE Transaction on Computers. 39: 882–888.
Chandy, K.M., Misra, J., and Haas, L. 1983. Distributed deadlock detection.ACM Transactions on Computer Systems. 1: 144–1566.
Choudhary, A., Kohler, W.H., Stankovic, J.A., and Towsley, D. 1989. Modified priority based probe for distributed deadlock detection and resolution.IEEE Transactions on Software Engineering. 15: 10–17.
Coffman, E., Elphick, M., and Shoshani, A. 1971. System deadlocks.ACM Computing Surveys, 3: 67–78.
Elmagarmid, A. 1986. A survey of distributed deadlock detection algorithms.SIGMOD Record. 15: 37–45.
Havender, J.W. 1968. Avoiding deadlock in multitasking systems.IBM Systems Journal. 2: 74–84.
Holt, R. 1972. Some deadlock properties of computer systems.ACM Computing Surveys. 4: 179–196.
Knapp, E. 1987. Deadlock detection in distributed databases.ACM Computing Surveys. 19: 304–328.
Misra, J. and Chandy, K.M. 1982. A distributed graph algorithm: knot detection.ACM Transactions on Programming Languages and Systems. 4: 679–686.
Rajkumar, R. 1989.Task Synchronization in Real-Time Systems. Ph.D. thesis, Carnegie Mellon University.
Rosenkrantz, D.J., Stearn, R., and Lewis, P. 1978. System level concurrency control for distributed database systems.ACM Transactions on Database Systems. 3: 178–198.
Sha, L., Rajkumar, R., and Lehoczky, J.P. 1987. Priority inheritance protocols: an approach to real-time synchronization. Tech. Rep. CMU-CX-87-181, Carnegie Mellon University.
Sha, L., Rajkumar, R., Son, S., and Chang, C. 1991. A real-time locking protocol.IEEE Transactions on Computers. 40: 793–800.
Shaw, A. 1974.The Logical Design of Operating Systems. Englewood Cliffs, NJ: Prentice-Hall.
Shih, C. and Stankovic, J.A. 1990. Distributed deadlock detection in Ada runtime environments.ACM SIGADA Ti-Ada Conference.
Stankovic, J. 1988. Misconceptions about real-time computing: a serious problem for next-generation systems.IEEE Computer. 21.
Wolfe, V., Davidson, S., and Lee, I. 1990. Supporting real-time concurrency.7th Workshop on Real-time Operating Systems and Software.
Wolfe, V., Davidson, S., and Lee, I. 1991. RTC: language support for real-time concurrency.Real-Time Systems Symposium. IEEE Computer Society.
Wolfe, V. 1991.Supporting Real-Time Concurrency. Ph.D. thesis, Department of Computer and Information Science, University of Pennsylvania. Available as Technical Report MS-CIS-91-55.