Chapter 12, Problem 12.29HW

Program Plan Intro

Deadlocks:

• The deadlock denotes a situation where a collection of threads remains blocked.
• It denotes waiting for a condition that will never be true.
• The progress graph denotes invaluable tool for understanding deadlock.
• If “P” and “V” operations are been ordered incorrectly, the forbidden regions for two semaphores would overlap.
• If some execution trajectory reaches deadlock state “d” then no further progress is possible.
• In this case each thread waits for the other one for a “V” operation that never occurs.
• The overlapping forbidden regions would induce a set of states called “deadlock region”.
• The deadlock is inevitable is trajectory touches a state in deadlock region.
• Once it enters deadlock regions, the trajectories could never leave.

Mutex lock ordering rule:

• A program is deadlock-free if each thread acquires its mutexes in order.
• It releases them in reverse order and given a total ordering for all mutexes.
• The mutex should be achieved in order to ensure deadlock free scheme.