List the three phases of resource use in the system model
Request → Use → Release.
What are resource types and instances?
A resource type is a category of resource (e.g., printer, mutex, CPU). An instance is one specific unit of that type (e.g., Printer #1).
Mutual Exclusion
At least one resource must be nonsharable—only one process can use it at a time.
Hold + Wait
A process holds one or more resources while waiting to acquire additional resources.
No Preemption
Resources can’t be forcibly taken from a process; they must be released voluntarily.
Circular Wait
A cycle of processes exists where each waits for a resource held by the next process in the cycle.
Can we deny mutual exclusion to prevent deadlock?
Only for resources that can be made sharable; many resources (e.g., mutexes, printers) are inherently nonsharable.
Prevention for hold and wait and it’s downside: describe Method 1
Require a process to request all resources it needs at once before it begins execution. Downside: Low resource utilization and potential starvation because resources may be held even when not immediately used.
Prevention for hold and wait and it’s downside: describe Method 2
Require a process to release all held resources before requesting any new ones. Downside: More overhead and delays; can reduce throughput and still risk starvation.
Prevention for no preemption + Downside
If a process holding resources requests another unavailable resource, preempt its held resources and make the process retry later. Downside: Not practical for many resources and can cause overhead or starvation.
Prevention for circular wait: what is the key idea?
Impose a total ordering of resource types and require processes to request resources only in increasing order.
What simple rule prevents circular wait when using two locks?
Always acquire the two locks in the same fixed order (e.g., Lock A then Lock B).
Request Edge
Pi → Rj means process Pi is requesting an instance of resource type Rj.
Assignment Edge
Rj → Pi means an instance of resource type Rj is allocated to process Pi.
Single Instance + No Cycle
= No Deadlock, if there is no cycle, deadlock cannot occur.
Single Instance + Cycle
= Deadlock, when each resource type has one instance, a cycle implies deadlock.
Multiple Instances + Cycle
= Possible Deadlock, True—cycle indicates possible deadlock, not guaranteed.
Safe State
A state where a safe sequence exists—processes can finish one by one using available resources plus resources released by earlier processes.
Unsafe State
A state where no safe sequence exists—deadlock is possible in the future but not guaranteed yet.
Deadlock Avoidance
Dynamically decide whether to grant requests based on maximum needs so the system never enters an unsafe state.
Deadlock Prevention
Design rules that ensure at least one of the four necessary deadlock conditions can never hold.
Deadlock Detection and Recovery
Allow deadlock to occur, detect it (e.g., via graph/algorithm), then recover by preempting, aborting, or rolling back processes.
Ignoring Deadlock
The OS does not try to prevent or detect deadlock and relies on the fact that deadlocks are rare or manageable.
Which strategy is used by most mainstream OSes?
Ignoring deadlock for many general-purpose resources (the “ostrich approach”).
