Dynamically allocating threads from a thread pool to thread boundaries configured to perform a service for an event

• US 8,397,237 B2
• Filed: 08/15/2005
• Issued: 03/12/2013
• Est. Priority Date: 08/17/2004
• Status: Active Grant

• Current Assignee: Intellectual Ventures I LLC (Intellectual Ventures LLC)
• Original Assignee: Shaw Parsing LLC (Intellectual Ventures LLC)
• Inventors: Rumelhart, Karl E., Tuttle, Timothy, Lueck, Jeremy S., Cano, Charles E., Huang, Alex, Benevidez, J. Joseph
• Primary Examiner(s): An, Meng
• Assistant Examiner(s): LEE, TAMMY EUNHYE
• Application Number:
  US11/205,263
• Publication Number:
  US 20060117318A1
• Time in Patent Office: 2,766 Days
• Field of Search: 718/104, 718/107, 719/316, 719/318, 709/314
• US Class Current: 718/104
• CPC Class Codes: G06F 2209/506 Constraint
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/505 considering the load

Abstract

Each of a plurality of thread boundaries comprises functionality to be performed for a given event by a single thread. A plurality of queues through which events may be routed may be coupled to the thread boundaries. A plurality of tasks may be configured in a defined relationship, each task being associated with a thread boundary and comprising a unit of code for performing a specific function. Resources may be allocated to thread boundaries based on queue depth.

Claims

1. A method, comprising:

determining, using a processing device, a load at a first thread boundary based on a comparison of a number of events being held at a first thread boundary queue coupled to the first thread boundary and a number of events being held in a second thread boundary queue coupled between the first thread boundary and a second thread boundary,

wherein the first and second thread boundaries are configured to perform a service for an event, the first thread boundary includes at least one thread and at least one task associated with at least a part of the service, and the at least one task is dynamically configured according to a high level language description; and

dynamically allocating, using the processing device, one or more additional threads from a thread pool, separate from the first and second thread boundaries, to the first thread boundary based on the determined load, wherein the one or more additional threads perform the at least a part of the service associated with the at least one task.

2. The method of claim 1, wherein determining the load further comprises determining the number of events to be processed by the first thread boundary.

3. The method of claim 2, wherein the first thread boundary queue is configured to hold the number of events.

4. The method of claim 3, wherein determining the load further comprises determining the number of events being held in the thread boundary queue.

5. The method of claim 2, wherein the first thread boundary is configured to perform the at least a part of the service on the number of events.

6. The method of claim 2, further comprising:

determining a second load for a second thread boundary; and

dynamically allocating a second set of one or more additional threads to the second thread boundary based on the determined second load, wherein the second set of one or more additional threads performs at least another part of the service.

7. The method of claim 6, wherein determining the second load comprises determining a second number of events to be processed by the second thread boundary.

8. The method of claim 1, wherein the at least one task has a defined relationship with at least one other task in order to perform the service for the event.

9. The method of claim 1, wherein the event is processed by the first and second thread boundaries in order to perform the service for the event.

10. The method of claim 1, wherein the event and a second event are processed in parallel in the first thread boundary.

11. The method of claim 1, wherein the high level language description is configured to automatically determine whether a configuration of the at least one task is logically consistent.

12. A computer system for processing events, the computer system comprising:

a plurality of thread boundaries, wherein the plurality of thread boundaries are configured to perform a service, wherein a first thread boundary in the plurality of thread boundaries includes at least one thread and at least one task configured to perform at least a part of the service;

a plurality of thread boundary queues coupled to the thread boundaries, wherein a first thread boundary queue is configured to hold one or more for routing to the first thread boundary, and wherein the first thread boundary is connected to a second thread boundary via a second thread boundary queue, and wherein the at least one task is dynamically configured according to a high level language description; and

a resource allocation module configured to allocate one or more additional threads to the first thread boundary from a thread pool, separate from the plurality of thread boundaries, based on a comparison of a number of events being held in the second thread boundary queue.

13. The system of claim 12, wherein the allocated one or more additional threads perform the at least the part of the service for the number of events being held in the first thread boundary queue.

14. The system of claim 12, wherein the resource allocation module is configured to allocate a first set of additional threads to the first thread boundary and a second set of additional threads to a second thread boundary in the plurality of thread boundaries further based on a first boundary queue depth, wherein the first thread boundary queue depth is based on a number of events being held in the first thread boundary queue, and a second thread boundary queue depth, wherein the second thread boundary queue depth is based on the second number of events being held in the second thread boundary queue.

15. The system of claim 12, further comprising:

a thread pool comprising the one or more threads to be allocated to thread boundaries based on thread boundary queue depth, the thread pool being coupled to the resource allocation module.

16. The system of claim 12, wherein at least one of the plurality of tasks is stateless.

17. The system of claim 12, further comprising a service utility configured to provide a utility, wherein the at least one task in the first thread boundary is configured to use the service utility to perform its part of the service.

18. The system of claim 17, wherein the service utility is configured to store a state.

19. The system of claim 12, wherein the at least one task of the first thread boundary has defined relationship with at least one other task in order to perform the service.

20. The system of claim 12, wherein an event in the number of events is processed by the plurality of thread boundaries in order to perform the service for the event.

21. The system of claim 20, wherein the event is passed from the first thread boundary to a second thread boundary queue, and wherein the second thread boundary processes the event.

22. The system of claim 12, wherein a first event and a second event in the one or more events are processed in parallel in the first thread boundary.

23. A computer system for processing events, the computer system comprising:

a first thread boundary comprising a first task, wherein the first task comprises processing functionality to perform a first function;

a second thread boundary comprising a second thread and a second task, wherein the second task comprises processing functionality to perform a second function;

a first thread boundary queue coupled to the first thread boundary;

a second thread boundary queue coupled to the second thread boundary, wherein the second thread boundary queue connects the first thread boundary and the second thread boundary and enqueues one or more events routed from the first thread boundary to the second thread boundary; and

a resource allocation module configured to allocate one or more additional threads from a thread pool, separate from the first and second thread boundaries, to the first and second thread boundaries, wherein one or more additional threads perform the first and second processing functions, wherein at least one of the first and second task is dynamically configured according to a high level language description, and wherein the one or more additional threads are allocated to the first thread boundary based on a comparison of a number of events being held in the first thread boundary queue with a number of events being held in the second thread boundary queue.

24. The system of claim 23 further comprising:

the thread pool comprising the one or more additional threads to be allocated to the first and second thread boundaries based on the first and second thread boundary queue depth.

25. The system of claim 23, wherein first and second tasks are stateless.

26. The system of claim 23, further comprising:

a service utility, wherein the service utility comprises a utility that is configured to be accessed by the first task or second task in performing the first processing function or the second processing function.

27. The system of claim 26, wherein the service utility is configured to store a state.

28. The system of claim 23, wherein the first task and the second task have a defined relationship in order to perform an overall functionality based on the first processing function and second processing function.

29. The system of claim 23, wherein the one or more events are processed by the first and second thread boundaries in order to perform an overall function defined by the first processing function and second processing function.

30. The system of claim 23, wherein a first event and a second event in the one or more events are processed in parallel.

31. A method for processing events, the method comprising:

receiving, using a processing device, a request for a service to be performed, wherein the request includes a first event;

dividing, using the processing device, logic of an application programmed to perform the service into a plurality of thread boundaries, each including at least one thread, according to a high level language description and dynamically configuring relationships between a plurality of tasks associated with the plurality of thread boundaries, wherein the plurality of thread boundaries are connected by a plurality of queues, wherein the first event is input into a first thread boundary in the plurality of thread boundaries via a first queue in the plurality of queues, and wherein the first thread boundary outputs a second event to a second queue in the plurality of queues, wherein the second queue is coupled between the first thread boundary and a second thread boundary;

determining, using the processing device, a load at the first thread boundary based on a comparison of a number of events held in the first queue with a number of events held in the second queue; and

dynamically allocating, using the processing device, one or more additional threads from a thread pool, separate from the plurality of thread boundaries, to the first thread boundary based on the determined load.