According to 15-410, deadlock has four requirements:
Mutual Exclusion: Some resource/lock is allocated to one process/thread at a time.
Hold & Wait: Processes/threads must have the potential to hold a lock while waiting for more.
No Preemption: No one is able to "give up" a resource.
Circular Wait: A cycle can be defined in the resource graph (ex, process 0 needs something from process 2, who needs something ... who needs something from process 0).
Deadlock MUST HAVE ALL FOUR REQUIREMENTS to occur.
This comment was marked helpful 1 times.
kayvonf
Absolutely. How do those four conditions manifest in this intersection example?
This comment was marked helpful 0 times.
moon
Mutual Exclusion: Our critical section is space on the road. A space of road can only hold one car at a time.
Hold & Wait: A car "holds" a resource by being on the road. It "waits" for the road it wants to travel on by simply stopping the car until the space is available.
No Preemption: Assuming this intersection deadlock situation only allows cars to move forward, cars cannot give up the road they are on because they have nowhere else to drive to.
Circular Wait: Each car needs the road in front of it to drive forward. Thus, the green cars need the resource occupied by the yellow cars, while the yellow cars need the resources occupied by the green cars, which forms a cycle.
We can note that since the 3rd requirement doesn't hold in real life (since cars can move in reverse), we don't have true deadlock in this situation.
This comment was marked helpful 0 times.
ron
We can divide the intersection into four quarters of space, and treat each of those as a resource. Then,
Mutual Exclusion : Each unit of road space in the intersection is being held by a car, and each of those units can be held by at most one car at a time.
Hold & Wait : A car holds a unit of road space, and can choose to remain there (assuming the civility of other road users :D), while waiting for the next road space it intends to consume to free up. In this situation, the green cars are holding a quarter of the intersection each, and each is waiting for a quarter being held by the yellow cars, and vice versa.
No pre-emption : This one is slightly confusing; each car is in fact able to back-up and so "give up" its resource. It makes more sense if you think of it in terms of a supervisor/operating system; no pre-emption on Wikipedia is defined as 'The operating system must not de-allocate resources once they have been allocated; they must be released by the holding process voluntarily'. In this example, I suppose you could say that there's no supervising traffic light that'll force the green cars to back up and allow the yellow cars to pass. Each car has complete, individual control over whether or not to give up its resource.
Circular wait : Each car is waiting for the road-space being held by its counter-clockwise adjacent neighbor.
According to 15-410, deadlock has four requirements:
Mutual Exclusion: Some resource/lock is allocated to one process/thread at a time.
Hold & Wait: Processes/threads must have the potential to hold a lock while waiting for more.
No Preemption: No one is able to "give up" a resource.
Circular Wait: A cycle can be defined in the resource graph (ex, process 0 needs something from process 2, who needs something ... who needs something from process 0).
Deadlock MUST HAVE ALL FOUR REQUIREMENTS to occur.
This comment was marked helpful 1 times.
Absolutely. How do those four conditions manifest in this intersection example?
This comment was marked helpful 0 times.
Mutual Exclusion: Our critical section is space on the road. A space of road can only hold one car at a time.
Hold & Wait: A car "holds" a resource by being on the road. It "waits" for the road it wants to travel on by simply stopping the car until the space is available.
No Preemption: Assuming this intersection deadlock situation only allows cars to move forward, cars cannot give up the road they are on because they have nowhere else to drive to.
Circular Wait: Each car needs the road in front of it to drive forward. Thus, the green cars need the resource occupied by the yellow cars, while the yellow cars need the resources occupied by the green cars, which forms a cycle.
We can note that since the 3rd requirement doesn't hold in real life (since cars can move in reverse), we don't have true deadlock in this situation.
This comment was marked helpful 0 times.
We can divide the intersection into four quarters of space, and treat each of those as a resource. Then,
This comment was marked helpful 0 times.