US 6,988,139 B1Granted

Distributed computing of a job corresponding to a plurality of predefined tasks

AssigneeMicrosoft Corporation

InventorsRobert B. Jervis, Xavier L. Bocken, Chad R. Shurtz

Life of this patent

Estimating the term…

Loading patent…

Abstract

In a distributed computing environment, a queue of jobs is maintained on a job database, along with parameters for each of the computing devices available to process the jobs. A task model defining the job is provided for generating a plurality of tasks comprising each job. The tasks are maintained in a tuple database, along with the status of each task, indicating when each task is ready for processing. As a computing device becomes available to process a task, its capabilities are matched with those required to complete tasks that are ready for processing and the highest priority task meeting those requirements is assigned to the computing device to be processed. These steps are repeated until all the tasks required for the job have been processed, or the job is otherwise terminated.

Claims35

Dependent claims

A method for processing a job using a plurality of computing devices that communicate over a network, the job having at least one task to be done on a computing device, comprising the steps of:

(a) creating a first database that includes a queue of computing jobs in which the job is listed, and parameters for each of the plurality of computing devices, said parameters indicating capabilities and characteristics of each computing device;
(b) assigning each computing device from the plurality of computing devices to at least one pool set, based upon the parameters of the computing device, each pool set including at least one pool;
(c) creating a second database in which each task of the job is indicated, along with a status indicating when the task is ready for execution, relative to any other task of the job;
(d) assigning each task of the job to a specific pool, based upon capabilities and characteristics needed for a computing device to carry out the task, to ensure that the task is able to be carried out by any computing device included in the specific pool to which the task is assigned;
(e) as a computing device from the plurality of computing devices becomes available to carry out a task, enabling said computing device to automatically request a task assigned to any pool in a pool set of the computing device;
(f) in response to the request, providing a task assigned to any pool in the pool set of the computing device to said computing device for execution by the computing device, if the status of said task in the second database indicates that the task is ready for execution;
and
(g) repeating steps (e) and (f) to complete the job.

5 more elements

A method for managing processing of a plurality of jobs in a distributed computing environment using a plurality of computing devices to complete the plurality of jobs, comprising the steps of:

(a) adding each of the plurality of jobs as the job is submitted, to a job queue that is maintained on a job database, said job database also including a list of the computing devices and parameters for each computing device comprising characteristics and capabilities of each computing device that form a basis for assigning each of the computing devices to a pool set, each pool set comprising at least one pool;
(b) providing a task model for each job, said task model being used to generate a plurality of tasks of the job, said plurality of tasks being included in a task database;
(c) enabling any available computing device to request that one of the plurality of tasks included in the task database be provided for execution by the available computing device;
(d) in response to said request from an available computing device, automatically selecting one of the tasks from the task database for execution by the available computing device, said one of the tasks being selected based upon the parameters of the available computing device and corresponding requirements for executing the task selected, so as to ensure that said available computing device can execute the task that is being selected;
and
(e) repeating steps (c) and (d) to process the plurality of jobs in the job queue.

3 more elements

A control system for a distributed computing system having a plurality of computing devices that are used to process a job, comprising:

(a) a memory in which a plurality of machine instructions are stored;
(b) a network interface coupled in communication with the plurality of computing devices;
and
(c) a processor coupled to the memory and the network interface, said processor executing the machine instructions, to carry out a plurality of functions, including:
(i) maintaining a first database that includes parameters for each of the plurality of computing devices in the plurality of computing devices, said parameters indicating capabilities and characteristics of each computing device;
(ii) assigning each computing device in the plurality of computing devices to at least one pool set, based upon the parameters of the computing device, each pool set including at least one pool;
(iii) generating a second database that includes a plurality of tasks of the job, each task having a status indicating whether the task is currently ready for execution by one of the computing devices;
(iv) assigning each task of the job to a specific pool, based upon capabilities and characteristics needed of a computing device to carryout the task, to ensure that the task is able to be carried out by any computing device included in the specific pool to which the task is assigned;
(v) receiving a request from any computing device from the plurality of computing devices that is currently available to carry out a task, to execute a task assigned to any pool in a pool set of the computing device;
(vi) in response to the request, providing a task assigned to any pool in the pool set of the computing device to said computing device for execution by the computing device, if the status of said task in the second database indicates that the task is ready for execution;
and
(vii) repeating the preceding two steps until the job is completed or terminated.

9 more elements

A system for managing processing of a plurality of jobs in a distributed computing environment using a plurality of computing devices to complete the plurality of jobs, comprising:

(a) a memory in which a plurality of machine instructions are stored;
(b) a network interface coupled in communication with the plurality of computing devices;
and
(c) a processor coupled to the memory and the network interface, said processor executing the machine instructions, to carry out a plurality of functions, including:
(i) maintaining a job database in which a job queue includes the plurality of jobs to be processed, said job database also including a list of the computing devices and parameters for each computing device comprising characteristics and capabilities of each computing device that form the basis of the assignment of each of the computing devices to a pool set, each pool set comprising at least one pool;
(ii) using a task model input for each job to generate a plurality of tasks of the job, and maintaining a task database that includes said plurality of tasks;
(iii) receiving a request from any available computing device be provided one of the plurality of tasks included in the task database, for execution by the available computing device;
(iv) in response to said request from an available computing device, automatically selecting one of the tasks from the task database for execution by the available computing device, said one of the tasks being selected based upon the parameters of the available computing device and corresponding requirements for executing the task selected, so as to ensure that said available computing device can execute the task selected;
and
(v) repeating the preceding two steps as required to process the plurality of jobs in the job queue.

7 more elements

Dependencies are inferred from the claim text.