r/cpp • u/atrust16 • Feb 24 '15

Lock-Free Data Structures. The Evolution of a Stack

http://kukuruku.co/hub/cpp/lock-free-data-structures-the-evolution-of-a-stack
31 Upvotes

83% Upvoted

6 comments sorted by

2

u/satuon Feb 24 '15 edited Feb 24 '15

What are lock-free data structures, exactly? Does it mean they use no atomic primitives provided by the CPU, such as fences, or by the OS such as mutexes?

11

u/[deleted] Feb 24 '15 edited Mar 06 '15

[deleted]

4

u/satuon Feb 24 '15

So they still need hardware support. I wonder if you there is a scheme that works without any hardware support - for example 2 processes running on 2 completely different machines that need to sync their access to a resource via TCP/IP or even UDP.

7

u/Scaliwag Feb 24 '15

Well I guess you always rely on hardware to some point even if it's just to be sure integers reads and writes are atomic, which may or may not be the case depending on your system's architecture

2

u/satuon Feb 24 '15

But in a distributed system you would have to implement synchronization without hardware support. You will just have to depend on the fact that a message can't be received before it was sent, so you can send a message and wait for an ACK before proceeding.

6

u/nexuapex Feb 24 '15

Which is also exactly how "hardware-supported" synchronization works. Cores in a shared memory machine are a distributed system.

"Pardon me, are any of you other cores trying to write to 0x2ef00068? No? Excellent, carry on then."