Task distribution method and system
Systems and methods for task distribution are provided. A total number of available computing system's processing units is defined, where the total number of available processing units includes a set of regular processing units available for executing tasks and a set of processing units that constitute the reserve pool. Tasks are assigned to processing units. The number of processing units assigned to the next task in the queue is no more than the total number of processing units available at the time, multiplied by the availability ratio. Iterative assignment of processing units to tasks according to the method described is performed as long as there are idle processing units available for task execution, when no more processing units are available, the processing units from the reserve pool are assigned. As a result, the method allows processing units to be available for allocation to a new incoming task at any time.
1. A method for task distribution, the method comprising:
determining a total number of a computing system's idle processing units available to be provisioned to existing tasks, including a first set of idle processing units available for executing regular tasks and a second set of idle processing units that constitute a reserve pool;
selecting an availability ratio, wherein the availability ratio is less than one;
assigning, to a first task in a processing queue, a first number of processing units from the first set, wherein the first number of processing units assigned is not greater than a number of idle processing units in the first set multiplied by the availability ratio, and not less than one such processing unit;
determining a remaining number of idle processing units in the first set; and
assigning, to a second task in the processing queue, a second number of processing units from the first set, wherein the second number of processing units assigned is not greater than the remaining number of idle processing units in the first set multiplied by the availability ratio, and not less than one such processing unit,
wherein when no remaining idle processing units in the first set are available for executing regular tasks, a next task is assigned at least one processing unit from the reserve pool.
2. The method of claim 1 , wherein a total number of tasks to which no processing unit has been assigned is further defined, and wherein the tasks are chosen for processing according to their priority with the subsequent assignment of the first number of processing units according to their priority.
3. The method of claim 1 , wherein a set of processing units available for threading (PAT) is further allocated from the first set of processing units available for executing regular tasks, and wherein a number of processing units in the set PAT is determined using a formula PAT=P−T−ER, where P is a total number of processing units available for executing regular tasks, T is a total number of distributed tasks, and ER is a number of processing units allocated to the reserve pool.
4. The method of claim 1 , wherein the second set of processing units constituting the reserve pool has a fixed number of processing units.
5. The method of claim 3 , wherein the number of processing units (PUT) available for executing a task is max (2, (PTT+1)*PTP), where PTT is a current number of processing units available for threading, and PTP is the percentage of processing units allowed for threading of the task.
6. The method of claim 5 , wherein the iterative assignment of processing units to the tasks is based on calculation of new number of processing units, where the new number of processing units for the task (NPUT) is max (CPUT, min (PUT, CPUT+FAT, ST)), where CPUT is a number of processing units used by the task at the moment of time; PUT is a number of processing units available for allocation to the task, wherein FAT is a maximum number of idle processing units available for threading, where FAT=F−ER; F is a total number of idle processing units at the moment of time; ER is a number of processing units allocated to the reserve pool; and ST is a maximum number of processing units required to process the task.
7. The method of claim 1 , wherein the reserve pool includes processing units not assigned to tasks when there are idle units in the set of processing units for executing regular tasks.
8. The method of claim 1 , wherein a number of idle processing units in the first set that are available for executing regular tasks at a second time, subsequent to the first time, is based on a difference between the number of idle processing units in the first set that are available for executing regular tasks at the first time and the first number of processing units assigned for the first task.
9. A non-transitory computer-readable storage medium having machine instructions stored therein, the instructions being executable by a processor to cause the processor to perform operations comprising:
determining a total number of a computing system's idle processing units available to be provisioned to existing tasks, including a first set of idle processing units available for executing regular tasks and a second set of idle processing units that constitute a reserve pool;
selecting an availability ratio, wherein the availability ratio is less than one;
assigning, to a first task in a processing queue, a first number of processing units from the first set, wherein the first number of processing units assigned is not greater than a number of idle processing units in the first set, multiplied by the availability ratio, and not less than one such processing unit;
determining a remaining number of idle processing units in the first set; and
assigning, to a second task in the processing queue, a second number of processing units from the first set, wherein the second number of processing units assigned is not greater than the remaining number of idle processing units in the first set multiplied by the availability ratio, and not less than one such processing unit,
wherein when no remaining idle processing units in the first set are available for executing regular tasks, a next task is assigned at least one processing unit from the reserve pool.
10. The non-transitory computer-readable storage medium of claim 9 , operations further comprising determining a total number of tasks for which no processing units have been assigned, wherein tasks are chosen for processing according to their priority with the subsequent assignment of the first number of processing units according to their priority.
11. The non-transitory computer-readable storage medium of claim 9 , operations further comprising allocating additional processing units for threading (PAT) from the first set of processing units available for executing regular tasks, and wherein a number of processing units in PAT is determined using the formula PAT=P−T−ER, where P is a total number of processing units available for executing regular tasks, T is a total number of distributed tasks, and ER is a number of processing units allocated to the reserve pool.
12. The non-transitory computer-readable storage medium of claim 9 , wherein the second set of processing units constituting the reserve pool has a fixed number of processing units.
13. The non-transitory computer-readable storage medium of claim 11 , wherein the number of processing units (PUT) available for executing complex tasks is max (2, (PTT+1)*PTP), where PTT is a current number of processing units available for threading, and PTP is a percentage of processing units allowed for threading of this task.
14. The non-transitory computer-readable storage medium of claim 13 , wherein the iterative assignment of processing units to tasks at the moment of time is based on a calculation of a new amount of processing units, where the new amount of processing units for the task (NPUT) is max (CPUT, min (PUT, CPUT+FAT, ST)), where CPUT is a number of processing units used by this task at the moment of time; PUT is a number of processing units available for allocation to this task; FAT is a maximum number of idle processing units available for threading, where FAT=F-ER; F is a total number of idle processing units at the moment of time; ER is a number of processing units allocated to the reserve pool; and ST is a maximum number of processing units required to process this task.
15. A system for task distribution among a set of computing devices, including:
one or more data processors; and
one or more storage devices storing instructions that, when executed by the one or more data processors, cause the one or more data processors to perform operations comprising:
determining a total number of a computing system's idle processing units available to be provisioned to existing tasks, including a first set of idle processing units available for executing regular tasks and a second set of idle processing units that constitute a reserve pool;
selecting an availability ratio, wherein the availability ratio is less than one;
assigning, to a first task in a processing queue, a first number of processing units from the first set, wherein the first number of processing units assigned is not greater than a number of idle processing units in the first set, multiplied by the availability ratio, and not less than one such processing unit;
determining a remaining number of idle processing units in the first set; and
assigning, to a second task in the processing queue, a second number of processing units from the first set, wherein the second number of processing units assigned is not greater than the remaining number of idle processing units in the first set multiplied by the availability ratio, and not less than one such processing unit,
wherein when no remaining idle processing units in the first set are available for executing regular tasks, a next task is assigned at least one processing unit from the reserve pool.
16. The system of claim 15 , wherein a total number of tasks to which no processing unit has been assigned is further determined, and wherein the tasks are chosen for processing according to their priority with the subsequent assignment of the first number of processing units according to their priority.
17. The system of claim 15 , wherein additional processing units for threading (PAT) are allocated from the first set of processing units available for executing regular tasks, and wherein a number of processing units in PAT is determined using the formula PAT=P−T−ER, where P is the total number of processing units available for executing regular tasks, T is the total number of distributed tasks, and ER is the number of processing units allocated to the reserve pool.
18. The system of claim 15 , wherein the second set of processing units constituting the reserve pool has a fixed number of processing units.
19. The system of claim 17 , wherein the number of processing units (PUT) available for executing complex tasks is max (2, (PTT+1)*PTP), where PTT is the current number of processing units available for threading, and PTP is the percentage of processing units allowed for threading of this task.
20. The system of claim 19 , wherein the iterative assignment of processing units to tasks at the moment of time is based on a calculation of a new number of processing units, and wherein the new number of processing units for this task (NPUT) is max (CPUT, min (PUT, CPUT+FAT, ST)), where CPUT is a number of processing units used by this task at the moment; PUT is a number of processing units available for allocation to this task; FAT is a maximum number of idle processing units available for threading, where FAT=F−ER; where F is a total number of idle processing units at the moment of time; ER is a number of processing units allocated to the reserve pool; and ST is a maximum number of processing units required to process this task.