I've studied The Art of Multiprocessor Programming1 and their text is lacking in clarity, just like the book you refer to. Here are some quotes from TAMPP:
Quote 1 (Definition of lock-free)
A method is lock-free if it guarantees that infinitely often some method call finishes in a finite number of steps.
Quote 2 (Definition of nonblocking)
a pending invocation of a total method is never required to wait for another pending invocation to complete.
Quote 3 (claim that lock-free is nonblocking)
The wait-free and lock-free nonblocking progress conditions guarantee that the computation as a whole makes progress, independently of how the system schedules threads.
The problem is that the claim in Quote 3 does not obviously follow from the definition in Quote 1. As already mentioned, a synchronized queue seems to satisfy Quote 1: infinitely often some method will successfully acquire the lock and complete.
Note specifically the quite vague phrase in Quote 3: "independently of how the system schedules threads". This is not preceded by any kind of a formal description of the "thread-scheduling system", so we are left to reconstruct its properties based on our preconceptions on what the definitions should mean:
- the system always executes instructions of some thread;
- it may never execute instructions of any given thread;
- all the threads are invoking the method under consideration.
On such a system, a blocking method cannot be lock-free: if the thread holding the lock is never again scheduled for execution, there will be no other thread which can complete its method invocation in a finite number of steps, yet there will be some threads that are executing steps of the method. For a more realistic system, one which does guarantee to give CPU time to each thread eventually, the definition must explicitly include the nonblocking property:
Corrected definition of lock-free
A method is lock-free if it is non-blocking and, additionally, guarantees that infinitely often some method call finishes in a finite number of steps.
1 Maurice Herlihy, Nir Shavit, The Art of Multiprocessor Programming, Elsevier 2008, pp. 58-60