R. Jain, "Control Theoretic Formulation of Operating Systems Resource Management Policies," Ph.D. Thesis, TR-10-78, Center for Research in Computing Technology, Harvard University, Cambridge, MA, May 1978, pp. 193, Also published as a book in Outstanding Dissertations in the Computer Sciences Series, Garland Publishing Company, New York, N.Y., 1979.


This thesis proposes the application of control theory to the dynamic optimization of computer systems performance. Until now, queueing theory has been extensively used in the evaluation and modeling of computer systems. It is a good design and static analysis tool. However, it provides little run time guidance. For dynamic (run time) optimization, we need to exploit modern control theoretic techniques such as state space models, stochastic filte ring and estimation, time series analysis, etc. In this thesis, a general control theoretic approach is proposed for the formulation of operating systems resource management policies. The approach is exemplified by formulating policies for CPU and memory management.

The problem of CPU management is that of deciding which task from among a set of ready tasks should be run next. The main problem encountered in the practical implementation of theoretically optimal algorithms is that the service-time requirements of tasks are unknown. Tbe proposed solution is to model the CPU demand as a stochastic process, and to predict the future demands of a job from its past behavior. Several analytical results concerning the effect of prediction errors are derived. An empirical study of program behavior is made to find a suitable predictor. Several different models are compared. Finally, it is shown that a zeroth order autoregressive moving average model is the most appropriate one. Based on this observation an adaptive scheduling algorithm called ''SPRPT" (Shortest Predicted Remaining Processing Time) is proposed.

The problem of memory management is also formulated as the problem of predicting future page references from past program behavior. Using a zero-one stochastic process model for page references, it is shown that the process is non-stationary. Empirical analysis is presented to show that the page reference pattern can be satisfactorily modeled by an autoregressive integrated moving average model of order 1, 1, 1. A two stage exponential predictor is derived for the model. Based on this predictor a new algorithm called "ARIMA Page Replacement Algorithm" is proposed. This algorithm is shown to be easy to implement. It is shown that many conventional page replacement algorithms, including Working Set, are merely boundary cases of the ARIMA algorithm. The conditions under which these conventional algorithms are optimal are described. The limitations of the formulation and possible directions for future extensions are also discussed.

The ARIMA model does not take into account the fact that a binary process takes only two values, 0 or 1. This discrepancy is removed by developing Boolean models for such processes. It is shown that if a binary process is Markov of a finite known order, it can be modeled as the output of a Boolean (switching) system driven by a set cf binary white noises. Modeling, estimation, and prediction of the process using the Boolean model is described. A method is developed for optimal non-linear prediction under any given non-linear cost criterion. All the results are then generalized to k-ary processes, i.e., processes which take integer values between 0 and k-1. Finally, the application of the model to the problem of memory management is described .

Complete Thesis in Adobe Acrobat format.

Back to the List of Papers
Back to Raj Jain's home page