A Model of System Structure and Program Behavior

[Neal H. Walfield]

System Structure
----------------

A general-purpose system consists of a number of computational
activities (hereafter referred to simply as activities).  Typically,
an activity has a single purpose: the delivery of some result to the
activity that initiated it.  An activity may consist of multiple
activities.  These are typically loosely coupled.  That is, there are
few interactions between the sub-activities.  This provides the view
of a system as a nested hierarchy of activities.

This nesting of activities can be observed by considering a typical
desktop scenario.  A user's shell is an activity that acts on behalf
of the user and is the ultimate parent of all activities that run on
the user's behalf.  A user may have a number of programs running on
her behalf.  For instance, a web browser, an editor, an email client,
an audio player, etc.  These programs are very loosely coupled at
most.  Each of these programs may consist of multiple activities.  The
web browser, for instance, may have multiple open tabs, each
displaying a different web site.  Each of tab can be viewed as a
separate activity having little to do with any other tab.  Each web
page may also contain multiple activities: the text as well as images
must be rendered, and active content, perhaps via plug-ins, must be
processed.  Similarly, the email program may have an interactive
window, one activity, as well as an activity that indexes the user's
mail in the background.

This structure can also be observed in server systems.  For a machine
that hosts many virtual machines, each machine can be seen as a
separate activity.  Of course, each guest consists of a number of
programs.

A typical server has two functions: it decomposes authority to some
large resource, and it perform operations on small chunks of that
large resource on behalf of its clients.  In this scenario, each
request can be modelled as a separate activity.


Program Behavior
----------------

Many programs are reactive.  We can identify three types of reactions:
those driven by timeliness requirements, those based on cooperation,
and those based on efficiency.

Many programs have timeliness requirements.  Multimedia programs are
one such example.  Many interactive programs have timeliness
requirements, as well [1].  These programs can change their behavior,
often altering the quality of output, according to the available
resources thereby ensuring that deadlines are met.

Some programs are cooperative and can reduce use based on
availability.  For instance, a program that implements a cache could
adapt the size of the cache according to the amount of otherwise idle
memory in the system.  This would allow the program to exploit the
cache when there are otherwise idle resources, however, to avoid
causing undue memory pressure.

Finally, there are programs that are able to change their
functionality according to the available resources.  Scientific
programs fall into this category.  For instance, when computing matrix
multiply with a very large input, the input can be broken into chunks
that match the size of available memory.  The results can then be
combined.  Similarly, a garbage collector can run its collector
exactly when there is a need.


This model of program behavior is fundamentally different from the
model of program behavior that gave rise to resource management
strategies employed by commodity operating systems--work set.  Denning
claims that the working set model of program behavior provides "an
/intrinsic measurement/ of the program's memory demand---a measurement
that is unperturbed by any other program in the system or by the
measurement procedure itself" [2].  From this statement, it is clear:
programs do not adapt their functionality according to available
resources.


A Utility Directed Approach to Resource Scheduling
--------------------------------------------------

This double observation, that activities are nested and that
activities adapt to available resources, suggests the following
approach to resource management: (1) activities should be allocated
near physical resources and (2) these should be able to divide these
resources among their composite activities according to their relative
importance (i.e., their expected utility).


Neal


[1] Jakob Nielsen, Usability Engineering, 1994
    http://www.useit.com/papers/responsetime.html

[2] Peter J. Denning, Working Sets Past and Present, 1980.

--