Amazon patents cloud scheduler that reserves space for new tasks

1. A system, comprising: one or more computing devices; wherein the one or more computing devices includes instructions that upon execution on the one or more computing devices cause the one or more computing devices to: acquire, from a computing service of a cloud provider network, a dynamically-allocated resource pool to execute a queue of tasks, wherein an amount of resources present in the dynamically-allocated resource pool changes over successive scheduling iterations of a task scheduling service of the cloud provider network; obtain an indication, via one or more programmatic interfaces, from a client of the task scheduling service, that the resources of the dynamically-allocated resource pool are to be assigned to individual tasks of the queue based at least in part on (a) respective share identifiers associated with the individual tasks and (b) a fairness-based reservation parameter; and conduct, at the task scheduling service, a plurality of scheduling iterations with respect to the queue, wherein a particular scheduling iteration of the plurality of scheduling iterations comprises at least: determining a set of currently-in-use share identifiers from a current task set comprising (a) one or more tasks present in the queue and (b) one or more currently-executing tasks which were in the queue prior to their execution, wherein a number of members of the set of currently-in-use share identifiers is smaller than a number of members of the current task set; computing, using at least the fairness-based reservation parameter, a first fraction of a capacity of the dynamically-allocated resource pool to be reserved for allocation, in a subsequent scheduling iteration, to tasks with share identifiers which are not members of the set of currently-in-use share identifiers; sorting share identifiers of at least a subset of the current task set based at least in part on respective aggregated resource usage metrics corresponding to the share identifiers; assigning, to one or more tasks selected from the queue based at least in part on a result of the sorting, one or more resources from a second fraction of the capacity of the dynamically-allocated resource pool, wherein the second fraction is determined at least in part from the first fraction; and causing the computing service to execute the one or more tasks selected from the queue on the one or more resources of the second fraction according to the assigning, wherein use of the at least the fairness-based reservation parameter in the computing of the first fraction of a capacity reduces a likelihood that the one or more tasks selected from the queue are starved of resources.