HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Does Deadlock imply Starvation

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
deadlockimplydoesstarvation

Problem

If there is a deadlock between the processes does that mean that there is starvation also?

My Thinking:

deadlock is no process using that resources , but starvation is like not giving chance to only that process so there is progress in starvation but not in deadlock

Is my thinking right?

Solution

You should first state the deadlock freedom property and the starvation freedom property more precisely.

I use the definition in the Book: The Art of Multiprocessor Programming; Section 2.2.

Freedom from Deadlock If some thread attempts to acquire the lock, then some thread (not necessarily the thread referred to in the if statement; emphasis added) will succeed in acquiring the lock.

Freedom from Starvation Every thread that attempts to acquire the lock eventually succeeds.

Note that by definition, starvation freedom implies deadlock freedom. Thus, if a mutual exclusion algorithm suffers from deadlock, it also suffers from starvation.

A direct argument is that: deadlock means that some thread attempts to acquire the lock, but no threads succeed. That is a special kind of starvation.

Context

StackExchange Computer Science Q#67406, answer score: 12

Revisions (0)

No revisions yet.