Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1999-07-28
2004-03-30
Follansbee, John (Department: 2126)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000, C707S793000, C710S200000
Reexamination Certificate
active
06714958
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to analyzing multi-threaded programs. More specifically, the invention relates to modifying the predisposed execution of a multi-threaded program to detect and cause latent deadlocks.
Traditional computer programs involved a single execution stream that performed operations sequentially. However, it is now common for computer programs to include multiple execution streams, which can perform operations in parallel. Each instruction stream is known as a “thread.”
Multi-threaded programs allow for better utilization of the computer system's resources. For example, where a traditional single-threaded program awaits for user input and wastes processing power, a multi-thread program can have a thread perform operations in the “background” while a different thread is processing the user input. Thus, a multi-threaded word processing program can perform spell checking or a multi-threaded spreadsheet program can recalculate the spreadsheet in the background to achieve more efficient utilization of processing power.
Although multi-threaded programs can provide better utilization of the computer system's resources, the dynamic execution of threads makes debugging the programs very difficult. Errors in thread synchronization may be rarely manifested during program execution. This can make the synchronization errors hard to detect, hard to reproduce and hard to verify that an error has been corrected.
Deadlocks can occur when multiple threads compete for the same set of multiple synchronization objects but acquire them in different orders. When one thread acquires a synchronization object, it exposes other threads that might also contend for that same synchronization object to a potential deadlock. As long as the first thread retains ownership of the synchronization object, the contending threads will typically be suspended whenever they attempt to acquire that synchronization object. The thread that holds the synchronization object may attempt to acquire another synchronization object. If this synchronization object is held by one of the contending, suspended threads, a deadlock can occur.
In order to illustrate how a deadlock can be latent,
FIG. 1
shows a simple illustration of two threads that acquire, hold, and release two synchronization objects. At an instruction
101
, thread
1
acquires a synchronization object called “mu
1
.” Subsequently, thread
1
acquires synchronization object “mu
2
” at an instruction
103
. At instructions
105
and
107
, thread
1
releases synchronization objects mu
2
and mu
1
, respectively.
At some point in time later, thread
2
acquires synchronization object mu
2
at an instruction
109
. Thread
2
then acquires synchronization object mu
1
at an instruction
111
. At instructions
113
and
115
, thread
2
releases synchronization objects mu
1
and mu
2
, respectively.
It should be understood that
FIG. 1
only includes instructions that acquire and release the two synchronization objects. Nevertheless, the Figure. Illustrates that both thread
1
and thread
2
were potentially contending for the synchronization objects mu
1
and mu
2
, but the sequence of execution of the threads did not cause a deadlock condition.
FIG. 2
shows a simple illustration of how the two threads of
FIG. 1
can become deadlocked. At an instruction
201
, thread
1
acquires synchronization object mu
1
. Thread
2
then executes and acquires synchronization object mu
2
at an instruction
203
. At an instruction
205
, thread
2
attempts to acquire synchronization object mu
1
. However, synchronization object mu
1
is currently being held by thread
1
. Therefore, thread
2
is not able to acquire synchronization object mu
1
and is suspended awaiting the availability of the synchronization object at an instruction
207
.
Thread
1
continues execution and attempts to acquire synchronization object mu
2
at an instruction
209
. Since synchronization object mu
2
is held by thread
2
, thread
1
is not able to acquire the synchronization object and is suspended awaiting the availability of synchronization mu
2
at an instruction
211
. At this point, deadlock has occurred since thread
2
is waiting for a synchronization object that thread
1
holds and thread
1
is waiting on a synchronization object that thread
2
holds.
As shown, in multi-threaded programs a deadlock can be latent and only surface if the right (or wrong) execution sequence occurs. It would be beneficial to have new techniques for detecting and causing latent deadlocks in a multi-threaded program. Additionally, it would be beneficial to have techniques that increase the opportunity for latent deadlocks to manifest themselves without introducing new deadlocks into the program.
SUMMARY OF THE INVENTION
Embodiments of the present invention provide methods and systems for analyzing multi-threaded programs. More specifically, the predisposed execution of multi-threaded programs is modified to cause and detect latent deadlocks. In general, synchronization objects are tracked and when a thread attempts to acquire a synchronization object that could result in a deadlock with another thread, the thread is suspended. When another thread attempts to acquire the synchronization object, the second thread is allowed to obtain the synchronization object and the first thread is awakened to potentially produce a deadlock.
In one embodiment, the invention provides a computer implemented method of analyzing multi-threaded programs. A request is received from a first thread that holds at least one synchronization object to acquire a synchronization object. It is determined if another thread previously held the synchronization object while acquiring another synchronization object. If another thread previously held the synchronization object while acquiring another synchronization object, the first thread is suspended. While the first thread is suspended, a request from a second thread to acquire the synchronization object is received. The second thread is allowed to acquire the synchronization object and the first thread is awakened thereby creating a potential deadlock.
REFERENCES:
patent: 5515538 (1996-05-01), Kleiman
patent: 6223204 (2001-04-01), Tucker
George Coulouris, “Distributed Systems Concept and Design” 1994, Dadison-Wesley, Second Edition, pp. 384 and 389.
Follansbee John
Hoang Phuong N.
International Business Machines - Corporation
Ritter Lang & Kaplan LLP
LandOfFree
Detecting and causing latent deadlocks in multi-threaded... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Detecting and causing latent deadlocks in multi-threaded..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Detecting and causing latent deadlocks in multi-threaded... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3270777