If mutual exclusion is guaranteed, say with semaphores, is a program deadlock-free?

Question

I define mutual exclusion and deadlock as below, respectively: The mutual exclusion condition exists if at every moment, each shared resource is either assigned to exactly one process, or available. 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.

Say, binary semaphores are used, ensuring that only one of them can enter its critical region at the same time. Since each process does a down just before entering its critical region and an up just after leaving it, mutual exclusion is guaranteed.

I understand there are four conditions which must all hold for deadlock to occur, one of which is the mutual exclusion condition (no two processes may be simultaneously inside their critical sections).

Since mutual exclusion is guaranteed, is the program, in this case, deadlock-free?

Regards.

Answer 1

Not necessarily. Imagine these two threads:

 Thread 1          Thread 2
 ============      =============
 Acquire A         Acquire B
 Acquire B         Acquire A
 Release B         Release A
 Release A         Release B

Here, mutual exclusion is indeed guaranteed - at each instant, semaphores A and B are either owned by one of the threads or available systemwide - but deadlock is still possible if Thread 1 and 2 each acquire their first lock (A for Thread 1, B for Thread 2), but then will deadlock waiting for the resource that the other is holding.

Hope this helps!