JP2012073690A - Job scheduling program, method and device - Google Patents

Abstract

PROBLEM TO BE SOLVED: To realize job execution using resources efficiently in a job scheduling apparatus.
A job information acquisition unit obtains a used resource amount and an estimated execution time of a job. The resource reservation management unit 12 searches the resource reservation information indicating the resource usage status of the scheduled job for a free time in which the resource usage amount of the target job can be secured. If the searched free time does not have a free time T1 corresponding to the estimated execution time starting within a certain time, the job allocating unit 13 searches for a free time T2 corresponding to the shortened predicted execution time and reduces the free time. If T2 starts earlier than the idle time T1, a job is assigned to the idle time T2. The job execution management unit 14 monitors the start and end of job execution. If the job execution is not completed within the free time T2, the job execution management unit 14 performs rescheduling with the expected execution time.
[Selection] Figure 1

Description

  The present invention relates to a job scheduling program, method, and apparatus for scheduling job execution based on the usage amount of a computing resource (resource) and an estimated execution time.

  For example, a job scheduling device (hereinafter referred to as a job scheduler) is used to efficiently execute jobs having various sizes and attributes in a large-scale computer environment.

  Some job schedulers mainly used in HPC (High Performance Computing) employ a processing method called backfill scheduling in order to use resources efficiently.

  Backfill scheduling is a scheduling technique for improving resource utilization efficiency in FCFS (First Come First Served) scheduling.

  In FCFS scheduling, resources are allocated to jobs in the order in which execution requests are received. Therefore, if scheduling is performed in the order of jobs with a large amount of used resources (large-scale jobs) and jobs with a small amount of used resources, it is possible to execute jobs that have a small amount of used resources even if there are vacant computational resources. Even in such a situation, resources are secured for the execution of the preceding large-scale job, so that it is not possible to execute a job with a small amount of subsequent resource use.

  In backfill scheduling, if a job is estimated to be completed by the start time of a large-scale job, that is, a job that does not affect the start of a large-scale job, if the resources are available, the order is overtaken. Run it to achieve effective use of resources.

  Also, in a parallel processing system, when job execution is managed by a job queue, the priority in the job queue is set according to the system resource request amount, waiting time, etc. of each job, and non-priority execution jobs being executed are set. As a swap-out target, a process is known in which a swapped-out processor is allocated to start a priority job waiting for execution, and an unprocessed processor is allocated to as many execution waiting jobs as possible.

  Also, in the execution management of a job that makes a space acquisition request on the external storage device, the space acquisition request exceeds the current free space size but does not exceed the total of the free space and the temporary file used space. In addition, there is known a process for reducing the number of cases of abnormal termination due to lack of space by putting the job that has requested the acquisition into a waiting state and terminating the job that has requested the acquisition when the total is exceeded.

JP-A-8-16410 Japanese Patent Publication No. 8-16869

  In the FCFS scheduling method, waiting jobs are sequentially processed, and jobs are allocated to locations where the amount of resources used and the estimated execution time necessary for job execution can be secured.

  FIG. 7 is a diagram illustrating a scheduling example of job execution by the FCFS scheduling method. The vertical axis in FIG. 7 represents the resource amount, the horizontal axis represents the elapsed time, and the used resource amount necessary for job execution and the expected execution time are shown as rectangular areas.

  As shown in FIG. 7A, assume that job j2 is assigned after job j1 in job execution scheduling. Next, assume that job execution of job j3 is scheduled. In this case, as shown in FIG. 7B, it is assumed that there is a free space in which the amount of resources used and the estimated execution time of job j3 can be allocated during job execution of job j1.

  However, in the FCFS scheduling method, the job j3 next to the job j2 cannot be assigned to this empty portion at the present time (current time), and the job execution of the job j3 is scheduled after the job j2. . Therefore, the empty space during execution of job j1 is wasted at the current time.

  On the other hand, in the backfill scheduling method, when there is a vacancy for executing a job in a resource, scheduling is performed based on the amount of resource used for the job and the expected execution time regardless of the order of acceptance.

  FIG. 8 is a diagram illustrating a scheduling example of job execution by the backfill scheduling method.

  In the backfill scheduling method, as shown in FIG. 8A, job j3 received after job j2 can be assigned to the current time.

  However, even in the backfill scheduling method, if the idle time is longer than the expected execution time of the job, it cannot be assigned. As shown in FIG. 8B, when job j4 is received next to job j3, the available resource amount at the current time is greater than or equal to the resource usage amount of job j4, but the expected execution time ta of job j4 is It is assumed that it is longer than the time (free time) tb in which the resource amount is secured. In this case, the available resource amount at the current time cannot be allocated and used for job j4, and job j4 is scheduled after job j2. For this reason, there is a problem in that the resources used cannot be effectively used.

  In addition, considering the amount of resource used that indicates the amount of resources required for job execution and the estimated execution time that is expected as the time required for job execution, specified when the job execution is requested, it was specified by the user. The expected execution time does not necessarily indicate an accurate execution time.

  Generally, a user who requests job execution may set a longer execution time so that it is not terminated in the middle of job execution.

  As an aspect of the present invention, when a specified amount of used resources can be secured but there is a free time shorter than the expected execution time, the job execution is attempted more efficiently by using the free time. An object of the present invention is to provide an apparatus that executes a scheduling process that enables resource use.

  A job scheduling program disclosed as one aspect of the present invention provides a computer having a storage unit for storing scheduling information including a job resource amount and an allocation time based on the scheduling information read from the storage unit. The resource amount of the job to be scheduled can be scheduled at the same time, but the process for searching for a free time that is less than the expected execution time and, if the free time exists, the target job is determined as the free time. This is for causing the scheduling process to be executed.

  A job scheduling method disclosed as one aspect of the present invention is a processing method executed by a computer, and includes a processing process realized by the job scheduling program.

  Furthermore, a job scheduling apparatus disclosed as one aspect of the present invention includes a processing unit that executes processing when realized by the job scheduling program.

  According to the disclosed job scheduling apparatus, it is possible to use the idle time during which resources are not used while guaranteeing job execution, and to realize efficient processing of resources.

It is a figure which shows the structural example of the job scheduling apparatus disclosed as one Embodiment of invention. It is a figure which shows the example of resource reservation information. It is a figure which shows the example of job information. It is a figure which shows the example of log | history information. It is a figure which shows the example of a processing flow of a job execution scheduling process. It is a figure which shows the example of a processing flow of a job execution management process. It is a figure which shows the example of a scheduling of the job execution by a FCFS scheduling method. It is a figure which shows the example of a scheduling of the job execution by a backfill scheduling method.

  FIG. 1 is a diagram illustrating a configuration example of a job scheduling apparatus disclosed as an embodiment of the invention.

  The job scheduling apparatus 1 executes scheduling processing based on the used resource amount of a job for which job execution is requested.

  The job scheduling apparatus 1 is realized by a computer system including hardware having a CPU, a memory, and the like, and a software program, or dedicated hardware.

(1) Configuration Unit The job scheduling apparatus 1 includes a resource reservation information storage unit 10, a job information acquisition unit 11, a resource reservation management unit 12, a job allocation unit 13, a job execution management unit 14, and a history information storage unit 15.

  The resource reservation information storage unit 10 stores resource reservation information.

  The resource reservation information is information indicating the job usage status for the resource on which the job is executed.

  FIG. 2 is a diagram illustrating an example of resource reservation information.

  In the example of resource reservation information shown in FIG. 2, the resource reservation information is implemented in a list structure, and the used resource amount (resource amount) used in the job or unused is set for each predetermined time interval. An array is prepared and listed in chronological order.

  The used resource amount is a value indicating the amount of calculation resources necessary for job execution, and is indicated by, for example, the number of CPUs, the number of storage devices (used areas), the number of licenses, and the like.

  The resource reservation information may be implemented as a two-dimensional array in which used resource amounts are mapped at each time.

  The job information acquisition unit 11 acquires the used resource amount and the estimated execution time of the job to be scheduled.

  More specifically, the job information acquisition unit 11 acquires, for example, a user name, job name, used resource amount, and estimated execution time for each job to be scheduled, and assigns information (ID) for uniquely identifying the job. Create job information.

  FIG. 3 is a diagram illustrating an example of job information.

  The job information includes ID, job name, user name, used resource amount, expected execution time, and speculative job.

  In the example of job information shown in FIG. 3, the amount of resources used is the number of CPUs, and the expected execution time is the time unit (H). A job with ID = 100 requires 16 CPUs for execution and requires 8 hours (H ) Execution time is expected.

  The speculative job is a setting that indicates whether the job is a speculative job. “True” indicates a speculative job, “false” indicates that speculative job setting is prohibited, and “null” indicates an initial setting.

  The speculative job is a job in which “true” is set in the speculative job of the job information by the job allocation unit 13, that is, a job in which job execution is allocated in a free time less than the expected execution time specified by the user. means.

  If the user specifies that the speculative job setting should be prohibited, the job information acquisition unit 11 sets “false” to the speculative job of the job information.

  The resource reservation management unit 12 manages the use status of jobs for resources.

  More specifically, the resource reservation management unit 12 allocates the resource of the used resource amount for the estimated execution time (allocation time) from the start time of the allocation time of the target job by the job allocation unit 13 and sets the resource reservation information. Set.

  Further, the resource reservation management unit 12 traces the resource reservation information (list of resource reservation information shown in FIG. 2) based on the used resource amount of the job information and the estimated execution time, and the time that can be allocated to the job. The start time is searched, and the time zone (free time) in which the necessary resources can be secured is searched. Then, the resource reservation management unit 12 notifies the job allocation unit 13 of the searched start time.

  Also, the resource reservation management unit 12 releases the notified start time, execution time, and resource amount from the resource reservation information.

  The job allocation unit 13 schedules job execution by referring to the resource reservation information based on the job information of the target job.

  More specifically, when the speculative job in the job information is initially set, the job allocation unit 13 checks whether there is a free time T1 having a length longer than the expected execution time in the searched free time. Further, the job allocation unit 13 checks whether the idle time T1 starts within a predetermined time from the current time. If the idle time T1 starts within a predetermined time from the current time, the job allocation unit 13 selects the idle time T1 as the allocation time, and does not set a speculative job in the job information. In this case, the target job is scheduled as in the conventional case.

  On the other hand, if the free time T1 does not start within a predetermined time from the current time, the job allocation unit 13 calculates a shortened predicted execution time obtained by shortening the predicted execution time. The job allocation unit 13 checks whether or not the searched free time has a free time T2 that is longer than the estimated shortened execution time. Here, if there is no free time T2 in the searched free time, the job allocation unit 13 may further reduce the predicted shortened execution time, and sets a lower limit value for the predicted shortened execution time. The calculation of the shortened expected execution time may be repeated a plurality of times in the range exceeding the above.

  Then, if there is a free time T2, the job allocation unit 13 checks whether the free time T2 is started before the free time T1. If the free time T2 starts early, the job allocation unit 13 selects the free time T2 as the allocation time, and sets “true” in the speculative job of the job information. In this case, the target job is a speculative job, and job execution is attempted in a free time shorter than the specified expected execution time.

  Further, when the speculative job setting is prohibited for the target job (“false” is set in the speculative job of the job information), the job allocation unit 13 calculates the estimated execution time from the searched free time. The free time T3 that can secure the resources for the remaining time is searched and assigned time.

  If "false" is set for the speculative job in the job information of the target job, the user has specified that the speculative job is prohibited, or it has already been scheduled as a speculative job, but the job execution could not be completed This is to ensure the certainty of job execution.

  Details of the calculation process of the shortened expected execution time and the allocation time selection process will be described later.

  The job execution management unit 14 manages the start and end of scheduled job execution based on the resource reservation information.

  More specifically, the job execution management unit 14 monitors the start and end of execution of the job assigned to the resource based on the resource reservation information. If the job execution is not completed within the assigned time, The job execution is forcibly terminated and the resource reservation management unit 12 is notified.

  If the job that has been forcibly terminated is a speculative job (speculative job = “true”), the job execution management unit 14 changes the speculative job in the job information to “false”, and the job allocation unit 13 sets the job as a scheduling target. Notify the job.

  On the other hand, when the job execution is completed within the allocated time, the job execution management unit 14 generates an execution history related to job execution and stores it in the history information storage unit 15.

  FIG. 4 is a diagram illustrating an example of an execution history.

  The execution history is information including a user name, a job name, a used resource amount, a job execution time, and a job completion time. The user name, job name, and resource usage are based on job information. The job execution time is the time when the job is actually executed, and the job completion time is the time when job execution is completed.

  FIG. 5 is a diagram illustrating a processing flow example of job execution scheduling processing.

  In the processing flow shown in FIG. 5, it is assumed that job information acquisition unit 11 has generated job information of a job to be scheduled (see FIG. 3).

  In the job scheduling apparatus 1, the resource reservation management unit 12 refers to the resource reservation information storage unit 10 and searches for all free times in which the used resource amount can be secured based on the used resource amount and the expected execution time. . The job allocation unit 13 searches the start time t1 of the free time T1, which is longer than the expected execution time, from the searched free time (step S1).

  The job allocation unit 13 receives the start time t1 from the resource reservation management unit 12, and checks whether the start time t1 is close to the current time (step S2). When the start time t1 is after a predetermined time from the current time (N in Step S2), the job allocation unit 13 checks whether the speculative job setting is prohibited for the job (Step S3).

  If the speculative job of the job information is not “false” (N in step S3), the job allocation unit 13 executes a calculation process of the shortened expected execution time (step S4).

  The resource reservation management unit 12 searches for the start time t2 of the free time that is equal to or longer than the estimated shortened execution time from the searched free time (step S5).

  The job allocation unit 13 receives the start time t2 from the resource reservation management unit 12, and checks whether there is a start time t2 earlier than the start time t1 (step S6).

  If there is a start time t2 earlier than the start time t1 (Y in step S6), the job allocation unit 13 sets “true” in the speculative job of the job information (step S7). The job allocation unit 13 sets the start time t2 as the job execution start time of the target job and the shortened expected execution time as the allocation time (step S8), and proceeds to the process of step S11.

  If there is no start time t2 earlier than the start time t1 (N in step S6), the job allocation unit 13 checks whether the shortened expected execution time does not fall below a predetermined lower limit and the time can be subtracted (step S9). If the estimated shortened execution time can be further subtracted (Y in step S9), the job allocation unit 13 returns to the process of step S3 and further obtains a predicted shortened execution time.

  If the shortened expected execution time cannot be subtracted (N in step S9), the job allocation unit 13 sets the start time t1 as the job execution start time of the target job, and sets the expected execution time as the allocation time. (Step S10), the process proceeds to Step S11.

  If the start time t1 is within a predetermined time from the current time (Y in step S2), or if “false” is set in the speculative job of the job information (Y in step S3), the job The allocation unit 13 proceeds to the process of step S10.

  After that, in step S11, the resource reservation management unit 12 receives the start time and the allocation time of the target job from the job allocation unit 13, and changes the allocation time from the corresponding start time of the resource reservation information to the used resource amount. Assign the target job to the corresponding resource.

  As the calculation process of the shortened estimated execution time in step S4, the job allocation unit 13 can perform various processes.

  For example, the job allocation unit 13 enables the user to specify in advance a “predetermined amount of time” to be subtracted from the expected execution time of the target job, or a time portion / ratio to be subtracted according to the expected execution time, It may be possible to set a lower limit value of the shortened predicted execution time. In this case, the job allocation unit 13 acquires specific numerical values designated by the user, such as the shortenable time (number of hours), the shortenable rate (percent), and the lower limit value.

  In addition, when the estimated execution time is short (for example, several hours), the job allocation unit 13 reduces the subtracted time / ratio, and when the estimated execution time is long (for example, several days). May be set by increasing the subtraction time / rate.

  Further, the job allocation unit 13 may use a large value as the subtraction time / ratio in the first calculation process, and subtract using a gradually reduced value in the second and subsequent calculation processes.

  Further, when the history information storage unit 15 is provided, the job allocation unit 13 can calculate the shortened estimated execution time based on the execution history. Specifically, the job allocation unit 13 extracts, from the history information storage unit 15, the execution history of a job that matches the user name, job name, amount of used resources, etc. as a job that matches the target job. . Furthermore, the job allocating unit 13 may extract an arbitrary number (for example, 10) of histories from the newest job completion time among execution histories of matching jobs. The extracted histories are arranged in ascending order of execution time, the median is obtained, and this is used as the shortened expected execution time. Alternatively, the job allocating unit 13 calculates a shortened predicted execution time by setting a time within a certain range (for example, 10%) of the job execution time recorded in the execution history as a time to be subtracted.

  Alternatively, the job allocating unit 13 determines the shortest job execution time out of the job execution times recorded in the execution history, the shortest job execution time out of the job execution times, or the second shortest job execution time. , Adopted as the lower limit value to calculate the shortened expected execution time.

  Alternatively, the job allocation unit 13 subtracts a predetermined amount of time, calculates a plurality of predicted shortened execution times within the range up to the lower limit value, and shortens the predicted predicted execution time for each predicted shortened execution time from the searched free time. The combination of the free time (time that becomes the allocation time) and the start time is calculated as a candidate allocation time. Then, the job allocation unit 13 allocates the obtained allocation time candidates in the order of time, with the longest time, the earliest start time, or the median time and start time. You may choose as time.

  Alternatively, the job allocation unit 13 calculates the time difference between the start time of the searched free time and the current time, and if this time difference is smaller than a certain value, the job allocation unit 13 uses a shortened expected execution time that is not very close to the lower limit value. When an idle time is selected and this time difference is larger than a certain value, the idle time may be selected with a shortened predicted execution time close to the lower limit value.

  In addition, the job allocation unit 13 can perform various processes as the job execution allocation time selection process.

  If the speculative job of the target job is other than “false”, the job allocation unit 13 may always select a free time shorter than the expected execution time. As a result, in principle, speculative job execution can be tried and scheduling that improves resource utilization efficiency can be realized.

  In addition, as described above, the job allocation unit 13 may select a free time that is equal to or greater than the expected execution time when a free time that is equal to or greater than the expected execution time is started within a predetermined time from the current time. . As a result, when the target job can be executed immediately or can be executed without much waiting at the present time point, it is possible to select a free time that is longer than the expected execution time to guarantee reliable job execution.

  Furthermore, the job allocation unit 13 may allow the user to specify a predetermined time from the current time in advance.

  Further, the job allocation unit 13 may allow the user to specify the job execution start time in advance. In this case, the job allocation unit 13 selects a free time starting from the start time closest to the designated start time as the free times T1, T2, and T3.

  FIG. 6 is a diagram illustrating a processing flow example of the job execution management process.

  In the job scheduling apparatus 1, the job execution management unit 14 starts job execution when the start time arrives based on the resource reservation information (step S20), and monitors completion of job execution (step S21).

  Then, the job execution management unit 14 checks whether or not the job execution has been completed during the allocation time to the job (step S22). While the completion of the job execution is not detected (N in step S22), the allocation time ends. Is monitored (step S23).

  The job execution management unit 14 checks whether the job is completed at the end of the allocated time (step S24). The job execution management unit 14 forcibly terminates the job (step S25) if the job is not completed at the end of the allocation time (N in step S24), and the resource reservation management unit 12 determines the resource allocated to the job. Release (step S26).

  Further, the job execution management unit 14 checks whether or not the job is a speculative job (speculative job = “true” in job information) (step S27). If the job is a speculative job (Y in step S27), the job execution management unit 14 sets “false” in the speculative job of the job information and requests the job allocation unit 13 for scheduling (step S28). If the job is not a speculative job (N in step S27), the process is terminated.

  When the job execution has been completed by the end of the time allotted to the job (Y in step S22, Y in S24), the job execution management unit 14 generates a job execution history, and the history information storage unit 15 (Step S29). The resource reservation manager 12 releases the resources allocated to the job (step S210).

  The job scheduling apparatus 1 for executing the above-described processing has an arithmetic unit (CPU), a temporary storage device (DRAM, flash memory, etc.), and a permanent storage device (HDD, flash memory, etc.). It can be implemented by a computer that outputs.

  The job scheduling apparatus 1 can also be implemented by a program that can be executed by this computer. In this case, a program describing the processing contents of the functions that the job scheduling apparatus 1 should have is provided. When the provided program is executed by the computer, the job information acquisition unit 11, the resource reservation management unit 12, the job allocation unit 13, and the job execution management unit 14, which realize the processing function of the job scheduling apparatus 1, are executed on the computer. Realized.

  The computer can also read a program directly from a portable recording medium and execute processing according to the program. Furthermore, the program can be recorded on a computer-readable recording medium.

  As described above, according to the job scheduling apparatus 1, when the execution of the target job can be started without waiting too much, it is allocated to the resource for the specified expected execution time, and the job execution is guaranteed. Is done. On the other hand, if it takes a long time to start executing the target job, it will be allocated to the resource by the amount of time specified by shortening the specified expected execution time (shortened expected execution time), and speculative job execution will be attempted. .

  Users tend to specify a longer expected execution time, and job execution may be completed in a shorter time than the specified time. This is not possible with scheduling processing using the conventional backfill scheduling method. It is possible to schedule job execution by using a free time that is started before the expected execution time specified by, and is less than the expected execution time.

  As described above, according to the disclosed job scheduling apparatus, the amount of resources necessary for job execution can be secured, but even in a situation where only a shorter time than the expected execution time is available, the job can be used in that idle time. Can be assigned and attempted to execute.

  Further, according to the disclosed job scheduling apparatus, if the job execution is not completed at the allocated time, it can be scheduled again.

  Therefore, the disclosed job scheduling apparatus can provide job scheduling that can use resources more efficiently.

  In addition, for the user, if a job assigned to a free time shorter than the expected execution time is completed within that time, the job execution result can be obtained earlier than the conventional scheduling.

DESCRIPTION OF SYMBOLS 1 Job scheduling apparatus 10 Resource reservation information storage part 11 Job information acquisition part 12 Resource reservation management part 13 Job allocation part 14 Job execution management part 15 History information storage part

Claims (8)

A computer having a storage unit for storing scheduling information including a job resource amount and an allocation time,
Based on the scheduling information read from the storage unit, it is possible to schedule the resource amount of a job to be newly scheduled, but to search for a free time that is less than the expected execution time;
A job scheduling program for executing a process of scheduling the target job at the free time when the free time exists. In the computer,
The job scheduling program according to claim 1, wherein when the target job is executed and is not completed within the allocated time, processing for rescheduling the target job is executed. In the computer,
A process of calculating a shortened expected execution time by reducing the expected execution time of the target job by a predetermined time when searching for an allocation time of the target job based on the scheduling information;
A process for selecting, from the searched free time, a free time that starts before a free time that is equal to or greater than the estimated execution time and that is equal to or greater than the shortened execution time as an allocation time for the target job. The job scheduling program according to claim 1 or 2. The computer includes a history information storage unit,
An execution history including start time and end time of execution of a job assigned to the resource is acquired in the computer, and an execution history including start time and end time of execution of the job is stored in the history information storage unit Processing to
4. The process for calculating the predicted shortened execution time based on the execution history related to the target job when calculating the predicted shortened execution time of the target job. The job scheduling program described. When searching for the allocation time of the target job, if the start time of the target job is specified, the allocation time of the job is calculated from the free time starting within a predetermined time from the start time. The job scheduling program according to any one of claims 3 and 4, for executing a process of selecting the. When calculating the shortened estimated execution time of the target job, an execution history of an arbitrary number of jobs corresponding to the target job is extracted from the history information storage unit, and the execution of the extracted arbitrary number of jobs is performed The job scheduling program according to any one of claims 3 to 5, wherein a process for setting a median time as the shortened expected execution time is executed. A processing method for scheduling job execution, executed by a computer having a storage unit for storing scheduling information including job resource amount and allocation time,
Based on the scheduling information read from the storage unit, it is possible to schedule the resource amount of a job to be newly scheduled, but to search for a free time that is less than the expected execution time;
And a processing step of scheduling the target job to the free time when the free time exists. A device for scheduling job execution,
A storage unit for storing scheduling information including job resource amount and allocated time;
Based on the scheduling information read from the storage unit, it is possible to schedule a resource amount of a job to be newly scheduled, but a processing unit that searches for a free time that is less than the expected execution time;
A job scheduling apparatus comprising: a processing unit that schedules the target job at the free time when the free time exists.

Images