S E L F - A D A P T I V E S O F T W A R E
Control Theory-Based
Foundations of Self-
Controlling Software
Mieczyslaw M. Kokar, Kenneth Baclawski, and Yonet A. Eracar, Northeastern University
ALGORITHMS WITH EMBEDDED
control and adaptation are common in soft-
ware systems. Some examples are
•
software for dynamically adjusting a
database-management system’s buffering
strategy,
•
routing algorithms for networks,
•
load-balancing algorithms for distributed
computer systems,
• graphical user interfaces that adapt to the
user, and
•
caching strategies for OS memory man-
agement.
All these software subsystems interact with
an environment that could be the external phys-
ical world or another layer of the computer sys-
tem. Such environments can be characterized
as dynamic systems.1 The essence of a dynamic
system is that its output depends on the system’s
state. So, the system does not shift dramatically
from one output to another (in response to
changes in the input) but exhibits some form of
inertia (because of the dependence on state).
When designing a software system that inter-
acts with a dynamic environment, software
engineers need to take into account the dynamic
characteristics of the environment and computer
system, or the system might behave differently
from what the engineer expected.
In computer systems, the first observed
form of inertia was locality of reference. This
property has been exploited heavily ever since
in both hardware and software. Hardware
devices use caches and buffers to exploit
locality of reference. Operating systems use
locality of reference to improve the perfor-
mance of virtual memory and file systems.
Communication networks have two kinds of
locality of reference. Physical locality of ref-
erence is the tendency for communication to
be between computers that are physically near
one another. Temporal locality of reference is
the tendency, once a pair of computers has
communicated, for that pair to communicate
again in the near future, and then repeatedly.
In spite of the obvious ana