Compile-time analysis of communicating processes

ABSTRACT

We present an algorithm for analyzing deadlock and for constructing sequentializations of a class of communicating sequential processes. The algorithm may be used for deadlock detection in parallel and distributed programs at compile time, or for debugging purposes at run time. The algorithm generates a data structure we call the flow graph, which contains all you need to know about the communications between the processes. If the algorithm is used only for debugging, it is not necessary to retain a copy of the flow graph. Both static deadlock analysis and trace generation are linear in the size of the (minimum) flow graph we construct.

REFERENCES

• Apt83: K. R. Apt, A Static Analysis o} CSP Programs, Logic~ of Programs, Lecture Notca in Computer Science 164, Springer-Verl~g, 1983, 1- 17.
• CunSny87: Janice E. Cuny , Lawrence Snyder, Conversion from data-driven to synchronous execution in loop programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.599-617, Oct. 1987 [doi>10.1145/29873.31334]
• HatPir88: Derek J. Hatley , Imtiaz A. Pirbhai, Strategies for real-time system specification, Dorset House Publishing Co., Inc., New York, NY, 1987
• Hoa78: 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]
• Hoa85: C. A. R. Hoare, Communicating sequential processes, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• Hol72: Richard C. Holt, Some Deadlock Properties of Computer Systems, ACM Computing Surveys (CSUR), v.4 n.3, p.179-196, Sept. 1972 [doi>10.1145/356603.356607]
• ISO88: LOTOS - A Formal Descr@tion Technique Based on the Temporal Ordering o} Observational Behaviour, DIS 8807, International Standards Org~nis~tion 1988.
• Jac86: M. A Jackson, System development (Prentice-Hall International series in computer science), Prentice-Hall, Inc., Upper Saddle River, NJ, 1983
• Jon87: Geraint Jones, Programming in Occam, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1986
• LadSim91: P. B. Ladkin and B. B. Simons, Compile- Time Analysis of Communicating Processes, IBM RJ 8488, Nov. 20, 1991.
• LadSim92: P. B. Ladldn and B. B. Simons, Static Analysis of Concurrent Communicating Loops, IBM RJ 8625, February 12, 1992.
• LadSim9x: P. B. Ladkin and B. B. Simons, The Flow Graph for Loop Processes using n-way Rendezvous, IBM RJ, to ~ppear.
• Lam90: Correspondence on the concurrency mailing fist, 1990.
• Mer90: N. Mercouroff, An Algorithm }or Analyzing Communicating Processes, technical report LIX/RR/90/12, Ecole Polytechnique, Laboratoire d'Inform~tique, Pala.iseau Cedex, France.
• ReiSmo90: John H. Reif , Scott A. Smolka, Data flow analysis of distributed communicating processes, International Journal of Parallel Programming, v.19 n.1, p.1-30, Feb. 1990 [doi>10.1007/BF01407862]
• Sch90: Fred B. Schneider , Richard Conway , Dale Skeen, Thrifty execution of task pipelines, Acta Informatica, v.22 n.1, p.35-45, April 1985 [doi>10.1007/BF00290144]
• SiAlFe90: B. Simons , D. Alpern , J. Ferrante, A foundation for sequentializing parallel code, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.350-359, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97702]
• Sim9x: B. Simons, A Polynomial Time Algorithm }or Compile-Time Deadlock Analysis when the Communication Graph is a Tree, to appear.
• SiPeGa91: Abraham Silberschatz , James L. Peterson , Peter B. Galvin, Operating system concepts (3rd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• SriHoa85: N. Sridhar and C.A.R. Hoare, JSD Expressed in CSP, in J. Cameron (ed.), JSP and JSD: The Jackson Approach to Software Development, 334-363, IEEE Computer Society Press 1989; also Oxford University Programming Research Group Technical Moztograph PRG-51, 1985.
• Tay83: Richard N. Taylor, A general-purpose algorithm for analyzing concurrent programs, Communications of the ACM, v.26 n.5, p.361-376, May 1983 [doi>10.1145/69586.69587]
• Val90: Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]
• WarMel85: Paul T. Ward , Stephen J. Mellor, Structured Development for Real-Time Systems, Prentice Hall Professional Technical Reference, 1991
• XuPar91: Jia Xu , David Lorge Parnas, On satisfying timing constraints in hard-real-time systems, Proceedings of the conference on Software for citical systems, p.132-146, December 04-06, 1991, New Orleans, Louisiana, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Distributed systems

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Performance