jed at atlassian.com
Sun Dec 13 18:35:40 EST 2009
This is definitely platform dependent, related to how the hardware
implements the CAS instruction, and specifically how the cache coherence
protocols work. Under heavy contention, CAS based algorithms tend to
degrade exponentially (or at least, worse than linearly as failed set
operations invalidate cache entries, so even an otherwise successful set
will need to reload from main memory. I am pretty sure that on most
current hardware designs this is not a wait-free algorithm.
For a thorough explanation, see The Art of Multiprocessor Programming
(Herlihy & Shavit) for the performance problems of a TASLock (7.2, 7.3
and App.B) which is a CAS based lock implementation.
Hans Boehm wrote:
> On Sat, 12 Dec 2009, bank kus wrote:
>> Is this guaranteed to complete in a finite number of steps. Asking
>> because am evaluating if I can implement ticket locking using this.
>> On a 16 virtual core system if all 16 vcores simultaneously had
>> threads invoke this operation ..
>> <a> are all vcores guaranteed to block context switching to any other
>> threads on their runqueues until this operation completes
>> <b> is there fair arbitration between cores. The pathological case
>> being vcore 2 gets to increment then gets to do it again while other
>> vcores wait trying to do so.
>> I understand this would depend upon the hw instructions used but am
>> curious if any fair expectation can be made out of this API.
> Given that that the JLS is intentionally silent on any sort of
> fairness guarantee for thread scheduling, I doubt that you can
> guarantee anything of this kind without making some platform
> assumptions. I expect that general purpose implementations and most
> hardware will generally do the right thing ...
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
More information about the Concurrency-interest