Hacker News Reader

Comment by samsquire | Hacker News Reader

I like the code of this ringbuffer

https://www.linuxjournal.com/content/lock-free-multi-produce...

I liked this whitepaper https://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf

I am a beginner at this kind of thing but I created an array of integers that each thread owns an index. They write to the array at their index that they want access to the critical section.

We scan the array forwards and backwards to see if there is any thread that has claim to the critical section.

I even TRIED to write a model checker https://github.com/samsquire/multithreaded-model-checker

This is inspired by left-right concurrency control whitepaper Left-Right: A Concurrency Control Technique with Wait-Free Population Oblivious Reads

View on HN

The article in the first link is pretty bad, and the entire code is undefined behavior. First of all, using inline asm + volatile to emulate well-ordered release & acquire on x86 is unnecessary. That's exactly what atomics are supposed to provide for you.

> In this article, I concentrate on x86, as it is the most widespread architecture rather than write generic (but slower) code.

Any reasonable C++ compiler will generate simple loads and stores for atomic r&a. There's no penalty for writing generic code.

I too am a beginner with concurrent programming—it's a difficult topic to get your head around at first. Some resources that I've found super helpful:

- Dmitry Vyukov's Lockless Algorithms: https://www.1024cores.net/home/lock-free-algorithms

- Jeff Preshing's blog (worth exploring all adjacent articles): https://preshing.com/20120612/an-introduction-to-lock-free-p...

- Bartosz Milewski: https://bartoszmilewski.com/2008/12/01/c-atomics-and-memory-...

- Memory Barriers: a Hardware View for Software Hackers—P.McKenney: https://www.researchgate.net/publication/228824849_Memory_Ba...

I hope you find some of these useful. I've re-read Paul McKenney's paper every 2-3 months in an attempt to get this stuff to stick! :)

The Art of Multiprocessor Programming is really good

Thanks for linking all these references!

I’m also new to a lot of these topics but recently read Rust Atomics and Locks which has helped my understanding quite a bit - at least keeping me above water reading all the discussion in this post. The examples are in Rust but the concepts are at the kernel/cpu level and apply beyond the language. I recommend it.

https://marabos.nl/atomics/

Ringbuffers are one of my favorite things to use. Thanks for the article.

Reply on news.ycombinator.com