Re: [PATCH 11/13] hrtimer: turn hrtimers into range timers

!MAILaRCHIVE_VOTE_RePLACE
Previous message: [thread] [date] [author]
Next message: [thread] [date] [author]
To: Arjan van de Ven <arjan@...>
Cc: <linux-kernel@...>, <torvalds@...>, <dwmw2@...>, <drepper@...>, <mingo@...>, <tglx@...>, Fabio Checconi <fabio@...>
Date: Tuesday, September 2, 2008 - 7:08 am

On Tue, 2008-09-02 at 10:22 +0200, Peter Zijlstra wrote:

What you need is a data structure that supports stabbing queries on
overlapping intervals, such like a Priority Search Tree.

If I'm not mistaken, then the augmented Red-Black tree from the EEVDF
paper is identical to PST [*].

This data-structure adds a Heap property to each RB-node, allowing one
to search the tree on a different property.

So what you can do in this case, is index the RB-tree on the soft
expire, and index the heap on the hard expire.

Then you can find the leftmost hard expire by traversing the tree using
the heap property - and program the clock-event using that time.

And you can search for soft expired entries using the RB-tree like we do
now.


[*] Fabio implemented it on top of the linux RB-tree for their wf2q+
implementation that they used for their BFQ I/O scheduler:

http://feanor.sssup.it/~fabio/linux/wfq/

And I borrowed their implementation for my scheduler work:

http://programming.kicks-ass.net/kernel-patches/sched-eevdf/sched-eedf.patch



--
Previous message: [thread] [date] [author]
Next message: [thread] [date] [author]

Messages in current thread:
[PATCH 0/13] Turn hrtimers into a range capable timer, Arjan van de Ven, (Mon Sep 1, 7:03 pm)
Re: [PATCH 0/13] Turn hrtimers into a range capable timer, Rusty Russell, (Thu Sep 11, 11:39 pm)
Re: [PATCH 0/13] Turn hrtimers into a range capable timer, Thomas Gleixner, (Fri Sep 12, 4:24 pm)
Re: [PATCH 0/13] Turn hrtimers into a range capable timer, Arjan van de Ven, (Fri Sep 12, 1:42 am)
Re: [PATCH 0/13] Turn hrtimers into a range capable timer, Arjan van de Ven, (Sat Sep 6, 12:30 pm)
[PATCH 9/13] hrtimer: convert sound/ to the new hrtimer apis, Arjan van de Ven, (Mon Sep 1, 7:11 pm)
[PATCH 8/13] hrtimer: convert s390 to the new hrtimer apis, Arjan van de Ven, (Mon Sep 1, 7:10 pm)
Re: [PATCH 12/13] hrtimer: create a "timer_slack" field in t..., Arjan van de Ven, (Sun Sep 14, 12:14 pm)
Re: [PATCH 12/13] hrtimer: create a "timer_slack" field in t..., Arjan van de Ven, (Sun Sep 14, 11:27 am)
[PATCH 2/13] hrtimer: convert kvm to the new hrtimer apis, Arjan van de Ven, (Mon Sep 1, 7:05 pm)
[PATCH 11/13] hrtimer: turn hrtimers into range timers, Arjan van de Ven, (Mon Sep 1, 7:13 pm)
Re: [PATCH 11/13] hrtimer: turn hrtimers into range timers, Arjan van de Ven, (Tue Sep 2, 9:05 am)
Re: [PATCH 11/13] hrtimer: turn hrtimers into range timers, Arjan van de Ven, (Tue Sep 2, 12:02 pm)
Re: [PATCH 11/13] hrtimer: turn hrtimers into range timers, Peter Zijlstra, (Tue Sep 2, 7:08 am)
Re: [PATCH 11/13] hrtimer: turn hrtimers into range timers, Arjan van de Ven, (Tue Sep 2, 9:06 am)