patternMinor
Bounded waiting and starvation free in critical section problem
Viewed 0 times
problemcriticalsectionfreestarvationwaitingandbounded
Problem
I have 4 questions regarding relation between starvation and bounded waiting.
1.Does starvation-freedom imply deadlock-freedom?
My Answer:
From here,
definition of starvation free is
Freedom from Starvation -:Every thread that attempts to acquire the lock eventually succeeds
Freedom from Deadlock -:for 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.
So, I can state that starvation-freedom imply deadlock-freedom
2.Does starvation-freedom imply bounded-waiting?
Approach-:
Starvation free implies that every thread that will attempt to acquire lock will succeed.
On the other hand
Bounded wait insures that there exists a bound, or limit, on the number of times other processes are allowed to enter their critical sections
after a process has made request to enter its critical section and before that request is granted.
Which implies that there must not be any starvation.
Am i correct? But the explanation is here confuses me.
1.Does starvation-freedom imply deadlock-freedom?
My Answer:
From here,
definition of starvation free is
Freedom from Starvation -:Every thread that attempts to acquire the lock eventually succeeds
Freedom from Deadlock -:for 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.
So, I can state that starvation-freedom imply deadlock-freedom
2.Does starvation-freedom imply bounded-waiting?
Approach-:
Starvation free implies that every thread that will attempt to acquire lock will succeed.
On the other hand
Bounded wait insures that there exists a bound, or limit, on the number of times other processes are allowed to enter their critical sections
after a process has made request to enter its critical section and before that request is granted.
Which implies that there must not be any starvation.
Am i correct? But the explanation is here confuses me.
Solution
No, starvation-free doesn't imply bounded waiting.
For instance, consider a procedure that never even attempts to acquire any lock; but the amount of time it takes is variable and can be arbitrarily long. Then there is no bound on the amount of time it might take to complete its operation.
Here is another example of how it can fail. Starvation-free means that every attempt to acquire the lock eventually succeeds -- but that says nothing about how long it might take. Maybe the amount of time it will take to acquire the lock is variable and can be arbitrarily long -- there is no upper bound on how long it takes to acquire the lock. Then a procedure that first attempts to acquire the lock before doing anything else won't satisfy bounded waiting.
For instance, consider a procedure that never even attempts to acquire any lock; but the amount of time it takes is variable and can be arbitrarily long. Then there is no bound on the amount of time it might take to complete its operation.
Here is another example of how it can fail. Starvation-free means that every attempt to acquire the lock eventually succeeds -- but that says nothing about how long it might take. Maybe the amount of time it will take to acquire the lock is variable and can be arbitrarily long -- there is no upper bound on how long it takes to acquire the lock. Then a procedure that first attempts to acquire the lock before doing anything else won't satisfy bounded waiting.
Context
StackExchange Computer Science Q#71703, answer score: 4
Revisions (0)
No revisions yet.