3 ms·
> And by the way if you know more methods or ideas please share them! Use a transaction manager (HTM or STM). The STM is going to boil down to lockfree synchro
by titzer 1y ago
> And by the way if you know more methods or ideas please share them!
Use a transaction manager (HTM or STM). The STM is going to boil down to lockfree synchronization, logging, and retry. Transactions can fail and retry.
But ultimately, all inter-thread communication boils down to programs (or libraries) using barriers for acquire/release semantics and/or using compare/swap and atomic read-modify-write.
> at any point of time there can be either one writer or multiple readers
Time is a slippery notion in concurrency. Most language-level memory models (e.g. Java) or even hardware-level concurrency models focus on happens-before relations, which are induced by executing certain operations. At the hardware level, you can basically think that a CPU receives asynchronous updates about cache lines from other processors (potentially out of order). While technically the cache coherence protocol pushes cache lines into processors, you can't ever guarantee that one "writer" can "push" updates into all other CPUs. Instead, you have to rely on those other CPUs executing either fences or being forced to execute fences through global OS means, such as IPIs. Those other CPUs executing fences (barriers) or other atomic operations induce happens-before relations.
- codedokode 1y ago> Time is a slippery notion in concurrency. Most language-level memory models (e.g. Java) or even hardware-level concurrency models focus on happens-before relations, which are induced by executing certain operations You are correct, but for simplicity we can assume that the CPU executes one operation at a time and still have a valid model for reasoning about data races. > But ultimately, all inter-thread communication boils down to programs (or libraries) using barriers for acquire/release semantics and/or using compare/swap and atomic read-modify-write. Interesting. I read about STM and it reminded me of "modification box" algorithm for modifying immutable trees, which also uses versions. So it is another clever but complicated trick. Also it seems that it requires locking? That's not very good given that locks often need syscalls.
- titzer 1y ago> Also it seems that it requires locking? That's not very good given that locks often need syscalls. AFAIU in most STMs all the fast paths are implemented using lock-free algorithms with just barriers.
- codedokode 1y agoHow do you implement "commit" part safely (writing changes to the object) without locking the object?
- titzer 1y agoOne way is that the writer thread prepares a completely new copy of the object in a private area and then either compare-and-swaps a pointer to it, or executes a store with a store-store barrier (depending on details of the STM system around it).
- codedokode 1y agoInteresting, it's almost like immutable data structures.
- mrkeen 1y ago> Also it seems that it requires locking? STM requires locking in the same way that GC requires malloc. It gets it right so that the programmer doesn't mess it up.
- astrange 1y agoA non-compacting GC still needs a good malloc because it needs to avoid heap fragmentation.