l4-hurd
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Resource Allocation Strategy


From: Neal H. Walfield
Subject: Resource Allocation Strategy
Date: Fri, 13 Jul 2007 14:31:37 +0200
User-agent: Wanderlust/2.14.0 (Africa) SEMI/1.14.6 (Maruoka) FLIM/1.14.6 (Marutamachi) APEL/10.6 Emacs/21.4 (i386-pc-linux-gnu) MULE/5.0 (SAKAKI)

In my last note, I explained how activities are nested and how many
programs are able to adapt to available resources.  I used this to
motivate (1) the allocation of (quasi) physical resources to
activities to enable adaptation, and (2) the distribution of resources
to composite activities according to their expected utility.

If a principal uses its own resources, and the end to which these
resources is put does not affect any other principals, the utility of
an allocation is determined solely by the principal which allocates
the resources.  Thus, maximizing expected utility can be achieved by
allowing activities to direct the resources they are allocated among
their composite activities.

The simplest and seemingly most flexible strategy to achieve this
would be to have an activity act as a resource manager for its
children, interposing all allocation requests and then delegating
resources appropriately.  An alternative approach is to use a central
resource manager.  Based on the preferences and demands of the
activities in the system, this manager formulates an allocation
strategy.  This latter approach appears to have the disadvantage that
a single interface is imposed.  To be successful, such an interface
must be sufficient for all parties.  However, the decentralized
approach, due to its complexity and the general desire to combine
unrelated components, also imposes an interface.  In this case, it is
de facto rather than de jure.  Thus, the real difference appears to be
that the decentralized approach is more expensive and likely results
in less optimal allocations.

Interposition
-------------

When an activity acts as a resource scheduler for its children, it has
maximum control over how resources are allocated between them.  In
principle, this allows the realization of most any conceivable
allocation policy or mechanism a developer may desire.  This control
has a number of costs.  There are computation costs in terms of
interposition and bookkeeping.  There is also the cost of added
complexity.  And, there are questions.  If components are often
combined, how much freedom do developers really have?  Equally
important, to what degree do developers require such control?

When every activity acts as a resource manager for its composite
activities, it interposes on every allocation request; when an
activity requires resources, it asks its parent.  If the parent does
not have sufficient resources, it may have to negotiate additional
resources with its parent, etc.  If the exact same interface is not
used between each child and parent, requests may have to be
translated.  This will likely introduce inaccuracies.  Additionally,
because a resource allocated to an activity is managed by every
ancestor, each must maintain bookkeeping data.  To avoid this series
of interactions for every request, activities may request a small
surplus of resources.  This can lead to resource underutilization.  As
each resource manager only has knowledge regarding its immediate
children, the flow of resources in the system is slowed; tradeoffs are
based on local resource availability.

Building a resource manager is also complex.  This can be mitigated
through the use of standard libraries that only need to be replaced in
exceptional circumstances.  But, if standard libraries are most always
used, then the added control has brought nothing.  Further, if
programs and libraries from different parties are expected to be used
together, a de facto interface will develop.  Again, the increased
flexibility, although technically available, will become practically
impossible to exploit.

Yet, do developpers even desire the control that this model
potentially offers.  Does an activity care which resources an activity
uses?  That is, its preferences are generally not that an activity
receive 5MB of RAM and another 10MB, but that the second activity
remain responsive or complete within a certain amount of time.  This
is analogous to the use of a library: a developer wants a well-defined
interface.  Exactly how a function is implemented is often immaterial.
That is, preferences appear to be qualitative, not quantitative.


Centralization
--------------

The alternative a distributed solution is a centralized one.  In such
a framework, an activity submits its resource requests to a central
manager rather than its parent.  Then, based on the preferences and
the demands, the central manager formulates an allocation strategy.
As the single manager, the costs of interposition is eliminated.
Further, the central manager knows the demands of all entities in the
system, and thus is in a better position to formulate an allocation
strategy that considers more trade-offs.  The problems are then
communicating the demands and preferences in such a way that they can
be realized.

Modelling can be used to obtain information regarding activities'
preferences.  Modelling may be good for large trends, however, it is
unclear to me how effective it can be in determining the preferences
of individual agents over short periods of time.

However, activities can simply communicate their preferences to the
resource manager.  As in the case of resource requests, the language
must be sufficiently expressive to convey the intent but not so
complex as to make drawing inferences too difficult.  These
preferences can be expressed as qualitative attributes.

Preferences cannot be used to game the system.  Preferences are simply
relative rankings.  That is, if an activity indicates that all of its
constituent activities are very important, they don't get any more
resources because the preferences are only used to determine how to
distribute an activity's resources among its constituent activities.


Summary
-------

The key idea is that absolute control is rarely required or exploited,
instead a small number of policies are likely sufficient to provide
the control applications desire.  Indeed, requiring a principal to
negotiate resources for the activities running directly and indirectly
on its behalf is a fool's errand.  Instead, we emphasize decentralized
policy specification and centralized computation of schedules based on
these policies.



--




reply via email to

[Prev in Thread] Current Thread [Next in Thread]