A scheduling method and system for controlling execution of processes

The present invention relates to scheduling methods and systems that control the execution of processing.

Scheduling methods are commonly used, for example, in some applications that manage a series of jobs in batch processing. Scheduling typically involves building a plan, which consists of a stream of jobs in a specified order that is used to request and control the execution of jobs. To build a plan, it is necessary to predict the expected duration of each job. For example, the estimated duration is set to the average measured duration of completed instances of previously run jobs.

If the job runs much longer than the estimated duration, the workload scheduler that controls the job execution detects the corresponding anomalous condition. In this situation, it is desirable to warn the operator. The operator decides, for example, whether a long-running job needs to be canceled and intervened. Alternatively, the scheduler calls the workload manager to give the job additional system resources (if classified as a limit).

A common technique is to specify a factor that multiplies the estimated duration. The resulting number gives a threshold for the current duration of the job. If the current duration exceeds the threshold, the job is considered to have a long run time and the corresponding action is taken.

The drawback of known solutions in the art is that the detection mechanism is inadequate and of little value. As a result, the workload scheduler may behave incorrectly.

Specifically, if the threshold is too low, false warnings will occur or system resources will be used indiscriminately, even if no real anomalies have occurred. Conversely, if the threshold is too high, long-running jobs will only be detected after a very long period of time.

<p> An object of the present invention is to provide a technique for alleviating the above-mentioned drawbacks.</p>

<p> According to the present invention, a scheduling method for controlling the execution of processing is provided.<u style="single">To. In one embodiment of the present invention</u>, This method is a step to estimate the expected duration of processing,<u style="single">With the step of calculating the multiplier as a decreasing function of the expected duration</u>Includes a step of multiplying the expected duration by a multiplier to determine the threshold, a step of executing the process, and a step of detecting an abnormal state when the actual duration of the process exceeds the threshold.<u style="single">The multiplier is calculated as a linear function of the expected duration, at least in a range of values.</u>。<u style="single">In another embodiment of the invention, the method uses a step of estimating the expected duration of processing, a step of calculating a multiplier as a decreasing function of the expected duration, and a threshold using the product of the expected duration and the multiplier. The steps to be calculated include a step of determining, a step of executing the process, and a step of detecting an abnormal state when the actual duration of the process exceeds the threshold, and the steps to be calculated are the first parameter and the second parameter. And the hyperbolic of the expected duration by dividing the third parameter by the sum of the first step of setting the third parameter, the product of the expected duration and the first parameter, and the second parameter. Includes a second step to calculate the multiplier as a function</u>。 </p><p> The present invention also provides a computer program that implements such a method, a program product that stores such a program, and a corresponding system.</p><p> Further features and advantages of the solutions according to the invention will be apparent by preferred embodiments of the invention described below with reference to the accompanying drawings, which are not limiting the invention.</p>

A specific reference to FIG. 1 shows a data processing system 100, such as a mainframe. System 100 contains several units, which are connected in parallel to the system bus (SYS_BUS) 105. Specifically, a plurality of microprocessors (μP) 110 control the operation of the system 100. The microprocessor 110 accesses a shared working memory 115, which is generally formed of DRAM with alternating modules. The read-only memory (ROM) 120 stores the basic program that starts the system 100.

Various peripheral units are clustered around the local bus (LOC_BUS) 125. More specifically, the mass storage consists of a hard disk 130, and the system 100 consists of an input unit (IN) 135, which consists of, for example, a keyboard and a driver for a CD-ROM 140, and, for example, a monitor and a printer. It also includes an output unit (OUT) 145. The bridge unit (BRIDGE) 150 interfaces system bus 105 with local bus 125.

Each microprocessor 110 and bridge unit 150 can act as a primary agent requesting access to system bus 105 to carry information. Authorization of access to system bus 105 with mutual exclusion is managed by Arbiter (ARB) 155.

The same is true if the system has a different structure (eg, has a single bus), consists of a network of minicomputers or workstations, contains different units (eg drivers for magnetic tape), and so on.

Considering FIG. 2 here, the partial contents of the working memory 115 of the operating system are shown. Information (programs and data) is typically stored on the hard disk and is (at least partially) in working memory when the program is running with the operating system and other application programs (not shown). Loaded. The program is first installed on the hard disk from the CD-ROM.

The working memory 115 includes an input / output interface (I / O) 205 used for exchanging information with the operator. The I / O interface 205 communicates with the batch controller (BATCH) 210. The batch controller 210 manages the execution of a series of non-interactive jobs (usually at night or whenever the system is idle). Batch processing is particularly useful for operations that require a system or peripherals for extended periods of time.

The batch controller 210 accesses database 215, which stores a description of the company's production workload. The workload database 215 contains records (accessed via their respective identifier codes) for each job in the batch that should be run on the system. The record consists of fields that describe the behavior of the job (JOB), scheduled execution times (hours, dates, weeks, months), and any dependencies on other jobs. In fact, even though the system can run multiple jobs in parallel through time-sharing techniques, some jobs often show order constraints. For example, if a resource (such as a file) that should be used by one job is being accessed by another job, that job's execution should not start until the other job's execution is complete. The record further includes a field (ED) that indicates the estimated duration of the job.

A description of the job to be executed and its estimated duration are provided to the batch controller 210 and then transmitted to the plan builder (BUILDER) 220. Builder 220 creates a scheduling plan that controls the flow of job execution in a predetermined order over a specified period of time. The plan is built with a preset scheduling strategy (eg, adjusting the system load or optimizing peak performance). The plan is fed to the plan executor (EXEC) 225 via the batch controller 210. The plan execution device 225 submits the batch in the production environment (RUN) 230 and controls the execution of the job accordingly.

The batch controller 210 further manages the parameter input to the configuration repository (CONFIG) 235. The configuration parameters stored in repository 235 are supplied to logical unit (LOGIC) 240. Logical unit 240 also receives an estimated duration ED for each current job from batch controller 210. Logical unit 240 calculates the multiplier (MF) for the current job, as described below. The multiplier MF and estimated duration ED are input to the multiplication block 250. The multiplication block 250 calculates the threshold (TH) corresponding to the current job, and this value is supplied to the comparison block (COMP) 255. Comparison block 255 also receives the current duration (CD) of the job. The current duration CD is measured by the plan executor 225 by subtracting the actual start time of the job from the current time (provided by the system clock). The comparison block 255 detects any abnormal condition resulting from a job that has been executed longer than expected, and notifies the plan execution device 225 accordingly. Abnormal conditions are further reported to the operator via batch controller 210 and I / O interface 205.

When the job finishes its execution (because all operations have been completed, canceled by the operator in response to an abnormal condition, or an error has occurred), feedback information is sent from plan executor 225 to batch controller 210, and then. Returned to I / O interface 205. Feedback information includes the actual start time of the job, the actual end time of the job, the return code that specifies the result of the operation, and so on. The plan executor 225 also measures the actual duration (AD) of the job by subtracting the actual start time from the actual end time.

The actual duration AD is supplied to the estimation module (EST) 235, which uses the actual duration AD to predict how long the job should run in the future. An algorithm is applied that weights the actual duration AD of each run and takes a continuously changing average of the duration of the job. Specifically, a factor having a value that decreases with the number of job executions is multiplied by the actual duration AD, and the result is used to review the current estimated duration. The reviewed estimated duration ED is provided to batch controller 210 and then stored in the corresponding record in workload database 215.

If the entire scheduling program (consisting of the various modules described above) and data are configured differently, for example if the workload database and configuration repository consist of a single inventory or are replaced by an equivalent memory structure. If so, different features may be provided, and the estimated duration may be expected in different ways (for example, by accumulating the actual duration of each completed instance of the job and calculating its actual execution average). , Considered as well.

Referring now to FIG. 3, the scheduling program (running on the system) implements method 300 starting at block 303. The method then moves to block 306, where a menu with a set of possible choices is displayed on the monitor of the system. This method performs the action corresponding to the selected choice. Specifically, when the operator selects the function to edit the configuration parameters, blocks 309 to 333 are executed, whereas when the operator selects the function to request a job, blocks 336 to 366 are executed. To. Otherwise, if the operator selects the end option, the method ends in final block 367.

Considering block 309 (editing function) here, the method examines how the multiplier MF is defined. If the multiplier MF is calculated as a linear function of the estimated duration ED, the method moves to block 312. The operator enters the higher level UL of the multiplier associated with the short-duration job. Proceeding to block 315, the operator enters a lower level LL (but LL &lt;UL) of the multiplier associated with the long-duration job. The method proceeds to block 318, where the operator enters a break limit BL for the multiplier. The break limit BL defines how fast the multiplier fluctuates between the upper level UL and the lower level LL, and is also used as a cap to stabilize the multiplier. The method then returns to block 306 and waits for a new command.

Referencing block 309 again, if the multiplier MF is calculated as a hyperbolic function of estimated duration ED, the method moves to test block 321. If the operator wants to define a reference factor A (for updating the hyperbolic recess), the method moves to block 324, where the operator enters the reference factor A. If no definition is desired, the reference factor is set to the constant value 1 in block 327. In either case, the operator inputs parameter B in block 330 and further in parameter C in block 333. The ratio between parameters B and C defines the higher level of multiplier for short-duration jobs. The method then returns to block 306.

If we refer to block 336 (submission function) here, the estimated duration ED of the current job is provided to the logical unit. The logical unit checks how the multiplier MF is defined in block 339. If the multiplier MF is calculated as a linear function of the estimated duration ED, the method moves to test block 342. If the estimated duration ED is greater than the break limit BL, then in block 348 the multiplier MF is set to the lower level LL (MF = LL). In the opposite case, the multiplier MF is calculated by the following equation as a linear interpolation between the upper level UL for the expected duration ED = 0 and the lower level LL for the expected duration ED = BL.

<maths num="1"><img file="JP3828112B2_D0001.tif" /></maths>

In either case, the method then proceeds to block 351 (described below).

For example, an operator can set a value of 3 for a higher level UL (that is, a job with a very short duration would be delayed when it was run 3 times longer than the estimated duration) for a lower level LL. Suppose you decide to choose 0.1 (that is, a job with a very long duration will be delayed if it runs beyond the estimated duration by 10%). In addition, the multiplier MF should be stable at 0.1 for any estimated duration greater than 24 hours (BL = 1440 minutes). In this case, a 1-minute job is considered delayed if it runs 2.979786 minutes (ie, the algorithm gives a lot of weight to the higher level UL). A 24-hour job is considered delayed if it runs for 1584 minutes (1440 + 10%). Some intermediate examples explain how the multiplier MF changes with the estimated duration ED.

<tables num="1"><img file="JP3828112B2_D0002.tif" /></tables>

The corresponding curve, which illustrates how the multiplier MF changes with the estimated duration ED, is shown in solid line in Figure 4.

In another example, the operator sets the break limit BL = 240 minutes (4 hours). In this case, the multiplier MF gradually decreases and then stabilizes at a constant of 0.1 over 4 hours.

<tables num="2"><img file="JP3828112B2_D0003.tif" /></tables>

The corresponding curve is shown by the dashed line in FIG.

Referencing block 339 again, if the multiplier MF is calculated as a hyperbolic function of estimated duration ED, the method moves to block 354, where the multiplier MF is defined by the following formula.

<maths num="2"><img file="JP3828112B2_D0004.tif" /></maths>

The method then proceeds to block 351.

For example, using A = 1, B = 500 and C = 100, the following values are obtained over a 12 hour period:

<tables num="3"><img file="JP3828112B2_D0005.tif" /></tables>

A corresponding curve illustrating how the multiplier MF changes with the estimated duration ED is shown in FIG.

Considering block 351 here, the threshold TH is calculated by multiplying the estimated duration ED by the factor MF, i.e. TH = MF · ED. The job is requested in block 357, and the method then verifies that the job has finished executing in block 360. When finished, the method goes back to block 306 and waits for a new command. If not finished, enter test block 363. If the current duration CD of the job exceeds the threshold TH, an abnormal condition is detected in block 366 and the operator is notified accordingly. The method then returns to block 306. If the threshold is not exceeded, the method returns to block 360 and repeats the above operation.

Similarly, if the program executes an equivalent method with an error routine, an exception handling function that overwrites a multiplier at the operation level, a monitoring function that tracks a job, and the like, the same consideration is given. Alternatively, these methods are used to control system resources in distributed computer networks and to do any other processing in different applications.

More generally, the present invention provides a scheduling method that controls the execution of processing. This method estimates the expected duration of processing and then multiplies the expected duration to determine the threshold. An abnormal condition is detected when the process is executed and the actual duration of the process exceeds the threshold. In the method of the invention, the multiplier is determined as a decreasing function of expected duration.

With this devised solution, any long-running job can be detected very accurately. This improves the operation of the workload scheduler. As a result, any warning issued by the workload scheduler always indicates a true anomaly due to a job running much longer than expected. System resources can also be used properly by the workload manager for marginal jobs that are actually running longer than the estimated duration.

In fact, the inventor of the present invention has found that preset multipliers are not allowed in the normal scenario where each batch consists of jobs with significantly different durations.

For example, a small multiplier is desirable to detect abnormal conditions in jobs that have a long duration after a certain amount of time. However, in this case, the (assumed) anomalous condition of a short-duration job is that the job overruns for just a few seconds (very often caused by minor perturbations that affect shorter jobs relatively often). May be detected later.

Larger multipliers, on the other hand, provide a threshold that is acceptable for short-duration jobs. Unfortunately, in this case, anomalous conditions for long-duration jobs are only detected after hours.

In contrast, the solution of the invention uses a method of detecting long-running jobs, which takes into account the inherent non-endurance of short-duration jobs, while long-duration jobs. Allows detection of any abnormal condition of the throat before a long period of time elapses.

The preferred embodiments of the invention described above provide additional benefits. For example, a multiplier is calculated in a very simple way (at least in a range of values) as a linear function of expected duration.

Preferably, this function is defined by lower level LL, higher level UL and break limit BL. This algorithm is useful because the parameters are very important to the operator who encodes the desired highest and lowest values for the multiplier MF. In this way, the algorithm calculates an appropriate multiplier MF for any job and further weights the higher level UL when the estimated duration ED is small, but the multiplier gradually fluctuates the level and the estimated duration. The longer the ED, the more important it is to the lower level LL.

In addition, the multiplier MF stabilizes at the constants defined by the lower level LL above the break limit BL. By doing so, the multiplier MF can be gradually reduced from the upper level UL to the lower level LL and maintained at a level acceptable for jobs with very long duration.

Alternatively, the multiplier MF is calculated as a hyperbolic function of estimated duration ED. In this way, the curve of the multiplier MF can be manipulated in the desired shape (even if the coefficients are less important to the operator and it is more difficult to understand which is the optimal value).

Preferably, the curvature of the hyperbola can also be further defined by the operator, thereby making the solution even more flexible.

The same applies when thresholds are defined differently, when different parameters are considered, and so on. Alternatively, the linear function does not use break limits and the multiplier is calculated by another function, such as a logarithmic function, an exponential function, or more generally any decreasing function of estimated duration. Further, the solution according to the invention will implement the solution itself to determine a multiplier in a preset table or in any other method that provides the logic described above.

Advantageously, the solution according to the invention is implemented in a computer program (software) provided on a CD-ROM.

Alternatively, these programs are provided on floppy (R) disks or tapes, pre-loaded on hard disks, or stored on any other computer-readable medium and sent to the system over a network (usually the Internet). It is broadcast, broadcast, and more generally provided in any other form that can be mounted directly into the working memory of a computer. Further, the method according to the present invention allows the method itself to be carried out, for example, in a hardware structure integrated on a chip of a semiconductor material.

<figref num="1">It is a basic block diagram which shows the data processing system which can use the scheduling method of this invention.</figref><figref num="2">It is a figure which shows the partial contents of the working memory of this system.</figref><figref num="3">It is a flow chart which shows the scheduling method implemented in this system.</figref><figref num="4">It is a figure which shows the curve which the multiplier / estimated duration of a function is different.</figref><figref num="5">It is a figure which shows the curve which the multiplier / estimated duration of a function is different.</figref>