Dynamic Scheduling of Large Digital Computer Systems Using Adaptive Control and Clustering Techniques

This research is directed toward the development of a scheduling algorithm for large digital computer systems. To meet this goal methods of adaptive control and pattern recognition are applied. As jobs are received by the computer, a pattern recognition scheme is applied to the job in an attempt to classify its characteristics, such as a CPU-bound job, an I/O job, a large memory job, etc. Simultaneously, another subsystem, using a linear programming model, evaluates the overall system performance, and from this information an optimized (or desired) job stream is determined. When the processor requests a new job, it is chosen from the various classifications in an attempt to meet the optimal (or desired) job stream. After the jobs are completely processed, their characteristics are compared to the projected classification produced by the pattern discriminant function. The results are then returned to the discriminant function to update the decision mechanism, a minimum-distance discriminant function. From a systems point of view, this results in an adaptive or self-organizing control system. The overall effect is a dynamic scheduling algorithm. Simulation studies indicated that the scheduler was able to adapt to changing work loads, and it improved the turnaround times significantly. These simulation studies were based on a multiprocessor-uniprogram environment.