CHAPTER 1
INTRODUCTION
Concurrent programming is becoming increasingly important in both scientific and commercial areas. Correspondly, therefore, debugging concurrent programs is becoming an important area of research and development. Debugging sequential programs is a well understood problem [LeBl87]. Debugging concurrent programs, however, is a new, more difficult and complex problem. As a result of this difficulty and complexity, standard tools used for sequential programs, such as monitors and debuggers, are not adequate.
The present research addresses a new approach for correcting a concurrent program. The rationale of this approach may be compared to that of researchers within the field of psychology who analyze a patient's drawings to make inferences about the patient's state. The programmer communicates a solution to a problem through a programming language, in this case a concurrent programming language. The resulting source code is a true expression of his intentions. By analyzing the communication patterns of a concurrent program, it is possible to make inferences regarding the programmer's intentions. The programmer can then be guided to express his ideas correctly. This approach is referred to as very high-level debugging. The idea of very high-level debugging in a prototype debugger is a central issue in the current research. An ancillary issue addressed is the impact of such a debugger on novice concurrent programmers.
More important than detecting and correcting an error in a concurrent program is the ability to correctly express concurrency. Modern technology can be exploited to relieve programmers from some of the complexities related to the task of debugging concurrent programs.
Before continuing with the discussion of concurrency, a brief definition of terms is needed. Bustard [Bust90] distinguishes concurrent, parallel, and distributed programs with the following definitions:
* A concurrent program defines actions that may be performed simultaneously.
* A parallel program is a concurrent program that is designed for execution on parallel hardware.
* A distributed program is a parallel program designed for execution on a network of autonomous processors that do not share main memory[Bal89].
In this context, Ada is an important vehicle for expressing concurrency because it allows the expression of concurrent algorithms regardless of the hardware platform. Ada was standardized in 1983 [DoD 83], and is intended to be used in all new U. S. Department of Defense related software development. Ada's tasking model provides an excellent vehicle for implementing concurrency.
1.1. Why Concurrency is Important
According to Gehani [Geha84]
The ability to write concurrent programs, i.e., programs with components that can be executed in parallel, is desirable for many reasons [HOA78a, GEH83a]:
* It leads to notational convenience and conceptual elegance in writing operating systems, real-time systems, database systems and simulation programs, all of which may have many events occurring concurrently.
* Inherently concurrent algorithms are best expressed with concurrency explicitly stated; otherwise the structure of the algorithm may be lost.
* It can reduce program execution time, because genuine multiprocessing hardware can be used to execute different parts of a program in parallel.
* Even on single CPU computers concurrent programming can reduce program execution time because lengthy input/output operations and the CPU operation can be processed in parallel.
Figure 1.1 depicts the area of the present research as the intersection of software debugging, software concurrency, and empirical studies of programmers within the educational context.
In all major scientific advances, teaching lags behind technical innovation. This is especially true in computer science. The lag in teaching is due to many circumstances: the age of computer science; the relatively low number of computer science professors, and how society understands what computers are in general and what software is in particular. It has often been said that a picture is worth a thousand words. Everyone can see the hardware, but few "see" the software and its almost unlimited potential. To bring into existence a new hardware platform requires a great deal of time, material and personnel. To bring into existence new software, few observable resources are required. In the case of software, human talent plays a major role. In this situation, teaching software-related topics is of immense importance. One of these topics is concurrent programming.
To reduce the gap between the current state of the art in concurrent programming and the software available for teaching concurrency, a group of researchers lead by Dr. Michael B. Feldman at George Washington University is developing a programming environment specifically dedicated to teaching concurrency [Feld90a]. According to Feldman [Feld90b],
The Small-Ada system exists for the purpose of teaching concurrency by giving students hands-on exposure to an Ada tasking model in which much can be visualized and changed. Small-Ada supports an approximately full Ada tasking model but relatively little of the sequential language (e.g. packages, generics, access types, etc., are not supported).
A monitoring tool has been developed for helping programmers understand concurrency. It has been incorporated into the Small Ada system. Small Ada is a P-code compiler for a subset of Ada [Hath89]. It supports the Ada tasking model. The Small Ada Parallel Monitoring (SAPM) [Lope91a, Lope91b] allows the monitoring of Small Ada tasks at the source code level. The SAPM was designed and implemented by the author during the spring of 1989.
A pilot study was conducted to evaluate the effectiveness of Small-Ada as a debugging tool [Lope91d]. The results of this study confirmed that debugging at the source level is a promising approach. While this study was being conducted, Small-Ada was being extended to exploit a new approach for assisting the identification and correction of bugs in concurrent programs written by novice programmers, especially task communication related bugs. This approach became the central focus of the present research.
An expert system can be deployed to understand some of the semantics of a concurrent program. Understanding the semantics of a program is a very complex and controversial issue. Some attempts have been made to match a set of specifications against a program [John86]. If a disagreement is found, the error can be found. A problem, however, occurs in this approach. The specification must be made in such a way that it is understandable by computer, so another abstraction mechanism must be mastered. Now, instead of a single abstraction, the original program, the programmer confronts a second abstraction also: the specification of the program. Until the specification can be transformed into a running program without human intervention, this approach will lead to serious problems for the same reason that programs are prone to having bugs in the first place. No solution is foreseen for this problem until the activity of programming evolves to a point that has been reached in the fields of architecture, engineering, and particularly medicine. In all of these fields, well-documented algorithms for performing specific tasks have been developed. The combination of such algorithms leads to the development of safe and reliable systems. Contemporary schools of medicine have available extraordinary resources that are used to enhance education in medicine. What would be the "output" of medical schools if students were deprived of studying dead and living bodies? Since computer programming is a young field and has only recently begun to build tools dedicated to software education purposes, only rudimentary resources exist.
In this situation, the task of trying to understand the semantics of a program is very difficult. Fortunately, much work has been performed regarding the use of expert systems for performing complex cognitive activities, including programming.
According to Anderson [Ande83],
Production systems are particularly general in that they claim to be computational universal -- capable of modeling all cognitive activity.
If it is possible for a human expert to study a computer program on paper and then find and correct a bug, then in theory, it should be possible to build an expert system that possesses the knowledge used by the human expert to perform this debugging activity. We can make an analogy by comparing this problem with that of performing a reverse translation of a program. There are instances in which programs are written, especially in assembler, with some cumbersome constructs that makes their reversal an extremely difficult task. Here one is faced with the striking evidence that programming is still a non-standardized activity. Yet it is still possible to build a database of mappings. Each mapping would be made up of a pair of a source code fragment and an equivalent object code. A rich set of these mappings would make it possible to reverse a program representation to the many levels now available for communicating algorithms to computers. Current perceptions of the abstractions involved in concurrent programming led the author to try applying this idea by transferring the knowledge of an expert programmer into the CLIPS production system based rules [Giar89a, 89b]. Using this approach, it was possible to detect a logic bug and issue a precise recommendation for fixing it. Further work led to the identification of a set of situations in which the same approach can be used. This work was initially documented in Lope91c. The main focus is in the understanding of the semantics of a concurrent program, especially where communication between tasks occurs.
Due to the way concurrency is presently understood, as a consequence of the implementation's complexity, one often loses track of the original abstractions as they are expressed in programs. Tools are needed to analyze the semantics of a program and guide the user in its correct logical development.
Such a tool might be an expert system with an inference engine that, based on a set of rules, could emulate an expert's strategy and tactics when studying and debugging a concurrent program. This expert system tool would allow the user to focus on concurrency issues without the distraction of other levels of abstractions that are often inherent in on-line debuggers and monitors.
The present research has three basic goals:
1) To develop a new approach for debugging concurrent programs;
2) To implement the approach into a prototype system called ADAT (Automated
Debugger for Ada Tasks); and
3) To evaluate the effectiveness of ADAT as a teaching tool for novice
programmers.
The present research will test the following hypotheses concerning the effectiveness of the ADAT as a tool:
a) The use of ADAT improves the performance of the debugging activity
b) The use of ADAT improves the understanding of concurrency
1.4. Dissertation Organization
This dissertation is comprised of seven chapters. Chapter One is an introduction. Chapter Two describes the basic research terminology in the area of debugging. In addition, a discussion on types of errors related to concurrency is presented. Chapter Three presents the related research on tools that are relevant to this research. Chapter Four describes ADAT and Small Ada. Chapter Five presents the experimental design. Chapter Six documents the evaluation study performed to assess the effectiveness of ADAT. Chapter Seven presents proposals for the continuation of this research. Appendices A-I are included for a review of materials used in the dissertation.