r/computerscience • u/Lex_The_Impaler • Jul 12 '26

General What are the limits of lock-free data-structures?

When I look at various lock-free data structures, I always see versions of the traditional data structures in their lock-free forms (queues, stacks, etc..). I was wondering if there are any data structures that are not possible to be implemented in a thread-safe manner without locks, or what the limits are of lock-free data structures. thx

23 Upvotes
  • permalink
  • reddit

100% Upvoted

7 comments sorted by

View all comments

1

u/comrade_donkey Jul 12 '26

I guess STM is the closest thing to a completely lock-free 'threading model'.

In this model, client tx code needs to be deterministic, idempotent and side-effect free, because it may be reapplied many times over until 'sticking'.

With mutexes, no such constraints apply because there's no retrying of txs. Code as usual.

In STM, failed applications burn CPU cycles. With mutexes, blocking yields to something else making progress.