SGG 8 – Deadlock
8.1 System Model
How do we define what deadlock is and how does it arise in the context of resource management?
You should be able to explain the following concepts and to construct scenarios that exemplify them:
- Blocking
- Deadlock
- Livelock
- Spinlock
8.2 Deadlock In Multithreaded Applications
This section includes a very straightforward cyclic dependency that leads to deadlock.
Separately (8.2.1): Describe how livelock is distinct from deadlock.
8.3 Deadlock Characterization
78.3.1 Explain the four necessary conditions that have to hold in order for a group of processes P that works with a collection of resources R to be in deadlock.
8.3.2 Given a resource-allocation graph, can you determine whether there is deadlock or the potential for deadlock? You need how to use the graphic conventions for creating resource-allocation graphs.
8.4 Methods for Handling Deadlock
There are three ways to deal with deadlock:
- Prevent or avoid deadlock.
- Allow deadlock to happen but provide a recovery mechanism to put the system back in operation.
- Live in denial and assume and pretend that nothing bad is going to happen.
You need to be able to compare the concepts of deadlock prevention and avoidance.
8.5 Deadlock Prevention
Given a mechanism for dealing with deadlock, you should be able to tell whether it can be categorized as a prevention technique.
8.6 Deadlock Avoidance
Given a mechanism for dealing with deadlock, you should be able to tell whether it can be categorized as a avoidance technique.
Given a formal description of the state of the system, you should be able to recognize it as safe or unsafe. Interpreting a resource-allocation graph is one of the methods for checking whether a state is safe. Another one is the Banker’s safety algorithm, which you need to understand and execute “by hand.” You should also know the Banker’s algorithm for dealing with resource requests and understand how/when it is used.
8.7 Deadlock Detection
If the possibility of deadlock exists, the system can opt to take action to detect if it has happened. This section presents an algorithm for this purpose. The big points to get here are how can we determine the tradeoffs involved in running it and to propose some intelligent strategy for dealing with them.
8.8 Deadlock Recovery
If deadlock happens, what can the system do to get out of it? What are the possible solutions and the consequences associated with each one?
