Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-01-14
2002-01-29
Powell, Mark R. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C700S017000, C703S022000
Reexamination Certificate
active
06343371
ABSTRACT:
The present invention relates generally to a system and method for statically detecting potential race conditions in multi-threaded computer programs, and more particularly to building and analyzing a synchronization graph—the synchronization graph representing certain computer program elements and execution paths—to detect potential race conditions on object data fields.
BACKGROUND
Most commercial operating systems, such as Microsoft Windows 95 and modern programming languages, such as C++ and Java, support the use of threads. Many popular software applications, such as Microsoft Word and Netscape Navigator, are multi-threaded. In a multi-threaded environment, a program may consist of one or more threads of control, each of which shares a common address space and most other program resources. Multi-threading is often used to exploit internal software application and hardware parallelism, resulting in among other things, improved networking performance, and the speeding up of user feedback response.
Programming with multiple threads introduces the potential for a timing dependent error known as a race condition. In order for a race condition to occur, the following three conditions must be present: (a) two or more threads executing in parallel (hereinafter referred to as “parallel threads”) access a same memory location at nearly the same time; (b) at least one of the threads modifies the data in that memory location; and (c) the threads use no explicit mechanism, or lock, to prevent the accesses from being simultaneous. This type of unsynchronized access to a memory location can produce unintended results. To illustrate the idea of a race condition, consider the program illustrated in Table 1, where two unsynchronized threads access and change the value of a shared resource. The program illustrated in Table 1 is written in the Java programming language, but the problem illustrated is applicable to all multithreaded programming environments.
TABLE 1
An Example of Unsynchronized Access to Shared Resource
public class T extends Thread {
static D d = new D ();
//create a shared object
public static void main (String []args) {
// main thread starts here
(new T ()).start ();
//starting new thread
d.f++;
//access a shared field
}
public void run () {
//the new thread starts here
d.f--;
//access to a shared field
}
}
class D {
int f = 0;
}
This program has a potential race condition because access to the shared data field “d.f” in both methods, “main( )” and “run( ),” is not protected by any lock. At runtime, the increment operation (d.f++) and the decrement operation (d.f−−) may therefore be interleaved in an arbitrary manner, producing unpredictable results. If these two operations do not overlap, then the resulting value of d.f will correctly be zero. If the operations do overlap, then the result could also be either of −1 or +1, which presumably is not what the programmer intended.
A few simple techniques are commonly used in modern programming languages to synchronize the activities of threads. Most of these techniques are based on the concept of monitors, or locks. It is not necessary to know the details of how these various techniques work to practice the present invention. However, a brief explanation of how locks work is provided as background information.
A lock is typically associated with a resource that multiple threads may need to access, but that should be accessed by only one thread at a time. If the resource is not being used, a thread can acquire its lock and access the resource. However, if another thread already has the lock to the resource, all other threads have to wait until the current thread finishes and releases the lock. Then another thread can acquire the lock and access the resource.
The unsynchronized access to a shared resource illustrated by the program in Table 1 can be fixed by coordinating the activities of the threads, so that they do not collide in the same address space. The program in Table 2 illustrates parallel executing threads synchronizing access to a shared resource.
TABLE 2
An Example of Synchronized Access to Shared Resource
100
public class T extends Thread {
101
static D d = new D ();
//create a shared object
102
103
public static void main (string []args) {
// main thread
starts here
104
(new T ()).start ();
//starting new thread
105
synchronized(d) {
106
d.f++;
//access a shared field
107
}
108
}
109
public void run () {
//the new thread starts here
110
synchronized
(d) {
//perform synchronization
111
d.f--;
//access to a shared field
112
}
113
}
114
}
115
116
class D {
117
int f = 0;
118
}
This program uses a locking mechanism (identified by the “synchronize” statement) to synchronize the two parallel executing threads. Thus, the increment operation (d.f++) and the decrement operation (d.f−−) cannot overlap and the value of d.f will correctly be zero.
Even with the availability of locks, or monitors, it is easy to introduce race conditions into a computer program. A computer programmer, for example, may inadvertently overlook the need for a synchronization instruction, accidentally leave a synchronization instruction out, or implement the instructions in the wrong order.
In addition to race conditions being easy to introduce into a computer program, they are also generally very difficult to find. For one, a data race typically becomes apparent only if two threads access an improperly protected memory location at nearly the same time. A program could potentially run for a long time without showing any signs of a problem. Also, since threads may be time-sliced, which means they can run in arbitrary bursts as directed by the operating system, the symptoms may be different each time a race condition actually occurs.
Race detection schemes have been studied for decades. What has resulted are a number of commonly used techniques used for detecting potential race conditions. These techniques can be categorized as either dynamic or static. In general each technique has problems. For instance, since dynamic detection schemes operate while the program is executing, they can significantly slow down an application due to the overhead incurred by making a procedure call at every load and store instruction. (See Savage et al., “Eraser: A dynamic Data Race Detector for Multi-threaded Programs,” 1997, page 32, first para.). Also, since dynamic detection schemes utilize testing methodologies, they may fail to detect certain race conditions because of insufficient test coverage.
An example of a static race detection scheme is disclosed by WARLOCK (See Sterling, “WARLOCK A Static Data Race Analysis Tool,” SunSoft, Inc., 1993). WARLOCK works “by tracing the execution of every path through the code.” (See page 3, col. 2, para. 2). WARLOCK traces each execution path by analyzing a file output as the result of compiling the computer program. One problem with path tracing race detection algorithms is that static race detection systems such as that of WARLOCK do not support the use of dynamically dispatched method calls and will therefore not detect potential race conditions in source code written with an object-oriented language, such as C++ or Java. Secondly, in a worst-case scenario, the execution time of the algorithm increases exponentially with the size of the program being analyzed. As if these problems were not enough, systems such as WARLOCK do not infer information about which fields may be shared between multiple threads (a race condition can only occur on object data fields shared by multiple threads). The absence of this information can result in spurious, or false alarms indicating potential race conditions on unshared, or thread-local, object data fields. Often, in order to avoid such false alarms, a programmer must annotate the source code of the computer program with declarations about which dat
Bernard Andrew B.
Flanagan Cormac A.
Compaq Computer Corporation
Khatri Anil
Powell Mark R.
LandOfFree
System and method for statically detecting potential race... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for statically detecting potential race..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for statically detecting potential race... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2823038