Is this a deadlock?

Question

Consider we have two processes P1 and P2. There are also two semaphores M and N which are initialized to zero. Here's how they execute:

+-----------+-----------+
|    P1     |    P2     |
+-----------+-----------+
| wait(M)   | wait(N)   |
| ...       | ...       |
| wait(N)   | wait(M)   |
| ...       | ...       |
| signal(N) | signal(M) |
| signal(M) | signal(N) |
+-----------+-----------+

So neither of the process will go through the first statement because the value of both M and N are zero, so they both get blocked.

But if the initialization value for both M and N were 1, then they successfully execute, with no deadlock.

Can this be considered deadlock solely because of the faulty initialization of the semaphore?

Answer 1

Assuming the semaphore only has 1 slot, Yes it can lead to Deadlock

Improper use of semaphores with wait queues can cause deadlock, As a good programming practice, a semaphore should be initialized once at the very beginning of your program and before the threads which use it are created. It is a bad practice to reinitialize semaphores in the middle of program execution.

Deadlock means a group of processes are all waiting for each other for some event.

For example (the following system has the potential for deadlock; see Deadlock.java):

Semaphore s=1, q=1

process p0 {     
   s.acquire();
   q.acquire();
   ...        
   s.release();
   q.release();
}

process p1 {     
   q.acquire();
   s.acquire();
   ...        
   q.release();
   s.release();
}

If p0 executes S.acquire(), then p1 executes Q.acquire(), the processes become deadlocked.

Solution:

Semaphore s=1, q=1;

process p0 {           
   // order matters a great deal on the waits
   q.acquire();                   
   s.acquire();                  
   ...                         
   // order does not matter that much on the signals 
   s.release();                 
   q.release();               
}

process p1 {           
   // order matters a great deal on the waits
   q.acquire();                   
   s.acquire();                  
   ...                         
   // order does not matter that much on the signals 
   q.release();                 
   s.release();               
}

Contrast deadlock with livelock, where a thread continuously attempts an action that fails.

A single semaphore will not deadlock unless it is being misused.

Semaphores Deadlock

Answer 2

It is a possible deadlock. There will be an actual deadlock if each process manages to execute one “wait” before the other one manages to execute the second “wait”.

That will happen if both processes try to run their code at almost exactly the same time. Since this is very time dependent, that kind of code will deadlock very rarely - which makes that kind of problem very hard to reproduce and therefore very hard to fix.