What I call "infinite loop" you call "starvation". So theoretically "arbitrarily many loops before setting succeeds" might become "infinite number of loops before setting succeeds". So why not modify algorithm to try N time to succeed and then throw an exception? Or something else?
-----Original Message----- From: Discussion of advanced .NET topics. [mailto:[EMAIL PROTECTED] On Behalf Of Barry Kelly Sent: Saturday, April 14, 2007 12:05 To: [EMAIL PROTECTED] Subject: Re: [ADVANCED-DOTNET] Lock-free collections Alex Ivanoff <[EMAIL PROTECTED]> wrote: > I looked at a couple of lock-free collection implementations (Richter's > PowerThreading Library, Lock-free LIFO Stack > http://msdn.microsoft.com/msdnmag/issues/07/05/CLRInsideOut/default.aspx#S7 > , etc.) based on InterlockedCompareExchange. All of them have potential of > going into infinite loop in Push/Enqueue/Pop/Dequeue methods. Although the > probability is very low it still exists. Can you explain your objection? The test and set loop that is at the root of most lock-free data structures only loops while there are concurrent modifications. How can it be infinite? It's not like you can get two loops causing each other to repeat, because the modification only occurs if the value tested hasn't changed, and thus one loop would always win and exit, letting the other through next time around. A possible "problem" is starvation due to too much concurrent access, resulting in arbitrarily many loops before setting succeeds, but this is no different from any other shared-state concurrency technique. -- Barry -- http://barrkel.blogspot.com/ =================================== This list is hosted by DevelopMentor. http://www.develop.com View archives and manage your subscription(s) at http://discuss.develop.com =================================== This list is hosted by DevelopMentor� http://www.develop.com View archives and manage your subscription(s) at http://discuss.develop.com
