VERY HIGH-LEVEL DEBUGGING: EVALUATION OF DIAGNOSIS AND SOLUTIONS FOR ADA CONCURRENT PROGRAMS
By
B.B.A. System Analysis, July 1983, Pontifical Catholic University of R.G.S., Brazil
M.S. Computer Science, May 1985, Central Michigan University
A Dissertation submitted to
The Faculty of the
Department of Electrical Engineering and Computer Science
The School of Engineering and Applied Science
The George Washington University
Washington D.C. 20052
in partial satisfaction of the requirements for the degree
of Doctor of Science in Computer Science
October 15, 1992
Dissertation directed by
Rachelle Sara Heller
Associate Professor of Engineering and Applied Science
This research was sponsored by the Brazilian National Council of Research and Development (CNPq) under contract number 20.5567/88.6 and by the Pontifical Catholic University of Rio Grande do Sul (PUCRS), Brazil.
ABSTRACT
This dissertation describes a new approach for debugging concurrent programs.
An enhanced SmallAda parser analyzes an erroneous source program and an expert system gives the programmer an explanation of the nature of the program's bug and guides the programmer in how to fix the bug. This approach is given the name very high level-debugging.
Due to the formidable complexities related to very high-level debugging, the problem domain has been confined to problems faced by novice concurrent programmers.
An Automated Debugger for Ada Tasks (ADAT) was designed and implemented to test the feasibility and usefulness of such approach.
A controlled experiment was performed to evaluate the effectiveness of ADAT as both a debugging and an instructional tool. The results show that ADAT is a valuable tool for assisting novices in concurrent Ada programming to identify and fix bugs.
Further development of ADAT is promising for teaching concurrency because ADAT allows the direct analysis of students' programs without the additional preparation of specifications or plans.
TABLE OF CONTENTS
1.1. Why Concurrency is Important
1.2. The Research
1.3. Research Goals
1.4. Dissertation Organization
2.1. Introduction
2.2. Debugging
2.3. Monitoring
2.4. Intrusive Monitors
2.5. Non-Intrusive Monitors
2.6. Low-Level Debugging
2.7. High-Level Debugging
2.8. Very High-Level Debugging
2.9. Static Analysis
2.10. Dynamic Analysis
2.11. Flowback Analysis
2.12. Semantic Analysis
2.13. Process Resolution
2.14. Errors
2.14.1. Task Sequencing Errors
2.14.1.1. Race Conditions
2.14.1.1.1. Initialization Anomaly
2.14.1.1.2. Update Anomaly
2.14.2. Deadness Errors
2.14.2.1. Deadlock
2.14.2.2. Task Communication Deadlocks
2.14.2.2.1. Self Blocking Anomaly
2.14.2.2.2. Circular Entry Call Anomaly
2.14.2.2.3. Dependence Blocking Anomaly
2.14.2.2.4. Acceptance Blocking Anomaly
2.14.2.2.5. Server Anomaly
3.1. Introduction
3.2. Monitoring Algorithms
3.3. MON
3.4. DBXTOOL
3.5. YODA
3.6. MORAN'S Monitor
3.7. CPEM
3.8. EDEN
3.9. BELVEDERE
3.10. PPD
3.11. MAD
3.12. VESTAL
3.13. PIEMON-1
3.14. An Intention-Based Diagnosis System - PROUST
3.15. Discussion and Comparison of Related Work
4. ADAT AND SMALL ADA OVERVIEW
4.1. History
4.2. Architecture
4.3. SAPM
4.4. Inspect Trace
4.5. Show CPU Consumption
4.6. Show Execution Replay
4.7. ADAT
4.7.1. Task Communication Anomalies
4.7.2. Task Communication Anomaly Patterns
4.7.3. Task Communication Reorientation Procedure
4.8. Conclusion
5.1. Introduction
5.2. The Setting and Subjects
5.3. Research Design
5.4. Procedure
5.5. Pilot Research
6.1. The Setting and Subjects
6.2. Analysis - Demographic Data
6.3. The Results with the Programs
6.3.1. The Results with Pgm1
6.3.2. The Results with Pgm2
6.3.3. The Results with Stage One
6.3.4. The Results with Stage Two
6.4. Subject Preferences and Suggestions
7. CONCLUSION AND FUTURE DIRECTIONS
7.1. Conclusion
7.2. Future Directions
APPENDIX A - Demographic Data Sheet
C.0 Program Zero - Warm Up
C.1 Program One
C.2 Program Two
C.3 Program Three
APPENDIX D - Subject Performance Evaluation Sheet
APPENDIX E - Follow Up Questionnaire
APPENDIX F - ADATPL Program for the Server Anomaly
APPENDIX H - CLIPS Pseudo Rules
APPENDIX I - Small-Ada Development History
I would like to express my gratitude to a special group of people.
To Dr. Rachelle Sara Heller, for her encouragement and patience throughout this research and especially for her guidance and help in shaping this dissertation.
To Dr. Michael Bliss Feldman, to whom I am greatly indebted for providing the encouragement and means to continue on track during turbulent times and for exposing me, from the very beginning of my work here at GWU, to the issue of concurrency.
To Dr. Thomas Nagy, for his constant encouragement, exceptional disposition to assist in this work and for the many careful revisions of this document.
To Dr. Abdou Youssef, who, first of all, helped with my arrival at GWU.
To Dr. Dianne C. Martin, for her helpful comments and suggestions.
To Dr. John Littlefield, University of Texas, Health Sciences Center at San Antonio, for his assistance with the statistics and data analysis.
And last, but foremost, to my students for their participation in the experiments.