An Introduction to Lockless Algorithms
One point that's frequently misunderstood about locks is that there's essentially no cost unless the lock is contested. This leads a lot of people to they must go lockless, when a simpler lock-based system would meet their requirements.<p>A lot of systems fit neatly into a paradigm of a single threaded hot path, plus a lot of infrequent peripheral threads that only have a low statistical contention cost.<p>For example let's say you want to process packets off the network very fast. But you also need some constant bounded garbage cleanup thread running periodically in the background. Maybe the thread runs every 30 seconds and takes 30 milliseconds per cycle. A lock won't have any effect on a 99th percentile SLA, because only 0.1% of inbound packets will experience contention.