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

Subjectify

What is your definition of starvation? – Weixel

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.

Dobby

Well explained! Let me try make a TLDR version here: Deadlock-free: at least one thread is not starving at any given time. Starvation-free: No thread will get starved. – Deepsea

Example of non-deadlock starving: LIFO style mutex, newer mutex waiter enters the critial section first and there have always been more than one waiter. Thus the first waiter never get a chance to enter the critical section and thus starves. – Deepsea

Answer 2

No—every reasonable definition of starvation includes deadlock.

Ingathering