dead-lock free vs. starvation free

Question

Can it happen that mutual exclusion algorithm doesn`t maintain dead-lock free property,but it maintains starvation freedom ?

Thank you

Answer 1

Starvation-freedom can be defined as: Whatever the process p, each invocation of acquire_mutex() issused by p eventually terminates. OR Any process trying to enter critical section, will eventually enter critical section.

Deadlock-freedom: Whatever the time T , if before T one or several processes have invoked the operation acquire_mutex() and none of them has terminated its invocation at time T , then there is a time T' > T at which a process that has invoked acquire_mutex() terminates its invocation.[Raynal, Concurrent Programming: Algorithms, Principles, and Foundations] OR If process is trying to enter critical section, then some process, not necessary same one, eventually will enter critical section. OR At least one, always wins.

Notice, that deadlock-freedom is saying that there are some processes will make progresses, but others might be stuck(starving), trying to get into critical section. It sound weird at first, but it is so: not all threads are stuck, so there is no deadlock, i.e. deadlock-freedom.

On other hand, starvation-freedom is saying that every process trying to get into critical section, will eventually do so. There will be no processes that will ever starve.

This makes starvation-freedom much stronger property than deadlock-freedom.

Answer to your question is NO.

Answer 2

No—every reasonable definition of starvation includes deadlock.