Pattern matching process scheduler in message passing environment
View Patent ↗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.
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.