NOT using the System.Threadpool in server class applications

[Chris Mullins]

"Carl Daniel [VC++ MVP]"

I have, a couple years back. It would be interestsing to dust that code
off, make it .NET friendly (it's native C++), and use it to build a
UMS-like framework for .NET. That'd be a powerful tool to have in the
.NET toolbox.

.... and here I thought I was hardcore. You, sir, are well and truly sick!

 

[Chris Mullins]

That's Maged Michael and Michael Scott's lock free queue algorithm if you
want to google for it.

Wow. I just spent some time reading Maged Michael's paper's over at IBM
reasearch. He's got some great, great stuff in there. Thanks for the
pointer.

Any idea if I can find nice (and debugged) C# implementations of his
algorithms?

 

[Vadym Stetsyak]

Hello, Chris!

CM> Any idea if I can find nice (and debugged) C# implementations of his
CM> algorithms?

Yep, the stuff is great out there.
Also some of the algorithms are in the links provided by you, namely CAS,
( http://www.boyet.com/Articles/LockfreeStack.html )

--
Regards, Vadym Stetsyak
www: http://vadmyst.blogspot.com

 

[Joe Seigh]

| gate.lock();
| queue.lock();
| for (; {
| if queue.empty()
| timeout = INFINITE;
| else
| timeout = queue.peek().deadline - now;
|
|
| if (timeout < 0)
| break;
|
| queue.unlock();
| event.wait(); // autoreset event
| queue.lock()
| }
|
| item = queue.pop();
| queue.unlock();
| gate.unlock();
|

I am not following that totally.
1) if queue is empty timeout is set to -1 (i.e. INFINITE). The next "if" is
then true and does a break. Then you try to pop() an empty queue? This
does not seem right. Please help.
2) Where else do you wait on timeout? Should it be event.wait(timeout)
instead of event.wait()?

tia

Right that should be "if (timeout != INFINITE && timeout < 0)"
and "event.wait(timeout)".

 

[Joe Seigh]

Wow. I just spent some time reading Maged Michael's paper's over at IBM
reasearch. He's got some great, great stuff in there. Thanks for the
pointer.

Any idea if I can find nice (and debugged) C# implementations of his
algorithms?

I'm not sure. Most of the stuff I did was read lock-free (as opposed
to write lock-free) and mainly used RCU, Maged's SMR hazard pointers,
or lock-free reference counting for the GC component of the lock-free
algorithms. So you could have read lock-free hash tables, linked lists,
or even balanced binary trees if I had ever gotten around to working out
the heuristics for balancing (you can't just plug in the current
AVL or Red/Black algorithms as is). But too much patent activity in
that area so I shut down those projects.

You could take a look at the java.util.concurrent classes in the latest
version of Java to see how they did it. JSR-166 added in lock-free support.
They basically use double wide interlocked compare and exchange to
implement the AtomicMarkableReference and AtomicStampedReference classes.
You need stuff like that to avoid the ABA problem. You can use tracing GC if
it's built in to avoid the ABA problem like the article above did but
for a high throughput queue, you are going to generate a lot of garbage
for the GC to collect.