Re: [RFC][PATCH] O(1) Entitlement Based Scheduler

[Andy Lutomirski <luto@myrealbox.com>]

How hard would it be to make shares hierarchial?  For example (quoted names are 
just descriptive):

      "guaranteed" (10 shares)       "user" (5 shares)
                |                          |
       -----------------            -----------------
       |               |            |               |
  "root" (1)      "apache" (2)    "bob" (5)       "fred" (5)
       |               |            |               |
(more groups?)    (web servers)   etc.            etc.


This way one user is prevented from taking unfair CPU time by launcing too many 
processes, apache gets enough time no matter what, etc.  In this scheme, numbers 
of shares would only be comparable if they are children of the same node.  Also, 
it now becomes safe to let users _increase_ priorities of their processes -- it 
doesn't affect anyone else.

Ignoring limts, this should be just an exercise in keeping track of shares and 
eliminating the 1/420 limit in precision.  It would take some thought to figure 
out what nice should do.


Also, could interactivity problems be solved something like this:

   prio = (  (old EBS usage ratio) - 0.5  ) * i + 0.5

"i" would be a per-process interactivity factor (normally 1, but higher for 
interactive processes) which would only boost them when their CPU usage is low. 
  This makes interactive processes get their timeslices early (very high 
priority at low CPU consumption) but prevents abuse by preventing excessive CPU 
consumption.  This could even by set by the (untrusted) process itself.


I imagine that these two together would nicely solve most interactivity and 
fairness issues -- the former prevents starvation by other users and the latter 
prevents latency caused by large numbers of CPU-light tasks.


Is this sane?  And does it break the O(1) promotion algorithm?

--Andy