Semaphore

Question

Will it causing deadlock? How do we fixed it?

P1:                                   P2:

Wait(S);                               Wait(Q);                     
Wait(Q);                               Wait(S);
........                               .............
Signal(S);                             Signal(Q);
Signal(Q);                             Signal(S);

 

Comments

yes , it leads a deadlock

how do we fixed  ?

P1:                                   P2:

Wait(S);                               Wait(S);                     
Wait(Q);                               Wait(Q);
........                               .............
Signal(S);                             Signal(Q);
Signal(Q);                             Signal(S);

 

 

---

plz describe more

---

but if use this

P1:                                   P2:

Wait(S);                               Wait(S);                     
Wait(Q);                               Wait(Q);
........                               .............
Signal(S);                             Signal(Q);
Signal(Q);                             Signal(S);

it doesn't lead any deadlock you check it out this condition in same manner

srestha  mam check

 

---

@srestha

a more conceptual way to understand it is as... give the lexicographic order to P & Q. say either p=1 & q= 2 or either q=1 & p=2. and we know that no deadlock will be there if we ensure that processes are requesting for resource in lexicographic order, as no circular wait would be there. so there are 2 ways for avoid deadlock here... either swap p's wait or swap q's wait.

---

It depends

1) If S and Q are binary semaphores and either of one is 0 then there is a deadlock.

2)  If S=1 and Q=1 and they are binary semaphores now

X1: Wait(S) (First line of process P1)

X2: Wait(Q) (First line of process P2)

Now consider following sequence of execution X1->X2 or X2->X1 if any one of the sequence is executed then there is a deadlock.

 

Now how to fix it

1) Make S and Q as counting Semaphore and make (S=1 and Q=2 or S=2 and Q=1)

2) If you want to keep S and Q as binary semaphore then swap first 2 line of either process P1 or P2 but not both

---

@Magma

Then both process can be in CS in same time . So, ME, and progress will be violated and no synchronization will be there

@ aambazinga

why lexicographic order has no deadlock?

@Tesla

If counting semaphore then initial value can be 1,2,3 or anything and any number of process can be in CS at the same time. So, no ME, Progress or BW

---

Then both process can be in CS in same time . So, ME, and progress will be violated and no synchronization will be there

How ??? In which case ??

---

Yes in counting  semaphore you can have any value but value that I have mentioned is one of the possible solution

---

@Tesla!

Is there any problem in Magma's solution? It will be deadlock free right? Please check once.

---

Magma answer won't have a deadlock its also one of the possible solution.

---

yeah there is no problem in @Magma solution.