Introduction to Deadlocks

Formal definition :
A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause

•Usually the event is release of a currently held resource

•None of the processes can …

–run

–release resources

–be awakened

Four Conditions for Deadlock

1.Mutual exclusion condition

•each resource assigned to 1 process or is available

2.Hold and wait condition

•process holding resources can request additional

3.No preemption condition

•previously granted resources cannot forcibly taken away

4.Circular wait condition

•must be a circular chain of 2 or more processes

•each is waiting for resource held by next member of the chain

Deadlock Modeling

•Modeled with directed graphs

–resource R assigned to process A

–process B is requesting/waiting for resource S

–process C and D are in deadlock over resources T and U