Adaptive job scheduling using neural network priority functions

• US 5,442,730 A
• Filed: 10/08/1993
• Issued: 08/15/1995
• Est. Priority Date: 10/08/1993
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bigus, Joseph P.
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): Dorvil, Richemond
• Application Number:
  US08/134,764
• Time in Patent Office: 676 Days
• Field of Search: 395/20-24, 395/650, 395/700, 364/401, 364/402
• US Class Current: 706/19
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A job scheduler makes decisions concerning the order and frequency of access to a resource according to a substantially optimum delay cost function. The delay cost function is a single value function of one or more inputs, where at least one of the inputs is a delay time which increases as a job waits for service. The job scheduler is preferably used by a multi-user computer operating system to schedule jobs of different classes. The delay cost functions are preferably implemented by neural networks. The user specifies desired performance objectives for each job class. The computer system runs for a specified period of time, collecting data on system performance. The differences between the actual and desired performance objectives are computed, and used to adaptively train the neural network. The process repeats until the delay cost functions stabilize near optimum value. However, if the system configuration, workload, or desired performance objectives change, the neural network will again start to adapt.

Claims

1. A method for scheduling jobs from among a plurality of job classes for service by a resource of a work-producing system, comprising the steps of:

defining a set of performance goals for said job classes;

training a neural network for producing a delay cost value function, said delay cost value function implementing said set of performance goals as output from at least one input, wherein at least one input to said neural network represents a delay time with respect to a job waiting for service by said resource;

assigning a respective job delay cost to each of a plurality of jobs waiting for service by said resource using said delay cost value function produced by said neural network; and

selecting a next job for service by said resource based on said job delay cost.

2. The method of claim 1, wherein said resource is a computer system resource, and said step of assigning a job delay cost, and said step of selecting a next job for service, are performed by a job scheduler of said computer system'"'"'s operating system.

3. The method of claim 1, wherein said step of training said neural network comprises the steps of:

gathering data regarding actual performance of said work-producing system; and

using said data as training data for said neural network.

4. The method of claim 3, further comprising the steps of:

continuing to gather data regarding actual performance of said work-producing system in response to scheduling jobs in accordance with said delay cost value function of said neural network; and

updating said neural network using said data gathered in response to scheduling jobs in accordance with said delay cost value function.

5. An apparatus for scheduling jobs in a computer system, comprising:

means for storing a set of user-defined performance goals for a plurality of job classes;

at least one job queue for jobs awaiting service by a resource in said computer system;

means for automatically constructing a substantially optimum delay cost value function, said delay cost value function implementing said set of performance goals, wherein at least one input to said delay cost value function represents a delay time with respect to a job waiting for service by said resource;

means for applying said delay cost value function to each of a plurality of jobs awaiting service by said resource in said at least one job queue for producing a respective delay cost value for each job;

means for comparing the respective delay cost value of each of said jobs to select a next job for service by said resource, wherein the next job for service selected is a job having highest delay cost value.

6. The apparatus for scheduling jobs of claim 5, wherein said means for automatically constructing a substantially optimum delay cost value function comprises means for training a neural network for producing a delay cost value functions, said delay cost value function implementing said set of performance goals as output from at least one input, wherein at least one input to said neural network represents said delay time with respect to a job waiting for service by said resource.

7. A computer implemented method for scheduling jobs from among a plurality of job classes for service by a resource, comprising the steps of:

inputting a set of performance goals for said job classes to a computer;

automatically constructing, with said computer, a substantially optimum delay cost value functions, said delay cost value function implementing said set of performance goals, wherein at least one input to said delay cost value function represents a delay time with respect to a job waiting for service by said resource;

assigning a respective job delay cost to each of a plurality of jobs waiting for service by said resource using said substantially Optimum delay cost will function automatically constructed by said computer; and

selecting a next job for service by said resource based on said job delay cost.

8. The computer implemented method of claim 7, wherein said resource is a resource of said computer system, and said steps of using said substantially optimum delay cost value function to assign a job delay cost, and said step of selecting a next job for service, are performed using a job scheduler of said computer system'"'"'s operating system.

9. A multi-user computer system for processing a plurality of jobs, comprising:

at least one processing unit;

storage means for storing data and programs in said computer system;

I/O means for communicating with a plurality of users and for receiving requests to perform jobs from said plurality of users;

means for automatically constructing a non-linear delay cost value function in response to a set of performance goals input by a user, wherein at least one input to said delay cost value function represents a delay time with respect to a job waiting for service by a resource of said computer system;

means for computing a respective delay cost value for each of said plurality of jobs in accordance with said delay cost value function;

a job scheduler for scheduling jobs from different users for service, said service being provided by one or more resources of said computer system, wherein said jobs are selected for service 1 in accordance with said delay cost value.

10. The multi-user computer system of claim 9, wherein said means for automatically constructing a non-linear delay cost value function comprises:

a neural network for producing a delay cost value as output from at least one input, wherein at least one input to said neural network represents said delay time with respect to a job waiting for service by said resource; and

means for training said neural network to produce a delay cost value function, said delay cost value function implementing said set of performance goals.

11. The multi-user computer system of claim 10, wherein said means for training said neural network comprises:

a performance data gatherer for acquiring data relating to the performance of said system;

means for placing said neural network in a training mode; and

means for inputting data gathered using said performance data gatherer as training data to said neural network.

12. A program product apparatus for scheduling jobs from among a plurality of job classes for service by a resource in a work-producing system, said program product being a plurality of computer executable instructions recorded on a computer-readable medium, said program product comprising:

means for receiving as input a set of performance goals for said job classes;

means for training a neural network to produce a delay cost value function, said delay cost value function implementing said set of performance goals as output from at least one input, wherein at least one input to said neural network represents a delay time with respect to a job waiting for service by said resource;

means for using said delay cost value function produced using said neural network for assigning a respective job delay cost to each of a plurality of jobs waiting for service by said resource; and

means for selecting a next job for service by said resource based on said job delay cost.

13. The program product of claim 12, wherein said means for training said neural network comprises:

means for gathering data regarding actual performance of said work-producing system; and

means for using said data as training data for said neural network.

14. The program product of claim 12, wherein said neural network is an artificial neural network implemented using a plurality of instructions contained in said program product for executing on a computer.