Deadlock, postponement, prevention, 2 processes

Deadlock (1 mark)

Deadlock is a state where each process of a set waits for a resource held by another process of the set, so none can continue.

Indefinite postponement (1 mark)

A process is delayed repeatedly, for an unbounded time, while other processes are served (also called starvation). Example: a low-priority process never scheduled because high-priority ones keep arriving. Unlike deadlock, the system as a whole keeps working.

Necessary conditions (3 marks)

1. Mutual exclusion: a resource is used by one process at a time.
2. Hold and wait: a process holds resources while requesting more.
3. No preemption: a resource cannot be taken away forcibly.
4. Circular wait: a circular chain of waiting processes exists.

Prevention (3 marks)

• Remove mutual exclusion by spooling.
• Remove hold and wait: request all resources at once.
• Allow preemption of resources.
• Impose a total ordering on resources and request in order, which prevents circular wait.

Two processes, three resources (2 marks)

Each process needs at most 2 resources. Worst case: each process holds 1 resource and waits for its second one. Together they hold 2 resources, so 3 − 2 = 1 resource is free. That free resource can be given to either process, which then has its 2 resources, finishes and releases both. The other process then gets its second resource.

 P1 holds 1 | P2 holds 1 | 1 free
 give free to P1 -> P1 finishes, releases 2
 P2 now gets its second -> finishes

In general, deadlock-free if Σ(maxᵢ − 1) + 1 ≤ R, i.e. (2−1)+(2−1)+1 = 3 ≤ 3.

Answer: Deadlock is not possible, because at least one process can always obtain its maximum need.