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

• US 6,988,139 B1
• Filed: 04/26/2002
• Issued: 01/17/2006
• Est. Priority Date: 04/26/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bocken, Xavier L., Shurtz, Chad R., Jervis, Robert B.
• Primary Examiner(s): BANANKHAH, MAJID A
• Application Number:
  US10/134,335
• Time in Patent Office: 1,362 Days
• Field of Search: 718/100, 718/102, 718/107, 718/104, 709/201, 709/203, 709/224, 709/226, 710/268
• US Class Current: 709/226
• CPC Class Codes: G06F 2209/5011 Pool
• 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

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.

Claims

1. 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.

2. The method of claim 1, further comprising the step of assigning a priority to each task that is ready for execution, as indicated by the status of the task in the second database.

3. The method of claim 2, wherein the step of providing a task includes the step of selecting a task with the highest priority for execution by the computing device that is available, from tasks assigned to any pool in the pool set of said computing device.

4. The method of claim 1, wherein steps (e) and (f) are repeated until one of the following has occurred:

(a) the job is completed, as determined from the status of the tasks of the job;

(b) a failure of a task has interrupted execution of the job; and

(c) the job has been manually interrupted.

5. The method of claim 1, wherein each task of a job is defined in a markup language file.

6. The method of claim 5, wherein each job in the plurality of computing jobs is defined by a task model that is coded in a separate markup language text file.

7. The method of claim 5, wherein a common task model is used for jobs of a specific type.

8. The method of claim 1, further comprising the step of providing a database that includes a plurality of templates, each template defining data for a task that may be executed by the plurality of computing devices.

9. The method of claim 1, wherein the job comprises testing a software program, and each task corresponds to a different test of the software program.

10. The method of claim 1, wherein each task is defined using at least one markup language tag.

11. The method of claim 1, further comprising the steps of:

(a) setting the status of any task that has failed to complete on a computing device, to indicate that the task has not yet been completed; and

(b) enabling the task that was not completed to again be made available for execution on a computing device.

12. A memory medium having processor executable machine instructions for performing the steps of claim 1.

13. 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.

14. The method of claim 13, further comprising the step of accessing a plurality of task templates that include data for completing tasks of the plurality of jobs, to process the plurality of jobs.

15. The method of claim 13, further comprising the steps of:

(a) determining that a task included in the plurality of task is a virtual task;

(b) producing a copy of the virtual task; and

(c) selecting and providing the copy of the virtual task to the available computing device for execution thereby.

16. The method of claim 13, further comprising the step of maintaining a status of each task in the task database, said status indicating whether the task is ready to be executed.

17. The method of claim 16, further comprising the steps of:

(a) determining a relative priority for the tasks included in the task database that are ready to be executed; and

(b) automatically selecting said one of the tasks from the task database with the highest priority, from among the tasks that are;

(i) then ready to be executed, as indicated by the status of the task; and

(ii) can be executed by the available computing device.

18. The method of claim 17, further comprising the step of:

(a) assigning each task to at least one pool, based upon the characteristics and capabilities required of a computing device to execute the task; and

(b) wherein the step of selecting said one of the tasks comprises the step of selecting a task for execution by the available computing device for which said at least one pool to which the task is assigned is included in a pool set assigned to the available computing device.

19. A memory medium having processor executable machine instructions for performing the steps of claim 13.

20. 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.

21. The control system of claim 20, wherein the machine instructions further cause the processor to assign a priority to each task that is currently ready for execution, as indicated by the status of the task in the second database.

22. The control system of claim 21, wherein the machine instructions further cause the processor to assign a task with the highest priority for execution by the computing device that is available, said task being selected from tasks assigned to any pool in the pool set of said computing device.

23. The control system of claim 20, wherein the job is terminated if:

(a) a failure of a task has interrupted execution of the job;

or

(b) the job has been manually interrupted.

24. The control system of claim 20, wherein each task of the job is defined in a markup language file.

25. The control system of claim 20, wherein the job is defined by a task model that is coded in a separate markup language text file.

26. The control system of claim 25, wherein the machine instructions further cause the processor to maintain a queue of jobs in the first database, wherein a common task model is used for jobs of a specific type.

27. The control system of claim 20, wherein the machine instructions further cause the processor to maintain a database having a plurality of templates, each template defining data for a task that may be executed by the plurality of computing devices.

28. The control system of claim 20, wherein the job comprises testing a software program, and each task corresponds to a different test of the software program.

29. The control system of claim 20, wherein each task is defined using at least one markup language tag.

30. The control system of claim 20, wherein the machine instructions further cause the processor to set the status of any task that has failed to complete on a computing device, to indicate that the task has not yet been completed, so that the task is again available for execution on a computing device.

31. 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.

32. The system of claim 31, wherein the machine instructions further cause the processor to access a plurality of task templates that include task-related data, for completing the tasks of the plurality of jobs.

33. The system of claim 31, wherein the machine instructions further cause the processor to maintain a status of each task in the task database, while a job is being processed, said status indicating whether the task is ready to be executed.

34. The system of claim 31, wherein the machine instructions further cause the processor to:

(a) determine a relative priority for the tasks included in the task database that are ready to be executed; and

(b) automatically select said one of the tasks with the highest priority from the task database, from among the tasks that are;

(i) then ready to be executed, as indicated by the status of the task; and

(ii) can be executed by the available computing device.

35. The system of claim 34, wherein the machine instructions further cause the processor to:

(a) assign each task to at least one pool, based upon the characteristics and capabilities required of a computing device to execute the task being assigned; and

(b) select said task for execution by the available computing device so that said at least one pool to which the task is assigned is included in a pool set assigned to the available computing device.