Making algorithms lock-free with Read-Copy Update (RCU)
the-paper-trail.org
the-paper-trail.org
Also I find the following troubling:
"[in the kernel] Even a concurrency scheme that nominally used spinlocks to protect critical sections would be lock-free, because every thread would exit their critical section in bounded time"
This ignores the possibility of deadlocks and livelocks. Also the lock-free definition requires that the system makes progress if other threads are halted; you can't just handwave the requirement away by claiming that your threads never halt; and even in practice you can't guarantee that a buggy NMI handler won't takes over the cpu effectively halting any thread.
edit: are never not halted -> never halt
"rcu_read_lock" doesn't ever block (as in wait for a spinlock), right? Sometimes you just need readers to never block and can pay higher price for other operations.
> So as soon as a thread yields its CPU, it’s guaranteed to be out of its critical section.
Therefore, the yielding can be seen as a blocking operation, meaning that readers do in fact block!
Unless you are in a critical section (in which your thread has exclusive control of the CPU). So the blocking may start again at the end of the section.
I hope this makes it clear.
There's a boot parameter that will let you black list CPUs on which to not schedule anything (by default). Then you use tasksel to schedule your process there as well. Finally, you can configure IRQ affinity so also doesn't handle interrupts on that core. It's not a 100% non pre-emptive but pretty close.
I believe there was work being to enable it to be even more accurately 100 but I haven't followed along.
Thread halting is a not problem as long as it resumes to complete the critical section. Interrupt can happen. The interrupt state is saved to be handled later, the thread resumes to finish the critical section, and then the saved interrupt is delivered to the interrupt handler. The scheduler is interrupt driven anyway.
Thread killed while inside a critical section can be a real problem, as the critical section is not released, preventing other threads from running on the processor. I'm not sure how Linux handles it, whether it would clean up the critical section when the thread is killed or the killing waits until the critical section has finished.
[1] https://en.wikipedia.org/wiki/Critical_section#Kernel-level_...
"Thread halting is a not problem as long as it resumes"
the whole point of a non blocking algorithm is that it gives guarantees if a thread doesn't resume for whatever reason.
(edit: s/per-thread/system-wide, since we're talking about lock-freedom).
Anyway, even controlling preemption and disabling interrupts very much does not make a spinlocked critical section a lock free algorithm. That's not just a theoretical issue. We are dealing right now with a couple of machines where periodically the kflush kernel thread livelocks hard preventing the rest of the system from ever writing a page to disk requiring a hard powercycle.
If you have an algorithm which might deadlock, 'progress' isn't really well defined.
edit: ah, and you might be running under a virtualized cpu and the host takes the cpu away from you.
Edit: another one: SMM mode kicks in and takes the CPU away from the OS.
Paul McKenney is going to be presenting. He is one of the inventors of RCU, the author of Linux's RCU code. He's going to be presenting about RCU and write rates.
I'm really curious to hear that talk so that's the primary reason I'm going. But there's going to be other great systems / application talks.
However, it is true that most ACM conferences do not record talks. That, however, is probably just because recording talks is expensive, and the conference organizers don't want to spend their budget on it.
The degenerate case of this is cooperative scheduling, which is painful in about the same way that manual memory management is painful. But the hybrid case, reduction scheduling ala Erlang, gets a lot of the same advantages (nothing pre-empting a function in the middle of a loop body) without the ability to forget to add yields (they happen at tail-call sites—which, for a language where tail-recursion is the only loop primitive, means your code will always have an O(1) runtime before a yield.)
I wonder how long it will take until academical papers are published with clickbait titles.
Seriously. It's the exact opposite of an abstract, which is to give a quick TL;DR summary so you can know if it's worth your time reading more about the paper.
Startup idea?
Having said that, even if most papers were vastly simplified I doubt that many topics could be lowered to ELI5.
It was not well received, so it worked as expected?
1. A misplaced comma adds substantial confusion: "during a critical section, a thread may not block, or be pre-empted by the scheduler." This sounds like the thread may not block OR if it's blocked, the scheduler would preempt it, which doesn't make sense in regarding to the readers using the critical section. It should read: "during a critical section, a thread may not block and it would NOT be preempted by the scheduler." That just means a thread in a critical section is guaranteed to run to the end of the critical section without worrying about other threads preempting it. It owns the processor until the end of the critical section.
Then it makes sense. When the readers exit the critical section, they have done dealing with the old shared data. The writer's scheduled thread won't preempt the reader threads in critical section, and when it runs, it means the readers have finished.
2. Critical section is a form of lock. I don't see how it can be claimed lock-free. May be it should say critical section help avoid inter-processor locking.
https://github.com/opensource-apple/objc4/blob/master/runtim...
Basically, issue a syscall that acquires the PC of all threads. When none of the PCs are in the critical section, then you can garbage collect old objects.
#define PC_SENTINEL 1
unsigned int count = x86_THREAD_STATE64_COUNT;
kern_return_t okay = thread_get_state (thread, x86_THREAD_STATE64, (thread_state_t)&state, &count);
return (okay == KERN_SUCCESS) ? state.__rip : PC_SENTINEL;
If you have a lot of threads running, this could get really expensive. I presume it works, but this doesn't seem like an efficient approach unless your "writes" are extremely rare relative to the number reads and number of threads.
I haven't been able to find source for thread_get_state(), though. I don't think there is any way to get the current PC from a core without an interrupt? I presume it at least reads the PC for sleeping threads without needing to wake them?
There was talk at some point of adding a single syscall that got all the PCs of all the threads at once to cut down on the overhead, but it looks like that still hasn't happened.
What's going on here is something like this:
1. objc_msgSend is Obj-C's method dispatcher, and it depends on method caches to make method lookup faster.
2. Sometimes the method caches become out of date. For instance, maybe the method cache filled up and the Obj-C runtime needs to allocate a larger method cache.
3. This old method cache has to be GC'd at some point, so it's added to a freelist.
4. This GC function (the "write" you're talking about) for these caches runs once the size of outdated method caches grows beyond a certain threshold (garbage_threshold in the code). So it shouldn't run too often. The GC function works by checking if any thread is currently within objc_msgSend. If no function is in objc_msgSend, then the runtime is sure that none of the method caches on the free list is in use.
5. It is definitely optimized for reads. The "read" in this case is literally a method dispatch so it happens all the time, and it's important for the read to be lock-free.
Most of the web is a mess. Let's not make this corner like that stuff over there.
At least for now we can recognize/detect that our psyches are being preyed upon (soon we will not, as the art of clickbait evolves and starts using machines)...
It's a sad world we live in.
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.
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 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.
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.)
So nice to read about techniques that can be implemented in kernel space. Inability to do a context switches often works against you there [1].
[1]: Many usermode waiting based constructs cannot be used, because they require yielding or pre-emption. You can't yield if you can't schedule (or block).
The stronger guarantee you're expecting is probably "wait free"
There's other similar methods RCU like hazard pointers. There was a patent application filed, but it was abandoned before it was granted.
It's when you are sitting, optimizing some bulk throughput rate in a router firmware, generally minding your own business and then a guy pops in and says that he just sped things up by a factor of 10. You get up, follow him to his cubicle and, lo and behold, it is 10x faster when blasted with a SmartBit stream. Ask him how he managed to achieve such a remarkable feat and he says - I just profiled the code, found a bottleneck and worked around it:
// some_random_mutex.lock();
...
// some_random_mutex.unlock();
Edit: to clarify - the lock was there for a reason. The whole thing whoopsed in an instant outside that specific test.