river-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Patricia Shanahan <p...@acm.org>
Subject Re: datastructure classes
Date Tue, 14 Dec 2010 08:02:33 GMT
On 12/13/2010 11:32 PM, MICHAEL MCGRADY wrote:
> Patricia
> http://www.cse.lehigh.edu/~spear/
> http://www.cs.rochester.edu/u/vmarathe/
> http://www.cs.rice.edu/~wns1/
> http://www.cs.rochester.edu/u/scott/papers/2003_FTDCS_IW.pdf
> A few other sources that are not so antiquated, which is not a negative.  I have asked
Prof Scott to share his latest research.

Good. I'll read those. Also, I'm trying looking for research on the 
trade-off between blocking and non-blocking.

At the high level, the way I see it is that blocking has the 
disadvantage that preemption of a thread while it holds the lock may 
delay the rest of the threads until the first thread gets back on a 
processor and finishes the critical region. The advantage is that 
processors that are waiting do not use the processor-memory interconnect 
and do not get in the way.

I've seen logic analyzer traces of 64 processors all trying to increment 
the same atomic counter by one. The counter was implemented using 
compare-and-swap. It looked something like this:

64 processors all look at the counter, and see it is zero.
64 processors all try to compare-and-swap change it to one.
1 processor succeeds, and goes on to do something else. The other 63 all 
see the counter has changed, and try again.

63 processors all look at the counter, and see it is one.

The reality was not quite that tidy - some processors might not get to 
see the new value of the counter until it has been incremented a couple 
of times - but the point is that contention costs either way.

In something like outrigger, part of the solution may be to work on 
having the optimal number of threads, so that the processors are kept 
busy as long as there is work to do, but the threads are not tripping 
over each other.


View raw message