If I use locks, can my algorithm still be lock-free?
- by Joe Pension
A common definition of lock-free is that at least one process makes progress. 1
If I have a simple data structure such as a queue, protected by a lock, then one process can always make progress, as one process can acquire the lock, do what it wants, and release it.
So does it meet the definition of lock-free?
1 See eg M. Herlihy, V. Luchangco, and M. Moir. Obstruction-free synchronization: Double-ended queues as an example. In Distributed Computing, 2003. "It is lock-free if it ensures only that some thread always makes progress".