As computer technology advanced and the complexity of computer systems and applications continued to grow, new customer and/or user requirements arose that were not fully addressed by previous classes of scheduling objective functions.  For this reason, research studies at IBM investigated specific scheduling optimization problems to consider the needs of certain IBM computer platforms.  Two such studies became the basis for the processor scheduling algorithms in the Application System/400 (AS/400) and System/390 (S/390) computer systems.

Basis for the AS/400 Processor Scheduler:

Much of the previous scheduling research considered scheduling strategies for minimizing a weighted sum of the per-class mean response times.  An important additional objective is to maintain a low variance of response times for each class.  Two related research studies at IBM that investigated this problem resulted in the concepts of Delay Cost Scheduling, due to Franaszek and Nelson (1995), and Time-Function Scheduling, due to Fong and Squillante (1995).  These two studies considered different forms of objective functions that are based on minimizing a weighted sum of per-class second moment measures of response time, and they used different approaches to establish certain structural properties for the respective optimal solutions.

One scheduling strategy with the structural properties for a particular instance of the scheduling objectives considered by Fong and Squillante is based on the use of general time-based functions to obtain effective and flexible control over the allocation of resources.  This scheduling strategy is in part a generalization of the linear time-dependent priority discipline due to Kleinrock (1964) in which the priority of each job increases (linearly) according to a per-class function of some measure of time and the job with the highest instantaneous priority value in the queue is selected for execution at each scheduling epoch.  In its most general setting, the time parameter for each per-class function can include any measure of the time spent waiting for a resource or set of resources (response mode), any measure of the time spent using a resource or set of resources (usage mode), and any combination of such modes, as developed by Fong, Hough and Squillante (1997).  An adaptive feedback mechanism is used together with mathematical control formulas to adjust these per-class time functions, as well as to migrate each job to a different class upon the occurrence of certain events or upon the job exceeding some criteria, in order to satisfy the scheduling objective function across all and/or varying workloads.  These control formulas can also be used to obtain a scheduling strategy that realizes the optimal or desired performance vector which is a (interior) point in the performance space, while providing better per-class response time variance properties.  A number of important scheduling issues can be easily accommodated in the per-class time functions and/or addressed by the use of these time functions to control resource scheduling decisions; examples include priority inversion and processor-cache affinities.  The theoretical properties of time-function scheduling can be further exploited to obtain very efficient implementations. 

The above scheduling strategy is a fundamental aspect of the dynamic priority scheduling algorithms employed in AS/400 systems.  Based on the control formulas mentioned above and a general set of assumptions regarding workloads and performance objectives, this scheduling technology offering has proven to be a great success with AS/400 customers providing efficient and effective control over resource management to address various customer requirements across numerous diverse workloads without any perceived increase in complexity by the system administrator and users. 

Basis for the S/390 Processor Scheduler: 

Instead of minimizing a weighted sum of the per-class mean response times, it can be more natural to associate a mean response time goal with each class and to consider the performance of the class relative to its goal.  The corresponding objective function then is to minimize a vector of the per-class ratios of the response time mean to the response time goal.  This problem is studied within the context of a multi-class M/GI/1 queue, with and without feedback, by Bhattacharya et al. (1993,1995) where adaptive scheduling strategies are presented and shown to lexicographically minimize the vector of per-class performance ratios (exactly or approximately).  The results also apply to other systems including certain multi-class Jackson networks and multi-class M/GI/c queues. 

Consider a $K$-class system at a scheduling decision time epoch in which the mean response time for class $i$ realized over the previous scheduling time interval(s) is $x_i$ and the specified mean response time goal for this class is $g_i$.  A fixed scheduling policy that gives priority to jobs of class $i$ over jobs of class $j$ if $x_i/g_i \geq x_j/g_j$ is then used for the next scheduling time interval.  In other words, priority is given to the class that has received the worse performance, relative to its goal, over the previous time interval(s).  The time intervals between scheduling decision epochs, in which priorities are updated, can be arbitrary provided that they are bounded above by a finite measure.  This scheduling strategy is proven optimal in the sense that it converges asymptotically in the number of time intervals to the optimal solution which lexicographically minimizes the vector of ratios $x_i/g_i$ arranged in non-increasing order $x_1/g_1 \geq x_2/g_2 \geq \cdots \geq x_K/g_K$ (with probability 1). 

The above scheduling strategy is an important aspect of the processor scheduling algorithms employed in S/390 systems, where $x_i$ and $g_i$ can be functions of performance metrics other than just mean response time -- in particular, response time percentiles and/or velocity goals can be used together with or instead of mean response time goals.  This S/390 concept is commonly referred to as goal-oriented scheduling.  It is a key component of the workload management system provided on S/390 computers, which has been a great success for IBM in the control and management of mainframes and mainframe clusters.

Various aspects of each of these principal cluster architecture alternatives have been analyzed with performance models, many of which have been formulated by decomposing the original problem into more tractable parts.  The solutions of these hierarchical models have often involved a combination of different methods including analytical, mathematical optimization and simulation.  The results of this analysis of the principal cluster architectures by researchers at IBM, such as King et al. (1997), and elsewhere influenced the design of the IBM S/390 Parallel Sysplex architecture, and was used by IBM to demonstrate the key advantages of this design over alternative cluster architectures.  In particular, the Parallel Sysplex architecture provides the benefits of shared-disk architectures and exploits the coupling facility services to obtain very efficient intertransaction concurrency control, buffer cache coherency control, shared buffer management, and shared job queues.  This results in transaction rate scaling which is close to linear in the number of nodes, high shared buffer hit ratios which can reduce the I/O rate per node, and excellent dynamic load balancing even in systems with heterogeneous nodes.