Pattern matching process scheduler with upstream optimization

• US 9,575,813 B2
• Filed: 07/17/2012
• Issued: 02/21/2017
• Est. Priority Date: 07/17/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Garrett, Charles D.
• Primary Examiner(s): Puente, Emerson
• Assistant Examiner(s): Labud, Jonathan R
• Application Number:
  US13/551,533
• Publication Number:
  US 20120317577A1
• Time in Patent Office: 1,680 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 2209/486 Scheduler internals
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues

Abstract

Processes in a message passing system may be launched when messages having data patterns match a function on a receiving process. The function may be identified by an execution pointer within the process. When the match occurs, the process may be added to a runnable queue, and in some embodiments, may be raised to the top of a runnable queue. When a match does not occur, the process may remain in a blocked or non-executing state. In some embodiments, a blocked process may be placed in an idle queue and may not be executed until a process scheduler determines that a message has been received that fulfills a function waiting for input. When the message fulfills the function, the process may be moved to a runnable queue.

Claims

1. A method comprising:

executing a first process on a computer processor, the first process including a function which consumes input data of a first input pattern and produces output data of a first output pattern;

determining that the function in the first process is waiting for input data of the first input pattern;

upon determining that the function in the first process is waiting for input data, setting the first process to a blocked state;

extracting the first input pattern;

examining a stored set of output patterns, each output pattern of the set of output patterns being, associated with a particular function of a particular output producing process, the examining including comparing the first input pattern to the stored set of output patterns;

based on the examined set of out patterns, selecting a second function of a second process, the second function of the second process having an output pattern which matches the first input pattern of the first function; and

causing the selected second function of the second process to execute such that the input data for the first function may be produced.

2. The method of claim 1 further comprising:

receiving said first process and said second process to execute; and

for both said first process and said second process;

identify the first input pattern, said first input pattern being a set of information received at a hold point to continue execution;

identify the first output pattern, said output pattern being a set of information transmitted to another process; and

store said first input pattern and said first output pattern in the metadata file.

3. The method of claim 2 further comprising:

determining that said first input pattern references a direct memory access location; and

storing said first input pattern in said direct memory access location.

4. The method of claim 3 further comprising:

identifying an interrupt related to said direct memory access location; and

storing said interrupt.

5. The method of claim 1, said second process being caused to execute on a prioritized basis by increasing the priority of the second process.

6. The method of claim 1, said first input pattern or said first output pattern comprising constants.

7. The method of claim 1, said first input pattern or said first output pattern comprising data types.

8. The method of claim 7, at least one of said data types having no value assigned during compiling.

9. The method of claim 8, said at least one of said data types having a reference to a value, said value being defined at runtime.

10. The method of claim 3, said identifying said first input pattern being determined by analysis of a first source code without executing the first source code, said first source code being intermediate code.

11. The method of claim 3, said identifying said first input pattern being determined during compiling of a first source code, said compiling being performed at runtime.

12. The method of claim 11, said first input pattern comprising a pattern element defined with a reference to a memory object.

13. The method of claim 12 further comprising:

retrieving a value for said pattern element by traversing said reference to said memory object.

14. The method of claim 1, said extracting said first input pattern being performed on an executable code, said executable code being intermediate code.

15. The method of claim 1, said extracted first input pattern being stored within an executable code.

16. A system comprising:

a computer processor;

a process scheduler operating on said computer processor, said process scheduler that;

executes a first process on a computer processor, the first process including a function which consumes input data of a first input pattern and produces out put data of a first output pattern;

determines that the function in the first process is waiting for input data of the first input pattern;

upon determing that the function in the first process is waiting for input data, sets the first process to a blocked state;

extracts the first input pattern;

examines a stored set of output patterns, each output pattern of the set of output patterns being associated with a particular function of a particular output producing process, the examining including comparing the first input pattern to the stored set of output patterns;

selects, based the examined set of output patterns, a second process, the second process having a second function which produces an output pattern that matches the first pattern of the first function; and

increases the priority of the selected second process such that the input data for the first function may be produced.

17. The system of claim 16 further comprising:

a monitoring agent that;

identifies the first input pattern;

determines that said first input pattern references a direct memory access location; and

when said direct memory access location changes state, creates a message having said first input pattern.

18. The method of claim 17, said monitoring agent that further:

identifies an interrupt related to said direct memory access location; and

creates said message when said interrupt is received.

19. The method of claim 16, said first process being written in a functional language.

20. The method of claim 16, said functional language being one of a group composed of:

Erlang;

Scala;

F#;

Lisp;

Clojure;

OCaml; and

Haskell.