4 ms·
> 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 fo
by jberryman 12y ago
> 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
- bandwitch 12y agoPeterson's Algorithm isn't lock-free, it's a blocking one.
- jberryman 12y agoHmm, 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 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.
- virtue3 12y ago... 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.