If this type hashtable cound be defined lock-free?

Question

In my understanding

block is there are =1 task could progress if there are N tasks concurrent running 
and one enter the critical area(enter the critical area one).

lock-free is there are >=1 tasks could progress if there are N tasks concurrent 
running and one enter the critical area.

wait-free is there are N tasks could progress if there are N tasks concurrent 
running and one enter the critical area(maybe it shouldn't be called `critical area`).

My questions is:

If a hash table have N buckets, and each one has a lock, in any time, there should be >=1 tasks could in progress. Is this type hash table could be defined lock-free?

bucket
+-------------+      +-------+      +-------+
| head | lock | ---> | entry | ---> | entry | ---> ...
+-------------+      +-------+      +-------+

Answer 1

If a hash table have N buckets, and each one has a lock, in any time, there should be >=1 tasks could in progress. Is this type hash table could be defined lock-free?

No. "each one has a lock" implies potential blocking. As a test for "lock free", consider whether a suspended thread could prevent another thread from making progress for the entire time it's suspended. If so, then it's not a lock free situation.

In lock free programming you use something like an atomic operation - often with a spin on update failure - such that a thread attempting to make progress may have to retry but each time there's a new race condition to see whether they progress; they're in with a genuine chance.

Spin locks

(I put some details in comments, but that was getting clumsy.)

"Spin lock" means different things to different people.

Historically, some people called a mutex or read-write lock a spin lock if it at least span a few (hundred/thousand) times trying to atomically acquire the lock before joining an OS queue for that lock (so it won't keep burning CPU if the thread holding the lock runs for a long time).

Microsoft at http://msdn.microsoft.com/en-us/library/ms894034.aspx use it in a different way:

Only the thread holding the spin lock can use the resource and only until the lock is released. The spin lock prevents other threads from accessing the resource. While waiting for the spin lock to release, another thread can initiate a loop that attempts to acquire the spin lock and continues looping until the thread that holds the lock releases the spin lock.

So, in that context they deem a spin lock to be akin to the usage I describe above, but have no provision for falling back on an event-driven queue to avoid burning CPU time.

Lock-free atomic operations tend to be spinning too - the difference is that they've completed their work when the spinning stops, rather than having shut out competing threads to allow them to begin the work (and having those competing threads blocked from progress even if the locking thread gets suspended or delayed in some way).

Answer 2

My understanding of lock free is:

There are multiple task that are running concurrency, and each of them can access shared data without any of them potentially blocking the progress of the others. Consequently, if you suspend a single thread it will never prevent other threads from making progress.

So (I think) if you use any lock your code isn't lock free. You actually use the lock precisely because multiple threads may attempt concurrent access to the shared data, so this single lock may be contested and serialise access; clearly this potential means your code is not lock-free. The lock you use in your buckets might be a mutex (with the OS managing a queue and providing event notification when the lock is acquired) or a busy loop (where the CPU spins in application space trying to atomically acquire the lock exclusively), but neither is lock free.

Using some technique for back-off is lock free if that satisfy this: Also if you suspend a single thread, it will never prevent other threads from making progress..

In your hash table more than one thread can make progress, but despite that threads can block each other when operating on elements in the same bucket. In the bucket's linked list you could use fine grained locks - letting more that one thread work with elements in the list - but even this isn't truly lock free.

Edit

Different between lock free and wait free(definitions from C++ Concurrency in action book):

Lock-Free: For a data structure to qualify as lock-free, more than one thread must be able to access the data structure concurrently. They don’t have to be able to do the same operations; a lock-free queue might allow one thread to push and one to pop but break if two threads try to push new items at the same time. Not only that, but if one of the threads accessing the data structure is suspended by the scheduler midway through its operation, the other threads must still be able to complete their operations without waiting for the suspended thread.

Algorithms that use compare/exchange operations on the data structure often have loops in them.Lock-free algorithms with such loops can result in one thread being subject to starvation. If another thread performs operations with the “wrong” timing, the other thread might make progress while the first thread continually has to retry its operation. Data structures that avoid this problem are wait-free as well as lock-free.

Wait free:A wait-free data structure is a lock-free data structure with the additional property that every thread accessing the data structure can complete its operation within a bounded number of steps. Algorithms that can involve an unbounded number of retries because of clashes with other threads are thus not wait-free.

With this definitions, i think that my description is like to lock free ;). But for your hash map, my vote is lock based code. Also in that book, author has implemented such hash table and insert that in lock-based data structures section of his book