An Introduction to Lockless Algorithms

• multithreaded-model-checker

  1 0 10.0 Python

  a model checker for my multithreaded algorithm

https://github.com/samsquire/multithreaded-model-checker

This is inspired by left-right concurrency control whitepaper

• loom

  14 1,891 6.8 Rust

  Concurrency permutation testing tool for Rust. (by tokio-rs)

  

> Mutexes are very cheap in the uncontended case

It was a while ago I was deep into this mess so forgive any ignorance–but–iirc the thread-mutex dogma[1] has many pitfalls despite being so widely used. Primarily they’re easy to misuse (deadlocks, holding a lock across a suspend point), and have unpredictable performance because they span so far into compiler, OS and CPU territory (instruction reordering, cache line invalidation, mode switches etc). Also on Arm it’s unclear if mutices are as cheap because of the relaxed memory order(?). Finally code with mutices are hard to test exhaustively, and are prone to heisenbugs.

Now, many if not most of the above apply to anything with atomics, so lock-free/wait-free won’t help either. There’s a reason why a lot of concurrency is ~phd level on the theoretical side, as well as deeply coupled with the gritty realities of hardware/compilers/os on the engineering side.

That said, I still think there’s room for a slightly expanded concurrency toolbox for mortals. For instance, a well implemented concurrent queue can be a significant improvement for many workflows, perhaps even with native OS support (io_uring style)?. Another exciting example is concurrency permutation test frameworks[2] for atomics that reorder operations in order to synthetically trigger rare logical race conditions. I’ve also personally had great experience with the Golang race detector. I hope we see some convergence on some of this stuff within a few years. Concurrency is still incredibly hard to get right.

[1]: I say this only because CS degrees has preached mutices to as the silver bullet for decades.

[2]: https://github.com/tokio-rs/loom

• InfluxDB

  www.influxdata.com sponsored

  Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.

  

• ctp

  1 4 4.4 C

  C Thread Primitives

  

You're too focused on "mutex". There are many more interesting constructs that one can build in a lockless manner: lists, hash tables, RCU, etc.

Here's some of mine: https://github.com/cryptonector/ctp/

Suggest a related project