Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

In the design of highly complex, heterogeneous, and concurrent systems, deadlock detection and resolution remains an important issue. In this paper, we systematically analyze the synchronization dependencies in concurrent systems modeled in the Metropolis design environment, where system functions, high level architectures and function-architecture mappings can be modeled and simulated. We propose a data structure called the dynamic synchronization dependency graph, which captures the runtime (blocking) dependencies. A loop-detection algorithm is then used to detect deadlocks and help designers quickly isolate and identify modeling errors that cause the deadlock problems. We demonstrate our approach through a real world design example, which is a complex functional model for video processing and a high level model of function-architecture mapping.

REFERENCES

• 1: http://www.eda.org/vfv, 2003.
• 2: Felice Balarin , Jerry Burch , Luciano Lavagno , Yosinori Watanabe , Roberto Passerone , Alberto Sangiovanni-Vincentelli, Constraints Specification at Higher Levels of Abstraction, Proceedings of the Sixth IEEE International High-Level Design Validation and Test Workshop (HLDVT'01), p.129, December 07-09, 2001
• 3: Felice Balarin , Yosinori Watanabe , Harry Hsieh , Luciano Lavagno , Claudio Passerone , Alberto Sangiovanni-Vincentelli, Metropolis: An Integrated Electronic System Design Environment, Computer, v.36 n.4, p.45-52, April 2003 [doi>10.1109/MC.2003.1193228]
• 4: Arthur Charlesworth, The multiway rendezvous, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.350-366, July 1987 [doi>10.1145/24039.24050]
• 5: E. G. Coffman , M. Elphick , A. Shoshani, System Deadlocks, ACM Computing Surveys (CSUR), v.3 n.2, p.67-78, June 1971 [doi>10.1145/356586.356588]
• 6: Om Prakash Gangwal , André Nieuwland , Paul Lippens, A scalable and flexible data synchronization scheme for embedded HW-SW shared-memory systems, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada [doi>10.1145/500001.500003]
• 7: Patrice Godefroid , Didier Pirottin, Refining Dependencies Improves Partial-Order Verification Methods (Extended Abstract), Proceedings of the 5th International Conference on Computer Aided Verification, p.438-449, June 28-July 01, 1993
• 8: A. N. Habermann, Prevention of system deadlocks, Communications of the ACM, v.12 n.7, p.373-ff., July 1969 [doi>10.1145/363156.363160]
• 9: C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
• 10: Gerard J. Holzmann, The Model Checker SPIN, IEEE Transactions on Software Engineering, v.23 n.5, p.279-295, May 1997 [doi>10.1109/32.588521]
• 11: K. Keutzer, S. Malik, A. R. Newton, J. Rabaey, and A. Sangiovanni-Vincentelli. System level design: orthogonalization of concerns and platform-based design. IEEE Transactions on Computer-Aided Design, 19(12):1523--1543, Dec. 2000.
• 12: Edgar Knapp, Deadlock detection in distributed databases, ACM Computing Surveys (CSUR), v.19 n.4, p.303-328, Dec. 1987 [doi>10.1145/45075.46163]
• 13: Murali Krishnamurthi , Amar Basavatia , Sanjeev Thallikar, Deadlock detection and resolution in simulation models, Proceedings of the 26th conference on Winter simulation, p.708-715, December 11-14, 1994, Orlando, Florida, United States
• 14: Zohar Manna , Amir Pnueli, The temporal logic of reactive and concurrent systems, Springer-Verlag New York, Inc., New York, NY, 1992
• 15: Kenneth L. McMillan, Symbolic Model Checking, Kluwer Academic Publishers, Norwell, MA, 1993
• 16: J. L. Peterson and A. Silbershatz. Operating System Concepts. Addison-Wesley, 1983.
• 17: M. Sfinghal, Deadlock Detection in Distributed Systems, Computer, v.22 n.11, p.37-48, November 1989 [doi>10.1109/2.43525]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Monitors

General Terms:
Verification

Keywords:
cyclic dependency, deadlock, metropolis, simulation, synchronization, system level