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 semaphore\\ Thread1 ... ...ta & // access\\ 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)