Debugging concurrent programs

ABSTRACT

The main problems associated with debugging concurrent programs are increased complexity, the "probe effect," nonrepeatability, and the lack of a synchronized global clock. The probe effect refers to the fact that any attempt to observe the behavior of a distributed system may change the behavior of that system. For some parallel programs, different executions with the same data will result in different results even without any attempt to observe the behavior. Even when the behavior can be observed, in many systems the lack of a synchronized global clock makes the results of the observation difficult to interpret. This paper discusses these and other problems related to debugging concurrent programs and presents a survey of current techniques used in debugging concurrent programs. Systems using three general techniques are described: traditional or breakpoint style debuggers, event monitoring systems, and static analysis systems. In addition, techniques for limiting, organizing, and displaying a large amount of data produced by the debugging systems are discussed.

REFERENCES

• ABKP86: ALLEN, R., BAUMGARTNER, D., KEN- NEDY, K., AND PORTERFIELD, A. 1986. Ptooh A semiautomatic parallel programming assistant. In Proceedings of the International Conference on Parallel Processing. IEEE, pp. 164-170.
• AG88: Ziya Aral , Ilya Gertner, High-level debugging in parasight, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.151-162, May 05-06, 1988, Madison, Wisconsin, United States
• AM85: APPELBE, W.F.,AND McDOWELL, C.E. 1985. Anomaly reporting: A tool for debugging and developing parallel numerical algorithms. In Proceedings of the 1st International Conference on Supercomputing Systems. IEEE, pp. 386-391.
• AM86: E Adams , S S Muchnick, Dbxtool: A window-based symbolic debugger for sun workstations, Software—Practice & Experience, v.16 n.7, p.653-669, July. 1986 [doi>10.1002/spe.4380160705]
• AM88: B. Appelbe , C. E. McDowell, Developing multitasking applications programs, Proceedings of the Twenty-First Annual Hawaii International Conference on Software Track, p.94-102, January 1988, Kailua-Kona, Hawaii, United States
• AP87: ALLEN, T. R., AND PADUA, D. A. 1987. Debugging FORTRAN on a shared memory machine. In Proceedings of the International Conference on Parallel Processing. Penn State University, pp. 721-727.
• Bat88: Peter Bates, Debugging heterogeneous distributed systems using event-based models of behavior, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.11-22, May 05-06, 1988, Madison, Wisconsin, United States
• BCKT79: BANERJEE, U., CHEN, S., KUCK, D. J., AND TOWLE, R. A. 1979. Time and parallel processor bounds for fortran-like loops. IEEE Trans. Comput. 28, 9 (Sept.), 660-670.
• BDER79a: G. Bristow , C. Drey , B. Edwards , W. Riddle, Anomaly detection in concurrent programs, Proceedings of the 4th international conference on Software engineering, p.265-273, September 17-19, 1979, Munich, Germany
• BDER79b: BRISTOW, G., DREY, C., EOWAROS, B., AND RIDDLE, W. 1979. Design of a system for anomaly detection in HAL/S programs. Tech. Rep. CU-CS-151-79. Univ. of Colorado at Boulder.
• BDV86: F Baiardi , N DeFrancesco , G Vaglini, Development of a debugger for a concurrent language, IEEE Transactions on Software Engineering, v.12 n.4, p.547-553, April 1986
• BW83: BATES, P. C., AND WILEDEN, J. C. 1983. High-level debugging of distributed systems: The behavioral abstraction approach. J. Syst. Softw. 3, 255-264. Also COINS Tech. Rep. 683-29.
• CL85: K. Mani Chandy , Leslie Lamport, Distributed snapshots: determining global states of distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.63-75, Feb. 1985 [doi>10.1145/214451.214456]
• Coo87: COOPER, R. 1987. Pilgram: A debugger for distributed systems. In Proceedings of the 7th International Conference on Distributed Computing Systems. IEEE, pp. 458-465.
• CP86: Paolo Corsini , Cosimo Antonio Prete, Multibug: Interactive debugging in distributed systems, IEEE Micro, v.6 n.3, p.26-33, June 1986 [doi>10.1109/MM.1986.304671]
• C888: David Callahan , Jaspal Sublok, Static analysis of low-level synchronization, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.100-111, May 05-06, 1988, Madison, Wisconsin, United States
• CW82: CURTm, R. S., AND WITTm, L. D. 1982. BugNet: A debugging system for parallel programming environments. In Proceedings of the 3rd International Conference on Distributed Computing Systems. ACM, pp. 394-399.
• Els88: I. J. P. Elshoff, A distributed debugger for Amoeba, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.1-10, May 05-06, 1988, Madison, Wisconsin, United States
• Fid88: C. J. Fidge, Partial orders for parallel debugging, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.183-194, May 05-06, 1988, Madison, Wisconsin, United States
• FLM88: Robert J. Fowler , Thomas J. LeBlanc , John M. Mellor-Crummey, An integrated approach to parallel program debugging and performance analysis onlarge-scale multiprocessors, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.163-173, May 05-06, 1988, Madison, Wisconsin, United States
• FO76: Lloyd D. Fosdick , Leon J. Osterweil, Data Flow Analysis in Software Reliability, ACM Computing Surveys (CSUR), v.8 n.3, p.305-330, Sept. 1976 [doi>10.1145/356674.356676]
• For88: Alessandro Forin, Debugging of heterogeneous parallel systems, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.130-140, May 05-06, 1988, Madison, Wisconsin, United States
• Gai85: Jason Gait, A debugger for concurrent programs, Software—Practice & Experience, v.15 n.6, p.539-554, June 1985 [doi>10.1002/spe.4380150603]
• GB85: GARCIA, M. E., AND BERMAN, W. J. 1985. An approach to concurrent systems debugging. In Proceedings of the 5th International Conference on Distributed Computing Systems. IEEE, pp. 507-514.
• GGK84: GARCIA-MOLINA, H., GERMANO, F., JR., AND KOHLER, W. H. 1984. Debugging a distributed computing system. IEEE Trans. Softw. Eng. SE-IO, 2 (Mar.), 210-219.
• GH83: GENTLEMAN, W. M., AND HOEKSMA, H. 1983. Hardware assisted high level debugging. SIGPLAN Notices 18, 8 (August), 140-144.
• GK86: Robert D. Gaglianello, The Meglos user interface, Proceedings of 1986 ACM Fall joint computer conference, p.169-177, November 1986, Dallas, Texas, United States
• GKY88: G. Goldszmidt , S. Katz , S. Yemini, Interactive blackbox debugging for concurrent languages, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.271-282, May 05-06, 1988, Madison, Wisconsin, United States
• Gol86: A T Goldberg, Knowledge-based programming: a survey of program design and construction techniques, IEEE Transactions on Software Engineering, v.12 n.7, p.752-768, July 1986
• GR85: GEHANI, N. H., AND ROOME, W. D. 1985. Concurrent C. Tech. Rep., AT&T Bell Laboratories.
• Gri87: GRIFFIN, J. 1987. Parallel debugging system user's guide. Tech. Rep., Los Alamos National Laboratory.
• HC87: HOUGH, A. A., ANO CUNY, J. 1987. Belvedere: Prototype of a pattern-oriented debugget for highly parallel computation. In Proceedings of the International Conference on Parallel Processing. Penn State University, pp. 735-738.
• HHK85: HARTER, P. K., JR., HEIMBIGNER, D. M., AND KING, R. 1985. IDD: An interactive distributed debugger. In Proceedings of the 5th International Conference on Distributed Computing Systems. IEEE, pp. 498-506.
• HL85a: HELMBOLD, D., AND LUCKHAM, D. 1985. Debugging ada tasking programs. IEEE Softw. 2, 2, 47-57.
• HL85b: David Helmbold , David Luckham, TSL: task sequencing language, Proceedings of the 1985 annual ACM SIGAda international conference on Ada, p.255-274, May 14-16, 1985, Paris, France
• HU75: HECHT, M. S., ANO ULLMAN, J. D. 1975. A simple algorithm for global data flow analysis problems. SIAM J. Comput. 4, 519-532.
• HW88: D. Haban , W. Weigel, Global events and global breakpoints in distributed systems, Proceedings of the Twenty-First Annual Hawaii International Conference on Software Track, p.166-175, January 1988, Kailua-Kona, Hawaii, United States
• Int87: INTEL CORP. 1987. iPSC Concurrent Debugger Manual.
• JLSU87: Jeffrey Joyce , Greg Lomow , Konrad Slind , Brian Unger, Monitoring distributed systems, ACM Transactions on Computer Systems (TOCS), v.5 n.2, p.121-150, May 1987 [doi>10.1145/13677.22723]
• Kar87: Alan H. Karp, Programming for parallelism, Computer, v.20 n.5, p.43-57, May 1987 [doi>10.1109/MC.1987.1663563]
• Lam78: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• LM87: T. J. LeBlanc , J. M. Mellor-Crummey, Debugging parallel programs with instant replay, IEEE Transactions on Computers, v.36 n.4, p.471-482, April 1987 [doi>10.1109/TC.1987.1676929]
• LP85: Carol H. LeDoux , D. Stott Parker, Jr., Saving traces for Ada debugging, Proceedings of the 1985 annual ACM SIGAda international conference on Ada, p.97-108, May 14-16, 1985, Paris, France
• LP86: B Lazzerini , C A Prete, DISDEB: an interactive high-level debugging system for a multi-microprocessor system, Microprocessing and Microprogramming, v.18 n.1-5, p.401-408, Dec. 1986 [doi>10.1016/0165-6074(86)90070-0]
• LR85: LEBLANC, R. J., ANO ROBBINS, A. D. 1985. Event-driven monitoring of distributed programs. In Proceedings of the 5th International Conference on Distributed Computing Systems. IEEE, pp. 515-522.
• Man87: Carl R. Manning, Traveler: the apiary observatory, European conference on object-oriented programming on ECOOP '87, p.89-97, October 1987, Paris, France
• MC88a: MILLER, B. P., AND CHOI, J.-D. 1988a. Breakpoints and halting in distributed systems. In Proceedings of International Conference on Distributed Computing Systems. IEEE.
• MC88b: Barton P. Miller , Jong-Deok Choi, A mechanism for efficient debugging of parallel programs, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.141-150, May 05-06, 1988, Madison, Wisconsin, United States
• McD88: McDOWELL, C. E. 1988. Viewing anomalous states in parallel programs. In Proceedings of the International Conference on Parallel Processing. Penn State University, pp. 54-57.
• McD89: Charles E. McDowell, A practical algorithm for static analysis of parallel programs, Journal of Parallel and Distributed Computing, v.6 n.3, p.515-536, June 1989 [doi>10.1016/0743-7315(89)90004-X]
• MCR85: A. Di Maio , S. Ceri , S. Crespi Reghizzi, Execution monitoring and debugging tool for Ada using relational algebra, Proceedings of the 1985 annual ACM SIGAda international conference on Ada, p.109-123, May 14-16, 1985, Paris, France
• MMS86: B. P. Miller , C. Macrander , S. Sechrest, A distributed programs monitor for Berkeley UNIX, Software—Practice & Experience, v.16 n.2, p.183-200, Feb. 1986 [doi>10.1002/spe.4380160209]
• Pet77: James L. Peterson, Petri Nets, ACM Computing Surveys (CSUR), v.9 n.3, p.223-252, Sept. 1977 [doi>10.1145/356698.356702]
• PL88: Douglas Z. Pan , Mark A. Linton, Supporting reverse execution for parallel programs, ACM SIGPLAN Notices, v.24 n.1, p.124-129, Jan. 1989
• RRZ88: Robert Rubin , Larry Rudolph , Dror Zernik, Debugging parallel programs in parallel, ACM SIGPLAN Notices, v.24 n.1, p.216-225, Jan. 1989
• SBN88: David Socha , Mary L. Bailey , David Notkin, Voyeur: graphical views of parallel programs, ACM SIGPLAN Notices, v.24 n.1, p.206-215, Jan. 1989
• Seq86: SEQUENT CORP. 1986. Dynix Pdbx Parallel Debugger User's Manual.
• SG86: Robert W. Scheifler , Jim Gettys, The X window system, ACM Transactions on Graphics (TOG), v.5 n.2, p.79-109, April 1986 [doi>10.1145/22949.24053]
• Sno84: Richard Snodgrass, Monitoring in a software development environment: A relational approach, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.124-131, April 1984
• ST83: SEIDNER, R., AND TINDALL, N. 1983. Interactive debug requirements. SIGPLAN Notices 9-22.
• Sto88: Janice M. Stone, A graphical representation of concurrent processes, ACM SIGPLAN Notices, v.24 n.1, p.226-235, Jan. 1989
• Sun86: SUN MICROSYSTEMS. 1986. NeWS Preliminary Technical Overview.
• Tan81: A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 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]
• Tay84: TAYLOR, R. N. 1984. Debugging real-time software in a host-target environment. Tech. Rep. 212, Univ. of California at Irvine.
• TO80: TAYLOR, R. N., AND OSTERWEIL, L. g. 1980. Anomaly detection in concurrent software by static data flow analysis. IEEE Trans. So{tw. Eng. SE-6, 3 (May), 265-278.
• Vic77: VICTOR, K. E. 1977. The design and implementation of DAD, a multiprocess, multimachine, multilanguage interactive debugger. In Proceedings of Hawaii International Conference on System Sciences. IEEE, pp. 196-199.
• Web83: Janice Cynthia Weber, Implementation issues: session summary, ACM SIGPLAN Notices, v.18 n.8, August 1983
• Wer88: Linda Louise Werner , William E. Howden, Fault detection in production programs by means of data usage analysis, 1988
• YT86: YOUNG, M., AND TAYLOR, R. N. 1986. Combining static concurrency analysis with symbolic execution. In Proceedings of Workshop on Software Testing. pp. 10-178.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Assertion checkers

General Terms:
Design, Languages, Performance