Parallel task scheduling system for computers

• US 7,565,651 B1
• Filed: 05/25/2000
• Issued: 07/21/2009
• Est. Priority Date: 05/25/2000
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Carey, James E.
• Primary Examiner(s): Ho; Andy
• Application Number:
  US09/578,290
• Time in Patent Office: 3,344 Days
• Field of Search: 709/100, 709/103, 709/102, 709/305, 709/330, 718/106, 718100-105, 718/107, 719/310, 719/330
• US Class Current: 718/100
• CPC Class Codes: G06F 2209/5011 Pool
• CPC Class Codes: G06F 2209/5018 Thread allocation
• CPC Class Codes: G06F 2209/508 Monitor
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/544 Buffers; Shared memory; Pipes

Abstract

A parallel task scheduling system in a multi-threaded computing environment includes a plurality of parallel task queues. Each task queue is associated with a respective worker thread from a plurality of worker threads. Each new task is assigned to one of the task queues. That assignment process including selecting a random queue and, from that starting point, locating an empty queue (if one exists). The task is then placed on that empty queue for processing.

Typically, the worker thread associated with the identified task queue will process the queued task. If the worker thread is busy processing another task, the queued task may be stolen by a free thread. A waiting task, can thus be processed in an efficient manner.

Claims

1. In a multithreaded computing environment, a method of processing computing tasks, comprising:

defining a plurality of worker threads, each thread capable of processing a task;

defining a plurality of task queues, each task queue capable of queuing a plurality of tasks;

associating each task queue with a single respective worker thread;

assigning a task to a task queue in an essentially random fashion, by;

selecting a task queue;

determining whether the selected task queue is in a non-empty state;

repeating the steps of selecting and determining until an empty task queue is found; and

placing the task in the empty task queue; and

from a worker thread, processing a task, wherein the task is located, during the act of processing, in a task queue not associated with the thread.

2. The method of claim 1 wherein selecting comprises selecting a task queue believed to be empty.

3. The method of claim 1 further comprising, from a worker thread, processing a task from an associated task queue.

4. The method of claim 1 wherein determining whether the selected task queue is in a non-empty state comprises:

checking a task in the selected task queue to determine if the task is in the process of being removed by a worker thread; and

checking a task in the selected task queue to determine if the task is being acted upon by a worker thread.

5. The method of claim 1 wherein assigning a task to a task queue in an essentially random fashion comprises:

selecting a task queue;

determining whether the selected task queue is in a non-empty state;

if the selected task queue is in a non-empty state, stealing a next task in sequence from the non-empty selected task queue by moving the task from the non-empty selected task queue to an associated queue that is empty, otherwise repeating the steps of selecting and determining until a selected task queue in a non-empty state is found.

6. In a multithreaded computing environment, a method of processing computing threads, comprising:

defining a plurality of worker threads, each thread capable of processing a task;

defining a plurality of task queues, each task queue capable of queuing a plurality of tasks accessible by the worker threads;

associating each task queue with a single respective worker thread;

assigning a task to an assigned task queue, by;

selecting a task queue;

determining whether the selected task queue is in a non-empty state;

repeating the steps of selecting and determining until an empty task queue is found; and

placing the task in the empty task queue, the empty task queue as a result being designated the assigned task queue; and

in a worker thread not associated with the assigned task queue, processing the task, wherein the task is located, during the act of processing, in the assigned task queue.

7. The method of claim 6 where assigning comprises selecting the assigned task queue based on an essentially random number.

8. The method of claim 6 wherein selecting comprises selecting a task queue believed to be empty.

9. The method of claim 6 wherein determining whether the selected task queue is in a non-empty state comprises:

checking a task in the selected task queue to determine if the task is in the process of being removed by a worker thread; and

checking a task in the selected task queue to determine if the task is being acted upon by a worker thread.

10. The method of claim 6 wherein assigning a task to an assigned task queue comprises:

selecting a task queue;

determining whether the selected task queue is in a non-empty state;

if the selected task queue is in a non-empty state, stealing a next task in sequence from the non-empty selected task queue by moving the task from the non-empty selected task queue to an associated queue that is empty, otherwise repeating the steps of selecting and determining until a selected task queue in a non-empty state is found.

11. In a multithreaded computing environment, a system for processing tasks, comprising:

a plurality of worker threads, each thread capable of processing a task;

a plurality of task queues, each task queue capable of queuing a plurality of tasks and each task queue associated with a single respective worker thread;

a task scheduler for assigning a task to a task queue in an essentially random fashion, by;

selecting a task queue;

determining whether the selected task queue is in a non-empty state;

repeating the steps of selecting and determining until an empty task queue is found; and

placing the task in the empty task queue; and

a worker thread processing a task, wherein the task is located, during the act of processing, in a task queue not associated with the thread.

12. The system of claim 11 wherein the task scheduler selects a task queue believed to be empty for assigning the task.

13. The system of claim 11 further comprising a worker thread processing a task from an associated task queue.

14. In a multithreaded computing environment, a system for processing computing threads, comprising:

a plurality of worker threads, each thread capable of processing a task;

a plurality of task queues, each task queue capable of queuing a plurality of tasks accessible by the worker threads and each task queue associated with a respective worker thread;

a task scheduler for assigning a task to an assigned task queue, by;

selecting a task queue;

determining whether the selected task queue is in a non-empty state;

repeating the steps of selecting and determining until an empty task queue is found; and

placing the task in the empty task queue, the empty task queue as a result being designated the assigned task queue; and

wherein the assigned task is processed by a thread not associated with the assigned task queue, wherein the task is located, during the act of processing, in the assigned task queue.

15. The system of claim 14 wherein the task scheduler selects the assigned task queue based on an essentially random number.

16. The system of claim 14 wherein the task scheduler selects a task queue believed to be empty for assigning the task.

17. An article of manufacturing, comprising:

a computer-readable storage medium;

a computer implemented program for processing computing tasks in a multithreaded computing environment embodied in the storage medium, comprising instructions for;

defining a plurality of worker threads, each thread capable of processing a task;

defining a plurality of task queues, each task queue capable of queuing a plurality of tasks;

associating each task queue with a single respective worker thread;

assigning a task to a task queue in an essentially random fashion, by;

selecting a task queue;

determining whether the selected task queue is in a non-empty state;

repeating the steps of selecting and determining until an empty task queue is found; and

placing the task in the empty task queue; and

processing, in a worker thread, a task, wherein the task is located, during the act of processing, in a task queue not associated with the thread.

18. The article of claim 17 wherein the instructions for selecting comprise selecting a task queue believed to be empty.

19. The article of claim 17 further comprising instructions for processing, in a worker thread, a task from an associated task queue.

20. An article of manufacture, comprising:

a computer-readable storage medium;

a computer-implemented program for processing computing threads, in a multithreaded computing environment embodied in the storage medium, the program comprising instructions for;

defining a plurality of worker threads, each thread capable of processing a task;

defining a plurality of task queues, each task queue capable of queuing a plurality of tasks accessible by the worker threads;

associating each task queue with a single respective worker thread;

assigning a task to an assigned task queue, by;

selecting a task queue;

determining whether the selected task queue is in a non-empty state;

repeating the steps of selecting and determining until an empty task queue is found; and

placing the task in the empty task queue, the empty task queue as a result being designated the assigned task queue; and

in a worker thread not associated with the assigned task queue, processing the task, wherein the task is located, during the act of processing, in the assigned task queue.

21. The article of claim 20 where the instructions for assigning comprise selecting the assigned task queue based on an essentially random number.

22. The article of claim 20 wherein the instructions for selecting comprise selecting a task queue believed to be empty.

23. In a multithreaded computing environment, a system for processing computing tasks, comprising:

means for defining a plurality of worker threads, each thread capable of processing a task;

means for defining a plurality of task queues, each task queue capable of queuing a plurality of tasks;

means for associating each task queue with a single respective worker thread;

means for assigning a task to a task queue in an essentially random fashion, by;

means for selecting a task queue;

means for determining whether the selected task queue is in a non-empty state;

means for repeating the steps of selecting and determining until an empty task queue is found; and

means for placing the task in the empty task queue; and

from a worker thread, means for processing a task, wherein the task is located, during the act of processing, in a task queue not associated with the thread.

24. The system of claim 23 wherein the means for selecting comprises means for selecting a task queue believed to be empty.

25. The system of claim 23 further comprising, from a worker thread, means for processing a task from an associated task queue.

26. In a multithreaded computing environment, a method of processing computing tasks, comprising:

defining a plurality of worker threads, each thread capable of processing a task;

defining a plurality of task queues, each task queue capable of queuing a plurality of tasks;

associating each task queue with a single respective worker thread;

assigning a task to an empty task queue in an essentially random fashion, by;

selecting a task queue;

determining whether the selected task queue is in a non-empty state;

repeating the steps of selecting and determining until an empty task queue is found; and

placing the task in the empty task queue; and

from a worker thread, processing a task, wherein the task is located, during the act of processing, in a task queue not associated with the thread.

27. The method of claim 26 wherein selecting comprises selecting a task queue believed to be empty.

28. The method of claim 26 further comprising, from a worker thread, processing a task from an associated task queue.

29. The method of claim 26 wherein determining whether the selected task queue is in a non-empty state comprises:

checking a task in the selected task queue to determine if the task is in the process of being removed by a worker thread; and

checking a task in the selected task queue to determine if the task is being acted upon by a worker thread.

30. The method of claim 26 wherein assigning a task to an empty task queue in an essentially random fashion comprises:

selecting a task queue;

determining whether the selected task queue is in a non-empty state;

if the selected task queue is in a non-empty state, stealing a next task in sequence from the non-empty selected task queue by moving the task from the non-empty selected task queue to an associated queue that is empty, otherwise repeating the steps of selecting and determining until a selected task queue in a non-empty state is found.

31. In a multithreaded computing environment, a method of processing computing tasks, comprising:

defining a plurality of worker threads, each thread capable of processing a task;

defining a plurality of task queues, each task queue capable of queuing a plurality of tasks;

associating each task queue with a single respective worker thread, an associated task queue capable of storing tasks assigned to an associated worker thread;

assigning a task to a task queue in an essentially random fashion, comprising;

using a random number generator to identify an initial task queue;

upon determining that the initial task queue is in a non-empty state, searching other task queues for an empty task queue; and

upon finding an empty task queue, storing the task in the empty task queue; and

from a worker thread, processing a task, wherein the task is located, during the act of processing, in a task queue not associated with the worker thread.

32. The method of claim 31 wherein processing comprises:

from a worker thread, processing a task from a task queue associated with the thread.

33. The method of claim 31 comprising:

determining that the initial task queue is in a non-empty state by;

checking a task in the initial task queue to determine if the task is in the process of being removed by a worker thread; and

checking a task in the initial task queue to determine if the task is being acted upon by a worker thread.

34. The method of claim 31 wherein assigning a task to a task queue in an essentially random fashion comprises:

using a random number generator to identify an initial task queue;

determining whether the initial task queue is in a non-empty state;

if the initial task queue is in a non-empty state, stealing a next task in sequence from the non-empty initial task queue by moving the task from the non-empty initial task queue to an associated queue that is empty, otherwise repeating the steps of using and determining until an initial task queue in a non-empty state is found.

35. In a computer, a system for processing computing threads, comprising:

a plurality of worker threads, each thread capable of processing a task;

a plurality of task queues, each task queue capable of queuing a plurality of tasks accessible by the worker threads and each task queue associated with a single respective worker thread, the associated task queue capable of storing tasks assigned to the associated worker thread;

a task scheduler for assigning a task to an assigned task queue in an essentially random fashion, the task scheduler using a random number generator to identify an initial task queue, upon determining that the initial task queue is in a non-empty state, searching other task queues for an empty task queue, and upon finding an empty task queue, the task scheduler stores the task in the empty task queue, the empty task queue as a result being designated the assigned task queue, a worker thread processing the task, wherein the task is located, during the act of processing, in the assigned task queue, which is not associated with the worker thread.

36. The system of claim 35 wherein a task scheduler comprises:

a task scheduler for assigning a task to a task queue in an essentially random fashion, the task scheduler using a random number generator to identify an initial task queue, upon determining that the initial task queue is in a non-empty state, searching other task queues for an empty task queue, and upon finding an empty task queue, the task scheduler stores the task in the empty task queue, the worker thread processing a task assigned to the associated task queue.

37. The system of claim 35 wherein the task scheduler comprises:

a task scheduler for assigning a task to an assigned task queue in an essentially random fashion, the task scheduler using a random number generator to identify an initial task queue, the task scheduler determining that the initial task queue is in a non-empty state by;

checking a task in the initial task queue to determine if the task is in the process of being removed by a worker thread, and checking a task in the initial task queue to determine if the task is being acted upon by a worker thread, upon determining that the initial task queue is in a non-empty state, searching other task queues for an empty task queue, and upon finding an empty task queue, the task scheduler stores the task in the empty task queue, the empty task queue as a result being designated the assigned task queue, a worker thread processing the task, wherein the task is located, during the act of processing, in the assigned task queue, which is not associated with the worker thread.

38. The system of claim 35 wherein the task scheduler comprises:

a task scheduler for assigning a task to an assigned task queue in an essentially random fashion, the task scheduler using a random number generator to identify an initial task queue, the task scheduler determining whether the initial task queue is in a non-empty state, if the initial task queue is in a non-empty state, stealing a next task in sequence from the non-empty initial task queue by moving the task from the non-empty initial task queue to an associated queue that is empty, otherwise using and determining until an initial task queue in a non-empty state is found, the associated empty task queue as a result being designated the assigned task queue, a worker thread processing the task, wherein the task is located, during the act of processing, in the assigned task queue, which is not associated with the worker thread.

39. In a multithreaded computing environment, a system for processing computing threads, comprising:

means for defining a plurality of worker threads, each thread capable of processing a task;

means for defining a plurality of task queues, each task queue capable of queuing a plurality of tasks accessible by the worker threads;

means for associating each task queue with a single respective worker thread;

means for assigning a task to an assigned task queue, by;

means for selecting a task queue;

means for determining whether the selected task queue is in a non-empty state;

means for repeating the steps of selecting and determining until an empty task queue is found; and

means for placing the task in the empty task queue, the empty task queue as a result being designated the assigned task queue; and

in a worker thread not associated with the assigned task queue, means for processing the task, wherein the task is located, during the act of processing, in the assigned task queue.

40. In a multithreaded computing environment, a system for processing computing tasks, comprising:

means for defining a plurality of worker threads, each thread capable of processing a task;

means for defining a plurality of task queues, each task queue capable of queuing a plurality of tasks;

means for associating each task queue with a single respective worker thread;

means for assigning a task to an empty task queue in an essentially random fashion, by;

means for selecting a task queue;

means for determining whether the selected task queue is in a non-empty state;

means for repeating the steps of selecting and determining until an empty task queue is found; and

means for placing the task in the empty task queue; and

from a worker thread, means for processing a task, wherein the task is located, during the act of processing, in a task queue not associated with the thread.

41. In a multithreaded computing environment, a system for processing computing tasks, comprising:

means for defining a plurality of worker threads, each thread capable of processing a task;

means for defining a plurality of task queues, each task queue capable of queuing a plurality of tasks;

means for associating each task queue with a single respective worker thread, an associated task queue capable of storing tasks assigned to an associated worker thread;

means for assigning a task to a task queue in an essentially random fashion, comprising;

means for using a random number generator to identify an initial task queue;

upon determining that the initial task queue is in a non-empty state, means for searching other task queues for an empty task queue; and

upon finding an empty task queue, means for storing the task in the empty task queue; and

from a worker thread, means for processing a task, wherein the task is located, during the act of processing, in a task queue not associated with the worker thread.

42. The system of claim 41 wherein means for processing comprises:

from a worker thread, means for processing a task from a task queue associated with the worker thread.