Hacker News Reader

Comment by jberryman | Hacker News Reader

> It’s quite difficult, if possible at all, to contrive an algorithm of a lock-free container, which uses read/ write only (I don’t know such data structures for a random number of threads).

I don't know either, but Peterson's Algorithm is a mind-melting and elegant way to achieve mutual exclusion for two threads, using reads and writes (and in reality probably some barriers), generalizable to N threads.

  http://en.wikipedia.org/wiki/Peterson%27s_algorithm

View on HN

Peterson's Algorithm isn't lock-free, it's a blocking one.

Hmm, are you sure that's correct? I believe both the qualities re. "progress" and "bounded waiting" here

http://en.wikipedia.org/wiki/Peterson%27s_algorithm#Progress

are enough to guarantee system-wide progress. Can you elaborate?

Edit: Nevermind. So of course we'd need the critical section and thread-coordination mechanism to be a single atomic operation for this to be a lock-free algorithm. I should RTFA.

... if you look at the psuedo code the "busy wait" (with a busy while loop...) comment and "critical section" comment should also be very large flags to this being a blocking operation.

Reply on news.ycombinator.com