Method for scheduling jobs using distributed utility-based preemption policies

A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for assigning jobs to a system containing a number of central processing units (CPUs), comprising:

• capturing a current state of the system, which describes available resources on the system, characteristics of jobs currently being processed, and characteristics of jobs waiting to be assigned, wherein capturing the state of the system involves describing the system state with respect to the CPUs and jobs with a set of state variables;
• using the current system state to estimate a long-term benefit to the system of not preempting any jobs currently being processed by feeding the set of state variables to a fuzzy rulebase to obtain an output which indicates a long-term expected utility, wherein the output of the fuzzy rulebase Q is computed as follows:
• Q
• =
• ∑
• i
• =
• 1
• 8
• ⁢
• A
• ⁡
• [
• i
• ]
• ·
• q
• ⁡
• [
• i
• ]
• ∑
• i
• =
• 1
• 8
• ⁢
• A
• ⁡
• [
• i
• ]
• ,
• wherein q[i] (i=1, . . . , 8) denote rulebase parameters and wherein activation of a fuzzy rule i (i=1, . . . , 8), which is denoted as A[i], is a product of degrees to which the state variables satisfy the preconditions for the fuzzy rules;
• identifying a new job with which the preemption of jobs currently being processed in the system results in a higher Q value;
• and
• preempting one or more jobs currently being processed on the system with the identified new job.

A computer system that assigns jobs to a number of central processing units (CPUs), comprising:

• one or more CPUs;
• an I/O mechanism;
• a memory system;
• and
• software stored in the memory system, wherein the software is configured to:
• capture a current state of the system, which describes available resources on the system, characteristics of jobs currently being processed, and characteristics of jobs waiting to be assigned, wherein capturing the state of the system involves describing the system state with respect to the CPUs and jobs with a set of state variables;
• use the current system state to estimate a long-term benefit to the system of not preempting any jobs currently being processed by feeding the set of state variables to a fuzzy rulebase to obtain an output which indicates a long-term expected utility, wherein the output of the fuzzy rulebase Q is computed as follows:
• Q
• =
• ∑
• i
• =
• 1
• 8
• ⁢
• A
• ⁡
• [
• i
• ]
• ·
• q
• ⁡
• [
• i
• ]
• ∑
• i
• =
• 1
• 8
• ⁢
• A
• ⁡
• [
• i
• ]
• ,
• wherein q[i] (i=1, . . . , 8) denote rulebase parameters and wherein activation of a fuzzy rule i (i=1, . . . , 8), which is denoted as A[i], is a product of degrees to which the state variables satisfy the preconditions for the fuzzy rules;
• identify a new job with which the preemption of jobs currently being processed in the system results in a higher Q value;
• and
• to preempt one or more jobs currently being processed on the system with the identified new job.