Deadlock
gap-in-knowledge It is possible for two program to be hung up waiting for each other.
For example
Two programs may reach require two I/O devices to perform some operations (e.g., disk to tape copy). One of the programs has seized control of one of the devices and the other program to release the desired resource. Such a deadlock may depend on the chance timing of resource allocation and release.
Patrick also gave me the analogy of the Dining philosophers problem. https://howardhinnant.github.io/dining_philosophers.html
→ Five philosophers dine together at the same table. Each philosopher has his own plate at the table. There is a fork between each plate. The dish served is a kind of spaghetti which has to be eaten with two forks. Each philosopher can only alternately think and eat. Moreover, a philosopher can only eat his spaghetti when he has both a left and right fork. Thus two forks will only be available when his two nearest neighbours are thinking, not eating. After an individual philosopher finishes eating, he will put down both forks. The problem is how to design a regimen (a concurrent algorithm) such that any philosopher will not starve; i.e., each can forever continue to alternate between eating and thinking, assuming that no philosopher can know when others may want to eat or think (an issue of incomplete information).
Deadlock avoidance: (Conditions and requirements)
- Maximum resource requirements must be stated in advance
- Processes under consideration must be independent; no synchronization requirements
- There must be a fixed number of resources to allocate
- No process may exit while holding resources
Difference between deadlock avoidance and detection?
Conditions for Deadlock
- Mutual exclusion
- Hold and wait
- No preemption
- Circular Wait