Hacker News Reader

Comment by ajamesm | Hacker News Reader

  In this post, I will summarize my understanding of a non-blocking (lock free) design of linked list data structure...

The author conflates blocking with lock-free. Starvation is a form of blocking, non-blocking implies no starvation.

View on HN

It isn't a form of blocking, and it doesn't imply that, in the conventional/widespread definitions of these terms: "Lock-freedom allows individual threads to starve but guarantees system-wide throughput" https://en.wikipedia.org/wiki/Non-blocking_algorithm#Lock-fr... . The subclassification of non-blocking that avoids starvation is wait-free ("Wait-freedom is the strongest non-blocking guarantee of progress, combining guaranteed system-wide throughput with starvation-freedom", from the Wikipedia article above).

In that case, I guess we're just drawing from different glossaries. I've always heard "blocked" used to mean "can't execute because of something other threads are doing" regardless of whether that's starvation or getting slept by a mutex.

I don't think that's a definition that makes sense - consider Thread.sleep(Integer.MAX_VALUE). I think we would all agree that the thread is blocked, but not on the progress of other threads.

Reply on news.ycombinator.com