Re: [Announce] [patch] Modular Scheduler Core and Completely Fair Scheduler [CFS]

Davide Libenzi
2007-04-14T22:38:12Z

On Fri, 13 Apr 2007, William Lee Irwin III wrote:

> On Fri, Apr 13, 2007 at 10:21:00PM +0200, Ingo Molnar wrote:
> > The CFS patch uses a completely different approach and implementation
> > from RSDL/SD. My goal was to make CFS's interactivity quality exceed
> > that of RSDL/SD, which is a high standard to meet :-) Testing
> > feedback is welcome to decide this one way or another. [ and, in any
> > case, all of SD's logic could be added via a kernel/sched_sd.c module
> > as well, if Con is interested in such an approach. ]
> > CFS's design is quite radical: it does not use runqueues, it uses a
> > time-ordered rbtree to build a 'timeline' of future task execution,
> > and thus has no 'array switch' artifacts (by which both the vanilla
> > scheduler and RSDL/SD are affected).
>
> A binomial heap would likely serve your purposes better than rbtrees.
> It's faster to have the next item to dequeue at the root of the tree
> structure rather than a leaf, for one. There are, of course, other
> priority queue structures (e.g. van Emde Boas) able to exploit the
> limited precision of the priority key for faster asymptotics, though
> actual performance is an open question.

Haven't looked at the scheduler code yet, but for a similar problem I use
a time ring. The ring has Ns (2 power is better) slots (where tasks are
queued - in my case they were som sort of timers), and it has a current
base index (Ib), a current base time (Tb) and a time granularity (Tg). It
also has a bitmap with bits telling you which slots contains queued tasks.
An item (task) that has to be scheduled at time T, will be queued in the slot:

S = Ib + min((T - Tb) / Tg, Ns - 1);

Items with T longer than Ns*Tg will be scheduled in the relative last slot
(chosing a proper Ns and Tg can minimize this).
Queueing is O(1) and de-queueing is O(Ns). You can play with Ns and Tg to
suite to your needs.
This is a simple bench between time-ring (TR) and CFS queueing:

http://www.xmailserver.org/smart-queue.c

In my box (Dual Opteron 252):

davide@alien:~$ ./smart-queue -n 8
CFS = 142.21 cycles/loop
TR = 72.33 cycles/loop
davide@alien:~$ ./smart-queue -n 16
CFS = 188.74 cycles/loop
TR = 83.79 cycles/loop
davide@alien:~$ ./smart-queue -n 32
CFS = 221.36 cycles/loop
TR = 75.93 cycles/loop
davide@alien:~$ ./smart-queue -n 64
CFS = 242.89 cycles/loop
TR = 81.29 cycles/loop

- Davide