12

In some articles about algorithm, some use the word lockfree, and some use lockless. What's the difference between lockless and lockfree? Thanks!

Update

http://www.intel.com/content/dam/www/public/us/en/documents/guides/intel-dpdk-programmers-guide.pdf

section 5.2 --"Lockless Ring Buffer in Linux*", it's a example of use word "lockless"

superK
  • 3,932
  • 6
  • 30
  • 54
  • 1
    From the contents of those articles - do you assume there's a difference? I only know "lock-free", but wouldn't think "lockless" describes something other (see "non-blocking" as well). – JeffRSon Dec 09 '13 at 09:35
  • 1
    Without a link to these articles, I think we'd just be guessing. They may be meaning exactly the same thing, or there may be some subtle nuance that they're attempting to highlight, but I'd usually assume them to be synonyms. – Damien_The_Unbeliever Dec 09 '13 at 09:37
  • @Damien_The_Unbeliever http://www.intel.com/content/dam/www/public/us/en/documents/guides/intel-dpdk-programmers-guide.pdf section 5.2--"Lockless Ring Buffer in Linux*" It's a example of use word "lockless". – superK Dec 09 '13 at 09:59

2 Answers2

11

An algorithm is lock-free if it satisfies that when the program threads are run sufficiently long at least one of the threads makes progress (for some sensible definition of progress). All wait-free algorithms are lock-free.

In general, a lock-free algorithm can run in four phases: completing one's own operation, assisting an obstructing operation, aborting an obstructing operation, and waiting. Completing one's own operation is complicated by the possibility of concurrent assistance and abortion, but is invariably the fastest path to completion. e.g. Non blocking algorithms

Lockless programming, is a set of techniques for safely manipulating shared data without using locks. There are lockless algorithms available for passing messages, sharing lists and queues of data, and other tasks. Lockless programming is pretty complicated. e.g. All purely functional data structures are inherently lock-free, since they are immutable

aryann
  • 909
  • 5
  • 11
  • I still don't know the difference between them, but this is the best current answer. So give you the coin. – superK Dec 10 '13 at 01:28
  • You should cite the source of information when your writing is not original material. Your post seems to be copied from https://en.wikipedia.org/wiki/Non-blocking_algorithm – Maxim Egorushkin Aug 10 '23 at 10:19
4

Lock-free is a more formal thing (look for lock-free algorithms). The essence of it for data structures is that if two threads/processes access the data structure and one of them dies, the other one is still guaranteed to complete the operation.

Lockless is about implementation - it means the algorithm does not use locks (or using the more formal name - mutual exclusion).

Therefore a lock-free algorithm is also lockless (because if one thread locks and then dies the other one would wait forever) but not the other way around - there are algorithms which don't use locks (e.g. they use compare-and-swap) but still can hang if the other process dies. The dpdk ring buffer mentioned above is an example of lockless which is not lock-free.

Uri Simchoni
  • 56
  • 1
  • 1
    https://en.wikipedia.org/wiki/Non-blocking_algorithm defines wait-free, lock-free, and obstruction-free, and yes those are much stronger requirements than just not using any traditional locks. For example, see an analysis (https://stackoverflow.com/questions/45907210/lock-free-progress-guarantees) of a lockless queue which is very efficient with minimal contention between threads, but will get stuck if a thread sleeps at just the wrong time. – Peter Cordes Sep 20 '17 at 07:05