example of how a lock-free algorithm could still have starvation: In the lock free stack a few slides in the future, it is possible that there are many threads trying to push onto the stack, and it could be the case that one of the threads never wins the race to copy and swap the values, which is starvation.
sadkins
At first I was confused about this concept, because it seems that even in a program with locks, the thread that has the lock is making progress so there is always systemwide progress. However, if that thread crashes for some reason before unlocking then no systemwide progress is made, therefore we can't guarantee it like we can for lock-free programming. The key difference is that in lock-free programming a thread can't block another thread from doing something
200
For the lock-free stack, critical section lengths for push and pop are almost same. But what if there is a operation has much longer critical section length than others, would lock-free approach cause starvation for the longer operation?
asd
@200 You would still have to roll back all the work that you did in the critical section. In fact, the work that you do would even be more in that case than you would've had to perform if your critical section had been small. I guess!
jedi
@crow, isn't the motivation for using a lock-free implementation that one of the threads in the stack example is guaranteed to win the race and succeed in the CAS operation?
crow
yes, one of the threads is always guaranteed to win the race. that doesn't mean that every thread is guaranteed to win at some point
example of how a lock-free algorithm could still have starvation: In the lock free stack a few slides in the future, it is possible that there are many threads trying to push onto the stack, and it could be the case that one of the threads never wins the race to copy and swap the values, which is starvation.
At first I was confused about this concept, because it seems that even in a program with locks, the thread that has the lock is making progress so there is always systemwide progress. However, if that thread crashes for some reason before unlocking then no systemwide progress is made, therefore we can't guarantee it like we can for lock-free programming. The key difference is that in lock-free programming a thread can't block another thread from doing something
For the lock-free stack, critical section lengths for push and pop are almost same. But what if there is a operation has much longer critical section length than others, would lock-free approach cause starvation for the longer operation?
@200 You would still have to roll back all the work that you did in the critical section. In fact, the work that you do would even be more in that case than you would've had to perform if your critical section had been small. I guess!
@crow, isn't the motivation for using a lock-free implementation that one of the threads in the stack example is guaranteed to win the race and succeed in the CAS operation?
yes, one of the threads is always guaranteed to win the race. that doesn't mean that every thread is guaranteed to win at some point