Deadlock

• Deadlock is defined as the permanent blocking of a set of processes that compete for system resources, including database records or communication lines
• Unlike other problems in multiprogramming systems, there is no efficient solution to the deadlock problem in the general case
• Deadlock prevention, by design, is the ``best'' solution
• Deadlock occurs when a set of processes are in a wait state, because each process is waiting for a resource that is held by some other waiting process
• None will release what they hold until they get what they are waiting for
• Therefore, all deadlocks involve conflicting resource needs by two or more processes
• Example: Unordered Mutex; Two threads accessing two locks
  $$\begin{array}{ll} Semaphore ~m[2] = \{1,1\}; & // binary sem... ... m[1].V(); & m[0].V();\\ m[0].V(); & m[1].V();\\ \end{array}$$
• What happens if Thread1 grabs $m[0]$ and Thread2 grabs $m[1]$? (P means down operation and V means up operation)