Can someone explain to me what Starvation free means compared to deadlocks?

I need to modify this deadlock answer so that is starvation free....

A mutex semaphore is all that will be needed to solve this problem. When a driver comes to the bridge they will reserve or request the semaphore. If they get the semaphore request, they will cross the bridge; once they have crossed the bridge they will give away or release the semaphore. If they don’t give it away, they will wait until they have received the semaphore.

how can this be modified to starvation free?

5 Years
Discussion Span
Last Post by Thermalnuke

School class exercise? So, define your terms. What do YOU mean by "starvation free"? What do you understand to be the relationship between deadlock and "starvation". These are broad terms, and are relevant to the environment, and specific situation in which you encounter them.

FWIW, typically "starvation free" refers to the fact that readers of a resource are not gated (blocked) by the writers of the resource. IE, until the writer has "committed" the changes to the resource, the reader will still be able to access the pre-commit state of the data. In your example, you have described a situation where starvation can occur, in that if the crosser of the bridge does not release the semaphore, no one else can cross, hence "starving" access to the bridge. So, to modify this algorithm to be starvation free, you need to change it so that there are no blockages upon subsequent accesses to the bridge.

This brings up the question, what SHOULD block access to the bridge?


I came up with the solution, kind of like traffic lights as soon as one passes the other one gets the green light to go and it will keep repeating this, while avoiding starvation. trying to figure out another solution right now.


Building upon your traffic light metaphor, around here we have freeways and there are lights (red/green) on the access ramps that normally, when traffic is light, stay green; however, if the traffic is heavy (during rush hour, for example) then the light stays red for some period, and then green to let one or two cars onto the freeway, and then change back to red for awhile. Effectively, this allows the freeway to attain the maximum throughput and not slow traffic down too much. So, some sort of adaptive metered access is what you are looking for?

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.