2
$\begingroup$

Let's suppose there are N processes and we have the following code:

atomic <int> c = 0;
semaphore b = 0;

proc P(i){
   ...
   if(c.getAndInc() < N - 1){
      b.wait();
   }
   else{
      b.signal();
   }
   ...
}

A deadlock will occur as N - 2 processes will be blocked by $ b.wait() $. I'm trying to identify how the Circular wait condition holds, being a necessary condition as it is.

(Circular wait means that "A set $\{ P_0, P_1, ..., P_n \}$ of waiting processes must exist such that $P_0$ is waiting for a resource held by $P_1$, $P_1$ is waiting for a resource held by $P_2$, ..., $P_{n-1}$ is waiting for a resource held by $P_n$, and $P_n$ is waiting for a resource held by $P_0$". This quote is from the book "Operating System Concepts", by Silberschatz, Galvin and Gagne.)

In other words, as there is deadlock, the circular wait condition must hold, but I just don't see it. Is there anything I am misunderstanding?

Thanks!

$\endgroup$
  • $\begingroup$ Note that the presence of the 4 conditions depends on whether or not it actually is possible to have a given condition in a given system, for example it is not always possible to request other resources while already holding one. This may be the case here. If that is the case, then 3 of the other 3 possible conditions do hold thus causing a deadlock. $\endgroup$ – Charmaine N Ndolo Aug 1 '17 at 21:39
0
$\begingroup$

Considering the definition of circularity you exposed, it is important to highlight that ownership is not implemented in semaphores (it is for mutexes). So, in a way, each task is waiting for each other because each one has the possibility to "release" (i.e. perform a post to the semaphore since it starts from $0$) the resource (only if the condition inside the "if" is not satisfied). Extending this approach, also the task itself has the possibility to post to the semaphore. Moreover, note that the deadlock is present when $N>2$.

$\endgroup$
  • $\begingroup$ Can you expand on your answer? Note also that you can use MathJax for inline math. $\endgroup$ – Yuval Filmus Dec 15 '18 at 19:18
  • $\begingroup$ You should add this to your actual answer. $\endgroup$ – Yuval Filmus Dec 15 '18 at 20:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.