▲ | codedokode 4 days ago | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
The general rule to prevent any data races (as I guess) between threads is that at any point of time there can be either one writer or multiple readers to the same object. Rust guarantees this by not allowing to have any other references if you have a read-write (mutable) reference. Note that Rust is more strict than necessary - theoretically you can have multiple writable and readable references, but not use them simultaneously and observe the rule. But it is difficult (or even impossible) to verify during compilation so Rust doesn't allow it. C allows it but leaves verification to the author which doesn't work well and doesn't scale. This situation can happen if you have a graph of objects. For example, in an OS you might have a Process object having references to a list of opened Files, and have a File hold reference back to Process that opened it. In this case you cannot ever have a writable reference to the Process from anywhere because Files already have multiple reading references. And Files can have only read-only references to the Process that opened them. So you have to use only read-only references and additional structures like Cell, Arc etc. that allow safe writing through them. They are cheap, but not free and ideally we as developers want to have memory safety for free. That's the problem yet to solve. Note that there are other ways to achieve safety: - use C and manually verify that your program never breaks this rule - requires god level coding skills - immutable data - after the writer finished writing, data are "frozen" and can be safely shared without any checks and no rules are broken. Very good, but modification is expensive and requires you to clone the data or use clever and complicated design (for example, if you have 10-elements array but shared a reference only to first 7 elements, you can safely append to the last 3 elements because nobody else knows about them - that's how ring buffers work). See immer C++ library for example. - atomic variables - allow safe reading and writing at the same time, but can hold at most 8 bytes. Note that using a same variable from different CPU cores causes L1 cache line migrations which, last time I measured it, takes about 2-3 ns or ~10-15 cycles. - mutexes - ensure rule is observed but make everyone wait. Python's approach. - using only a single thread. JavaScript's approach. You can have multiple references but you still need to ensure they are pointing to a live object (JS solves this by using an expensive garbage collector). And by the way if you know more methods or ideas please share them! | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
▲ | titzer 4 days ago | parent [-] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
> 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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|