Re: Position paper

[Neal H. Walfield]

Tom,

Sorry for not replying soon.  I've been quite busy the last few days
due to another deadline.

At Sat, 06 Jan 2007 19:26:32 +0100,
Tom Bachmann wrote:
> The paper tries to articulate problems and solutions. While I think it
> does so pretty well, the information density in the text is very high
> (certainly due to the five pages limit imposed), and therefore it is
> relatively hard to "fill in the gaps" of the proposed lowlevel system
> structure (i.e. resource pools).

Your criticism is well placed.

> I think it'd be great if you could
> elaborate on that a bit, concretizing the paper.
> I will outline my present understanding (or better, interpolation) of it
> below, in the hope of making the task easier for you (so you "just" have
> to correct the misstakes, which, however, will certainly be many).
> 
> A resource pool is an abstract entity to manage accounting of resources
> (e.g. cpu time). Associated with it is a scheduling policy (which might
> e.g. include a quota). A resource pool can be used to allocate from it,
> deallocate, subpools can be created (with equal policy),

I'm not sure what you mean here with equal policy.  A derived resource
pool is strictly inferior to its parent.  Derived pools compete for
the resources allocated to their common parent.

Let's consider a user resource pool, the policy on which is that
derived pool are controlled by a proportional share regime.  Alice and
Bob each have a pool derived from the user pool with equal priorities
and thus have an equal share of the resources allocated to the user
pool (assume no one directly allocates from the user pool).  Alice
creates two tasks from each with a new pool derived from her own.  The
tasks' resource pools are inferior to her own.  That is, Alice and Bob
and the two task don't each get 1/4 of the resources: Bob still has
first refusal for half of the resources allocated to the user pool.
Alice's task compete for only what Alice receives according to what
ever policy she set.

> the scheduling
> policy can be changed (e.g. to shrink the resources available from a
> subpool to be given to a child process) to be "worse" than before (e.g.
> a smaller quota), and it can be destroyed, destroying all subpools
> created as well. The mechanism of creating subpools effectively
> organizes resource pool as a tree. There exists a "master pool" from
> which all other pools are (directly or indirectly) derived, which
> scheduling policy basically says "all of the resource is available from
> this pool".

Right.

> Now there are three types of resource pools, for cpu time, for main
> memory, and for backing store memory.

I think these are usually used together and scheduled under the same
policy, there are not three typed resource pools but one general
resource pool out of which all three resources can be allocated.

> Those pools for cpu time are clearest, I think: they have policies like
> "at least 5% of the available time, with priority 7 to get more time" or
> "run at least once every 10ms for 1ms", allowing for both real-time and
> time-shared processing.
> What other examples of scheduling policies exist?

As I said in the paper, I think the two most important policies are
proportional-share and highest priority first (HPF).  There are, of
course, lots of others and as such room for finding an adequate
minimal set.

> However, it is not clear to me how the policies creatable in this way
> can be ordered (e.g., can a pool of the first type exemplfied created as
> a subpool of the second example?).

Does my first example (with Alice and Bob) clarify this point?

> I don't think cpu time pools are to be passed to servers. Although this
> would increase accounting, it would as well horrify the complexity of
> the server and require special kernel support, as has been discussed on
> the list (or on coyotos-dev?).

I think they should.  Especially if we are to try and provide quality
of service guarantees and reduce cross talk.  [1] provides one possible model 
for this.

 [1] U. Steinberg, J. Wolter, H. Härtig: Fast Component Interaction
     for Real-Time Systems

     http://os.inf.tu-dresden.de/papers_ps/steinberg_ecrts2005.pdf

> The pools for main and backing store memory are more complicated, as
> they interact. Main memory policies are probably in the spirit of "at
> least 25 pages accessible at any time" (or maybe even "exactly 25 pages
> accessible at any time"), backing store policies being similar.

I doubt that it useful for a principal to limit a task so precisely.
I think principals have a sense of priorities and a way priorities
should be related.  It is unclear to me that they require more
flexibility.

An application, of course, might request 25 pages and the resource
manager, based on the current policy, might grant that.

> What other policies exist? How are they ordered?

What do you mean by ordered?

> But what happens when pages have to be freed (e.g. because the parent
> shrinks the main memory pool size)?

This is the second important mechanism: applications are able to
specify policy regarding how memory is to be managed.  So the resource
manager looks for the lowest priority page and sends it to backing
store.

> As memory pools are to be passed to
> servers, it must be possible to specify from which backing store pool
> the backing store memory is to be taken when a page is written to disk.

The same pool out of which the memory was allocated.  It may make
sense to describe non-discardable pages are pre-allocated on backing
store thereby avoiding the scenario where the resource pool has no
more backing store available but there memory must be evicted.

> So, as it appears to me, an allocation of a main memory page has to have
> a (potentially void, indicating discardability) backing store allocation
> as an argument, and, as explained in the paper, a priority that gives
> the order in which pages are to be freed. "Backing store pages" can be
> allocated at will.

Basically.

> What happens when the page with the lowest priority is paged out, then
> referenced, which in turn causes the second lowest priority page to be
> freed, which is then next touched, paged in, causing the lowest priority
> page to be freed, and so on? That is, how are malicious applications
> stopped from slowing down the system by dictating a very bad page-out
> policy?

Applications are charged for the memory and CPU time this requires.
Thus, they should only hurt themselves.  Of course, you raise a good
point that I/O bandwidth may also need to be provisioned in a similar
way.


Tom, Thanks for your close reading and your precise questions.  You've
raised a number of important issues which are not clear from the
paper.

Neal