Coffman Conditions

Tags

comp-arch

Are 4 necessary and sufficient conditions for a deadlock:

• Mutual Exclusion: No 2 processes can obtain a resource at the same time.

  If this isn't the case then no process is waiting on another process for a resource since two can acquire it at the same time, thus there's no circular wait and no deadlock.

• Circular Wait: There exists a cycle in the RAG.

  Without a circular wait we know there is no cycle in the RAG, meaning there's at least one process that isn't waiting on a resource to be freed. Since the system can move forward it's not deadlocked.

• Hold and Wait: Once a resource is obtained, a process keeps it locked.

  If this isn't the case then one thread will eventually release a resource and continue meaning it's not deadlocked.

• No pre-emption: Nothing can force a process to give up a resource.

  If we have pre-emption then one or more processes will be forced to give up a resource and therefore the system will proceed and is not deadlocked.

When met there's a non-zero probability that the system will deadlock at any given iteration.