OSDev.org

Hi,

Is an ordered list the best mechanism to implement a timer list? I've been reading up a bit about red-black b-trees and it seems an interesting proposition...

What I find attractive about it is, according to wikipedia, it seems to have well defined worst case times.

Inserting items into a large sorted list can be a fairly expensive (and non-deterministic) operation.

I'm curous what your opinion is on this matter.

Does anybody have any links to articles etc on efficient timer queue designs?

Dushara

I don't have a link handy, but I've heard of a technique where you have a sorted list of timers. You sort by a relative time instead of an absolute time, so that the head of the list is always the next timer and whenever its count reaches zero it's time is up.

I think Brendan has implemented this scheme before... maybe he can describe it more coherently (if he's reading this ).

This is described briefly with a little example on the wiki in the article [wiki]Blocking Process[/wiki]. As Colonel Kernel said, Brendan always has something interesting to share regarding scheduling, so you might want to search through his posts.

Thanks for the replies...



This is what I meant when I said "ordered list" sorry if I didn't express myself clearly.

From my understanding, the problem with this scheme is, you have to traverse the whole list if you need to insert an item that belongs at the end (which is quite expensive).

I think the wiki article is also talking about the same thing.



Thanks I'll search his posts...

Dushara

If you are worried about the time it takes to insert an item, consider using a minimum heap, which does insertion in logarithmic time. Checking the minimum element can be done in constant time, but removal is logarithmic.

Ah, I thought you were worried about the time it takes to check when a timer should fire. I guess you're more worried about the scalability of adding new timers (since insertion in a simple list is linear)? How many timers do you expect will be in use typically? If you're optimizing something like this, surely the rest of your OS must be covered in polished chrome by now.

Thanks I'll see if that helps me...



Yes insertion is the issue.



What I've implemented is an RTOS kernel and I ignored most of the issues you guys take into consideration (MMU, networking, file systems, etc). I won't call it chrome, but I'm quite happy with it still... (You would have seen my announcement no doubt).

Once again thanks for the advice.

Dushara

If you're considering implementing red-black trees, I would also point to you http://en.wikipedia.org/wiki/AVL_Tree. AVL trees are very similar in most respects, in that the insertion, deletion and lookup times are the same. The difference is the algorithm used to optimise the tree (stopping it becoming a long linked list in the worst case), and I personally feel the AVL algorithm is easier to understand/implement.

JamesM[/url]

Thanks James...

Yes I'm looking into that as well... but from what I can gather, the AVL trees result in more rotations which can potentially be slower?

Don't know yet.

Dushara

Hi,




No....

If "removeEntry" is only used in the timer IRQ handler with interrupts disabled, and "insertEntry" is only used outside of IRQ handlers with interrupts enabled, then it's likely that the time "removeEntry" takes will be much more important than the time "insertEntry" takes.

Next, don't be fooled by "number of operations" (or "big O" notation). For example, an "O(n)" algorithm with poor cache locality might be much worse than an "O(n^2)" algorithm with good cache locality for all possible values of "n".

Then there's re-entrancy - if you're in the middle of inserting a new entry in the list and get a timer IRQ what are you going to do? For single CPU systems you could disable IRQs for all code that touches the list, but that won't work for SMP. To make it work with SMP you can't use a lock alone (the IRQ handler would cause deadlocks) and you can't use any kind of lock that causes task switches inside an IRQ handler. You could disable interrupts and use some kind of spinlock. The problem with that is there's no way to tell how long the IRQ handler would need to wait before it acquires the lock - for e.g. you could have 15 CPUs trying to get the lock to insert something and a timer IRQ at the same time, and the IRQ handler could be the last one to acquire the lock.

Then there's the quantizing effect of the timer. If the timer IRQ occurs every 10 ms, then you could have a list like "6 ms, 1 ms, 8 ms, 15 ms, 18 ms, 12 ms" and it won't matter. Threads don't need to be in strict order - you only need to sort threads according to the time quantum they wake up in.

Lastly, your kernel should guarantee that a thread will not wake up before it's time expires. This means that (for e.g.) if the timer IRQ occurs every 10 ms and a thread wants to sleep for 1 ms, then you don't know if a timer IRQ will occur 2 us after you put the thread on the list, and need to make it wake up after 11 ms to guarantee that it doesn't wake up sooner than 1 ms.

Based on all of the above, it makes sense to me to have a seperate unsorted list for each time quantum. The nice thing with this (assuming that your kernel does guarantee a thread won't wake up too early) is that the timer IRQ can check the "soonest" list without caring about new threads being added to the list. The problem here is you'd need a huge number of lists (a total of "maximumSleepTime / timeQuantum" lists), but we can "cheat" by using modulo and leaving things on the list if they aren't meant to wake up yet.

For an example (using 65536 singly linked lists):



If I didn't stuff something up (it's untested) this is entirely multi-CPU safe. Inserting an entry is "lock free" (but not "block free").

The timer IRQ handler is "block free". Worst case is many threads sleeping for a very long time and repeatedly being checked, but to be honest I wouldn't worry much about that. With a 10 ms timer IRQ, any thread that sleeps for less than 10.9 minutes (655.36 seconds) is only checked once when it needs to wake up.


Cheers,

Brendan

With a sorted list of timers, wouldn't removeEntry be trivial? You'd always be removing the head of the list...



I was with you until you said "all possible values of 'n'". It may be true for "today's practical values of 'n'", but those values change over time. Also, the difference between n and n^2 as n increases is a whopper... comparing n with n log n might be more appropriate.

This is not true. Yes, an O(n^2) algorithm might perform better then a O(n) for some values [0, X[ but since cache misses are constant time the above statement does not hold for n > X.

Change possible to reasonable.


[Edit]
Sorry, missed Colonel Kernel's reply...