Pattern matching process scheduler in message passing environment

• US 8,707,326 B2
• Filed: 07/17/2012
• Issued: 04/22/2014
• Est. Priority Date: 07/17/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Concurix Corporation
• Inventors: Garrett, Charles D.
• Primary Examiner(s): Truong, Lechi
• Application Number:
  US13/551,318
• Publication Number:
  US 20120317587A1
• Time in Patent Office: 644 Days
• Field of Search: 719/318, 718/100
• US Class Current: 719/310
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

Processes in a message passing system may be unblocked when messages having data patterns match data patterns of a function on a receiving 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 performed as part of an operating system, said method comprising:

executing a first process on a computer processor, said first process comprising a plurality of functions and said first process being managed by said operating system;

determining that a first function is waiting for a first input, said first input being defined by a first pattern and setting said first process to a blocked state;

receiving a first message, said first message comprising first data;

while said first process is in said blocked state, attempting to match said first data in said first pattern;

when said first data matches said first pattern, causing said first process to resume execution; and

when said first data does not match said first pattern, leaving said first process in said blocked state;

when said first data matches said first pattern, setting said first process in a runnable state;

when said first data matches said first pattern, moving said first process to a priority position in a runnable queue.

2. The method of claim 1 further comprising:

when said first data does not match said first pattern, adding said first message to a message queue.

3. The method of claim 2 further comprising:

matching said second pattern to a second message; and

causing said second function to execute using said second data in said second message.

4. The method of claim 3 further comprising:

when said first data matches said first pattern, placing said first process in a runnable queue.

5. The method of claim 1 further comprising:

determining that a second function is waiting for said second input, said second input being defined by a second pattern, said second function being comprised in said first process; and

attempting to match said second pattern to second data associated with messages in said message queue.

6. The method of claim 1, said first process being written in a functional language.

7. The method of claim 1, said functional language being one of a group composed of:

Erlang;

Scala;

F#;

Lisp;

Clojure;

OCaml; and

Haskell.

8. The method of claim 1, said first process being written in an imperative language.

9. A system comprising:

a computer processor;

a message passing system that receives messages from executing processes and passes said messages to other processes;

a runnable queue comprising processes ready for execution;

a process scheduler that;

causes a first process to execute on said computer processor, said first process comprising a plurality of functions;

determines that a first function is waiting for a first input, said first input being defined

by a first pattern and setting said first process to a blocked state;

receives a first message, said first message comprising first data for said first process;

attempts to match said first data to said first pattern;

when said first data matches said first pattern, causes said first process to resume execution; and

when said first data does not match said first pattern, leaves said first process in said blocked state;

said process scheduler being a component of an operating system;

said process scheduler that further;

when said first data matches said first pattern, places said first process in said runnable queue process scheduler that further;

when said first data matches said first pattern, moves said first process to a priority position in said runnable queue.

10. The system of claim 9 further comprising:

a message queue;

said process scheduler that further;

when said first data does not match said first pattern, adds said first message to a message queue.

11. The system of claim 10, said message queue containing messages only for said first process.

12. The system of claim 9, said process scheduler that further:

determines that a second function is waiting for said second input, said second input being defined by a second pattern, said second function being comprised in said first process; and

attempts to match said second pattern to second data associated with messages in said message queue.

13. The system of claim 12, said process scheduler that further:

matches said second pattern to a second message; and

causes said second function to execute using said second data in said second message.

14. The system of claim 9, said process scheduler that further:

when said first data matches said first pattern, sets said first process in a runnable state.

15. The system of claim 9, said first process being written in a functional language.

16. The system of claim 15, said functional language being one of a group composed of:

Erlang;

Scala;

F#;

Lisp;

Clojure;

OCaml; and

Haskell.

17. The system of claim 9, said first process being written in an imperative language.

18. A method performed by an operating system, said method comprising:

executing a first process on a first computer processor, said first process comprising a plurality of functions, said first process being managed by said operating system;

during said executing, maintaining an execution pointer at a currently executing location within said first process;

determining that a first function is waiting for a first input, said first input being defined by a first pattern and setting said first process to a blocked state, and storing said execution pointer at said first function;

receiving a first message, said first message being addressed to said first process;

examining said execution pointer to identify said first pattern;

comparing said first pattern to said first message while said first process is in said blocked state;

when said first data matches said first pattern, causing said first process to resume execution and to consume said first message;

when said first data matches said first pattern, setting said first process in a runnable state;

when said first data matches said first pattern, moving said first process to a priority position in said runnable queue.

19. The method of claim 18 further comprising:

receiving a second message, said second message being addressed to said first process;

examining said execution pointer to identify said first pattern;

comparing said first pattern to said second message while said first process is in said blocked state; and

when said second data does not match said first pattern, causing said first process to remain in said blocked state.

20. The method of claim 18 further comprising:

when said first data matches said first pattern, moving said first process into a runnable queue.

21. The method of claim 18 further comprising:

when determining that said first function is waiting for said first input, removing said first process from a runnable queue.

22. The method of claim 21 further comprising:

placing said first function in an idle queue.

23. The method of claim 22 further comprising:

when causing said first process to resume execution, moving said first process into a runnable queue.

24. The method of claim 23:

said first process being executed on said first computer processor prior to being placed in a blocked state; and

executing said first process on a second computer processor after being placed into said runnable queue.