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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[Index of Archives]
[Kernel Newbies]
[Netfilter]
[Bugtraq]
[Photo]
[Stuff]
[Gimp]
[Yosemite News]
[MIPS Linux]
[ARM Linux]
[Linux Security]
[Linux RAID]
[Video 4 Linux]
[Linux for the blind]
[Linux Resources]
