Managing high performance computing resources using job preemption

Patent metadata

Field	Value
Publication number	US-9424078-B2
Application number	US-201113296141-A
Country	US
Kind code	B2
Filing date	Nov 14, 2011
Priority date	Nov 14, 2011
Publication date	Aug 23, 2016
Grant date	Aug 23, 2016

Abstract

The preemption of running jobs by other running or queued jobs in a system that has processing resources. The system has running jobs, and queued jobs that are awaiting processing by the system. In a scheduling operation, preemptor jobs are identified, the preemptor jobs being jobs that are candidates for preempting one or more of the running jobs. The preemptor jobs include queued jobs, as well as running jobs that are capable of using more processing resource of the system. One of the other running jobs is preempted to free processing resources for the running job that was identified as a preemptor job. Accordingly, not only may queued jobs preempt running jobs, but currently running jobs may preempt other currently running jobs.

First claim

What is claimed is:

1. A computer system, comprising:
one or more processors; and
at least one computer-readable storage device having stored thereon computer-executable instructions that are executable by the one or more processors to cause the computer system to perform a scheduling iteration of one or more jobs of the computer system, the computer-executable instructions including instructions that are executable to cause the computer system to perform at least the following:
identify a plurality of running jobs that are running in the computer system and one or more queued jobs that are awaiting to be processed by the system, wherein each running job, and each queued job, specifies at least one of a minimum amount of processing resources that are to be allocated to processing the job and a maximum amount of processing resources that are to be allocated to processing the job;
identify a plurality of preemptor jobs that are eligible to preempt one or more of the plurality of running jobs, the plurality of preemptor jobs comprising all of the one or more queued jobs and each running job of the plurality of running jobs that is currently running below the maximum amount of processing resources that are to be allocated to processing the job,
wherein a threshold for determining whether one of the plurality of preemptor jobs preempts one or more of the plurality of running jobs is different for running jobs and queued jobs, wherein a threshold for running preemptor jobs to preempt other running jobs is met for a specific running preemptor job until the specified maximum amount of processing resources are available for assignment to the specific running preemptor job, and wherein a threshold for queued preemptor jobs to preempt other running jobs is met for a specific queued job until the specified minimum amount of processing resources will be available for assignment to the specific queued preemptor job after preempting a running job;

preempt at least one of the plurality of running jobs with a first job that is included in the plurality of preemptor jobs sorted based on, at least one of job priority and time elapsed since job request, and based on the job's threshold being met,
wherein at least the specified minimum amount of processing resources will be available for assignment to the first job after preempting the at least one of the plurality of running jobs; and

process the first job using at least the specified minimum amount of processing resources including an amount of system processing resources that became available as a result of the at least one of the plurality of running jobs being preempted.

2. The computer system in accordance with claim 1 , wherein the first job preempts running jobs from the plurality of running jobs until the first job is using the maximum amount of processing resources that are to be allocated to processing the first job.

3. The computer system in accordance with claim 1 , wherein one of the one or more queued jobs preempts at least one of the plurality of running jobs, wherein the queued job is processed as a result of preempting the at least one of the plurality of running jobs.

4. The computer system in accordance with claim 1 , wherein the system is a high performance computer system.

5. The computer system in accordance with claim 4 , wherein the processing resources are compute nodes.

6. The computer system in accordance with claim 1 , wherein in order to prevent subsequent preemption of a previously preempted job, the first job is verified to have not already been preempted prior to preempting the at least one of the plurality of running jobs with a different running job that was included in the identified preemptor jobs.

7. The computer system in accordance with claim 1 , wherein the plurality of preemptor jobs includes a second job that was included in the identified preemptor jobs, the second job being lower in processing priority than the first job.

8. The computer system in accordance with claim 7 , wherein the first job preempts the second job in order to provide additional processing resources to the first job.

9. The computer system in accordance with claim 1 , wherein processing comprises: processing the first job using the specified maximum amount of system processing resources for the first job.

10. A method, implemented at a computer system that includes one or more processors, for performing a scheduling iteration of one or more jobs of the computer system, the method comprising:
identifying a plurality of running jobs that are running in the computer system and one or more queued jobs that are awaiting to be processed by the system, wherein each running job, and each queued job, specifies at least one of a minimum amount of processing resources that are to be allocated to processing the job and a maximum amount of processing resources that are to be allocated to processing the job;
identifying a plurality of preemptor jobs that are eligible to preempt one or more of the plurality of running jobs, the plurality of preemptor jobs comprising all of the one or more queued jobs and each running job of the plurality of running jobs that is currently running below the maximum amount of processing resources that are to be allocated to processing the job,
wherein a threshold for determining whether one of the plurality of preemptor jobs preempts one or more of the plurality of running jobs is different for running jobs and queued jobs, wherein a threshold for running preemptor jobs to preempt other running jobs is met for a specific running preemptor job until the specified maximum amount of processing resources are available for assignment to the specific running preemptor job, and wherein a threshold for queued preemptor jobs to preempt other running jobs is met for a specific queued job until the specified minimum amount of processing resources will be available for assignment to the specific queued preemptor job after preempting a running job;

preempting at least one of the plurality of running jobs with a first job that is included in the plurality of preemptor jobs sorted based on, at least one of job priority and time elapsed since job request, and based on the job's threshold being met,
wherein at least the specified minimum amount of processing resources will be available for assignment to the first job after preempting the at least one of the plurality of running jobs; and
processing the first job using at least the specified minimum amount of processing resources including an amount of system processing resources that became available as a result of the at least one of the plurality of running job being preempted.

11. The method in accordance with claim 10 , wherein the first job preempts running jobs from the plurality of running jobs until the first job is using the maximum amount of processing resources that are to be allocated to processing the first job.

12. The method in accordance with claim 10 , further comprising:
preempting at least one of the plurality of running jobs with a queued job, wherein the queued job is processed as a result of the act of preempting.

13. The method in accordance with claim 10 , wherein the system is a high performance computer system.

14. The method in accordance with claim 10 , further comprising:
verifying, in order to prevent subsequent preemption of a previously preempted job, that the first job has not already been preempted prior to preempting, the at least one of the plurality of running jobs with a different running job that was included in the identified preemptor jobs.

15. The method in accordance with cl

Assignees

• Chakravorty Sayantan
• Watson Colin
• Crall Christopher J
• Microsoft Technology Licensing Llc

Inventors

• Chakravorty Sayantan
• Watson Colin
• Crall Christopher J

Classifications

• G06F9/4843 Primary

  by program, e.g. task dispatcher, supervisor, operating system · CPC title

• G06F9/4881

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title

• G06F9/52

  Program synchronisation; Mutual exclusion, e.g. by means of semaphores · CPC title

• G06F9/50

  Allocation of resources, e.g. of the central processing unit [CPU] · CPC title