US 7,743,382 B2 · System for deadlock condition detection and correction by allowing a queue limit of a number of data tokens on the queue to increase

Abstract

The execution environment provides for scalability where components will execute in parallel and exploit various patterns of parallelism. Dataflow applications are represented by reusable dataflow graphs called map components, while the executable version is called a prepared map. Using runtime properties the prepared map is executed in parallel with a thread allocated to each map process. The execution environment not only monitors threads, detects and corrects deadlocks, logs and controls program exceptions, but also data input and output ports of the map components are processed in parallel to take advantage of data partitioning schemes. Port implementation supports multi-state null value tokens to more accurately report exceptions. Data tokens are batched to minimize synchronization and transportation overhead and thread contention.

Claims18

Dependent claims

A method of deadlock management in a multi-thread, parallel processing data management system having ports for sending and receiving data tokens comprising:

allocating at least one thread to a first process and at least one thread to a second process, wherein the first and second processes are connected through a queue via sending and receiving ports;
using one thread to detect if one or more of said threads are blocked;
if a thread is determined blocked, determining if the blocked thread is sending data or receiving data, wherein a receiving port of said blocked thread blocks if a data token is unavailable and a sending port of said blocked thread blocks when a queue limit is reached;
determining if a deadlock exists using said block detecting thread by building a wait graph of said one or more blocked threads and determining if the graph is cyclic, wherein if said graph is cyclic, said graph is waiting on itself, indicating the deadlock exists;
and
correcting the deadlock, if the deadlock is detected, by allowing the queue limit of a number of the data tokens on the queue to increase.

3 more elements

Dependencies are inferred from the claim text.

System for deadlock condition detection and correction by allowing a queue limit of a number of data tokens on the queue to increase

Life of this patent

System for deadlock condition detection and correction by allowing a queue limit of a number of data tokens on the queue to increase

Life of this patent

Abstract

Claims18