Scheduling Memory in Viengoos

[Neal H. Walfield]

In this note, I very briefly describe how memory is scheduled in
Viengoos and how the per-principal availability metric is calculated.


Principals (called activities) on Viengoos form a hierarchy.  A parent
is able to set the scheduling policy for its immediate children.  When
an activity allocates memory, it is allocated out of its parent's
allocation.


                     o
                10  / \  20
                   o   o

One scheduling parameter is weight.  In the above figure, an activity
has two children, one with weight 10, the other with weight 20.  This
means that the former's share is 1/3 (= 10/(10+20)) of the parent's
allocation, and the latter's share is 2/3s (= 20/(10+20)).


As long as there is memory available, memory allocations are granted.
That is, the Viengoos scheduler is work conserving.  When this is no
longer the case, Viengoos must decide which activity must yield
memory.  This is accomplished by walking the activity hierarchy
starting at the root to find the activity that most exceeds its share
according to its scheduling parameters.  (As nodes as well as leaves
can allocate memory, each activity actually has two scheduling
policies: a child relative policy and a sibling relative policy.  The
sibling relative policy may only be set by the activity controller.
The child relative can be set by the activity itself and controls when
locally allocated resources should be less preferred than child
allocated resources.)

For example, assume there is 100MB RAM available to the parent.  In
this case, the former's share is 33MB and the latter's 67MB.  If the
first child has allocated 40 and the second 60, the the first child
will be chosen to release some memory.


Viengoos also provides a per-principal notion of availability.  The
very short version of how this is calculated is:

  A.available = MAX (A.share, A.allocated * A.pressure)

The share is derived from the scheduling policy and the amount
allocated is exactly that: the amount currently allocated.  When an
activity is selected to revoke pages, its pressure is increased.  The
result is that the available memory decreases.

Continuing with the above example, the first child's share is 40MB and
the second's 67.  Assume that we revoke 5MB from the first child.
This means that its allocation is now 35MB and its pressure has
increase.  When we report the availability to the child, we will not
report 35, but perhaps 34 so as to encourage it to free a bit more
memory.


Availability, along with some other statistics, is regenerated for
each active activity about every 2 seconds.  A thread can wait for
these statistics and when they are made available, it is notified.
This removes the need for polling.