Scalable synchronous and asynchronous processing of monitoring rules

• US 7,539,974 B2
• Filed: 10/24/2003
• Issued: 05/26/2009
• Est. Priority Date: 10/24/2003
• Status: Active Grant

• Current Assignee: ServiceNow Incorporated
• Original Assignee: Microsoft Corporation
• Inventors: McCollum, Raymond W., Beck, Douglas R., Menzies, Steven J., Palanca, Radu R.
• Primary Examiner(s): Bullock, Jr.; Lewis A
• Assistant Examiner(s): YAARY, MICHAEL D
• Application Number:
  US10/693,072
• Publication Number:
  US 20050114494A1
• Time in Patent Office: 2,041 Days
• Field of Search: 717/117, 717/136
• US Class Current: 717/117
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• CPC Class Codes: G06F 2201/81 Threshold
• CPC Class Codes: G06F 2201/88 Monitoring involving counting
• CPC Class Codes: G06F 8/314 Parallel programming languages G06F8/313 takes precedence
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications
• CPC Class Codes: G06N 5/025 Extracting rules from data

Abstract

A rules runtime engine for scheduling and concurrently processing of rules. The engine efficiently runs a large number of rules in a parallel fashion. This is accomplished by authoring rules in a rule definition language, passing these rules through the translator for communication to the runtime engine and, scheduling and concurrently processing the translated instructions using the runtime engine. The engine also receives configuration data that instantiates the instructions thus, giving form to a living set of rules.

Claims

1. A system embodied on a computer readable storage medium that when executed on one or more processors facilitate processing rules, comprising:

a translator component that translates synchronous statements to asynchronous instructions using a synchronous programming model;

a runtime engine that reads the translated instructions and facilitates efficient scheduling and parallel processing of the translated instructions;

in which the instructions insert periodic yield instructions into the statements to facilitate at least one of yielding to runtime rule code execution switching and calling a utility function provided by the processors, and

in which the translated instructions are scheduled for processing based upon a polling structure, which processing occurs for at least one of the polling structure of a current frame and the polling structure at the top of a stack.

2. The system of claim 1, the statements are organized into a series of rule types.

3. The system of claim 2, the rule types express logic that determines the desired state of a target resource.

4. The system of claim 3, in response to a desired state, and action is taken.

5. The system of claim 1, the translator component facilitates instantiation of the asynchronous instructions.

6. The system of claim 1, the instructions facilitate maintaining all states by the runtime engine, which states include at least one of arguments and local variables.

7. The system of claim 1, the translator component facilitates depth-first traversal to generate at least one of labels and temporary variables for corresponding nodes.

8. The system of claim 1, the translator component translates modules of the rules into classes.

9. The system of claim 1, the instruction includes an address code representation to facilitate context switching by the runtime engine.

10. The system of claim 9, the address code representation employs at least three address codes, which representation is used when a statement or expression includes an asynchronous call.

11. The system of claim 1, the instructions are translated into a series of instruction blocks that are separated into switch-case blocks.

12. The system of claim 11, instructions within the instruction block are executed as a unit, and yield to runtime execution only between such instruction blocks.

13. The system of claim 11, the series of instruction blocks has associated therewith an update identifier that maintains which instruction block of the series is to be executed next upon reentry into the rule.

35. The system of claim 1, wherein the instructions are scheduled for processing in batches by the runtime engine, such that rules of a batch are scheduled for processing uniformly over associated time interval for processing the batch.

14. A system embodied on a computer readable storage medium that when executed on one or more processors facilitates concurrent processing of rules comprising:

a translator component that translates the rules into instructions for concurrent processing;

a runtime engine that schedules the instructions for processing and processes some or all of the instructions concurrently according to the schedule, and

means for injecting yield instructions into the rule to facilitate at least one of;

yielding execution of the rule to rule code execution switching during processing by the runtime engine, and to facilitate calling utility functions provided by the runtime engine

the instructions are translated and scheduled for processing based upon a polling structure, which processing occurs for at least one of the polling structure of a current frame and the polling structure at the top of a stack.

15. The system of claim 14, the runtime engine facilitates implicit concurrent processing of the rules.

16. The system of claim 14, the runtime engine receives both the instructions and configuration data, which configuration data specifies at least one of which rules to run and the parameters required to run the rule.

17. A system embodied on a computer readable storage medium that when executed on one or more processors facilitates processing rules in a model-based management architecture, comprising:

a plurality of rules that express health criteria for the architecture;

a translator component that translates the rules into asynchronous instructions for concurrent processing; and

a runtime engine that schedules the translated instruction for processing by injecting periodic yield instructions into the rules to facilitate at least one of;

yielding execution of the rule to rule code execution switching during processing by the runtime engine, and to facilitate calling utility functions provided by the runtime engine and processes some or all of the instructions concurrently according to the schedule,

wherein the runtime engine schedules execution of an execution stack based on a polling structure for the current frame or the polling structure that is at the top of the execution stack.

18. The system of claim 17, the runtime engine operates according to one of the instructions that suspends processing of code and waits for an event to occur, in response to which processing of the code is resumed and allowed to act on the event.

19. The system of claim 17, one of the plurality of rules invokes another rule.

20. The system of claim 17, the instruction component includes a language that facilitates looping, such that prior to jumping, a rule returns to the runtime engine to facilitate non-pre-emptive scheduling.

21. The system of claim 17, the translated instructions facilitate cooperative multitasking so that an execution state of a function is preserved, and constituted at a later time.

22. The system of claim 17, the instruction facilitate constructing a call frame, which call frame includes at least one of a function parameter, current instruction block, current function, and local variable.

23. The system of claim 17, the runtime engine includes a spreading algorithm that spreads execution of tasks over a duration of time beginning from an arbitrary time to reduce over-utilization.

24. A computer system embodying the system of claim 17.

25. A method of processing rules, comprising:

receiving a plurality of the rules;

translating the rules into instructions for communication to a runtime engine;

scheduling the translated instructions for processing by the runtime engine;

processing at least two of the plurality of instructions concurrently with the runtime engine;

receiving configuration data into the runtime engine to instantiate the rules;

injecting yield instructions into the rule to facilitate yielding execution of the rule to rule code execution switching during processing by the runtime engine, and to facilitate calling utility functions provided by the runtime engine; and

scheduling the translated instructions for processing based upon a polling structure, which processing occurs for at least one of the polling structure of a current frame and the polling structure at the top of a stack.

26. The method of claim 25, the translated instructions are translated into a series of instruction blocks, wherein commencement of execution of the instruction block causes the instruction block to be executed in its entirety before yielding to the runtime engine.

27. The method of claim 25, further comprising during a startup process, building a task list of rules marked for execution by the runtime engine at startup, and spreading out initiation of the rules in batches such that each batch of rules is scheduled for processing within a time configured time interval.

28. The method of claim 27, further comprising configuring the time interval based upon predetermined criteria, which criteria includes a number of processors utilized by the computer.

29. The method of claim 25, the instructions are scheduled for processing in batches by the runtime engine, such that rules of a batch are scheduled for processing uniformly over associated time interval for processing the batch.

30. The method of claim 25, scheduling is performed according to a non-preemptive scheduling regime.

31. A system embodied on a computer readable storage medium that when executed on one or more processors for processing rules, comprising:

means for receiving a plurality of the rules;

means for converting the rules into instructions;

means for translating the instructions for processing by a runtime engine;

means for scheduling and processing concurrently at least two of the plurality of instructions;

means for injecting yield instructions into the rule to facilitate yielding execution of the rule to rule code execution switching during processing by the runtime engine, and to facilitate calling utility functions provided by the runtime engine; and

means for scheduling the translated instructions for processing based upon a polling structure, which processing occurs for at least one of the polling structure of a current frame and the polling structure at the top of a stack.

32. The system of claim 31, the means for converting includes means for inserting control relinquishment code into the rule that determines where to relinquish control of the associated translated instruction during execution thereof, which relinquishment code is associated with a stack frame that contains at least one of parameters, local variables, and where in the translated instruction to jump upon reentry.

33. The system of claim 31, further comprising means for task switching between rules, where the translated instructions includes call frames to facilitate task switching.

34. A computer-readable medium having computer-executable instructions for performing concurrent processing of rules, comprising:

a translator component that translates synchronous rule statements into asynchronous instructions using a synchronous programming model;

in which instructions facilitate calling utility functions and yielding to runtime code execution switching of the runtime engine;

wherein the instructions inject yield instructions into the rule to facilitate yielding execution of the rule to rule code execution switching during processing by the runtime engine, and to facilitate calling utility functions provided by the runtime engine and

the instructions are translated for processing based upon a polling structure, which processing occurs for at least one of the polling structure of a current frame and the polling structure at the top of a stack.