System for deadlock condition detection and correction by allowing a queue limit of a number of data tokens on the queue to increase
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.
1. 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.
2. The method of claim 1 , blocking the receiving port when a data token is not available.
3. The method of claim 1 , blocking the sending port when a limit on a number of data tokens in the queue is reached.
4. The method of claim 1 , including building the wait graph with said blocked threads and traversing said wait graph to determine if it is cyclic.
5. The method of claim 1 , wherein the limit of a queue associated with a sending port is allowed to increase.
6. The method of claim 1 , wherein a queue limit on the number of data tokens of a second queue is decreased while said limit of said queue is increasing.
7. The method of claim 1 , said block detection thread monitors one or more of the data queues.
8. The method of claim 7 , said block detection thread does not require communication from other threads to determine if a thread is blocked.
9. A method for executing a dataflow application comprising:
providing a dataflow application comprising a plurality of map components and data ports, some of said map components being linked between data ports and some map components comprising one or more composite components having a plurality of processes, wherein at least some of said linked data ports being linked by a queue;
allocating a processing thread to a respective map component;
executing multiple processing threads in parallel with each map component on a separate processing thread;
using a thread to detect if a deadlock condition does or will exist for one or more of said processing threads by building a wait graph of several thread states and determining if the wait graph is circular; and
correcting a deadlock condition for a deadlocked processing thread by allowing the queue linking data ports to exceed a queue limit of a number of data tokens.
10. The method of claim 9 , wherein the correcting step includes choosing a thread that waits as a producer if a circular wait graph is detected.
11. The method of claim 9 , wherein if the detecting step determines a wait graph is circular, the correcting step including analyzing queues other than said queue in the wait graph for token batch reduction.
12. The method of claim 9 , wherein if the detecting step determines a wait graph is circular, the correcting step including the substep of reducing said queue limit in one or more queues other than said queue in the wait graph.
13. A method for executing a dataflow application in a multi-thread processing system comprising:
providing a dataflow application comprising a plurality of map components and data ports, a number of map components being linked between data ports using queues and some map components comprising composite components having a plurality of processes;
allocating a processing thread to each composite map component including allocating a thread for deadlock detection;
executing each composite map component on a separate thread;
determining if a deadlock exists using said deadlock detection thread to monitor queues, including building a wait graph 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 exists, by allowing a queue limit of a number of data tokens on the queues to increase.
14. The method of claim 13 , wherein the queues including a first queue and a second queue, and a queue limit on the number of data tokens of the second queue is decreased while a limit of said first queue is increasing.
15. The method of claim 13 , including transporting data tokens among map components on said queues.
16. The method of claim 15 , batching the data tokens to regulate the length of time a map component may execute without synchronization.
17. The method of claim 13 , including ports associated with each map component for representing and transporting multi-state null value tokens.
18. The method of claim 17 , the null value tokens including an error null.