Is the following algorithm lock-free?
In my understanding, an algorithm is lock free if some thread always makes progress.
Now isn't this condition met by the following example (using locks):
Thread 1: using lock1 for critical section
Thread 2: using lock1 for critical section
Thread 3: some call independent of lock1 and the other two threads in general
What you describe certainly isn't "lock-free" in any meaningful sense. Thread 1 and 2 are dependent on the same shared resource (a critical section, enforced by "lock1"), so if one of them acquires that lock and then gets suspended, then the other thread will deadlock waiting on it.
Sure, Thread 3 will continue on unabated, but so will Thread A, B, and C (i.e., threads that have nothing to do with your program). That seems to be irrelevant when looking at the algorithm as a whole, which presumably consists of all three threads.
Essentially, the problem with your definition of "lock-free" is that it isn't precise enough. You say that an algorithm is lock-free "if some thread always makes progress", but you fail to look at the algorithm as a whole.
Thread 3 is trivially lock-free (because it makes progress on its own, without the assistance of any other threads), but your overall algorithm is not.
A better way to assess whether an algorithm is lock-free is asking yourself: if a single thread gets suspended, will this prevent the other threads from making progress as a group? In this case, yes. If Thread 1 or Thread 2 acquires the lock and then gets suspended, this will prevent the other thread from executing, and presumably these other threads are doing work that is important to your algorithm.
I recommend Jeff Preshing's blog post, "An Introduction to Lock-Free Programming". Here's a handy flow chart from that blog post:
