US 8,276,146 B2Granted

Grid non-deterministic job scheduling

AssigneeInternational Business Machines Corporation

InventorsChristopher James Dawson, Craig William Fellenstein, Rick Allen Hamilton, II, Joshy Joseph

Life of this patent

Estimating the term…

Loading patent…

Abstract

The present invention is method for scheduling jobs in a grid computing environment without having to monitor the state of the resource on the gird comprising a Global Scheduling Program (GSP) and a Local Scheduling Program (LSP). The GSP receives jobs submitted to the grid and distributes the job to the closest resource. The resource then runs the LSP to determine if the resource can execute the job under the conditions specified in the job. The LSP either rejects or accepts the job based on the current state of the resource properties and informs the GSP of the acceptance or rejection. If the job is rejected, the GSP randomly selects another resource to send the job to using a resource table. The resource table contains the state-independent properties of every resource on the grid.

Claims27

Dependent claims

A method for scheduling a job on a grid wherein a scheduler does not have to keep track of a plurality of state dependent resource properties, the method comprising:

a computer receiving notification that the job has been submitted to the grid from a submitting computer;
the computer determining whether the submitting computer is a resource of the grid;
responsive to the determination that the submitting computer is not the resource, the computer sending the job to a resource closest to the submitting computer;
running a local scheduling program at a resource with the job;
the computer determining whether the resource with the job accepted the job;
responsive to the determination that the resource with the job did not accept the job, adding the resource with the job to an attempted resources list, determining the remaining resources capable of executing the job using a resource table, removing from consideration the resource on the attempted resources list;
the computer determining if any remaining resources remain after removing from consideration the resource on the attempted resources list;
and responsive to the determination that remaining resources remain, randomly selecting a second resource from a plurality of remaining resources and sending the job to the second resource;
and
responsive to the determination that remaining resources do not remain, determining if a preset number of iterations have been reached;
responsive to the determination that the preset number of iterations have been reached, clearing the attempted resources list, waiting a specified amount of time, and re-determining the remaining resources capable of executing the job using the resource table.

8 more elements

A method for scheduling a job on a grid wherein a resource determines whether to accept the job, the method comprising:

a computer receiving notification that the job has been submitted to the grid from a submitting computer;
the computer determining whether the submitting computer is a resource of the grid;
responsive to the determination that the submitting computer is not the resource, the computer sending the job to a resource closest to the submitting computer;
running a local scheduling program at a resource with the job;
the computer determining whether the resource with the job can execute the job;
responsive to the determination that the resource with the job cannot execute the job, adding the resource with the job to an attempted resources list, determining the remaining resources capable of executing the job using a resource table, removing from consideration the resource on the attempted resources list, and determining if any remaining resources remain after removing from consideration the resource on the attempted resources list;
responsive to the determination that remaining resources remain, randomly selecting a second resource from a plurality of remaining resources and sending the job to the second resource;
and
responsive to the determination that remaining resources do not remain, determining if a preset number of iterations have been reached;
responsive to the determination that the preset number of iterations has been reached, clearing the attempted resources list, waiting a specified amount of time, and re-determining the remaining resources capable of executing the job using the resource table.

7 more elements

A computer program product for scheduling a job on a grid wherein a scheduler does not have to keep track of a plurality of state dependent resource properties, the computer program product comprising:

one or more computer-readable, tangible storage devices;
program instructions, stored on at least one of the one or more storage devices, to receive notification that the job has been submitted to the grid from a submitting computer;
program instructions, stored on at least one of the one or more storage devices, to determine whether the submitting computer is a resource of the grid;
program instructions, stored on at least one of the one or more storage devices, responsive to the determination that the submitting computer is not the resource, to send the job to a resource closest to the submitting computer;
program instructions, stored on at least one of the one or more storage devices, to run a local scheduling program at a resource with the job;
program instructions, stored on at least one of the one or more storage devices, to determine whether the resource with the job accepted the job;
program instructions, stored on at least one of the one or more storage devices, responsive to the determination that the resource with the job did not accept the job, to add the resource with the job to an attempted resources list;
program instructions, stored on at least one of the one or more storage devices, to determine the remaining resources capable of executing the job using a resource table, to remove from consideration the resource on the attempted resources list;
program instructions, stored on at least one of the one or more storage devices, to determine if any remaining resources remain after removing from consideration the resource on the attempted resources list;
and responsive to the determination that remaining resources remain, randomly selecting a second resource from a plurality of remaining resources and sending the job to the second resource;
program instructions, stored on at least one of the one or more storage devices, responsive to the determination that remaining resources do not remain, to determine if a preset number of iterations has been reached;
program instructions, stored on at least one of the one or more storage devices, responsive to the determination that the preset number of iterations has been reached, to clear the attempted resources list, waiting a specified amount of time, and to re-determine the remaining resources capable of executing the job using the resource table;
and
program instructions, stored on at least one of the one or more storage devices, responsive to the determination that the preset number of iterations has been reached, to notify an originating computer that the job has failed.

11 more elements

A computer program product for scheduling a job on a grid wherein a resource determines whether to accept the job, the computer program product comprising:

one or more computer-readable, tangible storage devices;
program instructions, stored on at least one of the one or more storage devices, to receive notification that the job has been submitted to the grid from a submitting computer;
program instructions, stored on at least one of the one or more storage devices, to determine whether the submitting computer is a resource of the grid;
program instructions, stored on at least one of the one or more storage devices, responsive to the determination that the submitting computer is not the resource, to send the job to a resource closest to the submitting computer;
program instructions, stored on at least one of the one or more storage devices, to run a local scheduling program at a resource with the job;
program instructions, stored on at least one of the one or more storage devices, to determine whether the resource with the job can execute the job;
program instructions, stored on at least one of the one or more storage devices, responsive to the determination that the resource with the job can not execute the job, to add the resource with the job to an attempted resources list;
program instructions, stored on at least one of the one or more storage devices, to determine the remaining resources capable of executing the job using a resource table, to remove from consideration the resource on the attempted resources list;
program instructions, stored on at least one of the one or more storage devices, to determine if any remaining resources remain after removing from consideration the resource on the attempted resources list;
and responsive to the determination that remaining resources remain, randomly selecting a second resource from a plurality of remaining resources and sending the job to the second resource;
program instructions, stored on at least one of the one or more storage devices, responsive to the determination that remaining resources do not remain, to determine if a preset number of iterations has been reached;
program instructions, stored on at least one of the one or more storage devices, responsive to the determination that the preset number of iterations has been reached, to clear the attempted resources list, waiting a specified amount of time, and to re-determine the remaining resources capable of executing the job using the resource table;
and
program instructions, stored on at least one of the one or more storage devices, responsive to the determination that the preset number of iterations has been reached, to notify an originating computer that the job has failed.

11 more elements

Dependencies are inferred from the claim text.