Re: AVL trees vs. Red-Black trees

Andrea Arcangeli (andrea@suse.de)
Tue, 30 Nov 1999 15:05:14 +0100 (CET)


On Mon, 29 Nov 1999, Oliver Xymoron wrote:

>At any rate, we have to figure out the rules we're going to use for the
>portable kernel and not focus so much on the x86 details. It's not
>immediately obvious where memory barriers should go on the generic system
>so it might be nice if someone laid down the minimum ordering assumptions
>for potential target machines.

Of course the common code is just completly correct and it's also the most
finegrined code we could write there. Also to optimize the x86
implementation we did a set_mb() to let x86 to use xchg while other archs
does a strightforward write + mb().

>(write ordered)? Other processors (processor ordered)? Do we try to hide
>all the interprocessor races inside a small set of macros like
>set_current_state?

For the wait_event interface case the memory barrier must be put between
setting the current->state and the reading if the event happened.
set_current_state() will achieve that (also efficiently).

Each time you write code that runs SMP threaded you must insert the proper
barriers and you must consider each case separately. That's why writing
SMP threaded code is harder ;).

Andrea

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/