Re:Lock-free multithreading with atomic operations
by kccqzy on Tuesday July 30, 2019 @03:21AM
(#20562747)
On the hardware level for example the x86 some of these atomics translate into instructions with the lock prefix which locks the bus. It's different from the usual "lock" concept in concurrent programming.
[ Parent
| on HN ]
Re:Lock-free multithreading with atomic operations
by amelius on Tuesday July 30, 2019 @03:27AM
(#20562780)
It's still a lock in the sense that it momentarily prevents another process from using a resource.
Re:Lock-free multithreading with atomic operations
by denormalfloat on Tuesday July 30, 2019 @03:39AM
(#20562829)
The correct term to use here is blocking. The hardware bus locks finish in a bounded amount of time and allow the other processors to eventually make progress.
Re:Lock-free multithreading with atomic operations
by amelius on Tuesday July 30, 2019 @04:54AM
(#20563178)
That is a good distinction, but I'm not sure if it's always true. A peripheral device on a shared bus could still hold the lock for an undetermined time.
Re:Lock-free multithreading with atomic operations
by jasonwatkinspdx on Tuesday July 30, 2019 @05:34AM
(#20563316)
When people say "lock the bus" they don't literally mean it's like there's a single bus and mutex.
Atomic operations execute atop the cache consistency protocol, which typically looks like: https://en.wikipedia.org/wiki/MOESI_protocol
It is indeed true that atomic operations will execute in a bounded time, and processors generally provide fairness guarantees as well.
Re:Lock-free multithreading with atomic operations
by gpderetta on Tuesday July 30, 2019 @07:16AM
(#20563750)
Yes. Even better than that, atomic instructions are usually completely local to a core. I think that the only interaction with with the coherency protocol is that a core is guaranteed to be able to hold a cache in exclusive mode long enough to execute an RMW (and even that it is not really required, but useful to guarantee forward progress).
Re:Lock-free multithreading with atomic operations
by namibj on Wednesday July 31, 2019 @11:32AM
(#20575214)
Since NVLink2 and POWER9, even a GPU can issue atomics over the bus, which will be executed local to the CPU that owns this cacheline.
This is very useful in high-contention write-heavy workloads, like atomic counters or accumulators.
Re:Lock-free multithreading with atomic operations
by amelius on Tuesday July 30, 2019 @06:31AM
(#20563520)
Yes, and the cache hierarchy ultimately depends on the memory bus. I suppose this bus, which may be shared with many other devices, doesn't always have bounded-time guarantee.
Re:Lock-free multithreading with atomic operations
by gpderetta on Tuesday July 30, 2019 @07:18AM
(#20563766)
Even to main memory there is not necessarily a single memory bus. Intracore or even intrasocket synchronization need not (and usually doesn't) go through main memory anyway.
Re:Lock-free multithreading with atomic operations
by amelius on Tuesday July 30, 2019 @08:07AM
(#20564058)
True, but some atomic instructions may need to access main memory to complete their operation. Whether shortcuts can be taken in most cases is not relevant for worst-case considerations.
Re:Lock-free multithreading with atomic operations
by bonzini on Tuesday July 30, 2019 @10:43AM
(#20565233)
They may need to access main memory, but the RMW operation don't happen over the memory bus. The processor appropriates the cache line just like any other memory access, and then operates atomically on the cache line.
Re:Lock-free multithreading with atomic operations
by amelius on Tuesday July 30, 2019 @01:03PM
(#20566804)
And what if the cache line is full/dirty?
Re:Lock-free multithreading with atomic operations
by bonzini on Tuesday July 30, 2019 @02:20PM
(#20567629)
The cache coherency protocol takes care of that. In other words the first part is just a memory load and can vary from 0 to a few hundred clock cycles, the second is local to the processor and has a more or less fixed cost. The worst-case execution time is completely dominated by the first part, the best case instead is dominated by the second.
Re:Lock-free multithreading with atomic operations
by jasonwatkinspdx on Tuesday July 30, 2019 @03:47PM
(#20568431)
I'd suggest reading the wiki articles about it for an introduction, and Ch 5 of https://www.amazon.com/Computer-Architecture-Quantitative-Jo... for a detailed understanding.
Right now you're asserting things about all this, while not being familiar with relatively basic aspects of how it works.
Re:Lock-free multithreading with atomic operations
by gpderetta on Tuesday July 30, 2019 @08:59AM
(#20564373)
Sure any memory access might access main memory. There is no special casing for atomic though.
Re:Lock-free multithreading with atomic operations
by kccqzy on Tuesday July 30, 2019 @03:35AM
(#20562816)
It is different. The lock prefix in x86 is only relevant in a multiprocessing (i.e. parallel) environment. But the general concept of locking is applicable to concurrent environments as well. For example when there are multiple processes on a uniprocessor machine, you still need to use locks (mutexes) which are implemented using, say, cmpxchg8b (atomically compare and exchange eight bytes), but in the absence of a second processor there's no need to use the lock prefix. Here on a machine level there's never really on any locking, but on an application level you are using locks.
Re:Lock-free multithreading with atomic operations
by gpderetta on Tuesday July 30, 2019 @07:44AM
(#20563922)
The only resource that is held exclusively during an RMW is a single cache line, and that's not due to the lock prefix.
Re:Lock-free multithreading with atomic operations
by fulafel on Tuesday July 30, 2019 @10:03AM
(#20564925)
X86 use MESI derivative directory-based cache coherency protocols on the cache line level (when synchronizing across sockets), bus-locking was probably in the 486/Pentium 1 days when bus snooping was used.
Re:Lock-free multithreading with atomic operations
by gpderetta on Tuesday July 30, 2019 @07:08AM
(#20563710)
Outside of some very exotic scenarios, this hasn't been the case for about 20 years.
Re:Lock-free multithreading with atomic operations
by zlynx on Tuesday July 30, 2019 @12:40PM
(#20566551)
I read about one recently where an evil user program was able to bring a 28 core Xeon to its knees. Apparently a LOCK INC on an unaligned value that hangs over a page boundary forces this super-advanced CPU to lock everything in every cache as if it was a 386.