Method of determining causal connections between events recorded during process execution

• US 6,807,583 B2
• Filed: 11/08/2001
• Issued: 10/19/2004
• Est. Priority Date: 09/24/1997
• Status: Expired due to Fees

• Current Assignee: Carleton University
• Original Assignee: Carleton University
• Inventors: Hrischuk, Curtis, Woodside, Charles Murray
• Primary Examiner(s): Follansbee, John
• Assistant Examiner(s): OPIE, GEORGE L
• Application Number:
  US10/007,211
• Publication Number:
  US 20020194393A1
• Time in Patent Office: 1,076 Days
• Field of Search: 702/182-186, 706/52, 706/900-915, 709/100, 709/310, 709/318, 709/320, 714/37-39, 714/45, 717/124-135
• US Class Current: 719/318
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications

Abstract

A method of determining scenario causality, along with precedence causality, is disclosed. Information is recorded relating to events occurring during execution of a process. The information includes object related information and process related information. The information is translated into a sequence of scenario graph language statements, one or more events translated to a statement. From the statements, process execution flow is determined establishing some scenario causality and precedence causality.

Claims

1. A method of determining, from recorded information relating to events occurring during execution of a process, a plurality of the events that are causally connected by scenario causality and precedence causality, the method comprising the steps of:

(a) translating the recorded information relating to the events to statements in a first scenario graph language;

(b) determining from the first graph language statements, information relating to execution flow of the process wherein each first graph language statement comprises information relating to a predetermined execution flow of the process; and

,

(c) based on the information relating to an execution flow of the process, determining, for a first plurality of events, events that precede each event from the first plurality of the events that are causally connected by scenario causality to said event from the first plurality of the events.

2. A method of determining a plurality of the events that are causally connected as defined in claim 1, comprising the step of:

performing run time behavior verification by analysis of the scenario event graph, or combinations thereof, for one of race conditions, live lock conditions, and deadlock conditions.

3. A method of determining a plurality of the events that are causally connected as defined in claim 1, comprising the step of:

determining the identity type of a scenario during execution and providing a different level or style of service based on this determination.

4. A method of determining a plurality of the events that are causally connected as defined in claim 1, comprising the steps of:

monitoring a process during execution; and

,

recording the information relating to events occurring during execution of the process, the recorded information comprising at least a time value from each of at least two clocks and wherein at least one of the clocks is a logical clock.

5. A method of determining a plurality of the events that are causally connected as defined in claim 1, wherein translating the recorded information is performed in each of two domains;

and, wherein determining from the statements information relating to execution flow of the process is performed in dependence upon the statements in each domain.

6. A method of determining a plurality of the events that are causally connected as defined in claim 1, wherein the process is a process executed by a microprocessor.

7. A method of determining a plurality of the events that are causally connected as defined in claim 1, wherein the process is a process executed in software on at least two processors in a distributed system and wherein the information relating to events comprises information relating to a time measured by a logical clock and another time measured by another clock.

8. A method of determining a plurality of the events that are causally connected as defined in claim 1, wherein a statement in the first graph language represents a node having an out degree of at least 2 and wherein statement in the first graph language represents a node having in degree of at least 2.

9. A method of determining a plurality of the events that are causally connected as defined in claim 1, wherein the recorded information relating to events comprises process event information and object event information.

10. A method of determining a plurality of the events that are causally connected as defined in claim 1, wherein the statements form a graph language that is complete and sound.

11. A method of determining a plurality of the events that are causally connected as defined in claim 1, wherein the statements relate to delimiting and progress events of a process and of an object.

12. A method of determining a plurality of the events that are causally connected as defined in claim 1, wherein the first graph language has nodes and edges from a group of:

external, thread begin, and-join, and-fork, thread end, activity, object period start, start process, next object event, next process node, next object period, and process thread fork.

13. A method of determining a plurality of the events that are causally connected as defined in claim 1, comprising the step of determining a UML behavioural diagram relating to process execution.

14. A method of determining a plurality of the events that are causally connected as defined in claim 1, comprising the step of determining a message sequence chart relating to process execution.

15. A method of determining a plurality of the events that are causally connected as defined in claim 1, comprising the step of determining design related information for use in one of design verification, business process modelling, performance modelling, and optimisation.

16. A method of determining a plurality of the events that are causally connected as defined in claim 1, wherein the recorded events form an angio trace defined as G_Trace=(N, Σ

_n, M_n, P, Ω

) where N is a set of recorded events;

Σ

_n is the alphabet of event time stamps;

M_n;

N→

Σ

_n is the mapping of events to time stamps;

P is a set of event predicates for identifying the type of an event; and

, Ω

is a set of partial-ordering relations.

17. A method of determining a plurality of the events that are causally connected as defined in claim 1, wherein the recorded information relating to an event comprises an event type from external event;

process thread begin event;

process activity event;

process thread fork event;

process thread half-join event; and

process thread end event.

18. A method of determining a plurality of the events that are causally connected as defined in claim 1, comprising the step of:

the replaying of execution of a scenario and system behavior on one of the actual system, a simulator tool, and a visualisation tool.

19. A method of determining a plurality of the events that are causally connected as defined in claim 1, wherein the process is a process executed in computer software and comprising the step of:

performing pattern analysis on the statements to detect at least one of software design and software execution patterns therein.

20. A method of determining a plurality of events that are causally connected for use with recorded information relating to the events occurring during execution of a process, the method comprising the steps of:

analysing the recorded information to determine a partial order of events from each of two relative perspectives;

combining the two partial orders of events to produce information relating to some forms of scenario causality and precedence causality.

21. A method of determining a plurality of events that are causally connected as defined in claim 20, wherein the recorded information relating to the events comprises at least an event type and two time stamps from each of two clocks wherein a clock from the two clocks is a logical clock and wherein causality is deduced in dependence upon precedence determined from the partial orders and recorded event types.