Browse Prior Art Database

Goal Oriented Central Processing Unit Scheduling

IP.com Disclosure Number: IPCOM000106776D
Original Publication Date: 1993-Dec-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 8 page(s) / 345K

Publishing Venue

IBM

Related People

Bhattacharya, P: AUTHOR [+6]

Abstract

This invention addresses the problem of goal-oriented CPU management. Work entering the computer system is categorized into service classes, each with its own response time or service rate goal. The problem is to devise effective, low overhead algorithms that enforce the response time goals, if achievable, even as arrival rates, workloads or computer configurations change, and with no a priori knowledge of service class CPU consumption characteristics. Algorithms are presented that provide effective ways to achieve performance time goals, if the goals are achievable, in a way adaptive to workload changes.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 24% of the total text.

Goal Oriented Central Processing Unit Scheduling

      This invention addresses the problem of goal-oriented CPU
management.  Work entering the computer system is categorized into
service classes, each with its own response time or service rate
goal.  The problem is to devise effective, low overhead algorithms
that enforce the response time goals, if achievable, even as arrival
rates, workloads or computer configurations change, and with no a
priori knowledge of service class CPU consumption characteristics.
Algorithms are presented that provide effective ways to achieve
performance time goals, if the goals are achievable, in a way
adaptive to workload changes.

      The invention is organized as follows: in section "Workload
Environment and Goal Specification" we present the workload
environment we are considering and provide the exact specification of
goals for the service classes.  A basic algorithm for evaluating the
criticality of the service classes is provided in section "Basic
Algorithm for Calculating Workload Imporatnce".  In section
"Algorithms for Adaptive CPU Scheduling", we present methods for
dynamically allocating CPU time to the service classes based on their
criticality.

      WORKLOAD ENVIRONMENT and GOAL SPECIFICATION - Assume that every
unit of work in the system belongs to a unique class which we call a
service class.  The exact resource requirements of the units of work
are not known beforehand, it is assumed however that units of work
belonging to the same service class have similar resource consumption
characteristics.  Units of work arrive in the system at random times.

      Since the exact resource requirements of the units of work are
not known beforehand, it may be desirable to specify different
response time or service rate goals for units of work with different
resource requirements within the same workload.  To accomplish this,
service class i is further subdivided into k sub i , %% k sub i ge 1,
subclasses which we call "periods".  Service class periods are
defined as follows: Let s be the CPU time for a unit of work.  Units
of work of service class i such that <S sub l-1 sup i > lt s le <S
sub l> sup i are considered to belong to period l.  <S sub <k sub i>>
sup i - i.e. the upper bound of s for the last period - is considered
to be infinite, while <S sub 0> sup i = 0 by convention.  The period
to which a unit of work belongs is not known when the unit of work is
generated.  All units of work belonging to a specific workload, start
in period 1 and are moved to higher periods as their execution time
exceeds the appropriate thresholds.

      With period l of service class i we associate a response time
goal g sub i ( <S sub l> sup i ) or a service rate goal h sub i (<S
sub l> sup i ).  The response time goals for periods other than the
last, satisfy the following relation:

  <S sub l> sup i lt g sub i ( <S sub l> sup i )

In addition, the following inequalities hold for al...