>The general pattern is that you can prepare an update to a data structure, and then use a machine primitive to atomically install the update by changing a pointer.
Interesting. Analogous to the "two phase" commit used by Oracle, as opposed to the global lock used by SQL server.
(sorry if tpc is ubiquitous now, or SQLs doesn't use the locking any more - haven't worked with these in a while)
This is "lock free" certainly - but it still requires atomic updates, which is another concurrency primitive. Sorry not an expert but doesn't this still require some kind of locking under the hood? More efficient than explicit locking certainly but locking nonetheless.
EDIT I just re-read - so he's proposing that rather than locking you just prevent a thread from being context-switched by the scheduler. So you're kind of stepping back from definitive preemptive multitasking and introducing a cooperative element.
So you can't really make "any" algorithm lock-free - only where the scheduler lets you put it on hold, and where your code has the execution privileges to do that.
I think he's speaking specifically about Linux system code, but you have to delve into the details of TFA before that becomes apparent.
It seems fairly obvious then that if you have a more cooperative multitasking model then locking isn't really as necessary.
> Interesting. Analogous to the "two phase" commit used by Oracle, as opposed to the global lock used by SQL server.
I don't think 2PC is the right analogy here (which is really about distributed commit). But if you want to go use a database analogy MVCC. For example in LMDB there's many reads and one writer, the write finishes by updating swapping the root page and all future readers can see updates via that root page (analogous to the pointer with new version).
In fact the way LMDB is implemented is essentially RCU with a reader table and GCing of old pages once the oldest reader with access to that page goes away.
Yes, the author is talking about (Linux) kernel space where you have a lot more control over the environment so it's "easier" to use / build various concurrency primitives. Simple example: it's possible in the kernel to be in a spinlock loop with interrupts disabled and the holder will not be pre-empted. You can't make guarantees like that in user space.
The problem with RCU is that the name is extremely misleading.
The name Read-Copy-Update describes the general way to concurrently update a shared data structure: make a local copy of the parts subject to change, modify the local copy then atomically substitute the original with the updated copy.
This is absolutely not exclusive of the RCU algorithm and in fact is pretty much how any lock free update of a data structure looks like (and even not lock free, see persistent data structures or MVCC).
A problem that lock free algorithms have is that they need a way to dispose of the now stale original node, which might be concurrently being accessed by other readers. There are many way to handle the disposal: for example hazard pointers, pass-the-buck, and full GC (this includes shared pointers).
RCU is one of these disposal algorithms and it uses epoch detection plus the contract that an accessor thread won't hold a reference across an epoch. Implementations of RCU can be very efficient for read mostly data structures because, on the reader side do not need expensive memory barriers (contrast with the store-load required to for hazard pointer updates even on the read side): a dependent load (the infamous load_consume) is enough.
> EDIT I just re-read - so he's proposing that rather than locking you just prevent a thread from being context-switched by the scheduler.
There are multiple implementations of RCU. One of them (the earliest) uses this mechanism. However, Linux also has a fully preemptible implementation of RCU, in which readers do not prevent context switch at all; that implementation tracks grace periods differently, without relying on context switch. (But still without making rcu_read_lock/rcu_read_unlock expensive.)
Interesting. Analogous to the "two phase" commit used by Oracle, as opposed to the global lock used by SQL server.
(sorry if tpc is ubiquitous now, or SQLs doesn't use the locking any more - haven't worked with these in a while)
This is "lock free" certainly - but it still requires atomic updates, which is another concurrency primitive. Sorry not an expert but doesn't this still require some kind of locking under the hood? More efficient than explicit locking certainly but locking nonetheless.
EDIT I just re-read - so he's proposing that rather than locking you just prevent a thread from being context-switched by the scheduler. So you're kind of stepping back from definitive preemptive multitasking and introducing a cooperative element.
So you can't really make "any" algorithm lock-free - only where the scheduler lets you put it on hold, and where your code has the execution privileges to do that.
I think he's speaking specifically about Linux system code, but you have to delve into the details of TFA before that becomes apparent.
It seems fairly obvious then that if you have a more cooperative multitasking model then locking isn't really as necessary.