The basic differentiator is that a locking algorithm or locking code has the potential to execute but not making progress. Lock-free code is always guaranteed t

The basic differentiator is that a locking algorithm or locking code has the potential to execute but not making progress. Lock-free code is always guaranteed to make progress if it runs. The queue implementation that blocks on an empty queue is fine if inserting into the queue is still lock-free, ie, your insert operation eventually completes or makes progress regardless of if a reader is spinning on the lock that allows you to pop a value from the queue. That means, while the popping of a value is locking, inserting is not. Hence the mutex locking the read does not turn the queue into a locking algorithm.