ABSTRACT:
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.