Deterministic replay of multithreaded applications
First Claim
1. A program storage device, readable by a machine, tangibly embodying instructions to perform method steps for recording a representation of run-time behavior of a program, wherein said run-time behavior of said program includes sequences of events, each sequence associated with one of a plurality of execution threads, said method steps comprising:
- identifying execution order of critical events of said program, wherein said program comprises critical events and non-critical events;
generating groups of critical events of said program,wherein, for each given group, critical events belonging to said given group belong to a common execution thread, critical events belonging to said given group are consecutive, and only non-critical events occur between any two consecutive critical events in said given group; and
wherein said groups are ordered and no two adjacent groups include critical events that belong to a common execution thread;
generating, for each given execution thread, a logical thread schedule that identifies a sequence of said groups associated with said given execution thread, andstoring said logical thread schedule in persistent storage for subsequent reuse.
1 Assignment
0 Petitions
Accused Products
Abstract
A multithreaded program includes sequences of events wherein each sequence is associated with one of a plurality of execution threads. In a record mode, the software tool of the present invention records a run-time representation of the program by distinguishing critical events from non-critical events of the program and identifying the execution order of such critical events. Groups of critical events are generated wherein, for each group Gi, critical events belonging to the group Gi belong to a common execution thread, critical events belonging to the group Gi are consecutive, and only non-critical events occur between any two consecutive critical events in the group Gi. In addition, the groups are ordered and no two adjacent groups include critical events that belong to a common execution thread. For each execution thread, a logical thread schedule is generated that identifies a sequence of said groups associated with the execution thread. The logical thread schedules are stored in persistent storage for subsequent reuse. In a replay mode, for each execution thread, the logical thread schedule associated with the execution thread is loaded from persistent storage and the critical events identified by the logical thread schedule are executed.
243 Citations
24 Claims
-
1. A program storage device, readable by a machine, tangibly embodying instructions to perform method steps for recording a representation of run-time behavior of a program, wherein said run-time behavior of said program includes sequences of events, each sequence associated with one of a plurality of execution threads, said method steps comprising:
-
identifying execution order of critical events of said program, wherein said program comprises critical events and non-critical events; generating groups of critical events of said program, wherein, for each given group, critical events belonging to said given group belong to a common execution thread, critical events belonging to said given group are consecutive, and only non-critical events occur between any two consecutive critical events in said given group; and wherein said groups are ordered and no two adjacent groups include critical events that belong to a common execution thread; generating, for each given execution thread, a logical thread schedule that identifies a sequence of said groups associated with said given execution thread, and storing said logical thread schedule in persistent storage for subsequent reuse. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A program storage device, readable by a machine, tangibly embodying instructions to perform method steps for replaying run-time behavior of a program, wherein said run-time behavior of said program includes sequences of events, each sequence associated with one of a plurality of execution threads, said method steps comprising:
-
for each given execution thread, loading from persistent storage a logical thread schedule associated with said given execution thread, wherein said logical thread schedule comprises a sequence of groups of critical events of said program, wherein said program comprises critical events and non-critical events, wherein, for each given group, critical events belonging to said given group belong to a common execution thread, critical events belonging to said given group are consecutive, and only non-critical events occur between any two consecutive critical events in said given group, and wherein said groups are ordered and no two adjacent groups include critical events that belong to a common execution thread; for each given execution thread, executing critical events identified by said logical thread schedule associated with said given execution thread. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
21. A program storage device, readable by a machine, tangibly embodying instructions to perform method steps for recording a representation of run-time behavior of a program, wherein said run-time behavior of said program includes sequences of events, each sequence associated with one of a plurality of execution threads, said method steps comprising:
-
identifying a suspend(self) operation within said sequences of events; in an atomic action, assigning an identifier to said suspend(self) operation and executing said suspend(self) operation, wherein said identifier identifies execution order of said suspend(self) operation within said sequences of events; controlling a second thread to complete said atomic action; and storing said identifier in persistent storage for subsequent reuse. - View Dependent Claims (22)
-
-
23. A program storage devices, readable by a machine, tangibly embodying instructions to perform method steps for replaying run-time behavior of a program, wherein said run-time behavior of said program includes sequences of events, each sequence associated with one of a plurality of execution threads, said method steps comprising:
-
for each given execution thread, loading from persistent storage a thread schedule associated with said given execution thread, wherein said thread schedule identifies sequences of events of said program; identifying a suspend(self) operation within said sequences of events; and in an atomic action, executing said suspend(self) operations; and controlling a second thread to complete said atomic action in accordance with the thread schedule. - View Dependent Claims (24)
-
Specification